1 //===-- UnrollLoopRuntime.cpp - Runtime Loop unrolling utilities ----------===// 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 some loop unrolling utilities for loops with run-time 11 // trip counts. See LoopUnroll.cpp for unrolling loops with compile-time 12 // trip counts. 13 // 14 // The functions in this file are used to generate extra code when the 15 // run-time trip count modulo the unroll factor is not 0. When this is the 16 // case, we need to generate code to execute these 'left over' iterations. 17 // 18 // The current strategy generates an if-then-else sequence prior to the 19 // unrolled loop to execute the 'left over' iterations. Other strategies 20 // include generate a loop before or after the unrolled loop. 21 // 22 //===----------------------------------------------------------------------===// 23 24 #include "llvm/Transforms/Utils/UnrollLoop.h" 25 #include "llvm/ADT/Statistic.h" 26 #include "llvm/Analysis/LoopIterator.h" 27 #include "llvm/Analysis/LoopPass.h" 28 #include "llvm/Analysis/ScalarEvolution.h" 29 #include "llvm/Analysis/ScalarEvolutionExpander.h" 30 #include "llvm/IR/BasicBlock.h" 31 #include "llvm/Support/Debug.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 34 #include "llvm/Transforms/Utils/Cloning.h" 35 #include <algorithm> 36 37 using namespace llvm; 38 39 #define DEBUG_TYPE "loop-unroll" 40 41 STATISTIC(NumRuntimeUnrolled, 42 "Number of loops unrolled with run-time trip counts"); 43 44 /// Connect the unrolling prolog code to the original loop. 45 /// The unrolling prolog code contains code to execute the 46 /// 'extra' iterations if the run-time trip count modulo the 47 /// unroll count is non-zero. 48 /// 49 /// This function performs the following: 50 /// - Create PHI nodes at prolog end block to combine values 51 /// that exit the prolog code and jump around the prolog. 52 /// - Add a PHI operand to a PHI node at the loop exit block 53 /// for values that exit the prolog and go around the loop. 54 /// - Branch around the original loop if the trip count is less 55 /// than the unroll factor. 56 /// 57 static void ConnectProlog(Loop *L, Value *TripCount, unsigned Count, 58 BasicBlock *LastPrologBB, BasicBlock *PrologEnd, 59 BasicBlock *OrigPH, BasicBlock *NewPH, 60 ValueToValueMapTy &LVMap, Pass *P) { 61 BasicBlock *Latch = L->getLoopLatch(); 62 assert(Latch && "Loop must have a latch"); 63 64 // Create a PHI node for each outgoing value from the original loop 65 // (which means it is an outgoing value from the prolog code too). 66 // The new PHI node is inserted in the prolog end basic block. 67 // The new PHI name is added as an operand of a PHI node in either 68 // the loop header or the loop exit block. 69 for (succ_iterator SBI = succ_begin(Latch), SBE = succ_end(Latch); 70 SBI != SBE; ++SBI) { 71 for (BasicBlock::iterator BBI = (*SBI)->begin(); 72 PHINode *PN = dyn_cast<PHINode>(BBI); ++BBI) { 73 74 // Add a new PHI node to the prolog end block and add the 75 // appropriate incoming values. 76 PHINode *NewPN = PHINode::Create(PN->getType(), 2, PN->getName()+".unr", 77 PrologEnd->getTerminator()); 78 // Adding a value to the new PHI node from the original loop preheader. 79 // This is the value that skips all the prolog code. 80 if (L->contains(PN)) { 81 NewPN->addIncoming(PN->getIncomingValueForBlock(NewPH), OrigPH); 82 } else { 83 NewPN->addIncoming(Constant::getNullValue(PN->getType()), OrigPH); 84 } 85 86 Value *V = PN->getIncomingValueForBlock(Latch); 87 if (Instruction *I = dyn_cast<Instruction>(V)) { 88 if (L->contains(I)) { 89 V = LVMap[I]; 90 } 91 } 92 // Adding a value to the new PHI node from the last prolog block 93 // that was created. 94 NewPN->addIncoming(V, LastPrologBB); 95 96 // Update the existing PHI node operand with the value from the 97 // new PHI node. How this is done depends on if the existing 98 // PHI node is in the original loop block, or the exit block. 99 if (L->contains(PN)) { 100 PN->setIncomingValue(PN->getBasicBlockIndex(NewPH), NewPN); 101 } else { 102 PN->addIncoming(NewPN, PrologEnd); 103 } 104 } 105 } 106 107 // Create a branch around the orignal loop, which is taken if the 108 // trip count is less than the unroll factor. 109 Instruction *InsertPt = PrologEnd->getTerminator(); 110 Instruction *BrLoopExit = 111 new ICmpInst(InsertPt, ICmpInst::ICMP_ULT, TripCount, 112 ConstantInt::get(TripCount->getType(), Count)); 113 BasicBlock *Exit = L->getUniqueExitBlock(); 114 assert(Exit && "Loop must have a single exit block only"); 115 // Split the exit to maintain loop canonicalization guarantees 116 SmallVector<BasicBlock*, 4> Preds(pred_begin(Exit), pred_end(Exit)); 117 if (!Exit->isLandingPad()) { 118 SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", P); 119 } else { 120 SmallVector<BasicBlock*, 2> NewBBs; 121 SplitLandingPadPredecessors(Exit, Preds, ".unr1-lcssa", ".unr2-lcssa", 122 P, NewBBs); 123 } 124 // Add the branch to the exit block (around the unrolled loop) 125 BranchInst::Create(Exit, NewPH, BrLoopExit, InsertPt); 126 InsertPt->eraseFromParent(); 127 } 128 129 /// Create a clone of the blocks in a loop and connect them together. 130 /// This function doesn't create a clone of the loop structure. 131 /// 132 /// There are two value maps that are defined and used. VMap is 133 /// for the values in the current loop instance. LVMap contains 134 /// the values from the last loop instance. We need the LVMap values 135 /// to update the initial values for the current loop instance. 136 /// 137 static void CloneLoopBlocks(Loop *L, 138 bool FirstCopy, 139 BasicBlock *InsertTop, 140 BasicBlock *InsertBot, 141 std::vector<BasicBlock *> &NewBlocks, 142 LoopBlocksDFS &LoopBlocks, 143 ValueToValueMapTy &VMap, 144 ValueToValueMapTy &LVMap, 145 LoopInfo *LI) { 146 147 BasicBlock *Preheader = L->getLoopPreheader(); 148 BasicBlock *Header = L->getHeader(); 149 BasicBlock *Latch = L->getLoopLatch(); 150 Function *F = Header->getParent(); 151 LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO(); 152 LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO(); 153 // For each block in the original loop, create a new copy, 154 // and update the value map with the newly created values. 155 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) { 156 BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".unr", F); 157 NewBlocks.push_back(NewBB); 158 159 if (Loop *ParentLoop = L->getParentLoop()) 160 ParentLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 161 162 VMap[*BB] = NewBB; 163 if (Header == *BB) { 164 // For the first block, add a CFG connection to this newly 165 // created block 166 InsertTop->getTerminator()->setSuccessor(0, NewBB); 167 168 // Change the incoming values to the ones defined in the 169 // previously cloned loop. 170 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) { 171 PHINode *NewPHI = cast<PHINode>(VMap[I]); 172 if (FirstCopy) { 173 // We replace the first phi node with the value from the preheader 174 VMap[I] = NewPHI->getIncomingValueForBlock(Preheader); 175 NewBB->getInstList().erase(NewPHI); 176 } else { 177 // Update VMap with values from the previous block 178 unsigned idx = NewPHI->getBasicBlockIndex(Latch); 179 Value *InVal = NewPHI->getIncomingValue(idx); 180 if (Instruction *I = dyn_cast<Instruction>(InVal)) 181 if (L->contains(I)) 182 InVal = LVMap[InVal]; 183 NewPHI->setIncomingValue(idx, InVal); 184 NewPHI->setIncomingBlock(idx, InsertTop); 185 } 186 } 187 } 188 189 if (Latch == *BB) { 190 VMap.erase((*BB)->getTerminator()); 191 NewBB->getTerminator()->eraseFromParent(); 192 BranchInst::Create(InsertBot, NewBB); 193 } 194 } 195 // LastValueMap is updated with the values for the current loop 196 // which are used the next time this function is called. 197 for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end(); 198 VI != VE; ++VI) { 199 LVMap[VI->first] = VI->second; 200 } 201 } 202 203 /// Insert code in the prolog code when unrolling a loop with a 204 /// run-time trip-count. 205 /// 206 /// This method assumes that the loop unroll factor is total number 207 /// of loop bodes in the loop after unrolling. (Some folks refer 208 /// to the unroll factor as the number of *extra* copies added). 209 /// We assume also that the loop unroll factor is a power-of-two. So, after 210 /// unrolling the loop, the number of loop bodies executed is 2, 211 /// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch 212 /// instruction in SimplifyCFG.cpp. Then, the backend decides how code for 213 /// the switch instruction is generated. 214 /// 215 /// extraiters = tripcount % loopfactor 216 /// if (extraiters == 0) jump Loop: 217 /// if (extraiters == loopfactor) jump L1 218 /// if (extraiters == loopfactor-1) jump L2 219 /// ... 220 /// L1: LoopBody; 221 /// L2: LoopBody; 222 /// ... 223 /// if tripcount < loopfactor jump End 224 /// Loop: 225 /// ... 226 /// End: 227 /// 228 bool llvm::UnrollRuntimeLoopProlog(Loop *L, unsigned Count, LoopInfo *LI, 229 LPPassManager *LPM) { 230 // for now, only unroll loops that contain a single exit 231 if (!L->getExitingBlock()) 232 return false; 233 234 // Make sure the loop is in canonical form, and there is a single 235 // exit block only. 236 if (!L->isLoopSimplifyForm() || !L->getUniqueExitBlock()) 237 return false; 238 239 // Use Scalar Evolution to compute the trip count. This allows more 240 // loops to be unrolled than relying on induction var simplification 241 if (!LPM) 242 return false; 243 ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>(); 244 if (!SE) 245 return false; 246 247 // Only unroll loops with a computable trip count and the trip count needs 248 // to be an int value (allowing a pointer type is a TODO item) 249 const SCEV *BECount = SE->getBackedgeTakenCount(L); 250 if (isa<SCEVCouldNotCompute>(BECount) || !BECount->getType()->isIntegerTy()) 251 return false; 252 253 // Add 1 since the backedge count doesn't include the first loop iteration 254 const SCEV *TripCountSC = 255 SE->getAddExpr(BECount, SE->getConstant(BECount->getType(), 1)); 256 if (isa<SCEVCouldNotCompute>(TripCountSC)) 257 return false; 258 259 // We only handle cases when the unroll factor is a power of 2. 260 // Count is the loop unroll factor, the number of extra copies added + 1. 261 if ((Count & (Count-1)) != 0) 262 return false; 263 264 // If this loop is nested, then the loop unroller changes the code in 265 // parent loop, so the Scalar Evolution pass needs to be run again 266 if (Loop *ParentLoop = L->getParentLoop()) 267 SE->forgetLoop(ParentLoop); 268 269 BasicBlock *PH = L->getLoopPreheader(); 270 BasicBlock *Header = L->getHeader(); 271 BasicBlock *Latch = L->getLoopLatch(); 272 // It helps to splits the original preheader twice, one for the end of the 273 // prolog code and one for a new loop preheader 274 BasicBlock *PEnd = SplitEdge(PH, Header, LPM->getAsPass()); 275 BasicBlock *NewPH = SplitBlock(PEnd, PEnd->getTerminator(), LPM->getAsPass()); 276 BranchInst *PreHeaderBR = cast<BranchInst>(PH->getTerminator()); 277 278 // Compute the number of extra iterations required, which is: 279 // extra iterations = run-time trip count % (loop unroll factor + 1) 280 SCEVExpander Expander(*SE, "loop-unroll"); 281 Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(), 282 PreHeaderBR); 283 284 IRBuilder<> B(PreHeaderBR); 285 Value *ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter"); 286 287 // Check if for no extra iterations, then jump to unrolled loop. We have to 288 // check that the trip count computation didn't overflow when adding one to 289 // the backedge taken count. 290 Value *LCmp = B.CreateIsNotNull(ModVal, "lcmp.mod"); 291 Value *OverflowCheck = B.CreateIsNull(TripCount, "lcmp.overflow"); 292 Value *BranchVal = B.CreateOr(OverflowCheck, LCmp, "lcmp.or"); 293 294 // Branch to either the extra iterations or the unrolled loop 295 // We will fix up the true branch label when adding loop body copies 296 BranchInst::Create(PEnd, PEnd, BranchVal, PreHeaderBR); 297 assert(PreHeaderBR->isUnconditional() && 298 PreHeaderBR->getSuccessor(0) == PEnd && 299 "CFG edges in Preheader are not correct"); 300 PreHeaderBR->eraseFromParent(); 301 302 ValueToValueMapTy LVMap; 303 Function *F = Header->getParent(); 304 // These variables are used to update the CFG links in each iteration 305 BasicBlock *CompareBB = nullptr; 306 BasicBlock *LastLoopBB = PH; 307 // Get an ordered list of blocks in the loop to help with the ordering of the 308 // cloned blocks in the prolog code 309 LoopBlocksDFS LoopBlocks(L); 310 LoopBlocks.perform(LI); 311 312 // 313 // For each extra loop iteration, create a copy of the loop's basic blocks 314 // and generate a condition that branches to the copy depending on the 315 // number of 'left over' iterations. 316 // 317 for (unsigned leftOverIters = Count-1; leftOverIters > 0; --leftOverIters) { 318 std::vector<BasicBlock*> NewBlocks; 319 ValueToValueMapTy VMap; 320 321 // Clone all the basic blocks in the loop, but we don't clone the loop 322 // This function adds the appropriate CFG connections. 323 CloneLoopBlocks(L, (leftOverIters == Count-1), LastLoopBB, PEnd, NewBlocks, 324 LoopBlocks, VMap, LVMap, LI); 325 LastLoopBB = cast<BasicBlock>(VMap[Latch]); 326 327 // Insert the cloned blocks into function just before the original loop 328 F->getBasicBlockList().splice(PEnd, F->getBasicBlockList(), 329 NewBlocks[0], F->end()); 330 331 // Generate the code for the comparison which determines if the loop 332 // prolog code needs to be executed. 333 if (leftOverIters == Count-1) { 334 // There is no compare block for the fall-thru case when for the last 335 // left over iteration 336 CompareBB = NewBlocks[0]; 337 } else { 338 // Create a new block for the comparison 339 BasicBlock *NewBB = BasicBlock::Create(CompareBB->getContext(), "unr.cmp", 340 F, CompareBB); 341 if (Loop *ParentLoop = L->getParentLoop()) { 342 // Add the new block to the parent loop, if needed 343 ParentLoop->addBasicBlockToLoop(NewBB, LI->getBase()); 344 } 345 346 // The comparison w/ the extra iteration value and branch 347 Type *CountTy = TripCount->getType(); 348 Value *BranchVal = new ICmpInst(*NewBB, ICmpInst::ICMP_EQ, ModVal, 349 ConstantInt::get(CountTy, leftOverIters), 350 "un.tmp"); 351 // Branch to either the extra iterations or the unrolled loop 352 BranchInst::Create(NewBlocks[0], CompareBB, 353 BranchVal, NewBB); 354 CompareBB = NewBB; 355 PH->getTerminator()->setSuccessor(0, NewBB); 356 VMap[NewPH] = CompareBB; 357 } 358 359 // Rewrite the cloned instruction operands to use the values 360 // created when the clone is created. 361 for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) { 362 for (BasicBlock::iterator I = NewBlocks[i]->begin(), 363 E = NewBlocks[i]->end(); I != E; ++I) { 364 RemapInstruction(I, VMap, 365 RF_NoModuleLevelChanges|RF_IgnoreMissingEntries); 366 } 367 } 368 } 369 370 // Connect the prolog code to the original loop and update the 371 // PHI functions. 372 ConnectProlog(L, TripCount, Count, LastLoopBB, PEnd, PH, NewPH, LVMap, 373 LPM->getAsPass()); 374 NumRuntimeUnrolled++; 375 return true; 376 } 377