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" @@ -115,6 +116,7 @@ #include "llvm/IR/PassManager.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/Casting.h" +#include "llvm/Support/GraphWriter.h" #include "llvm/Support/TimeProfiler.h" #include "llvm/Transforms/Utils/CallGraphUpdater.h" @@ -126,6 +128,7 @@ struct AbstractAttribute; struct InformationCache; struct AAIsDead; +struct AttributorCallGraph; class AAManager; class AAResults; @@ -1760,6 +1763,7 @@ ///} friend AADepGraph; + friend AttributorCallGraph; }; /// An interface to query the internal state of an abstract attribute. @@ -3855,6 +3859,156 @@ 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 AACallEdgeIterator + : public iterator_adaptor_base::iterator> { + AACallEdgeIterator(Attributor &A, SetVector::iterator Begin) + : iterator_adaptor_base(Begin), A(A) {} + +public: + AACallGraphNode *operator*() const; + +private: + Attributor &A; + friend AACallEdges; + friend AttributorCallGraph; +}; + +struct AACallGraphNode { + virtual AACallEdgeIterator optimisticEdgesBegin() const = 0; + virtual AACallEdgeIterator optimisticEdgesEnd() const = 0; + + /// Iterator range for exploring the call graph. + iterator_range optimisticEdgesRange() const { + 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. + AACallEdgeIterator optimisticEdgesBegin() const override { + return AACallEdgeIterator(A, getOptimisticEdges().begin()); + } + + /// Iterator for exploring the call graph. + AACallEdgeIterator optimisticEdgesEnd() const override { + return AACallEdgeIterator(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 AACallEdgeIterator; +}; + +// Synthetic root node for the Attributor's internal call graph. +struct AttributorCallGraph : public AACallGraphNode { + AttributorCallGraph(Attributor &A) : A(A) {} + + AACallEdgeIterator optimisticEdgesBegin() const override { + return AACallEdgeIterator(A, A.Functions.begin()); + } + + AACallEdgeIterator optimisticEdgesEnd() const override { + return AACallEdgeIterator(A, A.Functions.end()); + } + + /// Force populate the entire call graph. + void populateAll() const { + for (const AACallGraphNode *AA : optimisticEdgesRange()) { + // Nothing else to do here. + (void)AA; + } + } + + void print(); + + Attributor &A; +}; + +template <> struct GraphTraits { + using NodeRef = AACallGraphNode *; + using ChildIteratorType = AACallEdgeIterator; + + static AACallEdgeIterator child_begin(AACallGraphNode *Node) { + return Node->optimisticEdgesBegin(); + } + + static AACallEdgeIterator child_end(AACallGraphNode *Node) { + return Node->optimisticEdgesEnd(); + } +}; + +template <> +struct GraphTraits + : public GraphTraits { + using nodes_iterator = AACallEdgeIterator; + + static AACallGraphNode *getEntryNode(AttributorCallGraph *G) { + return static_cast(G); + } + + static AACallEdgeIterator nodes_begin(const AttributorCallGraph *G) { + return G->optimisticEdgesBegin(); + } + + static AACallEdgeIterator nodes_end(const AttributorCallGraph *G) { + return G->optimisticEdgesEnd(); + } +}; + +template <> +struct DOTGraphTraits : public DefaultDOTGraphTraits { + DOTGraphTraits(bool Simple = false) : DefaultDOTGraphTraits(Simple) {} + + std::string getNodeLabel(const AACallGraphNode *Node, + const AttributorCallGraph *Graph) { + const AACallEdges *AACE = static_cast(Node); + return AACE->getAssociatedFunction()->getName().str(); + } + + static bool isNodeHidden(const AACallGraphNode *Node, + const AttributorCallGraph *Graph) { + // Hide the synth root. + return static_cast(Graph) == Node; + } +}; + /// Run options, used by the pass manager. enum AttributorRunOption { NONE = 0, diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -148,6 +148,11 @@ cl::desc("Allow the Attributor to do call site specific analysis"), cl::init(false)); +static cl::opt + PrintCallGraph("attributor-print-call-graph", cl::Hidden, + cl::desc("Print Attributor's internal call graph"), + cl::init(false)); + /// Logic operators for the change status enum class. /// ///{ @@ -1466,6 +1471,10 @@ ChangeStatus Attributor::run() { TimeTraceScope TimeScope("Attributor::run"); + AttributorCallGraph ACallGraph(*this); + + if (PrintCallGraph) + ACallGraph.populateAll(); Phase = AttributorPhase::UPDATE; runTillFixpoint(); @@ -1486,6 +1495,9 @@ Phase = AttributorPhase::CLEANUP; ChangeStatus CleanupChange = cleanupIR(); + if (PrintCallGraph) + ACallGraph.print(); + return ManifestChange | CleanupChange; } 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 @@ -30,9 +30,10 @@ #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/NoFolder.h" #include "llvm/Support/CommandLine.h" +#include "llvm/Support/FileSystem.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/IPO/ArgumentPromotion.h" #include "llvm/Transforms/Utils/Local.h" - #include using namespace llvm; @@ -134,6 +135,7 @@ PIPE_OPERATOR(AAUndefinedBehavior) PIPE_OPERATOR(AAPotentialValues) PIPE_OPERATOR(AANoUndef) +PIPE_OPERATOR(AACallEdges) #undef PIPE_OPERATOR } // namespace llvm @@ -8133,8 +8135,81 @@ /// 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); + + 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.checkForAllCallLikeInstructions(ProcessCallInst, *this); + + 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 +AACallGraphNode *AACallEdgeIterator::operator*() const { + return static_cast(const_cast( + &A.getOrCreateAAFor(IRPosition::function(**I)))); +} + +void AttributorCallGraph::print() { + std::string Filename = "AttributorCallGraph.dot"; + std::error_code EC; + + raw_fd_ostream File(Filename, EC, sys::fs::OF_TextWithCRLF); + llvm::WriteGraph(File, this); +} + const char AAReturnedValues::ID = 0; const char AANoUnwind::ID = 0; const char AANoSync::ID = 0; @@ -8158,6 +8233,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 +8353,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) diff --git a/llvm/test/Transforms/Attributor/callgraph.ll b/llvm/test/Transforms/Attributor/callgraph.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/Attributor/callgraph.ll @@ -0,0 +1,47 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -passes=attributor -attributor-print-call-graph -S < %s | FileCheck %s --check-prefixes=CHECK +; RUN: FileCheck %s -input-file=AttributorCallGraph.dot --check-prefix=DOT + + +define dso_local void @func1() { +; CHECK-LABEL: @func1( +; CHECK-NEXT: br label [[TMP2:%.*]] +; CHECK: 1: +; CHECK-NEXT: unreachable +; CHECK: 2: +; CHECK-NEXT: call void (...) @func3() +; CHECK-NEXT: ret void +; + %1 = icmp ne i32 0, 0 + br i1 %1, label %2, label %3 + +2: ; preds = %0 + call void @func2() + br label %3 + +3: ; preds = %2, %0 + call void (...) @func3() + ret void +} + +declare void @func3(...) + +define dso_local void @func2() { +; CHECK-LABEL: @func2( +; CHECK-NEXT: call void (...) @func4() +; CHECK-NEXT: ret void +; + call void (...) @func4() + ret void +} + +declare void @func4(...) + +; DOT-DAG: Node[[FUNC1:0x[a-z0-9]+]] [shape=record,label="{func1}"]; +; DOT-DAG: Node[[FUNC2:0x[a-z0-9]+]] [shape=record,label="{func2}"]; +; DOT-DAG: Node[[FUNC3:0x[a-z0-9]+]] [shape=record,label="{func3}"]; +; DOT-DAG: Node[[FUNC4:0x[a-z0-9]+]] [shape=record,label="{func4}"]; + +; DOT-DAG: Node[[FUNC1]] -> Node[[FUNC3]]; +; DOT-DAG: Node[[FUNC2]] -> Node[[FUNC4]]; +