RFC: Update `branch_weights` metadata to allow tracking branch weight origins


Some types of diagnostics and analysis we provide in LLVM need to understand not just what values branch_weight metadata contains, but also where it came from. Specifically, the MisExpect[1] diagnostics need to know if branch_weight metadata originates from an llvm.expect intrinsic. Without that information, we redundantly check the same branch multiple times in the case of ThinLTO + SampleProfiling[2]. This can lead to some inaccuracy in how we report MisExpect related diagnostics to users, since we cannot disambiguate a branchweight added during Pre-Link LTO from one added by an llvm.expect.* intrinsic. It is also the case that Clang may add branch weights, which we would like to exclude from our analysis, such as weights added for initialization code, CFI, and other types of instrumentation. Because the weights look the same in IR, our analysis cannot distinguish between these cases, and we end up with false positives[3].

Further, there is already interest in extending support for this type of profile guided analysis. For example suggesting locations where adding __builtin_expect() would be profitable[4] or to identify when noinline functions are marked hot[5].


I propose that we update MD_prof metadata for branch weights to have an optional field that denotes if the branch weights were added via llvm.expect or llvm.expect.with.probability intrinsics. This would allow us to track the origins of the weights with more fidelity. The proposed change would leave other types of MD_prof metadata, like Value Profiling metadata, unchanged.

The new MD_prof metadata for branch weights would have the following format with an optional MDString field following the branch_weights moniker:

!0 = !{
  [ !"expected", ]

  !0 = !{
  [ !"expected", ]
  [ , i32 <CASE_BRANCH_WEIGHT> ... ]


There are other ways we could go about this. An obvious approach is to use a separate piece of metadata. This requires no change to the metadata format, but has some significant downsides. First, the additional metadata would need to be kept in sync with the branch_weights through a number of compiler transformations. This is notoriously difficult and was a mistake we made in the earliest versions of MisExpect.

Another way would be to infer how the weights were added through some type of analysis. This approach seems appealing, but conducting an analysis like this seems brittle and error prone. At best we would have a crude heuristic for something the compiler could know exactly. Relying on analysis also has to cope with the variety of changes that compiler transforms may make to the existing branch weights, including scaling.


Adding an optional field to branch weights seems like a more appealing choice than adding a separate metadata type, since it can be challenging to keep multiple types of metadata in sync through the various compiler passes. If new types of analysis would benefit from a similar annotation, such as demarking when a weight originates from a profile or were inferred by the compiler, they can use the new layout without requiring future changes to the metadata.

By making the field optional, we don’t need to change much in terms of our testing or make many changes to the LLVM code base. Tests in the LLVM codebase are largely unaffected, since only tests that use llvm.expect* intrinsics will be impacted and the existing textual and bitcode representations of the metadata will be valid. Most of the code changes can be limited to the ProfDataUtils library[6], the LowerExpectIntrisicsPass, and to any analysis that would consume the additional information.


Changes to metadata come with a cost. With this modification MD_prof metadata for branch weights will be larger in some cases. Generally the number of llvm.expect intrinsics is small compared to the number of blocks that carry branch weight metadata, but this change will still increase its size. There is also some computational cost. Since the new field is optional we have to check if it exists when processing branch weights.

The other obvious concern is that downstream projects may need to adjust their handling of MD_prof metadata if they encounter the new layout. I believe most of the challenges here can be addressed by our existing APIs for dealing with branch weights and auto-upgrading the IR, but that still may require adjustments for downstream consumers.

A prototype implementation can be found in ⚙ D131306 [llvm][misexpect] Track provenance of branch weights, which will require a rebase and/or a move to Github PRs, but the overall changes should be very close to what would still be required today.


[1] Misexpect — Clang 18.0.0git documentation
[2] https://github.com/llvm/llvm-project/blob/f027dd55f32a3c1803fc3cbd53029acee849465c/llvm/lib/Transforms/IPO/SampleProfile.cpp#L1749
[3] ⚙ D115907 [misexpect] Re-implement MisExpect Diagnostics
[4] ⚙ D131306 [llvm][misexpect] Track provenance of branch weights
[5] ⚙ D132186 Clang: Add a new flag Wmisnoinline for printing hot noinline functions
[6] https://github.com/llvm/llvm-project/blob/main/llvm/lib/IR/ProfDataUtils.cpp

CC: @teresajohnson @jdoerfert @petrhosek @nickdesaulniers @sstefan

This would be an useful piece of information to keep in the IR.


I also think this is useful information to have. Some additional use-cases that come to my mind:

  • We had some discussions here about the benefits of weights actually representing “edge counts” (execution count which they do represent immediate after loading a profile) or just “probabilities”. Edge counts may help verifying and repairing profiles between passes and in that scenario it would be neat to have a way to differentiate between those two interpretations.
  • A marker that differentiates between weights originating from a profile from ones that are just best-effort guesses by transformations may also be useful.

On the implementation side I wonder though whether a fixed position for the origin that could be null rather than an optional field would be worth it to keep things simple. I guess it depends a bit whether eventually we expect this origin field to be present in the majority of cases or not.

@MatzeB The hope was that the new format would be flexible, and make it easy to support new cases, but we weren’t sure how many would be useful outside of MisExpect, and therefore wanted to limit the scope as much as possible, so we could avoid (to some extent) the need to impact users not interested in the analysis or requiring a large effort to update IR tests.

The use-cases you pointed out are interesting, though, and I hadn’t given them too much thought. Indeed, I think some of the work you’ve been doing could benefit from making those distinctions, so I’m glad there’s further interest in the proposal.

Changes to metadata come with a cost.

I don’t have a good sense to the tradeoffs involved with modifying existing metadata forms.

From a read of your Motivation section “add new metadata” is what immediately came to mind, so your Proposal matches what additions I would have expected.

On the implementation side I wonder though whether a fixed position for the origin that could be null rather than an optional field would be worth it to keep things simple.

@ilovepi any thoughts on the tradeoffs wrt that suggestion? Is it possible to implement as @MatzeB suggests? Is it simpler, better, or worse?

@ilovepi any thoughts on the tradeoffs wrt that suggestion? Is it possible to implement as @MatzeB suggests? Is it simpler, better, or worse?

I think making it optional is a better tradeoff, for a few reasons. The biggest is that we don’t have to update all tests w/ branchweights to match the new format. The second is that most code wont use the metadata. If its an optional field, the only cost is minor bookkeeping when using ProfDataUtils, and even when we want to use the new field, we don’t need to keep it around forever, so space is minimally better. The space motivation is a bit weak in my opinion, but I’ve seen some pushback on increasing metadata size generally, so I think this is a good tradeoff.

As for feasibility: yes, a nullable field could work. It has the nice property that there isn’t any special handling, since that field is always present, but may be null. As @MatzeB mentioned, whether that’s worth it or not is correlated to how frequently its expected to be present. For the current motivation (e.g., MisExpect), I don’t think most metadata would end up setting anything. We’re interested in tagging the origin as being from an llvm.expect* intrinsic, so I would expect that to only be a small percentage of the branches in a typical program. Additionally, I don’t expect most typical users will need/want these types of analysis by default, so the total percentage is even smaller, which is one of the reasons we went with an optional field.