[Profiling] Write out sparse indexed profiles

[vsk]

Summary

Instead of writing out InstrProfRecords which contain only 0 counts, skip them.

The Xcode team asked for this so that the (often sparse) profiles gathered from UI tests take up less space.

[davidxl]

Any reason why we can not just always emit sparse output ?

unittests/ProfileData/CoverageMappingTest.cpp

293

what is this change about?

[slingn]

Making sparse the default would change the output of llvm-profdata show since zero count functions would no longer be listed. Is that a concern? In other words, could existing users of llvm-profdata be relying on it in any way?

include/llvm/ProfileData/InstrProfWriter.h

64

I'm also not sure about 'Useful' as the name - since zeros are useful - just not necessary to write out.

How about shouldEncodeData()?

lib/ProfileData/InstrProfWriter.cpp

153

Since this takes a boolean I would suggest naming it setSparseOutput(bool Sparse)

tools/llvm-profdata/llvm-profdata.cpp

231

I would invert this to say 'only meaningful for instrumentation profiles'.

[slingn]

If there is to be a new option for llvm-profdata then the *.rst documentation file needs to be updated too:
llvm/docs/CommandGuide/llvm-profdata.rst

[vsk]

I think we should keep the non-sparse mode. Users of llvm-profdata might rely on having records for functions which don't execute (though I imagine this is a small group). In addition, one of our tests assumes this (weight-instr.test). Having -sparse turned on by default seems fair to me.

unittests/ProfileData/CoverageMappingTest.cpp

293

IIUC, changing the counter from 10 to 0 doesn't alter the spirit of this test.

The change lets us check that we behave correctly when we don't write Record out.

[vsk]

• Addressed sling's comments.

[davidxl]

unittests/ProfileData/CoverageMappingTest.cpp

293

So why just this one change. For instance, the previous test can also be changed with {0, 0} counts to cover both the sparse and non sparse paths.

[davidxl]

I have one major concern with this patch:

When the records for those zero count functions are skipped, the profile-use compilation may get confused -- those functions are now treated as 'unknown functions' which the compiler can not do anything about them. One of the main benefit of keeping zero count functions is that the compiler can do very aggressive size optimizations on them.

If we go with this route, we need a way to store place holder records for the cold functions.

If we do care about size of indexed profile data, name compression will be very efficient way. My pending patch does not touch Indexed profile format, but it can be easily extended to Indexed format (and also keeping the ability to read the old format files).

lib/ProfileData/InstrProfWriter.cpp

197

Is this check needed?

[vsk]

(Sorry - typo earlier, slingn's*.)

unittests/ProfileData/CoverageMappingTest.cpp

293

Changing this one test lets us check that we get coverage information for functions which don't execute in sparse mode. I'll update the test you mentioned so it has records with zero and non-zero count.

[vsk]

• Extend a unittest in CoverageMappingTest.

[vsk]

Good point. Would making -sparse opt-in help with this? That way if someone really cares about trimming down the profdata file (e.g if optimization is not a concern), they have one more option. Having this in addition to your name compression patch can't hurt.

[vsk]

• Turn off -sparse by default to address @davidxl's concern. This has the added benefit of letting us leave weight-instr.test unchanged.

[davidxl]

that sounds good to me.

David

[vsk]

• Remove dead check.

[davidxl]

lib/ProfileData/InstrProfWriter.cpp

299–300

This guard is not right -- the function may be referenced by an indirect call target from another emitted function. In fact since text format is mainly used for debugging, I don't see much point honoring sparse flag here.

[davidxl]

Discard the first part of the comment -- that scenario can not exist.

David

[davidxl]

The text dump issue is minor. LGTM

docs/CommandGuide/llvm-profdata.rst

  sample-based and instrumentation-based profile. When this option is used
  the profile will be dumped in the text format that is parsable by the profile
  reader.
 
  .. option:: -gcc
 
  Emit the profile using GCC's gcov format (Not yet supported).
 
+ .. option:: -sparse[=true|false]
+
+ Do not emit function records with 0 execution count. Can only be used in
+ conjunction with -instr. Defaults to true.
+
 EXAMPLES
 ^^^^^^^^
 Basic Usage
 +++++++++++
 Merge three profiles:
 
 ::
 

include/llvm/ProfileData/InstrProfWriter.h

 class ProfOStream;
 class InstrProfRecordWriterTrait;
 
 class InstrProfWriter {
 public:
   typedef SmallDenseMap<uint64_t, InstrProfRecord, 1> ProfilingData;
 
 private:
+  bool Sparse;
   StringMap<ProfilingData> FunctionData;
   uint64_t MaxFunctionCount;
   // Use raw pointer here for the incomplete type object.
   InstrProfRecordWriterTrait *InfoObj;
 
 public:
-  InstrProfWriter();
+  InstrProfWriter(bool Sparse = true);
   ~InstrProfWriter();
 
   /// Add function counts for the given function. If there are already counts
   /// for this function and the hash and number of counts match, each counter is
   /// summed. Optionally scale counts by \p Weight.
   std::error_code addRecord(InstrProfRecord &&I, uint64_t Weight = 1);
   /// Write the profile to \c OS
   void write(raw_fd_ostream &OS);
   /// Write the profile in text format to \c OS
   void writeText(raw_fd_ostream &OS);
   /// Write \c Record in text format to \c OS
   static void writeRecordInText(const InstrProfRecord &Record,
                                 InstrProfSymtab &Symtab, raw_fd_ostream &OS);
   /// Write the profile, returning the raw data. For testing.
   std::unique_ptr<MemoryBuffer> writeBuffer();
 
   // Internal interface for testing purpose only.
   void setValueProfDataEndianness(support::endianness Endianness);
+  void setOutputSparse(bool Sparse);
 
 private:
+  bool shouldEncodeData(const ProfilingData &PD);
   void writeImpl(ProfOStream &OS);
 };
 
 } // end namespace llvm
 
 #endif

lib/ProfileData/InstrProfWriter.cpp

       uint32_t S = VDataPtr->getSize();
       VDataPtr->swapBytesFromHost(ValueProfDataEndianness);
       Out.write((const char *)VDataPtr.get(), S);
     }
   }
 };
 }
 
-InstrProfWriter::InstrProfWriter()
-    : FunctionData(), MaxFunctionCount(0),
+InstrProfWriter::InstrProfWriter(bool Sparse)
+    : Sparse(Sparse), FunctionData(), MaxFunctionCount(0),
       InfoObj(new InstrProfRecordWriterTrait()) {}
 
 InstrProfWriter::~InstrProfWriter() { delete InfoObj; }
 
 // Internal interface for testing purpose only.
 void InstrProfWriter::setValueProfDataEndianness(
     support::endianness Endianness) {
   InfoObj->ValueProfDataEndianness = Endianness;
 }
+void InstrProfWriter::setOutputSparse(bool Sparse) {
+  this->Sparse = Sparse;
+}
 
 std::error_code InstrProfWriter::addRecord(InstrProfRecord &&I,
                                            uint64_t Weight) {
   auto &ProfileDataMap = FunctionData[I.Name];
 
   bool NewFunc;
   ProfilingData::iterator Where;
   std::tie(Where, NewFunc) =

   // We keep track of the max function count as we go for simplicity.
   // Update this statistic no matter the result of the merge.
   if (Dest.Counts[0] > MaxFunctionCount)
     MaxFunctionCount = Dest.Counts[0];
 
   return Result;
 }
 
+bool InstrProfWriter::shouldEncodeData(const ProfilingData &PD) {
+  if (!Sparse)
+    return true;
+  for (const auto &Func : PD) {
+    const InstrProfRecord &IPR = Func.second;
+    if (std::any_of(IPR.Counts.begin(), IPR.Counts.end(),
+                    [](uint64_t Count) { return Count > 0; }) ||
+        IPR.getNumValueKinds())
+      return true;
+  }
+  return false;
+}
+
 void InstrProfWriter::writeImpl(ProfOStream &OS) {
   OnDiskChainedHashTableGenerator<InstrProfRecordWriterTrait> Generator;
   // Populate the hash table generator.
   for (const auto &I : FunctionData)
-    Generator.insert(I.getKey(), &I.getValue());
+    if (shouldEncodeData(I.getValue()))
+      Generator.insert(I.getKey(), &I.getValue());
   // Write the header.
   IndexedInstrProf::Header Header;
   Header.Magic = IndexedInstrProf::Magic;
   Header.Version = IndexedInstrProf::ProfVersion::CurrentVersion;
   Header.MaxFunctionCount = MaxFunctionCount;
   Header.HashType = static_cast<uint64_t>(IndexedInstrProf::HashType);
   Header.HashOffset = 0;
   int N = sizeof(IndexedInstrProf::Header) / sizeof(uint64_t);

   }
 
   OS << "\n";
 }
 
 void InstrProfWriter::writeText(raw_fd_ostream &OS) {
   InstrProfSymtab Symtab;
   for (const auto &I : FunctionData)
-    Symtab.addFuncName(I.getKey());
+    if (shouldEncodeData(I.getValue()))
+      Symtab.addFuncName(I.getKey());
   Symtab.finalizeSymtab();
 
   for (const auto &I : FunctionData)
-    for (const auto &Func : I.getValue())
-      writeRecordInText(Func.second, Symtab, OS);
+    if (shouldEncodeData(I.getValue()))
+      for (const auto &Func : I.getValue())
+        writeRecordInText(Func.second, Symtab, OS);
 }

test/tools/llvm-profdata/general.proftext

-
-
 # RUN: llvm-profdata merge %s -o %t.profdata
 
+# RUN: llvm-profdata merge -sparse=false %s -o %t.profdata.dense
+
 # RUN: llvm-profdata show %t.profdata --function function_count_only --counts | FileCheck %s -check-prefix=FUNC_COUNT_ONLY
 function_count_only
 0
 1
 97531
 # FUNC_COUNT_ONLY:      Hash: 0x{{0+$}}
 # FUNC_COUNT_ONLY-NEXT: Counters: 1
 # FUNC_COUNT_ONLY-NEXT: Function count: 97531
 # FUNC_COUNT_ONLY-NEXT: Block counts: []
 
-# RUN: llvm-profdata show %t.profdata --function "name with spaces" --counts | FileCheck %s -check-prefix=SPACES
+# RUN: llvm-profdata show %t.profdata.dense --function "name with spaces" --counts | FileCheck %s -check-prefix=SPACES
+# RUN: llvm-profdata show %t.profdata --function "name with spaces" --counts | FileCheck %s --check-prefix=SPARSE_SPACES
 name with spaces
 1024
 2
 0
 0
 # SPACES:      Hash: 0x{{0+}}400
 # SPACES-NEXT: Counters: 2
 # SPACES-NEXT: Function count: 0
 # SPACES-NEXT: Block counts: [0]
+# SPARSE_SPACES-NOT: Function count: 0
 
 # RUN: llvm-profdata show %t.profdata --function large_numbers --counts | FileCheck %s -check-prefix=LARGENUM
 large_numbers
 4611686018427387903
 6
 2305843009213693952
 1152921504606846976
 576460752303423488
 288230376151711744
 144115188075855872
 72057594037927936
 # LARGENUM:      Hash: 0x3fffffffffffffff
 # LARGENUM-NEXT: Counters: 6
 # LARGENUM-NEXT: Function count: 2305843009213693952
 # LARGENUM-NEXT: Block counts: [1152921504606846976, 576460752303423488, 288230376151711744, 144115188075855872, 72057594037927936]
 
-# RUN: llvm-profdata show %t.profdata --function hex_hash | FileCheck %s -check-prefix=HEX-HASH
+# RUN: llvm-profdata show %t.profdata.dense --function hex_hash | FileCheck %s -check-prefix=HEX-HASH
 hex_hash
 0x1234
 1
 0
 # HEX-HASH: Hash: 0x0000000000001234
 # HEX-HASH-NEXT: Counters: 1
 
 # RUN: llvm-profdata show %t.profdata --function NOSUCHFUNC | FileCheck %s -check-prefix=NOSUCHFUNC
 # NOSUCHFUNC-NOT: Counters:
 # NOSUCHFUNC: Functions shown: 0
 
 # RUN: llvm-profdata show %t.profdata --function _ | FileCheck %s -check-prefix=SOMEFUNCS
+# RUN: llvm-profdata show %t.profdata.dense --function _ | FileCheck %s -check-prefix=SOMEFUNCS_DENSE
 # SOMEFUNCS: Counters:
 # SOMEFUNCS: function_count_only:
 # SOMEFUNCS: large_numbers:
-# SOMEFUNCS: Functions shown: 3
+# SOMEFUNCS: Functions shown: 2
+# SOMEFUNCS_DENSE: Functions shown: 3
 
-# RUN: llvm-profdata show %t.profdata | FileCheck %s -check-prefix=SUMMARY
+# RUN: llvm-profdata show %t.profdata.dense | FileCheck %s -check-prefix=SUMMARY
 # SUMMARY-NOT: Counters:
 # SUMMARY-NOT: Functions shown:
 # SUMMARY: Total functions: 4
 # SUMMARY: Maximum function count: 2305843009213693952
 # SUMMARY: Maximum internal block count: 1152921504606846976
 
-# RUN: llvm-profdata show --detailed-summary %t.profdata | FileCheck %s -check-prefix=DETAILED-SUMMARY
+# RUN: llvm-profdata show --detailed-summary %t.profdata.dense | FileCheck %s -check-prefix=DETAILED-SUMMARY
 # DETAILED-SUMMARY: Detailed summary:
 # DETAILED-SUMMARY: Total number of blocks: 10
 # DETAILED-SUMMARY: Total count: 4539628424389557499
 # DETAILED-SUMMARY: 3 blocks with count >= 576460752303423488 account for 80 percentage of the total counts.
 # DETAILED-SUMMARY: 4 blocks with count >= 288230376151711744 account for 90 percentage of the total counts.
 # DETAILED-SUMMARY: 4 blocks with count >= 288230376151711744 account for 95 percentage of the total counts.
 # DETAILED-SUMMARY: 6 blocks with count >= 72057594037927936 account for 99 percentage of the total counts.
 # DETAILED-SUMMARY: 6 blocks with count >= 72057594037927936 account for 99.9 percentage of the total counts.

test/tools/llvm-profdata/weight-instr.test

 Tests for weighted merge of instrumented profiles.
 
 1- Merge the foo and bar profiles with unity weight and verify the combined output
-RUN: llvm-profdata merge -instr -weighted-input=1,%p/Inputs/weight-instr-bar.profdata -weighted-input=1,%p/Inputs/weight-instr-foo.profdata -o %t
+RUN: llvm-profdata merge -sparse=false -instr -weighted-input=1,%p/Inputs/weight-instr-bar.profdata -weighted-input=1,%p/Inputs/weight-instr-foo.profdata -o %t
 RUN: llvm-profdata show -instr -all-functions %t | FileCheck %s -check-prefix=1X_1X_WEIGHT
-RUN: llvm-profdata merge -instr -weighted-input=1,%p/Inputs/weight-instr-bar.profdata %p/Inputs/weight-instr-foo.profdata -o %t
+RUN: llvm-profdata merge -sparse=false -instr -weighted-input=1,%p/Inputs/weight-instr-bar.profdata %p/Inputs/weight-instr-foo.profdata -o %t
 RUN: llvm-profdata show -instr -all-functions %t | FileCheck %s -check-prefix=1X_1X_WEIGHT
 1X_1X_WEIGHT: Counters:
 1X_1X_WEIGHT-NEXT:   usage:
 1X_1X_WEIGHT-NEXT:     Hash: 0x0000000000000000
 1X_1X_WEIGHT-NEXT:     Counters: 1
 1X_1X_WEIGHT-NEXT:     Function count: 0
 1X_1X_WEIGHT-NEXT:   foo:
 1X_1X_WEIGHT-NEXT:     Hash: 0x000000000000028a
 1X_1X_WEIGHT-NEXT:     Counters: 3
 1X_1X_WEIGHT-NEXT:     Function count: 866988873
 1X_1X_WEIGHT-NEXT:   bar:
 1X_1X_WEIGHT-NEXT:     Hash: 0x000000000000028a
 1X_1X_WEIGHT-NEXT:     Counters: 3
 1X_1X_WEIGHT-NEXT:     Function count: 866988873
 1X_1X_WEIGHT-NEXT:   main:
 1X_1X_WEIGHT-NEXT:     Hash: 0x7d31c47ea98f8248
 1X_1X_WEIGHT-NEXT:     Counters: 60
 1X_1X_WEIGHT-NEXT:     Function count: 2
 1X_1X_WEIGHT-NEXT: Functions shown: 4
 1X_1X_WEIGHT-NEXT: Total functions: 4
 1X_1X_WEIGHT-NEXT: Maximum function count: 866988873
 1X_1X_WEIGHT-NEXT: Maximum internal block count: 267914296
 
 2- Merge the foo and bar profiles with weight 3x and 5x respectively and verify the combined output
-RUN: llvm-profdata merge -instr -weighted-input=3,%p/Inputs/weight-instr-bar.profdata -weighted-input=5,%p/Inputs/weight-instr-foo.profdata -o %t
+RUN: llvm-profdata merge -sparse=false -instr -weighted-input=3,%p/Inputs/weight-instr-bar.profdata -weighted-input=5,%p/Inputs/weight-instr-foo.profdata -o %t
 RUN: llvm-profdata show -instr -all-functions %t | FileCheck %s -check-prefix=3X_5X_WEIGHT
 3X_5X_WEIGHT: Counters:
 3X_5X_WEIGHT-NEXT:   usage:
 3X_5X_WEIGHT-NEXT:     Hash: 0x0000000000000000
 3X_5X_WEIGHT-NEXT:     Counters: 1
 3X_5X_WEIGHT-NEXT:     Function count: 0
 3X_5X_WEIGHT-NEXT:   foo:
 3X_5X_WEIGHT-NEXT:     Hash: 0x000000000000028a

tools/llvm-profdata/llvm-profdata.cpp

   WeightedFile() {}
 
   WeightedFile(StringRef F, uint64_t W) : Filename{F}, Weight{W} {}
 };
 typedef SmallVector<WeightedFile, 5> WeightedFileVector;
 
 static void mergeInstrProfile(const WeightedFileVector &Inputs,
                               StringRef OutputFilename,
-                              ProfileFormat OutputFormat) {
+                              ProfileFormat OutputFormat, bool OutputSparse) {
   if (OutputFilename.compare("-") == 0)
     exitWithError("Cannot write indexed profdata format to stdout.");
 
   if (OutputFormat != PF_Binary && OutputFormat != PF_Text)
     exitWithError("Unknown format is specified.");
 
   std::error_code EC;
   raw_fd_ostream Output(OutputFilename.data(), EC, sys::fs::F_None);
   if (EC)
     exitWithErrorCode(EC, OutputFilename);
 
-  InstrProfWriter Writer;
+  InstrProfWriter Writer(OutputSparse);
   SmallSet<std::error_code, 4> WriterErrorCodes;
   for (const auto &Input : Inputs) {
     auto ReaderOrErr = InstrProfReader::create(Input.Filename);
     if (std::error_code ec = ReaderOrErr.getError())
       exitWithErrorCode(ec, Input.Filename);
 
     auto Reader = std::move(ReaderOrErr.get());
     for (auto &I : *Reader) {

   cl::opt<ProfileFormat> OutputFormat(
       cl::desc("Format of output profile"), cl::init(PF_Binary),
       cl::values(clEnumValN(PF_Binary, "binary", "Binary encoding (default)"),
                  clEnumValN(PF_Text, "text", "Text encoding"),
                  clEnumValN(PF_GCC, "gcc",
                             "GCC encoding (only meaningful for -sample)"),
                  clEnumValEnd));
 
+  cl::opt<bool> OutputSparse("sparse", cl::init(true),
+      cl::desc("Generate a sparse profile (only meaningful for -instr)"));
+
   cl::ParseCommandLineOptions(argc, argv, "LLVM profile data merger\n");
 
   if (InputFilenames.empty() && WeightedInputFilenames.empty())
     exitWithError("No input files specified. See " +
                   sys::path::filename(argv[0]) + " -help");
 
   WeightedFileVector WeightedInputs;
   for (StringRef Filename : InputFilenames)
     WeightedInputs.push_back(WeightedFile(Filename, 1));
   for (StringRef WeightedFilename : WeightedInputFilenames)
     WeightedInputs.push_back(parseWeightedFile(WeightedFilename));
 
   if (ProfileKind == instr)
-    mergeInstrProfile(WeightedInputs, OutputFilename, OutputFormat);
+    mergeInstrProfile(WeightedInputs, OutputFilename, OutputFormat,
+                      OutputSparse);
   else
     mergeSampleProfile(WeightedInputs, OutputFilename, OutputFormat);
 
   return 0;
 }
 
 static int showInstrProfile(std::string Filename, bool ShowCounts,
                             bool ShowIndirectCallTargets,

unittests/ProfileData/CoverageMappingTest.cpp

struct CoverageMappingTest : ::testing::Test {
 
   InstrProfWriter ProfileWriter;
   std::unique_ptr<IndexedInstrProfReader> ProfileReader;
 
   std::unique_ptr<CoverageMapping> LoadedCoverage;
 
   void SetUp() override {
     NextFile = 0;
+    ProfileWriter.setOutputSparse(false);
   }
 
   unsigned getFile(StringRef Name) {
     auto R = Files.find(Name);
     if (R != Files.end())
       return R->second;
     Files[Name] = NextFile;
     return NextFile++;
for (const auto &E : Files)
       Filenames.push_back(E.getKey());
     OneFunctionCoverageReader CovReader(FuncName, Hash, Filenames, OutputCMRs);
     auto CoverageOrErr = CoverageMapping::load(CovReader, *ProfileReader);
     ASSERT_TRUE(NoError(CoverageOrErr.getError()));
     LoadedCoverage = std::move(CoverageOrErr.get());
   }
 };
 
-TEST_F(CoverageMappingTest, basic_write_read) {
+struct MaybeSparseCoverageMappingTest
+    : public CoverageMappingTest,
+      public ::testing::WithParamInterface<bool> {
+  void SetUp() {
+    CoverageMappingTest::SetUp();
+    ProfileWriter.setOutputSparse(GetParam());
+  }
+};
+
+TEST_P(MaybeSparseCoverageMappingTest, basic_write_read) {
   addCMR(Counter::getCounter(0), "foo", 1, 1, 1, 1);
   addCMR(Counter::getCounter(1), "foo", 2, 1, 2, 2);
   addCMR(Counter::getZero(),     "foo", 3, 1, 3, 4);
   addCMR(Counter::getCounter(2), "foo", 4, 1, 4, 8);
   addCMR(Counter::getCounter(3), "bar", 1, 2, 3, 4);
   std::string Coverage = writeCoverageRegions();
   readCoverageRegions(Coverage);
 
   size_t N = makeArrayRef(InputCMRs).size();
   ASSERT_EQ(N, OutputCMRs.size());
   for (size_t I = 0; I < N; ++I) {
     ASSERT_EQ(InputCMRs[I].Count,      OutputCMRs[I].Count);
     ASSERT_EQ(InputCMRs[I].FileID,     OutputCMRs[I].FileID);
     ASSERT_EQ(InputCMRs[I].startLoc(), OutputCMRs[I].startLoc());
     ASSERT_EQ(InputCMRs[I].endLoc(),   OutputCMRs[I].endLoc());
     ASSERT_EQ(InputCMRs[I].Kind,       OutputCMRs[I].Kind);
   }
 }
 
-TEST_F(CoverageMappingTest, expansion_gets_first_counter) {
+TEST_P(MaybeSparseCoverageMappingTest, expansion_gets_first_counter) {
   addCMR(Counter::getCounter(1), "foo", 10, 1, 10, 2);
   // This starts earlier in "foo", so the expansion should get its counter.
   addCMR(Counter::getCounter(2), "foo", 1, 1, 20, 1);
   addExpansionCMR("bar", "foo", 3, 3, 3, 3);
   std::string Coverage = writeCoverageRegions();
   readCoverageRegions(Coverage);
 
   ASSERT_EQ(CounterMappingRegion::ExpansionRegion, OutputCMRs[2].Kind);
   ASSERT_EQ(Counter::getCounter(2), OutputCMRs[2].Count);
   ASSERT_EQ(3U, OutputCMRs[2].LineStart);
 }
 
-TEST_F(CoverageMappingTest, basic_coverage_iteration) {
+TEST_P(MaybeSparseCoverageMappingTest, basic_coverage_iteration) {
   InstrProfRecord Record("func", 0x1234, {30, 20, 10, 0});
   ProfileWriter.addRecord(std::move(Record));
   readProfCounts();
 
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
   addCMR(Counter::getCounter(1), "file1", 1, 1, 4, 7);
   addCMR(Counter::getCounter(2), "file1", 5, 8, 9, 1);
   addCMR(Counter::getCounter(3), "file1", 10, 10, 11, 11);
   loadCoverageMapping("func", 0x1234);
 
   CoverageData Data = LoadedCoverage->getCoverageForFile("file1");
   std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
   ASSERT_EQ(7U, Segments.size());
   ASSERT_EQ(CoverageSegment(1, 1, 20, true),  Segments[0]);
   ASSERT_EQ(CoverageSegment(4, 7, 30, false), Segments[1]);
   ASSERT_EQ(CoverageSegment(5, 8, 10, true),  Segments[2]);
   ASSERT_EQ(CoverageSegment(9, 1, 30, false), Segments[3]);
   ASSERT_EQ(CoverageSegment(9, 9, false),     Segments[4]);
   ASSERT_EQ(CoverageSegment(10, 10, 0, true), Segments[5]);
   ASSERT_EQ(CoverageSegment(11, 11, false),   Segments[6]);
 }
 
-TEST_F(CoverageMappingTest, uncovered_function) {
+TEST_P(MaybeSparseCoverageMappingTest, uncovered_function) {
   readProfCounts();
 
   addCMR(Counter::getZero(), "file1", 1, 2, 3, 4);
   loadCoverageMapping("func", 0x1234);
 
   CoverageData Data = LoadedCoverage->getCoverageForFile("file1");
   std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
   ASSERT_EQ(2U, Segments.size());
   ASSERT_EQ(CoverageSegment(1, 2, 0, true), Segments[0]);
   ASSERT_EQ(CoverageSegment(3, 4, false),   Segments[1]);
 }
 
-TEST_F(CoverageMappingTest, uncovered_function_with_mapping) {
+TEST_P(MaybeSparseCoverageMappingTest, uncovered_function_with_mapping) {
   readProfCounts();
 
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
   addCMR(Counter::getCounter(1), "file1", 1, 1, 4, 7);
   loadCoverageMapping("func", 0x1234);
 
   CoverageData Data = LoadedCoverage->getCoverageForFile("file1");
   std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
   ASSERT_EQ(3U, Segments.size());
   ASSERT_EQ(CoverageSegment(1, 1, 0, true),  Segments[0]);
   ASSERT_EQ(CoverageSegment(4, 7, 0, false), Segments[1]);
   ASSERT_EQ(CoverageSegment(9, 9, false),    Segments[2]);
 }
 
-TEST_F(CoverageMappingTest, combine_regions) {
+TEST_P(MaybeSparseCoverageMappingTest, combine_regions) {
   InstrProfRecord Record("func", 0x1234, {10, 20, 30});
   ProfileWriter.addRecord(std::move(Record));
   readProfCounts();
 
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
   addCMR(Counter::getCounter(1), "file1", 3, 3, 4, 4);
   addCMR(Counter::getCounter(2), "file1", 3, 3, 4, 4);
   loadCoverageMapping("func", 0x1234);
 
   CoverageData Data = LoadedCoverage->getCoverageForFile("file1");
   std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
   ASSERT_EQ(4U, Segments.size());
   ASSERT_EQ(CoverageSegment(1, 1, 10, true), Segments[0]);
   ASSERT_EQ(CoverageSegment(3, 3, 50, true), Segments[1]);
   ASSERT_EQ(CoverageSegment(4, 4, 10, false), Segments[2]);
   ASSERT_EQ(CoverageSegment(9, 9, false), Segments[3]);
 }
 
-TEST_F(CoverageMappingTest, dont_combine_expansions) {
-  InstrProfRecord Record("func", 0x1234, {10, 20});
-  ProfileWriter.addRecord(std::move(Record));
+TEST_P(MaybeSparseCoverageMappingTest, dont_combine_expansions) {
+  InstrProfRecord Record1("func", 0x1234, {10, 20});
+  InstrProfRecord Record2("func", 0x1234, {0, 0});
+  ProfileWriter.addRecord(std::move(Record1));
+  ProfileWriter.addRecord(std::move(Record2));
   readProfCounts();
 
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
   addCMR(Counter::getCounter(1), "file1", 3, 3, 4, 4);
   addCMR(Counter::getCounter(1), "include1", 6, 6, 7, 7);
   addExpansionCMR("file1", "include1", 3, 3, 4, 4);
   loadCoverageMapping("func", 0x1234);
 
   CoverageData Data = LoadedCoverage->getCoverageForFile("file1");
   std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
   ASSERT_EQ(4U, Segments.size());
   ASSERT_EQ(CoverageSegment(1, 1, 10, true), Segments[0]);
   ASSERT_EQ(CoverageSegment(3, 3, 20, true), Segments[1]);
   ASSERT_EQ(CoverageSegment(4, 4, 10, false), Segments[2]);
   ASSERT_EQ(CoverageSegment(9, 9, false), Segments[3]);
 }
 
-TEST_F(CoverageMappingTest, strip_filename_prefix) {
-  InstrProfRecord Record("file1:func", 0x1234, {10});
+TEST_P(MaybeSparseCoverageMappingTest, strip_filename_prefix) {
+  InstrProfRecord Record("file1:func", 0x1234, {0});
   ProfileWriter.addRecord(std::move(Record));
   readProfCounts();
 
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
   loadCoverageMapping("file1:func", 0x1234);
 
   std::vector<std::string> Names;
   for (const auto &Func : LoadedCoverage->getCoveredFunctions())
     Names.push_back(Func.Name);
   ASSERT_EQ(1U, Names.size());
   ASSERT_EQ("func", Names[0]);
 }
 
+INSTANTIATE_TEST_CASE_P(MaybeSparse, MaybeSparseCoverageMappingTest,
+                        ::testing::Bool());
+
 } // end anonymous namespace

unittests/ProfileData/InstrProfTest.cpp

 }
 
 namespace {
 
 struct InstrProfTest : ::testing::Test {
   InstrProfWriter Writer;
   std::unique_ptr<IndexedInstrProfReader> Reader;
 
+  void SetUp() { Writer.setOutputSparse(false); }
+
   void readProfile(std::unique_ptr<MemoryBuffer> Profile) {
     auto ReaderOrErr = IndexedInstrProfReader::create(std::move(Profile));
     ASSERT_TRUE(NoError(ReaderOrErr.getError()));
     Reader = std::move(ReaderOrErr.get());
   }
 };
 
-TEST_F(InstrProfTest, write_and_read_empty_profile) {
+struct SparseInstrProfTest : public InstrProfTest {
+  void SetUp() { Writer.setOutputSparse(true); }
+};
+
+struct MaybeSparseInstrProfTest : public InstrProfTest,
+                                  public ::testing::WithParamInterface<bool> {
+  void SetUp() {
+    Writer.setOutputSparse(GetParam());
+  }
+};
+
+TEST_P(MaybeSparseInstrProfTest, write_and_read_empty_profile) {
   auto Profile = Writer.writeBuffer();
   readProfile(std::move(Profile));
   ASSERT_TRUE(Reader->begin() == Reader->end());
 }
 
-TEST_F(InstrProfTest, write_and_read_one_function) {
+TEST_P(MaybeSparseInstrProfTest, write_and_read_one_function) {
   InstrProfRecord Record("foo", 0x1234, {1, 2, 3, 4});
   Writer.addRecord(std::move(Record));
   auto Profile = Writer.writeBuffer();
   readProfile(std::move(Profile));
 
   auto I = Reader->begin(), E = Reader->end();
   ASSERT_TRUE(I != E);
   ASSERT_EQ(StringRef("foo"), I->Name);
   ASSERT_EQ(0x1234U, I->Hash);
   ASSERT_EQ(4U, I->Counts.size());
   ASSERT_EQ(1U, I->Counts[0]);
   ASSERT_EQ(2U, I->Counts[1]);
   ASSERT_EQ(3U, I->Counts[2]);
   ASSERT_EQ(4U, I->Counts[3]);
   ASSERT_TRUE(++I == E);
 }
 
-TEST_F(InstrProfTest, get_instr_prof_record) {
+TEST_P(MaybeSparseInstrProfTest, get_instr_prof_record) {
   InstrProfRecord Record1("foo", 0x1234, {1, 2});
   InstrProfRecord Record2("foo", 0x1235, {3, 4});
   Writer.addRecord(std::move(Record1));
   Writer.addRecord(std::move(Record2));
   auto Profile = Writer.writeBuffer();
   readProfile(std::move(Profile));
 
   ErrorOr<InstrProfRecord> R = Reader->getInstrProfRecord("foo", 0x1234);
TEST_P(MaybeSparseInstrProfTest, get_instr_prof_record) {
 
   R = Reader->getInstrProfRecord("foo", 0x5678);
   ASSERT_TRUE(ErrorEquals(instrprof_error::hash_mismatch, R.getError()));
 
   R = Reader->getInstrProfRecord("bar", 0x1234);
   ASSERT_TRUE(ErrorEquals(instrprof_error::unknown_function, R.getError()));
 }
 
-TEST_F(InstrProfTest, get_function_counts) {
+TEST_P(MaybeSparseInstrProfTest, get_function_counts) {
   InstrProfRecord Record1("foo", 0x1234, {1, 2});
   InstrProfRecord Record2("foo", 0x1235, {3, 4});
   Writer.addRecord(std::move(Record1));
   Writer.addRecord(std::move(Record2));
   auto Profile = Writer.writeBuffer();
   readProfile(std::move(Profile));
 
   std::vector<uint64_t> Counts;
TEST_P(MaybeSparseInstrProfTest, get_function_counts) {
   std::error_code EC;
   EC = Reader->getFunctionCounts("foo", 0x5678, Counts);
   ASSERT_TRUE(ErrorEquals(instrprof_error::hash_mismatch, EC));
 
   EC = Reader->getFunctionCounts("bar", 0x1234, Counts);
   ASSERT_TRUE(ErrorEquals(instrprof_error::unknown_function, EC));
 }
 
-TEST_F(InstrProfTest, get_icall_data_read_write) {
+TEST_P(MaybeSparseInstrProfTest, get_icall_data_read_write) {
   InstrProfRecord Record1("caller", 0x1234, {1, 2});
   InstrProfRecord Record2("callee1", 0x1235, {3, 4});
   InstrProfRecord Record3("callee2", 0x1235, {3, 4});
   InstrProfRecord Record4("callee3", 0x1235, {3, 4});
 
   // 4 value sites.
   Record1.reserveSites(IPVK_IndirectCallTarget, 4);
   InstrProfValueData VD0[] = {{(uint64_t) "callee1", 1},
TEST_P(MaybeSparseInstrProfTest, get_icall_data_read_write) {
   ASSERT_EQ(2U, VD[1].Count);
   ASSERT_EQ(1U, VD[2].Count);
 
   ASSERT_EQ(StringRef((const char *)VD[0].Value, 7), StringRef("callee3"));
   ASSERT_EQ(StringRef((const char *)VD[1].Value, 7), StringRef("callee2"));
   ASSERT_EQ(StringRef((const char *)VD[2].Value, 7), StringRef("callee1"));
 }
 
-TEST_F(InstrProfTest, get_icall_data_read_write_with_weight) {
+TEST_P(MaybeSparseInstrProfTest, get_icall_data_read_write_with_weight) {
   InstrProfRecord Record1("caller", 0x1234, {1, 2});
   InstrProfRecord Record2("callee1", 0x1235, {3, 4});
   InstrProfRecord Record3("callee2", 0x1235, {3, 4});
   InstrProfRecord Record4("callee3", 0x1235, {3, 4});
 
   // 4 value sites.
   Record1.reserveSites(IPVK_IndirectCallTarget, 4);
   InstrProfValueData VD0[] = {{(uint64_t) "callee1", 1},
TEST_P(MaybeSparseInstrProfTest, get_icall_data_read_write_with_weight) {
   ASSERT_EQ(20U, VD[1].Count);
   ASSERT_EQ(10U, VD[2].Count);
 
   ASSERT_EQ(StringRef((const char *)VD[0].Value, 7), StringRef("callee3"));
   ASSERT_EQ(StringRef((const char *)VD[1].Value, 7), StringRef("callee2"));
   ASSERT_EQ(StringRef((const char *)VD[2].Value, 7), StringRef("callee1"));
 }
 
-TEST_F(InstrProfTest, get_icall_data_read_write_big_endian) {
+TEST_P(MaybeSparseInstrProfTest, get_icall_data_read_write_big_endian) {
   InstrProfRecord Record1("caller", 0x1234, {1, 2});
   InstrProfRecord Record2("callee1", 0x1235, {3, 4});
   InstrProfRecord Record3("callee2", 0x1235, {3, 4});
   InstrProfRecord Record4("callee3", 0x1235, {3, 4});
 
   // 4 value sites.
   Record1.reserveSites(IPVK_IndirectCallTarget, 4);
   InstrProfValueData VD0[] = {{(uint64_t) "callee1", 1},
TEST_P(MaybeSparseInstrProfTest, get_icall_data_read_write_big_endian) {
   ASSERT_EQ(StringRef((const char *)VD[0].Value, 7), StringRef("callee3"));
   ASSERT_EQ(StringRef((const char *)VD[1].Value, 7), StringRef("callee2"));
   ASSERT_EQ(StringRef((const char *)VD[2].Value, 7), StringRef("callee1"));
 
   // Restore little endian default:
   Writer.setValueProfDataEndianness(support::little);
 }
 
-TEST_F(InstrProfTest, get_icall_data_merge1) {
+TEST_P(MaybeSparseInstrProfTest, get_icall_data_merge1) {
   static const char caller[] = "caller";
   static const char callee1[] = "callee1";
   static const char callee2[] = "callee2";
   static const char callee3[] = "callee3";
   static const char callee4[] = "callee4";
 
   InstrProfRecord Record11(caller, 0x1234, {1, 2});
   InstrProfRecord Record12(caller, 0x1234, {1, 2});
TEST_P(MaybeSparseInstrProfTest, get_icall_data_merge1) {
   ASSERT_EQ(StringRef((const char *)VD_4[0].Value, 7), StringRef("callee3"));
   ASSERT_EQ(6U, VD_4[0].Count);
   ASSERT_EQ(StringRef((const char *)VD_4[1].Value, 7), StringRef("callee2"));
   ASSERT_EQ(4U, VD_4[1].Count);
   ASSERT_EQ(StringRef((const char *)VD_4[2].Value, 7), StringRef("callee1"));
   ASSERT_EQ(2U, VD_4[2].Count);
 }
 
-TEST_F(InstrProfTest, get_icall_data_merge1_saturation) {
+TEST_P(MaybeSparseInstrProfTest, get_icall_data_merge1_saturation) {
   static const char bar[] = "bar";
 
   const uint64_t Max = std::numeric_limits<uint64_t>::max();
 
   InstrProfRecord Record1("foo", 0x1234, {1});
   auto Result1 = Writer.addRecord(std::move(Record1));
   ASSERT_EQ(Result1, instrprof_error::success);
 
std::unique_ptr<InstrProfValueData[]> VD =
       ReadRecord2.get().getValueForSite(IPVK_IndirectCallTarget, 0);
   ASSERT_EQ(StringRef("bar"), StringRef((const char *)VD[0].Value, 3));
   ASSERT_EQ(Max, VD[0].Count);
 }
 
 // This test tests that when there are too many values
 // for a given site, the merged results are properly
 // truncated.
-TEST_F(InstrProfTest, get_icall_data_merge_site_trunc) {
+TEST_P(MaybeSparseInstrProfTest, get_icall_data_merge_site_trunc) {
   static const char caller[] = "caller";
 
   InstrProfRecord Record11(caller, 0x1234, {1, 2});
   InstrProfRecord Record12(caller, 0x1234, {1, 2});
 
   // 2 value sites.
   Record11.reserveSites(IPVK_IndirectCallTarget, 2);
   InstrProfValueData VD0[255];

 ValueProfNode Site4Values[2] = {{{uint64_t("callee2"), 1800}, &Site4Values[1]},
                                 {{uint64_t("callee3"), 2000}, nullptr}};
 
 static ValueProfNode *ValueProfNodes[5] = {&Site1Values[0], &Site2Values[0],
                                            &Site3Values[0], &Site4Values[0],
                                            nullptr};
 
 static uint16_t NumValueSites[IPVK_Last + 1] = {5};
-TEST_F(InstrProfTest, runtime_value_prof_data_read_write) {
+TEST_P(MaybeSparseInstrProfTest, runtime_value_prof_data_read_write) {
   ValueProfRuntimeRecord RTRecord;
   initializeValueProfRuntimeRecord(&RTRecord, &NumValueSites[0],
                                    &ValueProfNodes[0]);
 
   ValueProfData *VPData = serializeValueProfDataFromRT(&RTRecord, nullptr);
 
   InstrProfRecord Record("caller", 0x1234, {1ULL << 31, 2});
 
TEST_P(MaybeSparseInstrProfTest, runtime_value_prof_data_read_write) {
   ASSERT_EQ(2000U, VD_3[0].Count);
   ASSERT_EQ(StringRef((const char *)VD_3[1].Value, 7), StringRef("callee2"));
   ASSERT_EQ(1800U, VD_3[1].Count);
 
   finalizeValueProfRuntimeRecord(&RTRecord);
   free(VPData);
 }
 
-TEST_F(InstrProfTest, get_max_function_count) {
+TEST_P(MaybeSparseInstrProfTest, get_max_function_count) {
   InstrProfRecord Record1("foo", 0x1234, {1ULL << 31, 2});
   InstrProfRecord Record2("bar", 0, {1ULL << 63});
   InstrProfRecord Record3("baz", 0x5678, {0, 0, 0, 0});
   Writer.addRecord(std::move(Record1));
   Writer.addRecord(std::move(Record2));
   Writer.addRecord(std::move(Record3));
   auto Profile = Writer.writeBuffer();
   readProfile(std::move(Profile));
 
   ASSERT_EQ(1ULL << 63, Reader->getMaximumFunctionCount());
 }
 
-TEST_F(InstrProfTest, get_weighted_function_counts) {
+TEST_P(MaybeSparseInstrProfTest, get_weighted_function_counts) {
   InstrProfRecord Record1("foo", 0x1234, {1, 2});
   InstrProfRecord Record2("foo", 0x1235, {3, 4});
   Writer.addRecord(std::move(Record1), 3);
   Writer.addRecord(std::move(Record2), 5);
   auto Profile = Writer.writeBuffer();
   readProfile(std::move(Profile));
 
   std::vector<uint64_t> Counts;
   ASSERT_TRUE(NoError(Reader->getFunctionCounts("foo", 0x1234, Counts)));
   ASSERT_EQ(2U, Counts.size());
   ASSERT_EQ(3U, Counts[0]);
   ASSERT_EQ(6U, Counts[1]);
 
   ASSERT_TRUE(NoError(Reader->getFunctionCounts("foo", 0x1235, Counts)));
   ASSERT_EQ(2U, Counts.size());
   ASSERT_EQ(15U, Counts[0]);
   ASSERT_EQ(20U, Counts[1]);
 }
 
-TEST_F(InstrProfTest, instr_prof_symtab_test) {
+TEST_P(MaybeSparseInstrProfTest, instr_prof_symtab_test) {
   std::vector<StringRef> FuncNames;
   FuncNames.push_back("func1");
   FuncNames.push_back("func2");
   FuncNames.push_back("func3");
   FuncNames.push_back("bar1");
   FuncNames.push_back("bar2");
   FuncNames.push_back("bar3");
   InstrProfSymtab Symtab;
TEST_P(MaybeSparseInstrProfTest, instr_prof_symtab_test) {
   R = Symtab.getFuncName(IndexedInstrProf::ComputeHash("bar1"));
   ASSERT_EQ(StringRef("bar1"), R);
   R = Symtab.getFuncName(IndexedInstrProf::ComputeHash("bar2"));
   ASSERT_EQ(StringRef("bar2"), R);
   R = Symtab.getFuncName(IndexedInstrProf::ComputeHash("bar3"));
   ASSERT_EQ(StringRef("bar3"), R);
 }
 
-TEST_F(InstrProfTest, instr_prof_symtab_module_test) {
+TEST_P(MaybeSparseInstrProfTest, instr_prof_symtab_module_test) {
   LLVMContext Ctx;
   std::unique_ptr<Module> M = llvm::make_unique<Module>("MyModule.cpp", Ctx);
   FunctionType *FTy = FunctionType::get(Type::getVoidTy(Ctx),
                                         /*isVarArg=*/false);
   Function::Create(FTy, Function::ExternalLinkage, "Gfoo", M.get());
   Function::Create(FTy, Function::ExternalLinkage, "Gblah", M.get());
   Function::Create(FTy, Function::ExternalLinkage, "Gbar", M.get());
   Function::Create(FTy, Function::InternalLinkage, "Ifoo", M.get());
for (unsigned I = 0; I < sizeof(Funcs) / sizeof(*Funcs); I++) {
     std::string PGOName = getPGOFuncName(*F);
     uint64_t Key = IndexedInstrProf::ComputeHash(PGOName);
     ASSERT_EQ(StringRef(PGOName),
               ProfSymtab.getFuncName(Key));
     ASSERT_EQ(StringRef(Funcs[I]), ProfSymtab.getOrigFuncName(Key));
   }
 }
 
-TEST_F(InstrProfTest, instr_prof_symtab_compression_test) {
+TEST_P(MaybeSparseInstrProfTest, instr_prof_symtab_compression_test) {
   std::vector<std::string> FuncNames1;
   std::vector<std::string> FuncNames2;
   for (int I = 0; I < 10 * 1024; I++) {
     std::string str;
     raw_string_ostream OS(str);
     OS << "func_" << I;
     FuncNames1.push_back(OS.str());
     str.clear();
for (int DoCompression = 0; DoCompression < 2; DoCompression++) {
           StringRef R = Symtab.getFuncName(IndexedInstrProf::ComputeHash(N[J]));
           ASSERT_EQ(StringRef(N[J]), R);
         }
       }
     }
   }
 }
 
+TEST_F(SparseInstrProfTest, preserve_no_records) {
+  InstrProfRecord Record1("foo", 0x1234, {0});
+  InstrProfRecord Record2("bar", 0x4321, {0, 0});
+  InstrProfRecord Record3("bar", 0x4321, {0, 0, 0});
+
+  Writer.addRecord(std::move(Record1));
+  Writer.addRecord(std::move(Record2));
+  Writer.addRecord(std::move(Record3));
+  auto Profile = Writer.writeBuffer();
+  readProfile(std::move(Profile));
+
+  auto I = Reader->begin(), E = Reader->end();
+  ASSERT_TRUE(I == E);
+}
+
+INSTANTIATE_TEST_CASE_P(MaybeSparse, MaybeSparseInstrProfTest,
+                        ::testing::Bool());
+
 } // end anonymous namespace