| Age | Commit message (Collapse) | Author |
|---|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179479 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
and add the cost of extracting values from the roots of the tree.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179475 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179470 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
perform a preliminary traversal of the graph to collect values with multiple users and check where the users came from.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179414 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179412 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Don't classify idiv/udiv as a reduction operation. Integer division is lossy.
For example : (1 / 2) * 4 != 4/2.
Example:
int a[] = { 2, 5, 2, 2}
int x = 80;
for()
x /= a[i];
Scalar:
x /= 2 // = 40
x /= 5 // = 8
x /= 2 // = 4
x /= 2 // = 2
Vectorized:
<80, 1> / <2,5> //= <40,0>
<40, 0> / <2,2> //= <20,0>
20*0 = 0
radar://13640654
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179381 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
expose it in the header file.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179272 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
function calls when we check if it is safe to sink instructions.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179207 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179206 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This commit adds the infrastructure for performing bottom-up SLP vectorization (and other optimizations) on parallel computations.
The infrastructure has three potential users:
1. The loop vectorizer needs to be able to vectorize AOS data structures such as (sum += A[i] + A[i+1]).
2. The BB-vectorizer needs this infrastructure for bottom-up SLP vectorization, because bottom-up vectorization is faster to compute.
3. A loop-roller needs to be able to analyze consecutive chains and roll them into a loop, in order to reduce code size. A loop roller does not need to create vector instructions, and this infrastructure separates the chain analysis from the vectorization.
This patch also includes a simple (100 LOC) bottom up SLP vectorizer that uses the infrastructure, and can vectorize this code:
void SAXPY(int *x, int *y, int a, int i) {
x[i] = a * x[i] + y[i];
x[i+1] = a * x[i+1] + y[i+1];
x[i+2] = a * x[i+2] + y[i+2];
x[i+3] = a * x[i+3] + y[i+3];
}
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179117 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Pass down the fact that an operand is going to be a vector of constants.
This should bring the performance of MultiSource/Benchmarks/PAQ8p/paq8p on x86
back. It had degraded to scalar performance due to my pervious shift cost change
that made all shifts expensive on x86.
radar://13576547
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@178809 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
We generate a select with a vectorized condition argument when the condition is
NOT loop invariant. Not the other way around.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177098 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
After the recent data-structure improvements, a couple of debugging statements
were broken (printing pointer values).
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176791 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This made us emit runtime checks in a random order. Hopefully bootstrap
miscompares will go away now.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176775 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Ignore all DbgIntriniscInfo instructions instead of just DbgValueInst.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176769 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
We want vectorization to happen at -g. Ignore calls to the dbg.value intrinsic
and don't transfer them to the vectorized code.
radar://13378964
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176768 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
domination.
Fixes PR15344.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176701 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
The LoopVectorizer often runs multiple times on the same function due to inlining.
When this happens the loop vectorizer often vectorizes the same loops multiple times, increasing code size and adding unneeded branches.
With this patch, the vectorizer during vectorization puts metadata on scalar loops and marks them as 'already vectorized' so that it knows to ignore them when it sees them a second time.
PR14448.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176399 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Fixes PR15384.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176366 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This properly asks TargetLibraryInfo if a call is available and if it is, it
can be translated into the corresponding LLVM builtin. We don't vectorize sqrt()
yet because I'm not sure about the semantics for negative numbers. The other
intrinsic should be exact equivalents to the libm functions.
Differential Revision: http://llvm-reviews.chandlerc.com/D465
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176188 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Storing the load/store instructions with the values
and inspect them using Alias Analysis to make sure
they don't alias, since the GEP pointer operand doesn't
take the offset into account.
Trying hard to not add any extra cost to loads and stores
that don't overlap on global values, AA is *only* calculated
if all of the previous attempts failed.
Using biggest vector register size as the stride for the
vectorization access, as we're being conservative and
the cost model (which calculates the real vectorization
factor) is only run after the legalization phase.
We might re-think this relationship in the future, but
for now, I'd rather be safe than sorry.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175818 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This fixes PR15289. This bug was introduced (recently) in r175215; collecting
all std::vector references for candidate pairs to delete at once is invalid
because subsequent lookups in the owning DenseMap could invalidate the
references.
bugpoint was able to reduce a useful test case. Unfortunately, because whether
or not this asserts depends on memory layout, this test case will sometimes
appear to produce valid output. Nevertheless, running under valgrind will
reveal the error.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175397 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Several functions and variable names used the term 'tree' to refer
to what is actually a DAG. Correcting this mistake will, hopefully,
prevent confusion in the future.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175278 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
For some basic blocks, it is possible to generate many candidate pairs for
relatively few pairable instructions. When many (tens of thousands) of these pairs
are generated for a single instruction group, the time taken to generate and
rank the different vectorization plans can become quite large. As a result, we now
cap the number of candidate pairs within each instruction group. This is done by
closing out the group once the threshold is reached (set now at 3000 pairs).
Although this will limit the overall compile-time impact, this may not be the best
way to achieve this result. It might be better, for example, to prune excessive
candidate pairs after the fact the prevent the generation of short, but highly-connected
groups. We can experiment with this in the future.
This change reduces the overall compile-time slowdown of the csa.ll test case in
PR15222 to ~5x. If 5x is still considered too large, a lower limit can be
used as the default.
This represents a functionality change, but only for very large inputs
(thus, there is no regression test).
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175251 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
All instances of std::multimap have now been replaced by
DenseMap<K, std::vector<V> >, and this yields a speedup of 5% on the
csa.ll test case from PR15222.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175216 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This is another commit on the road to removing std::multimap from
BBVectorize. This gives an ~1% speedup on the csa.ll test case
in PR15222.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175215 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
No functionality change.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175076 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
metadata is the loop vectorizer.
See the documentation update for more info.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175060 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
When building the pairable-instruction dependency map, don't search
past the last pairable instruction. For large blocks that have been
divided into multiple instruction groups, searching past the last
instruction in each group is very wasteful. This gives a 32% speedup
on the csa.ll test case from PR15222 (when using 50 instructions
in each group).
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174915 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This map is queried only for instructions in pairs of pairable
instructions; so make sure that only pairs of pairable
instructions are added to the map. This gives a 3.5% speedup
on the csa.ll test case from PR15222.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174914 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This eliminates one more linear search over a range of
std::multimap entries. This gives a 22% speedup on the
csa.ll test case from PR15222.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174893 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This removes the last of the linear searches over ranges of std::multimap
iterators, giving a 7% speedup on the doduc.bc input from PR15222.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174859 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This is another cleanup aimed at eliminating linear searches
in ranges of std::multimap.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174858 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Profiling suggests that getInstructionTypes is performance-sensitive,
this cleans up some double-casting in that function in favor of
using dyn_cast.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174857 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
By itself, this does not have much of an effect, but only because in the default
configuration the full cycle checks are used only for small problem sizes.
This is part of a general cleanup of uses of iteration over std::multimap
ranges only for the purpose of checking membership.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174856 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
This is a follow-up to the cost-model change in r174713 which splits
the cost of a memory operation between the address computation and the
actual memory access. In r174713, this cost is always added to the
memory operation cost, and so BBVectorize will do the same.
Currently, this new cost function is used only by ARM, and I don't
have any ARM test cases for BBVectorize. Assistance in generating some
good ARM test cases for BBVectorize would be greatly appreciated!
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174743 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174723 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Adds a function to target transform info to query for the cost of address
computation. The cost model analysis pass now also queries this interface.
The code in LoopVectorize adds the cost of address computation as part of the
memory instruction cost calculation. Only there, we know whether the instruction
will be scalarized or not.
Increase the penality for inserting in to D registers on swift. This becomes
necessary because we now always assume that address computation has a cost and
three is a closer value to the architecture.
radar://13097204
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174713 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174709 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174671 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
We don't want too many classes in a pass and the classes obscure the details. I
was going a little overboard with object modeling here. Replace classes by
generic code that handles both loads and stores.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174646 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
Introduce a helper class that computes the cost of memory access instructions.
No functionality change intended.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174422 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
In the loop vectorizer cost model, we used to ignore stores/loads of a pointer
type when computing the widest type within a loop. This meant that if we had
only stores/loads of pointers in a loop we would return a widest type of 8bits
(instead of 32 or 64 bit) and therefore a vector factor that was too big.
Now, if we see a consecutive store/load of pointers we use the size of a pointer
(from data layout).
This problem occured in SingleSource/Benchmarks/Shootout-C++/hash.cpp (reduced
test case is the first test in vector_ptr_load_store.ll).
radar://13139343
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@174377 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
to a command line switch.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173837 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
No intended functionality change.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173809 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173691 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
When flipping the pair of subvectors that form a vector, if the
vector length is 2, we can use the SK_Reverse shuffle kind to get
more-accurate cost information. Also we can use the SK_ExtractSubvector
shuffle kind to get accurate subvector extraction costs.
The current cost model implementations don't yet seem complex enough
for this to make a difference (thus, there are no test cases with this
commit), but it should help in future.
Depending on how the various targets optimize and combine shuffles in
practice, we might be able to get more-accurate costs by combining the
costs of multiple shuffle kinds. For example, the cost of flipping the
subvector pairs could be modeled as two extractions and two subvector
insertions. These changes, however, should probably be motivated
by specific test cases.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173621 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173580 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173579 91177308-0d34-0410-b5e6-96231b3b80d8
|
|
duplication.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173500 91177308-0d34-0410-b5e6-96231b3b80d8
|
