summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Fix a bug w/inbounds invalidation in LFTR (recommit)Philip Reames2019-06-171-11/+85
| | | | | | | | | | | | | | | | | | Recommit r363289 with a bug fix for crash identified in pr42279. Issue was that a loop exit test does not have to be an icmp, leading to a null dereference crash when new logic was exercised for that case. Test case previously committed in r363601. Original commit comment follows: This contains fixes for two cases where we might invalidate inbounds and leave it stale in the IR (a miscompile). Case 1 is when switching to an IV with no dynamically live uses, and case 2 is when doing pre-to-post conversion on the same pointer type IV. The basic scheme used is to prove that using the given IV (pre or post increment forms) would have to already trigger UB on the path to the test we're modifying. As such, our potential UB triggering use does not change the semantics of the original program. As was pointed out in the review thread by Nikita, this is defending against a separate issue from the hasConcreteDef case. This is about poison, that's about undef. Unfortunately, the two are different, see Nikita's comment for a fuller explanation, he explains it well. (Note: I'm going to address Nikita's last style comment in a separate commit just to minimize chance of subtle bugs being introduced due to typos.) Differential Revision: https://reviews.llvm.org/D62939 llvm-svn: 363613
* Revert Fix a bug w/inbounds invalidation in LFTRFlorian Hahn2019-06-141-83/+11
| | | | | | | | | Reverting because it breaks a green dragon build: http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/18208 This reverts r363289 (git commit eb88badff96dacef8fce3f003dec34c2ef6900bf) llvm-svn: 363427
* Revert [LFTR] Stylistic cleanup as suggested in last review comment of ↵Florian Hahn2019-06-141-9/+9
| | | | | | | | | | | D62939 [NFC] Reverting because it depends on r363289, which breaks a green dragon build: http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/18208 This reverts r363292 (git commit 42a3fc133d3544b5c0c032fe99c6e8a469a836c2) llvm-svn: 363426
* Revert [LFTR] Rename variable to minimize confusion [NFC]Florian Hahn2019-06-141-15/+18
| | | | | | | | | | Reverting because it depends on r363289, which breaks a green dragon build: http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/18208 This reverts r363293 (git commit c37be29634214fb1cb4c823840bffc31e5ebfe40) llvm-svn: 363425
* [LFTR] Rename variable to minimize confusion [NFC]Philip Reames2019-06-131-18/+15
| | | | | | As pointed out by Nikita in D62625, BackedgeTakenCount is generally used to refer to the backedge taken count of the loop. A conditional backedge taken count - one which only applies if a particular exit is taken - is called a ExitCount in SCEV code, so be consistent here. llvm-svn: 363293
* [LFTR] Stylistic cleanup as suggested in last review comment of D62939 [NFC]Philip Reames2019-06-131-9/+9
| | | | llvm-svn: 363292
* Fix a bug w/inbounds invalidation in LFTRPhilip Reames2019-06-131-11/+83
| | | | | | | | | | | | | | This contains fixes for two cases where we might invalidate inbounds and leave it stale in the IR (a miscompile). Case 1 is when switching to an IV with no dynamically live uses, and case 2 is when doing pre-to-post conversion on the same pointer type IV. The basic scheme used is to prove that using the given IV (pre or post increment forms) would have to already trigger UB on the path to the test we're modifying. As such, our potential UB triggering use does not change the semantics of the original program. As was pointed out in the review thread by Nikita, this is defending against a separate issue from the hasConcreteDef case. This is about poison, that's about undef. Unfortunately, the two are different, see Nikita's comment for a fuller explanation, he explains it well. (Note: I'm going to address Nikita's last style comment in a separate commit just to minimize chance of subtle bugs being introduced due to typos.) Differential Revision: https://reviews.llvm.org/D62939 llvm-svn: 363289
* [IndVars] Extend diagnostic -replexitval flag w/ability to bypass hard use ↵Philip Reames2019-06-121-2/+5
| | | | | | | hueristic Note: This does mean that "always" is now more powerful than it was. llvm-svn: 363196
* [LFTR] Use recomputed BE countPhilip Reames2019-06-101-9/+1
| | | | | | | | | | | | This was discussed as part of D62880. The basic thought is that computing BE taken count after widening should produce (on average) an equally good backedge taken count as the one before widening. Since there's only one test in the suite which is impacted by this change, and it's essentially equivelent codegen, that seems to be a reasonable assertion. This change was separated from r362971 so that if this turns out to be problematic, the triggering piece is obvious and easily revertable. For the nestedIV example from elim-extend.ll, we end up with the following BE counts: BEFORE: (-2 + (-1 * %innercount) + %limit) AFTER: (-1 + (sext i32 (-1 + %limit) to i64) + (-1 * (sext i32 %innercount to i64))<nsw>) Note that before is an i32 type, and the after is an i64. Truncating the i64 produces the i32. llvm-svn: 362975
* Prepare for multi-exit LFTR [NFC]Philip Reames2019-06-101-65/+77
| | | | | | | | | | | | | | | | This change does the plumbing to wire an ExitingBB parameter through the LFTR implementation, and reorganizes the code to work in terms of a set of individual loop exits. Most of it is fairly obvious, but there's one key complexity which makes it worthy of consideration. The actual multi-exit LFTR patch is in D62625 for context. Specifically, it turns out the existing code uses the backedge taken count from before a IV is widened. Oddly, we can end up with a different (more expensive, but semantically equivelent) BE count for the loop when requerying after widening. For the nestedIV example from elim-extend, we end up with the following BE counts: BEFORE: (-2 + (-1 * %innercount) + %limit) AFTER: (-1 + (sext i32 (-1 + %limit) to i64) + (-1 * (sext i32 %innercount to i64))<nsw>) This is the only test in tree which seems sensitive to this difference. The actual result of using the wider BETC on this example is that we actually produce slightly better code. :) In review, we decided to accept that test change. This patch is structured to preserve the old behavior, but a separate change will immediate follow with the behavior change. (I wanted it separate for problem attribution purposes.) Differential Revision: https://reviews.llvm.org/D62880 llvm-svn: 362971
* [IndVarSimplify] Fixup nowrap flags during LFTR (PR31181)Nikita Popov2019-06-011-0/+21
| | | | | | | | | | | | | | | | | | | | | | | | Fix for https://bugs.llvm.org/show_bug.cgi?id=31181 and partial fix for LFTR poison handling issues in general. When LFTR moves a condition from pre-inc to post-inc, it may now depend on value that is poison due to nowrap flags. To avoid this, we clear any nowrap flag that SCEV cannot prove for the post-inc addrec. Additionally, LFTR may switch to a different IV that is dynamically dead and as such may be arbitrarily poison. This patch will correct nowrap flags in some but not all cases where this happens. This is related to the adoption of IR nowrap flags for the pre-inc addrec. (See some of the switch_to_different_iv tests, where flags are not dropped or insufficiently dropped.) Finally, there are likely similar issues with the handling of GEP inbounds, but we don't have a test case for this yet. Differential Revision: https://reviews.llvm.org/D60935 llvm-svn: 362292
* [LFTR] Strengthen assertions in genLoopLimit [NFCI]Philip Reames2019-05-171-3/+3
| | | | llvm-svn: 360978
* [IndVars] Don't reimplement Loop::isLoopInvariant [NFC]Philip Reames2019-05-171-28/+17
| | | | | | Using dominance vs a set membership check is indistinguishable from a compile time perspective, and the two queries return equivelent results. Simplify code by using the existing function. llvm-svn: 360976
* [LFTR] Factor out a helper function for readability purpose [NFC]Philip Reames2019-05-171-24/+31
| | | | llvm-svn: 360972
* Clarify comments on helpers used by LFTR [NFC]Philip Reames2019-05-171-16/+15
| | | | | | I'm slowly wrapping my head around this code, and am making comment improvements where I can. llvm-svn: 360968
* Fix a release mode warning introduced in r360694Philip Reames2019-05-141-3/+1
| | | | llvm-svn: 360696
* [IndVars] Extend reasoning about loop invariant exits to non-header blocksPhilip Reames2019-05-141-7/+9
| | | | | | Noticed while glancing through the code for other reasons. The extension is trivial enough, decided to just do it. llvm-svn: 360694
* [IndVars] Fix corner case with unreachable Phi inputs. PR40454Max Kazantsev2019-02-121-6/+20
| | | | | | | | | | | | | | | Logic in `getInsertPointForUses` doesn't account for a corner case when `Def` only comes to a Phi user from unreachable blocks. In this case, the incoming value may be arbitrary (and not even available in the input block) and break the loop-related invariants that are asserted below. In fact, if we encounter this situation, no IR modification is needed. This Phi will be simplified away with nearest cleanup. Differential Revision: https://reviews.llvm.org/D58045 Reviewed By: spatel llvm-svn: 353816
* [opaque pointer types] Pass value type to GetElementPtr creation.James Y Knight2019-02-011-1/+2
| | | | | | | | | This cleans up all GetElementPtr creation in LLVM to explicitly pass a value type rather than deriving it from the pointer's element-type. Differential Revision: https://reviews.llvm.org/D57173 llvm-svn: 352913
* 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
* Return "[IndVars] Smart hard uses detection"Max Kazantsev2018-11-081-13/+26
| | | | | | | | | | The patch has been reverted because it ended up prohibiting propagation of a constant to exit value. For such values, we should skip all checks related to hard uses because propagating a constant is always profitable. Differential Revision: https://reviews.llvm.org/D53691 llvm-svn: 346397
* Revert "[IndVars] Smart hard uses detection"Max Kazantsev2018-11-061-26/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This reverts commit 2f425e9c7946b9d74e64ebbfa33c1caa36914402. It seems that the check that we still should do the transform if we know the result is constant is missing in this code. So the logic that has been deleted by this change is still sometimes accidentally useful. I revert the change to see what can be done about it. The motivating case is the following: @Y = global [400 x i16] zeroinitializer, align 1 define i16 @foo() { entry: br label %for.body for.body: ; preds = %entry, %for.body %i = phi i16 [ 0, %entry ], [ %inc, %for.body ] %arrayidx = getelementptr inbounds [400 x i16], [400 x i16]* @Y, i16 0, i16 %i store i16 0, i16* %arrayidx, align 1 %inc = add nuw nsw i16 %i, 1 %cmp = icmp ult i16 %inc, 400 br i1 %cmp, label %for.body, label %for.end for.end: ; preds = %for.body %inc.lcssa = phi i16 [ %inc, %for.body ] ret i16 %inc.lcssa } We should be able to figure out that the result is constant, but the patch breaks it. Differential Revision: https://reviews.llvm.org/D51584 llvm-svn: 346198
* [IndVars] Smart hard uses detectionMax Kazantsev2018-11-011-13/+26
| | | | | | | | | | | | | | | | When rewriting loop exit values, IndVars considers this transform not profitable if the loop instruction has a loop user which it believes cannot be optimized away. In current implementation only calls that immediately use the instruction are considered as such. This patch extends the definition of "hard" users to any side-effecting instructions (which usually cannot be optimized away from the loop) and also allows handling of not just immediate users, but use chains. Differentlai Revision: https://reviews.llvm.org/D51584 Reviewed By: etherzhhb llvm-svn: 345814
* [IndVars] Strengthen restricton in rewriteLoopExitValuesMax Kazantsev2018-10-311-28/+7
| | | | | | | | | | | | | | | | | | | | For some unclear reason rewriteLoopExitValues considers recalculation after the loop profitable if it has some "soft uses" outside the loop (i.e. any use other than call and return), even if we have proved that it has a user inside the loop which we think will not be optimized away. There is no existing unit test that would explain this. This patch provides an example when rematerialisation of exit value is not profitable but it passes this check due to presence of a "soft use" outside the loop. It makes no sense to recalculate value on exit if we are going to compute it due to some irremovable within the loop. This patch disallows applying this transform in the described situation. Differential Revision: https://reviews.llvm.org/D51581 Reviewed By: etherzhhb llvm-svn: 345708
* [IndVars] Remove unreasonable checks in rewriteLoopExitValuesMax Kazantsev2018-09-181-11/+5
| | | | | | | | | | | A piece of logic in rewriteLoopExitValues has a weird check on number of users which allowed an unprofitable transform in case if an instruction has more than 6 users. Differential Revision: https://reviews.llvm.org/D51404 Reviewed By: etherzhhb llvm-svn: 342444
* [NFC] Turn unsigned counters into boolean flagsMax Kazantsev2018-09-171-8/+13
| | | | llvm-svn: 342360
* [IndVars][NFC] Refactor to make modifications of Changed transparentMax Kazantsev2018-09-111-44/+47
| | | | | | | | | | | | | | | | | IndVarSimplify's design is somewhat odd in the way how it reports that some transform has made a change. It has a `Changed` field which can be set from within any function, which makes it hard to track whether or not it was set properly after a transform was made. It leads to oversights in setting this flag where needed, see example in PR38855. This patch removes the `Changed` field, turns it into a local and unifies the signatures of all relevant transform functions to return boolean value which designates whether or not this transform has made a change. Differential Revision: https://reviews.llvm.org/D51850 Reviewed By: skatkov llvm-svn: 341893
* [IndVars] Set Changed if rewriteFirstIterationLoopExitValues changes IR. PR38863Max Kazantsev2018-09-101-3/+6
| | | | | | | | | | | Currently, `rewriteFirstIterationLoopExitValues` does not set Changed flag even if it makes changes in the IR. There is no clear evidence that it can cause a crash, but it looks highly suspicious and likely invalid. Differential Revision: https://reviews.llvm.org/D51779 Reviewed By: skatkov llvm-svn: 341779
* [IndVars] Set Changed if sinkUnusedInvariants changes IR. PR38863Max Kazantsev2018-09-101-5/+9
| | | | | | | | | | | Currently, `sinkUnusedInvariants` does not set Changed flag even if it makes changes in the IR. There is no clear evidence that it can cause a crash, but it looks highly suspicious and likely invalid. Differential Revision: https://reviews.llvm.org/D51777 Reviewed By: skatkov llvm-svn: 341777
* [SimplifyIndVar] Avoid generating truncate instructions with non-hoisted ↵Abderrazek Zaafrani2018-09-071-0/+152
| | | | | | | | Laod operand. Differential Revision: https://reviews.llvm.org/D49151 llvm-svn: 341726
* [IndVars] Set Changed when we delete dead instructions. PR38855Max Kazantsev2018-09-071-1/+1
| | | | | | | | | | | IndVars does not set `Changed` flag when it eliminates dead instructions. As result, it may make IR modifications and report that it has done nothing. It leads to inconsistent preserved analyzes results. Differential Revision: https://reviews.llvm.org/D51770 Reviewed By: skatkov llvm-svn: 341633
* Revert "[IndVars] Turn isValidRewrite into an assertion" because it seems wrongMax Kazantsev2018-09-061-8/+9
| | | | llvm-svn: 341517
* [IndVars] Turn isValidRewrite into an assertionMax Kazantsev2018-09-061-9/+8
| | | | | | | | | | | | | | | Function rewriteLoopExitValues contains a check on isValidRewrite which is needed to make sure that SCEV does not convert the pattern `gep Base, (&p[n] - &p[0])` into `gep &p[n], Base - &p[0]`. This problem has been fixed in SCEV long ago, so this check is just obsolete. This patch converts it into an assertion to make sure that the SCEV will not mess up this case in the future. Differential Revision: https://reviews.llvm.org/D51582 Reviewed By: atrick llvm-svn: 341516
* [NFC] Add assert to detect LCSSA breaches earlyMax Kazantsev2018-09-041-0/+10
| | | | llvm-svn: 341347
* [IndVars] Fix usage of SCEVExpander to not mess with SCEVConstant. PR38674Max Kazantsev2018-09-041-18/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This patch removes the function `expandSCEVIfNeeded` which behaves not as it was intended. This function tries to make a lookup for exact existing expansion and only goes to normal expansion via `expandCodeFor` if this lookup hasn't found anything. As a result of this, if some instruction above the loop has a `SCEVConstant` SCEV, this logic will return this instruction when asked for this `SCEVConstant` rather than return a constant value. This is both non-profitable and in some cases leads to breach of LCSSA form (as in PR38674). Whether or not it is possible to break LCSSA with this algorithm and with some non-constant SCEVs is still in question, this is still being investigated. I wasn't able to construct such a test so far, so maybe this situation is impossible. If it is, it will go as a separate fix. Rather than do it, it is always correct to just invoke `expandCodeFor` unconditionally: it behaves smarter about insertion points, and as side effect of this it will choose a constant value for SCEVConstants. For other SCEVs it may end up finding a better insertion point. So it should not be worse in any case. NOTE: So far the only known case for which this transform may break LCSSA is mapping of SCEVConstant to an instruction. However there is a suspicion that the entire algorithm can compromise LCSSA form for other cases as well (yet not proved). Differential Revision: https://reviews.llvm.org/D51286 Reviewed By: etherzhhb llvm-svn: 341345
* [NFC] A loop can never contain Ret instructionMax Kazantsev2018-08-281-1/+1
| | | | llvm-svn: 340808
* Move Analysis/Utils/Local.h back to TransformsDavid Blaikie2018-06-041-1/+1
| | | | | | | | | | Review feedback from r328165. Split out just the one function from the file that's used by Analysis. (As chandlerc pointed out, the original change only moved the header and not the implementation anyway - which was fine for the one function that was used (since it's a template/inlined in the header) but not in general) llvm-svn: 333954
* Rename DEBUG macro to LLVM_DEBUG.Nicola Zaghen2018-05-141-24/+27
| | | | | | | | | | | | | | | | 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
* Fix a couple of layering violations in TransformsDavid Blaikie2018-03-211-1/+1
| | | | | | | | | | | | | Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering. Transforms depends on Transforms/Utils, not the other way around. So remove the header and the "createStripGCRelocatesPass" function declaration (& definition) that is unused and motivated this dependency. Move Transforms/Utils/Local.h into Analysis because it's used by Analysis/MemoryBuiltins.cpp. llvm-svn: 328165
* Use phi ranges to simplify code. No functionality change intended.Benjamin Kramer2017-12-301-12/+9
| | | | llvm-svn: 321585
* Remove redundant includes from lib/Transforms.Michael Zolotukhin2017-12-131-1/+0
| | | | llvm-svn: 320628
* IndVarSimplify: preserve debug information attached to widened PHI nodes.Adrian Prantl2017-11-021-0/+10
| | | | | | | | | | This fixes PR35015. https://bugs.llvm.org/show_bug.cgi?id=35015 Differential Revision: https://reviews.llvm.org/D39345 llvm-svn: 317282
* [Transforms] Fix some Clang-tidy modernize and Include What You Use ↵Eugene Zelenko2017-10-161-35/+82
| | | | | | warnings; other minor fixes (NFC). llvm-svn: 315940
* [SimplifyIndVar] Replace IVUsers with loop invariant whenever possibleHongbin Zheng2017-10-121-1/+2
| | | | | | Differential Revision: https://reviews.llvm.org/D38415 llvm-svn: 315551
* [IndVars] Add an option to be able to disable LFTRSerguei Katkov2017-06-091-1/+6
| | | | | | | | | | | | 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
* Added LLVM_FALLTHROUGH to address warning: this statement may fall through. NFC.Galina Kistanova2017-06-031-0/+1
| | | | llvm-svn: 304637
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-19/+12
| | | | | | This relands r301424. llvm-svn: 301812
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-12/+19
| | | | | | | | | | | | 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-19/+12
| | | | | | | | | | | | | | | | 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
* Use MutableArrayRef for APFloat::convertToIntegerSimon Pilgrim2017-03-201-2/+3
| | | | | | As discussed on D31074, use MutableArrayRef for destination integer buffers to help assert before stack overflows happen. llvm-svn: 298253
OpenPOWER on IntegriCloud