diff options
Diffstat (limited to 'contrib/llvm/lib/Analysis/ScalarEvolution.cpp')
| -rw-r--r-- | contrib/llvm/lib/Analysis/ScalarEvolution.cpp | 794 |
1 files changed, 407 insertions, 387 deletions
diff --git a/contrib/llvm/lib/Analysis/ScalarEvolution.cpp b/contrib/llvm/lib/Analysis/ScalarEvolution.cpp index e5134f2eeda9..bc2cfd6fcc42 100644 --- a/contrib/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/contrib/llvm/lib/Analysis/ScalarEvolution.cpp @@ -1,9 +1,8 @@ //===- ScalarEvolution.cpp - Scalar Evolution Analysis --------------------===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // @@ -203,15 +202,20 @@ static cl::opt<unsigned> MaxConstantEvolvingDepth( cl::desc("Maximum depth of recursive constant evolving"), cl::init(32)); static cl::opt<unsigned> - MaxExtDepth("scalar-evolution-max-ext-depth", cl::Hidden, - cl::desc("Maximum depth of recursive SExt/ZExt"), - cl::init(8)); + MaxCastDepth("scalar-evolution-max-cast-depth", cl::Hidden, + cl::desc("Maximum depth of recursive SExt/ZExt/Trunc"), + cl::init(8)); static cl::opt<unsigned> MaxAddRecSize("scalar-evolution-max-add-rec-size", cl::Hidden, cl::desc("Max coefficients in AddRec during evolving"), cl::init(8)); +static cl::opt<unsigned> + HugeExprThreshold("scalar-evolution-huge-expr-threshold", cl::Hidden, + cl::desc("Size of the expression which is considered huge"), + cl::init(4096)); + //===----------------------------------------------------------------------===// // SCEV class definitions //===----------------------------------------------------------------------===// @@ -273,7 +277,9 @@ void SCEV::print(raw_ostream &OS) const { case scAddExpr: case scMulExpr: case scUMaxExpr: - case scSMaxExpr: { + case scSMaxExpr: + case scUMinExpr: + case scSMinExpr: { const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(this); const char *OpStr = nullptr; switch (NAry->getSCEVType()) { @@ -281,6 +287,12 @@ void SCEV::print(raw_ostream &OS) const { case scMulExpr: OpStr = " * "; break; case scUMaxExpr: OpStr = " umax "; break; case scSMaxExpr: OpStr = " smax "; break; + case scUMinExpr: + OpStr = " umin "; + break; + case scSMinExpr: + OpStr = " smin "; + break; } OS << "("; for (SCEVNAryExpr::op_iterator I = NAry->op_begin(), E = NAry->op_end(); @@ -349,6 +361,8 @@ Type *SCEV::getType() const { case scMulExpr: case scUMaxExpr: case scSMaxExpr: + case scUMinExpr: + case scSMinExpr: return cast<SCEVNAryExpr>(this)->getType(); case scAddExpr: return cast<SCEVAddExpr>(this)->getType(); @@ -393,7 +407,7 @@ bool SCEV::isNonConstantNegative() const { } SCEVCouldNotCompute::SCEVCouldNotCompute() : - SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {} + SCEV(FoldingSetNodeIDRef(), scCouldNotCompute, 0) {} bool SCEVCouldNotCompute::classof(const SCEV *S) { return S->getSCEVType() == scCouldNotCompute; @@ -422,7 +436,7 @@ ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) { SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID, unsigned SCEVTy, const SCEV *op, Type *ty) - : SCEV(ID, SCEVTy), Op(op), Ty(ty) {} + : SCEV(ID, SCEVTy, computeExpressionSize(op)), Op(op), Ty(ty) {} SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID, const SCEV *op, Type *ty) @@ -713,7 +727,9 @@ static int CompareSCEVComplexity( case scAddExpr: case scMulExpr: case scSMaxExpr: - case scUMaxExpr: { + case scUMaxExpr: + case scSMinExpr: + case scUMinExpr: { const SCEVNAryExpr *LC = cast<SCEVNAryExpr>(LHS); const SCEVNAryExpr *RC = cast<SCEVNAryExpr>(RHS); @@ -795,11 +811,10 @@ static void GroupByComplexity(SmallVectorImpl<const SCEV *> &Ops, } // Do the rough sort by complexity. - std::stable_sort(Ops.begin(), Ops.end(), - [&](const SCEV *LHS, const SCEV *RHS) { - return CompareSCEVComplexity(EqCacheSCEV, EqCacheValue, LI, - LHS, RHS, DT) < 0; - }); + llvm::stable_sort(Ops, [&](const SCEV *LHS, const SCEV *RHS) { + return CompareSCEVComplexity(EqCacheSCEV, EqCacheValue, LI, LHS, RHS, DT) < + 0; + }); // Now that we are sorted by complexity, group elements of the same // complexity. Note that this is, at worst, N^2, but the vector is likely to @@ -846,6 +861,17 @@ static inline int sizeOfSCEV(const SCEV *S) { return F.Size; } +/// Returns true if the subtree of \p S contains at least HugeExprThreshold +/// nodes. +static bool isHugeExpression(const SCEV *S) { + return S->getExpressionSize() >= HugeExprThreshold; +} + +/// Returns true of \p Ops contains a huge SCEV (see definition above). +static bool hasHugeExpression(ArrayRef<const SCEV *> Ops) { + return any_of(Ops, isHugeExpression); +} + namespace { struct SCEVDivision : public SCEVVisitor<SCEVDivision, void> { @@ -913,6 +939,8 @@ public: void visitUDivExpr(const SCEVUDivExpr *Numerator) {} void visitSMaxExpr(const SCEVSMaxExpr *Numerator) {} void visitUMaxExpr(const SCEVUMaxExpr *Numerator) {} + void visitSMinExpr(const SCEVSMinExpr *Numerator) {} + void visitUMinExpr(const SCEVUMinExpr *Numerator) {} void visitUnknown(const SCEVUnknown *Numerator) {} void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {} @@ -1219,8 +1247,8 @@ const SCEV *SCEVAddRecExpr::evaluateAtIteration(const SCEV *It, // SCEV Expression folder implementations //===----------------------------------------------------------------------===// -const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, - Type *Ty) { +const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty, + unsigned Depth) { assert(getTypeSizeInBits(Op->getType()) > getTypeSizeInBits(Ty) && "This is not a truncating conversion!"); assert(isSCEVable(Ty) && @@ -1241,15 +1269,23 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, // trunc(trunc(x)) --> trunc(x) if (const SCEVTruncateExpr *ST = dyn_cast<SCEVTruncateExpr>(Op)) - return getTruncateExpr(ST->getOperand(), Ty); + return getTruncateExpr(ST->getOperand(), Ty, Depth + 1); // trunc(sext(x)) --> sext(x) if widening or trunc(x) if narrowing if (const SCEVSignExtendExpr *SS = dyn_cast<SCEVSignExtendExpr>(Op)) - return getTruncateOrSignExtend(SS->getOperand(), Ty); + return getTruncateOrSignExtend(SS->getOperand(), Ty, Depth + 1); // trunc(zext(x)) --> zext(x) if widening or trunc(x) if narrowing if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op)) - return getTruncateOrZeroExtend(SZ->getOperand(), Ty); + return getTruncateOrZeroExtend(SZ->getOperand(), Ty, Depth + 1); + + if (Depth > MaxCastDepth) { + SCEV *S = + new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator), Op, Ty); + UniqueSCEVs.InsertNode(S, IP); + addToLoopUseLists(S); + return S; + } // trunc(x1 + ... + xN) --> trunc(x1) + ... + trunc(xN) and // trunc(x1 * ... * xN) --> trunc(x1) * ... * trunc(xN), @@ -1261,7 +1297,7 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, unsigned numTruncs = 0; for (unsigned i = 0, e = CommOp->getNumOperands(); i != e && numTruncs < 2; ++i) { - const SCEV *S = getTruncateExpr(CommOp->getOperand(i), Ty); + const SCEV *S = getTruncateExpr(CommOp->getOperand(i), Ty, Depth + 1); if (!isa<SCEVCastExpr>(CommOp->getOperand(i)) && isa<SCEVTruncateExpr>(S)) numTruncs++; Operands.push_back(S); @@ -1285,7 +1321,7 @@ const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) { SmallVector<const SCEV *, 4> Operands; for (const SCEV *Op : AddRec->operands()) - Operands.push_back(getTruncateExpr(Op, Ty)); + Operands.push_back(getTruncateExpr(Op, Ty, Depth + 1)); return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap); } @@ -1619,7 +1655,7 @@ ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { ID.AddPointer(Ty); void *IP = nullptr; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - if (Depth > MaxExtDepth) { + if (Depth > MaxCastDepth) { SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator), Op, Ty); UniqueSCEVs.InsertNode(S, IP); @@ -1637,7 +1673,7 @@ ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { unsigned NewBits = getTypeSizeInBits(Ty); if (CR.truncate(TruncBits).zeroExtend(NewBits).contains( CR.zextOrTrunc(NewBits))) - return getTruncateOrZeroExtend(X, Ty); + return getTruncateOrZeroExtend(X, Ty, Depth); } // If the input value is a chrec scev, and we can prove that the value @@ -1679,9 +1715,9 @@ ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { // Check whether the backedge-taken count can be losslessly casted to // the addrec's type. The count is always unsigned. const SCEV *CastedMaxBECount = - getTruncateOrZeroExtend(MaxBECount, Start->getType()); - const SCEV *RecastedMaxBECount = - getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType()); + getTruncateOrZeroExtend(MaxBECount, Start->getType(), Depth); + const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend( + CastedMaxBECount, MaxBECount->getType(), Depth); if (MaxBECount == RecastedMaxBECount) { Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); // Check whether Start+Step*MaxBECount has no unsigned overflow. @@ -1930,7 +1966,7 @@ ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { void *IP = nullptr; if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; // Limit recursion depth. - if (Depth > MaxExtDepth) { + if (Depth > MaxCastDepth) { SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator), Op, Ty); UniqueSCEVs.InsertNode(S, IP); @@ -1948,7 +1984,7 @@ ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { unsigned NewBits = getTypeSizeInBits(Ty); if (CR.truncate(TruncBits).signExtend(NewBits).contains( CR.sextOrTrunc(NewBits))) - return getTruncateOrSignExtend(X, Ty); + return getTruncateOrSignExtend(X, Ty, Depth); } if (auto *SA = dyn_cast<SCEVAddExpr>(Op)) { @@ -2023,9 +2059,9 @@ ScalarEvolution::getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) { // Check whether the backedge-taken count can be losslessly casted to // the addrec's type. The count is always unsigned. const SCEV *CastedMaxBECount = - getTruncateOrZeroExtend(MaxBECount, Start->getType()); - const SCEV *RecastedMaxBECount = - getTruncateOrZeroExtend(CastedMaxBECount, MaxBECount->getType()); + getTruncateOrZeroExtend(MaxBECount, Start->getType(), Depth); + const SCEV *RecastedMaxBECount = getTruncateOrZeroExtend( + CastedMaxBECount, MaxBECount->getType(), Depth); if (MaxBECount == RecastedMaxBECount) { Type *WideTy = IntegerType::get(getContext(), BitWidth * 2); // Check whether Start+Step*MaxBECount has no signed overflow. @@ -2295,7 +2331,7 @@ CollectAddOperandsWithScales(DenseMap<const SCEV *, APInt> &M, // can't-overflow flags for the operation if possible. static SCEV::NoWrapFlags StrengthenNoWrapFlags(ScalarEvolution *SE, SCEVTypes Type, - const SmallVectorImpl<const SCEV *> &Ops, + const ArrayRef<const SCEV *> Ops, SCEV::NoWrapFlags Flags) { using namespace std::placeholders; @@ -2405,7 +2441,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, } // Limit recursion calls depth. - if (Depth > MaxArithDepth) + if (Depth > MaxArithDepth || hasHugeExpression(Ops)) return getOrCreateAddExpr(Ops, Flags); // Okay, check to see if the same value occurs in the operand list more than @@ -2743,7 +2779,7 @@ const SCEV *ScalarEvolution::getAddExpr(SmallVectorImpl<const SCEV *> &Ops, } const SCEV * -ScalarEvolution::getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops, +ScalarEvolution::getOrCreateAddExpr(ArrayRef<const SCEV *> Ops, SCEV::NoWrapFlags Flags) { FoldingSetNodeID ID; ID.AddInteger(scAddExpr); @@ -2765,7 +2801,7 @@ ScalarEvolution::getOrCreateAddExpr(SmallVectorImpl<const SCEV *> &Ops, } const SCEV * -ScalarEvolution::getOrCreateAddRecExpr(SmallVectorImpl<const SCEV *> &Ops, +ScalarEvolution::getOrCreateAddRecExpr(ArrayRef<const SCEV *> Ops, const Loop *L, SCEV::NoWrapFlags Flags) { FoldingSetNodeID ID; ID.AddInteger(scAddRecExpr); @@ -2788,7 +2824,7 @@ ScalarEvolution::getOrCreateAddRecExpr(SmallVectorImpl<const SCEV *> &Ops, } const SCEV * -ScalarEvolution::getOrCreateMulExpr(SmallVectorImpl<const SCEV *> &Ops, +ScalarEvolution::getOrCreateMulExpr(ArrayRef<const SCEV *> Ops, SCEV::NoWrapFlags Flags) { FoldingSetNodeID ID; ID.AddInteger(scMulExpr); @@ -2884,7 +2920,7 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, Flags = StrengthenNoWrapFlags(this, scMulExpr, Ops, Flags); // Limit recursion calls depth. - if (Depth > MaxArithDepth) + if (Depth > MaxArithDepth || hasHugeExpression(Ops)) return getOrCreateMulExpr(Ops, Flags); // If there are any constants, fold them together. @@ -3057,7 +3093,8 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, // Limit max number of arguments to avoid creation of unreasonably big // SCEVAddRecs with very complex operands. if (AddRec->getNumOperands() + OtherAddRec->getNumOperands() - 1 > - MaxAddRecSize) + MaxAddRecSize || isHugeExpression(AddRec) || + isHugeExpression(OtherAddRec)) continue; bool Overflow = false; @@ -3090,7 +3127,7 @@ const SCEV *ScalarEvolution::getMulExpr(SmallVectorImpl<const SCEV *> &Ops, AddRecOps.push_back(getAddExpr(SumOps, SCEV::FlagAnyWrap, Depth + 1)); } if (!Overflow) { - const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRec->getLoop(), + const SCEV *NewAddRec = getAddRecExpr(AddRecOps, AddRecLoop, SCEV::FlagAnyWrap); if (Ops.size() == 2) return NewAddRec; Ops[Idx] = NewAddRec; @@ -3493,209 +3530,166 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, return getAddExpr(BaseExpr, TotalOffset, Wrap); } -const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, - const SCEV *RHS) { - SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; - return getSMaxExpr(Ops); +std::tuple<const SCEV *, FoldingSetNodeID, void *> +ScalarEvolution::findExistingSCEVInCache(int SCEVType, + ArrayRef<const SCEV *> Ops) { + FoldingSetNodeID ID; + void *IP = nullptr; + ID.AddInteger(SCEVType); + for (unsigned i = 0, e = Ops.size(); i != e; ++i) + ID.AddPointer(Ops[i]); + return std::tuple<const SCEV *, FoldingSetNodeID, void *>( + UniqueSCEVs.FindNodeOrInsertPos(ID, IP), std::move(ID), IP); } -const SCEV * -ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { - assert(!Ops.empty() && "Cannot get empty smax!"); +const SCEV *ScalarEvolution::getMinMaxExpr(unsigned Kind, + SmallVectorImpl<const SCEV *> &Ops) { + assert(!Ops.empty() && "Cannot get empty (u|s)(min|max)!"); if (Ops.size() == 1) return Ops[0]; #ifndef NDEBUG Type *ETy = getEffectiveSCEVType(Ops[0]->getType()); for (unsigned i = 1, e = Ops.size(); i != e; ++i) assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy && - "SCEVSMaxExpr operand types don't match!"); + "Operand types don't match!"); #endif + bool IsSigned = Kind == scSMaxExpr || Kind == scSMinExpr; + bool IsMax = Kind == scSMaxExpr || Kind == scUMaxExpr; + // Sort by complexity, this groups all similar expression types together. GroupByComplexity(Ops, &LI, DT); + // Check if we have created the same expression before. + if (const SCEV *S = std::get<0>(findExistingSCEVInCache(Kind, Ops))) { + return S; + } + // If there are any constants, fold them together. unsigned Idx = 0; if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { ++Idx; assert(Idx < Ops.size()); + auto FoldOp = [&](const APInt &LHS, const APInt &RHS) { + if (Kind == scSMaxExpr) + return APIntOps::smax(LHS, RHS); + else if (Kind == scSMinExpr) + return APIntOps::smin(LHS, RHS); + else if (Kind == scUMaxExpr) + return APIntOps::umax(LHS, RHS); + else if (Kind == scUMinExpr) + return APIntOps::umin(LHS, RHS); + llvm_unreachable("Unknown SCEV min/max opcode"); + }; + while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { // We found two constants, fold them together! ConstantInt *Fold = ConstantInt::get( - getContext(), APIntOps::smax(LHSC->getAPInt(), RHSC->getAPInt())); + getContext(), FoldOp(LHSC->getAPInt(), RHSC->getAPInt())); Ops[0] = getConstant(Fold); Ops.erase(Ops.begin()+1); // Erase the folded element if (Ops.size() == 1) return Ops[0]; LHSC = cast<SCEVConstant>(Ops[0]); } - // If we are left with a constant minimum-int, strip it off. - if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(true)) { + bool IsMinV = LHSC->getValue()->isMinValue(IsSigned); + bool IsMaxV = LHSC->getValue()->isMaxValue(IsSigned); + + if (IsMax ? IsMinV : IsMaxV) { + // If we are left with a constant minimum(/maximum)-int, strip it off. Ops.erase(Ops.begin()); --Idx; - } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(true)) { - // If we have an smax with a constant maximum-int, it will always be - // maximum-int. - return Ops[0]; + } else if (IsMax ? IsMaxV : IsMinV) { + // If we have a max(/min) with a constant maximum(/minimum)-int, + // it will always be the extremum. + return LHSC; } if (Ops.size() == 1) return Ops[0]; } - // Find the first SMax - while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scSMaxExpr) + // Find the first operation of the same kind + while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < Kind) ++Idx; - // Check to see if one of the operands is an SMax. If so, expand its operands - // onto our operand list, and recurse to simplify. + // Check to see if one of the operands is of the same kind. If so, expand its + // operands onto our operand list, and recurse to simplify. if (Idx < Ops.size()) { - bool DeletedSMax = false; - while (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(Ops[Idx])) { + bool DeletedAny = false; + while (Ops[Idx]->getSCEVType() == Kind) { + const SCEVMinMaxExpr *SMME = cast<SCEVMinMaxExpr>(Ops[Idx]); Ops.erase(Ops.begin()+Idx); - Ops.append(SMax->op_begin(), SMax->op_end()); - DeletedSMax = true; + Ops.append(SMME->op_begin(), SMME->op_end()); + DeletedAny = true; } - if (DeletedSMax) - return getSMaxExpr(Ops); + if (DeletedAny) + return getMinMaxExpr(Kind, Ops); } // Okay, check to see if the same value occurs in the operand list twice. If // so, delete one. Since we sorted the list, these values are required to // be adjacent. - for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) - // 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; + llvm::CmpInst::Predicate GEPred = + IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; + llvm::CmpInst::Predicate LEPred = + IsSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; + llvm::CmpInst::Predicate FirstPred = IsMax ? GEPred : LEPred; + llvm::CmpInst::Predicate SecondPred = IsMax ? LEPred : GEPred; + for (unsigned i = 0, e = Ops.size() - 1; i != e; ++i) { + if (Ops[i] == Ops[i + 1] || + isKnownViaNonRecursiveReasoning(FirstPred, Ops[i], Ops[i + 1])) { + // X op Y op Y --> X op Y + // X op Y --> X, if we know X, Y are ordered appropriately + Ops.erase(Ops.begin() + i + 1, Ops.begin() + i + 2); + --i; + --e; + } else if (isKnownViaNonRecursiveReasoning(SecondPred, Ops[i], + Ops[i + 1])) { + // X op Y --> Y, if we know X, Y are ordered appropriately + Ops.erase(Ops.begin() + i, Ops.begin() + i + 1); + --i; + --e; } + } if (Ops.size() == 1) return Ops[0]; assert(!Ops.empty() && "Reduced smax down to nothing!"); - // Okay, it looks like we really DO need an smax expr. Check to see if we + // Okay, it looks like we really DO need an expr. Check to see if we // already have one, otherwise create a new one. + const SCEV *ExistingSCEV; FoldingSetNodeID ID; - ID.AddInteger(scSMaxExpr); - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - ID.AddPointer(Ops[i]); - void *IP = nullptr; - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; + void *IP; + std::tie(ExistingSCEV, ID, IP) = findExistingSCEVInCache(Kind, Ops); + if (ExistingSCEV) + return ExistingSCEV; const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(Ops.size()); std::uninitialized_copy(Ops.begin(), Ops.end(), O); - SCEV *S = new (SCEVAllocator) SCEVSMaxExpr(ID.Intern(SCEVAllocator), - O, Ops.size()); + SCEV *S = new (SCEVAllocator) SCEVMinMaxExpr( + ID.Intern(SCEVAllocator), static_cast<SCEVTypes>(Kind), O, Ops.size()); + UniqueSCEVs.InsertNode(S, IP); addToLoopUseLists(S); return S; } -const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, - const SCEV *RHS) { +const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) { SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; - return getUMaxExpr(Ops); + return getSMaxExpr(Ops); } -const SCEV * -ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { - assert(!Ops.empty() && "Cannot get empty umax!"); - if (Ops.size() == 1) return Ops[0]; -#ifndef NDEBUG - Type *ETy = getEffectiveSCEVType(Ops[0]->getType()); - for (unsigned i = 1, e = Ops.size(); i != e; ++i) - assert(getEffectiveSCEVType(Ops[i]->getType()) == ETy && - "SCEVUMaxExpr operand types don't match!"); -#endif - - // Sort by complexity, this groups all similar expression types together. - GroupByComplexity(Ops, &LI, DT); - - // If there are any constants, fold them together. - unsigned Idx = 0; - if (const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(Ops[0])) { - ++Idx; - assert(Idx < Ops.size()); - while (const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(Ops[Idx])) { - // We found two constants, fold them together! - ConstantInt *Fold = ConstantInt::get( - getContext(), APIntOps::umax(LHSC->getAPInt(), RHSC->getAPInt())); - Ops[0] = getConstant(Fold); - Ops.erase(Ops.begin()+1); // Erase the folded element - if (Ops.size() == 1) return Ops[0]; - LHSC = cast<SCEVConstant>(Ops[0]); - } - - // If we are left with a constant minimum-int, strip it off. - if (cast<SCEVConstant>(Ops[0])->getValue()->isMinValue(false)) { - Ops.erase(Ops.begin()); - --Idx; - } else if (cast<SCEVConstant>(Ops[0])->getValue()->isMaxValue(false)) { - // If we have an umax with a constant maximum-int, it will always be - // maximum-int. - return Ops[0]; - } - - if (Ops.size() == 1) return Ops[0]; - } - - // Find the first UMax - while (Idx < Ops.size() && Ops[Idx]->getSCEVType() < scUMaxExpr) - ++Idx; - - // Check to see if one of the operands is a UMax. If so, expand its operands - // onto our operand list, and recurse to simplify. - if (Idx < Ops.size()) { - bool DeletedUMax = false; - while (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(Ops[Idx])) { - Ops.erase(Ops.begin()+Idx); - Ops.append(UMax->op_begin(), UMax->op_end()); - DeletedUMax = true; - } - - if (DeletedUMax) - return getUMaxExpr(Ops); - } - - // Okay, check to see if the same value occurs in the operand list twice. If - // so, delete one. Since we sorted the list, these values are required to - // be adjacent. - for (unsigned i = 0, e = Ops.size()-1; i != e; ++i) - // 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] || isKnownViaNonRecursiveReasoning( - ICmpInst::ICMP_UGE, Ops[i], Ops[i + 1])) { - Ops.erase(Ops.begin() + i + 1, Ops.begin() + i + 2); - --i; --e; - } else if (isKnownViaNonRecursiveReasoning(ICmpInst::ICMP_ULE, Ops[i], - Ops[i + 1])) { - Ops.erase(Ops.begin() + i, Ops.begin() + i + 1); - --i; --e; - } - - if (Ops.size() == 1) return Ops[0]; +const SCEV *ScalarEvolution::getSMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { + return getMinMaxExpr(scSMaxExpr, Ops); +} - assert(!Ops.empty() && "Reduced umax down to nothing!"); +const SCEV *ScalarEvolution::getUMaxExpr(const SCEV *LHS, const SCEV *RHS) { + SmallVector<const SCEV *, 2> Ops = {LHS, RHS}; + return getUMaxExpr(Ops); +} - // Okay, it looks like we really DO need a umax expr. Check to see if we - // already have one, otherwise create a new one. - FoldingSetNodeID ID; - ID.AddInteger(scUMaxExpr); - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - ID.AddPointer(Ops[i]); - void *IP = nullptr; - if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S; - const SCEV **O = SCEVAllocator.Allocate<const SCEV *>(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); - addToLoopUseLists(S); - return S; +const SCEV *ScalarEvolution::getUMaxExpr(SmallVectorImpl<const SCEV *> &Ops) { + return getMinMaxExpr(scUMaxExpr, Ops); } const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS, @@ -3705,11 +3699,7 @@ const SCEV *ScalarEvolution::getSMinExpr(const SCEV *LHS, } const SCEV *ScalarEvolution::getSMinExpr(SmallVectorImpl<const SCEV *> &Ops) { - // ~smax(~x, ~y, ~z) == smin(x, y, z). - SmallVector<const SCEV *, 2> NotOps; - for (auto *S : Ops) - NotOps.push_back(getNotSCEV(S)); - return getNotSCEV(getSMaxExpr(NotOps)); + return getMinMaxExpr(scSMinExpr, Ops); } const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, @@ -3719,16 +3709,7 @@ const SCEV *ScalarEvolution::getUMinExpr(const SCEV *LHS, } const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops) { - assert(!Ops.empty() && "At least one operand must be!"); - // Trivial case. - if (Ops.size() == 1) - return Ops[0]; - - // ~umax(~x, ~y, ~z) == umin(x, y, z). - SmallVector<const SCEV *, 2> NotOps; - for (auto *S : Ops) - NotOps.push_back(getNotSCEV(S)); - return getNotSCEV(getUMaxExpr(NotOps)); + return getMinMaxExpr(scUMinExpr, Ops); } const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) { @@ -3892,7 +3873,7 @@ void ScalarEvolution::eraseValueFromMap(Value *V) { } /// Check whether value has nuw/nsw/exact set but SCEV does not. -/// TODO: In reality it is better to check the poison recursevely +/// TODO: In reality it is better to check the poison recursively /// but this is better than nothing. static bool SCEVLostPoisonFlags(const SCEV *S, const Value *V) { if (auto *I = dyn_cast<Instruction>(V)) { @@ -3970,12 +3951,45 @@ const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V, V, getConstant(cast<ConstantInt>(Constant::getAllOnesValue(Ty))), Flags); } +/// If Expr computes ~A, return A else return nullptr +static const SCEV *MatchNotExpr(const SCEV *Expr) { + const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr); + if (!Add || Add->getNumOperands() != 2 || + !Add->getOperand(0)->isAllOnesValue()) + return nullptr; + + const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1)); + if (!AddRHS || AddRHS->getNumOperands() != 2 || + !AddRHS->getOperand(0)->isAllOnesValue()) + return nullptr; + + return AddRHS->getOperand(1); +} + /// Return a SCEV corresponding to ~V = -1-V const SCEV *ScalarEvolution::getNotSCEV(const SCEV *V) { if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V)) return getConstant( cast<ConstantInt>(ConstantExpr::getNot(VC->getValue()))); + // Fold ~(u|s)(min|max)(~x, ~y) to (u|s)(max|min)(x, y) + if (const SCEVMinMaxExpr *MME = dyn_cast<SCEVMinMaxExpr>(V)) { + auto MatchMinMaxNegation = [&](const SCEVMinMaxExpr *MME) { + SmallVector<const SCEV *, 2> MatchedOperands; + for (const SCEV *Operand : MME->operands()) { + const SCEV *Matched = MatchNotExpr(Operand); + if (!Matched) + return (const SCEV *)nullptr; + MatchedOperands.push_back(Matched); + } + return getMinMaxExpr( + SCEVMinMaxExpr::negate(static_cast<SCEVTypes>(MME->getSCEVType())), + MatchedOperands); + }; + if (const SCEV *Replaced = MatchMinMaxNegation(MME)) + return Replaced; + } + Type *Ty = V->getType(); Ty = getEffectiveSCEVType(Ty); const SCEV *AllOnes = @@ -4022,29 +4036,28 @@ const SCEV *ScalarEvolution::getMinusSCEV(const SCEV *LHS, const SCEV *RHS, return getAddExpr(LHS, getNegativeSCEV(RHS, NegFlags), AddFlags, Depth); } -const SCEV * -ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty) { +const SCEV *ScalarEvolution::getTruncateOrZeroExtend(const SCEV *V, Type *Ty, + unsigned Depth) { Type *SrcTy = V->getType(); assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() && "Cannot truncate or zero extend with non-integer arguments!"); if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) return V; // No conversion if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) - return getTruncateExpr(V, Ty); - return getZeroExtendExpr(V, Ty); + return getTruncateExpr(V, Ty, Depth); + return getZeroExtendExpr(V, Ty, Depth); } -const SCEV * -ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, - Type *Ty) { +const SCEV *ScalarEvolution::getTruncateOrSignExtend(const SCEV *V, Type *Ty, + unsigned Depth) { Type *SrcTy = V->getType(); assert(SrcTy->isIntOrPtrTy() && Ty->isIntOrPtrTy() && "Cannot truncate or zero extend with non-integer arguments!"); if (getTypeSizeInBits(SrcTy) == getTypeSizeInBits(Ty)) return V; // No conversion if (getTypeSizeInBits(SrcTy) > getTypeSizeInBits(Ty)) - return getTruncateExpr(V, Ty); - return getSignExtendExpr(V, Ty); + return getTruncateExpr(V, Ty, Depth); + return getSignExtendExpr(V, Ty, Depth); } const SCEV * @@ -4530,52 +4543,21 @@ static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) { if (EVI->getNumIndices() != 1 || EVI->getIndices()[0] != 0) break; - auto *CI = dyn_cast<CallInst>(EVI->getAggregateOperand()); - if (!CI) + auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()); + if (!WO) break; - if (auto *F = CI->getCalledFunction()) - switch (F->getIntrinsicID()) { - case Intrinsic::sadd_with_overflow: - case Intrinsic::uadd_with_overflow: - if (!isOverflowIntrinsicNoWrap(cast<IntrinsicInst>(CI), DT)) - return BinaryOp(Instruction::Add, CI->getArgOperand(0), - CI->getArgOperand(1)); - - // Now that we know that all uses of the arithmetic-result component of - // CI are guarded by the overflow check, we can go ahead and pretend - // that the arithmetic is non-overflowing. - if (F->getIntrinsicID() == Intrinsic::sadd_with_overflow) - return BinaryOp(Instruction::Add, CI->getArgOperand(0), - CI->getArgOperand(1), /* IsNSW = */ true, - /* IsNUW = */ false); - else - return BinaryOp(Instruction::Add, CI->getArgOperand(0), - CI->getArgOperand(1), /* IsNSW = */ false, - /* IsNUW*/ true); - case Intrinsic::ssub_with_overflow: - case Intrinsic::usub_with_overflow: - if (!isOverflowIntrinsicNoWrap(cast<IntrinsicInst>(CI), DT)) - return BinaryOp(Instruction::Sub, CI->getArgOperand(0), - CI->getArgOperand(1)); - - // The same reasoning as sadd/uadd above. - if (F->getIntrinsicID() == Intrinsic::ssub_with_overflow) - return BinaryOp(Instruction::Sub, CI->getArgOperand(0), - CI->getArgOperand(1), /* IsNSW = */ true, - /* IsNUW = */ false); - else - return BinaryOp(Instruction::Sub, CI->getArgOperand(0), - CI->getArgOperand(1), /* IsNSW = */ false, - /* IsNUW = */ true); - case Intrinsic::smul_with_overflow: - case Intrinsic::umul_with_overflow: - return BinaryOp(Instruction::Mul, CI->getArgOperand(0), - CI->getArgOperand(1)); - default: - break; - } - break; + Instruction::BinaryOps BinOp = WO->getBinaryOp(); + bool Signed = WO->isSigned(); + // TODO: Should add nuw/nsw flags for mul as well. + if (BinOp == Instruction::Mul || !isOverflowIntrinsicNoWrap(WO, DT)) + return BinaryOp(BinOp, WO->getLHS(), WO->getRHS()); + + // Now that we know that all uses of the arithmetic-result component of + // CI are guarded by the overflow check, we can go ahead and pretend + // that the arithmetic is non-overflowing. + return BinaryOp(BinOp, WO->getLHS(), WO->getRHS(), + /* IsNSW = */ Signed, /* IsNUW = */ !Signed); } default: @@ -5009,7 +4991,7 @@ const SCEV *ScalarEvolution::createSimpleAffineAddRec(PHINode *PN, // overflow. if (auto *BEInst = dyn_cast<Instruction>(BEValueV)) if (isLoopInvariant(Accum, L) && isAddRecNeverPoison(BEInst, L)) - (void)getAddRecExpr(getAddExpr(StartVal, Accum), Accum, L, Flags); + (void)getAddRecExpr(getAddExpr(StartVal, Accum, Flags), Accum, L, Flags); return PHISCEV; } @@ -5196,6 +5178,8 @@ static bool IsAvailableOnEntry(const Loop *L, DominatorTree &DT, const SCEV *S, switch (S->getSCEVType()) { case scConstant: case scTruncate: case scZeroExtend: case scSignExtend: case scAddExpr: case scMulExpr: case scUMaxExpr: case scSMaxExpr: + case scUMinExpr: + case scSMinExpr: // These expressions are available if their operand(s) is/are. return true; @@ -5551,6 +5535,9 @@ ScalarEvolution::getRangeRef(const SCEV *S, DenseMap<const SCEV *, ConstantRange> &Cache = SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges; + ConstantRange::PreferredRangeType RangeType = + SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED + ? ConstantRange::Unsigned : ConstantRange::Signed; // See if we've computed this range already. DenseMap<const SCEV *, ConstantRange>::iterator I = Cache.find(S); @@ -5581,53 +5568,60 @@ ScalarEvolution::getRangeRef(const SCEV *S, ConstantRange X = getRangeRef(Add->getOperand(0), SignHint); for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) X = X.add(getRangeRef(Add->getOperand(i), SignHint)); - return setRange(Add, SignHint, ConservativeResult.intersectWith(X)); + return setRange(Add, SignHint, + ConservativeResult.intersectWith(X, RangeType)); } if (const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(S)) { ConstantRange X = getRangeRef(Mul->getOperand(0), SignHint); for (unsigned i = 1, e = Mul->getNumOperands(); i != e; ++i) X = X.multiply(getRangeRef(Mul->getOperand(i), SignHint)); - return setRange(Mul, SignHint, ConservativeResult.intersectWith(X)); + return setRange(Mul, SignHint, + ConservativeResult.intersectWith(X, RangeType)); } if (const SCEVSMaxExpr *SMax = dyn_cast<SCEVSMaxExpr>(S)) { ConstantRange X = getRangeRef(SMax->getOperand(0), SignHint); for (unsigned i = 1, e = SMax->getNumOperands(); i != e; ++i) X = X.smax(getRangeRef(SMax->getOperand(i), SignHint)); - return setRange(SMax, SignHint, ConservativeResult.intersectWith(X)); + return setRange(SMax, SignHint, + ConservativeResult.intersectWith(X, RangeType)); } if (const SCEVUMaxExpr *UMax = dyn_cast<SCEVUMaxExpr>(S)) { ConstantRange X = getRangeRef(UMax->getOperand(0), SignHint); for (unsigned i = 1, e = UMax->getNumOperands(); i != e; ++i) X = X.umax(getRangeRef(UMax->getOperand(i), SignHint)); - return setRange(UMax, SignHint, ConservativeResult.intersectWith(X)); + return setRange(UMax, SignHint, + ConservativeResult.intersectWith(X, RangeType)); } if (const SCEVUDivExpr *UDiv = dyn_cast<SCEVUDivExpr>(S)) { ConstantRange X = getRangeRef(UDiv->getLHS(), SignHint); ConstantRange Y = getRangeRef(UDiv->getRHS(), SignHint); return setRange(UDiv, SignHint, - ConservativeResult.intersectWith(X.udiv(Y))); + ConservativeResult.intersectWith(X.udiv(Y), RangeType)); } if (const SCEVZeroExtendExpr *ZExt = dyn_cast<SCEVZeroExtendExpr>(S)) { ConstantRange X = getRangeRef(ZExt->getOperand(), SignHint); return setRange(ZExt, SignHint, - ConservativeResult.intersectWith(X.zeroExtend(BitWidth))); + ConservativeResult.intersectWith(X.zeroExtend(BitWidth), + RangeType)); } if (const SCEVSignExtendExpr *SExt = dyn_cast<SCEVSignExtendExpr>(S)) { ConstantRange X = getRangeRef(SExt->getOperand(), SignHint); return setRange(SExt, SignHint, - ConservativeResult.intersectWith(X.signExtend(BitWidth))); + ConservativeResult.intersectWith(X.signExtend(BitWidth), + RangeType)); } if (const SCEVTruncateExpr *Trunc = dyn_cast<SCEVTruncateExpr>(S)) { ConstantRange X = getRangeRef(Trunc->getOperand(), SignHint); return setRange(Trunc, SignHint, - ConservativeResult.intersectWith(X.truncate(BitWidth))); + ConservativeResult.intersectWith(X.truncate(BitWidth), + RangeType)); } if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { @@ -5637,7 +5631,7 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart())) if (!C->getValue()->isZero()) ConservativeResult = ConservativeResult.intersectWith( - ConstantRange(C->getAPInt(), APInt(BitWidth, 0))); + ConstantRange(C->getAPInt(), APInt(BitWidth, 0)), RangeType); // If there's no signed wrap, and all the operands have the same sign or // zero, the value won't ever change sign. @@ -5651,11 +5645,11 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (AllNonNeg) ConservativeResult = ConservativeResult.intersectWith( ConstantRange(APInt(BitWidth, 0), - APInt::getSignedMinValue(BitWidth))); + APInt::getSignedMinValue(BitWidth)), RangeType); else if (AllNonPos) ConservativeResult = ConservativeResult.intersectWith( ConstantRange(APInt::getSignedMinValue(BitWidth), - APInt(BitWidth, 1))); + APInt(BitWidth, 1)), RangeType); } // TODO: non-affine addrec @@ -5668,14 +5662,14 @@ ScalarEvolution::getRangeRef(const SCEV *S, BitWidth); if (!RangeFromAffine.isFullSet()) ConservativeResult = - ConservativeResult.intersectWith(RangeFromAffine); + ConservativeResult.intersectWith(RangeFromAffine, RangeType); auto RangeFromFactoring = getRangeViaFactoring( AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount, BitWidth); if (!RangeFromFactoring.isFullSet()) ConservativeResult = - ConservativeResult.intersectWith(RangeFromFactoring); + ConservativeResult.intersectWith(RangeFromFactoring, RangeType); } } @@ -5686,7 +5680,8 @@ ScalarEvolution::getRangeRef(const SCEV *S, // Check if the IR explicitly contains !range metadata. Optional<ConstantRange> MDRange = GetRangeFromMetadata(U->getValue()); if (MDRange.hasValue()) - ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue()); + ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue(), + RangeType); // Split here to avoid paying the compile-time cost of calling both // computeKnownBits and ComputeNumSignBits. This restriction can be lifted @@ -5697,8 +5692,8 @@ ScalarEvolution::getRangeRef(const SCEV *S, KnownBits Known = computeKnownBits(U->getValue(), DL, 0, &AC, nullptr, &DT); if (Known.One != ~Known.Zero + 1) ConservativeResult = - ConservativeResult.intersectWith(ConstantRange(Known.One, - ~Known.Zero + 1)); + ConservativeResult.intersectWith( + ConstantRange(Known.One, ~Known.Zero + 1), RangeType); } else { assert(SignHint == ScalarEvolution::HINT_RANGE_SIGNED && "generalize as needed!"); @@ -5706,7 +5701,8 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (NS > 1) ConservativeResult = ConservativeResult.intersectWith( ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1), - APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1)); + APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1), + RangeType); } // A range of Phi is a subset of union of all ranges of its input. @@ -5721,7 +5717,8 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (RangeFromOps.isFullSet()) break; } - ConservativeResult = ConservativeResult.intersectWith(RangeFromOps); + ConservativeResult = + ConservativeResult.intersectWith(RangeFromOps, RangeType); bool Erased = PendingPhiRanges.erase(Phi); assert(Erased && "Failed to erase Phi properly?"); (void) Erased; @@ -5751,7 +5748,7 @@ static ConstantRange getRangeForAffineARHelper(APInt Step, // FullRange), then we don't know anything about the final range either. // Return FullRange. if (StartRange.isFullSet()) - return ConstantRange(BitWidth, /* isFullSet = */ true); + return ConstantRange::getFull(BitWidth); // If Step is signed and negative, then we use its absolute value, but we also // note that we're moving in the opposite direction. @@ -5767,7 +5764,7 @@ static ConstantRange getRangeForAffineARHelper(APInt Step, // Check if Offset is more than full span of BitWidth. If it is, the // expression is guaranteed to overflow. if (APInt::getMaxValue(StartRange.getBitWidth()).udiv(Step).ult(MaxBECount)) - return ConstantRange(BitWidth, /* isFullSet = */ true); + return ConstantRange::getFull(BitWidth); // Offset is by how much the expression can change. Checks above guarantee no // overflow here. @@ -5786,7 +5783,7 @@ static ConstantRange getRangeForAffineARHelper(APInt Step, // range (due to wrap around). This means that the expression can take any // value in this bitwidth, and we have to return full range. if (StartRange.contains(MovedBoundary)) - return ConstantRange(BitWidth, /* isFullSet = */ true); + return ConstantRange::getFull(BitWidth); APInt NewLower = Descending ? std::move(MovedBoundary) : std::move(StartLower); @@ -5794,12 +5791,8 @@ static ConstantRange getRangeForAffineARHelper(APInt Step, Descending ? std::move(StartUpper) : std::move(MovedBoundary); NewUpper += 1; - // If we end up with full range, return a proper full range. - if (NewLower == NewUpper) - return ConstantRange(BitWidth, /* isFullSet = */ true); - // No overflow detected, return [StartLower, StartUpper + Offset + 1) range. - return ConstantRange(std::move(NewLower), std::move(NewUpper)); + return ConstantRange::getNonEmpty(std::move(NewLower), std::move(NewUpper)); } ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start, @@ -5832,7 +5825,7 @@ ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start, MaxBECountValue, BitWidth, /* Signed = */ false); // Finally, intersect signed and unsigned ranges. - return SR.intersectWith(UR); + return SR.intersectWith(UR, ConstantRange::Smallest); } ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, @@ -5916,17 +5909,17 @@ ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start, SelectPattern StartPattern(*this, BitWidth, Start); if (!StartPattern.isRecognized()) - return ConstantRange(BitWidth, /* isFullSet = */ true); + return ConstantRange::getFull(BitWidth); SelectPattern StepPattern(*this, BitWidth, Step); if (!StepPattern.isRecognized()) - return ConstantRange(BitWidth, /* isFullSet = */ true); + return ConstantRange::getFull(BitWidth); if (StartPattern.Condition != StepPattern.Condition) { // We don't handle this case today; but we could, by considering four // possibilities below instead of two. I'm not sure if there are cases where // that will help over what getRange already does, though. - return ConstantRange(BitWidth, /* isFullSet = */ true); + return ConstantRange::getFull(BitWidth); } // NB! Calling ScalarEvolution::getConstant is fine, but we should not try to @@ -6128,7 +6121,7 @@ const SCEV *ScalarEvolution::createSCEV(Value *V) { // to obey basic rules for definitions dominating uses which this // analysis depends on. if (!DT.isReachableFromEntry(I->getParent())) - return getUnknown(V); + return getUnknown(UndefValue::get(V->getType())); } else if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) return getConstant(CI); else if (isa<ConstantPointerNull>(V)) @@ -6744,6 +6737,28 @@ ScalarEvolution::getBackedgeTakenInfo(const Loop *L) { return BackedgeTakenCounts.find(L)->second = std::move(Result); } +void ScalarEvolution::forgetAllLoops() { + // This method is intended to forget all info about loops. It should + // invalidate caches as if the following happened: + // - The trip counts of all loops have changed arbitrarily + // - Every llvm::Value has been updated in place to produce a different + // result. + BackedgeTakenCounts.clear(); + PredicatedBackedgeTakenCounts.clear(); + LoopPropertiesCache.clear(); + ConstantEvolutionLoopExitValue.clear(); + ValueExprMap.clear(); + ValuesAtScopes.clear(); + LoopDispositions.clear(); + BlockDispositions.clear(); + UnsignedRanges.clear(); + SignedRanges.clear(); + ExprValueMap.clear(); + HasRecMap.clear(); + MinTrailingZerosCache.clear(); + PredicatedSCEVRewrites.clear(); +} + void ScalarEvolution::forgetLoop(const Loop *L) { // Drop any stored trip count value. auto RemoveLoopFromBackedgeMap = @@ -6972,8 +6987,8 @@ ScalarEvolution::ExitLimit::ExitLimit(const SCEV *E, const SCEV *M, /// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each /// computable exit into a persistent ExitNotTakenInfo array. ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo( - SmallVectorImpl<ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo> - &&ExitCounts, + ArrayRef<ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo> + ExitCounts, bool Complete, const SCEV *MaxCount, bool MaxOrZero) : MaxAndComplete(MaxCount, Complete), MaxOrZero(MaxOrZero) { using EdgeExitInfo = ScalarEvolution::BackedgeTakenInfo::EdgeExitInfo; @@ -7256,6 +7271,14 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( if (EL0.ExactNotTaken == EL1.ExactNotTaken) BECount = EL0.ExactNotTaken; } + // There are cases (e.g. PR26207) where computeExitLimitFromCond is able + // to be more aggressive when computing BECount than when computing + // MaxBECount. In these cases it is possible for EL0.ExactNotTaken and + // EL1.ExactNotTaken to match, but for EL0.MaxNotTaken and EL1.MaxNotTaken + // to not. + if (isa<SCEVCouldNotCompute>(MaxBECount) && + !isa<SCEVCouldNotCompute>(BECount)) + MaxBECount = getConstant(getUnsignedRangeMax(BECount)); return ExitLimit(BECount, MaxBECount, false, {&EL0.Predicates, &EL1.Predicates}); @@ -7651,7 +7674,7 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeShiftCompareExitLimit( static bool CanConstantFold(const Instruction *I) { if (isa<BinaryOperator>(I) || isa<CmpInst>(I) || isa<SelectInst>(I) || isa<CastInst>(I) || isa<GetElementPtrInst>(I) || - isa<LoadInst>(I)) + isa<LoadInst>(I) || isa<ExtractValueInst>(I)) return true; if (const CallInst *CI = dyn_cast<CallInst>(I)) @@ -8075,7 +8098,9 @@ static Constant *BuildConstantFromSCEV(const SCEV *V) { } case scSMaxExpr: case scUMaxExpr: - break; // TODO: smax, umax. + case scSMinExpr: + case scUMinExpr: + break; // TODO: smax, umax, smin, umax. } return nullptr; } @@ -8087,44 +8112,64 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { // exit value from the loop without using SCEVs. if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V)) { if (Instruction *I = dyn_cast<Instruction>(SU->getValue())) { - const Loop *LI = this->LI[I->getParent()]; - if (LI && LI->getParentLoop() == L) // Looking for loop exit value. - if (PHINode *PN = dyn_cast<PHINode>(I)) - if (PN->getParent() == LI->getHeader()) { - // Okay, there is no closed form solution for the PHI node. Check - // to see if the loop that contains it has a known backedge-taken - // count. If so, we may be able to force computation of the exit - // value. - const SCEV *BackedgeTakenCount = getBackedgeTakenCount(LI); - if (const SCEVConstant *BTCC = - dyn_cast<SCEVConstant>(BackedgeTakenCount)) { - - // This trivial case can show up in some degenerate cases where - // the incoming IR has not yet been fully simplified. - if (BTCC->getValue()->isZero()) { - Value *InitValue = nullptr; - bool MultipleInitValues = false; - for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) { - if (!LI->contains(PN->getIncomingBlock(i))) { - if (!InitValue) - InitValue = PN->getIncomingValue(i); - else if (InitValue != PN->getIncomingValue(i)) { - MultipleInitValues = true; - break; - } - } - if (!MultipleInitValues && InitValue) - return getSCEV(InitValue); + if (PHINode *PN = dyn_cast<PHINode>(I)) { + const Loop *LI = this->LI[I->getParent()]; + // Looking for loop exit value. + if (LI && LI->getParentLoop() == L && + PN->getParent() == LI->getHeader()) { + // Okay, there is no closed form solution for the PHI node. Check + // to see if the loop that contains it has a known backedge-taken + // count. If so, we may be able to force computation of the exit + // value. + const SCEV *BackedgeTakenCount = getBackedgeTakenCount(LI); + // This trivial case can show up in some degenerate cases where + // the incoming IR has not yet been fully simplified. + if (BackedgeTakenCount->isZero()) { + Value *InitValue = nullptr; + bool MultipleInitValues = false; + for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) { + if (!LI->contains(PN->getIncomingBlock(i))) { + if (!InitValue) + InitValue = PN->getIncomingValue(i); + else if (InitValue != PN->getIncomingValue(i)) { + MultipleInitValues = true; + break; } } - // Okay, we know how many times the containing loop executes. If - // this is a constant evolving PHI node, get the final value at - // the specified iteration number. - Constant *RV = - getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), LI); - if (RV) return getSCEV(RV); } + if (!MultipleInitValues && InitValue) + return getSCEV(InitValue); } + // Do we have a loop invariant value flowing around the backedge + // for a loop which must execute the backedge? + if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && + isKnownPositive(BackedgeTakenCount) && + PN->getNumIncomingValues() == 2) { + unsigned InLoopPred = LI->contains(PN->getIncomingBlock(0)) ? 0 : 1; + const SCEV *OnBackedge = getSCEV(PN->getIncomingValue(InLoopPred)); + if (IsAvailableOnEntry(LI, DT, OnBackedge, PN->getParent())) + return OnBackedge; + } + if (auto *BTCC = dyn_cast<SCEVConstant>(BackedgeTakenCount)) { + // Okay, we know how many times the containing loop executes. If + // this is a constant evolving PHI node, get the final value at + // the specified iteration number. + Constant *RV = + getConstantEvolutionLoopExitValue(PN, BTCC->getAPInt(), LI); + if (RV) return getSCEV(RV); + } + } + + // If there is a single-input Phi, evaluate it at our scope. If we can + // prove that this replacement does not break LCSSA form, use new value. + if (PN->getNumOperands() == 1) { + const SCEV *Input = getSCEV(PN->getOperand(0)); + const SCEV *InputAtScope = getSCEVAtScope(Input, L); + // TODO: We can generalize it using LI.replacementPreservesLCSSAForm, + // for the simplest case just support constants. + if (isa<SCEVConstant>(InputAtScope)) return InputAtScope; + } + } // Okay, this is an expression that we cannot symbolically evaluate // into a SCEV. Check to see if it's possible to symbolically evaluate @@ -8198,13 +8243,11 @@ const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) { NewOps.push_back(OpAtScope); } if (isa<SCEVAddExpr>(Comm)) - return getAddExpr(NewOps); + return getAddExpr(NewOps, Comm->getNoWrapFlags()); if (isa<SCEVMulExpr>(Comm)) - return getMulExpr(NewOps); - if (isa<SCEVSMaxExpr>(Comm)) - return getSMaxExpr(NewOps); - if (isa<SCEVUMaxExpr>(Comm)) - return getUMaxExpr(NewOps); + return getMulExpr(NewOps, Comm->getNoWrapFlags()); + if (isa<SCEVMinMaxExpr>(Comm)) + return getMinMaxExpr(Comm->getSCEVType(), NewOps); llvm_unreachable("Unknown commutative SCEV type!"); } } @@ -10045,41 +10088,15 @@ bool ScalarEvolution::isImpliedCondOperands(ICmpInst::Predicate Pred, getNotSCEV(FoundLHS)); } -/// If Expr computes ~A, return A else return nullptr -static const SCEV *MatchNotExpr(const SCEV *Expr) { - const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(Expr); - if (!Add || Add->getNumOperands() != 2 || - !Add->getOperand(0)->isAllOnesValue()) - return nullptr; - - const SCEVMulExpr *AddRHS = dyn_cast<SCEVMulExpr>(Add->getOperand(1)); - if (!AddRHS || AddRHS->getNumOperands() != 2 || - !AddRHS->getOperand(0)->isAllOnesValue()) - return nullptr; - - return AddRHS->getOperand(1); -} - -/// Is MaybeMaxExpr an SMax or UMax of Candidate and some other values? -template<typename MaxExprType> -static bool IsMaxConsistingOf(const SCEV *MaybeMaxExpr, - const SCEV *Candidate) { - const MaxExprType *MaxExpr = dyn_cast<MaxExprType>(MaybeMaxExpr); - if (!MaxExpr) return false; - - return find(MaxExpr->operands(), Candidate) != MaxExpr->op_end(); -} - -/// Is MaybeMinExpr an SMin or UMin of Candidate and some other values? -template<typename MaxExprType> -static bool IsMinConsistingOf(ScalarEvolution &SE, - const SCEV *MaybeMinExpr, - const SCEV *Candidate) { - const SCEV *MaybeMaxExpr = MatchNotExpr(MaybeMinExpr); - if (!MaybeMaxExpr) +/// Is MaybeMinMaxExpr an (U|S)(Min|Max) of Candidate and some other values? +template <typename MinMaxExprType> +static bool IsMinMaxConsistingOf(const SCEV *MaybeMinMaxExpr, + const SCEV *Candidate) { + const MinMaxExprType *MinMaxExpr = dyn_cast<MinMaxExprType>(MaybeMinMaxExpr); + if (!MinMaxExpr) return false; - return IsMaxConsistingOf<MaxExprType>(MaybeMaxExpr, SE.getNotSCEV(Candidate)); + return find(MinMaxExpr->operands(), Candidate) != MinMaxExpr->op_end(); } static bool IsKnownPredicateViaAddRecStart(ScalarEvolution &SE, @@ -10128,20 +10145,20 @@ static bool IsKnownPredicateViaMinOrMax(ScalarEvolution &SE, LLVM_FALLTHROUGH; case ICmpInst::ICMP_SLE: return - // min(A, ...) <= A - IsMinConsistingOf<SCEVSMaxExpr>(SE, LHS, RHS) || - // A <= max(A, ...) - IsMaxConsistingOf<SCEVSMaxExpr>(RHS, LHS); + // min(A, ...) <= A + IsMinMaxConsistingOf<SCEVSMinExpr>(LHS, RHS) || + // A <= max(A, ...) + IsMinMaxConsistingOf<SCEVSMaxExpr>(RHS, LHS); case ICmpInst::ICMP_UGE: std::swap(LHS, RHS); LLVM_FALLTHROUGH; case ICmpInst::ICMP_ULE: return - // min(A, ...) <= A - IsMinConsistingOf<SCEVUMaxExpr>(SE, LHS, RHS) || - // A <= max(A, ...) - IsMaxConsistingOf<SCEVUMaxExpr>(RHS, LHS); + // min(A, ...) <= A + IsMinMaxConsistingOf<SCEVUMinExpr>(LHS, RHS) || + // A <= max(A, ...) + IsMinMaxConsistingOf<SCEVUMaxExpr>(RHS, LHS); } llvm_unreachable("covered switch fell through?!"); @@ -10691,13 +10708,10 @@ ScalarEvolution::howManyGreaterThans(const SCEV *LHS, const SCEV *RHS, IsSigned ? APIntOps::smax(getSignedRangeMin(RHS), Limit) : APIntOps::umax(getUnsignedRangeMin(RHS), Limit); - - const SCEV *MaxBECount = getCouldNotCompute(); - if (isa<SCEVConstant>(BECount)) - MaxBECount = BECount; - else - MaxBECount = computeBECount(getConstant(MaxStart - MinEnd), - getConstant(MinStride), false); + const SCEV *MaxBECount = isa<SCEVConstant>(BECount) + ? BECount + : computeBECount(getConstant(MaxStart - MinEnd), + getConstant(MinStride), false); if (isa<SCEVCouldNotCompute>(MaxBECount)) MaxBECount = BECount; @@ -10806,8 +10820,6 @@ static inline bool containsUndefs(const SCEV *S) { return SCEVExprContains(S, [](const SCEV *S) { if (const auto *SU = dyn_cast<SCEVUnknown>(S)) return isa<UndefValue>(SU->getValue()); - else if (const auto *SC = dyn_cast<SCEVConstant>(S)) - return isa<UndefValue>(SC->getValue()); return false; }); } @@ -11402,19 +11414,23 @@ static void PrintLoopInfo(raw_ostream &OS, ScalarEvolution *SE, L->getHeader()->printAsOperand(OS, /*PrintType=*/false); OS << ": "; - SmallVector<BasicBlock *, 8> ExitBlocks; - L->getExitBlocks(ExitBlocks); - if (ExitBlocks.size() != 1) + SmallVector<BasicBlock *, 8> ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + if (ExitingBlocks.size() != 1) OS << "<multiple exits> "; - if (SE->hasLoopInvariantBackedgeTakenCount(L)) { - OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L); - } else { - OS << "Unpredictable backedge-taken count. "; - } + if (SE->hasLoopInvariantBackedgeTakenCount(L)) + OS << "backedge-taken count is " << *SE->getBackedgeTakenCount(L) << "\n"; + else + OS << "Unpredictable backedge-taken count.\n"; - OS << "\n" - "Loop "; + if (ExitingBlocks.size() > 1) + for (BasicBlock *ExitingBlock : ExitingBlocks) { + OS << " exit count for " << ExitingBlock->getName() << ": " + << *SE->getExitCount(L, ExitingBlock) << "\n"; + } + + OS << "Loop "; L->getHeader()->printAsOperand(OS, /*PrintType=*/false); OS << ": "; @@ -11611,7 +11627,9 @@ ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) { case scAddExpr: case scMulExpr: case scUMaxExpr: - case scSMaxExpr: { + case scSMaxExpr: + case scUMinExpr: + case scSMinExpr: { bool HasVarying = false; for (auto *Op : cast<SCEVNAryExpr>(S)->operands()) { LoopDisposition D = getLoopDisposition(Op, L); @@ -11698,7 +11716,9 @@ ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) { case scAddExpr: case scMulExpr: case scUMaxExpr: - case scSMaxExpr: { + case scSMaxExpr: + case scUMinExpr: + case scSMinExpr: { const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S); bool Proper = true; for (const SCEV *NAryOp : NAry->operands()) { |