1//===- ProfDataUtils.cpp - Utility functions for MD_prof Metadata ---------===//
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 file implements utilities for working with Profiling Metadata.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/IR/ProfDataUtils.h"
14#include "IROptions.h"
15
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/STLFunctionalExtras.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/IR/Constants.h"
20#include "llvm/IR/Function.h"
21#include "llvm/IR/Instructions.h"
22#include "llvm/IR/LLVMContext.h"
23#include "llvm/IR/MDBuilder.h"
24#include "llvm/IR/Metadata.h"
25#include "llvm/Support/CommandLine.h"
26
27using namespace llvm;
28
29namespace llvm {
30extern cl::opt<bool> ProfcheckDisableMetadataFixes;
31}
32
33// MD_prof nodes have the following layout
34//
35// In general:
36// { String name, Array of i32 }
37//
38// In terms of Types:
39// { MDString, [i32, i32, ...]}
40//
41// Concretely for Branch Weights
42// { "branch_weights", [i32 1, i32 10000]}
43//
44// We maintain some constants here to ensure that we access the branch weights
45// correctly, and can change the behavior in the future if the layout changes
46
47// the minimum number of operands for MD_prof nodes with branch weights
48static constexpr unsigned MinBWOps = 3;
49
50// the minimum number of operands for MD_prof nodes with value profiles
51static constexpr unsigned MinVPOps = 5;
52
53// We may want to add support for other MD_prof types, so provide an abstraction
54// for checking the metadata type.
55static bool isTargetMD(const MDNode *ProfData, const char *Name,
56 unsigned MinOps) {
57 // TODO: This routine may be simplified if MD_prof used an enum instead of a
58 // string to differentiate the types of MD_prof nodes.
59 if (!ProfData || !Name || MinOps < 2)
60 return false;
61
62 unsigned NOps = ProfData->getNumOperands();
63 if (NOps < MinOps)
64 return false;
65
66 auto *ProfDataName = dyn_cast<MDString>(Val: ProfData->getOperand(I: 0));
67 if (!ProfDataName)
68 return false;
69
70 return ProfDataName->getString() == Name;
71}
72
73template <typename T,
74 typename = typename std::enable_if<std::is_arithmetic_v<T>>>
75static void extractFromBranchWeightMD(const MDNode *ProfileData,
76 SmallVectorImpl<T> &Weights) {
77 assert(isBranchWeightMD(ProfileData) && "wrong metadata");
78
79 unsigned NOps = ProfileData->getNumOperands();
80 unsigned WeightsIdx = getBranchWeightOffset(ProfileData);
81 assert(WeightsIdx < NOps && "Weights Index must be less than NOps.");
82 Weights.resize(NOps - WeightsIdx);
83
84 for (unsigned Idx = WeightsIdx, E = NOps; Idx != E; ++Idx) {
85 ConstantInt *Weight =
86 mdconst::dyn_extract<ConstantInt>(MD: ProfileData->getOperand(I: Idx));
87 assert(Weight && "Malformed branch_weight in MD_prof node");
88 assert(Weight->getValue().getActiveBits() <= (sizeof(T) * 8) &&
89 "Too many bits for MD_prof branch_weight");
90 Weights[Idx - WeightsIdx] = Weight->getZExtValue();
91 }
92}
93
94/// Push the weights right to fit in uint32_t.
95SmallVector<uint32_t> llvm::fitWeights(ArrayRef<uint64_t> Weights) {
96 SmallVector<uint32_t> Ret;
97 Ret.reserve(N: Weights.size());
98 uint64_t Max = *llvm::max_element(Range&: Weights);
99 if (Max > UINT_MAX) {
100 unsigned Offset = 32 - llvm::countl_zero(Val: Max);
101 for (const uint64_t &Value : Weights)
102 Ret.push_back(Elt: static_cast<uint32_t>(Value >> Offset));
103 } else {
104 append_range(C&: Ret, R&: Weights);
105 }
106 return Ret;
107}
108
109// This option is mainly used when constructing the pass pipeline, but needs to
110// be defined here so that it can also control all zero branch weight elision
111// and avoid layering issues.
112namespace llvm {
113cl::opt<bool> EnableProfcheckInPipeline(
114 "enable-profcheck-in-pipeline", cl::init(Val: false),
115 cl::desc("Adds profile verification to the pipeline, erroring if profile "
116 "information is dropped."));
117} // namespace llvm
118const char *MDProfLabels::BranchWeights = "branch_weights";
119const char *MDProfLabels::ExpectedBranchWeights = "expected";
120const char *MDProfLabels::ValueProfile = "VP";
121const char *MDProfLabels::FunctionEntryCount = "function_entry_count";
122const char *MDProfLabels::UnknownBranchWeightsMarker = "unknown";
123const char *llvm::LLVMLoopEstimatedTripCount = "llvm.loop.estimated_trip_count";
124
125bool llvm::hasProfMD(const Instruction &I) {
126 return I.hasMetadata(KindID: LLVMContext::MD_prof);
127}
128
129bool llvm::isBranchWeightMD(const MDNode *ProfileData) {
130 return isTargetMD(ProfData: ProfileData, Name: MDProfLabels::BranchWeights, MinOps: MinBWOps);
131}
132
133bool llvm::isValueProfileMD(const MDNode *ProfileData) {
134 return isTargetMD(ProfData: ProfileData, Name: MDProfLabels::ValueProfile, MinOps: MinVPOps);
135}
136
137bool llvm::hasBranchWeightMD(const Instruction &I) {
138 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
139 return isBranchWeightMD(ProfileData);
140}
141
142static bool hasCountTypeMD(const Instruction &I) {
143 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
144 // Value profiles record count-type information.
145 if (isValueProfileMD(ProfileData))
146 return true;
147 // Conservatively assume non CallBase instruction only get taken/not-taken
148 // branch probability, so not interpret them as count.
149 return isa<CallBase>(Val: I) && !isBranchWeightMD(ProfileData);
150}
151
152bool llvm::hasValidBranchWeightMD(const Instruction &I) {
153 return getValidBranchWeightMDNode(I);
154}
155
156bool llvm::hasBranchWeightOrigin(const Instruction &I) {
157 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
158 return hasBranchWeightOrigin(ProfileData);
159}
160
161bool llvm::hasBranchWeightOrigin(const MDNode *ProfileData) {
162 if (!isBranchWeightMD(ProfileData))
163 return false;
164 auto *ProfDataName = dyn_cast<MDString>(Val: ProfileData->getOperand(I: 1));
165 // NOTE: if we ever have more types of branch weight provenance,
166 // we need to check the string value is "expected". For now, we
167 // supply a more generic API, and avoid the spurious comparisons.
168 assert(ProfDataName == nullptr ||
169 ProfDataName->getString() == MDProfLabels::ExpectedBranchWeights);
170 return ProfDataName != nullptr;
171}
172
173unsigned llvm::getBranchWeightOffset(const MDNode *ProfileData) {
174 return hasBranchWeightOrigin(ProfileData) ? 2 : 1;
175}
176
177unsigned llvm::getNumBranchWeights(const MDNode &ProfileData) {
178 return ProfileData.getNumOperands() - getBranchWeightOffset(ProfileData: &ProfileData);
179}
180
181MDNode *llvm::getBranchWeightMDNode(const Instruction &I) {
182 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
183 if (!isBranchWeightMD(ProfileData))
184 return nullptr;
185 return ProfileData;
186}
187
188MDNode *llvm::getValidBranchWeightMDNode(const Instruction &I) {
189 auto *ProfileData = getBranchWeightMDNode(I);
190 if (ProfileData && getNumBranchWeights(ProfileData: *ProfileData) == I.getNumSuccessors())
191 return ProfileData;
192 return nullptr;
193}
194
195void llvm::extractFromBranchWeightMD32(const MDNode *ProfileData,
196 SmallVectorImpl<uint32_t> &Weights) {
197 extractFromBranchWeightMD(ProfileData, Weights);
198}
199
200void llvm::extractFromBranchWeightMD64(const MDNode *ProfileData,
201 SmallVectorImpl<uint64_t> &Weights) {
202 extractFromBranchWeightMD(ProfileData, Weights);
203}
204
205bool llvm::extractBranchWeights(const MDNode *ProfileData,
206 SmallVectorImpl<uint32_t> &Weights) {
207 if (!isBranchWeightMD(ProfileData))
208 return false;
209 extractFromBranchWeightMD(ProfileData, Weights);
210 return true;
211}
212
213bool llvm::extractBranchWeights(const Instruction &I,
214 SmallVectorImpl<uint32_t> &Weights) {
215 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
216 return extractBranchWeights(ProfileData, Weights);
217}
218
219bool llvm::extractBranchWeights(const Instruction &I, uint64_t &TrueVal,
220 uint64_t &FalseVal) {
221 assert((isa<CondBrInst, SelectInst>(I)) &&
222 "Looking for branch weights on something besides CondBr or Select");
223
224 SmallVector<uint32_t, 2> Weights;
225 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
226 if (!extractBranchWeights(ProfileData, Weights))
227 return false;
228
229 if (Weights.size() > 2)
230 return false;
231
232 TrueVal = Weights[0];
233 FalseVal = Weights[1];
234 return true;
235}
236
237bool llvm::extractProfTotalWeight(const MDNode *ProfileData,
238 uint64_t &TotalVal) {
239 TotalVal = 0;
240 if (!ProfileData)
241 return false;
242
243 auto *ProfDataName = dyn_cast<MDString>(Val: ProfileData->getOperand(I: 0));
244 if (!ProfDataName)
245 return false;
246
247 if (ProfDataName->getString() == MDProfLabels::BranchWeights) {
248 unsigned Offset = getBranchWeightOffset(ProfileData);
249 for (unsigned Idx = Offset; Idx < ProfileData->getNumOperands(); ++Idx) {
250 auto *V = mdconst::extract<ConstantInt>(MD: ProfileData->getOperand(I: Idx));
251 TotalVal += V->getValue().getZExtValue();
252 }
253 return true;
254 }
255
256 if (ProfDataName->getString() == MDProfLabels::ValueProfile &&
257 ProfileData->getNumOperands() > 3) {
258 TotalVal = mdconst::dyn_extract<ConstantInt>(MD: ProfileData->getOperand(I: 2))
259 ->getValue()
260 .getZExtValue();
261 return true;
262 }
263 return false;
264}
265
266bool llvm::extractProfTotalWeight(const Instruction &I, uint64_t &TotalVal) {
267 return extractProfTotalWeight(ProfileData: I.getMetadata(KindID: LLVMContext::MD_prof), TotalVal);
268}
269
270void llvm::setExplicitlyUnknownBranchWeights(Instruction &I,
271 StringRef PassName) {
272 MDBuilder MDB(I.getContext());
273 I.setMetadata(
274 KindID: LLVMContext::MD_prof,
275 Node: MDNode::get(Context&: I.getContext(),
276 MDs: {MDB.createString(Str: MDProfLabels::UnknownBranchWeightsMarker),
277 MDB.createString(Str: PassName)}));
278}
279
280void llvm::setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I,
281 StringRef PassName,
282 const Function *F) {
283 F = F ? F : I.getFunction();
284 assert(F && "Either pass a instruction attached to a Function, or explicitly "
285 "pass the Function that it will be attached to");
286 if (std::optional<uint64_t> EC = F->getEntryCount(); EC && *EC > 0)
287 setExplicitlyUnknownBranchWeights(I, PassName);
288}
289
290MDNode *llvm::getExplicitlyUnknownBranchWeightsIfProfiled(Function &F,
291 StringRef PassName) {
292 if (std::optional<uint64_t> EC = F.getEntryCount(); !EC || *EC == 0)
293 return nullptr;
294 MDBuilder MDB(F.getContext());
295 return MDNode::get(
296 Context&: F.getContext(),
297 MDs: {MDB.createString(Str: MDProfLabels::UnknownBranchWeightsMarker),
298 MDB.createString(Str: PassName)});
299}
300
301void llvm::setExplicitlyUnknownFunctionEntryCount(Function &F,
302 StringRef PassName) {
303 MDBuilder MDB(F.getContext());
304 F.setMetadata(
305 KindID: LLVMContext::MD_prof,
306 Node: MDNode::get(Context&: F.getContext(),
307 MDs: {MDB.createString(Str: MDProfLabels::UnknownBranchWeightsMarker),
308 MDB.createString(Str: PassName)}));
309}
310
311bool llvm::isExplicitlyUnknownProfileMetadata(const MDNode &MD) {
312 if (MD.getNumOperands() != 2)
313 return false;
314 return MD.getOperand(I: 0).equalsStr(Str: MDProfLabels::UnknownBranchWeightsMarker);
315}
316
317bool llvm::hasExplicitlyUnknownBranchWeights(const Instruction &I) {
318 auto *MD = I.getMetadata(KindID: LLVMContext::MD_prof);
319 if (!MD)
320 return false;
321 return isExplicitlyUnknownProfileMetadata(MD: *MD);
322}
323
324void llvm::setBranchWeights(Instruction &I, ArrayRef<uint32_t> Weights,
325 bool IsExpected, bool ElideAllZero) {
326 if ((getIROptions(C: I.getContext()).elide_all_zero_branch_weights &&
327 !EnableProfcheckInPipeline && ElideAllZero) &&
328 llvm::all_of(Range&: Weights, P: equal_to(Arg: 0))) {
329 I.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
330 return;
331 }
332
333 MDBuilder MDB(I.getContext());
334 MDNode *BranchWeights = MDB.createBranchWeights(Weights, IsExpected);
335 I.setMetadata(KindID: LLVMContext::MD_prof, Node: BranchWeights);
336}
337
338void llvm::setFittedBranchWeights(Instruction &I, ArrayRef<uint64_t> Weights,
339 bool IsExpected, bool ElideAllZero) {
340 setBranchWeights(I, Weights: fitWeights(Weights), IsExpected, ElideAllZero);
341}
342
343SmallVector<uint32_t>
344llvm::downscaleWeights(ArrayRef<uint64_t> Weights,
345 std::optional<uint64_t> KnownMaxCount) {
346 uint64_t MaxCount = KnownMaxCount.has_value() ? KnownMaxCount.value()
347 : *llvm::max_element(Range&: Weights);
348 assert(MaxCount > 0 && "Bad max count");
349 uint64_t Scale = calculateCountScale(MaxCount);
350 SmallVector<uint32_t> DownscaledWeights;
351 for (const auto &ECI : Weights)
352 DownscaledWeights.push_back(Elt: scaleBranchCount(Count: ECI, Scale));
353 return DownscaledWeights;
354}
355
356void llvm::scaleProfData(Instruction &I, uint64_t S, uint64_t T) {
357 assert(T != 0 && "Caller should guarantee");
358 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
359 if (ProfileData == nullptr)
360 return;
361
362 auto *ProfDataName = dyn_cast<MDString>(Val: ProfileData->getOperand(I: 0));
363 if (!ProfDataName ||
364 (ProfDataName->getString() != MDProfLabels::BranchWeights &&
365 ProfDataName->getString() != MDProfLabels::ValueProfile))
366 return;
367
368 if (!hasCountTypeMD(I))
369 return;
370
371 LLVMContext &C = I.getContext();
372
373 MDBuilder MDB(C);
374 SmallVector<Metadata *, 3> Vals;
375 Vals.push_back(Elt: ProfileData->getOperand(I: 0));
376 APInt APS(128, S), APT(128, T);
377 if (ProfDataName->getString() == MDProfLabels::BranchWeights &&
378 ProfileData->getNumOperands() > 0) {
379 // Using APInt::div may be expensive, but most cases should fit 64 bits.
380 APInt Val(128,
381 mdconst::dyn_extract<ConstantInt>(
382 MD: ProfileData->getOperand(I: getBranchWeightOffset(ProfileData)))
383 ->getValue()
384 .getZExtValue());
385 Val *= APS;
386 Vals.push_back(Elt: MDB.createConstant(C: ConstantInt::get(
387 Ty: Type::getInt32Ty(C), V: Val.udiv(RHS: APT).getLimitedValue(UINT32_MAX))));
388 } else if (ProfDataName->getString() == MDProfLabels::ValueProfile)
389 for (unsigned Idx = 1; Idx < ProfileData->getNumOperands(); Idx += 2) {
390 // The first value is the key of the value profile, which will not change.
391 Vals.push_back(Elt: ProfileData->getOperand(I: Idx));
392 uint64_t Count =
393 mdconst::dyn_extract<ConstantInt>(MD: ProfileData->getOperand(I: Idx + 1))
394 ->getValue()
395 .getZExtValue();
396 // Don't scale the magic number.
397 if (Count == NOMORE_ICP_MAGICNUM) {
398 Vals.push_back(Elt: ProfileData->getOperand(I: Idx + 1));
399 continue;
400 }
401 // Using APInt::div may be expensive, but most cases should fit 64 bits.
402 APInt Val(128, Count);
403 Val *= APS;
404 Vals.push_back(Elt: MDB.createConstant(C: ConstantInt::get(
405 Ty: Type::getInt64Ty(C), V: Val.udiv(RHS: APT).getLimitedValue())));
406 }
407 I.setMetadata(KindID: LLVMContext::MD_prof, Node: MDNode::get(Context&: C, MDs: Vals));
408}
409
410void llvm::applyProfMetadataIfEnabled(
411 Value *V, llvm::function_ref<void(Instruction *)> setMetadataCallback) {
412 if (!ProfcheckDisableMetadataFixes) {
413 if (Instruction *Inst = dyn_cast<Instruction>(Val: V)) {
414 setMetadataCallback(Inst);
415 }
416 }
417}
418