Metadata mapping for ThinLTO

[tejohnson]

Summary

Maps metadata as a post-pass from each module when importing complete,
suturing up final metadata to the temporary metadata left on the imported
instructions.

This entails saving the mapping from bitcode value id to temporary
metadata in the importing pass, and from bitcode value id to final
metadata during the metadata linking postpass.

Also, to avoid needing to parse the module level metadata during
function importing, a new module-level record is added which holds the
number of module-level metadata values. This is required because
metadata value ids are assigned implicitly during parsing, and the
function-level metadata ids start after the module-level metadata ids.

Additionally, only map in needed DISubroutine metadata (imported functions
and other DISubroutine transitively needed by those). This is also
supported for LTO and llvm-link --only-needed (with associated tests).

[tejohnson]

As discussed with Mehdi on IRC, I am going to split this up a bit. The
first part is the new MODULE_CODE_METADATA_VALUES record, which just
went out in D14825. I will split out the metadata post-pass linking
mechanics and send as a follow-up next, and finally the part that
suppresses linking of unneeded SPs.

As mentioned in the description of D14825, I made a change to this
support when splitting it out to get more consistent assertion
checking of the record value with and without lazy metadata loading,
so that all regression tests that generate new bitcode essentially act
as tests.

[tejohnson]

This patch has now been split into 3 parts:

http://reviews.llvm.org/D14825
http://reviews.llvm.org/D14838
http://reviews.llvm.org/D14843

[tejohnson]

Obsolete - this was split into 3 separate patches that have since gone in.

include/llvm/Bitcode/LLVMBitCodes.h

enum ModuleCodes {
 
     MODULE_CODE_GCNAME      = 11,  // GCNAME: [strchr x N]
     MODULE_CODE_COMDAT      = 12,  // COMDAT: [selection_kind, name]
 
     MODULE_CODE_VSTOFFSET   = 13,  // VSTOFFSET: [offset]
 
     // ALIAS: [alias value type, addrspace, aliasee val#, linkage, visibility]
     MODULE_CODE_ALIAS       = 14,
+
+    // METADATA_VALUES: [numvals]
+    MODULE_CODE_METADATA_VALUES = 15,
   };
 
   /// PARAMATTR blocks have code for defining a parameter attribute set.
   enum AttributeCodes {
     // FIXME: Remove `PARAMATTR_CODE_ENTRY_OLD' in 4.0
     PARAMATTR_CODE_ENTRY_OLD  = 1, // ENTRY: [paramidx0, attr0,
                                    //         paramidx1, attr1...]
     PARAMATTR_CODE_ENTRY      = 2, // ENTRY: [paramidx0, attrgrp0,

include/llvm/IR/DebugInfoMetadata.h

static DILocation *getImpl(LLVMContext &Context, unsigned Line,
                              unsigned Column, DILocalScope *Scope,
                              DILocation *InlinedAt, StorageType Storage,
                              bool ShouldCreate = true) {
     return getImpl(Context, Line, Column, static_cast<Metadata *>(Scope),
                    static_cast<Metadata *>(InlinedAt), Storage, ShouldCreate);
   }
 
   TempDILocation cloneImpl() const {
-    return getTemporary(getContext(), getLine(), getColumn(), getScope(),
-                        getInlinedAt());
+    // Get the raw scope/inlinedAt since it is possible to invoke this on
+    // a DILocation containing temporary metadata. Specifically, this happens
+    // when we are linking metadata as a postpass after function importing.
+    return getTemporary(getContext(), getLine(), getColumn(), getRawScope(),
+                        getRawInlinedAt());
   }
 
   // Disallow replacing operands.
   void replaceOperandWith(unsigned I, Metadata *New) = delete;
 
 public:
   DEFINE_MDNODE_GET(DILocation,
                     (unsigned Line, unsigned Column, Metadata *Scope,

include/llvm/IR/GVMaterializer.h

 // or interprocedural optimizers that do not need the entire program in memory
 // at the same time.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_GVMATERIALIZER_H
 #define LLVM_IR_GVMATERIALIZER_H
 
+#include "llvm/ADT/DenseMap.h"
 #include <system_error>
 #include <vector>
 
 namespace llvm {
 class Function;
 class GlobalValue;
 class Module;
 class StructType;
+class TrackingMDRef;
 
 class GVMaterializer {
 protected:
   GVMaterializer() {}
 
 public:
   virtual ~GVMaterializer();
 
public:
 
   /// Make sure the entire Module has been completely read.
   ///
   virtual std::error_code materializeModule(Module *M) = 0;
 
   virtual std::error_code materializeMetadata() = 0;
   virtual void setStripDebugInfo() = 0;
 
+  /// Client should define this interface if the mapping between metadata
+  /// values and value ids needs to be preserved, e.g. across materializer
+  /// instantiations. If OnlyTempMD is true, only those that have remained
+  /// temporary metadata are recorded in the map.
+  virtual void
+  saveMDValueList(DenseMap<TrackingMDRef, unsigned> &MDValueToValIDMap,
+                  bool OnlyTempMD) {}
+
   virtual std::vector<StructType *> getIdentifiedStructTypes() const = 0;
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/IR/Metadata.h

void replaceAllUsesWith(Metadata *MD) {
     assert(isTemporary() && "Expected temporary node");
     assert(!isResolved() && "Expected RAUW support");
     Context.getReplaceableUses()->replaceAllUsesWith(MD);
   }
 
   /// \brief Resolve cycles.
   ///
   /// Once all forward declarations have been resolved, force cycles to be
-  /// resolved.
+  /// resolved. If \a MDMaterialized is true, then any temporary metadata
+  /// is ignored, otherwise it asserts when encountering temporary metadata.
   ///
   /// \pre No operands (or operands' operands, etc.) have \a isTemporary().
-  void resolveCycles();
+  void resolveCycles(bool MDMaterialized = true);
 
   /// \brief Replace a temporary node with a permanent one.
   ///
   /// Try to create a uniqued version of \c N -- in place, if possible -- and
   /// return it.  If \c N cannot be uniqued, return a distinct node instead.
   template <class T>
   static typename std::enable_if<std::is_base_of<MDNode, T>::value, T *>::type
   replaceWithPermanent(std::unique_ptr<T, TempMDNodeDeleter> N) {

include/llvm/IR/TrackingMDRef.h

 //===- llvm/IR/TrackingMDRef.h - Tracking Metadata references ---*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // References to metadata that track RAUW.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_TRACKINGMDREF_H
 #define LLVM_IR_TRACKINGMDREF_H
 
+#include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/IR/MetadataTracking.h"
 #include "llvm/Support/Casting.h"
 
 namespace llvm {
 
 class Metadata;
 class MDNode;
 class ValueAsMetadata;
public:
   bool hasTrivialDestructor() const {
     return !MD || !MetadataTracking::isReplaceable(*MD);
   }
 
   bool operator==(const TrackingMDRef &X) const { return MD == X.MD; }
   bool operator!=(const TrackingMDRef &X) const { return MD != X.MD; }
 
 private:
+  /// Enabler for DenseMapInfo of TrackingMDRefs, ensure the MD is non-null
+  /// and not a special DenseMapInfo key.
+  bool isValid() {
+    return MD && MD != DenseMapInfo<Metadata *>::getEmptyKey() &&
+           MD != DenseMapInfo<Metadata *>::getTombstoneKey();
+  }
+
   void track() {
-    if (MD)
+    if (isValid())
       MetadataTracking::track(MD);
   }
   void untrack() {
-    if (MD)
+    if (isValid())
       MetadataTracking::untrack(MD);
   }
   void retrack(TrackingMDRef &X) {
     assert(MD == X.MD && "Expected values to match");
-    if (X.MD) {
+    if (X.isValid()) {
       MetadataTracking::retrack(X.MD, MD);
       X.MD = nullptr;
     }
   }
 };
 
 /// \brief Typed tracking ref.
 ///

 
 template <class T> struct simplify_type<const TypedTrackingMDRef<T>> {
   typedef T *SimpleType;
   static SimpleType getSimplifiedValue(const TypedTrackingMDRef<T> &MD) {
     return MD.get();
   }
 };
 
+/// Provide DenseMapInfo for TrackingMDRefs.
+template <> struct DenseMapInfo<TrackingMDRef> {
+  static inline TrackingMDRef getEmptyKey() {
+    return TrackingMDRef(DenseMapInfo<Metadata *>::getEmptyKey());
+  }
+  static inline TrackingMDRef getTombstoneKey() {
+    return TrackingMDRef(DenseMapInfo<Metadata *>::getTombstoneKey());
+  }
+  static unsigned getHashValue(const TrackingMDRef Val) {
+    return DenseMapInfo<Metadata *>::getHashValue(Val.get());
+  }
+  static bool isEqual(const TrackingMDRef LHS, const TrackingMDRef RHS) {
+    return LHS == RHS;
+  }
+};
+
 } // end namespace llvm
 
 #endif

include/llvm/IRReader/IRReader.h

 
 class Module;
 class SMDiagnostic;
 class LLVMContext;
 
 /// If the given file holds a bitcode image, return a Module
 /// for it which does lazy deserialization of function bodies.  Otherwise,
 /// attempt to parse it as LLVM Assembly and return a fully populated
-/// Module.
-std::unique_ptr<Module> getLazyIRFileModule(StringRef Filename,
-                                            SMDiagnostic &Err,
-                                            LLVMContext &Context);
+/// Module. The ShouldLazyLoadMetadata flag is passed down to the bitcode
+/// reader to optionally enable lazy metadata loading.
+std::unique_ptr<Module>
+getLazyIRFileModule(StringRef Filename, SMDiagnostic &Err, LLVMContext &Context,
+                    bool ShouldLazyLoadMetadata = false);
 
 /// If the given MemoryBuffer holds a bitcode image, return a Module
 /// for it.  Otherwise, attempt to parse it as LLVM Assembly and return
 /// a Module for it.
 std::unique_ptr<Module> parseIR(MemoryBufferRef Buffer, SMDiagnostic &Err,
                                 LLVMContext &Context);
 
 /// If the given file holds a bitcode image, return a Module for it.
 /// Otherwise, attempt to parse it as LLVM Assembly and return a Module
 /// for it.
 std::unique_ptr<Module> parseIRFile(StringRef Filename, SMDiagnostic &Err,
                                     LLVMContext &Context);
 }
 
 #endif

include/llvm/Linker/Linker.h

struct IdentifiedStructTypeSet {
     StructType *findNonOpaque(ArrayRef<Type *> ETypes, bool IsPacked);
     bool hasType(StructType *Ty);
   };
 
   enum Flags {
     None = 0,
     OverrideFromSrc = (1 << 0),
     LinkOnlyNeeded = (1 << 1),
-    InternalizeLinkedSymbols = (1 << 2)
+    InternalizeLinkedSymbols = (1 << 2),
+    /// Flag indicating whether this is simply a metadata linking postpass
+    /// when the functions and other global values were parsed and linked
+    /// by an earlier module link (e.g. during function importing).
+    MetadataLinkingPostpass = (1 << 3)
   };
 
   Linker(Module *M, DiagnosticHandlerFunction DiagnosticHandler);
   Linker(Module *M);
 
   Module *getModule() const { return Composite; }
   void deleteModule();
 
   /// \brief Link \p Src into the composite. The source is destroyed.
   /// Passing OverrideSymbols as true will have symbols from Src
   /// shadow those in the Dest.
   /// For ThinLTO function importing/exporting the \p FunctionInfoIndex
   /// is passed. If a \p FuncToImport is provided, only that single
-  /// function is imported from the source module.
+  /// function is imported from the source module. The ValIDToTempMDMap
+  /// is populated by the linker when function importing is performed, and
+  /// is passed as input along with the MetadataLinkingPostpass flag.
   /// Returns true on error.
   bool linkInModule(Module *Src, unsigned Flags = Flags::None,
                     FunctionInfoIndex *Index = nullptr,
-                    Function *FuncToImport = nullptr);
+                    Function *FuncToImport = nullptr,
+                    DenseMap<unsigned, MDNode *> *ValIDToTempMDMap = nullptr);
 
   /// \brief Set the composite to the passed-in module.
   void setModule(Module *Dst);
 
   static bool LinkModules(Module *Dest, Module *Src,
                           DiagnosticHandlerFunction DiagnosticHandler,
                           unsigned Flags = Flags::None);
 

include/llvm/Transforms/Utils/ValueMapper.h

protected:
     ValueMaterializer(const ValueMaterializer&) = default;
     ValueMaterializer &operator=(const ValueMaterializer&) = default;
 
   public:
     /// materializeValueFor - The client should implement this method if they
     /// want to generate a mapped Value on demand. For example, if linking
     /// lazily.
     virtual Value *materializeValueFor(Value *V) = 0;
+
+    /// If the client needs to handle temporary metadata it must implement
+    /// these methods.
+    virtual Metadata *mapTemporaryMetadata(Metadata *MD) { return nullptr; }
+    virtual void replaceTemporaryMetadata(const Metadata *OrigMD,
+                                          Metadata *NewMD) {}
+
+    /// The client should implement this method if some metadata need
+    /// not be mapped, for example DISubprogram metadata for functions not
+    /// linked into the destination module.
+    virtual bool isMetadataNeeded(Metadata *MD) { return true; }
   };
 
   /// RemapFlags - These are flags that the value mapping APIs allow.
   enum RemapFlags {
     RF_None = 0,
 
     /// RF_NoModuleLevelChanges - If this flag is set, the remapper knows that
     /// only local values within a function (such as an instruction or argument)
     /// are mapped, not global values like functions and global metadata.
     RF_NoModuleLevelChanges = 1,
 
     /// RF_IgnoreMissingEntries - If this flag is set, the remapper ignores
     /// entries that are not in the value map.  If it is unset, it aborts if an
     /// operand is asked to be remapped which doesn't exist in the mapping.
     RF_IgnoreMissingEntries = 2,
 
     /// Instruct the remapper to move distinct metadata instead of duplicating
     /// it when there are module-level changes.
     RF_MoveDistinctMDs = 4,
 
     /// Any global values not in value map are mapped to null instead of
     /// mapping to self. Illegal if RF_IgnoreMissingEntries is also set.
     RF_NullMapMissingGlobalValues = 8,
+
+    /// Set when there is still temporary metadata that must be handled,
+    /// such as when we are doing function importing and will materialize
+    /// and link metadata as a postpass.
+    RF_HaveUnmaterializedMetadata = 16,
   };
 
   static inline RemapFlags operator|(RemapFlags LHS, RemapFlags RHS) {
     return RemapFlags(unsigned(LHS)|unsigned(RHS));
   }
 
   Value *MapValue(const Value *V, ValueToValueMapTy &VM,
                   RemapFlags Flags = RF_None,

lib/Bitcode/Reader/BitcodeReader.cpp

public:
   /// Once all constants are read, this method bulk resolves any forward
   /// references.
   void resolveConstantForwardRefs();
 };
 
 class BitcodeReaderMDValueList {
   unsigned NumFwdRefs;
   bool AnyFwdRefs;
+  bool SavedFwdRefs;
   unsigned MinFwdRef;
   unsigned MaxFwdRef;
   std::vector<TrackingMDRef> MDValuePtrs;
 
   LLVMContext &Context;
 public:
   BitcodeReaderMDValueList(LLVMContext &C)
-      : NumFwdRefs(0), AnyFwdRefs(false), Context(C) {}
+      : NumFwdRefs(0), AnyFwdRefs(false), SavedFwdRefs(false), Context(C) {}
+  ~BitcodeReaderMDValueList() {
+    // Assert that we either replaced all forward references, or saved
+    // them for later replacement.
+    assert(!NumFwdRefs || SavedFwdRefs);
+  }
 
   // vector compatibility methods
   unsigned size() const       { return MDValuePtrs.size(); }
   void resize(unsigned N)     { MDValuePtrs.resize(N); }
   void push_back(Metadata *MD) { MDValuePtrs.emplace_back(MD); }
   void clear()                { MDValuePtrs.clear();  }
   Metadata *back() const      { return MDValuePtrs.back(); }
   void pop_back()             { MDValuePtrs.pop_back(); }
   bool empty() const          { return MDValuePtrs.empty(); }
 
+  void savedFwdRefs() { SavedFwdRefs = true; }
+
   Metadata *operator[](unsigned i) const {
     assert(i < MDValuePtrs.size());
     return MDValuePtrs[i];
   }
 
   void shrinkTo(unsigned N) {
     assert(N <= size() && "Invalid shrinkTo request!");
     MDValuePtrs.resize(N);
class BitcodeReader : public GVMaterializer {
   // Next offset to start scanning for lazy parsing of function bodies.
   uint64_t NextUnreadBit = 0;
   // Last function offset found in the VST.
   uint64_t LastFunctionBlockBit = 0;
   bool SeenValueSymbolTable = false;
   uint64_t VSTOffset = 0;
   // Contains an arbitrary and optional string identifying the bitcode producer
   std::string ProducerIdentification;
+  unsigned NumModuleMDs = 0;
+  // Support older bitcode without this record.
+  bool SeenModuleValuesRecord = false;
 
   std::vector<Type*> TypeList;
   BitcodeReaderValueList ValueList;
   BitcodeReaderMDValueList MDValueList;
   std::vector<Comdat *> ComdatList;
   SmallVector<Instruction *, 64> InstructionList;
 
   std::vector<std::pair<GlobalVariable*, unsigned> > GlobalInits;
public:
 
   static uint64_t decodeSignRotatedValue(uint64_t V);
 
   /// Materialize any deferred Metadata block.
   std::error_code materializeMetadata() override;
 
   void setStripDebugInfo() override;
 
+  /// Save the mapping between the metadata values and the corresponding
+  /// value id that were recorded in the MDValueList during parsing. If
+  /// OnlyTempMD is true, then only record those entries that are still
+  /// temporary metadata. This interface is used when metadata linking is
+  /// performed as a postpass, such as during function importing.
+  void saveMDValueList(DenseMap<TrackingMDRef, unsigned> &MDValueToValIDMap,
+                       bool OnlyTempMD) override;
+
 private:
   /// Parse the "IDENTIFICATION_BLOCK_ID" block, populate the
   // ProducerIdentification data member, and do some basic enforcement on the
   // "epoch" encoded in the bitcode.
   std::error_code parseBitcodeVersion();
 
   std::vector<StructType *> IdentifiedStructTypes;
   StructType *createIdentifiedStructType(LLVMContext &Context, StringRef Name);
private:
   std::error_code parseConstants();
   std::error_code rememberAndSkipFunctionBodies();
   std::error_code rememberAndSkipFunctionBody();
   /// Save the positions of the Metadata blocks and skip parsing the blocks.
   std::error_code rememberAndSkipMetadata();
   std::error_code parseFunctionBody(Function *F);
   std::error_code globalCleanup();
   std::error_code resolveGlobalAndAliasInits();
-  std::error_code parseMetadata();
+  std::error_code parseMetadata(bool LazyLoadOfModuleMetadata = false);
   std::error_code parseMetadataKinds();
   std::error_code parseMetadataKindRecord(SmallVectorImpl<uint64_t> &Record);
   std::error_code parseMetadataAttachment(Function &F);
   ErrorOr<std::string> parseModuleTriple();
   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);
BitcodeReader::parseMetadataKindRecord(SmallVectorImpl<uint64_t> &Record) {
   unsigned NewKind = TheModule->getMDKindID(Name.str());
   if (!MDKindMap.insert(std::make_pair(Kind, NewKind)).second)
     return error("Conflicting METADATA_KIND records");
   return std::error_code();
 }
 
 static int64_t unrotateSign(uint64_t U) { return U & 1 ? ~(U >> 1) : U >> 1; }
 
-std::error_code BitcodeReader::parseMetadata() {
+/// Parse a METADATA_BLOCK. If LazyLoadOfModuleMetadata is true then we were
+/// performing lazy metadata linking and this is the module level metadata.
+std::error_code BitcodeReader::parseMetadata(bool LazyLoadOfModuleMetadata) {
   IsMetadataMaterialized = true;
   unsigned NextMDValueNo = MDValueList.size();
+  if (LazyLoadOfModuleMetadata && SeenModuleValuesRecord) {
+    // Now that we are parsing the module level metadata, we want to restart
+    // the numbering of the MD values, and replace temp MD created earlier
+    // with their real values. If we saw a METADATA_VALUE record then we
+    // would have set the MDValueList size to the number specified in that
+    // record, to support parsing function-level metadata first, and we need
+    // to reset back to 0 to fill the MDValueList in with the parsed module
+    // The function-level metadata parsing should have reset the MDValueList
+    // size back to the value reported by the METADATA_VALUE record, saved in
+    // NumModuleMDs.
+    assert(NumModuleMDs == MDValueList.size() &&
+           "Expected MDValueList to only contain module level values");
+    NextMDValueNo = 0;
+  }
 
   if (Stream.EnterSubBlock(bitc::METADATA_BLOCK_ID))
     return error("Invalid record");
 
   SmallVector<uint64_t, 64> Record;
 
   auto getMD =
       [&](unsigned ID) -> Metadata *{ return MDValueList.getValueFwdRef(ID); };
if (Stream.SkipBlock())
     return error("Invalid record");
   return std::error_code();
 }
 
 std::error_code BitcodeReader::materializeMetadata() {
   for (uint64_t BitPos : DeferredMetadataInfo) {
     // Move the bit stream to the saved position.
     Stream.JumpToBit(BitPos);
-    if (std::error_code EC = parseMetadata())
+    if (std::error_code EC = parseMetadata(true))
       return EC;
   }
   DeferredMetadataInfo.clear();
   return std::error_code();
 }
 
 void BitcodeReader::setStripDebugInfo() { StripDebugInfo = true; }
 
+void BitcodeReader::saveMDValueList(
+    DenseMap<TrackingMDRef, unsigned> &MDValueToValIDMap, bool OnlyTempMD) {
+  for (unsigned i = 0; i < MDValueList.size(); ++i) {
+    Metadata *MD = MDValueList[i];
+    auto *N = dyn_cast_or_null<MDNode>(MD);
+    // Save all values if !OnlyTempMD, otherwise just the temporary metadata.
+    if (!OnlyTempMD || (N && N->isTemporary())) {
+      TrackingMDRef MDRef(MD);
+      // Will call this after materializing each function, in order to
+      // handle remapping of the function's instructions/metadata.
+      // See if we already have an entry in that case.
+      if (OnlyTempMD && MDValueToValIDMap.count(MDRef)) {
+        assert(MDValueToValIDMap[MDRef] == i &&
+               "Inconsistent metadata value id");
+        return;
+      }
+      MDValueToValIDMap[MDRef] = i;
+      // Flag that we saved the forward refs (temporary metadata) for error
+      // checking during MDValueList destruction.
+      if (OnlyTempMD)
+        MDValueList.savedFwdRefs();
+    }
+  }
+}
+
 /// When we see the block for a function body, remember where it is and then
 /// skip it.  This lets us lazily deserialize the functions.
 std::error_code BitcodeReader::rememberAndSkipFunctionBody() {
   // Get the function we are talking about.
   if (FunctionsWithBodies.empty())
     return error("Insufficient function protos");
 
   Function *Fn = FunctionsWithBodies.back();
case BitstreamEntry::SubBlock:
         }
         break;
       case bitc::CONSTANTS_BLOCK_ID:
         if (std::error_code EC = parseConstants())
           return EC;
         if (std::error_code EC = resolveGlobalAndAliasInits())
           return EC;
         break;
-      case bitc::METADATA_BLOCK_ID:
+      case bitc::METADATA_BLOCK_ID: {
         if (ShouldLazyLoadMetadata && !IsMetadataMaterialized) {
           if (std::error_code EC = rememberAndSkipMetadata())
             return EC;
+          // Older bitcode will not have a MODULE_CODE_METADATA_VALUES record.
+          // In that case we will need to materialize all metadata before
+          // parsing functions (handled in BitcodeReader::materialize()).
+          if (SeenModuleValuesRecord) {
+            // Set the MDValueList size so that the value ids for function-level
+            // metadata map to the appropriate id. This is needed because
+            // the ids of metadata are assigned implicitly based on their
+            // ordering in the bitcode (and order of insertion into the
+            // MDValueList).
+            assert(MDValueList.size() == 0);
+            MDValueList.resize(NumModuleMDs);
+          }
           break;
         }
         assert(DeferredMetadataInfo.empty() && "Unexpected deferred metadata");
         if (std::error_code EC = parseMetadata())
           return EC;
+        assert(
+            (!SeenModuleValuesRecord || NumModuleMDs == MDValueList.size()) &&
+            "Inconsistent bitcode: METADATA_VALUES mismatch");
         break;
+      }
       case bitc::METADATA_KIND_BLOCK_ID:
         if (std::error_code EC = parseMetadataKinds())
           return EC;
         break;
       case bitc::FUNCTION_BLOCK_ID:
         // If this is the first function body we've seen, reverse the
         // FunctionsWithBodies list.
         if (!SeenFirstFunctionBody) {
case bitc::MODULE_CODE_PURGEVALS:
       ValueList.shrinkTo(Record[0]);
       break;
     /// MODULE_CODE_VSTOFFSET: [offset]
     case bitc::MODULE_CODE_VSTOFFSET:
       if (Record.size() < 1)
         return error("Invalid record");
       VSTOffset = Record[0];
       break;
+    /// MODULE_CODE_METADATA_VALUES: [numvals]
+    case bitc::MODULE_CODE_METADATA_VALUES:
+      if (Record.size() < 1)
+        return error("Invalid record");
+      assert(!IsMetadataMaterialized);
+      // This record contains the number of metadata values in the module-level
+      // METADATA_BLOCK. It is used to support lazy parsing of metadata as
+      // a postpass, where we will parse function-level metadata first.
+      // This is needed because the ids of metadata are assigned implicitly
+      // based on their ordering in the bitcode, with the function-level
+      // metadata ids starting after the module-level metadata ids. Otherwise,
+      // we would have to parse the module-level metadata block to prime the
+      // MDValueList when we are lazy loading metadata during function
+      // importing.
+      NumModuleMDs = Record[0];
+      SeenModuleValuesRecord = true;
+      break;
     }
     Record.clear();
   }
 }
 
 /// Helper to read the header common to all bitcode files.
 static bool hasValidBitcodeHeader(BitstreamCursor &Stream) {
   // Sniff for the signature.

 
 //===----------------------------------------------------------------------===//
 // GVMaterializer implementation
 //===----------------------------------------------------------------------===//
 
 void BitcodeReader::releaseBuffer() { Buffer.release(); }
 
 std::error_code BitcodeReader::materialize(GlobalValue *GV) {
+  // In older bitcode we must materialize the metadata before parsing
+  // any functions, in order to set up the MDValueList properly.
+  if (!SeenModuleValuesRecord) {
     if (std::error_code EC = materializeMetadata())
       return EC;
+  }
 
   Function *F = dyn_cast<Function>(GV);
   // If it's not a function or is already material, ignore the request.
   if (!F || !F->isMaterializable())
     return std::error_code();
 
   DenseMap<Function*, uint64_t>::iterator DFII = DeferredFunctionInfo.find(F);
   assert(DFII != DeferredFunctionInfo.end() && "Deferred function not found!");
std::error_code BitcodeReader::materializeModule(Module *M) {
   WillMaterializeAllForwardRefs = true;
 
   // Iterate over the module, deserializing any functions that are still on
   // disk.
   for (Function &F : *TheModule) {
     if (std::error_code EC = materialize(&F))
       return EC;
   }
+
   // At this point, if there are any function bodies, parse the rest of
   // the bits in the module past the last function block we have recorded
   // through either lazy scanning or the VST.
   if (LastFunctionBlockBit || NextUnreadBit)
     parseModule(LastFunctionBlockBit > NextUnreadBit ? LastFunctionBlockBit
                                                      : NextUnreadBit);
 
   // Check that all block address forward references got resolved (as we

lib/Bitcode/Writer/BitcodeWriter.cpp

for (const GlobalAlias &A : M->aliases()) {
     Vals.push_back(getEncodedDLLStorageClass(A));
     Vals.push_back(getEncodedThreadLocalMode(A));
     Vals.push_back(A.hasUnnamedAddr());
     unsigned AbbrevToUse = 0;
     Stream.EmitRecord(bitc::MODULE_CODE_ALIAS, Vals, AbbrevToUse);
     Vals.clear();
   }
 
+  // Write a record indicating the number of module-level metadata IDs
+  // This is needed because the ids of metadata are assigned implicitly
+  // based on their ordering in the bitcode, with the function-level
+  // metadata ids starting after the module-level metadata ids. For
+  // function importing where we lazy load the metadata as a postpass,
+  // we want to avoid parsing the module-level metadata before parsing
+  // the imported functions.
+  BitCodeAbbrev *Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_METADATA_VALUES));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
+  unsigned MDValsAbbrev = Stream.EmitAbbrev(Abbv);
+  Vals.push_back(VE.numMDs());
+  Stream.EmitRecord(bitc::MODULE_CODE_METADATA_VALUES, Vals, MDValsAbbrev);
+  Vals.clear();
+
   uint64_t VSTOffsetPlaceholder =
       WriteValueSymbolTableForwardDecl(M->getValueSymbolTable(), Stream);
   return VSTOffsetPlaceholder;
 }
 
 static uint64_t GetOptimizationFlags(const Value *V) {
   uint64_t Flags = 0;
 

lib/Bitcode/Writer/ValueEnumerator.h

public:
   unsigned getMetadataID(const Metadata *MD) const {
     auto ID = getMetadataOrNullID(MD);
     assert(ID != 0 && "Metadata not in slotcalculator!");
     return ID - 1;
   }
   unsigned getMetadataOrNullID(const Metadata *MD) const {
     return MDValueMap.lookup(MD);
   }
+  unsigned numMDs() const { return MDs.size(); }
 
   bool hasMDString() const { return HasMDString; }
   bool hasDILocation() const { return HasDILocation; }
   bool hasGenericDINode() const { return HasGenericDINode; }
 
   bool shouldPreserveUseListOrder() const { return ShouldPreserveUseListOrder; }
 
   unsigned getTypeID(Type *T) const {

lib/IR/Metadata.cpp

 }
 
 void MDNode::decrementUnresolvedOperandCount() {
   if (!--NumUnresolved)
     // Last unresolved operand has just been resolved.
     resolve();
 }
 
-void MDNode::resolveCycles() {
+void MDNode::resolveCycles(bool MDMaterialized) {
   if (isResolved())
     return;
 
   // Resolve this node immediately.
   resolve();
 
   // Resolve all operands.
   for (const auto &Op : operands()) {
     auto *N = dyn_cast_or_null<MDNode>(Op);
     if (!N)
       continue;
 
+    if (N->isTemporary() && !MDMaterialized)
+      continue;
     assert(!N->isTemporary() &&
            "Expected all forward declarations to be resolved");
     if (!N->isResolved())
       N->resolveCycles();
   }
 }
 
 static bool hasSelfReference(MDNode *N) {

lib/IRReader/IRReader.cpp

namespace llvm {
   extern bool TimePassesIsEnabled;
 }
 
 static const char *const TimeIRParsingGroupName = "LLVM IR Parsing";
 static const char *const TimeIRParsingName = "Parse IR";
 
 static std::unique_ptr<Module>
 getLazyIRModule(std::unique_ptr<MemoryBuffer> Buffer, SMDiagnostic &Err,
-                LLVMContext &Context) {
+                LLVMContext &Context, bool ShouldLazyLoadMetadata) {
   if (isBitcode((const unsigned char *)Buffer->getBufferStart(),
                 (const unsigned char *)Buffer->getBufferEnd())) {
-    ErrorOr<std::unique_ptr<Module>> ModuleOrErr =
-        getLazyBitcodeModule(std::move(Buffer), Context);
+    ErrorOr<std::unique_ptr<Module>> ModuleOrErr = getLazyBitcodeModule(
+        std::move(Buffer), Context, nullptr, ShouldLazyLoadMetadata);
     if (std::error_code EC = ModuleOrErr.getError()) {
       Err = SMDiagnostic(Buffer->getBufferIdentifier(), SourceMgr::DK_Error,
                          EC.message());
       return nullptr;
     }
     return std::move(ModuleOrErr.get());
   }
 
   return parseAssembly(Buffer->getMemBufferRef(), Err, Context);
 }
 
 std::unique_ptr<Module> llvm::getLazyIRFileModule(StringRef Filename,
                                                   SMDiagnostic &Err,
-                                                  LLVMContext &Context) {
+                                                  LLVMContext &Context,
+                                                  bool ShouldLazyLoadMetadata) {
   ErrorOr<std::unique_ptr<MemoryBuffer>> FileOrErr =
       MemoryBuffer::getFileOrSTDIN(Filename);
   if (std::error_code EC = FileOrErr.getError()) {
     Err = SMDiagnostic(Filename, SourceMgr::DK_Error,
                        "Could not open input file: " + EC.message());
     return nullptr;
   }
 
-  return getLazyIRModule(std::move(FileOrErr.get()), Err, Context);
+  return getLazyIRModule(std::move(FileOrErr.get()), Err, Context,
+                         ShouldLazyLoadMetadata);
 }
 
 std::unique_ptr<Module> llvm::parseIR(MemoryBufferRef Buffer, SMDiagnostic &Err,
                                       LLVMContext &Context) {
   NamedRegionTimer T(TimeIRParsingName, TimeIRParsingGroupName,
                      TimePassesIsEnabled);
   if (isBitcode((const unsigned char *)Buffer.getBufferStart(),
                 (const unsigned char *)Buffer.getBufferEnd())) {

lib/Linker/LinkModules.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/DiagnosticPrinter.h"
+#include "llvm/IR/GVMaterializer.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/TypeFinder.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include <cctype>

 public:
   ValueMaterializerTy(TypeMapTy &TypeMap, Module *DstM,
                       std::vector<GlobalValue *> &LazilyLinkGlobalValues,
                       ModuleLinker *ModLinker)
       : ValueMaterializer(), TypeMap(TypeMap), DstM(DstM),
         LazilyLinkGlobalValues(LazilyLinkGlobalValues), ModLinker(ModLinker) {}
 
   Value *materializeValueFor(Value *V) override;
+
+  /// Invoke ModuleLinker callback to save the mapping between the
+  /// given temporary metadata and its metadata value id. Used to support
+  /// metadata linking as a postpass for function importing.
+  Metadata *mapTemporaryMetadata(Metadata *MD) override;
+
+  /// Invoke ModuleLinker callback to replace any temporary metadata saved
+  /// for the source metadata's id with the new non-temporary metadata.
+  /// Used when metadata linking as a postpass for function importing.
+  void replaceTemporaryMetadata(const Metadata *OrigMD,
+                                Metadata *NewMD) override;
+
+  /// Invoke ModuleLinker callback to indicate whether we need to map the
+  /// given metadata into the destination module. Used to prevent linking of
+  /// metadata only needed by functions not linked into the dest module.
+  bool isMetadataNeeded(Metadata *MD) override;
 };
 
 class LinkDiagnosticInfo : public DiagnosticInfo {
   const Twine &Msg;
 
 public:
   LinkDiagnosticInfo(DiagnosticSeverity Severity, const Twine &Msg);
   void print(DiagnosticPrinter &DP) const override;
class ModuleLinker {
   // Vector of GlobalValues to lazily link in.
   std::vector<GlobalValue *> LazilyLinkGlobalValues;
 
   DiagnosticHandlerFunction DiagnosticHandler;
 
   /// For symbol clashes, prefer those from Src.
   unsigned Flags;
 
+  /// Flags to pass to value mapper invocations.
+  RemapFlags ValueMapperFlags;
+
   /// Function index passed into ModuleLinker for using in function
   /// importing/exporting handling.
   FunctionInfoIndex *ImportIndex;
 
   /// Function to import from source module, all other functions are
   /// imported as declarations instead of definitions.
   Function *ImportFunction;
 
   /// Set to true if the given FunctionInfoIndex contains any functions
   /// from this source module, in which case we must conservatively assume
   /// that any of its functions may be imported into another module
   /// as part of a different backend compilation process.
   bool HasExportedFunctions;
 
   /// Set to true when all global value body linking is complete (including
   /// lazy linking). Used to prevent metadata linking from creating new
   /// references.
   bool DoneLinkingBodies;
 
+  /// Association between metadata values created during bitcode parsing and
+  /// the value id. Used to correlate temporary metadata created during
+  /// function importing with the final metadata parsed during the subsequent
+  /// metadata linking postpass.
+  DenseMap<TrackingMDRef, unsigned> MDValueToValIDMap;
+
+  /// Association between metadata value id and temporary metadata that
+  /// remains unmapped after function importing. Saved during function
+  /// importing and consumed during the metadata linking postpass.
+  DenseMap<unsigned, MDNode *> *ValIDToTempMDMap;
+
+  /// Set of subprogram metadata that does not need to be linked into the
+  /// destination module, because the functions were not imported directly
+  /// or via an inlined body in an imported function.
+  SmallPtrSet<const Metadata *, 16> *UnneededSubprograms;
+
 public:
   ModuleLinker(Module *dstM, Linker::IdentifiedStructTypeSet &Set, Module *srcM,
                DiagnosticHandlerFunction DiagnosticHandler, unsigned Flags,
                FunctionInfoIndex *Index = nullptr,
-               Function *FuncToImport = nullptr)
+               Function *FuncToImport = nullptr,
+               DenseMap<unsigned, MDNode *> *ValIDToTempMDMap = nullptr)
       : DstM(dstM), SrcM(srcM), TypeMap(Set),
         ValMaterializer(TypeMap, DstM, LazilyLinkGlobalValues, this),
-        DiagnosticHandler(DiagnosticHandler), Flags(Flags), ImportIndex(Index),
+        DiagnosticHandler(DiagnosticHandler), Flags(Flags),
+        ValueMapperFlags(RF_MoveDistinctMDs), ImportIndex(Index),
         ImportFunction(FuncToImport), HasExportedFunctions(false),
-        DoneLinkingBodies(false) {
+        DoneLinkingBodies(false), ValIDToTempMDMap(ValIDToTempMDMap),
+        UnneededSubprograms(nullptr) {
     assert((ImportIndex || !ImportFunction) &&
            "Expect a FunctionInfoIndex when importing");
     // If we have a FunctionInfoIndex but no function to import,
     // then this is the primary module being compiled in a ThinLTO
     // backend compilation, and we need to see if it has functions that
     // may be exported to another backend compilation.
     if (ImportIndex && !ImportFunction)
       HasExportedFunctions = ImportIndex->hasExportedFunctions(SrcM);
+
+    assert(!(isMetadataLinkingPostpass() && (ImportIndex || ImportFunction)) &&
+           "Illegal to pass a function index or function to import into "
+           "metadata linking postpass");
+    assert((ValIDToTempMDMap ||
+            (!ImportFunction && !isMetadataLinkingPostpass())) &&
+           "Function importing and metadata postpass linking must both provide "
+           "a ValIDToTempMDMap");
+
+    // If appropriate, tell the value mapper that it can expect to see
+    // temporary metadata.
+    if (!shouldLinkMetadata())
+      ValueMapperFlags = ValueMapperFlags | RF_HaveUnmaterializedMetadata;
   }
 
   bool run();
 
   bool shouldOverrideFromSrc() { return Flags & Linker::OverrideFromSrc; }
   bool shouldLinkOnlyNeeded() { return Flags & Linker::LinkOnlyNeeded; }
   bool shouldInternalizeLinkedSymbols() {
     return Flags & Linker::InternalizeLinkedSymbols;
   }
+  bool isMetadataLinkingPostpass() {
+    return Flags & Linker::MetadataLinkingPostpass;
+  }
+
+  bool shouldLinkMetadata() {
+    // This will be non-null when we are importing or otherwise want to link
+    // metadata lazily (LTO), and when linking the metadata.
+    return ValIDToTempMDMap == nullptr || isMetadataLinkingPostpass();
+  }
 
   /// Handles cloning of a global values from the source module into
   /// the destination module, including setting the attributes and visibility.
   GlobalValue *copyGlobalValueProto(TypeMapTy &TypeMap, const GlobalValue *SGV,
                                     const GlobalValue *DGV = nullptr);
 
   /// Check if we should promote the given local value to global scope.
   bool doPromoteLocalToGlobal(const GlobalValue *SGV);
 
   /// Check if all global value body linking is complete.
   bool doneLinkingBodies() { return DoneLinkingBodies; }
 
+  /// Save the mapping between the given temporary metadata and its metadata
+  /// value id. Used to support metadata linking as a postpass for function
+  /// importing.
+  Metadata *mapTemporaryMetadata(Metadata *MD);
+
+  /// Replace any temporary metadata saved for the source metadata's id with
+  /// the new non-temporary metadata. Used when metadata linking as a postpass
+  /// for function importing.
+  void replaceTemporaryMetadata(const Metadata *OrigMD, Metadata *NewMD);
+
+  /// Indicates whether we need to map the given metadata into the destination
+  /// module. Used to prevent linking of metadata only needed by functions not
+  /// linked into the dest module.
+  bool isMetadataNeeded(Metadata *MD);
+
 private:
   bool shouldLinkFromSource(bool &LinkFromSrc, const GlobalValue &Dest,
                             const GlobalValue &Src);
 
   /// Helper method for setting a message and returning an error code.
   bool emitError(const Twine &Message) {
     DiagnosticHandler(LinkDiagnosticInfo(DS_Error, Message));
     return true;
private:
   /// into the destination module.
   GlobalVariable *copyGlobalVariableProto(TypeMapTy &TypeMap,
                                           const GlobalVariable *SGVar);
   Function *copyFunctionProto(TypeMapTy &TypeMap, const Function *SF);
   GlobalValue *copyGlobalAliasProto(TypeMapTy &TypeMap, const GlobalAlias *SGA);
 
   /// Helper methods to check if we are importing from or potentially
   /// exporting from the current source module.
-  bool isPerformingImport() { return ImportFunction != nullptr; }
-  bool isModuleExporting() { return HasExportedFunctions; }
+  bool isPerformingImport() const { return ImportFunction != nullptr; }
+  bool isModuleExporting() const { return HasExportedFunctions; }
 
   /// If we are importing from the source module, checks if we should
   /// import SGV as a definition, otherwise import as a declaration.
   bool doImportAsDefinition(const GlobalValue *SGV);
 
   /// Get the name for SGV that should be used in the linked destination
   /// module. Specifically, this handles the case where we need to rename
   /// a local that is being promoted to global scope.
private:
 
   /// Updates the visibility for the new global cloned from the source
   /// and, if applicable, linked with an existing destination global.
   /// Handles visibility change required for promoted locals.
   void setVisibility(GlobalValue *NewGV, const GlobalValue *SGV,
                      const GlobalValue *DGV = nullptr);
 
   void linkNamedMDNodes();
+
+  /// Populate the UnneededSubprograms set with the DISubprogram metadata
+  /// from the source module that we don't need to link into the dest module,
+  /// because the functions were not imported directly or via an inlined body
+  /// in an imported function.
+  void findNeededSubprograms(ValueToValueMapTy &ValueMap);
+
+  /// The value mapper leaves nulls in the list of subprograms for any
+  /// in the UnneededSubprograms map. Strip those out after metadata linking.
+  void stripNullSubprograms();
 };
 }
 
 /// The LLVM SymbolTable class autorenames globals that conflict in the symbol
 /// table. This is good for all clients except for us. Go through the trouble
 /// to force this back.
 static void forceRenaming(GlobalValue *GV, StringRef Name) {
   // If the global doesn't force its name or if it already has the right name,
if (auto *DGO = dyn_cast<GlobalObject>(DGV)) {
       DGO->setComdat(DC);
     }
   }
 
   LazilyLinkGlobalValues.push_back(SGV);
   return DGV;
 }
 
+Metadata *ValueMaterializerTy::mapTemporaryMetadata(Metadata *MD) {
+  return ModLinker->mapTemporaryMetadata(MD);
+}
+
+void ValueMaterializerTy::replaceTemporaryMetadata(const Metadata *OrigMD,
+                                                   Metadata *NewMD) {
+  ModLinker->replaceTemporaryMetadata(OrigMD, NewMD);
+}
+
+bool ValueMaterializerTy::isMetadataNeeded(Metadata *MD) {
+  return ModLinker->isMetadataNeeded(MD);
+}
+
+Metadata *ModuleLinker::mapTemporaryMetadata(Metadata *MD) {
+  MDNode *Node = cast<MDNode>(MD);
+  assert(Node->isTemporary());
+  TrackingMDRef MDRef(MD);
+  // If this temporary metadata has a value id recorded during function
+  // parsing, record that in the ValIDToTempMDMap if one was provided.
+  if (ValIDToTempMDMap && MDValueToValIDMap.count(MDRef)) {
+    unsigned Idx = MDValueToValIDMap[MDRef];
+    // Check if we created a temp MD when importing a different function from
+    // this module. If so, reuse it the same temporary metadata, otherwise
+    // add this temporary metadata to the map.
+    if (!ValIDToTempMDMap->count(Idx))
+      (*ValIDToTempMDMap)[Idx] = Node;
+    return (*ValIDToTempMDMap)[Idx];
+  }
+  return nullptr;
+}
+
+void ModuleLinker::replaceTemporaryMetadata(const Metadata *OrigMD,
+                                            Metadata *NewMD) {
+#ifndef NDEBUG
+  auto *N = dyn_cast_or_null<MDNode>(NewMD);
+  assert(!N || !N->isTemporary());
+#endif
+  TrackingMDRef MDRef(const_cast<Metadata *>(OrigMD));
+  // If a mapping between metadata value ids and temporary metadata
+  // created during function importing was provided, and the source
+  // metadata has a value id recorded during metadata parsing, replace
+  // the temporary metadata with the final mapped metadata now.
+  if (ValIDToTempMDMap && MDValueToValIDMap.count(MDRef)) {
+    unsigned Idx = MDValueToValIDMap[MDRef];
+    // Nothing to do if we didn't need to create a temporary metadata during
+    // function importing.
+    if (!ValIDToTempMDMap->count(Idx))
+      return;
+    MDNode *TempMD = (*ValIDToTempMDMap)[Idx];
+    TempMD->replaceAllUsesWith(NewMD);
+    MDNode::deleteTemporary(TempMD);
+    ValIDToTempMDMap->erase(Idx);
+  }
+}
+
+bool ModuleLinker::isMetadataNeeded(Metadata *MD) {
+  // Currently only DISubprogram metadata is marked as being unneeded.
+  if (!UnneededSubprograms)
+    return true;
+  MDNode *Node = dyn_cast<MDNode>(MD);
+  if (!Node)
+    return true;
+  DISubprogram *SP = getDISubprogram(Node);
+  if (!SP)
+    return true;
+  return !UnneededSubprograms->count(SP);
+}
+
 bool ModuleLinker::getComdatLeader(Module *M, StringRef ComdatName,
                                    const GlobalVariable *&GVar) {
   const GlobalValue *GVal = M->getNamedValue(ComdatName);
   if (const auto *GA = dyn_cast_or_null<GlobalAlias>(GVal)) {
     GVal = GA->getBaseObject();
     if (!GVal)
       // We cannot resolve the size of the aliasee yet.
       return emitError("Linking COMDATs named '" + ComdatName +
bool ModuleLinker::getComdatResult(const Comdat *SrcC,
   Comdat::SelectionKind DSK = DstC->getSelectionKind();
   return computeResultingSelectionKind(ComdatName, SSK, DSK, Result,
                                        LinkFromSrc);
 }
 
 bool ModuleLinker::shouldLinkFromSource(bool &LinkFromSrc,
                                         const GlobalValue &Dest,
                                         const GlobalValue &Src) {
+  // Already imported all the values. Just map to the Dest value
+  // in case it is referenced in the metadata.
+  if (isMetadataLinkingPostpass()) {
+    LinkFromSrc = false;
+    return false;
+  }
+
   // Should we unconditionally use the Src?
   if (shouldOverrideFromSrc()) {
     LinkFromSrc = true;
     return false;
   }
 
   // We always have to add Src if it has appending linkage.
   if (Src.hasAppendingLinkage()) {
void ModuleLinker::linkAppendingVarInit(const AppendingVarInfo &AVI) {
 
   for (auto *V : SrcElements) {
     if (IsNewStructor) {
       Constant *Key = V->getAggregateElement(2);
       if (DoNotLinkFromSource.count(Key))
         continue;
     }
     DstElements.push_back(
-        MapValue(V, ValueMap, RF_MoveDistinctMDs, &TypeMap, &ValMaterializer));
+        MapValue(V, ValueMap, ValueMapperFlags, &TypeMap, &ValMaterializer));
   }
   if (IsNewStructor) {
     NewType = ArrayType::get(NewType->getElementType(), DstElements.size());
     AVI.NewGV->mutateType(PointerType::get(NewType, 0));
   }
 
   AVI.NewGV->setInitializer(ConstantArray::get(NewType, DstElements));
 }
 
 /// Update the initializers in the Dest module now that all globals that may be
 /// referenced are in Dest.
 void ModuleLinker::linkGlobalInit(GlobalVariable &Dst, GlobalVariable &Src) {
   // Figure out what the initializer looks like in the dest module.
-  Dst.setInitializer(MapValue(Src.getInitializer(), ValueMap,
-                              RF_MoveDistinctMDs, &TypeMap, &ValMaterializer));
+  Dst.setInitializer(MapValue(Src.getInitializer(), ValueMap, ValueMapperFlags,
+                              &TypeMap, &ValMaterializer));
 }
 
 /// Copy the source function over into the dest function and fix up references
 /// to values. At this point we know that Dest is an external function, and
 /// that Src is not.
 bool ModuleLinker::linkFunctionBody(Function &Dst, Function &Src) {
   assert(Dst.isDeclaration() && !Src.isDeclaration());
 
   // Materialize if needed.
   if (std::error_code EC = Src.materialize())
     return emitError(EC.message());
 
+  if (!shouldLinkMetadata())
+    // This is only supported for lazy links. Do after materialization of
+    // a function and before remapping metadata on instructions below
+    // in RemapInstruction, as the saved mapping is used to handle
+    // the temporary metadata hanging off instructions.
+    SrcM->getMaterializer()->saveMDValueList(MDValueToValIDMap, true);
+
   // Link in the prefix data.
   if (Src.hasPrefixData())
-    Dst.setPrefixData(MapValue(Src.getPrefixData(), ValueMap,
-                               RF_MoveDistinctMDs, &TypeMap, &ValMaterializer));
+    Dst.setPrefixData(MapValue(Src.getPrefixData(), ValueMap, ValueMapperFlags,
+                               &TypeMap, &ValMaterializer));
 
   // Link in the prologue data.
   if (Src.hasPrologueData())
     Dst.setPrologueData(MapValue(Src.getPrologueData(), ValueMap,
-                                 RF_MoveDistinctMDs, &TypeMap,
-                                 &ValMaterializer));
+                                 ValueMapperFlags, &TypeMap, &ValMaterializer));
 
   // Link in the personality function.
   if (Src.hasPersonalityFn())
     Dst.setPersonalityFn(MapValue(Src.getPersonalityFn(), ValueMap,
-                                  RF_MoveDistinctMDs, &TypeMap,
+                                  ValueMapperFlags, &TypeMap,
                                   &ValMaterializer));
 
   // Go through and convert function arguments over, remembering the mapping.
   Function::arg_iterator DI = Dst.arg_begin();
   for (Argument &Arg : Src.args()) {
     DI->setName(Arg.getName());  // Copy the name over.
 
     // Add a mapping to our mapping.
     ValueMap[&Arg] = &*DI;
     ++DI;
   }
 
   // Copy over the metadata attachments.
   SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
   Src.getAllMetadata(MDs);
   for (const auto &I : MDs)
-    Dst.setMetadata(I.first, MapMetadata(I.second, ValueMap, RF_MoveDistinctMDs,
+    Dst.setMetadata(I.first, MapMetadata(I.second, ValueMap, ValueMapperFlags,
                                          &TypeMap, &ValMaterializer));
 
   // Splice the body of the source function into the dest function.
   Dst.getBasicBlockList().splice(Dst.end(), Src.getBasicBlockList());
 
   // At this point, all of the instructions and values of the function are now
   // copied over.  The only problem is that they are still referencing values in
   // the Source function as operands.  Loop through all of the operands of the
   // functions and patch them up to point to the local versions.
   for (BasicBlock &BB : Dst)
     for (Instruction &I : BB)
-      RemapInstruction(&I, ValueMap,
-                       RF_IgnoreMissingEntries | RF_MoveDistinctMDs, &TypeMap,
-                       &ValMaterializer);
+      RemapInstruction(&I, ValueMap, RF_IgnoreMissingEntries | ValueMapperFlags,
+                       &TypeMap, &ValMaterializer);
 
   // There is no need to map the arguments anymore.
   for (Argument &Arg : Src.args())
     ValueMap.erase(&Arg);
 
   Src.dematerialize();
   return false;
 }
 
 void ModuleLinker::linkAliasBody(GlobalAlias &Dst, GlobalAlias &Src) {
   Constant *Aliasee = Src.getAliasee();
-  Constant *Val = MapValue(Aliasee, ValueMap, RF_MoveDistinctMDs, &TypeMap,
-                           &ValMaterializer);
+  Constant *Val =
+      MapValue(Aliasee, ValueMap, ValueMapperFlags, &TypeMap, &ValMaterializer);
   Dst.setAliasee(Val);
 }
 
 bool ModuleLinker::linkGlobalValueBody(GlobalValue &Src) {
   Value *Dst = ValueMap[&Src];
   assert(Dst);
   if (const Comdat *SC = Src.getComdat()) {
     // To ensure that we don't generate an incomplete comdat group,
bool ModuleLinker::linkGlobalValueBody(GlobalValue &Src) {
   if (auto *GVar = dyn_cast<GlobalVariable>(&Src)) {
     linkGlobalInit(cast<GlobalVariable>(*Dst), *GVar);
     return false;
   }
   linkAliasBody(cast<GlobalAlias>(*Dst), cast<GlobalAlias>(Src));
   return false;
 }
 
+void ModuleLinker::findNeededSubprograms(ValueToValueMapTy &ValueMap) {
+  // Track unneeded nodes to make it simpler to handle the case
+  // where we are checking if an already-mapped SP is needed.
+  NamedMDNode *CompileUnits = SrcM->getNamedMetadata("llvm.dbg.cu");
+  if (!CompileUnits)
+    return;
+  UnneededSubprograms = new SmallPtrSet<const Metadata *, 16>();
+  for (unsigned I = 0, E = CompileUnits->getNumOperands(); I != E; ++I) {
+    auto *CU = cast<DICompileUnit>(CompileUnits->getOperand(I));
+    assert(CU && "Expected valid compile unit");
+    for (const Metadata *Op : CU->getSubprograms()->operands()) {
+      // Unless we were doing function importing and deferred metadata linking,
+      // any needed SPs should have been mapped as they would be reached
+      // from the function linked in (either on the function itself for linked
+      // function bodies, or from DILocation on inlined instructions).
+      assert(!(ValueMap.MD()[Op] && isMetadataLinkingPostpass()) &&
+             "DISubprogram shouldn't be mapped yet");
+      if (!ValueMap.MD()[Op])
+        UnneededSubprograms->insert(Op);
+    }
+  }
+  if (!isMetadataLinkingPostpass())
+    return;
+  // In the case of metadata linking as a postpass (e.g. for function
+  // importing), see which DISubprogram MD from the source has an associated
+  // temporary metadata node, which means the SP was needed by an imported
+  // function.
+  for (auto MDI : MDValueToValIDMap) {
+    const MDNode *Node = dyn_cast<MDNode>(MDI.first);
+    if (!Node)
+      continue;
+    DISubprogram *SP = getDISubprogram(Node);
+    if (!SP || !ValIDToTempMDMap->count(MDI.second))
+      continue;
+    UnneededSubprograms->erase(SP);
+  }
+}
+
+// Squash null subprograms from compile unit subprogram lists.
+void ModuleLinker::stripNullSubprograms() {
+  NamedMDNode *CompileUnits = DstM->getNamedMetadata("llvm.dbg.cu");
+  if (CompileUnits) {
+    for (unsigned I = 0, E = CompileUnits->getNumOperands(); I != E; ++I) {
+      auto *CU = cast<DICompileUnit>(CompileUnits->getOperand(I));
+      assert(CU && "Expected valid compile unit");
+
+      SmallVector<Metadata *, 16> NewSPs;
+      NewSPs.reserve(CU->getSubprograms().size());
+      bool FoundNull = false;
+      for (DISubprogram *SP : CU->getSubprograms()) {
+        if (!SP) {
+          FoundNull = true;
+          continue;
+        }
+        NewSPs.push_back(SP);
+      }
+      if (FoundNull)
+        CU->replaceSubprograms(MDTuple::get(CU->getContext(), NewSPs));
+    }
+  }
+}
+
 /// Insert all of the named MDNodes in Src into the Dest module.
 void ModuleLinker::linkNamedMDNodes() {
+  findNeededSubprograms(ValueMap);
   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
   for (const NamedMDNode &NMD : SrcM->named_metadata()) {
     // Don't link module flags here. Do them separately.
     if (&NMD == SrcModFlags)
       continue;
     NamedMDNode *DestNMD = DstM->getOrInsertNamedMetadata(NMD.getName());
     // Add Src elements into Dest node.
     for (const MDNode *op : NMD.operands())
       DestNMD->addOperand(MapMetadata(
-          op, ValueMap, RF_MoveDistinctMDs | RF_NullMapMissingGlobalValues,
+          op, ValueMap, ValueMapperFlags | RF_NullMapMissingGlobalValues,
           &TypeMap, &ValMaterializer));
   }
+  stripNullSubprograms();
 }
 
 /// Merge the linker flags in Src into the Dest module.
 bool ModuleLinker::linkModuleFlagsMetadata() {
   // If the source module has no module flags, we are done.
   const NamedMDNode *SrcModFlags = SrcM->getModuleFlagsMetadata();
   if (!SrcModFlags) return false;
 
for (Function &F :*SrcM)
     if (linkGlobalValueProto(&F))
       return true;
 
   // If there were any aliases, link them now.
   for (GlobalAlias &GA : SrcM->aliases())
     if (linkGlobalValueProto(&GA))
       return true;
 
+  if (isMetadataLinkingPostpass()) {
+    // Ensure metadata materialized
+    if (SrcM->getMaterializer()->materializeMetadata())
+      return true;
+    SrcM->getMaterializer()->saveMDValueList(MDValueToValIDMap, false);
+
+    linkNamedMDNodes();
+
+    // Handle anything left in the ValIDToTempMDMap, such as metadata nodes
+    // not reached by the dbg.cu NamedMD (i.e. only reached from instructions).
+    // Walk the MDValueToValIDMap once to find the set of new (imported) MD
+    // that still has corresponding temporary metadata, and invoke metadata
+    // mapping on each one.
+    for (auto MDI : MDValueToValIDMap) {
+      if (!ValIDToTempMDMap->count(MDI.second))
+        continue;
+      MapMetadata(MDI.first, ValueMap, ValueMapperFlags, &TypeMap,
+                  &ValMaterializer);
+    }
+    assert(ValIDToTempMDMap->empty());
+
+    // Merge the module flags into the DstM module.
+    if (linkModuleFlagsMetadata())
+      return true;
+
+    return false;
+  }
+
   for (const AppendingVarInfo &AppendingVar : AppendingVars)
     linkAppendingVarInit(AppendingVar);
 
   for (const auto &Entry : DstM->getComdatSymbolTable()) {
     const Comdat &C = Entry.getValue();
     if (C.getSelectionKind() == Comdat::Any)
       continue;
     const GlobalValue *GV = SrcM->getNamedValue(C.getName());
     if (GV)
-      MapValue(GV, ValueMap, RF_MoveDistinctMDs, &TypeMap, &ValMaterializer);
+      MapValue(GV, ValueMap, ValueMapperFlags, &TypeMap, &ValMaterializer);
   }
 
   // Link in the function bodies that are defined in the source module into
   // DstM.
   for (Function &SF : *SrcM) {
     // Skip if no body (function is external).
     if (SF.isDeclaration())
       continue;
bool ModuleLinker::run() {
 
   // Note that we are done linking global value bodies. This prevents
   // metadata linking from creating new references.
   DoneLinkingBodies = true;
 
   // Remap all of the named MDNodes in Src into the DstM module. We do this
   // after linking GlobalValues so that MDNodes that reference GlobalValues
   // are properly remapped.
+  if (shouldLinkMetadata()) {
     linkNamedMDNodes();
 
     // Merge the module flags into the DstM module.
     if (linkModuleFlagsMetadata())
       return true;
+  }
 
   return false;
 }
 
 Linker::StructTypeKeyInfo::KeyTy::KeyTy(ArrayRef<Type *> E, bool P)
     : ETypes(E), IsPacked(P) {}
 
 Linker::StructTypeKeyInfo::KeyTy::KeyTy(const StructType *ST)

 }
 
 void Linker::deleteModule() {
   delete Composite;
   Composite = nullptr;
 }
 
 bool Linker::linkInModule(Module *Src, unsigned Flags, FunctionInfoIndex *Index,
-                          Function *FuncToImport) {
+                          Function *FuncToImport,
+                          DenseMap<unsigned, MDNode *> *ValIDToTempMDMap) {
   ModuleLinker TheLinker(Composite, IdentifiedStructTypes, Src,
-                         DiagnosticHandler, Flags, Index, FuncToImport);
+                         DiagnosticHandler, Flags, Index, FuncToImport,
+                         ValIDToTempMDMap);
   bool RetCode = TheLinker.run();
+  if (!(Flags & Linker::MetadataLinkingPostpass))
     Composite->dropTriviallyDeadConstantArrays();
   return RetCode;
 }
 
 void Linker::setModule(Module *Dst) {
   init(Dst, DiagnosticHandler);
 }
 
 //===----------------------------------------------------------------------===//

lib/Transforms/Utils/ValueMapper.cpp

if (isa<UndefValue>(C))
     return VM[V] = UndefValue::get(NewTy);
   if (isa<ConstantAggregateZero>(C))
     return VM[V] = ConstantAggregateZero::get(NewTy);
   assert(isa<ConstantPointerNull>(C));
   return VM[V] = ConstantPointerNull::get(cast<PointerType>(NewTy));
 }
 
 static Metadata *mapToMetadata(ValueToValueMapTy &VM, const Metadata *Key,
-                     Metadata *Val) {
+                               Metadata *Val, ValueMaterializer *Materializer,
+                               RemapFlags Flags) {
   VM.MD()[Key].reset(Val);
+  if (Materializer && !(Flags & RF_HaveUnmaterializedMetadata)) {
+    auto *N = dyn_cast_or_null<MDNode>(Val);
+    // Need to invoke this once we have non-temporary MD.
+    if (!N || !N->isTemporary())
+      Materializer->replaceTemporaryMetadata(Key, Val);
+  }
   return Val;
 }
 
-static Metadata *mapToSelf(ValueToValueMapTy &VM, const Metadata *MD) {
-  return mapToMetadata(VM, MD, const_cast<Metadata *>(MD));
+static Metadata *mapToSelf(ValueToValueMapTy &VM, const Metadata *MD,
+                           ValueMaterializer *Materializer, RemapFlags Flags) {
+  return mapToMetadata(VM, MD, const_cast<Metadata *>(MD), Materializer, Flags);
 }
 
 static Metadata *MapMetadataImpl(const Metadata *MD,
                                  SmallVectorImpl<MDNode *> &DistinctWorklist,
                                  ValueToValueMapTy &VM, RemapFlags Flags,
                                  ValueMapTypeRemapper *TypeMapper,
                                  ValueMaterializer *Materializer);
 
 static Metadata *mapMetadataOp(Metadata *Op,
                                SmallVectorImpl<MDNode *> &DistinctWorklist,
                                ValueToValueMapTy &VM, RemapFlags Flags,
                                ValueMapTypeRemapper *TypeMapper,
                                ValueMaterializer *Materializer) {
   if (!Op)
     return nullptr;
+
+  if (Materializer && !Materializer->isMetadataNeeded(Op))
+    return nullptr;
+
   if (Metadata *MappedOp = MapMetadataImpl(Op, DistinctWorklist, VM, Flags,
                                            TypeMapper, Materializer))
     return MappedOp;
   // Use identity map if MappedOp is null and we can ignore missing entries.
   if (Flags & RF_IgnoreMissingEntries)
     return Op;
 
   // FIXME: This assert crashes during bootstrap, but I think it should be
   // correct.  For now, just match behaviour from before the metadata/value
   // split.
   //
   //    assert((Flags & RF_NullMapMissingGlobalValues) &&
   //           "Referenced metadata not in value map!");
   return nullptr;
 }
 
 /// Resolve uniquing cycles involving the given metadata.
-static void resolveCycles(Metadata *MD) {
-  if (auto *N = dyn_cast_or_null<MDNode>(MD))
+static void resolveCycles(Metadata *MD, bool MDMaterialized) {
+  if (auto *N = dyn_cast_or_null<MDNode>(MD)) {
+    if (!MDMaterialized && N->isTemporary())
+      return;
     if (!N->isResolved())
-      N->resolveCycles();
+      N->resolveCycles(MDMaterialized);
+  }
 }
 
 /// Remap the operands of an MDNode.
 ///
 /// If \c Node is temporary, uniquing cycles are ignored.  If \c Node is
 /// distinct, uniquing cycles are resolved as they're found.
 ///
 /// \pre \c Node.isDistinct() or \c Node.isTemporary().
Metadata *New = mapMetadataOp(Old, DistinctWorklist, VM, Flags, TypeMapper,
                                   Materializer);
     if (Old != New) {
       AnyChanged = true;
       Node.replaceOperandWith(I, New);
 
       // Resolve uniquing cycles underneath distinct nodes on the fly so they
       // don't infect later operands.
       if (IsDistinct)
-        resolveCycles(New);
+        resolveCycles(New, !(Flags & RF_HaveUnmaterializedMetadata));
     }
   }
 
   return AnyChanged;
 }
 
 /// Map a distinct MDNode.
 ///
static Metadata *mapDistinctNode(const MDNode *Node,
   MDNode *NewMD;
   if (Flags & RF_MoveDistinctMDs)
     NewMD = const_cast<MDNode *>(Node);
   else
     NewMD = MDNode::replaceWithDistinct(Node->clone());
 
   // Remap operands later.
   DistinctWorklist.push_back(NewMD);
-  return mapToMetadata(VM, Node, NewMD);
+  return mapToMetadata(VM, Node, NewMD, Materializer, Flags);
 }
 
 /// \brief Map a uniqued MDNode.
 ///
 /// Uniqued nodes may not need to be recreated (they may map to themselves).
 static Metadata *mapUniquedNode(const MDNode *Node,
                                 SmallVectorImpl<MDNode *> &DistinctWorklist,
                                 ValueToValueMapTy &VM, RemapFlags Flags,
                                 ValueMapTypeRemapper *TypeMapper,
                                 ValueMaterializer *Materializer) {
-  assert(Node->isUniqued() && "Expected uniqued node");
+  assert(((Flags & RF_HaveUnmaterializedMetadata) ||
+          Node->isUniqued()) && "Expected uniqued node");
 
   // Create a temporary node and map it upfront in case we have a uniquing
   // cycle.  If necessary, this mapping will get updated by RAUW logic before
   // returning.
   auto ClonedMD = Node->clone();
-  mapToMetadata(VM, Node, ClonedMD.get());
+  mapToMetadata(VM, Node, ClonedMD.get(), Materializer, Flags);
   if (!remapOperands(*ClonedMD, DistinctWorklist, VM, Flags, TypeMapper,
                      Materializer)) {
     // No operands changed, so use the original.
     ClonedMD->replaceAllUsesWith(const_cast<MDNode *>(Node));
-    return const_cast<MDNode *>(Node);
+    // Even though replaceAllUsesWith would have replaced the value map
+    // entry, we need to explictly map with the final non-temporary node
+    // to replace any temporary metadata via the callback.
+    return mapToSelf(VM, Node, Materializer, Flags);
   }
 
-  // Uniquify the cloned node.
-  return MDNode::replaceWithUniqued(std::move(ClonedMD));
+  // Uniquify the cloned node. Explicitly map it with the final non-temporary
+  // node so that replacement of temporary metadata via the callback occurs.
+  return mapToMetadata(VM, Node,
+                       MDNode::replaceWithUniqued(std::move(ClonedMD)),
+                       Materializer, Flags);
 }
 
 static Metadata *MapMetadataImpl(const Metadata *MD,
                                  SmallVectorImpl<MDNode *> &DistinctWorklist,
                                  ValueToValueMapTy &VM, RemapFlags Flags,
                                  ValueMapTypeRemapper *TypeMapper,
                                  ValueMaterializer *Materializer) {
   // If the value already exists in the map, use it.
   if (Metadata *NewMD = VM.MD().lookup(MD).get())
     return NewMD;
 
   if (isa<MDString>(MD))
-    return mapToSelf(VM, MD);
+    return mapToSelf(VM, MD, Materializer, Flags);
 
   if (isa<ConstantAsMetadata>(MD))
     if ((Flags & RF_NoModuleLevelChanges))
-      return mapToSelf(VM, MD);
+      return mapToSelf(VM, MD, Materializer, Flags);
 
   if (const auto *VMD = dyn_cast<ValueAsMetadata>(MD)) {
     Value *MappedV =
         MapValue(VMD->getValue(), VM, Flags, TypeMapper, Materializer);
     if (VMD->getValue() == MappedV ||
         (!MappedV && (Flags & RF_IgnoreMissingEntries)))
-      return mapToSelf(VM, MD);
+      return mapToSelf(VM, MD, Materializer, Flags);
 
     // FIXME: This assert crashes during bootstrap, but I think it should be
     // correct.  For now, just match behaviour from before the metadata/value
     // split.
     //
     //    assert((MappedV || (Flags & RF_NullMapMissingGlobalValues)) &&
     //           "Referenced metadata not in value map!");
     if (MappedV)
-      return mapToMetadata(VM, MD, ValueAsMetadata::get(MappedV));
+      return mapToMetadata(VM, MD, ValueAsMetadata::get(MappedV), Materializer,
+                           Flags);
     return nullptr;
   }
 
   // Note: this cast precedes the Flags check so we always get its associated
   // assertion.
   const MDNode *Node = cast<MDNode>(MD);
 
   // If this is a module-level metadata and we know that nothing at the
   // module level is changing, then use an identity mapping.
   if (Flags & RF_NoModuleLevelChanges)
-    return mapToSelf(VM, MD);
+    return mapToSelf(VM, MD, Materializer, Flags);
 
   // Require resolved nodes whenever metadata might be remapped.
-  assert(Node->isResolved() && "Unexpected unresolved node");
+  assert(((Flags & RF_HaveUnmaterializedMetadata) ||
+          Node->isResolved()) && "Unexpected unresolved node");
+
+  if (Materializer && Node->isTemporary()) {
+    assert(Flags & RF_HaveUnmaterializedMetadata);
+    Metadata *TempMD =
+        Materializer->mapTemporaryMetadata(const_cast<Metadata *>(MD));
+    // If the above callback returned an existing temporary node, use it
+    // instead of the current temporary node. This happens when earlier
+    // function importing passes already created and saved a temporary
+    // metadata node for the same value id.
+    if (TempMD) {
+      mapToMetadata(VM, MD, TempMD, Materializer, Flags);
+      return TempMD;
+    }
+  }
 
   if (Node->isDistinct())
     return mapDistinctNode(Node, DistinctWorklist, VM, Flags, TypeMapper,
                            Materializer);
 
   return mapUniquedNode(Node, DistinctWorklist, VM, Flags, TypeMapper,
                         Materializer);
 }
 
 Metadata *llvm::MapMetadata(const Metadata *MD, ValueToValueMapTy &VM,
                             RemapFlags Flags, ValueMapTypeRemapper *TypeMapper,
                             ValueMaterializer *Materializer) {
   SmallVector<MDNode *, 8> DistinctWorklist;
   Metadata *NewMD = MapMetadataImpl(MD, DistinctWorklist, VM, Flags, TypeMapper,
                                     Materializer);
 
   // When there are no module-level changes, it's possible that the metadata
   // graph has temporaries.  Skip the logic to resolve cycles, since it's
   // unnecessary (and invalid) in that case.
   if (Flags & RF_NoModuleLevelChanges)
     return NewMD;
 
   // Resolve cycles involving the entry metadata.
-  resolveCycles(NewMD);
+  resolveCycles(NewMD, !(Flags & RF_HaveUnmaterializedMetadata));
 
   // Remap the operands of distinct MDNodes.
   while (!DistinctWorklist.empty())
     remapOperands(*DistinctWorklist.pop_back_val(), DistinctWorklist, VM, Flags,
                   TypeMapper, Materializer);
 
   return NewMD;
 }

test/Linker/Inputs/only-needed-debug-metadata.ll

+@X = external global i32
+
+declare i32 @foo()
+
+define void @bar() !dbg !4 {
+  load i32, i32* @X, !dbg !10
+  call i32 @foo(), !dbg !11
+  ret void, !dbg !12
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!7, !8}
+!llvm.ident = !{!9}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)", isOptimized: true, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3)
+!1 = !DIFile(filename: "linkused.b.c", directory: ".")
+!2 = !{}
+!3 = !{!4}
+!4 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 5, type: !5, isLocal: false, isDefinition: true, scopeLine: 5, isOptimized: true, variables: !2)
+!5 = !DISubroutineType(types: !6)
+!6 = !{null}
+!7 = !{i32 2, !"Dwarf Version", i32 4}
+!8 = !{i32 2, !"Debug Info Version", i32 3}
+!9 = !{!"clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)"}
+!10 = !DILocation(line: 6, column: 7, scope: !4)
+!11 = !DILocation(line: 6, column: 3, scope: !4)
+!12 = !DILocation(line: 7, column: 1, scope: !4)

test/Linker/Inputs/thinlto_funcimport_debug.ll

+; ModuleID = 'dbg_main.o'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define i32 @main() #0 !dbg !4 {
+entry:
+  %call = tail call i32 @func1(i32 10) #2, !dbg !11
+  %call1 = tail call i32 @func2(i32 10) #2, !dbg !12
+  ret i32 0, !dbg !13
+}
+
+declare i32 @func1(i32) #1
+
+declare i32 @func2(i32) #1
+
+attributes #0 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!8, !9}
+!llvm.ident = !{!10}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)", isOptimized: true, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3)
+!1 = !DIFile(filename: "dbg_main.c", directory: "/usr/local/google/home/tejohnson/llvm/tmp")
+!2 = !{}
+!3 = !{!4}
+!4 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 3, type: !5, isLocal: false, isDefinition: true, scopeLine: 3, isOptimized: true, variables: !2)
+!5 = !DISubroutineType(types: !6)
+!6 = !{!7}
+!7 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!8 = !{i32 2, !"Dwarf Version", i32 4}
+!9 = !{i32 2, !"Debug Info Version", i32 3}
+!10 = !{!"clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)"}
+!11 = !DILocation(line: 4, column: 3, scope: !4)
+!12 = !DILocation(line: 5, column: 3, scope: !4)
+!13 = !DILocation(line: 6, column: 1, scope: !4)

test/Linker/only-needed-debug-metadata.ll

+; RUN: llvm-as %s -o %t.bc
+; RUN: llvm-as %p/Inputs/only-needed-debug-metadata.ll -o %t2.bc
+
+; Without -only-needed, we need to link in both DISubprogram.
+; RUN: llvm-link -S %t2.bc %t.bc | FileCheck %s
+; CHECK: distinct !DISubprogram(name: "foo"
+; CHECK: distinct !DISubprogram(name: "unused"
+
+; With -only-needed, we only need to link in foo's DISubprogram.
+; RUN: llvm-link -S -only-needed %t2.bc %t.bc | FileCheck %s -check-prefix=ONLYNEEDED
+; ONLYNEEDED: distinct !DISubprogram(name: "foo"
+; ONLYNEEDED-NOT: distinct !DISubprogram(name: "unused"
+
+@X = global i32 5
+@U = global i32 6
+@U_linkonce = linkonce_odr hidden global i32 6
+define i32 @foo() !dbg !4 {
+    ret i32 7, !dbg !20
+}
+define i32 @unused() !dbg !10 {
+    ret i32 8, !dbg !21
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!16, !17}
+!llvm.ident = !{!18}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)", isOptimized: true, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3, globals: !13)
+!1 = !DIFile(filename: "linkused2.c", directory: "/usr/local/google/home/tejohnson/llvm/tmp")
+!2 = !{}
+!3 = !{!4, !10}
+!4 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 4, type: !5, isLocal: false, isDefinition: true, scopeLine: 4, flags: DIFlagPrototyped, isOptimized: true, variables: !8)
+!5 = !DISubroutineType(types: !6)
+!6 = !{!7, !7}
+!7 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!8 = !{!9}
+!9 = !DILocalVariable(name: "x", arg: 1, scope: !4, file: !1, line: 4, type: !7)
+!10 = distinct !DISubprogram(name: "unused", scope: !1, file: !1, line: 8, type: !11, isLocal: false, isDefinition: true, scopeLine: 8, isOptimized: true, variables: !2)
+!11 = !DISubroutineType(types: !12)
+!12 = !{!7}
+!13 = !{!14, !15}
+!14 = !DIGlobalVariable(name: "X", scope: !0, file: !1, line: 1, type: !7, isLocal: false, isDefinition: true, variable: i32* @X)
+!15 = !DIGlobalVariable(name: "U", scope: !0, file: !1, line: 2, type: !7, isLocal: false, isDefinition: true, variable: i32* @U)
+!16 = !{i32 2, !"Dwarf Version", i32 4}
+!17 = !{i32 2, !"Debug Info Version", i32 3}
+!18 = !{!"clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)"}
+!19 = !DIExpression()
+!20 = !DILocation(line: 4, column: 13, scope: !4)
+!21 = !DILocation(line: 9, column: 3, scope: !10)

test/Linker/thinlto_funcimport_debug.ll

+; Do setup work for all below tests: generate bitcode and combined index
+; RUN: llvm-as -function-summary %s -o %t.bc
+; RUN: llvm-as -function-summary %p/Inputs/thinlto_funcimport_debug.ll -o %t2.bc
+; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
+
+; If we import func1 and not func2 we should only link DISubprogram for func1
+; RUN: llvm-link %t2.bc -functionindex=%t3.thinlto.bc -import=func1:%t.bc -S | FileCheck %s
+
+; CHECK: declare i32 @func2
+; CHECK: define available_externally i32 @func1
+; CHECK: distinct !DISubprogram(name: "func1"
+; CHECK-NOT: distinct !DISubprogram(name: "func2"
+
+; ModuleID = 'dbg.o'
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind readnone uwtable
+define i32 @func1(i32 %n) #0 !dbg !4 {
+entry:
+  tail call void @llvm.dbg.value(metadata i32 %n, i64 0, metadata !9, metadata !17), !dbg !18
+  tail call void @llvm.dbg.value(metadata i32 5, i64 0, metadata !10, metadata !17), !dbg !19
+  %cmp = icmp sgt i32 %n, 10, !dbg !20
+  %. = select i1 %cmp, i32 10, i32 5, !dbg !22
+  tail call void @llvm.dbg.value(metadata i32 %., i64 0, metadata !10, metadata !17), !dbg !19
+  ret i32 %., !dbg !23
+}
+
+; Function Attrs: nounwind readnone uwtable
+define i32 @func2(i32 %n) #0 !dbg !11 {
+entry:
+  tail call void @llvm.dbg.value(metadata i32 %n, i64 0, metadata !13, metadata !17), !dbg !24
+  ret i32 %n, !dbg !25
+}
+
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.value(metadata, i64, metadata, metadata) #1
+
+attributes #0 = { nounwind readnone uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind readnone }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!14, !15}
+!llvm.ident = !{!16}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)", isOptimized: true, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3)
+!1 = !DIFile(filename: "dbg.c", directory: "/usr/local/google/home/tejohnson/llvm/tmp")
+!2 = !{}
+!3 = !{!4, !11}
+!4 = distinct !DISubprogram(name: "func1", scope: !1, file: !1, line: 1, type: !5, isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagPrototyped, isOptimized: true, variables: !8)
+!5 = !DISubroutineType(types: !6)
+!6 = !{!7, !7}
+!7 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!8 = !{!9, !10}
+!9 = !DILocalVariable(name: "n", arg: 1, scope: !4, file: !1, line: 1, type: !7)
+!10 = !DILocalVariable(name: "x", scope: !4, file: !1, line: 2, type: !7)
+!11 = distinct !DISubprogram(name: "func2", scope: !1, file: !1, line: 8, type: !5, isLocal: false, isDefinition: true, scopeLine: 8, flags: DIFlagPrototyped, isOptimized: true, variables: !12)
+!12 = !{!13}
+!13 = !DILocalVariable(name: "n", arg: 1, scope: !11, file: !1, line: 8, type: !7)
+!14 = !{i32 2, !"Dwarf Version", i32 4}
+!15 = !{i32 2, !"Debug Info Version", i32 3}
+!16 = !{!"clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)"}
+!17 = !DIExpression()
+!18 = !DILocation(line: 1, column: 15, scope: !4)
+!19 = !DILocation(line: 2, column: 7, scope: !4)
+!20 = !DILocation(line: 3, column: 9, scope: !21)
+!21 = distinct !DILexicalBlock(scope: !4, file: !1, line: 3, column: 7)
+!22 = !DILocation(line: 3, column: 7, scope: !4)
+!23 = !DILocation(line: 5, column: 3, scope: !4)
+!24 = !DILocation(line: 8, column: 15, scope: !11)
+!25 = !DILocation(line: 9, column: 3, scope: !11)

test/tools/gold/X86/Inputs/linkonce-weak.ll

-define weak_odr void @f() {
-  ret void
+define weak_odr void @f() !dbg !4 {
+  ret void, !dbg !10
 }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!7, !8}
+!llvm.ident = !{!9}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)", isOptimized: true, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3)
+!1 = !DIFile(filename: "linkonce-weak.c", directory: ".")
+!2 = !{}
+!3 = !{!4}
+!4 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 1, type: !5, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, variables: !2)
+!5 = !DISubroutineType(types: !6)
+!6 = !{null}
+!7 = !{i32 2, !"Dwarf Version", i32 4}
+!8 = !{i32 2, !"Debug Info Version", i32 3}
+!9 = !{!"clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)"}
+!10 = !DILocation(line: 2, column: 1, scope: !4)
+

test/tools/gold/X86/linkonce-weak.ll

 ; RUN: llvm-as %s -o %t.o
 ; RUN: llvm-as %p/Inputs/linkonce-weak.ll -o %t2.o
 
 ; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \
 ; RUN:    --plugin-opt=emit-llvm \
 ; RUN:    -shared %t.o %t2.o -o %t3.o
 ; RUN: llvm-dis %t3.o -o - | FileCheck %s
 
 ; RUN: %gold -plugin %llvmshlibdir/LLVMgold.so \
 ; RUN:    --plugin-opt=emit-llvm \
 ; RUN:    -shared %t2.o %t.o -o %t3.o
 ; RUN: llvm-dis %t3.o -o - | FileCheck %s
 
-define linkonce_odr void @f() {
-  ret void
+define linkonce_odr void @f() !dbg !4 {
+  ret void, !dbg !10
 }
 
 ; Test that we get a weak_odr regardless of the order of the files
-; CHECK: define weak_odr void @f() {
+; CHECK: define weak_odr void @f()
+
+; Test that we only get a single DISubprogram for @f
+; CHECK: !DISubprogram(name: "f"
+; CHECK-NOT: !DISubprogram(name: "f"
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!7, !8}
+!llvm.ident = !{!9}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)", isOptimized: true, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3)
+!1 = !DIFile(filename: "linkonce-weak.c", directory: ".")
+!2 = !{}
+!3 = !{!4}
+!4 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 1, type: !5, isLocal: false, isDefinition: true, scopeLine: 1, isOptimized: true, variables: !2)
+!5 = !DISubroutineType(types: !6)
+!6 = !{null}
+!7 = !{i32 2, !"Dwarf Version", i32 4}
+!8 = !{i32 2, !"Debug Info Version", i32 3}
+!9 = !{!"clang version 3.8.0 (trunk 251407) (llvm/trunk 251401)"}
+!10 = !DILocation(line: 2, column: 1, scope: !4)
+

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

default: return nullptr;
       STRINGIFY_CODE(MODULE_CODE, SECTIONNAME)
       STRINGIFY_CODE(MODULE_CODE, DEPLIB) // FIXME: Remove in 4.0
       STRINGIFY_CODE(MODULE_CODE, GLOBALVAR)
       STRINGIFY_CODE(MODULE_CODE, FUNCTION)
       STRINGIFY_CODE(MODULE_CODE, ALIAS)
       STRINGIFY_CODE(MODULE_CODE, PURGEVALS)
       STRINGIFY_CODE(MODULE_CODE, GCNAME)
       STRINGIFY_CODE(MODULE_CODE, VSTOFFSET)
+      STRINGIFY_CODE(MODULE_CODE, METADATA_VALUES)
     }
   case bitc::IDENTIFICATION_BLOCK_ID:
     switch (CodeID) {
     default:
       return nullptr;
       STRINGIFY_CODE(IDENTIFICATION_CODE, STRING)
       STRINGIFY_CODE(IDENTIFICATION_CODE, EPOCH)
     }

tools/llvm-link/llvm-link.cpp

 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/PrettyStackTrace.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/SystemUtils.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include <memory>
+#if 0
+#include <iostream>
+#include <sstream>
+#endif
 using namespace llvm;
 
 static cl::list<std::string>
 InputFilenames(cl::Positional, cl::OneOrMore,
                cl::desc("<input bitcode files>"));
 
 static cl::list<std::string> OverridingInputs(
     "override", cl::ZeroOrMore, cl::value_desc("filename"),

 static cl::opt<bool> PreserveAssemblyUseListOrder(
     "preserve-ll-uselistorder",
     cl::desc("Preserve use-list order when writing LLVM assembly."),
     cl::init(false), cl::Hidden);
 
 // Read the specified bitcode file in and return it. This routine searches the
 // link path for the specified file to try to find it...
 //
-static std::unique_ptr<Module>
-loadFile(const char *argv0, const std::string &FN, LLVMContext &Context) {
+static std::unique_ptr<Module> loadFile(const char *argv0,
+                                        const std::string &FN,
+                                        LLVMContext &Context,
+                                        bool MaterializeMetadata = true) {
   SMDiagnostic Err;
   if (Verbose) errs() << "Loading '" << FN << "'\n";
-  std::unique_ptr<Module> Result = getLazyIRFileModule(FN, Err, Context);
+  std::unique_ptr<Module> Result =
+      getLazyIRFileModule(FN, Err, Context, !MaterializeMetadata);
   if (!Result)
     Err.print(argv0, errs());
 
+  if (MaterializeMetadata) {
     Result->materializeMetadata();
     UpgradeDebugInfo(*Result);
+  }
 
   return Result;
 }
 
 static void diagnosticHandler(const DiagnosticInfo &DI) {
   unsigned Severity = DI.getSeverity();
   switch (Severity) {
   case DS_Error:
loadIndex(LLVMContext &Context, const Module *ExportingModule = nullptr) {
 
   object::FunctionIndexObjectFile &Obj = **ObjOrErr;
   return Obj.takeIndex();
 }
 
 /// Import any functions requested via the -import option.
 static bool importFunctions(const char *argv0, LLVMContext &Context,
                             Linker &L) {
+  StringMap<DenseMap<unsigned, MDNode *> *> ModuleToTempMDValsMap;
   for (const auto &Import : Imports) {
     // Identify the requested function and its bitcode source file.
     size_t Idx = Import.find(':');
     if (Idx == std::string::npos) {
       errs() << "Import parameter bad format: " << Import << "\n";
       return false;
     }
     std::string FunctionName = Import.substr(0, Idx);
     std::string FileName = Import.substr(Idx + 1, std::string::npos);
 
     // Load the specified source module.
-    std::unique_ptr<Module> M = loadFile(argv0, FileName, Context);
+    std::unique_ptr<Module> M = loadFile(argv0, FileName, Context, false);
     if (!M.get()) {
       errs() << argv0 << ": error loading file '" << FileName << "'\n";
       return false;
     }
 
     if (verifyModule(*M, &errs())) {
       errs() << argv0 << ": " << FileName
              << ": error: input module is broken!\n";
if (!FunctionIndex.empty()) {
       std::error_code EC = IndexOrErr.getError();
       if (EC) {
         errs() << EC.message() << '\n';
         return false;
       }
       Index = std::move(IndexOrErr.get());
     }
 
+    // Save the mapping of value ids to temporary metadata created when
+    // importing this function. If we have already imported from this module,
+    // add new temporary metadata to the existing mapping.
+    DenseMap<unsigned, MDNode *> *TempMDVals = ModuleToTempMDValsMap[FileName];
+    if (!TempMDVals)
+      TempMDVals = ModuleToTempMDValsMap[FileName] =
+          new DenseMap<unsigned, MDNode *>();
+
     // Link in the specified function.
-    if (L.linkInModule(M.get(), Linker::Flags::None, Index.get(), F))
+    if (L.linkInModule(M.get(), Linker::Flags::None, Index.get(), F,
+                       TempMDVals))
+      return false;
+  }
+
+  // Now link in metadata for all modules from which we imported functions.
+  for (StringMapEntry<DenseMap<unsigned, MDNode *> *> &SME :
+       ModuleToTempMDValsMap) {
+    // Load the specified source module.
+    std::unique_ptr<Module> M = loadFile(argv0, SME.getKey(), Context, true);
+    if (!M.get()) {
+      errs() << argv0 << ": error loading file '" << SME.getKey() << "'\n";
+      return false;
+    }
+
+    if (verifyModule(*M, &errs())) {
+      errs() << argv0 << ": " << SME.getKey()
+             << ": error: input module is broken!\n";
+      return false;
+    }
+
+    // Link in all necessary metadata from this module.
+    if (L.linkInModule(M.get(), Linker::Flags::MetadataLinkingPostpass, nullptr,
+                       nullptr, SME.getValue()))
       return false;
   }
   return true;
 }
 
 static bool linkFiles(const char *argv0, LLVMContext &Context, Linker &L,
                       const cl::list<std::string> &Files,
                       unsigned Flags) {