X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolution.cpp;h=62244ccb3a03a1222e5014c25a5b0ae0ba823b82;hb=a656b63ee4d5b0e3f4d26a55dd4cc69795746684;hp=6bb121f82ab078c647ad61b400eb3b438c55c44b;hpb=9f1fb42b7e6260bcc535cfd50df60b35e17672f8;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index 6bb121f82ab..62244ccb3a0 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -69,6 +69,7 @@ #include "llvm/Operator.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Assembly/Writer.h" @@ -103,8 +104,12 @@ MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, "derived loop"), cl::init(100)); -INITIALIZE_PASS(ScalarEvolution, "scalar-evolution", - "Scalar Evolution Analysis", false, true); +INITIALIZE_PASS_BEGIN(ScalarEvolution, "scalar-evolution", + "Scalar Evolution Analysis", false, true) +INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_END(ScalarEvolution, "scalar-evolution", + "Scalar Evolution Analysis", false, true) char ScalarEvolution::ID = 0; //===----------------------------------------------------------------------===// @@ -115,13 +120,139 @@ char ScalarEvolution::ID = 0; // Implementation of the SCEV class. // -SCEV::~SCEV() {} - void SCEV::dump() const { print(dbgs()); dbgs() << '\n'; } +void SCEV::print(raw_ostream &OS) const { + switch (getSCEVType()) { + case scConstant: + WriteAsOperand(OS, cast(this)->getValue(), false); + return; + case scTruncate: { + const SCEVTruncateExpr *Trunc = cast(this); + const SCEV *Op = Trunc->getOperand(); + OS << "(trunc " << *Op->getType() << " " << *Op << " to " + << *Trunc->getType() << ")"; + return; + } + case scZeroExtend: { + const SCEVZeroExtendExpr *ZExt = cast(this); + const SCEV *Op = ZExt->getOperand(); + OS << "(zext " << *Op->getType() << " " << *Op << " to " + << *ZExt->getType() << ")"; + return; + } + case scSignExtend: { + const SCEVSignExtendExpr *SExt = cast(this); + const SCEV *Op = SExt->getOperand(); + OS << "(sext " << *Op->getType() << " " << *Op << " to " + << *SExt->getType() << ")"; + return; + } + case scAddRecExpr: { + const SCEVAddRecExpr *AR = cast(this); + OS << "{" << *AR->getOperand(0); + for (unsigned i = 1, e = AR->getNumOperands(); i != e; ++i) + OS << ",+," << *AR->getOperand(i); + OS << "}<"; + if (AR->hasNoUnsignedWrap()) + OS << "nuw><"; + if (AR->hasNoSignedWrap()) + OS << "nsw><"; + WriteAsOperand(OS, AR->getLoop()->getHeader(), /*PrintType=*/false); + OS << ">"; + return; + } + case scAddExpr: + case scMulExpr: + case scUMaxExpr: + case scSMaxExpr: { + const SCEVNAryExpr *NAry = cast(this); + const char *OpStr = 0; + switch (NAry->getSCEVType()) { + case scAddExpr: OpStr = " + "; break; + case scMulExpr: OpStr = " * "; break; + case scUMaxExpr: OpStr = " umax "; break; + case scSMaxExpr: OpStr = " smax "; break; + } + OS << "("; + for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); + I != E; ++I) { + OS << **I; + if (llvm::next(I) != E) + OS << OpStr; + } + OS << ")"; + return; + } + case scUDivExpr: { + const SCEVUDivExpr *UDiv = cast(this); + OS << "(" << *UDiv->getLHS() << " /u " << *UDiv->getRHS() << ")"; + return; + } + case scUnknown: { + const SCEVUnknown *U = cast(this); + const Type *AllocTy; + if (U->isSizeOf(AllocTy)) { + OS << "sizeof(" << *AllocTy << ")"; + return; + } + if (U->isAlignOf(AllocTy)) { + OS << "alignof(" << *AllocTy << ")"; + return; + } + + const Type *CTy; + Constant *FieldNo; + if (U->isOffsetOf(CTy, FieldNo)) { + OS << "offsetof(" << *CTy << ", "; + WriteAsOperand(OS, FieldNo, false); + OS << ")"; + return; + } + + // Otherwise just print it normally. + WriteAsOperand(OS, U->getValue(), false); + return; + } + case scCouldNotCompute: + OS << "***COULDNOTCOMPUTE***"; + return; + default: break; + } + llvm_unreachable("Unknown SCEV kind!"); +} + +const Type *SCEV::getType() const { + switch (getSCEVType()) { + case scConstant: + return cast(this)->getType(); + case scTruncate: + case scZeroExtend: + case scSignExtend: + return cast(this)->getType(); + case scAddRecExpr: + case scMulExpr: + case scUMaxExpr: + case scSMaxExpr: + return cast(this)->getType(); + case scAddExpr: + return cast(this)->getType(); + case scUDivExpr: + return cast(this)->getType(); + case scUnknown: + return cast(this)->getType(); + case scCouldNotCompute: + llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); + return 0; + default: break; + } + llvm_unreachable("Unknown SCEV kind!"); + return 0; +} + bool SCEV::isZero() const { if (const SCEVConstant *SC = dyn_cast(this)) return SC->getValue()->isZero(); @@ -143,30 +274,6 @@ bool SCEV::isAllOnesValue() const { SCEVCouldNotCompute::SCEVCouldNotCompute() : SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {} -bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const { - llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); - return false; -} - -const Type *SCEVCouldNotCompute::getType() const { - llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); - return 0; -} - -bool SCEVCouldNotCompute::hasComputableLoopEvolution(const Loop *L) const { - llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); - return false; -} - -bool SCEVCouldNotCompute::hasOperand(const SCEV *) const { - llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); - return false; -} - -void SCEVCouldNotCompute::print(raw_ostream &OS) const { - OS << "***COULDNOTCOMPUTE***"; -} - bool SCEVCouldNotCompute::classof(const SCEV *S) { return S->getSCEVType() == scCouldNotCompute; } @@ -192,24 +299,10 @@ ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) { return getConstant(ConstantInt::get(ITy, V, isSigned)); } -const Type *SCEVConstant::getType() const { return V->getType(); } - -void SCEVConstant::print(raw_ostream &OS) const { - WriteAsOperand(OS, V, false); -} - SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID, unsigned SCEVTy, const SCEV *op, const Type *ty) : SCEV(ID, SCEVTy), Op(op), Ty(ty) {} -bool SCEVCastExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { - return Op->dominates(BB, DT); -} - -bool SCEVCastExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - return Op->properlyDominates(BB, DT); -} - SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op, const Type *ty) : SCEVCastExpr(ID, scTruncate, op, ty) { @@ -218,10 +311,6 @@ SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, "Cannot truncate non-integer value!"); } -void SCEVTruncateExpr::print(raw_ostream &OS) const { - OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; -} - SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, const SCEV *op, const Type *ty) : SCEVCastExpr(ID, scZeroExtend, op, ty) { @@ -230,10 +319,6 @@ SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, "Cannot zero extend non-integer value!"); } -void SCEVZeroExtendExpr::print(raw_ostream &OS) const { - OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; -} - SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, const SCEV *op, const Type *ty) : SCEVCastExpr(ID, scSignExtend, op, ty) { @@ -242,108 +327,9 @@ SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, "Cannot sign extend non-integer value!"); } -void SCEVSignExtendExpr::print(raw_ostream &OS) const { - OS << "(sext " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; -} - -void SCEVCommutativeExpr::print(raw_ostream &OS) const { - const char *OpStr = getOperationStr(); - OS << "("; - for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) { - OS << **I; - if (llvm::next(I) != E) - OS << OpStr; - } - OS << ")"; -} - -bool SCEVNAryExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { - if (!getOperand(i)->dominates(BB, DT)) - return false; - } - return true; -} - -bool SCEVNAryExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { - if (!getOperand(i)->properlyDominates(BB, DT)) - return false; - } - return true; -} - -bool SCEVUDivExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { - return LHS->dominates(BB, DT) && RHS->dominates(BB, DT); -} - -bool SCEVUDivExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - return LHS->properlyDominates(BB, DT) && RHS->properlyDominates(BB, DT); -} - -void SCEVUDivExpr::print(raw_ostream &OS) const { - OS << "(" << *LHS << " /u " << *RHS << ")"; -} - -const Type *SCEVUDivExpr::getType() const { - // In most cases the types of LHS and RHS will be the same, but in some - // crazy cases one or the other may be a pointer. ScalarEvolution doesn't - // depend on the type for correctness, but handling types carefully can - // avoid extra casts in the SCEVExpander. The LHS is more likely to be - // a pointer type than the RHS, so use the RHS' type here. - return RHS->getType(); -} - -bool SCEVAddRecExpr::isLoopInvariant(const Loop *QueryLoop) const { - // Add recurrences are never invariant in the function-body (null loop). - if (!QueryLoop) - return false; - - // This recurrence is variant w.r.t. QueryLoop if QueryLoop contains L. - if (QueryLoop->contains(L)) - return false; - - // This recurrence is invariant w.r.t. QueryLoop if L contains QueryLoop. - if (L->contains(QueryLoop)) - return true; - - // This recurrence is variant w.r.t. QueryLoop if any of its operands - // are variant. - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) - if (!getOperand(i)->isLoopInvariant(QueryLoop)) - return false; - - // Otherwise it's loop-invariant. - return true; -} - -bool -SCEVAddRecExpr::dominates(BasicBlock *BB, DominatorTree *DT) const { - return DT->dominates(L->getHeader(), BB) && - SCEVNAryExpr::dominates(BB, DT); -} - -bool -SCEVAddRecExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - // This uses a "dominates" query instead of "properly dominates" query because - // the instruction which produces the addrec's value is a PHI, and a PHI - // effectively properly dominates its entire containing block. - return DT->dominates(L->getHeader(), BB) && - SCEVNAryExpr::properlyDominates(BB, DT); -} - -void SCEVAddRecExpr::print(raw_ostream &OS) const { - OS << "{" << *Operands[0]; - for (unsigned i = 1, e = NumOperands; i != e; ++i) - OS << ",+," << *Operands[i]; - OS << "}<"; - WriteAsOperand(OS, L->getHeader(), /*PrintType=*/false); - OS << ">"; -} - void SCEVUnknown::deleted() { - // Clear this SCEVUnknown from ValuesAtScopes. - SE->ValuesAtScopes.erase(this); + // Clear this SCEVUnknown from various maps. + SE->forgetMemoizedResults(this); // Remove this SCEVUnknown from the uniquing map. SE->UniqueSCEVs.RemoveNode(this); @@ -353,8 +339,8 @@ void SCEVUnknown::deleted() { } void SCEVUnknown::allUsesReplacedWith(Value *New) { - // Clear this SCEVUnknown from ValuesAtScopes. - SE->ValuesAtScopes.erase(this); + // Clear this SCEVUnknown from various maps. + SE->forgetMemoizedResults(this); // Remove this SCEVUnknown from the uniquing map. SE->UniqueSCEVs.RemoveNode(this); @@ -365,32 +351,6 @@ void SCEVUnknown::allUsesReplacedWith(Value *New) { setValPtr(New); } -bool SCEVUnknown::isLoopInvariant(const Loop *L) const { - // All non-instruction values are loop invariant. All instructions are loop - // invariant if they are not contained in the specified loop. - // Instructions are never considered invariant in the function body - // (null loop) because they are defined within the "loop". - if (Instruction *I = dyn_cast(getValue())) - return L && !L->contains(I); - return true; -} - -bool SCEVUnknown::dominates(BasicBlock *BB, DominatorTree *DT) const { - if (Instruction *I = dyn_cast(getValue())) - return DT->dominates(I->getParent(), BB); - return true; -} - -bool SCEVUnknown::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - if (Instruction *I = dyn_cast(getValue())) - return DT->properlyDominates(I->getParent(), BB); - return true; -} - -const Type *SCEVUnknown::getType() const { - return getValue()->getType(); -} - bool SCEVUnknown::isSizeOf(const Type *&AllocTy) const { if (ConstantExpr *VCE = dyn_cast(getValue())) if (VCE->getOpcode() == Instruction::PtrToInt) @@ -455,69 +415,10 @@ bool SCEVUnknown::isOffsetOf(const Type *&CTy, Constant *&FieldNo) const { return false; } -void SCEVUnknown::print(raw_ostream &OS) const { - const Type *AllocTy; - if (isSizeOf(AllocTy)) { - OS << "sizeof(" << *AllocTy << ")"; - return; - } - if (isAlignOf(AllocTy)) { - OS << "alignof(" << *AllocTy << ")"; - return; - } - - const Type *CTy; - Constant *FieldNo; - if (isOffsetOf(CTy, FieldNo)) { - OS << "offsetof(" << *CTy << ", "; - WriteAsOperand(OS, FieldNo, false); - OS << ")"; - return; - } - - // Otherwise just print it normally. - WriteAsOperand(OS, getValue(), false); -} - //===----------------------------------------------------------------------===// // SCEV Utilities //===----------------------------------------------------------------------===// -static bool CompareTypes(const Type *A, const Type *B) { - if (A->getTypeID() != B->getTypeID()) - return A->getTypeID() < B->getTypeID(); - if (const IntegerType *AI = dyn_cast(A)) { - const IntegerType *BI = cast(B); - return AI->getBitWidth() < BI->getBitWidth(); - } - if (const PointerType *AI = dyn_cast(A)) { - const PointerType *BI = cast(B); - return CompareTypes(AI->getElementType(), BI->getElementType()); - } - if (const ArrayType *AI = dyn_cast(A)) { - const ArrayType *BI = cast(B); - if (AI->getNumElements() != BI->getNumElements()) - return AI->getNumElements() < BI->getNumElements(); - return CompareTypes(AI->getElementType(), BI->getElementType()); - } - if (const VectorType *AI = dyn_cast(A)) { - const VectorType *BI = cast(B); - if (AI->getNumElements() != BI->getNumElements()) - return AI->getNumElements() < BI->getNumElements(); - return CompareTypes(AI->getElementType(), BI->getElementType()); - } - if (const StructType *AI = dyn_cast(A)) { - const StructType *BI = cast(B); - if (AI->getNumElements() != BI->getNumElements()) - return AI->getNumElements() < BI->getNumElements(); - for (unsigned i = 0, e = AI->getNumElements(); i != e; ++i) - if (CompareTypes(AI->getElementType(i), BI->getElementType(i)) || - CompareTypes(BI->getElementType(i), AI->getElementType(i))) - return CompareTypes(AI->getElementType(i), BI->getElementType(i)); - } - return false; -} - namespace { /// SCEVComplexityCompare - Return true if the complexity of the LHS is less /// than the complexity of the RHS. This comparator is used to canonicalize @@ -527,125 +428,167 @@ namespace { public: explicit SCEVComplexityCompare(const LoopInfo *li) : LI(li) {} + // Return true or false if LHS is less than, or at least RHS, respectively. bool operator()(const SCEV *LHS, const SCEV *RHS) const { + return compare(LHS, RHS) < 0; + } + + // Return negative, zero, or positive, if LHS is less than, equal to, or + // greater than RHS, respectively. A three-way result allows recursive + // comparisons to be more efficient. + int compare(const SCEV *LHS, const SCEV *RHS) const { // Fast-path: SCEVs are uniqued so we can do a quick equality check. if (LHS == RHS) - return false; + return 0; // Primarily, sort the SCEVs by their getSCEVType(). unsigned LType = LHS->getSCEVType(), RType = RHS->getSCEVType(); if (LType != RType) - return LType < RType; + return (int)LType - (int)RType; // Aside from the getSCEVType() ordering, the particular ordering // isn't very important except that it's beneficial to be consistent, // so that (a + b) and (b + a) don't end up as different expressions. - - // Sort SCEVUnknown values with some loose heuristics. TODO: This is - // not as complete as it could be. - if (const SCEVUnknown *LU = dyn_cast(LHS)) { + switch (LType) { + case scUnknown: { + const SCEVUnknown *LU = cast(LHS); const SCEVUnknown *RU = cast(RHS); + // Sort SCEVUnknown values with some loose heuristics. TODO: This is + // not as complete as it could be. + const Value *LV = LU->getValue(), *RV = RU->getValue(); + // Order pointer values after integer values. This helps SCEVExpander // form GEPs. - bool LIsPointer = LU->getType()->isPointerTy(), - RIsPointer = RU->getType()->isPointerTy(); + bool LIsPointer = LV->getType()->isPointerTy(), + RIsPointer = RV->getType()->isPointerTy(); if (LIsPointer != RIsPointer) - return RIsPointer; + return (int)LIsPointer - (int)RIsPointer; // Compare getValueID values. - unsigned LID = LU->getValue()->getValueID(), - RID = RU->getValue()->getValueID(); + unsigned LID = LV->getValueID(), + RID = RV->getValueID(); if (LID != RID) - return LID < RID; + return (int)LID - (int)RID; // Sort arguments by their position. - if (const Argument *LA = dyn_cast(LU->getValue())) { - const Argument *RA = cast(RU->getValue()); - return LA->getArgNo() < RA->getArgNo(); + if (const Argument *LA = dyn_cast(LV)) { + const Argument *RA = cast(RV); + unsigned LArgNo = LA->getArgNo(), RArgNo = RA->getArgNo(); + return (int)LArgNo - (int)RArgNo; } - // For instructions, compare their loop depth, and their opcode. - // This is pretty loose. - if (const Instruction *LV = dyn_cast(LU->getValue())) { - const Instruction *RV = cast(RU->getValue()); + // For instructions, compare their loop depth, and their operand + // count. This is pretty loose. + if (const Instruction *LInst = dyn_cast(LV)) { + const Instruction *RInst = cast(RV); // Compare loop depths. - unsigned LDepth = LI->getLoopDepth(LV->getParent()), - RDepth = LI->getLoopDepth(RV->getParent()); - if (LDepth != RDepth) - return LDepth < RDepth; + const BasicBlock *LParent = LInst->getParent(), + *RParent = RInst->getParent(); + if (LParent != RParent) { + unsigned LDepth = LI->getLoopDepth(LParent), + RDepth = LI->getLoopDepth(RParent); + if (LDepth != RDepth) + return (int)LDepth - (int)RDepth; + } // Compare the number of operands. - unsigned LNumOps = LV->getNumOperands(), - RNumOps = RV->getNumOperands(); - if (LNumOps != RNumOps) - return LNumOps < RNumOps; + unsigned LNumOps = LInst->getNumOperands(), + RNumOps = RInst->getNumOperands(); + return (int)LNumOps - (int)RNumOps; } - return false; + return 0; } - // Compare constant values. - if (const SCEVConstant *LC = dyn_cast(LHS)) { + case scConstant: { + const SCEVConstant *LC = cast(LHS); const SCEVConstant *RC = cast(RHS); - const ConstantInt *LCC = LC->getValue(); - const ConstantInt *RCC = RC->getValue(); - unsigned LBitWidth = LCC->getBitWidth(), RBitWidth = RCC->getBitWidth(); + + // Compare constant values. + const APInt &LA = LC->getValue()->getValue(); + const APInt &RA = RC->getValue()->getValue(); + unsigned LBitWidth = LA.getBitWidth(), RBitWidth = RA.getBitWidth(); if (LBitWidth != RBitWidth) - return LBitWidth < RBitWidth; - return LCC->getValue().ult(RCC->getValue()); + return (int)LBitWidth - (int)RBitWidth; + return LA.ult(RA) ? -1 : 1; } - // Compare addrec loop depths. - if (const SCEVAddRecExpr *LA = dyn_cast(LHS)) { + case scAddRecExpr: { + const SCEVAddRecExpr *LA = cast(LHS); const SCEVAddRecExpr *RA = cast(RHS); - unsigned LDepth = LA->getLoop()->getLoopDepth(), - RDepth = RA->getLoop()->getLoopDepth(); - if (LDepth != RDepth) - return LDepth < RDepth; + + // Compare addrec loop depths. + const Loop *LLoop = LA->getLoop(), *RLoop = RA->getLoop(); + if (LLoop != RLoop) { + unsigned LDepth = LLoop->getLoopDepth(), + RDepth = RLoop->getLoopDepth(); + if (LDepth != RDepth) + return (int)LDepth - (int)RDepth; + } + + // Addrec complexity grows with operand count. + unsigned LNumOps = LA->getNumOperands(), RNumOps = RA->getNumOperands(); + if (LNumOps != RNumOps) + return (int)LNumOps - (int)RNumOps; + + // Lexicographically compare. + for (unsigned i = 0; i != LNumOps; ++i) { + long X = compare(LA->getOperand(i), RA->getOperand(i)); + if (X != 0) + return X; + } + + return 0; } - // Lexicographically compare n-ary expressions. - if (const SCEVNAryExpr *LC = dyn_cast(LHS)) { + case scAddExpr: + case scMulExpr: + case scSMaxExpr: + case scUMaxExpr: { + const SCEVNAryExpr *LC = cast(LHS); const SCEVNAryExpr *RC = cast(RHS); + + // Lexicographically compare n-ary expressions. unsigned LNumOps = LC->getNumOperands(), RNumOps = RC->getNumOperands(); for (unsigned i = 0; i != LNumOps; ++i) { if (i >= RNumOps) - return false; - const SCEV *LOp = LC->getOperand(i), *ROp = RC->getOperand(i); - if (operator()(LOp, ROp)) - return true; - if (operator()(ROp, LOp)) - return false; + return 1; + long X = compare(LC->getOperand(i), RC->getOperand(i)); + if (X != 0) + return X; } - return LNumOps < RNumOps; + return (int)LNumOps - (int)RNumOps; } - // Lexicographically compare udiv expressions. - if (const SCEVUDivExpr *LC = dyn_cast(LHS)) { + case scUDivExpr: { + const SCEVUDivExpr *LC = cast(LHS); const SCEVUDivExpr *RC = cast(RHS); - const SCEV *LL = LC->getLHS(), *LR = LC->getRHS(), - *RL = RC->getLHS(), *RR = RC->getRHS(); - if (operator()(LL, RL)) - return true; - if (operator()(RL, LL)) - return false; - if (operator()(LR, RR)) - return true; - if (operator()(RR, LR)) - return false; - return false; + + // Lexicographically compare udiv expressions. + long X = compare(LC->getLHS(), RC->getLHS()); + if (X != 0) + return X; + return compare(LC->getRHS(), RC->getRHS()); } - // Compare cast expressions by operand. - if (const SCEVCastExpr *LC = dyn_cast(LHS)) { + case scTruncate: + case scZeroExtend: + case scSignExtend: { + const SCEVCastExpr *LC = cast(LHS); const SCEVCastExpr *RC = cast(RHS); - return operator()(LC->getOperand(), RC->getOperand()); + + // Compare cast expressions by operand. + return compare(LC->getOperand(), RC->getOperand()); + } + + default: + break; } llvm_unreachable("Unknown SCEV kind!"); - return false; + return 0; } }; } @@ -666,8 +609,9 @@ static void GroupByComplexity(SmallVectorImpl &Ops, if (Ops.size() == 2) { // This is the common case, which also happens to be trivially simple. // Special case it. - if (SCEVComplexityCompare(LI)(Ops[1], Ops[0])) - std::swap(Ops[0], Ops[1]); + const SCEV *&LHS = Ops[0], *&RHS = Ops[1]; + if (SCEVComplexityCompare(LI)(RHS, LHS)) + std::swap(LHS, RHS); return; } @@ -875,6 +819,36 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, if (const SCEVZeroExtendExpr *SZ = dyn_cast(Op)) return getTruncateOrZeroExtend(SZ->getOperand(), Ty); + // trunc(x1+x2+...+xN) --> trunc(x1)+trunc(x2)+...+trunc(xN) if we can + // eliminate all the truncates. + if (const SCEVAddExpr *SA = dyn_cast(Op)) { + SmallVector Operands; + bool hasTrunc = false; + for (unsigned i = 0, e = SA->getNumOperands(); i != e && !hasTrunc; ++i) { + const SCEV *S = getTruncateExpr(SA->getOperand(i), Ty); + hasTrunc = isa(S); + Operands.push_back(S); + } + if (!hasTrunc) + return getAddExpr(Operands, false, false); + UniqueSCEVs.FindNodeOrInsertPos(ID, IP); // Mutates IP, returns NULL. + } + + // trunc(x1*x2*...*xN) --> trunc(x1)*trunc(x2)*...*trunc(xN) if we can + // eliminate all the truncates. + if (const SCEVMulExpr *SM = dyn_cast(Op)) { + SmallVector Operands; + bool hasTrunc = false; + for (unsigned i = 0, e = SM->getNumOperands(); i != e && !hasTrunc; ++i) { + const SCEV *S = getTruncateExpr(SM->getOperand(i), Ty); + hasTrunc = isa(S); + Operands.push_back(S); + } + if (!hasTrunc) + return getMulExpr(Operands, false, false); + UniqueSCEVs.FindNodeOrInsertPos(ID, IP); // Mutates IP, returns NULL. + } + // If the input value is a chrec scev, truncate the chrec's operands. if (const SCEVAddRecExpr *AddRec = dyn_cast(Op)) { SmallVector Operands; @@ -926,6 +900,19 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + // zext(trunc(x)) --> zext(x) or x or trunc(x) + if (const SCEVTruncateExpr *ST = dyn_cast(Op)) { + // It's possible the bits taken off by the truncate were all zero bits. If + // so, we should be able to simplify this further. + const SCEV *X = ST->getOperand(); + ConstantRange CR = getUnsignedRange(X); + unsigned TruncBits = getTypeSizeInBits(ST->getType()); + unsigned NewBits = getTypeSizeInBits(Ty); + if (CR.truncate(TruncBits).zeroExtend(NewBits).contains( + CR.zextOrTrunc(NewBits))) + return getTruncateOrZeroExtend(X, Ty); + } + // If the input value is a chrec scev, and we can prove that the value // did not overflow the old, smaller, value, we can zero extend all of the // operands (often constants). This allows analysis of something like @@ -1050,6 +1037,10 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, if (const SCEVSignExtendExpr *SS = dyn_cast(Op)) return getSignExtendExpr(SS->getOperand(), Ty); + // sext(zext(x)) --> zext(x) + if (const SCEVZeroExtendExpr *SZ = dyn_cast(Op)) + return getZeroExtendExpr(SZ->getOperand(), Ty); + // Before doing any expensive analysis, check to see if we've already // computed a SCEV for this Op and Ty. FoldingSetNodeID ID; @@ -1059,6 +1050,23 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + // If the input value is provably positive, build a zext instead. + if (isKnownNonNegative(Op)) + return getZeroExtendExpr(Op, Ty); + + // sext(trunc(x)) --> sext(x) or x or trunc(x) + if (const SCEVTruncateExpr *ST = dyn_cast(Op)) { + // It's possible the bits taken off by the truncate were all sign bits. If + // so, we should be able to simplify this further. + const SCEV *X = ST->getOperand(); + ConstantRange CR = getSignedRange(X); + unsigned TruncBits = getTypeSizeInBits(ST->getType()); + unsigned NewBits = getTypeSizeInBits(Ty); + if (CR.truncate(TruncBits).signExtend(NewBits).contains( + CR.sextOrTrunc(NewBits))) + return getTruncateOrSignExtend(X, Ty); + } + // If the input value is a chrec scev, and we can prove that the value // did not overflow the old, smaller, value, we can sign extend all of the // operands (often constants). This allows analysis of something like @@ -1339,8 +1347,9 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, // If HasNSW is true and all the operands are non-negative, infer HasNUW. if (!HasNUW && HasNSW) { bool All = true; - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - if (!isKnownNonNegative(Ops[i])) { + for (SmallVectorImpl::const_iterator I = Ops.begin(), + E = Ops.end(); I != E; ++I) + if (!isKnownNonNegative(*I)) { All = false; break; } @@ -1373,22 +1382,25 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, if (Ops.size() == 1) return Ops[0]; } - // Okay, check to see if the same value occurs in the operand list twice. If - // so, merge them together into an multiply expression. Since we sorted the - // list, these values are required to be adjacent. + // Okay, check to see if the same value occurs in the operand list more than + // once. If so, merge them together into an multiply expression. Since we + // sorted the list, these values are required to be adjacent. const Type *Ty = Ops[0]->getType(); bool FoundMatch = false; - for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) + for (unsigned i = 0, e = Ops.size(); i != e-1; ++i) if (Ops[i] == Ops[i+1]) { // X + Y + Y --> X + Y*2 - // Found a match, merge the two values into a multiply, and add any - // remaining values to the result. - const SCEV *Two = getConstant(Ty, 2); - const SCEV *Mul = getMulExpr(Two, Ops[i]); - if (Ops.size() == 2) + // Scan ahead to count how many equal operands there are. + unsigned Count = 2; + while (i+Count != e && Ops[i+Count] == Ops[i]) + ++Count; + // Merge the values into a multiply. + const SCEV *Scale = getConstant(Ty, Count); + const SCEV *Mul = getMulExpr(Scale, Ops[i]); + if (Ops.size() == Count) return Mul; Ops[i] = Mul; - Ops.erase(Ops.begin()+i+1); - --i; --e; + Ops.erase(Ops.begin()+i+1, Ops.begin()+i+Count); + --i; e -= Count - 1; FoundMatch = true; } if (FoundMatch) @@ -1489,7 +1501,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, // re-generate the operands list. Group the operands by constant scale, // to avoid multiplying by the same constant scale multiple times. std::map, APIntCompare> MulOpLists; - for (SmallVector::iterator I = NewOps.begin(), + for (SmallVector::const_iterator I = NewOps.begin(), E = NewOps.end(); I != E; ++I) MulOpLists[M.find(*I)->second].push_back(*I); // Re-generate the operands list. @@ -1525,8 +1537,9 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, if (Mul->getNumOperands() != 2) { // If the multiply has more than two operands, we must get the // Y*Z term. - SmallVector MulOps(Mul->op_begin(), Mul->op_end()); - MulOps.erase(MulOps.begin()+MulOp); + SmallVector MulOps(Mul->op_begin(), + Mul->op_begin()+MulOp); + MulOps.append(Mul->op_begin()+MulOp+1, Mul->op_end()); InnerMul = getMulExpr(MulOps); } const SCEV *One = getConstant(Ty, 1); @@ -1545,7 +1558,6 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, } // Check this multiply against other multiplies being added together. - bool AnyFold = false; for (unsigned OtherMulIdx = Idx+1; OtherMulIdx < Ops.size() && isa(Ops[OtherMulIdx]); ++OtherMulIdx) { @@ -1559,28 +1571,26 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, const SCEV *InnerMul1 = Mul->getOperand(MulOp == 0); if (Mul->getNumOperands() != 2) { SmallVector MulOps(Mul->op_begin(), - Mul->op_end()); - MulOps.erase(MulOps.begin()+MulOp); + Mul->op_begin()+MulOp); + MulOps.append(Mul->op_begin()+MulOp+1, Mul->op_end()); InnerMul1 = getMulExpr(MulOps); } const SCEV *InnerMul2 = OtherMul->getOperand(OMulOp == 0); if (OtherMul->getNumOperands() != 2) { SmallVector MulOps(OtherMul->op_begin(), - OtherMul->op_end()); - MulOps.erase(MulOps.begin()+OMulOp); + OtherMul->op_begin()+OMulOp); + MulOps.append(OtherMul->op_begin()+OMulOp+1, OtherMul->op_end()); InnerMul2 = getMulExpr(MulOps); } const SCEV *InnerMulSum = getAddExpr(InnerMul1,InnerMul2); const SCEV *OuterMul = getMulExpr(MulOpSCEV, InnerMulSum); if (Ops.size() == 2) return OuterMul; - Ops[Idx] = OuterMul; - Ops.erase(Ops.begin()+OtherMulIdx); - OtherMulIdx = Idx; - AnyFold = true; + Ops.erase(Ops.begin()+Idx); + Ops.erase(Ops.begin()+OtherMulIdx-1); + Ops.push_back(OuterMul); + return getAddExpr(Ops); } } - if (AnyFold) - return getAddExpr(Ops); } } @@ -1598,7 +1608,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, const SCEVAddRecExpr *AddRec = cast(Ops[Idx]); const Loop *AddRecLoop = AddRec->getLoop(); for (unsigned i = 0, e = Ops.size(); i != e; ++i) - if (Ops[i]->isLoopInvariant(AddRecLoop)) { + if (isLoopInvariant(Ops[i], AddRecLoop)) { LIOps.push_back(Ops[i]); Ops.erase(Ops.begin()+i); --i; --e; @@ -1635,30 +1645,31 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, // there are multiple AddRec's with the same loop induction variable being // added together. If so, we can fold them. for (unsigned OtherIdx = Idx+1; - OtherIdx < Ops.size() && isa(Ops[OtherIdx]);++OtherIdx) - if (OtherIdx != Idx) { - const SCEVAddRecExpr *OtherAddRec = cast(Ops[OtherIdx]); - if (AddRecLoop == OtherAddRec->getLoop()) { - // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D} - SmallVector NewOps(AddRec->op_begin(), - AddRec->op_end()); - for (unsigned i = 0, e = OtherAddRec->getNumOperands(); i != e; ++i) { - if (i >= NewOps.size()) { - NewOps.append(OtherAddRec->op_begin()+i, - OtherAddRec->op_end()); - break; + OtherIdx < Ops.size() && isa(Ops[OtherIdx]); + ++OtherIdx) + if (AddRecLoop == cast(Ops[OtherIdx])->getLoop()) { + // Other + {A,+,B} + {C,+,D} --> Other + {A+C,+,B+D} + SmallVector AddRecOps(AddRec->op_begin(), + AddRec->op_end()); + for (; OtherIdx != Ops.size() && isa(Ops[OtherIdx]); + ++OtherIdx) + if (const SCEVAddRecExpr *OtherAddRec = + dyn_cast(Ops[OtherIdx])) + if (OtherAddRec->getLoop() == AddRecLoop) { + for (unsigned i = 0, e = OtherAddRec->getNumOperands(); + i != e; ++i) { + if (i >= AddRecOps.size()) { + AddRecOps.append(OtherAddRec->op_begin()+i, + OtherAddRec->op_end()); + break; + } + AddRecOps[i] = getAddExpr(AddRecOps[i], + OtherAddRec->getOperand(i)); + } + Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; } - NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i)); - } - const SCEV *NewAddRec = getAddRecExpr(NewOps, AddRecLoop); - - if (Ops.size() == 2) return NewAddRec; - - Ops.erase(Ops.begin()+Idx); - Ops.erase(Ops.begin()+OtherIdx-1); - Ops.push_back(NewAddRec); - return getAddExpr(Ops); - } + Ops[Idx] = getAddRecExpr(AddRecOps, AddRecLoop); + return getAddExpr(Ops); } // Otherwise couldn't fold anything into this recurrence. Move onto the @@ -1669,7 +1680,6 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, // already have one, otherwise create a new one. FoldingSetNodeID ID; ID.AddInteger(scAddExpr); - ID.AddInteger(Ops.size()); for (unsigned i = 0, e = Ops.size(); i != e; ++i) ID.AddPointer(Ops[i]); void *IP = 0; @@ -1694,17 +1704,18 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops, assert(!Ops.empty() && "Cannot get empty mul!"); if (Ops.size() == 1) return Ops[0]; #ifndef NDEBUG + const Type *ETy = getEffectiveSCEVType(Ops[0]->getType()); for (unsigned i = 1, e = Ops.size(); i != e; ++i) - assert(getEffectiveSCEVType(Ops[i]->getType()) == - getEffectiveSCEVType(Ops[0]->getType()) && + assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy && "SCEVMulExpr operand types don't match!"); #endif // If HasNSW is true and all the operands are non-negative, infer HasNUW. if (!HasNUW && HasNSW) { bool All = true; - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - if (!isKnownNonNegative(Ops[i])) { + for (SmallVectorImpl::const_iterator I = Ops.begin(), + E = Ops.end(); I != E; ++I) + if (!isKnownNonNegative(*I)) { All = false; break; } @@ -1801,8 +1812,9 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops, // they are loop invariant w.r.t. the recurrence. SmallVector LIOps; const SCEVAddRecExpr *AddRec = cast(Ops[Idx]); + const Loop *AddRecLoop = AddRec->getLoop(); for (unsigned i = 0, e = Ops.size(); i != e; ++i) - if (Ops[i]->isLoopInvariant(AddRec->getLoop())) { + if (isLoopInvariant(Ops[i], AddRecLoop)) { LIOps.push_back(Ops[i]); Ops.erase(Ops.begin()+i); --i; --e; @@ -1819,7 +1831,7 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops, // Build the new addrec. Propagate the NUW and NSW flags if both the // outer mul and the inner addrec are guaranteed to have no overflow. - const SCEV *NewRec = getAddRecExpr(NewOps, AddRec->getLoop(), + const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, HasNUW && AddRec->hasNoUnsignedWrap(), HasNSW && AddRec->hasNoSignedWrap()); @@ -1839,28 +1851,30 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops, // there are multiple AddRec's with the same loop induction variable being // multiplied together. If so, we can fold them. for (unsigned OtherIdx = Idx+1; - OtherIdx < Ops.size() && isa(Ops[OtherIdx]);++OtherIdx) - if (OtherIdx != Idx) { - const SCEVAddRecExpr *OtherAddRec = cast(Ops[OtherIdx]); - if (AddRec->getLoop() == OtherAddRec->getLoop()) { - // F * G --> {A,+,B} * {C,+,D} --> {A*C,+,F*D + G*B + B*D} - const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec; - const SCEV *NewStart = getMulExpr(F->getStart(), - G->getStart()); - const SCEV *B = F->getStepRecurrence(*this); - const SCEV *D = G->getStepRecurrence(*this); - const SCEV *NewStep = getAddExpr(getMulExpr(F, D), - getMulExpr(G, B), - getMulExpr(B, D)); - const SCEV *NewAddRec = getAddRecExpr(NewStart, NewStep, - F->getLoop()); - if (Ops.size() == 2) return NewAddRec; - - Ops.erase(Ops.begin()+Idx); - Ops.erase(Ops.begin()+OtherIdx-1); - Ops.push_back(NewAddRec); - return getMulExpr(Ops); - } + OtherIdx < Ops.size() && isa(Ops[OtherIdx]); + ++OtherIdx) + if (AddRecLoop == cast(Ops[OtherIdx])->getLoop()) { + // F * G, where F = {A,+,B} and G = {C,+,D} --> + // {A*C,+,F*D + G*B + B*D} + for (; OtherIdx != Ops.size() && isa(Ops[OtherIdx]); + ++OtherIdx) + if (const SCEVAddRecExpr *OtherAddRec = + dyn_cast(Ops[OtherIdx])) + if (OtherAddRec->getLoop() == AddRecLoop) { + const SCEVAddRecExpr *F = AddRec, *G = OtherAddRec; + const SCEV *NewStart = getMulExpr(F->getStart(), G->getStart()); + const SCEV *B = F->getStepRecurrence(*this); + const SCEV *D = G->getStepRecurrence(*this); + const SCEV *NewStep = getAddExpr(getMulExpr(F, D), + getMulExpr(G, B), + getMulExpr(B, D)); + const SCEV *NewAddRec = getAddRecExpr(NewStart, NewStep, + F->getLoop()); + if (Ops.size() == 2) return NewAddRec; + Ops[Idx] = AddRec = cast(NewAddRec); + Ops.erase(Ops.begin() + OtherIdx); --OtherIdx; + } + return getMulExpr(Ops); } // Otherwise couldn't fold anything into this recurrence. Move onto the @@ -1871,7 +1885,6 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops, // already have one, otherwise create a new one. FoldingSetNodeID ID; ID.AddInteger(scMulExpr); - ID.AddInteger(Ops.size()); for (unsigned i = 0, e = Ops.size(); i != e; ++i) ID.AddPointer(Ops[i]); void *IP = 0; @@ -2016,10 +2029,13 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, bool HasNUW, bool HasNSW) { if (Operands.size() == 1) return Operands[0]; #ifndef NDEBUG + const Type *ETy = getEffectiveSCEVType(Operands[0]->getType()); for (unsigned i = 1, e = Operands.size(); i != e; ++i) - assert(getEffectiveSCEVType(Operands[i]->getType()) == - getEffectiveSCEVType(Operands[0]->getType()) && + assert(getEffectiveSCEVType(Operands[i]->getType()) == ETy && "SCEVAddRecExpr operand types don't match!"); + for (unsigned i = 0, e = Operands.size(); i != e; ++i) + assert(isLoopInvariant(Operands[i], L) && + "SCEVAddRecExpr operand is not loop-invariant!"); #endif if (Operands.back()->isZero()) { @@ -2036,8 +2052,9 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, // If HasNSW is true and all the operands are non-negative, infer HasNUW. if (!HasNUW && HasNSW) { bool All = true; - for (unsigned i = 0, e = Operands.size(); i != e; ++i) - if (!isKnownNonNegative(Operands[i])) { + for (SmallVectorImpl::const_iterator I = Operands.begin(), + E = Operands.end(); I != E; ++I) + if (!isKnownNonNegative(*I)) { All = false; break; } @@ -2047,9 +2064,9 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, // Canonicalize nested AddRecs in by nesting them in order of loop depth. if (const SCEVAddRecExpr *NestedAR = dyn_cast(Operands[0])) { const Loop *NestedLoop = NestedAR->getLoop(); - if (L->contains(NestedLoop->getHeader()) ? + if (L->contains(NestedLoop) ? (L->getLoopDepth() < NestedLoop->getLoopDepth()) : - (!NestedLoop->contains(L->getHeader()) && + (!NestedLoop->contains(L) && DT->dominates(L->getHeader(), NestedLoop->getHeader()))) { SmallVector NestedOperands(NestedAR->op_begin(), NestedAR->op_end()); @@ -2059,7 +2076,7 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, // requirement. bool AllInvariant = true; for (unsigned i = 0, e = Operands.size(); i != e; ++i) - if (!Operands[i]->isLoopInvariant(L)) { + if (!isLoopInvariant(Operands[i], L)) { AllInvariant = false; break; } @@ -2067,7 +2084,7 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, NestedOperands[0] = getAddRecExpr(Operands, L); AllInvariant = true; for (unsigned i = 0, e = NestedOperands.size(); i != e; ++i) - if (!NestedOperands[i]->isLoopInvariant(NestedLoop)) { + if (!isLoopInvariant(NestedOperands[i], NestedLoop)) { AllInvariant = false; break; } @@ -2084,7 +2101,6 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, // already have one, otherwise create a new one. FoldingSetNodeID ID; ID.AddInteger(scAddRecExpr); - ID.AddInteger(Operands.size()); for (unsigned i = 0, e = Operands.size(); i != e; ++i) ID.AddPointer(Operands[i]); ID.AddPointer(L); @@ -2116,9 +2132,9 @@ ScalarEvolution::getSMaxExpr(SmallVectorImpl &Ops) { assert(!Ops.empty() && "Cannot get empty smax!"); if (Ops.size() == 1) return Ops[0]; #ifndef NDEBUG + const Type *ETy = getEffectiveSCEVType(Ops[0]->getType()); for (unsigned i = 1, e = Ops.size(); i != e; ++i) - assert(getEffectiveSCEVType(Ops[i]->getType()) == - getEffectiveSCEVType(Ops[0]->getType()) && + assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy && "SCEVSMaxExpr operand types don't match!"); #endif @@ -2195,7 +2211,6 @@ ScalarEvolution::getSMaxExpr(SmallVectorImpl &Ops) { // already have one, otherwise create a new one. FoldingSetNodeID ID; ID.AddInteger(scSMaxExpr); - ID.AddInteger(Ops.size()); for (unsigned i = 0, e = Ops.size(); i != e; ++i) ID.AddPointer(Ops[i]); void *IP = 0; @@ -2221,9 +2236,9 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl &Ops) { assert(!Ops.empty() && "Cannot get empty umax!"); if (Ops.size() == 1) return Ops[0]; #ifndef NDEBUG + const Type *ETy = getEffectiveSCEVType(Ops[0]->getType()); for (unsigned i = 1, e = Ops.size(); i != e; ++i) - assert(getEffectiveSCEVType(Ops[i]->getType()) == - getEffectiveSCEVType(Ops[0]->getType()) && + assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy && "SCEVUMaxExpr operand types don't match!"); #endif @@ -2300,7 +2315,6 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl &Ops) { // already have one, otherwise create a new one. FoldingSetNodeID ID; ID.AddInteger(scUMaxExpr); - ID.AddInteger(Ops.size()); for (unsigned i = 0, e = Ops.size(); i != e; ++i) ID.AddPointer(Ops[i]); void *IP = 0; @@ -2458,10 +2472,15 @@ const SCEV *ScalarEvolution::getCouldNotCompute() { const SCEV *ScalarEvolution::getSCEV(Value *V) { assert(isSCEVable(V->getType()) && "Value is not SCEVable!"); - std::map::iterator I = Scalars.find(V); - if (I != Scalars.end()) return I->second; + ValueExprMapType::const_iterator I = ValueExprMap.find(V); + if (I != ValueExprMap.end()) return I->second; const SCEV *S = createSCEV(V); - Scalars.insert(std::make_pair(SCEVCallbackVH(V, this), S)); + + // The process of creating a SCEV for V may have caused other SCEVs + // to have been created, so it's necessary to insert the new entry + // from scratch, rather than trying to remember the insert position + // above. + ValueExprMap.insert(std::make_pair(SCEVCallbackVH(V, this), S)); return S; } @@ -2491,24 +2510,24 @@ const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { return getMinusSCEV(AllOnes, V); } -/// getMinusSCEV - Return a SCEV corresponding to LHS - RHS. -/// -const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, - const SCEV *RHS) { +/// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1, +/// and thus the HasNUW and HasNSW bits apply to the resultant add, not +/// whether the sub would have overflowed. +const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS, + bool HasNUW, bool HasNSW) { // Fast path: X - X --> 0. if (LHS == RHS) return getConstant(LHS->getType(), 0); // X - Y --> X + -Y - return getAddExpr(LHS, getNegativeSCEV(RHS)); + return getAddExpr(LHS, getNegativeSCEV(RHS), HasNUW, HasNSW); } /// 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. const SCEV * -ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, - const Type *Ty) { +ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, const Type *Ty) { const Type *SrcTy = V->getType(); assert((SrcTy->isIntegerTy() || SrcTy->isPointerTy()) && (Ty->isIntegerTy() || Ty->isPointerTy()) && @@ -2646,7 +2665,7 @@ PushDefUseChildren(Instruction *I, /// ForgetSymbolicValue - This looks up computed SCEV values for all /// instructions that depend on the given instruction and removes them from -/// the Scalars map if they reference SymName. This is used during PHI +/// the ValueExprMapType map if they reference SymName. This is used during PHI /// resolution. void ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) { @@ -2659,12 +2678,14 @@ ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) { Instruction *I = Worklist.pop_back_val(); if (!Visited.insert(I)) continue; - std::map::iterator It = - Scalars.find(static_cast(I)); - if (It != Scalars.end()) { + ValueExprMapType::iterator It = + ValueExprMap.find(static_cast(I)); + if (It != ValueExprMap.end()) { + const SCEV *Old = It->second; + // Short-circuit the def-use traversal if the symbolic name // ceases to appear in expressions. - if (It->second != SymName && !It->second->hasOperand(SymName)) + if (Old != SymName && !hasOperand(Old, SymName)) continue; // SCEVUnknown for a PHI either means that it has an unrecognized @@ -2675,10 +2696,10 @@ ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) { // updates on its own when it gets to that point. In the third, we do // want to forget the SCEVUnknown. if (!isa(I) || - !isa(It->second) || - (I != PN && It->second == SymName)) { - ValuesAtScopes.erase(It->second); - Scalars.erase(It); + !isa(Old) || + (I != PN && Old == SymName)) { + forgetMemoizedResults(Old); + ValueExprMap.erase(It); } } @@ -2715,9 +2736,9 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { if (BEValueV && StartValueV) { // While we are analyzing this PHI node, handle its value symbolically. const SCEV *SymbolicName = getUnknown(PN); - assert(Scalars.find(PN) == Scalars.end() && + assert(ValueExprMap.find(PN) == ValueExprMap.end() && "PHI node already processed?"); - Scalars.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName)); + ValueExprMap.insert(std::make_pair(SCEVCallbackVH(PN, this), SymbolicName)); // Using this symbolic name for the PHI, analyze the value coming around // the back-edge. @@ -2749,7 +2770,7 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { // This is not a valid addrec if the step amount is varying each // loop iteration, but is not itself an addrec in this loop. - if (Accum->isLoopInvariant(L) || + if (isLoopInvariant(Accum, L) || (isa(Accum) && cast(Accum)->getLoop() == L)) { bool HasNUW = false; @@ -2762,6 +2783,23 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { HasNUW = true; if (OBO->hasNoSignedWrap()) HasNSW = true; + } else if (const GEPOperator *GEP = + dyn_cast(BEValueV)) { + // If the increment is a GEP, then we know it won't perform a + // signed overflow, because the address space cannot be + // wrapped around. + // + // NOTE: This isn't strictly true, because you could have an + // object straddling the 2G address boundary in a 32-bit address + // space (for example). We really want to model this as a "has + // no signed/unsigned wrap" where the base pointer is treated as + // unsigned and the increment is known to not have signed + // wrapping. + // + // This is a highly theoretical concern though, and this is good + // enough for all cases we know of at this point. :) + // + HasNSW |= GEP->isInBounds(); } const SCEV *StartVal = getSCEV(StartValueV); @@ -2770,7 +2808,7 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { // Since the no-wrap flags are on the increment, they apply to the // post-incremented value as well. - if (Accum->isLoopInvariant(L)) + if (isLoopInvariant(Accum, L)) (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, HasNUW, HasNSW); @@ -2778,7 +2816,7 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { // to be symbolic. We now need to go back and purge all of the // entries for the scalars that use the symbolic expression. ForgetSymbolicName(PN, SymbolicName); - Scalars[SCEVCallbackVH(PN, this)] = PHISCEV; + ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV; return PHISCEV; } } @@ -2803,7 +2841,7 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { // to be symbolic. We now need to go back and purge all of the // entries for the scalars that use the symbolic expression. ForgetSymbolicName(PN, SymbolicName); - Scalars[SCEVCallbackVH(PN, this)] = PHISCEV; + ValueExprMap[SCEVCallbackVH(PN, this)] = PHISCEV; return PHISCEV; } } @@ -2815,17 +2853,9 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { // PHI's incoming blocks are in a different loop, in which case doing so // risks breaking LCSSA form. Instcombine would normally zap these, but // it doesn't have DominatorTree information, so it may miss cases. - if (Value *V = PN->hasConstantValue(DT)) { - bool AllSameLoop = true; - Loop *PNLoop = LI->getLoopFor(PN->getParent()); - for (size_t i = 0, e = PN->getNumIncomingValues(); i != e; ++i) - if (LI->getLoopFor(PN->getIncomingBlock(i)) != PNLoop) { - AllSameLoop = false; - break; - } - if (AllSameLoop) + if (Value *V = SimplifyInstruction(PN, TD, DT)) + if (LI->replacementPreservesLCSSAForm(PN, V)) return getSCEV(V); - } // If it's not a loop phi, we can't handle it yet. return getUnknown(PN); @@ -2840,6 +2870,7 @@ const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { // Add expression, because the Instruction may be guarded by control flow // and the no-overflow bits may not be valid for the expression in any // context. + bool isInBounds = GEP->isInBounds(); const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType()); Value *Base = GEP->getOperand(0); @@ -2868,7 +2899,8 @@ const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { IndexS = getTruncateOrSignExtend(IndexS, IntPtrTy); // Multiply the index by the element size to compute the element offset. - const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize); + const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize, /*NUW*/ false, + /*NSW*/ isInBounds); // Add the element offset to the running total offset. TotalOffset = getAddExpr(TotalOffset, LocalOffset); @@ -2879,7 +2911,8 @@ const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { const SCEV *BaseS = getSCEV(Base); // Add the total offset from all the GEP indices to the base. - return getAddExpr(BaseS, TotalOffset); + return getAddExpr(BaseS, TotalOffset, /*NUW*/ false, + /*NSW*/ isInBounds); } /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is @@ -2967,9 +3000,13 @@ ScalarEvolution::GetMinTrailingZeros(const SCEV *S) { /// ConstantRange ScalarEvolution::getUnsignedRange(const SCEV *S) { + // See if we've computed this range already. + DenseMap::iterator I = UnsignedRanges.find(S); + if (I != UnsignedRanges.end()) + return I->second; if (const SCEVConstant *C = dyn_cast(S)) - return ConstantRange(C->getValue()->getValue()); + return setUnsignedRange(C, ConstantRange(C->getValue()->getValue())); unsigned BitWidth = getTypeSizeInBits(S->getType()); ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true); @@ -2986,49 +3023,52 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { ConstantRange X = getUnsignedRange(Add->getOperand(0)); for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) X = X.add(getUnsignedRange(Add->getOperand(i))); - return ConservativeResult.intersectWith(X); + return setUnsignedRange(Add, ConservativeResult.intersectWith(X)); } if (const SCEVMulExpr *Mul = dyn_cast(S)) { ConstantRange X = getUnsignedRange(Mul->getOperand(0)); for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) X = X.multiply(getUnsignedRange(Mul->getOperand(i))); - return ConservativeResult.intersectWith(X); + return setUnsignedRange(Mul, ConservativeResult.intersectWith(X)); } if (const SCEVSMaxExpr *SMax = dyn_cast(S)) { ConstantRange X = getUnsignedRange(SMax->getOperand(0)); for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i) X = X.smax(getUnsignedRange(SMax->getOperand(i))); - return ConservativeResult.intersectWith(X); + return setUnsignedRange(SMax, ConservativeResult.intersectWith(X)); } if (const SCEVUMaxExpr *UMax = dyn_cast(S)) { ConstantRange X = getUnsignedRange(UMax->getOperand(0)); for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i) X = X.umax(getUnsignedRange(UMax->getOperand(i))); - return ConservativeResult.intersectWith(X); + return setUnsignedRange(UMax, ConservativeResult.intersectWith(X)); } if (const SCEVUDivExpr *UDiv = dyn_cast(S)) { ConstantRange X = getUnsignedRange(UDiv->getLHS()); ConstantRange Y = getUnsignedRange(UDiv->getRHS()); - return ConservativeResult.intersectWith(X.udiv(Y)); + return setUnsignedRange(UDiv, ConservativeResult.intersectWith(X.udiv(Y))); } if (const SCEVZeroExtendExpr *ZExt = dyn_cast(S)) { ConstantRange X = getUnsignedRange(ZExt->getOperand()); - return ConservativeResult.intersectWith(X.zeroExtend(BitWidth)); + return setUnsignedRange(ZExt, + ConservativeResult.intersectWith(X.zeroExtend(BitWidth))); } if (const SCEVSignExtendExpr *SExt = dyn_cast(S)) { ConstantRange X = getUnsignedRange(SExt->getOperand()); - return ConservativeResult.intersectWith(X.signExtend(BitWidth)); + return setUnsignedRange(SExt, + ConservativeResult.intersectWith(X.signExtend(BitWidth))); } if (const SCEVTruncateExpr *Trunc = dyn_cast(S)) { ConstantRange X = getUnsignedRange(Trunc->getOperand()); - return ConservativeResult.intersectWith(X.truncate(BitWidth)); + return setUnsignedRange(Trunc, + ConservativeResult.intersectWith(X.truncate(BitWidth))); } if (const SCEVAddRecExpr *AddRec = dyn_cast(S)) { @@ -3068,19 +3108,20 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { ConstantRange ExtEndRange = EndRange.zextOrTrunc(BitWidth*2+1); if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) != ExtEndRange) - return ConservativeResult; + return setUnsignedRange(AddRec, ConservativeResult); APInt Min = APIntOps::umin(StartRange.getUnsignedMin(), EndRange.getUnsignedMin()); APInt Max = APIntOps::umax(StartRange.getUnsignedMax(), EndRange.getUnsignedMax()); if (Min.isMinValue() && Max.isMaxValue()) - return ConservativeResult; - return ConservativeResult.intersectWith(ConstantRange(Min, Max+1)); + return setUnsignedRange(AddRec, ConservativeResult); + return setUnsignedRange(AddRec, + ConservativeResult.intersectWith(ConstantRange(Min, Max+1))); } } - return ConservativeResult; + return setUnsignedRange(AddRec, ConservativeResult); } if (const SCEVUnknown *U = dyn_cast(S)) { @@ -3089,20 +3130,25 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { APInt Zeros(BitWidth, 0), Ones(BitWidth, 0); ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones, TD); if (Ones == ~Zeros + 1) - return ConservativeResult; - return ConservativeResult.intersectWith(ConstantRange(Ones, ~Zeros + 1)); + return setUnsignedRange(U, ConservativeResult); + return setUnsignedRange(U, + ConservativeResult.intersectWith(ConstantRange(Ones, ~Zeros + 1))); } - return ConservativeResult; + return setUnsignedRange(S, ConservativeResult); } /// getSignedRange - Determine the signed range for a particular SCEV. /// ConstantRange ScalarEvolution::getSignedRange(const SCEV *S) { + // See if we've computed this range already. + DenseMap::iterator I = SignedRanges.find(S); + if (I != SignedRanges.end()) + return I->second; if (const SCEVConstant *C = dyn_cast(S)) - return ConstantRange(C->getValue()->getValue()); + return setSignedRange(C, ConstantRange(C->getValue()->getValue())); unsigned BitWidth = getTypeSizeInBits(S->getType()); ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true); @@ -3119,49 +3165,52 @@ ScalarEvolution::getSignedRange(const SCEV *S) { ConstantRange X = getSignedRange(Add->getOperand(0)); for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) X = X.add(getSignedRange(Add->getOperand(i))); - return ConservativeResult.intersectWith(X); + return setSignedRange(Add, ConservativeResult.intersectWith(X)); } if (const SCEVMulExpr *Mul = dyn_cast(S)) { ConstantRange X = getSignedRange(Mul->getOperand(0)); for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) X = X.multiply(getSignedRange(Mul->getOperand(i))); - return ConservativeResult.intersectWith(X); + return setSignedRange(Mul, ConservativeResult.intersectWith(X)); } if (const SCEVSMaxExpr *SMax = dyn_cast(S)) { ConstantRange X = getSignedRange(SMax->getOperand(0)); for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i) X = X.smax(getSignedRange(SMax->getOperand(i))); - return ConservativeResult.intersectWith(X); + return setSignedRange(SMax, ConservativeResult.intersectWith(X)); } if (const SCEVUMaxExpr *UMax = dyn_cast(S)) { ConstantRange X = getSignedRange(UMax->getOperand(0)); for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i) X = X.umax(getSignedRange(UMax->getOperand(i))); - return ConservativeResult.intersectWith(X); + return setSignedRange(UMax, ConservativeResult.intersectWith(X)); } if (const SCEVUDivExpr *UDiv = dyn_cast(S)) { ConstantRange X = getSignedRange(UDiv->getLHS()); ConstantRange Y = getSignedRange(UDiv->getRHS()); - return ConservativeResult.intersectWith(X.udiv(Y)); + return setSignedRange(UDiv, ConservativeResult.intersectWith(X.udiv(Y))); } if (const SCEVZeroExtendExpr *ZExt = dyn_cast(S)) { ConstantRange X = getSignedRange(ZExt->getOperand()); - return ConservativeResult.intersectWith(X.zeroExtend(BitWidth)); + return setSignedRange(ZExt, + ConservativeResult.intersectWith(X.zeroExtend(BitWidth))); } if (const SCEVSignExtendExpr *SExt = dyn_cast(S)) { ConstantRange X = getSignedRange(SExt->getOperand()); - return ConservativeResult.intersectWith(X.signExtend(BitWidth)); + return setSignedRange(SExt, + ConservativeResult.intersectWith(X.signExtend(BitWidth))); } if (const SCEVTruncateExpr *Trunc = dyn_cast(S)) { ConstantRange X = getSignedRange(Trunc->getOperand()); - return ConservativeResult.intersectWith(X.truncate(BitWidth)); + return setSignedRange(Trunc, + ConservativeResult.intersectWith(X.truncate(BitWidth))); } if (const SCEVAddRecExpr *AddRec = dyn_cast(S)) { @@ -3211,34 +3260,35 @@ ScalarEvolution::getSignedRange(const SCEV *S) { ConstantRange ExtEndRange = EndRange.sextOrTrunc(BitWidth*2+1); if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) != ExtEndRange) - return ConservativeResult; + return setSignedRange(AddRec, ConservativeResult); APInt Min = APIntOps::smin(StartRange.getSignedMin(), EndRange.getSignedMin()); APInt Max = APIntOps::smax(StartRange.getSignedMax(), EndRange.getSignedMax()); if (Min.isMinSignedValue() && Max.isMaxSignedValue()) - return ConservativeResult; - return ConservativeResult.intersectWith(ConstantRange(Min, Max+1)); + return setSignedRange(AddRec, ConservativeResult); + return setSignedRange(AddRec, + ConservativeResult.intersectWith(ConstantRange(Min, Max+1))); } } - return ConservativeResult; + return setSignedRange(AddRec, ConservativeResult); } if (const SCEVUnknown *U = dyn_cast(S)) { // For a SCEVUnknown, ask ValueTracking. if (!U->getValue()->getType()->isIntegerTy() && !TD) - return ConservativeResult; + return setSignedRange(U, ConservativeResult); unsigned NS = ComputeNumSignBits(U->getValue(), TD); if (NS == 1) - return ConservativeResult; - return ConservativeResult.intersectWith( + return setSignedRange(U, ConservativeResult); + return setSignedRange(U, ConservativeResult.intersectWith( ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1), - APInt::getSignedMaxValue(BitWidth).ashr(NS - 1)+1)); + APInt::getSignedMaxValue(BitWidth).ashr(NS - 1)+1))); } - return ConservativeResult; + return setSignedRange(S, ConservativeResult); } /// createSCEV - We know that there is no SCEV for the specified value. @@ -3271,12 +3321,42 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { Operator *U = cast(V); switch (Opcode) { - case Instruction::Add: - return getAddExpr(getSCEV(U->getOperand(0)), - getSCEV(U->getOperand(1))); - case Instruction::Mul: - return getMulExpr(getSCEV(U->getOperand(0)), - getSCEV(U->getOperand(1))); + case Instruction::Add: { + // The simple thing to do would be to just call getSCEV on both operands + // and call getAddExpr with the result. However if we're looking at a + // bunch of things all added together, this can be quite inefficient, + // because it leads to N-1 getAddExpr calls for N ultimate operands. + // Instead, gather up all the operands and make a single getAddExpr call. + // LLVM IR canonical form means we need only traverse the left operands. + SmallVector AddOps; + AddOps.push_back(getSCEV(U->getOperand(1))); + for (Value *Op = U->getOperand(0); ; Op = U->getOperand(0)) { + unsigned Opcode = Op->getValueID() - Value::InstructionVal; + if (Opcode != Instruction::Add && Opcode != Instruction::Sub) + break; + U = cast(Op); + const SCEV *Op1 = getSCEV(U->getOperand(1)); + if (Opcode == Instruction::Sub) + AddOps.push_back(getNegativeSCEV(Op1)); + else + AddOps.push_back(Op1); + } + AddOps.push_back(getSCEV(U->getOperand(0))); + return getAddExpr(AddOps); + } + case Instruction::Mul: { + // See the Add code above. + SmallVector MulOps; + MulOps.push_back(getSCEV(U->getOperand(1))); + for (Value *Op = U->getOperand(0); + Op->getValueID() == Instruction::Mul + Value::InstructionVal; + Op = U->getOperand(0)) { + U = cast(Op); + MulOps.push_back(getSCEV(U->getOperand(1))); + } + MulOps.push_back(getSCEV(U->getOperand(0))); + return getMulExpr(MulOps); + } case Instruction::UDiv: return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); @@ -3376,8 +3456,8 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // If C is a single bit, it may be in the sign-bit position // before the zero-extend. In this case, represent the xor // using an add, which is equivalent, and re-apply the zext. - APInt Trunc = APInt(CI->getValue()).trunc(Z0TySize); - if (APInt(Trunc).zext(getTypeSizeInBits(UTy)) == CI->getValue() && + APInt Trunc = CI->getValue().trunc(Z0TySize); + if (Trunc.zext(getTypeSizeInBits(UTy)) == CI->getValue() && Trunc.isSignBit()) return getZeroExtendExpr(getAddExpr(Z0, getConstant(Trunc)), UTy); @@ -3617,58 +3697,61 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // backedge-taken count, which could result in infinite recursion. std::pair::iterator, bool> Pair = BackedgeTakenCounts.insert(std::make_pair(L, getCouldNotCompute())); - if (Pair.second) { - BackedgeTakenInfo BECount = ComputeBackedgeTakenCount(L); - if (BECount.Exact != getCouldNotCompute()) { - assert(BECount.Exact->isLoopInvariant(L) && - BECount.Max->isLoopInvariant(L) && - "Computed backedge-taken count isn't loop invariant for loop!"); - ++NumTripCountsComputed; + if (!Pair.second) + return Pair.first->second; + + BackedgeTakenInfo BECount = ComputeBackedgeTakenCount(L); + if (BECount.Exact != getCouldNotCompute()) { + assert(isLoopInvariant(BECount.Exact, L) && + isLoopInvariant(BECount.Max, L) && + "Computed backedge-taken count isn't loop invariant for loop!"); + ++NumTripCountsComputed; + // Update the value in the map. + Pair.first->second = BECount; + } else { + if (BECount.Max != getCouldNotCompute()) // Update the value in the map. Pair.first->second = BECount; - } else { - if (BECount.Max != getCouldNotCompute()) - // Update the value in the map. - Pair.first->second = BECount; - if (isa(L->getHeader()->begin())) - // Only count loops that have phi nodes as not being computable. - ++NumTripCountsNotComputed; - } - - // Now that we know more about the trip count for this loop, forget any - // existing SCEV values for PHI nodes in this loop since they are only - // conservative estimates made without the benefit of trip count - // information. This is similar to the code in forgetLoop, except that - // it handles SCEVUnknown PHI nodes specially. - if (BECount.hasAnyInfo()) { - SmallVector Worklist; - PushLoopPHIs(L, Worklist); - - SmallPtrSet Visited; - while (!Worklist.empty()) { - Instruction *I = Worklist.pop_back_val(); - if (!Visited.insert(I)) continue; - - std::map::iterator It = - Scalars.find(static_cast(I)); - if (It != Scalars.end()) { - // SCEVUnknown for a PHI either means that it has an unrecognized - // structure, or it's a PHI that's in the progress of being computed - // by createNodeForPHI. In the former case, additional loop trip - // count information isn't going to change anything. In the later - // case, createNodeForPHI will perform the necessary updates on its - // own when it gets to that point. - if (!isa(I) || !isa(It->second)) { - ValuesAtScopes.erase(It->second); - Scalars.erase(It); - } - if (PHINode *PN = dyn_cast(I)) - ConstantEvolutionLoopExitValue.erase(PN); + if (isa(L->getHeader()->begin())) + // Only count loops that have phi nodes as not being computable. + ++NumTripCountsNotComputed; + } + + // Now that we know more about the trip count for this loop, forget any + // existing SCEV values for PHI nodes in this loop since they are only + // conservative estimates made without the benefit of trip count + // information. This is similar to the code in forgetLoop, except that + // it handles SCEVUnknown PHI nodes specially. + if (BECount.hasAnyInfo()) { + SmallVector Worklist; + PushLoopPHIs(L, Worklist); + + SmallPtrSet Visited; + while (!Worklist.empty()) { + Instruction *I = Worklist.pop_back_val(); + if (!Visited.insert(I)) continue; + + ValueExprMapType::iterator It = + ValueExprMap.find(static_cast(I)); + if (It != ValueExprMap.end()) { + const SCEV *Old = It->second; + + // SCEVUnknown for a PHI either means that it has an unrecognized + // structure, or it's a PHI that's in the progress of being computed + // by createNodeForPHI. In the former case, additional loop trip + // count information isn't going to change anything. In the later + // case, createNodeForPHI will perform the necessary updates on its + // own when it gets to that point. + if (!isa(I) || !isa(Old)) { + forgetMemoizedResults(Old); + ValueExprMap.erase(It); } - - PushDefUseChildren(I, Worklist); + if (PHINode *PN = dyn_cast(I)) + ConstantEvolutionLoopExitValue.erase(PN); } + + PushDefUseChildren(I, Worklist); } } return Pair.first->second; @@ -3690,17 +3773,21 @@ void ScalarEvolution::forgetLoop(const Loop *L) { Instruction *I = Worklist.pop_back_val(); if (!Visited.insert(I)) continue; - std::map::iterator It = - Scalars.find(static_cast(I)); - if (It != Scalars.end()) { - ValuesAtScopes.erase(It->second); - Scalars.erase(It); + ValueExprMapType::iterator It = ValueExprMap.find(static_cast(I)); + if (It != ValueExprMap.end()) { + forgetMemoizedResults(It->second); + ValueExprMap.erase(It); if (PHINode *PN = dyn_cast(I)) ConstantEvolutionLoopExitValue.erase(PN); } PushDefUseChildren(I, Worklist); } + + // Forget all contained loops too, to avoid dangling entries in the + // ValuesAtScopes map. + for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) + forgetLoop(*I); } /// forgetValue - This method should be called by the client when it has @@ -3719,11 +3806,10 @@ void ScalarEvolution::forgetValue(Value *V) { I = Worklist.pop_back_val(); if (!Visited.insert(I)) continue; - std::map::iterator It = - Scalars.find(static_cast(I)); - if (It != Scalars.end()) { - ValuesAtScopes.erase(It->second); - Scalars.erase(It); + ValueExprMapType::iterator It = ValueExprMap.find(static_cast(I)); + if (It != ValueExprMap.end()) { + forgetMemoizedResults(It->second); + ValueExprMap.erase(It); if (PHINode *PN = dyn_cast(I)) ConstantEvolutionLoopExitValue.erase(PN); } @@ -3936,6 +4022,105 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L, return ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB)); } +static const SCEVAddRecExpr * +isSimpleUnwrappingAddRec(const SCEV *S, const Loop *L) { + const SCEVAddRecExpr *SA = dyn_cast(S); + + // The SCEV must be an addrec of this loop. + if (!SA || SA->getLoop() != L || !SA->isAffine()) + return 0; + + // The SCEV must be known to not wrap in some way to be interesting. + if (!SA->hasNoUnsignedWrap() && !SA->hasNoSignedWrap()) + return 0; + + // The stride must be a constant so that we know if it is striding up or down. + if (!isa(SA->getOperand(1))) + return 0; + return SA; +} + +/// getMinusSCEVForExitTest - When considering an exit test for a loop with a +/// "x != y" exit test, we turn this into a computation that evaluates x-y != 0, +/// and this function returns the expression to use for x-y. We know and take +/// advantage of the fact that this subtraction is only being used in a +/// comparison by zero context. +/// +static const SCEV *getMinusSCEVForExitTest(const SCEV *LHS, const SCEV *RHS, + const Loop *L, ScalarEvolution &SE) { + // If either LHS or RHS is an AddRec SCEV (of this loop) that is known to not + // wrap (either NSW or NUW), then we know that the value will either become + // the other one (and thus the loop terminates), that the loop will terminate + // through some other exit condition first, or that the loop has undefined + // behavior. This information is useful when the addrec has a stride that is + // != 1 or -1, because it means we can't "miss" the exit value. + // + // In any of these three cases, it is safe to turn the exit condition into a + // "counting down" AddRec (to zero) by subtracting the two inputs as normal, + // but since we know that the "end cannot be missed" we can force the + // resulting AddRec to be a NUW addrec. Since it is counting down, this means + // that the AddRec *cannot* pass zero. + + // See if LHS and RHS are addrec's we can handle. + const SCEVAddRecExpr *LHSA = isSimpleUnwrappingAddRec(LHS, L); + const SCEVAddRecExpr *RHSA = isSimpleUnwrappingAddRec(RHS, L); + + // If neither addrec is interesting, just return a minus. + if (RHSA == 0 && LHSA == 0) + return SE.getMinusSCEV(LHS, RHS); + + // If only one of LHS and RHS are an AddRec of this loop, make sure it is LHS. + if (RHSA && LHSA == 0) { + // Safe because a-b === b-a for comparisons against zero. + std::swap(LHS, RHS); + std::swap(LHSA, RHSA); + } + + // Handle the case when only one is advancing in a non-overflowing way. + if (RHSA == 0) { + // If RHS is loop varying, then we can't predict when LHS will cross it. + if (!SE.isLoopInvariant(RHS, L)) + return SE.getMinusSCEV(LHS, RHS); + + // If LHS has a positive stride, then we compute RHS-LHS, because the loop + // is counting up until it crosses RHS (which must be larger than LHS). If + // it is negative, we compute LHS-RHS because we're counting down to RHS. + const ConstantInt *Stride = + cast(LHSA->getOperand(1))->getValue(); + if (Stride->getValue().isNegative()) + std::swap(LHS, RHS); + + return SE.getMinusSCEV(RHS, LHS, true /*HasNUW*/); + } + + // If both LHS and RHS are interesting, we have something like: + // a+i*4 != b+i*8. + const ConstantInt *LHSStride = + cast(LHSA->getOperand(1))->getValue(); + const ConstantInt *RHSStride = + cast(RHSA->getOperand(1))->getValue(); + + // If the strides are equal, then this is just a (complex) loop invariant + // comparison of a and b. + if (LHSStride == RHSStride) + return SE.getMinusSCEV(LHSA->getStart(), RHSA->getStart()); + + // If the signs of the strides differ, then the negative stride is counting + // down to the positive stride. + if (LHSStride->getValue().isNegative() != RHSStride->getValue().isNegative()){ + if (RHSStride->getValue().isNegative()) + std::swap(LHS, RHS); + } else { + // If LHS's stride is smaller than RHS's stride, then "b" must be less than + // "a" and "b" is RHS is counting up (catching up) to LHS. This is true + // whether the strides are positive or negative. + if (RHSStride->getValue().slt(LHSStride->getValue())) + std::swap(LHS, RHS); + } + + return SE.getMinusSCEV(LHS, RHS, true /*HasNUW*/); +} + /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of times the /// backedge of the specified loop will execute if its exit condition /// were a conditional branch of the ICmpInst ExitCond, TBB, and FBB. @@ -3970,7 +4155,7 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, // 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 (isLoopInvariant(LHS, L) && !isLoopInvariant(RHS, L)) { // If there is a loop-invariant, force it into the RHS. std::swap(LHS, RHS); Cond = ICmpInst::getSwappedPredicate(Cond); @@ -3995,7 +4180,8 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, switch (Cond) { case ICmpInst::ICMP_NE: { // while (X != Y) // Convert to: while (X-Y != 0) - BackedgeTakenInfo BTI = HowFarToZero(getMinusSCEV(LHS, RHS), L); + BackedgeTakenInfo BTI = HowFarToZero(getMinusSCEVForExitTest(LHS, RHS, L, + *this), L); if (BTI.hasAnyInfo()) return BTI; break; } @@ -4132,7 +4318,7 @@ ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount( // We can only recognize very limited forms of loop index expressions, in // particular, only affine AddRec's like {C1,+,C2}. const SCEVAddRecExpr *IdxExpr = dyn_cast(Idx); - if (!IdxExpr || !IdxExpr->isAffine() || IdxExpr->isLoopInvariant(L) || + if (!IdxExpr || !IdxExpr->isAffine() || isLoopInvariant(IdxExpr, L) || !isa(IdxExpr->getOperand(0)) || !isa(IdxExpr->getOperand(1))) return getCouldNotCompute(); @@ -4252,7 +4438,7 @@ Constant * ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, const APInt &BEs, const Loop *L) { - std::map::iterator I = + std::map::const_iterator I = ConstantEvolutionLoopExitValue.find(PN); if (I != ConstantEvolutionLoopExitValue.end()) return I->second; @@ -4606,7 +4792,7 @@ static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const APInt &B, // bit width during computations. APInt AD = A.lshr(Mult2).zext(BW + 1); // AD = A / D APInt Mod(BW + 1, 0); - Mod.set(BW - Mult2); // Mod = N / D + Mod.setBit(BW - Mult2); // Mod = N / D APInt I = AD.multiplicativeInverse(Mod); // 4. Compute the minimum unsigned root of the equation: @@ -4698,58 +4884,26 @@ ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { if (!AddRec || AddRec->getLoop() != L) return getCouldNotCompute(); - if (AddRec->isAffine()) { - // If this is an affine expression, the execution count of this branch is - // the minimum unsigned root of the following equation: - // - // Start + Step*N = 0 (mod 2^BW) - // - // equivalent to: - // - // Step*N = -Start (mod 2^BW) - // - // where BW is the common bit width of Start and Step. - - // Get the initial value for the loop. - const SCEV *Start = getSCEVAtScope(AddRec->getStart(), - L->getParentLoop()); - const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), - L->getParentLoop()); - - if (const SCEVConstant *StepC = dyn_cast(Step)) { - // For now we handle only constant steps. - - // First, handle unitary steps. - if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so: - return getNegativeSCEV(Start); // N = -Start (as unsigned) - if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so: - return Start; // N = Start (as unsigned) - - // Then, try to solve the above equation provided that Start is constant. - if (const SCEVConstant *StartC = dyn_cast(Start)) - return SolveLinEquationWithOverflow(StepC->getValue()->getValue(), - -StartC->getValue()->getValue(), - *this); - } - } else if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) { - // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of - // the quadratic equation to solve it. - std::pair Roots = SolveQuadraticEquation(AddRec, - *this); + // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of + // the quadratic equation to solve it. + if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) { + std::pair Roots = + SolveQuadraticEquation(AddRec, *this); const SCEVConstant *R1 = dyn_cast(Roots.first); const SCEVConstant *R2 = dyn_cast(Roots.second); - if (R1) { + if (R1 && R2) { #if 0 dbgs() << "HFTZ: " << *V << " - sol#1: " << *R1 << " sol#2: " << *R2 << "\n"; #endif // Pick the smallest positive root value. if (ConstantInt *CB = - dyn_cast(ConstantExpr::getICmp(ICmpInst::ICMP_ULT, - R1->getValue(), R2->getValue()))) { + dyn_cast(ConstantExpr::getICmp(CmpInst::ICMP_ULT, + R1->getValue(), + R2->getValue()))) { if (CB->getZExtValue() == false) std::swap(R1, R2); // R1 is the minimum root now. - + // We can only use this value if the chrec ends up with an exact zero // value at this index. When solving for "X*X != 5", for example, we // should not accept a root of 2. @@ -4758,8 +4912,54 @@ ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { return R1; // We found a quadratic root! } } + return getCouldNotCompute(); } + // Otherwise we can only handle this if it is affine. + if (!AddRec->isAffine()) + return getCouldNotCompute(); + + // If this is an affine expression, the execution count of this branch is + // the minimum unsigned root of the following equation: + // + // Start + Step*N = 0 (mod 2^BW) + // + // equivalent to: + // + // Step*N = -Start (mod 2^BW) + // + // where BW is the common bit width of Start and Step. + + // Get the initial value for the loop. + const SCEV *Start = getSCEVAtScope(AddRec->getStart(), L->getParentLoop()); + const SCEV *Step = getSCEVAtScope(AddRec->getOperand(1), L->getParentLoop()); + + // If the AddRec is NUW, then (in an unsigned sense) it cannot be counting up + // to wrap to 0, it must be counting down to equal 0. Also, while counting + // down, it cannot "miss" 0 (which would cause it to wrap), regardless of what + // the stride is. As such, NUW addrec's will always become zero in + // "start / -stride" steps, and we know that the division is exact. + if (AddRec->hasNoUnsignedWrap()) + // FIXME: We really want an "isexact" bit for udiv. + return getUDivExpr(Start, getNegativeSCEV(Step)); + + // For now we handle only constant steps. + const SCEVConstant *StepC = dyn_cast(Step); + if (StepC == 0) + return getCouldNotCompute(); + + // First, handle unitary steps. + if (StepC->getValue()->equalsInt(1)) // 1*N = -Start (mod 2^BW), so: + return getNegativeSCEV(Start); // N = -Start (as unsigned) + + if (StepC->getValue()->isAllOnesValue()) // -1*N = -Start (mod 2^BW), so: + return Start; // N = Start (as unsigned) + + // Then, try to solve the above equation provided that Start is constant. + if (const SCEVConstant *StartC = dyn_cast(Start)) + return SolveLinEquationWithOverflow(StepC->getValue()->getValue(), + -StartC->getValue()->getValue(), + *this); return getCouldNotCompute(); } @@ -4859,7 +5059,7 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, // as both operands could be addrecs loop-invariant in each other's loop. if (const SCEVAddRecExpr *AR = dyn_cast(RHS)) { const Loop *L = AR->getLoop(); - if (LHS->isLoopInvariant(L) && LHS->properlyDominates(L->getHeader(), DT)) { + if (isLoopInvariant(LHS, L) && properlyDominates(LHS, L->getHeader())) { std::swap(LHS, RHS); Pred = ICmpInst::getSwappedPredicate(Pred); Changed = true; @@ -5079,13 +5279,13 @@ bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, trivially_true: // Return 0 == 0. - LHS = RHS = getConstant(Type::getInt1Ty(getContext()), 0); + LHS = RHS = getConstant(ConstantInt::getFalse(getContext())); Pred = ICmpInst::ICMP_EQ; return true; trivially_false: // Return 0 != 0. - LHS = RHS = getConstant(Type::getInt1Ty(getContext()), 0); + LHS = RHS = getConstant(ConstantInt::getFalse(getContext())); Pred = ICmpInst::ICMP_NE; return true; } @@ -5476,7 +5676,7 @@ ScalarEvolution::BackedgeTakenInfo ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, bool isSigned) { // Only handle: "ADDREC < LoopInvariant". - if (!RHS->isLoopInvariant(L)) return getCouldNotCompute(); + if (!isLoopInvariant(RHS, L)) return getCouldNotCompute(); const SCEVAddRecExpr *AddRec = dyn_cast(LHS); if (!AddRec || AddRec->getLoop() != L) @@ -5709,7 +5909,7 @@ void ScalarEvolution::SCEVCallbackVH::deleted() { assert(SE && "SCEVCallbackVH called with a null ScalarEvolution!"); if (PHINode *PN = dyn_cast(getValPtr())) SE->ConstantEvolutionLoopExitValue.erase(PN); - SE->Scalars.erase(getValPtr()); + SE->ValueExprMap.erase(getValPtr()); // this now dangles! } @@ -5735,7 +5935,7 @@ void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *V) { continue; if (PHINode *PN = dyn_cast(U)) SE->ConstantEvolutionLoopExitValue.erase(PN); - SE->Scalars.erase(U); + SE->ValueExprMap.erase(U); for (Value::use_iterator UI = U->use_begin(), UE = U->use_end(); UI != UE; ++UI) Worklist.push_back(*UI); @@ -5743,7 +5943,7 @@ void ScalarEvolution::SCEVCallbackVH::allUsesReplacedWith(Value *V) { // Delete the Old value. if (PHINode *PN = dyn_cast(Old)) SE->ConstantEvolutionLoopExitValue.erase(PN); - SE->Scalars.erase(Old); + SE->ValueExprMap.erase(Old); // this now dangles! } @@ -5756,6 +5956,7 @@ ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se) ScalarEvolution::ScalarEvolution() : FunctionPass(ID), FirstUnknown(0) { + initializeScalarEvolutionPass(*PassRegistry::getPassRegistry()); } bool ScalarEvolution::runOnFunction(Function &F) { @@ -5773,10 +5974,14 @@ void ScalarEvolution::releaseMemory() { U->~SCEVUnknown(); FirstUnknown = 0; - Scalars.clear(); + ValueExprMap.clear(); BackedgeTakenCounts.clear(); ConstantEvolutionLoopExitValue.clear(); ValuesAtScopes.clear(); + LoopDispositions.clear(); + BlockDispositions.clear(); + UnsignedRanges.clear(); + SignedRanges.clear(); UniqueSCEVs.clear(); SCEVAllocator.Reset(); } @@ -5856,7 +6061,7 @@ void ScalarEvolution::print(raw_ostream &OS, const Module *) const { if (L) { OS << "\t\t" "Exits: "; const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); - if (!ExitValue->isLoopInvariant(L)) { + if (!SE.isLoopInvariant(ExitValue, L)) { OS << "<>"; } else { OS << *ExitValue; @@ -5873,3 +6078,240 @@ void ScalarEvolution::print(raw_ostream &OS, const Module *) const { PrintLoopInfo(OS, &SE, *I); } +ScalarEvolution::LoopDisposition +ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) { + std::map &Values = LoopDispositions[S]; + std::pair::iterator, bool> Pair = + Values.insert(std::make_pair(L, LoopVariant)); + if (!Pair.second) + return Pair.first->second; + + LoopDisposition D = computeLoopDisposition(S, L); + return LoopDispositions[S][L] = D; +} + +ScalarEvolution::LoopDisposition +ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) { + switch (S->getSCEVType()) { + case scConstant: + return LoopInvariant; + case scTruncate: + case scZeroExtend: + case scSignExtend: + return getLoopDisposition(cast(S)->getOperand(), L); + case scAddRecExpr: { + const SCEVAddRecExpr *AR = cast(S); + + // If L is the addrec's loop, it's computable. + if (AR->getLoop() == L) + return LoopComputable; + + // Add recurrences are never invariant in the function-body (null loop). + if (!L) + return LoopVariant; + + // This recurrence is variant w.r.t. L if L contains AR's loop. + if (L->contains(AR->getLoop())) + return LoopVariant; + + // This recurrence is invariant w.r.t. L if AR's loop contains L. + if (AR->getLoop()->contains(L)) + return LoopInvariant; + + // This recurrence is variant w.r.t. L if any of its operands + // are variant. + for (SCEVAddRecExpr::op_iterator I = AR->op_begin(), E = AR->op_end(); + I != E; ++I) + if (!isLoopInvariant(*I, L)) + return LoopVariant; + + // Otherwise it's loop-invariant. + return LoopInvariant; + } + case scAddExpr: + case scMulExpr: + case scUMaxExpr: + case scSMaxExpr: { + const SCEVNAryExpr *NAry = cast(S); + bool HasVarying = false; + for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); + I != E; ++I) { + LoopDisposition D = getLoopDisposition(*I, L); + if (D == LoopVariant) + return LoopVariant; + if (D == LoopComputable) + HasVarying = true; + } + return HasVarying ? LoopComputable : LoopInvariant; + } + case scUDivExpr: { + const SCEVUDivExpr *UDiv = cast(S); + LoopDisposition LD = getLoopDisposition(UDiv->getLHS(), L); + if (LD == LoopVariant) + return LoopVariant; + LoopDisposition RD = getLoopDisposition(UDiv->getRHS(), L); + if (RD == LoopVariant) + return LoopVariant; + return (LD == LoopInvariant && RD == LoopInvariant) ? + LoopInvariant : LoopComputable; + } + case scUnknown: + // All non-instruction values are loop invariant. All instructions are loop + // invariant if they are not contained in the specified loop. + // Instructions are never considered invariant in the function body + // (null loop) because they are defined within the "loop". + if (Instruction *I = dyn_cast(cast(S)->getValue())) + return (L && !L->contains(I)) ? LoopInvariant : LoopVariant; + return LoopInvariant; + case scCouldNotCompute: + llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); + return LoopVariant; + default: break; + } + llvm_unreachable("Unknown SCEV kind!"); + return LoopVariant; +} + +bool ScalarEvolution::isLoopInvariant(const SCEV *S, const Loop *L) { + return getLoopDisposition(S, L) == LoopInvariant; +} + +bool ScalarEvolution::hasComputableLoopEvolution(const SCEV *S, const Loop *L) { + return getLoopDisposition(S, L) == LoopComputable; +} + +ScalarEvolution::BlockDisposition +ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) { + std::map &Values = BlockDispositions[S]; + std::pair::iterator, bool> + Pair = Values.insert(std::make_pair(BB, DoesNotDominateBlock)); + if (!Pair.second) + return Pair.first->second; + + BlockDisposition D = computeBlockDisposition(S, BB); + return BlockDispositions[S][BB] = D; +} + +ScalarEvolution::BlockDisposition +ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) { + switch (S->getSCEVType()) { + case scConstant: + return ProperlyDominatesBlock; + case scTruncate: + case scZeroExtend: + case scSignExtend: + return getBlockDisposition(cast(S)->getOperand(), BB); + case scAddRecExpr: { + // This uses a "dominates" query instead of "properly dominates" query + // to test for proper dominance too, because the instruction which + // produces the addrec's value is a PHI, and a PHI effectively properly + // dominates its entire containing block. + const SCEVAddRecExpr *AR = cast(S); + if (!DT->dominates(AR->getLoop()->getHeader(), BB)) + return DoesNotDominateBlock; + } + // FALL THROUGH into SCEVNAryExpr handling. + case scAddExpr: + case scMulExpr: + case scUMaxExpr: + case scSMaxExpr: { + const SCEVNAryExpr *NAry = cast(S); + bool Proper = true; + for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); + I != E; ++I) { + BlockDisposition D = getBlockDisposition(*I, BB); + if (D == DoesNotDominateBlock) + return DoesNotDominateBlock; + if (D == DominatesBlock) + Proper = false; + } + return Proper ? ProperlyDominatesBlock : DominatesBlock; + } + case scUDivExpr: { + const SCEVUDivExpr *UDiv = cast(S); + const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS(); + BlockDisposition LD = getBlockDisposition(LHS, BB); + if (LD == DoesNotDominateBlock) + return DoesNotDominateBlock; + BlockDisposition RD = getBlockDisposition(RHS, BB); + if (RD == DoesNotDominateBlock) + return DoesNotDominateBlock; + return (LD == ProperlyDominatesBlock && RD == ProperlyDominatesBlock) ? + ProperlyDominatesBlock : DominatesBlock; + } + case scUnknown: + if (Instruction *I = + dyn_cast(cast(S)->getValue())) { + if (I->getParent() == BB) + return DominatesBlock; + if (DT->properlyDominates(I->getParent(), BB)) + return ProperlyDominatesBlock; + return DoesNotDominateBlock; + } + return ProperlyDominatesBlock; + case scCouldNotCompute: + llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); + return DoesNotDominateBlock; + default: break; + } + llvm_unreachable("Unknown SCEV kind!"); + return DoesNotDominateBlock; +} + +bool ScalarEvolution::dominates(const SCEV *S, const BasicBlock *BB) { + return getBlockDisposition(S, BB) >= DominatesBlock; +} + +bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) { + return getBlockDisposition(S, BB) == ProperlyDominatesBlock; +} + +bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const { + switch (S->getSCEVType()) { + case scConstant: + return false; + case scTruncate: + case scZeroExtend: + case scSignExtend: { + const SCEVCastExpr *Cast = cast(S); + const SCEV *CastOp = Cast->getOperand(); + return Op == CastOp || hasOperand(CastOp, Op); + } + case scAddRecExpr: + case scAddExpr: + case scMulExpr: + case scUMaxExpr: + case scSMaxExpr: { + const SCEVNAryExpr *NAry = cast(S); + for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); + I != E; ++I) { + const SCEV *NAryOp = *I; + if (NAryOp == Op || hasOperand(NAryOp, Op)) + return true; + } + return false; + } + case scUDivExpr: { + const SCEVUDivExpr *UDiv = cast(S); + const SCEV *LHS = UDiv->getLHS(), *RHS = UDiv->getRHS(); + return LHS == Op || hasOperand(LHS, Op) || + RHS == Op || hasOperand(RHS, Op); + } + case scUnknown: + return false; + case scCouldNotCompute: + llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); + return false; + default: break; + } + llvm_unreachable("Unknown SCEV kind!"); + return false; +} + +void ScalarEvolution::forgetMemoizedResults(const SCEV *S) { + ValuesAtScopes.erase(S); + LoopDispositions.erase(S); + BlockDispositions.erase(S); + UnsignedRanges.erase(S); + SignedRanges.erase(S); +}