This is an archive of the discontinued LLVM Phabricator instance.

[llvm][misexpect] Track provenance of branch weights
Needs ReviewPublic

Authored by paulkirth on Aug 5 2022, 4:40 PM.

Details

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.

Diff Detail

Event Timeline

paulkirth created this revision.Aug 5 2022, 4:40 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 5 2022, 4:40 PM
paulkirth requested review of this revision.Aug 5 2022, 4:40 PM
Herald added a reviewer: sstefan1. · View Herald Transcript
Herald added projects: Restricted Project, Restricted Project. · View Herald Transcript

@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).

@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.

@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.

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.

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.

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 added a comment.Aug 29 2022, 1:52 PM

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

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

@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 @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.

@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 @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 updated this revision to Diff 489176.Jan 13 2023, 6:06 PM

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

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).

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 updated this revision to Diff 492492.Jan 26 2023, 9:37 AM

Rebase and update lang ref

paulkirth updated this revision to Diff 492493.Jan 26 2023, 9:38 AM
paulkirth edited the summary of this revision. (Show Details)

Update summary

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 ↗(On Diff #492493)

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

397 ↗(On Diff #492493)

Should this be an assert?

llvm/lib/IR/Instructions.cpp
748

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
4571

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 added inline comments.Mar 6 2023, 2:07 PM
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 ↗(On Diff #492493)

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 ↗(On Diff #492493)

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

llvm/lib/IR/Verifier.cpp
4571

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 updated this revision to Diff 502873.Mar 6 2023, 5:33 PM
paulkirth marked 4 inline comments as done.

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 updated this revision to Diff 502875.Mar 6 2023, 5:38 PM

Remove redunant assert