summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* (Almost) always call reserveOperandSpace() on newly created PHINodes.Jay Foad2011-03-301-0/+1
| | | | llvm-svn: 128535
* Remove code for updating dominance frontiers and some outdated references toCameron Zwarich2011-01-181-44/+6
| | | | | | dominance and post-dominance frontiers. llvm-svn: 123725
* indentationChris Lattner2011-01-141-1/+1
| | | | llvm-svn: 123426
* split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner2011-01-021-1/+1
| | | | | | so that Dominators.h is *just* domtree. Also prune #includes a bit. llvm-svn: 122714
* Get rid of static constructors for pass registration. Instead, every pass ↵Owen Anderson2010-10-191-1/+3
| | | | | | | | | | | | | | | | | exposes an initializeMyPassFunction(), which must be called in the pass's constructor. This function uses static dependency declarations to recursively initialize the pass's dependencies. Clients that only create passes through the createFooPass() APIs will require no changes. Clients that want to use the CommandLine options for passes will need to manually call the appropriate initialization functions in PassInitialization.h before parsing commandline arguments. I have tested this with all standard configurations of clang and llvm-gcc on Darwin. It is possible that there are problems with the static dependencies that will only be visible with non-standard options. If you encounter any crash in pass registration/creation, please send the testcase to me directly. llvm-svn: 116820
* Now with fewer extraneous semicolons!Owen Anderson2010-10-071-1/+1
| | | | llvm-svn: 115996
* Now that PassInfo and Pass::ID have been separated, move the rest of the ↵Owen Anderson2010-08-231-2/+2
| | | | | | passes over to the new registration API. llvm-svn: 111815
* Reapply r110396, with fixes to appease the Linux buildbot gods.Owen Anderson2010-08-061-2/+2
| | | | llvm-svn: 110460
* Revert r110396 to fix buildbots.Owen Anderson2010-08-061-2/+2
| | | | llvm-svn: 110410
* Don't use PassInfo* as a type identifier for passes. Instead, use the ↵Owen Anderson2010-08-051-2/+2
| | | | | | | | address of the static ID member as the sole unique type identifier. Clean up APIs related to this change. llvm-svn: 110396
* mass elimination of reliance on automatic iterator dereferencingGabor Greif2010-07-221-1/+1
| | | | llvm-svn: 109103
* cache result of operator*Gabor Greif2010-07-091-3/+5
| | | | llvm-svn: 107984
* cache result of operator*Gabor Greif2010-07-091-2/+3
| | | | llvm-svn: 107981
* cache result of operator*Gabor Greif2010-07-091-4/+6
| | | | llvm-svn: 107975
* rename pred_const_iterator to const_pred_iterator for consistency's sakeGabor Greif2010-03-251-1/+1
| | | | llvm-svn: 99567
* Speed up codegen prepare from 3.58s to 0.488s.Chris Lattner2010-02-131-19/+52
| | | | llvm-svn: 96081
* PHINode::getBasicBlockIndex is O(n) in the number of inputsChris Lattner2010-02-131-3/+10
| | | | | | | | to a PHI, avoid it in the common case where the BB occurs in the same index for multiple phis. This speeds up CGP on an insane testcase from 8.35 to 3.58s. llvm-svn: 96080
* iterate over preds using PHI information when available instead ofChris Lattner2010-02-131-6/+14
| | | | | | using pred_begin/end. It is much faster. llvm-svn: 96079
* Add Loop contains utility methods for testing whether a loopDan Gohman2009-12-181-2/+2
| | | | | | | | contains another loop, or an instruction. The loop form is substantially more efficient on large loops than the typical code it replaces. llvm-svn: 91654
* improve comment.Chris Lattner2009-11-011-1/+1
| | | | llvm-svn: 85725
* update the comment above llvm::SplitCriticalEdge, and makeChris Lattner2009-10-311-6/+21
| | | | | | it abort on IndirectBrInst as describe in the comment. llvm-svn: 85688
* Remove includes of Support/Compiler.h that are no longer needed after theNick Lewycky2009-10-251-1/+0
| | | | | | VISIBILITY_HIDDEN removal. llvm-svn: 85043
* Remove VISIBILITY_HIDDEN from class/struct found inside anonymous namespaces.Nick Lewycky2009-10-251-1/+1
| | | | | | | Chris claims we should never have visibility_hidden inside any .cpp file but that's still not true even after this commit. llvm-svn: 85042
* Fix SplitCriticalEdge to properly update LCSSA form when splitting aDan Gohman2009-09-091-24/+51
| | | | | | | | | | loop exit edge -- new PHIs may be needed not only for the additional splits that are made to preserve LoopSimplify form, but also for the original split. Factor out the code that inserts new PHIs so that it can be used for both. Remove LoopRotation.cpp's code for manually updating LCSSA form, as it is now redundant. This fixes PR4934. llvm-svn: 81363
* Preserve ProfileInfo.Andreas Neustifter2009-09-091-0/+7
| | | | llvm-svn: 81360
OpenPOWER on IntegriCloud