[ThinLTO] Bitcode reading/writing support for ThinLTO function summary/index

[tejohnson]

Summary

This patch adds bitcode reading/writing support for the ThinLTO function summary/index in bitcode. Some of the support is currently stubbed out (e.g. the records within the ThinLTO blocks), pending comments on the associated file format RFC.

The ThinLTO data structures are defined in http://reviews.llvm.org/D11721.

Related RFCs:
RFC: ThinLTO File Format (http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-August/088947.html)
RFC: ThinLTO File API and Data Structures (http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-August/088951.html)

[tejohnson]

Updated the patch to use the parameter defined under -fthinlto in pending patch http://reviews.llvm.org/D11907. Added the same reviewers to this patch.

[reames]

Can you add references to the relevant RFCs to the review descriptions? It's getting hard to track all the pieces. My main comments can be found in the linked review for the data structures.

include/llvm/Bitcode/ReaderWriter.h

69

As a general comment: this index really isn't a ThinkLTO*Index, it's a *Index for the bitcode that happens to be used for LTO. The naming of the various methods and comments need to reflect that.

[tejohnson]

In D11722#223090, @reames wrote:

Can you add references to the relevant RFCs to the review descriptions? It's getting hard to track all the pieces. My main comments can be found in the linked review for the data structures.

Will do.

include/llvm/Bitcode/ReaderWriter.h

69

I responded to this suggestion in the review for D11721 as well - I didn't think this information would be used outside of ThinLTO importing decisions/mechanics. So thought it was better to name it accordingly. I'm open to changing the name, which currently also matches the names of the proposed bitcode sections.

[tejohnson]

Removed native object wrapper support from this patch.

[davidxl]

include/llvm/Bitcode/ReaderWriter.h

72

Add a comment here to make it clear that lazy summary parsing is needed for reading combined index in the function import phase.

76

Make the comment clearer that:

1. When reading combined index (ThinLTOSummaryIndex), getThinLTOIndex is first called with ParseFuncSummary=false
2. The method supports lazily reading Function summary data associated for the function specified by the function name.

77

Should it really be 'readThinLTOFunctionSummary'?

lib/Bitcode/Reader/BitcodeReader.cpp

425

parseBitcodeInto sounds too generic. Perhaps parseSummaryIndex?

427

Is it better to call it 'parseFunctionSummary'? Also move this interface decl after parseThinLTOSummary() below to show their order in the parsing hierarchy.

431

Do these parsing interfaces need to be public, other than the top level parseBitcodeInto and the lazy reading parseFunction?

433

Is it clearer to call it

parseThinLTOSummaries or parseThinLTOSummaryBlock?

437

parseBitCodeInto is a top level interface which is basically a wrapper to parseModule after seeking to the start of module block -- so it seems that parseModule can be inlined into parseBitcodeInto to avoid confusion.

4865

Add comment about the purpose of the function.

4931

Reorder this case to reflect the physical order of block ids on disk?

5116

It is more readable to have a helper function to do 'seekToModuleStart' which includes the loop, and move the parseModule outside of it.

5409

Suggested comment:

Otherwise skip the function summary section, but only create an index object with a map from function name to function summary offset. The index is used to perform lazy function summary reading later.

5464

FunctionSummaryOffset?

[tejohnson]

Responses and some other comments below. New patch being uploaded shortly.

include/llvm/Bitcode/ReaderWriter.h

77

Yes, changed.

lib/Bitcode/Reader/BitcodeReader.cpp

425

Since it mirrors BitcodeReader::parseBitcodeInto, I will change this to parseSummaryIndexInto.

427

Changed the name. Can't move after parseThinLTOSummary since this one needs to be public and I am making the other one private (see below). Instead added a comment about it being used to read a function summary entry lazily.

431

Moved all of these parseThinLTO* routines into the private section.

433

Changed to parseEntireThinLTOSummary.

437

I prefer to keep the current division as it mirrors how parseBitcodeInto/parseModule are structured in the normal BilcodeReader.

5116

I purposely structured this the same way as the corresponding BitcodeReader::parseBitcodeInto() function.

5384

Inlined into getThinLTOIndex since that was the only caller.

5419

Inlined into hasThinLTOIndex since that was the only caller.

5445

Inlined into readThinLTOFunctionInfo since that was the only caller.

5458

I have replaced this TODO with the code.

[tejohnson]

Changes based on review David's review comments. I also added lots of other comments, and replaced a TODO in readThinLTOFunctionSummary to actually walk through the infos for a function name and access the saved summary offset.

[tejohnson]

Obsolete. New patch is http://reviews.llvm.org/D13107

include/llvm/Bitcode/LLVMBitCodes.h

enum BlockIDs {
     UNUSED_ID1,
 
     VALUE_SYMTAB_BLOCK_ID,
     METADATA_BLOCK_ID,
     METADATA_ATTACHMENT_ID,
 
     TYPE_BLOCK_ID_NEW,
 
-    USELIST_BLOCK_ID
+    USELIST_BLOCK_ID,
+
+    THINLTO_BLOCK_ID,
+
+    // ThinLTO sub-block id's.
+    THINLTO_SYMTAB_BLOCK_ID,
+    THINLTO_MODULE_STRTAB_BLOCK_ID,
+    THINLTO_FUNCTION_SUMMARY_BLOCK_ID
   };
 
 
   /// MODULE blocks have a number of optional fields and subblocks.
   enum ModuleCodes {
     MODULE_CODE_VERSION     = 1,    // VERSION:     [version#]
     MODULE_CODE_TRIPLE      = 2,    // TRIPLE:      [strchr x N]
     MODULE_CODE_DATALAYOUT  = 3,    // DATALAYOUT:  [strchr x N]

include/llvm/Bitcode/ReaderWriter.h

 // This header defines interfaces to read and write LLVM bitcode files/streams.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_BITCODE_READERWRITER_H
 #define LLVM_BITCODE_READERWRITER_H
 
 #include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/IR/ThinLTOInfo.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <memory>
 #include <string>
 
 namespace llvm {
   class BitstreamWriter;
namespace llvm {
   getBitcodeTargetTriple(MemoryBufferRef Buffer, LLVMContext &Context,
                          DiagnosticHandlerFunction DiagnosticHandler = nullptr);
 
   /// Read the specified bitcode file, returning the module.
   ErrorOr<std::unique_ptr<Module>>
   parseBitcodeFile(MemoryBufferRef Buffer, LLVMContext &Context,
                    DiagnosticHandlerFunction DiagnosticHandler = nullptr);
 
+  /// Check if the given bitcode buffer contains a ThinLTO block.
+  bool hasThinLTOIndex(MemoryBufferRef Buffer, LLVMContext &Context,
+                       DiagnosticHandlerFunction DiagnosticHandler);
+
+  /// Parse the specified bitcode buffer, returning the ThinLTO index.
+  /// If ParseFuncSummary is true, parse the entire function summary into
+  /// the index. Otherwise skip the function summary section, and only create
+  /// an index object with a map from function name to function summary offset.
+  /// The index is used to perform lazy function summary reading later.
+  ErrorOr<std::unique_ptr<ThinLTOFunctionSummaryIndex>> getThinLTOIndex(
+      MemoryBufferRef Buffer, LLVMContext &Context,
+      DiagnosticHandlerFunction DiagnosticHandler,
+      bool ParseFuncSummary = true);
+
+  /// This method supports lazy reading of function summary data from
+  /// the combined index during function importing. When reading the combined
+  /// index file, getThinLTOIndex is first invoked with ParseFuncSummary=false.
+  /// Then this method is called for each function considered for importing,
+  /// to parse the summary information for the given function name into
+  /// the index.
+  std::error_code readThinLTOFunctionSummary(
+      MemoryBufferRef Buffer, LLVMContext &Context,
+      DiagnosticHandlerFunction DiagnosticHandler, StringRef FunctionName,
+      std::unique_ptr<ThinLTOFunctionSummaryIndex> Index);
+
   /// \brief Write the specified module to the specified raw output stream.
   ///
   /// For streams where it matters, the given stream should be in "binary"
   /// mode.
   ///
   /// If \c ShouldPreserveUseListOrder, encode the use-list order for each \a
   /// Value in \c M.  These will be reconstructed exactly when \a M is
   /// deserialized.
   void WriteBitcodeToFile(const Module *M, raw_ostream &Out,
                           bool ShouldPreserveUseListOrder = false);
 
+  // Write the specified ThinLTO index to the given raw output stream,
+  // where it will be written in a new bitcode block. This is used when
+  // writing the combined index file.
+  void WriteThinLTOToFile(const ThinLTOFunctionSummaryIndex *Index,
+                          raw_ostream &Out);
+
   /// isBitcodeWrapper - Return true if the given bytes are the magic bytes
   /// for an LLVM IR bitcode wrapper.
   ///
   inline bool isBitcodeWrapper(const unsigned char *BufPtr,
                                const unsigned char *BufEnd) {
     // See if you can find the hidden message in the magic bytes :-).
     // (Hint: it's a little-endian encoding.)
     return BufPtr != BufEnd &&

lib/Bitcode/Reader/BitcodeReader.cpp

 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/IR/GVMaterializer.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/IR/Operator.h"
+#include "llvm/IR/ThinLTOInfo.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/DataStream.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 #include <deque>
 using namespace llvm;
private:
   std::error_code parseUseLists();
   std::error_code initStream(std::unique_ptr<DataStreamer> Streamer);
   std::error_code initStreamFromBuffer();
   std::error_code initLazyStream(std::unique_ptr<DataStreamer> Streamer);
   std::error_code findFunctionInStream(
       Function *F,
       DenseMap<Function *, uint64_t>::iterator DeferredFunctionInfoIterator);
 };
+
+// Class to manage readig and parsing ThinLTO bitcode files/sections.
+class ThinLTOBitcodeReader {
+  LLVMContext &Context;
+  DiagnosticHandlerFunction DiagnosticHandler;
+  ThinLTOFunctionSummaryIndex *TheIndex = nullptr;
+  std::unique_ptr<MemoryBuffer> Buffer;
+  std::unique_ptr<BitstreamReader> StreamFile;
+  BitstreamCursor Stream;
+  uint64_t NextUnreadBit = 0;
+  bool SeenValueSymbolTable = false;
+  bool SeenThinLTO = false;
+  bool ParseFuncSummaryData = true;
+  bool CheckThinLTOPresenceOnly = false;
+  bool BufferContainsFuncSummaryDataOnly = false;
+  // Map built from the ThinLTO-specific value symbol table parser,
+  // which holds mapping from the value ID to the name, since the ThinLTO
+  // symbol table references the value ID for function names.
+  StringMap<unsigned> ValueSymtab;
+
+public:
+  std::error_code error(BitcodeError E, const Twine &Message);
+  std::error_code error(BitcodeError E);
+  std::error_code error(const Twine &Message);
+
+  ThinLTOBitcodeReader(MemoryBuffer *Buffer, LLVMContext &Context,
+                       DiagnosticHandlerFunction DiagnosticHandler,
+                       bool ParseFuncSummary = true,
+                       bool CheckPresenceOnly = false);
+  ThinLTOBitcodeReader(LLVMContext &Context,
+                       DiagnosticHandlerFunction DiagnosticHandler,
+                       bool ParseFuncSummary = true,
+                       bool CheckPresenceOnly = false);
+  ~ThinLTOBitcodeReader() { freeState(); }
+
+  void freeState();
+
+  void releaseBuffer();
+
+  bool foundThinLTO() {
+    return SeenThinLTO;
+  }
+
+  /// \brief Main interface to parsing a bitcode buffer.
+  /// \returns true if an error occurred.
+  std::error_code parseSummaryIndexInto(std::unique_ptr<DataStreamer> Streamer,
+                                        ThinLTOFunctionSummaryIndex *I);
+
+  /// \brief Interface for parsing a function summary lazily.
+  std::error_code parseFunctionSummary(std::unique_ptr<DataStreamer> Streamer,
+                                       ThinLTOFunctionSummaryIndex *I,
+                                       size_t FunctionSummaryOffset);
+
+private:
+  std::error_code parseModule();
+  std::error_code parseValueSymbolTable();
+  std::error_code parseThinLTOBlock();
+  std::error_code parseThinLTOSymtab();
+  std::error_code parseEntireThinLTOSummary();
+  std::error_code parseThinLTOModuleStringTable();
+  std::error_code initStream(std::unique_ptr<DataStreamer> Streamer);
+  std::error_code initStreamFromBuffer();
+  std::error_code initLazyStream(std::unique_ptr<DataStreamer> Streamer);
+};
 } // namespace
 
 BitcodeDiagnosticInfo::BitcodeDiagnosticInfo(std::error_code EC,
                                              DiagnosticSeverity Severity,
                                              const Twine &Msg)
     : DiagnosticInfo(DK_Bitcode, Severity), Msg(Msg), EC(EC) {}
 
 void BitcodeDiagnosticInfo::print(DiagnosticPrinter &DP) const { DP << Msg; }
if (isBitcodeWrapper(buf, buf + 4)) {
     const unsigned char *bitcodeEnd = buf + 16;
     SkipBitcodeWrapperHeader(bitcodeStart, bitcodeEnd, false);
     Bytes.dropLeadingBytes(bitcodeStart - buf);
     Bytes.setKnownObjectSize(bitcodeEnd - bitcodeStart);
   }
   return std::error_code();
 }
 
+std::error_code ThinLTOBitcodeReader::error(BitcodeError E,
+                                            const Twine &Message) {
+  return ::error(DiagnosticHandler, make_error_code(E), Message);
+}
+
+std::error_code ThinLTOBitcodeReader::error(const Twine &Message) {
+  return ::error(DiagnosticHandler,
+                 make_error_code(BitcodeError::CorruptedBitcode), Message);
+}
+
+std::error_code ThinLTOBitcodeReader::error(BitcodeError E) {
+  return ::error(DiagnosticHandler, make_error_code(E));
+}
+
+ThinLTOBitcodeReader::ThinLTOBitcodeReader(
+    MemoryBuffer *Buffer, LLVMContext &Context,
+    DiagnosticHandlerFunction DiagnosticHandler,
+    bool ParseFuncSummary, bool CheckPresenceOnly)
+    : Context(Context),
+      DiagnosticHandler(getDiagHandler(DiagnosticHandler, Context)),
+      Buffer(Buffer),
+      ParseFuncSummaryData(ParseFuncSummary),
+      CheckThinLTOPresenceOnly(CheckPresenceOnly) {}
+
+ThinLTOBitcodeReader::ThinLTOBitcodeReader(LLVMContext &Context,
+                             DiagnosticHandlerFunction DiagnosticHandler,
+                             bool ParseFuncSummary, bool CheckPresenceOnly)
+    : Context(Context),
+      DiagnosticHandler(getDiagHandler(DiagnosticHandler, Context)),
+      Buffer(nullptr),
+      ParseFuncSummaryData(ParseFuncSummary),
+      CheckThinLTOPresenceOnly(CheckPresenceOnly) {}
+
+void ThinLTOBitcodeReader::freeState() {
+  Buffer = nullptr;
+}
+
+void ThinLTOBitcodeReader::releaseBuffer() { Buffer.release(); }
+
+// Specialized value symbol table parser used when reading ThinLTO
+// blocks where we don't actually create global values. This builds a
+// map from the value ID to the name, since the ThinLTO symbol table
+// references the value ID for function names.
+std::error_code ThinLTOBitcodeReader::parseValueSymbolTable() {
+  if (Stream.EnterSubBlock(bitc::VALUE_SYMTAB_BLOCK_ID))
+    return error("Invalid record");
+
+  SmallVector<uint64_t, 64> Record;
+
+  // Read all the records for this value table.
+  SmallString<128> ValueName;
+  while (1) {
+    BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
+
+    switch (Entry.Kind) {
+    case BitstreamEntry::SubBlock: // Handled for us already.
+    case BitstreamEntry::Error:
+      return error("Malformed block");
+    case BitstreamEntry::EndBlock:
+      return std::error_code();
+    case BitstreamEntry::Record:
+      // The interesting case.
+      break;
+    }
+
+    // Read a record.
+    Record.clear();
+    switch (Stream.readRecord(Entry.ID, Record)) {
+      default:  // Default behavior: ignore (e.g. VST_CODE_BBENTRY records).
+        break;
+      case bitc::VST_CODE_ENTRY: {  // VST_ENTRY: [valueid, namechar x N]
+        if (convertToString(Record, 1, ValueName))
+          return error("Invalid record");
+        unsigned ValueID = Record[0];
+        ValueSymtab.insert(std::make_pair(
+            StringRef(ValueName.data(), ValueName.size()), ValueID));
+        ValueName.clear();
+        break;
+      }
+    }
+  }
+}
+
+// Parse just the blocks needed for ThinLTO index building out of the module.
+std::error_code ThinLTOBitcodeReader::parseModule() {
+  if (Stream.EnterSubBlock(bitc::MODULE_BLOCK_ID))
+    return error("Invalid record");
+
+  // Read the ThinLTO records for this module.
+  while (1) {
+    BitstreamEntry Entry = Stream.advance();
+
+    switch (Entry.Kind) {
+    case BitstreamEntry::Error:
+      return error("Malformed block");
+    case BitstreamEntry::EndBlock:
+      return std::error_code();
+
+    case BitstreamEntry::SubBlock:
+      switch (Entry.ID) {
+      default:  // Skip unknown content.
+        if (Stream.SkipBlock())
+          return error("Invalid record");
+        break;
+      case bitc::BLOCKINFO_BLOCK_ID:
+        // Need to parse these to get abbrev ids (e.g. for VST)
+        if (Stream.ReadBlockInfoBlock())
+          return error("Malformed block");
+        break;
+      case bitc::VALUE_SYMTAB_BLOCK_ID:
+        assert(!SeenValueSymbolTable);
+        SeenValueSymbolTable = true;
+        if (CheckThinLTOPresenceOnly) {
+          if (Stream.SkipBlock())
+            return error("Invalid record");
+        }
+        else if (std::error_code EC = parseValueSymbolTable())
+          return EC;
+        break;
+      case bitc::THINLTO_BLOCK_ID:
+        assert(SeenValueSymbolTable);
+        SeenThinLTO = true;
+        if (CheckThinLTOPresenceOnly) {
+          if (Stream.SkipBlock())
+            return error("Invalid record");
+        }
+        else if (std::error_code EC = parseThinLTOBlock())
+          return EC;
+        break;
+      }
+      continue;
+
+    case BitstreamEntry::Record:
+      Stream.skipRecord(Entry.ID);
+      continue;
+    }
+  }
+}
+
+// This will parse the top level ThinLTO block residing in the module block.
+// At the end of this routine the ThinLTO Index is populated with a map
+// from function name to ThinLTOFunctionInfo. The function info contains
+// either the parsed function summary information (when parsing summaries
+// eagerly), or just to the function's offset within the summary section
+// if parsing lazily (!ParseFuncSummaryData).
+std::error_code ThinLTOBitcodeReader::parseThinLTOBlock() {
+  if (Stream.EnterSubBlock(bitc::THINLTO_BLOCK_ID))
+    return error("Invalid record");
+
+  while (1) {
+    BitstreamEntry Entry = Stream.advance();
+
+    switch (Entry.Kind) {
+    case BitstreamEntry::Error:
+      return error("Malformed block");
+    case BitstreamEntry::EndBlock:
+      return std::error_code();
+
+    case BitstreamEntry::SubBlock:
+      switch (Entry.ID) {
+      default:  // Skip unknown content.
+        if (Stream.SkipBlock())
+          return error("Invalid record");
+        break;
+      case bitc::THINLTO_SYMTAB_BLOCK_ID:
+        if (std::error_code EC = parseThinLTOSymtab())
+          return EC;
+        break;
+      case bitc::THINLTO_FUNCTION_SUMMARY_BLOCK_ID:
+        if (!ParseFuncSummaryData) {
+          // Lazy parsing of summary info, skip it.
+          if (Stream.SkipBlock())
+            return error("Invalid record");
+        }
+        else if (std::error_code EC = parseEntireThinLTOSummary())
+          return EC;
+        break;
+      case bitc::THINLTO_MODULE_STRTAB_BLOCK_ID:
+        if (std::error_code EC = parseThinLTOModuleStringTable())
+          return EC;
+        break;
+      }
+      continue;
+
+    // TODO: Add ThinLTO version number record.
+    case BitstreamEntry::Record:
+      return error("Invalid record");
+    }
+  }
+  llvm_unreachable("Exit infinite loop");
+}
+
+// Parse the ThinLTO symbol table block which contains the mapping from
+// function name (via the VST index) to the function's summary within
+// the summary section.
+std::error_code ThinLTOBitcodeReader::parseThinLTOSymtab() {
+  if (Stream.EnterSubBlock(bitc::THINLTO_SYMTAB_BLOCK_ID))
+    return error("Invalid record");
+
+  SmallVector<uint64_t, 64> Record;
+
+  while (1) {
+    BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
+
+    switch (Entry.Kind) {
+    case BitstreamEntry::SubBlock: // Handled for us already.
+    case BitstreamEntry::Error:
+      return error("Malformed block");
+    case BitstreamEntry::EndBlock:
+      return std::error_code();
+    case BitstreamEntry::Record:
+      // The interesting case.
+      break;
+    }
+
+    // TODO: Read a record. This will eventually read the records
+    // containing the function name's VST index and the associated offset within
+    // the function summary section.
+    Record.clear();
+    switch (Stream.readRecord(Entry.ID, Record)) {
+    default:  // Default behavior: ignore.
+      break;
+    }
+  }
+  llvm_unreachable("Exit infinite loop");
+}
+
+// Eagerly parse the entire function summary block (i.e. for all functions
+// in the index). This populates the ThinLTOFunctionSummary objects in
+// the index.
+std::error_code ThinLTOBitcodeReader::parseEntireThinLTOSummary() {
+  if (Stream.EnterSubBlock(bitc::THINLTO_FUNCTION_SUMMARY_BLOCK_ID))
+    return error("Invalid record");
+
+  SmallVector<uint64_t, 64> Record;
+
+  while (1) {
+    BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
+
+    switch (Entry.Kind) {
+    case BitstreamEntry::SubBlock: // Handled for us already.
+    case BitstreamEntry::Error:
+      return error("Malformed block");
+    case BitstreamEntry::EndBlock:
+      return std::error_code();
+    case BitstreamEntry::Record:
+      // The interesting case.
+      break;
+    }
+
+    // TODO: Read a record. This will eventually read records containing
+    // function summary information for each function, specifically the
+    // function body's bitcode index, the index into the module string
+    // table for the bitcode module where it is found, and an evolving
+    // set of information used to guide function importing decisions.
+    Record.clear();
+    switch (Stream.readRecord(Entry.ID, Record)) {
+    default:  // Default behavior: ignore.
+      break;
+    }
+  }
+  llvm_unreachable("Exit infinite loop");
+}
+
+// Parse the ThinLTO module string table block into the Index.
+// This populates the ModulePathStringTable map in the index.
+std::error_code ThinLTOBitcodeReader::parseThinLTOModuleStringTable() {
+  if (Stream.EnterSubBlock(bitc::THINLTO_MODULE_STRTAB_BLOCK_ID))
+    return error("Invalid record");
+
+  SmallVector<uint64_t, 64> Record;
+
+  while (1) {
+    BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
+
+    switch (Entry.Kind) {
+    case BitstreamEntry::SubBlock: // Handled for us already.
+    case BitstreamEntry::Error:
+      return error("Malformed block");
+    case BitstreamEntry::EndBlock:
+      return std::error_code();
+    case BitstreamEntry::Record:
+      // The interesting case.
+      break;
+    }
+
+    // TODO: Read a record. This will eventually add records holding the
+    // module ID assigned during combined index generation and the associated
+    // bitcode module path.
+    Record.clear();
+    switch (Stream.readRecord(Entry.ID, Record)) {
+    default:  // Default behavior: ignore.
+      break;
+    }
+  }
+  llvm_unreachable("Exit infinite loop");
+}
+
+// Parse the ThinLTO index from the bitcode streamer into the given index.
+std::error_code
+ThinLTOBitcodeReader::parseSummaryIndexInto(
+    std::unique_ptr<DataStreamer> Streamer, ThinLTOFunctionSummaryIndex *I) {
+  TheIndex = I;
+
+  if (std::error_code EC = initStream(std::move(Streamer)))
+    return EC;
+
+  // Sniff for the signature.
+  if (Stream.Read(8) != 'B' ||
+      Stream.Read(8) != 'C' ||
+      Stream.Read(4) != 0x0 ||
+      Stream.Read(4) != 0xC ||
+      Stream.Read(4) != 0xE ||
+      Stream.Read(4) != 0xD)
+    return error("Invalid bitcode signature");
+
+  // We expect a number of well-defined blocks, though we don't necessarily
+  // need to understand them all.
+  while (1) {
+    if (Stream.AtEndOfStream()) {
+      // We didn't really read a proper Module block.
+      return error("Malformed ThihLTO IR file");
+    }
+
+    BitstreamEntry Entry =
+      Stream.advance(BitstreamCursor::AF_DontAutoprocessAbbrevs);
+
+    if (Entry.Kind != BitstreamEntry::SubBlock)
+      return error("Malformed block");
+
+    // If we see a MODULE_BLOCK, parse it to find the THINLTO_BLOCK.
+    if (Entry.ID == bitc::MODULE_BLOCK_ID)
+      return parseModule();
+
+    if (Stream.SkipBlock())
+      return error("Invalid record");
+  }
+}
+
+// Parse the function information at the given offset in the buffer into
+// the index. Used to support lazy parsing of function summaries from the
+// combined index during importing.
+std::error_code
+ThinLTOBitcodeReader::parseFunctionSummary(
+    std::unique_ptr<DataStreamer> Streamer,
+    ThinLTOFunctionSummaryIndex *I,
+    size_t FunctionSummaryOffset) {
+  TheIndex = I;
+
+  if (std::error_code EC = initStream(std::move(Streamer)))
+    return EC;
+
+  // Sniff for the signature.
+  if (Stream.Read(8) != 'B' ||
+      Stream.Read(8) != 'C' ||
+      Stream.Read(4) != 0x0 ||
+      Stream.Read(4) != 0xC ||
+      Stream.Read(4) != 0xE ||
+      Stream.Read(4) != 0xD)
+    return error("Invalid bitcode signature");
+
+  Stream.JumpToBit(FunctionSummaryOffset);
+
+  BitstreamEntry Entry = Stream.advanceSkippingSubblocks();
+
+  switch (Entry.Kind) {
+    default:
+      return error("Malformed block");
+    case BitstreamEntry::Record:
+      // The expected case.
+      break;
+  }
+
+  // TODO: Read a record.
+  SmallVector<uint64_t, 64> Record;
+  switch (Stream.readRecord(Entry.ID, Record)) {
+    default:  // Error, expected to jump to a valid function summary record.
+      return error("Invalid record");
+  }
+
+  return std::error_code();
+}
+
+std::error_code
+ThinLTOBitcodeReader::initStream(std::unique_ptr<DataStreamer> Streamer) {
+  if (Streamer)
+    return initLazyStream(std::move(Streamer));
+  return initStreamFromBuffer();
+}
+
+std::error_code ThinLTOBitcodeReader::initStreamFromBuffer() {
+  const unsigned char *BufPtr = (const unsigned char*)Buffer->getBufferStart();
+  const unsigned char *BufEnd = BufPtr+Buffer->getBufferSize();
+
+  if (Buffer->getBufferSize() & 3)
+    return error("Invalid bitcode signature");
+
+  // If we have a wrapper header, parse it and ignore the non-bc file contents.
+  // The magic number is 0x0B17C0DE stored in little endian.
+  if (isBitcodeWrapper(BufPtr, BufEnd))
+    if (SkipBitcodeWrapperHeader(BufPtr, BufEnd, true))
+      return error("Invalid bitcode wrapper header");
+
+  StreamFile.reset(new BitstreamReader(BufPtr, BufEnd));
+  Stream.init(&*StreamFile);
+
+  return std::error_code();
+}
+
+std::error_code
+ThinLTOBitcodeReader::initLazyStream(std::unique_ptr<DataStreamer> Streamer) {
+  // Check and strip off the bitcode wrapper; BitstreamReader expects never to
+  // see it.
+  auto OwnedBytes =
+      llvm::make_unique<StreamingMemoryObject>(std::move(Streamer));
+  StreamingMemoryObject &Bytes = *OwnedBytes;
+  StreamFile = llvm::make_unique<BitstreamReader>(std::move(OwnedBytes));
+  Stream.init(&*StreamFile);
+
+  unsigned char buf[16];
+  if (Bytes.readBytes(buf, 16, 0) != 16)
+    return error("Invalid bitcode signature");
+
+  if (!isBitcode(buf, buf + 16))
+    return error("Invalid bitcode signature");
+
+  if (isBitcodeWrapper(buf, buf + 4)) {
+    const unsigned char *bitcodeStart = buf;
+    const unsigned char *bitcodeEnd = buf + 16;
+    SkipBitcodeWrapperHeader(bitcodeStart, bitcodeEnd, false);
+    Bytes.dropLeadingBytes(bitcodeStart - buf);
+    Bytes.setKnownObjectSize(bitcodeEnd - bitcodeStart);
+  }
+  return std::error_code();
+}
+
 namespace {
 class BitcodeErrorCategoryType : public std::error_category {
   const char *name() const LLVM_NOEXCEPT override {
     return "llvm.bitcode";
   }
   std::string message(int IE) const override {
     BitcodeError E = static_cast<BitcodeError>(IE);
     switch (E) {
llvm::getBitcodeTargetTriple(MemoryBufferRef Buffer, LLVMContext &Context,
   std::unique_ptr<MemoryBuffer> Buf = MemoryBuffer::getMemBuffer(Buffer, false);
   auto R = llvm::make_unique<BitcodeReader>(Buf.release(), Context,
                                             DiagnosticHandler);
   ErrorOr<std::string> Triple = R->parseTriple();
   if (Triple.getError())
     return "";
   return Triple.get();
 }
+
+// Parse the specified bitcode buffer, returning the ThinLTO index.
+// If ParseFuncSummary is true, parse the entire function summary into
+// the index. Otherwise skip the function summary section, and only create
+// an index object with a map from function name to function summary offset.
+// The index is used to perform lazy function summary reading later.
+ErrorOr<std::unique_ptr<ThinLTOFunctionSummaryIndex>>
+llvm::getThinLTOIndex(MemoryBufferRef Buffer, LLVMContext &Context,
+                          DiagnosticHandlerFunction DiagnosticHandler,
+                          bool ParseFuncSummary) {
+  std::unique_ptr<MemoryBuffer> Buf = MemoryBuffer::getMemBuffer(Buffer, false);
+  ThinLTOBitcodeReader *R =
+      new ThinLTOBitcodeReader(Buf.get(), Context, DiagnosticHandler,
+                               ParseFuncSummary);
+
+  std::unique_ptr<ThinLTOFunctionSummaryIndex> Index =
+      llvm::make_unique<ThinLTOFunctionSummaryIndex>();
+
+  auto cleanupOnError = [&](std::error_code EC) {
+    R->releaseBuffer(); // Never take ownership on error.
+    return EC;
+  };
+
+  if (std::error_code EC = R->parseSummaryIndexInto(nullptr, Index.get()))
+    return cleanupOnError(EC);
+
+  Buf.release(); // The ThinLTOBitcodeReader owns it now.
+  return std::move(Index);
+}
+
+// Check if the given bitcode buffer contains a ThinLTO block.
+bool llvm::hasThinLTOIndex(MemoryBufferRef Buffer, LLVMContext &Context,
+    DiagnosticHandlerFunction DiagnosticHandler) {
+  std::unique_ptr<MemoryBuffer> Buf = MemoryBuffer::getMemBuffer(Buffer, false);
+  ThinLTOBitcodeReader *R =
+      new ThinLTOBitcodeReader(Buf.get(), Context, DiagnosticHandler,
+                               false, true);
+
+  auto cleanupOnError = [&](std::error_code EC) {
+    R->releaseBuffer(); // Never take ownership on error.
+    return false;
+  };
+
+  if (std::error_code EC = R->parseSummaryIndexInto(nullptr, nullptr))
+    return cleanupOnError(EC);
+
+  Buf.release(); // The ThinLTOBitcodeReader owns it now.
+  return R->foundThinLTO();
+}
+
+// This method supports lazy reading of function summary data from
+// the combined index during function importing. When reading the combined
+// index file, getThinLTOIndex is first invoked with ParseFuncSummary=false.
+// Then this method is called for each function considered for importing,
+// to parse the summary information for the given function name into
+// the index.
+std::error_code llvm::readThinLTOFunctionSummary(
+    MemoryBufferRef Buffer, LLVMContext &Context,
+    DiagnosticHandlerFunction DiagnosticHandler,
+    StringRef FunctionName,
+    std::unique_ptr<ThinLTOFunctionSummaryIndex> Index) {
+  std::unique_ptr<MemoryBuffer> Buf = MemoryBuffer::getMemBuffer(Buffer, false);
+  ThinLTOBitcodeReader *R =
+      new ThinLTOBitcodeReader(Buf.get(), Context, DiagnosticHandler);
+
+  auto cleanupOnError = [&](std::error_code EC) {
+    R->releaseBuffer(); // Never take ownership on error.
+    return EC;
+  };
+
+  // Lookup the given function name in the ThinLTOFunctionMap, which may
+  // contain a list of function infos in the case of a COMDAT. Walk through
+  // and parse each function summary info at the function summary offset
+  // recorded when parsing the ThinLTO symbol table.
+  ThinLTOFunctionInfoList FuncInfos = Index->getFunctionInfoList(FunctionName);
+  for (std::vector<ThinLTOFunctionInfo>::iterator FII = FuncInfos.begin();
+       FII != FuncInfos.end(); FII++) {
+    size_t FunctionSummaryOffset = FII->functionSummarySecOffset();
+    if (std::error_code EC = R->parseFunctionSummary(nullptr, Index.get(),
+                                                     FunctionSummaryOffset))
+      return cleanupOnError(EC);
+  }
+
+  Buf.release(); // The ThinLTOBitcodeReader owns it now.
+  return std::error_code();
+}

lib/Bitcode/Writer/BitcodeWriter.cpp

// FIXME: This should only use space for first class types!
     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID, Abbv) !=
         FUNCTION_INST_GEP_ABBREV)
       llvm_unreachable("Unexpected abbrev ordering!");
   }
 
   Stream.ExitBlock();
 }
 
+static void WriteThinLTOModStrings(const ThinLTOFunctionSummaryIndex *I,
+                                   BitstreamWriter &Stream) {
+  Stream.EnterSubblock(bitc::THINLTO_MODULE_STRTAB_BLOCK_ID, 3);
+  // TODO: Write records
+  Stream.ExitBlock();
+}
+
+static void WriteThinLTOSummary(const ThinLTOFunctionSummaryIndex *I,
+                                BitstreamWriter &Stream) {
+  Stream.EnterSubblock(bitc::THINLTO_FUNCTION_SUMMARY_BLOCK_ID, 3);
+  // TODO: Write records
+  Stream.ExitBlock();
+}
+
+static void WriteThinLTOSymtab(const ThinLTOFunctionSummaryIndex *I,
+                               BitstreamWriter &Stream) {
+  Stream.EnterSubblock(bitc::THINLTO_SYMTAB_BLOCK_ID, 3);
+  // TODO: Write records. We need to have built up a map from function
+  // name to ValueID saved on the Index before this.
+  Stream.ExitBlock();
+}
+
+static void WriteThinLTOBlock(const ThinLTOFunctionSummaryIndex *I,
+                              BitstreamWriter &Stream) {
+  Stream.EnterSubblock(bitc::THINLTO_BLOCK_ID, 3);
+
+  WriteThinLTOModStrings(I, Stream);
+  WriteThinLTOSummary(I, Stream);
+  WriteThinLTOSymtab(I, Stream);
+
+  Stream.ExitBlock();
+}
+
 /// WriteModule - Emit the specified module to the bitstream.
 static void WriteModule(const Module *M, BitstreamWriter &Stream,
                         bool ShouldPreserveUseListOrder) {
   Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
 
   SmallVector<unsigned, 1> Vals;
   unsigned CurVersion = 1;
   Vals.push_back(CurVersion);
static void WriteModule(const Module *M, BitstreamWriter &Stream,
   if (VE.shouldPreserveUseListOrder())
     WriteUseListBlock(nullptr, VE, Stream);
 
   // Emit function bodies.
   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F)
     if (!F->isDeclaration())
       WriteFunction(*F, VE, Stream);
 
+  // TODO: Setup/pass non-null index.
+  // This patch is dependent on patch that adds -fthinlto option and adds/sets
+  // the EmitThinLTOIndex parameter (http://reviews.llvm.org/D11907).
+  // Will sync and remove this comment before commit.
+  if (EmitThinLTOIndex)
+    WriteThinLTOBlock(nullptr, Stream);
+
   Stream.ExitBlock();
 }
 
 /// EmitDarwinBCHeader - If generating a bc file on darwin, we have to emit a
 /// header and trailer to make it compatible with the system archiver.  To do
 /// this we emit the following header, and then emit a trailer that pads the
 /// file out to be a multiple of 16 bytes.
 ///
void llvm::WriteBitcodeToFile(const Module *M, raw_ostream &Out,
   }
 
   if (TT.isOSDarwin())
     EmitDarwinBCHeaderAndTrailer(Buffer, TT);
 
   // Write the generated bitstream to "Out".
   Out.write((char*)&Buffer.front(), Buffer.size());
 }
+
+// Write the specified ThinLTO index to the given raw output stream,
+// where it will be written in a new bitcode block. This is used when
+// writing the combined index file.
+void llvm::WriteThinLTOToFile(const ThinLTOFunctionSummaryIndex *Index,
+                              raw_ostream &Out) {
+  SmallVector<char, 0> Buffer;
+  Buffer.reserve(256*1024);
+
+  BitstreamWriter Stream(Buffer);
+
+  // Emit the bitcode header.
+  Stream.Emit((unsigned)'B', 8);
+  Stream.Emit((unsigned)'C', 8);
+  Stream.Emit(0x0, 4);
+  Stream.Emit(0xC, 4);
+  Stream.Emit(0xE, 4);
+  Stream.Emit(0xD, 4);
+
+  WriteThinLTOBlock(Index, Stream);
+
+  Out.write((char*)&Buffer.front(), Buffer.size());
+}

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

static const char *GetBlockName(unsigned BlockID,
   case bitc::PARAMATTR_GROUP_BLOCK_ID: return "PARAMATTR_GROUP_BLOCK_ID";
   case bitc::TYPE_BLOCK_ID_NEW:        return "TYPE_BLOCK_ID";
   case bitc::CONSTANTS_BLOCK_ID:       return "CONSTANTS_BLOCK";
   case bitc::FUNCTION_BLOCK_ID:        return "FUNCTION_BLOCK";
   case bitc::VALUE_SYMTAB_BLOCK_ID:    return "VALUE_SYMTAB";
   case bitc::METADATA_BLOCK_ID:        return "METADATA_BLOCK";
   case bitc::METADATA_ATTACHMENT_ID:   return "METADATA_ATTACHMENT_BLOCK";
   case bitc::USELIST_BLOCK_ID:         return "USELIST_BLOCK_ID";
+  case bitc::THINLTO_BLOCK_ID:         return "THINLTO_BLOCK";
+  case bitc::THINLTO_SYMTAB_BLOCK_ID:  return "THINLTO_SYMTAB_BLOCK";
+  case bitc::THINLTO_FUNCTION_SUMMARY_BLOCK_ID:
+                                       return "THINLTO_FUNCTION_SUMMARY_BLOCK";
+  case bitc::THINLTO_MODULE_STRTAB_BLOCK_ID:
+                                       return "THINLTO_MODULE_STRTAB_BLOCK";
   }
 }
 
 /// GetCodeName - Return a symbolic code name if known, otherwise return
 /// null.
 static const char *GetCodeName(unsigned CodeID, unsigned BlockID,
                                const BitstreamReader &StreamFile,
                                CurStreamTypeType CurStreamType) {