summaryrefslogtreecommitdiffstats
path: root/llvm/test/Analysis/ScalarEvolution
Commit message (Collapse)AuthorAgeFilesLines
...
* Add testcases for PR4538, PR4537, and PR4534.Dan Gohman2009-07-132-0/+384
| | | | llvm-svn: 75533
* When comparing constants, consider a less wide constant to be "less complex"Nick Lewycky2009-07-041-0/+16
| | | | | | | than a wider one, before trying to compare their contents which will crash if their sizes are different. llvm-svn: 74792
* Add a testcase demoing some of ScalarEvolution's new trip count logic.Dan Gohman2009-06-241-0/+37
| | | | llvm-svn: 74049
* Fix a bug in the trip-count computation with And/Or. If either of theDan Gohman2009-06-221-0/+150
| | | | | | sides is CouldNotCompute, the resulting exact count must be CouldNotCompute. llvm-svn: 73920
* Fix llvm::ComputeNumSignBits to handle pointer typesDan Gohman2009-06-221-0/+220
| | | | | | conservatively correctly, instead of aborting. llvm-svn: 73908
* Teach ScalarEvolution how to analyze loops with multiple exitDan Gohman2009-06-221-0/+48
| | | | | | | | | blocks, and also exit blocks with multiple conditions (combined with (bitwise) ands and ors). It's often infeasible to compute an exact trip count in such cases, but a useful upper bound can often be found. llvm-svn: 73866
* Fix ScalarEvolution's backedge-taken count computations to check forDan Gohman2009-06-212-2/+11
| | | | | | | | overflow when computing a integer division to round up. Thanks to Nick Lewycky for noticing this! llvm-svn: 73862
* Teach ScalarEvolution how to recognize another xor(and(x, C), C) case.Dan Gohman2009-06-181-2/+3
| | | | | | | If C is a single bit and the and gets analyzed as a truncate and zero-extend, the xor can be represnted as an add. llvm-svn: 73664
* Add -disable-output to a bunch of tests that don't care about the output.Dan Gohman2009-06-1730-31/+31
| | | | llvm-svn: 73633
* Fix ScalarEvolution's Xor handling to not assume that an AndDan Gohman2009-06-171-0/+11
| | | | | | | that gets recognized with a SCEVZeroExtendExpr must be an And with a low-bits mask. With r73540, this is no longer the case. llvm-svn: 73594
* Split the Add, Sub, and Mul instruction opcodes into separateDan Gohman2009-06-043-6/+6
| | | | | | | | | | | | | | | integer and floating-point opcodes, introducing FAdd, FSub, and FMul. For now, the AsmParser, BitcodeReader, and IRBuilder all preserve backwards compatability, and the Core LLVM APIs preserve backwards compatibility for IR producers. Most front-ends won't need to change immediately. This implements the first step of the plan outlined here: http://nondot.org/sabre/LLVMNotes/IntegerOverflow.txt llvm-svn: 72897
* Teach ScalarEvolution to recognize x^-1 in the case where non-demandedDan Gohman2009-05-181-0/+8
| | | | | | bits have been stripped out by instcombine. llvm-svn: 72010
* Make ScalarEvolution::isLoopGuardedByCond work even when the edgeDan Gohman2009-05-181-1/+1
| | | | | | entering a loop is a non-split critical edge. llvm-svn: 72004
* Add nounwind to a few tests.Dan Gohman2009-05-181-1/+1
| | | | llvm-svn: 72002
* Allow scalar evolution to compute iteration counts for loops with a Eli Friedman2009-05-091-0/+27
| | | | | | pointer-based condition. This fixes PR3171. llvm-svn: 71354
* Fix bogus overflow checks by replacing them with actualDan Gohman2009-05-081-0/+10
| | | | | | overflow checks. llvm-svn: 71284
* Fold trunc casts into add-recurrence expressions, allowing theDan Gohman2009-05-081-0/+24
| | | | | | | add-recurrence to be exposed. Add a new SCEV folding rule to help simplify expressions in the presence of these extra truncs. llvm-svn: 71264
* 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. llvm-svn: 70554
* 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. llvm-svn: 70509
* 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. llvm-svn: 70421
* Fix this test to match the new output from scalar-evolution.Dan Gohman2009-04-291-1/+1
| | | | llvm-svn: 70410
* 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. llvm-svn: 70405
* Fix a grammaro in a comment.Dan Gohman2009-04-281-1/+1
| | | | llvm-svn: 70331
* Simplify trunc(extend(x)) in SCEVs, just for completeness. Also fix some oddNick Lewycky2009-04-231-0/+37
| | | | | | whitespace in the same file. llvm-svn: 69870
* Testcase for PR3909.Owen Anderson2009-04-231-0/+30
| | | | llvm-svn: 69868
* 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. llvm-svn: 69704
* 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. llvm-svn: 65382
* Wind SCEV back in time, to Nov 18th. This 'fixes' PR3275, PR3294, PR3295,Nick Lewycky2009-01-137-0/+7
| | | | | | PR3296 and PR3302. llvm-svn: 62160
* Don't try to analyze this "backward" case. This is overly conservative Nick Lewycky2009-01-021-0/+40
| | | | | | pending a correct solution. llvm-svn: 61589
* 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. llvm-svn: 61082
* Revert my re-instated reverted commit, fixes the bootstrap build on x86-64 ↵Nick Lewycky2008-12-122-0/+2
| | | | | | linux. llvm-svn: 60951
* 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. llvm-svn: 60881
* xfail this for now.Evan Cheng2008-12-091-0/+1
| | | | llvm-svn: 60777
* It's easy to handle SLE/SGE when the loop has a unit stride.Nick Lewycky2008-12-091-0/+24
| | | | llvm-svn: 60748
* 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. llvm-svn: 59528
* 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. llvm-svn: 59384
* 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. llvm-svn: 58592
* Finally re-apply r46959. This is made feasible by the combinationDan Gohman2008-09-162-3/+4
| | | | | | of r56230, r56232, and r56246. llvm-svn: 56247
* Fix spacing in the grep line for this test, following the recentDan Gohman2008-09-161-1/+1
| | | | | | SCEV-whitespace changes. llvm-svn: 56234
* 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. llvm-svn: 56232
* 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) llvm-svn: 56196
* 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. llvm-svn: 54697
* 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. llvm-svn: 54332
* 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. llvm-svn: 54194
* 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. llvm-svn: 54184
* Fix PR2088. Use modulo linear equation solver to compute loop iterationWojciech Matyjewicz2008-07-203-1/+30
| | | | | | count. llvm-svn: 53810
* XFAIL this test.Nick Lewycky2008-07-191-0/+1
| | | | llvm-svn: 53793
* 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. llvm-svn: 53792
* 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). llvm-svn: 53508
* 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. llvm-svn: 52248
OpenPOWER on IntegriCloud