[Coverage] Revise format to reduce binary size

Revise the coverage mapping format to reduce binary size by:

1. Naming function records and marking them `linkonce_odr`, and
2. Compressing filenames.

This shrinks the size of llc's coverage segment by 82% (334MB -> 62MB)
and speeds up end-to-end single-threaded report generation by 10%. For
reference the compressed name data in llc is 81MB (__llvm_prf_names).

Rationale for changes to the format:

- With the current format, most coverage function records are discarded.
  E.g., more than 97% of the records in llc are *duplicate* placeholders
  for functions visible-but-not-used in TUs. Placeholders *are* used to
  show under-covered functions, but duplicate placeholders waste space.

- We reached general consensus about giving (1) a try at the 2017 code
  coverage BoF [1]. The thinking was that using `linkonce_odr` to merge
  duplicates is simpler than alternatives like teaching build systems
  about a coverage-aware database/module/etc on the side.

- Revising the format is expensive due to the backwards compatibility
  requirement, so we might as well compress filenames while we're at it.
  This shrinks the encoded filenames in llc by 86% (12MB -> 1.6MB).

See CoverageMappingFormat.rst for the details on what exactly has
changed.

Fixes PR34533 [2], hopefully.

[1] http://lists.llvm.org/pipermail/llvm-dev/2017-October/118428.html
[2] https://bugs.llvm.org/show_bug.cgi?id=34533

Differential Revision: https://reviews.llvm.org/D69471

1 files changed, 40 insertions, 9 deletions

diff --git a/compiler-rt/include/profile/InstrProfData.inc b/compiler-rt/include/profile/InstrProfData.inc
index 99f41d8..5e5f4ff 100644
--- a/compiler-rt/include/profile/InstrProfData.inc
+++ b/compiler-rt/include/profile/InstrProfData.inc
@@ -198,6 +198,14 @@ VALUE_PROF_KIND(IPVK_Last, IPVK_MemOPSize, "last")
 #undef VALUE_PROF_KIND
 /* VALUE_PROF_KIND end */
 
+#undef COVMAP_V2_OR_V3
+#ifdef COVMAP_V2
+#define COVMAP_V2_OR_V3
+#endif
+#ifdef COVMAP_V3
+#define COVMAP_V2_OR_V3
+#endif
+
 /* COVMAP_FUNC_RECORD start */
 /* Definition of member fields of the function record structure in coverage
  * map.
@@ -214,16 +222,30 @@ COVMAP_FUNC_RECORD(const IntPtrT, llvm::Type::getInt8PtrTy(Ctx), \
 COVMAP_FUNC_RECORD(const uint32_t, llvm::Type::getInt32Ty(Ctx), NameSize, \
                    llvm::ConstantInt::get(llvm::Type::getInt32Ty(Ctx), \
                    NameValue.size()))
-#else
+#endif
+#ifdef COVMAP_V2_OR_V3
 COVMAP_FUNC_RECORD(const int64_t, llvm::Type::getInt64Ty(Ctx), NameRef, \
-                   llvm::ConstantInt::get(llvm::Type::getInt64Ty(Ctx), \
-                   llvm::IndexedInstrProf::ComputeHash(NameValue)))
+                   llvm::ConstantInt::get( \
+                     llvm::Type::getInt64Ty(Ctx), NameHash))
 #endif
 COVMAP_FUNC_RECORD(const uint32_t, llvm::Type::getInt32Ty(Ctx), DataSize, \
-                   llvm::ConstantInt::get(llvm::Type::getInt32Ty(Ctx),\
-                   CoverageMapping.size()))
+                   llvm::ConstantInt::get( \
+                     llvm::Type::getInt32Ty(Ctx), CoverageMapping.size()))
 COVMAP_FUNC_RECORD(const uint64_t, llvm::Type::getInt64Ty(Ctx), FuncHash, \
-                   llvm::ConstantInt::get(llvm::Type::getInt64Ty(Ctx), FuncHash))
+                   llvm::ConstantInt::get( \
+                     llvm::Type::getInt64Ty(Ctx), FuncHash))
+#ifdef COVMAP_V3
+COVMAP_FUNC_RECORD(const uint64_t, llvm::Type::getInt64Ty(Ctx), FilenamesRef, \
+                   llvm::ConstantInt::get( \
+                     llvm::Type::getInt64Ty(Ctx), FilenamesRef))
+COVMAP_FUNC_RECORD(const char, \
+                   llvm::ArrayType::get(llvm::Type::getInt8Ty(Ctx), \
+                                        CoverageMapping.size()), \
+                   CoverageMapping,
+                   llvm::ConstantDataArray::getRaw( \
+                     CoverageMapping, CoverageMapping.size(), \
+                     llvm::Type::getInt8Ty(Ctx)))
+#endif
 #undef COVMAP_FUNC_RECORD
 /* COVMAP_FUNC_RECORD end.  */
 
@@ -236,7 +258,7 @@ COVMAP_FUNC_RECORD(const uint64_t, llvm::Type::getInt64Ty(Ctx), FuncHash, \
 #define INSTR_PROF_DATA_DEFINED
 #endif
 COVMAP_HEADER(uint32_t, Int32Ty, NRecords, \
-              llvm::ConstantInt::get(Int32Ty,  FunctionRecords.size()))
+              llvm::ConstantInt::get(Int32Ty, NRecords))
 COVMAP_HEADER(uint32_t, Int32Ty, FilenamesSize, \
               llvm::ConstantInt::get(Int32Ty, FilenamesSize))
 COVMAP_HEADER(uint32_t, Int32Ty, CoverageSize, \
@@ -267,6 +289,9 @@ INSTR_PROF_SECT_ENTRY(IPSK_vnodes, \
 INSTR_PROF_SECT_ENTRY(IPSK_covmap, \
                       INSTR_PROF_QUOTE(INSTR_PROF_COVMAP_COMMON), \
                       INSTR_PROF_COVMAP_COFF, "__LLVM_COV,")
+INSTR_PROF_SECT_ENTRY(IPSK_covfun, \
+                      INSTR_PROF_QUOTE(INSTR_PROF_COVFUN_COMMON), \
+                      INSTR_PROF_COVFUN_COFF, "__LLVM_COV,")
 INSTR_PROF_SECT_ENTRY(IPSK_orderfile, \
                       INSTR_PROF_QUOTE(INSTR_PROF_ORDERFILE_COMMON), \
                       INSTR_PROF_QUOTE(INSTR_PROF_ORDERFILE_COFF), "__DATA,")
@@ -633,8 +658,8 @@ serializeValueProfDataFrom(ValueProfRecordClosure *Closure,
 #define INSTR_PROF_RAW_VERSION 5
 /* Indexed profile format version (start from 1). */
 #define INSTR_PROF_INDEX_VERSION 5
-/* Coverage mapping format vresion (start from 0). */
-#define INSTR_PROF_COVMAP_VERSION 2
+/* Coverage mapping format version (start from 0). */
+#define INSTR_PROF_COVMAP_VERSION 3
 
 /* Profile version is always of type uint64_t. Reserve the upper 8 bits in the
  * version for other variants of profile. We set the lowest bit of the upper 8
@@ -661,6 +686,7 @@ serializeValueProfDataFrom(ValueProfRecordClosure *Closure,
 #define INSTR_PROF_VALS_COMMON __llvm_prf_vals
 #define INSTR_PROF_VNODES_COMMON __llvm_prf_vnds
 #define INSTR_PROF_COVMAP_COMMON __llvm_covmap
+#define INSTR_PROF_COVFUN_COMMON __llvm_covfun
 #define INSTR_PROF_ORDERFILE_COMMON __llvm_orderfile
 /* Windows section names. Because these section names contain dollar characters,
  * they must be quoted.
@@ -671,6 +697,7 @@ serializeValueProfDataFrom(ValueProfRecordClosure *Closure,
 #define INSTR_PROF_VALS_COFF ".lprfv$M"
 #define INSTR_PROF_VNODES_COFF ".lprfnd$M"
 #define INSTR_PROF_COVMAP_COFF ".lcovmap$M"
+#define INSTR_PROF_COVFUN_COFF ".lcovfun$M"
 #define INSTR_PROF_ORDERFILE_COFF ".lorderfile$M"
 
 #ifdef _WIN32
@@ -685,6 +712,7 @@ serializeValueProfDataFrom(ValueProfRecordClosure *Closure,
 /* Value profile nodes section. */
 #define INSTR_PROF_VNODES_SECT_NAME INSTR_PROF_VNODES_COFF
 #define INSTR_PROF_COVMAP_SECT_NAME INSTR_PROF_COVMAP_COFF
+#define INSTR_PROF_COVFUN_SECT_NAME INSTR_PROF_COVFUN_COFF
 #define INSTR_PROF_ORDERFILE_SECT_NAME INSTR_PROF_ORDERFILE_COFF
 #else
 /* Runtime section names and name strings.  */
@@ -698,6 +726,7 @@ serializeValueProfDataFrom(ValueProfRecordClosure *Closure,
 /* Value profile nodes section. */
 #define INSTR_PROF_VNODES_SECT_NAME INSTR_PROF_QUOTE(INSTR_PROF_VNODES_COMMON)
 #define INSTR_PROF_COVMAP_SECT_NAME INSTR_PROF_QUOTE(INSTR_PROF_COVMAP_COMMON)
+#define INSTR_PROF_COVFUN_SECT_NAME INSTR_PROF_QUOTE(INSTR_PROF_COVFUN_COMMON)
 /* Order file instrumentation. */
 #define INSTR_PROF_ORDERFILE_SECT_NAME                                         \
   INSTR_PROF_QUOTE(INSTR_PROF_ORDERFILE_COMMON)
@@ -752,3 +781,5 @@ typedef struct InstrProfValueData {
 #else
 #undef INSTR_PROF_DATA_DEFINED
 #endif
+
+#undef COVMAP_V2_OR_V3