lib/Transforms/Scalar/LoopUnroll.cpp

   1 //===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===//
   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 pass implements a simple loop unroller.  It works best when loops have
  11 // been canonicalized by the -indvars pass, allowing it to determine the trip
  12 // counts of loops easily.
  13 //
  14 // This pass will multi-block loops only if they contain no non-unrolled
  15 // subloops.  The process of unrolling can produce extraneous basic blocks
  16 // linked with unconditional branches.  This will be corrected in the future.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "loop-unroll"
  21 #include "llvm/Transforms/Scalar.h"
  22 #include "llvm/Constants.h"
  23 #include "llvm/Function.h"
  24 #include "llvm/Instructions.h"
  25 #include "llvm/Analysis/ConstantFolding.h"
  26 #include "llvm/Analysis/LoopInfo.h"
  27 #include "llvm/Analysis/LoopPass.h"
  28 #include "llvm/Transforms/Utils/Cloning.h"
  29 #include "llvm/Transforms/Utils/Local.h"
  30 #include "llvm/Support/CFG.h"
  31 #include "llvm/Support/Compiler.h"
  32 #include "llvm/Support/CommandLine.h"
  33 #include "llvm/Support/Debug.h"
  34 #include "llvm/Support/MathExtras.h"
  35 #include "llvm/ADT/Statistic.h"
  36 #include "llvm/ADT/STLExtras.h"
  37 #include "llvm/ADT/SmallPtrSet.h"
  38 #include "llvm/IntrinsicInst.h"
  39 #include <cstdio>
  40 #include <algorithm>
  41 using namespace llvm;
  42
  43 STATISTIC(NumCompletelyUnrolled, "Number of loops completely unrolled");
  44 STATISTIC(NumUnrolled,    "Number of loops unrolled (completely or otherwise)");
  45
  46 namespace {
  47   cl::opt<unsigned>
  48   UnrollThreshold
  49     ("unroll-threshold", cl::init(100), cl::Hidden,
  50      cl::desc("The cut-off point for automatic loop unrolling"));
  51
  52   cl::opt<unsigned>
  53   UnrollCount
  54     ("unroll-count", cl::init(0), cl::Hidden,
  55      cl::desc("Use this unroll count for all loops, for testing purposes"));
  56
  57   class VISIBILITY_HIDDEN LoopUnroll : public LoopPass {
  58     LoopInfo *LI;  // The current loop information
  59   public:
  60     static char ID; // Pass ID, replacement for typeid
  61     LoopUnroll() : LoopPass((intptr_t)&ID) {}
  62
  63     /// A magic value for use with the Threshold parameter to indicate
  64     /// that the loop unroll should be performed regardless of how much
  65     /// code expansion would result.
  66     static const unsigned NoThreshold = UINT_MAX;
  67
  68     bool runOnLoop(Loop *L, LPPassManager &LPM);
  69     bool unrollLoop(Loop *L, unsigned Count, unsigned Threshold);
  70     BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB);
  71
  72     /// This transformation requires natural loop information & requires that
  73     /// loop preheaders be inserted into the CFG...
  74     ///
  75     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  76       AU.addRequiredID(LoopSimplifyID);
  77       AU.addRequiredID(LCSSAID);
  78       AU.addRequired<LoopInfo>();
  79       AU.addPreservedID(LCSSAID);
  80       AU.addPreserved<LoopInfo>();
  81     }
  82   };
  83   char LoopUnroll::ID = 0;
  84   RegisterPass<LoopUnroll> X("loop-unroll", "Unroll loops");
  85 }
  86
  87 LoopPass *llvm::createLoopUnrollPass() { return new LoopUnroll(); }
  88
  89 /// ApproximateLoopSize - Approximate the size of the loop.
  90 static unsigned ApproximateLoopSize(const Loop *L) {
  91   unsigned Size = 0;
  92   for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i) {
  93     BasicBlock *BB = L->getBlocks()[i];
  94     Instruction *Term = BB->getTerminator();
  95     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
  96       if (isa<PHINode>(I) && BB == L->getHeader()) {
  97         // Ignore PHI nodes in the header.
  98       } else if (I->hasOneUse() && I->use_back() == Term) {
  99         // Ignore instructions only used by the loop terminator.
 100       } else if (isa<DbgInfoIntrinsic>(I)) {
 101         // Ignore debug instructions
 102       } else {
 103         ++Size;
 104       }
 105
 106       // TODO: Ignore expressions derived from PHI and constants if inval of phi
 107       // is a constant, or if operation is associative.  This will get induction
 108       // variables.
 109     }
 110   }
 111
 112   return Size;
 113 }
 114
 115 // RemapInstruction - Convert the instruction operands from referencing the
 116 // current values into those specified by ValueMap.
 117 //
 118 static inline void RemapInstruction(Instruction *I,
 119                                     DenseMap<const Value *, Value*> &ValueMap) {
 120   for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) {
 121     Value *Op = I->getOperand(op);
 122     DenseMap<const Value *, Value*>::iterator It = ValueMap.find(Op);
 123     if (It != ValueMap.end()) Op = It->second;
 124     I->setOperand(op, Op);
 125   }
 126 }
 127
 128 // FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it
 129 // only has one predecessor, and that predecessor only has one successor.
 130 // Returns the new combined block.
 131 BasicBlock *LoopUnroll::FoldBlockIntoPredecessor(BasicBlock *BB) {
 132   // Merge basic blocks into their predecessor if there is only one distinct
 133   // pred, and if there is only one distinct successor of the predecessor, and
 134   // if there are no PHI nodes.
 135   //
 136   BasicBlock *OnlyPred = BB->getSinglePredecessor();
 137   if (!OnlyPred) return 0;
 138
 139   if (OnlyPred->getTerminator()->getNumSuccessors() != 1)
 140     return 0;
 141
 142   DOUT << "Merging: " << *BB << "into: " << *OnlyPred;
 143
 144   // Resolve any PHI nodes at the start of the block.  They are all
 145   // guaranteed to have exactly one entry if they exist, unless there are
 146   // multiple duplicate (but guaranteed to be equal) entries for the
 147   // incoming edges.  This occurs when there are multiple edges from
 148   // OnlyPred to OnlySucc.
 149   //
 150   while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
 151     PN->replaceAllUsesWith(PN->getIncomingValue(0));
 152     BB->getInstList().pop_front();  // Delete the phi node...
 153   }
 154
 155   // Delete the unconditional branch from the predecessor...
 156   OnlyPred->getInstList().pop_back();
 157
 158   // Move all definitions in the successor to the predecessor...
 159   OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
 160
 161   // Make all PHI nodes that referred to BB now refer to Pred as their
 162   // source...
 163   BB->replaceAllUsesWith(OnlyPred);
 164
 165   std::string OldName = BB->getName();
 166
 167   // Erase basic block from the function...
 168   LI->removeBlock(BB);
 169   BB->eraseFromParent();
 170
 171   // Inherit predecessor's name if it exists...
 172   if (!OldName.empty() && !OnlyPred->hasName())
 173     OnlyPred->setName(OldName);
 174
 175   return OnlyPred;
 176 }
 177
 178 bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) {
 179   LI = &getAnalysis<LoopInfo>();
 180
 181   // Unroll the loop.
 182   if (!unrollLoop(L, UnrollCount, UnrollThreshold))
 183     return false;
 184
 185   // Update the loop information for this loop.
 186   // If we completely unrolled the loop, remove it from the parent.
 187   if (L->getNumBackEdges() == 0)
 188     LPM.deleteLoopFromQueue(L);
 189
 190   return true;
 191 }
 192
 193 /// Unroll the given loop by UnrollCount, or by a heuristically-determined
 194 /// value if Count is zero. If Threshold is not NoThreshold, it is a value
 195 /// to limit code size expansion. If the loop size would expand beyond the
 196 /// threshold value, unrolling is suppressed. The return value is true if
 197 /// any transformations are performed.
 198 ///
 199 bool LoopUnroll::unrollLoop(Loop *L, unsigned Count, unsigned Threshold) {
 200   assert(L->isLCSSAForm());
 201
 202   BasicBlock *Header = L->getHeader();
 203   BasicBlock *LatchBlock = L->getLoopLatch();
 204   BranchInst *BI = dyn_cast<BranchInst>(LatchBlock->getTerminator());
 205
 206   DOUT << "Loop Unroll: F[" << Header->getParent()->getName()
 207        << "] Loop %" << Header->getName() << "\n";
 208
 209   if (!BI || BI->isUnconditional()) {
 210     // The loop-rorate pass can be helpful to avoid this in many cases.
 211     DOUT << "  Can't unroll; loop not terminated by a conditional branch.\n";
 212     return false;
 213   }
 214
 215   // Determine the trip count and/or trip multiple. A TripCount value of zero
 216   // is used to mean an unknown trip count. The TripMultiple value is the
 217   // greatest known integer multiple of the trip count.
 218   unsigned TripCount = 0;
 219   unsigned TripMultiple = 1;
 220   if (Value *TripCountValue = L->getTripCount()) {
 221     if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCountValue)) {
 222       // Guard against huge trip counts. This also guards against assertions in
 223       // APInt from the use of getZExtValue, below.
 224       if (TripCountC->getValue().getActiveBits() <= 32) {
 225         TripCount = (unsigned)TripCountC->getZExtValue();
 226       }
 227     } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCountValue)) {
 228       switch (BO->getOpcode()) {
 229       case BinaryOperator::Mul:
 230         if (ConstantInt *MultipleC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
 231           if (MultipleC->getValue().getActiveBits() <= 32) {
 232             TripMultiple = (unsigned)MultipleC->getZExtValue();
 233           }
 234         }
 235         break;
 236       default: break;
 237       }
 238     }
 239   }
 240   if (TripCount != 0)
 241     DOUT << "  Trip Count = " << TripCount << "\n";
 242   if (TripMultiple != 1)
 243     DOUT << "  Trip Multiple = " << TripMultiple << "\n";
 244
 245   // Automatically select an unroll count.
 246   if (Count == 0) {
 247     // Conservative heuristic: if we know the trip count, see if we can
 248     // completely unroll (subject to the threshold, checked below); otherwise
 249     // don't unroll.
 250     if (TripCount != 0) {
 251       Count = TripCount;
 252     } else {
 253       return false;
 254     }
 255   }
 256
 257   // Effectively "DCE" unrolled iterations that are beyond the tripcount
 258   // and will never be executed.
 259   if (TripCount != 0 && Count > TripCount)
 260     Count = TripCount;
 261
 262   assert(Count > 0);
 263   assert(TripMultiple > 0);
 264   assert(TripCount == 0 || TripCount % TripMultiple == 0);
 265
 266   // Enforce the threshold.
 267   if (Threshold != NoThreshold) {
 268     unsigned LoopSize = ApproximateLoopSize(L);
 269     DOUT << "  Loop Size = " << LoopSize << "\n";
 270     uint64_t Size = (uint64_t)LoopSize*Count;
 271     if (TripCount != 1 && Size > Threshold) {
 272       DOUT << "  TOO LARGE TO UNROLL: "
 273            << Size << ">" << Threshold << "\n";
 274       return false;
 275     }
 276   }
 277
 278   // Are we eliminating the loop control altogether?
 279   bool CompletelyUnroll = Count == TripCount;
 280
 281   // If we know the trip count, we know the multiple...
 282   unsigned BreakoutTrip = 0;
 283   if (TripCount != 0) {
 284     BreakoutTrip = TripCount % Count;
 285     TripMultiple = 0;
 286   } else {
 287     // Figure out what multiple to use.
 288     BreakoutTrip = TripMultiple =
 289       (unsigned)GreatestCommonDivisor64(Count, TripMultiple);
 290   }
 291
 292   if (CompletelyUnroll) {
 293     DOUT << "COMPLETELY UNROLLING loop %" << Header->getName()
 294          << " with trip count " << TripCount << "!\n";
 295   } else {
 296     DOUT << "UNROLLING loop %" << Header->getName()
 297          << " by " << Count;
 298     if (TripMultiple == 0 || BreakoutTrip != TripMultiple) {
 299       DOUT << " with a breakout at trip " << BreakoutTrip;
 300     } else if (TripMultiple != 1) {
 301       DOUT << " with " << TripMultiple << " trips per branch";
 302     }
 303     DOUT << "!\n";
 304   }
 305
 306   std::vector<BasicBlock*> LoopBlocks = L->getBlocks();
 307
 308   bool ContinueOnTrue = L->contains(BI->getSuccessor(0));
 309   BasicBlock *LoopExit = BI->getSuccessor(ContinueOnTrue);
 310
 311   // For the first iteration of the loop, we should use the precloned values for
 312   // PHI nodes.  Insert associations now.
 313   typedef DenseMap<const Value*, Value*> ValueMapTy;
 314   ValueMapTy LastValueMap;
 315   std::vector<PHINode*> OrigPHINode;
 316   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
 317     PHINode *PN = cast<PHINode>(I);
 318     OrigPHINode.push_back(PN);
 319     if (Instruction *I =
 320                 dyn_cast<Instruction>(PN->getIncomingValueForBlock(LatchBlock)))
 321       if (L->contains(I->getParent()))
 322         LastValueMap[I] = I;
 323   }
 324
 325   std::vector<BasicBlock*> Headers;
 326   std::vector<BasicBlock*> Latches;
 327   Headers.push_back(Header);
 328   Latches.push_back(LatchBlock);
 329
 330   for (unsigned It = 1; It != Count; ++It) {
 331     char SuffixBuffer[100];
 332     sprintf(SuffixBuffer, ".%d", It);
 333
 334     std::vector<BasicBlock*> NewBlocks;
 335
 336     for (std::vector<BasicBlock*>::iterator BB = LoopBlocks.begin(),
 337          E = LoopBlocks.end(); BB != E; ++BB) {
 338       ValueMapTy ValueMap;
 339       BasicBlock *New = CloneBasicBlock(*BB, ValueMap, SuffixBuffer);
 340       Header->getParent()->getBasicBlockList().push_back(New);
 341
 342       // Loop over all of the PHI nodes in the block, changing them to use the
 343       // incoming values from the previous block.
 344       if (*BB == Header)
 345         for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) {
 346           PHINode *NewPHI = cast<PHINode>(ValueMap[OrigPHINode[i]]);
 347           Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock);
 348           if (Instruction *InValI = dyn_cast<Instruction>(InVal))
 349             if (It > 1 && L->contains(InValI->getParent()))
 350               InVal = LastValueMap[InValI];
 351           ValueMap[OrigPHINode[i]] = InVal;
 352           New->getInstList().erase(NewPHI);
 353         }
 354
 355       // Update our running map of newest clones
 356       LastValueMap[*BB] = New;
 357       for (ValueMapTy::iterator VI = ValueMap.begin(), VE = ValueMap.end();
 358            VI != VE; ++VI)
 359         LastValueMap[VI->first] = VI->second;
 360
 361       L->addBasicBlockToLoop(New, LI->getBase());
 362
 363       // Add phi entries for newly created values to all exit blocks except
 364       // the successor of the latch block.  The successor of the exit block will
 365       // be updated specially after unrolling all the way.
 366       if (*BB != LatchBlock)
 367         for (Value::use_iterator UI = (*BB)->use_begin(), UE = (*BB)->use_end();
 368              UI != UE; ++UI) {
 369           Instruction *UseInst = cast<Instruction>(*UI);
 370           if (isa<PHINode>(UseInst) && !L->contains(UseInst->getParent())) {
 371             PHINode *phi = cast<PHINode>(UseInst);
 372             Value *Incoming = phi->getIncomingValueForBlock(*BB);
 373             phi->addIncoming(Incoming, New);
 374           }
 375         }
 376
 377       // Keep track of new headers and latches as we create them, so that
 378       // we can insert the proper branches later.
 379       if (*BB == Header)
 380         Headers.push_back(New);
 381       if (*BB == LatchBlock) {
 382         Latches.push_back(New);
 383
 384         // Also, clear out the new latch's back edge so that it doesn't look
 385         // like a new loop, so that it's amenable to being merged with adjacent
 386         // blocks later on.
 387         TerminatorInst *Term = New->getTerminator();
 388         assert(L->contains(Term->getSuccessor(!ContinueOnTrue)));
 389         assert(Term->getSuccessor(ContinueOnTrue) == LoopExit);
 390         Term->setSuccessor(!ContinueOnTrue, NULL);
 391       }
 392
 393       NewBlocks.push_back(New);
 394     }
 395
 396     // Remap all instructions in the most recent iteration
 397     for (unsigned i = 0; i < NewBlocks.size(); ++i)
 398       for (BasicBlock::iterator I = NewBlocks[i]->begin(),
 399            E = NewBlocks[i]->end(); I != E; ++I)
 400         RemapInstruction(I, LastValueMap);
 401   }
 402
 403   // The latch block exits the loop.  If there are any PHI nodes in the
 404   // successor blocks, update them to use the appropriate values computed as the
 405   // last iteration of the loop.
 406   if (Count != 1) {
 407     SmallPtrSet<PHINode*, 8> Users;
 408     for (Value::use_iterator UI = LatchBlock->use_begin(),
 409          UE = LatchBlock->use_end(); UI != UE; ++UI)
 410       if (PHINode *phi = dyn_cast<PHINode>(*UI))
 411         Users.insert(phi);
 412
 413     BasicBlock *LastIterationBB = cast<BasicBlock>(LastValueMap[LatchBlock]);
 414     for (SmallPtrSet<PHINode*,8>::iterator SI = Users.begin(), SE = Users.end();
 415          SI != SE; ++SI) {
 416       PHINode *PN = *SI;
 417       Value *InVal = PN->removeIncomingValue(LatchBlock, false);
 418       // If this value was defined in the loop, take the value defined by the
 419       // last iteration of the loop.
 420       if (Instruction *InValI = dyn_cast<Instruction>(InVal)) {
 421         if (L->contains(InValI->getParent()))
 422           InVal = LastValueMap[InVal];
 423       }
 424       PN->addIncoming(InVal, LastIterationBB);
 425     }
 426   }
 427
 428   // Now, if we're doing complete unrolling, loop over the PHI nodes in the
 429   // original block, setting them to their incoming values.
 430   if (CompletelyUnroll) {
 431     BasicBlock *Preheader = L->getLoopPreheader();
 432     for (unsigned i = 0, e = OrigPHINode.size(); i != e; ++i) {
 433       PHINode *PN = OrigPHINode[i];
 434       PN->replaceAllUsesWith(PN->getIncomingValueForBlock(Preheader));
 435       Header->getInstList().erase(PN);
 436     }
 437   }
 438
 439   // Now that all the basic blocks for the unrolled iterations are in place,
 440   // set up the branches to connect them.
 441   for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
 442     // The original branch was replicated in each unrolled iteration.
 443     BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
 444
 445     // The branch destination.
 446     unsigned j = (i + 1) % e;
 447     BasicBlock *Dest = Headers[j];
 448     bool NeedConditional = true;
 449
 450     // For a complete unroll, make the last iteration end with a branch
 451     // to the exit block.
 452     if (CompletelyUnroll && j == 0) {
 453       Dest = LoopExit;
 454       NeedConditional = false;
 455     }
 456
 457     // If we know the trip count or a multiple of it, we can safely use an
 458     // unconditional branch for some iterations.
 459     if (j != BreakoutTrip && (TripMultiple == 0 || j % TripMultiple != 0)) {
 460       NeedConditional = false;
 461     }
 462
 463     if (NeedConditional) {
 464       // Update the conditional branch's successor for the following
 465       // iteration.
 466       Term->setSuccessor(!ContinueOnTrue, Dest);
 467     } else {
 468       Term->setUnconditionalDest(Dest);
 469       // Merge adjacent basic blocks, if possible.
 470       if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest)) {
 471         std::replace(Latches.begin(), Latches.end(), Dest, Fold);
 472         std::replace(Headers.begin(), Headers.end(), Dest, Fold);
 473       }
 474     }
 475   }
 476
 477   // At this point, the code is well formed.  We now do a quick sweep over the
 478   // inserted code, doing constant propagation and dead code elimination as we
 479   // go.
 480   const std::vector<BasicBlock*> &NewLoopBlocks = L->getBlocks();
 481   for (std::vector<BasicBlock*>::const_iterator BB = NewLoopBlocks.begin(),
 482        BBE = NewLoopBlocks.end(); BB != BBE; ++BB)
 483     for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ) {
 484       Instruction *Inst = I++;
 485
 486       if (isInstructionTriviallyDead(Inst))
 487         (*BB)->getInstList().erase(Inst);
 488       else if (Constant *C = ConstantFoldInstruction(Inst)) {
 489         Inst->replaceAllUsesWith(C);
 490         (*BB)->getInstList().erase(Inst);
 491       }
 492     }
 493
 494   NumCompletelyUnrolled += CompletelyUnroll;
 495   ++NumUnrolled;
 496   return true;
 497 }