Add !callees metadata

[mssimpso]

Summary

This patch adds a new kind of metadata that indicates the possible callees of indirect calls.

[hfinkel]

I don't like the term "targets", in part because that term is generally used to refer to the target architecture. How about "callees"?

docs/LangRef.rst

4883

run-time -> runtime

4883

If `targets` metadata is attached to a call site, and any callee is not among the set of functions provided by the metadata, the behavior is undefined.

[mssimpso]

In D37354#859717, @hfinkel wrote:

I don't like the term "targets", in part because that term is generally used to refer to the target architecture. How about "callees"?

Yes, I like "callees" much better too. Thanks very much for the suggestions!

[mssimpso]

Addressed Hal's comments. Thanks!

[hfinkel]

docs/LangRef.rst

4883

You can remove this statement entirely: "It indicates a known set of functions that a call or invoke instruction could possibly target at runtime."

The next sentence says that same thing in a more precise way.

4886

You can remove this statement: "The compiler is free to optimize call sites under this assumption
(e.g., by performing indirect call promotion)."

The freedom for the compiler to optimize is implied by the preceding sentence. If you feel that stating an example optimization helps make the intent clearer, then I think that's fine. Maybe phrase this as:

The intent of this metadata is to facilitate optimizations such as indirect call promotion.

[mssimpso]

Addressed Hal's comments. Thanks again!

[hfinkel]

LGTM

docs/LangRef.rst

4884

indirect call promotion -> indirect-call promotion

docs/LangRef.rst

.. code-block:: llvm
 
       @a = external global i8, !absolute_symbol !0 ; Absolute symbol in range [0,256)
       @b = external global i8, !absolute_symbol !1 ; Absolute symbol in range [0,2^64)
 
     ...
     !0 = !{ i64 0, i64 256 }
     !1 = !{ i64 -1, i64 -1 }
 
+'``callees``' Metadata
+^^^^^^^^^^^^^^^^^^^^^^
+
+``callees`` metadata may be attached to indirect call sites. If ``callees``
+metadata is attached to a call site, and any callee is not among the set of
+functions provided by the metadata, the behavior is undefined. The intent of
+this metadata is to facilitate optimizations such as indirect call promotion.
+For example, in the code below, the call instruction may only target the
+``add`` or ``sub`` functions:
+
+.. code-block:: llvm
+
+      %result = call i64 %binop(i64 %x, i64 %y), !callees !0
+    ...
+    !0 = !{i64 (i64, i64)* @add, i64 (i64, i64)* @sub}
+
 '``unpredictable``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 ``unpredictable`` metadata may be attached to any branch or switch
 instruction. It can be used to express the unpredictability of control
 flow. Similar to the llvm.expect intrinsic, it may be used to alter
 optimizations related to compare and branch instructions. The metadata
 is treated as a boolean value; if it exists, it signals that the branch

include/llvm/IR/LLVMContext.h

enum {
     MD_unpredictable = 15,            // "unpredictable"
     MD_invariant_group = 16,          // "invariant.group"
     MD_align = 17,                    // "align"
     MD_loop = 18,                     // "llvm.loop"
     MD_type = 19,                     // "type"
     MD_section_prefix = 20,           // "section_prefix"
     MD_absolute_symbol = 21,          // "absolute_symbol"
     MD_associated = 22,               // "associated"
+    MD_callees = 23,                  // "callees"
   };
 
   /// Known operand bundle tag IDs, which always have the same value.  All
   /// operand bundle tags that LLVM has special knowledge of are listed here.
   /// Additionally, this scheme allows LLVM to efficiently check for specific
   /// operand bundle tags without comparing strings.
   enum {
     OB_deopt = 0,         // "deopt"

include/llvm/IR/MDBuilder.h

public:
 
   /// \brief Return metadata describing the range [Lo, Hi).
   MDNode *createRange(const APInt &Lo, const APInt &Hi);
 
   /// \brief Return metadata describing the range [Lo, Hi).
   MDNode *createRange(Constant *Lo, Constant *Hi);
 
   //===------------------------------------------------------------------===//
+  // Callees metadata.
+  //===------------------------------------------------------------------===//
+
+  /// \brief Return metadata indicating the possible callees of indirect calls.
+  MDNode *createCallees(ArrayRef<Function *> Callees);
+
+  //===------------------------------------------------------------------===//
   // AA metadata.
   //===------------------------------------------------------------------===//
 
 protected:
   /// \brief Return metadata appropriate for a AA root node (scope or TBAA).
   /// Each returned node is distinct from all other metadata and will never
   /// be identified (uniqued) with anything else.
   MDNode *createAnonymousAARoot(StringRef Name = StringRef(),

lib/IR/LLVMContext.cpp

std::pair<unsigned, StringRef> MDKinds[] = {
     {MD_unpredictable, "unpredictable"},
     {MD_invariant_group, "invariant.group"},
     {MD_align, "align"},
     {MD_loop, "llvm.loop"},
     {MD_type, "type"},
     {MD_section_prefix, "section_prefix"},
     {MD_absolute_symbol, "absolute_symbol"},
     {MD_associated, "associated"},
+    {MD_callees, "callees"},
   };
 
   for (auto &MDKind : MDKinds) {
     unsigned ID = getMDKindID(MDKind.second);
     assert(ID == MDKind.first && "metadata kind id drifted");
     (void)ID;
   }
 

lib/IR/MDBuilder.cpp

 //===---- llvm/MDBuilder.cpp - Builder for LLVM metadata ------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the MDBuilder class, which is used as a convenient way to
 // create LLVM metadata with a consistent and simplified interface.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
 #include "llvm/IR/Metadata.h"
 using namespace llvm;
 
 MDString *MDBuilder::createString(StringRef Str) {
   return MDString::get(Context, Str);
 }
 
 ConstantAsMetadata *MDBuilder::createConstant(Constant *C) {
MDNode *MDBuilder::createRange(Constant *Lo, Constant *Hi) {
   // If the range is everything then it is useless.
   if (Hi == Lo)
     return nullptr;
 
   // Return the range [Lo, Hi).
   return MDNode::get(Context, {createConstant(Lo), createConstant(Hi)});
 }
 
+MDNode *MDBuilder::createCallees(ArrayRef<Function *> Callees) {
+  SmallVector<Metadata *, 4> Ops;
+  for (Function *F : Callees)
+    Ops.push_back(createConstant(F));
+  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);
 
   SmallVector<Metadata *, 3> Args(1, Dummy.get());
   if (Extra)
     Args.push_back(Extra);
   if (!Name.empty())

test/ThinLTO/X86/lazyload_metadata.ll

 ; Do setup work for all below tests: generate bitcode and combined index
 ; RUN: opt -module-summary %s -o %t.bc -bitcode-mdindex-threshold=0
 ; RUN: opt -module-summary %p/Inputs/lazyload_metadata.ll -o %t2.bc -bitcode-mdindex-threshold=0
 ; RUN: llvm-lto -thinlto-action=thinlink -o %t3.bc %t.bc %t2.bc
 ; REQUIRES: asserts
 
 ; Check that importing @globalfunc1 does not trigger loading all the global
 ; metadata for @globalfunc2 and @globalfunc3
 
 ; RUN: llvm-lto -thinlto-action=import %t2.bc -thinlto-index=%t3.bc \
 ; RUN:          -o /dev/null -stats \
 ; RUN:  2>&1 | FileCheck %s -check-prefix=LAZY
-; LAZY: 51 bitcode-reader  - Number of Metadata records loaded
+; LAZY: 53 bitcode-reader  - Number of Metadata records loaded
 ; LAZY: 2 bitcode-reader  - Number of MDStrings loaded
 
 ; RUN: llvm-lto -thinlto-action=import %t2.bc -thinlto-index=%t3.bc \
 ; RUN:          -o /dev/null -disable-ondemand-mds-loading -stats \
 ; RUN:  2>&1 | FileCheck %s -check-prefix=NOTLAZY
-; NOTLAZY: 60 bitcode-reader  - Number of Metadata records loaded
+; NOTLAZY: 62 bitcode-reader  - Number of Metadata records loaded
 ; NOTLAZY: 7 bitcode-reader  - Number of MDStrings loaded
 
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.11.0"
 
 define void @globalfunc1(i32 %arg) {
   %x = call i1 @llvm.type.test(i8* undef, metadata !"typeid1")