aboutsummaryrefslogtreecommitdiffstats
path: root/test/Analysis/ScalarEvolution
Commit message (Collapse)AuthorAgeFilesLines
* Update aosp/master LLVM for rebase to r235153Pirama Arumuga Nainar2015-05-185-4/+59
| | | | | Change-Id: I9bf53792f9fc30570e81a8d80d296c681d005ea7 (cherry picked from commit 0c7f116bb6950ef819323d855415b2f2b0aad987)
* Update aosp/master llvm for rebase to r233350Pirama Arumuga Nainar2015-04-0946-220/+485
| | | | Change-Id: I07d935f8793ee8ec6b7da003f6483046594bca49
* Update aosp/master LLVM for rebase to r230699.Stephen Hines2015-03-2311-2/+489
| | | | Change-Id: I2b5be30509658cb8266be782de0ab24f9099f9b9
* Update aosp/master LLVM for rebase to r222494.Stephen Hines2014-12-024-3/+149
| | | | Change-Id: Ic787f5e0124df789bd26f3f24680f45e678eef2d
* Update LLVM for 3.5 rebase (r209712).Stephen Hines2014-05-291-0/+109
| | | | Change-Id: I149556c940fb7dc92d075273c87ff584f400941f
* Update to LLVM 3.5a.Stephen Hines2014-04-2410-18/+211
| | | | Change-Id: Ifadecab779f128e62e430c2b4f6ddd84953ed617
* Rewrite SCEV's backedge taken count computation.Andrew Trick2013-11-065-10/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@194116 91177308-0d34-0410-b5e6-96231b3b80d8
* 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193514 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193102 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193015 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach ScalarEvolution about pointer address spacesMatt Arsenault2013-09-101-0/+68
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@190425 91177308-0d34-0410-b5e6-96231b3b80d8
* FileCheck-ize tests.Bill Wendling2013-08-2224-32/+93
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188971 91177308-0d34-0410-b5e6-96231b3b80d8
* [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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188513 91177308-0d34-0410-b5e6-96231b3b80d8
* FileCheckize some of the testcases.Bill Wendling2013-08-0512-25/+32
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187756 91177308-0d34-0410-b5e6-96231b3b80d8
* Add newlines at end of test files, no functionality changeStephen Lin2013-07-131-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186263 91177308-0d34-0410-b5e6-96231b3b80d8
* Unit test for SCEV fix r182989, PR16130.Andrew Trick2013-05-311-3/+28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@183017 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@180743 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177986 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171250 91177308-0d34-0410-b5e6-96231b3b80d8
* 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). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171248 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@171246 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162097 91177308-0d34-0410-b5e6-96231b3b80d8
* 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! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161107 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. =/ git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159547 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159544 91177308-0d34-0410-b5e6-96231b3b80d8
* 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159525 91177308-0d34-0410-b5e6-96231b3b80d8
* 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! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159393 91177308-0d34-0410-b5e6-96231b3b80d8
* 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 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157673 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157092 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154910 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@154262 91177308-0d34-0410-b5e6-96231b3b80d8
* SCEV fix: Handle loop invariant loads.Andrew Trick2012-03-261-0/+47
| | | | | | Fixes PR11882: NULL dereference in ComputeLoadConstantCompareExitLimit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153480 91177308-0d34-0410-b5e6-96231b3b80d8
* Test scalar evolution directly instead of testing the result ofAndrew Trick2012-03-221-11/+9
| | | | | | canonical indvars. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153256 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@150664 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145367 91177308-0d34-0410-b5e6-96231b3b80d8
* Filecheckize.Andrew Trick2011-11-291-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145363 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't forget to check FlagNW when determining whether an AddRecExpr will wrapNick Lewycky2011-11-091-0/+35
| | | | | | | or not. Patch by Brendon Cahoon! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144173 91177308-0d34-0410-b5e6-96231b3b80d8
* 2>&1 doesn't work here, it just creates an empty file called "&1"Benjamin Kramer2011-10-271-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143117 91177308-0d34-0410-b5e6-96231b3b80d8
* 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! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142919 91177308-0d34-0410-b5e6-96231b3b80d8
* 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! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142916 91177308-0d34-0410-b5e6-96231b3b80d8
* 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! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142843 91177308-0d34-0410-b5e6-96231b3b80d8
* 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; } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142790 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142786 91177308-0d34-0410-b5e6-96231b3b80d8
* 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; } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142781 91177308-0d34-0410-b5e6-96231b3b80d8
* 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; } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142731 91177308-0d34-0410-b5e6-96231b3b80d8
* Missing test case for r141164.Andrew Trick2011-10-051-0/+50
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141166 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140992 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r140979 due to reports of bootstrap failure.Nick Lewycky2011-10-031-28/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140980 91177308-0d34-0410-b5e6-96231b3b80d8
* Add one more case we compute a max trip count.Nick Lewycky2011-10-031-0/+28
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@140979 91177308-0d34-0410-b5e6-96231b3b80d8
* This test only makes sense with -enable-iv-rewrite.Andrew Trick2011-09-131-3/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@139576 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2024-06-11 10:49:48 +0000