summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* [SCEV] Bring some methods up to coding style; NFCSanjoy Das2015-10-081-32/+27
| | | | | | | | - Start methods with lower case - Reflow a comment - Delete header comment repeated in .cpp file llvm-svn: 249716
* [SCEV] Remove comment repeated in cpp file; NFCSanjoy Das2015-10-081-5/+0
| | | | llvm-svn: 249713
* [SCEV] Pick backedge values for phi nodes correctlySanjoy Das2015-10-081-10/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively` assumed all phi nodes in the loop header have the same order of incoming values. This is not correct, and this commit changes `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively` to lookup the backedge value of a phi node using the loop's latch block. Unfortunately, there is still some code duplication `getConstantEvolutionLoopExitValue` and `ComputeExitCountExhaustively`. At some point in the future we should extract out a helper class / method that can evolve constant evolution phi nodes across iterations. Fixes 25060. Thanks to Mattias Eriksson for the spot-on analysis! Depends on D13457. Reviewers: atrick, hfinkel Subscribers: materi, llvm-commits Differential Revision: http://reviews.llvm.org/D13458 llvm-svn: 249712
* [SCEV] Check `Pred` first in isKnownPredicateViaSplittingSanjoy Das2015-10-081-2/+2
| | | | | | | Comparing `Pred` with `ICmpInst::ICMP_ULT` is cheaper that memory access -- do that check before loading / storing `ProvingSplitPredicate`. llvm-svn: 249654
* [SCEV] Use `auto *` instead of `auto`; NFCISanjoy Das2015-10-081-7/+7
| | | | | | (As prescribed by the coding style document) llvm-svn: 249653
* Revert "Revert "This patch builds on top of D13378 to handle constant ↵Mehdi Amini2015-10-071-0/+5
| | | | | | | | | | condition."" This reverts commit r249528 and reapply r249431. The fix for the fallout has been commited in r249575. From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 249581
* [SCEV] Use some C++11'ism, NFCSanjoy Das2015-10-071-26/+21
| | | | | | | | | | Summary: Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13457 llvm-svn: 249574
* Revert "This patch builds on top of D13378 to handle constant condition."James Molloy2015-10-071-5/+0
| | | | | | This reverts commit r249431. This caused failures in sqlite3: http://lab.llvm.org:8011/builders/clang-native-arm-lnt/builds/14453 llvm-svn: 249528
* This patch builds on top of D13378 to handle constant condition.Mehdi Amini2015-10-061-0/+5
| | | | | | | | | | | | | | | | | | | | With this patch, clang -O3 optimizes correctly providing > 1000x speedup on this artificial benchmark): for (a=0; a<n; a++) for (b=0; b<n; b++) for (c=0; c<n; c++) for (d=0; d<n; d++) for (e=0; e<n; e++) for (f=0; f<n; f++) x++; From test-suite/SingleSource/Benchmarks/Shootout/nestedloop.c Reviewers: sanjoyd Differential Revision: http://reviews.llvm.org/D13390 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 249431
* Try to appease MSVC, NFCI.Sanjoy Das2015-10-031-90/+91
| | | | | | | | This time by lifting the lambda's in `createNodeFromSelectLikePHI` to the file scope. Looks like there are differences in capture rules between clang and MSVC? llvm-svn: 249222
* Try to appease the MSVC bots, NFCI.Sanjoy Das2015-10-031-1/+1
| | | | llvm-svn: 249219
* Try to appease the MSVC bots, NFC.Sanjoy Das2015-10-021-1/+2
| | | | llvm-svn: 249216
* [SCEV] Recognize simple br-phi patternsSanjoy Das2015-10-021-141/+284
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Teach SCEV to match patterns like ``` br %cond, label %left, label %right left: br label %merge right: br label %merge merge: V = phi [ %x, %left ], [ %y, %right ] ``` as "select %cond, %x, %y". Before this SCEV would match PHI nodes exclusively to add recurrences. This addresses PR25005. Reviewers: joker.eph, joker-eph, atrick Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13378 llvm-svn: 249211
* [SCEV] Refactor out a createNodeForSelectSanjoy Das2015-10-021-88/+100
| | | | | | | | | | | | | Summary: We will shortly re-use this for select-like br-phi pairs. Reviewers: atrick, joker-eph, joker.eph Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13377 llvm-svn: 249177
* [SCEV] Try to prove predicates by splitting themSanjoy Das2015-10-021-3/+33
| | | | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV that to prove `A u< B` it is sufficient to prove each of these facts individually: - B >= 0 - A s< B - A >= 0 In practice, SCEV sometimes finds it easier to prove these facts individually than to prove `A u< B` as one atomic step. Reviewers: reames, atrick, nlewycky, hfinkel Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D13042 llvm-svn: 249168
* [SCEV] Don't crash on pointer comparisonsSanjoy Das2015-09-281-2/+1
| | | | | | | | | | | | `ScalarEvolution::isImpliedCondOperandsViaNoOverflow` tries to cast the operand type of the comparison it is given to an `IntegerType`. This is incorrect because it could actually be simplifying a comparison between two pointers. Switch it to using `getTypeSizeInBits` instead, which does the right thing for both pointers and integers. Fixed PR24956. llvm-svn: 248743
* [SCEV] identical instructions don't compute equal valuesSanjoy Das2015-09-271-1/+8
| | | | | | | | | | | | Before this change `HasSameValue` would return true for distinct `alloca` instructions if they happened to be allocating the same type (`alloca` instructions are not specified as reading memory). This change adds an explicit whitelist of instruction types for which "identical" instructions compute the same value. Fixes PR24952. llvm-svn: 248690
* [SCEV] Reapply 'Teach isLoopBackedgeGuardedByCond to exploit trip counts'Sanjoy Das2015-09-251-0/+16
| | | | | | | | | | | | | | | | | | | | | | Summary: If the trip count of a specific backedge is `N`, then we know that backedge is effectively guarded by the condition `{0,+,1} u< N`. This change teaches SCEV to use this condition to prove things in `isLoopBackedgeGuardedByCond`. Depends on D12948 Depends on D12949 The original checkin, r248608 had to be backed out due to an issue with a ObjCXX unit test. That issue is now fixed, so re-landing. Reviewers: atrick, reames, majnemer, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12950 llvm-svn: 248638
* [SCEV] Reapply 'Exploit A < B => (A+K) < (B+K) when possible'Sanjoy Das2015-09-251-0/+143
| | | | | | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV's `isImpliedCond` two new identities: A u< B u< -C => (A + C) u< (B + C) A s< B s< INT_MIN - C => (A + C) s< (B + C) While these are useful on their own, they're really intended to support D12950. The original checkin, r248606 had to be backed out due to an issue with a ObjCXX unit test. That issue is now fixed, so re-landing. Reviewers: atrick, reames, majnemer, nlewycky, hfinkel Subscribers: aadg, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12948 llvm-svn: 248637
* Revert two SCEV changes that caused test failures in clang.Sanjoy Das2015-09-251-159/+0
| | | | | | r248606: "[SCEV] Exploit A < B => (A+K) < (B+K) when possible" r248608: "[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts." llvm-svn: 248614
* [SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts.Sanjoy Das2015-09-251-0/+16
| | | | | | | | | | | | | | | | | | | Summary: If the trip count of a specific backedge is `N`, then we know that backedge is effectively guarded by the condition `{0,+,1} u< N`. This change teaches SCEV to use this condition to prove things in `isLoopBackedgeGuardedByCond`. Depends on D12948 Depends on D12949 Reviewers: atrick, reames, majnemer, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12950 llvm-svn: 248608
* [SCEV] Extract helper function from isImpliedCond; NFCSanjoy Das2015-09-251-0/+8
| | | | | | | | | | | | | Summary: This new helper routine will be used in a subsequent change. Reviewers: hfinkel Subscribers: hfinkel, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12949 llvm-svn: 248607
OpenPOWER on IntegriCloud