summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/Analysis/ScalarEvolutionTest.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [SCEV] Do not cache S -> V if S is not equivalent of VSerguei Katkov2018-01-091-0/+102
| | | | | | | | | | | | | | | | SCEV tracks the correspondence of created SCEV to original instruction. However during creation of SCEV it is possible that nuw/nsw/exact flags are lost. As a result during expansion of the SCEV the instruction with nuw/nsw/exact will be used where it was expected and we produce poison incorreclty. Reviewers: sanjoy, mkazantsev, sebpop, jbhateja Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41578 llvm-svn: 322058
* [SCEV] Be careful with nuw/nsw/exact in InsertBinopSerguei Katkov2017-12-271-0/+104
| | | | | | | | | | | | | | | | | | | | | | | | | InsertBinop tries to find an appropriate instruction instead of creating a new instruction. When it checks whether instruction is the same as we need to create it ignores nuw/nsw/exact flags. It leads to invalid behavior when poison instruction can be used when it was not expected. Specifically, for example Expander expands the SCEV built for instruction %a = add i32 %v, 1 It is possible that InsertBinop can find an instruction % b = add nuw nsw i32 %v, 1 and will use it instead of version w/o nuw nsw. It is incorrect. The patch conservatively ignores all instructions with any of poison flags installed. Reviewers: sanjoy, mkazantsev, sebpop, jbhateja Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41576 llvm-svn: 321475
* [SCEV][NFC] Introduce isSafeToExpandAt function to SCEVExpanderMax Kazantsev2017-11-161-0/+71
| | | | | | | | | | | This function checks that: 1) It is safe to expand a SCEV; 2) It is OK to materialize it at the specified location. For example, attempt to expand a loop's AddRec to the same loop's preheader should fail. Differential Revision: https://reviews.llvm.org/D39236 llvm-svn: 318377
* Revert "[SCEV] Maintain and use a loop->loop invalidation dependency"Sanjoy Das2017-10-171-77/+84
| | | | | | | | | This reverts commit r315713. It causes PR34968. I think I know what the problem is, but I don't think I'll have time to fix it this week. llvm-svn: 315962
* [SCEV] Maintain and use a loop->loop invalidation dependencySanjoy Das2017-10-131-84/+77
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This change uses the loop use list added in the previous change to remember the loops that appear in the trip count expressions of other loops; and uses it in forgetLoop. This lets us not scan every loop in the function on a forgetLoop call. With this change we no longer invalidate clear out backedge taken counts on forgetValue. I think this is fine -- the contract is that SCEV users must call forgetLoop(L) if their change to the IR could have changed the trip count of L; solely calling forgetValue on a value feeding into the backedge condition of L is not enough. Moreover, I don't think we can strengthen forgetValue to be sufficient for invalidating trip counts without significantly re-architecting SCEV. For instance, if we have the loop: I = *Ptr; E = I + 10; do { // ... } while (++I != E); then the backedge taken count of the loop is 9, and it has no reference to either I or E, i.e. there is no way in SCEV today to re-discover the dependency of the loop's trip count on E or I. So a SCEV client cannot change E to (say) "I + 20", call forgetValue(E) and expect the loop's trip count to be updated. Reviewers: atrick, sunfish, mkazantsev Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38435 llvm-svn: 315713
* [SCEV] Maintain loop use lists, and use them in forgetLoopSanjoy Das2017-10-131-0/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Currently we do not correctly invalidate memoized results for add recurrences that were created directly (i.e. they were not created from a `Value`). This change fixes this by keeping loop use lists and using the loop use lists to determine which SCEV expressions to invalidate. Here are some statistics on the number of uses of in the use lists of all loops on a clang bootstrap (config: release, no asserts): Count: 731310 Min: 1 Mean: 8.555150 50th %time: 4 95th %tile: 25 99th %tile: 53 Max: 433 Reviewers: atrick, sunfish, mkazantsev Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38434 llvm-svn: 315672
* [SCEV] Properly handle the case of a non-constant start with a zero accum in ↵Daniel Neilson2017-10-111-1/+57
| | | | | | | | | | | | | | | | | | | | ScalarEvolution::createAddRecFromPHIWithCastsImpl Summary: This patch fixes an error in the patch to ScalarEvolution::createAddRecFromPHIWithCastsImpl made in D37265. In that patch we handle the cases where the either the start or accum values can be zero after truncation. But, we assume that the start value must be a constant if the accum is zero. This is clearly an erroneous assumption. This change removes that assumption. Reviewers: sanjoy, dorit, mkazantsev Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D38814 llvm-svn: 315491
* [SCEV] Generalize folding of trunc(x)+n*trunc(y) into folding ↵Daniel Neilson2017-09-221-0/+32
| | | | | | | | | | | | | | | | | | | | | | | | | m*trunc(x)+n*trunc(y) Summary: A SCEV such as: {%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to i32)))}<%loop> can be folded into, simply, {%v2,+,0}. However, the current code in ::getAddExpr() will not try to apply the simplification m*trunc(x)+n*trunc(y) -> trunc(trunc(m)*x+trunc(n)*y) because it only keys off having a non-multiplied trunc as the first term in the simplification. This patch generalizes this code to try to do a more generic fold of these trunc expressions. Reviewers: sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D37888 llvm-svn: 313988
* [LoopInfo] Make LoopBase and Loop destructors non-publicSanjoy Das2017-09-191-141/+0
| | | | | | | | | | | | | | | | | | | Summary: See comment for why I think this is a good idea. This change also: - Removes an SCEV test case. The SCEV test was not testing anything useful (most of it was `#if 0` ed out) and it would need to be updated to deal with a private ~Loop::Loop. - Updates the loop pass manager test case to deal with a private ~Loop::Loop. - Renames markAsRemoved to markAsErased to contrast with removeLoop, via the usual remove vs. erase idiom we already have for instructions and basic blocks. Reviewers: chandlerc Subscribers: mehdi_amini, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D37996 llvm-svn: 313695
* [SCEV] Ensure ScalarEvolution::createAddRecFromPHIWithCastsImpl properly ↵Daniel Neilson2017-09-051-0/+55
| | | | | | | | | | | | | | | | | | | | | | | | | | | | handles out of range truncations of the start and accum values Summary: When constructing the predicate P1 in ScalarEvolution::createAddRecFromPHIWithCastsImpl() it is possible for the PHISCEV from which the predicate is constructed to be a SCEVConstant instead of a SCEVAddRec. If this happens, then the cast<SCEVAddRec>(PHISCEV) in the code will assert. Such a PHISCEV is possible if either the start value or the accumulator value is a constant value that not equal to its truncated value, and if the truncated value is zero. This patch adds tests that demonstrate the cast<> assertion, and fixes this problem by checking whether the PHISCEV is a constant before constructing the P1 predicate; if it is, then P1 is equivalent to one of P2 or P3. Additionally, if we know that the start value or accumulator value are constants then we check whether the P2 and/or P3 predicates are known false at compile time; if either is, then we bail out of constructing the AddRec. Reviewers: sanjoy, mkazantsev, silviu.baranga Reviewed By: mkazantsev Subscribers: mkazantsev, llvm-commits Differential Revision: https://reviews.llvm.org/D37265 llvm-svn: 312568
* Avoid comparison between signed and unsigned in SCEVExitLimitForget testsMax Kazantsev2017-08-041-3/+3
| | | | llvm-svn: 310029
* Fix SCEVExitLimitForget tests to make Sanitizer happyMax Kazantsev2017-08-041-2/+9
| | | | llvm-svn: 310023
* Fix use after free in unit test.Benjamin Kramer2017-08-031-6/+6
| | | | llvm-svn: 309952
* Removed unused variabled from unit testMax Kazantsev2017-08-031-2/+0
| | | | llvm-svn: 309929
* [SCEV] Re-enable "Cache results of computeExitLimit"Max Kazantsev2017-08-031-0/+160
| | | | | | | | | | The patch rL309080 was reverted because it did not clean up the cache on "forgetValue" method call. This patch re-enables this change, adds the missing check and introduces two new unit tests that make sure that the cache is cleaned properly. Differential Revision: https://reviews.llvm.org/D36087 llvm-svn: 309925
* Re-sort #include lines for unittests. This uses a slightly modifiedChandler Carruth2017-06-061-1/+0
| | | | | | | | | | | | | | | clang-format (https://reviews.llvm.org/D33932) to keep primary headers at the top and handle new utility headers like 'gmock' consistently with other utility headers. No other change was made. I did no manual edits, all of this is clang-format. This should allow other changes to have more clear and focused diffs, and is especially motivated by moving some headers into more focused libraries. llvm-svn: 304786
* ScalarEvolution unit test: fix typo that breaks check-allGor Nishanov2017-05-271-1/+1
| | | | llvm-svn: 304063
* [SCEVExpander] Try harder to avoid introducing inttoptrKeno Fischer2017-05-271-5/+83
| | | | | | | | | | | | | | | | Summary: This fixes introduction of an incorrect inttoptr/ptrtoint pair in the included test case which makes use of non-integral pointers. I suspect there are more cases like this left, but this takes care of the one I was seeing at the moment. Reviewers: sanjoy Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D33129 llvm-svn: 304058
* Teach SCEV normalization to de/normalize non-affine add recsSanjoy Das2017-04-251-1/+98
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Before this change, SCEV Normalization would incorrectly normalize non-affine add recurrences. To work around this there was (still is) a check in place to make sure we only tried to normalize affine add recurrences. We recently found a bug in aforementioned check to bail out of normalizing non-affine add recurrences. However, instead of fixing the bailout, I have decided to teach SCEV normalization to work correctly with non-affine add recurrences, making the bailout unnecessary (I'll remove it in a subsequent change). I've also added some unit tests (which would have failed before this change). Reviewers: atrick, sunfish, efriedma Reviewed By: atrick Subscribers: mcrosier, mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D32104 llvm-svn: 301281
* [SCEV] Add a local cache for getZeroExtendExpr and getSignExtendExpr to preventWei Mi2017-04-171-0/+90
| | | | | | | | | | | | | | | | | | the exponential behavior. The patch is to fix PR32043. Functions getZeroExtendExpr and getSignExtendExpr may call themselves recursively more than once. This is potentially a 2^N complexity behavior. The exponential behavior was not commonly exposed before because of existing global cache mechnism like UniqueSCEVs or some early return mechanism when flags FlagNSW or FlagNUW are seen. However, we still have case which can expose the exponential behavior, like the case in PR32043, so we add a local cache in getZeroExtendExpr and getSignExtendExpr. If the input of the functions -- SCEV and type pair have been seen before, we can find the extended expression directly in the local cache. Differential Revision: https://reviews.llvm.org/D30350 llvm-svn: 300494
* Generalize SCEV's unit testing helper a bitSanjoy Das2017-04-141-10/+11
| | | | llvm-svn: 300379
* Add a unit test for SCEV NormalizationSanjoy Das2017-04-141-0/+63
| | | | llvm-svn: 300332
* Allow DataLayout to specify addrspace for allocas.Matt Arsenault2017-04-101-1/+3
| | | | | | | | | | | | | | | | | | | | | | | LLVM makes several assumptions about address space 0. However, alloca is presently constrained to always return this address space. There's no real way to avoid using alloca, so without this there is no way to opt out of these assumptions. The problematic assumptions include: - That the pointer size used for the stack is the same size as the code size pointer, which is also the maximum sized pointer. - That 0 is an invalid, non-dereferencable pointer value. These are problems for AMDGPU because alloca is used to implement the private address space, which uses a 32-bit index as the pointer value. Other pointers are 64-bit and behave more like LLVM's notion of generic address space. By changing the address space used for allocas, we can change our generic pointer type to be LLVM's generic pointer type which does have similar properties. llvm-svn: 299888
* [SCEV] Decrease the recursion threshold for CompareValueComplexitySanjoy Das2017-03-051-1/+37
| | | | | | | | | | Fixes PR32142. r287232 accidentally increased the recursion threshold for CompareValueComplexity from 2 to 32. This change reverses that change by introducing a separate flag for CompareValueComplexity's threshold. llvm-svn: 296992
* [SCEV] Scale back the test added in r294181 as it goes quadratic inChandler Carruth2017-02-061-1/+5
| | | | | | | | | | | | | | | SCEV. This test was immediately the slowest test in 'check-llvm' even in an optimized build and was driving up the total test time by 50% for me. Sanjoy has filed a PR about the quadratic behavior in SCEV but it is also concerning that the test still passes given that r294181 added a threshold at 32 to SCEV. I've followed up on the original patch to figure out how this test should work long-term, but for now I want to get check-llvm to be fast again. llvm-svn: 294241
* [SCEV] limit recursion depth and operands number in getAddExprDaniil Fukalov2017-02-061-0/+28
| | | | | | | | | | | | | | | | | | | | | for a quite big function with source like %add = add nsw i32 %mul, %conv %mul1 = mul nsw i32 %add, %conv %add2 = add nsw i32 %mul1, %add %mul3 = mul nsw i32 %add2, %add ; repeat couple of thousands times that can be produced by loop unroll, getAddExpr() tries to recursively construct SCEV and runs almost infinite time. Added recursion depth restriction (with new parameter to set it) Reviewers: sanjoy Subscribers: hfinkel, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D28158 llvm-svn: 294181
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-1/+4
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-4/+1
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Revert "[SCEVExpand] do not hoist divisions by zero (PR30935)"Reid Kleckner2016-12-121-108/+4
| | | | | | | | | Reverts r289412. It caused an OOB PHI operand access in instcombine when ASan is enabled. Reduction in progress. Also reverts "[SCEVExpander] Add a test case related to r289412" llvm-svn: 289453
* [SCEVExpander] Add a test case related to r289412Sanjoy Das2016-12-121-5/+33
| | | | llvm-svn: 289435
* [SCEVExpand] do not hoist divisions by zero (PR30935)Sebastian Pop2016-12-121-0/+76
| | | | | | | | | | | | | | | SCEVExpand computes the insertion point for the components of a SCEV to be code generated. When it comes to generating code for a division, SCEVexpand would not be able to check (at compilation time) all the conditions necessary to avoid a division by zero. The patch disables hoisting of expressions containing divisions by anything other than non-zero constants in order to avoid hoisting these expressions past conditions that should hold before doing the division. The patch passes check-all on x86_64-linux. Differential Revision: https://reviews.llvm.org/D27216 llvm-svn: 289412
* [SCEV] limit recursion depth of CompareSCEVComplexityDaniil Fukalov2016-11-171-0/+67
| | | | | | | | | | | | | | | Summary: CompareSCEVComplexity goes too deep (50+ on a quite a big unrolled loop) and runs almost infinite time. Added cache of "equal" SCEV pairs to earlier cutoff of further estimation. Recursion depth limit was also introduced as a parameter. Reviewers: sanjoy Subscribers: mzolotukhin, tstellarAMD, llvm-commits Differential Revision: https://reviews.llvm.org/D26389 llvm-svn: 287232
* Revert r286437 r286438, they caused PR30976Nico Weber2016-11-101-89/+0
| | | | llvm-svn: 286483
* [SCEVExpander] Hoist unsigned divisons when safeSanjoy Das2016-11-101-0/+13
| | | | | | That is, when the divisor is a constant non-zero. llvm-svn: 286438
* [SCEVExpander] Don't hoist divisionsSanjoy Das2016-11-101-0/+76
| | | | | | Fixes PR30942. llvm-svn: 286437
* Lift out a helper lambda; NFCSanjoy Das2016-11-101-11/+11
| | | | llvm-svn: 286436
* Make a test case more rigorous; NFCSanjoy Das2016-10-311-21/+8
| | | | llvm-svn: 285536
* [SCEV] Try to order n-ary expressions in CompareValueComplexitySanjoy Das2016-10-311-20/+37
| | | | llvm-svn: 285535
* [SCEV] Reduce boilerplate in unit testsSanjoy Das2016-10-311-32/+27
| | | | llvm-svn: 285534
* [SCEV] In CompareValueComplexity, order global values by their nameSanjoy Das2016-10-301-1/+26
| | | | llvm-svn: 285529
* Clean up test a little bit; NFCSanjoy Das2016-10-301-16/+16
| | | | llvm-svn: 285527
* [SCEV] Make CompareValueComplexity a little bit smarterSanjoy Das2016-10-181-0/+112
| | | | | | | | This helps canonicalization in some cases. Thanks to Pankaj Chawla for the investigation and the test case! llvm-svn: 284501
* Add a C++ unittest to test the fix for PR30213.Wei Mi2016-09-151-0/+65
| | | | | | | | | The test exercises the branch in scev expansion when the value in ValueOffsetPair is a ptr and the offset is not divisible by the elem type size of value. Differential Revision: https://reviews.llvm.org/D24088 llvm-svn: 281575
* Use EXPECT_EQ in the unittests instead of plain assertTobias Grosser2016-02-221-2/+3
| | | | | | This addresses post-review comments from Duncan P. N. Exon Smith to r261485. llvm-svn: 261514
* ScalarEvolution: Do not keep temporary PHI values in ValueExprMapTobias Grosser2016-02-211-0/+26
| | | | | | | | | | 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
* [PM] Port ScalarEvolution to the new pass manager.Chandler Carruth2015-08-171-14/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change makes ScalarEvolution a stand-alone object and just produces one from a pass as needed. Making this work well requires making the object movable, using references instead of overwritten pointers in a number of places, and other refactorings. I've also wired it up to the new pass manager and added a RUN line to a test to exercise it under the new pass manager. This includes basic printing support much like with other analyses. But there is a big and somewhat scary change here. Prior to this patch ScalarEvolution was never *actually* invalidated!!! Re-running the pass just re-wired up the various other analyses and didn't remove any of the existing entries in the SCEV caches or clear out anything at all. This might seem OK as everything in SCEV that can uses ValueHandles to track updates to the values that serve as SCEV keys. However, this still means that as we ran SCEV over each function in the module, we kept accumulating more and more SCEVs into the cache. At the end, we would have a SCEV cache with every value that we ever needed a SCEV for in the entire module!!! Yowzers. The releaseMemory routine would dump all of this, but that isn't realy called during normal runs of the pipeline as far as I can see. To make matters worse, there *is* actually a key that we don't update with value handles -- there is a map keyed off of Loop*s. Because LoopInfo *does* release its memory from run to run, it is entirely possible to run SCEV over one function, then over another function, and then lookup a Loop* from the second function but find an entry inserted for the first function! Ouch. To make matters still worse, there are plenty of updates that *don't* trip a value handle. It seems incredibly unlikely that today GVN or another pass that invalidates SCEV can update values in *just* such a way that a subsequent run of SCEV will incorrectly find lookups in a cache, but it is theoretically possible and would be a nightmare to debug. With this refactoring, I've fixed all this by actually destroying and recreating the ScalarEvolution object from run to run. Technically, this could increase the amount of malloc traffic we see, but then again it is also technically correct. ;] I don't actually think we're suffering from tons of malloc traffic from SCEV because if we were, the fact that we never clear the memory would seem more likely to have come up as an actual problem before now. So, I've made the simple fix here. If in fact there are serious issues with too much allocation and deallocation, I can work on a clever fix that preserves the allocations (while clearing the data) between each run, but I'd prefer to do that kind of optimization with a test case / benchmark that shows why we need such cleverness (and that can test that we actually make it faster). It's possible that this will make some things faster by making the SCEV caches have higher locality (due to being significantly smaller) so until there is a clear benchmark, I think the simple change is best. Differential Revision: http://reviews.llvm.org/D12063 llvm-svn: 245193
* Use 'override/final' instead of 'virtual' for overridden methodsAlexander Kornienko2015-04-111-1/+1
| | | | | | | | | | | | | | The patch is generated using clang-tidy misc-use-override check. This command was used: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py \ -checks='-*,misc-use-override' -header-filter='llvm|clang' \ -j=32 -fix -format http://reviews.llvm.org/D8925 llvm-svn: 234679
* [PM] Remove the old 'PassManager.h' header file at the top level ofChandler Carruth2015-02-131-2/+2
| | | | | | | | | | | | | | | | | | | | LLVM's include tree and the use of using declarations to hide the 'legacy' namespace for the old pass manager. This undoes the primary modules-hostile change I made to keep out-of-tree targets building. I sent an email inquiring about whether this would be reasonable to do at this phase and people seemed fine with it, so making it a reality. This should allow us to start bootstrapping with modules to a certain extent along with making it easier to mix and match headers in general. The updates to any code for users of LLVM are very mechanical. Switch from including "llvm/PassManager.h" to "llvm/IR/LegacyPassManager.h". Qualify the types which now produce compile errors with "legacy::". The most common ones are "PassManager", "PassManagerBase", and "FunctionPassManager". llvm-svn: 229094
* [C++11] Use 'nullptr'.Craig Topper2014-06-081-2/+2
| | | | llvm-svn: 210442
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-4/+4
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
OpenPOWER on IntegriCloud