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