diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -102,6 +102,7 @@ #include "llvm/ADT/MapVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" +#include "llvm/ADT/iterator.h" #include "llvm/Analysis/AssumeBundleQueries.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CGSCCPassManager.h" @@ -126,6 +127,7 @@ struct AbstractAttribute; struct InformationCache; struct AAIsDead; +class AttributorCallGraph; class AAManager; class AAResults; @@ -1760,6 +1762,7 @@ ///} friend AADepGraph; + friend AttributorCallGraph; }; /// An interface to query the internal state of an abstract attribute. @@ -3855,6 +3858,125 @@ static const char ID; }; +struct AACallGraphNode; +struct AACallEdges; + +/// An Iterator for call edges, creates AACallEdges attributes in a lazy way. +/// This iterator becomes invalid if the underlying edge list changes. +/// So This shouldn't outlive a iteration of Attributor. +class CallEdgeIterator + : public iterator_adaptor_base::iterator> { + CallEdgeIterator(Attributor &A, SetVector::iterator Begin) + : iterator_adaptor_base(Begin), A(A) {} + +public: + const AACallGraphNode &operator*() const; + +private: + Attributor &A; + friend AACallEdges; + friend AttributorCallGraph; +}; + +struct AACallGraphNode { + virtual CallEdgeIterator optimisticEdgesBegin() const = 0; + virtual CallEdgeIterator optimisticEdgesEnd() const = 0; + + /// Iterator range for exploring the call graph. + iterator_range optimisticEdgesRange() { + return iterator_range(optimisticEdgesBegin(), + optimisticEdgesEnd()); + } +}; + +/// An abstract state for querying live call edges. +/// This interface uses the Attributor's optimistic liveness +/// information to compute the edges that are alive. +struct AACallEdges : public StateWrapper, + AACallGraphNode { + using Base = StateWrapper; + + AACallEdges(const IRPosition &IRP, Attributor &A) : Base(IRP), A(A) {} + + /// Get the optimistic edges. + virtual const SetVector &getOptimisticEdges() const = 0; + + /// Iterator for exploring the call graph. + CallEdgeIterator optimisticEdgesBegin() const override { + return CallEdgeIterator(A, getOptimisticEdges().begin()); + } + + /// Iterator for exploring the call graph. + CallEdgeIterator optimisticEdgesEnd() const override { + return CallEdgeIterator(A, getOptimisticEdges().end()); + } + + /// Create an abstract attribute view for the position \p IRP. + static AACallEdges &createForPosition(const IRPosition &IRP, Attributor &A); + + /// See AbstractAttribute::getName() + const std::string getName() const override { return "AACallEdges"; } + + /// See AbstractAttribute::getIdAddr() + const char *getIdAddr() const override { return &ID; } + + /// This function should return true if the type of the \p AA is AACallEdges. + static bool classof(const AbstractAttribute *AA) { + return (AA->getIdAddr() == &ID); + } + + /// Unique ID (due to the unique address) + static const char ID; + +private: + /// Reference to Attributor needed for GraphTraits implementation. + Attributor &A; + friend CallEdgeIterator; +}; + +// Synthetic root node for the Attributor's internal call graph. +struct AttributorCallGraph : AACallGraphNode { + AttributorCallGraph(Attributor &A) : A(A) {} + + CallEdgeIterator optimistcEdgesBegin() const { + return CallEdgeIterator(A, A.Functions.begin()); + } + + CallEdgeIterator optimistcEdgesEnd() const { + return CallEdgeIterator(A, A.Functions.end()); + } + + Attributor &A; +}; + +template <> struct GraphTraits { + using NodeRef = AACallGraphNode *; + using ChildIteratorType = CallEdgeIterator; + + static CallEdgeIterator child_begin(AACallEdges *Node) { + return Node->optimisticEdgesBegin(); + } + + static CallEdgeIterator child_end(AACallEdges *Node) { + return Node->optimisticEdgesEnd(); + } +}; + +template <> +struct GraphTraits + : public GraphTraits { + static AACallGraphNode *getEntryNode(AttributorCallGraph *G) { return G; } + + static CallEdgeIterator nodes_begin(const AttributorCallGraph *G) { + return G->optimisticEdgesBegin(); + } + + static CallEdgeIterator nodes_end(const AttributorCallGraph *G) { + return G->optimisticEdgesEnd(); + } +}; + /// Run options, used by the pass manager. enum AttributorRunOption { NONE = 0, diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp --- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -134,6 +134,7 @@ PIPE_OPERATOR(AAUndefinedBehavior) PIPE_OPERATOR(AAPotentialValues) PIPE_OPERATOR(AANoUndef) +PIPE_OPERATOR(AACallEdges) #undef PIPE_OPERATOR } // namespace llvm @@ -8133,8 +8134,74 @@ /// See AbstractAttribute::trackStatistics() void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noundef) } }; + +struct AACallEdgesFunction : public AACallEdges { + AACallEdgesFunction(const IRPosition &IRP, Attributor &A) + : AACallEdges(IRP, A) {} + + /// See AbstractAttribute::updateImpl(...). + ChangeStatus updateImpl(Attributor &A) override { + ChangeStatus Change = ChangeStatus::UNCHANGED; + + // A dependency will be added if the information is used. + const AAIsDead &LivenessAA = + A.getAAFor(*this, getIRPosition(), DepClassTy::NONE); + + // Opcodes of callable instructions. These all ineherit from CallBase. + auto Opcodes = {(unsigned)Instruction::Invoke, + (unsigned)Instruction::CallBr, (unsigned)Instruction::Call}; + + auto AddCalledFunction = [&](Function *Fn) { + // Track the changes. + if (CalledFunctions.insert(Fn)) + Change = Change | ChangeStatus::CHANGED; + }; + + auto ProcessCallInst = [&](Instruction &Inst) { + CallBase &CB = static_cast(Inst); + Function *Callee = CB.getCalledFunction(); + // The most simple case. + if (Callee) + AddCalledFunction(Callee); + + // Process callback functions. + SmallVector CallbackUses; + AbstractCallSite::getCallbackUses(CB, CallbackUses); + for (const Use *U : CallbackUses) { + AbstractCallSite ACS(U); + Function *Fn = ACS.getCalledFunction(); + Value *Val = U->get(); + // Ask the attributor if the value is alive. + if (Fn && !A.isAssumedDead(IRPosition::value(*Val), this, &LivenessAA)) + AddCalledFunction(Fn); + } + return true; + }; + // Visit all callable instructions. + A.checkForAllInstructions(ProcessCallInst, *this, Opcodes); + + return Change; + } + + virtual const SetVector &getOptimisticEdges() const override { + return CalledFunctions; + }; + + const std::string getAsStr() const override { + // TODO: Be more informative. + return "CallEdges"; + } + + void trackStatistics() const override {} + + SetVector CalledFunctions; +}; + } // namespace +const AACallGraphNode &CallEdgeIterator::operator*() const { + return A.getOrCreateAAFor(IRPosition::function(**I)); +} const char AAReturnedValues::ID = 0; const char AANoUnwind::ID = 0; const char AANoSync::ID = 0; @@ -8158,6 +8225,7 @@ const char AAValueConstantRange::ID = 0; const char AAPotentialValues::ID = 0; const char AANoUndef::ID = 0; +const char AACallEdges::ID = 0; // Macro magic to create the static generator function for attributes that // follow the naming scheme. @@ -8277,6 +8345,7 @@ CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack) CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReachability) CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAUndefinedBehavior) +CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AACallEdges) CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAMemoryBehavior)