lib/Transforms/Utils/UnrollLoop.cpp

   1 //===-- UnrollLoop.cpp - 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. It does not define any
  11 // actual pass or policy, but provides a single function to perform loop
  12 // unrolling.
  13 //
  14 // It works best when loops have been canonicalized by the -indvars pass,
  15 // allowing it to determine the trip counts of loops easily.
  16 //
  17 // The process of unrolling can produce extraneous basic blocks linked with
  18 // unconditional branches.  This will be corrected in the future.
  19 //===----------------------------------------------------------------------===//
  20
  21 #define DEBUG_TYPE "loop-unroll"
  22 #include "llvm/Transforms/Utils/UnrollLoop.h"
  23 #include "llvm/BasicBlock.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/Analysis/ConstantFolding.h"
  27 #include "llvm/Analysis/LoopPass.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Transforms/Utils/Cloning.h"
  30 #include "llvm/Transforms/Utils/Local.h"
  31
  32 using namespace llvm;
  33
  34 /* TODO: Should these be here or in LoopUnroll? */
  35 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
  36 STATISTIC(NumUnrolled,    "Number of loops unrolled (completely or otherwise)");
  37
  38 /// RemapInstruction - Convert the instruction operands from referencing the
  39 /// current values into those specified by ValueMap.
  40 static inline void RemapInstruction(Instruction *I,
  41                                     DenseMap<const Value *, Value*> &ValueMap) {
  42   for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
  43     Value *Op = I->getOperand(op);
  44     DenseMap<const Value *, Value*>::iterator It = ValueMap.find(Op);
  45     if (It != ValueMap.end()) Op = It->second;
  46     I->setOperand(op, Op);
  47   }
  48 }
  49
  50 /// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it
  51 /// only has one predecessor, and that predecessor only has one successor.
  52 /// The LoopInfo Analysis that is passed will be kept consistent.
  53 /// Returns the new combined block.
  54 static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI) {
  55   // Merge basic blocks into their predecessor if there is only one distinct
  56   // pred, and if there is only one distinct successor of the predecessor, and
  57   // if there are no PHI nodes.
  58   BasicBlock *OnlyPred = BB->getSinglePredecessor();
  59   if (!OnlyPred) return 0;
  60
  61   if (OnlyPred->getTerminator()->getNumSuccessors() != 1)
  62     return 0;
  63
  64   DOUT << "Merging: " << *BB << "into: " << *OnlyPred;
  65
  66   // Resolve any PHI nodes at the start of the block.  They are all
  67   // guaranteed to have exactly one entry if they exist, unless there are
  68   // multiple duplicate (but guaranteed to be equal) entries for the
  69   // incoming edges.  This occurs when there are multiple edges from
  70   // OnlyPred to OnlySucc.
  71   //
  72   while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
  73     PN->replaceAllUsesWith(PN->getIncomingValue(0));
  74     BB->getInstList().pop_front();  // Delete the phi node...
  75   }
  76
  77   // Delete the unconditional branch from the predecessor...
  78   OnlyPred->getInstList().pop_back();
  79
  80   // Move all definitions in the successor to the predecessor...
  81   OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
  82
  83   // Make all PHI nodes that referred to BB now refer to Pred as their
  84   // source...
  85   BB->replaceAllUsesWith(OnlyPred);
  86
  87   std::string OldName = BB->getName();
  88
  89   // Erase basic block from the function...
  90   LI->removeBlock(BB);
  91   BB->eraseFromParent();
  92
  93   // Inherit predecessor's name if it exists...
  94   if (!OldName.empty() && !OnlyPred->hasName())
  95     OnlyPred->setName(OldName);
  96
  97   return OnlyPred;
  98 }
  99
 100 /// Unroll the given loop by Count. The loop must be in LCSSA form. Returns true
 101 /// if unrolling was succesful, or false if the loop was unmodified. Unrolling
 102 /// can only fail when the loop's latch block is not terminated by a conditional
 103 /// branch instruction. However, if the trip count (and multiple) are not known,
 104 /// loop unrolling will mostly produce more code that is no faster.
 105 ///
 106 /// The LoopInfo Analysis that is passed will be kept consistent.
 107 ///
 108 /// If a LoopPassManager is passed in, and the loop is fully removed, it will be
 109 /// removed from the LoopPassManager as well. LPM can also be NULL.
 110 bool llvm::UnrollLoop(Loop *L, unsigned Count, LoopInfo* LI,
 111                       LPPassManager* LPM) {
 112   assert(L->isLCSSAForm());
 113
 114   BasicBlock *Header = L->getHeader();
 115   BasicBlock *LatchBlock = L->getLoopLatch();
 116   BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
 117
 118   Function *Func = Header->getParent();
 119   Function::iterator BBInsertPt = next(Function::iterator(LatchBlock));
 120
 121   if (!BI || BI->isUnconditional()) {
 122     // The loop-rotate pass can be helpful to avoid this in many cases.
 123     DOUT << "  Can't unroll; loop not terminated by a conditional branch.\n";
 124     return false;
 125   }
 126
 127   // Find trip count
 128   unsigned TripCount = L->getSmallConstantTripCount();
 129   // Find trip multiple if count is not available
 130   unsigned TripMultiple = 1;
 131   if (TripCount == 0)
 132     TripMultiple = L->getSmallConstantTripMultiple();
 133
 134   if (TripCount != 0)
 135     DOUT << "  Trip Count = " << TripCount << "\n";
 136   if (TripMultiple != 1)
 137     DOUT << "  Trip Multiple = " << TripMultiple << "\n";
 138
 139   // Effectively "DCE" unrolled iterations that are beyond the tripcount
 140   // and will never be executed.
 141   if (TripCount != 0 && Count > TripCount)
 142     Count = TripCount;
 143
 144   assert(Count > 0);
 145   assert(TripMultiple > 0);
 146   assert(TripCount == 0 || TripCount % TripMultiple == 0);
 147
 148   // Are we eliminating the loop control altogether?
 149   bool CompletelyUnroll = Count == TripCount;
 150
 151   // If we know the trip count, we know the multiple...
 152   unsigned BreakoutTrip = 0;
 153   if (TripCount != 0) {
 154     BreakoutTrip = TripCount % Count;
 155     TripMultiple = 0;
 156   } else {
 157     // Figure out what multiple to use.
 158     BreakoutTrip = TripMultiple =
 159       (unsigned)GreatestCommonDivisor64(Count, TripMultiple);
 160   }
 161
 162   if (CompletelyUnroll) {
 163     DOUT << "COMPLETELY UNROLLING loop %" << Header->getName()
 164          << " with trip count " << TripCount << "!\n";
 165   } else {
 166     DOUT << "UNROLLING loop %" << Header->getName()
 167          << " by " << Count;
 168     if (TripMultiple == 0 || BreakoutTrip != TripMultiple) {
 169       DOUT << " with a breakout at trip " << BreakoutTrip;
 170     } else if (TripMultiple != 1) {
 171       DOUT << " with " << TripMultiple << " trips per branch";
 172     }
 173     DOUT << "!\n";
 174   }
 175
 176   // Make a copy of the original LoopBlocks list so we can keep referring
 177   // to it while hacking on the loop.
 178   std::vector<BasicBlock*> LoopBlocks = L->getBlocks();
 179
 180   bool ContinueOnTrue = BI->getSuccessor(0) == Header;
 181   BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue);
 182
 183   // For the first iteration of the loop, we should use the precloned values for
 184   // PHI nodes.  Insert associations now.
 185   typedef DenseMap<const Value*, Value*> ValueMapTy;
 186   ValueMapTy LastValueMap;
 187   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 188     PHINode *PN = cast<PHINode>(I);
 189     if (Instruction *I =
 190                 dyn_cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock)))
 191       if (L->contains(I->getParent()))
 192         LastValueMap[I] = I;
 193   }
 194
 195   // Keep track of all the headers and latches that we create. These are
 196   // needed by the logic that inserts the branches to connect all the
 197   // new blocks.
 198   std::vector<BasicBlock*> Headers;
 199   std::vector<BasicBlock*> Latches;
 200   Headers.reserve(Count);
 201   Latches.reserve(Count);
 202   Headers.push_back(Header);
 203   Latches.push_back(LatchBlock);
 204
 205   // Iterate through all but the first iterations, cloning blocks from
 206   // the first iteration to populate the subsequent iterations.
 207   for (unsigned It = 1; It != Count; ++It) {
 208     char SuffixBuffer[100];
 209     sprintf(SuffixBuffer, ".%d", It);
 210
 211     std::vector<BasicBlock*> NewBlocks;
 212     NewBlocks.reserve(LoopBlocks.size());
 213
 214     // Iterate through all the blocks in the original loop.
 215     for (std::vector<BasicBlock*>::const_iterator BBI = LoopBlocks.begin(),
 216          E = LoopBlocks.end(); BBI != E; ++BBI) {
 217       bool SuppressExitEdges = false;
 218       BasicBlock *BB = *BBI;
 219       ValueMapTy ValueMap;
 220       BasicBlock *New = CloneBasicBlock(BB, ValueMap, SuffixBuffer);
 221       NewBlocks.push_back(New);
 222       Func->getBasicBlockList().insert(BBInsertPt, New);
 223       L->addBasicBlockToLoop(New, LI->getBase());
 224
 225       // Special handling for the loop header block.
 226       if (BB == Header) {
 227         // Keep track of new headers as we create them, so that we can insert
 228         // the proper branches later.
 229         Headers[It] = New;
 230
 231         // Loop over all of the PHI nodes in the block, changing them to use
 232         // the incoming values from the previous block.
 233         for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 234           PHINode *NewPHI = cast<PHINode>(ValueMap[I]);
 235           Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock);
 236           if (Instruction *InValI = dyn_cast<Instruction>(InVal))
 237             if (It > 1 && L->contains(InValI->getParent()))
 238               InVal = LastValueMap[InValI];
 239           ValueMap[I] = InVal;
 240           New->getInstList().erase(NewPHI);
 241         }
 242       }
 243
 244       // Special handling for the loop latch block.
 245       if (BB == LatchBlock) {
 246         // Keep track of new latches as we create them, so that we can insert
 247         // the proper branches later.
 248         Latches[It] = New;
 249
 250         // If knowledge of the trip count and/or multiple will allow us
 251         // to emit unconditional branches in some of the new latch blocks,
 252         // those blocks shouldn't be referenced by PHIs that reference
 253         // the original latch.
 254         unsigned NextIt = (It + 1) % Count;
 255         SuppressExitEdges =
 256           NextIt != BreakoutTrip &&
 257           (TripMultiple == 0 || NextIt % TripMultiple != 0);
 258       }
 259
 260       // Update our running map of newest clones
 261       LastValueMap[BB] = New;
 262       for (ValueMapTy::iterator VI = ValueMap.begin(), VE = ValueMap.end();
 263            VI != VE; ++VI)
 264         LastValueMap[VI->first] = VI->second;
 265
 266       // Add incoming values to phi nodes that reference this block. The last
 267       // latch block may need to be referenced by the first header, and any
 268       // block with an exit edge may be referenced from outside the loop.
 269       for (Value::use_iterator UI = BB->use_begin(), UE = BB->use_end();
 270            UI != UE; ) {
 271         PHINode *PN = dyn_cast<PHINode>(*UI++);
 272         if (PN &&
 273             ((BB == LatchBlock && It == Count - 1 && !CompletelyUnroll) ||
 274              (!SuppressExitEdges && !L->contains(PN->getParent())))) {
 275           Value *InVal = PN->getIncomingValueForBlock(BB);
 276           // If this value was defined in the loop, take the value defined
 277           // by the last iteration of the loop.
 278           ValueMapTy::iterator VI = LastValueMap.find(InVal);
 279           if (VI != LastValueMap.end())
 280             InVal = VI->second;
 281           PN->addIncoming(InVal, New);
 282         }
 283       }
 284     }
 285
 286     // Remap all instructions in the most recent iteration
 287     for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i)
 288       for (BasicBlock::iterator I = NewBlocks[i]->begin(),
 289            E = NewBlocks[i]->end(); I != E; ++I)
 290         RemapInstruction(I, LastValueMap);
 291   }
 292
 293   // Now that all the basic blocks for the unrolled iterations are in place,
 294   // set up the branches to connect them.
 295   for (unsigned It = 0; It != Count; ++It) {
 296     // The original branch was replicated in each unrolled iteration.
 297     BranchInst *Term = cast<BranchInst>(Latches[It]->getTerminator());
 298
 299     // The branch destination.
 300     unsigned NextIt = (It + 1) % Count;
 301     BasicBlock *Dest = Headers[NextIt];
 302     bool NeedConditional = true;
 303     bool HasExit = true;
 304
 305     // For a complete unroll, make the last iteration end with an
 306     // unconditional branch to the exit block.
 307     if (CompletelyUnroll && NextIt == 0) {
 308       Dest = LoopExit;
 309       NeedConditional = false;
 310     }
 311
 312     // If we know the trip count or a multiple of it, we can safely use an
 313     // unconditional branch for some iterations.
 314     if (NextIt != BreakoutTrip &&
 315         (TripMultiple == 0 || NextIt % TripMultiple != 0)) {
 316       NeedConditional = false;
 317       HasExit = false;
 318     }
 319
 320     if (NeedConditional) {
 321       // Update the conditional branch's successor for the following
 322       // iteration.
 323       Term->setSuccessor(!ContinueOnTrue, Dest);
 324     } else {
 325       Term->setUnconditionalDest(Dest);
 326       // Merge adjacent basic blocks, if possible.
 327       if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI)) {
 328         std::replace(Latches.begin(), Latches.end(), Dest, Fold);
 329         std::replace(Headers.begin(), Headers.end(), Dest, Fold);
 330       }
 331     }
 332
 333     // Special handling for the first iteration. If the first latch is
 334     // now unconditionally branching to the second header, then it is
 335     // no longer an exit node. Delete PHI references to it both from
 336     // the first header and from outsie the loop.
 337     if (It == 0)
 338       for (Value::use_iterator UI = LatchBlock->use_begin(),
 339            UE = LatchBlock->use_end(); UI != UE; ) {
 340         PHINode *PN = dyn_cast<PHINode>(*UI++);
 341         if (PN && (PN->getParent() == Header ? Count > 1 : !HasExit))
 342           PN->removeIncomingValue(LatchBlock);
 343       }
 344   }
 345
 346   // At this point, unrolling is complete and the code is well formed.
 347   // Now, do some simplifications.
 348
 349   // If we're doing complete unrolling, loop over the PHI nodes in the
 350   // original block, setting them to their incoming values.
 351   if (CompletelyUnroll) {
 352     BasicBlock *Preheader = L->getLoopPreheader();
 353     for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ) {
 354       PHINode *PN = cast<PHINode>(I++);
 355       PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
 356       Header->getInstList().erase(PN);
 357     }
 358   }
 359
 360   // We now do a quick sweep over the inserted code, doing constant
 361   // propagation and dead code elimination as we go.
 362   for (Loop::block_iterator BI = L->block_begin(), BBE = L->block_end();
 363        BI != BBE; ++BI) {
 364     BasicBlock *BB = *BI;
 365     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
 366       Instruction *Inst = I++;
 367
 368       if (isInstructionTriviallyDead(Inst))
 369         BB->getInstList().erase(Inst);
 370       else if (Constant *C = ConstantFoldInstruction(Inst)) {
 371         Inst->replaceAllUsesWith(C);
 372         BB->getInstList().erase(Inst);
 373       }
 374     }
 375   }
 376
 377   NumCompletelyUnrolled += CompletelyUnroll;
 378   ++NumUnrolled;
 379   // Remove the loop from the LoopPassManager if it's completely removed.
 380   if (CompletelyUnroll && LPM != NULL)
 381     LPM->deleteLoopFromQueue(L);
 382
 383   // If we didn't completely unroll the loop, it should still be in LCSSA form.
 384   if (!CompletelyUnroll)
 385     assert(L->isLCSSAForm());
 386
 387   return true;
 388 }