summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/IndVarSimplify
Commit message (Collapse)AuthorAgeFilesLines
* [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
* [IndVarSimplify] Use control-dependent range information to prove non-negativityArtur Pilipenko2016-10-191-0/+175
| | | | | | | | | | | | | | | | | | | | | | | | | | | | This change is motivated by the case when IndVarSimplify doesn't widen a comparison of IV increment because it can't prove IV increment being non-negative. We end up with a redundant trunc of the widened increment on this example. for.body: %i = phi i32 [ %start, %for.body.lr.ph ], [ %i.inc, %for.inc ] %within_limits = icmp ult i32 %i, 64 br i1 %within_limits, label %continue, label %for.end continue: %i.i64 = zext i32 %i to i64 %arrayidx = getelementptr inbounds i32, i32* %base, i64 %i.i64 %val = load i32, i32* %arrayidx, align 4 br label %for.inc for.inc: %i.inc = add nsw nuw i32 %i, 1 %cmp = icmp slt i32 %i.inc, %limit br i1 %cmp, label %for.body, label %for.end There is a range check inside of the loop which guarantees the IV to be non-negative. NSW on the increment guarantees that the increment is also non-negative. Teach IndVarSimplify to use the range check to prove non-negativity of loop increments. Reviewed By: sanjoy Differential Revision: https://reviews.llvm.org/D25738 llvm-svn: 284629
* Wisely choose sext or zext when widening IV.Evgeny Stupachenko2016-09-281-0/+270
| | | | | | | | | | | | Summary: The patch fixes regression caused by two earlier patches D18777 and D18867. Reviewers: reames, sanjoy Differential Revision: http://reviews.llvm.org/D24280 From: Li Huang llvm-svn: 282650
* Revert -r278269 [IndVarSimplify] Eliminate zext of a signed IV when the IV ↵Artur Pilipenko2016-08-221-82/+0
| | | | | | | | | | is known to be non-negative This change needs to be reverted in order to revert -r278267 which cause performance regression on MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt from LNT and some other bechmarks. See comments on https://reviews.llvm.org/D18777 for details. llvm-svn: 279432
* [IndVars] Ignore (s|z)exts that don't extend the induction variableSanjoy Das2016-08-131-0/+20
| | | | | | | | | | | | | | | | | | `IVVisitor::visitCast` used to have the invariant that if the instruction it was passed was a sext or zext instruction, the result of the instruction would be wider than the induction variable. This is no longer true after rL275037, so this change teaches `IndVarSimplify` s implementation of `IVVisitor::visitCast` to work with the relaxed invariant. A corresponding change to SimplifyIndVar to preserve the said invariant after rL275037 would also work, but given how `IVVisitor::visitCast` is spelled (no indication of said invariant), I figured the current fix is cleaner. Fixes PR28935. llvm-svn: 278584
* Extend trip count instead of truncating IV in LFTR, when legalEhsan Amiri2016-08-114-7/+168
| | | | | | | | | | | | | | | | | When legal, extending trip count in the loop control logic generates better code compared to truncating IV. This is because (1) extending trip count is a loop invariant operation (see genLoopLimit where we prove trip count is loop invariant). (2) Scalar Evolution seems to have problems understanding trunc when computing loop trip count. So removing them allows better analysis performed in Scalar Evolution. (In particular this fixes PR 28363 which is the motivation for this change). I am not going to perform any performance test. Any degradation caused by this should be an indication of a bug elsewhere. To prove legality, we rely on SCEV to prove zext(trunc(IV)) == IV (or similarly for sext). If this holds, we can prove equivalence of trunc(IV)==ExitCnt (1) and IV == zext(ExitCnt). Simply take zext of boths sides of (1) and apply the proven equivalence. This commit contains changes in a newly added testcase which was not included in the previous commit (which was reverted later on). https://reviews.llvm.org/D23075 llvm-svn: 278421
* revert 278334Ehsan Amiri2016-08-113-163/+2
| | | | llvm-svn: 278337
* Extend trip count instead of truncating IV in LFTR, when legalEhsan Amiri2016-08-113-2/+163
| | | | | | | | | | | | | | | When legal, extending trip count in the loop control logic generates better code compared to truncating IV. This is because (1) extending trip count is a loop invariant operation (see genLoopLimit where we prove trip count is loop invariant). (2) Scalar Evolution seems to have problems understanding trunc when computing loop trip count. So removing them allows better analysis performed in Scalar Evolution. (In particular this fixes PR 28363 which is the motivation for this change). I am not going to perform any performance test. Any degradation caused by this should be an indication of a bug elsewhere. To prove legality, we rely on SCEV to prove zext(trunc(IV)) == IV (or similarly for sext). If this holds, we can prove equivalence of trunc(IV)==ExitCnt (1) and IV == zext(ExitCnt). Simply take zext of boths sides of (1) and apply the proven equivalence. https://reviews.llvm.org/D23075 llvm-svn: 278334
* [IndVarSimplify] Eliminate zext of a signed IV when the IV is known to be ↵Andrew Kaylor2016-08-101-0/+82
| | | | | | | | | | non-negative Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18867 llvm-svn: 278269
* [IndVars] Un-grepify test; NFCSanjoy Das2016-08-0324-37/+87
| | | | | | | | Some of these tests need to be cleaned up further to make it obvious what they're testing, but as a first step remove all instances of "grep". llvm-svn: 277648
* Upgrade other old memset/memcpy signatures in tests causing buildbot ↵Artur Pilipenko2016-06-231-2/+0
| | | | | | failures with rL273568. llvm-svn: 273580
* [PM] Port IndVarSimplify to the new pass managerSanjoy Das2016-06-053-0/+3
| | | | | | | | | | | | | | | | | Summary: There are some rough corners, since the new pass manager doesn't have (as far as I can tell) LoopSimplify and LCSSA, so I've updated the tests to run them separately in the old pass manager in the lit tests. We also don't have an equivalent for AU.setPreservesCFG() in the new pass manager, so I've left a FIXME. Reviewers: bogner, chandlerc, davide Subscribers: sanjoy, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20783 llvm-svn: 271846
* [IndVars] Remove -liv-reduceSanjoy Das2016-06-051-56/+0
| | | | | | | | | | It is an off-by-default option that no one seems to use[0], and given that SCEV directly understands the overflow instrinsics there is no real need for it anymore. [0]: http://lists.llvm.org/pipermail/llvm-dev/2016-April/098181.html llvm-svn: 271845
* [IndVars] Eliminate op.with.overflow when possible (re-apply)Sanjoy Das2016-05-291-0/+137
| | | | | | | | | | | | | | | | | | | Summary: If we can prove that an op.with.overflow intrinsic does not overflow, we can get rid of the intrinsic, and replace it with non-wrapping arithmetic. This was first checked in at r265913 but reverted in r265950 because it exposed some issues around how SCEV handled post-inc add recurrences. Those issues have now been fixed. Reviewers: atrick, regehr Subscribers: sanjoy, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D18685 llvm-svn: 271153
* [SCEV] Don't always add no-wrap flags to post-inc add recsSanjoy Das2016-05-291-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Fixes PR27315. The post-inc version of an add recurrence needs to "follow the same rules" as a normal add or subtract expression. Otherwise we miscompile programs like ``` int main() { int a = 0; unsigned a_u = 0; volatile long last_value; do { a_u += 3; last_value = (long) ((int) a_u); if (will_add_overflow(a, 3)) { // Leave, and don't actually do the increment, so no UB. printf("last_value = %ld\n", last_value); exit(0); } a += 3; } while (a != 46); return 0; } ``` This patch changes SCEV to put no-wrap flags on post-inc add recurrences only when the poison from a potential overflow will go ahead to cause undefined behavior. To avoid regressing performance too much, I've assumed infinite loops without side effects is undefined behavior to prove poison<->UB equivalence in more cases. This isn't ideal, but is not new to LLVM as a whole, and far better than the situation I'm trying to fix. llvm-svn: 271151
OpenPOWER on IntegriCloud