[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
diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp
index 2b75f8e..6c0bd52 100644
--- a/lld/ELF/InputSection.cpp
+++ b/lld/ELF/InputSection.cpp
@@ -94,9 +94,38 @@
 
 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 @@
 
     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 @@
     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 @@
       continue;
     }
     Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc,
-                        SymVA + getAddend<ELFT>(RI));
+                        SymVA + getAddend<ELFT>(RI),
+                        findMipsPairedReloc(Buf, Type, NextRelocs));
   }
 }