197 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This contains code to emit warnings for potentially incorrect usage of the10// llvm.expect intrinsic. This utility extracts the threshold values from11// metadata associated with the instrumented Branch or Switch instruction. The12// 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 weights15// are managed in LLVM.16//17// 1) Frontend profiling weights are always in place before llvm.expect is18// lowered in LowerExpectIntrinsic.cpp. Frontend based instrumentation therefore19// needs to extract the branch weights and then compare them to the weights20// being added by the llvm.expect intrinsic lowering.21//22// 2) Sampling and IR based profiles will *only* have branch weight metadata23// before profiling data is consulted if they are from a lowered llvm.expect24// intrinsic. These profiles thus always extract the expected weights and then25// compare them to the weights collected during profiling to determine if a26// 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 48using namespace llvm;49using namespace misexpect;50 51// Command line option to enable/disable the warning when profile data suggests52// a mismatch with the use of the llvm.expect intrinsic53static cl::opt<bool> PGOWarnMisExpect(54 "pgo-warn-misexpect", cl::init(false), cl::Hidden,55 cl::desc("Use this option to turn on/off "56 "warnings about incorrect usage of llvm.expect intrinsics."));57 58// Command line option for setting the diagnostic tolerance threshold59static cl::opt<uint32_t> MisExpectTolerance(60 "misexpect-tolerance", cl::init(0),61 cl::desc("Prevents emitting diagnostics when profile counts are "62 "within N% of the threshold.."));63 64static bool isMisExpectDiagEnabled(const LLVMContext &Ctx) {65 return PGOWarnMisExpect || Ctx.getMisExpectWarningRequested();66}67 68static uint32_t getMisExpectTolerance(const LLVMContext &Ctx) {69 return std::max(static_cast<uint32_t>(MisExpectTolerance),70 Ctx.getDiagnosticsMisExpectTolerance());71}72 73static const Instruction *getInstCondition(const Instruction *I) {74 assert(I != nullptr && "MisExpect target Instruction cannot be nullptr");75 const Instruction *Ret = nullptr;76 if (auto *B = dyn_cast<BranchInst>(I)) {77 Ret = dyn_cast<Instruction>(B->getCondition());78 }79 // TODO: Find a way to resolve condition location for switches80 // Using the condition of the switch seems to often resolve to an earlier81 // point in the program, i.e. the calculation of the switch condition, rather82 // than the switch's location in the source code. Thus, we should use the83 // instruction to get source code locations rather than the condition to84 // improve diagnostic output, such as the caret. If the same problem exists85 // for branch instructions, then we should remove this function and directly86 // use the instruction87 //88 else if (auto *S = dyn_cast<SwitchInst>(I)) {89 Ret = dyn_cast<Instruction>(S->getCondition());90 }91 return Ret ? Ret : I;92}93 94static void emitMisexpectDiagnostic(const Instruction *I, LLVMContext &Ctx,95 uint64_t ProfCount, uint64_t TotalCount) {96 double PercentageCorrect = (double)ProfCount / TotalCount;97 auto PerString =98 formatv("{0:P} ({1} / {2})", PercentageCorrect, ProfCount, TotalCount);99 auto RemStr = formatv(100 "Potential performance regression from use of the llvm.expect intrinsic: "101 "Annotation was correct on {0} of profiled executions.",102 PerString);103 const Instruction *Cond = getInstCondition(I);104 if (isMisExpectDiagEnabled(Ctx))105 Ctx.diagnose(DiagnosticInfoMisExpect(Cond, Twine(PerString)));106 OptimizationRemarkEmitter ORE(I->getParent()->getParent());107 ORE.emit(OptimizationRemark(DEBUG_TYPE, "misexpect", Cond) << RemStr.str());108}109 110void misexpect::verifyMisExpect(const Instruction &I,111 ArrayRef<uint32_t> RealWeights,112 ArrayRef<uint32_t> ExpectedWeights) {113 // To determine if we emit a diagnostic, we need to compare the branch weights114 // from the profile to those added by the llvm.expect intrinsic.115 // So first, we extract the "likely" and "unlikely" weights from116 // ExpectedWeights And determine the correct weight in the profile to compare117 // against.118 uint64_t LikelyBranchWeight = 0,119 UnlikelyBranchWeight = std::numeric_limits<uint32_t>::max();120 size_t MaxIndex = 0;121 for (const auto &[Idx, V] : enumerate(ExpectedWeights)) {122 if (LikelyBranchWeight < V) {123 LikelyBranchWeight = V;124 MaxIndex = Idx;125 }126 if (UnlikelyBranchWeight > V)127 UnlikelyBranchWeight = V;128 }129 130 const uint64_t ProfiledWeight = RealWeights[MaxIndex];131 const uint64_t RealWeightsTotal =132 std::accumulate(RealWeights.begin(), RealWeights.end(), (uint64_t)0,133 std::plus<uint64_t>());134 const uint64_t NumUnlikelyTargets = RealWeights.size() - 1;135 136 uint64_t TotalBranchWeight =137 LikelyBranchWeight + (UnlikelyBranchWeight * NumUnlikelyTargets);138 139 // Failing this assert means that we have corrupted metadata.140 assert((TotalBranchWeight >= LikelyBranchWeight) && (TotalBranchWeight > 0) &&141 "TotalBranchWeight is less than the Likely branch weight");142 143 // To determine our threshold value we need to obtain the branch probability144 // for the weights added by llvm.expect and use that proportion to calculate145 // our threshold based on the collected profile data.146 auto LikelyProbablilty = BranchProbability::getBranchProbability(147 LikelyBranchWeight, TotalBranchWeight);148 149 uint64_t ScaledThreshold = LikelyProbablilty.scale(RealWeightsTotal);150 151 // clamp tolerance range to [0, 100)152 uint32_t Tolerance = getMisExpectTolerance(I.getContext());153 Tolerance = std::clamp(Tolerance, 0u, 99u);154 155 // Allow users to relax checking by N% i.e., if they use a 5% tolerance,156 // then we check against 0.95*ScaledThreshold157 if (Tolerance > 0)158 ScaledThreshold *= (1.0 - Tolerance / 100.0);159 160 // When the profile weight is below the threshold, we emit the diagnostic161 if (ProfiledWeight < ScaledThreshold)162 emitMisexpectDiagnostic(&I, I.getContext(), ProfiledWeight,163 RealWeightsTotal);164}165 166void misexpect::checkBackendInstrumentation(const Instruction &I,167 ArrayRef<uint32_t> RealWeights) {168 // Backend checking assumes any existing weight comes from an `llvm.expect`169 // intrinsic. However, SampleProfiling + ThinLTO add branch weights multiple170 // times, leading to an invalid assumption in our checking. Backend checks171 // should only operate on branch weights that carry the "!expected" field,172 // since they are guaranteed to be added by the LowerExpectIntrinsic pass.173 if (!hasBranchWeightOrigin(I))174 return;175 SmallVector<uint32_t> ExpectedWeights;176 if (!extractBranchWeights(I, ExpectedWeights))177 return;178 verifyMisExpect(I, RealWeights, ExpectedWeights);179}180 181void misexpect::checkFrontendInstrumentation(182 const Instruction &I, ArrayRef<uint32_t> ExpectedWeights) {183 SmallVector<uint32_t> RealWeights;184 if (!extractBranchWeights(I, RealWeights))185 return;186 verifyMisExpect(I, RealWeights, ExpectedWeights);187}188 189void misexpect::checkExpectAnnotations(const Instruction &I,190 ArrayRef<uint32_t> ExistingWeights,191 bool IsFrontend) {192 if (IsFrontend)193 checkFrontendInstrumentation(I, ExistingWeights);194 else195 checkBackendInstrumentation(I, ExistingWeights);196}197