[CallGraph] Ignore callback uses

[ggeorgakoudis]

Summary

Ignore callback uses when adding a callback function
in the CallGraph. Callback functions are typically
created when outlining, e.g. for OpenMP, so they have
internal scope and linkage. They should not be added
to the ExternalCallingNode since they are only callable
by the specified caller function at creation time.

A CGSCC pass, such as OpenMPOpt, may need to update
the CallGraph by adding a new outlined callback function.
Without ignoring callback uses, adding breaks CGSCC
pass restrictions and results to a broken CallGraph.

[lebedev.ri]

I may be missing context, but this may be missing some wording.
*Why* should they not be in the callgraph?

[ggeorgakoudis]

In D83370#2138377, @lebedev.ri wrote:

I may be missing context, but this may be missing some wording.
*Why* should they not be in the callgraph?

Thanks for the comment. The callback function is in the callgraph but it is not added to the ExternalCallingNode. I have updated the commit message to include more information.

[lebedev.ri]

In D83370#2139632, @ggeorgakoudis wrote:

In D83370#2138377, @lebedev.ri wrote:

I may be missing context, but this may be missing some wording.
*Why* should they not be in the callgraph?

Thanks for the comment. The callback function is in the callgraph but it is not added to the ExternalCallingNode. I have updated the commit message to include more information.

Thanks

[jdoerfert]

llvm/include/llvm/IR/Function.h

834

Not: missing ..

llvm/lib/IR/Function.cpp

1489

Nit: missing ..

[jdoerfert]

LGTM (forgot to accept earlier, sorry).

[ggeorgakoudis]

Update for comment

[ggeorgakoudis]

Update regression test

[lebedev.ri]

I'm not sure if this is the commit to blame, but i think this might have broken http://45.33.8.238/linux/22501/step_12.txt

[lebedev.ri]

Temporarily reverted in c2a61ef3885019c5e0444d8789de63e1ce4d5003.

[lebedev.ri]

Yep, that was it.

[ggeorgakoudis]

Update regression tests under Transforms/Attributor/IPConstantProp

[jdoerfert]

llvm/lib/IR/Function.cpp

1499

You might need to inspect the ACS here. Check if it is really a callback callsite.

llvm/test/Transforms/Attributor/IPConstantProp/pthreads.ll

104 ↗

(On Diff #277051)

TBH, this looks somehow we didn't run the script after a recent update. I'll commit an update to the tests.

[jdoerfert]

llvm/test/Transforms/Attributor/IPConstantProp/arg-count-mismatch.ll

47 ↗

(On Diff #277051)

The problem here is the missing "reference" edge in the old call graph. Before the patch bar is externally callable and foo calls an external function. With the patch, neither is the case but foo is also not calling bar (I think).

The solution is to verify we are looking at a callback call and not any abstract call site. Callback calls cause such "reference" edges since D82572.

[ggeorgakoudis]

Revert changes to regression tests

Check AbstractCallSite is indeed a callback

[jdoerfert]

llvm/lib/IR/Function.cpp

1499

Nit: Put the ACS stuff into a conditional guarded by the ignore. Trying to create an ACS is not completely free.

[ggeorgakoudis]

Update for latest nit comment

[jdoerfert]

LGTM. @lebedev.ri ?

[lebedev.ri]

I don't actually have any opinion here, i just wanted to get the bots green (:

llvm/lib/Analysis/CallGraph.cpp

84

Why not just /*IgnoreCallbackUses=*/true?

[ggeorgakoudis]

Update for latest comment

llvm/include/llvm/IR/Function.h

/// @}
   /// Since no other object in the module can have references into the body of a
   /// function, dropping all references deletes the entire body of the function,
   /// including any contained basic blocks.
   ///
   void dropAllReferences();
 
   /// hasAddressTaken - returns true if there are any uses of this function
   /// other than direct calls or invokes to it, or blockaddress expressions.
-  /// Optionally passes back an offending user for diagnostic purposes.
+  /// Optionally passes back an offending user for diagnostic purposes and
+  /// ignores callback uses.
   ///
-  bool hasAddressTaken(const User** = nullptr) const;
+  bool hasAddressTaken(const User ** = nullptr,
+                       bool IgnoreCallbackUses = false) const;
 
   /// isDefTriviallyDead - Return true if it is trivially safe to remove
   /// this function definition from the module (because it isn't externally
   /// visible, does not have its address taken, and has no callers).  To make
   /// this more accurate, call removeDeadConstantUsers first.
   bool isDefTriviallyDead() const;
 
   /// callsFunctionThatReturnsTwice - Return true if the function has a call to

llvm/lib/Analysis/CallGraph.cpp

bool CallGraph::invalidate(Module &, const PreservedAnalyses &PA,
   auto PAC = PA.getChecker<CallGraphAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>() ||
            PAC.preservedSet<CFGAnalyses>());
 }
 
 void CallGraph::addToCallGraph(Function *F) {
   CallGraphNode *Node = getOrInsertFunction(F);
 
-  // If this function has external linkage or has its address taken, anything
-  // could call it.
-  if (!F->hasLocalLinkage() || F->hasAddressTaken())
+  // If this function has external linkage or has its address taken and
+  // it is not a callback, then anything could call it.
+  if (!F->hasLocalLinkage() ||
+      F->hasAddressTaken(nullptr, /*IgnoreCallbackUses=*/true))
     ExternalCallingNode->addCalledFunction(nullptr, Node);
 
   populateCallGraphNode(Node);
 }
 
 void CallGraph::populateCallGraphNode(CallGraphNode *Node) {
   Function *F = Node->getFunction();
 
   // If this function is not defined in this translation unit, it could call

llvm/lib/IR/Function.cpp

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/IR/AbstractCallSite.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/InstIterator.h"
Optional<Function *> Intrinsic::remangleIntrinsicFunction(Function *F) {
   auto NewDecl = Intrinsic::getDeclaration(F->getParent(), ID, ArgTys);
   NewDecl->setCallingConv(F->getCallingConv());
   assert(NewDecl->getFunctionType() == F->getFunctionType() &&
          "Shouldn't change the signature");
   return NewDecl;
 }
 
 /// hasAddressTaken - returns true if there are any uses of this function
-/// other than direct calls or invokes to it.
-bool Function::hasAddressTaken(const User* *PutOffender) const {
+/// other than direct calls or invokes to it. Optionally ignores callback
+/// uses.
+bool Function::hasAddressTaken(const User **PutOffender,
+                               bool IgnoreCallbackUses) const {
   for (const Use &U : uses()) {
     const User *FU = U.getUser();
     if (isa<BlockAddress>(FU))
       continue;
+
+    if (IgnoreCallbackUses) {
+      AbstractCallSite ACS(&U);
+      if (ACS && ACS.isCallbackCall())
+        continue;
+    }
+
     const auto *Call = dyn_cast<CallBase>(FU);
     if (!Call) {
       if (PutOffender)
         *PutOffender = FU;
       return true;
     }
     if (!Call->isCallee(&U)) {
       if (PutOffender)

llvm/test/Analysis/CallGraph/ignore-callback-uses.ll

+; RUN: opt < %s -print-callgraph -disable-output 2>&1 | FileCheck %s
+; CHECK: Call graph node <<null function>><<{{.*}}>>  #uses=0
+; CHECK-NEXT:   CS<{{.*}}> calls function 'f'
+; CHECK-NEXT:   CS<{{.*}}> calls function '__kmpc_fork_call'
+; CHECK-EMPTY:
+
+%struct.ident_t = type { i32, i32, i32, i32, i8* }
+
+@0 = private unnamed_addr constant [23 x i8] c";unknown;unknown;0;0;;\00", align 1
+@1 = private unnamed_addr global %struct.ident_t { i32 0, i32 2, i32 0, i32 0, i8* getelementptr inbounds ([23 x i8], [23 x i8]* @0, i32 0, i32 0) }, align 8
+
+; Function Attrs: noinline nounwind optnone uwtable
+define dso_local void @f() {
+entry:
+  br label %omp_parallel
+
+omp_parallel:                                     ; preds = %entry
+  call void (%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) @__kmpc_fork_call(%struct.ident_t* @1, i32 0, void (i32*, i32*, ...)* bitcast (void (i32*, i32*)* @f..omp_par to void (i32*, i32*, ...)*))
+  br label %omp.par.exit.split
+
+omp.par.exit.split:                               ; preds = %omp_parallel
+  ret void
+}
+
+; Function Attrs: norecurse nounwind
+define internal void @f..omp_par(i32* noalias %tid.addr, i32* noalias %zero.addr) {
+omp.par.entry:
+  %tid.addr.local = alloca i32, align 4
+  %0 = load i32, i32* %tid.addr, align 4
+  store i32 %0, i32* %tid.addr.local, align 4
+  %tid = load i32, i32* %tid.addr.local, align 4
+  br label %omp.par.region
+
+omp.par.exit.split.exitStub:                      ; preds = %omp.par.outlined.exit
+  ret void
+
+omp.par.region:                                   ; preds = %omp.par.entry
+  br label %omp.par.pre_finalize
+
+omp.par.pre_finalize:                             ; preds = %omp.par.region
+  br label %omp.par.outlined.exit
+
+omp.par.outlined.exit:                            ; preds = %omp.par.pre_finalize
+  br label %omp.par.exit.split.exitStub
+}
+
+; Function Attrs: nounwind
+declare !callback !2 void @__kmpc_fork_call(%struct.ident_t*, i32, void (i32*, i32*, ...)*, ...) #2
+
+!2 = !{!3}
+!3 = !{i64 2, i64 -1, i64 -1, i1 true}