aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/LoopStrengthReduce.cpp
AgeCommit message (Collapse)Author
2009-02-20Simplify code and reduce indentation. No functionality change.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65167 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-20Fix 80-column violations.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65159 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-20It's not necessary to check if Base is null here.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65157 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-20Add a comment about how Imm can be used for loop-variant values.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65147 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-20Implement "superhero" strength reduction, or full strengthDan Gohman
reduction of address calculations down to basic pointer arithmetic. This is currently off by default, as it needs a few other features before it becomes generally useful. And even when enabled, full strength reduction is only performed when it doesn't increase register pressure, and when several other conditions are true. This also factors out a bunch of exisiting LSR code out of StrengthReduceStridedIVUsers into separate functions, and tidies up IV insertion. This actually decreases register pressure even in non-superhero mode. The change in iv-users-in-other-loops.ll is an example of this; there are two more adds because there are two fewer leas, and there is less spilling. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65108 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-19Use DEBUG() instead of passing *DOUT to WriteAsOperand,Dan Gohman
since the latter just passes a null reference when debugging is not enabled. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65060 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-19Make the debug output of LSR less cryptic and more informative.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65057 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-18Fix a typo in a comment.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64859 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-17Strengthen the "non-constant stride must dominate loop preheader" check.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64703 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-15Fix pr3571: If stride is a value defined by an instruction, make sure it ↵Evan Cheng
dominates the loop preheader. When IV users are strength reduced, the stride is inserted into the preheader. It could create a use before def situation. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64579 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-15ifdef out unneeded if statement.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64575 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-13Complete the sentance in this comment. I have reservationsDan Gohman
about the code it describes, but at least now the comment is right. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64465 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-13Fix the code that checked if a SCEVAddRecExpr Start contains anDan Gohman
addrec in a different loop to check the value being added to the accumulated Start value, not the Start value before it has the new value added to it. This prevents LSR from going crazy on the included testcase. Dale, please review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64440 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-13Fix LSR's IV sorting function to explicitly sort by bitwidthDan Gohman
after sorting by stride value. This prevents it from missing IV reuse opportunities in a host-sensitive manner. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64415 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-09Fix PR 3471, and some cleanups.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64177 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-14Fix the time regression I introduced in 464.h264ref withDale Johannesen
my earlier patch to this file. The issue there was that all uses of an IV inside a loop are actually references to Base[IV*2], and there was one use outside that was the same but LSR didn't see the base or the scaling because it didn't recurse into uses outside the loop; thus, it used base+IV*scale mode inside the loop instead of pulling base out of the loop. This was extra bad because register pressure later forced both base and IV into memory. Doing that recursion, at least enough to figure out addressing modes, is a good idea in general; the change in AddUsersIfInteresting does this. However, there were side effects.... It is also possible for recursing outside the loop to introduce another IV where there was only 1 before (if the refs inside are not scaled and the ref outside is). I don't think this is a common case, but it's in the testsuite. It is right to be very aggressive about getting rid of such introduced IVs (CheckForIVReuse and the handling of nonzero RewriteFactor in StrengthReduceStridedIVUsers). In the testcase in question the new IV produced this way has both a nonconstant stride and a nonzero base, neither of which was handled before. And when inserting new code that feeds into a PHI, it's right to put such code at the original location rather than in the PHI's immediate predecessor(s) when the original location is outside the loop (a case that couldn't happen before) (RewriteInstructionToUseNewBase); better to avoid making multiple copies of it in this case. Also, the mechanism for keeping SCEV's corresponding to GEP's no longer works, as the GEP might change after its SCEV is remembered, invalidating the SCEV, and we might get a bad SCEV value when looking up the GEP again for a later loop. This also couldn't happen before, as we weren't recursing into GEP's outside the loop. Also, when we build an expression that involves a (possibly non-affine) IV from a different loop as well as an IV from the one we're interested in (containsAddRecFromDifferentLoop), don't recurse into that. We can't do much with it and will get in trouble if we try to create new non-affine IVs or something. More testcases are coming. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62212 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-12Rename getABITypeSize to getTypePaddedSize, asDuncan Sands
suggested by Chris. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62099 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-23Revert 61362 and 61402 until SPEC breakage is fixed.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61403 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-23This fixes the bug in 175.vpr. It doesn't fix theDale Johannesen
other SPEC breakage. I'll be reverting all recent changes shortly, this checking is mostly so this change doesn't get lost. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61402 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-23Fix the time regression I introduced in 464.h264ref withDale Johannesen
my last patch to this file. The issue there was that all uses of an IV inside a loop are actually references to Base[IV*2], and there was one use outside that was the same but LSR didn't see the base or the scaling because it didn't recurse into uses outside the loop; thus, it used base+IV*scale mode inside the loop instead of pulling base out of the loop. This was extra bad because register pressure later forced both base and IV into memory. Doing that recursion, at least enough to figure out addressing modes, is a good idea in general; the change in AddUsersIfInteresting does this. However, there were side effects.... It is also possible for recursing outside the loop to introduce another IV where there was only 1 before (if the refs inside are not scaled and the ref outside is). I don't think this is a common case, but it's in the testsuite. It is right to be very aggressive about getting rid of such introduced IVs (CheckForIVReuse and the handling of nonzero RewriteFactor in StrengthReduceStridedIVUsers). In the testcase in question the new IV produced this way has both a nonconstant stride and a nonzero base, neither of which was handled before. And when inserting new code that feeds into a PHI, it's right to put such code at the original location rather than in the PHI's immediate predecessor(s) when the original location is outside the loop (a case that couldn't happen before) (RewriteInstructionToUseNewBase); better to avoid making multiple copies of it in this case. Also, the mechanism for keeping SCEV's corresponding to GEP's no longer works, as the GEP might change after its SCEV is remembered, invalidating the SCEV, and we might get a bad SCEV value when looking up the GEP again for a later loop. This also couldn't happen before, as we weren't recursing into GEP's outside the loop. I owe some testcases for this, want to get it in for nightly runs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61362 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-18Revert previous patch, appears to break bootstrap.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61181 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-18Fix the time regression I introduced in 464.h264ref withDale Johannesen
my last patch to this file. The issue there was that all uses of an IV inside a loop are actually references to Base[IV*2], and there was one use outside that was the same but LSR didn't see the base or the scaling because it didn't recurse into uses outside the loop; thus, it used base+IV*scale mode inside the loop instead of pulling base out of the loop. This was extra bad because register pressure later forced both base and IV into memory. Doing that recursion, at least enough to figure out addressing modes, is a good idea in general; the change in AddUsersIfInteresting does this. However, there were side effects.... It is also possible for recursing outside the loop to introduce another IV where there was only 1 before (if the refs inside are not scaled and the ref outside is). I don't think this is a common case, but it's in the testsuite. It is right to be very aggressive about getting rid of such introduced IVs (CheckForIVReuse and the handling of nonzero RewriteFactor in StrengthReduceStridedIVUsers). In the testcase in question the new IV produced this way has both a nonconstant stride and a nonzero base, neither of which was handled before. (This patch does not handle all the cases where this can happen.) And when inserting new code that feeds into a PHI, it's right to put such code at the original location rather than in the PHI's immediate predecessor(s) when the original location is outside the loop (a case that couldn't happen before) (RewriteInstructionToUseNewBase); better to avoid making multiple copies of it in this case. Everything above is exercised in CodeGen/X86/lsr-negative-stride.ll (and ifcvt4 in ARM which is the same IR). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61178 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-16Clarify that the scale factor from CheckForIVReuseDale Johannesen
can be negative. Keep track of whether all uses of an IV are outside the loop. Some cosmetics; no functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61109 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09Fix a really subtle off-by-one bug that Duncan noticed with valgrindChris Lattner
on test/CodeGen/Generic/2007-06-06-CriticalEdgeLandingPad. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60739 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-05Make LoopStrengthReduce smarter about hoisting things out ofDale Johannesen
loops when they can be subsumed into addressing modes. Change X86 addressing mode check to realize that some PIC references need an extra register. (I believe this is correct for Linux, if not, I'm sure someone will tell me.) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60608 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-03Remove an unused field.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60508 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-03Fix a misspelled function name.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60506 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-03Fix a really wrong comment.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60494 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-02Minor rewrite per review feedback.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60442 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-02Make the code do what the comment says it does.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60431 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-02some random comment improvements.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60395 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-01Consider only references to an IV within the loop whenDale Johannesen
figuring out the base of the IV. This produces better code in the example. (Addresses use (IV) instead of (BASE,IV) - a significant improvement on low-register machines like x86). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60374 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-01Introduce a new array_pod_sort function and switch LSR to use itChris Lattner
instead of std::sort. This shrinks the release-asserts LSR.o file by 1100 bytes of code on my system. We should start using array_pod_sort where possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60335 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-01Eliminate use of setvector for the DeadInsts set, just use a smallvector.Chris Lattner
This is a lot cheaper and conceptually simpler. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60332 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-01DeleteTriviallyDeadInstructions is always passed theChris Lattner
DeadInsts ivar, just use it directly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60330 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-01simplify DeleteTriviallyDeadInstructions again, unlike my previousChris Lattner
buggy rewrite, this notifies ScalarEvolution of a pending instruction about to be removed and then erases it, instead of erasing it then notifying. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60329 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-29Temporarily revert r60195. It's causing an optimized bootstrap of llvm-gcc ↵Bill Wendling
to fail. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60233 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-27Simplify LoopStrengthReduce::DeleteTriviallyDeadInstructions byChris Lattner
making it use RecursivelyDeleteTriviallyDeadInstructions to do the heavy lifting. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60195 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-27use continue to reduce indentationChris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60192 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-22Change create*Pass factory functions to return Pass* instead ofDaniel Dunbar
LoopPass*. - Although less precise, this means they can be used in clients without RTTI (who would otherwise need to include LoopPass.h, which eventually includes things using dynamic_cast). This was the simplest solution that presented itself, but I am happy to use a better one if available. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@58010 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-01Call ScalarEvolution's deleteValueFromRecords before deleting anDan Gohman
instruction, not after. This fixes some uses of free'd memory. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56908 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-15Teach LSR to optimize away SMAX operations for tripcounts in commonDan Gohman
cases. See the comment above OptimizeSMax for the full story, and the testcase for an example. This cancels out a pessimization commonly attributed to indvars, and will allow us to lift some of the artificial throttles in indvars, rather than add new ones. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56230 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-09fix overflow check.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56011 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-08Remove unused counter.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55924 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-08Remove OptimizeIVType()Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55913 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-04Tidy up several unbeseeming casts from pointer to intptr_t.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55779 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-03Add additional check to ensure that iv is canonicalized.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55682 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-03Check iteration count.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55680 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-03While removing PHI, use basicblock to identify incoming value.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55678 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-02If all IV uses are extending integer IV then change the type of IV itself, ↵Devang Patel
if possible. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55674 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-24 00:51:18 +0000