[ThinLTO/LTO] Don't link in unneeded metadata

[tejohnson]

Summary

Third patch split out from http://reviews.llvm.org/D14752.

Only map in needed DISubroutine metadata (imported or otherwise linked
in functions and other DISubroutine referenced by inlined instructions).
This is supported for ThinLTO, LTO and llvm-link --only-needed, with
associated tests for each one.

Depends on D14838.

[tejohnson]

Ping.
Thanks, Teresa

[mehdi_amini]

lib/Linker/LinkModules.cpp

482

Replace with a real member instead of a pointer.

1069

And test for emptiness instead of null.

1793

Remove :)

1826

Is there a test for this? I'm not sure I saw a CHECK-NOT: null line or something equivalent?

1828

early exit

[mehdi_amini]

LGTM with the previous comments :)

[tejohnson]

Thanks for the review. Rebased and addressed all your comments. Final version going in shortly.

lib/Linker/LinkModules.cpp

482

Done, along with your related suggestions that fall out as a result of this change.

1826

I added one to test/Linker/thinlto_funcimport_debug.ll. Turns out there is a verifier assert that fires if you have null in the SP list. I had to comment that out temporarily to test my new check. But I think it makes sense to check for it explicitly in the test case too.

1828

Done

[abadams]

I'm getting segfaults where CU->getSubprograms() in findNeededSubprograms is returning null and then being dereferenced.

See https://llvm.org/bugs/show_bug.cgi?id=25917

Commenting here so that hopefully the right people see the bug.

[tejohnson]

Hi Andrew,

This was also reported in https://llvm.org/bugs/show_bug.cgi?id=25915
and I have a fix, just working on a test case.

Teresa

[abadams]

Looks like Ivan beat me to it. Thanks Teresa, and sorry for the duplicate
bug.

• Andrew

include/llvm/Transforms/Utils/ValueMapper.h

public:
     /// 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)

lib/Linker/LinkModules.cpp

public:
   /// 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 {
   /// 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,
                DenseMap<unsigned, MDNode *> *ValIDToTempMDMap = nullptr)
       : DstM(dstM), SrcM(srcM), TypeMap(Set),
         ValMaterializer(TypeMap, DstM, LazilyLinkGlobalValues, this),
         DiagnosticHandler(DiagnosticHandler), Flags(Flags),
         ValueMapperFlags(RF_MoveDistinctMDs), ImportIndex(Index),
         ImportFunction(FuncToImport), HasExportedFunctions(false),
-        DoneLinkingBodies(false), ValIDToTempMDMap(ValIDToTempMDMap) {
+        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);
public:
   /// 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:
 
   /// 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,
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];
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::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, 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;
 

lib/Transforms/Utils/ValueMapper.cpp

 
 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

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/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: distinct !DISubprogram(name: "func2"
+; 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:

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)