[ELF] MIPS paired R_MIPS_HI16/LO16 relocations support

[atanasyan]

Summary

Some MIPS relocations including R_MIPS_HI16/R_MIPS_LO16 use combined addends. Such addend is calculated using addends of both paired relocations. Each R_MIPS_HI16 relocation is paired with the next R_MIPS_LO16 relocation. ABI requires to compute such combined addend in case of REL relocation record format only.

For details see p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf

This patch implements lookup of the next paired relocation suing new InputSectionBase::findPairedRelocLocation method. The primary disadvantage of this approach is that we put MIPS specific logic into the common code. The next disadvantage is that we lookup R_MIPS_LO16 for each R_MIPS_HI16 relocation, while in fact multiple R_MIPS_HI16 might be paired with the single R_MIPS_LO16. From the other side this way allows us to keep MipsTargetInfo class stateless and implement later relocation handling in parallel.

This patch does not support R_MIPS_HI16/R_MIPS_LO16 relocations against _gp_disp symbol. In that case the relocations use a special formula for the calculation. That will be implemented later.

[ruiu]

Overall looks good but a few nits.

ELF/InputSection.cpp

96 ↗

(On Diff #41515)

Do you have to template isRela? IIRC, it is always Elf_Rel on MIPS.

106–118 ↗

(On Diff #41515)

I'd write this as it's shorter.

if (Type == R_MIPS_HI16)
  Type = R_MIPS_LO16;
else if (Type == R_MIPS_PCHI16)
  Type = R_MIPS_PCLO16;
else if (Type == R_MICROMIPS_HI16)
  Type = R_MICROMIPS_LO16;
else
  return nullptr;

ELF/Target.h

62 ↗

(On Diff #41515)

Remove "= nullptr" since the argument is always passed.

[atanasyan]

ELF/InputSection.cpp

96 ↗

(On Diff #41515)

Yes, isRela is always false for MIPS O32 ABI but I have to template isRela to be able to put the findPairedRelocLocation call into the relocate function. Otherwise compiler complains about conversion NextRelocs from RelIteratorRange<true> to RelIteratorRange<false>.

ELF/Target.h

62 ↗

(On Diff #41515)

The relocateTlsOptimize is also called from routines like relocateTlsIeToLe, writePltZeroEntry etc. Do you think it is better to pass the last argument as nullptr explicitly in these cases too?

[ruiu]

ELF/InputSection.cpp

96 ↗

(On Diff #41515)

Got it.

98 ↗

(On Diff #41515)

Can you rename findMipsPairedReloc? I'd like to include "Mips" in this function name.

ELF/Target.h

62 ↗

(On Diff #41515)

I don't know which is better, but I want to make it consistent. Could you remove nullptr from "relocateOne(..., nullptr)" in this patch?

[atanasyan]

• Rebased
• s/findPairedRelocLocation/findMipsPairedReloc/
• Do not pass nullptr to the findMipsPairedReloc explicitly
• Replace switch by series of if/else if/else operators

[ruiu]

LGTM

lld/trunk/ELF/InputSection.h

public:
 
   ArrayRef<uint8_t> getSectionData() const;
 
   // Returns a section that Rel is pointing to. Used by the garbage collector.
   InputSectionBase<ELFT> *getRelocTarget(const Elf_Rel &Rel);
   InputSectionBase<ELFT> *getRelocTarget(const Elf_Rela &Rel);
 
   template <bool isRela>
-  void relocate(uint8_t *Buf, uint8_t *BufEnd,
-                llvm::iterator_range<
-                    const llvm::object::Elf_Rel_Impl<ELFT, isRela> *> Rels);
+  using RelIteratorRange =
+      llvm::iterator_range<const llvm::object::Elf_Rel_Impl<ELFT, isRela> *>;
+
+  template <bool isRela>
+  void relocate(uint8_t *Buf, uint8_t *BufEnd, RelIteratorRange<isRela> Rels);
+
+private:
+  template <bool isRela>
+  uint8_t *findMipsPairedReloc(uint8_t *Buf, uint32_t Type,
+                               RelIteratorRange<isRela> Rels);
 };
 
 template <class ELFT>
 InputSectionBase<ELFT>
     InputSectionBase<ELFT>::Discarded(nullptr, nullptr,
                                       InputSectionBase<ELFT>::Regular);
 
 template <class ELFT> class SplitInputSection : public InputSectionBase<ELFT> {

lld/trunk/ELF/InputSection.cpp

 
 template <class ELFT>
 bool InputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
   return S->SectionKind == Base::Regular;
 }
 
 template <class ELFT>
 template <bool isRela>
-void InputSectionBase<ELFT>::relocate(
-    uint8_t *Buf, uint8_t *BufEnd,
-    iterator_range<const Elf_Rel_Impl<ELFT, isRela> *> Rels) {
+uint8_t *
+InputSectionBase<ELFT>::findMipsPairedReloc(uint8_t *Buf, uint32_t Type,
+                                            RelIteratorRange<isRela> Rels) {
+  // Some MIPS relocations use addend calculated from addend of the relocation
+  // itself and addend of paired relocation. ABI requires to compute such
+  // combined addend in case of REL relocation record format only.
+  // See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
+  if (isRela || Config->EMachine != EM_MIPS)
+    return nullptr;
+  if (Type == R_MIPS_HI16)
+    Type = R_MIPS_LO16;
+  else if (Type == R_MIPS_PCHI16)
+    Type = R_MIPS_PCLO16;
+  else if (Type == R_MICROMIPS_HI16)
+    Type = R_MICROMIPS_LO16;
+  else
+    return nullptr;
+  for (const auto &RI : Rels) {
+    if (RI.getType(Config->Mips64EL) != Type)
+      continue;
+    uintX_t Offset = getOffset(RI.r_offset);
+    if (Offset == (uintX_t)-1)
+      return nullptr;
+    return Buf + Offset;
+  }
+  return nullptr;
+}
+
+template <class ELFT>
+template <bool isRela>
+void InputSectionBase<ELFT>::relocate(uint8_t *Buf, uint8_t *BufEnd,
+                                      RelIteratorRange<isRela> Rels) {
   typedef Elf_Rel_Impl<ELFT, isRela> RelType;
   size_t Num = Rels.end() - Rels.begin();
   for (size_t I = 0; I < Num; ++I) {
     const RelType &RI = *(Rels.begin() + I);
     uint32_t SymIndex = RI.getSymbol(Config->Mips64EL);
     uint32_t Type = RI.getType(Config->Mips64EL);
     uintX_t Offset = getOffset(RI.r_offset);
     if (Offset == (uintX_t)-1)
       continue;
 
     uint8_t *BufLoc = Buf + Offset;
     uintX_t AddrLoc = OutSec->getVA() + Offset;
+    auto NextRelocs = llvm::make_range(&RI, Rels.end());
 
     if (Target->isTlsLocalDynamicReloc(Type) &&
         !Target->isTlsOptimized(Type, nullptr)) {
       Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc,
                           Out<ELFT>::Got->getLocalTlsIndexVA() +
                               getAddend<ELFT>(RI));
       continue;
     }
 
     // Handle relocations for local symbols -- they never get
     // resolved so we don't allocate a SymbolBody.
     const Elf_Shdr *SymTab = File->getSymbolTable();
     if (SymIndex < SymTab->sh_info) {
       uintX_t SymVA = getLocalRelTarget(*File, RI);
-      Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc, SymVA);
+      Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc, SymVA,
+                          findMipsPairedReloc(Buf, Type, NextRelocs));
       continue;
     }
 
     SymbolBody &Body = *File->getSymbolBody(SymIndex)->repl();
 
     if (Target->isTlsGlobalDynamicReloc(Type) &&
         !Target->isTlsOptimized(Type, &Body)) {
       Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc,
if (Target->relocNeedsPlt(Type, Body)) {
         Type = Target->getTlsGotReloc();
     } else if (!Target->relocNeedsCopy(Type, Body) &&
                isa<SharedSymbol<ELFT>>(Body)) {
       continue;
     } else if (Target->isTlsDynReloc(Type)) {
       continue;
     }
     Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc,
-                        SymVA + getAddend<ELFT>(RI));
+                        SymVA + getAddend<ELFT>(RI),
+                        findMipsPairedReloc(Buf, Type, NextRelocs));
   }
 }
 
 template <class ELFT> void InputSection<ELFT>::writeTo(uint8_t *Buf) {
   if (this->Header->sh_type == SHT_NOBITS)
     return;
   // Copy section contents from source object file to output file.
   ArrayRef<uint8_t> Data = this->getSectionData();

lld/trunk/ELF/Target.h

public:
   virtual void writePltEntry(uint8_t *Buf, uint64_t GotAddr,
                              uint64_t GotEntryAddr, uint64_t PltEntryAddr,
                              int32_t Index, unsigned RelOff) const = 0;
   virtual bool isRelRelative(uint32_t Type) const;
   virtual bool relocNeedsCopy(uint32_t Type, const SymbolBody &S) const;
   virtual bool relocNeedsGot(uint32_t Type, const SymbolBody &S) const = 0;
   virtual bool relocNeedsPlt(uint32_t Type, const SymbolBody &S) const = 0;
   virtual void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type,
-                           uint64_t P, uint64_t SA) const = 0;
+                           uint64_t P, uint64_t SA,
+                           uint8_t *PairedLoc = nullptr) const = 0;
   virtual bool isTlsOptimized(unsigned Type, const SymbolBody *S) const;
   virtual unsigned relocateTlsOptimize(uint8_t *Loc, uint8_t *BufEnd,
                                        uint32_t Type, uint64_t P,
                                        uint64_t SA) const;
   virtual ~TargetInfo();
 
 protected:
   unsigned PageSize = 4096;

lld/trunk/ELF/Target.cpp

void writePltZeroEntry(uint8_t *Buf, uint64_t GotEntryAddr,
                          uint64_t PltEntryAddr) const override;
   void writePltEntry(uint8_t *Buf, uint64_t GotAddr, uint64_t GotEntryAddr,
                      uint64_t PltEntryAddr, int32_t Index,
                      unsigned RelOff) const override;
   bool relocNeedsCopy(uint32_t Type, const SymbolBody &S) const override;
   bool relocNeedsGot(uint32_t Type, const SymbolBody &S) const override;
   bool relocNeedsPlt(uint32_t Type, const SymbolBody &S) const override;
   void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type, uint64_t P,
-                   uint64_t SA) const override;
+                   uint64_t SA, uint8_t *PairedLoc = nullptr) const override;
 };
 
 class X86_64TargetInfo final : public TargetInfo {
 public:
   X86_64TargetInfo();
   unsigned getPltRefReloc(unsigned Type) const override;
   bool isTlsDynReloc(unsigned Type) const override;
   void writeGotPltHeaderEntries(uint8_t *Buf) const override;
   void writeGotPltEntry(uint8_t *Buf, uint64_t Plt) const override;
   void writePltZeroEntry(uint8_t *Buf, uint64_t GotEntryAddr,
                          uint64_t PltEntryAddr) const override;
   void writePltEntry(uint8_t *Buf, uint64_t GotAddr, uint64_t GotEntryAddr,
                      uint64_t PltEntryAddr, int32_t Index,
                      unsigned RelOff) const override;
   bool relocNeedsCopy(uint32_t Type, const SymbolBody &S) const override;
   bool relocNeedsGot(uint32_t Type, const SymbolBody &S) const override;
   bool relocNeedsPlt(uint32_t Type, const SymbolBody &S) const override;
   void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type, uint64_t P,
-                   uint64_t SA) const override;
+                   uint64_t SA, uint8_t *PairedLoc = nullptr) const override;
   bool isRelRelative(uint32_t Type) const override;
   bool isTlsOptimized(unsigned Type, const SymbolBody *S) const override;
   unsigned relocateTlsOptimize(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type,
                                uint64_t P, uint64_t SA) const override;
 
 private:
   void relocateTlsLdToLe(uint8_t *Loc, uint8_t *BufEnd, uint64_t P,
                          uint64_t SA) const;
public:
   void writePltZeroEntry(uint8_t *Buf, uint64_t GotEntryAddr,
                          uint64_t PltEntryAddr) const override;
   void writePltEntry(uint8_t *Buf, uint64_t GotAddr, uint64_t GotEntryAddr,
                      uint64_t PltEntryAddr, int32_t Index,
                      unsigned RelOff) const override;
   bool relocNeedsGot(uint32_t Type, const SymbolBody &S) const override;
   bool relocNeedsPlt(uint32_t Type, const SymbolBody &S) const override;
   void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type, uint64_t P,
-                   uint64_t SA) const override;
+                   uint64_t SA, uint8_t *PairedLoc = nullptr) const override;
   bool isRelRelative(uint32_t Type) const override;
 };
 
 class AArch64TargetInfo final : public TargetInfo {
 public:
   AArch64TargetInfo();
   unsigned getPltRefReloc(unsigned Type) const override;
   void writeGotPltEntry(uint8_t *Buf, uint64_t Plt) const override;
   void writePltZeroEntry(uint8_t *Buf, uint64_t GotEntryAddr,
                          uint64_t PltEntryAddr) const override;
   void writePltEntry(uint8_t *Buf, uint64_t GotAddr, uint64_t GotEntryAddr,
                      uint64_t PltEntryAddr, int32_t Index,
                      unsigned RelOff) const override;
   bool relocNeedsGot(uint32_t Type, const SymbolBody &S) const override;
   bool relocNeedsPlt(uint32_t Type, const SymbolBody &S) const override;
   void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type, uint64_t P,
-                   uint64_t SA) const override;
+                   uint64_t SA, uint8_t *PairedLoc = nullptr) const override;
 };
 
 template <class ELFT> class MipsTargetInfo final : public TargetInfo {
 public:
   MipsTargetInfo();
   void writeGotHeaderEntries(uint8_t *Buf) const override;
   void writeGotPltEntry(uint8_t *Buf, uint64_t Plt) const override;
   void writePltZeroEntry(uint8_t *Buf, uint64_t GotEntryAddr,
                          uint64_t PltEntryAddr) const override;
   void writePltEntry(uint8_t *Buf, uint64_t GotAddr, uint64_t GotEntryAddr,
                      uint64_t PltEntryAddr, int32_t Index,
                      unsigned RelOff) const override;
   bool relocNeedsGot(uint32_t Type, const SymbolBody &S) const override;
   bool relocNeedsPlt(uint32_t Type, const SymbolBody &S) const override;
   void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type, uint64_t P,
-                   uint64_t SA) const override;
+                   uint64_t SA, uint8_t *PairedLoc = nullptr) const override;
 };
 } // anonymous namespace
 
 TargetInfo *createTarget() {
   switch (Config->EMachine) {
   case EM_386:
     return new X86TargetInfo();
   case EM_AARCH64:
bool X86TargetInfo::relocNeedsGot(uint32_t Type, const SymbolBody &S) const {
   return Type == R_386_GOT32 || relocNeedsPlt(Type, S);
 }
 
 bool X86TargetInfo::relocNeedsPlt(uint32_t Type, const SymbolBody &S) const {
   return Type == R_386_PLT32 || (Type == R_386_PC32 && S.isShared());
 }
 
 void X86TargetInfo::relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type,
-                                uint64_t P, uint64_t SA) const {
+                                uint64_t P, uint64_t SA,
+                                uint8_t *PairedLoc) const {
   switch (Type) {
   case R_386_32:
     add32le(Loc, SA);
     break;
   case R_386_GOT32:
     add32le(Loc, SA - Out<ELF32LE>::Got->getVA());
     break;
   case R_386_GOTPC:
case R_X86_64_TLSLD:
     relocateTlsLdToLe(Loc, BufEnd, P, SA);
     // The next relocation should be against __tls_get_addr, so skip it
     return 1;
   }
   llvm_unreachable("Unknown TLS optimization");
 }
 
 void X86_64TargetInfo::relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type,
-                                   uint64_t P, uint64_t SA) const {
+                                   uint64_t P, uint64_t SA,
+                                   uint8_t *PairedLoc) const {
   switch (Type) {
   case R_X86_64_32:
     checkUInt<32>(SA, Type);
     write32le(Loc, SA);
     break;
   case R_X86_64_32S:
     checkInt<32>(SA, Type);
     write32le(Loc, SA);
default:
     return true;
   case R_PPC64_ADDR64:
   case R_PPC64_TOC:
     return false;
   }
 }
 
 void PPC64TargetInfo::relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type,
-                                  uint64_t P, uint64_t SA) const {
+                                  uint64_t P, uint64_t SA,
+                                  uint8_t *PairedLoc) const {
   uint64_t TB = getPPC64TocBase();
 
   // For a TOC-relative relocation, adjust the addend and proceed in terms of
   // the corresponding ADDR16 relocation type.
   switch (Type) {
   case R_PPC64_TOC16:       Type = R_PPC64_ADDR16;       SA -= TB; break;
   case R_PPC64_TOC16_DS:    Type = R_PPC64_ADDR16_DS;    SA -= TB; break;
   case R_PPC64_TOC16_HA:    Type = R_PPC64_ADDR16_HA;    SA -= TB; break;

 // Page(Expr) is the page address of the expression Expr, defined
 // as (Expr & ~0xFFF). (This applies even if the machine page size
 // supported by the platform has a different value.)
 static uint64_t getAArch64Page(uint64_t Expr) {
   return Expr & (~static_cast<uint64_t>(0xFFF));
 }
 
 void AArch64TargetInfo::relocateOne(uint8_t *Loc, uint8_t *BufEnd,
-                                    uint32_t Type, uint64_t P,
-                                    uint64_t SA) const {
+                                    uint32_t Type, uint64_t P, uint64_t SA,
+                                    uint8_t *PairedLoc) const {
   switch (Type) {
   case R_AARCH64_ABS16:
     checkIntUInt<16>(SA, Type);
     write16le(Loc, SA);
     break;
   case R_AARCH64_ABS32:
     checkIntUInt<32>(SA, Type);
     write32le(Loc, SA);

 template <class ELFT>
 bool MipsTargetInfo<ELFT>::relocNeedsPlt(uint32_t Type,
                                          const SymbolBody &S) const {
   return false;
 }
 
 template <class ELFT>
 void MipsTargetInfo<ELFT>::relocateOne(uint8_t *Loc, uint8_t *BufEnd,
-                                       uint32_t Type, uint64_t P,
-                                       uint64_t SA) const {
+                                       uint32_t Type, uint64_t P, uint64_t SA,
+                                       uint8_t *PairedLoc) const {
   const endianness E = ELFT::TargetEndianness;
   switch (Type) {
   case R_MIPS_32:
     add32<E>(Loc, SA);
     break;
+  case R_MIPS_HI16: {
+    uint32_t Instr = read32<E>(Loc);
+    if (PairedLoc) {
+      uint64_t AHL = ((Instr & 0xffff) << 16) +
+                     llvm::SignExtend64<16>(read32<E>(PairedLoc) & 0xffff);
+      write32<E>(Loc, (Instr & 0xffff0000) | (((SA + AHL) >> 16) & 0xffff));
+    } else {
+      warning("Can't find matching R_MIPS_LO16 relocation for R_MIPS_HI16");
+      write32<E>(Loc, (Instr & 0xffff0000) | ((SA >> 16) & 0xffff));
+    }
+    break;
+  }
+  case R_MIPS_LO16: {
+    uint32_t Instr = read32<E>(Loc);
+    int64_t AHL = llvm::SignExtend64<16>(Instr & 0xffff);
+    write32<E>(Loc, (Instr & 0xffff0000) | ((SA + AHL) & 0xffff));
+    break;
+  }
   case R_MIPS_CALL16:
   case R_MIPS_GOT16: {
     int64_t V = SA - getMipsGpAddr<ELFT>();
     if (Type == R_MIPS_GOT16)
       checkInt<16>(V, Type);
     write32<E>(Loc, (read32<E>(Loc) & 0xffff0000) | (V & 0xffff));
     break;
   }

lld/trunk/test/ELF/mips-hilo-hi-only.s

+# Check warning on orphaned R_MIPS_HI16 relocations.
+
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux %s -o %t.o
+# RUN: ld.lld %t.o -o %t.exe 2>&1 | FileCheck -check-prefix=WARN %s
+# RUN: llvm-objdump -d -t %t.exe | FileCheck %s
+
+# REQUIRES: mips
+
+  .text
+  .globl  __start
+__start:
+  lui    $t0,%hi(__start+0x10000)
+
+# WARN: Can't find matching R_MIPS_LO16 relocation for R_MIPS_HI16
+
+# CHECK:      Disassembly of section .text:
+# CHECK-NEXT: __start:
+# CHECK-NEXT:  20000:   3c 08 00 02   lui    $8, 2
+#                                                ^-- %hi(__start) w/o addend
+
+# CHECK: SYMBOL TABLE:
+# CHECK: 0020000     .text   00000000 __start

lld/trunk/test/ELF/mips-hilo.s

+# Check R_MIPS_HI16 / LO16 relocations calculation.
+
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux %s -o %t.o
+# RUN: ld.lld %t.o -o %t.exe
+# RUN: llvm-objdump -d -t %t.exe | FileCheck %s
+
+# REQUIRES: mips
+
+  .text
+  .globl  __start
+__start:
+  lui    $t0,%hi(__start)
+  lui    $t1,%hi(g1)
+  addi   $t0,$t0,%lo(__start+4)
+  addi   $t0,$t0,%lo(g1+8)
+
+  lui    $t0,%hi(l1+0x10000)
+  lui    $t1,%hi(l1+0x20000)
+  addi   $t0,$t0,%lo(l1+(-4))
+
+  .data
+  .type  l1,@object
+  .size  l1,4
+l1:
+  .word 0
+
+  .globl g1
+  .type  g1,@object
+  .size  g1,4
+g1:
+  .word 0
+
+# CHECK:      Disassembly of section .text:
+# CHECK-NEXT: __start:
+# CHECK-NEXT:  20000:   3c 08 00 02   lui    $8, 2
+#                                                ^-- %hi(__start+4)
+# CHECK-NEXT:  20004:   3c 09 00 03   lui    $9, 3
+#                                                ^-- %hi(g1+8)
+# CHECK-NEXT:  20008:   21 08 00 04   addi   $8, $8, 4
+#                                                    ^-- %lo(__start+4)
+# CHECK-NEXT:  2000c:   21 08 00 0c   addi   $8, $8, 12
+#                                                    ^-- %lo(g1+8)
+# CHECK-NEXT:  20010:   3c 08 00 03   lui    $8, 3
+#                                                ^-- %hi(l1+0x10000-4)
+# CHECK-NEXT:  20014:   3c 09 00 04   lui    $9, 4
+#                                                ^-- %hi(l1+0x20000-4)
+# CHECK-NEXT:  20018:   21 08 ff fc   addi   $8, $8, -4
+#                                                    ^-- %lo(l1-4)
+
+# CHECK: SYMBOL TABLE:
+# CHECK: 0030000 l   .data   00000004 l1
+# CHECK: 0020000     .text   00000000 __start
+# CHECK: 0030004 g   .data   00000004 g1