summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Properly use DT.verify in LoopSimplifyCFGMax Kazantsev2019-01-301-1/+1
| | | | llvm-svn: 352621
* [LoopSimplifyCFG] Fix inconsistency in blocks in loop markupMax Kazantsev2019-01-251-1/+1
| | | | | | | | | | | | 2nd part of D57095 with the same reason, just in another place. We never fold branches that are not immediately in the current loop, but this check is missing in `IsEdgeLive` As result, it may think that the edge in subloop is dead while it's live. It's a pessimization in the current stance. Differential Revision: https://reviews.llvm.org/D57147 Reviewed By: rupprecht llvm-svn: 352170
* [LoopSimplifyCFG] Fix inconsistency in live blocks markupMax Kazantsev2019-01-241-2/+3
| | | | | | | | | | | | | | | | | | | | | | When we choose whether or not we should mark block as dead, we have an inconsistent logic in markup of live blocks. - We take candidate IF its terminator branches on constant AND it is immediately in current loop; - We mark successor live IF its terminator doesn't branch by constant OR it branches by constant and the successor is its always taken block. What we are missing here is that when the terminator branches on a constant but is not taken as a candidate because is it not immediately in the current loop, we will mark only one (always taken) successor as live. Therefore, we do NOT do the actual folding but may NOT mark one of the successors as live. So the result of markup is wrong in this case, and we may then hit various asserts. Thanks Jordan Rupprech for reporting this! Differential Revision: https://reviews.llvm.org/D57095 Reviewed By: rupprecht llvm-svn: 352024
* Revert r351520, "Re-enable terminator folding in LoopSimplifyCFG"Jordan Rupprecht2019-01-221-1/+1
| | | | | | This is still causing compilation crashes in some targets. Will follow up shortly with a repro. llvm-svn: 351845
* 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
* Re-enable terminator folding in LoopSimplifyCFG: underlying bugs fixedMax Kazantsev2019-01-181-1/+1
| | | | llvm-svn: 351520
* [LoopSimplifyCFG] Form LCSSA when a parent loop becomes a siblingMax Kazantsev2019-01-171-0/+9
| | | | | | | | | | | | | During the transforms in LoopSimplifyCFG, when we remove a dead exiting edge, the parent loop may stop being reachable from the child loop, and therefore they become siblings. If the former child loop had uses of some values from its former parent loop, now such uses will require LCSSA Phis, even if they weren't needed before. So we must form LCSSA for all loops that stopped being ancestors of the current loop in this case. Differential Revision: https://reviews.llvm.org/D56144 Reviewed By: fedor.sergeev llvm-svn: 351434
* [LoopSimplifyCFG] Fix order of deletion of complex dead subloopsMax Kazantsev2019-01-171-2/+3
| | | | | | | | | | | | | | | | | Function `DeleteDeadBlock` requires that all predecessors of a block being deleted have already been deleted, with the exception of a single-block loop. When we use it for removal of dead subloops that contain more than one block, we may not fulfull this requirement and fail an assertion. This patch replaces invocation of `DeleteDeadBlock` with a generalized version `DeleteDeadBlocks` that is able to deal with multiple dead blocks, even if they contain some cycles. Differential Revision: https://reviews.llvm.org/D56121 Reviewed By: fedor.sergeev llvm-svn: 351433
* Give helper classes/functions local linkage. NFC.Benjamin Kramer2019-01-121-0/+2
| | | | llvm-svn: 351016
* Drop SE cache early because loop parent can change in LoopSimplifyCFGMax Kazantsev2018-12-291-3/+7
| | | | llvm-svn: 350145
* Temporarily disable term folding in LoopSimplifyCFG, add testsMax Kazantsev2018-12-281-1/+1
| | | | llvm-svn: 350117
* [LoopSimplifyCFG] Delete dead blocks in RPOMax Kazantsev2018-12-281-5/+8
| | | | | | | | | Deletion of dead blocks in arbitrary order may lead to failure of assertion in `DeleteDeadBlock` that requires that we have deleted all predecessors before we can delete the current block. We should instead delete them in RPO order. llvm-svn: 350116
* [LoopSimplifyCFG] Delete dead exiting edgesMax Kazantsev2018-12-241-8/+111
| | | | | | | | | | This patch teaches LoopSimplifyCFG to remove dead exiting edges from loops. Differential Revision: https://reviews.llvm.org/D54025 Reviewed By: fedor.sergeev llvm-svn: 350049
* Return "[LoopSimplifyCFG] Delete dead in-loop blocks"Max Kazantsev2018-12-241-10/+32
| | | | | | | | The underlying bug that caused the revert should be fixed by rL348567. Differential Revision: https://reviews.llvm.org/D54023 llvm-svn: 350045
* [LoopSimplifyCFG] Do not deal with loops with irreducible CFG insideMax Kazantsev2018-12-071-0/+40
| | | | | | | | | | | | | | | | | | | | | The current algorithm that collects live/dead/inloop blocks relies on some invariants related to RPO and PO traversals. In particular, the important fact it requires is that the only loop's latch is the first block in PO traversal. It also relies on fact that during RPO we visit all prececessors of a block before we visit this block (backedges ignored). If a loop has irreducible non-loop cycle inside, both these assumptions may break. This patch adds detection for this situation and prohibits the terminator folding for loops with irreducible CFG. We can in theory support this later, for this some algorithmic changes are needed. Besides, irreducible CFG is not a frequent situation and we can just don't bother. Thanks @uabelho for finding this! Differential Revision: https://reviews.llvm.org/D55357 Reviewed By: skatkov llvm-svn: 348567
* Revert "[LoopSimplifyCFG] Delete dead in-loop blocks"Ilya Biryukov2018-12-061-32/+10
| | | | | | | | This reverts commit r348457. The original commit causes clang to crash when doing an instrumented build with a new pass manager. Reverting to unbreak our integrate. llvm-svn: 348484
* [LoopSimplifyCFG] Delete dead in-loop blocksMax Kazantsev2018-12-061-10/+32
| | | | | | | | | | This patch teaches LoopSimplifyCFG to delete loop blocks that have become unreachable after terminator folding has been done. Differential Revision: https://reviews.llvm.org/D54023 Reviewed By: anna llvm-svn: 348457
* [LoopSimplifyCFG] Update MemorySSA in terminator folding. PR39783Max Kazantsev2018-11-301-6/+13
| | | | | | | | | | | | | | | | Terminator folding transform lacks MemorySSA update for memory Phis, while they exist within MemorySSA analysis. They need exactly the same type of updates as regular Phis. Failing to update them properly ends up with inconsistent MemorySSA and manifests in various assertion failures. This patch adds Memory Phi updates to this transform. Thanks to @jonpa for finding this! Differential Revision: https://reviews.llvm.org/D55050 Reviewed By: asbirlea llvm-svn: 347979
* Disable TermFolding in LoopSimplifyCFG until PR39783 is fixedMax Kazantsev2018-11-291-1/+1
| | | | llvm-svn: 347844
* [LoopSimplifyCFG] Turn on term folding after underlying bug fixedMax Kazantsev2018-11-271-1/+1
| | | | llvm-svn: 347641
* [LoopSimplifyCFG] Fix corner case with duplicating successorsMax Kazantsev2018-11-271-1/+11
| | | | | | | | | | | | It fixes a bug that doesn't update Phi inputs of the only live successor that is in the list of block's successors more than once. Thanks @uabelho for finding this. Differential Revision: https://reviews.llvm.org/D54849 Reviewed By: anna llvm-svn: 347640
* Disable LoopSimplifyCFG terminator folding by defaultMax Kazantsev2018-11-231-0/+6
| | | | llvm-svn: 347486
* [LoopSimplifyCFG] Don't delete LCSSA PhisMax Kazantsev2018-11-231-1/+4
| | | | | | | | | | | | When removing edges, we also update Phi inputs and may end up removing a Phi if it has only one input. We should not do it for edges that leave the current loop because these Phis are LCSSA Phis and need to be preserved. Thanks @dmgreen for finding this! Differential Revision: https://reviews.llvm.org/D54841 llvm-svn: 347484
* [NFC] Assert that all blocks staying in loop are liveMax Kazantsev2018-11-221-0/+2
| | | | llvm-svn: 347458
* [NFC] Ensure deterministic order of dead exit blocksMax Kazantsev2018-11-221-6/+11
| | | | llvm-svn: 347457
* [NFC] Simplify code by using standard exit blocks collectionMax Kazantsev2018-11-221-10/+8
| | | | llvm-svn: 347454
* Recommit "[LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches ↵Max Kazantsev2018-11-201-0/+315
| | | | | | | | | | | and switches" The initial version of patch lacked Phi nodes updates in destinations of removed edges. This version contains this update and tests on this situation. Differential Revision: https://reviews.llvm.org/D54021 llvm-svn: 347289
* Revert "[LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches ↵Benjamin Kramer2018-11-191-313/+0
| | | | | | | | and switches" This reverts commits r347183 & r347184. Crashes while building libxml. llvm-svn: 347260
* [LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches and switchesMax Kazantsev2018-11-191-0/+313
| | | | | | | | | | | | | | | | This patch introduces infrastructure and the simplest case for constant-folding of branch and switch instructions within loop into unconditional branches. It is useful as a cleanup for such passes as loop unswitching that sometimes produce such branches. Only the simplest case supported in this patch: after the folding, no block should become dead or stop being part of the loop. Support for more sophisticated cases will go separately in follow-up patches. Differential Revision: https://reviews.llvm.org/D54021 Reviewed By: anna llvm-svn: 347183
* [NFC] Reorganize code to prepare it for more transformsMax Kazantsev2018-11-011-4/+15
| | | | llvm-svn: 345820
* Update MemorySSA in LoopSimplifyCFG.Alina Sbirlea2018-08-221-4/+23
| | | | | | | | | | | | | | Summary: Add MemorySSA as a dependency to LoopSimplifyCFG and preserve it. Disabled by default until all passes preserve MemorySSA. Reviewers: bogner, chandlerc Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits Differential Revision: https://reviews.llvm.org/D50911 llvm-svn: 340445
* SCEV should forget all loops containing a deleted block.Alina Sbirlea2018-08-091-1/+2
| | | | | | | | | | | | | | Summary: LoopSimplifyCFG should update ScEv for all loops after a block is deleted. If the deleted block "Succ" is part of L, then it is part of all parent loops, so forget topmost loop. Reviewers: greened, mkazantsev, sanjoy Subscribers: jlebar, javed.absar, uabelho, llvm-commits Differential Revision: https://reviews.llvm.org/D50422 llvm-svn: 339363
* [Dominators] Convert existing passes and utils to use the DomTreeUpdater classChijun Sima2018-08-031-1/+3
| | | | | | | | | | | | | | | | | | Summary: This patch is the second in a series of patches related to the [[ http://lists.llvm.org/pipermail/llvm-dev/2018-June/123883.html | RFC - A new dominator tree updater for LLVM ]]. It converts passes (e.g. adce/jump-threading) and various functions which currently accept DDT in local.cpp and BasicBlockUtils.cpp to use the new DomTreeUpdater class. These converted functions in utils can accept DomTreeUpdater with either UpdateStrategy and can deal with both DT and PDT held by the DomTreeUpdater. Reviewers: brzycki, kuhar, dmgreen, grosser, davide Reviewed By: brzycki Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D48967 llvm-svn: 338814
* Generalize MergeBlockIntoPredecessor. Replace uses of ↵Alina Sbirlea2018-06-201-6/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | MergeBasicBlockIntoOnlyPred. Summary: Two utils methods have essentially the same functionality. This is an attempt to merge them into one. 1. lib/Transforms/Utils/Local.cpp : MergeBasicBlockIntoOnlyPred 2. lib/Transforms/Utils/BasicBlockUtils.cpp : MergeBlockIntoPredecessor Prior to the patch: 1. MergeBasicBlockIntoOnlyPred Updates either DomTree or DeferredDominance Moves all instructions from Pred to BB, deletes Pred Asserts BB has single predecessor If address was taken, replace the block address with constant 1 (?) 2. MergeBlockIntoPredecessor Updates DomTree, LoopInfo and MemoryDependenceResults Moves all instruction from BB to Pred, deletes BB Returns if doesn't have a single predecessor Returns if BB's address was taken After the patch: Method 2. MergeBlockIntoPredecessor is attempting to become the new default: Updates DomTree or DeferredDominance, and LoopInfo and MemoryDependenceResults Moves all instruction from BB to Pred, deletes BB Returns if doesn't have a single predecessor Returns if BB's address was taken Uses of MergeBasicBlockIntoOnlyPred that need to be replaced: 1. lib/Transforms/Scalar/LoopSimplifyCFG.cpp Updated in this patch. No challenges. 2. lib/CodeGen/CodeGenPrepare.cpp Updated in this patch. i. eliminateFallThrough is straightforward, but I added using a temporary array to avoid the iterator invalidation. ii. eliminateMostlyEmptyBlock(s) methods also now use a temporary array for blocks Some interesting aspects: - Since Pred is not deleted (BB is), the entry block does not need updating. - The entry block was being updated with the deleted block in eliminateMostlyEmptyBlock. Added assert to make obvious that BB=SinglePred. - isMergingEmptyBlockProfitable assumes BB is the one to be deleted. - eliminateMostlyEmptyBlock(BB) does not delete BB on one path, it deletes its unique predecessor instead. - adding some test owner as subscribers for the interesting tests modified: test/CodeGen/X86/avx-cmp.ll test/CodeGen/AMDGPU/nested-loop-conditions.ll test/CodeGen/AMDGPU/si-annotate-cf.ll test/CodeGen/X86/hoist-spill.ll test/CodeGen/X86/2006-11-17-IllegalMove.ll 3. lib/Transforms/Scalar/JumpThreading.cpp Not covered in this patch. It is the only use case using the DeferredDominance. I would defer to Brian Rzycki to make this replacement. Reviewers: chandlerc, spatel, davide, brzycki, bkramer, javed.absar Subscribers: qcolombet, sanjoy, nemanjai, nhaehnle, jlebar, tpr, kbarton, RKSimon, wmi, arsenm, llvm-commits Differential Revision: https://reviews.llvm.org/D48202 llvm-svn: 335183
* [LoopSimplifyCFG] Invalidate SCEV in LoopSimplifyCFGDavid Green2018-06-191-3/+7
| | | | | | | | | | LoopSimplifyCFG, being a loop pass, needs to preserve scalar evolution. This invalidates SE for the loops altered during block merging. Differential Revision: https://reviews.llvm.org/D48258 llvm-svn: 335036
* 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
* Transforms: Introduce Transforms/Utils.h rather than spreading the ↵David Blaikie2018-03-281-0/+1
| | | | | | | | | declarations amongst Scalar.h and IPO.h Fixes layering - Transforms/Utils shouldn't depend on including a Scalar or IPO header, because Scalar and IPO depend on Utils. llvm-svn: 328717
* 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
* Rename WeakVH to WeakTrackingVH; NFCSanjoy Das2017-05-011-1/+1
| | | | | | This relands r301424. llvm-svn: 301812
* Reverts commit r301424, r301425 and r301426Sanjoy Das2017-04-261-1/+1
| | | | | | | | | | | | 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-1/+1
| | | | | | | | | | | | | | | | 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
* [PM] Introduce an analysis set used to preserve all analyses overChandler Carruth2017-01-151-0/+1
| | | | | | | | | | | | | | | 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-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-10/+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
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-0/+1
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-1/+0
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Consistently use LoopAnalysisManagerSean Silva2016-08-091-1/+1
| | | | | | | | | | | | | | | | | One exception here is LoopInfo which must forward-declare it (because the typedef is in LoopPassManager.h which depends on LoopInfo). Also, some includes for LoopPassManager.h were needed since that file provides the typedef. Besides a general consistently benefit, the extra layer of indirection allows the mechanical part of https://reviews.llvm.org/D23256 that requires touching every transformation and analysis to be factored out cleanly. Thanks to David for the suggestion. llvm-svn: 278079
* LoopSimplifyCFG: Prefer `const auto &` to `auto &`, for clarity. NFCJustin Bogner2016-06-171-1/+2
| | | | llvm-svn: 273023
* [PM] Port of the DepndenceAnalysis to the new PM.Chandler Carruth2016-05-121-1/+1
| | | | | | | | | | | | | Ported DA to the new PM by splitting the former DependenceAnalysis Pass into a DependenceInfo result type and DependenceAnalysisWrapperPass type and adding a new PM-style DependenceAnalysis analysis pass returning the DependenceInfo. Patch by Philip Pfaffe, most of the review by Justin. Differential Revision: http://reviews.llvm.org/D18834 llvm-svn: 269370
* PM: Port LoopSimplifyCFG to the new pass managerJustin Bogner2016-05-031-42/+55
| | | | llvm-svn: 268446
OpenPOWER on IntegriCloud