1//=-- SampleProf.h - Sampling profiling format support --------------------===// 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/SmallVector.h" 19#include "llvm/ADT/StringMap.h" 20#include "llvm/Support/Debug.h" 21#include "llvm/Support/ErrorOr.h" 22#include "llvm/Support/raw_ostream.h" 23 24#include <map> 25#include <system_error> 26 27namespace llvm { 28 29const std::error_category &sampleprof_category(); 30 31enum class sampleprof_error { 32 success = 0, 33 bad_magic, 34 unsupported_version, 35 too_large, 36 truncated, 37 malformed, 38 unrecognized_format, 39 unsupported_writing_format, 40 truncated_name_table, 41 not_implemented, 42 counter_overflow 43}; 44 45inline std::error_code make_error_code(sampleprof_error E) { 46 return std::error_code(static_cast<int>(E), sampleprof_category()); 47} 48 49inline sampleprof_error MergeResult(sampleprof_error &Accumulator, 50 sampleprof_error Result) { 51 // Prefer first error encountered as later errors may be secondary effects of 52 // the initial problem. 53 if (Accumulator == sampleprof_error::success && 54 Result != sampleprof_error::success) 55 Accumulator = Result; 56 return Accumulator; 57} 58 59} // end namespace llvm 60 61namespace std { 62template <> 63struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {}; 64} 65 66namespace llvm { 67 68namespace sampleprof { 69 70static inline uint64_t SPMagic() { 71 return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) | 72 uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) | 73 uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) | 74 uint64_t('2') << (64 - 56) | uint64_t(0xff); 75} 76 77static inline uint64_t SPVersion() { return 102; } 78 79/// Represents the relative location of an instruction. 80/// 81/// Instruction locations are specified by the line offset from the 82/// beginning of the function (marked by the line where the function 83/// header is) and the discriminator value within that line. 84/// 85/// The discriminator value is useful to distinguish instructions 86/// that are on the same line but belong to different basic blocks 87/// (e.g., the two post-increment instructions in "if (p) x++; else y++;"). 88struct LineLocation { 89 LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {} 90 void print(raw_ostream &OS) const; 91 void dump() const; 92 bool operator<(const LineLocation &O) const { 93 return LineOffset < O.LineOffset || 94 (LineOffset == O.LineOffset && Discriminator < O.Discriminator); 95 } 96 97 uint32_t LineOffset; 98 uint32_t Discriminator; 99}; 100 101raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc); 102 103/// Represents the relative location of a callsite. 104/// 105/// Callsite locations are specified by the line offset from the 106/// beginning of the function (marked by the line where the function 107/// head is), the discriminator value within that line, and the callee 108/// function name. 109struct CallsiteLocation : public LineLocation { 110 CallsiteLocation(uint32_t L, uint32_t D, StringRef N) 111 : LineLocation(L, D), CalleeName(N) {} 112 void print(raw_ostream &OS) const; 113 void dump() const; 114 115 StringRef CalleeName; 116}; 117 118raw_ostream &operator<<(raw_ostream &OS, const CallsiteLocation &Loc); 119 120/// Representation of a single sample record. 121/// 122/// A sample record is represented by a positive integer value, which 123/// indicates how frequently was the associated line location executed. 124/// 125/// Additionally, if the associated location contains a function call, 126/// the record will hold a list of all the possible called targets. For 127/// direct calls, this will be the exact function being invoked. For 128/// indirect calls (function pointers, virtual table dispatch), this 129/// will be a list of one or more functions. 130class SampleRecord { 131public: 132 typedef StringMap<uint64_t> CallTargetMap; 133 134 SampleRecord() : NumSamples(0), CallTargets() {} 135 136 /// Increment the number of samples for this record by \p S. 137 /// Optionally scale sample count \p S by \p Weight. 138 /// 139 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping 140 /// around unsigned integers. 141 sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) { 142 bool Overflowed; 143 if (Weight > 1) { 144 S = SaturatingMultiply(S, Weight, &Overflowed); 145 if (Overflowed) 146 return sampleprof_error::counter_overflow; 147 } 148 NumSamples = SaturatingAdd(NumSamples, S, &Overflowed); 149 if (Overflowed) 150 return sampleprof_error::counter_overflow; 151 152 return sampleprof_error::success; 153 } 154 155 /// Add called function \p F with samples \p S. 156 /// Optionally scale sample count \p S by \p Weight. 157 /// 158 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping 159 /// around unsigned integers. 160 sampleprof_error addCalledTarget(StringRef F, uint64_t S, 161 uint64_t Weight = 1) { 162 uint64_t &TargetSamples = CallTargets[F]; 163 bool Overflowed; 164 if (Weight > 1) { 165 S = SaturatingMultiply(S, Weight, &Overflowed); 166 if (Overflowed) 167 return sampleprof_error::counter_overflow; 168 } 169 TargetSamples = SaturatingAdd(TargetSamples, S, &Overflowed); 170 if (Overflowed) 171 return sampleprof_error::counter_overflow; 172 173 return sampleprof_error::success; 174 } 175 176 /// Return true if this sample record contains function calls. 177 bool hasCalls() const { return CallTargets.size() > 0; } 178 179 uint64_t getSamples() const { return NumSamples; } 180 const CallTargetMap &getCallTargets() const { return CallTargets; } 181 182 /// Merge the samples in \p Other into this record. 183 /// Optionally scale sample counts by \p Weight. 184 sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) { 185 sampleprof_error Result = addSamples(Other.getSamples(), Weight); 186 for (const auto &I : Other.getCallTargets()) { 187 MergeResult(Result, addCalledTarget(I.first(), I.second, Weight)); 188 } 189 return Result; 190 } 191 192 void print(raw_ostream &OS, unsigned Indent) const; 193 void dump() const; 194 195private: 196 uint64_t NumSamples; 197 CallTargetMap CallTargets; 198}; 199 200raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample); 201 202typedef std::map<LineLocation, SampleRecord> BodySampleMap; 203class FunctionSamples; 204typedef std::map<CallsiteLocation, FunctionSamples> CallsiteSampleMap; 205 206/// Representation of the samples collected for a function. 207/// 208/// This data structure contains all the collected samples for the body 209/// of a function. Each sample corresponds to a LineLocation instance 210/// within the body of the function. 211class FunctionSamples { 212public: 213 FunctionSamples() : TotalSamples(0), TotalHeadSamples(0) {} 214 void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const; 215 void dump() const; 216 sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) { 217 bool Overflowed; 218 if (Weight > 1) { 219 Num = SaturatingMultiply(Num, Weight, &Overflowed); 220 if (Overflowed) 221 return sampleprof_error::counter_overflow; 222 } 223 TotalSamples = SaturatingAdd(TotalSamples, Num, &Overflowed); 224 if (Overflowed) 225 return sampleprof_error::counter_overflow; 226 227 return sampleprof_error::success; 228 } 229 sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) { 230 bool Overflowed; 231 if (Weight > 1) { 232 Num = SaturatingMultiply(Num, Weight, &Overflowed); 233 if (Overflowed) 234 return sampleprof_error::counter_overflow; 235 } 236 TotalHeadSamples = SaturatingAdd(TotalHeadSamples, Num, &Overflowed); 237 if (Overflowed) 238 return sampleprof_error::counter_overflow; 239 240 return sampleprof_error::success; 241 } 242 sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator, 243 uint64_t Num, uint64_t Weight = 1) { 244 return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples( 245 Num, Weight); 246 } 247 sampleprof_error addCalledTargetSamples(uint32_t LineOffset, 248 uint32_t Discriminator, 249 std::string FName, uint64_t Num, 250 uint64_t Weight = 1) { 251 return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget( 252 FName, Num, Weight); 253 } 254 255 /// Return the number of samples collected at the given location. 256 /// Each location is specified by \p LineOffset and \p Discriminator. 257 /// If the location is not found in profile, return error. 258 ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset, 259 uint32_t Discriminator) const { 260 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator)); 261 if (ret == BodySamples.end()) 262 return std::error_code(); 263 else 264 return ret->second.getSamples(); 265 } 266 267 /// Return the function samples at the given callsite location. 268 FunctionSamples &functionSamplesAt(const CallsiteLocation &Loc) { 269 return CallsiteSamples[Loc]; 270 } 271 272 /// Return a pointer to function samples at the given callsite location. 273 const FunctionSamples * 274 findFunctionSamplesAt(const CallsiteLocation &Loc) const { 275 auto iter = CallsiteSamples.find(Loc); 276 if (iter == CallsiteSamples.end()) { 277 return nullptr; 278 } else { 279 return &iter->second; 280 } 281 } 282 283 bool empty() const { return TotalSamples == 0; } 284 285 /// Return the total number of samples collected inside the function. 286 uint64_t getTotalSamples() const { return TotalSamples; } 287 288 /// Return the total number of samples collected at the head of the 289 /// function. 290 uint64_t getHeadSamples() const { return TotalHeadSamples; } 291 292 /// Return all the samples collected in the body of the function. 293 const BodySampleMap &getBodySamples() const { return BodySamples; } 294 295 /// Return all the callsite samples collected in the body of the function. 296 const CallsiteSampleMap &getCallsiteSamples() const { 297 return CallsiteSamples; 298 } 299 300 /// Merge the samples in \p Other into this one. 301 /// Optionally scale samples by \p Weight. 302 sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) { 303 sampleprof_error Result = sampleprof_error::success; 304 MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight)); 305 MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight)); 306 for (const auto &I : Other.getBodySamples()) { 307 const LineLocation &Loc = I.first; 308 const SampleRecord &Rec = I.second; 309 MergeResult(Result, BodySamples[Loc].merge(Rec, Weight)); 310 } 311 for (const auto &I : Other.getCallsiteSamples()) { 312 const CallsiteLocation &Loc = I.first; 313 const FunctionSamples &Rec = I.second; 314 MergeResult(Result, functionSamplesAt(Loc).merge(Rec, Weight)); 315 } 316 return Result; 317 } 318 319private: 320 /// Total number of samples collected inside this function. 321 /// 322 /// Samples are cumulative, they include all the samples collected 323 /// inside this function and all its inlined callees. 324 uint64_t TotalSamples; 325 326 /// Total number of samples collected at the head of the function. 327 /// This is an approximation of the number of calls made to this function 328 /// at runtime. 329 uint64_t TotalHeadSamples; 330 331 /// Map instruction locations to collected samples. 332 /// 333 /// Each entry in this map contains the number of samples 334 /// collected at the corresponding line offset. All line locations 335 /// are an offset from the start of the function. 336 BodySampleMap BodySamples; 337 338 /// Map call sites to collected samples for the called function. 339 /// 340 /// Each entry in this map corresponds to all the samples 341 /// collected for the inlined function call at the given 342 /// location. For example, given: 343 /// 344 /// void foo() { 345 /// 1 bar(); 346 /// ... 347 /// 8 baz(); 348 /// } 349 /// 350 /// If the bar() and baz() calls were inlined inside foo(), this 351 /// map will contain two entries. One for all the samples collected 352 /// in the call to bar() at line offset 1, the other for all the samples 353 /// collected in the call to baz() at line offset 8. 354 CallsiteSampleMap CallsiteSamples; 355}; 356 357raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS); 358 359/// Sort a LocationT->SampleT map by LocationT. 360/// 361/// It produces a sorted list of <LocationT, SampleT> records by ascending 362/// order of LocationT. 363template <class LocationT, class SampleT> class SampleSorter { 364public: 365 typedef std::pair<const LocationT, SampleT> SamplesWithLoc; 366 typedef SmallVector<const SamplesWithLoc *, 20> SamplesWithLocList; 367 368 SampleSorter(const std::map<LocationT, SampleT> &Samples) { 369 for (const auto &I : Samples) 370 V.push_back(&I); 371 std::stable_sort(V.begin(), V.end(), 372 [](const SamplesWithLoc *A, const SamplesWithLoc *B) { 373 return A->first < B->first; 374 }); 375 } 376 const SamplesWithLocList &get() const { return V; } 377 378private: 379 SamplesWithLocList V; 380}; 381 382} // end namespace sampleprof 383 384} // end namespace llvm 385 386#endif // LLVM_PROFILEDATA_SAMPLEPROF_H_ 387