summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* [SCEV] Exploit A < B => (A+K) < (B+K) when possibleSanjoy 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. Reviewers: atrick, reames, majnemer, nlewycky, hfinkel Subscribers: aadg, sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12948 llvm-svn: 248606
* [SCEV] Introduce ScalarEvolution::getOne and getZero.Sanjoy Das2015-09-231-21/+20
| | | | | | | | | | | | | | | | | | Summary: It is fairly common to call SE->getConstant(Ty, 0) or SE->getConstant(Ty, 1); this change makes such uses a little bit briefer. I've refactored the call sites I could find easily to use getZero / getOne. Reviewers: hfinkel, majnemer, reames Subscribers: sanjoy, llvm-commits Differential Revision: http://reviews.llvm.org/D12947 llvm-svn: 248362
* [SCEV] Use SaveAndRestore<T> instead of a hand rolled struct; NFCI.Sanjoy Das2015-09-221-13/+2
| | | | | | | `ClearWalkingBEDominatingCondsOnExit` is exactly `SaveAndRestore<bool>`, so use `SaveAndRestore<bool>` instead. llvm-svn: 248227
* [SCEV] Use auto instead of full iterator type; NFCI.Sanjoy Das2015-09-171-2/+1
| | | | llvm-svn: 247919
* ScalarEvolution: added tmp to avoid use-after-dtor in for loop.Naomi Musgrave2015-09-161-2/+5
| | | | | | | | | | | | | | | | | Summary: For loop destroyed current instance before invoking next. Temporary variable added to prevent use-after-dtor when invoke destructor on current instance. Reviewers: eugenis Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D12912 Rename temp var. llvm-svn: 247867
* [SCEV] Consistently Handle Expressions That Cannot Be DividedMatthew Simpson2015-09-101-36/+26
| | | | | | | | | | | | | | | | This patch addresses the issue of SCEV division asserting on some input expressions (e.g., non-affine expressions) and quietly giving up on others. When giving up, we set the quotient to be equal to zero and the remainder to be equal to the numerator. With this patch, we always quietly give up when we cannot perform the division. This patch also adds a test case for DependenceAnalysis that previously caused an assertion. Differential Revision: http://reviews.llvm.org/D11725 llvm-svn: 247314
* [ScalarEvolution] Fix PR24757.Sanjoy Das2015-09-101-2/+42
| | | | | | | | | | | | | | | | | | | Summary: PR24757 was caused by some incorect math in `ScalarEvolution::HowFarToZero` -- the smallest unsigned solution for X in 2^N * A = 2^N * X is not necessarily A. Reviewers: atrick, majnemer, meheff Subscribers: llvm-commits, sanjoy Differential Revision: http://reviews.llvm.org/D12721 llvm-svn: 247242
* ScalarEvolution assume hanging bugfixPiotr Padlewski2015-09-091-13/+13
| | | | | | http://reviews.llvm.org/D12719 llvm-svn: 247184
* [SCEV] Fix GCC 4.8.0 ICE in lambda functionHal Finkel2015-08-191-7/+3
| | | | | | | | | Rewrite some code to not use a lambda function. The non-lambda code is just about as clean as the original, and not any longer. The lambda function causes an internal compiler error in GCC 4.8.0, and it is not worth breaking support for that compiler over this. NFC. llvm-svn: 245466
OpenPOWER on IntegriCloud