Correct callgraph construction. It has two problems:

(1) code left over from the days of ConstantPointerRef:
if a use of a function is a GlobalValue then that is
not considered a reason to add an edge from the external
node, even though the use may be as an initializer for
an externally visible global!  There might be some point
to this behaviour when the use is by an alias (though the
code predated aliases by some centuries), but I think
PR2782 is a better way of handling that.  (2) If function
F calls function G, and also G is a parameter to the
call, then an F->G edge is not added to the callgraph.
While this doesn't seem to matter much, adding such an
edge makes the callgraph more regular.
In addition, the new code should be faster as well as
simpler.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@55987 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 36 insertions, 34 deletions

diff --git a/lib/Analysis/IPA/CallGraph.cpp b/lib/Analysis/IPA/CallGraph.cpp
index 062e859..d24373c 100644
--- a/lib/Analysis/IPA/CallGraph.cpp
+++ b/lib/Analysis/IPA/CallGraph.cpp
@@ -21,14 +21,6 @@
 #include <ostream>
 using namespace llvm;
 
-/// isOnlyADirectCall - Return true if this callsite is *just* a direct call to
-/// the specified function.  Specifically return false if the callsite also
-/// takes the address of the function.
-static bool isOnlyADirectCall(Function *F, CallSite CS) {
-  if (!CS.getInstruction()) return false;
-  return !CS.hasArgument(F);
-}
-
 namespace {
 
 //===----------------------------------------------------------------------===//
@@ -137,44 +129,32 @@ private:
     if (F->isDeclaration() && !F->isIntrinsic())
       Node->addCalledFunction(CallSite(), CallsExternalNode);
 
-    // Loop over all of the users of the function... looking for callers...
-    //
+    // Loop over all of the users of the function, looking for non-call uses.
     bool isUsedExternally = false;
-    for (Value::use_iterator I = F->use_begin(), E = F->use_end(); I != E; ++I){
+    for (Value::use_iterator I = F->use_begin(), E = F->use_end();
+         I != E && !isUsedExternally; ++I) {
       if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
         CallSite CS = CallSite::get(Inst);
-        if (isOnlyADirectCall(F, CS))
-          getOrInsertFunction(Inst->getParent()->getParent())
-              ->addCalledFunction(CS, Node);
-        else
-          isUsedExternally = true;
-      } else if (GlobalValue *GV = dyn_cast<GlobalValue>(*I)) {
-        for (Value::use_iterator I = GV->use_begin(), E = GV->use_end();
-             I != E; ++I)
-          if (Instruction *Inst = dyn_cast<Instruction>(*I)) {
-            CallSite CS = CallSite::get(Inst);
-            if (isOnlyADirectCall(F, CS))
-              getOrInsertFunction(Inst->getParent()->getParent())
-                ->addCalledFunction(CS, Node);
-            else
-              isUsedExternally = true;
-          } else {
-            isUsedExternally = true;
-          }
-      } else {                        // Can't classify the user!
+        isUsedExternally = !CS.getInstruction() || CS.hasArgument(F);
+      } else {                        // User is not a direct call!
         isUsedExternally = true;
       }
     }
     if (isUsedExternally)
       ExternalCallingNode->addCalledFunction(CallSite(), Node);
 
-    // Look for an indirect function call.
+    // 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 = CallSite::get(II);
-      if (CS.getInstruction() && !CS.getCalledFunction())
-        Node->addCalledFunction(CS, CallsExternalNode);
+        CallSite CS = CallSite::get(II);
+        if (CS.getInstruction()) {
+          const Function *Callee = CS.getCalledFunction();
+          if (Callee)
+            Node->addCalledFunction(CS, getOrInsertFunction(Callee));
+          else
+            Node->addCalledFunction(CS, CallsExternalNode);
+        }
       }
   }
 
diff --git a/test/Analysis/CallGraph/2008-09-09-DirectCall.ll b/test/Analysis/CallGraph/2008-09-09-DirectCall.ll
new file mode 100644
index 0000000..4f090d5
--- /dev/null
+++ b/test/Analysis/CallGraph/2008-09-09-DirectCall.ll
@@ -0,0 +1,12 @@
+; RUN: llvm-as < %s | opt -analyze -callgraph -disable-output | grep {Calls function 'callee'} | count 2
+
+define internal void @callee(...) {
+entry:
+	unreachable
+}
+
+define void @caller() {
+entry:
+	call void (...)* @callee( void (...)* @callee )
+	unreachable
+}
diff --git a/test/Analysis/CallGraph/2008-09-09-UsedByGlobal.ll b/test/Analysis/CallGraph/2008-09-09-UsedByGlobal.ll
new file mode 100644
index 0000000..e37e112
--- /dev/null
+++ b/test/Analysis/CallGraph/2008-09-09-UsedByGlobal.ll
@@ -0,0 +1,7 @@
+; RUN: llvm-as < %s | opt -analyze -callgraph -disable-output | grep {Calls function}
+
+@a = global void ()* @f		; <void ()**> [#uses=0]
+
+define internal void @f() {
+	unreachable
+}
diff --git a/test/Analysis/CallGraph/dg.exp b/test/Analysis/CallGraph/dg.exp
new file mode 100644
index 0000000..f200589
--- /dev/null
+++ b/test/Analysis/CallGraph/dg.exp
@@ -0,0 +1,3 @@
+load_lib llvm.exp
+
+RunLLVMTests [lsort [glob -nocomplain $srcdir/$subdir/*.{ll,c,cpp}]]