summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [SCEV] Introduce add operation inlining limitDaniil Fukalov2017-01-261-0/+8
| | | | | | | | | | | | | Inlining in getAddExpr() can cause abnormal computational time in some cases. New parameter -scev-addops-inline-threshold is intruduced with default value 500. Reviewers: sanjoy Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D28812 llvm-svn: 293176
* [SCEV] Make getUDivExactExpr handle non-nuw multiplies correctly.Eli Friedman2017-01-181-16/+21
| | | | | | | | | | | | | | | | | To avoid regressions, make ScalarEvolution::createSCEV a bit more clever. Also get rid of some useless code in ScalarEvolution::howFarToZero which was hiding this bug. No new testcase because it's impossible to actually expose this bug: we don't have any in-tree users of getUDivExactExpr besides the two functions I just mentioned, and they both dodged the problem. I'll try to add some interesting users in a followup. Differential Revision: https://reviews.llvm.org/D28587 llvm-svn: 292449
* [SCEV] Limit recursion depth of constant evolving.Michael Liao2017-01-131-3/+10
| | | | | | | | | | - For a loop body with VERY complicated exit condition evaluation, constant evolving may run out of stack on platforms such as Windows. Need to limit the recursion depth. Differential Revision: https://reviews.llvm.org/D28629 llvm-svn: 291927
* [SCEV] Simplify SolveLinEquationWithOverflow a bit.Eli Friedman2017-01-121-7/+8
| | | | | | Cleanup in preparation for generalizing it. llvm-svn: 291808
* [SCEV] Make howFarToZero max backedge-taken count check for precondition.Eli Friedman2017-01-111-0/+17
| | | | | | | | | Refines max backedge-taken count if a loop like "for (int i = 0; i != n; ++i) { /* body */ }" is rotated. Differential Revision: https://reviews.llvm.org/D28536 llvm-svn: 291704
* [SCEV] Make howFarToZero use a simpler formula for max backedge-taken count.Eli Friedman2017-01-111-11/+2
| | | | | | | | | This is both easier to understand, and produces a tighter bound in certain cases. Differential Revision: https://reviews.llvm.org/D28393 llvm-svn: 291701
* [PM] Teach SCEV to invalidate itself when its dependencies becomeChandler Carruth2017-01-091-0/+12
| | | | | | | | | | | | | invalid. This fixes use-after-free bugs that will arise with any interesting use of SCEV. I've added a dedicated test that works diligently to trigger these kinds of bugs in the new pass manager and also checks for them explicitly as well as triggering ASan failures when things go squirly. llvm-svn: 291426
* [SCEV] Be less conservative when extending bitwidths for computing ranges.Michael Zolotukhin2016-12-201-7/+6
| | | | | | | | | | | | | | | | | | | | | | | | Summary: In getRangeForAffineAR we compute ranges for affine exprs E = A + B*C, where ranges for A, B, and C are known. To avoid overflow, we need to operate on a bigger bitwidth, and originally we chose 2*x+1 for this (x being the original bitwidth). However, it is safe to use just 2*x: A+B*C <= (2^x - 1) + (2^x - 1)*(2^x - 1) = = 2^x - 1 + 2^2x - 2^x - 2^x + 1 = = 2^2x - 2^x <= 2^2x - 1 Unnecessary extending of bitwidths results in noticeable slowdowns: ranges perform arithmetic operations using APInt, which are much slower when bitwidths are bigger than 64. Reviewers: sanjoy, majnemer, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D27795 llvm-svn: 290211
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-85/+36
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Fix iterator-invalidation issueHal Finkel2016-12-151-1/+3
| | | | | | | | | Inserting a new key into a DenseMap potentially invalidates iterators into that map. Trying to fix an issue from r289755 triggering this assertion: Assertion `isHandleInSync() && "invalid iterator access!"' failed. llvm-svn: 289757
* Remove the AssumptionCacheHal Finkel2016-12-151-16/+11
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Make processing @llvm.assume more efficient by using operand bundlesHal Finkel2016-12-151-20/+72
| | | | | | | | | | | | | | | | | | | | | | | | | | | There was an efficiency problem with how we processed @llvm.assume in ValueTracking (and other places). The AssumptionCache tracked all of the assumptions in a given function. In order to find assumptions relevant to computing known bits, etc. we searched every assumption in the function. For ValueTracking, that means that we did O(#assumes * #values) work in InstCombine and other passes (with a constant factor that can be quite large because we'd repeat this search at every level of recursion of the analysis). Several of us discussed this situation at the last developers' meeting, and this implements the discussed solution: Make the values that an assume might affect operands of the assume itself. To avoid exposing this detail to frontends and passes that need not worry about it, I've used the new operand-bundle feature to add these extra call "operands" in a way that does not affect the intrinsic's signature. I think this solution is relatively clean. InstCombine adds these extra operands based on what ValueTracking, LVI, etc. will need and then those passes need only search the users of the values under consideration. This should fix the computational-complexity problem. At this point, no passes depend on the AssumptionCache, and so I'll remove that as a follow-up change. Differential Revision: https://reviews.llvm.org/D27259 llvm-svn: 289755
* Revert "[SCEVExpand] do not hoist divisions by zero (PR30935)"Reid Kleckner2016-12-121-1/+1
| | | | | | | | | Reverts r289412. It caused an OOB PHI operand access in instcombine when ASan is enabled. Reduction in progress. Also reverts "[SCEVExpander] Add a test case related to r289412" llvm-svn: 289453
* [SCEVExpand] do not hoist divisions by zero (PR30935)Sebastian Pop2016-12-121-1/+1
| | | | | | | | | | | | | | | SCEVExpand computes the insertion point for the components of a SCEV to be code generated. When it comes to generating code for a division, SCEVexpand would not be able to check (at compilation time) all the conditions necessary to avoid a division by zero. The patch disables hoisting of expressions containing divisions by anything other than non-zero constants in order to avoid hoisting these expressions past conditions that should hold before doing the division. The patch passes check-all on x86_64-linux. Differential Revision: https://reviews.llvm.org/D27216 llvm-svn: 289412
* IR: Change PointerType to derive from Type rather than SequentialType.Peter Collingbourne2016-12-021-2/+2
| | | | | | | | | | | | | | | | | | | As proposed on llvm-dev: http://lists.llvm.org/pipermail/llvm-dev/2016-October/106640.html This is for a couple of reasons: - Values of type PointerType are unlike the other SequentialTypes (arrays and vectors) in that they do not hold values of the element type. By moving PointerType we can unify certain aspects of how the other SequentialTypes are handled. - PointerType will have no place in the SequentialType hierarchy once pointee types are removed, so this is a necessary step towards removing pointee types. Differential Revision: https://reviews.llvm.org/D26595 llvm-svn: 288462
* [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
OpenPOWER on IntegriCloud