1 //===- InductionVariable.cpp - Induction variable classification ----------===//
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 // This file implements identification and classification of induction
11 // variables. Induction variables must contain a PHI node that exists in a
12 // loop header. Because of this, they are identified an managed by this PHI
15 // Induction variables are classified into a type. Knowing that an induction
16 // variable is of a specific type can constrain the values of the start and
17 // step. For example, a SimpleLinear induction variable must have a start and
18 // step values that are constants.
20 // Induction variables can be created with or without loop information. If no
21 // loop information is available, induction variables cannot be recognized to be
22 // more than SimpleLinear variables.
24 //===----------------------------------------------------------------------===//
26 #include "llvm/Analysis/InductionVariable.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/Analysis/Expressions.h"
29 #include "llvm/BasicBlock.h"
30 #include "llvm/Instructions.h"
31 #include "llvm/Type.h"
32 #include "llvm/Constants.h"
33 #include "llvm/Support/CFG.h"
34 #include "llvm/Assembly/Writer.h"
35 #include "Support/Debug.h"
38 static bool isLoopInvariant(const Value *V, const Loop *L) {
39 if (const Instruction *I = dyn_cast<Instruction>(V))
40 return !L->contains(I->getParent());
41 // non-instructions all dominate instructions/blocks
45 enum InductionVariable::iType
46 InductionVariable::Classify(const Value *Start, const Value *Step,
48 // Check for canonical and simple linear expressions now...
49 if (const ConstantInt *CStart = dyn_cast<ConstantInt>(Start))
50 if (const ConstantInt *CStep = dyn_cast<ConstantInt>(Step)) {
51 if (CStart->isNullValue() && CStep->equalsInt(1))
57 // Without loop information, we cannot do any better, so bail now...
58 if (L == 0) return Unknown;
60 if (isLoopInvariant(Start, L) && isLoopInvariant(Step, L))
65 // Create an induction variable for the specified value. If it is a PHI, and
66 // if it's recognizable, classify it and fill in instance variables.
68 InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo): End(0) {
69 InductionType = Unknown; // Assume the worst
72 // If the PHI node has more than two predecessors, we don't know how to
75 if (Phi->getNumIncomingValues() != 2) return;
77 // FIXME: Handle FP induction variables.
78 if (Phi->getType() == Type::FloatTy || Phi->getType() == Type::DoubleTy)
81 // If we have loop information, make sure that this PHI node is in the header
84 const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
85 if (L && L->getHeader() != Phi->getParent())
88 Value *V1 = Phi->getIncomingValue(0);
89 Value *V2 = Phi->getIncomingValue(1);
91 if (L == 0) { // No loop information? Base everything on expression analysis
92 ExprType E1 = ClassifyExpr(V1);
93 ExprType E2 = ClassifyExpr(V2);
95 if (E1.ExprTy > E2.ExprTy) // Make E1 be the simpler expression
98 // E1 must be a constant incoming value, and E2 must be a linear expression
99 // with respect to the PHI node.
101 if (E1.ExprTy > ExprType::Constant || E2.ExprTy != ExprType::Linear ||
105 // Okay, we have found an induction variable. Save the start and step values
106 const Type *ETy = Phi->getType();
107 if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
109 Start = (Value*)(E1.Offset ? E1.Offset : ConstantInt::get(ETy, 0));
110 Step = (Value*)(E2.Offset ? E2.Offset : ConstantInt::get(ETy, 0));
112 // Okay, at this point, we know that we have loop information...
114 // Make sure that V1 is the incoming value, and V2 is from the backedge of
116 if (L->contains(Phi->getIncomingBlock(0))) // Wrong order. Swap now.
119 Start = V1; // We know that Start has to be loop invariant...
122 if (V2 == Phi) { // referencing the PHI directly? Must have zero step
123 Step = Constant::getNullValue(Phi->getType());
124 } else if (BinaryOperator *I = dyn_cast<BinaryOperator>(V2)) {
125 if (I->getOpcode() == Instruction::Add) {
126 if (I->getOperand(0) == Phi)
127 Step = I->getOperand(1);
128 else if (I->getOperand(1) == Phi)
129 Step = I->getOperand(0);
130 } else if (I->getOpcode() == Instruction::Sub &&
131 I->getOperand(0) == Phi) {
132 // If the incoming value is a constant, just form a constant negative
133 // step. Otherwise, negate the step outside of the loop and use it.
134 Value *V = I->getOperand(1);
135 Constant *Zero = Constant::getNullValue(V->getType());
136 if (Constant *CV = dyn_cast<Constant>(V))
137 Step = ConstantExpr::get(Instruction::Sub, Zero, CV);
138 else if (Instruction *I = dyn_cast<Instruction>(V)) {
139 BasicBlock::iterator InsertPt = I;
140 for (++InsertPt; isa<PHINode>(InsertPt); ++InsertPt)
142 Step = BinaryOperator::create(Instruction::Sub, Zero, V,
143 V->getName()+".neg", InsertPt);
146 // Must be loop invariant
147 Step = BinaryOperator::create(Instruction::Sub, Zero, V,
149 Phi->getParent()->getParent()->begin()->begin());
152 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V2)) {
153 if (GEP->getNumOperands() == 2 &&
154 GEP->getOperand(0) == Phi)
155 Step = GEP->getOperand(1);
158 if (Step == 0) { // Unrecognized step value...
159 ExprType StepE = ClassifyExpr(V2);
160 if (StepE.ExprTy != ExprType::Linear ||
161 StepE.Var != Phi) return;
163 const Type *ETy = Phi->getType();
164 if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
165 Step = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy, 0));
166 } else { // We were able to get a step value, simplify with expr analysis
167 ExprType StepE = ClassifyExpr(Step);
168 if (StepE.ExprTy == ExprType::Linear && StepE.Offset == 0) {
169 // No offset from variable? Grab the variable
171 } else if (StepE.ExprTy == ExprType::Constant) {
173 Step = (Value*)StepE.Offset;
175 Step = Constant::getNullValue(Step->getType());
176 const Type *ETy = Phi->getType();
177 if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
178 Step = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy,0));
183 // Classify the induction variable type now...
184 InductionType = InductionVariable::Classify(Start, Step, L);
188 Value *InductionVariable::getExecutionCount(LoopInfo *LoopInfo) {
189 if (InductionType != Canonical) return 0;
191 DEBUG(std::cerr << "entering getExecutionCount\n");
193 // Don't recompute if already available
195 DEBUG(std::cerr << "returning cached End value.\n");
199 const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
201 DEBUG(std::cerr << "null loop. oops\n");
205 // >1 backedge => cannot predict number of iterations
206 if (Phi->getNumIncomingValues() != 2) {
207 DEBUG(std::cerr << ">2 incoming values. oops\n");
211 // Find final node: predecessor of the loop header that's also an exit
212 BasicBlock *terminator = 0;
213 for (pred_iterator PI = pred_begin(L->getHeader()),
214 PE = pred_end(L->getHeader()); PI != PE; ++PI)
215 if (L->isLoopExit(*PI)) {
220 // Break in the loop => cannot predict number of iterations
221 // break: any block which is an exit node whose successor is not in loop,
222 // and this block is not marked as the terminator
224 const std::vector<BasicBlock*> &blocks = L->getBlocks();
225 for (std::vector<BasicBlock*>::const_iterator I = blocks.begin(),
226 e = blocks.end(); I != e; ++I)
227 if (L->isLoopExit(*I) && *I != terminator)
228 for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI)
229 if (!L->contains(*SI)) {
230 DEBUG(std::cerr << "break found in loop");
234 BranchInst *B = dyn_cast<BranchInst>(terminator->getTerminator());
236 DEBUG(std::cerr << "Terminator is not a cond branch!");
239 SetCondInst *SCI = dyn_cast<SetCondInst>(B->getCondition());
241 DEBUG(std::cerr << "Not a cond branch on setcc!\n");
245 DEBUG(std::cerr << "sci:" << *SCI);
246 Value *condVal0 = SCI->getOperand(0);
247 Value *condVal1 = SCI->getOperand(1);
249 // The induction variable is the one coming from the backedge
250 Value *indVar = Phi->getIncomingValue(L->contains(Phi->getIncomingBlock(1)));
253 // Check to see if indVar is one of the parameters in SCI and if the other is
254 // loop-invariant, it is the UB
255 if (indVar == condVal0) {
256 if (isLoopInvariant(condVal1, L))
259 DEBUG(std::cerr << "not loop invariant 1\n");
262 } else if (indVar == condVal1) {
263 if (isLoopInvariant(condVal0, L))
266 DEBUG(std::cerr << "not loop invariant 0\n");
270 DEBUG(std::cerr << "Loop condition doesn't directly uses indvar\n");
274 switch (SCI->getOpcode()) {
275 case Instruction::SetLT:
276 case Instruction::SetNE: return End; // already done
277 case Instruction::SetLE:
278 // if compared to a constant int N, then predict N+1 iterations
279 if (ConstantSInt *ubSigned = dyn_cast<ConstantSInt>(End)) {
280 DEBUG(std::cerr << "signed int constant\n");
281 return ConstantSInt::get(ubSigned->getType(), ubSigned->getValue()+1);
282 } else if (ConstantUInt *ubUnsigned = dyn_cast<ConstantUInt>(End)) {
283 DEBUG(std::cerr << "unsigned int constant\n");
284 return ConstantUInt::get(ubUnsigned->getType(),
285 ubUnsigned->getValue()+1);
287 DEBUG(std::cerr << "symbolic bound\n");
288 // new expression N+1, insert right before the SCI. FIXME: If End is loop
289 // invariant, then so is this expression. We should insert it in the loop
290 // preheader if it exists.
291 return BinaryOperator::create(Instruction::Add, End,
292 ConstantInt::get(End->getType(), 1),
297 return 0; // cannot predict
302 void InductionVariable::print(std::ostream &o) const {
303 switch (InductionType) {
304 case InductionVariable::Canonical: o << "Canonical "; break;
305 case InductionVariable::SimpleLinear: o << "SimpleLinear "; break;
306 case InductionVariable::Linear: o << "Linear "; break;
307 case InductionVariable::Unknown: o << "Unrecognized "; break;
309 o << "Induction Variable: ";
311 WriteAsOperand(o, Phi);
316 if (InductionType == InductionVariable::Unknown) return;
318 o << " Start = "; WriteAsOperand(o, Start);
319 o << " Step = " ; WriteAsOperand(o, Step);
321 o << " End = " ; WriteAsOperand(o, End);