[BOLT] Add support for GOTPCRELX relocations

[maksfb]

Summary

The linker can convert instructions with GOTPCRELX relocations into a
form that uses an absolute addressing with an immediate. BOLT needs to
recognize such conversions and symbolize the immediates.

[rafauler]

Thanks! LGTM pending the test fix

bolt/lib/Target/X86/X86MCSymbolizer.cpp

91

If the operand if PC-relative -> If the operand is PC-relative

[maksfb]

Currently blocked on having trunk-built LLD available for pre-merge checks: https://github.com/google/llvm-premerge-checks/issues/401. The system LLD does not properly support --no-relax option.

[MaskRay]

bolt/lib/Core/Relocation.cpp

568

[maksfb]

Address comments.

[Amir]

In D126747#3562160, @maksfb wrote:

Currently blocked on having trunk-built LLD available for pre-merge checks: https://github.com/google/llvm-premerge-checks/issues/401. The system LLD does not properly support --no-relax option.

Should be unblocked now as pre-merge checks should now use lld build from trunk: https://github.com/google/llvm-premerge-checks/issues/401
Retriggered pre-merge checks which came back clean.

[maksfb]

In D126747#3571277, @Amir wrote:

In D126747#3562160, @maksfb wrote:

Currently blocked on having trunk-built LLD available for pre-merge checks: https://github.com/google/llvm-premerge-checks/issues/401. The system LLD does not properly support --no-relax option.

Should be unblocked now as pre-merge checks should now use lld build from trunk: https://github.com/google/llvm-premerge-checks/issues/401
Retriggered pre-merge checks which came back clean.

Great. Thank you.

bolt/include/bolt/Core/BinaryFunction.h

public:
   /// or nullptr if no such relocation exists.
   const Relocation *getRelocationAt(uint64_t Offset) const {
     assert(CurrentState == State::Empty &&
            "Relocations unavailable in the current function state.");
     auto RI = Relocations.find(Offset);
     return (RI == Relocations.end()) ? nullptr : &RI->second;
   }
 
+  /// Return the first relocation in the function that starts at an address in
+  /// the [StartOffset, EndOffset) range. Return nullptr if no such relocation
+  /// exists.
+  const Relocation *getRelocationInRange(uint64_t StartOffset,
+                                         uint64_t EndOffset) const {
+    assert(CurrentState == State::Empty &&
+           "Relocations unavailable in the current function state.");
+    auto RI = Relocations.lower_bound(StartOffset);
+    if (RI != Relocations.end() && RI->first < EndOffset)
+      return &RI->second;
+
+    return nullptr;
+  }
+
   /// Returns the raw binary encoding of this function.
   ErrorOr<ArrayRef<uint8_t>> getData() const;
 
   BinaryFunction &updateState(BinaryFunction::State State) {
     CurrentState = State;
     return *this;
   }
 
void addRelocationX86(uint64_t Offset, MCSymbol *Symbol, uint64_t RelType,
     case ELF::R_X86_64_8:
     case ELF::R_X86_64_16:
     case ELF::R_X86_64_32:
     case ELF::R_X86_64_32S:
     case ELF::R_X86_64_64:
     case ELF::R_X86_64_PC8:
     case ELF::R_X86_64_PC32:
     case ELF::R_X86_64_PC64:
+    case ELF::R_X86_64_GOTPCRELX:
+    case ELF::R_X86_64_REX_GOTPCRELX:
       Relocations[Offset] = Relocation{Offset, Symbol, RelType, Addend, Value};
       return;
     case ELF::R_X86_64_PLT32:
-    case ELF::R_X86_64_GOTPCRELX:
-    case ELF::R_X86_64_REX_GOTPCRELX:
     case ELF::R_X86_64_GOTPCREL:
     case ELF::R_X86_64_TPOFF32:
     case ELF::R_X86_64_GOTTPOFF:
       return;
     default:
       llvm_unreachable("Unexpected x86 relocation type in code");
     }
   }

bolt/include/bolt/Core/Relocation.h

struct Relocation {
   static bool isPCRelative(uint64_t Type);
 
   /// Check if \p Type is a supported relocation type.
   static bool isSupported(uint64_t Type);
 
   /// Return true if relocation type implies the creation of a GOT entry
   static bool isGOT(uint64_t Type);
 
+  /// Special relocation type that allows the linker to modify the instruction.
+  static bool isX86GOTPCRELX(uint64_t Type);
+
   /// Return true if relocation type is NONE
   static bool isNone(uint64_t Type);
 
   /// Return true if relocation type is RELATIVE
   static bool isRelative(uint64_t Type);
 
   /// Return true if relocation type is IRELATIVE
   static bool isIRelative(uint64_t Type);

bolt/lib/Core/Relocation.cpp

 }
 
 bool Relocation::isGOT(uint64_t Type) {
   if (Arch == Triple::aarch64)
     return isGOTAArch64(Type);
   return isGOTX86(Type);
 }
 
+bool Relocation::isX86GOTPCRELX(uint64_t Type) {
+  if (Arch != Triple::x86_64)
+    return false;
+  return Type == ELF::R_X86_64_GOTPCRELX || Type == ELF::R_X86_64_REX_GOTPCRELX;
+}
+
 bool Relocation::isNone(uint64_t Type) { return Type == getNone(); }
 
 bool Relocation::isRelative(uint64_t Type) {
   if (Arch == Triple::aarch64)
     return Type == ELF::R_AARCH64_RELATIVE;
   return Type == ELF::R_X86_64_RELATIVE;
 }
 

bolt/lib/Target/X86/X86MCSymbolizer.cpp

bool X86MCSymbolizer::tryAddingSymbolicOperand(
   auto addOperand = [&](const MCSymbol *Symbol, uint64_t Addend) {
     const MCExpr *Expr = MCSymbolRefExpr::create(Symbol, *Ctx);
     if (Addend)
       Expr = MCBinaryExpr::createAdd(Expr, MCConstantExpr::create(Addend, *Ctx),
                                      *Ctx);
     Inst.addOperand(MCOperand::createExpr(Expr));
   };
 
-  // Check for relocations against the operand.
-  const uint64_t InstOffset = InstAddress - Function.getAddress();
-  if (const Relocation *Relocation =
-          Function.getRelocationAt(InstOffset + ImmOffset)) {
-    uint64_t SymbolValue = Relocation->Value - Relocation->Addend;
-    if (Relocation->isPCRelative())
-      SymbolValue += InstAddress + ImmOffset;
-
-    // Process reference to the symbol.
-    BC.handleAddressRef(SymbolValue, Function, Relocation->isPCRelative());
-
-    uint64_t Addend = Relocation->Addend;
-    // Real addend for pc-relative targets is adjusted with a delta from
-    // the relocation placement to the next instruction.
-    if (Relocation->isPCRelative())
-      Addend += InstOffset + InstSize - Relocation->Offset;
-
-    addOperand(Relocation->Symbol, Addend);
-
-    return true;
-  }
-
   // Check if the operand being added is a displacement part of a compound
   // memory operand that uses PC-relative addressing. If it is, try to symbolize
-  // it without relocations.
+  // it without relocations. Return true on success, false otherwise.
+  auto processPCRelOperandNoRel = [&]() {
     const int MemOp = BC.MIB->getMemoryOperandNo(Inst);
     if (MemOp == -1)
       return false;
 
     const unsigned DispOp = MemOp + X86::AddrDisp;
     if (Inst.getNumOperands() != DispOp)
       return false;
 
     const MCOperand &Base = Inst.getOperand(MemOp + X86::AddrBaseReg);
     if (Base.getReg() != BC.MRI->getProgramCounter())
       return false;
 
     const MCOperand &Scale = Inst.getOperand(MemOp + X86::AddrScaleAmt);
     const MCOperand &Index = Inst.getOperand(MemOp + X86::AddrIndexReg);
     if (Scale.getImm() != 0 && Index.getReg() != MCRegister::NoRegister)
       return false;
 
     const MCSymbol *TargetSymbol;
     uint64_t TargetOffset;
     std::tie(TargetSymbol, TargetOffset) =
-      BC.handleAddressRef(Value, Function, /*IsPCRel*/ true);
+        BC.handleAddressRef(Value, Function, /*IsPCRel=*/true);
 
     addOperand(TargetSymbol, TargetOffset);
 
     return true;
+  };
+
+  // Check for GOTPCRELX relocations first. Because these relocations allow the
+  // linker to modify the instruction, we have to check the offset range
+  // corresponding to the instruction, not the offset of the operand.
+  // Note that if there is GOTPCRELX relocation against the instruction, there
+  // will be no other relocation in this range, since GOTPCRELX applies only to
+  // certain instruction types.
+  const uint64_t InstOffset = InstAddress - Function.getAddress();
+  const Relocation *Relocation =
+      Function.getRelocationInRange(InstOffset, InstOffset + InstSize);
+  if (Relocation && Relocation::isX86GOTPCRELX(Relocation->Type)) {
+    // If the operand is PC-relative, convert it without using the relocation
+    // information. For GOTPCRELX, it is safe to use the absolute address
+    // instead of extracting the addend from the relocation, as non-standard
+    // forms will be rejected by linker conversion process and the operand
+    // will always reference GOT which we don't rewrite.
+    if (processPCRelOperandNoRel())
+      return true;
+
+    // The linker converted the PC-relative address to an absolute one.
+    // Symbolize this address.
+    BC.handleAddressRef(Value, Function, /*IsPCRel=*/false);
+    const BinaryData *Target = BC.getBinaryDataAtAddress(Value);
+    assert(Target &&
+           "BinaryData should exist at converted GOTPCRELX destination");
+
+    addOperand(Target->getSymbol(), /*Addend=*/0);
+
+    return true;
+  }
+
+  // Check for relocations against the operand.
+  if (!Relocation || Relocation->Offset != InstOffset + ImmOffset)
+    Relocation = Function.getRelocationAt(InstOffset + ImmOffset);
+
+  if (!Relocation)
+    return processPCRelOperandNoRel();
+
+  uint64_t SymbolValue = Relocation->Value - Relocation->Addend;
+  if (Relocation->isPCRelative())
+    SymbolValue += InstAddress + ImmOffset;
+
+  // Process reference to the symbol.
+  BC.handleAddressRef(SymbolValue, Function, Relocation->isPCRelative());
+
+  uint64_t Addend = Relocation->Addend;
+  // Real addend for pc-relative targets is adjusted with a delta from
+  // the relocation placement to the next instruction.
+  if (Relocation->isPCRelative())
+    Addend += InstOffset + InstSize - Relocation->Offset;
+
+  addOperand(Relocation->Symbol, Addend);
+
+  return true;
 }
 
 void X86MCSymbolizer::tryAddingPcLoadReferenceComment(raw_ostream &CStream,
                                                       int64_t Value,
                                                       uint64_t Address) {}
 
 } // namespace bolt
 } // namespace llvm

bolt/test/X86/gotpcrelx.s

-# This reproduces a bug with misinterpreting the gotpcrelx reloc
-
-# Here we use llvm-mc -relax-relocations to produce R_X86_64_REX_GOTPCRELX
-# and ld.lld to consume it and optimize it, transforming a CMP <mem, reg>
-# into CMP <imm, reg>.
-# Then we check that BOLT updates correctly the imm operand that references
-# a function address. Currently XFAIL as we do not support it.
-
 # REQUIRES: system-linux
-# XFAIL: *
+
+## Check that BOLT correctly handles different types of instructions with
+## R_X86_64_GOTPCRELX or R_X86_64_REX_GOTPCRELX relocations and different
+## kinds of handling of the relocation by the linker (no relaxation, pic, and
+## non-pic).
 
 # RUN: llvm-mc -filetype=obj -triple x86_64-unknown-linux \
 # RUN:   -relax-relocations %s -o %t.o
-# RUN: llvm-strip --strip-unneeded %t.o
 # RUN: ld.lld %t.o -o %t.exe -q
-# RUN: llvm-readobj -r %t.exe | FileCheck --check-prefix=READOBJ %s
-# RUN: llvm-bolt %t.exe -relocs -o %t.out -lite=0
+# RUN: ld.lld %t.o -o %t.pie.exe -q -pie
+# RUN: ld.lld %t.o -o %t.no-relax.exe -q --no-relax
+# RUN: llvm-bolt %t.exe -relocs -o %t.out -print-cfg -print-only=_start \
+# RUN:   |& FileCheck --check-prefix=BOLT %s
+# RUN: llvm-bolt %t.pie.exe -o /dev/null -print-cfg -print-only=_start \
+# RUN:   |& FileCheck --check-prefix=PIE-BOLT %s
+# RUN: llvm-bolt %t.no-relax.exe -o /dev/null -print-cfg -print-only=_start \
+# RUN:   |& FileCheck --check-prefix=NO-RELAX-BOLT %s
 # RUN: llvm-objdump -d --no-show-raw-insn --print-imm-hex \
 # RUN:   %t.out | FileCheck --check-prefix=DISASM %s
 
-# Check that R_X86_64_REX_GOTPCRELX is present in the input binary
-# READOBJ: 0x[[#%X,]] R_X86_64_REX_GOTPCRELX foo 0x[[#%X,]]
-
-# DISASM:      Disassembly of section .text:
-# DISASM-EMPTY:
-# DISASM-NEXT: <_start>:
-# DISASM-NEXT:                 leaq  0x[[#%x,ADDR:]], %rax
-# DISASM-NEXT:                 cmpq  0x[[#ADDR]], %rax
-
   .text
   .globl _start
   .type _start, %function
 _start:
   .cfi_startproc
-  leaq foo, %rax
+# DISASM:      Disassembly of section .text:
+# DISASM-EMPTY:
+# DISASM-NEXT: <_start>:
+
+                      call *foo@GOTPCREL(%rip)
+# NO-RELAX-BOLT:      callq *{{.*}}(%rip)
+# BOLT:               callq foo
+# PIE-BOLT:           callq foo
+# DISASM-NEXT:        callq 0x[[#%x,ADDR:]]
+
+                      movq foo@GOTPCREL(%rip), %rdi
+# NO-RELAX-BOLT-NEXT: movq {{.*}}(%rip), %rdi
+# BOLT-NEXT:          leaq foo(%rip), %rdi
+# PIE-BOLT-NEXT:      leaq foo(%rip), %rdi
+# DISASM-NEXT:        leaq {{.*}}(%rip), %rdi # 0x[[#ADDR]]
+
+                      movl foo@GOTPCREL+4(%rip), %edi
+# NO-RELAX-BOLT-NEXT: movl {{.*}}(%rip), %edi
+# BOLT-NEXT:          movl {{.*}}(%rip), %edi
+# PIE-BOLT-NEXT:      movl {{.*}}(%rip), %edi
+# DISASM-NEXT:        movl {{.*}}(%rip), %edi
+
+                      test %rdi, foo@GOTPCREL(%rip)
+# NO-RELAX-BOLT-NEXT: testq %rdi, DATA{{.*}}(%rip)
+# BOLT-NEXT:          testq $foo, %rdi
+# PIE-BOLT-NEXT:      testq %rdi, DATA{{.*}}(%rip)
+# DISASM-NEXT:        testq $0x[[#ADDR]], %rdi
+
                       cmpq foo@GOTPCREL(%rip), %rax
-  je  b
-c:
-  mov $1, %rdi
-  callq foo
-b:
-  xorq %rdi, %rdi
-  callq foo
+# NO-RELAX-BOLT-NEXT: cmpq DATA{{.*}}(%rip), %rax
+# BOLT-NEXT:          cmpq $foo, %rax
+# PIE-BOLT-NEXT:      cmpq DATA{{.*}}(%rip), %rax
+# DISASM-NEXT:        cmpq $0x[[#ADDR]], %rax
+
+                      jmp *foo@GOTPCREL(%rip)
+# NO-RELAX-BOLT-NEXT: jmpq *DATA{{.*}}(%rip)
+# BOLT-NEXT:          jmp foo
+# PIE-BOLT-NEXT:      jmp foo
+# DISASM-NEXT:        jmp 0x[[#ADDR]]
+
   ret
   .cfi_endproc
   .size _start, .-_start
 
   .globl foo
   .type foo, %function
 foo:
   .cfi_startproc
   ret
   .cfi_endproc
   .size foo, .-foo