ELF: Place ordered sections in the middle of the unordered section list on targets with limited-range branches.

[pcc]

Summary

It generally does not matter much where we place sections ordered
by --symbol-ordering-file relative to other sections. But if the
ordered sections are hot (which is the case already for some users
of --symbol-ordering-file, and is increasingly more likely to be
the case once profile-guided section layout lands) and the target
has limited-range branches, it is beneficial to place the ordered
sections in the middle of the output section in order to decrease
the likelihood that a range extension thunk will be required to call
a hot function from a cold function or vice versa.

That is what this patch does. After D44966 it reduces the size of
Chromium for Android's .text section by 60KB.

[peter.smith]

That looks reasonable to me. Another heuristic that can be used in at least C programs is to look for the sections with the most number of calls to them and place these in the centre. This tends to reduce the number of thunks as many library functions are called from all over the program, however I think the performance loss of going through a thunk means that moving the hot functions makes more sense.

[ruiu]

I don't think I understand why this patch can reduce size of generated executables. This may increase performance because we use short branches to jump to hot functions, but how can it reduce the size of thunks?

lld/ELF/Writer.cpp

1088 ↗

(On Diff #140036)

Can you add a comment?

1091 ↗

(On Diff #140036)

nit: I'd write it in two lines.

[pcc]

Imagine that you have 8MB of hot code and 32MB of cold code. If the layout is:

8MB hot
32MB cold

only the first 8-16MB of the cold code (depending on which hot function it is actually calling) can call the hot code without a range extension thunk. However, if we use this layout:

16MB cold
8MB hot
16MB cold

both the last 8-16MB of the first block of cold code and the first 8-16MB of the second block of cold code can call the hot code without a thunk. So we effectively double the amount of code that could potentially call into the hot code without a thunk, reducing the number of thunks that we need.

[pcc]

• Address review comments

[ruiu]

Ah, so the assumption I was missing is that hot functions are called from many more places than cold functions. That's perhaps obvious, but that's not necessarily true. Could you add your explanation as a comment?

[pcc]

• Add comment

[ruiu]

LGTM

Thanks!

lld/trunk/ELF/Writer.cpp

static DenseMap<const InputSectionBase *, int> buildSectionOrder() {
   if (Config->WarnSymbolOrdering)
     for (auto OrderEntry : SymbolOrder)
       if (!OrderEntry.second.Present)
         warn("symbol ordering file: no such symbol: " + OrderEntry.first);
 
   return SectionOrder;
 }
 
+// Sorts the sections in ISD according to the provided section order.
+static void
+sortISDBySectionOrder(InputSectionDescription *ISD,
+                      const DenseMap<const InputSectionBase *, int> &Order) {
+  std::vector<InputSection *> UnorderedSections;
+  std::vector<InputSection *> OrderedSections;
+  uint64_t UnorderedSize = 0;
+
+  for (InputSection *IS : ISD->Sections) {
+    if (!Order.count(IS)) {
+      UnorderedSections.push_back(IS);
+      UnorderedSize += IS->getSize();
+      continue;
+    }
+    OrderedSections.push_back(IS);
+  }
+  std::sort(OrderedSections.begin(), OrderedSections.end(),
+            [&](InputSection *A, InputSection *B) {
+              return Order.lookup(A) < Order.lookup(B);
+            });
+
+  // Find an insertion point for the ordered section list in the unordered
+  // section list. On targets with limited-range branches, this is the mid-point
+  // of the unordered section list. This decreases the likelihood that a range
+  // extension thunk will be needed to enter or exit the ordered region. If the
+  // ordered section list is a list of hot functions, we can generally expect
+  // the ordered functions to be called more often than the unordered functions,
+  // making it more likely that any particular call will be within range, and
+  // therefore reducing the number of thunks required.
+  //
+  // For example, imagine that you have 8MB of hot code and 32MB of cold code.
+  // If the layout is:
+  //
+  // 8MB hot
+  // 32MB cold
+  //
+  // only the first 8-16MB of the cold code (depending on which hot function it
+  // is actually calling) can call the hot code without a range extension thunk.
+  // However, if we use this layout:
+  //
+  // 16MB cold
+  // 8MB hot
+  // 16MB cold
+  //
+  // both the last 8-16MB of the first block of cold code and the first 8-16MB
+  // of the second block of cold code can call the hot code without a thunk. So
+  // we effectively double the amount of code that could potentially call into
+  // the hot code without a thunk.
+  size_t UnorderedInsPt = 0;
+  if (Target->ThunkSectionSpacing && !OrderedSections.empty()) {
+    uint64_t UnorderedPos = 0;
+    for (; UnorderedInsPt != UnorderedSections.size(); ++UnorderedInsPt) {
+      UnorderedPos += UnorderedSections[UnorderedInsPt]->getSize();
+      if (UnorderedPos > UnorderedSize / 2)
+        break;
+    }
+  }
+
+  std::copy(UnorderedSections.begin(),
+            UnorderedSections.begin() + UnorderedInsPt, ISD->Sections.begin());
+  std::copy(OrderedSections.begin(), OrderedSections.end(),
+            ISD->Sections.begin() + UnorderedInsPt);
+  std::copy(UnorderedSections.begin() + UnorderedInsPt, UnorderedSections.end(),
+            ISD->Sections.begin() + UnorderedInsPt + OrderedSections.size());
+}
+
 static void sortSection(OutputSection *Sec,
                         const DenseMap<const InputSectionBase *, int> &Order) {
   StringRef Name = Sec->Name;
 
   // Sort input sections by section name suffixes for
   // __attribute__((init_priority(N))).
   if (Name == ".init_array" || Name == ".fini_array") {
     if (!Script->HasSectionsCommand)
static void sortSection(OutputSection *Sec,
 
   // Never sort these.
   if (Name == ".init" || Name == ".fini")
     return;
 
   // Sort input sections by priority using the list provided
   // by --symbol-ordering-file.
   if (!Order.empty())
-    Sec->sort([&](InputSectionBase *S) { return Order.lookup(S); });
+    for (BaseCommand *B : Sec->SectionCommands)
+      if (auto *ISD = dyn_cast<InputSectionDescription>(B))
+        sortISDBySectionOrder(ISD, Order);
 }
 
 // If no layout was provided by linker script, we want to apply default
 // sorting for special input sections. This also handles --symbol-ordering-file.
 template <class ELFT> void Writer<ELFT>::sortInputSections() {
   // Build the order once since it is expensive.
   DenseMap<const InputSectionBase *, int> Order = buildSectionOrder();
   for (BaseCommand *Base : Script->SectionCommands)

lld/trunk/test/ELF/arm-symbol-ordering-file.s

+# REQUIRES: arm
+# RUN: llvm-mc -filetype=obj -triple=armv7-unknown-linux %s -o %t.o
+
+# RUN: echo ordered > %t_order.txt
+# RUN: ld.lld --symbol-ordering-file %t_order.txt %t.o -o %t2.out
+# RUN: llvm-nm -n %t2.out | FileCheck %s
+
+# CHECK: unordered1
+# CHECK-NEXT: unordered2
+# CHECK-NEXT: unordered3
+# CHECK-NEXT: ordered
+# CHECK-NEXT: unordered4
+
+.section .foo,"ax",%progbits,unique,1
+unordered1:
+.zero 1
+
+.section .foo,"ax",%progbits,unique,2
+unordered2:
+.zero 1
+
+.section .foo,"ax",%progbits,unique,3
+unordered3:
+.zero 2
+
+.section .foo,"ax",%progbits,unique,4
+unordered4:
+.zero 4
+
+.section .foo,"ax",%progbits,unique,5
+ordered:
+.zero 1