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