paulkirth created this revision.
paulkirth added reviewers: phosek, leonardchan, jakehehrlich, mcgrathr.
Herald added subscribers: cfe-commits, kristof.beyls, javed.absar, mgorny.
Herald added a project: clang.
**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've used the existing thresholds for determining
FFA_Hot/FFA_Cold function annotations. This is a dubious choice for the
thresholds, but are a suitable heuristic for the prototype. Feedback on a more
appropriate set of threshold values is welcome and desirable.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D65300
Files:
clang/include/clang/Basic/CodeGenOptions.def
clang/include/clang/Driver/Options.td
clang/lib/CodeGen/CGStmt.cpp
clang/lib/CodeGen/CMakeLists.txt
clang/lib/CodeGen/CodeGenFunction.cpp
clang/lib/CodeGen/CodeGenFunction.h
clang/lib/CodeGen/MisExpect.cpp
clang/lib/CodeGen/MisExpect.h
clang/lib/Driver/ToolChains/Clang.cpp
clang/lib/Frontend/CompilerInvocation.cpp
clang/test/Profile/Inputs/misexpect-branch-nonconst-expect-arg.proftext
clang/test/Profile/Inputs/misexpect-branch.proftext
clang/test/Profile/Inputs/misexpect-switch.proftext
clang/test/Profile/misexpect-branch-cold.c
clang/test/Profile/misexpect-branch-nonconst-expected-val.c
clang/test/Profile/misexpect-branch.c
clang/test/Profile/misexpect-no-warning-without-flag.c
clang/test/Profile/misexpect-switch-default.c
clang/test/Profile/misexpect-switch.c
Index: clang/test/Profile/misexpect-switch.c
===================================================================
--- /dev/null
+++ clang/test/Profile/misexpect-switch.c
@@ -0,0 +1,68 @@
+// Test that misexpect detects mis-annotated switch statements
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-switch.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -fmisexpect
+
+int sum(int *buff, int size);
+int random_sample(int *buff, int size);
+int rand();
+
+const int inner_loop = 1000;
+const int outer_loop = 20;
+const int arry_size = 25;
+
+int arry[arry_size] = {0};
+
+void init_arry() {
+ int i;
+ for (i = 0; i < arry_size; ++i) {
+ arry[i] = rand() % 10;
+ }
+}
+
+int main() {
+ init_arry();
+ int val = 0;
+
+ int j, k;
+ for (j = 0; j < outer_loop; ++j) {
+ for (k = 0; k < inner_loop; ++k) {
+ unsigned condition = rand() % 10000;
+ switch (__builtin_expect(condition, 0)) { //expected-warning {{Current PGO counters disagree with the use of __builtin_expect().}}
+ case 0:
+ val += sum(arry, arry_size);
+ break;
+ case 1:
+ case 2:
+ case 3:
+ case 4:
+ val += random_sample(arry, arry_size);
+ break;
+ default:
+ __builtin_unreachable();
+ } // end switch
+ } // end inner_loop
+ } // end outer_loop
+
+ return 0;
+}
+
+int sum(int *buff, int size) {
+ int total = 0;
+ int i = 0;
+ for (i = 0; i < size; ++i) {
+ total += buff[i];
+ }
+ return total;
+}
+
+int random_sample(int *buff, int size) {
+ int total = 0;
+ int i;
+ for (i = 0; i < size; ++i) {
+ if (rand() % 5 == 0)
+ total += buff[i];
+ }
+
+ return total;
+}
Index: clang/test/Profile/misexpect-switch-default.c
===================================================================
--- /dev/null
+++ clang/test/Profile/misexpect-switch-default.c
@@ -0,0 +1,68 @@
+// Test that misexpect detects mis-annotated switch statements
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-switch.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -fmisexpect
+
+int sum(int *buff, int size);
+int random_sample(int *buff, int size);
+int rand();
+
+const int inner_loop = 1000;
+const int outer_loop = 20;
+const int arry_size = 25;
+
+int arry[arry_size] = {0};
+
+void init_arry() {
+ int i;
+ for (i = 0; i < arry_size; ++i) {
+ arry[i] = rand() % 10;
+ }
+}
+
+int main() {
+ init_arry();
+ int val = 0;
+
+ int j, k;
+ for (j = 0; j < outer_loop; ++j) {
+ for (k = 0; k < inner_loop; ++k) {
+ unsigned condition = rand() % 5;
+ switch (__builtin_expect(condition, 6)) { //expected-warning {{Current PGO counters disagree with the use of __builtin_expect().}}
+ case 0:
+ val += sum(arry, arry_size);
+ break;
+ case 1:
+ case 2:
+ case 3:
+ case 4:
+ val += random_sample(arry, arry_size);
+ break;
+ default:
+ __builtin_unreachable();
+ } // end switch
+ } // end inner_loop
+ } // end outer_loop
+
+ return 0;
+}
+
+int sum(int *buff, int size) {
+ int total = 0;
+ int i = 0;
+ for (i = 0; i < size; ++i) {
+ total += buff[i];
+ }
+ return total;
+}
+
+int random_sample(int *buff, int size) {
+ int total = 0;
+ int i;
+ for (i = 0; i < size; ++i) {
+ if (rand() % 5 == 0)
+ total += buff[i];
+ }
+
+ return total;
+}
Index: clang/test/Profile/misexpect-no-warning-without-flag.c
===================================================================
--- /dev/null
+++ clang/test/Profile/misexpect-no-warning-without-flag.c
@@ -0,0 +1,51 @@
+// Test that misexpect detects mis-annotated branches
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-branch.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify
+
+// expected-no-diagnostics
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+
+int foo(int);
+int bar();
+int baz(int);
+int buzz();
+
+const int inner_loop = 100;
+const int outer_loop = 2000;
+
+int main() {
+ int val = 0;
+ for (int i = 0; i < outer_loop; ++i) {
+ for (int i = 0; i < inner_loop; ++i) {
+ val = bar();
+ }
+ }
+ return 0;
+}
+
+int bar() {
+ int rando = buzz();
+ int x = 0;
+ if (likely(rando % (outer_loop * inner_loop) == 0)) {
+ x = baz(rando);
+ } else {
+ x = foo(50);
+ }
+ return x;
+}
+
+int foo(int i) {
+ int j = 0;
+ while (i < 100) {
+ i += buzz() % 5;
+ j++;
+ }
+ return j;
+}
+
+int baz(int rando) {
+ int x = rando;
+ return x;
+}
Index: clang/test/Profile/misexpect-branch.c
===================================================================
--- /dev/null
+++ clang/test/Profile/misexpect-branch.c
@@ -0,0 +1,50 @@
+// Test that misexpect detects mis-annotated branches
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-branch.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -fmisexpect
+
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+
+int foo(int);
+int bar();
+int baz(int);
+int buzz();
+
+const int inner_loop = 100;
+const int outer_loop = 2000;
+
+int main() {
+ int val = 0;
+ for (int i = 0; i < outer_loop; ++i) {
+ for (int i = 0; i < inner_loop; ++i) {
+ val = bar();
+ }
+ }
+ return 0;
+}
+
+int bar() {
+ int rando = buzz();
+ int x = 0;
+ if (likely(rando % (outer_loop * inner_loop) == 0)) { // expected-warning {{Current PGO counters disagree with the use of __builtin_expect()}}
+ x = baz(rando);
+ } else {
+ x = foo(50);
+ }
+ return x;
+}
+
+int foo(int i) {
+ int j = 0;
+ while (i < 100) {
+ i += buzz() % 5;
+ j++;
+ }
+ return j;
+}
+
+int baz(int rando) {
+ int x = rando;
+ return x;
+}
Index: clang/test/Profile/misexpect-branch-nonconst-expected-val.c
===================================================================
--- /dev/null
+++ clang/test/Profile/misexpect-branch-nonconst-expected-val.c
@@ -0,0 +1,51 @@
+// Test that misexpect detects mis-annotated branches
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-branch-nonconst-expect-arg.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -fmisexpect
+
+// expected-no-diagnostics
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+
+int foo(int);
+int bar();
+int baz(int);
+int buzz();
+
+const int inner_loop = 100;
+const int outer_loop = 2000;
+
+int main() {
+ int val = 0;
+ for (int i = 0; i < outer_loop; ++i) {
+ for (int i = 0; i < inner_loop; ++i) {
+ val = bar();
+ }
+ }
+ return 0;
+}
+
+int bar() {
+ int rando = buzz();
+ int x = 0;
+ if (__builtin_expect(rando % (outer_loop * inner_loop) == 0, buzz())) {
+ x = baz(rando);
+ } else {
+ x = foo(50);
+ }
+ return x;
+}
+
+int foo(int i) {
+ int j = 0;
+ while (i < 100) {
+ i += buzz() % 5;
+ j++;
+ }
+ return j;
+}
+
+int baz(int rando) {
+ int x = rando;
+ return x;
+}
Index: clang/test/Profile/misexpect-branch-cold.c
===================================================================
--- /dev/null
+++ clang/test/Profile/misexpect-branch-cold.c
@@ -0,0 +1,51 @@
+// Test that misexpect detects mis-annotated branches
+
+// RUN: llvm-profdata merge %S/Inputs/misexpect-branch.proftext -o %t.profdata
+// RUN: %clang_cc1 %s -O2 -o - -disable-llvm-passes -emit-llvm -fprofile-instrument-use-path=%t.profdata -verify -fmisexpect
+
+// expected-no-diagnostics
+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+
+int foo(int);
+int bar();
+int baz(int);
+int buzz();
+
+const int inner_loop = 100;
+const int outer_loop = 2000;
+
+int main() {
+ int val = 0;
+ for (int i = 0; i < outer_loop; ++i) {
+ for (int i = 0; i < inner_loop; ++i) {
+ val = bar();
+ }
+ }
+ return 0;
+}
+
+int bar() {
+ int rando = buzz();
+ int x = 0;
+ if (unlikely(rando % (outer_loop * inner_loop) == 0)) {
+ x = baz(rando);
+ } else {
+ x = foo(50);
+ }
+ return x;
+}
+
+int foo(int i) {
+ int j = 0;
+ while (i < 100) {
+ i += buzz() % 5;
+ j++;
+ }
+ return j;
+}
+
+int baz(int rando) {
+ int x = rando;
+ return x;
+}
Index: clang/test/Profile/Inputs/misexpect-switch.proftext
===================================================================
--- /dev/null
+++ clang/test/Profile/Inputs/misexpect-switch.proftext
@@ -0,0 +1,45 @@
+init_arry
+# Func Hash:
+18129
+# Num Counters:
+2
+# Counter Values:
+1
+25
+
+main
+# Func Hash:
+1965403898329309329
+# Num Counters:
+10
+# Counter Values:
+1
+20
+20000
+20000
+5
+19995
+0
+0
+0
+0
+
+random_sample
+# Func Hash:
+19458874217560
+# Num Counters:
+3
+# Counter Values:
+19995
+499875
+100042
+
+sum
+# Func Hash:
+1160280
+# Num Counters:
+2
+# Counter Values:
+5
+125
+
Index: clang/test/Profile/Inputs/misexpect-branch.proftext
===================================================================
--- /dev/null
+++ clang/test/Profile/Inputs/misexpect-branch.proftext
@@ -0,0 +1,36 @@
+bar
+# Func Hash:
+45795613684824
+# Num Counters:
+2
+# Counter Values:
+200000
+0
+
+baz
+# Func Hash:
+24
+# Num Counters:
+1
+# Counter Values:
+0
+
+foo
+# Func Hash:
+635992
+# Num Counters:
+2
+# Counter Values:
+200000
+5095099
+
+main
+# Func Hash:
+303943193688
+# Num Counters:
+3
+# Counter Values:
+1
+2000
+200000
+
Index: clang/test/Profile/Inputs/misexpect-branch-nonconst-expect-arg.proftext
===================================================================
--- /dev/null
+++ clang/test/Profile/Inputs/misexpect-branch-nonconst-expect-arg.proftext
@@ -0,0 +1,36 @@
+bar
+# Func Hash:
+11262309464
+# Num Counters:
+2
+# Counter Values:
+200000
+2
+
+baz
+# Func Hash:
+24
+# Num Counters:
+1
+# Counter Values:
+2
+
+foo
+# Func Hash:
+635992
+# Num Counters:
+2
+# Counter Values:
+199998
+5096876
+
+main
+# Func Hash:
+303943193688
+# Num Counters:
+3
+# Counter Values:
+1
+2000
+200000
+
Index: clang/lib/Frontend/CompilerInvocation.cpp
===================================================================
--- clang/lib/Frontend/CompilerInvocation.cpp
+++ clang/lib/Frontend/CompilerInvocation.cpp
@@ -809,6 +809,7 @@
<< Args.getLastArg(OPT_fprofile_remapping_file_EQ)->getAsString(Args)
<< "-fexperimental-new-pass-manager";
}
+ Opts.MisExpect = Args.hasFlag(OPT_fmisexpect, OPT_fno_misexpect, false);
Opts.CoverageMapping =
Args.hasFlag(OPT_fcoverage_mapping, OPT_fno_coverage_mapping, false);
Index: clang/lib/Driver/ToolChains/Clang.cpp
===================================================================
--- clang/lib/Driver/ToolChains/Clang.cpp
+++ clang/lib/Driver/ToolChains/Clang.cpp
@@ -3998,6 +3998,11 @@
Args.AddLastArg(CmdArgs, options::OPT_ffine_grained_bitfield_accesses,
options::OPT_fno_fine_grained_bitfield_accesses);
+ if (Args.hasFlag(options::OPT_fmisexpect, options::OPT_fno_misexpect,
+ false)) {
+ CmdArgs.push_back("-fmisexpect");
+ }
+
// Handle segmented stacks.
if (Args.hasArg(options::OPT_fsplit_stack))
CmdArgs.push_back("-split-stacks");
Index: clang/lib/CodeGen/MisExpect.h
===================================================================
--- /dev/null
+++ clang/lib/CodeGen/MisExpect.h
@@ -0,0 +1,52 @@
+//===--- MisExpect.h - Emit LLVM Code from Statements ---------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This contains code to emit warnings for potentially incorrect usage of
+// __builtin_expect(). It uses PGO profiles to validation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_LIB_CODEGEN_MISEXPECT_H
+#define LLVM_CLANG_LIB_CODEGEN_MISEXPECT_H
+
+#include "CodeGenModule.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Expr.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/Optional.h"
+
+namespace clang {
+namespace CodeGen {
+namespace MisExpect {
+
+/// getExpectedValue - Returns the value that __builtin_expect() is expecting.
+/// If the second parameter cannot be evaluated at compile-time, returns an
+/// empty Optional. Returns None when Call is not __builtin_expect()
+Optional<int64_t> getExpectedValue(const clang::CallExpr *Call,
+ ASTContext &Context);
+
+/// CheckMisExpectBranch - check if a branch is annotated with
+/// __builting_expect and when using profiling data, verify that the profile
+/// agrees with the use of the annotation
+
+void CheckMisExpectBranch(const Expr *Cond, uint64_t TrueCount,
+ uint64_t CurrProfCount, CodeGenModule &CGM);
+
+/// CheckMisExpect - check if a branch is annotated with __builting_expect and
+/// when using profiling data, verify that the profile agrees with the use of
+/// the annotation
+void CheckMisExpectSwitch(const CallExpr *Call,
+ llvm::SmallVector<uint64_t, 16> *SwitchWeights,
+ llvm::DenseMap<int64_t, size_t> *CaseMap,
+ CodeGenModule &CGM);
+
+} // namespace MisExpect
+} // namespace CodeGen
+} // namespace clang
+
+#endif // LLVM_CLANG_LIB_CODEGEN_MISEXPECT_H
Index: clang/lib/CodeGen/MisExpect.cpp
===================================================================
--- /dev/null
+++ clang/lib/CodeGen/MisExpect.cpp
@@ -0,0 +1,175 @@
+//===--- MisExpect.cpp - Emit LLVM Code from Statements -------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This contains code to emit warnings for potentially incorrect usage of
+// __builtin_expect(). It uses PGO profiles to validation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "MisExpect.h"
+#include "CodeGenModule.h"
+#include "clang/Basic/Builtins.h"
+#include "clang/Basic/CodeGenOptions.h"
+#include "llvm/Support/BranchProbability.h"
+
+#include <algorithm>
+#include <numeric>
+
+namespace clang {
+namespace CodeGen {
+namespace MisExpect {
+
+#define DEBUG_TYPE "misexpect"
+
+void DebugPrintMisExpectSwitchInfo(SmallVector<uint64_t, 16> *SwitchWeights,
+ llvm::DenseMap<int64_t, size_t> *CaseMap);
+
+void EmitMisExpectWarning(const CallExpr *Call, CodeGenModule &CGM);
+
+Optional<int64_t> getExpectedValue(const clang::CallExpr *Call,
+ ASTContext &Context) {
+ if (!Call)
+ return Optional<int64_t>(None);
+
+ auto *FD = dyn_cast_or_null<FunctionDecl>(Call->getCalleeDecl());
+ if (!FD || FD->getBuiltinID() != Builtin::BI__builtin_expect) {
+ return Optional<int64_t>(None);
+ }
+
+ // Check if we can evaluate the 2nd parameter to __builtin_expect(expr,long)
+ // since it may not be able to be evaluated at compile-time
+ Expr::EvalResult ExprResult;
+ auto Arg = Call->getArg(1);
+ Arg->EvaluateAsInt(ExprResult, Context, Expr::SE_AllowSideEffects);
+
+ if (!ExprResult.Val.hasValue())
+ return Optional<int64_t>(None);
+
+ llvm::APSInt &Into = ExprResult.Val.getInt();
+ int64_t ExpectedVal = Into.getExtValue();
+ return Optional<int64_t>(ExpectedVal);
+}
+
+void CheckMisExpectBranch(const Expr *Cond, uint64_t TrueCount,
+ uint64_t CurrProfCount, CodeGenModule &CGM) {
+ if (!CGM.getCodeGenOpts().MisExpect ||
+ CGM.getCodeGenOpts().getProfileUse() == CodeGenOptions::ProfileNone)
+ return;
+
+ auto *Call = dyn_cast<CallExpr>(Cond->IgnoreImpCasts());
+
+ Optional<int64_t> ExpectedValOpt = getExpectedValue(Call, CGM.getContext());
+
+ if (!ExpectedValOpt.hasValue())
+ return;
+
+ const long ExpectedVal = ExpectedValOpt.getValue();
+ const bool ExpectedTrueBranch = (ExpectedVal != 0);
+
+ LLVM_DEBUG(llvm::dbgs() << "Expected Value:\t" << ExpectedVal << "\n");
+ LLVM_DEBUG(llvm::dbgs() << "Current Count: \t" << CurrProfCount << "\n");
+ LLVM_DEBUG(llvm::dbgs() << "True Count: \t" << TrueCount << "\n");
+
+ bool IncorrectPerfCounters = false;
+ uint64_t Scaled;
+
+ // TODO: determine better heuristics than hot/cold function thresholds
+ if (ExpectedTrueBranch) {
+ const llvm::BranchProbability HotFunctionThreshold(1, 100);
+ Scaled = HotFunctionThreshold.scale(CurrProfCount);
+ if (TrueCount < Scaled)
+ IncorrectPerfCounters = true;
+ } else {
+ const llvm::BranchProbability ColdFunctionThreshold(2, 10000);
+ Scaled = ColdFunctionThreshold.scale(CurrProfCount);
+ if (TrueCount > Scaled)
+ IncorrectPerfCounters = true;
+ }
+ LLVM_DEBUG(llvm::dbgs() << "Scaled Count:\t" << Scaled << "\n");
+
+ if (IncorrectPerfCounters) {
+ EmitMisExpectWarning(Call, CGM);
+ }
+}
+void CheckMisExpectSwitch(const CallExpr *Call,
+ SmallVector<uint64_t, 16> *SwitchWeights,
+ llvm::DenseMap<int64_t, size_t> *CaseMap,
+ CodeGenModule &CGM) {
+ if (!SwitchWeights || !CaseMap)
+ return;
+
+ LLVM_DEBUG(DebugPrintMisExpectSwitchInfo(SwitchWeights, CaseMap));
+
+ uint64_t CaseTotal =
+ std::accumulate(SwitchWeights->begin(), SwitchWeights->end(), 0);
+
+ LLVM_DEBUG(llvm::dbgs() << "Switch Profile Count:\t" << CaseTotal << "\n");
+
+ Optional<int64_t> ExpectedValOpt = getExpectedValue(Call, CGM.getContext());
+
+ if (!ExpectedValOpt.hasValue())
+ return;
+
+ const long ExpectedVal = ExpectedValOpt.getValue();
+
+ LLVM_DEBUG(llvm::dbgs() << "Expected Value:\t" << ExpectedVal << "\n");
+
+ uint64_t Max =
+ *std::max_element(SwitchWeights->begin(), SwitchWeights->end());
+
+ auto MapIndex = CaseMap->find(ExpectedVal);
+
+ uint64_t Index;
+ if (MapIndex != CaseMap->end()) {
+ Index = MapIndex->second;
+ } else {
+ Index = 0;
+ }
+
+ uint64_t TakenCount = (*SwitchWeights)[Index];
+
+ LLVM_DEBUG(llvm::dbgs() << "Taken Count:\t" << TakenCount << "\n");
+ LLVM_DEBUG(llvm::dbgs() << "Max Count:\t" << Max << "\n");
+
+ if (TakenCount < Max) {
+ EmitMisExpectWarning(Call, CGM);
+ } // end if
+}
+
+void EmitMisExpectWarning(const CallExpr *Call, CodeGenModule &CGM) {
+ SourceLocation ExprLoc = Call->getBeginLoc();
+ unsigned DiagID = CGM.getDiags().getCustomDiagID(
+ DiagnosticsEngine::Warning, "Current PGO counters disagree with "
+ "the use of __builtin_expect().");
+ CGM.getDiags().Report(ExprLoc, DiagID);
+}
+
+void DebugPrintMisExpectSwitchInfo(SmallVector<uint64_t, 16> *SwitchWeights,
+ llvm::DenseMap<int64_t, size_t> *CaseMap) {
+
+ auto size = SwitchWeights->size();
+ for (size_t i = 0; i < size; ++i) {
+ llvm::dbgs() << "Index: " << i << "\tProfile Value:\t"
+ << (*SwitchWeights)[i] << "\n";
+ }
+
+ llvm::dbgs() << "------------------\n";
+
+ for (auto &item : *CaseMap) {
+ llvm::dbgs() << "Case Key: " << item.first << "\tRelated Index:\t"
+ << item.second << "\n";
+ }
+
+ llvm::dbgs() << "------------------\n";
+}
+
+#undef DEBUG_TYPE
+
+} // namespace MisExpect
+} // namespace CodeGen
+} // namespace clang
Index: clang/lib/CodeGen/CodeGenFunction.h
===================================================================
--- clang/lib/CodeGen/CodeGenFunction.h
+++ clang/lib/CodeGen/CodeGenFunction.h
@@ -1370,6 +1370,8 @@
llvm::SwitchInst *SwitchInsn = nullptr;
/// The branch weights of SwitchInsn when doing instrumentation based PGO.
SmallVector<uint64_t, 16> *SwitchWeights = nullptr;
+ llvm::DenseMap<int64_t, size_t> *CaseMap = nullptr;
+
/// CaseRangeBlock - This block holds if condition check for last case
/// statement range in current switch instruction.
Index: clang/lib/CodeGen/CodeGenFunction.cpp
===================================================================
--- clang/lib/CodeGen/CodeGenFunction.cpp
+++ clang/lib/CodeGen/CodeGenFunction.cpp
@@ -20,6 +20,7 @@
#include "CodeGenModule.h"
#include "CodeGenPGO.h"
#include "TargetInfo.h"
+#include "MisExpect.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/ASTLambda.h"
#include "clang/AST/Decl.h"
@@ -1346,8 +1347,6 @@
return true;
}
-
-
/// EmitBranchOnBoolExpr - Emit a branch on a boolean condition (e.g. for an if
/// statement) to the specified blocks. Based on the condition, this might try
/// to simplify the codegen of the conditional based on the branch.
@@ -1358,6 +1357,8 @@
uint64_t TrueCount) {
Cond = Cond->IgnoreParens();
+ MisExpect::CheckMisExpectBranch(Cond, TrueCount, getCurrentProfileCount(), CGM);
+
if (const BinaryOperator *CondBOp = dyn_cast<BinaryOperator>(Cond)) {
// Handle X && Y in a condition.
Index: clang/lib/CodeGen/CMakeLists.txt
===================================================================
--- clang/lib/CodeGen/CMakeLists.txt
+++ clang/lib/CodeGen/CMakeLists.txt
@@ -87,6 +87,7 @@
ItaniumCXXABI.cpp
MacroPPCallbacks.cpp
MicrosoftCXXABI.cpp
+ MisExpect.cpp
ModuleBuilder.cpp
ObjectFilePCHContainerOperations.cpp
PatternInit.cpp
Index: clang/lib/CodeGen/CGStmt.cpp
===================================================================
--- clang/lib/CodeGen/CGStmt.cpp
+++ clang/lib/CodeGen/CGStmt.cpp
@@ -14,6 +14,7 @@
#include "CGDebugInfo.h"
#include "CodeGenModule.h"
#include "TargetInfo.h"
+#include "MisExpect.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/Basic/Builtins.h"
#include "clang/Basic/PrettyStackTrace.h"
@@ -1284,8 +1285,16 @@
llvm::BasicBlock *CaseDest = createBasicBlock("sw.bb");
EmitBlockWithFallThrough(CaseDest, &S);
- if (SwitchWeights)
+ size_t MapIndex = 0;
+ if (SwitchWeights) {
SwitchWeights->push_back(getProfileCount(&S));
+ if (CaseMap) {
+ MapIndex = SwitchWeights->size() - 1;
+ llvm::ConstantInt *CaseVal =
+ Builder.getInt(S.getLHS()->EvaluateKnownConstInt(getContext()));
+ (*CaseMap)[CaseVal->getSExtValue()] = MapIndex;
+ }
+ }
SwitchInsn->addCase(CaseVal, CaseDest);
// Recursively emitting the statement is acceptable, but is not wonderful for
@@ -1306,8 +1315,15 @@
llvm::ConstantInt *CaseVal =
Builder.getInt(CurCase->getLHS()->EvaluateKnownConstInt(getContext()));
- if (SwitchWeights)
+ if (SwitchWeights) {
SwitchWeights->push_back(getProfileCount(NextCase));
+ if (CaseMap) {
+ // only the original statement gets a counter, so map back to it's index
+ // in SwitchWeights
+ (*CaseMap)[CaseVal->getSExtValue()] = MapIndex;
+ }
+ }
+
if (CGM.getCodeGenOpts().hasProfileClangInstr()) {
CaseDest = createBasicBlock("sw.bb");
EmitBlockWithFallThrough(CaseDest, &S);
@@ -1575,6 +1591,7 @@
// Handle nested switch statements.
llvm::SwitchInst *SavedSwitchInsn = SwitchInsn;
SmallVector<uint64_t, 16> *SavedSwitchWeights = SwitchWeights;
+ llvm::DenseMap<int64_t, size_t> *SavedCaseMap = CaseMap;
llvm::BasicBlock *SavedCRBlock = CaseRangeBlock;
// See if we can constant fold the condition of the switch and therefore only
@@ -1646,6 +1663,8 @@
}
SwitchWeights = new SmallVector<uint64_t, 16>();
SwitchWeights->reserve(NumCases);
+ CaseMap = new llvm::DenseMap<int64_t, size_t>();
+ CaseMap->reserve(NumCases);
// The default needs to be first. We store the edge count, so we already
// know the right weight.
SwitchWeights->push_back(DefaultCount);
@@ -1698,10 +1717,15 @@
auto *Call = dyn_cast<CallExpr>(S.getCond());
if (Call && CGM.getCodeGenOpts().OptimizationLevel != 0) {
auto *FD = dyn_cast_or_null<FunctionDecl>(Call->getCalleeDecl());
- if (FD && FD->getBuiltinID() == Builtin::BI__builtin_unpredictable) {
- llvm::MDBuilder MDHelper(getLLVMContext());
- SwitchInsn->setMetadata(llvm::LLVMContext::MD_unpredictable,
- MDHelper.createUnpredictable());
+ if (FD) {
+ if (FD->getBuiltinID() == Builtin::BI__builtin_unpredictable) {
+ llvm::MDBuilder MDHelper(getLLVMContext());
+ SwitchInsn->setMetadata(llvm::LLVMContext::MD_unpredictable,
+ MDHelper.createUnpredictable());
+ } else if (CGM.getCodeGenOpts().MisExpect &&
+ FD->getBuiltinID() == Builtin::BI__builtin_expect) {
+ MisExpect::CheckMisExpectSwitch(Call, SwitchWeights, CaseMap, CGM);
+ }
}
}
@@ -1714,8 +1738,14 @@
createProfileWeights(*SwitchWeights));
delete SwitchWeights;
}
+
+ if (CaseMap) {
+ delete CaseMap;
+ }
+
SwitchInsn = SavedSwitchInsn;
SwitchWeights = SavedSwitchWeights;
+ CaseMap = SavedCaseMap;
CaseRangeBlock = SavedCRBlock;
}
Index: clang/include/clang/Driver/Options.td
===================================================================
--- clang/include/clang/Driver/Options.td
+++ clang/include/clang/Driver/Options.td
@@ -716,6 +716,11 @@
Group<f_Group>, Alias<fprofile_sample_accurate>;
def fno_auto_profile_accurate : Flag<["-"], "fno-auto-profile-accurate">,
Group<f_Group>, Alias<fno_profile_sample_accurate>;
+def fmisexpect : Flag<["-"], "fmisexpect">,
+ Group<f_Group>, Flags<[CC1Option]>,
+ HelpText<"Validate use of __builtin_expect with instrumentation data">;
+def fno_misexpect : Flag<["-"], "fno-misexpect">,
+ Group<f_Group>, Flags<[CC1Option]>;
def fdebug_compilation_dir : Separate<["-"], "fdebug-compilation-dir">,
Group<f_Group>, Flags<[CC1Option, CC1AsOption, CoreOption]>,
HelpText<"The compilation directory to embed in the debug info.">;
Index: clang/include/clang/Basic/CodeGenOptions.def
===================================================================
--- clang/include/clang/Basic/CodeGenOptions.def
+++ clang/include/clang/Basic/CodeGenOptions.def
@@ -169,6 +169,7 @@
///< enable code coverage analysis.
CODEGENOPT(DumpCoverageMapping , 1, 0) ///< Dump the generated coverage mapping
///< regions.
+CODEGENOPT(MisExpect , 1, 0) ///< Validate __builtin_expect with PGO counters
/// If -fpcc-struct-return or -freg-struct-return is specified.
ENUM_CODEGENOPT(StructReturnConvention, StructReturnConventionKind, 2, SRCK_Default)
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
