From bae1c656bb33de759d3ea70d8089a25e7cc33ff8 Mon Sep 17 00:00:00 2001
From: Eugene Leviant <evgeny.leviant@gmail.com>
Date: Tue, 8 Nov 2016 10:44:48 +0000
Subject: [PATCH] [ELF] Heuristic for placing orphan section

Differential revision: https://reviews.llvm.org/D25325

llvm-svn: 286225
---
 lld/ELF/Writer.cpp                              | 57 ++++++++++++++++++++-----
 lld/test/ELF/linkerscript/orphan.s              | 29 +++++++++++++
 lld/test/ELF/linkerscript/sections-constraint.s |  2 +-
 3 files changed, 77 insertions(+), 11 deletions(-)
 create mode 100644 lld/test/ELF/linkerscript/orphan.s

diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index 18d1c7d..7f244d9 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -701,6 +701,22 @@ template <class ELFT> void Writer<ELFT>::createSections() {
     Sec->assignOffsets();
 }
 
+template <class ELFT>
+static bool canSharePtLoad(const OutputSectionBase<ELFT> &S1,
+                           const OutputSectionBase<ELFT> &S2) {
+  if (!(S1.getFlags() & SHF_ALLOC) || !(S2.getFlags() & SHF_ALLOC))
+    return false;
+
+  bool S1IsWrite = S1.getFlags() & SHF_WRITE;
+  bool S2IsWrite = S2.getFlags() & SHF_WRITE;
+  if (S1IsWrite != S2IsWrite)
+    return false;
+
+  if (!S1IsWrite)
+    return true; // RO and RX share a PT_LOAD with linker scripts.
+  return (S1.getFlags() & SHF_EXECINSTR) == (S2.getFlags() & SHF_EXECINSTR);
+}
+
 template <class ELFT> void Writer<ELFT>::sortSections() {
   if (!ScriptConfig->HasSections) {
     std::stable_sort(OutputSections.begin(), OutputSections.end(),
@@ -729,25 +745,46 @@ template <class ELFT> void Writer<ELFT>::sortSections() {
   // The way we define an order then is:
   // *  First put script sections at the start and sort the script and
   //    non-script sections independently.
-  // *  Move each non-script section to the first position where it
-  //    compareSectionsNonScript less than the successor.
+  // *  Move each non-script section to its preferred position. We try
+  //    to put each section in the last position where it it can share
+  //    a PT_LOAD.
 
   std::stable_sort(OutputSections.begin(), OutputSections.end(),
                    compareSections<ELFT>);
 
   auto I = OutputSections.begin();
   auto E = OutputSections.end();
-  auto NonScriptI = std::find_if(I, E, [](OutputSectionBase<ELFT> *S) {
-    return Script<ELFT>::X->getSectionIndex(S->getName()) == INT_MAX;
-  });
+  auto NonScriptI =
+      std::find_if(OutputSections.begin(), E, [](OutputSectionBase<ELFT> *S) {
+        return Script<ELFT>::X->getSectionIndex(S->getName()) == INT_MAX;
+      });
   while (NonScriptI != E) {
-    auto FirstGreater =
-        std::find_if(I, NonScriptI, [&](OutputSectionBase<ELFT> *S) {
-          return compareSectionsNonScript<ELFT>(*NonScriptI, S);
+    auto BestPos =
+        std::max_element(I, NonScriptI, [&](OutputSectionBase<ELFT> *&A,
+                                            OutputSectionBase<ELFT> *&B) {
+          bool ACanSharePtLoad = canSharePtLoad(**NonScriptI, *A);
+          bool BCanSharePtLoad = canSharePtLoad(**NonScriptI, *B);
+          if (ACanSharePtLoad != BCanSharePtLoad)
+            return BCanSharePtLoad;
+
+          bool ACmp = compareSectionsNonScript<ELFT>(*NonScriptI, A);
+          bool BCmp = compareSectionsNonScript<ELFT>(*NonScriptI, B);
+          if (ACmp != BCmp)
+            return BCmp; // FIXME: missing test
+
+          size_t PosA = &A - &OutputSections[0];
+          size_t PosB = &B - &OutputSections[0];
+          return ACmp ? PosA > PosB : PosA < PosB;
         });
-    std::rotate(FirstGreater, NonScriptI, NonScriptI + 1);
+
+    // max_element only returns NonScriptI if the range is empty. If the range
+    // is not empty we should consider moving the the element forward one
+    // position.
+    if (BestPos != NonScriptI &&
+        !compareSectionsNonScript<ELFT>(*NonScriptI, *BestPos))
+      ++BestPos;
+    std::rotate(BestPos, NonScriptI, NonScriptI + 1);
     ++NonScriptI;
-    ++I;
   }
 }
 
diff --git a/lld/test/ELF/linkerscript/orphan.s b/lld/test/ELF/linkerscript/orphan.s
new file mode 100644
index 0000000..48b5a95
--- /dev/null
+++ b/lld/test/ELF/linkerscript/orphan.s
@@ -0,0 +1,29 @@
+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: echo "SECTIONS {       \
+# RUN:  .text : { *(.text) }  \
+# RUN:  .rw1 : { *(.rw1) }    \
+# RUN:  .rw2 : { *(.rw2) }    \
+# RUN:  .rw3 : { *(.rw3) }    \
+# RUN: }" > %t.script
+# RUN: ld.lld -o %t1 --script %t.script %t
+# RUN: llvm-objdump -section-headers %t1 | FileCheck %s
+
+# CHECK:       0               00000000 0000000000000000 
+# CHECK-NEXT:  1 .text         00000000 0000000000000000 TEXT DATA 
+# CHECK-NEXT:  2 .jcr          00000008 0000000000000000 DATA 
+# CHECK-NEXT:  3 .rw1          00000008 0000000000000008 DATA 
+# CHECK-NEXT:  4 .rw2          00000008 0000000000000010 DATA 
+# CHECK-NEXT:  5 .rw3          00000008 0000000000000018 DATA 
+
+.section .rw1, "aw"
+ .quad 0
+
+.section .rw2, "aw"
+ .quad 0
+
+.section .rw3, "aw"
+ .quad 0
+
+.section .jcr, "aw"
+ .quad 0
diff --git a/lld/test/ELF/linkerscript/sections-constraint.s b/lld/test/ELF/linkerscript/sections-constraint.s
index a270e13..4d95ec18 100644
--- a/lld/test/ELF/linkerscript/sections-constraint.s
+++ b/lld/test/ELF/linkerscript/sections-constraint.s
@@ -23,9 +23,9 @@
 # NO1-NEXT: Idx Name          Size
 # NO1-NEXT: 0               00000000
 # NO1:  .writable     00000004
+# NO1:  .foo.2        00000004
 # NO1:  .readable     00000004
 # NO1:  .foo.1        00000004
-# NO1:  .foo.2        00000004
 
 .global _start
 _start:
-- 
2.7.4