Index: include/llvm/Transforms/IPO/FunctionAttrs.h =================================================================== --- include/llvm/Transforms/IPO/FunctionAttrs.h +++ include/llvm/Transforms/IPO/FunctionAttrs.h @@ -22,11 +22,469 @@ namespace llvm { +class AbstractAttribute; +class DominatorTree; +class AbstractState; +class Attributor; class AAResults; +class Statistic; class Function; class Module; class Pass; +namespace { + +struct ReturnedValueInfo { + ReturnedValueInfo(Value *V = nullptr, Instruction *CtxI = nullptr, + const ReturnedValueInfo *RV = nullptr) + : V(V), CtxI(CtxI), RV(RV) {} + Value *V; + Instruction *CtxI; + const ReturnedValueInfo *RV; +}; + +template using GetterTy = std::function; +using AAGetterTy = GetterTy; +using DTGetterTy = GetterTy; +using SCCNodeSet = llvm::SmallSetVector; +using AASetVector = llvm::SmallSetVector; + +template using CallbackTy = std::function; +using ReturnedValueCallbackTy = CallbackTy; +using InstructionCallbackTy = CallbackTy; +using CallSiteCallbackTy = CallbackTy; + +template +using ReturnedValueStateCallbackTy = + CallbackTy; + +template +using CallSiteStateCallbackTy = CallbackTy; + +} // anonymous namespace + + enum Direction { + FORWARD, + BACKWARD, + }; + +/// Base class for all abstract states maintained for potential attributes. +struct AbstractAttribute { + + enum ManifestPosition { + MP_FUNCTION, + MP_RETURNED, + MP_ARGUMENT, + MP_CALL_SITE_ARGUMENT, + MP_CALL_SITE_ARGUMENT_NOT_IR, + MP_INSTRUCTION_METADATA, + }; + + /// An abstract attribute for @p V with an optimistic (=bottom) value. + AbstractAttribute(Value &V) : V(V) {} + + /// Hook for the Attributor to trigger an update of the internal state. + /// If this attribute is already fixed, nothing happens, if it is not, the + /// environment was CHANGED and we have to determine if the current + /// information is still valid or adjust it otherwise. There is no explicit + /// return value but the internal "CHANGED" variable is set accordingly. + bool update(Attributor &A, Direction Dir); + + /// Hook for the Attributor to trigger the manifestation of the information + /// represented by the abstract attribute in the LLVM-IR. + virtual bool manifest(Attributor &A); + + virtual void useKnownAccessInformation(uint64_t Length, const APInt &Offset) { + /* No-Op */ + } + + virtual AbstractState &getState() = 0; + virtual const AbstractState &getState() const = 0; + + virtual bool isImplied(Attributor &A, Direction Dir, bool &Changed); + virtual bool isImpliedBy(AbstractAttribute &AA, Direction Dir, bool &Changed); + + virtual void registerPrecedingAndSucceedingAAs(const AASetVector &AAs, + bool Preceding, + bool Succeeding, + bool StripInbounds = true); + + /// Return the llvm::Value this abstract attribute is anchored with. + /// TODO + ///{ + Value &getAnchoredValue() { return V; } + const Value &getAnchoredValue() const { return V; } + ///} + + /// Return the llvm::Value this abstract attribute is associated with. + ///{ + virtual Value &getAssociatedValue() { return V; } + virtual const Value &getAssociatedValue() const { return V; } + ///} + + virtual Statistic *getStatisticObj() const { return nullptr; } + virtual ManifestPosition getManifestPosition() const = 0; + + /// Helper functions, for debug purposes only. + ///{ + virtual const std::string getAsStr() const = 0; + virtual Attribute::AttrKind getAttrKind() const = 0; + virtual uint64_t getAttrValue() const { return 0; }; + virtual int getArgumentNo() const { return -1; }; + + virtual MDNode *getMetadataNode() const { + llvm_unreachable("No metadata node available!"); + }; + virtual unsigned getMetadataID() const { + llvm_unreachable("No metadata ID available!"); + }; + + virtual void print(raw_ostream &OS) const; + void dump() const { print(dbgs()); } + ///} + + /// The identifier used as a fallback. + static constexpr Attribute::AttrKind ID = Attribute::None; + + friend class Attributor; + +protected: + + /// The actual update/transfer function which has to be implemented by the + /// derived classes. + virtual bool updateImpl(Attributor &A, Direction Dir) = 0; + + /// The llvm::Value this abstract attribute is associated with. + Value &V; + + AASetVector PrecedingAAs, SucceedingAAs; +}; +raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA); +raw_ostream &operator<<(raw_ostream &OS, AbstractAttribute::ManifestPosition); +raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State); + + +/// An abstract interface for all non-null attributes. +struct AANonNull : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AANonNull(Value &V) : AbstractAttribute(V) {} + + /// Return true if the associated value is known to be non-null. + virtual bool isKnownNonNull() const = 0; + + /// Return true if we assume that the underlying value cannot be null. The + /// direction @p Dir decides if we look at the assumed information for forward + /// or backward traversal, or both, either inclusive or exclusive (see enum + /// Direction). + virtual bool isAssumedNonNull() const = 0; + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractState::getAttrKind(). + Attribute::AttrKind getAttrKind() const override { + return ID; + } + + /// See AbstractState::getAsStr(). + virtual const std::string getAsStr() const override { + return isAssumedNonNull() ? "non-null" : "maybe-null"; + } + + ///} + + /// The identifier used by the Attributor for this class of attributes. + static constexpr Attribute::AttrKind ID = Attribute::NonNull; +}; + +/// An abstract interface for all no-alias attributes. +struct AANoAlias : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AANoAlias(Value &V) : AbstractAttribute(V) {} + + /// Return true if we know that the underlying value cannot alias with + /// anything (not based on it) in its respective scope. + virtual bool isKnownNoAlias() const = 0; + + /// Return true if we assume that the underlying value cannot alias with + /// anything (not based on it) in its respective scope. The direction @p Dir + /// decides if we look at the assumed information for forward or backward + /// traversal, or both, either inclusive or exclusive (see enum Direction). + virtual bool isAssumedNoAlias() const = 0; + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractState::getAttrKind(). + Attribute::AttrKind getAttrKind() const override { + return ID; + } + + /// See AbstractState::getAsStr(). + const std::string getAsStr() const override { + return isAssumedNoAlias() ? "no-alias" : "may-alias"; + }; + + ///} + + /// The identifier used by the Attributor for this class of attributes. + static constexpr Attribute::AttrKind ID = Attribute::NoAlias; +}; + +/// An abstract interface for all nocapture attributes. +struct AAMemoryAccessBehavior : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AAMemoryAccessBehavior(Value &V) : AbstractAttribute(V) {} + + /// Return true if we know that the underlying value is not read or accessed + /// in its respective scope. + virtual bool isKnownReadNone() const = 0; + + /// Return true if we assume that the underlying value is not read or accessed + /// in its respective scope. + virtual bool isAssumedReadNone() const = 0; + + /// Return true if we know that the underlying value is not accessed + /// (=written) in its respective scope. + virtual bool isKnownReadOnly() const = 0; + + /// Return true if we assume that the underlying value is not accessed + /// (=written) in its respective scope. + virtual bool isAssumedReadOnly() const = 0; + + /// Return true if we know that the underlying value is not read in its + /// respective scope. + virtual bool isKnownWriteOnly() const = 0; + + /// Return true if we assume that the underlying value is not read in its + /// respective scope. + virtual bool isAssumedWriteOnly() const = 0; + + /// Return true if we know that the underlying value (which has to be a + /// function!) will only read argument memory. + virtual bool isKnownArgMemOnly() const { + llvm_unreachable("isKnownArgMemOnly() is only callable for functions!"); + } + + /// Return true if we assume that the underlying value (which has to be a + /// function!) will only read argument memory. + virtual bool isAssumedArgMemOnly() const { + llvm_unreachable("isAssumedArgMemOnly() is only callable for functions!"); + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractState::getAttrKind(). + Attribute::AttrKind getAttrKind() const override { + return isAssumedReadNone() + ? Attribute::ReadNone + : (isAssumedReadOnly() + ? Attribute::ReadOnly + : (isAssumedWriteOnly() ? Attribute::WriteOnly + : Attribute::None)); + } + + /// See AbstractState::getAsStr(). + const std::string getAsStr() const override { + return isAssumedReadNone() + ? "readnone" + : (isAssumedReadOnly() + ? "readonly" + : (isAssumedWriteOnly() ? "writeonly" + : "may-read/write")); + }; + + ///} + + /// The identifier used by the Attributor for this class of attributes. + static constexpr Attribute::AttrKind ID = Attribute::ReadNone; +}; + +/// An abstract interface for all nocapture attributes. +struct AANoCapture : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AANoCapture(Value &V) : AbstractAttribute(V) {} + + /// Return true if we know that the underlying value is not captured in its + /// respective scope. + virtual bool isKnownNoCapture() const = 0; + + /// Return true if we assume that the underlying value is not captured in its + /// respective scope. + virtual bool isAssumedNoCapture() const = 0; + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractState::getAttrKind(). + Attribute::AttrKind getAttrKind() const override { + return ID; + } + + /// See AbstractState::getAsStr(). + const std::string getAsStr() const override { + return isAssumedNoCapture() ? "not-captured" : "maybe-captured"; + }; + + ///} + + /// The identifier used by the Attributor for this class of attributes. + static constexpr Attribute::AttrKind ID = Attribute::NoCapture; +}; + +/// An abstract interface for all dereferenceable(-or-null) attributes. +struct AADereferenceableOrNull : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AADereferenceableOrNull(Value &V) : AbstractAttribute(V) {} + + /// Return true if the associated value is known to be non-null. + virtual bool isKnownNonNull() const = 0; + + /// Return true if we assume that the underlying value cannot be null. The + /// direction @p Dir decides if we look at the assumed information for forward + /// or backward traversal, or both, either inclusive or exclusive (see enum + /// Direction). + virtual bool isAssumedNonNull() const = 0; + + /// Return the number of bytes that are known to be dereferenceable, if the + /// underlying value is not null, see isAssumedNonNull/isKnownNonNull. + virtual uint64_t getKnownDereferenceableBytes() const = 0; + virtual uint64_t getAssumedDereferenceableBytes() const = 0; + + /// See the AbstractAttribute interface for information. + ///{ + + /// Return the LLVM-IR attribute kind, thus dereferenceable or + /// dereferenceable-or-null, depending on the internal state + /// (see AADereferenceableOrNull::isAssumedNonNull()). + Attribute::AttrKind getAttrKind() const override { + return isAssumedNonNull() + ? Attribute::Dereferenceable + : Attribute::DereferenceableOrNull; + } + + uint64_t getAttrValue() const override { + return getKnownDereferenceableBytes(); + } + + /// Pretty print the attribute similar to the IR representation. + const std::string getAsStr() const override { + return (isAssumedNonNull() ? "dereferenceable(" + : "dereferenceable-or-null(") + + std::to_string(getKnownDereferenceableBytes()) + "-" + + std::to_string(getAssumedDereferenceableBytes()) + ")"; + } + + ///} + + /// The identifier used by the Attributor for this class of attributes. + static constexpr Attribute::AttrKind ID = Attribute::Dereferenceable; +}; + +/// An abstract attribute to determine the returned values of a function. If +/// there is a unique returned value R, the manifest method will: +/// - mark R with the "returned" attribute, if R is an argument. +/// - replace the uses of call sites with R, if R is a constant. +/// Even if there is no unique return value, or it is neither an argument or a +/// constant, the information can be used for further forward propagation. +struct AAReturnedValues : public AbstractAttribute { + + /// See AbstractAttribute::AbstractAttribute(...). + AAReturnedValues(Function &F) : AbstractAttribute(F) {} + + using ReturnedValuesTy = DenseSet; + + /// Iterators to walk through all possibly returned values. + ///{ + using iterator = ReturnedValuesTy::iterator; + virtual iterator begin() = 0; + virtual iterator end() = 0; + ///} + + virtual size_t getNumReturnValues() const =0; + + /// Return the unique value returned by the associated function if one exists. + virtual Value *getUniqueReturnedValue(Attributor &A) const = 0; + + virtual Attribute::AttrKind getAttrKind() const override { + return ID; + } + + /// The identifier used by the Attributor for this class of attributes. + static constexpr Attribute::AttrKind ID = Attribute::Returned; +}; + +struct Attributor { + + Attributor(AAGetterTy &AARGetter, DTGetterTy &DTGetter) + : AARGetter(AARGetter), DTGetter(DTGetter) {} + + bool run(Module &M); + + template + AAType *getAAFor(const Value &V, int ArgNo = -1, + Attribute::AttrKind ID = AAType::ID); + + void registerDependence(AbstractAttribute &From, AbstractAttribute &To); + + AAResults &getAAR(Function &F) { return AARGetter(F); } + const DominatorTree &getDT(Function &F) { return DTGetter(F); } + + bool foreachReturnedValue(Function &F, ReturnedValueCallbackTy &Callback); + + template + bool forwardReturnedValues(StateTy &State, Function &F, + ReturnedValueStateCallbackTy &Callback, + bool LookThroughRecursion = false); + + bool foreachCallSite(Function &F, CallSiteCallbackTy &Callback, + bool RequireAllCallSites = true); + + template + bool forwardCallSiteStates(StateTy &State, Function &F, + CallSiteStateCallbackTy &Callback, + bool RequireAllCallSites = true); + +private: + + using AAVector = SmallVector; + + template + AAType ®isterAA(AAType &AA, AASetVector *LiveAAs = nullptr); + + /// Determine opportunities to derive attributes. + bool identifyAbstractAttributes(Function &F); + + void tryToUseCallSite(CallSite CS, AASetVector &LiveAAs) ; + + void tryToUseInstruction(Instruction &I, AASetVector &LiveAAs); + + bool identifyExistingInformation(Function &F); + + /// TODO + AAGetterTy &AARGetter; + DTGetterTy &DTGetter; + + /// A map that represents the dependence graph between abstract attributes. + /// Each entry relates an abstract attribute A with all the abstract + /// attributes which used the optimistic information of A in the last fix + /// point iteration. + DenseMap AADependenceMap; + + AAVector AAsInSCC; + + /// A map that allows to lookup abstract attributes based on llvm::Values and + /// a Attribute::AttrKind. + using KindToAbstractAttributeMap = DenseMap; + DenseMap, KindToAbstractAttributeMap> AAMap; +}; + /// The three kinds of memory access relevant to 'readonly' and /// 'readnone' attributes. enum MemoryAccessKind { Index: lib/Transforms/IPO/FunctionAttrs.cpp =================================================================== --- lib/Transforms/IPO/FunctionAttrs.cpp +++ lib/Transforms/IPO/FunctionAttrs.cpp @@ -14,6 +14,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/IPO/FunctionAttrs.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" @@ -27,7 +28,10 @@ #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/CallGraphSCCPass.h" #include "llvm/Analysis/CaptureTracking.h" +#include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/Analysis/Loads.h" +#include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" @@ -36,12 +40,15 @@ #include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Metadata.h" +#include "llvm/IR/Operator.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/Type.h" #include "llvm/IR/Use.h" @@ -57,32 +64,73 @@ #include "llvm/Transforms/IPO.h" #include #include -#include -#include +#include using namespace llvm; #define DEBUG_TYPE "functionattrs" -STATISTIC(NumReadNone, "Number of functions marked readnone"); -STATISTIC(NumReadOnly, "Number of functions marked readonly"); -STATISTIC(NumWriteOnly, "Number of functions marked writeonly"); -STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); -STATISTIC(NumReturned, "Number of arguments marked returned"); -STATISTIC(NumReturnedWithCalls, "Number of arguments marked returned with calls"); -STATISTIC(NumReturnedKnownWithCalls, - "Number of returned values identified with call returns"); -STATISTIC(NumReturnedConstantWithCalls, - "Number of returned constant values identified with call returns"); -STATISTIC(NumReturnedKnown, "Number of returned values identified"); -STATISTIC(NumReturnedConstantKnown, - "Number of returned constant values identified"); -STATISTIC(NumReadNoneArg, "Number of arguments marked readnone"); -STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly"); -STATISTIC(NumNoAlias, "Number of function returns marked noalias"); -STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull"); -STATISTIC(NumNoRecurse, "Number of functions marked as norecurse"); -STATISTIC(NumNoUnwind, "Number of functions marked as nounwind"); +STATISTIC(NumReadNone, "Old: Number of functions marked readnone"); +STATISTIC(NumReadOnly, "Old: Number of functions marked readonly"); +STATISTIC(NumWriteOnly, "Old: Number of functions marked writeonly"); +STATISTIC(NumNoCapture, "Old: Number of arguments marked nocapture"); +STATISTIC(NumReturned, "Old: Number of arguments marked returned"); +STATISTIC(NumReadNoneArg, "Old: Number of arguments marked readnone"); +STATISTIC(NumReadOnlyArg, "Old: Number of arguments marked readonly"); +STATISTIC(NumNoAlias, "Old: Number of function returns marked noalias"); +STATISTIC(NumNonNullReturn, "Old: Number of function returns marked nonnull"); +STATISTIC(NumNoRecurse, "Old: Number of functions marked as norecurse"); +STATISTIC(NumNoUnwind, "Old: Number of functions marked as nounwind"); + +STATISTIC(NumSufficientConditionsRegistered, + "Number of sufficient conditions registered"); +STATISTIC(NumMaxIterationsPerLevelReached, + "Number of times max iterations per lvl were reached"); + +STATISTIC(NumFnWithExactDefinition, + "Number of function with exact definitions"); +STATISTIC(NumFnWithoutExactDefinition, + "Number of function without exact definitions"); + +STATISTIC(NumFnReturnNoAlias, + "Number of function return values marked no-alias"); +STATISTIC(NumFnArgumentNoAlias, "Number of function arguments marked no-alias"); + +STATISTIC(NumFnReturntNonNull, + "Number of function return values marked non-null"); +STATISTIC(NumFnArgumentNonNull, "Number of function arguments marked non-null"); +STATISTIC(NumCSArgumentNonNull, + "Number of call site arguments marked non-null"); +STATISTIC(NumLoadMetadataNonNull, "Number of load results marked non-null"); + +STATISTIC(NumFnUniqueReturned, "Number of function with unique return"); +STATISTIC(NumFnArgumentReturned, + "Number of function arguments marked returned"); +STATISTIC(NumFnReturnedConstantsReplaced, + "Number of function returned constants replaced"); + +STATISTIC(NumFnArgumentNoCapture, "Number of function arguments marked no-capture"); + +STATISTIC(NumFnsReadNone, "Number of functions marked read-none"); +STATISTIC(NumFnsReadOnly, "Number of functions marked read-only"); +STATISTIC(NumFnsWriteOnly, "Number of functions marked write-only"); + +STATISTIC(NumArgReadNone, "Number of function arguments marked read-none"); +STATISTIC(NumArgReadOnly, "Number of function arguments marked read-only"); +STATISTIC(NumArgWriteOnly, "Number of function arguments marked write-only"); + +STATISTIC(NumFnReturnDereferenceable, + "Number of function return values marked dereferenceable"); +STATISTIC(NumFnArgumentDereferenceable, + "Number of function arguments marked dereferenceable"); +STATISTIC(NumCSArgumentDereferenceable, + "Number of call site arguments marked dereferenceable"); +STATISTIC(NumFnReturnDereferenceableOrNull, + "Number of function return values marked dereferenceable-or-null"); +STATISTIC(NumFnArgumentDereferenceableOrNull, + "Number of function arguments marked dereferenceable-or-null"); +STATISTIC(NumCSArgumentDereferenceableOrNull, + "Number of call site arguments marked dereferenceable-or-null"); // FIXME: This is disabled by default to avoid exposing security vulnerabilities // in C/C++ code compiled by clang: @@ -96,11 +144,3167 @@ "disable-nounwind-inference", cl::Hidden, cl::desc("Stop inferring nounwind attribute during function-attrs pass")); +static cl::opt MAX_ATTRIBUTOR_ITERATIONS_PER_LVL( + "functionattrs-attributor-iterations-per-lvl", cl::Hidden, + cl::desc( + "Perform at most this many iterations to find a fix point per level."), + cl::init(100)); + namespace { +static const bool CHANGED = true; +static const bool UNCHANGED = false; + +static raw_ostream &operator<<(raw_ostream &OS, const ReturnedValueInfo &RV) { + OS << "RV: " << *RV.V; + if (RV.CtxI) { + OS << " @ " << RV.CtxI; + OS << " @ " << *RV.CtxI; + } + if (RV.RV) + OS << "\n\t-> via " << *RV.RV; + return OS; +} + +template +using StateCache = DenseMap>; + +template +StateTy cachedPointerTraversal(StateCache &Cache, Value *V, + CallbackTy &&CB, ArgsTy &&... args) { + V = V->stripPointerCasts(); + + Optional &CachedResult = Cache[V]; + if (CachedResult.hasValue()) + return CachedResult.getValue(); + CachedResult = StateTy::bot(); + + StateTy Result = StateTy::bot(); + if (auto *PHI = dyn_cast(V)) { + + for (Value *Op : PHI->operands()) + Result.getLowerBound( + cachedPointerTraversal(Cache, Op, CB, std::forward(args)...)); + + } else if (auto *Select = dyn_cast(V)) { + Result = cachedPointerTraversal(Cache, Select->getTrueValue(), CB, + std::forward(args)...); + Result.getLowerBound(cachedPointerTraversal( + Cache, Select->getFalseValue(), CB, std::forward(args)...)); + } else { + Result = CB(V, std::forward(args)...); + } + + Cache[V] = Result; + return Result; +} + +} // end anonymous namespace + +raw_ostream &llvm::operator<<(raw_ostream &OS, + AbstractAttribute::ManifestPosition AP) { + switch (AP) { + case AbstractAttribute::MP_FUNCTION: + return OS << "fnc"; + case AbstractAttribute::MP_RETURNED: + return OS << "ret"; + case AbstractAttribute::MP_ARGUMENT: + return OS << "arg"; + case AbstractAttribute::MP_CALL_SITE_ARGUMENT: + case AbstractAttribute::MP_CALL_SITE_ARGUMENT_NOT_IR: + return OS << "csa"; + case AbstractAttribute::MP_INSTRUCTION_METADATA: + return OS << "imd"; + } + llvm_unreachable("Unknown attribute position!"); +} + +struct llvm::AbstractState { + + virtual void resetAssumed() = 0; + + /// Return if this abstract state is the worst possible. + virtual bool isWorstPossible() const = 0; + + /// Return if this abstract state is the best possible. + virtual bool isBestPossible() const = 0; + + /// Fix this abstract state to the known state, thus eliminate the optimism. + virtual void revertToKnown() = 0; + + /// Return if this abstract state is fixed, thus does not need to be updated + /// if information changes as it cannot change itself. + virtual bool isAtFixpoint() const = 0; + + /// Indicate that the abstract state is at a fixpoint. This will usually make + /// the assumed state the known state and cause "isAtFixpoint()" to be true. + virtual void indicateFixpoint() = 0; + + /// Return true if the state is in a consistent state. Non-consistent states + /// indicate an error in the analysis. + virtual bool isConsistent() const = 0; +}; + +raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &State) { + return OS << (State.isWorstPossible() + ? "top" + : (State.isBestPossible() ? "fix" : "")); +} + +template +struct PairState : public AbstractState { + + PairState() {} + PairState(const StateLeftTy &Left, const StateRightTy &Right) + : Left(Left), Right(Right) {} + + virtual void resetAssumed() override { + Left.resetAssumed(); + Right.resetAssumed(); + } + + /// Return if this abstract state is the worst possible. + virtual bool isWorstPossible() const override { + return Left.isWorstPossible() && Right.isWorstPossible(); + } + + /// Return if this abstract state is the best possible. + virtual bool isBestPossible() const override { + return Left.isBestPossible() && Right.isBestPossible(); + } + + virtual bool isConsistent() const override { + return Left.isConsistent() && Right.isConsistent(); + } + + virtual void getLowerBound(const PairState &Other) { + Left.getLowerBound(Other.Left); + Right.getLowerBound(Other.Right); + assert(isConsistent()); + } + + virtual void getUpperBound(const AbstractState &Other) { + Left.getUpperBound(static_cast(Other).Left); + Right.getUpperBound(static_cast(Other).Right); + } + + virtual bool combine(const AbstractState &Other) { + bool Changed = false; + Changed |= Left.combine(static_cast(Other).Left); + Changed |= Right.combine(static_cast(Other).Right); + return Changed; + } + + virtual bool operator==(const PairState &Other) const { + return Left == Other.Left && Right == Other.Right; + } + virtual bool operator!=(const PairState &Other) const { + return !(*this == Other); + } + + virtual void revertToKnown() override { + Left.revertToKnown(); + Right.revertToKnown(); + } + + virtual bool isAtFixpoint() const override { + return Left.isAtFixpoint() && Right.isAtFixpoint(); + } + virtual void indicateFixpoint() override { + Left.indicateFixpoint(); + Right.indicateFixpoint(); + } + + StateLeftTy Left; + StateRightTy Right; +}; + +template +struct IntegerState : public AbstractState { + + IntegerState() : Known(InitKnown), Assumed(InitAssumed) { + assert(isConsistent()); + } + + IntegerState(BaseTy KnownValue) : IntegerState(KnownValue, InitAssumed) {} + + IntegerState(BaseTy KnownValue, BaseTy AssumedValue) + : Known(KnownValue), Assumed(AssumedValue) { + assert(isConsistent()); + } + + bool isConsistent() const override { return Assumed >= Known; } + + void getLowerBound(const IntegerState &Other) { + Known = std::min(Known, Other.Known); + Assumed = std::min(Assumed, Other.Assumed); + assert(isConsistent()); + } + + void getUpperBound(const IntegerState &Other) { + Assumed = std::max(Assumed, Other.Assumed); + Known = std::max(Known, Other.Known); + Assumed = std::max(Known, Assumed); + assert(isConsistent()); + } + + // virtual bool combine(const AbstractState &Other) override{ + // return combine(static_cast(Other)); + //} + bool combine(const IntegerState &Other) { + auto OldState = *this; + Assumed = std::min(Assumed, Other.Assumed); + Known = std::max(Known, Other.Known); + Assumed = std::max(Known, Assumed); + assert(isConsistent()); + return *this == OldState ? UNCHANGED : CHANGED; + } + + bool operator==(const IntegerState &Other) const { + return Known == Other.Known && Assumed == Other.Assumed; + } + bool operator!=(const IntegerState &Other) const { return !(*this == Other); } + + void resetAssumed() override { + Assumed = InitAssumed; + assert(isConsistent()); + } + + bool isWorstPossible() const override { return Assumed == InitKnown; } + + bool isBestPossible() const override { return Known == InitAssumed; } + + void revertToKnown() override { + Assumed = Known; + assert(isConsistent()); + } + + bool isAtFixpoint() const override { return Assumed == Known; } + + void indicateFixpoint() override { + Known = Assumed; + assert(isConsistent()); + } + + // virtual void mergeKnownState(const AbstractState &State) override { + // Known = std::max(Known, static_cast(State).Known); + //} + + static IntegerState bot() { return IntegerState(InitAssumed, InitAssumed); } + static IntegerState top() { return IntegerState(InitKnown, InitKnown); } + + BaseTy getKnown() const { return Known; } + BaseTy getAssumed() const { return Assumed; } + + void setKnown(BaseTy NewKnown) { + Known = NewKnown; + Assumed = std::max(Assumed, Known); + } + + void setAssumed(BaseTy NewAssumed) { Assumed = NewAssumed; } + +private: + BaseTy Known; + BaseTy Assumed; +}; + +using BooleanState = IntegerState; + +raw_ostream &operator<<(raw_ostream &OS, const BooleanState &State) { + return OS << (State.getKnown() ? "known" + : (State.getAssumed() ? "assumed" : "top")); +} + +template +raw_ostream & +operator<<(raw_ostream &OS, + const IntegerState &State) { + return OS << " {" << State.getKnown() << "-" << State.getAssumed() << "} " + << static_cast(State); +} + +/// Helper to dump abstract attributes into a stream. +raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) { + AA.print(OS); + return OS; +} + +/// Hook for the Attributor to trigger an update of the internal state. +/// If this attribute is already fixed, nothing happens, if it is not, the +/// environment was CHANGED and we have to determine if the current +/// information is still valid or adjust it otherwise. There is no explicit +/// return value but the internal "CHANGED" variable is set accordingly. +bool AbstractAttribute::update(Attributor &A, Direction Dir) { + if (getState().isAtFixpoint()) + return UNCHANGED; + + LLVM_DEBUG(errs() << "RUN updateImpl on: " << *this << "\n"); + + bool Changed = UNCHANGED; + if (isImplied(A, Dir, Changed)) + return Changed; + + Changed = updateImpl(A, Dir); + LLVM_DEBUG(errs() << "[" << Changed << "] updateImpl on: " << *this << "\n"); + + return Changed; +} + +/// Hook for the Attributor to trigger the manifestation of the information +/// represented by the abstract attribute in the LLVM-IR. +bool AbstractAttribute::manifest(Attributor &A) { + if (getState().isWorstPossible()) + return false; + + LLVMContext &Ctx = V.getContext(); + + switch (getManifestPosition()) { + case MP_FUNCTION: { + Function &F = cast(getAnchoredValue()); + if (F.hasFnAttribute(getAttrKind())) { + Attribute Attr = F.getFnAttribute(getAttrKind()); + if (!Attr.isIntAttribute() || Attr.getValueAsInt() >= getAttrValue()) + return false; + } + + F.addFnAttr(Attribute::get(Ctx, getAttrKind(), getAttrValue())); + break; + } + case MP_RETURNED: { + Function &F = cast(getAnchoredValue()); + if (F.hasAttribute(AttributeList::ReturnIndex, getAttrKind())) { + Attribute Attr = + F.getAttribute(AttributeList::ReturnIndex, getAttrKind()); + if (!Attr.isIntAttribute() || Attr.getValueAsInt() >= getAttrValue()) + return false; + } + + F.addAttribute(AttributeList::ReturnIndex, + Attribute::get(Ctx, getAttrKind(), getAttrValue())); + break; + } + case MP_ARGUMENT: { + Argument &A = cast(getAnchoredValue()); + if (A.hasAttribute(getAttrKind())) { + Attribute Attr = A.getParent()->getAttributes().getParamAttr( + getArgumentNo(), getAttrKind()); + if (!Attr.isIntAttribute() || Attr.getValueAsInt() >= getAttrValue()) + return false; + } + + A.addAttr(Attribute::get(Ctx, getAttrKind(), getAttrValue())); + break; + } + case MP_INSTRUCTION_METADATA: { + Instruction &I = cast(getAnchoredValue()); + assert(0 <= getAttrValue() && getAttrValue() <= 1); + if (I.getMetadata(getMetadataID())) + return false; + I.setMetadata(getMetadataID(), getMetadataNode()); + break; + } + case MP_CALL_SITE_ARGUMENT: { + CallSite CS(&getAnchoredValue()); + assert(0 <= getAttrValue() && getAttrValue() <= 1); + bool Changed = true; + if (CS.paramHasAttr(getArgumentNo(), getAttrKind())) { + Attribute Attr = + CS.getAttributes().getParamAttr(getArgumentNo(), getAttrKind()); + if (!Attr.isIntAttribute() || Attr.getValueAsInt() >= getAttrValue()) + Changed = false; + } + + CS.addParamAttr(getArgumentNo(), getAttrKind()); + if (!Changed) + return false; + break; + } + case MP_CALL_SITE_ARGUMENT_NOT_IR: + return false; + break; + } + + // Bookkeeping. + if (auto *Stats = getStatisticObj()) + (*Stats)++; + + return true; +} + +bool AbstractAttribute::isImpliedBy(AbstractAttribute &AA, Direction Dir, + bool &Changed) { + assert(AA.getAttrKind() == getAttrKind()); + + const BooleanState &OtherState = + static_cast(AA.getState()); + static_cast(getState()).setKnown(OtherState.getKnown()); + + if (!getState().isBestPossible()) + return false; + + Changed = true; + return true; +} + +bool AbstractAttribute::isImplied(Attributor &A, Direction Dir, bool &Changed) { + + AASetVector &AAs = Dir == FORWARD ? PrecedingAAs : SucceedingAAs; + // errs() << "isImplied check with " << AAs.size() << " AAs!\n"; + + if (AAs.empty()) + return false; + + LLVM_DEBUG(dbgs() << "Check if one of the " << AAs.size() + << (Dir == FORWARD ? "preceding" : "succeeding") + << " AAs imply this one!\n"); + + for (AbstractAttribute *AA : AAs) { + LLVM_DEBUG(dbgs() << " -- Check " << *AA << "\n"); + if (isImpliedBy(*AA, Dir, Changed)) + return true; + } + + LLVM_DEBUG(dbgs() << " -- Failed to find implying AA!\n"); + return false; +} + +void AbstractAttribute::registerPrecedingAndSucceedingAAs( + const AASetVector &AAs, bool Preceding, bool Succeeding, + bool StripInbounds) { + + assert(Preceding | Succeeding); + + if (AAs.empty()) + return; + + // errs() << "rPredAAs [" << AAs.size() << "]: for " << *this << "\n"; + + Value *BasePtr = &getAssociatedValue(); + // errs() << *BasePtr << ":"; + if (StripInbounds) + BasePtr = BasePtr->stripInBoundsOffsets(); + // errs() << *BasePtr << "\n"; + + const auto &Range = make_range(AAs.rbegin(), AAs.rend()); + for (AbstractAttribute *AA : Range) { + if (AA->getAttrKind() != getAttrKind()) + continue; + + Value *AABasePtr = &AA->getAssociatedValue(); + // errs() << *AABasePtr << ":"; + + if (StripInbounds) + AABasePtr = AABasePtr->stripInBoundsOffsets(); + + // errs() << *AABasePtr << "\n"; + if (BasePtr != AABasePtr) + continue; + + if (Preceding) + this->PrecedingAAs.insert(AA); + + if (Succeeding) + AA->SucceedingAAs.insert(this); + } +} + +void AbstractAttribute::print(raw_ostream &OS) const { + const AbstractState &State = getState(); + if (isa(V)) + OS << "[" << getManifestPosition() + << (getArgumentNo() >= 0 ? "(" + std::to_string(getArgumentNo()) + ")" + : "") + << "][" << getAsStr() << "=" << getState() << "][" << V.getName() << "]"; + else + OS << "[" << getManifestPosition() + << (getArgumentNo() >= 0 ? "(" + std::to_string(getArgumentNo()) + ")" + : "") + << "][" << getAsStr() << "=" << getState() << "][" << V << "]"; +} + +/// ------------------------ No-Null Attributes ------------------------------- + +/// A class to hold the state of for non-null attributes. +struct AANonNullImpl : public AANonNull { + + /// Constructor that takes the value this attribute is anchored with (@p V), + /// the address space of the associated value, as well as the function this + /// attribute is related to. + AANonNullImpl(Value &V, unsigned AddrSpace, Function &F); + + /// Return true if the associated value is known to be non-null. + bool isKnownNonNull() const override { return State.getKnown(); } + + /// Return true if we assume that the underlying value cannot be null. + bool isAssumedNonNull() const override { return State.getAssumed(); } + + /// See the AbstractAttribute interface for information. + ///{ + + virtual bool isImpliedBy(AbstractAttribute &OtherAA, Direction Dir, + bool &Changed) override; + + /// See AbstractAttribute::useKnownAccessInformation(...). + virtual void useKnownAccessInformation(uint64_t Length, + const APInt &Offset) override; + + /// See AbstractState::getState(). + ///{ + virtual AbstractState &getState() override { return State; } + virtual const AbstractState &getState() const override { return State; } + ///} + + ///} + + /// Encapsulate the name of the underlying abstract state. + using NonNullStateTy = BooleanState; + + /// Check the value @p V for non-nullness and update the internal state + /// (IsAssumedNonNull. + NonNullStateTy + checkValueForNonNullness(Value *V, Attributor &A, Direction Dir, + Instruction *CtxI, + DenseMap> &Cache); + + /// TODO + static NonNullStateTy checkExactValueForNonNullness(Value *V, Attributor &A, + Direction Dir, + Instruction *CtxI, + Function &F); + +protected: + /// The function associated with this abstract state. + Function &F; + + /// Flag that indicates if, for the underlying value, nullptr is inaccessible. + const bool NullPtrIsUndefined; + + /// The underlying abstract state for all AANonNullImpl classes. + NonNullStateTy State; +}; + +AANonNullImpl::AANonNullImpl(Value &V, unsigned AddrSpace, Function &F) + : AANonNull(V), F(F), + NullPtrIsUndefined(!NullPointerIsDefined(&F, AddrSpace)) {} + +void AANonNullImpl::useKnownAccessInformation(uint64_t Length, + const APInt &Offset) { + if (isKnownNonNull() || !Length || !NullPtrIsUndefined) + return; + + State.setKnown(true); + assert(State.isAtFixpoint()); +} + +#if 0 +bool AANonNullImpl::checkDerefOrNullAA(Attributor &A, Direction Dir) { + assert(!isKnownNonNull()); + + // As long as the AADereferenceableOrNull assumes the associated value is + // non-null, we do not have to analyze anything. If that attribute knows it is + // non-null, we can copy that information and found a fix point. + auto *DerefOrNullAA = + A.getAAFor(getAnchoredValue(), getArgumentNo()); + //errs() << "DerefOrNullAA for " << *this << "\n--> " << DerefOrNullAA << "\n"; + //if (DerefOrNullAA) + //errs() << "--> " << *DerefOrNullAA + //<< " :: " << DerefOrNullAA->isAssumedNonNull() << "\n"; + if (!DerefOrNullAA || !DerefOrNullAA->isAssumedNonNull()) + return false; + + if (DerefOrNullAA->isKnownNonNull()) { + State.setKnown(true); + assert(State.isAtFixpoint()); + } else { + // addUsedAA(*DerefOrNullAA); + } + + return true; +} +#endif + +AANonNullImpl::NonNullStateTy AANonNullImpl::checkValueForNonNullness( + Value *V, Attributor &A, Direction Dir, Instruction *CtxI, + DenseMap> &Cache) { + + NonNullStateTy Result = cachedPointerTraversal( + Cache, V, checkExactValueForNonNullness, A, Dir, CtxI, F); + + // TODO: This should not be needed as a similar check is performed in the + // isKnownNonZero call below. However, there we only look through + // in-bounds GEPs. Because looking through all GEPs was the default + // implementation for non-null interference for a while now, this code + // is put in place to avoid regressions. + if (const auto *GEP = dyn_cast(V)) { + if (!Result.getKnown()) + Result.getUpperBound( + checkValueForNonNullness(GEP->getOperand(0), A, Dir, CtxI, Cache)); + } + + return Result; +} + +AANonNullImpl::NonNullStateTy AANonNullImpl::checkExactValueForNonNullness( + Value *V, Attributor &A, Direction Dir, Instruction *CtxI, Function &F) { + + { + auto *NonNullAA = A.getAAFor(*V); + if (NonNullAA && NonNullAA->isAssumedNonNull()) + return NonNullAA->State; + } + + const DominatorTree &DT = A.getDT(F); + const DataLayout &DL = F.getParent()->getDataLayout(); + if (isKnownNonZero(V, DL, 0, nullptr, CtxI, &DT)) + return NonNullStateTy::bot(); + + if (V->getType()->isPointerTy()) { + + bool isKnownNonNull = false; + if (V->getPointerDereferenceableBytes(DL, isKnownNonNull)) + if (isKnownNonNull) + return NonNullStateTy::bot(); + + if (!NullPointerIsDefined(&F, V->getType()->getPointerAddressSpace()) && + isDereferenceablePointer(V, DL)) + return NonNullStateTy::bot(); + } + + return NonNullStateTy::top(); +} + +bool AANonNullImpl::isImpliedBy(AbstractAttribute &OtherAA, Direction Dir, + bool &Changed) { + Attribute::AttrKind OtherKind = OtherAA.getAttrKind(); + + if (OtherKind == getAttrKind()) + return AbstractAttribute::isImpliedBy(OtherAA, Dir, Changed); + + assert(OtherKind == Attribute::Dereferenceable || + OtherKind == Attribute::DereferenceableOrNull); + + auto &OtherDerefOrNullAA = static_cast(OtherAA); + State.setKnown(OtherDerefOrNullAA.isKnownNonNull()); + + if (!isKnownNonNull()) + return false; + + Changed = true; + return true; +} + +/// ------------------------ No-Null Arguments -------------------------------- + +/// An AA to represent the non-null argument attribute. +struct AANonNullArgument final : public AANonNullImpl { + + /// See AANonNullImpl::AANonNullImpl(...). + AANonNullArgument(Argument &Arg) + : AANonNullImpl(Arg, Arg.getType()->getPointerAddressSpace(), + *Arg.getParent()) { + + // Determine if the IR already provides enough information. + if (Arg.hasNonNullAttr()) { + State.setKnown(true); + assert(State.isAtFixpoint()); + } + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AbstractAttribute::getArgumentNo(). + virtual int getArgumentNo() const override { + return cast(getAnchoredValue()).getArgNo(); + } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_ARGUMENT; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return &NumFnArgumentNonNull; + } + + ///} +}; + +bool AANonNullArgument::updateImpl(Attributor &A, Direction Dir) { + if (Dir == BACKWARD) { + State.revertToKnown(); + return CHANGED; + } + + Argument &Arg = cast(getAnchoredValue()); + + const DataLayout &DL = F.getParent()->getDataLayout(); + unsigned ArgNo = Arg.getArgNo(); + SmallPtrSet Visited; + + bool AllCallSitesAreKnownNonNull = true; + + // Callback function + CallSiteCallbackTy CallSiteCheck = [&](CallSite CS) { + assert(CS && "Sanity check: Call site was not initialized properly!"); + + if (CS.paramHasAttr(ArgNo, Attribute::NonNull)) + return true; + + AANonNull *NonNullCSArgAA = + A.getAAFor(*CS.getInstruction(), getArgumentNo()); + if (!NonNullCSArgAA || !NonNullCSArgAA->isAssumedNonNull()) + return false; + + if (!NonNullCSArgAA->isKnownNonNull()) + AllCallSitesAreKnownNonNull = false; + + return true; + }; + + // If no abstract argument was found look at the call sites. + if (A.foreachCallSite(F, CallSiteCheck)) { + if (AllCallSitesAreKnownNonNull) + State.indicateFixpoint(); + + return UNCHANGED; + } + + State.revertToKnown(); + return CHANGED; +} + +/// ------------------- No-Null Call Site Arguments ---------------------------- + +/// An AA to represent the non-null attribute for a call site argument. +struct AANonNullCallSiteArgument final : public AANonNullImpl { + + /// See AANonNullImpl::AANonNullImpl(...). + AANonNullCallSiteArgument(CallSite CS, unsigned ArgNo) + : AANonNullImpl( + *CS.getInstruction(), + CS.getArgOperand(ArgNo)->getType()->getPointerAddressSpace(), + *CS.getCaller()), + ArgNo(ArgNo) { + + // Determine if the IR already provides enough information. + if (CS.paramHasAttr(ArgNo, getAttrKind())) + State.indicateFixpoint(); + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AbstractAttribute::getArgumentNo(). + virtual int getArgumentNo() const override { return ArgNo; } + + /// See AbstractAttribute::getAssociatedValue(). + ///{ + Value &getAssociatedValue() override { + return *CallSite(&getAnchoredValue()).getArgOperand(getArgumentNo()); + } + const Value &getAssociatedValue() const override { + return *ImmutableCallSite(&getAnchoredValue()) + .getArgOperand(getArgumentNo()); + } + ///} + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_CALL_SITE_ARGUMENT; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return &NumCSArgumentNonNull; + } + + ///} + +private: + /// The underlying value is the argument at position "ArgNo" of the call site + /// that is used as the underyling anchor. See + /// AbstractAttribute::getAssociatedValue(). + const unsigned ArgNo; +}; + +bool AANonNullCallSiteArgument::updateImpl(Attributor &A, Direction Dir) { + CallSite CS(&getAnchoredValue()); + Value *V = CS.getArgOperand(getArgumentNo()); + + if (Dir == BACKWARD) { + Function *Callee = CS.getCalledFunction(); + assert(Callee && Callee->arg_size() > getArgumentNo()); + + Argument *FnArg = Callee->arg_begin() + getArgumentNo(); + auto *NonNullFnArgAA = A.getAAFor(*FnArg); + + if (NonNullFnArgAA && NonNullFnArgAA->isAssumedNonNull()) { + State.setKnown(NonNullFnArgAA->isKnownNonNull()); + // errs() << "<- backward from arg: " << *NonNullFnArgAA << "\n"; + return /* Changed */ State.getKnown(); + } + State.revertToKnown(); + return CHANGED; + } + + Instruction *CSInst = CS.getInstruction(); + DenseMap> Cache; + NonNullStateTy ValState = checkValueForNonNullness(V, A, Dir, CSInst, Cache); + // errs() << "dir: " << Dir << " checkValueForNonNullness: " << ValState << + // "\n"; + + if (ValState == State) + return UNCHANGED; + + State = ValState; + return CHANGED; +} + +/// ----------------------- No-Null Load Results ------------------------------- + +/// An AA to represent the non-null metadata for a memory instruction. +struct AANonNullLoadResult final : public AANonNullImpl { + + /// See AANonNullImpl::AANonNullImpl(...). + AANonNullLoadResult(LoadInst &I) + : AANonNullImpl(I, I.getType()->getPointerAddressSpace(), + *I.getFunction()) { + + // Determine if the IR already provides enough information. + if (I.getMetadata(getMetadataID())) + State.indicateFixpoint(); + } + + virtual MDNode *getMetadataNode() const override { + return MDNode::get(getAnchoredValue().getContext(), {}); + } + virtual unsigned getMetadataID() const override { + return LLVMContext::MD_nonnull; + } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_INSTRUCTION_METADATA; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return &NumLoadMetadataNonNull; + } + +private: + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; +}; + +bool AANonNullLoadResult::updateImpl(Attributor &A, Direction Dir) { + // LoadInst &Load = cast(getAnchoredValue()); + + State.revertToKnown(); + return CHANGED; +} + +/// ---------------------- No-Null Return Values ------------------------------ + +/// An AA to represent the non-null function return attribute. +struct AANonNullReturned final : public AANonNullImpl { + + /// See AANonNullImpl::AANonNullImpl(...). + AANonNullReturned(Function &F) + : AANonNullImpl(F, F.getReturnType()->getPointerAddressSpace(), F) { + + // Determine if the IR already provides enough information. + if (F.hasAttribute(AttributeList::ReturnIndex, getAttrKind())) + State.indicateFixpoint(); + } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_RETURNED; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return &NumFnReturntNonNull; + } + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; +}; + +bool AANonNullReturned::updateImpl(Attributor &A, Direction Dir) { + if (Dir == FORWARD) { + // Check all values returned by this function. + DenseMap> Cache; + ReturnedValueStateCallbackTy RVCallback = + [&](const ReturnedValueInfo *RVPtr) { + return checkValueForNonNullness(RVPtr->V, A, Dir, RVPtr->CtxI, Cache); + }; + return A.forwardReturnedValues(State, F, RVCallback); + } + + State.revertToKnown(); + return CHANGED; +} + +/// ------------------------ No-Alias Attributes ------------------------------ + +/// A compound class for all no-alias attributes. +struct AANoAliasImpl : public AANoAlias { + + /// See AbstractAttribute::AbstractAttribute(...). + AANoAliasImpl(Value &V) : AANoAlias(V) {} + + /// Return true if we know that the underlying value cannot alias with + /// anything (not based on it) in its respective scope. + bool isKnownNoAlias() const override { return State.getKnown(); } + + /// Return true if we assume that the underlying value cannot alias with + /// anything (not based on it) in its respective scope. The direction @p Dir + /// decides if we look at the assumed information for forward or backward + /// traversal, or both, either inclusive or exclusive (see enum Direction). + bool isAssumedNoAlias() const override { return State.getAssumed(); } + + /// See AbstractState::getState(). + ///{ + AbstractState &getState() override { return State; } + const AbstractState &getState() const override { return State; } + ///} + +protected: + /// Encapsulate the name of the underlying abstract state. + using NoAliasStateTy = BooleanState; + using NoAliasStateCache = StateCache; + + /// General helper function to determine if @p V is alias free in the + /// respective scope with regards to the deduction direction @p Dir. + NoAliasStateTy computeNoAliasState(Attributor &A, Value *V, Direction Dir, + NoAliasStateCache &Cache); + + static NoAliasStateTy computeNoAliasStateForExactValue(Value *V, + Attributor &A); + + /// The underlying abstract state for all AANoAliasImpl classes. + NoAliasStateTy State; +}; + +AANoAliasImpl::NoAliasStateTy +AANoAliasImpl::computeNoAliasState(Attributor &A, Value *V, Direction Dir, + NoAliasStateCache &Cache) { + if (Dir == BACKWARD) + return NoAliasStateTy::top(); + + return cachedPointerTraversal(Cache, V, computeNoAliasStateForExactValue, A); +} + +AANoAliasImpl::NoAliasStateTy +AANoAliasImpl::computeNoAliasStateForExactValue(Value *V, Attributor &A) { + + if (auto *C = dyn_cast(V)) { + if (C->isZeroValue() || isa(V)) + return NoAliasStateTy::bot(); + return NoAliasStateTy::top(); + } + + if (isa(V)) + return NoAliasStateTy::top(); + + // TODO: Use AANoCapture attributes. + if (PointerMayBeCaptured(V, /* ReturnCaptures */ false, + /* StoreCaptures */ true)) + return NoAliasStateTy::top(); + + auto *NoAliasAA = A.getAAFor(*V); + if (NoAliasAA && NoAliasAA->isAssumedNoAlias()) { + if (!NoAliasAA->isKnownNoAlias()) + /* register dependence */; + return NoAliasAA->State; + } + + if (isNoAliasFn(V, /* TLI */ nullptr, /* LookThroughBitcasts */ true)) + return NoAliasStateTy::bot(); + + return NoAliasStateTy::top(); +} + +/// ------------------------ No-Alias Arguments ------------------------------- + +/// An AA to represent the no-alias function return attribute. +struct AANoAliasArgument final : public AANoAliasImpl { + + /// See AANoAliasImpl::AANoAliasImpl(...). + AANoAliasArgument(Argument &Arg) : AANoAliasImpl(Arg) { + + // Determine if the IR already provides enough information. + if (Arg.hasAttribute(Attribute::NoAlias)) + State.indicateFixpoint(); + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AbstractAttribute::getArgumentNo(). + virtual int getArgumentNo() const override { + return cast(getAnchoredValue()).getArgNo(); + } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_ARGUMENT; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return &NumFnArgumentNoAlias; + } + + ///} +}; + +bool AANoAliasArgument::updateImpl(Attributor &A, Direction Dir) { + if (Dir == BACKWARD) { + State.revertToKnown(); + return CHANGED; + } + + Argument &Arg = cast(getAnchoredValue()); + Function &F = *Arg.getParent(); + bool IsArgMemOnlyFn = + F.hasFnAttribute(Attribute::ArgMemOnly) || + F.hasFnAttribute(Attribute::InaccessibleMemOrArgMemOnly); + + // Callback function + CallSiteCallbackTy CallSiteCheck = [&](CallSite CS) { + assert(CS && "Sanity check: Call site was not initialized properly!"); + Function &CSFn = *CS.getCaller(); + + Value *V = CS.getArgOperand(Arg.getArgNo()); + V = V->stripInBoundsOffsets(); + + if (isa(V)) { + LLVM_DEBUG(errs() << "no-alias failed maybe captured (global!): " << *V + << " in " << CSFn.getName() << "\n"); + return false; + } + + auto *NoAliasAA = A.getAAFor(*V); + bool VisNoAlias = NoAliasAA && NoAliasAA->isAssumedNoAlias(); + + if (!IsArgMemOnlyFn && !VisNoAlias && !isIdentifiedFunctionLocal(V)) { + LLVM_DEBUG(errs() << "no-alias failed non-func-loc: " << *V << " in " + << CSFn.getName() << "\n"); + return false; + } + + const DominatorTree &DT = A.getDT(CSFn); + Instruction *CSInst = CS.getInstruction(); + if (PointerMayBeCapturedBefore(V, /* ReturnCaptures */ false, + /* StoreCaptures */ true, CSInst, &DT)) { + LLVM_DEBUG(errs() << "no-alias failed maybe captured: " << *V << " in " + << CSFn.getName() << "\n"); + return false; + } + + AAResults &AAR = A.getAAR(CSFn); + for (Use &U : CS.args()) { + if (CS.getArgumentNo(&U) == Arg.getArgNo()) + continue; + Value *ArgOp = U->stripInBoundsOffsets(); + if (!AAR.alias(MemoryLocation(ArgOp), MemoryLocation(V))) + continue; + LLVM_DEBUG(errs() << "May alias: " << *U.get() << " : " << *V << " in " + << CSFn.getName() << "\n"); + return false; + } + + if (VisNoAlias) + LLVM_DEBUG(errs() << "CS in " << CSFn.getName() << " is OK of " << Arg + << "\n"); + return true; + }; + + if (A.foreachCallSite(F, CallSiteCheck)) + return UNCHANGED; + + State.revertToKnown(); + return CHANGED; +} + +/// -------- Memory Behavior Attributes (write/read-only/none) ---------------- + +/// A class to hold the state of for memory behaviour attributes. +struct AAMemoryAccessBehaviorImpl : public AAMemoryAccessBehavior { + + AAMemoryAccessBehaviorImpl(Value &V) : AAMemoryAccessBehavior(V) { + } + + /// See AAMemoryAccessBehavior::isKnownReadNone(); + bool isKnownReadNone() const override { + return getNoReadState().getKnown() && getNoWriteState().getKnown(); + } + + /// See AAMemoryAccessBehavior::isAssumedReadNone(); + bool isAssumedReadNone() const override { + return getNoReadState().getAssumed() && getNoWriteState().getAssumed(); + } + + /// See AAMemoryAccessBehavior::isKnownReadOnly(); + bool isKnownReadOnly() const override { + return getNoWriteState().getKnown(); + } + + /// See AAMemoryAccessBehavior::isAssumedReadOnly(); + bool isAssumedReadOnly() const override { + return getNoWriteState().getAssumed(); + } + + /// See AAMemoryAccessBehavior::isKnownWriteOnly(); + bool isKnownWriteOnly() const override { + return getNoReadState().getKnown(); + } + + /// See AAMemoryAccessBehavior::isAssumedWriteOnly(); + bool isAssumedWriteOnly() const override { + return getNoReadState().getAssumed(); + } + + /// See AbstractAttribute::getState() + ///{ + AbstractState &getState() override { return State; } + const AbstractState &getState() const override { return State; } + ///} + + // TODO!! Add may-read/write + /// See AbstractAttribute::useKnownAccessInformation(...). + //virtual void useKnownAccessInformation(uint64_t Length, + //const APInt &Offset) override; + BooleanState &getNoReadState() { return State.Left; } + const BooleanState &getNoReadState() const { return State.Left; } + BooleanState &getNoWriteState() { return State.Right; } + const BooleanState &getNoWriteState() const { return State.Right; } + +protected: + + using StateTy = PairState; + StateTy State; +}; + +/// An AA to represent the memory behavior function attributes. +struct AAFunctionMemoryBehavior final : public AAMemoryAccessBehaviorImpl { + + /// See AAMemoryAccessBehaviorImpl::AAMemoryAccessBehaviorImpl(...). + AAFunctionMemoryBehavior(Function &F, AAResults &AAR) + : AAMemoryAccessBehaviorImpl(F), AAR(AAR), + State(*this, AAMemoryAccessBehaviorImpl::getState()) { + + auto ModRef = AAR.getModRefBehavior(&F); + if (AAResults::onlyReadsMemory(ModRef)) + getNoWriteState().setKnown(true); + if (AAResults::doesNotReadMemory(ModRef)) + getNoReadState().setKnown(true); + + if (AAResults::onlyAccessesArgPointees(ModRef)) + State.ArgMemOnly.setKnown(true); + } + + void addMemoryAccessInst(Instruction &I) { + CallSite CS(&I); + if (CS) + State.AllCalls.push_back(&I); + else + State.AllMemInst.push_back(&I); + categorize(I); + } + + /// See AAMemoryAccessBehavior::isKnownReadNone(); + bool isKnownReadNone() const override { + return State.UnknownCalls.empty() && AAMemoryAccessBehaviorImpl::isKnownReadNone(); + } + + /// See AAMemoryAccessBehavior::isKnownReadOnly(); + bool isKnownReadOnly() const override { + return State.UnknownCalls.empty() && AAMemoryAccessBehaviorImpl::isKnownReadOnly(); + } + + /// See AAMemoryAccessBehavior::isKnownWriteOnly(); + bool isKnownWriteOnly() const override { + return State.UnknownCalls.empty() && AAMemoryAccessBehaviorImpl::isKnownWriteOnly(); + } + + virtual bool isKnownArgMemOnly() const override { + return State.UnknownCalls.empty() && State.ArgMemOnly.getKnown(); + } + + virtual bool isAssumedArgMemOnly() const override { + return State.ArgMemOnly.getAssumed(); + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + virtual bool manifest(Attributor &A) override; + + /// See AbstractAttribute::getState() + ///{ + AbstractState &getState() override { return State; } + const AbstractState &getState() const override { return State; } + ///} + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_FUNCTION; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return isAssumedReadNone() + ? &NumFnsReadNone + : (isAssumedReadOnly() + ? &NumFnsReadOnly + : (isAssumedWriteOnly() ? &NumFnsWriteOnly : nullptr)); + } + + ///} + +protected: + + struct MemoryBehaviorState : public AbstractState { + + MemoryBehaviorState(AAFunctionMemoryBehavior &MemAccBehImpl, AbstractState &Parent) + : MemAccBehImpl(MemAccBehImpl), Parent(Parent) {} + + void resetAssumed() override { + Parent.resetAssumed(); + ArgMemOnly.resetAssumed(); + + UnknownCalls = AllCalls; + for (Instruction *MemInst : AllMemInst) + MemAccBehImpl.categorize(*MemInst); + } + + bool isWorstPossible() const override { + return Parent.isWorstPossible() && ArgMemOnly.isWorstPossible(); + } + + bool isBestPossible() const override { + return Parent.isBestPossible() && ArgMemOnly.isBestPossible() && + UnknownCalls.empty(); + } + + void revertToKnown() override { + Parent.revertToKnown(); + ArgMemOnly.revertToKnown(); + UnknownCalls.clear(); + } + + bool isAtFixpoint() const override { + return Parent.isAtFixpoint() && ArgMemOnly.isAtFixpoint() && + UnknownCalls.empty(); + } + + void indicateFixpoint() override { + Parent.indicateFixpoint(); + ArgMemOnly.indicateFixpoint(); + UnknownCalls.clear(); + } + + bool isConsistent() const override { + return Parent.isConsistent() && ArgMemOnly.isConsistent(); + } + + AAFunctionMemoryBehavior &MemAccBehImpl; + AbstractState &Parent; + + BooleanState ArgMemOnly; + + SmallVector AllCalls; + SmallVector AllMemInst; + SmallVector UnknownCalls; + }; + + friend class MemoryBehaviorState; + + bool isIgnoredLocation(const MemoryLocation &Loc); + void categorize(Instruction &I); + + AAResults &AAR; + + using StateTy = MemoryBehaviorState; + StateTy State; +}; + +bool AAFunctionMemoryBehavior::isIgnoredLocation(const MemoryLocation &Loc) { + if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) { + errs() << *Loc.Ptr << " + [0:" << Loc.Size << "] is ignored!\n"; + return true; + } + + return false; +} + +void AAFunctionMemoryBehavior::categorize(Instruction &I) { + CallSite CS(&I); + if (CS) { + State.UnknownCalls.push_back(&I); + return; + } + + Value *Ptr = nullptr; + if (auto *LI = dyn_cast(&I)) { + Ptr = LI->getPointerOperand()->stripInBoundsOffsets(); + // Ignore non-volatile loads from local memory. (Atomic is okay here.) + if (!LI->isVolatile() && isIgnoredLocation(MemoryLocation(Ptr))) + return; + } else if (auto *SI = dyn_cast(&I)) { + Ptr = SI->getPointerOperand()->stripInBoundsOffsets(); + // Ignore non-volatile stores to local memory. (Atomic is okay here.) + if (!SI->isVolatile() && isIgnoredLocation(MemoryLocation(Ptr))) + return; + } else if (auto *VI = dyn_cast(&I)) { + Ptr = VI->getPointerOperand()->stripInBoundsOffsets(); + // Ignore vaargs on local memory. + if (isIgnoredLocation(MemoryLocation(Ptr))) + return; + } + + if (!Ptr || !isa(Ptr)) + State.ArgMemOnly.revertToKnown(); + + errs() << "I: " << I << "\n"; + if (Ptr) + errs() << " PTr " << *Ptr <<"\n"; + errs() << I.mayReadFromMemory() << " : " << I.mayWriteToMemory() << "\n"; + + if (I.mayReadFromMemory()) + getNoReadState().revertToKnown(); + if (I.mayWriteToMemory()) + getNoWriteState().revertToKnown(); +} + +bool AAFunctionMemoryBehavior::updateImpl(Attributor &A, Direction Dir) { + if (Dir == FORWARD){ + State.revertToKnown(); + return CHANGED; + } + + auto IsIgnoredUseValue = [&](const Use &U) { + Value *BasePtr = U.get()->stripInBoundsOffsets(); + return isIgnoredLocation(MemoryLocation(BasePtr)); + }; + auto IsArgumentOrIgnoredUseValue = [&](const Use &U) { + Value *BasePtr = U.get()->stripInBoundsOffsets(); + return isa(BasePtr) || IsIgnoredUseValue(U); + }; + auto ExtractCallSiteInfo = [&](CallSite CS, bool &MayRead, + bool &MayWrite, bool &MayNonArgMem) { + auto ModRef = AAR.getModRefBehavior(CS); + MayRead = !AAResults::doesNotReadMemory(ModRef); + MayWrite = !AAResults::onlyReadsMemory(ModRef); + MayNonArgMem = !AAResults::onlyAccessesArgPointees(ModRef); + + if (!CS.getCalledFunction()) + return; + + auto *CalledFnAA = + A.getAAFor(*CS.getCalledFunction()); + if (!CalledFnAA) + return; + + if (CalledFnAA->isAssumedReadOnly()) + MayWrite = false; + if (CalledFnAA->isAssumedWriteOnly()) + MayRead = false; + if (CalledFnAA->isAssumedArgMemOnly()) + MayNonArgMem = false; + }; + + bool Changed = UNCHANGED; + errs() << "UPDATE nr:" << getNoReadState() << " | nw:" << getNoWriteState() + << " | #c:" << State.UnknownCalls.size() << "\n"; + + for (Instruction *I : State.UnknownCalls) { + CallSite CS(I); + assert(CS); + + if (CS.hasOperandBundles()) { + State.revertToKnown(); + return CHANGED; + } + + bool MayRead, MayWrite, MayNonArgMem; + ExtractCallSiteInfo(CS, MayRead, MayWrite, MayNonArgMem); + errs() << "CS: " << *I << " : " << MayRead << " : " << MayWrite << " : " << MayNonArgMem << "\n"; + + if (!MayNonArgMem && + std::all_of(CS.arg_begin(), CS.arg_end(), IsIgnoredUseValue)) + continue; + + if (MayNonArgMem || + !std::all_of(CS.arg_begin(), CS.arg_end(), IsArgumentOrIgnoredUseValue)) + State.ArgMemOnly.revertToKnown(); + + if (MayRead) + getNoReadState().revertToKnown(); + if (MayWrite) + getNoWriteState().revertToKnown(); + } + + return Changed; +} + +bool AAFunctionMemoryBehavior::manifest(Attributor &A) { + if (getState().isWorstPossible()) + return false; + + Function &F = cast(getAnchoredValue()); + if (isKnownReadNone()) { + F.removeFnAttr(Attribute::ReadOnly); + F.removeFnAttr(Attribute::WriteOnly); + F.removeFnAttr(Attribute::ArgMemOnly); + F.removeFnAttr(Attribute::InaccessibleMemOnly); + F.removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly); + + return AbstractAttribute::manifest(A); + } + + bool Changed = false; + if (isKnownArgMemOnly() && !F.hasFnAttribute(Attribute::ArgMemOnly)) { + // TODO: Inacc + F.removeFnAttr(Attribute::InaccessibleMemOnly); + F.removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly); + F.addFnAttr(Attribute::ArgMemOnly); + Changed = true; + } + + if (isKnownReadOnly()) { + F.removeFnAttr(Attribute::WriteOnly); + return AbstractAttribute::manifest(A) || Changed; + } + + if (isKnownWriteOnly()) { + F.removeFnAttr(Attribute::ReadOnly); + return AbstractAttribute::manifest(A) || Changed; + } + + return Changed; +} + +/// An AA to represent the memory behavior argument attributes. +struct AAArgumentMemoryBehavior final : public AAMemoryAccessBehaviorImpl { + + /// See AAMemoryAccessBehaviorImpl::AAMemoryAccessBehaviorImpl(...). + AAArgumentMemoryBehavior(Argument &Arg) : AAMemoryAccessBehaviorImpl(Arg) { + for (const Use &U : Arg.uses()) + Uses.push_back(&U); + // TODO + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_ARGUMENT; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return isAssumedReadNone() + ? &NumArgReadNone + : (isAssumedReadOnly() + ? &NumArgReadOnly + : (isAssumedWriteOnly() ? &NumArgWriteOnly : nullptr)); + } + + ///} + +private: + + bool followUseIn(Attributor &A, const Use *U, Instruction *UserI); + bool analyzeUseIn(Attributor &A, const Use *U, Instruction *UserI); + + SmallVector Uses; + +}; + +bool AAArgumentMemoryBehavior::followUseIn(Attributor &A, const Use *U, Instruction *UserI) { + switch (UserI->getOpcode()) { + case Instruction::Load: return false; + + case Instruction::Call: + case Instruction::Invoke: { + CallSite CS(UserI); + if (!CS.isArgOperand(U) || !CS.getCalledFunction()) + return true; + unsigned ArgNo = CS.getArgumentNo(U); + auto *ArgNoCaptureAA = A.getAAFor( + *(CS.getCalledFunction()->arg_begin() + ArgNo)); + return !(ArgNoCaptureAA && ArgNoCaptureAA->isAssumedNoCapture()); + } + } + return true; +} + +bool AAArgumentMemoryBehavior::analyzeUseIn(Attributor &A, const Use *U, + Instruction *UserI) { + bool MayRead = false, MayWrite = false; + switch (UserI->getOpcode()) { + case Instruction::Load: + MayRead = true; + //MayWrite |= UserI->mayWriteToMemory(); + break; + case Instruction::Store: + //MayRead |= UserI->mayReadFromMemory(); + MayWrite |= cast(UserI)->getPointerOperand() == U->get(); + break; + case Instruction::Call: + case Instruction::Invoke: { + CallSite CS(UserI); + if (CS.isArgOperand(U) && CS.getCalledFunction()) { + unsigned ArgNo = CS.getArgumentNo(U); + auto *ArgMemAccBehavior = A.getAAFor( + *(CS.getCalledFunction()->arg_begin() + ArgNo)); + if (ArgMemAccBehavior) { + MayRead |= !(ArgMemAccBehavior->isAssumedReadOnly()); + MayWrite |= !(ArgMemAccBehavior->isAssumedWriteOnly()); + break; + } + } + LLVM_FALLTHROUGH; + } + default: + MayRead |= UserI->mayReadFromMemory(); + MayWrite |= UserI->mayWriteToMemory(); + break; + }; + + bool Changed = false; + if (MayRead && isAssumedWriteOnly()) { + getNoReadState().revertToKnown(); + assert(!isAssumedWriteOnly()); + Changed = true; + } + if (MayWrite && isAssumedReadOnly()) { + getNoWriteState().revertToKnown(); + assert(!isAssumedReadOnly()); + Changed = true; + } + + return Changed; +} + +bool AAArgumentMemoryBehavior::updateImpl(Attributor &A, Direction Dir) { + assert(isAssumedReadOnly() || isAssumedWriteOnly()); + + if (Dir == FORWARD) { + State.revertToKnown(); + return CHANGED; + } + + Argument &Arg = cast(getAssociatedValue()); + auto *FnMemBehavior = A.getAAFor(*Arg.getParent()); + if (FnMemBehavior) { + if (FnMemBehavior->isAssumedReadNone()) { + assert(isAssumedReadNone()); + return UNCHANGED; + } + if (!isAssumedWriteOnly() && FnMemBehavior->isAssumedReadOnly()) { + assert(isAssumedReadOnly()); + return UNCHANGED; + } + if (!isAssumedReadOnly() && FnMemBehavior->isAssumedWriteOnly()) { + assert(isAssumedWriteOnly()); + return UNCHANGED; + } + } + + bool Changed = false; + for (int i = 0; i < Uses.size(); i++) { + const Use *U = Uses[i]; + Instruction *UserI = cast(U->getUser()); + + if (followUseIn(A, U, UserI)) + for (const Use &UserIUse : UserI->uses()) + Uses.push_back(&UserIUse); + + if (!UserI->mayReadOrWriteMemory()) + continue; + + Changed |= analyzeUseIn(A, U, UserI); + } + + return Changed; +} + +/// ---------------- No-Capture Attributes ----------------------- + +/// A class to hold the state of for no-capture attributes. +struct AANoCaptureImpl : public AANoCapture { + + /// Constructor that takes the value this attribute is associated with (@p V) + /// as well as the function this attribute is related to. + AANoCaptureImpl(Value &V, Function &F) : AANoCapture(V) { + if (F.onlyReadsMemory() && F.doesNotThrow() && + F.getReturnType()->isVoidTy()) + State.indicateFixpoint(); + if (V.getNumUses() == 0) + State.indicateFixpoint(); + } + + /// See AANoCapture::isKnownNoCapture(). + bool isKnownNoCapture() const override { return State.getKnown(); } + + /// See AANoCapture::isAssumedNoCapture(...). + bool isAssumedNoCapture() const override { return State.getAssumed(); } + + /// See AbstractAttribute::getState() + ///{ + AbstractState &getState() override { return State; } + const AbstractState &getState() const override { return State; } + ///} + +protected: + + using StateTy = BooleanState; + + StateTy State; +}; + +struct AACaptureUseTracker final : public CaptureTracker { + + AACaptureUseTracker(Attributor &A) : A(A), AssumedNoCapture(true) {} + + void tooManyUses() override { AssumedNoCapture = false; } + + bool captured(const Use *U) override { + errs() << "Check use: " << *U->get() << " in " << *U->getUser() << "\n"; + CallSite CS(U->getUser()); + if (!CS || !CS.getCalledFunction() || !CS.isArgOperand(U)) { + AssumedNoCapture = false; + return true; + } + + int ArgNo = CS.getArgumentNo(U); + auto *ArgNoCaptureAA = + A.getAAFor(*(CS.getCalledFunction()->arg_begin() + ArgNo)); + errs() << *CS.getInstruction() << " @@@ " << ArgNo << " : " << ArgNoCaptureAA << "\n"; + if (ArgNoCaptureAA) + errs( ) << *ArgNoCaptureAA << "\n"; + if (ArgNoCaptureAA && ArgNoCaptureAA->isAssumedNoCapture()) + return false; + + AssumedNoCapture = false; + return true; + } + + bool shouldExplore(const Use *U) override{ + // TODO: "returned" and "no-capture" should be combinable in the future! + CallSite CS(U->get()); + if (CS && !isa(CS.getInstruction())) + return false; + return true; + } + + bool AssumedNoCapture; + + Attributor &A; +}; + +/// An AA to represent the no-capture argument attribute. +struct AANoCaptureArgument final : public AANoCaptureImpl { + + /// See AANoCaptureImpl::AANoCaptureImpl(...). + AANoCaptureArgument(Argument &Arg) : AANoCaptureImpl(Arg, *Arg.getParent()) { + if (Arg.hasAttribute(getAttrKind())) + State.indicateFixpoint(); + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AbstractAttribute::getArgumentNo(). + virtual int getArgumentNo() const override { + return cast(getAnchoredValue()).getArgNo(); + } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_ARGUMENT; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return &NumFnArgumentNoCapture; + } + + ///} +}; + +bool AANoCaptureArgument::updateImpl(Attributor &A, Direction Dir) { + if (Dir == FORWARD) { + State.revertToKnown(); + return CHANGED; + } + + // Functions that are readonly (or readnone) and nounwind and don't return + // a value can't capture arguments. Don't analyze them. + //if (F.onlyReadsMemory() && F.doesNotThrow() && + //F.getReturnType()->isVoidTy()) { + //State.indicateFixpoint(); + //return CHANGED; + //} + + AACaptureUseTracker Tracker(A); + PointerMayBeCaptured(&getAssociatedValue(), &Tracker); + if (Tracker.AssumedNoCapture) + return UNCHANGED; + + State.revertToKnown(); + return CHANGED; +} + + + +/// ---------------- Dereferenceable-Or-Null Attributes ----------------------- + +/// A class to hold the state of for dereferenceable(-or-null) attributes. +struct AADereferenceableOrNullImpl : public AADereferenceableOrNull { + + /// Constructor that takes the value this attribute is associated with (@p V) + /// as well as the function this attribute is related to. + AADereferenceableOrNullImpl(Value &V, unsigned AddrSpace, Function &F) + : AADereferenceableOrNull(V), F(F), + NullPtrIsUndefined(!NullPointerIsDefined(&F, AddrSpace)) {} + + /// See AADereferenceableOrNull::isKnownNonNull(). + bool isKnownNonNull() const override { return State.getNonNull().getKnown(); } + + /// See AADereferenceableOrNull::isAssumedNonNull(...). + bool isAssumedNonNull() const override { + return State.getNonNull().getAssumed(); + } + + /// See AADereferenceableOrNull::getKnownDereferenceableBytes(). + uint64_t getKnownDereferenceableBytes() const override { + return State.getDerefBytes().getKnown(); + } + + /// See AADereferenceableOrNull::getAssumedDereferenceableBytes(...). + uint64_t getAssumedDereferenceableBytes() const override { + return State.getDerefBytes().getAssumed(); + } + + /// See AbstractAttribute::useKnownAccessInformation(...). + virtual void useKnownAccessInformation(uint64_t Length, + const APInt &Offset) override; + + /// See AbstractAttribute::getState() + ///{ + virtual AbstractState &getState() override { return State; } + virtual const AbstractState &getState() const override { return State; } + ///} + + virtual bool isImpliedBy(AbstractAttribute &OtherAA, Direction Dir, + bool &Changed) override; + + using DerefBytesStateTy = IntegerState; + using NonNullStateTy = BooleanState; + + struct DerefBytesOrNullStateTy + : public PairState { + using Super = PairState; + + DerefBytesOrNullStateTy() : Super() {} + DerefBytesOrNullStateTy(const DerefBytesStateTy &DerefBytes, + const NonNullStateTy &NonNull) + : Super(DerefBytes, NonNull) {} + + DerefBytesStateTy &getDerefBytes() { return Left; } + const DerefBytesStateTy &getDerefBytes() const { return Left; } + + NonNullStateTy &getNonNull() { return Right; } + const NonNullStateTy &getNonNull() const { return Right; } + + virtual bool isWorstPossible() const override { + return getDerefBytes().isWorstPossible(); + } + + void combineStateWithOffset(const APInt &Offset, bool NullPtrIsUndefined) { + LLVM_DEBUG(errs() << "State: " << getDerefBytes() << " - Off: " << Offset + << ":\n"); + auto &DerefBytes = getDerefBytes(); + if (DerefBytes.isWorstPossible()) + return; + + DerefBytes.setKnown( + std::max((int64_t)0, + ((int64_t)DerefBytes.getKnown()) - Offset.getSExtValue())); + getNonNull().setKnown(NullPtrIsUndefined && DerefBytes.getKnown() > 0); + + LLVM_DEBUG(errs() << "State: " << getDerefBytes() << " - Off: " << Offset + << ":\n"); + + isConsistent(); + } + + static DerefBytesOrNullStateTy bot() { + return DerefBytesOrNullStateTy(DerefBytesStateTy::bot(), + NonNullStateTy::bot()); + } + static DerefBytesOrNullStateTy top() { + return DerefBytesOrNullStateTy(DerefBytesStateTy::top(), + NonNullStateTy::top()); + } + }; + + using DerefBytesOrNullStateCache = StateCache; + +protected: + /// Check the value @p V for dereferenceability and update the internal state + /// (IsAssumedNonNull and DerefBytes.Assumed). Returns true if the state was + /// altered. + DerefBytesOrNullStateTy + computeDerefOrNullStateTy(Value *V, Attributor &A, Direction Dir, + DerefBytesOrNullStateCache &Cache); + + static DerefBytesOrNullStateTy + computeDerefOrNullStateTyForExactValue(Value *V, Attributor &A, Direction Dir, + Function &F, bool NullPtrIsUndefined); + + DerefBytesOrNullStateTy State; + + const bool NullPtrIsUndefined; + + /// The function associated with this abstract state. + Function &F; +}; + +void AADereferenceableOrNullImpl::useKnownAccessInformation( + uint64_t Length, const APInt &Offset) { + assert(Length); + + DerefBytesStateTy DerefBytes(Length); + NonNullStateTy NonNull(NullPtrIsUndefined); + + DerefBytesOrNullStateTy AccessState(DerefBytes, NonNull); + + APInt AdjOffset(Offset); + AdjOffset.negate(); + AccessState.combineStateWithOffset(AdjOffset, NullPtrIsUndefined); + + State.getUpperBound(AccessState); +} + +bool AADereferenceableOrNullImpl::isImpliedBy(AbstractAttribute &OtherAA, + Direction Dir, bool &Changed) { + Attribute::AttrKind OtherKind = OtherAA.getAttrKind(); + assert(OtherKind == Attribute::Dereferenceable || + OtherKind == Attribute::DereferenceableOrNull); + + auto &OtherDerefOrNullAA = + static_cast(OtherAA); + if (OtherDerefOrNullAA.getKnownDereferenceableBytes() == 0) + return false; + + Value &Ptr = OtherAA.getAssociatedValue(); + const DataLayout &DL = F.getParent()->getDataLayout(); + unsigned IdxWidth = + DL.getIndexSizeInBits(Ptr.getType()->getPointerAddressSpace()); + APInt Offset(IdxWidth, 0); + Value *Base = Ptr.stripAndAccumulateInBoundsConstantOffsets(DL, Offset); + if (Base != &getAssociatedValue()) + return false; + + auto OtherState = OtherDerefOrNullAA.State; + OtherState.combineStateWithOffset(Offset, NullPtrIsUndefined); + OtherState.revertToKnown(); + + auto OldState = State; + State.combine(OtherState); + + Changed = (OldState != State); + + // Try to improve the state and do not stop here. + return false; +} + +AADereferenceableOrNullImpl::DerefBytesOrNullStateTy +AADereferenceableOrNullImpl::computeDerefOrNullStateTy( + Value *V, Attributor &A, Direction Dir, DerefBytesOrNullStateCache &Cache) { + return cachedPointerTraversal(Cache, V, + computeDerefOrNullStateTyForExactValue, A, Dir, + F, NullPtrIsUndefined); +} + +AADereferenceableOrNullImpl::DerefBytesOrNullStateTy +AADereferenceableOrNullImpl::computeDerefOrNullStateTyForExactValue( + Value *Ptr, Attributor &A, Direction Dir, Function &F, + bool NullPtrIsUndefined) { + + if (!Ptr->getType()->isPointerTy()) + return DerefBytesOrNullStateTy::top(); + + const DataLayout &DL = F.getParent()->getDataLayout(); + + unsigned IdxWidth = + DL.getIndexSizeInBits(Ptr->getType()->getPointerAddressSpace()); + APInt Offset(IdxWidth, 0); + Value *Base; + if (Dir == BACKWARD) { + Base = Ptr->stripAndAccumulateInBoundsConstantOffsets(DL, Offset); + } else { + Base = Ptr->stripPointerCasts(); + } + + // A "NULL" value is often defined as non-dereferenceable. If encountered we + // jump immediately to top. + if (isa(Base) && cast(Base)->isZeroValue() && + NullPtrIsUndefined) { + return DerefBytesOrNullStateTy::top(); + } + + // Check if the value has an associated abstract attribute, e.g. an argument + // or call site. If that is the case, we can use the optimistic information, + // which should be the best possible information available, to update the + // current attribute. + auto *BaseDerefOrNullAA = A.getAAFor(*Base); + // errs() << "BAse: " << *Base << " : " << BaseDerefOrNullAA << "\n"; + if (BaseDerefOrNullAA) { + // This attribute now depends on the abstract attribute for the value. + // addUsedAA(*BaseDerefOrNullAA); + + DerefBytesOrNullStateTy BaseState = BaseDerefOrNullAA->State; + // errs() << BaseState << "\n"; + BaseState.combineStateWithOffset(Offset, NullPtrIsUndefined); + // BaseState.revertToKnown(); + // errs() << BaseState << "\n"; + return BaseState; + } + + bool BaseKnownCanBeNull = false; + if (uint64_t BaseKnownDerefBytes = + Base->getPointerDereferenceableBytes(DL, BaseKnownCanBeNull)) { + DerefBytesOrNullStateTy BaseState; + BaseState.getDerefBytes().setKnown(BaseKnownDerefBytes); + BaseState.getNonNull().setKnown(!BaseKnownCanBeNull); + + BaseState.combineStateWithOffset(Offset, NullPtrIsUndefined); + BaseState.revertToKnown(); + + return BaseState; + } + + if (isDereferenceablePointer(Base, DL)) { + uint64_t AccessSize = + DL.getTypeStoreSize(Base->getType()->getPointerElementType()); + DerefBytesOrNullStateTy BaseState; + BaseState.getDerefBytes().setKnown(AccessSize); + BaseState.getNonNull().setKnown(NullPtrIsUndefined); + + BaseState.combineStateWithOffset(Offset, NullPtrIsUndefined); + BaseState.revertToKnown(); + + return BaseState; + } + + return DerefBytesOrNullStateTy::top(); +} + +raw_ostream & +operator<<(raw_ostream &OS, + const AADereferenceableOrNullImpl::DerefBytesOrNullStateTy &State) { + return OS << "\tDereferenceable bytes " << State.getDerefBytes() + << ", non-null " << State.getNonNull(); +} + +/// An AA to represent the dereferenceable(-or-null) argument attribute. +struct AADereferenceableOrNullArgument final + : public AADereferenceableOrNullImpl { + + /// See AADereferenceableOrNullImpl::AADereferenceableOrNullImpl(...). + AADereferenceableOrNullArgument(Argument &Arg) + : AADereferenceableOrNullImpl( + Arg, Arg.getType()->getPointerAddressSpace(), *Arg.getParent()) { + uint64_t DerefBytes = Arg.getDereferenceableBytes(); + if (DerefBytes) + State.getNonNull().setKnown(true); + + uint64_t DerefOrNullBytes = Arg.getDereferenceableOrNullBytes(); + State.getDerefBytes().setKnown(std::max(DerefBytes, DerefOrNullBytes)); + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AbstractAttribute::getArgumentNo(). + virtual int getArgumentNo() const override { + return cast(getAnchoredValue()).getArgNo(); + } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_ARGUMENT; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return isKnownNonNull() ? &NumFnArgumentDereferenceable + : &NumFnArgumentDereferenceableOrNull; + } + + ///} +}; + +bool AADereferenceableOrNullArgument::updateImpl(Attributor &A, Direction Dir) { + if (Dir == BACKWARD) { + State.revertToKnown(); + return CHANGED; + } + + DerefBytesOrNullStateTy UpdateState = DerefBytesOrNullStateTy::bot(); + + const DataLayout &DL = F.getParent()->getDataLayout(); + + DerefBytesOrNullStateCache Cache; + // Callback function + CallSiteCallbackTy CallSiteCheck = [&](CallSite CS) { + assert(CS && "Sanity check: Call site was not initialized properly!"); + + Value *Op = CS.getArgOperand(getArgumentNo()); + DerefBytesOrNullStateTy OpState = + computeDerefOrNullStateTy(Op, A, Dir, Cache); + LLVM_DEBUG(dbgs() << "Operand: " << *Op << " at call site " + << *CS.getInstruction() << " in " + << CS.getCaller()->getName() << ":\n" + << OpState << "\n";); + assert(OpState.isConsistent()); + + UpdateState.getLowerBound(OpState); + // errs() << "US: " << UpdateState << " OS: " << OpState << "\n"; + + return true; + }; + + // If no abstract argument was found look at the call sites. + if (A.foreachCallSite(F, CallSiteCheck)) { + // errs() << "fCS OK: " << UpdateState << "\n"; + auto OldState = State; + State.combine(UpdateState); + return (State != OldState); + } + + State.revertToKnown(); + return CHANGED; +} + +/// An AA to represent the dereferenceable(-or-null) argument attribute. +struct AADereferenceableOrNullCallSiteArgument final + : public AADereferenceableOrNullImpl { + + /// See AADereferenceableOrNullImpl::AADereferenceableOrNullImpl(...). + AADereferenceableOrNullCallSiteArgument(CallSite CS, unsigned ArgNo) + : AADereferenceableOrNullImpl( + *CS.getInstruction(), + CS.getArgOperand(ArgNo)->getType()->getPointerAddressSpace(), + *CS.getCaller()), + ArgNo(ArgNo) { + + uint64_t DerefBytes = CS.getDereferenceableBytes(ArgNo); + if (DerefBytes) + State.getNonNull().setKnown(true); + + uint64_t DerefOrNullBytes = CS.getDereferenceableOrNullBytes(ArgNo); + State.getDerefBytes().setKnown(std::max(DerefBytes, DerefOrNullBytes)); + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AbstractAttribute::getArgumentNo(). + virtual int getArgumentNo() const override { return ArgNo; } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + // This attribute doesn't exist in IR so we won't manifest it. + return MP_CALL_SITE_ARGUMENT_NOT_IR; + }; + + /// See AbstractAttribute::getAssociatedValue(). + ///{ + Value &getAssociatedValue() override { + return *CallSite(&getAnchoredValue()).getArgOperand(getArgumentNo()); + } + const Value &getAssociatedValue() const override { + return *ImmutableCallSite(&getAnchoredValue()) + .getArgOperand(getArgumentNo()); + } + ///} + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return isKnownNonNull() ? &NumCSArgumentDereferenceable + : &NumCSArgumentDereferenceableOrNull; + } + + ///} + +private: + /// The underlying value is the argument at position "ArgNo" of the call site + /// that is used as the underyling anchor. See + /// AbstractAttribute::getAssociatedValue(). + const unsigned ArgNo; +}; + +bool AADereferenceableOrNullCallSiteArgument::updateImpl(Attributor &A, + Direction Dir) { + CallSite CS(&getAnchoredValue()); + Value *V = CS.getArgOperand(getArgumentNo()); + + if (Dir == BACKWARD) { + Function *Callee = CS.getCalledFunction(); + assert(Callee && Callee->arg_size() > getArgumentNo()); + + Argument *FnArg = Callee->arg_begin() + getArgumentNo(); + auto *DerefOrNullFnArgAA = A.getAAFor(*FnArg); + // errs() << "FnArg: " << *FnArg << " : " << DerefOrNullFnArgAA << "\n"; + + if (!DerefOrNullFnArgAA) { + State.revertToKnown(); + return CHANGED; + } + // errs() << "FnArg: " << *FnArg << " : " << *DerefOrNullFnArgAA << "\n"; + + auto &ArgState = + static_cast(DerefOrNullFnArgAA->getState()); + if (State == ArgState) + return UNCHANGED; + + State.combine(ArgState); + return CHANGED; + } + + DerefBytesOrNullStateCache Cache; + DerefBytesOrNullStateTy UpdateState = + computeDerefOrNullStateTy(V, A, Dir, Cache); + + auto OldState = State; + State.combine(UpdateState); + return !(State == OldState); +} + +/// An AA to represent the dereferenceable(-or-null) function return attribute. +struct AADereferenceableOrNullReturned final + : public AADereferenceableOrNullImpl { + + /// See AADereferenceableOrNullImpl::AADereferenceableOrNullImpl(...). + AADereferenceableOrNullReturned(Function &F) + : AADereferenceableOrNullImpl( + F, F.getReturnType()->getPointerAddressSpace(), F) {} + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_RETURNED; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return isKnownNonNull() ? &NumFnReturnDereferenceable + : &NumFnReturnDereferenceableOrNull; + } +}; + +bool AADereferenceableOrNullReturned::updateImpl(Attributor &A, Direction Dir) { + + if (Dir == FORWARD) { + DerefBytesOrNullStateCache Cache; + // Check all values returned by this function. + ReturnedValueStateCallbackTy RVCallback = + [&](const ReturnedValueInfo *RVPtr) { + return computeDerefOrNullStateTy(RVPtr->V, A, Dir, Cache); + }; + return A.forwardReturnedValues(State, F, RVCallback); + } + + State.revertToKnown(); + return CHANGED; +} + +/// --------------------- Function Return Values ------------------------------- + +struct AAReturnedValuesImpl final : public AAReturnedValues { + + /// See AbstractAttribute::AbstractAttribute(...). + AAReturnedValuesImpl(Function &F) : AAReturnedValues(F) {} + + /// If this attribute is not top, we annotate the unique returned argument if + /// one exists. + virtual bool manifest(Attributor &A) override; + + virtual AbstractState &getState() override { return State; } + virtual const AbstractState &getState() const override { return State; } + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + // Unused, AbstractAttribute::manifest() is overwritten! + return MP_ARGUMENT; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return &NumFnArgumentReturned; + } + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AAReturnedValues::getNumReturnValues(). + size_t getNumReturnValues() const override { + return State.ReturnedValues.size(); + } + + void setUniqueReturnedValue(Argument &Arg) { + assert(State.ReturnedValues.empty()); + State.ReturnedValues.insert(new ReturnedValueInfo(&Arg)); + } + + /// Return the unique value returned by the associated function if one exists. + Value *getUniqueReturnedValue(Attributor &A) const override; + + /// Iterators to walk through all possibly returned values. + ///{ + iterator begin() override { return State.ReturnedValues.begin(); } + iterator end() override { return State.ReturnedValues.end(); } + ///} + + /// Pretty print the attribute similar to the IR representation. + virtual const std::string getAsStr() const override; + + /// Recursively collect potentially returned values, starting from + /// @p RV, into @p Container. While intermediate values are + /// also collected, this function walks through select/phi/casts. + bool collectReturnedValuesRecursively(Value *V, Instruction *CtxI, + const ReturnedValueInfo *RV); + +private: + struct ReturnedValuesStateTy final : public AbstractState { + + ~ReturnedValuesStateTy() { DeleteContainerPointers(ReturnedValues); } + + void resetAssumed() override {} + + bool isWorstPossible() const override { return IsWorstPossible; } + bool isBestPossible() const override { return IsFixed; } + + void revertToKnown() override { IsFixed = IsWorstPossible = true; } + + bool isAtFixpoint() const override { return IsFixed; } + + void indicateFixpoint() override { IsFixed = true; } + + bool isConsistent() const override { return true; } + + bool IsWorstPossible = false; + bool IsFixed = false; + + /// The set of values potentially returned by the associated function. + ReturnedValuesTy ReturnedValues; + SmallPtrSet SeenValues; + }; + + ReturnedValuesStateTy State; +}; + +bool AAReturnedValuesImpl::manifest(Attributor &A) { + Value *UniqueReturn = getUniqueReturnedValue(A); + if (!UniqueReturn) + return false; + + NumFnUniqueReturned++; + + if (auto *C = dyn_cast(UniqueReturn)) { + SmallVector Uses; + CallSiteCallbackTy CallSiteCheck = [&](CallSite CS) { + LLVM_DEBUG(dbgs() << "replace " << *CS.getInstruction() + << " [#U: " << CS.getInstruction()->getNumUses() + << " ] by " << *C << "\n";); + for (Use &U : CS.getInstruction()->uses()) + if (isa(U.getUser())) + Uses.push_back(&U); + return true; + }; + A.foreachCallSite(cast(getAnchoredValue()), CallSiteCheck, false); + + for (Use *U : Uses) { + NumFnReturnedConstantsReplaced++; + U->set(C); + } + return false; + } + + // If we have a unique return value _and_ it is an argument we + // annotate that argument as "returned". + if (auto *UniqueReturnArg = dyn_cast(UniqueReturn)) { + if (UniqueReturnArg->hasAttribute(Attribute::Returned)) + return false; + + UniqueReturnArg->addAttr(Attribute::Returned); + NumFnArgumentReturned++; + return true; + } + + return false; +} + +/// Pretty print the attribute similar to the IR representation. +const std::string AAReturnedValuesImpl::getAsStr() const { + return "returned(" + + (getState().isWorstPossible() + ? "inf" + : std::string("<= #") + + std::to_string(State.ReturnedValues.size())) + + ")"; +}; + +/// Recursively collect potentially returned values, starting from +/// @p RV, into @p Container. While intermediate values are +/// also collected, this function walks through select/phi/casts. +bool AAReturnedValuesImpl::collectReturnedValuesRecursively( + Value *V, Instruction *CtxI, const ReturnedValueInfo *RV) { + bool CHANGED = false; + if (isa(V)) + return CHANGED; + + // Collect the initial V just to see if we have seen it before. + if (!State.SeenValues.insert(V).second) + return CHANGED; + + // Note that stripPointerCasts looks through functions with a returned + // arguments. + Value *StrippedRV = V->stripPointerCasts(); + if (StrippedRV != V && !State.SeenValues.insert(StrippedRV).second) + return CHANGED; + + // Look through select instructions. + if (auto *SI = dyn_cast(StrippedRV)) { + CHANGED |= collectReturnedValuesRecursively(SI->getTrueValue(), CtxI, RV); + CHANGED |= collectReturnedValuesRecursively(SI->getFalseValue(), CtxI, RV); + return CHANGED; + } + + // Look through phi nodes. Recursion is not a problem as we keep the PHI + // node in the container as well (see above). + if (auto *PHI = dyn_cast(StrippedRV)) { + for (int i = 0, e = PHI->getNumIncomingValues(); i < e; i++) { + BasicBlock *BB = PHI->getIncomingBlock(i); + Value *Op = PHI->getIncomingValue(i); + CHANGED |= collectReturnedValuesRecursively(Op, BB->getTerminator(), RV); + } + return CHANGED; + } + + ReturnedValueInfo *NewRV = new ReturnedValueInfo(StrippedRV, CtxI, RV); + CHANGED |= State.ReturnedValues.insert(NewRV).second; + return CHANGED; +} + +bool AAReturnedValuesImpl::updateImpl(Attributor &A, Direction Dir) { + + // Check if we know of any values returned by the associated function, if not + // we are done. + if (getNumReturnValues() == 0) { + State.indicateFixpoint(); + return UNCHANGED; + } + + Function &F = cast(getAnchoredValue()); + assert(F.hasExactDefinition()); + + SmallVector NewReturnedValues; + SmallPtrSet ToBeRemovedRVs; + + // Check if any of the returned values is a call instruction that we have to + // refine, thus it is a call of a function in this SCC. + ReturnedValueCallbackTy RVCallback = [&](const ReturnedValueInfo *RVPtr) { + const ReturnedValueInfo &RV = *RVPtr; + LLVM_DEBUG(errs() << "- " << RV << "\n"); + + CallSite ReturnedCallSite(RV.V); + if (!ReturnedCallSite) + return true; + + Function *CalledFunction = ReturnedCallSite.getCalledFunction(); + if (!CalledFunction) + return true; + + // Iterate over the called function return values and determine if we can + // express them in the context of the call. If that works for all of them, + // the call is removed from the returned values and the values returned by + // the callee are used instead. If some values returned by the callee cannot + // be represented in the caller context, the call is kept and no values are + // added to the returned set. + SmallVector NewCallReturnedValues; + + Instruction *RVCallInst = ReturnedCallSite.getInstruction(); + ReturnedValueCallbackTy InnerRVCallback = + [&](const ReturnedValueInfo *InnerRVPtr) { + const ReturnedValueInfo &InnerRV = *InnerRVPtr; + LLVM_DEBUG(errs() << "-- Inner" << InnerRV << "\n"); + + if (auto *CFMRVArg = dyn_cast(InnerRV.V)) { + Value *ReturnedCallOperand = + ReturnedCallSite.getArgOperand(CFMRVArg->getArgNo()); + NewCallReturnedValues.push_back( + ReturnedValueInfo(ReturnedCallOperand, RV.CtxI, &RV)); + LLVM_DEBUG(errs() + << "--- New" << NewCallReturnedValues.back() << "\n"); + return true; + } + + if (auto *C = dyn_cast(InnerRV.V)) { + NewCallReturnedValues.push_back( + ReturnedValueInfo(C, RV.CtxI, &InnerRV)); + LLVM_DEBUG(errs() + << "--- New" << NewCallReturnedValues.back() << "\n"); + return true; + } + + CallSite InnerRVCallSite(InnerRV.V); + if (InnerRVCallSite && InnerRVCallSite.getCalledFunction() == &F) { + return true; + } + + LLVM_DEBUG(errs() << "ARA updateImpl: leftover call RV: " + << *InnerRV.V << "\n"); + return false; + }; + + if (A.foreachReturnedValue(*CalledFunction, InnerRVCallback)) { + LLVM_DEBUG(errs() << "ARA updateImpl: remove call!\n"); + ToBeRemovedRVs.insert(const_cast(&RV)); + NewReturnedValues.append(NewCallReturnedValues.begin(), + NewCallReturnedValues.end()); + } + + return true; + }; + + bool Success = A.foreachReturnedValue(F, RVCallback); + assert(Success); + + bool CHANGED = ToBeRemovedRVs.empty() ? UNCHANGED : CHANGED; + + for (ReturnedValueInfo *RV : ToBeRemovedRVs) + State.ReturnedValues.erase(RV); + + for (const ReturnedValueInfo &NewRV : NewReturnedValues) { + LLVM_DEBUG(errs() << "Collect new rvs rec: " << *NewRV.V << "\n"); + if (collectReturnedValuesRecursively(NewRV.V, NewRV.CtxI, NewRV.RV)) + CHANGED = CHANGED; + } + + LLVM_DEBUG(errs() << "ARA updateImpl: CHANGED: " << CHANGED << "\n\n"); + + return CHANGED; +} + +Value *AAReturnedValuesImpl::getUniqueReturnedValue(Attributor &A) const { + Value *UniqueReturnedValue = nullptr; + + for (const ReturnedValueInfo *RV : State.ReturnedValues) { + + // If we haven't determined a unique returned value, or it is equal to the + // current one, we remember the current one and continue. + if (!UniqueReturnedValue || UniqueReturnedValue == RV->V) { + UniqueReturnedValue = RV->V; + continue; + } + + // We found a second value that could be returned and therefore conclude + // that there is no unique one. + LLVM_DEBUG(errs() << "No unique RV: " << *UniqueReturnedValue << " vs " + << *RV->V << "\n"); + return nullptr; + } + + // If we never set a unique return value it means we never returned anything. + // In this case we can assume we return "undef". + // TODO: For the purpose of improving later analyses we could also mark the + // instruction after the call sites as unreachable! + if (!UniqueReturnedValue) + return UndefValue::get(cast(getAnchoredValue()).getReturnType()); + + Argument *UniqueReturnArg = dyn_cast(UniqueReturnedValue); + if (!UniqueReturnArg) + return UniqueReturnedValue; + + return UniqueReturnedValue; +} + +/// --------------------- No-Alias function return ---------------------------- + +/// An AA to represent the no-alias function return attribute. +struct AANoAliasReturned final : public AANoAliasImpl { + + /// See AANoAliasImpl::AANoAliasImpl(...). + AANoAliasReturned(Function &F) : AANoAliasImpl(F) { + + // Determine if the IR already provides enough information. + if (F.hasAttribute(AttributeList::ReturnIndex, Attribute::NoAlias)) + State.indicateFixpoint(); + } + + /// See the AbstractAttribute interface for information. + ///{ + + /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir). + virtual bool updateImpl(Attributor &A, Direction Dir) override; + + /// See AbstractAttribute::getManifestPosition(). + virtual ManifestPosition getManifestPosition() const override { + return MP_RETURNED; + }; + + /// See AbstractAttribute::getStatisticObj(). + virtual Statistic *getStatisticObj() const override { + return &NumFnReturnNoAlias; + } + + ///} +}; + +bool AANoAliasReturned::updateImpl(Attributor &A, Direction Dir) { + Function &F = cast(getAssociatedValue()); + + if (Dir == FORWARD) { + NoAliasStateCache Cache; + // Check all values returned by this function. + ReturnedValueStateCallbackTy RVCallback = + [&](const ReturnedValueInfo *RVPtr) { + return computeNoAliasState(A, RVPtr->V, Dir, Cache); + }; + return A.forwardReturnedValues(State, F, RVCallback); + } + + State.revertToKnown(); + return CHANGED; +} + +/// -------------------------- Attributor ------------------------------------- + +bool Attributor::run(Module &M) { + bool Changed = false; + + for (Function &F : M) { + + // TODO: We could always determine abstract attributes and if sufficient + // information was found we could duplicate the functions that do not have + // an exact definition. + if (!F.hasExactDefinition()) { + + // Bookkeeping. + NumFnWithoutExactDefinition++; + continue; + } + + if (F.hasFnAttribute(Attribute::Naked) || + F.hasFnAttribute(Attribute::OptimizeNone)) + continue; + + // Bookkeeping. + NumFnWithExactDefinition++; + + // Sanity check. + assert(!F.isDeclaration() && "Expected a definition not a declaration!"); + + Changed |= identifyAbstractAttributes(F); + Changed |= identifyExistingInformation(F); + } + + AAVector AAWorklist, AAWorklistBuffer; + + auto ScheduleDependentAAs = [&](AbstractAttribute *AA) { + // We iterate over all dependent abstract attributes. + const AASetVector &DependentAAs = AADependenceMap.lookup(AA); + for (AbstractAttribute *DependentAA : DependentAAs) { + const AbstractState &DependentAAState = DependentAA->getState(); + + // If the dependent attribute is already fixed there is no need to + // schedule it. + // if (DependentAAState.isAtFixpoint()) + // continue; + + // Since AA CHANGED and DependentAA depens on the information provided + // by AA we need to revisit DependentAA. + AAWorklist.push_back(DependentAA); + } + }; + + Direction Dir = BACKWARD, LastDir = FORWARD; + int Iterations = 0; + int Fixpoints = 0; + while (Fixpoints != 3) { + assert(Fixpoints >= 0 && Fixpoints <= 2); + + LLVM_DEBUG(errs() << "\n\n[IT: " << Iterations << "] Start fixpoint in " + << Dir << " with " << AAsInSCC.size() << "AAs:\n"); + + bool ChangedLast; + do { + ChangedLast = UNCHANGED; + for (AbstractAttribute *AA : AAsInSCC) + ChangedLast |= AA->update(*this, Dir); + } while (ChangedLast && (Iterations++ < MAX_ATTRIBUTOR_ITERATIONS_PER_LVL)); + + if (ChangedLast) + NumMaxIterationsPerLevelReached++; + + bool ManifestChange = false; + for (AbstractAttribute *AA : AAsInSCC) { + AbstractState &AAState = AA->getState(); + + LLVM_DEBUG(errs() << "Attributor: PRE-FINAL: " << *AA << "\n"); + ChangedLast ? AAState.revertToKnown() : AAState.indicateFixpoint(); + LLVM_DEBUG(errs() << "Attributor: [" << ChangedLast << "] FINAL: " << *AA + << "\n"); + if (AAState.isWorstPossible()) + continue; + + bool LocalChange = AA->manifest(*this); + LLVM_DEBUG(errs() << "MANIFEST [" << LocalChange << "]: " << *AA << "\n"); + ManifestChange |= LocalChange; + } -using SCCNodeSet = SmallSetVector; + Changed |= ManifestChange; -} // end anonymous namespace + Fixpoints++; + if (ManifestChange) + Fixpoints = 0; + + if (Iterations >= MAX_ATTRIBUTOR_ITERATIONS_PER_LVL) + break; + + std::swap(Dir, LastDir); + + for (AbstractAttribute *AA : AAsInSCC) { + AA->getState().resetAssumed(); + } + } + + if (Iterations >= MAX_ATTRIBUTOR_ITERATIONS_PER_LVL) { + M.dump(); + assert(0); + } + + return Changed; +} + +void Attributor::registerDependence(AbstractAttribute &From, + AbstractAttribute &To) { + LLVM_DEBUG(errs() << "-- DEP " << From << "\n => " << To << "\n"); + AADependenceMap[&To].insert(&From); +} + +template +AAType *Attributor::getAAFor(const Value &V, int ArgNo, + Attribute::AttrKind ID) { + assert(ID != Attribute::None && "TODO"); + ImmutableCallSite CS(&V); + if (CS && ArgNo == -1 && CS.getCalledFunction()) + return getAAFor(*CS.getCalledFunction(), -1, ID); + + if (auto *Arg = dyn_cast(&V)) + ArgNo = Arg->getArgNo(); + + const auto &KindToAbstractAttributeMap = AAMap.lookup({&V, ArgNo}); + return static_cast(KindToAbstractAttributeMap.lookup(ID)); +} + +template +AAType &Attributor::registerAA(AAType &AA, AASetVector *LiveAAs) { + AAMap[{&AA.getAnchoredValue(), AA.getArgumentNo()}][AAType::ID] = &AA; + AAsInSCC.push_back(&AA); + + if (LiveAAs) { + AA.registerPrecedingAndSucceedingAAs(*LiveAAs, /* Preceding */ true, + /* Succeeding */ true); + LiveAAs->insert(&AA); + } + return AA; +} + +bool Attributor::foreachReturnedValue(Function &F, + ReturnedValueCallbackTy &Callback) { + auto *RVAA = getAAFor(F); + if (!RVAA) + return false; + + if (RVAA->getState().isWorstPossible()) + return false; + + for (const ReturnedValueInfo *RV : *RVAA) + if (!Callback(RV)) + return false; + + return true; +} + +template +bool Attributor::forwardReturnedValues( + StateTy &State, Function &F, + ReturnedValueStateCallbackTy &Callback, + bool LookThroughRecursion) { + + StateTy UpdateState = StateTy::bot(); + + // Check all values returned by this function. + ReturnedValueCallbackTy RVCallback = [&](const ReturnedValueInfo *RVPtr) { + // errs() << "RV: " << *RVPtr->V << " :: " << RVPtr->RV << "\n"; + + StateTy RVState = StateTy::top(); + do { + if (!LookThroughRecursion && RVPtr->RV && + RVPtr->RV->CtxI->getFunction() == &F) + return true; + + RVState.getUpperBound(Callback(RVPtr)); + } while (!RVState.isBestPossible() && (RVPtr = RVPtr->RV)); + + UpdateState.getLowerBound(RVState); + // errs() << "RVS: " << RVState << " US: "<hasExactDefinition()) { + if (!RequireAllCallSites) + continue; + + LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser() + << " is an invalid use of " << F.getName() << "\n"); + return false; + } + + assert(CS); + if (Callback(CS)) + continue; + + LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for " + << *CS.getInstruction() << "\n"); + return false; + } + + return true; +} + +template +bool Attributor::forwardCallSiteStates( + StateTy &State, Function &F, CallSiteStateCallbackTy &Callback, + bool RequireAllCallSites) { +#if 0 + + // we can try to determine information from + // the call sites. However, this is only possible all call sites are known, + // hence the function has internal linkage. + if (RequireAllCallSites && !F.hasInternalLinkage()) { + LLVM_DEBUG( + dbgs() + << "Attributor: Function " << F.getName() + << " hasn't internal linkage, hence call sites might be unknown\n"); + return false; + } + + for (const Use &U : F.uses()) { + + CallSite CS(U.getUser()); + if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) { + if (!RequireAllCallSites) + continue; + + LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser() + << " is an invalid use of " << F.getName() << "\n"); + return false; + } + + assert(CS); + StateTy CSState = Callback(CS); + + + LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for " + << *CS.getInstruction() << "\n"); + return false; + } + + return true; +#endif + return false; +} + +/// Determine opportunities to derive attributes. +bool Attributor::identifyAbstractAttributes(Function &F) { + bool Changed = false; + + auto &FunctionMemBehaviorAA = *new AAFunctionMemoryBehavior(F, getAAR(F)); + registerAA(FunctionMemBehaviorAA); + + // Return attributes are only appropriate if the return type is non void. + Type *ReturnType = F.getReturnType(); + if (!ReturnType->isVoidTy()) { + + if (ReturnType->isPointerTy()) { + // Return value attribute "no-alias". + registerAA(*new AANoAliasReturned(F)); + + // Return value attribute "dereferenceable(-or-null)". + registerAA(*new AADereferenceableOrNullReturned(F)); + + // TODO: Non-null should be a valid qualifier for integer types as + // well. Though, for now only pointer types are allowed. + // Return value attribute "non-null". + registerAA(*new AANonNullReturned(F)); + } + + // Argument attribute "returned" --- once per function. + registerAA(*new AAReturnedValuesImpl(F)); + } + + // TODO + DenseMap LiveAAsMap; + + BasicBlock *EntryBB = &F.getEntryBlock(); + AASetVector &ArgumentAAs = LiveAAsMap[EntryBB]; + + // For each argument we check if we can derive attributes. + for (Argument &Arg : F.args()) { + + // So far only pointer arguments are interesting. However, "returned" + // is also derived but as a "function return attribute" (see above). + if (!Arg.getType()->isPointerTy()) + continue; + + registerAA(*new AANoCaptureArgument(Arg), &ArgumentAAs); + + registerAA(*new AAArgumentMemoryBehavior(Arg), &ArgumentAAs); + + if (Arg.getNumUses() == 0) + continue; + + // Argument attribute "dereferenceable(-or-null)". + auto &DerefOrNullAA = registerAA( + *new AADereferenceableOrNullArgument(Arg), &ArgumentAAs); + + // Argument attribute "non-null". + auto &NonNullAA = registerAA(*new AANonNullArgument(Arg), + &ArgumentAAs); + NonNullAA.PrecedingAAs.insert(&DerefOrNullAA); + + // Return value attribute "no-alias". + registerAA(*new AANoAliasArgument(Arg), &ArgumentAAs); + } + + ReversePostOrderTraversal RPOT(&F); + + for (BasicBlock *BB : RPOT) { + AASetVector &LiveAAs = LiveAAsMap[BB]; + + bool UniquePred = true; + BasicBlock *UniquePredBB = nullptr; + SmallVector PredLiveAAsWithBBAsUniqueSuccVec; + for (BasicBlock *PredBB : predecessors(BB)) { + UniquePred &= (!UniquePredBB || UniquePredBB == PredBB); + UniquePredBB = PredBB; + + if (PredBB->getUniqueSuccessor() != BB) + continue; + + if (!LiveAAsMap.count(PredBB)) + continue; + + PredLiveAAsWithBBAsUniqueSuccVec.push_back(&LiveAAsMap[PredBB]); + } + + const AASetVector &UniquePredLiveAAs = + LiveAAsMap.lookup(UniquePred ? UniquePredBB : nullptr); + assert(UniquePred || UniquePredLiveAAs.empty()); + + auto RegisterLivePredAndSuccAAs = [&](AbstractAttribute &AA) { + AA.registerPrecedingAndSucceedingAAs( + UniquePredLiveAAs, /* Preceding */ true, /* Succeeding */ false); + + for (const AASetVector *PredLiveAAsWithBBAsUniqueSucc : + PredLiveAAsWithBBAsUniqueSuccVec) + AA.registerPrecedingAndSucceedingAAs(*PredLiveAAsWithBBAsUniqueSucc, + /* Preceding */ false, + /* Succeeding */ true); + }; + + for (Instruction &I : *BB) { + LLVM_DEBUG(errs() << " Visit: " << I << " [#LAAs: " << LiveAAs.size() + << "]\n"); + + if (I.mayReadOrWriteMemory()) + FunctionMemBehaviorAA.addMemoryAccessInst(I); + + if (LoadInst *Load = dyn_cast(&I)) { + if (Load->getType()->isPointerTy()) { + auto &AA = registerAA(*new AANonNullLoadResult(*Load), &LiveAAs); + RegisterLivePredAndSuccAAs(AA); + } + } else { + CallSite CS(&I); + if (CS && CS.getCalledFunction()) { + for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) { + if (!CS.getArgument(i)->getType()->isPointerTy()) + continue; + + { + // Call site argument attribute "dereferenceable-or-null". + auto &AA = registerAA( + *new AADereferenceableOrNullCallSiteArgument(CS, i), + &LiveAAs); + RegisterLivePredAndSuccAAs(AA); + } + + { + // Call site argument attribute "non-null". + auto &AA = + registerAA(*new AANonNullCallSiteArgument(CS, i), &LiveAAs); + RegisterLivePredAndSuccAAs(AA); + } + } + } + } + + tryToUseInstruction(I, LiveAAs); + + if (!isGuaranteedToTransferExecutionToSuccessor(&I)) + LiveAAs.clear(); + } + + if (LiveAAs.empty()) + continue; + + if (BasicBlock *UniqSuccBB = BB->getUniqueSuccessor()) { + // AASetVector &SuccAAs = LiveAAsMap[UniqSuccBB]; + // AASetVector &LiveAAs = LiveAAsMap[BB]; + // SuccAAs.insert(LiveAAs.begin(), LiveAAs.end()); + } + } + + return Changed; +} + +void Attributor::tryToUseCallSite(CallSite CS, AASetVector &InFlightAAs) { + + Instruction *CSInst = CS.getInstruction(); + LLVM_DEBUG(dbgs() << "Try to use CS [" << *CSInst << "]\n"); + + for (Use &ArgUse : CS.args()) { + const auto &CSArgK2AAMap = + AAMap.lookup({CSInst, CS.getArgumentNo(&ArgUse)}); + LLVM_DEBUG({ + dbgs() << " - Got " << CSArgK2AAMap.size() << " AAs for arg [" + << *ArgUse.get() << "]\n"; + for (const auto &It : CSArgK2AAMap) + dbgs() << " - " << It.first << " :" << *It.getSecond() << "\n"; + }); + + if (CSArgK2AAMap.empty()) + continue; + + Value *ArgBase = ArgUse->stripInBoundsConstantOffsets(); + const auto &BaseK2AAMap = AAMap.lookup({ArgBase, -1}); + LLVM_DEBUG(dbgs() << " - Base is [" << *ArgBase << "]\n with " + << BaseK2AAMap.size() << " AAs\n"); + + for (const auto &It : BaseK2AAMap) { + AbstractAttribute *AA = It.getSecond(); + + if (!InFlightAAs.count(AA)) + continue; + + // if (!EnableNonnullArgPropagation && + // AA->getAttrKind() == Attribute::NonNull) + // continue; + + // AbstractAttribute *CSAA = CSArgK2AAMap.lookup(AA->getAttrKind()); + // if (!CSAA) + // continue; + + // AA->addSufficientAA(*CSAA); + // CSAA->addSufficientAA(*AA); + } + } +} + +void Attributor::tryToUseInstruction(Instruction &I, AASetVector &InFlightAAs) { + Function &F = *I.getFunction(); + const DataLayout &DL = F.getParent()->getDataLayout(); + + auto UseAccess = [&](Value *Ptr, Value *LengthVal) { + uint64_t Length = 0; + + if (!LengthVal) { + assert(Ptr->getType()->isSized() && + "Sanity Check: Access to unsized pointer found!"); + Length = DL.getTypeStoreSize(Ptr->getType()->getPointerElementType()); + } else if (ConstantInt *CI = dyn_cast_or_null(LengthVal)) { + Length = CI->getZExtValue(); + } else if (isKnownNonZero(LengthVal, DL)) { + Length = 1; + } + + // If no length was determined we are unsure if there is an access at all. + if (!Length) + return; + + unsigned IdxWidth = + DL.getIndexSizeInBits(Ptr->getType()->getPointerAddressSpace()); + APInt Offset(IdxWidth, 0); + Ptr = Ptr->stripAndAccumulateInBoundsConstantOffsets(DL, Offset); + // Offset.negate(); + + int ArgNo = -1; + if (auto *Arg = dyn_cast(Ptr)) + ArgNo = Arg->getArgNo(); + + const auto &PtrK2AAMap = AAMap.lookup({Ptr, ArgNo}); + LLVM_DEBUG(errs() << "Ptr " << *Ptr << ", length: " << Length + << ", offset: " << Offset + << " #AssAAs: " << PtrK2AAMap.size() << "\n"); + + for (const auto &It : PtrK2AAMap) { + AbstractAttribute *AA = It.getSecond(); + LLVM_DEBUG(errs() << "Associated AA: " << *AA << "\n"); + + if (!InFlightAAs.count(AA)) + continue; + + AA->useKnownAccessInformation(Length, Offset); + } + }; + + if (auto *LI = dyn_cast(&I)) { + if (!LI->isVolatile()) + UseAccess(LI->getPointerOperand(), nullptr); + return; + } + if (auto *SI = dyn_cast(&I)) { + if (!SI->isVolatile()) + UseAccess(SI->getPointerOperand(), nullptr); + return; + } + + if (auto *MI = dyn_cast(&I)) { + if (!MI->isVolatile()) { + UseAccess(MI->getDest(), MI->getLength()); + if (auto *MTI = dyn_cast(&I)) + UseAccess(MTI->getSource(), MI->getLength()); + } + return; + } + + // CallSite CS(&I); + // if (CS) + // tryToUseCallSite(CS, InFlightAAs); +} + +bool Attributor::identifyExistingInformation(Function &F) { + auto *ReturnedValuesAA = getAAFor(F); + + if (ReturnedValuesAA) { + // There is nothing to do if an argument is already marked as + // 'returned' so we first check them. + for (Argument &Arg : F.args()) + if (Arg.hasReturnedAttr()) + ReturnedValuesAA->setUniqueReturnedValue(Arg); + + // If no "returned" argument was present we check all blocks for return + // instructions and add the returned values, and potentially their + // operands, to the set of potentially returned values. Also see + // AAReturnedValuesImpl::collectReturnedValuesRecursively(...). + if (!ReturnedValuesAA->getNumReturnValues()) { + for (BasicBlock &BB : F) + if (auto *RI = dyn_cast(BB.getTerminator())) + ReturnedValuesAA->collectReturnedValuesRecursively( + RI->getReturnValue(), RI, nullptr); + } + + auto MightChange = [&](const ReturnedValueInfo *RV) { + CallSite CS(RV->V); + if (CS && CS.getCalledFunction() && + CS.getCalledFunction()->hasExactDefinition()) + return true; + return false; + }; + + if (std::any_of(ReturnedValuesAA->begin(), ReturnedValuesAA->end(), + MightChange)) + return false; + + // Fix the result so we know it will never change. + ReturnedValuesAA->getState().indicateFixpoint(); + return ReturnedValuesAA->manifest(*this); + } + + return false; +} /// Returns the memory access attribute for function F using AAR for AA results, /// where SCCNodes is the current SCC. @@ -188,21 +3392,21 @@ ReadsMemory = true; } continue; - } else if (LoadInst *LI = dyn_cast(I)) { + } else if (auto *LI = dyn_cast(I)) { // Ignore non-volatile loads from local memory. (Atomic is okay here.) if (!LI->isVolatile()) { MemoryLocation Loc = MemoryLocation::get(LI); if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) continue; } - } else if (StoreInst *SI = dyn_cast(I)) { + } else if (auto *SI = dyn_cast(I)) { // Ignore non-volatile stores to local memory. (Atomic is okay here.) if (!SI->isVolatile()) { MemoryLocation Loc = MemoryLocation::get(SI); if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) continue; } - } else if (VAArgInst *VI = dyn_cast(I)) { + } else if (auto *VI = dyn_cast(I)) { // Ignore vaargs on local memory. MemoryLocation Loc = MemoryLocation::get(VI); if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) @@ -248,8 +3452,8 @@ // Non-exact function definitions may not be selected at link time, and an // alternative version that writes to memory may be selected. See the // comment on GlobalValue::isDefinitionExact for more details. - switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(), - AAR, SCCNodes)) { + switch ( + checkFunctionMemoryAccess(*F, F->hasExactDefinition(), AAR, SCCNodes)) { case MAK_MayWrite: return false; case MAK_ReadOnly: @@ -269,7 +3473,7 @@ bool MadeChange = false; assert(!(ReadsMemory && WritesMemory) && - "Function marked read-only and write-only"); + "Function marked read-only and write-only"); for (Function *F : SCCNodes) { if (F->doesNotAccessMemory()) // Already perfect! @@ -284,6 +3488,9 @@ MadeChange = true; + errs() << "Write: " << WritesMemory << " Reads: " << ReadsMemory << "\n"; + F->dump(); + // Clear out any existing attributes. F->removeFnAttr(Attribute::ReadOnly); F->removeFnAttr(Attribute::ReadNone); @@ -302,6 +3509,7 @@ else F->addFnAttr(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone); + if (WritesMemory && !ReadsMemory) ++NumWriteOnly; else if (ReadsMemory) @@ -310,6 +3518,7 @@ ++NumReadNone; } + assert(!MadeChange); return MadeChange; } @@ -571,9 +3780,60 @@ return IsRead ? Attribute::ReadOnly : Attribute::ReadNone; } -/// Deduce returned attributes for the SCC. static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) { - bool Changed = false; + bool CHANGED = false; + + // Check each function in turn, determining if an argument is always returned. + for (Function *F : SCCNodes) { + // We can infer and propagate function attributes only when we know that the + // definition we'll get at link time is *exactly* the definition we see now. + // For more details, see GlobalValue::mayBeDerefined. + if (!F->hasExactDefinition()) + continue; + + if (F->getReturnType()->isVoidTy()) + continue; + + // There is nothing to do if an argument is already marked as 'returned'. + if (llvm::any_of(F->args(), + [](const Argument &Arg) { return Arg.hasReturnedAttr(); })) + continue; + + auto FindRetArg = [&]() -> Value * { + Value *RetArg = nullptr; + for (BasicBlock &BB : *F) + if (auto *Ret = dyn_cast(BB.getTerminator())) { + // Note that stripPointerCasts should look through functions with + // returned arguments. + Value *RetVal = Ret->getReturnValue()->stripPointerCasts(); + if (!isa(RetVal) || RetVal->getType() != F->getReturnType()) + return nullptr; + + if (!RetArg) + RetArg = RetVal; + else if (RetArg != RetVal) + return nullptr; + } + + return RetArg; + }; + + if (Value *RetArg = FindRetArg()) { + auto *A = cast(RetArg); + A->addAttr(Attribute::Returned); + ++NumReturned; + CHANGED = true; + F->dump(); + } + } + + assert(!CHANGED); + return CHANGED; +} + +/// Deduce returned attributes for the SCC. +static bool addArgumentReturnedAttrs2(const SCCNodeSet &SCCNodes) { + bool CHANGED = false; struct ReturnValueInfoTy { Value *ReturnValue; @@ -686,33 +3946,29 @@ } } while (!AllFunctionsAreFixed); - for (Function *F : SCCNodes) { auto &RVI = FunctionReturnValueInfo[F]; if (!RVI.ReturnValue) continue; - NumReturnedKnown++; - NumReturnedKnownWithCalls += !RVI.CallReturnValues.empty(); - if (Argument *Arg = dyn_cast(RVI.ReturnValue)) { + if (Arg->hasReturnedAttr()) + continue; + Arg->addAttr(Attribute::Returned); - NumReturned++; - NumReturnedWithCalls += !RVI.CallReturnValues.empty(); - Changed = true; + CHANGED = true; } else if (isa(RVI.ReturnValue)) { - NumReturnedConstantKnown++; - NumReturnedConstantWithCalls += !RVI.CallReturnValues.empty(); - //errs() << "Found returned value is " << *RVI.ReturnValue - //<< " [#RetCalls: " << RVI.CallReturnValues.size() << "]\n"; + // errs() << "Found returned value is " << *RVI.ReturnValue + //<< " [#RetCalls: " << RVI.CallReturnValues.size() << "]\n"; } else { - //errs() << "Found returned value is " << *RVI.ReturnValue - //<< " [#RetCalls: " << RVI.CallReturnValues.size() << "]\n"; + // errs() << "Found returned value is " << *RVI.ReturnValue + //<< " [#RetCalls: " << RVI.CallReturnValues.size() << "]\n"; } } - return Changed; + assert(!CHANGED); + return CHANGED; } /// If a callsite has arguments that are also arguments to the parent function, @@ -723,7 +3979,7 @@ if (!EnableNonnullArgPropagation) return false; - bool Changed = false; + bool CHANGED = false; // For an argument attribute to transfer from a callsite to the parent, the // call must be guaranteed to execute every time the parent is called. @@ -746,7 +4002,7 @@ auto *FArg = dyn_cast(CS.getArgOperand(CSArg.getArgNo())); if (FArg && !FArg->hasNonNullAttr()) { FArg->addAttr(Attribute::NonNull); - Changed = true; + CHANGED = true; } } } @@ -755,12 +4011,13 @@ break; } - return Changed; + return CHANGED; } /// Deduce nocapture attributes for the SCC. static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) { - bool Changed = false; + bool CHANGED = false; + bool NEWCAPTURE = false; ArgumentGraph AG; @@ -769,11 +4026,11 @@ for (Function *F : SCCNodes) { // We can infer and propagate function attributes only when we know that the // definition we'll get at link time is *exactly* the definition we see now. - // For more details, see GlobalValue::mayBeDerefined. + // For more details, see GlobalValue::canBeDerefined. if (!F->hasExactDefinition()) continue; - Changed |= addArgumentAttrsFromCallsites(*F); + CHANGED |= addArgumentAttrsFromCallsites(*F); // Functions that are readonly (or readnone) and nounwind and don't return // a value can't capture arguments. Don't analyze them. @@ -784,7 +4041,9 @@ if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { A->addAttr(Attribute::NoCapture); ++NumNoCapture; - Changed = true; + CHANGED = true; + NEWCAPTURE = true; + F->dump(); } } continue; @@ -803,7 +4062,9 @@ // If it's trivially not captured, mark it nocapture now. A->addAttr(Attribute::NoCapture); ++NumNoCapture; - Changed = true; + CHANGED = true; + NEWCAPTURE = true; + F->dump(); } else { // If it's not trivially captured and not trivially not captured, // then it must be calling into another function in our SCC. Save @@ -828,8 +4089,9 @@ Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self); if (R != Attribute::None) { A->addAttr(R); - Changed = true; + CHANGED = true; R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; + A->getParent()->dump(); } } } @@ -854,7 +4116,9 @@ Argument *A = ArgumentSCC[0]->Definition; A->addAttr(Attribute::NoCapture); ++NumNoCapture; - Changed = true; + CHANGED = true; + NEWCAPTURE = true; + ArgumentSCC[0]->Definition->getParent()->dump(); } continue; } @@ -896,7 +4160,9 @@ Argument *A = ArgumentSCC[i]->Definition; A->addAttr(Attribute::NoCapture); ++NumNoCapture; - Changed = true; + CHANGED = true; + NEWCAPTURE = true; + A->getParent()->dump(); } // We also want to compute readonly/readnone. With a small number of false @@ -932,12 +4198,15 @@ A->removeAttr(Attribute::ReadNone); A->addAttr(ReadAttr); ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg; - Changed = true; + CHANGED = true; + A->getParent()->dump(); } } } - return Changed; + assert(!NEWCAPTURE); + assert(!CHANGED); + return CHANGED; } /// Tests whether a function is "malloc-like". @@ -1033,8 +4302,7 @@ bool MadeChange = false; for (Function *F : SCCNodes) { - if (F->returnDoesNotAlias() || - !F->getReturnType()->isPointerTy()) + if (F->returnDoesNotAlias() || !F->getReturnType()->isPointerTy()) continue; F->setReturnDoesNotAlias(); @@ -1042,6 +4310,9 @@ MadeChange = true; } + // if (MadeChange) + //(*SCCNodes.begin())->getParent()->dump(); + // assert(!MadeChange); return MadeChange; } @@ -1149,8 +4420,7 @@ if (!Speculative) { // Mark the function eagerly since we may discover a function // which prevents us from speculating about the entire SCC - LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName() - << " as nonnull\n"); + (dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n"); F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull); ++NumNonNullReturn; MadeChange = true; @@ -1169,13 +4439,16 @@ !F->getReturnType()->isPointerTy()) continue; - LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n"); + (dbgs() << "SCC marking " << F->getName() << " as nonnull\n"); F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull); ++NumNonNullReturn; MadeChange = true; } } + if (MadeChange) + (*SCCNodes.begin())->getParent()->dump(); + assert(!MadeChange); return MadeChange; } @@ -1257,7 +4530,8 @@ }); // For each attribute still in InferInSCC that doesn't explicitly skip F, - // set up the F instructions scan to verify assumptions of the attribute. + // set up the F instructions scan to isConsistent assumptions of the + // attribute. SmallVector InferInThisFunc; llvm::copy_if( InferInSCC, std::back_inserter(InferInThisFunc), @@ -1288,7 +4562,7 @@ if (InferInSCC.empty()) return false; - bool Changed = false; + bool CHANGED = false; for (Function *F : SCCNodes) // At this point InferInSCC contains only functions that were either: // - explicitly skipped from scan/inference, or @@ -1297,10 +4571,10 @@ for (auto &ID : InferInSCC) { if (ID.SkipFunction(*F)) continue; - Changed = true; + CHANGED = true; ID.SetAttribute(*F); } - return Changed; + return CHANGED; } } // end anonymous namespace @@ -1425,27 +4699,27 @@ template static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes, AARGetterT &&AARGetter, - bool HasUnknownCall) { - bool Changed = false; + DTGetterTy &DTGetter, bool HasUnknownCall) { + bool CHANGED = false; // Bail if the SCC only contains optnone functions. if (SCCNodes.empty()) - return Changed; + return CHANGED; - Changed |= addArgumentReturnedAttrs(SCCNodes); - Changed |= addReadAttrs(SCCNodes, AARGetter); - Changed |= addArgumentAttrs(SCCNodes); + CHANGED |= addArgumentReturnedAttrs(SCCNodes); + CHANGED |= addReadAttrs(SCCNodes, AARGetter); + CHANGED |= addArgumentAttrs(SCCNodes); // If we have no external nodes participating in the SCC, we can deduce some // more precise attributes as well. if (!HasUnknownCall) { - Changed |= addNoAliasAttrs(SCCNodes); - Changed |= addNonNullAttrs(SCCNodes); - Changed |= inferAttrsFromFunctionBodies(SCCNodes); - Changed |= addNoRecurseAttrs(SCCNodes); + CHANGED |= addNoAliasAttrs(SCCNodes); + CHANGED |= addNonNullAttrs(SCCNodes); + CHANGED |= inferAttrsFromFunctionBodies(SCCNodes); + CHANGED |= addNoRecurseAttrs(SCCNodes); } - return Changed; + return CHANGED; } PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C, @@ -1457,8 +4731,10 @@ // We pass a lambda into functions to wire them up to the analysis manager // for getting function analyses. - auto AARGetter = [&](Function &F) -> AAResults & { - return FAM.getResult(F); + std::function AARGetter = + [&](Function &F) -> AAResults & { return FAM.getResult(F); }; + DTGetterTy DTGetter = [&](Function &F) -> const DominatorTree & { + return FAM.getResult(F); }; // Fill SCCNodes with the elements of the SCC. Also track whether there are @@ -1490,7 +4766,12 @@ SCCNodes.insert(&F); } - if (deriveAttrsInPostOrder(SCCNodes, AARGetter, HasUnknownCall)) + if (SCCNodes.size()) { + Attributor A(AARGetter, DTGetter); + A.run(*SCCNodes.front()->getParent()); + } + + if (deriveAttrsInPostOrder(SCCNodes, AARGetter, DTGetter, HasUnknownCall)) return PreservedAnalyses::none(); return PreservedAnalyses::all(); @@ -1498,22 +4779,32 @@ namespace { -struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass { +struct PostOrderFunctionAttrsLegacyPass : public ModulePass { + // struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass { // Pass identification, replacement for typeid static char ID; - PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) { + // PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) { + PostOrderFunctionAttrsLegacyPass() : ModulePass(ID) { initializePostOrderFunctionAttrsLegacyPassPass( *PassRegistry::getPassRegistry()); } - bool runOnSCC(CallGraphSCC &SCC) override; + bool runOnModule(Module &M) override; + // bool runOnSCC(CallGraphSCC &SCC) override; void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); AU.addRequired(); getAAResultsAnalysisUsage(AU); - CallGraphSCCPass::getAnalysisUsage(AU); + AU.addRequired(); + AU.addRequired(); + + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); + // CallGraphSCCPass::getAnalysisUsage(AU); } }; @@ -1524,6 +4815,7 @@ "Deduce function attributes", false, false) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs", "Deduce function attributes", false, false) @@ -1531,8 +4823,9 @@ return new PostOrderFunctionAttrsLegacyPass(); } -template -static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) { +template +static bool runImpl(CGSCC &SCC, AARGetterT AARGetter, DTGetterTy &DTGetter, + Attributor &A) { // Fill SCCNodes with the elements of the SCC. Used for quickly looking up // whether a given CallGraphNode is in this SCC. Also track whether there are @@ -1540,7 +4833,7 @@ // part of the SCC. SCCNodeSet SCCNodes; bool ExternalNode = false; - for (CallGraphNode *I : SCC) { + for (auto *I : SCC) { Function *F = I->getFunction(); if (!F || F->hasFnAttribute(Attribute::OptimizeNone) || F->hasFnAttribute(Attribute::Naked)) { @@ -1553,14 +4846,51 @@ SCCNodes.insert(F); } - return deriveAttrsInPostOrder(SCCNodes, AARGetter, ExternalNode); + return deriveAttrsInPostOrder(SCCNodes, AARGetter, DTGetter, ExternalNode); +} + +bool PostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) { + if (skipModule(M)) + return false; + + LegacyAARGetter LAARGetter(*this); + std::function AARGetter = + [&](Function &F) -> AAResults & { return LAARGetter(F); }; + DTGetterTy DTGetter = [&](Function &F) -> const DominatorTree & { + return getAnalysis(F).getDomTree(); + }; + + Attributor A(AARGetter, DTGetter); + A.run(M); + + bool Changed = false; + auto &CG = getAnalysis().getCallGraph(); + for (scc_iterator I = scc_begin(&CG); !I.isAtEnd(); ++I) + Changed |= runImpl(*I, AARGetter, DTGetter, A); + + return Changed; } +#if 0 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) { if (skipSCC(SCC)) return false; - return runImpl(SCC, LegacyAARGetter(*this)); + + LegacyAARGetter LAARGetter(*this); + std::function AARGetter = + [&](Function &F) -> AAResults & { return LAARGetter(F); }; + DenseMap DTMap; + DTGetterTy DTGetter = [&](Function &F) -> const DominatorTree & { + auto *&DT = DTMap[&F]; + if (!DT) { + DT = new DominatorTree(F); + } + return *DT; + }; + + return runImpl(SCC, AARGetter, DTGetter, A); } +#endif namespace { @@ -1586,11 +4916,13 @@ char ReversePostOrderFunctionAttrsLegacyPass::ID = 0; -INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs", - "Deduce function attributes in RPO", false, false) +INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, + "rpo-functionattrs", "Deduce function attributes in RPO", + false, false) INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) -INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs", - "Deduce function attributes in RPO", false, false) +INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, + "rpo-functionattrs", "Deduce function attributes in RPO", + false, false) Pass *llvm::createReversePostOrderFunctionAttrsPass() { return new ReversePostOrderFunctionAttrsLegacyPass(); @@ -1627,8 +4959,6 @@ static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) { // We only have a post-order SCC traversal (because SCCs are inherently - // discovered in post-order), so we accumulate them in a vector and then walk - // it in reverse. This is simpler than using the RPO iterator infrastructure // because we need to combine SCC detection and the PO walk of the call // graph. We can also cheat egregiously because we're primarily interested in // synthesizing norecurse and so we can only save the singular SCCs as SCCs @@ -1644,7 +4974,7 @@ Worklist.push_back(F); } - bool Changed = false; + bool Changed = UNCHANGED; for (auto *F : llvm::reverse(Worklist)) Changed |= addNoRecurseAttrsTopDown(*F); @@ -1671,3 +5001,5 @@ PA.preserve(); return PA; } +//===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===// +// Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -528,6 +528,7 @@ // analysis infrastructure this "works" in that the analysis stays alive // for the entire SCC pass run below. MPM.add(createGlobalsAAWrapperPass()); + MPM.add(createPostOrderFunctionAttrsLegacyPass()); // Start of CallGraph SCC passes. MPM.add(createPruneEHPass()); // Remove dead EH info @@ -538,7 +539,6 @@ RunInliner = true; } - MPM.add(createPostOrderFunctionAttrsLegacyPass()); if (OptLevel > 2) MPM.add(createArgumentPromotionPass()); // Scalarize uninlined fn args @@ -565,6 +565,7 @@ // and saves running remaining passes on the eliminated functions. MPM.add(createEliminateAvailableExternallyPass()); + MPM.add(createPostOrderFunctionAttrsLegacyPass()); MPM.add(createReversePostOrderFunctionAttrsPass()); // The inliner performs some kind of dead code elimination as it goes, @@ -765,6 +766,7 @@ // Infer attributes about declarations if possible. PM.add(createInferFunctionAttrsLegacyPass()); + PM.add(createPostOrderFunctionAttrsLegacyPass()); if (OptLevel > 1) { // Split call-site with more constrained arguments. @@ -789,7 +791,6 @@ // Infer attributes about definitions. The readnone attribute in particular is // required for virtual constant propagation. - PM.add(createPostOrderFunctionAttrsLegacyPass()); PM.add(createReversePostOrderFunctionAttrsPass()); // Split globals using inrange annotations on GEP indices. This can help @@ -852,8 +853,8 @@ PM.add(createSROAPass()); // Run a few AA driven optimizations here and now, to cleanup the code. - PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture. PM.add(createGlobalsAAWrapperPass()); // IP alias analysis. + PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture. PM.add(createLICMPass()); // Hoist loop invariants. PM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds. Index: test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll =================================================================== --- test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll +++ test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll @@ -9,13 +9,13 @@ ; invalid, as it's possible that this only happens after optimization on a ; code path which isn't ever executed. -; CHECK: define void @test0_yes(i32* nocapture %p) #0 { +; CHECK: define void @test0_yes(i32* nocapture nonnull dereferenceable(4) %p) #0 { define void @test0_yes(i32* %p) nounwind { store i32 0, i32* %p, !tbaa !1 ret void } -; CHECK: define void @test0_no(i32* nocapture %p) #1 { +; CHECK: define void @test0_no(i32* nocapture nonnull dereferenceable(4) %p) #1 { define void @test0_no(i32* %p) nounwind { store i32 0, i32* %p, !tbaa !2 ret void Index: test/ThinLTO/X86/devirt-after-icp.ll =================================================================== --- test/ThinLTO/X86/devirt-after-icp.ll +++ test/ThinLTO/X86/devirt-after-icp.ll @@ -122,7 +122,7 @@ %8 = load i32 (%class.B*)*, i32 (%class.B*)** %vfn.i, align 8 ; Call to bar() can be devirtualized to call to B::bar(), since it was ; inlined from B::foo() after ICP introduced the guarded promotion. -; CHECK-IR: %call.i = tail call i32 @_ZN1B3barEv(%class.B* %3) +; CHECK-IR: %call.i = tail call i32 @_ZN1B3barEv(%class.B* nonnull %3) %call.i = tail call i32 %8(%class.B* %5) br label %if.end.icp Index: test/Transforms/FunctionAttrs/2009-01-02-LocalStores.ll =================================================================== --- test/Transforms/FunctionAttrs/2009-01-02-LocalStores.ll +++ test/Transforms/FunctionAttrs/2009-01-02-LocalStores.ll @@ -1,7 +1,7 @@ ; RUN: opt < %s -functionattrs -S | FileCheck %s ; RUN: opt < %s -passes=function-attrs -S | FileCheck %s -; CHECK: define i32* @a(i32** nocapture readonly %p) +; CHECK: define i32* @a(i32** nocapture nonnull readonly dereferenceable(8) %p) define i32* @a(i32** %p) { %tmp = load i32*, i32** %p ret i32* %tmp @@ -14,11 +14,3 @@ %tmp = call i32* @a(i32** %mem) ret i32* %tmp } - -; CHECK: define i32* @c(i32* readnone returned %r) -@g = global i32 0 -define i32* @c(i32 *%r) { - %a = icmp eq i32* %r, null - store i32 1, i32* @g - ret i32* %r -} Index: test/Transforms/FunctionAttrs/atomic.ll =================================================================== --- test/Transforms/FunctionAttrs/atomic.ll +++ test/Transforms/FunctionAttrs/atomic.ll @@ -14,11 +14,11 @@ ; A function with an Acquire load is not readonly. define i32 @test2(i32* %x) uwtable ssp { -; CHECK: define i32 @test2(i32* nocapture readonly %x) #1 { +; CHECK: define i32 @test2(i32* nocapture nonnull readonly dereferenceable(4) %x) #1 { entry: %r = load atomic i32, i32* %x seq_cst, align 4 ret i32 %r } ; CHECK: attributes #0 = { norecurse nounwind readnone ssp uwtable } -; CHECK: attributes #1 = { norecurse nounwind ssp uwtable } +; CHECK: attributes #1 = { argmemonly norecurse nounwind ssp uwtable } Index: test/Transforms/FunctionAttrs/attribute_propagation.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/attribute_propagation.ll @@ -0,0 +1,38 @@ +; RUN: opt -functionattrs -S < %s | FileCheck %s +; +; void foo(int *A) { +; bar(A); +; } +; +; void bar(int *A) { +; baz(A - 33); +; } +; +; void baz(int *A) { +; A[100] = 0; +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +; CHECK: define dso_local void @foo(i32* nocapture nonnull dereferenceable(536) %A) +define dso_local void @foo(i32* %A) { +entry: + call void @bar(i32* %A) + ret void +} + +; CHECK: define dso_local void @bar(i32* nocapture nonnull dereferenceable(536) %B) +define dso_local void @bar(i32* %B) { +entry: + %add.ptr = getelementptr inbounds i32, i32* %B, i64 -33 + call void @baz(i32* %add.ptr) + ret void +} + +define dso_local void @baz(i32* %C) { +entry: + %arrayidx = getelementptr inbounds i32, i32* %C, i64 100 + store i32 0, i32* %arrayidx, align 4 + ret void +} + Index: test/Transforms/FunctionAttrs/attribute_propagation_chain.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/attribute_propagation_chain.ll @@ -0,0 +1,83 @@ +; RUN: opt -functionattrs -S < %s | FileCheck %s +; +; void a(int *A) { +; A[-4] = 0; +; } +; void b(int *A) { +; A[100] = 0; +; a(A); +; } +; void c(int *A) { +; b(A); +; } +; void d(int *A) { +; c(A + 1); +; } +; void e(int *A) { +; d(A - 1); +; } +; void f(int *A) { +; e(A); +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define dso_local void @a0(i64* %A) { +entry: + %arrayidx = getelementptr inbounds i64, i64* %A, i64 -3 + %bc8 = bitcast i64* %arrayidx to i8* + store i8 0, i8* %bc8, align 4 + ret void +} + +define dso_local void @a1(i64* %A) { +entry: + %arrayidx = getelementptr inbounds i64, i64* %A, i64 -3 + %bc32 = bitcast i64* %arrayidx to <8 x i32>* + store <8 x i32> undef, <8 x i32>* %bc32, align 16 + ret void +} + +define dso_local void @a2(i64* %A) { +entry: + %arrayidx = getelementptr inbounds i64, i64* %A, i64 -3 + %bc64 = bitcast i64* %arrayidx to <8 x i64>* + store <8 x i64> undef, <8 x i64>* %bc64, align 16 + ret void +} + +define dso_local void @b(i64* %A) { +entry: + %arrayidx = getelementptr inbounds i64, i64* %A, i64 100 + store i64 0, i64* %arrayidx, align 4 + call void @a0(i64* %A) + call void @a1(i64* %A) + call void @a2(i64* %A) + ret void +} + +define dso_local void @c(i64* %A) { +entry: + call void @b(i64* %A) + ret void +} + +define dso_local void @d(i64* %A) { +entry: + %add.ptr = getelementptr inbounds i64, i64* %A, i64 1 + call void @c(i64* nonnull %add.ptr) + ret void +} + +define dso_local void @e(i64* %A) { +entry: + %add.ptr = getelementptr inbounds i64, i64* %A, i64 -1 + call void @d(i64* nonnull %add.ptr) + ret void +} + +define dso_local void @f(i64* %A) { +entry: + call void @e(i64* %A) + ret void +} Index: test/Transforms/FunctionAttrs/internal_callee.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/internal_callee.ll @@ -0,0 +1,64 @@ +; RUN: opt -S -functionattrs < %s | FileCheck %s +; +; Check that we derive the noalias and dereferenceable_or_null attribute +; for the argument of the rec_internal function. +; +; If nonnull propagation is enabled we should combine dereferenceable_or_null +; and nonnull to dereferenceable. +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +; Function Attrs: noinline nounwind uwtable +define dso_local void @g(i32* noalias dereferenceable_or_null(4) %A) #0 { +entry: + call void @rec_internal(i32* nonnull %A) + ret void +} + +; Function Attrs: noinline nounwind uwtable +define dso_local void @h() #0 { +entry: + %A = alloca i32, align 4 + store i32 5, i32* %A, align 4 + call void @rec_internal(i32* nonnull %A) + ret void +} + +; CHECK: define internal void @rec_internal(i32* noalias nocapture nonnull dereferenceable(4) %A) +; +; Function Attrs: noinline nounwind uwtable +define internal void @rec_internal(i32* %A) #1 { +entry: + %0 = load i32, i32* %A, align 4 + %sub = add nsw i32 %0, -1 + store i32 %sub, i32* %A, align 4 + %tobool = icmp eq i32 %sub, 0 + br i1 %tobool, label %if.end, label %if.then + +if.then: ; preds = %entry + call void @rec_internal(i32* %A) + br label %if.end + +if.end: ; preds = %entry, %if.then + ret void +} + +; CHECK: define void @rec(i32* nocapture nonnull dereferenceable(4) %A) +define void @rec(i32* %A) #0 { +entry: + %0 = load i32, i32* %A, align 4 + %sub = add nsw i32 %0, -1 + store i32 %sub, i32* %A, align 4 + %tobool = icmp eq i32 %sub, 0 + br i1 %tobool, label %if.end, label %if.then + +if.then: ; preds = %entry + call void @rec(i32* %A) + br label %if.end + +if.end: ; preds = %entry, %if.then + ret void +} + +attributes #0 = { noinline nounwind uwtable } +attributes #1 = { argmemonly noinline nounwind uwtable } Index: test/Transforms/FunctionAttrs/internal_large-agg.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/internal_large-agg.ll @@ -0,0 +1,67 @@ +; RUN: opt -S -functionattrs < %s | FileCheck %s +; RUN: opt -S -functionattrs -rpo-functionattrs -enable-nonnull-arg-prop < %s | FileCheck %s +; +; This test was taken from D4609, slightly simplified, and ported to +; the new encoding. +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +%struct.s = type { [65280 x i32] } +%struct.x = type opaque +%struct.x.0 = type opaque + +; CHECK: define void @bar() + +define void @bar() { +entry: + %x = alloca %struct.s, align 32 + %y = alloca %struct.s, align 4 + %0 = bitcast %struct.s* %x to i8* + call void @llvm.lifetime.start(i64 261120, i8* %0) + %1 = bitcast %struct.s* %y to i8* + call void @llvm.lifetime.start(i64 261120, i8* %1) + br label %for.body + +for.body: ; preds = %for.body, %entry + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %arrayidx = getelementptr inbounds %struct.s, %struct.s* %x, i64 0, i32 0, i64 %indvars.iv + %2 = trunc i64 %indvars.iv to i32 + store i32 %2, i32* %arrayidx, align 4 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 17800 + br i1 %exitcond, label %for.end, label %for.body + +for.end: ; preds = %for.body + %3 = bitcast %struct.s* %y to %struct.x* + call fastcc void @foo(%struct.s* %x, %struct.x* %3) + call void @llvm.lifetime.end(i64 261120, i8* %1) + call void @llvm.lifetime.end(i64 261120, i8* %0) + ret void +} + +declare void @llvm.lifetime.start(i64, i8* nocapture) + +; CHECK: define internal fastcc void @foo(%struct.s* noalias nocapture nonnull readonly dereferenceable(261120) %x, %struct.x* noalias nonnull dereferenceable(261120) %y) + +define internal fastcc void @foo(%struct.s* %x, %struct.x* %y) { +entry: + br label %for.body + +for.body: ; preds = %for.body, %entry + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %sum.05 = phi i32 [ 0, %entry ], [ %add, %for.body ] + %arrayidx = getelementptr inbounds %struct.s, %struct.s* %x, i64 0, i32 0, i64 %indvars.iv + %0 = load i32, i32* %arrayidx, align 4 + %add = add nsw i32 %0, %sum.05 + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + %exitcond = icmp eq i64 %indvars.iv.next, 16000 + br i1 %exitcond, label %for.end, label %for.body + +for.end: ; preds = %for.body + %1 = bitcast %struct.x* %y to %struct.x.0* + tail call void @goo(i32 %add, %struct.x.0* %1) + ret void +} + +declare void @llvm.lifetime.end(i64, i8* nocapture) + +declare void @goo(i32, %struct.x.0*) Index: test/Transforms/FunctionAttrs/internal_malloc.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/internal_malloc.ll @@ -0,0 +1,33 @@ +; RUN: opt -S -functionattrs < %s | FileCheck %s +; +; This test was taken from D4609, slightly simplified, and ported to +; the new encoding. +; +; TODO: It seems no pass determines the initial dereferenceable_or_null +; attribute for the malloc so we have to place it ourselves. +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define i32 @bar() { +entry: + %call = tail call noalias dereferenceable_or_null(12345) i8* @malloc(i64 12345) + %0 = bitcast i8* %call to i32* + store i32 10, i32* %0, align 4 + tail call fastcc void @foo(i32* %0) + ret i32 0 +} + +declare noalias i8* @malloc(i64) + + +; CHECK: define internal fastcc void @foo(i32* noalias nonnull dereferenceable(12345) %x) + +define internal fastcc void @foo(i32* %x) { +entry: + %arrayidx = getelementptr inbounds i32, i32* %x, i64 5 + store i32 10, i32* %arrayidx, align 4 + tail call void @goo(i32* %x) + ret void +} + +declare void @goo(i32*) Index: test/Transforms/FunctionAttrs/internal_noalias.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/internal_noalias.ll @@ -0,0 +1,53 @@ +; RUN: opt -S -functionattrs -mem2reg -functionattrs < %s | FileCheck %s +; +; Check that we derive noalias attributes for the arguments of the +; noalias_args_argmem function from its call sites. +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +; Function Attrs: noinline nounwind uwtable +define dso_local i32 @visible(i32* noalias %A, i32* noalias %B) #0 { +entry: + %call1 = call i32 @noalias_args(i32* %A, i32* %B) + %call2 = call i32 @noalias_args_argmem(i32* %A, i32* %B) + %add = add nsw i32 %call1, %call2 + ret i32 %add +} + +; CHECK: define internal i32 @noalias_args(i32* noalias nocapture nonnull readonly dereferenceable(4) %A, i32* noalias nocapture nonnull readonly dereferenceable(4) %B) +; +; Function Attrs: noinline nounwind uwtable +define internal i32 @noalias_args(i32* %A, i32* %B) #0 { +entry: + %0 = load i32, i32* %A, align 4 + %1 = load i32, i32* %B, align 4 + %add = add nsw i32 %0, %1 + %call = call i32 @noalias_args_argmem(i32* %A, i32* %B) + %add2 = add nsw i32 %add, %call + ret i32 %add2 +} + +; CHECK: define internal i32 @noalias_args_argmem(i32* noalias nocapture nonnull readonly dereferenceable(4) %A, i32* noalias nocapture nonnull readonly dereferenceable(4) %B) +; +; Function Attrs: noinline nounwind uwtable +define internal i32 @noalias_args_argmem(i32* %A, i32* %B) #1 { +entry: + %0 = load i32, i32* %A, align 4 + %1 = load i32, i32* %B, align 4 + %add = add nsw i32 %0, %1 + ret i32 %add +} + +; Function Attrs: noinline nounwind uwtable +define dso_local i32 @visible_local(i32* %A) #0 { +entry: + %B = alloca i32, align 4 + store i32 5, i32* %B, align 4 + %call1 = call i32 @noalias_args(i32* %A, i32* nonnull %B) + %call2 = call i32 @noalias_args_argmem(i32* %A, i32* nonnull %B) + %add = add nsw i32 %call1, %call2 + ret i32 %add +} + +attributes #0 = { noinline nounwind uwtable } +attributes #1 = { argmemonly noinline nounwind uwtable } Index: test/Transforms/FunctionAttrs/naked_functions.ll =================================================================== --- test/Transforms/FunctionAttrs/naked_functions.ll +++ test/Transforms/FunctionAttrs/naked_functions.ll @@ -9,7 +9,7 @@ define i32 @bar() { entry: %call = call i32 @foo(i32* @g) -; CHECK: %call = call i32 @foo(i32* @g) +; CHECK: %call = call i32 @foo(i32* nonnull @g) ret i32 %call } Index: test/Transforms/FunctionAttrs/noalias_phi.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/noalias_phi.ll @@ -0,0 +1,65 @@ +; RUN: opt -S -functionattrs < %s | FileCheck %s +; +; int *foo(int Off, int N) { +; int *A = malloc(N); +; while (Off-- > 0) +; *(A++) = Off; +; return A; +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +; CHECK: define dso_local noalias i32* @foo(i32 %Off, i32 %N) { +define dso_local i32* @foo(i32 %Off, i32 %N) { +entry: + %conv = sext i32 %N to i64 + %call = call i8* @malloc(i64 %conv) + %tmp = bitcast i8* %call to i32* + br label %while.cond + +while.cond: ; preds = %while.body, %entry + %A.0 = phi i32* [ %tmp, %entry ], [ %incdec.ptr, %while.body ] + %Off.addr.0 = phi i32 [ %Off, %entry ], [ %dec, %while.body ] + %dec = add nsw i32 %Off.addr.0, -1 + %cmp = icmp sgt i32 %Off.addr.0, 0 + br i1 %cmp, label %while.body, label %while.end + +while.body: ; preds = %while.cond + %incdec.ptr = getelementptr inbounds i32, i32* %A.0, i64 1 + store i32 %dec, i32* %A.0, align 4 + br label %while.cond + +while.end: ; preds = %while.cond + %A.0.lcssa = phi i32* [ %A.0, %while.cond ] + ret i32* %A.0.lcssa +} + +declare dso_local noalias i8* @malloc(i64) + + +; CHECK: define dso_local noalias i32* @bar(i32 %Off, i32 %N) { +define dso_local i32* @bar(i32 %Off, i32 %N) { +entry: + %conv = sext i32 %N to i64 + %call = call noalias i8* @mymalloc(i64 %conv) + %tmp = bitcast i8* %call to i32* + br label %while.cond + +while.cond: ; preds = %while.body, %entry + %A.0 = phi i32* [ %tmp, %entry ], [ %incdec.ptr, %while.body ] + %Off.addr.0 = phi i32 [ %Off, %entry ], [ %dec, %while.body ] + %dec = add nsw i32 %Off.addr.0, -1 + %cmp = icmp sgt i32 %Off.addr.0, 0 + br i1 %cmp, label %while.body, label %while.end + +while.body: ; preds = %while.cond + %incdec.ptr = getelementptr inbounds i32, i32* %A.0, i64 1 + store i32 %dec, i32* %A.0, align 4 + br label %while.cond + +while.end: ; preds = %while.cond + %A.0.lcssa = phi i32* [ %A.0, %while.cond ] + ret i32* %A.0.lcssa +} + +declare dso_local i8* @mymalloc(i64) Index: test/Transforms/FunctionAttrs/nonnull-global.ll =================================================================== --- test/Transforms/FunctionAttrs/nonnull-global.ll +++ test/Transforms/FunctionAttrs/nonnull-global.ll @@ -1,11 +1,25 @@ ; RUN: opt -S -functionattrs %s | FileCheck %s ; RUN: opt -S -passes=function-attrs %s | FileCheck %s +; Note that @a might be at address '0', according to the !absolute_symbol +; metadata, _but_ only in @bar this is actually allowed. In @foo, null is +; not a valid pointer to be referenced while @a has to be a dereferenceable +; address. Thus, for @foo we derive the return attribute nonnull and for +; @bar we won't. + @a = external global i8, !absolute_symbol !0 -; CHECK-NOT: define nonnull +; CHECK: define nonnull dereferenceable(1) define i8* @foo() { ret i8* @a } +; CHECK: define dereferenceable_or_null(1) +; CHECK-NOT: nonnull +define i8* @bar() #0 { + ret i8* @a +} + +attributes #0 = { "null-pointer-is-valid"="true" } + !0 = !{i64 0, i64 256} Index: test/Transforms/FunctionAttrs/nonnull.ll =================================================================== --- test/Transforms/FunctionAttrs/nonnull.ll +++ test/Transforms/FunctionAttrs/nonnull.ll @@ -19,7 +19,7 @@ ; Given an SCC where one of the functions can not be marked nonnull, ; can we still mark the other one which is trivially nonnull define i8* @scc_binder() { -; CHECK: define i8* @scc_binder +; CHECK: define noalias i8* @scc_binder call i8* @test3() ret i8* null } @@ -35,13 +35,13 @@ ; nonnull if neither can ever return null. (In this case, they ; just never return period.) define i8* @test4_helper() { -; CHECK: define noalias nonnull i8* @test4_helper +; CHECK: define noalias nonnull dereferenceable(1073741824) i8* @test4_helper %ret = call i8* @test4() ret i8* %ret } define i8* @test4() { -; CHECK: define noalias nonnull i8* @test4 +; CHECK: define noalias nonnull dereferenceable(1073741824) i8* @test4 %ret = call i8* @test4_helper() ret i8* %ret } @@ -90,7 +90,7 @@ define void @parent1(i8* %a, i8* %b, i8* %c) { ; CHECK-LABEL: @parent1(i8* %a, i8* %b, i8* %c) ; CHECK-NEXT: call void @use3(i8* %c, i8* %a, i8* %b) -; CHECK-NEXT: call void @use3nonnull(i8* %b, i8* %c, i8* %a) +; CHECK-NEXT: call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a) ; CHECK-NEXT: ret void ; call void @use3(i8* %c, i8* %a, i8* %b) @@ -102,8 +102,8 @@ define void @parent2(i8* %a, i8* %b, i8* %c) { ; CHECK-LABEL: @parent2(i8* nonnull %a, i8* nonnull %b, i8* nonnull %c) -; CHECK-NEXT: call void @use3nonnull(i8* %b, i8* %c, i8* %a) -; CHECK-NEXT: call void @use3(i8* %c, i8* %a, i8* %b) +; CHECK-NEXT: call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a) +; CHECK-NEXT: call void @use3(i8* nonnull %c, i8* nonnull %a, i8* nonnull %b) ; CHECK-NEXT: ret void ; call void @use3nonnull(i8* %b, i8* %c, i8* %a) @@ -115,8 +115,8 @@ define void @parent3(i8* %a, i8* %b, i8* %c) { ; CHECK-LABEL: @parent3(i8* nonnull %a, i8* %b, i8* %c) -; CHECK-NEXT: call void @use1nonnull(i8* %a) -; CHECK-NEXT: call void @use3(i8* %c, i8* %b, i8* %a) +; CHECK-NEXT: call void @use1nonnull(i8* nonnull %a) +; CHECK-NEXT: call void @use3(i8* %c, i8* %b, i8* nonnull %a) ; CHECK-NEXT: ret void ; call void @use1nonnull(i8* %a) @@ -128,9 +128,9 @@ define void @parent4(i8* %a, i8* %b, i8* %c) { ; CHECK-LABEL: @parent4(i8* %a, i8* nonnull %b, i8* nonnull %c) -; CHECK-NEXT: call void @use2nonnull(i8* %c, i8* %b) -; CHECK-NEXT: call void @use2(i8* %a, i8* %c) -; CHECK-NEXT: call void @use1(i8* %b) +; CHECK-NEXT: call void @use2nonnull(i8* nonnull %c, i8* nonnull %b) +; CHECK-NEXT: call void @use2(i8* %a, i8* nonnull %c) +; CHECK-NEXT: call void @use1(i8* nonnull %b) ; CHECK-NEXT: ret void ; call void @use2nonnull(i8* %c, i8* %b) @@ -147,7 +147,7 @@ ; CHECK-LABEL: @parent5(i8* %a, i1 %a_is_notnull) ; CHECK-NEXT: br i1 %a_is_notnull, label %t, label %f ; CHECK: t: -; CHECK-NEXT: call void @use1nonnull(i8* %a) +; CHECK-NEXT: call void @use1nonnull(i8* nonnull %a) ; CHECK-NEXT: ret void ; CHECK: f: ; CHECK-NEXT: ret void @@ -166,7 +166,7 @@ define i8 @parent6(i8* %a, i8* %b) { ; CHECK-LABEL: @parent6(i8* %a, i8* %b) ; CHECK-NEXT: [[C:%.*]] = load volatile i8, i8* %b -; CHECK-NEXT: call void @use1nonnull(i8* %a) +; CHECK-NEXT: call void @use1nonnull(i8* nonnull %a) ; CHECK-NEXT: ret i8 [[C]] ; %c = load volatile i8, i8* %b @@ -178,8 +178,8 @@ define i8 @parent7(i8* %a) { ; CHECK-LABEL: @parent7(i8* nonnull %a) -; CHECK-NEXT: [[RET:%.*]] = call i8 @use1safecall(i8* %a) -; CHECK-NEXT: call void @use1nonnull(i8* %a) +; CHECK-NEXT: [[RET:%.*]] = call i8 @use1safecall(i8* nonnull %a) +; CHECK-NEXT: call void @use1nonnull(i8* nonnull %a) ; CHECK-NEXT: ret i8 [[RET]] ; %ret = call i8 @use1safecall(i8* %a) @@ -194,7 +194,7 @@ define i1 @parent8(i8* %a, i8* %bogus1, i8* %b) personality i8* bitcast (i32 (...)* @esfp to i8*){ ; CHECK-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b) ; CHECK-NEXT: entry: -; CHECK-NEXT: invoke void @use2nonnull(i8* %a, i8* %b) +; CHECK-NEXT: invoke void @use2nonnull(i8* nonnull %a, i8* nonnull %b) ; CHECK-NEXT: to label %cont unwind label %exc ; CHECK: cont: ; CHECK-NEXT: [[NULL_CHECK:%.*]] = icmp eq i8* %b, null @@ -237,4 +237,16 @@ ret i32 addrspace(3)* %q } + +declare i8* @strrchr(i8*, i32) + +define internal fastcc nonnull i8* @select(i8* nonnull readonly %str) unnamed_addr #3 { +entry: + %call = call i8* @strrchr(i8* %str, i32 47) #8 + %tobool = icmp eq i8* %call, null + %add.ptr = getelementptr inbounds i8, i8* %call, i64 1 + %cond = select i1 %tobool, i8* %str, i8* %add.ptr + ret i8* %cond +} + attributes #0 = { "null-pointer-is-valid"="true" } Index: test/Transforms/FunctionAttrs/readattrs.ll =================================================================== --- test/Transforms/FunctionAttrs/readattrs.ll +++ test/Transforms/FunctionAttrs/readattrs.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -functionattrs -S | FileCheck %s +; RUN: opt < %s -functionattrs -mem2reg -functionattrs -S | FileCheck %s ; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(function-attrs)' -S | FileCheck %s @x = global i32 0 @@ -32,7 +32,7 @@ ret void } -; CHECK: define void @test5(i8** nocapture %p, i8* %q) +; CHECK: define void @test5(i8** nocapture nonnull dereferenceable(8) %p, i8* %q) ; Missed optz'n: we could make %q readnone, but don't break test6! define void @test5(i8** %p, i8* %q) { store i8* %q, i8** %p @@ -40,7 +40,7 @@ } declare void @test6_1() -; CHECK: define void @test6_2(i8** nocapture %p, i8* %q) +; CHECK: define void @test6_2(i8** nocapture nonnull dereferenceable(8) %p, i8* %q) ; This is not a missed optz'n. define void @test6_2(i8** %p, i8* %q) { store i8* %q, i8** %p @@ -60,7 +60,7 @@ ret i32* %p } -; CHECK: define void @test8_2(i32* %p) +; CHECK: define void @test8_2(i32* nonnull dereferenceable(4) %p) define void @test8_2(i32* %p) { entry: %call = call i32* @test8_1(i32* %p) Index: test/Transforms/FunctionAttrs/recursion_and_phi.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/recursion_and_phi.ll @@ -0,0 +1,43 @@ +; RUN: opt -S -functionattrs %s | FileCheck %s +; RUN: opt -S -passes=function-attrs %s | FileCheck %s + +%struct.splay_node = type { i64, i64, %struct.splay_node*, %struct.splay_node* } + +; CHECK: define dso_local nonnull dereferenceable(8) %struct.splay_node* @find(%struct.splay_node* nonnull readonly dereferenceable(8) %root, i64 %key) local_unnamed_addr #0 { +define dso_local %struct.splay_node* @find(%struct.splay_node* readonly %root, i64 %key) local_unnamed_addr #0 { +entry: + %key1 = getelementptr inbounds %struct.splay_node, %struct.splay_node* %root, i64 0, i32 0 + %0 = load i64, i64* %key1, align 8 + %cmp = icmp slt i64 %0, %key + br i1 %cmp, label %land.lhs.true, label %if.else + +land.lhs.true: ; preds = %entry + %right = getelementptr inbounds %struct.splay_node, %struct.splay_node* %root, i64 0, i32 3 + %1 = load %struct.splay_node*, %struct.splay_node** %right, align 8 + %cmp2 = icmp eq %struct.splay_node* %1, null + br i1 %cmp2, label %if.else, label %if.then + +if.then: ; preds = %land.lhs.true + %call = call %struct.splay_node* @find(%struct.splay_node* %1, i64 %key) + br label %return + +if.else: ; preds = %land.lhs.true, %entry + %2 = load i64, i64* %key1, align 8 + %cmp6 = icmp sgt i64 %2, %key + br i1 %cmp6, label %land.lhs.true7, label %return + +land.lhs.true7: ; preds = %if.else + %left = getelementptr inbounds %struct.splay_node, %struct.splay_node* %root, i64 0, i32 2 + %3 = load %struct.splay_node*, %struct.splay_node** %left, align 8 + %cmp8 = icmp eq %struct.splay_node* %3, null + br i1 %cmp8, label %return, label %if.then9 + +if.then9: ; preds = %land.lhs.true7 + %call11 = call %struct.splay_node* @find(%struct.splay_node* %3, i64 %key) + br label %return + +return: ; preds = %if.else, %land.lhs.true7, %if.then9, %if.then + %retval.0 = phi %struct.splay_node* [ %call, %if.then ], [ %call11, %if.then9 ], [ %root, %land.lhs.true7 ], [ %root, %if.else ] + ret %struct.splay_node* %retval.0 +} + Index: test/Transforms/FunctionAttrs/sql_malloc.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionAttrs/sql_malloc.ll @@ -0,0 +1,99 @@ +; RUN: opt -S -functionattrs < %s | FileCheck %s + +declare noalias i8* @malloc(i64) +@mem.0 = common global i64 0, align 4 +@mem.1 = common global void (i8*, i64, i32)* null, align 4 +@mem.2 = common global i8* null, align 4 +@mem.3 = common global i1 0, align 4 +@mem.4 = common global i64* null, align 4 +@mem.5 = common global i64 0, align 4 +@mem.6 = common global i64 0, align 4 + +; CHECK: define dso_local noalias i8* @sqlite3_malloc(i32 %nBytes) +define dso_local i8* @sqlite3_malloc(i32 %nBytes) { +entry: + %cmp = icmp sgt i32 %nBytes, 0 + br i1 %cmp, label %if.then, label %if.end23 + +if.then: ; preds = %entry + %0 = load i64*, i64** @mem.4, align 8 + %cmp.i = icmp eq i64* %0, null + br i1 %cmp.i, label %if.then.i, label %enterMem.exit + +if.then.i: ; preds = %if.then + store i64* inttoptr (i64 8 to i64*), i64** @mem.4, align 8 + br label %enterMem.exit + +enterMem.exit: ; preds = %if.then, %if.then.i + %1 = load void (i8*, i64, i32)*, void (i8*, i64, i32)** @mem.1, align 8 + %cmp1 = icmp eq void (i8*, i64, i32)* %1, null + br i1 %cmp1, label %if.end, label %land.lhs.true + +land.lhs.true: ; preds = %enterMem.exit + %2 = load i64, i64* @mem.5, align 8 + %conv = sext i32 %nBytes to i64 + %add = add nsw i64 %2, %conv + %3 = load i64, i64* @mem.0, align 8 + %cmp2 = icmp slt i64 %add, %3 + br i1 %cmp2, label %if.end, label %if.then4 + +if.then4: ; preds = %land.lhs.true + %.b.i38 = load i1, i1* @mem.3, align 8 + br i1 %.b.i38, label %if.end, label %if.end.i40 + +if.end.i40: ; preds = %if.then4 + store i1 true, i1* @mem.3, align 8 + %4 = load i8*, i8** @mem.2, align 8 + tail call void %1(i8* %4, i64 %2, i32 %nBytes) #6 + store i1 false, i1* @mem.3, align 8 + br label %if.end + +if.end: ; preds = %if.end.i40, %if.then4, %land.lhs.true, %enterMem.exit + %add5 = add nsw i32 %nBytes, 8 + %conv6 = sext i32 %add5 to i64 + %call = tail call noalias i8* @malloc(i64 %conv6) #6 + %cmp7 = icmp eq i8* %call, null + br i1 %cmp7, label %if.then9, label %if.then14 + +if.then9: ; preds = %if.end + %5 = load void (i8*, i64, i32)*, void (i8*, i64, i32)** @mem.1, align 8 + %cmp.i36 = icmp eq void (i8*, i64, i32)* %5, null + %.b.i = load i1, i1* @mem.3, align 8 + %or.cond.i = or i1 %cmp.i36, %.b.i + br i1 %or.cond.i, label %if.end13, label %if.end.i + +if.end.i: ; preds = %if.then9 + store i1 true, i1* @mem.3, align 8 + %6 = load i64, i64* @mem.5, align 8 + %7 = load i8*, i8** @mem.2, align 8 + tail call void %5(i8* %7, i64 %6, i32 %nBytes) #6 + store i1 false, i1* @mem.3, align 8 + br label %if.end13 + +if.end13: ; preds = %if.end.i, %if.then9 + %call12 = tail call noalias i8* @malloc(i64 %conv6) #6 + %tobool = icmp eq i8* %call12, null + br i1 %tobool, label %if.end23, label %if.then14 + +if.then14: ; preds = %if.end, %if.end13 + %p.0.in43 = phi i8* [ %call12, %if.end13 ], [ %call, %if.end ] + %p.0 = bitcast i8* %p.0.in43 to i64* + %conv15 = sext i32 %nBytes to i64 + store i64 %conv15, i64* %p.0, align 8 + %incdec.ptr = getelementptr inbounds i8, i8* %p.0.in43, i64 8 + %8 = load i64, i64* @mem.5, align 8 + %add17 = add nsw i64 %8, %conv15 + store i64 %add17, i64* @mem.5, align 8 + %9 = load i64, i64* @mem.6, align 8 + %cmp18 = icmp sgt i64 %add17, %9 + br i1 %cmp18, label %if.then20, label %if.end23 + +if.then20: ; preds = %if.then14 + store i64 %add17, i64* @mem.6, align 8 + br label %if.end23 + +if.end23: ; preds = %if.end13, %if.then20, %if.then14, %entry + %10 = phi i8* [ %incdec.ptr, %if.then20 ], [ %incdec.ptr, %if.then14 ], [ null, %if.end13 ], [ null, %entry ] + ret i8* %10 +} + Index: test/Transforms/Inline/delete-call.ll =================================================================== --- test/Transforms/Inline/delete-call.ll +++ test/Transforms/Inline/delete-call.ll @@ -2,7 +2,7 @@ ; RUN: opt -S -inline -stats < %s 2>&1 | FileCheck %s ; CHECK: Number of functions inlined -; RUN: opt -S -inline -functionattrs -stats < %s 2>&1 | FileCheck -check-prefix=CHECK-FUNCTIONATTRS %s +; RUN: opt -S -functionattrs -inline -stats < %s 2>&1 | FileCheck -check-prefix=CHECK-FUNCTIONATTRS %s ; CHECK-FUNCTIONATTRS: Number of call sites deleted, not inlined target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32" Index: test/Transforms/Reassociate/reassociate-deadinst.ll =================================================================== --- test/Transforms/Reassociate/reassociate-deadinst.ll +++ test/Transforms/Reassociate/reassociate-deadinst.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -inline -functionattrs -reassociate -S | FileCheck %s +; RUN: opt < %s -functionattrs -inline -reassociate -S | FileCheck %s ; CHECK-NOT: func1 ; CHECK-LABEL: main