LLVM API Documentation
00001 //===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass performs several transformations to transform natural loops into a 00011 // simpler form, which makes subsequent analyses and transformations simpler and 00012 // more effective. 00013 // 00014 // Loop pre-header insertion guarantees that there is a single, non-critical 00015 // entry edge from outside of the loop to the loop header. This simplifies a 00016 // number of analyses and transformations, such as LICM. 00017 // 00018 // Loop exit-block insertion guarantees that all exit blocks from the loop 00019 // (blocks which are outside of the loop that have predecessors inside of the 00020 // loop) only have predecessors from inside of the loop (and are thus dominated 00021 // by the loop header). This simplifies transformations such as store-sinking 00022 // that are built into LICM. 00023 // 00024 // This pass also guarantees that loops will have exactly one backedge. 00025 // 00026 // Note that the simplifycfg pass will clean up blocks which are split out but 00027 // end up being unnecessary, so usage of this pass should not pessimize 00028 // generated code. 00029 // 00030 // This pass obviously modifies the CFG, but updates loop information and 00031 // dominator information. 00032 // 00033 //===----------------------------------------------------------------------===// 00034 00035 #include "llvm/Transforms/Scalar.h" 00036 #include "llvm/Constant.h" 00037 #include "llvm/Instructions.h" 00038 #include "llvm/Function.h" 00039 #include "llvm/Type.h" 00040 #include "llvm/Analysis/Dominators.h" 00041 #include "llvm/Analysis/LoopInfo.h" 00042 #include "llvm/Support/CFG.h" 00043 #include "llvm/Transforms/Utils/Local.h" 00044 #include "llvm/ADT/SetOperations.h" 00045 #include "llvm/ADT/SetVector.h" 00046 #include "llvm/ADT/Statistic.h" 00047 #include "llvm/ADT/DepthFirstIterator.h" 00048 using namespace llvm; 00049 00050 namespace { 00051 Statistic<> 00052 NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted"); 00053 Statistic<> 00054 NumNested("loopsimplify", "Number of nested loops split out"); 00055 00056 struct LoopSimplify : public FunctionPass { 00057 virtual bool runOnFunction(Function &F); 00058 00059 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00060 // We need loop information to identify the loops... 00061 AU.addRequired<LoopInfo>(); 00062 AU.addRequired<DominatorSet>(); 00063 AU.addRequired<DominatorTree>(); 00064 00065 AU.addPreserved<LoopInfo>(); 00066 AU.addPreserved<DominatorSet>(); 00067 AU.addPreserved<ImmediateDominators>(); 00068 AU.addPreserved<DominatorTree>(); 00069 AU.addPreserved<DominanceFrontier>(); 00070 AU.addPreservedID(BreakCriticalEdgesID); // No crit edges added.... 00071 } 00072 private: 00073 bool ProcessLoop(Loop *L); 00074 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 00075 const std::vector<BasicBlock*> &Preds); 00076 BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 00077 void InsertPreheaderForLoop(Loop *L); 00078 Loop *SeparateNestedLoop(Loop *L); 00079 void InsertUniqueBackedgeBlock(Loop *L); 00080 00081 void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 00082 std::vector<BasicBlock*> &PredBlocks); 00083 }; 00084 00085 RegisterOpt<LoopSimplify> 00086 X("loopsimplify", "Canonicalize natural loops", true); 00087 } 00088 00089 // Publically exposed interface to pass... 00090 const PassInfo *llvm::LoopSimplifyID = X.getPassInfo(); 00091 FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 00092 00093 /// runOnFunction - Run down all loops in the CFG (recursively, but we could do 00094 /// it in any convenient order) inserting preheaders... 00095 /// 00096 bool LoopSimplify::runOnFunction(Function &F) { 00097 bool Changed = false; 00098 LoopInfo &LI = getAnalysis<LoopInfo>(); 00099 00100 for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) 00101 Changed |= ProcessLoop(*I); 00102 00103 return Changed; 00104 } 00105 00106 00107 /// ProcessLoop - Walk the loop structure in depth first order, ensuring that 00108 /// all loops have preheaders. 00109 /// 00110 bool LoopSimplify::ProcessLoop(Loop *L) { 00111 bool Changed = false; 00112 00113 // Check to see that no blocks (other than the header) in the loop have 00114 // predecessors that are not in the loop. This is not valid for natural 00115 // loops, but can occur if the blocks are unreachable. Since they are 00116 // unreachable we can just shamelessly destroy their terminators to make them 00117 // not branch into the loop! 00118 assert(L->getBlocks()[0] == L->getHeader() && 00119 "Header isn't first block in loop?"); 00120 for (unsigned i = 1, e = L->getBlocks().size(); i != e; ++i) { 00121 BasicBlock *LoopBB = L->getBlocks()[i]; 00122 Retry: 00123 for (pred_iterator PI = pred_begin(LoopBB), E = pred_end(LoopBB); 00124 PI != E; ++PI) 00125 if (!L->contains(*PI)) { 00126 // This predecessor is not in the loop. Kill its terminator! 00127 BasicBlock *DeadBlock = *PI; 00128 for (succ_iterator SI = succ_begin(DeadBlock), E = succ_end(DeadBlock); 00129 SI != E; ++SI) 00130 (*SI)->removePredecessor(DeadBlock); // Remove PHI node entries 00131 00132 // Delete the dead terminator. 00133 DeadBlock->getInstList().pop_back(); 00134 00135 Value *RetVal = 0; 00136 if (LoopBB->getParent()->getReturnType() != Type::VoidTy) 00137 RetVal = Constant::getNullValue(LoopBB->getParent()->getReturnType()); 00138 new ReturnInst(RetVal, DeadBlock); 00139 goto Retry; // We just invalidated the pred_iterator. Retry. 00140 } 00141 } 00142 00143 // Does the loop already have a preheader? If so, don't modify the loop... 00144 if (L->getLoopPreheader() == 0) { 00145 InsertPreheaderForLoop(L); 00146 NumInserted++; 00147 Changed = true; 00148 } 00149 00150 // Next, check to make sure that all exit nodes of the loop only have 00151 // predecessors that are inside of the loop. This check guarantees that the 00152 // loop preheader/header will dominate the exit blocks. If the exit block has 00153 // predecessors from outside of the loop, split the edge now. 00154 std::vector<BasicBlock*> ExitBlocks; 00155 L->getExitBlocks(ExitBlocks); 00156 00157 SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 00158 for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 00159 E = ExitBlockSet.end(); I != E; ++I) { 00160 BasicBlock *ExitBlock = *I; 00161 for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 00162 PI != PE; ++PI) 00163 if (!L->contains(*PI)) { 00164 RewriteLoopExitBlock(L, ExitBlock); 00165 NumInserted++; 00166 Changed = true; 00167 break; 00168 } 00169 } 00170 00171 // If the header has more than two predecessors at this point (from the 00172 // preheader and from multiple backedges), we must adjust the loop. 00173 if (L->getNumBackEdges() != 1) { 00174 // If this is really a nested loop, rip it out into a child loop. 00175 if (Loop *NL = SeparateNestedLoop(L)) { 00176 ++NumNested; 00177 // This is a big restructuring change, reprocess the whole loop. 00178 ProcessLoop(NL); 00179 return true; 00180 } 00181 00182 InsertUniqueBackedgeBlock(L); 00183 NumInserted++; 00184 Changed = true; 00185 } 00186 00187 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 00188 Changed |= ProcessLoop(*I); 00189 return Changed; 00190 } 00191 00192 /// SplitBlockPredecessors - Split the specified block into two blocks. We want 00193 /// to move the predecessors specified in the Preds list to point to the new 00194 /// block, leaving the remaining predecessors pointing to BB. This method 00195 /// updates the SSA PHINode's, but no other analyses. 00196 /// 00197 BasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB, 00198 const char *Suffix, 00199 const std::vector<BasicBlock*> &Preds) { 00200 00201 // Create new basic block, insert right before the original block... 00202 BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB); 00203 00204 // The preheader first gets an unconditional branch to the loop header... 00205 BranchInst *BI = new BranchInst(BB, NewBB); 00206 00207 // For every PHI node in the block, insert a PHI node into NewBB where the 00208 // incoming values from the out of loop edges are moved to NewBB. We have two 00209 // possible cases here. If the loop is dead, we just insert dummy entries 00210 // into the PHI nodes for the new edge. If the loop is not dead, we move the 00211 // incoming edges in BB into new PHI nodes in NewBB. 00212 // 00213 if (!Preds.empty()) { // Is the loop not obviously dead? 00214 // Check to see if the values being merged into the new block need PHI 00215 // nodes. If so, insert them. 00216 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) { 00217 PHINode *PN = cast<PHINode>(I); 00218 ++I; 00219 00220 // Check to see if all of the values coming in are the same. If so, we 00221 // don't need to create a new PHI node. 00222 Value *InVal = PN->getIncomingValueForBlock(Preds[0]); 00223 for (unsigned i = 1, e = Preds.size(); i != e; ++i) 00224 if (InVal != PN->getIncomingValueForBlock(Preds[i])) { 00225 InVal = 0; 00226 break; 00227 } 00228 00229 // If the values coming into the block are not the same, we need a PHI. 00230 if (InVal == 0) { 00231 // Create the new PHI node, insert it into NewBB at the end of the block 00232 PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 00233 00234 // Move all of the edges from blocks outside the loop to the new PHI 00235 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 00236 Value *V = PN->removeIncomingValue(Preds[i], false); 00237 NewPHI->addIncoming(V, Preds[i]); 00238 } 00239 InVal = NewPHI; 00240 } else { 00241 // Remove all of the edges coming into the PHI nodes from outside of the 00242 // block. 00243 for (unsigned i = 0, e = Preds.size(); i != e; ++i) 00244 PN->removeIncomingValue(Preds[i], false); 00245 } 00246 00247 // Add an incoming value to the PHI node in the loop for the preheader 00248 // edge. 00249 PN->addIncoming(InVal, NewBB); 00250 00251 // Can we eliminate this phi node now? 00252 if (Value *V = hasConstantValue(PN)) { 00253 if (!isa<Instruction>(V) || 00254 getAnalysis<DominatorSet>().dominates(cast<Instruction>(V), PN)) { 00255 PN->replaceAllUsesWith(V); 00256 BB->getInstList().erase(PN); 00257 } 00258 } 00259 } 00260 00261 // Now that the PHI nodes are updated, actually move the edges from 00262 // Preds to point to NewBB instead of BB. 00263 // 00264 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 00265 TerminatorInst *TI = Preds[i]->getTerminator(); 00266 for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 00267 if (TI->getSuccessor(s) == BB) 00268 TI->setSuccessor(s, NewBB); 00269 } 00270 00271 } else { // Otherwise the loop is dead... 00272 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) { 00273 PHINode *PN = cast<PHINode>(I); 00274 // Insert dummy values as the incoming value... 00275 PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 00276 } 00277 } 00278 return NewBB; 00279 } 00280 00281 /// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 00282 /// preheader, this method is called to insert one. This method has two phases: 00283 /// preheader insertion and analysis updating. 00284 /// 00285 void LoopSimplify::InsertPreheaderForLoop(Loop *L) { 00286 BasicBlock *Header = L->getHeader(); 00287 00288 // Compute the set of predecessors of the loop that are not in the loop. 00289 std::vector<BasicBlock*> OutsideBlocks; 00290 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 00291 PI != PE; ++PI) 00292 if (!L->contains(*PI)) // Coming in from outside the loop? 00293 OutsideBlocks.push_back(*PI); // Keep track of it... 00294 00295 // Split out the loop pre-header 00296 BasicBlock *NewBB = 00297 SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 00298 00299 //===--------------------------------------------------------------------===// 00300 // Update analysis results now that we have performed the transformation 00301 // 00302 00303 // We know that we have loop information to update... update it now. 00304 if (Loop *Parent = L->getParentLoop()) 00305 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 00306 00307 // If the header for the loop used to be an exit node for another loop, then 00308 // we need to update this to know that the loop-preheader is now the exit 00309 // node. Note that the only loop that could have our header as an exit node 00310 // is a sibling loop, ie, one with the same parent loop, or one if it's 00311 // children. 00312 // 00313 LoopInfo::iterator ParentLoops, ParentLoopsE; 00314 if (Loop *Parent = L->getParentLoop()) { 00315 ParentLoops = Parent->begin(); 00316 ParentLoopsE = Parent->end(); 00317 } else { // Must check top-level loops... 00318 ParentLoops = getAnalysis<LoopInfo>().begin(); 00319 ParentLoopsE = getAnalysis<LoopInfo>().end(); 00320 } 00321 00322 DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info 00323 DominatorTree &DT = getAnalysis<DominatorTree>(); 00324 00325 00326 // Update the dominator tree information. 00327 // The immediate dominator of the preheader is the immediate dominator of 00328 // the old header. 00329 DominatorTree::Node *PHDomTreeNode = 00330 DT.createNewNode(NewBB, DT.getNode(Header)->getIDom()); 00331 00332 // Change the header node so that PNHode is the new immediate dominator 00333 DT.changeImmediateDominator(DT.getNode(Header), PHDomTreeNode); 00334 00335 { 00336 // The blocks that dominate NewBB are the blocks that dominate Header, 00337 // minus Header, plus NewBB. 00338 DominatorSet::DomSetType DomSet = DS.getDominators(Header); 00339 DomSet.erase(Header); // Header does not dominate us... 00340 DS.addBasicBlock(NewBB, DomSet); 00341 00342 // The newly created basic block dominates all nodes dominated by Header. 00343 for (df_iterator<DominatorTree::Node*> DFI = df_begin(PHDomTreeNode), 00344 E = df_end(PHDomTreeNode); DFI != E; ++DFI) 00345 DS.addDominator((*DFI)->getBlock(), NewBB); 00346 } 00347 00348 // Update immediate dominator information if we have it... 00349 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 00350 // Whatever i-dominated the header node now immediately dominates NewBB 00351 ID->addNewBlock(NewBB, ID->get(Header)); 00352 00353 // The preheader now is the immediate dominator for the header node... 00354 ID->setImmediateDominator(Header, NewBB); 00355 } 00356 00357 // Update dominance frontier information... 00358 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 00359 // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates 00360 // everything that Header does, and it strictly dominates Header in 00361 // addition. 00362 assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?"); 00363 DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second; 00364 NewDFSet.erase(Header); 00365 DF->addBasicBlock(NewBB, NewDFSet); 00366 00367 // Now we must loop over all of the dominance frontiers in the function, 00368 // replacing occurrences of Header with NewBB in some cases. If a block 00369 // dominates a (now) predecessor of NewBB, but did not strictly dominate 00370 // Header, it will have Header in it's DF set, but should now have NewBB in 00371 // its set. 00372 for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) { 00373 // Get all of the dominators of the predecessor... 00374 const DominatorSet::DomSetType &PredDoms = 00375 DS.getDominators(OutsideBlocks[i]); 00376 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 00377 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 00378 BasicBlock *PredDom = *PDI; 00379 // If the loop header is in DF(PredDom), then PredDom didn't dominate 00380 // the header but did dominate a predecessor outside of the loop. Now 00381 // we change this entry to include the preheader in the DF instead of 00382 // the header. 00383 DominanceFrontier::iterator DFI = DF->find(PredDom); 00384 assert(DFI != DF->end() && "No dominance frontier for node?"); 00385 if (DFI->second.count(Header)) { 00386 DF->removeFromFrontier(DFI, Header); 00387 DF->addToFrontier(DFI, NewBB); 00388 } 00389 } 00390 } 00391 } 00392 } 00393 00394 /// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 00395 /// blocks. This method is used to split exit blocks that have predecessors 00396 /// outside of the loop. 00397 BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 00398 DominatorSet &DS = getAnalysis<DominatorSet>(); 00399 00400 std::vector<BasicBlock*> LoopBlocks; 00401 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 00402 if (L->contains(*I)) 00403 LoopBlocks.push_back(*I); 00404 00405 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 00406 BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 00407 00408 // Update Loop Information - we know that the new block will be in the parent 00409 // loop of L. 00410 if (Loop *Parent = L->getParentLoop()) 00411 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 00412 00413 // Update dominator information (set, immdom, domtree, and domfrontier) 00414 UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks); 00415 return NewBB; 00416 } 00417 00418 /// AddBlockAndPredsToSet - Add the specified block, and all of its 00419 /// predecessors, to the specified set, if it's not already in there. Stop 00420 /// predecessor traversal when we reach StopBlock. 00421 static void AddBlockAndPredsToSet(BasicBlock *BB, BasicBlock *StopBlock, 00422 std::set<BasicBlock*> &Blocks) { 00423 if (!Blocks.insert(BB).second) return; // already processed. 00424 if (BB == StopBlock) return; // Stop here! 00425 00426 for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) 00427 AddBlockAndPredsToSet(*I, StopBlock, Blocks); 00428 } 00429 00430 /// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 00431 /// PHI node that tells us how to partition the loops. 00432 static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorSet &DS) { 00433 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 00434 PHINode *PN = cast<PHINode>(I); 00435 ++I; 00436 if (Value *V = hasConstantValue(PN)) 00437 if (!isa<Instruction>(V) || DS.dominates(cast<Instruction>(V), PN)) { 00438 // This is a degenerate PHI already, don't modify it! 00439 PN->replaceAllUsesWith(V); 00440 PN->getParent()->getInstList().erase(PN); 00441 continue; 00442 } 00443 00444 // Scan this PHI node looking for a use of the PHI node by itself. 00445 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00446 if (PN->getIncomingValue(i) == PN && 00447 L->contains(PN->getIncomingBlock(i))) 00448 // We found something tasty to remove. 00449 return PN; 00450 } 00451 return 0; 00452 } 00453 00454 /// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 00455 /// them out into a nested loop. This is important for code that looks like 00456 /// this: 00457 /// 00458 /// Loop: 00459 /// ... 00460 /// br cond, Loop, Next 00461 /// ... 00462 /// br cond2, Loop, Out 00463 /// 00464 /// To identify this common case, we look at the PHI nodes in the header of the 00465 /// loop. PHI nodes with unchanging values on one backedge correspond to values 00466 /// that change in the "outer" loop, but not in the "inner" loop. 00467 /// 00468 /// If we are able to separate out a loop, return the new outer loop that was 00469 /// created. 00470 /// 00471 Loop *LoopSimplify::SeparateNestedLoop(Loop *L) { 00472 PHINode *PN = FindPHIToPartitionLoops(L, getAnalysis<DominatorSet>()); 00473 if (PN == 0) return 0; // No known way to partition. 00474 00475 // Pull out all predecessors that have varying values in the loop. This 00476 // handles the case when a PHI node has multiple instances of itself as 00477 // arguments. 00478 std::vector<BasicBlock*> OuterLoopPreds; 00479 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00480 if (PN->getIncomingValue(i) != PN || 00481 !L->contains(PN->getIncomingBlock(i))) 00482 OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 00483 00484 BasicBlock *Header = L->getHeader(); 00485 BasicBlock *NewBB = SplitBlockPredecessors(Header, ".outer", OuterLoopPreds); 00486 00487 // Update dominator information (set, immdom, domtree, and domfrontier) 00488 UpdateDomInfoForRevectoredPreds(NewBB, OuterLoopPreds); 00489 00490 // Create the new outer loop. 00491 Loop *NewOuter = new Loop(); 00492 00493 LoopInfo &LI = getAnalysis<LoopInfo>(); 00494 00495 // Change the parent loop to use the outer loop as its child now. 00496 if (Loop *Parent = L->getParentLoop()) 00497 Parent->replaceChildLoopWith(L, NewOuter); 00498 else 00499 LI.changeTopLevelLoop(L, NewOuter); 00500 00501 // This block is going to be our new header block: add it to this loop and all 00502 // parent loops. 00503 NewOuter->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 00504 00505 // L is now a subloop of our outer loop. 00506 NewOuter->addChildLoop(L); 00507 00508 for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) 00509 NewOuter->addBlockEntry(L->getBlocks()[i]); 00510 00511 // Determine which blocks should stay in L and which should be moved out to 00512 // the Outer loop now. 00513 DominatorSet &DS = getAnalysis<DominatorSet>(); 00514 std::set<BasicBlock*> BlocksInL; 00515 for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 00516 if (DS.dominates(Header, *PI)) 00517 AddBlockAndPredsToSet(*PI, Header, BlocksInL); 00518 00519 00520 // Scan all of the loop children of L, moving them to OuterLoop if they are 00521 // not part of the inner loop. 00522 for (Loop::iterator I = L->begin(); I != L->end(); ) 00523 if (BlocksInL.count((*I)->getHeader())) 00524 ++I; // Loop remains in L 00525 else 00526 NewOuter->addChildLoop(L->removeChildLoop(I)); 00527 00528 // Now that we know which blocks are in L and which need to be moved to 00529 // OuterLoop, move any blocks that need it. 00530 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 00531 BasicBlock *BB = L->getBlocks()[i]; 00532 if (!BlocksInL.count(BB)) { 00533 // Move this block to the parent, updating the exit blocks sets 00534 L->removeBlockFromLoop(BB); 00535 if (LI[BB] == L) 00536 LI.changeLoopFor(BB, NewOuter); 00537 --i; 00538 } 00539 } 00540 00541 return NewOuter; 00542 } 00543 00544 00545 00546 /// InsertUniqueBackedgeBlock - This method is called when the specified loop 00547 /// has more than one backedge in it. If this occurs, revector all of these 00548 /// backedges to target a new basic block and have that block branch to the loop 00549 /// header. This ensures that loops have exactly one backedge. 00550 /// 00551 void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { 00552 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 00553 00554 // Get information about the loop 00555 BasicBlock *Preheader = L->getLoopPreheader(); 00556 BasicBlock *Header = L->getHeader(); 00557 Function *F = Header->getParent(); 00558 00559 // Figure out which basic blocks contain back-edges to the loop header. 00560 std::vector<BasicBlock*> BackedgeBlocks; 00561 for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 00562 if (*I != Preheader) BackedgeBlocks.push_back(*I); 00563 00564 // Create and insert the new backedge block... 00565 BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F); 00566 BranchInst *BETerminator = new BranchInst(Header, BEBlock); 00567 00568 // Move the new backedge block to right after the last backedge block. 00569 Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 00570 F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 00571 00572 // Now that the block has been inserted into the function, create PHI nodes in 00573 // the backedge block which correspond to any PHI nodes in the header block. 00574 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 00575 PHINode *PN = cast<PHINode>(I); 00576 PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be", 00577 BETerminator); 00578 NewPN->op_reserve(2*BackedgeBlocks.size()); 00579 00580 // Loop over the PHI node, moving all entries except the one for the 00581 // preheader over to the new PHI node. 00582 unsigned PreheaderIdx = ~0U; 00583 bool HasUniqueIncomingValue = true; 00584 Value *UniqueValue = 0; 00585 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 00586 BasicBlock *IBB = PN->getIncomingBlock(i); 00587 Value *IV = PN->getIncomingValue(i); 00588 if (IBB == Preheader) { 00589 PreheaderIdx = i; 00590 } else { 00591 NewPN->addIncoming(IV, IBB); 00592 if (HasUniqueIncomingValue) { 00593 if (UniqueValue == 0) 00594 UniqueValue = IV; 00595 else if (UniqueValue != IV) 00596 HasUniqueIncomingValue = false; 00597 } 00598 } 00599 } 00600 00601 // Delete all of the incoming values from the old PN except the preheader's 00602 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 00603 if (PreheaderIdx != 0) { 00604 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 00605 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 00606 } 00607 PN->op_erase(PN->op_begin()+2, PN->op_end()); 00608 00609 // Finally, add the newly constructed PHI node as the entry for the BEBlock. 00610 PN->addIncoming(NewPN, BEBlock); 00611 00612 // As an optimization, if all incoming values in the new PhiNode (which is a 00613 // subset of the incoming values of the old PHI node) have the same value, 00614 // eliminate the PHI Node. 00615 if (HasUniqueIncomingValue) { 00616 NewPN->replaceAllUsesWith(UniqueValue); 00617 BEBlock->getInstList().erase(NewPN); 00618 } 00619 } 00620 00621 // Now that all of the PHI nodes have been inserted and adjusted, modify the 00622 // backedge blocks to just to the BEBlock instead of the header. 00623 for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 00624 TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 00625 for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 00626 if (TI->getSuccessor(Op) == Header) 00627 TI->setSuccessor(Op, BEBlock); 00628 } 00629 00630 //===--- Update all analyses which we must preserve now -----------------===// 00631 00632 // Update Loop Information - we know that this block is now in the current 00633 // loop and all parent loops. 00634 L->addBasicBlockToLoop(BEBlock, getAnalysis<LoopInfo>()); 00635 00636 // Update dominator information (set, immdom, domtree, and domfrontier) 00637 UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks); 00638 } 00639 00640 /// UpdateDomInfoForRevectoredPreds - This method is used to update the four 00641 /// different kinds of dominator information (dominator sets, immediate 00642 /// dominators, dominator trees, and dominance frontiers) after a new block has 00643 /// been added to the CFG. 00644 /// 00645 /// This only supports the case when an existing block (known as "NewBBSucc"), 00646 /// had some of its predecessors factored into a new basic block. This 00647 /// transformation inserts a new basic block ("NewBB"), with a single 00648 /// unconditional branch to NewBBSucc, and moves some predecessors of 00649 /// "NewBBSucc" to now branch to NewBB. These predecessors are listed in 00650 /// PredBlocks, even though they are the same as 00651 /// pred_begin(NewBB)/pred_end(NewBB). 00652 /// 00653 void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 00654 std::vector<BasicBlock*> &PredBlocks) { 00655 assert(!PredBlocks.empty() && "No predblocks??"); 00656 assert(succ_begin(NewBB) != succ_end(NewBB) && 00657 ++succ_begin(NewBB) == succ_end(NewBB) && 00658 "NewBB should have a single successor!"); 00659 BasicBlock *NewBBSucc = *succ_begin(NewBB); 00660 DominatorSet &DS = getAnalysis<DominatorSet>(); 00661 00662 // Update dominator information... The blocks that dominate NewBB are the 00663 // intersection of the dominators of predecessors, plus the block itself. 00664 // 00665 DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]); 00666 for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 00667 set_intersect(NewBBDomSet, DS.getDominators(PredBlocks[i])); 00668 NewBBDomSet.insert(NewBB); // All blocks dominate themselves... 00669 DS.addBasicBlock(NewBB, NewBBDomSet); 00670 00671 // The newly inserted basic block will dominate existing basic blocks iff the 00672 // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate 00673 // the non-pred blocks, then they all must be the same block! 00674 // 00675 bool NewBBDominatesNewBBSucc = true; 00676 { 00677 BasicBlock *OnePred = PredBlocks[0]; 00678 for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 00679 if (PredBlocks[i] != OnePred) { 00680 NewBBDominatesNewBBSucc = false; 00681 break; 00682 } 00683 00684 if (NewBBDominatesNewBBSucc) 00685 for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 00686 PI != E; ++PI) 00687 if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) { 00688 NewBBDominatesNewBBSucc = false; 00689 break; 00690 } 00691 } 00692 00693 // The other scenario where the new block can dominate its successors are when 00694 // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc 00695 // already. 00696 if (!NewBBDominatesNewBBSucc) { 00697 NewBBDominatesNewBBSucc = true; 00698 for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 00699 PI != E; ++PI) 00700 if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) { 00701 NewBBDominatesNewBBSucc = false; 00702 break; 00703 } 00704 } 00705 00706 // If NewBB dominates some blocks, then it will dominate all blocks that 00707 // NewBBSucc does. 00708 if (NewBBDominatesNewBBSucc) { 00709 BasicBlock *PredBlock = PredBlocks[0]; 00710 Function *F = NewBB->getParent(); 00711 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 00712 if (DS.dominates(NewBBSucc, I)) 00713 DS.addDominator(I, NewBB); 00714 } 00715 00716 // Update immediate dominator information if we have it... 00717 BasicBlock *NewBBIDom = 0; 00718 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 00719 // To find the immediate dominator of the new exit node, we trace up the 00720 // immediate dominators of a predecessor until we find a basic block that 00721 // dominates the exit block. 00722 // 00723 BasicBlock *Dom = PredBlocks[0]; // Some random predecessor... 00724 while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator... 00725 assert(Dom != 0 && "No shared dominator found???"); 00726 Dom = ID->get(Dom); 00727 } 00728 00729 // Set the immediate dominator now... 00730 ID->addNewBlock(NewBB, Dom); 00731 NewBBIDom = Dom; // Reuse this if calculating DominatorTree info... 00732 00733 // If NewBB strictly dominates other blocks, we need to update their idom's 00734 // now. The only block that need adjustment is the NewBBSucc block, whose 00735 // idom should currently be set to PredBlocks[0]. 00736 if (NewBBDominatesNewBBSucc) 00737 ID->setImmediateDominator(NewBBSucc, NewBB); 00738 } 00739 00740 // Update DominatorTree information if it is active. 00741 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 00742 // If we don't have ImmediateDominator info around, calculate the idom as 00743 // above. 00744 DominatorTree::Node *NewBBIDomNode; 00745 if (NewBBIDom) { 00746 NewBBIDomNode = DT->getNode(NewBBIDom); 00747 } else { 00748 NewBBIDomNode = DT->getNode(PredBlocks[0]); // Random pred 00749 while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) { 00750 NewBBIDomNode = NewBBIDomNode->getIDom(); 00751 assert(NewBBIDomNode && "No shared dominator found??"); 00752 } 00753 } 00754 00755 // Create the new dominator tree node... and set the idom of NewBB. 00756 DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, NewBBIDomNode); 00757 00758 // If NewBB strictly dominates other blocks, then it is now the immediate 00759 // dominator of NewBBSucc. Update the dominator tree as appropriate. 00760 if (NewBBDominatesNewBBSucc) { 00761 DominatorTree::Node *NewBBSuccNode = DT->getNode(NewBBSucc); 00762 DT->changeImmediateDominator(NewBBSuccNode, NewBBNode); 00763 } 00764 } 00765 00766 // Update dominance frontier information... 00767 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 00768 // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the 00769 // DF(PredBlocks[0]) without the stuff that the new block does not dominate 00770 // a predecessor of. 00771 if (NewBBDominatesNewBBSucc) { 00772 DominanceFrontier::iterator DFI = DF->find(PredBlocks[0]); 00773 if (DFI != DF->end()) { 00774 DominanceFrontier::DomSetType Set = DFI->second; 00775 // Filter out stuff in Set that we do not dominate a predecessor of. 00776 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 00777 E = Set.end(); SetI != E;) { 00778 bool DominatesPred = false; 00779 for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); 00780 PI != E; ++PI) 00781 if (DS.dominates(NewBB, *PI)) 00782 DominatesPred = true; 00783 if (!DominatesPred) 00784 Set.erase(SetI++); 00785 else 00786 ++SetI; 00787 } 00788 00789 DF->addBasicBlock(NewBB, Set); 00790 } 00791 00792 } else { 00793 // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate 00794 // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> 00795 // NewBBSucc)). NewBBSucc is the single successor of NewBB. 00796 DominanceFrontier::DomSetType NewDFSet; 00797 NewDFSet.insert(NewBBSucc); 00798 DF->addBasicBlock(NewBB, NewDFSet); 00799 } 00800 00801 // Now we must loop over all of the dominance frontiers in the function, 00802 // replacing occurrences of NewBBSucc with NewBB in some cases. All 00803 // blocks that dominate a block in PredBlocks and contained NewBBSucc in 00804 // their dominance frontier must be updated to contain NewBB instead. 00805 // 00806 for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) { 00807 BasicBlock *Pred = PredBlocks[i]; 00808 // Get all of the dominators of the predecessor... 00809 const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred); 00810 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 00811 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 00812 BasicBlock *PredDom = *PDI; 00813 00814 // If the NewBBSucc node is in DF(PredDom), then PredDom didn't 00815 // dominate NewBBSucc but did dominate a predecessor of it. Now we 00816 // change this entry to include NewBB in the DF instead of NewBBSucc. 00817 DominanceFrontier::iterator DFI = DF->find(PredDom); 00818 assert(DFI != DF->end() && "No dominance frontier for node?"); 00819 if (DFI->second.count(NewBBSucc)) { 00820 // If NewBBSucc should not stay in our dominator frontier, remove it. 00821 // We remove it unless there is a predecessor of NewBBSucc that we 00822 // dominate, but we don't strictly dominate NewBBSucc. 00823 bool ShouldRemove = true; 00824 if (PredDom == NewBBSucc || !DS.dominates(PredDom, NewBBSucc)) { 00825 // Okay, we know that PredDom does not strictly dominate NewBBSucc. 00826 // Check to see if it dominates any predecessors of NewBBSucc. 00827 for (pred_iterator PI = pred_begin(NewBBSucc), 00828 E = pred_end(NewBBSucc); PI != E; ++PI) 00829 if (DS.dominates(PredDom, *PI)) { 00830 ShouldRemove = false; 00831 break; 00832 } 00833 } 00834 00835 if (ShouldRemove) 00836 DF->removeFromFrontier(DFI, NewBBSucc); 00837 DF->addToFrontier(DFI, NewBB); 00838 } 00839 } 00840 } 00841 } 00842 } 00843