aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolution.cpp
AgeCommit message (Collapse)Author
2011-10-05Fixes PR11070 - assert in SCEV getConstantEvolvingPHIOperands.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141219 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-05Typo. Thanks Bob.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141188 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-05Fix a broken assert found by -Wparentheses.Chandler Carruth
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141168 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-05Fix disabled SCEV analysis caused r141161 and add unit test.Andrew Trick
I noticed during self-review that my previous checkin disabled some analysis. Even with the reenabled analysis the test case runs in about 5ms. Without the fix, it will take several minutes at least. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141164 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-05Avoid exponential recursion in SCEV getConstantEvolvingPHI and ↵Andrew Trick
EvaluateExpression. Note to compiler writers: never recurse on multiple instruction operands without memoization. Fixes rdar://10187945. Was taking 45s, now taking 5ms. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141161 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-04The product of two chrec's can always be represented as a chrec.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141066 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-03Reapply r140979 with fix! We never did get a testcase, but careful review of theNick Lewycky
logic by David Meyer revealed this bug. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140992 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-03Revert r140979 due to reports of bootstrap failure.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140980 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-03Add one more case we compute a max trip count.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140979 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-28indvars: generalize SCEV getPreStartForSignExtend.Andrew Trick
Handle general Add expressions to avoid leaving around redundant 32-bit IVs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140701 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-10Set NSW/NUW flags on SCEVAddExpr when the operation is flagged asAndrew Trick
such. I'm doing this now for completeness because I can't think of/remember any reason that it was left out. I'm not sure it will help anything, but if we don't do it we need to explain why in comments. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139450 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06This transform only handles two-operand AddRec's. Prevent it from trying toNick Lewycky
handle anything more complex. Fixes PR10383 again! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139186 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06Fix typo in comment again.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139139 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06Apparently we compile the code, not the comments. Thanks Eli!Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139138 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06Fix typo in comment.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139137 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06Nope! I had it right the first time. Revert the operative part of r139135 andNick Lewycky
add more showing of my work. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139136 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06Fix flipped sign. While there, show my math.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139135 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06No no no, fix typo properly!Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139134 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06The logic inside getMulExpr to simplify {a,+,b}*{c,+,d} was wrong, which wasNick Lewycky
visible given a=b=c=d=1, on iteration #1 (the second iteration). Replace it with correct math. Fixes PR10383! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139133 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-06Revert r139126 due to selfhost failures reported by buildbots.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139130 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-05Teach SCEV to report a max backedge count in one interesting case inNick Lewycky
HowFarToZero; the case for a canonical loop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139126 91177308-0d34-0410-b5e6-96231b3b80d8
2011-09-02Comment and clarifying assert.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139036 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-11Allow loop unrolling to get known trip counts from ScalarEvolution.Andrew Trick
SCEV unrolling can unroll loops with arbitrary induction variables. It is a prerequisite for -disable-iv-rewrite performance. It is also easily handles loops of arbitrary structure including multiple exits and is generally more robust. This is under a temporary option to avoid affecting default behavior for the next couple of weeks. It is needed so that I can checkin unit tests for updateUnloop. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137384 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-06Made SCEV's UDiv expressions more canonical. When dividing aAndrew Trick
recurrence, the initial values low bits can sometimes be ignored. To take advantage of this, added FoldIVUser to IndVarSimplify to fold an IV operand into a udiv/lshr if the operator doesn't affect the result. -indvars -disable-iv-rewrite now transforms i = phi i4 i1 = i0 + 1 idx = i1 >> (2 or more) i4 = i + 4 into i = phi i4 idx = i0 >> ... i4 = i + 4 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137013 91177308-0d34-0410-b5e6-96231b3b80d8
2011-08-02Use consistent terminology for loop exit/exiting blocks. Name change only.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136677 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-26SCEV: Added a data structure for storing not-taken info per loopAndrew Trick
exit. Added an interfaces for querying either the loop's exact/max backedge taken count or a specific loop exit's not-taken count. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136100 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-19Use ArrayRef in ConstantFoldInstOperands and ConstantFoldCall.Jay Foad
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135477 91177308-0d34-0410-b5e6-96231b3b80d8
2011-07-18land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@135375 91177308-0d34-0410-b5e6-96231b3b80d8
2011-06-01SCEV: missing null check fix for r132360, dragonegg crash.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132416 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-31scev: Better sign-extend removal. Normalize postincrement recurrencesAndrew Trick
so that their sign extended forms are congruent when no overflow occurs. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132360 91177308-0d34-0410-b5e6-96231b3b80d8
2011-05-09Change a few std::maps to DenseMaps.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131088 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-27Corrects an old, old typo in a case that doesn't seem to be reached in practice.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130316 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-27Test case and comment for PR9633.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130294 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-27Fix for PR9633 [indvars] Assertion `isa<X>(Val) && "cast<Ty>() argument of ↵Andrew Trick
incompatible type!"' failed. Added a type check in ScalarEvolution::computeSCEVAtScope to handle the case in which operands of an AddRecExpr in the current scope are folded. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130271 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-25Fix an iterator invalidation bug.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130166 91177308-0d34-0410-b5e6-96231b3b80d8
2011-04-15Fix a ton of comment typos found by codespell. Patch byChris Lattner
Luis Felipe Strano Moraes! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129558 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-17Added isValidRewrite() to check the result of ScalarEvolutionExpander.Andrew Trick
SCEV may generate expressions composed of multiple pointers, which can lead to invalid GEP expansion. Until we can teach SCEV to follow strict pointer rules, make sure no bad GEPs creep into IR. Fixes rdar://problem/9038671. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127839 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-15Remove getMinusSCEVForExitTest().Andrew Trick
This function performed acrobatics to prove no-self-wrap, which we now have for free. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127643 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-15Propagate SCEV no-wrap flags whenever possible.Andrew Trick
This needs review. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127638 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-14Negating a recurrence preserves no-self-wrap.Andrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127593 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-14HowFarToZero can compute a trip count as long as the recurrence has ↵Andrew Trick
no-self-wrap. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127591 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-14Added SCEV::NoWrapFlags to manage unsigned, signed, and self wrapAndrew Trick
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
2011-03-09When SCEV can determine the loop test is X < X, set ExactBECount=0.Andrew Trick
When ExactBECount is a constant, use it for MaxBECount. When MaxBECount cannot be computed, replace it with ExactBECount. Fixes PR9424. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127342 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-09whitespaceAndrew Trick
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127340 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-13teach SCEV that the scale and addition of an inbounds gep don't NSW.Chris Lattner
This fixes a FIXME in scev-aa.ll (allowing a new no-alias result) and generally makes things more precise. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125449 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-11Per discussion with Dan G, inbounds geps *certainly* can haveChris Lattner
unsigned overflow (e.g. "gep P, -1"), and while they can have signed wrap in theoretical situations, modelling an AddRec as not having signed wrap is going enough for any case we can think of today. In the future if this isn't enough, we can revisit this. Modeling them as having NUW isn't causing any known problems either FWIW. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125410 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-26Fix memory corruption. If one of the SCEV creation functions calls another butNick Lewycky
doesn't return immediately after then the insert position in UniqueSCEVs will be out of date. No test because this is a memory corruption issue. Fixes PR9051! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124282 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-24Add a comment.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124126 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23Simplify some code with no functionality change. Make the test a lot moreNick Lewycky
robust against smarter optimizations, using the power of FileCheck. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124081 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23Use value ranges to fold ext(trunc) in SCEV when possible.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124062 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-05 21:49:52 +0000