Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 1 | //===- BreakCriticalEdges.cpp - Critical Edge Elimination Pass ------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 9 | // |
| 10 | // BreakCriticalEdges pass - Break all of the critical edges in the CFG by |
| 11 | // inserting a dummy basic block. This pass may be "required" by passes that |
| 12 | // cannot deal with critical edges. For this usage, the structure type is |
| 13 | // forward declared. This pass obviously invalidates the CFG, but can update |
Chris Lattner | 363ca61 | 2003-11-10 04:42:42 +0000 | [diff] [blame] | 14 | // forward dominator (set, immediate dominators, tree, and frontier) |
| 15 | // information. |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 16 | // |
| 17 | //===----------------------------------------------------------------------===// |
| 18 | |
| 19 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | d23520c | 2003-11-10 04:10:50 +0000 | [diff] [blame] | 20 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 21 | #include "llvm/Analysis/Dominators.h" |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 22 | #include "llvm/Analysis/LoopInfo.h" |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 23 | #include "llvm/Function.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 24 | #include "llvm/Instructions.h" |
Chris Lattner | 5b3a455 | 2005-03-17 15:38:16 +0000 | [diff] [blame] | 25 | #include "llvm/Type.h" |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 26 | #include "llvm/Support/CFG.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 27 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 28 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 29 | |
Chris Lattner | 6de302b | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 30 | namespace { |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 31 | Statistic<> NumBroken("break-crit-edges", "Number of blocks inserted"); |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 32 | |
Chris Lattner | 6de302b | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 33 | struct BreakCriticalEdges : public FunctionPass { |
| 34 | virtual bool runOnFunction(Function &F); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 35 | |
Chris Lattner | 6de302b | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 36 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 37 | AU.addPreserved<DominatorSet>(); |
| 38 | AU.addPreserved<ImmediateDominators>(); |
| 39 | AU.addPreserved<DominatorTree>(); |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 40 | AU.addPreserved<DominanceFrontier>(); |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 41 | AU.addPreserved<LoopInfo>(); |
Chris Lattner | 98bf436 | 2003-10-12 21:52:28 +0000 | [diff] [blame] | 42 | |
| 43 | // No loop canonicalization guarantees are broken by this pass. |
| 44 | AU.addPreservedID(LoopSimplifyID); |
Chris Lattner | 6de302b | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 45 | } |
| 46 | }; |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 47 | |
Chris Lattner | 6de302b | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 48 | RegisterOpt<BreakCriticalEdges> X("break-crit-edges", |
| 49 | "Break critical edges in CFG"); |
| 50 | } |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 51 | |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 52 | // Publically exposed interface to pass... |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 53 | const PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo(); |
Chris Lattner | 1e5fdf8 | 2004-07-31 10:01:58 +0000 | [diff] [blame] | 54 | FunctionPass *llvm::createBreakCriticalEdgesPass() { |
| 55 | return new BreakCriticalEdges(); |
| 56 | } |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 57 | |
Chris Lattner | 363ca61 | 2003-11-10 04:42:42 +0000 | [diff] [blame] | 58 | // runOnFunction - Loop over all of the edges in the CFG, breaking critical |
| 59 | // edges as they are found. |
| 60 | // |
| 61 | bool BreakCriticalEdges::runOnFunction(Function &F) { |
| 62 | bool Changed = false; |
| 63 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { |
| 64 | TerminatorInst *TI = I->getTerminator(); |
| 65 | if (TI->getNumSuccessors() > 1) |
| 66 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) |
| 67 | if (SplitCriticalEdge(TI, i, this)) { |
| 68 | ++NumBroken; |
| 69 | Changed = true; |
| 70 | } |
| 71 | } |
| 72 | |
| 73 | return Changed; |
| 74 | } |
| 75 | |
| 76 | //===----------------------------------------------------------------------===// |
| 77 | // Implementation of the external critical edge manipulation functions |
| 78 | //===----------------------------------------------------------------------===// |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 79 | |
| 80 | // isCriticalEdge - Return true if the specified edge is a critical edge. |
| 81 | // Critical edges are edges from a block with multiple successors to a block |
| 82 | // with multiple predecessors. |
| 83 | // |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 84 | bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum) { |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 85 | assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 86 | if (TI->getNumSuccessors() == 1) return false; |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 87 | |
| 88 | const BasicBlock *Dest = TI->getSuccessor(SuccNum); |
| 89 | pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); |
| 90 | |
| 91 | // If there is more than one predecessor, this is a critical edge... |
| 92 | assert(I != E && "No preds, but we have an edge to the block?"); |
| 93 | ++I; // Skip one edge due to the incoming arc from TI. |
| 94 | return I != E; |
| 95 | } |
| 96 | |
Chris Lattner | d23520c | 2003-11-10 04:10:50 +0000 | [diff] [blame] | 97 | // SplitCriticalEdge - If this edge is a critical edge, insert a new node to |
| 98 | // split the critical edge. This will update DominatorSet, ImmediateDominator, |
| 99 | // DominatorTree, and DominatorFrontier information if it is available, thus |
| 100 | // calling this pass will not invalidate either of them. This returns true if |
| 101 | // the edge was split, false otherwise. |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 102 | // |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 103 | bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P) { |
Chris Lattner | d23520c | 2003-11-10 04:10:50 +0000 | [diff] [blame] | 104 | if (!isCriticalEdge(TI, SuccNum)) return false; |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 105 | BasicBlock *TIBB = TI->getParent(); |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 106 | BasicBlock *DestBB = TI->getSuccessor(SuccNum); |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 107 | |
| 108 | // Create a new basic block, linking it into the CFG. |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 109 | BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." + |
| 110 | DestBB->getName() + "_crit_edge"); |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 111 | // Create our unconditional branch... |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 112 | new BranchInst(DestBB, NewBB); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 113 | |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 114 | // Branch to the new block, breaking the edge... |
| 115 | TI->setSuccessor(SuccNum, NewBB); |
| 116 | |
| 117 | // Insert the block into the function... right after the block TI lives in. |
| 118 | Function &F = *TIBB->getParent(); |
| 119 | F.getBasicBlockList().insert(TIBB->getNext(), NewBB); |
| 120 | |
| 121 | // If there are any PHI nodes in DestBB, we need to update them so that they |
| 122 | // merge incoming values from NewBB instead of from TIBB. |
| 123 | // |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 124 | for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { |
| 125 | PHINode *PN = cast<PHINode>(I); |
Chris Lattner | 06887c9 | 2004-02-29 22:24:41 +0000 | [diff] [blame] | 126 | // We no longer enter through TIBB, now we come in through NewBB. Revector |
| 127 | // exactly one entry in the PHI node that used to come from TIBB to come |
| 128 | // from NewBB. |
Chris Lattner | b01bfd4 | 2005-08-12 21:58:07 +0000 | [diff] [blame] | 129 | int BBIdx = PN->getBasicBlockIndex(TIBB); |
| 130 | PN->setIncomingBlock(BBIdx, NewBB); |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 131 | } |
| 132 | |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 133 | // If we don't have a pass object, we can't update anything... |
Chris Lattner | d23520c | 2003-11-10 04:10:50 +0000 | [diff] [blame] | 134 | if (P == 0) return true; |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 135 | |
Chris Lattner | c178d94 | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 136 | // Now update analysis information. These are the analyses that we are |
| 137 | // currently capable of updating... |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 138 | // |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 139 | |
Chris Lattner | c178d94 | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 140 | // Should we update DominatorSet information? |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 141 | if (DominatorSet *DS = P->getAnalysisToUpdate<DominatorSet>()) { |
Chris Lattner | c178d94 | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 142 | // The blocks that dominate the new one are the blocks that dominate TIBB |
| 143 | // plus the new block itself. |
| 144 | DominatorSet::DomSetType DomSet = DS->getDominators(TIBB); |
| 145 | DomSet.insert(NewBB); // A block always dominates itself. |
| 146 | DS->addBasicBlock(NewBB, DomSet); |
| 147 | } |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 148 | |
Misha Brukman | cf00c4a | 2003-10-10 17:57:28 +0000 | [diff] [blame] | 149 | // Should we update ImmediateDominator information? |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 150 | if (ImmediateDominators *ID = P->getAnalysisToUpdate<ImmediateDominators>()) { |
Chris Lattner | c178d94 | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 151 | // TIBB is the new immediate dominator for NewBB. NewBB doesn't dominate |
| 152 | // anything. |
| 153 | ID->addNewBlock(NewBB, TIBB); |
| 154 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 155 | |
Chris Lattner | c178d94 | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 156 | // Should we update DominatorTree information? |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 157 | if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) { |
Chris Lattner | c178d94 | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 158 | DominatorTree::Node *TINode = DT->getNode(TIBB); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 159 | |
Chris Lattner | c178d94 | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 160 | // The new block is not the immediate dominator for any other nodes, but |
| 161 | // TINode is the immediate dominator for the new node. |
| 162 | // |
Chris Lattner | d3d06a5 | 2002-10-08 21:53:51 +0000 | [diff] [blame] | 163 | if (TINode) // Don't break unreachable code! |
| 164 | DT->createNewNode(NewBB, TINode); |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 165 | } |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 166 | |
| 167 | // Should we update DominanceFrontier information? |
| 168 | if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) { |
| 169 | // Since the new block is dominated by its only predecessor TIBB, |
| 170 | // it cannot be in any block's dominance frontier. Its dominance |
| 171 | // frontier is {DestBB}. |
| 172 | DominanceFrontier::DomSetType NewDFSet; |
| 173 | NewDFSet.insert(DestBB); |
| 174 | DF->addBasicBlock(NewBB, NewDFSet); |
| 175 | } |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 176 | |
| 177 | // Update LoopInfo if it is around. |
| 178 | if (LoopInfo *LI = P->getAnalysisToUpdate<LoopInfo>()) { |
| 179 | // If one or the other blocks were not in a loop, the new block is not |
| 180 | // either, and thus LI doesn't need to be updated. |
| 181 | if (Loop *TIL = LI->getLoopFor(TIBB)) |
| 182 | if (Loop *DestLoop = LI->getLoopFor(DestBB)) { |
| 183 | if (TIL == DestLoop) { |
| 184 | // Both in the same loop, the NewBB joins loop. |
| 185 | DestLoop->addBasicBlockToLoop(NewBB, *LI); |
| 186 | } else if (TIL->contains(DestLoop->getHeader())) { |
| 187 | // Edge from an outer loop to an inner loop. Add to the outer lopo. |
| 188 | TIL->addBasicBlockToLoop(NewBB, *LI); |
| 189 | } else if (DestLoop->contains(TIL->getHeader())) { |
| 190 | // Edge from an inner loop to an outer loop. Add to the outer lopo. |
| 191 | DestLoop->addBasicBlockToLoop(NewBB, *LI); |
| 192 | } else { |
| 193 | // Edge from two loops with no containment relation. Because these |
| 194 | // are natural loops, we know that the destination block must be the |
| 195 | // header of its loop (adding a branch into a loop elsewhere would |
| 196 | // create an irreducible loop). |
| 197 | assert(DestLoop->getHeader() == DestBB && |
| 198 | "Should not create irreducible loops!"); |
| 199 | if (Loop *P = DestLoop->getParentLoop()) |
| 200 | P->addBasicBlockToLoop(NewBB, *LI); |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | } |
Chris Lattner | d23520c | 2003-11-10 04:10:50 +0000 | [diff] [blame] | 205 | return true; |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 206 | } |