[memprof] Use CallStackRadixTreeBuilder in the V3 format (#94708)

This patch integrates CallStackRadixTreeBuilder into the V3 format,
reducing the profile size to about 27% of the V2 profile size.

- Serialization: writeMemProfCallStackArray just needs to write out
  the radix tree array prepared by CallStackRadixTreeBuilder.
  Mappings from CallStackIds to LinearCallStackIds are moved by new
  function CallStackRadixTreeBuilder::takeCallStackPos.

- Deserialization: Deserializing a call stack is the same as
  deserializing an array encoded in the obvious manner -- the length
  followed by the payload, except that we need to follow a pointer to
  the parent to take advantage of common prefixes once in a while.
  This patch teaches LinearCallStackIdConverter to how to handle those
  pointers.

1 files changed, 4 insertions, 4 deletions

diff --git a/llvm/unittests/ProfileData/MemProfTest.cpp b/llvm/unittests/ProfileData/MemProfTest.cpp
index e120bc3..2642120 100644
--- a/llvm/unittests/ProfileData/MemProfTest.cpp
+++ b/llvm/unittests/ProfileData/MemProfTest.cpp
@@ -670,7 +670,7 @@ TEST(MemProf, RadixTreeBuilderEmpty) {
   llvm::memprof::CallStackRadixTreeBuilder Builder;
   Builder.build(std::move(MemProfCallStackData), MemProfFrameIndexes);
   ASSERT_THAT(Builder.getRadixArray(), testing::IsEmpty());
-  const auto &Mappings = Builder.getCallStackPos();
+  const auto Mappings = Builder.takeCallStackPos();
   ASSERT_THAT(Mappings, testing::IsEmpty());
 }
 
@@ -689,7 +689,7 @@ TEST(MemProf, RadixTreeBuilderOne) {
                                            2U, // MemProfFrameIndexes[12]
                                            1U  // MemProfFrameIndexes[11]
                                        }));
-  const auto &Mappings = Builder.getCallStackPos();
+  const auto Mappings = Builder.takeCallStackPos();
   ASSERT_THAT(Mappings, SizeIs(1));
   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
                             llvm::memprof::hashCallStack(CS1), 0U)));
@@ -715,7 +715,7 @@ TEST(MemProf, RadixTreeBuilderTwo) {
                   2U,                        // MemProfFrameIndexes[12]
                   1U                         // MemProfFrameIndexes[11]
               }));
-  const auto &Mappings = Builder.getCallStackPos();
+  const auto Mappings = Builder.takeCallStackPos();
   ASSERT_THAT(Mappings, SizeIs(2));
   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
                             llvm::memprof::hashCallStack(CS1), 0U)));
@@ -758,7 +758,7 @@ TEST(MemProf, RadixTreeBuilderSuccessiveJumps) {
                   2U,                        // MemProfFrameIndexes[12]
                   1U                         // MemProfFrameIndexes[11]
               }));
-  const auto &Mappings = Builder.getCallStackPos();
+  const auto Mappings = Builder.takeCallStackPos();
   ASSERT_THAT(Mappings, SizeIs(4));
   EXPECT_THAT(Mappings, testing::Contains(testing::Pair(
                             llvm::memprof::hashCallStack(CS1), 0U)));