[LCG] Build an edge abstraction for the LazyCallGraph and use it to differentiate between indirect references to functions an direct calls.

[chandlerc]

Summary

This doesn't do a whole lot yet other than change the print out produced
by the analysis, but it lays the groundwork for a very major change I'm
working on next: teaching the call graph to actually be a call graph,
modeling *both* the indirect reference graph and the call graph
simultaneously. More details on that in the next patch though.

Here, the biggest qustion I have for reviewers is whether they like the
core interface used by the edge abstraction. Notably, the Edge::Kind
enums end up used broadly in the API of the entire call graph. Better
names or structure for these abstractions would be very interesting.

The rest of this is essentially a bunch of over-engineering that won't be
interesting until the next patch. But this also isolates essentially all of the
churn necessary to introduce the edge abstraction from the very important
behavior change necessary in order to separately model the two graphs. So it
should make review of the subsequent patch a bit easier at the cost of making
this patch seem poorly motivated. ;]

That said, if folks would rather me merge this into the big patch that
makes having this abstraction necessary, I'm happy to do that.

[chandlerc]

Finish nuking the 'clear' method that I never ended up using. I nuked the declaration but not the definition.

[chandlerc]

Ping.

[reames]

LGTM w/minor comments. The added abstraction is entirely reasonable.

include/llvm/Analysis/LazyCallGraph.h

109 ↗

(On Diff #44424)

Having a class called edge which doesn't encode the source seems mildly confusing. Possibly OutboundEdge? Decidedly minor and optional.

If you make the change suggested, it might be good to pull enum out as a class enum Edge to keep the use sites descriptive. Edge::Ref is more meaningful that OutgoingEdge::Ref to me. Either way, nit, I'd be fine with either.

A bit more detail about the Function/Node and lazy creation might be useful for context on the accessors below.

115 ↗

(On Diff #44424)

Minor: doxygen

137 ↗

(On Diff #44424)

built

Also, the last half of the comment doesn't parse when reading from the top of the diff? Is this something which needs more explanation or is it obvious from something else in the code?

156 ↗

(On Diff #44424)

I'm going to trust you got the double tagging right here. I'm not bothering to look into the implementation to check.

259 ↗

(On Diff #44424)

This iterator code is a bit confusing to read through - probably just because I'm not familiar with the base class.

263 ↗

(On Diff #44424)

Could this be separated into a helper "advance_to_next_call" or something? Might make the code more obvious.

Also, this looks like this stops on a null edge? Why?

608 ↗

(On Diff #44424)

Consistency: tested vs queried four lines apart.

626 ↗

(On Diff #44424)

It looks like this can be:
if (auto *Existing = getNode())

return Existing;

Node &M = ...

lib/Analysis/LazyCallGraph.cpp

26 ↗

(On Diff #44424)

Why are we excluding edges to declarations? That seems odd to me. (Not directly related to this review and should not block.)

318 ↗

(On Diff #44424)

Hm, time for a getNodeRequired()?

[echristo]

LGTM as well (other than the things Philip brings up inline and one of my own inline).

Thanks!

-eric

lib/Analysis/LazyCallGraph.cpp

74 ↗

(On Diff #44424)

s/constant/"direct call" perhaps?

[chandlerc]

Thanks both!

Planning to submit soon, but please keep discussing any of the open issues here and I'll make sure to follow up with patches to correct anything. Also lemme know if my resolution isn't really satisfactory.

include/llvm/Analysis/LazyCallGraph.h

109 ↗

(On Diff #44424)

Yea, I hear what you're saying here, but I think I'm going to keep this the shorter "edge" for now.

One reason why is that the way you *get* edges is from the source, and I think that will help keep it from being too confusing.

But the comment about more context is very helpful, I'll beef up the comments, but let me know if I get it detailed enough to help.

137 ↗

(On Diff #44424)

Yea, I think your context comment above was spot on. Hopefully addressed.

263 ↗

(On Diff #44424)

Meh, sure on the refactoring.

It should *continue* on null edges and non-call edges to find the first valid edge? Added to comment.

608 ↗

(On Diff #44424)

Tested -> a bool result
Queried -> a non bool result

Anyways, I don't care deeply, happy to make them all say queried...

626 ↗

(On Diff #44424)

I mean, it could, it just didn't seem to simplify anything, especially as I'll still need to query P to get the function out.

lib/Analysis/LazyCallGraph.cpp

26 ↗

(On Diff #44424)

It is odd, and something I plan to add after we *actually* start modeling call edges correctly. Currently, this patch has us track which edges are calls but do nothing useful with them. Next step is to build useful graph structures with them. Then I plan to add support for declarations and flags indicating when there is a call to a totally unknown function.

74 ↗

(On Diff #44424)

Hmm, no, I really do mean constant here? We *don't* add direct calls to the worklist.

318 ↗

(On Diff #44424)

Meh, but then it couldn't include the helpful context?

[chandlerc]

include/llvm/Analysis/LazyCallGraph.h

263 ↗

(On Diff #44424)

Heh. there was a bug here that I had fixed in my next patch. backported the fix. It should have been (!*I || !I->isCall())

llvm/trunk/include/llvm/Analysis/LazyCallGraph.h

 ///
 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
 /// it from the existing CallGraph. At some point, it is expected that this
 /// will be the only call graph and it will be renamed accordingly.
 class LazyCallGraph {
 public:
   class Node;
   class SCC;
-  class iterator;
-  typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
-  typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;
+  class edge_iterator;
+
+  /// A class used to represent edges in the call graph.
+  ///
+  /// The lazy call graph models both *call* edges and *reference* edges. Call
+  /// edges are much what you would expect, and exist when there is a 'call' or
+  /// 'invoke' instruction of some function. Reference edges are also tracked
+  /// along side these, and exist whenever any instruction (transitively
+  /// through its operands) references a function. All call edges are
+  /// inherently reference edges, and so the reference graph forms a superset
+  /// of the formal call graph.
+  ///
+  /// Furthermore, edges also may point to raw \c Function objects when those
+  /// functions have not been scanned and incorporated into the graph (yet).
+  /// This is one of the primary ways in which the graph can be lazy. When
+  /// functions are scanned and fully incorporated into the graph, all of the
+  /// edges referencing them are updated to point to the graph \c Node objects
+  /// instead of to the raw \c Function objects. This class even provides
+  /// methods to trigger this scan on-demand by attempting to get the target
+  /// node of the graph and providing a reference back to the graph in order to
+  /// lazily build it if necessary.
+  ///
+  /// All of these forms of edges are fundamentally represented as outgoing
+  /// edges. The edges are stored in the source node and point at the target
+  /// node. This allows the edge structure itself to be a very compact data
+  /// structure: essentially a tagged pointer.
+  class Edge {
+  public:
+    /// The kind of edge in the graph.
+    enum Kind : bool { Ref = false, Call = true };
+
+    Edge();
+    explicit Edge(Function &F, Kind K);
+    explicit Edge(Node &N, Kind K);
+
+    /// Test whether the edge is null.
+    ///
+    /// This happens when an edge has been deleted. We leave the edge objects
+    /// around but clear them.
+    operator bool() const;
+
+    /// Test whether the edge represents a direct call to a function.
+    ///
+    /// This requires that the edge is not null.
+    bool isCall() const;
+
+    /// Get the function referenced by this edge.
+    ///
+    /// This requires that the edge is not null, but will succeed whether we
+    /// have built a graph node for the function yet or not.
+    Function &getFunction() const;
+
+    /// Get the call graph node referenced by this edge if one exists.
+    ///
+    /// This requires that the edge is not null. If we have built a graph node
+    /// for the function this edge points to, this will return that node,
+    /// otherwise it will return null.
+    Node *getNode() const;
+
+    /// Get the call graph node for this edge, building it if necessary.
+    ///
+    /// This requires that the edge is not null. If we have not yet built
+    /// a graph node for the function this edge points to, this will first ask
+    /// the graph to build that node, inserting it into all the relevant
+    /// structures.
+    Node &getNode(LazyCallGraph &G);
+
+  private:
+    PointerIntPair<PointerUnion<Function *, Node *>, 1, Kind> Value;
+  };
+
+  typedef SmallVector<Edge, 4> EdgeVectorT;
+  typedef SmallVectorImpl<Edge> EdgeVectorImplT;
 
   /// 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;
+    mutable EdgeVectorT Edges;
+    DenseMap<Function *, size_t> EdgeIndexMap;
 
-    /// Basic constructor implements the scanning of F into Callees and
-    /// CalleeIndexMap.
+    /// Basic constructor implements the scanning of F into Edges and
+    /// EdgeIndexMap.
     Node(LazyCallGraph &G, Function &F);
 
-    /// Internal helper to insert a callee.
-    void insertEdgeInternal(Function &Callee);
+    /// Internal helper to insert an edge to a function.
+    void insertEdgeInternal(Function &ChildF, Edge::Kind EK);
 
-    /// Internal helper to insert a callee.
-    void insertEdgeInternal(Node &CalleeN);
+    /// Internal helper to insert an edge to a node.
+    void insertEdgeInternal(Node &ChildN, Edge::Kind EK);
 
-    /// Internal helper to remove a callee from this node.
-    void removeEdgeInternal(Function &Callee);
+    /// Internal helper to remove the edge to the given function.
+    void removeEdgeInternal(Function &ChildF);
 
   public:
-    typedef LazyCallGraph::iterator iterator;
+    typedef LazyCallGraph::edge_iterator edge_iterator;
+
+    LazyCallGraph &getGraph() const { return *G; }
 
     Function &getFunction() const { return F; }
 
-    iterator begin() const {
-      return iterator(*G, Callees.begin(), Callees.end());
+    edge_iterator begin() const {
+      return edge_iterator(Edges.begin(), Edges.end());
     }
-    iterator end() const { return iterator(*G, Callees.end(), Callees.end()); }
+    edge_iterator end() const { return edge_iterator(Edges.end(), Edges.end()); }
 
     /// Equality is defined as address equality.
     bool operator==(const Node &N) const { return this == &N; }
     bool operator!=(const Node &N) const { return !operator==(N); }
   };
 
   /// A lazy iterator used for both the entry nodes and child nodes.
   ///
   /// When this iterator is dereferenced, if not yet available, a function will
   /// be scanned for "calls" or uses of functions and its child information
   /// will be constructed. All of these results are accumulated and cached in
   /// the graph.
-  class iterator
-      : public iterator_adaptor_base<iterator, NodeVectorImplT::iterator,
-                                     std::forward_iterator_tag, Node> {
+  class edge_iterator
+      : public iterator_adaptor_base<edge_iterator, EdgeVectorImplT::iterator,
+                                     std::forward_iterator_tag> {
     friend class LazyCallGraph;
     friend class LazyCallGraph::Node;
 
-    LazyCallGraph *G;
-    NodeVectorImplT::iterator E;
+    EdgeVectorImplT::iterator E;
 
-    // Build the iterator for a specific position in a node list.
-    iterator(LazyCallGraph &G, NodeVectorImplT::iterator NI,
-             NodeVectorImplT::iterator E)
-        : iterator_adaptor_base(NI), G(&G), E(E) {
-      while (I != E && I->isNull())
+    // Build the iterator for a specific position in the edge list.
+    edge_iterator(EdgeVectorImplT::iterator BaseI,
+                  EdgeVectorImplT::iterator E)
+        : iterator_adaptor_base(BaseI), E(E) {
+      while (I != E && !*I)
         ++I;
     }
 
   public:
-    iterator() {}
+    edge_iterator() {}
 
     using iterator_adaptor_base::operator++;
-    iterator &operator++() {
+    edge_iterator &operator++() {
       do {
         ++I;
-      } while (I != E && I->isNull());
+      } while (I != E && !*I);
       return *this;
     }
+  };
+
+  /// A lazy iterator over specifically call edges.
+  ///
+  /// This has the same iteration properties as the \c edge_iterator, but
+  /// restricts itself to edges which represent actual calls.
+  class call_edge_iterator
+      : public iterator_adaptor_base<call_edge_iterator,
+                                     EdgeVectorImplT::iterator,
+                                     std::forward_iterator_tag> {
+    friend class LazyCallGraph;
+    friend class LazyCallGraph::Node;
+
+    EdgeVectorImplT::iterator E;
+
+    /// Advance the iterator to the next valid, call edge.
+    void advanceToNextEdge() {
+      while (I != E && (!*I || !I->isCall()))
+        ++I;
+    }
 
-    reference operator*() const {
-      if (I->is<Node *>())
-        return *I->get<Node *>();
-
-      Function *F = I->get<Function *>();
-      Node &ChildN = G->get(*F);
-      *I = &ChildN;
-      return ChildN;
+    // Build the iterator for a specific position in the edge list.
+    call_edge_iterator(EdgeVectorImplT::iterator BaseI,
+                       EdgeVectorImplT::iterator E)
+        : iterator_adaptor_base(BaseI), E(E) {
+      advanceToNextEdge();
+    }
+
+  public:
+    call_edge_iterator() {}
+
+    using iterator_adaptor_base::operator++;
+    call_edge_iterator &operator++() {
+      ++I;
+      advanceToNextEdge();
+      return *this;
     }
   };
 
   /// 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;
 
     LazyCallGraph *G;
     SmallPtrSet<SCC *, 1> ParentSCCs;
     SmallVector<Node *, 1> Nodes;
 
     SCC(LazyCallGraph &G) : G(&G) {}
 
     void insert(Node &N);
 
     void
-    internalDFS(SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
+    internalDFS(SmallVectorImpl<std::pair<Node *, Node::edge_iterator>> &DFSStack,
                 SmallVectorImpl<Node *> &PendingSCCStack, Node *N,
                 SmallVectorImpl<SCC *> &ResultSCCs);
 
   public:
     typedef SmallVectorImpl<Node *>::const_iterator iterator;
     typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator>
         parent_iterator;
 
public:
     ///
     /// Note that these methods sometimes have complex runtimes, so be careful
     /// how you call them.
 
     /// Insert an edge from one node in this SCC to another in this SCC.
     ///
     /// By the definition of an SCC, this does not change the nature or make-up
     /// of any SCCs.
-    void insertIntraSCCEdge(Node &CallerN, Node &CalleeN);
+    void insertIntraSCCEdge(Node &ParentN, Node &ChildN, Edge::Kind EK);
 
     /// Insert an edge whose tail is in this SCC and head is in some child SCC.
     ///
     /// There must be an existing path from the caller to the callee. This
     /// operation is inexpensive and does not change the set of SCCs in the
     /// graph.
-    void insertOutgoingEdge(Node &CallerN, Node &CalleeN);
+    void insertOutgoingEdge(Node &ParentN, Node &ChildN, Edge::Kind EK);
 
     /// Insert an edge whose tail is in a descendant SCC and head is in this
     /// SCC.
     ///
     /// There must be an existing path from the callee to the caller in this
     /// case. NB! This is has the potential to be a very expensive function. It
     /// inherently forms a cycle in the prior SCC DAG and we have to merge SCCs
     /// to resolve that cycle. But finding all of the SCCs which participate in
     /// the cycle can in the worst case require traversing every SCC in the
     /// graph. Every attempt is made to avoid that, but passes must still
     /// exercise caution calling this routine repeatedly.
     ///
     /// FIXME: We could possibly optimize this quite a bit for cases where the
     /// caller and callee are very nearby in the graph. See comments in the
     /// implementation for details, but that use case might impact users.
-    SmallVector<SCC *, 1> insertIncomingEdge(Node &CallerN, Node &CalleeN);
+    SmallVector<SCC *, 1> insertIncomingEdge(Node &ParentN, Node &ChildN,
+                                             Edge::Kind EK);
 
     /// Remove an edge whose source is in this SCC and target is *not*.
     ///
     /// This removes an inter-SCC edge. All inter-SCC edges originating from
     /// this SCC have been fully explored by any in-flight DFS SCC formation,
     /// so this is always safe to call once you have the source SCC.
     ///
     /// This operation does not change the set of SCCs or the members of the
     /// SCCs and so is very inexpensive. It may change the connectivity graph
     /// of the SCCs though, so be careful calling this while iterating over
     /// them.
-    void removeInterSCCEdge(Node &CallerN, Node &CalleeN);
+    void removeInterSCCEdge(Node &ParentN, Node &ChildN);
 
     /// Remove an edge which is entirely within this SCC.
     ///
-    /// Both the \a Caller and the \a Callee must be within this SCC. Removing
+    /// Both the \a ParentN and the \a ChildN must be within this SCC. Removing
     /// such an edge make break cycles that form this SCC and thus this
     /// operation may change the SCC graph significantly. In particular, this
     /// operation will re-form new SCCs based on the remaining connectivity of
     /// the graph. The following invariants are guaranteed to hold after
     /// calling this method:
     ///
     /// 1) This SCC is still an SCC in the graph.
     /// 2) This SCC will be the parent of any new SCCs. Thus, this SCC is
public:
     /// the SCC graph.
     ///
     /// The runtime complexity of this method is, in the worst case, O(V+E)
     /// where V is the number of nodes in this SCC and E is the number of edges
     /// leaving the nodes in this SCC. Note that E includes both edges within
     /// this SCC and edges from this SCC to child SCCs. Some effort has been
     /// made to minimize the overhead of common cases such as self-edges and
     /// edge removals which result in a spanning tree with no more cycles.
-    SmallVector<SCC *, 1> removeIntraSCCEdge(Node &CallerN, Node &CalleeN);
+    SmallVector<SCC *, 1> removeIntraSCCEdge(Node &ParentN, Node &ChildN);
 
     ///@}
   };
 
   /// 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
public:
   /// This sets up the graph and computes all of the entry points of the graph.
   /// No function definitions are scanned until their nodes in the graph are
   /// requested during traversal.
   LazyCallGraph(Module &M);
 
   LazyCallGraph(LazyCallGraph &&G);
   LazyCallGraph &operator=(LazyCallGraph &&RHS);
 
-  iterator begin() {
-    return iterator(*this, EntryNodes.begin(), EntryNodes.end());
+  edge_iterator begin() {
+    return edge_iterator(EntryEdges.begin(), EntryEdges.end());
+  }
+  edge_iterator end() {
+    return edge_iterator(EntryEdges.end(), EntryEdges.end());
   }
-  iterator end() { return iterator(*this, EntryNodes.end(), EntryNodes.end()); }
 
   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());
   }
 
public:
   /// These methods are only valid to call prior to forming any SCCs for this
   /// call graph. They can be used to update the core node-graph during
   /// a node-based inorder traversal that precedes any SCC-based traversal.
   ///
   /// Once you begin manipulating a call graph's SCCs, you must perform all
   /// mutation of the graph via the SCC methods.
 
   /// Update the call graph after inserting a new edge.
-  void insertEdge(Node &Caller, Function &Callee);
+  void insertEdge(Node &Caller, Function &Callee, Edge::Kind EK);
 
   /// Update the call graph after inserting a new edge.
-  void insertEdge(Function &Caller, Function &Callee) {
-    return insertEdge(get(Caller), Callee);
+  void insertEdge(Function &Caller, Function &Callee, Edge::Kind EK) {
+    return insertEdge(get(Caller), Callee, EK);
   }
 
   /// Update the call graph after deleting an edge.
   void removeEdge(Node &Caller, Function &Callee);
 
   /// Update the call graph after deleting an edge.
   void removeEdge(Function &Caller, Function &Callee) {
     return removeEdge(get(Caller), Callee);
   }
 
   ///@}
 
 private:
   /// Allocator that holds all the call graph nodes.
   SpecificBumpPtrAllocator<Node> BPA;
 
   /// Maps function->node for fast lookup.
   DenseMap<const Function *, Node *> NodeMap;
 
   /// The entry nodes to the graph.
   ///
   /// These nodes are reachable through "external" means. Put another way, they
   /// escape at the module scope.
-  NodeVectorT EntryNodes;
+  EdgeVectorT EntryEdges;
 
-  /// Map of the entry nodes in the graph to their indices in \c EntryNodes.
+  /// Map of the entry nodes in the graph to their indices in \c EntryEdges.
   DenseMap<Function *, size_t> EntryIndexMap;
 
   /// Allocator that holds all the call graph SCCs.
   SpecificBumpPtrAllocator<SCC> SCCBPA;
 
   /// Maps Function -> SCC for fast lookup.
   DenseMap<Node *, SCC *> SCCMap;
 
   /// The leaf SCCs of the graph.
   ///
   /// These are all of the SCCs which have no children.
   SmallVector<SCC *, 4> LeafSCCs;
 
   /// Stack of nodes in the DFS walk.
-  SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
+  SmallVector<std::pair<Node *, edge_iterator>, 4> DFSStack;
 
   /// Set of entry nodes not-yet-processed into SCCs.
   SmallVector<Function *, 4> SCCEntryNodes;
 
   /// Stack of nodes the DFS has walked but not yet put into a SCC.
   SmallVector<Node *, 4> PendingSCCStack;
 
   /// Counter for the next DFS number to assign.
private:
   /// Helper to form a new SCC out of the top of a DFSStack-like
   /// structure.
   SCC *formSCC(Node *RootN, SmallVectorImpl<Node *> &NodeStack);
 
   /// Retrieve the next node in the post-order SCC walk of the call graph.
   SCC *getNextSCCInPostOrder();
 };
 
+inline LazyCallGraph::Edge::Edge() : Value() {}
+inline LazyCallGraph::Edge::Edge(Function &F, Kind K) : Value(&F, K) {}
+inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {}
+
+inline LazyCallGraph::Edge::operator bool() const {
+  return !Value.getPointer().isNull();
+}
+
+inline bool LazyCallGraph::Edge::isCall() const {
+  assert(*this && "Queried a null edge!");
+  return Value.getInt() == Call;
+}
+
+inline Function &LazyCallGraph::Edge::getFunction() const {
+  assert(*this && "Queried a null edge!");
+  auto P = Value.getPointer();
+  if (auto *F = P.dyn_cast<Function *>())
+    return *F;
+
+  return P.get<Node *>()->getFunction();
+}
+
+inline LazyCallGraph::Node *LazyCallGraph::Edge::getNode() const {
+  assert(*this && "Queried a null edge!");
+  auto P = Value.getPointer();
+  if (auto *N = P.dyn_cast<Node *>())
+    return N;
+
+  return nullptr;
+}
+
+inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode(LazyCallGraph &G) {
+  assert(*this && "Queried a null edge!");
+  auto P = Value.getPointer();
+  if (auto *N = P.dyn_cast<Node *>())
+    return *N;
+
+  Node &N = G.get(*P.get<Function *>());
+  Value.setPointer(&N);
+  return N;
+}
+
 // Provide GraphTraits specializations for call graphs.
 template <> struct GraphTraits<LazyCallGraph::Node *> {
   typedef LazyCallGraph::Node NodeType;
-  typedef LazyCallGraph::iterator ChildIteratorType;
+  typedef LazyCallGraph::edge_iterator ChildIteratorType;
 
   static NodeType *getEntryNode(NodeType *N) { return N; }
   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 };
 template <> struct GraphTraits<LazyCallGraph *> {
   typedef LazyCallGraph::Node NodeType;
-  typedef LazyCallGraph::iterator ChildIteratorType;
+  typedef LazyCallGraph::edge_iterator ChildIteratorType;
 
   static NodeType *getEntryNode(NodeType *N) { return N; }
   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
 };
 
 /// An analysis pass which computes the call graph for a module.
 class LazyCallGraphAnalysis {

llvm/trunk/lib/Analysis/LazyCallGraph.cpp

 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "lcg"
 
-static void findCallees(
-    SmallVectorImpl<Constant *> &Worklist, SmallPtrSetImpl<Constant *> &Visited,
-    SmallVectorImpl<PointerUnion<Function *, LazyCallGraph::Node *>> &Callees,
-    DenseMap<Function *, size_t> &CalleeIndexMap) {
-  while (!Worklist.empty()) {
-    Constant *C = Worklist.pop_back_val();
-
-    if (Function *F = dyn_cast<Function>(C)) {
-      // Note that we consider *any* function with a definition to be a viable
-      // edge. Even if the function's definition is subject to replacement by
-      // some other module (say, a weak definition) there may still be
-      // optimizations which essentially speculate based on the definition and
-      // a way to check that the specific definition is in fact the one being
-      // used. For example, this could be done by moving the weak definition to
-      // a strong (internal) definition and making the weak definition be an
-      // alias. Then a test of the address of the weak function against the new
-      // strong definition's address would be an effective way to determine the
-      // safety of optimizing a direct call edge.
-      if (!F->isDeclaration() &&
-          CalleeIndexMap.insert(std::make_pair(F, Callees.size())).second) {
-        DEBUG(dbgs() << "    Added callable function: " << F->getName()
-                     << "\n");
-        Callees.push_back(F);
-      }
+static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges,
+                    DenseMap<Function *, size_t> &EdgeIndexMap, Function &F,
+                    LazyCallGraph::Edge::Kind EK) {
+  if (!F.isDeclaration() &&
+      EdgeIndexMap.insert(std::make_pair(&F, Edges.size())).second) {
+    DEBUG(dbgs() << "    Added callable function: " << F.getName() << "\n");
+    Edges.emplace_back(LazyCallGraph::Edge(F, EK));
+  }
+
+static void findReferences(
+                      SmallVectorImpl<Constant *> &Worklist,
+                      SmallPtrSetImpl<Constant *> &Visited,
+                      SmallVectorImpl<LazyCallGraph::Edge> &Edges,
+                      DenseMap<Function *, size_t> &EdgeIndexMap) {
+  while (!Worklist.empty()) {
+    Constant *C = Worklist.pop_back_val();
+
+    if (Function *F = dyn_cast<Function>(C)) {
+      addEdge(Edges, EdgeIndexMap, *F, LazyCallGraph::Edge::Ref);
       continue;
     }
 
     for (Value *Op : C->operand_values())
       if (Visited.insert(cast<Constant>(Op)).second)
         Worklist.push_back(cast<Constant>(Op));
   }
 }
 
 LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F)
     : G(&G), F(F), DFSNumber(0), LowLink(0) {
   DEBUG(dbgs() << "  Adding functions called by '" << F.getName()
                << "' to the graph.\n");
 
   SmallVector<Constant *, 16> Worklist;
+  SmallPtrSet<Function *, 4> Callees;
   SmallPtrSet<Constant *, 16> Visited;
-  // Find all the potential callees in this function. First walk the
-  // instructions and add every operand which is a constant to the worklist.
+
+  // Find all the potential call graph edges in this function. We track both
+  // actual call edges and indirect references to functions. The direct calls
+  // are trivially added, but to accumulate the latter we walk the instructions
+  // and add every operand which is a constant to the worklist to process
+  // afterward.
   for (BasicBlock &BB : F)
-    for (Instruction &I : BB)
+    for (Instruction &I : BB) {
+      if (auto CS = CallSite(&I))
+        if (Function *Callee = CS.getCalledFunction())
+          if (Callees.insert(Callee).second) {
+            Visited.insert(Callee);
+            addEdge(Edges, EdgeIndexMap, *Callee, LazyCallGraph::Edge::Call);
+          }
+
       for (Value *Op : I.operand_values())
         if (Constant *C = dyn_cast<Constant>(Op))
           if (Visited.insert(C).second)
             Worklist.push_back(C);
+    }
 
   // We've collected all the constant (and thus potentially function or
   // function containing) operands to all of the instructions in the function.
   // Process them (recursively) collecting every function found.
-  findCallees(Worklist, Visited, Callees, CalleeIndexMap);
+  findReferences(Worklist, Visited, Edges, EdgeIndexMap);
 }
 
-void LazyCallGraph::Node::insertEdgeInternal(Function &Callee) {
-  if (Node *N = G->lookup(Callee))
-    return insertEdgeInternal(*N);
+void LazyCallGraph::Node::insertEdgeInternal(Function &Child, Edge::Kind EK) {
+  if (Node *N = G->lookup(Child))
+    return insertEdgeInternal(*N, EK);
 
-  CalleeIndexMap.insert(std::make_pair(&Callee, Callees.size()));
-  Callees.push_back(&Callee);
+  EdgeIndexMap.insert(std::make_pair(&Child, Edges.size()));
+  Edges.emplace_back(Child, EK);
 }
 
-void LazyCallGraph::Node::insertEdgeInternal(Node &CalleeN) {
-  CalleeIndexMap.insert(std::make_pair(&CalleeN.getFunction(), Callees.size()));
-  Callees.push_back(&CalleeN);
+void LazyCallGraph::Node::insertEdgeInternal(Node &ChildN, Edge::Kind EK) {
+  EdgeIndexMap.insert(std::make_pair(&ChildN.getFunction(), Edges.size()));
+  Edges.emplace_back(ChildN, EK);
 }
 
-void LazyCallGraph::Node::removeEdgeInternal(Function &Callee) {
-  auto IndexMapI = CalleeIndexMap.find(&Callee);
-  assert(IndexMapI != CalleeIndexMap.end() &&
-         "Callee not in the callee set for this caller?");
+void LazyCallGraph::Node::removeEdgeInternal(Function &Child) {
+  auto IndexMapI = EdgeIndexMap.find(&Child);
+  assert(IndexMapI != EdgeIndexMap.end() &&
+         "Child not in the edge set for this caller?");
 
-  Callees[IndexMapI->second] = nullptr;
-  CalleeIndexMap.erase(IndexMapI);
+  Edges[IndexMapI->second] = Edge();
+  EdgeIndexMap.erase(IndexMapI);
 }
 
 LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) {
   DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()
                << "\n");
   for (Function &F : M)
     if (!F.isDeclaration() && !F.hasLocalLinkage())
-      if (EntryIndexMap.insert(std::make_pair(&F, EntryNodes.size())).second) {
+      if (EntryIndexMap.insert(std::make_pair(&F, EntryEdges.size())).second) {
         DEBUG(dbgs() << "  Adding '" << F.getName()
                      << "' to entry set of the graph.\n");
-        EntryNodes.push_back(&F);
+        EntryEdges.emplace_back(F, Edge::Ref);
       }
 
   // Now add entry nodes for functions reachable via initializers to globals.
   SmallVector<Constant *, 16> Worklist;
   SmallPtrSet<Constant *, 16> Visited;
   for (GlobalVariable &GV : M.globals())
     if (GV.hasInitializer())
       if (Visited.insert(GV.getInitializer()).second)
         Worklist.push_back(GV.getInitializer());
 
   DEBUG(dbgs() << "  Adding functions referenced by global initializers to the "
                   "entry set.\n");
-  findCallees(Worklist, Visited, EntryNodes, EntryIndexMap);
+  findReferences(Worklist, Visited, EntryEdges, EntryIndexMap);
 
-  for (auto &Entry : EntryNodes) {
-    assert(!Entry.isNull() &&
-           "We can't have removed edges before we finish the constructor!");
-    if (Function *F = Entry.dyn_cast<Function *>())
-      SCCEntryNodes.push_back(F);
-    else
-      SCCEntryNodes.push_back(&Entry.get<Node *>()->getFunction());
-  }
+  for (const Edge &E : EntryEdges)
+    SCCEntryNodes.push_back(&E.getFunction());
 }
 
 LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
     : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
-      EntryNodes(std::move(G.EntryNodes)),
+      EntryEdges(std::move(G.EntryEdges)),
       EntryIndexMap(std::move(G.EntryIndexMap)), 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)),
       NextDFSNumber(G.NextDFSNumber) {
   updateGraphPtrs();
 }
 
 LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) {
   BPA = std::move(G.BPA);
   NodeMap = std::move(G.NodeMap);
-  EntryNodes = std::move(G.EntryNodes);
+  EntryEdges = std::move(G.EntryEdges);
   EntryIndexMap = std::move(G.EntryIndexMap);
   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);
   NextDFSNumber = G.NextDFSNumber;
   updateGraphPtrs();
if (AncestorC->isChildOf(C))
       return true;
     for (const SCC *ParentC : AncestorC->ParentSCCs)
       AncestorWorklist.push_back(ParentC);
   } while (!AncestorWorklist.empty());
 
   return false;
 }
 
-void LazyCallGraph::SCC::insertIntraSCCEdge(Node &CallerN, Node &CalleeN) {
+void LazyCallGraph::SCC::insertIntraSCCEdge(Node &ParentN, Node &ChildN,
+                                            Edge::Kind EK) {
   // First insert it into the caller.
-  CallerN.insertEdgeInternal(CalleeN);
+  ParentN.insertEdgeInternal(ChildN, EK);
 
-  assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC.");
-  assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC.");
+  assert(G->SCCMap.lookup(&ParentN) == this && "Parent must be in this SCC.");
+  assert(G->SCCMap.lookup(&ChildN) == this && "Child must be in this SCC.");
 
   // Nothing changes about this SCC or any other.
 }
 
-void LazyCallGraph::SCC::insertOutgoingEdge(Node &CallerN, Node &CalleeN) {
+void LazyCallGraph::SCC::insertOutgoingEdge(Node &ParentN, Node &ChildN,
+                                            Edge::Kind EK) {
   // First insert it into the caller.
-  CallerN.insertEdgeInternal(CalleeN);
+  ParentN.insertEdgeInternal(ChildN, EK);
 
-  assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC.");
+  assert(G->SCCMap.lookup(&ParentN) == this && "Parent must be in this SCC.");
 
-  SCC &CalleeC = *G->SCCMap.lookup(&CalleeN);
-  assert(&CalleeC != this && "Callee must not be in this SCC.");
-  assert(CalleeC.isDescendantOf(*this) &&
-         "Callee must be a descendant of the Caller.");
+  SCC &ChildC = *G->SCCMap.lookup(&ChildN);
+  assert(&ChildC != this && "Child must not be in this SCC.");
+  assert(ChildC.isDescendantOf(*this) &&
+         "Child must be a descendant of the Parent.");
 
   // The only change required is to add this SCC to the parent set of the
   // callee.
-  CalleeC.ParentSCCs.insert(this);
+  ChildC.ParentSCCs.insert(this);
 }
 
 SmallVector<LazyCallGraph::SCC *, 1>
-LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) {
+LazyCallGraph::SCC::insertIncomingEdge(Node &ParentN, Node &ChildN,
+                                       Edge::Kind EK) {
   // First insert it into the caller.
-  CallerN.insertEdgeInternal(CalleeN);
+  ParentN.insertEdgeInternal(ChildN, EK);
 
-  assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC.");
+  assert(G->SCCMap.lookup(&ChildN) == this && "Child must be in this SCC.");
 
-  SCC &CallerC = *G->SCCMap.lookup(&CallerN);
-  assert(&CallerC != this && "Caller must not be in this SCC.");
-  assert(CallerC.isDescendantOf(*this) &&
-         "Caller must be a descendant of the Callee.");
+  SCC &ParentC = *G->SCCMap.lookup(&ParentN);
+  assert(&ParentC != this && "Parent must not be in this SCC.");
+  assert(ParentC.isDescendantOf(*this) &&
+         "Parent must be a descendant of the Child.");
 
   // The algorithm we use for merging SCCs based on the cycle introduced here
   // is to walk the SCC inverted DAG formed by the parent SCC sets. The inverse
   // graph has the same cycle properties as the actual DAG of the SCCs, and
   // when forming SCCs lazily by a DFS, the bottom of the graph won't exist in
   // many cases which should prune the search space.
   //
   // FIXME: We can get this pruning behavior even after the incremental SCC
   // formation by leaving behind (conservative) DFS numberings in the nodes,
   // and pruning the search with them. These would need to be cleverly updated
   // during the removal of intra-SCC edges, but could be preserved
   // conservatively.
 
   // The set of SCCs that are connected to the caller, and thus will
   // participate in the merged connected component.
   SmallPtrSet<SCC *, 8> ConnectedSCCs;
   ConnectedSCCs.insert(this);
-  ConnectedSCCs.insert(&CallerC);
+  ConnectedSCCs.insert(&ParentC);
 
   // We build up a DFS stack of the parents chains.
   SmallVector<std::pair<SCC *, SCC::parent_iterator>, 8> DFSSCCs;
   SmallPtrSet<SCC *, 8> VisitedSCCs;
   int ConnectedDepth = -1;
   SCC *C = this;
   parent_iterator I = parent_begin(), E = parent_end();
   for (;;) {
for (SCC *C : ConnectedSCCs) {
     if (C == this)
       continue;
     for (SCC *ParentC : C->ParentSCCs)
       if (!ConnectedSCCs.count(ParentC))
         ParentSCCs.insert(ParentC);
     C->ParentSCCs.clear();
 
     for (Node *N : *C) {
-      for (Node &ChildN : *N) {
-        SCC &ChildC = *G->SCCMap.lookup(&ChildN);
+      for (Edge &E : *N) {
+        assert(E.getNode() && "Cannot have a null node within a visited SCC!");
+        SCC &ChildC = *G->SCCMap.lookup(E.getNode());
         if (&ChildC != C)
           ChildC.ParentSCCs.erase(C);
       }
       G->SCCMap[N] = this;
       Nodes.push_back(N);
     }
     C->Nodes.clear();
   }
   for (auto I = Nodes.begin() + NewNodeBeginIdx, E = Nodes.end(); I != E; ++I)
-    for (Node &ChildN : **I) {
-      SCC &ChildC = *G->SCCMap.lookup(&ChildN);
+    for (Edge &E : **I) {
+      assert(E.getNode() && "Cannot have a null node within a visited SCC!");
+      SCC &ChildC = *G->SCCMap.lookup(E.getNode());
       if (&ChildC != this)
         ChildC.ParentSCCs.insert(this);
     }
 
   // We return the list of SCCs which were merged so that callers can
   // invalidate any data they have associated with those SCCs. Note that these
   // SCCs are no longer in an interesting state (they are totally empty) but
   // the pointers will remain stable for the life of the graph itself.
   return SmallVector<SCC *, 1>(ConnectedSCCs.begin(), ConnectedSCCs.end());
 }
 
-void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) {
+void LazyCallGraph::SCC::removeInterSCCEdge(Node &ParentN, Node &ChildN) {
   // First remove it from the node.
-  CallerN.removeEdgeInternal(CalleeN.getFunction());
+  ParentN.removeEdgeInternal(ChildN.getFunction());
 
-  assert(G->SCCMap.lookup(&CallerN) == this &&
+  assert(G->SCCMap.lookup(&ParentN) == this &&
          "The caller must be a member of this SCC.");
 
-  SCC &CalleeC = *G->SCCMap.lookup(&CalleeN);
-  assert(&CalleeC != this &&
+  SCC &ChildC = *G->SCCMap.lookup(&ChildN);
+  assert(&ChildC != this &&
          "This API only supports the rmoval of inter-SCC edges.");
 
   assert(std::find(G->LeafSCCs.begin(), G->LeafSCCs.end(), this) ==
              G->LeafSCCs.end() &&
          "Cannot have a leaf SCC caller with a different SCC callee.");
 
-  bool HasOtherCallToCalleeC = false;
-  bool HasOtherCallOutsideSCC = false;
+  bool HasOtherEdgeToChildC = false;
+  bool HasOtherChildC = false;
   for (Node *N : *this) {
-    for (Node &OtherCalleeN : *N) {
-      SCC &OtherCalleeC = *G->SCCMap.lookup(&OtherCalleeN);
-      if (&OtherCalleeC == &CalleeC) {
-        HasOtherCallToCalleeC = true;
+    for (Edge &E : *N) {
+      assert(E.getNode() && "Cannot have a missing node in a visited SCC!");
+      SCC &OtherChildC = *G->SCCMap.lookup(E.getNode());
+      if (&OtherChildC == &ChildC) {
+        HasOtherEdgeToChildC = true;
         break;
       }
-      if (&OtherCalleeC != this)
-        HasOtherCallOutsideSCC = true;
+      if (&OtherChildC != this)
+        HasOtherChildC = true;
     }
-    if (HasOtherCallToCalleeC)
+    if (HasOtherEdgeToChildC)
       break;
   }
   // Because the SCCs form a DAG, deleting such an edge cannot change the set
   // of SCCs in the graph. However, it may cut an edge of the SCC DAG, making
-  // the caller no longer a parent of the callee. Walk the other call edges
-  // in the caller to tell.
-  if (!HasOtherCallToCalleeC) {
-    bool Removed = CalleeC.ParentSCCs.erase(this);
+  // the parent SCC no longer connected to the child SCC. If so, we need to
+  // update the child SCC's map of its parents.
+  if (!HasOtherEdgeToChildC) {
+    bool Removed = ChildC.ParentSCCs.erase(this);
     (void)Removed;
     assert(Removed &&
-           "Did not find the caller SCC in the callee SCC's parent list!");
+           "Did not find the parent SCC in the child SCC's parent list!");
 
     // It may orphan an SCC if it is the last edge reaching it, but that does
     // not violate any invariants of the graph.
-    if (CalleeC.ParentSCCs.empty())
-      DEBUG(dbgs() << "LCG: Update removing " << CallerN.getFunction().getName()
-                   << " -> " << CalleeN.getFunction().getName()
+    if (ChildC.ParentSCCs.empty())
+      DEBUG(dbgs() << "LCG: Update removing " << ParentN.getFunction().getName()
+                   << " -> " << ChildN.getFunction().getName()
                    << " edge orphaned the callee's SCC!\n");
   }
 
-  // It may make the Caller SCC a leaf SCC.
-  if (!HasOtherCallOutsideSCC)
+  // It may make the Parent SCC a leaf SCC.
+  if (!HasOtherChildC)
     G->LeafSCCs.push_back(this);
 }
 
 void LazyCallGraph::SCC::internalDFS(
-    SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
+    SmallVectorImpl<std::pair<Node *, Node::edge_iterator>> &DFSStack,
     SmallVectorImpl<Node *> &PendingSCCStack, Node *N,
     SmallVectorImpl<SCC *> &ResultSCCs) {
-  Node::iterator I = N->begin();
+  auto I = N->begin();
   N->LowLink = N->DFSNumber = 1;
   int NextDFSNumber = 2;
   for (;;) {
     assert(N->DFSNumber != 0 && "We should always assign a DFS number "
                                 "before processing a node.");
 
     // We simulate recursion by popping out of the nested loop and continuing.
-    Node::iterator E = N->end();
+    auto E = N->end();
     while (I != E) {
-      Node &ChildN = *I;
+      Node &ChildN = I->getNode(*G);
       if (SCC *ChildSCC = G->SCCMap.lookup(&ChildN)) {
         // Check if we have reached a node in the new (known connected) set of
         // this SCC. If so, the entire stack is necessarily in that set and we
         // can re-start.
         if (ChildSCC == this) {
           insert(*N);
           while (!PendingSCCStack.empty())
             insert(*PendingSCCStack.pop_back_val());
for (;;) {
 
     N = DFSStack.back().first;
     I = DFSStack.back().second;
     DFSStack.pop_back();
   }
 }
 
 SmallVector<LazyCallGraph::SCC *, 1>
-LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN, Node &CalleeN) {
+LazyCallGraph::SCC::removeIntraSCCEdge(Node &ParentN, Node &ChildN) {
   // First remove it from the node.
-  CallerN.removeEdgeInternal(CalleeN.getFunction());
+  ParentN.removeEdgeInternal(ChildN.getFunction());
 
   // We return a list of the resulting *new* SCCs in postorder.
   SmallVector<SCC *, 1> ResultSCCs;
 
   // Direct recursion doesn't impact the SCC graph at all.
-  if (&CallerN == &CalleeN)
+  if (&ParentN == &ChildN)
     return ResultSCCs;
 
   // The worklist is every node in the original SCC.
   SmallVector<Node *, 1> Worklist;
   Worklist.swap(Nodes);
   for (Node *N : Worklist) {
     // The nodes formerly in this SCC are no longer in any SCC.
     N->DFSNumber = 0;
     N->LowLink = 0;
     G->SCCMap.erase(N);
   }
   assert(Worklist.size() > 1 && "We have to have at least two nodes to have an "
                                 "edge between them that is within the SCC.");
 
-  // The callee can already reach every node in this SCC (by definition). It is
+  // The child can already reach every node in this SCC (by definition). It is
   // the only node we know will stay inside this SCC. Everything which
-  // transitively reaches Callee will also remain in the SCC. To model this we
+  // transitively reaches Child will also remain in the SCC. To model this we
   // incrementally add any chain of nodes which reaches something in the new
   // node set to the new node set. This short circuits one side of the Tarjan's
   // walk.
-  insert(CalleeN);
+  insert(ChildN);
 
   // We're going to do a full mini-Tarjan's walk using a local stack here.
-  SmallVector<std::pair<Node *, Node::iterator>, 4> DFSStack;
+  SmallVector<std::pair<Node *, Node::edge_iterator>, 4> DFSStack;
   SmallVector<Node *, 4> PendingSCCStack;
   do {
     Node *N = Worklist.pop_back_val();
     if (N->DFSNumber == 0)
       internalDFS(DFSStack, PendingSCCStack, N, ResultSCCs);
 
     assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
     assert(PendingSCCStack.empty() && "Didn't flush all pending SCC nodes!");
   } while (!Worklist.empty());
 
   // Now we need to reconnect the current SCC to the graph.
   bool IsLeafSCC = true;
   for (Node *N : Nodes) {
-    for (Node &ChildN : *N) {
-      SCC &ChildSCC = *G->SCCMap.lookup(&ChildN);
+    for (Edge &E : *N) {
+      assert(E.getNode() && "Cannot have a missing node in a visited SCC!");
+      SCC &ChildSCC = *G->SCCMap.lookup(E.getNode());
       if (&ChildSCC == this)
         continue;
       ChildSCC.ParentSCCs.insert(this);
       IsLeafSCC = false;
     }
   }
 #ifndef NDEBUG
   if (!ResultSCCs.empty())
#endif
   if (!IsLeafSCC && !ResultSCCs.empty())
     G->LeafSCCs.erase(std::remove(G->LeafSCCs.begin(), G->LeafSCCs.end(), this),
                       G->LeafSCCs.end());
 
   // Return the new list of SCCs.
   return ResultSCCs;
 }
 
-void LazyCallGraph::insertEdge(Node &CallerN, Function &Callee) {
+void LazyCallGraph::insertEdge(Node &ParentN, Function &Child, Edge::Kind EK) {
   assert(SCCMap.empty() && DFSStack.empty() &&
          "This method cannot be called after SCCs have been formed!");
 
-  return CallerN.insertEdgeInternal(Callee);
+  return ParentN.insertEdgeInternal(Child, EK);
 }
 
-void LazyCallGraph::removeEdge(Node &CallerN, Function &Callee) {
+void LazyCallGraph::removeEdge(Node &ParentN, Function &Child) {
   assert(SCCMap.empty() && DFSStack.empty() &&
          "This method cannot be called after SCCs have been formed!");
 
-  return CallerN.removeEdgeInternal(Callee);
+  return ParentN.removeEdgeInternal(Child);
 }
 
 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
   return *new (MappedN = BPA.Allocate()) Node(*this, F);
 }
 
 void LazyCallGraph::updateGraphPtrs() {
   // Process all nodes updating the graph pointers.
   {
     SmallVector<Node *, 16> Worklist;
-    for (auto &Entry : EntryNodes)
-      if (Node *EntryN = Entry.dyn_cast<Node *>())
+    for (Edge &E : EntryEdges)
+      if (Node *EntryN = E.getNode())
         Worklist.push_back(EntryN);
 
     while (!Worklist.empty()) {
       Node *N = Worklist.pop_back_val();
       N->G = this;
-      for (auto &Callee : N->Callees)
-        if (!Callee.isNull())
-          if (Node *CalleeN = Callee.dyn_cast<Node *>())
-            Worklist.push_back(CalleeN);
+      for (Edge &E : N->Edges)
+        if (Node *ChildN = E.getNode())
+          Worklist.push_back(ChildN);
     }
   }
 
   // Process all SCCs updating the graph pointers.
   {
     SmallVector<SCC *, 16> Worklist(LeafSCCs.begin(), LeafSCCs.end());
 
     while (!Worklist.empty()) {
LazyCallGraph::SCC *LazyCallGraph::formSCC(Node *RootN,
   }
   NewSCC->insert(*RootN);
 
   // 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) {
-      SCC &ChildSCC = *SCCMap.lookup(&SCCChildN);
+    for (Edge &E : *SCCN) {
+      assert(E.getNode() && "Cannot have a missing node in a visited SCC!");
+      SCC &ChildSCC = *SCCMap.lookup(E.getNode());
       if (&ChildSCC == NewSCC)
         continue;
       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;
 }
 
 LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
   Node *N;
-  Node::iterator I;
+  Node::edge_iterator I;
   if (!DFSStack.empty()) {
     N = DFSStack.back().first;
     I = DFSStack.back().second;
     DFSStack.pop_back();
   } else {
     // If we've handled all candidate entry nodes to the SCC forest, we're done.
     do {
       if (SCCEntryNodes.empty())
         return nullptr;
 
       N = &get(*SCCEntryNodes.pop_back_val());
     } while (N->DFSNumber != 0);
     I = N->begin();
     N->LowLink = N->DFSNumber = 1;
     NextDFSNumber = 2;
   }
 
   for (;;) {
     assert(N->DFSNumber != 0 && "We should always assign a DFS number "
                                 "before placing a node onto the stack.");
 
-    Node::iterator E = N->end();
+    auto E = N->end();
     while (I != E) {
-      Node &ChildN = *I;
+      Node &ChildN = I->getNode(*this);
       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.
         DFSStack.push_back(std::make_pair(N, N->begin()));
 
         // Recurse onto this node via a tail call.
         assert(!SCCMap.count(&ChildN) &&

 }
 
 char LazyCallGraphAnalysis::PassID;
 
 LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
 
 static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N,
                        SmallPtrSetImpl<LazyCallGraph::Node *> &Printed) {
+  LazyCallGraph &G = N.getGraph();
+
   // Recurse depth first through the nodes.
-  for (LazyCallGraph::Node &ChildN : N)
+  for (LazyCallGraph::Edge &E : N) {
+    LazyCallGraph::Node &ChildN = E.getNode(G);
     if (Printed.insert(&ChildN).second)
       printNodes(OS, ChildN, Printed);
+  }
 
-  OS << "  Call edges in function: " << N.getFunction().getName() << "\n";
-  for (LazyCallGraph::iterator I = N.begin(), E = N.end(); I != E; ++I)
-    OS << "    -> " << I->getFunction().getName() << "\n";
+  OS << "  Edges in function: " << N.getFunction().getName() << "\n";
+  for (const LazyCallGraph::Edge &E : N)
+    OS << "    " << (E.isCall() ? "call" : "ref ") << " -> "
+       << E.getFunction().getName() << "\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);
 
   OS << "Printing the call graph for module: " << M.getModuleIdentifier()
      << "\n\n";
 
   SmallPtrSet<LazyCallGraph::Node *, 16> Printed;
-  for (LazyCallGraph::Node &N : G)
+  for (LazyCallGraph::Edge &E : G) {
+    LazyCallGraph::Node &N = E.getNode(G);
     if (Printed.insert(&N).second)
       printNodes(OS, N, Printed);
+  }
 
   for (LazyCallGraph::SCC &SCC : G.postorder_sccs())
     printSCC(OS, SCC);
 
   return PreservedAnalyses::all();
 }

llvm/trunk/test/Analysis/LazyCallGraph/basic.ll

 ; RUN: opt -disable-output -passes=print-cg %s 2>&1 | FileCheck %s
 ;
 ; Basic validation of the call graph analysis used in the new pass manager.
 
 define void @f() {
-; CHECK-LABEL: Call edges in function: f
+; CHECK-LABEL: Edges in function: f
 ; CHECK-NOT: ->
 
 entry:
   ret void
 }
 
 ; A bunch more functions just to make it easier to test several call edges at once.
 define void @f1() {

 }
 define void @f12() {
   ret void
 }
 
 declare i32 @__gxx_personality_v0(...)
 
 define void @test0() {
-; CHECK-LABEL: Call edges in function: test0
-; CHECK-NEXT: -> f
+; CHECK-LABEL: Edges in function: test0
+; CHECK-NEXT: call -> f
 ; CHECK-NOT: ->
 
 entry:
   call void @f()
   call void @f()
   call void @f()
   call void @f()
   ret void
 }
 
 define void ()* @test1(void ()** %x) personality i32 (...)* @__gxx_personality_v0 {
-; CHECK-LABEL: Call edges in function: test1
-; CHECK-NEXT: -> f12
-; CHECK-NEXT: -> f11
-; CHECK-NEXT: -> f10
-; CHECK-NEXT: -> f7
-; CHECK-NEXT: -> f9
-; CHECK-NEXT: -> f8
-; CHECK-NEXT: -> f6
-; CHECK-NEXT: -> f5
-; CHECK-NEXT: -> f4
-; CHECK-NEXT: -> f3
-; CHECK-NEXT: -> f2
-; CHECK-NEXT: -> f1
+; CHECK-LABEL: Edges in function: test1
+; CHECK-NEXT: call -> f6
+; CHECK-NEXT: call -> f10
+; CHECK-NEXT: ref -> f12
+; CHECK-NEXT: ref -> f11
+; CHECK-NEXT: ref -> f7
+; CHECK-NEXT: ref -> f9
+; CHECK-NEXT: ref -> f8
+; CHECK-NEXT: ref -> f5
+; CHECK-NEXT: ref -> f4
+; CHECK-NEXT: ref -> f3
+; CHECK-NEXT: ref -> f2
+; CHECK-NEXT: ref -> f1
 ; CHECK-NOT: ->
 
 entry:
   br label %next
 
 dead:
   br label %next
 

 }
 
 @g = global void ()* @f1
 @g1 = global [4 x void ()*] [void ()* @f2, void ()* @f3, void ()* @f4, void ()* @f5]
 @g2 = global {i8, void ()*, i8} {i8 1, void ()* @f6, i8 2}
 @h = constant void ()* @f7
 
 define void @test2() {
-; CHECK-LABEL: Call edges in function: test2
-; CHECK-NEXT: -> f7
-; CHECK-NEXT: -> f6
-; CHECK-NEXT: -> f5
-; CHECK-NEXT: -> f4
-; CHECK-NEXT: -> f3
-; CHECK-NEXT: -> f2
-; CHECK-NEXT: -> f1
+; CHECK-LABEL: Edges in function: test2
+; CHECK-NEXT: ref -> f7
+; CHECK-NEXT: ref -> f6
+; CHECK-NEXT: ref -> f5
+; CHECK-NEXT: ref -> f4
+; CHECK-NEXT: ref -> f3
+; CHECK-NEXT: ref -> f2
+; CHECK-NEXT: ref -> f1
 ; CHECK-NOT: ->
 
   load i8*, i8** bitcast (void ()** @g to i8**)
   load i8*, i8** bitcast (void ()** getelementptr ([4 x void ()*], [4 x void ()*]* @g1, i32 0, i32 2) to i8**)
   load i8*, i8** bitcast (void ()** getelementptr ({i8, void ()*, i8}, {i8, void ()*, i8}* @g2, i32 0, i32 1) to i8**)
   load i8*, i8** bitcast (void ()** @h to i8**)
   ret void
 }

 ;
 ; 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-NEXT:    f10
 ;
 ; CHECK-LABEL: SCC with 1 functions:
-; CHECK-NEXT:    f11
+; CHECK-NEXT:    f12
 ;
 ; CHECK-LABEL: SCC with 1 functions:
-; CHECK-NEXT:    f10
+; CHECK-NEXT:    f11
 ;
 ; 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

llvm/trunk/test/Analysis/LazyCallGraph/non-leaf-intrinsics.ll

 ; RUN: opt -S -disable-output -passes=print-cg < %s 2>&1 | FileCheck %s
 
 declare void @llvm.experimental.patchpoint.void(i64, i32, i8*, i32, ...)
 declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
 
 define private void @f() {
   ret void
 }
 
 define void @calls_statepoint(i8 addrspace(1)* %arg) gc "statepoint-example" {
-; CHECK: Call edges in function: calls_statepoint
+; CHECK: Edges in function: calls_statepoint
 ; CHECK-NEXT:  -> f
 entry:
   %cast = bitcast i8 addrspace(1)* %arg to i64 addrspace(1)*
   %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @f, i32 0, i32 0, i32 0, i32 5, i32 0, i32 0, i32 0, i32 10, i32 0, i8 addrspace(1)* %arg, i64 addrspace(1)* %cast, i8 addrspace(1)* %arg, i8 addrspace(1)* %arg)
   ret void
 }
 
 define void @calls_patchpoint() {
-; CHECK:  Call edges in function: calls_patchpoint
+; CHECK:  Edges in function: calls_patchpoint
 ; CHECK-NEXT:    -> f
 entry:
   %c = bitcast void()* @f to i8*
   tail call void (i64, i32, i8*, i32, ...) @llvm.experimental.patchpoint.void(i64 1, i32 15, i8* %c, i32 0, i16 65535, i16 -1, i32 65536, i32 2000000000, i32 2147483647, i32 -1, i32 4294967295, i32 4294967296, i64 2147483648, i64 4294967295, i64 4294967296, i64 -1)
   ret void
 }

llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp

 TEST(LazyCallGraphTest, BasicGraphFormation) {
   std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
   LazyCallGraph CG(*M);
 
   // The order of the entry nodes should be stable w.r.t. the source order of
   // the IR, and everything in our module is an entry node, so just directly
   // build variables for each node.
   auto I = CG.begin();
-  LazyCallGraph::Node &A1 = *I++;
+  LazyCallGraph::Node &A1 = (I++)->getNode(CG);
   EXPECT_EQ("a1", A1.getFunction().getName());
-  LazyCallGraph::Node &A2 = *I++;
+  LazyCallGraph::Node &A2 = (I++)->getNode(CG);
   EXPECT_EQ("a2", A2.getFunction().getName());
-  LazyCallGraph::Node &A3 = *I++;
+  LazyCallGraph::Node &A3 = (I++)->getNode(CG);
   EXPECT_EQ("a3", A3.getFunction().getName());
-  LazyCallGraph::Node &B1 = *I++;
+  LazyCallGraph::Node &B1 = (I++)->getNode(CG);
   EXPECT_EQ("b1", B1.getFunction().getName());
-  LazyCallGraph::Node &B2 = *I++;
+  LazyCallGraph::Node &B2 = (I++)->getNode(CG);
   EXPECT_EQ("b2", B2.getFunction().getName());
-  LazyCallGraph::Node &B3 = *I++;
+  LazyCallGraph::Node &B3 = (I++)->getNode(CG);
   EXPECT_EQ("b3", B3.getFunction().getName());
-  LazyCallGraph::Node &C1 = *I++;
+  LazyCallGraph::Node &C1 = (I++)->getNode(CG);
   EXPECT_EQ("c1", C1.getFunction().getName());
-  LazyCallGraph::Node &C2 = *I++;
+  LazyCallGraph::Node &C2 = (I++)->getNode(CG);
   EXPECT_EQ("c2", C2.getFunction().getName());
-  LazyCallGraph::Node &C3 = *I++;
+  LazyCallGraph::Node &C3 = (I++)->getNode(CG);
   EXPECT_EQ("c3", C3.getFunction().getName());
-  LazyCallGraph::Node &D1 = *I++;
+  LazyCallGraph::Node &D1 = (I++)->getNode(CG);
   EXPECT_EQ("d1", D1.getFunction().getName());
-  LazyCallGraph::Node &D2 = *I++;
+  LazyCallGraph::Node &D2 = (I++)->getNode(CG);
   EXPECT_EQ("d2", D2.getFunction().getName());
-  LazyCallGraph::Node &D3 = *I++;
+  LazyCallGraph::Node &D3 = (I++)->getNode(CG);
   EXPECT_EQ("d3", D3.getFunction().getName());
   EXPECT_EQ(CG.end(), I);
 
   // Build vectors and sort them for the rest of the assertions to make them
   // independent of order.
   std::vector<std::string> Nodes;
 
-  for (LazyCallGraph::Node &N : A1)
-    Nodes.push_back(N.getFunction().getName());
+  for (LazyCallGraph::Edge &E : A1)
+    Nodes.push_back(E.getFunction().getName());
   std::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ("a2", Nodes[0]);
   EXPECT_EQ("b2", Nodes[1]);
   EXPECT_EQ("c3", Nodes[2]);
   Nodes.clear();
 
   EXPECT_EQ(A2.end(), std::next(A2.begin()));
   EXPECT_EQ("a3", A2.begin()->getFunction().getName());
   EXPECT_EQ(A3.end(), std::next(A3.begin()));
   EXPECT_EQ("a1", A3.begin()->getFunction().getName());
 
-  for (LazyCallGraph::Node &N : B1)
-    Nodes.push_back(N.getFunction().getName());
+  for (LazyCallGraph::Edge &E : B1)
+    Nodes.push_back(E.getFunction().getName());
   std::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ("b2", Nodes[0]);
   EXPECT_EQ("d3", Nodes[1]);
   Nodes.clear();
 
   EXPECT_EQ(B2.end(), std::next(B2.begin()));
   EXPECT_EQ("b3", B2.begin()->getFunction().getName());
   EXPECT_EQ(B3.end(), std::next(B3.begin()));
   EXPECT_EQ("b1", B3.begin()->getFunction().getName());
 
-  for (LazyCallGraph::Node &N : C1)
-    Nodes.push_back(N.getFunction().getName());
+  for (LazyCallGraph::Edge &E : C1)
+    Nodes.push_back(E.getFunction().getName());
   std::sort(Nodes.begin(), Nodes.end());
   EXPECT_EQ("c2", Nodes[0]);
   EXPECT_EQ("d2", Nodes[1]);
   Nodes.clear();
 
   EXPECT_EQ(C2.end(), std::next(C2.begin()));
   EXPECT_EQ("c3", C2.begin()->getFunction().getName());
   EXPECT_EQ(C3.end(), std::next(C3.begin()));
std::unique_ptr<Module> M = parseAssembly(
       "}\n");
   LazyCallGraph CG(*M);
 
   LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
   LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
   EXPECT_EQ(2, std::distance(A.begin(), A.end()));
   EXPECT_EQ(0, std::distance(B.begin(), B.end()));
 
-  CG.insertEdge(B, lookupFunction(*M, "c"));
+  CG.insertEdge(B, lookupFunction(*M, "c"), LazyCallGraph::Edge::Call);
   EXPECT_EQ(1, std::distance(B.begin(), B.end()));
-  LazyCallGraph::Node &C = *B.begin();
+  LazyCallGraph::Node &C = B.begin()->getNode(CG);
   EXPECT_EQ(0, std::distance(C.begin(), C.end()));
 
-  CG.insertEdge(C, B.getFunction());
+  CG.insertEdge(C, B.getFunction(), LazyCallGraph::Edge::Call);
   EXPECT_EQ(1, std::distance(C.begin(), C.end()));
-  EXPECT_EQ(&B, &*C.begin());
+  EXPECT_EQ(&B, C.begin()->getNode());
 
-  CG.insertEdge(C, C.getFunction());
+  CG.insertEdge(C, C.getFunction(), LazyCallGraph::Edge::Call);
   EXPECT_EQ(2, std::distance(C.begin(), C.end()));
-  EXPECT_EQ(&B, &*C.begin());
-  EXPECT_EQ(&C, &*std::next(C.begin()));
+  EXPECT_EQ(&B, C.begin()->getNode());
+  EXPECT_EQ(&C, std::next(C.begin())->getNode());
 
   CG.removeEdge(C, B.getFunction());
   EXPECT_EQ(1, std::distance(C.begin(), C.end()));
-  EXPECT_EQ(&C, &*C.begin());
+  EXPECT_EQ(&C, C.begin()->getNode());
 
   CG.removeEdge(C, C.getFunction());
   EXPECT_EQ(0, std::distance(C.begin(), C.end()));
 
   CG.removeEdge(B, C.getFunction());
   EXPECT_EQ(0, std::distance(B.begin(), B.end()));
 }
 
TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) {
   EXPECT_TRUE(AC.isAncestorOf(BC));
   EXPECT_TRUE(AC.isAncestorOf(CC));
   EXPECT_TRUE(AC.isAncestorOf(DC));
   EXPECT_TRUE(DC.isDescendantOf(AC));
   EXPECT_TRUE(DC.isDescendantOf(BC));
   EXPECT_TRUE(DC.isDescendantOf(CC));
 
   EXPECT_EQ(2, std::distance(A.begin(), A.end()));
-  AC.insertOutgoingEdge(A, D);
+  AC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call);
   EXPECT_EQ(3, std::distance(A.begin(), A.end()));
   EXPECT_TRUE(AC.isParentOf(DC));
   EXPECT_EQ(&AC, CG.lookupSCC(A));
   EXPECT_EQ(&BC, CG.lookupSCC(B));
   EXPECT_EQ(&CC, CG.lookupSCC(C));
   EXPECT_EQ(&DC, CG.lookupSCC(D));
 }
 
TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) {
   //      /     \    |  |
   //     b1     c1   |  |
   //   /  \    /  \ /   |
   //  b3--b2  c3--c2    |
   //       \  /         |
   //        a1          |
   //       /  \         |
   //      a3--a2        |
-  CC.insertIncomingEdge(D2, C2);
+  CC.insertIncomingEdge(D2, C2, LazyCallGraph::Edge::Call);
   // Make sure we connected the nodes.
   EXPECT_EQ(2, std::distance(D2.begin(), D2.end()));
 
   // Make sure we have the correct nodes in the SCC sets.
   EXPECT_EQ(&AC, CG.lookupSCC(A1));
   EXPECT_EQ(&AC, CG.lookupSCC(A2));
   EXPECT_EQ(&AC, CG.lookupSCC(A3));
   EXPECT_EQ(&BC, CG.lookupSCC(B1));
TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) {
   ASSERT_EQ(&CC, CG.lookupSCC(C1));
   ASSERT_EQ(&CC, CG.lookupSCC(C2));
   ASSERT_EQ(&CC, CG.lookupSCC(C3));
   ASSERT_EQ(&DC, CG.lookupSCC(D1));
   ASSERT_EQ(&DC, CG.lookupSCC(D2));
   ASSERT_EQ(&DC, CG.lookupSCC(D3));
   ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
 
-  CC.insertIncomingEdge(D2, C2);
+  CC.insertIncomingEdge(D2, C2, LazyCallGraph::Edge::Call);
   EXPECT_EQ(2, std::distance(D2.begin(), D2.end()));
 
   // Make sure we have the correct nodes in the SCC sets.
   EXPECT_EQ(&CC, CG.lookupSCC(C1));
   EXPECT_EQ(&CC, CG.lookupSCC(C2));
   EXPECT_EQ(&CC, CG.lookupSCC(C3));
   EXPECT_EQ(&CC, CG.lookupSCC(D1));
   EXPECT_EQ(&CC, CG.lookupSCC(D2));
TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) {
   LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a"));
   LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b"));
   LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c"));
   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
 
   // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs.
-  SCC.insertIntraSCCEdge(A, C);
+  SCC.insertIntraSCCEdge(A, C, LazyCallGraph::Edge::Call);
   EXPECT_EQ(2, std::distance(A.begin(), A.end()));
   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
 
   // Insert a self edge from 'a' back to 'a'.
-  SCC.insertIntraSCCEdge(A, A);
+  SCC.insertIntraSCCEdge(A, A, LazyCallGraph::Edge::Call);
   EXPECT_EQ(3, std::distance(A.begin(), A.end()));
   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
 }
 
 TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) {
   // A nice fully connected (including self-edges) SCC.