summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Fix a bug with inttoptr/ptrtoint casts where the pointer has a differentDan Gohman2009-04-161-3/+6
| | | | | | | | size from the integer, requiring zero extension or truncation. Don't create ZExtInsts with pointer types. This fixes a regression in consumer-jpeg. llvm-svn: 69307
* Expand GEPs in ScalarEvolution expressions. SCEV expressions can nowDan Gohman2009-04-161-122/+283
| | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 69258
* Rename ScalarEvolution's getIterationCount to getBackedgeTakenCount,Dan Gohman2009-02-241-76/+99
| | | | | | | | | 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. llvm-svn: 65382
* Use a sign-extend instead of a zero-extend when promoting aDan Gohman2009-02-181-0/+15
| | | | | | | | | | | | 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. llvm-svn: 64918
* Add a method to ScalarEvolution for telling it when a loop has beenDan Gohman2009-02-171-0/+16
| | | | | | | | | | | 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. llvm-svn: 64810
* Strengthen the "non-constant stride must dominate loop preheader" check.Evan Cheng2009-02-171-0/+40
| | | | llvm-svn: 64703
* Teach IndVarSimplify to optimize code using the C "int" type forDan Gohman2009-02-121-27/+73
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 64407
* Start generating arbitrary precision integer SCEVs. This removes the temporaryNick Lewycky2009-01-251-11/+1
| | | | | | code that rounded up and capped the size. llvm-svn: 62958
* Reinstate r60509 from Dale:Nick Lewycky2009-01-161-0/+1
| | | | | | Make the debugging dump be a full line. llvm-svn: 62325
* Wind SCEV back in time, to Nov 18th. This 'fixes' PR3275, PR3294, PR3295,Nick Lewycky2009-01-131-202/+41
| | | | | | PR3296 and PR3302. llvm-svn: 62160
* We know it's always a SCEVConstant if it gets here, so just cast it andNick Lewycky2009-01-031-6/+2
| | | | | | inline the only use of isNegative. Fixes warning reported by Mike Stump. llvm-svn: 61600
* Don't try to analyze this "backward" case. This is overly conservative Nick Lewycky2009-01-021-0/+12
| | | | | | pending a correct solution. llvm-svn: 61589
* Generalize support for analyzing loops to include SLE/SGE loop exit conditionsNick Lewycky2008-12-161-24/+23
| | | | | | and support for non-unit strides with signed exit conditions. llvm-svn: 61082
* Revert my re-instated reverted commit, fixes the bootstrap build on x86-64 ↵Nick Lewycky2008-12-121-15/+15
| | | | | | linux. llvm-svn: 60951
* Sneaky, sneaky: move the -1 to the outside of the SMax. Reinstate theNick Lewycky2008-12-111-15/+15
| | | | | | optimization of SGE/SLE with unit stride, now that it works properly. llvm-svn: 60881
* Back out 60748 for now. It's breaking SPASS, 254.gap, and 464.h264ref.Evan Cheng2008-12-091-5/+1
| | | | llvm-svn: 60776
* It's easy to handle SLE/SGE when the loop has a unit stride.Nick Lewycky2008-12-091-1/+5
| | | | llvm-svn: 60748
* Minor cleanup. Use dyn_cast, not isa/cast pairs. No functionality change.Nick Lewycky2008-12-061-5/+5
| | | | llvm-svn: 60623
* Make the debugging dump be a full line.Dale Johannesen2008-12-031-0/+1
| | | | llvm-svn: 60509
* Add a new SCEV representing signed division.Nick Lewycky2008-12-021-10/+67
| | | | llvm-svn: 60407
* Add a utility function that detects whether a loop is guaranteed to be finite.Nick Lewycky2008-11-181-31/+127
| | | | | | | | | | | 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. llvm-svn: 59528
* Remove unused variable.Duncan Sands2008-11-181-3/+0
| | | | llvm-svn: 59515
* Don't brute-force analyze cubic or higher polynomials.Nick Lewycky2008-11-161-21/+0
| | | | | | | 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. llvm-svn: 59384
* Silence unused variable warning.Devang Patel2008-11-111-0/+1
| | | | llvm-svn: 59064
* Don't crash analyzing certain quadratics (addrec of {X,+,Y,+,1}).Nick Lewycky2008-11-031-0/+5
| | | | | | We're still waiting on code that actually analyzes them properly. llvm-svn: 58592
* Disallow the construction of SCEVs with could-not-compute operands. Catch CNCsNick Lewycky2008-10-131-72/+6
| | | | | | | returned by BinomialCoefficient and don't try to operate with them. This replaces the previous fix for PR2857. llvm-svn: 57431
* Allow the construction of SCEVs with SCEVCouldNotCompute operands, byNick Lewycky2008-10-041-0/+67
| | | | | | implementing folding. Fixes PR2857. llvm-svn: 57049
* Finally re-apply r46959. This is made feasible by the combinationDan Gohman2008-09-161-2/+2
| | | | | | of r56230, r56232, and r56246. llvm-svn: 56247
* Improve instcombine's handling of integer min and max in two ways:Dan Gohman2008-09-161-5/+0
| | | | | | | | | | | | | | | | - 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. llvm-svn: 56246
* Teach ScalarEvolution to consider loop preheaders in the search forDan Gohman2008-09-151-8/+38
| | | | | | | an if statement that guards a loop, to allow indvars to avoid smax operations in more situations. llvm-svn: 56232
* Fix WriteAsOperand to not emit a leading space character. AdjustDan Gohman2008-09-141-4/+4
| | | | | | | | | | | | | | | | | | 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) llvm-svn: 56196
* Extend ScalarEvolution's executesAtLeastOnce logic to be able toDan Gohman2008-08-121-55/+57
| | | | | | | | 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. llvm-svn: 54697
* Canonicalize nested AddRecs in by nesting them in order of loop depth.Dan Gohman2008-08-081-0/+13
| | | | llvm-svn: 54545
* PR2621: Improvements to the SCEV AddRec binomial expansion. This Eli Friedman2008-08-041-84/+111
| | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 54332
* Another SCEV issue from PR2607; essentially the same issue, but this Eli Friedman2008-07-301-4/+4
| | | | | | | | | | | 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. llvm-svn: 54194
* Fix for PR2607: SCEV miscomputing the loop count for loops with an Eli Friedman2008-07-301-3/+7
| | | | | | | | | | | | 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. llvm-svn: 54184
* Revert r53812 -- premature. LegalizeTypes isn't actually on yet!Nick Lewycky2008-07-211-8/+22
| | | | llvm-svn: 53816
* Switch on the use of arbitrary precision integers in scalar evolution. This willNick Lewycky2008-07-211-22/+8
| | | | | | | | | | 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. llvm-svn: 53812
* This header isn't necessary now.Wojciech Matyjewicz2008-07-201-2/+0
| | | | llvm-svn: 53811
* Fix PR2088. Use modulo linear equation solver to compute loop iterationWojciech Matyjewicz2008-07-201-22/+71
| | | | | | count. llvm-svn: 53810
* Correct this inversion!Nick Lewycky2008-07-151-1/+1
| | | | | | I swear that didn't show up in svn diff... llvm-svn: 53587
* Fix up comments.Nick Lewycky2008-07-151-5/+7
| | | | llvm-svn: 53586
* Stop creating extraneous smax/umax in SCEV. This removes a regression where weNick Lewycky2008-07-121-6/+79
| | | | | | started complicating many loops ('for' loops, in fact). llvm-svn: 53508
* Remove getValueRange from SCEV. It wasn't doing anything there anyways, and aNick Lewycky2008-07-091-31/+0
| | | | | | more complete version is now available from the LoopVR pass. llvm-svn: 53269
* Handle 'lshr' instruction with SCEVUDiv object.Nick Lewycky2008-07-071-2/+14
| | | | | | Comment the xor %x, -1 case. llvm-svn: 53167
* Generalize createSCEV to be able to form SCEV expressions fromDan Gohman2008-06-221-110/+117
| | | | | | ConstantExprs. llvm-svn: 52615
* Move LSR's private isZero function to a public SCEV memberDan Gohman2008-06-181-8/+12
| | | | | | function, and make use of it in several places. llvm-svn: 52463
* Crash less. The i64 restriction in BinomialCoefficient caused some problemsNick Lewycky2008-06-131-24/+30
| | | | | | | | with code that was expecting different bit widths for different values. Make getTruncateOrZeroExtend a method on ScalarEvolution, and use it. llvm-svn: 52248
* Don't treat values as signed when looking at loop steppings in HowForToNonZero.Nick Lewycky2008-05-251-2/+2
| | | | llvm-svn: 51560
* Clean up the use of static and anonymous namespaces. This turned upDan Gohman2008-05-131-5/+3
| | | | | | | several things that were neither in an anonymous namespace nor static but not intended to be global. llvm-svn: 51017
OpenPOWER on IntegriCloud