summaryrefslogtreecommitdiffstats
path: root/llvm/test/Analysis/ScalarEvolution
Commit message (Collapse)AuthorAgeFilesLines
...
* SCEV: Make the final add of an inbounds GEP nuw if we know that the index is ↵Benjamin Kramer2013-10-281-2/+38
| | | | | | | | | | | | | | | | | | | | | | | positive. We can't do this for the general case as saying a GEP with a negative index doesn't have unsigned wrap isn't valid for negative indices. %gep = getelementptr inbounds i32* %p, i64 -1 But an inbounds GEP cannot run past the end of address space. So we check for the very common case of a positive index and make GEPs derived from that NUW. Together with Andy's recent non-unit stride work this lets us analyze loops like void foo3(int *a, int *b) { for (; a < b; a++) {} } PR12375, PR12376. Differential Revision: http://llvm-reviews.chandlerc.com/D2033 llvm-svn: 193514
* Fix creating bitcasts between address spaces in SCEV.Matt Arsenault2013-10-211-1/+27
| | | | | | | | The test before wasn't successfully testing this since it was missing the datalayout piece to change the size of the second address space. llvm-svn: 193102
* SCEV should use NSW to get trip count for positive nonunit stride loops.Andrew Trick2013-10-181-18/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | SCEV currently fails to compute loop counts for nonunit stride loops. This comes up frequently. It prevents loop optimization and forces vectorization to insert extra loop checks. For example: void foo(int n, int *x) { for (int i = 0; i < n; i += 3) { x[i] = i; x[i+1] = i+1; x[i+2] = i+2; } } We need to properly handle the case in which limit > INT_MAX-stride. In the above case: n > INT_MAX-3. In this case the loop counter will step beyond the limit and overflow at the same time. However, knowing that signed integer overlow in undefined, we can assume the loop test behavior is arbitrary after overflow. This obeys both C undefined behavior rules, and the more strict LLVM poison value rules. I'm finally fixing this in response to Hal Finkel's persistence. The most probable reason that we never optimized this before is that we were being careful to handle case where the developer expected a side-effect free infinite loop relying on overflow: for (int i = 0; i < n; i += s) { ++j; } return j; If INT_MAX+1 is a multiple of s and n > INT_MAX-s, then we might expect an infinite loop. However there are plenty of ways to achieve this effect without relying on undefined behavior of signed overflow. llvm-svn: 193015
* Teach ScalarEvolution about pointer address spacesMatt Arsenault2013-09-101-0/+68
| | | | llvm-svn: 190425
* FileCheck-ize tests.Bill Wendling2013-08-2224-32/+93
| | | | llvm-svn: 188971
* [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
* FileCheckize some of the testcases.Bill Wendling2013-08-0512-25/+32
| | | | llvm-svn: 187756
* Add newlines at end of test files, no functionality changeStephen Lin2013-07-131-1/+1
| | | | llvm-svn: 186263
* Unit test for SCEV fix r182989, PR16130.Andrew Trick2013-05-311-3/+28
| | | | llvm-svn: 183017
* TBAA: remove !tbaa from testing cases if not used.Manman Ren2013-04-291-10/+6
| | | | | | | This will make it easier to turn on struct-path aware TBAA since the metadata format will change. llvm-svn: 180743
* Fix SCEV forgetMemoizedResults should search and destroy backedge exprs.Andrew Trick2013-03-261-0/+34
| | | | | | | | | | | | | | | Fixes PR15570: SEGV: SCEV back-edge info invalid after dead code removal. Indvars creates a SCEV expression for the loop's back edge taken count, then determines that the comparison is always true and removes it. When loop-unroll asks for the expression, it contains a NULL SCEVUnknkown (as a CallbackVH). forgetMemoizedResults should invalidate the loop back edges expression. llvm-svn: 177986
* 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
* Add a check to the test ↵Dmitri Gribenko2012-12-301-1/+3
| | | | | | | | | Analysis/ScalarEvolution/2010-09-03-RequiredTransitive.ll This test did not test anything at all (except for opt crashing, but that was not the reason why it was added). llvm-svn: 171248
* 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
* Fix broken check lines.Benjamin Kramer2012-08-171-1/+1
| | | | | | | | I really need to find a way to automate this, but I can't come up with a regex that has no false positives while handling tricky cases like custom check prefixes. llvm-svn: 162097
* Stay rational; don't assert trying to take the square root of a negative value.Nick Lewycky2012-08-011-0/+21
| | | | | | If it's negative, the loop is already proven to be infinite. Fixes PR13489! llvm-svn: 161107
* Fix the remaining TCL-style quotes found in the testsuite. This isChandler Carruth2012-07-024-4/+4
| | | | | | | | | | | | | | | | | 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 the uses of '|&' to use '2>&1 |' instead, which works on oldChandler Carruth2012-07-027-7/+7
| | | | | | | | | | versions of Bash. In addition, I can back out the change to the lit built-in shell test runner to support this. This should fix the majority of fallout on Darwin, but I suspect there will be a few straggling issues. llvm-svn: 159544
* Convert all tests using TCL-style quoting to use shell-style quoting.Chandler Carruth2012-07-0226-27/+27
| | | | | | | | | | | | | | | | | | | | | | | | 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
* If the step value is a constant zero, the loop isn't going to terminate. FixesNick Lewycky2012-06-281-0/+27
| | | | | | the assert reported in PR13228! llvm-svn: 159393
* SCEV: Handle a corner case reducing AddRecExpr * AddRecExprAndrew Trick2012-05-301-0/+45
| | | | | | | | | If integer overflow causes one of the terms to reach zero, that can force the entire expression to zero. Fixes PR12929: cast<Ty>() argument of incompatible type llvm-svn: 157673
* SCEV: Add MarkPendingLoopPredicates to avoid recursive isImpliedCond.Andrew Trick2012-05-191-0/+30
| | | | | | | | | | getUDivExpr attempts to simplify by checking for overflow. isLoopEntryGuardedByCond then evaluates the loop predicate which may lead to the same getUDivExpr causing endless recursion. Fixes PR12868: clang 3.2 segmentation fault. llvm-svn: 157092
* Revert "SCEV: When expanding a GEP the final addition to the base pointer ↵Benjamin Kramer2012-04-172-5/+5
| | | | | | | | has NUW but not NSW." This isn't right either, reverting for now. llvm-svn: 154910
* SCEV: When expanding a GEP the final addition to the base pointer has NUW ↵Benjamin Kramer2012-04-072-5/+5
| | | | | | | | but not NSW. Found by inspection. llvm-svn: 154262
* SCEV fix: Handle loop invariant loads.Andrew Trick2012-03-261-0/+47
| | | | | | Fixes PR11882: NULL dereference in ComputeLoadConstantCompareExitLimit. llvm-svn: 153480
* Test scalar evolution directly instead of testing the result ofAndrew Trick2012-03-221-11/+9
| | | | | | canonical indvars. llvm-svn: 153256
* 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
* SCEV fix. In general, Add/Mul expressions should not inherit NSW/NUW.Andrew Trick2011-11-291-1/+19
| | | | | | | This reverts r139450, fixes r139453, and adds much needed comments and a unit test. llvm-svn: 145367
* Filecheckize.Andrew Trick2011-11-291-1/+2
| | | | llvm-svn: 145363
* Don't forget to check FlagNW when determining whether an AddRecExpr will wrapNick Lewycky2011-11-091-0/+35
| | | | | | or not. Patch by Brendon Cahoon! llvm-svn: 144173
* 2>&1 doesn't work here, it just creates an empty file called "&1"Benjamin Kramer2011-10-271-1/+1
| | | | llvm-svn: 143117
* Restore commits 142790 and 142843 - they weren't breaking the buildDuncan Sands2011-10-252-1/+62
| | | | | | | | | | | | | | | | | | | | | | | | | | bots. Original commit messages: - Reapply r142781 with fix. Original message: Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } - Now that we look at all the header PHIs, we need to consider all the header PHIs when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! llvm-svn: 142919
* Speculatively revert commits 142790 and 142843 to see if it fixesDuncan Sands2011-10-252-62/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | the dragonegg and llvm-gcc self-host buildbots. Original commit messages: - Reapply r142781 with fix. Original message: Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } - Now that we look at all the header PHIs, we need to consider all the header PHIs when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! llvm-svn: 142916
* Now that we look at all the header PHIs, we need to consider all the header PHIsNick Lewycky2011-10-241-0/+29
| | | | | | | when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! llvm-svn: 142843
* Reapply r142781 with fix. Original message:Nick Lewycky2011-10-241-1/+33
| | | | | | | | | | | | | | | | | | | Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } llvm-svn: 142790
* Speculatively revert r142781. Bots are showingNick Lewycky2011-10-241-33/+1
| | | | | | | Assertion `i_nocapture < OperandTraits<PHINode>::operands(this) && "getOperand() out of range!"' failed. coming out of indvars. llvm-svn: 142786
* Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in theNick Lewycky2011-10-231-1/+33
| | | | | | | | | | | | | | | | | | loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } llvm-svn: 142781
* Make SCEV's brute force analysis stronger in two ways. Firstly, we should beNick Lewycky2011-10-221-0/+33
| | | | | | | | | | | | | | | | able to constant fold load instructions where the argument is a constant. Second, we should be able to watch multiple PHI nodes through the loop; this patch only supports PHIs in loop headers, more can be done here. With this patch, we now constant evaluate: static const int arr[] = {1, 2, 3, 4, 5}; int test() { int sum = 0; for (int i = 0; i < 5; ++i) sum += arr[i]; return sum; } llvm-svn: 142731
* Missing test case for r141164.Andrew Trick2011-10-051-0/+50
| | | | llvm-svn: 141166
* Reapply r140979 with fix! We never did get a testcase, but careful review of theNick Lewycky2011-10-031-0/+28
| | | | | | logic by David Meyer revealed this bug. llvm-svn: 140992
* Revert r140979 due to reports of bootstrap failure.Nick Lewycky2011-10-031-28/+0
| | | | llvm-svn: 140980
* Add one more case we compute a max trip count.Nick Lewycky2011-10-031-0/+28
| | | | llvm-svn: 140979
* This test only makes sense with -enable-iv-rewrite.Andrew Trick2011-09-131-3/+4
| | | | llvm-svn: 139576
* This transform only handles two-operand AddRec's. Prevent it from trying toNick Lewycky2011-09-061-1/+20
| | | | | | handle anything more complex. Fixes PR10383 again! llvm-svn: 139186
* The logic inside getMulExpr to simplify {a,+,b}*{c,+,d} was wrong, which wasNick Lewycky2011-09-061-3/+34
| | | | | | | visible given a=b=c=d=1, on iteration #1 (the second iteration). Replace it with correct math. Fixes PR10383! llvm-svn: 139133
* Revert r139126 due to selfhost failures reported by buildbots.Nick Lewycky2011-09-061-31/+0
| | | | llvm-svn: 139130
* Teach SCEV to report a max backedge count in one interesting case inNick Lewycky2011-09-051-0/+31
| | | | | | HowFarToZero; the case for a canonical loop. llvm-svn: 139126
* Remove support for parsing the "type i32" syntax for defining a numberedChris Lattner2011-06-192-28/+28
| | | | | | | top level type without a specified number. This syntax isn't documented and blocks forward progress. llvm-svn: 133371
* rip out a ton of intrinsic modernization logic from AutoUpgrade.cpp, which isChris Lattner2011-06-182-50/+49
| | | | | | | | | for pre-2.9 bitcode files. We keep x86 unaligned loads, movnt, crc32, and the target indep prefetch change. As usual, updating the testsuite is a PITA. llvm-svn: 133337
* Remove support for using "foo" as symbols instead of %"foo". This is ancientChris Lattner2011-06-173-3/+1
| | | | | | | syntax and has been long obsolete. As usual, updating the tests is the nasty part of this. llvm-svn: 133242
OpenPOWER on IntegriCloud