[Attributor] Derive AACallEdges attribute

[kuter]

Summary

This attribute computes the optimistic live call edges using the attributor
liveness information. This attribute will be used for deriving a
inter-procedural function reachability attribute.

[kuter]

The way CallGraph handles callbacks doesn't make sense to me.
In the CallGraph::populateCallGraphNode callbacks are handled by the forEachCallbackFunction function.
like this:

// Add reference to callback functions.
forEachCallbackFunction(*Call, [=](Function *CB) {
    Node->addCalledFunction(nullptr, getOrInsertFunction(CB));
});

Which uses the AbstractCallSite::getCallbackUses and checks if the Use is a function.
The source of the AbstractCallSite::getCallbackUses is given below.

void AbstractCallSite::getCallbackUses(       
    const CallBase &CB, SmallVectorImpl<const Use *> &CallbackUses) { 
  const Function *Callee = CB.getCalledFunction(); 
  if (!Callee)                                                      
    return; 

   ....                                                              
}

CB.getCalledFunction returns null if the call is indirect. And a callback is indirect, right ?
Also the getCallbackUses uses the callback metadata which is intended for the function definitions rather than calls.

Am I misunderstanding something ?

[jdoerfert]

Can you please reupload after clang formatting the code :)

[kuter]

• Custom iterator for lazly creating AACallEdges
• GraphTraits implementation

[kuter]

In D104059#2811617, @jdoerfert wrote:

Can you please reupload after clang formatting the code :)

Sorry, I thought arcanist did that automatically.

[kuter]

• Added DOTGraphTraits implementation
• Added Test
• Small fix

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

3881

Maybe call it AACallEdgeIterator?

3935

Don't store the Attributor instance, let the user pass it where needed.

3961

Same as above.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8177

Rather than asking for liveness, use a generic value traversal to visit all potential values of Val. Each of which is a potential callee. Also make sure to handle the case where a callee is not known, e.g., a function pointer call. We need to add them to the call graph as unknown callees too.

8182

checkForAllCallLikeInstructions

8193

Return at least the number as well.

[kuter]

• Reanme custom iterator
• Use checkForAllCallLikeInstructions

[kuter]

llvm/include/llvm/Transforms/IPO/Attributor.h

3935

I wanted not to but we need this to have a GraphTraits implementation.
GraphTraits::child_begin only takes the node itself and we need Attributor to create the AACallEdges.
I don't think there are any other way to inject the Attributor inside GraphTraits::child_begin

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

3935

Then store it in AACallGraphNode I gues.

[kuter]

Move attributor instance to the AACallGraphNode

[kuter]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8177

Ok when I add the genericValueTraversal should we still keep the getCallbackUses function since it uses the callback metadata ?
There is also a callees meta data that is ment to annotate a call, it gurantees that the called function is one of the functions it specifies.
This seems useful for our purposes. getCallbackUses doesn't use it.

I was planning to add a flag to tell if there are any calls to a unknown function somethling like bool hasUnknownCallee()

Also for us to be able to say that function x can't reach function b, we need to make sure that we know all functions that function x might ever call. Meaning that if there are any functions that x can reach that has a unknown callee we can't tell for sure, right ?

[jdoerfert]

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8177

I would have done getCallbackUses and then on the argument operands a genericValueTraversal. In the code above that means genericValueTraversal for Val. See also callees metadata below

If we have an unknown caller, we can reach any "visible" function. For now, you can assume any function but in reality you could exclude internal functions that don't have their address taken, for example.

So, how to use callees metadata is a good question. We want to expand what an AbstractCallSite is, I think. So first, an AbstractCallSite needs to get a new "kind", which is a direct call site with a "potential" callee. This is somewhat independent and we want to use it also as part of the checkForAllCallSites. To make this happen we'll need to either go through metadata uses (which is hard, IIRC) or use the AACallEdge in checkForAllCallSites. For the latter we also track in the AACallEdgeFunction node what all callers are, basically the callers should notify the AACallEdgeFunction of the Callee. If we do it that way, we can handle callee metadata here. I would suggest to have a new AbstractCallSite interface that allows you to iterate over a set of AbstractCallSites that a CallBase "exposes". For a direct call, that's just the direct callee. For a call with callees metadata, it will be one AbstractCallSite per callee node specified. And for all callbacks annotations, it would be one AbstractCallSite per callback annotation on the callee, basically line 8166-8168 above. This new interface would replace the getCallbackUses above and we could also (for now at least) ignore the genericValueTraversal thing. Certainly remove the isdead part.
Does this make sense?

[kuter]

• Add genericValueTraveral
• Add test a test for call with select (Doesn't work :/)
• Track if there are any unknown callees.

[kuter]

llvm/test/Transforms/Attributor/callgraph.ll

63

This edge is missing. genericValueTraversal doesn't seem to be returning the func4.

[jdoerfert]

More comments, also, please fix the clang tidy warnings, they make it hard to read.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8152

8170

You need to bail if the return value is false, IIRC.

8173

8192

You need to bail if the return value is false.

llvm/test/Transforms/Attributor/callgraph.ll

63

That would be a problem, can you try to figure out what's going on?

[kuter]

Fix code styling.

there is not much I can do with the clang tidy since.

• I can't rename nodes_begin, it is needed for GraphTraits.
• And you should never desconstruct a AACallGraphNode.

[kuter]

Fix the problem with the missing edge.

[kuter]

Asume that there are unknown callees if we haven't looked at all values/instructions.

[kuter]

clang-format

[jdoerfert]

Can you add a test case with a callback and one with an unknown function pointer call. Maybe also one with a function pointer and callee metadata + a FIXME.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8158

[kuter]

• Handle callees metadata..
• Added test cases for callees and callback attributes.
• Small fix

[kuter]

clang-format

[kuter]

small fix

[jdoerfert]

LGTM, some nits. Thanks for fixing this up so quickly.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8179

We should not do this if we have callee metadata. Except maybe (later) if we can improve the callee metadata.

8192

No cast, a Function is a Value.

8224

Documentation.

[hokein]

I encountered two issues while integrating this patch to our internal codebase -- And the fixes look like trivial, I landed them directly to unblock my integration. Feel free to improve them if they don't suit.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

8146

undefined behavior detected by asan: HasUnknownCallee value might be undefined, fixed in 3f5d53a525c62c507a482fd5f4c08451835b342d.

8246

hard-coding a filename looks like not a common pattern in LLVM AFAIK, and the test might fail on some sandbox environment. I landed 7670938bbad8755a34a282febc852651255c69b3 to improve this behavior.

llvm/include/llvm/Transforms/IPO/Attributor.h

 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/GraphTraits.h"
 #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"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/AbstractCallSite.h"
 #include "llvm/IR/ConstantRange.h"
 #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"
 
 namespace llvm {
 
 struct AADepGraphNode;
 struct AADepGraph;
 struct Attributor;
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
+struct AttributorCallGraph;
 
 class AAManager;
 class AAResults;
 class Function;
 
 /// Abstract Attribute helper functions.
 namespace AA {
 /// Try to convert \p V to type \p Ty without introducing new instructions. If
private:
   ///
   ///{
   SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
   SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
   SmallDenseSet<WeakVH, 8> ToBeDeletedInsts;
   ///}
 
   friend AADepGraph;
+  friend AttributorCallGraph;
 };
 
 /// An interface to query the internal state of an abstract attribute.
 ///
 /// The abstract state is a minimal interface that allows the Attributor to
 /// communicate with the abstract attributes about their internal state without
 /// enforcing or exposing implementation details, e.g., the (existence of an)
 /// underlying lattice.
struct AANoUndef
   static bool classof(const AbstractAttribute *AA) {
     return (AA->getIdAddr() == &ID);
   }
 
   /// Unique ID (due to the unique address)
   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,
   MODULE = 1 << 0,
   CGSCC = 1 << 1,
   ALL = MODULE | CGSCC
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H

llvm/lib/Transforms/IPO/Attributor.cpp

static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden,
                                        cl::desc("Print attribute dependencies"),
                                        cl::init(false));
 
 static cl::opt<bool> EnableCallSiteSpecific(
     "attributor-enable-call-site-specific-deduction", cl::Hidden,
     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.
 ///
 ///{
 ChangeStatus llvm::operator|(ChangeStatus L, ChangeStatus R) {
   return L == ChangeStatus::CHANGED ? L : R;
 }
 ChangeStatus llvm::operator&(ChangeStatus L, ChangeStatus R) {
   return L == ChangeStatus::UNCHANGED ? L : R;
#ifdef EXPENSIVE_CHECKS
   }
 #endif
 
   return ManifestChange;
 }
 
 ChangeStatus Attributor::run() {
   TimeTraceScope TimeScope("Attributor::run");
+  AttributorCallGraph ACallGraph(*this);
+
+  if (PrintCallGraph)
+    ACallGraph.populateAll();
 
   Phase = AttributorPhase::UPDATE;
   runTillFixpoint();
 
   // dump graphs on demand
   if (DumpDepGraph)
     DG.dumpGraph();
 
   if (ViewDepGraph)
     DG.viewGraph();
 
   if (PrintDependencies)
     DG.print();
 
   Phase = AttributorPhase::MANIFEST;
   ChangeStatus ManifestChange = manifestAttributes();
 
   Phase = AttributorPhase::CLEANUP;
   ChangeStatus CleanupChange = cleanupIR();
 
+  if (PrintCallGraph)
+    ACallGraph.print();
+
   return ManifestChange | CleanupChange;
 }
 
 ChangeStatus Attributor::updateAA(AbstractAttribute &AA) {
   TimeTraceScope TimeScope(
       AA.getName() + std::to_string(AA.getIRPosition().getPositionKind()) +
       "::updateAA");
   assert(Phase == AttributorPhase::UPDATE &&

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instruction.h"
 #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;
 
 #define DEBUG_TYPE "attributor"
 
 static cl::opt<bool> ManifestInternal(
     "attributor-manifest-internal", cl::Hidden,

 PIPE_OPERATOR(AAReachability)
 PIPE_OPERATOR(AAMemoryBehavior)
 PIPE_OPERATOR(AAMemoryLocation)
 PIPE_OPERATOR(AAValueConstantRange)
 PIPE_OPERATOR(AAPrivatizablePtr)
 PIPE_OPERATOR(AAUndefinedBehavior)
 PIPE_OPERATOR(AAPotentialValues)
 PIPE_OPERATOR(AANoUndef)
+PIPE_OPERATOR(AACallEdges)
 
 #undef PIPE_OPERATOR
 } // namespace llvm
 
 namespace {
 
 /// Get pointer operand of memory accessing instruction. If \p I is
 /// not a memory accessing instruction, return nullptr. If \p AllowVolatile,

 struct AANoUndefCallSiteReturned final
     : AACallSiteReturnedFromReturned<AANoUndef, AANoUndefImpl> {
   AANoUndefCallSiteReturned(const IRPosition &IRP, Attributor &A)
       : AACallSiteReturnedFromReturned<AANoUndef, AANoUndefImpl>(IRP, A) {}
 
   /// 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;
 const char AANoFree::ID = 0;
 const char AANonNull::ID = 0;
 const char AANoRecurse::ID = 0;
 const char AAWillReturn::ID = 0;
 const char AAUndefinedBehavior::ID = 0;
 const char AANoAlias::ID = 0;
 const char AAReachability::ID = 0;
 const char AANoReturn::ID = 0;
 const char AAIsDead::ID = 0;
 const char AADereferenceable::ID = 0;
 const char AAAlign::ID = 0;
 const char AANoCapture::ID = 0;
 const char AAValueSimplify::ID = 0;
 const char AAHeapToStack::ID = 0;
 const char AAPrivatizablePtr::ID = 0;
 const char AAMemoryBehavior::ID = 0;
 const char AAMemoryLocation::ID = 0;
 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.
 
 #define SWITCH_PK_INV(CLASS, PK, POS_NAME)                                     \
   case IRPosition::PK:                                                         \
     llvm_unreachable("Cannot create " #CLASS " for a " POS_NAME " position!");
 

 
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify)
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead)
 CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFree)
 
 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)
 
 #undef CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_NON_RET_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION
 #undef SWITCH_PK_CREATE
 #undef SWITCH_PK_INV

llvm/test/Transforms/Attributor/callgraph.ll

+; 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]];