1 //===- LoopRotation.cpp - Loop Rotation 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 file implements Loop Rotation Pass. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Transforms/Scalar.h" 15 #include "llvm/ADT/Statistic.h" 16 #include "llvm/Analysis/AssumptionCache.h" 17 #include "llvm/Analysis/CodeMetrics.h" 18 #include "llvm/Analysis/InstructionSimplify.h" 19 #include "llvm/Analysis/LoopPass.h" 20 #include "llvm/Analysis/ScalarEvolution.h" 21 #include "llvm/Analysis/TargetTransformInfo.h" 22 #include "llvm/Analysis/ValueTracking.h" 23 #include "llvm/IR/CFG.h" 24 #include "llvm/IR/Dominators.h" 25 #include "llvm/IR/Function.h" 26 #include "llvm/IR/IntrinsicInst.h" 27 #include "llvm/IR/Module.h" 28 #include "llvm/Support/CommandLine.h" 29 #include "llvm/Support/Debug.h" 30 #include "llvm/Support/raw_ostream.h" 31 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 32 #include "llvm/Transforms/Utils/Local.h" 33 #include "llvm/Transforms/Utils/SSAUpdater.h" 34 #include "llvm/Transforms/Utils/ValueMapper.h" 35 using namespace llvm; 36 37 #define DEBUG_TYPE "loop-rotate" 38 39 static cl::opt<unsigned> 40 DefaultRotationThreshold("rotation-max-header-size", cl::init(16), cl::Hidden, 41 cl::desc("The default maximum header size for automatic loop rotation")); 42 43 STATISTIC(NumRotated, "Number of loops rotated"); 44 namespace { 45 46 class LoopRotate : public LoopPass { 47 public: 48 static char ID; // Pass ID, replacement for typeid 49 LoopRotate(int SpecifiedMaxHeaderSize = -1) : LoopPass(ID) { 50 initializeLoopRotatePass(*PassRegistry::getPassRegistry()); 51 if (SpecifiedMaxHeaderSize == -1) 52 MaxHeaderSize = DefaultRotationThreshold; 53 else 54 MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize); 55 } 56 57 // LCSSA form makes instruction renaming easier. 58 void getAnalysisUsage(AnalysisUsage &AU) const override { 59 AU.addRequired<AssumptionCacheTracker>(); 60 AU.addPreserved<DominatorTreeWrapperPass>(); 61 AU.addRequired<LoopInfoWrapperPass>(); 62 AU.addPreserved<LoopInfoWrapperPass>(); 63 AU.addRequiredID(LoopSimplifyID); 64 AU.addPreservedID(LoopSimplifyID); 65 AU.addRequiredID(LCSSAID); 66 AU.addPreservedID(LCSSAID); 67 AU.addPreserved<ScalarEvolution>(); 68 AU.addRequired<TargetTransformInfoWrapperPass>(); 69 } 70 71 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 72 bool simplifyLoopLatch(Loop *L); 73 bool rotateLoop(Loop *L, bool SimplifiedLatch); 74 75 private: 76 unsigned MaxHeaderSize; 77 LoopInfo *LI; 78 const TargetTransformInfo *TTI; 79 AssumptionCache *AC; 80 DominatorTree *DT; 81 }; 82 } 83 84 char LoopRotate::ID = 0; 85 INITIALIZE_PASS_BEGIN(LoopRotate, "loop-rotate", "Rotate Loops", false, false) 86 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 87 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 88 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 89 INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 90 INITIALIZE_PASS_DEPENDENCY(LCSSA) 91 INITIALIZE_PASS_END(LoopRotate, "loop-rotate", "Rotate Loops", false, false) 92 93 Pass *llvm::createLoopRotatePass(int MaxHeaderSize) { 94 return new LoopRotate(MaxHeaderSize); 95 } 96 97 /// Rotate Loop L as many times as possible. Return true if 98 /// the loop is rotated at least once. 99 bool LoopRotate::runOnLoop(Loop *L, LPPassManager &LPM) { 100 if (skipOptnoneFunction(L)) 101 return false; 102 103 // Save the loop metadata. 104 MDNode *LoopMD = L->getLoopID(); 105 106 Function &F = *L->getHeader()->getParent(); 107 108 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 109 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 110 AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 111 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 112 DT = DTWP ? &DTWP->getDomTree() : nullptr; 113 114 // Simplify the loop latch before attempting to rotate the header 115 // upward. Rotation may not be needed if the loop tail can be folded into the 116 // loop exit. 117 bool SimplifiedLatch = simplifyLoopLatch(L); 118 119 // One loop can be rotated multiple times. 120 bool MadeChange = false; 121 while (rotateLoop(L, SimplifiedLatch)) { 122 MadeChange = true; 123 SimplifiedLatch = false; 124 } 125 126 // Restore the loop metadata. 127 // NB! We presume LoopRotation DOESN'T ADD its own metadata. 128 if ((MadeChange || SimplifiedLatch) && LoopMD) 129 L->setLoopID(LoopMD); 130 131 return MadeChange; 132 } 133 134 /// RewriteUsesOfClonedInstructions - We just cloned the instructions from the 135 /// old header into the preheader. If there were uses of the values produced by 136 /// these instruction that were outside of the loop, we have to insert PHI nodes 137 /// to merge the two values. Do this now. 138 static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader, 139 BasicBlock *OrigPreheader, 140 ValueToValueMapTy &ValueMap) { 141 // Remove PHI node entries that are no longer live. 142 BasicBlock::iterator I, E = OrigHeader->end(); 143 for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I) 144 PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader)); 145 146 // Now fix up users of the instructions in OrigHeader, inserting PHI nodes 147 // as necessary. 148 SSAUpdater SSA; 149 for (I = OrigHeader->begin(); I != E; ++I) { 150 Value *OrigHeaderVal = I; 151 152 // If there are no uses of the value (e.g. because it returns void), there 153 // is nothing to rewrite. 154 if (OrigHeaderVal->use_empty()) 155 continue; 156 157 Value *OrigPreHeaderVal = ValueMap[OrigHeaderVal]; 158 159 // The value now exits in two versions: the initial value in the preheader 160 // and the loop "next" value in the original header. 161 SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName()); 162 SSA.AddAvailableValue(OrigHeader, OrigHeaderVal); 163 SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal); 164 165 // Visit each use of the OrigHeader instruction. 166 for (Value::use_iterator UI = OrigHeaderVal->use_begin(), 167 UE = OrigHeaderVal->use_end(); UI != UE; ) { 168 // Grab the use before incrementing the iterator. 169 Use &U = *UI; 170 171 // Increment the iterator before removing the use from the list. 172 ++UI; 173 174 // SSAUpdater can't handle a non-PHI use in the same block as an 175 // earlier def. We can easily handle those cases manually. 176 Instruction *UserInst = cast<Instruction>(U.getUser()); 177 if (!isa<PHINode>(UserInst)) { 178 BasicBlock *UserBB = UserInst->getParent(); 179 180 // The original users in the OrigHeader are already using the 181 // original definitions. 182 if (UserBB == OrigHeader) 183 continue; 184 185 // Users in the OrigPreHeader need to use the value to which the 186 // original definitions are mapped. 187 if (UserBB == OrigPreheader) { 188 U = OrigPreHeaderVal; 189 continue; 190 } 191 } 192 193 // Anything else can be handled by SSAUpdater. 194 SSA.RewriteUse(U); 195 } 196 } 197 } 198 199 /// Determine whether the instructions in this range may be safely and cheaply 200 /// speculated. This is not an important enough situation to develop complex 201 /// heuristics. We handle a single arithmetic instruction along with any type 202 /// conversions. 203 static bool shouldSpeculateInstrs(BasicBlock::iterator Begin, 204 BasicBlock::iterator End, Loop *L) { 205 bool seenIncrement = false; 206 bool MultiExitLoop = false; 207 208 if (!L->getExitingBlock()) 209 MultiExitLoop = true; 210 211 for (BasicBlock::iterator I = Begin; I != End; ++I) { 212 213 if (!isSafeToSpeculativelyExecute(I)) 214 return false; 215 216 if (isa<DbgInfoIntrinsic>(I)) 217 continue; 218 219 switch (I->getOpcode()) { 220 default: 221 return false; 222 case Instruction::GetElementPtr: 223 // GEPs are cheap if all indices are constant. 224 if (!cast<GEPOperator>(I)->hasAllConstantIndices()) 225 return false; 226 // fall-thru to increment case 227 case Instruction::Add: 228 case Instruction::Sub: 229 case Instruction::And: 230 case Instruction::Or: 231 case Instruction::Xor: 232 case Instruction::Shl: 233 case Instruction::LShr: 234 case Instruction::AShr: { 235 Value *IVOpnd = !isa<Constant>(I->getOperand(0)) 236 ? I->getOperand(0) 237 : !isa<Constant>(I->getOperand(1)) 238 ? I->getOperand(1) 239 : nullptr; 240 if (!IVOpnd) 241 return false; 242 243 // If increment operand is used outside of the loop, this speculation 244 // could cause extra live range interference. 245 if (MultiExitLoop) { 246 for (User *UseI : IVOpnd->users()) { 247 auto *UserInst = cast<Instruction>(UseI); 248 if (!L->contains(UserInst)) 249 return false; 250 } 251 } 252 253 if (seenIncrement) 254 return false; 255 seenIncrement = true; 256 break; 257 } 258 case Instruction::Trunc: 259 case Instruction::ZExt: 260 case Instruction::SExt: 261 // ignore type conversions 262 break; 263 } 264 } 265 return true; 266 } 267 268 /// Fold the loop tail into the loop exit by speculating the loop tail 269 /// instructions. Typically, this is a single post-increment. In the case of a 270 /// simple 2-block loop, hoisting the increment can be much better than 271 /// duplicating the entire loop header. In the case of loops with early exits, 272 /// rotation will not work anyway, but simplifyLoopLatch will put the loop in 273 /// canonical form so downstream passes can handle it. 274 /// 275 /// I don't believe this invalidates SCEV. 276 bool LoopRotate::simplifyLoopLatch(Loop *L) { 277 BasicBlock *Latch = L->getLoopLatch(); 278 if (!Latch || Latch->hasAddressTaken()) 279 return false; 280 281 BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator()); 282 if (!Jmp || !Jmp->isUnconditional()) 283 return false; 284 285 BasicBlock *LastExit = Latch->getSinglePredecessor(); 286 if (!LastExit || !L->isLoopExiting(LastExit)) 287 return false; 288 289 BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator()); 290 if (!BI) 291 return false; 292 293 if (!shouldSpeculateInstrs(Latch->begin(), Jmp, L)) 294 return false; 295 296 DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into " 297 << LastExit->getName() << "\n"); 298 299 // Hoist the instructions from Latch into LastExit. 300 LastExit->getInstList().splice(BI, Latch->getInstList(), Latch->begin(), Jmp); 301 302 unsigned FallThruPath = BI->getSuccessor(0) == Latch ? 0 : 1; 303 BasicBlock *Header = Jmp->getSuccessor(0); 304 assert(Header == L->getHeader() && "expected a backward branch"); 305 306 // Remove Latch from the CFG so that LastExit becomes the new Latch. 307 BI->setSuccessor(FallThruPath, Header); 308 Latch->replaceSuccessorsPhiUsesWith(LastExit); 309 Jmp->eraseFromParent(); 310 311 // Nuke the Latch block. 312 assert(Latch->empty() && "unable to evacuate Latch"); 313 LI->removeBlock(Latch); 314 if (DT) 315 DT->eraseNode(Latch); 316 Latch->eraseFromParent(); 317 return true; 318 } 319 320 /// Rotate loop LP. Return true if the loop is rotated. 321 /// 322 /// \param SimplifiedLatch is true if the latch was just folded into the final 323 /// loop exit. In this case we may want to rotate even though the new latch is 324 /// now an exiting branch. This rotation would have happened had the latch not 325 /// been simplified. However, if SimplifiedLatch is false, then we avoid 326 /// rotating loops in which the latch exits to avoid excessive or endless 327 /// rotation. LoopRotate should be repeatable and converge to a canonical 328 /// form. This property is satisfied because simplifying the loop latch can only 329 /// happen once across multiple invocations of the LoopRotate pass. 330 bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) { 331 // If the loop has only one block then there is not much to rotate. 332 if (L->getBlocks().size() == 1) 333 return false; 334 335 BasicBlock *OrigHeader = L->getHeader(); 336 BasicBlock *OrigLatch = L->getLoopLatch(); 337 338 BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator()); 339 if (!BI || BI->isUnconditional()) 340 return false; 341 342 // If the loop header is not one of the loop exiting blocks then 343 // either this loop is already rotated or it is not 344 // suitable for loop rotation transformations. 345 if (!L->isLoopExiting(OrigHeader)) 346 return false; 347 348 // If the loop latch already contains a branch that leaves the loop then the 349 // loop is already rotated. 350 if (!OrigLatch) 351 return false; 352 353 // Rotate if either the loop latch does *not* exit the loop, or if the loop 354 // latch was just simplified. 355 if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch) 356 return false; 357 358 // Check size of original header and reject loop if it is very big or we can't 359 // duplicate blocks inside it. 360 { 361 SmallPtrSet<const Value *, 32> EphValues; 362 CodeMetrics::collectEphemeralValues(L, AC, EphValues); 363 364 CodeMetrics Metrics; 365 Metrics.analyzeBasicBlock(OrigHeader, *TTI, EphValues); 366 if (Metrics.notDuplicatable) { 367 DEBUG(dbgs() << "LoopRotation: NOT rotating - contains non-duplicatable" 368 << " instructions: "; L->dump()); 369 return false; 370 } 371 if (Metrics.NumInsts > MaxHeaderSize) 372 return false; 373 } 374 375 // Now, this loop is suitable for rotation. 376 BasicBlock *OrigPreheader = L->getLoopPreheader(); 377 378 // If the loop could not be converted to canonical form, it must have an 379 // indirectbr in it, just give up. 380 if (!OrigPreheader) 381 return false; 382 383 // Anything ScalarEvolution may know about this loop or the PHI nodes 384 // in its header will soon be invalidated. 385 if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>()) 386 SE->forgetLoop(L); 387 388 DEBUG(dbgs() << "LoopRotation: rotating "; L->dump()); 389 390 // Find new Loop header. NewHeader is a Header's one and only successor 391 // that is inside loop. Header's other successor is outside the 392 // loop. Otherwise loop is not suitable for rotation. 393 BasicBlock *Exit = BI->getSuccessor(0); 394 BasicBlock *NewHeader = BI->getSuccessor(1); 395 if (L->contains(Exit)) 396 std::swap(Exit, NewHeader); 397 assert(NewHeader && "Unable to determine new loop header"); 398 assert(L->contains(NewHeader) && !L->contains(Exit) && 399 "Unable to determine loop header and exit blocks"); 400 401 // This code assumes that the new header has exactly one predecessor. 402 // Remove any single-entry PHI nodes in it. 403 assert(NewHeader->getSinglePredecessor() && 404 "New header doesn't have one pred!"); 405 FoldSingleEntryPHINodes(NewHeader); 406 407 // Begin by walking OrigHeader and populating ValueMap with an entry for 408 // each Instruction. 409 BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); 410 ValueToValueMapTy ValueMap; 411 412 // For PHI nodes, the value available in OldPreHeader is just the 413 // incoming value from OldPreHeader. 414 for (; PHINode *PN = dyn_cast<PHINode>(I); ++I) 415 ValueMap[PN] = PN->getIncomingValueForBlock(OrigPreheader); 416 417 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); 418 419 // For the rest of the instructions, either hoist to the OrigPreheader if 420 // possible or create a clone in the OldPreHeader if not. 421 TerminatorInst *LoopEntryBranch = OrigPreheader->getTerminator(); 422 while (I != E) { 423 Instruction *Inst = I++; 424 425 // If the instruction's operands are invariant and it doesn't read or write 426 // memory, then it is safe to hoist. Doing this doesn't change the order of 427 // execution in the preheader, but does prevent the instruction from 428 // executing in each iteration of the loop. This means it is safe to hoist 429 // something that might trap, but isn't safe to hoist something that reads 430 // memory (without proving that the loop doesn't write). 431 if (L->hasLoopInvariantOperands(Inst) && 432 !Inst->mayReadFromMemory() && !Inst->mayWriteToMemory() && 433 !isa<TerminatorInst>(Inst) && !isa<DbgInfoIntrinsic>(Inst) && 434 !isa<AllocaInst>(Inst)) { 435 Inst->moveBefore(LoopEntryBranch); 436 continue; 437 } 438 439 // Otherwise, create a duplicate of the instruction. 440 Instruction *C = Inst->clone(); 441 442 // Eagerly remap the operands of the instruction. 443 RemapInstruction(C, ValueMap, 444 RF_NoModuleLevelChanges|RF_IgnoreMissingEntries); 445 446 // With the operands remapped, see if the instruction constant folds or is 447 // otherwise simplifyable. This commonly occurs because the entry from PHI 448 // nodes allows icmps and other instructions to fold. 449 // FIXME: Provide TLI, DT, AC to SimplifyInstruction. 450 Value *V = SimplifyInstruction(C, DL); 451 if (V && LI->replacementPreservesLCSSAForm(C, V)) { 452 // If so, then delete the temporary instruction and stick the folded value 453 // in the map. 454 delete C; 455 ValueMap[Inst] = V; 456 } else { 457 // Otherwise, stick the new instruction into the new block! 458 C->setName(Inst->getName()); 459 C->insertBefore(LoopEntryBranch); 460 ValueMap[Inst] = C; 461 } 462 } 463 464 // Along with all the other instructions, we just cloned OrigHeader's 465 // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's 466 // successors by duplicating their incoming values for OrigHeader. 467 TerminatorInst *TI = OrigHeader->getTerminator(); 468 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 469 for (BasicBlock::iterator BI = TI->getSuccessor(i)->begin(); 470 PHINode *PN = dyn_cast<PHINode>(BI); ++BI) 471 PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader); 472 473 // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove 474 // OrigPreHeader's old terminator (the original branch into the loop), and 475 // remove the corresponding incoming values from the PHI nodes in OrigHeader. 476 LoopEntryBranch->eraseFromParent(); 477 478 // If there were any uses of instructions in the duplicated block outside the 479 // loop, update them, inserting PHI nodes as required 480 RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap); 481 482 // NewHeader is now the header of the loop. 483 L->moveToHeader(NewHeader); 484 assert(L->getHeader() == NewHeader && "Latch block is our new header"); 485 486 487 // At this point, we've finished our major CFG changes. As part of cloning 488 // the loop into the preheader we've simplified instructions and the 489 // duplicated conditional branch may now be branching on a constant. If it is 490 // branching on a constant and if that constant means that we enter the loop, 491 // then we fold away the cond branch to an uncond branch. This simplifies the 492 // loop in cases important for nested loops, and it also means we don't have 493 // to split as many edges. 494 BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator()); 495 assert(PHBI->isConditional() && "Should be clone of BI condbr!"); 496 if (!isa<ConstantInt>(PHBI->getCondition()) || 497 PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero()) 498 != NewHeader) { 499 // The conditional branch can't be folded, handle the general case. 500 // Update DominatorTree to reflect the CFG change we just made. Then split 501 // edges as necessary to preserve LoopSimplify form. 502 if (DT) { 503 // Everything that was dominated by the old loop header is now dominated 504 // by the original loop preheader. Conceptually the header was merged 505 // into the preheader, even though we reuse the actual block as a new 506 // loop latch. 507 DomTreeNode *OrigHeaderNode = DT->getNode(OrigHeader); 508 SmallVector<DomTreeNode *, 8> HeaderChildren(OrigHeaderNode->begin(), 509 OrigHeaderNode->end()); 510 DomTreeNode *OrigPreheaderNode = DT->getNode(OrigPreheader); 511 for (unsigned I = 0, E = HeaderChildren.size(); I != E; ++I) 512 DT->changeImmediateDominator(HeaderChildren[I], OrigPreheaderNode); 513 514 assert(DT->getNode(Exit)->getIDom() == OrigPreheaderNode); 515 assert(DT->getNode(NewHeader)->getIDom() == OrigPreheaderNode); 516 517 // Update OrigHeader to be dominated by the new header block. 518 DT->changeImmediateDominator(OrigHeader, OrigLatch); 519 } 520 521 // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and 522 // thus is not a preheader anymore. 523 // Split the edge to form a real preheader. 524 BasicBlock *NewPH = SplitCriticalEdge( 525 OrigPreheader, NewHeader, 526 CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA()); 527 NewPH->setName(NewHeader->getName() + ".lr.ph"); 528 529 // Preserve canonical loop form, which means that 'Exit' should have only 530 // one predecessor. Note that Exit could be an exit block for multiple 531 // nested loops, causing both of the edges to now be critical and need to 532 // be split. 533 SmallVector<BasicBlock *, 4> ExitPreds(pred_begin(Exit), pred_end(Exit)); 534 bool SplitLatchEdge = false; 535 for (SmallVectorImpl<BasicBlock *>::iterator PI = ExitPreds.begin(), 536 PE = ExitPreds.end(); 537 PI != PE; ++PI) { 538 // We only need to split loop exit edges. 539 Loop *PredLoop = LI->getLoopFor(*PI); 540 if (!PredLoop || PredLoop->contains(Exit)) 541 continue; 542 if (isa<IndirectBrInst>((*PI)->getTerminator())) 543 continue; 544 SplitLatchEdge |= L->getLoopLatch() == *PI; 545 BasicBlock *ExitSplit = SplitCriticalEdge( 546 *PI, Exit, CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA()); 547 ExitSplit->moveBefore(Exit); 548 } 549 assert(SplitLatchEdge && 550 "Despite splitting all preds, failed to split latch exit?"); 551 } else { 552 // We can fold the conditional branch in the preheader, this makes things 553 // simpler. The first step is to remove the extra edge to the Exit block. 554 Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/); 555 BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI); 556 NewBI->setDebugLoc(PHBI->getDebugLoc()); 557 PHBI->eraseFromParent(); 558 559 // With our CFG finalized, update DomTree if it is available. 560 if (DT) { 561 // Update OrigHeader to be dominated by the new header block. 562 DT->changeImmediateDominator(NewHeader, OrigPreheader); 563 DT->changeImmediateDominator(OrigHeader, OrigLatch); 564 565 // Brute force incremental dominator tree update. Call 566 // findNearestCommonDominator on all CFG predecessors of each child of the 567 // original header. 568 DomTreeNode *OrigHeaderNode = DT->getNode(OrigHeader); 569 SmallVector<DomTreeNode *, 8> HeaderChildren(OrigHeaderNode->begin(), 570 OrigHeaderNode->end()); 571 bool Changed; 572 do { 573 Changed = false; 574 for (unsigned I = 0, E = HeaderChildren.size(); I != E; ++I) { 575 DomTreeNode *Node = HeaderChildren[I]; 576 BasicBlock *BB = Node->getBlock(); 577 578 pred_iterator PI = pred_begin(BB); 579 BasicBlock *NearestDom = *PI; 580 for (pred_iterator PE = pred_end(BB); PI != PE; ++PI) 581 NearestDom = DT->findNearestCommonDominator(NearestDom, *PI); 582 583 // Remember if this changes the DomTree. 584 if (Node->getIDom()->getBlock() != NearestDom) { 585 DT->changeImmediateDominator(BB, NearestDom); 586 Changed = true; 587 } 588 } 589 590 // If the dominator changed, this may have an effect on other 591 // predecessors, continue until we reach a fixpoint. 592 } while (Changed); 593 } 594 } 595 596 assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation"); 597 assert(L->getLoopLatch() && "Invalid loop latch after loop rotation"); 598 599 // Now that the CFG and DomTree are in a consistent state again, try to merge 600 // the OrigHeader block into OrigLatch. This will succeed if they are 601 // connected by an unconditional branch. This is just a cleanup so the 602 // emitted code isn't too gross in this common case. 603 MergeBlockIntoPredecessor(OrigHeader, DT, LI); 604 605 DEBUG(dbgs() << "LoopRotation: into "; L->dump()); 606 607 ++NumRotated; 608 return true; 609 } 610