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