[Remarks] Add string deduplication using a string table

[thegameg]

Summary

• Add support for uniquing strings in the remark streamer and emitting the string table in the remarks section.

• Add parsing support for the string table in the RemarkParser.

From this remark:

--- !Missed
Pass:            inline
Name:            NoDefinition
DebugLoc:        { File: 'test-suite/SingleSource/UnitTests/2002-04-17-PrintfChar.c',
                   Line: 7, Column: 3 }
Function:        printArgsNoRet
Args:
  - Callee:          printf
  - String:          ' will not be inlined into '
  - Caller:          printArgsNoRet
    DebugLoc:        { File: 'test-suite/SingleSource/UnitTests/2002-04-17-PrintfChar.c',
                       Line: 6, Column: 0 }
  - String:          ' because its definition is unavailable'
...

to:

--- !Missed
Pass:            0
Name:            1
DebugLoc:        { File: 3, Line: 7, Column: 3 }
Function:        2
Args:
  - Callee:          4
  - String:          5
  - Caller:          2
    DebugLoc:        { File: 3, Line: 6, Column: 0 }
  - String:          6
...

And the string table in the .remarks/__remarks section containing:

inline\0NoDefinition\0printArgsNoRet\0test-suite/SingleSource/UnitTests/2002-04-17-PrintfChar.c\0printf\0 will not be inlined into \0 because its definition is unavailable\0

This is mostly supposed to be used for testing purposes, but it gives us a 2x reduction in the remark size, and is an incremental change for the updates to the remarks file format.

[paquette]

llvm/include/llvm/Remarks/RemarkStringTable.h

46 ↗

(On Diff #193571)

Why undefined?

[thegameg]

llvm/include/llvm/Remarks/RemarkStringTable.h

46 ↗

(On Diff #193571)

This class is supposed to be used by having a sequence of calls to add(...) and then serialize(OS). After thinking a bit more I will just remove the get function.

[thegameg]

Remove remarks::StringTable::get.

[hfinkel]

Is this transparent to tools that use LLVM's YAML library? Other tools?

If not, we'll need to update the llvm-opt-report tool and the opt-viewer tool.

[JDevlieghere]

llvm/include/llvm/Remarks/RemarkStringTable.h

40 ↗

(On Diff #193598)

Can we not use the size of the StringMap?

llvm/lib/IR/DiagnosticInfo.cpp

428 ↗

(On Diff #193598)

Since the keys are the same and only the values are different, I'd extract this in a helper function.

llvm/lib/Remarks/RemarkParser.cpp

85 ↗

(On Diff #193598)

Not sure if this would actually simplify things, but you could do

size_t NextOffset = (Index == Offsets.size() - 1) ? Buffer.size() : Offsets[Index + 1];

to not repeat the computation in the StringRef ctor.

[thegameg]

Address Jonas' remarks.

[thegameg]

In D60227#1454110, @hfinkel wrote:

Is this transparent to tools that use LLVM's YAML library? Other tools?

If not, we'll need to update the llvm-opt-report tool and the opt-viewer tool.

This is disabled by default, and enabled under -mllvm -remarks-yaml-string-table so tools like llvm-opt-report and the opt-viewer won't need any changes yet.

On the parsing side, this will expect the usage of a string table in the YAML only if the constructor with an actual string table buffer is provided. The tools don't know how to do this yet since they operate on the YAML files alone (the string table is in a section in the object file), but anyone using libRemarks.dylib/.so could use this to parse these files. I plan on making all these tools use this library at some point.

llvm/include/llvm/Remarks/RemarkStringTable.h

40 ↗

(On Diff #193598)

This is the total size of the string table that is going to be written to disk. It's the sum of the sizes of every string in the map. I can recompute this in serialize() if you think it's a nicer way to do this.

[JDevlieghere]

LGTM with the outstanding comments/questions addressed.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1365 ↗

(On Diff #193649)

Can you be more specific? Could we write everything but the version to a buffer and EmitBinaryData here?

[thegameg]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1365 ↗

(On Diff #193649)

Yes, we could, but we would perform an extra copy of the strings which this allows us to avoid.

[JDevlieghere]

LGTM

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1365 ↗

(On Diff #193649)

Fair!

llvm/trunk/docs/CodeGenerator.rst

 Emitting remark diagnostics in the object file
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 A section containing metadata on remark diagnostics will be emitted when
 -remarks-section is passed. The section contains:
 
 * a magic number: "REMARKS\0"
 * the version number: a little-endian uint64_t
+* the string table:
+  * the total size of the string table (the size itself excluded):
+    little-endian uint64_t
+  * a list of null-terminated strings
 * the absolute file path to the serialized remark diagnostics: a
   null-terminated string.
 
 VLIW Packetizer
 ---------------
 
 In a Very Long Instruction Word (VLIW) architecture, the compiler is responsible
 for mapping instructions to functional-units available on the architecture. To

llvm/trunk/include/llvm/IR/RemarkStreamer.h

 //===- llvm/IR/RemarkStreamer.h - Remark Streamer ---------------*- 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 declares the main interface for outputting remarks.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_REMARKSTREAMER_H
 #define LLVM_IR_REMARKSTREAMER_H
 
 #include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/Remarks/RemarkStringTable.h"
 #include "llvm/Support/Error.h"
+#include "llvm/Support/Regex.h"
 #include "llvm/Support/YAMLTraits.h"
 #include "llvm/Support/raw_ostream.h"
-#include "llvm/Support/Regex.h"
 #include <string>
 #include <vector>
 
 namespace llvm {
 /// Streamer for remarks.
 class RemarkStreamer {
   /// The filename that the remark diagnostics are emitted to.
   const std::string Filename;
   /// The open raw_ostream that the remark diagnostics are emitted to.
   raw_ostream &OS;
   /// The regex used to filter remarks based on the passes that emit them.
   Optional<Regex> PassFilter;
 
   /// The YAML streamer.
   yaml::Output YAMLOutput;
 
+  /// The string table containing all the unique strings used in the output.
+  /// The table will be serialized in a section to be consumed after the
+  /// compilation.
+  remarks::StringTable StrTab;
+
 public:
   RemarkStreamer(StringRef Filename, raw_ostream& OS);
   /// Return the filename that the remark diagnostics are emitted to.
   StringRef getFilename() const { return Filename; }
   /// Return stream that the remark diagnostics are emitted to.
   raw_ostream &getStream() { return OS; }
   /// Set a pass filter based on a regex \p Filter.
   /// Returns an error if the regex is invalid.
   Error setFilter(StringRef Filter);
   /// Emit a diagnostic through the streamer.
   void emit(const DiagnosticInfoOptimizationBase &Diag);
+  /// The string table used during emission.
+  remarks::StringTable &getStringTable() { return StrTab; }
+  const remarks::StringTable &getStringTable() const { return StrTab; }
 };
 } // end namespace llvm
 
 #endif // LLVM_IR_REMARKSTREAMER_H

llvm/trunk/include/llvm/Remarks/RemarkParser.h

 //===-- llvm/Remarks/Remark.h - The remark type -----------------*- 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 provides an interface for parsing remarks in LLVM.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_REMARKS_REMARK_PARSER_H
 #define LLVM_REMARKS_REMARK_PARSER_H
 
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Remarks/Remark.h"
 #include "llvm/Support/Error.h"
 #include <memory>
 
 namespace llvm {
 namespace remarks {
 
 struct ParserImpl;
 
 /// Parser used to parse a raw buffer to remarks::Remark objects.
 struct Parser {
   /// The hidden implementation of the parser.
   std::unique_ptr<ParserImpl> Impl;
 
   /// Create a parser parsing \p Buffer to Remark objects.
   /// This constructor should be only used for parsing YAML remarks.
   Parser(StringRef Buffer);
 
+  /// Create a parser parsing \p Buffer to Remark objects, using \p StrTabBuf as
+  /// string table.
+  /// This constructor should be only used for parsing YAML remarks.
+  Parser(StringRef Buffer, StringRef StrTabBuf);
+
   // Needed because ParserImpl is an incomplete type.
   ~Parser();
 
   /// Returns an empty Optional if it reached the end.
   /// Returns a valid remark otherwise.
   Expected<const Remark *> getNext() const;
 };
 
+/// In-memory representation of the string table parsed from a buffer (e.g. the
+/// remarks section).
+struct ParsedStringTable {
+  /// The buffer mapped from the section contents.
+  StringRef Buffer;
+  /// Collection of offsets in the buffer for each string entry.
+  SmallVector<size_t, 8> Offsets;
+
+  Expected<StringRef> operator[](size_t Index);
+  ParsedStringTable(StringRef Buffer);
+};
+
 } // end namespace remarks
 } // end namespace llvm
 
 #endif /* LLVM_REMARKS_REMARK_PARSER_H */

llvm/trunk/include/llvm/Remarks/RemarkStringTable.h

+//===-- RemarkStringTable.h - Serializing string table ----------*- 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 class is used to deduplicate and serialize a string table used for
+// generating remarks.
+//
+// For parsing a string table, use ParsedStringTable in RemarkParser.h
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_REMARKS_REMARK_STRING_TABLE_H
+#define LLVM_REMARKS_REMARK_STRING_TABLE_H
+
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Allocator.h"
+#include <vector>
+
+namespace llvm {
+
+class raw_ostream;
+
+namespace remarks {
+
+/// The string table used for serializing remarks.
+/// This table can be for example serialized in a section to be consumed after
+/// the compilation.
+struct StringTable {
+  /// Allocator holding all the memory used by the map.
+  BumpPtrAllocator Allocator;
+  /// The string table containing all the unique strings used in the output.
+  /// It maps a string to an unique ID.
+  StringMap<unsigned, BumpPtrAllocator &> StrTab;
+  /// Total size of the string table when serialized.
+  size_t SerializedSize = 0;
+
+  StringTable() : Allocator(), StrTab(Allocator) {}
+  /// Add a string to the table. It returns an unique ID of the string.
+  std::pair<unsigned, StringRef> add(StringRef Str);
+  /// Serialize the string table to a stream. It is serialized as a little
+  /// endian uint64 (the size of the table in bytes) followed by a sequence of
+  /// NULL-terminated strings, where the N-th string is the string with the ID N
+  /// in the StrTab map.
+  void serialize(raw_ostream &OS) const;
+  /// Serialize the string table to a vector. This allows users to do the actual
+  /// writing to file/memory/other.
+  /// The string with the ID == N should be the N-th element in the vector.
+  std::vector<StringRef> serialize() const;
+};
+
+} // end namespace remarks
+} // end namespace llvm
+
+#endif /* LLVM_REMARKS_REMARK_STRING_TABLE_H */

llvm/trunk/include/llvm/Support/YAMLTraits.h

struct SequenceTraits<std::vector<T>,
                       typename std::enable_if<CheckIsBool<
                           SequenceElementTraits<T>::flow>::value>::type>
     : SequenceTraitsImpl<std::vector<T>, SequenceElementTraits<T>::flow> {};
 template <typename T, unsigned N>
 struct SequenceTraits<SmallVector<T, N>,
                       typename std::enable_if<CheckIsBool<
                           SequenceElementTraits<T>::flow>::value>::type>
     : SequenceTraitsImpl<SmallVector<T, N>, SequenceElementTraits<T>::flow> {};
+template <typename T>
+struct SequenceTraits<SmallVectorImpl<T>,
+                      typename std::enable_if<CheckIsBool<
+                          SequenceElementTraits<T>::flow>::value>::type>
+    : SequenceTraitsImpl<SmallVectorImpl<T>, SequenceElementTraits<T>::flow> {};
 
 // Sequences of fundamental types use flow formatting.
 template <typename T>
 struct SequenceElementTraits<
     T, typename std::enable_if<std::is_fundamental<T>::value>::type> {
   static const bool flow = true;
 };
 

llvm/trunk/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

void AsmPrinter::emitRemarksSection(Module &M) {
   OutStreamer->EmitIntValue(/*Value=*/0, /*Size=*/1);
 
   // Emit the version number: little-endian uint64_t.
   // The version number is located at the offset 0x0 in the section.
   std::array<char, 8> Version;
   support::endian::write64le(Version.data(), remarks::Version);
   OutStreamer->EmitBinaryData(StringRef(Version.data(), Version.size()));
 
+  // Emit the string table in the section.
+  // Note: we need to use the streamer here to emit it in the section. We can't
+  // just use the serialize function with a raw_ostream because of the way
+  // MCStreamers work.
+  const remarks::StringTable &StrTab = RS->getStringTable();
+  std::vector<StringRef> StrTabStrings = StrTab.serialize();
+  uint64_t StrTabSize = StrTab.SerializedSize;
+  // Emit the total size of the string table (the size itself excluded):
+  // little-endian uint64_t.
+  // The total size is located after the version number.
+  std::array<char, 8> StrTabSizeBuf;
+  support::endian::write64le(StrTabSizeBuf.data(), StrTabSize);
+  OutStreamer->EmitBinaryData(
+      StringRef(StrTabSizeBuf.data(), StrTabSizeBuf.size()));
+  // Emit a list of null-terminated strings.
+  // Note: the order is important here: the ID used in the remarks corresponds
+  // to the position of the string in the section.
+  for (StringRef Str : StrTabStrings) {
+    OutStreamer->EmitBytes(Str);
+    // Explicitly emit a '\0'.
+    OutStreamer->EmitIntValue(/*Value=*/0, /*Size=*/1);
+  }
+
   // Emit the null-terminated absolute path to the remark file.
   // The path is located at the offset 0x4 in the section.
   StringRef FilenameRef = RS->getFilename();
   SmallString<128> Filename = FilenameRef;
   sys::fs::make_absolute(Filename);
   assert(!Filename.empty() && "The filename can't be empty.");
   OutStreamer->EmitBytes(Filename);
   // Explicitly emit a '\0'.

llvm/trunk/lib/CodeGen/AsmPrinter/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
 name = AsmPrinter
 parent = Libraries
-required_libraries = Analysis BinaryFormat CodeGen Core DebugInfoCodeView DebugInfoDWARF DebugInfoMSF MC MCParser Support Target
+required_libraries = Analysis BinaryFormat CodeGen Core DebugInfoCodeView DebugInfoDWARF DebugInfoMSF MC MCParser Remarks Support Target

llvm/trunk/lib/IR/DiagnosticInfo.cpp

 #include "llvm/Support/raw_ostream.h"
 #include <atomic>
 #include <cassert>
 #include <memory>
 #include <string>
 
 using namespace llvm;
 
+cl::opt<bool> UseStringTable("remarks-yaml-string-table", cl::init(false));
+
 int llvm::getNextAvailablePluginDiagnosticKind() {
   static std::atomic<int> PluginKindID(DK_FirstPluginKind);
   return ++PluginKindID;
 }
 
 const char *OptimizationRemarkAnalysis::AlwaysPrint = "";
 
 DiagnosticInfoInlineAsm::DiagnosticInfoInlineAsm(const Instruction &I,
for (const DiagnosticInfoOptimizationBase::Argument &Arg :
                                     : Args.begin() + FirstExtraArgIndex))
     OS << Arg.Val;
   return OS.str();
 }
 
 void OptimizationRemarkAnalysisFPCommute::anchor() {}
 void OptimizationRemarkAnalysisAliasing::anchor() {}
 
+template <typename T>
+static void mapRemarkHeader(
+    yaml::IO &io, T PassName, T RemarkName, DiagnosticLocation DL,
+    T FunctionName, Optional<uint64_t> Hotness,
+    SmallVectorImpl<DiagnosticInfoOptimizationBase::Argument> &Args) {
+  io.mapRequired("Pass", PassName);
+  io.mapRequired("Name", RemarkName);
+  if (!io.outputting() || DL.isValid())
+    io.mapOptional("DebugLoc", DL);
+  io.mapRequired("Function", FunctionName);
+  io.mapOptional("Hotness", Hotness);
+  io.mapOptional("Args", Args);
+}
+
 namespace llvm {
 namespace yaml {
 
 void MappingTraits<DiagnosticInfoOptimizationBase *>::mapping(
     IO &io, DiagnosticInfoOptimizationBase *&OptDiag) {
   assert(io.outputting() && "input not yet implemented");
 
   if (io.mapTag("!Passed",
else
     llvm_unreachable("Unknown remark type");
 
   // These are read-only for now.
   DiagnosticLocation DL = OptDiag->getLocation();
   StringRef FN =
       GlobalValue::dropLLVMManglingEscape(OptDiag->getFunction().getName());
 
   StringRef PassName(OptDiag->PassName);
-  io.mapRequired("Pass", PassName);
-  io.mapRequired("Name", OptDiag->RemarkName);
-  if (!io.outputting() || DL.isValid())
-    io.mapOptional("DebugLoc", DL);
-  io.mapRequired("Function", FN);
-  io.mapOptional("Hotness", OptDiag->Hotness);
-  io.mapOptional("Args", OptDiag->Args);
+  if (UseStringTable) {
+    remarks::StringTable &StrTab =
+        reinterpret_cast<RemarkStreamer *>(io.getContext())->getStringTable();
+    unsigned PassID = StrTab.add(PassName).first;
+    unsigned NameID = StrTab.add(OptDiag->RemarkName).first;
+    unsigned FunctionID = StrTab.add(FN).first;
+    mapRemarkHeader(io, PassID, NameID, DL, FunctionID, OptDiag->Hotness,
+                    OptDiag->Args);
+  } else {
+    mapRemarkHeader(io, PassName, OptDiag->RemarkName, DL, FN, OptDiag->Hotness,
+                    OptDiag->Args);
+  }
 }
 
 template <> struct MappingTraits<DiagnosticLocation> {
   static void mapping(IO &io, DiagnosticLocation &DL) {
     assert(io.outputting() && "input not yet implemented");
 
     StringRef File = DL.getRelativePath();
     unsigned Line = DL.getLine();
     unsigned Col = DL.getColumn();
 
+    if (UseStringTable) {
+      remarks::StringTable &StrTab =
+          reinterpret_cast<RemarkStreamer *>(io.getContext())->getStringTable();
+      unsigned FileID = StrTab.add(File).first;
+      io.mapRequired("File", FileID);
+    } else {
       io.mapRequired("File", File);
+    }
+
     io.mapRequired("Line", Line);
     io.mapRequired("Column", Col);
   }
 
   static const bool flow = true;
 };
 
 /// Helper struct for multiline string block literals. Use this type to preserve
static StringRef input(StringRef Scalar, void *Ctx, StringBlockVal &S) {
     return ScalarTraits<StringRef>::input(Scalar, Ctx, S.Value);
   }
 };
 
 // Implement this as a mapping for now to get proper quotation for the value.
 template <> struct MappingTraits<DiagnosticInfoOptimizationBase::Argument> {
   static void mapping(IO &io, DiagnosticInfoOptimizationBase::Argument &A) {
     assert(io.outputting() && "input not yet implemented");
-    // Emit a string block scalar for multiline strings, to preserve newlines.
-    if (StringRef(A.Val).count('\n') > 1) {
+
+    if (UseStringTable) {
+      remarks::StringTable &StrTab =
+          reinterpret_cast<RemarkStreamer *>(io.getContext())->getStringTable();
+      auto ValueID = StrTab.add(A.Val).first;
+      io.mapRequired(A.Key.data(), ValueID);
+    } else if (StringRef(A.Val).count('\n') > 1) {
       StringBlockVal S(A.Val);
       io.mapRequired(A.Key.data(), S);
-    } else
+    } else {
       io.mapRequired(A.Key.data(), A.Val);
+    }
     if (A.Loc.isValid())
       io.mapOptional("DebugLoc", A.Loc);
   }
 };
 
 } // end namespace yaml
 } // end namespace llvm
 
 LLVM_YAML_IS_SEQUENCE_VECTOR(DiagnosticInfoOptimizationBase::Argument)

llvm/trunk/lib/IR/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
 name = Core
 parent = Libraries
-required_libraries = BinaryFormat Support
+required_libraries = BinaryFormat Remarks Support

llvm/trunk/lib/IR/RemarkStreamer.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/RemarkStreamer.h"
 
 using namespace llvm;
 
 RemarkStreamer::RemarkStreamer(StringRef Filename, raw_ostream &OS)
     : Filename(Filename), OS(OS),
-      YAMLOutput(OS, reinterpret_cast<void *>(this)) {
+      YAMLOutput(OS, reinterpret_cast<void *>(this)), StrTab() {
   assert(!Filename.empty() && "This needs to be a real filename.");
 }
 
 Error RemarkStreamer::setFilter(StringRef Filter) {
   Regex R = Regex(Filter);
   std::string RegexError;
   if (!R.isValid(RegexError))
     return createStringError(std::make_error_code(std::errc::invalid_argument),

llvm/trunk/lib/Remarks/CMakeLists.txt

 add_llvm_library(LLVMRemarks
   Remark.cpp
   RemarkParser.cpp
+  RemarkStringTable.cpp
   YAMLRemarkParser.cpp
 )

llvm/trunk/lib/Remarks/RemarkParser.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/CBindingWrapping.h"
 
 using namespace llvm;
 using namespace llvm::remarks;
 
 Parser::Parser(StringRef Buf) : Impl(llvm::make_unique<YAMLParserImpl>(Buf)) {}
 
+Parser::Parser(StringRef Buf, StringRef StrTabBuf)
+    : Impl(llvm::make_unique<YAMLParserImpl>(Buf, StrTabBuf)) {}
+
 Parser::~Parser() = default;
 
 static Expected<const Remark *> getNextYAML(YAMLParserImpl &Impl) {
   YAMLRemarkParser &YAMLParser = Impl.YAMLParser;
   // Check for EOF.
   if (Impl.YAMLIt == Impl.YAMLParser.Stream.end())
     return nullptr;
 

 }
 
 Expected<const Remark *> Parser::getNext() const {
   if (auto *Impl = dyn_cast<YAMLParserImpl>(this->Impl.get()))
     return getNextYAML(*Impl);
   llvm_unreachable("Get next called with an unknown parsing implementation.");
 }
 
+ParsedStringTable::ParsedStringTable(StringRef InBuffer) : Buffer(InBuffer) {
+  while (!InBuffer.empty()) {
+    // Strings are separated by '\0' bytes.
+    std::pair<StringRef, StringRef> Split = InBuffer.split('\0');
+    // We only store the offset from the beginning of the buffer.
+    Offsets.push_back(Split.first.data() - Buffer.data());
+    InBuffer = Split.second;
+  }
+}
+
+Expected<StringRef> ParsedStringTable::operator[](size_t Index) {
+  if (Index >= Offsets.size())
+    return createStringError(
+        std::make_error_code(std::errc::invalid_argument),
+        "String with index %u is out of bounds (size = %u).", Index,
+        Offsets.size());
+
+  size_t Offset = Offsets[Index];
+  // If it's the last offset, we can't use the next offset to know the size of
+  // the string.
+  size_t NextOffset =
+      (Index == Offsets.size() - 1) ? Buffer.size() : Offsets[Index + 1];
+  return StringRef(Buffer.data() + Offset, NextOffset - Offset - 1);
+}
+
 // Create wrappers for C Binding types (see CBindingWrapping.h).
 DEFINE_SIMPLE_CONVERSION_FUNCTIONS(remarks::Parser, LLVMRemarkParserRef)
 
 extern "C" LLVMRemarkParserRef LLVMRemarkParserCreateYAML(const void *Buf,
                                                           uint64_t Size) {
   return wrap(
       new remarks::Parser(StringRef(static_cast<const char *>(Buf), Size)));
 }

llvm/trunk/lib/Remarks/RemarkStringTable.cpp

+//===- RemarkStringTable.cpp ----------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of the Remark string table used at remark generation.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Remarks/RemarkStringTable.h"
+#include "llvm/Support/EndianStream.h"
+#include "llvm/Support/Error.h"
+#include <vector>
+
+using namespace llvm;
+using namespace llvm::remarks;
+
+std::pair<unsigned, StringRef> StringTable::add(StringRef Str) {
+  size_t NextID = StrTab.size();
+  auto KV = StrTab.insert({Str, NextID});
+  // If it's a new string, add it to the final size.
+  if (KV.second)
+    SerializedSize += KV.first->first().size() + 1; // +1 for the '\0'
+  // Can be either NextID or the previous ID if the string is already there.
+  return {KV.first->second, KV.first->first()};
+}
+
+void StringTable::serialize(raw_ostream &OS) const {
+  // Emit the number of strings.
+  uint64_t StrTabSize = SerializedSize;
+  support::endian::write(OS, StrTabSize, support::little);
+  // Emit the sequence of strings.
+  for (StringRef Str : serialize()) {
+    OS << Str;
+    // Explicitly emit a '\0'.
+    OS.write('\0');
+  }
+}
+
+std::vector<StringRef> StringTable::serialize() const {
+  std::vector<StringRef> Strings{StrTab.size()};
+  for (const auto &KV : StrTab)
+    Strings[KV.second] = KV.first();
+  return Strings;
+}

llvm/trunk/lib/Remarks/YAMLRemarkParser.h

 
 #ifndef LLVM_REMARKS_YAML_REMARK_PARSER_H
 #define LLVM_REMARKS_YAML_REMARK_PARSER_H
 
 #include "RemarkParserImpl.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Remarks/Remark.h"
+#include "llvm/Remarks/RemarkParser.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/YAMLParser.h"
 #include "llvm/Support/YAMLTraits.h"
 #include "llvm/Support/raw_ostream.h"
 #include <string>
 
 namespace llvm {
 namespace remarks {
 /// Parses and holds the state of the latest parsed remark.
 struct YAMLRemarkParser {
   /// Source manager for better error messages.
   SourceMgr SM;
   /// Stream for yaml parsing.
   yaml::Stream Stream;
   /// Storage for the error stream.
   std::string ErrorString;
   /// The error stream.
   raw_string_ostream ErrorStream;
   /// Temporary parsing buffer for the arguments.
   SmallVector<Argument, 8> TmpArgs;
-
+  /// The string table used for parsing strings.
+  Optional<ParsedStringTable> StrTab;
   /// The state used by the parser to parse a remark entry. Invalidated with
   /// every call to `parseYAMLElement`.
   struct ParseState {
     /// Temporary parsing buffer for the arguments.
     /// The parser itself is owning this buffer in order to reduce the number of
     /// allocations.
     SmallVectorImpl<Argument> &Args;
     Remark TheRemark;
 
     ParseState(SmallVectorImpl<Argument> &Args) : Args(Args) {}
     /// Use Args only as a **temporary** buffer.
     ~ParseState() { Args.clear(); }
   };
 
   /// The current state of the parser. If the parsing didn't start yet, it will
   /// not be containing any value.
   Optional<ParseState> State;
 
-  YAMLRemarkParser(StringRef Buf)
+  YAMLRemarkParser(StringRef Buf, Optional<StringRef> StrTabBuf = None)
       : SM(), Stream(Buf, SM), ErrorString(), ErrorStream(ErrorString),
-        TmpArgs() {
+        TmpArgs(), StrTab() {
     SM.setDiagHandler(YAMLRemarkParser::HandleDiagnostic, this);
+
+    if (StrTabBuf)
+      StrTab.emplace(*StrTabBuf);
   }
 
   /// Parse a YAML element.
   Error parseYAMLElement(yaml::Document &Remark);
 
 private:
   /// Parse one key to a string.
   /// otherwise.

 struct YAMLParserImpl : public ParserImpl {
   /// The object parsing the YAML.
   YAMLRemarkParser YAMLParser;
   /// Iterator in the YAML stream.
   yaml::document_iterator YAMLIt;
   /// Set to `true` if we had any errors during parsing.
   bool HasErrors = false;
 
-  YAMLParserImpl(StringRef Buf)
-      : ParserImpl{ParserImpl::Kind::YAML}, YAMLParser(Buf),
+  YAMLParserImpl(StringRef Buf, Optional<StringRef> StrTabBuf = None)
+      : ParserImpl{ParserImpl::Kind::YAML}, YAMLParser(Buf, StrTabBuf),
         YAMLIt(YAMLParser.Stream.begin()), HasErrors(false) {}
 
   static bool classof(const ParserImpl *PI) {
     return PI->ParserKind == ParserImpl::Kind::YAML;
   }
 };
 } // end namespace remarks
 } // end namespace llvm
 
 #endif /* LLVM_REMARKS_YAML_REMARK_PARSER_H */

llvm/trunk/lib/Remarks/YAMLRemarkParser.cpp

Error YAMLRemarkParser::parseKey(StringRef &Result, yaml::KeyValueNode &Node) {
   return make_error<YAMLParseError>("key is not a string.", Node);
 }
 
 template <typename T>
 Error YAMLRemarkParser::parseStr(T &Result, yaml::KeyValueNode &Node) {
   auto *Value = dyn_cast<yaml::ScalarNode>(Node.getValue());
   if (!Value)
     return make_error<YAMLParseError>("expected a value of scalar type.", Node);
-  StringRef Tmp = Value->getRawValue();
+  StringRef Tmp;
+  if (!StrTab) {
+    Tmp = Value->getRawValue();
+  } else {
+    // If we have a string table, parse it as an unsigned.
+    unsigned StrID = 0;
+    if (Error E = parseUnsigned(StrID, Node))
+      return E;
+    if (Expected<StringRef> Str = (*StrTab)[StrID])
+      Tmp = *Str;
+    else
+      return Str.takeError();
+  }
 
   if (Tmp.front() == '\'')
     Tmp = Tmp.drop_front();
 
   if (Tmp.back() == '\'')
     Tmp = Tmp.drop_back();
 
   Result = Tmp;

llvm/trunk/test/CodeGen/X86/remarks-section.ll

 ; RUN: llc < %s -mtriple=x86_64-linux -remarks-section -pass-remarks-output=%/t.yaml | FileCheck -DPATH=%/t.yaml %s
 ; RUN: llc < %s -mtriple=x86_64-darwin -remarks-section -pass-remarks-output=%/t.yaml | FileCheck --check-prefix=CHECK-DARWIN -DPATH=%/t.yaml %s
+; RUN: llc < %s -mtriple=x86_64-darwin -remarks-section -remarks-yaml-string-table -pass-remarks-output=%/t.yaml | FileCheck --check-prefix=CHECK-DARWIN-STRTAB -DPATH=%/t.yaml %s
 
 ; CHECK-LABEL: func1:
 
 ; CHECK: .section .remarks,"e",@progbits
 ; The magic number:
 ; CHECK-NEXT: .ascii "REMARKS"
 ; Null-terminator:
 ; CHECK-NEXT: .byte 0
 ; The version:
 ; CHECK-NEXT: .byte 0x00, 0x00, 0x00, 0x00
 ; CHECK-NEXT: .byte 0x00, 0x00, 0x00, 0x00
+; The string table size:
+; CHECK-NEXT: .byte 0x00, 0x00, 0x00, 0x00
+; CHECK-NEXT: .byte 0x00, 0x00, 0x00, 0x00
+; The string table:
+; EMPTY
 ; The remark file path:
 ; CHECK-NEXT: .ascii "[[PATH]]"
 ; Null-terminator:
 ; CHECK-NEXT: .byte 0
 
 ; CHECK-DARWIN: .section __LLVM,__remarks,regular,debug
 ; The magic number:
 ; CHECK-DARWIN-NEXT: .ascii "REMARKS"
 ; Null-terminator:
 ; CHECK-DARWIN-NEXT: .byte 0
 ; The version:
 ; CHECK-DARWIN-NEXT: .byte 0x00, 0x00, 0x00, 0x00
 ; CHECK-DARWIN-NEXT: .byte 0x00, 0x00, 0x00, 0x00
+; The string table size:
+; CHECK-DARWIN-NEXT: .byte 0x00, 0x00, 0x00, 0x00
+; CHECK-DARWIN-NEXT: .byte 0x00, 0x00, 0x00, 0x00
+; The string table:
+; EMPTY
 ; The remark file path:
 ; CHECK-DARWIN-NEXT: .ascii "[[PATH]]"
 ; Null-terminator:
 ; CHECK-DARWIN-NEXT: .byte 0
+
+; CHECK-DARWIN-STRTAB: .section __LLVM,__remarks,regular,debug
+; The magic number:
+; CHECK-DARWIN-STRTAB-NEXT: .ascii "REMARKS"
+; Null-terminator:
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; The version:
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0x00, 0x00, 0x00, 0x00
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0x00, 0x00, 0x00, 0x00
+; The size of the string table:
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0x71, 0x00, 0x00, 0x00
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0x00, 0x00, 0x00, 0x00
+; The string table:
+; CHECK-DARWIN-STRTAB-NEXT: .ascii "prologepilog"
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; CHECK-DARWIN-STRTAB-NEXT: .ascii "StackSize"
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; CHECK-DARWIN-STRTAB-NEXT: .ascii "func1"
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; CHECK-DARWIN-STRTAB-NEXT: .byte 48
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; CHECK-DARWIN-STRTAB-NEXT: .ascii " stack bytes in function"
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; CHECK-DARWIN-STRTAB-NEXT: .ascii "asm-printer"
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; CHECK-DARWIN-STRTAB-NEXT: .ascii "InstructionCount"
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; CHECK-DARWIN-STRTAB-NEXT: .byte 49
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; CHECK-DARWIN-STRTAB-NEXT: .ascii " instructions in function"
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
+; The remark file path:
+; CHECK-DARWIN-STRTAB-NEXT: .ascii "[[PATH]]"
+; Null-terminator:
+; CHECK-DARWIN-STRTAB-NEXT: .byte 0
 define void @func1() {
   ret void
 }

llvm/trunk/unittests/Remarks/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Remarks
   Support
   )
 
 add_llvm_unittest(RemarksTests
+  RemarksStrTabParsingTest.cpp
   YAMLRemarksParsingTest.cpp
   )

llvm/trunk/unittests/Remarks/RemarksStrTabParsingTest.cpp

+//===- unittest/Support/RemarksStrTabParsingTest.cpp - StrTab tests -------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Remarks/Remark.h"
+#include "llvm/Remarks/RemarkParser.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+TEST(RemarksStrTab, ParsingEmpty) {
+  StringRef Empty("", 0);
+  remarks::ParsedStringTable StrTab(Empty);
+  Expected<StringRef> Nothing = StrTab[0];
+  EXPECT_FALSE(static_cast<bool>(Nothing));
+  EXPECT_EQ(toString(Nothing.takeError()),
+            "String with index 0 is out of bounds (size = 0).");
+}
+
+TEST(RemarksStrTab, ParsingGood) {
+  StringRef Strings("str1\0str2\0str3\0str4", 20);
+  remarks::ParsedStringTable StrTab(Strings);
+  Expected<StringRef> Result = StrTab[0];
+  EXPECT_TRUE(static_cast<bool>(Result));
+  EXPECT_EQ(*Result, "str1");
+  Result = StrTab[1];
+  EXPECT_TRUE(static_cast<bool>(Result));
+  EXPECT_EQ(*Result, "str2");
+  Result = StrTab[2];
+  EXPECT_TRUE(static_cast<bool>(Result));
+  EXPECT_EQ(*Result, "str3");
+  Result = StrTab[3];
+  EXPECT_TRUE(static_cast<bool>(Result));
+  EXPECT_EQ(*Result, "str4");
+}

llvm/trunk/unittests/Remarks/YAMLRemarksParsingTest.cpp

do {
     ++ArgID;
   } while ((Arg = LLVMRemarkEntryGetNextArg(Arg, Remark)));
 
   EXPECT_EQ(LLVMRemarkParserGetNext(Parser), nullptr);
 
   EXPECT_FALSE(LLVMRemarkParserHasError(Parser));
   LLVMRemarkParserDispose(Parser);
 }
+
+TEST(YAMLRemarks, ContentsStrTab) {
+  StringRef Buf = "\n"
+                  "--- !Missed\n"
+                  "Pass: 0\n"
+                  "Name: 1\n"
+                  "DebugLoc: { File: 2, Line: 3, Column: 12 }\n"
+                  "Function: 3\n"
+                  "Hotness: 4\n"
+                  "Args:\n"
+                  "  - Callee: 5\n"
+                  "  - String: 7\n"
+                  "  - Caller: 3\n"
+                  "    DebugLoc: { File: 2, Line: 2, Column: 0 }\n"
+                  "  - String: 8\n"
+                  "\n";
+
+  StringRef StrTabBuf =
+      StringRef("inline\0NoDefinition\0file.c\0foo\0Callee\0bar\0String\0 "
+                "will not be inlined into \0 because its definition is "
+                "unavailable",
+                115);
+
+  remarks::Parser Parser(Buf, StrTabBuf);
+  Expected<const remarks::Remark *> RemarkOrErr = Parser.getNext();
+  EXPECT_FALSE(errorToBool(RemarkOrErr.takeError()));
+  EXPECT_TRUE(*RemarkOrErr != nullptr);
+
+  const remarks::Remark &Remark = **RemarkOrErr;
+  EXPECT_EQ(Remark.RemarkType, remarks::Type::Missed);
+  EXPECT_EQ(checkStr(Remark.PassName, 6), "inline");
+  EXPECT_EQ(checkStr(Remark.RemarkName, 12), "NoDefinition");
+  EXPECT_EQ(checkStr(Remark.FunctionName, 3), "foo");
+  EXPECT_TRUE(Remark.Loc);
+  const remarks::RemarkLocation &RL = *Remark.Loc;
+  EXPECT_EQ(checkStr(RL.SourceFilePath, 6), "file.c");
+  EXPECT_EQ(RL.SourceLine, 3U);
+  EXPECT_EQ(RL.SourceColumn, 12U);
+  EXPECT_TRUE(Remark.Hotness);
+  EXPECT_EQ(*Remark.Hotness, 4U);
+  EXPECT_EQ(Remark.Args.size(), 4U);
+
+  unsigned ArgID = 0;
+  for (const remarks::Argument &Arg : Remark.Args) {
+    switch (ArgID) {
+    case 0:
+      EXPECT_EQ(checkStr(Arg.Key, 6), "Callee");
+      EXPECT_EQ(checkStr(Arg.Val, 3), "bar");
+      EXPECT_FALSE(Arg.Loc);
+      break;
+    case 1:
+      EXPECT_EQ(checkStr(Arg.Key, 6), "String");
+      EXPECT_EQ(checkStr(Arg.Val, 26), " will not be inlined into ");
+      EXPECT_FALSE(Arg.Loc);
+      break;
+    case 2: {
+      EXPECT_EQ(checkStr(Arg.Key, 6), "Caller");
+      EXPECT_EQ(checkStr(Arg.Val, 3), "foo");
+      EXPECT_TRUE(Arg.Loc);
+      const remarks::RemarkLocation &RL = *Arg.Loc;
+      EXPECT_EQ(checkStr(RL.SourceFilePath, 6), "file.c");
+      EXPECT_EQ(RL.SourceLine, 2U);
+      EXPECT_EQ(RL.SourceColumn, 0U);
+      break;
+    }
+    case 3:
+      EXPECT_EQ(checkStr(Arg.Key, 6), "String");
+      EXPECT_EQ(checkStr(Arg.Val, 38),
+                " because its definition is unavailable");
+      EXPECT_FALSE(Arg.Loc);
+      break;
+    default:
+      break;
+    }
+    ++ArgID;
+  }
+
+  RemarkOrErr = Parser.getNext();
+  EXPECT_FALSE(errorToBool(RemarkOrErr.takeError()));
+  EXPECT_EQ(*RemarkOrErr, nullptr);
+}
+
+TEST(YAMLRemarks, ParsingBadStringTableIndex) {
+  StringRef Buf = "\n"
+                  "--- !Missed\n"
+                  "Pass: 50\n"
+                  "\n";
+
+  StringRef StrTabBuf = StringRef("inline");
+
+  remarks::Parser Parser(Buf, StrTabBuf);
+  Expected<const remarks::Remark *> Remark = Parser.getNext();
+  EXPECT_FALSE(Remark); // Expect an error here.
+
+  std::string ErrorStr;
+  raw_string_ostream Stream(ErrorStr);
+  handleAllErrors(Remark.takeError(),
+                  [&](const ErrorInfoBase &EIB) { EIB.log(Stream); });
+  EXPECT_TRUE(
+      StringRef(Stream.str())
+          .contains("String with index 50 is out of bounds (size = 1)."));
+}