IPO: Introduce ThinLTOBitcodeWriter pass.

[pcc]

Summary

This pass prepares a module containing type metadata for ThinLTO by splitting
it into regular and thin LTO parts if possible, and writing both parts to
a multi-module bitcode file. Modules that do not contain type metadata are
written unmodified as a single module.

All globals with type metadata are added to the regular LTO module, and
the rest are added to the thin LTO module.

[tejohnson]

Just skimmed the code so far, and have a high-level question. Why a new pass instead of building this into the existing WriteBitcodePass as an option? It's confusing because that pass also has the ability to write bitcode for ThinLTO. Is the intention to use this new pass instead of WriteBitcodePass when we are building with -flto=thin (i.e. from clang)? Seems cleaner to use a single pass and not have clang worry about which to invoke. Also avoids redundancy in the ThinLTO handling.

llvm/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

202

The WriteBitcodePass instead uses the ModuleSummaryIndexAnalysis pass to construct the index. This pass should be consistent with that.

[pcc]

In D27324#611918, @tejohnson wrote:

Just skimmed the code so far, and have a high-level question. Why a new pass instead of building this into the existing WriteBitcodePass as an option?

I see the WriteBitcodePass as a "pure" serialization pass, whereas this pass will do whatever is required to write out the module for ThinLTO. I also see this pass as potentially diverging a lot from WriteBitcodePass, e.g. it could be doing code generation for non-importable functions (as I think we discussed a long time ago), which is way outside the bounds of what WriteBitcodePass is or should be doing.

It's confusing because that pass also has the ability to write bitcode for ThinLTO.

To a certain extent that's coincidental to the pass's ability to write a summary. I suspect that we'll just want to use that capability in "opt" for testing purposes and use this new pass in production pipelines.

Is the intention to use this new pass instead of WriteBitcodePass when we are building with -flto=thin (i.e. from clang)?

Yes.

Seems cleaner to use a single pass and not have clang worry about which to invoke.

In the end some code does need to make some choice about which code path to take. The question is whether we want separate passes or one pass that does everything and takes a ton of flags. It may come down to personal preference but at least I think that avoiding flags where possible makes the code more readable.

Also avoids redundancy in the ThinLTO handling.

It's not a lot of code to be honest, most of the implementation is in BitcodeWriter which is already shared.

llvm/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

202

Note that this is a separate module from the "main" module. We can't just use the main module summary from the pass manager because we may have renamed some of the globals to export them. Running a separate pass manager on the newly created module to build the summary also seems like the wrong approach, as I mentioned in the FIXME I think we'll eventually want to pull profiling information out of the main module analysis and match it up with the globals in ThinM. That would require going outside the bounds of what the pass manager supports (or needs to support, I'd argue).

[mehdi_amini]

Another high-level comment: technically I don't think we need to split anything for type-based LTO devirtualization.

[pcc]

In D27324#612009, @mehdi_amini wrote:

Another high-level comment: technically I don't think we need to split anything for type-based LTO devirtualization.

It may be possible to implement vcall opt without splitting, but it certainly seems a lot more complicated. For example virtual const prop works by "evaluating" each virtual function; we'd somehow need to figure out which virtual functions can be evaluated and store the values in the summary.

[mehdi_amini]

Not reading any IR during ThinLTO is important, only if we really can do differently I'd consider it. But I'd look at every options/tradeoff before and make sure the design does not lock us in.

[pcc]

In D27324#612038, @mehdi_amini wrote:

Not reading any IR during ThinLTO is important, only if we really can do differently I'd consider it. But I'd look at every options/tradeoff before and make sure the design does not lock us in.

I intend the amount of IR we read during ThinLTO to be minimal. Basically just the vtables and a small number of virtual functions (for vcall opt). The fact that we're reading IR seems less important than that we're reading less of it; I don't want to be in a situation where we keep adding things to the summary only to discover that we've just reinvented parts of the IR and we're just reading it via a "summary" code path.

[pcc]

In D27324#612053, @pcc wrote:

In D27324#612038, @mehdi_amini wrote:

Not reading any IR during ThinLTO is important, only if we really can do differently I'd consider it. But I'd look at every options/tradeoff before and make sure the design does not lock us in.

I intend the amount of IR we read during ThinLTO to be minimal. Basically just the vtables and a small number of virtual functions (for vcall opt). The fact that we're reading IR seems less important than that we're reading less of it; I don't want to be in a situation where we keep adding things to the summary only to discover that we've just reinvented parts of the IR and we're just reading it via a "summary" code path.

(and incidentally, this is part of why I've been pushing on the typeless pointer work lately; it would allow us to strip a lot of useless data from the IR in these cases)

[tejohnson]

In D27324#611987, @pcc wrote:

In D27324#611918, @tejohnson wrote:

Just skimmed the code so far, and have a high-level question. Why a new pass instead of building this into the existing WriteBitcodePass as an option?

I see the WriteBitcodePass as a "pure" serialization pass, whereas this pass will do whatever is required to write out the module for ThinLTO. I also see this pass as potentially diverging a lot from WriteBitcodePass, e.g. it could be doing code generation for non-importable functions (as I think we discussed a long time ago), which is way outside the bounds of what WriteBitcodePass is or should be doing.

It's confusing because that pass also has the ability to write bitcode for ThinLTO.

To a certain extent that's coincidental to the pass's ability to write a summary. I suspect that we'll just want to use that capability in "opt" for testing purposes and use this new pass in production pipelines.

Why would we want to write ThinLTO bitcode one way in opt and another way in the production pipelines? I think we should keep it simple and have one way to write the ThinLTO bitcode.

Is the intention to use this new pass instead of WriteBitcodePass when we are building with -flto=thin (i.e. from clang)?

Yes.

Seems cleaner to use a single pass and not have clang worry about which to invoke.

In the end some code does need to make some choice about which code path to take. The question is whether we want separate passes or one pass that does everything and takes a ton of flags. It may come down to personal preference but at least I think that avoiding flags where possible makes the code more readable.

But I assume the intention is to always do this under -flto=thin, in which case there's just one parameter, analogous to the existing BitcodeWriterPass's EmitSummaryIndex. I have less of a strong feeling about having this as a separate pass though if we can (eventually) remove the existing ThinLTO handling from BitcodeWriterPass. But I would imagine the splitting should stay optional for the time being.

llvm/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

202

Ok, that makes sense.

[tejohnson]

In D27324#612037, @pcc wrote:

In D27324#612009, @mehdi_amini wrote:

Another high-level comment: technically I don't think we need to split anything for type-based LTO devirtualization.

It may be possible to implement vcall opt without splitting, but it certainly seems a lot more complicated. For example virtual const prop works by "evaluating" each virtual function; we'd somehow need to figure out which virtual functions can be evaluated and store the values in the summary.

I haven't thought through this, but is it possible to evaluate the virtual functions at compile time (without WPA)? I.e. is the issue deciding which virtual functions can be evaluated, doing the evaluation, or how to store that in the summary?

[pcc]

In D27324#612112, @tejohnson wrote:

In D27324#611987, @pcc wrote:

In D27324#611918, @tejohnson wrote:

Just skimmed the code so far, and have a high-level question. Why a new pass instead of building this into the existing WriteBitcodePass as an option?

I see the WriteBitcodePass as a "pure" serialization pass, whereas this pass will do whatever is required to write out the module for ThinLTO. I also see this pass as potentially diverging a lot from WriteBitcodePass, e.g. it could be doing code generation for non-importable functions (as I think we discussed a long time ago), which is way outside the bounds of what WriteBitcodePass is or should be doing.

It's confusing because that pass also has the ability to write bitcode for ThinLTO.

To a certain extent that's coincidental to the pass's ability to write a summary. I suspect that we'll just want to use that capability in "opt" for testing purposes and use this new pass in production pipelines.

Why would we want to write ThinLTO bitcode one way in opt and another way in the production pipelines? I think we should keep it simple and have one way to write the ThinLTO bitcode.

The idea was to allow testing something about the summary writer in isolation without worrying about the rest of the pipeline.

Is the intention to use this new pass instead of WriteBitcodePass when we are building with -flto=thin (i.e. from clang)?

Yes.

Seems cleaner to use a single pass and not have clang worry about which to invoke.

In the end some code does need to make some choice about which code path to take. The question is whether we want separate passes or one pass that does everything and takes a ton of flags. It may come down to personal preference but at least I think that avoiding flags where possible makes the code more readable.

But I assume the intention is to always do this under -flto=thin, in which case there's just one parameter, analogous to the existing BitcodeWriterPass's EmitSummaryIndex. I have less of a strong feeling about having this as a separate pass though if we can (eventually) remove the existing ThinLTO handling from BitcodeWriterPass. But I would imagine the splitting should stay optional for the time being.

The idea is that splitting would only happen if you have enabled a feature that needs it (that's what requiresSplit is testing for), so there should be no functional change for existing users once we switch clang to using ThinLTOBitcodeWriterPass.

I'm not sure if this is a good idea yet, but maybe there should just be two bitcode writer passes: LTOBitcodeWriterPass and ThinLTOBitcodeWriterPass. Neither would take flags, and basically they would be the only supported "production" passes for writing LTO bitcode. If something like "opt" wants to go under the hood and test a specific feature of the bitcode writer (e.g. the summary writer), it can run a pass pipeline without a bitcode writer and call the writer itself.

[pcc]

In D27324#612128, @tejohnson wrote:

In D27324#612037, @pcc wrote:

In D27324#612009, @mehdi_amini wrote:

Another high-level comment: technically I don't think we need to split anything for type-based LTO devirtualization.

It may be possible to implement vcall opt without splitting, but it certainly seems a lot more complicated. For example virtual const prop works by "evaluating" each virtual function; we'd somehow need to figure out which virtual functions can be evaluated and store the values in the summary.

I haven't thought through this, but is it possible to evaluate the virtual functions at compile time (without WPA)? I.e. is the issue deciding which virtual functions can be evaluated, doing the evaluation, or how to store that in the summary?

I think it's more doing the evaluation. Basically we support virtual const prop on functions which take arguments that are constant at the call site. Currently this works by scanning the module for calls and evaluating the function for each set of constant arguments that are actually passed. To make this work on a whole program basis we'd either need to evaluate functions with every possible set of arguments (probably too expensive in non-trivial cases) or somehow encode the function body in the "summary" (which at that point wouldn't really be a summary at all).

[mehdi_amini]

(at this point I agree with Teresa on the structure of the writer, it is not clear to me why changing it)

[tejohnson]

In D27324#612167, @pcc wrote:

In D27324#612128, @tejohnson wrote:

In D27324#612037, @pcc wrote:

In D27324#612009, @mehdi_amini wrote:

Another high-level comment: technically I don't think we need to split anything for type-based LTO devirtualization.

It may be possible to implement vcall opt without splitting, but it certainly seems a lot more complicated. For example virtual const prop works by "evaluating" each virtual function; we'd somehow need to figure out which virtual functions can be evaluated and store the values in the summary.

I haven't thought through this, but is it possible to evaluate the virtual functions at compile time (without WPA)? I.e. is the issue deciding which virtual functions can be evaluated, doing the evaluation, or how to store that in the summary?

I think it's more doing the evaluation. Basically we support virtual const prop on functions which take arguments that are constant at the call site. Currently this works by scanning the module for calls and evaluating the function for each set of constant arguments that are actually passed. To make this work on a whole program basis we'd either need to evaluate functions with every possible set of arguments (probably too expensive in non-trivial cases) or somehow encode the function body in the "summary" (which at that point wouldn't really be a summary at all).

Or encode as a function based on TBD const param values, and encode callsite constant param values in the summary...ok I agree that this is more complex that needed at least for now. It seems simpler to do the splitting for now.

[pcc]

Mehdi asked me to look at the cost of the split module design. To do that, I took my prototype [0] and made a change [1] to shrink the size of the regular LTO module. With that the total time spent in LTO::addRegularLTO and LTO::addThinLTO on my machine during a ThinLTO link of Chromium is:

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
 6.1434 ( 58.6%)   0.2158 ( 36.2%)   6.3591 ( 57.4%)   6.1709 ( 55.6%)  LTO::addRegularLTO
 4.3320 ( 41.4%)   0.3805 ( 63.8%)   4.7125 ( 42.6%)   4.9269 ( 44.4%)  LTO::addThinLTO
10.4754 (100.0%)   0.5963 (100.0%)  11.0717 (100.0%)  11.0978 (100.0%)  Total

So that's about 6 seconds spent loading and linking all of Chromium's vtables, as compared to 5 seconds spent building the combined summary. If the figures were an order of magnitude off I'd be concerned, but these figures seem reasonable enough to me.

[0] https://github.com/pcc/llvm-project/tree/cfi-thinlto
[1] https://github.com/pcc/llvm-project/commit/de5bd8fe4c05c6e9aecf1e5384ef5553bf7332f0

[mehdi_amini]

Does this include all the codegen as well?

Also, what is the story for incremental build with respect to ThinLTO devirtualization?

[pcc]

In D27324#613922, @mehdi_amini wrote:

Does this include all the codegen as well?

No, I'll measure that as well.

Also, what is the story for incremental build with respect to ThinLTO devirtualization?

Basically we want to cache the combined module and the part of the combined summary that contains the resolutions for each of the type tests. The cache would be keyed on the regular LTO module hashes. We'd only copy the needed resolutions into the individual summaries like we do for the import/export lists.

[pcc]

Basically we want to cache the combined module

By which I mean the object file representing the combined module, sorry.

[mehdi_amini]

In D27324#613959, @pcc wrote:

Basically we want to cache the combined module

By which I mean the object file representing the combined module, sorry.

I'm not totally sure about this (the time to hash the IR may be almost as long as the codegen for this module if it contains "only" the Vtables). But that's a detail that can be tuned later.

I'm more interested to understand the flow of devirtualization in particular. How do we know which type resolution impact which ThinLTO backend?
I haven't all the pieces of the flow yet.

[pcc]

In D27324#613964, @mehdi_amini wrote:

In D27324#613959, @pcc wrote:

Basically we want to cache the combined module

By which I mean the object file representing the combined module, sorry.

I'm not totally sure about this (the time to hash the IR may be almost as long as the codegen for this module if it contains "only" the Vtables). But that's a detail that can be tuned later.

At least the LowerTypeTests pass needed for CFI can get expensive, so I'd like to be able to cache its output. But it may be possible to optimize that pass further (the pass hasn't historically shown up in profiles simply because it was being run along with the other regular LTO passes), so ok, let's think about what to do about it later.

FWIW for hashing I was thinking that we'd just read the MODULE_CODE_HASH.

I'm more interested to understand the flow of devirtualization in particular. How do we know which type resolution impact which ThinLTO backend?
I haven't all the pieces of the flow yet.

This was discussed on the original RFC thread, and the conclusion was at the end of this message:
http://lists.llvm.org/pipermail/llvm-dev/2016-October/106628.html
Basically the information is stored in the individual summaries.

[pcc]

Here are the results after applying https://github.com/pcc/llvm-project/commit/07bc98867d232add3bd823a7e6e0b1257ff836ca to collect more timing information:

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
190.1413 ( 94.1%)   1.2036 ( 59.0%)  191.3449 ( 93.8%)  191.2808 ( 93.8%)  lto::backend opt
 6.3190 (  3.1%)   0.2526 ( 12.4%)   6.5716 (  3.2%)   6.2862 (  3.1%)  LTO::addRegularLTO
 4.5287 (  2.2%)   0.3791 ( 18.6%)   4.9079 (  2.4%)   5.1791 (  2.5%)  LTO::addThinLTO
 1.0622 (  0.5%)   0.2041 ( 10.0%)   1.2663 (  0.6%)   1.2656 (  0.6%)  lto::backend codegen
202.0513 (100.0%)   2.0394 (100.0%)  204.0907 (100.0%)  204.0117 (100.0%)  Total

In other words: as expected, most of the regular LTO time is being spent in the optimizer, and the time spent in the backend is quite small.

[mehdi_amini]

What does the 190s in the optimizer correspond to? (i.e. is it only building the combined "vtables module"?)

[pcc]

In D27324#613981, @mehdi_amini wrote:

What does the 190s in the optimizer correspond to? (i.e. is it only building the combined "vtables module"?)

Yes, that's the "vtables module". Note that it's probably just the LowerTypeTests pass being slow.

[mehdi_amini]

Ouch, that seems *huge* to me.

[pcc]

In D27324#613985, @mehdi_amini wrote:

Ouch, that seems *huge* to me.

As mentioned on IRC: the time spent in the midend is CFI-specific (and necessarily sequential), and I'm going to be looking at optimizing it anyway. The parts that would have similar timings regardless of CFI/devirtualization settings are "LTO::addRegularLTO" and "lto::backend codegen", and I'm satisfied with the timings for those parts.

[pcc]

After D27484 (actually a slightly different version of that patch rebased onto my prototype branch) the timings look like this:

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
 5.8192 ( 40.7%)   0.1061 ( 17.5%)   5.9253 ( 39.8%)   5.6562 ( 37.7%)  LTO::addRegularLTO
 3.9290 ( 27.5%)   0.2029 ( 33.5%)   4.1319 ( 27.7%)   4.4836 ( 29.9%)  LTO::addThinLTO
 3.6604 ( 25.6%)   0.1720 ( 28.4%)   3.8325 ( 25.7%)   3.8303 ( 25.6%)  lto::backend opt
 0.8909 (  6.2%)   0.1242 ( 20.5%)   1.0151 (  6.8%)   1.0144 (  6.8%)  lto::backend codegen
14.2996 (100.0%)   0.6052 (100.0%)  14.9048 (100.0%)  14.9844 (100.0%)  Total

[mehdi_amini]

It seems like > 100% overhead for an incremental build, right?

[mehdi_amini]

Mmm, no, it does not include the thin-link. So hard to evaluate.

[pcc]

With a timer for the thin-link phase (https://github.com/pcc/llvm-project/commit/9f389f9d1c16c34d32d040cfb55aa69e97d9ad9f) the timings are:

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
 6.2637 ( 28.1%)   0.2148 ( 10.6%)   6.4785 ( 26.7%)   6.2113 ( 25.5%)  LTO::addRegularLTO
 5.1410 ( 23.1%)   0.6442 ( 31.7%)   5.7852 ( 23.8%)   5.7871 ( 23.8%)  LTO::runThinLTO thin-link
 5.1463 ( 23.1%)   0.5565 ( 27.4%)   5.7028 ( 23.5%)   5.7000 ( 23.4%)  lto::backend opt
 4.4082 ( 19.8%)   0.3652 ( 18.0%)   4.7735 ( 19.7%)   5.0972 ( 20.9%)  LTO::addThinLTO
 1.2965 (  5.8%)   0.2523 ( 12.4%)   1.5487 (  6.4%)   1.5487 (  6.4%)  lto::backend codegen
22.2557 (100.0%)   2.0330 (100.0%)  24.2887 (100.0%)  24.3442 (100.0%)  Total

So that's 5.0972 + 5.7871 = 10.8843s for the sequential parts of ThinLTO and 6.2113 + 5.7000 + 1.5487 = 13.4600s for regular LTO.

[pcc]

• Drop unused globals, and drop type information from function declarations. This helps improve the performance of the regular LTO link phase.

[mehdi_amini]

llvm/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

73

We call this export "Promotion" in ThinLTO usually I believe.

201

This seems dead code to me, the returned value is return ("$" + Str).str(); which can't be empty.

210

"Regular" was misleading to me, because I see the ThinLTO module as the regular one, the other that only contains the VTable and the types is the "special" one.

211

Should this be a check on GlobalObject instead? Technically GlobalObject can have MDs attached. I guess you assume that we'll never see a typeMD on anything else than a GlobalVariable?

217

Looks like we could have method bool GlobalObject::hasMD(unsigned KindID);

225

I'm concerned about the cost: cloning a module isn't free.
Why do you need to clone the Thin module? Can't you just strip it from what was moved to the other?
Could we just have an option to clone module so that it actually move directly so that it'll do exactly what's needed?

295

} // anonymous namespace

[pcc]

llvm/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

201

See line 63, also the test case unsplittable.ll.

210

Renamed to MergedM.

211

Yes, at this point we only support type metadata on GlobalVariables. We can also have type metadata attached to Functions, which is used to support CFI on indirect calls, but that will be implemented separately (and much differently).

217

It doesn't seem worth it to me, we're basically only doing this in this pass.

225

I added a filterModule function that operates on an existing module and used it here.

[pcc]

• Address review comments

[mehdi_amini]

LGTM.

llvm/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

201

Oh right!

llvm/include/llvm/InitializePasses.h

 void initializeUnreachableBlockElimLegacyPassPass(PassRegistry&);
 void initializeUnreachableMachineBlockElimPass(PassRegistry&);
 void initializeVerifierLegacyPassPass(PassRegistry&);
 void initializeVirtRegMapPass(PassRegistry&);
 void initializeVirtRegRewriterPass(PassRegistry&);
 void initializeWholeProgramDevirtPass(PassRegistry &);
 void initializeWinEHPreparePass(PassRegistry&);
 void initializeWriteBitcodePassPass(PassRegistry &);
+void initializeWriteThinLTOBitcodePass(PassRegistry &);
 void initializeXRayInstrumentationPass(PassRegistry &);
 }
 
 #endif

llvm/include/llvm/Transforms/IPO.h

 struct InlineParams;
 class StringRef;
 class ModuleSummaryIndex;
 class ModulePass;
 class Pass;
 class Function;
 class BasicBlock;
 class GlobalValue;
+class raw_ostream;
 
 //===----------------------------------------------------------------------===//
 //
 // These functions removes symbols from functions and modules.  If OnlyDebugInfo
 // is true, only debugging information is removed from the module.
 //
 ModulePass *createStripSymbolsPass(bool OnlyDebugInfo = false);
 

 ModulePass *createGlobalSplitPass();
 
 //===----------------------------------------------------------------------===//
 // SampleProfilePass - Loads sample profile data from disk and generates
 // IR metadata to reflect the profile.
 ModulePass *createSampleProfileLoaderPass();
 ModulePass *createSampleProfileLoaderPass(StringRef Name);
 
+/// Write ThinLTO-ready bitcode to Str.
+ModulePass *createWriteThinLTOBitcodePass(raw_ostream &Str);
+
 } // End llvm namespace
 
 #endif

llvm/lib/Transforms/IPO/CMakeLists.txt

add_llvm_library(LLVMipo
   LowerTypeTests.cpp
   MergeFunctions.cpp
   PartialInlining.cpp
   PassManagerBuilder.cpp
   PruneEH.cpp
   SampleProfile.cpp
   StripDeadPrototypes.cpp
   StripSymbols.cpp
+  ThinLTOBitcodeWriter.cpp
   WholeProgramDevirt.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/IPO
 
   DEPENDS
   intrinsics_gen
   )

llvm/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

+//===- ThinLTOBitcodeWriter.cpp - Bitcode writing pass for ThinLTO --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass prepares a module containing type metadata for ThinLTO by splitting
+// it into regular and thin LTO parts if possible, and writing both parts to
+// a multi-module bitcode file. Modules that do not contain type metadata are
+// written unmodified as a single module.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO.h"
+#include "llvm/Analysis/ModuleSummaryAnalysis.h"
+#include "llvm/Analysis/TypeMetadataUtils.h"
+#include "llvm/Bitcode/BitcodeWriter.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+using namespace llvm;
+
+namespace {
+
+// Produce a unique identifier for this module by taking the MD5 sum of the
+// names of the module's strong external symbols. This identifier is
+// normally guaranteed to be unique, or the program would fail to link due to
+// multiply defined symbols.
+//
+// If the module has no strong external symbols (such a module may still have a
+// semantic effect if it performs global initialization), we cannot produce a
+// unique identifier for this module, so we return the empty string, which
+// causes the entire module to be written as a regular LTO module.
+std::string getModuleId(Module *M) {
+  MD5 Md5;
+  bool ExportsSymbols = false;
+  auto AddGlobal = [&](GlobalValue &GV) {
+    if (GV.isDeclaration() || GV.getName().startswith("llvm.") ||
+        !GV.hasExternalLinkage())
+      return;
+    ExportsSymbols = true;
+    Md5.update(GV.getName());
+    Md5.update(ArrayRef<uint8_t>{0});
+  };
+
+  for (auto &F : *M)
+    AddGlobal(F);
+  for (auto &GV : M->globals())
+    AddGlobal(GV);
+  for (auto &GA : M->aliases())
+    AddGlobal(GA);
+  for (auto &IF : M->ifuncs())
+    AddGlobal(IF);
+
+  if (!ExportsSymbols)
+    return "";
+
+  MD5::MD5Result R;
+  Md5.final(R);
+
+  SmallString<32> Str;
+  MD5::stringifyResult(R, Str);
+  return ("$" + Str).str();
+}
+
+// Export each local-linkage entity defined by ExportM and used by ImportM by
+// changing visibility and appending the given ModuleId.
+void exportInternals(Module &ExportM, Module &ImportM, StringRef ModuleId) {
+  auto ExportInternal = [&](GlobalValue &ExportGV) {
+    if (!ExportGV.hasLocalLinkage())
+      return;
+
+    GlobalValue *ImportGV = ImportM.getNamedValue(ExportGV.getName());
+    if (!ImportGV || ImportGV->use_empty())
+      return;
+
+    std::string NewName = (ExportGV.getName() + ModuleId).str();
+
+    ExportGV.setName(NewName);
+    ExportGV.setLinkage(GlobalValue::ExternalLinkage);
+    ExportGV.setVisibility(GlobalValue::HiddenVisibility);
+
+    ImportGV->setName(NewName);
+    ImportGV->setVisibility(GlobalValue::HiddenVisibility);
+  };
+
+  for (auto &F : ExportM)
+    ExportInternal(F);
+  for (auto &GV : ExportM.globals())
+    ExportInternal(GV);
+  for (auto &GA : ExportM.aliases())
+    ExportInternal(GA);
+  for (auto &IF : ExportM.ifuncs())
+    ExportInternal(IF);
+}
+
+// Export all internal (i.e. distinct) type ids used by the module by replacing
+// them with external type ids formed using the module id.
+//
+// Note that this needs to be done before we clone the module because each clone
+// will receive its own set of distinct metadata nodes.
+void exportTypeIds(Module &M, StringRef ModuleId) {
+  DenseMap<Metadata *, Metadata *> LocalToGlobal;
+  auto ExternalizeTypeId = [&](CallInst *CI, unsigned ArgNo) {
+    Metadata *MD =
+        cast<MetadataAsValue>(CI->getArgOperand(ArgNo))->getMetadata();
+
+    if (isa<MDNode>(MD) && cast<MDNode>(MD)->isDistinct()) {
+      Metadata *&GlobalMD = LocalToGlobal[MD];
+      if (!GlobalMD) {
+        std::string NewName =
+            (to_string(LocalToGlobal.size()) + ModuleId).str();
+        GlobalMD = MDString::get(M.getContext(), NewName);
+      }
+
+      CI->setArgOperand(ArgNo,
+                        MetadataAsValue::get(M.getContext(), GlobalMD));
+    }
+  };
+
+  if (Function *TypeTestFunc =
+          M.getFunction(Intrinsic::getName(Intrinsic::type_test))) {
+    for (const Use &U : TypeTestFunc->uses()) {
+      auto CI = cast<CallInst>(U.getUser());
+      ExternalizeTypeId(CI, 1);
+    }
+  }
+
+  if (Function *TypeCheckedLoadFunc =
+          M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load))) {
+    for (const Use &U : TypeCheckedLoadFunc->uses()) {
+      auto CI = cast<CallInst>(U.getUser());
+      ExternalizeTypeId(CI, 2);
+    }
+  }
+
+  for (GlobalObject &GO : M.global_objects()) {
+    SmallVector<MDNode *, 1> MDs;
+    GO.getMetadata(LLVMContext::MD_type, MDs);
+
+    GO.eraseMetadata(LLVMContext::MD_type);
+    for (auto MD : MDs) {
+      auto I = LocalToGlobal.find(MD->getOperand(1));
+      if (I == LocalToGlobal.end()) {
+        GO.addMetadata(LLVMContext::MD_type, *MD);
+        continue;
+      }
+      GO.addMetadata(
+          LLVMContext::MD_type,
+          *MDNode::get(M.getContext(),
+                       ArrayRef<Metadata *>{MD->getOperand(0), I->second}));
+    }
+  }
+}
+
+// Drop unused globals, and drop type information from function declarations.
+// FIXME: If we made functions typeless then there would be no need to do this.
+void simplifyExternals(Module &M) {
+  FunctionType *EmptyFT =
+      FunctionType::get(Type::getVoidTy(M.getContext()), false);
+
+  for (auto I = M.begin(), E = M.end(); I != E;) {
+    Function &F = *I++;
+    if (F.isDeclaration() && F.use_empty()) {
+      F.eraseFromParent();
+      continue;
+    }
+
+    if (!F.isDeclaration() || F.getFunctionType() == EmptyFT)
+      continue;
+
+    Function *NewF =
+        Function::Create(EmptyFT, GlobalValue::ExternalLinkage, "", &M);
+    NewF->setVisibility(F.getVisibility());
+    NewF->takeName(&F);
+    F.replaceAllUsesWith(ConstantExpr::getBitCast(NewF, F.getType()));
+    F.eraseFromParent();
+  }
+
+  for (auto I = M.global_begin(), E = M.global_end(); I != E;) {
+    GlobalVariable &GV = *I++;
+    if (GV.isDeclaration() && GV.use_empty()) {
+      GV.eraseFromParent();
+      continue;
+    }
+  }
+}
+
+// If it's possible to split M into regular and thin LTO parts, do so and write
+// a multi-module bitcode file with the two parts to OS. Otherwise, write only a
+// regular LTO bitcode file to OS.
+void splitAndWriteThinLTOBitcode(raw_ostream &OS, Module &M) {
+  std::string ModuleId = getModuleId(&M);
+  if (ModuleId.empty()) {
+    // We couldn't generate a module ID for this module, just write it out as a
+    // regular LTO module.
+    WriteBitcodeToFile(&M, OS);
+    return;
+  }
+
+  exportTypeIds(M, ModuleId);
+
+  auto IsInRegularM = [&](const GlobalValue *GV) {
+    auto *GVar = dyn_cast<GlobalVariable>(GV->getBaseObject());
+    if (!GVar)
+      return false;
+
+    SmallVector<MDNode *, 1> MDs;
+    GVar->getMetadata(LLVMContext::MD_type, MDs);
+    return !MDs.empty();
+  };
+
+  ValueToValueMapTy VMap1;
+  std::unique_ptr<Module> RegularM(CloneModule(&M, VMap1, IsInRegularM));
+
+  ValueToValueMapTy VMap2;
+  std::unique_ptr<Module> ThinM(CloneModule(
+      &M, VMap2, [&](const GlobalValue *GV) { return !IsInRegularM(GV); }));
+
+  exportInternals(*RegularM, *ThinM, ModuleId);
+  exportInternals(*ThinM, *RegularM, ModuleId);
+
+  simplifyExternals(*RegularM);
+
+  SmallVector<char, 0> Buffer;
+  BitcodeWriter W(Buffer);
+
+  // FIXME: Try to re-use BSI and PFI from the original module here.
+  ModuleSummaryIndex Index = buildModuleSummaryIndex(*ThinM, nullptr, nullptr);
+  W.writeModule(ThinM.get(), /*ShouldPreserveUseListOrder=*/false, &Index,
+                /*GenerateHash=*/true);
+
+  W.writeModule(RegularM.get());
+
+  OS << Buffer;
+}
+
+// Returns whether this module needs to be split because it uses type metadata.
+bool requiresSplit(Module &M) {
+  SmallVector<MDNode *, 1> MDs;
+  for (auto &GO : M.global_objects()) {
+    GO.getMetadata(LLVMContext::MD_type, MDs);
+    if (!MDs.empty())
+      return true;
+  }
+
+  return false;
+}
+
+void writeThinLTOBitcode(raw_ostream &OS, Module &M,
+                         const ModuleSummaryIndex *Index) {
+  // See if this module has any type metadata. If so, we need to split it.
+  if (requiresSplit(M))
+    return splitAndWriteThinLTOBitcode(OS, M);
+
+  // Otherwise we can just write it out as a regular module.
+  WriteBitcodeToFile(&M, OS, /*ShouldPreserveUseListOrder=*/false, Index,
+                     /*GenerateHash=*/true);
+}
+
+class WriteThinLTOBitcode : public ModulePass {
+  raw_ostream &OS; // raw_ostream to print on
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+  WriteThinLTOBitcode() : ModulePass(ID), OS(dbgs()) {
+    initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
+  }
+
+  explicit WriteThinLTOBitcode(raw_ostream &o)
+      : ModulePass(ID), OS(o) {
+    initializeWriteThinLTOBitcodePass(*PassRegistry::getPassRegistry());
+  }
+
+  StringRef getPassName() const override { return "ThinLTO Bitcode Writer"; }
+
+  bool runOnModule(Module &M) override {
+    const ModuleSummaryIndex *Index =
+        &(getAnalysis<ModuleSummaryIndexWrapperPass>().getIndex());
+    writeThinLTOBitcode(OS, M, Index);
+    return true;
+  }
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+    AU.addRequired<ModuleSummaryIndexWrapperPass>();
+  }
+};
+}
+
+char WriteThinLTOBitcode::ID = 0;
+INITIALIZE_PASS_BEGIN(WriteThinLTOBitcode, "write-thinlto-bitcode",
+                      "Write ThinLTO Bitcode", false, true)
+INITIALIZE_PASS_DEPENDENCY(ModuleSummaryIndexWrapperPass)
+INITIALIZE_PASS_END(WriteThinLTOBitcode, "write-thinlto-bitcode",
+                    "Write ThinLTO Bitcode", false, true)
+
+ModulePass *llvm::createWriteThinLTOBitcodePass(raw_ostream &Str) {
+  return new WriteThinLTOBitcode(Str);
+}

llvm/test/Transforms/ThinLTOBitcodeWriter/no-type-md.ll

+; RUN: opt -thinlto-bc -o %t %s
+; RUN: llvm-dis -o - %t | FileCheck %s
+; RUN: llvm-bcanalyzer -dump %t | FileCheck --check-prefix=BCA %s
+
+; BCA: <GLOBALVAL_SUMMARY_BLOCK
+
+; CHECK: @g = global i8 42
+@g = global i8 42
+
+; CHECK: define void @f()
+define void @f() {
+  ret void
+}

llvm/test/Transforms/ThinLTOBitcodeWriter/split-internal-typeid.ll

+; RUN: opt -thinlto-bc -o %t %s
+; RUN: llvm-modextract -b -n 0 -o %t0 %t
+; RUN: llvm-modextract -b -n 1 -o %t1 %t
+; RUN: not llvm-modextract -b -n 2 -o - %t 2>&1 | FileCheck --check-prefix=ERROR %s
+; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=M0 %s
+; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=M1 %s
+; RUN: llvm-bcanalyzer -dump %t0 | FileCheck --check-prefix=BCA0 %s
+; RUN: llvm-bcanalyzer -dump %t1 | FileCheck --check-prefix=BCA1 %s
+
+; ERROR: llvm-modextract: error: module index out of range; bitcode file contains 2 module(s)
+
+; BCA0: <GLOBALVAL_SUMMARY_BLOCK
+; BCA1-NOT: <GLOBALVAL_SUMMARY_BLOCK
+
+; M0: @g = external global i8{{$}}
+; M1: @g = global i8 42, !type !0, !type !1, !type !2
+@g = global i8 42, !type !1, !type !2, !type !4
+
+; M0: define void @f()
+; M1-NOT: @f()
+define void @f() {
+  ; M0: llvm.type.test{{.*}}metadata !"1$f50b51a12bb012bebbeff978335e34cf"
+  %p = call i1 @llvm.type.test(i8* null, metadata !0)
+  ; M0: llvm.type.checked.load{{.*}}metadata !"2$f50b51a12bb012bebbeff978335e34cf"
+  %q = call {i8*, i1} @llvm.type.checked.load(i8* null, i32 0, metadata !3)
+  ret void
+}
+
+declare i1 @llvm.type.test(i8*, metadata)
+declare {i8*, i1} @llvm.type.checked.load(i8*, i32, metadata)
+
+!0 = distinct !{}
+; M1: !0 = !{i32 0, !"1$f50b51a12bb012bebbeff978335e34cf"}
+!1 = !{i32 0, !0}
+; M1: !1 = !{i32 1, !"1$f50b51a12bb012bebbeff978335e34cf"}
+!2 = !{i32 1, !0}
+
+!3 = distinct !{}
+; M1: !2 = !{i32 0, !"2$f50b51a12bb012bebbeff978335e34cf"}
+!4 = !{i32 0, !3}

llvm/test/Transforms/ThinLTOBitcodeWriter/split-internal1.ll

+; RUN: opt -thinlto-bc -o %t %s
+; RUN: llvm-modextract -b -n 0 -o %t0 %t
+; RUN: llvm-modextract -b -n 1 -o %t1 %t
+; RUN: not llvm-modextract -b -n 2 -o - %t 2>&1 | FileCheck --check-prefix=ERROR %s
+; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=M0 %s
+; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=M1 %s
+; RUN: llvm-bcanalyzer -dump %t0 | FileCheck --check-prefix=BCA0 %s
+; RUN: llvm-bcanalyzer -dump %t1 | FileCheck --check-prefix=BCA1 %s
+
+; ERROR: llvm-modextract: error: module index out of range; bitcode file contains 2 module(s)
+
+; BCA0: <GLOBALVAL_SUMMARY_BLOCK
+; BCA1-NOT: <GLOBALVAL_SUMMARY_BLOCK
+
+; M0: @"g$581d7631532fa146ba4061179da39272" = external hidden global i8{{$}}
+; M1: @"g$581d7631532fa146ba4061179da39272" = hidden global i8 42, !type !0
+@g = internal global i8 42, !type !0
+
+; M0: define i8* @f()
+; M1-NOT: @f()
+define i8* @f() {
+  ; M0: ret i8* @"g$581d7631532fa146ba4061179da39272"
+  ret i8* @g
+}
+
+; M1: !0 = !{i32 0, !"typeid"}
+!0 = !{i32 0, !"typeid"}

llvm/test/Transforms/ThinLTOBitcodeWriter/split-internal2.ll

+; RUN: opt -thinlto-bc -o %t %s
+; RUN: llvm-modextract -b -n 0 -o %t0 %t
+; RUN: llvm-modextract -b -n 1 -o %t1 %t
+; RUN: not llvm-modextract -b -n 2 -o - %t 2>&1 | FileCheck --check-prefix=ERROR %s
+; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=M0 %s
+; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=M1 %s
+; RUN: llvm-bcanalyzer -dump %t0 | FileCheck --check-prefix=BCA0 %s
+; RUN: llvm-bcanalyzer -dump %t1 | FileCheck --check-prefix=BCA1 %s
+
+; ERROR: llvm-modextract: error: module index out of range; bitcode file contains 2 module(s)
+
+; BCA0: <GLOBALVAL_SUMMARY_BLOCK
+; BCA1-NOT: <GLOBALVAL_SUMMARY_BLOCK
+
+; M0: @g = external global void ()*{{$}}
+; M1: @g = global void ()* @"f$13757e0fb71915e385efa4dc9d1e08fd", !type !0
+@g = global void ()* @f, !type !0
+
+; M0: define hidden void @"f$13757e0fb71915e385efa4dc9d1e08fd"()
+; M1: declare hidden void @"f$13757e0fb71915e385efa4dc9d1e08fd"()
+define internal void @f() {
+  call void @f2()
+  ret void
+}
+
+; M0: define internal void @f2()
+define internal void @f2() {
+  ret void
+}
+
+; M1: !0 = !{i32 0, !"typeid"}
+!0 = !{i32 0, !"typeid"}

llvm/test/Transforms/ThinLTOBitcodeWriter/split.ll

+; RUN: opt -thinlto-bc -o %t %s
+; RUN: llvm-modextract -b -n 0 -o %t0 %t
+; RUN: llvm-modextract -b -n 1 -o %t1 %t
+; RUN: not llvm-modextract -b -n 2 -o - %t 2>&1 | FileCheck --check-prefix=ERROR %s
+; RUN: llvm-dis -o - %t0 | FileCheck --check-prefix=M0 %s
+; RUN: llvm-dis -o - %t1 | FileCheck --check-prefix=M1 %s
+; RUN: llvm-bcanalyzer -dump %t0 | FileCheck --check-prefix=BCA0 %s
+; RUN: llvm-bcanalyzer -dump %t1 | FileCheck --check-prefix=BCA1 %s
+
+; ERROR: llvm-modextract: error: module index out of range; bitcode file contains 2 module(s)
+
+; BCA0: <GLOBALVAL_SUMMARY_BLOCK
+; BCA1-NOT: <GLOBALVAL_SUMMARY_BLOCK
+
+; M0: @g = external global i8{{$}}
+; M1: @g = global i8 42, !type !0
+@g = global i8 42, !type !0
+
+; M0: define i8* @f()
+; M1-NOT: @f()
+define i8* @f() {
+  ret i8* @g
+}
+
+; M1: !0 = !{i32 0, !"typeid"}
+!0 = !{i32 0, !"typeid"}

llvm/test/Transforms/ThinLTOBitcodeWriter/unsplittable.ll

+; RUN: opt -thinlto-bc -o %t %s
+; RUN: llvm-dis -o - %t | FileCheck %s
+; RUN: llvm-bcanalyzer -dump %t | FileCheck --check-prefix=BCA %s
+
+; BCA-NOT: <GLOBALVAL_SUMMARY_BLOCK
+
+; CHECK: @llvm.global_ctors = appending global
[e-mail]_ctors = appending global [1 x { i32, void ()* }] [{ i32, void ()* } { i32 65535, void ()* @f }]
+
+; CHECK: @g = internal global i8 42, !type !0
+@g = internal global i8 42, !type !0
+
+declare void @sink(i8*)
+
+; CHECK: define internal void @f()
+define internal void @f() {
+  call void @sink(i8* @g)
+  ret void
+}
+
+!0 = !{i32 0, !"typeid"}

llvm/tools/opt/opt.cpp

 static cl::opt<bool>
 NoOutput("disable-output",
          cl::desc("Do not write result bitcode file"), cl::Hidden);
 
 static cl::opt<bool>
 OutputAssembly("S", cl::desc("Write output as LLVM assembly"));
 
 static cl::opt<bool>
+    OutputThinLTOBC("thinlto-bc",
+                    cl::desc("Write output as ThinLTO-ready bitcode"));
+
+static cl::opt<bool>
 NoVerify("disable-verify", cl::desc("Do not run the verifier"), cl::Hidden);
 
 static cl::opt<bool>
 VerifyEach("verify-each", cl::desc("Verify after each transform"));
 
 static cl::opt<bool>
     DisableDITypeMap("disable-debug-info-type-map",
                      cl::desc("Don't use a uniquing type map for debug info"));
if (RunTwice) {
       OS = BOS.get();
     }
     if (OutputAssembly) {
       if (EmitSummaryIndex)
         report_fatal_error("Text output is incompatible with -module-summary");
       if (EmitModuleHash)
         report_fatal_error("Text output is incompatible with -module-hash");
       Passes.add(createPrintModulePass(*OS, "", PreserveAssemblyUseListOrder));
-    } else
+    } else if (OutputThinLTOBC)
+      Passes.add(createWriteThinLTOBitcodePass(*OS));
+    else
       Passes.add(createBitcodeWriterPass(*OS, PreserveBitcodeUseListOrder,
                                          EmitSummaryIndex, EmitModuleHash));
   }
 
   // Before executing passes, print the final values of the LLVM options.
   cl::PrintOptionValues();
 
   // If requested, run all passes again with the same pass manager to catch