Index: include/llvm/Analysis/CallGraph.h
===================================================================
--- include/llvm/Analysis/CallGraph.h
+++ include/llvm/Analysis/CallGraph.h
@@ -47,6 +47,7 @@
 #define LLVM_ANALYSIS_CALLGRAPH_H
 
 #include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Function.h"
@@ -77,9 +78,22 @@
   using FunctionMapTy =
       std::map<const Function *, std::unique_ptr<CallGraphNode>>;
 
+  /// \brief A type for maintaining dummy nodes.
+  ///
+  /// Dummy nodes (i.e., nodes having a null function) include those created to
+  /// represent !callees metadata. A void pointer is used as the key to allow
+  /// for various kinds of dummy nodes. A MapVector is used to ensure a
+  /// deterministic iteration order since there's no meaningful way to sort
+  /// dummy nodes. A deterministic iteration order is primarily useful testing.
+  using DummyNodeMapTy =
+      MapVector<const void *, std::unique_ptr<CallGraphNode>>;
+
   /// \brief A map from \c Function* to \c CallGraphNode*.
   FunctionMapTy FunctionMap;
 
+  /// \brief A map for maintaining dummy nodes.
+  DummyNodeMapTy DummyNodeMap;
+
   /// \brief This node has edges to all external functions and those internal
   /// functions that have their address taken.
   CallGraphNode *ExternalCallingNode;
@@ -99,6 +113,9 @@
   /// functions that it calls.
   void addToCallGraph(Function *F);
 
+  /// \brief Return the dummy node associated with the given pointer.
+  CallGraphNode *getOrInsertDummyNode(const void *P);
+
 public:
   explicit CallGraph(Module &M);
   CallGraph(CallGraph &&Arg);
Index: lib/Analysis/CallGraph.cpp
===================================================================
--- lib/Analysis/CallGraph.cpp
+++ lib/Analysis/CallGraph.cpp
@@ -54,6 +54,8 @@
 #ifndef NDEBUG
   for (auto &I : FunctionMap)
     I.second->allReferencesDropped();
+  for (auto &I : DummyNodeMap)
+    I.second->allReferencesDropped();
 #endif
 }
 
@@ -75,13 +77,34 @@
     for (Instruction &I : BB) {
       if (auto CS = CallSite(&I)) {
         const Function *Callee = CS.getCalledFunction();
-        if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
+        MDNode *CalleesMDNode = I.getMetadata(LLVMContext::MD_callees);
+        if (!Callee && CalleesMDNode) {
+          // If an indirect call site has !callees metadata, we add an edge
+          // from the call site to a dummy node. When constructing the dummy
+          // node, we add edges from it to the functions indicated by the
+          // metadata.
+          bool InitCallees = !DummyNodeMap.count(CalleesMDNode);
+          CallGraphNode *Dummy = getOrInsertDummyNode(CalleesMDNode);
+          Node->addCalledFunction(CS, Dummy);
+          if (!InitCallees)
+            continue;
+          for (const MDOperand &Op : CalleesMDNode->operands()) {
+            auto *MDConstant = mdconst::extract_or_null<Constant>(Op);
+            if (!MDConstant)
+              continue;
+            auto *PossibleCallee = cast<Function>(MDConstant->stripPointerCasts());
+            if (PossibleCallee && !PossibleCallee->isIntrinsic())
+              Dummy->addCalledFunction(CallSite(),
+                                       getOrInsertFunction(PossibleCallee));
+          }
+        } else if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID())) {
           // Indirect calls of intrinsics are not allowed so no need to check.
           // We can be more precise here by using TargetArg returned by
           // Intrinsic::isLeaf.
           Node->addCalledFunction(CS, CallsExternalNode.get());
-        else if (!Callee->isIntrinsic())
+        } else if (!Callee->isIntrinsic()) {
           Node->addCalledFunction(CS, getOrInsertFunction(Callee));
+        }
       }
     }
 }
@@ -107,6 +130,12 @@
 
   for (CallGraphNode *CN : Nodes)
     CN->print(OS);
+
+  // The iteration order of the DummyNodeMap is deterministic (it's a
+  // MapVector), so we don't need to sort the nodes. Just print them in the
+  // order they were created.
+  for (auto &Entry : DummyNodeMap)
+    Entry.second->print(OS);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
@@ -122,6 +151,12 @@
 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
   assert(CGN->empty() && "Cannot remove function from call "
          "graph if it references other functions!");
+
+  // If any dummy node references the node for the given function, we first
+  // need to remove those edges.
+  for (auto &Entry : DummyNodeMap)
+    Entry.second->removeAnyCallEdgeTo(CGN);
+
   Function *F = CGN->getFunction(); // Get the function for the call graph node
   FunctionMap.erase(F);             // Remove the call graph node from the map
 
@@ -156,6 +191,14 @@
   return CGN.get();
 }
 
+CallGraphNode *CallGraph::getOrInsertDummyNode(const void *P) {
+  auto &CGN = DummyNodeMap[P];
+  if (CGN)
+    return CGN.get();
+  CGN = llvm::make_unique<CallGraphNode>(nullptr);
+  return CGN.get();
+}
+
 //===----------------------------------------------------------------------===//
 // Implementations of the CallGraphNode class methods.
 //
@@ -173,7 +216,7 @@
     if (Function *FI = I.second->getFunction())
       OS << "function '" << FI->getName() <<"'\n";
     else
-      OS << "external node\n";
+      OS << "<<null function>><<" << I.second << ">>\n";
   }
   OS << '\n';
 }
Index: test/Analysis/CallGraph/callees-metadata.ll
===================================================================
--- /dev/null
+++ test/Analysis/CallGraph/callees-metadata.ll
@@ -0,0 +1,42 @@
+; RUN: opt < %s -print-callgraph -disable-output 2>&1 | FileCheck %s -check-prefix=CG
+; RUN: opt < %s -print-callgraph-sccs -disable-output 2>&1 | FileCheck %s -check-prefix=SCC
+
+; CG:       Call graph node <<null function>><<{{.+}}>> #uses=0
+; CG-NEXT:    CS<0x0> calls function 'main'
+; CG-NEXT:    CS<0x0> calls function 'add'
+; CG-NEXT:    CS<0x0> calls function 'sub'
+;
+; CG:       Call graph node for function: 'add'<<{{.+}}>> #uses=2
+;
+; CG:       Call graph node for function: 'main'<<{{.+}}>> #uses=1
+; CG-NEXT:    CS<{{.+}}> calls <<null function>><<[[CALLEES:.+]]>>
+;
+; CG:       Call graph node for function: 'sub'<<{{.+}}>> #uses=2
+;
+; CG:       Call graph node <<null function>><<[[CALLEES]]>> #uses=1
+; CG-NEXT:    CS<0x0> calls function 'add'
+; CG-NEXT:    CS<0x0> calls function 'sub'
+;
+; SCC:      SCCs for the program in PostOrder
+; SCC-DAG:  SCC #1 : add
+; SCC-DAG:  SCC #2 : sub
+; SCC:      SCC #3 : external node
+; SCC-NEXT: SCC #4 : main
+; SCC-NEXT: SCC #5 : external node
+
+define i64 @main(i64 %x, i64 %y, i64 (i64, i64)* %binop) {
+  %tmp0 = call i64 %binop(i64 %x, i64 %y), !callees !0
+  ret i64 %tmp0
+}
+
+define i64 @add(i64 %x, i64 %y) {
+  %tmp0 = add i64 %x, %y
+  ret i64 %tmp0
+}
+
+define i64 @sub(i64 %x, i64 %y) {
+  %tmp0 = sub i64 %x, %y
+  ret i64 %tmp0
+}
+
+!0 = !{i64 (i64, i64)* @add, i64 (i64, i64)* @sub}
Index: test/Analysis/CallGraph/non-leaf-intrinsics.ll
===================================================================
--- test/Analysis/CallGraph/non-leaf-intrinsics.ll
+++ test/Analysis/CallGraph/non-leaf-intrinsics.ll
@@ -26,7 +26,7 @@
 ; CHECK:  CS<0x0> calls function 'f'
 
 ; CHECK: Call graph node for function: 'calls_patchpoint'
-; CHECK-NEXT:  CS<[[addr_1:[^>]+]]> calls external node
+; CHECK-NEXT:  CS<[[addr_1:[^>]+]]> calls <<null function>>
 
 ; CHECK: Call graph node for function: 'calls_statepoint'
-; CHECK-NEXT:  CS<[[addr_0:[^>]+]]> calls external node
+; CHECK-NEXT:  CS<[[addr_0:[^>]+]]> calls <<null function>>