1//===- SampleProf.h - Sampling profiling format support ---------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains common definitions used in the reading and writing of 11// sample profile data. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_PROFILEDATA_SAMPLEPROF_H 16#define LLVM_PROFILEDATA_SAMPLEPROF_H 17 18#include "llvm/ADT/DenseSet.h" 19#include "llvm/ADT/SmallVector.h" 20#include "llvm/ADT/StringMap.h" 21#include "llvm/ADT/StringRef.h" 22#include "llvm/IR/Function.h" 23#include "llvm/IR/GlobalValue.h" 24#include "llvm/IR/Module.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/ErrorOr.h" 27#include "llvm/Support/MathExtras.h" 28#include <algorithm> 29#include <cstdint> 30#include <map> 31#include <string> 32#include <system_error> 33#include <utility> 34 35namespace llvm { 36 37class raw_ostream; 38 39const std::error_category &sampleprof_category(); 40 41enum class sampleprof_error { 42 success = 0, 43 bad_magic, 44 unsupported_version, 45 too_large, 46 truncated, 47 malformed, 48 unrecognized_format, 49 unsupported_writing_format, 50 truncated_name_table, 51 not_implemented, 52 counter_overflow 53}; 54 55inline std::error_code make_error_code(sampleprof_error E) { 56 return std::error_code(static_cast<int>(E), sampleprof_category()); 57} 58 59inline sampleprof_error MergeResult(sampleprof_error &Accumulator, 60 sampleprof_error Result) { 61 // Prefer first error encountered as later errors may be secondary effects of 62 // the initial problem. 63 if (Accumulator == sampleprof_error::success && 64 Result != sampleprof_error::success) 65 Accumulator = Result; 66 return Accumulator; 67} 68 69} // end namespace llvm 70 71namespace std { 72 73template <> 74struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {}; 75 76} // end namespace std 77 78namespace llvm { 79namespace sampleprof { 80 81static inline uint64_t SPMagic() { 82 return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) | 83 uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) | 84 uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) | 85 uint64_t('2') << (64 - 56) | uint64_t(0xff); 86} 87 88static inline uint64_t SPVersion() { return 103; } 89 90/// Represents the relative location of an instruction. 91/// 92/// Instruction locations are specified by the line offset from the 93/// beginning of the function (marked by the line where the function 94/// header is) and the discriminator value within that line. 95/// 96/// The discriminator value is useful to distinguish instructions 97/// that are on the same line but belong to different basic blocks 98/// (e.g., the two post-increment instructions in "if (p) x++; else y++;"). 99struct LineLocation { 100 LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {} 101 102 void print(raw_ostream &OS) const; 103 void dump() const; 104 105 bool operator<(const LineLocation &O) const { 106 return LineOffset < O.LineOffset || 107 (LineOffset == O.LineOffset && Discriminator < O.Discriminator); 108 } 109 110 uint32_t LineOffset; 111 uint32_t Discriminator; 112}; 113 114raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc); 115 116/// Representation of a single sample record. 117/// 118/// A sample record is represented by a positive integer value, which 119/// indicates how frequently was the associated line location executed. 120/// 121/// Additionally, if the associated location contains a function call, 122/// the record will hold a list of all the possible called targets. For 123/// direct calls, this will be the exact function being invoked. For 124/// indirect calls (function pointers, virtual table dispatch), this 125/// will be a list of one or more functions. 126class SampleRecord { 127public: 128 using CallTargetMap = StringMap<uint64_t>; 129 130 SampleRecord() = default; 131 132 /// Increment the number of samples for this record by \p S. 133 /// Optionally scale sample count \p S by \p Weight. 134 /// 135 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping 136 /// around unsigned integers. 137 sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) { 138 bool Overflowed; 139 NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed); 140 return Overflowed ? sampleprof_error::counter_overflow 141 : sampleprof_error::success; 142 } 143 144 /// Add called function \p F with samples \p S. 145 /// Optionally scale sample count \p S by \p Weight. 146 /// 147 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping 148 /// around unsigned integers. 149 sampleprof_error addCalledTarget(StringRef F, uint64_t S, 150 uint64_t Weight = 1) { 151 uint64_t &TargetSamples = CallTargets[F]; 152 bool Overflowed; 153 TargetSamples = 154 SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed); 155 return Overflowed ? sampleprof_error::counter_overflow 156 : sampleprof_error::success; 157 } 158 159 /// Return true if this sample record contains function calls. 160 bool hasCalls() const { return !CallTargets.empty(); } 161 162 uint64_t getSamples() const { return NumSamples; } 163 const CallTargetMap &getCallTargets() const { return CallTargets; } 164 165 /// Merge the samples in \p Other into this record. 166 /// Optionally scale sample counts by \p Weight. 167 sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) { 168 sampleprof_error Result = addSamples(Other.getSamples(), Weight); 169 for (const auto &I : Other.getCallTargets()) { 170 MergeResult(Result, addCalledTarget(I.first(), I.second, Weight)); 171 } 172 return Result; 173 } 174 175 void print(raw_ostream &OS, unsigned Indent) const; 176 void dump() const; 177 178private: 179 uint64_t NumSamples = 0; 180 CallTargetMap CallTargets; 181}; 182 183raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample); 184 185class FunctionSamples; 186 187using BodySampleMap = std::map<LineLocation, SampleRecord>; 188using FunctionSamplesMap = StringMap<FunctionSamples>; 189using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>; 190 191/// Representation of the samples collected for a function. 192/// 193/// This data structure contains all the collected samples for the body 194/// of a function. Each sample corresponds to a LineLocation instance 195/// within the body of the function. 196class FunctionSamples { 197public: 198 FunctionSamples() = default; 199 200 void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const; 201 void dump() const; 202 203 sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) { 204 bool Overflowed; 205 TotalSamples = 206 SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed); 207 return Overflowed ? sampleprof_error::counter_overflow 208 : sampleprof_error::success; 209 } 210 211 sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) { 212 bool Overflowed; 213 TotalHeadSamples = 214 SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed); 215 return Overflowed ? sampleprof_error::counter_overflow 216 : sampleprof_error::success; 217 } 218 219 sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator, 220 uint64_t Num, uint64_t Weight = 1) { 221 return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples( 222 Num, Weight); 223 } 224 225 sampleprof_error addCalledTargetSamples(uint32_t LineOffset, 226 uint32_t Discriminator, 227 const std::string &FName, 228 uint64_t Num, uint64_t Weight = 1) { 229 return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget( 230 FName, Num, Weight); 231 } 232 233 /// Return the number of samples collected at the given location. 234 /// Each location is specified by \p LineOffset and \p Discriminator. 235 /// If the location is not found in profile, return error. 236 ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset, 237 uint32_t Discriminator) const { 238 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator)); 239 if (ret == BodySamples.end()) 240 return std::error_code(); 241 else 242 return ret->second.getSamples(); 243 } 244 245 /// Returns the call target map collected at a given location. 246 /// Each location is specified by \p LineOffset and \p Discriminator. 247 /// If the location is not found in profile, return error. 248 ErrorOr<SampleRecord::CallTargetMap> 249 findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const { 250 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator)); 251 if (ret == BodySamples.end()) 252 return std::error_code(); 253 return ret->second.getCallTargets(); 254 } 255 256 /// Return the function samples at the given callsite location. 257 FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) { 258 return CallsiteSamples[Loc]; 259 } 260 261 /// Returns the FunctionSamplesMap at the given \p Loc. 262 const FunctionSamplesMap * 263 findFunctionSamplesMapAt(const LineLocation &Loc) const { 264 auto iter = CallsiteSamples.find(Loc); 265 if (iter == CallsiteSamples.end()) 266 return nullptr; 267 return &iter->second; 268 } 269 270 /// Returns a pointer to FunctionSamples at the given callsite location \p Loc 271 /// with callee \p CalleeName. If no callsite can be found, relax the 272 /// restriction to return the FunctionSamples at callsite location \p Loc 273 /// with the maximum total sample count. 274 const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc, 275 StringRef CalleeName) const { 276 auto iter = CallsiteSamples.find(Loc); 277 if (iter == CallsiteSamples.end()) 278 return nullptr; 279 auto FS = iter->second.find(CalleeName); 280 if (FS != iter->second.end()) 281 return &FS->getValue(); 282 // If we cannot find exact match of the callee name, return the FS with 283 // the max total count. 284 uint64_t MaxTotalSamples = 0; 285 const FunctionSamples *R = nullptr; 286 for (const auto &NameFS : iter->second) 287 if (NameFS.second.getTotalSamples() >= MaxTotalSamples) { 288 MaxTotalSamples = NameFS.second.getTotalSamples(); 289 R = &NameFS.second; 290 } 291 return R; 292 } 293 294 bool empty() const { return TotalSamples == 0; } 295 296 /// Return the total number of samples collected inside the function. 297 uint64_t getTotalSamples() const { return TotalSamples; } 298 299 /// Return the total number of branch samples that have the function as the 300 /// branch target. This should be equivalent to the sample of the first 301 /// instruction of the symbol. But as we directly get this info for raw 302 /// profile without referring to potentially inaccurate debug info, this 303 /// gives more accurate profile data and is preferred for standalone symbols. 304 uint64_t getHeadSamples() const { return TotalHeadSamples; } 305 306 /// Return the sample count of the first instruction of the function. 307 /// The function can be either a standalone symbol or an inlined function. 308 uint64_t getEntrySamples() const { 309 // Use either BodySamples or CallsiteSamples which ever has the smaller 310 // lineno. 311 if (!BodySamples.empty() && 312 (CallsiteSamples.empty() || 313 BodySamples.begin()->first < CallsiteSamples.begin()->first)) 314 return BodySamples.begin()->second.getSamples(); 315 if (!CallsiteSamples.empty()) { 316 uint64_t T = 0; 317 // An indirect callsite may be promoted to several inlined direct calls. 318 // We need to get the sum of them. 319 for (const auto &N_FS : CallsiteSamples.begin()->second) 320 T += N_FS.second.getEntrySamples(); 321 return T; 322 } 323 return 0; 324 } 325 326 /// Return all the samples collected in the body of the function. 327 const BodySampleMap &getBodySamples() const { return BodySamples; } 328 329 /// Return all the callsite samples collected in the body of the function. 330 const CallsiteSampleMap &getCallsiteSamples() const { 331 return CallsiteSamples; 332 } 333 334 /// Merge the samples in \p Other into this one. 335 /// Optionally scale samples by \p Weight. 336 sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) { 337 sampleprof_error Result = sampleprof_error::success; 338 Name = Other.getName(); 339 MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight)); 340 MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight)); 341 for (const auto &I : Other.getBodySamples()) { 342 const LineLocation &Loc = I.first; 343 const SampleRecord &Rec = I.second; 344 MergeResult(Result, BodySamples[Loc].merge(Rec, Weight)); 345 } 346 for (const auto &I : Other.getCallsiteSamples()) { 347 const LineLocation &Loc = I.first; 348 FunctionSamplesMap &FSMap = functionSamplesAt(Loc); 349 for (const auto &Rec : I.second) 350 MergeResult(Result, FSMap[Rec.first()].merge(Rec.second, Weight)); 351 } 352 return Result; 353 } 354 355 /// Recursively traverses all children, if the corresponding function is 356 /// not defined in module \p M, and its total sample is no less than 357 /// \p Threshold, add its corresponding GUID to \p S. Also traverse the 358 /// BodySamples to add hot CallTarget's GUID to \p S. 359 void findImportedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M, 360 uint64_t Threshold) const { 361 if (TotalSamples <= Threshold) 362 return; 363 Function *F = M->getFunction(Name); 364 if (!F || !F->getSubprogram()) 365 S.insert(Function::getGUID(Name)); 366 // Import hot CallTargets, which may not be available in IR because full 367 // profile annotation cannot be done until backend compilation in ThinLTO. 368 for (const auto &BS : BodySamples) 369 for (const auto &TS : BS.second.getCallTargets()) 370 if (TS.getValue() > Threshold) { 371 Function *Callee = M->getFunction(TS.getKey()); 372 if (!Callee || !Callee->getSubprogram()) 373 S.insert(Function::getGUID(TS.getKey())); 374 } 375 for (auto CS : CallsiteSamples) 376 for (const auto &NameFS : CS.second) 377 NameFS.second.findImportedFunctions(S, M, Threshold); 378 } 379 380 /// Set the name of the function. 381 void setName(StringRef FunctionName) { Name = FunctionName; } 382 383 /// Return the function name. 384 const StringRef &getName() const { return Name; } 385 386private: 387 /// Mangled name of the function. 388 StringRef Name; 389 390 /// Total number of samples collected inside this function. 391 /// 392 /// Samples are cumulative, they include all the samples collected 393 /// inside this function and all its inlined callees. 394 uint64_t TotalSamples = 0; 395 396 /// Total number of samples collected at the head of the function. 397 /// This is an approximation of the number of calls made to this function 398 /// at runtime. 399 uint64_t TotalHeadSamples = 0; 400 401 /// Map instruction locations to collected samples. 402 /// 403 /// Each entry in this map contains the number of samples 404 /// collected at the corresponding line offset. All line locations 405 /// are an offset from the start of the function. 406 BodySampleMap BodySamples; 407 408 /// Map call sites to collected samples for the called function. 409 /// 410 /// Each entry in this map corresponds to all the samples 411 /// collected for the inlined function call at the given 412 /// location. For example, given: 413 /// 414 /// void foo() { 415 /// 1 bar(); 416 /// ... 417 /// 8 baz(); 418 /// } 419 /// 420 /// If the bar() and baz() calls were inlined inside foo(), this 421 /// map will contain two entries. One for all the samples collected 422 /// in the call to bar() at line offset 1, the other for all the samples 423 /// collected in the call to baz() at line offset 8. 424 CallsiteSampleMap CallsiteSamples; 425}; 426 427raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS); 428 429/// Sort a LocationT->SampleT map by LocationT. 430/// 431/// It produces a sorted list of <LocationT, SampleT> records by ascending 432/// order of LocationT. 433template <class LocationT, class SampleT> class SampleSorter { 434public: 435 using SamplesWithLoc = std::pair<const LocationT, SampleT>; 436 using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>; 437 438 SampleSorter(const std::map<LocationT, SampleT> &Samples) { 439 for (const auto &I : Samples) 440 V.push_back(&I); 441 std::stable_sort(V.begin(), V.end(), 442 [](const SamplesWithLoc *A, const SamplesWithLoc *B) { 443 return A->first < B->first; 444 }); 445 } 446 447 const SamplesWithLocList &get() const { return V; } 448 449private: 450 SamplesWithLocList V; 451}; 452 453} // end namespace sampleprof 454} // end namespace llvm 455 456#endif // LLVM_PROFILEDATA_SAMPLEPROF_H 457