1//===- ProfileVerify.cpp - Verify profile info for testing ----------------===//
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#include "llvm/Transforms/Utils/ProfileVerify.h"
10#include "llvm/ADT/DynamicAPInt.h"
11#include "llvm/ADT/STLExtras.h"
12#include "llvm/Analysis/BranchProbabilityInfo.h"
13#include "llvm/IR/Analysis.h"
14#include "llvm/IR/Constants.h"
15#include "llvm/IR/Dominators.h"
16#include "llvm/IR/Function.h"
17#include "llvm/IR/GlobalValue.h"
18#include "llvm/IR/GlobalVariable.h"
19#include "llvm/IR/Instructions.h"
20#include "llvm/IR/IntrinsicInst.h"
21#include "llvm/IR/LLVMContext.h"
22#include "llvm/IR/MDBuilder.h"
23#include "llvm/IR/Module.h"
24#include "llvm/IR/PassManager.h"
25#include "llvm/IR/ProfDataUtils.h"
26#include "llvm/ProfileData/InstrProf.h"
27#include "llvm/Support/BranchProbability.h"
28#include "llvm/Support/Casting.h"
29#include "llvm/Support/CommandLine.h"
30
31using namespace llvm;
32static cl::opt<int64_t>
33 DefaultFunctionEntryCount("profcheck-default-function-entry-count",
34 cl::init(Val: 1000));
35static cl::opt<bool>
36 AnnotateSelect("profcheck-annotate-select", cl::init(Val: true),
37 cl::desc("Also inject (if missing) and verify MD_prof for "
38 "`select` instructions"));
39static cl::opt<bool>
40 WeightsForTest("profcheck-weights-for-test", cl::init(Val: false),
41 cl::desc("Generate weights with small values for tests."));
42
43static cl::opt<uint32_t> SelectTrueWeight(
44 "profcheck-default-select-true-weight", cl::init(Val: 2U),
45 cl::desc("When annotating `select` instructions, this value will be used "
46 "for the first ('true') case."));
47static cl::opt<uint32_t> SelectFalseWeight(
48 "profcheck-default-select-false-weight", cl::init(Val: 3U),
49 cl::desc("When annotating `select` instructions, this value will be used "
50 "for the second ('false') case."));
51static cl::opt<bool> AnnotateIndirectCalls(
52 "profcheck-annotate-indirect-calls", cl::init(Val: false),
53 cl::desc("Also inject (if missing) and verify MD_prof for indirect calls"));
54static cl::opt<bool> AnnotateMemoryOperations(
55 "profcheck-annotate-mem-ops", cl::init(Val: false),
56 cl::desc(
57 "Also inject (if missing) and verify MD_prof for memory operations"));
58namespace {
59class ProfileInjector {
60 Function &F;
61 FunctionAnalysisManager &FAM;
62
63public:
64 static const Instruction *
65 getTerminatorBenefitingFromMDProf(const BasicBlock &BB) {
66 if (succ_size(BB: &BB) < 2)
67 return nullptr;
68 auto *Term = BB.getTerminator();
69 return (isa<CondBrInst>(Val: Term) || isa<SwitchInst>(Val: Term) ||
70 isa<IndirectBrInst>(Val: Term) || isa<CallBrInst>(Val: Term))
71 ? Term
72 : nullptr;
73 }
74
75 static Instruction *getTerminatorBenefitingFromMDProf(BasicBlock &BB) {
76 return const_cast<Instruction *>(
77 getTerminatorBenefitingFromMDProf(BB: const_cast<const BasicBlock &>(BB)));
78 }
79
80 ProfileInjector(Function &F, FunctionAnalysisManager &FAM) : F(F), FAM(FAM) {}
81 bool inject();
82};
83
84bool isAsmOnly(const Function &F) {
85 if (!F.hasFnAttribute(Kind: Attribute::AttrKind::Naked))
86 return false;
87 for (const auto &BB : F)
88 for (const auto &I : drop_end(RangeOrContainer: BB)) {
89 const auto *CB = dyn_cast<CallBase>(Val: &I);
90 if (!CB || !CB->isInlineAsm())
91 return false;
92 }
93 return true;
94}
95
96void emitProfileError(StringRef Msg, Function &F) {
97 F.getContext().emitError(ErrorStr: "Profile verification failed for function '" +
98 F.getName() + "': " + Msg);
99}
100
101} // namespace
102
103// FIXME: currently this injects only for terminators. Select isn't yet
104// supported.
105bool ProfileInjector::inject() {
106 // skip purely asm functions
107 if (isAsmOnly(F))
108 return false;
109 // Get whatever branch probability info can be derived from the given IR -
110 // whether it has or not metadata. The main intention for this pass is to
111 // ensure that other passes don't drop or "forget" to update MD_prof. We do
112 // this as a mode in which lit tests would run. We want to avoid changing the
113 // behavior of those tests. A pass may use BPI (or BFI, which is computed from
114 // BPI). If no metadata is present, BPI is guesstimated by
115 // BranchProbabilityAnalysis. The injector (this pass) only persists whatever
116 // information the analysis provides, in other words, the pass being tested
117 // will get the same BPI it does if the injector wasn't running.
118 auto &BPI = FAM.getResult<BranchProbabilityAnalysis>(IR&: F);
119
120 // Inject a function count if there's none. It's reasonable for a pass to
121 // want to clear the MD_prof of a function with zero entry count. If the
122 // original profile (iFDO or AFDO) is empty for a function, it's simpler to
123 // require assigning it the 0-entry count explicitly than to mark every branch
124 // as cold (we do want some explicit information in the spirit of what this
125 // verifier wants to achieve - make dropping / corrupting MD_prof
126 // unit-testable)
127 if (!F.getEntryCount())
128 F.setEntryCount(Count: DefaultFunctionEntryCount);
129 // If there is an entry count that's 0, then don't bother injecting. We won't
130 // verify these either.
131 if (*F.getEntryCount() == 0)
132 return false;
133 bool Changed = false;
134 // Cycle through the weights list. If we didn't, tests with more than (say)
135 // one conditional branch would have the same !prof metadata on all of them,
136 // and numerically that may make for a poor unit test.
137 uint32_t WeightsForTestOffset = 0;
138 for (auto &BB : F) {
139 for (Instruction &I : BB) {
140 if (I.getMetadata(KindID: LLVMContext::MD_prof))
141 continue;
142 if (AnnotateSelect) {
143 if (auto *SI = dyn_cast<SelectInst>(Val: &I)) {
144 if (SI->getCondition()->getType()->isVectorTy())
145 continue;
146 setBranchWeights(I, Weights: {SelectTrueWeight, SelectFalseWeight},
147 /*IsExpected=*/false);
148 Changed = true;
149 }
150 }
151 if (AnnotateMemoryOperations) {
152 if (auto *MI = dyn_cast<MemIntrinsic>(Val: &I)) {
153 if (isa<ConstantInt>(Val: MI->getLength()))
154 continue;
155 annotateValueSite(M&: *F.getParent(), Inst&: *MI, VDs: {{.Value: 19797, .Count: 2}, {.Value: 18770, .Count: 3}}, Sum: 10,
156 ValueKind: InstrProfValueKind::IPVK_MemOPSize, MaxMDCount: 30);
157 Changed = true;
158 }
159 }
160 if (AnnotateIndirectCalls) {
161 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
162 if (!CB->isIndirectCall())
163 continue;
164 annotateValueSite(M&: *F.getParent(), Inst&: *CB, VDs: {{.Value: 19797, .Count: 2}, {.Value: 18770, .Count: 3}}, Sum: 10,
165 ValueKind: InstrProfValueKind::IPVK_IndirectCallTarget, MaxMDCount: 30);
166 Changed = true;
167 }
168 }
169 }
170 auto *Term = getTerminatorBenefitingFromMDProf(BB);
171 if (!Term || Term->getMetadata(KindID: LLVMContext::MD_prof))
172 continue;
173 SmallVector<BranchProbability> Probs;
174
175 SmallVector<uint32_t> Weights;
176 Weights.reserve(N: Term->getNumSuccessors());
177 if (WeightsForTest) {
178 static const std::array Primes{3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
179 37, 41, 43, 47, 53, 59, 61, 67, 71};
180 for (uint32_t I = 0, E = Term->getNumSuccessors(); I < E; ++I)
181 Weights.emplace_back(
182 Args: Primes[(WeightsForTestOffset + I) % Primes.size()]);
183 ++WeightsForTestOffset;
184 } else {
185 Probs.reserve(N: Term->getNumSuccessors());
186 for (auto I = 0U, E = Term->getNumSuccessors(); I < E; ++I)
187 Probs.emplace_back(Args: BPI.getEdgeProbability(Src: &BB, Dst: Term->getSuccessor(Idx: I)));
188
189 assert(llvm::find_if(Probs,
190 [](const BranchProbability &P) {
191 return P.isUnknown();
192 }) == Probs.end() &&
193 "All branch probabilities should be valid");
194 const auto *FirstZeroDenominator =
195 find_if(Range&: Probs, P: [](const BranchProbability &P) {
196 return P.getDenominator() == 0;
197 });
198 (void)FirstZeroDenominator;
199 assert(FirstZeroDenominator == Probs.end());
200 const auto *FirstNonZeroNumerator = find_if(
201 Range&: Probs, P: [](const BranchProbability &P) { return !P.isZero(); });
202 assert(FirstNonZeroNumerator != Probs.end());
203 DynamicAPInt LCM(Probs[0].getDenominator());
204 DynamicAPInt GCD(FirstNonZeroNumerator->getNumerator());
205 for (const auto &Prob : drop_begin(RangeOrContainer&: Probs)) {
206 if (!Prob.getNumerator())
207 continue;
208 LCM = llvm::lcm(A: LCM, B: DynamicAPInt(Prob.getDenominator()));
209 GCD = llvm::gcd(A: GCD, B: DynamicAPInt(Prob.getNumerator()));
210 }
211 for (const auto &Prob : Probs) {
212 DynamicAPInt W =
213 (Prob.getNumerator() * LCM / GCD) / Prob.getDenominator();
214 Weights.emplace_back(Args: static_cast<uint32_t>((int64_t)W));
215 }
216 }
217 setBranchWeights(I&: *Term, Weights, /*IsExpected=*/false);
218 Changed = true;
219 }
220 return Changed;
221}
222
223PreservedAnalyses ProfileInjectorPass::run(Function &F,
224 FunctionAnalysisManager &FAM) {
225 ProfileInjector PI(F, FAM);
226 if (!PI.inject())
227 return PreservedAnalyses::all();
228
229 return PreservedAnalyses::none();
230}
231
232PreservedAnalyses ProfileVerifierPass::run(Module &M,
233 ModuleAnalysisManager &MAM) {
234 auto PopulateIgnoreList = [&](StringRef GVName) {
235 if (const auto *CT = M.getGlobalVariable(Name: GVName))
236 if (CT->hasInitializer())
237 if (const auto *CA =
238 dyn_cast_if_present<ConstantArray>(Val: CT->getInitializer()))
239 for (const auto &Elt : CA->operands())
240 if (const auto *CS = dyn_cast<ConstantStruct>(Val: Elt))
241 if (CS->getNumOperands() >= 2 && CS->getOperand(i_nocapture: 1))
242 if (const auto *F = dyn_cast<Function>(
243 Val: CS->getOperand(i_nocapture: 1)->stripPointerCasts()))
244 IgnoreList.insert(V: F);
245 };
246 PopulateIgnoreList("llvm.global_ctors");
247 PopulateIgnoreList("llvm.global_dtors");
248
249 // expose the function-level run as public through a wrapper, so we can use
250 // pass manager mechanisms dealing with declarations and with composing the
251 // returned PreservedAnalyses values.
252 struct Wrapper : OptionalPassInfoMixin<Wrapper> {
253 ProfileVerifierPass &PVP;
254 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM) {
255 return PVP.run(F, FAM);
256 }
257 explicit Wrapper(ProfileVerifierPass &PVP) : PVP(PVP) {}
258 };
259
260 return createModuleToFunctionPassAdaptor(Pass: Wrapper(*this)).run(M, AM&: MAM);
261}
262
263PreservedAnalyses ProfileVerifierPass::run(Function &F,
264 FunctionAnalysisManager &FAM) {
265 // skip purely asm functions
266 if (isAsmOnly(F))
267 return PreservedAnalyses::all();
268 if (IgnoreList.contains(V: &F))
269 return PreservedAnalyses::all();
270
271 const auto EntryCount = F.getEntryCount();
272 if (!EntryCount) {
273 auto *MD = F.getMetadata(KindID: LLVMContext::MD_prof);
274 if (!MD || !isExplicitlyUnknownProfileMetadata(MD: *MD)) {
275 emitProfileError(Msg: "function entry count missing (set to 0 if cold)", F);
276 return PreservedAnalyses::all();
277 }
278 } else if (*EntryCount == 0) {
279 return PreservedAnalyses::all();
280 }
281 for (const auto &BB : F) {
282 for (const auto &I : BB) {
283 if (I.getMetadata(KindID: LLVMContext::MD_prof))
284 continue;
285 if (AnnotateSelect) {
286 if (auto *SI = dyn_cast<SelectInst>(Val: &I)) {
287 if (SI->getCondition()->getType()->isVectorTy())
288 continue;
289 emitProfileError(Msg: "select annotation missing", F);
290 }
291 }
292 if (AnnotateMemoryOperations) {
293 if (auto *MI = dyn_cast<MemIntrinsic>(Val: &I)) {
294 if (isa<ConstantInt>(Val: MI->getLength()))
295 continue;
296 emitProfileError(Msg: "memory operation annotation missing", F);
297 }
298 }
299 if (AnnotateIndirectCalls) {
300 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
301 if (!CB->isIndirectCall())
302 continue;
303 emitProfileError(Msg: "indirect call annotation missing", F);
304 }
305 }
306 }
307 if (const auto *Term =
308 ProfileInjector::getTerminatorBenefitingFromMDProf(BB))
309 if (!Term->getMetadata(KindID: LLVMContext::MD_prof))
310 emitProfileError(Msg: "branch annotation missing", F);
311 }
312 return PreservedAnalyses::all();
313}
314