summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Enable LSR IV Chains with sufficient heuristics.Andrew Trick2012-01-101-5/+210
| | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 147826
* Adding IV chain generation to LSR.Andrew Trick2012-01-091-5/+228
| | | | | | | | | | | | | | | | | | 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. llvm-svn: 147801
* Adding collection of IV chains to LSR.Andrew Trick2012-01-091-0/+242
| | | | | | | | 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. llvm-svn: 147797
* "Minor LSR debugging stuff"Andrew Trick2012-01-091-1/+4
| | | | llvm-svn: 147785
* Enable redundant phi elimination after LSR.Andrew Trick2012-01-071-1/+3
| | | | | | 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. llvm-svn: 147724
* LSR: Don't optimize loops if an outer loop has no preheader.Andrew Trick2012-01-071-1/+8
| | | | | | | | 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. llvm-svn: 147718
* LSR: run DeleteDeadPhis before replaceCongruentPhis.Andrew Trick2012-01-071-19/+15
| | | | llvm-svn: 147711
* Extended replaceCongruentPhis to handle mixed phi types.Andrew Trick2012-01-071-2/+2
| | | | llvm-svn: 147707
* Cleanup. Clarify LSRInstance public methods.Andrew Trick2011-12-131-1/+1
| | | | llvm-svn: 146459
* LSR: ignore strides in outer loops.Andrew Trick2011-12-101-1/+2
| | | | | | | | 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. llvm-svn: 146302
* LSR: prune undesirable formulae early.Andrew Trick2011-12-061-46/+85
| | | | | | | | | 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. llvm-svn: 145906
* Move code into anonymous namespaces.Benjamin Kramer2011-11-261-7/+5
| | | | llvm-svn: 145154
* Fix MSVC warnings by adding a cast. Nadav Rotem2011-11-151-4/+4
| | | | llvm-svn: 144721
* Avoid undefined behavior in negation in LSR. Patch by Ahmed Charles.Eli Friedman2011-10-131-2/+2
| | | | | | 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. llvm-svn: 141916
* Add experimental -enable-lsr-phielim option.Andrew Trick2011-10-111-0/+22
| | | | | | | 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". llvm-svn: 141634
* LSR should only reuse phis that match its formula.Andrew Trick2011-10-071-0/+1
| | | | | | Fixes rdar://problem/5064068 llvm-svn: 141442
* LSR should avoid redundant edge splitting.Andrew Trick2011-10-041-1/+3
| | | | | | | | 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" llvm-svn: 141059
* typo + pastoAndrew Trick2011-09-291-2/+2
| | | | llvm-svn: 140769
* LSR: rewrite inner loops only.Andrew Trick2011-09-291-5/+21
| | | | | | | | 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. llvm-svn: 140762
* Disable LSR retry by default.Andrew Trick2011-09-271-0/+16
| | | | | | | Disabling aggressive LSR saves compilation time, and with the new indvars behavior usually improves performance. llvm-svn: 140590
* LSR, one of the new Cost::isLoser() checks did not get merged in the ↵Andrew Trick2011-09-261-2/+6
| | | | | | previous checkin. llvm-svn: 140583
* LSR cost metric minor fix and verification.Andrew Trick2011-09-261-3/+26
| | | | | | | | The minor bug heuristic was noticed by inspection. I added the isLoser/isValid helpers because they will become more important with subsequent checkins. llvm-svn: 140580
* LSR minor bug fix in RateRegister.Andrew Trick2011-09-231-1/+1
| | | | | | | No test case. Noticed by inspection and I doubt it ever affects the outcome of the overall heuristic, let alone final codegen. llvm-svn: 140431
* LSR wants to split the landing pad's critical edge. Let it do it, but use theBill Wendling2011-08-251-1/+8
| | | | | | proper function to do it. llvm-svn: 138550
* When inserting new instructions, use getFirstInsertionPt instead ofBill Wendling2011-08-251-3/+4
| | | | | | getFirstNonPHI so that it will skip over the landingpad instructions as well. llvm-svn: 138537
* Skip the landingpad instruction when determining the insertion point.Bill Wendling2011-08-241-0/+3
| | | | llvm-svn: 138481
* LSR, correct fix for rdar://9786536. Silly casting bug.Andrew Trick2011-07-211-2/+2
| | | | llvm-svn: 135654
* LSR must sometimes sign-extend before generating double constants.Andrew Trick2011-07-211-3/+10
| | | | | | rdar://9786536 llvm-svn: 135650
* LSR crashes on an empty IVUsers list.Andrew Trick2011-07-211-0/+3
| | | | | | rdar://9786536 llvm-svn: 135644
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-37/+37
| | | | llvm-svn: 135375
* start using the new helper methods a bit.Chris Lattner2011-07-151-1/+1
| | | | llvm-svn: 135251
* SCEVExpander: give new insts a name that identifies the reponsible pass.Andrew Trick2011-06-281-1/+1
| | | | llvm-svn: 133992
* IVUsers no longer needs to record the phis.Andrew Trick2011-06-211-2/+1
| | | | llvm-svn: 133518
* When checking for signed multiplication overflow, watch out for INT_MIN and -1.Dan Gohman2011-05-231-0/+2
| | | | | | This fixes PR9845. llvm-svn: 131919
* indvars: Prototyping Sign/ZeroExtend elimination without canonical IVs.Andrew Trick2011-05-201-1/+2
| | | | | | | | | | 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. llvm-svn: 131744
* When forming an ICmpZero LSRUse, normalize the non-IV operandDan Gohman2011-05-181-0/+4
| | | | | | | of the comparison, so that the resulting expression is fully normalized. This fixes PR9939. llvm-svn: 131576
* Add an unfolded offset field to LSR's Formula record. This is used toDan Gohman2011-05-031-9/+62
| | | | | | | | model constants which can be added to base registers via add-immediate instructions which don't require an additional register to materialize the immediate. llvm-svn: 130743
* Fix a ton of comment typos found by codespell. Patch byChris Lattner2011-04-151-2/+2
| | | | | | Luis Felipe Strano Moraes! llvm-svn: 129558
* Reapply r129401 with patch for clang.Bill Wendling2011-04-131-3/+0
| | | | llvm-svn: 129419
* Revert r129401 for now. Clang is using the old way of doing things.Bill Wendling2011-04-121-0/+3
| | | | llvm-svn: 129403
* Remove the unaligned load intrinsics in favor of using native unaligned loads.Bill Wendling2011-04-121-3/+0
| | | | | | | | | Now that we have a first-class way to represent unaligned loads, the unaligned load intrinsics are superfluous. First part of <rdar://problem/8460511>. llvm-svn: 129401
* Remove PHINode::reserveOperandSpace(). Instead, add a parameter toJay Foad2011-03-301-2/+1
| | | | | | PHINode::Create() giving the (known or expected) number of operands. llvm-svn: 128537
* (Almost) always call reserveOperandSpace() on newly created PHINodes.Jay Foad2011-03-301-0/+1
| | | | llvm-svn: 128535
* Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrapAndrew Trick2011-03-141-6/+16
| | | | | | | | | 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. llvm-svn: 127590
* If we can't avoid running loop-simplify twice for now, at least avoid runningCameron Zwarich2011-02-101-0/+3
| | | | | | iv-users twice. llvm-svn: 125318
* Revert this in an attempt to bring the builders back.Eric Christopher2011-02-101-4/+4
| | | | llvm-svn: 125257
* Turn this pass ordering:Cameron Zwarich2011-02-101-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 125254
* Don't split any loop backedges, including backedges of loops other thanDan Gohman2011-02-081-15/+17
| | | | | | | | the active loop. This is generally desirable, and it avoids trouble in situations such as the testcase in PR9123, though the failure mode depends on use-list order, so it is infeasible to test. llvm-svn: 125065
* Remove code for updating dominance frontiers and some outdated references toCameron Zwarich2011-01-181-1/+0
| | | | | | dominance and post-dominance frontiers. llvm-svn: 123725
* split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner2011-01-021-0/+1
| | | | | | so that Dominators.h is *just* domtree. Also prune #includes a bit. llvm-svn: 122714
OpenPOWER on IntegriCloud