Vendor import of lld trunk r305575:vendor/lld/lld-trunk-r305575

https://llvm.org/svn/llvm-project/lld/trunk@305575

1 files changed, 151 insertions, 112 deletions

diff --git a/ELF/Writer.cpp b/ELF/Writer.cpp
index ad95a8acced4..4ff06388ec78 100644
--- a/ELF/Writer.cpp
+++ b/ELF/Writer.cpp
@@ -73,8 +73,6 @@ private:
 
   std::unique_ptr<FileOutputBuffer> Buffer;
 
-  std::vector<OutputSection *> OutputSections;
-  std::vector<OutputSectionCommand *> OutputSectionCommands;
   OutputSectionFactory Factory{OutputSections};
 
   void addRelIpltSymbols();
@@ -137,46 +135,6 @@ template <class ELFT> void Writer<ELFT>::removeEmptyPTLoad() {
   Phdrs.erase(I, Phdrs.end());
 }
 
-// This function scans over the input sections and creates mergeable
-// synthetic sections. It removes MergeInputSections from array and
-// adds new synthetic ones. Each synthetic section is added to the
-// location of the first input section it replaces.
-static void combineMergableSections() {
-  std::vector<MergeSyntheticSection *> MergeSections;
-  for (InputSectionBase *&S : InputSections) {
-    MergeInputSection *MS = dyn_cast<MergeInputSection>(S);
-    if (!MS)
-      continue;
-
-    // We do not want to handle sections that are not alive, so just remove
-    // them instead of trying to merge.
-    if (!MS->Live)
-      continue;
-
-    StringRef OutsecName = getOutputSectionName(MS->Name);
-    uint64_t Flags = MS->Flags & ~(uint64_t)SHF_GROUP;
-    uint32_t Alignment = std::max<uint32_t>(MS->Alignment, MS->Entsize);
-
-    auto I = llvm::find_if(MergeSections, [=](MergeSyntheticSection *Sec) {
-      return Sec->Name == OutsecName && Sec->Flags == Flags &&
-             Sec->Alignment == Alignment;
-    });
-    if (I == MergeSections.end()) {
-      MergeSyntheticSection *Syn =
-          make<MergeSyntheticSection>(OutsecName, MS->Type, Flags, Alignment);
-      MergeSections.push_back(Syn);
-      I = std::prev(MergeSections.end());
-      S = Syn;
-    } else {
-      S = nullptr;
-    }
-    (*I)->addSection(MS);
-  }
-
-  std::vector<InputSectionBase *> &V = InputSections;
-  V.erase(std::remove(V.begin(), V.end(), nullptr), V.end());
-}
-
 template <class ELFT> static void combineEhFrameSections() {
   for (InputSectionBase *&S : InputSections) {
     EhInputSection *ES = dyn_cast<EhInputSection>(S);
@@ -192,6 +150,10 @@ template <class ELFT> static void combineEhFrameSections() {
 }
 
 template <class ELFT> void Writer<ELFT>::clearOutputSections() {
+  if (Script->Opt.HasSections)
+    Script->createOrphanCommands();
+  else
+    Script->fabricateDefaultCommands();
   // Clear the OutputSections to make sure it is not used anymore. Any
   // code from this point on should be using the linker script
   // commands.
@@ -205,7 +167,6 @@ template <class ELFT> void Writer<ELFT>::run() {
   // Create linker-synthesized sections such as .got or .plt.
   // Such sections are of type input section.
   createSyntheticSections();
-  combineMergableSections();
 
   if (!Config->Relocatable)
     combineEhFrameSections<ELFT>();
@@ -215,7 +176,6 @@ template <class ELFT> void Writer<ELFT>::run() {
     addReservedSymbols();
 
   // Create output sections.
-  Script->OutputSections = &OutputSections;
   if (Script->Opt.HasSections) {
     // If linker script contains SECTIONS commands, let it create sections.
     Script->processCommands(Factory);
@@ -256,7 +216,7 @@ template <class ELFT> void Writer<ELFT>::run() {
       OutputSectionCommands.begin(), OutputSectionCommands.end(),
       [](OutputSectionCommand *Cmd) { Cmd->maybeCompress<ELFT>(); });
 
-  Script->assignAddresses(Phdrs, OutputSectionCommands);
+  Script->assignAddresses(Phdrs);
 
   // Remove empty PT_LOAD to avoid causing the dynamic linker to try to mmap a
   // 0 sized region. This has to be done late since only after assignAddresses
@@ -340,9 +300,6 @@ template <class ELFT> void Writer<ELFT>::createSyntheticSections() {
     InX::Interp = nullptr;
   }
 
-  if (!Config->Relocatable)
-    Add(createCommentSection<ELFT>());
-
   if (Config->Strip != StripPolicy::All) {
     InX::StrTab = make<StringTableSection>(".strtab", false);
     InX::SymTab = make<SymbolTableSection<ELFT>>(*InX::StrTab);
@@ -772,8 +729,9 @@ static unsigned getSectionRank(const OutputSection *Sec) {
   return Rank;
 }
 
-static bool compareSectionsNonScript(const OutputSection *A,
-                                     const OutputSection *B) {
+static bool compareSections(const BaseCommand *ACmd, const BaseCommand *BCmd) {
+  const OutputSection *A = cast<OutputSectionCommand>(ACmd)->Sec;
+  const OutputSection *B = cast<OutputSectionCommand>(BCmd)->Sec;
   if (A->SortRank != B->SortRank)
     return A->SortRank < B->SortRank;
   if (!(A->SortRank & RF_NOT_ADDR_SET))
@@ -782,19 +740,6 @@ static bool compareSectionsNonScript(const OutputSection *A,
   return false;
 }
 
-// Output section ordering is determined by this function.
-static bool compareSections(const OutputSection *A, const OutputSection *B) {
-  // For now, put sections mentioned in a linker script
-  // first. Sections not on linker script will have a SectionIndex of
-  // INT_MAX.
-  int AIndex = A->SectionIndex;
-  int BIndex = B->SectionIndex;
-  if (AIndex != BIndex)
-    return AIndex < BIndex;
-
-  return compareSectionsNonScript(A, B);
-}
-
 void PhdrEntry::add(OutputSection *Sec) {
   Last = Sec;
   if (!First)
@@ -1004,30 +949,70 @@ template <class ELFT> void Writer<ELFT>::createSections() {
 // The more branches in getSectionRank that match, the more similar they are.
 // Since each branch corresponds to a bit flag, we can just use
 // countLeadingZeros.
-static unsigned getRankProximity(OutputSection *A, OutputSection *B) {
+static int getRankProximity(OutputSection *A, OutputSection *B) {
   return countLeadingZeros(A->SortRank ^ B->SortRank);
 }
 
+static int getRankProximity(OutputSection *A, BaseCommand *B) {
+  if (auto *Cmd = dyn_cast<OutputSectionCommand>(B))
+    if (Cmd->Sec)
+      return getRankProximity(A, Cmd->Sec);
+  return -1;
+}
+
+// When placing orphan sections, we want to place them after symbol assignments
+// so that an orphan after
+//   begin_foo = .;
+//   foo : { *(foo) }
+//   end_foo = .;
+// doesn't break the intended meaning of the begin/end symbols.
+// We don't want to go over sections since findOrphanPos is the
+// one in charge of deciding the order of the sections.
+// We don't want to go over changes to '.', since doing so in
+//  rx_sec : { *(rx_sec) }
+//  . = ALIGN(0x1000);
+//  /* The RW PT_LOAD starts here*/
+//  rw_sec : { *(rw_sec) }
+// would mean that the RW PT_LOAD would become unaligned.
+static bool shouldSkip(BaseCommand *Cmd) {
+  if (isa<OutputSectionCommand>(Cmd))
+    return false;
+  if (auto *Assign = dyn_cast<SymbolAssignment>(Cmd))
+    return Assign->Name != ".";
+  return true;
+}
+
 // We want to place orphan sections so that they share as much
 // characteristics with their neighbors as possible. For example, if
 // both are rw, or both are tls.
 template <typename ELFT>
-static std::vector<OutputSection *>::iterator
-findOrphanPos(std::vector<OutputSection *>::iterator B,
-              std::vector<OutputSection *>::iterator E) {
-  OutputSection *Sec = *E;
+static std::vector<BaseCommand *>::iterator
+findOrphanPos(std::vector<BaseCommand *>::iterator B,
+              std::vector<BaseCommand *>::iterator E) {
+  OutputSection *Sec = cast<OutputSectionCommand>(*E)->Sec;
 
   // Find the first element that has as close a rank as possible.
-  auto I = std::max_element(B, E, [=](OutputSection *A, OutputSection *B) {
+  auto I = std::max_element(B, E, [=](BaseCommand *A, BaseCommand *B) {
     return getRankProximity(Sec, A) < getRankProximity(Sec, B);
   });
   if (I == E)
     return E;
 
   // Consider all existing sections with the same proximity.
-  unsigned Proximity = getRankProximity(Sec, *I);
-  while (I != E && getRankProximity(Sec, *I) == Proximity &&
-         Sec->SortRank >= (*I)->SortRank)
+  int Proximity = getRankProximity(Sec, *I);
+  for (; I != E; ++I) {
+    auto *Cmd = dyn_cast<OutputSectionCommand>(*I);
+    if (!Cmd || !Cmd->Sec)
+      continue;
+    if (getRankProximity(Sec, Cmd->Sec) != Proximity ||
+        Sec->SortRank < Cmd->Sec->SortRank)
+      break;
+  }
+  auto J = std::find_if(
+      llvm::make_reverse_iterator(I), llvm::make_reverse_iterator(B),
+      [](BaseCommand *Cmd) { return isa<OutputSectionCommand>(Cmd); });
+  I = J.base();
+  while (I != E && shouldSkip(*I))
     ++I;
   return I;
 }
@@ -1041,19 +1026,38 @@ template <class ELFT> void Writer<ELFT>::sortSections() {
   if (Script->Opt.HasSections)
     Script->adjustSectionsBeforeSorting();
 
-  for (OutputSection *Sec : OutputSections)
-    Sec->SortRank = getSectionRank(Sec);
+  for (BaseCommand *Base : Script->Opt.Commands)
+    if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
+      if (OutputSection *Sec = Cmd->Sec)
+        Sec->SortRank = getSectionRank(Sec);
 
   if (!Script->Opt.HasSections) {
-    std::stable_sort(OutputSections.begin(), OutputSections.end(),
-                     compareSectionsNonScript);
+    // We know that all the OutputSectionCommands are contiguous in
+    // this case.
+    auto E = Script->Opt.Commands.end();
+    auto I = Script->Opt.Commands.begin();
+    auto IsSection = [](BaseCommand *Base) {
+      return isa<OutputSectionCommand>(Base);
+    };
+    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;
   }
 
+  // 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
-  // compareSectionsNonScript. This means that we cannot easily define a
-  // strict weak ordering. To see why, consider a comparison of a section in the
-  // script and one not in the script. We have a two simple options:
+  // compareSections. This means that we cannot easily define a strict weak
+  // ordering. To see why, consider a comparison of a section in the script and
+  // one not in the script. We have a two simple options:
   // * Make them equivalent (a is not less than b, and b is not less than a).
   //   The problem is then that equivalence has to be transitive and we can
   //   have sections a, b and c with only b in a script and a less than c
@@ -1068,27 +1072,51 @@ template <class ELFT> void Writer<ELFT>::sortSections() {
   //   .d (ro) # not in script
   //
   // The way we define an order then is:
-  // *  First put script sections at the start and sort the script sections.
-  // *  Move each non-script section to its preferred position. We try
+  // *  Sort only the orphan sections. They are in the end right now.
+  // *  Move each orphan section to its preferred position. We try
   //    to put each section in the last position where it it can share
   //    a PT_LOAD.
+  //
+  // There is some ambiguity as to where exactly a new entry should be
+  // inserted, because Opt.Commands contains not only output section
+  // commands but also other types of commands such as symbol assignment
+  // expressions. There's no correct answer here due to the lack of the
+  // formal specification of the linker script. We use heuristics to
+  // determine whether a new output command should be added before or
+  // after another commands. For the details, look at shouldSkip
+  // function.
+
+  auto I = Script->Opt.Commands.begin();
+  auto E = Script->Opt.Commands.end();
+  auto NonScriptI = std::find_if(I, E, [](BaseCommand *Base) {
+    if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
+      return Cmd->Sec && Cmd->Sec->SectionIndex == INT_MAX;
+    return false;
+  });
+
+  // Sort the orphan sections.
+  std::stable_sort(NonScriptI, E, compareSections);
 
-  std::stable_sort(OutputSections.begin(), OutputSections.end(),
-                   compareSections);
+  // As a horrible special case, skip the first . assignment if it is before any
+  // section. We do this because it is common to set a load address by starting
+  // the script with ". = 0xabcd" and the expectation is that every section is
+  // after that.
+  auto FirstSectionOrDotAssignment =
+      std::find_if(I, E, [](BaseCommand *Cmd) { return !shouldSkip(Cmd); });
+  if (FirstSectionOrDotAssignment != E &&
+      isa<SymbolAssignment>(**FirstSectionOrDotAssignment))
+    ++FirstSectionOrDotAssignment;
+  I = FirstSectionOrDotAssignment;
 
-  auto I = OutputSections.begin();
-  auto E = OutputSections.end();
-  auto NonScriptI =
-      std::find_if(OutputSections.begin(), E,
-                   [](OutputSection *S) { return S->SectionIndex == INT_MAX; });
   while (NonScriptI != E) {
     auto Pos = findOrphanPos<ELFT>(I, NonScriptI);
+    OutputSection *Orphan = cast<OutputSectionCommand>(*NonScriptI)->Sec;
 
     // As an optimization, find all sections with the same sort rank
     // and insert them with one rotate.
-    unsigned Rank = (*NonScriptI)->SortRank;
-    auto End = std::find_if(NonScriptI + 1, E, [=](OutputSection *Sec) {
-      return Sec->SortRank != Rank;
+    unsigned Rank = Orphan->SortRank;
+    auto End = std::find_if(NonScriptI + 1, E, [=](BaseCommand *Cmd) {
+      return cast<OutputSectionCommand>(Cmd)->Sec->SortRank != Rank;
     });
     std::rotate(Pos, NonScriptI, End);
     NonScriptI = End;
@@ -1194,25 +1222,27 @@ template <class ELFT> void Writer<ELFT>::finalizeSections() {
   addPredefinedSections();
   removeUnusedSyntheticSections(OutputSections);
 
+  clearOutputSections();
   sortSections();
 
+  // Now that we have the final list, create a list of all the
+  // OutputSectionCommands for convenience.
+  for (BaseCommand *Base : Script->Opt.Commands)
+    if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
+      OutputSectionCommands.push_back(Cmd);
+
   // This is a bit of a hack. A value of 0 means undef, so we set it
   // to 1 t make __ehdr_start defined. The section number is not
   // particularly relevant.
   Out::ElfHeader->SectionIndex = 1;
 
   unsigned I = 1;
-  for (OutputSection *Sec : OutputSections) {
+  for (OutputSectionCommand *Cmd : OutputSectionCommands) {
+    OutputSection *Sec = Cmd->Sec;
     Sec->SectionIndex = I++;
     Sec->ShName = InX::ShStrTab->addString(Sec->Name);
   }
 
-  if (!Script->Opt.HasSections)
-    Script->fabricateDefaultCommands();
-  for (BaseCommand *Base : Script->Opt.Commands)
-    if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
-      OutputSectionCommands.push_back(Cmd);
-
   // Binary and relocatable output does not have PHDRS.
   // The headers have to be created before finalize as that can influence the
   // image base and the dynamic section on mips includes the image base.
@@ -1222,8 +1252,6 @@ template <class ELFT> void Writer<ELFT>::finalizeSections() {
     Out::ProgramHeaders->Size = sizeof(Elf_Phdr) * Phdrs.size();
   }
 
-  clearOutputSections();
-
   // Compute the size of .rela.dyn and .rela.plt early since we need
   // them to populate .dynamic.
   for (SyntheticSection *SS : {In<ELFT>::RelaDyn, In<ELFT>::RelaPlt})
@@ -1253,9 +1281,12 @@ template <class ELFT> void Writer<ELFT>::finalizeSections() {
     // are out of range. This will need to turn into a loop that converges
     // when no more Thunks are added
     ThunkCreator TC;
-    if (TC.createThunks(OutputSectionCommands))
+    if (TC.createThunks(OutputSectionCommands)) {
       applySynthetic({InX::MipsGot},
                      [](SyntheticSection *SS) { SS->updateAllocSize(); });
+      if (TC.createThunks(OutputSectionCommands))
+        fatal("All non-range thunks should be created in first call");
+    }
   }
 
   // Fill other section headers. The dynamic table is finalized
@@ -1386,7 +1417,7 @@ template <class ELFT> std::vector<PhdrEntry> Writer<ELFT>::createPhdrs() {
   AddHdr(PT_PHDR, PF_R)->add(Out::ProgramHeaders);
 
   // PT_INTERP must be the second entry if exists.
-  if (OutputSection *Sec = findSection(".interp"))
+  if (OutputSection *Sec = findSectionInScript(".interp"))
     AddHdr(PT_INTERP, Sec->getPhdrFlags())->add(Sec);
 
   // Add the first PT_LOAD segment for regular output sections.
@@ -1397,7 +1428,8 @@ template <class ELFT> std::vector<PhdrEntry> Writer<ELFT>::createPhdrs() {
   Load->add(Out::ElfHeader);
   Load->add(Out::ProgramHeaders);
 
-  for (OutputSection *Sec : OutputSections) {
+  for (OutputSectionCommand *Cmd : OutputSectionCommands) {
+    OutputSection *Sec = Cmd->Sec;
     if (!(Sec->Flags & SHF_ALLOC))
       break;
     if (!needsPtLoad(Sec))
@@ -1419,9 +1451,11 @@ template <class ELFT> std::vector<PhdrEntry> Writer<ELFT>::createPhdrs() {
 
   // Add a TLS segment if any.
   PhdrEntry TlsHdr(PT_TLS, PF_R);
-  for (OutputSection *Sec : OutputSections)
+  for (OutputSectionCommand *Cmd : OutputSectionCommands) {
+    OutputSection *Sec = Cmd->Sec;
     if (Sec->Flags & SHF_TLS)
       TlsHdr.add(Sec);
+  }
   if (TlsHdr.First)
     Ret.push_back(std::move(TlsHdr));
 
@@ -1433,9 +1467,11 @@ template <class ELFT> std::vector<PhdrEntry> Writer<ELFT>::createPhdrs() {
   // PT_GNU_RELRO includes all sections that should be marked as
   // read-only by dynamic linker after proccessing relocations.
   PhdrEntry RelRo(PT_GNU_RELRO, PF_R);
-  for (OutputSection *Sec : OutputSections)
+  for (OutputSectionCommand *Cmd : OutputSectionCommands) {
+    OutputSection *Sec = Cmd->Sec;
     if (needsPtLoad(Sec) && isRelroSection(Sec))
       RelRo.add(Sec);
+  }
   if (RelRo.First)
     Ret.push_back(std::move(RelRo));
 
@@ -1447,7 +1483,7 @@ template <class ELFT> std::vector<PhdrEntry> Writer<ELFT>::createPhdrs() {
 
   // PT_OPENBSD_RANDOMIZE is an OpenBSD-specific feature. That makes
   // the dynamic linker fill the segment with random data.
-  if (OutputSection *Sec = findSection(".openbsd.randomdata"))
+  if (OutputSection *Sec = findSectionInScript(".openbsd.randomdata"))
     AddHdr(PT_OPENBSD_RANDOMIZE, Sec->getPhdrFlags())->add(Sec);
 
   // PT_GNU_STACK is a special section to tell the loader to make the
@@ -1470,7 +1506,8 @@ template <class ELFT> std::vector<PhdrEntry> Writer<ELFT>::createPhdrs() {
 
   // Create one PT_NOTE per a group of contiguous .note sections.
   PhdrEntry *Note = nullptr;
-  for (OutputSection *Sec : OutputSections) {
+  for (OutputSectionCommand *Cmd : OutputSectionCommands) {
+    OutputSection *Sec = Cmd->Sec;
     if (Sec->Type == SHT_NOTE) {
       if (!Note || Script->hasLMA(Sec))
         Note = AddHdr(PT_NOTE, PF_R);
@@ -1486,15 +1523,17 @@ template <class ELFT>
 void Writer<ELFT>::addPtArmExid(std::vector<PhdrEntry> &Phdrs) {
   if (Config->EMachine != EM_ARM)
     return;
-  auto I = std::find_if(
-      OutputSections.begin(), OutputSections.end(),
-      [](OutputSection *Sec) { return Sec->Type == SHT_ARM_EXIDX; });
-  if (I == OutputSections.end())
+  auto I =
+      std::find_if(OutputSectionCommands.begin(), OutputSectionCommands.end(),
+                   [](OutputSectionCommand *Cmd) {
+                     return Cmd->Sec->Type == SHT_ARM_EXIDX;
+                   });
+  if (I == OutputSectionCommands.end())
     return;
 
   // PT_ARM_EXIDX is the ARM EHABI equivalent of PT_GNU_EH_FRAME
   PhdrEntry ARMExidx(PT_ARM_EXIDX, PF_R);
-  ARMExidx.add(*I);
+  ARMExidx.add((*I)->Sec);
   Phdrs.push_back(ARMExidx);
 }