[llvm][misexpect] Track provenance of branch weights

[paulkirth]

Summary

MisExpect diagnostics need to know if branch_weight metadata originates
from an llvm.expect intrinsic. Without that information, we check branch
weights multiple times in the case if ThinLTO + SampleProfiling, leading
to some inaccuracy in how we report MisExpect related diagnostics to
users.

This patch allows us to track that provenance by adding a new optional
field to the branch weight metadata type. Since we change the format of
MD_prof metadata in a fundamental way, we need to update code handling
branch weights in a number of places.

We also update the lang ref for branch weights to reflect the change.

[tejohnson]

@davidxl @xur for review and thoughts.

I'm a little wary of requiring that both pieces of metadata be carried together, as that seems very brittle to maintain in the compiler. What would happen if the MD_expected didn't get propagated by some pass along with the MD_prof? I think you would get a false negative, which I suppose is better than a false positive. An alternative, that I guess would require more extensive changes, is to add an additional item to the "branch_weights" list (would need to be obviously distinguishable by type from the list of weights since that can be variable though).

Patch needs tests showing uses of the new metadata, and some documentation in LangRef (i.e. near https://llvm.org/docs/LangRef.html#prof-metadata).

[paulkirth]

In D131306#3756009, @tejohnson wrote:

@davidxl @xur for review and thoughts.

I'm a little wary of requiring that both pieces of metadata be carried together, as that seems very brittle to maintain in the compiler. What would happen if the MD_expected didn't get propagated by some pass along with the MD_prof? I think you would get a false negative, which I suppose is better than a false positive. An alternative, that I guess would require more extensive changes, is to add an additional item to the "branch_weights" list (would need to be obviously distinguishable by type from the list of weights since that can be variable though).

Agreed. This isn't my preferred solution, but it seemed far less invasive than changing the format of profiling metadata. Originally, I had looked into adding a provenance field to the metadata. It required changes to every test that has branch weights, and I balked at submitting that. I'm also a little wary of making a heavily used metadata type larger. I guess there isn't a lot of difference, but the external metadata is optional, and we could remove it after checking is complete.

Unfortunately, I just don't think there is a clean solution here. Either we make an invasive change to the metadata format, or we deal w/ updating 2 pieces of metadata everywhere. I'm just very unsure about which is the right tradeoff.

Patch needs tests showing uses of the new metadata, and some documentation in LangRef (i.e. near https://llvm.org/docs/LangRef.html#prof-metadata).

Yes, testing and documentation is something I plan to improve, but I wanted to get some feedback on this approach before investing too heavily.

[tejohnson]

In D131306#3756074, @paulkirth wrote:

In D131306#3756009, @tejohnson wrote:

@davidxl @xur for review and thoughts.

I'm a little wary of requiring that both pieces of metadata be carried together, as that seems very brittle to maintain in the compiler. What would happen if the MD_expected didn't get propagated by some pass along with the MD_prof? I think you would get a false negative, which I suppose is better than a false positive. An alternative, that I guess would require more extensive changes, is to add an additional item to the "branch_weights" list (would need to be obviously distinguishable by type from the list of weights since that can be variable though).

Agreed. This isn't my preferred solution, but it seemed far less invasive than changing the format of profiling metadata. Originally, I had looked into adding a provenance field to the metadata. It required changes to every test that has branch weights, and I balked at submitting that. I'm also a little wary of making a heavily used metadata type larger. I guess there isn't a lot of difference, but the external metadata is optional, and we could remove it after checking is complete.

Well I was thinking the extra field would be optional as well and could be removed. But understood that this requires more changes (although maybe not if it is optional, and after your recent changes to centralize some of the prof metadata handling in the compiler).

Unfortunately, I just don't think there is a clean solution here. Either we make an invasive change to the metadata format, or we deal w/ updating 2 pieces of metadata everywhere. I'm just very unsure about which is the right tradeoff.

Patch needs tests showing uses of the new metadata, and some documentation in LangRef (i.e. near https://llvm.org/docs/LangRef.html#prof-metadata).

Yes, testing and documentation is something I plan to improve, but I wanted to get some feedback on this approach before investing too heavily.

Ok understood. Hopefully others will chime in with feedback.

[paulkirth]

In D131306#3756087, @tejohnson wrote:

Well I was thinking the extra field would be optional as well and could be removed. But understood that this requires more changes (although maybe not if it is optional, and after your recent changes to centralize some of the prof metadata handling in the compiler).

Hmm, I don't think I considered that a field in the metadata could be optional. Do you mean something like this?

!{!"branch_weights", !10, i32 1717986918, i32 429496731}

where !10 is just some optional metadata, and we'd just ensure things that parse the MD_prof data skip it correctly? Given that we've mostly consolidated how branch weights are extracted and manipulated that might only require a limited number of updates to the code and tests.

[tejohnson]

In D131306#3756153, @paulkirth wrote:

In D131306#3756087, @tejohnson wrote:

Well I was thinking the extra field would be optional as well and could be removed. But understood that this requires more changes (although maybe not if it is optional, and after your recent changes to centralize some of the prof metadata handling in the compiler).

Hmm, I don't think I considered that a field in the metadata could be optional. Do you mean something like this?

!{!"branch_weights", !10, i32 1717986918, i32 429496731}

where !10 is just some optional metadata, and we'd just ensure things that parse the MD_prof data skip it correctly? Given that we've mostly consolidated how branch weights are extracted and manipulated that might only require a limited number of updates to the code and tests.

Yep! Or a string. I was thinking it might be easier at the end of the list of fields, but either way.

[paulkirth]

I think that may be a better approach. Let me investigate a bit and see what the exact tradeoffs are.

If anyone else has a suggestion or thought on another way to handle this, I'm all ears.

[xur]

I agreed with Teresa: adding an optional string is better than using a separated metadata here.

[paulkirth]

rebase and change implementation to include provenance information directly in the MD_prof metadata

[paulkirth]

@tejohnson @xur I kind of dropped the ball on these patches, but what are your thoughts on this approach over the old(more invasive) change to the profdata format I had prototyped before? the patch will obviously need to be rebased, but other than that, do we see a downside to handling provenance tracking for branch weights this way?

[tejohnson]

In D131306#4037037, @paulkirth wrote:

@tejohnson @xur I kind of dropped the ball on these patches, but what are your thoughts on this approach over the old(more invasive) change to the profdata format I had prototyped before? the patch will obviously need to be rebased, but other than that, do we see a downside to handling provenance tracking for branch weights this way?

Sorry, it looks like you were waiting on a review of the latest changes from me but I didn't get to it. I don't recall the other changes you prototyped off the top of my head - can you point me to that? But I don't have an issue with this approach as I recall it seemed cleanest at the time.

[paulkirth]

In D131306#4052782, @tejohnson wrote:

In D131306#4037037, @paulkirth wrote:

@tejohnson @xur I kind of dropped the ball on these patches, but what are your thoughts on this approach over the old(more invasive) change to the profdata format I had prototyped before? the patch will obviously need to be rebased, but other than that, do we see a downside to handling provenance tracking for branch weights this way?

Sorry, it looks like you were waiting on a review of the latest changes from me but I didn't get to it. I don't recall the other changes you prototyped off the top of my head - can you point me to that?

It was just the last revision of this patch https://reviews.llvm.org/D131306?vs=on&id=450448#toc. The way I handled it before was to leave the MD_prof layout alone and use a new MD type to track the provenance. It had the benefit of leaving the layout alone, and the downside that every place that did something w/ MD_prof needed to copy that as well.

But I don't have an issue with this approach as I recall it seemed cleanest at the time.

Sounds good. I'll start work updating this then. Thanks!

[tejohnson]

In D131306#4052878, @paulkirth wrote:

In D131306#4052782, @tejohnson wrote:

In D131306#4037037, @paulkirth wrote:

@tejohnson @xur I kind of dropped the ball on these patches, but what are your thoughts on this approach over the old(more invasive) change to the profdata format I had prototyped before? the patch will obviously need to be rebased, but other than that, do we see a downside to handling provenance tracking for branch weights this way?

Sorry, it looks like you were waiting on a review of the latest changes from me but I didn't get to it. I don't recall the other changes you prototyped off the top of my head - can you point me to that?

It was just the last revision of this patch https://reviews.llvm.org/D131306?vs=on&id=450448#toc. The way I handled it before was to leave the MD_prof layout alone and use a new MD type to track the provenance. It had the benefit of leaving the layout alone, and the downside that every place that did something w/ MD_prof needed to copy that as well.

Ok, yeah, I definitely prefer it to not be a separate metadata that we need to keep in sync. I prefer this approach.

But I don't have an issue with this approach as I recall it seemed cleanest at the time.

Sounds good. I'll start work updating this then. Thanks!

[paulkirth]

Rebase.

• fix test cases
• improve code swaping branch weights in instruction.cpp
• clean up some dead metadata types left over from an old version of this patch

[paulkirth]

Rebase

[jdoerfert]

Drive by: There should be a lang ref component to this. Also, changing branch weight metadata might impact downstream users, an RFC seems in order (assuming I didn't miss one).

[paulkirth]

In D131306#4081864, @jdoerfert wrote:

Drive by: There should be a lang ref component to this.

Thanks for pointing out that we need to update the langref. Offhand, do you recall if there are places other than BranchWeightMetadata.rst that would need to be updated?

Also, changing branch weight metadata might impact downstream users, an RFC seems in order (assuming I didn't miss one).

You didn't miss one. I was under the impression that the layout of MD_prof was an internal detail that wouldn't require one. I think that is doubly true since the new field is optional, and existing bitcode/IR can still be consumed.

But you raise a fair point that it would impact anyone trying to process new IR, so maybe one is in order to be a good citizen. I'll try to set aside some time to draft a short RFC for discourse.

[paulkirth]

Rebase and update lang ref

[paulkirth]

Update summary

[tejohnson]

Sorry for the slow response. Looks pretty good, just a few minor suggestions and questions.

llvm/include/llvm/IR/MDBuilder.h

61

Update comment to mention new parameter in this and the below methods.

Also, I wonder if it would be better to make the IsExpected non-optional, to force any new callers to think about whether they need that and help avoid issues where it gets dropped incorrectly?

llvm/include/llvm/IR/ProfDataUtils.h

58

Maybe note the meaning of the expected field (i.e. had an llvm.expect intrinsic).

llvm/lib/Analysis/BranchProbabilityInfo.cpp

394

Isn't it now the first 1 or 2 are a name?

397

Should this be an assert?

llvm/lib/IR/Instructions.cpp

732

I guess we don't have to worry about pushing the expect provenance because this is a call and it shouldn't have one. Maybe add an assert that the offset is 1?

llvm/lib/IR/Verifier.cpp

4531

Related to an earlier comment regarding calls - maybe the verifier should ensure that "expected" only shows up on certain instruction types?

llvm/lib/Transforms/Utils/MisExpect.cpp

156

Why not check it within verifyMisExpect, seems less error prone than requiring callers to check?

[paulkirth]

llvm/include/llvm/IR/MDBuilder.h

61

Also, I wonder if it would be better to make the IsExpected non-optional, to force any new callers to think about whether they need that and help avoid issues where it gets dropped incorrectly?

I think that's a good idea. I can see how much that affects this patch after addressing the current set of comments.

llvm/lib/Analysis/BranchProbabilityInfo.cpp

394

Actually, this code block doesn' need to be here at all anymore. That check was moved up into getValidBranchWeightMDNode. I must have missed that when I rebased.

397

Same as above. This wasn't an assert originally, so I didn't change its behavior.

llvm/lib/IR/Verifier.cpp

4531

I think the issue is that we've overload "branch_weights" for lots of things that aren't branch weights, but are similar. IMO it should be something like: !{!"call_count", i32 2000}, but that likely would break a number of things in the codebase, and require lots of special handling for the various different uses. Right now the IR change I've made doesn't really disambiguate the various cases and just treats them all uniformly.

I'll take a look at updating the verifier rules after addressing the other comments.

llvm/lib/Transforms/Utils/MisExpect.cpp

156

Centralizing the checking would be ideal, but because Frontend and Backend checking are not completely symmetric, we cannot rely on the instruction having the Expected flag set in the metadata when verifyMisExpect is called for Frontend based instrumentation.

Maybe I should update the comment to reflect that the "provenance" check ensures we won't run backend checks multiple times, and put a more explicit comment about it in checkBackendInstrumentation?

[paulkirth]

Rebase and address comments.

• update doc comments and describe IsExpected parameter
• add assert when scaling branch weights on calls
• remove redundant check, now done in getValidBranchWeightMDNode()
• update assert comment, and describe rationale for hasExpectedProvenance in checkBackendInstrumentation()

TODO:

• investigate making IsExpected a non-optional parameter.
• investigate more checks on the instruction type when metadata has an !expected field

[paulkirth]

Remove redunant assert

clang/test/CodeGenCXX/attr-likelihood-if-branch-weights.cpp

if (b)
     switch (i)
       [[unlikely]] {}
   else {
     // Make sure the branches aren't optimized away.
     b = true;
   }
 }
 
-// CHECK: ![[PROF_LIKELY]] = !{!"branch_weights", i32 [[UNLIKELY]], i32 [[LIKELY]]}
-// CHECK: ![[PROF_UNLIKELY]] = !{!"branch_weights", i32 [[LIKELY]], i32 [[UNLIKELY]]}
+// CHECK: ![[PROF_LIKELY]] = !{!"branch_weights", !"expected", i32 [[UNLIKELY]], i32 [[LIKELY]]}
+// CHECK: ![[PROF_UNLIKELY]] = !{!"branch_weights", !"expected", i32 [[LIKELY]], i32 [[UNLIKELY]]}

clang/test/CodeGenCXX/attr-likelihood-if-vs-builtin-expect.cpp

void tu2(int &i) {
   // CHECK: br {{.*}} !prof [[BW_UNLIKELY]]
   if (a() ? b() : c()) [[unlikely]] {
     ++i;
   } else {
     --i;
   }
 }
 
-// CHECK: [[BW_LIKELY]] = !{!"branch_weights", i32 2000, i32 1}
-// CHECK: [[BW_UNLIKELY]] = !{!"branch_weights", i32 1, i32 2000}
+// CHECK: [[BW_LIKELY]] = !{!"branch_weights", !"expected", i32 2000, i32 1}
+// CHECK: [[BW_UNLIKELY]] = !{!"branch_weights", !"expected", i32 1, i32 2000}

llvm/include/llvm/IR/MDBuilder.h

public:
   /// for the Accuracy parameter indicates the default (maximal precision)
   /// setting.
   MDNode *createFPMath(float Accuracy);
 
   //===------------------------------------------------------------------===//
   // Prof metadata.
   //===------------------------------------------------------------------===//
 
   /// Return metadata containing two branch weights.
-  MDNode *createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight);
+  MDNode *createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight,
+                              bool IsExpected = false);
 
   /// Return metadata containing a number of branch weights.
-  MDNode *createBranchWeights(ArrayRef<uint32_t> Weights);
+  MDNode *createBranchWeights(ArrayRef<uint32_t> Weights,
+                              bool IsExpected = false);
 
   /// Return metadata specifying that a branch or switch is unpredictable.
   MDNode *createUnpredictable();
 
   /// Return metadata containing the entry \p Count for a function, a boolean
   /// \Synthetic indicating whether the counts were synthetized, and the
   /// GUIDs stored in \p Imports that need to be imported for sample PGO, to
   /// enable the same inlines as the profiled optimized binary

llvm/include/llvm/IR/ProfDataUtils.h

 
 /// Get the valid branch weights metadata node
 ///
 /// \param I The Instruction to get the weights from.
 /// \returns A pointer to I's valid branch weights metadata node, if it exists.
 /// Nullptr otherwise.
 MDNode *getValidBranchWeightMDNode(const Instruction &I);
 
+/// Check if Branch Weight Metadata has an "expected" field
+bool hasExpectedProvenance(const Instruction &I);
+
+/// Check if Branch Weight Metadata has an "expected" field
+bool hasExpectedProvenance(const MDNode *ProfileData);
+
+/// return the offset to the first branch weight data
+unsigned getBranchWeightOffset(const Instruction &I);
+
+/// return the offset to the first branch weight data
+unsigned getBranchWeightOffset(const MDNode *ProfileData);
+
 /// Extract branch weights from MD_prof metadata
 ///
 /// \param ProfileData A pointer to an MDNode.
 /// \param [out] Weights An output vector to fill with branch weights
 /// \returns True if weights were extracted, False otherwise. When false Weights
 /// will be cleared.
 bool extractBranchWeights(const MDNode *ProfileData,
                           SmallVectorImpl<uint32_t> &Weights);

llvm/lib/Analysis/BranchProbabilityInfo.cpp

bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
 
   MDNode *WeightsNode = getValidBranchWeightMDNode(*TI);
   if (!WeightsNode)
     return false;
 
   // Check that the number of successors is manageable.
   assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
 
+  // Ensure there are weights for all of the successors. Note that the first
+  // operand to the metadata node is a name, not a weight.
+  if (WeightsNode->getNumOperands() !=
+      TI->getNumSuccessors() + getBranchWeightOffset(WeightsNode))
+    return false;
+
   // Build up the final weights that will be used in a temporary buffer.
   // Compute the sum of all weights to later decide whether they need to
   // be scaled to fit in 32 bits.
   uint64_t WeightSum = 0;
   SmallVector<uint32_t, 2> Weights;
   SmallVector<unsigned, 2> UnreachableIdxs;
   SmallVector<unsigned, 2> ReachableIdxs;
 

llvm/lib/CodeGen/CodeGenPrepare.cpp

if (Opc == Instruction::Or) {
       // TmpBB, but the math is more complicated.
       uint64_t TrueWeight, FalseWeight;
       if (extractBranchWeights(*Br1, TrueWeight, FalseWeight)) {
         uint64_t NewTrueWeight = TrueWeight;
         uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
         scaleWeights(NewTrueWeight, NewFalseWeight);
         Br1->setMetadata(LLVMContext::MD_prof,
                          MDBuilder(Br1->getContext())
-                             .createBranchWeights(TrueWeight, FalseWeight));
+                             .createBranchWeights(TrueWeight, FalseWeight,
+                                                  hasExpectedProvenance(*Br1)));
 
         NewTrueWeight = TrueWeight;
         NewFalseWeight = 2 * FalseWeight;
         scaleWeights(NewTrueWeight, NewFalseWeight);
         Br2->setMetadata(LLVMContext::MD_prof,
                          MDBuilder(Br2->getContext())
                              .createBranchWeights(TrueWeight, FalseWeight));
       }

llvm/lib/IR/Instruction.cpp

if (getSuccessor(Idx) == OldBB)
       setSuccessor(Idx, NewBB);
 }
 
 Instruction *Instruction::cloneImpl() const {
   llvm_unreachable("Subclass of Instruction failed to implement cloneImpl");
 }
 
 void Instruction::swapProfMetadata() {
-  MDNode *ProfileData = getBranchWeightMDNode(*this);
-  if (!ProfileData || ProfileData->getNumOperands() != 3)
+  MDNode *ProfileData = getMetadata(LLVMContext::MD_prof);
+  if (!isBranchWeightMD(ProfileData))
     return;
+  SmallVector<Metadata *, 4> Ops;
+  int FirstIdx = getBranchWeightOffset(ProfileData);
+  int SecondIdx = FirstIdx + 1;
+  Ops.push_back(ProfileData->getOperand(0));
+  if (hasExpectedProvenance(ProfileData)) {
+    Ops.push_back(ProfileData->getOperand(1));
+  }
+  // Switch the order of the weights
+  Ops.push_back(ProfileData->getOperand(SecondIdx));
+  Ops.push_back(ProfileData->getOperand(FirstIdx));
 
-  // The first operand is the name. Fetch them backwards and build a new one.
-  Metadata *Ops[] = {ProfileData->getOperand(0), ProfileData->getOperand(2),
-                     ProfileData->getOperand(1)};
   setMetadata(LLVMContext::MD_prof,
               MDNode::get(ProfileData->getContext(), Ops));
 }
 
 void Instruction::copyMetadata(const Instruction &SrcInst,
                                ArrayRef<unsigned> WL) {
   if (!SrcInst.hasMetadata())
     return;

llvm/lib/IR/Instructions.cpp

void CallInst::updateProfWeight(uint64_t S, uint64_t T) {
   }
 
   MDBuilder MDB(getContext());
   SmallVector<Metadata *, 3> Vals;
   Vals.push_back(ProfileData->getOperand(0));
   APInt APS(128, S), APT(128, T);
   if (ProfDataName->getString().equals("branch_weights") &&
       ProfileData->getNumOperands() > 0) {
+    auto Offset = getBranchWeightOffset(ProfileData);
     // Using APInt::div may be expensive, but most cases should fit 64 bits.
-    APInt Val(128, mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1))
-                       ->getValue()
-                       .getZExtValue());
+    APInt Val(128,
+              mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(Offset))
     Val *= APS;
     Vals.push_back(MDB.createConstant(
         ConstantInt::get(Type::getInt32Ty(getContext()),
                          Val.udiv(APT).getLimitedValue(UINT32_MAX))));
   } else if (ProfDataName->getString().equals("VP"))
     for (unsigned i = 1; i < ProfileData->getNumOperands(); i += 2) {
       // The first value is the key of the value profile, which will not change.
       Vals.push_back(ProfileData->getOperand(i));
MDNode *SwitchInstProfUpdateWrapper::buildProfBranchWeightsMD() {
 
   if (AllZeroes || Weights->size() < 2)
     return nullptr;
 
   return MDBuilder(SI.getParent()->getContext()).createBranchWeights(*Weights);
 }
 
 void SwitchInstProfUpdateWrapper::init() {
-  MDNode *ProfileData = getBranchWeightMDNode(SI);
-  if (!ProfileData)
+  SmallVector<uint32_t, 8> Weights;
+  if (!extractBranchWeights(SI, Weights))
     return;
 
-  if (ProfileData->getNumOperands() != SI.getNumSuccessors() + 1) {
+  if (Weights.size() != SI.getNumSuccessors()) {
     llvm_unreachable("number of prof branch_weights metadata operands does "
                      "not correspond to number of succesors");
   }
 
-  SmallVector<uint32_t, 8> Weights;
-  if (!extractBranchWeights(ProfileData, Weights))
-    return;
   this->Weights = std::move(Weights);
 }
 
 SwitchInst::CaseIt
 SwitchInstProfUpdateWrapper::removeCase(SwitchInst::CaseIt I) {
   if (Weights) {
     assert(SI.getNumSuccessors() == Weights->size() &&
            "num of prof branch_weights must accord with num of successors");

llvm/lib/IR/MDBuilder.cpp

if (Accuracy == 0.0)
     return nullptr;
   assert(Accuracy > 0.0 && "Invalid fpmath accuracy!");
   auto *Op =
       createConstant(ConstantFP::get(Type::getFloatTy(Context), Accuracy));
   return MDNode::get(Context, Op);
 }
 
 MDNode *MDBuilder::createBranchWeights(uint32_t TrueWeight,
-                                       uint32_t FalseWeight) {
-  return createBranchWeights({TrueWeight, FalseWeight});
+                                       uint32_t FalseWeight, bool IsExpected) {
+  return createBranchWeights({TrueWeight, FalseWeight}, IsExpected);
 }
 
-MDNode *MDBuilder::createBranchWeights(ArrayRef<uint32_t> Weights) {
+MDNode *MDBuilder::createBranchWeights(ArrayRef<uint32_t> Weights,
+                                       bool IsExpected) {
   assert(Weights.size() >= 1 && "Need at least one branch weights!");
 
-  SmallVector<Metadata *, 4> Vals(Weights.size() + 1);
+  auto Offset = IsExpected ? 2 : 1;
+  SmallVector<Metadata *, 4> Vals(Weights.size() + Offset);
   Vals[0] = createString("branch_weights");
+  if (IsExpected)
+    Vals[1] = createString("expected");
 
   Type *Int32Ty = Type::getInt32Ty(Context);
   for (unsigned i = 0, e = Weights.size(); i != e; ++i)
-    Vals[i + 1] = createConstant(ConstantInt::get(Int32Ty, Weights[i]));
+    Vals[i + Offset] = createConstant(ConstantInt::get(Int32Ty, Weights[i]));
 
   return MDNode::get(Context, Vals);
 }
 
 MDNode *MDBuilder::createUnpredictable() {
   return MDNode::get(Context, std::nullopt);
 }
 

llvm/lib/IR/ProfDataUtils.cpp

 // { MDString,            [i32, i32, ...]}
 //
 // Concretely for Branch Weights
 // { "branch_weights",    [i32 1, i32 10000]}
 //
 // We maintain some constants here to ensure that we access the branch weights
 // correctly, and can change the behavior in the future if the layout changes
 
-// The index at which the weights vector starts
-constexpr unsigned WeightsIdx = 1;
-
 // the minimum number of operands for MD_prof nodes with branch weights
 constexpr unsigned MinBWOps = 3;
 
 bool extractWeights(const MDNode *ProfileData,
                     SmallVectorImpl<uint32_t> &Weights) {
   // Assume preconditions are already met (i.e. this is valid metadata)
   assert(ProfileData && "ProfileData was nullptr in extractWeights");
   unsigned NOps = ProfileData->getNumOperands();
 
+  // The index at which the weights vector starts
+  unsigned WeightsIdx = getBranchWeightOffset(ProfileData);
   assert(WeightsIdx < NOps && "Weights Index must be less than NOps.");
   Weights.resize(NOps - WeightsIdx);
 
   for (unsigned Idx = WeightsIdx, E = NOps; Idx != E; ++Idx) {
     ConstantInt *Weight =
         mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(Idx));
     assert(Weight && "Malformed branch_weight in MD_prof node");
     assert(Weight->getValue().getActiveBits() <= 32 &&
MDNode *getBranchWeightMDNode(const Instruction &I) {
   auto *ProfileData = I.getMetadata(LLVMContext::MD_prof);
   if (!isBranchWeightMD(ProfileData))
     return nullptr;
   return ProfileData;
 }
 
 MDNode *getValidBranchWeightMDNode(const Instruction &I) {
   auto *ProfileData = getBranchWeightMDNode(I);
-  if (ProfileData && ProfileData->getNumOperands() == 1 + I.getNumSuccessors())
+  if (ProfileData &&
+      ProfileData->getNumOperands() ==
+          getBranchWeightOffset(ProfileData) + I.getNumSuccessors())
     return ProfileData;
   return nullptr;
 }
 
+bool hasExpectedProvenance(const Instruction &I) {
+  auto *ProfileData = I.getMetadata(LLVMContext::MD_prof);
+  return hasExpectedProvenance(ProfileData);
+}
+
+bool hasExpectedProvenance(const MDNode *ProfileData) {
+  if (!isBranchWeightMD(ProfileData))
+    return false;
+
+  auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(1));
+  if (!ProfDataName)
+    return false;
+  return ProfDataName->getString().equals("expected");
+}
+
+unsigned getBranchWeightOffset(const Instruction &I) {
+  auto *ProfileData = I.getMetadata(LLVMContext::MD_prof);
+  return getBranchWeightOffset(ProfileData);
+}
+
+unsigned getBranchWeightOffset(const MDNode *ProfileData) {
+  return hasExpectedProvenance(ProfileData) ? 2 : 1;
+}
+
 bool extractBranchWeights(const MDNode *ProfileData,
                           SmallVectorImpl<uint32_t> &Weights) {
   if (!isBranchWeightMD(ProfileData))
     return false;
   return extractWeights(ProfileData, Weights);
 }
 
 bool extractBranchWeights(const Instruction &I,
bool extractProfTotalWeight(const MDNode *ProfileData, uint64_t &TotalVal) {
   if (!ProfileData)
     return false;
 
   auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0));
   if (!ProfDataName)
     return false;
 
   if (ProfDataName->getString().equals("branch_weights")) {
-    for (unsigned Idx = 1; Idx < ProfileData->getNumOperands(); Idx++) {
+    int Offset = getBranchWeightOffset(ProfileData);
+    for (unsigned Idx = Offset; Idx < ProfileData->getNumOperands(); Idx++) {
       auto *V = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(Idx));
       assert(V && "Malformed branch_weight in MD_prof node");
       TotalVal += V->getValue().getZExtValue();
     }
     return true;
   }
 
   if (ProfDataName->getString().equals("VP") &&

llvm/lib/IR/Verifier.cpp

 #include "llvm/IR/IntrinsicsAArch64.h"
 #include "llvm/IR/IntrinsicsARM.h"
 #include "llvm/IR/IntrinsicsWebAssembly.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ModuleSlotTracker.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/ProfDataUtils.h"
 #include "llvm/IR/Statepoint.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/AtomicOrdering.h"
Check(MD->getNumOperands() >= 2,
         "!prof annotations should have no less than 2 operands", MD);
 
   // Check first operand.
   Check(MD->getOperand(0) != nullptr, "first operand should not be null", MD);
   Check(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();
+  unsigned Offset = getBranchWeightOffset(I);
 
   // Check consistency of !prof branch_weights metadata.
   if (ProfName.equals("branch_weights")) {
     if (isa<InvokeInst>(&I)) {
-      Check(MD->getNumOperands() == 2 || MD->getNumOperands() == 3,
+      Check(MD->getNumOperands() == (1 + Offset) ||
+                MD->getNumOperands() == (2 + Offset),
             "Wrong number of InvokeInst branch_weights operands", MD);
     } else {
       unsigned ExpectedNumOperands = 0;
       if (BranchInst *BI = dyn_cast<BranchInst>(&I))
         ExpectedNumOperands = BI->getNumSuccessors();
       else if (SwitchInst *SI = dyn_cast<SwitchInst>(&I))
         ExpectedNumOperands = SI->getNumSuccessors();
       else if (isa<CallInst>(&I))
         ExpectedNumOperands = 1;
       else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(&I))
         ExpectedNumOperands = IBI->getNumDestinations();
       else if (isa<SelectInst>(&I))
         ExpectedNumOperands = 2;
       else if (CallBrInst *CI = dyn_cast<CallBrInst>(&I))
         ExpectedNumOperands = CI->getNumSuccessors();
       else
         CheckFailed("!prof branch_weights are not allowed for this instruction",
                     MD);
 
-      Check(MD->getNumOperands() == 1 + ExpectedNumOperands,
+      Check(MD->getNumOperands() == Offset + ExpectedNumOperands,
             "Wrong number of operands", MD);
     }
-    for (unsigned i = 1; i < MD->getNumOperands(); ++i) {
+    for (unsigned i = Offset; i < MD->getNumOperands(); ++i) {
       auto &MDO = MD->getOperand(i);
       Check(MDO, "second operand should not be null", MD);
       Check(mdconst::dyn_extract<ConstantInt>(MDO),
             "!prof brunch_weights operand is not a const int");
     }
   }
 }
 

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

static bool handleSwitchExpect(SwitchInst &SI) {
   uint64_t Index = (Case == *SI.case_default()) ? 0 : Case.getCaseIndex() + 1;
   Weights[Index] = LikelyBranchWeightVal;
 
   misexpect::checkExpectAnnotations(SI, Weights, /*IsFrontend=*/true);
 
   SI.setCondition(ArgValue);
 
   SI.setMetadata(LLVMContext::MD_prof,
-                 MDBuilder(CI->getContext()).createBranchWeights(Weights));
+                 MDBuilder(CI->getContext())
+                     .createBranchWeights(Weights, /*IsExpected*/ true));
 
   return true;
 }
 
 /// Handler for PHINodes that define the value argument to an
 /// @llvm.expect call.
 ///
 /// If the operand of the phi has a constant value and it 'contradicts'
for (unsigned i = 0, e = PhiDef->getNumIncomingValues(); i != e; ++i) {
     std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) = getBranchWeight(
         Expect->getCalledFunction()->getIntrinsicID(), Expect, 2);
     if (!ExpectedValueIsLikely)
       std::swap(LikelyBranchWeightVal, UnlikelyBranchWeightVal);
 
     if (IsOpndComingFromSuccessor(BI->getSuccessor(1)))
       BI->setMetadata(LLVMContext::MD_prof,
                       MDB.createBranchWeights(LikelyBranchWeightVal,
-                                              UnlikelyBranchWeightVal));
+                                              UnlikelyBranchWeightVal,
+                                              /*IsExpected=*/true));
     else if (IsOpndComingFromSuccessor(BI->getSuccessor(0)))
       BI->setMetadata(LLVMContext::MD_prof,
                       MDB.createBranchWeights(UnlikelyBranchWeightVal,
-                                              LikelyBranchWeightVal));
+                                              LikelyBranchWeightVal,
+                                              /*IsExpected=*/true));
   }
 }
 
 // Handle both BranchInst and SelectInst.
 template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
 
   // Handle non-optimized IR code like:
   //   %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1)
template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
 
   uint32_t LikelyBranchWeightVal, UnlikelyBranchWeightVal;
   std::tie(LikelyBranchWeightVal, UnlikelyBranchWeightVal) =
       getBranchWeight(Fn->getIntrinsicID(), CI, 2);
 
   SmallVector<uint32_t, 4> ExpectedWeights;
   if ((ExpectedValue->getZExtValue() == ValueComparedTo) ==
       (Predicate == CmpInst::ICMP_EQ)) {
-    Node =
-        MDB.createBranchWeights(LikelyBranchWeightVal, UnlikelyBranchWeightVal);
+    Node = MDB.createBranchWeights(
+        LikelyBranchWeightVal, UnlikelyBranchWeightVal, /*IsExpected=*/true);
     ExpectedWeights = {LikelyBranchWeightVal, UnlikelyBranchWeightVal};
   } else {
-    Node =
-        MDB.createBranchWeights(UnlikelyBranchWeightVal, LikelyBranchWeightVal);
+    Node = MDB.createBranchWeights(UnlikelyBranchWeightVal,
+                                   LikelyBranchWeightVal, /*IsExpected=*/true);
     ExpectedWeights = {UnlikelyBranchWeightVal, LikelyBranchWeightVal};
   }
 
   if (CmpI)
     CmpI->setOperand(0, ArgValue);
   else
     BSI.setCondition(ArgValue);
 

llvm/lib/Transforms/Utils/Local.cpp

for (auto I = SI->case_begin(), E = SI->case_end(); I != E;) {
         break;
       }
 
       // Check to see if this branch is going to the same place as the default
       // dest.  If so, eliminate it as an explicit compare.
       if (I->getCaseSuccessor() == DefaultDest) {
         MDNode *MD = getValidBranchWeightMDNode(*SI);
         unsigned NCases = SI->getNumCases();
+        // Collect branch weights into a vector.
+        SmallVector<uint32_t> Weights;
         // Fold the case metadata into the default if there will be any branches
         // left, unless the metadata doesn't match the switch.
         if (NCases > 1 && MD) {
           // Collect branch weights into a vector.
           SmallVector<uint32_t, 8> Weights;
           extractBranchWeights(MD, Weights);
 
           // Merge weight of this case to the default weight.
           unsigned Idx = I->getCaseIndex();
           // TODO: Add overflow check.
           Weights[0] += Weights[Idx+1];
           // Remove weight for this case.
           std::swap(Weights[Idx+1], Weights.back());
           Weights.pop_back();
-          SI->setMetadata(LLVMContext::MD_prof,
-                          MDBuilder(BB->getContext()).
-                          createBranchWeights(Weights));
+          SI->setMetadata(
+              LLVMContext::MD_prof,
+              MDBuilder(BB->getContext())
+                  .createBranchWeights(Weights, hasExpectedProvenance(MD)));
         }
         // Remove this entry.
         BasicBlock *ParentBB = SI->getParent();
         DefaultDest->removePredecessor(ParentBB);
         I = SI->removeCase(I);
         E = SI->case_end();
 
         // Removing this case may have made the condition constant. In that

llvm/lib/Transforms/Utils/MisExpect.cpp

 
 // Command line option to enable/disable the warning when profile data suggests
 // a mismatch with the use of the llvm.expect intrinsic
 static cl::opt<bool> PGOWarnMisExpect(
     "pgo-warn-misexpect", cl::init(false), cl::Hidden,
     cl::desc("Use this option to turn on/off "
              "warnings about incorrect usage of llvm.expect intrinsics."));
 
+// Command line option for setting the diagnostic tolerance threshold
 static cl::opt<uint32_t> MisExpectTolerance(
     "misexpect-tolerance", cl::init(0),
-    cl::desc("Prevents emiting diagnostics when profile counts are "
+    cl::desc("Prevents emitting diagnostics when profile counts are "
              "within N% of the threshold.."));
 
 } // namespace llvm
 
 namespace {
 
 bool isMisExpectDiagEnabled(LLVMContext &Ctx) {
   return PGOWarnMisExpect || Ctx.getMisExpectWarningRequested();
Instruction *getInstCondition(Instruction *I) {
   // TODO: Find a way to resolve condition location for switches
   // Using the condition of the switch seems to often resolve to an earlier
   // point in the program, i.e. the calculation of the switch condition, rather
   // than the switch's location in the source code. Thus, we should use the
   // instruction to get source code locations rather than the condition to
   // improve diagnostic output, such as the caret. If the same problem exists
   // for branch instructions, then we should remove this function and directly
   // use the instruction
-  //
   else if (auto *S = dyn_cast<SwitchInst>(I)) {
     Ret = dyn_cast<Instruction>(S->getCondition());
   }
   return Ret ? Ret : I;
 }
 
 void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx,
                              uint64_t ProfCount, uint64_t TotalCount) {
void verifyMisExpect(Instruction &I, ArrayRef<uint32_t> RealWeights,
   const uint64_t RealWeightsTotal =
       std::accumulate(RealWeights.begin(), RealWeights.end(), (uint64_t)0,
                       std::plus<uint64_t>());
   const uint64_t NumUnlikelyTargets = RealWeights.size() - 1;
 
   uint64_t TotalBranchWeight =
       LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets);
 
-  // FIXME: When we've addressed sample profiling, restore the assertion
-  //
-  // We cannot calculate branch probability if either of these invariants aren't
-  // met. However, MisExpect diagnostics should not prevent code from compiling,
-  // so we simply forgo emitting diagnostics here, and return early.
-  // assert((TotalBranchWeight >= LikelyBranchWeight) && (TotalBranchWeight > 0)
-  //              && "TotalBranchWeight is less than the Likely branch weight");
-  if ((TotalBranchWeight == 0) || (TotalBranchWeight <= LikelyBranchWeight))
-    return;
+  // Failing this assert means that we've either got corrupted metadata, that
+  // we're checking stale or manually inserted branch weights, or that branch
+  // weights are being added multiple times, as is the case for SampleProfiling
+  // under ThinLTO. We gate all known entry paths to verifyMisExpect() by first
+  // checking for the presence of the "expected" tag in the metadata, which is
+  // *only* added in the LowerExpectIntrinsic Pass, avoiding a false positive.
+  assert((TotalBranchWeight >= LikelyBranchWeight) && (TotalBranchWeight > 0) &&
+         "TotalBranchWeight is less than the Likely branch weight");
 
   // To determine our threshold value we need to obtain the branch probability
   // for the weights added by llvm.expect and use that proportion to calculate
   // our threshold based on the collected profile data.
   auto LikelyProbablilty = BranchProbability::getBranchProbability(
       LikelyBranchWeight, TotalBranchWeight);
 
   uint64_t ScaledThreshold = LikelyProbablilty.scale(RealWeightsTotal);
void verifyMisExpect(Instruction &I, ArrayRef<uint32_t> RealWeights,
   // When the profile weight is below the threshold, we emit the diagnostic
   if (ProfiledWeight < ScaledThreshold)
     emitMisexpectDiagnostic(&I, I.getContext(), ProfiledWeight,
                             RealWeightsTotal);
 }
 
 void checkBackendInstrumentation(Instruction &I,
                                  const ArrayRef<uint32_t> RealWeights) {
+  if (!hasExpectedProvenance(I))
+    return;
   SmallVector<uint32_t> ExpectedWeights;
   if (!extractBranchWeights(I, ExpectedWeights))
     return;
   verifyMisExpect(I, RealWeights, ExpectedWeights);
 }
 
 void checkFrontendInstrumentation(Instruction &I,
                                   const ArrayRef<uint32_t> ExpectedWeights) {

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 
 /// Get Weights of a given terminator, the default weight is at the front
 /// of the vector. If TI is a conditional eq, we need to swap the branch-weight
 /// metadata.
 static void GetBranchWeights(Instruction *TI,
                              SmallVectorImpl<uint64_t> &Weights) {
   MDNode *MD = TI->getMetadata(LLVMContext::MD_prof);
   assert(MD);
-  for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) {
+  // TODO: this should just use extractBranchWeights(), but a lot of this code
+  // assumes uint64_t
+  auto Offset = getBranchWeightOffset(MD);
+  for (unsigned i = Offset, e = MD->getNumOperands(); i < e; ++i) {
     ConstantInt *CI = mdconst::extract<ConstantInt>(MD->getOperand(i));
     Weights.push_back(CI->getValue().getZExtValue());
   }
 
   // If TI is a conditional eq, the default case is the false case,
   // and the corresponding branch-weight data is at index 2. We swap the
   // default weight to be the first entry.
   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {

llvm/test/Transforms/LowerExpectIntrinsic/basic.ll

define i32 @test10(i64 %t6) {
   %t9 = select i1 %t8, i32 1, i32 2
 ; CHECK: select{{.*}}, !prof !1
   ret i32 %t9
 }
 
 
 declare i1 @llvm.expect.i1(i1, i1) nounwind readnone
 
-; CHECK: !0 = !{!"branch_weights", i32 2000, i32 1}
-; CHECK: !1 = !{!"branch_weights", i32 1, i32 2000}
-; CHECK: !2 = !{!"branch_weights", i32 1, i32 1, i32 2000}
-; CHECK: !3 = !{!"branch_weights", i32 2000, i32 1, i32 1}
+; CHECK: !0 = !{!"branch_weights", !"expected", i32 2000, i32 1}
+; CHECK: !1 = !{!"branch_weights", !"expected", i32 1, i32 2000}
+; CHECK: !2 = !{!"branch_weights", !"expected", i32 1, i32 1, i32 2000}
+; CHECK: !3 = !{!"branch_weights", !"expected", i32 2000, i32 1, i32 1}

llvm/test/Transforms/LowerExpectIntrinsic/expect-with-probability.ll

define i32 @test10(i64 %t6) {
   %t9 = select i1 %t8, i32 1, i32 2
 ; CHECK: select{{.*}}, !prof !1
   ret i32 %t9
 }
 
 
 declare i1 @llvm.expect.with.probability.i1(i1, i1, double) nounwind readnone
 
-; CHECK: !0 = !{!"branch_weights", i32 1717986918, i32 429496731}
-; CHECK: !1 = !{!"branch_weights", i32 429496731, i32 1717986918}
-; CHECK: !2 = !{!"branch_weights", i32 214748366, i32 214748366, i32 1717986918}
-; CHECK: !3 = !{!"branch_weights", i32 1717986918, i32 214748366, i32 214748366}
+; CHECK: !0 = !{!"branch_weights", !"expected", i32 1717986918, i32 429496731}
+; CHECK: !1 = !{!"branch_weights", !"expected", i32 429496731, i32 1717986918}
+; CHECK: !2 = !{!"branch_weights", !"expected", i32 214748366, i32 214748366, i32 1717986918}
+; CHECK: !3 = !{!"branch_weights", !"expected", i32 1717986918, i32 214748366, i32 214748366}

llvm/test/Transforms/LowerExpectIntrinsic/expect_nonboolean.ll

 attributes #0 = { nounwind uwtable }
 attributes #1 = { nounwind readnone }
 
 !llvm.module.flags = !{!0}
 !llvm.ident = !{!1}
 
 !0 = !{i32 1, !"wchar_size", i32 4}
 !1 = !{!"clang version 5.0.0 (trunk 304373)"}
-; CHECK: [[LIKELY]] = !{!"branch_weights", i32 2000, i32 1}
-; CHECK: [[UNLIKELY]] = !{!"branch_weights", i32 1, i32 2000}
+; CHECK: [[LIKELY]] = !{!"branch_weights", !"expected", i32 2000, i32 1}
+; CHECK: [[UNLIKELY]] = !{!"branch_weights", !"expected", i32 1, i32 2000}
 

llvm/test/Transforms/LowerExpectIntrinsic/phi_merge.ll

 declare i8 @too8()
 
 ; Function Attrs: nounwind readnone
 declare i64 @llvm.expect.i64(i64, i64)
 
 !llvm.ident = !{!0}
 
 !0 = !{!"clang version 5.0.0 (trunk 302965)"}
-; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 2000, i32 1}
-; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 1, i32 2000}
+; CHECK: [[WEIGHT]] = !{!"branch_weights", !"expected", i32 2000, i32 1}
+; CHECK: [[WEIGHT2]] = !{!"branch_weights", !"expected", i32 1, i32 2000}

llvm/test/Transforms/LowerExpectIntrinsic/phi_or.ll

 declare i32 @hoo()
 declare i64 @llvm.expect.i64(i64, i64)
 
 
 !llvm.ident = !{!0}
 
 
 !0 = !{!"clang version 5.0.0 (trunk 302965)"}
-; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 2000, i32 1}
-; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 1, i32 2000}
+; CHECK: [[WEIGHT]] = !{!"branch_weights", !"expected", i32 2000, i32 1}
+; CHECK: [[WEIGHT2]] = !{!"branch_weights", !"expected", i32 1, i32 2000}

llvm/test/Transforms/LowerExpectIntrinsic/phi_tern.ll

 declare i64 @llvm.expect.i64(i64, i64)
 
 
 
 !llvm.ident = !{!0}
 
 !0 = !{!"clang version 5.0.0 (trunk 302965)"}
 
-; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 1, i32 2000}
+; CHECK: [[WEIGHT]] = !{!"branch_weights", !"expected", i32 1, i32 2000}

llvm/test/Transforms/LowerExpectIntrinsic/phi_unexpect.ll

 block4:
   call void @foo()
   br label %block5
 
 block5:
   ret void
 }
 
-; CHECK: !0 = !{!"branch_weights", i32 2147483647, i32 1}
-; CHECK: !1 = !{!"branch_weights", i32 1, i32 2147483647}
+; CHECK: !0 = !{!"branch_weights", !"expected", i32 2147483647, i32 1}
+; CHECK: !1 = !{!"branch_weights", !"expected", i32 1, i32 2147483647}