Page MenuHomePhabricator

[clang] [CodeGen] clang-misexpect prototype for compiler warnings
AbandonedPublic

Authored by paulkirth on Jul 25 2019, 2:38 PM.

Details

Summary

Overview:
This patch contains a prototype of the basic functionality of clang-misexpect in the PGO pipeline. clang-misexpect is a proposed clang-tool that can report 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)

This patch adds the basic checking mechanisms to the compiler in the CodeGen library as a set of warnings usable when compiling with PGO. Once the logic in this patch is verified, it can be used to as the basis for a standalone tool.

This patch adds a new flag -fmisexpect to clang, and adds additional checks for branches and switch statements when branch weights are assigned in clang/lib/CodeGen/CodeGenFunction.cpp & clang/lib/CodeGen/CGStmt.cpp.

The bulk of the checking logic is implemented in clang/lib/CodeGen/MisExpect.cpp. It has some minor changes to some of the logic in CGStmt.cpp to properly map the profiling counters to their concrete values in the case statements for switches.

The patch also provides a number of lit based tests for various usage of __builtin_expect() for branches and switch statements.

Details:

The strategy for MisExpect checks is straightforward: when __builtin_expect() is used, then compare the relevant profile counter against a threshold value, and emit a warning if we've found a mismatch (i.e. the profile counter is outside the acceptable range).

For conditional statements this is simple. We can determine whether the profile count agrees with the annotation via direct comparison w/ the appropriate hot/cold thresholds.

For switch statements the situation is slightly more complex due to the way profiling counters are assigned.

Each case statement in the switch body will get its own counter, except when the cases are empty fall-throughs, in which case they will share a counter.

So, in the case where:

switch(x){
case 1:
case 2:
  break;
case default:
  break;
};

Here, values 1 & 2 will share a single counter, and all other cases will share a counter for the default case.

However, in the following example:

switch(x){
case 1:
 x = x+1;
case 2:
  break;
case default:
  break;
};

In the example above, values 1 & 2 will each have their own profiling counter instead of sharing one, even though case 1 falls through to case 2. The default case stays the same with a shared counter for every value not present in the switch body.

To be align with developer expectations we treat these empty fall-throughs conservatively for the purpose of generating warnings, i.e. if the expected value results in the hottest branch being executed we will not emit the warning, even though the strict semantics of __builtin_expect() are slightly different. We support this by maintaining a mapping from the concrete value in the switch arm back to its relevant profile counter.

In the case where the profile counters are not shared, we always do a direct check using the relevant profile counter.

Right now MisExpect only ensures that the hottest arm of the switch statement is the one the developer chosen, without reference to any particular threshold. It is arguable that we should have an additional check against a threshold, similar to what is done for conditional statements.

Heuristics:
For branch 'hotness' I have switched from using the existing thresholds for determining FFA_Hot/FFA_Cold function annotations to using the same branch probability that LLVM asigns when lowerin the __builtin_expect intrinsic (see LowerExpectIntrinsic.cpp for more details). The weight is roughly 2000:1, which is heavily skewed, and may be a bit too tight for practical use. This however is a reasonable default, and the threshold can be exposed through a compiler option. Feedback on a more appropriate set of threshold values is welcome and desirable.

Diff Detail

Event Timeline

paulkirth created this revision.Jul 25 2019, 2:38 PM
paulkirth updated this revision to Diff 211831.Jul 25 2019, 2:59 PM

Refactors some debug code to be more centralized and cleans up some comments.

Nice work!

It would be nice if we also have “-fsuggest-expect” so we could fix perf issues thanks to PGO counters even for non-PGO builds. What do you think?

Nice work!

Glad to hear you like it.

It would be nice if we also have “-fsuggest-expect” so we could fix perf issues thanks to PGO counters even for non-PGO builds. What do you think?

Supporting suggestions is something we're planning to do in the future. Non-PGO builds are even the main motivation. I wanted to get this logic correct first, and make sure that we're handling all the odd edge cases before making new suggestions. I feel like our approach is really straightforward, but some things in clang are spread out in surprising ways or have interactions I've been surprised to find. That said, if finding problematic usage is done correctly, then reversing the logic to make a suggestions about useful annotations should be pretty easy.

I still need to give some thought to how to express the right balance between execution count and frequency when suggesting new annotations, so that the user won't be overwhelmed with suggestions. I'm not sure that branch weights by themselves are sufficient for that use-case, but we should be able to come up with something that behaves reasonably well without too much trouble.

paulkirth updated this revision to Diff 211853.Jul 25 2019, 4:21 PM

Add missing test for switch statements when the expected value is not a compile time constant.

Make sure that when the expected value cannot be evaluated, we do not issue any warnings or errors

paulkirth updated this revision to Diff 212492.Jul 30 2019, 7:14 PM

Update diff to have proper context on Phabricator

phosek added inline comments.Jul 30 2019, 7:41 PM
clang/lib/CodeGen/MisExpect.cpp
30

It seems like DebugPrintMisExpectSwitchInfo and EmitMisExpectWarning is only used within this file, so I'd move them to anonymous namespace.

75

No space between : and \t here and below.

83

Are these thresholds defined anywhere as constants?

95

No need for { and }.

123

No need for { and }, in this case you can probably just use ternary expression.

134

No need for { and }.

clang/lib/CodeGen/MisExpect.h
11

for validation or to validate?

35

s/__builting_expect/__builtin_expect/

37

extra empty line

41

s/__builting_expect/__builtin_expect/

leonardchan accepted this revision.Jul 30 2019, 7:47 PM

LGTM but I'd wait a day to see if anyone else has comments they'd like to add before landing.

This revision is now accepted and ready to land.Jul 30 2019, 7:47 PM
lebedev.ri requested changes to this revision.Jul 31 2019, 4:42 AM

Thank you for working on this!

I'm guessing this doesn't have a -Werror= mode?

I still believe this should output a remark.
It will still be visible in the compiler console output,
but won't get buried there but will actually be recorded in the remarks file.

clang/lib/CodeGen/MisExpect.cpp
2

Wrong comment

37

llvm::None

41

llvm::None

51

llvm::None

55

return ExpectedVal;
should just work?

141–147

This is rather undescriptive.
Can you output some more useful info?

clang/lib/CodeGen/MisExpect.h
2

Wrong comment

This revision now requires changes to proceed.Jul 31 2019, 4:42 AM
paulkirth updated this revision to Diff 213059.Aug 2 2019, 9:17 AM
paulkirth marked 2 inline comments as done.

Fix typo in comments

paulkirth marked 2 inline comments as done.Aug 2 2019, 11:30 AM
paulkirth added inline comments.
clang/lib/CodeGen/MisExpect.cpp
83

These thresholds come from PGOInstrumentation.cpp:1084

I will update with a reference to the code that this comes from, but, as noted in the TODO we need a better heuristic.

141–147

Do you have a suggestion about what feedback would be more useful?

My initial thought with the somewhat generic message was to simply point out that this usage looked problematic, and let the developer investigate. I wasn't sure we wanted to expose details of the internal heuristic to the user by reporting the internal thresholds.

xbolva00 added inline comments.Aug 2 2019, 11:42 AM
clang/lib/CodeGen/MisExpect.cpp
141–147

Message is currently confusing a bit. I really miss clear info like

“This compiler hint seems to be incorrect according to current PGO counters. Please check the hint if it is still valid and perf-profitable”.

paulkirth updated this revision to Diff 213164.Aug 2 2019, 7:19 PM

Address feedback from review

  1. Fixed comments in License headers
  2. removed excess {}
  3. Changed conditional assignment to ternary operation
  4. Moved local functions into anonymous namespace
  5. Added reference to the origin of the threshold values in the clang source code
  6. Updated warning to have more useful text
  7. Fixed whitespace
  8. Updated unqualified use of llvm::None
  9. Updated tests with new warning text
paulkirth marked 12 inline comments as done.Aug 2 2019, 7:21 PM
paulkirth updated this revision to Diff 213167.Aug 2 2019, 7:38 PM

Update documentation and fix typos

paulkirth marked 2 inline comments as done.Aug 2 2019, 7:40 PM
paulkirth updated this revision to Diff 213379.Aug 5 2019, 9:25 AM
paulkirth edited the summary of this revision. (Show Details)

Update threshold values to match those assigned when lowering __builtin_expect intrinsic.

I've modified the branch probability to match the probability assigned in LowerExpectIntrinsics.cpp

This is still debatable, but seems like a reasonable default. My next patch will make the probability threshold assignable through the command line, and extend the probability calculation into switch statements. This way users can determine how hot is hot enough, and otherwise get the same behavior that builtin expect will use anyway.

I also re applied a fix to a typo that I overwrote in an earlier patch.

Thank you for working on this!

I'm guessing this doesn't have a -Werror= mode?

I still believe this should output a remark.
It will still be visible in the compiler console output,
but won't get buried there but will actually be recorded in the remarks file.

“Clang supports -R flags for enabling remarks. These are diagnostic messages that provide information about the compilation process, but don’t suggest that a problem has been detected.”

I think this patch is okay.

paulkirth updated this revision to Diff 213725.Aug 6 2019, 2:54 PM

Use existing LLVM code for mapping case literals to their case arms.

This update refactors a great deal of the implementation and test code.

  1. Removes the CaseMap data structure completely. LLVM already maintains a mapping of the constants to their case arm, so there is no reason to duplicate that logic. This also minimizes the changes impacting existing Clang/LLVM components.
  2. Cleans up debug printing. Without the CaseMap printing debug output can be simplified.
  3. Minimizes the code in the end-to-end tests & test profiles.
  4. Improves formatting, white space, and comments.

Please can you clarify hat's the current layout of these patches?
Is this patch required, or is it superseded by D66324 (and thus should be abandoned)?
I'd like to begin reviewing, but i don't understand where to start.

Please can you clarify hat's the current layout of these patches?
Is this patch required, or is it superseded by D66324 (and thus should be abandoned)?
I'd like to begin reviewing, but i don't understand where to start.

Sorry for the confusion. D66324 should supersede this patch. It re-implements everything in the backend, and adds support for IR & Sample based profiles, so I think it is safe to ignore this patch for now.

Is there something I should do to mark/change the patches?

Also, thanks for the feedback.

Please can you clarify hat's the current layout of these patches?
Is this patch required, or is it superseded by D66324 (and thus should be abandoned)?
I'd like to begin reviewing, but i don't understand where to start.

Sorry for the confusion. D66324 should supersede this patch.

Okay, i'll be reviewing that one then.

It re-implements everything in the backend, and adds support for IR & Sample based profiles, so I think it is safe to ignore this patch for now.

Is there something I should do to mark/change the patches?

Please abandon this patch to make it obvious (Add Action -> Abandon)

Also, thanks for the feedback.

paulkirth abandoned this revision.Tue, Aug 27, 2:32 PM

This is being abandoned in favor of D66324, which reimplements this logic completely in the LLVM backend.