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