[COFF] Only consider associated EH sections during ICF

[rnk]

Summary

The only known reason why ICF should not merge otherwise identical
sections with differing associated sections has to do with exception
handling tables. It's not clear what ICF should do when there are other
kinds of associated sections. In every other case when this has come up,
debug info and CF guard metadata, we have opted to make ICF ignore the
associated sections.

For comparison, ELF doesn't do anything for comdat groups. Instead,
.eh_frame is parsed to figure out if a section has an LSDA, and if so,
ICF is disabled.

Another issue is that the order of associated sections is not defined.
We have had issues in the past where changing the order of the
.xdata/.pdata sections in the object file lead to large ICF slowdowns.

To address these issues, I decided it would be best to explicitly
consider only .pdata and .xdata sections during ICF. This makes it easy
to ignore the object file order, and I think it makes the intention of
the code clearer.

I've also made the children() accessor return an empty list for
associated sections. This mostly only affects ICF and GC. This was the
behavior before I made this a linked list, so the behavior change should
be good. This had positive effects on chrome.dll: more .xdata sections
were merged that previously could not be merged because they were
associated with distinct .pdata sections.

[mstorsjo]

LGTM, this sounds sensible.

Would this have fixed the issue in https://bugs.chromium.org/p/chromium/issues/detail?id=1144476 ?

[rnk]

In D98993#2639507, @mstorsjo wrote:

LGTM, this sounds sensible.

Would this have fixed the issue in https://bugs.chromium.org/p/chromium/issues/detail?id=1144476 ?

Yes, thanks, that's the issue I was referring to. :) I was away from my email when I wrote this, so I couldn't even dig it up to add to the description.

[mstorsjo]

In D98993#2642758, @rnk wrote:

In D98993#2639507, @mstorsjo wrote:

LGTM, this sounds sensible.

Would this have fixed the issue in https://bugs.chromium.org/p/chromium/issues/detail?id=1144476 ?

Yes, thanks, that's the issue I was referring to. :) I was away from my email when I wrote this, so I couldn't even dig it up to add to the description.

Ah, nice. :-)

I actually have a couple follow-up patches relating to when/where xdata/pdata are emitted - I think they should be safe wrt ICF but I didn't bother to risk anything back when I wrote them.

[thakis]

This breaks asan's odr detector: https://bugs.chromium.org/p/chromium/issues/detail?id=1193130#c2

[akhuang]

Gonna revert this for now--

lld/COFF/Chunks.h

public:
     }
 
   private:
     SectionChunk *cur = nullptr;
   };
 
   // Allow iteration over the associated child chunks for this section.
   llvm::iterator_range<AssociatedIterator> children() const {
-    return llvm::make_range(AssociatedIterator(assocChildren),
-                            AssociatedIterator(nullptr));
+    // Associated sections do not have children. The assocChildren field is
+    // part of the parent's list of children.
+    bool isAssoc = selection == llvm::COFF::IMAGE_COMDAT_SELECT_ASSOCIATIVE;
+    return llvm::make_range(
+        AssociatedIterator(isAssoc ? nullptr : assocChildren),
   }
 
   // The section ID this chunk belongs to in its Obj.
   uint32_t getSectionNumber() const;
 
   ArrayRef<uint8_t> consumeDebugMagic();
 
   static ArrayRef<uint8_t> consumeDebugMagic(ArrayRef<uint8_t> data,

lld/COFF/ICF.cpp

 class ICF {
 public:
   ICF(ICFLevel icfLevel) : icfLevel(icfLevel){};
   void run(ArrayRef<Chunk *> v);
 
 private:
   void segregate(size_t begin, size_t end, bool constant);
 
-  bool assocEquals(const SectionChunk *a, const SectionChunk *b);
+  bool equalsEHData(const SectionChunk *a, const SectionChunk *b);
 
   bool equalsConstant(const SectionChunk *a, const SectionChunk *b);
   bool equalsVariable(const SectionChunk *a, const SectionChunk *b);
 
   bool isEligible(SectionChunk *c);
 
   size_t findBoundary(size_t begin, size_t end);
 
while (begin < end) {
     // If we created a group, we need to iterate the main loop again.
     if (mid != end)
       repeat = true;
 
     begin = mid;
   }
 }
 
-// Returns true if two sections' associative children are equal.
-bool ICF::assocEquals(const SectionChunk *a, const SectionChunk *b) {
-  // Ignore associated metadata sections that don't participate in ICF, such as
-  // debug info and CFGuard metadata.
-  auto considerForICF = [](const SectionChunk &assoc) {
-    StringRef Name = assoc.getSectionName();
-    return !(Name.startswith(".debug") || Name == ".gfids$y" ||
-             Name == ".giats$y" || Name == ".gljmp$y");
+// Returns true if two sections have equivalent associated .pdata/.xdata
+// sections.
+bool ICF::equalsEHData(const SectionChunk *a, const SectionChunk *b) {
+  auto findEHData = [](const SectionChunk *s) {
+    const SectionChunk *pdata = nullptr;
+    const SectionChunk *xdata = nullptr;
+    for (const SectionChunk &assoc : s->children()) {
+      StringRef name = assoc.getSectionName();
+      if (name.startswith(".pdata") && (name.size() == 6 || name[6] == '$'))
+        pdata = &assoc;
+      else if (name.startswith(".xdata") &&
+               (name.size() == 6 || name[6] == '$'))
+        xdata = &assoc;
+    }
+    return std::make_pair(pdata, xdata);
   };
-  auto ra = make_filter_range(a->children(), considerForICF);
-  auto rb = make_filter_range(b->children(), considerForICF);
-  return std::equal(ra.begin(), ra.end(), rb.begin(), rb.end(),
-                    [&](const SectionChunk &ia, const SectionChunk &ib) {
-                      return ia.eqClass[cnt % 2] == ib.eqClass[cnt % 2];
-                    });
+  auto aData = findEHData(a);
+  auto bData = findEHData(b);
+  auto considerEqual = [cnt = cnt](const SectionChunk *l,
+                                   const SectionChunk *r) {
+    return l == r || (l->getContents() == r->getContents() &&
+                      l->eqClass[cnt % 2] == r->eqClass[cnt % 2]);
+  };
+  return considerEqual(aData.first, bData.first) &&
+         considerEqual(aData.second, bData.second);
 }
 
 // Compare "non-moving" part of two sections, namely everything
 // except relocation targets.
 bool ICF::equalsConstant(const SectionChunk *a, const SectionChunk *b) {
   if (a->relocsSize != b->relocsSize)
     return false;
 
if (!std::equal(a->getRelocs().begin(), a->getRelocs().end(),
                   b->getRelocs().begin(), eq))
     return false;
 
   // Compare section attributes and contents.
   return a->getOutputCharacteristics() == b->getOutputCharacteristics() &&
          a->getSectionName() == b->getSectionName() &&
          a->header->SizeOfRawData == b->header->SizeOfRawData &&
          a->checksum == b->checksum && a->getContents() == b->getContents() &&
-         assocEquals(a, b);
+         equalsEHData(a, b);
 }
 
 // Compare "moving" part of two sections, namely relocation targets.
 bool ICF::equalsVariable(const SectionChunk *a, const SectionChunk *b) {
   // Compare relocations.
   auto eq = [&](const coff_relocation &r1, const coff_relocation &r2) {
     Symbol *b1 = a->file->getSymbol(r1.SymbolTableIndex);
     Symbol *b2 = b->file->getSymbol(r2.SymbolTableIndex);
     if (b1 == b2)
       return true;
     if (auto *d1 = dyn_cast<DefinedRegular>(b1))
       if (auto *d2 = dyn_cast<DefinedRegular>(b2))
         return d1->getChunk()->eqClass[cnt % 2] == d2->getChunk()->eqClass[cnt % 2];
     return false;
   };
   return std::equal(a->getRelocs().begin(), a->getRelocs().end(),
                     b->getRelocs().begin(), eq) &&
-         assocEquals(a, b);
+         equalsEHData(a, b);
 }
 
 // Find the first Chunk after Begin that has a different class from Begin.
 size_t ICF::findBoundary(size_t begin, size_t end) {
   for (size_t i = begin + 1; i < end; ++i)
     if (chunks[begin]->eqClass[cnt % 2] != chunks[i]->eqClass[cnt % 2])
       return i;
   return end;

lld/test/COFF/icf-assoc-order.s

+# REQUIRES: x86
+# RUN: llvm-mc %s -filetype=obj -triple=x86_64-windows-msvc -o %t.obj
+# RUN: lld-link %t.obj -export:foo -export:bar -dll -noentry -out:%t.dll -verbose 2>&1 | FileCheck %s
+# RUN: llvm-readobj --sections %t.dll | FileCheck %s --check-prefix=TEXT
+
+# The order of the pdata and xdata sections here shouldn't matter. We should
+# still replace bar with foo.
+
+# CHECK: ICF needed {{.*}} iterations
+# CHECK: Selected foo
+# CHECK: Removed bar
+
+# We should only have five bytes of text.
+# TEXT: Name: .text
+# TEXT-NEXT: Size: 0x5
+
+  .section  .text,"xr",discard,foo
+  .globl  foo
+foo:
+  pushq %rbx
+  pushq %rdi
+  popq %rdi
+  popq %rbx
+        retq
+
+
+.section .pdata,"r",associative,foo
+.long foo
+.long 5
+.long foo_xdata@IMGREL
+
+.section .xdata,"r",associative,foo
+foo_xdata:
+.long 42
+
+  .section  .text,"xr",discard,bar
+  .globl  bar
+bar:
+  pushq %rbx
+  pushq %rdi
+  popq %rdi
+  popq %rbx
+        retq
+
+.section .xdata,"r",associative,bar
+bar_xdata:
+.long 42
+
+.section .pdata,"r",associative,bar
+.long bar
+.long 5
+.long bar_xdata@IMGREL

lld/test/COFF/icf-xdata-last.s

+# REQUIRES: x86
+# RUN: llvm-mc %s -filetype=obj -triple=x86_64-windows-msvc -o %t.obj
+# RUN: lld-link %t.obj -export:foo -export:bar -dll -noentry -out:%t.dll -merge:.xdata=.xdata -verbose 2>&1 | FileCheck %s
+# RUN: llvm-readobj --sections %t.dll | FileCheck %s --check-prefix=XDATA
+
+# Test xdata can be merged when text and pdata differ. This test is structured
+# so that xdata comes after pdata, which makes xdata come before pdata in the
+# assocChildren linked list.
+
+# CHECK: ICF needed {{.*}} iterations
+# CHECK: Selected
+# CHECK: Removed
+
+# XDATA:         Name: .xdata
+# XDATA-NEXT:    VirtualSize: 0x4
+
+  .section  .text,"xr",discard,foo
+  .globl  foo
+foo:
+  pushq %rax
+  popq %rax
+        retq
+
+.section .pdata,"r",associative,foo
+.long foo
+.long 5
+.long foo_xdata@IMGREL
+
+
+.section .xdata,"r",associative,foo
+foo_xdata:
+.long 42
+
+  .section  .text,"xr",discard,bar
+  .globl  bar
+bar:
+  pushq %rcx
+  popq %rcx
+        retq
+
+.section .pdata,"r",associative,bar
+.long bar
+.long 5
+.long bar_xdata@IMGREL
+
+.section .xdata,"r",associative,bar
+bar_xdata:
+.long 42