summaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Commit message (Collapse)AuthorAge
...
* Handle a corner case with IV chain collection with bailout instead of assert.Andrew Trick2012-01-20
| | | | | | | Fixes PR11783: bad cast to AddRecExpr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148572 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander fixes. Affects LSR and indvars.Andrew Trick2012-01-20
| | | | | | | | | | | | | | | | | LSR has gradually been improved to more aggressively reuse existing code, particularly existing phi cycles. This exposed problems with the SCEVExpander's sloppy treatment of its insertion point. I applied some rigor to the insertion point problem that will hopefully avoid an endless bug cycle in this area. Changes: - Always used properlyDominates to check safe code hoisting. - The insertion point provided to SCEV is now considered a lower bound. This is usually a block terminator or the use itself. Under no cirumstance may SCEVExpander insert below this point. - LSR is reponsible for finding a "canonical" insertion point across expansion of different expressions. - Robust logic to determine whether IV increments are in "expanded" form and/or can be safely hoisted above some insertion point. Fixes PR11783: SCEVExpander assert. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148535 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR fix: broaden the check for loop preheaders.Andrew Trick2012-01-17
| | | | | | | | It's becoming clear that LoopSimplify needs to unconditionally create loop preheaders. But that is a bigger fix. For now, continuing to hack LSR. Fixes rdar://10701050 "Cannot split an edge from an IndirectBrInst" assert. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148288 91177308-0d34-0410-b5e6-96231b3b80d8
* Enable LSR IV Chains with sufficient heuristics.Andrew Trick2012-01-10
| | | | | | | | | | | | | | | | | | | | | | | | | | These heuristics are sufficient for enabling IV chains by default. Performance analysis has been done for i386, x86_64, and thumbv7. The optimization is rarely important, but can significantly speed up certain cases by eliminating spill code within the loop. Unrolled loops are prime candidates for IV chains. In many cases, the final code could still be improved with more target specific optimization following LSR. The goal of this feature is for LSR to make the best choice of induction variables. Instruction selection may not completely take advantage of this feature yet. As a result, there could be cases of slight code size increase. Code size can be worse on x86 because it doesn't support postincrement addressing. In fact, when chains are formed, you may see redundant address plus stride addition in the addressing mode. GenerateIVChains tries to compensate for the common cases. On ARM, code size increase can be mitigated by using postincrement addressing, but downstream codegen currently misses some opportunities. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147826 91177308-0d34-0410-b5e6-96231b3b80d8
* Adding IV chain generation to LSR.Andrew Trick2012-01-09
| | | | | | | | | | | | | | | | | | | After collecting chains, check if any should be materialized. If so, hide the chained IV users from the LSR solver. LSR will only solve for the head of the chain. GenerateIVChains will then materialize the chained IV users by computing the IV relative to its previous value in the chain. In theory, chained IV users could be exposed to LSR's solver. This would be considerably complicated to implement and I'm not aware of a case where we need it. In practice it's more important to intelligently prune the search space of nontrivial loops before running the solver, otherwise the solver is often forced to prune the most optimal solutions. Hiding the chained users does this well, so that LSR is more likely to find the best IV for the chain as a whole. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147801 91177308-0d34-0410-b5e6-96231b3b80d8
* Adding collection of IV chains to LSR.Andrew Trick2012-01-09
| | | | | | | | | This collects a set of IV uses within the loop whose values can be computed relative to each other in a sequence. Following checkins will make use of this information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147797 91177308-0d34-0410-b5e6-96231b3b80d8
* "Minor LSR debugging stuff"Andrew Trick2012-01-09
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147785 91177308-0d34-0410-b5e6-96231b3b80d8
* Enable redundant phi elimination after LSR.Andrew Trick2012-01-07
| | | | | | | This will be more important as we extend the LSR pass in ways that don't rely on the formula solver. In particular, we need it for constructing IV chains. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147724 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR: Don't optimize loops if an outer loop has no preheader.Andrew Trick2012-01-07
| | | | | | | | | LoopSimplify may not run on some outer loops, e.g. because of indirect branches. SCEVExpander simply cannot handle outer loops with no preheaders. Fixes rdar://10655343 SCEVExpander segfault. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147718 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR: run DeleteDeadPhis before replaceCongruentPhis.Andrew Trick2012-01-07
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147711 91177308-0d34-0410-b5e6-96231b3b80d8
* Extended replaceCongruentPhis to handle mixed phi types.Andrew Trick2012-01-07
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147707 91177308-0d34-0410-b5e6-96231b3b80d8
* Cleanup. Clarify LSRInstance public methods.Andrew Trick2011-12-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146459 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR: ignore strides in outer loops.Andrew Trick2011-12-10
| | | | | | | | | Since we're not rewriting IVs in other loops, there's not much reason to consider their stride when generating formulae. This should reduce the number of useless formulas considered by LSR. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146302 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR: prune undesirable formulae early.Andrew Trick2011-12-06
| | | | | | | | | | It's always good to prune early, but formulae that are unsatisfactory in their own right need to be removed before running any other pruning heuristics. We easily avoid generating such formulae, but we need them as an intermediate basis for forming other good formulae. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145906 91177308-0d34-0410-b5e6-96231b3b80d8
* Move code into anonymous namespaces.Benjamin Kramer2011-11-26
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145154 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix MSVC warnings by adding a cast. Nadav Rotem2011-11-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144721 91177308-0d34-0410-b5e6-96231b3b80d8
* Avoid undefined behavior in negation in LSR. Patch by Ahmed Charles.Eli Friedman2011-10-13
| | | | | | | | Someone more familiar with LSR should double-check that the extra cast is actually doing the right thing in the overflow cases; I'm not completely confident that's that case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141916 91177308-0d34-0410-b5e6-96231b3b80d8
* Add experimental -enable-lsr-phielim option.Andrew Trick2011-10-11
| | | | | | | | I'm not sure we will need it in the long run, but the option is currently useful for checking if the output of LSR is "clean". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141634 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR should only reuse phis that match its formula.Andrew Trick2011-10-07
| | | | | | | Fixes rdar://problem/5064068 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141442 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR should avoid redundant edge splitting.Andrew Trick2011-10-04
| | | | | | | | | This handles the case in which LSR rewrites an IV user that is a phi and splits critical edges originating from a switch. Fixes <rdar://problem/6453893> LSR is not splitting edges "nicely" git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141059 91177308-0d34-0410-b5e6-96231b3b80d8
* typo + pastoAndrew Trick2011-09-29
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140769 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR: rewrite inner loops only.Andrew Trick2011-09-29
| | | | | | | | | Rewriting the entire loop nest now requires -enable-lsr-nested. See PR11035 for some performance data. A few unit tests specifically test nested LSR, and are now under a flag. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140762 91177308-0d34-0410-b5e6-96231b3b80d8
* Disable LSR retry by default.Andrew Trick2011-09-27
| | | | | | | | Disabling aggressive LSR saves compilation time, and with the new indvars behavior usually improves performance. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140590 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR, one of the new Cost::isLoser() checks did not get merged in the ↵Andrew Trick2011-09-26
| | | | | | previous checkin. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140583 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR cost metric minor fix and verification.Andrew Trick2011-09-26
| | | | | | | | | The minor bug heuristic was noticed by inspection. I added the isLoser/isValid helpers because they will become more important with subsequent checkins. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140580 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR minor bug fix in RateRegister.Andrew Trick2011-09-23
| | | | | | | | No test case. Noticed by inspection and I doubt it ever affects the outcome of the overall heuristic, let alone final codegen. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140431 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR wants to split the landing pad's critical edge. Let it do it, but use theBill Wendling2011-08-25
| | | | | | | proper function to do it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138550 91177308-0d34-0410-b5e6-96231b3b80d8
* When inserting new instructions, use getFirstInsertionPt instead ofBill Wendling2011-08-25
| | | | | | | getFirstNonPHI so that it will skip over the landingpad instructions as well. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138537 91177308-0d34-0410-b5e6-96231b3b80d8
* Skip the landingpad instruction when determining the insertion point.Bill Wendling2011-08-24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138481 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR, correct fix for rdar://9786536. Silly casting bug.Andrew Trick2011-07-21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135654 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR must sometimes sign-extend before generating double constants.Andrew Trick2011-07-21
| | | | | | | rdar://9786536 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135650 91177308-0d34-0410-b5e6-96231b3b80d8
* LSR crashes on an empty IVUsers list.Andrew Trick2011-07-21
| | | | | | | rdar://9786536 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135644 91177308-0d34-0410-b5e6-96231b3b80d8
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
* start using the new helper methods a bit.Chris Lattner2011-07-15
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135251 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEVExpander: give new insts a name that identifies the reponsible pass.Andrew Trick2011-06-28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133992 91177308-0d34-0410-b5e6-96231b3b80d8
* IVUsers no longer needs to record the phis.Andrew Trick2011-06-21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133518 91177308-0d34-0410-b5e6-96231b3b80d8
* When checking for signed multiplication overflow, watch out for INT_MIN and -1.Dan Gohman2011-05-23
| | | | | | | This fixes PR9845. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131919 91177308-0d34-0410-b5e6-96231b3b80d8
* indvars: Prototyping Sign/ZeroExtend elimination without canonical IVs.Andrew Trick2011-05-20
| | | | | | | | | | | No functionality enabled by default. Use -disable-iv-rewrite. Extended IVUsers to keep track of the phi that represents the users' IV. Added the WidenIV transform to replace a narrow IV with a wide IV by doing a one-for-one replacement of IV users instead of expanding the SCEV expressions. [sz]exts are removed and truncs are inserted. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131744 91177308-0d34-0410-b5e6-96231b3b80d8
* When forming an ICmpZero LSRUse, normalize the non-IV operandDan Gohman2011-05-18
| | | | | | | | of the comparison, so that the resulting expression is fully normalized. This fixes PR9939. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131576 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an unfolded offset field to LSR's Formula record. This is used toDan Gohman2011-05-03
| | | | | | | | | model constants which can be added to base registers via add-immediate instructions which don't require an additional register to materialize the immediate. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130743 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a ton of comment typos found by codespell. Patch byChris Lattner2011-04-15
| | | | | | | | Luis Felipe Strano Moraes! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129558 91177308-0d34-0410-b5e6-96231b3b80d8
* Reapply r129401 with patch for clang.Bill Wendling2011-04-13
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129419 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r129401 for now. Clang is using the old way of doing things.Bill Wendling2011-04-12
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129403 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove the unaligned load intrinsics in favor of using native unaligned loads.Bill Wendling2011-04-12
| | | | | | | | | | Now that we have a first-class way to represent unaligned loads, the unaligned load intrinsics are superfluous. First part of <rdar://problem/8460511>. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129401 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove PHINode::reserveOperandSpace(). Instead, add a parameter toJay Foad2011-03-30
| | | | | | PHINode::Create() giving the (known or expected) number of operands. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128537 91177308-0d34-0410-b5e6-96231b3b80d8
* (Almost) always call reserveOperandSpace() on newly created PHINodes.Jay Foad2011-03-30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128535 91177308-0d34-0410-b5e6-96231b3b80d8
* Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrapAndrew Trick2011-03-14
| | | | | | | | | | properties. Added the self-wrap flag for SCEV::AddRecExpr. A slew of temporary FIXMEs indicate the intention of the no-self-wrap flag without changing behavior in this revision. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127590 91177308-0d34-0410-b5e6-96231b3b80d8
* If we can't avoid running loop-simplify twice for now, at least avoid runningCameron Zwarich2011-02-10
| | | | | | iv-users twice. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125318 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert this in an attempt to bring the builders back.Eric Christopher2011-02-10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125257 91177308-0d34-0410-b5e6-96231b3b80d8
* Turn this pass ordering:Cameron Zwarich2011-02-10
| | | | | | | | | | | | | | | | | | | | | | | | | | Natural Loop Information Loop Pass Manager Canonicalize natural loops Scalar Evolution Analysis Loop Pass Manager Induction Variable Users Canonicalize natural loops Induction Variable Users Loop Strength Reduction into this: Scalar Evolution Analysis Loop Pass Manager Canonicalize natural loops Induction Variable Users Loop Strength Reduction This fixes <rdar://problem/8869639>. I also filed PR9184 on doing this sort of thing automatically, but it seems easier to just change the ordering of the passes if this is the only case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125254 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-03 11:55:13 +0000