summaryrefslogtreecommitdiffstats
path: root/llvm/test/Analysis/ScalarEvolution
Commit message (Collapse)AuthorAgeFilesLines
* Revert "Revert "Revert "[IndVars] Canonicalize comparisons between ↵Max Kazantsev2017-07-061-3/+3
| | | | | | | | | non-negative values and indvars""" It appears that the problem is still there. Needs more analysis to understand why SaturatedMultiply test fails. llvm-svn: 307249
* Revert "Revert "[IndVars] Canonicalize comparisons between non-negative ↵Max Kazantsev2017-07-061-3/+3
| | | | | | | | | | | | | values and indvars"" It seems that the patch was reverted by mistake. Clang testing showed failure of the MathExtras.SaturatingMultiply test, however I was unable to reproduce the issue on the fresh code base and was able to confirm that the transformation introduced by the change does not happen in the said test. This gives a strong confidence that the actual reason of the failure of the initial patch was somewhere else, and that problem now seems to be fixed. Re-submitting the change to confirm that. llvm-svn: 307244
* Revert "[IndVars] Canonicalize comparisons between non-negative values and ↵Max Kazantsev2017-07-051-3/+3
| | | | | | | | | | | indvars" This patch seems to cause failures of test MathExtras.SaturatingMultiply on multiple buildbots. Reverting until the reason of that is clarified. Differential Revision: https://reviews.llvm.org/rL307126 llvm-svn: 307135
* [IndVars] Canonicalize comparisons between non-negative values and indvarsMax Kazantsev2017-07-051-3/+3
| | | | | | | | | | | | | | | | | -If there is a IndVar which is known to be non-negative, and there is a value which is also non-negative, then signed and unsigned comparisons between them produce the same result. Both of those can be seen in the same loop. To allow other optimizations to simplify them, we turn all instructions like %c = icmp slt i32 %iv, %b to %c = icmp ult i32 %iv, %b if both %iv and %b are known to be non-negative. Differential Revision: https://reviews.llvm.org/D34979 llvm-svn: 307126
* [SCEV] Use depth limit instead of local cache for SExt and ZExtMax Kazantsev2017-06-301-1/+57
| | | | | | | | | | | | | | | | In rL300494 there was an attempt to deal with excessive compile time on invocations of getSign/ZeroExtExpr using local caching. This approach only helps if we request the same SCEV multiple times throughout recursion. But in the bug PR33431 we see a case where we request different values all the time, so caching does not help and the size of the cache grows enormously. In this patch we remove the local cache for this methods and add the recursion depth limit instead, as we do for arithmetics. This gives us a guarantee that the invocation sequence is limited and reasonably short. Differential Revision: https://reviews.llvm.org/D34273 llvm-svn: 306785
* Reverting r306695 while investigating failing test case.Alexandre Isoard2017-06-292-37/+0
| | | | | | | Failing test case: Transforms/LoopVectorize.iv_outside_user.ll llvm-svn: 306723
* ScalarEvolution: Add URem supportAlexandre Isoard2017-06-292-0/+37
| | | | | | | | | | | | | | | | | | | | In LLVM IR the following code: %r = urem <ty> %t, %b is equivalent to: %q = udiv <ty> %t, %b %s = mul <ty> nuw %q, %b %r = sub <ty> nuw %t, %q ; (t / b) * b + (t % b) = t As UDiv, Mul and Sub are already supported by SCEV, URem can be implemented with minimal effort this way. Note: While SRem and SDiv are also related this way, SCEV does not provides SDiv yet. llvm-svn: 306695
* [ScalarEvolution] Apply Depth limit to getMulExprMax Kazantsev2017-06-151-0/+44
| | | | | | | | | | | | | | | | | | | | | This is a fix for PR33292 that shows a case of extremely long compilation of a single .c file with clang, with most time spent within SCEV. We have a mechanism of limiting recursion depth for getAddExpr to avoid long analysis in SCEV. However, there are calls from getAddExpr to getMulExpr and back that do not propagate the info about depth. As result of this, a chain getAddExpr -> ... .> getAddExpr -> getMulExpr -> getAddExpr -> ... -> getAddExpr can be extremely long, with every segment of getAddExpr's being up to max depth long. This leads either to long compilation or crash by stack overflow. We face this situation while analyzing big SCEVs in the test of PR33292. This patch applies the same limit on max expression depth for getAddExpr and getMulExpr. Differential Revision: https://reviews.llvm.org/D33984 llvm-svn: 305463
* Re-enable "[SCEV] Do not fold dominated SCEVUnknown into AddRecExpr start"Max Kazantsev2017-05-261-3/+61
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The patch rL303730 was reverted because test lsr-expand-quadratic.ll failed on many non-X86 configs with this patch. The reason of this is that the patch makes a correctless fix that changes optimizer's behavior for this test. Without the change, LSR was making an overconfident simplification basing on a wrong SCEV. Apparently it did not need the IV analysis to do this. With the change, it chose a different way to simplify (that wasn't so confident), and this way required the IV analysis. Now, following the right execution path, LSR tries to make a transformation relying on IV Users analysis. This analysis is target-dependent due to this code: // LSR is not APInt clean, do not touch integers bigger than 64-bits. // Also avoid creating IVs of non-native types. For example, we don't want a // 64-bit IV in 32-bit code just because the loop has one 64-bit cast. uint64_t Width = SE->getTypeSizeInBits(I->getType()); if (Width > 64 || !DL.isLegalInteger(Width)) return false; To make a proper transformation in this test case, the type i32 needs to be legal for the specified data layout. When the test runs on some non-X86 configuration (e.g. pure ARM 64), opt gets confused by the specified target and does not use it, rejecting the specified data layout as well. Instead, it uses some default layout that does not treat i32 as a legal type (currently the layout that is used when it is not specified does not have legal types at all). As result, the transformation we expect to happen does not happen for this test. This re-enabling patch does not have any source code changes compared to the original patch rL303730. The only difference is that the failing test is moved to X86 directory and now has requirement of running on x86 only to comply with the specified target triple and data layout. Differential Revision: https://reviews.llvm.org/D33543 llvm-svn: 303971
* Revert "[SCEV] Do not fold dominated SCEVUnknown into AddRecExpr start"Diana Picus2017-05-241-61/+3
| | | | | | This reverts commit r303730 because it broke all the buildbots. llvm-svn: 303747
* [SCEV] Do not fold dominated SCEVUnknown into AddRecExpr startMax Kazantsev2017-05-241-3/+61
| | | | | | | | | | | | | | | | | | | | | | | | | | | When folding arguments of AddExpr or MulExpr with recurrences, we rely on the fact that the loop of our base recurrency is the bottom-lost in terms of domination. This assumption may be broken by an expression which is treated as invariant, and which depends on a complex Phi for which SCEVUnknown was created. If such Phi is a loop Phi, and this loop is lower than the chosen AddRecExpr's loop, it is invalid to fold our expression with the recurrence. Another reason why it might be invalid to fold SCEVUnknown into Phi start value is that unlike other SCEVs, SCEVUnknown are sometimes position-bound. For example, here: for (...) { // loop phi = {A,+,B} } X = load ... Folding phi + X into {A+X,+,B}<loop> actually makes no sense, because X does not exist and cannot exist while we are iterating in loop (this memory can be even not allocated and not filled by this moment). It is only valid to make such folding if X is defined before the loop. In this case the recurrence {A+X,+,B}<loop> may be existant. This patch prohibits folding of SCEVUnknown (and those who use them) into the start value of an AddRecExpr, if this instruction is dominated by the loop. Merging the dominating unknown values is still valid. Some tests that relied on the fact that some SCEVUnknown should be folded into AddRec's are changed so that they no longer expect such behavior. llvm-svn: 303730
* [SCEV] Clarify behavior around max backedge taken countSanjoy Das2017-05-222-6/+6
| | | | | | | | | | | | | | | | | | | | | | | This is a re-application of a r303497 that was reverted in r303498. I thought it had broken a bot when it had not (the breakage did not go away with the revert). This change makes the split between the "exact" backedge taken count and the "maximum" backedge taken count a bit more obvious. Both of these are upper bounds on the number of times the loop header executes (since SCEV does not account for most kinds of abnormal control flow), but the latter is guaranteed to be a constant. There were a few places where the max backedge taken count *was* a non-constant; I've changed those to compute constants instead. At this point, I'm not sure if the constant max backedge count can be computed by calling `getUnsignedRange(Exact).getUnsignedMax()` without losing precision. If it can, we can simplify even further by making `getMaxBackedgeTakenCount` a thin wrapper around `getBackedgeTakenCount` and `getUnsignedRange`. llvm-svn: 303531
* Revert "[SCEV] Clarify behavior around max backedge taken count"Sanjoy Das2017-05-212-6/+6
| | | | | | | This reverts commit r303497 since it breaks the msan bootstrap bot: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap/builds/1379/ llvm-svn: 303498
* [SCEV] Clarify behavior around max backedge taken countSanjoy Das2017-05-212-6/+6
| | | | | | | | | | | | | | | | | | | This change makes the split between the "exact" backedge taken count and the "maximum" backedge taken count a bit more obvious. Both of these are upper bounds on the number of times the loop header executes (since SCEV does not account for most kinds of abnormal control flow), but the latter is guaranteed to be a constant. There were a few places where the max backedge taken count *was* a non-constant; I've changed those to compute constants instead. At this point, I'm not sure if the constant max backedge count can be computed by calling `getUnsignedRange(Exact).getUnsignedMax()` without losing precision. If it can, we can simplify even further by making `getMaxBackedgeTakenCount` a thin wrapper around `getBackedgeTakenCount` and `getUnsignedRange`. llvm-svn: 303497
* [SCEV] Fix sorting order for AddRecExprsMax Kazantsev2017-05-161-0/+454
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The existing sorting order in defined CompareSCEVComplexity sorts AddRecExprs by loop depth, but does not pay attention to dominance of loops. This can lead us to the following buggy situation: for (...) { // loop1 op1 = {A,+,B} } for (...) { // loop2 op2 = {A,+,B} S = add op1, op2 } In this case there is no guarantee that in operand list of S the op2 comes before op1 (loop depth is the same, so they will be sorted just lexicographically), so we can incorrectly treat S as a recurrence of loop1, which is wrong. This patch changes the sorting logic so that it places the dominated recs before the dominating recs. This ensures that when we pick the first recurrency in the operands order, it will be the bottom-most in terms of domination tree. The attached test set includes some tests that produce incorrect SCEV estimations and crashes with oldlogic. Reviewers: sanjoy, reames, apilipenko, anna Reviewed By: sanjoy Subscribers: llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D33121 llvm-svn: 303148
* [SCEV] createAddRecFromPHI: Optimize for the most common case.Michael Zolotukhin2017-05-031-0/+18
| | | | | | | | | | | | | | | | | | | 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/+1
| | | | | | | | | | | | | | | | | 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] Fix exponential time complexity by cachingSanjoy Das2017-04-241-0/+57
| | | | llvm-svn: 301149
* Revert r300746 (SCEV analysis for or instructions).Eli Friedman2017-04-201-38/+0
| | | | | | | | 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
* [SCEV] Make SCEV or modeling more aggressive.Eli Friedman2017-04-191-0/+38
| | | | | | | | | | 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
* [ScalarEvolution] Re-enable Predicate implication from operationsMax Kazantsev2017-03-312-0/+381
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Revert "[ScalarEvolution] Re-enable Predicate implication from operations"Max Kazantsev2017-03-242-358/+0
| | | | | | | | This reverts commit rL298690 Causes failures on clang. llvm-svn: 298693
* [ScalarEvolution] Re-enable Predicate implication from operationsMax Kazantsev2017-03-242-0/+358
| | | | | | | | | | | | | | | | | | | | | | | | 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-232-0/+128
| | | | | | | | | | | | | 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 "[ScalarEvolution] Predicate implication from operations"Max Kazantsev2017-03-221-334/+0
| | | | | | | | This reverts commit rL298481 Fails clang-with-lto-ubuntu build. llvm-svn: 298489
* [ScalarEvolution] Predicate implication from operationsMax Kazantsev2017-03-221-0/+334
| | | | | | | | | | | | | | | | | | | | | | | 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-0/+125
| | | | | | | | | | | | | | | | | | | | 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] Compute affine range in another way to avoid bitwidth extending.Michael Zolotukhin2017-03-161-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [ValueTracking] Make poison propagation more aggressiveSanjoy Das2017-02-221-15/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Motivation: fix PR31181 without regression (the actual fix is still in progress). However, the actual content of PR31181 is not relevant here. This change makes poison propagation more aggressive in the following cases: 1. poision * Val == poison, for any Val. In particular, this changes existing intentional and documented behavior in these two cases: a. Val is 0 b. Val is 2^k * N 2. poison << Val == poison, for any Val 3. getelementptr is poison if any input is poison I think all of these are justified (and are axiomatically true in the new poison / undef model): 1a: we need poison * 0 to be poison to allow transforms like these: A * (B + C) ==> A * B + A * C If poison * 0 were 0 then the above transform could not be allowed since e.g. we could have A = poison, B = 1, C = -1, making the LHS poison * (1 + -1) = poison * 0 = 0 and the RHS poison * 1 + poison * -1 = poison + poison = poison 1b: we need e.g. poison * 4 to be poison since we want to allow A * 4 ==> A + A + A + A If poison * 4 were a value with all of their bits poison except the last four; then we'd not be able to do this transform since then if A were poison the LHS would only be "partially" poison while the RHS would be "full" poison. 2: Same reasoning as (1b), we'd like have the following kinds transforms be legal: A << 1 ==> A + A Reviewers: majnemer, efriedma Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D30185 llvm-svn: 295809
* [SCEV] Cache results during GetMinTrailingZeros queryIgor Laevsky2017-02-141-0/+63
| | | | | | Differential Revision: https://reviews.llvm.org/D29759 llvm-svn: 295060
* [SCEV] Simplify/generalize howFarToZero solving.Eli Friedman2017-01-312-4/+38
| | | | | | | | | | | | | | 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
* [SCEV] Introduce add operation inlining limitDaniil Fukalov2017-01-261-0/+17
| | | | | | | | | | | | | 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
* This test apparently requires an x86 target and is failing on numerousChandler Carruth2017-01-231-48/+0
| | | | | | | | | | | bots ever since d0k fixed the CHECK lines so that it did something at all. It isn't actually testing SCEV directly but LSR, so move it into LSR and the x86-specific tree of tests that already exists there. Target dependence is common and unavoidable with the current design of LSR. llvm-svn: 292774
* Attempt to fix test in release builds.Benjamin Kramer2017-01-221-5/+5
| | | | llvm-svn: 292762
* Fix some broken CHECK lines.Benjamin Kramer2017-01-221-6/+6
| | | | | | The colon is important. llvm-svn: 292761
* [SCEV] Make getUDivExactExpr handle non-nuw multiplies correctly.Eli Friedman2017-01-181-1/+1
| | | | | | | | | | | | | | | | | 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
* [PM] Clean up the testing for IVUsers, especially with the new PM.Chandler Carruth2017-01-153-0/+3
| | | | | | | | | | First, I've moved a test of IVUsers from the LSR tree to a dedicated IVUsers test directory. I've also simplified its RUN line now that the new pass manager's loop PM is providing analyses on their own. No functionality changed, but it makes subsequent changes cleaner. llvm-svn: 292060
* [PM] The assumption cache is fundamentally designed to be self-updating,Chandler Carruth2017-01-151-13/+0
| | | | | | | | | | | | | | mark it as never invalidated in the new PM. The old PM already required this to work, and after a discussion with Hal this seems to really be the only sensible answer. The cache gracefully degrades as the IR is mutated, and most things which do this should already be incrementally updating the cache. This gets rid of a bunch of logic preserving and testing the invalidation of this analysis. llvm-svn: 292039
* [SCEV] Make howFarToZero max backedge-taken count check for precondition.Eli Friedman2017-01-111-4/+2
| | | | | | | | | 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-0/+83
| | | | | | | | | 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/+70
| | | | | | | | | | | | | 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
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-192-3/+3
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Make processing @llvm.assume more efficient by using operand bundlesHal Finkel2016-12-152-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | There was an efficiency problem with how we processed @llvm.assume in ValueTracking (and other places). The AssumptionCache tracked all of the assumptions in a given function. In order to find assumptions relevant to computing known bits, etc. we searched every assumption in the function. For ValueTracking, that means that we did O(#assumes * #values) work in InstCombine and other passes (with a constant factor that can be quite large because we'd repeat this search at every level of recursion of the analysis). Several of us discussed this situation at the last developers' meeting, and this implements the discussed solution: Make the values that an assume might affect operands of the assume itself. To avoid exposing this detail to frontends and passes that need not worry about it, I've used the new operand-bundle feature to add these extra call "operands" in a way that does not affect the intrinsic's signature. I think this solution is relatively clean. InstCombine adds these extra operands based on what ValueTracking, LVI, etc. will need and then those passes need only search the users of the values under consideration. This should fix the computational-complexity problem. At this point, no passes depend on the AssumptionCache, and so I'll remove that as a follow-up change. Differential Revision: https://reviews.llvm.org/D27259 llvm-svn: 289755
* [SCEV] Memoize visitMulExpr results in SCEVRewriteVisitor.Li Huang2016-10-211-0/+67
| | | | | | | | | | | | | | | | | | Summary: When SCEVRewriteVisitor traverses the SCEV DAG, it may visit the same SCEV multiple times if this SCEV is referenced by multiple other SCEVs. This has exponential time complexity in the worst case. Memoizing the results will avoid re-visiting the same SCEV. Add a map to save the results, and override the visit function of SCEVVisitor. Now SCEVRewriteVisitor only visit each SCEV once and thus returns the same result for the same input SCEV. This patch fixes PR18606, PR18607. Reviewers: Sanjoy Das, Mehdi Amini, Michael Zolotukhin Differential Revision: https://reviews.llvm.org/D25810 llvm-svn: 284868
* [LoopUnroll] Keep the loop test only on the first iteration of max-or-zero loopsJohn Brawn2016-10-212-12/+12
| | | | | | | | | | | | | | | | When we have a loop with a known upper bound on the number of iterations, and furthermore know that either the number of iterations will be either exactly that upper bound or zero, then we can fully unroll up to that upper bound keeping only the first loop test to check for the zero iteration case. Most of the work here is in plumbing this 'max-or-zero' information from the part of scalar evolution where it's detected through to loop unrolling. I've also gone for the safe default of 'false' everywhere but howManyLessThans which could probably be improved. Differential Revision: https://reviews.llvm.org/D25682 llvm-svn: 284818
* [SCEV] Add a threshold to restrict number of mul operands to be inlined into ↵Li Huang2016-10-201-0/+29
| | | | | | | | | | | | | SCEV This is to avoid inlining too many multiplication operands into a SCEV, which could take exponential time in the worst case. Reviewers: Sanjoy Das, Mehdi Amini, Michael Zolotukhin Differential Revision: https://reviews.llvm.org/D25794 llvm-svn: 284784
* [SCEV] More accurate calculation of max backedge count of some less-than loopsJohn Brawn2016-10-182-4/+181
| | | | | | | | | | | | | | | | | | | | | In loops that look something like i = n; do { ... } while(i++ < n+k); where k is a constant, the maximum backedge count is k (in fact the backedge count will be either 0 or k, depending on whether n+k wraps). More generally for LHS < RHS if RHS-(LHS of first comparison) is a constant then the loop will iterate either 0 or that constant number of times. This allows for more loop unrolling with the recent upper bound loop unrolling changes, and I'm working on a patch that will let loop unrolling additionally make use of the loop being executed either 0 or k times (we need to retain the loop comparison only on the first unrolled iteration). Differential Revision: https://reviews.llvm.org/D25607 llvm-svn: 284465
* Reapplying r278731 after fixing the problem that caused it to be reverted.David L Kreitzer2016-09-161-0/+62
| | | | | | | | | | Enhance SCEV to compute the trip count for some loops with unknown stride. Patch by Pankaj Chawla Differential Revision: https://reviews.llvm.org/D22377 llvm-svn: 281732
* Create a getelementptr instead of sub expr for ValueOffsetPair if theWei Mi2016-09-141-0/+36
| | | | | | | | | | | | value is a pointer. This patch is to fix PR30213. When expanding an expr based on ValueOffsetPair, if the value is of pointer type, we can only create a getelementptr instead of sub expr. Differential Revision: https://reviews.llvm.org/D24088 llvm-svn: 281439
* [UNROLL] Postpone ScalarEvolution::forgetLoop after TripCountSC is expandedWei Mi2016-08-252-0/+37
| | | | | | | | | | | | | | when unroll runtime iteration loop. In llvm::UnrollRuntimeLoopRemainder, if the loop to be unrolled is the inner loop inside a loop nest, the scalar evolution needs to be dropped for its parent loop which is done by ScalarEvolution::forgetLoop. However, we can postpone forgetLoop to the end of UnrollRuntimeLoopRemainder so TripCountSC expansion can still reuse existing value. Differential Revision: https://reviews.llvm.org/D23572 llvm-svn: 279748
OpenPOWER on IntegriCloud