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" @@ -116,6 +117,7 @@ #include "llvm/IR/ConstantRange.h" #include "llvm/IR/PassManager.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Transforms/Utils/CallGraphUpdater.h" namespace llvm { @@ -2974,6 +2976,250 @@ static const char ID; }; +/// Provide DenseMapInfo for APInt. +struct DenseMapAPIntKeyInfo { + static inline APInt getEmptyKey() { + APInt V(nullptr, 0); + V.U.VAL = 0; + return V; + } + + static inline APInt getTombstoneKey() { + APInt V(nullptr, 0); + V.U.VAL = 1; + return V; + } + + static unsigned getHashValue(const APInt &Key) { + return static_cast(hash_value(Key)); + } + + static bool isEqual(const APInt &LHS, const APInt &RHS) { + return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS; + } +}; + +/// A class for a set that the size of it can be infinitely large. +template > +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 MemberTy &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 (const MemberTy &C : R.Set) + Set.insert(C); + } + + /// 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; + } + SetTy intersectSet; + for (const MemberTy &C : Set) { + if (R.Set.count(C)) + intersectSet.insert(C); + } + Set = intersectSet; + } + + /// This indicates whether the corresponding set is full set or not. + /// If this is true, the value of \p Set is meaningless. + bool isFull; + + /// When \p isFull is false, this corresponds to the actual set. + SetTy Set; +}; + +using PotentialConstantIntValueSet = + PotentialValueSet; + +// static cl::opt +// MaxPotentialValues("attributor-max-potential-values", cl::Hidden, +// cl::desc("Maximal number of potential values to be " +// "tracked for each position."), +// cl::init(7)); +static const unsigned MaxPotentialValues = 7; + +/// State for potential values. +struct PotentialValuesState : AbstractState { + + using SetTy = PotentialConstantIntValueSet::SetTy; + + using StateTy = PotentialConstantIntValueSet; + + 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 threshold, we give + /// up. + bool isValidState() const override { + return !Assumed.isFull && Assumed.Set.size() < MaxPotentialValues; + } + + /// See AbstractState::isAtFixpoint() + bool isAtFixpoint() const override { return Assumed == Known; } + + /// See AbstractState::indicateOptimisticFixpoint(...) + ChangeStatus indicateOptimisticFixpoint() override { + Known = Assumed; + return ChangeStatus::UNCHANGED; + } + + /// See AbstractState::indicatePessimisticFixpoint(...) + ChangeStatus indicatePessimisticFixpoint() override { + Assumed = Known; + return ChangeStatus::CHANGED; + } + + /// Return empty set as the best state of potential values. + static StateTy getBestState() { return StateTy(/* isFull */ false); } + static StateTy getBestState(PotentialValuesState &PVS) { + return getBestState(); + } + + /// Return full set as the worst state of potential values. + 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; } + + /// Return the assumed set is full set or not. + bool AssumedIsFull() const { return Assumed.isFull; } + + /// Return the known set is full set or not. + bool KnownIsFull() const { return Known.isFull; } + + /// Return the assumed set. + /// Note: If AssumedIsFull() is true, this is meaningless. + SetTy getAssumedSet() const { return Assumed.Set; } + + /// Return the known set. + /// Note: If KnownIsFull() is true, this is meaningless. + SetTy getKnownSet() const { return Known.Set; } + + /// Unite assumed set with the passed value. + void unionAssumed(const APInt &C) { + Assumed.insert(C); + Assumed.intersectWith(Known); + } + + /// Unite assumed set with the passed state. + void unionAssumed(const StateTy &R) { + Assumed.unionWith(R); + Assumed.intersectWith(Known); + } + + /// Unite assumed set with assumed set of the passed state \p PVS. + void unionAssumed(const PotentialValuesState &PVS) { + unionAssumed(PVS.getAssumed()); + } + + /// Unite known set with the passed state. + void unionKnown(const StateTy &R) { + Known.unionWith(R); + Assumed.intersectWith(Known); + } + + /// Unite known set with known set of the passed state \p PVS. + void unionKnown(const PotentialValuesState &PVS) { + unionKnown(PVS.getKnown()); + } + + /// Intersect known set with the passed state. + void intersectKnown(const StateTy &R) { + Assumed.intersectWith(R); + Known.intersectWith(R); + } + + /// "Clamp" this state with \p PVS. + PotentialValuesState operator^=(const PotentialValuesState &PVS) { + unionAssumed(PVS); + return *this; + } + + PotentialValuesState operator&=(const PotentialValuesState &PVS) { + unionKnown(PVS); + unionAssumed(PVS); + return *this; + } + + /// Set representing known set of potential values. + StateTy Known; + + /// Set representing assumed set of potential values. + StateTy 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 PotentialValuesState &getState() const override { return *this; } + + /// Create an abstract attribute view for the position \p IRP. + static AAPotentialValues &createForPosition(const IRPosition &IRP, + Attributor &A); + + /// Return assumed constant for the associated value + 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 @@ -2007,6 +2007,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 @@ -117,6 +117,7 @@ PIPE_OPERATOR(AAValueConstantRange) PIPE_OPERATOR(AAPrivatizablePtr) PIPE_OPERATOR(AAUndefinedBehavior) +PIPE_OPERATOR(AAPotentialValues) #undef PIPE_OPERATOR } // namespace llvm @@ -4366,24 +4367,37 @@ return true; } - bool askSimplifiedValueForAAValueConstantRange(Attributor &A) { - if (!getAssociatedValue().getType()->isIntegerTy()) - return false; + template + void askSimplifiedValueFor(Attributor &A, bool &failAll, + bool &conflictAssumedConstantInt) { + if (!getAssociatedType()->isIntegerTy()) + return; - const auto &ValueConstantRangeAA = - A.getAAFor(*this, getIRPosition()); + const auto &AA = + A.getAAFor(*this, getIRPosition(), /* TrackDependence */ true, + DepClassTy::OPTIONAL); - Optional COpt = - ValueConstantRangeAA.getAssumedConstantInt(A); - if (COpt.hasValue()) { - if (auto *C = COpt.getValue()) - SimplifiedAssociatedValue = C; - else - return false; - } else { - SimplifiedAssociatedValue = llvm::None; + Optional COpt = AA.getAssumedConstantInt(A); + + if (!COpt.hasValue()) + failAll = false; + else if (auto *C = COpt.getValue()) { + if (SimplifiedAssociatedValue.hasValue()) + conflictAssumedConstantInt |= + (C != SimplifiedAssociatedValue.getValue()); + SimplifiedAssociatedValue = C; + failAll = false; } - return true; + } + + bool askSimplifiedValueForOtherAAs(Attributor &A) { + bool failAll = true; + bool conflictAssumedConstantInt = false; + askSimplifiedValueFor(A, failAll, + conflictAssumedConstantInt); + askSimplifiedValueFor(A, failAll, + conflictAssumedConstantInt); + return !conflictAssumedConstantInt && !failAll; } /// See AbstractAttribute::manifest(...). @@ -4490,7 +4504,7 @@ bool AllCallSitesKnown; if (!A.checkForAllCallSites(PredForCallSite, *this, true, AllCallSitesKnown)) - if (!askSimplifiedValueForAAValueConstantRange(A)) + if (!askSimplifiedValueForOtherAAs(A)) return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. @@ -4518,7 +4532,7 @@ }; if (!A.checkForAllReturnedValues(PredForReturned, *this)) - if (!askSimplifiedValueForAAValueConstantRange(A)) + if (!askSimplifiedValueForOtherAAs(A)) return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. @@ -4608,11 +4622,10 @@ if (!genericValueTraversal( A, getIRPosition(), *this, Dummy, VisitValueCB, getCtxI(), /* UseValueSimplify */ false)) - if (!askSimplifiedValueForAAValueConstantRange(A)) + if (!askSimplifiedValueForOtherAAs(A)) return indicatePessimisticFixpoint(); // If a candicate was found in this update, return CHANGED. - return HasValueBefore == SimplifiedAssociatedValue.hasValue() ? ChangeStatus::UNCHANGED : ChangeStatus ::CHANGED; @@ -4670,6 +4683,29 @@ AAValueSimplifyCallSiteArgument(const IRPosition &IRP, Attributor &A) : AAValueSimplifyFloating(IRP, A) {} + ChangeStatus manifest(Attributor &A) override { + ChangeStatus Changed = ChangeStatus::UNCHANGED; + + if (SimplifiedAssociatedValue.hasValue() && + !SimplifiedAssociatedValue.getValue()) + return Changed; + + Value &V = getAssociatedValue(); + auto *C = SimplifiedAssociatedValue.hasValue() + ? dyn_cast(SimplifiedAssociatedValue.getValue()) + : UndefValue::get(V.getType()); + Use &U = cast(&getAnchorValue())->getArgOperandUse(getArgNo()); + if (C) { + // We can replace the AssociatedValue with the constant. + if (&V != C && V.getType() == C->getType()) { + if (A.changeUseAfterManifest(U, *C)) + Changed = ChangeStatus::CHANGED; + } + } + + return Changed | AAValueSimplify::manifest(A); + } + void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(value_simplify) } @@ -7049,6 +7085,437 @@ 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(); + } +}; + +struct AAPotentialValuesArgument final + : AAArgumentFromCallSiteArguments { + using Base = + AAArgumentFromCallSiteArguments; + AAPotentialValuesArgument(const IRPosition &IRP, Attributor &A) + : Base(IRP, A) {} + + /// See AbstractAttribute::initialize(..). + void initialize(Attributor &A) override { + 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::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 { + Value &V = getAssociatedValue(); + + if (auto *C = dyn_cast(&V)) { + unionAssumed(C->getValue()); + indicateOptimisticFixpoint(); + return; + } + + if (isa(&V)) { + // Collapse the undef state to 0. + unionAssumed( + APInt(/* numBits */ getAssociatedType()->getIntegerBitWidth(), + /* val */ 0)); + indicateOptimisticFixpoint(); + return; + } + + if (isa(&V) || isa(&V) || isa(&V)) + return; + + if (isa(V) || isa(V)) + return; + + indicatePessimisticFixpoint(); + + LLVM_DEBUG(dbgs() << "[AAPotentialValues] We give up: " + << getAssociatedValue() << "\n"); + } + + static bool calculateICmpInst(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 calculateCastInst(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 &Valid) { + Instruction::BinaryOps BinOpcode = BinOp->getOpcode(); + // Valid is set to false when the binary operator is not supported or + // division by zero occur. + Valid = true; + APInt LHSCopy = LHS; + switch (BinOpcode) { + default: + Valid = false; + return LHS; + case Instruction::Add: + return (LHSCopy += RHS); + case Instruction::Sub: + return (LHSCopy -= RHS); + case Instruction::Mul: + return LHS * RHS; + case Instruction::UDiv: + if (RHS.isNullValue()) { + Valid = false; + return LHS; + } + return LHS.udiv(RHS); + case Instruction::SDiv: + if (RHS.isNullValue()) { + Valid = false; + return LHS; + } + return LHS.sdiv(RHS); + case Instruction::URem: + if (RHS.isNullValue()) { + Valid = false; + return LHS; + } + return LHS.urem(RHS); + case Instruction::SRem: + if (RHS.isNullValue()) { + Valid = false; + return LHS; + } + 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); + } + } + + ChangeStatus updateWithICmpInst(Attributor &A, ICmpInst *ICI) { + auto AssumedBefore = getAssumed(); + 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.isValidState() || !RHSAA.isValidState()) + return indicatePessimisticFixpoint(); + + auto LHSAAPVS = LHSAA.getAssumedSet(); + auto RHSAAPVS = RHSAA.getAssumedSet(); + + bool MaybeTrue = false, MaybeFalse = false; + for (auto &L : LHSAAPVS) { + for (auto &R : RHSAAPVS) { + bool CmpResult = calculateICmpInst(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; + } + + ChangeStatus updateWithSelectInst(Attributor &A, SelectInst *SI) { + auto AssumedBefore = getAssumed(); + 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.isValidState() || !RHSAA.isValidState()) + return indicatePessimisticFixpoint(); + + unionAssumed(LHSAA); + unionAssumed(RHSAA); + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + ChangeStatus updateWithCastInst(Attributor &A, CastInst *CI) { + auto AssumedBefore = getAssumed(); + 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.isValidState()) + return indicatePessimisticFixpoint(); + auto SrcAAPVS = SrcAA.getAssumedSet(); + for (APInt &S : SrcAAPVS) { + APInt T = calculateCastInst(CI, S, ResultBitWidth); + unionAssumed(T); + } + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + ChangeStatus updateWithBinaryOperator(Attributor &A, BinaryOperator *BinOp) { + auto AssumedBefore = getAssumed(); + 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.isValidState() || !RHSAA.isValidState()) + return indicatePessimisticFixpoint(); + + auto LHSAAPVS = LHSAA.getAssumedSet(); + auto RHSAAPVS = RHSAA.getAssumedSet(); + + for (auto &L : LHSAAPVS) { + for (auto &R : RHSAAPVS) { + bool Valid = true; + APInt Result = calculateBinaryOperator(BinOp, L, R, Valid); + if (!Valid) + return indicatePessimisticFixpoint(); + unionAssumed(Result); + } + } + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + ChangeStatus updateWithPHINode(Attributor &A, PHINode *PHI) { + auto AssumedBefore = getAssumed(); + for (unsigned u = 0, e = PHI->getNumIncomingValues(); u < e; u++) { + Value *IncomingValue = PHI->getIncomingValue(u); + auto &PotentialValuesAA = A.getAAFor( + *this, IRPosition::value(*IncomingValue)); + if (!PotentialValuesAA.isValidState()) + return indicatePessimisticFixpoint(); + unionAssumed(PotentialValuesAA.getAssumed()); + } + return AssumedBefore == getAssumed() ? ChangeStatus::UNCHANGED + : ChangeStatus::CHANGED; + } + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + Value &V = getAssociatedValue(); + Instruction *I = dyn_cast(&V); + + if (auto *ICI = dyn_cast(I)) + return updateWithICmpInst(A, ICI); + + if (auto *SI = dyn_cast(I)) + return updateWithSelectInst(A, SI); + + if (auto *CI = dyn_cast(I)) + return updateWithCastInst(A, CI); + + if (auto *BinOp = dyn_cast(I)) + return updateWithBinaryOperator(A, BinOp); + + if (auto *PHI = dyn_cast(I)) + return updateWithPHINode(A, PHI); + + 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::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 { + Value &V = getAssociatedValue(); + + if (auto *C = dyn_cast(&V)) { + unionAssumed(C->getValue()); + indicateOptimisticFixpoint(); + return; + } + + if (isa(&V)) { + unionAssumed( + APInt(/* numBits */ getAssociatedType()->getIntegerBitWidth(), + /* val */ 0)); + indicateOptimisticFixpoint(); + return; + } + } + + /// See AbstractAttribute::updateImpl(...). + 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; @@ -7072,6 +7539,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. @@ -7181,6 +7649,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,351 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes +; RUN: opt -attributor -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=20 -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=19 -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: define {{[^@]+}}@iszero1 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; 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: define {{[^@]+}}@potential_test1 +; IS__TUNIT____-SAME: (i1 [[C:%.*]]) +; IS__TUNIT____-NEXT: ret i1 false +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test1 +; IS__CGSCC____-SAME: (i1 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[ARG:%.*]] = select i1 [[C]], i32 -1, i32 1 +; IS__CGSCC____-NEXT: [[RET:%.*]] = tail call i1 @iszero1(i32 [[ARG]]) +; 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 +; +; potential values of argument of iszero are {1,-1} +; potential value of returned value of iszero is 0 +; +; int call_with_two_values(int x) { return iszero(x) + iszero(-x); } +; int potential_test2(int x) { return call_with_two_values(1) + call_with_two_values(-1); } + +define internal i32 @iszero2(i32 %c) { +; IS__CGSCC____-LABEL: define {{[^@]+}}@iszero2 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; 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: define {{[^@]+}}@call_with_two_values +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @iszero2(i32 [[C]]) +; IS__CGSCC____-NEXT: [[MINUSC:%.*]] = sub nsw i32 0, [[C]] +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @iszero2(i32 [[MINUSC]]) +; IS__CGSCC____-NEXT: [[RET:%.*]] = add i32 [[CSRET1]], [[CSRET2]] +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret1 = tail call i32 @call_with_two_values(i32 1) + %csret2 = tail call i32 @call_with_two_values(i32 -1) + %ret = add nsw i32 %csret1, %csret2 + ret i32 %ret +} + +define i32 @potential_test2(i1 %c) { +; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test2 +; IS__TUNIT____-SAME: (i1 [[C:%.*]]) +; IS__TUNIT____-NEXT: ret i32 0 +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test2 +; IS__CGSCC____-SAME: (i1 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @call_with_two_values(i32 1) +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @call_with_two_values(i32 -1) +; IS__CGSCC____-NEXT: [[RET:%.*]] = select i1 [[C]], i32 [[CSRET1]], i32 [[CSRET2]] +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %csret1 = tail call i32 @iszero2(i32 %c) + %minusc = sub nsw i32 0, %c + %csret2 = tail call i32 @iszero2(i32 %minusc) + %ret = add nsw i32 %csret1, %csret2 + ret i32 %ret +} + + +; potential-test 3 +; +; potential values of returned value of f are {0,1} +; potential values of argument of g are {0,1} +; potential value of returned value of g is 1 +; then returned value of g can be simplified +; +; int zero_or_one(int c) { return c < 2; } +; int potential_test3() { return zero_or_one(iszero(0))+zero_or_one(iszero(1)); } + +define internal i32 @iszero3(i32 %c) { +; IS__CGSCC____-LABEL: define {{[^@]+}}@iszero3 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; 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: define {{[^@]+}}@less_than_two +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CMP:%.*]] = icmp slt i32 [[C]], 2 +; IS__CGSCC____-NEXT: [[RET:%.*]] = zext i1 [[CMP]] to i32 +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %cmp1 = tail call i32 @iszero3(i32 0) + %true1 = tail call i32 @zero_or_one(i32 %cmp1) + %cmp2 = tail call i32 @iszero3(i32 1) + %true2 = tail call i32 @zero_or_one(i32 %cmp2) + %ret = add nsw i32 %true1, %true2 + ret i32 %ret +} + +define i32 @potential_test3() { +; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test3() +; IS__TUNIT____-NEXT: ret i32 2 +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test3() +; IS__CGSCC____-NEXT: [[CMP1:%.*]] = call i32 @iszero3(i32 0) +; IS__CGSCC____-NEXT: [[TRUE1:%.*]] = call i32 @less_than_two(i32 [[CMP1]]) +; IS__CGSCC____-NEXT: [[CMP2:%.*]] = call i32 @iszero3(i32 1) +; IS__CGSCC____-NEXT: [[TRUE2:%.*]] = call i32 @less_than_two(i32 [[CMP2]]) +; IS__CGSCC____-NEXT: [[RET:%.*]] = add i32 [[TRUE1]], [[TRUE2]] +; IS__CGSCC____-NEXT: ret i32 [[RET]] +; + %cmp = icmp slt i32 %c, 2 + %ret = zext i1 %cmp to i32 + ret i32 %ret +} + + +; potential-test 4,5 +; +; 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: define {{[^@]+}}@potential_test4 +; IS__TUNIT____-SAME: (i32 [[C:%.*]]) +; IS__TUNIT____-NEXT: ret i32 0 +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test4 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET:%.*]] = call i32 @return1or3(i32 [[C]]) +; 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 = tail 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: define {{[^@]+}}@potential_test5 +; IS__TUNIT____-SAME: (i32 [[C:%.*]]) +; IS__TUNIT____-NEXT: ret i32 0 +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test5 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @return2or4(i32 [[C]]) +; 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 = tail call i32 @return1or3(i32 %c) + %csret2 = tail 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: define {{[^@]+}}@potential_test6 +; IS__TUNIT____-SAME: (i32 [[C:%.*]]) +; 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: define {{[^@]+}}@potential_test6 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) +; 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: define {{[^@]+}}@potential_test7 +; IS__TUNIT____-SAME: (i32 [[C:%.*]]) +; 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: define {{[^@]+}}@potential_test7 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[CSRET1:%.*]] = call i32 @return1or3(i32 [[C]]) +; IS__CGSCC____-NEXT: [[CSRET2:%.*]] = call i32 @return3or4(i32 [[C]]) +; 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: define {{[^@]+}}@return1or3 +; CHECK-SAME: (i32 [[C:%.*]]) +; 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: define {{[^@]+}}@return2or4 +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; 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: define {{[^@]+}}@return3or4 +; CHECK-SAME: (i32 [[C:%.*]]) +; 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: define {{[^@]+}}@cmp_with_four +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; 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: define {{[^@]+}}@wrapper +; IS__CGSCC____-SAME: (i32 [[C:%.*]]) +; IS__CGSCC____-NEXT: [[RET:%.*]] = call i1 @cmp_with_four(i32 [[C]]) +; IS__CGSCC____-NEXT: ret i1 [[RET]] +; + %ret = call i1 @cmp_with_four(i32 %c) + ret i1 %ret +} + +define i1 @potential_test8() { +; IS__TUNIT____-LABEL: define {{[^@]+}}@potential_test8() +; IS__TUNIT____-NEXT: ret i1 false +; +; IS__CGSCC____-LABEL: define {{[^@]+}}@potential_test8() +; IS__CGSCC____-NEXT: [[RES1:%.*]] = call i1 @wrapper(i32 1) +; IS__CGSCC____-NEXT: [[RES3:%.*]] = call i1 @wrapper(i32 3) +; IS__CGSCC____-NEXT: [[RES5:%.*]] = call i1 @wrapper(i32 5) +; 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 +} + +define i1 @potential_test9() { +; CHECK-LABEL: define {{[^@]+}}@potential_test9() +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[COND:%.*]] +; CHECK: cond: +; CHECK-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I_1:%.*]], [[INC:%.*]] ] +; CHECK-NEXT: [[C_0:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ [[C_1:%.*]], [[INC]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_0]], 10 +; CHECK-NEXT: br i1 [[CMP]], label [[BODY:%.*]], label [[END:%.*]] +; CHECK: body: +; CHECK-NEXT: [[C_1]] = mul i32 [[C_0]], -1 +; CHECK-NEXT: br label [[INC]] +; CHECK: inc: +; CHECK-NEXT: [[I_1]] = add i32 [[I_0]], 1 +; CHECK-NEXT: br label [[COND]] +; CHECK: end: +; CHECK-NEXT: ret i1 false +; +entry: + br label %cond +cond: + %i.0 = phi i32 [0, %entry], [%i.1, %inc] + %c.0 = phi i32 [1, %entry], [%c.1, %inc] + %cmp = icmp slt i32 %i.0, 10 + br i1 %cmp, label %body, label %end +body: + %c.1 = mul i32 %c.0, -1 + br label %inc +inc: + %i.1 = add i32 %i.0, 1 + br label %cond +end: + %ret = icmp eq i32 %c.0, 0 + ret i1 %ret +}