summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* [ScalarEvolution] Get rid of NDEBUG in header.Davide Italiano2015-10-251-7/+0
| | | | llvm-svn: 251249
* Extract out getConstantRangeFromMetadata; NFCSanjoy Das2015-10-241-20/+3
| | | | | | | | | | | | The loop idiom creating a ConstantRange is repeated twice in the codebase, time to give it a name and a home. The loop is also repeated in `rangeMetadataExcludesValue`, but using `getConstantRangeFromMetadata` there would not be an NFC -- the range returned by `getConstantRangeFromMetadata` may contain a value that none of the subranges did. llvm-svn: 251180
* Fix whitespace issues in two places; NFCSanjoy Das2015-10-241-2/+2
| | | | llvm-svn: 251179
* [SCEV] Fix stylistic issue in MatchBinaryAddToConst; NFCISanjoy Das2015-10-231-1/+1
| | | | | | | | | | Instead of checking `(FlagsPresent & ExpectedFlags) != 0`, check `(FlagsPresent & ExpectedFlags) == ExpectedFlags`. Right now they're equivalent since `ExpectedFlags` can only be either `FlagNUW` or `FlagNSW`, but if we ever pass in `ExpectedFlags` as `FlagNUW | FlagNSW` then checking `(FlagsPresent & ExpectedFlags) != 0` would be wrong. llvm-svn: 251142
* [SCEV] Get rid of an unnecessary lambda; NFCSanjoy Das2015-10-231-11/+9
| | | | llvm-svn: 251099
* [SCEV] Fix a latent bug in `getPreStartForExtend`Sanjoy Das2015-10-231-1/+3
| | | | | | | | | | | | | | | | | | I could not come up a way to test this -- I think this bug is latent today, and will not actually result in a miscompile. In `getPreStartForExtend`, SCEV constructs `PreStart` as a sum of all of `SA`'s operands except `Op`. It also uses `SA`'s no-wrap flags, and this is problematic because removing an element from an add expression can make it signed-wrap. E.g. if `SA` was `(127 + 1 + -1)`, then it could safely be `<nsw>` (since `sext(127) + sext(1) + sext(-1)` == `sext(127 + 1 + -1)`), but `(127 + 1)` (== `PreStart` if `Op` is `-1`) is not `<nsw>`. Transferring `<nuw>` from `SA` to `PreStart` is safe, as far as I can tell. llvm-svn: 251097
* [SCEV] Commute zero extends through <nuw> additionsSanjoy Das2015-10-221-0/+12
| | | | llvm-svn: 251052
* [SCEV] Opportunistically interpret unsigned constraints as signedSanjoy Das2015-10-221-0/+7
| | | | | | | | | | | | | | | Summary: An unsigned comparision is equivalent to is corresponding signed version if both the operands being compared are positive. Teach SCEV to use this fact when profitable. Reviewers: atrick, hfinkel, reames, nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13687 llvm-svn: 251051
* [SCEV] Teach SCEV some axioms about non-wrapping arithmeticSanjoy Das2015-10-221-2/+57
| | | | | | | | | | | | | | | | | | | 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: 251050
* [SCEV] Commute sign extends through nsw additionsSanjoy Das2015-10-221-0/+10
| | | | | | | | | | | | Summary: Depends on D13613. Reviewers: atrick, hfinkel, reames, nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13685 llvm-svn: 251049
* [SCEV] Mark AddExprs as nsw or nuw if legalSanjoy Das2015-10-221-5/+30
| | | | | | | | | | | | | | Summary: This uses `ScalarEvolution::getRange` and not potentially control dependent `nsw` and `nuw` bits on the arithmetic instruction. Reviewers: atrick, hfinkel, nlewycky Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D13613 llvm-svn: 251048
* [SCEV] Fix whitespace issues and remove extra braces; NFCSanjoy Das2015-10-181-10/+7
| | | | llvm-svn: 250636
* [SCEV] Use std::all_of and std::any_of; NFCSanjoy Das2015-10-181-16/+11
| | | | llvm-svn: 250635
* [SCEV] Use auto where it helps remove line breaks; NFCSanjoy Das2015-10-181-13/+6
| | | | llvm-svn: 250634
* [SCEV] Use range for loops; NFCSanjoy Das2015-10-181-22/+17
| | | | llvm-svn: 250633
* [SCEV] Use `SCEV::isAllOnesValue` directly; NFC.Sanjoy Das2015-10-131-8/+4
| | | | | | | Instead of `dyn_cast` ing to `SCEVConstant` and checking the contained `ConstantInteger. llvm-svn: 250251
* [SCEV] Put some utilites in the ScalarEvolution classSanjoy Das2015-10-131-18/+22
| | | | | | | | | | | In a later commit, `SplitBinaryAdd` will be used outside `IsConstDiff`, so lift that out. And lift out `IsConstDiff` as `computeConstantDifference` to keep things clean and to avoid playing C++ access specifier games. NFC. llvm-svn: 250143
* SCEV: Allow simple AddRec * Parameter products in delinearizationTobias Grosser2015-10-121-3/+83
| | | | | | | | | This patch also allows the -delinearize pass to delinearize expressions that do not have an outermost SCEVAddRec expression. The SCEV::delinearize infrastructure allowed this since r240952, but the -delinearize pass was not updated yet. llvm-svn: 250018
* [SCEV] Call `StrengthenNoWrapFlags` after `GroupByComplexity`; NFCISanjoy Das2015-10-091-4/+4
| | | | | | | | | The current implementation of `StrengthenNoWrapFlags` is agnostic to the order of `Ops`, so this commit should not change anything semantic. An upcoming change will make `StrengthenNoWrapFlags` sensitive to the order of `Ops`. llvm-svn: 249802
OpenPOWER on IntegriCloud