LoopSimplify.cpp revision 2aa93efa0c983449e5464165e80ebd9c0fb5f6c1
1//===- LoopSimplify.cpp - Loop Canonicalization Pass ----------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/Constants.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/Transforms/Utils/BasicBlockUtils.h" 45#include "llvm/Transforms/Utils/Local.h" 46#include "llvm/Support/CFG.h" 47#include "llvm/Support/Compiler.h" 48#include "llvm/ADT/SetOperations.h" 49#include "llvm/ADT/SetVector.h" 50#include "llvm/ADT/Statistic.h" 51#include "llvm/ADT/DepthFirstIterator.h" 52using namespace llvm; 53 54STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 55STATISTIC(NumNested , "Number of nested loops split out"); 56 57namespace { 58 struct VISIBILITY_HIDDEN LoopSimplify : public FunctionPass { 59 static char ID; // Pass identification, replacement for typeid 60 LoopSimplify() : FunctionPass(&ID) {} 61 62 // AA - If we have an alias analysis object to update, this is it, otherwise 63 // this is null. 64 AliasAnalysis *AA; 65 LoopInfo *LI; 66 DominatorTree *DT; 67 virtual bool runOnFunction(Function &F); 68 69 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 70 // We need loop information to identify the loops... 71 AU.addRequired<LoopInfo>(); 72 AU.addRequired<DominatorTree>(); 73 74 AU.addPreserved<LoopInfo>(); 75 AU.addPreserved<DominatorTree>(); 76 AU.addPreserved<DominanceFrontier>(); 77 AU.addPreserved<AliasAnalysis>(); 78 AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 79 } 80 81 /// verifyAnalysis() - Verify loop nest. 82 void verifyAnalysis() const { 83#ifndef NDEBUG 84 LoopInfo *NLI = &getAnalysis<LoopInfo>(); 85 for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I) 86 (*I)->verifyLoop(); 87#endif 88 } 89 90 private: 91 bool ProcessLoop(Loop *L); 92 BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 93 void InsertPreheaderForLoop(Loop *L); 94 Loop *SeparateNestedLoop(Loop *L); 95 void InsertUniqueBackedgeBlock(Loop *L); 96 void PlaceSplitBlockCarefully(BasicBlock *NewBB, 97 SmallVectorImpl<BasicBlock*> &SplitPreds, 98 Loop *L); 99 }; 100} 101 102char LoopSimplify::ID = 0; 103static RegisterPass<LoopSimplify> 104X("loopsimplify", "Canonicalize natural loops", true); 105 106// Publically exposed interface to pass... 107const PassInfo *const llvm::LoopSimplifyID = &X; 108FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 109 110/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 111/// it in any convenient order) inserting preheaders... 112/// 113bool LoopSimplify::runOnFunction(Function &F) { 114 bool Changed = false; 115 LI = &getAnalysis<LoopInfo>(); 116 AA = getAnalysisIfAvailable<AliasAnalysis>(); 117 DT = &getAnalysis<DominatorTree>(); 118 119 // Check to see that no blocks (other than the header) in loops have 120 // predecessors that are not in loops. This is not valid for natural loops, 121 // but can occur if the blocks are unreachable. Since they are unreachable we 122 // can just shamelessly destroy their terminators to make them not branch into 123 // the loop! 124 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 125 // This case can only occur for unreachable blocks. Blocks that are 126 // unreachable can't be in loops, so filter those blocks out. 127 if (LI->getLoopFor(BB)) continue; 128 129 bool BlockUnreachable = false; 130 TerminatorInst *TI = BB->getTerminator(); 131 132 // Check to see if any successors of this block are non-loop-header loops 133 // that are not the header. 134 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 135 // If this successor is not in a loop, BB is clearly ok. 136 Loop *L = LI->getLoopFor(TI->getSuccessor(i)); 137 if (!L) continue; 138 139 // If the succ is the loop header, and if L is a top-level loop, then this 140 // is an entrance into a loop through the header, which is also ok. 141 if (L->getHeader() == TI->getSuccessor(i) && L->getParentLoop() == 0) 142 continue; 143 144 // Otherwise, this is an entrance into a loop from some place invalid. 145 // Either the loop structure is invalid and this is not a natural loop (in 146 // which case the compiler is buggy somewhere else) or BB is unreachable. 147 BlockUnreachable = true; 148 break; 149 } 150 151 // If this block is ok, check the next one. 152 if (!BlockUnreachable) continue; 153 154 // Otherwise, this block is dead. To clean up the CFG and to allow later 155 // loop transformations to ignore this case, we delete the edges into the 156 // loop by replacing the terminator. 157 158 // Remove PHI entries from the successors. 159 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 160 TI->getSuccessor(i)->removePredecessor(BB); 161 162 // Add a new unreachable instruction before the old terminator. 163 new UnreachableInst(TI); 164 165 // Delete the dead terminator. 166 if (AA) AA->deleteValue(TI); 167 if (!TI->use_empty()) 168 TI->replaceAllUsesWith(UndefValue::get(TI->getType())); 169 TI->eraseFromParent(); 170 Changed |= true; 171 } 172 173 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 174 Changed |= ProcessLoop(*I); 175 176 return Changed; 177} 178 179/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 180/// all loops have preheaders. 181/// 182bool LoopSimplify::ProcessLoop(Loop *L) { 183 bool Changed = false; 184ReprocessLoop: 185 186 // Canonicalize inner loops before outer loops. Inner loop canonicalization 187 // can provide work for the outer loop to canonicalize. 188 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 189 Changed |= ProcessLoop(*I); 190 191 assert(L->getBlocks()[0] == L->getHeader() && 192 "Header isn't first block in loop?"); 193 194 // Does the loop already have a preheader? If so, don't insert one. 195 if (L->getLoopPreheader() == 0) { 196 InsertPreheaderForLoop(L); 197 NumInserted++; 198 Changed = true; 199 } 200 201 // Next, check to make sure that all exit nodes of the loop only have 202 // predecessors that are inside of the loop. This check guarantees that the 203 // loop preheader/header will dominate the exit blocks. If the exit block has 204 // predecessors from outside of the loop, split the edge now. 205 SmallVector<BasicBlock*, 8> ExitBlocks; 206 L->getExitBlocks(ExitBlocks); 207 208 SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 209 for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 210 E = ExitBlockSet.end(); I != E; ++I) { 211 BasicBlock *ExitBlock = *I; 212 for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 213 PI != PE; ++PI) 214 // Must be exactly this loop: no subloops, parent loops, or non-loop preds 215 // allowed. 216 if (!L->contains(*PI)) { 217 RewriteLoopExitBlock(L, ExitBlock); 218 NumInserted++; 219 Changed = true; 220 break; 221 } 222 } 223 224 // If the header has more than two predecessors at this point (from the 225 // preheader and from multiple backedges), we must adjust the loop. 226 unsigned NumBackedges = L->getNumBackEdges(); 227 if (NumBackedges != 1) { 228 // If this is really a nested loop, rip it out into a child loop. Don't do 229 // this for loops with a giant number of backedges, just factor them into a 230 // common backedge instead. 231 if (NumBackedges < 8) { 232 if (Loop *NL = SeparateNestedLoop(L)) { 233 ++NumNested; 234 // This is a big restructuring change, reprocess the whole loop. 235 ProcessLoop(NL); 236 Changed = true; 237 // GCC doesn't tail recursion eliminate this. 238 goto ReprocessLoop; 239 } 240 } 241 242 // If we either couldn't, or didn't want to, identify nesting of the loops, 243 // insert a new block that all backedges target, then make it jump to the 244 // loop header. 245 InsertUniqueBackedgeBlock(L); 246 NumInserted++; 247 Changed = true; 248 } 249 250 // Scan over the PHI nodes in the loop header. Since they now have only two 251 // incoming values (the loop is canonicalized), we may have simplified the PHI 252 // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 253 PHINode *PN; 254 for (BasicBlock::iterator I = L->getHeader()->begin(); 255 (PN = dyn_cast<PHINode>(I++)); ) 256 if (Value *V = PN->hasConstantValue()) { 257 if (AA) AA->deleteValue(PN); 258 PN->replaceAllUsesWith(V); 259 PN->eraseFromParent(); 260 } 261 262 // If this loop has muliple exits and the exits all go to the same 263 // block, attempt to merge the exits. This helps several passes, such 264 // as LoopRotation, which do not support loops with multiple exits. 265 // SimplifyCFG also does this (and this code uses the same utility 266 // function), however this code is loop-aware, where SimplifyCFG is 267 // not. That gives it the advantage of being able to hoist 268 // loop-invariant instructions out of the way to open up more 269 // opportunities, and the disadvantage of having the responsibility 270 // to preserve dominator information. 271 if (ExitBlocks.size() > 1 && L->getUniqueExitBlock()) { 272 SmallVector<BasicBlock*, 8> ExitingBlocks; 273 L->getExitingBlocks(ExitingBlocks); 274 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 275 BasicBlock *ExitingBlock = ExitingBlocks[i]; 276 if (!ExitingBlock->getSinglePredecessor()) continue; 277 BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 278 if (!BI || !BI->isConditional()) continue; 279 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 280 if (!CI || CI->getParent() != ExitingBlock) continue; 281 282 // Attempt to hoist out all instructions except for the 283 // comparison and the branch. 284 bool AllInvariant = true; 285 for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 286 Instruction *Inst = I++; 287 if (Inst == CI) 288 continue; 289 if (Inst->isTrapping()) { 290 AllInvariant = false; 291 break; 292 } 293 for (unsigned j = 0, f = Inst->getNumOperands(); j != f; ++j) 294 if (!L->isLoopInvariant(Inst->getOperand(j))) { 295 AllInvariant = false; 296 break; 297 } 298 if (!AllInvariant) 299 break; 300 // Hoist. 301 Inst->moveBefore(L->getLoopPreheader()->getTerminator()); 302 } 303 if (!AllInvariant) continue; 304 305 // The block has now been cleared of all instructions except for 306 // a comparison and a conditional branch. SimplifyCFG may be able 307 // to fold it now. 308 if (!FoldBranchToCommonDest(BI)) continue; 309 310 // Success. The block is now dead, so remove it from the loop, 311 // update the dominator tree and dominance frontier, and delete it. 312 assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 313 Changed = true; 314 LI->removeBlock(ExitingBlock); 315 316 DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>(); 317 DomTreeNode *Node = DT->getNode(ExitingBlock); 318 const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 319 Node->getChildren(); 320 for (unsigned k = 0, g = Children.size(); k != g; ++k) { 321 DT->changeImmediateDominator(Children[k], Node->getIDom()); 322 if (DF) DF->changeImmediateDominator(Children[k]->getBlock(), 323 Node->getIDom()->getBlock(), 324 DT); 325 } 326 DT->eraseNode(ExitingBlock); 327 if (DF) DF->removeBlock(ExitingBlock); 328 329 BI->getSuccessor(0)->removePredecessor(ExitingBlock); 330 BI->getSuccessor(1)->removePredecessor(ExitingBlock); 331 ExitingBlock->eraseFromParent(); 332 } 333 } 334 335 return Changed; 336} 337 338/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 339/// preheader, this method is called to insert one. This method has two phases: 340/// preheader insertion and analysis updating. 341/// 342void LoopSimplify::InsertPreheaderForLoop(Loop *L) { 343 BasicBlock *Header = L->getHeader(); 344 345 // Compute the set of predecessors of the loop that are not in the loop. 346 SmallVector<BasicBlock*, 8> OutsideBlocks; 347 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 348 PI != PE; ++PI) 349 if (!L->contains(*PI)) // Coming in from outside the loop? 350 OutsideBlocks.push_back(*PI); // Keep track of it... 351 352 // Split out the loop pre-header. 353 BasicBlock *NewBB = 354 SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), 355 ".preheader", this); 356 357 358 //===--------------------------------------------------------------------===// 359 // Update analysis results now that we have performed the transformation 360 // 361 362 // We know that we have loop information to update... update it now. 363 if (Loop *Parent = L->getParentLoop()) 364 Parent->addBasicBlockToLoop(NewBB, LI->getBase()); 365 366 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 367 // code layout too horribly. 368 PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); 369} 370 371/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 372/// blocks. This method is used to split exit blocks that have predecessors 373/// outside of the loop. 374BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 375 SmallVector<BasicBlock*, 8> LoopBlocks; 376 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 377 if (L->contains(*I)) 378 LoopBlocks.push_back(*I); 379 380 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 381 BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], 382 LoopBlocks.size(), ".loopexit", 383 this); 384 385 // Update Loop Information - we know that the new block will be in whichever 386 // loop the Exit block is in. Note that it may not be in that immediate loop, 387 // if the successor is some other loop header. In that case, we continue 388 // walking up the loop tree to find a loop that contains both the successor 389 // block and the predecessor block. 390 Loop *SuccLoop = LI->getLoopFor(Exit); 391 while (SuccLoop && !SuccLoop->contains(L->getHeader())) 392 SuccLoop = SuccLoop->getParentLoop(); 393 if (SuccLoop) 394 SuccLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 395 396 return NewBB; 397} 398 399/// AddBlockAndPredsToSet - Add the specified block, and all of its 400/// predecessors, to the specified set, if it's not already in there. Stop 401/// predecessor traversal when we reach StopBlock. 402static void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 403 std::set<BasicBlock*> &Blocks) { 404 std::vector<BasicBlock *> WorkList; 405 WorkList.push_back(InputBB); 406 do { 407 BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 408 if (Blocks.insert(BB).second && BB != StopBlock) 409 // If BB is not already processed and it is not a stop block then 410 // insert its predecessor in the work list 411 for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 412 BasicBlock *WBB = *I; 413 WorkList.push_back(WBB); 414 } 415 } while(!WorkList.empty()); 416} 417 418/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a 419/// PHI node that tells us how to partition the loops. 420static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT, 421 AliasAnalysis *AA) { 422 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) { 423 PHINode *PN = cast<PHINode>(I); 424 ++I; 425 if (Value *V = PN->hasConstantValue()) 426 if (!isa<Instruction>(V) || DT->dominates(cast<Instruction>(V), PN)) { 427 // This is a degenerate PHI already, don't modify it! 428 PN->replaceAllUsesWith(V); 429 if (AA) AA->deleteValue(PN); 430 PN->eraseFromParent(); 431 continue; 432 } 433 434 // Scan this PHI node looking for a use of the PHI node by itself. 435 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 436 if (PN->getIncomingValue(i) == PN && 437 L->contains(PN->getIncomingBlock(i))) 438 // We found something tasty to remove. 439 return PN; 440 } 441 return 0; 442} 443 444// PlaceSplitBlockCarefully - If the block isn't already, move the new block to 445// right after some 'outside block' block. This prevents the preheader from 446// being placed inside the loop body, e.g. when the loop hasn't been rotated. 447void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB, 448 SmallVectorImpl<BasicBlock*> &SplitPreds, 449 Loop *L) { 450 // Check to see if NewBB is already well placed. 451 Function::iterator BBI = NewBB; --BBI; 452 for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 453 if (&*BBI == SplitPreds[i]) 454 return; 455 } 456 457 // If it isn't already after an outside block, move it after one. This is 458 // always good as it makes the uncond branch from the outside block into a 459 // fall-through. 460 461 // Figure out *which* outside block to put this after. Prefer an outside 462 // block that neighbors a BB actually in the loop. 463 BasicBlock *FoundBB = 0; 464 for (unsigned i = 0, e = SplitPreds.size(); i != e; ++i) { 465 Function::iterator BBI = SplitPreds[i]; 466 if (++BBI != NewBB->getParent()->end() && 467 L->contains(BBI)) { 468 FoundBB = SplitPreds[i]; 469 break; 470 } 471 } 472 473 // If our heuristic for a *good* bb to place this after doesn't find 474 // anything, just pick something. It's likely better than leaving it within 475 // the loop. 476 if (!FoundBB) 477 FoundBB = SplitPreds[0]; 478 NewBB->moveAfter(FoundBB); 479} 480 481 482/// SeparateNestedLoop - If this loop has multiple backedges, try to pull one of 483/// them out into a nested loop. This is important for code that looks like 484/// this: 485/// 486/// Loop: 487/// ... 488/// br cond, Loop, Next 489/// ... 490/// br cond2, Loop, Out 491/// 492/// To identify this common case, we look at the PHI nodes in the header of the 493/// loop. PHI nodes with unchanging values on one backedge correspond to values 494/// that change in the "outer" loop, but not in the "inner" loop. 495/// 496/// If we are able to separate out a loop, return the new outer loop that was 497/// created. 498/// 499Loop *LoopSimplify::SeparateNestedLoop(Loop *L) { 500 PHINode *PN = FindPHIToPartitionLoops(L, DT, AA); 501 if (PN == 0) return 0; // No known way to partition. 502 503 // Pull out all predecessors that have varying values in the loop. This 504 // handles the case when a PHI node has multiple instances of itself as 505 // arguments. 506 SmallVector<BasicBlock*, 8> OuterLoopPreds; 507 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 508 if (PN->getIncomingValue(i) != PN || 509 !L->contains(PN->getIncomingBlock(i))) 510 OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 511 512 BasicBlock *Header = L->getHeader(); 513 BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0], 514 OuterLoopPreds.size(), 515 ".outer", this); 516 517 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 518 // code layout too horribly. 519 PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 520 521 // Create the new outer loop. 522 Loop *NewOuter = new Loop(); 523 524 // Change the parent loop to use the outer loop as its child now. 525 if (Loop *Parent = L->getParentLoop()) 526 Parent->replaceChildLoopWith(L, NewOuter); 527 else 528 LI->changeTopLevelLoop(L, NewOuter); 529 530 // This block is going to be our new header block: add it to this loop and all 531 // parent loops. 532 NewOuter->addBasicBlockToLoop(NewBB, LI->getBase()); 533 534 // L is now a subloop of our outer loop. 535 NewOuter->addChildLoop(L); 536 537 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 538 I != E; ++I) 539 NewOuter->addBlockEntry(*I); 540 541 // Determine which blocks should stay in L and which should be moved out to 542 // the Outer loop now. 543 std::set<BasicBlock*> BlocksInL; 544 for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 545 if (DT->dominates(Header, *PI)) 546 AddBlockAndPredsToSet(*PI, Header, BlocksInL); 547 548 549 // Scan all of the loop children of L, moving them to OuterLoop if they are 550 // not part of the inner loop. 551 const std::vector<Loop*> &SubLoops = L->getSubLoops(); 552 for (size_t I = 0; I != SubLoops.size(); ) 553 if (BlocksInL.count(SubLoops[I]->getHeader())) 554 ++I; // Loop remains in L 555 else 556 NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); 557 558 // Now that we know which blocks are in L and which need to be moved to 559 // OuterLoop, move any blocks that need it. 560 for (unsigned i = 0; i != L->getBlocks().size(); ++i) { 561 BasicBlock *BB = L->getBlocks()[i]; 562 if (!BlocksInL.count(BB)) { 563 // Move this block to the parent, updating the exit blocks sets 564 L->removeBlockFromLoop(BB); 565 if ((*LI)[BB] == L) 566 LI->changeLoopFor(BB, NewOuter); 567 --i; 568 } 569 } 570 571 return NewOuter; 572} 573 574 575 576/// InsertUniqueBackedgeBlock - This method is called when the specified loop 577/// has more than one backedge in it. If this occurs, revector all of these 578/// backedges to target a new basic block and have that block branch to the loop 579/// header. This ensures that loops have exactly one backedge. 580/// 581void LoopSimplify::InsertUniqueBackedgeBlock(Loop *L) { 582 assert(L->getNumBackEdges() > 1 && "Must have > 1 backedge!"); 583 584 // Get information about the loop 585 BasicBlock *Preheader = L->getLoopPreheader(); 586 BasicBlock *Header = L->getHeader(); 587 Function *F = Header->getParent(); 588 589 // Figure out which basic blocks contain back-edges to the loop header. 590 std::vector<BasicBlock*> BackedgeBlocks; 591 for (pred_iterator I = pred_begin(Header), E = pred_end(Header); I != E; ++I) 592 if (*I != Preheader) BackedgeBlocks.push_back(*I); 593 594 // Create and insert the new backedge block... 595 BasicBlock *BEBlock = BasicBlock::Create(Header->getName()+".backedge", F); 596 BranchInst *BETerminator = BranchInst::Create(Header, BEBlock); 597 598 // Move the new backedge block to right after the last backedge block. 599 Function::iterator InsertPos = BackedgeBlocks.back(); ++InsertPos; 600 F->getBasicBlockList().splice(InsertPos, F->getBasicBlockList(), BEBlock); 601 602 // Now that the block has been inserted into the function, create PHI nodes in 603 // the backedge block which correspond to any PHI nodes in the header block. 604 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 605 PHINode *PN = cast<PHINode>(I); 606 PHINode *NewPN = PHINode::Create(PN->getType(), PN->getName()+".be", 607 BETerminator); 608 NewPN->reserveOperandSpace(BackedgeBlocks.size()); 609 if (AA) AA->copyValue(PN, NewPN); 610 611 // Loop over the PHI node, moving all entries except the one for the 612 // preheader over to the new PHI node. 613 unsigned PreheaderIdx = ~0U; 614 bool HasUniqueIncomingValue = true; 615 Value *UniqueValue = 0; 616 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 617 BasicBlock *IBB = PN->getIncomingBlock(i); 618 Value *IV = PN->getIncomingValue(i); 619 if (IBB == Preheader) { 620 PreheaderIdx = i; 621 } else { 622 NewPN->addIncoming(IV, IBB); 623 if (HasUniqueIncomingValue) { 624 if (UniqueValue == 0) 625 UniqueValue = IV; 626 else if (UniqueValue != IV) 627 HasUniqueIncomingValue = false; 628 } 629 } 630 } 631 632 // Delete all of the incoming values from the old PN except the preheader's 633 assert(PreheaderIdx != ~0U && "PHI has no preheader entry??"); 634 if (PreheaderIdx != 0) { 635 PN->setIncomingValue(0, PN->getIncomingValue(PreheaderIdx)); 636 PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); 637 } 638 // Nuke all entries except the zero'th. 639 for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) 640 PN->removeIncomingValue(e-i, false); 641 642 // Finally, add the newly constructed PHI node as the entry for the BEBlock. 643 PN->addIncoming(NewPN, BEBlock); 644 645 // As an optimization, if all incoming values in the new PhiNode (which is a 646 // subset of the incoming values of the old PHI node) have the same value, 647 // eliminate the PHI Node. 648 if (HasUniqueIncomingValue) { 649 NewPN->replaceAllUsesWith(UniqueValue); 650 if (AA) AA->deleteValue(NewPN); 651 BEBlock->getInstList().erase(NewPN); 652 } 653 } 654 655 // Now that all of the PHI nodes have been inserted and adjusted, modify the 656 // backedge blocks to just to the BEBlock instead of the header. 657 for (unsigned i = 0, e = BackedgeBlocks.size(); i != e; ++i) { 658 TerminatorInst *TI = BackedgeBlocks[i]->getTerminator(); 659 for (unsigned Op = 0, e = TI->getNumSuccessors(); Op != e; ++Op) 660 if (TI->getSuccessor(Op) == Header) 661 TI->setSuccessor(Op, BEBlock); 662 } 663 664 //===--- Update all analyses which we must preserve now -----------------===// 665 666 // Update Loop Information - we know that this block is now in the current 667 // loop and all parent loops. 668 L->addBasicBlockToLoop(BEBlock, LI->getBase()); 669 670 // Update dominator information 671 DT->splitBlock(BEBlock); 672 if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>()) 673 DF->splitBlock(BEBlock); 674} 675