summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Be wary of abnormal exits from loop when exploiting UBSanjoy Das2016-06-091-1/+2
| | | | | | | | | | | | | | We can safely rely on a NoWrap add recurrence causing UB down the road only if we know the loop does not have a exit expressed in a way that is opaque to ScalarEvolution (e.g. by a function call that conditionally calls exit(0)). I believe with this change PR28012 is fixed. Note: I had to change some llvm-lit tests in LoopReroll, since it looks like they were depending on this incorrect behavior. llvm-svn: 272237
* Factor out a loopHasNoAbnormalExits; NFCSanjoy Das2016-06-091-9/+8
| | | | llvm-svn: 272236
* Apply most suggestions of clang-tidy's performance-unnecessary-value-paramBenjamin Kramer2016-06-081-1/+1
| | | | | | | Avoids unnecessary copies. All changes audited & pass tests with asan. No functional change intended. llvm-svn: 272190
* [SCEV] Break out of loop if there is no more work to doSanjoy Das2016-06-081-1/+1
| | | | | | | This is NFC as far as externally visible behavior is concerned, but will keep us from spinning in the worklist traversal algorithm unnecessarily. llvm-svn: 272182
* [SCEV] Track no-abnormal-exits instead of no-throw callsSanjoy Das2016-06-081-10/+10
| | | | | | | | | | | Absence of may-unwind calls is not enough to guarantee that a UB-generating use of an add-rec poison in the loop latch will actually cause UB. We also need to guard against calls that terminate the thread or infinite loop themselves. This partially addresses PR28012. llvm-svn: 272181
* Fix a bug in SCEV's poison value propagationSanjoy Das2016-06-081-12/+13
| | | | | | | | | | | | | The worklist algorithm introduced in rL271151 didn't check to see if the direct users of the post-inc add recurrence propagates poison. This change fixes the problem and makes the code structure more obvious. Note for release managers: correctness wise, this bug wasn't a regression introduced by rL271151 -- the behavior of SCEV around post-inc add recurrences was strictly improved (in terms of correctness) in rL271151. llvm-svn: 272179
* [SCEV] Consolidate comments; NFCSanjoy Das2016-05-291-240/+86
| | | | | | | Consolidate documentation by removing comments from the .cpp file where the comments in the .cpp file were copy-pasted from the header. llvm-svn: 271157
* [SCEV] Rename functions to LLVM style; NFCSanjoy Das2016-05-291-13/+13
| | | | llvm-svn: 271156
* [SCEV] See through op.with.overflow intrinsics (re-apply)Sanjoy Das2016-05-291-5/+49
| | | | | | | | | | | | | | | | | | | Summary: This change teaches SCEV to see reduce `(extractvalue 0 (op.with.overflow X Y))` into `op X Y` (with a no-wrap tag if possible). This was first checked in at r265912 but reverted in r265950 because it exposed some issues around how SCEV handled post-inc add recurrences. Those issues have now been fixed. Reviewers: atrick, regehr Subscribers: mcrosier, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18684 llvm-svn: 271152
* [SCEV] Don't always add no-wrap flags to post-inc add recsSanjoy Das2016-05-291-7/+91
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fixes PR27315. The post-inc version of an add recurrence needs to "follow the same rules" as a normal add or subtract expression. Otherwise we miscompile programs like ``` int main() { int a = 0; unsigned a_u = 0; volatile long last_value; do { a_u += 3; last_value = (long) ((int) a_u); if (will_add_overflow(a, 3)) { // Leave, and don't actually do the increment, so no UB. printf("last_value = %ld\n", last_value); exit(0); } a += 3; } while (a != 46); return 0; } ``` This patch changes SCEV to put no-wrap flags on post-inc add recurrences only when the poison from a potential overflow will go ahead to cause undefined behavior. To avoid regressing performance too much, I've assumed infinite loops without side effects is undefined behavior to prove poison<->UB equivalence in more cases. This isn't ideal, but is not new to LLVM as a whole, and far better than the situation I'm trying to fix. llvm-svn: 271151
* [SCEV] No-wrap flags are not propagated when folding "{S,+,X}+T ==> {S+T,+,X}"Oleg Ranevskyy2016-05-251-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: **Description** This makes `WidenIV::widenIVUse` (IndVarSimplify.cpp) fail to widen narrow IV uses in some cases. The latter affects IndVarSimplify which may not eliminate narrow IV's when there actually exists such a possibility, thereby producing ineffective code. When `WidenIV::widenIVUse` gets a NarrowUse such as `{(-2 + %inc.lcssa),+,1}<nsw><%for.body3>`, it first tries to get a wide recurrence for it via the `getWideRecurrence` call. `getWideRecurrence` returns recurrence like this: `{(sext i32 (-2 + %inc.lcssa) to i64),+,1}<nsw><%for.body3>`. Then a wide use operation is generated by `cloneIVUser`. The generated wide use is evaluated to `{(-2 + (sext i32 %inc.lcssa to i64))<nsw>,+,1}<nsw><%for.body3>`, which is different from the `getWideRecurrence` result. `cloneIVUser` sees the difference and returns nullptr. This patch also fixes the broken LLVM tests by adding missing <nsw> entries introduced by the correction. **Minimal reproducer:** ``` int foo(int a, int b, int c); int baz(); void bar() { int arr[20]; int i = 0; for (i = 0; i < 4; ++i) arr[i] = baz(); for (; i < 20; ++i) arr[i] = foo(arr[i - 4], arr[i - 3], arr[i - 2]); } ``` **Clang command line:** ``` clang++ -mllvm -debug -S -emit-llvm -O3 --target=aarch64-linux-elf test.cpp -o test.ir ``` **Expected result:** The ` -mllvm -debug` log shows that all the IV's for the second `for` loop have been eliminated. Reviewers: sanjoy Subscribers: atrick, asl, aemerson, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D20058 llvm-svn: 270695
* [SCEV] Be more aggressive in proving NUWSanjoy Das2016-05-171-7/+20
| | | | | | | | | | ... for AddRec's in loops for which SCEV is unable to compute a max tripcount. This is the NUW variant of r269211 and fixes PR27691. (Note: PR27691 is not a correct or stability bug, it was created to track a pending task). llvm-svn: 269790
* [scan-build] fix warnings emiited on LLVM Analysis code baseSilviu Baranga2016-05-131-0/+2
| | | | | | | | | | | | Fix "Logic error" warnings of the type "Called C++ object pointer is null" reported by Clang Static Analyzer on the following files: lib/Analysis/ScalarEvolution.cpp, lib/Analysis/LoopInfo.cpp. Patch by Apelete Seketeli! llvm-svn: 269424
* [SCEV] Be more aggressive around proving no-wrapSanjoy Das2016-05-111-4/+17
| | | | | | | | | | | | | | | ... for AddRec's in loops for which SCEV is unable to compute a max tripcount. This is not a problem for "normal" loops[0] that don't have guards or assumes, but helps in cases where we have guards or assumes in the loop that can be used to constrain incoming values over the backedge. This partially fixes PR27691 (we still don't handle the NUW case). [0]: for "normal" loops, in the cases where we'd be able to prove no-wrap via isKnownPredicate, we'd also be able to compute a max tripcount. llvm-svn: 269211
* [SCEV] Use guards to prove predicatesSanjoy Das2016-05-101-3/+44
| | | | | | | | | We can use calls to @llvm.experimental.guard to prove predicates, relying on the fact that in all locations domianted by a call to @llvm.experimental.guard the predicate it is guarding is known to be true. llvm-svn: 268997
* [SCEV] Tweak the output format and content of -analyzeSanjoy Das2016-05-031-3/+18
| | | | | | | | | | | | | In the "LoopDispositions:" section: - Instead of printing out a list, print out a "dictionary" to make it obvious by inspection which disposition is for which loop. This is just a cosmetic change. - Print dispositions for parent _and_ sibling loops. I will use this to write a test case. llvm-svn: 268405
* Fixed MSVC 'not all control paths return a value' warningSimon Pilgrim2016-05-011-0/+1
| | | | llvm-svn: 268198
* [SCEV] When printing via -analysis, dump loop dispositionSanjoy Das2016-05-011-0/+25
| | | | | | | | | | | There are currently some bugs in tree around SCEV caching an incorrect loop disposition. Printing out loop dispositions will let us write whitebox tests as those are fixed. The dispositions are printed as a list in "inside out" order, i.e. innermost loop first. llvm-svn: 268177
* Unify XDEBUG and EXPENSIVE_CHECKS (into the latter), and add an option to ↵Filipe Cabecinhas2016-04-291-1/+1
| | | | | | | | | | | | | | | | | | | the cmake build to enable them. Summary: Historically, we had a switch in the Makefiles for turning on "expensive checks". This has never been ported to the cmake build, but the (dead-ish) code is still around. This will also make it easier to turn it on in buildbots. Reviewers: chandlerc Subscribers: jyknight, mzolotukhin, RKSimon, gberry, llvm-commits Differential Revision: http://reviews.llvm.org/D19723 llvm-svn: 268050
* [SCEV] Extract out a `isSCEVExprNeverPoison` helper; NFCISanjoy Das2016-04-221-29/+41
| | | | | | | | | | | | | | Summary: Also adds a small comment blurb on control flow + no-wrap flags, since that question came up a few days back on llvm-dev. Reviewers: bjarke.roune, broune Subscribers: sanjoy, mcrosier, llvm-commits, mzolotukhin Differential Revision: http://reviews.llvm.org/D19209 llvm-svn: 267110
* [SCEV][LAA] Add tests for SCEV expression transformations performed during LAASilviu Baranga2016-04-141-0/+23
| | | | | | | | | | | | | | | | | | | | Summary: Add a print method to Predicated Scalar Evolution which prints all interesting transformations done by PSE. Loop Access Analysis will now print this as part of the analysis output. We now use this to check the exact expression transformations that were done by PSE in LAA. The additional checking also acts as white-box testing for the getAsAddRec method. Reviewers: anemet, sanjoy Subscribers: sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18792 llvm-svn: 266334
* Add space between words in verify-scev-maps option help messageJeroen Ketema2016-04-121-1/+1
| | | | llvm-svn: 266149
* This reverts commit r265913 and r265912Sanjoy Das2016-04-111-49/+5
| | | | | | | | | See PR27315 r265913: "[IndVars] Eliminate op.with.overflow when possible" r265912: "[SCEV] See through op.with.overflow intrinsics" llvm-svn: 265950
* [SCEV] See through op.with.overflow intrinsicsSanjoy Das2016-04-101-5/+49
| | | | | | | | | | | | | | | Summary: This change teaches SCEV to see reduce `(extractvalue 0 (op.with.overflow X Y))` into `op X Y` (with a no-wrap tag if possible). Reviewers: atrick, regehr Subscribers: mcrosier, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18684 llvm-svn: 265912
* Re-commit [SCEV] Introduce a guarded backedge taken count and use it in LAA ↵Silviu Baranga2016-04-081-86/+229
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | and LV This re-commits r265535 which was reverted in r265541 because it broke the windows bots. The problem was that we had a PointerIntPair which took a pointer to a struct allocated with new. The problem was that new doesn't provide sufficient alignment guarantees. This pattern was already present before r265535 and it just happened to work. To fix this, we now separate the PointerToIntPair from the ExitNotTakenInfo struct into a pointer and a bool. Original commit message: Summary: When the backedge taken codition is computed from an icmp, SCEV can deduce the backedge taken count only if one of the sides of the icmp is an AddRecExpr. However, due to sign/zero extensions, we sometimes end up with something that is not an AddRecExpr. However, we can use SCEV predicates to produce a 'guarded' expression. This change adds a method to SCEV to get this expression, and the SCEV predicate associated with it. In HowManyGreaterThans and HowManyLessThans we will now add a SCEV predicate associated with the guarded backedge taken count when the analyzed SCEV expression is not an AddRecExpr. Note that we only do this as an alternative to returning a 'CouldNotCompute'. We use new feature in Loop Access Analysis and LoopVectorize to analyze and transform more loops. Reviewers: anemet, mzolotukhin, hfinkel, sanjoy Subscribers: flyingforyou, mcrosier, atrick, mssimpso, sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D17201 llvm-svn: 265786
* Don't IPO over functions that can be de-refinedSanjoy Das2016-04-081-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Fixes PR26774. If you're aware of the issue, feel free to skip the "Motivation" section and jump directly to "This patch". Motivation: I define "refinement" as discarding behaviors from a program that the optimizer has license to discard. So transforming: ``` void f(unsigned x) { unsigned t = 5 / x; (void)t; } ``` to ``` void f(unsigned x) { } ``` is refinement, since the behavior went from "if x == 0 then undefined else nothing" to "nothing" (the optimizer has license to discard undefined behavior). Refinement is a fundamental aspect of many mid-level optimizations done by LLVM. For instance, transforming `x == (x + 1)` to `false` also involves refinement since the expression's value went from "if x is `undef` then { `true` or `false` } else { `false` }" to "`false`" (by definition, the optimizer has license to fold `undef` to any non-`undef` value). Unfortunately, refinement implies that the optimizer cannot assume that the implementation of a function it can see has all of the behavior an unoptimized or a differently optimized version of the same function can have. This is a problem for functions with comdat linkage, where a function can be replaced by an unoptimized or a differently optimized version of the same source level function. For instance, FunctionAttrs cannot assume a comdat function is actually `readnone` even if it does not have any loads or stores in it; since there may have been loads and stores in the "original function" that were refined out in the currently visible variant, and at the link step the linker may in fact choose an implementation with a load or a store. As an example, consider a function that does two atomic loads from the same memory location, and writes to memory only if the two values are not equal. The optimizer is allowed to refine this function by first CSE'ing the two loads, and the folding the comparision to always report that the two values are equal. Such a refined variant will look like it is `readonly`. However, the unoptimized version of the function can still write to memory (since the two loads //can// result in different values), and selecting the unoptimized version at link time will retroactively invalidate transforms we may have done under the assumption that the function does not write to memory. Note: this is not just a problem with atomics or with linking differently optimized object files. See PR26774 for more realistic examples that involved neither. This patch: This change introduces a new set of linkage types, predicated as `GlobalValue::mayBeDerefined` that returns true if the linkage type allows a function to be replaced by a differently optimized variant at link time. It then changes a set of IPO passes to bail out if they see such a function. Reviewers: chandlerc, hfinkel, dexonsmith, joker.eph, rnk Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D18634 llvm-svn: 265762
* Revert r265535 until we know how we can fix the bots Silviu Baranga2016-04-061-229/+86
| | | | llvm-svn: 265541
* [SCEV] Introduce a guarded backedge taken count and use it in LAA and LVSilviu Baranga2016-04-061-86/+229
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: When the backedge taken codition is computed from an icmp, SCEV can deduce the backedge taken count only if one of the sides of the icmp is an AddRecExpr. However, due to sign/zero extensions, we sometimes end up with something that is not an AddRecExpr. However, we can use SCEV predicates to produce a 'guarded' expression. This change adds a method to SCEV to get this expression, and the SCEV predicate associated with it. In HowManyGreaterThans and HowManyLessThans we will now add a SCEV predicate associated with the guarded backedge taken count when the analyzed SCEV expression is not an AddRecExpr. Note that we only do this as an alternative to returning a 'CouldNotCompute'. We use new feature in Loop Access Analysis and LoopVectorize to analyze and transform more loops. Reviewers: anemet, mzolotukhin, hfinkel, sanjoy Subscribers: flyingforyou, mcrosier, atrick, mssimpso, sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D17201 llvm-svn: 265535
* [SCEV] Track NoWrap properties using MatchBinaryOp, NFCSanjoy Das2016-03-311-7/+16
| | | | | | | | | This way once we teach MatchBinaryOp to map more things into arithmetic, the non-wrapping add recurrence construction would understand it too. Right now MatchBinaryOp still only understands arithmetic, so this is solely a code-reorganization change. llvm-svn: 264994
* [SCEV] NFC code motion to simplify later changeSanjoy Das2016-03-311-77/+77
| | | | llvm-svn: 264993
* [SCEV] Extract out a MatchBinaryOp; NFCISanjoy Das2016-03-291-222/+284
| | | | | | | | | MatchBinaryOp abstracts out the IR instructions from the operations they represent. While this change is NFC, we will use this factoring later to map things like `(extractvalue 0 (sadd.with.overflow X Y))` to `(add X Y)`. llvm-svn: 264747
* [SCEV] Use Operator::getOpcode instead of manual dispatch; NFCSanjoy Das2016-03-291-8/+3
| | | | llvm-svn: 264746
* [SCEV] Change the SCEV Predicates interfaces for conversion to AddRecExpr to ↵Silviu Baranga2016-03-231-4/+18
| | | | | | | | | | | | | | | | | | | | | | | | return SCEVAddRecExpr* instead of SCEV* Summary: This changes the conversion functions from SCEV * to SCEVAddRecExpr from ScalarEvolution and PredicatedScalarEvolution to return a SCEVAddRecExpr* instead of a SCEV* (which removes the need of most clients to do a dyn_cast right after calling these functions). We also don't add new predicates if the transformation was not successful. This is not entirely a NFC (as it can theoretically remove some predicates from LAA when we have an unknown dependece), but I couldn't find an obvious regression test for it. Reviewers: sanjoy Subscribers: sanjoy, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18368 llvm-svn: 264161
* [PM] Make the AnalysisManager parameter to run methods a reference.Chandler Carruth2016-03-111-7/+7
| | | | | | | | | | | | This was originally a pointer to support pass managers which didn't use AnalysisManagers. However, that doesn't realistically come up much and the complexity of supporting it doesn't really make sense. In fact, *many* parts of the pass manager were just assuming the pointer was never null already. This at least makes it much more explicit and clear. llvm-svn: 263219
* [PM] Implement the final conclusion as to how the analysis IDs shouldChandler Carruth2016-03-111-1/+1
| | | | | | | | | | | | | | | | | | | | work in the face of the limitations of DLLs and templated static variables. This requires passes that use the AnalysisBase mixin provide a static variable themselves. So as to keep their APIs clean, I've made these private and befriended the CRTP base class (which is the common practice). I've added documentation to AnalysisBase for why this is necessary and at what point we can go back to the much simpler system. This is clearly a better pattern than the extern template as it caught *numerous* places where the template magic hadn't been applied and things were "just working" but would eventually have broken mysteriously. llvm-svn: 263216
* [SCEV] Slightly generalize getRangeViaFactoringSanjoy Das2016-03-091-13/+18
| | | | | | | | | Building on the previous change, this generalizes ScalarEvolution::getRangeViaFactoring to work with {Ext(C?A:B)+k0,+,Ext(C?A:B)+k1} where Ext can be a zero extend, sign extend or truncate operation, and k0 and k1 are constants. llvm-svn: 262979
* [SCEV] Slightly generalize getRangeViaFactoringSanjoy Das2016-03-091-23/+51
| | | | | | | | This change generalizes ScalarEvolution::getRangeViaFactoring to work with {Ext(C?A:B),+,Ext(C?A:B)} where Ext can be a zero extend, sign extend or truncate operation. llvm-svn: 262978
* [SCEV] Prove no-overflow via constant rangesSanjoy Das2016-03-031-0/+41
| | | | | | | Exploit ScalarEvolution::getRange's newly acquired smartness (since r262438) by using that to infer nsw and nuw when possible. llvm-svn: 262639
* [SCEV] Be less eager about demoting zexts to sextsSanjoy Das2016-03-031-4/+5
| | | | | | | | | | | | After r262438 we can have provably positive NSW SCEV expressions whose zero extensions cannot be simplified (since r262438 makes SCEV better at computing constant ranges). This means demoting sexts of positive add recurrences eagerly can result in an unsimplified zero extension where we could have had a simplified sign extension. This change fixes the issue by teaching SCEV to demote sext of a positive SCEV expression to a zext only if the sext could not be simplified. llvm-svn: 262638
* [SCEV] Minor naming, braces cleanup; NFCSanjoy Das2016-03-021-5/+4
| | | | llvm-svn: 262459
* Add a comment with a rational for the unusual code structureSanjoy Das2016-03-021-0/+3
| | | | llvm-svn: 262454
* Qualify getRangeForAffineAR with this-> for MSVCSanjoy Das2016-03-021-2/+2
| | | | llvm-svn: 262453
* Perturb code in an attempt to appease MSVCSanjoy Das2016-03-021-9/+9
| | | | | | | | For some reason MSVC seems to think I'm calling getConstant() from a static context. Try to avoid this issue by explicitly specifying 'this->' (though I'm not confident that this will actually work). llvm-svn: 262451
* More code permutation to appease MSVCSanjoy Das2016-03-021-4/+7
| | | | llvm-svn: 262449
* Remove "auto" to appease the MSVC botsSanjoy Das2016-03-021-2/+2
| | | | llvm-svn: 262448
* [SCEV] Make getRange smarter around selectsSanjoy Das2016-03-021-0/+83
| | | | | | | | | | | | Have ScalarEvolution::getRange re-consider cases like "{C?A:B,+,C?P:Q}" by factoring out "C" and computing RangeOf{A,+,P} union RangeOf({B,+,Q}) instead. The latter can be easier to compute precisely in cases like "{C?0:N,+,C?1:-1}" N is the backedge taken count of the loop; since in such cases the latter form simplifies to [0,N+1) union [0,N+1). llvm-svn: 262438
* [SCEV] Extract out a getRangeForAffineAR; NFCSanjoy Das2016-03-021-57/+71
| | | | | | Pure code-motion change. Will be used later in making getRange more clever. llvm-svn: 262437
* [SCEV] Minor cleanup: rename method, C++11'ify; NFCSanjoy Das2016-03-011-4/+3
| | | | llvm-svn: 262374
* [PM] Appease mingw32's auto-import DLL build with minimal tweaks, with fix ↵NAKAMURA Takumi2016-02-281-0/+2
| | | | | | | | for clang. char AnalysisBase::ID should be declared as extern and defined in one module. llvm-svn: 262188
* Revert r262185, "[PM] Appease mingw32's auto-import DLL build with minimal ↵NAKAMURA Takumi2016-02-281-2/+0
| | | | | | | | tweaks." I'll rework soon. llvm-svn: 262186
OpenPOWER on IntegriCloud