Page MenuHomePhabricator

clang-misexpect: Profile Guided Validation of Performance Annotations in LLVM
ClosedPublic

Authored by paulkirth on Aug 15 2019, 5:06 PM.

Details

Summary

This patch contains the basic functionality for reporting potentially incorrect usage of __builtin_expect() by comparing the developer's annotation against a collected PGO profile. A more detailed proposal and discussion appears on the CFE-dev mailing list (http://lists.llvm.org/pipermail/cfe-dev/2019-July/062971.html) and a prototype of the initial frontend changes appear here in D65300

We revised the work in D65300 by moving the misexpect check into the LLVM backend, and adding support for IR and sampling based profiles, in addition to frontend instrumentation.

We add new misexpect metadata tags to those instructions directly influenced by the llvm.expect intrinsic (branch, switch, and select) when lowering the intrinsics. The misexpect metadata contains information about the expected target of the intrinsic so that we can check against the correct PGO counter when emitting diagnostics, and the compiler's values for the LikelyBranchWeight and UnlikelyBranchWeight. We use these branch weight values to determine when to emit the diagnostic to the user.

A future patch should address the comment at the top of LowerExpectIntrisic.cpp to hoist the LikelyBranchWeight and UnlikelyBranchWeight values into a shared space that can be accessed outside of the LowerExpectIntrinsic pass. Once that is done, the misexpect metadata can be updated to be smaller.

In the long term, it is possible to reconstruct portions of the misexpect metadata from the existing profile data. However, we have avoided this to keep the code simple, and because some kind of metadata tag will be required to identify which branch/switch/select instructions are influenced by the use of llvm.expect

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

Actually address nits

paulkirth marked 3 inline comments as done.Aug 29 2019, 8:13 PM
leonardchan accepted this revision.Aug 29 2019, 8:21 PM

Sorry about that. Still LGTM.

Trying to start reviewing this.
The llvm side of the patch is self contained; clang patch should be split into a dependent review.

clang/lib/CodeGen/CodeGenAction.cpp
626 ↗(On Diff #218017)

This should be BadDebugInfoLoc (in getBestLocationFromDebugLoc() too)

clang/lib/CodeGen/CodeGenFunction.cpp
28–1361 ↗(On Diff #218017)

Dubious changes, drop

clang/lib/Frontend/CompilerInvocation.cpp
3451–3454 ↗(On Diff #218017)

Here you are checking that -Wmisexpect is passed to clang?
This doesn't seem idiomatic. Was this copied from somewhere?
Normally this is Diags.isIgnored(diag::warn_profile_data_misexpect, ???)

llvm/include/llvm/Transforms/Utils/MisExpect.h
1 ↗(On Diff #218017)

__builtin_expect() is a clang-specific thing.
Can all instances of it in all comments be reworded to be more agnostic?

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
78–87 ↗(On Diff #218017)

Why can't LLVMContext::MD_prof be reused?

82 ↗(On Diff #218017)

Why do you need to move this line?

84 ↗(On Diff #218017)

clang is not the only llvm frontend, this should not be so specific

llvm/lib/Transforms/Utils/MisExpect.cpp
30 ↗(On Diff #218017)

This doesn't look correct.

33 ↗(On Diff #218017)

<cstdint>

llvm/test/Transforms/LowerExpectIntrinsic/basic.ll
288–289 ↗(On Diff #218017)

; CHECK: !1 = ??? ?

paulkirth marked an inline comment as done.Aug 30 2019, 10:35 AM

Thanks for the review.

I'm working on splitting up the patch now.

I should be able to address most of your comments, but I left some inline comments for clarification/discussion.

clang/lib/CodeGen/CodeGenAction.cpp
626 ↗(On Diff #218017)

That should be in a separate patch, right?

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
78–87 ↗(On Diff #218017)

It didn't seem appropriate to me, but that can be changed if it is the right thing to do.

However, I don't see code elsewhere that loops over MD_prof metadata checking its tag. I see lots of examples that check if the tag matches, and then exits if it doesn't match.

If I added "misexpect" as a new MD_proftag, then code in places like extractProfTotalWeight(...) in IR/Metadata.cpp would have to be updated. I'm not sure how pervasive that pattern is, but I did want to avoid introducing systemic changes like that.

https://github.com/llvm/llvm-project/blob/9976a5bc1db5a240378a61a68c0e182060bcb554/llvm/lib/IR/Metadata.cpp#L1336

82 ↗(On Diff #218017)

I did this so that the condition is available to check when performing validation, and the metadata won't be replaced by the likely/unlikely values until after I've finished the validation. Having the condition available in when performing the check provides for better diagnostics output.

paulkirth updated this revision to Diff 218164.Aug 30 2019, 2:05 PM

Address Review items

  • minimize debug info in llvm tests
  • sanitize paths in debug info
  • use more complete checks in test for LowerExpectIntrisic
  • remove references to __builtin_expect from backend code
    • update test code for new diagnostic messages
  • rename checkClangInstrumentation to checkFrontendInstrumentation
  • revert whitespace removal in CodeGenFunction.cpp
  • use more idomatic check when adding diagnostic to the backend
paulkirth marked 7 inline comments as done and an inline comment as not done.Aug 30 2019, 2:08 PM

Trying to start reviewing this.
The llvm side of the patch is self contained; clang patch should be split into a dependent review.

Looking at this, is it necessary to split up the patch? That will loose a lot of the previous comment/context, and I'd prefer to land this as a single change. Doing so has the benefit that if my patch needs to be reverted, it can be done all together. For example, if only the llvm patch is reverted, then it will likely cause other problems and make triage needlessly painful.

paulkirth updated this revision to Diff 218168.Aug 30 2019, 2:23 PM

Remove extra include from CodeGenFunction.cpp

paulkirth updated this revision to Diff 218171.Aug 30 2019, 2:29 PM

Fix comment for misexpect option

phosek accepted this revision.Aug 30 2019, 2:56 PM

Trying to start reviewing this.
The llvm side of the patch is self contained; clang patch should be split into a dependent review.

Looking at this, is it necessary to split up the patch? That will loose a lot of the previous comment/context, and I'd prefer to land this as a single change. Doing so has the benefit that if my patch needs to be reverted, it can be done all together. For example, if only the llvm patch is reverted, then it will likely cause other problems and make triage needlessly painful.

I'd actually prefer to land this as a single change, it makes it easier to revert and look at the diff later.

Missing tests for __builtin_unpredictable().

clang/lib/CodeGen/CodeGenAction.cpp
369 ↗(On Diff #218171)

Comment missing

626 ↗(On Diff #218017)

Yeah, let's keep that for later.

clang/lib/Frontend/CompilerInvocation.cpp
3449 ↗(On Diff #218171)

Err, this works? I'd expect ! to be missing here..

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
78–87 ↗(On Diff #218017)

That's not exactly what i was asking.
I'm specifically talking about how "misexpect" and "branch_weigths" carry basically the same data,
are set basically in the same place always, with the difference that "misexpect" also has the switch case index.
This is both somewhat bloaty, and is prone to getting out of sync.

I have two questions:

  1. Can "misexpect" metadata simply not be invented, but can existing LLVMContext::MD_misexpect simply be used?
  2. Can "misexpect" be changed to not store the weights, but a reference to the LLVMContext::MD_misexpect metadata that will be emitted anyway?
llvm/test/Transforms/LowerExpectIntrinsic/basic.ll
141 ↗(On Diff #218171)

Here and elsewhere:
is !prof !1 no longer present?

292–293 ↗(On Diff #218171)

Should there be a FIXME, are some misexpect missing here?

paulkirth added inline comments.Aug 30 2019, 6:40 PM
clang/lib/Frontend/CompilerInvocation.cpp
3449 ↗(On Diff #218171)

I ran check-clang and check-llvm. Are there more tests I should be running?

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
78–87 ↗(On Diff #218017)

Sorry for the misunderstanding.

I think what you are suggesting is to recreate the misexpect metadata from the MD_prof "branch_weights metadata. Is that right?

I think that may be possible, but it will add complexity. While the metadata approach is very straightforward. I think there is value in keeping this simple, and then iterating on it.

Also, LowerExpectIntrinsic.cpp has a comment near the top suggesting that the LikelyBranchWeight and UnlikelyBranchWeights be hoisted to a common space. This would significantly shrink the size of the misexpect metadata if it were accessible directly. However, that is a change that should happen separately from this patch, and might require further discussion to find the correct shared space.

Ultimately, however, I do not see a way to completely remove some kind of metadata tag, as we only need to perform misexpect checks when the intrinsic was used -- which should be a small minority of cases. If there is another way, then I am happy to hear it, but again, maybe that should be another patch.

paulkirth marked 2 inline comments as done.Aug 30 2019, 6:56 PM
paulkirth added inline comments.
llvm/test/Transforms/LowerExpectIntrinsic/basic.ll
141 ↗(On Diff #218171)

The misexpect metadata tags take those slots.

br i1 %tobool, label %if.then, label %if.end, !prof !0, !misexpect !1

Unless my understanding of how the tags work is flawed, I think this is the expected behavior

292–293 ↗(On Diff #218171)

This is happenstance unfortunately.

; CHECK: !4 = !{!"branch_weights", i32 1, i32 2000, i32 1}
; CHECK: !5 = !{!"branch_weights", i32 2000, i32 1, i32 1}

In both of these cases the expected index is still 0 or 1, so the metadata tags are deduplicated.

If we want to check further, then we need to modify the test to select an index greater than 1.

paulkirth updated this revision to Diff 218197.Aug 30 2019, 7:03 PM

Update LowerExpectIntrinsic/basic.ll to generate misexpect metadata for a switch

paulkirth updated this revision to Diff 218198.Aug 30 2019, 7:10 PM

Add inline checks for misexpect tags to LowerExpectIntrinstic test

paulkirth updated this revision to Diff 218200.Aug 30 2019, 7:37 PM

Add clang and LLVM tests for __builtin_unpredictable

paulkirth updated this revision to Diff 219219.Sep 6 2019, 8:31 PM

Improve diagnostic output with profile counts

lebedev.ri accepted this revision.Sep 7 2019, 12:17 AM
lebedev.ri marked an inline comment as done.

Okay, thank you for the patience, this looks good to me now too.
Please update patch description/subject - this patch is not a standalone tool.

clang/test/Profile/misexpect-branch-cold.c
4 ↗(On Diff #219219)

Is there a test where -Wmisexpect isn't present, to verify that it is off-by-default?

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
78–87 ↗(On Diff #218017)

nonnull

Yes.

...

Well, alright i guess, please add a note that this was at least considered into the patch description.

llvm/test/Transforms/LowerExpectIntrinsic/basic.ll
141 ↗(On Diff #218171)

I was worried that here the !prof were no longer emitted, but only !misexpect were emitted.
This seems not to be the case, so all good i think.

paulkirth edited the summary of this revision. (Show Details)Sep 7 2019, 11:35 AM
paulkirth added inline comments.Sep 7 2019, 11:38 AM
clang/test/Profile/misexpect-branch-cold.c
4 ↗(On Diff #219219)

We can add one, but is that necessary? Don't the tests for diagnostics cover those already?

lebedev.ri added inline comments.Sep 8 2019, 4:59 AM
clang/test/Profile/misexpect-branch-cold.c
4 ↗(On Diff #219219)

To clarify: i'm interested in the case where the PGO data is provided but -Wmisexpect is *not* specified.

paulkirth marked an inline comment as done.Sep 9 2019, 12:16 PM
paulkirth added inline comments.
clang/test/Profile/misexpect-branch-cold.c
4 ↗(On Diff #219219)

Actually, this is moot. That test already exists in misexpect-branch.c: line 6.

Since that file actually has a mismatched use of __builtin_expect(), it's a better candidate anyway.

// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify=foo
This revision was automatically updated to reflect the committed changes.
paulkirth reopened this revision.Sep 10 2019, 3:24 PM
This revision is now accepted and ready to land.Sep 10 2019, 3:24 PM
paulkirth updated this revision to Diff 219617.EditedSep 10 2019, 3:32 PM

Add a new profdata file to use w/ misexpect-nonconst-switch.c

ASAN exposed an issue where a function may hash the same even if the number of counters is different. This means that when a PGO profile is read in, it is possible for an out of bounds write to occur due to a mismatch in the number of statements that require profile counters, and the number of counters initialized from the profile that was read in.

This change should allow the misexpect patch to reland w/o issue.

This revision was automatically updated to reflect the committed changes.
chandlerc added inline comments.
compiler-rt/trunk/lib/profile/xxhash.h
41–42 ↗(On Diff #219645)

Sorry folks, but you can't do this.

You can't depend on ADT from compiler-rt currently.

There are at least two problems here:

First problem is that this pollutes the profile library with symbols from ADT. That really doesn't seem reasonable without *significant* and invasive changes to ADT. Otherwise building LLVM and linking it with the profile library will create an ODR violation (imagine different assert levels or different versions of LLVM buing built and the host toolchain).

Second, and much more critically, we haven't gotten to 100% relicensed on ADT, so it is critical that we not depend on it from runtime libraries.

Third, a lot of this code seems to use old license headers. Please do not add any code like this to LLVM, and instead use the new LLVM license for all new code.

For now, this patch (and any related patches) need to be reverted until these are addressed. Especially the license issues.

Reverted in r371598.

Another concern that I have is cross-compilation. LLVM's ADT is not set up to be cross-compiled like the rest of compiler-rt is.

lebedev.ri added a comment.EditedSep 11 2019, 2:25 AM

Reverted in r371598.

Another concern that I have is cross-compilation. LLVM's ADT is not set up to be cross-compiled like the rest of compiler-rt is.

Uhm, i have a better question still - why xxhash is even there? it's not used in the diff, and was not reviewed, it just magically appeared in the last update of the patch:
https://reviews.llvm.org/D66324?vs=219617&id=219645

paulkirth marked an inline comment as done.Sep 11 2019, 9:01 AM
paulkirth added inline comments.
compiler-rt/trunk/lib/profile/xxhash.h
41–42 ↗(On Diff #219645)

Sorry, this looks like a mismerge somehow. My patch should't have anything from compiler-rt. I think maybe a local change got rolled in when Petr landed my patch.

phosek added inline comments.Sep 11 2019, 9:02 AM
compiler-rt/trunk/lib/profile/xxhash.h
41–42 ↗(On Diff #219645)

Sorry about that, this was my mistake, it seems two of my stales files got included in when I applied the patch locally. I'll revert the change and reland it correctly.

Reverted in r371598.

Another concern that I have is cross-compilation. LLVM's ADT is not set up to be cross-compiled like the rest of compiler-rt is.

Uhm, i have a better question still - why xxhash is even there? it's not used in the diff, and was not reviewed, it just magically appeared in the last update of the patch:
https://reviews.llvm.org/D66324?vs=219617&id=219645

It shouldn't have. My last change only modified a test file to not trigger a memory corruption bug. I'm filing a bug for that, but am waiting on a login for the bug tracker.

What I suspect happened is that when this landed some local changes got sucked in. I'm terribly sorry, it wasn't my intention to add anything significant to the patch.

paulkirth reopened this revision.Sep 11 2019, 9:05 AM
This revision is now accepted and ready to land.Sep 11 2019, 9:05 AM
paulkirth updated this revision to Diff 219728.Sep 11 2019, 9:06 AM

Revert mismerge when landing.

This revision was automatically updated to reflect the committed changes.
jrtc27 added a subscriber: jrtc27.Sep 16 2019, 9:19 AM
jrtc27 added inline comments.
llvm/trunk/include/llvm/IR/DiagnosticInfo.h
79

Is this not going to clash with the first caller to getNextAvailablePluginDiagnosticKind? DK_FirstPluginKind is special and shouldn't have anything after it.

paulkirth added inline comments.Sep 16 2019, 9:34 PM
llvm/trunk/include/llvm/IR/DiagnosticInfo.h
79

hmm, I wasn't aware of that. Is this documented somewhere? Also no tests seem to break from this, so that might be another area to address.

I'll upload a patch for this that moves the flag, and adds a note about the ordering.

paulkirth marked an inline comment as done.Sep 16 2019, 9:51 PM
paulkirth added inline comments.
llvm/trunk/include/llvm/IR/DiagnosticInfo.h
79

Please see D67648 for future reference of this defect.

wenju added a subscriber: wenju.Sep 24 2019, 12:41 AM

We see error "clang (LLVM option parsing): for the --pgo-warn-misexpect option: may only occur zero or one times!" when clang::CompilerInvocation::CreateFromArgs and clang::ExecuteCompilerInvocation are called twice.

This line: if (Diags.isIgnored(diag::warn_profile_data_misexpect, SourceLocation()))
I think it should be !Diags.isIgnored.