summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/IndVarSimplify
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Convert all tests using TCL-style quoting to use shell-style quoting.Chandler Carruth2012-07-027-7/+7
| | | | | | | | | | | | | | | | | | | | | | | | This was done through the aid of a terrible Perl creation. I will not paste any of the horrors here. Suffice to say, it require multiple staged rounds of replacements, state carried between, and a few nested-construct-parsing hacks that I'm not proud of. It happens, by luck, to be able to deal with all the TCL-quoting patterns in evidence in the LLVM test suite. If anyone is maintaining large out-of-tree test trees, feel free to poke me and I'll send you the steps I used to convert things, as well as answer any painful questions etc. IRC works best for this type of thing I find. Once converted, switch the LLVM lit config to use ShTests the same as Clang. In addition to being able to delete large amounts of Python code from 'lit', this will also simplify the entire test suite and some of lit's architecture. Finally, the test suite runs 33% faster on Linux now. ;] For my 16-hardware-thread (2x 4-core xeon e5520): 36s -> 24s llvm-svn: 159525
* Teach SCEV's icmp simplification logic that a-b == 0 is equivalent to a == b.Benjamin Kramer2012-05-301-0/+42
| | | | | | | | | | | | | | | This also required making recursive simplifications until nothing changes or a hard limit (currently 3) is hit. With the simplification in place indvars can canonicalize loops of the form for (unsigned i = 0; i < a-b; ++i) into for (unsigned i = 0; i != a-b; ++i) which used to fail because SCEV created a weird umax expr for the backedge taken count. llvm-svn: 157701
* Convert -indvars tests that rely on SCEV expansion to -loop-reduce tests.Andrew Trick2012-03-222-120/+0
| | | | llvm-svn: 153259
* Remove tests: indvars trivially preserves GEPs now.Andrew Trick2012-03-224-203/+0
| | | | llvm-svn: 153258
* Remove test: trivial canonical IV test which is covered by other SCEV tests.Andrew Trick2012-03-221-31/+0
| | | | llvm-svn: 153257
* Remove redundant -enable-iv-rewrite=false flags from test cases.Andrew Trick2012-03-2210-13/+7
| | | | llvm-svn: 153255
* Replace all instances of dg.exp file with lit.local.cfg, since all tests are ↵Eli Bendersky2012-02-162-3/+1
| | | | | | | | run with LIT now and now Dejagnu. dg.exp is no longer needed. Patch reviewed by Daniel Dunbar. It will be followed by additional cleanup patches. llvm-svn: 150664
* Extended replaceCongruentPhis to handle mixed phi types.Andrew Trick2012-01-071-2/+2
| | | | llvm-svn: 147707
* Reenable this IndVars unit test.Andrew Trick2011-11-291-4/+1
| | | | | | SCEV can't optimize undef in all cases, which is a separate issue from this test case. llvm-svn: 145343
* Upgrade syntax of tests using volatile instructions to use 'load volatile' ↵Chris Lattner2011-11-273-4/+4
| | | | | | instead of 'volatile load', which is archaic. llvm-svn: 145171
* XFAIL this test until I figure out what indvars is doing here (or find ↵Benjamin Kramer2011-11-201-0/+3
| | | | | | someone who does) llvm-svn: 145008
* Fix an overly general check in SimplifyIndvar to handle useless phi cycles.Andrew Trick2011-11-171-0/+29
| | | | | | | | | | | | | | The right way to check for a binary operation is cast<BinaryOperator>. The original check: cast<Instruction> && numOperands() == 2 would match phi "instructions", leading to an infinite loop in extreme corner case: a useless phi with operands [self, constant] that prior optimization passes failed to remove, being used in the loop by another useless phi, in turn being used by an lshr or udiv. Fixes PR11350: runaway iteration assertion. llvm-svn: 144935
* Fix SCEV overly optimistic back edge taken count for multi-exit loops.Andrew Trick2011-11-163-2/+53
| | | | | | Fixes PR11375: Different results for 'clang++ huh.cpp'... llvm-svn: 144746
* Rewrite LinearFunctionTestReplace to handle pointer-type IVs.Andrew Trick2011-11-021-11/+115
| | | | | | | | We've been hitting asserts in this code due to the many supported combintions of modes (iv-rewrite/no-iv-rewrite) and IV types. This second rewrite of the code attempts to deal with these cases systematically. llvm-svn: 143546
* Broaden an assert to handle enable-iv-rewrite=true following r143183.Andrew Trick2011-11-021-0/+38
| | | | | | Narrowest possible fix for PR11279. llvm-svn: 143522
* LFTR should avoid a type mismatch with null pointer IVs.Andrew Trick2011-10-281-0/+59
| | | | | | Fixes rdar://10359193 Indvar LinearFunctionTestReplace assertion llvm-svn: 143183
* It is not safe to sink an alloca into a stacksave/stackrestore pair, so ↵Eli Friedman2011-10-271-9/+34
| | | | | | don't do that. <rdar://problem/10352360> llvm-svn: 143093
* Removed colons from some target datalayout strings in test, since they don't ↵Lang Hames2011-10-1212-12/+12
| | | | | | match the required format. llvm-svn: 141825
* Move replaceCongruentIVs into SCEVExapander and bias toward "expanded"Andrew Trick2011-10-111-0/+1
| | | | | | | | | | | IVs. Indvars previously chose randomly between congruent IVs. Now it will bias the decision toward IVs that SCEVExpander likes to create. This was not done to fix any problem, it's just a welcome side effect of factoring code. llvm-svn: 141633
OpenPOWER on IntegriCloud