X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolution.cpp;h=3c67a348fe84f735f705b93845411732f197e699;hp=c2284a8ab9bd22a2ee429a6cf8d2f0241e44e759;hb=d13db2c59cc94162d6cf0a04187d408bfef6d4a7;hpb=aa11defd1c66dbde0c757c99791c4ae4d740fc3e diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp index c2284a8ab9b..3c67a348fe8 100644 --- a/lib/Analysis/ScalarEvolution.cpp +++ b/lib/Analysis/ScalarEvolution.cpp @@ -103,8 +103,8 @@ MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden, "derived loop"), cl::init(100)); -static RegisterPass -R("scalar-evolution", "Scalar Evolution Analysis", false, true); +INITIALIZE_PASS(ScalarEvolution, "scalar-evolution", + "Scalar Evolution Analysis", false, true); char ScalarEvolution::ID = 0; //===----------------------------------------------------------------------===// @@ -141,7 +141,7 @@ bool SCEV::isAllOnesValue() const { } SCEVCouldNotCompute::SCEVCouldNotCompute() : - SCEV(FoldingSetNodeID(), scCouldNotCompute) {} + SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {} bool SCEVCouldNotCompute::isLoopInvariant(const Loop *L) const { llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!"); @@ -177,8 +177,7 @@ const SCEV *ScalarEvolution::getConstant(ConstantInt *V) { ID.AddPointer(V); void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); - new (S) SCEVConstant(ID, V); + SCEV *S = new (SCEVAllocator) SCEVConstant(ID.Intern(SCEVAllocator), V); UniqueSCEVs.InsertNode(S, IP); return S; } @@ -189,8 +188,8 @@ const SCEV *ScalarEvolution::getConstant(const APInt& Val) { const SCEV * ScalarEvolution::getConstant(const Type *Ty, uint64_t V, bool isSigned) { - return getConstant( - ConstantInt::get(cast(Ty), V, isSigned)); + const IntegerType *ITy = cast(getEffectiveSCEVType(Ty)); + return getConstant(ConstantInt::get(ITy, V, isSigned)); } const Type *SCEVConstant::getType() const { return V->getType(); } @@ -199,7 +198,7 @@ void SCEVConstant::print(raw_ostream &OS) const { WriteAsOperand(OS, V, false); } -SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeID &ID, +SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID, unsigned SCEVTy, const SCEV *op, const Type *ty) : SCEV(ID, SCEVTy), Op(op), Ty(ty) {} @@ -211,7 +210,7 @@ bool SCEVCastExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { return Op->properlyDominates(BB, DT); } -SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeID &ID, +SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op, const Type *ty) : SCEVCastExpr(ID, scTruncate, op, ty) { assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) && @@ -223,7 +222,7 @@ void SCEVTruncateExpr::print(raw_ostream &OS) const { OS << "(trunc " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; } -SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeID &ID, +SCEVZeroExtendExpr::SCEVZeroExtendExpr(const FoldingSetNodeIDRef ID, const SCEV *op, const Type *ty) : SCEVCastExpr(ID, scZeroExtend, op, ty) { assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) && @@ -235,7 +234,7 @@ void SCEVZeroExtendExpr::print(raw_ostream &OS) const { OS << "(zext " << *Op->getType() << " " << *Op << " to " << *Ty << ")"; } -SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeID &ID, +SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID, const SCEV *op, const Type *ty) : SCEVCastExpr(ID, scSignExtend, op, ty) { assert((Op->getType()->isIntegerTy() || Op->getType()->isPointerTy()) && @@ -248,11 +247,13 @@ void SCEVSignExtendExpr::print(raw_ostream &OS) const { } void SCEVCommutativeExpr::print(raw_ostream &OS) const { - assert(Operands.size() > 1 && "This plus expr shouldn't exist!"); const char *OpStr = getOperationStr(); - OS << "(" << *Operands[0]; - for (unsigned i = 1, e = Operands.size(); i != e; ++i) - OS << OpStr << *Operands[i]; + OS << "("; + for (op_iterator I = op_begin(), E = op_end(); I != E; ++I) { + OS << **I; + if (next(I) != E) + OS << OpStr; + } OS << ")"; } @@ -329,7 +330,7 @@ SCEVAddRecExpr::properlyDominates(BasicBlock *BB, DominatorTree *DT) const { void SCEVAddRecExpr::print(raw_ostream &OS) const { OS << "{" << *Operands[0]; - for (unsigned i = 1, e = Operands.size(); i != e; ++i) + for (unsigned i = 1, e = NumOperands; i != e; ++i) OS << ",+," << *Operands[i]; OS << "}<"; WriteAsOperand(OS, L->getHeader(), /*PrintType=*/false); @@ -616,7 +617,7 @@ namespace { /// When this routine is finished, we know that any duplicates in the vector are /// consecutive and that complexity is monotonically increasing. /// -/// Note that we go take special precautions to ensure that we get determinstic +/// Note that we go take special precautions to ensure that we get deterministic /// results from this routine. In other words, we don't want the results of /// this to depend on where the addresses of various SCEV objects happened to /// land in memory. @@ -744,7 +745,7 @@ static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, // We need at least W + T bits for the multiplication step unsigned CalculationBits = W + T; - // Calcuate 2^T, at width T+W. + // Calculate 2^T, at width T+W. APInt DivFactor = APInt(CalculationBits, 1).shl(T); // Calculate the multiplicative inverse of K! / 2^T; @@ -760,7 +761,7 @@ static const SCEV *BinomialCoefficient(const SCEV *It, unsigned K, CalculationBits); const SCEV *Dividend = SE.getTruncateOrZeroExtend(It, CalculationTy); for (unsigned i = 1; i != K; ++i) { - const SCEV *S = SE.getMinusSCEV(It, SE.getIntegerSCEV(i, It->getType())); + const SCEV *S = SE.getMinusSCEV(It, SE.getConstant(It->getType(), i)); Dividend = SE.getMulExpr(Dividend, SE.getTruncateOrZeroExtend(S, CalculationTy)); } @@ -821,7 +822,8 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, // Fold if the operand is constant. if (const SCEVConstant *SC = dyn_cast(Op)) return getConstant( - cast(ConstantExpr::getTrunc(SC->getValue(), Ty))); + cast(ConstantExpr::getTrunc(SC->getValue(), + getEffectiveSCEVType(Ty)))); // trunc(trunc(x)) --> trunc(x) if (const SCEVTruncateExpr *ST = dyn_cast(Op)) @@ -843,11 +845,18 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, return getAddRecExpr(Operands, AddRec->getLoop()); } - // The cast wasn't folded; create an explicit cast node. - // Recompute the insert position, as it may have been invalidated. - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); - new (S) SCEVTruncateExpr(ID, Op, Ty); + // As a special case, fold trunc(undef) to undef. We don't want to + // know too much about SCEVUnknowns, but this special case is handy + // and harmless. + if (const SCEVUnknown *U = dyn_cast(Op)) + if (isa(U->getValue())) + return getSCEV(UndefValue::get(Ty)); + + // The cast wasn't folded; create an explicit cast node. We can reuse + // the existing insert position since if we get here, we won't have + // made any changes which would invalidate it. + SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator), + Op, Ty); UniqueSCEVs.InsertNode(S, IP); return S; } @@ -861,12 +870,10 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Ty = getEffectiveSCEVType(Ty); // Fold if the operand is constant. - if (const SCEVConstant *SC = dyn_cast(Op)) { - const Type *IntTy = getEffectiveSCEVType(Ty); - Constant *C = ConstantExpr::getZExt(SC->getValue(), IntTy); - if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); - return getConstant(cast(C)); - } + if (const SCEVConstant *SC = dyn_cast(Op)) + return getConstant( + cast(ConstantExpr::getZExt(SC->getValue(), + getEffectiveSCEVType(Ty)))); // zext(zext(x)) --> zext(x) if (const SCEVZeroExtendExpr *SZ = dyn_cast(Op)) @@ -921,9 +928,7 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, if (MaxBECount == RecastedMaxBECount) { const Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); // Check whether Start+Step*MaxBECount has no unsigned overflow. - const SCEV *ZMul = - getMulExpr(CastedMaxBECount, - getTruncateOrZeroExtend(Step, Start->getType())); + const SCEV *ZMul = getMulExpr(CastedMaxBECount, Step); const SCEV *Add = getAddExpr(Start, ZMul); const SCEV *OperandExtendedAdd = getAddExpr(getZeroExtendExpr(Start, WideTy), @@ -937,9 +942,7 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, // Similar to above, only this time treat the step value as signed. // This covers loops that count down. - const SCEV *SMul = - getMulExpr(CastedMaxBECount, - getTruncateOrSignExtend(Step, Start->getType())); + const SCEV *SMul = getMulExpr(CastedMaxBECount, Step); Add = getAddExpr(Start, SMul); OperandExtendedAdd = getAddExpr(getZeroExtendExpr(Start, WideTy), @@ -960,7 +963,7 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, const SCEV *N = getConstant(APInt::getMinValue(BitWidth) - getUnsignedRange(Step).getUnsignedMax()); if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR, N) || - (isLoopGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) && + (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) && isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR->getPostIncExpr(*this), N))) // Return the expression with the addrec on the outside. @@ -970,8 +973,8 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, } else if (isKnownNegative(Step)) { const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) - getSignedRange(Step).getSignedMin()); - if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) && - (isLoopGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) || + if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) || + (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) && isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR->getPostIncExpr(*this), N))) // Return the expression with the addrec on the outside. @@ -985,8 +988,8 @@ const SCEV *ScalarEvolution::getZeroExtendExpr(const SCEV *Op, // The cast wasn't folded; create an explicit cast node. // Recompute the insert position, as it may have been invalidated. if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); - new (S) SCEVZeroExtendExpr(ID, Op, Ty); + SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), + Op, Ty); UniqueSCEVs.InsertNode(S, IP); return S; } @@ -1000,12 +1003,10 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, Ty = getEffectiveSCEVType(Ty); // Fold if the operand is constant. - if (const SCEVConstant *SC = dyn_cast(Op)) { - const Type *IntTy = getEffectiveSCEVType(Ty); - Constant *C = ConstantExpr::getSExt(SC->getValue(), IntTy); - if (IntTy != Ty) C = ConstantExpr::getIntToPtr(C, Ty); - return getConstant(cast(C)); - } + if (const SCEVConstant *SC = dyn_cast(Op)) + return getConstant( + cast(ConstantExpr::getSExt(SC->getValue(), + getEffectiveSCEVType(Ty)))); // sext(sext(x)) --> sext(x) if (const SCEVSignExtendExpr *SS = dyn_cast(Op)) @@ -1060,9 +1061,7 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, if (MaxBECount == RecastedMaxBECount) { const Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); // Check whether Start+Step*MaxBECount has no signed overflow. - const SCEV *SMul = - getMulExpr(CastedMaxBECount, - getTruncateOrSignExtend(Step, Start->getType())); + const SCEV *SMul = getMulExpr(CastedMaxBECount, Step); const SCEV *Add = getAddExpr(Start, SMul); const SCEV *OperandExtendedAdd = getAddExpr(getSignExtendExpr(Start, WideTy), @@ -1076,9 +1075,7 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, // Similar to above, only this time treat the step value as unsigned. // This covers loops that count up with an unsigned step. - const SCEV *UMul = - getMulExpr(CastedMaxBECount, - getTruncateOrZeroExtend(Step, Start->getType())); + const SCEV *UMul = getMulExpr(CastedMaxBECount, Step); Add = getAddExpr(Start, UMul); OperandExtendedAdd = getAddExpr(getSignExtendExpr(Start, WideTy), @@ -1099,7 +1096,7 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, const SCEV *N = getConstant(APInt::getSignedMinValue(BitWidth) - getSignedRange(Step).getSignedMax()); if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT, AR, N) || - (isLoopGuardedByCond(L, ICmpInst::ICMP_SLT, Start, N) && + (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SLT, Start, N) && isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SLT, AR->getPostIncExpr(*this), N))) // Return the expression with the addrec on the outside. @@ -1110,7 +1107,7 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, const SCEV *N = getConstant(APInt::getSignedMaxValue(BitWidth) - getSignedRange(Step).getSignedMin()); if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT, AR, N) || - (isLoopGuardedByCond(L, ICmpInst::ICMP_SGT, Start, N) && + (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_SGT, Start, N) && isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_SGT, AR->getPostIncExpr(*this), N))) // Return the expression with the addrec on the outside. @@ -1124,8 +1121,8 @@ const SCEV *ScalarEvolution::getSignExtendExpr(const SCEV *Op, // The cast wasn't folded; create an explicit cast node. // Recompute the insert position, as it may have been invalidated. if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); - new (S) SCEVSignExtendExpr(ID, Op, Ty); + SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), + Op, Ty); UniqueSCEVs.InsertNode(S, IP); return S; } @@ -1173,6 +1170,13 @@ const SCEV *ScalarEvolution::getAnyExtendExpr(const SCEV *Op, return getAddRecExpr(Ops, AR->getLoop()); } + // As a special case, fold anyext(undef) to undef. We don't want to + // know too much about SCEVUnknowns, but this special case is handy + // and harmless. + if (const SCEVUnknown *U = dyn_cast(Op)) + if (isa(U->getValue())) + return getSCEV(UndefValue::get(Ty)); + // If the expression is obviously signed, use the sext cast value. if (isa(Op)) return SExt; @@ -1210,23 +1214,34 @@ static bool CollectAddOperandsWithScales(DenseMap &M, SmallVector &NewOps, APInt &AccumulatedConstant, - const SmallVectorImpl &Ops, + const SCEV *const *Ops, size_t NumOperands, const APInt &Scale, ScalarEvolution &SE) { bool Interesting = false; - // Iterate over the add operands. - for (unsigned i = 0, e = Ops.size(); i != e; ++i) { + // Iterate over the add operands. They are sorted, with constants first. + unsigned i = 0; + while (const SCEVConstant *C = dyn_cast(Ops[i])) { + ++i; + // Pull a buried constant out to the outside. + if (Scale != 1 || AccumulatedConstant != 0 || C->getValue()->isZero()) + Interesting = true; + AccumulatedConstant += Scale * C->getValue()->getValue(); + } + + // Next comes everything else. We're especially interested in multiplies + // here, but they're in the middle, so just visit the rest with one loop. + for (; i != NumOperands; ++i) { const SCEVMulExpr *Mul = dyn_cast(Ops[i]); if (Mul && isa(Mul->getOperand(0))) { APInt NewScale = Scale * cast(Mul->getOperand(0))->getValue()->getValue(); if (Mul->getNumOperands() == 2 && isa(Mul->getOperand(1))) { // A multiplication of a constant with another add; recurse. + const SCEVAddExpr *Add = cast(Mul->getOperand(1)); Interesting |= CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant, - cast(Mul->getOperand(1)) - ->getOperands(), + Add->op_begin(), Add->getNumOperands(), NewScale, SE); } else { // A multiplication of a constant with some other value. Update @@ -1244,11 +1259,6 @@ CollectAddOperandsWithScales(DenseMap &M, Interesting = true; } } - } else if (const SCEVConstant *C = dyn_cast(Ops[i])) { - // Pull a buried constant out to the outside. - if (Scale != 1 || AccumulatedConstant != 0 || C->isZero()) - Interesting = true; - AccumulatedConstant += Scale * C->getValue()->getValue(); } else { // An ordinary operand. Update the map. std::pair::iterator, bool> Pair = @@ -1282,9 +1292,9 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, assert(!Ops.empty() && "Cannot get empty add!"); 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 && "SCEVAddExpr operand types don't match!"); #endif @@ -1317,13 +1327,13 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, } // If we are left with a constant zero being added, strip it off. - if (cast(Ops[0])->getValue()->isZero()) { + if (LHSC->getValue()->isZero()) { Ops.erase(Ops.begin()); --Idx; } - } - if (Ops.size() == 1) return Ops[0]; + 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 @@ -1333,7 +1343,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, 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 = getIntegerSCEV(2, Ty); + const SCEV *Two = getConstant(Ty, 2); const SCEV *Mul = getMulExpr(Ops[i], Two); if (Ops.size() == 2) return Mul; @@ -1362,9 +1372,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, } LargeOps.push_back(T->getOperand()); } else if (const SCEVConstant *C = dyn_cast(Ops[i])) { - // This could be either sign or zero extension, but sign extension - // is much more likely to be foldable here. - LargeOps.push_back(getSignExtendExpr(C, SrcType)); + LargeOps.push_back(getAnyExtendExpr(C, SrcType)); } else if (const SCEVMulExpr *M = dyn_cast(Ops[i])) { SmallVector LargeMulOps; for (unsigned j = 0, f = M->getNumOperands(); j != f && Ok; ++j) { @@ -1377,9 +1385,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, LargeMulOps.push_back(T->getOperand()); } else if (const SCEVConstant *C = dyn_cast(M->getOperand(j))) { - // This could be either sign or zero extension, but sign extension - // is much more likely to be foldable here. - LargeMulOps.push_back(getSignExtendExpr(C, SrcType)); + LargeMulOps.push_back(getAnyExtendExpr(C, SrcType)); } else { Ok = false; break; @@ -1411,14 +1417,14 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, while (const SCEVAddExpr *Add = dyn_cast(Ops[Idx])) { // If we have an add, expand the add operands onto the end of the operands // list. - Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); Ops.erase(Ops.begin()+Idx); + Ops.append(Add->op_begin(), Add->op_end()); DeletedAdd = true; } // If we deleted at least one add, we added operands to the end of the list, // and they are not necessarily sorted. Recurse to resort and resimplify - // any operands we just aquired. + // any operands we just acquired. if (DeletedAdd) return getAddExpr(Ops); } @@ -1435,7 +1441,8 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, SmallVector NewOps; APInt AccumulatedConstant(BitWidth, 0); if (CollectAddOperandsWithScales(M, NewOps, AccumulatedConstant, - Ops, APInt(BitWidth, 1), *this)) { + Ops.data(), Ops.size(), + APInt(BitWidth, 1), *this)) { // Some interesting folding opportunity is present, so its worthwhile to // re-generate the operands list. Group the operands by constant scale, // to avoid multiplying by the same constant scale multiple times. @@ -1453,7 +1460,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, Ops.push_back(getMulExpr(getConstant(I->first), getAddExpr(I->second))); if (Ops.empty()) - return getIntegerSCEV(0, Ty); + return getConstant(Ty, 0); if (Ops.size() == 1) return Ops[0]; return getAddExpr(Ops); @@ -1478,7 +1485,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, MulOps.erase(MulOps.begin()+MulOp); InnerMul = getMulExpr(MulOps); } - const SCEV *One = getIntegerSCEV(1, Ty); + const SCEV *One = getConstant(Ty, 1); const SCEV *AddOne = getAddExpr(InnerMul, One); const SCEV *OuterMul = getMulExpr(AddOne, Ops[AddOp]); if (Ops.size() == 2) return OuterMul; @@ -1542,8 +1549,9 @@ const SCEV *ScalarEvolution::getAddExpr(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 (Ops[i]->isLoopInvariant(AddRecLoop)) { LIOps.push_back(Ops[i]); Ops.erase(Ops.begin()+i); --i; --e; @@ -1558,9 +1566,11 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, AddRec->op_end()); AddRecOps[0] = getAddExpr(LIOps); - // It's tempting to propagate NUW/NSW flags here, but nuw/nsw addition - // is not associative so this isn't necessarily safe. - const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRec->getLoop()); + // Build the new addrec. Propagate the NUW and NSW flags if both the + // outer add and the inner addrec are guaranteed to have no overflow. + const SCEV *NewRec = getAddRecExpr(AddRecOps, AddRecLoop, + HasNUW && AddRec->hasNoUnsignedWrap(), + HasNSW && AddRec->hasNoSignedWrap()); // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; @@ -1581,19 +1591,19 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, OtherIdx < Ops.size() && isa(Ops[OtherIdx]);++OtherIdx) if (OtherIdx != Idx) { const SCEVAddRecExpr *OtherAddRec = cast(Ops[OtherIdx]); - if (AddRec->getLoop() == OtherAddRec->getLoop()) { + 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.insert(NewOps.end(), OtherAddRec->op_begin()+i, + NewOps.append(OtherAddRec->op_begin()+i, OtherAddRec->op_end()); break; } NewOps[i] = getAddExpr(NewOps[i], OtherAddRec->getOperand(i)); } - const SCEV *NewAddRec = getAddRecExpr(NewOps, AddRec->getLoop()); + const SCEV *NewAddRec = getAddRecExpr(NewOps, AddRecLoop); if (Ops.size() == 2) return NewAddRec; @@ -1619,8 +1629,10 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl &Ops, SCEVAddExpr *S = static_cast(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)); if (!S) { - S = SCEVAllocator.Allocate(); - new (S) SCEVAddExpr(ID, Ops); + const SCEV **O = SCEVAllocator.Allocate(Ops.size()); + std::uninitialized_copy(Ops.begin(), Ops.end(), O); + S = new (SCEVAllocator) SCEVAddExpr(ID.Intern(SCEVAllocator), + O, Ops.size()); UniqueSCEVs.InsertNode(S, IP); } if (HasNUW) S->setHasNoUnsignedWrap(true); @@ -1703,29 +1715,29 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops, return getAddExpr(NewOps); } } + + if (Ops.size() == 1) + return Ops[0]; } // Skip over the add expression until we get to a multiply. while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scMulExpr) ++Idx; - if (Ops.size() == 1) - return Ops[0]; - // If there are mul operands inline them all into this expression. if (Idx < Ops.size()) { bool DeletedMul = false; while (const SCEVMulExpr *Mul = dyn_cast(Ops[Idx])) { // If we have an mul, expand the mul operands onto the end of the operands // list. - Ops.insert(Ops.end(), Mul->op_begin(), Mul->op_end()); Ops.erase(Ops.begin()+Idx); + Ops.append(Mul->op_begin(), Mul->op_end()); DeletedMul = true; } // If we deleted at least one mul, we added operands to the end of the list, // and they are not necessarily sorted. Recurse to resort and resimplify - // any operands we just aquired. + // any operands we just acquired. if (DeletedMul) return getMulExpr(Ops); } @@ -1754,23 +1766,15 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops, // NLI * LI * {Start,+,Step} --> NLI * {LI*Start,+,LI*Step} SmallVector NewOps; NewOps.reserve(AddRec->getNumOperands()); - if (LIOps.size() == 1) { - const SCEV *Scale = LIOps[0]; - for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) - NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i))); - } else { - for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { - SmallVector MulOps(LIOps.begin(), LIOps.end()); - MulOps.push_back(AddRec->getOperand(i)); - NewOps.push_back(getMulExpr(MulOps)); - } - } + const SCEV *Scale = getMulExpr(LIOps); + for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) + NewOps.push_back(getMulExpr(Scale, AddRec->getOperand(i))); - // It's tempting to propagate the NSW flag here, but nsw multiplication - // is not associative so this isn't necessarily safe. + // 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(), HasNUW && AddRec->hasNoUnsignedWrap(), - /*HasNSW=*/false); + HasNSW && AddRec->hasNoSignedWrap()); // If all of the other operands were loop invariant, we are done. if (Ops.size() == 1) return NewRec; @@ -1827,8 +1831,10 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl &Ops, SCEVMulExpr *S = static_cast(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)); if (!S) { - S = SCEVAllocator.Allocate(); - new (S) SCEVMulExpr(ID, Ops); + const SCEV **O = SCEVAllocator.Allocate(Ops.size()); + std::uninitialized_copy(Ops.begin(), Ops.end(), O); + S = new (SCEVAllocator) SCEVMulExpr(ID.Intern(SCEVAllocator), + O, Ops.size()); UniqueSCEVs.InsertNode(S, IP); } if (HasNUW) S->setHasNoUnsignedWrap(true); @@ -1847,79 +1853,81 @@ const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, if (const SCEVConstant *RHSC = dyn_cast(RHS)) { if (RHSC->getValue()->equalsInt(1)) return LHS; // X udiv 1 --> x - if (RHSC->isZero()) - return getIntegerSCEV(0, LHS->getType()); // value is undefined - - // Determine if the division can be folded into the operands of - // its operands. - // TODO: Generalize this to non-constants by using known-bits information. - const Type *Ty = LHS->getType(); - unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros(); - unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ; - // For non-power-of-two values, effectively round the value up to the - // nearest power of two. - if (!RHSC->getValue()->getValue().isPowerOf2()) - ++MaxShiftAmt; - const IntegerType *ExtTy = - IntegerType::get(getContext(), getTypeSizeInBits(Ty) + MaxShiftAmt); - // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded. - if (const SCEVAddRecExpr *AR = dyn_cast(LHS)) - if (const SCEVConstant *Step = - dyn_cast(AR->getStepRecurrence(*this))) - if (!Step->getValue()->getValue() - .urem(RHSC->getValue()->getValue()) && - getZeroExtendExpr(AR, ExtTy) == - getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), - getZeroExtendExpr(Step, ExtTy), - AR->getLoop())) { - SmallVector Operands; - for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i) - Operands.push_back(getUDivExpr(AR->getOperand(i), RHS)); - return getAddRecExpr(Operands, AR->getLoop()); - } - // (A*B)/C --> A*(B/C) if safe and B/C can be folded. - if (const SCEVMulExpr *M = dyn_cast(LHS)) { - SmallVector Operands; - for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) - Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy)); - if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands)) - // Find an operand that's safely divisible. - for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) { - const SCEV *Op = M->getOperand(i); - const SCEV *Div = getUDivExpr(Op, RHSC); - if (!isa(Div) && getMulExpr(Div, RHSC) == Op) { - const SmallVectorImpl &MOperands = M->getOperands(); - Operands = SmallVector(MOperands.begin(), - MOperands.end()); - Operands[i] = Div; - return getMulExpr(Operands); + // If the denominator is zero, the result of the udiv is undefined. Don't + // try to analyze it, because the resolution chosen here may differ from + // the resolution chosen in other parts of the compiler. + if (!RHSC->getValue()->isZero()) { + // Determine if the division can be folded into the operands of + // its operands. + // TODO: Generalize this to non-constants by using known-bits information. + const Type *Ty = LHS->getType(); + unsigned LZ = RHSC->getValue()->getValue().countLeadingZeros(); + unsigned MaxShiftAmt = getTypeSizeInBits(Ty) - LZ; + // For non-power-of-two values, effectively round the value up to the + // nearest power of two. + if (!RHSC->getValue()->getValue().isPowerOf2()) + ++MaxShiftAmt; + const IntegerType *ExtTy = + IntegerType::get(getContext(), getTypeSizeInBits(Ty) + MaxShiftAmt); + // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded. + if (const SCEVAddRecExpr *AR = dyn_cast(LHS)) + if (const SCEVConstant *Step = + dyn_cast(AR->getStepRecurrence(*this))) + if (!Step->getValue()->getValue() + .urem(RHSC->getValue()->getValue()) && + getZeroExtendExpr(AR, ExtTy) == + getAddRecExpr(getZeroExtendExpr(AR->getStart(), ExtTy), + getZeroExtendExpr(Step, ExtTy), + AR->getLoop())) { + SmallVector Operands; + for (unsigned i = 0, e = AR->getNumOperands(); i != e; ++i) + Operands.push_back(getUDivExpr(AR->getOperand(i), RHS)); + return getAddRecExpr(Operands, AR->getLoop()); } + // (A*B)/C --> A*(B/C) if safe and B/C can be folded. + if (const SCEVMulExpr *M = dyn_cast(LHS)) { + SmallVector Operands; + for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) + Operands.push_back(getZeroExtendExpr(M->getOperand(i), ExtTy)); + if (getZeroExtendExpr(M, ExtTy) == getMulExpr(Operands)) + // Find an operand that's safely divisible. + for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) { + const SCEV *Op = M->getOperand(i); + const SCEV *Div = getUDivExpr(Op, RHSC); + if (!isa(Div) && getMulExpr(Div, RHSC) == Op) { + Operands = SmallVector(M->op_begin(), + M->op_end()); + Operands[i] = Div; + return getMulExpr(Operands); + } + } + } + // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded. + if (const SCEVAddRecExpr *A = dyn_cast(LHS)) { + SmallVector Operands; + for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) + Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy)); + if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) { + Operands.clear(); + for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) { + const SCEV *Op = getUDivExpr(A->getOperand(i), RHS); + if (isa(Op) || + getMulExpr(Op, RHS) != A->getOperand(i)) + break; + Operands.push_back(Op); + } + if (Operands.size() == A->getNumOperands()) + return getAddExpr(Operands); } - } - // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded. - if (const SCEVAddRecExpr *A = dyn_cast(LHS)) { - SmallVector Operands; - for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) - Operands.push_back(getZeroExtendExpr(A->getOperand(i), ExtTy)); - if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) { - Operands.clear(); - for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) { - const SCEV *Op = getUDivExpr(A->getOperand(i), RHS); - if (isa(Op) || getMulExpr(Op, RHS) != A->getOperand(i)) - break; - Operands.push_back(Op); - } - if (Operands.size() == A->getNumOperands()) - return getAddExpr(Operands); } - } - // Fold if both operands are constant. - if (const SCEVConstant *LHSC = dyn_cast(LHS)) { - Constant *LHSCV = LHSC->getValue(); - Constant *RHSCV = RHSC->getValue(); - return getConstant(cast(ConstantExpr::getUDiv(LHSCV, - RHSCV))); + // Fold if both operands are constant. + if (const SCEVConstant *LHSC = dyn_cast(LHS)) { + Constant *LHSCV = LHSC->getValue(); + Constant *RHSCV = RHSC->getValue(); + return getConstant(cast(ConstantExpr::getUDiv(LHSCV, + RHSCV))); + } } } @@ -1929,8 +1937,8 @@ const SCEV *ScalarEvolution::getUDivExpr(const SCEV *LHS, ID.AddPointer(RHS); void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); - new (S) SCEVUDivExpr(ID, LHS, RHS); + SCEV *S = new (SCEVAllocator) SCEVUDivExpr(ID.Intern(SCEVAllocator), + LHS, RHS); UniqueSCEVs.InsertNode(S, IP); return S; } @@ -1945,8 +1953,7 @@ const SCEV *ScalarEvolution::getAddRecExpr(const SCEV *Start, Operands.push_back(Start); if (const SCEVAddRecExpr *StepChrec = dyn_cast(Step)) if (StepChrec->getLoop() == L) { - Operands.insert(Operands.end(), StepChrec->op_begin(), - StepChrec->op_end()); + Operands.append(StepChrec->op_begin(), StepChrec->op_end()); return getAddRecExpr(Operands, L); } @@ -1973,6 +1980,12 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, return getAddRecExpr(Operands, L, HasNUW, HasNSW); // {X,+,0} --> X } + // It's tempting to want to call getMaxBackedgeTakenCount count here and + // use that information to infer NUW and NSW flags. However, computing a + // BE count requires calling getAddRecExpr, so we may not yet have a + // meaningful BE count at this point (and if we don't, we'd be stuck + // with a SCEVCouldNotCompute as the cached BE count). + // If HasNSW is true and all the operands are non-negative, infer HasNUW. if (!HasNUW && HasNSW) { bool All = true; @@ -2032,8 +2045,10 @@ ScalarEvolution::getAddRecExpr(SmallVectorImpl &Operands, SCEVAddRecExpr *S = static_cast(UniqueSCEVs.FindNodeOrInsertPos(ID, IP)); if (!S) { - S = SCEVAllocator.Allocate(); - new (S) SCEVAddRecExpr(ID, Operands, L); + const SCEV **O = SCEVAllocator.Allocate(Operands.size()); + std::uninitialized_copy(Operands.begin(), Operands.end(), O); + S = new (SCEVAllocator) SCEVAddRecExpr(ID.Intern(SCEVAllocator), + O, Operands.size(), L); UniqueSCEVs.InsertNode(S, IP); } if (HasNUW) S->setHasNoUnsignedWrap(true); @@ -2088,9 +2103,9 @@ ScalarEvolution::getSMaxExpr(SmallVectorImpl &Ops) { // maximum-int. return Ops[0]; } - } - if (Ops.size() == 1) return Ops[0]; + if (Ops.size() == 1) return Ops[0]; + } // Find the first SMax while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr) @@ -2101,8 +2116,8 @@ ScalarEvolution::getSMaxExpr(SmallVectorImpl &Ops) { if (Idx < Ops.size()) { bool DeletedSMax = false; while (const SCEVSMaxExpr *SMax = dyn_cast(Ops[Idx])) { - Ops.insert(Ops.end(), SMax->op_begin(), SMax->op_end()); Ops.erase(Ops.begin()+Idx); + Ops.append(SMax->op_begin(), SMax->op_end()); DeletedSMax = true; } @@ -2114,7 +2129,13 @@ ScalarEvolution::getSMaxExpr(SmallVectorImpl &Ops) { // 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 smax Y smax Y --> X smax Y + // X smax Y smax Y --> X smax Y + // X smax Y --> X, if X is always greater than Y + if (Ops[i] == Ops[i+1] || + isKnownPredicate(ICmpInst::ICMP_SGE, Ops[i], Ops[i+1])) { + Ops.erase(Ops.begin()+i+1, Ops.begin()+i+2); + --i; --e; + } else if (isKnownPredicate(ICmpInst::ICMP_SLE, Ops[i], Ops[i+1])) { Ops.erase(Ops.begin()+i, Ops.begin()+i+1); --i; --e; } @@ -2132,8 +2153,10 @@ ScalarEvolution::getSMaxExpr(SmallVectorImpl &Ops) { ID.AddPointer(Ops[i]); void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); - new (S) SCEVSMaxExpr(ID, Ops); + const SCEV **O = SCEVAllocator.Allocate(Ops.size()); + std::uninitialized_copy(Ops.begin(), Ops.end(), O); + SCEV *S = new (SCEVAllocator) SCEVSMaxExpr(ID.Intern(SCEVAllocator), + O, Ops.size()); UniqueSCEVs.InsertNode(S, IP); return S; } @@ -2185,9 +2208,9 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl &Ops) { // maximum-int. return Ops[0]; } - } - if (Ops.size() == 1) return Ops[0]; + if (Ops.size() == 1) return Ops[0]; + } // Find the first UMax while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr) @@ -2198,8 +2221,8 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl &Ops) { if (Idx < Ops.size()) { bool DeletedUMax = false; while (const SCEVUMaxExpr *UMax = dyn_cast(Ops[Idx])) { - Ops.insert(Ops.end(), UMax->op_begin(), UMax->op_end()); Ops.erase(Ops.begin()+Idx); + Ops.append(UMax->op_begin(), UMax->op_end()); DeletedUMax = true; } @@ -2211,7 +2234,13 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl &Ops) { // 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 + // X umax Y umax Y --> X umax Y + // X umax Y --> X, if X is always greater than Y + if (Ops[i] == Ops[i+1] || + isKnownPredicate(ICmpInst::ICMP_UGE, Ops[i], Ops[i+1])) { + Ops.erase(Ops.begin()+i+1, Ops.begin()+i+2); + --i; --e; + } else if (isKnownPredicate(ICmpInst::ICMP_ULE, Ops[i], Ops[i+1])) { Ops.erase(Ops.begin()+i, Ops.begin()+i+1); --i; --e; } @@ -2229,8 +2258,10 @@ ScalarEvolution::getUMaxExpr(SmallVectorImpl &Ops) { ID.AddPointer(Ops[i]); void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); - new (S) SCEVUMaxExpr(ID, Ops); + const SCEV **O = SCEVAllocator.Allocate(Ops.size()); + std::uninitialized_copy(Ops.begin(), Ops.end(), O); + SCEV *S = new (SCEVAllocator) SCEVUMaxExpr(ID.Intern(SCEVAllocator), + O, Ops.size()); UniqueSCEVs.InsertNode(S, IP); return S; } @@ -2248,9 +2279,17 @@ const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, } const SCEV *ScalarEvolution::getSizeOfExpr(const Type *AllocTy) { + // If we have TargetData, we can bypass creating a target-independent + // constant expression and then folding it back into a ConstantInt. + // This is just a compile-time optimization. + if (TD) + return getConstant(TD->getIntPtrType(getContext()), + TD->getTypeAllocSize(AllocTy)); + Constant *C = ConstantExpr::getSizeOf(AllocTy); if (ConstantExpr *CE = dyn_cast(C)) - C = ConstantFoldConstantExpression(CE, TD); + if (Constant *Folded = ConstantFoldConstantExpression(CE, TD)) + C = Folded; const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy)); return getTruncateOrZeroExtend(getSCEV(C), Ty); } @@ -2258,16 +2297,25 @@ const SCEV *ScalarEvolution::getSizeOfExpr(const Type *AllocTy) { const SCEV *ScalarEvolution::getAlignOfExpr(const Type *AllocTy) { Constant *C = ConstantExpr::getAlignOf(AllocTy); if (ConstantExpr *CE = dyn_cast(C)) - C = ConstantFoldConstantExpression(CE, TD); + if (Constant *Folded = ConstantFoldConstantExpression(CE, TD)) + C = Folded; const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(AllocTy)); return getTruncateOrZeroExtend(getSCEV(C), Ty); } const SCEV *ScalarEvolution::getOffsetOfExpr(const StructType *STy, unsigned FieldNo) { + // If we have TargetData, we can bypass creating a target-independent + // constant expression and then folding it back into a ConstantInt. + // This is just a compile-time optimization. + if (TD) + return getConstant(TD->getIntPtrType(getContext()), + TD->getStructLayout(STy)->getElementOffset(FieldNo)); + Constant *C = ConstantExpr::getOffsetOf(STy, FieldNo); if (ConstantExpr *CE = dyn_cast(C)) - C = ConstantFoldConstantExpression(CE, TD); + if (Constant *Folded = ConstantFoldConstantExpression(CE, TD)) + C = Folded; const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(STy)); return getTruncateOrZeroExtend(getSCEV(C), Ty); } @@ -2276,7 +2324,8 @@ const SCEV *ScalarEvolution::getOffsetOfExpr(const Type *CTy, Constant *FieldNo) { Constant *C = ConstantExpr::getOffsetOf(CTy, FieldNo); if (ConstantExpr *CE = dyn_cast(C)) - C = ConstantFoldConstantExpression(CE, TD); + if (Constant *Folded = ConstantFoldConstantExpression(CE, TD)) + C = Folded; const Type *Ty = getEffectiveSCEVType(PointerType::getUnqual(CTy)); return getTruncateOrZeroExtend(getSCEV(C), Ty); } @@ -2292,8 +2341,7 @@ const SCEV *ScalarEvolution::getUnknown(Value *V) { ID.AddPointer(V); void *IP = 0; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - SCEV *S = SCEVAllocator.Allocate(); - new (S) SCEVUnknown(ID, V); + SCEV *S = new (SCEVAllocator) SCEVUnknown(ID.Intern(SCEVAllocator), V); UniqueSCEVs.InsertNode(S, IP); return S; } @@ -2364,13 +2412,6 @@ const SCEV *ScalarEvolution::getSCEV(Value *V) { return S; } -/// getIntegerSCEV - Given a SCEVable type, create a constant for the -/// specified signed integer value and return a SCEV for the constant. -const SCEV *ScalarEvolution::getIntegerSCEV(int64_t Val, const Type *Ty) { - const IntegerType *ITy = cast(getEffectiveSCEVType(Ty)); - return getConstant(ConstantInt::get(ITy, Val)); -} - /// getNegativeSCEV - Return a SCEV corresponding to -V = -1*V /// const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V) { @@ -2401,6 +2442,10 @@ const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { /// const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS) { + // Fast path: X - X --> 0. + if (LHS == RHS) + return getConstant(LHS->getType(), 0); + // X - Y --> X + -Y return getAddExpr(LHS, getNegativeSCEV(RHS)); } @@ -2551,12 +2596,12 @@ PushDefUseChildren(Instruction *I, /// the Scalars map if they reference SymName. This is used during PHI /// resolution. void -ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) { +ScalarEvolution::ForgetSymbolicName(Instruction *PN, const SCEV *SymName) { SmallVector Worklist; - PushDefUseChildren(I, Worklist); + PushDefUseChildren(PN, Worklist); SmallPtrSet Visited; - Visited.insert(I); + Visited.insert(PN); while (!Worklist.empty()) { Instruction *I = Worklist.pop_back_val(); if (!Visited.insert(I)) continue; @@ -2570,12 +2615,15 @@ ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) { continue; // 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)) { + // structure, it's a PHI that's in the progress of being computed + // by createNodeForPHI, or it's a single-value PHI. In the first case, + // additional loop trip count information isn't going to change anything. + // In the second case, createNodeForPHI will perform the necessary + // 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); } @@ -2589,14 +2637,29 @@ ScalarEvolution::ForgetSymbolicName(Instruction *I, const SCEV *SymName) { /// a loop header, making it a potential recurrence, or it doesn't. /// const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { - if (PN->getNumIncomingValues() == 2) // The loops have been canonicalized. - if (const Loop *L = LI->getLoopFor(PN->getParent())) - if (L->getHeader() == PN->getParent()) { - // If it lives in the loop header, it has two incoming values, one - // from outside the loop, and one from inside. - unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); - unsigned BackEdge = IncomingEdge^1; - + if (const Loop *L = LI->getLoopFor(PN->getParent())) + if (L->getHeader() == PN->getParent()) { + // The loop may have multiple entrances or multiple exits; we can analyze + // this phi as an addrec if it has a unique entry value and a unique + // backedge value. + Value *BEValueV = 0, *StartValueV = 0; + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { + Value *V = PN->getIncomingValue(i); + if (L->contains(PN->getIncomingBlock(i))) { + if (!BEValueV) { + BEValueV = V; + } else if (BEValueV != V) { + BEValueV = 0; + break; + } + } else if (!StartValueV) { + StartValueV = V; + } else if (StartValueV != V) { + StartValueV = 0; + break; + } + } + 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() && @@ -2605,7 +2668,6 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { // Using this symbolic name for the PHI, analyze the value coming around // the back-edge. - Value *BEValueV = PN->getIncomingValue(BackEdge); const SCEV *BEValue = getSCEV(BEValueV); // NOTE: If BEValue is loop invariant, we know that the PHI node just @@ -2649,8 +2711,7 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { HasNSW = true; } - const SCEV *StartVal = - getSCEV(PN->getIncomingValue(IncomingEdge)); + const SCEV *StartVal = getSCEV(StartValueV); const SCEV *PHISCEV = getAddRecExpr(StartVal, Accum, L, HasNUW, HasNSW); @@ -2676,12 +2737,12 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { // Because the other in-value of i (0) fits the evolution of BEValue // i really is an addrec evolution. if (AddRec->getLoop() == L && AddRec->isAffine()) { - const SCEV *StartVal = getSCEV(PN->getIncomingValue(IncomingEdge)); + const SCEV *StartVal = getSCEV(StartValueV); // If StartVal = j.start - j.stride, we can use StartVal as the // initial step of the addrec evolution. if (StartVal == getMinusSCEV(AddRec->getOperand(0), - AddRec->getOperand(1))) { + AddRec->getOperand(1))) { const SCEV *PHISCEV = getAddRecExpr(StartVal, AddRec->getOperand(1), L); @@ -2694,13 +2755,24 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { } } } - - return SymbolicName; } + } - // It's tempting to recognize PHIs with a unique incoming value, however - // this leads passes like indvars to break LCSSA form. Fortunately, such - // PHIs are rare, as instcombine zaps them. + // If the PHI has a single incoming value, follow that value, unless the + // 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) + return getSCEV(V); + } // If it's not a loop phi, we can't handle it yet. return getUnknown(PN); @@ -2711,13 +2783,17 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) { /// const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { - bool InBounds = GEP->isInBounds(); + // Don't blindly transfer the inbounds flag from the GEP instruction to the + // 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. + const Type *IntPtrTy = getEffectiveSCEVType(GEP->getType()); Value *Base = GEP->getOperand(0); // Don't attempt to analyze GEPs over unsized objects. if (!cast(Base->getType())->getElementType()->isSized()) return getUnknown(GEP); - const SCEV *TotalOffset = getIntegerSCEV(0, IntPtrTy); + const SCEV *TotalOffset = getConstant(IntPtrTy, 0); gep_type_iterator GTI = gep_type_begin(GEP); for (GetElementPtrInst::op_iterator I = next(GEP->op_begin()), E = GEP->op_end(); @@ -2727,23 +2803,30 @@ const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { if (const StructType *STy = dyn_cast(*GTI++)) { // For a struct, add the member offset. unsigned FieldNo = cast(Index)->getZExtValue(); - TotalOffset = getAddExpr(TotalOffset, - getOffsetOfExpr(STy, FieldNo), - /*HasNUW=*/false, /*HasNSW=*/InBounds); + const SCEV *FieldOffset = getOffsetOfExpr(STy, FieldNo); + + // Add the field offset to the running total offset. + TotalOffset = getAddExpr(TotalOffset, FieldOffset); } else { // For an array, add the element offset, explicitly scaled. - const SCEV *LocalOffset = getSCEV(Index); - // Getelementptr indicies are signed. - LocalOffset = getTruncateOrSignExtend(LocalOffset, IntPtrTy); - // Lower "inbounds" GEPs to NSW arithmetic. - LocalOffset = getMulExpr(LocalOffset, getSizeOfExpr(*GTI), - /*HasNUW=*/false, /*HasNSW=*/InBounds); - TotalOffset = getAddExpr(TotalOffset, LocalOffset, - /*HasNUW=*/false, /*HasNSW=*/InBounds); + const SCEV *ElementSize = getSizeOfExpr(*GTI); + const SCEV *IndexS = getSCEV(Index); + // Getelementptr indices are signed. + IndexS = getTruncateOrSignExtend(IndexS, IntPtrTy); + + // Multiply the index by the element size to compute the element offset. + const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize); + + // Add the element offset to the running total offset. + TotalOffset = getAddExpr(TotalOffset, LocalOffset); } } - return getAddExpr(getSCEV(Base), TotalOffset, - /*HasNUW=*/false, /*HasNSW=*/InBounds); + + // Get the SCEV for the GEP base. + const SCEV *BaseS = getSCEV(Base); + + // Add the total offset from all the GEP indices to the base. + return getAddExpr(BaseS, TotalOffset); } /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is @@ -2900,9 +2983,10 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { // initial value. if (AddRec->hasNoUnsignedWrap()) if (const SCEVConstant *C = dyn_cast(AddRec->getStart())) - ConservativeResult = - ConstantRange(C->getValue()->getValue(), - APInt(getTypeSizeInBits(C->getType()), 0)); + if (!C->getValue()->isZero()) + ConservativeResult = + ConservativeResult.intersectWith( + ConstantRange(C->getValue()->getValue(), APInt(BitWidth, 0))); // TODO: non-affine addrec if (AddRec->isAffine()) { @@ -2913,14 +2997,26 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty); const SCEV *Start = AddRec->getStart(); - const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this); + const SCEV *Step = AddRec->getStepRecurrence(*this); - // Check for overflow. - if (!AddRec->hasNoUnsignedWrap()) + ConstantRange StartRange = getUnsignedRange(Start); + ConstantRange StepRange = getSignedRange(Step); + ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount); + ConstantRange EndRange = + StartRange.add(MaxBECountRange.multiply(StepRange)); + + // Check for overflow. This must be done with ConstantRange arithmetic + // because we could be called from within the ScalarEvolution overflow + // checking code. + ConstantRange ExtStartRange = StartRange.zextOrTrunc(BitWidth*2+1); + ConstantRange ExtStepRange = StepRange.sextOrTrunc(BitWidth*2+1); + ConstantRange ExtMaxBECountRange = + MaxBECountRange.zextOrTrunc(BitWidth*2+1); + ConstantRange ExtEndRange = EndRange.zextOrTrunc(BitWidth*2+1); + if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) != + ExtEndRange) return ConservativeResult; - ConstantRange StartRange = getUnsignedRange(Start); - ConstantRange EndRange = getUnsignedRange(End); APInt Min = APIntOps::umin(StartRange.getUnsignedMin(), EndRange.getUnsignedMin()); APInt Max = APIntOps::umax(StartRange.getUnsignedMax(), @@ -2936,7 +3032,6 @@ ScalarEvolution::getUnsignedRange(const SCEV *S) { if (const SCEVUnknown *U = dyn_cast(S)) { // For a SCEVUnknown, ask ValueTracking. - unsigned BitWidth = getTypeSizeInBits(U->getType()); APInt Mask = APInt::getAllOnesValue(BitWidth); APInt Zeros(BitWidth, 0), Ones(BitWidth, 0); ComputeMaskedBits(U->getValue(), Mask, Zeros, Ones, TD); @@ -3045,14 +3140,26 @@ ScalarEvolution::getSignedRange(const SCEV *S) { MaxBECount = getNoopOrZeroExtend(MaxBECount, Ty); const SCEV *Start = AddRec->getStart(); - const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this); + const SCEV *Step = AddRec->getStepRecurrence(*this); - // Check for overflow. - if (!AddRec->hasNoSignedWrap()) + ConstantRange StartRange = getSignedRange(Start); + ConstantRange StepRange = getSignedRange(Step); + ConstantRange MaxBECountRange = getUnsignedRange(MaxBECount); + ConstantRange EndRange = + StartRange.add(MaxBECountRange.multiply(StepRange)); + + // Check for overflow. This must be done with ConstantRange arithmetic + // because we could be called from within the ScalarEvolution overflow + // checking code. + ConstantRange ExtStartRange = StartRange.sextOrTrunc(BitWidth*2+1); + ConstantRange ExtStepRange = StepRange.sextOrTrunc(BitWidth*2+1); + ConstantRange ExtMaxBECountRange = + MaxBECountRange.zextOrTrunc(BitWidth*2+1); + ConstantRange ExtEndRange = EndRange.sextOrTrunc(BitWidth*2+1); + if (ExtStartRange.add(ExtMaxBECountRange.multiply(ExtStepRange)) != + ExtEndRange) return ConservativeResult; - ConstantRange StartRange = getSignedRange(Start); - ConstantRange EndRange = getSignedRange(End); APInt Min = APIntOps::smin(StartRange.getSignedMin(), EndRange.getSignedMin()); APInt Max = APIntOps::smax(StartRange.getSignedMax(), @@ -3089,16 +3196,21 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { return getUnknown(V); unsigned Opcode = Instruction::UserOp1; - if (Instruction *I = dyn_cast(V)) + if (Instruction *I = dyn_cast(V)) { Opcode = I->getOpcode(); - else if (ConstantExpr *CE = dyn_cast(V)) + + // Don't attempt to analyze instructions in blocks that aren't + // reachable. Such instructions don't matter, and they aren't required + // to obey basic rules for definitions dominating uses which this + // analysis depends on. + if (!DT->isReachableFromEntry(I->getParent())) + return getUnknown(V); + } else if (ConstantExpr *CE = dyn_cast(V)) Opcode = CE->getOpcode(); else if (ConstantInt *CI = dyn_cast(V)) return getConstant(CI); else if (isa(V)) - return getIntegerSCEV(0, V->getType()); - else if (isa(V)) - return getIntegerSCEV(0, V->getType()); + return getConstant(V->getType(), 0); else if (GlobalAlias *GA = dyn_cast(V)) return GA->mayBeOverridden() ? getUnknown(V) : getSCEV(GA->getAliasee()); else @@ -3107,15 +3219,9 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { Operator *U = cast(V); switch (Opcode) { case Instruction::Add: - // Don't transfer the NSW and NUW bits from the Add instruction to the - // 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. return getAddExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); case Instruction::Mul: - // Don't transfer the NSW and NUW bits from the Mul instruction to the - // Mul expression, as with Add. return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(U->getOperand(1))); case Instruction::UDiv: @@ -3208,7 +3314,7 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { const Type *Z0Ty = Z0->getType(); unsigned Z0TySize = getTypeSizeInBits(Z0Ty); - // If C is a low-bits mask, the zero extend is zerving to + // If C is a low-bits mask, the zero extend is serving to // mask off the high bits. Complement the operand and // re-apply the zext. if (APIntOps::isMask(Z0TySize, CI->getValue())) @@ -3230,8 +3336,16 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // Turn shift left of a constant amount into a multiply. if (ConstantInt *SA = dyn_cast(U->getOperand(1))) { uint32_t BitWidth = cast(U->getType())->getBitWidth(); + + // If the shift count is not less than the bitwidth, the result of + // the shift is undefined. Don't try to analyze it, because the + // resolution chosen here may differ from the resolution chosen in + // other parts of the compiler. + if (SA->getValue().uge(BitWidth)) + break; + Constant *X = ConstantInt::get(getContext(), - APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth))); + APInt(BitWidth, 1).shl(SA->getZExtValue())); return getMulExpr(getSCEV(U->getOperand(0)), getSCEV(X)); } break; @@ -3240,8 +3354,16 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // Turn logical shift right of a constant into a unsigned divide. if (ConstantInt *SA = dyn_cast(U->getOperand(1))) { uint32_t BitWidth = cast(U->getType())->getBitWidth(); + + // If the shift count is not less than the bitwidth, the result of + // the shift is undefined. Don't try to analyze it, because the + // resolution chosen here may differ from the resolution chosen in + // other parts of the compiler. + if (SA->getValue().uge(BitWidth)) + break; + Constant *X = ConstantInt::get(getContext(), - APInt(BitWidth, 1).shl(SA->getLimitedValue(BitWidth))); + APInt(BitWidth, 1).shl(SA->getZExtValue())); return getUDivExpr(getSCEV(U->getOperand(0)), getSCEV(X)); } break; @@ -3249,19 +3371,26 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { case Instruction::AShr: // For a two-shift sext-inreg, use sext(trunc(x)) as the SCEV expression. if (ConstantInt *CI = dyn_cast(U->getOperand(1))) - if (Instruction *L = dyn_cast(U->getOperand(0))) + if (Operator *L = dyn_cast(U->getOperand(0))) if (L->getOpcode() == Instruction::Shl && L->getOperand(1) == U->getOperand(1)) { - unsigned BitWidth = getTypeSizeInBits(U->getType()); + uint64_t BitWidth = getTypeSizeInBits(U->getType()); + + // If the shift count is not less than the bitwidth, the result of + // the shift is undefined. Don't try to analyze it, because the + // resolution chosen here may differ from the resolution chosen in + // other parts of the compiler. + if (CI->getValue().uge(BitWidth)) + break; + uint64_t Amt = BitWidth - CI->getZExtValue(); if (Amt == BitWidth) return getSCEV(L->getOperand(0)); // shift by zero --> noop - if (Amt > BitWidth) - return getIntegerSCEV(0, U->getType()); // value is undefined return getSignExtendExpr(getTruncateExpr(getSCEV(L->getOperand(0)), - IntegerType::get(getContext(), Amt)), - U->getType()); + IntegerType::get(getContext(), + Amt)), + U->getType()); } break; @@ -3304,10 +3433,22 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // fall through case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGE: - if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) - return getSMaxExpr(getSCEV(LHS), getSCEV(RHS)); - else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) - return getSMinExpr(getSCEV(LHS), getSCEV(RHS)); + // a >s b ? a+x : b+x -> smax(a, b)+x + // a >s b ? b+x : a+x -> smin(a, b)+x + if (LHS->getType() == U->getType()) { + const SCEV *LS = getSCEV(LHS); + const SCEV *RS = getSCEV(RHS); + const SCEV *LA = getSCEV(U->getOperand(1)); + const SCEV *RA = getSCEV(U->getOperand(2)); + const SCEV *LDiff = getMinusSCEV(LA, LS); + const SCEV *RDiff = getMinusSCEV(RA, RS); + if (LDiff == RDiff) + return getAddExpr(getSMaxExpr(LS, RS), LDiff); + LDiff = getMinusSCEV(LA, RS); + RDiff = getMinusSCEV(RA, LS); + if (LDiff == RDiff) + return getAddExpr(getSMinExpr(LS, RS), LDiff); + } break; case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: @@ -3315,28 +3456,52 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // fall through case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGE: - if (LHS == U->getOperand(1) && RHS == U->getOperand(2)) - return getUMaxExpr(getSCEV(LHS), getSCEV(RHS)); - else if (LHS == U->getOperand(2) && RHS == U->getOperand(1)) - return getUMinExpr(getSCEV(LHS), getSCEV(RHS)); + // a >u b ? a+x : b+x -> umax(a, b)+x + // a >u b ? b+x : a+x -> umin(a, b)+x + if (LHS->getType() == U->getType()) { + const SCEV *LS = getSCEV(LHS); + const SCEV *RS = getSCEV(RHS); + const SCEV *LA = getSCEV(U->getOperand(1)); + const SCEV *RA = getSCEV(U->getOperand(2)); + const SCEV *LDiff = getMinusSCEV(LA, LS); + const SCEV *RDiff = getMinusSCEV(RA, RS); + if (LDiff == RDiff) + return getAddExpr(getUMaxExpr(LS, RS), LDiff); + LDiff = getMinusSCEV(LA, RS); + RDiff = getMinusSCEV(RA, LS); + if (LDiff == RDiff) + return getAddExpr(getUMinExpr(LS, RS), LDiff); + } break; case ICmpInst::ICMP_NE: - // n != 0 ? n : 1 -> umax(n, 1) - if (LHS == U->getOperand(1) && - isa(U->getOperand(2)) && - cast(U->getOperand(2))->isOne() && + // n != 0 ? n+x : 1+x -> umax(n, 1)+x + if (LHS->getType() == U->getType() && isa(RHS) && - cast(RHS)->isZero()) - return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(2))); + cast(RHS)->isZero()) { + const SCEV *One = getConstant(LHS->getType(), 1); + const SCEV *LS = getSCEV(LHS); + const SCEV *LA = getSCEV(U->getOperand(1)); + const SCEV *RA = getSCEV(U->getOperand(2)); + const SCEV *LDiff = getMinusSCEV(LA, LS); + const SCEV *RDiff = getMinusSCEV(RA, One); + if (LDiff == RDiff) + return getAddExpr(getUMaxExpr(LS, One), LDiff); + } break; case ICmpInst::ICMP_EQ: - // n == 0 ? 1 : n -> umax(n, 1) - if (LHS == U->getOperand(2) && - isa(U->getOperand(1)) && - cast(U->getOperand(1))->isOne() && + // n == 0 ? 1+x : n+x -> umax(n, 1)+x + if (LHS->getType() == U->getType() && isa(RHS) && - cast(RHS)->isZero()) - return getUMaxExpr(getSCEV(LHS), getSCEV(U->getOperand(1))); + cast(RHS)->isZero()) { + const SCEV *One = getConstant(LHS->getType(), 1); + const SCEV *LS = getSCEV(LHS); + const SCEV *LA = getSCEV(U->getOperand(1)); + const SCEV *RA = getSCEV(U->getOperand(2)); + const SCEV *LDiff = getMinusSCEV(LA, One); + const SCEV *RDiff = getMinusSCEV(RA, LS); + if (LDiff == RDiff) + return getAddExpr(getUMaxExpr(LS, One), LDiff); + } break; default: break; @@ -3393,7 +3558,7 @@ PushLoopPHIs(const Loop *L, SmallVectorImpl &Worklist) { const ScalarEvolution::BackedgeTakenInfo & ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { // Initially insert a CouldNotCompute for this loop. If the insertion - // succeeds, procede to actually compute a backedge-taken count and + // succeeds, proceed to actually compute a backedge-taken count and // update the value. The temporary CouldNotCompute value tells SCEV // code elsewhere that it shouldn't attempt to request a new // backedge-taken count, which could result in infinite recursion. @@ -3510,6 +3675,26 @@ void ScalarEvolution::forgetValue(Value *V) { ConstantEvolutionLoopExitValue.erase(PN); } + // If there's a SCEVUnknown tying this value into the SCEV + // space, remove it from the folding set map. The SCEVUnknown + // object and any other SCEV objects which reference it + // (transitively) remain allocated, effectively leaked until + // the underlying BumpPtrAllocator is freed. + // + // This permits SCEV pointers to be used as keys in maps + // such as the ValuesAtScopes map. + FoldingSetNodeID ID; + ID.AddInteger(scUnknown); + ID.AddPointer(I); + void *IP; + if (SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) { + UniqueSCEVs.RemoveNode(S); + + // This isn't necessary, but we might as well remove the + // value from the ValuesAtScopes map too. + ValuesAtScopes.erase(S); + } + PushDefUseChildren(I, Worklist); } } @@ -3610,7 +3795,7 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExit(const Loop *L, return getCouldNotCompute(); } - // Procede to the next level to examine the exit condition expression. + // Proceed to the next level to examine the exit condition expression. return ComputeBackedgeTakenCountFromExitCond(L, ExitBr->getCondition(), ExitBr->getSuccessor(0), ExitBr->getSuccessor(1)); @@ -3699,10 +3884,23 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCond(const Loop *L, } // With an icmp, it may be feasible to compute an exact backedge-taken count. - // Procede to the next level to examine the icmp. + // Proceed to the next level to examine the icmp. if (ICmpInst *ExitCondICmp = dyn_cast(ExitCond)) return ComputeBackedgeTakenCountFromExitCondICmp(L, ExitCondICmp, TBB, FBB); + // Check for a constant condition. These are normally stripped out by + // SimplifyCFG, but ScalarEvolution may be used by a pass which wishes to + // preserve the CFG and is temporarily leaving constant conditions + // in place. + if (ConstantInt *CI = dyn_cast(ExitCond)) { + if (L->contains(FBB) == !CI->getZExtValue()) + // The backedge is always taken. + return getCouldNotCompute(); + else + // The backedge is never taken. + return getConstant(CI->getType(), 0); + } + // If it's not an integer or pointer comparison then compute it the hard way. return ComputeBackedgeTakenCountExhaustively(L, ExitCond, !L->contains(TBB)); } @@ -3726,14 +3924,10 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, // Handle common loops like: for (X = "string"; *X; ++X) if (LoadInst *LI = dyn_cast(ExitCond->getOperand(0))) if (Constant *RHS = dyn_cast(ExitCond->getOperand(1))) { - const SCEV *ItCnt = + BackedgeTakenInfo ItCnt = ComputeLoadConstantCompareBackedgeTakenCount(LI, RHS, L, Cond); - if (!isa(ItCnt)) { - unsigned BitWidth = getTypeSizeInBits(ItCnt->getType()); - return BackedgeTakenInfo(ItCnt, - isa(ItCnt) ? ItCnt : - getConstant(APInt::getMaxValue(BitWidth)-1)); - } + if (ItCnt.hasAnyInfo()) + return ItCnt; } const SCEV *LHS = getSCEV(ExitCond->getOperand(0)); @@ -3751,6 +3945,9 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, Cond = ICmpInst::getSwappedPredicate(Cond); } + // Simplify the operands before analyzing them. + (void)SimplifyICmpOperands(Cond, LHS, RHS); + // If we have a comparison of a chrec against a constant, try to use value // ranges to answer this query. if (const SCEVConstant *RHSC = dyn_cast(RHS)) @@ -3767,14 +3964,14 @@ ScalarEvolution::ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, switch (Cond) { case ICmpInst::ICMP_NE: { // while (X != Y) // Convert to: while (X-Y != 0) - const SCEV *TC = HowFarToZero(getMinusSCEV(LHS, RHS), L); - if (!isa(TC)) return TC; + BackedgeTakenInfo BTI = HowFarToZero(getMinusSCEV(LHS, RHS), L); + if (BTI.hasAnyInfo()) return BTI; break; } case ICmpInst::ICMP_EQ: { // while (X == Y) // Convert to: while (X-Y == 0) - const SCEV *TC = HowFarToNonZero(getMinusSCEV(LHS, RHS), L); - if (!isa(TC)) return TC; + BackedgeTakenInfo BTI = HowFarToNonZero(getMinusSCEV(LHS, RHS), L); + if (BTI.hasAnyInfo()) return BTI; break; } case ICmpInst::ICMP_SLT: { @@ -3861,7 +4058,7 @@ GetAddressedElementFromGlobal(GlobalVariable *GV, /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition of /// 'icmp op load X, cst', try to see if we can compute the backedge /// execution count. -const SCEV * +ScalarEvolution::BackedgeTakenInfo ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount( LoadInst *LI, Constant *RHS, @@ -3870,6 +4067,7 @@ ScalarEvolution::ComputeLoadConstantCompareBackedgeTakenCount( if (LI->isVolatile()) return getCouldNotCompute(); // Check to see if the loaded pointer is a getelementptr of a global. + // TODO: Use SCEV instead of manually grubbing with GEPs. GetElementPtrInst *GEP = dyn_cast(LI->getOperand(0)); if (!GEP) return getCouldNotCompute(); @@ -3978,8 +4176,7 @@ static PHINode *getConstantEvolvingPHI(Value *V, const Loop *L) { // constant or derived from a PHI node themselves. PHINode *PHI = 0; for (unsigned Op = 0, e = I->getNumOperands(); Op != e; ++Op) - if (!(isa(I->getOperand(Op)) || - isa(I->getOperand(Op)))) { + if (!isa(I->getOperand(Op))) { PHINode *P = getConstantEvolvingPHI(I->getOperand(Op), L); if (P == 0) return 0; // Not evolving from PHI if (PHI == 0) @@ -4000,11 +4197,9 @@ static Constant *EvaluateExpression(Value *V, Constant *PHIVal, const TargetData *TD) { if (isa(V)) return PHIVal; if (Constant *C = dyn_cast(V)) return C; - if (GlobalValue *GV = dyn_cast(V)) return GV; Instruction *I = cast(V); - std::vector Operands; - Operands.resize(I->getNumOperands()); + std::vector Operands(I->getNumOperands()); for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { Operands[i] = EvaluateExpression(I->getOperand(i), PHIVal, TD); @@ -4031,7 +4226,7 @@ ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, if (I != ConstantEvolutionLoopExitValue.end()) return I->second; - if (BEs.ugt(APInt(BEs.getBitWidth(),MaxBruteForceIterations))) + if (BEs.ugt(MaxBruteForceIterations)) return ConstantEvolutionLoopExitValue[PN] = 0; // Not going to evaluate it. Constant *&RetVal = ConstantEvolutionLoopExitValue[PN]; @@ -4046,8 +4241,8 @@ ScalarEvolution::getConstantEvolutionLoopExitValue(PHINode *PN, return RetVal = 0; // Must be a constant. Value *BEValue = PN->getIncomingValue(SecondIsBackedge); - PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); - if (PN2 != PN) + if (getConstantEvolvingPHI(BEValue, L) != PN && + !isa(BEValue)) return RetVal = 0; // Not derived from same PHI. // Execute the loop symbolically to determine the exit value. @@ -4082,8 +4277,11 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, PHINode *PN = getConstantEvolvingPHI(Cond, L); if (PN == 0) return getCouldNotCompute(); - // Since the loop is canonicalized, the PHI node must have two entries. One - // entry must be a constant (coming in from outside of the loop), and the + // If the loop is canonicalized, the PHI will have exactly two entries. + // That's the only form we support here. + if (PN->getNumIncomingValues() != 2) return getCouldNotCompute(); + + // One entry must be a constant (coming in from outside of the loop), and the // second must be derived from the same PHI. bool SecondIsBackedge = L->contains(PN->getIncomingBlock(1)); Constant *StartCST = @@ -4091,8 +4289,9 @@ ScalarEvolution::ComputeBackedgeTakenCountExhaustively(const Loop *L, if (StartCST == 0) return getCouldNotCompute(); // Must be a constant. Value *BEValue = PN->getIncomingValue(SecondIsBackedge); - PHINode *PN2 = getConstantEvolvingPHI(BEValue, L); - if (PN2 != PN) return getCouldNotCompute(); // Not derived from same PHI. + if (getConstantEvolvingPHI(BEValue, L) != PN && + !isa(BEValue)) + return getCouldNotCompute(); // Not derived from same PHI. // Okay, we find a PHI node that defines the trip count of this loop. Execute // the loop symbolically to determine when the condition gets a value of @@ -4180,53 +4379,51 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // the arguments into constants, and if so, try to constant propagate the // result. This is particularly useful for computing loop exit values. if (CanConstantFold(I)) { - std::vector Operands; - Operands.reserve(I->getNumOperands()); + SmallVector Operands; + bool MadeImprovement = false; for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { Value *Op = I->getOperand(i); if (Constant *C = dyn_cast(Op)) { Operands.push_back(C); - } else { - // If any of the operands is non-constant and if they are - // non-integer and non-pointer, don't even try to analyze them - // with scev techniques. - if (!isSCEVable(Op->getType())) - return V; - - const SCEV *OpV = getSCEVAtScope(Op, L); - if (const SCEVConstant *SC = dyn_cast(OpV)) { - Constant *C = SC->getValue(); - if (C->getType() != Op->getType()) - C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, - Op->getType(), - false), - C, Op->getType()); - Operands.push_back(C); - } else if (const SCEVUnknown *SU = dyn_cast(OpV)) { - if (Constant *C = dyn_cast(SU->getValue())) { - if (C->getType() != Op->getType()) - C = - ConstantExpr::getCast(CastInst::getCastOpcode(C, false, - Op->getType(), - false), - C, Op->getType()); - Operands.push_back(C); - } else - return V; - } else { - return V; - } + continue; } + + // If any of the operands is non-constant and if they are + // non-integer and non-pointer, don't even try to analyze them + // with scev techniques. + if (!isSCEVable(Op->getType())) + return V; + + const SCEV *OrigV = getSCEV(Op); + const SCEV *OpV = getSCEVAtScope(OrigV, L); + MadeImprovement |= OrigV != OpV; + + Constant *C = 0; + if (const SCEVConstant *SC = dyn_cast(OpV)) + C = SC->getValue(); + if (const SCEVUnknown *SU = dyn_cast(OpV)) + C = dyn_cast(SU->getValue()); + if (!C) return V; + if (C->getType() != Op->getType()) + C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false, + Op->getType(), + false), + C, Op->getType()); + Operands.push_back(C); } - Constant *C; - if (const CmpInst *CI = dyn_cast(I)) - C = ConstantFoldCompareInstOperands(CI->getPredicate(), - Operands[0], Operands[1], TD); - else - C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), - &Operands[0], Operands.size(), TD); - return getSCEV(C); + // Check to see if getSCEVAtScope actually made an improvement. + if (MadeImprovement) { + Constant *C = 0; + if (const CmpInst *CI = dyn_cast(I)) + C = ConstantFoldCompareInstOperands(CI->getPredicate(), + Operands[0], Operands[1], TD); + else + C = ConstantFoldInstOperands(I->getOpcode(), I->getType(), + &Operands[0], Operands.size(), TD); + if (!C) return V; + return getSCEV(C); + } } } @@ -4276,7 +4473,29 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // If this is a loop recurrence for a loop that does not contain L, then we // are dealing with the final value computed by the loop. if (const SCEVAddRecExpr *AddRec = dyn_cast(V)) { - if (!L || !AddRec->getLoop()->contains(L)) { + // First, attempt to evaluate each operand. + // Avoid performing the look-up in the common case where the specified + // expression has no loop-variant portions. + for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { + const SCEV *OpAtScope = getSCEVAtScope(AddRec->getOperand(i), L); + if (OpAtScope == AddRec->getOperand(i)) + continue; + + // Okay, at least one of these operands is loop variant but might be + // foldable. Build a new instance of the folded commutative expression. + SmallVector NewOps(AddRec->op_begin(), + AddRec->op_begin()+i); + NewOps.push_back(OpAtScope); + for (++i; i != e; ++i) + NewOps.push_back(getSCEVAtScope(AddRec->getOperand(i), L)); + + AddRec = cast(getAddRecExpr(NewOps, AddRec->getLoop())); + break; + } + + // If the scope is outside the addrec's loop, evaluate it by using the + // loop exit value of the addrec. + if (!AddRec->getLoop()->contains(L)) { // To evaluate this recurrence, we need to know how many times the AddRec // loop iterates. Compute this now. const SCEV *BackedgeTakenCount = getBackedgeTakenCount(AddRec->getLoop()); @@ -4285,6 +4504,7 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // Then, evaluate the AddRec. return AddRec->evaluateAtIteration(BackedgeTakenCount, *this); } + return AddRec; } @@ -4434,7 +4654,8 @@ SolveQuadraticEquation(const SCEVAddRecExpr *AddRec, ScalarEvolution &SE) { /// HowFarToZero - Return the number of times a backedge comparing the specified /// value to zero will execute. If not computable, return CouldNotCompute. -const SCEV *ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { +ScalarEvolution::BackedgeTakenInfo +ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { // If the value is a constant if (const SCEVConstant *C = dyn_cast(V)) { // If the value is already zero, the branch will execute zero times. @@ -4514,7 +4735,8 @@ const SCEV *ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L) { /// HowFarToNonZero - Return the number of times a backedge checking the /// specified value for nonzero will execute. If not computable, return /// CouldNotCompute -const SCEV *ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) { +ScalarEvolution::BackedgeTakenInfo +ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) { // Loops that look like: while (X == 0) are very strange indeed. We don't // handle them yet except for the trivial case. This could be expanded in the // future as needed. @@ -4523,7 +4745,7 @@ const SCEV *ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) { // already. If so, the backedge will execute zero times. if (const SCEVConstant *C = dyn_cast(V)) { if (!C->getValue()->isNullValue()) - return getIntegerSCEV(0, C->getType()); + return getConstant(C->getType(), 0); return getCouldNotCompute(); // Otherwise it will loop infinitely. } @@ -4532,41 +4754,26 @@ const SCEV *ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) { return getCouldNotCompute(); } -/// getLoopPredecessor - If the given loop's header has exactly one unique -/// predecessor outside the loop, return it. Otherwise return null. -/// -BasicBlock *ScalarEvolution::getLoopPredecessor(const Loop *L) { - BasicBlock *Header = L->getHeader(); - BasicBlock *Pred = 0; - for (pred_iterator PI = pred_begin(Header), E = pred_end(Header); - PI != E; ++PI) - if (!L->contains(*PI)) { - if (Pred && Pred != *PI) return 0; // Multiple predecessors. - Pred = *PI; - } - return Pred; -} - /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one /// successor from which BB is reachable, or null if no such block is /// found. /// -BasicBlock * +std::pair ScalarEvolution::getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB) { // If the block has a unique predecessor, then there is no path from the // predecessor to the block that does not go through the direct edge // from the predecessor to the block. if (BasicBlock *Pred = BB->getSinglePredecessor()) - return Pred; + return std::make_pair(Pred, BB); // A loop's header is defined to be a block that dominates the loop. // If the header has a unique predecessor outside the loop, it must be // a block that has exactly one successor that can reach the loop. if (Loop *L = LI->getLoopFor(BB)) - return getLoopPredecessor(L); + return std::make_pair(L->getLoopPredecessor(), L->getHeader()); - return 0; + return std::pair(); } /// HasSameValue - SCEV structural equivalence is usually sufficient for @@ -4592,6 +4799,266 @@ static bool HasSameValue(const SCEV *A, const SCEV *B) { return false; } +/// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with +/// predicate Pred. Return true iff any changes were made. +/// +bool ScalarEvolution::SimplifyICmpOperands(ICmpInst::Predicate &Pred, + const SCEV *&LHS, const SCEV *&RHS) { + bool Changed = false; + + // Canonicalize a constant to the right side. + if (const SCEVConstant *LHSC = dyn_cast(LHS)) { + // Check for both operands constant. + if (const SCEVConstant *RHSC = dyn_cast(RHS)) { + if (ConstantExpr::getICmp(Pred, + LHSC->getValue(), + RHSC->getValue())->isNullValue()) + goto trivially_false; + else + goto trivially_true; + } + // Otherwise swap the operands to put the constant on the right. + std::swap(LHS, RHS); + Pred = ICmpInst::getSwappedPredicate(Pred); + Changed = true; + } + + // If we're comparing an addrec with a value which is loop-invariant in the + // addrec's loop, put the addrec on the left. Also make a dominance check, + // 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)) { + std::swap(LHS, RHS); + Pred = ICmpInst::getSwappedPredicate(Pred); + Changed = true; + } + } + + // If there's a constant operand, canonicalize comparisons with boundary + // cases, and canonicalize *-or-equal comparisons to regular comparisons. + if (const SCEVConstant *RC = dyn_cast(RHS)) { + const APInt &RA = RC->getValue()->getValue(); + switch (Pred) { + default: llvm_unreachable("Unexpected ICmpInst::Predicate value!"); + case ICmpInst::ICMP_EQ: + case ICmpInst::ICMP_NE: + break; + case ICmpInst::ICMP_UGE: + if ((RA - 1).isMinValue()) { + Pred = ICmpInst::ICMP_NE; + RHS = getConstant(RA - 1); + Changed = true; + break; + } + if (RA.isMaxValue()) { + Pred = ICmpInst::ICMP_EQ; + Changed = true; + break; + } + if (RA.isMinValue()) goto trivially_true; + + Pred = ICmpInst::ICMP_UGT; + RHS = getConstant(RA - 1); + Changed = true; + break; + case ICmpInst::ICMP_ULE: + if ((RA + 1).isMaxValue()) { + Pred = ICmpInst::ICMP_NE; + RHS = getConstant(RA + 1); + Changed = true; + break; + } + if (RA.isMinValue()) { + Pred = ICmpInst::ICMP_EQ; + Changed = true; + break; + } + if (RA.isMaxValue()) goto trivially_true; + + Pred = ICmpInst::ICMP_ULT; + RHS = getConstant(RA + 1); + Changed = true; + break; + case ICmpInst::ICMP_SGE: + if ((RA - 1).isMinSignedValue()) { + Pred = ICmpInst::ICMP_NE; + RHS = getConstant(RA - 1); + Changed = true; + break; + } + if (RA.isMaxSignedValue()) { + Pred = ICmpInst::ICMP_EQ; + Changed = true; + break; + } + if (RA.isMinSignedValue()) goto trivially_true; + + Pred = ICmpInst::ICMP_SGT; + RHS = getConstant(RA - 1); + Changed = true; + break; + case ICmpInst::ICMP_SLE: + if ((RA + 1).isMaxSignedValue()) { + Pred = ICmpInst::ICMP_NE; + RHS = getConstant(RA + 1); + Changed = true; + break; + } + if (RA.isMinSignedValue()) { + Pred = ICmpInst::ICMP_EQ; + Changed = true; + break; + } + if (RA.isMaxSignedValue()) goto trivially_true; + + Pred = ICmpInst::ICMP_SLT; + RHS = getConstant(RA + 1); + Changed = true; + break; + case ICmpInst::ICMP_UGT: + if (RA.isMinValue()) { + Pred = ICmpInst::ICMP_NE; + Changed = true; + break; + } + if ((RA + 1).isMaxValue()) { + Pred = ICmpInst::ICMP_EQ; + RHS = getConstant(RA + 1); + Changed = true; + break; + } + if (RA.isMaxValue()) goto trivially_false; + break; + case ICmpInst::ICMP_ULT: + if (RA.isMaxValue()) { + Pred = ICmpInst::ICMP_NE; + Changed = true; + break; + } + if ((RA - 1).isMinValue()) { + Pred = ICmpInst::ICMP_EQ; + RHS = getConstant(RA - 1); + Changed = true; + break; + } + if (RA.isMinValue()) goto trivially_false; + break; + case ICmpInst::ICMP_SGT: + if (RA.isMinSignedValue()) { + Pred = ICmpInst::ICMP_NE; + Changed = true; + break; + } + if ((RA + 1).isMaxSignedValue()) { + Pred = ICmpInst::ICMP_EQ; + RHS = getConstant(RA + 1); + Changed = true; + break; + } + if (RA.isMaxSignedValue()) goto trivially_false; + break; + case ICmpInst::ICMP_SLT: + if (RA.isMaxSignedValue()) { + Pred = ICmpInst::ICMP_NE; + Changed = true; + break; + } + if ((RA - 1).isMinSignedValue()) { + Pred = ICmpInst::ICMP_EQ; + RHS = getConstant(RA - 1); + Changed = true; + break; + } + if (RA.isMinSignedValue()) goto trivially_false; + break; + } + } + + // Check for obvious equality. + if (HasSameValue(LHS, RHS)) { + if (ICmpInst::isTrueWhenEqual(Pred)) + goto trivially_true; + if (ICmpInst::isFalseWhenEqual(Pred)) + goto trivially_false; + } + + // If possible, canonicalize GE/LE comparisons to GT/LT comparisons, by + // adding or subtracting 1 from one of the operands. + switch (Pred) { + case ICmpInst::ICMP_SLE: + if (!getSignedRange(RHS).getSignedMax().isMaxSignedValue()) { + RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, + /*HasNUW=*/false, /*HasNSW=*/true); + Pred = ICmpInst::ICMP_SLT; + Changed = true; + } else if (!getSignedRange(LHS).getSignedMin().isMinSignedValue()) { + LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS, + /*HasNUW=*/false, /*HasNSW=*/true); + Pred = ICmpInst::ICMP_SLT; + Changed = true; + } + break; + case ICmpInst::ICMP_SGE: + if (!getSignedRange(RHS).getSignedMin().isMinSignedValue()) { + RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS, + /*HasNUW=*/false, /*HasNSW=*/true); + Pred = ICmpInst::ICMP_SGT; + Changed = true; + } else if (!getSignedRange(LHS).getSignedMax().isMaxSignedValue()) { + LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, + /*HasNUW=*/false, /*HasNSW=*/true); + Pred = ICmpInst::ICMP_SGT; + Changed = true; + } + break; + case ICmpInst::ICMP_ULE: + if (!getUnsignedRange(RHS).getUnsignedMax().isMaxValue()) { + RHS = getAddExpr(getConstant(RHS->getType(), 1, true), RHS, + /*HasNUW=*/true, /*HasNSW=*/false); + Pred = ICmpInst::ICMP_ULT; + Changed = true; + } else if (!getUnsignedRange(LHS).getUnsignedMin().isMinValue()) { + LHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), LHS, + /*HasNUW=*/true, /*HasNSW=*/false); + Pred = ICmpInst::ICMP_ULT; + Changed = true; + } + break; + case ICmpInst::ICMP_UGE: + if (!getUnsignedRange(RHS).getUnsignedMin().isMinValue()) { + RHS = getAddExpr(getConstant(RHS->getType(), (uint64_t)-1, true), RHS, + /*HasNUW=*/true, /*HasNSW=*/false); + Pred = ICmpInst::ICMP_UGT; + Changed = true; + } else if (!getUnsignedRange(LHS).getUnsignedMax().isMaxValue()) { + LHS = getAddExpr(getConstant(RHS->getType(), 1, true), LHS, + /*HasNUW=*/true, /*HasNSW=*/false); + Pred = ICmpInst::ICMP_UGT; + Changed = true; + } + break; + default: + break; + } + + // TODO: More simplifications are possible here. + + return Changed; + +trivially_true: + // Return 0 == 0. + LHS = RHS = getConstant(Type::getInt1Ty(getContext()), 0); + Pred = ICmpInst::ICMP_EQ; + return true; + +trivially_false: + // Return 0 != 0. + LHS = RHS = getConstant(Type::getInt1Ty(getContext()), 0); + Pred = ICmpInst::ICMP_NE; + return true; +} + bool ScalarEvolution::isKnownNegative(const SCEV *S) { return getSignedRange(S).getSignedMax().isNegative(); } @@ -4614,10 +5081,36 @@ bool ScalarEvolution::isKnownNonZero(const SCEV *S) { bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS) { + // Canonicalize the inputs first. + (void)SimplifyICmpOperands(Pred, LHS, RHS); + + // If LHS or RHS is an addrec, check to see if the condition is true in + // every iteration of the loop. + if (const SCEVAddRecExpr *AR = dyn_cast(LHS)) + if (isLoopEntryGuardedByCond( + AR->getLoop(), Pred, AR->getStart(), RHS) && + isLoopBackedgeGuardedByCond( + AR->getLoop(), Pred, AR->getPostIncExpr(*this), RHS)) + return true; + if (const SCEVAddRecExpr *AR = dyn_cast(RHS)) + if (isLoopEntryGuardedByCond( + AR->getLoop(), Pred, LHS, AR->getStart()) && + isLoopBackedgeGuardedByCond( + AR->getLoop(), Pred, LHS, AR->getPostIncExpr(*this))) + return true; + + // Otherwise see what can be done with known constant ranges. + return isKnownPredicateWithRanges(Pred, LHS, RHS); +} +bool +ScalarEvolution::isKnownPredicateWithRanges(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS) { if (HasSameValue(LHS, RHS)) return ICmpInst::isTrueWhenEqual(Pred); + // This code is split out from isKnownPredicate because it is called from + // within isLoopEntryGuardedByCond. switch (Pred) { default: llvm_unreachable("Unexpected ICmpInst::Predicate value!"); @@ -4714,35 +5207,33 @@ ScalarEvolution::isLoopBackedgeGuardedByCond(const Loop *L, LoopContinuePredicate->getSuccessor(0) != L->getHeader()); } -/// isLoopGuardedByCond - Test whether entry to the loop is protected +/// isLoopEntryGuardedByCond - Test whether entry to the loop is protected /// by a conditional between LHS and RHS. This is used to help avoid max /// expressions in loop trip counts, and to eliminate casts. bool -ScalarEvolution::isLoopGuardedByCond(const Loop *L, - ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS) { +ScalarEvolution::isLoopEntryGuardedByCond(const Loop *L, + ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS) { // Interpret a null as meaning no loop, where there is obviously no guard // (interprocedural conditions notwithstanding). if (!L) return false; - BasicBlock *Predecessor = getLoopPredecessor(L); - BasicBlock *PredecessorDest = L->getHeader(); - // Starting at the loop predecessor, climb up the predecessor chain, as long // as there are predecessors that can be found that have unique successors // leading to the original header. - for (; Predecessor; - PredecessorDest = Predecessor, - Predecessor = getPredecessorWithUniqueSuccessorForBB(Predecessor)) { + for (std::pair + Pair(L->getLoopPredecessor(), L->getHeader()); + Pair.first; + Pair = getPredecessorWithUniqueSuccessorForBB(Pair.first)) { BranchInst *LoopEntryPredicate = - dyn_cast(Predecessor->getTerminator()); + dyn_cast(Pair.first->getTerminator()); if (!LoopEntryPredicate || LoopEntryPredicate->isUnconditional()) continue; if (isImpliedCond(LoopEntryPredicate->getCondition(), Pred, LHS, RHS, - LoopEntryPredicate->getSuccessor(0) != PredecessorDest)) + LoopEntryPredicate->getSuccessor(0) != Pair.second)) return true; } @@ -4755,7 +5246,7 @@ bool ScalarEvolution::isImpliedCond(Value *CondValue, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, bool Inverse) { - // Recursivly handle And and Or conditions. + // Recursively handle And and Or conditions. if (BinaryOperator *BO = dyn_cast(CondValue)) { if (BO->getOpcode() == Instruction::And) { if (!Inverse) @@ -4806,117 +5297,12 @@ bool ScalarEvolution::isImpliedCond(Value *CondValue, // Canonicalize the query to match the way instcombine will have // canonicalized the comparison. - // First, put a constant operand on the right. - if (isa(LHS)) { - std::swap(LHS, RHS); - Pred = ICmpInst::getSwappedPredicate(Pred); - } - // Then, canonicalize comparisons with boundary cases. - if (const SCEVConstant *RC = dyn_cast(RHS)) { - const APInt &RA = RC->getValue()->getValue(); - switch (Pred) { - default: llvm_unreachable("Unexpected ICmpInst::Predicate value!"); - case ICmpInst::ICMP_EQ: - case ICmpInst::ICMP_NE: - break; - case ICmpInst::ICMP_UGE: - if ((RA - 1).isMinValue()) { - Pred = ICmpInst::ICMP_NE; - RHS = getConstant(RA - 1); - break; - } - if (RA.isMaxValue()) { - Pred = ICmpInst::ICMP_EQ; - break; - } - if (RA.isMinValue()) return true; - break; - case ICmpInst::ICMP_ULE: - if ((RA + 1).isMaxValue()) { - Pred = ICmpInst::ICMP_NE; - RHS = getConstant(RA + 1); - break; - } - if (RA.isMinValue()) { - Pred = ICmpInst::ICMP_EQ; - break; - } - if (RA.isMaxValue()) return true; - break; - case ICmpInst::ICMP_SGE: - if ((RA - 1).isMinSignedValue()) { - Pred = ICmpInst::ICMP_NE; - RHS = getConstant(RA - 1); - break; - } - if (RA.isMaxSignedValue()) { - Pred = ICmpInst::ICMP_EQ; - break; - } - if (RA.isMinSignedValue()) return true; - break; - case ICmpInst::ICMP_SLE: - if ((RA + 1).isMaxSignedValue()) { - Pred = ICmpInst::ICMP_NE; - RHS = getConstant(RA + 1); - break; - } - if (RA.isMinSignedValue()) { - Pred = ICmpInst::ICMP_EQ; - break; - } - if (RA.isMaxSignedValue()) return true; - break; - case ICmpInst::ICMP_UGT: - if (RA.isMinValue()) { - Pred = ICmpInst::ICMP_NE; - break; - } - if ((RA + 1).isMaxValue()) { - Pred = ICmpInst::ICMP_EQ; - RHS = getConstant(RA + 1); - break; - } - if (RA.isMaxValue()) return false; - break; - case ICmpInst::ICMP_ULT: - if (RA.isMaxValue()) { - Pred = ICmpInst::ICMP_NE; - break; - } - if ((RA - 1).isMinValue()) { - Pred = ICmpInst::ICMP_EQ; - RHS = getConstant(RA - 1); - break; - } - if (RA.isMinValue()) return false; - break; - case ICmpInst::ICMP_SGT: - if (RA.isMinSignedValue()) { - Pred = ICmpInst::ICMP_NE; - break; - } - if ((RA + 1).isMaxSignedValue()) { - Pred = ICmpInst::ICMP_EQ; - RHS = getConstant(RA + 1); - break; - } - if (RA.isMaxSignedValue()) return false; - break; - case ICmpInst::ICMP_SLT: - if (RA.isMaxSignedValue()) { - Pred = ICmpInst::ICMP_NE; - break; - } - if ((RA - 1).isMinSignedValue()) { - Pred = ICmpInst::ICMP_EQ; - RHS = getConstant(RA - 1); - break; - } - if (RA.isMinSignedValue()) return false; - break; - } - } + if (SimplifyICmpOperands(Pred, LHS, RHS)) + if (LHS == RHS) + return CmpInst::isTrueWhenEqual(Pred); + if (SimplifyICmpOperands(FoundPred, FoundLHS, FoundRHS)) + if (FoundLHS == FoundRHS) + return CmpInst::isFalseWhenEqual(Pred); // Check to see if we can make the LHS or RHS match. if (LHS == FoundRHS || RHS == FoundLHS) { @@ -4958,7 +5344,7 @@ bool ScalarEvolution::isImpliedCond(Value *CondValue, } /// isImpliedCondOperands - Test whether the condition described by Pred, -/// LHS, and RHS is true whenever the condition desribed by Pred, FoundLHS, +/// LHS, and RHS is true whenever the condition described by Pred, FoundLHS, /// and FoundRHS is true. bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, @@ -4973,7 +5359,7 @@ bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred, } /// isImpliedCondOperandsHelper - Test whether the condition described by -/// Pred, LHS, and RHS is true whenever the condition desribed by Pred, +/// Pred, LHS, and RHS is true whenever the condition described by Pred, /// FoundLHS, and FoundRHS is true. bool ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, @@ -4989,26 +5375,26 @@ ScalarEvolution::isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, break; case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLE: - if (isKnownPredicate(ICmpInst::ICMP_SLE, LHS, FoundLHS) && - isKnownPredicate(ICmpInst::ICMP_SGE, RHS, FoundRHS)) + if (isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, LHS, FoundLHS) && + isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, RHS, FoundRHS)) return true; break; case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGE: - if (isKnownPredicate(ICmpInst::ICMP_SGE, LHS, FoundLHS) && - isKnownPredicate(ICmpInst::ICMP_SLE, RHS, FoundRHS)) + if (isKnownPredicateWithRanges(ICmpInst::ICMP_SGE, LHS, FoundLHS) && + isKnownPredicateWithRanges(ICmpInst::ICMP_SLE, RHS, FoundRHS)) return true; break; case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: - if (isKnownPredicate(ICmpInst::ICMP_ULE, LHS, FoundLHS) && - isKnownPredicate(ICmpInst::ICMP_UGE, RHS, FoundRHS)) + if (isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, LHS, FoundLHS) && + isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, RHS, FoundRHS)) return true; break; case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGE: - if (isKnownPredicate(ICmpInst::ICMP_UGE, LHS, FoundLHS) && - isKnownPredicate(ICmpInst::ICMP_ULE, RHS, FoundRHS)) + if (isKnownPredicateWithRanges(ICmpInst::ICMP_UGE, LHS, FoundLHS) && + isKnownPredicateWithRanges(ICmpInst::ICMP_ULE, RHS, FoundRHS)) return true; break; } @@ -5027,7 +5413,7 @@ const SCEV *ScalarEvolution::getBECount(const SCEV *Start, "This code doesn't handle negative strides yet!"); const Type *Ty = Start->getType(); - const SCEV *NegOne = getIntegerSCEV(-1, Ty); + const SCEV *NegOne = getConstant(Ty, (uint64_t)-1); const SCEV *Diff = getMinusSCEV(End, Start); const SCEV *RoundUp = getAddExpr(Step, NegOne); @@ -5083,7 +5469,7 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, // behavior, so if wrap does occur, the loop could either terminate or // loop infinitely, but in either case, the loop is guaranteed to // iterate at least until the iteration where the wrapping occurs. - const SCEV *One = getIntegerSCEV(1, Step->getType()); + const SCEV *One = getConstant(Step->getType(), 1); if (isSigned) { APInt Max = APInt::getSignedMaxValue(BitWidth); if ((Max - getSignedRange(getMinusSCEV(Step, One)).getSignedMax()) @@ -5117,10 +5503,10 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, // only know that it will execute (max(m,n)-n)/s times. In both cases, // the division must round up. const SCEV *End = RHS; - if (!isLoopGuardedByCond(L, - isSigned ? ICmpInst::ICMP_SLT : - ICmpInst::ICMP_ULT, - getMinusSCEV(Start, Step), RHS)) + if (!isLoopEntryGuardedByCond(L, + isSigned ? ICmpInst::ICMP_SLT : + ICmpInst::ICMP_ULT, + getMinusSCEV(Start, Step), RHS)) End = isSigned ? getSMaxExpr(RHS, Start) : getUMaxExpr(RHS, Start); @@ -5131,10 +5517,10 @@ ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS, // If MaxEnd is within a step of the maximum integer value in its type, // adjust it down to the minimum value which would produce the same effect. - // This allows the subsequent ceiling divison of (N+(step-1))/step to + // This allows the subsequent ceiling division of (N+(step-1))/step to // compute the correct value. const SCEV *StepMinusOne = getMinusSCEV(Step, - getIntegerSCEV(1, Step->getType())); + getConstant(Step->getType(), 1)); MaxEnd = isSigned ? getSMinExpr(MaxEnd, getMinusSCEV(getConstant(APInt::getSignedMaxValue(BitWidth)), @@ -5171,7 +5557,7 @@ const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, if (const SCEVConstant *SC = dyn_cast(getStart())) if (!SC->getValue()->isZero()) { SmallVector Operands(op_begin(), op_end()); - Operands[0] = SE.getIntegerSCEV(0, SC->getType()); + Operands[0] = SE.getConstant(SC->getType(), 0); const SCEV *Shifted = SE.getAddRecExpr(Operands, getLoop()); if (const SCEVAddRecExpr *ShiftedAddRec = dyn_cast(Shifted)) @@ -5195,7 +5581,7 @@ const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range, // iteration exits. unsigned BitWidth = SE.getTypeSizeInBits(getType()); if (!Range.contains(APInt(BitWidth, 0))) - return SE.getIntegerSCEV(0, getType()); + return SE.getConstant(getType(), 0); if (isAffine()) { // If this is an affine expression then we have this situation: @@ -5348,8 +5734,8 @@ ScalarEvolution::ScalarEvolution() bool ScalarEvolution::runOnFunction(Function &F) { this->F = &F; LI = &getAnalysis(); - DT = &getAnalysis(); TD = getAnalysisIfAvailable(); + DT = &getAnalysis(); return false; } @@ -5408,7 +5794,7 @@ static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, } void ScalarEvolution::print(raw_ostream &OS, const Module *) const { - // ScalarEvolution's implementaiton of the print method is to print + // ScalarEvolution's implementation of the print method is to print // out SCEV values of all instructions that are interesting. Doing // this potentially causes it to create new SCEV objects though, // which technically conflicts with the const qualifier. This isn't @@ -5420,7 +5806,7 @@ void ScalarEvolution::print(raw_ostream &OS, const Module *) const { WriteAsOperand(OS, F, /*PrintType=*/false); OS << "\n"; for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) - if (isSCEVable(I->getType())) { + if (isSCEVable(I->getType()) && !isa(*I)) { OS << *I << '\n'; OS << " --> "; const SCEV *SV = SE.getSCEV(&*I);