summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Remove duplicated code; NFCSanjoy Das2016-10-021-2/+2
| | | | | | | ICmpInst::makeConstantRange does exactly the same thing as ConstantRange::makeExactICmpRegion. llvm-svn: 283059
* [SCEV] Rely on ConstantRange instead of custom logic; NFCISanjoy Das2016-10-021-124/+52
| | | | llvm-svn: 283058
* [SCEV] Remove commented out code; NFCSanjoy Das2016-10-021-3/+1
| | | | llvm-svn: 283056
* [SCEV] Use a SmallPtrSet as a temporary union predicate; NFCSanjoy Das2016-09-281-55/+65
| | | | | | | | | | | | | | | | Summary: Instead of creating and destroying SCEVUnionPredicate instances (which internally creates and destroys a DenseMap), use temporary SmallPtrSet instances of remember the set of predicates that will get reified into a SCEVUnionPredicate. Reviewers: silviu.baranga, sbaranga Subscribers: sanjoy, mcrosier, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D25000 llvm-svn: 282606
* [SCEV] Replace a struct with a function; NFCSanjoy Das2016-09-271-153/+139
| | | | | | We can do this now thanks to C++11 lambdas. llvm-svn: 282515
* [SCEV] Use find instead of find_as; NFCSanjoy Das2016-09-271-1/+1
| | | | | | We don't need the extra generality here. llvm-svn: 282514
* [SCEV] Reduce the scope of a struct; NFCSanjoy Das2016-09-271-22/+20
| | | | llvm-svn: 282513
* [SCEV] Remove custom RAII wrapper; NFCSanjoy Das2016-09-271-22/+5
| | | | | | Instead use the pre-existing `scope_exit` class. llvm-svn: 282512
* [SCEV] Make PendingLoopPredicates more frugal; NFCISanjoy Das2016-09-271-3/+4
| | | | | | | | | I don't expect `PendingLoopPredicates` to have very many elements (e.g. when -O3'ing the sqlite3 amalgamation, `PendingLoopPredicates` has at most 3 elements). So now we use a `SmallPtrSet` for it instead of the more heavyweight `DenseSet`. llvm-svn: 282511
* [SCEV] Fix the order of members in the initializer list.Chandler Carruth2016-09-261-1/+1
| | | | | | | Noticed due to the warning on this line. Sanjoy is on a less-than-awesome internet connection, so committing on his behalf. llvm-svn: 282380
* [SCEV] Assign LoopPropertiesCache in the move constructorSanjoy Das2016-09-261-0/+1
| | | | | | | | | | | In a previous change I collapsed two different caches into one. When doing that I noticed that ScalarEvolution's move constructor was not moving those caches. To keep the previous change simple, I've moved that bugfix into this separate change. llvm-svn: 282376
* [SCEV] Combine two predicates into one; NFCSanjoy Das2016-09-261-31/+24
| | | | | | | | | Both `loopHasNoSideEffects` and `loopHasNoAbnormalExits` involve walking the loop and maintaining similar sorts of caches. This commit changes SCEV to compute both the predicates via a single walk, and maintain a single cache instead of two. llvm-svn: 282375
* [SCEV] Make it obvious BackedgeTakenInfo's constructor steals storageSanjoy Das2016-09-261-2/+4
| | | | | | | Specifically, it moves SCEVUnionPredicates from its input into its own storage. Make this obvious at the type level. llvm-svn: 282374
* [SCEV] Further isolate incidental data structure; NFCSanjoy Das2016-09-261-4/+7
| | | | llvm-svn: 282373
* [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
OpenPOWER on IntegriCloud