[analyzer] Improve the accuracy of the Clang call graph analysis

[jcranmer-intel]

Summary

This patch improves Clang call graph analysis by adding in expressions that are not found in regular function bodies, such as default arguments or C++ member initializers.

[NoQ]

This will slightly skew Static Analyzer exploration order, not necessarily in a good way, as default arguments and (sometimes) default initializers are not modeled properly. But this doesn't sound dangerous, because whether functions will be analyzed at top level doesn't depend on where they're positioned in the CallGraph, but instead on whether they've been actually visited during symbolic execution. So it's mostly about order rather than coverage. So i'm not worried.

[NoQ]

Do you have commit access or should i commit this for you?

[jcranmer-intel]

No, I do not have commit access, so if you could commit it, it would be greatly appreciated.

[NoQ]

Hmm, the patch doesn't pass its own test for me, could you double-check?

[jcranmer-intel]

The test has been passing for me. What error are you seeing?

[NoQ]

For me ddd() doesn't call c::c(). I can fix it by adding the following code:

void VisitCXXConstructExpr(CXXConstructExpr *CE) {
  addCalledDecl(CE->getConstructor());
  VisitChildren(CE);
}

I don't see why it would work without that code, as CXXConstructExpr isn't a sub-class of CallExpr. So that's another obvious omission in the CallGraph.

Might it be that you have it locally but forgot to include in the patch? It also fails a couple more unrelated tests when i add it because it affects analysis order.

[NoQ]

clang/lib/Analysis/CallGraph.cpp

81–116

Yes, there it is. Where does it come from? I don't have it in master.

[jcranmer-intel]

Okay, I see the issue now. I originally developed this patch on a fork with a whole lot of extra changes, and that fork included some extra modifications to the callgraph that I had missed: https://github.com/intel/llvm/commit/971fecdc316930c0c1c79283d1094ee4c4ca41e0#diff-cae4e2b4043cd0f49ce29e77de22a5a5. I'll merge the callgraph-related changes in that patch back onto a clean patch for upstream.

[jcranmer-intel]

I've rolled the relevant call graph analysis changes from the prior commit into this updated patch.

[NoQ]

Thanks! This looks very useful.

clang/lib/Analysis/CallGraph.cpp

97–102

Ugh this is questionable. The object may easily outlive the function, so the destructor may be called from another function. I see where this was supposed to go (i.e., this is perfectly correct when the constructor is constructing a non-RVO'd temporary or a non-NRVO'd local variable), but in the general case it's not true.

The really nice way to implement this functionality would be to rely on the constructor's ConstructionContext, but as of now it's only available in the CFG and there's no easy way to retrieve it by looking at the AST node (and if you have a CFG you might as well look at destructors directly, as they're listed there explicitly).

It should also be possible to do that by hand by matching DeclStmts and CXXBindTemporaryExprs.

Let's omit this part for now because currently the analysis seems to be conservative in the sense that it doesn't add calls when it's not sure.

[Szelethus]

I hope you dont mind me changing the revision title -- many of us are subscribed to the "analyzer" tag and like learning about whats changing :)

This is not an objection to the patch or anything of course, just adding some lurkers.

[jcranmer-intel]

I think there are use cases for having a callgraph that errs on the side of adding edges that might not exist, but I'm happy enough to leave that for a later patch.

This does remind me that we need a real clang IR that we can leverage for this sort of thing.

[NoQ]

Thanks! I'll try to land again.

clang/include/clang/Analysis/CallGraph.h

bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
     return true;
   }
 
   // We are only collecting the declarations, so do not step into the bodies.
   bool TraverseStmt(Stmt *S) { return true; }
 
   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 *);
 };

clang/lib/Analysis/CallGraph.cpp

void addCalledDecl(Decl *D) {
     }
   }
 
   void VisitCallExpr(CallExpr *CE) {
     if (Decl *D = getDeclFromCall(CE))
       addCalledDecl(D);
     VisitChildren(CE);
   }
 
+  void VisitLambdaExpr(LambdaExpr *LE) {
+    if (CXXMethodDecl *MD = LE->getCallOperator())
+      G->VisitFunctionDecl(MD);
+  }
+
+  void VisitCXXNewExpr(CXXNewExpr *E) {
+    if (FunctionDecl *FD = E->getOperatorNew())
+      addCalledDecl(FD);
+    VisitChildren(E);
+  }
+
+  void VisitCXXConstructExpr(CXXConstructExpr *E) {
+    CXXConstructorDecl *Ctor = E->getConstructor();
+    if (FunctionDecl *Def = Ctor->getDefinition())
+      addCalledDecl(Def);
+    const auto *ConstructedType = Ctor->getParent();
+    if (ConstructedType->hasUserDeclaredDestructor()) {
+      CXXDestructorDecl *Dtor = ConstructedType->getDestructor();
+      if (FunctionDecl *Def = Dtor->getDefinition())
+        addCalledDecl(Def);
+    }
+    VisitChildren(E);
+  }
+
+  // Include the evaluation of the default argument.
+  void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) {
+    Visit(E->getExpr());
+  }
+
+  // Include the evaluation of the default initializers in a class.
+  void VisitCXXDefaultInitExpr(CXXDefaultInitExpr *E) {
+    Visit(E->getExpr());
+  }
+
   // Adds may-call edges for the ObjC message sends.
   void VisitObjCMessageExpr(ObjCMessageExpr *ME) {
     if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) {
       Selector Sel = ME->getSelector();
 
       // Find the callee definition within the same translation unit.
       Decl *D = nullptr;
       if (ME->isInstanceMessage())
         D = IDecl->lookupPrivateMethod(Sel);
bool CallGraph::includeInGraph(const Decl *D) {
   }
 
   return true;
 }
 
 void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
   assert(D);
 
-  // Allocate a new node, mark it as root, and process it's calls.
+  // Allocate a new node, mark it as root, and process its calls.
   CallGraphNode *Node = getOrInsertNode(D);
 
   // Process all the calls by this function as well.
   CGBuilder builder(this, Node);
   if (Stmt *Body = D->getBody())
     builder.Visit(Body);
+
+  // Include C++ constructor member initializers.
+  if (auto constructor = dyn_cast<CXXConstructorDecl>(D)) {
+    for (CXXCtorInitializer *init : constructor->inits()) {
+      builder.Visit(init->getInit());
+    }
+  }
 }
 
 CallGraphNode *CallGraph::getNode(const Decl *F) const {
   FunctionMapTy::const_iterator I = FunctionMap.find(F);
   if (I == FunctionMap.end()) return nullptr;
   return I->second.get();
 }
 

clang/test/Analysis/cxx-callgraph.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.DumpCallGraph %s 2>&1 | FileCheck %s
+
+static int aaa() {
+  return 0;
+}
+
+static int bbb(int param=aaa()) {
+  return 1;
+}
+
+int ddd();
+
+struct c {
+  c(int param=2) : val(bbb(param)) {}
+  int val;
+  int val2 = ddd();
+};
+
+int ddd() {
+  c c;
+  return bbb();
+}
+
+// CHECK:--- Call graph Dump ---
+// CHECK-NEXT: {{Function: < root > calls: aaa bbb c::c ddd}}
+// CHECK-NEXT: {{Function: c::c calls: bbb ddd $}}
+// CHECK-NEXT: {{Function: ddd calls: c::c bbb aaa $}}
+// CHECK-NEXT: {{Function: bbb calls: $}}
+// CHECK-NEXT: {{Function: aaa calls: $}}