lib/Transforms/Utils/LoopUnrollRuntime.cpp

   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   Type *CountTy = TripCount->getType();
 284   BinaryOperator *ModVal =
 285     BinaryOperator::CreateURem(TripCount,
 286                                ConstantInt::get(CountTy, Count),
 287                                "xtraiter");
 288   ModVal->insertBefore(PreHeaderBR);
 289
 290   // Check if for no extra iterations, then jump to unrolled loop
 291   Value *BranchVal = new ICmpInst(PreHeaderBR,
 292                                   ICmpInst::ICMP_NE, ModVal,
 293                                   ConstantInt::get(CountTy, 0), "lcmp");
 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       Value *BranchVal = new ICmpInst(*NewBB, ICmpInst::ICMP_EQ, ModVal,
 348                                       ConstantInt::get(CountTy, leftOverIters),
 349                                       "un.tmp");
 350       // Branch to either the extra iterations or the unrolled loop
 351       BranchInst::Create(NewBlocks[0], CompareBB,
 352                          BranchVal, NewBB);
 353       CompareBB = NewBB;
 354       PH->getTerminator()->setSuccessor(0, NewBB);
 355       VMap[NewPH] = CompareBB;
 356     }
 357
 358     // Rewrite the cloned instruction operands to use the values
 359     // created when the clone is created.
 360     for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) {
 361       for (BasicBlock::iterator I = NewBlocks[i]->begin(),
 362              E = NewBlocks[i]->end(); I != E; ++I) {
 363         RemapInstruction(I, VMap,
 364                          RF_NoModuleLevelChanges|RF_IgnoreMissingEntries);
 365       }
 366     }
 367   }
 368
 369   // Connect the prolog code to the original loop and update the
 370   // PHI functions.
 371   ConnectProlog(L, TripCount, Count, LastLoopBB, PEnd, PH, NewPH, LVMap,
 372                 LPM->getAsPass());
 373   NumRuntimeUnrolled++;
 374   return true;
 375 }