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