summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [PM] Appease mingw32's auto-import DLL build with minimal tweaks.NAKAMURA Takumi2016-02-281-0/+2
| | | | | | char AnalysisBase::ID should be declared as extern and defined in one module. llvm-svn: 262185
* [PM] Introduce CRTP mixin base classes to help define passes andChandler Carruth2016-02-261-2/+0
| | | | | | | | | | | | | | | | | analyses in the new pass manager. These just handle really basic stuff: turning a type name into a string statically that is nice to print in logs, and getting a static unique ID for each analysis. Sadly, the format of passes in anonymous namespaces makes using their names in tests really annoying so I've customized the names of the no-op passes to keep tests sane to read. This is the first of a few simplifying refactorings for the new pass manager that should reduce boilerplate and confusion. llvm-svn: 262004
* [ConstantRange] Rename a method and add more docSanjoy Das2016-02-221-5/+4
| | | | | | | | Rename makeNoWrapRegion to a more obvious makeGuaranteedNoWrapRegion, and add a comment about the counter-intuitive aspects of the function. This is to help prevent cases like PR26628. llvm-svn: 261532
* ScalerEvolution: Only erase temporary values if they actually have been addedTobias Grosser2016-02-211-5/+6
| | | | | | This addresses post-review comments from Sanjoy Das for r261485. llvm-svn: 261486
* ScalarEvolution: Do not keep temporary PHI values in ValueExprMapTobias Grosser2016-02-211-0/+5
| | | | | | | | | | Before this patch simplified SCEV expressions for PHI nodes were only returned the very first time getSCEV() was called, but later calls to getSCEV always returned the non-simplified value, which had "temporarily" been stored in the ValueExprMap, but was never removed and consequently blocked the caching of the simplified PHI expression. llvm-svn: 261485
* [SCEV] Don't spell `SCEV *` variables as `Scev`; NFCSanjoy Das2016-02-201-15/+14
| | | | | | | It reads odd since most other places name a `SCEV *` as `S`. Pure renaming change. llvm-svn: 261393
* [SCEV] Don't use std::make_pair; NFCSanjoy Das2016-02-201-15/+14
| | | | | | `{A, B}` reads cleaner than `std::make_pair(A, B)`. llvm-svn: 261392
* [SCEV][LAA] Re-commit r260085 and r260086, this time with a fix for the memorySilviu Baranga2016-02-081-10/+188
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | sanitizer issue. The PredicatedScalarEvolution's copy constructor wasn't copying the Generation value, and was leaving it un-initialized. Original commit message: [SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided pointer detection Summary: This change adds no wrap SCEV predicates with: - support for runtime checking - support for expression rewriting: (sext ({x,+,y}) -> {sext(x),+,sext(y)} (zext ({x,+,y}) -> {zext(x),+,sext(y)} Note that we are sign extending the increment of the SCEV, even for the zext case. This is needed to cover the fairly common case where y would be a (small) negative integer. In order to do this, this change adds two new flags: nusw and nssw that are applicable to AddRecExprs and permit the transformations above. We also change isStridedPtr in LAA to be able to make use of these predicates. With this feature we should now always be able to work around overflow issues in the dependence analysis. Reviewers: mzolotukhin, sanjoy, anemet Subscribers: mzolotukhin, sanjoy, llvm-commits, rengolin, jmolloy, hfinkel Differential Revision: http://reviews.llvm.org/D15412 llvm-svn: 260112
* Revert r260086 and r260085. They have broken the memorySilviu Baranga2016-02-081-187/+10
| | | | | | sanitizer bots. llvm-svn: 260087
* [SCEV][LAA] Add no wrap SCEV predicates and use use them to improve strided ↵Silviu Baranga2016-02-081-10/+187
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | pointer detection Summary: This change adds no wrap SCEV predicates with: - support for runtime checking - support for expression rewriting: (sext ({x,+,y}) -> {sext(x),+,sext(y)} (zext ({x,+,y}) -> {zext(x),+,sext(y)} Note that we are sign extending the increment of the SCEV, even for the zext case. This is needed to cover the fairly common case where y would be a (small) negative integer. In order to do this, this change adds two new flags: nusw and nssw that are applicable to AddRecExprs and permit the transformations above. We also change isStridedPtr in LAA to be able to make use of these predicates. With this feature we should now always be able to work around overflow issues in the dependence analysis. Reviewers: mzolotukhin, sanjoy, anemet Subscribers: mzolotukhin, sanjoy, llvm-commits, rengolin, jmolloy, hfinkel Differential Revision: http://reviews.llvm.org/D15412 llvm-svn: 260085
* [SCEV] Add boolean accessors for NSW, NUW and NW; NFCSanjoy Das2016-02-041-14/+14
| | | | llvm-svn: 259809
* [SCEV] Try to reuse existing value during SCEV expansionWei Mi2016-02-041-4/+86
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Current SCEV expansion will expand SCEV as a sequence of operations and doesn't utilize the value already existed. This will introduce redundent computation which may not be cleaned up throughly by following optimizations. This patch introduces an ExprValueMap which is a map from SCEV to the set of equal values with the same SCEV. When a SCEV is expanded, the set of values is checked and reused whenever possible before generating a sequence of operations. The original commit triggered regressions in Polly tests. The regressions exposed two problems which have been fixed in current version. 1. Polly will generate a new function based on the old one. To generate an instruction for the new function, it builds SCEV for the old instruction, applies some tranformation on the SCEV generated, then expands the transformed SCEV and insert the expanded value into new function. Because SCEV expansion may reuse value cached in ExprValueMap, the value in old function may be inserted into new function, which is wrong. In SCEVExpander::expand, there is a logic to check the cached value to be used should dominate the insertion point. However, for the above case, the check always passes. That is because the insertion point is in a new function, which is unreachable from the old function. However for unreachable node, DominatorTreeBase::dominates thinks it will be dominated by any other node. The fix is to simply add a check that the cached value to be used in expansion should be in the same function as the insertion point instruction. 2. When the SCEV is of scConstant type, expanding it directly is cheaper than reusing a normal value cached. Although in the cached value set in ExprValueMap, there is a Constant type value, but it is not easy to find it out -- the cached Value set is not sorted according to the potential cost. Existing reuse logic in SCEVExpander::expand simply chooses the first legal element from the cached value set. The fix is that when the SCEV is of scConstant type, don't try the reuse logic. simply expand it. Differential Revision: http://reviews.llvm.org/D12090 llvm-svn: 259736
* Revert r259662, which caused regressions on polly tests.Wei Mi2016-02-031-86/+4
| | | | llvm-svn: 259675
* [SCEV] Try to reuse existing value during SCEV expansionWei Mi2016-02-031-4/+86
| | | | | | | | | | | | | | | | Current SCEV expansion will expand SCEV as a sequence of operations and doesn't utilize the value already existed. This will introduce redundent computation which may not be cleaned up throughly by following optimizations. This patch introduces an ExprValueMap which is a map from SCEV to the set of equal values with the same SCEV. When a SCEV is expanded, the set of values is checked and reused whenever possible before generating a sequence of operations. Differential Revision: http://reviews.llvm.org/D12090 llvm-svn: 259662
* [SCEV] Clean up isKnownPredicateViaConstantRanges; NFCISanjoy Das2016-02-011-63/+20
| | | | | | | | | | | | | | | - ScalarEvolution::isKnownPredicateViaConstantRanges duplicates some logic already present in ConstantRange, use ConstantRange for those bits. - In some cases ScalarEvolution::isKnownPredicateViaConstantRanges returns `false` to mean "definitely false" (e.g. see the `LHSRange.getSignedMin().sge(RHSRange.getSignedMax())` case for `ICmpInst::ICMP_SLT`), but for `isKnownPredicateViaConstantRanges`, `false` actually means "don't know". Get rid of this extra bit of code to avoid confusion. llvm-svn: 259401
* [SCEV] Rename isKnownPredicateWithRanges; NFCSanjoy Das2016-02-011-7/+8
| | | | | | | Make it obvious that it uses constant ranges, and use `Via` instead of `With`, like other similar functions in SCEV. llvm-svn: 259400
* [opaque pointer types] [NFC] Add an explicit type argument to ↵Eduard Burtescu2016-01-221-2/+2
| | | | | | | | | | | | ConstantFoldLoadFromConstPtr. Reviewers: mjacob, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16418 llvm-svn: 258472
* Change ConstantFoldInstOperands to take Instruction instead of opcode and ↵Manuel Jacob2016-01-211-4/+2
| | | | | | | | | | | | | | | | | | | | | type. NFC. Summary: The previous form, taking opcode and type, is moved to an internal helper and the new form, taking an instruction, is a wrapper around this helper. Although this is a slight cleanup on its own, the main motivation is to refactor the constant folding API to ease migration to opaque pointers. This will be follow-up work. Reviewers: eddyb Subscribers: dblaikie, llvm-commits Differential Revision: http://reviews.llvm.org/D16383 llvm-svn: 258391
* [SCEV] Fix PR26207Sanjoy Das2016-01-191-0/+8
| | | | | | | | | | | | | | | | | | | | | | | In some cases, the max backedge taken count can be more conservative than the exact backedge taken count (for instance, because ScalarEvolution::getRange is not control-flow sensitive whereas computeExitLimitFromICmp can be). In these cases, computeExitLimitFromCond (specifically the bit that deals with `and` and `or` instructions) can create an ExitLimit instance with a `SCEVCouldNotCompute` max backedge count expression, but a computable exact backedge count expression. This violates an implicit SCEV assumption: a computable exact BE count should imply a computable max BE count. This change - Makes the above implicit invariant explicit by adding an assert to ExitLimit's constructor - Changes `computeExitLimitFromCond` to be more robust around conservative max backedge counts llvm-svn: 258184
* [SCEV] Use range-for; NFCSanjoy Das2016-01-191-5/+4
| | | | llvm-svn: 258183
* [opaque pointer types] [NFC] GEP: replace get(Pointer)ElementType uses with ↵Eduard Burtescu2016-01-191-4/+4
| | | | | | | | | | | | | | | | | | get{Source,Result}ElementType. Summary: GEPOperator: provide getResultElementType alongside getSourceElementType. This is made possible by adding a result element type field to GetElementPtrConstantExpr, which GetElementPtrInst already has. GEP: replace get(Pointer)ElementType uses with get{Source,Result}ElementType. Reviewers: mjacob, dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D16275 llvm-svn: 258145
* Fix SCEV r256338.JF Bastien2015-12-231-2/+2
| | | | llvm-svn: 256344
* [SCEV] Fix getLoopBackedgeTakenCountsSanjoy Das2015-12-231-17/+16
| | | | | | | | The way `getLoopBackedgeTakenCounts` is written right now isn't correct. It will try to compute and store the BE counts of a Loop #{child loop} number of times (which may be zero). llvm-svn: 256338
* [SCEV] Add and use SCEVConstant::getAPInt; NFCISanjoy Das2015-12-171-70/+62
| | | | llvm-svn: 255921
* Revert r254592 (virtual dtor in SCEVPredicate).Andy Gibbs2015-12-171-2/+0
| | | | | | | | Clang has better diagnostics in this case. It is not necessary therefore to change the destructor to avoid what is effectively an invalid warning in gcc. Instead, better handle the warning flags given to the compiler. llvm-svn: 255905
* Re-commit r255115, with the PredicatedScalarEvolution class moved toSilviu Baranga2015-12-091-0/+43
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ScalarEvolution.h, in order to avoid cyclic dependencies between the Transform and Analysis modules: [LV][LAA] Add a layer over SCEV to apply run-time checked knowledge on SCEV expressions Summary: This change creates a layer over ScalarEvolution for LAA and LV, and centralizes the usage of SCEV predicates. The SCEVPredicatedLayer takes the statically deduced knowledge by ScalarEvolution and applies the knowledge from the SCEV predicates. The end goal is that both LAA and LV should use this interface everywhere. This also solves a problem involving the result of SCEV expression rewritting when the predicate changes. Suppose we have the expression (sext {a,+,b}) and two predicates P1: {a,+,b} has nsw P2: b = 1. Applying P1 and then P2 gives us {a,+,1}, while applying P2 and the P1 gives us sext({a,+,1}) (the AddRec expression was changed by P2 so P1 no longer applies). The SCEVPredicatedLayer maintains the order of transformations by feeding back the results of previous transformations into new transformations, and therefore avoiding this issue. The SCEVPredicatedLayer maintains a cache to remember the results of previous SCEV rewritting results. This also has the benefit of reducing the overall number of expression rewrites. Reviewers: mzolotukhin, anemet Subscribers: jmolloy, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D14296 llvm-svn: 255122
* [SCEV] Use for-each; NFCSanjoy Das2015-12-081-19/+13
| | | | llvm-svn: 255069
* [SCEV] Move some struct declarations inside functions; NFCSanjoy Das2015-12-081-63/+54
| | | | | | | | | Reduces the scope over which the struct is visible, making its usages obvious. I did not move structs in cases where this wasn't a clear win (the struct is too large, or is grouped in some other interesting way). llvm-svn: 255003
* [SCEV] Fix indentation; NFCSanjoy Das2015-12-081-150/+150
| | | | llvm-svn: 255002
* Fix class SCEVPredicate has virtual functions and accessible non-virtual ↵Andy Gibbs2015-12-031-0/+2
| | | | | | | | | | destructor. It is not enough to simply make the destructor virtual since there is a g++ 4.7 issue (see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=53613) that throws the error "looser throw specifier for ... overridding ~SCEVPredicate() noexcept". llvm-svn: 254592
* Introduce a range version of std::find, and use in SCEVSanjoy Das2015-12-011-2/+1
| | | | | | | | | | Reviewers: dblaikie, pcc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15064 llvm-svn: 254391
* Introduce a range version of std::any_of, and use it in SCEVSanjoy Das2015-12-011-4/+3
| | | | | | | | | | Reviewers: dblaikie, pcc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D15063 llvm-svn: 254390
* [SCEV] Use lambda instead of std::bind; NFCSanjoy Das2015-11-291-2/+3
| | | | | | The lambda is more readable. llvm-svn: 254276
* [SCEV] Use range version of all_of; NFCSanjoy Das2015-11-291-13/+10
| | | | llvm-svn: 254275
* [SCEV] Use C++11'ismsSanjoy Das2015-11-221-24/+19
| | | | llvm-svn: 253837
* ScalarEvolution: do not set nuw when creating exprs of form <expr> + <all-ones>.Peter Collingbourne2015-11-201-4/+2
| | | | | | | | | | | The nuw constraint will not be satisfied unless <expr> == 0. This bug has been around since r102234 (in 2010!), but was uncovered by r251052, which introduced more aggressive optimization of nuw scev expressions. Differential Revision: http://reviews.llvm.org/D14850 llvm-svn: 253627
* Move helper classes into anonymous namespaces. NFC.Benjamin Kramer2015-11-161-0/+4
| | | | llvm-svn: 253189
* Re-apply r251050 with a for PR25421Sanjoy Das2015-11-051-1/+58
| | | | | | | | | | | | | | | | | | | | | | | | | The bug: I missed adding break statements in the switch / case. Original commit message: [SCEV] Teach SCEV some axioms about non-wrapping arithmetic Summary: - A s< (A + C)<nsw> if C > 0 - A s<= (A + C)<nsw> if C >= 0 - (A + C)<nsw> s< A if C < 0 - (A + C)<nsw> s<= A if C <= 0 Right now `C` needs to be a constant, but we can later generalize it to be a non-constant if needed. Reviewers: atrick, hfinkel, reames, nlewycky Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13686 llvm-svn: 252236
* Revert r251050 to fix miscompile when running Clang -O1Richard Trieu2015-11-051-56/+1
| | | | | | | See bug for details: https://llvm.org/bugs/show_bug.cgi?id=25421 Some comparisons were incorrectly replaced with a constant value. llvm-svn: 252231
* Refactor: Simplify boolean conditional return statements in llvm/lib/AnalysisAlexander Kornienko2015-11-051-6/+3
| | | | | | | | Patch by Richard Thomson! Differential revision: http://reviews.llvm.org/D9967 llvm-svn: 252209
* [SCEV][LV] Add SCEV Predicates and use them to re-implement stride versioningSilviu Baranga2015-11-021-0/+132
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: SCEV Predicates represent conditions that typically cannot be derived from static analysis, but can be used to reduce SCEV expressions to forms which are usable for different optimizers. ScalarEvolution now has the rewriteUsingPredicate method which can simplify a SCEV expression using a SCEVPredicateSet. The normal workflow of a pass using SCEVPredicates would be to hold a SCEVPredicateSet and every time assumptions need to be made a new SCEV Predicate would be created and added to the set. Each time after calling getSCEV, the user will call the rewriteUsingPredicate method. We add two types of predicates SCEVPredicateSet - implements a set of predicates SCEVEqualPredicate - tests for equality between two SCEV expressions We use the SCEVEqualPredicate to re-implement stride versioning. Every time we version a stride, we will add a SCEVEqualPredicate to the context. Instead of adding specific stride checks, LoopVectorize now adds a more generic SCEV check. We only need to add support for this in the LoopVectorizer since this is the only pass that will do stride versioning. Reviewers: mzolotukhin, anemet, hfinkel, sanjoy Subscribers: sanjoy, hfinkel, rengolin, jmolloy, llvm-commits Differential Revision: http://reviews.llvm.org/D13595 llvm-svn: 251800
* [SCEV] Fix PR25369Sanjoy Das2015-11-021-27/+26
| | | | | | | | | | | | | Have `getConstantEvolutionLoopExitValue` work correctly with multiple entry loops. As far as I can tell, `getConstantEvolutionLoopExitValue` never did the right thing for multiple entry loops; and before r249712 it would silently return an incorrect answer. r249712 changed SCEV to fail an assert on a multiple entry loop, and this change fixes the underlying issue. llvm-svn: 251770
* [SCEV] Don't create SCEV expressions that break LCSSASanjoy Das2015-10-311-0/+5
| | | | | | | | | | | | | Prevent `createNodeFromSelectLikePHI` from creating SCEV expressions that break LCSSA. A better fix for the same issue is to teach SCEVExpander to not break LCSSA by inserting PHI nodes at appropriate places. That's planned for the future. Fixes PR25360. llvm-svn: 251756
* [SCEV] Use auto and range for; NFCSanjoy Das2015-10-311-10/+7
| | | | llvm-svn: 251755
* [SCEV] Generalize the SCEV algorithm for creating expressions for PHI nodesSilviu Baranga2015-10-301-14/+77
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When forming expressions for phi nodes having an incoming value from outside the loop A and a value coming from the previous iteration B we were forming an AddRec if: - B was an AddRec - the value A was equal to the value for B at iteration -1 (or equal to the value of B shifted by one iteration, at iteration 0) In this case, we were computing the expression to be the expression of B, shifted by one iteration. This changes generalizes the logic above by removing the restriction that B needs to be an AddRec. For this we introduce two expression rewriters that allow us to - shift an expression by one iteration - get the value of an expression at iteration 0 This allows us to get SCEV expressions for PHI nodes when these expressions are not AddRecExprs. Reviewers: sanjoy Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D14175 llvm-svn: 251700
* [SCEV] Compute max backedge count for loops with "shift ivs"Sanjoy Das2015-10-281-0/+149
| | | | | | | | | | | | | | This teaches SCEV to compute //max// backedge taken counts for loops like for (int i = k; i != 0; i >>>= 1) whatever(); SCEV yet cannot represent the exact backedge count for these loops, and this patch does not change that. This is really geared towards teaching SCEV that loops like the above are *not* infinite. llvm-svn: 251558
* Put global classes into the appropriate namespace.Benjamin Kramer2015-10-281-0/+2
| | | | | | | Most of the cases belong into an anonymous namespace. No functionality change intended. llvm-svn: 251515
* [SCEV] Refactor out ScalarEvolution::getDataLayout; NFCSanjoy Das2015-10-271-17/+13
| | | | llvm-svn: 251375
* [ScalarEvolution] Throw away dead code.Davide Italiano2015-10-251-17/+0
| | | | llvm-svn: 251256
* [ScalarEvolution] Get rid of NDEBUG in header (correctly this time).Davide Italiano2015-10-251-0/+6
| | | | llvm-svn: 251255
OpenPOWER on IntegriCloud