STATISTIC(NumBruteForceTripCountsComputed,
"Number of loops with trip counts computed by force");
-cl::opt<unsigned>
+static cl::opt<unsigned>
MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
cl::desc("Maximum number of iterations SCEV will "
"symbolically execute a constant derived loop"),
cl::init(100));
-namespace {
- RegisterPass<ScalarEvolution>
- R("scalar-evolution", "Scalar Evolution Analysis");
-}
+static RegisterPass<ScalarEvolution>
+R("scalar-evolution", "Scalar Evolution Analysis", false, true);
char ScalarEvolution::ID = 0;
//===----------------------------------------------------------------------===//
return 0;
}
+bool SCEV::isZero() const {
+ if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(this))
+ return SC->getValue()->isZero();
+ return false;
+}
+
SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(scCouldNotCompute) {}
return SE.getMulExpr(NewOps);
else if (isa<SCEVSMaxExpr>(this))
return SE.getSMaxExpr(NewOps);
+ else if (isa<SCEVUMaxExpr>(this))
+ return SE.getUMaxExpr(NewOps);
else
assert(0 && "Unknown commutative expr!");
}
/// than the complexity of the RHS. This comparator is used to canonicalize
/// expressions.
struct VISIBILITY_HIDDEN SCEVComplexityCompare {
- bool operator()(SCEV *LHS, SCEV *RHS) {
+ bool operator()(const SCEV *LHS, const SCEV *RHS) const {
return LHS->getSCEVType() < RHS->getSCEVType();
}
};
if (Ops.size() == 2) {
// This is the common case, which also happens to be trivially simple.
// Special case it.
- if (Ops[0]->getSCEVType() > Ops[1]->getSCEVType())
+ if (SCEVComplexityCompare()(Ops[1], Ops[0]))
std::swap(Ops[0], Ops[1]);
return;
}
if (Val == 0)
C = Constant::getNullValue(Ty);
else if (Ty->isFloatingPoint())
- C = ConstantFP::get(Ty, APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
- APFloat::IEEEdouble, Val));
+ C = ConstantFP::get(APFloat(Ty==Type::FloatTy ? APFloat::IEEEsingle :
+ APFloat::IEEEdouble, Val));
else
C = ConstantInt::get(Ty, Val);
return getUnknown(C);
}
-/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion of the
-/// input value to the specified type. If the type must be extended, it is zero
-/// extended.
-static SCEVHandle getTruncateOrZeroExtend(const SCEVHandle &V, const Type *Ty,
- ScalarEvolution &SE) {
- const Type *SrcTy = V->getType();
- assert(SrcTy->isInteger() && Ty->isInteger() &&
- "Cannot truncate or zero extend with non-integer arguments!");
- if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits())
- return V; // No conversion
- if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits())
- return SE.getTruncateExpr(V, Ty);
- return SE.getZeroExtendExpr(V, Ty);
-}
-
/// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V
///
SCEVHandle ScalarEvolution::getNegativeSCEV(const SCEVHandle &V) {
if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
return getUnknown(ConstantExpr::getNeg(VC->getValue()));
- return getMulExpr(V, getIntegerSCEV(-1, V->getType()));
+ return getMulExpr(V, getConstant(ConstantInt::getAllOnesValue(V->getType())));
+}
+
+/// getNotSCEV - Return a SCEV corresponding to ~V = -1-V
+SCEVHandle ScalarEvolution::getNotSCEV(const SCEVHandle &V) {
+ if (SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
+ return getUnknown(ConstantExpr::getNot(VC->getValue()));
+
+ SCEVHandle AllOnes = getConstant(ConstantInt::getAllOnesValue(V->getType()));
+ return getMinusSCEV(AllOnes, V);
}
/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS.
#endif
const IntegerType *DividendTy = IntegerType::get(DividendBits);
- const SCEVHandle ExIt = SE.getZeroExtendExpr(It, DividendTy);
+ const SCEVHandle ExIt = SE.getTruncateOrZeroExtend(It, DividendTy);
// The final number of bits we need to perform the division is the maximum of
// dividend and divisor bitwidths.
Dividend *= N-(K-1);
if (DividendTy != DivisionTy)
Dividend = Dividend.zext(DivisionTy->getBitWidth());
- return SE.getConstant(Dividend.udiv(Divisor).trunc(It->getBitWidth()));
+
+ APInt Result = Dividend.udiv(Divisor);
+ if (Result.getBitWidth() != It->getBitWidth())
+ Result = Result.trunc(It->getBitWidth());
+
+ return SE.getConstant(Result);
}
SCEVHandle Dividend = ExIt;
Dividend =
SE.getMulExpr(Dividend,
SE.getMinusSCEV(ExIt, SE.getIntegerSCEV(i, DividendTy)));
- if (DividendTy != DivisionTy)
- Dividend = SE.getZeroExtendExpr(Dividend, DivisionTy);
- return
- SE.getTruncateExpr(SE.getUDivExpr(Dividend, SE.getConstant(Divisor)),
- It->getType());
+
+ return SE.getTruncateOrZeroExtend(
+ SE.getUDivExpr(
+ SE.getTruncateOrZeroExtend(Dividend, DivisionTy),
+ SE.getConstant(Divisor)
+ ), It->getType());
}
/// evaluateAtIteration - Return the value of this chain of recurrences at
return Result;
}
+/// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion
+/// of the input value to the specified type. If the type must be
+/// extended, it is zero extended.
+SCEVHandle ScalarEvolution::getTruncateOrZeroExtend(const SCEVHandle &V,
+ const Type *Ty) {
+ const Type *SrcTy = V->getType();
+ assert(SrcTy->isInteger() && Ty->isInteger() &&
+ "Cannot truncate or zero extend with non-integer arguments!");
+ if (SrcTy->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits())
+ return V; // No conversion
+ if (SrcTy->getPrimitiveSizeInBits() > Ty->getPrimitiveSizeInBits())
+ return getTruncateExpr(V, Ty);
+ return getZeroExtendExpr(V, Ty);
+}
+
// get - Get a canonical add expression, or something simpler if possible.
SCEVHandle ScalarEvolution::getAddExpr(std::vector<SCEVHandle> &Ops) {
assert(!Ops.empty() && "Cannot get empty add!");
assert(Idx < Ops.size());
while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- Constant *Fold = ConstantInt::get(LHSC->getValue()->getValue() +
- RHSC->getValue()->getValue());
- if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) {
- Ops[0] = getConstant(CI);
- Ops.erase(Ops.begin()+1); // Erase the folded element
- if (Ops.size() == 1) return Ops[0];
- LHSC = cast<SCEVConstant>(Ops[0]);
- } else {
- // If we couldn't fold the expression, move to the next constant. Note
- // that this is impossible to happen in practice because we always
- // constant fold constant ints to constant ints.
- ++Idx;
- }
+ ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() +
+ RHSC->getValue()->getValue());
+ Ops[0] = getConstant(Fold);
+ Ops.erase(Ops.begin()+1); // Erase the folded element
+ if (Ops.size() == 1) return Ops[0];
+ LHSC = cast<SCEVConstant>(Ops[0]);
}
// If we are left with a constant zero being added, strip it off.
++Idx;
while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- Constant *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
- RHSC->getValue()->getValue());
- if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) {
- Ops[0] = getConstant(CI);
- Ops.erase(Ops.begin()+1); // Erase the folded element
- if (Ops.size() == 1) return Ops[0];
- LHSC = cast<SCEVConstant>(Ops[0]);
- } else {
- // If we couldn't fold the expression, move to the next constant. Note
- // that this is impossible to happen in practice because we always
- // constant fold constant ints to constant ints.
- ++Idx;
- }
+ ConstantInt *Fold = ConstantInt::get(LHSC->getValue()->getValue() *
+ RHSC->getValue()->getValue());
+ Ops[0] = getConstant(Fold);
+ Ops.erase(Ops.begin()+1); // Erase the folded element
+ if (Ops.size() == 1) return Ops[0];
+ LHSC = cast<SCEVConstant>(Ops[0]);
}
// If we are left with a constant one being multiplied, strip it off.
const Loop *L) {
if (Operands.size() == 1) return Operands[0];
- if (SCEVConstant *StepC = dyn_cast<SCEVConstant>(Operands.back()))
- if (StepC->getValue()->isZero()) {
- Operands.pop_back();
- return getAddRecExpr(Operands, L); // { X,+,0 } --> X
- }
+ if (Operands.back()->isZero()) {
+ Operands.pop_back();
+ return getAddRecExpr(Operands, L); // { X,+,0 } --> X
+ }
SCEVAddRecExpr *&Result =
(*SCEVAddRecExprs)[std::make_pair(L, std::vector<SCEV*>(Operands.begin(),
assert(Idx < Ops.size());
while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
// We found two constants, fold them together!
- Constant *Fold = ConstantInt::get(
+ ConstantInt *Fold = ConstantInt::get(
APIntOps::smax(LHSC->getValue()->getValue(),
RHSC->getValue()->getValue()));
- if (ConstantInt *CI = dyn_cast<ConstantInt>(Fold)) {
- Ops[0] = getConstant(CI);
- Ops.erase(Ops.begin()+1); // Erase the folded element
- if (Ops.size() == 1) return Ops[0];
- LHSC = cast<SCEVConstant>(Ops[0]);
- } else {
- // If we couldn't fold the expression, move to the next constant. Note
- // that this is impossible to happen in practice because we always
- // constant fold constant ints to constant ints.
- ++Idx;
- }
+ Ops[0] = getConstant(Fold);
+ Ops.erase(Ops.begin()+1); // Erase the folded element
+ if (Ops.size() == 1) return Ops[0];
+ LHSC = cast<SCEVConstant>(Ops[0]);
}
// If we are left with a constant -inf, strip it off.
assert(!Ops.empty() && "Reduced smax down to nothing!");
- // Okay, it looks like we really DO need an add expr. Check to see if we
+ // Okay, it looks like we really DO need an smax expr. Check to see if we
// already have one, otherwise create a new one.
std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scSMaxExpr,
return Result;
}
+SCEVHandle ScalarEvolution::getUMaxExpr(const SCEVHandle &LHS,
+ const SCEVHandle &RHS) {
+ std::vector<SCEVHandle> Ops;
+ Ops.push_back(LHS);
+ Ops.push_back(RHS);
+ return getUMaxExpr(Ops);
+}
+
+SCEVHandle ScalarEvolution::getUMaxExpr(std::vector<SCEVHandle> Ops) {
+ assert(!Ops.empty() && "Cannot get empty umax!");
+ if (Ops.size() == 1) return Ops[0];
+
+ // Sort by complexity, this groups all similar expression types together.
+ GroupByComplexity(Ops);
+
+ // If there are any constants, fold them together.
+ unsigned Idx = 0;
+ if (SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) {
+ ++Idx;
+ assert(Idx < Ops.size());
+ while (SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) {
+ // We found two constants, fold them together!
+ ConstantInt *Fold = ConstantInt::get(
+ APIntOps::umax(LHSC->getValue()->getValue(),
+ RHSC->getValue()->getValue()));
+ Ops[0] = getConstant(Fold);
+ Ops.erase(Ops.begin()+1); // Erase the folded element
+ if (Ops.size() == 1) return Ops[0];
+ LHSC = cast<SCEVConstant>(Ops[0]);
+ }
+
+ // If we are left with a constant zero, strip it off.
+ if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) {
+ Ops.erase(Ops.begin());
+ --Idx;
+ }
+ }
+
+ if (Ops.size() == 1) return Ops[0];
+
+ // Find the first UMax
+ while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr)
+ ++Idx;
+
+ // Check to see if one of the operands is a UMax. If so, expand its operands
+ // onto our operand list, and recurse to simplify.
+ if (Idx < Ops.size()) {
+ bool DeletedUMax = false;
+ while (SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) {
+ Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end());
+ Ops.erase(Ops.begin()+Idx);
+ DeletedUMax = true;
+ }
+
+ if (DeletedUMax)
+ return getUMaxExpr(Ops);
+ }
+
+ // Okay, check to see if the same value occurs in the operand list twice. If
+ // so, delete one. Since we sorted the list, these values are required to
+ // be adjacent.
+ for (unsigned i = 0, e = Ops.size()-1; i != e; ++i)
+ if (Ops[i] == Ops[i+1]) { // X umax Y umax Y --> X umax Y
+ Ops.erase(Ops.begin()+i, Ops.begin()+i+1);
+ --i; --e;
+ }
+
+ if (Ops.size() == 1) return Ops[0];
+
+ assert(!Ops.empty() && "Reduced umax down to nothing!");
+
+ // Okay, it looks like we really DO need a umax expr. Check to see if we
+ // already have one, otherwise create a new one.
+ std::vector<SCEV*> SCEVOps(Ops.begin(), Ops.end());
+ SCEVCommutativeExpr *&Result = (*SCEVCommExprs)[std::make_pair(scUMaxExpr,
+ SCEVOps)];
+ if (Result == 0) Result = new SCEVUMaxExpr(Ops);
+ return Result;
+}
+
SCEVHandle ScalarEvolution::getUnknown(Value *V) {
if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
return getConstant(CI);
return MinOpRes;
}
+ if (SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
+ // The result is the min of all operands results.
+ uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
+ for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
+ MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
+ return MinOpRes;
+ }
+
// SCEVUDivExpr, SCEVUnknown
return 0;
}
if (!isa<IntegerType>(V->getType()))
return SE.getUnknown(V);
- if (Instruction *I = dyn_cast<Instruction>(V)) {
- switch (I->getOpcode()) {
- case Instruction::Add:
- return SE.getAddExpr(getSCEV(I->getOperand(0)),
- getSCEV(I->getOperand(1)));
- case Instruction::Mul:
- return SE.getMulExpr(getSCEV(I->getOperand(0)),
- getSCEV(I->getOperand(1)));
- case Instruction::UDiv:
- return SE.getUDivExpr(getSCEV(I->getOperand(0)),
- getSCEV(I->getOperand(1)));
- case Instruction::Sub:
- return SE.getMinusSCEV(getSCEV(I->getOperand(0)),
- getSCEV(I->getOperand(1)));
- case Instruction::Or:
- // If the RHS of the Or is a constant, we may have something like:
- // X*4+1 which got turned into X*4|1. Handle this as an Add so loop
- // optimizations will transparently handle this case.
- //
- // In order for this transformation to be safe, the LHS must be of the
- // form X*(2^n) and the Or constant must be less than 2^n.
- if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
- SCEVHandle LHS = getSCEV(I->getOperand(0));
- const APInt &CIVal = CI->getValue();
- if (GetMinTrailingZeros(LHS) >=
- (CIVal.getBitWidth() - CIVal.countLeadingZeros()))
- return SE.getAddExpr(LHS, getSCEV(I->getOperand(1)));
- }
- break;
- case Instruction::Xor:
- // If the RHS of the xor is a signbit, then this is just an add.
- // Instcombine turns add of signbit into xor as a strength reduction step.
- if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
- if (CI->getValue().isSignBit())
- return SE.getAddExpr(getSCEV(I->getOperand(0)),
- getSCEV(I->getOperand(1)));
- }
- break;
-
- case Instruction::Shl:
- // Turn shift left of a constant amount into a multiply.
- if (ConstantInt *SA = dyn_cast<ConstantInt>(I->getOperand(1))) {
- uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
- Constant *X = ConstantInt::get(
- APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
- return SE.getMulExpr(getSCEV(I->getOperand(0)), getSCEV(X));
- }
- break;
-
- case Instruction::Trunc:
- return SE.getTruncateExpr(getSCEV(I->getOperand(0)), I->getType());
-
- case Instruction::ZExt:
- return SE.getZeroExtendExpr(getSCEV(I->getOperand(0)), I->getType());
-
- case Instruction::SExt:
- return SE.getSignExtendExpr(getSCEV(I->getOperand(0)), I->getType());
-
- case Instruction::BitCast:
- // BitCasts are no-op casts so we just eliminate the cast.
- if (I->getType()->isInteger() &&
- I->getOperand(0)->getType()->isInteger())
- return getSCEV(I->getOperand(0));
- break;
-
- case Instruction::PHI:
- return createNodeForPHI(cast<PHINode>(I));
-
- case Instruction::Select:
- // This could be an SCEVSMax that was lowered earlier. Try to recover it.
- if (ICmpInst *ICI = dyn_cast<ICmpInst>(I->getOperand(0))) {
- Value *LHS = ICI->getOperand(0);
- Value *RHS = ICI->getOperand(1);
- switch (ICI->getPredicate()) {
- case ICmpInst::ICMP_SLT:
- case ICmpInst::ICMP_SLE:
- std::swap(LHS, RHS);
- // fall through
- case ICmpInst::ICMP_SGT:
- case ICmpInst::ICMP_SGE:
- if (LHS == I->getOperand(1) && RHS == I->getOperand(2))
- return SE.getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
- default:
- break;
- }
- }
+ unsigned Opcode = Instruction::UserOp1;
+ if (Instruction *I = dyn_cast<Instruction>(V))
+ Opcode = I->getOpcode();
+ else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
+ Opcode = CE->getOpcode();
+ else
+ return SE.getUnknown(V);
- default: // We cannot analyze this expression.
- break;
+ User *U = cast<User>(V);
+ switch (Opcode) {
+ case Instruction::Add:
+ return SE.getAddExpr(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
+ case Instruction::Mul:
+ return SE.getMulExpr(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
+ case Instruction::UDiv:
+ return SE.getUDivExpr(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
+ case Instruction::Sub:
+ return SE.getMinusSCEV(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
+ case Instruction::Or:
+ // If the RHS of the Or is a constant, we may have something like:
+ // X*4+1 which got turned into X*4|1. Handle this as an Add so loop
+ // optimizations will transparently handle this case.
+ //
+ // In order for this transformation to be safe, the LHS must be of the
+ // form X*(2^n) and the Or constant must be less than 2^n.
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
+ SCEVHandle LHS = getSCEV(U->getOperand(0));
+ const APInt &CIVal = CI->getValue();
+ if (GetMinTrailingZeros(LHS) >=
+ (CIVal.getBitWidth() - CIVal.countLeadingZeros()))
+ return SE.getAddExpr(LHS, getSCEV(U->getOperand(1)));
}
+ break;
+ case Instruction::Xor:
+ // If the RHS of the xor is a signbit, then this is just an add.
+ // Instcombine turns add of signbit into xor as a strength reduction step.
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(U->getOperand(1))) {
+ if (CI->getValue().isSignBit())
+ return SE.getAddExpr(getSCEV(U->getOperand(0)),
+ getSCEV(U->getOperand(1)));
+ else if (CI->isAllOnesValue())
+ return SE.getNotSCEV(getSCEV(U->getOperand(0)));
+ }
+ break;
+
+ case Instruction::Shl:
+ // Turn shift left of a constant amount into a multiply.
+ if (ConstantInt *SA = dyn_cast<ConstantInt>(U->getOperand(1))) {
+ uint32_t BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
+ Constant *X = ConstantInt::get(
+ APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth)));
+ return SE.getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X));
+ }
+ break;
+
+ case Instruction::Trunc:
+ return SE.getTruncateExpr(getSCEV(U->getOperand(0)), U->getType());
+
+ case Instruction::ZExt:
+ return SE.getZeroExtendExpr(getSCEV(U->getOperand(0)), U->getType());
+
+ case Instruction::SExt:
+ return SE.getSignExtendExpr(getSCEV(U->getOperand(0)), U->getType());
+
+ case Instruction::BitCast:
+ // BitCasts are no-op casts so we just eliminate the cast.
+ if (U->getType()->isInteger() &&
+ U->getOperand(0)->getType()->isInteger())
+ return getSCEV(U->getOperand(0));
+ break;
+
+ case Instruction::PHI:
+ return createNodeForPHI(cast<PHINode>(U));
+
+ case Instruction::Select:
+ // This could be a smax or umax that was lowered earlier.
+ // Try to recover it.
+ if (ICmpInst *ICI = dyn_cast<ICmpInst>(U->getOperand(0))) {
+ Value *LHS = ICI->getOperand(0);
+ Value *RHS = ICI->getOperand(1);
+ switch (ICI->getPredicate()) {
+ case ICmpInst::ICMP_SLT:
+ case ICmpInst::ICMP_SLE:
+ std::swap(LHS, RHS);
+ // fall through
+ case ICmpInst::ICMP_SGT:
+ case ICmpInst::ICMP_SGE:
+ if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
+ return SE.getSMaxExpr(getSCEV(LHS), getSCEV(RHS));
+ else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
+ // -smax(-x, -y) == smin(x, y).
+ return SE.getNegativeSCEV(SE.getSMaxExpr(
+ SE.getNegativeSCEV(getSCEV(LHS)),
+ SE.getNegativeSCEV(getSCEV(RHS))));
+ break;
+ case ICmpInst::ICMP_ULT:
+ case ICmpInst::ICMP_ULE:
+ std::swap(LHS, RHS);
+ // fall through
+ case ICmpInst::ICMP_UGT:
+ case ICmpInst::ICMP_UGE:
+ if (LHS == U->getOperand(1) && RHS == U->getOperand(2))
+ return SE.getUMaxExpr(getSCEV(LHS), getSCEV(RHS));
+ else if (LHS == U->getOperand(2) && RHS == U->getOperand(1))
+ // ~umax(~x, ~y) == umin(x, y)
+ return SE.getNotSCEV(SE.getUMaxExpr(SE.getNotSCEV(getSCEV(LHS)),
+ SE.getNotSCEV(getSCEV(RHS))));
+ break;
+ default:
+ break;
+ }
+ }
+
+ default: // We cannot analyze this expression.
+ break;
}
return SE.getUnknown(V);
ICmpInst *ExitCond = dyn_cast<ICmpInst>(ExitBr->getCondition());
- // If its not an integer comparison then compute it the hard way.
+ // If it's not an integer comparison then compute it the hard way.
// Note that ICmpInst deals with pointer comparisons too so we must check
// the type of the operand.
if (ExitCond == 0 || isa<PointerType>(ExitCond->getOperand(0)->getType()))
// At this point, we would like to compute how many iterations of the
// loop the predicate will return true for these inputs.
- if (LHS->isLoopInvariant(L) && !RHS->isLoopInvariant(L)) {
- // If there is a loop-invariant, force it into the RHS.
+ if (isa<SCEVConstant>(LHS) && !isa<SCEVConstant>(RHS)) {
+ // If there is a constant, force it into the RHS.
std::swap(LHS, RHS);
Cond = ICmpInst::getSwappedPredicate(Cond);
}
break;
}
case ICmpInst::ICMP_UGT: {
- SCEVHandle TC = HowManyLessThans(SE.getNegativeSCEV(LHS),
- SE.getNegativeSCEV(RHS), L, false);
+ SCEVHandle TC = HowManyLessThans(SE.getNotSCEV(LHS),
+ SE.getNotSCEV(RHS), L, false);
if (!isa<SCEVCouldNotCompute>(TC)) return TC;
break;
}
}
/// ComputeLoadConstantCompareIterationCount - Given an exit condition of
-/// 'icmp op load X, cst', try to se if we can compute the trip count.
+/// 'icmp op load X, cst', try to see if we can compute the trip count.
SCEVHandle ScalarEvolutionsImpl::
ComputeLoadConstantCompareIterationCount(LoadInst *LI, Constant *RHS,
const Loop *L,
Instruction *I = dyn_cast<Instruction>(V);
if (I == 0 || !L->contains(I->getParent())) return 0;
- if (PHINode *PN = dyn_cast<PHINode>(I))
+ if (PHINode *PN = dyn_cast<PHINode>(I)) {
if (L->getHeader() == I->getParent())
return PN;
else
// We don't currently keep track of the control flow needed to evaluate
// PHIs, so we cannot handle PHIs inside of loops.
return 0;
+ }
// If we won't be able to constant fold this expression even if the operands
// are constants, return early.
/// reason, return null.
static Constant *EvaluateExpression(Value *V, Constant *PHIVal) {
if (isa<PHINode>(V)) return PHIVal;
- if (GlobalValue *GV = dyn_cast<GlobalValue>(V))
- return GV;
if (Constant *C = dyn_cast<Constant>(V)) return C;
Instruction *I = cast<Instruction>(V);
if (isa<SCEVConstant>(V)) return V;
- // If this instruction is evolves from a constant-evolving PHI, compute the
+ // If this instruction is evolved from a constant-evolving PHI, compute the
// exit value from the loop without using SCEVs.
if (SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) {
if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) {
return SE.getMulExpr(NewOps);
if (isa<SCEVSMaxExpr>(Comm))
return SE.getSMaxExpr(NewOps);
+ if (isa<SCEVUMaxExpr>(Comm))
+ return SE.getUMaxExpr(NewOps);
assert(0 && "Unknown commutative SCEV type!");
}
}
// loop iterates. Compute this now.
SCEVHandle IterationCount = getIterationCount(AddRec->getLoop());
if (IterationCount == UnknownValue) return UnknownValue;
- IterationCount = getTruncateOrZeroExtend(IterationCount,
- AddRec->getType(), SE);
+ IterationCount = SE.getTruncateOrZeroExtend(IterationCount,
+ AddRec->getType());
// If the value is affine, simplify the expression evaluation to just
// Start + Step*IterationCount.
if (SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) {
ConstantInt *StartCC = StartC->getValue();
Constant *StartNegC = ConstantExpr::getNeg(StartCC);
- Constant *Rem = ConstantExpr::getSRem(StartNegC, StepC->getValue());
+ Constant *Rem = ConstantExpr::getURem(StartNegC, StepC->getValue());
if (Rem->isNullValue()) {
- Constant *Result =ConstantExpr::getSDiv(StartNegC,StepC->getValue());
+ Constant *Result = ConstantExpr::getUDiv(StartNegC,StepC->getValue());
return SE.getUnknown(Result);
}
}
// value at this index. When solving for "X*X != 5", for example, we
// should not accept a root of 2.
SCEVHandle Val = AddRec->evaluateAtIteration(R1, SE);
- if (SCEVConstant *EvalVal = dyn_cast<SCEVConstant>(Val))
- if (EvalVal->getValue()->isZero())
- return R1; // We found a quadratic root!
+ if (Val->isZero())
+ return R1; // We found a quadratic root!
}
}
}
// If the value is a constant, check to see if it is known to be non-zero
// already. If so, the backedge will execute zero times.
if (SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
- Constant *Zero = Constant::getNullValue(C->getValue()->getType());
- Constant *NonZero =
- ConstantExpr::getICmp(ICmpInst::ICMP_NE, C->getValue(), Zero);
- if (NonZero == ConstantInt::getTrue())
- return getSCEV(Zero);
+ if (!C->getValue()->isNullValue())
+ return SE.getIntegerSCEV(0, C->getType());
return UnknownValue; // Otherwise it will loop infinitely.
}
return UnknownValue;
if (AddRec->isAffine()) {
- // The number of iterations for "{n,+,1} < m", is m-n. However, we don't
- // know that m is >= n on input to the loop. If it is, the condition
- // returns true zero times. To handle both cases, we return SMAX(0, m-n).
-
// FORNOW: We only support unit strides.
SCEVHandle One = SE.getIntegerSCEV(1, RHS->getType());
if (AddRec->getOperand(1) != One)
return UnknownValue;
- SCEVHandle Iters = SE.getMinusSCEV(RHS, AddRec->getOperand(0));
+ // We know the LHS is of the form {n,+,1} and the RHS is some loop-invariant
+ // m. So, we count the number of iterations in which {n,+,1} < m is true.
+ // Note that we cannot simply return max(m-n,0) because it's not safe to
+ // treat m-n as signed nor unsigned due to overflow possibility.
- if (isSigned)
- return SE.getSMaxExpr(SE.getIntegerSCEV(0, RHS->getType()), Iters);
- else
- return Iters;
+ // First, we get the value of the LHS in the first iteration: n
+ SCEVHandle Start = AddRec->getOperand(0);
+
+ // Then, we get the value of the LHS in the first iteration in which the
+ // above condition doesn't hold. This equals to max(m,n).
+ SCEVHandle End = isSigned ? SE.getSMaxExpr(RHS, Start)
+ : SE.getUMaxExpr(RHS, Start);
+
+ // Finally, we subtract these two values to get the number of times the
+ // backedge is executed: max(m,n)-n.
+ return SE.getMinusSCEV(End, Start);
}
return UnknownValue;
projects / oota-llvm.git / blobdiff