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
109const char *MDProfLabels::BranchWeights = "branch_weights";
110const char *MDProfLabels::ExpectedBranchWeights = "expected";
111const char *MDProfLabels::ValueProfile = "VP";
112const char *MDProfLabels::FunctionEntryCount = "function_entry_count";
113const char *MDProfLabels::SyntheticFunctionEntryCount =
114 "synthetic_function_entry_count";
115const char *MDProfLabels::UnknownBranchWeightsMarker = "unknown";
116const char *llvm::LLVMLoopEstimatedTripCount = "llvm.loop.estimated_trip_count";
117
118bool llvm::hasProfMD(const Instruction &I) {
119 return I.hasMetadata(KindID: LLVMContext::MD_prof);
120}
121
122bool llvm::isBranchWeightMD(const MDNode *ProfileData) {
123 return isTargetMD(ProfData: ProfileData, Name: MDProfLabels::BranchWeights, MinOps: MinBWOps);
124}
125
126bool llvm::isValueProfileMD(const MDNode *ProfileData) {
127 return isTargetMD(ProfData: ProfileData, Name: MDProfLabels::ValueProfile, MinOps: MinVPOps);
128}
129
130bool llvm::hasBranchWeightMD(const Instruction &I) {
131 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
132 return isBranchWeightMD(ProfileData);
133}
134
135static bool hasCountTypeMD(const Instruction &I) {
136 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
137 // Value profiles record count-type information.
138 if (isValueProfileMD(ProfileData))
139 return true;
140 // Conservatively assume non CallBase instruction only get taken/not-taken
141 // branch probability, so not interpret them as count.
142 return isa<CallBase>(Val: I) && !isBranchWeightMD(ProfileData);
143}
144
145bool llvm::hasValidBranchWeightMD(const Instruction &I) {
146 return getValidBranchWeightMDNode(I);
147}
148
149bool llvm::hasBranchWeightOrigin(const Instruction &I) {
150 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
151 return hasBranchWeightOrigin(ProfileData);
152}
153
154bool llvm::hasBranchWeightOrigin(const MDNode *ProfileData) {
155 if (!isBranchWeightMD(ProfileData))
156 return false;
157 auto *ProfDataName = dyn_cast<MDString>(Val: ProfileData->getOperand(I: 1));
158 // NOTE: if we ever have more types of branch weight provenance,
159 // we need to check the string value is "expected". For now, we
160 // supply a more generic API, and avoid the spurious comparisons.
161 assert(ProfDataName == nullptr ||
162 ProfDataName->getString() == MDProfLabels::ExpectedBranchWeights);
163 return ProfDataName != nullptr;
164}
165
166unsigned llvm::getBranchWeightOffset(const MDNode *ProfileData) {
167 return hasBranchWeightOrigin(ProfileData) ? 2 : 1;
168}
169
170unsigned llvm::getNumBranchWeights(const MDNode &ProfileData) {
171 return ProfileData.getNumOperands() - getBranchWeightOffset(ProfileData: &ProfileData);
172}
173
174MDNode *llvm::getBranchWeightMDNode(const Instruction &I) {
175 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
176 if (!isBranchWeightMD(ProfileData))
177 return nullptr;
178 return ProfileData;
179}
180
181MDNode *llvm::getValidBranchWeightMDNode(const Instruction &I) {
182 auto *ProfileData = getBranchWeightMDNode(I);
183 if (ProfileData && getNumBranchWeights(ProfileData: *ProfileData) == I.getNumSuccessors())
184 return ProfileData;
185 return nullptr;
186}
187
188void llvm::extractFromBranchWeightMD32(const MDNode *ProfileData,
189 SmallVectorImpl<uint32_t> &Weights) {
190 extractFromBranchWeightMD(ProfileData, Weights);
191}
192
193void llvm::extractFromBranchWeightMD64(const MDNode *ProfileData,
194 SmallVectorImpl<uint64_t> &Weights) {
195 extractFromBranchWeightMD(ProfileData, Weights);
196}
197
198bool llvm::extractBranchWeights(const MDNode *ProfileData,
199 SmallVectorImpl<uint32_t> &Weights) {
200 if (!isBranchWeightMD(ProfileData))
201 return false;
202 extractFromBranchWeightMD(ProfileData, Weights);
203 return true;
204}
205
206bool llvm::extractBranchWeights(const Instruction &I,
207 SmallVectorImpl<uint32_t> &Weights) {
208 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
209 return extractBranchWeights(ProfileData, Weights);
210}
211
212bool llvm::extractBranchWeights(const Instruction &I, uint64_t &TrueVal,
213 uint64_t &FalseVal) {
214 assert((isa<CondBrInst, SelectInst>(I)) &&
215 "Looking for branch weights on something besides CondBr or Select");
216
217 SmallVector<uint32_t, 2> Weights;
218 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
219 if (!extractBranchWeights(ProfileData, Weights))
220 return false;
221
222 if (Weights.size() > 2)
223 return false;
224
225 TrueVal = Weights[0];
226 FalseVal = Weights[1];
227 return true;
228}
229
230bool llvm::extractProfTotalWeight(const MDNode *ProfileData,
231 uint64_t &TotalVal) {
232 TotalVal = 0;
233 if (!ProfileData)
234 return false;
235
236 auto *ProfDataName = dyn_cast<MDString>(Val: ProfileData->getOperand(I: 0));
237 if (!ProfDataName)
238 return false;
239
240 if (ProfDataName->getString() == MDProfLabels::BranchWeights) {
241 unsigned Offset = getBranchWeightOffset(ProfileData);
242 for (unsigned Idx = Offset; Idx < ProfileData->getNumOperands(); ++Idx) {
243 auto *V = mdconst::extract<ConstantInt>(MD: ProfileData->getOperand(I: Idx));
244 TotalVal += V->getValue().getZExtValue();
245 }
246 return true;
247 }
248
249 if (ProfDataName->getString() == MDProfLabels::ValueProfile &&
250 ProfileData->getNumOperands() > 3) {
251 TotalVal = mdconst::dyn_extract<ConstantInt>(MD: ProfileData->getOperand(I: 2))
252 ->getValue()
253 .getZExtValue();
254 return true;
255 }
256 return false;
257}
258
259bool llvm::extractProfTotalWeight(const Instruction &I, uint64_t &TotalVal) {
260 return extractProfTotalWeight(ProfileData: I.getMetadata(KindID: LLVMContext::MD_prof), TotalVal);
261}
262
263void llvm::setExplicitlyUnknownBranchWeights(Instruction &I,
264 StringRef PassName) {
265 MDBuilder MDB(I.getContext());
266 I.setMetadata(
267 KindID: LLVMContext::MD_prof,
268 Node: MDNode::get(Context&: I.getContext(),
269 MDs: {MDB.createString(Str: MDProfLabels::UnknownBranchWeightsMarker),
270 MDB.createString(Str: PassName)}));
271}
272
273void llvm::setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I,
274 StringRef PassName,
275 const Function *F) {
276 F = F ? F : I.getFunction();
277 assert(F && "Either pass a instruction attached to a Function, or explicitly "
278 "pass the Function that it will be attached to");
279 if (std::optional<uint64_t> EC = F->getEntryCount(); EC && *EC > 0)
280 setExplicitlyUnknownBranchWeights(I, PassName);
281}
282
283MDNode *llvm::getExplicitlyUnknownBranchWeightsIfProfiled(Function &F,
284 StringRef PassName) {
285 if (std::optional<uint64_t> EC = F.getEntryCount(); !EC || *EC == 0)
286 return nullptr;
287 MDBuilder MDB(F.getContext());
288 return MDNode::get(
289 Context&: F.getContext(),
290 MDs: {MDB.createString(Str: MDProfLabels::UnknownBranchWeightsMarker),
291 MDB.createString(Str: PassName)});
292}
293
294void llvm::setExplicitlyUnknownFunctionEntryCount(Function &F,
295 StringRef PassName) {
296 MDBuilder MDB(F.getContext());
297 F.setMetadata(
298 KindID: LLVMContext::MD_prof,
299 Node: MDNode::get(Context&: F.getContext(),
300 MDs: {MDB.createString(Str: MDProfLabels::UnknownBranchWeightsMarker),
301 MDB.createString(Str: PassName)}));
302}
303
304bool llvm::isExplicitlyUnknownProfileMetadata(const MDNode &MD) {
305 if (MD.getNumOperands() != 2)
306 return false;
307 return MD.getOperand(I: 0).equalsStr(Str: MDProfLabels::UnknownBranchWeightsMarker);
308}
309
310bool llvm::hasExplicitlyUnknownBranchWeights(const Instruction &I) {
311 auto *MD = I.getMetadata(KindID: LLVMContext::MD_prof);
312 if (!MD)
313 return false;
314 return isExplicitlyUnknownProfileMetadata(MD: *MD);
315}
316
317void llvm::setBranchWeights(Instruction &I, ArrayRef<uint32_t> Weights,
318 bool IsExpected, bool ElideAllZero) {
319 if (ElideAllZero && llvm::all_of(Range&: Weights, P: equal_to(Arg: 0)) &&
320 getIROptions(C: I.getContext()).elide_all_zero_branch_weights) {
321 I.setMetadata(KindID: LLVMContext::MD_prof, Node: nullptr);
322 return;
323 }
324
325 MDBuilder MDB(I.getContext());
326 MDNode *BranchWeights = MDB.createBranchWeights(Weights, IsExpected);
327 I.setMetadata(KindID: LLVMContext::MD_prof, Node: BranchWeights);
328}
329
330void llvm::setFittedBranchWeights(Instruction &I, ArrayRef<uint64_t> Weights,
331 bool IsExpected, bool ElideAllZero) {
332 setBranchWeights(I, Weights: fitWeights(Weights), IsExpected, ElideAllZero);
333}
334
335SmallVector<uint32_t>
336llvm::downscaleWeights(ArrayRef<uint64_t> Weights,
337 std::optional<uint64_t> KnownMaxCount) {
338 uint64_t MaxCount = KnownMaxCount.has_value() ? KnownMaxCount.value()
339 : *llvm::max_element(Range&: Weights);
340 assert(MaxCount > 0 && "Bad max count");
341 uint64_t Scale = calculateCountScale(MaxCount);
342 SmallVector<uint32_t> DownscaledWeights;
343 for (const auto &ECI : Weights)
344 DownscaledWeights.push_back(Elt: scaleBranchCount(Count: ECI, Scale));
345 return DownscaledWeights;
346}
347
348void llvm::scaleProfData(Instruction &I, uint64_t S, uint64_t T) {
349 assert(T != 0 && "Caller should guarantee");
350 auto *ProfileData = I.getMetadata(KindID: LLVMContext::MD_prof);
351 if (ProfileData == nullptr)
352 return;
353
354 auto *ProfDataName = dyn_cast<MDString>(Val: ProfileData->getOperand(I: 0));
355 if (!ProfDataName ||
356 (ProfDataName->getString() != MDProfLabels::BranchWeights &&
357 ProfDataName->getString() != MDProfLabels::ValueProfile))
358 return;
359
360 if (!hasCountTypeMD(I))
361 return;
362
363 LLVMContext &C = I.getContext();
364
365 MDBuilder MDB(C);
366 SmallVector<Metadata *, 3> Vals;
367 Vals.push_back(Elt: ProfileData->getOperand(I: 0));
368 APInt APS(128, S), APT(128, T);
369 if (ProfDataName->getString() == MDProfLabels::BranchWeights &&
370 ProfileData->getNumOperands() > 0) {
371 // Using APInt::div may be expensive, but most cases should fit 64 bits.
372 APInt Val(128,
373 mdconst::dyn_extract<ConstantInt>(
374 MD: ProfileData->getOperand(I: getBranchWeightOffset(ProfileData)))
375 ->getValue()
376 .getZExtValue());
377 Val *= APS;
378 Vals.push_back(Elt: MDB.createConstant(C: ConstantInt::get(
379 Ty: Type::getInt32Ty(C), V: Val.udiv(RHS: APT).getLimitedValue(UINT32_MAX))));
380 } else if (ProfDataName->getString() == MDProfLabels::ValueProfile)
381 for (unsigned Idx = 1; Idx < ProfileData->getNumOperands(); Idx += 2) {
382 // The first value is the key of the value profile, which will not change.
383 Vals.push_back(Elt: ProfileData->getOperand(I: Idx));
384 uint64_t Count =
385 mdconst::dyn_extract<ConstantInt>(MD: ProfileData->getOperand(I: Idx + 1))
386 ->getValue()
387 .getZExtValue();
388 // Don't scale the magic number.
389 if (Count == NOMORE_ICP_MAGICNUM) {
390 Vals.push_back(Elt: ProfileData->getOperand(I: Idx + 1));
391 continue;
392 }
393 // Using APInt::div may be expensive, but most cases should fit 64 bits.
394 APInt Val(128, Count);
395 Val *= APS;
396 Vals.push_back(Elt: MDB.createConstant(C: ConstantInt::get(
397 Ty: Type::getInt64Ty(C), V: Val.udiv(RHS: APT).getLimitedValue())));
398 }
399 I.setMetadata(KindID: LLVMContext::MD_prof, Node: MDNode::get(Context&: C, MDs: Vals));
400}
401
402void llvm::applyProfMetadataIfEnabled(
403 Value *V, llvm::function_ref<void(Instruction *)> setMetadataCallback) {
404 if (!ProfcheckDisableMetadataFixes) {
405 if (Instruction *Inst = dyn_cast<Instruction>(Val: V)) {
406 setMetadataCallback(Inst);
407 }
408 }
409}
410