summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Reverting r315590; it did not include changes for llvm-tblgen, which is ↵Aaron Ballman2017-10-151-1/+1
| | | | | | | | causing link errors for several people. Error LNK2019 unresolved external symbol "public: void __cdecl `anonymous namespace'::MatchableInfo::dump(void)const " (?dump@MatchableInfo@?A0xf4f1c304@@QEBAXXZ) referenced in function "public: void __cdecl `anonymous namespace'::AsmMatcherEmitter::run(class llvm::raw_ostream &)" (?run@AsmMatcherEmitter@?A0xf4f1c304@@QEAAXAEAVraw_ostream@llvm@@@Z) llvm-tblgen D:\llvm\2017\utils\TableGen\AsmMatcherEmitter.obj 1 llvm-svn: 315854
* [SCEV] Maintain and use a loop->loop invalidation dependencySanjoy Das2017-10-131-31/+49
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: This change uses the loop use list added in the previous change to remember the loops that appear in the trip count expressions of other loops; and uses it in forgetLoop. This lets us not scan every loop in the function on a forgetLoop call. With this change we no longer invalidate clear out backedge taken counts on forgetValue. I think this is fine -- the contract is that SCEV users must call forgetLoop(L) if their change to the IR could have changed the trip count of L; solely calling forgetValue on a value feeding into the backedge condition of L is not enough. Moreover, I don't think we can strengthen forgetValue to be sufficient for invalidating trip counts without significantly re-architecting SCEV. For instance, if we have the loop: I = *Ptr; E = I + 10; do { // ... } while (++I != E); then the backedge taken count of the loop is 9, and it has no reference to either I or E, i.e. there is no way in SCEV today to re-discover the dependency of the loop's trip count on E or I. So a SCEV client cannot change E to (say) "I + 20", call forgetValue(E) and expect the loop's trip count to be updated. Reviewers: atrick, sunfish, mkazantsev Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38435 llvm-svn: 315713
* [SCEV] Teach SCEV to find maxBECount when loop endbound is variantAnna Thomas2017-10-131-34/+56
| | | | | | | | | | | | | | | | | | | | | | | Summary: This patch teaches SCEV to calculate the maxBECount when the end bound of the loop can vary. Note that we cannot calculate the exactBECount. This will only be done when both conditions are satisfied: 1. the loop termination condition is strictly LT. 2. the IV is proven to not overflow. This provides more information to users of SCEV and can be used to improve identification of finite loops. Reviewers: sanjoy, mkazantsev, silviu.baranga, atrick Reviewed by: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D38825 llvm-svn: 315683
* [SCEV] Maintain loop use lists, and use them in forgetLoopSanjoy Das2017-10-131-0/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Currently we do not correctly invalidate memoized results for add recurrences that were created directly (i.e. they were not created from a `Value`). This change fixes this by keeping loop use lists and using the loop use lists to determine which SCEV expressions to invalidate. Here are some statistics on the number of uses of in the use lists of all loops on a clang bootstrap (config: release, no asserts): Count: 731310 Min: 1 Mean: 8.555150 50th %time: 4 95th %tile: 25 99th %tile: 53 Max: 433 Reviewers: atrick, sunfish, mkazantsev Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D38434 llvm-svn: 315672
* [dump] Remove NDEBUG from test to enable dump methods [NFC]Don Hinton2017-10-121-1/+1
| | | | | | | | | | | | | | | Summary: Add LLVM_FORCE_ENABLE_DUMP cmake option, and use it along with LLVM_ENABLE_ASSERTIONS to set LLVM_ENABLE_DUMP. Remove NDEBUG and only use LLVM_ENABLE_DUMP to enable dump methods. Move definition of LLVM_ENABLE_DUMP from config.h to llvm-config.h so it'll be picked up by public headers. Differential Revision: https://reviews.llvm.org/D38406 llvm-svn: 315590
* [SCEV] Properly handle the case of a non-constant start with a zero accum in ↵Daniel Neilson2017-10-111-2/+1
| | | | | | | | | | | | | | | | | | | | ScalarEvolution::createAddRecFromPHIWithCastsImpl Summary: This patch fixes an error in the patch to ScalarEvolution::createAddRecFromPHIWithCastsImpl made in D37265. In that patch we handle the cases where the either the start or accum values can be zero after truncation. But, we assume that the start value must be a constant if the accum is zero. This is clearly an erroneous assumption. This change removes that assumption. Reviewers: sanjoy, dorit, mkazantsev Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D38814 llvm-svn: 315491
* Remove trailing whitespaces.Michael Liao2017-09-251-41/+41
| | | | llvm-svn: 314115
* [SCEV] Generalize folding of trunc(x)+n*trunc(y) into folding ↵Daniel Neilson2017-09-221-6/+17
| | | | | | | | | | | | | | | | | | | | | | | | | m*trunc(x)+n*trunc(y) Summary: A SCEV such as: {%v2,+,((-1 * (trunc i64 (-1 * %v1) to i32)) + (-1 * (trunc i64 %v1 to i32)))}<%loop> can be folded into, simply, {%v2,+,0}. However, the current code in ::getAddExpr() will not try to apply the simplification m*trunc(x)+n*trunc(y) -> trunc(trunc(m)*x+trunc(n)*y) because it only keys off having a non-multiplied trunc as the first term in the simplification. This patch generalizes this code to try to do a more generic fold of these trunc expressions. Reviewers: sanjoy Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D37888 llvm-svn: 313988
* [ScalarEvolution] Refactor forgetLoop() to improve performanceMarcello Maggioni2017-09-111-40/+45
| | | | | | | | | | | | | | | forgetLoop() has pretty bad performance because it goes over the same instructions over and over again in particular when nested loop are involved. The refactoring changes the function to a not-recursive function and reusing the allocation for data-structures and the Visited set. NFCI Differential Revision: https://reviews.llvm.org/D37659 llvm-svn: 312920
* [SCEV] Ensure ScalarEvolution::createAddRecFromPHIWithCastsImpl properly ↵Daniel Neilson2017-09-051-15/+59
| | | | | | | | | | | | | | | | | | | | | | | | | | | | handles out of range truncations of the start and accum values Summary: When constructing the predicate P1 in ScalarEvolution::createAddRecFromPHIWithCastsImpl() it is possible for the PHISCEV from which the predicate is constructed to be a SCEVConstant instead of a SCEVAddRec. If this happens, then the cast<SCEVAddRec>(PHISCEV) in the code will assert. Such a PHISCEV is possible if either the start value or the accumulator value is a constant value that not equal to its truncated value, and if the truncated value is zero. This patch adds tests that demonstrate the cast<> assertion, and fixes this problem by checking whether the PHISCEV is a constant before constructing the P1 predicate; if it is, then P1 is equivalent to one of P2 or P3. Additionally, if we know that the start value or accumulator value are constants then we check whether the P2 and/or P3 predicates are known false at compile time; if either is, then we bail out of constructing the AddRec. Reviewers: sanjoy, mkazantsev, silviu.baranga Reviewed By: mkazantsev Subscribers: mkazantsev, llvm-commits Differential Revision: https://reviews.llvm.org/D37265 llvm-svn: 312568
* [SCEV] Add URem support to SCEVAlexandre Isoard2017-09-011-0/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 using that relation: %r --> (-%b * (%t /u %b)) + %t We implement two special cases: - if %b is 1, the result is always 0 - if %b is a power-of-two, we produce a zext/trunc based expression instead That is, the following code: %r = urem i32 %t, 65536 Produces: %r --> (zext i16 (trunc i32 %a to i16) to i32) Note that while this helps get a tighter bound on the range analysis and the known-bits analysis, this exposes some normalization shortcoming of SCEVs: %div = udim i32 %a, 65536 %mul = mul i32 %div, 65536 %rem = urem i32 %a, 65536 %add = add i32 %mul, %rem Will usually not be reduced. llvm-svn: 312329
* [Analysis] Fix some Clang-tidy modernize and Include What You Use warnings; ↵Eugene Zelenko2017-08-181-82/+105
| | | | | | other minor fixes (NFC). llvm-svn: 311212
* [SCEV] Preserve NSW information for sext(subtract).Amara Emerson2017-08-041-3/+29
| | | | | | | | | | Pushes the sext onto the operands of a Sub if NSW is present. Also adds support for propagating the nowrap flags of the llvm.ssub.with.overflow intrinsic during analysis. Differential Revision: https://reviews.llvm.org/D35256 llvm-svn: 310117
* [SCEV] Re-enable "Cache results of computeExitLimit"Max Kazantsev2017-08-031-2/+37
| | | | | | | | | | The patch rL309080 was reverted because it did not clean up the cache on "forgetValue" method call. This patch re-enables this change, adds the missing check and introduces two new unit tests that make sure that the cache is cleaned properly. Differential Revision: https://reviews.llvm.org/D36087 llvm-svn: 309925
* [SCEV/IndVars] Always compute loop exiting values if the backedge count is 0Sanjoy Das2017-08-011-0/+19
| | | | | | | | | If SCEV can prove that the backedge taken count for a loop is zero, it does not need to "understand" a recursive PHI to compute its exiting value. This should fix PR33885. llvm-svn: 309758
* [SCEV] Change an early exit to an assert; NFCSanjoy Das2017-07-291-2/+2
| | | | llvm-svn: 309480
* [SCEV] Do not visit nodes twice in containsConstantSomewhereMax Kazantsev2017-07-281-13/+20
| | | | | | | | | | This patch reworks the function that searches constants in Add and Mul SCEV expression chains so that now it does not visit a node more than once, and also renames this function for better correspondence between its implementation and semantics. Differential Revision: https://reviews.llvm.org/D35931 llvm-svn: 309367
* Revert "[SCEV] Cache results of computeExitLimit"Sanjoy Das2017-07-281-21/+0
| | | | | | | | | This reverts commit r309080. The patch needs to clear out the ScalarEvolution::ExitLimits cache in forgetMemoizedResults. I've replied on the commit thread for the patch with more details. llvm-svn: 309357
* [SCEV] Cache results of computeExitLimitMax Kazantsev2017-07-261-0/+21
| | | | | | | | | This patch adds a cache for computeExitLimit to save compilation time. A lot of examples of tests that take extensive time to compile are attached to the bug 33494. Differential Revision: https://reviews.llvm.org/D35827 llvm-svn: 309080
* [SCEV] Remove unnecessary call to forgetMemoizedResultsSanjoy Das2017-07-261-3/+0
| | | | | | | | | | | | | `SCEVUnknown::allUsesReplacedWith` does not need to call `forgetMemoizedResults` since RAUW does a value-equivalent replacement by assumption. If this assumption was false then the later setValPtr(New) call would be incorrect too. This is a non-trivial performance optimization for functions with a large number of loops since `forgetMemoizedResults` walks all loop backedge taken counts to see if any of them use the SCEVUnknown being RAUWed. However, this improvement is difficult to demonstrate without checking in an excessively large IR file. llvm-svn: 309072
* [SCEV] Limit max size of AddRecExpr during evolvingMax Kazantsev2017-07-231-0/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | When SCEV calculates product of two SCEVAddRecs from the same loop, it tries to combine them into one big AddRecExpr. If the sizes of the initial SCEVs were `S1` and `S2`, the size of their product is `S1 + S2 - 1`, and every operand of the resulting SCEV is combined from operands of initial SCEV and has much higher complexity than they have. As result, if we try to calculate something like: %x1 = {a,+,b} %x2 = mul i32 %x1, %x1 %x3 = mul i32 %x2, %x1 %x4 = mul i32 %x3, %x2 ... The size of such SCEVs grows as `2^N`, and the arguments become more and more complex as we go forth. This leads to long compilation and huge memory consumption. This patch sets a limit after which we don't try to combine two `SCEVAddRecExpr`s into one. By default, max allowed size of the resulting AddRecExpr is set to 16. Differential Revision: https://reviews.llvm.org/D35664 llvm-svn: 308847
* PSCEV] Create AddRec for Phis in cases of possible integer overflow,Dorit Nuzman2017-07-181-13/+372
| | | | | | | | | | | | | using runtime checks Extend the SCEVPredicateRewriter to work a bit harder when it encounters an UnknownSCEV for a Phi node; Try to build an AddRecurrence also for Phi nodes whose update chain involves casts that can be ignored under the proper runtime overflow test. This is one step towards addressing PR30654. Differential revision: http://reviews.llvm.org/D30041 llvm-svn: 308299
* [Constants] Replace calls to ConstantInt::equalsInt(0)/equalsInt(1) with ↵Craig Topper2017-07-061-3/+3
| | | | | | isZero and isOne. NFCI llvm-svn: 307293
* [Constants] If we already have a ConstantInt*, prefer to use ↵Craig Topper2017-07-061-7/+7
| | | | | | | | isZero/isOne/isMinusOne instead of isNullValue/isOneValue/isAllOnesValue inherited from Constant. NFCI Going through the Constant methods requires redetermining that the Constant is a ConstantInt and then calling isZero/isOne/isMinusOne. llvm-svn: 307292
* [SCEV] Use depth limit instead of local cache for SExt and ZExtMax Kazantsev2017-06-301-124/+119
| | | | | | | | | | | | | | | | 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-291-26/+0
| | | | | | | Failing test case: Transforms/LoopVectorize.iv_outside_user.ll llvm-svn: 306723
* ScalarEvolution: Add URem supportAlexandre Isoard2017-06-291-0/+26
| | | | | | | | | | | | | | | | | | | | 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
* [SCEV] Avoid copying ConstantRange just to get the min/max valueCraig Topper2017-06-241-67/+62
| | | | | | | | | | | | | | | | | | | | | Summary: This patch changes getRange to getRangeRef and returns a reference to the ConstantRange object stored inside the DenseMap caches. We then take advantage of that to add new helper methods that can return min/max value of a signed or unsigned ConstantRange using that reference without first copying the ConstantRange. getRangeRef calls itself recursively and I believe the reference return is fine for those calls. I've left getSignedRange and getUnsignedRange returning a ConstantRange object so they will make a copy now. This is to ensure safety since the reference will be invalidated if the DenseMap changes. I'm sure there are still more places that can take advantage of the reference and I'll submit future patches as I find them. Reviewers: sanjoy, davide Reviewed By: sanjoy Subscribers: zzheng, llvm-commits, mzolotukhin Differential Revision: https://reviews.llvm.org/D32978 llvm-svn: 306229
* [SCEV] Make MulOpsInlineThreshold lower to avoid excessive compilation timeMax Kazantsev2017-06-211-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | MulOpsInlineThreshold option of SCEV is defaulted to 1000, which is inadequately high. When constructing SCEVs of expressions like: x1 = a * a x2 = x1 * x1 x3 = x2 * x2 ... We actually have huge SCEVs with max allowed amount of operands inlined. Such expressions are easy to get from unrolling of loops looking like x = a for (i = 0; i < n; i++) x = x * x Or more tricky cases where big powers are involved. If some non-linear analysis tries to work with a SCEV that has 1000 operands, it may lead to excessively long compilation. The attached test does not pass within 1 minute with default threshold. This patch decreases its default value to 32, which looks much more reasonable if we use analyzes with complexity O(N^2) or O(N^3) working with SCEV. Differential Revision: https://reviews.llvm.org/D34397 llvm-svn: 305882
* [SCEV][NFC] Fix a misleading description of AddOpsInlineThresholdMax Kazantsev2017-06-201-1/+1
| | | | | | | | | The description of this option was copy-pasted from another one and does not correspond to reality. Differential Revision: https://reviews.llvm.org/D34390 llvm-svn: 305782
* [ScalarEvolution] Apply Depth limit to getMulExprMax Kazantsev2017-06-151-53/+76
| | | | | | | | | | | | | | | | | | | | | 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
* [InstSimplify] Don't constant fold or DCE calls that are marked nobuiltinAndrew Kaylor2017-06-091-1/+1
| | | | | | Differential Revision: https://reviews.llvm.org/D33737 llvm-svn: 305132
* Sort the remaining #include lines in include/... and lib/....Chandler Carruth2017-06-061-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | I did this a long time ago with a janky python script, but now clang-format has built-in support for this. I fed clang-format every line with a #include and let it re-sort things according to the precise LLVM rules for include ordering baked into clang-format these days. I've reverted a number of files where the results of sorting includes isn't healthy. Either places where we have legacy code relying on particular include ordering (where possible, I'll fix these separately) or where we have particular formatting around #include lines that I didn't want to disturb in this patch. This patch is *entirely* mechanical. If you get merge conflicts or anything, just ignore the changes in this patch and run clang-format over your #include lines in the files. Sorry for any noise here, but it is important to keep these things stable. I was seeing an increasing number of patches with irrelevant re-ordering of #include lines because clang-format was used. This patch at least isolates that churn, makes it easy to skip when resolving conflicts, and gets us to a clean baseline (again). llvm-svn: 304787
* Added LLVM_FALLTHROUGH to address warning: this statement may fall through. NFC.Galina Kistanova2017-05-311-0/+4
| | | | llvm-svn: 304358
* [SCEV][NFC] Remove redundant params from isAvailableAtLoopEntryMax Kazantsev2017-05-301-4/+3
| | | | | | | | Params DT and LI are redundant, because these values are contained in fields anyways. Differential Revision: https://reviews.llvm.org/D33668 llvm-svn: 304204
* [SCEV] Assume parameters coming from function calls contain IVsTobias Grosser2017-05-271-1/+4
| | | | | | | | | | | | | | | | | | | | The optimistic delinearization implemented in LLVM detects array sizes by looking for non-linear products between parameters and induction variables. In OpenCL code, such products often look like: A[get_global_id(0) * N + get_global_id(1)] Hence, the IV is hidden in the get_global_id() call and consequently delinearization would fail as no induction variable is available that helps us to identify N as array size parameter. We now use a very simple heuristic to change this. We assume that each parameter that comes directly from a function call is a hidden induction variable. As a result, we can delinearize the access above to: A[get_global_id(0)][get_global_id(1] llvm-svn: 304073
* Re-enable "[SCEV] Do not fold dominated SCEVUnknown into AddRecExpr start"Max Kazantsev2017-05-261-2/+59
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [ValueTracking] Convert most of the calls to computeKnownBits to use the ↵Craig Topper2017-05-241-6/+2
| | | | | | | | | | version that returns the KnownBits object. This continues the changes started when computeSignBit was replaced with this new version of computeKnowBits. Differential Revision: https://reviews.llvm.org/D33431 llvm-svn: 303773
* Revert "[SCEV] Do not fold dominated SCEVUnknown into AddRecExpr start"Diana Picus2017-05-241-59/+2
| | | | | | 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-2/+59
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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-221-10/+37
| | | | | | | | | | | | | | | | | | | | | | | 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-211-37/+10
| | | | | | | 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-211-10/+37
| | | | | | | | | | | | | | | | | | | 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][NFC] Remove duplication of isLoopInvariant codeMax Kazantsev2017-05-181-2/+2
| | | | | | | | | Replace two places that duplicate the code of isLoopInvariant method with the invocation of this method. Differential Revision: https://reviews.llvm.org/D33313 llvm-svn: 303336
* [SCEV] Always sort AddRecExprs from different loops by dominanceMax Kazantsev2017-05-171-7/+7
| | | | | | | | | | | | | | Sorting of AddRecExprs by loop nesting does not make sense since we only invoke the CompareSCEVComplexity for AddRecExprs that are used by one SCEV. This guarantees that there is always a dominance relationship between them. This patch removes the sorting by nesting which is a dead code in current usage of this function. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D33228 llvm-svn: 303235
* [SCEV][NFC] Replace redundant dyn_cast with cast in getAddExprMax Kazantsev2017-05-171-14/+15
| | | | | | | | Replace dyn_cast which is ensured by isa just one line above with cast. Differential Revision: https://reviews.llvm.org/D33231 llvm-svn: 303234
* [SCEV] Fix sorting order for AddRecExprsMax Kazantsev2017-05-161-16/+31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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] Use copy initialization of APInts instead of direct initialization.Craig Topper2017-05-151-6/+6
| | | | | | This is based on post commit feed back from r302769. llvm-svn: 303092
* [ValueTracking] Replace all uses of ComputeSignBit with computeKnownBits.Craig Topper2017-05-151-5/+4
| | | | | | | | This patch finishes off the conversion of ComputeSignBit to computeKnownBits. Differential Revision: https://reviews.llvm.org/D33166 llvm-svn: 303035
* Move some code into ScalarEvolution.cpp; NFCSanjoy Das2017-05-151-0/+24
| | | | | | | I need to add some asserts to these constructors that are easier to add once they're in the .cpp file. llvm-svn: 303032
OpenPOWER on IntegriCloud