Index: llvm/include/llvm/Transforms/IPO/Attributor.h =================================================================== --- llvm/include/llvm/Transforms/IPO/Attributor.h +++ llvm/include/llvm/Transforms/IPO/Attributor.h @@ -97,6 +97,7 @@ #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/SetVector.h" @@ -2955,6 +2956,216 @@ static const char ID; }; +static const APInt EmptyKey = APInt::getAllOnesValue(100); +static const APInt TombstoneKey = APInt::getAllOnesValue(101); + +// Provide DenseMapInfo for APInt. +template <> struct DenseMapInfo : DenseMapInfo { + static inline APInt getEmptyKey() { return EmptyKey; } + static inline APInt getTombstoneKey() { return TombstoneKey; } + static unsigned getHashValue(const APInt &Val) { + return (unsigned)Val.getLimitedValue(); + } + static bool isEqual(const APInt &LHS, const APInt &RHS) { + if (LHS.getBitWidth() != RHS.getBitWidth()) + return false; + return LHS == RHS; + } +}; + +struct PotentialValueSet { + using SetTy = DenseSet; + + PotentialValueSet(bool isFull) : isFull(isFull) {} + + PotentialValueSet(const SetTy &PS) : isFull(false) { Set = PS; } + + bool operator==(const PotentialValueSet &RHS) const { + if (isFull != RHS.isFull) + return false; + return Set == RHS.Set; + } + + void insert(const APInt &C) { + if (isFull) + return; + Set.insert(C); + } + + /// take union with R + void unionWith(const PotentialValueSet &R) { + /// if this is a full set, do nothing + if (isFull) + return; + /// if R is full set, change L to a full set + if (R.isFull) { + isFull = true; + return; + } + for (auto &e : R.Set) { + Set.insert(e); + } + } + + /// take intersection with R + void intersectWith(const PotentialValueSet &R) { + /// if R is a full set, do nothing + if (R.isFull) + return; + /// if this is a full set, change this to R + if (isFull) { + *this = R; + return; + } + SmallVector eraseList; + for (auto &e : Set) { + if (!R.Set.count(e)) + eraseList.push_back(e); + } + for (auto &e : eraseList) { + Set.erase(e); + } + } + + bool isFull; + SetTy Set; +}; + +struct PotentialValuesState : AbstractState { + + using SetTy = DenseSet; + + // first boolean value indicates wheather the set is a full set or not + using StateTy = PotentialValueSet; + + PotentialValuesState() : Known(true), Assumed(false) {} + + PotentialValuesState(const StateTy &PS) : Known(true), Assumed(PS) {} + + /// See AbstractState::isValidState() + /// If the number of potential values become no less than 7, we give up + bool isValidState() const override { + return !Assumed.isFull && Assumed.Set.size() < 7; + } + + /// See AbstractState::isAtFixpoint() + bool isAtFixpoint() const override { return Assumed == Known; } + + ChangeStatus indicateOptimisticFixpoint() override { + Known = Assumed; + return ChangeStatus::UNCHANGED; + } + + ChangeStatus indicatePessimisticFixpoint() override { + Assumed = Known; + return ChangeStatus::CHANGED; + } + + static StateTy getBestState() { return StateTy(/* isFull */ false); } + static StateTy getBestState(PotentialValuesState &PVS) { + return getBestState(); + } + + static StateTy getWorstState() { return StateTy(/* isFull */ true); } + + /// Return the assumed state + StateTy getAssumed() const { return Assumed; } + + /// Return the known state + StateTy getKnown() const { return Known; } + + bool AssumedIsFull() const { return Assumed.isFull; } + + bool KnownIsFull() const { return Known.isFull; } + + SetTy getAssumedSet() const { return Assumed.Set; } + + SetTy getKnownSet() const { return Known.Set; } + + void unionAssumed(const APInt &C) { + Assumed.insert(C); + Assumed.intersectWith(Known); + } + + void unionAssumed(const StateTy &R) { + Assumed.unionWith(R); + Assumed.intersectWith(Known); + } + + void unionAssumed(const PotentialValuesState &PVS) { + unionAssumed(PVS.getAssumed()); + } + + void unionKnown(const StateTy &R) { + Known.unionWith(R); + Assumed.intersectWith(Known); + } + + void unionKnown(const PotentialValuesState &PVS) { + unionKnown(PVS.getKnown()); + } + + void intersectKnown(const StateTy &R) { + Assumed.intersectWith(R); + Known.intersectWith(R); + } + + PotentialValuesState operator^=(const PotentialValuesState &PVS) { + unionAssumed(PVS); + return *this; + } + + PotentialValuesState operator&=(const PotentialValuesState &PVS) { + unionKnown(PVS); + unionAssumed(PVS); + return *this; + } + + StateTy Known, Assumed; +}; + +raw_ostream &operator<<(raw_ostream &OS, const PotentialValuesState &R); + +/// An abstract interface for potential values analysis. +struct AAPotentialValues + : public StateWrapper { + using Base = StateWrapper; + AAPotentialValues(const IRPosition &IRP, Attributor &A) : Base(IRP) {} + + /// See AbstractAttribute::getState(...). + PotentialValuesState &getState() override { return *this; } + const AbstractState &getState() const override { return *this; } + + /// Create an abstract attribute view for the position \p IRP. + static AAPotentialValues &createForPosition(const IRPosition &IRP, + Attributor &A); + + /// virtual PotentialValuesState::SetTy & + /// getAssumedPotentialValues(Attributor &A, + /// const Instruction *CtxI = nullptr) const = 0; + + /// virtual PotentialValuesState::SetTy & + /// getKnownPotentialValues(Attributor &A, + /// const Instruction *CtxI = nullptr) const = 0; + + Optional + getAssumedConstantInt(Attributor &A, + const Instruction *CtxI = nullptr) const { + if (AssumedIsFull()) + return nullptr; + if (getAssumedSet().size() == 1) + return cast( + ConstantInt::get(getAssociatedType(), *(getAssumedSet().begin()))); + if (getAssumedSet().size() == 0) + return llvm::None; + + return nullptr; + } + + /// Unique ID (due to the unique address) + static const char ID; +}; + /// Run options, used by the pass manager. enum AttributorRunOption { NONE = 0, Index: llvm/lib/Transforms/IPO/Attributor.cpp =================================================================== --- llvm/lib/Transforms/IPO/Attributor.cpp +++ llvm/lib/Transforms/IPO/Attributor.cpp @@ -2000,6 +2000,24 @@ return OS; } +raw_ostream &llvm::operator<<(raw_ostream &OS, const PotentialValuesState &S) { + OS << "set-state(< {"; + if (S.KnownIsFull()) + OS << "full-set"; + else + for (auto &it : S.getKnownSet()) + OS << it << ", "; + OS << "} / {"; + if (S.AssumedIsFull()) + OS << "full-set"; + else + for (auto &it : S.getAssumedSet()) + OS << it << ", "; + OS << "} >)"; + + return OS; +} + void AbstractAttribute::print(raw_ostream &OS) const { OS << "[P: " << getIRPosition() << "][" << getAsStr() << "][S: " << getState() << "]"; Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp =================================================================== --- llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -116,6 +116,7 @@ PIPE_OPERATOR(AAValueConstantRange) PIPE_OPERATOR(AAPrivatizablePtr) PIPE_OPERATOR(AAUndefinedBehavior) +PIPE_OPERATOR(AAPotentialValues) #undef PIPE_OPERATOR } // namespace llvm @@ -1051,9 +1052,10 @@ // map, NewRVsMap. decltype(ReturnedValues) NewRVsMap; - auto HandleReturnValue = [&](Value *RV, SmallSetVector &RIs) { - LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV - << " by #" << RIs.size() << " RIs\n"); + auto HandleReturnValue = [&](Value *RV, + SmallSetVector &RIs) { + LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned value: " << *RV << " by #" + << RIs.size() << " RIs\n"); CallBase *CB = dyn_cast(RV); if (!CB || UnresolvedCalls.count(CB)) return; @@ -3424,7 +3426,6 @@ T.GlobalState &= DS.GlobalState; } - // 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. @@ -4385,6 +4386,40 @@ return true; } + bool askSimplifiedValueForAAPotentialValues(Attributor &A) { + if (!getAssociatedType()->isIntegerTy()) + return false; + + const auto &PotentialValuesAA = + A.getAAFor(*this, getIRPosition()); + + LLVM_DEBUG(dbgs() << "[askAAPotentialValues] " + << PotentialValuesAA.getAsStr() << "\n" + << getAssociatedValue() << "\n"); + + Optional COpt = PotentialValuesAA.getAssumedConstantInt(A); + + if (COpt.hasValue()) { + if (COpt.getValue()) + LLVM_DEBUG(dbgs() << "simplified value : " + << COpt.getValue()->getValue() << "\n"); + else + LLVM_DEBUG(dbgs() << "nullptr\n"); + } else { + LLVM_DEBUG(dbgs() << "None\n"); + } + + if (COpt.hasValue()) { + if (auto *C = COpt.getValue()) + SimplifiedAssociatedValue = C; + else + return false; + } else { + SimplifiedAssociatedValue = llvm::None; + } + return true; + } + /// See AbstractAttribute::manifest(...). ChangeStatus manifest(Attributor &A) override { ChangeStatus Changed = ChangeStatus::UNCHANGED; @@ -4465,6 +4500,18 @@ bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); + if (askSimplifiedValueForAAPotentialValues(A)) { + return HasValueBefore == SimplifiedAssociatedValue.hasValue() + ? ChangeStatus::UNCHANGED + : ChangeStatus ::CHANGED; + } + + if (askSimplifiedValueForAAValueConstantRange(A)) { + return HasValueBefore == SimplifiedAssociatedValue.hasValue() + ? ChangeStatus::UNCHANGED + : ChangeStatus ::CHANGED; + } + auto PredForCallSite = [&](AbstractCallSite ACS) { const IRPosition &ACSArgPos = IRPosition::callsite_argument(ACS, getArgNo()); @@ -4489,8 +4536,7 @@ bool AllCallSitesKnown; if (!A.checkForAllCallSites(PredForCallSite, *this, true, AllCallSitesKnown)) - if (!askSimplifiedValueForAAValueConstantRange(A)) - return indicatePessimisticFixpoint(); + return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. return HasValueBefore == SimplifiedAssociatedValue.hasValue() @@ -4510,15 +4556,35 @@ /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { + LLVM_DEBUG(dbgs() << "[ValueSimplifyReturned][updateImpl] " + << getAssociatedValue() << "\n"); bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); + if (askSimplifiedValueForAAPotentialValues(A)) { + return HasValueBefore == SimplifiedAssociatedValue.hasValue() + ? ChangeStatus::UNCHANGED + : ChangeStatus ::CHANGED; + } + + if (askSimplifiedValueForAAValueConstantRange(A)) { + return HasValueBefore == SimplifiedAssociatedValue.hasValue() + ? ChangeStatus::UNCHANGED + : ChangeStatus ::CHANGED; + } + auto PredForReturned = [&](Value &V) { return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue); }; if (!A.checkForAllReturnedValues(PredForReturned, *this)) - if (!askSimplifiedValueForAAValueConstantRange(A)) - return indicatePessimisticFixpoint(); + return indicatePessimisticFixpoint(); + + LLVM_DEBUG(dbgs() << "HasVsalueBefore : " << HasValueBefore << "\n"); + LLVM_DEBUG(dbgs() << "new : " << SimplifiedAssociatedValue.hasValue() + << "\n"); + if (SimplifiedAssociatedValue.hasValue()) { + LLVM_DEBUG(dbgs() << *(SimplifiedAssociatedValue.getValue()) << "\n"); + } // If a candicate was found in this update, return CHANGED. return HasValueBefore == SimplifiedAssociatedValue.hasValue() @@ -4588,8 +4654,22 @@ /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A) override { + LLVM_DEBUG(dbgs() << "[ValueSimplifyFloating] " << getAssociatedValue() + << " \n"); bool HasValueBefore = SimplifiedAssociatedValue.hasValue(); + if (askSimplifiedValueForAAPotentialValues(A)) { + return HasValueBefore == SimplifiedAssociatedValue.hasValue() + ? ChangeStatus::UNCHANGED + : ChangeStatus ::CHANGED; + } + + if (askSimplifiedValueForAAValueConstantRange(A)) { + return HasValueBefore == SimplifiedAssociatedValue.hasValue() + ? ChangeStatus::UNCHANGED + : ChangeStatus ::CHANGED; + } + auto VisitValueCB = [&](Value &V, const Instruction *CtxI, bool &, bool Stripped) -> bool { auto &AA = A.getAAFor(*this, IRPosition::value(V)); @@ -4607,8 +4687,11 @@ if (!genericValueTraversal( A, getIRPosition(), *this, Dummy, VisitValueCB, getCtxI(), /* UseValueSimplify */ false)) - if (!askSimplifiedValueForAAValueConstantRange(A)) - return indicatePessimisticFixpoint(); + return indicatePessimisticFixpoint(); + + if (SimplifiedAssociatedValue.hasValue()) + LLVM_DEBUG(dbgs() << "candidate : " + << *(SimplifiedAssociatedValue.getValue()) << "\n"); // If a candicate was found in this update, return CHANGED. @@ -7048,6 +7131,438 @@ STATS_DECLTRACK_CSARG_ATTR(value_range) } }; + +/// ------------------ Potential Values Attribute ------------------------- + +struct AAPotentialValuesImpl : AAPotentialValues { + using StateType = PotentialValuesState; + + AAPotentialValuesImpl(const IRPosition &IRP, Attributor &A) + : AAPotentialValues(IRP, A) {} + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr() const override { + std::string Str; + llvm::raw_string_ostream OS(Str); + OS << "set-state < {"; + if (getKnown().isFull) { + OS << "full-set"; + } else { + for (auto &it : getKnown().Set) { + OS << it << " , "; + } + } + OS << "} / {"; + if (getAssumed().isFull) { + OS << "full-set"; + } else { + for (auto &it : getAssumed().Set) { + OS << it << " , "; + } + } + OS << "} >"; + return OS.str(); + } + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + LLVM_DEBUG(dbgs() << "[AAPotentialValues] initialize " + << getAssociatedValue() << "\n"); + } + + static bool calcICmpInst(const ICmpInst *ICI, APInt &LHS, APInt &RHS) { + ICmpInst::Predicate Pred = ICI->getPredicate(); + switch (Pred) { + case ICmpInst::ICMP_UGT: + return LHS.ugt(RHS); + case ICmpInst::ICMP_SGT: + return LHS.sgt(RHS); + case ICmpInst::ICMP_EQ: + return LHS.eq(RHS); + case ICmpInst::ICMP_UGE: + return LHS.uge(RHS); + case ICmpInst::ICMP_SGE: + return LHS.sge(RHS); + case ICmpInst::ICMP_ULT: + return LHS.ult(RHS); + case ICmpInst::ICMP_SLT: + return LHS.slt(RHS); + case ICmpInst::ICMP_NE: + return LHS.ne(RHS); + case ICmpInst::ICMP_ULE: + return LHS.ule(RHS); + case ICmpInst::ICMP_SLE: + return LHS.sle(RHS); + default: + llvm_unreachable("Invalid ICmp predicate!"); + } + } + + static APInt calcCastInst(const CastInst *CI, APInt &Src, + uint32_t ResultBitWidth) { + Instruction::CastOps CastOp = CI->getOpcode(); + switch (CastOp) { + default: + llvm_unreachable("unsupported or not integer cast"); + case Instruction::Trunc: + return Src.trunc(ResultBitWidth); + case Instruction::SExt: + return Src.sext(ResultBitWidth); + case Instruction::ZExt: + return Src.zext(ResultBitWidth); + case Instruction::BitCast: + return Src; + } + } + + static APInt calculateBinaryOperator(const BinaryOperator *BinOp, + const APInt &LHS, const APInt &RHS, + bool &ValidOperator) { + Instruction::BinaryOps BinOpcode = BinOp->getOpcode(); + ValidOperator = true; + APInt LHSCopy = LHS; + switch (BinOpcode) { + default: + ValidOperator = false; + return LHS; + case Instruction::Add: + return (LHSCopy += RHS); + case Instruction::Sub: + return (LHSCopy -= RHS); + case Instruction::Mul: + return LHS * RHS; + case Instruction::UDiv: + return LHS.udiv(RHS); + case Instruction::SDiv: + return LHS.sdiv(RHS); + case Instruction::URem: + return LHS.urem(RHS); + case Instruction::SRem: + return LHS.srem(RHS); + case Instruction::Shl: + return LHS.shl(RHS); + case Instruction::LShr: + return LHS.lshr(RHS); + case Instruction::AShr: + return LHS.ashr(RHS); + case Instruction::And: + return (LHSCopy &= RHS); + case Instruction::Or: + return (LHSCopy |= RHS); + case Instruction::Xor: + return (LHSCopy ^= RHS); + } + } +}; + +struct AAPotentialValuesArgument final + : AAArgumentFromCallSiteArguments { + using Base = + AAArgumentFromCallSiteArguments; + AAPotentialValuesArgument(const IRPosition &IRP, Attributor &A) + : Base(IRP, A) {} + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + LLVM_DEBUG(dbgs() << "[AAPotentialValuesArgument] initialize " + << getAssociatedValue() << "\n"); + if (!getAnchorScope() || getAnchorScope()->isDeclaration()) { + indicatePessimisticFixpoint(); + } else { + Base::initialize(A); + } + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_ARG_ATTR(potential_values) + } +}; + +struct AAPotentialValuesReturned + : AAReturnedFromReturnedValues { + using Base = + AAReturnedFromReturnedValues; + AAPotentialValuesReturned(const IRPosition &IRP, Attributor &A) + : Base(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + LLVM_DEBUG(dbgs() << "\n\n[AAPotentialValuesReturned] initialize " + << getAssociatedValue() << "\n"); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FNRET_ATTR(potential_values) + } +}; + +struct AAPotentialValuesFloating : AAPotentialValuesImpl { + AAPotentialValuesFloating(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + LLVM_DEBUG(dbgs() << "[AAPotentialValuesFloating] initialize \n"); + Value &V = getAssociatedValue(); + + if (auto *C = dyn_cast(&V)) { + LLVM_DEBUG(dbgs() << "ConstantInt" << C->getValue() + << ", indicate optimistic fix point\n"); + unionAssumed(C->getValue()); + indicateOptimisticFixpoint(); + return; + } + + if (isa(&V)) { + LLVM_DEBUG(dbgs() << "UndefValue, optimistic\n"); + indicateOptimisticFixpoint(); + return; + } + + if (isa(&V) || isa(&V) || isa(&V)) { + LLVM_DEBUG(dbgs() << "BinaryOperator or ICmpInst or CastInst\n"); + return; + } + + if (isa(V) || isa(V)) { + LLVM_DEBUG(dbgs() << "SelectInst or PHINode\n"); + return; + } + + indicatePessimisticFixpoint(); + + LLVM_DEBUG(dbgs() << "[AAPotentialValues] We give up: " + << getAssociatedValue() << "\n"); + } + + ChangeStatus updateImpl(Attributor &A) override { + + LLVM_DEBUG(dbgs() << "\n\n[AAPotentialValuesFloating] updateImpl " + << getAssociatedValue() << "\n"); + + Value &V = getAssociatedValue(); + Instruction *I = dyn_cast(&V); + auto AssumedBefore = getAssumed(); + + if (auto *ICI = dyn_cast(I)) { + LLVM_DEBUG(dbgs() << "update with ICmpInst\n"); + Value *LHS = ICI->getOperand(0); + Value *RHS = ICI->getOperand(1); + // TODO: Allow non integers as well. + if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) + return indicatePessimisticFixpoint(); + + auto &LHSAA = + A.getAAFor(*this, IRPosition::value(*LHS)); + auto &RHSAA = + A.getAAFor(*this, IRPosition::value(*RHS)); + + if (LHSAA.AssumedIsFull() || RHSAA.AssumedIsFull()) { + return indicatePessimisticFixpoint(); + } + + auto LHSAAPVS = LHSAA.getAssumedSet(); + auto RHSAAPVS = RHSAA.getAssumedSet(); + + bool MaybeTrue = false, MaybeFalse = false; + for (auto &L : LHSAAPVS) { + for (auto &R : RHSAAPVS) { + LLVM_DEBUG(dbgs() << "calc cmp" << L.toString(10, true) << " " + << R.toString(10, true) << "\n"); + bool CmpResult = calcICmpInst(ICI, L, R); + MaybeTrue |= CmpResult; + MaybeFalse |= !CmpResult; + } + } + if (MaybeTrue) + unionAssumed(APInt(/* numBits */ 1, /* val */ 1)); + if (MaybeFalse) + unionAssumed(APInt(/* numBits */ 1, /* val */ 0)); + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + if (auto *SI = dyn_cast(I)) { + LLVM_DEBUG(dbgs() << "update with SelectInst\n"); + Value *LHS = SI->getTrueValue(); + Value *RHS = SI->getFalseValue(); + if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) + return indicatePessimisticFixpoint(); + + // TODO: consider simplified condition value + auto &LHSAA = + A.getAAFor(*this, IRPosition::value(*LHS)); + auto &RHSAA = + A.getAAFor(*this, IRPosition::value(*RHS)); + + if (LHSAA.AssumedIsFull() || RHSAA.AssumedIsFull()) + return indicatePessimisticFixpoint(); + + LLVM_DEBUG(dbgs() << "union true value and false value\n"); + unionAssumed(LHSAA); + unionAssumed(RHSAA); + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + if (auto *CI = dyn_cast(I)) { + LLVM_DEBUG(dbgs() << "update with CastInst\n"); + if (!CI->isIntegerCast()) + return indicatePessimisticFixpoint(); + assert(CI->getNumOperands() == 1 && "Expected cast to be unary!"); + uint32_t ResultBitWidth = CI->getDestTy()->getIntegerBitWidth(); + Value *Src = CI->getOperand(0); + auto &SrcAA = + A.getAAFor(*this, IRPosition::value(*Src)); + if (SrcAA.AssumedIsFull()) + return indicatePessimisticFixpoint(); + auto SrcAAPVS = SrcAA.getAssumedSet(); + for (APInt &S : SrcAAPVS) { + APInt T = calcCastInst(CI, S, ResultBitWidth); + unionAssumed(T); + } + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + // TODO: Binary Operator + if (auto *BinOp = dyn_cast(I)) { + LLVM_DEBUG(dbgs() << "update with BinaryOperator\n"); + Value *LHS = BinOp->getOperand(0); + Value *RHS = BinOp->getOperand(1); + // TODO: Allow non integers as well. + if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy()) + return indicatePessimisticFixpoint(); + + auto &LHSAA = + A.getAAFor(*this, IRPosition::value(*LHS)); + auto &RHSAA = + A.getAAFor(*this, IRPosition::value(*RHS)); + + if (LHSAA.AssumedIsFull() || RHSAA.AssumedIsFull()) { + return indicatePessimisticFixpoint(); + } + + auto LHSAAPVS = LHSAA.getAssumedSet(); + auto RHSAAPVS = RHSAA.getAssumedSet(); + + for (auto &L : LHSAAPVS) { + for (auto &R : RHSAAPVS) { + LLVM_DEBUG(dbgs() + << "calculate binary operator" << L.toString(10, true) + << " " << R.toString(10, true) << "\n"); + bool ValidOperator = true; + APInt Result = calculateBinaryOperator(BinOp, L, R, ValidOperator); + if (!ValidOperator) + return indicatePessimisticFixpoint(); + unionAssumed(Result); + } + } + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + LLVM_DEBUG( + dbgs() << "[AAPotentialValuesFloating::updateImpl] We give up\n"); + return indicatePessimisticFixpoint(); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FLOATING_ATTR(potential_values) + } +}; + +struct AAPotentialValuesFunction : AAPotentialValuesImpl { + AAPotentialValuesFunction(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + ChangeStatus updateImpl(Attributor &A) override { + llvm_unreachable("AAPotentialValues(Function|CallSite)::updateImpl will " + "not be called"); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_FN_ATTR(potential_values) + } +}; + +struct AAPotentialValuesCallSite : AAPotentialValuesFunction { + AAPotentialValuesCallSite(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesFunction(IRP, A) {} + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CS_ATTR(potential_values) + } +}; + +struct AAPotentialValuesCallSiteReturned + : AACallSiteReturnedFromReturned { + AAPotentialValuesCallSiteReturned(const IRPosition &IRP, Attributor &A) + : AACallSiteReturnedFromReturned(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + LLVM_DEBUG(dbgs() << "[AAPotentialValuesCSReturned] initialize called: " + << getAssociatedValue() << "\n"); + AAPotentialValuesImpl::initialize(A); + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSRET_ATTR(potential_values) + } +}; + +struct AAPotentialValuesCallSiteArgument : AAPotentialValuesImpl { + AAPotentialValuesCallSiteArgument(const IRPosition &IRP, Attributor &A) + : AAPotentialValuesImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + LLVM_DEBUG(dbgs() << "[AAPotentialValuesCSArgument] initialize called: " + << getAssociatedValue() << "\n"); + Value &V = getAssociatedValue(); + + if (auto *C = dyn_cast(&V)) { + LLVM_DEBUG(dbgs() << "ConstantInt " << C->getValue() + << ", indicate optimistic fix point\n"); + unionAssumed(C->getValue()); + indicateOptimisticFixpoint(); + return; + } + + if (isa(&V)) { + LLVM_DEBUG(dbgs() << "UndefValue, optimistic\n"); + indicateOptimisticFixpoint(); + return; + } + } + + ChangeStatus updateImpl(Attributor &A) override { + Value &V = getAssociatedValue(); + auto AssumedBefore = getAssumed(); + auto &AA = A.getAAFor(*this, IRPosition::value(V)); + const auto &S = AA.getAssumed(); + unionAssumed(S); + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + /// See AbstractAttribute::trackStatistics() + void trackStatistics() const override { + STATS_DECLTRACK_CSARG_ATTR(potential_values) + } +}; + } // namespace const char AAReturnedValues::ID = 0; @@ -7071,6 +7586,7 @@ const char AAMemoryBehavior::ID = 0; const char AAMemoryLocation::ID = 0; const char AAValueConstantRange::ID = 0; +const char AAPotentialValues::ID = 0; // Macro magic to create the static generator function for attributes that // follow the naming scheme. @@ -7180,6 +7696,7 @@ CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAlign) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoCapture) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueConstantRange) +CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAPotentialValues) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) Index: llvm/test/Transforms/Attributor/potential.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/Attributor/potential.ll @@ -0,0 +1,282 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=9 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM +; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=9 -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_CGSCC_OPM,NOT_CGSCC_NPM,NOT_TUNIT_OPM,IS__TUNIT____,IS________NPM,IS__TUNIT_NPM +; RUN: opt -attributor-cgscc -attributor-manifest-internal -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_NPM,IS__CGSCC____,IS________OPM,IS__CGSCC_OPM +; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,NOT_TUNIT_NPM,NOT_TUNIT_OPM,NOT_CGSCC_OPM,IS__CGSCC____,IS________NPM,IS__CGSCC_NPM +; +; Test for multiple potential values +; +; potential-test 1 +; bool iszero(int c) { return c == 0; } +; bool potential_test1(bool c) { return iszero(c ? 1 : -1); } + +define internal i1 @iszero1(i32 %c) { +; IS__CGSCC____-LABEL: @iszero1( +; IS__CGSCC____-NEXT: [[CMP:%.*]] = icmp eq i32 [[C:%.*]], 0 +; IS__CGSCC____-NEXT: ret i1 [[CMP]] +; + %cmp = icmp eq i32 %c, 0 + ret i1 %cmp +} + +define i1 @potential_test1(i1 %c) { +; IS__TUNIT____-LABEL: @potential_test1( +; IS__TUNIT____-NEXT: ret i1 false +; +; IS__CGSCC____-LABEL: @potential_test1( +; IS__CGSCC____-NEXT: [[ARG:%.*]] = select i1 [[C:%.*]], i32 -1, i32 1 +; IS__CGSCC____-NEXT: [[RET:%.*]] = tail call i1 @iszero1(i32 [[ARG]]) #1 +; IS__CGSCC____-NEXT: ret i1 [[RET]] +; + %arg = select i1 %c, i32 -1, i32 1 + %ret = tail call i1 @iszero1(i32 %arg) + ret i1 %ret +} + + +; potential-test 2 + +define internal i32 @iszero2(i32 %c) { +; IS__CGSCC____-LABEL: @iszero2( +; IS__CGSCC____-NEXT: [[CMP:%.*]] = icmp eq i32 [[C:%.*]], 0 +; IS__CGSCC____-NEXT: [[RET:%.*]] = zext i1 [[CMP]] to i32 +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = zext i1 %cmp to i32 + ret i32 %ret +} + +define internal i32 @call_with_two_values(i32 %c) { +; IS__CGSCC____-LABEL: @call_with_two_values( +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @iszero2(i32 [[C:%.*]]) #1 +; IS__CGSCC____-NEXT: [[MINUSC:%.*]] = sub nsw i32 0, [[C]] +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @iszero2(i32 [[MINUSC]]) #1 +; IS__CGSCC____-NEXT: [[RET:%.*]] = add i32 [[CSRET1]], [[CSRET2]] +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret1 = call i32 @iszero2(i32 %c) + %minusc = sub nsw i32 0, %c + %csret2 = call i32 @iszero2(i32 %minusc) + %ret = add i32 %csret1, %csret2 + ret i32 %ret +} + +define i32 @potential_test2(i1 %c) { +; IS__TUNIT____-LABEL: @potential_test2( +; IS__TUNIT____-NEXT: ret i32 0 +; +; IS__CGSCC____-LABEL: @potential_test2( +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @call_with_two_values(i32 1) #1 +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @call_with_two_values(i32 -1) #1 +; IS__CGSCC____-NEXT: [[RET:%.*]] = select i1 [[C:%.*]], i32 [[CSRET1]], i32 [[CSRET2]] +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret1 = call i32 @call_with_two_values(i32 1) + %csret2 = call i32 @call_with_two_values(i32 -1) + %ret = select i1 %c, i32 %csret1, i32 %csret2 + ret i32 %ret +} + +; potential-test 3 +; +; int less_than_two(int c) { return c < 2; } +; int potential_test3() { return less_than_two(iszero(0))+less_than_two(iszero(1)); } + +define internal i32 @iszero3(i32 %c) { +; IS__CGSCC____-LABEL: @iszero3( +; IS__CGSCC____-NEXT: [[CMP:%.*]] = icmp eq i32 [[C:%.*]], 0 +; IS__CGSCC____-NEXT: [[RET:%.*]] = zext i1 [[CMP]] to i32 +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = zext i1 %cmp to i32 + ret i32 %ret +} + +define internal i32 @less_than_two(i32 %c) { +; IS__CGSCC____-LABEL: @less_than_two( +; IS__CGSCC____-NEXT: [[CMP:%.*]] = icmp slt i32 [[C:%.*]], 2 +; IS__CGSCC____-NEXT: [[RET:%.*]] = zext i1 [[CMP]] to i32 +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %cmp = icmp slt i32 %c, 2 + %ret = zext i1 %cmp to i32 + ret i32 %ret +} + +define i32 @potential_test3() { +; IS__TUNIT____-LABEL: @potential_test3( +; IS__TUNIT____-NEXT: ret i32 2 +; +; IS__CGSCC____-LABEL: @potential_test3( +; IS__CGSCC____-NEXT: [[CMP1:%.*]] = call i32 @iszero3(i32 0) #1 +; IS__CGSCC____-NEXT: [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]]) #1 +; IS__CGSCC____-NEXT: [[CMP2:%.*]] = call i32 @iszero3(i32 1) #1 +; IS__CGSCC____-NEXT: [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]]) #1 +; IS__CGSCC____-NEXT: [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]] +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %cmp1 = call i32 @iszero3(i32 0) + %true1 = call i32 @less_than_two(i32 %cmp1) + %cmp2 = call i32 @iszero3(i32 1) + %true2 = call i32 @less_than_two(i32 %cmp2) + %ret = add i32 %true1, %true2 + ret i32 %ret +} + + + +; potential-test 4,5,6,7 +; +; simplified +; int potential_test4(int c) { return return1or3(c) == 2; } +; int potential_test5(int c) { return return1or3(c) == return2or4(c); } +; +; not simplified +; int potential_test6(int c) { return return1or3(c) == 3; } +; int potential_test7(int c) { return return1or3(c) == return3or4(c); } + +define i32 @potential_test4(i32 %c) { +; IS__TUNIT____-LABEL: @potential_test4( +; IS__TUNIT____-NEXT: ret i32 0 +; +; IS__CGSCC____-LABEL: @potential_test4( +; IS__CGSCC____-NEXT: [[CSRET:%.*]] = call i32 @return1or3(i32 [[C:%.*]]) #1 +; IS__CGSCC____-NEXT: [[FALSE:%.*]] = icmp eq i32 [[CSRET]], 2 +; IS__CGSCC____-NEXT: [[RET:%.*]] = zext i1 [[FALSE]] to i32 +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret = call i32 @return1or3(i32 %c) + %false = icmp eq i32 %csret, 2 + %ret = zext i1 %false to i32 + ret i32 %ret +} + +define i32 @potential_test5(i32 %c) { +; IS__TUNIT____-LABEL: @potential_test5( +; IS__TUNIT____-NEXT: ret i32 0 +; +; IS__CGSCC____-LABEL: @potential_test5( +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C:%.*]]) #1 +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @return2or4(i32 [[C]]) #1 +; IS__CGSCC____-NEXT: [[FALSE:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]] +; IS__CGSCC____-NEXT: [[RET:%.*]] = zext i1 [[FALSE]] to i32 +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret1 = call i32 @return1or3(i32 %c) + %csret2 = call i32 @return2or4(i32 %c) + %false = icmp eq i32 %csret1, %csret2 + %ret = zext i1 %false to i32 + ret i32 %ret +} + +define i1 @potential_test6(i32 %c) { +; IS__TUNIT____-LABEL: @potential_test6( +; IS__TUNIT____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C:%.*]]) #0, !range !0 +; IS__TUNIT____-NEXT: [[RET:%.*]] = icmp eq i32 [[CSRET1]], 3 +; IS__TUNIT____-NEXT: ret i1 [[RET]] +; +; IS__CGSCC____-LABEL: @potential_test6( +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C:%.*]]) #1 +; IS__CGSCC____-NEXT: [[RET:%.*]] = icmp eq i32 [[CSRET1]], 3 +; IS__CGSCC____-NEXT: ret i1 [[RET]] +; + %csret1 = call i32 @return1or3(i32 %c) + %ret = icmp eq i32 %csret1, 3 + ret i1 %ret +} + +define i1 @potential_test7(i32 %c) { +; IS__TUNIT____-LABEL: @potential_test7( +; IS__TUNIT____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C:%.*]]) #0, !range !0 +; IS__TUNIT____-NEXT: [[CSRET2:%.*]] = call i32 @return3or4(i32 [[C]]) #0, !range !1 +; IS__TUNIT____-NEXT: [[RET:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]] +; IS__TUNIT____-NEXT: ret i1 [[RET]] +; +; IS__CGSCC____-LABEL: @potential_test7( +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C:%.*]]) #1 +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @return3or4(i32 [[C]]) #1 +; IS__CGSCC____-NEXT: [[RET:%.*]] = icmp eq i32 [[CSRET1]], [[CSRET2]] +; IS__CGSCC____-NEXT: ret i1 [[RET]] +; + %csret1 = call i32 @return1or3(i32 %c) + %csret2 = call i32 @return3or4(i32 %c) + %ret = icmp eq i32 %csret1, %csret2 + ret i1 %ret +} + +define internal i32 @return1or3(i32 %c) { +; CHECK-LABEL: @return1or3( +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[C:%.*]], 0 +; CHECK-NEXT: [[RET:%.*]] = select i1 [[CMP]], i32 1, i32 3 +; CHECK-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = select i1 %cmp, i32 1, i32 3 + ret i32 %ret +} + +define internal i32 @return2or4(i32 %c) { +; IS__CGSCC____-LABEL: @return2or4( +; IS__CGSCC____-NEXT: [[CMP:%.*]] = icmp eq i32 [[C:%.*]], 0 +; IS__CGSCC____-NEXT: [[RET:%.*]] = select i1 [[CMP]], i32 2, i32 4 +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = select i1 %cmp, i32 2, i32 4 + ret i32 %ret +} + +define internal i32 @return3or4(i32 %c) { +; CHECK-LABEL: @return3or4( +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[C:%.*]], 0 +; CHECK-NEXT: [[RET:%.*]] = select i1 [[CMP]], i32 3, i32 4 +; CHECK-NEXT: ret i32 [[RET]] +; + %cmp = icmp eq i32 %c, 0 + %ret = select i1 %cmp, i32 3, i32 4 + ret i32 %ret +} + +; potential-test 8 +; +; propagate argument to callsite argument + +define internal i1 @cmp_with_four(i32 %c) { +; IS__CGSCC____-LABEL: @cmp_with_four( +; IS__CGSCC____-NEXT: [[CMP:%.*]] = icmp eq i32 [[C:%.*]], 4 +; IS__CGSCC____-NEXT: ret i1 [[CMP]] +; + %cmp = icmp eq i32 %c, 4 + ret i1 %cmp +} + +define internal i1 @wrapper(i32 %c) { +; IS__CGSCC____-LABEL: @wrapper( +; IS__CGSCC____-NEXT: [[RET:%.*]] = call i1 @cmp_with_four(i32 [[C:%.*]]) #1 +; IS__CGSCC____-NEXT: ret i1 [[RET]] +; + %ret = call i1 @cmp_with_four(i32 %c) + ret i1 %ret +} + +define i1 @potential_test8() { +; IS__TUNIT____-LABEL: @potential_test8( +; IS__TUNIT____-NEXT: ret i1 false +; +; IS__CGSCC____-LABEL: @potential_test8( +; IS__CGSCC____-NEXT: [[RES1:%.*]] = call i1 @wrapper(i32 1) #1 +; IS__CGSCC____-NEXT: [[RES3:%.*]] = call i1 @wrapper(i32 3) #1 +; IS__CGSCC____-NEXT: [[RES5:%.*]] = call i1 @wrapper(i32 5) #1 +; IS__CGSCC____-NEXT: [[RES13:%.*]] = or i1 [[RES1]], [[RES3]] +; IS__CGSCC____-NEXT: [[RES135:%.*]] = or i1 [[RES13]], [[RES5]] +; IS__CGSCC____-NEXT: ret i1 [[RES135]] +; + %res1 = call i1 @wrapper(i32 1) + %res3 = call i1 @wrapper(i32 3) + %res5 = call i1 @wrapper(i32 5) + %res13 = or i1 %res1, %res3 + %res135 = or i1 %res13, %res5 + ret i1 %res135 +}