LLVM API Documentation
00001 //===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by Nate Begeman and is distributed under the 00006 // University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass performs a strength reduction on array references inside loops that 00011 // have as one or more of their components the loop induction variable. This is 00012 // accomplished by creating a new Value to hold the initial value of the array 00013 // access for the first iteration, and then creating a new GEP instruction in 00014 // the loop to increment the value by the appropriate amount. 00015 // 00016 // There are currently several deficiencies in the implementation, marked with 00017 // FIXME in the code. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #include "llvm/Transforms/Scalar.h" 00022 #include "llvm/Constants.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/Type.h" 00025 #include "llvm/Analysis/Dominators.h" 00026 #include "llvm/Analysis/LoopInfo.h" 00027 #include "llvm/Support/CFG.h" 00028 #include "llvm/Transforms/Utils/Local.h" 00029 #include "llvm/ADT/Statistic.h" 00030 #include <set> 00031 using namespace llvm; 00032 00033 namespace { 00034 Statistic<> NumReduced ("loop-reduce", "Number of GEPs strength reduced"); 00035 00036 class LoopStrengthReduce : public FunctionPass { 00037 LoopInfo *LI; 00038 DominatorSet *DS; 00039 bool Changed; 00040 public: 00041 virtual bool runOnFunction(Function &) { 00042 LI = &getAnalysis<LoopInfo>(); 00043 DS = &getAnalysis<DominatorSet>(); 00044 Changed = false; 00045 00046 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 00047 runOnLoop(*I); 00048 return Changed; 00049 } 00050 00051 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00052 AU.setPreservesCFG(); 00053 AU.addRequired<LoopInfo>(); 00054 AU.addRequired<DominatorSet>(); 00055 } 00056 private: 00057 void runOnLoop(Loop *L); 00058 void strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, 00059 Instruction *InsertBefore, 00060 std::set<Instruction*> &DeadInsts); 00061 void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts); 00062 }; 00063 RegisterOpt<LoopStrengthReduce> X("loop-reduce", 00064 "Strength Reduce GEP Uses of Ind. Vars"); 00065 } 00066 00067 FunctionPass *llvm::createLoopStrengthReducePass() { 00068 return new LoopStrengthReduce(); 00069 } 00070 00071 /// DeleteTriviallyDeadInstructions - If any of the instructions is the 00072 /// specified set are trivially dead, delete them and see if this makes any of 00073 /// their operands subsequently dead. 00074 void LoopStrengthReduce:: 00075 DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) { 00076 while (!Insts.empty()) { 00077 Instruction *I = *Insts.begin(); 00078 Insts.erase(Insts.begin()); 00079 if (isInstructionTriviallyDead(I)) { 00080 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 00081 if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i))) 00082 Insts.insert(U); 00083 I->getParent()->getInstList().erase(I); 00084 Changed = true; 00085 } 00086 } 00087 } 00088 00089 void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L, 00090 Instruction *InsertBefore, 00091 std::set<Instruction*> &DeadInsts) { 00092 // We will strength reduce the GEP by splitting it into two parts. The first 00093 // is a GEP to hold the initial value of the non-strength-reduced GEP upon 00094 // entering the loop, which we will insert at the end of the loop preheader. 00095 // The second is a GEP to hold the incremented value of the initial GEP. 00096 // The LoopIndVarSimplify pass guarantees that loop counts start at zero, so 00097 // we will replace the indvar with a constant zero value to create the first 00098 // GEP. 00099 // 00100 // We currently only handle GEP instructions that consist of zero or more 00101 // constants and one instance of the canonical induction variable. 00102 bool foundIndvar = false; 00103 bool indvarLast = false; 00104 std::vector<Value *> pre_op_vector; 00105 std::vector<Value *> inc_op_vector; 00106 Value *CanonicalIndVar = L->getCanonicalInductionVariable(); 00107 for (unsigned op = 1, e = GEPI->getNumOperands(); op != e; ++op) { 00108 Value *operand = GEPI->getOperand(op); 00109 if (operand == CanonicalIndVar) { 00110 // FIXME: We currently only support strength reducing GEP instructions 00111 // with one instance of the canonical induction variable. This means that 00112 // we can't deal with statements of the form A[i][i]. 00113 if (foundIndvar == true) 00114 return; 00115 00116 // FIXME: use getCanonicalInductionVariableIncrement to choose between 00117 // one and neg one maybe? We need to support int *foo = GEP base, -1 00118 const Type *Ty = CanonicalIndVar->getType(); 00119 pre_op_vector.push_back(Constant::getNullValue(Ty)); 00120 inc_op_vector.push_back(ConstantInt::get(Ty, 1)); 00121 foundIndvar = true; 00122 indvarLast = true; 00123 } else if (isa<Constant>(operand)) { 00124 pre_op_vector.push_back(operand); 00125 if (indvarLast == true) indvarLast = false; 00126 } else 00127 return; 00128 } 00129 // FIXME: handle GEPs where the indvar is not the last element of the index 00130 // array. 00131 if (indvarLast == false) 00132 return; 00133 assert(true == foundIndvar && "Indvar used by GEP not found in operand list"); 00134 00135 // FIXME: Being able to hoist the definition of the initial pointer value 00136 // would allow us to strength reduce more loops. For example, %tmp.32 in the 00137 // following loop: 00138 // entry: 00139 // br label %no_exit.0 00140 // no_exit.0: ; preds = %entry, %no_exit.0 00141 // %init.1.0 = phi uint [ 0, %entry ], [ %indvar.next, %no_exit.0 ] 00142 // %tmp.32 = load uint** %CROSSING 00143 // %tmp.35 = getelementptr uint* %tmp.32, uint %init.1.0 00144 // br label %no_exit.0 00145 BasicBlock *Header = L->getHeader(); 00146 if (Instruction *GepPtrOp = dyn_cast<Instruction>(GEPI->getOperand(0))) 00147 if (!DS->dominates(GepPtrOp, Header->begin())) 00148 return; 00149 00150 // If all operands of the GEP we are going to insert into the preheader 00151 // are constants, generate a GEP ConstantExpr instead. 00152 // 00153 // If there is only one operand after the initial non-constant one, we know 00154 // that it was the induction variable, and has been replaced by a constant 00155 // null value. In this case, replace the GEP with a use of pointer directly. 00156 // 00157 // 00158 BasicBlock *Preheader = L->getLoopPreheader(); 00159 Value *PreGEP; 00160 if (isa<Constant>(GEPI->getOperand(0))) { 00161 Constant *C = dyn_cast<Constant>(GEPI->getOperand(0)); 00162 PreGEP = ConstantExpr::getGetElementPtr(C, pre_op_vector); 00163 } else if (pre_op_vector.size() == 1) { 00164 PreGEP = GEPI->getOperand(0); 00165 } else { 00166 PreGEP = new GetElementPtrInst(GEPI->getOperand(0), 00167 pre_op_vector, GEPI->getName(), 00168 Preheader->getTerminator()); 00169 } 00170 00171 // The next step of the strength reduction is to create a PHI that will choose 00172 // between the initial GEP we created and inserted into the preheader, and 00173 // the incremented GEP that we will create below and insert into the loop body 00174 PHINode *NewPHI = new PHINode(PreGEP->getType(), 00175 GEPI->getName()+".str", InsertBefore); 00176 NewPHI->addIncoming(PreGEP, Preheader); 00177 00178 // Now, create the GEP instruction to increment the value selected by the PHI 00179 // instruction we just created above by one, and add it as the second incoming 00180 // Value and BasicBlock pair to the PHINode. 00181 Instruction *IncrInst = 00182 const_cast<Instruction*>(L->getCanonicalInductionVariableIncrement()); 00183 GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector, 00184 GEPI->getName()+".inc", 00185 IncrInst); 00186 NewPHI->addIncoming(StrGEP, IncrInst->getParent()); 00187 00188 // Replace all uses of the old GEP instructions with the new PHI 00189 GEPI->replaceAllUsesWith(NewPHI); 00190 00191 // The old GEP is now dead. 00192 DeadInsts.insert(GEPI); 00193 ++NumReduced; 00194 } 00195 00196 void LoopStrengthReduce::runOnLoop(Loop *L) { 00197 // First step, transform all loops nesting inside of this loop. 00198 for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I) 00199 runOnLoop(*I); 00200 00201 // Next, get the first PHINode since it is guaranteed to be the canonical 00202 // induction variable for the loop by the preceding IndVarSimplify pass. 00203 PHINode *PN = L->getCanonicalInductionVariable(); 00204 if (0 == PN) 00205 return; 00206 00207 // Insert secondary PHI nodes after the canonical induction variable's PHI 00208 // for the strength reduced pointers that we will be creating. 00209 Instruction *InsertBefore = PN->getNext(); 00210 00211 // FIXME: Need to use SCEV to detect GEP uses of the indvar, since indvars 00212 // pass creates code like this, which we can't currently detect: 00213 // %tmp.1 = sub uint 2000, %indvar 00214 // %tmp.8 = getelementptr int* %y, uint %tmp.1 00215 00216 // Strength reduce all GEPs in the Loop 00217 std::set<Instruction*> DeadInsts; 00218 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end(); 00219 UI != UE; ++UI) 00220 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) 00221 strengthReduceGEP(GEPI, L, InsertBefore, DeadInsts); 00222 00223 // Clean up after ourselves 00224 if (!DeadInsts.empty()) { 00225 DeleteTriviallyDeadInstructions(DeadInsts); 00226 00227 // At this point, we know that we have killed one or more GEP instructions. 00228 // It is worth checking to see if the cann indvar is also dead, so that we 00229 // can remove it as well. The requirements for the cann indvar to be 00230 // considered dead are: 00231 // 1. the cann indvar has one use 00232 // 2. the use is an add instruction 00233 // 3. the add has one use 00234 // 4. the add is used by the cann indvar 00235 // If all four cases above are true, then we can remove both the add and 00236 // the cann indvar. 00237 if (PN->hasOneUse()) { 00238 BinaryOperator *BO = dyn_cast<BinaryOperator>(*(PN->use_begin())); 00239 if (BO && BO->getOpcode() == Instruction::Add) 00240 if (BO->hasOneUse()) { 00241 PHINode *PotentialIndvar = dyn_cast<PHINode>(*(BO->use_begin())); 00242 if (PotentialIndvar && PN == PotentialIndvar) { 00243 PN->dropAllReferences(); 00244 DeadInsts.insert(BO); 00245 DeadInsts.insert(PN); 00246 DeleteTriviallyDeadInstructions(DeadInsts); 00247 } 00248 } 00249 } 00250 } 00251 }