Revert "[LLD] Implement --enable-non-contiguous-regions" (#92005)

Reverts llvm/llvm-project#90007

Broke in merging I think.

12 files changed, 17 insertions, 261 deletions

diff --git a/lld/ELF/Config.h b/lld/ELF/Config.h
index dbb8141..c55b547 100644
--- a/lld/ELF/Config.h
+++ b/lld/ELF/Config.h
@@ -238,7 +238,6 @@ struct Config {
   bool emitLLVM;
   bool emitRelocs;
   bool enableNewDtags;
-  bool enableNonContiguousRegions;
   bool executeOnly;
   bool exportDynamic;
   bool fixCortexA53Errata843419;
diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp
index 828499f..dd33f4b 100644
--- a/lld/ELF/Driver.cpp
+++ b/lld/ELF/Driver.cpp
@@ -1250,8 +1250,6 @@ static void readConfigs(opt::InputArgList &args) {
   config->emitRelocs = args.hasArg(OPT_emit_relocs);
   config->enableNewDtags =
       args.hasFlag(OPT_enable_new_dtags, OPT_disable_new_dtags, true);
-  config->enableNonContiguousRegions =
-      args.hasArg(OPT_enable_non_contiguous_regions);
   config->entry = args.getLastArgValue(OPT_entry);
 
   errorHandler().errorHandlingScript =
@@ -3087,7 +3085,7 @@ template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
     // sectionBases.
     for (SectionCommand *cmd : script->sectionCommands)
       if (auto *osd = dyn_cast<OutputDesc>(cmd))
-        osd->osec.finalizeInputSections(script.get());
+        osd->osec.finalizeInputSections();
   }
 
   // Two input sections with different output sections should not be folded.
diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp
index 2a1ccd9..fa81611 100644
--- a/lld/ELF/InputSection.cpp
+++ b/lld/ELF/InputSection.cpp
@@ -161,7 +161,6 @@ uint64_t SectionBase::getOffset(uint64_t offset) const {
   }
   case Regular:
   case Synthetic:
-  case Spill:
     return cast<InputSection>(this)->outSecOff + offset;
   case EHFrame: {
     // Two code paths may reach here. First, clang_rt.crtbegin.o and GCC
@@ -310,12 +309,6 @@ std::string InputSectionBase::getObjMsg(uint64_t off) const {
       .str();
 }
 
-PotentialSpillSection::PotentialSpillSection(const InputSectionBase &source,
-                                             InputSectionDescription &isd)
-    : InputSection(source.file, source.flags, source.type, source.addralign, {},
-                   source.name, SectionBase::Spill),
-      isd(&isd) {}
-
 InputSection InputSection::discarded(nullptr, 0, 0, 0, ArrayRef<uint8_t>(), "");
 
 InputSection::InputSection(InputFile *f, uint64_t flags, uint32_t type,
diff --git a/lld/ELF/InputSection.h b/lld/ELF/InputSection.h
index 58e5306..1fb7077 100644
--- a/lld/ELF/InputSection.h
+++ b/lld/ELF/InputSection.h
@@ -48,7 +48,7 @@ template <class ELFT> struct RelsOrRelas {
 // sections.
 class SectionBase {
 public:
-  enum Kind { Regular, Synthetic, Spill, EHFrame, Merge, Output };
+  enum Kind { Regular, Synthetic, EHFrame, Merge, Output };
 
   Kind kind() const { return (Kind)sectionKind; }
 
@@ -382,8 +382,7 @@ public:
 
   static bool classof(const SectionBase *s) {
     return s->kind() == SectionBase::Regular ||
-           s->kind() == SectionBase::Synthetic ||
-           s->kind() == SectionBase::Spill;
+           s->kind() == SectionBase::Synthetic;
   }
 
   // Write this section to a mmap'ed file, assuming Buf is pointing to
@@ -426,26 +425,6 @@ private:
   template <class ELFT> void copyShtGroup(uint8_t *buf);
 };
 
-// A marker for a potential spill location for another input section. This
-// broadly acts as if it were the original section until address assignment.
-// Then it is either replaced with the real input section or removed.
-class PotentialSpillSection : public InputSection {
-public:
-  // The containing input section description; used to quickly replace this stub
-  // with the actual section.
-  InputSectionDescription *isd;
-
-  // Next potential spill location for the same source input section.
-  PotentialSpillSection *next = nullptr;
-
-  PotentialSpillSection(const InputSectionBase &source,
-                        InputSectionDescription &isd);
-
-  static bool classof(const SectionBase *sec) {
-    return sec->kind() == InputSectionBase::Spill;
-  }
-};
-
 static_assert(sizeof(InputSection) <= 160, "InputSection is too big");
 
 class SyntheticSection : public InputSection {
diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp
index 3ba59c1..c0a5014 100644
--- a/lld/ELF/LinkerScript.cpp
+++ b/lld/ELF/LinkerScript.cpp
@@ -304,9 +304,6 @@ getChangedSymbolAssignment(const SymbolAssignmentMap &oldValues) {
 void LinkerScript::processInsertCommands() {
   SmallVector<OutputDesc *, 0> moves;
   for (const InsertCommand &cmd : insertCommands) {
-    if (config->enableNonContiguousRegions)
-      error("INSERT cannot be used with --enable-non-contiguous-regions");
-
     for (StringRef name : cmd.names) {
       // If base is empty, it may have been discarded by
       // adjustOutputSections(). We do not handle such output sections.
@@ -489,12 +486,10 @@ static void sortInputSections(MutableArrayRef<InputSectionBase *> vec,
 // Compute and remember which sections the InputSectionDescription matches.
 SmallVector<InputSectionBase *, 0>
 LinkerScript::computeInputSections(const InputSectionDescription *cmd,
-                                   ArrayRef<InputSectionBase *> sections,
-                                   const OutputSection &outCmd) {
+                                   ArrayRef<InputSectionBase *> sections) {
   SmallVector<InputSectionBase *, 0> ret;
   SmallVector<size_t, 0> indexes;
   DenseSet<size_t> seen;
-  DenseSet<InputSectionBase *> spills;
   auto sortByPositionThenCommandLine = [&](size_t begin, size_t end) {
     llvm::sort(MutableArrayRef<size_t>(indexes).slice(begin, end - begin));
     for (size_t i = begin; i != end; ++i)
@@ -510,10 +505,10 @@ LinkerScript::computeInputSections(const InputSectionDescription *cmd,
     size_t sizeBeforeCurrPat = ret.size();
 
     for (size_t i = 0, e = sections.size(); i != e; ++i) {
-      // Skip if the section is dead or has been matched by a previous pattern
-      // in this input section description.
+      // Skip if the section is dead or has been matched by a previous input
+      // section description or a previous pattern.
       InputSectionBase *sec = sections[i];
-      if (!sec->isLive() || seen.contains(i))
+      if (!sec->isLive() || sec->parent || seen.contains(i))
         continue;
 
       // For --emit-relocs we have to ignore entries like
@@ -534,29 +529,6 @@ LinkerScript::computeInputSections(const InputSectionDescription *cmd,
           (sec->flags & cmd->withoutFlags) != 0)
         continue;
 
-      if (sec->parent) {
-        // Skip if not allowing multiple matches.
-        if (!config->enableNonContiguousRegions)
-          continue;
-
-        // Disallow spilling into /DISCARD/; special handling would be needed
-        // for this in address assignment, and the semantics are nebulous.
-        if (outCmd.name == "/DISCARD/")
-          continue;
-
-        // Skip if the section's first match was /DISCARD/; such sections are
-        // always discarded.
-        if (sec->parent->name == "/DISCARD/")
-          continue;
-
-        // Skip if the section was already matched by a different input section
-        // description within this output section.
-        if (sec->parent == &outCmd)
-          continue;
-
-        spills.insert(sec);
-      }
-
       ret.push_back(sec);
       indexes.push_back(i);
       seen.insert(i);
@@ -583,30 +555,6 @@ LinkerScript::computeInputSections(const InputSectionDescription *cmd,
   // Matched sections after the last SORT* are sorted by (--sort-alignment,
   // input order).
   sortByPositionThenCommandLine(sizeAfterPrevSort, ret.size());
-
-  // The flag --enable-non-contiguous-regions may cause sections to match an
-  // InputSectionDescription in more than one OutputSection. Matches after the
-  // first were collected in the spills set, so replace these with potential
-  // spill sections.
-  if (!spills.empty()) {
-    for (InputSectionBase *&sec : ret) {
-      if (!spills.contains(sec))
-        continue;
-
-      // Append the spill input section to the list for the input section,
-      // creating it if necessary.
-      PotentialSpillSection *pss = make<PotentialSpillSection>(
-          *sec, const_cast<InputSectionDescription &>(*cmd));
-      auto [it, inserted] =
-          potentialSpillLists.try_emplace(sec, PotentialSpillList{pss, pss});
-      if (!inserted) {
-        PotentialSpillSection *&tail = it->second.tail;
-        tail = tail->next = pss;
-      }
-      sec = pss;
-    }
-  }
-
   return ret;
 }
 
@@ -629,7 +577,7 @@ void LinkerScript::discardSynthetic(OutputSection &outCmd) {
         part.armExidx->exidxSections.end());
     for (SectionCommand *cmd : outCmd.commands)
       if (auto *isd = dyn_cast<InputSectionDescription>(cmd))
-        for (InputSectionBase *s : computeInputSections(isd, secs, outCmd))
+        for (InputSectionBase *s : computeInputSections(isd, secs))
           discard(*s);
   }
 }
@@ -640,7 +588,7 @@ LinkerScript::createInputSectionList(OutputSection &outCmd) {
 
   for (SectionCommand *cmd : outCmd.commands) {
     if (auto *isd = dyn_cast<InputSectionDescription>(cmd)) {
-      isd->sectionBases = computeInputSections(isd, ctx.inputSections, outCmd);
+      isd->sectionBases = computeInputSections(isd, ctx.inputSections);
       for (InputSectionBase *s : isd->sectionBases)
         s->parent = &outCmd;
       ret.insert(ret.end(), isd->sectionBases.begin(), isd->sectionBases.end());
@@ -696,9 +644,6 @@ void LinkerScript::processSectionCommands() {
 
   // Process OVERWRITE_SECTIONS first so that it can overwrite the main script
   // or orphans.
-  if (config->enableNonContiguousRegions && !overwriteSections.empty())
-    error("OVERWRITE_SECTIONS cannot be used with "
-          "--enable-non-contiguous-regions");
   DenseMap<CachedHashStringRef, OutputDesc *> map;
   size_t i = 0;
   for (OutputDesc *osd : overwriteSections) {
@@ -1121,12 +1066,8 @@ void LinkerScript::assignOffsets(OutputSection *sec) {
     // Handle a single input section description command.
     // It calculates and assigns the offsets for each section and also
     // updates the output section size.
-
-    auto &sections = cast<InputSectionDescription>(cmd)->sections;
-    for (InputSection *isec : sections) {
+    for (InputSection *isec : cast<InputSectionDescription>(cmd)->sections) {
       assert(isec->getParent() == sec);
-      if (isa<PotentialSpillSection>(isec))
-        continue;
       const uint64_t pos = dot;
       dot = alignToPowerOf2(dot, isec->addralign);
       isec->outSecOff = dot - sec->addr;
@@ -1423,114 +1364,6 @@ const Defined *LinkerScript::assignAddresses() {
   return getChangedSymbolAssignment(oldValues);
 }
 
-static bool hasRegionOverflowed(MemoryRegion *mr) {
-  if (!mr)
-    return false;
-  return mr->curPos - mr->getOrigin() > mr->getLength();
-}
-
-// Spill input sections in reverse order of address assignment to (potentially)
-// bring memory regions out of overflow. The size savings of a spill can only be
-// estimated, since general linker script arithmetic may occur afterwards.
-// Under-estimates may cause unnecessary spills, but over-estimates can always
-// be corrected on the next pass.
-bool LinkerScript::spillSections() {
-  if (!config->enableNonContiguousRegions)
-    return false;
-
-  bool spilled = false;
-  for (SectionCommand *cmd : reverse(sectionCommands)) {
-    auto *od = dyn_cast<OutputDesc>(cmd);
-    if (!od)
-      continue;
-    OutputSection *osec = &od->osec;
-    if (!osec->memRegion)
-      continue;
-
-    // Input sections that have replaced a potential spill and should be removed
-    // from their input section description.
-    DenseSet<InputSection *> spilledInputSections;
-
-    for (SectionCommand *cmd : reverse(osec->commands)) {
-      if (!hasRegionOverflowed(osec->memRegion) &&
-          !hasRegionOverflowed(osec->lmaRegion))
-        break;
-
-      auto *isd = dyn_cast<InputSectionDescription>(cmd);
-      if (!isd)
-        continue;
-      for (InputSection *isec : reverse(isd->sections)) {
-        // Potential spill locations cannot be spilled.
-        if (isa<PotentialSpillSection>(isec))
-          continue;
-
-        // Find the next potential spill location and remove it from the list.
-        auto it = potentialSpillLists.find(isec);
-        if (it == potentialSpillLists.end())
-          continue;
-        PotentialSpillList &list = it->second;
-        PotentialSpillSection *spill = list.head;
-        if (spill->next)
-          list.head = spill->next;
-        else
-          potentialSpillLists.erase(isec);
-
-        // Replace the next spill location with the spilled section and adjust
-        // its properties to match the new location. Note that the alignment of
-        // the spill section may have diverged from the original due to e.g. a
-        // SUBALIGN. Correct assignment requires the spill's alignment to be
-        // used, not the original.
-        spilledInputSections.insert(isec);
-        *llvm::find(spill->isd->sections, spill) = isec;
-        isec->parent = spill->parent;
-        isec->addralign = spill->addralign;
-
-        // Record the (potential) reduction in the region's end position.
-        osec->memRegion->curPos -= isec->getSize();
-        if (osec->lmaRegion)
-          osec->lmaRegion->curPos -= isec->getSize();
-
-        // Spilling continues until the end position no longer overflows the
-        // region. Then, another round of address assignment will either confirm
-        // the spill's success or lead to yet more spilling.
-        if (!hasRegionOverflowed(osec->memRegion) &&
-            !hasRegionOverflowed(osec->lmaRegion))
-          break;
-      }
-
-      // Remove any spilled input sections to complete their move.
-      if (!spilledInputSections.empty()) {
-        spilled = true;
-        llvm::erase_if(isd->sections, [&](InputSection *isec) {
-          return spilledInputSections.contains(isec);
-        });
-      }
-    }
-  }
-
-  return spilled;
-}
-
-// Erase any potential spill sections that were not used.
-void LinkerScript::erasePotentialSpillSections() {
-  if (potentialSpillLists.empty())
-    return;
-
-  // Collect the set of input section descriptions that contain potential
-  // spills.
-  DenseSet<InputSectionDescription *> isds;
-  for (const auto &[_, list] : potentialSpillLists)
-    for (PotentialSpillSection *s = list.head; s; s = s->next)
-      isds.insert(s->isd);
-
-  for (InputSectionDescription *isd : isds)
-    llvm::erase_if(isd->sections, [](InputSection *s) {
-      return isa<PotentialSpillSection>(s);
-    });
-
-  potentialSpillLists.clear();
-}
-
 // Creates program headers as instructed by PHDRS linker script command.
 SmallVector<PhdrEntry *, 0> LinkerScript::createPhdrs() {
   SmallVector<PhdrEntry *, 0> ret;
diff --git a/lld/ELF/LinkerScript.h b/lld/ELF/LinkerScript.h
index 734d4e7..b09cd12 100644
--- a/lld/ELF/LinkerScript.h
+++ b/lld/ELF/LinkerScript.h
@@ -10,7 +10,6 @@
 #define LLD_ELF_LINKER_SCRIPT_H
 
 #include "Config.h"
-#include "InputSection.h"
 #include "Writer.h"
 #include "lld/Common/LLVM.h"
 #include "lld/Common/Strings.h"
@@ -288,8 +287,7 @@ class LinkerScript final {
 
   SmallVector<InputSectionBase *, 0>
   computeInputSections(const InputSectionDescription *,
-                       ArrayRef<InputSectionBase *>,
-                       const OutputSection &outCmd);
+                       ArrayRef<InputSectionBase *>);
 
   SmallVector<InputSectionBase *, 0> createInputSectionList(OutputSection &cmd);
 
@@ -335,8 +333,6 @@ public:
 
   bool shouldKeep(InputSectionBase *s);
   const Defined *assignAddresses();
-  bool spillSections();
-  void erasePotentialSpillSections();
   void allocateHeaders(SmallVector<PhdrEntry *, 0> &phdrs);
   void processSectionCommands();
   void processSymbolAssignments();
@@ -404,15 +400,6 @@ public:
   //
   // then provideMap should contain the mapping: 'v' -> ['a', 'b', 'c']
   llvm::MapVector<StringRef, SmallVector<StringRef, 0>> provideMap;
-
-  // List of potential spill locations (PotentialSpillSection) for an input
-  // section.
-  struct PotentialSpillList {
-    // Never nullptr.
-    PotentialSpillSection *head;
-    PotentialSpillSection *tail;
-  };
-  llvm::DenseMap<InputSectionBase *, PotentialSpillList> potentialSpillLists;
 };
 
 struct ScriptWrapper {
diff --git a/lld/ELF/Options.td b/lld/ELF/Options.td
index 883a607..b9e05a4 100644
--- a/lld/ELF/Options.td
+++ b/lld/ELF/Options.td
@@ -197,9 +197,6 @@ def emit_relocs: F<"emit-relocs">, HelpText<"Generate relocations in output">;
 def enable_new_dtags: F<"enable-new-dtags">,
   HelpText<"Enable new dynamic tags (default)">;
 
-def enable_non_contiguous_regions : FF<"enable-non-contiguous-regions">,
-  HelpText<"Spill input sections to later matching output sections to avoid memory region overflow">;
-
 def end_group: F<"end-group">,
   HelpText<"Ignored for compatibility with GNU unless you pass --warn-backrefs">;
 
diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
index fcb4c43..9c66724 100644
--- a/lld/ELF/OutputSections.cpp
+++ b/lld/ELF/OutputSections.cpp
@@ -186,7 +186,7 @@ static MergeSyntheticSection *createMergeSynthetic(StringRef name,
 // new synthetic sections at the location of the first input section
 // that it replaces. It then finalizes each synthetic section in order
 // to compute an output offset for each piece of each input section.
-void OutputSection::finalizeInputSections(LinkerScript *script) {
+void OutputSection::finalizeInputSections() {
   std::vector<MergeSyntheticSection *> mergeSections;
   for (SectionCommand *cmd : commands) {
     auto *isd = dyn_cast<InputSectionDescription>(cmd);
@@ -226,11 +226,6 @@ void OutputSection::finalizeInputSections(LinkerScript *script) {
         i = std::prev(mergeSections.end());
         syn->entsize = ms->entsize;
         isd->sections.push_back(syn);
-        // The merge synthetic section inherits the potential spill locations of
-        // its first contained section.
-        auto it = script->potentialSpillLists.find(ms);
-        if (it != script->potentialSpillLists.end())
-          script->potentialSpillLists.try_emplace(syn, it->second);
       }
       (*i)->addSection(ms);
     }
diff --git a/lld/ELF/OutputSections.h b/lld/ELF/OutputSections.h
index 78fede4..421a018 100644
--- a/lld/ELF/OutputSections.h
+++ b/lld/ELF/OutputSections.h
@@ -75,7 +75,7 @@ public:
 
   void recordSection(InputSectionBase *isec);
   void commitSection(InputSection *isec);
-  void finalizeInputSections(LinkerScript *script = nullptr);
+  void finalizeInputSections();
 
   // The following members are normally only used in linker scripts.
   MemoryRegion *memRegion = nullptr;
diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index 298c714..7b9ada4 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -4074,13 +4074,6 @@ static bool isDuplicateArmExidxSec(InputSection *prev, InputSection *cur) {
 // InputSection with the highest address and any InputSections that have
 // mergeable .ARM.exidx table entries are removed from it.
 void ARMExidxSyntheticSection::finalizeContents() {
-  // Ensure that any fixed-point iterations after the first see the original set
-  // of sections.
-  if (!originalExecutableSections.empty())
-    executableSections = originalExecutableSections;
-  else if (config->enableNonContiguousRegions)
-    originalExecutableSections = executableSections;
-
   // The executableSections and exidxSections that we use to derive the final
   // contents of this SyntheticSection are populated before
   // processSectionCommands() and ICF. A /DISCARD/ entry in SECTIONS command or
diff --git a/lld/ELF/SyntheticSections.h b/lld/ELF/SyntheticSections.h
index 34949025..995fd4b 100644
--- a/lld/ELF/SyntheticSections.h
+++ b/lld/ELF/SyntheticSections.h
@@ -1255,10 +1255,6 @@ private:
   // either find the .ARM.exidx section or know that we need to generate one.
   SmallVector<InputSection *, 0> executableSections;
 
-  // Value of executableSecitons before finalizeContents(), so that it can be
-  // run repeateadly during fixed point iteration.
-  SmallVector<InputSection *, 0> originalExecutableSections;
-
   // The executable InputSection with the highest address to use for the
   // sentinel. We store separately from ExecutableSections as merging of
   // duplicate entries may mean this InputSection is removed from
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index 8d529f2..e400ed2 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -1403,18 +1403,13 @@ template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
   AArch64Err843419Patcher a64p;
   ARMErr657417Patcher a32p;
   script->assignAddresses();
-
   // .ARM.exidx and SHF_LINK_ORDER do not require precise addresses, but they
   // do require the relative addresses of OutputSections because linker scripts
   // can assign Virtual Addresses to OutputSections that are not monotonically
-  // increasing. Anything here must be repeatable, since spilling may change
-  // section order.
-  const auto finalizeOrderDependentContent = [this] {
-    for (Partition &part : partitions)
-      finalizeSynthetic(part.armExidx.get());
-    resolveShfLinkOrder();
-  };
-  finalizeOrderDependentContent();
+  // increasing.
+  for (Partition &part : partitions)
+    finalizeSynthetic(part.armExidx.get());
+  resolveShfLinkOrder();
 
   // Converts call x@GDPLT to call __tls_get_addr
   if (config->emachine == EM_HEXAGON)
@@ -1424,8 +1419,6 @@ template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
   for (;;) {
     bool changed = target->needsThunks ? tc.createThunks(pass, outputSections)
                                        : target->relaxOnce(pass);
-    bool spilled = script->spillSections();
-    changed |= spilled;
     ++pass;
 
     // With Thunk Size much smaller than branch range we expect to
@@ -1471,9 +1464,6 @@ template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
                     " does not converge");
         break;
       }
-    } else if (spilled) {
-      // Spilling can change relative section order.
-      finalizeOrderDependentContent();
     }
   }
   if (!config->relocatable)
@@ -1493,10 +1483,6 @@ template <class ELFT> void Writer<ELFT>::finalizeAddressDependentContent() {
              osec->name + " is not a multiple of alignment (" +
              Twine(osec->addralign) + ")");
     }
-
-  // Sizes are no longer allowed to grow, so all allowable spills have been
-  // taken. Remove any leftover potential spills.
-  script->erasePotentialSpillSections();
 }
 
 // If Input Sections have been shrunk (basic block sections) then