LLVM  10.0.0svn
MisExpect.cpp
Go to the documentation of this file.
1 //===--- MisExpect.cpp - Check the use of llvm.expect with PGO data -------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This contains code to emit warnings for potentially incorrect usage of the
10 // llvm.expect intrinsic. This utility extracts the threshold values from
11 // metadata associated with the instrumented Branch or Switch instruction. The
12 // threshold values are then used to determine if a warning should be emmited.
13 //
14 // MisExpect metadata is generated when llvm.expect intrinsics are lowered see
15 // LowerExpectIntrinsic.cpp
16 //
17 //===----------------------------------------------------------------------===//
18 
20 #include "llvm/ADT/Twine.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/DiagnosticInfo.h"
24 #include "llvm/IR/Instruction.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/LLVMContext.h"
28 #include "llvm/Support/Debug.h"
30 #include <cstdint>
31 #include <functional>
32 #include <numeric>
33 
34 #define DEBUG_TYPE "misexpect"
35 
36 using namespace llvm;
37 using namespace misexpect;
38 
39 namespace llvm {
40 
41 // Command line option to enable/disable the warning when profile data suggests
42 // a mismatch with the use of the llvm.expect intrinsic
44  "pgo-warn-misexpect", cl::init(false), cl::Hidden,
45  cl::desc("Use this option to turn on/off "
46  "warnings about incorrect usage of llvm.expect intrinsics."));
47 
48 } // namespace llvm
49 
50 namespace {
51 
52 Instruction *getOprndOrInst(Instruction *I) {
53  assert(I != nullptr && "MisExpect target Instruction cannot be nullptr");
54  Instruction *Ret = nullptr;
55  if (auto *B = dyn_cast<BranchInst>(I)) {
56  Ret = dyn_cast<Instruction>(B->getCondition());
57  }
58  // TODO: Find a way to resolve condition location for switches
59  // Using the condition of the switch seems to often resolve to an earlier
60  // point in the program, i.e. the calculation of the switch condition, rather
61  // than the switches location in the source code. Thus, we should use the
62  // instruction to get source code locations rather than the condition to
63  // improve diagnostic output, such as the caret. If the same problem exists
64  // for branch instructions, then we should remove this function and directly
65  // use the instruction
66  //
67  // else if (auto S = dyn_cast<SwitchInst>(I)) {
68  // Ret = I;
69  //}
70  return Ret ? Ret : I;
71 }
72 
73 void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx,
74  uint64_t ProfCount, uint64_t TotalCount) {
75  double PercentageCorrect = (double)ProfCount / TotalCount;
76  auto PerString =
77  formatv("{0:P} ({1} / {2})", PercentageCorrect, ProfCount, TotalCount);
78  auto RemStr = formatv(
79  "Potential performance regression from use of the llvm.expect intrinsic: "
80  "Annotation was correct on {0} of profiled executions.",
81  PerString);
82  Twine Msg(PerString);
83  Instruction *Cond = getOprndOrInst(I);
84  if (PGOWarnMisExpect)
85  Ctx.diagnose(DiagnosticInfoMisExpect(Cond, Msg));
87  ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str());
88 }
89 
90 } // namespace
91 
92 namespace llvm {
93 namespace misexpect {
94 
96  LLVMContext &Ctx) {
97  if (auto *MisExpectData = I->getMetadata(LLVMContext::MD_misexpect)) {
98  auto *MisExpectDataName = dyn_cast<MDString>(MisExpectData->getOperand(0));
99  if (MisExpectDataName &&
100  MisExpectDataName->getString().equals("misexpect")) {
101  LLVM_DEBUG(llvm::dbgs() << "------------------\n");
103  << "Function: " << I->getFunction()->getName() << "\n");
104  LLVM_DEBUG(llvm::dbgs() << "Instruction: " << *I << ":\n");
105  LLVM_DEBUG(for (int Idx = 0, Size = Weights.size(); Idx < Size; ++Idx) {
106  llvm::dbgs() << "Weights[" << Idx << "] = " << Weights[Idx] << "\n";
107  });
108 
109  // extract values from misexpect metadata
110  const auto *IndexCint =
111  mdconst::dyn_extract<ConstantInt>(MisExpectData->getOperand(1));
112  const auto *LikelyCInt =
113  mdconst::dyn_extract<ConstantInt>(MisExpectData->getOperand(2));
114  const auto *UnlikelyCInt =
115  mdconst::dyn_extract<ConstantInt>(MisExpectData->getOperand(3));
116 
117  if (!IndexCint || !LikelyCInt || !UnlikelyCInt)
118  return;
119 
120  const uint64_t Index = IndexCint->getZExtValue();
121  const uint64_t LikelyBranchWeight = LikelyCInt->getZExtValue();
122  const uint64_t UnlikelyBranchWeight = UnlikelyCInt->getZExtValue();
123  const uint64_t ProfileCount = Weights[Index];
124  const uint64_t CaseTotal = std::accumulate(
125  Weights.begin(), Weights.end(), (uint64_t)0, std::plus<uint64_t>());
126  const uint64_t NumUnlikelyTargets = Weights.size() - 1;
127 
128  const uint64_t TotalBranchWeight =
129  LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets);
130 
131  const llvm::BranchProbability LikelyThreshold(LikelyBranchWeight,
132  TotalBranchWeight);
133  uint64_t ScaledThreshold = LikelyThreshold.scale(CaseTotal);
134 
136  << "Unlikely Targets: " << NumUnlikelyTargets << ":\n");
137  LLVM_DEBUG(llvm::dbgs() << "Profile Count: " << ProfileCount << ":\n");
139  << "Scaled Threshold: " << ScaledThreshold << ":\n");
140  LLVM_DEBUG(llvm::dbgs() << "------------------\n");
141  if (ProfileCount < ScaledThreshold)
142  emitMisexpectDiagnostic(I, Ctx, ProfileCount, CaseTotal);
143  }
144  }
145 }
146 
148  if (auto *MD = I.getMetadata(LLVMContext::MD_prof)) {
149  unsigned NOps = MD->getNumOperands();
150 
151  // Only emit misexpect diagnostics if at least 2 branch weights are present.
152  // Less than 2 branch weights means that the profiling metadata is:
153  // 1) incorrect/corrupted
154  // 2) not branch weight metadata
155  // 3) completely deterministic
156  // In these cases we should not emit any diagnostic related to misexpect.
157  if (NOps < 3)
158  return;
159 
160  // Operand 0 is a string tag "branch_weights"
161  if (MDString *Tag = cast<MDString>(MD->getOperand(0))) {
162  if (Tag->getString().equals("branch_weights")) {
163  SmallVector<uint32_t, 4> RealWeights(NOps - 1);
164  for (unsigned i = 1; i < NOps; i++) {
165  ConstantInt *Value =
166  mdconst::dyn_extract<ConstantInt>(MD->getOperand(i));
167  RealWeights[i - 1] = Value->getZExtValue();
168  }
169  verifyMisExpect(&I, RealWeights, I.getContext());
170  }
171  }
172  }
173 }
174 
175 } // namespace misexpect
176 } // namespace llvm
177 #undef DEBUG_TYPE
This class represents lattice values for constants.
Definition: AllocatorList.h:23
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:743
auto formatv(const char *Fmt, Ts &&... Vals) -> formatv_object< decltype(std::make_tuple(detail::build_format_adapter(std::forward< Ts >(Vals))...))>
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
#define DEBUG_TYPE
Definition: MisExpect.cpp:34
static cl::opt< bool > PGOWarnMisExpect("pgo-warn-misexpect", cl::init(false), cl::Hidden, cl::desc("Use this option to turn on/off " "warnings about incorrect usage of llvm.expect intrinsics."))
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:244
void verifyMisExpect(llvm::Instruction *I, const llvm::SmallVector< uint32_t, 4 > &Weights, llvm::LLVMContext &Ctx)
verifyMisExpect - compares PGO counters to the thresholds used for llvm.expect and warns if the PGO c...
Definition: MisExpect.cpp:95
static cl::opt< uint32_t > UnlikelyBranchWeight("unlikely-branch-weight", cl::Hidden, cl::init(1), cl::desc("Weight of the branch unlikely to be taken (default = 1)"))
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:148
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:64
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Diagnostic information for applied optimization remarks.
Diagnostic information for MisExpect analysis.
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:59
static cl::opt< uint32_t > LikelyBranchWeight("likely-branch-weight", cl::Hidden, cl::init(2000), cl::desc("Weight of the branch likely to be taken (default = 2000)"))
Class to represent profile counts.
Definition: Function.h:260
size_t size() const
Definition: SmallVector.h:52
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
uint32_t Size
Definition: Profile.cpp:46
void diagnose(const DiagnosticInfo &DI)
Report a message to the currently installed diagnostic handler.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:74
A single uniqued string.
Definition: Metadata.h:603
#define LLVM_DEBUG(X)
Definition: Debug.h:122
void checkFrontendInstrumentation(Instruction &I)
checkClangInstrumentation - verify if llvm.expect matches PGO profile This function checks the fronte...
Definition: MisExpect.cpp:147
The optimization diagnostic interface.
const BasicBlock * getParent() const
Definition: Instruction.h:66