Motivation
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].
Proposal
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:
BranchInst:
!0 = !{
!"branch_weights",
[ !"expected", ]
i32 <TRUE_BRANCH_WEIGHT>,
i32 <FALSE_BRANCH_WEIGHT>
}
SwitchInst:
!0 = !{
!"branch_weights",
[ !"expected", ]
i32 <DEFAULT_BRANCH_WEIGHT>
[ , i32 <CASE_BRANCH_WEIGHT> ... ]
}
Alternatives
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.
Benefits
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.
Downsides
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.
References
[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