summaryrefslogtreecommitdiff
path: root/lib/Transforms/Vectorize/LoopVectorize.cpp
Commit message (Collapse)AuthorAge
* Merging r199570:Tom Stellard2014-04-09
| | | | | | | | | | | | | | | | | | | | ------------------------------------------------------------------------ r199570 | aschwaighofer | 2014-01-18 22:18:31 -0500 (Sat, 18 Jan 2014) | 11 lines LoopVectorizer: A reduction that has multiple uses of the reduction value is not a reduction. Really. Under certain circumstances (the use list of an instruction has to be set up right - hence the extra pass in the test case) we would not recognize when a value in a potential reduction cycle was used multiple times by the reduction cycle. Fixes PR18526. radar://15851149 ------------------------------------------------------------------------ git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_34@205818 91177308-0d34-0410-b5e6-96231b3b80d8
* Merging r197449:Bill Wendling2013-12-17
| | | | | | | | | | | | | | | | | ------------------------------------------------------------------------ r197449 | arnolds | 2013-12-16 17:11:01 -0800 (Mon, 16 Dec 2013) | 7 lines LoopVectorizer: Don't if-convert constant expressions that can trap A phi node operand or an instruction operand could be a constant expression that can trap (division). Check that we don't vectorize such cases. PR16729 radar://15653590 ------------------------------------------------------------------------ git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_34@197453 91177308-0d34-0410-b5e6-96231b3b80d8
* Merging r195787:Bill Wendling2013-12-01
| | | | | | | | | | | | | | | | | | ------------------------------------------------------------------------ r195787 | arnolds | 2013-11-26 14:11:23 -0800 (Tue, 26 Nov 2013) | 8 lines LoopVectorizer: Truncate i64 trip counts of i32 phis if necessary In signed arithmetic we could end up with an i64 trip count for an i32 phi. Because it is signed arithmetic we know that this is only defined if the i32 does not wrap. It is therefore safe to truncate the i64 trip count to a i32 value. Fixes PR18049. ------------------------------------------------------------------------ git-svn-id: https://llvm.org/svn/llvm-project/llvm/branches/release_34@195991 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Extend the induction variable to a larger typeArnold Schwaighofer2013-11-18
| | | | | | | | | | | | | | | | | | | | | | | | | | | In some case the loop exit count computation can overflow. Extend the type to prevent most of those cases. The problem is loops like: int main () { int a = 1; char b = 0; lbl: a &= 4; b--; if (b) goto lbl; return a; } The backedge count is 255. The induction variable type is i8. If we add one to 255 to get the exit count we overflow to zero. To work around this issue we extend the type of the induction variable to i32 in the case of i8 and i16. PR17532 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@195008 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Use abi alignment for accesses with no alignmentArnold Schwaighofer2013-11-15
| | | | | | | | | | | When we vectorize a scalar access with no alignment specified, we have to set the target's abi alignment of the scalar access on the vectorized access. Using the same alignment of zero would be wrong because most targets will have a bigger abi alignment for vector types. This probably fixes PR17878. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194876 91177308-0d34-0410-b5e6-96231b3b80d8
* Move debug message in vectorizerRenato Golin2013-11-11
| | | | | | No functional change, just better reporting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194388 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: Remove quadratic behavior the local CSE.Benjamin Kramer2013-11-02
| | | | | | | | Doing this with a hash map doesn't change behavior and avoids calling isIdenticalTo O(n^2) times. This should probably eventually move into a utility class shared with EarlyCSE and the limited CSE in the SLPVectorizer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193926 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Move cse code into its own functionArnold Schwaighofer2013-11-01
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193895 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Perform redundancy elimination on induction variablesArnold Schwaighofer2013-11-01
| | | | | | | | | | | | | | | | | | | | When the loop vectorizer was part of the SCC inliner pass manager gvn would run after the loop vectorizer followed by instcombine. This way redundancy (multiple uses) were removed and instcombine could perform scalarization on the induction variables. Having moved the loop vectorizer to later we no longer run any form of redundancy elimination before we perform instcombine. This caused vectorized induction variables to survive that did not before. On a recent iMac this helps linpack back from 6000Mflops to 7000Mflops. This should also help lpbench and paq8p. I ran a Release (without Asserts) build over the test-suite and did not see any negative impact on compile time. radar://15339680 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193891 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: Look for consecutive acces in GEPs with trailing zero indicesBenjamin Kramer2013-11-01
| | | | | | | If we have a pointer to a single-element struct we can still build wide loads and stores to it (if there is no padding). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193860 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: If dependency checks fail try runtime checksArnold Schwaighofer2013-11-01
| | | | | | | | | | | | When a dependence check fails we can still try to vectorize loops with runtime array bounds checks. This helps linpack to vectorize a loop in dgefa. And we are back to 2x of the scalar performance on a corei7-avx. radar://15339680 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193853 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Clear all member data structures in RuntimeCheck.reset()Arnold Schwaighofer2013-11-01
| | | | | | | | Clear all data structures when resetting the RuntimeCheck data structure. No test case. This was exposed by an upcomming change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193852 91177308-0d34-0410-b5e6-96231b3b80d8
* Quick look-up for block in loop.Wan Xiaofei2013-10-26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch implements quick look-up for block in loop by maintaining a hash set for blocks. It improves the efficiency of loop analysis a lot, the biggest improvement could be 5-6%(458.sjeng). Below are the compilation time for our benchmark in llc before & after the patch. Benchmark llc - trunk llc - patched 401.bzip2 0.339081 100.00% 0.329657 102.86% 403.gcc 19.853966 100.00% 19.605466 101.27% 429.mcf 0.049823 100.00% 0.048451 102.83% 433.milc 0.514898 100.00% 0.510217 100.92% 444.namd 1.109328 100.00% 1.103481 100.53% 445.gobmk 4.988028 100.00% 4.929114 101.20% 456.hmmer 0.843871 100.00% 0.825865 102.18% 458.sjeng 0.754238 100.00% 0.714095 105.62% 464.h264ref 2.9668 100.00% 2.90612 102.09% 471.omnetpp 4.556533 100.00% 4.511886 100.99% bitmnp01 0.038168 100.00% 0.0357 106.91% idctrn01 0.037745 100.00% 0.037332 101.11% libquake2 3.78689 100.00% 3.76209 100.66% libquake_ 2.251525 100.00% 2.234104 100.78% linpack 0.033159 100.00% 0.032788 101.13% matrix01 0.045319 100.00% 0.043497 104.19% nbench 0.333161 100.00% 0.329799 101.02% tblook01 0.017863 100.00% 0.017666 101.12% ttsprk01 0.054337 100.00% 0.053057 102.41% Reviewer : Andrew Trick <atrick@apple.com>, Hal Finkel <hfinkel@anl.gov> Approver : Andrew Trick <atrick@apple.com> Test : Pass make check-all & llvm test-suite git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193460 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Don't attempt to vectorize extractelement instructionsHal Finkel2013-10-25
| | | | | | | | | | | | | | | The loop vectorizer does not currently understand how to vectorize extractelement instructions. The existing check, which excluded all vector-valued instructions, did not catch extractelement instructions because it checked only the return value. As a result, vectorization would proceed, producing illegal instructions like this: %58 = extractelement <2 x i32> %15, i32 0 %59 = extractelement i32 %58, i32 0 where the second extractelement is illegal because its first operand is not a vector. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193434 91177308-0d34-0410-b5e6-96231b3b80d8
* Mark vector loops as already vectorizedRenato Golin2013-10-24
| | | | | | | | Make sure we mark all loops (scalar and vector) when vectorizing, so that we don't try to vectorize them anymore. Also, set unroll to 1, since this is what we check for on early exit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193349 91177308-0d34-0410-b5e6-96231b3b80d8
* Use more type helper functionsMatt Arsenault2013-10-21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193109 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: Properly reflect PODness in comments.Benjamin Kramer2013-10-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192717 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: Add missing INITIALIZE_PASS_DEPENDENCY macrosTobias Grosser2013-10-12
| | | | | | Contributed-by: Peter Zotov <whitequark@whitequark.org> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192536 91177308-0d34-0410-b5e6-96231b3b80d8
* Better info when debugging vectorizerRenato Golin2013-10-11
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192460 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: External uses must use the last value in a reduction cycleArnold Schwaighofer2013-10-07
| | | | | | | | | Otherwise, we don't perform operations that would have been performed on the scalar version. Fixes PR17498. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@192133 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't use runtime bounds check between address spaces.Matt Arsenault2013-10-02
| | | | | | | | | Don't vectorize with a runtime check if it requires a comparison between pointers with different address spaces. The values can't be assumed to be directly comparable. Previously it would create an illegal bitcast. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191862 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix debug printing spacing.Matt Arsenault2013-10-02
| | | | | | Fix missing newlines, missing and extra spaces in printed messages. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191851 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix comment grammar and capitalization.Matt Arsenault2013-10-02
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191850 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove several unused variables.Rafael Espindola2013-10-01
| | | | | | Patch by Alp Toker. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191757 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert manual insert point restores to the new RAII object.Benjamin Kramer2013-09-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191675 91177308-0d34-0410-b5e6-96231b3b80d8
* Even more spelling fixes for "instruction".Robert Wilhelm2013-09-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191611 91177308-0d34-0410-b5e6-96231b3b80d8
* Transforms: Use getFirstNonPHI to set the insertion point for PHIsJustin Bogner2013-09-27
| | | | | | | | | | We were previously using getFirstInsertionPt to insert PHI instructions when vectorizing, but getFirstInsertionPt also skips past landingpads, causing this to generate invalid IR. We can avoid this issue by using getFirstNonPHI instead. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191526 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert "LoopVectorizer: Only allow vectorization of intrinsics."Arnold Schwaighofer2013-09-23
| | | | | | | | | | | | | | Revert 191122 - with extra checks we are allowed to vectorize math library function calls. Standard library indentifiers are reserved names so functions with external linkage must not overrided them. However, functions with internal linkage can. Therefore, we can vectorize calls to math library functions with a check for external linkage and matching signature. This matches what we do during SelectionDAG building. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191206 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Only allow vectorization of intrinsics. We can't know for ↵Nadav Rotem2013-09-21
| | | | | | | | | | sure that the functions 'abs' or 'round' are the functions from libm. rdar://15012650 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@191122 91177308-0d34-0410-b5e6-96231b3b80d8
* Prevent LoopVectorizer and SLPVectorizer running if the target has no vector ↵Robert Lytton2013-09-18
| | | | | | | | | | registers. XCore target: Add XCoreTargetTransformInfo This is where getNumberOfRegisters() resides, which in turn returns the number of vector registers (=0). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190936 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't vectorize if there are outside loop users of the induction variable.Arnold Schwaighofer2013-09-16
| | | | | | | | | | | | We would have to compute the pre increment value, either by computing it on every loop iteration or by splitting the edge out of the loop and inserting a computation for it there. For now, just give up vectorizing such loops. Fixes PR17179. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190790 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't assert on invalid loop vectorization hint.Eli Friedman2013-09-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190450 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: PHI nodes are always at the beginning of a block, no need to ↵Benjamin Kramer2013-09-10
| | | | | | scan the whole block. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190422 91177308-0d34-0410-b5e6-96231b3b80d8
* Disable unrolling in the loop vectorizer when disabled in the pass managerHal Finkel2013-08-28
| | | | | | | | | | | | | | | | | When unrolling is disabled in the pass manager, the loop vectorizer should also not unroll loops. This will allow the -fno-unroll-loops option in Clang to behave as expected (even for vectorizable loops). The loop vectorizer's -force-vector-unroll option will (continue to) override the pass-manager setting (including -force-vector-unroll=0 to force use of the internal auto-selection logic). In order to test this, I added a flag to opt (-disable-loop-unrolling) to force disable unrolling through opt (the analog of -fno-unroll-loops in Clang). Also, this fixes a small bug in opt where the loop vectorizer was enabled only after the pass manager populated the queue of passes (the global_alias.ll test needed a slight update to the RUN line as a result of this fix). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@189499 91177308-0d34-0410-b5e6-96231b3b80d8
* Refactor 'vectorizeLoop' no functionality change.Nadav Rotem2013-08-27
| | | | | | | | This patch merges LoopVectorize of InnerLoopVectorizer and InnerLoopUnroller by adding checks for VF=1. This helps in erasing the Unroller code that is almost identical to the InnerLoopVectorizer code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@189391 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: Implement partial loop unrolling when vectorization is not ↵Nadav Rotem2013-08-26
| | | | | | | | | | | | | | | | | | profitable. This patch enables unrolling of loops when vectorization is legal but not profitable. We add a new class InnerLoopUnroller, that extends InnerLoopVectorizer and replaces some of the vector-specific logic with scalars. This patch does not introduce any runtime regressions and improves the following workloads: SingleSource/Benchmarks/Shootout/matrix -22.64% SingleSource/Benchmarks/Shootout-C++/matrix -13.06% External/SPEC/CINT2006/464_h264ref/464_h264ref -3.99% SingleSource/Benchmarks/Adobe-C++/simple_types_constant_folding -1.95% git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@189281 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach LoopVectorize about address space sizesMatt Arsenault2013-08-22
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188980 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a llvm.copysign intrinsicHal Finkel2013-08-19
| | | | | | | | | | | | | | | | | | | | | This adds a llvm.copysign intrinsic; We already have Libfunc recognition for copysign (which is turned into the FCOPYSIGN SDAG node). In order to autovectorize calls to copysign in the loop vectorizer, we need a corresponding intrinsic as well. In addition to the expected changes to the language reference, the loop vectorizer, BasicTTI, and the SDAG builder (the intrinsic is transformed into an FCOPYSIGN node, just like the function call), this also adds FCOPYSIGN to a few lists in LegalizeVector{Ops,Types} so that vector copysigns can be expanded. In TargetLoweringBase::initActions, I've made the default action for FCOPYSIGN be Expand for vector types. This seems correct for all in-tree targets, and I think is the right thing to do because, previously, there was no way to generate vector-values FCOPYSIGN nodes (and most targets don't specify an action for vector-typed FCOPYSIGN). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188728 91177308-0d34-0410-b5e6-96231b3b80d8
* Add ISD::FROUND for libm round()Hal Finkel2013-08-07
| | | | | | | | | | | | | | | All libm floating-point rounding functions, except for round(), had their own ISD nodes. Recent PowerPC cores have an instruction for round(), and so here I'm adding ISD::FROUND so that round() can be custom lowered as well. For the most part, this is straightforward. I've added an intrinsic and a matching ISD node just like those for nearbyint() and friends. The SelectionDAG pattern I've named frnd (because ISD::FP_ROUND has already claimed fround). This will be used by the PowerPC backend in a follow-up commit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187926 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: Allow vectorization of loops with lifetime markersArnold Schwaighofer2013-08-06
| | | | | | Patch by Marc Jessome! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187825 91177308-0d34-0410-b5e6-96231b3b80d8
* 80-colNadav Rotem2013-07-31
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187535 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix an obvious typo in the loop vectorizer where the cost model uses the ↵Nadav Rotem2013-07-22
| | | | | | | | | | wrong variable. The variable BlockCost is ignored. We don't have tests for the effect of if-conversion loops because it requires a big test (that includes if-converted loops) and it is difficult to find and balance a loop to do the right thing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186845 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Disallow reductions whose header phi is used outside the loopArnold Schwaighofer2013-07-13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | If an outside loop user of the reduction value uses the header phi node we cannot just reduce the vectorized phi value in the vector code epilog because we would loose VF-1 reductions. lp: p = phi (0, lv) lv = lv + 1 ... brcond , lp, outside outside: usr = add 0, p (Say the loop iterates two times, the value of p coming out of the loop is one). We cannot just transform this to: vlp: p = phi (<0,0>, lv) lv = lv + <1,1> .. brcond , lp, outside outside: p_reduced = p[0] + [1]; usr = add 0, p_reduced (Because the original loop iterated two times the vectorized loop would iterate one time, but p_reduced ends up being zero instead of one). We would have to execute VF-1 iterations in the scalar remainder loop in such cases. For now, just disable vectorization. PR16522 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186256 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize fix: LoopInfo must be valid when invoking utils like SCEVExpander.Andrew Trick2013-07-13
| | | | | | | | | | | In general, one should always complete CFG modifications first, update CFG-based analyses, like Dominatores and LoopInfo, then generate instruction sequences. LoopVectorizer was creating a new loop, calling SCEVExpander to generate checks, then updating LoopInfo. I just changed the order. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186241 91177308-0d34-0410-b5e6-96231b3b80d8
* TargetTransformInfo: address calculation parameter for gather/scatherArnold Schwaighofer2013-07-12
| | | | | | | | | | | Address calculation for gather/scather in vectorized code can incur a significant cost making vectorization unbeneficial. Add infrastructure to add cost. Tests and cost model for targets will be in follow-up commits. radar://14351991 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186187 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: Vectorize all accesses in address space zero with unit strideArnold Schwaighofer2013-07-11
| | | | | | | | | | | We can vectorize them because in the case where we wrap in the address space the unvectorized code would have had to access a pointer value of zero which is undefined behavior in address space zero according to the LLVM IR semantics. (Thank you Duncan, for pointing this out to me). Fixes PR16592. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186088 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorize: Math functions only read rounding modeArnold Schwaighofer2013-07-01
| | | | | | | | Math functions are mark as readonly because they read the floating point rounding mode. Because we don't vectorize loops that would contain function calls that set the rounding mode it is safe to ignore this memory read. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185299 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Pack MemAccessInfo pairs.Benjamin Kramer2013-06-29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185263 91177308-0d34-0410-b5e6-96231b3b80d8
* Move helper classes into anonymous namespaces.Benjamin Kramer2013-06-29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185262 91177308-0d34-0410-b5e6-96231b3b80d8
* LoopVectorizer: Refactor the code that checks if it is safe to predicate ↵Nadav Rotem2013-06-28
| | | | | | | | | | | blocks. In this code we keep track of pointers that we are allowed to read from, if they are accessed by non-predicated blocks. We use this list to allow vectorization of conditional loads in predicated blocks because we know that these addresses don't segfault. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185214 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-03 22:54:06 +0000