ELF: Allow forward references to linked sections.

[pcc]

Summary

It's possible to create IR that uses !associated to refer to a global that
appears later in the module, which can result in these types of forward
references being generated. Unfortunately our assembler does not currently
accept the resulting .s so I needed to use yaml2obj to test this.

[MaskRay]

The latest semantics of SHF_LINK_ORDER agreed by several parties on generic-abi has the following wording:

SHF_LINK_ORDER 

This flag adds special ordering requirements for link editors. The 
requirements apply to the referenced section identified by the sh_link 
field of this section's header.  If this section is combined with other 
sections in the output file, the section must appear in the same 
relative order with respect to those sections, as the referenced 
section appears with respect to sections the referenced section is 
combined with. 

A typical use of this flag is to build a table that references 
text or data sections in address order. 

In addition to adding ordering requirements, SHF_LINK_ORDER indicates 
that the section contains metadata describing the referenced section. 
When performing unused section elimination, the link editor should 
ensure that both the section and the referenced section are retained 
or discarded together. Furthermore, relocations from this section 
into the referenced section should not be taken as evidence that the 
referenced section should be retained.

Allowing forward references is natural and does not conflict with the wording. LGTM.

lld/ELF/InputFiles.cpp

657 ↗

(On Diff #210396)

This can be changed to a range-based for.

lld/test/ELF/linkorder-forward-ref.test

5 ↗

(On Diff #210396)

This test needs a comment explaining what it intends to test.

[pcc]

• Add comment

lld/ELF/InputFiles.cpp

657 ↗

(On Diff #210396)

We're iterating over two arrays here (this->sections and objSections) which makes it simpler to use a regular for loop.

[grimar]

LGTM. A few "up to you" suggestions are below

lld/ELF/InputFiles.cpp

657 ↗

(On Diff #210477)

nit: we usually use ++i form I think.

lld/test/ELF/linkorder-forward-ref.test

6 ↗

(On Diff #210477)

nit: for LLVM tools it became common to start comments from ##.
Many tests in LLD also do that (it is actually where this style initially start spreading).
I'd suggest using it.

20 ↗

(On Diff #210477)

nit: seems you do not need SHF_ALLOC, SHF_EXECINSTR flags here?

[peter.smith]

lld/ELF/InputFiles.cpp

656 ↗

(On Diff #210477)

A possible optimization would be to remember the index of the first SHF_LINK_ORDER section in the previous loop. Then start the second iteration from there. If there were no SHF_LINK_ORDER sections which I would expect to be rare outside of Arm then we would skip the second loop entirely. I wouldn't expect this to be significant though so it may be better to keep it simple.

[ruiu]

LGTM

lld/ELF/InputFiles.cpp

656 ↗

(On Diff #210477)

I thought that too, but since the section table is an efficient data structure (a vector) and its size is not very large, so I don't think we'll see a difference by caching something in the first loop.

664 ↗

(On Diff #210477)

Flip the condition to continue early.

lld/trunk/ELF/InputFiles.cpp

void ObjFile<ELFT>::initializeSections(bool ignoreComdats) {
   const ELFFile<ELFT> &obj = this->getObj();
 
   ArrayRef<Elf_Shdr> objSections = CHECK(obj.sections(), this);
   uint64_t size = objSections.size();
   this->sections.resize(size);
   this->sectionStringTable =
       CHECK(obj.getSectionStringTable(objSections), this);
 
-  for (size_t i = 0, e = objSections.size(); i < e; i++) {
+  for (size_t i = 0, e = objSections.size(); i < e; ++i) {
     if (this->sections[i] == &InputSection::discarded)
       continue;
     const Elf_Shdr &sec = objSections[i];
 
     if (sec.sh_type == ELF::SHT_LLVM_CALL_GRAPH_PROFILE)
       cgProfile =
           check(obj.template getSectionContentsAsArray<Elf_CGProfile>(&sec));
 
case SHT_SYMTAB_SHNDX:
       break;
     case SHT_SYMTAB:
     case SHT_STRTAB:
     case SHT_NULL:
       break;
     default:
       this->sections[i] = createInputSection(sec);
     }
+  }
+
+  for (size_t i = 0, e = objSections.size(); i < e; ++i) {
+    if (this->sections[i] == &InputSection::discarded)
+      continue;
+    const Elf_Shdr &sec = objSections[i];
+    if (!(sec.sh_flags & SHF_LINK_ORDER))
+      continue;
 
     // .ARM.exidx sections have a reverse dependency on the InputSection they
     // have a SHF_LINK_ORDER dependency, this is identified by the sh_link.
-    if (sec.sh_flags & SHF_LINK_ORDER) {
-      InputSectionBase *linkSec = nullptr;
-      if (sec.sh_link < this->sections.size())
-        linkSec = this->sections[sec.sh_link];
-      if (!linkSec)
-        fatal(toString(this) +
-              ": invalid sh_link index: " + Twine(sec.sh_link));
+      fatal(toString(this) + ": invalid sh_link index: " + Twine(sec.sh_link));
 
-      InputSection *isec = cast<InputSection>(this->sections[i]);
-      linkSec->dependentSections.push_back(isec);
-      if (!isa<InputSection>(linkSec))
-        error("a section " + isec->name +
-              " with SHF_LINK_ORDER should not refer a non-regular "
-              "section: " +
-              toString(linkSec));
-    }
-  }
-}
+            " with SHF_LINK_ORDER should not refer a non-regular section: " +
 
 // For ARM only, to set the EF_ARM_ABI_FLOAT_SOFT or EF_ARM_ABI_FLOAT_HARD
 // flag in the ELF Header we need to look at Tag_ABI_VFP_args to find out how
 // the input objects have been compiled.
 static void updateARMVFPArgs(const ARMAttributeParser &attributes,
                              const InputFile *f) {
   if (!attributes.hasAttribute(ARMBuildAttrs::ABI_VFP_args))
     // If an ABI tag isn't present then it is implicitly given the value of 0

lld/trunk/test/ELF/linkorder-forward-ref.test

+# REQUIRES: x86
+# RUN: yaml2obj %s -o %t.o
+# RUN: ld.lld %t.o -o %t
+# RUN: llvm-readelf -S %t | FileCheck %s
+
+## Test that we accept forward sh_link references.
+
+# CHECK: .linkorder
+# CHECK: .text
+
+--- !ELF
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_REL
+  Machine:         EM_X86_64
+Sections:
+  - Name:          .linkorder
+    Type:          SHT_PROGBITS
+    Flags:         [ SHF_LINK_ORDER ]
+    Link:          2
+  - Name:          .text
+    Type:          SHT_PROGBITS