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 "llvm/ADT/SmallVector.h" 15 #include "llvm/IR/Constants.h" 16 #include "llvm/IR/Function.h" 17 #include "llvm/IR/Instructions.h" 18 #include "llvm/IR/LLVMContext.h" 19 #include "llvm/IR/MDBuilder.h" 20 #include "llvm/IR/Metadata.h" 21 #include "llvm/IR/ProfDataUtils.h" 22 23 using namespace llvm; 24 25 namespace { 26 27 // MD_prof nodes have the following layout 28 // 29 // In general: 30 // { String name, Array of i32 } 31 // 32 // In terms of Types: 33 // { MDString, [i32, i32, ...]} 34 // 35 // Concretely for Branch Weights 36 // { "branch_weights", [i32 1, i32 10000]} 37 // 38 // We maintain some constants here to ensure that we access the branch weights 39 // correctly, and can change the behavior in the future if the layout changes 40 41 // the minimum number of operands for MD_prof nodes with branch weights 42 constexpr unsigned MinBWOps = 3; 43 44 // the minimum number of operands for MD_prof nodes with value profiles 45 constexpr unsigned MinVPOps = 5; 46 47 // We may want to add support for other MD_prof types, so provide an abstraction 48 // for checking the metadata type. 49 bool isTargetMD(const MDNode *ProfData, const char *Name, unsigned MinOps) { 50 // TODO: This routine may be simplified if MD_prof used an enum instead of a 51 // string to differentiate the types of MD_prof nodes. 52 if (!ProfData || !Name || MinOps < 2) 53 return false; 54 55 unsigned NOps = ProfData->getNumOperands(); 56 if (NOps < MinOps) 57 return false; 58 59 auto *ProfDataName = dyn_cast<MDString>(ProfData->getOperand(0)); 60 if (!ProfDataName) 61 return false; 62 63 return ProfDataName->getString() == Name; 64 } 65 66 template <typename T, 67 typename = typename std::enable_if<std::is_arithmetic_v<T>>> 68 static void extractFromBranchWeightMD(const MDNode *ProfileData, 69 SmallVectorImpl<T> &Weights) { 70 assert(isBranchWeightMD(ProfileData) && "wrong metadata"); 71 72 unsigned NOps = ProfileData->getNumOperands(); 73 unsigned WeightsIdx = getBranchWeightOffset(ProfileData); 74 assert(WeightsIdx < NOps && "Weights Index must be less than NOps."); 75 Weights.resize(NOps - WeightsIdx); 76 77 for (unsigned Idx = WeightsIdx, E = NOps; Idx != E; ++Idx) { 78 ConstantInt *Weight = 79 mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(Idx)); 80 assert(Weight && "Malformed branch_weight in MD_prof node"); 81 assert(Weight->getValue().getActiveBits() <= (sizeof(T) * 8) && 82 "Too many bits for MD_prof branch_weight"); 83 Weights[Idx - WeightsIdx] = Weight->getZExtValue(); 84 } 85 } 86 87 } // namespace 88 89 namespace llvm { 90 91 bool hasProfMD(const Instruction &I) { 92 return I.hasMetadata(LLVMContext::MD_prof); 93 } 94 95 bool isBranchWeightMD(const MDNode *ProfileData) { 96 return isTargetMD(ProfileData, "branch_weights", MinBWOps); 97 } 98 99 bool isValueProfileMD(const MDNode *ProfileData) { 100 return isTargetMD(ProfileData, "VP", MinVPOps); 101 } 102 103 bool hasBranchWeightMD(const Instruction &I) { 104 auto *ProfileData = I.getMetadata(LLVMContext::MD_prof); 105 return isBranchWeightMD(ProfileData); 106 } 107 108 bool hasCountTypeMD(const Instruction &I) { 109 auto *ProfileData = I.getMetadata(LLVMContext::MD_prof); 110 // Value profiles record count-type information. 111 if (isValueProfileMD(ProfileData)) 112 return true; 113 // Conservatively assume non CallBase instruction only get taken/not-taken 114 // branch probability, so not interpret them as count. 115 return isa<CallBase>(I) && !isBranchWeightMD(ProfileData); 116 } 117 118 bool hasValidBranchWeightMD(const Instruction &I) { 119 return getValidBranchWeightMDNode(I); 120 } 121 122 bool hasBranchWeightOrigin(const Instruction &I) { 123 auto *ProfileData = I.getMetadata(LLVMContext::MD_prof); 124 return hasBranchWeightOrigin(ProfileData); 125 } 126 127 bool hasBranchWeightOrigin(const MDNode *ProfileData) { 128 if (!isBranchWeightMD(ProfileData)) 129 return false; 130 auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(1)); 131 // NOTE: if we ever have more types of branch weight provenance, 132 // we need to check the string value is "expected". For now, we 133 // supply a more generic API, and avoid the spurious comparisons. 134 assert(ProfDataName == nullptr || ProfDataName->getString() == "expected"); 135 return ProfDataName != nullptr; 136 } 137 138 unsigned getBranchWeightOffset(const MDNode *ProfileData) { 139 return hasBranchWeightOrigin(ProfileData) ? 2 : 1; 140 } 141 142 unsigned getNumBranchWeights(const MDNode &ProfileData) { 143 return ProfileData.getNumOperands() - getBranchWeightOffset(&ProfileData); 144 } 145 146 MDNode *getBranchWeightMDNode(const Instruction &I) { 147 auto *ProfileData = I.getMetadata(LLVMContext::MD_prof); 148 if (!isBranchWeightMD(ProfileData)) 149 return nullptr; 150 return ProfileData; 151 } 152 153 MDNode *getValidBranchWeightMDNode(const Instruction &I) { 154 auto *ProfileData = getBranchWeightMDNode(I); 155 if (ProfileData && getNumBranchWeights(*ProfileData) == I.getNumSuccessors()) 156 return ProfileData; 157 return nullptr; 158 } 159 160 void extractFromBranchWeightMD32(const MDNode *ProfileData, 161 SmallVectorImpl<uint32_t> &Weights) { 162 extractFromBranchWeightMD(ProfileData, Weights); 163 } 164 165 void extractFromBranchWeightMD64(const MDNode *ProfileData, 166 SmallVectorImpl<uint64_t> &Weights) { 167 extractFromBranchWeightMD(ProfileData, Weights); 168 } 169 170 bool extractBranchWeights(const MDNode *ProfileData, 171 SmallVectorImpl<uint32_t> &Weights) { 172 if (!isBranchWeightMD(ProfileData)) 173 return false; 174 extractFromBranchWeightMD(ProfileData, Weights); 175 return true; 176 } 177 178 bool extractBranchWeights(const Instruction &I, 179 SmallVectorImpl<uint32_t> &Weights) { 180 auto *ProfileData = I.getMetadata(LLVMContext::MD_prof); 181 return extractBranchWeights(ProfileData, Weights); 182 } 183 184 bool extractBranchWeights(const Instruction &I, uint64_t &TrueVal, 185 uint64_t &FalseVal) { 186 assert((I.getOpcode() == Instruction::Br || 187 I.getOpcode() == Instruction::Select) && 188 "Looking for branch weights on something besides branch, select, or " 189 "switch"); 190 191 SmallVector<uint32_t, 2> Weights; 192 auto *ProfileData = I.getMetadata(LLVMContext::MD_prof); 193 if (!extractBranchWeights(ProfileData, Weights)) 194 return false; 195 196 if (Weights.size() > 2) 197 return false; 198 199 TrueVal = Weights[0]; 200 FalseVal = Weights[1]; 201 return true; 202 } 203 204 bool extractProfTotalWeight(const MDNode *ProfileData, uint64_t &TotalVal) { 205 TotalVal = 0; 206 if (!ProfileData) 207 return false; 208 209 auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0)); 210 if (!ProfDataName) 211 return false; 212 213 if (ProfDataName->getString() == "branch_weights") { 214 unsigned Offset = getBranchWeightOffset(ProfileData); 215 for (unsigned Idx = Offset; Idx < ProfileData->getNumOperands(); ++Idx) { 216 auto *V = mdconst::extract<ConstantInt>(ProfileData->getOperand(Idx)); 217 TotalVal += V->getValue().getZExtValue(); 218 } 219 return true; 220 } 221 222 if (ProfDataName->getString() == "VP" && ProfileData->getNumOperands() > 3) { 223 TotalVal = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2)) 224 ->getValue() 225 .getZExtValue(); 226 return true; 227 } 228 return false; 229 } 230 231 bool extractProfTotalWeight(const Instruction &I, uint64_t &TotalVal) { 232 return extractProfTotalWeight(I.getMetadata(LLVMContext::MD_prof), TotalVal); 233 } 234 235 void setBranchWeights(Instruction &I, ArrayRef<uint32_t> Weights, 236 bool IsExpected) { 237 MDBuilder MDB(I.getContext()); 238 MDNode *BranchWeights = MDB.createBranchWeights(Weights, IsExpected); 239 I.setMetadata(LLVMContext::MD_prof, BranchWeights); 240 } 241 242 void scaleProfData(Instruction &I, uint64_t S, uint64_t T) { 243 assert(T != 0 && "Caller should guarantee"); 244 auto *ProfileData = I.getMetadata(LLVMContext::MD_prof); 245 if (ProfileData == nullptr) 246 return; 247 248 auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0)); 249 if (!ProfDataName || (ProfDataName->getString() != "branch_weights" && 250 ProfDataName->getString() != "VP")) 251 return; 252 253 if (!hasCountTypeMD(I)) 254 return; 255 256 LLVMContext &C = I.getContext(); 257 258 MDBuilder MDB(C); 259 SmallVector<Metadata *, 3> Vals; 260 Vals.push_back(ProfileData->getOperand(0)); 261 APInt APS(128, S), APT(128, T); 262 if (ProfDataName->getString() == "branch_weights" && 263 ProfileData->getNumOperands() > 0) { 264 // Using APInt::div may be expensive, but most cases should fit 64 bits. 265 APInt Val(128, 266 mdconst::dyn_extract<ConstantInt>( 267 ProfileData->getOperand(getBranchWeightOffset(ProfileData))) 268 ->getValue() 269 .getZExtValue()); 270 Val *= APS; 271 Vals.push_back(MDB.createConstant(ConstantInt::get( 272 Type::getInt32Ty(C), Val.udiv(APT).getLimitedValue(UINT32_MAX)))); 273 } else if (ProfDataName->getString() == "VP") 274 for (unsigned i = 1; i < ProfileData->getNumOperands(); i += 2) { 275 // The first value is the key of the value profile, which will not change. 276 Vals.push_back(ProfileData->getOperand(i)); 277 uint64_t Count = 278 mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(i + 1)) 279 ->getValue() 280 .getZExtValue(); 281 // Don't scale the magic number. 282 if (Count == NOMORE_ICP_MAGICNUM) { 283 Vals.push_back(ProfileData->getOperand(i + 1)); 284 continue; 285 } 286 // Using APInt::div may be expensive, but most cases should fit 64 bits. 287 APInt Val(128, Count); 288 Val *= APS; 289 Vals.push_back(MDB.createConstant(ConstantInt::get( 290 Type::getInt64Ty(C), Val.udiv(APT).getLimitedValue()))); 291 } 292 I.setMetadata(LLVMContext::MD_prof, MDNode::get(C, Vals)); 293 } 294 295 } // namespace llvm 296