1 //===- llvm/Analysis/InductionVariable.h - Induction variable ----*- C++ -*--=//
3 // This interface is used to identify and classify induction variables that
4 // exist in the program. Induction variables must contain a PHI node that
5 // exists in a loop header. Because of this, they are identified an managed by
8 // Induction variables are classified into a type. Knowing that an induction
9 // variable is of a specific type can constrain the values of the start and
10 // step. For example, a SimpleLinear induction variable must have a start and
11 // step values that are constants.
13 // Induction variables can be created with or without loop information. If no
14 // loop information is available, induction variables cannot be recognized to be
15 // more than SimpleLinear variables.
17 //===----------------------------------------------------------------------===//
19 #include "llvm/Analysis/InductionVariable.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/Expressions.h"
22 #include "llvm/BasicBlock.h"
23 #include "llvm/iPHINode.h"
24 #include "llvm/iOperators.h"
25 #include "llvm/iTerminators.h"
26 #include "llvm/Type.h"
27 #include "llvm/Constants.h"
28 #include "llvm/Support/CFG.h"
29 #include "llvm/Assembly/Writer.h"
30 #include "Support/Statistic.h"
32 static bool isLoopInvariant(const Value *V, const Loop *L) {
33 if (isa<Constant>(V) || isa<Argument>(V) || isa<GlobalValue>(V))
36 const Instruction *I = cast<Instruction>(V);
37 const BasicBlock *BB = I->getParent();
39 return !L->contains(BB);
42 enum InductionVariable::iType
43 InductionVariable::Classify(const Value *Start, const Value *Step,
45 // Check for cannonical and simple linear expressions now...
46 if (const ConstantInt *CStart = dyn_cast<ConstantInt>(Start))
47 if (const ConstantInt *CStep = dyn_cast<ConstantInt>(Step)) {
48 if (CStart->equalsInt(0) && CStep->equalsInt(1))
54 // Without loop information, we cannot do any better, so bail now...
55 if (L == 0) return Unknown;
57 if (isLoopInvariant(Start, L) && isLoopInvariant(Step, L))
62 // Create an induction variable for the specified value. If it is a PHI, and
63 // if it's recognizable, classify it and fill in instance variables.
65 InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo): End(0) {
66 InductionType = Unknown; // Assume the worst
69 // If the PHI node has more than two predecessors, we don't know how to
72 if (Phi->getNumIncomingValues() != 2) return;
74 // FIXME: Handle FP induction variables.
75 if (Phi->getType() == Type::FloatTy || Phi->getType() == Type::DoubleTy)
78 // If we have loop information, make sure that this PHI node is in the header
81 const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
82 if (L && L->getHeader() != Phi->getParent())
85 Value *V1 = Phi->getIncomingValue(0);
86 Value *V2 = Phi->getIncomingValue(1);
88 if (L == 0) { // No loop information? Base everything on expression analysis
89 ExprType E1 = ClassifyExpression(V1);
90 ExprType E2 = ClassifyExpression(V2);
92 if (E1.ExprTy > E2.ExprTy) // Make E1 be the simpler expression
95 // E1 must be a constant incoming value, and E2 must be a linear expression
96 // with respect to the PHI node.
98 if (E1.ExprTy > ExprType::Constant || E2.ExprTy != ExprType::Linear ||
102 // Okay, we have found an induction variable. Save the start and step values
103 const Type *ETy = Phi->getType();
104 if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
106 Start = (Value*)(E1.Offset ? E1.Offset : ConstantInt::get(ETy, 0));
107 Step = (Value*)(E2.Offset ? E2.Offset : ConstantInt::get(ETy, 0));
109 // Okay, at this point, we know that we have loop information...
111 // Make sure that V1 is the incoming value, and V2 is from the backedge of
113 if (L->contains(Phi->getIncomingBlock(0))) // Wrong order. Swap now.
116 Start = V1; // We know that Start has to be loop invariant...
119 if (V2 == Phi) { // referencing the PHI directly? Must have zero step
120 Step = Constant::getNullValue(Phi->getType());
121 } else if (BinaryOperator *I = dyn_cast<BinaryOperator>(V2)) {
122 // TODO: This could be much better...
123 if (I->getOpcode() == Instruction::Add) {
124 if (I->getOperand(0) == Phi)
125 Step = I->getOperand(1);
126 else if (I->getOperand(1) == Phi)
127 Step = I->getOperand(0);
131 if (Step == 0) { // Unrecognized step value...
132 ExprType StepE = ClassifyExpression(V2);
133 if (StepE.ExprTy != ExprType::Linear ||
134 StepE.Var != Phi) return;
136 const Type *ETy = Phi->getType();
137 if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
138 Step = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy, 0));
139 } else { // We were able to get a step value, simplify with expr analysis
140 ExprType StepE = ClassifyExpression(Step);
141 if (StepE.ExprTy == ExprType::Linear && StepE.Offset == 0) {
142 // No offset from variable? Grab the variable
144 } else if (StepE.ExprTy == ExprType::Constant) {
146 Step = (Value*)StepE.Offset;
148 Step = Constant::getNullValue(Step->getType());
149 const Type *ETy = Phi->getType();
150 if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
151 Step = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy,0));
156 // Classify the induction variable type now...
157 InductionType = InductionVariable::Classify(Start, Step, L);
161 Value* InductionVariable::getExecutionCount(LoopInfo *LoopInfo) {
162 DEBUG(std::cerr << "entering getExecutionCount\n");
164 // Don't recompute if already available
166 DEBUG(std::cerr << "returning cached End value.\n");
170 const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
172 DEBUG(std::cerr << "null loop. oops\n");
176 // >1 backedge => cannot predict number of iterations
177 if (Phi->getNumIncomingValues() != 2) {
178 DEBUG(std::cerr << ">2 incoming values. oops\n");
182 // Find final node: predecesor of the loop header that's also an exit
183 BasicBlock *terminator = 0;
184 BasicBlock *header = L->getHeader();
185 for (pred_iterator PI = pred_begin(header), PE = pred_end(header);
187 if (L->isLoopExit(*PI)) {
193 // Break in the loop => cannot predict number of iterations
194 // break: any block which is an exit node whose successor is not in loop,
195 // and this block is not marked as the terminator
197 const std::vector<BasicBlock*> &blocks = L->getBlocks();
198 for (std::vector<BasicBlock*>::const_iterator i = blocks.begin(), e = blocks.end();
200 if (L->isLoopExit(*i) && (*i != terminator)) {
201 for (succ_iterator SI = succ_begin(*i), SE = succ_end(*i); SI != SE; ++SI) {
202 if (! L->contains(*SI)) {
203 DEBUG(std::cerr << "break found in loop");
210 BranchInst *B = dyn_cast<BranchInst>(terminator->getTerminator());
212 // this really should not happen
213 DEBUG(std::cerr << "no terminator instruction!");
216 SetCondInst *SCI = dyn_cast<SetCondInst>(B->getCondition());
218 if (SCI && InductionType == Cannonical) {
219 DEBUG(std::cerr << "sci:" << *SCI);
220 Value *condVal0 = SCI->getOperand(0);
221 Value *condVal1 = SCI->getOperand(1);
224 // the induction variable is the one coming from the backedge
225 if (L->contains(Phi->getIncomingBlock(0))) {
226 indVar = Phi->getIncomingValue(0);
228 indVar = Phi->getIncomingValue(1);
231 // check to see if indVar is one of the parameters in SCI
232 // and if the other is loop-invariant, it is the UB
233 if (indVar == condVal0) {
234 if (isLoopInvariant(condVal1, L)) {
237 DEBUG(std::cerr << "not loop invariant 1\n");
239 } else if (indVar == condVal1) {
240 if (isLoopInvariant(condVal0, L)) {
243 DEBUG(std::cerr << "not loop invariant 0\n");
248 switch (SCI->getOpcode()) {
249 case Instruction::SetLT:
250 case Instruction::SetNE: break; // already done
251 case Instruction::SetLE: {
252 // if compared to a constant int N, then predict N+1 iterations
253 if (ConstantSInt *ubSigned = dyn_cast<ConstantSInt>(End)) {
254 End = ConstantSInt::get(ubSigned->getType(), ubSigned->getValue()+1);
255 DEBUG(std::cerr << "signed int constant\n");
256 } else if (ConstantUInt *ubUnsigned = dyn_cast<ConstantUInt>(End)) {
257 End = ConstantUInt::get(ubUnsigned->getType(), ubUnsigned->getValue()+1);
258 DEBUG(std::cerr << "unsigned int constant\n");
260 DEBUG(std::cerr << "symbolic bound\n");
262 // new expression N+1
263 End = BinaryOperator::create(Instruction::Add, End,
264 ConstantUInt::get(ubUnsigned->getType(), 1));
268 default: End = NULL; // cannot predict
273 DEBUG(std::cerr << "SCI null or non-cannonical ind var\n");
279 void InductionVariable::print(std::ostream &o) const {
280 switch (InductionType) {
281 case InductionVariable::Cannonical: o << "Cannonical "; break;
282 case InductionVariable::SimpleLinear: o << "SimpleLinear "; break;
283 case InductionVariable::Linear: o << "Linear "; break;
284 case InductionVariable::Unknown: o << "Unrecognized "; break;
286 o << "Induction Variable: ";
288 WriteAsOperand(o, Phi);
293 if (InductionType == InductionVariable::Unknown) return;
295 o << " Start = "; WriteAsOperand(o, Start);
296 o << " Step = " ; WriteAsOperand(o, Step);
298 o << " End = " ; WriteAsOperand(o, End);