1 //===- SampleProfReader.h - Read LLVM sample profile data -----------------===// 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 definitions needed for reading sample profiles. 11 // 12 // NOTE: If you are making changes to this file format, please remember 13 // to document them in the Clang documentation at 14 // tools/clang/docs/UsersManual.rst. 15 // 16 // Text format 17 // ----------- 18 // 19 // Sample profiles are written as ASCII text. The file is divided into 20 // sections, which correspond to each of the functions executed at runtime. 21 // Each section has the following format 22 // 23 // function1:total_samples:total_head_samples 24 // offset1[.discriminator]: number_of_samples [fn1:num fn2:num ... ] 25 // offset2[.discriminator]: number_of_samples [fn3:num fn4:num ... ] 26 // ... 27 // offsetN[.discriminator]: number_of_samples [fn5:num fn6:num ... ] 28 // offsetA[.discriminator]: fnA:num_of_total_samples 29 // offsetA1[.discriminator]: number_of_samples [fn7:num fn8:num ... ] 30 // ... 31 // 32 // This is a nested tree in which the identation represents the nesting level 33 // of the inline stack. There are no blank lines in the file. And the spacing 34 // within a single line is fixed. Additional spaces will result in an error 35 // while reading the file. 36 // 37 // Any line starting with the '#' character is completely ignored. 38 // 39 // Inlined calls are represented with indentation. The Inline stack is a 40 // stack of source locations in which the top of the stack represents the 41 // leaf function, and the bottom of the stack represents the actual 42 // symbol to which the instruction belongs. 43 // 44 // Function names must be mangled in order for the profile loader to 45 // match them in the current translation unit. The two numbers in the 46 // function header specify how many total samples were accumulated in the 47 // function (first number), and the total number of samples accumulated 48 // in the prologue of the function (second number). This head sample 49 // count provides an indicator of how frequently the function is invoked. 50 // 51 // There are two types of lines in the function body. 52 // 53 // * Sampled line represents the profile information of a source location. 54 // * Callsite line represents the profile information of a callsite. 55 // 56 // Each sampled line may contain several items. Some are optional (marked 57 // below): 58 // 59 // a. Source line offset. This number represents the line number 60 // in the function where the sample was collected. The line number is 61 // always relative to the line where symbol of the function is 62 // defined. So, if the function has its header at line 280, the offset 63 // 13 is at line 293 in the file. 64 // 65 // Note that this offset should never be a negative number. This could 66 // happen in cases like macros. The debug machinery will register the 67 // line number at the point of macro expansion. So, if the macro was 68 // expanded in a line before the start of the function, the profile 69 // converter should emit a 0 as the offset (this means that the optimizers 70 // will not be able to associate a meaningful weight to the instructions 71 // in the macro). 72 // 73 // b. [OPTIONAL] Discriminator. This is used if the sampled program 74 // was compiled with DWARF discriminator support 75 // (http://wiki.dwarfstd.org/index.php?title=Path_Discriminators). 76 // DWARF discriminators are unsigned integer values that allow the 77 // compiler to distinguish between multiple execution paths on the 78 // same source line location. 79 // 80 // For example, consider the line of code ``if (cond) foo(); else bar();``. 81 // If the predicate ``cond`` is true 80% of the time, then the edge 82 // into function ``foo`` should be considered to be taken most of the 83 // time. But both calls to ``foo`` and ``bar`` are at the same source 84 // line, so a sample count at that line is not sufficient. The 85 // compiler needs to know which part of that line is taken more 86 // frequently. 87 // 88 // This is what discriminators provide. In this case, the calls to 89 // ``foo`` and ``bar`` will be at the same line, but will have 90 // different discriminator values. This allows the compiler to correctly 91 // set edge weights into ``foo`` and ``bar``. 92 // 93 // c. Number of samples. This is an integer quantity representing the 94 // number of samples collected by the profiler at this source 95 // location. 96 // 97 // d. [OPTIONAL] Potential call targets and samples. If present, this 98 // line contains a call instruction. This models both direct and 99 // number of samples. For example, 100 // 101 // 130: 7 foo:3 bar:2 baz:7 102 // 103 // The above means that at relative line offset 130 there is a call 104 // instruction that calls one of ``foo()``, ``bar()`` and ``baz()``, 105 // with ``baz()`` being the relatively more frequently called target. 106 // 107 // Each callsite line may contain several items. Some are optional. 108 // 109 // a. Source line offset. This number represents the line number of the 110 // callsite that is inlined in the profiled binary. 111 // 112 // b. [OPTIONAL] Discriminator. Same as the discriminator for sampled line. 113 // 114 // c. Number of samples. This is an integer quantity representing the 115 // total number of samples collected for the inlined instance at this 116 // callsite 117 // 118 // 119 // Binary format 120 // ------------- 121 // 122 // This is a more compact encoding. Numbers are encoded as ULEB128 values 123 // and all strings are encoded in a name table. The file is organized in 124 // the following sections: 125 // 126 // MAGIC (uint64_t) 127 // File identifier computed by function SPMagic() (0x5350524f463432ff) 128 // 129 // VERSION (uint32_t) 130 // File format version number computed by SPVersion() 131 // 132 // NAME TABLE 133 // SIZE (uint32_t) 134 // Number of entries in the name table. 135 // NAMES 136 // A NUL-separated list of SIZE strings. 137 // 138 // FUNCTION BODY (one for each uninlined function body present in the profile) 139 // HEAD_SAMPLES (uint64_t) [only for top-level functions] 140 // Total number of samples collected at the head (prologue) of the 141 // function. 142 // NOTE: This field should only be present for top-level functions 143 // (i.e., not inlined into any caller). Inlined function calls 144 // have no prologue, so they don't need this. 145 // NAME_IDX (uint32_t) 146 // Index into the name table indicating the function name. 147 // SAMPLES (uint64_t) 148 // Total number of samples collected in this function. 149 // NRECS (uint32_t) 150 // Total number of sampling records this function's profile. 151 // BODY RECORDS 152 // A list of NRECS entries. Each entry contains: 153 // OFFSET (uint32_t) 154 // Line offset from the start of the function. 155 // DISCRIMINATOR (uint32_t) 156 // Discriminator value (see description of discriminators 157 // in the text format documentation above). 158 // SAMPLES (uint64_t) 159 // Number of samples collected at this location. 160 // NUM_CALLS (uint32_t) 161 // Number of non-inlined function calls made at this location. In the 162 // case of direct calls, this number will always be 1. For indirect 163 // calls (virtual functions and function pointers) this will 164 // represent all the actual functions called at runtime. 165 // CALL_TARGETS 166 // A list of NUM_CALLS entries for each called function: 167 // NAME_IDX (uint32_t) 168 // Index into the name table with the callee name. 169 // SAMPLES (uint64_t) 170 // Number of samples collected at the call site. 171 // NUM_INLINED_FUNCTIONS (uint32_t) 172 // Number of callees inlined into this function. 173 // INLINED FUNCTION RECORDS 174 // A list of NUM_INLINED_FUNCTIONS entries describing each of the inlined 175 // callees. 176 // OFFSET (uint32_t) 177 // Line offset from the start of the function. 178 // DISCRIMINATOR (uint32_t) 179 // Discriminator value (see description of discriminators 180 // in the text format documentation above). 181 // FUNCTION BODY 182 // A FUNCTION BODY entry describing the inlined function. 183 //===----------------------------------------------------------------------===// 184 #ifndef LLVM_PROFILEDATA_SAMPLEPROFREADER_H 185 #define LLVM_PROFILEDATA_SAMPLEPROFREADER_H 186 187 #include "llvm/ADT/StringMap.h" 188 #include "llvm/ADT/StringRef.h" 189 #include "llvm/ADT/Twine.h" 190 #include "llvm/IR/DiagnosticInfo.h" 191 #include "llvm/IR/Function.h" 192 #include "llvm/IR/LLVMContext.h" 193 #include "llvm/ProfileData/SampleProf.h" 194 #include "llvm/Support/Debug.h" 195 #include "llvm/Support/ErrorHandling.h" 196 #include "llvm/Support/ErrorOr.h" 197 #include "llvm/Support/GCOV.h" 198 #include "llvm/Support/MemoryBuffer.h" 199 #include "llvm/Support/raw_ostream.h" 200 201 namespace llvm { 202 203 namespace sampleprof { 204 205 /// \brief Sample-based profile reader. 206 /// 207 /// Each profile contains sample counts for all the functions 208 /// executed. Inside each function, statements are annotated with the 209 /// collected samples on all the instructions associated with that 210 /// statement. 211 /// 212 /// For this to produce meaningful data, the program needs to be 213 /// compiled with some debug information (at minimum, line numbers: 214 /// -gline-tables-only). Otherwise, it will be impossible to match IR 215 /// instructions to the line numbers collected by the profiler. 216 /// 217 /// From the profile file, we are interested in collecting the 218 /// following information: 219 /// 220 /// * A list of functions included in the profile (mangled names). 221 /// 222 /// * For each function F: 223 /// 1. The total number of samples collected in F. 224 /// 225 /// 2. The samples collected at each line in F. To provide some 226 /// protection against source code shuffling, line numbers should 227 /// be relative to the start of the function. 228 /// 229 /// The reader supports two file formats: text and binary. The text format 230 /// is useful for debugging and testing, while the binary format is more 231 /// compact and I/O efficient. They can both be used interchangeably. 232 class SampleProfileReader { 233 public: 234 SampleProfileReader(std::unique_ptr<MemoryBuffer> B, LLVMContext &C) 235 : Profiles(0), Ctx(C), Buffer(std::move(B)) {} 236 237 virtual ~SampleProfileReader() {} 238 239 /// \brief Read and validate the file header. 240 virtual std::error_code readHeader() = 0; 241 242 /// \brief Read sample profiles from the associated file. 243 virtual std::error_code read() = 0; 244 245 /// \brief Print the profile for \p FName on stream \p OS. 246 void dumpFunctionProfile(StringRef FName, raw_ostream &OS = dbgs()); 247 248 /// \brief Print all the profiles on stream \p OS. 249 void dump(raw_ostream &OS = dbgs()); 250 251 /// \brief Return the samples collected for function \p F. 252 FunctionSamples *getSamplesFor(const Function &F) { 253 return &Profiles[F.getName()]; 254 } 255 256 /// \brief Return all the profiles. 257 StringMap<FunctionSamples> &getProfiles() { return Profiles; } 258 259 /// \brief Report a parse error message. 260 void reportError(int64_t LineNumber, Twine Msg) const { 261 Ctx.diagnose(DiagnosticInfoSampleProfile(Buffer->getBufferIdentifier(), 262 LineNumber, Msg)); 263 } 264 265 /// \brief Create a sample profile reader appropriate to the file format. 266 static ErrorOr<std::unique_ptr<SampleProfileReader>> 267 create(StringRef Filename, LLVMContext &C); 268 269 /// \brief Create a sample profile reader from the supplied memory buffer. 270 static ErrorOr<std::unique_ptr<SampleProfileReader>> 271 create(std::unique_ptr<MemoryBuffer> &B, LLVMContext &C); 272 273 protected: 274 /// \brief Map every function to its associated profile. 275 /// 276 /// The profile of every function executed at runtime is collected 277 /// in the structure FunctionSamples. This maps function objects 278 /// to their corresponding profiles. 279 StringMap<FunctionSamples> Profiles; 280 281 /// \brief LLVM context used to emit diagnostics. 282 LLVMContext &Ctx; 283 284 /// \brief Memory buffer holding the profile file. 285 std::unique_ptr<MemoryBuffer> Buffer; 286 }; 287 288 class SampleProfileReaderText : public SampleProfileReader { 289 public: 290 SampleProfileReaderText(std::unique_ptr<MemoryBuffer> B, LLVMContext &C) 291 : SampleProfileReader(std::move(B), C) {} 292 293 /// \brief Read and validate the file header. 294 std::error_code readHeader() override { return sampleprof_error::success; } 295 296 /// \brief Read sample profiles from the associated file. 297 std::error_code read() override; 298 299 /// \brief Return true if \p Buffer is in the format supported by this class. 300 static bool hasFormat(const MemoryBuffer &Buffer); 301 }; 302 303 class SampleProfileReaderBinary : public SampleProfileReader { 304 public: 305 SampleProfileReaderBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C) 306 : SampleProfileReader(std::move(B), C), Data(nullptr), End(nullptr) {} 307 308 /// \brief Read and validate the file header. 309 std::error_code readHeader() override; 310 311 /// \brief Read sample profiles from the associated file. 312 std::error_code read() override; 313 314 /// \brief Return true if \p Buffer is in the format supported by this class. 315 static bool hasFormat(const MemoryBuffer &Buffer); 316 317 protected: 318 /// \brief Read a numeric value of type T from the profile. 319 /// 320 /// If an error occurs during decoding, a diagnostic message is emitted and 321 /// EC is set. 322 /// 323 /// \returns the read value. 324 template <typename T> ErrorOr<T> readNumber(); 325 326 /// \brief Read a string from the profile. 327 /// 328 /// If an error occurs during decoding, a diagnostic message is emitted and 329 /// EC is set. 330 /// 331 /// \returns the read value. 332 ErrorOr<StringRef> readString(); 333 334 /// Read a string indirectly via the name table. 335 ErrorOr<StringRef> readStringFromTable(); 336 337 /// \brief Return true if we've reached the end of file. 338 bool at_eof() const { return Data >= End; } 339 340 /// Read the contents of the given profile instance. 341 std::error_code readProfile(FunctionSamples &FProfile); 342 343 /// \brief Points to the current location in the buffer. 344 const uint8_t *Data; 345 346 /// \brief Points to the end of the buffer. 347 const uint8_t *End; 348 349 /// Function name table. 350 std::vector<StringRef> NameTable; 351 }; 352 353 typedef SmallVector<FunctionSamples *, 10> InlineCallStack; 354 355 // Supported histogram types in GCC. Currently, we only need support for 356 // call target histograms. 357 enum HistType { 358 HIST_TYPE_INTERVAL, 359 HIST_TYPE_POW2, 360 HIST_TYPE_SINGLE_VALUE, 361 HIST_TYPE_CONST_DELTA, 362 HIST_TYPE_INDIR_CALL, 363 HIST_TYPE_AVERAGE, 364 HIST_TYPE_IOR, 365 HIST_TYPE_INDIR_CALL_TOPN 366 }; 367 368 class SampleProfileReaderGCC : public SampleProfileReader { 369 public: 370 SampleProfileReaderGCC(std::unique_ptr<MemoryBuffer> B, LLVMContext &C) 371 : SampleProfileReader(std::move(B), C), GcovBuffer(Buffer.get()) {} 372 373 /// \brief Read and validate the file header. 374 std::error_code readHeader() override; 375 376 /// \brief Read sample profiles from the associated file. 377 std::error_code read() override; 378 379 /// \brief Return true if \p Buffer is in the format supported by this class. 380 static bool hasFormat(const MemoryBuffer &Buffer); 381 382 protected: 383 std::error_code readNameTable(); 384 std::error_code readOneFunctionProfile(const InlineCallStack &InlineStack, 385 bool Update, uint32_t Offset); 386 std::error_code readFunctionProfiles(); 387 std::error_code skipNextWord(); 388 template <typename T> ErrorOr<T> readNumber(); 389 ErrorOr<StringRef> readString(); 390 391 /// \brief Read the section tag and check that it's the same as \p Expected. 392 std::error_code readSectionTag(uint32_t Expected); 393 394 /// GCOV buffer containing the profile. 395 GCOVBuffer GcovBuffer; 396 397 /// Function names in this profile. 398 std::vector<std::string> Names; 399 400 /// GCOV tags used to separate sections in the profile file. 401 static const uint32_t GCOVTagAFDOFileNames = 0xaa000000; 402 static const uint32_t GCOVTagAFDOFunction = 0xac000000; 403 }; 404 405 } // End namespace sampleprof 406 407 } // End namespace llvm 408 409 #endif // LLVM_PROFILEDATA_SAMPLEPROFREADER_H 410
