AbstractCallSite -- A unified interface for (in)direct and callback calls

  An abstract call site is a wrapper that allows to treat direct,
  indirect, and callback calls the same. If an abstract call site
  represents a direct or indirect call site it behaves like a stripped
  down version of a normal call site object. The abstract call site can
  also represent a callback call, thus the fact that the initially
  called function (=broker) may invoke a third one (=callback callee).
  In this case, the abstract call side hides the middle man, hence the
  broker function. The result is a representation of the callback call,
  inside the broker, but in the context of the original instruction that
  invoked the broker.

  Again, there are up to three functions involved when we talk about
  callback call sites. The caller (1), which invokes the broker
  function. The broker function (2), that may or may not invoke the
  callback callee. And finally the callback callee (3), which is the
  target of the callback call.

  The abstract call site will handle the mapping from parameters to
  arguments depending on the semantic of the broker function. However,
  it is important to note that the mapping is often partial. Thus, some
  arguments of the call/invoke instruction are mapped to parameters of
  the callee while others are not. At the same time, arguments of the
  callback callee might be unknown, thus "null" if queried.

  This patch introduces also !callback metadata which describe how a
  callback broker maps from parameters to arguments. This metadata is
  directly created by clang for known broker functions, provided through
  source code attributes by the user, or later deduced by analyses.

For motivation and additional information please see the corresponding
talk (slides/video)
  https://llvm.org/devmtg/2018-10/talk-abstracts.html#talk20
as well as the LCPC paper
  http://compilers.cs.uni-saarland.de/people/doerfert/par_opt_lcpc18.pdf

Differential Revision: https://reviews.llvm.org/D54498

llvm-svn: 351627

4 files changed, 181 insertions, 0 deletions

diff --git a/llvm/lib/IR/AbstractCallSite.cpp b/llvm/lib/IR/AbstractCallSite.cpp
new file mode 100644
index 00000000000..6ad2df85169
--- /dev/null
+++ b/llvm/lib/IR/AbstractCallSite.cpp
@@ -0,0 +1,135 @@
+//===-- AbstractCallSite.cpp - Implementation of abstract call sites ------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements abstract call sites which unify the interface for
+// direct, indirect, and callback call sites.
+//
+// For more information see:
+// https://llvm.org/devmtg/2018-10/talk-abstracts.html#talk20
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringSwitch.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "abstract-call-sites"
+
+STATISTIC(NumCallbackCallSites, "Number of callback call sites created");
+STATISTIC(NumDirectAbstractCallSites,
+          "Number of direct abstract call sites created");
+STATISTIC(NumInvalidAbstractCallSitesUnknownUse,
+          "Number of invalid abstract call sites created (unknown use)");
+STATISTIC(NumInvalidAbstractCallSitesUnknownCallee,
+          "Number of invalid abstract call sites created (unknown callee)");
+STATISTIC(NumInvalidAbstractCallSitesNoCallback,
+          "Number of invalid abstract call sites created (no callback)");
+
+/// Create an abstract call site from a use.
+AbstractCallSite::AbstractCallSite(const Use *U) : CS(U->getUser()) {
+
+  // First handle unknown users.
+  if (!CS) {
+
+    // If the use is actually in a constant cast expression which itself
+    // has only one use, we look through the constant cast expression.
+    // This happens by updating the use @p U to the use of the constant
+    // cast expression and afterwards re-initializing CS accordingly.
+    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U->getUser()))
+      if (CE->getNumUses() == 1 && CE->isCast()) {
+        U = &*CE->use_begin();
+        CS = CallSite(U->getUser());
+      }
+
+    if (!CS) {
+      NumInvalidAbstractCallSitesUnknownUse++;
+      return;
+    }
+  }
+
+  // Then handle direct or indirect calls. Thus, if U is the callee of the
+  // call site CS it is not a callback and we are done.
+  if (CS.isCallee(U)) {
+    NumDirectAbstractCallSites++;
+    return;
+  }
+
+  // If we cannot identify the broker function we cannot create a callback and
+  // invalidate the abstract call site.
+  Function *Callee = CS.getCalledFunction();
+  if (!Callee) {
+    NumInvalidAbstractCallSitesUnknownCallee++;
+    CS = CallSite();
+    return;
+  }
+
+  MDNode *CallbackMD = Callee->getMetadata(LLVMContext::MD_callback);
+  if (!CallbackMD) {
+    NumInvalidAbstractCallSitesNoCallback++;
+    CS = CallSite();
+    return;
+  }
+
+  unsigned UseIdx = CS.getArgumentNo(U);
+  MDNode *CallbackEncMD = nullptr;
+  for (const MDOperand &Op : CallbackMD->operands()) {
+    MDNode *OpMD = cast<MDNode>(Op.get());
+    auto *CBCalleeIdxAsCM = cast<ConstantAsMetadata>(OpMD->getOperand(0));
+    uint64_t CBCalleeIdx =
+        cast<ConstantInt>(CBCalleeIdxAsCM->getValue())->getZExtValue();
+    if (CBCalleeIdx != UseIdx)
+      continue;
+    CallbackEncMD = OpMD;
+    break;
+  }
+
+  if (!CallbackEncMD) {
+    NumInvalidAbstractCallSitesNoCallback++;
+    CS = CallSite();
+    return;
+  }
+
+  NumCallbackCallSites++;
+
+  assert(CallbackEncMD->getNumOperands() >= 2 && "Incomplete !callback metadata");
+
+  unsigned NumCallOperands = CS.getNumArgOperands();
+  // Skip the var-arg flag at the end when reading the metadata.
+  for (unsigned u = 0, e = CallbackEncMD->getNumOperands() - 1; u < e; u++) {
+    Metadata *OpAsM = CallbackEncMD->getOperand(u).get();
+    auto *OpAsCM = cast<ConstantAsMetadata>(OpAsM);
+    assert(OpAsCM->getType()->isIntegerTy(64) &&
+           "Malformed !callback metadata");
+
+    int64_t Idx = cast<ConstantInt>(OpAsCM->getValue())->getSExtValue();
+    assert(-1 <= Idx && Idx <= NumCallOperands &&
+           "Out-of-bounds !callback metadata index");
+
+    CI.ParameterEncoding.push_back(Idx);
+  }
+
+  if (!Callee->isVarArg())
+    return;
+
+  Metadata *VarArgFlagAsM =
+      CallbackEncMD->getOperand(CallbackEncMD->getNumOperands() - 1).get();
+  auto *VarArgFlagAsCM = cast<ConstantAsMetadata>(VarArgFlagAsM);
+  assert(VarArgFlagAsCM->getType()->isIntegerTy(1) &&
+         "Malformed !callback metadata var-arg flag");
+
+  if (VarArgFlagAsCM->getValue()->isNullValue())
+    return;
+
+  // Add all variadic arguments at the end.
+  for (unsigned u = Callee->arg_size(); u < NumCallOperands; u++)
+    CI.ParameterEncoding.push_back(u);
+}
diff --git a/llvm/lib/IR/CMakeLists.txt b/llvm/lib/IR/CMakeLists.txt
index 2586f987289..e52da6182c4 100644
--- a/llvm/lib/IR/CMakeLists.txt
+++ b/llvm/lib/IR/CMakeLists.txt
@@ -3,6 +3,7 @@ tablegen(LLVM AttributesCompatFunc.inc -gen-attrs)
 add_public_tablegen_target(AttributeCompatFuncTableGen)
 
 add_llvm_library(LLVMCore
+  AbstractCallSite.cpp
   AsmWriter.cpp
   Attributes.cpp
   AutoUpgrade.cpp
diff --git a/llvm/lib/IR/LLVMContext.cpp b/llvm/lib/IR/LLVMContext.cpp
index 944d8265151..5c4f0de33b1 100644
--- a/llvm/lib/IR/LLVMContext.cpp
+++ b/llvm/lib/IR/LLVMContext.cpp
@@ -62,6 +62,7 @@ LLVMContext::LLVMContext() : pImpl(new LLVMContextImpl(*this)) {
     {MD_callees, "callees"},
     {MD_irr_loop, "irr_loop"},
     {MD_access_group, "llvm.access.group"},
+    {MD_callback, "callback"},
   };
 
   for (auto &MDKind : MDKinds) {
diff --git a/llvm/lib/IR/MDBuilder.cpp b/llvm/lib/IR/MDBuilder.cpp
index 3fa541f1b53..3b5f2fec971 100644
--- a/llvm/lib/IR/MDBuilder.cpp
+++ b/llvm/lib/IR/MDBuilder.cpp
@@ -107,6 +107,50 @@ MDNode *MDBuilder::createCallees(ArrayRef<Function *> Callees) {
   return MDNode::get(Context, Ops);
 }
 
+MDNode *MDBuilder::createCallbackEncoding(unsigned CalleeArgNo,
+                                          ArrayRef<int> Arguments,
+                                          bool VarArgArePassed) {
+  SmallVector<Metadata *, 4> Ops;
+
+  Type *Int64 = Type::getInt64Ty(Context);
+  Ops.push_back(createConstant(ConstantInt::get(Int64, CalleeArgNo)));
+
+  for (int ArgNo : Arguments)
+    Ops.push_back(createConstant(ConstantInt::get(Int64, ArgNo, true)));
+
+  Type *Int1 = Type::getInt1Ty(Context);
+  Ops.push_back(createConstant(ConstantInt::get(Int1, VarArgArePassed)));
+
+  return MDNode::get(Context, Ops);
+}
+
+MDNode *MDBuilder::mergeCallbackEncodings(MDNode *ExistingCallbacks,
+                                          MDNode *NewCB) {
+  if (!ExistingCallbacks)
+    return MDNode::get(Context, {NewCB});
+
+  auto *NewCBCalleeIdxAsCM = cast<ConstantAsMetadata>(NewCB->getOperand(0));
+  uint64_t NewCBCalleeIdx =
+      cast<ConstantInt>(NewCBCalleeIdxAsCM->getValue())->getZExtValue();
+
+  SmallVector<Metadata *, 4> Ops;
+  unsigned NumExistingOps = ExistingCallbacks->getNumOperands();
+  Ops.resize(NumExistingOps + 1);
+
+  for (unsigned u = 0; u < NumExistingOps; u++) {
+    Ops[u] = ExistingCallbacks->getOperand(u);
+
+    auto *OldCBCalleeIdxAsCM = cast<ConstantAsMetadata>(Ops[u]);
+    uint64_t OldCBCalleeIdx =
+      cast<ConstantInt>(OldCBCalleeIdxAsCM->getValue())->getZExtValue();
+    assert(NewCBCalleeIdx != OldCBCalleeIdx &&
+           "Cannot map a callback callee index twice!");
+  }
+
+  Ops[NumExistingOps] = NewCB;
+  return MDNode::get(Context, Ops);
+}
+
 MDNode *MDBuilder::createAnonymousAARoot(StringRef Name, MDNode *Extra) {
   // To ensure uniqueness the root node is self-referential.
   auto Dummy = MDNode::getTemporary(Context, None);