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