[InstrProf] Prevent duplicate functions in correlated data

[ellis]

Summary

When using debug info for profile correlation, avoid adding duplicate
functions in the synthetic Data section.

Before this patch, n duplicate function entries in the Data section would
cause counter values to be a factor of n larger. I built instrumented
clang with and without debug info correlation and got these summaries.

# With Debug Info Correlate
$ llvm-profdata show default.profdata
Instrumentation level: IR  entry_first = 0
Total functions: 182530
Maximum function count: 52034
Maximum internal block count: 5763

# Without
$ llvm-profdata show default.profdata
Instrumentation level: IR  entry_first = 0
Total functions: 183212
Maximum function count: 52034
Maximum internal block count: 5766

The slight difference in counts seem to be mostly from FileSystem and
Map functions and the difference in the number of instrumented functions
seems to come from missing debug info like destructors without source.

[kyulee]

I presume without debug-info related correlation (normal IRPGO), the metadata is merged by their linkage types/contents.
For my education, I wonder whether IRPGO might have the same named function with different different CFG shapes -- e.g., static functions.
This approach seems to pick the first appearance of metadata for the same named functions, and ignore the rest assuming they are all identical.
And also can we have a test case for this?

[ellis]

In D116051#3203500, @kyulee wrote:

I presume without debug-info related correlation (normal IRPGO), the metadata is merged by their linkage types/contents.
For my education, I wonder whether IRPGO might have the same named function with different different CFG shapes -- e.g., static functions.
This approach seems to pick the first appearance of metadata for the same named functions, and ignore the rest assuming they are all identical.

IRPGO uses GlobalValue::getGlobalIdentifier() as the function name, which will prepend the filename if necessary. https://llvm.org/doxygen/Globals_8cpp_source.html#l00133
I suppose it might be more accurate to track the counter pointers and add an assert that if there are two entries with the same counter pointer, then they must have the same function name.

And also can we have a test case for this?

I can try to find a reproducer, but I assume it would require more than one module.

[ellis]

Use CounterOffset to find duplicate probes and refactor the compiler-rt test to check this case.

[ellis]

Clear CounterOffsets set to save memory.

[kyulee]

Makes sense to check deduplication using counter address instead of function name.
LGTM.

compiler-rt/test/profile/Darwin/instrprof-debug-info-correlate.c

 // REQUIRES: zlib
 
 // Value profiling is currently not supported in lightweight mode.
-// RUN: %clang_pgogen -o %t.normal -mllvm --disable-vp=true %s
-// RUN: env LLVM_PROFILE_FILE=%t.profraw %run %t.normal
-// RUN: llvm-profdata merge -o %t.normal.profdata %t.profraw
-
-// RUN: %clang_pgogen -o %t -g -mllvm --debug-info-correlate -mllvm --disable-vp=true %s
+// RUN: %clang_pgogen -o %t -g -mllvm --debug-info-correlate -mllvm --disable-vp=true %S/../Inputs/instrprof-debug-info-correlate-main.cpp %S/../Inputs/instrprof-debug-info-correlate-foo.cpp
 // RUN: env LLVM_PROFILE_FILE=%t.proflite %run %t
 // RUN: llvm-profdata merge -o %t.profdata --debug-info=%t.dSYM %t.proflite
 
-// RUN: diff %t.normal.profdata %t.profdata
-
-int foo(int a) {
-  if (a % 2)
-    return 4 * a + 1;
-  return 0;
-}
-
-int bar(int a) {
-  while (a > 100)
-    a /= 2;
-  return a;
-}
-
-typedef int (*FP)(int);
-FP Fps[3] = {foo, bar};
+// RUN: %clang_pgogen -o %t.normal -mllvm --disable-vp=true %S/../Inputs/instrprof-debug-info-correlate-main.cpp %S/../Inputs/instrprof-debug-info-correlate-foo.cpp
+// RUN: env LLVM_PROFILE_FILE=%t.profraw %run %t.normal
+// RUN: llvm-profdata merge -o %t.normal.profdata %t.profraw
 
-int main() {
-  for (int i = 0; i < 5; i++)
-    Fps[i % 2](i);
-  return 0;
-}
+// RUN: diff %t.normal.profdata %t.profdata

compiler-rt/test/profile/Inputs/instrprof-debug-info-correlate-bar.h

+int foo(int);
+
+inline int bar(int a) {
+  while (a > 100)
+    a /= 2;
+  return a;
+}

compiler-rt/test/profile/Inputs/instrprof-debug-info-correlate-foo.cpp

+#include "instrprof-debug-info-correlate-bar.h"
+
+int foo(int a) {
+  if (a % 2)
+    return 4 * a + 1;
+  return bar(a);
+}

compiler-rt/test/profile/Inputs/instrprof-debug-info-correlate-main.cpp

+#include "instrprof-debug-info-correlate-bar.h"
+
+typedef int (*FP)(int);
+FP Fps[2] = {foo, bar};
+
+int main() {
+  for (int i = 0; i < 5; i++)
+    Fps[i % 2](i);
+  return 0;
+}

compiler-rt/test/profile/Linux/instrprof-debug-info-correlate.c

 // REQUIRES: zlib
 
 // Value profiling is currently not supported in lightweight mode.
-// RUN: %clang_pgogen -o %t.normal -mllvm --disable-vp=true %s
-// RUN: env LLVM_PROFILE_FILE=%t.profraw %run %t.normal
-// RUN: llvm-profdata merge -o %t.normal.profdata %t.profraw
-
-// RUN: %clang_pgogen -o %t -g -mllvm --debug-info-correlate -mllvm --disable-vp=true %s
+// RUN: %clang_pgogen -o %t -g -mllvm --debug-info-correlate -mllvm --disable-vp=true %S/../Inputs/instrprof-debug-info-correlate-main.cpp %S/../Inputs/instrprof-debug-info-correlate-foo.cpp
 // RUN: env LLVM_PROFILE_FILE=%t.proflite %run %t
 // RUN: llvm-profdata merge -o %t.profdata --debug-info=%t %t.proflite
 
-// RUN: diff %t.normal.profdata %t.profdata
-
-int foo(int a) {
-  if (a % 2)
-    return 4 * a + 1;
-  return 0;
-}
-
-int bar(int a) {
-  while (a > 100)
-    a /= 2;
-  return a;
-}
-
-typedef int (*FP)(int);
-FP Fps[3] = {foo, bar};
+// RUN: %clang_pgogen -o %t.normal -mllvm --disable-vp=true %S/../Inputs/instrprof-debug-info-correlate-main.cpp %S/../Inputs/instrprof-debug-info-correlate-foo.cpp
+// RUN: env LLVM_PROFILE_FILE=%t.profraw %run %t.normal
+// RUN: llvm-profdata merge -o %t.normal.profdata %t.profraw
 
-int main() {
-  for (int i = 0; i < 5; i++)
-    Fps[i % 2](i);
-  return 0;
-}
+// RUN: diff %t.normal.profdata %t.profdata

llvm/include/llvm/ProfileData/InstrProfCorrelator.h

 //===- InstrProfCorrelator.h ------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 // This file defines InstrProfCorrelator used to generate PGO profiles from
 // raw profile data and debug info.
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_PROFILEDATA_INSTRPROFCORRELATOR_H
 #define LLVM_PROFILEDATA_INSTRPROFCORRELATOR_H
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/Object/Binary.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <vector>
protected:
   void addProbe(StringRef FunctionName, uint64_t CFGHash, IntPtrT CounterOffset,
                 IntPtrT FunctionPtr, uint32_t NumCounters);
 
 private:
   InstrProfCorrelatorImpl(InstrProfCorrelatorKind Kind,
                           std::unique_ptr<InstrProfCorrelator::Context> Ctx)
       : InstrProfCorrelator(Kind, std::move(Ctx)){};
   std::vector<std::string> Names;
+  llvm::DenseSet<IntPtrT> CounterOffsets;
 
   // Byte-swap the value if necessary.
   template <class T> T maybeSwap(T Value) const {
     return Ctx->ShouldSwapBytes ? sys::getSwappedBytes(Value) : Value;
   }
 };
 
 /// DwarfInstrProfCorrelator - A child of InstrProfCorrelatorImpl that takes

llvm/lib/ProfileData/InstrProfCorrelator.cpp

 }
 
 template <class IntPtrT>
 Error InstrProfCorrelatorImpl<IntPtrT>::correlateProfileData() {
   assert(Data.empty() && CompressedNames.empty() && Names.empty());
   correlateProfileDataImpl();
   auto Result =
       collectPGOFuncNameStrings(Names, /*doCompression=*/true, CompressedNames);
+  CounterOffsets.clear();
   Names.clear();
   return Result;
 }
 
 template <class IntPtrT>
 void InstrProfCorrelatorImpl<IntPtrT>::addProbe(StringRef FunctionName,
                                                 uint64_t CFGHash,
                                                 IntPtrT CounterOffset,
                                                 IntPtrT FunctionPtr,
                                                 uint32_t NumCounters) {
+  // Check if a probe was already added for this counter offset.
+  if (!CounterOffsets.insert(CounterOffset).second)
+    return;
   Data.push_back({
       maybeSwap<uint64_t>(IndexedInstrProf::ComputeHash(FunctionName)),
       maybeSwap<uint64_t>(CFGHash),
       // In this mode, CounterPtr actually stores the section relative address
       // of the counter.
       maybeSwap<IntPtrT>(CounterOffset),
       maybeSwap<IntPtrT>(FunctionPtr),
       // TODO: Value profiling is not yet supported.