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