-//===- llvm/Analysis/InductionVariable.h - Induction variable ----*- C++ -*--=//
+//===- InductionVariable.cpp - Induction variable classification ----------===//
+//
+// The LLVM Compiler Infrastructure
//
-// This interface is used to identify and classify induction variables that
-// exist in the program. Induction variables must contain a PHI node that
-// exists in a loop header. Because of this, they are identified an managed by
-// this PHI node.
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements identification and classification of induction
+// variables. Induction variables must contain a PHI node that exists in a
+// loop header. Because of this, they are identified an managed by this PHI
+// node.
//
// Induction variables are classified into a type. Knowing that an induction
// variable is of a specific type can constrain the values of the start and
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/Expressions.h"
#include "llvm/BasicBlock.h"
-#include "llvm/iPHINode.h"
-#include "llvm/iOperators.h"
-#include "llvm/iTerminators.h"
+#include "llvm/Instructions.h"
#include "llvm/Type.h"
#include "llvm/Constants.h"
#include "llvm/Support/CFG.h"
#include "llvm/Assembly/Writer.h"
-#include "Support/Statistic.h"
+#include "Support/Debug.h"
+using namespace llvm;
static bool isLoopInvariant(const Value *V, const Loop *L) {
- if (isa<Constant>(V) || isa<Argument>(V) || isa<GlobalValue>(V))
- return true;
-
- const Instruction *I = cast<Instruction>(V);
- const BasicBlock *BB = I->getParent();
-
- return !L->contains(BB);
+ if (const Instruction *I = dyn_cast<Instruction>(V))
+ return !L->contains(I->getParent());
+ // non-instructions all dominate instructions/blocks
+ return true;
}
enum InductionVariable::iType
InductionVariable::Classify(const Value *Start, const Value *Step,
const Loop *L) {
- // Check for cannonical and simple linear expressions now...
+ // Check for canonical and simple linear expressions now...
if (const ConstantInt *CStart = dyn_cast<ConstantInt>(Start))
if (const ConstantInt *CStep = dyn_cast<ConstantInt>(Step)) {
- if (CStart->equalsInt(0) && CStep->equalsInt(1))
- return Cannonical;
+ if (CStart->isNullValue() && CStep->equalsInt(1))
+ return Canonical;
else
return SimpleLinear;
}
Value *V2 = Phi->getIncomingValue(1);
if (L == 0) { // No loop information? Base everything on expression analysis
- ExprType E1 = ClassifyExpression(V1);
- ExprType E2 = ClassifyExpression(V2);
+ ExprType E1 = ClassifyExpr(V1);
+ ExprType E2 = ClassifyExpr(V2);
if (E1.ExprTy > E2.ExprTy) // Make E1 be the simpler expression
std::swap(E1, E2);
if (V2 == Phi) { // referencing the PHI directly? Must have zero step
Step = Constant::getNullValue(Phi->getType());
} else if (BinaryOperator *I = dyn_cast<BinaryOperator>(V2)) {
- // TODO: This could be much better...
if (I->getOpcode() == Instruction::Add) {
if (I->getOperand(0) == Phi)
Step = I->getOperand(1);
else if (I->getOperand(1) == Phi)
Step = I->getOperand(0);
+ } else if (I->getOpcode() == Instruction::Sub &&
+ I->getOperand(0) == Phi) {
+ // If the incoming value is a constant, just form a constant negative
+ // step. Otherwise, negate the step outside of the loop and use it.
+ Value *V = I->getOperand(1);
+ Constant *Zero = Constant::getNullValue(V->getType());
+ if (Constant *CV = dyn_cast<Constant>(V))
+ Step = ConstantExpr::get(Instruction::Sub, Zero, CV);
+ else if (Instruction *I = dyn_cast<Instruction>(V)) {
+ Step = BinaryOperator::create(Instruction::Sub, Zero, V,
+ V->getName()+".neg", I->getNext());
+
+ } else {
+ Step = BinaryOperator::create(Instruction::Sub, Zero, V,
+ V->getName()+".neg",
+ Phi->getParent()->getParent()->begin()->begin());
+ }
}
+ } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(V2)) {
+ if (GEP->getNumOperands() == 2 &&
+ GEP->getOperand(0) == Phi)
+ Step = GEP->getOperand(1);
}
if (Step == 0) { // Unrecognized step value...
- ExprType StepE = ClassifyExpression(V2);
+ ExprType StepE = ClassifyExpr(V2);
if (StepE.ExprTy != ExprType::Linear ||
StepE.Var != Phi) return;
if (isa<PointerType>(ETy)) ETy = Type::ULongTy;
Step = (Value*)(StepE.Offset ? StepE.Offset : ConstantInt::get(ETy, 0));
} else { // We were able to get a step value, simplify with expr analysis
- ExprType StepE = ClassifyExpression(Step);
+ ExprType StepE = ClassifyExpr(Step);
if (StepE.ExprTy == ExprType::Linear && StepE.Offset == 0) {
// No offset from variable? Grab the variable
Step = StepE.Var;
}
-Value* InductionVariable::getExecutionCount(LoopInfo *LoopInfo) {
+Value *InductionVariable::getExecutionCount(LoopInfo *LoopInfo) {
+ if (InductionType != Canonical) return 0;
+
DEBUG(std::cerr << "entering getExecutionCount\n");
// Don't recompute if already available
const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
if (!L) {
DEBUG(std::cerr << "null loop. oops\n");
- return NULL;
+ return 0;
}
// >1 backedge => cannot predict number of iterations
if (Phi->getNumIncomingValues() != 2) {
DEBUG(std::cerr << ">2 incoming values. oops\n");
- return NULL;
+ return 0;
}
- // Find final node: predecesor of the loop header that's also an exit
+ // Find final node: predecessor of the loop header that's also an exit
BasicBlock *terminator = 0;
- BasicBlock *header = L->getHeader();
- for (pred_iterator PI = pred_begin(header), PE = pred_end(header);
- PI != PE; ++PI) {
+ for (pred_iterator PI = pred_begin(L->getHeader()),
+ PE = pred_end(L->getHeader()); PI != PE; ++PI)
if (L->isLoopExit(*PI)) {
terminator = *PI;
break;
}
- }
// Break in the loop => cannot predict number of iterations
// break: any block which is an exit node whose successor is not in loop,
// and this block is not marked as the terminator
//
const std::vector<BasicBlock*> &blocks = L->getBlocks();
- for (std::vector<BasicBlock*>::const_iterator i = blocks.begin(), e = blocks.end();
- i != e; ++i) {
- if (L->isLoopExit(*i) && (*i != terminator)) {
- for (succ_iterator SI = succ_begin(*i), SE = succ_end(*i); SI != SE; ++SI) {
- if (! L->contains(*SI)) {
+ for (std::vector<BasicBlock*>::const_iterator I = blocks.begin(),
+ e = blocks.end(); I != e; ++I)
+ if (L->isLoopExit(*I) && *I != terminator)
+ for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI)
+ if (!L->contains(*SI)) {
DEBUG(std::cerr << "break found in loop");
- return NULL;
+ return 0;
}
- }
- }
- }
BranchInst *B = dyn_cast<BranchInst>(terminator->getTerminator());
if (!B) {
- // this really should not happen
- DEBUG(std::cerr << "no terminator instruction!");
- return NULL;
+ DEBUG(std::cerr << "Terminator is not a cond branch!");
+ return 0;
}
SetCondInst *SCI = dyn_cast<SetCondInst>(B->getCondition());
+ if (!SCI) {
+ DEBUG(std::cerr << "Not a cond branch on setcc!\n");
+ return 0;
+ }
- if (SCI && InductionType == Cannonical) {
- DEBUG(std::cerr << "sci:" << *SCI);
- Value *condVal0 = SCI->getOperand(0);
- Value *condVal1 = SCI->getOperand(1);
- Value *indVar = 0;
+ DEBUG(std::cerr << "sci:" << *SCI);
+ Value *condVal0 = SCI->getOperand(0);
+ Value *condVal1 = SCI->getOperand(1);
- // the induction variable is the one coming from the backedge
- if (L->contains(Phi->getIncomingBlock(0))) {
- indVar = Phi->getIncomingValue(0);
- } else {
- indVar = Phi->getIncomingValue(1);
- }
+ // The induction variable is the one coming from the backedge
+ Value *indVar = Phi->getIncomingValue(L->contains(Phi->getIncomingBlock(1)));
- // check to see if indVar is one of the parameters in SCI
- // and if the other is loop-invariant, it is the UB
- if (indVar == condVal0) {
- if (isLoopInvariant(condVal1, L)) {
- End = condVal1;
- } else {
- DEBUG(std::cerr << "not loop invariant 1\n");
- }
- } else if (indVar == condVal1) {
- if (isLoopInvariant(condVal0, L)) {
- End = condVal0;
- } else {
- DEBUG(std::cerr << "not loop invariant 0\n");
- }
- }
- if (End) {
- switch (SCI->getOpcode()) {
- case Instruction::SetLT:
- case Instruction::SetNE: break; // already done
- case Instruction::SetLE: {
- // if compared to a constant int N, then predict N+1 iterations
- if (ConstantSInt *ubSigned = dyn_cast<ConstantSInt>(End)) {
- End = ConstantSInt::get(ubSigned->getType(), ubSigned->getValue()+1);
- DEBUG(std::cerr << "signed int constant\n");
- } else if (ConstantUInt *ubUnsigned = dyn_cast<ConstantUInt>(End)) {
- End = ConstantUInt::get(ubUnsigned->getType(), ubUnsigned->getValue()+1);
- DEBUG(std::cerr << "unsigned int constant\n");
- } else {
- DEBUG(std::cerr << "symbolic bound\n");
- //End = NULL;
- // new expression N+1
- End = BinaryOperator::create(Instruction::Add, End,
- ConstantUInt::get(ubUnsigned->getType(), 1));
- }
- break;
- }
- default: End = NULL; // cannot predict
- }
+ // Check to see if indVar is one of the parameters in SCI and if the other is
+ // loop-invariant, it is the UB
+ if (indVar == condVal0) {
+ if (isLoopInvariant(condVal1, L))
+ End = condVal1;
+ else {
+ DEBUG(std::cerr << "not loop invariant 1\n");
+ return 0;
+ }
+ } else if (indVar == condVal1) {
+ if (isLoopInvariant(condVal0, L))
+ End = condVal0;
+ else {
+ DEBUG(std::cerr << "not loop invariant 0\n");
+ return 0;
}
- return End;
} else {
- DEBUG(std::cerr << "SCI null or non-cannonical ind var\n");
+ DEBUG(std::cerr << "Loop condition doesn't directly uses indvar\n");
+ return 0;
+ }
+
+ switch (SCI->getOpcode()) {
+ case Instruction::SetLT:
+ case Instruction::SetNE: return End; // already done
+ case Instruction::SetLE:
+ // if compared to a constant int N, then predict N+1 iterations
+ if (ConstantSInt *ubSigned = dyn_cast<ConstantSInt>(End)) {
+ DEBUG(std::cerr << "signed int constant\n");
+ return ConstantSInt::get(ubSigned->getType(), ubSigned->getValue()+1);
+ } else if (ConstantUInt *ubUnsigned = dyn_cast<ConstantUInt>(End)) {
+ DEBUG(std::cerr << "unsigned int constant\n");
+ return ConstantUInt::get(ubUnsigned->getType(),
+ ubUnsigned->getValue()+1);
+ } else {
+ DEBUG(std::cerr << "symbolic bound\n");
+ // new expression N+1, insert right before the SCI. FIXME: If End is loop
+ // invariant, then so is this expression. We should insert it in the loop
+ // preheader if it exists.
+ return BinaryOperator::create(Instruction::Add, End,
+ ConstantInt::get(End->getType(), 1),
+ "tripcount", SCI);
+ }
+
+ default:
+ return 0; // cannot predict
}
- return NULL;
}
void InductionVariable::print(std::ostream &o) const {
switch (InductionType) {
- case InductionVariable::Cannonical: o << "Cannonical "; break;
+ case InductionVariable::Canonical: o << "Canonical "; break;
case InductionVariable::SimpleLinear: o << "SimpleLinear "; break;
case InductionVariable::Linear: o << "Linear "; break;
case InductionVariable::Unknown: o << "Unrecognized "; break;
projects / oota-llvm.git / blobdiff