[clang-misexpect] suggest __builtin_expect placement

[nickdesaulniers]

@ilovepi, @petrhosek , and I had a discussion yesterday about the possibility for clang-misexpect or clang itself suggesting the placement of __builtin_expect in sources when give profile data, such that layout related optimization could result regardless of the presence of profile data. Filing a feature request to track this.

[ilovepi]

Thanks for filing this. I'll start looking into the required changes.

As a rough outline, I think we can adapt the logic already present in the MisExpect diagnostics to emit a suggestion when the branch doesn't come from an expect intrinsic, but exceeds the hotness threshold. For now, I think we should only expose reports for missing branch weights through ORE, since I expect there to be a large volume of these cases on average. Bulk diagnostics like this I think would be more useful from a machine readable output like JSON or YAML vs. the warnings we emit for MisExpect. We can evaluate if the same style of warning would be useful later.

Given that this is a second type of PGO related diagnostic, I think we we should consider how we interface with profiling based diagnostics, and perhaps provide a common entry point for for MisExpect and other similar checks. That will greatly improve our ability to add new ways to introspect on PGO data in the future.

This also makes some of the cleanups consolidating how we process common MD_prof data like "branch_weights" a priority.

[ilovepi]

I'm prototyping this in https://reviews.llvm.org/D129889

The current prototype emits remarks for PGO profiles only. I'll need to implement similar checking for Sample Profiles once we handle MisExpect more correctly in that case.

Frontend profiles are more challenging. I'll need to look at LowerExpectIntrinsic to see if there is a good place to add these checks, since IIRC it filters out uninteresting branch/switch conditions(i.e, those w/o llvm.expect intrinsics) early before most of the useful checks/processing for the branches is done. It may be simple to support, but I'd have to check, and I have a feeling it's slightly more complex than the inserting checks the same way we do for PGO of Sample Profiles.

Another note is that the prototype is just that, a prototype. I don't intend for these checks to live in MisExpect.cpp, and I'd like to take think about the design here, since there are now two different diagnostics that would like to examine branch_weights and the interactions w/ llvm.expect intrinsics.

[nickdesaulniers]

Side note: it might be a problem if this feature suggests the use of hot and cold attributes if those would be case statements in a switch, or labels, if we don't support those attributes on those statements: #46831

[ilovepi]

Thanks for pointing that out. I’ll keep this interaction in mind as the work continues. I think we’ll be fine as long as we stick to suggestions about llvm.expect. They’re already used switch statements and most types of control flow. I’ll need to check on goto though.

On Fri, Jul 15, 2022 at 12:10 PM Nick Desaulniers ***@***.***> wrote: Side note: it might be a problem if this feature suggests the use of hot and cold attributes if those would be case statements in a switch, or labels, if we don't support those attributes on those statements: #46831 <#46831> — Reply to this email directly, view it on GitHub <#56502 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABBCPR3LLZB2RJ5TYRMFZPDVUGZQJANCNFSM53MUKKMQ> . You are receiving this because you were assigned.Message ID: ***@***.***>

-- Paul Kirth

[nickdesaulniers]

They’re already used switch statements

We can express that various cases of a switch are hot?

[ilovepi]

llvm.expect lets you describe a specific value as the expected value. So if you use it in a switch, then that arm of the switch will be marked hot, and all the others as cold. I'd have to look and see if there is another way to only mark some parts as cold.

[nickdesaulniers]

Sorry, I meant in C, not LLVM IR. If misexpect tells you one case is hot, I wonder how we express that in C. (I don't think we can, ATM).

[ilovepi]

sorry, I wasn't clear either. you can use __builtin_expect(...) if you know one branch has should be prioritized. __builtin_expect will be inserted into llvm IR as an llvm.expect intrinsic.

As an example from our tests for misexpect in clang:

llvm-project/clang/test/Profile/misexpect-switch-default.c

Line 23 in d11ac96

switch (__builtin_expect(condition, 6)) { // expected-warning-re {{Potential performance regression from use of __builtin_expect(): Annotation was correct on {{.+}}% ({{[0-9]+ / [0-9]+}}) of profiled executions.}}

For telling the compiler switch arms A,B, & C are cold, but D, E, F & G are unknown or equally hot is the case I don't know how to express at the C level. If we start supporting the GCC syntax for hot/cold annotations outside of functions(as in the issue you linked), then we'll need to wire up some way to get the branch weights set correctly. That would also significantly complicate the checking we do in MisExpect, so I'm not too bullish on that idea purely for selfish reasons.