diff options
Diffstat (limited to 'llvm/lib/Analysis/ScalarEvolution.cpp')
| -rw-r--r-- | llvm/lib/Analysis/ScalarEvolution.cpp | 285 |
1 files changed, 186 insertions, 99 deletions
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 5ce0a1adeaa0c..26a9a5ddf1ea7 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -112,6 +112,7 @@ #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/IR/Verifier.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" @@ -220,6 +221,12 @@ static cl::opt<unsigned> cl::desc("Size of the expression which is considered huge"), cl::init(4096)); +static cl::opt<bool> +ClassifyExpressions("scalar-evolution-classify-expressions", + cl::Hidden, cl::init(true), + cl::desc("When printing analysis, include information on every instruction")); + + //===----------------------------------------------------------------------===// // SCEV class definitions //===----------------------------------------------------------------------===// @@ -3488,7 +3495,7 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, const SCEV *BaseExpr = getSCEV(GEP->getPointerOperand()); // getSCEV(Base)->getType() has the same address space as Base->getType() // because SCEV::getType() preserves the address space. - Type *IntPtrTy = getEffectiveSCEVType(BaseExpr->getType()); + Type *IntIdxTy = getEffectiveSCEVType(BaseExpr->getType()); // FIXME(PR23527): Don't blindly transfer the inbounds flag from the GEP // instruction to its SCEV, because the Instruction may be guarded by control // flow and the no-overflow bits may not be valid for the expression in any @@ -3497,7 +3504,7 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, SCEV::NoWrapFlags Wrap = GEP->isInBounds() ? SCEV::FlagNSW : SCEV::FlagAnyWrap; - const SCEV *TotalOffset = getZero(IntPtrTy); + const SCEV *TotalOffset = getZero(IntIdxTy); // The array size is unimportant. The first thing we do on CurTy is getting // its element type. Type *CurTy = ArrayType::get(GEP->getSourceElementType(), 0); @@ -3507,7 +3514,7 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, // For a struct, add the member offset. ConstantInt *Index = cast<SCEVConstant>(IndexExpr)->getValue(); unsigned FieldNo = Index->getZExtValue(); - const SCEV *FieldOffset = getOffsetOfExpr(IntPtrTy, STy, FieldNo); + const SCEV *FieldOffset = getOffsetOfExpr(IntIdxTy, STy, FieldNo); // Add the field offset to the running total offset. TotalOffset = getAddExpr(TotalOffset, FieldOffset); @@ -3518,9 +3525,9 @@ ScalarEvolution::getGEPExpr(GEPOperator *GEP, // Update CurTy to its element type. CurTy = cast<SequentialType>(CurTy)->getElementType(); // For an array, add the element offset, explicitly scaled. - const SCEV *ElementSize = getSizeOfExpr(IntPtrTy, CurTy); + const SCEV *ElementSize = getSizeOfExpr(IntIdxTy, CurTy); // Getelementptr indices are signed. - IndexExpr = getTruncateOrSignExtend(IndexExpr, IntPtrTy); + IndexExpr = getTruncateOrSignExtend(IndexExpr, IntIdxTy); // Multiply the index by the element size to compute the element offset. const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, Wrap); @@ -3779,7 +3786,7 @@ uint64_t ScalarEvolution::getTypeSizeInBits(Type *Ty) const { /// Return a type with the same bitwidth as the given type and which represents /// how SCEV will treat the given type, for which isSCEVable must return -/// true. For pointer types, this is the pointer-sized integer type. +/// true. For pointer types, this is the pointer index sized integer type. Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const { assert(isSCEVable(Ty) && "Type is not SCEVable!"); @@ -3788,7 +3795,7 @@ Type *ScalarEvolution::getEffectiveSCEVType(Type *Ty) const { // The only other support type is pointer. assert(Ty->isPointerTy() && "Unexpected non-pointer non-integer type!"); - return getDataLayout().getIntPtrType(Ty); + return getDataLayout().getIndexType(Ty); } Type *ScalarEvolution::getWiderType(Type *T1, Type *T2) const { @@ -4568,6 +4575,12 @@ static Optional<BinaryOp> MatchBinaryOp(Value *V, DominatorTree &DT) { break; } + // Recognise intrinsic loop.decrement.reg, and as this has exactly the same + // semantics as a Sub, return a binary sub expression. + if (auto *II = dyn_cast<IntrinsicInst>(V)) + if (II->getIntrinsicID() == Intrinsic::loop_decrement_reg) + return BinaryOp(Instruction::Sub, II->getOperand(0), II->getOperand(1)); + return None; } @@ -5553,6 +5566,7 @@ ScalarEvolution::getRangeRef(const SCEV *S, unsigned BitWidth = getTypeSizeInBits(S->getType()); ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true); + using OBO = OverflowingBinaryOperator; // If the value has known zeros, the maximum value will have those known zeros // as well. @@ -5570,8 +5584,14 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { ConstantRange X = getRangeRef(Add->getOperand(0), SignHint); + unsigned WrapType = OBO::AnyWrap; + if (Add->hasNoSignedWrap()) + WrapType |= OBO::NoSignedWrap; + if (Add->hasNoUnsignedWrap()) + WrapType |= OBO::NoUnsignedWrap; for (unsigned i = 1, e = Add->getNumOperands(); i != e; ++i) - X = X.add(getRangeRef(Add->getOperand(i), SignHint)); + X = X.addWithNoWrap(getRangeRef(Add->getOperand(i), SignHint), + WrapType, RangeType); return setRange(Add, SignHint, ConservativeResult.intersectWith(X, RangeType)); } @@ -5647,29 +5667,38 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) { // If there's no unsigned wrap, the value will never be less than its // initial value. - if (AddRec->hasNoUnsignedWrap()) - if (const SCEVConstant *C = dyn_cast<SCEVConstant>(AddRec->getStart())) - if (!C->getValue()->isZero()) - ConservativeResult = ConservativeResult.intersectWith( - 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. + if (AddRec->hasNoUnsignedWrap()) { + APInt UnsignedMinValue = getUnsignedRangeMin(AddRec->getStart()); + if (!UnsignedMinValue.isNullValue()) + ConservativeResult = ConservativeResult.intersectWith( + ConstantRange(UnsignedMinValue, APInt(BitWidth, 0)), RangeType); + } + + // If there's no signed wrap, and all the operands except initial value have + // the same sign or zero, the value won't ever be: + // 1: smaller than initial value if operands are non negative, + // 2: bigger than initial value if operands are non positive. + // For both cases, value can not cross signed min/max boundary. if (AddRec->hasNoSignedWrap()) { bool AllNonNeg = true; bool AllNonPos = true; - for (unsigned i = 0, e = AddRec->getNumOperands(); i != e; ++i) { - if (!isKnownNonNegative(AddRec->getOperand(i))) AllNonNeg = false; - if (!isKnownNonPositive(AddRec->getOperand(i))) AllNonPos = false; + for (unsigned i = 1, e = AddRec->getNumOperands(); i != e; ++i) { + if (!isKnownNonNegative(AddRec->getOperand(i))) + AllNonNeg = false; + if (!isKnownNonPositive(AddRec->getOperand(i))) + AllNonPos = false; } if (AllNonNeg) ConservativeResult = ConservativeResult.intersectWith( - ConstantRange(APInt(BitWidth, 0), - APInt::getSignedMinValue(BitWidth)), RangeType); + ConstantRange::getNonEmpty(getSignedRangeMin(AddRec->getStart()), + APInt::getSignedMinValue(BitWidth)), + RangeType); else if (AllNonPos) ConservativeResult = ConservativeResult.intersectWith( - ConstantRange(APInt::getSignedMinValue(BitWidth), - APInt(BitWidth, 1)), RangeType); + ConstantRange::getNonEmpty( + APInt::getSignedMinValue(BitWidth), + getSignedRangeMax(AddRec->getStart()) + 1), + RangeType); } // TODO: non-affine addrec @@ -5710,14 +5739,26 @@ ScalarEvolution::getRangeRef(const SCEV *S, if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) { // For a SCEVUnknown, ask ValueTracking. 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), RangeType); + if (Known.getBitWidth() != BitWidth) + Known = Known.zextOrTrunc(BitWidth, true); + // If Known does not result in full-set, intersect with it. + if (Known.getMinValue() != Known.getMaxValue() + 1) + ConservativeResult = ConservativeResult.intersectWith( + ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1), + RangeType); } else { assert(SignHint == ScalarEvolution::HINT_RANGE_SIGNED && "generalize as needed!"); unsigned NS = ComputeNumSignBits(U->getValue(), DL, 0, &AC, nullptr, &DT); + // If the pointer size is larger than the index size type, this can cause + // NS to be larger than BitWidth. So compensate for this. + if (U->getType()->isPointerTy()) { + unsigned ptrSize = DL.getPointerTypeSizeInBits(U->getType()); + int ptrIdxDiff = ptrSize - BitWidth; + if (ptrIdxDiff > 0 && ptrSize > BitWidth && NS > (unsigned)ptrIdxDiff) + NS -= ptrIdxDiff; + } + if (NS > 1) ConservativeResult = ConservativeResult.intersectWith( ConstantRange(APInt::getSignedMinValue(BitWidth).ashr(NS - 1), @@ -6599,12 +6640,16 @@ ScalarEvolution::getSmallConstantTripMultiple(const Loop *L, return (unsigned)Result->getZExtValue(); } -/// Get the expression for the number of loop iterations for which this loop is -/// guaranteed not to exit via ExitingBlock. Otherwise return -/// SCEVCouldNotCompute. const SCEV *ScalarEvolution::getExitCount(const Loop *L, - BasicBlock *ExitingBlock) { - return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); + BasicBlock *ExitingBlock, + ExitCountKind Kind) { + switch (Kind) { + case Exact: + return getBackedgeTakenInfo(L).getExact(ExitingBlock, this); + case ConstantMaximum: + return getBackedgeTakenInfo(L).getMax(ExitingBlock, this); + }; + llvm_unreachable("Invalid ExitCountKind!"); } const SCEV * @@ -6613,14 +6658,15 @@ ScalarEvolution::getPredicatedBackedgeTakenCount(const Loop *L, return getPredicatedBackedgeTakenInfo(L).getExact(L, this, &Preds); } -const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) { - return getBackedgeTakenInfo(L).getExact(L, this); -} - -/// Similar to getBackedgeTakenCount, except return the least SCEV value that is -/// known never to be less than the actual backedge taken count. -const SCEV *ScalarEvolution::getConstantMaxBackedgeTakenCount(const Loop *L) { - return getBackedgeTakenInfo(L).getMax(this); +const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L, + ExitCountKind Kind) { + switch (Kind) { + case Exact: + return getBackedgeTakenInfo(L).getExact(L, this); + case ConstantMaximum: + return getBackedgeTakenInfo(L).getMax(this); + }; + llvm_unreachable("Invalid ExitCountKind!"); } bool ScalarEvolution::isBackedgeTakenCountMaxOrZero(const Loop *L) { @@ -6929,6 +6975,16 @@ ScalarEvolution::BackedgeTakenInfo::getExact(BasicBlock *ExitingBlock, return SE->getCouldNotCompute(); } +const SCEV * +ScalarEvolution::BackedgeTakenInfo::getMax(BasicBlock *ExitingBlock, + ScalarEvolution *SE) const { + for (auto &ENT : ExitNotTaken) + if (ENT.ExitingBlock == ExitingBlock && ENT.hasAlwaysTruePredicate()) + return ENT.MaxNotTaken; + + return SE->getCouldNotCompute(); +} + /// getMax - Get the max backedge taken count for the loop. const SCEV * ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const { @@ -7020,13 +7076,15 @@ ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo( BasicBlock *ExitBB = EEI.first; const ExitLimit &EL = EEI.second; if (EL.Predicates.empty()) - return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, nullptr); + return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, EL.MaxNotTaken, + nullptr); std::unique_ptr<SCEVUnionPredicate> Predicate(new SCEVUnionPredicate); for (auto *Pred : EL.Predicates) Predicate->add(Pred); - return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, std::move(Predicate)); + return ExitNotTakenInfo(ExitBB, EL.ExactNotTaken, EL.MaxNotTaken, + std::move(Predicate)); }); assert((isa<SCEVCouldNotCompute>(MaxCount) || isa<SCEVConstant>(MaxCount)) && "No point in having a non-constant max backedge taken count!"); @@ -7058,6 +7116,17 @@ ScalarEvolution::computeBackedgeTakenCount(const Loop *L, // Do a union of all the predicates here. for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) { BasicBlock *ExitBB = ExitingBlocks[i]; + + // We canonicalize untaken exits to br (constant), ignore them so that + // proving an exit untaken doesn't negatively impact our ability to reason + // about the loop as whole. + if (auto *BI = dyn_cast<BranchInst>(ExitBB->getTerminator())) + if (auto *CI = dyn_cast<ConstantInt>(BI->getCondition())) { + bool ExitIfTrue = !L->contains(BI->getSuccessor(0)); + if ((ExitIfTrue && CI->isZero()) || (!ExitIfTrue && CI->isOne())) + continue; + } + ExitLimit EL = computeExitLimit(L, ExitBB, AllowPredicates); assert((AllowPredicates || EL.Predicates.empty()) && @@ -7217,6 +7286,11 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( ExitLimit EL1 = computeExitLimitFromCondCached( Cache, L, BO->getOperand(1), ExitIfTrue, ControlsExit && !EitherMayExit, AllowPredicates); + // Be robust against unsimplified IR for the form "and i1 X, true" + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) + return CI->isOne() ? EL0 : EL1; + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0))) + return CI->isOne() ? EL1 : EL0; const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); if (EitherMayExit) { @@ -7265,6 +7339,11 @@ ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl( ExitLimit EL1 = computeExitLimitFromCondCached( Cache, L, BO->getOperand(1), ExitIfTrue, ControlsExit && !EitherMayExit, AllowPredicates); + // Be robust against unsimplified IR for the form "or i1 X, true" + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) + return CI->isZero() ? EL0 : EL1; + if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0))) + return CI->isZero() ? EL1 : EL0; const SCEV *BECount = getCouldNotCompute(); const SCEV *MaxBECount = getCouldNotCompute(); if (EitherMayExit) { @@ -10976,7 +11055,7 @@ struct SCEVCollectAddRecMultiplies { } else if (Unknown) { HasAddRec = true; } else { - bool ContainsAddRec; + bool ContainsAddRec = false; SCEVHasAddRec ContiansAddRec(ContainsAddRec); visitAll(Op, ContiansAddRec); HasAddRec |= ContainsAddRec; @@ -11544,77 +11623,79 @@ void ScalarEvolution::print(raw_ostream &OS) const { // const isn't dangerous. ScalarEvolution &SE = *const_cast<ScalarEvolution *>(this); - OS << "Classifying expressions for: "; - F.printAsOperand(OS, /*PrintType=*/false); - OS << "\n"; - for (Instruction &I : instructions(F)) - if (isSCEVable(I.getType()) && !isa<CmpInst>(I)) { - OS << I << '\n'; - OS << " --> "; - const SCEV *SV = SE.getSCEV(&I); - SV->print(OS); - if (!isa<SCEVCouldNotCompute>(SV)) { - OS << " U: "; - SE.getUnsignedRange(SV).print(OS); - OS << " S: "; - SE.getSignedRange(SV).print(OS); - } - - const Loop *L = LI.getLoopFor(I.getParent()); - - const SCEV *AtUse = SE.getSCEVAtScope(SV, L); - if (AtUse != SV) { + if (ClassifyExpressions) { + OS << "Classifying expressions for: "; + F.printAsOperand(OS, /*PrintType=*/false); + OS << "\n"; + for (Instruction &I : instructions(F)) + if (isSCEVable(I.getType()) && !isa<CmpInst>(I)) { + OS << I << '\n'; OS << " --> "; - AtUse->print(OS); - if (!isa<SCEVCouldNotCompute>(AtUse)) { + const SCEV *SV = SE.getSCEV(&I); + SV->print(OS); + if (!isa<SCEVCouldNotCompute>(SV)) { OS << " U: "; - SE.getUnsignedRange(AtUse).print(OS); + SE.getUnsignedRange(SV).print(OS); OS << " S: "; - SE.getSignedRange(AtUse).print(OS); + SE.getSignedRange(SV).print(OS); } - } - if (L) { - OS << "\t\t" "Exits: "; - const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); - if (!SE.isLoopInvariant(ExitValue, L)) { - OS << "<<Unknown>>"; - } else { - OS << *ExitValue; + const Loop *L = LI.getLoopFor(I.getParent()); + + const SCEV *AtUse = SE.getSCEVAtScope(SV, L); + if (AtUse != SV) { + OS << " --> "; + AtUse->print(OS); + if (!isa<SCEVCouldNotCompute>(AtUse)) { + OS << " U: "; + SE.getUnsignedRange(AtUse).print(OS); + OS << " S: "; + SE.getSignedRange(AtUse).print(OS); + } } - bool First = true; - for (auto *Iter = L; Iter; Iter = Iter->getParentLoop()) { - if (First) { - OS << "\t\t" "LoopDispositions: { "; - First = false; + if (L) { + OS << "\t\t" "Exits: "; + const SCEV *ExitValue = SE.getSCEVAtScope(SV, L->getParentLoop()); + if (!SE.isLoopInvariant(ExitValue, L)) { + OS << "<<Unknown>>"; } else { - OS << ", "; + OS << *ExitValue; } - Iter->getHeader()->printAsOperand(OS, /*PrintType=*/false); - OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, Iter)); - } + bool First = true; + for (auto *Iter = L; Iter; Iter = Iter->getParentLoop()) { + if (First) { + OS << "\t\t" "LoopDispositions: { "; + First = false; + } else { + OS << ", "; + } - for (auto *InnerL : depth_first(L)) { - if (InnerL == L) - continue; - if (First) { - OS << "\t\t" "LoopDispositions: { "; - First = false; - } else { - OS << ", "; + Iter->getHeader()->printAsOperand(OS, /*PrintType=*/false); + OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, Iter)); } - InnerL->getHeader()->printAsOperand(OS, /*PrintType=*/false); - OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, InnerL)); + for (auto *InnerL : depth_first(L)) { + if (InnerL == L) + continue; + if (First) { + OS << "\t\t" "LoopDispositions: { "; + First = false; + } else { + OS << ", "; + } + + InnerL->getHeader()->printAsOperand(OS, /*PrintType=*/false); + OS << ": " << loopDispositionToStr(SE.getLoopDisposition(SV, InnerL)); + } + + OS << " }"; } - OS << " }"; + OS << "\n"; } - - OS << "\n"; - } + } OS << "Determining loop execution counts for: "; F.printAsOperand(OS, /*PrintType=*/false); @@ -11994,6 +12075,12 @@ ScalarEvolution ScalarEvolutionAnalysis::run(Function &F, } PreservedAnalyses +ScalarEvolutionVerifierPass::run(Function &F, FunctionAnalysisManager &AM) { + AM.getResult<ScalarEvolutionAnalysis>(F).verify(); + return PreservedAnalyses::all(); +} + +PreservedAnalyses ScalarEvolutionPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { AM.getResult<ScalarEvolutionAnalysis>(F).print(OS); return PreservedAnalyses::all(); @@ -12462,7 +12549,7 @@ PredicatedScalarEvolution::PredicatedScalarEvolution( const PredicatedScalarEvolution &Init) : RewriteMap(Init.RewriteMap), SE(Init.SE), L(Init.L), Preds(Init.Preds), Generation(Init.Generation), BackedgeCount(Init.BackedgeCount) { - for (const auto &I : Init.FlagsMap) + for (auto I : Init.FlagsMap) FlagsMap.insert(I); } |