aboutsummaryrefslogtreecommitdiffstats
path: root/test/Analysis/ScalarEvolution
Commit message (Collapse)AuthorAgeFilesLines
* When printing a SCEVUnknown with pointer type, don't print anDan Gohman2009-05-011-1/+1
| | | | | | | | | artificial "ptrtoint", as it tends to clutter up complicated expressions. The cast operators now print both source and destination types, which is usually sufficient. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70554 91177308-0d34-0410-b5e6-96231b3b80d8
* Extend ScalarEvolution's getBackedgeTakenCount to be able toDan Gohman2009-04-303-1/+106
| | | | | | | | | | | | | compute an upper-bound value for the trip count, in addition to the actual trip count. Use this to allow getZeroExtendExpr and getSignExtendExpr to fold casts in more cases. This may eventually morph into a more general value-range analysis capability; there are certainly plenty of places where more complete value-range information would allow more folding. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70509 91177308-0d34-0410-b5e6-96231b3b80d8
* Generalize the cast-of-addrec folding to handle folding of SCEVs likeDan Gohman2009-04-292-0/+131
| | | | | | | | | (sext i8 {-128,+,1} to i64) to i64 {-128,+,1}, where the iteration crosses from negative to positive, but is still safe if the trip count is within range. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70421 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix this test to match the new output from scalar-evolution.Dan Gohman2009-04-291-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70410 91177308-0d34-0410-b5e6-96231b3b80d8
* Include the source type in SCEV cast expression debug output, andDan Gohman2009-04-291-2/+3
| | | | | | | | print sext, zext, and trunc, instead of signextend, zeroextend, and truncate, respectively, for consistency with the main IR. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70405 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a grammaro in a comment.Dan Gohman2009-04-281-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@70331 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify trunc(extend(x)) in SCEVs, just for completeness. Also fix some oddNick Lewycky2009-04-231-0/+37
| | | | | | | whitespace in the same file. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69870 91177308-0d34-0410-b5e6-96231b3b80d8
* Testcase for PR3909.Owen Anderson2009-04-231-0/+30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69868 91177308-0d34-0410-b5e6-96231b3b80d8
* When turning (ashr(shl(x, n), n)) into sext(trunc(x)), the width of theDan Gohman2009-04-211-0/+29
| | | | | | | | | type to truncate to should be the number of bits of the value that are preserved, not the number that are clobbered with sign-extension. This fixes regressions in ldecod. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@69704 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename ScalarEvolution's getIterationCount to getBackedgeTakenCount,Dan Gohman2009-02-2415-15/+15
| | | | | | | | | | 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
* Wind SCEV back in time, to Nov 18th. This 'fixes' PR3275, PR3294, PR3295,Nick Lewycky2009-01-137-0/+7
| | | | | | | PR3296 and PR3302. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@62160 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't try to analyze this "backward" case. This is overly conservative Nick Lewycky2009-01-021-0/+40
| | | | | | | pending a correct solution. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@61589 91177308-0d34-0410-b5e6-96231b3b80d8
* Generalize support for analyzing loops to include SLE/SGE loop exit conditionsNick Lewycky2008-12-164-2/+41
| | | | | | | 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
* Revert my re-instated reverted commit, fixes the bootstrap build on x86-64 ↵Nick Lewycky2008-12-122-0/+2
| | | | | | linux. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60951 91177308-0d34-0410-b5e6-96231b3b80d8
* Sneaky, sneaky: move the -1 to the outside of the SMax. Reinstate theNick Lewycky2008-12-112-1/+27
| | | | | | | 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
* xfail this for now.Evan Cheng2008-12-091-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60777 91177308-0d34-0410-b5e6-96231b3b80d8
* It's easy to handle SLE/SGE when the loop has a unit stride.Nick Lewycky2008-12-091-0/+24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@60748 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a utility function that detects whether a loop is guaranteed to be finite.Nick Lewycky2008-11-183-0/+91
| | | | | | | | | | | | 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
* Don't brute-force analyze cubic or higher polynomials.Nick Lewycky2008-11-161-0/+19
| | | | | | | | 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
* Don't crash analyzing certain quadratics (addrec of {X,+,Y,+,1}).Nick Lewycky2008-11-031-0/+21
| | | | | | | 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
* Finally re-apply r46959. This is made feasible by the combinationDan Gohman2008-09-162-3/+4
| | | | | | | of r56230, r56232, and r56246. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56247 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix spacing in the grep line for this test, following the recentDan Gohman2008-09-161-1/+1
| | | | | | | SCEV-whitespace changes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56234 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach ScalarEvolution to consider loop preheaders in the search forDan Gohman2008-09-152-0/+234
| | | | | | | | 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
* Fix WriteAsOperand to not emit a leading space character. AdjustDan Gohman2008-09-149-9/+9
| | | | | | | | | | | | | | | | | | | 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
* Extend ScalarEvolution's executesAtLeastOnce logic to be able toDan Gohman2008-08-121-0/+35
| | | | | | | | | 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
* PR2621: Improvements to the SCEV AddRec binomial expansion. This Eli Friedman2008-08-042-0/+81
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Another SCEV issue from PR2607; essentially the same issue, but this Eli Friedman2008-07-301-0/+24
| | | | | | | | | | | | | 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
* Fix for PR2607: SCEV miscomputing the loop count for loops with an Eli Friedman2008-07-301-0/+27
| | | | | | | | | | | | | | 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
* Fix PR2088. Use modulo linear equation solver to compute loop iterationWojciech Matyjewicz2008-07-203-1/+30
| | | | | | | count. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53810 91177308-0d34-0410-b5e6-96231b3b80d8
* XFAIL this test.Nick Lewycky2008-07-191-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53793 91177308-0d34-0410-b5e6-96231b3b80d8
* While testing particular algorithms to compute loop iteration count the bruteWojciech Matyjewicz2008-07-195-7/+10
| | | | | | | | | | | | | | | force evaluation (ComputeIterationCountExhaustively) should be turned off. It doesn't apply to trip-count2.ll because this file tests the brute force evaluation. The test for PR2364 (2008-05-25-NegativeStepToZero.ll) currently fails showing that the patch for this bug doesn't work. I'll fix it in a few hours with a patch for PR2088. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@53792 91177308-0d34-0410-b5e6-96231b3b80d8
* Stop creating extraneous smax/umax in SCEV. This removes a regression where weNick Lewycky2008-07-123-1/+67
| | | | | | | 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
* Crash less. The i64 restriction in BinomialCoefficient caused some problemsNick Lewycky2008-06-131-0/+43
| | | | | | | | | 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
* Whoops -- forgot PR reference on this test.Nick Lewycky2008-05-261-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51569 91177308-0d34-0410-b5e6-96231b3b80d8
* Use {} instead of "" in RUN lines.Nick Lewycky2008-05-261-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51561 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't treat values as signed when looking at loop steppings in HowForToNonZero.Nick Lewycky2008-05-251-0/+20
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51560 91177308-0d34-0410-b5e6-96231b3b80d8
* Temporarily reverting 46959.Evan Cheng2008-02-251-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47542 91177308-0d34-0410-b5e6-96231b3b80d8
* Add 'umax' similar to 'smax' SCEV. Closes PR2003.Nick Lewycky2008-02-202-1/+18
| | | | | | | | | | | | | | | | 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(). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47360 91177308-0d34-0410-b5e6-96231b3b80d8
* Now that ScalarEvolution::print writes to the correct stream, there is Wojciech Matyjewicz2008-02-127-7/+7
| | | | | | | no need to redirect stderr into stdout. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47009 91177308-0d34-0410-b5e6-96231b3b80d8
* Change negative grep into positive one in my yesterday's testcase.Wojciech Matyjewicz2008-02-121-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47008 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix PR2002. Suppose n is the initial value for the induction Wojciech Matyjewicz2008-02-121-0/+16
| | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@47007 91177308-0d34-0410-b5e6-96231b3b80d8
* If the LHS of the comparison is a loop-invariant we also want to move it Wojciech Matyjewicz2008-02-111-0/+15
| | | | | | | | | 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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46959 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix PR1798 - an error in the evaluation of SCEVAddRecExpr at an Wojciech Matyjewicz2008-02-111-1/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | arbitrary iteration. The patch: 1) changes SCEVSDivExpr into SCEVUDivExpr, 2) replaces PartialFact() function with BinomialCoefficient(); the computations (essentially, the division) in BinomialCoefficient() are performed with the apprioprate bitwidth necessary to avoid overflow; unsigned division is used instead of the signed one. Computations in BinomialCoefficient() require support from the code generator for APInts. Currently, we use a hack rounding up the neccessary bitwidth to the nearest power of 2. The hack is easy to turn off in future. One remaining issue: we assume the divisor of the binomial coefficient formula can be computed accurately using 16 bits. It means we can handle AddRecs of length up to 9. In future, we should use APInts to evaluate the divisor. Thanks to Nicholas for cooperation! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@46955 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix bug in regression tests that ignored stderr output in RUN lines. Updated ↵Tanya Lattner2007-11-281-1/+1
| | | | | | | | | tests and fixed broken run lines. XFAILed 3 arm regressions (will file bugs) git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44389 91177308-0d34-0410-b5e6-96231b3b80d8
* Change grep '' to grep {}.Dan Gohman2007-11-273-3/+3
| | | | | | | Change 2>&1 | to |&. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44344 91177308-0d34-0410-b5e6-96231b3b80d8
* Add new SCEV, SCEVSMax. This allows LLVM to analyze do-while loops.Nick Lewycky2007-11-252-0/+30
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44319 91177308-0d34-0410-b5e6-96231b3b80d8
* Be more careful when transforming | to +. Patch from Wojciech Matyjewicz.Nick Lewycky2007-11-201-0/+18
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44248 91177308-0d34-0410-b5e6-96231b3b80d8
* Reverted r44163 per requestAnton Korobeynikov2007-11-151-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44177 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix handling of overflow in loop calculation by adding new UDiv SCEV. This SCEVNick Lewycky2007-11-151-0/+24
| | | | | | | | is disabled in the sense that it will refuse to create one from a UDiv instruction, until the code is better tested. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44163 91177308-0d34-0410-b5e6-96231b3b80d8
* Build the correct range for loops with unusual bounds. Fix from Jay Foad.Nick Lewycky2007-09-271-0/+21
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42394 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-08-15 05:43:03 +0000