IR: Use ODR to unique DICompositeType members

Merge members that are describing the same member of the same ODR type,
even if other bits differ.  If the file or line differ, we don't care;
if anything else differs, it's an ODR violation (and we still don't
really care).

For DISubprogram declarations, this looks at the LinkageName and Scope.
For DW_TAG_member instances of DIDerivedType, this looks at the Name and
Scope.  In both cases, we know that the Scope follows ODR rules if it
has a non-empty identifier.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@266548 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 133 insertions, 2 deletions

diff --git a/docs/LangRef.rst b/docs/LangRef.rst
index b1edb500035..d3ad74ffd58 100644
--- a/docs/LangRef.rst
+++ b/docs/LangRef.rst
@@ -3976,7 +3976,10 @@ The following ``tag:`` values are valid:
 
 ``DW_TAG_member`` is used to define a member of a :ref:`composite type
 <DICompositeType>`. The type of the member is the ``baseType:``. The
-``offset:`` is the member's bit offset.
+``offset:`` is the member's bit offset.  If the composite type has a non-empty
+``identifier:``, then it respects ODR rules.  In that case, the ``scope:``
+reference will be a :ref:`metadata string <metadata-string>`, and the member
+will be uniqued solely based on its ``name:`` and ``scope:``.
 
 ``DW_TAG_inheritance`` and ``DW_TAG_friend`` are used in the ``elements:``
 field of :ref:`composite types <DICompositeType>` to describe parents and
@@ -4125,6 +4128,12 @@ metadata. The ``variables:`` field points at :ref:`variables <DILocalVariable>`
 that must be retained, even if their IR counterparts are optimized out of
 the IR. The ``type:`` field must point at an :ref:`DISubroutineType`.
 
+When ``isDefinition: false``, subprograms describe a declaration in the type
+tree as opposed to a definition of a funciton.  If the scope is a
+:ref:`metadata string <metadata-string>` then the composite type follows ODR
+rules, and the subprogram declaration is uniqued based only on its
+``linkageName:`` and ``scope:``.
+
 .. code-block:: llvm
 
     define void @_Z3foov() !dbg !0 {
@@ -4133,7 +4142,7 @@ the IR. The ``type:`` field must point at an :ref:`DISubroutineType`.
 
     !0 = distinct !DISubprogram(name: "foo", linkageName: "_Zfoov", scope: !1,
                                 file: !2, line: 7, type: !3, isLocal: true,
-                                isDefinition: false, scopeLine: 8,
+                                isDefinition: true, scopeLine: 8,
                                 containingType: !4,
                                 virtuality: DW_VIRTUALITY_pure_virtual,
                                 virtualIndex: 10, flags: DIFlagPrototyped,
diff --git a/lib/IR/LLVMContextImpl.h b/lib/IR/LLVMContextImpl.h
index bd61648264d..8a2c43909b4 100644
--- a/lib/IR/LLVMContextImpl.h
+++ b/lib/IR/LLVMContextImpl.h
@@ -32,6 +32,7 @@
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/ValueHandle.h"
+#include "llvm/Support/Dwarf.h"
 #include <vector>
 
 namespace llvm {
@@ -376,6 +377,12 @@ template <> struct MDNodeKeyImpl<DIDerivedType> {
            ExtraData == RHS->getRawExtraData();
   }
   unsigned getHashValue() const {
+    // If this is a member inside an ODR type, only hash the type and the name.
+    // Otherwise the hash will be stronger than
+    // MDNodeSubsetEqualImpl::isODRMember().
+    if (Tag == dwarf::DW_TAG_member && Name && Scope && isa<MDString>(Scope))
+      return hash_combine(Name, Scope);
+
     // Intentionally computes the hash on a subset of the operands for
     // performance reason. The subset has to be significant enough to avoid
     // collision "most of the time". There is no correctness issue in case of
@@ -384,6 +391,30 @@ template <> struct MDNodeKeyImpl<DIDerivedType> {
   }
 };
 
+template <> struct MDNodeSubsetEqualImpl<DIDerivedType> {
+  typedef MDNodeKeyImpl<DIDerivedType> KeyTy;
+  static bool isSubsetEqual(const KeyTy &LHS, const DIDerivedType *RHS) {
+    return isODRMember(LHS.Tag, LHS.Scope, LHS.Name, RHS);
+  }
+  static bool isSubsetEqual(const DIDerivedType *LHS, const DIDerivedType *RHS) {
+    return isODRMember(LHS->getTag(), LHS->getRawScope(), LHS->getRawName(),
+                       RHS);
+  }
+
+  /// Subprograms compare equal if they declare the same function in an ODR
+  /// type.
+  static bool isODRMember(unsigned Tag, const Metadata *Scope,
+                          const MDString *Name, const DIDerivedType *RHS) {
+    // Check whether the LHS is eligible.
+    if (Tag != dwarf::DW_TAG_member || !Name || !Scope || !isa<MDString>(Scope))
+      return false;
+
+    // Compare to the RHS.
+    return Tag == RHS->getTag() && Name == RHS->getRawName() &&
+           Scope == RHS->getRawScope();
+  }
+};
+
 template <> struct MDNodeKeyImpl<DICompositeType> {
   unsigned Tag;
   MDString *Name;
@@ -537,6 +568,12 @@ template <> struct MDNodeKeyImpl<DISubprogram> {
            Variables == RHS->getRawVariables();
   }
   unsigned getHashValue() const {
+    // If this is a declaration inside an ODR type, only hash the type and the
+    // name.  Otherwise the hash will be stronger than
+    // MDNodeSubsetEqualImpl::isDeclarationOfODRMember().
+    if (!IsDefinition && LinkageName && Scope && isa<MDString>(Scope))
+      return hash_combine(LinkageName, Scope);
+
     // Intentionally computes the hash on a subset of the operands for
     // performance reason. The subset has to be significant enough to avoid
     // collision "most of the time". There is no correctness issue in case of
@@ -545,6 +582,33 @@ template <> struct MDNodeKeyImpl<DISubprogram> {
   }
 };
 
+template <> struct MDNodeSubsetEqualImpl<DISubprogram> {
+  typedef MDNodeKeyImpl<DISubprogram> KeyTy;
+  static bool isSubsetEqual(const KeyTy &LHS, const DISubprogram *RHS) {
+    return isDeclarationOfODRMember(LHS.IsDefinition, LHS.Scope,
+                                    LHS.LinkageName, RHS);
+  }
+  static bool isSubsetEqual(const DISubprogram *LHS, const DISubprogram *RHS) {
+    return isDeclarationOfODRMember(LHS->isDefinition(), LHS->getRawScope(),
+                                    LHS->getRawLinkageName(), RHS);
+  }
+
+  /// Subprograms compare equal if they declare the same function in an ODR
+  /// type.
+  static bool isDeclarationOfODRMember(bool IsDefinition, const Metadata *Scope,
+                                       const MDString *LinkageName,
+                                       const DISubprogram *RHS) {
+    // Check whether the LHS is eligible.
+    if (IsDefinition || !Scope || !LinkageName || !Scope ||
+        !isa<MDString>(Scope))
+      return false;
+
+    // Compare to the RHS.
+    return IsDefinition == RHS->isDefinition() && Scope == RHS->getRawScope() &&
+           LinkageName == RHS->getRawLinkageName();
+  }
+};
+
 template <> struct MDNodeKeyImpl<DILexicalBlock> {
   Metadata *Scope;
   Metadata *File;
diff --git a/test/Assembler/dicompositetype-members.ll b/test/Assembler/dicompositetype-members.ll
new file mode 100644
index 00000000000..631023e7a55
--- /dev/null
+++ b/test/Assembler/dicompositetype-members.ll
@@ -0,0 +1,54 @@
+; RUN: llvm-as < %s | llvm-dis | llvm-as | llvm-dis | FileCheck %s
+; RUN: verify-uselistorder %s
+
+; Anchor the order of the nodes.
+!named = !{!0, !1, !2, !3, !4, !5, !6, !7, !8, !9, !10, !11, !12, !13, !14, !15, !16, !17}
+
+; Some basic building blocks.
+; CHECK:      !0 = !DIBasicType
+; CHECK-NEXT: !1 = !DIFile
+; CHECK-NEXT: !2 = !DIFile
+!0 = !DIBasicType(tag: DW_TAG_base_type, name: "name", size: 1, align: 2, encoding: DW_ATE_unsigned_char)
+!1 = !DIFile(filename: "path/to/file", directory: "/path/to/dir")
+!2 = !DIFile(filename: "path/to/other", directory: "/path/to/dir")
+
+; Define an identified type with fields and functions.
+; CHECK-NEXT: !3 = !DICompositeType(tag: DW_TAG_structure_type, name: "has-uuid",
+; CHECK-NEXT: !4 = !DIDerivedType(tag: DW_TAG_member, name: "field1", scope: !"has-uuid", file: !1
+; CHECK-NEXT: !5 = !DIDerivedType(tag: DW_TAG_member, name: "field2", scope: !"has-uuid", file: !1
+; CHECK-NEXT: !6 = !DISubprogram(name: "foo", linkageName: "foo1", scope: !"has-uuid", file: !1
+; CHECK-NEXT: !7 = !DISubprogram(name: "foo", linkageName: "foo2", scope: !"has-uuid", file: !1
+!3 = !DICompositeType(tag: DW_TAG_structure_type, name: "has-uuid", file: !1, line: 2, size: 64, align: 32, identifier: "uuid")
+!4 = !DIDerivedType(tag: DW_TAG_member, name: "field1", scope: !"has-uuid", file: !1, line: 4, baseType: !0, size: 32, align: 32, offset: 32)
+!5 = !DIDerivedType(tag: DW_TAG_member, name: "field2", scope: !"has-uuid", file: !1, line: 4, baseType: !0, size: 32, align: 32, offset: 32)
+!6 = !DISubprogram(name: "foo", linkageName: "foo1", scope: !"has-uuid", file: !1, isDefinition: false)
+!7 = !DISubprogram(name: "foo", linkageName: "foo2", scope: !"has-uuid", file: !1, isDefinition: false)
+
+; Define an un-identified type with fields and functions.
+; CHECK-NEXT: !8 = !DICompositeType(tag: DW_TAG_structure_type, name: "no-uuid", file: !1
+; CHECK-NEXT: !9 = !DIDerivedType(tag: DW_TAG_member, name: "field1", scope: !8, file: !1
+; CHECK-NEXT: !10 = !DIDerivedType(tag: DW_TAG_member, name: "field2", scope: !8, file: !1
+; CHECK-NEXT: !11 = !DISubprogram(name: "foo", linkageName: "foo1", scope: !8, file: !1
+; CHECK-NEXT: !12 = !DISubprogram(name: "foo", linkageName: "foo2", scope: !8, file: !1
+!8 = !DICompositeType(tag: DW_TAG_structure_type, name: "no-uuid", file: !1, line: 2, size: 64, align: 32)
+!9 = !DIDerivedType(tag: DW_TAG_member, name: "field1", scope: !8, file: !1, line: 4, baseType: !0, size: 32, align: 32, offset: 32)
+!10 = !DIDerivedType(tag: DW_TAG_member, name: "field2", scope: !8, file: !1, line: 4, baseType: !0, size: 32, align: 32, offset: 32)
+!11 = !DISubprogram(name: "foo", linkageName: "foo1", scope: !8, file: !1, isDefinition: false)
+!12 = !DISubprogram(name: "foo", linkageName: "foo2", scope: !8, file: !1, isDefinition: false)
+
+; Add duplicate fields and members of "no-uuid" in a different file.  These
+; should stick around, since "no-uuid" does not have an "identifier:" field.
+; CHECK-NEXT: !13 = !DIDerivedType(tag: DW_TAG_member, name: "field1", scope: !8, file: !2,
+; CHECK-NEXT: !14 = !DISubprogram(name: "foo", linkageName: "foo1", scope: !8, file: !2,
+!13 = !DIDerivedType(tag: DW_TAG_member, name: "field1", scope: !8, file: !2, line: 4, baseType: !0, size: 32, align: 32, offset: 32)
+!14 = !DISubprogram(name: "foo", linkageName: "foo1", scope: !8, file: !2, isDefinition: false)
+
+; Add duplicate fields and members of "has-uuid" in a different file.  These
+; should be merged.
+!15 = !DIDerivedType(tag: DW_TAG_member, name: "field1", scope: !"has-uuid", file: !2, line: 4, baseType: !0, size: 32, align: 32, offset: 32)
+!16 = !DISubprogram(name: "foo", linkageName: "foo1", scope: !"has-uuid", file: !2, isDefinition: false)
+
+; CHECK-NEXT: !15 = !{!4, !6}
+; CHECK-NOT: !DIDerivedType
+; CHECK-NOT: !DISubprogram
+!17 = !{!15, !16}
diff --git a/test/Linker/type-unique-odr-a.ll b/test/Linker/type-unique-odr-a.ll
index eeb1db763eb..d7640ea761c 100644
--- a/test/Linker/type-unique-odr-a.ll
+++ b/test/Linker/type-unique-odr-a.ll
@@ -4,6 +4,10 @@
 ; RUN:   | %llc_dwarf -dwarf-linkage-names=Enable -filetype=obj -O0 \
 ; RUN:   | llvm-dwarfdump -debug-dump=info - \
 ; RUN:   | FileCheck %s
+; RUN: llvm-link %p/type-unique-odr-b.ll %s -S -o - \
+; RUN:   | %llc_dwarf -dwarf-linkage-names=Enable -filetype=obj -O0 \
+; RUN:   | llvm-dwarfdump -debug-dump=info - \
+; RUN:   | FileCheck %s
 ;
 ; Test ODR-based type uniquing for C++ class members.
 ; rdar://problem/15851313.