LoopRotation.cpp revision 7be06f9158bb139b88d68fc5f149018db88dc6a0
1//===- LoopRotation.cpp - Loop Rotation Pass ------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Devang Patel and is distributed under 6// the University of Illinois Open Source 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 16#include "llvm/Transforms/Scalar.h" 17#include "llvm/Function.h" 18#include "llvm/Instructions.h" 19#include "llvm/Analysis/LoopInfo.h" 20#include "llvm/Analysis/LoopPass.h" 21#include "llvm/Analysis/Dominators.h" 22#include "llvm/Analysis/ScalarEvolution.h" 23#include "llvm/Transforms/Utils/Local.h" 24#include "llvm/Transforms/Utils/BasicBlockUtils.h" 25#include "llvm/Support/CommandLine.h" 26#include "llvm/Support/Debug.h" 27#include "llvm/ADT/Statistic.h" 28#include "llvm/ADT/SmallVector.h" 29 30using namespace llvm; 31 32#define MAX_HEADER_SIZE 16 33 34STATISTIC(NumRotated, "Number of loops rotated"); 35namespace { 36 37 class VISIBILITY_HIDDEN RenameData { 38 public: 39 RenameData(Instruction *O, Value *P, Instruction *H) 40 : Original(O), PreHeader(P), Header(H) { } 41 public: 42 Instruction *Original; // Original instruction 43 Value *PreHeader; // Original pre-header replacement 44 Instruction *Header; // New header replacement 45 }; 46 47 class VISIBILITY_HIDDEN LoopRotate : public LoopPass { 48 49 public: 50 static char ID; // Pass ID, replacement for typeid 51 LoopRotate() : LoopPass((intptr_t)&ID) {} 52 53 // Rotate Loop L as many times as possible. Return true if 54 // loop is rotated at least once. 55 bool runOnLoop(Loop *L, LPPassManager &LPM); 56 57 // LCSSA form makes instruction renaming easier. 58 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 59 AU.addRequiredID(LCSSAID); 60 AU.addPreservedID(LCSSAID); 61 AU.addPreserved<ScalarEvolution>(); 62 AU.addPreserved<LoopInfo>(); 63 AU.addRequiredID(LoopSimplifyID); 64 AU.addPreservedID(LoopSimplifyID); 65 AU.addPreserved<DominatorTree>(); 66 // Request DominanceFrontier now, even though Loop Rotate does 67 // not use it. This allows Pass Manager to schedule Dominance 68 // Frontier early enough such that one LPPassManager can handle 69 // loop rotate as well as licm pass. 70 AU.addRequired<DominanceFrontier>(); 71 AU.addPreserved<DominanceFrontier>(); 72 } 73 74 // Helper functions 75 76 /// Do actual work 77 bool rotateLoop(Loop *L, LPPassManager &LPM); 78 79 /// Initialize local data 80 void initialize(); 81 82 /// Make sure all Exit block PHINodes have required incoming values. 83 /// If incoming value is constant or defined outside the loop then 84 /// PHINode may not have an entry for original pre-header. 85 void updateExitBlock(); 86 87 /// Return true if this instruction is used outside original header. 88 bool usedOutsideOriginalHeader(Instruction *In); 89 90 /// Find Replacement information for instruction. Return NULL if it is 91 /// not available. 92 const RenameData *findReplacementData(Instruction *I); 93 94 /// After loop rotation, loop pre-header has multiple sucessors. 95 /// Insert one forwarding basic block to ensure that loop pre-header 96 /// has only one successor. 97 void preserveCanonicalLoopForm(LPPassManager &LPM); 98 99 private: 100 101 Loop *L; 102 BasicBlock *OrigHeader; 103 BasicBlock *OrigPreHeader; 104 BasicBlock *OrigLatch; 105 BasicBlock *NewHeader; 106 BasicBlock *Exit; 107 LPPassManager *LPM_Ptr; 108 SmallVector<RenameData, MAX_HEADER_SIZE> LoopHeaderInfo; 109 }; 110 111 char LoopRotate::ID = 0; 112 RegisterPass<LoopRotate> X ("loop-rotate", "Rotate Loops"); 113} 114 115LoopPass *llvm::createLoopRotatePass() { return new LoopRotate(); } 116 117/// Rotate Loop L as many times as possible. Return true if 118/// loop is rotated at least once. 119bool LoopRotate::runOnLoop(Loop *Lp, LPPassManager &LPM) { 120 121 bool RotatedOneLoop = false; 122 initialize(); 123 LPM_Ptr = &LPM; 124 125 // One loop can be rotated multiple times. 126 while (rotateLoop(Lp,LPM)) { 127 RotatedOneLoop = true; 128 initialize(); 129 } 130 131 return RotatedOneLoop; 132} 133 134/// Rotate loop LP. Return true if the loop is rotated. 135bool LoopRotate::rotateLoop(Loop *Lp, LPPassManager &LPM) { 136 137 L = Lp; 138 139 OrigHeader = L->getHeader(); 140 OrigPreHeader = L->getLoopPreheader(); 141 OrigLatch = L->getLoopLatch(); 142 143 // If loop has only one block then there is not much to rotate. 144 if (L->getBlocks().size() == 1) 145 return false; 146 147 assert (OrigHeader && OrigLatch && OrigPreHeader && 148 "Loop is not in canonical form"); 149 150 // If loop header is not one of the loop exit block then 151 // either this loop is already rotated or it is not 152 // suitable for loop rotation transformations. 153 if (!L->isLoopExit(OrigHeader)) 154 return false; 155 156 BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator()); 157 if (!BI) 158 return false; 159 assert (BI->isConditional() && "Branch Instruction is not condiitional"); 160 161 // Updating PHInodes in loops with multiple exits adds complexity. 162 // Keep it simple, and restrict loop rotation to loops with one exit only. 163 // In future, lift this restriction and support for multiple exits if 164 // required. 165 std::vector<BasicBlock *> ExitBlocks; 166 L->getExitBlocks(ExitBlocks); 167 if (ExitBlocks.size() > 1) 168 return false; 169 170 // Check size of original header and reject 171 // loop if it is very big. 172 if (OrigHeader->getInstList().size() > MAX_HEADER_SIZE) 173 return false; 174 175 // Now, this loop is suitable for rotation. 176 177 // Find new Loop header. NewHeader is a Header's one and only successor 178 // that is inside loop. Header's other successor is out side the 179 // loop. Otherwise loop is not suitable for rotation. 180 Exit = BI->getSuccessor(0); 181 NewHeader = BI->getSuccessor(1); 182 if (L->contains(Exit)) 183 std::swap(Exit, NewHeader); 184 assert (NewHeader && "Unable to determine new loop header"); 185 assert(L->contains(NewHeader) && !L->contains(Exit) && 186 "Unable to determine loop header and exit blocks"); 187 188 // Copy PHI nodes and other instructions from original header 189 // into original pre-header. Unlike original header, original pre-header is 190 // not a member of loop. 191 // 192 // New loop header is one and only successor of original header that 193 // is inside the loop. All other original header successors are outside 194 // the loop. Copy PHI Nodes from original header into new loop header. 195 // Add second incoming value, from original loop pre-header into these phi 196 // nodes. If a value defined in original header is used outside original 197 // header then new loop header will need new phi nodes with two incoming 198 // values, one definition from original header and second definition is 199 // from original loop pre-header. 200 201 // Remove terminator from Original pre-header. Original pre-header will 202 // receive a clone of original header terminator as a new terminator. 203 OrigPreHeader->getInstList().pop_back(); 204 BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); 205 PHINode *PN = NULL; 206 for (; (PN = dyn_cast<PHINode>(I)); ++I) { 207 Instruction *In = I; 208 209 // PHI nodes are not copied into original pre-header. Instead their values 210 // are directly propagated. 211 Value * NPV = PN->getIncomingValueForBlock(OrigPreHeader); 212 213 // Create new PHI node with two incoming values for NewHeader. 214 // One incoming value is from OrigLatch (through OrigHeader) and 215 // second incoming value is from original pre-header. 216 PHINode *NH = new PHINode(In->getType(), In->getName()); 217 NH->addIncoming(PN->getIncomingValueForBlock(OrigLatch), OrigHeader); 218 NH->addIncoming(NPV, OrigPreHeader); 219 NewHeader->getInstList().push_front(NH); 220 221 // "In" can be replaced by NH at various places. 222 LoopHeaderInfo.push_back(RenameData(In, NPV, NH)); 223 } 224 225 // Now, handle non-phi instructions. 226 for (; I != E; ++I) { 227 Instruction *In = I; 228 229 assert (!isa<PHINode>(In) && "PHINode is not expected here"); 230 // This is not a PHI instruction. Insert its clone into original pre-header. 231 // If this instruction is using a value from same basic block then 232 // update it to use value from cloned instruction. 233 Instruction *C = In->clone(); 234 C->setName(In->getName()); 235 OrigPreHeader->getInstList().push_back(C); 236 237 for (unsigned opi = 0, e = In->getNumOperands(); opi != e; ++opi) { 238 if (Instruction *OpPhi = dyn_cast<PHINode>(In->getOperand(opi))) { 239 if (const RenameData *D = findReplacementData(OpPhi)) { 240 // This is using values from original header PHI node. 241 // Here, directly used incoming value from original pre-header. 242 C->setOperand(opi, D->PreHeader); 243 } 244 } 245 else if (Instruction *OpInsn = 246 dyn_cast<Instruction>(In->getOperand(opi))) { 247 if (const RenameData *D = findReplacementData(OpInsn)) 248 C->setOperand(opi, D->PreHeader); 249 } 250 } 251 252 253 // If this instruction is used outside this basic block then 254 // create new PHINode for this instruction. 255 Instruction *NewHeaderReplacement = NULL; 256 if (usedOutsideOriginalHeader(In)) { 257 PHINode *PN = new PHINode(In->getType(), In->getName()); 258 PN->addIncoming(In, OrigHeader); 259 PN->addIncoming(C, OrigPreHeader); 260 NewHeader->getInstList().push_front(PN); 261 NewHeaderReplacement = PN; 262 } 263 264 // "In" can be replaced by NPH or NH at various places. 265 LoopHeaderInfo.push_back(RenameData(In, C, NewHeaderReplacement)); 266 } 267 268 // Rename uses of original header instructions to reflect their new 269 // definitions (either from original pre-header node or from newly created 270 // new header PHINodes. 271 // 272 // Original header instructions are used in 273 // 1) Original header: 274 // 275 // If instruction is used in non-phi instructions then it is using 276 // defintion from original heder iteself. Do not replace this use 277 // with definition from new header or original pre-header. 278 // 279 // If instruction is used in phi node then it is an incoming 280 // value. Rename its use to reflect new definition from new-preheader 281 // or new header. 282 // 283 // 2) Inside loop but not in original header 284 // 285 // Replace this use to reflect definition from new header. 286 for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) { 287 const RenameData &ILoopHeaderInfo = LoopHeaderInfo[LHI]; 288 289 if (!ILoopHeaderInfo.Header) 290 continue; 291 292 Instruction *OldPhi = ILoopHeaderInfo.Original; 293 Instruction *NewPhi = ILoopHeaderInfo.Header; 294 295 // Before replacing uses, collect them first, so that iterator is 296 // not invalidated. 297 SmallVector<Instruction *, 16> AllUses; 298 for (Value::use_iterator UI = OldPhi->use_begin(), UE = OldPhi->use_end(); 299 UI != UE; ++UI) { 300 Instruction *U = cast<Instruction>(UI); 301 AllUses.push_back(U); 302 } 303 304 for (SmallVector<Instruction *, 16>::iterator UI = AllUses.begin(), 305 UE = AllUses.end(); UI != UE; ++UI) { 306 Instruction *U = *UI; 307 BasicBlock *Parent = U->getParent(); 308 309 // Used inside original header 310 if (Parent == OrigHeader) { 311 // Do not rename uses inside original header non-phi instructions. 312 PHINode *PU = dyn_cast<PHINode>(U); 313 if (!PU) 314 continue; 315 316 // Do not rename uses inside original header phi nodes, if the 317 // incoming value is for new header. 318 if (PU->getBasicBlockIndex(NewHeader) != -1 319 && PU->getIncomingValueForBlock(NewHeader) == U) 320 continue; 321 322 U->replaceUsesOfWith(OldPhi, NewPhi); 323 continue; 324 } 325 326 // Used inside loop, but not in original header. 327 if (L->contains(U->getParent())) { 328 if (U != NewPhi) 329 U->replaceUsesOfWith(OldPhi, NewPhi); 330 continue; 331 } 332 333 // Used inside Exit Block. Since we are in LCSSA form, U must be PHINode. 334 if (U->getParent() == Exit) { 335 assert (isa<PHINode>(U) && "Use in Exit Block that is not PHINode"); 336 337 PHINode *UPhi = cast<PHINode>(U); 338 // UPhi already has one incoming argument from original header. 339 // Add second incoming argument from new Pre header. 340 UPhi->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader); 341 } else { 342 // Used outside Exit block. Create a new PHI node from exit block 343 // to receive value from ne new header ane pre header. 344 PHINode *PN = new PHINode(U->getType(), U->getName()); 345 PN->addIncoming(ILoopHeaderInfo.PreHeader, OrigPreHeader); 346 PN->addIncoming(OldPhi, OrigHeader); 347 Exit->getInstList().push_front(PN); 348 U->replaceUsesOfWith(OldPhi, PN); 349 } 350 } 351 } 352 353 /// Make sure all Exit block PHINodes have required incoming values. 354 updateExitBlock(); 355 356 // Update CFG 357 358 // Removing incoming branch from loop preheader to original header. 359 // Now original header is inside the loop. 360 for (BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end(); 361 I != E; ++I) { 362 Instruction *In = I; 363 PHINode *PN = dyn_cast<PHINode>(In); 364 if (!PN) 365 break; 366 367 PN->removeIncomingValue(OrigPreHeader); 368 } 369 370 // Make NewHeader as the new header for the loop. 371 L->moveToHeader(NewHeader); 372 373 preserveCanonicalLoopForm(LPM); 374 375 NumRotated++; 376 return true; 377} 378 379/// Make sure all Exit block PHINodes have required incoming values. 380/// If incoming value is constant or defined outside the loop then 381/// PHINode may not have an entry for original pre-header. 382void LoopRotate::updateExitBlock() { 383 384 for (BasicBlock::iterator I = Exit->begin(), E = Exit->end(); 385 I != E; ++I) { 386 387 PHINode *PN = dyn_cast<PHINode>(I); 388 if (!PN) 389 break; 390 391 // There is already one incoming value from original pre-header block. 392 if (PN->getBasicBlockIndex(OrigPreHeader) != -1) 393 continue; 394 395 const RenameData *ILoopHeaderInfo; 396 Value *V = PN->getIncomingValueForBlock(OrigHeader); 397 if (isa<Instruction>(V) && 398 (ILoopHeaderInfo = findReplacementData(cast<Instruction>(V)))) { 399 assert(ILoopHeaderInfo->PreHeader && "Missing New Preheader Instruction"); 400 PN->addIncoming(ILoopHeaderInfo->PreHeader, OrigPreHeader); 401 } else { 402 PN->addIncoming(V, OrigPreHeader); 403 } 404 } 405} 406 407/// Initialize local data 408void LoopRotate::initialize() { 409 L = NULL; 410 OrigHeader = NULL; 411 OrigPreHeader = NULL; 412 NewHeader = NULL; 413 Exit = NULL; 414 415 LoopHeaderInfo.clear(); 416} 417 418/// Return true if this instruction is used by any instructions in the loop that 419/// aren't in original header. 420bool LoopRotate::usedOutsideOriginalHeader(Instruction *In) { 421 422 for (Value::use_iterator UI = In->use_begin(), UE = In->use_end(); 423 UI != UE; ++UI) { 424 Instruction *U = cast<Instruction>(UI); 425 if (U->getParent() != OrigHeader) { 426 if (L->contains(U->getParent())) 427 return true; 428 } 429 } 430 431 return false; 432} 433 434/// Find Replacement information for instruction. Return NULL if it is 435/// not available. 436const RenameData *LoopRotate::findReplacementData(Instruction *In) { 437 438 // Since LoopHeaderInfo is small, linear walk is OK. 439 for(unsigned LHI = 0, LHI_E = LoopHeaderInfo.size(); LHI != LHI_E; ++LHI) { 440 const RenameData &ILoopHeaderInfo = LoopHeaderInfo[LHI]; 441 if (ILoopHeaderInfo.Original == In) 442 return &ILoopHeaderInfo; 443 } 444 return NULL; 445} 446 447/// After loop rotation, loop pre-header has multiple sucessors. 448/// Insert one forwarding basic block to ensure that loop pre-header 449/// has only one successor. 450void LoopRotate::preserveCanonicalLoopForm(LPPassManager &LPM) { 451 452 // Right now original pre-header has two successors, new header and 453 // exit block. Insert new block between original pre-header and 454 // new header such that loop's new pre-header has only one successor. 455 BasicBlock *NewPreHeader = new BasicBlock("bb.nph", OrigHeader->getParent(), 456 NewHeader); 457 LoopInfo &LI = LPM.getAnalysis<LoopInfo>(); 458 if (Loop *PL = LI.getLoopFor(OrigPreHeader)) 459 PL->addBasicBlockToLoop(NewPreHeader, LI); 460 new BranchInst(NewHeader, NewPreHeader); 461 462 BranchInst *OrigPH_BI = cast<BranchInst>(OrigPreHeader->getTerminator()); 463 if (OrigPH_BI->getSuccessor(0) == NewHeader) 464 OrigPH_BI->setSuccessor(0, NewPreHeader); 465 else { 466 assert (OrigPH_BI->getSuccessor(1) == NewHeader && 467 "Unexpected original pre-header terminator"); 468 OrigPH_BI->setSuccessor(1, NewPreHeader); 469 } 470 471 for (BasicBlock::iterator I = NewHeader->begin(), E = NewHeader->end(); 472 I != E; ++I) { 473 Instruction *In = I; 474 PHINode *PN = dyn_cast<PHINode>(In); 475 if (!PN) 476 break; 477 478 int index = PN->getBasicBlockIndex(OrigPreHeader); 479 assert (index != -1 && "Expected incoming value from Original PreHeader"); 480 PN->setIncomingBlock(index, NewPreHeader); 481 assert (PN->getBasicBlockIndex(OrigPreHeader) == -1 && 482 "Expected only one incoming value from Original PreHeader"); 483 } 484 485 SplitEdge(L->getLoopLatch(), Exit, this); 486 487 if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) { 488 DT->addNewBlock(NewPreHeader, OrigPreHeader); 489 DT->changeImmediateDominator(L->getHeader(), NewPreHeader); 490 DT->changeImmediateDominator(Exit, OrigPreHeader); 491 for (Loop::block_iterator BI = L->block_begin(), BE = L->block_end(); 492 BI != BE; ++BI) { 493 BasicBlock *B = *BI; 494 if (L->getHeader() != B) { 495 DomTreeNode *Node = DT->getNode(B); 496 if (Node && Node->getBlock() == OrigHeader) 497 DT->changeImmediateDominator(*BI, L->getHeader()); 498 } 499 } 500 DT->changeImmediateDominator(OrigHeader, OrigLatch); 501 } 502 503 if(DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>()) { 504 505 // New Preheader's dominance frontier is same as original preheader. 506 DominanceFrontier::iterator DFI = DF->find(OrigPreHeader); 507 if (DFI != DF->end()) { 508 DominanceFrontier::DomSetType NPHSet(DFI->second), NHSet(DFI->second); 509 // NPHSet.insert(DFI->second.begin(), DFI->second.end(), NPHSet.begin()); 510 DF->addBasicBlock(NewPreHeader, NPHSet); 511 512 DominanceFrontier::iterator DHI = DF->find(L->getHeader()); 513 if (DHI != DF->end()) { 514 DominanceFrontier::DomSetType DHSet = DHI->second; 515 DHSet.clear(); 516 DHSet.insert(DFI->second.begin(), DFI->second.end()); 517 } else { 518 DominanceFrontier::DomSetType NHSet(DFI->second); 519 // NHSet.insert(DFI->second.begin(), DFI->second.end(), NHSet.begin()); 520 DF->addBasicBlock(L->getHeader(), NHSet); 521 } 522 } 523 524 // Original header no longer dominates Exit 525 DFI = DF->find(OrigHeader); 526 if (DFI != DF->end()) { 527 for (succ_iterator SI = succ_begin(Exit), SE = succ_end(Exit); 528 SI != SE; ++SI) { 529 BasicBlock *Succ = *SI; 530 DominanceFrontier::DomSetType::iterator DSI = DFI->second.find(Succ); 531 if (DSI != DFI->second.end()) 532 DFI->second.erase(DSI); 533 } 534 } 535 } 536 537 assert (NewHeader && L->getHeader() == NewHeader 538 && "Invalid loop header after loop rotation"); 539 assert (NewPreHeader && L->getLoopPreheader() == NewPreHeader 540 && "Invalid loop preheader after loop rotation"); 541 assert (L->getLoopLatch() 542 && "Invalid loop latch after loop rotation"); 543 544} 545