summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* Strip trailing whitespaceSimon Pilgrim2017-03-201-3/+3
| | | | llvm-svn: 298249
* [IndVars] Add an assertSanjoy Das2017-02-201-0/+3
| | | | | | | We've already checked that the loop is in simplify form before, but a little paranoia never hurt anyone. llvm-svn: 295680
* [PM] Introduce an analysis set used to preserve all analyses overChandler Carruth2017-01-151-2/+3
| | | | | | | | | | | | | | | a function's CFG when that CFG is unchanged. This allows transformation passes to simply claim they preserve the CFG and analysis passes to check for the CFG being preserved to remove the fanout of all analyses being listed in all passes. I've gone through and removed or cleaned up as many of the comments reminding us to do this as I could. Differential Revision: https://reviews.llvm.org/D28627 llvm-svn: 292054
* [PM] Separate the LoopAnalysisManager from the LoopPassManager and moveChandler Carruth2017-01-111-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | the latter to the Transforms library. While the loop PM uses an analysis to form the IR units, the current plan is to have the PM itself establish and enforce both loop simplified form and LCSSA. This would be a layering violation in the analysis library. Fundamentally, the idea behind the loop PM is to *transform* loops in addition to running passes over them, so it really seemed like the most natural place to sink this was into the transforms library. We can't just move *everything* because we also have loop analyses that rely on a subset of the invariants. So this patch splits the the loop infrastructure into the analysis management that has to be part of the analysis library, and the transform-aware pass manager. This also required splitting the loop analyses' printer passes out to the transforms library, which makes sense to me as running these will transform the code into LCSSA in theory. I haven't split the unittest though because testing one component without the other seems nearly intractable. Differential Revision: https://reviews.llvm.org/D28452 llvm-svn: 291662
* [PM] Rewrite the loop pass manager to use a worklist and augmented runChandler Carruth2017-01-111-14/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | arguments much like the CGSCC pass manager. This is a major redesign following the pattern establish for the CGSCC layer to support updates to the set of loops during the traversal of the loop nest and to support invalidation of analyses. An additional significant burden in the loop PM is that so many passes require access to a large number of function analyses. Manually ensuring these are cached, available, and preserved has been a long-standing burden in LLVM even with the help of the automatic scheduling in the old pass manager. And it made the new pass manager extremely unweildy. With this design, we can package the common analyses up while in a function pass and make them immediately available to all the loop passes. While in some cases this is unnecessary, I think the simplicity afforded is worth it. This does not (yet) address loop simplified form or LCSSA form, but those are the next things on my radar and I have a clear plan for them. While the patch is very large, most of it is either mechanically updating loop passes to the new API or the new testing for the loop PM. The code for it is reasonably compact. I have not yet updated all of the loop passes to correctly leverage the update mechanisms demonstrated in the unittests. I'll do that in follow-up patches along with improved FileCheck tests for those passes that ensure things work in more realistic scenarios. In many cases, there isn't much we can do with these until the loop simplified form and LCSSA form are in place. Differential Revision: https://reviews.llvm.org/D28292 llvm-svn: 291651
* Fix a typo and also test a new machine for commit. NFC.Xin Tong2017-01-101-1/+1
| | | | llvm-svn: 291532
* Fix a typo. NFCXin Tong2017-01-071-1/+1
| | | | llvm-svn: 291335
* Fix spelling mistakes in Transforms comments. NFC.Simon Pilgrim2016-11-201-1/+1
| | | | | | Identified by Pedro Giffuni in PR27636. llvm-svn: 287488
* [IndVars] Change the order to compute WidenAddRec in widenIVUse.Wei Mi2016-11-151-2/+2
| | | | | | | | | | | | | | | | 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][DebugLoc] When widening the exit loop condition, correctly ↵Andrea Di Biagio2016-10-261-0/+5
| | | | | | | | | | | | | | | reuse the debug location of the original comparison. When the loop exit condition is canonicalized as a != compaison, reuse the debug location of the original (non canonical) comparison. Before this patch, the debug location of the new icmp was obtained from the loop latch terminator. This patch fixes the issue by correctly setting the IRBuilder's "current debug location" to the location of the original compare. Differential Revision: https://reviews.llvm.org/D25953 llvm-svn: 285185
OpenPOWER on IntegriCloud