[ELF] - ICF: handle SHF_LINK_ORDER sections properly.

[grimar]

Summary

ICF code currently handles SHF_LINK_ORDER section only for ARM.
Though it is possible (and testcase shows that) to use them in
other targets.

Testcase provided would crash before such change. Patch
adds verbose reporting when removing of SHF_LINK_ORDER sections
and also makes logic to work for all targets instead of only ARM.

[ruiu]

Why do you want to do this? Why don't you just remove EM_ARM?

[grimar]

In D37739#868992, @ruiu wrote:

Why do you want to do this? Why don't you just remove EM_ARM?

Reporting sections removed by ICF is consistent, I supposed we want it.
I also using --verbose reporting in my testcase (most of ICF tests use --verbose messages for checking,
so it is also a consistent way, though I sure can write regular testcase).
Do you think we should not do that, but why not ?

[ruiu]

This seems to be another instance of attempting to "fix" an issue at surface-level where deeper planning is needed.

Current ICF doesn't actually work for SHF_LINK_ORDER, no? Assume you have three sections A, B and C, where C depends on A but B doesn't have any dependent section. Do you think A and B can be merged? No, because A and B are not really identical. The problem is that ICF doesn't take section dependencies into account. I don't want you to update this patch immediately, but can you please think about that to come up with a plan how you would deal with it and explain it to me?

[grimar]

In D37739#872899, @ruiu wrote:

This seems to be another instance of attempting to "fix" an issue at surface-level where deeper planning is needed.

Current ICF doesn't actually work for SHF_LINK_ORDER, no? Assume you have three sections A, B and C, where C depends on A but B doesn't have any dependent section. Do you think A and B can be merged? No, because A and B are not really identical. The problem is that ICF doesn't take section dependencies into account. I don't want you to update this patch immediately, but can you please think about that to come up with a plan how you would deal with it and explain it to me?

I think probably the most correct way to handle this is to merge A and B only if their dependent sections are equal.
So if we have equal sections A and B and SHF_LINK_ORDER sections C and D where C depends on A and D depends on B,
we can merge A and B and just drop C or D, so that one leaved alive will still depend on A/B.

We should be able to check if dependent sections are equal using existent infrastructure I think (that will require scanning
relocations for them and doing other things which ICF code already do).

[grimar]

Abandoned in favor of D38180.

ELF/ICF.cpp

forEachClass([&](size_t Begin, size_t End) {
 
     log("selected " + Sections[Begin]->Name);
     for (size_t I = Begin + 1; I < End; ++I) {
       log("  removed " + Sections[I]->Name);
       Sections[Begin]->replace(Sections[I]);
     }
   });
 
-  // Mark ARM Exception Index table sections that refer to folded code
+  // Mark SHF_LINK_ORDER sections that refer to folded code
   // sections as not live. These sections have an implict dependency
   // via the link order dependency.
-  if (Config->EMachine == EM_ARM)
-    for (InputSectionBase *Sec : InputSections)
-      if (auto *S = dyn_cast<InputSection>(Sec))
-        if (S->Flags & SHF_LINK_ORDER)
-          S->Live = S->getLinkOrderDep()->Live;
+  for (InputSectionBase *Sec : InputSections) {
+    auto *S = dyn_cast<InputSection>(Sec);
+    if (!S || !S->Live)
+      continue;
+    InputSection *Dep = S->getLinkOrderDep();
+    if (Dep && !Dep->Live) {
+      log("  removed " + S->Name);
+      S->Live = false;
+    }
+  }
 }
 
 // ICF entry point function.
 template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
 
 template void elf::doIcf<ELF32LE>();
 template void elf::doIcf<ELF32BE>();
 template void elf::doIcf<ELF64LE>();
 template void elf::doIcf<ELF64BE>();

test/ELF/icf-link-order.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %t2 --icf=all --verbose | FileCheck %s
+# CHECK: selected .text.foo
+# CHECK:   removed .text.bar
+# CHECK:   removed .order_bar
+
+.section .text.foo, "ax"
+nop
+
+.section .text.bar, "ax"
+nop
+
+.section .order_foo,"ao",@progbits,.text.foo
+
+.section .order_bar,"ao",@progbits,.text.bar