summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/IndVarSimplify
Commit message (Collapse)AuthorAgeFilesLines
...
* Reverts r221772 which fails testsJingyue Wu2014-11-121-37/+0
| | | | llvm-svn: 221773
* Disable indvar widening if arithmetics on the wider type are more expensiveJingyue Wu2014-11-121-0/+37
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: IndVarSimplify should not widen an indvar if arithmetics on the wider indvar are more expensive than those on the narrower indvar. For instance, although NVPTX64 treats i64 as a legal type, an ADD on i64 is twice as expensive as that on i32, because the hardware needs to simulate a 64-bit integer using two 32-bit integers. Split from D6188, and based on D6195 which adds NVPTXTargetTransformInfo. Fixes PR21148. Test Plan: Added @indvar_32_bit that verifies we do not widen an indvar if the arithmetics on the wider type are more expensive. Reviewers: jholewinski, eliben, meheff, atrick Reviewed By: atrick Subscribers: jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D6196 llvm-svn: 221772
* Revert "r219834 - Teach ScalarEvolution to sharpen range information"Sanjoy Das2014-10-152-40/+2
| | | | | | | This change breaks the asan buildbots: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/13468 llvm-svn: 219878
* Teach ScalarEvolution to sharpen range information.Sanjoy Das2014-10-152-2/+40
| | | | | | | | | | | | If x is known to have the range [a, b) in a loop predicated by (icmp ne x, a), its range can be sharpened to [a + 1, b). Get ScalarEvolution and hence IndVars to exploit this fact. This change triggers an optimization to widen-loop-comp.ll, so it had to be edited to get it to pass. phabricator: http://reviews.llvm.org/D5639 llvm-svn: 219834
* This patch teaches ScalarEvolution to pick and use !range metadata.Sanjoy Das2014-10-101-0/+37
| | | | | | | | | | | | It also makes it more aggressive in querying range information by adding a call to isKnownPredicateWithRanges to isLoopBackedgeGuardedByCond and isLoopEntryGuardedByCond. phabricator: http://reviews.llvm.org/D5638 Reviewed by: atrick, hfinkel llvm-svn: 219532
* [BUG][INDVAR] Fix for PR21014: wrong SCEV operands commuting for ↵Zinovy Nis2014-10-021-2/+6
| | | | | | | | | | | | non-commutative instructions My commit rL216160 introduced a bug PR21014: IndVars widens code 'for (i = ; i < ...; i++) arr[ CONST - i]' into 'for (i = ; i < ...; i++) arr[ i - CONST]' thus inverting index expression. This patch fixes it. Thanks to Jörg Sonnenberger for pointing. Differential Revision: http://reviews.llvm.org/D5576 llvm-svn: 218867
* [IndVarSimplify] Widen loop unsigned compares.Chad Rosier2014-09-301-0/+28
| | | | | | | This patch extends r217953 to handle unsigned comparison. Phabricator revision: http://reviews.llvm.org/D5526 llvm-svn: 218659
* [IndVar] Don't widen loop compare unless IV user is sign extended.Chad Rosier2014-09-261-0/+26
| | | | | | PR21030 llvm-svn: 218539
* [IndVarSimplify] Partially revert r217953 to see if this fixes the bots.Chad Rosier2014-09-171-28/+0
| | | | | | Specifically, disable widening of unsigned compare instructions. llvm-svn: 217962
* [IndVarSimplify] Widen loop compare instructions.Chad Rosier2014-09-173-5/+172
| | | | | | | This improves other optimizations such as LSR. A sext may be added to the compare's other operand, but this can often be hoisted outside of the loop. llvm-svn: 217953
* IndVarSimplify: Don't let LFTR compare against a poison valueDavid Majnemer2014-09-035-13/+240
| | | | | | | | | | | | | | LinearFunctionTestReplace tries to use the *next* indvar to compare against when possible. However, it may be the case that the calculation for the next indvar has NUW/NSW flags and that it may only be safely used inside the loop. Using it in a comparison to calculate the exit condition could result in observing poison. This fixes PR20680. Differential Revision: http://reviews.llvm.org/D5174 llvm-svn: 217102
* [INDVARS] Extend using of widening of induction variables for the cases of ↵Zinovy Nis2014-08-211-4/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | "sub nsw" and "mul nsw" instructions. Currently only "add nsw" are widened. This patch eliminates tons of "sext" instructions for 64 bit code (and the corresponding target code) in cases like: int N = 100; float **A; void foo(int x0, int x1) { float * A_cur = &A[0][0]; float * A_next = &A[1][0]; for(int x = x0; x < x1; ++x). { // Currently only [x+N] case is widened. Others 2 cases lead to sext. // This patch fixes it, so all 3 cases do not need sext. const float div = A_cur[x + N] + A_cur[x - N] + A_cur[x * N]; A_next[x] = div; } } ... > clang++ test.cpp -march=core-avx2 -Ofast -fno-unroll-loops -fno-tree-vectorize -S -o - Differential Revision: http://reviews.llvm.org/D4695 llvm-svn: 216160
* Add a description to the test from r211433 explaining why it's written that way.Benjamin Kramer2014-06-221-0/+6
| | | | llvm-svn: 211465
* SCEVExpander: Fold constant PHIs harder. The logic below only understands ↵Benjamin Kramer2014-06-211-0/+51
| | | | | | | | proper IVs. PR20093. llvm-svn: 211433
* ScalarEvolution: Fix handling of AddRecs in isKnownPredicateJustin Bogner2014-05-231-0/+30
| | | | | | | | | | | | | ScalarEvolution::isKnownPredicate() can wrongly reduce a comparison when both the LHS and RHS are SCEVAddRecExprs. This checks that both LHS and RHS are guarded in the case when both are SCEVAddRecExprs. The test case is against indvars because I could not find a way to directly test SCEV. Patch by Sanjay Patel! llvm-svn: 209487
* [LPM] Fix PR18642, a pretty nasty bug in IndVars that "never mattered"Chandler Carruth2014-01-291-0/+51
| | | | | | | | | | | | | | | | | | | | | | | because of the inside-out run of LoopSimplify in the LoopPassManager and the fact that LoopSimplify couldn't be "preserved" across two independent LoopPassManagers. Anyways, in that case, IndVars wasn't correctly preserving an LCSSA PHI node because it thought it was rewriting (via SCEV) the incoming value to a loop invariant value. While it may well be invariant for the current loop, it may be rewritten in terms of an enclosing loop's values. This in and of itself is fine, as the LCSSA PHI node in the enclosing loop for the inner loop value we're rewriting will have its own LCSSA PHI node if used outside of the enclosing loop. With me so far? Well, the current loop and the enclosing loop may share an exiting block and exit block, and when they do they also share LCSSA PHI nodes. In this case, its not valid to RAUW through the LCSSA PHI node. Expected crazy test included. llvm-svn: 200372
* [LPM] Make LoopSimplify no longer a LoopPass and instead both a utilityChandler Carruth2014-01-231-6/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | function and a FunctionPass. This has many benefits. The motivating use case was to be able to compute function analysis passes *after* running LoopSimplify (to avoid invalidating them) and then to run other passes which require LoopSimplify. Specifically passes like unrolling and vectorization are critical to wire up to BranchProbabilityInfo and BlockFrequencyInfo so that they can be profile aware. For the LoopVectorize pass the only things in the way are LoopSimplify and LCSSA. This fixes LoopSimplify and LCSSA is next on my list. There are also a bunch of other benefits of doing this: - It is now very feasible to make more passes *preserve* LoopSimplify because they can simply run it after changing a loop. Because subsequence passes can assume LoopSimplify is preserved we can reduce the runs of this pass to the times when we actually mutate a loop structure. - The new pass manager should be able to more easily support loop passes factored in this way. - We can at long, long last observe that LoopSimplify is preserved across SCEV. This *halves* the number of times we run LoopSimplify!!! Now, getting here wasn't trivial. First off, the interfaces used by LoopSimplify are all over the map regarding how analysis are updated. We end up with weird "pass" parameters as a consequence. I'll try to clean at least some of this up later -- I'll have to have it all clean for the new pass manager. Next up I discovered a really frustrating bug. LoopUnroll *claims* to preserve LoopSimplify. That's actually a lie. But the way the LoopPassManager ends up running the passes, it always ran LoopSimplify on the unrolled-into loop, rectifying this oversight before any verification could kick in and point out that in fact nothing was preserved. So I've added code to the unroller to *actually* simplify the surrounding loop when it succeeds at unrolling. The only functional change in the test suite is that we now catch a case that was previously missed because SCEV and other loop transforms see their containing loops as simplified and thus don't miss some opportunities. One test case has been converted to check that we catch this case rather than checking that we miss it but at least don't get the wrong answer. Note that I have #if-ed out all of the verification logic in LoopSimplify! This is a temporary workaround while extracting these bits from the LoopPassManager. Currently, there is no way to have a pass in the LoopPassManager which preserves LoopSimplify along with one which does not. The LPM will try to verify on each loop in the nest that LoopSimplify holds but the now-Function-pass cannot distinguish what loop is being verified and so must try to verify all of them. The inner most loop is clearly no longer simplified as there is a pass which didn't even *attempt* to preserve it. =/ Once I get LCSSA out (and maybe LoopVectorize and some other fixes) I'll be able to re-enable this check and catch any places where we are still failing to preserve LoopSimplify. If this causes problems I can back this out and try to commit *all* of this at once, but so far this seems to work and allow much more incremental progress. llvm-svn: 199884
* Fix PR18449: SCEV needs more precise max BECount for multi-exit loop.Andrew Trick2014-01-151-0/+31
| | | | llvm-svn: 199299
* Fix broken CHECK lines.Benjamin Kramer2014-01-111-2/+2
| | | | llvm-svn: 199016
* Reapply r198654 "indvars: sink truncates outside the loop."Andrew Trick2014-01-071-3/+4
| | | | | | | | | | | This doesn't seem to have actually broken anything. It was paranoia on my part. Trying again now that bots are more stable. This is a follow up of the r198338 commit that added truncates for lcssa phi nodes. Sinking the truncates below the phis cleans up the loop and simplifies subsequent analysis within the indvars pass. llvm-svn: 198678
* Revert "indvars: sink truncates outside the loop."Andrew Trick2014-01-071-4/+3
| | | | | | | | This reverts commit r198654. One of the bots reported a SciMark failure. llvm-svn: 198659
* indvars: sink truncates outside the loop.Andrew Trick2014-01-071-3/+4
| | | | | | | | This is a follow up of the r198338 commit that added truncates for lcssa phi nodes. Sinking the truncates below the phis cleans up the loop and simplifies subsequent analysis within the indvars pass. llvm-svn: 198654
* indvars: insert truncate at loop boundary to avoid redundant IVs.Andrew Trick2014-01-021-0/+39
| | | | | | | | | When widening an IV to remove s/zext, we generally try to eliminate the original narrow IV. However, LCSSA phi nodes outside the loop were still using the original IV. Clean this up more aggressively to avoid redundancy in generated code. llvm-svn: 198338
* Add support to indvars for optimizing sadd.with.overflow.Andrew Trick2013-12-231-0/+56
| | | | | | | | | | | | | | | | Split sadd.with.overflow into add + sadd.with.overflow to allow analysis and optimization. This should ideally be done after InstCombine, which can perform code motion (eventually indvars should run after all canonical instcombines). We want ISEL to recombine the add and the check, at least on x86. This is currently under an option for reducing live induction variables: -liv-reduce. The next step is reducing liveness of IVs that are live out of the overflow check paths. Once the related optimizations are fully developed, reviewed and tested, I do expect this to become default. llvm-svn: 197926
* Add test case for PR12377, it was fixed by r194116.Benjamin Kramer2013-11-061-4/+30
| | | | llvm-svn: 194147
* Rewrite SCEV's backedge taken count computation.Andrew Trick2013-11-062-7/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Patch by Michele Scandale! Rewrite of the functions used to compute the backedge taken count of a loop on LT and GT comparisons. I decided to split the handling of LT and GT cases becasue the trick "a > b == -a < -b" in some cases prevents the trip count computation due to the multiplication by -1 on the two operands of the comparison. This issue comes from the conservative computation of value range of SCEVs: taking the negative SCEV of an expression that have a small positive range (e.g. [0,31]), we would have a SCEV with a fullset as value range. Indeed, in the new rewritten function I tried to better handle the maximum backedge taken count computation when MAX/MIN expression are used to handle the cases where no entry guard is found. Some test have been modified in order to check the new value correctly (I manually check them and reasoning on possible overflow the new values seem correct). I finally added a new test case related to the multiplication by -1 issue on GT comparisons. llvm-svn: 194116
* Fix a bug in LinearFunctionTestReplace that created invalid loop exit checks.Juergen Ributzka2013-10-241-0/+26
| | | | | | Reviewed by Andy llvm-svn: 193303
* Teach loop-idiom about address space pointer sizesMatt Arsenault2013-09-111-0/+69
| | | | llvm-svn: 190491
* [tests] Cleanup initialization of test suffixes.Daniel Dunbar2013-08-161-1/+0
| | | | | | | | | | | | | | | | | - Instead of setting the suffixes in a bunch of places, just set one master list in the top-level config. We now only modify the suffix list in a few suites that have one particular unique suffix (.ml, .mc, .yaml, .td, .py). - Aside from removing the need for a bunch of lit.local.cfg files, this enables 4 tests that were inadvertently being skipped (one in Transforms/BranchFolding, a .s file each in DebugInfo/AArch64 and CodeGen/PowerPC, and one in CodeGen/SI which is now failing and has been XFAILED). - This commit also fixes a bunch of config files to use config.root instead of older copy-pasted code. llvm-svn: 188513
* Teach indvars to generate nsw/nuw flags when widening an induction variable.Andrew Trick2013-07-141-0/+29
| | | | | | Fixes PR16600. llvm-svn: 186272
* Update Transforms tests to use CHECK-LABEL for easier debugging. No ↵Stephen Lin2013-07-1416-39/+39
| | | | | | | | | | | | | | | | | | | | | | functionality change. This update was done with the following bash script: find test/Transforms -name "*.ll" | \ while read NAME; do echo "$NAME" if ! grep -q "^; *RUN: *llc" $NAME; then TEMP=`mktemp -t temp` cp $NAME $TEMP sed -n "s/^define [^@]*@\([A-Za-z0-9_]*\)(.*$/\1/p" < $NAME | \ while read FUNC; do sed -i '' "s/;\(.*\)\([A-Za-z0-9_]*\):\( *\)@$FUNC\([( ]*\)\$/;\1\2-LABEL:\3@$FUNC(/g" $TEMP done mv $TEMP $NAME fi done llvm-svn: 186268
* LFTR improvement to avoid truncation.Andrew Trick2013-07-121-0/+44
| | | | | | This is a reimplemntation of the patch originally in r186107. llvm-svn: 186215
* Revert "indvars: Improve LFTR by eliminating truncation when comparingChandler Carruth2013-07-121-25/+0
| | | | | | | | | | | | | | | | | | | against a constant." This reverts commit r186107. It didn't handle wrapping arithmetic in the loop correctly and thus caused the following C program to count from 0 to UINT64_MAX instead of from 0 to 255 as intended: #include <stdio.h> int main() { unsigned char first = 0, last = 255; do { printf("%d\n", first); } while (first++ != last); } Full test case and instructions to reproduce with just the -indvars pass sent to the original review thread rather than to r186107's commit. llvm-svn: 186152
* indvars: Improve LFTR by eliminating truncation when comparing against a ↵Andrew Trick2013-07-111-0/+25
| | | | | | | | | | | | | | | | | constant. Patch by Michele Scandale! Adds a special handling of the case where, during the loop exit condition rewriting, the exit value is a constant of bitwidth lower than the type of the induction variable: instead of introducing a trunc operation in order to match correctly the operand types, it allows to convert the constant value to an equivalent constant, depending on the initial value of the induction variable and the trip count, in order have an equivalent comparison between the induction variable and the new constant. llvm-svn: 186107
* IndVarSimplify: check if loop invariant expansion can trapDavid Majnemer2013-06-041-0/+32
| | | | | | | | | | | | | | | IndVarSimplify is willing to move divide instructions outside of their loop bodies if they are invariant of the loop. However, it may not be safe to expand them if we do not know if they can trap. Instead, check to see if it is not safe to expand the instruction and skip the expansion. This fixes PR16041. Testcase by Rafael Ávila de Espíndola. llvm-svn: 183239
* IndVarSimplify: do not recompute an IV value outside of the loop if :Arnaud A. de Grandmaison2013-03-191-0/+69
| | | | | | | - it is trivially known to be used inside the loop in a way that can not be optimized away - there is no use outside of the loop which can take advantage of the computation hoisting llvm-svn: 177432
* Revert the test moves from 176733. Use "REQUIRES: asserts" instead.Jan Wen Voung2013-03-122-4/+1
| | | | llvm-svn: 176873
* Disable statistics on Release builds and move tests that depend on -stats.Jan Wen Voung2013-03-082-0/+4
| | | | | | | | | | | | | | | | | Summary: Statistics are still available in Release+Asserts (any +Asserts builds), and stats can also be turned on with LLVM_ENABLE_STATS. Move some of the FastISel stats that were moved under DEBUG() back out of DEBUG(), since stats are disabled across the board now. Many tests depend on grepping "-stats" output. Move those into a orig_dir/Stats/. so that they can be marked as unsupported when building without statistics. Differential Revision: http://llvm-reviews.chandlerc.com/D486 llvm-svn: 176733
* Tests: rewrite 'opt ... %s' to 'opt ... < %s' so that opt does not emit a ↵Dmitri Gribenko2012-12-301-1/+1
| | | | | | | | ModuleID This is done to avoid odd test failures, like the one fixed in r171243. llvm-svn: 171250
* Tests: rewrite 'opt ... %s' to 'opt ... < %s' so that opt does not emit a ↵Dmitri Gribenko2012-12-301-1/+1
| | | | | | | | ModuleID This is done to avoid odd test failures, like the one fixed in r171243. llvm-svn: 171246
* Follow up to 168711: It's safe to base this analysis on the found compare, ↵Benjamin Kramer2012-11-291-0/+49
| | | | | | | | just return the value for the right predicate. Thanks to Andy for catching this. llvm-svn: 168921
* SCEV: Even if the latch terminator is foldable we can't deduce the result of ↵Benjamin Kramer2012-11-271-0/+54
| | | | | | | | an unrelated condition with it. Fixes PR14432. llvm-svn: 168711
* Disallow the undocumented practice of starting the datalayout string with '-'.Patrik Hägglund2012-11-231-1/+1
| | | | | | Update some test cases accordingly. llvm-svn: 168516
* Fix SCEV cache invalidation in LCSSA and LoopSimplify.Benjamin Kramer2012-10-261-0/+421
| | | | | | | | | | | | | | The LoopSimplify bug is pretty harmless because the loop goes from unanalyzable to analyzable but the LCSSA bug is very nasty. It only comes into play with a specific order of the LoopPassManager worklist and can cause actual miscompilations, when a SCEV refers to a value that has been replaced with PHI node. SCEVExpander may then insert code into the wrong place, either violating domination or randomly miscompiling stuff. Comes with an extensive test case reduced from the test-suite with bugpoint+SCEVValidator. llvm-svn: 166787
* Indvars: Don't recursively delete instruction during BB iteration.Benjamin Kramer2012-10-191-0/+18
| | | | | | | This can invalidate the iterators leading to use after frees and crashes. Fixes PR12536. llvm-svn: 166291
* SCEVExpander: Don't crash when trying to merge two constant phis.Benjamin Kramer2012-10-192-1/+27
| | | | | | Just constant fold them so they can't cause any trouble. Fixes PR12627. llvm-svn: 166286
* Move TargetData to DataLayout.Micah Villmow2012-10-081-2/+2
| | | | llvm-svn: 165403
* Fix PR13967.Jakub Staszak2012-10-031-0/+26
| | | | llvm-svn: 165187
* indvars: Linear function test replace should avoid reusing undef.Andrew Trick2012-07-182-4/+29
| | | | | | | | | | | | | | | | | | | | | | | Fixes PR13371: indvars pass incorrectly substitutes 'undef' values. I do not like this fix. It's needed until/unless the meaning of undef changes. It attempts to be complete according to the IR spec, but I don't have much confidence in the implementation given the difficulty testing undefined behavior. Worse, this invalidates some of my hard-fought work on indvars and LSR to optimize pointer induction variables. It results benchmark regressions, which I'll track internally. On x86_64 no LTO I see: -3% huffbench -3% 400.perlbench -8% fhourstones My only suggestion for recovering is to change the meaning of undef. If we could trust an arbitrary instruction to produce a some real value that can be manipulated (e.g. incremented) according to non-undef rules, then this case could be easily handled with SCEV. llvm-svn: 160421
* Fix the remaining TCL-style quotes found in the testsuite. This isChandler Carruth2012-07-025-6/+6
| | | | | | | | | | | | | | | | | another mechanical change accomplished though the power of terrible Perl scripts. I have manually switched some "s to 's to make escaping simpler. While I started this to fix tests that aren't run in all configurations, the massive number of tests is due to a really frustrating fragility of our testing infrastructure: things like 'grep -v', 'not grep', and 'expected failures' can mask broken tests all too easily. Essentially, I'm deeply disturbed that I can change the testsuite so radically without causing any change in results for most platforms. =/ llvm-svn: 159547
OpenPOWER on IntegriCloud