summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Transforms: Introduce Transforms/Utils.h rather than spreading the ↵David Blaikie2018-03-281-1/+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
* Use phi ranges to simplify code. No functionality change intended.Benjamin Kramer2017-12-301-6/+5
| | | | llvm-svn: 321585
* Remove redundant includes from lib/Transforms.Michael Zolotukhin2017-12-131-1/+0
| | | | llvm-svn: 320628
* Split IndirectBr critical edges before PGO gen/use passes.Hiroshi Yamauchi2017-12-121-6/+28
| | | | | | | | | | | | | | | | | | | | | | Summary: The PGO gen/use passes currently fail with an assert failure if there's a critical edge whose source is an IndirectBr instruction and that edge needs to be instrumented. To avoid this in certain cases, split IndirectBr critical edges in the PGO gen/use passes. This works for blocks with single indirectbr predecessors, but not for those with multiple indirectbr predecessors (splitting an IndirectBr critical edge isn't always possible.) Reviewers: davidxl, xur Reviewed By: davidxl Subscribers: efriedma, llvm-commits, mehdi_amini Differential Revision: https://reviews.llvm.org/D40699 llvm-svn: 320511
* Move splitIndirectCriticalEdges() to BasicBlockUtils.h.Hiroshi Yamauchi2017-12-041-0/+139
| | | | | | | | | | | | | | | | Summary: Move splitIndirectCriticalEdges() from CodeGenPrepare to BasicBlockUtils.h so that it can be called from other places. Reviewers: davidxl Reviewed By: davidxl Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D40750 llvm-svn: 319689
* [Dominators] Teach LoopUnswitch to use the incremental APIJakub Kuderski2017-08-171-51/+15
| | | | | | | | | | | | | | | | | | Summary: This patch makes LoopUnswitch use new incremental API for updating dominators. It also updates SplitCriticalEdge, as it is called in LoopUnswitch. There doesn't seem to be any noticeable performance difference when bootstrapping clang with this patch. Reviewers: dberlin, davide, sanjoy, grosser, chandlerc Reviewed By: davide, grosser Subscribers: mzolotukhin, llvm-commits Differential Revision: https://reviews.llvm.org/D35528 llvm-svn: 311093
* [PM] Port BreakCriticalEdges to the new PM.Wei Mi2016-07-221-2/+16
| | | | | | Differential Revision: https://reviews.llvm.org/D22688 llvm-svn: 276449
* improve documentation comments; NFCSanjay Patel2016-04-231-24/+7
| | | | llvm-svn: 267292
* TransformUtils: Remove implicit ilist iterator conversions, NFCDuncan P. N. Exon Smith2015-10-131-5/+4
| | | | | | | | | | | Continuing the work from last week to remove implicit ilist iterator conversions. First related commit was probably r249767, with some more motivation in r249925. This edition gets LLVMTransformUtils compiling without the implicit conversions. No functional change intended. llvm-svn: 250142
* Drive-by fixes for LandingPad -> EHPadDavid Majnemer2015-08-041-4/+3
| | | | | | | | This change was done as an audit and is by inspection. The new EH system is still very much a work in progress. NFC for the landingpad case. llvm-svn: 243965
* [PM/AA] Remove all of the dead AliasAnalysis pointers being threadedChandler Carruth2015-07-221-2/+1
| | | | | | | | | | through APIs that are no longer necessary now that the update API has been removed. This will make changes to the AA interfaces significantly less disruptive (I hope). Either way, it seems like a really nice cleanup. llvm-svn: 242882
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* [PM] Remove the Pass argument from all of the critical edge splittingChandler Carruth2015-01-191-24/+17
| | | | | | | | | | | | | | | | | | | APIs and replace it and numerous booleans with an option struct. The critical edge splitting API has a really large surface of flags and so it seems worth burning a small option struct / builder. This struct can be constructed with the various preserved analyses and then flags can be flipped in a builder style. The various users are now responsible for directly passing along their analysis information. This should be enough for the critical edge splitting to work cleanly with the new pass manager as well. This API is still pretty crufty and could be cleaned up a lot, but I've focused on this change just threading an option struct rather than a pass through the API. llvm-svn: 226456
* [PM] Relax asserts and always try to reconstruct loop simplify form whenChandler Carruth2015-01-191-10/+4
| | | | | | | | | | | | | | | | | we can while splitting critical edges. The only code which called this and didn't require simplified loops to be preserved is polly, and the code behaves correctly there anyways. Without this change, it becomes really hard to share this code with the new pass manager where things like preserving loop simplify form don't make any sense. If anyone discovers this code behaving incorrectly, what it *should* be testing for is whether the loops it needs to be in simplified form are in fact in that form. It should always be trying to preserve that form when it exists. llvm-svn: 226443
* [PM] Pull the analyses used for another utility routine into its APIChandler Carruth2015-01-181-6/+9
| | | | | | | | | | | rather than relying on the pass object. This one is a bit annoying, but will pay off. First, supporting this one will make the next one much easier, and for utilities like LoopSimplify, this is moving them (slowly) closer to not having to pass the pass object around throughout their APIs. llvm-svn: 226396
* [PM] Now that LoopInfo isn't in the Pass type hierarchy, it is muchChandler Carruth2015-01-181-4/+4
| | | | | | | | | | | | cleaner to derive from the generic base. Thise removes a ton of boiler plate code and somewhat strange and pointless indirections. It also remove a bunch of the previously needed friend declarations. To fully remove these, I also lifted the verify logic into the generic LoopInfoBase, which seems good anyways -- it is generic and useful logic even for the machine side. llvm-svn: 226385
* [PM] Split the LoopInfo object apart from the legacy pass, creatingChandler Carruth2015-01-171-2/+3
| | | | | | | | | | a LoopInfoWrapperPass to wire the object up to the legacy pass manager. This switches all the clients of LoopInfo over and paves the way to port LoopInfo to the new pass manager. No functionality change is intended with this iteration. llvm-svn: 226373
* Introduce llvm::SplitAllCriticalEdgesKostya Serebryany2014-11-191-19/+5
| | | | | | | | | | | | | | | | | | | | Summary: move the code from BreakCriticalEdges::runOnFunction() into a separate utility function llvm::SplitAllCriticalEdges() so that it can be used independently. No functionality change intended. Test Plan: check-llvm Reviewers: nlewycky Reviewed By: nlewycky Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D6313 llvm-svn: 222288
* Revert "[C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) ↵Duncan P. N. Exon Smith2014-07-211-2/+6
| | | | | | | | | iterator ranges." This reverts commit r213474 (and r213475), which causes a miscompile on a stage2 LTO build. I'll reply on the list in a moment. llvm-svn: 213562
* [C++11] Add predecessors(BasicBlock *) / successors(BasicBlock *) iterator ↵Manuel Jacob2014-07-201-6/+2
| | | | | | | | | | | | | | | | | | ranges. Summary: This patch introduces two new iterator ranges and updates existing code to use it. No functional change intended. Test Plan: All tests (make check-all) still pass. Reviewers: dblaikie Reviewed By: dblaikie Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4481 llvm-svn: 213474
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-6/+6
| | | | llvm-svn: 207196
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. llvm-svn: 206844
* [C++11] Add 'override' keyword to virtual methods that override their base ↵Craig Topper2014-03-051-2/+2
| | | | | | class. llvm-svn: 202953
* [Modules] Move CFG.h to the IR library as it defines graph traits overChandler Carruth2014-03-041-1/+1
| | | | | | IR types. llvm-svn: 202827
* [LPM] Fix PR18643, another scary place where loop transforms failed toChandler Carruth2014-01-291-46/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | preserve loop simplify of enclosing loops. The problem here starts with LoopRotation which ends up cloning code out of the latch into the new preheader it is buidling. This can create a new edge from the preheader into the exit block of the loop which breaks LoopSimplify form. The code tries to fix this by splitting the critical edge between the latch and the exit block to get a new exit block that only the latch dominates. This sadly isn't sufficient. The exit block may be an exit block for multiple nested loops. When we clone an edge from the latch of the inner loop to the new preheader being built in the outer loop, we create an exiting edge from the outer loop to this exit block. Despite breaking the LoopSimplify form for the inner loop, this is fine for the outer loop. However, when we split the edge from the inner loop to the exit block, we create a new block which is in neither the inner nor outer loop as the new exit block. This is a predecessor to the old exit block, and so the split itself takes the outer loop out of LoopSimplify form. We need to split every edge entering the exit block from inside a loop nested more deeply than the exit block in order to preserve all of the loop simplify constraints. Once we try to do that, a problem with splitting critical edges surfaces. Previously, we tried a very brute force to update LoopSimplify form by re-computing it for all exit blocks. We don't need to do this, and doing this much will sometimes but not always overlap with the LoopRotate bug fix. Instead, the code needs to specifically handle the cases which can start to violate LoopSimplify -- they aren't that common. We need to see if the destination of the split edge was a loop exit block in simplified form for the loop of the source of the edge. For this to be true, all the predecessors need to be in the exact same loop as the source of the edge being split. If the dest block was originally in this form, we have to split all of the deges back into this loop to recover it. The old mechanism of doing this was conservatively correct because at least *one* of the exiting blocks it rewrote was the DestBB and so the DestBB's predecessors were fixed. But this is a much more targeted way of doing it. Making it targeted is important, because ballooning the set of edges touched prevents LoopRotate from being able to split edges *it* needs to split to preserve loop simplify in a coherent way -- the critical edge splitting would sometimes find the other edges in need of splitting but not others. Many, *many* thanks for help from Nick reducing these test cases mightily. And helping lots with the analysis here as this one was quite tricky to track down. llvm-svn: 200393
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-2/+4
| | | | | | | | | | | | | | | | | | | | | | | can be used by both the new pass manager and the old. This removes it from any of the virtual mess of the pass interfaces and lets it derive cleanly from the DominatorTreeBase<> template. In turn, tons of boilerplate interface can be nuked and it turns into a very straightforward extension of the base DominatorTree interface. The old analysis pass is now a simple wrapper. The names and style of this split should match the split between CallGraph and CallGraphWrapperPass. All of the users of DominatorTree have been updated to match using many of the same tricks as with CallGraph. The goal is that the common type remains the resulting DominatorTree rather than the pass. This will make subsequent work toward the new pass manager significantly easier. Also in numerous places things became cleaner because I switched from re-running the pass (!!! mid way through some other passes run!!!) to directly recomputing the domtree. llvm-svn: 199104
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-131-1/+1
| | | | | | | | | | | | | | | | | | directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. llvm-svn: 199082
* Remove the very substantial, largely unmaintained legacy PGOChandler Carruth2013-10-021-8/+1
| | | | | | | | | | | | | | | | | | | | infrastructure. This was essentially work toward PGO based on a design that had several flaws, partially dating from a time when LLVM had a different architecture, and with an effort to modernize it abandoned without being completed. Since then, it has bitrotted for several years further. The result is nearly unusable, and isn't helping any of the modern PGO efforts. Instead, it is getting in the way, adding confusion about PGO in LLVM and distracting everyone with maintenance on essentially dead code. Removing it paves the way for modern efforts around PGO. Among other effects, this removes the last of the runtime libraries from LLVM. Those are being developed in the separate 'compiler-rt' project now, with somewhat different licensing specifically more approriate for runtimes. llvm-svn: 191835
* Reimplement isPotentiallyReachable to make nocapture deduction much stronger.Nick Lewycky2013-07-271-33/+1
| | | | | | | | | | Adds unit tests for it too. Split BasicBlockUtils into an analysis-half and a transforms-half, and put the analysis bits into a new Analysis/CFG.{h,cpp}. Promote isPotentiallyReachable into llvm::isPotentiallyReachable and move it into Analysis/CFG. llvm-svn: 187283
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-3/+3
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-4/+4
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru2012-09-271-1/+1
| | | | | | See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 llvm-svn: 164768
* Fix a typo 'iff' => 'if'Sylvestre Ledru2012-09-271-1/+1
| | | | llvm-svn: 164767
* Second attempt at PR12573:Bill Wendling2012-04-301-11/+26
| | | | | | | | | | | Allow the "SplitCriticalEdge" function to split the edge to a landing pad. If the pass is *sure* that it thinks it knows what it's doing, then it may go ahead and specify that the landing pad can have its critical edge split. The loop unswitch pass is one of these passes. It will split the critical edges of all edges coming from a loop to a landing pad not within the loop. Doing so will retain important loop analysis information, such as loop simplify. llvm-svn: 155817
* Use an ArrayRef instead of explicit vector type.Bill Wendling2012-04-301-8/+5
| | | | llvm-svn: 155816
* SplitBlockPredecessors uses ArrayRef instead of Data and Size.Jakub Staszak2011-12-091-2/+1
| | | | llvm-svn: 146277
* LSR should avoid redundant edge splitting.Andrew Trick2011-10-041-2/+3
| | | | | | | | This handles the case in which LSR rewrites an IV user that is a phi and splits critical edges originating from a switch. Fixes <rdar://problem/6453893> LSR is not splitting edges "nicely" llvm-svn: 141059
* whitespaceAndrew Trick2011-10-041-18/+18
| | | | llvm-svn: 141058
* Relax this condition.Bill Wendling2011-09-201-2/+1
| | | | | | | Some passes require breaking critical edges before they're called. Don't segfault because of that. llvm-svn: 140196
* Assert that we aren't trying to split the critical edge of a landing pad. DoingBill Wendling2011-08-171-0/+5
| | | | | | so requires more care than this generic algorithm should handle. llvm-svn: 137866
* PR10386: Don't try to split an edge from an indirectbr.Eli Friedman2011-07-191-2/+9
| | | | llvm-svn: 135534
* Reinstate r133513 (reverted in r133700) with an additional fix for aJay Foad2011-06-231-38/+16
| | | | | | -Wshorten-64-to-32 warning in Instructions.h. llvm-svn: 133708
* Revert r133513:Eric Christopher2011-06-231-16/+38
| | | | | | | | | "Reinstate r133435 and r133449 (reverted in r133499) now that the clang self-hosted build failure has been fixed (r133512)." Due to some additional warnings. llvm-svn: 133700
* Reinstate r133435 and r133449 (reverted in r133499) now that the clangJay Foad2011-06-211-38/+16
| | | | | | self-hosted build failure has been fixed (r133512). llvm-svn: 133513
* Revert r133435 and r133449 to appease buildbots.Chad Rosier2011-06-211-16/+38
| | | | llvm-svn: 133499
* Change how PHINodes store their operands.Jay Foad2011-06-201-38/+16
| | | | | | | | | | | | | | | | | | | Change PHINodes to store simple pointers to their incoming basic blocks, instead of full-blown Uses. Note that this loses an optimization in SplitCriticalEdge(), because we can no longer walk the use list of a BasicBlock to find phi nodes. See the comment I removed starting "However, the foreach loop is slow for blocks with lots of predecessors". Extend replaceAllUsesWith() on a BasicBlock to also update any phi nodes in the block's successors. This mimics what would have happened when PHINodes were proper Users of their incoming blocks. (Note that this only works if OldBB->replaceAllUsesWith(NewBB) is called when OldBB still has a terminator instruction, so it still has some successors.) llvm-svn: 133435
* Preserve line number information.Devang Patel2011-05-171-1/+2
| | | | llvm-svn: 131480
* Fix a ton of comment typos found by codespell. Patch byChris Lattner2011-04-151-1/+1
| | | | | | Luis Felipe Strano Moraes! llvm-svn: 129558
* Remove PHINode::reserveOperandSpace(). Instead, add a parameter toJay Foad2011-03-301-2/+1
| | | | | | PHINode::Create() giving the (known or expected) number of operands. llvm-svn: 128537
OpenPOWER on IntegriCloud