LoopSimplify.cpp revision 0a205a459884ec745df1c529396dd921f029dafd
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/LLVMContext.h" 41#include "llvm/Type.h" 42#include "llvm/Analysis/AliasAnalysis.h" 43#include "llvm/Analysis/Dominators.h" 44#include "llvm/Analysis/LoopInfo.h" 45#include "llvm/Transforms/Utils/BasicBlockUtils.h" 46#include "llvm/Transforms/Utils/Local.h" 47#include "llvm/Support/CFG.h" 48#include "llvm/Support/Compiler.h" 49#include "llvm/ADT/SetOperations.h" 50#include "llvm/ADT/SetVector.h" 51#include "llvm/ADT/Statistic.h" 52#include "llvm/ADT/DepthFirstIterator.h" 53using namespace llvm; 54 55STATISTIC(NumInserted, "Number of pre-header or exit blocks inserted"); 56STATISTIC(NumNested , "Number of nested loops split out"); 57 58namespace { 59 struct VISIBILITY_HIDDEN LoopSimplify : public FunctionPass { 60 static char ID; // Pass identification, replacement for typeid 61 LoopSimplify() : FunctionPass(&ID) {} 62 63 // AA - If we have an alias analysis object to update, this is it, otherwise 64 // this is null. 65 AliasAnalysis *AA; 66 LoopInfo *LI; 67 DominatorTree *DT; 68 virtual bool runOnFunction(Function &F); 69 70 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 71 // We need loop information to identify the loops... 72 AU.addRequired<LoopInfo>(); 73 AU.addRequired<DominatorTree>(); 74 75 AU.addPreserved<LoopInfo>(); 76 AU.addPreserved<DominatorTree>(); 77 AU.addPreserved<DominanceFrontier>(); 78 AU.addPreserved<AliasAnalysis>(); 79 AU.addPreservedID(BreakCriticalEdgesID); // No critical edges added. 80 } 81 82 /// verifyAnalysis() - Verify loop nest. 83 void verifyAnalysis() const { 84#ifndef NDEBUG 85 LoopInfo *NLI = &getAnalysis<LoopInfo>(); 86 for (LoopInfo::iterator I = NLI->begin(), E = NLI->end(); I != E; ++I) 87 (*I)->verifyLoop(); 88#endif 89 } 90 91 private: 92 bool ProcessLoop(Loop *L); 93 BasicBlock *RewriteLoopExitBlock(Loop *L, BasicBlock *Exit); 94 void InsertPreheaderForLoop(Loop *L); 95 Loop *SeparateNestedLoop(Loop *L); 96 void InsertUniqueBackedgeBlock(Loop *L); 97 void PlaceSplitBlockCarefully(BasicBlock *NewBB, 98 SmallVectorImpl<BasicBlock*> &SplitPreds, 99 Loop *L); 100 }; 101} 102 103char LoopSimplify::ID = 0; 104static RegisterPass<LoopSimplify> 105X("loopsimplify", "Canonicalize natural loops", true); 106 107// Publically exposed interface to pass... 108const PassInfo *const llvm::LoopSimplifyID = &X; 109FunctionPass *llvm::createLoopSimplifyPass() { return new LoopSimplify(); } 110 111/// runOnFunction - Run down all loops in the CFG (recursively, but we could do 112/// it in any convenient order) inserting preheaders... 113/// 114bool LoopSimplify::runOnFunction(Function &F) { 115 bool Changed = false; 116 LI = &getAnalysis<LoopInfo>(); 117 AA = getAnalysisIfAvailable<AliasAnalysis>(); 118 DT = &getAnalysis<DominatorTree>(); 119 120 // Check to see that no blocks (other than the header) in loops have 121 // predecessors that are not in loops. This is not valid for natural loops, 122 // but can occur if the blocks are unreachable. Since they are unreachable we 123 // can just shamelessly destroy their terminators to make them not branch into 124 // the loop! 125 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 126 // This case can only occur for unreachable blocks. Blocks that are 127 // unreachable can't be in loops, so filter those blocks out. 128 if (LI->getLoopFor(BB)) continue; 129 130 bool BlockUnreachable = false; 131 TerminatorInst *TI = BB->getTerminator(); 132 133 // Check to see if any successors of this block are non-loop-header loops 134 // that are not the header. 135 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 136 // If this successor is not in a loop, BB is clearly ok. 137 Loop *L = LI->getLoopFor(TI->getSuccessor(i)); 138 if (!L) continue; 139 140 // If the succ is the loop header, and if L is a top-level loop, then this 141 // is an entrance into a loop through the header, which is also ok. 142 if (L->getHeader() == TI->getSuccessor(i) && L->getParentLoop() == 0) 143 continue; 144 145 // Otherwise, this is an entrance into a loop from some place invalid. 146 // Either the loop structure is invalid and this is not a natural loop (in 147 // which case the compiler is buggy somewhere else) or BB is unreachable. 148 BlockUnreachable = true; 149 break; 150 } 151 152 // If this block is ok, check the next one. 153 if (!BlockUnreachable) continue; 154 155 // Otherwise, this block is dead. To clean up the CFG and to allow later 156 // loop transformations to ignore this case, we delete the edges into the 157 // loop by replacing the terminator. 158 159 // Remove PHI entries from the successors. 160 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 161 TI->getSuccessor(i)->removePredecessor(BB); 162 163 // Add a new unreachable instruction before the old terminator. 164 new UnreachableInst(TI); 165 166 // Delete the dead terminator. 167 if (AA) AA->deleteValue(TI); 168 if (!TI->use_empty()) 169 TI->replaceAllUsesWith(Context->getUndef(TI->getType())); 170 TI->eraseFromParent(); 171 Changed |= true; 172 } 173 174 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 175 Changed |= ProcessLoop(*I); 176 177 return Changed; 178} 179 180/// ProcessLoop - Walk the loop structure in depth first order, ensuring that 181/// all loops have preheaders. 182/// 183bool LoopSimplify::ProcessLoop(Loop *L) { 184 bool Changed = false; 185ReprocessLoop: 186 187 // Canonicalize inner loops before outer loops. Inner loop canonicalization 188 // can provide work for the outer loop to canonicalize. 189 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 190 Changed |= ProcessLoop(*I); 191 192 assert(L->getBlocks()[0] == L->getHeader() && 193 "Header isn't first block in loop?"); 194 195 // Does the loop already have a preheader? If so, don't insert one. 196 if (L->getLoopPreheader() == 0) { 197 InsertPreheaderForLoop(L); 198 NumInserted++; 199 Changed = true; 200 } 201 202 // Next, check to make sure that all exit nodes of the loop only have 203 // predecessors that are inside of the loop. This check guarantees that the 204 // loop preheader/header will dominate the exit blocks. If the exit block has 205 // predecessors from outside of the loop, split the edge now. 206 SmallVector<BasicBlock*, 8> ExitBlocks; 207 L->getExitBlocks(ExitBlocks); 208 209 SetVector<BasicBlock*> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end()); 210 for (SetVector<BasicBlock*>::iterator I = ExitBlockSet.begin(), 211 E = ExitBlockSet.end(); I != E; ++I) { 212 BasicBlock *ExitBlock = *I; 213 for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock); 214 PI != PE; ++PI) 215 // Must be exactly this loop: no subloops, parent loops, or non-loop preds 216 // allowed. 217 if (!L->contains(*PI)) { 218 RewriteLoopExitBlock(L, ExitBlock); 219 NumInserted++; 220 Changed = true; 221 break; 222 } 223 } 224 225 // If the header has more than two predecessors at this point (from the 226 // preheader and from multiple backedges), we must adjust the loop. 227 unsigned NumBackedges = L->getNumBackEdges(); 228 if (NumBackedges != 1) { 229 // If this is really a nested loop, rip it out into a child loop. Don't do 230 // this for loops with a giant number of backedges, just factor them into a 231 // common backedge instead. 232 if (NumBackedges < 8) { 233 if (Loop *NL = SeparateNestedLoop(L)) { 234 ++NumNested; 235 // This is a big restructuring change, reprocess the whole loop. 236 ProcessLoop(NL); 237 Changed = true; 238 // GCC doesn't tail recursion eliminate this. 239 goto ReprocessLoop; 240 } 241 } 242 243 // If we either couldn't, or didn't want to, identify nesting of the loops, 244 // insert a new block that all backedges target, then make it jump to the 245 // loop header. 246 InsertUniqueBackedgeBlock(L); 247 NumInserted++; 248 Changed = true; 249 } 250 251 // Scan over the PHI nodes in the loop header. Since they now have only two 252 // incoming values (the loop is canonicalized), we may have simplified the PHI 253 // down to 'X = phi [X, Y]', which should be replaced with 'Y'. 254 PHINode *PN; 255 for (BasicBlock::iterator I = L->getHeader()->begin(); 256 (PN = dyn_cast<PHINode>(I++)); ) 257 if (Value *V = PN->hasConstantValue()) { 258 if (AA) AA->deleteValue(PN); 259 PN->replaceAllUsesWith(V); 260 PN->eraseFromParent(); 261 } 262 263 // If this loop has muliple exits and the exits all go to the same 264 // block, attempt to merge the exits. This helps several passes, such 265 // as LoopRotation, which do not support loops with multiple exits. 266 // SimplifyCFG also does this (and this code uses the same utility 267 // function), however this code is loop-aware, where SimplifyCFG is 268 // not. That gives it the advantage of being able to hoist 269 // loop-invariant instructions out of the way to open up more 270 // opportunities, and the disadvantage of having the responsibility 271 // to preserve dominator information. 272 if (ExitBlocks.size() > 1 && L->getUniqueExitBlock()) { 273 SmallVector<BasicBlock*, 8> ExitingBlocks; 274 L->getExitingBlocks(ExitingBlocks); 275 for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { 276 BasicBlock *ExitingBlock = ExitingBlocks[i]; 277 if (!ExitingBlock->getSinglePredecessor()) continue; 278 BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); 279 if (!BI || !BI->isConditional()) continue; 280 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); 281 if (!CI || CI->getParent() != ExitingBlock) continue; 282 283 // Attempt to hoist out all instructions except for the 284 // comparison and the branch. 285 bool AllInvariant = true; 286 for (BasicBlock::iterator I = ExitingBlock->begin(); &*I != BI; ) { 287 Instruction *Inst = I++; 288 if (Inst == CI) 289 continue; 290 if (Inst->isTrapping()) { 291 AllInvariant = false; 292 break; 293 } 294 for (unsigned j = 0, f = Inst->getNumOperands(); j != f; ++j) 295 if (!L->isLoopInvariant(Inst->getOperand(j))) { 296 AllInvariant = false; 297 break; 298 } 299 if (!AllInvariant) 300 break; 301 // Hoist. 302 Inst->moveBefore(L->getLoopPreheader()->getTerminator()); 303 } 304 if (!AllInvariant) continue; 305 306 // The block has now been cleared of all instructions except for 307 // a comparison and a conditional branch. SimplifyCFG may be able 308 // to fold it now. 309 if (!FoldBranchToCommonDest(BI)) continue; 310 311 // Success. The block is now dead, so remove it from the loop, 312 // update the dominator tree and dominance frontier, and delete it. 313 assert(pred_begin(ExitingBlock) == pred_end(ExitingBlock)); 314 Changed = true; 315 LI->removeBlock(ExitingBlock); 316 317 DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>(); 318 DomTreeNode *Node = DT->getNode(ExitingBlock); 319 const std::vector<DomTreeNodeBase<BasicBlock> *> &Children = 320 Node->getChildren(); 321 for (unsigned k = 0, g = Children.size(); k != g; ++k) { 322 DT->changeImmediateDominator(Children[k], Node->getIDom()); 323 if (DF) DF->changeImmediateDominator(Children[k]->getBlock(), 324 Node->getIDom()->getBlock(), 325 DT); 326 } 327 DT->eraseNode(ExitingBlock); 328 if (DF) DF->removeBlock(ExitingBlock); 329 330 BI->getSuccessor(0)->removePredecessor(ExitingBlock); 331 BI->getSuccessor(1)->removePredecessor(ExitingBlock); 332 ExitingBlock->eraseFromParent(); 333 } 334 } 335 336 return Changed; 337} 338 339/// InsertPreheaderForLoop - Once we discover that a loop doesn't have a 340/// preheader, this method is called to insert one. This method has two phases: 341/// preheader insertion and analysis updating. 342/// 343void LoopSimplify::InsertPreheaderForLoop(Loop *L) { 344 BasicBlock *Header = L->getHeader(); 345 346 // Compute the set of predecessors of the loop that are not in the loop. 347 SmallVector<BasicBlock*, 8> OutsideBlocks; 348 for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); 349 PI != PE; ++PI) 350 if (!L->contains(*PI)) // Coming in from outside the loop? 351 OutsideBlocks.push_back(*PI); // Keep track of it... 352 353 // Split out the loop pre-header. 354 BasicBlock *NewBB = 355 SplitBlockPredecessors(Header, &OutsideBlocks[0], OutsideBlocks.size(), 356 ".preheader", this); 357 358 359 //===--------------------------------------------------------------------===// 360 // Update analysis results now that we have performed the transformation 361 // 362 363 // We know that we have loop information to update... update it now. 364 if (Loop *Parent = L->getParentLoop()) 365 Parent->addBasicBlockToLoop(NewBB, LI->getBase()); 366 367 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 368 // code layout too horribly. 369 PlaceSplitBlockCarefully(NewBB, OutsideBlocks, L); 370} 371 372/// RewriteLoopExitBlock - Ensure that the loop preheader dominates all exit 373/// blocks. This method is used to split exit blocks that have predecessors 374/// outside of the loop. 375BasicBlock *LoopSimplify::RewriteLoopExitBlock(Loop *L, BasicBlock *Exit) { 376 SmallVector<BasicBlock*, 8> LoopBlocks; 377 for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) 378 if (L->contains(*I)) 379 LoopBlocks.push_back(*I); 380 381 assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); 382 BasicBlock *NewBB = SplitBlockPredecessors(Exit, &LoopBlocks[0], 383 LoopBlocks.size(), ".loopexit", 384 this); 385 386 // Update Loop Information - we know that the new block will be in whichever 387 // loop the Exit block is in. Note that it may not be in that immediate loop, 388 // if the successor is some other loop header. In that case, we continue 389 // walking up the loop tree to find a loop that contains both the successor 390 // block and the predecessor block. 391 Loop *SuccLoop = LI->getLoopFor(Exit); 392 while (SuccLoop && !SuccLoop->contains(L->getHeader())) 393 SuccLoop = SuccLoop->getParentLoop(); 394 if (SuccLoop) 395 SuccLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 396 397 return NewBB; 398} 399 400/// AddBlockAndPredsToSet - Add the specified block, and all of its 401/// predecessors, to the specified set, if it's not already in there. Stop 402/// predecessor traversal when we reach StopBlock. 403static void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock, 404 std::set<BasicBlock*> &Blocks) { 405 std::vector<BasicBlock *> WorkList; 406 WorkList.push_back(InputBB); 407 do { 408 BasicBlock *BB = WorkList.back(); WorkList.pop_back(); 409 if (Blocks.insert(BB).second && BB != StopBlock) 410 // If BB is not already processed and it is not a stop block then 411 // insert its predecessor in the work list 412 for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 413 BasicBlock *WBB = *I; 414 WorkList.push_back(WBB); 415 } 416 } while(!WorkList.empty()); 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, DominatorTree *DT, 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) || DT->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 SmallVectorImpl<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 PHINode *PN = FindPHIToPartitionLoops(L, DT, AA); 502 if (PN == 0) return 0; // No known way to partition. 503 504 // Pull out all predecessors that have varying values in the loop. This 505 // handles the case when a PHI node has multiple instances of itself as 506 // arguments. 507 SmallVector<BasicBlock*, 8> OuterLoopPreds; 508 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 509 if (PN->getIncomingValue(i) != PN || 510 !L->contains(PN->getIncomingBlock(i))) 511 OuterLoopPreds.push_back(PN->getIncomingBlock(i)); 512 513 BasicBlock *Header = L->getHeader(); 514 BasicBlock *NewBB = SplitBlockPredecessors(Header, &OuterLoopPreds[0], 515 OuterLoopPreds.size(), 516 ".outer", this); 517 518 // Make sure that NewBB is put someplace intelligent, which doesn't mess up 519 // code layout too horribly. 520 PlaceSplitBlockCarefully(NewBB, OuterLoopPreds, L); 521 522 // Create the new outer loop. 523 Loop *NewOuter = new Loop(); 524 525 // Change the parent loop to use the outer loop as its child now. 526 if (Loop *Parent = L->getParentLoop()) 527 Parent->replaceChildLoopWith(L, NewOuter); 528 else 529 LI->changeTopLevelLoop(L, NewOuter); 530 531 // This block is going to be our new header block: add it to this loop and all 532 // parent loops. 533 NewOuter->addBasicBlockToLoop(NewBB, LI->getBase()); 534 535 // L is now a subloop of our outer loop. 536 NewOuter->addChildLoop(L); 537 538 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 539 I != E; ++I) 540 NewOuter->addBlockEntry(*I); 541 542 // Determine which blocks should stay in L and which should be moved out to 543 // the Outer loop now. 544 std::set<BasicBlock*> BlocksInL; 545 for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); PI!=E; ++PI) 546 if (DT->dominates(Header, *PI)) 547 AddBlockAndPredsToSet(*PI, Header, BlocksInL); 548 549 550 // Scan all of the loop children of L, moving them to OuterLoop if they are 551 // not part of the inner loop. 552 const std::vector<Loop*> &SubLoops = L->getSubLoops(); 553 for (size_t I = 0; I != SubLoops.size(); ) 554 if (BlocksInL.count(SubLoops[I]->getHeader())) 555 ++I; // Loop remains in L 556 else 557 NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + 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 = BasicBlock::Create(Header->getName()+".backedge", F); 597 BranchInst *BETerminator = BranchInst::Create(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 = PHINode::Create(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->getBase()); 670 671 // Update dominator information 672 DT->splitBlock(BEBlock); 673 if (DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>()) 674 DF->splitBlock(BEBlock); 675} 676