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