summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [MemorySSA] Update analysis when the terminator is a memory instruction.Alina Sbirlea2019-11-201-0/+3
| | | | | Update MemorySSA when moving the terminator instruction, as that may be a memory touching instruction. Resolves PR44029.
* Add missing includes needed to prune LLVMContext.h include, NFCReid Kleckner2019-11-141-0/+1
| | | | | These are a pre-requisite to removing #include "llvm/Support/Options.h" from LLVMContext.h: https://reviews.llvm.org/D70280
* Sink all InitializePasses.h includesReid Kleckner2019-11-131-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
* [MemorySSA] Loop passes should mark MSSA preserved when available.Alina Sbirlea2019-08-171-2/+2
| | | | | | | | This patch applies only to the new pass manager. Currently, when MSSA Analysis is available, and pass to each loop pass, it will be preserved by that loop pass. Hence, mark the analysis preserved based on that condition, vs the current `EnableMSSALoopDependency`. This leaves the global flag to affect only the entry point in the loop pass manager (in FunctionToLoopPassAdaptor). llvm-svn: 369181
* [MemorySSA] Use SetVector to avoid nondeterminism.Alina Sbirlea2019-07-121-2/+2
| | | | | | | | | | | | | | | | Summary: Use a SetVector for DeadBlockSet. Resolves PR42574. Reviewers: george.burgess.iv, uabelho, dblaikie Subscribers: jlebar, Prazek, mgrang, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D64601 llvm-svn: 365970
* Only passes that preserve MemorySSA must mark it as preserved.Alina Sbirlea2019-06-111-1/+4
| | | | | | | | | | | | | | | | | | | | Summary: The method `getLoopPassPreservedAnalyses` should not mark MemorySSA as preserved, because it's being called in a lot of passes that do not preserve MemorySSA. Instead, mark the MemorySSA analysis as preserved by each pass that does preserve it. These changes only affect the new pass mananger. Reviewers: chandlerc Subscribers: mehdi_amini, jlebar, Prazek, george.burgess.iv, llvm-commits Tags: #llvm Differential Revision: https://reviews.llvm.org/D62536 llvm-svn: 363091
* [LoopSimplifyCFG] Suppress expensive DomTree verificationYevgeny Rouban2019-04-291-1/+7
| | | | | | | | | This patch makes verification level lower for builds with inexpensive checks. Differential Revision: https://reviews.llvm.org/D61055 llvm-svn: 359446
* [LoopSimplifyCFG] Update MemorySSA after r353911.Alina Sbirlea2019-02-211-10/+17
| | | | | | | | | | | | | | | | | 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
* [LoopSimplifyCFG] Add missing MSSA edge deletionMax Kazantsev2019-02-211-0/+2
| | | | | | | | When we create fictive switch in preheader, we should take care about MSSA and delete edge between old preheader and header. llvm-svn: 354547
* [NFC] API for signaling that the current loop is being deletedMax Kazantsev2019-02-191-9/+30
| | | | | | | We are planning to be able to delete the current loop in LoopSimplifyCFG in the future. Add API to notify the loop pass manager that it happened. llvm-svn: 354314
* [NFC] Store loop header in a local to keep it available after the loop is ↵Max Kazantsev2019-02-191-11/+9
| | | | | | deleted llvm-svn: 354313
* [NFC] Teach getInnermostLoopFor walk up the loop treesMax Kazantsev2019-02-171-6/+10
| | | | | | | This should be NFC in current use case of this method, but it will help to use it for solving more compex tasks in follow-up patches. llvm-svn: 354227
* [NFC] Fix name and clarifying comment for factored-out functionMax Kazantsev2019-02-171-4/+5
| | | | llvm-svn: 354220
* [NFC] Factor out a function for future reuseMax Kazantsev2019-02-171-8/+15
| | | | llvm-svn: 354218
* [NFCI] Factor out block removal from stack of nested loopsMax Kazantsev2019-02-151-6/+14
| | | | llvm-svn: 354124
* Fix "field 'DFS' will be initialized after field 'DTU'" warning. NFCI.Simon Pilgrim2019-02-151-1/+1
| | | | llvm-svn: 354123
* [NFC] Promote DFS to field for further useMax Kazantsev2019-02-151-2/+2
| | | | llvm-svn: 354118
* [LoopSimplifyCFG] Re-enable const branch folding by defaultMax Kazantsev2019-02-131-1/+1
| | | | | | | | Known underlying bugs have been fixed, intensive fuzz testing did not find any new problems. Re-enabling by default. Feel free to revert if it causes any functional failures. llvm-svn: 353911
* [LoopSimplifyCFG] Change logic of dead loops removal to avoid hitting assertsMax Kazantsev2019-02-121-4/+21
| | | | | | | | | | | | | | | | | | | | 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
* Delete blocks from DTU to avoid dangling pointersMax Kazantsev2019-02-121-1/+1
| | | | llvm-svn: 353804
* [LoopSimplifyCFG] Pay respect to LCSSA when removing dead blocksMax Kazantsev2019-02-121-1/+1
| | | | | | | | | | | 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-11/+22
| | | | | | | | | | | `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-1/+3
| | | | llvm-svn: 353276
* Move DomTreeUpdater from IR to AnalysisRichard Trieu2019-02-061-1/+1
| | | | | | | | DomTreeUpdater depends on headers from Analysis, but is in IR. This is a layering violation since Analysis depends on IR. Relocate this code from IR to Analysis to fix the layering violation. llvm-svn: 353265
* 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
OpenPOWER on IntegriCloud