[CallGraph] Teach the CallGraph about non-leaf intrinsics.

[sanjoy]

Summary

Currently intrinsics don't affect the creation of the call graph.
This is not accurate with respect to statepoint and patchpoint
intrinsics -- these do call (or invoke) LLVM level functions.

This change fixes this inconsistency by adding a call to the external
node for call sites that call these non-leaf intrinsics. This coupled
with the fact that these intrinsics also escape the function pointer
they call gives us a conservatively correct call graph.

[chandlerc]

As I mentioned on the email thread, I expect LazyCallGraph to just DTRT, but I'd love it if you could add the analogous test case to it and make sure of that.

This patch looks fine without the output parameter (see my comment below). If I've missed something and it is needed, just explain and I'll think more about the API.

include/llvm/IR/Intrinsics.h

55–61 ↗

(On Diff #27905)

The TargetArg parameter isn't used yet, correct? I'd leave it off until it is used. I'm not a huge fan of the unsigned output parameter, but hard to suggest alternatives when there are no users..

[pgavlin]

This looks good to me as well. I'm also a bit leery of returning the call target as an argument index. Perhaps it will eventually make more sense to add an overload that operates on the call itself and returns the argument itself, but as Chandler mentioned, it's hard to tell without an example use.

[sanjoy]

• address review

llvm/trunk/include/llvm/Analysis/CallGraph.h

 
 #ifndef LLVM_ANALYSIS_CALLGRAPH_H
 #define LLVM_ANALYSIS_CALLGRAPH_H
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include <map>
 
 namespace llvm {
 
 class Function;
 class Module;
void stealCalledFunctionsFrom(CallGraphNode *N) {
     assert(CalledFunctions.empty() &&
            "Cannot steal callsite information if I already have some");
     std::swap(CalledFunctions, N->CalledFunctions);
   }
 
   /// \brief Adds a function to the list of functions called by this one.
   void addCalledFunction(CallSite CS, CallGraphNode *M) {
     assert(!CS.getInstruction() || !CS.getCalledFunction() ||
-           !CS.getCalledFunction()->isIntrinsic());
+           !CS.getCalledFunction()->isIntrinsic() ||
+           !Intrinsic::isLeaf(CS.getCalledFunction()->getIntrinsicID()));
     CalledFunctions.emplace_back(CS.getInstruction(), M);
     M->AddRef();
   }
 
   void removeCallEdge(iterator I) {
     I->second->DropRef();
     *I = CalledFunctions.back();
     CalledFunctions.pop_back();

llvm/trunk/include/llvm/IR/Intrinsics.h

#undef GET_INTRINSIC_ENUM_VALUES
 
   /// Return the function type for an intrinsic.
   FunctionType *getType(LLVMContext &Context, ID id,
                         ArrayRef<Type*> Tys = None);
 
   /// Returns true if the intrinsic can be overloaded.
   bool isOverloaded(ID id);
 
+  /// Returns true if the intrinsic is a leaf, i.e. it does not make any calls
+  /// itself.  Most intrinsics are leafs, the exceptions being the patchpoint
+  /// and statepoint intrinsics. These call (or invoke) their "target" argument.
+  bool isLeaf(ID id);
+
   /// Return the attributes for an intrinsic.
   AttributeSet getAttributes(LLVMContext &C, ID id);
 
   /// Create or insert an LLVM Function declaration for an intrinsic, and return
   /// it.
   ///
   /// The Tys parameter is for intrinsics with overloaded types (e.g., those
   /// using iAny, fAny, vAny, or iPTRAny).  For a declaration of an overloaded

llvm/trunk/lib/Analysis/IPA/CallGraph.cpp

void CallGraph::addToCallGraph(Function *F) {
 
   // Look for calls by this function.
   for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
     for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;
          ++II) {
       CallSite CS(cast<Value>(II));
       if (CS) {
         const Function *Callee = CS.getCalledFunction();
-        if (!Callee)
+        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);
         else if (!Callee->isIntrinsic())
           Node->addCalledFunction(CS, getOrInsertFunction(Callee));
       }
     }
 }
 
 void CallGraph::print(raw_ostream &OS) const {

llvm/trunk/lib/Analysis/IPA/CallGraphSCCPass.cpp

for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
           // list of the same call.
           CallSites.count(I->first) ||
 
           // If the call edge is not from a call or invoke, or it is a
           // instrinsic call, then the function pass RAUW'd a call with 
           // another value. This can happen when constant folding happens
           // of well known functions etc.
           !CallSite(I->first) ||
-           (CallSite(I->first).getCalledFunction() &&
-            CallSite(I->first).getCalledFunction()->isIntrinsic())) {
+           CallSite(I->first).getCalledFunction()->isIntrinsic() &&
+           Intrinsic::isLeaf(
+               CallSite(I->first).getCalledFunction()->getIntrinsicID()))) {
         assert(!CheckingMode &&
                "CallGraphSCCPass did not update the CallGraph correctly!");
         
         // If this was an indirect call site, count it.
         if (!I->second->getFunction())
           ++NumIndirectRemoved;
         else 
           ++NumDirectRemoved;

llvm/trunk/lib/IR/Function.cpp

 }
 
 bool Intrinsic::isOverloaded(ID id) {
 #define GET_INTRINSIC_OVERLOAD_TABLE
 #include "llvm/IR/Intrinsics.gen"
 #undef GET_INTRINSIC_OVERLOAD_TABLE
 }
 
+bool Intrinsic::isLeaf(ID id) {
+  switch (id) {
+  default:
+    return true;
+
+  case Intrinsic::experimental_gc_statepoint:
+  case Intrinsic::experimental_patchpoint_void:
+  case Intrinsic::experimental_patchpoint_i64:
+    return false;
+  }
+}
+
 /// This defines the "Intrinsic::getAttributes(ID id)" method.
 #define GET_INTRINSIC_ATTRIBUTES
 #include "llvm/IR/Intrinsics.gen"
 #undef GET_INTRINSIC_ATTRIBUTES
 
 Function *Intrinsic::getDeclaration(Module *M, ID id, ArrayRef<Type*> Tys) {
   // There can never be multiple globals with the same name of different types,
   // because intrinsics must be a specific type.

llvm/trunk/test/Analysis/CallGraph/non-leaf-intrinsics.ll

+; RUN: opt -S -print-callgraph -disable-output < %s 2>&1 | FileCheck %s
+
+declare void @llvm.experimental.patchpoint.void(i64, i32, i8*, i32, ...)
+declare i32 @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
+
+define private void @f() {
+  ret void
+}
+
+define void @calls_statepoint(i8 addrspace(1)* %arg) gc "statepoint-example" {
+entry:
+  %cast = bitcast i8 addrspace(1)* %arg to i64 addrspace(1)*
+  %safepoint_token = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @f, i32 0, i32 0, i32 0, i32 5, i32 0, i32 0, i32 0, i32 10, i32 0, i8 addrspace(1)* %arg, i64 addrspace(1)* %cast, i8 addrspace(1)* %arg, i8 addrspace(1)* %arg)
+  ret void
+}
+
+define void @calls_patchpoint() {
+entry:
+  %c = bitcast void()* @f to i8*
+  tail call void (i64, i32, i8*, i32, ...) @llvm.experimental.patchpoint.void(i64 1, i32 15, i8* %c, i32 0, i16 65535, i16 -1, i32 65536, i32 2000000000, i32 2147483647, i32 -1, i32 4294967295, i32 4294967296, i64 2147483648, i64 4294967295, i64 4294967296, i64 -1)
+  ret void
+}
+
+
+; CHECK: Call graph node <<null function>>
+; CHECK:  CS<0x0> calls function 'f'
+
+; CHECK: Call graph node for function: 'calls_statepoint'
+; CHECK-NEXT:  CS<[[addr_0:[^>]+]]> calls external node
+
+; CHECK: Call graph node for function: 'calls_patchpoint'
+; CHECK-NEXT:  CS<[[addr_1:[^>]+]]> calls external node