aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolution.cpp
AgeCommit message (Collapse)Author
2009-01-13Wind SCEV back in time, to Nov 18th. This 'fixes' PR3275, PR3294, PR3295,Nick Lewycky
PR3296 and PR3302. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62160 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-03We know it's always a SCEVConstant if it gets here, so just cast it andNick Lewycky
inline the only use of isNegative. Fixes warning reported by Mike Stump. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61600 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-02Don't try to analyze this "backward" case. This is overly conservative Nick Lewycky
pending a correct solution. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61589 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-16Generalize support for analyzing loops to include SLE/SGE loop exit conditionsNick Lewycky
and support for non-unit strides with signed exit conditions. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61082 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-12Revert my re-instated reverted commit, fixes the bootstrap build on x86-64 ↵Nick Lewycky
linux. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60951 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-11Sneaky, sneaky: move the -1 to the outside of the SMax. Reinstate theNick Lewycky
optimization of SGE/SLE with unit stride, now that it works properly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60881 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09Back out 60748 for now. It's breaking SPASS, 254.gap, and 464.h264ref.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60776 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-09It's easy to handle SLE/SGE when the loop has a unit stride.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60748 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-06Minor cleanup. Use dyn_cast, not isa/cast pairs. No functionality change.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60623 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-03Make the debugging dump be a full line.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60509 91177308-0d34-0410-b5e6-96231b3b80d8
2008-12-02Add a new SCEV representing signed division.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60407 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-18Add a utility function that detects whether a loop is guaranteed to be finite.Nick Lewycky
Use it to safely handle less-than-or-equals-to exit conditions in loops. These also occur when the loop exit branch is exit on true because SCEV inverses the icmp predicate. Use it again to handle non-zero strides, but only with an unsigned comparison in the exit condition. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59528 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-18Remove unused variable.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59515 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-16Don't brute-force analyze cubic or higher polynomials.Nick Lewycky
If this patch causes a performance regression for anyone, please let me know, and it can be fixed in a different way with much more effort. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59384 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-11Silence unused variable warning.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59064 91177308-0d34-0410-b5e6-96231b3b80d8
2008-11-03Don't crash analyzing certain quadratics (addrec of {X,+,Y,+,1}).Nick Lewycky
We're still waiting on code that actually analyzes them properly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@58592 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-13Disallow the construction of SCEVs with could-not-compute operands. Catch CNCsNick Lewycky
returned by BinomialCoefficient and don't try to operate with them. This replaces the previous fix for PR2857. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@57431 91177308-0d34-0410-b5e6-96231b3b80d8
2008-10-04Allow the construction of SCEVs with SCEVCouldNotCompute operands, byNick Lewycky
implementing folding. Fixes PR2857. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@57049 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-16Finally re-apply r46959. This is made feasible by the combinationDan Gohman
of r56230, r56232, and r56246. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56247 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-16Improve instcombine's handling of integer min and max in two ways:Dan Gohman
- Recognize expressions like "x > -1 ? x : 0" as min/max and turn them into expressions like "x < 0 ? 0 : x", which is easily recognizable as a min/max operation. - Refrain from folding expression like "y/2 < 1" to "y < 2" when the comparison is being used as part of a min or max idiom, like "y/2 < 1 ? 1 : y/2". In that case, the division has another use, so folding doesn't eliminate it, and obfuscates the min/max, making it harder to recognize as a min/max operation. These benefit ScalarEvolution, CodeGen, and anything else that wants to recognize integer min and max. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56246 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-15Teach ScalarEvolution to consider loop preheaders in the search forDan Gohman
an if statement that guards a loop, to allow indvars to avoid smax operations in more situations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56232 91177308-0d34-0410-b5e6-96231b3b80d8
2008-09-14Fix WriteAsOperand to not emit a leading space character. AdjustDan Gohman
its callers to emit a space character before calling it when a space is needed. This fixes several spurious whitespace issues in ScalarEvolution's debug dumps. See the test changes for examples. This also fixes odd space-after-tab indentation in the output for switch statements, and changes calls from being printed like this: call void @foo( i32 %x ) to this: call void @foo(i32 %x) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56196 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-12Extend ScalarEvolution's executesAtLeastOnce logic to be able toDan Gohman
continue past the first conditional branch when looking for a relevant test. This helps it avoid using MAX expressions in loop trip counts in more cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54697 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-08Canonicalize nested AddRecs in by nesting them in order of loop depth.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54545 91177308-0d34-0410-b5e6-96231b3b80d8
2008-08-04PR2621: Improvements to the SCEV AddRec binomial expansion. This Eli Friedman
version uses a new algorithm for evaluating the binomial coefficients which is significantly more efficient for AddRecs of more than 2 terms (see the comments in the code for details on how the algorithm works). It also fixes some bugs: it removes the arbitrary length restriction for AddRecs, it fixes the silent generation of incorrect code for AddRecs which require a wide calculation width, and it fixes an issue where we were incorrectly truncating the iteration count too far when evaluating an AddRec expression narrower than the induction variable. There are still a few related issues I know of: I think there's still an issue with the SCEVExpander expansion of AddRec in terms of the width of the induction variable used. The hack to avoid generating too-wide integers shouldn't be necessary; instead, the callers should be considering the cost of the expansion before expanding it (in addition to not expanding too-wide integers, we might not want to expand expressions that are really expensive, especially when optimizing for size; calculating an length-17 32-bit AddRec currently generates about 250 instructions of straight-line code on X86). Also, for long 32-bit AddRecs on X86, CodeGen really sucks at scheduling the code. I'm planning on filing follow-up PRs for these issues. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54332 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-30Another SCEV issue from PR2607; essentially the same issue, but this Eli Friedman
time applying to the implicit comparison in smin expressions. The correct way to transform an inequality into the opposite inequality, either signed or unsigned, is with a not expression. I looked through the SCEV code, and I don't think there are any more occurrences of this issue. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54194 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-30Fix for PR2607: SCEV miscomputing the loop count for loops with an Eli Friedman
SGT exit condition. Essentially, the correct way to flip an inequality in 2's complement is the not operator, not the negation operator. That said, the difference only affects cases involving INT_MIN. Also, enhance the pre-test search logic to be a bit smarter about inequalities flipped with a not operator, so it can eliminate the smax from the iteration count for simple loops. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@54184 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-21Revert r53812 -- premature. LegalizeTypes isn't actually on yet!Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53816 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-21Switch on the use of arbitrary precision integers in scalar evolution. This willNick Lewycky
bail after 256-bits to avoid producing code that the backends can't handle. Previously, we capped it at 64-bits, preferring to miscompile in those cases. This change also reverts much of r52248 because the invariants the code was expecting are now being met. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53812 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-20This header isn't necessary now.Wojciech Matyjewicz
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53811 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-20Fix PR2088. Use modulo linear equation solver to compute loop iterationWojciech Matyjewicz
count. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53810 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-15Correct this inversion!Nick Lewycky
I swear that didn't show up in svn diff... git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53587 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-15Fix up comments.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53586 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-12Stop creating extraneous smax/umax in SCEV. This removes a regression where weNick Lewycky
started complicating many loops ('for' loops, in fact). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53508 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-09Remove getValueRange from SCEV. It wasn't doing anything there anyways, and aNick Lewycky
more complete version is now available from the LoopVR pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53269 91177308-0d34-0410-b5e6-96231b3b80d8
2008-07-07Handle 'lshr' instruction with SCEVUDiv object.Nick Lewycky
Comment the xor %x, -1 case. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53167 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-22Generalize createSCEV to be able to form SCEV expressions fromDan Gohman
ConstantExprs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52615 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-18Move LSR's private isZero function to a public SCEV memberDan Gohman
function, and make use of it in several places. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52463 91177308-0d34-0410-b5e6-96231b3b80d8
2008-06-13Crash less. The i64 restriction in BinomialCoefficient caused some problemsNick Lewycky
with code that was expecting different bit widths for different values. Make getTruncateOrZeroExtend a method on ScalarEvolution, and use it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52248 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-25Don't treat values as signed when looking at loop steppings in HowForToNonZero.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51560 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-13Clean up the use of static and anonymous namespaces. This turned upDan Gohman
several things that were neither in an anonymous namespace nor static but not intended to be global. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51017 91177308-0d34-0410-b5e6-96231b3b80d8
2008-05-06Fix typo and indentation.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50706 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-20(re)fix handling of UGT. Pointed out by Nick Lewycky.Dale Johannesen
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49991 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-20Switch to using Simplified ConstantFP::get API.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49977 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-18Fix a scalar evolution bug. Reversing everythingDale Johannesen
does not work because of 0; 2>0 but -2U is also >0. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49928 91177308-0d34-0410-b5e6-96231b3b80d8
2008-04-14In the special case, call the comparison function instead ofDan Gohman
manually performing the comparison. This allows the special case to work correctly even in the case where someone is experimenting with a different comparison function :-). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@49670 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-20Restore isCFGOnly property of various analysis passes.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48579 91177308-0d34-0410-b5e6-96231b3b80d8
2008-03-19PassInfo keep tracks whether a pass is an analysis pass or not.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@48554 91177308-0d34-0410-b5e6-96231b3b80d8
2008-02-25Temporarily reverting 46959.Evan Cheng
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47542 91177308-0d34-0410-b5e6-96231b3b80d8
2008-02-21Simplify this code, no functionality change.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47434 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-05-02 15:16:02 +0000