diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -105,6 +105,7 @@ #include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/CallSite.h" +#include "llvm/IR/ConstantRange.h" #include "llvm/IR/PassManager.h" namespace llvm { @@ -1503,6 +1504,116 @@ } }; +/// State for an integer range. +struct IntegerRangeState : public AbstractState { + + /// Bitwidth of the associated value. + uint32_t BitWidth; + + /// State representing assumed range, initially set to empty. + ConstantRange Assumed; + + /// State representing known range, initially set to [-inf, inf]. + ConstantRange Known; + + IntegerRangeState(uint32_t BitWidth) + : BitWidth(BitWidth), Assumed(ConstantRange::getEmpty(BitWidth)), + Known(ConstantRange::getFull(BitWidth)) {} + + /// Return the worst possible representable state. + static ConstantRange getWorstState(uint32_t BitWidth) { + return ConstantRange::getFull(BitWidth); + } + + /// Return the best possible representable state. + static ConstantRange getBestState(uint32_t BitWidth) { + return ConstantRange::getEmpty(BitWidth); + } + + /// Return associated values' bit width. + uint32_t getBitWidth() const { return BitWidth; } + + /// See AbstractState::isValidState() + bool isValidState() const override { + return BitWidth > 0 && !Assumed.isFullSet(); + } + + /// See AbstractState::isAtFixpoint() + bool isAtFixpoint() const override { return Assumed == Known; } + + /// See AbstractState::indicateOptimisticFixpoint(...) + ChangeStatus indicateOptimisticFixpoint() override { + Known = Assumed; + return ChangeStatus::CHANGED; + } + + /// See AbstractState::indicatePessimisticFixpoint(...) + ChangeStatus indicatePessimisticFixpoint() override { + Assumed = Known; + return ChangeStatus::CHANGED; + } + + /// Return the known state encoding + ConstantRange getKnown() const { return Known; } + + /// Return the assumed state encoding. + ConstantRange getAssumed() const { return Assumed; } + + /// Unite assumed range with the passed state. + void unionAssumed(const ConstantRange &R) { + // Don't loose a known range. + Assumed = Assumed.unionWith(R).intersectWith(Known); + } + + /// See IntegerRangeState::unionAssumed(..). + void unionAssumed(const IntegerRangeState &R) { + unionAssumed(R.getAssumed()); + } + + /// Unite known range with the passed state. + void unionKnown(const ConstantRange &R) { + // Don't loose a known range. + Known = Known.unionWith(R); + Assumed = Assumed.unionWith(Known); + } + + /// See IntegerRangeState::unionKnown(..). + void unionKnown(const IntegerRangeState &R) { unionKnown(R.getKnown()); } + + /// Intersect known range with the passed state. + void intersectKnown(const ConstantRange &R) { + Assumed = Assumed.intersectWith(R); + Known = Known.intersectWith(R); + } + + /// See IntegerRangeState::intersectKnown(..). + void intersectKnown(const IntegerRangeState &R) { + intersectKnown(R.getKnown()); + } + + /// Equality for IntegerRangeState. + bool operator==(const IntegerRangeState &R) const { + return getAssumed() == R.getAssumed() && getKnown() == R.getKnown(); + } + + /// "Clamp" this state with \p R. The result is subtype dependent but it is + /// intended that only information assumed in both states will be assumed in + /// this one afterwards. + IntegerRangeState operator^=(const IntegerRangeState &R) { + // NOTE: `^=` operator seems like `intersect` but in this case, we need to + // take `union`. + unionAssumed(R); + return *this; + } + + IntegerRangeState operator&=(const IntegerRangeState &R) { + // NOTE: `&=` operator seems like `intersect` but in this case, we need to + // take `union`. + unionKnown(R); + unionAssumed(R); + return *this; + } +}; /// Helper struct necessary as the modular build fails if the virtual method /// IRAttribute::manifest is defined in the Attributor.cpp. struct IRAttributeManifest { @@ -1696,6 +1807,7 @@ raw_ostream & operator<<(raw_ostream &OS, const IntegerStateBase &State); +raw_ostream &operator<<(raw_ostream &OS, const IntegerRangeState &State); ///} struct AttributorPass : public PassInfoMixin { @@ -2331,6 +2443,55 @@ static const char ID; }; +/// An abstract interface for range value analysis. +struct AAValueConstantRange : public IntegerRangeState, + public AbstractAttribute, + public IRPosition { + AAValueConstantRange(const IRPosition &IRP) + : IntegerRangeState( + IRP.getAssociatedValue().getType()->getIntegerBitWidth()), + IRPosition(IRP) {} + + /// Return an IR position, see struct IRPosition. + const IRPosition &getIRPosition() const override { return *this; } + + /// See AbstractAttribute::getState(...). + IntegerRangeState &getState() override { return *this; } + const AbstractState &getState() const override { return *this; } + + /// Create an abstract attribute view for the position \p IRP. + static AAValueConstantRange &createForPosition(const IRPosition &IRP, + Attributor &A); + + /// Return an assumed range for the assocaited value a program point \p CtxI. + /// If \p I is nullptr, simply return an assumed range. + virtual ConstantRange + getAssumedConstantRange(Attributor &A, + const Instruction *CtxI = nullptr) const = 0; + + /// Return a known range for the assocaited value at a program point \p CtxI. + /// If \p I is nullptr, simply return a known range. + virtual ConstantRange + getKnownConstantRange(Attributor &A, + const Instruction *CtxI = nullptr) const = 0; + + /// Return an assumed constant for the assocaited value a program point \p + /// CtxI. + Optional + getAssumedConstantInt(Attributor &A, const Instruction *CtxI = nullptr) const { + ConstantRange RangeV = getAssumedConstantRange(A, CtxI); + if (auto *C = RangeV.getSingleElement()) + return cast( + ConstantInt::get(getAssociatedValue().getType(), *C)); + if (RangeV.isEmptySet()) + return llvm::None; + return nullptr; + } + + /// Unique ID (due to the unique address) + static const char ID; +}; + } // end namespace llvm #endif // LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -23,8 +23,10 @@ #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/LazyValueInfo.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" @@ -127,6 +129,7 @@ PIPE_OPERATOR(AAHeapToStack) PIPE_OPERATOR(AAReachability) PIPE_OPERATOR(AAMemoryBehavior) +PIPE_OPERATOR(AAValueConstantRange) #undef PIPE_OPERATOR } // namespace llvm @@ -3284,6 +3287,8 @@ T.GlobalState &= DS.GlobalState; } + // TODO: Use `AAConstantRange` to infer dereferenceable bytes. + // For now we do not try to "increase" dereferenceability due to negative // indices as we first have to come up with code to deal with loops and // for overflows of the dereferenceable bytes. @@ -4158,6 +4163,28 @@ return true; } + bool askSimplifiedValueForAAValueConstantRange(Attributor &A) { + if (!getAssociatedValue().getType()->isIntegerTy()) + return false; + + const auto &ValueConstantRangeAA = + A.getAAFor(*this, getIRPosition()); + + Optional COpt = + ValueConstantRangeAA.getAssumedConstantInt(A); + if (COpt.hasValue()) { + if (auto *C = COpt.getValue()) + SimplifiedAssociatedValue = C; + else + return false; + } else { + // FIXME: It should be llvm::None but if you set llvm::None, + // values are mistakenly infered as `undef` now. + SimplifiedAssociatedValue = &getAssociatedValue(); + } + return true; + } + /// See AbstractAttribute::manifest(...). ChangeStatus manifest(Attributor &A) override { ChangeStatus Changed = ChangeStatus::UNCHANGED; @@ -4241,7 +4268,8 @@ }; if (!A.checkForAllCallSites(PredForCallSite, *this, true)) - return indicatePessimisticFixpoint(); + if (!askSimplifiedValueForAAValueConstantRange(A)) + return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. return HasValueBefore == SimplifiedAssociatedValue.hasValue() @@ -4267,7 +4295,8 @@ }; if (!A.checkForAllReturnedValues(PredForReturned, *this)) - return indicatePessimisticFixpoint(); + if (!askSimplifiedValueForAAValueConstantRange(A)) + return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. return HasValueBefore == SimplifiedAssociatedValue.hasValue() @@ -4300,10 +4329,10 @@ auto &AA = A.getAAFor(*this, IRPosition::value(V)); if (!Stripped && this == &AA) { // TODO: Look the instruction and check recursively. + LLVM_DEBUG( dbgs() << "[Attributor][ValueSimplify] Can't be stripped more : " << V << "\n"); - indicatePessimisticFixpoint(); return false; } return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue); @@ -4312,7 +4341,8 @@ if (!genericValueTraversal( A, getIRPosition(), *this, static_cast(*this), VisitValueCB)) - return indicatePessimisticFixpoint(); + if (!askSimplifiedValueForAAValueConstantRange(A)) + return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. @@ -5083,7 +5113,451 @@ if (UserI->mayWriteToMemory()) removeAssumedBits(NO_WRITES); } +/// ------------------ Value Constant Range Attribute ------------------------- + +struct AAValueConstantRangeImpl : AAValueConstantRange { + using StateType = IntegerRangeState; + AAValueConstantRangeImpl(const IRPosition &IRP) : AAValueConstantRange(IRP) {} + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + std::string Str; + llvm::raw_string_ostream OS(Str); + OS << "range(" << getBitWidth() << ")<"; + getKnown().print(OS); + OS << " / "; + getAssumed().print(OS); + OS << ">"; + return OS.str(); + } + + /// Helper function to get a SCEV expr for the associated value at program + /// point \p I. + const SCEV *getSCEV(Attributor &A, const Instruction *I = nullptr) const { + if (!getAnchorScope()) + return nullptr; + + ScalarEvolution *SE = + A.getInfoCache().getAnalysisResultForFunction( + *getAnchorScope()); + + LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction( + *getAnchorScope()); + + if (!SE || !LI) + return nullptr; + + const SCEV *S = SE->getSCEV(&getAssociatedValue()); + if (!I) + return S; + + return SE->getSCEVAtScope(S, LI->getLoopFor(I->getParent())); + } + + /// Helper function to get a range from SCEV for the associated value at + /// program point \p I. + ConstantRange getConstantRangeFromSCEV(Attributor &A, + const Instruction *I = nullptr) const { + if (!getAnchorScope()) + return getWorstState(getBitWidth()); + + ScalarEvolution *SE = + A.getInfoCache().getAnalysisResultForFunction( + *getAnchorScope()); + + const SCEV *S = getSCEV(A, I); + if (!SE || !S) + return getWorstState(getBitWidth()); + + return SE->getUnsignedRange(S); + } + + /// Helper function to get a range from LVI for the associated value at + /// program point \p I. + ConstantRange + getConstantRangeFromLVI(Attributor &A, + const Instruction *CtxI = nullptr) const { + if (!getAnchorScope()) + return getWorstState(getBitWidth()); + + LazyValueInfo *LVI = + A.getInfoCache().getAnalysisResultForFunction( + *getAnchorScope()); + + if (!LVI || !CtxI) + return getWorstState(getBitWidth()); + return LVI->getConstantRange(&getAssociatedValue(), + const_cast(CtxI->getParent()), + const_cast(CtxI)); + } + + /// See AAValueConstantRange::getKnownConstantRange(..). + ConstantRange + getKnownConstantRange(Attributor &A, + const Instruction *CtxI = nullptr) const override { + if (!CtxI || CtxI == getCtxI()) + return getKnown(); + + ConstantRange LVIR = getConstantRangeFromLVI(A, CtxI); + ConstantRange SCEVR = getConstantRangeFromSCEV(A, CtxI); + return getKnown().intersectWith(SCEVR).intersectWith(LVIR); + } + + /// See AAValueConstantRange::getAssumedConstantRange(..). + ConstantRange + getAssumedConstantRange(Attributor &A, + const Instruction *CtxI = nullptr) const override { + // TODO: Make SCEV use Attributor assumption. + // We may be able to bound a variable range via assumptions in + // Attributor. ex.) If x is assumed to be in [1, 3] and y is known to + // evolve to x^2 + x, then we can say that y is in [2, 12]. + + if (!CtxI || CtxI == getCtxI()) + return getAssumed(); + + ConstantRange LVIR = getConstantRangeFromLVI(A, CtxI); + ConstantRange SCEVR = getConstantRangeFromSCEV(A, CtxI); + return getAssumed().intersectWith(SCEVR).intersectWith(LVIR); + } + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + // Intersect a range given by SCEV. + intersectKnown(getConstantRangeFromSCEV(A, getCtxI())); + + // Intersect a range given by LVI. + intersectKnown(getConstantRangeFromLVI(A, getCtxI())); + } + + /// Helper function to create MDNode for range metadata. + static MDNode * + getMDNodeForConstantRange(Type *Ty, LLVMContext &Ctx, + const ConstantRange &AssumedConstantRange) { + Metadata *LowAndHigh[] = {ConstantAsMetadata::get(ConstantInt::get( + Ty, AssumedConstantRange.getLower())), + ConstantAsMetadata::get(ConstantInt::get( + Ty, AssumedConstantRange.getUpper()))}; + return MDNode::get(Ctx, LowAndHigh); + } + + /// Return true if \p Assumed is included in \p KnownRanges. + static bool isBetterRange(const ConstantRange &Assumed, MDNode *KnownRanges) { + + if (Assumed.isFullSet()) + return false; + + if (!KnownRanges) + return true; + + // If multiple ranges are annotated in IR, we give up to annotate assumed + // range for now. + + // TODO: If there exists a known range which containts assumed range, we + // can say assumed range is better. + if (KnownRanges->getNumOperands() > 2) + return false; + + ConstantInt *Lower = + mdconst::extract(KnownRanges->getOperand(0)); + ConstantInt *Upper = + mdconst::extract(KnownRanges->getOperand(1)); + + ConstantRange Known(Lower->getValue(), Upper->getValue()); + return Known.contains(Assumed) && Known != Assumed; + } + + /// Helper function to set range metadata. + static bool + setRangeMetadataIfisBetterRange(Instruction *I, + const ConstantRange &AssumedConstantRange) { + auto *OldRangeMD = I->getMetadata(LLVMContext::MD_range); + if (isBetterRange(AssumedConstantRange, OldRangeMD)) { + if (!AssumedConstantRange.isEmptySet()) { + I->setMetadata(LLVMContext::MD_range, + getMDNodeForConstantRange(I->getType(), I->getContext(), + AssumedConstantRange)); + return true; + } + } + return false; + } + + /// See AbstractAttribute::manifest() + ChangeStatus manifest(Attributor &A) override { + ChangeStatus Changed = ChangeStatus::UNCHANGED; + ConstantRange AssumedConstantRange = getAssumedConstantRange(A); + assert(!AssumedConstantRange.isFullSet() && "Invalid state"); + + auto &V = getAssociatedValue(); + if (!AssumedConstantRange.isEmptySet() && + !AssumedConstantRange.isSingleElement()) { + if (Instruction *I = dyn_cast(&V)) + if (isa(I) || isa(I)) + if (setRangeMetadataIfisBetterRange(I, AssumedConstantRange)) + Changed = ChangeStatus::CHANGED; + } + + return Changed; + } +}; + +struct AAValueConstantRangeArgument final : public AAValueConstantRangeImpl { + + AAValueConstantRangeArgument(const IRPosition &IRP) + : AAValueConstantRangeImpl(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + // TODO: Use AAArgumentFromCallSiteArguments + + IntegerRangeState S(getBitWidth()); + clampCallSiteArgumentStates( + A, *this, S); + + // TODO: If we know we visited all incoming values, thus no are assumed + // dead, we can take the known information from the state T. + return clampStateAndIndicateChange(this->getState(), S); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_ARG_ATTR(value_range) + } +}; + +struct AAValueConstantRangeReturned : AAValueConstantRangeImpl { + AAValueConstantRangeReturned(const IRPosition &IRP) + : AAValueConstantRangeImpl(IRP) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + // TODO: Use AAReturnedFromReturnedValues + + // TODO: If we know we visited all returned values, thus no are assumed + // dead, we can take the known information from the state T. + + IntegerRangeState S(getBitWidth()); + + clampReturnedValueStates(A, *this, + S); + return clampStateAndIndicateChange(this->getState(), S); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FNRET_ATTR(value_range) + } +}; +struct AAValueConstantRangeFloating : AAValueConstantRangeImpl { + AAValueConstantRangeFloating(const IRPosition &IRP) + : AAValueConstantRangeImpl(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + AAValueConstantRange::initialize(A); + Value &V = getAssociatedValue(); + + if (auto *C = dyn_cast(&V)) { + unionAssumed(ConstantRange(C->getValue())); + indicateOptimisticFixpoint(); + return; + } + + if (isa(&V)) { + indicateOptimisticFixpoint(); + return; + } + + if (auto *I = dyn_cast(&V)) + if (isa(I) || isa(I)) { + Value *LHS = I->getOperand(0); + Value *RHS = I->getOperand(1); + + if (LHS->getType()->isIntegerTy() && RHS->getType()->isIntegerTy()) + return; + } + + // If it is a load instruction with range metadata, use it. + if (LoadInst *LI = dyn_cast(&V)) + if (auto *RangeMD = LI->getMetadata(LLVMContext::MD_range)) { + intersectKnown(getConstantRangeFromMetadata(*RangeMD)); + return; + } + + // Otherwise we give up. + indicatePessimisticFixpoint(); + + LLVM_DEBUG(dbgs() << "[Attributor][AAValueConstantRange] We give up: " + << getAssociatedValue()); + } + + bool calculateBinaryOperator(Attributor &A, BinaryOperator *BinOp, + IntegerRangeState &T, Instruction *CtxI) { + Value *LHS = BinOp->getOperand(0); + Value *RHS = BinOp->getOperand(1); + + auto &LHSAA = + A.getAAFor(*this, IRPosition::value(*LHS)); + auto LHSAARange = LHSAA.getAssumedConstantRange(A, CtxI); + + auto &RHSAA = + A.getAAFor(*this, IRPosition::value(*RHS)); + auto RHSAARange = RHSAA.getAssumedConstantRange(A, CtxI); + + auto AssumedRange = LHSAARange.binaryOp(BinOp->getOpcode(), RHSAARange); + + T.unionAssumed(AssumedRange); + + // TODO: Track a known state too. + + return T.isValidState(); + } + + bool calculateCmpInst(Attributor &A, CmpInst *CmpI, IntegerRangeState &T, + Instruction *CtxI) { + Value *LHS = CmpI->getOperand(0); + Value *RHS = CmpI->getOperand(1); + + auto &LHSAA = + A.getAAFor(*this, IRPosition::value(*LHS)); + auto &RHSAA = + A.getAAFor(*this, IRPosition::value(*RHS)); + + auto LHSAARange = LHSAA.getAssumedConstantRange(A, CtxI); + auto RHSAARange = RHSAA.getAssumedConstantRange(A, CtxI); + + // If one of them is empty set, we can't decide. + if (LHSAARange.isEmptySet() || RHSAARange.isEmptySet()) + return true; + + bool MustTrue = false, MustFalse = false; + + auto AllowedRegion = + ConstantRange::makeAllowedICmpRegion(CmpI->getPredicate(), RHSAARange); + + auto SatisfyingRegion = ConstantRange::makeSatisfyingICmpRegion( + CmpI->getPredicate(), RHSAARange); + + if (AllowedRegion.intersectWith(LHSAARange).isEmptySet()) + MustFalse = true; + + if (SatisfyingRegion.contains(LHSAARange)) + MustTrue = true; + + assert((!MustTrue || !MustFalse) && + "Either MustTrue or MustFalse should be false!"); + + if (MustTrue) + T.unionAssumed(ConstantRange(APInt(/* numBits */ 1, /* val */ 1))); + else if (MustFalse) + T.unionAssumed(ConstantRange(APInt(/* numBits */ 1, /* val */ 0))); + else + T.unionAssumed(ConstantRange(/* BitWidth */ 1, /* isFullSet */ true)); + + LLVM_DEBUG(dbgs() << "[AAValueConstantRange] " << *CmpI << " " << LHSAA + << " " << RHSAA << "\n"); + + // TODO: Track a known state too. + return T.isValidState(); + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + Instruction *CtxI = getCtxI(); + auto VisitValueCB = [&](Value &V, IntegerRangeState &T, + bool Stripped) -> bool { + Instruction *I = dyn_cast(&V); + if (!I) { + + // If the value is not instruction, we query AA to Attributor. + const auto &AA = + A.getAAFor(*this, IRPosition::value(V)); + + // Clamp operator is not used to utilize a program point CtxI. + T.unionAssumed(AA.getAssumedConstantRange(A, CtxI)); + + return T.isValidState(); + } + + if (auto *BinOp = dyn_cast(I)) + return calculateBinaryOperator(A, BinOp, T, CtxI); + else if (auto *CmpI = dyn_cast(I)) + return calculateCmpInst(A, CmpI, T, CtxI); + else { + // Give up with other instructions. + // TODO: Add other instructions + + T.indicatePessimisticFixpoint(); + return false; + } + }; + + IntegerRangeState T(getBitWidth()); + + if (!genericValueTraversal( + A, getIRPosition(), *this, T, VisitValueCB)) + return indicatePessimisticFixpoint(); + + return clampStateAndIndicateChange(getState(), T); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FLOATING_ATTR(value_range) + } +}; + +struct AAValueConstantRangeFunction : AAValueConstantRangeImpl { + AAValueConstantRangeFunction(const IRPosition &IRP) + : AAValueConstantRangeImpl(IRP) {} + + /// See AbstractAttribute::initialize(...). + ChangeStatus updateImpl(Attributor &A) override { + llvm_unreachable("AAValueConstantRange(Function|CallSite)::updateImpl will " + "not be called"); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(value_range) } +}; + +struct AAValueConstantRangeCallSite : AAValueConstantRangeFunction { + AAValueConstantRangeCallSite(const IRPosition &IRP) + : AAValueConstantRangeFunction(IRP) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(value_range) } +}; + +struct AAValueConstantRangeCallSiteReturned : AAValueConstantRangeReturned { + AAValueConstantRangeCallSiteReturned(const IRPosition &IRP) + : AAValueConstantRangeReturned(IRP) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + // If it is a load instruction with range metadata, use the metadata. + if (CallInst *CI = dyn_cast(&getAssociatedValue())) + if (auto *RangeMD = CI->getMetadata(LLVMContext::MD_range)) + intersectKnown(getConstantRangeFromMetadata(*RangeMD)); + + AAValueConstantRangeReturned::initialize(A); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSRET_ATTR(value_range) + } +}; +struct AAValueConstantRangeCallSiteArgument : AAValueConstantRangeFloating { + AAValueConstantRangeCallSiteArgument(const IRPosition &IRP) + : AAValueConstantRangeFloating(IRP) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSARG_ATTR(value_range) + } +}; /// ---------------------------------------------------------------------------- /// Attributor /// ---------------------------------------------------------------------------- @@ -6121,10 +6595,16 @@ return true; if (!Callee->getReturnType()->isVoidTy() && !CS->use_empty()) { + IRPosition CSRetPos = IRPosition::callsite_returned(CS); // Call site return values might be dead. getOrCreateAAFor(CSRetPos); + + // Call site return integer values might be limited by a constant range. + if (Callee->getReturnType()->isIntegerTy()) { + getOrCreateAAFor(CSRetPos); + } } for (int i = 0, e = CS.getNumArgOperands(); i < e; i++) { @@ -6224,13 +6704,23 @@ } template -raw_ostream &llvm:: -operator<<(raw_ostream &OS, - const IntegerStateBase &S) { +raw_ostream & +llvm::operator<<(raw_ostream &OS, + const IntegerStateBase &S) { return OS << "(" << S.getKnown() << "-" << S.getAssumed() << ")" << static_cast(S); } +raw_ostream &llvm::operator<<(raw_ostream &OS, const IntegerRangeState &S) { + OS << "range-state(" << S.getBitWidth() << ")<"; + S.getKnown().print(OS); + OS << " / "; + S.getAssumed().print(OS); + OS << ">"; + + return OS << static_cast(S); +} + raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) { return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : "")); } @@ -6347,6 +6837,7 @@ const char AAValueSimplify::ID = 0; const char AAHeapToStack::ID = 0; const char AAMemoryBehavior::ID = 0; +const char AAValueConstantRange::ID = 0; // Macro magic to create the static generator function for attributes that // follow the naming scheme. @@ -6452,6 +6943,7 @@ CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AADereferenceable) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAlign) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture) +CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueConstantRange) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) diff --git a/llvm/test/Transforms/Attributor/IPConstantProp/return-constant.ll b/llvm/test/Transforms/Attributor/IPConstantProp/return-constant.ll --- a/llvm/test/Transforms/Attributor/IPConstantProp/return-constant.ll +++ b/llvm/test/Transforms/Attributor/IPConstantProp/return-constant.ll @@ -9,8 +9,7 @@ ; CHECK-NEXT: [[X:%.*]] = call i32 @foo(i1 [[C]]) ; CHECK-NEXT: br label [[OK:%.*]] ; CHECK: OK: -; CHECK-NEXT: [[Y:%.*]] = icmp ne i32 52, 0 -; CHECK-NEXT: ret i1 [[Y]] +; CHECK-NEXT: ret i1 true ; CHECK: FAIL: ; CHECK-NEXT: unreachable ; @@ -46,8 +45,7 @@ ; CHECK-LABEL: define {{[^@]+}}@caller ; CHECK-SAME: (i1 [[C:%.*]]) ; CHECK-NEXT: [[X:%.*]] = call i32 @foo(i1 [[C]]) -; CHECK-NEXT: [[Y:%.*]] = icmp ne i32 52, 0 -; CHECK-NEXT: ret i1 [[Y]] +; CHECK-NEXT: ret i1 true ; %X = call i32 @foo( i1 %C ) ; [#uses=1] %Y = icmp ne i32 %X, 0 ; [#uses=1] diff --git a/llvm/test/Transforms/Attributor/IPConstantProp/solve-after-each-resolving-undefs-for-function.ll b/llvm/test/Transforms/Attributor/IPConstantProp/solve-after-each-resolving-undefs-for-function.ll --- a/llvm/test/Transforms/Attributor/IPConstantProp/solve-after-each-resolving-undefs-for-function.ll +++ b/llvm/test/Transforms/Attributor/IPConstantProp/solve-after-each-resolving-undefs-for-function.ll @@ -33,12 +33,11 @@ ; CHECK-NEXT: br label [[IF_THEN:%.*]] ; CHECK: if.then: ; CHECK-NEXT: [[CALL:%.*]] = call i32 @testf(i1 [[C]]) -; CHECK-NEXT: [[RES:%.*]] = icmp eq i32 10, 10 -; CHECK-NEXT: br i1 [[RES]], label [[RET1:%.*]], label [[RET2:%.*]] +; CHECK-NEXT: br label [[RET1:%.*]] ; CHECK: ret1: ; CHECK-NEXT: ret i32 99 ; CHECK: ret2: -; CHECK-NEXT: ret i32 0 +; CHECK-NEXT: unreachable ; entry: br label %if.then @@ -59,7 +58,7 @@ ; CHECK-LABEL: define {{[^@]+}}@main ; CHECK-SAME: (i1 [[C:%.*]]) ; CHECK-NEXT: [[RES:%.*]] = call i32 @test1(i1 [[C]]) -; CHECK-NEXT: ret i32 [[RES]] +; CHECK-NEXT: ret i32 99 ; %res = call i32 @test1(i1 %c) ret i32 %res diff --git a/llvm/test/Transforms/Attributor/dereferenceable-1.ll b/llvm/test/Transforms/Attributor/dereferenceable-1.ll --- a/llvm/test/Transforms/Attributor/dereferenceable-1.ll +++ b/llvm/test/Transforms/Attributor/dereferenceable-1.ll @@ -1,4 +1,5 @@ -; RUN: opt -attributor -attributor-manifest-internal --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -attributor -attributor-manifest-internal --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR declare void @deref_phi_user(i32* %a); @@ -207,3 +208,105 @@ store i32 1, i32* %0 ret void } + +; TEST 8 +; Use Constant range in deereferenceable +; void g(int *p, long long int *range){ +; int r = *range ; // [10, 99] +; fill_range(p, *range); +; } + +; void fill_range(int* p, long long int start){ +; for(long long int i = start;i + ret i32 30 +} + +; FIXME: We should be able to merge cont into do. +define i32 @test4(i32 %i, i1 %f, i32 %n) { +; CHECK-LABEL: define {{[^@]+}}@test4 +; CHECK-SAME: (i32 [[I:%.*]], i1 [[F:%.*]], i32 [[N:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: [[C:%.*]] = icmp ne i32 [[I:%.*]], -2134 +; CHECK-NEXT: br i1 [[C]], label [[DO:%.*]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: [[C1:%.*]] = icmp ne i32 [[I]], -42 +; CHECK-NEXT: br i1 [[C1]], label [[EXIT2:%.*]], label [[EXIT]] +; CHECK: cont: +; CHECK-NEXT: call void @dummy(i1 [[F:%.*]]) +; CHECK-NEXT: br label [[EXIT2]] +; CHECK: do: +; CHECK-NEXT: call void @dummy(i1 [[F]]) +; CHECK-NEXT: [[CONSUME:%.*]] = call i32 @exit() +; CHECK-NEXT: call void @llvm.assume(i1 [[F]]) +; CHECK-NEXT: [[COND:%.*]] = icmp eq i1 [[F]], false +; CHECK-NEXT: br i1 [[COND]], label [[EXIT]], label [[CONT:%.*]] +; CHECK: exit2: +; CHECK-NEXT: ret i32 30 +; +; FIXME: COND should be replaced with false. This will be fixed by improving LVI. +entry: + %c = icmp ne i32 %i, -2134 + br i1 %c, label %do, label %exit + +exit: ; preds = %do, %cont, %exit, %entry + %c1 = icmp ne i32 %i, -42 + br i1 %c1, label %exit2, label %exit + +cont: ; preds = %do + call void @dummy(i1 %f) + br label %exit2 + +do: ; preds = %entry + call void @dummy(i1 %f) + %consume = call i32 @exit() + call void @llvm.assume(i1 %f) + %cond = icmp eq i1 %f, false + br i1 %cond, label %exit, label %cont + +exit2: ; preds = %cont, %exit + ret i32 30 +} + +declare i32 @exit() +declare i32 @consume(i1) +declare void @llvm.assume(i1) nounwind +declare void @dummy(i1) nounwind +declare void @llvm.experimental.guard(i1, ...) diff --git a/llvm/test/Transforms/Attributor/lvi-for-ashr.ll b/llvm/test/Transforms/Attributor/lvi-for-ashr.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/Attributor/lvi-for-ashr.ll @@ -0,0 +1,46 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -passes=attributor -attributor-disable=false -S < %s | FileCheck %s +define i32 @test-ashr(i32 %c) { +; CHECK-LABEL: define {{[^@]+}}@test-ashr +; CHECK-SAME: (i32 [[C:%.*]]) +; CHECK-NEXT: chk65: +; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i32 [[C:%.*]], 65 +; CHECK-NEXT: br i1 [[CMP]], label [[RETURN:%.*]], label [[CHK0:%.*]] +; CHECK: chk0: +; CHECK-NEXT: [[CMP1:%.*]] = icmp slt i32 [[C]], 0 +; CHECK-NEXT: br i1 [[CMP]], label [[RETURN]], label [[BB_IF:%.*]] +; CHECK: bb_if: +; CHECK-NEXT: [[ASHR_VAL:%.*]] = ashr exact i32 [[C]], 2 +; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i32 [[ASHR_VAL]], 15 +; CHECK-NEXT: br i1 [[CMP2]], label [[BB_THEN:%.*]], label [[RETURN]] +; CHECK: bb_then: +; CHECK-NEXT: [[CMP3:%.*]] = icmp eq i32 [[ASHR_VAL]], 16 +; CHECK-NEXT: [[DOT:%.*]] = select i1 [[CMP3]], i32 3, i32 2 +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL:%.*]] = phi i32 [ 0, [[CHK65:%.*]] ], [ 1, [[CHK0]] ], [ [[DOT]], [[BB_THEN]] ], [ 4, [[BB_IF]] ] +; CHECK-NEXT: ret i32 [[RETVAL]] +; +; FIXME: DOT should be replaced with 3 +chk65: + %cmp = icmp sgt i32 %c, 65 + br i1 %cmp, label %return, label %chk0 + +chk0: + %cmp1 = icmp slt i32 %c, 0 + br i1 %cmp, label %return, label %bb_if + +bb_if: + %ashr.val = ashr exact i32 %c, 2 + %cmp2 = icmp sgt i32 %ashr.val, 15 + br i1 %cmp2, label %bb_then, label %return + +bb_then: + %cmp3 = icmp eq i32 %ashr.val, 16 + %. = select i1 %cmp3, i32 3, i32 2 + br label %return + +return: + %retval = phi i32 [0, %chk65], [1, %chk0], [%., %bb_then], [4, %bb_if] + ret i32 %retval +} diff --git a/llvm/test/Transforms/Attributor/range.ll b/llvm/test/Transforms/Attributor/range.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/Attributor/range.ll @@ -0,0 +1,504 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -passes=attributor -attributor-disable=false -S < %s | FileCheck %s + +define i32 @test0(i32* %p) { +; CHECK-LABEL: define {{[^@]+}}@test0 +; CHECK-SAME: (i32* nocapture nofree nonnull readonly dereferenceable(4) [[P:%.*]]) +; CHECK-NEXT: [[A:%.*]] = load i32, i32* [[P]], !range !0 +; CHECK-NEXT: ret i32 [[A]] +; + %a = load i32, i32* %p, !range !0 + ret i32 %a +} + +define i32 @test0-range-check(i32* %p) { +; CHECK-LABEL: define {{[^@]+}}@test0-range-check +; CHECK-SAME: (i32* nocapture nofree readonly [[P:%.*]]) +; CHECK-NEXT: [[A:%.*]] = tail call i32 @test0(i32* nocapture nofree readonly [[P]]) +; CHECK-SAME: !range !0 +; CHECK-NEXT: ret i32 [[A]] +; + %a = tail call i32 @test0(i32* %p) + ret i32 %a +} + +declare void @use3-dummy(i1, i1, i1) +define void @use3(i1, i1, i1) { +; CHECK-LABEL: define {{[^@]+}}@use3 +; CHECK-SAME: (i1 [[TMP0:%.*]], i1 [[TMP1:%.*]], i1 [[TMP2:%.*]]) +; CHECK-NEXT: tail call void @use3-dummy(i1 [[TMP0]], i1 [[TMP1]], i1 [[TMP2]]) +; CHECK-NEXT: ret void +; + tail call void @use3-dummy(i1 %0, i1 %1, i1 %2) + ret void +} + +; TEST0 icmp test +define void @test0-icmp-check(i32* %p){ +; CHECK-LABEL: define {{[^@]+}}@test0-icmp-check +; CHECK-SAME: (i32* nocapture nofree readonly [[P:%.*]]) +; CHECK-NEXT: [[RET:%.*]] = tail call i32 @test0(i32* nocapture nofree readonly [[P]]) +; CHECK-SAME: !range !0 +; CHECK-NEXT: [[CMP_EQ_2:%.*]] = icmp eq i32 [[RET]], 9 +; CHECK-NEXT: [[CMP_EQ_3:%.*]] = icmp eq i32 [[RET]], 8 +; CHECK-NEXT: [[CMP_EQ_4:%.*]] = icmp eq i32 [[RET]], 1 +; CHECK-NEXT: [[CMP_EQ_5:%.*]] = icmp eq i32 [[RET]], 0 +; CHECK-NEXT: tail call void @use3(i1 false, i1 [[CMP_EQ_2]], i1 [[CMP_EQ_3]]) +; CHECK-NEXT: tail call void @use3(i1 [[CMP_EQ_4]], i1 [[CMP_EQ_5]], i1 false) +; CHECK-NEXT: [[CMP_NE_2:%.*]] = icmp ne i32 [[RET]], 9 +; CHECK-NEXT: [[CMP_NE_3:%.*]] = icmp ne i32 [[RET]], 8 +; CHECK-NEXT: [[CMP_NE_4:%.*]] = icmp ne i32 [[RET]], 1 +; CHECK-NEXT: [[CMP_NE_5:%.*]] = icmp ne i32 [[RET]], 0 +; CHECK-NEXT: tail call void @use3(i1 true, i1 [[CMP_NE_2]], i1 [[CMP_NE_3]]) +; CHECK-NEXT: tail call void @use3(i1 [[CMP_NE_4]], i1 [[CMP_NE_5]], i1 true) +; CHECK-NEXT: [[CMP_UGT_3:%.*]] = icmp ugt i32 [[RET]], 8 +; CHECK-NEXT: [[CMP_UGT_4:%.*]] = icmp ugt i32 [[RET]], 1 +; CHECK-NEXT: [[CMP_UGT_5:%.*]] = icmp ugt i32 [[RET]], 0 +; CHECK-NEXT: tail call void @use3(i1 false, i1 false, i1 [[CMP_UGT_3]]) +; CHECK-NEXT: tail call void @use3(i1 [[CMP_UGT_4]], i1 [[CMP_UGT_5]], i1 false) +; CHECK-NEXT: [[CMP_UGE_2:%.*]] = icmp uge i32 [[RET]], 9 +; CHECK-NEXT: [[CMP_UGE_3:%.*]] = icmp uge i32 [[RET]], 8 +; CHECK-NEXT: [[CMP_UGE_4:%.*]] = icmp uge i32 [[RET]], 1 +; CHECK-NEXT: tail call void @use3(i1 false, i1 [[CMP_UGE_2]], i1 [[CMP_UGE_3]]) +; CHECK-NEXT: tail call void @use3(i1 [[CMP_UGE_4]], i1 true, i1 false) +; CHECK-NEXT: [[CMP_SGT_3:%.*]] = icmp sgt i32 [[RET]], 8 +; CHECK-NEXT: [[CMP_SGT_4:%.*]] = icmp sgt i32 [[RET]], 1 +; CHECK-NEXT: [[CMP_SGT_5:%.*]] = icmp sgt i32 [[RET]], 0 +; CHECK-NEXT: tail call void @use3(i1 false, i1 false, i1 [[CMP_SGT_3]]) +; CHECK-NEXT: tail call void @use3(i1 [[CMP_SGT_4]], i1 [[CMP_SGT_5]], i1 true) +; CHECK-NEXT: [[CMP_GTE_2:%.*]] = icmp sge i32 [[RET]], 9 +; CHECK-NEXT: [[CMP_GTE_3:%.*]] = icmp sge i32 [[RET]], 8 +; CHECK-NEXT: [[CMP_GTE_4:%.*]] = icmp sge i32 [[RET]], 1 +; CHECK-NEXT: tail call void @use3(i1 false, i1 [[CMP_GTE_2]], i1 [[CMP_GTE_3]]) +; CHECK-NEXT: tail call void @use3(i1 [[CMP_GTE_4]], i1 true, i1 true) +; CHECK-NEXT: [[CMP_SLT_2:%.*]] = icmp slt i32 [[RET]], 9 +; CHECK-NEXT: [[CMP_SLT_3:%.*]] = icmp slt i32 [[RET]], 8 +; CHECK-NEXT: [[CMP_SLT_4:%.*]] = icmp slt i32 [[RET]], 1 +; CHECK-NEXT: tail call void @use3(i1 true, i1 [[CMP_SLT_2]], i1 [[CMP_SLT_3]]) +; CHECK-NEXT: tail call void @use3(i1 [[CMP_SLT_4]], i1 false, i1 false) +; CHECK-NEXT: [[CMP_LTE_3:%.*]] = icmp sle i32 [[RET]], 8 +; CHECK-NEXT: [[CMP_LTE_4:%.*]] = icmp sle i32 [[RET]], 1 +; CHECK-NEXT: [[CMP_LTE_5:%.*]] = icmp sle i32 [[RET]], 0 +; CHECK-NEXT: tail call void @use3(i1 true, i1 true, i1 [[CMP_LTE_3]]) +; CHECK-NEXT: tail call void @use3(i1 [[CMP_LTE_4]], i1 [[CMP_LTE_5]], i1 false) +; CHECK-NEXT: ret void +; + ; ret = [0, 10) + %ret = tail call i32 @test0(i32 *%p) + + ; ret = [0, 10), eq + %cmp-eq-1 = icmp eq i32 %ret, 10 + %cmp-eq-2 = icmp eq i32 %ret, 9 + %cmp-eq-3 = icmp eq i32 %ret, 8 + %cmp-eq-4 = icmp eq i32 %ret, 1 + %cmp-eq-5 = icmp eq i32 %ret, 0 + %cmp-eq-6 = icmp eq i32 %ret, -1 + tail call void @use3(i1 %cmp-eq-1, i1 %cmp-eq-2, i1 %cmp-eq-3) + tail call void @use3(i1 %cmp-eq-4, i1 %cmp-eq-5, i1 %cmp-eq-6) + + ; ret = [0, 10), ne + %cmp-ne-1 = icmp ne i32 %ret, 10 + %cmp-ne-2 = icmp ne i32 %ret, 9 + %cmp-ne-3 = icmp ne i32 %ret, 8 + %cmp-ne-4 = icmp ne i32 %ret, 1 + %cmp-ne-5 = icmp ne i32 %ret, 0 + %cmp-ne-6 = icmp ne i32 %ret, -1 + tail call void @use3(i1 %cmp-ne-1, i1 %cmp-ne-2, i1 %cmp-ne-3) + tail call void @use3(i1 %cmp-ne-4, i1 %cmp-ne-5, i1 %cmp-ne-6) + + ; ret = [0, 10), ugt + %cmp-ugt-1 = icmp ugt i32 %ret, 10 + %cmp-ugt-2 = icmp ugt i32 %ret, 9 + %cmp-ugt-3 = icmp ugt i32 %ret, 8 + %cmp-ugt-4 = icmp ugt i32 %ret, 1 + %cmp-ugt-5 = icmp ugt i32 %ret, 0 + %cmp-ugt-6 = icmp ugt i32 %ret, -1 + tail call void @use3(i1 %cmp-ugt-1, i1 %cmp-ugt-2, i1 %cmp-ugt-3) + tail call void @use3(i1 %cmp-ugt-4, i1 %cmp-ugt-5, i1 %cmp-ugt-6) + + ; ret = [0, 10), uge + %cmp-uge-1 = icmp uge i32 %ret, 10 + %cmp-uge-2 = icmp uge i32 %ret, 9 + %cmp-uge-3 = icmp uge i32 %ret, 8 + %cmp-uge-4 = icmp uge i32 %ret, 1 + %cmp-uge-5 = icmp uge i32 %ret, 0 + %cmp-uge-6 = icmp uge i32 %ret, -1 + tail call void @use3(i1 %cmp-uge-1, i1 %cmp-uge-2, i1 %cmp-uge-3) + tail call void @use3(i1 %cmp-uge-4, i1 %cmp-uge-5, i1 %cmp-uge-6) + + ; ret = [0, 10), sgt + %cmp-sgt-1 = icmp sgt i32 %ret, 10 + %cmp-sgt-2 = icmp sgt i32 %ret, 9 + %cmp-sgt-3 = icmp sgt i32 %ret, 8 + %cmp-sgt-4 = icmp sgt i32 %ret, 1 + %cmp-sgt-5 = icmp sgt i32 %ret, 0 + %cmp-sgt-6 = icmp sgt i32 %ret, -1 + tail call void @use3(i1 %cmp-sgt-1, i1 %cmp-sgt-2, i1 %cmp-sgt-3) + tail call void @use3(i1 %cmp-sgt-4, i1 %cmp-sgt-5, i1 %cmp-sgt-6) + + ; ret = [0, 10), sge + %cmp-gte-1 = icmp sge i32 %ret, 10 + %cmp-gte-2 = icmp sge i32 %ret, 9 + %cmp-gte-3 = icmp sge i32 %ret, 8 + %cmp-gte-4 = icmp sge i32 %ret, 1 + %cmp-gte-5 = icmp sge i32 %ret, 0 + %cmp-gte-6 = icmp sge i32 %ret, -1 + tail call void @use3(i1 %cmp-gte-1, i1 %cmp-gte-2, i1 %cmp-gte-3) + tail call void @use3(i1 %cmp-gte-4, i1 %cmp-gte-5, i1 %cmp-gte-6) + + ; ret = [0, 10), slt + %cmp-slt-1 = icmp slt i32 %ret, 10 + %cmp-slt-2 = icmp slt i32 %ret, 9 + %cmp-slt-3 = icmp slt i32 %ret, 8 + %cmp-slt-4 = icmp slt i32 %ret, 1 + %cmp-slt-5 = icmp slt i32 %ret, 0 + %cmp-slt-6 = icmp slt i32 %ret, -1 + tail call void @use3(i1 %cmp-slt-1, i1 %cmp-slt-2, i1 %cmp-slt-3) + tail call void @use3(i1 %cmp-slt-4, i1 %cmp-slt-5, i1 %cmp-slt-6) + + ; ret = [0, 10), sle + %cmp-lte-1 = icmp sle i32 %ret, 10 + %cmp-lte-2 = icmp sle i32 %ret, 9 + %cmp-lte-3 = icmp sle i32 %ret, 8 + %cmp-lte-4 = icmp sle i32 %ret, 1 + %cmp-lte-5 = icmp sle i32 %ret, 0 + %cmp-lte-6 = icmp sle i32 %ret, -1 + tail call void @use3(i1 %cmp-lte-1, i1 %cmp-lte-2, i1 %cmp-lte-3) + tail call void @use3(i1 %cmp-lte-4, i1 %cmp-lte-5, i1 %cmp-lte-6) + + ret void +} +define i32 @test1(i32* %p) { +; CHECK-LABEL: define {{[^@]+}}@test1 +; CHECK-SAME: (i32* nocapture nofree nonnull readonly dereferenceable(4) [[P:%.*]]) +; CHECK-NEXT: [[LOAD_10_100:%.*]] = load i32, i32* [[P]], !range !1 +; CHECK-NEXT: [[ADD_10_THEN_20_110:%.*]] = add i32 [[LOAD_10_100]], 10 +; CHECK-NEXT: [[MUL_10_THEN_200_1091:%.*]] = mul i32 [[ADD_10_THEN_20_110]], 10 +; CHECK-NEXT: ret i32 [[MUL_10_THEN_200_1091]] +; + %load-10-100 = load i32, i32* %p, !range !1 + %add-10-then-20-110 = add i32 %load-10-100, 10 + %mul-10-then-200-1091 = mul i32 %add-10-then-20-110, 10 + ret i32 %mul-10-then-200-1091 +} + +define i1 @test1-check(i32* %p) { +; CHECK-LABEL: define {{[^@]+}}@test1-check +; CHECK-SAME: (i32* nocapture nofree readonly [[P:%.*]]) +; CHECK-NEXT: [[RES:%.*]] = tail call i32 @test1(i32* nocapture nofree readonly [[P]]) +; CHECK-SANME: !range !2 +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[RES]], 500 +; CHECK-NEXT: ret i1 [[CMP]] +; + %res = tail call i32 @test1(i32* %p) + %cmp = icmp eq i32 %res, 500 + ret i1 %cmp +} + +; TEST2 +; int test2(int *p) { return *p == 0 ? 4 : 3; } +; int test2_check(int *p) { +; int call = test2(p); +; if (call == 5) { +; // dead block +; return 2; +; } else { +; return 3; +; } +; } + +define i32 @test2(i32* %p) { +; CHECK-LABEL: define {{[^@]+}}@test2 +; CHECK-SAME: (i32* nocapture nofree nonnull readonly align 4 dereferenceable(4) [[P:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = load i32, i32* [[P]], align 4 +; CHECK-NEXT: [[TOBOOL:%.*]] = icmp eq i32 [[TMP0]], 0 +; CHECK-NEXT: [[COND:%.*]] = select i1 [[TOBOOL]], i32 4, i32 3 +; CHECK-NEXT: ret i32 [[COND]] +; +entry: + %0 = load i32, i32* %p, align 4 + %tobool = icmp eq i32 %0, 0 + %cond = select i1 %tobool, i32 4, i32 3 + ret i32 %cond +} + +define i32 @test2_check(i32* %p) { +; CHECK-LABEL: define {{[^@]+}}@test2_check +; CHECK-SAME: (i32* nocapture nofree readonly align 4 [[P:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[IF_THEN:%.*]] +; CHECK: if.then: +; CHECK-NEXT: br label [[RETURN:%.*]] +; CHECK: if.end: +; CHECK-NEXT: unreachable +; CHECK: return: +; CHECK-NEXT: ret i32 2 +; +entry: + %call = tail call i32 @test2(i32* %p) + %cmp = icmp slt i32 %call, 5 + br i1 %cmp, label %if.then, label %if.end + +if.then: ; preds = %entry + br label %return + +if.end: ; preds = %entry + br label %return + +return: ; preds = %if.end, %if.then + %retval.0 = phi i32 [ 2, %if.then ], [ 3, %if.end ] + ret i32 %retval.0 +} + +; TEST 3 SECV test + +; void unkown(); +; int r1(unsigned int u){ +; int sum = 0; +; for(int i = 0; i<100;i++){ +; sum += i; +; } +; // sum = 50 * 49 / 2 +; if(sum > 10000){ +; // dead block +; return 20; +; }else { +; return 10; +; } +; } +; void f1(int u){ +; if(r1(u) > 15){ +; // deadblock +; unkown(); +; }else { +; return; +; } +; } + +declare dso_local void @unkown() + +define internal i32 @r1(i32) local_unnamed_addr { +; CHECK-LABEL: define {{[^@]+}}@r1() local_unnamed_addr +; CHECK-NEXT: br label [[TMP3:%.*]] +; CHECK: 1: +; CHECK-NEXT: br label [[F:%.*]] +; CHECK: 2: +; CHECK-NEXT: unreachable +; CHECK: f: +; CHECK-NEXT: ret i32 10 +; CHECK: 3: +; CHECK-NEXT: [[TMP4:%.*]] = phi i32 [ 0, [[TMP0:%.*]] ], [ [[TMP7:%.*]], [[TMP3]] ] +; CHECK-NEXT: [[TMP5:%.*]] = phi i32 [ 0, [[TMP0]] ], [ [[TMP6:%.*]], [[TMP3]] ] +; CHECK-NEXT: [[TMP6]] = add nuw nsw i32 [[TMP4]], [[TMP5]] +; CHECK-NEXT: [[TMP7]] = add nuw nsw i32 [[TMP4]], 1 +; CHECK-NEXT: [[TMP8:%.*]] = icmp eq i32 [[TMP7]], 100 +; CHECK-NEXT: br i1 [[TMP8]], label [[TMP1:%.*]], label [[TMP3]] +; + br label %5 + +2: ; preds = %5 + %3 = icmp sgt i32 %8, 10000 + br i1 %3, label %4, label %f +4: + ret i32 20 +f: + ret i32 10 +5: ; preds = %5, %1 + %6 = phi i32 [ 0, %1 ], [ %9, %5 ] + %7 = phi i32 [ 0, %1 ], [ %8, %5 ] + %8 = add nuw nsw i32 %6, %7 + %9 = add nuw nsw i32 %6, 1 + %10 = icmp eq i32 %9, 100 + br i1 %10, label %2, label %5 +} + +define void @f1(i32){ +; CHECK-LABEL: define {{[^@]+}}@f1 +; CHECK-SAME: (i32 [[TMP0:%.*]]) +; CHECK-NEXT: [[TMP2:%.*]] = tail call i32 @r1() +; CHECK-NEXT: br label [[TMP4:%.*]] +; CHECK: 3: +; CHECK-NEXT: unreachable +; CHECK: 4: +; CHECK-NEXT: ret void +; + %2 = tail call i32 @r1(i32 %0) + %3 = icmp sgt i32 %2, 15 + br i1 %3, label %4, label %5 + +4: ; preds = %1 + tail call void @unkown() + br label %5 + +5: ; preds = %1, %4 + ret void +} + +; TEST4 LVI test + +; f1 +; int test4-f1(int u){ +; if(u>=0) { +; return u; +; }else{ +; return 0; +; } +; } +define dso_local i32 @test4-f1(i32 %u) { +; CHECK-LABEL: define {{[^@]+}}@test4-f1 +; CHECK-SAME: (i32 [[U:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i32 [[U]], -1 +; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN:%.*]], label [[RETURN:%.*]] +; CHECK: if.then: +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ [[U]], [[IF_THEN]] ], [ 0, [[ENTRY:%.*]] ] +; CHECK-NEXT: ret i32 [[RETVAL_0]] +; +; FIXME: RETVAL_0 >= 0 +entry: + %cmp = icmp sgt i32 %u, -1 + br i1 %cmp, label %if.then, label %return + +if.then: ; preds = %entry + br label %return + +return: ; preds = %entry, %if.then + %retval.0 = phi i32 [ %u, %if.then ], [ 0, %entry ] + ret i32 %retval.0 +} + + +define dso_local i32 @test4-g1(i32 %u) { +; CHECK-LABEL: define {{[^@]+}}@test4-g1 +; CHECK-SAME: (i32 [[U:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CALL:%.*]] = tail call i32 @test4-f1(i32 [[U]]) +; CHECK-NEXT: ret i32 [[CALL]] +; +; FIXME: %call should have range [0, inf] + +entry: + %call = tail call i32 @test4-f1(i32 %u) + ret i32 %call +} + +; f2 +; int test4-f1(int u){ +; if(u>-1) { +; return u+1; +; }else{ +; return 1; +; } +; } +define dso_local i32 @test4-f2(i32 %u) { +; CHECK-LABEL: define {{[^@]+}}@test4-f2 +; CHECK-SAME: (i32 [[U:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP:%.*]] = icmp sgt i32 [[U]], -1 +; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i32 [[U]], 1 +; CHECK-NEXT: br label [[RETURN:%.*]] +; CHECK: if.else: +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ [[ADD]], [[IF_THEN]] ], [ 1, [[IF_ELSE]] ] +; CHECK-NEXT: ret i32 [[RETVAL_0]] +; +entry: + %cmp = icmp sgt i32 %u, -1 + br i1 %cmp, label %if.then, label %if.else + +if.then: ; preds = %entry + %add = add nuw nsw i32 %u, 1 + br label %return + +if.else: ; preds = %entry + br label %return + +return: ; preds = %if.else, %if.then + %retval.0 = phi i32 [ %add, %if.then ], [ 1, %if.else ] + ret i32 %retval.0 +} + + +define dso_local i32 @test4-g2(i32 %u) { +; CHECK-LABEL: define {{[^@]+}}@test4-g2 +; CHECK-SAME: (i32 [[U:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CALL:%.*]] = tail call i32 @test4-f2(i32 [[U]]) +; CHECK-NEXT: ret i32 [[CALL]] +; +; FIXME: %call should have range [1, inf] +entry: + %call = tail call i32 @test4-f2(i32 %u) + ret i32 %call +} + +define dso_local i32 @test-5() { +; CHECK-LABEL: define {{[^@]+}}@test-5() +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @rec(i32 0), !range !3 +; CHECK-NEXT: ret i32 [[CALL]] +; +entry: + %call = call i32 @rec(i32 0) + ret i32 %call +} +define internal i32 @rec(i32 %depth) { +; CHECK-LABEL: define {{[^@]+}}@rec +; CHECK-SAME: (i32 [[DEPTH:%.*]]) +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CALL:%.*]] = call i32 @foo(i32 [[DEPTH]]) +; CHECK-NEXT: [[TOBOOL:%.*]] = icmp ne i32 [[CALL]], 0 +; CHECK-NEXT: br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_END:%.*]] +; CHECK: if.then: +; CHECK-NEXT: br label [[RETURN:%.*]] +; CHECK: if.end: +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[DEPTH]], 10 +; CHECK-NEXT: br i1 [[CMP]], label [[IF_THEN1:%.*]], label [[IF_END3:%.*]] +; CHECK: if.then1: +; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[DEPTH]], 1 +; CHECK-NEXT: [[CALL2:%.*]] = call i32 @rec(i32 [[ADD]]) +; CHECK-NEXT: br label [[IF_END3]] +; CHECK: if.end3: +; CHECK-NEXT: br label [[RETURN]] +; CHECK: return: +; CHECK-NEXT: [[RETVAL_0:%.*]] = phi i32 [ 0, [[IF_THEN]] ], [ 1, [[IF_END3]] ] +; CHECK-NEXT: ret i32 [[RETVAL_0]] +; +entry: + %call = call i32 @foo(i32 %depth) + %tobool = icmp ne i32 %call, 0 + br i1 %tobool, label %if.then, label %if.end + +if.then: ; preds = %entry + br label %return + +if.end: ; preds = %entry + %cmp = icmp slt i32 %depth, 10 + br i1 %cmp, label %if.then1, label %if.end3 + +if.then1: ; preds = %if.end + %add = add nsw i32 %depth, 1 + %call2 = call i32 @rec(i32 %add) + br label %if.end3 + +if.end3: ; preds = %if.then1, %if.end + br label %return + +return: ; preds = %if.end3, %if.then + %retval.0 = phi i32 [ 0, %if.then ], [ 1, %if.end3 ] + ret i32 %retval.0 +} +declare dso_local i32 @foo(i32) + +!0 = !{i32 0, i32 10} +!1 = !{i32 10, i32 100} +;CHECK: !0 = !{i32 0, i32 10} +;CHECK-NEXT: !1 = !{i32 10, i32 100} +;CHECK-NEXT: !2 = !{i32 200, i32 1091} + diff --git a/llvm/test/Transforms/Attributor/value-simplify.ll b/llvm/test/Transforms/Attributor/value-simplify.ll --- a/llvm/test/Transforms/Attributor/value-simplify.ll +++ b/llvm/test/Transforms/Attributor/value-simplify.ll @@ -36,9 +36,6 @@ br i1 %c, label %if.true, label %if.false if.true: %call = tail call i32 @return0() - -; FIXME: %ret0 should be replaced with i32 1. -; CHECK: %ret0 = add i32 0, 1 %ret0 = add i32 %call, 1 br label %end if.false: @@ -46,23 +43,19 @@ br label %end end: -; FIXME: %ret should be replaced with i32 1. ; CHECK: %ret = phi i32 [ %ret0, %if.true ], [ 1, %if.false ] %ret = phi i32 [ %ret0, %if.true ], [ %ret1, %if.false ] -; FIXME: ret i32 1 -; CHECK: ret i32 %ret - ret i32 %ret +; CHECK: ret i32 1 + ret i32 1 } ; CHECK: define i32 @test2_2(i1 %c) define i32 @test2_2(i1 %c) { -; FIXME: %ret should be replaced with i32 1. %ret = tail call i32 @test2_1(i1 %c) -; FIXME: ret i32 1 -; CHECK: ret i32 %ret +; CHECK: ret i32 1 ret i32 %ret } @@ -127,7 +120,7 @@ define i32 @ipccp1(i32 %a) { ; CHECK-LABEL: define {{[^@]+}}@ipccp1 -; CHECK-SAME: (i32 returned [[A:%.*]]) #0 +; CHECK-SAME: (i32 returned [[A:%.*]]) ; CHECK-NEXT: br i1 true, label [[T:%.*]], label [[F:%.*]] ; CHECK: t: ; CHECK-NEXT: ret i32 [[A:%.*]] @@ -144,7 +137,7 @@ define internal i1 @ipccp2i(i1 %a) { ; CHECK-LABEL: define {{[^@]+}}@ipccp2i -; CHECK-SAME: (i1 returned [[A:%.*]]) #0 +; CHECK-SAME: (i1 returned [[A:%.*]]) ; CHECK-NEXT: br label %t ; CHECK: t: ; CHECK-NEXT: ret i1 true @@ -160,8 +153,8 @@ } define i1 @ipccp2() { -; CHECK-LABEL: define {{[^@]+}}@ipccp2() #1 -; CHECK-NEXT: [[R:%.*]] = call i1 @ipccp2i(i1 true) #0 +; CHECK-LABEL: define {{[^@]+}}@ipccp2() +; CHECK-NEXT: [[R:%.*]] = call i1 @ipccp2i(i1 true) ; CHECK-NEXT: ret i1 [[R]] ; %r = call i1 @ipccp2i(i1 true) @@ -170,14 +163,12 @@ define internal i32 @ipccp3i(i32 %a) { ; CHECK-LABEL: define {{[^@]+}}@ipccp3i -; CHECK-SAME: (i32 [[A:%.*]]) #1 -; CHECK-NEXT: [[C:%.*]] = icmp eq i32 [[A:%.*]], 7 -; CHECK-NEXT: br i1 [[C]], label [[T:%.*]], label [[F:%.*]] +; CHECK-SAME: (i32 returned [[A:%.*]]) +; CHECK-NEXT: br label [[T:%.*]] ; CHECK: t: -; CHECK-NEXT: ret i32 [[A]] +; CHECK-NEXT: ret i32 7 ; CHECK: f: -; CHECK-NEXT: [[R:%.*]] = call i32 @ipccp3i(i32 5) #1 -; CHECK-NEXT: ret i32 [[R]] +; CHECK-NEXT: unreachable ; %c = icmp eq i32 %a, 7 br i1 %c, label %t, label %f @@ -189,10 +180,10 @@ } define i32 @ipccp3() { -; CHECK-LABEL: define {{[^@]+}}@ipccp3() #1 -; CHECK-NEXT: [[R:%.*]] = call i32 @ipccp3i(i32 7) #1 +; CHECK-LABEL: define {{[^@]+}}@ipccp3() +; CHECK-NEXT: [[R:%.*]] = call i32 @ipccp3i(i32 7) ; CHECK-NEXT: ret i32 [[R]] -; +; FIXME: R should be replaced with 7 %r = call i32 @ipccp3i(i32 7) ret i32 %r }