COFF: Fix ICF correctness bug.

When comparing two COMDAT sections, we need to take section values
and associative sections into account. This patch fixes that bug.
It fixes a crash bug of llvm-tblgen when linked with /opt:lldicf.

One thing I don't understand yet is that this logic seems to be
too strict. MSVC linker is able to create more compact executables
(which of course work correctly). With this ICF algorithm, LLD is
able to make executable smaller, but the outputs are larger than
MSVC's. There must be something I'm missing here.

llvm-svn: 240897

6 files changed, 98 insertions, 6 deletions

diff --git a/lld/COFF/Chunks.cpp b/lld/COFF/Chunks.cpp
index aa2c0be3ef51..7a068eebf102 100644
--- a/lld/COFF/Chunks.cpp
+++ b/lld/COFF/Chunks.cpp
@@ -173,6 +173,13 @@ bool SectionChunk::equals(const SectionChunk *X) const {
   if (getContents() != X->getContents())
     return false;
 
+  // Compare associative sections
+  if (AssocChildren.size() != X->AssocChildren.size())
+    return false;
+  for (size_t I = 0, E = AssocChildren.size(); I != E; ++I)
+    if (AssocChildren[I]->Ptr != X->AssocChildren[I]->Ptr)
+      return false;
+
   // Compare relocations
   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
     if (R1.Type != R2.Type)
@@ -181,11 +188,13 @@ bool SectionChunk::equals(const SectionChunk *X) const {
       return false;
     SymbolBody *B1 = File->getSymbolBody(R1.SymbolTableIndex);
     SymbolBody *B2 = X->File->getSymbolBody(R2.SymbolTableIndex);
+    if (B1 == B2)
+      return true;
     auto *D1 = dyn_cast<DefinedRegular>(B1);
     auto *D2 = dyn_cast<DefinedRegular>(B2);
-    if (D1 && D2 && D1->getChunk() == D2->getChunk())
-      return true;
-    return B1 == B2;
+    return (D1 && D2 &&
+            D1->getValue() == D2->getValue() &&
+            D1->getChunk() == D2->getChunk());
   };
   return std::equal(Relocs.begin(), Relocs.end(), X->Relocs.begin(), Eq);
 }
diff --git a/lld/COFF/Chunks.h b/lld/COFF/Chunks.h
index 37a6003cf8ec..3b6bf5f7700b 100644
--- a/lld/COFF/Chunks.h
+++ b/lld/COFF/Chunks.h
@@ -151,7 +151,7 @@ private:
 
   const coff_section *Header;
   StringRef SectionName;
-  std::vector<Chunk *> AssocChildren;
+  std::vector<SectionChunk *> AssocChildren;
   llvm::iterator_range<const coff_relocation *> Relocs;
   size_t NumRelocs;
 
diff --git a/lld/COFF/Symbols.h b/lld/COFF/Symbols.h
index e0cb7b16acb0..f87b8f12d378 100644
--- a/lld/COFF/Symbols.h
+++ b/lld/COFF/Symbols.h
@@ -137,6 +137,7 @@ public:
   bool isLive() const { return (*Data)->isLive(); }
   void markLive() { (*Data)->markLive(); }
   Chunk *getChunk() { return *Data; }
+  uint64_t getValue() { return Sym.getValue(); }
 
 private:
   StringRef Name;
diff --git a/lld/test/COFF/Inputs/icf4.yaml b/lld/test/COFF/Inputs/icf4.yaml
new file mode 100644
index 000000000000..a013d5516ba2
--- /dev/null
+++ b/lld/test/COFF/Inputs/icf4.yaml
@@ -0,0 +1,47 @@
+---
+header:
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: []
+sections:
+  - Name:            .text
+    Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_LNK_COMDAT, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
+    Alignment:       16
+    SectionData:     0000000000000000
+  - Name:            .assoc
+    Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_LNK_COMDAT, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
+    Alignment:       16
+    SectionData:     0000000000000000
+symbols:
+  - Name:            .text
+    Value:           0
+    SectionNumber:   1
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+    SectionDefinition:
+      Length:          8
+      NumberOfRelocations: 0
+      NumberOfLinenumbers: 0
+      CheckSum:        0
+      Number:          0
+      Selection:       IMAGE_COMDAT_SELECT_ANY
+  # icf4 is *not* identical with mainCRTStartup because it has an associative section
+  - Name:            icf4
+    Value:           0
+    SectionNumber:   1
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
+    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
+  - Name:            .assoc
+    Value:           0
+    SectionNumber:   2
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+    SectionDefinition:
+      Length:          8
+      NumberOfRelocations: 0
+      NumberOfLinenumbers: 0
+      CheckSum:        0
+      Number:          1
+      Selection:       IMAGE_COMDAT_SELECT_ASSOCIATIVE
diff --git a/lld/test/COFF/Inputs/icf5.yaml b/lld/test/COFF/Inputs/icf5.yaml
new file mode 100644
index 000000000000..d5b5cbfd5b81
--- /dev/null
+++ b/lld/test/COFF/Inputs/icf5.yaml
@@ -0,0 +1,30 @@
+---
+header:
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: []
+sections:
+  - Name:            .text
+    Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_LNK_COMDAT, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
+    Alignment:       16
+    SectionData:     0000000000000000
+symbols:
+  - Name:            .text
+    Value:           0
+    SectionNumber:   1
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+    SectionDefinition:
+      Length:          8
+      NumberOfRelocations: 0
+      NumberOfLinenumbers: 0
+      CheckSum:        0
+      Number:          0
+      Selection:       IMAGE_COMDAT_SELECT_ANY
+  # icf5 is *not* identical with its symbol value is different
+  - Name:            icf5
+    Value:           5
+    SectionNumber:   1
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
+    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
diff --git a/lld/test/COFF/icf.test b/lld/test/COFF/icf.test
index d5ea949df6ff..cc4e856a9e1e 100644
--- a/lld/test/COFF/icf.test
+++ b/lld/test/COFF/icf.test
@@ -1,11 +1,16 @@
 # RUN: yaml2obj < %p/Inputs/icf1.yaml > %t1.obj
 # RUN: yaml2obj < %p/Inputs/icf2.yaml > %t2.obj
 # RUN: yaml2obj < %p/Inputs/icf3.yaml > %t3.obj
+# RUN: yaml2obj < %p/Inputs/icf4.yaml > %t4.obj
+# RUN: yaml2obj < %p/Inputs/icf5.yaml > %t5.obj
 #
-# RUN: lld -flavor link2 /out:%t.exe %t1.obj %t2.obj %t3.obj \
-# RUN:   /opt:lldicf /include:icf2 /include:icf3 /verbose >& %t.log
+# RUN: lld -flavor link2 /out:%t.exe %t1.obj %t2.obj %t3.obj %t4.obj %t5.obj \
+# RUN:   /opt:lldicf /include:icf2 /include:icf3 /include:icf4 /include:icf5 \
+# RUN:   /verbose >& %t.log
 # RUN: FileCheck %s < %t.log
 
 CHECK-NOT: Replaced mainCRTStartup
 CHECK:     Replaced icf2
 CHECK-NOT: Replaced icf3
+CHECK-NOT: Replaced icf4
+CHECK-NOT: Replaced icf5