From 5ea6d50af113043da8a82215bb23f98c620e0112 Mon Sep 17 00:00:00 2001 From: Peter Collingbourne Date: Fri, 30 Mar 2018 21:36:54 +0000 Subject: [PATCH] ELF: Place ordered sections in the middle of the unordered section list on targets with limited-range branches. 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. Differential Revision: https://reviews.llvm.org/D44969 llvm-svn: 328905 --- lld/ELF/Writer.cpp | 70 ++++++++++++++++++++++++++++++++- lld/test/ELF/arm-symbol-ordering-file.s | 32 +++++++++++++++ 2 files changed, 101 insertions(+), 1 deletion(-) create mode 100644 lld/test/ELF/arm-symbol-ordering-file.s diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp index e685c8e..7178dbc 100644 --- a/lld/ELF/Writer.cpp +++ b/lld/ELF/Writer.cpp @@ -1087,6 +1087,72 @@ static DenseMap buildSectionOrder() { return SectionOrder; } +// Sorts the sections in ISD according to the provided section order. +static void +sortISDBySectionOrder(InputSectionDescription *ISD, + const DenseMap &Order) { + std::vector UnorderedSections; + std::vector 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 &Order) { StringRef Name = Sec->Name; @@ -1113,7 +1179,9 @@ static void sortSection(OutputSection *Sec, // 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(B)) + sortISDBySectionOrder(ISD, Order); } // If no layout was provided by linker script, we want to apply default diff --git a/lld/test/ELF/arm-symbol-ordering-file.s b/lld/test/ELF/arm-symbol-ordering-file.s new file mode 100644 index 0000000..fe3de0d --- /dev/null +++ b/lld/test/ELF/arm-symbol-ordering-file.s @@ -0,0 +1,32 @@ +# 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 -- 2.7.4