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 27 namespace llvm { 28 29 const std::error_category &sampleprof_category(); 30 31 enum 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 45 inline std::error_code make_error_code(sampleprof_error E) { 46 return std::error_code(static_cast<int>(E), sampleprof_category()); 47 } 48 49 inline 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 61 namespace std { 62 template <> 63 struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {}; 64 } 65 66 namespace llvm { 67 68 namespace sampleprof { 69 70 static 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 77 static inline uint64_t SPVersion() { return 103; } 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++;"). 88 struct 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 101 raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc); 102 103 /// Representation of a single sample record. 104 /// 105 /// A sample record is represented by a positive integer value, which 106 /// indicates how frequently was the associated line location executed. 107 /// 108 /// Additionally, if the associated location contains a function call, 109 /// the record will hold a list of all the possible called targets. For 110 /// direct calls, this will be the exact function being invoked. For 111 /// indirect calls (function pointers, virtual table dispatch), this 112 /// will be a list of one or more functions. 113 class SampleRecord { 114 public: 115 typedef StringMap<uint64_t> CallTargetMap; 116 117 SampleRecord() : NumSamples(0), CallTargets() {} 118 119 /// Increment the number of samples for this record by \p S. 120 /// Optionally scale sample count \p S by \p Weight. 121 /// 122 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping 123 /// around unsigned integers. 124 sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) { 125 bool Overflowed; 126 NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed); 127 return Overflowed ? sampleprof_error::counter_overflow 128 : sampleprof_error::success; 129 } 130 131 /// Add called function \p F with samples \p S. 132 /// Optionally scale sample count \p S by \p Weight. 133 /// 134 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping 135 /// around unsigned integers. 136 sampleprof_error addCalledTarget(StringRef F, uint64_t S, 137 uint64_t Weight = 1) { 138 uint64_t &TargetSamples = CallTargets[F]; 139 bool Overflowed; 140 TargetSamples = 141 SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed); 142 return Overflowed ? sampleprof_error::counter_overflow 143 : sampleprof_error::success; 144 } 145 146 /// Return true if this sample record contains function calls. 147 bool hasCalls() const { return CallTargets.size() > 0; } 148 149 uint64_t getSamples() const { return NumSamples; } 150 const CallTargetMap &getCallTargets() const { return CallTargets; } 151 152 /// Merge the samples in \p Other into this record. 153 /// Optionally scale sample counts by \p Weight. 154 sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) { 155 sampleprof_error Result = addSamples(Other.getSamples(), Weight); 156 for (const auto &I : Other.getCallTargets()) { 157 MergeResult(Result, addCalledTarget(I.first(), I.second, Weight)); 158 } 159 return Result; 160 } 161 162 void print(raw_ostream &OS, unsigned Indent) const; 163 void dump() const; 164 165 private: 166 uint64_t NumSamples; 167 CallTargetMap CallTargets; 168 }; 169 170 raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample); 171 172 typedef std::map<LineLocation, SampleRecord> BodySampleMap; 173 class FunctionSamples; 174 typedef std::map<LineLocation, FunctionSamples> CallsiteSampleMap; 175 176 /// Representation of the samples collected for a function. 177 /// 178 /// This data structure contains all the collected samples for the body 179 /// of a function. Each sample corresponds to a LineLocation instance 180 /// within the body of the function. 181 class FunctionSamples { 182 public: 183 FunctionSamples() : Name(), TotalSamples(0), TotalHeadSamples(0) {} 184 void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const; 185 void dump() const; 186 sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) { 187 bool Overflowed; 188 TotalSamples = 189 SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed); 190 return Overflowed ? sampleprof_error::counter_overflow 191 : sampleprof_error::success; 192 } 193 sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) { 194 bool Overflowed; 195 TotalHeadSamples = 196 SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed); 197 return Overflowed ? sampleprof_error::counter_overflow 198 : sampleprof_error::success; 199 } 200 sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator, 201 uint64_t Num, uint64_t Weight = 1) { 202 return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples( 203 Num, Weight); 204 } 205 sampleprof_error addCalledTargetSamples(uint32_t LineOffset, 206 uint32_t Discriminator, 207 const std::string &FName, 208 uint64_t Num, uint64_t Weight = 1) { 209 return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget( 210 FName, Num, Weight); 211 } 212 213 /// Return the number of samples collected at the given location. 214 /// Each location is specified by \p LineOffset and \p Discriminator. 215 /// If the location is not found in profile, return error. 216 ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset, 217 uint32_t Discriminator) const { 218 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator)); 219 if (ret == BodySamples.end()) 220 return std::error_code(); 221 else 222 return ret->second.getSamples(); 223 } 224 225 /// Return the function samples at the given callsite location. 226 FunctionSamples &functionSamplesAt(const LineLocation &Loc) { 227 return CallsiteSamples[Loc]; 228 } 229 230 /// Return a pointer to function samples at the given callsite location. 231 const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc) const { 232 auto iter = CallsiteSamples.find(Loc); 233 if (iter == CallsiteSamples.end()) { 234 return nullptr; 235 } else { 236 return &iter->second; 237 } 238 } 239 240 bool empty() const { return TotalSamples == 0; } 241 242 /// Return the total number of samples collected inside the function. 243 uint64_t getTotalSamples() const { return TotalSamples; } 244 245 /// Return the total number of samples collected at the head of the 246 /// function. 247 uint64_t getHeadSamples() const { return TotalHeadSamples; } 248 249 /// Return all the samples collected in the body of the function. 250 const BodySampleMap &getBodySamples() const { return BodySamples; } 251 252 /// Return all the callsite samples collected in the body of the function. 253 const CallsiteSampleMap &getCallsiteSamples() const { 254 return CallsiteSamples; 255 } 256 257 /// Merge the samples in \p Other into this one. 258 /// Optionally scale samples by \p Weight. 259 sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) { 260 sampleprof_error Result = sampleprof_error::success; 261 Name = Other.getName(); 262 MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight)); 263 MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight)); 264 for (const auto &I : Other.getBodySamples()) { 265 const LineLocation &Loc = I.first; 266 const SampleRecord &Rec = I.second; 267 MergeResult(Result, BodySamples[Loc].merge(Rec, Weight)); 268 } 269 for (const auto &I : Other.getCallsiteSamples()) { 270 const LineLocation &Loc = I.first; 271 const FunctionSamples &Rec = I.second; 272 MergeResult(Result, functionSamplesAt(Loc).merge(Rec, Weight)); 273 } 274 return Result; 275 } 276 277 /// Set the name of the function. 278 void setName(StringRef FunctionName) { Name = FunctionName; } 279 280 /// Return the function name. 281 const StringRef &getName() const { return Name; } 282 283 private: 284 /// Mangled name of the function. 285 StringRef Name; 286 287 /// Total number of samples collected inside this function. 288 /// 289 /// Samples are cumulative, they include all the samples collected 290 /// inside this function and all its inlined callees. 291 uint64_t TotalSamples; 292 293 /// Total number of samples collected at the head of the function. 294 /// This is an approximation of the number of calls made to this function 295 /// at runtime. 296 uint64_t TotalHeadSamples; 297 298 /// Map instruction locations to collected samples. 299 /// 300 /// Each entry in this map contains the number of samples 301 /// collected at the corresponding line offset. All line locations 302 /// are an offset from the start of the function. 303 BodySampleMap BodySamples; 304 305 /// Map call sites to collected samples for the called function. 306 /// 307 /// Each entry in this map corresponds to all the samples 308 /// collected for the inlined function call at the given 309 /// location. For example, given: 310 /// 311 /// void foo() { 312 /// 1 bar(); 313 /// ... 314 /// 8 baz(); 315 /// } 316 /// 317 /// If the bar() and baz() calls were inlined inside foo(), this 318 /// map will contain two entries. One for all the samples collected 319 /// in the call to bar() at line offset 1, the other for all the samples 320 /// collected in the call to baz() at line offset 8. 321 CallsiteSampleMap CallsiteSamples; 322 }; 323 324 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS); 325 326 /// Sort a LocationT->SampleT map by LocationT. 327 /// 328 /// It produces a sorted list of <LocationT, SampleT> records by ascending 329 /// order of LocationT. 330 template <class LocationT, class SampleT> class SampleSorter { 331 public: 332 typedef std::pair<const LocationT, SampleT> SamplesWithLoc; 333 typedef SmallVector<const SamplesWithLoc *, 20> SamplesWithLocList; 334 335 SampleSorter(const std::map<LocationT, SampleT> &Samples) { 336 for (const auto &I : Samples) 337 V.push_back(&I); 338 std::stable_sort(V.begin(), V.end(), 339 [](const SamplesWithLoc *A, const SamplesWithLoc *B) { 340 return A->first < B->first; 341 }); 342 } 343 const SamplesWithLocList &get() const { return V; } 344 345 private: 346 SamplesWithLocList V; 347 }; 348 349 } // end namespace sampleprof 350 351 } // end namespace llvm 352 353 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H_ 354
