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's implementation relies on two assumptions about how branch weights 15 // are managed in LLVM. 16 // 17 // 1) Frontend profiling weights are always in place before llvm.expect is 18 // lowered in LowerExpectIntrinsic.cpp. Frontend based instrumentation therefore 19 // needs to extract the branch weights and then compare them to the weights 20 // being added by the llvm.expect intrinsic lowering. 21 // 22 // 2) Sampling and IR based profiles will *only* have branch weight metadata 23 // before profiling data is consulted if they are from a lowered llvm.expect 24 // intrinsic. These profiles thus always extract the expected weights and then 25 // compare them to the weights collected during profiling to determine if a 26 // diagnostic message is warranted. 27 // 28 //===----------------------------------------------------------------------===// 29 30 #include "llvm/Transforms/Utils/MisExpect.h" 31 #include "llvm/ADT/Twine.h" 32 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 33 #include "llvm/IR/DiagnosticInfo.h" 34 #include "llvm/IR/Instruction.h" 35 #include "llvm/IR/Instructions.h" 36 #include "llvm/IR/LLVMContext.h" 37 #include "llvm/IR/ProfDataUtils.h" 38 #include "llvm/Support/BranchProbability.h" 39 #include "llvm/Support/CommandLine.h" 40 #include "llvm/Support/FormatVariadic.h" 41 #include <algorithm> 42 #include <cstdint> 43 #include <functional> 44 #include <numeric> 45 46 #define DEBUG_TYPE "misexpect" 47 48 using namespace llvm; 49 using namespace misexpect; 50 51 namespace llvm { 52 53 // Command line option to enable/disable the warning when profile data suggests 54 // a mismatch with the use of the llvm.expect intrinsic 55 static cl::opt<bool> PGOWarnMisExpect( 56 "pgo-warn-misexpect", cl::init(false), cl::Hidden, 57 cl::desc("Use this option to turn on/off " 58 "warnings about incorrect usage of llvm.expect intrinsics.")); 59 60 // Command line option for setting the diagnostic tolerance threshold 61 static cl::opt<uint32_t> MisExpectTolerance( 62 "misexpect-tolerance", cl::init(0), 63 cl::desc("Prevents emitting diagnostics when profile counts are " 64 "within N% of the threshold..")); 65 66 } // namespace llvm 67 68 namespace { 69 70 bool isMisExpectDiagEnabled(LLVMContext &Ctx) { 71 return PGOWarnMisExpect || Ctx.getMisExpectWarningRequested(); 72 } 73 74 uint32_t getMisExpectTolerance(LLVMContext &Ctx) { 75 return std::max(static_cast<uint32_t>(MisExpectTolerance), 76 Ctx.getDiagnosticsMisExpectTolerance()); 77 } 78 79 Instruction *getInstCondition(Instruction *I) { 80 assert(I != nullptr && "MisExpect target Instruction cannot be nullptr"); 81 Instruction *Ret = nullptr; 82 if (auto *B = dyn_cast<BranchInst>(I)) { 83 Ret = dyn_cast<Instruction>(B->getCondition()); 84 } 85 // TODO: Find a way to resolve condition location for switches 86 // Using the condition of the switch seems to often resolve to an earlier 87 // point in the program, i.e. the calculation of the switch condition, rather 88 // than the switch's location in the source code. Thus, we should use the 89 // instruction to get source code locations rather than the condition to 90 // improve diagnostic output, such as the caret. If the same problem exists 91 // for branch instructions, then we should remove this function and directly 92 // use the instruction 93 // 94 else if (auto *S = dyn_cast<SwitchInst>(I)) { 95 Ret = dyn_cast<Instruction>(S->getCondition()); 96 } 97 return Ret ? Ret : I; 98 } 99 100 void emitMisexpectDiagnostic(Instruction *I, LLVMContext &Ctx, 101 uint64_t ProfCount, uint64_t TotalCount) { 102 double PercentageCorrect = (double)ProfCount / TotalCount; 103 auto PerString = 104 formatv("{0:P} ({1} / {2})", PercentageCorrect, ProfCount, TotalCount); 105 auto RemStr = formatv( 106 "Potential performance regression from use of the llvm.expect intrinsic: " 107 "Annotation was correct on {0} of profiled executions.", 108 PerString); 109 Twine Msg(PerString); 110 Instruction *Cond = getInstCondition(I); 111 if (isMisExpectDiagEnabled(Ctx)) 112 Ctx.diagnose(DiagnosticInfoMisExpect(Cond, Msg)); 113 OptimizationRemarkEmitter ORE(I->getParent()->getParent()); 114 ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str()); 115 } 116 117 } // namespace 118 119 namespace llvm { 120 namespace misexpect { 121 122 void verifyMisExpect(Instruction &I, ArrayRef<uint32_t> RealWeights, 123 ArrayRef<uint32_t> ExpectedWeights) { 124 // To determine if we emit a diagnostic, we need to compare the branch weights 125 // from the profile to those added by the llvm.expect intrinsic. 126 // So first, we extract the "likely" and "unlikely" weights from 127 // ExpectedWeights And determine the correct weight in the profile to compare 128 // against. 129 uint64_t LikelyBranchWeight = 0, 130 UnlikelyBranchWeight = std::numeric_limits<uint32_t>::max(); 131 size_t MaxIndex = 0; 132 for (size_t Idx = 0, End = ExpectedWeights.size(); Idx < End; Idx++) { 133 uint32_t V = ExpectedWeights[Idx]; 134 if (LikelyBranchWeight < V) { 135 LikelyBranchWeight = V; 136 MaxIndex = Idx; 137 } 138 if (UnlikelyBranchWeight > V) { 139 UnlikelyBranchWeight = V; 140 } 141 } 142 143 const uint64_t ProfiledWeight = RealWeights[MaxIndex]; 144 const uint64_t RealWeightsTotal = 145 std::accumulate(RealWeights.begin(), RealWeights.end(), (uint64_t)0, 146 std::plus<uint64_t>()); 147 const uint64_t NumUnlikelyTargets = RealWeights.size() - 1; 148 149 uint64_t TotalBranchWeight = 150 LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets); 151 152 // Failing this assert means that we have corrupted metadata. 153 assert((TotalBranchWeight >= LikelyBranchWeight) && (TotalBranchWeight > 0) && 154 "TotalBranchWeight is less than the Likely branch weight"); 155 156 // To determine our threshold value we need to obtain the branch probability 157 // for the weights added by llvm.expect and use that proportion to calculate 158 // our threshold based on the collected profile data. 159 auto LikelyProbablilty = BranchProbability::getBranchProbability( 160 LikelyBranchWeight, TotalBranchWeight); 161 162 uint64_t ScaledThreshold = LikelyProbablilty.scale(RealWeightsTotal); 163 164 // clamp tolerance range to [0, 100) 165 auto Tolerance = getMisExpectTolerance(I.getContext()); 166 Tolerance = std::clamp(Tolerance, 0u, 99u); 167 168 // Allow users to relax checking by N% i.e., if they use a 5% tolerance, 169 // then we check against 0.95*ScaledThreshold 170 if (Tolerance > 0) 171 ScaledThreshold *= (1.0 - Tolerance / 100.0); 172 173 // When the profile weight is below the threshold, we emit the diagnostic 174 if (ProfiledWeight < ScaledThreshold) 175 emitMisexpectDiagnostic(&I, I.getContext(), ProfiledWeight, 176 RealWeightsTotal); 177 } 178 179 void checkBackendInstrumentation(Instruction &I, 180 const ArrayRef<uint32_t> RealWeights) { 181 // Backend checking assumes any existing weight comes from an `llvm.expect` 182 // intrinsic. However, SampleProfiling + ThinLTO add branch weights multiple 183 // times, leading to an invalid assumption in our checking. Backend checks 184 // should only operate on branch weights that carry the "!expected" field, 185 // since they are guaranteed to be added by the LowerExpectIntrinsic pass. 186 if (!hasBranchWeightOrigin(I)) 187 return; 188 SmallVector<uint32_t> ExpectedWeights; 189 if (!extractBranchWeights(I, ExpectedWeights)) 190 return; 191 verifyMisExpect(I, RealWeights, ExpectedWeights); 192 } 193 194 void checkFrontendInstrumentation(Instruction &I, 195 const ArrayRef<uint32_t> ExpectedWeights) { 196 SmallVector<uint32_t> RealWeights; 197 if (!extractBranchWeights(I, RealWeights)) 198 return; 199 verifyMisExpect(I, RealWeights, ExpectedWeights); 200 } 201 202 void checkExpectAnnotations(Instruction &I, 203 const ArrayRef<uint32_t> ExistingWeights, 204 bool IsFrontend) { 205 if (IsFrontend) { 206 checkFrontendInstrumentation(I, ExistingWeights); 207 } else { 208 checkBackendInstrumentation(I, ExistingWeights); 209 } 210 } 211 212 } // namespace misexpect 213 } // namespace llvm 214 #undef DEBUG_TYPE 215