[LLD][ELF] Make createThunks() use InputSectionDescriptions

[peter.smith]

Summary

Some Thunks such as Mips LA25 Thunks need to be added at a specific address, when the OutputSection is covered by a SECTIONS command the script assigns the addresses using the InputSectionDescription. This will take precedence over the OutputSections::Sections. By inserting into InputSectionDescription the Script->assignAddresses() will correctly take into account of the placement of inserted thunks.

This change is a step towards range extension Thunks. We will need to iteratively add Thunks, recalculate addresses, add more Thunks until no more Thunks are added. All the address calculation is now driven by Script->assignAddresses() which works from InputSectionDescriptions::Sections so at the end of each iteration we'll need to have the Thunks inserted into InputSectionDescriptions::Sections.

The translation from using OutputSection::Sections() to InputSectionDescriptions() is fairly mechanical, instead of tracking the Thunks inserted per OutputSection we track the Thunks inserted per InputSectionDescription::Sections.

There is some extra complication in mergeThunks() as it is not sufficient to just add the ThunkSections to the end of OutputSection::Sections. The call to Script->synchronize() before the final address allocation will prefer the order of OutputSection::Sections over InputSectionDescriptions::Sections. To solve this we copy the InputSectionDescriptions with Thunks inserted back into OutputSections. This will only need to be done once after createThunks() has finished.

There are some design alternatives that could avoid the synchronization to OutputSections::Sections
1.) Don't convert createThunks() to use InputSectionDescriptions, instead we will call Script->synchronize() after we have added the Thunks. This was how the original range thunk submission D31656 worked. If the intention is to move away from OutputSection::Sections then this is not the right option.
2.) Only call Script->synchronize() on the OutputSections that need synchronizing, this shouldn't involve any OutputSections that contain Thunks. This could work although it could be fragile.
3.) Move the call to createThunks() after the call to Sec->finalize<ELFT>(), and move Script->synchronize() before createThunks(). I'm not keen on doing this as it implies that Sec->finalize<ELFT>() is not final.
4.) Instead of calling Script->finalize(), reorder the SHF_LINK_ORDER sections using InputSectionDescription so that Script->finalize() is not necessary. See D32233

[peter.smith]

Updating diff to account for the detemplating of ThunkCreator and the proposed change in D33239 to move SHF_LINK_ORDER processing earlier in the link.
The key differences are:

• When taken together with the proposed change in D33239 synchronize() is no longer needed
• I've separated allocateHeaders() which only needs to, and I think can only, run once from assignAddresses() which needs to run many times for Thunks

[peter.smith]

This is no longer required it was implemented in D33835

ELF/LinkerScript.h

 
   std::vector<OutputSection *> *OutputSections;
   void fabricateDefaultCommands();
+  std::vector<std::vector<InputSectionBase *> *>
+  inputSectionRanges(StringRef S);
   void addOrphanSections(OutputSectionFactory &Factory);
   void removeEmptyCommands();
   void adjustSectionsBeforeSorting();

   void placeOrphanSections();
   void processNonSectionCommands();
   void sortLinkOrder();
-  void synchronize();
   void resetAddressState();
   void assignAddresses();
   void allocateHeaders(std::vector<PhdrEntry> &Phdrs);

ELF/LinkerScript.cpp

   Opt.Commands = std::move(Commands);
 }
 
+// For an OutputSection S, return the InputSectionDescriptions that are
+// associated with S. The intention is that callers can iterate over
+// InputSectionDescription::Sections and insert sections such as Thunks.
+std::vector<std::vector<InputSectionBase *> *>
+LinkerScript::inputSectionRanges(StringRef S) {
+  std::vector<std::vector<InputSectionBase *> *> Ranges;
+  auto OutCmdPos = std::find_if(
+      Opt.Commands.begin(), Opt.Commands.end(), [=](BaseCommand *Cmd) {
+        if (auto *OSCmd = dyn_cast<OutputSectionCommand>(Cmd))
+          return (OSCmd->Name == S);
+        return false;
+      });
+  if (OutCmdPos == Opt.Commands.end())
+    return Ranges;
+  auto *OutCmd = cast<OutputSectionCommand>(*OutCmdPos);
+  for (auto *BaseCmd : OutCmd->Commands) {
+    if (auto *ISD = dyn_cast<InputSectionDescription>(BaseCmd))
+      Ranges.push_back(&ISD->Sections);
+  }
+  return Ranges;
+}
+
 // Add sections that didn't match any sections command.
 void LinkerScript::addOrphanSections(OutputSectionFactory &Factory) {
   for (InputSectionBase *S : InputSections) {

       *ScriptSections[I] = Sections[I];
   }
 }
-// Do a last effort at synchronizing the linker script "AST" and the section
-// list. This is needed to account for last minute changes, like adding thunks
-//
-// FIXME: We should instead create the "AST" earlier and the above changes would
-// be done directly in the "AST".
-//
-// This can only handle new sections being added and sections being reordered.
-void LinkerScript::synchronize() {
-  for (BaseCommand *Base : Opt.Commands) {
-    auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
-    if (!Cmd || (Cmd->Sec->Flags & SHF_LINK_ORDER))
-      continue;
-    ArrayRef<InputSection *> Sections = Cmd->Sec->Sections;
-    std::vector<InputSectionBase **> ScriptSections;
-    DenseSet<InputSectionBase *> ScriptSectionsSet;
-    for (BaseCommand *Base : Cmd->Commands) {
-      auto *ISD = dyn_cast<InputSectionDescription>(Base);
-      if (!ISD)
-        continue;
-      for (InputSectionBase *&IS : ISD->Sections) {
-        if (IS->Live) {
-          ScriptSections.push_back(&IS);
-          ScriptSectionsSet.insert(IS);
-        }
-      }
-    }
-    std::vector<InputSectionBase *> Missing;
-    for (InputSection *IS : Sections)
-      if (!ScriptSectionsSet.count(IS))
-        Missing.push_back(IS);
-    if (!Missing.empty()) {
-      auto ISD = make<InputSectionDescription>("");
-      ISD->Sections = Missing;
-      Cmd->Commands.push_back(ISD);
-      for (InputSectionBase *&IS : ISD->Sections)
-        if (IS->Live)
-          ScriptSections.push_back(&IS);
-    }
-    assert(ScriptSections.size() == Sections.size());
-    for (int I = 0, N = Sections.size(); I < N; ++I)
-      *ScriptSections[I] = Sections[I];
-  }
-}
 
 static bool allocateHeadersImpl(std::vector<PhdrEntry> &Phdrs,
                                 ArrayRef<OutputSection *> OutputSections,
                                 uint64_t Min) {
   auto FirstPTLoad =
       std::find_if(Phdrs.begin(), Phdrs.end(),
                    [](const PhdrEntry &E) { return E.p_type == PT_LOAD; });

ELF/Relocations.h

   // Return true if Thunks have been added to OutputSections
   bool createThunks(ArrayRef<OutputSection *> OutputSections);
 
+  using ISRange = std::vector<InputSectionBase *>;
+
 private:
-  void mergeThunks(OutputSection *OS, std::vector<ThunkSection *> &Thunks);
-  ThunkSection *getOSThunkSec(ThunkSection *&TS, OutputSection *OS);
+  void mergeThunks();
+  ThunkSection *getOSThunkSec(ThunkSection *&TS, OutputSection *OS,
+                              ISRange *ISR);
   ThunkSection *getISThunkSec(InputSection *IS, OutputSection *OS);
   std::pair<Thunk *, bool> getThunk(SymbolBody &Body, uint32_t Type);
 

   // Track InputSections that have a ThunkSection placed in front
   llvm::DenseMap<InputSection *, ThunkSection *> ThunkedSections;
 
-  // Track the ThunksSections that need to be inserted into an OutputSection
-  std::map<OutputSection *, std::vector<ThunkSection *>> ThunkSections;
+  // Track the ThunksSections that need to be inserted into an InputSectionRange
+  std::map<ISRange *, std::vector<ThunkSection *>> ThunkSections;
 };
 
 // Return a int64_t to make sure we get the sign extension out of the way as

ELF/Relocations.cpp

 
 #include "Relocations.h"
 #include "Config.h"
+#include "LinkerScript.h"
 #include "Memory.h"
 #include "OutputSections.h"
 #include "Strings.h"

     scanRelocs<ELFT>(S, S.rels<ELFT>());
 }
 
-// Insert the Thunks for OutputSection OS into their designated place
-// in the Sections vector, and recalculate the InputSection output section
-// offsets.
-// This may invalidate any output section offsets stored outside of InputSection
-void ThunkCreator::mergeThunks(OutputSection *OS,
-                               std::vector<ThunkSection *> &Thunks) {
-  // Order Thunks in ascending OutSecOff
-  auto ThunkCmp = [](const ThunkSection *A, const ThunkSection *B) {
-    return A->OutSecOff < B->OutSecOff;
-  };
-  std::stable_sort(Thunks.begin(), Thunks.end(), ThunkCmp);
-
-  // Merge sorted vectors of Thunks and InputSections by OutSecOff
-  std::vector<InputSection *> Tmp;
-  Tmp.reserve(OS->Sections.size() + Thunks.size());
-  auto MergeCmp = [](const InputSection *A, const InputSection *B) {
-    // std::merge requires a strict weak ordering.
-    if (A->OutSecOff < B->OutSecOff)
-      return true;
-    if (A->OutSecOff == B->OutSecOff)
-      // Check if Thunk is immediately before any specific Target InputSection
-      // for example Mips LA25 Thunks.
-      if (auto *TA = dyn_cast<ThunkSection>(A))
-        if (TA && TA->getTargetInputSection() == B)
-          return true;
-    return false;
-  };
-  std::merge(OS->Sections.begin(), OS->Sections.end(), Thunks.begin(),
-             Thunks.end(), std::back_inserter(Tmp), MergeCmp);
-  OS->Sections = std::move(Tmp);
-  OS->assignOffsets();
+// Insert the Thunks into their designated place in both
+// InputSectionDescriptions and the OutputSection::Sections.
+void ThunkCreator::mergeThunks() {
+  // Step 1 merge all Thunks into the InputSectionDescriptions
+  for (auto &KV : ThunkSections) {
+    ISRange *ISR = KV.first;
+    std::vector<ThunkSection *> &Thunks = KV.second;
+    // Order Thunks in ascending OutSecOff
+    auto ThunkCmp = [](const ThunkSection *A, const ThunkSection *B) {
+      return A->OutSecOff < B->OutSecOff;
+    };
+    std::stable_sort(Thunks.begin(), Thunks.end(), ThunkCmp);
+
+    // Merge sorted vectors of Thunks and InputSections by OutSecOff
+    std::vector<InputSectionBase *> Tmp;
+    Tmp.reserve(ISR->size() + Thunks.size());
+    auto MergeCmp = [](const InputSectionBase *A, const InputSectionBase *B) {
+      // std::merge requires a strict weak ordering.
+      auto *ISA = cast<InputSection>(A);
+      auto *ISB = cast<InputSection>(B);
+      if (ISA->OutSecOff < ISB->OutSecOff)
+        return true;
+      if (ISA->OutSecOff == ISB->OutSecOff)
+        // Check if Thunk is immediately before any specific Target InputSection
+        // for example Mips LA25 Thunks.
+        if (auto *TA = dyn_cast<ThunkSection>(ISA))
+          if (TA && TA->getTargetInputSection() == ISB)
+            return true;
+      return false;
+    };
+    std::merge(ISR->begin(), ISR->end(), Thunks.begin(), Thunks.end(),
+               std::back_inserter(Tmp), MergeCmp);
+    *ISR = std::move(Tmp);
+    OutputSection *ModifiedOS = cast<InputSection>(ISR->front())->OutSec;
+    for (InputSection *TS : Thunks)
+      ModifiedOS->Sections.push_back(TS);
+  }
 }
 
 ThunkSection *ThunkCreator::getOSThunkSec(ThunkSection *&TS,
-                                          OutputSection *OS) {
+                                          OutputSection *OS,
+                                          ISRange *ISR) {
   if (TS == nullptr) {
     uint32_t Off = 0;
     for (auto *IS : OS->Sections) {

         break;
     }
     TS = make<ThunkSection>(OS, Off);
-    ThunkSections[OS].push_back(TS);
+    ThunkSections[ISR].push_back(TS);
   }
   return TS;
 }

     return TS;
   auto *TOS = cast<OutputSection>(IS->OutSec);
   TS = make<ThunkSection>(TOS, IS->OutSecOff);
-  ThunkSections[TOS].push_back(TS);
+
+  // Find InputSectionRange within TOS that IS is in
+  std::vector<ISRange *> Ranges = Script->inputSectionRanges(TOS->Name);
+  auto ISIter = std::find_if(Ranges.begin(), Ranges.end(), [=](ISRange *R) {
+    InputSection *first = cast<InputSection>(R->front());
+    InputSection *last = cast<InputSection>(R->back());
+    return IS->OutSecOff >= first->OutSecOff &&
+           IS->OutSecOff <= last->OutSecOff;
+  });
+  ThunkSections[*ISIter].push_back(TS);
   ThunkedSections[IS] = TS;
   return TS;
 }

   // ThunkSections back into the OutputSection as ThunkSections are not always
   // inserted into the same OutputSection as the caller.
   for (OutputSection *OS : OutputSections) {
-    ThunkSection *OSTS = nullptr;
-    for (InputSection *IS : OS->Sections) {
-      for (Relocation &Rel : IS->Relocations) {
-        SymbolBody &Body = *Rel.Sym;
-        if (!Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Body))
-          continue;
-        Thunk *T;
-        bool IsNew;
-        std::tie(T, IsNew) = getThunk(Body, Rel.Type);
-        if (IsNew) {
-          // Find or create a ThunkSection for the new Thunk
-          ThunkSection *TS;
-          if (auto *TIS = T->getTargetInputSection())
-            TS = getISThunkSec(TIS, OS);
-          else
-            TS = getOSThunkSec(OSTS, OS);
-          TS->addThunk(T);
+    if (!(OS->Flags & SHF_ALLOC) || !(OS->Flags & SHF_EXECINSTR))
+      continue;
+    std::vector<ISRange *> Ranges = Script->inputSectionRanges(OS->Name);
+    for (ISRange *Range : Ranges) {
+      for (InputSectionBase *ISB : *Range) {
+        ThunkSection *ISRTS = nullptr;
+        auto *IS = cast<InputSection>(ISB);
+        for (Relocation &Rel : IS->Relocations) {
+          SymbolBody &Body = *Rel.Sym;
+          if (!Target->needsThunk(Rel.Expr, Rel.Type, IS->File, Body))
+            continue;
+          Thunk *T;
+          bool IsNew;
+          std::tie(T, IsNew) = getThunk(Body, Rel.Type);
+          if (IsNew) {
+            // Find or create a ThunkSection for the new Thunk
+            ThunkSection *TS;
+            if (auto *TIS = T->getTargetInputSection())
+              TS = getISThunkSec(TIS, OS);
+            else
+              TS = getOSThunkSec(ISRTS, OS, Range);
+            TS->addThunk(T);
+          }
+          // Redirect relocation to Thunk, we never go via the PLT to a Thunk
+          Rel.Sym = T->ThunkSym;
+          Rel.Expr = fromPlt(Rel.Expr);
         }
-        // Redirect relocation to Thunk, we never go via the PLT to a Thunk
-        Rel.Sym = T->ThunkSym;
-        Rel.Expr = fromPlt(Rel.Expr);
       }
     }
   }
 
-  // Merge all created synthetic ThunkSections back into OutputSection
-  for (auto &KV : ThunkSections)
-    mergeThunks(KV.first, KV.second);
+  // Merge all created synthetic ThunkSections back into the OutputSections
+  mergeThunks();
   return !ThunkSections.empty();
 }
 

ELF/Writer.cpp

   if (Config->Relocatable) {
     assignFileOffsets();
   } else {
-    Script->synchronize();
     Script->assignAddresses();
     Script->allocateHeaders(Phdrs);
 

   // Some architectures use small displacements for jump instructions.
   // It is linker's responsibility to create thunks containing long
   // jump instructions if jump targets are too far. Create thunks.
-  if (Target->NeedsThunks) {
+  if (Target->NeedsThunks && !Config->Relocatable) {
     // FIXME: only ARM Interworking and Mips LA25 Thunks are implemented,
     // these
     // do not require address information. To support range extension Thunks
     // we need to assign addresses so that we can tell if jump instructions
     // are out of range. This will need to turn into a loop that converges
     // when no more Thunks are added
+    Script->assignAddresses();
     ThunkCreator TC;
     if (TC.createThunks(OutputSections))
       applySynthetic({InX::MipsGot},

test/ELF/mips-npic-call-pic-script.s

+# REQUIRES: mips
+# Check LA25 stubs creation. This stub code is necessary when
+# non-PIC code calls PIC function.
+# RUN: echo "SECTIONS { .out 0x20000 : { *(.text.*) . = . + 0x100 ;  *(.text) }  }" > %t1.script
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux \
+# RUN:   %p/Inputs/mips-fpic.s -o %t-fpic.o
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux \
+# RUN:   %p/Inputs/mips-fnpic.s -o %t-fnpic.o
+# RUN: ld.lld -r %t-fpic.o %t-fnpic.o -o %t-sto-pic.o
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux \
+# RUN:   %p/Inputs/mips-pic.s -o %t-pic.o
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux %s -o %t-npic.o
+# RUN: ld.lld --script %t1.script %t-npic.o %t-pic.o %t-sto-pic.o -o %t.exe
+# RUN: llvm-objdump -d %t.exe | FileCheck %s
+
+# CHECK: Disassembly of section .out:
+# CHECK-NEXT: __LA25Thunk_foo1a:
+# CHECK-NEXT:    20000:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20004:       08 00 80 08     j       131104 <foo1a>
+# CHECK-NEXT:    20008:       27 39 00 20     addiu   $25, $25, 32
+# CHECK-NEXT:    2000c:       00 00 00 00     nop
+# CHECK: __LA25Thunk_foo1b:
+# CHECK-NEXT:    20010:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20014:       08 00 80 09     j       131108 <foo1b>
+# CHECK-NEXT:    20018:       27 39 00 24     addiu   $25, $25, 36
+# CHECK-NEXT:    2001c:       00 00 00 00     nop
+# CHECK: foo1a:
+# CHECK-NEXT:    20020:       00 00 00 00     nop
+# CHECK: foo1b:
+# CHECK-NEXT:    20024:       00 00 00 00     nop
+# CHECK: __LA25Thunk_foo2:
+# CHECK-NEXT:    20028:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    2002c:       08 00 80 10     j       131136 <foo2>
+# CHECK-NEXT:    20030:       27 39 00 40     addiu   $25, $25, 64
+# CHECK-NEXT:    20034:       00 00 00 00     nop
+# CHECK-NEXT:    20038:       00 00 00 00     nop
+# CHECK-NEXT:    2003c:       00 00 00 00     nop
+# CHECK: foo2:
+# CHECK-NEXT:    20040:       00 00 00 00     nop
+# CHECK-NEXT:    20044:       00 00 00 00     nop
+# CHECK-NEXT:    20048:       00 00 00 00     nop
+# CHECK-NEXT:    2004c:       00 00 00 00     nop
+# CHECK-NEXT:    20050:       00 00 00 00     nop
+# CHECK-NEXT:    20054:       00 00 00 00     nop
+# CHECK-NEXT:    20058:       00 00 00 00     nop
+# CHECK-NEXT:    2005c:       00 00 00 00     nop
+# CHECK-NEXT:    20060:       00 00 00 00     nop
+# CHECK-NEXT:    20064:       00 00 00 00     nop
+# CHECK-NEXT:    20068:       00 00 00 00     nop
+# CHECK-NEXT:    2006c:       00 00 00 00     nop
+# CHECK-NEXT:    20070:       00 00 00 00     nop
+# CHECK-NEXT:    20074:       00 00 00 00     nop
+# CHECK-NEXT:    20078:       00 00 00 00     nop
+# CHECK-NEXT:    2007c:       00 00 00 00     nop
+# CHECK-NEXT:    20080:       00 00 00 00     nop
+# CHECK-NEXT:    20084:       00 00 00 00     nop
+# CHECK-NEXT:    20088:       00 00 00 00     nop
+# CHECK-NEXT:    2008c:       00 00 00 00     nop
+# CHECK-NEXT:    20090:       00 00 00 00     nop
+# CHECK-NEXT:    20094:       00 00 00 00     nop
+# CHECK-NEXT:    20098:       00 00 00 00     nop
+# CHECK-NEXT:    2009c:       00 00 00 00     nop
+# CHECK-NEXT:    200a0:       00 00 00 00     nop
+# CHECK-NEXT:    200a4:       00 00 00 00     nop
+# CHECK-NEXT:    200a8:       00 00 00 00     nop
+# CHECK-NEXT:    200ac:       00 00 00 00     nop
+# CHECK-NEXT:    200b0:       00 00 00 00     nop
+# CHECK-NEXT:    200b4:       00 00 00 00     nop
+# CHECK-NEXT:    200b8:       00 00 00 00     nop
+# CHECK-NEXT:    200bc:       00 00 00 00     nop
+# CHECK-NEXT:    200c0:       00 00 00 00     nop
+# CHECK-NEXT:    200c4:       00 00 00 00     nop
+# CHECK-NEXT:    200c8:       00 00 00 00     nop
+# CHECK-NEXT:    200cc:       00 00 00 00     nop
+# CHECK-NEXT:    200d0:       00 00 00 00     nop
+# CHECK-NEXT:    200d4:       00 00 00 00     nop
+# CHECK-NEXT:    200d8:       00 00 00 00     nop
+# CHECK-NEXT:    200dc:       00 00 00 00     nop
+# CHECK-NEXT:    200e0:       00 00 00 00     nop
+# CHECK-NEXT:    200e4:       00 00 00 00     nop
+# CHECK-NEXT:    200e8:       00 00 00 00     nop
+# CHECK-NEXT:    200ec:       00 00 00 00     nop
+# CHECK-NEXT:    200f0:       00 00 00 00     nop
+# CHECK-NEXT:    200f4:       00 00 00 00     nop
+# CHECK-NEXT:    200f8:       00 00 00 00     nop
+# CHECK-NEXT:    200fc:       00 00 00 00     nop
+# CHECK-NEXT:    20100:       00 00 00 00     nop
+# CHECK-NEXT:    20104:       00 00 00 00     nop
+# CHECK-NEXT:    20108:       00 00 00 00     nop
+# CHECK-NEXT:    2010c:       00 00 00 00     nop
+# CHECK-NEXT:    20110:       00 00 00 00     nop
+# CHECK-NEXT:    20114:       00 00 00 00     nop
+# CHECK-NEXT:    20118:       00 00 00 00     nop
+# CHECK-NEXT:    2011c:       00 00 00 00     nop
+# CHECK-NEXT:    20120:       00 00 00 00     nop
+# CHECK-NEXT:    20124:       00 00 00 00     nop
+# CHECK-NEXT:    20128:       00 00 00 00     nop
+# CHECK-NEXT:    2012c:       00 00 00 00     nop
+# CHECK-NEXT:    20130:       00 00 00 00     nop
+# CHECK-NEXT:    20134:       00 00 00 00     nop
+# CHECK-NEXT:    20138:       00 00 00 00     nop
+# CHECK-NEXT:    2013c:       00 00 00 00     nop
+# CHECK-NEXT:    20140:       00 00 00 00     nop
+# CHECK-NEXT:    20144:       00 00 00 00     nop
+# CHECK-NEXT:    20148:       00 00 00 00     nop
+# CHECK-NEXT:    2014c:       00 00 00 00     nop
+# CHECK: __start:
+# CHECK-NEXT:    20150:       0c 00 80 00     jal     131072 <__LA25Thunk_foo1a>
+# CHECK-NEXT:    20154:       00 00 00 00     nop
+# CHECK-NEXT:    20158:       0c 00 80 0a     jal     131112 <__LA25Thunk_foo2>
+# CHECK-NEXT:    2015c:       00 00 00 00     nop
+# CHECK-NEXT:    20160:       0c 00 80 04     jal     131088 <__LA25Thunk_foo1b>
+# CHECK-NEXT:    20164:       00 00 00 00     nop
+# CHECK-NEXT:    20168:       0c 00 80 0a     jal     131112 <__LA25Thunk_foo2>
+# CHECK-NEXT:    2016c:       00 00 00 00     nop
+# CHECK-NEXT:    20170:       0c 00 80 60     jal     131456 <__LA25Thunk_fpic>
+# CHECK-NEXT:    20174:       00 00 00 00     nop
+# CHECK-NEXT:    20178:       0c 00 80 68     jal     131488 <fnpic>
+# CHECK-NEXT:    2017c:       00 00 00 00     nop
+# CHECK: __LA25Thunk_fpic:
+# CHECK-NEXT:    20180:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20184:       08 00 80 64     j       131472 <fpic>
+# CHECK-NEXT:    20188:       27 39 01 90     addiu   $25, $25, 400
+# CHECK-NEXT:    2018c:       00 00 00 00     nop
+# CHECK: fpic:
+# CHECK-NEXT:    20190:       00 00 00 00     nop
+# CHECK-NEXT:    20194:       00 00 00 00     nop
+# CHECK-NEXT:    20198:       00 00 00 00     nop
+# CHECK-NEXT:    2019c:       00 00 00 00     nop
+# CHECK: fnpic:
+# CHECK-NEXT:    201a0:       00 00 00 00     nop
+
+  .text
+  .globl __start
+__start:
+  jal foo1a
+  jal foo2
+  jal foo1b
+  jal foo2
+  jal fpic
+  jal fnpic
+
+# Test script with orphans added to existing OutputSection, the .text.1 and
+# .text.2 sections will be added to .text
+# RUN: echo "SECTIONS { .text 0x20000 : { *(.text) }  }" > %t2.script
+# RUN: ld.lld --script %t2.script %t-npic.o %t-pic.o %t-sto-pic.o -o %t2.exe
+# RUN: llvm-objdump -d %t2.exe | FileCheck -check-prefix=ORPH1 %s
+# ORPH1: Disassembly of section .text:
+# ORPH1-NEXT: __start:
+# ORPH1-NEXT:    20000:       0c 00 80 15     jal     131156 <__LA25Thunk_foo1a>
+# ORPH1-NEXT:    20004:       00 00 00 00     nop
+# ORPH1-NEXT:    20008:       0c 00 80 22     jal     131208 <__LA25Thunk_foo2>
+# ORPH1-NEXT:    2000c:       00 00 00 00     nop
+# ORPH1-NEXT:    20010:       0c 00 80 19     jal     131172 <__LA25Thunk_foo1b>
+# ORPH1-NEXT:    20014:       00 00 00 00     nop
+# ORPH1-NEXT:    20018:       0c 00 80 22     jal     131208 <__LA25Thunk_foo2>
+# ORPH1-NEXT:    2001c:       00 00 00 00     nop
+# ORPH1-NEXT:    20020:       0c 00 80 0c     jal     131120 <__LA25Thunk_fpic>
+# ORPH1-NEXT:    20024:       00 00 00 00     nop
+# ORPH1-NEXT:    20028:       0c 00 80 14     jal     131152 <fnpic>
+# ORPH1-NEXT:    2002c:       00 00 00 00     nop
+# ORPH1: __LA25Thunk_fpic:
+# ORPH1-NEXT:    20030:       3c 19 00 02     lui     $25, 2
+# ORPH1-NEXT:    20034:       08 00 80 10     j       131136 <fpic>
+# ORPH1-NEXT:    20038:       27 39 00 40     addiu   $25, $25, 64
+# ORPH1-NEXT:    2003c:       00 00 00 00     nop
+# ORPH1: fpic:
+# ORPH1-NEXT:    20040:       00 00 00 00     nop
+# ORPH1-NEXT:    20044:       00 00 00 00     nop
+# ORPH1-NEXT:    20048:       00 00 00 00     nop
+# ORPH1-NEXT:    2004c:       00 00 00 00     nop
+# ORPH1: fnpic:
+# ORPH1-NEXT:    20050:       00 00 00 00     nop
+# ORPH1: __LA25Thunk_foo1a:
+# ORPH1-NEXT:    20054:       3c 19 00 02     lui     $25, 2
+# ORPH1-NEXT:    20058:       08 00 80 20     j       131200 <foo1a>
+# ORPH1-NEXT:    2005c:       27 39 00 80     addiu   $25, $25, 128
+# ORPH1-NEXT:    20060:       00 00 00 00     nop
+# ORPH1: __LA25Thunk_foo1b:
+# ORPH1-NEXT:    20064:       3c 19 00 02     lui     $25, 2
+# ORPH1-NEXT:    20068:       08 00 80 21     j       131204 <foo1b>
+# ORPH1-NEXT:    2006c:       27 39 00 84     addiu   $25, $25, 132
+# ORPH1-NEXT:    20070:       00 00 00 00     nop
+# ORPH1-NEXT:    20074:       00 00 00 00     nop
+# ORPH1-NEXT:    20078:       00 00 00 00     nop
+# ORPH1-NEXT:    2007c:       00 00 00 00     nop
+# ORPH1: foo1a:
+# ORPH1-NEXT:    20080:       00 00 00 00     nop
+# ORPH1: foo1b:
+# ORPH1-NEXT:    20084:       00 00 00 00     nop
+# ORPH1: __LA25Thunk_foo2:
+# ORPH1-NEXT:    20088:       3c 19 00 02     lui     $25, 2
+# ORPH1-NEXT:    2008c:       08 00 80 28     j       131232 <foo2>
+# ORPH1-NEXT:    20090:       27 39 00 a0     addiu   $25, $25, 160
+# ORPH1-NEXT:    20094:       00 00 00 00     nop
+# ORPH1-NEXT:    20098:       00 00 00 00     nop
+# ORPH1-NEXT:    2009c:       00 00 00 00     nop
+# ORPH1: foo2:
+# ORPH1-NEXT:    200a0:       00 00 00 00     nop
+
+# Test script with orphans added to new OutputSection, the .text.1 and
+# .text.2 sections will form a new OutputSection .text
+# RUN: echo "SECTIONS { .out 0x20000 : { *(.text) }  }" > %t3.script
+# RUN: ld.lld --script %t3.script %t-npic.o %t-pic.o %t-sto-pic.o -o %t3.exe
+# RUN: llvm-objdump -d %t3.exe | FileCheck -check-prefix=ORPH2 %s
+# ORPH2: Disassembly of section .out:
+# ORPH2-NEXT: __start:
+# ORPH2-NEXT:    20000:       0c 00 80 18     jal     131168 <__LA25Thunk_foo1a>
+# ORPH2-NEXT:    20004:       00 00 00 00     nop
+# ORPH2-NEXT:    20008:       0c 00 80 22     jal     131208 <__LA25Thunk_foo2>
+# ORPH2-NEXT:    2000c:       00 00 00 00     nop
+# ORPH2-NEXT:    20010:       0c 00 80 1c     jal     131184 <__LA25Thunk_foo1b>
+# ORPH2-NEXT:    20014:       00 00 00 00     nop
+# ORPH2-NEXT:    20018:       0c 00 80 22     jal     131208 <__LA25Thunk_foo2>
+# ORPH2-NEXT:    2001c:       00 00 00 00     nop
+# ORPH2-NEXT:    20020:       0c 00 80 0c     jal     131120 <__LA25Thunk_fpic>
+# ORPH2-NEXT:    20024:       00 00 00 00     nop
+# ORPH2-NEXT:    20028:       0c 00 80 14     jal     131152 <fnpic>
+# ORPH2-NEXT:    2002c:       00 00 00 00     nop
+# ORPH2: __LA25Thunk_fpic:
+# ORPH2-NEXT:    20030:       3c 19 00 02     lui     $25, 2
+# ORPH2-NEXT:    20034:       08 00 80 10     j       131136 <fpic>
+# ORPH2-NEXT:    20038:       27 39 00 40     addiu   $25, $25, 64
+# ORPH2-NEXT:    2003c:       00 00 00 00     nop
+# ORPH2: fpic:
+# ORPH2-NEXT:    20040:       00 00 00 00     nop
+# ORPH2-NEXT:    20044:       00 00 00 00     nop
+# ORPH2-NEXT:    20048:       00 00 00 00     nop
+# ORPH2-NEXT:    2004c:       00 00 00 00     nop
+# ORPH2: fnpic:
+# ORPH2-NEXT:    20050:       00 00 00 00     nop
+# ORPH2-NEXT: Disassembly of section .text:
+# ORPH2-NEXT: __LA25Thunk_foo1a:
+# ORPH2-NEXT:    20060:       3c 19 00 02     lui     $25, 2
+# ORPH2-NEXT:    20064:       08 00 80 20     j       131200 <foo1a>
+# ORPH2-NEXT:    20068:       27 39 00 80     addiu   $25, $25, 128
+# ORPH2-NEXT:    2006c:       00 00 00 00     nop
+# ORPH2: __LA25Thunk_foo1b:
+# ORPH2-NEXT:    20070:       3c 19 00 02     lui     $25, 2
+# ORPH2-NEXT:    20074:       08 00 80 21     j       131204 <foo1b>
+# ORPH2-NEXT:    20078:       27 39 00 84     addiu   $25, $25, 132
+# ORPH2-NEXT:    2007c:       00 00 00 00     nop
+# ORPH2: foo1a:
+# ORPH2-NEXT:    20080:       00 00 00 00     nop
+# ORPH2: foo1b:
+# ORPH2-NEXT:    20084:       00 00 00 00     nop
+# ORPH2: __LA25Thunk_foo2:
+# ORPH2-NEXT:    20088:       3c 19 00 02     lui     $25, 2
+# ORPH2-NEXT:    2008c:       08 00 80 28     j       131232 <foo2>
+# ORPH2-NEXT:    20090:       27 39 00 a0     addiu   $25, $25, 160
+# ORPH2-NEXT:    20094:       00 00 00 00     nop
+# ORPH2-NEXT:    20098:       00 00 00 00     nop
+# ORPH2-NEXT:    2009c:       00 00 00 00     nop
+# ORPH2: foo2:
+# ORPH2-NEXT:    200a0:       00 00 00 00     nop