[llvm-profdata] Add overlap command to compute similarity b/w two profile files

[xur]

Summary

Add overlap functionality to llvm-profdata tool to compute the similarity between two profile files.

[xur]

Minor fix of the comments.

[xur]

Removed some un-intended changes.

[davidxl]

llvm/docs/CommandGuide/llvm-profdata.rst

240 ↗

(On Diff #196121)

match underscore length with word.

250 ↗

(On Diff #196121)

show --> overlap

253 ↗

(On Diff #196121)

as follows

258 ↗

(On Diff #196121)

add space between ')' and 'and'

259 ↗

(On Diff #196121)

what does 'unique' mean here?

270 ↗

(On Diff #196121)

This definition of 'overlap' captures branch probability well (relatvie), but loses the information on absolute count. There should be an option to measure that.

[xur]

llvm/docs/CommandGuide/llvm-profdata.rst

259 ↗

(On Diff #196121)

I changed to "unmatched counters (or counters only existing in) "

270 ↗

(On Diff #196121)

You are right that it does not computer the absolute counter difference.

The overlap is actually the overlap of distribution of the counts.
I changed the description a little bit to reflect this.

The summary of the overlap does print out the sum of the counts for both profiles. But the absolute counter difference is not the main purpose.
If I want that, I think it should belong to another sub-command, like "diff".

[xur]

Integrated David's review comments.

[davidxl]

llvm/docs/CommandGuide/llvm-profdata.rst

268 ↗

(On Diff #196347)

not --> no

286 ↗

(On Diff #196347)

-o=output or -o output

llvm/lib/ProfileData/InstrProf.cpp

1210 ↗

(On Diff #196347)

For function level dump, the # of function is redundant -- perhaps change it to # of counters

The overall dump format looks better with this:

1. program level:
   
   Edge Profile: (overlap, # of functions ) 80%, 10 Incall Profile: (overlap, # of functions) 70%, 10 ...
2. function level Edge Profile: (overlap, # of counters) 75%, 10 ...

1211 ↗

(On Diff #196347)

The header and content does not match in fields.

llvm/lib/ProfileData/InstrProfWriter.cpp

190 ↗

(On Diff #196347)

Why is this a writer method?

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

223 ↗

(On Diff #196347)

The title print including the summary can be pushed into FuncOverlap::dump() method

228 ↗

(On Diff #196347)

The title can be pushed into FunctionOverlap::dump() method.

[xur]

llvm/docs/CommandGuide/llvm-profdata.rst

286 ↗

(On Diff #196347)

it does take -output.
may be "-output=output, -output output, -o=output, or -o output"? (it's a little verbose). I actually copied this line from merge and show subcommand

llvm/lib/ProfileData/InstrProf.cpp

1210 ↗

(On Diff #196347)

I will change to this format.

add number of counts to function level is a good idea.

1211 ↗

(On Diff #196347)

why this does not match?
the first column is the percent score and the second is the number if functions in this category. I don't see the problem.

llvm/lib/ProfileData/InstrProfWriter.cpp

190 ↗

(On Diff #196347)

because this reuses the merge framework (load the base profile to write context) and load the second one to do the overlap calculation.

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

223 ↗

(On Diff #196347)

This would require to put a flag in the structure to distinguish whether this is function level or program level. It can be done.

228 ↗

(On Diff #196347)

This would require add both profile file name to the structure.

[xur]

Integrated David's review comments. Mainly changed the reporting format.

[davidxl]

llvm/include/llvm/ProfileData/InstrProf.h

594 ↗

(On Diff #196884)

How to tell if count or percentage is stored here?

597 ↗

(On Diff #196884)

The name EdgeCount is misleading -- it sounds like number of 'edges' in CFG. Perhaps just 'TotalCount' or 'CountSum'

612 ↗

(On Diff #196884)

BaseSum-->Base

614 ↗

(On Diff #196884)

TestSum --> Test

llvm/lib/ProfileData/InstrProf.cpp

482 ↗

(On Diff #196884)

This is not 'getCountSums' -- but 'accumuateCounts' -- perhaps rename it.

511 ↗

(On Diff #196884)

The loop nest can be merged into one single loop:

while (i != ie && j != je) {

  if (i->v == j->v) {
     //match:
     ...
     i++; j++;
  } else if (i->v > j->v) {
      j++;
      // handle mismatch case -- as one value appears in only one record (assuming count == 0)
     ...
  } else {
      i++;
       // handle mismatch
  }
}
// handle the rest of the mismatched cases.

}

553 ↗

(On Diff #196884)

already be computed and is nonzero

560 ↗

(On Diff #196884)

Perhaps just check the function hash?

596 ↗

(On Diff #196884)

+= or just = ?

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

212 ↗

(On Diff #196884)

-> silently

I don't see a return here.

[xur]

llvm/include/llvm/ProfileData/InstrProf.h

594 ↗

(On Diff #196884)

The caller should keep track of this. This data structure does not know -- it just a floating points.

llvm/lib/ProfileData/InstrProf.cpp

511 ↗

(On Diff #196884)

Yes. The version I used is a copy from merge function.
Your version is better here because it will terminate when one of arrays reaches the end.

553 ↗

(On Diff #196884)

Yes. it's true for call chains in this patch.
I put an assert here just to catch others callers that not init TestSum.

560 ↗

(On Diff #196884)

FuncHash already being checked (In Reader). This is just to handle the cases that escapes the hash check.

596 ↗

(On Diff #196884)

they are the same. the incoming value should be 0 by the initializer.

[xur]

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

212 ↗

(On Diff #196884)

fixed

[xur]

Integrated David's review comments

[xur]

Discussed offline with David. We changed the output to a simpler: "Description: <Value>" format. This tool will mostly used in a script. Simpler format will make text grep cleaner.

[davidxl]

llvm/lib/ProfileData/InstrProf.cpp

1240 ↗

(On Diff #197161)

"mismatched count percentage(EdgeProfile): " seems more obvious.

1243 ↗

(On Diff #197161)

percentage of EdgeProfile only in test_profile:

llvm/lib/ProfileData/InstrProfWriter.cpp

219 ↗

(On Diff #197161)

why resetting it to zero?

[xur]

llvm/lib/ProfileData/InstrProfWriter.cpp

219 ↗

(On Diff #197161)

setting to zero so that the comparison always true in function InstrProfRecord::overlap() (so that we output function level information).
this way we only need to pass the cutoff value rather the filter object.

[xur]

Adjusted the output string with David's comments.
Also made the naming more uniformed for edge and value profiles.

[davidxl]

lgtm

llvm/trunk/docs/CommandGuide/llvm-profdata.rst

 The :program:`llvm-profdata` tool is a small utility for working with profile
 data files.
 
 COMMANDS
 --------
 
 * :ref:`merge <profdata-merge>`
 * :ref:`show <profdata-show>`
+* :ref:`overlap <profdata-overlap>`
 
 .. program:: llvm-profdata merge
 
 .. _profdata-merge:
 
 MERGE
 -----
 

  Only output names of functions whose max count value are below the cutoff
  value.
 
 .. option:: -showcs
 
  Only show context sensitive profile counts. The default is to filter all
  context sensitive profile counts.
 
+.. program:: llvm-profdata overlap
+
+.. _profdata-overlap:
+
+OVERLAP
+-------
+
+SYNOPSIS
+^^^^^^^^
+
+:program:`llvm-profdata overlap` [*options*] [*base profile file*] [*test profile file*]
+
+DESCRIPTION
+^^^^^^^^^^^
+
+:program:`llvm-profdata overlap` takes two profile data files and displays the
+*overlap* of counter distribution between the whole files and between any of the
+specified functions.
+
+In this command, *overlap* is defined as follows:
+Suppose *base profile file* has the following counts:
+{c1_1, c1_2, ..., c1_n, c1_u_1, c2_u_2, ..., c2_u_s},
+and *test profile file* has
+{c2_1, c2_2, ..., c2_n, c2_v_1, c2_v_2, ..., c2_v_t}.
+Here c{1|2}_i (i = 1 .. n) are matched counters and c1_u_i (i = 1 .. s) and
+c2_v_i (i = 1 .. v) are unmatched counters (or counters only existing in)
+*base profile file* and *test profile file*, respectively.
+Let sum_1 = c1_1 + c1_2 +  ... + c1_n +  c1_u_1 + c2_u_2 + ... + c2_u_s, and
+sum_2 = c2_1 + c2_2 + ... + c2_n + c2_v_1 + c2_v_2 + ... + c2_v_t.
+*overlap* = min(c1_1/sum_1, c2_1/sum_2) + min(c1_2/sum_1, c2_2/sum_2) + ...
+            min(c1_n/sum_1, c2_n/sum_2).
+
+The result overlap distribution is a percentage number, ranging from 0.0% to
+100.0%, where 0.0% means there is no overlap and 100.0% means a perfect
+overlap.
+
+Here is an example, if *base profile file* has counts of {400, 600}, and
+*test profile file* has matched counts of {60000, 40000}. The *overlap* is 80%.
+
+
+OPTIONS
+^^^^^^^
+
+.. option:: -function=string
+
+ Print details for a function if the function's name contains the given string.
+
+.. option:: -help
+
+ Print a summary of command line options.
+
+.. option:: -o=output or -o output
+
+ Specify the output file name.  If *output* is ``-`` or it isn't specified,
+ then the output is sent to standard output.
+
+.. option:: -value-cutoff=n
+
+ Show only those functions whose max count values are greater or equal to ``n``.
+ By default, the value-cutoff is set to max of unsigned long long.
+
+.. option:: -cs
+
+ Only show overlap for the context sensitive profile counts. The default is to show
+ non-context sensitive profile counts.
+
 EXIT STATUS
 -----------
 
 :program:`llvm-profdata` returns 1 if the command is omitted or is invalid,
 if it cannot read input files, or if there is a mismatch between their data.

llvm/trunk/include/llvm/ProfileData/InstrProf.h

 StringRef InstrProfSymtab::getOrigFuncName(uint64_t FuncMD5Hash) {
   StringRef PGOName = getFuncName(FuncMD5Hash);
   size_t S = PGOName.find_first_of(':');
   if (S == StringRef::npos)
     return PGOName;
   return PGOName.drop_front(S + 1);
 }
 
+// To store the sums of profile count values, or the percentage of
+// the sums of the total count values.
+struct CountSumOrPercent {
+  uint64_t NumEntries;
+  double CountSum;
+  double ValueCounts[IPVK_Last - IPVK_First + 1];
+  CountSumOrPercent() : NumEntries(0), CountSum(0.0f), ValueCounts() {}
+  void reset() {
+    NumEntries = 0;
+    CountSum = 0.0f;
+    for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++)
+      ValueCounts[I] = 0.0f;
+  }
+};
+
+// Function level or program level overlap information.
+struct OverlapStats {
+  enum OverlapStatsLevel { ProgramLevel, FunctionLevel };
+  // Sum of the total count values for the base profile.
+  CountSumOrPercent Base;
+  // Sum of the total count values for the test profile.
+  CountSumOrPercent Test;
+  // Overlap lap score. Should be in range of [0.0f to 1.0f].
+  CountSumOrPercent Overlap;
+  CountSumOrPercent Mismatch;
+  CountSumOrPercent Unique;
+  OverlapStatsLevel Level;
+  const std::string *BaseFilename;
+  const std::string *TestFilename;
+  StringRef FuncName;
+  uint64_t FuncHash;
+  bool Valid;
+
+  OverlapStats(OverlapStatsLevel L = ProgramLevel)
+      : Level(L), BaseFilename(nullptr), TestFilename(nullptr), FuncHash(0),
+        Valid(false) {}
+
+  void dump(raw_fd_ostream &OS) const;
+
+  void setFuncInfo(StringRef Name, uint64_t Hash) {
+    FuncName = Name;
+    FuncHash = Hash;
+  }
+
+  Error accumuateCounts(const std::string &BaseFilename,
+                        const std::string &TestFilename, bool IsCS);
+  void addOneMismatch(const CountSumOrPercent &MismatchFunc);
+  void addOneUnique(const CountSumOrPercent &UniqueFunc);
+
+  static inline double score(uint64_t Val1, uint64_t Val2, double Sum1,
+                             double Sum2) {
+    if (Sum1 < 1.0f || Sum2 < 1.0f)
+      return 0.0f;
+    return std::min(Val1 / Sum1, Val2 / Sum2);
+  }
+};
+
+// This is used to filter the functions whose overlap information
+// to be output.
+struct OverlapFuncFilters {
+  uint64_t ValueCutoff;
+  const std::string NameFilter;
+};
+
 struct InstrProfValueSiteRecord {
   /// Value profiling data pairs at a given value site.
   std::list<InstrProfValueData> ValueData;
 
   InstrProfValueSiteRecord() { ValueData.clear(); }
   template <class InputIterator>
   InstrProfValueSiteRecord(InputIterator F, InputIterator L)
       : ValueData(F, L) {}
struct InstrProfValueSiteRecord {
   inline void sortByCount();
 
   /// Merge data from another InstrProfValueSiteRecord
   /// Optionally scale merged counts by \p Weight.
   void merge(InstrProfValueSiteRecord &Input, uint64_t Weight,
              function_ref<void(instrprof_error)> Warn);
   /// Scale up value profile data counts.
   void scale(uint64_t Weight, 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);
 };
 
 /// 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 Clear() {
     Counts.clear();
     clearValueData();
   }
 
   /// Clear value data entries
   void clearValueData() { ValueData = nullptr; }
 
+  /// Compute the sums of all counts and store in Sum.
+  void accumuateCounts(CountSumOrPercent &Sum) const;
+
+  /// Compute the overlap b/w this IntrprofRecord and Other.
+  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);
+
 private:
   struct ValueProfData {
     std::vector<InstrProfValueSiteRecord> IndirectCallSites;
     std::vector<InstrProfValueSiteRecord> MemOPSizes;
   };
   std::unique_ptr<ValueProfData> ValueData;
 
   MutableArrayRef<InstrProfValueSiteRecord>

 // Create a COMDAT variable INSTR_PROF_RAW_VERSION_VAR to make the runtime
 // aware this is an ir_level profile so it can set the version flag.
 void createIRLevelProfileFlagVar(Module &M, bool IsCS);
 
 // Create the variable for the profile file name.
 void createProfileFileNameVar(Module &M, StringRef InstrProfileOutput);
 
 } // end namespace llvm
-
 #endif // LLVM_PROFILEDATA_INSTRPROF_H

llvm/trunk/include/llvm/ProfileData/InstrProfReader.h

public:
   /// backend or frontend). Since creating PGO symtab can create
   /// significant runtime and memory overhead (as it touches data
   /// for the whole program), InstrProfSymtab for the indexed profile
   /// reader should be created on demand and it is recommended to be
   /// only used for dumping purpose with llvm-proftool, not with the
   /// compiler.
   virtual InstrProfSymtab &getSymtab() = 0;
 
+  /// Compute the sum of counts and return in Sum.
+  void accumuateCounts(CountSumOrPercent &Sum, bool IsCS);
+
 protected:
   std::unique_ptr<InstrProfSymtab> Symtab;
 
   /// Set the current error and return same.
   Error error(instrprof_error Err) {
     LastError = Err;
     if (Err == instrprof_error::success)
       return Error::success();

llvm/trunk/include/llvm/ProfileData/InstrProfWriter.h

if (ProfileKind == PF_IRLevel && WithCS)
       ProfileKind = PF_IRLevelWithCS;
 
     return Error::success();
   }
 
   // Internal interface for testing purpose only.
   void setValueProfDataEndianness(support::endianness Endianness);
   void setOutputSparse(bool Sparse);
+  // Compute the overlap b/w this object and Other. Program level result is
+  // stored in Overlap and function level result is stored in FuncLevelOverlap.
+  void overlapRecord(NamedInstrProfRecord &&Other, OverlapStats &Overlap,
+                     OverlapStats &FuncLevelOverlap,
+                     const OverlapFuncFilters &FuncFilter);
 
 private:
   void addRecord(StringRef Name, uint64_t Hash, InstrProfRecord &&I,
                  uint64_t Weight, function_ref<void(Error)> Warn);
   bool shouldEncodeData(const ProfilingData &PD);
   void writeImpl(ProfOStream &OS);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_INSTRPROFWRITER_H

llvm/trunk/lib/ProfileData/InstrProf.cpp

 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
+#include "llvm/ProfileData/InstrProfReader.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/LEB128.h"
for (StringRef &Name : Names)
         return E;
 
     while (P < EndP && *P == 0)
       P++;
   }
   return Error::success();
 }
 
+void InstrProfRecord::accumuateCounts(CountSumOrPercent &Sum) const {
+  uint64_t FuncSum = 0;
+  Sum.NumEntries += Counts.size();
+  for (size_t F = 0, E = Counts.size(); F < E; ++F)
+    FuncSum += Counts[F];
+  Sum.CountSum += FuncSum;
+
+  for (uint32_t VK = IPVK_First; VK <= IPVK_Last; ++VK) {
+    uint64_t KindSum = 0;
+    uint32_t NumValueSites = getNumValueSites(VK);
+    for (size_t I = 0; I < NumValueSites; ++I) {
+      uint32_t NV = getNumValueDataForSite(VK, I);
+      std::unique_ptr<InstrProfValueData[]> VD = getValueForSite(VK, I);
+      for (uint32_t V = 0; V < NV; V++)
+        KindSum += VD[V].Count;
+    }
+    Sum.ValueCounts[VK] += KindSum;
+  }
+}
+
+void InstrProfValueSiteRecord::overlap(InstrProfValueSiteRecord &Input,
+                                       uint32_t ValueKind,
+                                       OverlapStats &Overlap,
+                                       OverlapStats &FuncLevelOverlap) {
+  this->sortByTargetValues();
+  Input.sortByTargetValues();
+  double Score = 0.0f, FuncLevelScore = 0.0f;
+  auto I = ValueData.begin();
+  auto IE = ValueData.end();
+  auto J = Input.ValueData.begin();
+  auto JE = Input.ValueData.end();
+  while (I != IE && J != JE) {
+    if (I->Value == J->Value) {
+      Score += OverlapStats::score(I->Count, J->Count,
+                                   Overlap.Base.ValueCounts[ValueKind],
+                                   Overlap.Test.ValueCounts[ValueKind]);
+      FuncLevelScore += OverlapStats::score(
+          I->Count, J->Count, FuncLevelOverlap.Base.ValueCounts[ValueKind],
+          FuncLevelOverlap.Test.ValueCounts[ValueKind]);
+      ++I;
+    } else if (I->Value < J->Value) {
+      ++I;
+      continue;
+    }
+    ++J;
+  }
+  Overlap.Overlap.ValueCounts[ValueKind] += Score;
+  FuncLevelOverlap.Overlap.ValueCounts[ValueKind] += FuncLevelScore;
+}
+
+// Return false on mismatch.
+void InstrProfRecord::overlapValueProfData(uint32_t ValueKind,
+                                           InstrProfRecord &Other,
+                                           OverlapStats &Overlap,
+                                           OverlapStats &FuncLevelOverlap) {
+  uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
+  uint32_t OtherNumValueSites = Other.getNumValueSites(ValueKind);
+  assert(ThisNumValueSites == OtherNumValueSites);
+  if (!ThisNumValueSites)
+    return;
+
+  std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =
+      getOrCreateValueSitesForKind(ValueKind);
+  MutableArrayRef<InstrProfValueSiteRecord> OtherSiteRecords =
+      Other.getValueSitesForKind(ValueKind);
+  for (uint32_t I = 0; I < ThisNumValueSites; I++)
+    ThisSiteRecords[I].overlap(OtherSiteRecords[I], ValueKind, Overlap,
+                               FuncLevelOverlap);
+}
+
+void InstrProfRecord::overlap(InstrProfRecord &Other, OverlapStats &Overlap,
+                              OverlapStats &FuncLevelOverlap,
+                              uint64_t ValueCutoff) {
+  // FuncLevel CountSum for other should already computed and nonzero.
+  assert(FuncLevelOverlap.Test.CountSum >= 1.0f);
+  accumuateCounts(FuncLevelOverlap.Base);
+  bool Mismatch = (Counts.size() != Other.Counts.size());
+
+  // Check if the value profiles mismatch.
+  if (!Mismatch) {
+    for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) {
+      uint32_t ThisNumValueSites = getNumValueSites(Kind);
+      uint32_t OtherNumValueSites = Other.getNumValueSites(Kind);
+      if (ThisNumValueSites != OtherNumValueSites) {
+        Mismatch = true;
+        break;
+      }
+    }
+  }
+  if (Mismatch) {
+    Overlap.addOneMismatch(FuncLevelOverlap.Test);
+    return;
+  }
+
+  // Compute overlap for value counts.
+  for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
+    overlapValueProfData(Kind, Other, Overlap, FuncLevelOverlap);
+
+  double Score = 0.0;
+  uint64_t MaxCount = 0;
+  // Compute overlap for edge counts.
+  for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {
+    Score += OverlapStats::score(Counts[I], Other.Counts[I],
+                                 Overlap.Base.CountSum, Overlap.Test.CountSum);
+    MaxCount = std::max(Other.Counts[I], MaxCount);
+  }
+  Overlap.Overlap.CountSum += Score;
+  Overlap.Overlap.NumEntries += 1;
+
+  if (MaxCount >= ValueCutoff) {
+    double FuncScore = 0.0;
+    for (size_t I = 0, E = Other.Counts.size(); I < E; ++I)
+      FuncScore += OverlapStats::score(Counts[I], Other.Counts[I],
+                                       FuncLevelOverlap.Base.CountSum,
+                                       FuncLevelOverlap.Test.CountSum);
+    FuncLevelOverlap.Overlap.CountSum = FuncScore;
+    FuncLevelOverlap.Overlap.NumEntries = Other.Counts.size();
+    FuncLevelOverlap.Valid = true;
+  }
+}
+
 void InstrProfValueSiteRecord::merge(InstrProfValueSiteRecord &Input,
                                      uint64_t Weight,
                                      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;
void createProfileFileNameVar(Module &M, StringRef InstrProfileOutput) {
   Triple TT(M.getTargetTriple());
   if (TT.supportsCOMDAT()) {
     ProfileNameVar->setLinkage(GlobalValue::ExternalLinkage);
     ProfileNameVar->setComdat(M.getOrInsertComdat(
         StringRef(INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_NAME_VAR))));
   }
 }
 
+Error OverlapStats::accumuateCounts(const std::string &BaseFilename,
+                                    const std::string &TestFilename,
+                                    bool IsCS) {
+  auto getProfileSum = [IsCS](const std::string &Filename,
+                              CountSumOrPercent &Sum) -> Error {
+    auto ReaderOrErr = InstrProfReader::create(Filename);
+    if (Error E = ReaderOrErr.takeError()) {
+      return E;
+    }
+    auto Reader = std::move(ReaderOrErr.get());
+    Reader->accumuateCounts(Sum, IsCS);
+    return Error::success();
+  };
+  auto Ret = getProfileSum(BaseFilename, Base);
+  if (Ret)
+    return std::move(Ret);
+  Ret = getProfileSum(TestFilename, Test);
+  if (Ret)
+    return std::move(Ret);
+  this->BaseFilename = &BaseFilename;
+  this->TestFilename = &TestFilename;
+  Valid = true;
+  return Error::success();
+}
+
+void OverlapStats::addOneMismatch(const CountSumOrPercent &MismatchFunc) {
+  Mismatch.NumEntries += 1;
+  Mismatch.CountSum += MismatchFunc.CountSum / Test.CountSum;
+  for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++) {
+    if (Test.ValueCounts[I] >= 1.0f)
+      Mismatch.ValueCounts[I] +=
+          MismatchFunc.ValueCounts[I] / Test.ValueCounts[I];
+  }
+}
+
+void OverlapStats::addOneUnique(const CountSumOrPercent &UniqueFunc) {
+  Unique.NumEntries += 1;
+  Unique.CountSum += UniqueFunc.CountSum / Test.CountSum;
+  for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++) {
+    if (Test.ValueCounts[I] >= 1.0f)
+      Unique.ValueCounts[I] += UniqueFunc.ValueCounts[I] / Test.ValueCounts[I];
+  }
+}
+
+void OverlapStats::dump(raw_fd_ostream &OS) const {
+  if (!Valid)
+    return;
+
+  const char *EntryName =
+      (Level == ProgramLevel ? "functions" : "edge counters");
+  if (Level == ProgramLevel) {
+    OS << "Profile overlap infomation for base_profile: " << *BaseFilename
+       << " and test_profile: " << *TestFilename << "\nProgram level:\n";
+  } else {
+    OS << "Function level:\n"
+       << "  Function: " << FuncName << " (Hash=" << FuncHash << ")\n";
+  }
+
+  OS << "  # of " << EntryName << " overlap: " << Overlap.NumEntries << "\n";
+  if (Mismatch.NumEntries)
+    OS << "  # of " << EntryName << " mismatch: " << Mismatch.NumEntries
+       << "\n";
+  if (Unique.NumEntries)
+    OS << "  # of " << EntryName
+       << " only in test_profile: " << Unique.NumEntries << "\n";
+
+  OS << "  Edge profile overlap: " << format("%.3f%%", Overlap.CountSum * 100)
+     << "\n";
+  if (Mismatch.NumEntries)
+    OS << "  Mismatched count percentage (Edge): "
+       << format("%.3f%%", Mismatch.CountSum * 100) << "\n";
+  if (Unique.NumEntries)
+    OS << "  Percentage of Edge profile only in test_profile: "
+       << format("%.3f%%", Unique.CountSum * 100) << "\n";
+  OS << "  Edge profile base count sum: " << format("%.0f", Base.CountSum)
+     << "\n"
+     << "  Edge profile test count sum: " << format("%.0f", Test.CountSum)
+     << "\n";
+
+  for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++) {
+    if (Base.ValueCounts[I] < 1.0f && Test.ValueCounts[I] < 1.0f)
+      continue;
+    char ProfileKindName[20];
+    switch (I) {
+    case IPVK_IndirectCallTarget:
+      strncpy(ProfileKindName, "IndirectCall", 19);
+      break;
+    case IPVK_MemOPSize:
+      strncpy(ProfileKindName, "MemOP", 19);
+      break;
+    default:
+      snprintf(ProfileKindName, 19, "VP[%d]", I);
+      break;
+    }
+    OS << "  " << ProfileKindName
+       << " profile overlap: " << format("%.3f%%", Overlap.ValueCounts[I] * 100)
+       << "\n";
+    if (Mismatch.NumEntries)
+      OS << "  Mismatched count percentage (" << ProfileKindName
+         << "): " << format("%.3f%%", Mismatch.ValueCounts[I] * 100) << "\n";
+    if (Unique.NumEntries)
+      OS << "  Percentage of " << ProfileKindName
+         << " profile only in test_profile: "
+         << format("%.3f%%", Unique.ValueCounts[I] * 100) << "\n";
+    OS << "  " << ProfileKindName
+       << " profile base count sum: " << format("%.0f", Base.ValueCounts[I])
+       << "\n"
+       << "  " << ProfileKindName
+       << " profile test count sum: " << format("%.0f", Test.ValueCounts[I])
+       << "\n";
+  }
+}
+
 } // end namespace llvm

llvm/trunk/lib/ProfileData/InstrProfReader.cpp

Error IndexedInstrProfReader::readNextRecord(NamedInstrProfRecord &Record) {
 
   Record = Data[RecordIndex++];
   if (RecordIndex >= Data.size()) {
     Index->advanceToNextKey();
     RecordIndex = 0;
   }
   return success();
 }
+
+void InstrProfReader::accumuateCounts(CountSumOrPercent &Sum, bool IsCS) {
+  uint64_t NumFuncs = 0;
+  for (const auto &Func : *this) {
+    if (isIRLevelProfile()) {
+      bool FuncIsCS = NamedInstrProfRecord::hasCSFlagInHash(Func.Hash);
+      if (FuncIsCS != IsCS)
+        continue;
+    }
+    Func.accumuateCounts(Sum);
+    ++NumFuncs;
+  }
+  Sum.NumEntries = NumFuncs;
+}

llvm/trunk/lib/ProfileData/InstrProfWriter.cpp

 
 void InstrProfWriter::addRecord(NamedInstrProfRecord &&I, uint64_t Weight,
                                 function_ref<void(Error)> Warn) {
   auto Name = I.Name;
   auto Hash = I.Hash;
   addRecord(Name, Hash, std::move(I), Weight, Warn);
 }
 
+void InstrProfWriter::overlapRecord(NamedInstrProfRecord &&Other,
+                                    OverlapStats &Overlap,
+                                    OverlapStats &FuncLevelOverlap,
+                                    const OverlapFuncFilters &FuncFilter) {
+  auto Name = Other.Name;
+  auto Hash = Other.Hash;
+  Other.accumuateCounts(FuncLevelOverlap.Test);
+  if (FunctionData.find(Name) == FunctionData.end()) {
+    Overlap.addOneUnique(FuncLevelOverlap.Test);
+    return;
+  }
+  if (FuncLevelOverlap.Test.CountSum < 1.0f) {
+    Overlap.Overlap.NumEntries += 1;
+    return;
+  }
+  auto &ProfileDataMap = FunctionData[Name];
+  bool NewFunc;
+  ProfilingData::iterator Where;
+  std::tie(Where, NewFunc) =
+      ProfileDataMap.insert(std::make_pair(Hash, InstrProfRecord()));
+  if (NewFunc) {
+    Overlap.addOneMismatch(FuncLevelOverlap.Test);
+    return;
+  }
+  InstrProfRecord &Dest = Where->second;
+
+  uint64_t ValueCutoff = FuncFilter.ValueCutoff;
+  if (!FuncFilter.NameFilter.empty() &&
+      Name.find(FuncFilter.NameFilter) != Name.npos)
+    ValueCutoff = 0;
+
+  Dest.overlap(Other, Overlap, FuncLevelOverlap, ValueCutoff);
+}
+
 void InstrProfWriter::addRecord(StringRef Name, uint64_t Hash,
                                 InstrProfRecord &&I, uint64_t Weight,
                                 function_ref<void(Error)> Warn) {
   auto &ProfileDataMap = FunctionData[Name];
 
   bool NewFunc;
   ProfilingData::iterator Where;
   std::tie(Where, NewFunc) =

llvm/trunk/test/tools/llvm-profdata/Inputs/overlap_1.proftext

+# IR level Instrumentation Flag
+:ir
+bar
+# Func Hash:
[phone]
+# Num Counters:
+1
+# Counter Values:
+100000
+
+bar1
+# Func Hash:
[phone]
+# Num Counters:
+1
+# Counter Values:
+100000
+
+foo
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
+40000
+60000
+
+main
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
+200000
+0
+

llvm/trunk/test/tools/llvm-profdata/Inputs/overlap_1_cs.proftext

+# CSIR level Instrumentation Flag
+:csir
+bar
+# Func Hash:
+1152921534274394772
+# Num Counters:
+2
+# Counter Values:
+6000
+4000
+

llvm/trunk/test/tools/llvm-profdata/Inputs/overlap_1_vp.proftext

+:IR
+foo
+# Func Hash:
+72057649435042473
+# Num Counters:
+2
+# Counter Values:
+40000
+60000
+# Num Value Kinds:
+2
+# ValueKind = IPVK_IndirectCallTarget:
+0
+# NumValueSites:
+1
+2
+bar1:40000
+bar2:60000
+# ValueKind = IPVK_MemOPSize:
+1
+# NumValueSites:
+1
+2
+1:40000
+4:60000

llvm/trunk/test/tools/llvm-profdata/Inputs/overlap_2.proftext

+# IR level Instrumentation Flag
+:ir
+bar
+# Func Hash:
[phone]
+# Num Counters:
+1
+# Counter Values:
+10000
+
+bar2
+# Func Hash:
[phone]
+# Num Counters:
+1
+# Counter Values:
+10000
+
+foo
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
+4000
+6000
+
+main
+# Func Hash:
[phone]
+# Num Counters:
+2
+# Counter Values:
+20000
+0
+

llvm/trunk/test/tools/llvm-profdata/Inputs/overlap_2_cs.proftext

+# CSIR level Instrumentation Flag
+:csir
+bar
+# Func Hash:
+1152921534274394772
+# Num Counters:
+2
+# Counter Values:
+4000
+6000
+

llvm/trunk/test/tools/llvm-profdata/Inputs/overlap_2_vp.proftext

+:IR
+foo
+# Func Hash:
+72057649435042473
+# Num Counters:
+2
+# Counter Values:
+30000
+20000
+# Num Value Kinds:
+2
+# ValueKind = IPVK_IndirectCallTarget:
+0
+# NumValueSites:
+1
+2
+bar1:30000
+bar2:20000
+# ValueKind = IPVK_MemOPSize:
+1
+# NumValueSites:
+1
+2
+1:3000
+4:2000

llvm/trunk/test/tools/llvm-profdata/overlap.test

+RUN: llvm-profdata overlap %p/Inputs/overlap_1.proftext %p/Inputs/overlap_2.proftext | FileCheck %s -check-prefix=OVERLAP
+RUN: llvm-profdata overlap -function=main %p/Inputs/overlap_1.proftext %p/Inputs/overlap_2.proftext | FileCheck %s -check-prefix=MAINFUNC -check-prefix=OVERLAP
+RUN: llvm-profdata overlap -value-cutoff=15000 %p/Inputs/overlap_1.proftext %p/Inputs/overlap_2.proftext | FileCheck %s -check-prefix=MAINFUNC -check-prefix=OVERLAP
+RUN: llvm-profdata merge %p/Inputs/overlap_1.proftext -o %t_1.profdata
+RUN: llvm-profdata merge %p/Inputs/overlap_2.proftext -o %t_2.profdata
+RUN: llvm-profdata overlap %t_1.profdata %t_2.profdata | FileCheck %s -check-prefix=OVERLAP
+MAINFUNC: Function: main (Hash=29212902728)
+MAINFUNC:   # of edge counters overlap: 2
+MAINFUNC:   Edge profile overlap: 100.000%
+MAINFUNC:   Edge profile base count sum: 200000
+MAINFUNC:   Edge profile test count sum: 20000
+OVERLAP: Profile overlap infomation for base_profile: {{.*}} and test_profile:
+OVERLAP: Program level:
+OVERLAP:   # of functions overlap: 2
+OVERLAP:   # of functions mismatch: 1
+OVERLAP:   # of functions only in test_profile: 1
+OVERLAP:   Edge profile overlap: 60.000%
+OVERLAP:   Mismatched count percentage (Edge): 20.000%
+OVERLAP:   Percentage of Edge profile only in test_profile: 20.000%
+OVERLAP:   Edge profile base count sum: 500000
+OVERLAP:   Edge profile test count sum: 50000

llvm/trunk/test/tools/llvm-profdata/overlap_cs.test

+RUN: llvm-profdata overlap -cs %p/Inputs/overlap_1_cs.proftext %p/Inputs/overlap_2_cs.proftext | FileCheck %s -check-prefix=OVERLAP
+RUN: llvm-profdata merge %p/Inputs/overlap_1_cs.proftext -o %t_1_cs.profdata
+RUN: llvm-profdata merge %p/Inputs/overlap_2_cs.proftext -o %t_2_cs.profdata
+RUN: llvm-profdata overlap -cs %t_1_cs.profdata %t_2_cs.profdata | FileCheck %s -check-prefix=OVERLAP
+OVERLAP: Profile overlap infomation for base_profile: {{.*}} and test_profile:
+OVERLAP: Program level:
+OVERLAP:  # of functions overlap: 1
+OVERLAP:  Edge profile overlap: 80.000%
+OVERLAP:  Edge profile base count sum: 10000
+OVERLAP:  Edge profile test count sum: 10000

llvm/trunk/test/tools/llvm-profdata/overlap_vp.test

+RUN: llvm-profdata overlap %p/Inputs/overlap_1_vp.proftext %p/Inputs/overlap_2_vp.proftext | FileCheck %s -check-prefix=OVERLAP
+RUN: llvm-profdata merge %p/Inputs/overlap_1_vp.proftext -o %t_1_vp.profdata
+RUN: llvm-profdata merge %p/Inputs/overlap_2_vp.proftext -o %t_2_vp.profdata
+RUN: llvm-profdata overlap %t_1_vp.profdata %t_2_vp.profdata | FileCheck %s -check-prefix=OVERLAP
+OVERLAP: Profile overlap infomation for base_profile: {{.*}} and test_profile:
+OVERLAP: Program level:
+OVERLAP:   # of functions overlap: 1
+OVERLAP:   Edge profile overlap: 80.000%
+OVERLAP:   Edge profile base count sum: 100000
+OVERLAP:   Edge profile test count sum: 50000
+OVERLAP:   IndirectCall profile overlap: 80.000%
+OVERLAP:   IndirectCall profile base count sum: 100000
+OVERLAP:   IndirectCall profile test count sum: 50000
+OVERLAP:   MemOP profile overlap: 80.000%
+OVERLAP:   MemOP profile base count sum: 100000
+OVERLAP:   MemOP profile test count sum: 5000

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

static bool isFatalError(instrprof_error IPE) {
   case instrprof_error::hash_mismatch:
   case instrprof_error::count_mismatch:
   case instrprof_error::counter_overflow:
   case instrprof_error::value_site_count_mismatch:
     return false;
   }
 }
 
+/// Computer the overlap b/w profile BaseFilename and TestFileName,
+/// and store the program level result to Overlap.
+static void overlapInput(const std::string &BaseFilename,
+                         const std::string &TestFilename, WriterContext *WC,
+                         OverlapStats &Overlap,
+                         const OverlapFuncFilters &FuncFilter,
+                         raw_fd_ostream &OS, bool IsCS) {
+  auto ReaderOrErr = InstrProfReader::create(TestFilename);
+  if (Error E = ReaderOrErr.takeError()) {
+    // Skip the empty profiles by returning sliently.
+    instrprof_error IPE = InstrProfError::take(std::move(E));
+    if (IPE != instrprof_error::empty_raw_profile)
+      WC->Err = make_error<InstrProfError>(IPE);
+    return;
+  }
+
+  auto Reader = std::move(ReaderOrErr.get());
+  for (auto &I : *Reader) {
+    OverlapStats FuncOverlap(OverlapStats::FunctionLevel);
+    FuncOverlap.setFuncInfo(I.Name, I.Hash);
+
+    WC->Writer.overlapRecord(std::move(I), Overlap, FuncOverlap, FuncFilter);
+    FuncOverlap.dump(OS);
+  }
+}
+
 /// Load an input into a writer context.
 static void loadInput(const WeightedFile &Input, SymbolRemapper *Remapper,
                       WriterContext *WC) {
   std::unique_lock<std::mutex> CtxGuard{WC->Lock};
 
   // If there's a pending hard error, don't do more work.
   if (WC->Err)
     return;
mergeInstrProfile(WeightedInputs, Remapper.get(), OutputFilename,
                       OutputFormat, OutputSparse, NumThreads);
   else
     mergeSampleProfile(WeightedInputs, Remapper.get(), OutputFilename,
                        OutputFormat);
 
   return 0;
 }
 
+/// Computer the overlap b/w profile BaseFilename and profile TestFilename.
+static void overlapInstrProfile(const std::string &BaseFilename,
+                                const std::string &TestFilename,
+                                const OverlapFuncFilters &FuncFilter,
+                                raw_fd_ostream &OS, bool IsCS) {
+  std::mutex ErrorLock;
+  SmallSet<instrprof_error, 4> WriterErrorCodes;
+  WriterContext Context(false, ErrorLock, WriterErrorCodes);
+  WeightedFile WeightedInput{BaseFilename, 1};
+  OverlapStats Overlap;
+  Error E = Overlap.accumuateCounts(BaseFilename, TestFilename, IsCS);
+  if (E)
+    exitWithError(std::move(E), "Error in getting profile count sums");
+  if (Overlap.Base.CountSum < 1.0f) {
+    OS << "Sum of edge counts for profile " << BaseFilename << " is 0.\n";
+    exit(0);
+  }
+  if (Overlap.Test.CountSum < 1.0f) {
+    OS << "Sum of edge counts for profile " << TestFilename << " is 0.\n";
+    exit(0);
+  }
+  loadInput(WeightedInput, nullptr, &Context);
+  overlapInput(BaseFilename, TestFilename, &Context, Overlap, FuncFilter, OS,
+               IsCS);
+  Overlap.dump(OS);
+}
+
+static int overlap_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> Output("output", cl::value_desc("output"), cl::init("-"),
+                              cl::desc("Output file"));
+  cl::alias OutputA("o", cl::desc("Alias for --output"), cl::aliasopt(Output));
+  cl::opt<bool> IsCS("cs", cl::init(false),
+                     cl::desc("For context sensitive counts"));
+  cl::opt<unsigned long long> ValueCutoff(
+      "value-cutoff", cl::init(-1),
+      cl::desc(
+          "Function level overlap information for every function in test "
+          "profile with max count value greater then the parameter value"));
+  cl::opt<std::string> FuncNameFilter(
+      "function",
+      cl::desc("Function level overlap information for matching functions"));
+  cl::ParseCommandLineOptions(argc, argv, "LLVM profile data overlap tool\n");
+
+  std::error_code EC;
+  raw_fd_ostream OS(Output.data(), EC, sys::fs::F_Text);
+  if (EC)
+    exitWithErrorCode(EC, Output);
+
+  overlapInstrProfile(BaseFilename, TestFilename,
+                      OverlapFuncFilters{ValueCutoff, FuncNameFilter}, OS,
+                      IsCS);
+
+  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;
int main(int argc, const char *argv[]) {
   StringRef ProgName(sys::path::filename(argv[0]));
   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;
 
     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 ||
         strcmp(argv[1], "--help") == 0) {
 
       errs() << "OVERVIEW: LLVM profile data tools\n\n"
              << "USAGE: " << ProgName << " <command> [args...]\n"
              << "USAGE: " << ProgName << " <command> -help\n\n"
              << "See each individual command --help for more details.\n"
-             << "Available commands: merge, show\n";
+             << "Available commands: merge, show, overlap\n";
       return 0;
     }
   }
 
   if (argc < 2)
     errs() << ProgName << ": No command specified!\n";
   else
     errs() << ProgName << ": Unknown command!\n";
 
-  errs() << "USAGE: " << ProgName << " <merge|show> [args...]\n";
+  errs() << "USAGE: " << ProgName << " <merge|show|overlap> [args...]\n";
   return 1;
 }