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