summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [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
* [SCEV] Introduce add operation inlining limitDaniil Fukalov2017-01-261-0/+8
| | | | | | | | | | | | | Inlining in getAddExpr() can cause abnormal computational time in some cases. New parameter -scev-addops-inline-threshold is intruduced with default value 500. Reviewers: sanjoy Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D28812 llvm-svn: 293176
* [SCEV] Make getUDivExactExpr handle non-nuw multiplies correctly.Eli Friedman2017-01-181-16/+21
| | | | | | | | | | | | | | | | | To avoid regressions, make ScalarEvolution::createSCEV a bit more clever. Also get rid of some useless code in ScalarEvolution::howFarToZero which was hiding this bug. No new testcase because it's impossible to actually expose this bug: we don't have any in-tree users of getUDivExactExpr besides the two functions I just mentioned, and they both dodged the problem. I'll try to add some interesting users in a followup. Differential Revision: https://reviews.llvm.org/D28587 llvm-svn: 292449
* [SCEV] Limit recursion depth of constant evolving.Michael Liao2017-01-131-3/+10
| | | | | | | | | | - For a loop body with VERY complicated exit condition evaluation, constant evolving may run out of stack on platforms such as Windows. Need to limit the recursion depth. Differential Revision: https://reviews.llvm.org/D28629 llvm-svn: 291927
* [SCEV] Simplify SolveLinEquationWithOverflow a bit.Eli Friedman2017-01-121-7/+8
| | | | | | Cleanup in preparation for generalizing it. llvm-svn: 291808
* [SCEV] Make howFarToZero max backedge-taken count check for precondition.Eli Friedman2017-01-111-0/+17
| | | | | | | | | Refines max backedge-taken count if a loop like "for (int i = 0; i != n; ++i) { /* body */ }" is rotated. Differential Revision: https://reviews.llvm.org/D28536 llvm-svn: 291704
* [SCEV] Make howFarToZero use a simpler formula for max backedge-taken count.Eli Friedman2017-01-111-11/+2
| | | | | | | | | This is both easier to understand, and produces a tighter bound in certain cases. Differential Revision: https://reviews.llvm.org/D28393 llvm-svn: 291701
* [PM] Teach SCEV to invalidate itself when its dependencies becomeChandler Carruth2017-01-091-0/+12
| | | | | | | | | | | | | invalid. This fixes use-after-free bugs that will arise with any interesting use of SCEV. I've added a dedicated test that works diligently to trigger these kinds of bugs in the new pass manager and also checks for them explicitly as well as triggering ASan failures when things go squirly. llvm-svn: 291426
* [SCEV] Be less conservative when extending bitwidths for computing ranges.Michael Zolotukhin2016-12-201-7/+6
| | | | | | | | | | | | | | | | | | | | | | | | Summary: In getRangeForAffineAR we compute ranges for affine exprs E = A + B*C, where ranges for A, B, and C are known. To avoid overflow, we need to operate on a bigger bitwidth, and originally we chose 2*x+1 for this (x being the original bitwidth). However, it is safe to use just 2*x: A+B*C <= (2^x - 1) + (2^x - 1)*(2^x - 1) = = 2^x - 1 + 2^2x - 2^x - 2^x + 1 = = 2^2x - 2^x <= 2^2x - 1 Unnecessary extending of bitwidths results in noticeable slowdowns: ranges perform arithmetic operations using APInt, which are much slower when bitwidths are bigger than 64. Reviewers: sanjoy, majnemer, chandlerc Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D27795 llvm-svn: 290211
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-85/+36
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Fix iterator-invalidation issueHal Finkel2016-12-151-1/+3
| | | | | | | | | Inserting a new key into a DenseMap potentially invalidates iterators into that map. Trying to fix an issue from r289755 triggering this assertion: Assertion `isHandleInSync() && "invalid iterator access!"' failed. llvm-svn: 289757
OpenPOWER on IntegriCloud