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 | |
Chris Lattner | d216e8b | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 19 | #define DEBUG_TYPE "break-crit-edges" |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 20 | #include "llvm/Transforms/Scalar.h" |
Chris Lattner | d23520c | 2003-11-10 04:10:50 +0000 | [diff] [blame] | 21 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 22 | #include "llvm/Analysis/Dominators.h" |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 23 | #include "llvm/Analysis/LoopInfo.h" |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 24 | #include "llvm/Function.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 25 | #include "llvm/Instructions.h" |
Chris Lattner | 5b3a455 | 2005-03-17 15:38:16 +0000 | [diff] [blame] | 26 | #include "llvm/Type.h" |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 27 | #include "llvm/Support/CFG.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 28 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 29 | #include "llvm/ADT/SmallVector.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 30 | #include "llvm/ADT/Statistic.h" |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 31 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 32 | |
Chris Lattner | d216e8b | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 33 | STATISTIC(NumBroken, "Number of blocks inserted"); |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 34 | |
Chris Lattner | d216e8b | 2006-12-19 22:17:40 +0000 | [diff] [blame] | 35 | namespace { |
Chris Lattner | 9525528 | 2006-06-28 23:17:24 +0000 | [diff] [blame] | 36 | struct VISIBILITY_HIDDEN BreakCriticalEdges : public FunctionPass { |
Nick Lewycky | ecd94c8 | 2007-05-06 13:37:16 +0000 | [diff] [blame] | 37 | static char ID; // Pass identification, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 38 | BreakCriticalEdges() : FunctionPass((intptr_t)&ID) {} |
| 39 | |
Chris Lattner | 6de302b | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 40 | virtual bool runOnFunction(Function &F); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 41 | |
Chris Lattner | 6de302b | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 42 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
Owen Anderson | a3ca0b6 | 2007-04-07 05:57:09 +0000 | [diff] [blame] | 43 | AU.addPreserved<DominatorTree>(); |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 44 | AU.addPreserved<DominanceFrontier>(); |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 45 | AU.addPreserved<LoopInfo>(); |
Chris Lattner | 98bf436 | 2003-10-12 21:52:28 +0000 | [diff] [blame] | 46 | |
| 47 | // No loop canonicalization guarantees are broken by this pass. |
| 48 | AU.addPreservedID(LoopSimplifyID); |
Chris Lattner | 6de302b | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 49 | } |
| 50 | }; |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 51 | |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame] | 52 | char BreakCriticalEdges::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 53 | RegisterPass<BreakCriticalEdges> X("break-crit-edges", |
Chris Lattner | 6de302b | 2002-09-24 15:43:12 +0000 | [diff] [blame] | 54 | "Break critical edges in CFG"); |
| 55 | } |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 56 | |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 57 | // Publically exposed interface to pass... |
Chris Lattner | f7703df | 2004-01-09 06:12:26 +0000 | [diff] [blame] | 58 | const PassInfo *llvm::BreakCriticalEdgesID = X.getPassInfo(); |
Chris Lattner | 1e5fdf8 | 2004-07-31 10:01:58 +0000 | [diff] [blame] | 59 | FunctionPass *llvm::createBreakCriticalEdgesPass() { |
| 60 | return new BreakCriticalEdges(); |
| 61 | } |
Chris Lattner | d76efa0 | 2002-09-24 00:08:39 +0000 | [diff] [blame] | 62 | |
Chris Lattner | 363ca61 | 2003-11-10 04:42:42 +0000 | [diff] [blame] | 63 | // runOnFunction - Loop over all of the edges in the CFG, breaking critical |
| 64 | // edges as they are found. |
| 65 | // |
| 66 | bool BreakCriticalEdges::runOnFunction(Function &F) { |
| 67 | bool Changed = false; |
| 68 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { |
| 69 | TerminatorInst *TI = I->getTerminator(); |
| 70 | if (TI->getNumSuccessors() > 1) |
| 71 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) |
| 72 | if (SplitCriticalEdge(TI, i, this)) { |
| 73 | ++NumBroken; |
| 74 | Changed = true; |
| 75 | } |
| 76 | } |
| 77 | |
| 78 | return Changed; |
| 79 | } |
| 80 | |
| 81 | //===----------------------------------------------------------------------===// |
| 82 | // Implementation of the external critical edge manipulation functions |
| 83 | //===----------------------------------------------------------------------===// |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 84 | |
| 85 | // isCriticalEdge - Return true if the specified edge is a critical edge. |
| 86 | // Critical edges are edges from a block with multiple successors to a block |
| 87 | // with multiple predecessors. |
| 88 | // |
Chris Lattner | b57de33 | 2006-10-28 06:58:17 +0000 | [diff] [blame] | 89 | bool llvm::isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, |
| 90 | bool AllowIdenticalEdges) { |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 91 | assert(SuccNum < TI->getNumSuccessors() && "Illegal edge specification!"); |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 92 | if (TI->getNumSuccessors() == 1) return false; |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 93 | |
| 94 | const BasicBlock *Dest = TI->getSuccessor(SuccNum); |
| 95 | pred_const_iterator I = pred_begin(Dest), E = pred_end(Dest); |
| 96 | |
| 97 | // If there is more than one predecessor, this is a critical edge... |
| 98 | assert(I != E && "No preds, but we have an edge to the block?"); |
Chris Lattner | b57de33 | 2006-10-28 06:58:17 +0000 | [diff] [blame] | 99 | const BasicBlock *FirstPred = *I; |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 100 | ++I; // Skip one edge due to the incoming arc from TI. |
Chris Lattner | b57de33 | 2006-10-28 06:58:17 +0000 | [diff] [blame] | 101 | if (!AllowIdenticalEdges) |
| 102 | return I != E; |
| 103 | |
| 104 | // If AllowIdenticalEdges is true, then we allow this edge to be considered |
| 105 | // non-critical iff all preds come from TI's block. |
| 106 | for (; I != E; ++I) |
| 107 | if (*I != FirstPred) return true; |
| 108 | return false; |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 109 | } |
| 110 | |
Chris Lattner | d23520c | 2003-11-10 04:10:50 +0000 | [diff] [blame] | 111 | // SplitCriticalEdge - If this edge is a critical edge, insert a new node to |
Devang Patel | f86a73c | 2007-06-08 00:02:08 +0000 | [diff] [blame] | 112 | // split the critical edge. This will update DominatorTree, and DominatorFrontier |
| 113 | // information if it is available, thus calling this pass will not invalidate |
| 114 | // any of them. This returns true if the edge was split, false otherwise. |
| 115 | // This ensures that all edges to that dest go to one block instead of each |
| 116 | // going to a different block. |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 117 | // |
Chris Lattner | 27e1f90 | 2006-10-28 06:44:56 +0000 | [diff] [blame] | 118 | bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P, |
| 119 | bool MergeIdenticalEdges) { |
Chris Lattner | b57de33 | 2006-10-28 06:58:17 +0000 | [diff] [blame] | 120 | if (!isCriticalEdge(TI, SuccNum, MergeIdenticalEdges)) return false; |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 121 | BasicBlock *TIBB = TI->getParent(); |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 122 | BasicBlock *DestBB = TI->getSuccessor(SuccNum); |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 123 | |
| 124 | // Create a new basic block, linking it into the CFG. |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 125 | BasicBlock *NewBB = new BasicBlock(TIBB->getName() + "." + |
| 126 | DestBB->getName() + "_crit_edge"); |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 127 | // Create our unconditional branch... |
Chris Lattner | 108e4ab | 2003-11-21 16:52:05 +0000 | [diff] [blame] | 128 | new BranchInst(DestBB, NewBB); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 129 | |
Chris Lattner | 27e1f90 | 2006-10-28 06:44:56 +0000 | [diff] [blame] | 130 | // Branch to the new block, breaking the edge. |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 131 | TI->setSuccessor(SuccNum, NewBB); |
| 132 | |
| 133 | // Insert the block into the function... right after the block TI lives in. |
| 134 | Function &F = *TIBB->getParent(); |
Chris Lattner | 261cdfb | 2007-04-17 18:09:47 +0000 | [diff] [blame] | 135 | Function::iterator FBBI = TIBB; |
| 136 | F.getBasicBlockList().insert(++FBBI, NewBB); |
Chris Lattner | 27e1f90 | 2006-10-28 06:44:56 +0000 | [diff] [blame] | 137 | |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 138 | // If there are any PHI nodes in DestBB, we need to update them so that they |
| 139 | // merge incoming values from NewBB instead of from TIBB. |
| 140 | // |
Reid Spencer | 2da5c3d | 2004-09-15 17:06:42 +0000 | [diff] [blame] | 141 | for (BasicBlock::iterator I = DestBB->begin(); isa<PHINode>(I); ++I) { |
| 142 | PHINode *PN = cast<PHINode>(I); |
Chris Lattner | 06887c9 | 2004-02-29 22:24:41 +0000 | [diff] [blame] | 143 | // We no longer enter through TIBB, now we come in through NewBB. Revector |
| 144 | // exactly one entry in the PHI node that used to come from TIBB to come |
| 145 | // from NewBB. |
Chris Lattner | b01bfd4 | 2005-08-12 21:58:07 +0000 | [diff] [blame] | 146 | int BBIdx = PN->getBasicBlockIndex(TIBB); |
| 147 | PN->setIncomingBlock(BBIdx, NewBB); |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 148 | } |
Chris Lattner | 27e1f90 | 2006-10-28 06:44:56 +0000 | [diff] [blame] | 149 | |
| 150 | // If there are any other edges from TIBB to DestBB, update those to go |
| 151 | // through the split block, making those edges non-critical as well (and |
| 152 | // reducing the number of phi entries in the DestBB if relevant). |
| 153 | if (MergeIdenticalEdges) { |
| 154 | for (unsigned i = SuccNum+1, e = TI->getNumSuccessors(); i != e; ++i) { |
| 155 | if (TI->getSuccessor(i) != DestBB) continue; |
| 156 | |
| 157 | // Remove an entry for TIBB from DestBB phi nodes. |
| 158 | DestBB->removePredecessor(TIBB); |
| 159 | |
| 160 | // We found another edge to DestBB, go to NewBB instead. |
| 161 | TI->setSuccessor(i, NewBB); |
| 162 | } |
| 163 | } |
| 164 | |
| 165 | |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 166 | |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 167 | // 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] | 168 | if (P == 0) return true; |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 169 | |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 170 | // Now update analysis information. Since the only predecessor of NewBB is |
| 171 | // the TIBB, TIBB clearly dominates NewBB. TIBB usually doesn't dominate |
| 172 | // anything, as there are other successors of DestBB. However, if all other |
| 173 | // predecessors of DestBB are already dominated by DestBB (e.g. DestBB is a |
| 174 | // loop header) then NewBB dominates DestBB. |
| 175 | SmallVector<BasicBlock*, 8> OtherPreds; |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 176 | |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 177 | for (pred_iterator I = pred_begin(DestBB), E = pred_end(DestBB); I != E; ++I) |
| 178 | if (*I != NewBB) |
| 179 | OtherPreds.push_back(*I); |
| 180 | |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 181 | bool NewBBDominatesDestBB = true; |
| 182 | |
Chris Lattner | c178d94 | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 183 | // Should we update DominatorTree information? |
Chris Lattner | e802a02 | 2002-10-08 21:06:27 +0000 | [diff] [blame] | 184 | if (DominatorTree *DT = P->getAnalysisToUpdate<DominatorTree>()) { |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 185 | DomTreeNode *TINode = DT->getNode(TIBB); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 186 | |
Chris Lattner | c178d94 | 2002-09-26 16:18:51 +0000 | [diff] [blame] | 187 | // The new block is not the immediate dominator for any other nodes, but |
| 188 | // TINode is the immediate dominator for the new node. |
| 189 | // |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 190 | if (TINode) { // Don't break unreachable code! |
Devang Patel | 83beaee | 2007-06-04 16:43:25 +0000 | [diff] [blame] | 191 | DomTreeNode *NewBBNode = DT->addNewBlock(NewBB, TIBB); |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 192 | DomTreeNode *DestBBNode = 0; |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 193 | |
| 194 | // If NewBBDominatesDestBB hasn't been computed yet, do so with DT. |
| 195 | if (!OtherPreds.empty()) { |
| 196 | DestBBNode = DT->getNode(DestBB); |
| 197 | while (!OtherPreds.empty() && NewBBDominatesDestBB) { |
Devang Patel | 2604242 | 2007-06-04 00:32:22 +0000 | [diff] [blame] | 198 | if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back())) |
Devang Patel | 9a51157 | 2007-06-07 17:47:21 +0000 | [diff] [blame] | 199 | NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode); |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 200 | OtherPreds.pop_back(); |
| 201 | } |
| 202 | OtherPreds.clear(); |
| 203 | } |
| 204 | |
| 205 | // If NewBBDominatesDestBB, then NewBB dominates DestBB, otherwise it |
| 206 | // doesn't dominate anything. |
| 207 | if (NewBBDominatesDestBB) { |
| 208 | if (!DestBBNode) DestBBNode = DT->getNode(DestBB); |
| 209 | DT->changeImmediateDominator(DestBBNode, NewBBNode); |
| 210 | } |
| 211 | } |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 212 | } |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 213 | |
| 214 | // Should we update DominanceFrontier information? |
| 215 | if (DominanceFrontier *DF = P->getAnalysisToUpdate<DominanceFrontier>()) { |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 216 | // If NewBBDominatesDestBB hasn't been computed yet, do so with DF. |
| 217 | if (!OtherPreds.empty()) { |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 218 | // FIXME: IMPLEMENT THIS! |
Chris Lattner | 3a15503 | 2006-10-04 04:58:58 +0000 | [diff] [blame] | 219 | assert(0 && "Requiring domfrontiers but not idom/domtree/domset." |
| 220 | " not implemented yet!"); |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 221 | } |
| 222 | |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 223 | // Since the new block is dominated by its only predecessor TIBB, |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 224 | // it cannot be in any block's dominance frontier. If NewBB dominates |
| 225 | // DestBB, its dominance frontier is the same as DestBB's, otherwise it is |
| 226 | // just {DestBB}. |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 227 | DominanceFrontier::DomSetType NewDFSet; |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 228 | if (NewBBDominatesDestBB) { |
| 229 | DominanceFrontier::iterator I = DF->find(DestBB); |
Devang Patel | 6acc9e6 | 2007-08-13 21:59:17 +0000 | [diff] [blame] | 230 | if (I != DF->end()) { |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 231 | DF->addBasicBlock(NewBB, I->second); |
Devang Patel | 6acc9e6 | 2007-08-13 21:59:17 +0000 | [diff] [blame] | 232 | // However NewBB's frontier does not include DestBB. |
| 233 | DominanceFrontier::iterator NF = DF->find(NewBB); |
| 234 | DF->removeFromFrontier(NF, DestBB); |
| 235 | } |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 236 | else |
| 237 | DF->addBasicBlock(NewBB, DominanceFrontier::DomSetType()); |
| 238 | } else { |
| 239 | DominanceFrontier::DomSetType NewDFSet; |
| 240 | NewDFSet.insert(DestBB); |
| 241 | DF->addBasicBlock(NewBB, NewDFSet); |
| 242 | } |
Chris Lattner | 6918c07 | 2002-10-31 02:44:36 +0000 | [diff] [blame] | 243 | } |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 244 | |
| 245 | // Update LoopInfo if it is around. |
| 246 | if (LoopInfo *LI = P->getAnalysisToUpdate<LoopInfo>()) { |
| 247 | // If one or the other blocks were not in a loop, the new block is not |
| 248 | // either, and thus LI doesn't need to be updated. |
| 249 | if (Loop *TIL = LI->getLoopFor(TIBB)) |
| 250 | if (Loop *DestLoop = LI->getLoopFor(DestBB)) { |
| 251 | if (TIL == DestLoop) { |
| 252 | // Both in the same loop, the NewBB joins loop. |
Owen Anderson | d735ee8 | 2007-11-27 03:43:35 +0000 | [diff] [blame] | 253 | DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 254 | } else if (TIL->contains(DestLoop->getHeader())) { |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 255 | // Edge from an outer loop to an inner loop. Add to the outer loop. |
Owen Anderson | d735ee8 | 2007-11-27 03:43:35 +0000 | [diff] [blame] | 256 | TIL->addBasicBlockToLoop(NewBB, LI->getBase()); |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 257 | } else if (DestLoop->contains(TIL->getHeader())) { |
Chris Lattner | 86f7b21 | 2006-10-03 07:02:02 +0000 | [diff] [blame] | 258 | // Edge from an inner loop to an outer loop. Add to the outer loop. |
Owen Anderson | d735ee8 | 2007-11-27 03:43:35 +0000 | [diff] [blame] | 259 | DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 260 | } else { |
| 261 | // Edge from two loops with no containment relation. Because these |
| 262 | // are natural loops, we know that the destination block must be the |
| 263 | // header of its loop (adding a branch into a loop elsewhere would |
| 264 | // create an irreducible loop). |
| 265 | assert(DestLoop->getHeader() == DestBB && |
| 266 | "Should not create irreducible loops!"); |
| 267 | if (Loop *P = DestLoop->getParentLoop()) |
Owen Anderson | d735ee8 | 2007-11-27 03:43:35 +0000 | [diff] [blame] | 268 | P->addBasicBlockToLoop(NewBB, LI->getBase()); |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 269 | } |
| 270 | } |
Chris Lattner | 0ae380a | 2005-08-13 01:38:43 +0000 | [diff] [blame] | 271 | } |
Chris Lattner | d23520c | 2003-11-10 04:10:50 +0000 | [diff] [blame] | 272 | return true; |
Chris Lattner | eb0456c | 2002-09-24 15:51:56 +0000 | [diff] [blame] | 273 | } |