LoopSimplify.cpp revision 98599ba6c6b12a01718b08f57ceb7aa3397c5b2d
1//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass performs several transformations to transform natural loops into a 11// simpler form, which makes subsequent analyses and transformations simpler and 12// more effective. 13// 14// Loop pre-header insertion guarantees that there is a single, non-critical 15// entry edge from outside of the loop to the loop header. This simplifies a 16// number of analyses and transformations, such as LICM. 17// 18// Loop exit-block insertion guarantees that all exit blocks from the loop 19// (blocks which are outside of the loop that have predecessors inside of the 20// loop) only have predecessors from inside of the loop (and are thus dominated 21// by the loop header). This simplifies transformations such as store-sinking 22// that are built into LICM. 23// 24// This pass also guarantees that loops will have exactly one backedge. 25// 26// Note that the simplifycfg pass will clean up blocks which are split out but 27// end up being unnecessary, so usage of this pass should not pessimize 28// generated code. 29// 30// This pass obviously modifies the CFG, but updates loop information and 31// dominator information. 32// 33//===----------------------------------------------------------------------===// 34 35#include "llvm/Transforms/Scalar.h" 36#include "llvm/Constant.h" 37#include "llvm/Instructions.h" 38#include "llvm/Function.h" 39#include "llvm/Type.h" 40#include "llvm/Analysis/AliasAnalysis.h" 41#include "llvm/Analysis/Dominators.h" 42#include "llvm/Analysis/LoopInfo.h" 43#include "llvm/Support/CFG.h" 44#include "llvm/ADT/SetOperations.h" 45#include "llvm/ADT/SetVector.h" 46#include "llvm/ADT/Statistic.h" 47#include "llvm/ADT/DepthFirstIterator.h" 48using namespace llvm; 49 50namespace { 51 Statistic<> 52 NumInserted("loopsimplify", "Number of pre-header or exit blocks inserted"); 53 Statistic<> 54 NumNested("loopsimplify", "Number of nested loops split out"); 55 56 struct LoopSimplify : public FunctionPass { 57 // AA - If we have an alias analysis object to update, this is it, otherwise 58 // this is null. 59 AliasAnalysis *AA; 60 61 virtual bool runOnFunction(Function &F); 62 63 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 64 // We need loop information to identify the loops... 65 AU.addRequired<LoopInfo>(); 66 AU.addRequired<DominatorSet>(); 67 AU.addRequired<DominatorTree>(); 68 69 AU.addPreserved<LoopInfo>(); 70 AU.addPreserved<DominatorSet>(); 71 AU.addPreserved<ImmediateDominators>(); 72 AU.addPreserved<DominatorTree>(); 73 AU.addPreserved<DominanceFrontier>(); 74 AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 75 } 76 private: 77 bool ProcessLoop(Loop *L); 78 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, const char *Suffix, 79 const std::vector<BasicBlock*> &Preds); 80 BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 81 void InsertPreheaderForLoop(Loop *L); 82 Loop *SeparateNestedLoop(Loop *L); 83 void InsertUniqueBackedgeBlock(Loop *L); 84 85 void UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 86 std::vector<BasicBlock*> &PredBlocks); 87 }; 88 89 RegisterOpt<LoopSimplify> 90 X("loopsimplify", "Canonicalize natural loops", true); 91} 92 93// Publically exposed interface to pass... 94const PassInfo *llvm::LoopSimplifyID = X.getPassInfo(); 95FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 96 97/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 98/// it in any convenient order) inserting preheaders... 99/// 100bool LoopSimplify::runOnFunction(Function &F) { 101 bool Changed = false; 102 LoopInfo &LI = getAnalysis<LoopInfo>(); 103 AA = getAnalysisToUpdate<AliasAnalysis>(); 104 105 for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) 106 Changed |= ProcessLoop(*I); 107 108 return Changed; 109} 110 111 112/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 113/// all loops have preheaders. 114/// 115bool LoopSimplify::ProcessLoop(Loop *L) { 116 bool Changed = false; 117 118 // Check to see that no blocks (other than the header) in the loop have 119 // predecessors that are not in the loop. This is not valid for natural 120 // loops, but can occur if the blocks are unreachable. Since they are 121 // unreachable we can just shamelessly destroy their terminators to make them 122 // not branch into the loop! 123 assert(L->getBlocks()[0] == L->getHeader() && 124 "Header isn't first block in loop?"); 125 for (unsigned i = 1, e = L->getBlocks().size(); i != e; ++i) { 126 BasicBlock *LoopBB = L->getBlocks()[i]; 127 Retry: 128 for (pred_iterator PI = pred_begin(LoopBB), E = pred_end(LoopBB); 129 PI != E; ++PI) 130 if (!L->contains(*PI)) { 131 // This predecessor is not in the loop. Kill its terminator! 132 BasicBlock *DeadBlock = *PI; 133 for (succ_iterator SI = succ_begin(DeadBlock), E = succ_end(DeadBlock); 134 SI != E; ++SI) 135 (*SI)->removePredecessor(DeadBlock); // Remove PHI node entries 136 137 // Delete the dead terminator. 138 if (AA) AA->deleteValue(&DeadBlock->back()); 139 DeadBlock->getInstList().pop_back(); 140 141 Value *RetVal = 0; 142 if (LoopBB->getParent()->getReturnType() != Type::VoidTy) 143 RetVal = Constant::getNullValue(LoopBB->getParent()->getReturnType()); 144 new ReturnInst(RetVal, DeadBlock); 145 goto Retry; // We just invalidated the pred_iterator. Retry. 146 } 147 } 148 149 // Does the loop already have a preheader? If so, don't modify the loop... 150 if (L->getLoopPreheader() == 0) { 151 InsertPreheaderForLoop(L); 152 NumInserted++; 153 Changed = true; 154 } 155 156 // Next, check to make sure that all exit nodes of the loop only have 157 // predecessors that are inside of the loop. This check guarantees that the 158 // loop preheader/header will dominate the exit blocks. If the exit block has 159 // predecessors from outside of the loop, split the edge now. 160 std::vector<BasicBlock*> ExitBlocks; 161 L->getExitBlocks(ExitBlocks); 162 163 SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 164 for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 165 E = ExitBlockSet.end(); I != E; ++I) { 166 BasicBlock *ExitBlock = *I; 167 for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 168 PI != PE; ++PI) 169 if (!L->contains(*PI)) { 170 RewriteLoopExitBlock(L, ExitBlock); 171 NumInserted++; 172 Changed = true; 173 break; 174 } 175 } 176 177 // If the header has more than two predecessors at this point (from the 178 // preheader and from multiple backedges), we must adjust the loop. 179 if (L->getNumBackEdges() != 1) { 180 // If this is really a nested loop, rip it out into a child loop. 181 if (Loop *NL = SeparateNestedLoop(L)) { 182 ++NumNested; 183 // This is a big restructuring change, reprocess the whole loop. 184 ProcessLoop(NL); 185 return true; 186 } 187 188 InsertUniqueBackedgeBlock(L); 189 NumInserted++; 190 Changed = true; 191 } 192 193 // Scan over the PHI nodes in the loop header. Since they now have only two 194 // incoming values (the loop is canonicalized), we may have simplified the PHI 195 // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 196 PHINode *PN; 197 DominatorSet &DS = getAnalysis<DominatorSet>(); 198 for (BasicBlock::iterator I = L->getHeader()->begin(); 199 (PN = dyn_cast<PHINode>(I++)); ) 200 if (Value *V = PN->hasConstantValue()) { 201 PN->replaceAllUsesWith(V); 202 PN->eraseFromParent(); 203 } 204 205 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 206 Changed |= ProcessLoop(*I); 207 208 return Changed; 209} 210 211/// SplitBlockPredecessors - Split the specified block into two blocks. We want 212/// to move the predecessors specified in the Preds list to point to the new 213/// block, leaving the remaining predecessors pointing to BB. This method 214/// updates the SSA PHINode's, but no other analyses. 215/// 216BasicBlock *LoopSimplify::SplitBlockPredecessors(BasicBlock *BB, 217 const char *Suffix, 218 const std::vector<BasicBlock*> &Preds) { 219 220 // Create new basic block, insert right before the original block... 221 BasicBlock *NewBB = new BasicBlock(BB->getName()+Suffix, BB->getParent(), BB); 222 223 // The preheader first gets an unconditional branch to the loop header... 224 BranchInst *BI = new BranchInst(BB, NewBB); 225 226 // For every PHI node in the block, insert a PHI node into NewBB where the 227 // incoming values from the out of loop edges are moved to NewBB. We have two 228 // possible cases here. If the loop is dead, we just insert dummy entries 229 // into the PHI nodes for the new edge. If the loop is not dead, we move the 230 // incoming edges in BB into new PHI nodes in NewBB. 231 // 232 if (!Preds.empty()) { // Is the loop not obviously dead? 233 // Check to see if the values being merged into the new block need PHI 234 // nodes. If so, insert them. 235 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ) { 236 PHINode *PN = cast<PHINode>(I); 237 ++I; 238 239 // Check to see if all of the values coming in are the same. If so, we 240 // don't need to create a new PHI node. 241 Value *InVal = PN->getIncomingValueForBlock(Preds[0]); 242 for (unsigned i = 1, e = Preds.size(); i != e; ++i) 243 if (InVal != PN->getIncomingValueForBlock(Preds[i])) { 244 InVal = 0; 245 break; 246 } 247 248 // If the values coming into the block are not the same, we need a PHI. 249 if (InVal == 0) { 250 // Create the new PHI node, insert it into NewBB at the end of the block 251 PHINode *NewPHI = new PHINode(PN->getType(), PN->getName()+".ph", BI); 252 if (AA) AA->copyValue(PN, NewPHI); 253 254 // Move all of the edges from blocks outside the loop to the new PHI 255 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 256 Value *V = PN->removeIncomingValue(Preds[i], false); 257 NewPHI->addIncoming(V, Preds[i]); 258 } 259 InVal = NewPHI; 260 } else { 261 // Remove all of the edges coming into the PHI nodes from outside of the 262 // block. 263 for (unsigned i = 0, e = Preds.size(); i != e; ++i) 264 PN->removeIncomingValue(Preds[i], false); 265 } 266 267 // Add an incoming value to the PHI node in the loop for the preheader 268 // edge. 269 PN->addIncoming(InVal, NewBB); 270 271 // Can we eliminate this phi node now? 272 if (Value *V = PN->hasConstantValue(true)) { 273 if (!isa<Instruction>(V) || 274 getAnalysis<DominatorSet>().dominates(cast<Instruction>(V), PN)) { 275 PN->replaceAllUsesWith(V); 276 if (AA) AA->deleteValue(PN); 277 BB->getInstList().erase(PN); 278 } 279 } 280 } 281 282 // Now that the PHI nodes are updated, actually move the edges from 283 // Preds to point to NewBB instead of BB. 284 // 285 for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 286 TerminatorInst *TI = Preds[i]->getTerminator(); 287 for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) 288 if (TI->getSuccessor(s) == BB) 289 TI->setSuccessor(s, NewBB); 290 } 291 292 } else { // Otherwise the loop is dead... 293 for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) { 294 PHINode *PN = cast<PHINode>(I); 295 // Insert dummy values as the incoming value... 296 PN->addIncoming(Constant::getNullValue(PN->getType()), NewBB); 297 } 298 } 299 return NewBB; 300} 301 302/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 303/// preheader, this method is called to insert one. This method has two phases: 304/// preheader insertion and analysis updating. 305/// 306void LoopSimplify::InsertPreheaderForLoop(Loop *L) { 307 BasicBlock *Header = L->getHeader(); 308 309 // Compute the set of predecessors of the loop that are not in the loop. 310 std::vector<BasicBlock*> OutsideBlocks; 311 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 312 PI != PE; ++PI) 313 if (!L->contains(*PI)) // Coming in from outside the loop? 314 OutsideBlocks.push_back(*PI); // Keep track of it... 315 316 // Split out the loop pre-header 317 BasicBlock *NewBB = 318 SplitBlockPredecessors(Header, ".preheader", OutsideBlocks); 319 320 //===--------------------------------------------------------------------===// 321 // Update analysis results now that we have performed the transformation 322 // 323 324 // We know that we have loop information to update... update it now. 325 if (Loop *Parent = L->getParentLoop()) 326 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 327 328 // If the header for the loop used to be an exit node for another loop, then 329 // we need to update this to know that the loop-preheader is now the exit 330 // node. Note that the only loop that could have our header as an exit node 331 // is a sibling loop, ie, one with the same parent loop, or one if it's 332 // children. 333 // 334 LoopInfo::iterator ParentLoops, ParentLoopsE; 335 if (Loop *Parent = L->getParentLoop()) { 336 ParentLoops = Parent->begin(); 337 ParentLoopsE = Parent->end(); 338 } else { // Must check top-level loops... 339 ParentLoops = getAnalysis<LoopInfo>().begin(); 340 ParentLoopsE = getAnalysis<LoopInfo>().end(); 341 } 342 343 DominatorSet &DS = getAnalysis<DominatorSet>(); // Update dominator info 344 DominatorTree &DT = getAnalysis<DominatorTree>(); 345 346 347 // Update the dominator tree information. 348 // The immediate dominator of the preheader is the immediate dominator of 349 // the old header. 350 DominatorTree::Node *PHDomTreeNode = 351 DT.createNewNode(NewBB, DT.getNode(Header)->getIDom()); 352 353 // Change the header node so that PNHode is the new immediate dominator 354 DT.changeImmediateDominator(DT.getNode(Header), PHDomTreeNode); 355 356 { 357 // The blocks that dominate NewBB are the blocks that dominate Header, 358 // minus Header, plus NewBB. 359 DominatorSet::DomSetType DomSet = DS.getDominators(Header); 360 DomSet.erase(Header); // Header does not dominate us... 361 DS.addBasicBlock(NewBB, DomSet); 362 363 // The newly created basic block dominates all nodes dominated by Header. 364 for (df_iterator<DominatorTree::Node*> DFI = df_begin(PHDomTreeNode), 365 E = df_end(PHDomTreeNode); DFI != E; ++DFI) 366 DS.addDominator((*DFI)->getBlock(), NewBB); 367 } 368 369 // Update immediate dominator information if we have it... 370 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 371 // Whatever i-dominated the header node now immediately dominates NewBB 372 ID->addNewBlock(NewBB, ID->get(Header)); 373 374 // The preheader now is the immediate dominator for the header node... 375 ID->setImmediateDominator(Header, NewBB); 376 } 377 378 // Update dominance frontier information... 379 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 380 // The DF(NewBB) is just (DF(Header)-Header), because NewBB dominates 381 // everything that Header does, and it strictly dominates Header in 382 // addition. 383 assert(DF->find(Header) != DF->end() && "Header node doesn't have DF set?"); 384 DominanceFrontier::DomSetType NewDFSet = DF->find(Header)->second; 385 NewDFSet.erase(Header); 386 DF->addBasicBlock(NewBB, NewDFSet); 387 388 // Now we must loop over all of the dominance frontiers in the function, 389 // replacing occurrences of Header with NewBB in some cases. If a block 390 // dominates a (now) predecessor of NewBB, but did not strictly dominate 391 // Header, it will have Header in it's DF set, but should now have NewBB in 392 // its set. 393 for (unsigned i = 0, e = OutsideBlocks.size(); i != e; ++i) { 394 // Get all of the dominators of the predecessor... 395 const DominatorSet::DomSetType &PredDoms = 396 DS.getDominators(OutsideBlocks[i]); 397 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 398 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 399 BasicBlock *PredDom = *PDI; 400 // If the loop header is in DF(PredDom), then PredDom didn't dominate 401 // the header but did dominate a predecessor outside of the loop. Now 402 // we change this entry to include the preheader in the DF instead of 403 // the header. 404 DominanceFrontier::iterator DFI = DF->find(PredDom); 405 assert(DFI != DF->end() && "No dominance frontier for node?"); 406 if (DFI->second.count(Header)) { 407 DF->removeFromFrontier(DFI, Header); 408 DF->addToFrontier(DFI, NewBB); 409 } 410 } 411 } 412 } 413} 414 415/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 416/// blocks. This method is used to split exit blocks that have predecessors 417/// outside of the loop. 418BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 419 DominatorSet &DS = getAnalysis<DominatorSet>(); 420 421 std::vector<BasicBlock*> LoopBlocks; 422 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 423 if (L->contains(*I)) 424 LoopBlocks.push_back(*I); 425 426 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 427 BasicBlock *NewBB = SplitBlockPredecessors(Exit, ".loopexit", LoopBlocks); 428 429 // Update Loop Information - we know that the new block will be in the parent 430 // loop of L. 431 if (Loop *Parent = L->getParentLoop()) 432 Parent->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 433 434 // Update dominator information (set, immdom, domtree, and domfrontier) 435 UpdateDomInfoForRevectoredPreds(NewBB, LoopBlocks); 436 return NewBB; 437} 438 439/// AddBlockAndPredsToSet - Add the specified block, and all of its 440/// predecessors, to the specified set, if it's not already in there. Stop 441/// predecessor traversal when we reach StopBlock. 442static void AddBlockAndPredsToSet(BasicBlock *BB, BasicBlock *StopBlock, 443 std::set<BasicBlock*> &Blocks) { 444 if (!Blocks.insert(BB).second) return; // already processed. 445 if (BB == StopBlock) return; // Stop here! 446 447 for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) 448 AddBlockAndPredsToSet(*I, StopBlock, Blocks); 449} 450 451/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 452/// PHI node that tells us how to partition the loops. 453static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorSet &DS, 454 AliasAnalysis *AA) { 455 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 456 PHINode *PN = cast<PHINode>(I); 457 ++I; 458 if (Value *V = PN->hasConstantValue()) 459 if (!isa<Instruction>(V) || DS.dominates(cast<Instruction>(V), PN)) { 460 // This is a degenerate PHI already, don't modify it! 461 PN->replaceAllUsesWith(V); 462 if (AA) AA->deleteValue(PN); 463 PN->eraseFromParent(); 464 continue; 465 } 466 467 // Scan this PHI node looking for a use of the PHI node by itself. 468 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 469 if (PN->getIncomingValue(i) == PN && 470 L->contains(PN->getIncomingBlock(i))) 471 // We found something tasty to remove. 472 return PN; 473 } 474 return 0; 475} 476 477/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 478/// them out into a nested loop. This is important for code that looks like 479/// this: 480/// 481/// Loop: 482/// ... 483/// br cond, Loop, Next 484/// ... 485/// br cond2, Loop, Out 486/// 487/// To identify this common case, we look at the PHI nodes in the header of the 488/// loop. PHI nodes with unchanging values on one backedge correspond to values 489/// that change in the "outer" loop, but not in the "inner" loop. 490/// 491/// If we are able to separate out a loop, return the new outer loop that was 492/// created. 493/// 494Loop *LoopSimplify::SeparateNestedLoop(Loop *L) { 495 PHINode *PN = FindPHIToPartitionLoops(L, getAnalysis<DominatorSet>(), AA); 496 if (PN == 0) return 0; // No known way to partition. 497 498 // Pull out all predecessors that have varying values in the loop. This 499 // handles the case when a PHI node has multiple instances of itself as 500 // arguments. 501 std::vector<BasicBlock*> OuterLoopPreds; 502 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 503 if (PN->getIncomingValue(i) != PN || 504 !L->contains(PN->getIncomingBlock(i))) 505 OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 506 507 BasicBlock *Header = L->getHeader(); 508 BasicBlock *NewBB = SplitBlockPredecessors(Header, ".outer", OuterLoopPreds); 509 510 // Update dominator information (set, immdom, domtree, and domfrontier) 511 UpdateDomInfoForRevectoredPreds(NewBB, OuterLoopPreds); 512 513 // Create the new outer loop. 514 Loop *NewOuter = new Loop(); 515 516 LoopInfo &LI = getAnalysis<LoopInfo>(); 517 518 // Change the parent loop to use the outer loop as its child now. 519 if (Loop *Parent = L->getParentLoop()) 520 Parent->replaceChildLoopWith(L, NewOuter); 521 else 522 LI.changeTopLevelLoop(L, NewOuter); 523 524 // This block is going to be our new header block: add it to this loop and all 525 // parent loops. 526 NewOuter->addBasicBlockToLoop(NewBB, getAnalysis<LoopInfo>()); 527 528 // L is now a subloop of our outer loop. 529 NewOuter->addChildLoop(L); 530 531 for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) 532 NewOuter->addBlockEntry(L->getBlocks()[i]); 533 534 // Determine which blocks should stay in L and which should be moved out to 535 // the Outer loop now. 536 DominatorSet &DS = getAnalysis<DominatorSet>(); 537 std::set<BasicBlock*> BlocksInL; 538 for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 539 if (DS.dominates(Header, *PI)) 540 AddBlockAndPredsToSet(*PI, Header, BlocksInL); 541 542 543 // Scan all of the loop children of L, moving them to OuterLoop if they are 544 // not part of the inner loop. 545 for (Loop::iterator I = L->begin(); I != L->end(); ) 546 if (BlocksInL.count((*I)->getHeader())) 547 ++I; // Loop remains in L 548 else 549 NewOuter->addChildLoop(L->removeChildLoop(I)); 550 551 // Now that we know which blocks are in L and which need to be moved to 552 // OuterLoop, move any blocks that need it. 553 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 554 BasicBlock *BB = L->getBlocks()[i]; 555 if (!BlocksInL.count(BB)) { 556 // Move this block to the parent, updating the exit blocks sets 557 L->removeBlockFromLoop(BB); 558 if (LI[BB] == L) 559 LI.changeLoopFor(BB, NewOuter); 560 --i; 561 } 562 } 563 564 return NewOuter; 565} 566 567 568 569/// InsertUniqueBackedgeBlock - This method is called when the specified loop 570/// has more than one backedge in it. If this occurs, revector all of these 571/// backedges to target a new basic block and have that block branch to the loop 572/// header. This ensures that loops have exactly one backedge. 573/// 574void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { 575 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 576 577 // Get information about the loop 578 BasicBlock *Preheader = L->getLoopPreheader(); 579 BasicBlock *Header = L->getHeader(); 580 Function *F = Header->getParent(); 581 582 // Figure out which basic blocks contain back-edges to the loop header. 583 std::vector<BasicBlock*> BackedgeBlocks; 584 for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 585 if (*I != Preheader) BackedgeBlocks.push_back(*I); 586 587 // Create and insert the new backedge block... 588 BasicBlock *BEBlock = new BasicBlock(Header->getName()+".backedge", F); 589 BranchInst *BETerminator = new BranchInst(Header, BEBlock); 590 591 // Move the new backedge block to right after the last backedge block. 592 Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 593 F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 594 595 // Now that the block has been inserted into the function, create PHI nodes in 596 // the backedge block which correspond to any PHI nodes in the header block. 597 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 598 PHINode *PN = cast<PHINode>(I); 599 PHINode *NewPN = new PHINode(PN->getType(), PN->getName()+".be", 600 BETerminator); 601 NewPN->reserveOperandSpace(BackedgeBlocks.size()); 602 if (AA) AA->copyValue(PN, NewPN); 603 604 // Loop over the PHI node, moving all entries except the one for the 605 // preheader over to the new PHI node. 606 unsigned PreheaderIdx = ~0U; 607 bool HasUniqueIncomingValue = true; 608 Value *UniqueValue = 0; 609 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 610 BasicBlock *IBB = PN->getIncomingBlock(i); 611 Value *IV = PN->getIncomingValue(i); 612 if (IBB == Preheader) { 613 PreheaderIdx = i; 614 } else { 615 NewPN->addIncoming(IV, IBB); 616 if (HasUniqueIncomingValue) { 617 if (UniqueValue == 0) 618 UniqueValue = IV; 619 else if (UniqueValue != IV) 620 HasUniqueIncomingValue = false; 621 } 622 } 623 } 624 625 // Delete all of the incoming values from the old PN except the preheader's 626 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 627 if (PreheaderIdx != 0) { 628 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 629 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 630 } 631 // Nuke all entries except the zero'th. 632 for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 633 PN->removeIncomingValue(e-i, false); 634 635 // Finally, add the newly constructed PHI node as the entry for the BEBlock. 636 PN->addIncoming(NewPN, BEBlock); 637 638 // As an optimization, if all incoming values in the new PhiNode (which is a 639 // subset of the incoming values of the old PHI node) have the same value, 640 // eliminate the PHI Node. 641 if (HasUniqueIncomingValue) { 642 NewPN->replaceAllUsesWith(UniqueValue); 643 if (AA) AA->deleteValue(NewPN); 644 BEBlock->getInstList().erase(NewPN); 645 } 646 } 647 648 // Now that all of the PHI nodes have been inserted and adjusted, modify the 649 // backedge blocks to just to the BEBlock instead of the header. 650 for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 651 TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 652 for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 653 if (TI->getSuccessor(Op) == Header) 654 TI->setSuccessor(Op, BEBlock); 655 } 656 657 //===--- Update all analyses which we must preserve now -----------------===// 658 659 // Update Loop Information - we know that this block is now in the current 660 // loop and all parent loops. 661 L->addBasicBlockToLoop(BEBlock, getAnalysis<LoopInfo>()); 662 663 // Update dominator information (set, immdom, domtree, and domfrontier) 664 UpdateDomInfoForRevectoredPreds(BEBlock, BackedgeBlocks); 665} 666 667/// UpdateDomInfoForRevectoredPreds - This method is used to update the four 668/// different kinds of dominator information (dominator sets, immediate 669/// dominators, dominator trees, and dominance frontiers) after a new block has 670/// been added to the CFG. 671/// 672/// This only supports the case when an existing block (known as "NewBBSucc"), 673/// had some of its predecessors factored into a new basic block. This 674/// transformation inserts a new basic block ("NewBB"), with a single 675/// unconditional branch to NewBBSucc, and moves some predecessors of 676/// "NewBBSucc" to now branch to NewBB. These predecessors are listed in 677/// PredBlocks, even though they are the same as 678/// pred_begin(NewBB)/pred_end(NewBB). 679/// 680void LoopSimplify::UpdateDomInfoForRevectoredPreds(BasicBlock *NewBB, 681 std::vector<BasicBlock*> &PredBlocks) { 682 assert(!PredBlocks.empty() && "No predblocks??"); 683 assert(succ_begin(NewBB) != succ_end(NewBB) && 684 ++succ_begin(NewBB) == succ_end(NewBB) && 685 "NewBB should have a single successor!"); 686 BasicBlock *NewBBSucc = *succ_begin(NewBB); 687 DominatorSet &DS = getAnalysis<DominatorSet>(); 688 689 // Update dominator information... The blocks that dominate NewBB are the 690 // intersection of the dominators of predecessors, plus the block itself. 691 // 692 DominatorSet::DomSetType NewBBDomSet = DS.getDominators(PredBlocks[0]); 693 for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 694 set_intersect(NewBBDomSet, DS.getDominators(PredBlocks[i])); 695 NewBBDomSet.insert(NewBB); // All blocks dominate themselves... 696 DS.addBasicBlock(NewBB, NewBBDomSet); 697 698 // The newly inserted basic block will dominate existing basic blocks iff the 699 // PredBlocks dominate all of the non-pred blocks. If all predblocks dominate 700 // the non-pred blocks, then they all must be the same block! 701 // 702 bool NewBBDominatesNewBBSucc = true; 703 { 704 BasicBlock *OnePred = PredBlocks[0]; 705 for (unsigned i = 1, e = PredBlocks.size(); i != e; ++i) 706 if (PredBlocks[i] != OnePred) { 707 NewBBDominatesNewBBSucc = false; 708 break; 709 } 710 711 if (NewBBDominatesNewBBSucc) 712 for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 713 PI != E; ++PI) 714 if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) { 715 NewBBDominatesNewBBSucc = false; 716 break; 717 } 718 } 719 720 // The other scenario where the new block can dominate its successors are when 721 // all predecessors of NewBBSucc that are not NewBB are dominated by NewBBSucc 722 // already. 723 if (!NewBBDominatesNewBBSucc) { 724 NewBBDominatesNewBBSucc = true; 725 for (pred_iterator PI = pred_begin(NewBBSucc), E = pred_end(NewBBSucc); 726 PI != E; ++PI) 727 if (*PI != NewBB && !DS.dominates(NewBBSucc, *PI)) { 728 NewBBDominatesNewBBSucc = false; 729 break; 730 } 731 } 732 733 // If NewBB dominates some blocks, then it will dominate all blocks that 734 // NewBBSucc does. 735 if (NewBBDominatesNewBBSucc) { 736 BasicBlock *PredBlock = PredBlocks[0]; 737 Function *F = NewBB->getParent(); 738 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 739 if (DS.dominates(NewBBSucc, I)) 740 DS.addDominator(I, NewBB); 741 } 742 743 // Update immediate dominator information if we have it... 744 BasicBlock *NewBBIDom = 0; 745 if (ImmediateDominators *ID = getAnalysisToUpdate<ImmediateDominators>()) { 746 // To find the immediate dominator of the new exit node, we trace up the 747 // immediate dominators of a predecessor until we find a basic block that 748 // dominates the exit block. 749 // 750 BasicBlock *Dom = PredBlocks[0]; // Some random predecessor... 751 while (!NewBBDomSet.count(Dom)) { // Loop until we find a dominator... 752 assert(Dom != 0 && "No shared dominator found???"); 753 Dom = ID->get(Dom); 754 } 755 756 // Set the immediate dominator now... 757 ID->addNewBlock(NewBB, Dom); 758 NewBBIDom = Dom; // Reuse this if calculating DominatorTree info... 759 760 // If NewBB strictly dominates other blocks, we need to update their idom's 761 // now. The only block that need adjustment is the NewBBSucc block, whose 762 // idom should currently be set to PredBlocks[0]. 763 if (NewBBDominatesNewBBSucc) 764 ID->setImmediateDominator(NewBBSucc, NewBB); 765 } 766 767 // Update DominatorTree information if it is active. 768 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 769 // If we don't have ImmediateDominator info around, calculate the idom as 770 // above. 771 DominatorTree::Node *NewBBIDomNode; 772 if (NewBBIDom) { 773 NewBBIDomNode = DT->getNode(NewBBIDom); 774 } else { 775 NewBBIDomNode = DT->getNode(PredBlocks[0]); // Random pred 776 while (!NewBBDomSet.count(NewBBIDomNode->getBlock())) { 777 NewBBIDomNode = NewBBIDomNode->getIDom(); 778 assert(NewBBIDomNode && "No shared dominator found??"); 779 } 780 } 781 782 // Create the new dominator tree node... and set the idom of NewBB. 783 DominatorTree::Node *NewBBNode = DT->createNewNode(NewBB, NewBBIDomNode); 784 785 // If NewBB strictly dominates other blocks, then it is now the immediate 786 // dominator of NewBBSucc. Update the dominator tree as appropriate. 787 if (NewBBDominatesNewBBSucc) { 788 DominatorTree::Node *NewBBSuccNode = DT->getNode(NewBBSucc); 789 DT->changeImmediateDominator(NewBBSuccNode, NewBBNode); 790 } 791 } 792 793 // Update dominance frontier information... 794 if (DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 795 // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the 796 // DF(PredBlocks[0]) without the stuff that the new block does not dominate 797 // a predecessor of. 798 if (NewBBDominatesNewBBSucc) { 799 DominanceFrontier::iterator DFI = DF->find(PredBlocks[0]); 800 if (DFI != DF->end()) { 801 DominanceFrontier::DomSetType Set = DFI->second; 802 // Filter out stuff in Set that we do not dominate a predecessor of. 803 for (DominanceFrontier::DomSetType::iterator SetI = Set.begin(), 804 E = Set.end(); SetI != E;) { 805 bool DominatesPred = false; 806 for (pred_iterator PI = pred_begin(*SetI), E = pred_end(*SetI); 807 PI != E; ++PI) 808 if (DS.dominates(NewBB, *PI)) 809 DominatesPred = true; 810 if (!DominatesPred) 811 Set.erase(SetI++); 812 else 813 ++SetI; 814 } 815 816 DF->addBasicBlock(NewBB, Set); 817 } 818 819 } else { 820 // DF(NewBB) is {NewBBSucc} because NewBB does not strictly dominate 821 // NewBBSucc, but it does dominate itself (and there is an edge (NewBB -> 822 // NewBBSucc)). NewBBSucc is the single successor of NewBB. 823 DominanceFrontier::DomSetType NewDFSet; 824 NewDFSet.insert(NewBBSucc); 825 DF->addBasicBlock(NewBB, NewDFSet); 826 } 827 828 // Now we must loop over all of the dominance frontiers in the function, 829 // replacing occurrences of NewBBSucc with NewBB in some cases. All 830 // blocks that dominate a block in PredBlocks and contained NewBBSucc in 831 // their dominance frontier must be updated to contain NewBB instead. 832 // 833 for (unsigned i = 0, e = PredBlocks.size(); i != e; ++i) { 834 BasicBlock *Pred = PredBlocks[i]; 835 // Get all of the dominators of the predecessor... 836 const DominatorSet::DomSetType &PredDoms = DS.getDominators(Pred); 837 for (DominatorSet::DomSetType::const_iterator PDI = PredDoms.begin(), 838 PDE = PredDoms.end(); PDI != PDE; ++PDI) { 839 BasicBlock *PredDom = *PDI; 840 841 // If the NewBBSucc node is in DF(PredDom), then PredDom didn't 842 // dominate NewBBSucc but did dominate a predecessor of it. Now we 843 // change this entry to include NewBB in the DF instead of NewBBSucc. 844 DominanceFrontier::iterator DFI = DF->find(PredDom); 845 assert(DFI != DF->end() && "No dominance frontier for node?"); 846 if (DFI->second.count(NewBBSucc)) { 847 // If NewBBSucc should not stay in our dominator frontier, remove it. 848 // We remove it unless there is a predecessor of NewBBSucc that we 849 // dominate, but we don't strictly dominate NewBBSucc. 850 bool ShouldRemove = true; 851 if (PredDom == NewBBSucc || !DS.dominates(PredDom, NewBBSucc)) { 852 // Okay, we know that PredDom does not strictly dominate NewBBSucc. 853 // Check to see if it dominates any predecessors of NewBBSucc. 854 for (pred_iterator PI = pred_begin(NewBBSucc), 855 E = pred_end(NewBBSucc); PI != E; ++PI) 856 if (DS.dominates(PredDom, *PI)) { 857 ShouldRemove = false; 858 break; 859 } 860 } 861 862 if (ShouldRemove) 863 DF->removeFromFrontier(DFI, NewBBSucc); 864 DF->addToFrontier(DFI, NewBB); 865 } 866 } 867 } 868 } 869} 870 871