summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/LazyCallGraph.h118
-rw-r--r--lib/Analysis/LazyCallGraph.cpp122
-rw-r--r--test/Analysis/LazyCallGraph/basic.ll50
3 files changed, 286 insertions, 4 deletions
diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h
index d22f2cf8db..bcd06c2a10 100644
--- a/include/llvm/Analysis/LazyCallGraph.h
+++ b/include/llvm/Analysis/LazyCallGraph.h
@@ -38,8 +38,10 @@
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Module.h"
@@ -100,6 +102,7 @@ class raw_ostream;
class LazyCallGraph {
public:
class Node;
+ class SCC;
typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;
@@ -173,9 +176,16 @@ public:
/// a callee, and facilitate iteration of child nodes in the graph.
class Node {
friend class LazyCallGraph;
+ friend class LazyCallGraph::SCC;
LazyCallGraph *G;
Function &F;
+
+ // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
+ // stored directly within the node.
+ int DFSNumber;
+ int LowLink;
+
mutable NodeVectorT Callees;
SmallPtrSet<Function *, 4> CalleeSet;
@@ -201,6 +211,79 @@ public:
bool operator!=(const Node &N) const { return !operator==(N); }
};
+ /// \brief An SCC of the call graph.
+ ///
+ /// This represents a Strongly Connected Component of the call graph as
+ /// a collection of call graph nodes. While the order of nodes in the SCC is
+ /// stable, it is not any particular order.
+ class SCC {
+ friend class LazyCallGraph;
+ friend class LazyCallGraph::Node;
+
+ SmallSetVector<SCC *, 1> ParentSCCs;
+ SmallVector<Node *, 1> Nodes;
+ SmallPtrSet<Function *, 1> NodeSet;
+
+ SCC() {}
+
+ public:
+ typedef SmallVectorImpl<Node *>::const_iterator iterator;
+
+ iterator begin() const { return Nodes.begin(); }
+ iterator end() const { return Nodes.end(); }
+ };
+
+ /// \brief A post-order depth-first SCC iterator over the call graph.
+ ///
+ /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
+ /// the call graph, walking it lazily in depth-first post-order. That is, it
+ /// always visits SCCs for a callee prior to visiting the SCC for a caller
+ /// (when they are in different SCCs).
+ class postorder_scc_iterator
+ : public std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t, SCC *,
+ SCC *> {
+ friend class LazyCallGraph;
+ friend class LazyCallGraph::Node;
+ typedef std::iterator<std::forward_iterator_tag, SCC *, ptrdiff_t,
+ SCC *, SCC *> BaseT;
+
+ /// \brief Nonce type to select the constructor for the end iterator.
+ struct IsAtEndT {};
+
+ LazyCallGraph *G;
+ SCC *C;
+
+ // Build the begin iterator for a node.
+ postorder_scc_iterator(LazyCallGraph &G) : G(&G) {
+ C = G.getNextSCCInPostOrder();
+ }
+
+ // Build the end iterator for a node. This is selected purely by overload.
+ postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
+ : G(&G), C(nullptr) {}
+
+ public:
+ bool operator==(const postorder_scc_iterator &Arg) {
+ return G == Arg.G && C == Arg.C;
+ }
+ bool operator!=(const postorder_scc_iterator &Arg) {
+ return !operator==(Arg);
+ }
+
+ reference operator*() const { return C; }
+ pointer operator->() const { return operator*(); }
+
+ postorder_scc_iterator &operator++() {
+ C = G->getNextSCCInPostOrder();
+ return *this;
+ }
+ postorder_scc_iterator operator++(int) {
+ postorder_scc_iterator prev = *this;
+ ++*this;
+ return prev;
+ }
+ };
+
/// \brief Construct a graph for the given module.
///
/// This sets up the graph and computes all of the entry points of the graph.
@@ -229,6 +312,18 @@ public:
iterator begin() { return iterator(*this, EntryNodes); }
iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); }
+ postorder_scc_iterator postorder_scc_begin() {
+ return postorder_scc_iterator(*this);
+ }
+ postorder_scc_iterator postorder_scc_end() {
+ return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT());
+ }
+
+ iterator_range<postorder_scc_iterator> postorder_sccs() {
+ return iterator_range<postorder_scc_iterator>(postorder_scc_begin(),
+ postorder_scc_end());
+ }
+
/// \brief Lookup a function in the graph which has already been scanned and
/// added.
Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
@@ -259,12 +354,35 @@ private:
/// \brief Set of the entry nodes to the graph.
SmallPtrSet<Function *, 4> EntryNodeSet;
+ /// \brief Allocator that holds all the call graph SCCs.
+ SpecificBumpPtrAllocator<SCC> SCCBPA;
+
+ /// \brief Maps Function -> SCC for fast lookup.
+ DenseMap<const Function *, SCC *> SCCMap;
+
+ /// \brief The leaf SCCs of the graph.
+ ///
+ /// These are all of the SCCs which have no children.
+ SmallVector<SCC *, 4> LeafSCCs;
+
+ /// \brief Stack of nodes not-yet-processed into SCCs.
+ SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
+
+ /// \brief Set of entry nodes not-yet-processed into SCCs.
+ SmallSetVector<Function *, 4> SCCEntryNodes;
+
+ /// \brief Counter for the next DFS number to assign.
+ int NextDFSNumber;
+
/// \brief Helper to insert a new function, with an already looked-up entry in
/// the NodeMap.
Node *insertInto(Function &F, Node *&MappedN);
/// \brief Helper to copy a node from another graph into this one.
Node *copyInto(const Node &OtherN);
+
+ /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
+ SCC *getNextSCCInPostOrder();
};
// Provide GraphTraits specializations for call graphs.
diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp
index 8a0d00ac49..dd5c7df784 100644
--- a/lib/Analysis/LazyCallGraph.cpp
+++ b/lib/Analysis/LazyCallGraph.cpp
@@ -8,7 +8,7 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/LazyCallGraph.h"
-#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/Instructions.h"
@@ -46,7 +46,8 @@ static void findCallees(
}
}
-LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) : G(&G), F(F) {
+LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F)
+ : G(&G), F(F), DFSNumber(0), LowLink(0) {
SmallVector<Constant *, 16> Worklist;
SmallPtrSet<Constant *, 16> Visited;
// Find all the potential callees in this function. First walk the
@@ -65,7 +66,7 @@ LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) : G(&G), F(F) {
}
LazyCallGraph::Node::Node(LazyCallGraph &G, const Node &OtherN)
- : G(&G), F(OtherN.F), CalleeSet(OtherN.CalleeSet) {
+ : G(&G), F(OtherN.F), DFSNumber(0), LowLink(0), CalleeSet(OtherN.CalleeSet) {
// Loop over the other node's callees, adding the Function*s to our list
// directly, and recursing to add the Node*s.
Callees.reserve(OtherN.Callees.size());
@@ -91,6 +92,12 @@ LazyCallGraph::LazyCallGraph(Module &M) {
Worklist.push_back(GV.getInitializer());
findCallees(Worklist, Visited, EntryNodes, EntryNodeSet);
+
+ for (auto &Entry : EntryNodes)
+ if (Function *F = Entry.dyn_cast<Function *>())
+ SCCEntryNodes.insert(F);
+ else
+ SCCEntryNodes.insert(&Entry.get<Node *>()->getFunction());
}
LazyCallGraph::LazyCallGraph(const LazyCallGraph &G)
@@ -101,11 +108,22 @@ LazyCallGraph::LazyCallGraph(const LazyCallGraph &G)
EntryNodes.push_back(Callee);
else
EntryNodes.push_back(copyInto(*EntryNode.get<Node *>()));
+
+ // Just re-populate the SCCEntryNodes structure so we recompute the SCCs if
+ // needed.
+ for (auto &Entry : EntryNodes)
+ if (Function *F = Entry.dyn_cast<Function *>())
+ SCCEntryNodes.insert(F);
+ else
+ SCCEntryNodes.insert(&Entry.get<Node *>()->getFunction());
}
LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
: BPA(std::move(G.BPA)), EntryNodes(std::move(G.EntryNodes)),
- EntryNodeSet(std::move(G.EntryNodeSet)) {
+ EntryNodeSet(std::move(G.EntryNodeSet)), SCCBPA(std::move(G.SCCBPA)),
+ SCCMap(std::move(G.SCCMap)), LeafSCCs(std::move(G.LeafSCCs)),
+ DFSStack(std::move(G.DFSStack)),
+ SCCEntryNodes(std::move(G.SCCEntryNodes)) {
// Process all nodes updating the graph pointers.
SmallVector<Node *, 16> Worklist;
for (auto &Entry : EntryNodes)
@@ -133,6 +151,88 @@ LazyCallGraph::Node *LazyCallGraph::copyInto(const Node &OtherN) {
return new (N = BPA.Allocate()) Node(*this, OtherN);
}
+LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
+ // When the stack is empty, there are no more SCCs to walk in this graph.
+ if (DFSStack.empty()) {
+ // If we've handled all candidate entry nodes to the SCC forest, we're done.
+ if (SCCEntryNodes.empty())
+ return nullptr;
+
+ Node *N = get(*SCCEntryNodes.pop_back_val());
+ DFSStack.push_back(std::make_pair(N, N->begin()));
+ }
+
+ Node *N = DFSStack.back().first;
+ if (N->DFSNumber == 0) {
+ // This node hasn't been visited before, assign it a DFS number and remove
+ // it from the entry set.
+ N->LowLink = N->DFSNumber = NextDFSNumber++;
+ SCCEntryNodes.remove(&N->getFunction());
+ }
+
+ for (auto I = DFSStack.back().second, E = N->end(); I != E; ++I) {
+ Node *ChildN = *I;
+ if (ChildN->DFSNumber == 0) {
+ // Mark that we should start at this child when next this node is the
+ // top of the stack. We don't start at the next child to ensure this
+ // child's lowlink is reflected.
+ // FIXME: I don't actually think this is required, and we could start
+ // at the next child.
+ DFSStack.back().second = I;
+
+ // Recurse onto this node via a tail call.
+ DFSStack.push_back(std::make_pair(ChildN, ChildN->begin()));
+ return LazyCallGraph::getNextSCCInPostOrder();
+ }
+
+ // Track the lowest link of the childen, if any are still in the stack.
+ if (ChildN->LowLink < N->LowLink && !SCCMap.count(&ChildN->getFunction()))
+ N->LowLink = ChildN->LowLink;
+ }
+
+ // The tail of the stack is the new SCC. Allocate the SCC and pop the stack
+ // into it.
+ SCC *NewSCC = new (SCCBPA.Allocate()) SCC();
+
+ // Because we don't follow the strict Tarjan recursive formulation, walk
+ // from the top of the stack down, propagating the lowest link and stopping
+ // when the DFS number is the lowest link.
+ int LowestLink = N->LowLink;
+ do {
+ Node *SCCN = DFSStack.pop_back_val().first;
+ SCCMap.insert(std::make_pair(&SCCN->getFunction(), NewSCC));
+ NewSCC->Nodes.push_back(SCCN);
+ LowestLink = std::min(LowestLink, SCCN->LowLink);
+ bool Inserted =
+ NewSCC->NodeSet.insert(&SCCN->getFunction());
+ (void)Inserted;
+ assert(Inserted && "Cannot have duplicates in the DFSStack!");
+ } while (!DFSStack.empty() && LowestLink <= DFSStack.back().first->DFSNumber);
+ assert(LowestLink == NewSCC->Nodes.back()->DFSNumber &&
+ "Cannot stop with a DFS number greater than the lowest link!");
+
+ // A final pass over all edges in the SCC (this remains linear as we only
+ // do this once when we build the SCC) to connect it to the parent sets of
+ // its children.
+ bool IsLeafSCC = true;
+ for (Node *SCCN : NewSCC->Nodes)
+ for (Node *SCCChildN : *SCCN) {
+ if (NewSCC->NodeSet.count(&SCCChildN->getFunction()))
+ continue;
+ SCC *ChildSCC = SCCMap.lookup(&SCCChildN->getFunction());
+ assert(ChildSCC &&
+ "Must have all child SCCs processed when building a new SCC!");
+ ChildSCC->ParentSCCs.insert(NewSCC);
+ IsLeafSCC = false;
+ }
+
+ // For the SCCs where we fine no child SCCs, add them to the leaf list.
+ if (IsLeafSCC)
+ LeafSCCs.push_back(NewSCC);
+
+ return NewSCC;
+}
+
char LazyCallGraphAnalysis::PassID;
LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
@@ -151,6 +251,16 @@ static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N,
OS << "\n";
}
+static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &SCC) {
+ ptrdiff_t SCCSize = std::distance(SCC.begin(), SCC.end());
+ OS << " SCC with " << SCCSize << " functions:\n";
+
+ for (LazyCallGraph::Node *N : SCC)
+ OS << " " << N->getFunction().getName() << "\n";
+
+ OS << "\n";
+}
+
PreservedAnalyses LazyCallGraphPrinterPass::run(Module *M,
ModuleAnalysisManager *AM) {
LazyCallGraph &G = AM->getResult<LazyCallGraphAnalysis>(M);
@@ -163,5 +273,9 @@ PreservedAnalyses LazyCallGraphPrinterPass::run(Module *M,
if (Printed.insert(N))
printNodes(OS, *N, Printed);
+ for (LazyCallGraph::SCC *SCC : G.postorder_sccs())
+ printSCC(OS, *SCC);
+
return PreservedAnalyses::all();
+
}
diff --git a/test/Analysis/LazyCallGraph/basic.ll b/test/Analysis/LazyCallGraph/basic.ll
index ebadb75154..b8108d99ed 100644
--- a/test/Analysis/LazyCallGraph/basic.ll
+++ b/test/Analysis/LazyCallGraph/basic.ll
@@ -124,3 +124,53 @@ define void @test2() {
load i8** bitcast (void ()** @h to i8**)
ret void
}
+
+; Verify the SCCs formed.
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f7
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f6
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f5
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f4
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f3
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f2
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f1
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: test2
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f12
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f11
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f10
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f9
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f8
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: test1
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: f
+;
+; CHECK-LABEL: SCC with 1 functions:
+; CHECK-NEXT: test0
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-31 11:04:49 +0000