summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [PM] Change the static object whose address is used to uniquely identifyChandler Carruth2016-11-231-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | analyses to have a common type which is enforced rather than using a char object and a `void *` type when used as an identifier. This has a number of advantages. First, it at least helps some of the confusion raised in Justin Lebar's code review of why `void *` was being used everywhere by having a stronger type that connects to documentation about this. However, perhaps more importantly, it addresses a serious issue where the alignment of these pointer-like identifiers was unknown. This made it hard to use them in pointer-like data structures. We were already dodging this in dangerous ways to create the "all analyses" entry. In a subsequent patch I attempted to use these with TinyPtrVector and things fell apart in a very bad way. And it isn't just a compile time or type system issue. Worse than that, the actual alignment of these pointer-like opaque identifiers wasn't guaranteed to be a useful alignment as they were just characters. This change introduces a type to use as the "key" object whose address forms the opaque identifier. This both forces the objects to have proper alignment, and provides type checking that we get it right everywhere. It also makes the types somewhat less mysterious than `void *`. We could go one step further and introduce a truly opaque pointer-like type to return from the `ID()` static function rather than returning `AnalysisKey *`, but that didn't seem to be a clear win so this is just the initial change to get to a reliably typed and aligned object serving is a key for all the analyses. Thanks to Richard Smith and Justin Lebar for helping pick plausible names and avoid making this refactoring many times. =] And thanks to Sean for the super fast review! While here, I've tried to move away from the "PassID" nomenclature entirely as it wasn't really helping and is overloaded with old pass manager constructs. Now we have IDs for analyses, and key objects whose address can be used as IDs. Where possible and clear I've shortened this to just "ID". In a few places I kept "AnalysisID" to make it clear what was being identified. Differential Revision: https://reviews.llvm.org/D27031 llvm-svn: 287783
* Fix comment typos. NFC.Simon Pilgrim2016-11-201-2/+2
| | | | | | Identified by Pedro Giffuni in PR27636. llvm-svn: 287490
* [SCEV] limit recursion depth of CompareSCEVComplexityDaniil Fukalov2016-11-171-17/+44
| | | | | | | | | | | | | | | Summary: CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and runs almost infinite time. Added cache of "equal" SCEV pairs to earlier cutoff of further estimation. Recursion depth limit was also introduced as a parameter. Reviewers: sanjoy Subscribers: mzolotukhin, tstellarAMD, llvm-commits Differential Revision: https://reviews.llvm.org/D26389 llvm-svn: 287232
* test commit, changed tab to spaces, NFCDaniil Fukalov2016-11-161-1/+1
| | | | llvm-svn: 287116
* Analysis: Simplify the ScalarEvolution::getGEPExpr() interface. NFCI.Peter Collingbourne2016-11-131-8/+7
| | | | | | | | All existing callers were manually extracting information out of an existing GEP instruction and passing it to getGEPExpr(). Simplify the interface by changing it to take a GEPOperator instead. llvm-svn: 286751
* [SCEV] Eta reduce some lambdas; NFCSanjoy Das2016-11-101-3/+2
| | | | llvm-svn: 286429
* [SCEV] Refactor out a useful pattern; NFCSanjoy Das2016-11-091-134/+20
| | | | llvm-svn: 286386
* [SCEV] Try to order n-ary expressions in CompareValueComplexitySanjoy Das2016-10-311-10/+35
| | | | llvm-svn: 285535
* [SCEV] In CompareValueComplexity, order global values by their nameSanjoy Das2016-10-301-0/+15
| | | | llvm-svn: 285529
* [SCEV] Use auto for consistency with an upcoming change; NFCSanjoy Das2016-10-301-4/+4
| | | | llvm-svn: 285528
* [LoopUnroll] Keep the loop test only on the first iteration of max-or-zero loopsJohn Brawn2016-10-211-17/+40
| | | | | | | | | | | | | | | | When we have a loop with a known upper bound on the number of iterations, and furthermore know that either the number of iterations will be either exactly that upper bound or zero, then we can fully unroll up to that upper bound keeping only the first loop test to check for the zero iteration case. Most of the work here is in plumbing this 'max-or-zero' information from the part of scalar evolution where it's detected through to loop unrolling. I've also gone for the safe default of 'false' everywhere but howManyLessThans which could probably be improved. Differential Revision: https://reviews.llvm.org/D25682 llvm-svn: 284818
* [SCEV] Add a threshold to restrict number of mul operands to be inlined into ↵Li Huang2016-10-201-0/+7
| | | | | | | | | | | | | SCEV This is to avoid inlining too many multiplication operands into a SCEV, which could take exponential time in the worst case. Reviewers: Sanjoy Das, Mehdi Amini, Michael Zolotukhin Differential Revision: https://reviews.llvm.org/D25794 llvm-svn: 284784
* [SCEV] Make CompareValueComplexity a little bit smarterSanjoy Das2016-10-181-2/+12
| | | | | | | | This helps canonicalization in some cases. Thanks to Pankaj Chawla for the investigation and the test case! llvm-svn: 284501
* [SCEV] Extract out a helper function; NFCSanjoy Das2016-10-181-45/+46
| | | | llvm-svn: 284500
* [SCEV] More accurate calculation of max backedge count of some less-than loopsJohn Brawn2016-10-181-28/+53
| | | | | | | | | | | | | | | | | | | | | In loops that look something like i = n; do { ... } while(i++ < n+k); where k is a constant, the maximum backedge count is k (in fact the backedge count will be either 0 or k, depending on whether n+k wraps). More generally for LHS < RHS if RHS-(LHS of first comparison) is a constant then the loop will iterate either 0 or that constant number of times. This allows for more loop unrolling with the recent upper bound loop unrolling changes, and I'm working on a patch that will let loop unrolling additionally make use of the loop being executed either 0 or k times (we need to retain the loop comparison only on the first unrolled iteration). Differential Revision: https://reviews.llvm.org/D25607 llvm-svn: 284465
* [SCEV] Consider delinearization pattern with extension with identity factorTobias Grosser2016-10-171-1/+2
| | | | | | | | | | | | Summary: The delinearization algorithm did not consider terms which had an extension without a multiply factor, i.e. a identify factor. We lose cases where size is char type where there will no multiply factor. Reviewers: sanjoy, grosser Subscribers: mzolotukhin, Eugene.Zelenko, llvm-commits, mssimpso, sanjoy, grosser Differential Revision: https://reviews.llvm.org/D16492 llvm-svn: 284378
* Reapply "[LoopUnroll] Use the upper bound of the loop trip count to fullly ↵Haicheng Wu2016-10-121-10/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | unroll a loop" Reappy r284044 after revert in r284051. Krzysztof fixed the error in r284049. The original summary: This patch tries to fully unroll loops having break statement like this for (int i = 0; i < 8; i++) { if (a[i] == value) { found = true; break; } } GCC can fully unroll such loops, but currently LLVM cannot because LLVM only supports loops having exact constant trip counts. The upper bound of the trip count can be obtained from calling ScalarEvolution::getMaxBackedgeTakenCount(). Part of the patch is the refactoring work in SCEV to prevent duplicating code. The feature of using the upper bound is enabled under the same circumstance when runtime unrolling is enabled since both are used to unroll loops without knowing the exact constant trip count. llvm-svn: 284053
* Revert "[LoopUnroll] Use the upper bound of the loop trip count to fullly ↵Haicheng Wu2016-10-121-20/+10
| | | | | | | | unroll a loop" This reverts commit r284044. llvm-svn: 284051
* [LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loopHaicheng Wu2016-10-121-10/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | This patch tries to fully unroll loops having break statement like this for (int i = 0; i < 8; i++) { if (a[i] == value) { found = true; break; } } GCC can fully unroll such loops, but currently LLVM cannot because LLVM only supports loops having exact constant trip counts. The upper bound of the trip count can be obtained from calling ScalarEvolution::getMaxBackedgeTakenCount(). Part of the patch is the refactoring work in SCEV to prevent duplicating code. The feature of using the upper bound is enabled under the same circumstance when runtime unrolling is enabled since both are used to unroll loops without knowing the exact constant trip count. Differential Revision: https://reviews.llvm.org/D24790 llvm-svn: 284044
* [SCEV] Rely on ConstantRange instead of custom logic; NFCISanjoy Das2016-10-021-124/+52
| | | | | | | This was first landed in rL283058 and subsequenlty reverted since a change this depends on (rL283057) was buggy and had to be reverted. llvm-svn: 283079
* Revert r283057 and r283058Sanjoy Das2016-10-021-52/+124
| | | | | | | | | | | They've broken the sanitizer-bootstrap bots. Reverting while I investigate. Original commit messages: r283057: "[ConstantRange] Make getEquivalentICmp smarter" r283058: "[SCEV] Rely on ConstantRange instead of custom logic; NFCI" llvm-svn: 283062
* 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
OpenPOWER on IntegriCloud