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