LLVM API Documentation

LoopUnroll.cpp

Go to the documentation of this file.
00001 //===-- LoopUnroll.cpp - Loop unroller pass -------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass implements a simple loop unroller.  It works best when loops have
00011 // been canonicalized by the -indvars pass, allowing it to determine the trip
00012 // counts of loops easily.
00013 //===----------------------------------------------------------------------===//
00014 
00015 #define DEBUG_TYPE "loop-unroll"
00016 #include "llvm/IntrinsicInst.h"
00017 #include "llvm/Transforms/Scalar.h"
00018 #include "llvm/Analysis/LoopInfo.h"
00019 #include "llvm/Analysis/LoopPass.h"
00020 #include "llvm/Support/Compiler.h"
00021 #include "llvm/Support/CommandLine.h"
00022 #include "llvm/Support/Debug.h"
00023 #include "llvm/Support/raw_ostream.h"
00024 #include "llvm/Transforms/Utils/UnrollLoop.h"
00025 #include <climits>
00026 
00027 using namespace llvm;
00028 
00029 static cl::opt<unsigned>
00030 UnrollThreshold("unroll-threshold", cl::init(100), cl::Hidden,
00031   cl::desc("The cut-off point for automatic loop unrolling"));
00032 
00033 static cl::opt<unsigned>
00034 UnrollCount("unroll-count", cl::init(0), cl::Hidden,
00035   cl::desc("Use this unroll count for all loops, for testing purposes"));
00036 
00037 static cl::opt<bool>
00038 UnrollAllowPartial("unroll-allow-partial", cl::init(false), cl::Hidden,
00039   cl::desc("Allows loops to be partially unrolled until "
00040            "-unroll-threshold loop size is reached."));
00041 
00042 namespace {
00043   class VISIBILITY_HIDDEN LoopUnroll : public LoopPass {
00044   public:
00045     static char ID; // Pass ID, replacement for typeid
00046     LoopUnroll() : LoopPass(&ID) {}
00047 
00048     /// A magic value for use with the Threshold parameter to indicate
00049     /// that the loop unroll should be performed regardless of how much
00050     /// code expansion would result.
00051     static const unsigned NoThreshold = UINT_MAX;
00052 
00053     bool runOnLoop(Loop *L, LPPassManager &LPM);
00054 
00055     /// This transformation requires natural loop information & requires that
00056     /// loop preheaders be inserted into the CFG...
00057     ///
00058     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00059       AU.addRequiredID(LoopSimplifyID);
00060       AU.addRequiredID(LCSSAID);
00061       AU.addRequired<LoopInfo>();
00062       AU.addPreservedID(LCSSAID);
00063       AU.addPreserved<LoopInfo>();
00064       // FIXME: Loop unroll requires LCSSA. And LCSSA requires dom info.
00065       // If loop unroll does not preserve dom info then LCSSA pass on next
00066       // loop will receive invalid dom info.
00067       // For now, recreate dom info, if loop is unrolled.
00068       AU.addPreserved<DominatorTree>();
00069       AU.addPreserved<DominanceFrontier>();
00070     }
00071   };
00072 }
00073 
00074 char LoopUnroll::ID = 0;
00075 static RegisterPass<LoopUnroll> X("loop-unroll", "Unroll loops");
00076 
00077 Pass *llvm::createLoopUnrollPass() { return new LoopUnroll(); }
00078 
00079 /// ApproximateLoopSize - Approximate the size of the loop.
00080 static unsigned ApproximateLoopSize(const Loop *L) {
00081   unsigned Size = 0;
00082   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
00083        I != E; ++I) {
00084     BasicBlock *BB = *I;
00085     Instruction *Term = BB->getTerminator();
00086     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
00087       if (isa<PHINode>(I) && BB == L->getHeader()) {
00088         // Ignore PHI nodes in the header.
00089       } else if (I->hasOneUse() && I->use_back() == Term) {
00090         // Ignore instructions only used by the loop terminator.
00091       } else if (isa<DbgInfoIntrinsic>(I)) {
00092         // Ignore debug instructions
00093       } else if (isa<GetElementPtrInst>(I) && I->hasOneUse()) {
00094         // Ignore GEP as they generally are subsumed into a load or store.
00095       } else if (isa<CallInst>(I)) {
00096         // Estimate size overhead introduced by call instructions which
00097         // is higher than other instructions. Here 3 and 10 are magic
00098         // numbers that help one isolated test case from PR2067 without
00099         // negatively impacting measured benchmarks.
00100         Size += isa<IntrinsicInst>(I) ? 3 : 10;
00101       } else {
00102         ++Size;
00103       }
00104 
00105       // TODO: Ignore expressions derived from PHI and constants if inval of phi
00106       // is a constant, or if operation is associative.  This will get induction
00107       // variables.
00108     }
00109   }
00110 
00111   return Size;
00112 }
00113 
00114 bool LoopUnroll::runOnLoop(Loop *L, LPPassManager &LPM) {
00115   assert(L->isLCSSAForm());
00116   LoopInfo *LI = &getAnalysis<LoopInfo>();
00117 
00118   BasicBlock *Header = L->getHeader();
00119   DEBUG(errs() << "Loop Unroll: F[" << Header->getParent()->getName()
00120         << "] Loop %" << Header->getName() << "\n");
00121   (void)Header;
00122 
00123   // Find trip count
00124   unsigned TripCount = L->getSmallConstantTripCount();
00125   unsigned Count = UnrollCount;
00126 
00127   // Automatically select an unroll count.
00128   if (Count == 0) {
00129     // Conservative heuristic: if we know the trip count, see if we can
00130     // completely unroll (subject to the threshold, checked below); otherwise
00131     // try to find greatest modulo of the trip count which is still under
00132     // threshold value.
00133     if (TripCount == 0)
00134       return false;
00135     Count = TripCount;
00136   }
00137 
00138   // Enforce the threshold.
00139   if (UnrollThreshold != NoThreshold) {
00140     unsigned LoopSize = ApproximateLoopSize(L);
00141     DEBUG(errs() << "  Loop Size = " << LoopSize << "\n");
00142     uint64_t Size = (uint64_t)LoopSize*Count;
00143     if (TripCount != 1 && Size > UnrollThreshold) {
00144       DEBUG(errs() << "  Too large to fully unroll with count: " << Count
00145             << " because size: " << Size << ">" << UnrollThreshold << "\n");
00146       if (!UnrollAllowPartial) {
00147         DEBUG(errs() << "  will not try to unroll partially because "
00148               << "-unroll-allow-partial not given\n");
00149         return false;
00150       }
00151       // Reduce unroll count to be modulo of TripCount for partial unrolling
00152       Count = UnrollThreshold / LoopSize;
00153       while (Count != 0 && TripCount%Count != 0) {
00154         Count--;
00155       }
00156       if (Count < 2) {
00157         DEBUG(errs() << "  could not unroll partially\n");
00158         return false;
00159       }
00160       DEBUG(errs() << "  partially unrolling with count: " << Count << "\n");
00161     }
00162   }
00163 
00164   // Unroll the loop.
00165   Function *F = L->getHeader()->getParent();
00166   if (!UnrollLoop(L, Count, LI, &LPM))
00167     return false;
00168 
00169   // FIXME: Reconstruct dom info, because it is not preserved properly.
00170   DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>();
00171   if (DT) {
00172     DT->runOnFunction(*F);
00173     DominanceFrontier *DF = getAnalysisIfAvailable<DominanceFrontier>();
00174     if (DF)
00175       DF->runOnFunction(*F);
00176   }
00177   return true;
00178 }