summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Fix typo and indentation.Nick Lewycky2008-05-061-2/+2
| | | | llvm-svn: 50706
* (re)fix handling of UGT. Pointed out by Nick Lewycky.Dale Johannesen2008-04-201-1/+2
| | | | llvm-svn: 49991
* Switch to using Simplified ConstantFP::get API.Chris Lattner2008-04-201-2/+2
| | | | llvm-svn: 49977
* Fix a scalar evolution bug. Reversing everythingDale Johannesen2008-04-181-2/+1
| | | | | | does not work because of 0; 2>0 but -2U is also >0. llvm-svn: 49928
* In the special case, call the comparison function instead ofDan Gohman2008-04-141-2/+2
| | | | | | | | 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 :-). llvm-svn: 49670
* Restore isCFGOnly property of various analysis passes.Devang Patel2008-03-201-1/+1
| | | | llvm-svn: 48579
* PassInfo keep tracks whether a pass is an analysis pass or not.Devang Patel2008-03-191-1/+1
| | | | llvm-svn: 48554
* Temporarily reverting 46959.Evan Cheng2008-02-251-2/+2
| | | | llvm-svn: 47542
* Simplify this code, no functionality change.Nick Lewycky2008-02-211-5/+2
| | | | llvm-svn: 47434
* GlobalValues are Constants, remove redundant code. Also fix typo in a comment.Nick Lewycky2008-02-211-3/+1
| | | | llvm-svn: 47433
* Unbreak build with gcc 4.3: provide missed includes and silence most ↵Anton Korobeynikov2008-02-201-1/+2
| | | | | | annoying warnings. llvm-svn: 47367
* Use getConstant for ConstantInts.Nick Lewycky2008-02-201-2/+2
| | | | llvm-svn: 47361
* Add 'umax' similar to 'smax' SCEV. Closes PR2003.Nick Lewycky2008-02-201-44/+146
| | | | | | | | | | | | | | | Parse reversed smax and umax as smin and umin and express them with negative or binary-not SCEVs (which are really just subtract under the hood). Parse 'xor %x, -1' as (-1 - %x). Remove dead code (ConstantInt::get always returns a ConstantInt). Don't use getIntegerSCEV(-1, Ty). The first value is an int, then it gets passed into a uint64_t. Instead, create the -1 directly from ConstantInt::getAllOnesValue(). llvm-svn: 47360
* Fix typo. Thanks to Duncan for noticing.Wojciech Matyjewicz2008-02-131-1/+1
| | | | llvm-svn: 47062
* Add comments as per review feedback.Wojciech Matyjewicz2008-02-131-5/+13
| | | | llvm-svn: 47061
* Fix PR2002. Suppose n is the initial value for the induction Wojciech Matyjewicz2008-02-121-6/+4
| | | | | | | | | | variable (with step 1) and m is its final value. Then, the correct trip count is SMAX(m,n)-n. Previously, we used SMAX(0,m-n), but m-n may overflow and can't in general be interpreted as signed. Patch by Nick Lewycky. llvm-svn: 47007
* If the LHS of the comparison is a loop-invariant we also want to move it Wojciech Matyjewicz2008-02-111-2/+2
| | | | | | | | to the RHS. This simple change allows to compute loop iteration count for loops with condition similar to the one in the testcase (which seems to be quite common). llvm-svn: 46959
OpenPOWER on IntegriCloud