#include "llvm/Analysis/InductionVariable.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/Expressions.h"
+#include "llvm/BasicBlock.h"
#include "llvm/iPHINode.h"
-#include "llvm/InstrTypes.h"
+#include "llvm/iOperators.h"
+#include "llvm/iTerminators.h"
#include "llvm/Type.h"
#include "llvm/Constants.h"
-
-using analysis::ExprType;
-
+#include "llvm/Support/CFG.h"
+#include "llvm/Assembly/Writer.h"
+#include "Support/Statistic.h"
static bool isLoopInvariant(const Value *V, const Loop *L) {
if (isa<Constant>(V) || isa<Argument>(V) || isa<GlobalValue>(V))
enum InductionVariable::iType
InductionVariable::Classify(const Value *Start, const Value *Step,
- const Loop *L) {
+ const Loop *L) {
// Check for cannonical 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;
+ return Cannonical;
else
- return SimpleLinear;
+ return SimpleLinear;
}
// Without loop information, we cannot do any better, so bail now...
// Create an induction variable for the specified value. If it is a PHI, and
// if it's recognizable, classify it and fill in instance variables.
//
-InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo) {
+InductionVariable::InductionVariable(PHINode *P, LoopInfo *LoopInfo): End(0) {
InductionType = Unknown; // Assume the worst
Phi = P;
Value *V2 = Phi->getIncomingValue(1);
if (L == 0) { // No loop information? Base everything on expression analysis
- ExprType E1 = analysis::ClassifyExpression(V1);
- ExprType E2 = analysis::ClassifyExpression(V2);
+ ExprType E1 = ClassifyExpression(V1);
+ ExprType E2 = ClassifyExpression(V2);
if (E1.ExprTy > E2.ExprTy) // Make E1 be the simpler expression
std::swap(E1, E2);
// with respect to the PHI node.
//
if (E1.ExprTy > ExprType::Constant || E2.ExprTy != ExprType::Linear ||
- E2.Var != Phi)
+ E2.Var != Phi)
return;
// Okay, we have found an induction variable. Save the start and step values
} 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);
+ if (I->getOperand(0) == Phi)
+ Step = I->getOperand(1);
+ else if (I->getOperand(1) == Phi)
+ Step = I->getOperand(0);
}
}
if (Step == 0) { // Unrecognized step value...
- ExprType StepE = analysis::ClassifyExpression(V2);
+ ExprType StepE = ClassifyExpression(V2);
if (StepE.ExprTy != ExprType::Linear ||
- StepE.Var != Phi) return;
+ StepE.Var != Phi) return;
const Type *ETy = Phi->getType();
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 = analysis::ClassifyExpression(Step);
+ ExprType StepE = ClassifyExpression(Step);
if (StepE.ExprTy == ExprType::Linear && StepE.Offset == 0) {
// No offset from variable? Grab the variable
Step = StepE.Var;
// Classify the induction variable type now...
InductionType = InductionVariable::Classify(Start, Step, L);
}
+
+
+Value* InductionVariable::getExecutionCount(LoopInfo *LoopInfo) {
+ DEBUG(std::cerr << "entering getExecutionCount\n");
+
+ // Don't recompute if already available
+ if (End) {
+ DEBUG(std::cerr << "returning cached End value.\n");
+ return End;
+ }
+
+ const Loop *L = LoopInfo ? LoopInfo->getLoopFor(Phi->getParent()) : 0;
+ if (!L) {
+ DEBUG(std::cerr << "null loop. oops\n");
+ return NULL;
+ }
+
+ // >1 backedge => cannot predict number of iterations
+ if (Phi->getNumIncomingValues() != 2) {
+ DEBUG(std::cerr << ">2 incoming values. oops\n");
+ return NULL;
+ }
+
+ // Find final node: predecesor 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) {
+ 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)) {
+ DEBUG(std::cerr << "break found in loop");
+ return NULL;
+ }
+ }
+ }
+ }
+
+ BranchInst *B = dyn_cast<BranchInst>(terminator->getTerminator());
+ if (!B) {
+ // this really should not happen
+ DEBUG(std::cerr << "no terminator instruction!");
+ return NULL;
+ }
+ SetCondInst *SCI = dyn_cast<SetCondInst>(&*B->getCondition());
+
+ if (SCI && InductionType == Cannonical) {
+ DEBUG(std::cerr << "sci:" << *SCI);
+ Value *condVal0 = SCI->getOperand(0);
+ Value *condVal1 = SCI->getOperand(1);
+ Value *indVar = 0;
+
+ // 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);
+ }
+
+ // 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
+ }
+ }
+ return End;
+ } else {
+ DEBUG(std::cerr << "SCI null or non-cannonical ind var\n");
+ }
+ return NULL;
+}
+
+
+void InductionVariable::print(std::ostream &o) const {
+ switch (InductionType) {
+ case InductionVariable::Cannonical: o << "Cannonical "; break;
+ case InductionVariable::SimpleLinear: o << "SimpleLinear "; break;
+ case InductionVariable::Linear: o << "Linear "; break;
+ case InductionVariable::Unknown: o << "Unrecognized "; break;
+ }
+ o << "Induction Variable: ";
+ if (Phi) {
+ WriteAsOperand(o, Phi);
+ o << ":\n" << Phi;
+ } else {
+ o << "\n";
+ }
+ if (InductionType == InductionVariable::Unknown) return;
+
+ o << " Start = "; WriteAsOperand(o, Start);
+ o << " Step = " ; WriteAsOperand(o, Step);
+ if (End) {
+ o << " End = " ; WriteAsOperand(o, End);
+ }
+ o << "\n";
+}
projects / oota-llvm.git / blobdiff