[clang][Analysis] CallGraph: store the actual call `Expr*` in the CallGraphNode::CallRecord

[lebedev.ri]

Summary

Storing not just the callee, but the actual call may be interesting for some use-cases.
In particular, D72362 would like that to better pretty-print the cycles in call graph.

[NoQ]

Looks great, thanks!

[lebedev.ri]

Rebased, NFC.

In D74081#1860932, @NoQ wrote:

Looks great, thanks!

Thank you for the review!

clang-tools-extra/clang-move/HelperDeclRefGraph.cpp

void HelperDeclRefGraph::print(raw_ostream &OS) const {
   for (auto I = DeclMap.begin(); I != DeclMap.end(); ++I) {
     const CallGraphNode *N = (I->second).get();
 
     OS << "  Declarations: ";
     N->print(OS);
     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';
   }
   OS.flush();
 }
 
 void HelperDeclRefGraph::addEdge(const Decl *Caller, const Decl *Callee) {
   assert(Caller);
   assert(Callee);
 
   // Ignore the case where Caller equals Callee. This happens in the static
   // class member definitions in global namespace like "int CLASS::static_var =
   // 1;", its DC is a VarDel whose outmost enclosing declaration is the "CLASS"
   // CXXRecordDecl.
   if (Caller == Callee) return;
 
   // 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()); }
 
 CallGraphNode *HelperDeclRefGraph::getOrInsertNode(Decl *F) {
   F = F->getCanonicalDecl();
   std::unique_ptr<CallGraphNode> &Node = DeclMap[F];
   if (Node)

clang/include/clang/Analysis/CallGraph.h

 
 #include "clang/AST/Decl.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/GraphTraits.h"
 #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 {
 
 class CallGraphNode;
 class Decl;
 class DeclContext;
 class Stmt;
public:
 
   bool shouldWalkTypesOfTypeLocs() const { return false; }
   bool shouldVisitTemplateInstantiations() const { return true; }
   bool shouldVisitImplicitCode() const { return true; }
 
 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.
   Decl *FD;
 
   /// The list of functions called from this node.
   SmallVector<CallRecord, 5> CalledFunctions;
 
 public:
   CallGraphNode(Decl *D) : FD(D) {}
 
   using iterator = SmallVectorImpl<CallRecord>::iterator;
   using const_iterator = SmallVectorImpl<CallRecord>::const_iterator;
 
   /// Iterators through all the callees/children of the node.
   iterator begin() { return CalledFunctions.begin(); }
   iterator end() { return CalledFunctions.end(); }
   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; }
 
   void print(raw_ostream &os) const;
   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 *;
   using ChildIteratorType = NodeType::iterator;
 
   static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
   static ChildIteratorType child_begin(NodeType *N) { return N->begin();  }
   static ChildIteratorType child_end(NodeType *N) { return N->end(); }

clang/lib/Analysis/CallGraph.cpp

Decl *getDeclFromCall(CallExpr *CE) {
     if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) {
       NumBlockCallEdges++;
       return Block->getBlockDecl();
     }
 
     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);
   }
 
   void VisitLambdaExpr(LambdaExpr *LE) {
     if (FunctionTemplateDecl *FTD = LE->getDependentCallOperator())
       for (FunctionDecl *FD : FTD->specializations())
         G->VisitFunctionDecl(FD);
     else if (CXXMethodDecl *MD = LE->getCallOperator())
       G->VisitFunctionDecl(MD);
   }
 
   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);
   }
 
   // Include the evaluation of the default argument.
   void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) {
     Visit(E->getExpr());
   }
 
if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) {
 
       // Find the callee definition within the same translation unit.
       Decl *D = nullptr;
       if (ME->isInstanceMessage())
         D = IDecl->lookupPrivateMethod(Sel);
       else
         D = IDecl->lookupPrivateClassMethod(Sel);
       if (D) {
-        addCalledDecl(D);
+        addCalledDecl(D, ME);
         NumObjCCallEdges++;
       }
     }
   }
 
   void VisitChildren(Stmt *S) {
     for (Stmt *SubStmt : S->children())
       if (SubStmt)
CallGraphNode *CallGraph::getOrInsertNode(Decl *F) {
 
   std::unique_ptr<CallGraphNode> &Node = FunctionMap[F];
   if (Node)
     return Node.get();
 
   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();
 }
 
 void CallGraph::print(raw_ostream &OS) const {
   OS << " --- Call graph Dump --- \n";
 
   // We are going to print the graph in reverse post order, partially, to make
   // sure the output is deterministic.
   llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this);
   for (llvm::ReversePostOrderTraversal<const CallGraph *>::rpo_iterator
          I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
     const CallGraphNode *N = *I;
 
     OS << "  Function: ";
     if (N == Root)
       OS << "< root >";
     else
       N->print(OS);
 
     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';
   }
   OS.flush();
 }
 
 LLVM_DUMP_METHOD void CallGraph::dump() const {