1 #ifndef LLVM_PROFILEDATA_MEMPROF_H_ 2 #define LLVM_PROFILEDATA_MEMPROF_H_ 3 4 #include "llvm/ADT/DenseMap.h" 5 #include "llvm/ADT/STLFunctionalExtras.h" 6 #include "llvm/ADT/SmallVector.h" 7 #include "llvm/IR/GlobalValue.h" 8 #include "llvm/ProfileData/MemProfData.inc" 9 #include "llvm/Support/Endian.h" 10 #include "llvm/Support/EndianStream.h" 11 #include "llvm/Support/raw_ostream.h" 12 13 #include <cstdint> 14 #include <optional> 15 16 namespace llvm { 17 namespace memprof { 18 19 enum class Meta : uint64_t { 20 Start = 0, 21 #define MIBEntryDef(NameTag, Name, Type) NameTag, 22 #include "llvm/ProfileData/MIBEntryDef.inc" 23 #undef MIBEntryDef 24 Size 25 }; 26 27 using MemProfSchema = llvm::SmallVector<Meta, static_cast<int>(Meta::Size)>; 28 29 // Holds the actual MemInfoBlock data with all fields. Contents may be read or 30 // written partially by providing an appropriate schema to the serialize and 31 // deserialize methods. 32 struct PortableMemInfoBlock { 33 PortableMemInfoBlock() = default; 34 explicit PortableMemInfoBlock(const MemInfoBlock &Block) { 35 #define MIBEntryDef(NameTag, Name, Type) Name = Block.Name; 36 #include "llvm/ProfileData/MIBEntryDef.inc" 37 #undef MIBEntryDef 38 } 39 40 PortableMemInfoBlock(const MemProfSchema &Schema, const unsigned char *Ptr) { 41 deserialize(Schema, Ptr); 42 } 43 44 // Read the contents of \p Ptr based on the \p Schema to populate the 45 // MemInfoBlock member. 46 void deserialize(const MemProfSchema &Schema, const unsigned char *Ptr) { 47 using namespace support; 48 49 for (const Meta Id : Schema) { 50 switch (Id) { 51 #define MIBEntryDef(NameTag, Name, Type) \ 52 case Meta::Name: { \ 53 Name = endian::readNext<Type, little, unaligned>(Ptr); \ 54 } break; 55 #include "llvm/ProfileData/MIBEntryDef.inc" 56 #undef MIBEntryDef 57 default: 58 llvm_unreachable("Unknown meta type id, is the profile collected from " 59 "a newer version of the runtime?"); 60 } 61 } 62 } 63 64 // Write the contents of the MemInfoBlock based on the \p Schema provided to 65 // the raw_ostream \p OS. 66 void serialize(const MemProfSchema &Schema, raw_ostream &OS) const { 67 using namespace support; 68 69 endian::Writer LE(OS, little); 70 for (const Meta Id : Schema) { 71 switch (Id) { 72 #define MIBEntryDef(NameTag, Name, Type) \ 73 case Meta::Name: { \ 74 LE.write<Type>(Name); \ 75 } break; 76 #include "llvm/ProfileData/MIBEntryDef.inc" 77 #undef MIBEntryDef 78 default: 79 llvm_unreachable("Unknown meta type id, invalid input?"); 80 } 81 } 82 } 83 84 // Print out the contents of the MemInfoBlock in YAML format. 85 void printYAML(raw_ostream &OS) const { 86 OS << " MemInfoBlock:\n"; 87 #define MIBEntryDef(NameTag, Name, Type) \ 88 OS << " " << #Name << ": " << Name << "\n"; 89 #include "llvm/ProfileData/MIBEntryDef.inc" 90 #undef MIBEntryDef 91 } 92 93 // Define getters for each type which can be called by analyses. 94 #define MIBEntryDef(NameTag, Name, Type) \ 95 Type get##Name() const { return Name; } 96 #include "llvm/ProfileData/MIBEntryDef.inc" 97 #undef MIBEntryDef 98 99 void clear() { *this = PortableMemInfoBlock(); } 100 101 // Returns the full schema currently in use. 102 static MemProfSchema getSchema() { 103 MemProfSchema List; 104 #define MIBEntryDef(NameTag, Name, Type) List.push_back(Meta::Name); 105 #include "llvm/ProfileData/MIBEntryDef.inc" 106 #undef MIBEntryDef 107 return List; 108 } 109 110 bool operator==(const PortableMemInfoBlock &Other) const { 111 #define MIBEntryDef(NameTag, Name, Type) \ 112 if (Other.get##Name() != get##Name()) \ 113 return false; 114 #include "llvm/ProfileData/MIBEntryDef.inc" 115 #undef MIBEntryDef 116 return true; 117 } 118 119 bool operator!=(const PortableMemInfoBlock &Other) const { 120 return !operator==(Other); 121 } 122 123 static constexpr size_t serializedSize() { 124 size_t Result = 0; 125 #define MIBEntryDef(NameTag, Name, Type) Result += sizeof(Type); 126 #include "llvm/ProfileData/MIBEntryDef.inc" 127 #undef MIBEntryDef 128 return Result; 129 } 130 131 private: 132 #define MIBEntryDef(NameTag, Name, Type) Type Name = Type(); 133 #include "llvm/ProfileData/MIBEntryDef.inc" 134 #undef MIBEntryDef 135 }; 136 137 // A type representing the id generated by hashing the contents of the Frame. 138 using FrameId = uint64_t; 139 // Describes a call frame for a dynamic allocation context. The contents of 140 // the frame are populated by symbolizing the stack depot call frame from the 141 // compiler runtime. 142 struct Frame { 143 // A uuid (uint64_t) identifying the function. It is obtained by 144 // llvm::md5(FunctionName) which returns the lower 64 bits. 145 GlobalValue::GUID Function; 146 // The symbol name for the function. Only populated in the Frame by the reader 147 // if requested during initialization. This field should not be serialized. 148 std::optional<std::string> SymbolName; 149 // The source line offset of the call from the beginning of parent function. 150 uint32_t LineOffset; 151 // The source column number of the call to help distinguish multiple calls 152 // on the same line. 153 uint32_t Column; 154 // Whether the current frame is inlined. 155 bool IsInlineFrame; 156 157 Frame(const Frame &Other) { 158 Function = Other.Function; 159 SymbolName = Other.SymbolName; 160 LineOffset = Other.LineOffset; 161 Column = Other.Column; 162 IsInlineFrame = Other.IsInlineFrame; 163 } 164 165 Frame(uint64_t Hash, uint32_t Off, uint32_t Col, bool Inline) 166 : Function(Hash), LineOffset(Off), Column(Col), IsInlineFrame(Inline) {} 167 168 bool operator==(const Frame &Other) const { 169 // Ignore the SymbolName field to avoid a string compare. Comparing the 170 // function hash serves the same purpose. 171 return Other.Function == Function && Other.LineOffset == LineOffset && 172 Other.Column == Column && Other.IsInlineFrame == IsInlineFrame; 173 } 174 175 Frame &operator=(const Frame &Other) { 176 Function = Other.Function; 177 SymbolName = Other.SymbolName; 178 LineOffset = Other.LineOffset; 179 Column = Other.Column; 180 IsInlineFrame = Other.IsInlineFrame; 181 return *this; 182 } 183 184 bool operator!=(const Frame &Other) const { return !operator==(Other); } 185 186 // Write the contents of the frame to the ostream \p OS. 187 void serialize(raw_ostream &OS) const { 188 using namespace support; 189 190 endian::Writer LE(OS, little); 191 192 // If the type of the GlobalValue::GUID changes, then we need to update 193 // the reader and the writer. 194 static_assert(std::is_same<GlobalValue::GUID, uint64_t>::value, 195 "Expect GUID to be uint64_t."); 196 LE.write<uint64_t>(Function); 197 198 LE.write<uint32_t>(LineOffset); 199 LE.write<uint32_t>(Column); 200 LE.write<bool>(IsInlineFrame); 201 } 202 203 // Read a frame from char data which has been serialized as little endian. 204 static Frame deserialize(const unsigned char *Ptr) { 205 using namespace support; 206 207 const uint64_t F = endian::readNext<uint64_t, little, unaligned>(Ptr); 208 const uint32_t L = endian::readNext<uint32_t, little, unaligned>(Ptr); 209 const uint32_t C = endian::readNext<uint32_t, little, unaligned>(Ptr); 210 const bool I = endian::readNext<bool, little, unaligned>(Ptr); 211 return Frame(/*Function=*/F, /*LineOffset=*/L, /*Column=*/C, 212 /*IsInlineFrame=*/I); 213 } 214 215 // Returns the size of the frame information. 216 static constexpr size_t serializedSize() { 217 return sizeof(Frame::Function) + sizeof(Frame::LineOffset) + 218 sizeof(Frame::Column) + sizeof(Frame::IsInlineFrame); 219 } 220 221 // Print the frame information in YAML format. 222 void printYAML(raw_ostream &OS) const { 223 OS << " -\n" 224 << " Function: " << Function << "\n" 225 << " SymbolName: " << SymbolName.value_or("<None>") << "\n" 226 << " LineOffset: " << LineOffset << "\n" 227 << " Column: " << Column << "\n" 228 << " Inline: " << IsInlineFrame << "\n"; 229 } 230 231 // Return a hash value based on the contents of the frame. Here we don't use 232 // hashing from llvm ADT since we are going to persist the hash id, the hash 233 // combine algorithm in ADT uses a new randomized seed each time. 234 inline FrameId hash() const { 235 auto HashCombine = [](auto Value, size_t Seed) { 236 std::hash<decltype(Value)> Hasher; 237 // The constant used below is the 64 bit representation of the fractional 238 // part of the golden ratio. Used here for the randomness in their bit 239 // pattern. 240 return Hasher(Value) + 0x9e3779b97f4a7c15 + (Seed << 6) + (Seed >> 2); 241 }; 242 243 size_t Result = 0; 244 Result ^= HashCombine(Function, Result); 245 Result ^= HashCombine(LineOffset, Result); 246 Result ^= HashCombine(Column, Result); 247 Result ^= HashCombine(IsInlineFrame, Result); 248 return static_cast<FrameId>(Result); 249 } 250 }; 251 252 // Holds allocation information in a space efficient format where frames are 253 // represented using unique identifiers. 254 struct IndexedAllocationInfo { 255 // The dynamic calling context for the allocation in bottom-up (leaf-to-root) 256 // order. Frame contents are stored out-of-line. 257 llvm::SmallVector<FrameId> CallStack; 258 // The statistics obtained from the runtime for the allocation. 259 PortableMemInfoBlock Info; 260 261 IndexedAllocationInfo() = default; 262 IndexedAllocationInfo(ArrayRef<FrameId> CS, const MemInfoBlock &MB) 263 : CallStack(CS.begin(), CS.end()), Info(MB) {} 264 265 // Returns the size in bytes when this allocation info struct is serialized. 266 size_t serializedSize() const { 267 return sizeof(uint64_t) + // The number of frames to serialize. 268 sizeof(FrameId) * CallStack.size() + // The callstack frame ids. 269 PortableMemInfoBlock::serializedSize(); // The size of the payload. 270 } 271 272 bool operator==(const IndexedAllocationInfo &Other) const { 273 if (Other.Info != Info) 274 return false; 275 276 if (Other.CallStack.size() != CallStack.size()) 277 return false; 278 279 for (size_t J = 0; J < Other.CallStack.size(); J++) { 280 if (Other.CallStack[J] != CallStack[J]) 281 return false; 282 } 283 return true; 284 } 285 286 bool operator!=(const IndexedAllocationInfo &Other) const { 287 return !operator==(Other); 288 } 289 }; 290 291 // Holds allocation information with frame contents inline. The type should 292 // be used for temporary in-memory instances. 293 struct AllocationInfo { 294 // Same as IndexedAllocationInfo::CallStack with the frame contents inline. 295 llvm::SmallVector<Frame> CallStack; 296 // Same as IndexedAllocationInfo::Info; 297 PortableMemInfoBlock Info; 298 299 AllocationInfo() = default; 300 AllocationInfo( 301 const IndexedAllocationInfo &IndexedAI, 302 llvm::function_ref<const Frame(const FrameId)> IdToFrameCallback) { 303 for (const FrameId &Id : IndexedAI.CallStack) { 304 CallStack.push_back(IdToFrameCallback(Id)); 305 } 306 Info = IndexedAI.Info; 307 } 308 309 void printYAML(raw_ostream &OS) const { 310 OS << " -\n"; 311 OS << " Callstack:\n"; 312 // TODO: Print out the frame on one line with to make it easier for deep 313 // callstacks once we have a test to check valid YAML is generated. 314 for (const Frame &F : CallStack) { 315 F.printYAML(OS); 316 } 317 Info.printYAML(OS); 318 } 319 }; 320 321 // Holds the memprof profile information for a function. The internal 322 // representation stores frame ids for efficiency. This representation should 323 // be used in the profile conversion and manipulation tools. 324 struct IndexedMemProfRecord { 325 // Memory allocation sites in this function for which we have memory 326 // profiling data. 327 llvm::SmallVector<IndexedAllocationInfo> AllocSites; 328 // Holds call sites in this function which are part of some memory 329 // allocation context. We store this as a list of locations, each with its 330 // list of inline locations in bottom-up order i.e. from leaf to root. The 331 // inline location list may include additional entries, users should pick 332 // the last entry in the list with the same function GUID. 333 llvm::SmallVector<llvm::SmallVector<FrameId>> CallSites; 334 335 void clear() { 336 AllocSites.clear(); 337 CallSites.clear(); 338 } 339 340 void merge(const IndexedMemProfRecord &Other) { 341 // TODO: Filter out duplicates which may occur if multiple memprof 342 // profiles are merged together using llvm-profdata. 343 AllocSites.append(Other.AllocSites); 344 CallSites.append(Other.CallSites); 345 } 346 347 size_t serializedSize() const { 348 size_t Result = sizeof(GlobalValue::GUID); 349 for (const IndexedAllocationInfo &N : AllocSites) 350 Result += N.serializedSize(); 351 352 // The number of callsites we have information for. 353 Result += sizeof(uint64_t); 354 for (const auto &Frames : CallSites) { 355 // The number of frame ids to serialize. 356 Result += sizeof(uint64_t); 357 Result += Frames.size() * sizeof(FrameId); 358 } 359 return Result; 360 } 361 362 bool operator==(const IndexedMemProfRecord &Other) const { 363 if (Other.AllocSites.size() != AllocSites.size()) 364 return false; 365 366 if (Other.CallSites.size() != CallSites.size()) 367 return false; 368 369 for (size_t I = 0; I < AllocSites.size(); I++) { 370 if (AllocSites[I] != Other.AllocSites[I]) 371 return false; 372 } 373 374 for (size_t I = 0; I < CallSites.size(); I++) { 375 if (CallSites[I] != Other.CallSites[I]) 376 return false; 377 } 378 return true; 379 } 380 381 // Serializes the memprof records in \p Records to the ostream \p OS based 382 // on the schema provided in \p Schema. 383 void serialize(const MemProfSchema &Schema, raw_ostream &OS); 384 385 // Deserializes memprof records from the Buffer. 386 static IndexedMemProfRecord deserialize(const MemProfSchema &Schema, 387 const unsigned char *Buffer); 388 389 // Returns the GUID for the function name after canonicalization. For 390 // memprof, we remove any .llvm suffix added by LTO. MemProfRecords are 391 // mapped to functions using this GUID. 392 static GlobalValue::GUID getGUID(const StringRef FunctionName); 393 }; 394 395 // Holds the memprof profile information for a function. The internal 396 // representation stores frame contents inline. This representation should 397 // be used for small amount of temporary, in memory instances. 398 struct MemProfRecord { 399 // Same as IndexedMemProfRecord::AllocSites with frame contents inline. 400 llvm::SmallVector<AllocationInfo> AllocSites; 401 // Same as IndexedMemProfRecord::CallSites with frame contents inline. 402 llvm::SmallVector<llvm::SmallVector<Frame>> CallSites; 403 404 MemProfRecord() = default; 405 MemProfRecord( 406 const IndexedMemProfRecord &Record, 407 llvm::function_ref<const Frame(const FrameId Id)> IdToFrameCallback) { 408 for (const IndexedAllocationInfo &IndexedAI : Record.AllocSites) { 409 AllocSites.emplace_back(IndexedAI, IdToFrameCallback); 410 } 411 for (const ArrayRef<FrameId> Site : Record.CallSites) { 412 llvm::SmallVector<Frame> Frames; 413 for (const FrameId Id : Site) { 414 Frames.push_back(IdToFrameCallback(Id)); 415 } 416 CallSites.push_back(Frames); 417 } 418 } 419 420 // Prints out the contents of the memprof record in YAML. 421 void print(llvm::raw_ostream &OS) const { 422 if (!AllocSites.empty()) { 423 OS << " AllocSites:\n"; 424 for (const AllocationInfo &N : AllocSites) 425 N.printYAML(OS); 426 } 427 428 if (!CallSites.empty()) { 429 OS << " CallSites:\n"; 430 for (const llvm::SmallVector<Frame> &Frames : CallSites) { 431 for (const Frame &F : Frames) { 432 OS << " -\n"; 433 F.printYAML(OS); 434 } 435 } 436 } 437 } 438 }; 439 440 // Reads a memprof schema from a buffer. All entries in the buffer are 441 // interpreted as uint64_t. The first entry in the buffer denotes the number of 442 // ids in the schema. Subsequent entries are integers which map to memprof::Meta 443 // enum class entries. After successfully reading the schema, the pointer is one 444 // byte past the schema contents. 445 Expected<MemProfSchema> readMemProfSchema(const unsigned char *&Buffer); 446 447 // Trait for reading IndexedMemProfRecord data from the on-disk hash table. 448 class RecordLookupTrait { 449 public: 450 using data_type = const IndexedMemProfRecord &; 451 using internal_key_type = uint64_t; 452 using external_key_type = uint64_t; 453 using hash_value_type = uint64_t; 454 using offset_type = uint64_t; 455 456 RecordLookupTrait() = delete; 457 RecordLookupTrait(const MemProfSchema &S) : Schema(S) {} 458 459 static bool EqualKey(uint64_t A, uint64_t B) { return A == B; } 460 static uint64_t GetInternalKey(uint64_t K) { return K; } 461 static uint64_t GetExternalKey(uint64_t K) { return K; } 462 463 hash_value_type ComputeHash(uint64_t K) { return K; } 464 465 static std::pair<offset_type, offset_type> 466 ReadKeyDataLength(const unsigned char *&D) { 467 using namespace support; 468 469 offset_type KeyLen = endian::readNext<offset_type, little, unaligned>(D); 470 offset_type DataLen = endian::readNext<offset_type, little, unaligned>(D); 471 return std::make_pair(KeyLen, DataLen); 472 } 473 474 uint64_t ReadKey(const unsigned char *D, offset_type /*Unused*/) { 475 using namespace support; 476 return endian::readNext<external_key_type, little, unaligned>(D); 477 } 478 479 data_type ReadData(uint64_t K, const unsigned char *D, 480 offset_type /*Unused*/) { 481 Record = IndexedMemProfRecord::deserialize(Schema, D); 482 return Record; 483 } 484 485 private: 486 // Holds the memprof schema used to deserialize records. 487 MemProfSchema Schema; 488 // Holds the records from one function deserialized from the indexed format. 489 IndexedMemProfRecord Record; 490 }; 491 492 // Trait for writing IndexedMemProfRecord data to the on-disk hash table. 493 class RecordWriterTrait { 494 public: 495 using key_type = uint64_t; 496 using key_type_ref = uint64_t; 497 498 using data_type = IndexedMemProfRecord; 499 using data_type_ref = IndexedMemProfRecord &; 500 501 using hash_value_type = uint64_t; 502 using offset_type = uint64_t; 503 504 // Pointer to the memprof schema to use for the generator. Unlike the reader 505 // we must use a default constructor with no params for the writer trait so we 506 // have a public member which must be initialized by the user. 507 MemProfSchema *Schema = nullptr; 508 509 RecordWriterTrait() = default; 510 511 static hash_value_type ComputeHash(key_type_ref K) { return K; } 512 513 static std::pair<offset_type, offset_type> 514 EmitKeyDataLength(raw_ostream &Out, key_type_ref K, data_type_ref V) { 515 using namespace support; 516 517 endian::Writer LE(Out, little); 518 offset_type N = sizeof(K); 519 LE.write<offset_type>(N); 520 offset_type M = V.serializedSize(); 521 LE.write<offset_type>(M); 522 return std::make_pair(N, M); 523 } 524 525 void EmitKey(raw_ostream &Out, key_type_ref K, offset_type /*Unused*/) { 526 using namespace support; 527 endian::Writer LE(Out, little); 528 LE.write<uint64_t>(K); 529 } 530 531 void EmitData(raw_ostream &Out, key_type_ref /*Unused*/, data_type_ref V, 532 offset_type /*Unused*/) { 533 assert(Schema != nullptr && "MemProf schema is not initialized!"); 534 V.serialize(*Schema, Out); 535 } 536 }; 537 538 // Trait for writing frame mappings to the on-disk hash table. 539 class FrameWriterTrait { 540 public: 541 using key_type = FrameId; 542 using key_type_ref = FrameId; 543 544 using data_type = Frame; 545 using data_type_ref = Frame &; 546 547 using hash_value_type = FrameId; 548 using offset_type = uint64_t; 549 550 static hash_value_type ComputeHash(key_type_ref K) { return K; } 551 552 static std::pair<offset_type, offset_type> 553 EmitKeyDataLength(raw_ostream &Out, key_type_ref K, data_type_ref V) { 554 using namespace support; 555 endian::Writer LE(Out, little); 556 offset_type N = sizeof(K); 557 LE.write<offset_type>(N); 558 offset_type M = V.serializedSize(); 559 LE.write<offset_type>(M); 560 return std::make_pair(N, M); 561 } 562 563 void EmitKey(raw_ostream &Out, key_type_ref K, offset_type /*Unused*/) { 564 using namespace support; 565 endian::Writer LE(Out, little); 566 LE.write<key_type>(K); 567 } 568 569 void EmitData(raw_ostream &Out, key_type_ref /*Unused*/, data_type_ref V, 570 offset_type /*Unused*/) { 571 V.serialize(Out); 572 } 573 }; 574 575 // Trait for reading frame mappings from the on-disk hash table. 576 class FrameLookupTrait { 577 public: 578 using data_type = const Frame; 579 using internal_key_type = FrameId; 580 using external_key_type = FrameId; 581 using hash_value_type = FrameId; 582 using offset_type = uint64_t; 583 584 static bool EqualKey(internal_key_type A, internal_key_type B) { 585 return A == B; 586 } 587 static uint64_t GetInternalKey(internal_key_type K) { return K; } 588 static uint64_t GetExternalKey(external_key_type K) { return K; } 589 590 hash_value_type ComputeHash(internal_key_type K) { return K; } 591 592 static std::pair<offset_type, offset_type> 593 ReadKeyDataLength(const unsigned char *&D) { 594 using namespace support; 595 596 offset_type KeyLen = endian::readNext<offset_type, little, unaligned>(D); 597 offset_type DataLen = endian::readNext<offset_type, little, unaligned>(D); 598 return std::make_pair(KeyLen, DataLen); 599 } 600 601 uint64_t ReadKey(const unsigned char *D, offset_type /*Unused*/) { 602 using namespace support; 603 return endian::readNext<external_key_type, little, unaligned>(D); 604 } 605 606 data_type ReadData(uint64_t K, const unsigned char *D, 607 offset_type /*Unused*/) { 608 return Frame::deserialize(D); 609 } 610 }; 611 } // namespace memprof 612 } // namespace llvm 613 614 #endif // LLVM_PROFILEDATA_MEMPROF_H_ 615