[ELF] MIPS paired R_MIPS_HI16/LO16 relocations support

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.

Differential Revision: http://reviews.llvm.org/D15112

llvm-svn: 254461

6 files changed, 157 insertions, 21 deletions

diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp
index 2b75f8ea5b9..6c0bd5259b0 100644
--- a/lld/ELF/InputSection.cpp
+++ b/lld/ELF/InputSection.cpp
@@ -94,9 +94,38 @@ bool InputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
 
 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) {
@@ -109,6 +138,7 @@ void InputSectionBase<ELFT>::relocate(
 
     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)) {
@@ -123,7 +153,8 @@ void InputSectionBase<ELFT>::relocate(
     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;
     }
 
@@ -161,7 +192,8 @@ void InputSectionBase<ELFT>::relocate(
       continue;
     }
     Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc,
-                        SymVA + getAddend<ELFT>(RI));
+                        SymVA + getAddend<ELFT>(RI),
+                        findMipsPairedReloc(Buf, Type, NextRelocs));
   }
 }
 
diff --git a/lld/ELF/InputSection.h b/lld/ELF/InputSection.h
index 20fb0de5aa8..d72f9f23dd4 100644
--- a/lld/ELF/InputSection.h
+++ b/lld/ELF/InputSection.h
@@ -76,9 +76,16 @@ public:
   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>
diff --git a/lld/ELF/Target.cpp b/lld/ELF/Target.cpp
index fde140c25e1..e32c6901b12 100644
--- a/lld/ELF/Target.cpp
+++ b/lld/ELF/Target.cpp
@@ -87,7 +87,7 @@ public:
   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 {
@@ -106,7 +106,7 @@ public:
   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,
@@ -133,7 +133,7 @@ public:
   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;
 };
 
@@ -150,7 +150,7 @@ public:
   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 {
@@ -166,7 +166,7 @@ public:
   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
 
@@ -308,7 +308,8 @@ bool X86TargetInfo::relocNeedsPlt(uint32_t Type, const SymbolBody &S) const {
 }
 
 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);
@@ -581,7 +582,8 @@ unsigned X86_64TargetInfo::relocateTlsOptimize(uint8_t *Loc, uint8_t *BufEnd,
 }
 
 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);
@@ -728,7 +730,8 @@ bool PPC64TargetInfo::isRelRelative(uint32_t Type) const {
 }
 
 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
@@ -933,8 +936,8 @@ static uint64_t getAArch64Page(uint64_t Expr) {
 }
 
 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);
@@ -1046,13 +1049,31 @@ bool MipsTargetInfo<ELFT>::relocNeedsPlt(uint32_t Type,
 
 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>();
diff --git a/lld/ELF/Target.h b/lld/ELF/Target.h
index 3abf942102a..f9e8e853937 100644
--- a/lld/ELF/Target.h
+++ b/lld/ELF/Target.h
@@ -57,7 +57,8 @@ public:
   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,
diff --git a/lld/test/ELF/mips-hilo-hi-only.s b/lld/test/ELF/mips-hilo-hi-only.s
new file mode 100644
index 00000000000..e6aad8345aa
--- /dev/null
+++ b/lld/test/ELF/mips-hilo-hi-only.s
@@ -0,0 +1,22 @@
+# 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
diff --git a/lld/test/ELF/mips-hilo.s b/lld/test/ELF/mips-hilo.s
new file mode 100644
index 00000000000..51a5a5084e0
--- /dev/null
+++ b/lld/test/ELF/mips-hilo.s
@@ -0,0 +1,53 @@
+# 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