[MC] Replace fragment ilist with singly-linked lists

Fragments are allocated with `operator new` and stored in an ilist with
Prev/Next/Parent pointers. A more efficient representation would be an
array of fragments without the overhead of Prev/Next pointers.

As the first step, replace ilist with singly-linked lists.

* `getPrevNode` uses have been eliminated by previous changes.
* The last use of the `Prev` pointer remains: for each subsection, there is an insertion point and
  the current insertion point is stored at `CurInsertionPoint`.
* `HexagonAsmBackend::finishLayout` needs a backward iterator. Save all
  fragments within `Frags`. Hexagon programs are usually small, and the
  performance does not matter that much.

To eliminate `Prev`, change the subsection representation to
singly-linked lists for subsections and a pointer to the active
singly-linked list. The fragments from all subsections will be chained
together at layout time.

Since fragment lists are disconnected before layout time, we can remove
`MCFragment::SubsectionNumber` (https://reviews.llvm.org/D69411). The
current implementation of `AttemptToFoldSymbolOffsetDifference` requires
future improvement for robustness.

Pull Request: https://github.com/llvm/llvm-project/pull/95077

6 files changed, 56 insertions, 72 deletions

diff --git a/llvm/lib/MC/MCAssembler.cpp b/llvm/lib/MC/MCAssembler.cpp
index 8490853e..4ff606d 100644
--- a/llvm/lib/MC/MCAssembler.cpp
+++ b/llvm/lib/MC/MCAssembler.cpp
@@ -831,6 +831,19 @@ void MCAssembler::layout(MCAsmLayout &Layout) {
     MCSection *Sec = Layout.getSectionOrder()[i];
     Sec->setLayoutOrder(i);
 
+    // Chain together fragments from all subsections.
+    MCDummyFragment Dummy(Sec);
+    MCFragment *Tail = &Dummy;
+    for (auto &[_, List] : Sec->Subsections) {
+      if (!List.Head)
+        continue;
+      Tail->Next = List.Head;
+      Tail = List.Tail;
+    }
+    Sec->Subsections.clear();
+    Sec->Subsections.push_back({0u, {Dummy.getNext(), Tail}});
+    Sec->CurFragList = &Sec->Subsections[0].second;
+
     unsigned FragmentIndex = 0;
     for (MCFragment &Frag : *Sec)
       Frag.setLayoutOrder(FragmentIndex++);
@@ -1094,7 +1107,7 @@ bool MCAssembler::relaxBoundaryAlign(MCAsmLayout &Layout,
 
   uint64_t AlignedOffset = Layout.getFragmentOffset(&BF);
   uint64_t AlignedSize = 0;
-  for (const MCFragment *F = BF.getNextNode();; F = F->getNextNode()) {
+  for (const MCFragment *F = BF.getNext();; F = F->getNext()) {
     AlignedSize += computeFragmentSize(Layout, *F);
     if (F == BF.getLastFragment())
       break;
diff --git a/llvm/lib/MC/MCExpr.cpp b/llvm/lib/MC/MCExpr.cpp
index b70ac86..2eecdb8 100644
--- a/llvm/lib/MC/MCExpr.cpp
+++ b/llvm/lib/MC/MCExpr.cpp
@@ -661,25 +661,16 @@ static void AttemptToFoldSymbolOffsetDifference(
     // this is important when the Subtarget is changed and a new MCDataFragment
     // is created in the case of foo: instr; .arch_extension ext; instr .if . -
     // foo.
-    if (SA.isVariable() || SB.isVariable() ||
-        FA->getSubsectionNumber() != FB->getSubsectionNumber())
+    if (SA.isVariable() || SB.isVariable())
       return;
 
     // Try to find a constant displacement from FA to FB, add the displacement
     // between the offset in FA of SA and the offset in FB of SB.
     bool Reverse = false;
-    if (FA == FB) {
+    if (FA == FB)
       Reverse = SA.getOffset() < SB.getOffset();
-    } else if (!isa<MCDummyFragment>(FA)) {
-      // Testing FA < FB is slow. Use setLayoutOrder to speed up computation.
-      // The formal layout order will be finalized in MCAssembler::layout.
-      if (FA->getLayoutOrder() == 0 || FB->getLayoutOrder()== 0) {
-        unsigned LayoutOrder = 0;
-        for (MCFragment &F : *FA->getParent())
-          F.setLayoutOrder(++LayoutOrder);
-      }
+    else if (!isa<MCDummyFragment>(FA))
       Reverse = FA->getLayoutOrder() < FB->getLayoutOrder();
-    }
 
     uint64_t SAOffset = SA.getOffset(), SBOffset = SB.getOffset();
     int64_t Displacement = SA.getOffset() - SB.getOffset();
@@ -695,7 +686,7 @@ static void AttemptToFoldSymbolOffsetDifference(
     // instruction, the difference cannot be resolved as it may be changed by
     // the linker.
     bool BBeforeRelax = false, AAfterRelax = false;
-    for (auto FI = FB->getIterator(), FE = SecA.end(); FI != FE; ++FI) {
+    for (auto FI = FB; FI; FI = FI->getNext()) {
       auto DF = dyn_cast<MCDataFragment>(FI);
       if (DF && DF->isLinkerRelaxable()) {
         if (&*FI != FB || SBOffset != DF->getContents().size())
@@ -726,12 +717,14 @@ static void AttemptToFoldSymbolOffsetDifference(
         return;
       }
     }
-    // If the previous loop does not find FA, FA must be a dummy fragment not in
-    // the fragment list (which means SA is a pending label (see
-    // flushPendingLabels)). In either case, we can resolve the difference.
-    assert(Found || isa<MCDummyFragment>(FA));
-    Addend += Reverse ? -Displacement : Displacement;
-    FinalizeFolding();
+    // If FA and FB belong to the same subsection, either the previous loop
+    // found FA, or FA is a dummy fragment not in the fragment list (which means
+    // SA is a pending label (see flushPendingLabels)) or FA and FB belong to
+    // different subsections. In either case, we can resolve the difference.
+    if (Found || isa<MCDummyFragment>(FA)) {
+      Addend += Reverse ? -Displacement : Displacement;
+      FinalizeFolding();
+    }
   }
 }
 
diff --git a/llvm/lib/MC/MCFragment.cpp b/llvm/lib/MC/MCFragment.cpp
index 84a5871..6d97e8c 100644
--- a/llvm/lib/MC/MCFragment.cpp
+++ b/llvm/lib/MC/MCFragment.cpp
@@ -141,7 +141,7 @@ const MCSymbol *MCAsmLayout::getBaseSymbol(const MCSymbol &Symbol) const {
 
 uint64_t MCAsmLayout::getSectionAddressSize(const MCSection *Sec) const {
   // The size is the last fragment's end offset.
-  const MCFragment &F = Sec->getFragmentList().back();
+  const MCFragment &F = *Sec->curFragList()->Tail;
   return getFragmentOffset(&F) + getAssembler().computeFragmentSize(*this, F);
 }
 
@@ -197,8 +197,6 @@ uint64_t llvm::computeBundlePadding(const MCAssembler &Assembler,
 
 /* *** */
 
-void ilist_alloc_traits<MCFragment>::deleteNode(MCFragment *V) { V->destroy(); }
-
 MCFragment::MCFragment(FragmentType Kind, bool HasInstructions,
                        MCSection *Parent)
     : Parent(Parent), Atom(nullptr), Offset(~UINT64_C(0)), LayoutOrder(0),
diff --git a/llvm/lib/MC/MCObjectStreamer.cpp b/llvm/lib/MC/MCObjectStreamer.cpp
index ae4e691..bf1ce76 100644
--- a/llvm/lib/MC/MCObjectStreamer.cpp
+++ b/llvm/lib/MC/MCObjectStreamer.cpp
@@ -180,7 +180,6 @@ void MCObjectStreamer::reset() {
     if (getContext().getTargetOptions())
       Assembler->setRelaxAll(getContext().getTargetOptions()->MCRelaxAll);
   }
-  CurInsertionPoint = MCSection::iterator();
   EmitEHFrame = true;
   EmitDebugFrame = false;
   PendingLabels.clear();
@@ -200,12 +199,7 @@ void MCObjectStreamer::emitFrames(MCAsmBackend *MAB) {
 }
 
 MCFragment *MCObjectStreamer::getCurrentFragment() const {
-  assert(getCurrentSectionOnly() && "No current section!");
-
-  if (CurInsertionPoint != getCurrentSectionOnly()->begin())
-    return &*std::prev(CurInsertionPoint);
-
-  return nullptr;
+  return getCurrentSectionOnly()->curFragList()->Tail;
 }
 
 static bool canReuseDataFragment(const MCDataFragment &F,
@@ -391,8 +385,7 @@ bool MCObjectStreamer::changeSectionImpl(MCSection *Section,
   }
 
   CurSubsectionIdx = unsigned(IntSubsection);
-  CurInsertionPoint =
-      Section->getSubsectionInsertionPoint(CurSubsectionIdx);
+  Section->switchSubsection(CurSubsectionIdx);
   return Created;
 }
 
diff --git a/llvm/lib/MC/MCSection.cpp b/llvm/lib/MC/MCSection.cpp
index 9848d7f..1d9fe2c 100644
--- a/llvm/lib/MC/MCSection.cpp
+++ b/llvm/lib/MC/MCSection.cpp
@@ -24,7 +24,10 @@ MCSection::MCSection(SectionVariant V, StringRef Name, SectionKind K,
                      MCSymbol *Begin)
     : Begin(Begin), BundleGroupBeforeFirstInst(false), HasInstructions(false),
       HasLayout(false), IsRegistered(false), DummyFragment(this), Name(Name),
-      Variant(V), Kind(K) {}
+      Variant(V), Kind(K) {
+  // The initial subsection number is 0. Create a fragment list.
+  CurFragList = &Subsections.emplace_back(0u, FragList{}).second;
+}
 
 MCSymbol *MCSection::getEndSymbol(MCContext &Ctx) {
   if (!End)
@@ -34,7 +37,14 @@ MCSymbol *MCSection::getEndSymbol(MCContext &Ctx) {
 
 bool MCSection::hasEnded() const { return End && End->isInSection(); }
 
-MCSection::~MCSection() = default;
+MCSection::~MCSection() {
+  for (auto &[_, Chain] : Subsections) {
+    for (MCFragment *X = Chain.Head, *Y; X; X = Y) {
+      Y = X->Next;
+      X->destroy();
+    }
+  }
+}
 
 void MCSection::setBundleLockState(BundleLockStateType NewState) {
   if (NewState == NotBundleLocked) {
@@ -55,35 +65,15 @@ void MCSection::setBundleLockState(BundleLockStateType NewState) {
   ++BundleLockNestingDepth;
 }
 
-MCSection::iterator
-MCSection::getSubsectionInsertionPoint(unsigned Subsection) {
-  if (Subsection == 0 && SubsectionFragmentMap.empty())
-    return end();
-
-  SmallVectorImpl<std::pair<unsigned, MCFragment *>>::iterator MI = lower_bound(
-      SubsectionFragmentMap, std::make_pair(Subsection, (MCFragment *)nullptr));
-  bool ExactMatch = false;
-  if (MI != SubsectionFragmentMap.end()) {
-    ExactMatch = MI->first == Subsection;
-    if (ExactMatch)
-      ++MI;
-  }
-  iterator IP;
-  if (MI == SubsectionFragmentMap.end())
-    IP = end();
-  else
-    IP = MI->second->getIterator();
-  if (!ExactMatch && Subsection != 0) {
-    // The GNU as documentation claims that subsections have an alignment of 4,
-    // although this appears not to be the case.
-    MCFragment *F = new MCDataFragment();
-    SubsectionFragmentMap.insert(MI, std::make_pair(Subsection, F));
-    getFragmentList().insert(IP, F);
-    F->setParent(this);
-    F->setSubsectionNumber(Subsection);
-  }
-
-  return IP;
+void MCSection::switchSubsection(unsigned Subsection) {
+  size_t I = 0, E = Subsections.size();
+  while (I != E && Subsections[I].first < Subsection)
+    ++I;
+  // If the subsection number is not in the sorted Subsections list, create a
+  // new fragment list.
+  if (I == E || Subsections[I].first != Subsection)
+    Subsections.insert(Subsections.begin() + I, {Subsection, FragList{}});
+  CurFragList = &Subsections[I].second;
 }
 
 StringRef MCSection::getVirtualSectionKind() const { return "virtual"; }
@@ -111,13 +101,11 @@ void MCSection::flushPendingLabels() {
   // creating new empty data fragments for each Subsection with labels pending.
   while (!PendingLabels.empty()) {
     PendingLabel& Label = PendingLabels[0];
-    iterator CurInsertionPoint =
-      this->getSubsectionInsertionPoint(Label.Subsection);
-    const MCSymbol *Atom = nullptr;
-    if (CurInsertionPoint != begin())
-      Atom = std::prev(CurInsertionPoint)->getAtom();
+    switchSubsection(Label.Subsection);
+    const MCSymbol *Atom =
+        CurFragList->Tail ? CurFragList->Tail->getAtom() : nullptr;
     MCFragment *F = new MCDataFragment();
-    getFragmentList().insert(CurInsertionPoint, F);
+    addFragment(*F);
     F->setParent(this);
     F->setAtom(Atom);
     flushPendingLabels(F, 0, Label.Subsection);
diff --git a/llvm/lib/MC/WasmObjectWriter.cpp b/llvm/lib/MC/WasmObjectWriter.cpp
index 4512696..522e268 100644
--- a/llvm/lib/MC/WasmObjectWriter.cpp
+++ b/llvm/lib/MC/WasmObjectWriter.cpp
@@ -1864,15 +1864,14 @@ uint64_t WasmObjectWriter::writeOneObject(MCAssembler &Asm,
     if (EmptyFrag.getKind() != MCFragment::FT_Data)
       report_fatal_error(".init_array section should be aligned");
 
-    IT = std::next(IT);
-    const MCFragment &AlignFrag = *IT;
+    const MCFragment &AlignFrag = *EmptyFrag.getNext();
     if (AlignFrag.getKind() != MCFragment::FT_Align)
       report_fatal_error(".init_array section should be aligned");
     if (cast<MCAlignFragment>(AlignFrag).getAlignment() !=
         Align(is64Bit() ? 8 : 4))
       report_fatal_error(".init_array section should be aligned for pointers");
 
-    const MCFragment &Frag = *std::next(IT);
+    const MCFragment &Frag = *AlignFrag.getNext();
     if (Frag.hasInstructions() || Frag.getKind() != MCFragment::FT_Data)
       report_fatal_error("only data supported in .init_array section");