[ELF] - Implemented support for test/binop relaxations from latest ABI.

[grimar]

Summary

Patch implements next relaxation from latest ABI:

"Convert memory operand of test and binop into immediate operand, where binop is one of adc, add, and, cmp, or,
sbb, sub, xor instructions, when position-independent code is disabled."

It is described in System V Application Binary Interface AMD64 Architecture Processor
Supplement Draft Version 0.99.8 (https://github.com/hjl-tools/x86-psABI/wiki/x86-64-psABI-r249.pdf,
B.2 "B.2 Optimize GOTPCRELX Relocations").

The last relaxation to do after that afaik is:
"When PIC is disabled and foo is defined locally in the lower 32 bit address space, memory operand in mov can be converted into immediate operand."

[grimar]

• Do not relax 32bit no-PIC case (as it unknown what can use such instructions, llvm-mc does not generate relaxable relocations types for them).
• Updated test to use llvm-mc instead of precompiled binary.
• Minor redesign and comments adjustment.

[• rafael]

ELF/InputSection.cpp

260 ↗

(On Diff #59076)

This is the same value as R_ABS, move it there.

ELF/Relocations.cpp

247 ↗

(On Diff #59076)

This one is not RelExpr if it has the same value as R_ABS.

ELF/Relocations.h

42 ↗

(On Diff #59076)

Maybe just name this R_RELAX_GOT.

[• rafael]

ELF/Target.cpp

746 ↗

(On Diff #59076)

A mov can be relaxed into a "mov $" if we are producing a non pic output. No need to do it now, but add a fixme about it.

797 ↗

(On Diff #59076)

These are for the encoding? Maybe refer the official intel docs?

801 ↗

(On Diff #59076)

Which instruction is this? testq?

test/ELF/gotpc-relax-nopic.s

92 ↗

(On Diff #59076)

Not sure there is any value is testing movl in here. We know we don't produce a relaxable relocation with mc.

[grimar]

• Addressed Rafael's review comments.

ELF/InputSection.cpp

260 ↗

(On Diff #59076)

Done.

ELF/Relocations.cpp

247 ↗

(On Diff #59076)

Removed.

ELF/Target.cpp

746 ↗

(On Diff #59076)

Done.

797 ↗

(On Diff #59076)

Done.
(Btw we are using (1) in comments about TLS relaxations.)

801 ↗

(On Diff #59076)

Yes, it is testq.

test/ELF/gotpc-relax-nopic.s

92 ↗

(On Diff #59076)

Did it to show the difference between lld and other linkers here. Do not have strong opinion about real value, so removed.

[• rafael]

LGTM with nits

ELF/Target.cpp

759 ↗

(On Diff #59194)

You can drop the Type == R_X86_64_REX_GOTPCRELX making this just

return Config->Pic ? RelExpl : R_RELAX_GOT_PC_NOPIC;

no?

782 ↗

(On Diff #59194)

git-clang-format

test/ELF/gotpc-relax-nopic.s

16 ↗

(On Diff #59194)

Comment out of date.

[grimar]

In D20793#445826, @rafael wrote:

LGTM with nits

Thanks for review !
r271405 and waiting for buildbot results, just in case.

ELF/Target.cpp

759 ↗

(On Diff #59194)

Yes. I placed assert there instead to make clear what we expect.
Since we don't have testcase part for 32x instructions anymore, and llvm-mc
generating slightly different result from gas, I think it is reasonable.

lld/trunk/ELF/InputSection.cpp

getSymVA(uint32_t Type, typename ELFT::uint A, typename ELFT::uint P,
   case R_TLS:
     if (Target->TcbSize)
       return Body.getVA<ELFT>(A) +
              alignTo(Target->TcbSize, Out<ELFT>::TlsPhdr->p_align);
     return Body.getVA<ELFT>(A) - Out<ELFT>::TlsPhdr->p_memsz;
   case R_NEG_TLS:
     return Out<ELF32LE>::TlsPhdr->p_memsz - Body.getVA<ELFT>(A);
   case R_ABS:
+  case R_RELAX_GOT_PC_NOPIC:
     return Body.getVA<ELFT>(A);
   case R_GOT_OFF:
     return Body.getGotOffset<ELFT>() + A;
   case R_MIPS_GOT_LOCAL_PAGE:
     // If relocation against MIPS local symbol requires GOT entry, this entry
     // should be initialized by 'page address'. This address is high 16-bits
     // of sum the symbol's value and the addend.
     return Out<ELFT>::Got->getMipsLocalPageOffset(Body.getVA<ELFT>(A));
for (const Relocation &Rel : Relocations) {
 
     uintX_t AddrLoc = OutSec->getVA() + Offset;
     RelExpr Expr = Rel.Expr;
     uint64_t SymVA = SignExtend64<Bits>(
         getSymVA<ELFT>(Type, A, AddrLoc, *Rel.Sym, BufLoc, *File, Expr));
 
     switch (Expr) {
     case R_RELAX_GOT_PC:
+    case R_RELAX_GOT_PC_NOPIC:
       Target->relaxGot(BufLoc, SymVA);
       break;
     case R_RELAX_TLS_IE_TO_LE:
       Target->relaxTlsIeToLe(BufLoc, Type, SymVA);
       break;
     case R_RELAX_TLS_LD_TO_LE:
       Target->relaxTlsLdToLe(BufLoc, Type, SymVA);
       break;

lld/trunk/ELF/Relocations.h

enum RelExpr {
   R_PAGE_PC,
   R_PC,
   R_PLT,
   R_PLT_PC,
   R_PPC_OPD,
   R_PPC_PLT_OPD,
   R_PPC_TOC,
   R_RELAX_GOT_PC,
+  R_RELAX_GOT_PC_NOPIC,
   R_RELAX_TLS_GD_TO_IE,
   R_RELAX_TLS_GD_TO_LE,
   R_RELAX_TLS_IE_TO_LE,
   R_RELAX_TLS_LD_TO_LE,
   R_SIZE,
   R_THUNK,
   R_TLS,
   R_TLSGD,

lld/trunk/ELF/Relocations.cpp

static RelExpr adjustExpr(const elf::ObjectFile<ELFT> &File, SymbolBody &Body,
   if (Target->needsThunk(Type, File, Body))
     return R_THUNK;
   bool Preemptible = isPreemptible(Body, Type);
   if (Body.isGnuIFunc()) {
     Expr = toPlt(Expr);
   } else if (!Preemptible) {
     if (needsPlt(Expr))
       Expr = fromPlt(Expr);
-    if (Expr == R_GOT_PC && Target->canRelaxGot(Type, Data + Offset))
-      Expr = R_RELAX_GOT_PC;
+    if (Expr == R_GOT_PC)
+      Expr = Target->adjustRelaxGotExpr(Type, Data + Offset, Expr);
   }
 
   if (IsWrite || isStaticLinkTimeConstant<ELFT>(Expr, Type, Body))
     return Expr;
 
   // This relocation would require the dynamic linker to write a value to read
   // only memory. We can hack around it if we are producing an executable and
   // the refered symbol can be preemepted to refer to the executable.

lld/trunk/ELF/Target.h

public:
   // to support lazy loading.
   unsigned GotPltHeaderEntriesNum = 3;
 
   // Set to 0 for variant 2
   unsigned TcbSize = 0;
 
   uint32_t ThunkSize = 0;
 
-  virtual bool canRelaxGot(uint32_t Type, const uint8_t *Data) const;
+  virtual RelExpr adjustRelaxGotExpr(uint32_t Type, const uint8_t *Data,
+                                     RelExpr Expr) const;
   virtual void relaxGot(uint8_t *Loc, uint64_t Val) const;
   virtual void relaxTlsGdToIe(uint8_t *Loc, uint32_t Type, uint64_t Val) const;
   virtual void relaxTlsGdToLe(uint8_t *Loc, uint32_t Type, uint64_t Val) const;
   virtual void relaxTlsIeToLe(uint8_t *Loc, uint32_t Type, uint64_t Val) const;
   virtual void relaxTlsLdToLe(uint8_t *Loc, uint32_t Type, uint64_t Val) const;
 };
 
 uint64_t getPPC64TocBase();

lld/trunk/ELF/Target.cpp

public:
   bool isTlsInitialExecRel(uint32_t Type) const override;
   void writeGotPltHeader(uint8_t *Buf) const override;
   void writeGotPlt(uint8_t *Buf, uint64_t Plt) const override;
   void writePltZero(uint8_t *Buf) const override;
   void writePlt(uint8_t *Buf, uint64_t GotEntryAddr, uint64_t PltEntryAddr,
                 int32_t Index, unsigned RelOff) const override;
   void relocateOne(uint8_t *Loc, uint32_t Type, uint64_t Val) const override;
 
-  bool canRelaxGot(uint32_t Type, const uint8_t *Data) const override;
+  RelExpr adjustRelaxGotExpr(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 relaxTlsLdToLe(uint8_t *Loc, uint32_t Type, uint64_t Val) const override;
 };
 
 class PPCTargetInfo final : public TargetInfo {

 bool TargetInfo::isTlsInitialExecRel(uint32_t Type) const { return false; }
 
 bool TargetInfo::isTlsLocalDynamicRel(uint32_t Type) const { return false; }
 
 bool TargetInfo::isTlsGlobalDynamicRel(uint32_t Type) const {
   return false;
 }
 
-bool TargetInfo::canRelaxGot(uint32_t Type, const uint8_t *Data) const {
-  return false;
+RelExpr TargetInfo::adjustRelaxGotExpr(uint32_t Type, const uint8_t *Data,
+                                       RelExpr Expr) const {
+  return Expr;
 }
 
 void TargetInfo::relaxGot(uint8_t *Loc, uint64_t Val) const {
   llvm_unreachable("Should not have claimed to be relaxable");
 }
 
 void TargetInfo::relaxTlsGdToLe(uint8_t *Loc, uint32_t Type,
                                 uint64_t Val) const {
void X86_64TargetInfo::relocateOne(uint8_t *Loc, uint32_t Type,
   case R_X86_64_PC64:
     write64le(Loc, Val);
     break;
   default:
     fatal("unrecognized reloc " + Twine(Type));
   }
 }
 
-bool X86_64TargetInfo::canRelaxGot(uint32_t Type, const uint8_t *Data) const {
+RelExpr X86_64TargetInfo::adjustRelaxGotExpr(uint32_t Type, const uint8_t *Data,
+                                             RelExpr RelExpr) const {
   if (Type != R_X86_64_GOTPCRELX && Type != R_X86_64_REX_GOTPCRELX)
-    return false;
+    return RelExpr;
   const uint8_t Op = Data[-2];
   const uint8_t ModRm = Data[-1];
-  // Relax mov.
+  // FIXME: When PIC is disabled and foo is defined locally in the
+  // lower 32 bit address space, memory operand in mov can be converted into
+  // immediate operand. Otherwise, mov must be changed to lea. We support only
+  // latter relaxation at this moment.
   if (Op == 0x8b)
-    return true;
+    return R_RELAX_GOT_PC;
   // Relax call and jmp.
-  return Op == 0xff && (ModRm == 0x15 || ModRm == 0x25);
+  if (Op == 0xff && (ModRm == 0x15 || ModRm == 0x25))
+    return R_RELAX_GOT_PC;
+
+  // Relaxation of test, adc, add, and, cmp, or, sbb, sub, xor.
+  // If PIC then no relaxation is available.
+  // We also don't relax test/binop instructions without REX byte,
+  // they are 32bit operations and not common to have.
+  assert(Type == R_X86_64_REX_GOTPCRELX);
+  return Config->Pic ? RelExpr : R_RELAX_GOT_PC_NOPIC;
 }
 
 void X86_64TargetInfo::relaxGot(uint8_t *Loc, uint64_t Val) const {
   const uint8_t Op = Loc[-2];
   const uint8_t ModRm = Loc[-1];
 
   // Convert mov foo@GOTPCREL(%rip), %reg to lea foo(%rip), %reg.
   if (Op == 0x8b) {
     *(Loc - 2) = 0x8d;
     relocateOne(Loc, R_X86_64_PC32, Val);
     return;
   }
 
-  assert(Op == 0xff);
+  // Convert call/jmp instructions.
+  if (Op == 0xff) {
     if (ModRm == 0x15) {
       // ABI says we can convert call *foo@GOTPCREL(%rip) to nop call foo.
       // Instead we convert to addr32 call foo, where addr32 is instruction
       // prefix. That makes result expression to be a single instruction.
       *(Loc - 2) = 0x67; // addr32 prefix
       *(Loc - 1) = 0xe8; // call
     } else {
       assert(ModRm == 0x25);
       // Convert jmp *foo@GOTPCREL(%rip) to jmp foo nop.
       // jmp doesn't return, so it is fine to use nop here, it is just a stub.
       *(Loc - 2) = 0xe9; // jmp
       *(Loc + 3) = 0x90; // nop
       Loc -= 1;
       Val += 1;
     }
     relocateOne(Loc, R_X86_64_PC32, Val);
+    return;
+  }
+
+  assert(!Config->Pic);
+  // We are relaxing a rip relative to an absolute, so compensate for the old
+  // -4 addend.
+  Val += 4;
+  // "Intel 64 and IA-32 Architectures Software Developer's Manual V2"
+  // (http://www.intel.com/content/dam/www/public/us/en/documents/manuals/
+  //    64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf)
+  // can be used as reference.
+
+  const uint8_t Rex = Loc[-3];
+  // Convert "test %reg, foo@GOTPCREL(%rip)" to "test $foo, %reg".
+  if (Op == 0x85) {
+    // See "TEST-Logical Compare" (4-428 Vol. 2B),
+    // TEST r/m64, r64 uses "full" ModR / M byte (no opcode extension).
+
+    // ModR/M byte has form XX YYY ZZZ, where
+    // YYY is MODRM.reg(register 2), ZZZ is MODRM.rm(register 1).
+    // XX has different meanings:
+    // 00: The operand's memory address is in reg1.
+    // 01: The operand's memory address is reg1 + a byte-sized displacement.
+    // 10: The operand's memory address is reg1 + a word-sized displacement.
+    // 11: The operand is reg1 itself.
+    // If an instruction requires only one operand, the unused reg2 field
+    // holds extra opcode bits rather than a register code
+    // 0xC0 == 11 000 000 binary.
+    // 0x38 == 00 111 000 binary.
+    // We transfer reg2 to reg1 here as operand.
+    // See "2.1.3 ModR/M and SIB Bytes" (Vol. 2A 2-3).
+    *(Loc - 1) = 0xc0 | (ModRm & 0x38) >> 3; // ModR/M byte.
+
+    // Change opcode from TEST r/m64, r64 to TEST r/m64, imm32
+    // See "TEST-Logical Compare" (4-428 Vol. 2B).
+    *(Loc - 2) = 0xf7;
+
+    // Move R bit to the B bit in REX byte.
+    // REX byte is encoded as 0100WRXB, where
+    // 0100 is 4bit fixed pattern.
+    // REX.W When 1, a 64-bit operand size is used. Otherwise, when 0, the
+    //   default operand size is used (which is 32-bit for most but not all
+    //   instructions).
+    // REX.R This 1-bit value is an extension to the MODRM.reg field.
+    // REX.X This 1-bit value is an extension to the SIB.index field.
+    // REX.B This 1-bit value is an extension to the MODRM.rm field or the
+    // SIB.base field.
+    // See "2.2.1.2 More on REX Prefix Fields " (2-8 Vol. 2A).
+    *(Loc - 3) = (Rex & ~0x4) | (Rex & 0x4) >> 2;
+    relocateOne(Loc, R_X86_64_PC32, Val);
+    return;
+  }
+
+  // If we are here then we need to relax the adc, add, and, cmp, or, sbb, sub
+  // or xor operations.
+
+  // Convert "binop foo@GOTPCREL(%rip), %reg" to "binop $foo, %reg".
+  // Logic is close to one for test instruction above, but we also
+  // write opcode extension here, see below for details.
+  *(Loc - 1) = 0xc0 | (ModRm & 0x38) >> 3 | (Op & 0x3c); // ModR/M byte.
+
+  // Primary opcode is 0x81, opcode extension is one of:
+  // 000b = ADD, 001b is OR, 010b is ADC, 011b is SBB,
+  // 100b is AND, 101b is SUB, 110b is XOR, 111b is CMP.
+  // This value was wrote to MODRM.reg in a line above.
+  // See "3.2 INSTRUCTIONS (A-M)" (Vol. 2A 3-15),
+  // "INSTRUCTION SET REFERENCE, N-Z" (Vol. 2B 4-1) for
+  // descriptions about each operation.
+  *(Loc - 2) = 0x81;
+  *(Loc - 3) = (Rex & ~0x4) | (Rex & 0x4) >> 2;
+  relocateOne(Loc, R_X86_64_PC32, Val);
 }
 
 // Relocation masks following the #lo(value), #hi(value), #ha(value),
 // #higher(value), #highera(value), #highest(value), and #highesta(value)
 // macros defined in section 4.5.1. Relocation Types of the PPC-elf64abi
 // document.
 static uint16_t applyPPCLo(uint64_t V) { return V; }
 static uint16_t applyPPCHi(uint64_t V) { return V >> 16; }

lld/trunk/test/ELF/gotpc-relax-nopic.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -relax-relocations -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: ld.lld %t.o -o %t1
+# RUN: llvm-readobj -symbols -r %t1 | FileCheck --check-prefix=SYMRELOC %s
+# RUN: llvm-objdump -d %t1 | FileCheck --check-prefix=DISASM %s
+
+## There is no relocations.
+# SYMRELOC:      Relocations [
+# SYMRELOC-NEXT: ]
+# SYMRELOC:      Symbols [
+# SYMRELOC:       Symbol {
+# SYMRELOC:        Name: bar
+# SYMRELOC-NEXT:   Value: 0x12000
+
+## 73728 = 0x12000 (bar)
+# DISASM:      Disassembly of section .text:
+# DISASM-NEXT: _start:
+# DISASM-NEXT:    11000:  48 81 d0 00 20 01 00  adcq  $73728, %rax
+# DISASM-NEXT:    11007:  48 81 c3 00 20 01 00  addq  $73728, %rbx
+# DISASM-NEXT:    1100e:  48 81 e1 00 20 01 00  andq  $73728, %rcx
+# DISASM-NEXT:    11015:  48 81 fa 00 20 01 00  cmpq  $73728, %rdx
+# DISASM-NEXT:    1101c:  48 81 cf 00 20 01 00  orq   $73728, %rdi
+# DISASM-NEXT:    11023:  48 81 de 00 20 01 00  sbbq  $73728, %rsi
+# DISASM-NEXT:    1102a:  48 81 ed 00 20 01 00  subq  $73728, %rbp
+# DISASM-NEXT:    11031:  49 81 f0 00 20 01 00  xorq  $73728, %r8
+# DISASM-NEXT:    11038:  49 f7 c7 00 20 01 00  testq $73728, %r15
+
+# RUN: ld.lld -shared %t.o -o %t2
+# RUN: llvm-readobj -s %t2 | FileCheck --check-prefix=SEC-PIC    %s
+# RUN: llvm-objdump -d %t2 | FileCheck --check-prefix=DISASM-PIC %s
+# SEC-PIC:      Section {
+# SEC-PIC:        Index:
+# SEC-PIC:        Name: .got
+# SEC-PIC-NEXT:   Type: SHT_PROGBITS
+# SEC-PIC-NEXT:   Flags [
+# SEC-PIC-NEXT:     SHF_ALLOC
+# SEC-PIC-NEXT:     SHF_WRITE
+# SEC-PIC-NEXT:   ]
+# SEC-PIC-NEXT:   Address: 0x2090
+# SEC-PIC-NEXT:   Offset: 0x2090
+# SEC-PIC-NEXT:   Size: 8
+# SEC-PIC-NEXT:   Link:
+# SEC-PIC-NEXT:   Info:
+# SEC-PIC-NEXT:   AddressAlignment:
+# SEC-PIC-NEXT:   EntrySize:
+# SEC-PIC-NEXT: }
+
+## Check that there was no relaxation performed. All values refer to got entry.
+## Ex: 0x1000 + 4233 + 7 = 0x2090
+##     0x102a + 4191 + 7 = 0x2090
+# DISASM-PIC:      Disassembly of section .text:
+# DISASM-PIC-NEXT: _start:
+# DISASM-PIC-NEXT:  1000: 48 13 05 89 10 00 00 adcq  4233(%rip), %rax
+# DISASM-PIC-NEXT:  1007: 48 03 1d 82 10 00 00 addq  4226(%rip), %rbx
+# DISASM-PIC-NEXT:  100e: 48 23 0d 7b 10 00 00 andq  4219(%rip), %rcx
+# DISASM-PIC-NEXT:  1015: 48 3b 15 74 10 00 00 cmpq  4212(%rip), %rdx
+# DISASM-PIC-NEXT:  101c: 48 0b 3d 6d 10 00 00 orq   4205(%rip), %rdi
+# DISASM-PIC-NEXT:  1023: 48 1b 35 66 10 00 00 sbbq  4198(%rip), %rsi
+# DISASM-PIC-NEXT:  102a: 48 2b 2d 5f 10 00 00 subq  4191(%rip), %rbp
+# DISASM-PIC-NEXT:  1031: 4c 33 05 58 10 00 00 xorq  4184(%rip), %r8
+# DISASM-PIC-NEXT:  1038: 4c 85 3d 51 10 00 00 testq 4177(%rip), %r15
+
+.data
+.type   bar, @object
+bar:
+ .byte   1
+ .size   bar, .-bar
+
+.text
+.globl  _start
+.type   _start, @function
+_start:
+  adcq    bar@GOTPCREL(%rip), %rax
+  addq    bar@GOTPCREL(%rip), %rbx
+  andq    bar@GOTPCREL(%rip), %rcx
+  cmpq    bar@GOTPCREL(%rip), %rdx
+  orq     bar@GOTPCREL(%rip), %rdi
+  sbbq    bar@GOTPCREL(%rip), %rsi
+  subq    bar@GOTPCREL(%rip), %rbp
+  xorq    bar@GOTPCREL(%rip), %r8
+  testq   %r15, bar@GOTPCREL(%rip)