+ /// \brief A node in the call graph.
+ ///
+ /// This represents a single node. It's primary roles are to cache the list of
+ /// callees, de-duplicate and provide fast testing of whether a function is
+ /// 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;
+ DenseMap<Function *, size_t> CalleeIndexMap;
+
+ /// \brief Basic constructor implements the scanning of F into Callees and
+ /// CalleeIndexMap.
+ Node(LazyCallGraph &G, Function &F);
+
+ public:
+ typedef LazyCallGraph::iterator iterator;
+
+ Function &getFunction() const {
+ return F;
+ };
+
+ iterator begin() const { return iterator(*G, Callees); }
+ iterator end() const { return iterator(*G, Callees, iterator::IsAtEndT()); }
+
+ /// Equality is defined as address equality.
+ bool operator==(const Node &N) const { return this == &N; }
+ 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;
+
+ SmallPtrSet<SCC *, 1> ParentSCCs;
+ SmallVector<Node *, 1> Nodes;
+
+ SCC() {}
+
+ void removeEdge(LazyCallGraph &G, Function &Caller, Function &Callee,
+ SCC &CalleeC);
+
+ SmallVector<LazyCallGraph::SCC *, 1>
+ removeInternalEdge(LazyCallGraph &G, Node &Caller, Node &Callee);
+
+ public:
+ typedef SmallVectorImpl<Node *>::const_iterator iterator;
+ typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator> parent_iterator;
+
+ iterator begin() const { return Nodes.begin(); }
+ iterator end() const { return Nodes.end(); }
+
+ parent_iterator parent_begin() const { return ParentSCCs.begin(); }
+ parent_iterator parent_end() const { return ParentSCCs.end(); }
+
+ iterator_range<parent_iterator> parents() const {
+ return iterator_range<parent_iterator>(parent_begin(), parent_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> {
+ friend class LazyCallGraph;
+ friend class LazyCallGraph::Node;
+
+ /// \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) const {
+ return G == Arg.G && C == Arg.C;
+ }
+ bool operator!=(const postorder_scc_iterator &Arg) const {
+ 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;
+ }
+ };
+