[llvm-profdata] Add intersect/exclude subcommands to aid differential code coverage analysis.

[dokyungs]

Summary

[llvm-profdata] Add intersect/exclude subcommands to aid differential code coverage analysis.

This patch adds llvm-profdata [intersect|exclude] subcommands to help with differential code coverage analysis.

1. llvm-profdata intersect <base profdata> <test profdata> -o <output filename>
   
   takes two profile data as input, and outputs their intersection as a file on a given path.

2. llvm-profdata exclude <base profdata> <test profdata> -o <output filename>
   
   takes two profile data as input (base and test profdata, respectively), reduces the the base profdata such that it excludes any data found in the test profdata, and outputs the resulting profile data as a file on a given path.

These commands can be useful when comparing two distinct code coverage data obtained from different sets of test cases. With these commands we can more easily identify code regions that are (i) commonly covered by different sets of test cases via llvm-profdata intersect, and (ii) only covered by certain set of test cases via llvm-profdata exclude.

[dokyungs]

Exit on errors, rename function names, and write comments.

[morehouse]

Thanks, DK, this looks like approximately what we want.

@vsk, @wmi, @davidxl: Would you be willing to take this patch once we clean it up? The exclude operation is particularly useful for comparing coverage reports between fuzzing engines, or for checking new code coverage reached by a test case.

llvm/lib/ProfileData/InstrProf.cpp

653

It seems that we're adding all J's to ValueData, even if they don't intersect with existing values in ValueData. Is this what we really want?

751

This is nearly identical to mergeValueProfData. Can we reuse some code?

And same for uniqueValueProfData.

llvm/tools/llvm-profdata/llvm-profdata.cpp

1155

This is nearly identical to intersect_main. Can we reuse some code?

[vsk]

I haven't had a chance to look at this patch yet, but have no objection to adding these subcommands.

[dokyungs]

Fixed intersect/exclude logic; skip unmatching test profile data.

Added tests for both intersect/exclude subcommands to check their basic functionality.

Code deduplication/cleanup is work in progress; will be addressed in the next upload.

[dokyungs]

Deduplicated almost identical code; merged intersect_main and
exclude_main into reduce_main, intersectValueProfdate and
excludeValueProfData into reduceValueProfData.

[davidxl]

please also document the new commands in docs/CommandGuide/llvm-profdata.rst

[dokyungs]

Document the new subcommands.

Support -text and -binary output only for the new subcommands.

[dokyungs]

Ping

llvm/include/llvm/ProfileData/InstrProf.h

struct InstrProfValueSiteRecord {
   void merge(InstrProfValueSiteRecord &Input, uint64_t Weight,
              function_ref<void(instrprof_error)> Warn);
   /// Scale up value profile data counts by N (Numerator) / D (Denominator).
   void scale(uint64_t N, uint64_t D, function_ref<void(instrprof_error)> Warn);
 
   /// Compute the overlap b/w this record and Input record.
   void overlap(InstrProfValueSiteRecord &Input, uint32_t ValueKind,
                OverlapStats &Overlap, OverlapStats &FuncLevelOverlap);
+
+  /// Reduce this record to the intersection of this and \p Input record.
+  void intersect(InstrProfValueSiteRecord &Input,
+                 function_ref<void(instrprof_error)> Warn);
+
+  /// Exclude data from this record if found in \p Input record.
+  void exclude(InstrProfValueSiteRecord &Input,
+               function_ref<void(instrprof_error)> Warn);
 };
 
 /// Profiling information for a single function.
 struct InstrProfRecord {
   std::vector<uint64_t> Counts;
 
   InstrProfRecord() = default;
   InstrProfRecord(std::vector<uint64_t> Counts) : Counts(std::move(Counts)) {}
struct InstrProfRecord {
   void overlap(InstrProfRecord &Other, OverlapStats &Overlap,
                OverlapStats &FuncLevelOverlap, uint64_t ValueCutoff);
 
   /// Compute the overlap of value profile counts.
   void overlapValueProfData(uint32_t ValueKind, InstrProfRecord &Src,
                             OverlapStats &Overlap,
                             OverlapStats &FuncLevelOverlap);
 
+  /// Reduce this record to the intersection of this one and \p Other.
+  void intersect(InstrProfRecord &Other,
+                 function_ref<void(instrprof_error)> Warn);
+
+  /// Reduce this record such that it excludes any profile data
+  /// found in \p Other.
+  void exclude(InstrProfRecord &Other,
+               function_ref<void(instrprof_error)> Warn);
+
 private:
   struct ValueProfData {
     std::vector<InstrProfValueSiteRecord> IndirectCallSites;
     std::vector<InstrProfValueSiteRecord> MemOPSizes;
   };
   std::unique_ptr<ValueProfData> ValueData;
 
   MutableArrayRef<InstrProfValueSiteRecord>
private:
   // Scale merged value counts by \p Weight.
   void mergeValueProfData(uint32_t ValkeKind, InstrProfRecord &Src,
                           uint64_t Weight,
                           function_ref<void(instrprof_error)> Warn);
 
   // Scale up value profile data count by N (Numerator) / D (Denominator).
   void scaleValueProfData(uint32_t ValueKind, uint64_t N, uint64_t D,
                           function_ref<void(instrprof_error)> Warn);
+
+  // Reduce data to the intersection of \p Src record and this record.
+  void intersectValueProfData(uint32_t ValkeKind, InstrProfRecord &Src,
+                              function_ref<void(instrprof_error)> Warn);
+
+  // Exclude any data found in \p Src record from this record.
+  void excludeValueProfData(uint32_t ValkeKind, InstrProfRecord &Src,
+                            function_ref<void(instrprof_error)> Warn);
 };
 
 struct NamedInstrProfRecord : InstrProfRecord {
   StringRef Name;
   uint64_t Hash;
 
   // We reserve this bit as the flag for context sensitive profile record.
   static const int CS_FLAG_IN_FUNC_HASH = 60;

llvm/lib/ProfileData/InstrProf.cpp

void InstrProfValueSiteRecord::scale(uint64_t N, uint64_t D,
   for (auto I = ValueData.begin(), IE = ValueData.end(); I != IE; ++I) {
     bool Overflowed;
     I->Count = SaturatingMultiply(I->Count, N, &Overflowed) / D;
     if (Overflowed)
       Warn(instrprof_error::counter_overflow);
   }
 }
 
+void InstrProfValueSiteRecord::intersect(
+    InstrProfValueSiteRecord &Input, function_ref<void(instrprof_error)> Warn) {
+  this->sortByTargetValues();
+  Input.sortByTargetValues();
+  auto I = ValueData.begin();
+  auto IE = ValueData.end();
+  for (auto J = Input.ValueData.begin(), JE = Input.ValueData.end(); J != JE;
+       ++J) {
+    while (I != IE && I->Value < J->Value)
+      ++I;
+    if (I != IE && I->Value == J->Value) {
+      I->Count = std::min<uint64_t>(I->Count, J->Count);
+      ++I;
+    }
+  }
+}
+
+void InstrProfValueSiteRecord::exclude(
+    InstrProfValueSiteRecord &Input, function_ref<void(instrprof_error)> Warn) {
+  this->sortByTargetValues();
+  Input.sortByTargetValues();
+  auto I = ValueData.begin();
+  auto IE = ValueData.end();
+  for (auto J = Input.ValueData.begin(), JE = Input.ValueData.end(); J != JE;
+       ++J) {
+    while (I != IE && I->Value < J->Value)
+      ++I;
+    if (I != IE && I->Value == J->Value) {
+      if (J->Count > 0)
+        I->Count = 0;
+      ++I;
+    }
+  }
+}
+
 // Merge Value Profile data from Src record to this record for ValueKind.
 // Scale merged value counts by \p Weight.
 void InstrProfRecord::mergeValueProfData(
     uint32_t ValueKind, InstrProfRecord &Src, uint64_t Weight,
     function_ref<void(instrprof_error)> Warn) {
   uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
   uint32_t OtherNumValueSites = Src.getNumValueSites(ValueKind);
   if (ThisNumValueSites != OtherNumValueSites) {
for (auto &Count : this->Counts) {
     Count = SaturatingMultiply(Count, N, &Overflowed) / D;
     if (Overflowed)
       Warn(instrprof_error::counter_overflow);
   }
   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
     scaleValueProfData(Kind, N, D, Warn);
 }
 
+void InstrProfRecord::intersectValueProfData(
+    uint32_t ValueKind, InstrProfRecord &Src,
+    function_ref<void(instrprof_error)> Warn) {
+  uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
+  uint32_t OtherNumValueSites = Src.getNumValueSites(ValueKind);
+  if (ThisNumValueSites != OtherNumValueSites) {
+    Warn(instrprof_error::value_site_count_mismatch);
+    return;
+  }
+  if (!ThisNumValueSites)
+    return;
+  std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =
+      getOrCreateValueSitesForKind(ValueKind);
+  MutableArrayRef<InstrProfValueSiteRecord> OtherSiteRecords =
+      Src.getValueSitesForKind(ValueKind);
+  for (uint32_t I = 0; I < ThisNumValueSites; I++)
+    ThisSiteRecords[I].intersect(OtherSiteRecords[I], Warn);
+}
+
+void InstrProfRecord::intersect(InstrProfRecord &Other,
+                                function_ref<void(instrprof_error)> Warn) {
+  // If the number of counters doesn't match we either have bad data
+  // or a hash collision.
+  if (Counts.size() != Other.Counts.size()) {
+    Warn(instrprof_error::count_mismatch);
+    return;
+  }
+
+  for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {
+    Counts[I] = std::min<uint64_t>(Counts[I], Other.Counts[I]);
+  }
+
+  for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
+    intersectValueProfData(Kind, Other, Warn);
+}
+
+void InstrProfRecord::excludeValueProfData(
+    uint32_t ValueKind, InstrProfRecord &Src,
+    function_ref<void(instrprof_error)> Warn) {
+  uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
+  uint32_t OtherNumValueSites = Src.getNumValueSites(ValueKind);
+  if (ThisNumValueSites != OtherNumValueSites) {
+    Warn(instrprof_error::value_site_count_mismatch);
+    return;
+  }
+  if (!ThisNumValueSites)
+    return;
+  std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =
+      getOrCreateValueSitesForKind(ValueKind);
+  MutableArrayRef<InstrProfValueSiteRecord> OtherSiteRecords =
+      Src.getValueSitesForKind(ValueKind);
+  for (uint32_t I = 0; I < ThisNumValueSites; I++)
+    ThisSiteRecords[I].exclude(OtherSiteRecords[I], Warn);
+}
+
+void InstrProfRecord::exclude(InstrProfRecord &Other,
+                              function_ref<void(instrprof_error)> Warn) {
+  // If the number of counters doesn't match we either have bad data
+  // or a hash collision.
+  if (Counts.size() != Other.Counts.size()) {
+    Warn(instrprof_error::count_mismatch);
+    return;
+  }
+
+  for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {
+    if (Other.Counts[I] > 0)
+      Counts[I] = 0;
+  }
+
+  for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
+    excludeValueProfData(Kind, Other, Warn);
+}
+
 // Map indirect call target name hash to name string.
 uint64_t InstrProfRecord::remapValue(uint64_t Value, uint32_t ValueKind,
                                      InstrProfSymtab *SymTab) {
   if (!SymTab)
     return Value;
 
   if (ValueKind == IPVK_IndirectCallTarget)
     return SymTab->getFunctionHashFromAddress(Value);

llvm/test/tools/llvm-profdata/exclude.test

+RUN: llvm-profdata merge -o %t_ir_base.profdata %p/Inputs/overlap_1.proftext
+RUN: llvm-profdata merge -o %t_ir_test.profdata %p/Inputs/overlap_2.proftext
+RUN: llvm-profdata exclude -text -o %t_ir_output.proftext %t_ir_base.profdata %t_ir_test.profdata
+RUN: FileCheck --input-file=%t_ir_output.proftext %s
+
+CHECK: :ir
+CHECK: bar
+CHECK: 12884901887
+CHECK: 1
+CHECK: 0
+
+CHECK: bar1
+CHECK: 12884901887
+CHECK: 1
+CHECK: 100000
+
+CHECK: foo
+CHECK: 25571299074
+CHECK: 2
+CHECK: 40000
+CHECK: 60000
+
+CHECK: main
+CHECK: 29212902728
+CHECK: 2
+CHECK: 0
+CHECK: 0

llvm/test/tools/llvm-profdata/intersect.test

+RUN: llvm-profdata merge -o %t_ir_base.profdata %p/Inputs/overlap_1.proftext
+RUN: llvm-profdata merge -o %t_ir_test.profdata %p/Inputs/overlap_2.proftext
+RUN: llvm-profdata intersect -text -o %t_ir_output.proftext %t_ir_base.profdata %t_ir_test.profdata
+RUN: FileCheck --input-file=%t_ir_output.proftext %s
+
+CHECK: :ir
+CHECK: bar
+CHECK: 12884901887
+CHECK: 1
+CHECK: 10000
+
+CHECK: main
+CHECK: 29212902728
+CHECK: 2
+CHECK: 20000
+CHECK: 0

llvm/tools/llvm-profdata/llvm-profdata.cpp

static int overlap_main(int argc, const char *argv[]) {
 
   overlapInstrProfile(BaseFilename, TestFilename,
                       OverlapFuncFilters{ValueCutoff, FuncNameFilter}, OS,
                       IsCS);
 
   return 0;
 }
 
+static void intersectInstrProfile(const std::string &BaseFilename,
+                                  const std::string &TestFilename,
+                                  const std::string &OutputFilename,
+                                  ProfileFormat OutputFormat) {
+  if (OutputFilename.compare("-") == 0)
+    exitWithError("Cannot write indexed profdata format to stdout.");
+
+  if (OutputFormat != PF_Binary && OutputFormat != PF_Compact_Binary &&
+      OutputFormat != PF_Ext_Binary && OutputFormat != PF_Text)
+    exitWithError("Unknown format is specified.");
+
+  std::mutex ErrorLock;
+  SmallSet<instrprof_error, 4> WriterErrorCodes;
+  WriterContext WC(false, ErrorLock, WriterErrorCodes);
+  WeightedFile BaseInput{BaseFilename, 1};
+  WeightedFile TestInput{TestFilename, 1};
+
+  auto BaseReaderOrErr = InstrProfReader::create(BaseInput.Filename);
+  if (Error E = BaseReaderOrErr.takeError()) {
+    exitWithError(std::move(E), "Error in reading base profile data");
+  }
+  auto TestReaderOrErr = IndexedInstrProfReader::create(TestInput.Filename);
+  if (Error E = TestReaderOrErr.takeError()) {
+    exitWithError(std::move(E), "Error in reading test profile data");
+  }
+
+  auto BaseReader = std::move(BaseReaderOrErr.get());
+  auto TestReader = std::move(TestReaderOrErr.get());
+
+  bool IsIRProfile = BaseReader->isIRLevelProfile();
+  bool HasCSIRProfile = BaseReader->hasCSIRLevelProfile();
+  if (WC.Writer.setIsIRLevelProfile(IsIRProfile, HasCSIRProfile)) {
+    exitWithError("Mixing IR generated profile with Clang generated profile.");
+  }
+  WC.Writer.setInstrEntryBBEnabled(BaseReader->instrEntryBBEnabled());
+
+  for (auto &I : *BaseReader) {
+    const StringRef FuncName = I.Name;
+    const auto FuncHash = I.Hash;
+
+    auto RecordOrErr = TestReader->getInstrProfRecord(FuncName, FuncHash);
+    if (Error E = RecordOrErr.takeError()) {
+      consumeError(std::move(E));
+      continue;
+    }
+
+    auto Record = std::move(RecordOrErr.get());
+    I.intersect(Record, [&](instrprof_error E) {
+      exitWithError(toString(make_error<InstrProfError>(E)));
+    });
+
+    WC.Writer.addRecord(std::move(I), BaseInput.Weight,
+                        [&](Error E) { exitWithError(std::move(E)); });
+  }
+
+  writeInstrProfile(OutputFilename, OutputFormat, WC.Writer);
+}
+
+static int intersect_main(int argc, const char *argv[]) {
+  cl::opt<std::string> BaseFilename(cl::Positional, cl::Required,
+                                    cl::desc("<base profile file>"));
+  cl::opt<std::string> TestFilename(cl::Positional, cl::Required,
+                                    cl::desc("<test profile file>"));
+  cl::opt<std::string> OutputFilename("output", cl::value_desc("output"),
+                                      cl::init("-"), cl::Required,
+                                      cl::desc("Output file"));
+  cl::alias OutputA("o", cl::desc("Alias for --output"),
+                    cl::aliasopt(OutputFilename));
+  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_Compact_Binary, "compbinary",
+                     "Compact binary encoding"),
+          clEnumValN(PF_Ext_Binary, "extbinary", "Extensible binary encoding"),
+          clEnumValN(PF_Text, "text", "Text encoding"),
+          clEnumValN(PF_GCC, "gcc",
+                     "GCC encoding (only meaningful for -sample)")));
+  cl::ParseCommandLineOptions(
+      argc, argv,
+      "LLVM profile data tool that performs the following set operation: <base "
+      "profile file> INTERSECT <test profile file>\n");
+
+  intersectInstrProfile(BaseFilename, TestFilename, OutputFilename,
+                        OutputFormat);
+
+  return 0;
+}
+
+static void excludeInstrProfile(const std::string &BaseFilename,
+                                const std::string &TestFilename,
+                                const std::string &OutputFilename,
+                                ProfileFormat OutputFormat) {
+  if (OutputFilename.compare("-") == 0)
+    exitWithError("Cannot write indexed profdata format to stdout.");
+
+  if (OutputFormat != PF_Binary && OutputFormat != PF_Compact_Binary &&
+      OutputFormat != PF_Ext_Binary && OutputFormat != PF_Text)
+    exitWithError("Unknown format is specified.");
+
+  std::mutex ErrorLock;
+  SmallSet<instrprof_error, 4> WriterErrorCodes;
+  WriterContext WC(false, ErrorLock, WriterErrorCodes);
+  WeightedFile BaseInput{BaseFilename, 1};
+  WeightedFile TestInput{TestFilename, 1};
+
+  auto BaseReaderOrErr = InstrProfReader::create(BaseInput.Filename);
+  if (Error E = BaseReaderOrErr.takeError()) {
+    exitWithError(std::move(E), "Error in reading base profile data");
+  }
+  auto TestReaderOrErr = IndexedInstrProfReader::create(TestInput.Filename);
+  if (Error E = TestReaderOrErr.takeError()) {
+    exitWithError(std::move(E), "Error in reading test profile data");
+  }
+
+  auto BaseReader = std::move(BaseReaderOrErr.get());
+  auto TestReader = std::move(TestReaderOrErr.get());
+
+  bool IsIRProfile = BaseReader->isIRLevelProfile();
+  bool HasCSIRProfile = BaseReader->hasCSIRLevelProfile();
+  if (WC.Writer.setIsIRLevelProfile(IsIRProfile, HasCSIRProfile)) {
+    exitWithError("Mixing IR generated profile with Clang generated profile.");
+  }
+  WC.Writer.setInstrEntryBBEnabled(BaseReader->instrEntryBBEnabled());
+
+  for (auto &I : *BaseReader) {
+    const StringRef FuncName = I.Name;
+    const auto FuncHash = I.Hash;
+
+    auto RecordOrErr = TestReader->getInstrProfRecord(FuncName, FuncHash);
+    if (Error E = RecordOrErr.takeError()) {
+      consumeError(std::move(E));
+    } else {
+      auto Record = std::move(RecordOrErr.get());
+      I.exclude(Record, [&](instrprof_error E) {
+        exitWithError(toString(make_error<InstrProfError>(E)));
+      });
+    }
+
+    WC.Writer.addRecord(std::move(I), BaseInput.Weight,
+                        [&](Error E) { exitWithError(std::move(E)); });
+  }
+
+  writeInstrProfile(OutputFilename, OutputFormat, WC.Writer);
+}
+
+static int exclude_main(int argc, const char *argv[]) {
+  cl::opt<std::string> BaseFilename(cl::Positional, cl::Required,
+                                    cl::desc("<base profile file>"));
+  cl::opt<std::string> TestFilename(cl::Positional, cl::Required,
+                                    cl::desc("<test profile file>"));
+  cl::opt<std::string> OutputFilename("output", cl::value_desc("output"),
+                                      cl::init("-"), cl::Required,
+                                      cl::desc("Output file"));
+  cl::alias OutputA("o", cl::desc("Alias for --output"),
+                    cl::aliasopt(OutputFilename));
+  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_Compact_Binary, "compbinary",
+                     "Compact binary encoding"),
+          clEnumValN(PF_Ext_Binary, "extbinary", "Extensible binary encoding"),
+          clEnumValN(PF_Text, "text", "Text encoding"),
+          clEnumValN(PF_GCC, "gcc",
+                     "GCC encoding (only meaningful for -sample)")));
+  cl::ParseCommandLineOptions(
+      argc, argv,
+      "LLVM profile data tool that performs the following set operation: <base "
+      "profile file> NOT IN <test profile file>\n");
+
+  excludeInstrProfile(BaseFilename, TestFilename, OutputFilename, OutputFormat);
+
+  return 0;
+}
+
 typedef struct ValueSitesStats {
   ValueSitesStats()
       : TotalNumValueSites(0), TotalNumValueSitesWithValueProfile(0),
         TotalNumValues(0) {}
   uint64_t TotalNumValueSites;
   uint64_t TotalNumValueSitesWithValueProfile;
   uint64_t TotalNumValues;
   std::vector<unsigned> ValueSitesHistogram;
if (argc > 1) {
     int (*func)(int, const char *[]) = nullptr;
 
     if (strcmp(argv[1], "merge") == 0)
       func = merge_main;
     else if (strcmp(argv[1], "show") == 0)
       func = show_main;
     else if (strcmp(argv[1], "overlap") == 0)
       func = overlap_main;
+    // Other useful operators for differential coverage analysis
+    else if (strcmp(argv[1], "intersect") == 0)
+      func = intersect_main;
+    else if (strcmp(argv[1], "exclude") == 0)
+      func = exclude_main;
 
     if (func) {
       std::string Invocation(ProgName.str() + " " + argv[1]);
       argv[1] = Invocation.c_str();
       return func(argc - 1, argv + 1);
     }
 
     if (strcmp(argv[1], "-h") == 0 || strcmp(argv[1], "-help") == 0 ||