aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopStrengthReduce.cpp
AgeCommit message (Collapse)Author
2012-07-17Reapply r160340. LSR: Limit CollectSubexprs.Andrew Trick
Speculatively fix crashes by code inspection. Can't reproduce them yet. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160344 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-17Revert "LSR: try not to blow up solving combinatorial problems brute force."Andrew Trick
Some units tests crashed on a different platform. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160341 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-17LSR: try not to blow up solving combinatorial problems brute force.Andrew Trick
This places limits on CollectSubexprs to constrains the number of reassociation possibilities. It limits the recursion depth and skips over chains of nested recurrences outside the current loop. Fixes PR13361. Although underlying SCEV behavior is still potentially bad. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160340 91177308-0d34-0410-b5e6-96231b3b80d8
2012-07-13LSR Fix: check SCEV expression safety before expansion.Andrew Trick
All SCEV expressions used by LSR formulae must be safe to expand. i.e. they may not contain UDiv unless we can prove nonzero denominator. Fixes PR11356: LSR hoists UDiv. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@160205 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-15LSR: fix expansion of scaled reg in non-address type formulae.Andrew Trick
For non-address users, Base and Scaled registers are not specially associated to fit an address mode, so SCEVExpander should apply normal expansion rules. Otherwise we may sink computation into inner loops that have already been optimized. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158537 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-15LSR fix: "Special" users are just like "Basic" users but allow -1 scale.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158536 91177308-0d34-0410-b5e6-96231b3b80d8
2012-06-02Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157885 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-30Make sure HoistInsertPosition finds a position that is dominated by allRafael Espindola
inputs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155809 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-26Break up getProfitableChainIncrement().Jakob Stoklund Olesen
The required checks are moved to ChainInstruction() itself and the policy decisions are moved to IVChain::isProfitableInc(). Also cache the ExprBase in IVChain to avoid frequent recomputations. No functional change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155676 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-26Turn IVChain into a struct.Jakob Stoklund Olesen
No functional change intended. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155675 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-25Print IV chain numbers while collecting them.Jakob Stoklund Olesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155567 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-18loop-reduce: Add an early bailout to catch extremely large loops.Andrew Trick
This introduces a threshold of 200 IV Users, which is very conservative but should be sufficient to avoid serious compile time sink or stack overflow. The llvm test-suite with LTO never exceeds 190 users per loop. The bug doesn't relate to a specific type of loop. Checking in an arbitrary giant loop as a unit test would be silly. Fixes rdar://11262507. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154983 91177308-0d34-0410-b5e6-96231b3b80d8
2012-04-05Pass the right sign to TLI->isLegalICmpImmediate.Jakob Stoklund Olesen
LSR can fold three addressing modes into its ICmpZero node: ICmpZero BaseReg + Offset => ICmp BaseReg, -Offset ICmpZero -1*ScaleReg + Offset => ICmp ScaleReg, Offset ICmpZero BaseReg + -1*ScaleReg => ICmp BaseReg, ScaleReg The first two cases are only used if TLI->isLegalICmpImmediate() likes the offset. Make sure the right Offset sign is passed to this method in the second case. The ARM version is not symmetric. <rdar://problem/11184260> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154079 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-26LSR ivchain bug fix: corner case with ConstantExpr.Andrew Trick
Fixes PR11950. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153463 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-26comment typoAndrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153462 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-26LSR cleanup: potential bug caught by PVS-Studio.Andrew Trick
Thanks Andrey. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153451 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-22Remove -enable-lsr-retry in time for 3.1.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153287 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-22Remove -enable-lsr-nested in time for 3.1.Andrew Trick
Tests cases have been removed but attached to open PR12330. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153286 91177308-0d34-0410-b5e6-96231b3b80d8
2012-03-16LSR fix: Add isSimplifiedLoopNest to IVUsers analysis.Andrew Trick
Only record IVUsers that are dominated by simplified loop headers. Otherwise SCEVExpander will crash while looking for a preheader. I previously tried to work around this in LSR itself, but that was insufficient. This way, LSR can continue to run if some uses are not in simple loops, as long as we don't attempt to analyze those users. Fixes <rdar://problem/11049788> Segmentation fault: 11 in LoopStrengthReduce git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152892 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-20More dead code removal (using -Wunreachable-code)David Blaikie
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148578 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-20Handle a corner case with IV chain collection with bailout instead of assert.Andrew Trick
Fixes PR11783: bad cast to AddRecExpr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148572 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-20SCEVExpander fixes. Affects LSR and indvars.Andrew Trick
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
2012-01-17LSR fix: broaden the check for loop preheaders.Andrew Trick
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
2012-01-10Enable LSR IV Chains with sufficient heuristics.Andrew Trick
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
2012-01-09Adding IV chain generation to LSR.Andrew Trick
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
2012-01-09Adding collection of IV chains to LSR.Andrew Trick
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
2012-01-09"Minor LSR debugging stuff"Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147785 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-07Enable redundant phi elimination after LSR.Andrew Trick
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
2012-01-07LSR: Don't optimize loops if an outer loop has no preheader.Andrew Trick
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
2012-01-07LSR: run DeleteDeadPhis before replaceCongruentPhis.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147711 91177308-0d34-0410-b5e6-96231b3b80d8
2012-01-07Extended replaceCongruentPhis to handle mixed phi types.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@147707 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-13Cleanup. Clarify LSRInstance public methods.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146459 91177308-0d34-0410-b5e6-96231b3b80d8
2011-12-10LSR: ignore strides in outer loops.Andrew Trick
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
2011-12-06LSR: prune undesirable formulae early.Andrew Trick
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
2011-11-26Move code into anonymous namespaces.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145154 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-15Fix MSVC warnings by adding a cast. Nadav Rotem
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144721 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-13Avoid undefined behavior in negation in LSR. Patch by Ahmed Charles.Eli Friedman
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
2011-10-11Add experimental -enable-lsr-phielim option.Andrew Trick
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
2011-10-07LSR should only reuse phis that match its formula.Andrew Trick
Fixes rdar://problem/5064068 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141442 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-04LSR should avoid redundant edge splitting.Andrew Trick
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
2011-09-29typo + pastoAndrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140769 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-29LSR: rewrite inner loops only.Andrew Trick
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
2011-09-27Disable LSR retry by default.Andrew Trick
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
2011-09-26LSR, one of the new Cost::isLoser() checks did not get merged in the ↵Andrew Trick
previous checkin. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140583 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-26LSR cost metric minor fix and verification.Andrew Trick
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
2011-09-23LSR minor bug fix in RateRegister.Andrew Trick
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
2011-08-25LSR wants to split the landing pad's critical edge. Let it do it, but use theBill Wendling
proper function to do it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138550 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-25When inserting new instructions, use getFirstInsertionPt instead ofBill Wendling
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
2011-08-24Skip the landingpad instruction when determining the insertion point.Bill Wendling
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@138481 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-21LSR, correct fix for rdar://9786536. Silly casting bug.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135654 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-08 08:40:44 +0000