aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Vectorize
AgeCommit message (Collapse)Author
2013-04-23LoopVectorizer: Fix 15830. When scalarizing and unrolling stores make sure ↵Nadav Rotem
that the order in which the elements are scalarized is the same as the original order. This fixes a miscompilation in FreeBSD's regex library. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180121 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-23Call the potentially costly isAnnotatedParallel() only once. Pekka Jaaskelainen
Made the uniform write test's checks a bit stricter. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180119 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-23Refuse to (even try to) vectorize loops which have uniform writes,Pekka Jaaskelainen
even if erroneously annotated with the parallel loop metadata. Fixes Bug 15794: "Loop Vectorizer: Crashes with the use of llvm.loop.parallel metadata" git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180081 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-22Move C++ code out of the C headers and into either C++ headersEric Christopher
or the C++ files themselves. This enables people to use just a C compiler to interoperate with LLVM. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180063 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-21SLPVectorize: Add support for vectorization of casts.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179975 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-21SLPVectorizer: Fix a bug in the code that scans the tree in search of nodes ↵Nadav Rotem
with multiple users. We did not terminate the switch case and we executed the search routine twice. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179974 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20Fix PR15800. Do not try to vectorize vectors and structs.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179960 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20VecUtils: Clean up uses of dyn_cast.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179936 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20SLPVectorizer: Strength reduce SmallVectors to ArrayRefs.Benjamin Kramer
Avoids a couple of copies and allows more flexibility in the clients. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179935 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20SLPVectorizer: Reduce the compile time by eliminating the search for some of ↵Nadav Rotem
the more expensive patterns. After this change will only check basic arithmetic trees that start at cmpinstr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179933 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20refactor tryToVectorizePair to a new method that supports vectorization of ↵Nadav Rotem
lists. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179932 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20Fix an unused variable warning.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179931 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20SLPVectorizer: Improve the cost model for loop invariant broadcast values.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179930 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20Report the number of stores that were found in the debug message.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179929 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20Fix the header comment.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179928 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-20Use 64bit arithmetic for calculating distance between pointers.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179927 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-19LoopVectorizer: Use matcher from PatternMatch.h for the min/max patternsArnold Schwaighofer
Also make some static function class functions to avoid having to mention the class namespace for enums all the time. No functionality change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179886 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-18Fix a -Wdocumentation warningDmitri Gribenko
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179789 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-18LoopVectorizer: Recognize min/max reductionsArnold Schwaighofer
A min/max operation is represented by a select(cmp(lt/le/gt/ge, X, Y), X, Y) sequence in LLVM. If we see such a sequence we can treat it just as any other commutative binary instruction and reduce it. This appears to help bzip2 by about 1.5% on an imac12,2. radar://12960601 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179773 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-18LoopVectorize: Use a set to avoid longer cycles in the reduction chain too.Benjamin Kramer
Fixes PR15748. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179757 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-15SLPVectorizer: Make it a function pass and add code for hoisting the ↵Nadav Rotem
vector-gather sequence out of loops. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179562 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-15SLPVectorizer: Add support for vectorizing trees that start at compare ↵Nadav Rotem
instructions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179504 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-14Miscellaneous cleanups for VecUtils.hBenjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179483 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-14SLP: Document the scalarization cost method.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179479 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-14SLPVectorizer: Add support for trees that don't start at binary operators, ↵Nadav Rotem
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
2013-04-14SLPVectorizer: add initial support for reduction variable vectorization.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179470 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-12SLPVectorizer: add support for vectorization of diamond shaped trees. We now ↵Nadav Rotem
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
2013-04-12Add debug prints.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179412 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-12LoopVectorizer: integer division is not a reduction operationArnold Schwaighofer
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
2013-04-11Rename the C function to create a SLPVectorizerPass to something sane and ↵Benjamin Kramer
expose it in the header file. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179272 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-10Make the SLP store-merger less paranoid about function calls. We check for ↵Nadav Rotem
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
2013-04-10We require DataLayout for analyzing the size of stores.Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@179206 91177308-0d34-0410-b5e6-96231b3b80d8
2013-04-09Add support for bottom-up SLP vectorization infrastructure.Nadav Rotem
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
2013-04-04LoopVectorizer: Pass OperandValueKind information to the cost modelArnold Schwaighofer
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
2013-03-14LoopVectorize: Invert case when we use a vector cmp value to query select costArnold Schwaighofer
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
2013-03-10BBVectorize: Fixup debugging statementsHal Finkel
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
2013-03-09Remove a source of nondeterminism from the LoopVectorizer.Benjamin Kramer
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
2013-03-09LoopVectorizer: Ignore all dbg intrinisicArnold Schwaighofer
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
2013-03-09LoopVectorizer: Ignore dbg.value instructionsArnold Schwaighofer
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
2013-03-08Insert the reduction start value into the first bypass block to preserve ↵Benjamin Kramer
domination. Fixes PR15344. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176701 91177308-0d34-0410-b5e6-96231b3b80d8
2013-03-02PR14448 - prevent the loop vectorizer from vectorizing the same loop twice.Nadav Rotem
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
2013-03-01LoopVectorize: Don't hang forever if a PHI only has skipped PHI uses.Benjamin Kramer
Fixes PR15384. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@176366 91177308-0d34-0410-b5e6-96231b3b80d8
2013-02-27LoopVectorize: Vectorize math builtin calls.Benjamin Kramer
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
2013-02-21Allow GlobalValues to vectorize with AliasAnalysisRenato Golin
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
2013-02-17BBVectorize: Fix an invalid reference bugHal Finkel
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
2013-02-15BBVectorize: Call a DAG and DAG instead of a treeHal Finkel
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
2013-02-15BBVectorize: Cap the number of candidate pairs in each instruction groupHal Finkel
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
2013-02-14BBVectorize: Remove the remaining instances of std::multimapHal Finkel
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
2013-02-14BBVectorize: Don't store candidate pairs in a std::multimapHal Finkel
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
2013-02-13LoopVectorize: Simplify code for clarity.Benjamin Kramer
No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@175076 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-22 10:45:19 +0000