summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/IndVarSimplify
Commit message (Collapse)AuthorAgeFilesLines
* [SimplifyIndVar] Canonicalize comparisons to unsigned while eliminating truncsMax Kazantsev2018-07-271-0/+31
| | | | | | | | | | | This is a follow-up for the patch rL335020. When we replace compares against trunc with compares against wide IV, we can also replace signed predicates with unsigned where it is legal. Reviewed By: reames Differential Revision: https://reviews.llvm.org/D48763 llvm-svn: 338115
* [SCEV] Add [zs]ext{C,+,x} -> (D + [zs]ext{C-D,+,x})<nuw><nsw> transformRoman Tereshin2018-07-251-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | as well as sext(C + x + ...) -> (D + sext(C-D + x + ...))<nuw><nsw> similar to the equivalent transformation for zext's if the top level addition in (D + (C-D + x * n)) could be proven to not wrap, where the choice of D also maximizes the number of trailing zeroes of (C-D + x * n), ensuring homogeneous behaviour of the transformation and better canonicalization of such AddRec's (indeed, there are 2^(2w) different expressions in `B1 + ext(B2 + Y)` form for the same Y, but only 2^(2w - k) different expressions in the resulting `B3 + ext((B4 * 2^k) + Y)` form, where w is the bit width of the integral type) This patch generalizes sext(C1 + C2*X) --> sext(C1) + sext(C2*X) and sext{C1,+,C2} --> sext(C1) + sext{0,+,C2} transformations added in r209568 relaxing the requirements the following way: 1. C2 doesn't have to be a power of 2, it's enough if it's divisible by 2 a sufficient number of times; 2. C1 doesn't have to be less than C2, instead of extracting the entire C1 we can split it into 2 terms: (00...0XXX + YY...Y000), keep the second one that may cause wrapping within the extension operator, and move the first one that doesn't affect wrapping out of the extension operator, enabling further simplifications; 3. C1 and C2 don't have to be positive, splitting C1 like shown above produces a sum that is guaranteed to not wrap, signed or unsigned; 4. in AddExpr case there could be more than 2 terms, and in case of AddExpr the 2nd and following terms and in case of AddRecExpr the Step component don't have to be in the C2*X form or constant (respectively), they just need to have enough trailing zeros, which in turn could be guaranteed by means other than arithmetics, e.g. by a pointer alignment; 5. the extension operator doesn't have to be a sext, the same transformation works and profitable for zext's as well. Apparently, optimizations like SLPVectorizer currently fail to vectorize even rather trivial cases like the following: double bar(double *a, unsigned n) { double x = 0.0; double y = 0.0; for (unsigned i = 0; i < n; i += 2) { x += a[i]; y += a[i + 1]; } return x * y; } If compiled with `clang -std=c11 -Wpedantic -Wall -O3 main.c -S -o - -emit-llvm` (!{!"clang version 7.0.0 (trunk 337339) (llvm/trunk 337344)"}) it produces scalar code with the loop not unrolled with the unsigned `n` and `i` (like shown above), but vectorized and unrolled loop with signed `n` and `i`. With the changes made in this commit the unsigned version will be vectorized (though not unrolled for unclear reasons). How it all works: Let say we have an AddExpr that looks like (C + x + y + ...), where C is a constant and x, y, ... are arbitrary SCEVs. Let's compute the minimum number of trailing zeroes guaranteed of that sum w/o the constant term: (x + y + ...). If, for example, those terms look like follows: i XXXX...X000 YYYY...YY00 ... ZZZZ...0000 then the rightmost non-guaranteed-zero bit (a potential one at i-th position above) can change the bits of the sum to the left (and at i-th position itself), but it can not possibly change the bits to the right. So we can compute the number of trailing zeroes by taking a minimum between the numbers of trailing zeroes of the terms. Now let's say that our original sum with the constant is effectively just C + X, where X = x + y + .... Let's also say that we've got 2 guaranteed trailing zeros for X: j CCCC...CCCC XXXX...XX00 // this is X = (x + y + ...) Any bit of C to the left of j may in the end cause the C + X sum to wrap, but the rightmost 2 bits of C (at positions j and j - 1) do not affect wrapping in any way. If the upper bits cause a wrap, it will be a wrap regardless of the values of the 2 least significant bits of C. If the upper bits do not cause a wrap, it won't be a wrap regardless of the values of the 2 bits on the right (again). So let's split C to 2 constants like follows: 0000...00CC = D CCCC...CC00 = (C - D) and represent the whole sum as D + (C - D + X). The second term of this new sum looks like this: CCCC...CC00 XXXX...XX00 ----------- // let's add them up YYYY...YY00 The sum above (let's call it Y)) may or may not wrap, we don't know, so we need to keep it under a sext/zext. Adding D to that sum though will never wrap, signed or unsigned, if performed on the original bit width or the extended one, because all that that final add does is setting the 2 least significant bits of Y to the bits of D: YYYY...YY00 = Y 0000...00CC = D ----------- <nuw><nsw> YYYY...YYCC Which means we can safely move that D out of the sext or zext and claim that the top-level sum neither sign wraps nor unsigned wraps. Let's run an example, let's say we're working in i8's and the original expression (zext's or sext's operand) is 21 + 12x + 8y. So it goes like this: 0001 0101 // 21 XXXX XX00 // 12x YYYY Y000 // 8y 0001 0101 // 21 ZZZZ ZZ00 // 12x + 8y 0000 0001 // D 0001 0100 // 21 - D = 20 ZZZZ ZZ00 // 12x + 8y 0000 0001 // D WWWW WW00 // 21 - D + 12x + 8y = 20 + 12x + 8y therefore zext(21 + 12x + 8y) = (1 + zext(20 + 12x + 8y))<nuw><nsw> This approach could be improved if we move away from using trailing zeroes and use KnownBits instead. For instance, with KnownBits we could have the following picture: i 10 1110...0011 // this is C XX X1XX...XX00 // this is X = (x + y + ...) Notice that some of the bits of X are known ones, also notice that known bits of X are interspersed with unknown bits and not grouped on the rigth or left. We can see at the position i that C(i) and X(i) are both known ones, therefore the (i + 1)th carry bit is guaranteed to be 1 regardless of the bits of C to the right of i. For instance, the C(i - 1) bit only affects the bits of the sum at positions i - 1 and i, and does not influence if the sum is going to wrap or not. Therefore we could split the constant C the following way: i 00 0010...0011 = D 10 1100...0000 = (C - D) Let's compute the KnownBits of (C - D) + X: XX1 1 = carry bit, blanks stand for known zeroes 10 1100...0000 = (C - D) XX X1XX...XX00 = X --- ----------- XX X0XX...XX00 Will this add wrap or not essentially depends on bits of X. Adding D to this sum, however, is guaranteed to not to wrap: 0 X 00 0010...0011 = D sX X0XX...XX00 = (C - D) + X --- ----------- sX XXXX XX11 As could be seen above, adding D preserves the sign bit of (C - D) + X, if any, and has a guaranteed 0 carry out, as expected. The more bits of (C - D) we constrain, the better the transformations introduced here canonicalize expressions as it leaves less freedom to what values the constant part of ((C - D) + x + y + ...) can take. Reviewed By: mzolotukhin, efriedma Differential Revision: https://reviews.llvm.org/D48853 llvm-svn: 337943
* [IndVarSimplify] Ignore unreachable users of truncsMax Kazantsev2018-06-281-0/+47
| | | | | | | If a trunc has a user in a block which is not reachable from entry, we can safely perform trunc elimination as if this user didn't exist. llvm-svn: 335816
* [SimplifyIndVars] Eliminate redundant truncsMax Kazantsev2018-06-193-3/+496
| | | | | | | | | | | | | | | | | | | | | | | This patch adds logic to deal with the following constructions: %iv = phi i64 ... %trunc = trunc i64 %iv to i32 %cmp = icmp <pred> i32 %trunc, %invariant Replacing it with %iv = phi i64 ... %cmp = icmp <pred> i64 %iv, sext/zext(%invariant) In case if it is legal. Specifically, if `%iv` has signed comparison users, it is required that `sext(trunc(%iv)) == %iv`, and if it has unsigned comparison uses then we require `zext(trunc(%iv)) == %iv`. The current implementation bails if `%trunc` has other uses than `icmp`, but in theory we can handle more cases here (e.g. if the user of trunc is bitcast). Differential Revision: https://reviews.llvm.org/D47928 Reviewed By: reames llvm-svn: 335020
* Revert "[SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags"Sanjoy Das2018-06-191-1/+1
| | | | | | | | | | | | | | This reverts r334428. It incorrectly marks some multiplications as nuw. Tim Shen is working on a proper fix. Original commit message: [SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags where safe. Summary: Previously we would add them for adds, but not multiplies. llvm-svn: 335016
* [SimplifyIndVars] Ignore dead usersMax Kazantsev2018-06-136-2/+55
| | | | | | | | | | | | | IndVarSimplify sometimes makes transforms basing on users that are trivially dead. In particular, if DCE wasn't run before it, there may be a dead `sext/zext` in loop that will trigger widening transforms, however it makes no sense to do it. This patch teaches IndVarsSimplify ignore the mist trivial cases of that. Differential Revision: https://reviews.llvm.org/D47974 Reviewed By: sanjoy llvm-svn: 334567
* [SCEV] Add nuw/nsw to mul ops in StrengthenNoWrapFlags where safe.Justin Lebar2018-06-111-1/+1
| | | | | | | | | | | | | Summary: Previously we would add them for adds, but not multiplies. Reviewers: sanjoy Subscribers: llvm-commits, hiraditya Differential Revision: https://reviews.llvm.org/D48038 llvm-svn: 334428
* [DebugInfo] Add DILabel metadata and intrinsic llvm.dbg.label.Shiva Chen2018-05-091-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In order to set breakpoints on labels and list source code around labels, we need collect debug information for labels, i.e., label name, the function label belong, line number in the file, and the address label located. In order to keep these information in LLVM IR and to allow backend to generate debug information correctly. We create a new kind of metadata for labels, DILabel. The format of DILabel is !DILabel(scope: !1, name: "foo", file: !2, line: 3) We hope to keep debug information as much as possible even the code is optimized. So, we create a new kind of intrinsic for label metadata to avoid the metadata is eliminated with basic block. The intrinsic will keep existing if we keep it from optimized out. The format of the intrinsic is llvm.dbg.label(metadata !1) It has only one argument, that is the DILabel metadata. The intrinsic will follow the label immediately. Backend could get the label metadata through the intrinsic's parameter. We also create DIBuilder API for labels to be used by Frontend. Frontend could use createLabel() to allocate DILabel objects, and use insertLabel() to insert llvm.dbg.label intrinsic in LLVM IR. Differential Revision: https://reviews.llvm.org/D45024 Patch by Hsiangkai Wang. llvm-svn: 331841
* [SCEV] Prove implications for SCEVUnknown PhisMax Kazantsev2018-04-041-0/+38
| | | | | | | | | | | | | | | | | This patch teaches SCEV how to prove implications for SCEVUnknown nodes that are Phis. If we need to prove `Pred` for `LHS, RHS`, and `LHS` is a Phi with possible incoming values `L1, L2, ..., LN`, then if we prove `Pred` for `(L1, RHS), (L2, RHS), ..., (LN, RHS)` then we can also prove it for `(LHS, RHS)`. If both `LHS` and `RHS` are Phis from the same block, it is sufficient to prove the predicate for values that come from the same predecessor block. The typical case that it handles is that we sometimes need to prove that `Phi(Len, Len - 1) >= 0` given that `Len > 0`. The new logic was added to `isImpliedViaOperations` and only uses it and non-recursive reasoning to prove the facts we need, so it should not hurt compile time a lot. Differential Revision: https://reviews.llvm.org/D44001 Reviewed By: anna llvm-svn: 329150
* [SCEV] Make exact taken count calculation more optimisticMax Kazantsev2018-03-271-5/+0
| | | | | | | | | | | | | | | | | | | | | Currently, `getExact` fails if it sees two exit counts in different blocks. There is no solid reason to do so, given that we only calculate exact non-taken count for exiting blocks that dominate latch. Using this fact, we can simply take min out of all exits of all blocks to get the exact taken count. This patch makes the calculation more optimistic with enforcing our assumption with asserts. It allows us to calculate exact backedge taken count in trivial loops like for (int i = 0; i < 100; i++) { if (i > 50) break; . . . } Differential Revision: https://reviews.llvm.org/D44676 Reviewed By: fhahn llvm-svn: 328611
* [SCEV] Add one more case in computeConstantDifferenceMax Kazantsev2018-03-271-0/+89
| | | | | | | | | | This patch teaches `computeConstantDifference` handle calculation of constant difference between `(X + C1)` and `(X + C2)` which is `(C2 - C1)`. Differential Revision: https://reviews.llvm.org/D43759 Reviewed By: anna llvm-svn: 328609
* [SCEV] Re-land: Fix isKnownPredicateSerguei Katkov2018-03-191-0/+35
| | | | | | | | | | | | | | | | | This is re-land of https://reviews.llvm.org/rL327362 with a fix and regression test. The crash was due to it is possible that for found MDL loop, LHS or RHS may contain an invariant unknown SCEV which does not dominate the MDL. Please see regression test for an example. Reviewers: sanjoy, mkazantsev, reames Reviewed By: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D44553 llvm-svn: 327822
* Revert [SCEV] Fix isKnownPredicateSerguei Katkov2018-03-131-33/+0
| | | | | | | | It is a revert of rL327362 which causes build bot failures with assert like Assertion `isAvailableAtLoopEntry(RHS, L) && "RHS is not available at Loop Entry"' failed. llvm-svn: 327363
* [SCEV] Fix isKnownPredicateSerguei Katkov2018-03-131-0/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | IsKnownPredicate is updated to implement the following algorithm proposed by @sanjoy and @mkazantsev : isKnownPredicate(Pred, LHS, RHS) { Collect set S all loops on which either LHS or RHS depend. If S is non-empty a. Let PD be the element of S which is dominated by all other elements of S b. Let E(LHS) be value of LHS on entry of PD. To get E(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their entry values. Define E(RHS) in the same way. c. Let B(LHS) be value of L on backedge of PD. To get B(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their backedge values. Define B(RHS) in the same way. d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, so we can assert on that. e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS)) Return true if Pred, L, R is known from ranges, splitting etc. } This is follow-up for https://reviews.llvm.org/D42417. Reviewers: sanjoy, mkazantsev, reames Reviewed By: sanjoy, mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D43507 llvm-svn: 327362
* [NFC] Fix metadata placement in testMax Kazantsev2018-02-151-3/+1
| | | | llvm-svn: 325215
* [SCEV] Favor isKnownViaSimpleReasoning over constant ranges checkMax Kazantsev2018-02-151-0/+32
| | | | | | | | | | | | | | | | | | | | | There is a more powerful but still simple function `isKnownViaSimpleReasoning ` that does constant range check and few more additional checks. We use it some places (e.g. when proving implications) and in some other places we only check constant ranges. Currently, indvar simplifier fails to remove the check in following loop: int inc = ...; for (int i = inc, j = inc - 1; i < 200; ++i, ++j) if (i > j) { ... } This patch replaces all usages of `isKnownPredicateViaConstantRanges` with `isKnownViaSimpleReasoning` to have smarter proofs. In particular, it fixes the case above. Reviewed-By: sanjoy Differential Revision: https://reviews.llvm.org/D43175 llvm-svn: 325214
* Re-enable "[SCEV] Make isLoopEntryGuardedByCond a bit smarter"Max Kazantsev2018-02-071-0/+30
| | | | | | | | | The failures happened because of assert which was overconfident about SCEV's proving capabilities and is generally not valid. Differential Revision: https://reviews.llvm.org/D42835 llvm-svn: 324473
* Revert [SCEV] Make isLoopEntryGuardedByCond a bit smarterSerguei Katkov2018-02-071-30/+0
| | | | | | | | Revert rL324453 commit which causes buildbot failures. Differential Revision: https://reviews.llvm.org/D42835 llvm-svn: 324462
* [SCEV] Make isLoopEntryGuardedByCond a bit smarterMax Kazantsev2018-02-071-0/+30
| | | | | | | | | | | Sometimes `isLoopEntryGuardedByCond` cannot prove predicate `a > b` directly. But it is a common situation when `a >= b` is known from ranges and `a != b` is known from a dominating condition. Thia patch teaches SCEV to sum these facts together and prove strict comparison via non-strict one. Differential Revision: https://reviews.llvm.org/D42835 llvm-svn: 324453
* Re-apply [SCEV] Fix isLoopEntryGuardedByCond usageSerguei Katkov2018-02-051-0/+54
| | | | | | | | | | | | | | | | | ScalarEvolution::isKnownPredicate invokes isLoopEntryGuardedByCond without check that SCEV is available at entry point of the loop. It is incorrect and fixed by patch. To bugs additionally fixed: assert is moved after the check whether loop is not a nullptr. Usage of isLoopEntryGuardedByCond in ScalarEvolution::isImpliedCondOperandsViaNoOverflow is guarded by isAvailableAtLoopEntry. Reviewers: sanjoy, mkazantsev, anna, dorit, reames Reviewed By: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D42417 llvm-svn: 324204
* Revert [SCEV] Fix isLoopEntryGuardedByCond usageSerguei Katkov2018-01-221-54/+0
| | | | | | | It causes buildbot failures. New added assert is fired. It seems not all usages of isLoopEntryGuardedByCond are fixed. llvm-svn: 323079
* [SCEV] Fix isLoopEntryGuardedByCond usageSerguei Katkov2018-01-221-0/+54
| | | | | | | | | | | | ScalarEvolution::isKnownPredicate invokes isLoopEntryGuardedByCond without check that SCEV is available at entry point of the loop. It is incorrect and fixed by patch. Reviewers: sanjoy, mkazantsev, anna, dorit Reviewed By: mkazantsev Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D42165 llvm-svn: 323077
* [SCEV] Fix the movement of insertion point in expander. PR35406.Serguei Katkov2017-12-151-0/+88
| | | | | | | | | | | | We cannot move the insertion point to header if SCEV contains div/rem operations due to they may go over check for zero denominator. Reviewers: sanjoy, mkazantsev, sebpop Reviewed By: sebpop Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D41229 llvm-svn: 320789
* [ScalarEvolution] Fix base condition in isNormalAddRecPHI.Bjorn Pettersson2017-12-141-0/+63
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The function is meant to recurse until it comes upon the phi it's looking for. However, with the current condition, it will recurse until it finds anything _but_ the phi. The function will even fail for simple cases like: %i = phi i32 [ %inc, %loop ], ... ... %inc = add i32 %i, 1 because the base condition will not happen when the phi is recursed to, and the recursion will end with a 'false' result since the previous instruction is a phi. Reviewers: sanjoy, atrick Reviewed By: sanjoy Subscribers: Ka-Ka, bjope, llvm-commits Committing on behalf of: Bevin Hansson (bevinh) Differential Revision: https://reviews.llvm.org/D40946 llvm-svn: 320700
* [IndVars] Fix a bug introduced in r317012Philip Reames2017-12-011-0/+30
| | | | | | | | Turns out we can have comparisons which are indirect users of the induction variable that we can make invariant. In this case, there is no loop invariant value contributing and we'd fail an assert. The test case was found by a java fuzzer and reduced. It's a real cornercase. You have to have a static loop which we've already proven only executes once, but haven't broken the backedge on, and an inner phi whose result can be constant folded by SCEV using exit count reasoning but not proven by isKnownPredicate. To my knowledge, only the fuzzer has hit this case. llvm-svn: 319583
* IndVarSimplify: preserve debug information attached to widened PHI nodes.Adrian Prantl2017-11-021-0/+71
| | | | | | | | | | This fixes PR35015. https://bugs.llvm.org/show_bug.cgi?id=35015 Differential Revision: https://reviews.llvm.org/D39345 llvm-svn: 317282
* [IndVarSimplify] Simplify code using preheader assumptionPhilip Reames2017-10-311-0/+22
| | | | | | | | As noted in the nice block comment, the previous code didn't actually handle multi-entry loops correctly, it just assumed SCEV didn't analyze such loops. Given SCEV has comments to the contrary, that seems a bit suspect. More importantly, the pass actually requires loopsimplify form which ensures a loop-preheader is available. Remove the excessive generaility and shorten the code greatly. Note that we do successfully analyze many multi-entry loops, but we do so by converting them to single entry loops. See the added test case. llvm-svn: 316976
* Revert rL316568 because of sudden performance drop on ARMMax Kazantsev2017-10-271-38/+2
| | | | llvm-svn: 316739
* [SCEV] Enhance SCEVFindUnsafe for divisionMax Kazantsev2017-10-251-2/+38
| | | | | | | | | This patch allows SCEVFindUnsafe algorithm to tread division by any non-positive value as safe. Previously, it could only recognize non-zero constants. Differential Revision: https://reviews.llvm.org/D39228 llvm-svn: 316568
* [SimplifyIndVar] Replace IVUsers with loop invariant whenever possibleHongbin Zheng2017-10-122-39/+88
| | | | | | Differential Revision: https://reviews.llvm.org/D38415 llvm-svn: 315551
* [SimplifyIndVar] Do not fail when we constant fold an IV user to ↵Hongbin Zheng2017-09-292-1/+40
| | | | | | | | | | ConstantPointerNull The type of a SCEVConstant may not match the corresponding LLVM Value. In this case, we skip the constant folding for now. TODO: Replace ConstantInt Zero by ConstantPointerNull llvm-svn: 314531
* [SimplifyIndVar] Constant fold IV usersHongbin Zheng2017-09-272-1/+48
| | | | | | | | | | | | | | | | | | | | | This patch tries to transform cases like: for (unsigned i = 0; i < N; i += 2) { bool c0 = (i & 0x1) == 0; bool c1 = ((i + 1) & 0x1) == 1; } To for (unsigned i = 0; i < N; i += 2) { bool c0 = true; bool c1 = true; } This commit also update test/Transforms/IndVarSimplify/replace-srem-by-urem.ll to prevent constant folding. Differential Revision: https://reviews.llvm.org/D38272 llvm-svn: 314266
* [SimplifyIndvar] Replace the srem used by IV if we can prove both of its ↵Hongbin Zheng2017-09-252-3/+112
| | | | | | | | | | | | operands are non-negative Since now SCEV can handle 'urem', an 'urem' is a better canonical form than an 'srem' because it has well-defined behavior This is a follow up of D34598 Differential Revision: https://reviews.llvm.org/D38072 llvm-svn: 314125
* [SCEV/IndVars] Always compute loop exiting values if the backedge count is 0Sanjoy Das2017-08-011-3/+25
| | | | | | | | | 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
* Re-enable "[IndVars] Canonicalize comparisons between non-negative values ↵Max Kazantsev2017-07-083-3/+101
| | | | | | | | | | | | | | and indvars" The patch was reverted due to a bug. The bug was that if the IV is the 2nd operand of the icmp instruction, then the "Pred" variable gets swapped and differs from the instruction's predicate. In this patch we use the original predicate to do the transformation. Also added a test case that exercises this situation. Differentian Revision: https://reviews.llvm.org/D35107 llvm-svn: 307477
* Revert "Revert "Revert "[IndVars] Canonicalize comparisons between ↵Max Kazantsev2017-07-063-55/+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-063-3/+55
| | | | | | | | | | | | | 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
* [IndVarSimplify] Add AShr exact flags using induction variables ranges.David Green2017-07-051-0/+84
| | | | | | | | | | This adds exact flags to AShr/LShr flags where we can statically prove it is valid using the range of induction variables. This allows further optimisations to remove extra loads. Differential Revision: https://reviews.llvm.org/D34207 llvm-svn: 307157
* Revert "[IndVars] Canonicalize comparisons between non-negative values and ↵Max Kazantsev2017-07-053-55/+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-053-3/+55
| | | | | | | | | | | | | | | | | -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] Make MulOpsInlineThreshold lower to avoid excessive compilation timeMax Kazantsev2017-06-211-0/+87
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [IndVars] Add an option to be able to disable LFTRSerguei Katkov2017-06-091-0/+28
| | | | | | | | | | | | This change adds an option disable-lftr to be able to disable Linear Function Test Replace optimization. By default option is off so current behavior is not changed. Reviewers: reames, sanjoy, wmi, andreadb, apilipenko Reviewed By: sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D33979 llvm-svn: 305055
* ConstantFold: Fold getelementptr (i32, i32* null, i64 undef) to null.Daniel Berlin2017-05-081-1/+1
| | | | | | | | Transforms/IndVarSimplify/2011-10-27-lftrnull will fail if this regresses. Transforms/GVN/PRE/2011-06-01-NonLocalMemdepMiscompile.ll has been changed to still test what it was trying to test. llvm-svn: 302446
* Add address space mangling to lifetime intrinsicsMatt Arsenault2017-04-101-4/+4
| | | | | | In preparation for allowing allocas to have non-0 addrspace. llvm-svn: 299876
* [SimplifyIndvar] Replace the sdiv used by IV if we can prove both of its ↵Hongbin Zheng2017-03-301-0/+130
| | | | | | | | | | operands are non-negative Since there is no sdiv in SCEV, an 'udiv' is a better canonical form than an 'sdiv' as the user of induction variable Differential Revision: https://reviews.llvm.org/D31488 llvm-svn: 299118
* AMDGPU: Mark all unspecified CC functions in tests as amdgpu_kernelMatt Arsenault2017-03-211-3/+3
| | | | | | | | | | | | Currently the default C calling convention functions are treated the same as compute kernels. Make this explicit so the default calling convention can be changed to a non-kernel. Converted with perl -pi -e 's/define void/define amdgpu_kernel void/' on the relevant test directories (and undoing in one place that actually wanted a non-kernel). llvm-svn: 298444
* [ValueTracking] Don't do an unchecked shift in ComputeNumSignBitsSanjoy Das2017-02-251-0/+39
| | | | | | | | | | | | | | | | | | | | | | Summary: Previously we used to return a bogus result, 0, for IR like `ashr %val, -1`. I've also added an assert checking that `ComputeNumSignBits` at least returns 1. That assert found an already checked in test case where we were returning a bad result for `ashr %val, -1`. Fixes PR32045. Reviewers: spatel, majnemer Reviewed By: spatel, majnemer Subscribers: efriedma, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D30311 llvm-svn: 296273
* opt: Rename -default-data-layout flag to -data-layout and make it always ↵Peter Collingbourne2017-02-171-2/+2
| | | | | | | | | | override the layout. There isn't much point in a flag that only works if the data layout is empty. Differential Revision: https://reviews.llvm.org/D30014 llvm-svn: 295468
* [IndVars] Change the order to compute WidenAddRec in widenIVUse.Wei Mi2016-11-152-2/+63
| | | | | | | | | | | | | | | | When both WidenIV::getWideRecurrence and WidenIV::getExtendedOperandRecurrence return non-null but different WideAddRec, if getWideRecurrence is called before getExtendedOperandRecurrence, we won't bother to call getExtendedOperandRecurrence again. But As we know it is possible that after SCEV folding, we cannot prove the legality using the SCEVAddRecExpr returned by getWideRecurrence. Meanwhile if getExtendedOperandRecurrence returns non-null WideAddRec, we know for sure that it is legal to do widening for current instruction. So it is better to put getExtendedOperandRecurrence before getWideRecurrence, which will increase the chance of successful widening. Differential Revision: https://reviews.llvm.org/D26059 llvm-svn: 286987
* [IndVarSimplify] Teach calculatePostIncRange to take guards into accountArtur Pilipenko2016-10-191-0/+114
| | | | | | | | Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D25739 llvm-svn: 284632
OpenPOWER on IntegriCloud