summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [KnownBits] Add bit counting methods to KnownBits struct and use them where ↵Craig Topper2017-05-121-1/+1
| | | | | | | | | | | | possible This patch adds min/max population count, leading/trailing zero/one bit counting methods. The min methods return answers based on bits that are known without considering unknown bits. The max methods give answers taking into account the largest count that unknown bits could give. Differential Revision: https://reviews.llvm.org/D32931 llvm-svn: 302925
* [SCEV] Reduce possible APInt allocations a bit.Craig Topper2017-05-111-7/+11
| | | | llvm-svn: 302769
* [SCEV] Remove unneeded 'using namespace APIntOps'.Craig Topper2017-05-111-37/+34
| | | | llvm-svn: 302768
* [SCEV] Don't use std::move on both inputs to APInt::operator+ or operator-. ↵Craig Topper2017-05-081-4/+4
| | | | | | It might be confusing to the reader. NFC llvm-svn: 302448
* [SCEV] Use APInt::operator*=(uint64_t) to avoid a temporary APInt for a ↵Craig Topper2017-05-081-2/+1
| | | | | | constant. llvm-svn: 302404
* [SCEV] Have getRangeForAffineARHelper take StartRange by const reference to ↵Craig Topper2017-05-081-1/+1
| | | | | | avoid a copy in many of the cases. llvm-svn: 302398
* [SCEV] Use move semantics in ScalarEvolution::setRangeCraig Topper2017-05-071-3/+3
| | | | | | | | | | | | | | Summary: This makes setRange take ConstantRange by rvalue reference since most callers were passing an unnamed temporary ConstantRange. We can then move that ConstantRange into the DenseMap caches. For the callers that weren't passing a temporary, I've added std::move to to the local variable being passed. Reviewers: sanjoy, mzolotukhin, efriedma Reviewed By: sanjoy Subscribers: takuto.ikuta, llvm-commits Differential Revision: https://reviews.llvm.org/D32943 llvm-svn: 302371
* Remove unnecessary const_castSanjoy Das2017-05-071-7/+4
| | | | llvm-svn: 302368
* Use array_pod_sort instead of std::sortSanjoy Das2017-05-071-1/+1
| | | | llvm-svn: 302367
* [SCEV] Remove extra APInt copies from getRangeForAffineARHelper.Craig Topper2017-05-061-13/+10
| | | | | | This changes one parameter to be a const APInt& since we only read from it. Use std::move on local APInts once they are no longer needed so we can reuse their allocations. Lastly, use operator+=(uint64_t) instead of adding 1 to an APInt twice creating a new APInt each time. llvm-svn: 302335
* [SCEV] Use std::move to avoid some APInt copies.Craig Topper2017-05-061-5/+5
| | | | llvm-svn: 302334
* [SCEV] Use APInt's uint64_t operations instead of creating a temporary APInt ↵Craig Topper2017-05-061-3/+2
| | | | | | to hold 1. llvm-svn: 302333
* [SCEV] Avoid a couple APInt copies by capturing by reference since the ↵Craig Topper2017-05-061-2/+2
| | | | | | method returns a reference. llvm-svn: 302332
* Fix a typo.Michael Zolotukhin2017-05-041-2/+2
| | | | llvm-svn: 302175
* [SCEV] createAddRecFromPHI: Optimize for the most common case.Michael Zolotukhin2017-05-031-2/+58
| | | | | | | | | | | | | | | | | | | Summary: The existing implementation creates a symbolic SCEV expression every time we analyze a phi node and then has to remove it, when the analysis is finished. This is very expensive, and in most of the cases it's also unnecessary. According to the data I collected, ~60-70% of analyzed phi nodes (measured on SPEC) have the following form: PN = phi(Start, OP(Self, Constant)) Handling such cases separately significantly speeds this up. Reviewers: sanjoy, pete Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D32663 llvm-svn: 302096
* Rename isKnownNotFullPoison to programUndefinedIfPoison; NFCSanjoy Das2017-04-301-1/+2
| | | | | | | | | | | | | | | | | Summary: programUndefinedIfPoison makes more sense, given what the function does; and I'm about to add a function with a name similar to isKnownNotFullPoison (so do the rename to avoid confusion). Reviewers: broune, majnemer, bjarke.roune Reviewed By: broune Subscribers: mcrosier, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D30444 llvm-svn: 301776
* [SCEV] Use early exit in createAddRecFromPHI. NFC.Michael Zolotukhin2017-04-281-109/+110
| | | | llvm-svn: 301703
* Kill off the old SimplifyInstruction API by converting remaining users.Daniel Berlin2017-04-281-1/+1
| | | | llvm-svn: 301673
* [ValueTracking] Introduce a KnownBits struct to wrap the two APInts for ↵Craig Topper2017-04-261-10/+12
| | | | | | | | | | | | | | | | computeKnownBits This patch introduces a new KnownBits struct that wraps the two APInt used by computeKnownBits. This allows us to treat them as more of a unit. Initially I've just altered the signatures of computeKnownBits and InstCombine's simplifyDemandedBits to pass a KnownBits reference instead of two separate APInt references. I'll do similar to the SelectionDAG version of computeKnownBits/simplifyDemandedBits as a separate patch. I've added a constructor that allows initializing both APInts to the same bit width with a starting value of 0. This reduces the repeated pattern of initializing both APInts. Once place default constructed the APInts so I added a default constructor for those cases. Going forward I would like to add more methods that will work on the pairs. For example trunc, zext, and sext occur on both APInts together in several places. We should probably add a clear method that can be used to clear both pieces. Maybe a method to check for conflicting information. A method to return (Zero|One) so we don't write it out everywhere. Maybe a method for (Zero|One).isAllOnesValue() to determine if all bits are known. I'm sure there are many other methods we can come up with. Differential Revision: https://reviews.llvm.org/D32376 llvm-svn: 301432
* Revert "[SCEV] Enable SCEV verification by default in EXPENSIVE_CHECKS builds"Sanjoy Das2017-04-241-10/+3
| | | | | | | This reverts commit r301150. It breaks CodeGen/Hexagon/hwloop-wrap2.ll, reverting while I investigate. llvm-svn: 301154
* Fix unused variables / fields warnings in release buildsSanjoy Das2017-04-241-0/+6
| | | | llvm-svn: 301151
* [SCEV] Enable SCEV verification by default in EXPENSIVE_CHECKS buildsSanjoy Das2017-04-241-3/+10
| | | | llvm-svn: 301150
* [SCEV] Fix exponential time complexity by cachingSanjoy Das2017-04-241-19/+63
| | | | llvm-svn: 301149
* [SCEV] Move towards a verifier without false positivesSanjoy Das2017-04-231-68/+59
| | | | | | | | | | | | | | | This change reboots SCEV's current (off by default) verification logic to avoid false failures. Instead of stringifying trip counts, it maps old and new trip counts to the same ScalarEvolution "universe" and asks ScalarEvolution to compute the difference between them. If the difference comes out to be a non-zero constant, then (barring some corner cases) we *know* we messed up. I've not yet enabled this by default since it hits an exponential time issue in SCEV, but once I fix that, I'll flip it on by default in EXPENSIVE_CHECKS builds. llvm-svn: 301146
* Revert r300746 (SCEV analysis for or instructions).Eli Friedman2017-04-201-6/+22
| | | | | | | | There have been multiple reports of this causing problems: a compile-time explosion on the LLVM testsuite, and a stack overflow for an opencl kernel. llvm-svn: 300928
* [APInt] Rename getSignBit to getSignMaskCraig Topper2017-04-201-4/+4
| | | | | | | | getSignBit is a static function that creates an APInt with only the sign bit set. getSignMask seems like a better name to convey its functionality. In fact several places use it and then store in an APInt named SignMask. Differential Revision: https://reviews.llvm.org/D32108 llvm-svn: 300856
* [SCEV] Make SCEV or modeling more aggressive.Eli Friedman2017-04-191-22/+6
| | | | | | | | | | Use haveNoCommonBitsSet to figure out whether an "or" instruction is equivalent to addition. This handles more cases than just checking for a constant on the RHS. Differential Revision: https://reviews.llvm.org/D32239 llvm-svn: 300746
* [APInt] Use lshrInPlace to replace lshr where possibleCraig Topper2017-04-181-1/+1
| | | | | | | | | | This patch uses lshrInPlace to replace code where the object that lshr is called on is being overwritten with the result. This adds an lshrInPlace(const APInt &) version as well. Differential Revision: https://reviews.llvm.org/D32155 llvm-svn: 300566
* [SCEV] Fix another unused variable warning in release builds.Benjamin Kramer2017-04-171-0/+1
| | | | llvm-svn: 300500
* Fix an unused variable error in rL300494.Wei Mi2017-04-171-0/+1
| | | | llvm-svn: 300499
* [SCEV] Add a local cache for getZeroExtendExpr and getSignExtendExpr to preventWei Mi2017-04-171-61/+115
| | | | | | | | | | | | | | | | | | 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
* [APInt] Move isMask and isShiftedMask out of APIntOps and into the APInt ↵Craig Topper2017-04-031-1/+1
| | | | | | | | | | class. Implement them without memory allocation for multiword This moves the isMask and isShiftedMask functions to be class methods. They now use the MathExtras.h function for single word size and leading/trailing zeros/ones or countPopulation for the multiword size. The previous implementation made multiple temorary memory allocations to do the bitwise arithmetic operations to match the MathExtras.h implementation. Differential Revision: https://reviews.llvm.org/D31565 llvm-svn: 299362
* [APInt] Remove the mul/urem/srem/udiv/sdiv functions from the APIntOps ↵Craig Topper2017-04-011-1/+1
| | | | | | namespace. Replace the few usages with calls to the class methods. NFC llvm-svn: 299292
* [ScalarEvolution] Re-enable Predicate implication from operationsMax Kazantsev2017-03-311-16/+171
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The patch rL298481 was reverted due to crash on clang-with-lto-ubuntu build. The reason of the crash was type mismatch between either a or b and RHS in the following situation: LHS = sext(a +nsw b) > RHS. This is quite rare, but still possible situation. Normally we need to cast all {a, b, RHS} to their widest type. But we try to avoid creation of new SCEV that are not constants to avoid initiating recursive analysis that can take a lot of time and/or cache a bad value for iterations number. To deal with this, in this patch we reject this case and will not try to analyze it if the type of sum doesn't match with the type of RHS. In this situation we don't need to create any non-constant SCEVs. This patch also adds an assertion to the method IsProvedViaContext so that we could fail on it and not go further into range analysis etc (because in some situations these analyzes succeed even when the passed arguments have wrong types, what should not normally happen). The patch also contains a fix for a problem with too narrow scope of the analysis caused by wrong usage of predicates in recursive invocations. The regression test on the said failure: test/Analysis/ScalarEvolution/implied-via-addition.ll Reviewers: reames, apilipenko, anna, sanjoy Reviewed By: sanjoy Subscribers: mzolotukhin, mehdi_amini, llvm-commits Differential Revision: https://reviews.llvm.org/D31238 llvm-svn: 299205
* Spelling mistakes in comments. NFCI.Simon Pilgrim2017-03-311-1/+1
| | | | llvm-svn: 299197
* Revert "[ScalarEvolution] Re-enable Predicate implication from operations"Max Kazantsev2017-03-241-159/+16
| | | | | | | | This reverts commit rL298690 Causes failures on clang. llvm-svn: 298693
* [ScalarEvolution] Re-enable Predicate implication from operationsMax Kazantsev2017-03-241-16/+159
| | | | | | | | | | | | | | | | | | | | | | | | The patch rL298481 was reverted due to crash on clang-with-lto-ubuntu build. The reason of the crash was type mismatch between either a or b and RHS in the following situation: LHS = sext(a +nsw b) > RHS. This is quite rare, but still possible situation. Normally we need to cast all {a, b, RHS} to their widest type. But we try to avoid creation of new SCEV that are not constants to avoid initiating recursive analysis that can take a lot of time and/or cache a bad value for iterations number. To deal with this, in this patch we reject this case and will not try to analyze it if the type of sum doesn't match with the type of RHS. In this situation we don't need to create any non-constant SCEVs. This patch also adds an assertion to the method IsProvedViaContext so that we could fail on it and not go further into range analysis etc (because in some situations these analyzes succeed even when the passed arguments have wrong types, what should not normally happen). The patch also contains a fix for a problem with too narrow scope of the analysis caused by wrong usage of predicates in recursive invocations. The regression test on the said failure: test/Analysis/ScalarEvolution/implied-via-addition.ll llvm-svn: 298690
* Model ashr(shl(x, n), m) as mul(x, 2^(n-m)) when n > mZhaoshi Zheng2017-03-231-19/+46
| | | | | | | | | | | | | Given below case: %y = shl %x, n %z = ashr %y, m when n = m, SCEV models it as sext(trunc(x)). This patch tries to handle the case where n > m by using sext(mul(trunc(x), 2^(n-m)))) as the SCEV expression. llvm-svn: 298631
* revert test commit r298629Zhaoshi Zheng2017-03-231-4/+0
| | | | llvm-svn: 298630
* test commitZhaoshi Zheng2017-03-231-0/+4
| | | | llvm-svn: 298629
* Revert "[ScalarEvolution] Predicate implication from operations"Max Kazantsev2017-03-221-147/+16
| | | | | | | | This reverts commit rL298481 Fails clang-with-lto-ubuntu build. llvm-svn: 298489
* [ScalarEvolution] Predicate implication from operationsMax Kazantsev2017-03-221-16/+147
| | | | | | | | | | | | | | | | | | | | | | | This patch allows SCEV predicate analysis to prove implication of some expression predicates from context predicates related to arguments of those expressions. It introduces three new rules: For addition: (A >X && B >= 0) || (B >= 0 && A > X) ===> (A + B) > X. For division: (A > X) && (0 < B <= X + 1) ===> (A / B > 0). (A > X) && (-B <= X < 0) ===> (A / B >= 0). Using these rules, SCEV is able to prove facts like "if X > 1 then X / 2 > 0". They can also be combined with the same context, to prove more complex expressions like "if X > 1 then X/2 + 1 > 1". Diffirential Revision: https://reviews.llvm.org/D30887 Reviewed by: sanjoy llvm-svn: 298481
* [SCEV] Fix trip multiple calculationEli Friedman2017-03-201-10/+16
| | | | | | | | | | | | | | | | | | | | If loop bound containing calculations like min(a,b), the Scalar Evolution API getSmallConstantTripMultiple returns 4294967295 "-1" as the trip multiple. The problem is that, SCEV use -1 * umax to represent umin. The multiple constant -1 was returned, and the logic of guarding against huge trip counts was skipped. Because -1 has 32 active bits. The fix attempt to factor more general cases. First try to get the greatest power of two divisor of trip count expression. In case overflow happens, the trip count expression is still divisible by the greatest power of two divisor returned. Returns 1 if not divisible by 2. Patch by Huihui Zhang <huihuiz@codeaurora.org> Differential Revision: https://reviews.llvm.org/D30840 llvm-svn: 298301
* [SCEV] Use const Loop *L instead of Loop *L. NFCEli Friedman2017-03-171-6/+7
| | | | | | | | Use const pointer in the trip count and trip multiple calculations. Patch by Huihui Zhang <huihuiz@codeaurora.org> llvm-svn: 298161
* [SCEV] Compute affine range in another way to avoid bitwidth extending.Michael Zolotukhin2017-03-161-49/+90
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This approach has two major advantages over the existing one: 1. We don't need to extend bitwidth in our computations. Extending bitwidth is a big issue for compile time as we often end up working with APInts wider than 64bit, which is a slow case for APInt. 2. When we zero extend a wrapped range, we lose some information (we replace the range with [0, 1 << src bit width)). Thus, avoiding such extensions better preserves information. Correctness testing: I ran 'ninja check' with assertions that the new implementation of getRangeForAffineAR gives the same results as the old one (this functionality is not present in this patch). There were several failures - I inspected them manually and found out that they all are caused by the fact that we're returning more accurate results now (see bullet (2) above). Without such assertions 'ninja check' works just fine, as well as SPEC2006. Compile time testing: CTMark/Os: - mafft/pairlocalalign -16.98% - tramp3d-v4/tramp3d-v4 -12.72% - lencod/lencod -11.51% - Bullet/bullet -4.36% - ClamAV/clamscan -3.66% - 7zip/7zip-benchmark -3.19% - sqlite3/sqlite3 -2.95% - SPASS/SPASS -2.74% - Average -5.81% Performance testing: The changes are expected to be neutral for runtime performance. Reviewers: sanjoy, atrick, pete Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D30477 llvm-svn: 297992
* [SCEV] Decrease the recursion threshold for CompareValueComplexitySanjoy Das2017-03-051-6/+11
| | | | | | | | | | 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] Cache results during GetMinTrailingZeros queryIgor Laevsky2017-02-141-8/+22
| | | | | | Differential Revision: https://reviews.llvm.org/D29759 llvm-svn: 295060
* [SCEV] limit recursion depth and operands number in getAddExprDaniil Fukalov2017-02-061-19/+39
| | | | | | | | | | | | | | | | | | | | | 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
* [SCEV] Simplify/generalize howFarToZero solving.Eli Friedman2017-01-311-59/+9
| | | | | | | | | | | | | | Make SolveLinEquationWithOverflow take the start as a SCEV, so we can solve more cases. With that implemented, get rid of the special case for powers of two. The additional functionality probably isn't particularly useful, but it might help a little for certain cases involving pointer arithmetic. Differential Revision: https://reviews.llvm.org/D28884 llvm-svn: 293576
* Cleanup dump() functions.Matthias Braun2017-01-281-2/+3
| | | | | | | | | | | | | | | | | | We had various variants of defining dump() functions in LLVM. Normalize them (this should just consistently implement the things discussed in http://lists.llvm.org/pipermail/cfe-dev/2014-January/034323.html For reference: - Public headers should just declare the dump() method but not use LLVM_DUMP_METHOD or #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) - The definition of a dump method should look like this: #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) LLVM_DUMP_METHOD void MyClass::dump() { // print stuff to dbgs()... } #endif llvm-svn: 293359
OpenPOWER on IntegriCloud