summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [SCEV] Simplify BackedgeTakenInfo::getMax; NFCSanjoy Das2016-09-261-7/+7
| | | | llvm-svn: 282372
* [SCEV] Reserve space in SmallVector; NFCSanjoy Das2016-09-251-0/+1
| | | | llvm-svn: 282368
* [SCEV] Have ExitNotTakenInfo keep a pointer to its predicate; NFCSanjoy Das2016-09-251-11/+15
| | | | | | | SCEVUnionPredicate is a "heavyweight" structure, so it is beneficial to store the (optional) data out of line. llvm-svn: 282366
* [SCEV] Simplify tracking ExitNotTakenInfo instances; NFCSanjoy Das2016-09-251-72/+24
| | | | | | | | | | This change simplifies a data structure optimization in the `BackedgeTakenInfo` class for loops with exactly one computable exit. I've sanity checked that this does not regress compile time performance, using sqlite3's amalgamated build. llvm-svn: 282365
* [SCEV] Rename a couple of fields; NFCSanjoy Das2016-09-251-48/+55
| | | | llvm-svn: 282364
* [SCEV] Remove incidental data structure; NFCSanjoy Das2016-09-251-15/+19
| | | | llvm-svn: 282363
* Reapplying r278731 after fixing the problem that caused it to be reverted.David L Kreitzer2016-09-161-15/+100
| | | | | | | | | | Enhance SCEV to compute the trip count for some loops with unknown stride. Patch by Pankaj Chawla Differential Revision: https://reviews.llvm.org/D22377 llvm-svn: 281732
* SCEV: Don't assert about non-SCEV-able value in isSCEVExprNeverPoison() ↵Hans Wennborg2016-08-171-0/+4
| | | | | | | | (PR28932) Differential Revision: https://reviews.llvm.org/D23594 llvm-svn: 278999
* Replace a few more "fall through" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-171-5/+7
| | | | | | Follow up to r278902. I had missed "fall through", with a space. llvm-svn: 278970
* Revert "Enhance SCEV to compute the trip count for some loops with unknown ↵Reid Kleckner2016-08-161-77/+4
| | | | | | | | stride." This reverts commit r278731. It caused http://crbug.com/638314 llvm-svn: 278853
* Enhance SCEV to compute the trip count for some loops with unknown stride.David L Kreitzer2016-08-151-4/+77
| | | | | | | | Patch by Pankaj Chawla Differential Revision: https://reviews.llvm.org/D22377 llvm-svn: 278731
* Use the range variant of remove_if instead of unpacking begin/endDavid Majnemer2016-08-121-4/+3
| | | | | | No functionality change is intended. llvm-svn: 278475
* Recommit "Use ValueOffsetPair to enhance value reuse during SCEV expansion".Wei Mi2016-08-091-20/+62
| | | | | | | | | | | | | | | | | | | | | | | | | The fix for PR28705 will be committed consecutively. In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion. However, const folding and sext/zext distribution can make the reuse still difficult. A simplified case is: suppose we know S1 expands to V1 in ExprValueMap, and S1 = S2 + C_a S3 = S2 + C_b where C_a and C_b are different SCEVConstants. Then we'd like to expand S3 as V1 - C_a + C_b instead of expanding S2 literally. It is helpful when S2 is a complex SCEV expr and S2 has no entry in ExprValueMap, which is usually caused by the fact that S3 is generated from S1 after const folding. In order to do that, we represent ExprValueMap as a mapping from SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a} into the ExprValueMap when we create SCEV for V1. When S3 is expanded, it will first expand S2 to V1 - C_a because of S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b. Differential Revision: https://reviews.llvm.org/D21313 llvm-svn: 278160
* Consistently use FunctionAnalysisManagerSean Silva2016-08-091-2/+2
| | | | | | | | | | | Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278077
* [SCEV] Don't infinitely recurse on unreachable codeSanjoy Das2016-08-051-1/+3
| | | | llvm-svn: 277848
* Revert r276136 "Use ValueOffsetPair to enhance value reuse during SCEV ↵Hans Wennborg2016-07-261-62/+20
| | | | | | | | | | expansion." It causes Clang tests to fail after Windows self-host (PR28705). (Also reverts follow-up r276139.) llvm-svn: 276822
* [SCEV] Make isImpliedCondOperandsViaRanges smarterSanjoy Das2016-07-231-11/+1
| | | | | | | | | | | | This change lets us prove things like "{X,+,10} s< 5000" implies "{X+7,+,10} does not sign overflow" It does this by replacing replacing getConstantDifference by computeConstantDifference (which is smarter) in isImpliedCondOperandsViaRanges. llvm-svn: 276505
* [SCEV] Change the interface of computeConstantDifference; NFCSanjoy Das2016-07-231-24/+17
| | | | | | | This is in preparation of s/getConstantDifference/computeConstantDifference/ in a later change. llvm-svn: 276503
* [SCEV] Extract out a helper function; NFCSanjoy Das2016-07-221-7/+14
| | | | | | | The helper will get smarter in a later change, but right now this is just code reorganization. llvm-svn: 276467
* Use ValueOffsetPair to enhance value reuse during SCEV expansion.Wei Mi2016-07-201-20/+62
| | | | | | | | | | | | | | | | | | | | | | | In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion. However, const folding and sext/zext distribution can make the reuse still difficult. A simplified case is: suppose we know S1 expands to V1 in ExprValueMap, and S1 = S2 + C_a S3 = S2 + C_b where C_a and C_b are different SCEVConstants. Then we'd like to expand S3 as V1 - C_a + C_b instead of expanding S2 literally. It is helpful when S2 is a complex SCEV expr and S2 has no entry in ExprValueMap, which is usually caused by the fact that S3 is generated from S1 after const folding. In order to do that, we represent ExprValueMap as a mapping from SCEV to ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a} into the ExprValueMap when we create SCEV for V1. When S3 is expanded, it will first expand S2 to V1 - C_a because of S2->{V1, C_a} in the map, then expand S3 to V1 - C_a + C_b. Differential Revision: https://reviews.llvm.org/D21313 llvm-svn: 276136
* Teach SCEV to look through returned-argument functionsHal Finkel2016-07-111-0/+7
| | | | | | | | | When building SCEVs, if a function is known to return its argument, then we can build the SCEV using the corresponding argument value. Differential Revision: http://reviews.llvm.org/D9381 llvm-svn: 275037
* Untabify.NAKAMURA Takumi2016-07-041-1/+1
| | | | llvm-svn: 274479
* Use arrays or initializer lists to feed ArrayRefs instead of SmallVector ↵Benjamin Kramer2016-07-021-6/+2
| | | | | | | | where possible. No functionality change intended. llvm-svn: 274431
* [SCEV] Compute max be count from shift operator only if all else failsSanjoy Das2016-06-301-6/+9
| | | | | | | In particular, check to see if we can compute a precise trip count by exhaustively simulating the loop first. llvm-svn: 274199
* Apply clang-tidy's modernize-loop-convert to lib/Analysis.Benjamin Kramer2016-06-261-8/+8
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273816
* [SCEV] Fix incorrect trip count computationSanjoy Das2016-06-181-24/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The way we elide max expressions when computing trip counts is incorrect -- it breaks cases like this: ``` static int wrapping_add(int a, int b) { return (int)((unsigned)a + (unsigned)b); } void test() { volatile int end_buf = 2147483548; // INT_MIN - 100 int end = end_buf; unsigned counter = 0; for (int start = wrapping_add(end, 200); start < end; start++) counter++; print(counter); } ``` Note: the `NoWrap` variable that was being tested has little to do with the values flowing into the max expression; it is a property of the induction variable. test/Transforms/LoopUnroll/nsw-tripcount.ll was added to solely test functionality I'm reverting in this change, so I've deleted the test fully. llvm-svn: 273079
* [SCEV] Use dyn_cast<T> instead of dyn_cast<const T>; NFCSanjoy Das2016-06-151-7/+7
| | | | | | The const is unnecessary. llvm-svn: 272759
* [SCEV] Use cast<> instead of dyn_cast; NFCSanjoy Das2016-06-151-4/+2
| | | | llvm-svn: 272758
* [SCEV] clang-format some sectionsSanjoy Das2016-06-151-12/+10
| | | | llvm-svn: 272753
* [SCEV] Change the interface for SolveQuadraticEquation; NFCSanjoy Das2016-06-151-21/+14
| | | | | | | | Use Optional<T> to denote the absence of a solution, not SCEVCouldNotCompute. This makes the usage of SolveQuadraticEquation somewhat simpler. llvm-svn: 272752
* Minor clean up in loopHasNoAbnormalExits; NFCSanjoy Das2016-06-091-8/+7
| | | | llvm-svn: 272238
* Be wary of abnormal exits from loop when exploiting UBSanjoy Das2016-06-091-1/+2
| | | | | | | | | | | | | | We can safely rely on a NoWrap add recurrence causing UB down the road only if we know the loop does not have a exit expressed in a way that is opaque to ScalarEvolution (e.g. by a function call that conditionally calls exit(0)). I believe with this change PR28012 is fixed. Note: I had to change some llvm-lit tests in LoopReroll, since it looks like they were depending on this incorrect behavior. llvm-svn: 272237
* Factor out a loopHasNoAbnormalExits; NFCSanjoy Das2016-06-091-9/+8
| | | | llvm-svn: 272236
* Apply most suggestions of clang-tidy's performance-unnecessary-value-paramBenjamin Kramer2016-06-081-1/+1
| | | | | | | Avoids unnecessary copies. All changes audited & pass tests with asan. No functional change intended. llvm-svn: 272190
* [SCEV] Break out of loop if there is no more work to doSanjoy Das2016-06-081-1/+1
| | | | | | | This is NFC as far as externally visible behavior is concerned, but will keep us from spinning in the worklist traversal algorithm unnecessarily. llvm-svn: 272182
* [SCEV] Track no-abnormal-exits instead of no-throw callsSanjoy Das2016-06-081-10/+10
| | | | | | | | | | | Absence of may-unwind calls is not enough to guarantee that a UB-generating use of an add-rec poison in the loop latch will actually cause UB. We also need to guard against calls that terminate the thread or infinite loop themselves. This partially addresses PR28012. llvm-svn: 272181
* Fix a bug in SCEV's poison value propagationSanjoy Das2016-06-081-12/+13
| | | | | | | | | | | | | The worklist algorithm introduced in rL271151 didn't check to see if the direct users of the post-inc add recurrence propagates poison. This change fixes the problem and makes the code structure more obvious. Note for release managers: correctness wise, this bug wasn't a regression introduced by rL271151 -- the behavior of SCEV around post-inc add recurrences was strictly improved (in terms of correctness) in rL271151. llvm-svn: 272179
* [SCEV] Consolidate comments; NFCSanjoy Das2016-05-291-240/+86
| | | | | | | Consolidate documentation by removing comments from the .cpp file where the comments in the .cpp file were copy-pasted from the header. llvm-svn: 271157
* [SCEV] Rename functions to LLVM style; NFCSanjoy Das2016-05-291-13/+13
| | | | llvm-svn: 271156
* [SCEV] See through op.with.overflow intrinsics (re-apply)Sanjoy Das2016-05-291-5/+49
| | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV to see reduce `(extractvalue 0 (op.with.overflow X Y))` into `op X Y` (with a no-wrap tag if possible). This was first checked in at r265912 but reverted in r265950 because it exposed some issues around how SCEV handled post-inc add recurrences. Those issues have now been fixed. Reviewers: atrick, regehr Subscribers: mcrosier, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18684 llvm-svn: 271152
* [SCEV] Don't always add no-wrap flags to post-inc add recsSanjoy Das2016-05-291-7/+91
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fixes PR27315. The post-inc version of an add recurrence needs to "follow the same rules" as a normal add or subtract expression. Otherwise we miscompile programs like ``` int main() { int a = 0; unsigned a_u = 0; volatile long last_value; do { a_u += 3; last_value = (long) ((int) a_u); if (will_add_overflow(a, 3)) { // Leave, and don't actually do the increment, so no UB. printf("last_value = %ld\n", last_value); exit(0); } a += 3; } while (a != 46); return 0; } ``` This patch changes SCEV to put no-wrap flags on post-inc add recurrences only when the poison from a potential overflow will go ahead to cause undefined behavior. To avoid regressing performance too much, I've assumed infinite loops without side effects is undefined behavior to prove poison<->UB equivalence in more cases. This isn't ideal, but is not new to LLVM as a whole, and far better than the situation I'm trying to fix. llvm-svn: 271151
* [SCEV] No-wrap flags are not propagated when folding "{S,+,X}+T ==> {S+T,+,X}"Oleg Ranevskyy2016-05-251-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: **Description** This makes `WidenIV::widenIVUse` (IndVarSimplify.cpp) fail to widen narrow IV uses in some cases. The latter affects IndVarSimplify which may not eliminate narrow IV's when there actually exists such a possibility, thereby producing ineffective code. When `WidenIV::widenIVUse` gets a NarrowUse such as `{(-2 + %inc.lcssa),+,1}<nsw><%for.body3>`, it first tries to get a wide recurrence for it via the `getWideRecurrence` call. `getWideRecurrence` returns recurrence like this: `{(sext i32 (-2 + %inc.lcssa) to i64),+,1}<nsw><%for.body3>`. Then a wide use operation is generated by `cloneIVUser`. The generated wide use is evaluated to `{(-2 + (sext i32 %inc.lcssa to i64))<nsw>,+,1}<nsw><%for.body3>`, which is different from the `getWideRecurrence` result. `cloneIVUser` sees the difference and returns nullptr. This patch also fixes the broken LLVM tests by adding missing <nsw> entries introduced by the correction. **Minimal reproducer:** ``` int foo(int a, int b, int c); int baz(); void bar() { int arr[20]; int i = 0; for (i = 0; i < 4; ++i) arr[i] = baz(); for (; i < 20; ++i) arr[i] = foo(arr[i - 4], arr[i - 3], arr[i - 2]); } ``` **Clang command line:** ``` clang++ -mllvm -debug -S -emit-llvm -O3 --target=aarch64-linux-elf test.cpp -o test.ir ``` **Expected result:** The ` -mllvm -debug` log shows that all the IV's for the second `for` loop have been eliminated. Reviewers: sanjoy Subscribers: atrick, asl, aemerson, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D20058 llvm-svn: 270695
* [SCEV] Be more aggressive in proving NUWSanjoy Das2016-05-171-7/+20
| | | | | | | | | | ... for AddRec's in loops for which SCEV is unable to compute a max tripcount. This is the NUW variant of r269211 and fixes PR27691. (Note: PR27691 is not a correct or stability bug, it was created to track a pending task). llvm-svn: 269790
* [scan-build] fix warnings emiited on LLVM Analysis code baseSilviu Baranga2016-05-131-0/+2
| | | | | | | | | | | | Fix "Logic error" warnings of the type "Called C++ object pointer is null" reported by Clang Static Analyzer on the following files: lib/Analysis/ScalarEvolution.cpp, lib/Analysis/LoopInfo.cpp. Patch by Apelete Seketeli! llvm-svn: 269424
* [SCEV] Be more aggressive around proving no-wrapSanjoy Das2016-05-111-4/+17
| | | | | | | | | | | | | | | ... for AddRec's in loops for which SCEV is unable to compute a max tripcount. This is not a problem for "normal" loops[0] that don't have guards or assumes, but helps in cases where we have guards or assumes in the loop that can be used to constrain incoming values over the backedge. This partially fixes PR27691 (we still don't handle the NUW case). [0]: for "normal" loops, in the cases where we'd be able to prove no-wrap via isKnownPredicate, we'd also be able to compute a max tripcount. llvm-svn: 269211
* [SCEV] Use guards to prove predicatesSanjoy Das2016-05-101-3/+44
| | | | | | | | | We can use calls to @llvm.experimental.guard to prove predicates, relying on the fact that in all locations domianted by a call to @llvm.experimental.guard the predicate it is guarding is known to be true. llvm-svn: 268997
* [SCEV] Tweak the output format and content of -analyzeSanjoy Das2016-05-031-3/+18
| | | | | | | | | | | | | In the "LoopDispositions:" section: - Instead of printing out a list, print out a "dictionary" to make it obvious by inspection which disposition is for which loop. This is just a cosmetic change. - Print dispositions for parent _and_ sibling loops. I will use this to write a test case. llvm-svn: 268405
* Fixed MSVC 'not all control paths return a value' warningSimon Pilgrim2016-05-011-0/+1
| | | | llvm-svn: 268198
* [SCEV] When printing via -analysis, dump loop dispositionSanjoy Das2016-05-011-0/+25
| | | | | | | | | | | There are currently some bugs in tree around SCEV caching an incorrect loop disposition. Printing out loop dispositions will let us write whitebox tests as those are fixed. The dispositions are printed as a list in "inside out" order, i.e. innermost loop first. llvm-svn: 268177
* Unify XDEBUG and EXPENSIVE_CHECKS (into the latter), and add an option to ↵Filipe Cabecinhas2016-04-291-1/+1
| | | | | | | | | | | | | | | | | | | the cmake build to enable them. Summary: Historically, we had a switch in the Makefiles for turning on "expensive checks". This has never been ported to the cmake build, but the (dead-ish) code is still around. This will also make it easier to turn it on in buildbots. Reviewers: chandlerc Subscribers: jyknight, mzolotukhin, RKSimon, gberry, llvm-commits Differential Revision: http://reviews.llvm.org/D19723 llvm-svn: 268050
OpenPOWER on IntegriCloud