[ELF] - Support INSERT AFTER statement in linker script.

[grimar]

Summary

This is for PR35877.

Seems simple and isolated implementation. It remembers all sections
that are part of "INSERT AFTER" statement and makes them
to be placed like orphans. That allows orphan placing code to find
and place such sections after regular common and regular orphans.

It looks to be consistent with spec which says:
(https://sourceware.org/binutils/docs/ld/Miscellaneous-Commands.html)
"It inserts all prior linker script statements after (or before) output_section, and also
causes ‘-T’ to not override the default linker script. The exact insertion point is as for
orphan sections.".

"INSERT AFTER" sections can't refer to each other in this implementation.
(it will not place them correctly). Though that does not look what was needed in original
PR request, so should be fine probably.

[ruiu]

Hmm, isn't this too restricted? It may work for .text or .data because sections are sorted by section attributes, but it doesn't work for other cases, no?

[grimar]

In D42482#992724, @ruiu wrote:

Hmm, isn't this too restricted? It may work for .text or .data because sections are sorted by section attributes, but it doesn't work for other cases, no?

Yes, exactly. Tried to find balance between simplicity and functionality here. Original PR case was saying that such mini-scripts with "INSERT AFTER xxx"
are used in addition to default bfd script to place some sections and symbols.

If we have .text (ax) and .data (aw) and some .foo (aw) and trying to insert .foo after .text (INSERT AFTER .text).
Then .foo will be inserted after .data in our case. Though that still does not violate spec which says:
"The exact insertion point is as for orphan sections" and technically we still would insert after .text.

By "other cases", do you have some specific useful case in mind where this patch would not work ? I just wonder how much simple approach
can/should be and if we really need anything more complex than that.

[grimar]

As was reported on PR page it does not work good there. Going to try reimplement in a different way.

ELF/LinkerScript.h

 #include "Config.h"
 #include "Strings.h"
 #include "Writer.h"
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <cstddef>
 #include <cstdint>
 #include <functional>
 #include <memory>
 #include <vector>
 
public:
   // be kept even if they are unused and --gc-sections is specified.
   std::vector<InputSectionDescription *> KeptSections;
 
   // A map from memory region name to a memory region descriptor.
   llvm::MapVector<llvm::StringRef, MemoryRegion *> MemoryRegions;
 
   // A list of symbols referenced by the script.
   std::vector<llvm::StringRef> ReferencedSymbols;
+
+  // Used to implement INSERT AFTER sequence.
+  llvm::SetVector<OutputSection*> InsertAfter;
 };
 
 extern LinkerScript *Script;
 
 } // end namespace elf
 } // end namespace lld
 
 #endif // LLD_ELF_LINKER_SCRIPT_H

ELF/ScriptParser.cpp

while (!errorCount() && !consume("}")) {
     if (!Cmd) {
       if (Tok == "ASSERT")
         Cmd = readAssert();
       else
         Cmd = readOutputSectionDescription(Tok);
     }
     Script->SectionCommands.push_back(Cmd);
   }
+
+  if (!atEOF() && consume("INSERT")) {
+    expect("AFTER");
+    skip();
+    for (BaseCommand *Base : Script->SectionCommands)
+      if (auto *Sec = dyn_cast<OutputSection>(Base))
+        Script->InsertAfter.insert(Sec);
+  }
 }
 
 static int precedence(StringRef Op) {
   return StringSwitch<int>(Op)
       .Cases("*", "/", 5)
       .Cases("+", "-", 4)
       .Cases("<<", ">>", 3)
       .Cases("<", "<=", ">", ">=", "==", "!=", 2)

ELF/Writer.cpp

if (!Script->HasSectionsCommand) {
     I = std::find_if(I, E, IsSection);
     E = std::find_if(llvm::make_reverse_iterator(E),
                      llvm::make_reverse_iterator(I), IsSection)
             .base();
     std::stable_sort(I, E, compareSections);
     return;
   }
 
+  // This is used to implement INSERT AFTER .section sequence.
+  // In this case we let our orphans placement algorithm to find
+  // and place sections from sequence. We move them to the end so
+  // them are placed after all other sections.
+  if (!Script->InsertAfter.empty()) {
+    std::stable_partition(Script->SectionCommands.begin(),
+                          Script->SectionCommands.end(), [](BaseCommand *Base) {
+                            if (auto *Sec = dyn_cast<OutputSection>(Base))
+                              return !Script->InsertAfter.count(Sec);
+                            return true;
+                          });
+    // Orphan sections assumed to have no valid section index below.
+    for (OutputSection *Sec : Script->InsertAfter)
+      Sec->SectionIndex = INT_MAX;
+  }
+
   // Orphan sections are sections present in the input files which are
   // not explicitly placed into the output file by the linker script.
   //
   // The sections in the linker script are already in the correct
   // order. We have to figuere out where to insert the orphan
   // sections.
   //
   // The order of the sections in the script is arbitrary and may not agree with

test/ELF/linkerscript/insert-after.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+# RUN: echo "SECTIONS {                                         \
+# RUN:   .bar1 : { __start_bar1 = .; *(.foo1) __end_bar1 = .; } \
+# RUN:  } INSERT AFTER .data;                                   \
+# RUN:  SECTIONS {                                              \
+# RUN:   .bar2 : { __start_bar2 = .; *(.foo2) __end_bar2 = .; } \
+# RUN:  } INSERT AFTER .text;" > %t.script
+
+# RUN: ld.lld %t1.o -o %t1 --script %t.script
+# RUN: llvm-objdump -section-headers %t1 | FileCheck %s
+
+# CHECK:      Sections:
+# CHECK-NEXT: Idx Name          Size      Address          Type
+# CHECK-NEXT:   0               00000000 0000000000000000
+# CHECK-NEXT:   1 .text         00000001 0000000000000000 TEXT DATA
+# CHECK-NEXT:   2 .bar2         00000008 0000000000000001 TEXT DATA
+# CHECK-NEXT:   3 .data         00000008 0000000000000009 DATA
+# CHECK-NEXT:   4 .bar1         00000008 0000000000000011 DATA
+# CHECK-NEXT:   5 .comment      00000008 0000000000000000
+# CHECK-NEXT:   6 .symtab       00000090 0000000000000000
+# CHECK-NEXT:   7 .shstrtab     0000003c 0000000000000000
+# CHECK-NEXT:   8 .strtab       00000038 0000000000000000
+
+.global _start
+_start:
+ nop
+
+.section .data,"aw"
+.quad 0
+
+.section .foo1,"aw"
+.quad 1
+
+.section .foo2,"ax"
+.quad 1