aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/ScalarEvolution.cpp
AgeCommit message (Collapse)Author
2009-04-21Introduce encapsulation for ScalarEvolution's TargetData object, and refactorDan Gohman
the code to minimize dependencies on TargetData. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69644 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21Move some assertion checks so they can do more complete checking.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69643 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-21Convert ScalarEvolution to use raw_ostream instead of OStream.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69640 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-18Add a ScalarEvolution::getCouldNotCompute() function, and use itDan Gohman
instead of allocating and leaking new SCEVCouldNotCompute objects. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69452 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-16Fix a bug with inttoptr/ptrtoint casts where the pointer has a differentDan Gohman
size from the integer, requiring zero extension or truncation. Don't create ZExtInsts with pointer types. This fixes a regression in consumer-jpeg. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69307 91177308-0d34-0410-b5e6-96231b3b80d8
2009-04-16Expand GEPs in ScalarEvolution expressions. SCEV expressions can nowDan Gohman
have pointer types, though in contrast to C pointer types, SCEV addition is never implicitly scaled. This not only eliminates the need for special code like IndVars' EliminatePointerRecurrence and LSR's own GEP expansion code, it also does a better job because it lets the normal optimizations handle pointer expressions just like integer expressions. Also, since LLVM IR GEPs can't directly index into multi-dimensional VLAs, moving the GEP analysis out of client code and into the SCEV framework makes it easier for clients to handle multi-dimensional VLAs the same way as other arrays. Some existing regression tests show improved optimization. test/CodeGen/ARM/2007-03-13-InstrSched.ll in particular improved to the point where if-conversion started kicking in; I turned it off for this test to preserve the intent of the test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69258 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-24Rename ScalarEvolution's getIterationCount to getBackedgeTakenCount,Dan Gohman
to more accurately describe what it does. Expand its doxygen comment to describe what the backedge-taken count is and how it differs from the actual iteration count of the loop. Adjust names and comments in associated code accordingly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@65382 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-18Use a sign-extend instead of a zero-extend when promoting aDan Gohman
trip count value when the original loop iteration condition is signed and the canonical induction variable won't undergo signed overflow. This isn't required for correctness; it just preserves more information about original loop iteration values. Add a getTruncateOrSignExtend method to ScalarEvolution, following getTruncateOrZeroExtend. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64918 91177308-0d34-0410-b5e6-96231b3b80d8
2009-02-17Add a method to ScalarEvolution for telling it when a loop has beenDan Gohman
modified in a way that may effect the trip count calculation. Change IndVars to use this method when it rewrites pointer or floating-point induction variables instead of using a doInitialization method to sneak these changes in before ScalarEvolution has a chance to see the loop. This eliminates the need for LoopPass to depend on ScalarEvolution. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64810 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-12Teach IndVarSimplify to optimize code using the C "int" type forDan Gohman
loop induction on LP64 targets. When the induction variable is used in addressing, IndVars now is usually able to inserst a 64-bit induction variable and eliminates the sign-extending cast. This is also useful for code using C "short" types for induction variables on targets with 32-bit addressing. Inserting a wider induction variable is easy; the tricky part is determining when trunc(sext(i)) expressions are no-ops. This requires range analysis of the loop trip count. A common case is when the original loop iteration starts at 0 and exits when the induction variable is signed-less-than a fixed value; this case is now handled. This replaces IndVarSimplify's OptimizeCanonicalIVType. It was doing the same optimization, but it was limited to loops with constant trip counts, because it was running after the loop rewrite, and the information about the original induction variable is lost by that point. Rename ScalarEvolution's executesAtLeastOnce to isLoopGuardedByCond, generalize it to be able to test for ICMP_NE conditions, and move it to be a public function so that IndVars can use it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@64407 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-25Start generating arbitrary precision integer SCEVs. This removes the temporaryNick Lewycky
code that rounded up and capped the size. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62958 91177308-0d34-0410-b5e6-96231b3b80d8
2009-01-16Reinstate r60509 from Dale:Nick Lewycky
Make the debugging dump be a full line. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62325 91177308-0d34-0410-b5e6-96231b3b80d8
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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-06-24 09:01:23 +0000