diff options
Diffstat (limited to 'lib/Transforms/Utils/BreakCriticalEdges.cpp')
| -rw-r--r-- | lib/Transforms/Utils/BreakCriticalEdges.cpp | 206 |
1 files changed, 206 insertions, 0 deletions
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp new file mode 100644 index 0000000000..7e44574a6e --- /dev/null +++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -0,0 +1,206 @@ +//===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// BreakCriticalEdges pass - Break all of the critical edges in the CFG by +// inserting a dummy basic block. This pass may be "required" by passes that +// cannot deal with critical edges. For this usage, the structure type is +// forward declared. This pass obviously invalidates the CFG, but can update +// forward dominator (set, immediate dominators, tree, and frontier) +// information. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Function.h" +#include "llvm/Instructions.h" +#include "llvm/Type.h" +#include "llvm/Support/CFG.h" +#include "llvm/ADT/Statistic.h" +using namespace llvm; + +namespace { + Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted"); + + struct BreakCriticalEdges : public FunctionPass { + virtual bool runOnFunction(Function &F); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addPreserved<DominatorSet>(); + AU.addPreserved<ImmediateDominators>(); + AU.addPreserved<DominatorTree>(); + AU.addPreserved<DominanceFrontier>(); + AU.addPreserved<LoopInfo>(); + + // No loop canonicalization guarantees are broken by this pass. + AU.addPreservedID(LoopSimplifyID); + } + }; + + RegisterOpt<BreakCriticalEdges> X("break-crit-edges", + "Break critical edges in CFG"); +} + +// Publically exposed interface to pass... +const PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo(); +FunctionPass *llvm::createBreakCriticalEdgesPass() { + return new BreakCriticalEdges(); +} + +// runOnFunction - Loop over all of the edges in the CFG, breaking critical +// edges as they are found. +// +bool BreakCriticalEdges::runOnFunction(Function &F) { + bool Changed = false; + for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { + TerminatorInst *TI = I->getTerminator(); + if (TI->getNumSuccessors() > 1) + for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) + if (SplitCriticalEdge(TI, i, this)) { + ++NumBroken; + Changed = true; + } + } + + return Changed; +} + +//===----------------------------------------------------------------------===// +// Implementation of the external critical edge manipulation functions +//===----------------------------------------------------------------------===// + +// isCriticalEdge - Return true if the specified edge is a critical edge. +// Critical edges are edges from a block with multiple successors to a block +// with multiple predecessors. +// +bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) { + assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); + if (TI->getNumSuccessors() == 1) return false; + + const BasicBlock *Dest = TI->getSuccessor(SuccNum); + pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); + + // If there is more than one predecessor, this is a critical edge... + assert(I != E && "No preds, but we have an edge to the block?"); + ++I; // Skip one edge due to the incoming arc from TI. + return I != E; +} + +// SplitCriticalEdge - If this edge is a critical edge, insert a new node to +// split the critical edge. This will update DominatorSet, ImmediateDominator, +// DominatorTree, and DominatorFrontier information if it is available, thus +// calling this pass will not invalidate either of them. This returns true if +// the edge was split, false otherwise. +// +bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { + if (!isCriticalEdge(TI, SuccNum)) return false; + BasicBlock *TIBB = TI->getParent(); + BasicBlock *DestBB = TI->getSuccessor(SuccNum); + + // Create a new basic block, linking it into the CFG. + BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." + + DestBB->getName() + "_crit_edge"); + // Create our unconditional branch... + new BranchInst(DestBB, NewBB); + + // Branch to the new block, breaking the edge... + TI->setSuccessor(SuccNum, NewBB); + + // Insert the block into the function... right after the block TI lives in. + Function &F = *TIBB->getParent(); + F.getBasicBlockList().insert(TIBB->getNext(), NewBB); + + // If there are any PHI nodes in DestBB, we need to update them so that they + // merge incoming values from NewBB instead of from TIBB. + // + for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { + PHINode *PN = cast<PHINode>(I); + // We no longer enter through TIBB, now we come in through NewBB. Revector + // exactly one entry in the PHI node that used to come from TIBB to come + // from NewBB. + int BBIdx = PN->getBasicBlockIndex(TIBB); + PN->setIncomingBlock(BBIdx, NewBB); + } + + // If we don't have a pass object, we can't update anything... + if (P == 0) return true; + + // Now update analysis information. These are the analyses that we are + // currently capable of updating... + // + + // Should we update DominatorSet information? + if (DominatorSet *DS = P->getAnalysisToUpdate<DominatorSet>()) { + // The blocks that dominate the new one are the blocks that dominate TIBB + // plus the new block itself. + DominatorSet::DomSetType DomSet = DS->getDominators(TIBB); + DomSet.insert(NewBB); // A block always dominates itself. + DS->addBasicBlock(NewBB, DomSet); + } + + // Should we update ImmediateDominator information? + if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) { + // TIBB is the new immediate dominator for NewBB. NewBB doesn't dominate + // anything. + ID->addNewBlock(NewBB, TIBB); + } + + // Should we update DominatorTree information? + if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) { + DominatorTree::Node *TINode = DT->getNode(TIBB); + + // The new block is not the immediate dominator for any other nodes, but + // TINode is the immediate dominator for the new node. + // + if (TINode) // Don't break unreachable code! + DT->createNewNode(NewBB, TINode); + } + + // Should we update DominanceFrontier information? + if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) { + // Since the new block is dominated by its only predecessor TIBB, + // it cannot be in any block's dominance frontier. Its dominance + // frontier is {DestBB}. + DominanceFrontier::DomSetType NewDFSet; + NewDFSet.insert(DestBB); + DF->addBasicBlock(NewBB, NewDFSet); + } + + // Update LoopInfo if it is around. + if (LoopInfo *LI = P->getAnalysisToUpdate<LoopInfo>()) { + // If one or the other blocks were not in a loop, the new block is not + // either, and thus LI doesn't need to be updated. + if (Loop *TIL = LI->getLoopFor(TIBB)) + if (Loop *DestLoop = LI->getLoopFor(DestBB)) { + if (TIL == DestLoop) { + // Both in the same loop, the NewBB joins loop. + DestLoop->addBasicBlockToLoop(NewBB, *LI); + } else if (TIL->contains(DestLoop->getHeader())) { + // Edge from an outer loop to an inner loop. Add to the outer lopo. + TIL->addBasicBlockToLoop(NewBB, *LI); + } else if (DestLoop->contains(TIL->getHeader())) { + // Edge from an inner loop to an outer loop. Add to the outer lopo. + DestLoop->addBasicBlockToLoop(NewBB, *LI); + } else { + // Edge from two loops with no containment relation. Because these + // are natural loops, we know that the destination block must be the + // header of its loop (adding a branch into a loop elsewhere would + // create an irreducible loop). + assert(DestLoop->getHeader() == DestBB && + "Should not create irreducible loops!"); + if (Loop *P = DestLoop->getParentLoop()) + P->addBasicBlockToLoop(NewBB, *LI); + } + } + + } + return true; +} |