[ELF] - ICF: improve support of SHF_LINK_ORDER sections.

[grimar]

Summary

Previously when ICF merged 2 code sections it did not take
SHF_LINK_ORDER dependencies in account at all.
So if one of order sections was absent or different from another one,
ICF still performed code folding for code sections, what was not correct.
Patch improves the support, teaching ICF to compare static contents of
SHF_LINK_ORDER sections.

[ruiu]

ELF/InputSection.cpp

244

You are assuming that there's up to one dependent section, but are you sure that the assumption is correct? I don't think that's guaranteed by the standard.

[grimar]

ELF/InputSection.cpp

244

It should not be too hard to change I believe.
At the same time spec says "A typical use of this flag is to build a table that references text or data sections in address order.", it seems to me one dependency should be sufficient here, though not explicitly said. I suggest to replace the assert (in this method) checking we have only one dependent link order section with an error for now and watch.
What do you think ?

[ruiu]

ELF/InputSection.cpp

244

At least you need to be consistent with your own choice. Support multiple sections or report an error.

[grimar]

• Added error for case when multiple SHF_LINK_ORDER sections with the same target.
• Added testcase for checking above.

[ruiu]

ELF/ICF.cpp

279

You shouldn't make this change -- you can check it on the caller side.

434–435

This is pretty odd piece of code. You do not call replace on LinkOrder section, but you are reporting that you have removed it. It looks buggy even if it is not buggy.

ELF/InputSection.cpp

244

Why don't you just add a LinkOrderSection * member to InputSection?

[grimar]

• Addressed review comments.

[grimar]

ELF/ICF.cpp

279

OK.

434–435

Fixed.

ELF/InputSection.cpp

244

If D38170 be landed, we will have InputSection *LinkOrderSection; in InputSectionBase, but that is different pointer.
For SHF_LINK_ORDER sections it will contain section linked to via sh_link flag. So for section X it returns section L.
This metod returns SHF_LINK_ORDER section. It is reverse, for L it returns X.

Doesn't seem we should add one more member for that, because we already have X in DependentSections member for L.
And DependentSections should be little vector normally I think, traversing is cheap.

[grimar]

Ping.

[grimar]

Do we want to go in this direction or should I abandon this for now ?

[ruiu]

If you have time to work on improving this, do you mind if I ask you to work on emitting per-function .eh_frame sections from clang?

[grimar]

In D38180#927065, @ruiu wrote:

If you have time to work on improving this, do you mind if I ask you to work on emitting per-function .eh_frame sections from clang?

Yes, I think at least I can try. Unfortunately I am not familar with clang code at all, so it probably will take some time before any first results,
I'll try to investigate how to implement this.

ELF/ICF.cpp

bool ICF<ELFT>::constantEq(const InputSection *SecA, ArrayRef<RelTy> RA,
   return true;
 }
 
 // Compare "non-moving" part of two InputSections, namely everything
 // except relocation targets.
 template <class ELFT>
 bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
   if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
       A->getSize() != B->getSize() || A->Data != B->Data)
     return false;
 
+  const InputSection *LinkSecA = A->getLinkOrderSec();
+  const InputSection *LinkSecB = B->getLinkOrderSec();
+  if (LinkSecA || LinkSecB)
+    if (!LinkSecA || !LinkSecB || !equalsConstant(LinkSecA, LinkSecB))
+      return false;
+
   if (A->AreRelocsRela)
     return constantEq(A, A->template relas<ELFT>(), B,
                       B->template relas<ELFT>());
   return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
 }
 
 // Compare two lists of relocations. Returns true if all pairs of
 // relocations point to the same section in terms of ICF.
template <class ELFT> void ICF<ELFT>::run() {
   log("ICF needed " + Twine(Cnt) + " iterations");
 
   // Merge sections by the equivalence class.
   forEachClass([&](size_t Begin, size_t End) {
     if (End - Begin == 1)
       return;
 
     log("selected " + Sections[Begin]->Name);
-    for (size_t I = Begin + 1; I < End; ++I) {
-      log("  removed " + Sections[I]->Name);
+    for (size_t I = Begin + 1; I < End; ++I)
       Sections[Begin]->replace(Sections[I]);
-    }
   });
-
-  // Mark ARM Exception Index table 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;
 }
 
 // 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>();

ELF/InputSection.h

public:
 
   template <class ELFT> ObjFile<ELFT> *getFile() const;
 
   template <class ELFT> llvm::object::ELFFile<ELFT> getObj() const {
     return getFile<ELFT>()->getObj();
   }
 
   InputSection *getLinkOrderDep() const;
+  InputSection *getLinkOrderSec() const;
 
   void uncompress();
 
   // Returns a source location string. Used to construct an error message.
   template <class ELFT> std::string getLocation(uint64_t Offset);
   template <class ELFT> std::string getSrcMsg(uint64_t Offset);
   template <class ELFT> std::string getObjMsg(uint64_t Offset);
 

ELF/InputSection.cpp

if (auto *IS = dyn_cast<InputSection>(L))
       return IS;
     error("a section with SHF_LINK_ORDER should not refer a non-regular "
           "section: " +
           toString(L));
   }
   return nullptr;
 }
 
+InputSection *InputSectionBase::getLinkOrderSec() const {
+  InputSection *Ret = nullptr;
+  for (InputSectionBase *Sec : DependentSections) {
+    if (!(Sec->Flags & SHF_LINK_ORDER))
+      continue;
+    if (Ret)
+      error("multiple SHF_LINK_ORDER sections are not supported: " +
+            toString(this));
+    Ret = cast<InputSection>(Sec);
+  }
+  return Ret;
+}
+
 // Returns a source location string. Used to construct an error message.
 template <class ELFT>
 std::string InputSectionBase::getLocation(uint64_t Offset) {
   // We don't have file for synthetic sections.
   if (getFile<ELFT>() == nullptr)
     return (Config->OutputFile + ":(" + Name + "+0x" + utohexstr(Offset) + ")")
         .str();
 
template <class ELFT> void InputSection::writeTo(uint8_t *Buf) {
   // Copy section contents from source object file to output file
   // and then apply relocations.
   memcpy(Buf + OutSecOff, Data.data(), Data.size());
   uint8_t *BufEnd = Buf + OutSecOff + Data.size();
   this->relocate<ELFT>(Buf, BufEnd);
 }
 
 void InputSection::replace(InputSection *Other) {
+  log("  removed " + Other->Name);
   this->Alignment = std::max(this->Alignment, Other->Alignment);
   Other->Repl = this->Repl;
   Other->Live = false;
+
+  // Handle SHF_LINK_ORDER sections. These sections have an
+  // implicit dependency via the link order dependency.
+  if (InputSection *LinkOrder = getLinkOrderSec())
+    LinkOrder->replace(Other->getLinkOrderSec());
 }
 
 template <class ELFT>
 EhInputSection::EhInputSection(ObjFile<ELFT> *F,
                                const typename ELFT::Shdr *Header,
                                StringRef Name)
     : InputSectionBase(F, Header, Name, InputSectionBase::EHFrame) {
   // Mark .eh_frame sections as live by default because there are

test/ELF/icf-link-order-err.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: not ld.lld %t.o -o %t2 --icf=all 2>&1 | FileCheck %s
+# CHECK: multiple SHF_LINK_ORDER sections are not supported: {{.*}}.o:(.text.bar)
+
+.section .text.foo, "ax"
+nop
+
+.section .text.bar, "ax"
+nop
+
+.section .order_foo,"ao",@progbits,.text.foo
+.quad 0
+
+.section .order_bar1,"ao",@progbits,.text.bar
+.quad 0
+
+.section .order_bar2,"ao",@progbits,.text.bar
+.quad 0

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-NEXT:   removed .text.bar
+# CHECK-NEXT:   removed .order_bar
+# CHECK-NOT: selected
+# CHECK-NOT: removed
+
+.section .text.foo, "ax"
+nop
+
+.section .text.bar, "ax"
+nop
+
+.section .text.dah, "ax"
+nop
+
+.section .text.zed, "ax"
+nop
+
+.section .order_foo,"ao",@progbits,.text.foo
+.quad 0
+
+.section .order_bar,"ao",@progbits,.text.bar
+.quad 0
+
+.section .order_dah,"ao",@progbits,.text.dah
+.quad 1