summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Revert "[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC)."Florian Hahn2020-01-041-1/+1
| | | | | This reverts commit 51ef53f3bd23559203fe9af82ff2facbfedc1db3, as it breaks some bots.
* [SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).Florian Hahn2020-01-041-1/+1
| | | | | | | | | | | | SCEVExpander modifies the underlying function so it is more suitable in Transforms/Utils, rather than Analysis. This allows using other transform utils in SCEVExpander. Reviewers: sanjoy.google, efriedma, reames Reviewed By: sanjoy.google Differential Revision: https://reviews.llvm.org/D71537
* [SimplifyIndVar] Simplify non-overflowing saturating add/subNikita Popov2019-06-151-0/+24
| | | | | | | | | | | If we can detect that saturating math that depends on an IV cannot overflow, replace it with simple math. This is similar to the CVP optimization from D62703, just based on a different underlying analysis (SCEV vs LVI) that catches different cases. Differential Revision: https://reviews.llvm.org/D62792 llvm-svn: 363489
* Generalize icmp matching in IndVars' eliminateTruncPhilip Reames2019-06-111-14/+15
| | | | | | | | We were only matching RHS being a loop invariant value, not the inverse. Since there's nothing which appears to canonicalize loop invariant values to RHS, this means we missed cases. Differential Revision: https://reviews.llvm.org/D63112 llvm-svn: 363108
* [SimplifyIndVar] Refactor overflow check elimination code; NFCNikita Popov2019-06-011-97/+43
| | | | | | | | | | | Extract a willNotOverflow() helper function that is shared between eliminateOverflowIntrinsic() and strengthenOverflowingOperation(). Use WithOverflowInst for the former. We'll be able to reuse the same code for saturating intrinsics as well. llvm-svn: 362305
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* [IndVars] Drop "exact" flag from lshr and udiv when substituting their argsMax Kazantsev2018-10-111-0/+9
| | | | | | | | | | | | There is a transform that may replace `lshr (x+1), 1` with `lshr x, 1` in case if it can prove that the result will be the same. However the initial instruction might have an `exact` flag set, and it now should be dropped unless we prove that it may hold. Incorrectly set `exact` attribute may then produce poison. Differential Revision: https://reviews.llvm.org/D53061 Reviewed By: sanjoy llvm-svn: 344223
* [NFC] Make a variable constMax Kazantsev2018-10-101-1/+1
| | | | llvm-svn: 344113
* Remove trailing spaceFangrui Song2018-07-301-1/+1
| | | | | | sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h} llvm-svn: 338293
* [SimplifyIndVar] Canonicalize comparisons to unsigned while eliminating truncsMax Kazantsev2018-07-271-2/+23
| | | | | | | | | | | 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
* [IndVarSimplify] Ignore unreachable users of truncsMax Kazantsev2018-06-281-0/+4
| | | | | | | 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-191-0/+92
| | | | | | | | | | | | | | | | | | | | | | | 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
* [SimplifyIndVars] Ignore dead usersMax Kazantsev2018-06-131-0/+10
| | | | | | | | | | | | | 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
* [NFC] Use variable instead of accessing pair many timesMax Kazantsev2018-06-071-6/+6
| | | | llvm-svn: 334173
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-13/+14
| | | | | | | | | | | | | | | | The DEBUG() macro is very generic so it might clash with other projects. The renaming was done as follows: - git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g' - git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM - Manual change to APInt - Manually chage DOCS as regex doesn't match it. In the transition period the DEBUG() macro is still present and aliased to the LLVM_DEBUG() one. Differential Revision: https://reviews.llvm.org/D43624 llvm-svn: 332240
* Remove redundant includes from lib/Transforms.Michael Zolotukhin2017-12-131-2/+0
| | | | llvm-svn: 320628
* [IndVars] Fix a bug introduced in r317012Philip Reames2017-12-011-3/+13
| | | | | | | | 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
* Revert 317016 and 317048Philip Reames2017-11-011-44/+50
| | | | | | The former appears to have introduced a miscompile in a stage2 clang build. Revert so I can investigate offline. llvm-svn: 317116
* [SimplifyIndVar] Inline makIVComparisonInvariant to eleminate code ↵Philip Reames2017-10-311-51/+29
| | | | | | | | duplication [NFC] This formulation might be slightly slower since I eagerly compute the cheap replacements. If anyone sees this having a compile time impact, let me know and I'll use lazy population instead. llvm-svn: 317048
* [IndVarSimplify] Extract wrapper around SE-.isLoopInvariantPredicate [NFC]Philip Reames2017-10-311-17/+33
| | | | | | This an intermediate state, the next patch will re-inline the markLoopInvariantPredicate function to reduce code duplication. llvm-svn: 317016
* [IndVarSimplify] Simplify code using a dictionaryPhilip Reames2017-10-311-16/+8
| | | | | | Possibly very slightly slower, but this code is not performance critical and the readability benefit alone is huge. llvm-svn: 317012
* [IndVarSimplify] Simplify code using preheader assumptionPhilip Reames2017-10-311-44/+6
| | | | | | | | 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
* [SimplifyIndVar] Extract out invariant expression handlingPhilip Reames2017-10-311-82/+107
| | | | | | | | Previously, the code returned early from the *function* when it couldn't find a free expansion, it should be returning from the *transform*. I don't have a test case, noticed this via inspection. As a follow up, I'm going to revisit the logic in the extract function. I think that essentially the whole helper routine can be replaced with SCEVExpander, but I wanted to do that in a series of separate commits. llvm-svn: 316974
* Undo accidental commitPhilip Reames2017-10-311-237/+82
| | | | | | These files shouldn't have been submitted in 316967 llvm-svn: 316968
* [CGP] Fix crash on i96 bit multiplyPhilip Reames2017-10-301-82/+237
| | | | | | | | Issue found by llvm-isel-fuzzer on OSS fuzz, https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=3725 If anyone actually cares about > 64 bit arithmetic, there's a lot more to do in this area. There's a bunch of obviously wrong code in the same function. I don't have the time to fix all of them and am just using this to understand what the workflow for fixing fuzzer cases might look like. llvm-svn: 316967
* [SimplifyIndVars] Shorten code by using SCEV helper [NFC]Philip Reames2017-10-261-7/+4
| | | | llvm-svn: 316709
* [SimplifyIndVar] Replace IVUsers with loop invariant whenever possibleHongbin Zheng2017-10-121-32/+54
| | | | | | 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-291-10/+17
| | | | | | | | | | 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-271-0/+30
| | | | | | | | | | | | | | | | | | | | | 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] Minor change to refine r314125, NFCHongbin Zheng2017-09-251-1/+1
| | | | llvm-svn: 314130
* [SimplifyIndvar] Replace the srem used by IV if we can prove both of its ↵Hongbin Zheng2017-09-251-38/+80
| | | | | | | | | | | | 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
* Re-enable "[IndVars] Canonicalize comparisons between non-negative values ↵Max Kazantsev2017-07-081-0/+11
| | | | | | | | | | | | | | 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-061-4/+0
| | | | | | | | | 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-0/+4
| | | | | | | | | | | | | 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-2/+34
| | | | | | | | | | 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-051-4/+0
| | | | | | | | | | | 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-0/+4
| | | | | | | | | | | | | | | | | -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-5/+5
| | | | | | | | | | | | | | | | 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
* [ScalarEvolution] Apply Depth limit to getMulExprMax Kazantsev2017-06-151-7/+7
| | | | | | | | | | | | | | | | | | | | | 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
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-4/+4
| | | | | | This relands r301424. llvm-svn: 301812
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-4/+4
| | | | | | | | | | | | Commits were: "Use WeakVH instead of WeakTrackingVH in AliasSetTracker's UnkownInsts" "Add a new WeakVH value handle; NFC" "Rename WeakVH to WeakTrackingVH; NFC" The changes assumed pointers are 8 byte aligned on all architectures. llvm-svn: 301429
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-04-261-4/+4
| | | | | | | | | | | | | | | | Summary: I plan to use WeakVH to mean "nulls itself out on deletion, but does not track RAUW" in a subsequent commit. Reviewers: dblaikie, davide Reviewed By: davide Subscribers: arsenm, mehdi_amini, mcrosier, mzolotukhin, jfb, llvm-commits, nhaehnle Differential Revision: https://reviews.llvm.org/D32266 llvm-svn: 301424
* [SimplifyIndvar] Replace the sdiv used by IV if we can prove both of its ↵Hongbin Zheng2017-03-301-4/+38
| | | | | | | | | | 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
* [IndVars] Remove -liv-reduceSanjoy Das2016-06-051-72/+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/+107
| | | | | | | | | | | | | | | | | | | 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
* [NFC] Header cleanupMehdi Amini2016-04-181-1/+0
| | | | | | | | | | | | | | Removed some unused headers, replaced some headers with forward class declarations. Found using simple scripts like this one: clear && ack --cpp -l '#include "llvm/ADT/IndexedMap.h"' | xargs grep -L 'IndexedMap[<]' | xargs grep -n --color=auto 'IndexedMap' Patch by Eugene Kosov <claprix@yandex.ru> Differential Revision: http://reviews.llvm.org/D19219 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 266595
* This reverts commit r265913 and r265912Sanjoy Das2016-04-111-107/+0
| | | | | | | | | See PR27315 r265913: "[IndVars] Eliminate op.with.overflow when possible" r265912: "[SCEV] See through op.with.overflow intrinsics" llvm-svn: 265950
* [IndVars] Eliminate op.with.overflow when possibleSanjoy Das2016-04-101-0/+107
| | | | | | | | | | | | | | | 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. Reviewers: atrick, regehr Subscribers: sanjoy, mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D18685 llvm-svn: 265913
* [IndVars] Make the fix for PR26973 more obvious; NFCISanjoy Das2016-03-181-3/+42
| | | | llvm-svn: 263828
* [IndVars] Pass the right loop to isLoopInvariantPredicateSanjoy Das2016-03-181-3/+2
| | | | | | | | | | | The loop on IVOperand's incoming values assumes IVOperand to be an induction variable on the loop over which `S Pred X` is invariant; otherwise loop invariant incoming values to IVOperand are not guaranteed to dominate the comparision. This fixes PR26973. llvm-svn: 263827
OpenPOWER on IntegriCloud