summaryrefslogtreecommitdiffstats
path: root/llvm/unittests/Analysis/ScalarEvolutionTest.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Sort the #include lines for unittest/...Chandler Carruth2012-12-041-2/+2
| | | | llvm-svn: 169250
* Fix includes of llvm files that used angle brackets.Craig Topper2012-09-151-8/+8
| | | | llvm-svn: 163979
* The product of two chrec's can always be represented as a chrec.Nick Lewycky2011-10-041-7/+159
| | | | llvm-svn: 141066
* land David Blaikie's patch to de-constify Type, with a few tweaks.Chris Lattner2011-07-181-2/+2
| | | | llvm-svn: 135375
* Second attempt at de-constifying LLVM Types in FunctionType::get(),Jay Foad2011-07-121-1/+1
| | | | | | StructType::get() and TargetData::getIntPtrType(). llvm-svn: 134982
* Revert r134893 and r134888 (and related patches in other trees). It was causingBill Wendling2011-07-121-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | an assert on Darwin llvm-gcc builds. Assertion failed: (castIsValid(op, S, Ty) && "Invalid cast!"), function Create, file /Users/buildslave/zorg/buildbot/smooshlab/slave-0.8/build.llvm-gcc-i386-darwin9-RA/llvm.src/lib/VMCore/Instructions.cpp, li\ ne 2067. etc. http://smooshlab.apple.com:8013/builders/llvm-gcc-i386-darwin9-RA/builds/2354 --- Reverse-merging r134893 into '.': U include/llvm/Target/TargetData.h U include/llvm/DerivedTypes.h U tools/bugpoint/ExtractFunction.cpp U unittests/Support/TypeBuilderTest.cpp U lib/Target/ARM/ARMGlobalMerge.cpp U lib/Target/TargetData.cpp U lib/VMCore/Constants.cpp U lib/VMCore/Type.cpp U lib/VMCore/Core.cpp U lib/Transforms/Utils/CodeExtractor.cpp U lib/Transforms/Instrumentation/ProfilingUtils.cpp U lib/Transforms/IPO/DeadArgumentElimination.cpp U lib/CodeGen/SjLjEHPrepare.cpp --- Reverse-merging r134888 into '.': G include/llvm/DerivedTypes.h U include/llvm/Support/TypeBuilder.h U include/llvm/Intrinsics.h U unittests/Analysis/ScalarEvolutionTest.cpp U unittests/ExecutionEngine/JIT/JITTest.cpp U unittests/ExecutionEngine/JIT/JITMemoryManagerTest.cpp U unittests/VMCore/PassManagerTest.cpp G unittests/Support/TypeBuilderTest.cpp U lib/Target/MBlaze/MBlazeIntrinsicInfo.cpp U lib/Target/Blackfin/BlackfinIntrinsicInfo.cpp U lib/VMCore/IRBuilder.cpp G lib/VMCore/Type.cpp U lib/VMCore/Function.cpp G lib/VMCore/Core.cpp U lib/VMCore/Module.cpp U lib/AsmParser/LLParser.cpp U lib/Transforms/Utils/CloneFunction.cpp G lib/Transforms/Utils/CodeExtractor.cpp U lib/Transforms/Utils/InlineFunction.cpp U lib/Transforms/Instrumentation/GCOVProfiling.cpp U lib/Transforms/Scalar/ObjCARC.cpp U lib/Transforms/Scalar/SimplifyLibCalls.cpp U lib/Transforms/Scalar/MemCpyOptimizer.cpp G lib/Transforms/IPO/DeadArgumentElimination.cpp U lib/Transforms/IPO/ArgumentPromotion.cpp U lib/Transforms/InstCombine/InstCombineCompares.cpp U lib/Transforms/InstCombine/InstCombineAndOrXor.cpp U lib/Transforms/InstCombine/InstCombineCalls.cpp U lib/CodeGen/DwarfEHPrepare.cpp U lib/CodeGen/IntrinsicLowering.cpp U lib/Bitcode/Reader/BitcodeReader.cpp llvm-svn: 134949
* De-constify Types in FunctionType::get().Jay Foad2011-07-111-1/+1
| | | | llvm-svn: 134888
* Make SCEVUnknown a CallbackVH, so that it can be notified directlyDan Gohman2010-08-021-0/+82
| | | | | | | | | | | of Value deletions and RAUWs, instead of relying on ScalarEvolution's Scalars map being notified, as that's complicated at best, and insufficient in general. This means SCEVUnknown needs a non-trivial destructor, so introduce a mechanism to allow ScalarEvolution to locate all the SCEVUnknowns. llvm-svn: 110086
* Speculatively revert r109705 since it seems to be causing some build botEric Christopher2010-07-291-78/+0
| | | | | | angst. llvm-svn: 109718
* Factor out some of the code for updating old SCEVUnknown values, andDan Gohman2010-07-291-0/+78
extend it to handle the case where multiple RAUWs affect a single SCEVUnknown. Add a ScalarEvolution unittest to test for this situation. llvm-svn: 109705
OpenPOWER on IntegriCloud