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