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

This can be changed to a range-based for.

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

6

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

[pcc]

• Add comment

lld/ELF/InputFiles.cpp

657

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

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

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

6

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

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

[peter.smith]

lld/ELF/InputFiles.cpp

656

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

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

Flip the condition to continue early.

lld/ELF/InputFiles.cpp

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];
 
     // .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));
 
       InputSection *isec = cast<InputSection>(this->sections[i]);

lld/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_ALLOC, SHF_EXECINSTR, SHF_LINK_ORDER ]
+    Link:          2
+  - Name:          .text
+    Type:          SHT_PROGBITS
+    Flags:         [ SHF_ALLOC, SHF_EXECINSTR ]