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