COFF: ICF a section and its associated pdata section as a unit.

[pcc]

Summary

This is needed to avoid merging two functions with identical
instructions but different xdata. It also reduces binary size by
deduplicating identical pdata sections.

Fixes PR35337.

[rnk]

Looks good to me, but let @ruiu review for more style feedback.

It might be worth pointing out somewhere in comments that it's the xdata section that might differ, and the pdata section will refer to the xdata, which makes it appear different during ICF.

We're convinced .pdata is special, right? What about other applications of comdat associative metadata, like ASan global metadata? ASan typically doesn't register metadata for readonly globals, but if it did register different metadata for two readonly globals with the same contents that got folded by ICF, would that be correct?

The other main application of associative comdats is debug info. If we ICF two functions together, we probably want to toss the debug info for the function we choose to discard, otherwise the debugger might get confused. This needs testing and experimentation, but it something to think about, since this is another instance of metadata using labels to refer to offsets in ICF'ed code.

[pcc]

In D46672#1094887, @rnk wrote:

Looks good to me, but let @ruiu review for more style feedback.

It might be worth pointing out somewhere in comments that it's the xdata section that might differ, and the pdata section will refer to the xdata, which makes it appear different during ICF.

We're convinced .pdata is special, right? What about other applications of comdat associative metadata, like ASan global metadata?

I'm not sure that I'm convinced. A simpler rule that I can think of based on the observed behaviour is that

1. an associative reference is like a relocation from the parent to the child
2. pdata is special in the same way as xdata and vtables are: it is a magic section name that allows ICF.

We can see this by taking my example from crbug.com/838449#c8 and renaming the pdata section:

$ sed -e 's/pdata/qdata/g' 1.obj > 1q.obj

C:\src\tmp\pdata-test>link /noentry /opt:icf 1q.obj  2.obj /dll /map:1q.map /include:?f1@@YAXXZ /include:?f2@@YAXXZ
Microsoft (R) Incremental Linker Version 14.12.25835.0
Copyright (C) Microsoft Corporation.  All rights reserved.


C:\src\tmp\pdata-test>wsl grep f[12] 1q.map
 0001:00000000       ?f1@@YAXXZ                 0000000180001000 f   1q.obj
 0001:00000010       ?f2@@YAXXZ                 0000000180001010 f   1q.obj
 0002:0000007c       $unwind$?f2@@YAXXZ         000000018000207c     1q.obj
 0002:0000007c       $unwind$?f1@@YAXXZ         000000018000207c     1q.obj
 0003:00000000       $qdata$?f1@@YAXXZ          0000000180003000     1q.obj
 0003:0000000c       $qdata$?f2@@YAXXZ          000000018000300c     1q.obj

ASan typically doesn't register metadata for readonly globals, but if it did register different metadata for two readonly globals with the same contents that got folded by ICF, would that be correct?

I think that if asan named its associative globals like vtables to get around the ICF rodata rule, or if we started embedding address-significant information in the symbol table to allow for safe ICF, we would probably would want the "relocation" behaviour.

The other main application of associative comdats is debug info. If we ICF two functions together, we probably want to toss the debug info for the function we choose to discard, otherwise the debugger might get confused. This needs testing and experimentation, but it something to think about, since this is another instance of metadata using labels to refer to offsets in ICF'ed code.

Yes. In fact, debug info may be the special case here: a mismatching debug info shouldn't inhibit ICF.

I'll see how easy it is to implement the "simple" rule. If it doesn't work out, let's go with this patch.

[ruiu]

LGTM

lld/COFF/ICF.cpp

153–154 ↗

(On Diff #146059)

Maybe it is a bit cleaner if you simply pass A->Pdata and B->PData to equalsConstant (you would have to make a change to equalsConstant to allow a nullptr.)

[pcc]

• Better rule

[pcc]

Okay, this seems to be the rule that MSVC uses. With this, ICF seems to work as well as before. PTAL.

[ruiu]

lld/COFF/ICF.cpp

133 ↗

(On Diff #146357)

Is there any way to write this without creating temporary std::vector objects?

[smeenai]

lld/COFF/ICF.cpp

141 ↗

(On Diff #146357)

Is there a possibility of ChildClasses(A) and ChildClasses(B) having the same contents but in a different order? Would we want to ICF in that case? (Since right now the == is going to be doing an ordered comparison.)

[pcc]

lld/COFF/ICF.cpp

133 ↗

(On Diff #146357)

We could use a pair of iterators instead, but then we would have to handle skipping the debug/CFG sections in the right places, and I'm not sure that it's worth it.

141 ↗

(On Diff #146357)

It's theoretically possible, but it turns out that clang-cl (and probably cl as well?) always emits the associative sections in the same order. Initially I had a sort on the vector here, but I removed it because it turned out that it didn't make a difference when linking Chrome. MSVC doesn't seem to care about the order, so it would probably be fine to put it back.

[ruiu]

LGTM

lld/trunk/COFF/ICF.cpp

 
 class ICF {
 public:
   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 equalsConstant(const SectionChunk *A, const SectionChunk *B);
   bool equalsVariable(const SectionChunk *A, const SectionChunk *B);
 
   uint32_t getHash(SectionChunk *C);
   bool isEligible(SectionChunk *C);
 
   size_t findBoundary(size_t Begin, size_t End);
 
bool ICF::isEligible(SectionChunk *C) {
   bool Writable = C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
   if (!C->isCOMDAT() || !C->isLive() || Writable)
     return false;
 
   // Code sections are eligible.
   if (C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE)
     return true;
 
-  // .xdata unwind info sections are eligible.
-  if (C->getSectionName().split('$').first == ".xdata")
+  // .pdata and .xdata unwind info sections are eligible.
+  StringRef OutSecName = C->getSectionName().split('$').first;
+  if (OutSecName == ".pdata" || OutSecName == ".xdata")
     return true;
 
   // So are vtables.
   return C->Sym && C->Sym->getName().startswith("??_7");
 }
 
 // Split an equivalence class into smaller classes.
 void ICF::segregate(size_t Begin, size_t End, bool Constant) {
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) {
+  auto ChildClasses = [&](const SectionChunk *SC) {
+    std::vector<uint32_t> Classes;
+    for (const SectionChunk *C : SC->children())
+      if (!C->SectionName.startswith(".debug") &&
+          C->SectionName != ".gfids$y" && C->SectionName != ".gljmp$y")
+        Classes.push_back(C->Class[Cnt % 2]);
+    return Classes;
+  };
+  return ChildClasses(A) == ChildClasses(B);
+}
+
 // Compare "non-moving" part of two sections, namely everything
 // except relocation targets.
 bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
   if (A->Relocs.size() != B->Relocs.size())
     return false;
 
   // Compare relocations.
   auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
   };
   if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq))
     return false;
 
   // Compare section attributes and contents.
   return A->getOutputCharacteristics() == B->getOutputCharacteristics() &&
          A->SectionName == B->SectionName && A->Alignment == B->Alignment &&
          A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
-         A->Checksum == B->Checksum && A->getContents() == B->getContents();
+         A->Checksum == B->Checksum && A->getContents() == B->getContents() &&
+         assocEquals(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()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
     return false;
   };
-  return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq);
+  return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(),
+                    Eq) &&
+         assocEquals(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]->Class[Cnt % 2] != Chunks[I]->Class[Cnt % 2])
       return I;
   return End;

lld/trunk/test/COFF/icf-pdata.s

+# RUN: llvm-mc %s -triple x86_64-windows-msvc -filetype=obj -o %t.obj
+# RUN: lld-link %t.obj -dll -noentry -out:%t.dll -merge:.xdata=.xdata
+# RUN: llvm-readobj -sections -coff-exports %t.dll | FileCheck %s
+
+# CHECK:         Name: .pdata
+# CHECK-NEXT:    VirtualSize: 0x18
+# CHECK:         Name: .xdata
+# CHECK-NEXT:    VirtualSize: 0x10
+
+# CHECK:         Name: xdata1
+# CHECK-NEXT:    RVA: 0x1010
+# CHECK:         Name: xdata1a
+# CHECK-NEXT:    RVA: 0x1010
+# CHECK:         Name: xdata1b
+# CHECK-NEXT:    RVA: 0x1030
+
+  .text
+callee:
+  ret
+
+  .def   xdata1;
+  .scl  2;
+  .type 32;
+  .endef
+  .section  .text,"xr",one_only,xdata1
+  .globl  xdata1                  # -- Begin function xdata1
+  .p2align  4, 0x90
+xdata1:                                 # @xdata1
+.seh_proc xdata1
+# BB#0:                                 # %entry
+  subq  $40, %rsp
+  .seh_stackalloc 40
+  .seh_endprologue
+  callq callee
+  nop
+  addq  $40, %rsp
+  jmp callee                  # TAILCALL
+  .seh_handlerdata
+  .section  .text,"xr",one_only,xdata1
+  .seh_endproc
+                                        # -- End function
+
+# xdata1a is identical to xdata1, so it should be ICFd, and so should its pdata.
+# It also has associative debug and CFG sections which should be ignored by ICF.
+  .def   xdata1a;
+  .scl  2;
+  .type 32;
+  .endef
+  .section  .text,"xr",one_only,xdata1a
+  .globl  xdata1a                  # -- Begin function xdata1a
+  .p2align  4, 0x90
+xdata1a:                                 # @xdata1a
+.seh_proc xdata1a
+# BB#0:                                 # %entry
+  subq  $40, %rsp
+  .seh_stackalloc 40
+  .seh_endprologue
+  callq callee
+  nop
+  addq  $40, %rsp
+  jmp callee                  # TAILCALL
+  .seh_handlerdata
+  .section  .text,"xr",one_only,xdata1a
+  .seh_endproc
+
+  .section .debug$S,"r",associative,xdata1a
+  .section .gfids$y,"r",associative,xdata1a
+  .section .gljmp$y,"r",associative,xdata1a
+
+# xdata1b's text is identical to xdata1, but its xdata specifies a different
+# stack size, so it cannot be ICFd with xdata1.
+  .def   xdata1b;
+  .scl  2;
+  .type 32;
+  .endef
+  .section  .text,"xr",one_only,xdata1b
+  .globl  xdata1b                  # -- Begin function xdata1b
+  .p2align  4, 0x90
+xdata1b:                                 # @xdata1b
+.seh_proc xdata1b
+# BB#0:                                 # %entry
+  subq  $40, %rsp
+  .seh_stackalloc 48
+  .seh_endprologue
+  callq callee
+  nop
+  addq  $40, %rsp
+  jmp callee                  # TAILCALL
+  .seh_handlerdata
+  .section  .text,"xr",one_only,xdata1b
+  .seh_endproc
+                                        # -- End function
+
+  .section  .drectve,"yn"
+  .ascii  " -export:xdata1"
+  .ascii  " -export:xdata1a"
+  .ascii  " -export:xdata1b"