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 @@ -119,6 +119,318 @@ ChangeStatus operator&(ChangeStatus l, ChangeStatus r); ///} +/// Helper to describe and deal with positions in the LLVM-IR. +/// +/// A position in the IR is described by an anchor value and an "offset" that +/// could be the argument number, for call sites and arguments, or an indicator +/// of the "position kind". The kinds, specified in the Kind enum below, include +/// the locations in the attribute list, i.a., function scope and return value, +/// as well as a distinction between call sites and functions. Finally, there +/// are floating values that do not have a corresponding attribute list +/// position. +struct IRPosition { + virtual ~IRPosition() {} + + /// The positions we distinguish in the IR. + /// + /// The values are chosen such that the KindOrArgNo member has a value >= 1 + /// if it is an argument or call site argument while a value < 1 indicates the + /// respective kind of that value. + enum Kind : int { + IRP_INVALID = -6, ///< An invalid position. + IRP_FLOAT = -5, ///< A position that is not associated with a spot suitable + ///< for attributes. This could be any value or instruction. + IRP_RETURNED = -4, ///< An attribute for the function return value. + IRP_CALL_SITE_RETURNED = -3, ///< An attribute for a call site return value. + IRP_FUNCTION = -2, ///< An attribute for a function (scope). + IRP_CALL_SITE = -1, ///< An attribute for a call site (function scope). + IRP_ARGUMENT = 0, ///< An attribute for a function argument. + IRP_CALL_SITE_ARGUMENT = 1, ///< An attribute for a call site argument. + }; + + /// Default constructor available to create invalid positions implicitly. All + /// other positions need to be created explicitly through the appropriate + /// static member function. + IRPosition() : AnchorVal(nullptr), KindOrArgNo(IRP_INVALID) { verify(); } + + /// Create a position describing the value of \p V in \p AnchorScope. + static const IRPosition value(const Value &V, const Function &AnchorScope) { + // TODO: Determine if we need the scope at all. + if (auto *Arg = dyn_cast(&V)) + return IRPosition::argument(*Arg); + if (auto *CB = dyn_cast(&V)) + return IRPosition::callsite_returned(*CB); + return IRPosition(const_cast(V), IRP_FLOAT); + } + + /// Create a position describing the value of \p I in its function. + static const IRPosition value(const Instruction &I) { + return IRPosition::value(I, *I.getFunction()); + } + + /// Create a position describing the function scope of \p F. + static const IRPosition function(const Function &F) { + return IRPosition(const_cast(F), IRP_FUNCTION); + } + + /// Create a position describing the returned value of \p F. + static const IRPosition returned(const Function &F) { + return IRPosition(const_cast(F), IRP_RETURNED); + } + + /// Create a position describing the argument \p Arg. + static const IRPosition argument(const Argument &Arg) { + return IRPosition(const_cast(Arg), Kind(Arg.getArgNo())); + } + + /// Create a position describing the function scope of \p CB. + static const IRPosition callsite_function(const CallBase &CB) { + return IRPosition(const_cast(CB), IRP_CALL_SITE); + } + + /// Create a position describing the returned value of \p CB. + static const IRPosition callsite_returned(const CallBase &CB) { + return IRPosition(const_cast(CB), IRP_CALL_SITE_RETURNED); + } + + /// Create a position describing the argument of \p CB at position \p ArgNo. + static const IRPosition callsite_argument(const CallBase &CB, + unsigned ArgNo) { + return IRPosition(const_cast(CB), Kind(ArgNo)); + } + + /// Create a position describing the function scope of \p ICS. + static const IRPosition callsite_function(ImmutableCallSite ICS) { + return IRPosition::callsite_function(cast(*ICS.getInstruction())); + } + + /// Create a position describing the returned value of \p ICS. + static const IRPosition callsite_returned(ImmutableCallSite ICS) { + return IRPosition::callsite_returned(cast(*ICS.getInstruction())); + } + + /// Create a position describing the argument of \p ICS at position \p ArgNo. + static const IRPosition callsite_argument(ImmutableCallSite ICS, + unsigned ArgNo) { + return IRPosition::callsite_argument(cast(*ICS.getInstruction()), + ArgNo); + } + + bool operator==(const IRPosition &RHS) const { + return (AnchorVal == RHS.AnchorVal) && (KindOrArgNo == RHS.KindOrArgNo); + } + bool operator!=(const IRPosition &RHS) const { return !(*this == RHS); } + + /// Return the value this abstract attribute is anchored with. + /// + /// The anchor value might not be the associated value if the latter is not + /// sufficient to determine where arguments will be manifested. This is, so + /// far, only the case for call site arguments as the value is not sufficient + /// to pinpoint them. Instead, we can use the call site as an anchor. + /// + ///{ + Value &getAnchorValue() { + assert(KindOrArgNo != IRP_INVALID && + "Invalid position does not have an anchor value!"); + return *AnchorVal; + } + const Value &getAnchorValue() const { + return const_cast(this)->getAnchorValue(); + } + ///} + + /// Return the Function surrounding the anchor value. + /// + ///{ + Function &getAnchorScope() { + assert(KindOrArgNo != IRP_INVALID && + "Invalid position does not have an anchor scope!"); + Value &V = getAnchorValue(); + if (isa(V)) + return cast(V); + if (isa(V)) + return *cast(V).getParent(); + if (isa(V)) + return *cast(V).getFunction(); + // TODO: Figure out if this makes sense. + llvm_unreachable("Could not determine scope!"); + } + const Function &getAnchorScope() const { + return const_cast(this)->getAnchorScope(); + } + ///} + + /// Return the value this abstract attribute is associated with. + /// + ///{ + Value &getAssociatedValue() { + assert(KindOrArgNo != IRP_INVALID && + "Invalid position does not have an associated value!"); + if (getArgNo() < 0 || isa(AnchorVal)) + return *AnchorVal; + assert(isa(AnchorVal) && "Expected a call base!"); + return *cast(AnchorVal)->getArgOperand(getArgNo()); + } + const Value &getAssociatedValue() const { + return const_cast(this)->getAssociatedValue(); + } + ///} + + /// Return the argument number of the associated value if it is an argument or + /// call site argument, otherwise a negative value. + int getArgNo() const { return KindOrArgNo; } + + /// Return the index in the attribute list for this position. + unsigned getAttrIdx() const { + switch (getPositionKind()) { + case IRPosition::IRP_INVALID: + case IRPosition::IRP_FLOAT: + break; + case IRPosition::IRP_FUNCTION: + case IRPosition::IRP_CALL_SITE: + return AttributeList::FunctionIndex; + case IRPosition::IRP_RETURNED: + case IRPosition::IRP_CALL_SITE_RETURNED: + return AttributeList::ReturnIndex; + case IRPosition::IRP_ARGUMENT: + case IRPosition::IRP_CALL_SITE_ARGUMENT: + return KindOrArgNo + AttributeList::FirstArgIndex; + } + llvm_unreachable( + "There is no attribute index for a floating or invalid position!"); + } + + /// Return the associated position kind. + Kind getPositionKind() const { + if (getArgNo() >= 0) { + assert(((isa(getAnchorValue()) && + isa(getAssociatedValue())) || + isa(getAnchorValue())) && + "Expected argument or call base due to argument number!"); + if (isa(getAnchorValue())) + return IRP_CALL_SITE_ARGUMENT; + return IRP_ARGUMENT; + } + + assert(KindOrArgNo < 0 && + "Expected (call site) arguments to never reach this point!"); + assert(!isa(getAnchorValue()) && + "Expected arguments to have an associated argument position!"); + return Kind(KindOrArgNo); + } + + /// TODO: Figure out if the attribute related helper functions should live + /// here or somewhere else. + + /// Return true if any kind in \p AKs existing in the IR at a position that + /// will affect this one. See also getAttrs(...). + bool hasAttr(ArrayRef AKs) const; + + /// Return the attributes of any kind in \p AKs existing in the IR at a + /// position that will affect this one. While each position can only have a + /// single attribute of any kind in \p AKs, there are "subsuming" positions + /// that could have an attribute as well. This method returns all attributes + /// found in \p Attrs. + void getAttrs(ArrayRef AKs, + SmallVectorImpl &Attrs) const; + + /// Return the attribute of kind \p AK existing in the IR at this position. + Attribute getAttr(Attribute::AttrKind AK) const { + if (getPositionKind() == IRP_INVALID || getPositionKind() == IRP_FLOAT) + return Attribute(); + + AttributeList AttrList; + if (ImmutableCallSite ICS = ImmutableCallSite(&getAnchorValue())) + AttrList = ICS.getAttributes(); + else + AttrList = getAnchorScope().getAttributes(); + + if (AttrList.hasAttribute(getAttrIdx(), AK)) + return AttrList.getAttribute(getAttrIdx(), AK); + return Attribute(); + } + + /// Return the data layout associated with the anchor scope. + const DataLayout &getDataLayout() const { + return getAnchorScope().getParent()->getDataLayout(); + } + + /// Special DenseMap key values. + /// + ///{ + static const IRPosition EmptyKey; + static const IRPosition TombstoneKey; + ///} + +private: + /// Private constructor for special values only! + explicit IRPosition(int KindOrArgNo) + : AnchorVal(0), KindOrArgNo(KindOrArgNo) {} + + /// IRPosition anchored at \p AnchorVal with kind/argument numbet \p PK. + explicit IRPosition(Value &AnchorVal, Kind PK) + : AnchorVal(&AnchorVal), KindOrArgNo(PK) { + verify(); + } + + /// Verify internal invariants. + void verify(); + + /// The value this position is anchored at. + Value *AnchorVal; + + /// The argument number, if non-negative, or the position "kind". + int KindOrArgNo; +}; + +/// Helper that allows IRPosition as a key in a DenseMap. +template <> struct DenseMapInfo { + static inline IRPosition getEmptyKey() { return IRPosition::EmptyKey; } + static inline IRPosition getTombstoneKey() { + return IRPosition::TombstoneKey; + } + static unsigned getHashValue(const IRPosition &IRP) { + return (DenseMapInfo::getHashValue(&IRP.getAnchorValue()) << 4) ^ + (unsigned(IRP.getArgNo())); + } + static bool isEqual(const IRPosition &LHS, const IRPosition &RHS) { + return LHS == RHS; + } +}; + +/// A visitor class for IR positions. +/// +/// Given a position P, the SubsumingPositionIterator allows to visit "subsuming +/// positions" wrt. attributes/information. Thus, if a piece of information +/// holds for a subsuming position, it also holds for the position P. +/// +/// The subsuming positions always include the initial position and then, +/// depending on the position kind, additionally the following ones: +/// - for IRP_RETURNED: +/// - the function (IRP_FUNCTION) +/// - for IRP_ARGUMENT: +/// - the function (IRP_FUNCTION) +/// - for IRP_CALL_SITE: +/// - the callee (IRP_FUNCTION), if known +/// - for IRP_CALL_SITE_RETURNED: +/// - the callee (IRP_RETURNED), if known +/// - the call site (IRP_FUNCTION) +/// - the callee (IRP_FUNCTION), if known +/// - for IRP_CALL_SITE_ARGUMENT: +/// - the argument of the callee (IRP_ARGUMENT), if known +/// - the callee (IRP_FUNCTION), if known +/// - the position the call site argument is associated with if it is not +/// anchored to the call site, e.g., if it is an arugment then the argument +/// (IRP_ARGUMENT) +class SubsumingPositionIterator { + SmallVector IRPositions; + using iterator = decltype(IRPositions)::iterator; +public: + SubsumingPositionIterator(const IRPosition &IRP); + iterator begin() { return IRPositions.begin(); } + iterator end() { return IRPositions.end(); } +}; + /// The fixpoint analysis framework that orchestrates the attribute deduction. /// /// The Attributor provides a general abstract analysis framework (guided @@ -157,10 +469,11 @@ /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED. ChangeStatus run(InformationCache &InfoCache); - /// Lookup an abstract attribute of type \p AAType anchored at value \p V and - /// argument number \p ArgNo. If no attribute is found and \p V is a call base - /// instruction, the called function is tried as a value next. Thus, the - /// returned abstract attribute might be anchored at the callee of \p V. + /// Lookup an abstract attribute of type \p AAType at position \p IRP. While + /// no abstract attribute is found equivalent positions are checked, see + /// SubsumingPositionIterator. Thus, the returned abstract attribute + /// might be anchored at a different position, e.g., the callee if \p IRP is a + /// call base. /// /// This method is the only (supported) way an abstract attribute can retrieve /// information from another abstract attribute. As an example, take an @@ -170,46 +483,30 @@ /// the one reasoning about the "captured" state for the argument or the one /// reasoning on the memory access behavior of the function as a whole. template - const AAType *getAAFor(const AbstractAttribute &QueryingAA, const Value &V, - int ArgNo = -1) { + const AAType *getAAFor(const AbstractAttribute &QueryingAA, + const IRPosition &IRP) { static_assert(std::is_base_of::value, "Cannot query an attribute with a type not derived from " "'AbstractAttribute'!"); - // Determine the argument number automatically for llvm::Arguments if none - // is set. Do not override a given one as it could be a use of the argument - // in a call site. - if (ArgNo == -1) - if (auto *Arg = dyn_cast(&V)) - ArgNo = Arg->getArgNo(); - - // If a function was given together with an argument number, perform the - // lookup for the actual argument instead. Don't do it for variadic - // arguments. - if (ArgNo >= 0 && isa(&V) && - cast(&V)->arg_size() > (size_t)ArgNo) - return getAAFor( - QueryingAA, *(cast(&V)->arg_begin() + ArgNo), ArgNo); - - // Lookup the abstract attribute of type AAType. If found, return it after - // registering a dependence of QueryingAA on the one returned attribute. - const auto &KindToAbstractAttributeMap = AAMap.lookup({&V, ArgNo}); - if (AAType *AA = static_cast( - KindToAbstractAttributeMap.lookup(&AAType::ID))) { - // Do not return an attribute with an invalid state. This minimizes checks - // at the calls sites and allows the fallback below to kick in. - if (AA->getState().isValidState()) { - QueryMap[AA].insert(const_cast(&QueryingAA)); - return AA; + // Let's try an equivalent position if available, see + // SubsumingPositionIterator for more information. + for (const IRPosition &EquivIRP : SubsumingPositionIterator(IRP)) { + // Lookup the abstract attribute of type AAType. If found, return it after + // registering a dependence of QueryingAA on the one returned attribute. + const auto &KindToAbstractAttributeMap = + AAMap.lookup(const_cast(EquivIRP)); + if (AAType *AA = static_cast( + KindToAbstractAttributeMap.lookup(&AAType::ID))) { + // Do not return an attribute with an invalid state. This minimizes + // checks at the calls sites and allows the fallback below to kick in. + if (AA->getState().isValidState()) { + QueryMap[AA].insert(const_cast(&QueryingAA)); + return AA; + } } } - // If no abstract attribute was found and we look for a call site argument, - // defer to the actual argument instead. - ImmutableCallSite ICS(&V); - if (ICS && ICS.getCalledValue()) - return getAAFor(QueryingAA, *ICS.getCalledValue(), ArgNo); - // No matching attribute found return nullptr; } @@ -219,27 +516,16 @@ /// Note that ownership of the attribute is given to the Attributor. It will /// invoke delete for the Attributor on destruction of the Attributor. /// - /// Attributes are identified by - /// (1) their anchored value (see AA.getAnchoredValue()), - /// (2) their argument number (\p ArgNo, or Argument::getArgNo()), and - /// (3) the address of their static member (see AAType::ID). - template AAType ®isterAA(AAType &AA, int ArgNo = -1) { + /// Attributes are identified by their IR position (AAType::getIRPosition()) + /// and the address of their static member (see AAType::ID). + template AAType ®isterAA(AAType &AA) { static_assert(std::is_base_of::value, "Cannot register an attribute with a type not derived from " "'AbstractAttribute'!"); - - // Determine the anchor value and the argument number which are used to - // lookup the attribute together with AAType::ID. If passed an argument, - // use its argument number but do not override a given one as it could be a - // use of the argument at a call site. - Value &AnchorVal = AA.getIRPosition().getAnchorValue(); - if (ArgNo == -1) - if (auto *Arg = dyn_cast(&AnchorVal)) - ArgNo = Arg->getArgNo(); - // Put the attribute in the lookup map structure and the container we use to // keep track of all attributes. - AAMap[{&AnchorVal, ArgNo}][&AAType::ID] = &AA; + IRPosition &IRP = AA.getIRPosition(); + AAMap[IRP][&AAType::ID] = &AA; AllAbstractAttributes.push_back(&AA); return AA; } @@ -325,13 +611,13 @@ AAVector AllAbstractAttributes; ///} - /// A nested map to lookup abstract attributes based on the anchored value and - /// an argument positions (or -1) on the outer level, and the addresses of the - /// static member (AAType::ID) on the inner level. + /// A nested map to lookup abstract attributes based on the argument position + /// on the outer level, and the addresses of the static member (AAType::ID) on + /// the inner level. ///{ using KindToAbstractAttributeMap = DenseMap; - DenseMap, KindToAbstractAttributeMap> AAMap; + DenseMap AAMap; ///} /// A map from abstract attributes to the ones that queried them through calls @@ -547,142 +833,6 @@ BooleanState() : IntegerState(1){}; }; -/// Struct to encode the position in the LLVM-IR with regards to the associated -/// value but also the attribute lists. -struct IRPosition { - - /// The positions attributes can be manifested in. - enum Kind { - IRP_FUNCTION = AttributeList::FunctionIndex, ///< An attribute for a - ///< function as a whole. - IRP_RETURNED = AttributeList::ReturnIndex, ///< An attribute for the - ///< function return value. - IRP_ARGUMENT, ///< An attribute for a function argument. - IRP_CALL_SITE_ARGUMENT, ///< An attribute for a call site argument. - }; - - /// Create an IRPosition for an argument. - explicit IRPosition(Argument &Arg) : IRPosition(&Arg, Arg, Arg.getArgNo()) {} - - /// Create an IRPosition for a function return or function body position. - /// - /// \param Fn The value this abstract attributes is anchored at and - /// associated with. - /// \param PK The kind of attribute position, can not be a (call site) - /// argument. - explicit IRPosition(Function &Fn, Kind PK) - : AssociatedVal(&Fn), AnchorVal(Fn), AttributeIdx(PK) { - assert((PK == IRP_RETURNED || PK == IRP_FUNCTION) && - "Expected non-argument position!"); - } - - /// An abstract attribute associated with \p AssociatedVal and anchored at - /// \p AnchorVal. - /// - /// \param AssociatedVal The value this abstract attribute is associated with. - /// \param AnchorVal The value this abstract attributes is anchored at. - /// \param ArgumentNo The index in the attribute list, encodes also the - /// argument number if this is one. - explicit IRPosition(Value *AssociatedVal, Value &AnchorVal, - unsigned ArgumentNo) - : AssociatedVal(AssociatedVal), AnchorVal(AnchorVal), - AttributeIdx(ArgumentNo + AttributeList::FirstArgIndex) { - assert(((isa(&AnchorVal) && - cast(&AnchorVal)->arg_size() > ArgumentNo) || - (isa(AnchorVal) && - cast(AnchorVal).getArgNo() == ArgumentNo)) && - "Expected a valid argument index!"); - } - -#define IRPositionConstructorForward(NAME, BASE) \ - explicit NAME(Argument &Arg) : BASE(Arg) {} \ - explicit NAME(Function &Fn, IRPosition::Kind PK) : BASE(Fn, PK) {} \ - NAME(Value *AssociatedVal, Value &AnchorVal, unsigned ArgumentNo) \ - : BASE(AssociatedVal, AnchorVal, ArgumentNo) {} - - IRPosition(const IRPosition &AAP) - : IRPosition(AAP.AssociatedVal, AAP.AnchorVal, AAP.AttributeIdx) {} - - /// Virtual destructor. - virtual ~IRPosition() {} - - /// Return the value this abstract attribute is anchored with. - /// - /// The anchored value might not be the associated value if the latter is not - /// sufficient to determine where arguments will be manifested. This is mostly - /// the case for call site arguments as the value is not sufficient to - /// pinpoint them. Instead, we can use the call site as an anchor. - /// - ///{ - Value &getAnchorValue() { return AnchorVal; } - const Value &getAnchorValue() const { return AnchorVal; } - ///} - - /// Return the llvm::Function surrounding the anchored value. - /// - ///{ - Function &getAnchorScope() { - Value &V = getAnchorValue(); - if (isa(V)) - return cast(V); - if (isa(V)) - return *cast(V).getParent(); - if (isa(V)) - return *cast(V).getFunction(); - llvm_unreachable("No scope for anchored value found!"); - } - const Function &getAnchorScope() const { - return const_cast(this)->getAnchorScope(); - } - ///} - - /// Return the value this abstract attribute is associated with. - /// - /// The abstract state usually represents this value. - /// - ///{ - Value *getAssociatedValue() { return AssociatedVal; } - const Value *getAssociatedValue() const { return AssociatedVal; } - ///} - - /// Return the argument number of the associated value if it is an argument or - /// call site argument, otherwise a negative value. - int getArgNo() const { return AttributeIdx - AttributeList::FirstArgIndex; } - - /// Return the position this abstract state is manifested in. - Kind getPositionKind() const { - if (getArgNo() >= 0) { - if (isa(getAnchorValue())) - return IRP_CALL_SITE_ARGUMENT; - assert((isa(getAnchorValue()) || - isa_and_nonnull(getAssociatedValue()) || - (!getAssociatedValue() && isa(getAnchorValue()))) && - "Expected argument or call base due to argument number!"); - return IRP_ARGUMENT; - } - return (Kind)AttributeIdx; - } - - /// Return the index in the attribute list for this position. - int getAttrIdx() const { return AttributeIdx; } - - /// Change the associated value. - void setAssociatedValue(Value *V) { AssociatedVal = V; } - - /// Change the associated attribue list position. - void setAttributeIdx(int AttrIdx) { AttributeIdx = AttrIdx; } - -protected: - /// The value this abstract attribute is associated with. - Value *AssociatedVal; - - /// The value this abstract attribute is anchored at. - Value &AnchorVal; - - /// The index in the attribute list. - int AttributeIdx; -}; - /// Helper struct necessary as the modular build fails if the virtual method /// IRAttribute::manifest is defined in the Attributor.cpp. struct IRAttributeManifest { @@ -705,16 +855,10 @@ /// Helper class that provides common functionality to manifest IR attributes. template -struct IRAttribute : public IRPosition, - public Base { +struct IRAttribute : public IRPosition, public Base { + IRAttribute(const IRPosition &IRP) : IRPosition(IRP) {} ~IRAttribute() {} - /// Constructors for the IRPosition. - /// - ///{ - IRPositionConstructorForward(IRAttribute, IRPosition); - ///} - /// See AbstractAttribute::manifest(...). ChangeStatus manifest(Attributor &A) { SmallVector DeducedAttrs; @@ -878,7 +1022,7 @@ /// An abstract attribute for the returned values of a function. struct AAReturnedValues : public IRAttribute { - IRPositionConstructorForward(AAReturnedValues, IRAttribute); + AAReturnedValues(const IRPosition &IRP) : IRAttribute(IRP) {} /// Check \p Pred on all returned values. /// @@ -899,7 +1043,7 @@ struct AANoUnwind : public IRAttribute> { - IRPositionConstructorForward(AANoUnwind, IRAttribute); + AANoUnwind(const IRPosition &IRP) : IRAttribute(IRP) {} /// Returns true if nounwind is assumed. bool isAssumedNoUnwind() const { return getAssumed(); } @@ -914,7 +1058,7 @@ struct AANoSync : public IRAttribute> { - IRPositionConstructorForward(AANoSync, IRAttribute); + AANoSync(const IRPosition &IRP) : IRAttribute(IRP) {} /// Returns true if "nosync" is assumed. bool isAssumedNoSync() const { return getAssumed(); } @@ -930,7 +1074,7 @@ struct AANonNull : public IRAttribute> { - IRPositionConstructorForward(AANonNull, IRAttribute); + AANonNull(const IRPosition &IRP) : IRAttribute(IRP) {} /// Return true if we assume that the underlying value is nonnull. bool isAssumedNonNull() const { return getAssumed(); } @@ -946,7 +1090,7 @@ struct AANoRecurse : public IRAttribute> { - IRPositionConstructorForward(AANoRecurse, IRAttribute); + AANoRecurse(const IRPosition &IRP) : IRAttribute(IRP) {} /// Return true if "norecurse" is assumed. bool isAssumedNoRecurse() const { return getAssumed(); } @@ -962,7 +1106,7 @@ struct AAWillReturn : public IRAttribute> { - IRPositionConstructorForward(AAWillReturn, IRAttribute); + AAWillReturn(const IRPosition &IRP) : IRAttribute(IRP) {} /// Return true if "willreturn" is assumed. bool isAssumedWillReturn() const { return getAssumed(); } @@ -978,7 +1122,7 @@ struct AANoAlias : public IRAttribute> { - IRPositionConstructorForward(AANoAlias, IRAttribute); + AANoAlias(const IRPosition &IRP) : IRAttribute(IRP) {} /// Return true if we assume that the underlying value is alias. bool isAssumedNoAlias() const { return getAssumed(); } @@ -994,7 +1138,7 @@ struct AANoFree : public IRAttribute> { - IRPositionConstructorForward(AANoFree, IRAttribute); + AANoFree(const IRPosition &IRP) : IRAttribute(IRP) {} /// Return true if "nofree" is assumed. bool isAssumedNoFree() const { return getAssumed(); } @@ -1010,7 +1154,7 @@ struct AANoReturn : public IRAttribute> { - IRPositionConstructorForward(AANoReturn, IRAttribute); + AANoReturn(const IRPosition &IRP) : IRAttribute(IRP) {} /// Return true if the underlying object is assumed to never return. bool isAssumedNoReturn() const { return getAssumed(); } @@ -1025,7 +1169,7 @@ /// An abstract interface for liveness abstract attribute. struct AAIsDead : public StateWrapper, public IRPosition { - IRPositionConstructorForward(AAIsDead, IRPosition); + AAIsDead(const IRPosition &IRP) : IRPosition(IRP) {} /// Returns true if \p BB is assumed dead. virtual bool isAssumedDead(const BasicBlock *BB) const = 0; @@ -1067,7 +1211,7 @@ /// An abstract interface for all dereferenceable attribute. struct AADereferenceable : public IRAttribute { - IRPositionConstructorForward(AADereferenceable, IRAttribute); + AADereferenceable(const IRPosition &IRP) : IRAttribute(IRP) {} /// Return true if we assume that the underlying value is nonnull. virtual bool isAssumedNonNull() const = 0; @@ -1097,7 +1241,7 @@ struct AAAlign : public IRAttribute> { - IRPositionConstructorForward(AAAlign, IRAttribute); + AAAlign(const IRPosition &IRP) : IRAttribute(IRP) {} /// Return assumed alignment. unsigned getAssumedAlign() const { return getAssumed(); } 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 @@ -266,9 +266,6 @@ ChangeStatus IRAttributeManifest::manifestAttrs(Attributor &A, IRPosition &IRP, const ArrayRef &DeducedAttrs) { - assert(IRP.getAssociatedValue() && - "Attempted to manifest an attribute without associated value!"); - ChangeStatus HasChanged = ChangeStatus::UNCHANGED; Function &ScopeFn = IRP.getAnchorScope(); @@ -281,11 +278,16 @@ AttributeList Attrs; switch (PK) { + case IRPosition::IRP_INVALID: + case IRPosition::IRP_FLOAT: + llvm_unreachable("Cannot manifest at a floating or invalid position!"); case IRPosition::IRP_ARGUMENT: case IRPosition::IRP_FUNCTION: case IRPosition::IRP_RETURNED: Attrs = ScopeFn.getAttributes(); break; + case IRPosition::IRP_CALL_SITE: + case IRPosition::IRP_CALL_SITE_RETURNED: case IRPosition::IRP_CALL_SITE_ARGUMENT: Attrs = ImmutableCallSite(&IRP.getAnchorValue()).getAttributes(); break; @@ -307,17 +309,145 @@ case IRPosition::IRP_RETURNED: ScopeFn.setAttributes(Attrs); break; + case IRPosition::IRP_CALL_SITE: + case IRPosition::IRP_CALL_SITE_RETURNED: case IRPosition::IRP_CALL_SITE_ARGUMENT: CallSite(&IRP.getAnchorValue()).setAttributes(Attrs); + case IRPosition::IRP_FLOAT: + case IRPosition::IRP_INVALID: + break; } return HasChanged; } +const IRPosition IRPosition::EmptyKey(255); +const IRPosition IRPosition::TombstoneKey(256); + +SubsumingPositionIterator::SubsumingPositionIterator(const IRPosition &IRP) { + IRPositions.emplace_back(IRP); + + ImmutableCallSite ICS(&IRP.getAnchorValue()); + switch (IRP.getPositionKind()) { + case IRPosition::IRP_INVALID: + case IRPosition::IRP_FLOAT: + case IRPosition::IRP_FUNCTION: + return; + case IRPosition::IRP_ARGUMENT: + case IRPosition::IRP_RETURNED: + IRPositions.emplace_back(IRPosition::function(IRP.getAnchorScope())); + return; + case IRPosition::IRP_CALL_SITE: + assert(ICS && "Expected call site!"); + // TODO: We need to look at the operand bundles similar to the redirection + // in CallBase. + if (!ICS.hasOperandBundles()) + if (const Function *Callee = ICS.getCalledFunction()) + IRPositions.emplace_back(IRPosition::function(*Callee)); + return; + case IRPosition::IRP_CALL_SITE_RETURNED: + assert(ICS && "Expected call site!"); + // TODO: We need to look at the operand bundles similar to the redirection + // in CallBase. + if (!ICS.hasOperandBundles()) { + if (const Function *Callee = ICS.getCalledFunction()) { + IRPositions.emplace_back(IRPosition::returned(*Callee)); + IRPositions.emplace_back(IRPosition::function(*Callee)); + } + } + IRPositions.emplace_back( + IRPosition::callsite_function(cast(*ICS.getInstruction()))); + return; + case IRPosition::IRP_CALL_SITE_ARGUMENT: { + int ArgNo = IRP.getArgNo(); + assert(ICS && ArgNo >= 0 && "Expected call site!"); + // TODO: We need to look at the operand bundles similar to the redirection + // in CallBase. + if (!ICS.hasOperandBundles()) { + const Function *Callee = ICS.getCalledFunction(); + if (Callee && Callee->arg_size() > unsigned(ArgNo)) + IRPositions.emplace_back(IRPosition::argument(*Callee->getArg(ArgNo))); + if (Callee) + IRPositions.emplace_back(IRPosition::function(*Callee)); + } + IRPositions.emplace_back( + IRPosition::value(IRP.getAssociatedValue(), IRP.getAnchorScope())); + return; + } + } +} + +bool IRPosition::hasAttr(ArrayRef AKs) const { + for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) + for (Attribute::AttrKind AK : AKs) + if (EquivIRP.getAttr(AK).getKindAsEnum() == AK) + return true; + return false; +} + +void IRPosition::getAttrs(ArrayRef AKs, + SmallVectorImpl &Attrs) const { + for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) + for (Attribute::AttrKind AK : AKs) { + const Attribute &Attr = EquivIRP.getAttr(AK); + if (Attr.getKindAsEnum() == AK) + Attrs.push_back(Attr); + } +} + +void IRPosition::verify() { + switch (KindOrArgNo) { + default: + assert(KindOrArgNo >= 0 && "Expected argument or call site argument!"); + assert((isa(AnchorVal) || isa(AnchorVal)) && + "Expected call base or argument for positive attribute index!"); + if (auto *Arg = dyn_cast(AnchorVal)) { + assert(Arg->getArgNo() == unsigned(getArgNo()) && + "Argument number mismatch!"); + assert(Arg == &getAssociatedValue() && "Associated value mismatch!"); + } else { + auto &CB = cast(*AnchorVal); + assert(CB.arg_size() > unsigned(getArgNo()) && + "Call site argument number mismatch!"); + assert(CB.getArgOperand(getArgNo()) == &getAssociatedValue() && + "Associated value mismatch!"); + } + break; + case IRP_INVALID: + assert(!AnchorVal && "Expected no value for an invalid position!"); + break; + case IRP_FLOAT: + assert((!isa(&getAssociatedValue()) && + !isa(&getAssociatedValue())) && + "Expected specialized kind for call base and argument values!"); + break; + case IRP_RETURNED: + assert(isa(AnchorVal) && + "Expected function for a 'returned' position!"); + assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!"); + break; + case IRP_CALL_SITE_RETURNED: + assert((isa(AnchorVal)) && + "Expected call base for 'call site returned' position!"); + assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!"); + break; + case IRP_CALL_SITE: + assert((isa(AnchorVal)) && + "Expected call base for 'call site function' position!"); + assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!"); + break; + case IRP_FUNCTION: + assert(isa(AnchorVal) && + "Expected function for a 'function' position!"); + assert(AnchorVal == &getAssociatedValue() && "Associated value mismatch!"); + break; + } +} + /// -----------------------NoUnwind Function Attribute-------------------------- struct AANoUnwindImpl : AANoUnwind { - IRPositionConstructorForward(AANoUnwindImpl, AANoUnwind); + AANoUnwindImpl(const IRPosition &IRP) : AANoUnwind(IRP) {} const std::string getAsStr() const override { return getAssumed() ? "nounwind" : "may-unwind"; @@ -328,7 +458,7 @@ }; struct AANoUnwindFunction final : public AANoUnwindImpl { - AANoUnwindFunction(Function &F) : AANoUnwindImpl(F, IRP_FUNCTION) {} + AANoUnwindFunction(const IRPosition &IRP) : AANoUnwindImpl(IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { @@ -350,7 +480,7 @@ if (!I.mayThrow()) return true; - auto *NoUnwindAA = A.getAAFor(*this, I); + auto *NoUnwindAA = A.getAAFor(*this, IRPosition::value(I)); return NoUnwindAA && NoUnwindAA->isAssumedNoUnwind(); }; @@ -408,12 +538,11 @@ } public: - IRPositionConstructorForward(AAReturnedValuesImpl, AAReturnedValues); + AAReturnedValuesImpl(const IRPosition &IRP) : AAReturnedValues(IRP) {} /// See AbstractAttribute::initialize(...). void initialize(Attributor &A, InformationCache &InfoCache) override { // Reset the state. - setAssociatedValue(nullptr); IsFixed = false; IsValidState = true; HasOverdefinedReturnedCalls = false; @@ -496,9 +625,8 @@ } }; -struct AAReturnedValuesFunction final : public AAReturnedValuesImpl { - AAReturnedValuesFunction(Function &F) - : AAReturnedValuesImpl(F, IRP_FUNCTION) {} +struct AAReturnedValuesReturned final : public AAReturnedValuesImpl { + AAReturnedValuesReturned(const IRPosition &IRP) : AAReturnedValuesImpl(IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { @@ -526,8 +654,7 @@ // If the assumed unique return value is an argument, annotate it. if (auto *UniqueRVArg = dyn_cast(UniqueRV.getValue())) { - setAssociatedValue(UniqueRVArg); - setAttributeIdx(UniqueRVArg->getArgNo() + AttributeList::FirstArgIndex); + getIRPosition() = IRPosition::argument(*UniqueRVArg); Changed = IRAttribute::manifest(A) | Changed; } @@ -612,7 +739,7 @@ // Keep track of any change to trigger updates on dependent attributes. ChangeStatus Changed = ChangeStatus::UNCHANGED; - auto *LivenessAA = A.getAAFor(*this, getAnchorScope()); + auto *LivenessAA = A.getAAFor(*this, getIRPosition()); // Look at all returned call sites. for (auto &It : ReturnedValues) { @@ -641,7 +768,8 @@ } // Try to find a assumed unique return value for the called function. - auto *RetCSAA = A.getAAFor(*this, *RV); + auto *RetCSAA = A.getAAFor( + *this, IRPosition::callsite_returned(RetCS)); if (!RetCSAA) { if (!HasOverdefinedReturnedCalls) Changed = ChangeStatus::CHANGED; @@ -657,9 +785,9 @@ // If no assumed unique return value was found due to the lack of // candidates, we may need to resolve more calls (through more update - // iterations) or the called function will not return. Either way, we simply - // stick with the call sites as return values. Because there were not - // multiple possibilities, we do not treat it as overdefined. + // iterations) or the called function will not return. Either way, we + // simply stick with the call sites as return values. Because there were + // not multiple possibilities, we do not treat it as overdefined. if (!AssumedUniqueRV.hasValue()) continue; @@ -686,8 +814,9 @@ // If the assumed unique return value is an argument, lookup the matching // call site operand and recursively collect new returned values. - // If it is not an argument, it is just put into the set of returned values - // as we would have already looked through casts, phis, and similar values. + // If it is not an argument, it is just put into the set of returned + // values as we would have already looked through casts, phis, and similar + // values. if (Argument *AssumedRetArg = dyn_cast(AssumedRetVal)) collectValuesRecursively(A, RetCS.getArgOperand(AssumedRetArg->getArgNo()), @@ -719,7 +848,7 @@ /// ------------------------ NoSync Function Attribute ------------------------- struct AANoSyncImpl : AANoSync { - IRPositionConstructorForward(AANoSyncImpl, AANoSync); + AANoSyncImpl(const IRPosition &IRP) : AANoSync(IRP) {} const std::string getAsStr() const override { return getAssumed() ? "nosync" : "may-sync"; @@ -742,7 +871,7 @@ }; struct AANoSyncFunction final : public AANoSyncImpl { - AANoSyncFunction(Function &F) : AANoSyncImpl(F, IRP_FUNCTION) {} + AANoSyncFunction(const IRPosition &IRP) : AANoSyncImpl(IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECL_AND_TRACK_FN_ATTR(nosync) } @@ -845,18 +974,19 @@ /// We are looking for volatile instructions or Non-Relaxed atomics. /// FIXME: We should ipmrove the handling of intrinsics. - ImmutableCallSite ICS(&I); - auto *NoSyncAA = A.getAAFor(*this, I); - if (isa(&I) && isNoSyncIntrinsic(&I)) return true; - if (ICS && (!NoSyncAA || !NoSyncAA->isAssumedNoSync()) && - !ICS.hasFnAttr(Attribute::NoSync)) - return false; + if (ImmutableCallSite ICS = ImmutableCallSite(&I)) { + if (ICS.hasFnAttr(Attribute::NoSync)) + return true; - if (ICS) - return true; + auto *NoSyncAA = + A.getAAFor(*this, IRPosition::callsite_function(ICS)); + if (NoSyncAA && NoSyncAA->isAssumedNoSync()) + return true; + return false; + } if (!isVolatile(&I) && !isNonRelaxedAtomic(&I)) return true; @@ -885,7 +1015,7 @@ /// ------------------------ No-Free Attributes ---------------------------- struct AANoFreeImpl : public AANoFree { - IRPositionConstructorForward(AANoFreeImpl, AANoFree); + AANoFreeImpl(const IRPosition &IRP) : AANoFree(IRP) {} /// See AbstractAttribute::getAsStr(). const std::string getAsStr() const override { @@ -897,7 +1027,7 @@ }; struct AANoFreeFunction final : public AANoFreeImpl { - AANoFreeFunction(Function &F) : AANoFreeImpl(F, IRP_FUNCTION) {} + AANoFreeFunction(const IRPosition &IRP) : AANoFreeImpl(IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECL_AND_TRACK_FN_ATTR(nofree) } @@ -908,10 +1038,12 @@ Function &F = getAnchorScope(); auto CheckForNoFree = [&](Instruction &I) { - if (ImmutableCallSite(&I).hasFnAttr(Attribute::NoFree)) + ImmutableCallSite ICS(&I); + if (ICS.hasFnAttr(Attribute::NoFree)) return true; - auto *NoFreeAA = A.getAAFor(*this, I); + auto *NoFreeAA = + A.getAAFor(*this, IRPosition::callsite_function(ICS)); return NoFreeAA && NoFreeAA->isAssumedNoFree(); }; @@ -922,13 +1054,19 @@ /// ------------------------ NonNull Argument Attribute ------------------------ struct AANonNullImpl : AANonNull { - IRPositionConstructorForward(AANonNullImpl, AANonNull); + AANonNullImpl(const IRPosition &IRP) : AANonNull(IRP) {} /// See AbstractAttribute::getAsStr(). const std::string getAsStr() const override { return getAssumed() ? "nonnull" : "may-null"; } + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A, InformationCache &InfoCache) override { + if (hasAttr({Attribute::NonNull, Attribute::Dereferenceable})) + indicateOptimisticFixpoint(); + } + /// Generate a predicate that checks if a given value is assumed nonnull. /// The generated function returns true if a value satisfies any of /// following conditions. @@ -946,22 +1084,18 @@ // version of `isKnownNonZero`. This should fix `test11` in // `test/Transforms/FunctionAttrs/nonnull.ll` + const Function &F = getAnchorScope(); std::function &)> Pred = [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { - Function &F = getAnchorScope(); - - if (isKnownNonZero(&RV, F.getParent()->getDataLayout())) + if (isKnownNonZero(&RV, getDataLayout())) return true; - auto *NonNullAA = A.getAAFor(*this, RV); - - ImmutableCallSite ICS(&RV); - - if ((!NonNullAA || !NonNullAA->isAssumedNonNull()) && - (!ICS || !ICS.hasRetAttr(Attribute::NonNull))) - return false; + if (ImmutableCallSite ICS = ImmutableCallSite(&RV)) + if (ICS.hasRetAttr(Attribute::NonNull)) + return true; - return true; + auto *NonNullAA = A.getAAFor(*this, IRPosition::value(RV, F)); + return (NonNullAA && NonNullAA->isAssumedNonNull()); }; return Pred; @@ -969,19 +1103,7 @@ /// NonNull attribute for function return value. struct AANonNullReturned final : AANonNullImpl { - AANonNullReturned(Function &F) : AANonNullImpl(F, IRP_RETURNED) {} - - /// See AbstractAttribute::initialize(...). - void initialize(Attributor &A, InformationCache &InfoCache) override { - Function &F = getAnchorScope(); - - // Already nonnull. - if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex, - Attribute::NonNull) || - F.getAttributes().hasAttribute(AttributeList::ReturnIndex, - Attribute::Dereferenceable)) - indicateOptimisticFixpoint(); - } + AANonNullReturned(const IRPosition &IRP) : AANonNullImpl(IRP) {} /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A, InformationCache &InfoCache) override; @@ -1006,14 +1128,7 @@ /// NonNull attribute for function argument. struct AANonNullArgument final : AANonNullImpl { - AANonNullArgument(Argument &A) : AANonNullImpl(A) {} - - /// See AbstractAttriubute::initialize(...). - void initialize(Attributor &A, InformationCache &InfoCache) override { - Argument *Arg = cast(getAssociatedValue()); - if (Arg->hasNonNullAttr()) - indicateOptimisticFixpoint(); - } + AANonNullArgument(const IRPosition &IRP) : AANonNullImpl(IRP) {} /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A, InformationCache &InfoCache) override; @@ -1026,16 +1141,13 @@ /// NonNull attribute for a call site argument. struct AANonNullCallSiteArgument final : AANonNullImpl { - AANonNullCallSiteArgument(Instruction &I, unsigned ArgNo) - : AANonNullImpl(CallSite(&I).getArgOperand(ArgNo), I, ArgNo) {} + AANonNullCallSiteArgument(const IRPosition &IRP) : AANonNullImpl(IRP) {} /// See AbstractAttribute::initialize(...). void initialize(Attributor &A, InformationCache &InfoCache) override { - CallSite CS(&getAnchorValue()); - if (CS.paramHasAttr(getArgNo(), getAttrKind()) || - CS.paramHasAttr(getArgNo(), Attribute::Dereferenceable) || - isKnownNonZero(getAssociatedValue(), - getAnchorScope().getParent()->getDataLayout())) + AANonNullImpl::initialize(A, InfoCache); + if (!isKnownNonNull() && + isKnownNonZero(&getAssociatedValue(), getDataLayout())) indicateOptimisticFixpoint(); } @@ -1057,22 +1169,20 @@ std::function CallSiteCheck = [&](CallSite CS) { assert(CS && "Sanity check: Call site was not initialized properly!"); - auto *NonNullAA = - A.getAAFor(*this, *CS.getInstruction(), ArgNo); + IRPosition CSArgPos = IRPosition::callsite_argument(CS, ArgNo); + if (CSArgPos.hasAttr({Attribute::NonNull, Attribute::Dereferenceable})) + return true; // Check that NonNullAA is AANonNullCallSiteArgument. - if (NonNullAA) { + if (auto *NonNullAA = A.getAAFor(*this, CSArgPos)) { ImmutableCallSite ICS(&NonNullAA->getAnchorValue()); if (ICS && CS.getInstruction() == ICS.getInstruction()) return NonNullAA->isAssumedNonNull(); return false; } - if (CS.paramHasAttr(ArgNo, Attribute::NonNull)) - return true; - Value *V = CS.getArgOperand(ArgNo); - if (isKnownNonZero(V, getAnchorScope().getParent()->getDataLayout())) + if (isKnownNonZero(V, getDataLayout())) return true; return false; @@ -1088,9 +1198,9 @@ // NOTE: Never look at the argument of the callee in this method. // If we do this, "nonnull" is always deduced because of the assumption. - Value &V = *getAssociatedValue(); - - auto *NonNullAA = A.getAAFor(*this, V); + Value &V = getAssociatedValue(); + auto *NonNullAA = + A.getAAFor(*this, IRPosition::value(V, getAnchorScope())); if (!NonNullAA || !NonNullAA->isAssumedNonNull()) return indicatePessimisticFixpoint(); @@ -1101,7 +1211,7 @@ /// ------------------------ Will-Return Attributes ---------------------------- struct AAWillReturnImpl : public AAWillReturn { - IRPositionConstructorForward(AAWillReturnImpl, AAWillReturn); + AAWillReturnImpl(const IRPosition &IRP) : AAWillReturn(IRP) {} /// See AbstractAttribute::getAsStr() const std::string getAsStr() const override { @@ -1110,7 +1220,7 @@ }; struct AAWillReturnFunction final : AAWillReturnImpl { - AAWillReturnFunction(Function &F) : AAWillReturnImpl(F, IRP_FUNCTION) {} + AAWillReturnFunction(const IRPosition &IRP) : AAWillReturnImpl(IRP) {} /// See AbstractAttribute::initialize(...). void initialize(Attributor &A, InformationCache &InfoCache) override; @@ -1164,7 +1274,8 @@ if (ICS.hasFnAttr(Attribute::WillReturn)) return true; - auto *WillReturnAA = A.getAAFor(*this, I); + IRPosition IPos = IRPosition::callsite_function(ICS); + auto *WillReturnAA = A.getAAFor(*this, IPos); if (!WillReturnAA || !WillReturnAA->isAssumedWillReturn()) return false; @@ -1172,7 +1283,7 @@ if (ICS.hasFnAttr(Attribute::NoRecurse)) return true; - auto *NoRecurseAA = A.getAAFor(*this, I); + auto *NoRecurseAA = A.getAAFor(*this, IPos); return NoRecurseAA && NoRecurseAA->isAssumedNoRecurse(); }; @@ -1186,7 +1297,7 @@ /// ------------------------ NoAlias Argument Attribute ------------------------ struct AANoAliasImpl : AANoAlias { - IRPositionConstructorForward(AANoAliasImpl, AANoAlias); + AANoAliasImpl(const IRPosition &IRP) : AANoAlias(IRP) {} const std::string getAsStr() const override { return getAssumed() ? "noalias" : "may-alias"; @@ -1195,7 +1306,7 @@ /// NoAlias attribute for function return value. struct AANoAliasReturned final : AANoAliasImpl { - AANoAliasReturned(Function &F) : AANoAliasImpl(F, IRP_RETURNED) {} + AANoAliasReturned(const IRPosition &IRP) : AANoAliasImpl(IRP) {} /// See AbstractAttriubute::initialize(...). void initialize(Attributor &A, InformationCache &InfoCache) override { @@ -1234,7 +1345,8 @@ return false; if (!ICS.returnDoesNotAlias()) { - auto *NoAliasAA = A.getAAFor(*this, RV); + auto *NoAliasAA = + A.getAAFor(*this, IRPosition::callsite_returned(ICS)); if (!NoAliasAA || !NoAliasAA->isAssumedNoAlias()) return false; } @@ -1258,7 +1370,7 @@ /// -------------------AAIsDead Function Attribute----------------------- struct AAIsDeadImpl : public AAIsDead { - IRPositionConstructorForward(AAIsDeadImpl, AAIsDead); + AAIsDeadImpl(const IRPosition &IRP) : AAIsDead(IRP) {} void initialize(Attributor &A, InformationCache &InfoCache) override { const Function &F = getAnchorScope(); @@ -1317,7 +1429,8 @@ /// and only place an unreachable in the normal successor. if (Invoke2CallAllowed) { if (Function *Callee = II->getCalledFunction()) { - auto *AANoUnw = A.getAAFor(*this, *Callee); + auto *AANoUnw = + A.getAAFor(*this, IRPosition::function(*Callee)); if (Callee->hasFnAttribute(Attribute::NoUnwind) || (AANoUnw && AANoUnw->isAssumedNoUnwind())) { LLVM_DEBUG(dbgs() @@ -1409,7 +1522,7 @@ }; struct AAIsDeadFunction final : public AAIsDeadImpl { - AAIsDeadFunction(Function &F) : AAIsDeadImpl(F, IRP_FUNCTION) {} + AAIsDeadFunction(const IRPosition &IRP) : AAIsDeadImpl(IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { @@ -1452,12 +1565,13 @@ ImmutableCallSite ICS(I); if (ICS) { + const IRPosition &IPos = IRPosition::callsite_function(ICS); // Regarless of the no-return property of an invoke instruction we only // learn that the regular successor is not reachable through this // instruction but the unwind block might still be. if (auto *Invoke = dyn_cast(I)) { // Use nounwind to justify the unwind block is dead as well. - auto *AANoUnw = A.getAAFor(*this, *Invoke); + auto *AANoUnw = A.getAAFor(*this, IPos); if (!Invoke2CallAllowed || (!AANoUnw || !AANoUnw->isAssumedNoUnwind())) { AssumedLiveBlocks.insert(Invoke->getUnwindDest()); @@ -1465,7 +1579,7 @@ } } - auto *NoReturnAA = A.getAAFor(*this, *I); + auto *NoReturnAA = A.getAAFor(*this, IPos); if (ICS.hasFnAttr(Attribute::NoReturn) || (NoReturnAA && NoReturnAA->isAssumedNoReturn())) return I; @@ -1596,7 +1710,7 @@ }; struct AADereferenceableImpl : AADereferenceable, DerefState { - IRPositionConstructorForward(AADereferenceableImpl, AADereferenceable); + AADereferenceableImpl(const IRPosition &IRP) : AADereferenceable(IRP) {} using StateType = DerefState; /// See AbstractAttribute::getState() @@ -1663,13 +1777,11 @@ bool &IsNonNull, bool &IsGlobal); void initialize(Attributor &A, InformationCache &InfoCache) override { - Function &F = getAnchorScope(); - unsigned AttrIdx = getIRPosition().getAttrIdx(); - - for (Attribute::AttrKind AK : - {Attribute::Dereferenceable, Attribute::DereferenceableOrNull}) - if (F.getAttributes().hasAttribute(AttrIdx, AK)) - takeKnownDerefBytesMaximum(F.getAttribute(AttrIdx, AK).getValueAsInt()); + SmallVector Attrs; + getAttrs({Attribute::Dereferenceable, Attribute::DereferenceableOrNull}, + Attrs); + for (const Attribute &Attr : Attrs) + takeKnownDerefBytesMaximum(Attr.getValueAsInt()); } /// See AbstractAttribute::getAsStr(). @@ -1685,8 +1797,8 @@ }; struct AADereferenceableReturned final : AADereferenceableImpl { - AADereferenceableReturned(Function &F) - : AADereferenceableImpl(F, IRP_RETURNED) {} + AADereferenceableReturned(const IRPosition &IRP) + : AADereferenceableImpl(IRP) {} /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A, InformationCache &InfoCache) override; @@ -1711,19 +1823,21 @@ IsGlobal = false; // First, we try to get information about V from Attributor. - if (auto *DerefAA = A.getAAFor(*this, V)) { + if (auto *DerefAA = A.getAAFor( + *this, IRPosition::value(V, getAnchorScope()))) { IsNonNull &= DerefAA->isAssumedNonNull(); return DerefAA->getAssumedDereferenceableBytes(); } // Otherwise, we try to compute assumed bytes from base pointer. - const DataLayout &DL = getAnchorScope().getParent()->getDataLayout(); + const DataLayout &DL = getDataLayout(); unsigned IdxWidth = DL.getIndexSizeInBits(V.getType()->getPointerAddressSpace()); APInt Offset(IdxWidth, 0); Value *Base = V.stripAndAccumulateInBoundsConstantOffsets(DL, Offset); - if (auto *BaseDerefAA = A.getAAFor(*this, *Base)) { + if (auto *BaseDerefAA = A.getAAFor( + *this, IRPosition::value(*Base, getAnchorScope()))) { IsNonNull &= Offset != 0; return calcDifferenceIfBaseIsNonNull( BaseDerefAA->getAssumedDereferenceableBytes(), Offset.getSExtValue(), @@ -1749,7 +1863,7 @@ Function &F = getAnchorScope(); auto BeforeState = static_cast(*this); - syncNonNull(A.getAAFor(*this, F)); + syncNonNull(A.getAAFor(*this, getIRPosition())); bool IsNonNull = isAssumedNonNull(); bool IsGlobal = isAssumedGlobal(); @@ -1770,7 +1884,8 @@ } struct AADereferenceableArgument final : AADereferenceableImpl { - AADereferenceableArgument(Argument &A) : AADereferenceableImpl(A) {} + AADereferenceableArgument(const IRPosition &IRP) + : AADereferenceableImpl(IRP) {} /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A, InformationCache &InfoCache) override; @@ -1791,7 +1906,7 @@ unsigned ArgNo = Arg.getArgNo(); - syncNonNull(A.getAAFor(*this, F, ArgNo)); + syncNonNull(A.getAAFor(*this, getIRPosition())); bool IsNonNull = isAssumedNonNull(); bool IsGlobal = isAssumedGlobal(); @@ -1801,8 +1916,8 @@ assert(CS && "Sanity check: Call site was not initialized properly!"); // Check that DereferenceableAA is AADereferenceableCallSiteArgument. - if (auto *DereferenceableAA = - A.getAAFor(*this, *CS.getInstruction(), ArgNo)) { + if (auto *DereferenceableAA = A.getAAFor( + *this, IRPosition::callsite_argument(CS, ArgNo))) { ImmutableCallSite ICS( &DereferenceableAA->getIRPosition().getAnchorValue()); if (ICS && CS.getInstruction() == ICS.getInstruction()) { @@ -1831,18 +1946,8 @@ /// Dereferenceable attribute for a call site argument. struct AADereferenceableCallSiteArgument final : AADereferenceableImpl { - AADereferenceableCallSiteArgument(Instruction &I, unsigned ArgNo) - : AADereferenceableImpl(CallSite(&I).getArgOperand(ArgNo), I, ArgNo) {} - - /// See AbstractAttribute::initialize(...). - void initialize(Attributor &A, InformationCache &InfoCache) override { - CallSite CS(&getAnchorValue()); - if (CS.paramHasAttr(getArgNo(), Attribute::Dereferenceable)) - takeKnownDerefBytesMaximum(CS.getDereferenceableBytes(getArgNo())); - - if (CS.paramHasAttr(getArgNo(), Attribute::DereferenceableOrNull)) - takeKnownDerefBytesMaximum(CS.getDereferenceableOrNullBytes(getArgNo())); - } + AADereferenceableCallSiteArgument(const IRPosition &IRP) + : AADereferenceableImpl(IRP) {} /// See AbstractAttribute::updateImpl(Attributor &A). ChangeStatus updateImpl(Attributor &A, InformationCache &InfoCache) override; @@ -1860,11 +1965,11 @@ // If we do this, "dereferenceable" is always deduced because of the // assumption. - Value &V = *getAssociatedValue(); + Value &V = getAssociatedValue(); auto BeforeState = static_cast(*this); - syncNonNull(A.getAAFor(*this, getAnchorValue(), getArgNo())); + syncNonNull(A.getAAFor(*this, getIRPosition())); bool IsNonNull = isAssumedNonNull(); bool IsGlobal = isKnownGlobal(); @@ -1879,7 +1984,7 @@ // ------------------------ Align Argument Attribute ------------------------ struct AAAlignImpl : AAAlign { - IRPositionConstructorForward(AAAlignImpl, AAAlign); + AAAlignImpl(const IRPosition &IRP) : AAAlign(IRP) {} // Max alignemnt value allowed in IR static const unsigned MAX_ALIGN = 1U << 29; @@ -1894,13 +1999,10 @@ void initialize(Attributor &A, InformationCache &InfoCache) override { takeAssumedMinimum(MAX_ALIGN); - Function &F = getAnchorScope(); - - unsigned AttrIdx = getAttrIdx(); - // Already the function has align attribute on return value or argument. - if (F.getAttributes().hasAttribute(AttrIdx, Attribute::Alignment)) - addKnownBits( - F.getAttribute(AttrIdx, Attribute::Alignment).getAlignment()); + SmallVector Attrs; + getAttrs({Attribute::Alignment}, Attrs); + for (const Attribute &Attr : Attrs) + takeKnownMaximum(Attr.getValueAsInt()); } /// See AbstractAttribute::getDeducedAttributes @@ -1913,7 +2015,7 @@ /// Align attribute for function return value. struct AAAlignReturned final : AAAlignImpl { - AAAlignReturned(Function &F) : AAAlignImpl(F, IRP_RETURNED) {} + AAAlignReturned(const IRPosition &IRP) : AAAlignImpl(IRP) {} /// See AbstractAttribute::updateImpl(...). ChangeStatus updateImpl(Attributor &A, InformationCache &InfoCache) override; @@ -1936,14 +2038,13 @@ base_t BeforeState = getAssumed(); auto CheckReturnValue = [&](Value &RV, const SmallPtrSetImpl &RetInsts) -> bool { - auto *AlignAA = A.getAAFor(*this, RV); + auto *AlignAA = A.getAAFor(*this, IRPosition::value(RV, F)); if (AlignAA) takeAssumedMinimum(AlignAA->getAssumedAlign()); else // Use IR information. - takeAssumedMinimum(RV.getPointerAlignment( - getAnchorScope().getParent()->getDataLayout())); + takeAssumedMinimum(RV.getPointerAlignment(getDataLayout())); return isValidState(); }; @@ -1957,7 +2058,7 @@ /// Align attribute for function argument. struct AAAlignArgument final : AAAlignImpl { - AAAlignArgument(Argument &A) : AAAlignImpl(A) {} + AAAlignArgument(const IRPosition &IRP) : AAAlignImpl(IRP) {} /// See AbstractAttribute::updateImpl(...). virtual ChangeStatus updateImpl(Attributor &A, @@ -1974,7 +2075,7 @@ Argument &Arg = cast(getAnchorValue()); unsigned ArgNo = Arg.getArgNo(); - const DataLayout &DL = F.getParent()->getDataLayout(); + const DataLayout &DL = getDataLayout(); auto BeforeState = getAssumed(); @@ -1982,7 +2083,8 @@ std::function CallSiteCheck = [&](CallSite CS) { assert(CS && "Sanity check: Call site was not initialized properly!"); - auto *AlignAA = A.getAAFor(*this, *CS.getInstruction(), ArgNo); + auto *AlignAA = + A.getAAFor(*this, IRPosition::callsite_argument(CS, ArgNo)); // Check that AlignAA is AAAlignCallSiteArgument. if (AlignAA) { @@ -2006,14 +2108,11 @@ } struct AAAlignCallSiteArgument final : AAAlignImpl { - AAAlignCallSiteArgument(Instruction &I, unsigned ArgNo) - : AAAlignImpl(CallSite(&I).getArgOperand(ArgNo), I, ArgNo) {} + AAAlignCallSiteArgument(const IRPosition &IRP) : AAAlignImpl(IRP) {} /// See AbstractAttribute::initialize(...). void initialize(Attributor &A, InformationCache &InfoCache) override { - CallSite CS(&getAnchorValue()); - takeKnownMaximum(getAssociatedValue()->getPointerAlignment( - getAnchorScope().getParent()->getDataLayout())); + takeKnownMaximum(getAssociatedValue().getPointerAlignment(getDataLayout())); } /// See AbstractAttribute::updateImpl(Attributor &A). @@ -2032,9 +2131,9 @@ auto BeforeState = getAssumed(); - Value &V = *getAssociatedValue(); - - auto *AlignAA = A.getAAFor(*this, V); + Value &V = getAssociatedValue(); + auto *AlignAA = + A.getAAFor(*this, IRPosition::value(V, getAnchorScope())); if (AlignAA) takeAssumedMinimum(AlignAA->getAssumedAlign()); @@ -2047,7 +2146,7 @@ /// ------------------ Function No-Return Attribute ---------------------------- struct AANoReturnImpl : public AANoReturn { - IRPositionConstructorForward(AANoReturnImpl, AANoReturn); + AANoReturnImpl(const IRPosition &IRP) : AANoReturn(IRP) {} /// See AbstractAttribute::getAsStr(). const std::string getAsStr() const override { @@ -2056,8 +2155,7 @@ /// See AbstractAttribute::initialize(...). void initialize(Attributor &A, InformationCache &InfoCache) override { - Function &F = getAnchorScope(); - if (F.hasFnAttribute(getAttrKind())) + if (hasAttr({getAttrKind()})) indicateOptimisticFixpoint(); } @@ -2074,7 +2172,7 @@ }; struct AANoReturnFunction final : AANoReturnImpl { - AANoReturnFunction(Function &F) : AANoReturnImpl(F, IRP_FUNCTION) {} + AANoReturnFunction(const IRPosition &IRP) : AANoReturnImpl(IRP) {} /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { @@ -2103,9 +2201,10 @@ for (const Use &U : F.uses()) { Instruction *I = cast(U.getUser()); - Function *AnchorValue = I->getParent()->getParent(); + Function *Caller = I->getFunction(); - auto *LivenessAA = getAAFor(QueryingAA, *AnchorValue); + auto *LivenessAA = + getAAFor(QueryingAA, IRPosition::function(*Caller)); // Skip dead calls. if (LivenessAA && LivenessAA->isAssumedDead(I)) @@ -2138,11 +2237,12 @@ &Pred, const AbstractAttribute &QueryingAA) { - auto *AARetVal = getAAFor(QueryingAA, F); + auto *AARetVal = + getAAFor(QueryingAA, IRPosition::returned(F)); if (!AARetVal) return false; - auto *LivenessAA = getAAFor(QueryingAA, F); + auto *LivenessAA = getAAFor(QueryingAA, IRPosition::function(F)); if (!LivenessAA) return AARetVal->checkForAllReturnedValuesAndReturnInsts(Pred); @@ -2164,11 +2264,12 @@ const Function &F, const function_ref &Pred, const AbstractAttribute &QueryingAA) { - auto *AARetVal = getAAFor(QueryingAA, F); + auto *AARetVal = + getAAFor(QueryingAA, IRPosition::returned(F)); if (!AARetVal) return false; - auto *LivenessAA = getAAFor(QueryingAA, F); + auto *LivenessAA = getAAFor(QueryingAA, IRPosition::function(F)); if (!LivenessAA) return AARetVal->checkForAllReturnedValuesAndReturnInsts( [&](Value &RV, const SmallPtrSetImpl &) { @@ -2190,7 +2291,7 @@ const AbstractAttribute &QueryingAA, InformationCache &InfoCache, const ArrayRef &Opcodes) { - auto *LivenessAA = getAAFor(QueryingAA, F); + auto *LivenessAA = getAAFor(QueryingAA, IRPosition::function(F)); auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F); for (unsigned Opcode : Opcodes) { @@ -2211,7 +2312,7 @@ const Function &F, const llvm::function_ref &Pred, AbstractAttribute &QueryingAA, InformationCache &InfoCache) { - auto *LivenessAA = getAAFor(QueryingAA, F); + auto *LivenessAA = getAAFor(QueryingAA, IRPosition::function(F)); for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(F)) { // Skip dead instructions. @@ -2363,84 +2464,83 @@ } /// Helper function that checks if an abstract attribute of type \p AAType -/// should be created for \p V (with argument number \p ArgNo) and if so creates -/// and registers it with the Attributor \p A. +/// should be created for IR position \p IRP and if so creates and registers it +/// with the Attributor \p A. /// /// This method will look at the provided whitelist. If one is given and the /// kind \p AAType::ID is not contained, no abstract attribute is created. /// /// \returns The created abstract argument, or nullptr if none was created. -template -static AAType *checkAndRegisterAA(const Function &F, Attributor &A, - DenseSet *Whitelist, - ValueType &V, int ArgNo, ArgsTy... Args) { +template +static AAType *checkAndRegisterAA(IRPosition &IRP, Attributor &A, + DenseSet *Whitelist) { if (Whitelist && !Whitelist->count(&AAType::ID)) return nullptr; - return &A.registerAA(*new AAType(V, Args...), ArgNo); + return &A.registerAA(*new AAType(IRP)); } void Attributor::identifyDefaultAbstractAttributes( Function &F, InformationCache &InfoCache, DenseSet *Whitelist) { + IRPosition FPos = IRPosition::function(F); + // Check for dead BasicBlocks in every function. // We need dead instruction detection because we do not want to deal with // broken IR in which SSA rules do not apply. - checkAndRegisterAA(F, *this, /* Whitelist */ nullptr, F, - -1); + checkAndRegisterAA(FPos, *this, /* Whitelist */ nullptr); // Every function might be "will-return". - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(FPos, *this, Whitelist); // Every function can be nounwind. - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(FPos, *this, Whitelist); // Every function might be marked "nosync" - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(FPos, *this, Whitelist); // Every function might be "no-free". - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(FPos, *this, Whitelist); // Every function might be "no-return". - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(FPos, *this, Whitelist); // Return attributes are only appropriate if the return type is non void. Type *ReturnType = F.getReturnType(); if (!ReturnType->isVoidTy()) { + IRPosition RetPos = IRPosition::returned(F); // Argument attribute "returned" --- Create only one per function even // though it is an argument attribute. - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(RetPos, *this, Whitelist); if (ReturnType->isPointerTy()) { // Every function with pointer return type might be marked align. - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(RetPos, *this, Whitelist); // Every function with pointer return type might be marked nonnull. - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(RetPos, *this, Whitelist); // Every function with pointer return type might be marked noalias. - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(RetPos, *this, Whitelist); // Every function with pointer return type might be marked // dereferenceable. - checkAndRegisterAA(F, *this, Whitelist, F, -1); + checkAndRegisterAA(RetPos, *this, Whitelist); } } for (Argument &Arg : F.args()) { if (Arg.getType()->isPointerTy()) { + IRPosition ArgPos = IRPosition::argument(Arg); // Every argument with pointer type might be marked nonnull. - checkAndRegisterAA(F, *this, Whitelist, Arg, - Arg.getArgNo()); + checkAndRegisterAA(ArgPos, *this, Whitelist); // Every argument with pointer type might be marked dereferenceable. - checkAndRegisterAA(F, *this, Whitelist, Arg, - Arg.getArgNo()); + checkAndRegisterAA(ArgPos, *this, Whitelist); // Every argument with pointer type might be marked align. - checkAndRegisterAA(F, *this, Whitelist, Arg, - Arg.getArgNo()); + checkAndRegisterAA(ArgPos, *this, Whitelist); } } @@ -2483,18 +2583,18 @@ for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) { if (!CS.getArgument(i)->getType()->isPointerTy()) continue; + IRPosition CSArgPos = IRPosition::callsite_argument(CS, i); // Call site argument attribute "non-null". - checkAndRegisterAA(F, *this, Whitelist, I, i, - i); + checkAndRegisterAA(CSArgPos, *this, + Whitelist); // Call site argument attribute "dereferenceable". - checkAndRegisterAA( - F, *this, Whitelist, I, i, i); + checkAndRegisterAA(CSArgPos, *this, + Whitelist); // Call site argument attribute "align". - checkAndRegisterAA(F, *this, Whitelist, I, i, - i); + checkAndRegisterAA(CSArgPos, *this, Whitelist); } } } @@ -2509,22 +2609,29 @@ raw_ostream &llvm::operator<<(raw_ostream &OS, IRPosition::Kind AP) { switch (AP) { + case IRPosition::IRP_INVALID: + return OS << "inv"; + case IRPosition::IRP_FLOAT: + return OS << "flt"; + case IRPosition::IRP_RETURNED: + return OS << "fn_ret"; + case IRPosition::IRP_CALL_SITE_RETURNED: + return OS << "cs_ret"; + case IRPosition::IRP_FUNCTION: + return OS << "fn"; + case IRPosition::IRP_CALL_SITE: + return OS << "cs"; case IRPosition::IRP_ARGUMENT: return OS << "arg"; case IRPosition::IRP_CALL_SITE_ARGUMENT: return OS << "cs_arg"; - case IRPosition::IRP_FUNCTION: - return OS << "fn"; - case IRPosition::IRP_RETURNED: - return OS << "fn_ret"; } llvm_unreachable("Unknown attribute position!"); } raw_ostream &llvm::operator<<(raw_ostream &OS, const IRPosition &Pos) { - const Value *AV = Pos.getAssociatedValue(); - return OS << "{" << Pos.getPositionKind() << ":" - << (AV ? AV->getName() : "n/a") << " [" + const Value &AV = Pos.getAssociatedValue(); + return OS << "{" << Pos.getPositionKind() << ":" << AV.getName() << " [" << Pos.getAnchorValue().getName() << "@" << Pos.getArgNo() << "]}"; }