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