1 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Guarantees that all loops with identifiable, linear, induction variables will
11 // be transformed to have a single, canonical, induction variable. After this
12 // pass runs, it guarantees the the first PHI node of the header block in the
13 // loop is the canonical induction variable if there is one.
15 //===----------------------------------------------------------------------===//
17 #define DEBUG_TYPE "indvar"
18 #include "llvm/Transforms/Scalar.h"
19 #include "llvm/Constants.h"
20 #include "llvm/Type.h"
21 #include "llvm/Instructions.h"
22 #include "llvm/Analysis/InductionVariable.h"
23 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/Support/CFG.h"
25 #include "llvm/Target/TargetData.h"
26 #include "llvm/Transforms/Utils/Local.h"
27 #include "Support/Debug.h"
28 #include "Support/Statistic.h"
32 Statistic<> NumRemoved ("indvars", "Number of aux indvars removed");
33 Statistic<> NumInserted("indvars", "Number of canonical indvars added");
35 class IndVarSimplify : public FunctionPass {
40 virtual bool runOnFunction(Function &) {
41 Loops = &getAnalysis<LoopInfo>();
42 TD = &getAnalysis<TargetData>();
45 // Induction Variables live in the header nodes of loops
46 for (LoopInfo::iterator I = Loops->begin(), E = Loops->end(); I != E; ++I)
51 unsigned getTypeSize(const Type *Ty) {
52 if (unsigned Size = Ty->getPrimitiveSize())
54 return TD->getTypeSize(Ty); // Must be a pointer
57 Value *ComputeAuxIndVarValue(InductionVariable &IV, Value *CIV);
58 void ReplaceIndVar(InductionVariable &IV, Value *Counter);
60 void runOnLoop(Loop *L);
62 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
63 AU.addRequired<TargetData>(); // Need pointer size
64 AU.addRequired<LoopInfo>();
65 AU.addRequiredID(LoopSimplifyID);
66 AU.addPreservedID(LoopSimplifyID);
70 RegisterOpt<IndVarSimplify> X("indvars", "Canonicalize Induction Variables");
73 Pass *llvm::createIndVarSimplifyPass() {
74 return new IndVarSimplify();
78 void IndVarSimplify::runOnLoop(Loop *Loop) {
79 // Transform all subloops before this loop...
80 for (LoopInfo::iterator I = Loop->begin(), E = Loop->end(); I != E; ++I)
83 // Get the header node for this loop. All of the phi nodes that could be
84 // induction variables must live in this basic block.
86 BasicBlock *Header = Loop->getHeader();
88 // Loop over all of the PHI nodes in the basic block, calculating the
89 // induction variables that they represent... stuffing the induction variable
90 // info into a vector...
92 std::vector<InductionVariable> IndVars; // Induction variables for block
93 BasicBlock::iterator AfterPHIIt = Header->begin();
94 for (; PHINode *PN = dyn_cast<PHINode>(AfterPHIIt); ++AfterPHIIt)
95 IndVars.push_back(InductionVariable(PN, Loops));
96 // AfterPHIIt now points to first non-phi instruction...
98 // If there are no phi nodes in this basic block, there can't be indvars...
99 if (IndVars.empty()) return;
101 // Loop over the induction variables, looking for a canonical induction
102 // variable, and checking to make sure they are not all unknown induction
103 // variables. Keep track of the largest integer size of the induction
106 InductionVariable *Canonical = 0;
107 unsigned MaxSize = 0;
109 for (unsigned i = 0; i != IndVars.size(); ++i) {
110 InductionVariable &IV = IndVars[i];
112 if (IV.InductionType != InductionVariable::Unknown) {
113 unsigned IVSize = getTypeSize(IV.Phi->getType());
115 if (IV.InductionType == InductionVariable::Canonical &&
116 !isa<PointerType>(IV.Phi->getType()) && IVSize >= MaxSize)
119 if (IVSize > MaxSize) MaxSize = IVSize;
121 // If this variable is larger than the currently identified canonical
122 // indvar, the canonical indvar is not usable.
123 if (Canonical && IVSize > getTypeSize(Canonical->Phi->getType()))
128 // No induction variables, bail early... don't add a canonical indvar
129 if (MaxSize == 0) return;
132 // Figure out what the exit condition of the loop is. We can currently only
133 // handle loops with a single exit. If we cannot figure out what the
134 // termination condition is, we leave this variable set to null.
136 SetCondInst *TermCond = 0;
137 if (Loop->getExitBlocks().size() == 1) {
138 // Get ExitingBlock - the basic block in the loop which contains the branch
140 BasicBlock *Exit = Loop->getExitBlocks()[0];
141 pred_iterator PI = pred_begin(Exit);
142 assert(PI != pred_end(Exit) && "Should have one predecessor in loop!");
143 BasicBlock *ExitingBlock = *PI;
144 assert(++PI == pred_end(Exit) && "Exit block should have one pred!");
145 assert(Loop->isLoopExit(ExitingBlock) && "Exiting block is not loop exit!");
147 // Since the block is in the loop, yet branches out of it, we know that the
148 // block must end with multiple destination terminator. Which means it is
149 // either a conditional branch, a switch instruction, or an invoke.
150 if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator())) {
151 assert(BI->isConditional() && "Unconditional branch has multiple succs?");
152 TermCond = dyn_cast<SetCondInst>(BI->getCondition());
154 // NOTE: if people actually exit loops with switch instructions, we could
155 // handle them, but I don't think this is important enough to spend time
157 assert(isa<SwitchInst>(ExitingBlock->getTerminator()) ||
158 isa<InvokeInst>(ExitingBlock->getTerminator()) &&
159 "Unknown multi-successor terminator!");
164 DEBUG(std::cerr << "INDVAR: Found termination condition: " << *TermCond);
166 // Okay, we want to convert other induction variables to use a canonical
167 // indvar. If we don't have one, add one now...
169 // Create the PHI node for the new induction variable, and insert the phi
170 // node at the start of the PHI nodes...
173 default: assert(0 && "Unknown integer type size!");
174 case 1: IVType = Type::UByteTy; break;
175 case 2: IVType = Type::UShortTy; break;
176 case 4: IVType = Type::UIntTy; break;
177 case 8: IVType = Type::ULongTy; break;
180 PHINode *PN = new PHINode(IVType, "cann-indvar", Header->begin());
182 // Create the increment instruction to add one to the counter...
183 Instruction *Add = BinaryOperator::create(Instruction::Add, PN,
184 ConstantUInt::get(IVType, 1),
185 "next-indvar", AfterPHIIt);
187 // Figure out which block is incoming and which is the backedge for the loop
188 BasicBlock *Incoming, *BackEdgeBlock;
189 pred_iterator PI = pred_begin(Header);
190 assert(PI != pred_end(Header) && "Loop headers should have 2 preds!");
191 if (Loop->contains(*PI)) { // First pred is back edge...
192 BackEdgeBlock = *PI++;
196 BackEdgeBlock = *PI++;
198 assert(PI == pred_end(Header) && "Loop headers should have 2 preds!");
200 // Add incoming values for the PHI node...
201 PN->addIncoming(Constant::getNullValue(IVType), Incoming);
202 PN->addIncoming(Add, BackEdgeBlock);
204 // Analyze the new induction variable...
205 IndVars.push_back(InductionVariable(PN, Loops));
206 assert(IndVars.back().InductionType == InductionVariable::Canonical &&
207 "Just inserted canonical indvar that is not canonical!");
208 Canonical = &IndVars.back();
211 DEBUG(std::cerr << "INDVAR: Inserted canonical iv: " << *PN);
213 // If we have a canonical induction variable, make sure that it is the first
214 // one in the basic block.
215 if (&Header->front() != Canonical->Phi)
216 Header->getInstList().splice(Header->begin(), Header->getInstList(),
218 DEBUG(std::cerr << "IndVar: Existing canonical iv used: "
222 DEBUG(std::cerr << "INDVAR: Replacing Induction variables:\n");
224 // Get the current loop iteration count, which is always the value of the
225 // canonical phi node...
227 PHINode *IterCount = Canonical->Phi;
229 // Loop through and replace all of the auxiliary induction variables with
230 // references to the canonical induction variable...
232 for (unsigned i = 0; i != IndVars.size(); ++i) {
233 InductionVariable *IV = &IndVars[i];
235 DEBUG(IV->print(std::cerr));
237 // Don't modify the canonical indvar or unrecognized indvars...
238 if (IV != Canonical && IV->InductionType != InductionVariable::Unknown) {
239 ReplaceIndVar(*IV, IterCount);
246 /// ComputeAuxIndVarValue - Given an auxillary induction variable, compute and
247 /// return a value which will always be equal to the induction variable PHI, but
248 /// is based off of the canonical induction variable CIV.
250 Value *IndVarSimplify::ComputeAuxIndVarValue(InductionVariable &IV, Value *CIV){
251 Instruction *Phi = IV.Phi;
252 const Type *IVTy = Phi->getType();
253 if (isa<PointerType>(IVTy)) // If indexing into a pointer, make the
254 IVTy = TD->getIntPtrType(); // index the appropriate type.
256 BasicBlock::iterator AfterPHIIt = Phi;
257 while (isa<PHINode>(AfterPHIIt)) ++AfterPHIIt;
260 if (Val->getType() != IVTy)
261 Val = new CastInst(Val, IVTy, Val->getName(), AfterPHIIt);
263 if (!isa<ConstantInt>(IV.Step) || // If the step != 1
264 !cast<ConstantInt>(IV.Step)->equalsInt(1)) {
266 // If the types are not compatible, insert a cast now...
267 if (IV.Step->getType() != IVTy)
268 IV.Step = new CastInst(IV.Step, IVTy, IV.Step->getName(), AfterPHIIt);
270 Val = BinaryOperator::create(Instruction::Mul, Val, IV.Step,
271 Phi->getName()+"-scale", AfterPHIIt);
274 // If this is a pointer indvar...
275 if (isa<PointerType>(Phi->getType())) {
276 std::vector<Value*> Idx;
277 // FIXME: this should not be needed when we fix PR82!
278 if (Val->getType() != Type::LongTy)
279 Val = new CastInst(Val, Type::LongTy, Val->getName(), AfterPHIIt);
281 Val = new GetElementPtrInst(IV.Start, Idx,
282 Phi->getName()+"-offset",
285 } else if (!isa<Constant>(IV.Start) || // If Start != 0...
286 !cast<Constant>(IV.Start)->isNullValue()) {
287 // If the types are not compatible, insert a cast now...
288 if (IV.Start->getType() != IVTy)
289 IV.Start = new CastInst(IV.Start, IVTy, IV.Start->getName(),
292 // Insert the instruction after the phi nodes...
293 Val = BinaryOperator::create(Instruction::Add, Val, IV.Start,
294 Phi->getName()+"-offset", AfterPHIIt);
297 // If the PHI node has a different type than val is, insert a cast now...
298 if (Val->getType() != Phi->getType())
299 Val = new CastInst(Val, Phi->getType(), Val->getName(), AfterPHIIt);
301 // Move the PHI name to it's new equivalent value...
302 std::string OldName = Phi->getName();
304 Val->setName(OldName);
309 // ReplaceIndVar - Replace all uses of the specified induction variable with
310 // expressions computed from the specified loop iteration counter variable.
311 // Return true if instructions were deleted.
312 void IndVarSimplify::ReplaceIndVar(InductionVariable &IV, Value *CIV) {
313 Value *IndVarVal = 0;
314 PHINode *Phi = IV.Phi;
316 assert(Phi->getNumOperands() == 4 &&
317 "Only expect induction variables in canonical loops!");
319 // Remember the incoming values used by the PHI node
320 std::vector<Value*> PHIOps;
322 PHIOps.push_back(Phi->getIncomingValue(0));
323 PHIOps.push_back(Phi->getIncomingValue(1));
325 // Delete all of the operands of the PHI node... so that the to-be-deleted PHI
326 // node does not cause any expressions to be computed that would not otherwise
328 Phi->dropAllReferences();
330 // Now that we are rid of unneeded uses of the PHI node, replace any remaining
331 // ones with the appropriate code using the canonical induction variable.
332 while (!Phi->use_empty()) {
333 Instruction *U = cast<Instruction>(Phi->use_back());
335 // TODO: Perform LFTR here if possible
339 // Replace all uses of the old PHI node with the new computed value...
341 IndVarVal = ComputeAuxIndVarValue(IV, CIV);
342 U->replaceUsesOfWith(Phi, IndVarVal);
346 // If the PHI is the last user of any instructions for computing PHI nodes
347 // that are irrelevant now, delete those instructions.
348 while (!PHIOps.empty()) {
349 Instruction *MaybeDead = dyn_cast<Instruction>(PHIOps.back());
352 if (MaybeDead && isInstructionTriviallyDead(MaybeDead) &&
353 (!isa<PHINode>(MaybeDead) ||
354 MaybeDead->getParent() != Phi->getParent())) {
355 PHIOps.insert(PHIOps.end(), MaybeDead->op_begin(),
356 MaybeDead->op_end());
357 MaybeDead->getParent()->getInstList().erase(MaybeDead);
359 // Erase any duplicates entries in the PHIOps list.
360 std::vector<Value*>::iterator It =
361 std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
362 while (It != PHIOps.end()) {
364 It = std::find(PHIOps.begin(), PHIOps.end(), MaybeDead);
369 // Delete the old, now unused, phi node...
370 Phi->getParent()->getInstList().erase(Phi);