diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h
--- a/llvm/include/llvm/Transforms/IPO/Attributor.h
+++ b/llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -102,6 +102,7 @@
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/iterator.h"
 #include "llvm/Analysis/AssumeBundleQueries.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
@@ -115,6 +116,7 @@
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Support/GraphWriter.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
 
@@ -126,6 +128,7 @@
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
+struct AttributorCallGraph;
 
 class AAManager;
 class AAResults;
@@ -1760,6 +1763,7 @@
   ///}
 
   friend AADepGraph;
+  friend AttributorCallGraph;
 };
 
 /// An interface to query the internal state of an abstract attribute.
@@ -3855,6 +3859,159 @@
   static const char ID;
 };
 
+struct AACallGraphNode;
+struct AACallEdges;
+
+/// An Iterator for call edges, creates AACallEdges attributes in a lazy way.
+/// This iterator becomes invalid if the underlying edge list changes.
+/// So This shouldn't outlive a iteration of Attributor.
+class AACallEdgeIterator
+    : public iterator_adaptor_base<AACallEdgeIterator,
+                                   SetVector<Function *>::iterator> {
+  AACallEdgeIterator(Attributor &A, SetVector<Function *>::iterator Begin)
+      : iterator_adaptor_base(Begin), A(A) {}
+
+public:
+  AACallGraphNode *operator*() const;
+
+private:
+  Attributor &A;
+  friend AACallEdges;
+  friend AttributorCallGraph;
+};
+
+struct AACallGraphNode {
+  AACallGraphNode(Attributor &A) : A(A) {}
+
+  virtual AACallEdgeIterator optimisticEdgesBegin() const = 0;
+  virtual AACallEdgeIterator optimisticEdgesEnd() const = 0;
+
+  /// Iterator range for exploring the call graph.
+  iterator_range<AACallEdgeIterator> optimisticEdgesRange() const {
+    return iterator_range<AACallEdgeIterator>(optimisticEdgesBegin(),
+                                              optimisticEdgesEnd());
+  }
+
+protected:
+  /// Reference to Attributor needed for GraphTraits implementation.
+  Attributor &A;
+};
+
+/// An abstract state for querying live call edges.
+/// This interface uses the Attributor's optimistic liveness
+/// information to compute the edges that are alive.
+struct AACallEdges : public StateWrapper<BooleanState, AbstractAttribute>,
+                     AACallGraphNode {
+  using Base = StateWrapper<BooleanState, AbstractAttribute>;
+
+  AACallEdges(const IRPosition &IRP, Attributor &A)
+      : Base(IRP), AACallGraphNode(A) {}
+
+  /// Get the optimistic edges.
+  virtual const SetVector<Function *> &getOptimisticEdges() const = 0;
+
+  /// Is there in this function call with a unknown Callee.
+  virtual bool hasUnknownCallee() const = 0;
+
+  /// Iterator for exploring the call graph.
+  AACallEdgeIterator optimisticEdgesBegin() const override {
+    return AACallEdgeIterator(A, getOptimisticEdges().begin());
+  }
+
+  /// Iterator for exploring the call graph.
+  AACallEdgeIterator optimisticEdgesEnd() const override {
+    return AACallEdgeIterator(A, getOptimisticEdges().end());
+  }
+
+  /// Create an abstract attribute view for the position \p IRP.
+  static AACallEdges &createForPosition(const IRPosition &IRP, Attributor &A);
+
+  /// See AbstractAttribute::getName()
+  const std::string getName() const override { return "AACallEdges"; }
+
+  /// See AbstractAttribute::getIdAddr()
+  const char *getIdAddr() const override { return &ID; }
+
+  /// This function should return true if the type of the \p AA is AACallEdges.
+  static bool classof(const AbstractAttribute *AA) {
+    return (AA->getIdAddr() == &ID);
+  }
+
+  /// Unique ID (due to the unique address)
+  static const char ID;
+};
+
+// Synthetic root node for the Attributor's internal call graph.
+struct AttributorCallGraph : public AACallGraphNode {
+  AttributorCallGraph(Attributor &A) : AACallGraphNode(A) {}
+
+  AACallEdgeIterator optimisticEdgesBegin() const override {
+    return AACallEdgeIterator(A, A.Functions.begin());
+  }
+
+  AACallEdgeIterator optimisticEdgesEnd() const override {
+    return AACallEdgeIterator(A, A.Functions.end());
+  }
+
+  /// Force populate the entire call graph.
+  void populateAll() const {
+    for (const AACallGraphNode *AA : optimisticEdgesRange()) {
+      // Nothing else to do here.
+      (void)AA;
+    }
+  }
+
+  void print();
+};
+
+template <> struct GraphTraits<AACallGraphNode *> {
+  using NodeRef = AACallGraphNode *;
+  using ChildIteratorType = AACallEdgeIterator;
+
+  static AACallEdgeIterator child_begin(AACallGraphNode *Node) {
+    return Node->optimisticEdgesBegin();
+  }
+
+  static AACallEdgeIterator child_end(AACallGraphNode *Node) {
+    return Node->optimisticEdgesEnd();
+  }
+};
+
+template <>
+struct GraphTraits<AttributorCallGraph *>
+    : public GraphTraits<AACallGraphNode *> {
+  using nodes_iterator = AACallEdgeIterator;
+
+  static AACallGraphNode *getEntryNode(AttributorCallGraph *G) {
+    return static_cast<AACallGraphNode *>(G);
+  }
+
+  static AACallEdgeIterator nodes_begin(const AttributorCallGraph *G) {
+    return G->optimisticEdgesBegin();
+  }
+
+  static AACallEdgeIterator nodes_end(const AttributorCallGraph *G) {
+    return G->optimisticEdgesEnd();
+  }
+};
+
+template <>
+struct DOTGraphTraits<AttributorCallGraph *> : public DefaultDOTGraphTraits {
+  DOTGraphTraits(bool Simple = false) : DefaultDOTGraphTraits(Simple) {}
+
+  std::string getNodeLabel(const AACallGraphNode *Node,
+                           const AttributorCallGraph *Graph) {
+    const AACallEdges *AACE = static_cast<const AACallEdges *>(Node);
+    return AACE->getAssociatedFunction()->getName().str();
+  }
+
+  static bool isNodeHidden(const AACallGraphNode *Node,
+                           const AttributorCallGraph *Graph) {
+    // Hide the synth root.
+    return static_cast<const AACallGraphNode *>(Graph) == Node;
+  }
+};
+
 /// Run options, used by the pass manager.
 enum AttributorRunOption {
   NONE = 0,
diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp
--- a/llvm/lib/Transforms/IPO/Attributor.cpp
+++ b/llvm/lib/Transforms/IPO/Attributor.cpp
@@ -148,6 +148,11 @@
     cl::desc("Allow the Attributor to do call site specific analysis"),
     cl::init(false));
 
+static cl::opt<bool>
+    PrintCallGraph("attributor-print-call-graph", cl::Hidden,
+                   cl::desc("Print Attributor's internal call graph"),
+                   cl::init(false));
+
 /// Logic operators for the change status enum class.
 ///
 ///{
@@ -1466,6 +1471,10 @@
 
 ChangeStatus Attributor::run() {
   TimeTraceScope TimeScope("Attributor::run");
+  AttributorCallGraph ACallGraph(*this);
+
+  if (PrintCallGraph)
+    ACallGraph.populateAll();
 
   Phase = AttributorPhase::UPDATE;
   runTillFixpoint();
@@ -1486,6 +1495,9 @@
   Phase = AttributorPhase::CLEANUP;
   ChangeStatus CleanupChange = cleanupIR();
 
+  if (PrintCallGraph)
+    ACallGraph.print();
+
   return ManifestChange | CleanupChange;
 }
 
diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp
--- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp
+++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp
@@ -30,9 +30,10 @@
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/NoFolder.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO/ArgumentPromotion.h"
 #include "llvm/Transforms/Utils/Local.h"
-
 #include <cassert>
 
 using namespace llvm;
@@ -134,6 +135,7 @@
 PIPE_OPERATOR(AAUndefinedBehavior)
 PIPE_OPERATOR(AAPotentialValues)
 PIPE_OPERATOR(AANoUndef)
+PIPE_OPERATOR(AACallEdges)
 
 #undef PIPE_OPERATOR
 } // namespace llvm
@@ -8133,8 +8135,121 @@
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noundef) }
 };
+
+struct AACallEdgesFunction : public AACallEdges {
+  AACallEdgesFunction(const IRPosition &IRP, Attributor &A)
+      : AACallEdges(IRP, A) {}
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    ChangeStatus Change = ChangeStatus::UNCHANGED;
+    bool OldHasUnknownCallee = HasUnknownCallee;
+
+    auto AddCalledFunction = [&](Function *Fn) {
+      if (CalledFunctions.insert(Fn)) {
+        Change = ChangeStatus::CHANGED;
+        LLVM_DEBUG(dbgs() << "[AACallEdges] New call edge: " << Fn->getName()
+                          << "\n");
+      }
+    };
+
+    auto VisitValue = [&](Value &V, const Instruction *CtxI, bool &HasUnknown,
+                          bool Stripped) -> bool {
+      if (Function *Fn = dyn_cast<Function>(&V)) {
+        AddCalledFunction(Fn);
+      } else {
+        LLVM_DEBUG(dbgs() << "[AACallEdges] Unrecognized value: " << V << "\n");
+        HasUnknown = true;
+      }
+
+      // Explore all values.
+      return true;
+    };
+
+    // Process any value that we might call.
+    auto ProcessCalledOperand = [&](Value *V, Instruction *Ctx) {
+      if (!genericValueTraversal<AACallEdges, bool>(A, IRPosition::value(*V),
+                                                    *this, HasUnknownCallee,
+                                                    VisitValue, nullptr, false))
+        // If we haven't gone through all values, assume that there are unknown
+        // callees.
+        HasUnknownCallee = true;
+    };
+
+    auto ProcessCallInst = [&](Instruction &Inst) {
+      CallBase &CB = static_cast<CallBase &>(Inst);
+
+      // Process callee metadata if available.
+      if (auto *MD = Inst.getMetadata(LLVMContext::MD_callees)) {
+        for (auto &Op : MD->operands()) {
+          Function *Callee = mdconst::extract_or_null<Function>(Op);
+          if (Callee)
+            AddCalledFunction(Callee);
+        }
+        // Callees metadata grantees that the called function is one of its
+        // operands, So we are done.
+        return true;
+      }
+
+      // The most simple case.
+      ProcessCalledOperand(CB.getCalledOperand(), &Inst);
+
+      // Process callback functions.
+      SmallVector<const Use *, 4u> CallbackUses;
+      AbstractCallSite::getCallbackUses(CB, CallbackUses);
+      for (const Use *U : CallbackUses)
+        ProcessCalledOperand(U->get(), &Inst);
+
+      return true;
+    };
+
+    // Visit all callable instructions.
+    if (!A.checkForAllCallLikeInstructions(ProcessCallInst, *this))
+      // If we haven't looked at all call like instructions, assume that there
+      // are unknown callees.
+      HasUnknownCallee = true;
+    // Track changes.
+    if (OldHasUnknownCallee != HasUnknownCallee)
+      Change = ChangeStatus::CHANGED;
+
+    return Change;
+  }
+
+  virtual const SetVector<Function *> &getOptimisticEdges() const override {
+    return CalledFunctions;
+  };
+
+  virtual bool hasUnknownCallee() const override { return HasUnknownCallee; }
+
+  const std::string getAsStr() const override {
+    return "CallEdges[" + std::to_string(HasUnknownCallee) + "," +
+           std::to_string(CalledFunctions.size()) + "]";
+  }
+
+  void trackStatistics() const override {}
+
+  /// Optimistic set of functions that might be called by this function.
+  SetVector<Function *> CalledFunctions;
+
+  /// Does this function have a call to a function that we don't know about.
+  bool HasUnknownCallee;
+};
+
 } // namespace
 
+AACallGraphNode *AACallEdgeIterator::operator*() const {
+  return static_cast<AACallGraphNode *>(const_cast<AACallEdges *>(
+      &A.getOrCreateAAFor<AACallEdges>(IRPosition::function(**I))));
+}
+
+void AttributorCallGraph::print() {
+  std::string Filename = "AttributorCallGraph.dot";
+  std::error_code EC;
+
+  raw_fd_ostream File(Filename, EC, sys::fs::OF_TextWithCRLF);
+  llvm::WriteGraph(File, this);
+}
+
 const char AAReturnedValues::ID = 0;
 const char AANoUnwind::ID = 0;
 const char AANoSync::ID = 0;
@@ -8158,6 +8273,7 @@
 const char AAValueConstantRange::ID = 0;
 const char AAPotentialValues::ID = 0;
 const char AANoUndef::ID = 0;
+const char AACallEdges::ID = 0;
 
 // Macro magic to create the static generator function for attributes that
 // follow the naming scheme.
@@ -8277,6 +8393,7 @@
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAHeapToStack)
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAReachability)
 CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAUndefinedBehavior)
+CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION(AACallEdges)
 
 CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAMemoryBehavior)
 
diff --git a/llvm/test/Transforms/Attributor/callgraph.ll b/llvm/test/Transforms/Attributor/callgraph.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/Attributor/callgraph.ll
@@ -0,0 +1,106 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=attributor -attributor-print-call-graph -S < %s | FileCheck %s --check-prefixes=CHECK
+; RUN: FileCheck %s -input-file=AttributorCallGraph.dot --check-prefix=DOT
+
+
+define dso_local void @func1() {
+; CHECK-LABEL: @func1(
+; CHECK-NEXT:    br label [[TMP2:%.*]]
+; CHECK:       1:
+; CHECK-NEXT:    unreachable
+; CHECK:       2:
+; CHECK-NEXT:    call void @func3()
+; CHECK-NEXT:    ret void
+;
+  %1 = icmp ne i32 0, 0
+  br i1 %1, label %2, label %3
+
+2:                                                ; preds = %0
+  call void @func2()
+  br label %3
+
+3:                                                ; preds = %2, %0
+  call void () @func3()
+  ret void
+}
+
+declare void @func3()
+declare void @func4()
+
+define dso_local void @func2() {
+; CHECK-LABEL: @func2(
+; CHECK-NEXT:    call void @func4()
+; CHECK-NEXT:    ret void
+;
+  call void @func4()
+  ret void
+}
+
+
+define void @func5(i32 %0) {
+; CHECK-LABEL: @func5(
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], void ()* @func4, void ()* @func3
+; CHECK-NEXT:    call void [[TMP3]]()
+; CHECK-NEXT:    ret void
+;
+  %2 = icmp ne i32 %0, 0
+  %3 = select i1 %2, void ()* @func4, void ()* @func3
+  call void () %3()
+  ret void
+}
+
+define void @broker(void ()* %unknown) !callback !0 {
+; CHECK-LABEL: @broker(
+; CHECK-NEXT:    call void [[UNKNOWN:%.*]]()
+; CHECK-NEXT:    ret void
+;
+  call void %unknown()
+  ret void
+}
+
+define void @func6() {
+; CHECK-LABEL: @func6(
+; CHECK-NEXT:    call void @broker(void ()* nocapture nofree noundef @func3)
+; CHECK-NEXT:    ret void
+;
+  call void @broker(void ()* @func3)
+  ret void
+}
+
+define void @func7(void ()* %unknown) {
+; CHECK-LABEL: @func7(
+; CHECK-NEXT:    call void [[UNKNOWN:%.*]](), !callees !2
+; CHECK-NEXT:    ret void
+;
+  call void %unknown(), !callees !2
+  ret void
+}
+
+!0 = !{!1}
+!1 = !{i64 0, i1 false}
+!2 = !{void ()* @func3, void ()* @func4}
+
+; DOT-DAG: Node[[FUNC1:0x[a-z0-9]+]] [shape=record,label="{func1}"];
+; DOT-DAG: Node[[FUNC2:0x[a-z0-9]+]] [shape=record,label="{func2}"];
+; DOT-DAG: Node[[FUNC3:0x[a-z0-9]+]] [shape=record,label="{func3}"];
+; DOT-DAG: Node[[FUNC4:0x[a-z0-9]+]] [shape=record,label="{func4}"];
+; DOT-DAG: Node[[FUNC5:0x[a-z0-9]+]] [shape=record,label="{func5}"];
+; DOT-DAG: Node[[FUNC6:0x[a-z0-9]+]] [shape=record,label="{func6}"];
+; DOT-DAG: Node[[FUNC7:0x[a-z0-9]+]] [shape=record,label="{func7}"];
+
+; DOT-DAG: Node[[BROKER:0x[a-z0-9]+]] [shape=record,label="{broker}"];
+
+; DOT-DAG: Node[[FUNC1]] -> Node[[FUNC3]];
+; DOT-DAG: Node[[FUNC2]] -> Node[[FUNC4]];
+; DOT-DAG: Node[[FUNC5]] -> Node[[FUNC3]];
+; DOT-DAG: Node[[FUNC5]] -> Node[[FUNC4]];
+
+; DOT-DAG: Node[[FUNC6]] -> Node[[BROKER]];
+
+; This one gets added because of the callback metadata.
+; DOT-DAG: Node[[FUNC6]] -> Node[[FUNC3]];
+
+; These ones are added because of the callees metadata.
+; DOT-DAG: Node[[FUNC7]] -> Node[[FUNC3]];
+; DOT-DAG: Node[[FUNC7]] -> Node[[FUNC4]];