diff --git a/clang-tools-extra/clang-move/HelperDeclRefGraph.cpp b/clang-tools-extra/clang-move/HelperDeclRefGraph.cpp
--- a/clang-tools-extra/clang-move/HelperDeclRefGraph.cpp
+++ b/clang-tools-extra/clang-move/HelperDeclRefGraph.cpp
@@ -27,7 +27,7 @@
     OS << " (" << N << ") ";
     OS << " calls: ";
     for (auto CI = N->begin(), CE = N->end(); CI != CE; ++CI) {
-      (*CI)->print(OS);
+      CI->Callee->print(OS);
       OS << " (" << CI << ") ";
     }
     OS << '\n';
@@ -48,7 +48,7 @@
   // Allocate a new node, mark it as root, and process it's calls.
   CallGraphNode *CallerNode = getOrInsertNode(const_cast<Decl *>(Caller));
   CallGraphNode *CalleeNode = getOrInsertNode(const_cast<Decl *>(Callee));
-  CallerNode->addCallee(CalleeNode);
+  CallerNode->addCallee({CalleeNode, /*CallExpr=*/nullptr});
 }
 
 void HelperDeclRefGraph::dump() const { print(llvm::errs()); }
diff --git a/clang/include/clang/Analysis/CallGraph.h b/clang/include/clang/Analysis/CallGraph.h
--- a/clang/include/clang/Analysis/CallGraph.h
+++ b/clang/include/clang/Analysis/CallGraph.h
@@ -24,6 +24,7 @@
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
 #include <memory>
 
 namespace clang {
@@ -136,14 +137,23 @@
 private:
   /// Add the given declaration to the call graph.
   void addNodeForDecl(Decl *D, bool IsGlobal);
-
-  /// Allocate a new node in the graph.
-  CallGraphNode *allocateNewNode(Decl *);
 };
 
 class CallGraphNode {
 public:
-  using CallRecord = CallGraphNode *;
+  struct CallRecord {
+    CallGraphNode *Callee;
+    Expr *CallExpr;
+
+    CallRecord() = default;
+
+    CallRecord(CallGraphNode *Callee_, Expr *CallExpr_)
+        : Callee(Callee_), CallExpr(CallExpr_) {}
+
+    // The call destination is the only important data here,
+    // allow to transparently unwrap into it.
+    operator CallGraphNode *() const { return Callee; }
+  };
 
 private:
   /// The function/method declaration.
@@ -164,12 +174,18 @@
   const_iterator begin() const { return CalledFunctions.begin(); }
   const_iterator end() const { return CalledFunctions.end(); }
 
+  /// Iterator access to callees/children of the node.
+  llvm::iterator_range<iterator> callees() {
+    return llvm::make_range(begin(), end());
+  }
+  llvm::iterator_range<const_iterator> callees() const {
+    return llvm::make_range(begin(), end());
+  }
+
   bool empty() const { return CalledFunctions.empty(); }
   unsigned size() const { return CalledFunctions.size(); }
 
-  void addCallee(CallGraphNode *N) {
-    CalledFunctions.push_back(N);
-  }
+  void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); }
 
   Decl *getDecl() const { return FD; }
 
@@ -177,11 +193,44 @@
   void dump() const;
 };
 
+// NOTE: we are comparing based on the callee only. So different call records
+// (with different call expressions) to the same callee will compare equal!
+inline bool operator==(const CallGraphNode::CallRecord &LHS,
+                       const CallGraphNode::CallRecord &RHS) {
+  return LHS.Callee == RHS.Callee;
+}
+
 } // namespace clang
 
-// Graph traits for iteration, viewing.
 namespace llvm {
 
+// Specialize DenseMapInfo for clang::CallGraphNode::CallRecord.
+template <> struct DenseMapInfo<clang::CallGraphNode::CallRecord> {
+  static inline clang::CallGraphNode::CallRecord getEmptyKey() {
+    return clang::CallGraphNode::CallRecord(
+        DenseMapInfo<clang::CallGraphNode *>::getEmptyKey(),
+        DenseMapInfo<clang::Expr *>::getEmptyKey());
+  }
+
+  static inline clang::CallGraphNode::CallRecord getTombstoneKey() {
+    return clang::CallGraphNode::CallRecord(
+        DenseMapInfo<clang::CallGraphNode *>::getTombstoneKey(),
+        DenseMapInfo<clang::Expr *>::getTombstoneKey());
+  }
+
+  static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val) {
+    // NOTE: we are comparing based on the callee only.
+    // Different call records with the same callee will compare equal!
+    return DenseMapInfo<clang::CallGraphNode *>::getHashValue(Val.Callee);
+  }
+
+  static bool isEqual(const clang::CallGraphNode::CallRecord &LHS,
+                      const clang::CallGraphNode::CallRecord &RHS) {
+    return LHS == RHS;
+  }
+};
+
+// Graph traits for iteration, viewing.
 template <> struct GraphTraits<clang::CallGraphNode*> {
   using NodeType = clang::CallGraphNode;
   using NodeRef = clang::CallGraphNode *;
diff --git a/clang/lib/Analysis/CallGraph.cpp b/clang/lib/Analysis/CallGraph.cpp
--- a/clang/lib/Analysis/CallGraph.cpp
+++ b/clang/lib/Analysis/CallGraph.cpp
@@ -66,16 +66,16 @@
     return nullptr;
   }
 
-  void addCalledDecl(Decl *D) {
+  void addCalledDecl(Decl *D, Expr *CallExpr) {
     if (G->includeInGraph(D)) {
       CallGraphNode *CalleeNode = G->getOrInsertNode(D);
-      CallerNode->addCallee(CalleeNode);
+      CallerNode->addCallee({CalleeNode, CallExpr});
     }
   }
 
   void VisitCallExpr(CallExpr *CE) {
     if (Decl *D = getDeclFromCall(CE))
-      addCalledDecl(D);
+      addCalledDecl(D, CE);
     VisitChildren(CE);
   }
 
@@ -89,14 +89,14 @@
 
   void VisitCXXNewExpr(CXXNewExpr *E) {
     if (FunctionDecl *FD = E->getOperatorNew())
-      addCalledDecl(FD);
+      addCalledDecl(FD, E);
     VisitChildren(E);
   }
 
   void VisitCXXConstructExpr(CXXConstructExpr *E) {
     CXXConstructorDecl *Ctor = E->getConstructor();
     if (FunctionDecl *Def = Ctor->getDefinition())
-      addCalledDecl(Def);
+      addCalledDecl(Def, E);
     VisitChildren(E);
   }
 
@@ -122,7 +122,7 @@
       else
         D = IDecl->lookupPrivateClassMethod(Sel);
       if (D) {
-        addCalledDecl(D);
+        addCalledDecl(D, ME);
         NumObjCCallEdges++;
       }
     }
@@ -207,7 +207,7 @@
   Node = std::make_unique<CallGraphNode>(F);
   // Make Root node a parent of all functions to make sure all are reachable.
   if (F)
-    Root->addCallee(Node.get());
+    Root->addCallee({Node.get(), /*Call=*/nullptr});
   return Node.get();
 }
 
@@ -230,8 +230,8 @@
     OS << " calls: ";
     for (CallGraphNode::const_iterator CI = N->begin(),
                                        CE = N->end(); CI != CE; ++CI) {
-      assert(*CI != Root && "No one can call the root node.");
-      (*CI)->print(OS);
+      assert(CI->Callee != Root && "No one can call the root node.");
+      CI->Callee->print(OS);
       OS << " ";
     }
     OS << '\n';