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.
Wrong comment