Add function entry count metadata.

[dnovillo]

Summary

This adds three Function methods to handle function entry counts:
setEntryCount(), hasEntryCount() and getEntryCount().

Entry counts are stored under the MD_prof metadata node with the name
"function_entry_count". They are unsigned 64 bit values set by profilers
(instrumentation and sample profiler changes coming up).

I had some internal debate about what to return when
Function::getEntryCount() is called without the function having its
metadata set. I don't want to return a special sentinel value, because
those are typically problematic down the road.

So, I added a Function::hasEntryCount() predicate. If
Function::getEntryCount() is called with no metadata present, it will
cause a compiler assertion.

[dnovillo]

Return Optional<uint64_t> from getEntryCount to indicate whether a count is available.

I'm getting several odd failures in the testsuite. Even though the new code
is only called from the unittest, I'm getting several related failures.
For example,

bin/opt -S test/Verifier/statepoint.ll -verify

Exit Code: 2

Command Output (stderr):

gc.statepoint mismatch in number of vararg call args

%safepoint_token = call i32 (void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 0, i32 0, i32 10, i32 0, i8 addrspace(1)* %arg, i64 addrspace(1)* %cast, i8 addrspace(1)* %arg, i8 addrspace(1)* %arg)

gc.statepoint mismatch in number of vararg call args

%safepoint_token = call i32 (void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 0, i32 0, i32 10, i32 0, i8 addrspace(1)* %arg, i64 addrspace(1)* %cast, i8 addrspace(1)* %arg, i8 addrspace(1)* %arg)

gc.statepoint mismatch in number of vararg call args

%0 = invoke i32 (void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0, i8 addrspace(1)* %obj, i8 addrspace(1)* %obj1)
        to label %normal_dest unwind label %exceptional_return

It seems related to metadata, but I'm not sure how my patch could've triggered
this. Am I missing anything obvious?

Thanks.

[dnovillo]

This update includes the following changes:

• Return Optional<uint64_t> from getEntryCount to indicate whether a count is available.
• Move setEntrycount() and getEntryCount() to lib/IR/Function.cpp.
• Remove @brief from comments.
• Add IR verification to !prof nodes and tests.

[reames]

Reading through the code, I was a left a bit confused as to the actual structure. Could you update with the LangRef update so that it's easier to review? Also, tests for correct usage would be helpful.

lib/IR/Function.cpp

995 ↗

(On Diff #25488)

I'm mildly bothered by using the same name for two different pieces of metadata. Is there a reason not to use a different name here?

[reames]

Before going any further discussing this, I'd like to see an example or
LangRef documentation with an example. I'm not even sure I read the
code right and don't want to waste time discussing something which might
be a result of a misread.

[dnovillo]

• Add documentation for function_entry_count counter.

[reames]

LGTM w/ minor comments addressed. No further review needed.

docs/BranchWeightMetadata.rst

124 ↗

(On Diff #25641)

"function header"? What's that? I assume you mean the definition or declaration itself?

operand -> operator

lib/IR/Verifier.cpp

1480 ↗

(On Diff #25641)

cast rather than dyn_cast

test/Verifier/function-metadata.ll

3 ↗

(On Diff #25641)

I still want to see a positive test example. Your example from the documentation would be a good one. Something to show that the profiling is valid when used properly.

llvm/trunk/docs/BranchWeightMetadata.rst

.. code-block:: c++
   }
 
 CFG Modifications
 =================
 
 Branch Weight Metatada is not proof against CFG changes. If terminator operands'
 are changed some action should be taken. In other case some misoptimizations may
 occur due to incorrent branch prediction information.
+
+Function Entry Counts
+=====================
+
+To allow comparing different functions durint inter-procedural analysis and
+optimization, ``MD_prof`` nodes can also be assigned to a function definition.
+The first operand is a string indicating the name of the associated counter.
+
+Currently, one counter is supported: "function_entry_count". This is a 64-bit
+counter that indicates the number of times that this function was invoked (in
+the case of instrumentation-based profiles). In the case of sampling-based
+profiles, this counter is an approximation of how many times the function was
+invoked.
+
+For example, in the code below, the instrumentation for function foo()
+indicates that it was called 2,590 times at runtime.
+
+.. code-block:: llvm
+
+  define i32 @foo() !prof !1 {
+    ret i32 0
+  }
+  !1 = !{!"function_entry_count", i64 2590}

llvm/trunk/include/llvm/IR/Function.h

 // and a symbol table.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_FUNCTION_H
 #define LLVM_IR_FUNCTION_H
 
 #include "llvm/ADT/iterator_range.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/GlobalObject.h"
 #include "llvm/Support/Compiler.h"
 
 namespace llvm {
setAttributes(
                                  AttributeSet::FunctionIndex, Kind));
   }
   void addFnAttr(StringRef Kind, StringRef Value) {
     setAttributes(
       AttributeSets.addAttribute(getContext(),
                                  AttributeSet::FunctionIndex, Kind, Value));
   }
 
+  /// Set the entry count for this function.
+  void setEntryCount(uint64_t Count);
+
+  /// Get the entry count for this function.
+  Optional<uint64_t> getEntryCount() const;
+
   /// @brief Return true if the function has the attribute.
   bool hasFnAttribute(Attribute::AttrKind Kind) const {
     return AttributeSets.hasAttribute(AttributeSet::FunctionIndex, Kind);
   }
   bool hasFnAttribute(StringRef Kind) const {
     return AttributeSets.hasAttribute(AttributeSet::FunctionIndex, Kind);
   }
 

llvm/trunk/include/llvm/IR/MDBuilder.h

public:
   //===------------------------------------------------------------------===//
 
   /// \brief Return metadata containing two branch weights.
   MDNode *createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight);
 
   /// \brief Return metadata containing a number of branch weights.
   MDNode *createBranchWeights(ArrayRef<uint32_t> Weights);
 
+  /// Return metadata containing the entry count for a function.
+  MDNode *createFunctionEntryCount(uint64_t Count);
+
   //===------------------------------------------------------------------===//
   // Range metadata.
   //===------------------------------------------------------------------===//
 
   /// \brief Return metadata describing the range [Lo, Hi).
   MDNode *createRange(const APInt &Lo, const APInt &Hi);
 
   /// \brief Return metadata describing the range [Lo, Hi).

llvm/trunk/lib/IR/Function.cpp

 #include "llvm/IR/Function.h"
 #include "LLVMContextImpl.h"
 #include "SymbolTableListTraitsImpl.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/IR/CallSite.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/RWMutex.h"
 #include "llvm/Support/StringPool.h"
 #include "llvm/Support/Threading.h"
 using namespace llvm;
 
 // Explicit instantiations of SymbolTableListTraits since some of the methods
void llvm::overrideFunctionAttribute(StringRef Kind, StringRef Value,
 
   AttrsToRemove =
       AttrsToRemove.addAttribute(Ctx, AttributeSet::FunctionIndex, Kind);
   Attrs = Attrs.removeAttributes(Ctx, AttributeSet::FunctionIndex,
                                  AttrsToRemove);
   Attrs = Attrs.addAttribute(Ctx, AttributeSet::FunctionIndex, Kind, Value);
   F.setAttributes(Attrs);
 }
+
+void Function::setEntryCount(uint64_t Count) {
+  MDBuilder MDB(getContext());
+  setMetadata(LLVMContext::MD_prof, MDB.createFunctionEntryCount(Count));
+}
+
+Optional<uint64_t> Function::getEntryCount() const {
+  MDNode *MD = getMetadata(LLVMContext::MD_prof);
+  if (MD && MD->getOperand(0))
+    if (MDString *MDS = dyn_cast<MDString>(MD->getOperand(0)))
+      if (MDS->getString().equals("function_entry_count")) {
+        ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(1));
+        return CI->getValue().getZExtValue();
+      }
+  return None;
+}

llvm/trunk/lib/IR/MDBuilder.cpp

MDNode *MDBuilder::createBranchWeights(ArrayRef<uint32_t> Weights) {
 
   Type *Int32Ty = Type::getInt32Ty(Context);
   for (unsigned i = 0, e = Weights.size(); i != e; ++i)
     Vals[i + 1] = createConstant(ConstantInt::get(Int32Ty, Weights[i]));
 
   return MDNode::get(Context, Vals);
 }
 
+MDNode *MDBuilder::createFunctionEntryCount(uint64_t Count) {
+  SmallVector<Metadata *, 2> Vals(2);
+  Vals[0] = createString("function_entry_count");
+
+  Type *Int64Ty = Type::getInt64Ty(Context);
+  Vals[1] = createConstant(ConstantInt::get(Int64Ty, Count));
+
+  return MDNode::get(Context, Vals);
+}
+
 MDNode *MDBuilder::createRange(const APInt &Lo, const APInt &Hi) {
   assert(Lo.getBitWidth() == Hi.getBitWidth() && "Mismatched bitwidths!");
 
   Type *Ty = IntegerType::get(Context, Lo.getBitWidth());
   return createRange(ConstantInt::get(Ty, Lo), ConstantInt::get(Ty, Hi));
 }
 
 MDNode *MDBuilder::createRange(Constant *Lo, Constant *Hi) {

llvm/trunk/lib/IR/Verifier.cpp

bool VerifyIntrinsicIsVarArg(bool isVarArg,
                                ArrayRef<Intrinsic::IITDescriptor> &Infos);
   bool VerifyAttributeCount(AttributeSet Attrs, unsigned Params);
   void VerifyAttributeTypes(AttributeSet Attrs, unsigned Idx, bool isFunction,
                             const Value *V);
   void VerifyParameterAttrs(AttributeSet Attrs, unsigned Idx, Type *Ty,
                             bool isReturnValue, const Value *V);
   void VerifyFunctionAttrs(FunctionType *FT, AttributeSet Attrs,
                            const Value *V);
+  void VerifyFunctionMetadata(
+      const SmallVector<std::pair<unsigned, MDNode *>, 4> MDs);
 
   void VerifyConstantExprBitcastType(const ConstantExpr *CE);
   void VerifyStatepoint(ImmutableCallSite CS);
   void verifyFrameRecoverIndices();
 
   // Module-level debug info verification...
   void verifyTypeRefs();
   template <class MapTy>
void Verifier::VerifyFunctionAttrs(FunctionType *FT, AttributeSet Attrs,
   if (Attrs.hasAttribute(AttributeSet::FunctionIndex,
                          Attribute::JumpTable)) {
     const GlobalValue *GV = cast<GlobalValue>(V);
     Assert(GV->hasUnnamedAddr(),
            "Attribute 'jumptable' requires 'unnamed_addr'", V);
   }
 }
 
+void Verifier::VerifyFunctionMetadata(
+    const SmallVector<std::pair<unsigned, MDNode *>, 4> MDs) {
+  if (MDs.empty())
+    return;
+
+  for (unsigned i = 0; i < MDs.size(); i++) {
+    if (MDs[i].first == LLVMContext::MD_prof) {
+      MDNode *MD = MDs[i].second;
+      Assert(MD->getNumOperands() == 2,
+             "!prof annotations should have exactly 2 operands", MD);
+
+      // Check first operand.
+      Assert(MD->getOperand(0) != nullptr, "first operand should not be null",
+             MD);
+      Assert(isa<MDString>(MD->getOperand(0)),
+             "expected string with name of the !prof annotation", MD);
+      MDString *MDS = cast<MDString>(MD->getOperand(0));
+      StringRef ProfName = MDS->getString();
+      Assert(ProfName.equals("function_entry_count"),
+             "first operand should be 'function_entry_count'", MD);
+
+      // Check second operand.
+      Assert(MD->getOperand(1) != nullptr, "second operand should not be null",
+             MD);
+      Assert(isa<ConstantAsMetadata>(MD->getOperand(1)),
+             "expected integer argument to function_entry_count", MD);
+    }
+  }
+}
+
 void Verifier::VerifyConstantExprBitcastType(const ConstantExpr *CE) {
   if (CE->getOpcode() != Instruction::BitCast)
     return;
 
   Assert(CastInst::castIsValid(Instruction::BitCast, CE->getOperand(0),
                                CE->getType()),
          "Invalid bitcast", CE);
 }
if (!isLLVMdotName)
       Assert(!I->getType()->isMetadataTy(),
              "Function takes metadata but isn't an intrinsic", I, &F);
   }
 
   // Get the function metadata attachments.
   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
   F.getAllMetadata(MDs);
   assert(F.hasMetadata() != MDs.empty() && "Bit out-of-sync");
+  VerifyFunctionMetadata(MDs);
 
   if (F.isMaterializable()) {
     // Function has a body somewhere we can't see.
     Assert(MDs.empty(), "unmaterialized function cannot have metadata", &F,
            MDs.empty() ? nullptr : MDs.front().second);
   } else if (F.isDeclaration()) {
     Assert(F.hasExternalLinkage() || F.hasExternalWeakLinkage(),
            "invalid linkage type for function declaration", &F);

llvm/trunk/test/Verifier/function-metadata-bad.ll

+; RUN: not llvm-as < %s -o /dev/null 2>&1 | FileCheck %s
+
+define i32 @bad1() !prof !0 {
+  ret i32 0
+}
+
+!0 = !{i32 123, i32 3}
+; CHECK: assembly parsed, but does not verify as correct!
+; CHECK-NEXT: expected string with name of the !prof annotation
+; CHECK-NEXT: !0 = !{i32 123, i32 3}
+
+define i32 @bad2() !prof !1 {
+  ret i32 0
+}
+
+!1 = !{!"function_entry_count"}
+; CHECK-NEXT: !prof annotations should have exactly 2 operands
+; CHECK-NEXT: !1 = !{!"function_entry_count"}
+
+
+define i32 @bad3() !prof !2 {
+  ret i32 0
+}
+
+!2 = !{!"some_other_count", i64 200}
+; CHECK-NEXT: first operand should be 'function_entry_count'
+; CHECK-NEXT: !2 = !{!"some_other_count", i64 200}
+
+define i32 @bad4() !prof !3 {
+  ret i32 0
+}
+
+!3 = !{!"function_entry_count", !"string"}
+; CHECK-NEXT: expected integer argument to function_entry_count
+; CHECK-NEXT: !3 = !{!"function_entry_count", !"string"}

llvm/trunk/test/Verifier/function-metadata-good.ll

+; RUN: llvm-as < %s -o /dev/null 2>&1
+
+; Function foo() is called 2,304 times at runtime.
+define i32 @foo() !prof !0 {
+  ret i32 0
+}
+
+!0 = !{!"function_entry_count", i32 2304}

llvm/trunk/unittests/IR/MetadataTest.cpp

TEST_F(FunctionAttachmentTest, Verifier) {
   EXPECT_TRUE(verifyModule(*F->getParent()));
 
   // Functions with a body can.
   (void)new UnreachableInst(Context, BasicBlock::Create(Context, "bb", F));
   EXPECT_FALSE(verifyModule(*F->getParent()));
   EXPECT_FALSE(verifyFunction(*F));
 }
 
+TEST_F(FunctionAttachmentTest, EntryCount) {
+  Function *F = getFunction("foo");
+  EXPECT_FALSE(F->getEntryCount().hasValue());
+  F->setEntryCount(12304);
+  EXPECT_TRUE(F->getEntryCount().hasValue());
+  EXPECT_EQ(12304u, *F->getEntryCount());
+}
+
 }