[ELF, draft] - Combine GOTPLT and GOT slots.

[grimar]

Summary

This is the PR27972 and PR32938.
I am posting it to show problems I faced when tried
to support this optimization and have some discussion
about it. Main question is do we want to support this optimization ?
And how to deal with 2, 3 paragraphs from below if yes,

x86_64 ABI (section B.1) tolds that when there are both
GOT and PLT references to the same symbol, normally linker
creates GOTPLT entry and GOT entry. Two dynamic relocations:
JUMP_SLOT and GLOB_DAT serves to handle things. That is
what LLD already implemented.

As optimization, linker may skip creating GOTPLT entry and create
special PLT entry that will use GOT instead. That allows to use single
GLOB_DAT dynamic relocation. Also since PLT entry is special,
it can be 8 bytes only and ABI suggests to use separate section for that.

Patch do next things:

1. It introduces .plt.got section. Name is consistent with bfd.

Section keeps special 8 PLT bytes entries with jump instruction which
uses address from GOT as destination. It was possible to use regular
.plt section (16 bytes for x86_64), but it would be suboptimal and probably not clean
from code POV.

2. When scanning relocations, new logic does not create got.plt entry if it is known

that symbol has got entry already. But not vise-versa. So currently it will optimize following code
correctly:

movq  foo@GOTPCREL(%rip), %rax
callq foo@PLT

but not:

callq foo@PLT
movq  foo@GOTPCREL(%rip), %rax

I thought about how to implement both.
I think it is possible if we delay creating plt entries until all relocations are
scanned. Then we will know if symbol uses got and so can avoid creation of .got.plt for it.
It should not be hard, but to keep patch cleaner, smaller and simpler I did not do that in draft.
Not sure what is better way to do that.

3. ABI says that optimization must be avoided if pointer equality is needed.

Looks it is possible to support if we scan relocations for checking that somehow.
That is what bfd do I believe. Not sure what is correct/best way to check that equality is needed ?
It may bring additional complication. Or should we disable this relaxation by default ?

[ruiu]

When you attempt to implement a documented ABI, please include a reference to the ABI. It seems you are implementing this: https://github.com/hjl-tools/x86-psABI/blob/68edce4f22070cc83ebc4a5df4b74222300dd24d/linker-optimization.tex

So, IIUC, this optimization aims to reduce the number of relocations for an interruptible function from 2 to 1. I'm skeptical if that makes some noticeable difference in performance because .got.plt isn't usually that big, and processing relocations is usually fast. IIRC, in lld (modulo the difference between static and dynamic linkers), we can process millions of relocations in a few seconds, so that's not slow at least.

We don't have to implement all optimizations that the ABI defines. We instead want to implement some of them that have non-marginal performance improvement. You presumably could see a difference in performance in a benchmark for the sake of benchmark, but my feeling is that I don't want to implement it unless someone comes to us with some numbers such as "we want to use this optimization because it makes our application starts up XX% faster" or something like that.

So, what is the motivation of implementing it? If it is because the ABI defines it, I don't think I'm convinced that we want it.

[grimar]

In D37333#858170, @ruiu wrote:

When you attempt to implement a documented ABI, please include a reference to the ABI. It seems you are implementing this: https://github.com/hjl-tools/x86-psABI/blob/68edce4f22070cc83ebc4a5df4b74222300dd24d/linker-optimization.tex

So, IIUC, this optimization aims to reduce the number of relocations for an interruptible function from 2 to 1. I'm skeptical if that makes some noticeable difference in performance because .got.plt isn't usually that big, and processing relocations is usually fast. IIRC, in lld (modulo the difference between static and dynamic linkers), we can process millions of relocations in a few seconds, so that's not slow at least.

We don't have to implement all optimizations that the ABI defines. We instead want to implement some of them that have non-marginal performance improvement. You presumably could see a difference in performance in a benchmark for the sake of benchmark, but my feeling is that I don't want to implement it unless someone comes to us with some numbers such as "we want to use this optimization because it makes our application starts up XX% faster" or something like that.

So, what is the motivation of implementing it? If it is because the ABI defines it, I don't think I'm convinced that we want it.

I am agree with you.
We had 2 open issues about this. In one of them Rafael also mentioned that it is not clear how much it is useful,
and I just wanted to check by myself how much hard to support it. If it would be few lines, we could implement it for feature completeness,
but when I faced problems mentioned in description of patch decided to tell about them first,
because I also suppose it is not very useful optimization and given the amount of changes it requires I would not
implement it.

So I suggest to close this bug with explicit "Will not fix" statement and look at possible objections from users then.

ELF/Arch/X86_64.cpp

public:
   RelExpr getRelExpr(uint32_t Type, const SymbolBody &S, const InputFile &File,
                      const uint8_t *Loc) const override;
   bool isPicRel(uint32_t Type) const override;
   void writeGotPltHeader(uint8_t *Buf) const override;
   void writeGotPlt(uint8_t *Buf, const SymbolBody &S) const override;
   void writePltHeader(uint8_t *Buf) const override;
   void writePlt(uint8_t *Buf, uint64_t GotPltEntryAddr, uint64_t PltEntryAddr,
                 int32_t Index, unsigned RelOff) const override;
+  void writePltGot(uint8_t *Buf, uint64_t GotEntryAddr,
+                   uint64_t PltEntryAddr) const override;
   void relocateOne(uint8_t *Loc, uint32_t Type, uint64_t Val) const override;
 
   RelExpr adjustRelaxExpr(uint32_t Type, const uint8_t *Data,
                           RelExpr Expr) const override;
   void relaxGot(uint8_t *Loc, uint64_t Val) const override;
   void relaxTlsGdToIe(uint8_t *Loc, uint32_t Type, uint64_t Val) const override;
   void relaxTlsGdToLe(uint8_t *Loc, uint32_t Type, uint64_t Val) const override;
   void relaxTlsIeToLe(uint8_t *Loc, uint32_t Type, uint64_t Val) const override;
void X86_64<ELFT>::writePlt(uint8_t *Buf, uint64_t GotPltEntryAddr,
   };
   memcpy(Buf, Inst, sizeof(Inst));
 
   write32le(Buf + 2, GotPltEntryAddr - PltEntryAddr - 6);
   write32le(Buf + 7, Index);
   write32le(Buf + 12, -Index * PltEntrySize - PltHeaderSize - 16);
 }
 
+template <class ELFT>
+void X86_64<ELFT>::writePltGot(uint8_t *Buf, uint64_t GotEntryAddr,
+                               uint64_t PltEntryAddr) const {
+  const uint8_t Inst[] = {
+      0xff, 0x25, 0x00, 0x00, 0x00, 0x00, // jmpq *got(%rip)
+      0xcc, 0xcc                          // trap instructions
+  };
+  memcpy(Buf, Inst, sizeof(Inst));
+  write32le(Buf + 2, GotEntryAddr - PltEntryAddr - 6);
+}
+
 template <class ELFT> bool X86_64<ELFT>::isPicRel(uint32_t Type) const {
   return Type != R_X86_64_PC32 && Type != R_X86_64_32 &&
          Type != R_X86_64_TPOFF32;
 }
 
 template <class ELFT>
 void X86_64<ELFT>::relaxTlsGdToLe(uint8_t *Loc, uint32_t Type,
                                   uint64_t Val) const {

ELF/Relocations.cpp

if (unsigned Processed =
       continue;
     }
 
     // If a relocation needs PLT, we create PLT and GOTPLT slots for the symbol.
     if (needsPlt(Expr) && !Body.isInPlt()) {
       if (Body.isGnuIFunc() && !Preemptible)
         addPltEntry(InX::Iplt, InX::IgotPlt, In<ELFT>::RelaIplt,
                     Target->IRelativeRel, Body, true);
+      else if (Body.isInGot() && InX::PltGot)
+        InX::PltGot->addEntry(Body);
       else
         addPltEntry(InX::Plt, InX::GotPlt, In<ELFT>::RelaPlt, Target->PltRel,
                     Body, !Preemptible);
     }
 
     // Create a GOT slot if a relocation needs GOT.
     if (needsGot(Expr)) {
       if (Config->EMachine == EM_MIPS) {

ELF/Symbols.h

public:
   unsigned Is32BitMipsGot : 1;
 
   // True if this symbol is in the Iplt sub-section of the Plt.
   unsigned IsInIplt : 1;
 
   // True if this symbol is in the Igot sub-section of the .got.plt or .got.
   unsigned IsInIgot : 1;
 
+  // True if this symbol is in the .plt.got section.
+  unsigned IsInPltGot : 1;
+
   unsigned IsPreemptible : 1;
 
   // The following fields have the same meaning as the ELF symbol attributes.
   uint8_t Type;    // symbol type
   uint8_t StOther; // st_other field value
 
   // The Type field may also have this value. It means that we have not yet seen
   // a non-Lazy symbol with this name, so we don't know what its type is. The

ELF/Symbols.cpp

static uint64_t getSymVA(const SymbolBody &Body, int64_t &Addend) {
   }
   llvm_unreachable("invalid symbol kind");
 }
 
 SymbolBody::SymbolBody(Kind K, StringRefZ Name, bool IsLocal, uint8_t StOther,
                        uint8_t Type)
     : SymbolKind(K), NeedsPltAddr(false), IsLocal(IsLocal),
       IsInGlobalMipsGot(false), Is32BitMipsGot(false), IsInIplt(false),
-      IsInIgot(false), IsPreemptible(false), Type(Type), StOther(StOther),
-      Name(Name) {}
+      IsInIgot(false), IsInPltGot(false), IsPreemptible(false), Type(Type),
+      StOther(StOther), Name(Name) {}
 
 InputFile *SymbolBody::getFile() const {
   if (isLocal()) {
     const SectionBase *Sec = cast<DefinedRegular>(this)->Section;
     // Local absolute symbols actually have a file, but that is not currently
     // used. We could support that by having a mostly redundant InputFile in
     // SymbolBody, or having a special absolute section if needed.
     return Sec ? cast<InputSectionBase>(Sec)->File : nullptr;

 
 uint64_t SymbolBody::getGotPltOffset() const {
   return GotPltIndex * Target->GotPltEntrySize;
 }
 
 uint64_t SymbolBody::getPltVA() const {
   if (this->IsInIplt)
     return InX::Iplt->getVA() + PltIndex * Target->PltEntrySize;
+  if (this->IsInPltGot)
+    return InX::PltGot->getVA() + PltIndex * InX::PltGot->Entsize;
   return InX::Plt->getVA() + Target->PltHeaderSize +
          PltIndex * Target->PltEntrySize;
 }
 
 template <class ELFT> typename ELFT::uint SymbolBody::getSize() const {
   if (const auto *C = dyn_cast<DefinedCommon>(this))
     return C->Size;
   if (const auto *DR = dyn_cast<DefinedRegular>(this))

ELF/SyntheticSections.h

 
 private:
   unsigned getPltRelocOff() const;
   std::vector<std::pair<const SymbolBody *, unsigned>> Entries;
   // Iplt always has HeaderSize of 0, the Plt HeaderSize is always non-zero
   size_t HeaderSize;
 };
 
+// When there are both PLT and GOT references to symbol, linker normally
+// creates GOTPLT slot for PLT entry and GOT slot for GOT reference. Two
+// dynamic relocations are used. It is possible to combine GOTPLT and GOT slot.
+// PltGotSection is used for this optimization, it contains special 8-bytes
+// entries that are used instead of regular PLT entries.
+class PltGotSection : public SyntheticSection {
+public:
+  PltGotSection();
+  void writeTo(uint8_t *Buf) override;
+  size_t getSize() const override { return Entries.size() * 8; }
+  bool empty() const override { return Entries.empty(); }
+  void addEntry(SymbolBody &Sym);
+
+private:
+  std::vector<SymbolBody *> Entries;
+};
+
 class GdbIndexSection final : public SyntheticSection {
   const unsigned OffsetTypeSize = 4;
   const unsigned CuListOffset = 6 * OffsetTypeSize;
   const unsigned CompilationUnitSize = 16;
   const unsigned AddressEntrySize = 16 + OffsetTypeSize;
   const unsigned SymTabEntrySize = 2 * OffsetTypeSize;
 
 public:
struct InX {
   static InputSection *Interp;
   static GdbIndexSection *GdbIndex;
   static GotSection *Got;
   static GotPltSection *GotPlt;
   static IgotPltSection *IgotPlt;
   static MipsGotSection *MipsGot;
   static MipsRldMapSection *MipsRldMap;
   static PltSection *Plt;
+  static PltGotSection *PltGot;
   static PltSection *Iplt;
   static StringTableSection *ShStrTab;
   static StringTableSection *StrTab;
   static SymbolTableBaseSection *SymTab;
 };
 
 template <class ELFT> struct In : public InX {
   static EhFrameHeader<ELFT> *EhFrameHdr;

ELF/SyntheticSections.cpp

for (size_t I = 0; I < Entries.size(); ++I) {
     Off += Target->PltEntrySize;
   }
 }
 
 unsigned PltSection::getPltRelocOff() const {
   return (HeaderSize == 0) ? InX::Plt->getSize() : 0;
 }
 
+PltGotSection::PltGotSection()
+    : SyntheticSection(SHF_ALLOC | SHF_EXECINSTR, SHT_PROGBITS, 8, ".plt.got") {
+  Entsize = 8;
+}
+
+void PltGotSection::writeTo(uint8_t *Buf) {
+  uint64_t Off = 0;
+  for (SymbolBody *B : Entries) {
+    uint64_t Got = B->getGotVA();
+    uint64_t Plt = this->getVA() + Off;
+    Target->writePltGot(Buf + Off, Got, Plt);
+    Off += Target->PltEntrySize;
+  }
+}
+
+void PltGotSection::addEntry(SymbolBody &Sym) {
+  Sym.PltIndex = Entries.size();
+  Sym.IsInPltGot = true;
+  Entries.push_back(&Sym);
+}
+
 // The hash function used for .gdb_index version 5 or above.
 static uint32_t gdbHash(StringRef Str) {
   uint32_t R = 0;
   for (uint8_t C : Str)
     R = R * 67 + tolower(C) - 113;
   return R;
 }
 

 GdbIndexSection *InX::GdbIndex;
 GotSection *InX::Got;
 GotPltSection *InX::GotPlt;
 GnuHashTableSection *InX::GnuHashTab;
 IgotPltSection *InX::IgotPlt;
 MipsGotSection *InX::MipsGot;
 MipsRldMapSection *InX::MipsRldMap;
 PltSection *InX::Plt;
+PltGotSection *InX::PltGot;
 PltSection *InX::Iplt;
 StringTableSection *InX::ShStrTab;
 StringTableSection *InX::StrTab;
 SymbolTableBaseSection *InX::SymTab;
 
 template GdbIndexSection *elf::createGdbIndex<ELF32LE>();
 template GdbIndexSection *elf::createGdbIndex<ELF32BE>();
 template GdbIndexSection *elf::createGdbIndex<ELF64LE>();

ELF/Target.h

public:
   // If lazy binding is supported, the first entry of the PLT has code
   // to call the dynamic linker to resolve PLT entries the first time
   // they are called. This function writes that code.
   virtual void writePltHeader(uint8_t *Buf) const {}
 
   virtual void writePlt(uint8_t *Buf, uint64_t GotEntryAddr,
                         uint64_t PltEntryAddr, int32_t Index,
                         unsigned RelOff) const {}
+  virtual void writePltGot(uint8_t *Buf, uint64_t GotEntryAddr,
+                           uint64_t PltEntryAddr) const {}
   virtual void addPltHeaderSymbols(InputSectionBase *IS) const {}
   virtual void addPltSymbols(InputSectionBase *IS, uint64_t Off) const {}
   // Returns true if a relocation only uses the low bits of a value such that
   // all those bits are in in the same page. For example, if the relocation
   // only uses the low 12 bits in a system with 4k pages. If this is true, the
   // bits will always have the same value at runtime and we don't have to emit
   // a dynamic relocation.
   virtual bool usesOnlyLowPageBits(uint32_t Type) const;

ELF/Writer.cpp

In<ELFT>::RelaIplt = make<RelocationSection<ELFT>>(
       false /*Sort*/);
   Add(In<ELFT>::RelaIplt);
 
   InX::Plt = make<PltSection>(Target->PltHeaderSize);
   Add(InX::Plt);
   InX::Iplt = make<PltSection>(0);
   Add(InX::Iplt);
 
+  if (Config->EMachine == EM_X86_64) {
+    InX::PltGot = make<PltGotSection>();
+    Add(InX::PltGot);
+  }
+
   if (!Config->Relocatable) {
     if (Config->EhFrameHdr) {
       In<ELFT>::EhFrameHdr = make<EhFrameHeader<ELFT>>();
       Add(In<ELFT>::EhFrameHdr);
     }
     In<ELFT>::EhFrame = make<EhFrameSection<ELFT>>();
     Add(In<ELFT>::EhFrame);
   }

test/ELF/gotplt-x86-64.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
+# RUN: ld.lld %t -shared -o %t.so
+# RUN: llvm-readobj -s -r %t.so | FileCheck %s
+# RUN: llvm-objdump -d %t.so | FileCheck %s --check-prefix=DISASM
+
+# CHECK:      Section {
+# CHECK:        Index:
+# CHECK:        Name: .plt.got
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:     SHF_EXECINSTR
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x1010
+# CHECK-NEXT:   Offset: 0x1010
+# CHECK-NEXT:   Size: 8
+# CHECK-NEXT:   Link: 0
+# CHECK-NEXT:   Info: 0
+# CHECK-NEXT:   AddressAlignment: 8
+# CHECK-NEXT:   EntrySize: 8
+# CHECK-NEXT: }
+# CHECK:      Section {
+# CHECK:        Index:
+# CHECK:        Name: .got
+# CHECK-NEXT:   Type: SHT_PROGBITS
+# CHECK-NEXT:   Flags [
+# CHECK-NEXT:     SHF_ALLOC
+# CHECK-NEXT:     SHF_WRITE
+# CHECK-NEXT:   ]
+# CHECK-NEXT:   Address: 0x2090
+# CHECK-NEXT:   Offset: 0x2090
+# CHECK-NEXT:   Size: 8
+# CHECK-NEXT:   Link: 0
+# CHECK-NEXT:   Info: 0
+# CHECK-NEXT:   AddressAlignment: 8
+# CHECK-NEXT:   EntrySize: 0
+# CHECK-NEXT: }
+# CHECK:      Relocations [
+# CHECK-NEXT:  Section ({{.*}}) .rela.dyn {
+# CHECK-NEXT:    0x2090 R_X86_64_GLOB_DAT foo 0x0
+# CHECK-NEXT:  }
+# CHECK-NEXT: ]
+
+# DISASM:       Disassembly of section .text:
+# DISASM-NEXT:  _start:
+## 4233 == 0x1089; 0x1000 + 7 + 0x1089 == 0x2090 (.got).
+# DISASM-NEXT:      1000: {{.*}} movq  4233(%rip), %rax
+## 0x1007 + 4 + 5 == 0x1010 (.plt.got[0])
+# DISASM-NEXT:      1007: {{.*}} callq 4
+# DISASM-NEXT:  Disassembly of section .plt.got:
+# DISASM-NEXT:  .plt.got:
+# DISASM-NEXT:      1010: {{.*}} jmpq *4218(%rip)
+# DISASM-NEXT:      1016: {{.*}} int3
+# DISASM-NEXT:      1017: {{.*}} int3
+
+.globl _start
+_start:
+ movq  foo@GOTPCREL(%rip), %rax
+ callq foo@PLT