1 //===- LoopStrengthReduce.cpp - Strength Reduce GEPs in Loops -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Nate Begeman and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass performs a strength reduction on array references inside loops that
11 // have as one or more of their components the loop induction variable. This is
12 // accomplished by creating a new Value to hold the initial value of the array
13 // access for the first iteration, and then creating a new GEP instruction in
14 // the loop to increment the value by the appropriate amount.
16 // There are currently several deficiencies in the implementation, marked with
19 //===----------------------------------------------------------------------===//
21 #include "llvm/Transforms/Scalar.h"
22 #include "llvm/Constants.h"
23 #include "llvm/Instructions.h"
24 #include "llvm/Type.h"
25 #include "llvm/DerivedTypes.h"
26 #include "llvm/Analysis/Dominators.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/Support/CFG.h"
29 #include "llvm/Transforms/Utils/Local.h"
30 #include "llvm/Target/TargetData.h"
31 #include "llvm/ADT/Statistic.h"
36 Statistic<> NumReduced ("loop-reduce", "Number of GEPs strength reduced");
40 GEPCache() : CachedPHINode(0), Map() {}
42 GEPCache *get(Value *v) {
43 std::map<Value *, GEPCache>::iterator I = Map.find(v);
45 I = Map.insert(std::pair<Value *, GEPCache>(v, GEPCache())).first;
49 PHINode *CachedPHINode;
50 std::map<Value *, GEPCache> Map;
53 class LoopStrengthReduce : public FunctionPass {
57 unsigned MaxTargetAMSize;
59 LoopStrengthReduce(unsigned MTAMS = 1)
60 : MaxTargetAMSize(MTAMS) {
63 virtual bool runOnFunction(Function &) {
64 LI = &getAnalysis<LoopInfo>();
65 DS = &getAnalysis<DominatorSet>();
68 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
73 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
75 AU.addRequiredID(LoopSimplifyID);
76 AU.addRequired<LoopInfo>();
77 AU.addRequired<DominatorSet>();
78 AU.addRequired<TargetData>();
81 void runOnLoop(Loop *L);
82 void strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
84 Instruction *InsertBefore,
85 std::set<Instruction*> &DeadInsts);
86 void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
88 RegisterOpt<LoopStrengthReduce> X("loop-reduce",
89 "Strength Reduce GEP Uses of Ind. Vars");
92 FunctionPass *llvm::createLoopStrengthReducePass(unsigned MaxTargetAMSize) {
93 return new LoopStrengthReduce(MaxTargetAMSize);
96 /// DeleteTriviallyDeadInstructions - If any of the instructions is the
97 /// specified set are trivially dead, delete them and see if this makes any of
98 /// their operands subsequently dead.
99 void LoopStrengthReduce::
100 DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
101 while (!Insts.empty()) {
102 Instruction *I = *Insts.begin();
103 Insts.erase(Insts.begin());
104 if (isInstructionTriviallyDead(I)) {
105 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
106 if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
108 I->getParent()->getInstList().erase(I);
114 void LoopStrengthReduce::strengthReduceGEP(GetElementPtrInst *GEPI, Loop *L,
116 Instruction *InsertBefore,
117 std::set<Instruction*> &DeadInsts) {
118 // We will strength reduce the GEP by splitting it into two parts. The first
119 // is a GEP to hold the initial value of the non-strength-reduced GEP upon
120 // entering the loop, which we will insert at the end of the loop preheader.
121 // The second is a GEP to hold the incremented value of the initial GEP.
122 // The LoopIndVarSimplify pass guarantees that loop counts start at zero, so
123 // we will replace the indvar with a constant zero value to create the first
126 // We currently only handle GEP instructions that consist of zero or more
127 // constants or loop invariable expressions prior to an instance of the
128 // canonical induction variable.
130 std::vector<Value *> pre_op_vector;
131 std::vector<Value *> inc_op_vector;
132 const Type *ty = GEPI->getOperand(0)->getType();
133 Value *CanonicalIndVar = L->getCanonicalInductionVariable();
134 BasicBlock *Header = L->getHeader();
135 BasicBlock *Preheader = L->getLoopPreheader();
136 bool AllConstantOperands = true;
137 Cache = Cache->get(GEPI->getOperand(0));
139 for (unsigned op = 1, e = GEPI->getNumOperands(); op != e; ++op) {
140 Value *operand = GEPI->getOperand(op);
141 if (ty->getTypeID() == Type::StructTyID) {
142 assert(isa<ConstantUInt>(operand));
143 ConstantUInt *c = dyn_cast<ConstantUInt>(operand);
144 ty = ty->getContainedType(unsigned(c->getValue()));
146 ty = ty->getContainedType(0);
149 if (operand == CanonicalIndVar) {
150 // FIXME: use getCanonicalInductionVariableIncrement to choose between
151 // one and neg one maybe? We need to support int *foo = GEP base, -1
152 const Type *Ty = CanonicalIndVar->getType();
153 pre_op_vector.push_back(Constant::getNullValue(Ty));
154 inc_op_vector.push_back(ConstantInt::get(Ty, 1));
157 } else if (isa<Argument>(operand)) {
158 pre_op_vector.push_back(operand);
159 AllConstantOperands = false;
160 } else if (isa<Constant>(operand)) {
161 pre_op_vector.push_back(operand);
162 } else if (Instruction *inst = dyn_cast<Instruction>(operand)) {
163 if (!DS->dominates(inst, Preheader->getTerminator()))
165 pre_op_vector.push_back(operand);
166 AllConstantOperands = false;
168 return; // Cannot handle this.
170 Cache = Cache->get(operand);
172 assert(indvar > 0 && "Indvar used by GEP not found in operand list");
174 // Ensure the pointer base is loop invariant. While strength reduction
175 // makes sense even if the pointer changed on every iteration, there is no
176 // realistic way of handling it unless GEPs were completely decomposed into
177 // their constituent operations so we have explicit multiplications to work
179 if (Instruction *GepPtrOp = dyn_cast<Instruction>(GEPI->getOperand(0)))
180 if (!DS->dominates(GepPtrOp, Preheader->getTerminator()))
183 // Don't reduce multiplies that the target can handle via addressing modes.
184 uint64_t sz = getAnalysis<TargetData>().getTypeSize(ty);
185 if (sz && (sz & (sz-1)) == 0) // Power of two?
186 if (sz <= (1ULL << (MaxTargetAMSize-1)))
189 // If all operands of the GEP we are going to insert into the preheader
190 // are constants, generate a GEP ConstantExpr instead.
192 // If there is only one operand after the initial non-constant one, we know
193 // that it was the induction variable, and has been replaced by a constant
194 // null value. In this case, replace the GEP with a use of pointer directly.
196 if (Cache->CachedPHINode == 0) {
198 if (AllConstantOperands && isa<Constant>(GEPI->getOperand(0))) {
199 Constant *C = dyn_cast<Constant>(GEPI->getOperand(0));
200 PreGEP = ConstantExpr::getGetElementPtr(C, pre_op_vector);
201 } else if (pre_op_vector.size() == 1) {
202 PreGEP = GEPI->getOperand(0);
204 PreGEP = new GetElementPtrInst(GEPI->getOperand(0),
205 pre_op_vector, GEPI->getName()+".pre",
206 Preheader->getTerminator());
209 // The next step of the strength reduction is to create a PHI that will
210 // choose between the initial GEP we created and inserted into the
211 // preheader, and the incremented GEP that we will create below and insert
212 // into the loop body.
213 NewPHI = new PHINode(PreGEP->getType(),
214 GEPI->getName()+".str", InsertBefore);
215 NewPHI->addIncoming(PreGEP, Preheader);
217 // Now, create the GEP instruction to increment by one the value selected
218 // by the PHI instruction we just created above, and add it as the second
219 // incoming Value/BasicBlock pair to the PHINode. It is inserted before
220 // the increment of the canonical induction variable.
221 Instruction *IncrInst =
222 const_cast<Instruction*>(L->getCanonicalInductionVariableIncrement());
223 GetElementPtrInst *StrGEP = new GetElementPtrInst(NewPHI, inc_op_vector,
224 GEPI->getName()+".inc",
226 pred_iterator PI = pred_begin(Header);
227 if (*PI == Preheader)
229 NewPHI->addIncoming(StrGEP, *PI);
230 Cache->CachedPHINode = NewPHI;
232 // Reuse previously created pointer, as it is identical to the one we were
234 NewPHI = Cache->CachedPHINode;
237 if (GEPI->getNumOperands() - 1 == indvar) {
238 // If there were no operands following the induction variable, replace all
239 // uses of the old GEP instruction with the new PHI.
240 GEPI->replaceAllUsesWith(NewPHI);
242 // Create a new GEP instruction using the new PHI as the base. The
243 // operands of the original GEP past the induction variable become
244 // operands of this new GEP.
245 std::vector<Value *> op_vector;
246 const Type *Ty = CanonicalIndVar->getType();
247 op_vector.push_back(Constant::getNullValue(Ty));
248 for (unsigned op = indvar + 1; op < GEPI->getNumOperands(); op++)
249 op_vector.push_back(GEPI->getOperand(op));
250 GetElementPtrInst *newGEP = new GetElementPtrInst(NewPHI, op_vector,
251 GEPI->getName() + ".lsr",
253 GEPI->replaceAllUsesWith(newGEP);
256 // The old GEP is now dead.
257 DeadInsts.insert(GEPI);
261 void LoopStrengthReduce::runOnLoop(Loop *L) {
262 // First step, transform all loops nesting inside of this loop.
263 for (LoopInfo::iterator I = L->begin(), E = L->end(); I != E; ++I)
266 // Next, get the first PHINode since it is guaranteed to be the canonical
267 // induction variable for the loop by the preceding IndVarSimplify pass.
268 PHINode *PN = L->getCanonicalInductionVariable();
272 // FIXME: Need to use SCEV to detect GEP uses of the indvar, since indvars
273 // pass creates code like this, which we can't currently detect:
274 // %tmp.1 = sub uint 2000, %indvar
275 // %tmp.8 = getelementptr int* %y, uint %tmp.1
277 // Strength reduce all GEPs in the Loop. Insert secondary PHI nodes for the
278 // strength reduced pointers we'll be creating after the canonical induction
280 std::set<Instruction*> DeadInsts;
282 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
284 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI))
285 strengthReduceGEP(GEPI, L, &Cache, PN->getNext(), DeadInsts);
287 // Clean up after ourselves
288 if (!DeadInsts.empty()) {
289 DeleteTriviallyDeadInstructions(DeadInsts);
291 // At this point, we know that we have killed one or more GEP instructions.
292 // It is worth checking to see if the cann indvar is also dead, so that we
293 // can remove it as well. The requirements for the cann indvar to be
294 // considered dead are:
295 // 1. the cann indvar has one use
296 // 2. the use is an add instruction
297 // 3. the add has one use
298 // 4. the add is used by the cann indvar
299 // If all four cases above are true, then we can remove both the add and
301 // FIXME: this needs to eliminate an induction variable even if it's being
302 // compared against some value to decide loop termination.
303 if (PN->hasOneUse()) {
304 BinaryOperator *BO = dyn_cast<BinaryOperator>(*(PN->use_begin()));
305 if (BO && BO->getOpcode() == Instruction::Add)
306 if (BO->hasOneUse()) {
307 if (PN == dyn_cast<PHINode>(*(BO->use_begin()))) {
308 DeadInsts.insert(BO);
309 // Break the cycle, then delete the PHI.
310 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
311 PN->eraseFromParent();
312 DeleteTriviallyDeadInstructions(DeadInsts);