xref: /llvm-project/llvm/unittests/ProfileData/MemProfTest.cpp (revision 76b493128cb171455a1890f7bd2b54f32b7ec2a7)
1 //===- unittests/Support/MemProfTest.cpp ----------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/ProfileData/MemProf.h"
10 #include "llvm/ADT/DenseMap.h"
11 #include "llvm/ADT/MapVector.h"
12 #include "llvm/ADT/STLForwardCompat.h"
13 #include "llvm/DebugInfo/DIContext.h"
14 #include "llvm/DebugInfo/Symbolize/SymbolizableModule.h"
15 #include "llvm/IR/Value.h"
16 #include "llvm/Object/ObjectFile.h"
17 #include "llvm/ProfileData/MemProfData.inc"
18 #include "llvm/ProfileData/MemProfReader.h"
19 #include "llvm/Support/raw_ostream.h"
20 #include "gmock/gmock.h"
21 #include "gtest/gtest.h"
22 
23 #include <initializer_list>
24 
25 namespace llvm {
26 namespace memprof {
27 namespace {
28 
29 using ::llvm::DIGlobal;
30 using ::llvm::DIInliningInfo;
31 using ::llvm::DILineInfo;
32 using ::llvm::DILineInfoSpecifier;
33 using ::llvm::DILocal;
34 using ::llvm::StringRef;
35 using ::llvm::object::SectionedAddress;
36 using ::llvm::symbolize::SymbolizableModule;
37 using ::testing::ElementsAre;
38 using ::testing::IsEmpty;
39 using ::testing::Pair;
40 using ::testing::Return;
41 using ::testing::SizeIs;
42 using ::testing::UnorderedElementsAre;
43 
44 class MockSymbolizer : public SymbolizableModule {
45 public:
46   MOCK_CONST_METHOD3(symbolizeInlinedCode,
47                      DIInliningInfo(SectionedAddress, DILineInfoSpecifier,
48                                     bool));
49   // Most of the methods in the interface are unused. We only mock the
50   // method that we expect to be called from the memprof reader.
51   virtual DILineInfo symbolizeCode(SectionedAddress, DILineInfoSpecifier,
52                                    bool) const {
53     llvm_unreachable("unused");
54   }
55   virtual DIGlobal symbolizeData(SectionedAddress) const {
56     llvm_unreachable("unused");
57   }
58   virtual std::vector<DILocal> symbolizeFrame(SectionedAddress) const {
59     llvm_unreachable("unused");
60   }
61   virtual std::vector<SectionedAddress> findSymbol(StringRef Symbol,
62                                                    uint64_t Offset) const {
63     llvm_unreachable("unused");
64   }
65   virtual bool isWin32Module() const { llvm_unreachable("unused"); }
66   virtual uint64_t getModulePreferredBase() const {
67     llvm_unreachable("unused");
68   }
69 };
70 
71 struct MockInfo {
72   std::string FunctionName;
73   uint32_t Line;
74   uint32_t StartLine;
75   uint32_t Column;
76   std::string FileName = "valid/path.cc";
77 };
78 DIInliningInfo makeInliningInfo(std::initializer_list<MockInfo> MockFrames) {
79   DIInliningInfo Result;
80   for (const auto &Item : MockFrames) {
81     DILineInfo Frame;
82     Frame.FunctionName = Item.FunctionName;
83     Frame.Line = Item.Line;
84     Frame.StartLine = Item.StartLine;
85     Frame.Column = Item.Column;
86     Frame.FileName = Item.FileName;
87     Result.addFrame(Frame);
88   }
89   return Result;
90 }
91 
92 llvm::SmallVector<SegmentEntry, 4> makeSegments() {
93   llvm::SmallVector<SegmentEntry, 4> Result;
94   // Mimic an entry for a non position independent executable.
95   Result.emplace_back(0x0, 0x40000, 0x0);
96   return Result;
97 }
98 
99 const DILineInfoSpecifier specifier() {
100   return DILineInfoSpecifier(
101       DILineInfoSpecifier::FileLineInfoKind::RawValue,
102       DILineInfoSpecifier::FunctionNameKind::LinkageName);
103 }
104 
105 MATCHER_P4(FrameContains, FunctionName, LineOffset, Column, Inline, "") {
106   const Frame &F = arg;
107 
108   const uint64_t ExpectedHash = IndexedMemProfRecord::getGUID(FunctionName);
109   if (F.Function != ExpectedHash) {
110     *result_listener << "Hash mismatch";
111     return false;
112   }
113   if (F.SymbolName && *F.SymbolName != FunctionName) {
114     *result_listener << "SymbolName mismatch\nWant: " << FunctionName
115                      << "\nGot: " << *F.SymbolName;
116     return false;
117   }
118   if (F.LineOffset == LineOffset && F.Column == Column &&
119       F.IsInlineFrame == Inline) {
120     return true;
121   }
122   *result_listener << "LineOffset, Column or Inline mismatch";
123   return false;
124 }
125 
126 TEST(MemProf, FillsValue) {
127   auto Symbolizer = std::make_unique<MockSymbolizer>();
128 
129   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x1000},
130                                                 specifier(), false))
131       .Times(1) // Only once since we remember invalid PCs.
132       .WillRepeatedly(Return(makeInliningInfo({
133           {"new", 70, 57, 3, "memprof/memprof_new_delete.cpp"},
134       })));
135 
136   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x2000},
137                                                 specifier(), false))
138       .Times(1) // Only once since we cache the result for future lookups.
139       .WillRepeatedly(Return(makeInliningInfo({
140           {"foo", 10, 5, 30},
141           {"bar", 201, 150, 20},
142       })));
143 
144   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x3000},
145                                                 specifier(), false))
146       .Times(1)
147       .WillRepeatedly(Return(makeInliningInfo({
148           {"xyz.llvm.123", 10, 5, 30},
149           {"abc", 10, 5, 30},
150       })));
151 
152   CallStackMap CSM;
153   CSM[0x1] = {0x1000, 0x2000, 0x3000};
154 
155   llvm::MapVector<uint64_t, MemInfoBlock> Prof;
156   Prof[0x1].AllocCount = 1;
157 
158   auto Seg = makeSegments();
159 
160   RawMemProfReader Reader(std::move(Symbolizer), Seg, Prof, CSM,
161                           /*KeepName=*/true);
162 
163   llvm::DenseMap<llvm::GlobalValue::GUID, MemProfRecord> Records;
164   for (const auto &Pair : Reader) {
165     Records.insert({Pair.first, Pair.second});
166   }
167 
168   // Mock program pseudocode and expected memprof record contents.
169   //
170   //                              AllocSite       CallSite
171   // inline foo() { new(); }         Y               N
172   // bar() { foo(); }                Y               Y
173   // inline xyz() { bar(); }         N               Y
174   // abc() { xyz(); }                N               Y
175 
176   // We expect 4 records. We attach alloc site data to foo and bar, i.e.
177   // all frames bottom up until we find a non-inline frame. We attach call site
178   // data to bar, xyz and abc.
179   ASSERT_THAT(Records, SizeIs(4));
180 
181   // Check the memprof record for foo.
182   const llvm::GlobalValue::GUID FooId = IndexedMemProfRecord::getGUID("foo");
183   ASSERT_TRUE(Records.contains(FooId));
184   const MemProfRecord &Foo = Records[FooId];
185   ASSERT_THAT(Foo.AllocSites, SizeIs(1));
186   EXPECT_EQ(Foo.AllocSites[0].Info.getAllocCount(), 1U);
187   EXPECT_THAT(Foo.AllocSites[0].CallStack[0],
188               FrameContains("foo", 5U, 30U, true));
189   EXPECT_THAT(Foo.AllocSites[0].CallStack[1],
190               FrameContains("bar", 51U, 20U, false));
191   EXPECT_THAT(Foo.AllocSites[0].CallStack[2],
192               FrameContains("xyz", 5U, 30U, true));
193   EXPECT_THAT(Foo.AllocSites[0].CallStack[3],
194               FrameContains("abc", 5U, 30U, false));
195   EXPECT_TRUE(Foo.CallSites.empty());
196 
197   // Check the memprof record for bar.
198   const llvm::GlobalValue::GUID BarId = IndexedMemProfRecord::getGUID("bar");
199   ASSERT_TRUE(Records.contains(BarId));
200   const MemProfRecord &Bar = Records[BarId];
201   ASSERT_THAT(Bar.AllocSites, SizeIs(1));
202   EXPECT_EQ(Bar.AllocSites[0].Info.getAllocCount(), 1U);
203   EXPECT_THAT(Bar.AllocSites[0].CallStack[0],
204               FrameContains("foo", 5U, 30U, true));
205   EXPECT_THAT(Bar.AllocSites[0].CallStack[1],
206               FrameContains("bar", 51U, 20U, false));
207   EXPECT_THAT(Bar.AllocSites[0].CallStack[2],
208               FrameContains("xyz", 5U, 30U, true));
209   EXPECT_THAT(Bar.AllocSites[0].CallStack[3],
210               FrameContains("abc", 5U, 30U, false));
211 
212   EXPECT_THAT(Bar.CallSites,
213               ElementsAre(ElementsAre(FrameContains("foo", 5U, 30U, true),
214                                       FrameContains("bar", 51U, 20U, false))));
215 
216   // Check the memprof record for xyz.
217   const llvm::GlobalValue::GUID XyzId = IndexedMemProfRecord::getGUID("xyz");
218   ASSERT_TRUE(Records.contains(XyzId));
219   const MemProfRecord &Xyz = Records[XyzId];
220   // Expect the entire frame even though in practice we only need the first
221   // entry here.
222   EXPECT_THAT(Xyz.CallSites,
223               ElementsAre(ElementsAre(FrameContains("xyz", 5U, 30U, true),
224                                       FrameContains("abc", 5U, 30U, false))));
225 
226   // Check the memprof record for abc.
227   const llvm::GlobalValue::GUID AbcId = IndexedMemProfRecord::getGUID("abc");
228   ASSERT_TRUE(Records.contains(AbcId));
229   const MemProfRecord &Abc = Records[AbcId];
230   EXPECT_TRUE(Abc.AllocSites.empty());
231   EXPECT_THAT(Abc.CallSites,
232               ElementsAre(ElementsAre(FrameContains("xyz", 5U, 30U, true),
233                                       FrameContains("abc", 5U, 30U, false))));
234 }
235 
236 TEST(MemProf, PortableWrapper) {
237   MemInfoBlock Info(/*size=*/16, /*access_count=*/7, /*alloc_timestamp=*/1000,
238                     /*dealloc_timestamp=*/2000, /*alloc_cpu=*/3,
239                     /*dealloc_cpu=*/4, /*Histogram=*/0, /*HistogramSize=*/0);
240 
241   const auto Schema = getFullSchema();
242   PortableMemInfoBlock WriteBlock(Info, Schema);
243 
244   std::string Buffer;
245   llvm::raw_string_ostream OS(Buffer);
246   WriteBlock.serialize(Schema, OS);
247 
248   PortableMemInfoBlock ReadBlock(
249       Schema, reinterpret_cast<const unsigned char *>(Buffer.data()));
250 
251   EXPECT_EQ(ReadBlock, WriteBlock);
252   // Here we compare directly with the actual counts instead of MemInfoBlock
253   // members. Since the MemInfoBlock struct is packed and the EXPECT_EQ macros
254   // take a reference to the params, this results in unaligned accesses.
255   EXPECT_EQ(1UL, ReadBlock.getAllocCount());
256   EXPECT_EQ(7ULL, ReadBlock.getTotalAccessCount());
257   EXPECT_EQ(3UL, ReadBlock.getAllocCpuId());
258 }
259 
260 TEST(MemProf, RecordSerializationRoundTripVerion2) {
261   const auto Schema = getFullSchema();
262 
263   MemInfoBlock Info(/*size=*/16, /*access_count=*/7, /*alloc_timestamp=*/1000,
264                     /*dealloc_timestamp=*/2000, /*alloc_cpu=*/3,
265                     /*dealloc_cpu=*/4, /*Histogram=*/0, /*HistogramSize=*/0);
266 
267   llvm::SmallVector<CallStackId> CallStackIds = {0x123, 0x456};
268 
269   llvm::SmallVector<CallStackId> CallSiteIds = {0x333, 0x444};
270 
271   IndexedMemProfRecord Record;
272   for (const auto &CSId : CallStackIds) {
273     // Use the same info block for both allocation sites.
274     Record.AllocSites.emplace_back(CSId, Info);
275   }
276   Record.CallSiteIds.assign(CallSiteIds);
277 
278   std::string Buffer;
279   llvm::raw_string_ostream OS(Buffer);
280   Record.serialize(Schema, OS, Version2);
281 
282   const IndexedMemProfRecord GotRecord = IndexedMemProfRecord::deserialize(
283       Schema, reinterpret_cast<const unsigned char *>(Buffer.data()), Version2);
284 
285   EXPECT_EQ(Record, GotRecord);
286 }
287 
288 TEST(MemProf, RecordSerializationRoundTripVersion2HotColdSchema) {
289   const auto Schema = getHotColdSchema();
290 
291   MemInfoBlock Info;
292   Info.AllocCount = 11;
293   Info.TotalSize = 22;
294   Info.TotalLifetime = 33;
295   Info.TotalLifetimeAccessDensity = 44;
296 
297   llvm::SmallVector<CallStackId> CallStackIds = {0x123, 0x456};
298 
299   llvm::SmallVector<CallStackId> CallSiteIds = {0x333, 0x444};
300 
301   IndexedMemProfRecord Record;
302   for (const auto &CSId : CallStackIds) {
303     // Use the same info block for both allocation sites.
304     Record.AllocSites.emplace_back(CSId, Info, Schema);
305   }
306   Record.CallSiteIds.assign(CallSiteIds);
307 
308   std::bitset<llvm::to_underlying(Meta::Size)> SchemaBitSet;
309   for (auto Id : Schema)
310     SchemaBitSet.set(llvm::to_underlying(Id));
311 
312   // Verify that SchemaBitSet has the fields we expect and nothing else, which
313   // we check with count().
314   EXPECT_EQ(SchemaBitSet.count(), 4U);
315   EXPECT_TRUE(SchemaBitSet[llvm::to_underlying(Meta::AllocCount)]);
316   EXPECT_TRUE(SchemaBitSet[llvm::to_underlying(Meta::TotalSize)]);
317   EXPECT_TRUE(SchemaBitSet[llvm::to_underlying(Meta::TotalLifetime)]);
318   EXPECT_TRUE(
319       SchemaBitSet[llvm::to_underlying(Meta::TotalLifetimeAccessDensity)]);
320 
321   // Verify that Schema has propagated all the way to the Info field in each
322   // IndexedAllocationInfo.
323   ASSERT_THAT(Record.AllocSites, SizeIs(2));
324   EXPECT_EQ(Record.AllocSites[0].Info.getSchema(), SchemaBitSet);
325   EXPECT_EQ(Record.AllocSites[1].Info.getSchema(), SchemaBitSet);
326 
327   std::string Buffer;
328   llvm::raw_string_ostream OS(Buffer);
329   Record.serialize(Schema, OS, Version2);
330 
331   const IndexedMemProfRecord GotRecord = IndexedMemProfRecord::deserialize(
332       Schema, reinterpret_cast<const unsigned char *>(Buffer.data()), Version2);
333 
334   // Verify that Schema comes back correctly after deserialization. Technically,
335   // the comparison between Record and GotRecord below includes the comparison
336   // of their Schemas, but we'll verify the Schemas on our own.
337   ASSERT_THAT(GotRecord.AllocSites, SizeIs(2));
338   EXPECT_EQ(GotRecord.AllocSites[0].Info.getSchema(), SchemaBitSet);
339   EXPECT_EQ(GotRecord.AllocSites[1].Info.getSchema(), SchemaBitSet);
340 
341   EXPECT_EQ(Record, GotRecord);
342 }
343 
344 TEST(MemProf, SymbolizationFilter) {
345   auto Symbolizer = std::make_unique<MockSymbolizer>();
346 
347   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x1000},
348                                                 specifier(), false))
349       .Times(1) // once since we don't lookup invalid PCs repeatedly.
350       .WillRepeatedly(Return(makeInliningInfo({
351           {"malloc", 70, 57, 3, "memprof/memprof_malloc_linux.cpp"},
352       })));
353 
354   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x2000},
355                                                 specifier(), false))
356       .Times(1) // once since we don't lookup invalid PCs repeatedly.
357       .WillRepeatedly(Return(makeInliningInfo({
358           {"new", 70, 57, 3, "memprof/memprof_new_delete.cpp"},
359       })));
360 
361   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x3000},
362                                                 specifier(), false))
363       .Times(1) // once since we don't lookup invalid PCs repeatedly.
364       .WillRepeatedly(Return(makeInliningInfo({
365           {DILineInfo::BadString, 0, 0, 0},
366       })));
367 
368   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x4000},
369                                                 specifier(), false))
370       .Times(1)
371       .WillRepeatedly(Return(makeInliningInfo({
372           {"foo", 10, 5, 30, "memprof/memprof_test_file.cpp"},
373       })));
374 
375   EXPECT_CALL(*Symbolizer, symbolizeInlinedCode(SectionedAddress{0x5000},
376                                                 specifier(), false))
377       .Times(1)
378       .WillRepeatedly(Return(makeInliningInfo({
379           // Depending on how the runtime was compiled, only the filename
380           // may be present in the debug information.
381           {"malloc", 70, 57, 3, "memprof_malloc_linux.cpp"},
382       })));
383 
384   CallStackMap CSM;
385   CSM[0x1] = {0x1000, 0x2000, 0x3000, 0x4000};
386   // This entry should be dropped since all PCs are either not
387   // symbolizable or belong to the runtime.
388   CSM[0x2] = {0x1000, 0x2000, 0x5000};
389 
390   llvm::MapVector<uint64_t, MemInfoBlock> Prof;
391   Prof[0x1].AllocCount = 1;
392   Prof[0x2].AllocCount = 1;
393 
394   auto Seg = makeSegments();
395 
396   RawMemProfReader Reader(std::move(Symbolizer), Seg, Prof, CSM);
397 
398   llvm::SmallVector<MemProfRecord, 1> Records;
399   for (const auto &KeyRecordPair : Reader) {
400     Records.push_back(KeyRecordPair.second);
401   }
402 
403   ASSERT_THAT(Records, SizeIs(1));
404   ASSERT_THAT(Records[0].AllocSites, SizeIs(1));
405   EXPECT_THAT(Records[0].AllocSites[0].CallStack,
406               ElementsAre(FrameContains("foo", 5U, 30U, false)));
407 }
408 
409 TEST(MemProf, BaseMemProfReader) {
410   IndexedMemProfData MemProfData;
411   Frame F1(/*Hash=*/IndexedMemProfRecord::getGUID("foo"), /*LineOffset=*/20,
412            /*Column=*/5, /*IsInlineFrame=*/true);
413   Frame F2(/*Hash=*/IndexedMemProfRecord::getGUID("bar"), /*LineOffset=*/10,
414            /*Column=*/2, /*IsInlineFrame=*/false);
415   MemProfData.addFrame(F1);
416   MemProfData.addFrame(F2);
417 
418   llvm::SmallVector<FrameId> CallStack{F1.hash(), F2.hash()};
419   CallStackId CSId = MemProfData.addCallStack(std::move(CallStack));
420 
421   IndexedMemProfRecord FakeRecord;
422   MemInfoBlock Block;
423   Block.AllocCount = 1U, Block.TotalAccessDensity = 4,
424   Block.TotalLifetime = 200001;
425   FakeRecord.AllocSites.emplace_back(/*CSId=*/CSId, /*MB=*/Block);
426   MemProfData.Records.insert({F1.hash(), FakeRecord});
427 
428   MemProfReader Reader(std::move(MemProfData));
429 
430   llvm::SmallVector<MemProfRecord, 1> Records;
431   for (const auto &KeyRecordPair : Reader) {
432     Records.push_back(KeyRecordPair.second);
433   }
434 
435   ASSERT_THAT(Records, SizeIs(1));
436   ASSERT_THAT(Records[0].AllocSites, SizeIs(1));
437   EXPECT_THAT(Records[0].AllocSites[0].CallStack,
438               ElementsAre(FrameContains("foo", 20U, 5U, true),
439                           FrameContains("bar", 10U, 2U, false)));
440 }
441 
442 TEST(MemProf, BaseMemProfReaderWithCSIdMap) {
443   IndexedMemProfData MemProfData;
444   Frame F1(/*Hash=*/IndexedMemProfRecord::getGUID("foo"), /*LineOffset=*/20,
445            /*Column=*/5, /*IsInlineFrame=*/true);
446   Frame F2(/*Hash=*/IndexedMemProfRecord::getGUID("bar"), /*LineOffset=*/10,
447            /*Column=*/2, /*IsInlineFrame=*/false);
448   MemProfData.addFrame(F1);
449   MemProfData.addFrame(F2);
450 
451   llvm::SmallVector<FrameId> CallStack = {F1.hash(), F2.hash()};
452   MemProfData.addCallStack(CallStack);
453 
454   IndexedMemProfRecord FakeRecord;
455   MemInfoBlock Block;
456   Block.AllocCount = 1U, Block.TotalAccessDensity = 4,
457   Block.TotalLifetime = 200001;
458   FakeRecord.AllocSites.emplace_back(
459       /*CSId=*/hashCallStack(CallStack),
460       /*MB=*/Block);
461   MemProfData.Records.insert({F1.hash(), FakeRecord});
462 
463   MemProfReader Reader(std::move(MemProfData));
464 
465   llvm::SmallVector<MemProfRecord, 1> Records;
466   for (const auto &KeyRecordPair : Reader) {
467     Records.push_back(KeyRecordPair.second);
468   }
469 
470   ASSERT_THAT(Records, SizeIs(1));
471   ASSERT_THAT(Records[0].AllocSites, SizeIs(1));
472   EXPECT_THAT(Records[0].AllocSites[0].CallStack,
473               ElementsAre(FrameContains("foo", 20U, 5U, true),
474                           FrameContains("bar", 10U, 2U, false)));
475 }
476 
477 TEST(MemProf, IndexedMemProfRecordToMemProfRecord) {
478   // Verify that MemProfRecord can be constructed from IndexedMemProfRecord with
479   // CallStackIds only.
480 
481   IndexedMemProfData MemProfData;
482   Frame F1(1, 0, 0, false);
483   Frame F2(2, 0, 0, false);
484   Frame F3(3, 0, 0, false);
485   Frame F4(4, 0, 0, false);
486   MemProfData.addFrame(F1);
487   MemProfData.addFrame(F2);
488   MemProfData.addFrame(F3);
489   MemProfData.addFrame(F4);
490 
491   llvm::SmallVector<FrameId> CS1 = {F1.hash(), F2.hash()};
492   llvm::SmallVector<FrameId> CS2 = {F1.hash(), F3.hash()};
493   llvm::SmallVector<FrameId> CS3 = {F2.hash(), F3.hash()};
494   llvm::SmallVector<FrameId> CS4 = {F2.hash(), F4.hash()};
495   MemProfData.addCallStack(CS1);
496   MemProfData.addCallStack(CS2);
497   MemProfData.addCallStack(CS3);
498   MemProfData.addCallStack(CS4);
499 
500   IndexedMemProfRecord IndexedRecord;
501   IndexedAllocationInfo AI;
502   AI.CSId = hashCallStack(CS1);
503   IndexedRecord.AllocSites.push_back(AI);
504   AI.CSId = hashCallStack(CS2);
505   IndexedRecord.AllocSites.push_back(AI);
506   IndexedRecord.CallSiteIds.push_back(hashCallStack(CS3));
507   IndexedRecord.CallSiteIds.push_back(hashCallStack(CS4));
508 
509   FrameIdConverter<decltype(MemProfData.Frames)> FrameIdConv(
510       MemProfData.Frames);
511   CallStackIdConverter<decltype(MemProfData.CallStacks)> CSIdConv(
512       MemProfData.CallStacks, FrameIdConv);
513 
514   MemProfRecord Record = IndexedRecord.toMemProfRecord(CSIdConv);
515 
516   // Make sure that all lookups are successful.
517   ASSERT_EQ(FrameIdConv.LastUnmappedId, std::nullopt);
518   ASSERT_EQ(CSIdConv.LastUnmappedId, std::nullopt);
519 
520   // Verify the contents of Record.
521   ASSERT_THAT(Record.AllocSites, SizeIs(2));
522   EXPECT_THAT(Record.AllocSites[0].CallStack, ElementsAre(F1, F2));
523   EXPECT_THAT(Record.AllocSites[1].CallStack, ElementsAre(F1, F3));
524   EXPECT_THAT(Record.CallSites,
525               ElementsAre(ElementsAre(F2, F3), ElementsAre(F2, F4)));
526 }
527 
528 // Populate those fields returned by getHotColdSchema.
529 MemInfoBlock makePartialMIB() {
530   MemInfoBlock MIB;
531   MIB.AllocCount = 1;
532   MIB.TotalSize = 5;
533   MIB.TotalLifetime = 10;
534   MIB.TotalLifetimeAccessDensity = 23;
535   return MIB;
536 }
537 
538 TEST(MemProf, MissingCallStackId) {
539   // Use a non-existent CallStackId to trigger a mapping error in
540   // toMemProfRecord.
541   IndexedAllocationInfo AI(0xdeadbeefU, makePartialMIB(), getHotColdSchema());
542 
543   IndexedMemProfRecord IndexedMR;
544   IndexedMR.AllocSites.push_back(AI);
545 
546   // Create empty maps.
547   IndexedMemProfData MemProfData;
548   FrameIdConverter<decltype(MemProfData.Frames)> FrameIdConv(
549       MemProfData.Frames);
550   CallStackIdConverter<decltype(MemProfData.CallStacks)> CSIdConv(
551       MemProfData.CallStacks, FrameIdConv);
552 
553   // We are only interested in errors, not the return value.
554   (void)IndexedMR.toMemProfRecord(CSIdConv);
555 
556   ASSERT_TRUE(CSIdConv.LastUnmappedId.has_value());
557   EXPECT_EQ(*CSIdConv.LastUnmappedId, 0xdeadbeefU);
558   EXPECT_EQ(FrameIdConv.LastUnmappedId, std::nullopt);
559 }
560 
561 TEST(MemProf, MissingFrameId) {
562   IndexedAllocationInfo AI(0x222, makePartialMIB(), getHotColdSchema());
563 
564   IndexedMemProfRecord IndexedMR;
565   IndexedMR.AllocSites.push_back(AI);
566 
567   // An empty Frame map to trigger a mapping error.
568   IndexedMemProfData MemProfData;
569   MemProfData.CallStacks.insert({0x222, {2, 3}});
570 
571   FrameIdConverter<decltype(MemProfData.Frames)> FrameIdConv(
572       MemProfData.Frames);
573   CallStackIdConverter<decltype(MemProfData.CallStacks)> CSIdConv(
574       MemProfData.CallStacks, FrameIdConv);
575 
576   // We are only interested in errors, not the return value.
577   (void)IndexedMR.toMemProfRecord(CSIdConv);
578 
579   EXPECT_EQ(CSIdConv.LastUnmappedId, std::nullopt);
580   ASSERT_TRUE(FrameIdConv.LastUnmappedId.has_value());
581   EXPECT_EQ(*FrameIdConv.LastUnmappedId, 3U);
582 }
583 
584 // Verify CallStackRadixTreeBuilder can handle empty inputs.
585 TEST(MemProf, RadixTreeBuilderEmpty) {
586   llvm::DenseMap<FrameId, LinearFrameId> MemProfFrameIndexes;
587   llvm::MapVector<CallStackId, llvm::SmallVector<FrameId>> MemProfCallStackData;
588   llvm::DenseMap<FrameId, FrameStat> FrameHistogram =
589       computeFrameHistogram<FrameId>(MemProfCallStackData);
590   CallStackRadixTreeBuilder<FrameId> Builder;
591   Builder.build(std::move(MemProfCallStackData), &MemProfFrameIndexes,
592                 FrameHistogram);
593   ASSERT_THAT(Builder.getRadixArray(), testing::IsEmpty());
594   const auto Mappings = Builder.takeCallStackPos();
595   ASSERT_THAT(Mappings, testing::IsEmpty());
596 }
597 
598 // Verify CallStackRadixTreeBuilder can handle one trivial call stack.
599 TEST(MemProf, RadixTreeBuilderOne) {
600   llvm::DenseMap<FrameId, LinearFrameId> MemProfFrameIndexes = {
601       {11, 1}, {12, 2}, {13, 3}};
602   llvm::SmallVector<FrameId> CS1 = {13, 12, 11};
603   llvm::MapVector<CallStackId, llvm::SmallVector<FrameId>> MemProfCallStackData;
604   MemProfCallStackData.insert({hashCallStack(CS1), CS1});
605   llvm::DenseMap<FrameId, FrameStat> FrameHistogram =
606       computeFrameHistogram<FrameId>(MemProfCallStackData);
607   CallStackRadixTreeBuilder<FrameId> Builder;
608   Builder.build(std::move(MemProfCallStackData), &MemProfFrameIndexes,
609                 FrameHistogram);
610   EXPECT_THAT(Builder.getRadixArray(),
611               ElementsAre(3U, // Size of CS1,
612                           3U, // MemProfFrameIndexes[13]
613                           2U, // MemProfFrameIndexes[12]
614                           1U  // MemProfFrameIndexes[11]
615                           ));
616   const auto Mappings = Builder.takeCallStackPos();
617   EXPECT_THAT(Mappings, UnorderedElementsAre(Pair(hashCallStack(CS1), 0U)));
618 }
619 
620 // Verify CallStackRadixTreeBuilder can form a link between two call stacks.
621 TEST(MemProf, RadixTreeBuilderTwo) {
622   llvm::DenseMap<FrameId, LinearFrameId> MemProfFrameIndexes = {
623       {11, 1}, {12, 2}, {13, 3}};
624   llvm::SmallVector<FrameId> CS1 = {12, 11};
625   llvm::SmallVector<FrameId> CS2 = {13, 12, 11};
626   llvm::MapVector<CallStackId, llvm::SmallVector<FrameId>> MemProfCallStackData;
627   MemProfCallStackData.insert({hashCallStack(CS1), CS1});
628   MemProfCallStackData.insert({hashCallStack(CS2), CS2});
629   llvm::DenseMap<FrameId, FrameStat> FrameHistogram =
630       computeFrameHistogram<FrameId>(MemProfCallStackData);
631   CallStackRadixTreeBuilder<FrameId> Builder;
632   Builder.build(std::move(MemProfCallStackData), &MemProfFrameIndexes,
633                 FrameHistogram);
634   EXPECT_THAT(Builder.getRadixArray(),
635               ElementsAre(2U,                        // Size of CS1
636                           static_cast<uint32_t>(-3), // Jump 3 steps
637                           3U,                        // Size of CS2
638                           3U,                        // MemProfFrameIndexes[13]
639                           2U,                        // MemProfFrameIndexes[12]
640                           1U                         // MemProfFrameIndexes[11]
641                           ));
642   const auto Mappings = Builder.takeCallStackPos();
643   EXPECT_THAT(Mappings, UnorderedElementsAre(Pair(hashCallStack(CS1), 0U),
644                                              Pair(hashCallStack(CS2), 2U)));
645 }
646 
647 // Verify CallStackRadixTreeBuilder can form a jump to a prefix that itself has
648 // another jump to another prefix.
649 TEST(MemProf, RadixTreeBuilderSuccessiveJumps) {
650   llvm::DenseMap<FrameId, LinearFrameId> MemProfFrameIndexes = {
651       {11, 1}, {12, 2}, {13, 3}, {14, 4}, {15, 5}, {16, 6}, {17, 7}, {18, 8},
652   };
653   llvm::SmallVector<FrameId> CS1 = {14, 13, 12, 11};
654   llvm::SmallVector<FrameId> CS2 = {15, 13, 12, 11};
655   llvm::SmallVector<FrameId> CS3 = {17, 16, 12, 11};
656   llvm::SmallVector<FrameId> CS4 = {18, 16, 12, 11};
657   llvm::MapVector<CallStackId, llvm::SmallVector<FrameId>> MemProfCallStackData;
658   MemProfCallStackData.insert({hashCallStack(CS1), CS1});
659   MemProfCallStackData.insert({hashCallStack(CS2), CS2});
660   MemProfCallStackData.insert({hashCallStack(CS3), CS3});
661   MemProfCallStackData.insert({hashCallStack(CS4), CS4});
662   llvm::DenseMap<FrameId, FrameStat> FrameHistogram =
663       computeFrameHistogram<FrameId>(MemProfCallStackData);
664   CallStackRadixTreeBuilder<FrameId> Builder;
665   Builder.build(std::move(MemProfCallStackData), &MemProfFrameIndexes,
666                 FrameHistogram);
667   EXPECT_THAT(Builder.getRadixArray(),
668               ElementsAre(4U,                        // Size of CS1
669                           4U,                        // MemProfFrameIndexes[14]
670                           static_cast<uint32_t>(-3), // Jump 3 steps
671                           4U,                        // Size of CS2
672                           5U,                        // MemProfFrameIndexes[15]
673                           3U,                        // MemProfFrameIndexes[13]
674                           static_cast<uint32_t>(-7), // Jump 7 steps
675                           4U,                        // Size of CS3
676                           7U,                        // MemProfFrameIndexes[17]
677                           static_cast<uint32_t>(-3), // Jump 3 steps
678                           4U,                        // Size of CS4
679                           8U,                        // MemProfFrameIndexes[18]
680                           6U,                        // MemProfFrameIndexes[16]
681                           2U,                        // MemProfFrameIndexes[12]
682                           1U                         // MemProfFrameIndexes[11]
683                           ));
684   const auto Mappings = Builder.takeCallStackPos();
685   EXPECT_THAT(Mappings, UnorderedElementsAre(Pair(hashCallStack(CS1), 0U),
686                                              Pair(hashCallStack(CS2), 3U),
687                                              Pair(hashCallStack(CS3), 7U),
688                                              Pair(hashCallStack(CS4), 10U)));
689 }
690 
691 // Verify that we can parse YAML and retrieve IndexedMemProfData as expected.
692 TEST(MemProf, YAMLParser) {
693   StringRef YAMLData = R"YAML(
694 ---
695 HeapProfileRecords:
696 - GUID: 0xdeadbeef12345678
697   AllocSites:
698   - Callstack:
699     - {Function: 0x100, LineOffset: 11, Column: 10, IsInlineFrame: true}
700     - {Function: 0x200, LineOffset: 22, Column: 20, IsInlineFrame: false}
701     MemInfoBlock:
702       AllocCount: 777
703       TotalSize: 888
704   - Callstack:
705     - {Function: 0x300, LineOffset: 33, Column: 30, IsInlineFrame: false}
706     - {Function: 0x400, LineOffset: 44, Column: 40, IsInlineFrame: true}
707     MemInfoBlock:
708       AllocCount: 666
709       TotalSize: 555
710   CallSites:
711   - - {Function: 0x500, LineOffset: 55, Column: 50, IsInlineFrame: true}
712     - {Function: 0x600, LineOffset: 66, Column: 60, IsInlineFrame: false}
713   - - {Function: 0x700, LineOffset: 77, Column: 70, IsInlineFrame: true}
714     - {Function: 0x800, LineOffset: 88, Column: 80, IsInlineFrame: false}
715 )YAML";
716 
717   YAMLMemProfReader YAMLReader;
718   YAMLReader.parse(YAMLData);
719   IndexedMemProfData MemProfData = YAMLReader.takeMemProfData();
720 
721   Frame F1(0x100, 11, 10, true);
722   Frame F2(0x200, 22, 20, false);
723   Frame F3(0x300, 33, 30, false);
724   Frame F4(0x400, 44, 40, true);
725   Frame F5(0x500, 55, 50, true);
726   Frame F6(0x600, 66, 60, false);
727   Frame F7(0x700, 77, 70, true);
728   Frame F8(0x800, 88, 80, false);
729 
730   llvm::SmallVector<FrameId> CS1 = {F1.hash(), F2.hash()};
731   llvm::SmallVector<FrameId> CS2 = {F3.hash(), F4.hash()};
732   llvm::SmallVector<FrameId> CS3 = {F5.hash(), F6.hash()};
733   llvm::SmallVector<FrameId> CS4 = {F7.hash(), F8.hash()};
734 
735   // Verify the entire contents of MemProfData.Frames.
736   EXPECT_THAT(MemProfData.Frames,
737               UnorderedElementsAre(Pair(F1.hash(), F1), Pair(F2.hash(), F2),
738                                    Pair(F3.hash(), F3), Pair(F4.hash(), F4),
739                                    Pair(F5.hash(), F5), Pair(F6.hash(), F6),
740                                    Pair(F7.hash(), F7), Pair(F8.hash(), F8)));
741 
742   // Verify the entire contents of MemProfData.Frames.
743   EXPECT_THAT(MemProfData.CallStacks,
744               UnorderedElementsAre(Pair(hashCallStack(CS1), CS1),
745                                    Pair(hashCallStack(CS2), CS2),
746                                    Pair(hashCallStack(CS3), CS3),
747                                    Pair(hashCallStack(CS4), CS4)));
748 
749   // Verify the entire contents of MemProfData.Records.
750   ASSERT_THAT(MemProfData.Records, SizeIs(1));
751   const auto &[GUID, Record] = *MemProfData.Records.begin();
752   EXPECT_EQ(GUID, 0xdeadbeef12345678ULL);
753   ASSERT_THAT(Record.AllocSites, SizeIs(2));
754   EXPECT_EQ(Record.AllocSites[0].CSId, hashCallStack(CS1));
755   EXPECT_EQ(Record.AllocSites[0].Info.getAllocCount(), 777U);
756   EXPECT_EQ(Record.AllocSites[0].Info.getTotalSize(), 888U);
757   EXPECT_EQ(Record.AllocSites[1].CSId, hashCallStack(CS2));
758   EXPECT_EQ(Record.AllocSites[1].Info.getAllocCount(), 666U);
759   EXPECT_EQ(Record.AllocSites[1].Info.getTotalSize(), 555U);
760   EXPECT_THAT(Record.CallSiteIds,
761               ElementsAre(hashCallStack(CS3), hashCallStack(CS4)));
762 }
763 
764 // Verify that the YAML parser accepts a GUID expressed as a function name.
765 TEST(MemProf, YAMLParserGUID) {
766   StringRef YAMLData = R"YAML(
767 ---
768 HeapProfileRecords:
769 - GUID: _Z3fooi
770   AllocSites:
771   - Callstack:
772     - {Function: 0x100, LineOffset: 11, Column: 10, IsInlineFrame: true}
773     MemInfoBlock: {}
774   CallSites: []
775 )YAML";
776 
777   YAMLMemProfReader YAMLReader;
778   YAMLReader.parse(YAMLData);
779   IndexedMemProfData MemProfData = YAMLReader.takeMemProfData();
780 
781   Frame F1(0x100, 11, 10, true);
782 
783   llvm::SmallVector<FrameId> CS1 = {F1.hash()};
784 
785   // Verify the entire contents of MemProfData.Frames.
786   EXPECT_THAT(MemProfData.Frames, UnorderedElementsAre(Pair(F1.hash(), F1)));
787 
788   // Verify the entire contents of MemProfData.Frames.
789   EXPECT_THAT(MemProfData.CallStacks,
790               UnorderedElementsAre(Pair(hashCallStack(CS1), CS1)));
791 
792   // Verify the entire contents of MemProfData.Records.
793   ASSERT_THAT(MemProfData.Records, SizeIs(1));
794   const auto &[GUID, Record] = MemProfData.Records.front();
795   EXPECT_EQ(GUID, IndexedMemProfRecord::getGUID("_Z3fooi"));
796   ASSERT_THAT(Record.AllocSites, SizeIs(1));
797   EXPECT_EQ(Record.AllocSites[0].CSId, hashCallStack(CS1));
798   EXPECT_THAT(Record.CallSiteIds, IsEmpty());
799 }
800 
801 template <typename T> std::string serializeInYAML(T &Val) {
802   std::string Out;
803   llvm::raw_string_ostream OS(Out);
804   llvm::yaml::Output Yout(OS);
805   Yout << Val;
806   return Out;
807 }
808 
809 TEST(MemProf, YAMLWriterFrame) {
810   Frame F(11, 22, 33, true);
811 
812   std::string Out = serializeInYAML(F);
813   EXPECT_EQ(Out, R"YAML(---
814 { Function: 11, LineOffset: 22, Column: 33, IsInlineFrame: true }
815 ...
816 )YAML");
817 }
818 
819 TEST(MemProf, YAMLWriterMIB) {
820   MemInfoBlock MIB;
821   MIB.AllocCount = 111;
822   MIB.TotalSize = 222;
823   MIB.TotalLifetime = 333;
824   MIB.TotalLifetimeAccessDensity = 444;
825   PortableMemInfoBlock PMIB(MIB, getHotColdSchema());
826 
827   std::string Out = serializeInYAML(PMIB);
828   EXPECT_EQ(Out, R"YAML(---
829 AllocCount:      111
830 TotalSize:       222
831 TotalLifetime:   333
832 TotalLifetimeAccessDensity: 444
833 ...
834 )YAML");
835 }
836 } // namespace
837 } // namespace memprof
838 } // namespace llvm
839