[FunctionAttrs] Introduce transitive call sites to represent callbacks

[jdoerfert]

Summary

This patch adds transitive call sites that represent a (potential) call
made by the callee of a direct call site. Thus, if assume we have three
functions that can call each other:

foo --> bar --> baz

A transitive call site does now represent a call of baz in bar,
with regards to the values passed to bar when it is called in foo.

The reason transitive call sites are useful is because the code of the
"broker function", in the example above bar, might not be available.
However, if we know the function, or if recognized callbacks when we
analyzed its code at some earlier point, we can now make a connection
between the caller, foo in the above example, and the transitively
called value, here baz.

The first "real" use case for this extensions are outlined functions
passed to OpenMP runtime calls. Providing proper annotations for these
(see also D50125) has already proven to have a significant performance
impact [1,2]. However, there are also other kinds of callbacks which
often heavily restrict the set of applied optimizations.

To show how transitive call sites can be used, we added logic that can
deduce parameter attributes for call sites to broker functions. Though,
in this initial version we simply assume that a function with the
callback annotation will only "pass through" all arguments that are
referenced by the annotation. Thus, these arguments are not inspected,
nor captured by the broker function. As this might be too restrictive
for custom callbacks, we should look into a "passthrough" attribute for
arguments or some other encoding that allows us to match parameter to
arguments.

[1] http://compilers.cs.uni-saarland.de/people/doerfert/par_opt18.pdf
[2] https://llvm.org/devmtg/2018-04/talks.html#Talk_1

[jdoerfert]

Abstract call sites are in and the Attributor can do IPO based on them.

include/llvm/IR/CallSite.h

public:
   ImmutableCallSite() = default;
   ImmutableCallSite(const CallInst *CI) : CallSiteBase(CI) {}
   ImmutableCallSite(const InvokeInst *II) : CallSiteBase(II) {}
   explicit ImmutableCallSite(const Instruction *II) : CallSiteBase(II) {}
   explicit ImmutableCallSite(const Value *V) : CallSiteBase(V) {}
   ImmutableCallSite(CallSite CS) : CallSiteBase(CS.getInstruction()) {}
 };
 
+/// Given an ordinary call site that describes how and when one function
+/// invokes another. An associated transitive call site then describes how the
+/// called function may invoked a third one, with regards to context of the
+/// original call site. Thus, there are up to three functions involved when we
+/// talk about transitive call sites. The caller (1), which invokes the broker
+/// function. The broker function (2), that may or may not invoke the callee.
+/// And finally the callee (3), which is the target of the indirect call.
+class TransitiveCallSite {
+public:
+  using IndexTy = signed char;
+
+  CallSite getInitialCallSite() const { return CS; }
+
+  IndexTy getCallerParameterNoForArgumentNo(unsigned ArgNo) const {
+    return ArgumentForwardingIndices[ArgNo];
+  }
+
+  IndexTy getCallerParameterNoForArgument(Argument &Arg) const {
+    return getCallerParameterNoForArgumentNo(Arg.getArgNo());
+  }
+
+  Value *getCallerValueForArgumentNo(unsigned ArgNo) const {
+    IndexTy Idx = getCallerParameterNoForArgumentNo(ArgNo);
+    return Idx < 0 ? nullptr : CS.getArgument(Idx);
+  }
+
+  Value *getCallerValueForArgument(Argument &Arg) const {
+    return getCallerValueForArgumentNo(Arg.getArgNo());
+  }
+
+  /// Return the pointer to function that is being called.
+  Value *getCalledValue() const {
+    return CallTarget;
+  }
+
+  /// Return the function being called transitively or null if it is unknown.
+  Function *getCalledFunction() const {
+    return dyn_cast<Function>(getCalledValue()->stripPointerCasts());
+  }
+
+  /// Return the broker function that issues this transitive call.
+  Function *getBrokerFunction() const {
+    return CS.getCalledFunction();
+  }
+
+  /// Return the caller function that calls the broker which calls the callee.
+  Function *getCallerFunction() const {
+    return CS.getCaller();
+  }
+
+  unsigned getNumArgOperands() const {
+    return ArgumentForwardingIndices.size();
+  }
+
+  static bool containsTransitiveCallSites(const Function &F);
+
+  static void getTransitiveCallSites(CallSite CS,
+                              SmallVectorImpl<TransitiveCallSite> &TCSs);
+
+  static void getTransitiveCallSites(Function &BrokerFn,
+                              SmallVectorImpl<TransitiveCallSite> &TCSs);
+
+private:
+
+  /// The target of this transitive call.
+  Value *CallTarget;
+
+  /// The initial call site that might trigger this transitive call.
+  CallSite CS;
+
+  /// A vector to describe how arguments of the initial call site are forwarded.
+  ///
+  /// For each argument of the call target there should be one element in this
+  /// vector. If it is < 0, we do not know the value that is forwarded to the
+  /// call target. If it is >= 0, the argument of the initial call site at the
+  /// described position is forwarded to the call target.
+  SmallVector<IndexTy, 8> ArgumentForwardingIndices;
+
+  /// Simple initializer.
+  TransitiveCallSite(Value *CallTarget, CallSite CS,
+                     ArrayRef<IndexTy> ArgumentForwardingIndices)
+      : CallTarget(CallTarget), CS(CS),
+        ArgumentForwardingIndices(ArgumentForwardingIndices.begin(),
+                                  ArgumentForwardingIndices.end()) {}
+
+};
+
 } // end namespace llvm
 
 #endif // LLVM_IR_CALLSITE_H

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   CallGraph.cpp
   CallGraphSCCPass.cpp
   CallPrinter.cpp
   CaptureTracking.cpp
   CmpInstAnalysis.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
+  CallbackInfo.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DominanceFrontier.cpp
   EHPersonalities.cpp
   GlobalsModRef.cpp

lib/Analysis/CallbackInfo.cpp

+//===- CallbackInfo.cpp - Function call callback info interface -----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/CallSite.h"
+
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
+
+#include <limits>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "callback-info"
+
+STATISTIC(NumCallSitesToCallbackFn,
+          "# analyzed call sites to callback functions");
+
+static const std::string CallbacksMetadataID = "callback";
+
+//===----------------------------------------------------------------------===//
+// TransitiveCallSite implementation
+//
+
+/// Extract and return the offset encoded by @p M after verification wrt. @p CS.
+static TransitiveCallSite::IndexTy getOffsetForMetadataAtCallSite(Metadata *M,
+                                                                  CallSite CS) {
+  auto *CAM = dyn_cast<ConstantAsMetadata>(M);
+  assert(CAM && "Malformed callback encoding: Expected constant value!");
+
+  assert(CAM->getType()->isIntegerTy(8) &&
+         "Malformed callback encoding: Expected i8 type in callback metadata");
+
+  auto SExtCV = cast<ConstantInt>(CAM->getValue())->getSExtValue();
+  assert(SExtCV >= -1 &&
+         "Malformed callback encoding: Unexpected argument offset!");
+
+  auto MaxIndex = std::numeric_limits<TransitiveCallSite::IndexTy>::max();
+  assert(((SExtCV == (decltype(SExtCV))MaxIndex) ||
+          (SExtCV < (decltype(SExtCV))MaxIndex &&
+           SExtCV < (decltype(SExtCV))CS.getNumArgOperands())) &&
+         "Malformed callback encoding: Argument offset too large!");
+
+  return SExtCV;
+}
+
+/// Return the value identified by @p M in the context of the call site @p CS.
+static Value *getValueForMetadataAtCallSite(Metadata *M, CallSite CS) {
+  TransitiveCallSite::IndexTy Offset = getOffsetForMetadataAtCallSite(M, CS);
+
+  if (Offset == -1)
+    return nullptr;
+
+  assert(Offset >= 0);
+  return CS.getArgOperand(Offset);
+}
+
+bool TransitiveCallSite::containsTransitiveCallSites(const Function &F) {
+  return F.hasMetadata(CallbacksMetadataID);
+}
+
+static bool isVarArgsBegin(TransitiveCallSite::IndexTy Offset) {
+  auto MaxOffset = std::numeric_limits<TransitiveCallSite::IndexTy>::max();
+  return Offset == MaxOffset;
+}
+
+void TransitiveCallSite::getTransitiveCallSites(
+    CallSite CS, SmallVectorImpl<TransitiveCallSite> &TCSs) {
+
+  // If the potential broker function is unknown, or it does not have
+  // the callback annotation, there is nothing to do.
+  Function *BrokerFn = CS.getCalledFunction();
+  if (!BrokerFn)
+    return;
+
+  MDNode *CallbacksMD = BrokerFn->getMetadata(CallbacksMetadataID);
+  if (!CallbacksMD)
+    return;
+
+  // Bookkeeping.
+  ++NumCallSitesToCallbackFn;
+
+  int NumCallbacks = CallbacksMD->getNumOperands();
+  for (int CallbackIdx = 0; CallbackIdx < NumCallbacks; CallbackIdx++) {
+    Metadata *CallbackM = CallbacksMD->getOperand(CallbackIdx);
+    assert(isa<MDNode>(CallbackM) &&
+           "Malformed callback encoding: Wrong metadata callback node!");
+
+    MDNode *CallbackMD = cast<MDNode>(CallbackM);
+    assert(CallbackMD->getNumOperands() > 0 &&
+           "Malformed callback encoding: Empty metadata callback node!");
+
+    Metadata *CalleeM = CallbackMD->getOperand(0);
+    Value *Callee = getValueForMetadataAtCallSite(CalleeM, CS);
+
+    int NumArgs = CallbackMD->getNumOperands() - 1;
+    SmallVector<TransitiveCallSite::IndexTy, 8> ArgumentForwardingIndices;
+    ArgumentForwardingIndices.resize(NumArgs);
+
+    int VarArgsInsertionIdx = -1;
+    for (int ArgIdx = 0; ArgIdx < NumArgs; ArgIdx++) {
+      Metadata *ArgM = CallbackMD->getOperand(ArgIdx + 1);
+      TransitiveCallSite::IndexTy Offset =
+          getOffsetForMetadataAtCallSite(ArgM, CS);
+      ArgumentForwardingIndices[ArgIdx] = Offset;
+
+      if (isVarArgsBegin(Offset)) {
+        assert(VarArgsInsertionIdx == -1 &&
+               "Malformed callback encoding: Multiple var-args uses in one "
+               "callback not supported!");
+        VarArgsInsertionIdx = ArgIdx;
+      }
+    }
+
+    // If we have a "var-args" broker function, it can forward a variable number
+    // of arguments. If it does, we will have set the VarArgsInsertionIdx
+    // variable to the offset at which these arguments have to be inserted into
+    // the transitive call site.
+    if (VarArgsInsertionIdx >= 0) {
+      assert(Callee && "Malformed callback encoding: Use of var-args requires "
+                       "a callee value!");
+
+      // Determine the callee function type as we need to know how many
+      // arguments the callee function actually has.
+      FunctionType *CalleeFnTy = nullptr;
+      if (Function *CalleeFn =
+              dyn_cast<Function>(Callee->stripPointerCasts()))
+        CalleeFnTy = CalleeFn->getFunctionType();
+      assert(CalleeFnTy && "Malformed callback encoding: Callee value does not "
+                           "have function type!");
+
+      int NumCalleeArgs = CalleeFnTy->getNumParams();
+      int NumVarArgs = NumCalleeArgs - NumArgs + 1;
+      assert(NumVarArgs >= 0 && "Malformed callback encoding: Too many fixed "
+                                "arguments for variadic transitive call site.");
+      ArgumentForwardingIndices.resize(NumCalleeArgs);
+
+      // Overwrite the "var args insertion point" with the first variadic
+      // argument position. Then continue with the remaining variadic ones but
+      // we have to move existing argument positions behind the last variadic
+      // one.
+      ArgumentForwardingIndices[VarArgsInsertionIdx] = BrokerFn->arg_size();
+
+      for (int VarArgIdx = 1; VarArgIdx < NumVarArgs; VarArgIdx++) {
+        // Move the argument that currently occupies the next slot, if any.
+        // Since we want to put the next variadic argument in the next slot,
+        // the current occupant has to be moved to the next free spot after the
+        // variadic arguments.
+        if (NumArgs + VarArgIdx < NumCalleeArgs) {
+          ArgumentForwardingIndices[NumArgs + VarArgIdx] =
+              ArgumentForwardingIndices[VarArgsInsertionIdx + VarArgIdx];
+        }
+
+        // Then insert the index of the next variadic argument.
+        ArgumentForwardingIndices[VarArgsInsertionIdx + VarArgIdx] =
+            BrokerFn->arg_size() + VarArgIdx;
+      }
+    }
+
+    // Create the transitive call site and add it to the result.
+    TCSs.push_back(
+        std::move(TransitiveCallSite(Callee, CS, ArgumentForwardingIndices)));
+
+    LLVM_DEBUG({
+      auto &TCS = TCSs.back();
+      dbgs() << "Transitive call site created:\n\t CS: " << *CS.getInstruction()
+             << "\n";
+      dbgs() << "\t Callee: " << (Callee ? Callee->getName() : "n/a") << "\n";
+      for (int u = 0; u < (int)TCS.getNumArgOperands(); u++) {
+        Value *V = TCS.getCallerValueForArgumentNo(u);
+        dbgs() << "\t - " << u << " [Idx: " << (int)ArgumentForwardingIndices[u]
+               << "] [V: " << (V ? V->getName() : "n/a") << "]\n";
+      }
+    });
+  }
+}
+
+void TransitiveCallSite::getTransitiveCallSites(Function &BrokerFn,
+                                  SmallVectorImpl<TransitiveCallSite> &TCSs) {
+  for (const auto &U : BrokerFn.uses()) {
+    CallSite CS(U.getUser());
+    if (CS && CS.isCallee(&U))
+      getTransitiveCallSites(CS, TCSs);
+  }
+}

lib/Transforms/IPO/FunctionAttrs.cpp

 
 using namespace llvm;
 
 #define DEBUG_TYPE "functionattrs"
 
 STATISTIC(NumReadNone, "Number of functions marked readnone");
 STATISTIC(NumReadOnly, "Number of functions marked readonly");
 STATISTIC(NumWriteOnly, "Number of functions marked writeonly");
-STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
-STATISTIC(NumReturned, "Number of arguments marked returned");
+STATISTIC(NumNoCaptureArg, "Number of arguments marked nocapture");
+STATISTIC(NumReturnedArg, "Number of arguments marked returned");
 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
+STATISTIC(NumWriteOnlyArg, "Number of arguments marked writeonly");
 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
 STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
 
 // FIXME: This is disabled by default to avoid exposing security vulnerabilities
 // in C/C++ code compiled by clang:
 // http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html
for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
     if (I->mayWriteToMemory())
       // Writes memory, remember that.
       WritesMemory = true;
 
     // If this instruction may read memory, remember that.
     ReadsMemory |= I->mayReadFromMemory();
   }
 
-  if (WritesMemory) { 
+  if (WritesMemory) {
     if (!ReadsMemory)
       return MAK_WriteOnly;
     else
       return MAK_MayWrite;
   }
 
   return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
 }
while (!Worklist.empty()) {
     default:
       return Attribute::None;
     }
   }
 
   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
 }
 
+/// Deduce attributes for passthrough arguments based on information for
+/// transitive call sites invoked by functions in this SCC.
+static bool deriveCallSiteAttrsForPassthroughArgs(const SCCNodeSet &SCCNodes) {
+  bool Changed = false;
+
+  for (Function *F : SCCNodes) {
+
+    // We scan each function in the SCC for direct call sites and then collect
+    // all transitive ones that are associated with the directly called
+    // function.
+    SmallVector<TransitiveCallSite, 8> TCSs;
+    for (Instruction &I : instructions(F)) {
+      CallSite CS(&I);
+      if (CS)
+        TransitiveCallSite::getTransitiveCallSites(CS, TCSs);
+    }
+
+    // Since each parameter at a call site in the currently analyzed function
+    // might be mapped to multiple arguments in the transitively called
+    // function, we first collect all arguments a parameter is mapped to
+    // before we derive attributes from them.
+    DenseMap<Instruction *, SmallVector<SmallPtrSet<Argument *, 1>, 4>>
+        ParameterArgumentsMap;
+
+    // We then iterate over all transitive call sites.
+    for (TransitiveCallSite &TCS : TCSs) {
+
+      // Sanity check.
+      assert(TCS.getCallerFunction() == F);
+
+      // If the called function is not known or variable, we cannot derive
+      // information from its arguments.
+      Function *CalledFn = TCS.getCalledFunction();
+      if (!CalledFn)
+        continue;
+
+      // Sanity check.
+      assert(CalledFn->getFunctionType()->getNumParams() ==
+                 TCS.getNumArgOperands() &&
+             "The number of arguments and parameters did not match for a "
+             "transitive call site!");
+
+      CallSite CS = TCS.getInitialCallSite();
+      auto &ParameterArguments = ParameterArgumentsMap[CS.getInstruction()];
+      ParameterArguments.resize(CS.getNumArgOperands());
+
+      // Sanity check.
+      assert(CS.getCaller() == F);
+
+      // We want to propagate attributes from pointer arguments of the
+      // transitively called function to the parameters at the currently
+      // analyzed call site. To this end, we check for each pointer argument if
+      // we know the corresponding parameter at the current call site.
+      for (Argument &Arg : CalledFn->args()) {
+        if (!Arg.getType()->isPointerTy())
+          continue;
+
+        // TODO: For now, we know that all transitive call sites we can
+        //       identify only pass their arguments through to the final
+        //       callee. However, we might want to add a "passthrough"
+        //       argument to denote this fact.
+        //
+        // if (!Arg.hasAttribute(Attribute::Passthrough))
+        //   continue;
+
+        // If we do not know the origin of an argument the associated parameter
+        // number will be -1.
+        int ParamNo = TCS.getCallerParameterNoForArgument(Arg);
+        if (ParamNo < 0)
+          continue;
+
+        // Sanity check.
+        assert(ParamNo < (int)CS.getNumArgOperands() &&
+               "Parameter number in transitive call site too large.");
+        ParameterArguments[ParamNo].insert(&Arg);
+      }
+    }
+
+    // Once the parameter argument mappings per call site have been collected,
+    // we can use them to derive attributes for the respective call site.
+    for (auto &It : ParameterArgumentsMap) {
+      CallSite CS (It.first);
+      auto &ParameterArguments = It.second;
+
+      for (unsigned ParamNo = 0; ParamNo < CS.getNumArgOperands(); ParamNo++) {
+
+        // Check if this parameter is mapped to any arguments at all, if not
+        // there is nothing to propagate.
+        auto &Arguments = ParameterArguments[ParamNo];
+        if (Arguments.empty())
+          continue;
+
+        using AttrGroupTy = SmallVector<Attribute::AttrKind, 2>;
+        AttrGroupTy AttrGroups[] = {
+            AttrGroupTy({Attribute::ReadNone}),
+            AttrGroupTy({Attribute::ReadOnly, Attribute::ReadNone}),
+            AttrGroupTy({Attribute::WriteOnly, Attribute::ReadNone}),
+            AttrGroupTy({Attribute::NoCapture})};
+
+        for (auto AttrGroup : AttrGroups) {
+          // If the parameter is mapped to arguments, we have to ensure that all
+          // of them carry an attribute that implies the currently derived one
+          // before we propagate it to the parameter.
+          if (!std::all_of(Arguments.begin(), Arguments.end(),
+                           [=](Argument *Arg) {
+                             for (auto Attr : AttrGroup)
+                               if (Arg->hasAttribute(Attr))
+                                 return true;
+                             return false;
+                           }))
+            continue;
+
+          // If the attribute group contains multiple attributes, all that
+          // follow the first one (=leader) imply the leader attribute. Thus, if
+          // the attribute, or any of the trailing stronger ones, is already
+          // set, we do not need to add a new one.
+          if (std::any_of(AttrGroup.begin(), AttrGroup.end(),
+                          [&](Attribute::AttrKind Attr) {
+                            return CS.paramHasAttr(ParamNo, Attr);
+                          }))
+            continue;
+
+          // Annotate the parameter and note the change.
+          auto AttrGroupLeader = AttrGroup.front();
+          CS.addParamAttr(ParamNo, AttrGroupLeader);
+          Changed = true;
+
+          // Bookkeeping.
+          switch (AttrGroupLeader) {
+          case Attribute::ReadNone:
+            ++NumReadNoneArg;
+            break;
+          case Attribute::ReadOnly:
+            ++NumReadOnlyArg;
+            break;
+          case Attribute::WriteOnly:
+            ++NumWriteOnlyArg;
+            break;
+          case Attribute::NoCapture:
+            ++NumNoCaptureArg;
+            break;
+          default:
+            break;
+          }
+        }
+      }
+    }
+  }
+
+  return Changed;
+}
+
 /// Deduce returned attributes for the SCC.
 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
   bool Changed = false;
 
   // Check each function in turn, determining if an argument is always returned.
   for (Function *F : SCCNodes) {
     // We can infer and propagate function attributes only when we know that the
     // definition we'll get at link time is *exactly* the definition we see now.
auto FindRetArg = [&]() -> Value * {
         }
 
       return RetArg;
     };
 
     if (Value *RetArg = FindRetArg()) {
       auto *A = cast<Argument>(RetArg);
       A->addAttr(Attribute::Returned);
-      ++NumReturned;
+      ++NumReturnedArg;
       Changed = true;
     }
   }
 
   return Changed;
 }
 
 /// If a callsite has arguments that are also arguments to the parent function,
for (Function *F : SCCNodes) {
     // Functions that are readonly (or readnone) and nounwind and don't return
     // a value can't capture arguments. Don't analyze them.
     if (F->onlyReadsMemory() && F->doesNotThrow() &&
         F->getReturnType()->isVoidTy()) {
       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
            ++A) {
         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
           A->addAttr(Attribute::NoCapture);
-          ++NumNoCapture;
+          ++NumNoCaptureArg;
           Changed = true;
         }
       }
       continue;
     }
 
     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
          ++A) {
       if (!A->getType()->isPointerTy())
         continue;
       bool HasNonLocalUses = false;
       if (!A->hasNoCaptureAttr()) {
         ArgumentUsesTracker Tracker(SCCNodes);
         PointerMayBeCaptured(&*A, &Tracker);
         if (!Tracker.Captured) {
           if (Tracker.Uses.empty()) {
             // If it's trivially not captured, mark it nocapture now.
             A->addAttr(Attribute::NoCapture);
-            ++NumNoCapture;
+            ++NumNoCaptureArg;
             Changed = true;
           } else {
             // If it's not trivially captured and not trivially not captured,
             // then it must be calling into another function in our SCC. Save
             // its particulars for Argument-SCC analysis later.
             ArgumentGraphNode *Node = AG[&*A];
             for (Argument *Use : Tracker.Uses) {
               Node->Uses.push_back(AG[Use]);
if (ArgumentSCC.size() == 1) {
       if (!ArgumentSCC[0]->Definition)
         continue; // synthetic root node
 
       // eg. "void f(int* x) { if (...) f(x); }"
       if (ArgumentSCC[0]->Uses.size() == 1 &&
           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
         Argument *A = ArgumentSCC[0]->Definition;
         A->addAttr(Attribute::NoCapture);
-        ++NumNoCapture;
+        ++NumNoCaptureArg;
         Changed = true;
       }
       continue;
     }
 
     bool SCCCaptured = false;
     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
          I != E && !SCCCaptured; ++I) {
for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
       }
     }
     if (SCCCaptured)
       continue;
 
     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
       Argument *A = ArgumentSCC[i]->Definition;
       A->addAttr(Attribute::NoCapture);
-      ++NumNoCapture;
+      ++NumNoCaptureArg;
       Changed = true;
     }
 
     // We also want to compute readonly/readnone. With a small number of false
     // negatives, we can assume that any pointer which is captured isn't going
     // to be provably readonly or readnone, since by definition we can't
     // analyze all uses of a captured pointer.
     //

 static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
                                    bool HasUnknownCall) {
   bool Changed = false;
 
   // Bail if the SCC only contains optnone functions.
   if (SCCNodes.empty())
     return Changed;
 
+  // Determine if the module contains transitive call sites.
+  //
+  // TODO: This should be placed in some kind of initialization of the passes
+  //       that is only evaluated once for the whole module.
+  bool ModuleHasTransitiveCalls = false;
+  Module *M = SCCNodes.front()->getParent();
+  for (const Function &F : M->functions())
+    if (TransitiveCallSite::containsTransitiveCallSites(F)) {
+      ModuleHasTransitiveCalls = true;
+      break;
+    }
+
+  if (ModuleHasTransitiveCalls)
+    Changed |= deriveCallSiteAttrsForPassthroughArgs(SCCNodes);
+
   Changed |= addArgumentReturnedAttrs(SCCNodes);
   Changed |= addReadAttrs(SCCNodes, AARGetter);
   Changed |= addArgumentAttrs(SCCNodes);
 
   // If we have no external nodes participating in the SCC, we can deduce some
   // more precise attributes as well.
   if (!HasUnknownCall) {
     Changed |= addNoAliasAttrs(SCCNodes);

test/Transforms/FunctionAttrs/transitive_call.ll

+; RUN: opt -functionattrs -S < %s | FileCheck %s
+;
+; Verify that we propagate callee information to the caller if the calle is
+; invoked transitively by a broker function function. We encode such transitive
+; calls with the "callback" metadata at the broker function (see EOF).
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; int callee(int *R, int *W, int *RW, float *N) {
+;   *W = *R;
+;   (*RW)++;
+;   return N ? 0 : 1;
+; }
+;
+; int broker(int *, int *, int(*)(int*, int*, int *, float*), float*);
+;
+; int caller(int *READ_READ_WRITE, int *WRITE, float *NONE) {
+;   return broker(READ_READ_WRITE, WRITE, callee, NONE);
+; }
+
+; Verify the argument attributes in the callee:
+;
+; CHECK: @callee(i32* nocapture readonly %R, i32* nocapture writeonly %W, i32* nocapture %RW, float* readnone %N) {
+;
+; TODO: Once we automatically derive writeonly (D48387) we should remove it below!
+;
+define dso_local i32 @callee(i32* %R, i32* writeonly %W, i32* %RW, float* %N) {
+entry:
+  %0 = load i32, i32* %R, align 4
+  store i32 %0, i32* %W, align 4
+  %1 = load i32, i32* %RW, align 4
+  %inc = add nsw i32 %1, 1
+  store i32 %inc, i32* %RW, align 4
+  %tobool = icmp eq float* %N, null
+  %cond = zext i1 %tobool to i32
+  ret i32 %cond
+}
+
+define dso_local i32 @caller(i32* %READ_READ_WRITE, i32* %WRITE, float* %NONE) {
+entry:
+
+; Verify we derive and propagate nocapture attributes for all passthrough pointer arguments (READ_READ_WRITE, WRITE, NONE).
+; WRITE and NONE should additionally have writeonly and respectively readnone annotations. READ_READ_WRITE should not have
+; a readonly attribute as it is passed twice to the callee and only once it is marked readonly.
+;
+; CHECK: %call = call i32 @broker(i32* nocapture %READ_READ_WRITE, i32* nocapture writeonly %WRITE, i32 (i32*, i32*, i32*, float*)* nonnull @callee, float* readnone %NONE)
+  %call = call i32 @broker(i32* %READ_READ_WRITE, i32* %WRITE, i32 (i32*, i32*, i32*, float*)* nonnull @callee, float* %NONE)
+
+  ret i32 %call
+}
+
+declare !callback !0 dso_local i32 @broker(i32*, i32*, i32 (i32*, i32*, i32*, float*)*, float*)
+
+; The callback metadata points to a list of callbacks. In the following there is only one.
+!0 = !{ !1 }
+
+; Each callback first identifies the called value, here argument 2 of the broker.
+; Then, the arguments to the called value are identified. In this example we assume
+; that @broker will invoke @callee like this (wrt. to the call site in @caller):
+;   callee(READ_READ_WRITE, WRITE, READ_READ_WRITE, NONE);
+;
+!1 = !{ i8 2, i8 0, i8 1, i8 0, i8 3 }

test/Transforms/FunctionAttrs/transitive_var_arg_call.ll

+; RUN: opt -functionattrs -S < %s | FileCheck %s
+; RUN: opt -dse -S < %s | FileCheck %s -check-prefix=DSE_NO_FNATTR
+; RUN: opt -functionattrs -dse -S < %s | FileCheck %s -check-prefix=CHECK -check-prefix=DSE_FNATTR
+;
+; Verify that we propagate callee information to the caller if the calle is
+; invoked transitively by a broker function function. We encode such transitive
+; calls with the "callback" metadata at the broker function (see EOF).
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; TODO: We should actually be able to deduce the writeonly and nocapture attributes below.
+;
+define dso_local i32 @callee(i32* %R, i32* writeonly %W, i32* %RW, float* nocapture %N) {
+entry:
+  %0 = load i32, i32* %R, align 4
+  store i32 %0, i32* %W, align 4
+  %1 = load i32, i32* %RW, align 4
+  %inc = add nsw i32 %1, 1
+  store i32 %inc, i32* %RW, align 4
+  %tobool = icmp eq float* %N, null
+  %cond = zext i1 %tobool to i32
+  ret i32 %cond
+}
+
+; TODO: We should determine readonly for F1 in the declaration of caller1
+;
+; CHECK: define dso_local i32 @caller1(i32* nocapture %I1, float* nocapture %F1) {
+define dso_local i32 @caller1(i32* %I1, float* %F1) {
+entry:
+  %I2 = alloca i32
+
+; Since I2 is _not_ writeonly in the call, we should _not_ eliminate this store.
+;
+; DSE_NO_FNATTR: store
+; DSE_FNATTR:    store
+  store i32 0, i32* %I2, align 4
+
+; Verify that the parameter F1 is annotated as readonly. Since I2 is in fact
+; _not_ writeonly during broker call (see EOF for the encoded scenario),
+; _only_ the first use and not the second are annotated as such. To check
+; that this distinction (wrt. the situation in caller2) is taken seriously,
+; we also verify that the store prior to the call is not removed in this 
+; function but only in caller2 below.
+;
+; CHECK: %call = call i32 (i32*, i32 (i32*, ...)*, ...) @broker(i32* nocapture writeonly %I2, i32 (i32*, ...)* bitcast (i32 (i32*, i32*, i32*, float*)* @callee to i32 (i32*, ...)*), float* nocapture readonly %F1, i32* nocapture %I1, i32* nocapture %I2)
+  %call = call i32 (i32*, i32 (i32*, ...)*, ...) @broker(i32* %I2, i32 (i32*, ...)* bitcast (i32 (i32*, i32*, i32*, float*)* @callee to i32 (i32*, ...)*), float* %F1, i32* %I1, i32* %I2)
+
+; DSE_NO_FNATTR:  store
+; DSE_FNATTR-NOT: store
+  store i32 1, i32* %I2, align 4
+
+  ret i32 %call
+}
+
+; TODO: We should determine writeonly for I1 an readonly for F1 in the declaration of caller2
+;
+; CHECK: define dso_local i32 @caller2(i32* nocapture %I1, float* nocapture %F1) {
+define dso_local i32 @caller2(i32* %I1, float* %F1) {
+entry:
+  %I2 = alloca i32
+
+; Since I2 is writeonly in the call, we should eliminate this store.
+;
+; DSE_NO_FNATTR:  store
+; DSE_FNATTR-NOT: store
+  store i32 0, i32* %I2, align 4
+
+; Verify that the parameter F1 is annotated as readonly and I1 as writeonly.
+;
+; CHECK: %call = call i32 (i32*, i32 (i32*, ...)*, ...) @broker(i32* nocapture writeonly %I2, i32 (i32*, ...)* bitcast (i32 (i32*, i32*, i32*, float*)* @callee to i32 (i32*, ...)*), float* nocapture readonly %F1, i32* nocapture %I1, i32* nocapture %I1)
+  %call = call i32 (i32*, i32 (i32*, ...)*, ...) @broker(i32* %I2, i32 (i32*, ...)* bitcast (i32 (i32*, i32*, i32*, float*)* @callee to i32 (i32*, ...)*), float* %F1, i32* %I1, i32* %I1)
+
+; DSE_NO_FNATTR:  store
+; DSE_FNATTR-NOT: store
+  store i32 1, i32* %I2, align 4
+
+  ret i32 %call
+}
+
+declare !callback !0 dso_local i32 @broker(i32*, i32 (i32*, ...)*, ...)
+
+; The callback metadata points to a list of callbacks.
+; In the following list there are three, two that specify the
+; argument mapping and one that describes the passthrough of all
+; variadic arguments.
+!0 = !{ !1, !2, !3 }
+
+; Each callback first identifies the called value and then the arguments.
+;
+; In this example we assume that @broker will invoke @callee three times.
+; Wrt. to the call site in @caller1 this would look like:
+;
+;                                   r-o w-o n/a r-n  <-- argument attributes
+; 1)                         callee(I2, I2, I1, F1)
+; 2)                         callee(F1, I2, I2, I2)
+; 3)  callee(VAR_ARGS, I2) = callee(F1, I1, I2, I2)
+; ==> I1 -> n/a, I2 -> n/a, F1 -> r-o
+;
+; Wrt. to the call site in @caller2 this would look like:
+;
+;                                   r-o w-o n/a r-n  <-- argument attributes
+; 1)                         callee(I2, I1, I2, F1);
+; 2)                         callee(F1, I1, I2, I1);
+; 3)  callee(VAR_ARGS, II) = callee(F1, I2, I2, I1)
+; ==> I1 -> w-o, I2 -> n/a, F1 -> r-o
+;
+!1 = !{ i8 1, i8 4, i8 0, i8 3, i8 2 }
+!2 = !{ i8 1, i8 2, i8 0, i8 4, i8 0 }
+!3 = !{ i8 1, i8 127, i8 0 }