[ThinLTO] Emit individual index files for distributed backends

[tejohnson]

Summary

When launching ThinLTO backends in a distributed build (currently
supported in gold via the thinlto-index-only plugin option), emit
an individual index file for each backend process as described here:
http://lists.llvm.org/pipermail/llvm-dev/2016-April/098272.html

The individual index file encodes the summary and module information
required for implementing the importing/exporting decisions made
for a given module in the thin link step.
This is in place of the current mechanism that uses the combined index
to make importing decisions in each back end independently. It is an
enabler for doing global summary based optimizations in the thin link
step (which will be recorded in the individual index files), and reduces
the size of the index that must be sent to each backend process, and
the amount of work to scan it in the backends.

Rather than create entirely new ModuleSummaryIndex structures (and all
the included unique_ptrs) for each backend index file, a map is created
to record all of the GUID and summary pointers needed for a particular
index file. The IndexBitcodeWriter walks this map instead of the full
index (hiding the details of managing the appropriate summary iteration
in a new iterator subclass). This is more efficient than walking the
entire combined index and filtering out just the needed summaries during
each backend bitcode index write.

Depends on D19481.

[tejohnson]

Rebase

[tejohnson]

• Refactor ThinLTO handling out of allSymbolsReadHook as it is getting big

[mehdi_amini]

Is it possible to have some coverage in a test based on llvm-lto (or other standard tools)?
The availability of the gold plugin is rather limited usually.

lib/Bitcode/Writer/BitcodeWriter.cpp

396

no else after return.

[mehdi_amini]

Same as before, it'd be nice to have a llvm-lto based test to cover this.

lib/Bitcode/Writer/BitcodeWriter.cpp

283

Why not use directly the ImportMapTy populated by ComputeCrossModuleImportForModule?
That would avoid restructuring the data. If the only thing is the use of std::map instead of StringMap for the purpose of stable ordering, let's change what ComputeCrossModuleImportForModule operates on.

tools/gold/gold-plugin.cpp

1232

Why?

[tejohnson]

In D19556#415035, @joker.eph wrote:

Is it possible to have some coverage in a test based on llvm-lto (or other standard tools)?
The availability of the gold plugin is rather limited usually.

Ok, looking at the code added here to gold-plugin, I think it makes most sense to move the setup of the ModuleToSummariesForIndex map into a helper method in FunctionImport.cpp. I would leave the actual invocation of WriteIndexToFile here, so that I don't need to add a dependence from Transforms/IPO to libBitWriter (which is doable, won't introduce a circular dependence, but seems somewhat strange). I would also leave the invocation of collectDefinedGVSummariesPerModule and ComputeCrossModuleImport here for now - eventually we will want to do similar optimizations in gold to what you are doing in libLTO, which means refactoring that handling out of libLTO, but that is an orthogonal thing I would like to leave for another day.

Then I can add a similar mechanism to libLTO (similar interface to e.g. ThinLTOGenerator::internalize - take a module and the combined index as input, but then invoke the new mechanism to compute and return the individual index summaries map. Then I can add a mechanism to llvm-lto to invoke it and write out the individual index files, and add a llvm-lto based test.

lib/Bitcode/Writer/BitcodeWriter.cpp

283

Initially I planned to do exactly that. It required refactoring ImportMapTy out of FunctionImport.h, since I needed to use it in BitcodeWriter.cpp, so I moved it to ModuleSummaryIndex.h and made the necessary changes. I put it back when I realized the following:

But the bigger issue is that it didn't really give me the information I needed:

• The ImportMapTy is a map to FunctionsToImportTy, which provides the GUID of the functions to import. I would then need to perform an extra step in the bitcode writer to find the corresponding summary object for that module. It was more natural and efficient to get that directly from the ModuleToDefinedGVSummaries map already populated in the client (and in fact this map and ModuleToDefinedGVSummaries use the same GVSummaryMapTy).
• I also need to emit the summaries for the module we are importing into (see response to your other comment below on why), which are not in the import map, so I would have had to pass in additional info and handle it separately inside the bitcode writer.
• I don't need the other information in the FunctionsToImportTy (the threshold), although that is not a big issue

396

Will fix.

tools/gold/gold-plugin.cpp

1232

Because when we make global optimization decisions here (i.e. promotion, ODR resolution, etc), we will need to note the info (e.g. updated linkage type) in the summaries for this module in its individual backend index, so that the linkage changes can be made in the backend process.

See also the "Individual Module Index Files" overview section in http://lists.llvm.org/pipermail/llvm-dev/2016-April/098272.html.

[tejohnson]

Address comments, including refactoring some of the handling out of
gold-plugins and into FunctionImport. Invoke the refactored helper in
libLTO and add llvm-lto support and test.

[tejohnson]

• Refine libLTO support: parsing module not needed for computing summaries.

[mehdi_amini]

LGTM (see one bikeshed suggestion inline)

lib/Bitcode/Writer/BitcodeWriter.cpp

283

The ImportMapTy is a map to FunctionsToImportTy, which provides the GUID of the functions to import. I would then need to perform an extra step in the bitcode writer to find the corresponding summary object for that module. It was more natural and efficient to get that directly from the ModuleToDefinedGVSummaries map already populated in the client (and in fact this map and ModuleToDefinedGVSummaries use the same GVSummaryMapTy).

OK I missed this the first time, seems obvious afterward...
It seems like something that could be changed in whatever ComputeCrossModuleImportForModule produces, but we can refactor/change that later (indeed this is the kind of information I was expected to gather from your current series of patches to feed the design a common API for linkers).

lib/Transforms/IPO/FunctionImport.cpp

423 ↗

(On Diff #55527)

bikeshed: what about llvm::gatherImportedSummariesForModule() (i.e. we don't really "compute", and "File" seems odd compare to the usual use of "Module")

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

745 ↗

(On Diff #55527)

I am wondering if this need to sit on the ThinLTOCodeGenerator though: it does not use any member, does it?

[tejohnson]

lib/Bitcode/Writer/BitcodeWriter.cpp

283

Yes, I agree that some of these steps can/should be combined when we refactor into a common library.

lib/Transforms/IPO/FunctionImport.cpp

423 ↗

(On Diff #55527)

Good idea, will switch to that name.

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

745 ↗

(On Diff #55527)

You're right it doesn't. It is invoked from llvm-lto - would it be better to just create a global function outside the class but still in ThinLTOCodeGenerator.h/cpp (in the llvm namespace)?

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

745 ↗

(On Diff #55527)

I'm not totally sure what is "the right thing to do", maybe just turning it into a static method in the class would be enough for now?

I don't have a strong opinion on this, I figured I'll just mention it.

Initially I had this class only having addModule and run. The individual method I added were here to support breaking down testing of all of what's going on in run(). It is slightly slipping here, but we'll refactor all of that later, hopefully not in too long.

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

745 ↗

(On Diff #55527)

I think using a static class member makes the most sense for now, will do that.

[mehdi_amini]

For the MSAN issue:

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

347 ↗

(On Diff #56279)

Here if Writer.Index.begin() == Writer.Index.end() we end up with IndexGVSummariesIter being uninitialized.

363 ↗

(On Diff #56279)

Here we don't check for the same conditions as in the ctor.

[tejohnson]

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

363 ↗

(On Diff #56279)

(Copying from IRC for posterity)

This was also my first instinct, until I realized that operator++ should never be executed here.

It's coming from the "for (const auto &I : *this)" on line 291 for an empty index. The == end() check should be done before attempting to do the operator++. Confirmed with a normal llvm-lto build that it detects it is at the end and exits (operator++ is never entered for the test case). So something else is going wrong. Attempting to build an msan compiler to track this down better.

[vitalybuka]

As a sanitizers build cop, I am going to revert this path. It should be easy to re-apply the patch when a fix is ready.

[mehdi_amini]

LGTM, it does not hurt to revert during the investigation.

[vitalybuka]

Reverted in r268660

[tejohnson]

I'm at a loss as to what is going on with the msan failures. Maybe it will be obvious to someone else, so posting what I found so far here.

Unfortunately, I can make the msan failure go away any number of ways (including building at a lower level of optimization or adding any print statements, which is making debugging challenging). I also put a log from a debugging session below to show what info I can get.

With my own msan built compiler, I can reproduce most but not all of the failures from the bot. The case I have been looking at is with the distributed_indexes.ll test added with this patch. In that case when we create the IndexBitcodeWriter we have a non-null ModuleToSummariesForIndex pointer, so we don't initialize the IndexSummaries* pointers. When I step through in the debugger, the range based for loop in the IndexBitcodeWriter constructor executes the expected paths in the begin() and end() iterator constructors (not shown in the below trace). After the first for loop body executes, I can see where we execute the iterator's operator++() and operator==() paths for the expected ModuleToSummariesForIndex!=null case. But then oddly we seem to jump back to operator++() handling on the wrong path (that we would execute if ModuleToSummariesForIndex==null), and is where we attempt to access and get the msan error on the IndexSummaries* iterator accesses.

A few things that make it go away, but I don't understand why (may be luck):

1. Initializing the IndexSummariesBack and IndexSummariesIter unconditionally in the constructor (we can do this safely since the Index is always passed in).
2. Re-initializing IndexSummariesBack in the operator++() code right before we access it (although that access shouldn't happen as noted above).

For both 1) and 2) I don't understand why these would help except luck, since we shouldn't be executing the path that accesses these iterators. Is there something about the way they are declared that would make the compiler think it can hoist the accesses so that they are unconditionally executed?

3. Change the range based for loop to be a non-range for loop: for (IndexBitcodeWriter::iterator I = begin(); I != end(); ++I) GUIDToValueIdMap[(*I).first] = ++GlobalValueId;
4. Change the range based for loop to make a copy of the value instead of assigning to a const reference: for (auto I : *this) GUIDToValueIdMap[I.first] = ++GlobalValueId;

For both 3) and 4) this avoids binding the return of the iterator::operator* (which is a std::pair) to a const reference. However, looking at operator* which invokes make_pair on a GUID and summary pointer to create the return value, I think the const reference should extend the lifetime of the returned temporary through the loop body shouldn't it? In any case, this doesn't explain why I am seeing the wrong path of the operator++() being executed after we appear to already have done the operator++ and operator==.

Here's the debugging log, with some comments sprinkled in:

Starting program: /usr/local/google/home/tejohnson/llvm/llvm_msan/bin/llvm-lto -thinlto-action=distributedindexes -thinlto-index /usr/local/google/home/tejohnson/llvm/llvm_msan/test/ThinLTO/X86/Output/distributed_indexes.ll.tmp.index.bc /usr/local/google/home/tejohnson/llvm/llvm_msan/test/ThinLTO/X86/Output/distributed_indexes.ll.tmp1.bc /usr/local/google/home/tejohnson/llvm/llvm_msan/test/ThinLTO/X86/Output/distributed_indexes.ll.tmp2.bc

Breakpoint 3, IndexBitcodeWriter () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:285
285 : BitcodeWriter(Buffer), Index(Index),

// entered the IndexBitcodeWriter constructor, use next to get to the body of the first iteration:

(gdb) n
286 ModuleToSummariesForIndex(ModuleToSummariesForIndex) {
(gdb)
285 : BitcodeWriter(Buffer), Index(Index),
(gdb)
286 ModuleToSummariesForIndex(ModuleToSummariesForIndex) {
(gdb)
281 IndexBitcodeWriter(SmallVectorImpl<char> &Buffer,
(gdb)
275 unsigned GlobalValueId = 0;
(gdb)
291 for (const auto &I : *this)
(gdb)
292 GUIDToValueIdMap[I.first] = ++GlobalValueId;

// single step from here. First set of instructions are the emplace into map from line 292:

(gdb) s
operator[] () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:292
292 GUIDToValueIdMap[I.first] = ++GlobalValueId;
(gdb)
emplace_unique_key_args<unsigned long, const std::1::piecewise_construct_t &, std::1::tuple<const unsigned long &>, std::1::tuple<> > () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:292
292 GUIDToValueIdMap[I.first] = ++GlobalValueId;
(gdb)
insert_node_at () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:292
292 GUIDToValueIdMap[I.first] = ++GlobalValueId;
(gdb)
size () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:292
292 GUIDToValueIdMap[I.first] = ++GlobalValueId;
(gdb)
first () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:292
292 GUIDToValueIdMap[I.first] = ++GlobalValueId;
(gdb)
first () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/memory:2312
2312 _LIBCPP_INLINE_VISIBILITY _T1_reference first() _NOEXCEPT {return first_;}
(gdb)
emplace_unique_key_args<unsigned long, const std::1::piecewise_construct_t &, std::1::tuple<const unsigned long &>, std::1::tuple<> > () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/__tree:2013
2013 node_base_pointer& child = find_equal(parent, k);
(gdb)
find_equal<unsigned long> () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/__tree:1887
1887 if (nd != nullptr)
(gdb)
emplace_unique_key_args<unsigned long, const std::1::piecewise_construct_t &, std::1::tuple<const unsigned long &>, std::1::tuple<> > () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/tree:2023
2023 insert_node_at(parent, child, static_cast<node_base_pointer>(h.get()));
(gdb)
insert_node_at () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/__tree:1997
1997 ++size();

// Now enter the operator++() in the range for loop, executes the Writer.ModuleToSummariesForIndex!=null case as expected:

(gdb)
357 if (ModuleGVSummariesIter == ModuleSummariesIter->second.end() &&
(gdb) list
352 First the inner iterator is incremented, then if it is at the end
353 and there are more outer iterations to go, the inner is reset to
354 // the start of the next inner list.
355 if (Writer.ModuleToSummariesForIndex) {
356 ++ModuleGVSummariesIter;
357 if (ModuleGVSummariesIter == ModuleSummariesIter->second.end() &&
358 ModuleSummariesIter != ModuleSummariesBack) {
359 ++ModuleSummariesIter;
360 ModuleGVSummariesIter = ModuleSummariesIter->second.begin();
361 }
(gdb) up
#1 IndexBitcodeWriter () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:291
291 for (const auto &I : *this)
(gdb) down
#0 operator++ () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:357
357 if (ModuleGVSummariesIter == ModuleSummariesIter->second.end() &&
(gdb) s
end () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:357
357 if (ModuleGVSummariesIter == ModuleSummariesIter->second.end() &&
(gdb)
end () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:357
357 if (ModuleGVSummariesIter == ModuleSummariesIter->second.end() &&
(gdb)
end_node () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:357
357 if (ModuleGVSummariesIter == ModuleSummariesIter->second.end() &&
(gdb)
first () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:357
357 if (ModuleGVSummariesIter == ModuleSummariesIter->second.end() &&
(gdb)
first () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/memory:2312
2312 _LIBCPP_INLINE_VISIBILITY _T1_reference first() _NOEXCEPT {return first_;}
(gdb)
operator++ () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:358
358 ModuleSummariesIter != ModuleSummariesBack) {
(gdb) s
operator!= () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:358
358 ModuleSummariesIter != ModuleSummariesBack) {
(gdb) s
operator!= () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/__tree:810
810 {return !(x == y);}
(gdb)
operator++ () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:357
357 if (ModuleGVSummariesIter == ModuleSummariesIter->second.end() &&
(gdb)
IndexBitcodeWriter () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:291
291 for (const auto &I : *this)

// Next we execute the operator!= to check if for loop at end():

(gdb) s
operator!= () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:291
291 for (const auto &I : *this)
(gdb)
operator== () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:291
291 for (const auto &I : *this)
(gdb) up
#1 operator!= () at llvm/include/llvm/ADT/iterator.h:97
97 return !static_cast<const DerivedT *>(this)->operator==(RHS);
(gdb) up
#2 IndexBitcodeWriter () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:291
291 for (const auto &I : *this)
(gdb) down
#1 operator!= () at llvm/include/llvm/ADT/iterator.h:97
97 return !static_cast<const DerivedT *>(this)->operator==(RHS);
(gdb) down
#0 operator== () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:291
291 for (const auto &I : *this)
(gdb) s
operator== () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:291
291 for (const auto &I : *this)

// This is the Writer.ModuleToSummariesForIndex!=null case of operator==() as expected:

(gdb) up
#1 operator== () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:395
395 return ModuleGVSummariesIter == RHS.ModuleGVSummariesIter;
(gdb) s
operator== () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/__tree:807
807 {return x.ptr_ == y.ptr_;}
(gdb) s
IndexBitcodeWriter () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:291
291 for (const auto &I : *this)

// Here's where things go weird. This is the Writer.ModuleToSummariesForIndex==null case of operator++():

(gdb) s
operator++ () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:364
364 if (IndexGVSummariesIter == IndexSummariesIter->second.end() &&
(gdb) up
#1 IndexBitcodeWriter () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:291
291 for (const auto &I : *this)
(gdb) down
#0 operator++ () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:364
364 if (IndexGVSummariesIter == IndexSummariesIter->second.end() &&
(gdb) s
365 IndexSummariesIter != IndexSummariesBack) {
(gdb) s
operator!= () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:365
365 IndexSummariesIter != IndexSummariesBack) {
(gdb) s
operator!= () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/__tree:886
886 {return !(x == y);}
(gdb) up
#1 operator!= () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/map:798
798 {return x.i_ != y.i_;}
(gdb) up
#2 operator++ () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:365
365 IndexSummariesIter != IndexSummariesBack) {
(gdb) down
#1 operator!= () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/map:798
798 {return x.i_ != y.i_;}
(gdb) down
#0 operator!= () at /usr/local/google/home/tejohnson/llvm/llvm_msan/build-libcxx-msan/include/c++/v1/__tree:886
886 {return !(x == y);}
(gdb) s
operator++ () at llvm/lib/Bitcode/Writer/BitcodeWriter.cpp:364
364 if (IndexGVSummariesIter == IndexSummariesIter->second.end() &&
(gdb) s

Breakpoint 2, __msan_warning_noreturn ()

at /usr/local/google/home/tejohnson/llvm/llvm_msan/llvm/projects/compiler-rt/lib/msan/msan.cc:362

362 void __msan_warning_noreturn() {

[tejohnson]

BitcodeWriter.cpp.s.msan.proc193 KBDownload

[tejohnson]

For the assembly just posted, the issue is around line 1211. Note that earlier in that block we are supposedly executing BitcodeWriter.cpp:357 (which is in the expected path of operator++). Then we have some code that is attributed to line 364. The je .LBB91_91 is not taken, but je .LBB91_310 is, which branches to the msan warning call. Note that if we didn't take this second branch, the next thing would be the operator* code at line 377 (which is from the expected Writer.ModuleToSummariesForIndex!=null path).

[tejohnson]

beforeunswitch23 MBDownload

afterunswitch23 MBDownload

Upload of the module IR before and after unswitching the loop in question. The message with the debug info about the unswitch in this function (there was only one) is at the end of the beforeunswitch file. I had made some minor edits to BitcodeWriter.cpp for this compile, but nothing that had any effect and the line numbers should be the same.

[tejohnson]

BitcodeWriter.cpp.s.nomsan.proc65 KBDownload

Here is the assembly from -O3 without msan instrumentation. It looks more sane. I.e. the execution of the BitcodeWriter.cpp:364 (line 733) appears to be guarded by an earlier conditional branch from the 355 (see the jne .LBB91_77 just above).

include/llvm/Bitcode/ReaderWriter.h

namespace llvm {
   /// for use in ThinLTO optimization).
   void WriteBitcodeToFile(const Module *M, raw_ostream &Out,
                           bool ShouldPreserveUseListOrder = false,
                           const ModuleSummaryIndex *Index = nullptr,
                           bool GenerateHash = false);
 
   /// Write the specified module summary 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 for ThinLTO.
-  void WriteIndexToFile(const ModuleSummaryIndex &Index, raw_ostream &Out);
+  /// writing the combined index file for ThinLTO. When writing a subset of the
+  /// index for a distributed backend, provide the \p ModuleToSummariesForIndex
+  /// map.
+  void WriteIndexToFile(
+      const ModuleSummaryIndex &Index, raw_ostream &Out,
+      std::map<StringRef, GVSummaryMapTy> *ModuleToSummariesForIndex = nullptr);
 
   /// 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.)

lib/Bitcode/Writer/BitcodeWriter.cpp

private:
   void writeModuleHash(size_t BlockStartPos);
 };
 
 /// Class to manage the bitcode writing for a combined index.
 class IndexBitcodeWriter : public BitcodeWriter {
   /// The combined index to write to bitcode.
   const ModuleSummaryIndex &Index;
 
+  /// When writing a subset of the index for distributed backends, client
+  /// provides a map of modules to the corresponding GUIDs/summaries to write.
+  std::map<StringRef, GVSummaryMapTy> *ModuleToSummariesForIndex;
+
   /// Map that holds the correspondence between the GUID used in the combined
   /// index and a value id generated by this class to use in references.
   std::map<GlobalValue::GUID, unsigned> GUIDToValueIdMap;
 
   /// Tracks the last value id recorded in the GUIDToValueMap.
   unsigned GlobalValueId = 0;
 
 public:
   /// Constructs a IndexBitcodeWriter object for the given combined index,
-  /// writing to the provided \p Buffer.
-  IndexBitcodeWriter(SmallVectorImpl<char> &Buffer,
-                     const ModuleSummaryIndex &Index)
-      : BitcodeWriter(Buffer), Index(Index) {
-    // Assign unique value ids to all functions in the index for use
+  /// writing to the provided \p Buffer. When writing a subset of the index
+  /// for a distributed backend, provide a \p ModuleToSummariesForIndex map.
+  IndexBitcodeWriter(
+      SmallVectorImpl<char> &Buffer, const ModuleSummaryIndex &Index,
+      std::map<StringRef, GVSummaryMapTy> *ModuleToSummariesForIndex = nullptr)
+      : BitcodeWriter(Buffer), Index(Index),
+        ModuleToSummariesForIndex(ModuleToSummariesForIndex) {
+    // Assign unique value ids to all summaries to be written, for use
     // in writing out the call graph edges. Save the mapping from GUID
     // to the new global value id to use when writing those edges, which
     // are currently saved in the index in terms of GUID.
-    for (auto &II : Index)
-      GUIDToValueIdMap[II.first] = ++GlobalValueId;
+    for (const auto &I : *this)
+      GUIDToValueIdMap[I.first] = ++GlobalValueId;
+  }
+
+  /// The below iterator returns the GUID and associated summary.
+  typedef std::pair<GlobalValue::GUID, GlobalValueSummary *> GVInfo;
+
+  /// Iterator over the value GUID and summaries to be written to bitcode,
+  /// hides the details of whether they are being pulled from the entire
+  /// index or just those in a provided ModuleToSummariesForIndex map.
+  class iterator
+      : public llvm::iterator_facade_base<iterator, std::forward_iterator_tag,
+                                          GVInfo> {
+    /// Enables access to parent class.
+    const IndexBitcodeWriter &Writer;
+
+    // Iterators used when writing only those summaries in a provided
+    // ModuleToSummariesForIndex map:
+
+    /// Points to the last element in outer ModuleToSummariesForIndex map.
+    std::map<StringRef, GVSummaryMapTy>::iterator ModuleSummariesBack;
+    /// Iterator on outer ModuleToSummariesForIndex map.
+    std::map<StringRef, GVSummaryMapTy>::iterator ModuleSummariesIter;
+    /// Iterator on an inner global variable summary map.
+    GVSummaryMapTy::iterator ModuleGVSummariesIter;
+
+    // Iterators used when writing all summaries in the index:
+
+    /// Points to the last element in the Index outer GlobalValueMap.
+    const_gvsummary_iterator IndexSummariesBack;
+    /// Iterator on outer GlobalValueMap.
+    const_gvsummary_iterator IndexSummariesIter;
+    /// Iterator on an inner GlobalValueSummaryList.
+    GlobalValueSummaryList::const_iterator IndexGVSummariesIter;
+
+  public:
+    /// Construct iterator from parent \p Writer and indicate if we are
+    /// constructing the end iterator.
+    iterator(const IndexBitcodeWriter &Writer, bool IsAtEnd) : Writer(Writer) {
+      // Set up the appropriate set of iterators given whether we are writing
+      // the full index or just a subset.
+      // Can't setup the Back or inner iterators if the corresponding map
+      // is empty. This will be handled specially in operator== as well.
+      if (Writer.ModuleToSummariesForIndex &&
+          !Writer.ModuleToSummariesForIndex->empty()) {
+        ModuleSummariesBack =
+            std::prev(Writer.ModuleToSummariesForIndex->end());
+        ModuleSummariesIter = Writer.ModuleToSummariesForIndex->begin();
+        ModuleGVSummariesIter = !IsAtEnd ? ModuleSummariesIter->second.begin()
+                                         : ModuleSummariesBack->second.end();
+      } else if (!Writer.ModuleToSummariesForIndex &&
+                 Writer.Index.begin() != Writer.Index.end()) {
+        IndexSummariesBack = std::prev(Writer.Index.end());
+        IndexSummariesIter = Writer.Index.begin();
+        IndexGVSummariesIter = !IsAtEnd ? IndexSummariesIter->second.begin()
+                                        : IndexSummariesBack->second.end();
+      }
+    }
+
+    /// Increment the appropriate set of iterators.
+    iterator &operator++() {
+      // First the inner iterator is incremented, then if it is at the end
+      // and there are more outer iterations to go, the inner is reset to
+      // the start of the next inner list.
+      if (Writer.ModuleToSummariesForIndex) {
+        ++ModuleGVSummariesIter;
+        if (ModuleGVSummariesIter == ModuleSummariesIter->second.end() &&
+            ModuleSummariesIter != ModuleSummariesBack) {
+          ++ModuleSummariesIter;
+          ModuleGVSummariesIter = ModuleSummariesIter->second.begin();
+        }
+      } else {
+        ++IndexGVSummariesIter;
+        if (IndexGVSummariesIter == IndexSummariesIter->second.end() &&
+            IndexSummariesIter != IndexSummariesBack) {
+          ++IndexSummariesIter;
+          IndexGVSummariesIter = IndexSummariesIter->second.begin();
+        }
+      }
+      return *this;
+    }
+
+    /// Access the <GUID,GlobalValueSummary*> pair corresponding to the current
+    /// outer and inner iterator positions.
+    GVInfo operator*() {
+      if (Writer.ModuleToSummariesForIndex)
+        return std::make_pair(ModuleGVSummariesIter->first,
+                              ModuleGVSummariesIter->second);
+      else
+        return std::make_pair(IndexSummariesIter->first,
+                              IndexGVSummariesIter->get());
+    }
+
+    /// Checks if the iterators are equal, with special handling for empty
+    /// indexes.
+    bool operator==(const iterator &RHS) const {
+      if (Writer.ModuleToSummariesForIndex) {
+        // First ensure that both are writing the same subset.
+        if (Writer.ModuleToSummariesForIndex !=
+            RHS.Writer.ModuleToSummariesForIndex)
+          return false;
+        // Already determined above that maps are the same, so if one is
+        // empty, they both are.
+        if (Writer.ModuleToSummariesForIndex->empty())
+          return true;
+        return ModuleGVSummariesIter == RHS.ModuleGVSummariesIter;
+      } else {
+        // First ensure RHS also writing the full index, and that both are
+        // writing the same full index.
+        if (RHS.Writer.ModuleToSummariesForIndex ||
+            &Writer.Index != &RHS.Writer.Index)
+          return false;
+        // Already determined above that maps are the same, so if one is
+        // empty, they both are.
+        if (Writer.Index.begin() == Writer.Index.end())
+          return true;
+        return IndexGVSummariesIter == RHS.IndexGVSummariesIter;
+      }
     }
+  };
+
+  /// Obtain the start iterator over the summaries to be written.
+  iterator begin() { return iterator(*this, /*IsAtEnd=*/false); }
+  /// Obtain the end iterator over the summaries to be written.
+  iterator end() { return iterator(*this, /*IsAtEnd=*/true); }
 
 private:
   /// Main entry point for writing a combined index to bitcode, invoked by
   /// BitcodeWriter::write() after it writes the header.
   void writeBlocks() override;
 
   void writeIndex();
   void writeModStrings();
   void writeCombinedValueSymbolTable();
   void writeCombinedGlobalValueSummary();
 
+  /// Indicates whether the provided \p ModulePath should be written into
+  /// the module string table, e.g. if full index written or if it is in
+  /// the provided subset.
+  bool doIncludeModule(StringRef ModulePath) {
+    return !ModuleToSummariesForIndex ||
+           ModuleToSummariesForIndex->count(ModulePath);
+  }
+
   bool hasValueId(GlobalValue::GUID ValGUID) {
     const auto &VMI = GUIDToValueIdMap.find(ValGUID);
     return VMI != GUIDToValueIdMap.end();
   }
   unsigned getValueId(GlobalValue::GUID ValGUID) {
     const auto &VMI = GUIDToValueIdMap.find(ValGUID);
     // If this GUID doesn't have an entry, assign one.
     if (VMI == GUIDToValueIdMap.end()) {
void IndexBitcodeWriter::writeModStrings() {
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   unsigned AbbrevHash = Stream.EmitAbbrev(Abbv);
 
   SmallVector<unsigned, 64> Vals;
   for (const auto &MPSE : Index.modulePaths()) {
+    if (!doIncludeModule(MPSE.getKey()))
+      continue;
     StringEncoding Bits =
         getStringEncoding(MPSE.getKey().data(), MPSE.getKey().size());
     unsigned AbbrevToUse = Abbrev8Bit;
     if (Bits == SE_Char6)
       AbbrevToUse = Abbrev6Bit;
     else if (Bits == SE_Fixed7)
       AbbrevToUse = Abbrev7Bit;
 
void IndexBitcodeWriter::writeCombinedGlobalValueSummary() {
   auto MaybeEmitOriginalName = [&](GlobalValueSummary &S) {
     if (!GlobalValue::isLocalLinkage(S.linkage()))
       return;
     NameVals.push_back(S.getOriginalName());
     Stream.EmitRecord(bitc::FS_COMBINED_ORIGINAL_NAME, NameVals);
     NameVals.clear();
   };
 
-  for (const auto &GSI : Index) {
-    for (auto &SI : GSI.second) {
-      GlobalValueSummary *S = SI.get();
-      assert(S);
+  for (const auto &I : *this) {
+    GlobalValueSummary *S = I.second;
 
-      assert(hasValueId(GSI.first));
-      unsigned ValueId = getValueId(GSI.first);
-      SummaryToValueIdMap[S] = ValueId;
+    assert(hasValueId(I.first));
+    unsigned ValueId = getValueId(I.first);
 
-      if (auto *AS = dyn_cast<AliasSummary>(S)) {
-        // Will process aliases as a post-pass because the reader wants all
-        // global to be loaded first.
-        Aliases.push_back(AS);
-        continue;
-      }
 
-      if (auto *VS = dyn_cast<GlobalVarSummary>(S)) {
-        NameVals.push_back(ValueId);
-        NameVals.push_back(Index.getModuleId(VS->modulePath()));
-        NameVals.push_back(getEncodedGVSummaryFlags(VS->flags()));
-        for (auto &RI : VS->refs()) {
-          NameVals.push_back(getValueId(RI.getGUID()));
-        }
 
-        // Emit the finished record.
-        Stream.EmitRecord(bitc::FS_COMBINED_GLOBALVAR_INIT_REFS, NameVals,
-                          FSModRefsAbbrev);
-        NameVals.clear();
-        MaybeEmitOriginalName(*S);
-        continue;
-      }
 
-      auto *FS = cast<FunctionSummary>(S);
-      NameVals.push_back(ValueId);
-      NameVals.push_back(Index.getModuleId(FS->modulePath()));
-      NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
-      NameVals.push_back(FS->instCount());
-      NameVals.push_back(FS->refs().size());
 
-      for (auto &RI : FS->refs()) {
-        NameVals.push_back(getValueId(RI.getGUID()));
-      }
 
-      bool HasProfileData = false;
-      for (auto &EI : FS->calls()) {
-        HasProfileData |= EI.second.ProfileCount != 0;
-        if (HasProfileData)
-          break;
-      }
 
-      for (auto &EI : FS->calls()) {
-        // If this GUID doesn't have a value id, it doesn't have a function
-        // summary and we don't need to record any calls to it.
-        if (!hasValueId(EI.first.getGUID()))
-          continue;
-        NameVals.push_back(getValueId(EI.first.getGUID()));
-        assert(EI.second.CallsiteCount > 0 && "Expected at least one callsite");
-        NameVals.push_back(EI.second.CallsiteCount);
-        if (HasProfileData)
-          NameVals.push_back(EI.second.ProfileCount);
-      }
 
-      unsigned FSAbbrev =
-          (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev);
-      unsigned Code =
-          (HasProfileData ? bitc::FS_COMBINED_PROFILE : bitc::FS_COMBINED);
+    unsigned FSAbbrev = (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev);
 
-      // Emit the finished record.
-      Stream.EmitRecord(Code, NameVals, FSAbbrev);
-      NameVals.clear();
-      MaybeEmitOriginalName(*S);
-    }
-  }
 
   for (auto *AS : Aliases) {
     auto AliasValueId = SummaryToValueIdMap[AS];
     assert(AliasValueId);
     NameVals.push_back(AliasValueId);
     NameVals.push_back(Index.getModuleId(AS->modulePath()));
     NameVals.push_back(getEncodedGVSummaryFlags(AS->flags()));
     auto AliaseeValueId = SummaryToValueIdMap[&AS->getAliasee()];
void IndexBitcodeWriter::writeIndex() {
   // real VST and real values when this is invoked).
   writeCombinedValueSymbolTable();
 
   Stream.ExitBlock();
 }
 
 // Write the specified module summary 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 for ThinLTO.
-void llvm::WriteIndexToFile(const ModuleSummaryIndex &Index, raw_ostream &Out) {
+// writing the combined index file for ThinLTO. When writing a subset of the
+// index for a distributed backend, provide a \p ModuleToSummariesForIndex map.
+void llvm::WriteIndexToFile(
+    const ModuleSummaryIndex &Index, raw_ostream &Out,
+    std::map<StringRef, GVSummaryMapTy> *ModuleToSummariesForIndex) {
   SmallVector<char, 0> Buffer;
   Buffer.reserve(256 * 1024);
 
-  IndexBitcodeWriter IndexWriter(Buffer, Index);
+  IndexBitcodeWriter IndexWriter(Buffer, Index, ModuleToSummariesForIndex);
   IndexWriter.write();
 
   Out.write((char *)&Buffer.front(), Buffer.size());
 }

test/tools/gold/X86/thinlto.ll

 ; RUN: opt -module-summary %s -o %t.o
 ; RUN: opt -module-summary %p/Inputs/thinlto.ll -o %t2.o
 
 ; Ensure gold generates an index and not a binary if requested.
 ; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \
 ; RUN:    --plugin-opt=thinlto \
 ; RUN:    --plugin-opt=thinlto-index-only \
 ; RUN:    -shared %t.o %t2.o -o %t3
-; RUN: llvm-bcanalyzer -dump %t3.thinlto.bc | FileCheck %s --check-prefix=COMBINED
+; RUN: llvm-bcanalyzer -dump %t.o.thinlto.bc | FileCheck %s --check-prefix=BACKEND1
+; RUN: llvm-bcanalyzer -dump %t2.o.thinlto.bc | FileCheck %s --check-prefix=BACKEND2
 ; RUN: not test -e %t3
 
 ; Ensure gold generates an index as well as a binary by default in ThinLTO mode.
 ; First force single-threaded mode
 ; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \
 ; RUN:    --plugin-opt=thinlto \
 ; RUN:    --plugin-opt=jobs=1 \
 ; RUN:    -shared %t.o %t2.o -o %t4

 ; RUN:    --plugin-opt=obj-path=%t5.o \
 ; RUN:    -shared %t.o %t2.o -o %t4
 ; RUN: llvm-nm %t5.o0 | FileCheck %s --check-prefix=NM2
 ; RUN: llvm-nm %t5.o1 | FileCheck %s --check-prefix=NM2
 
 ; NM: T f
 ; NM2: T {{f|g}}
 
+; The backend index for this module contains summaries from itself and
+; Inputs/thinlto.ll, as it imports from the latter.
+; BACKEND1: <MODULE_STRTAB_BLOCK
+; BACKEND1-NEXT: <ENTRY {{.*}} record string = '{{.*}}/test/tools/gold/X86/Output/thinlto.ll.tmp{{.*}}.o'
+; BACKEND1-NEXT: <ENTRY {{.*}} record string = '{{.*}}/test/tools/gold/X86/Output/thinlto.ll.tmp{{.*}}.o'
+; BACKEND1-NEXT: </MODULE_STRTAB_BLOCK
+; BACKEND1-NEXT: <GLOBALVAL_SUMMARY_BLOCK
+; BACKEND1-NEXT: <VERSION
+; BACKEND1-NEXT: <COMBINED
+; BACKEND1-NEXT: <COMBINED
+; BACKEND1-NEXT: </GLOBALVAL_SUMMARY_BLOCK
+; BACKEND1-NEXT: <VALUE_SYMTAB
+; Check that the format is: op0=valueid, op1=offset, op2=funcguid,
+; where funcguid is the lower 64 bits of the function name MD5.
+; BACKEND1-NEXT: <COMBINED_ENTRY abbrevid={{[0-9]+}} op0={{1|2}} op1={{-3706093650706652785|-5300342847281564238}}
+; BACKEND1-NEXT: <COMBINED_ENTRY abbrevid={{[0-9]+}} op0={{1|2}} op1={{-3706093650706652785|-5300342847281564238}}
+; BACKEND1-NEXT: </VALUE_SYMTAB
+
+; The backend index for Input/thinlto.ll contains summaries from itself only,
+; as it does not import anything.
+; BACKEND2: <MODULE_STRTAB_BLOCK
+; BACKEND2-NEXT: <ENTRY {{.*}} record string = '{{.*}}/test/tools/gold/X86/Output/thinlto.ll.tmp2.o'
+; BACKEND2-NEXT: </MODULE_STRTAB_BLOCK
+; BACKEND2-NEXT: <GLOBALVAL_SUMMARY_BLOCK
+; BACKEND2-NEXT: <VERSION
+; BACKEND2-NEXT: <COMBINED
+; BACKEND2-NEXT: </GLOBALVAL_SUMMARY_BLOCK
+; BACKEND2-NEXT: <VALUE_SYMTAB
+; Check that the format is: op0=valueid, op1=offset, op2=funcguid,
+; where funcguid is the lower 64 bits of the function name MD5.
+; BACKEND2-NEXT: <COMBINED_ENTRY abbrevid={{[0-9]+}} op0=1 op1=-5300342847281564238
+; BACKEND2-NEXT: </VALUE_SYMTAB
+
 ; COMBINED: <MODULE_STRTAB_BLOCK
 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}/test/tools/gold/X86/Output/thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}/test/tools/gold/X86/Output/thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: </MODULE_STRTAB_BLOCK
 ; COMBINED-NEXT: <GLOBALVAL_SUMMARY_BLOCK
 ; COMBINED-NEXT: <VERSION
 ; COMBINED-NEXT: <COMBINED
 ; COMBINED-NEXT: <COMBINED

tools/gold/gold-plugin.cpp

 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/ThreadPool.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/thread.h"
 #include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/IPO/FunctionImport.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
 #include "llvm/Transforms/Utils/GlobalStatus.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include <list>
 #include <plugin-api.h>
 #include <system_error>
 #include <vector>
#endif
   static std::string triple;
   static std::string mcpu;
   // When the thinlto plugin option is specified, only read the function
   // the information from intermediate files and write a combined
   // global index for the ThinLTO backends.
   static bool thinlto = false;
   // If false, all ThinLTO backend compilations through code gen are performed
   // using multiple threads in the gold-plugin, before handing control back to
-  // gold. If true, exit after creating the combined index, the assuming is
+  // gold. If true, write individual backend index files which reflect
+  // the import decisions, and exit afterwards. The assumption is
   // that the build system will launch the backend processes.
   static bool thinlto_index_only = false;
   // Additional options to pass into the code generator.
   // Note: This array will contain all plugin options which are not claimed
   // as plugin exclusive to pass to the code generator.
   // For example, "generate-api-file" and "as"options are for the plugin
   // use only and will not be passed.
   static std::vector<const char *> extra;
for (claimed_file &F : Modules) {
       std::unique_ptr<ModuleSummaryIndex> Index =
           getModuleSummaryIndexForFile(F, InputFile.file());
 
       // Skip files without a module summary.
       if (Index)
         CombinedIndex.mergeFrom(std::move(Index), ++NextModuleId);
     }
 
+    if (options::thinlto_index_only) {
+      // Collect for each module the list of function it defines (GUID ->
+      // Summary).
+      StringMap<std::map<GlobalValue::GUID, GlobalValueSummary *>>
+          ModuleToDefinedGVSummaries(NextModuleId);
+      CombinedIndex.collectDefinedGVSummariesPerModule(
+          ModuleToDefinedGVSummaries);
+
+      // FIXME: We want to do this for the case where the threads are launched
+      // from gold as well, in which case this will be moved out of the
+      // thinlto_index_only handling, and the function importer will be invoked
+      // directly using the Lists.
+      StringMap<FunctionImporter::ImportMapTy> ImportLists(NextModuleId);
+      StringMap<FunctionImporter::ExportSetTy> ExportLists(NextModuleId);
+      ComputeCrossModuleImport(CombinedIndex, ModuleToDefinedGVSummaries,
+                               ImportLists, ExportLists);
+
+      // For each input bitcode file, generate an individual index that
+      // contains summaries only for its own global values, and for any that
+      // should be imported.
+      for (claimed_file &F : Modules) {
+        PluginInputFile InputFile(F.handle);
+        std::error_code EC;
+        raw_fd_ostream OS((Twine(InputFile.file().name) + ".thinlto.bc").str(),
+                          EC, sys::fs::OpenFlags::F_None);
+        if (EC)
+          message(LDPL_FATAL, "Unable to open %s.thinlto.bc for writing: %s",
+                  InputFile.file().name, EC.message().c_str());
+        // Build a map of module to the GUIDs and summary objects that should
+        // be written to its index.
+        // Use a std::map instead of StringMap to get stable order for
+        // bitcode emission.
+        std::map<StringRef, GVSummaryMapTy> ModuleToSummariesForIndex;
+        // Include all summaries from the importing module.
+        ModuleToSummariesForIndex[InputFile.file().name] =
+            ModuleToDefinedGVSummaries[InputFile.file().name];
+        auto ModuleImports = ImportLists.find(InputFile.file().name);
+        if (ModuleImports != ImportLists.end()) {
+          // Include summaries for imports.
+          for (auto &ILI : ModuleImports->second) {
+            auto &SummariesForIndex = ModuleToSummariesForIndex[ILI.first()];
+            auto &DefinedGVSummaries = ModuleToDefinedGVSummaries[ILI.first()];
+            for (auto &GI : ILI.second) {
+              SummariesForIndex[GI.first] = DefinedGVSummaries[GI.first];
+            }
+          }
+        }
+        WriteIndexToFile(CombinedIndex, OS, &ModuleToSummariesForIndex);
+      }
+
+      cleanup_hook();
+      exit(0);
+    }
+
+    // Create OS in nested scope so that it will be closed on destruction.
+    {
       std::error_code EC;
       raw_fd_ostream OS(output_name + ".thinlto.bc", EC,
                         sys::fs::OpenFlags::F_None);
       if (EC)
         message(LDPL_FATAL, "Unable to open %s.thinlto.bc for writing: %s",
                 output_name.data(), EC.message().c_str());
       WriteIndexToFile(CombinedIndex, OS);
-    OS.close();
-
-    if (options::thinlto_index_only) {
-      cleanup_hook();
-      exit(0);
     }
 
     thinLTOBackends(ApiFile, CombinedIndex);
     return LDPS_OK;
   }
 
   LLVMContext Context;
   Context.setDiscardValueNames(options::TheOutputType !=