LLVM API Documentation
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 }