summaryrefslogtreecommitdiffstats
path: root/llvm/test/Transforms/LoopSimplifyCFG
Commit message (Collapse)AuthorAgeFilesLines
* Revert "Temporarily Revert "Add basic loop fusion pass.""Eric Christopher2019-04-1710-0/+3485
| | | | | | | | The reversion apparently deleted the test/Transforms directory. Will be re-reverting again. llvm-svn: 358552
* Temporarily Revert "Add basic loop fusion pass."Eric Christopher2019-04-1710-3485/+0
| | | | | | | | As it's causing some bot failures (and per request from kbarton). This reverts commit r358543/ab70da07286e618016e78247e4a24fcb84077fda. llvm-svn: 358546
* [LoopSimplifyCFG] Update MemorySSA after r353911.Alina Sbirlea2019-02-215-27/+26
| | | | | | | | | | | | | | | | | Summary: MemorySSA is not properly updated in LoopSimplifyCFG after recent changes. Use SplitBlock utility to resolve that and clear all updates once handleDeadExits is finished. All updates that follow are removal of edges which are safe to handle via the removeEdge() API. Also, deleting dead blocks is done correctly as is, i.e. delete from MemorySSA before updating the CFG and DT. Reviewers: mkazantsev, rtereshin Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D58524 llvm-svn: 354613
* [NFC] Replace EOL in test fileMax Kazantsev2019-02-211-41/+41
| | | | llvm-svn: 354562
* [TEST] Add failing test that shows problems with MSSA update in LoopSimplifyCFGMax Kazantsev2019-02-211-0/+41
| | | | llvm-svn: 354559
* [LoopSimplifyCFG] Add missing MSSA edge deletionMax Kazantsev2019-02-211-0/+38
| | | | | | | | When we create fictive switch in preheader, we should take care about MSSA and delete edge between old preheader and header. llvm-svn: 354547
* [TEST] Remove 2>&1 from testsMax Kazantsev2019-02-171-3/+3
| | | | | | Avoid confusing CHECKS with debug dumps of sets that can be printed differently. llvm-svn: 354229
* [LoopSimplifyCFG] Fix test broken in release mode in r353813Sam McCall2019-02-121-0/+1
| | | | llvm-svn: 353842
* [LoopSimplifyCFG] Change logic of dead loops removal to avoid hitting assertsMax Kazantsev2019-02-121-4/+35
| | | | | | | | | | | | | | | | | | | | The function `LI.erase` has some invariants that need to be preserved when it tries to remove a loop which is not the top-level loop. In particular, it requires loop's preheader to be strictly in loop's parent. Our current logic of deletion of dead blocks may erase the information about preheader before we handle the loop, and therefore we may hit this assertion. This patch changes the logic of loop deletion: we make them top-level loops before we actually erase them. This allows us to trigger the simple branch of `erase` logic which just detatches blocks from the loop and does not try to do some complex stuff that need this invariant. Thanks to @uabelho for reporting this! Differential Revision: https://reviews.llvm.org/D57221 Reviewed By: fedor.sergeev llvm-svn: 353813
* [LoopSimplifyCFG] Pay respect to LCSSA when removing dead blocksMax Kazantsev2019-02-121-8/+29
| | | | | | | | | | | Utility function that we use for blocks deletion always unconditionally removes one-input Phis. In LoopSimplifyCFG, it can lead to breach of LCSSA form. This patch alters this function to keep them if needed. Differential Revision: https://reviews.llvm.org/D57231 Reviewed By: fedor.sergeev llvm-svn: 353803
* [LoopSimplifyCFG] Use DTU.applyUpdates instead of insert/deleteEdgeMax Kazantsev2019-02-081-21/+98
| | | | | | | | | | | `insert/deleteEdge` methods in DTU can make updates incorrectly in some cases (see https://bugs.llvm.org/show_bug.cgi?id=40528), and it is recommended to use `applyUpdates` methods instead when it is needed to make a mass update in CFG. Differential Revision: https://reviews.llvm.org/D57316 Reviewed By: kuhar llvm-svn: 353502
* [LoopSimplifyCFG] Do not count dead exit blocks twice, make CFG simplerMax Kazantsev2019-02-061-2/+0
| | | | llvm-svn: 353276
* [NFC] One more crashing test on LoopSimplifyCFGMax Kazantsev2019-01-251-0/+116
| | | | llvm-svn: 352194
* [NFC] Add failing test on LCSSA formingMax Kazantsev2019-01-251-0/+43
| | | | llvm-svn: 352190
* [NFC] Add test with multiple loopsMax Kazantsev2019-01-251-0/+55
| | | | llvm-svn: 352176
* [LoopSimplifyCFG] Fix inconsistency in blocks in loop markupMax Kazantsev2019-01-251-3/+5
| | | | | | | | | | | | 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
* [NFC] Add another failing test on LoopSimplifyCFGMax Kazantsev2019-01-241-0/+32
| | | | llvm-svn: 352026
* [LoopSimplifyCFG] Fix inconsistency in live blocks markupMax Kazantsev2019-01-241-2/+22
| | | | | | | | | | | | | | | | | | | | | | 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
* [NFC] Add a failing test on live block markup in term foldingMax Kazantsev2019-01-241-0/+40
| | | | llvm-svn: 352023
* [LoopSimplifyCFG] Form LCSSA when a parent loop becomes a siblingMax Kazantsev2019-01-171-3/+18
| | | | | | | | | | | | | 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-3/+18
| | | | | | | | | | | | | | | | | 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
* [NFC] Add failing test on LCSSA form preservation of LoopSimplifyCFGMax Kazantsev2018-12-281-0/+25
| | | | llvm-svn: 350119
* Temporarily disable term folding in LoopSimplifyCFG, add testsMax Kazantsev2018-12-281-0/+59
| | | | llvm-svn: 350117
* [LoopSimplifyCFG] Delete dead exiting edgesMax Kazantsev2018-12-241-104/+82
| | | | | | | | | | 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-104/+26
| | | | | | | | 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/+51
| | | | | | | | | | | | | | | | | | | | | 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-26/+104
| | | | | | | | 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-104/+26
| | | | | | | | | | 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
* [NFC] Verify memoryssa in test for PR39783Max Kazantsev2018-12-051-1/+1
| | | | llvm-svn: 348333
* [LoopSimplifyCFG] Update MemorySSA in terminator folding. PR39783Max Kazantsev2018-11-301-1/+0
| | | | | | | | | | | | | | | | 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
* [NFC] Simplify and reduce tests for PR39783Max Kazantsev2018-11-303-279/+111
| | | | llvm-svn: 347976
* [NFC] Add two XFAIL tests from PR39783Max Kazantsev2018-11-292-0/+279
| | | | llvm-svn: 347845
* Add missing REQUIRES: assertsMax Kazantsev2018-11-271-0/+1
| | | | llvm-svn: 347644
* [LoopSimplifyCFG] Fix corner case with duplicating successorsMax Kazantsev2018-11-271-3/+14
| | | | | | | | | | | | 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
* [NFC] Add test that demonstrates buggy behavior on term folding of ↵Max Kazantsev2018-11-231-0/+29
| | | | | | LoopSimplifyCFG llvm-svn: 347488
* Disable LoopSimplifyCFG terminator folding by defaultMax Kazantsev2018-11-232-6/+6
| | | | llvm-svn: 347486
* [LoopSimplifyCFG] Don't delete LCSSA PhisMax Kazantsev2018-11-231-0/+52
| | | | | | | | | | | | 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] Add verification flags to testsMax Kazantsev2018-11-231-3/+3
| | | | llvm-svn: 347483
* [NFC] More complex tests for LoopSimplifyCFGMax Kazantsev2018-11-211-0/+345
| | | | llvm-svn: 347384
* [NFC] Add some sophisticated tests on LoopSimplifyCFGMax Kazantsev2018-11-211-47/+724
| | | | llvm-svn: 347381
* Recommit "[LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches ↵Max Kazantsev2018-11-201-9/+149
| | | | | | | | | | | 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-49/+9
| | | | | | | | and switches" This reverts commits r347183 & r347184. Crashes while building libxml. llvm-svn: 347260
* [LoopSimplifyCFG] Add requires: asserts after rL347183Fangrui Song2018-11-191-0/+1
| | | | llvm-svn: 347184
* [LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches and switchesMax Kazantsev2018-11-191-9/+48
| | | | | | | | | | | | | | | | 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] Add missing test case, some test renamingMax Kazantsev2018-11-071-4/+43
| | | | llvm-svn: 346295
* [NFC] Add tests for loop-simplifycfg for further developmentMax Kazantsev2018-10-311-0/+1408
| | | | llvm-svn: 345713
* Update MemorySSA in LoopSimplifyCFG.Alina Sbirlea2018-08-222-0/+2
| | | | | | | | | | | | | | 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
* Generalize MergeBlockIntoPredecessor. Replace uses of ↵Alina Sbirlea2018-06-201-12/+12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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-0/+57
| | | | | | | | | | 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
* LPM: Drop require<loops> from these tests, it's redundant. NFCJustin Bogner2016-05-101-1/+1
| | | | | | | | The LoopPassManager needs to calculate the loops analysis in order to iterate over the loops at all. Requiring it is redundant and just adds noise to the RUN lines here. llvm-svn: 269097
OpenPOWER on IntegriCloud