[RuntimeDyld] Support more relocations

[rafauler]

Summary

This patch introduces functionality used by BOLT when
re-linking the final binary. It adds new relocation types that
are currently unsupported by RuntimeDyldELF.

[lhames]

LGTM.

Any interest in adding those relocation types to JITLink's ELF/x86-64 backend (llvm/lib/ExecutionEngine/JITLink/ELF_x86_64.cpp)? I'm planning to have LLJIT use JITLink by default for ELF/x86-64 in LLVM 13.

[rafauler]

Sure, let me take a look at that.

[rafauler]

I took a look at JITLink, including the design document, and it doesn't look like it will need to support 8B and 16B relocs. It looks like it was developed to support code generated by LLVM and LLVM will never emit those. According to the x86-64-psABI document:

A program or object file using R_X86_64_8, R_X86_64_16, R_X86_64_PC16 or R_X86_64_PC8 relocations is not conformant to this ABI, these relocations are only added for documentation purposes. The R_X86_64_16, and R_X86_64_8 relocations truncate the computed value to 16-bits resp. 8-bits.

The challenge with a tool like BOLT that consumes arbitrary executables in its input is that it needs to support code from multiple compilers/people and assembly-language programmers can get pretty creative, violating the ABI without realizing they are doing so.

BOLT works by using LLVM's tablegen'd disassembler to read a final binary (already linked), building an IR on top of MCInsts, running transformation passes on it and then using MCStreamer to generate an object file that represents the rearranged binary. At this step, it needs RuntimeDyld to resolve relocations emitted by MCStreamer. That's why we end up using a wider range of relocation types.

If you still think it is valuable, I'll definitely go ahead and add those. If the plan is to deprecate RuntimeDyld for good, let me know too.

[MaskRay]

The R_X86_64_8 range checking is wrong. See D63690.
It also feels wrong to use assert because the relocation overflow can happen and ExecutionEngine should not crash in that case.

LLVM only emits R_X86_64_8 for !absolute_symbol. I think R_X86_64_16 is not used.

[rafauler]

Thanks, MaskRay, I'll fix this

llvm/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

void RuntimeDyldELF::resolveX86_64Relocation(const SectionEntry &Section,
                                              uint32_t Type, int64_t Addend,
                                              uint64_t SymOffset) {
   switch (Type) {
   default:
     report_fatal_error("Relocation type not implemented yet!");
     break;
   case ELF::R_X86_64_NONE:
     break;
+  case ELF::R_X86_64_8: {
+    Value += Addend;
+    assert((int64_t)Value <= INT8_MAX && (int64_t)Value >= INT8_MIN);
+    uint8_t TruncatedAddr = (Value & 0xFF);
+    *Section.getAddressWithOffset(Offset) = TruncatedAddr;
+    LLVM_DEBUG(dbgs() << "Writing " << format("%p", TruncatedAddr) << " at "
+                      << format("%p\n", Section.getAddressWithOffset(Offset)));
+    break;
+  }
+  case ELF::R_X86_64_16: {
+    Value += Addend;
+    assert((int64_t)Value <= INT16_MAX && (int64_t)Value >= INT16_MIN);
+    uint16_t TruncatedAddr = (Value & 0xFFFF);
+    support::ulittle16_t::ref(Section.getAddressWithOffset(Offset)) =
+        TruncatedAddr;
+    LLVM_DEBUG(dbgs() << "Writing " << format("%p", TruncatedAddr) << " at "
+                      << format("%p\n", Section.getAddressWithOffset(Offset)));
+    break;
+  }
   case ELF::R_X86_64_64: {
     support::ulittle64_t::ref(Section.getAddressWithOffset(Offset)) =
         Value + Addend;
     LLVM_DEBUG(dbgs() << "Writing " << format("%p", (Value + Addend)) << " at "
                       << format("%p\n", Section.getAddressWithOffset(Offset)));
     break;
   }
   case ELF::R_X86_64_32:
case ELF::R_AARCH64_PREL32: {
     assert(static_cast<int64_t>(Result) >= INT32_MIN &&
            static_cast<int64_t>(Result) <= UINT32_MAX);
     write(isBE, TargetPtr, static_cast<uint32_t>(Result & 0xffffffffU));
     break;
   }
   case ELF::R_AARCH64_PREL64:
     write(isBE, TargetPtr, Value + Addend - FinalAddress);
     break;
+  case ELF::R_AARCH64_CONDBR19: {
+    uint64_t BranchImm = Value + Addend - FinalAddress;
+
+    assert(isInt<21>(BranchImm));
+    *TargetPtr &= 0xff00001fU;
+    // Immediate:20:2 goes in bits 23:5 of Bcc, CBZ, CBNZ
+    or32le(TargetPtr, (BranchImm & 0x001FFFFC) << 3);
+    break;
+  }
+  case ELF::R_AARCH64_TSTBR14: {
+    uint64_t BranchImm = Value + Addend - FinalAddress;
+
+    assert(isInt<16>(BranchImm));
+
+    *TargetPtr &= 0xfff8001fU;
+    // Immediate:15:2 goes in bits 18:5 of TBZ, TBNZ
+    or32le(TargetPtr, (BranchImm & 0x0FFFFFFC) << 3);
+    break;
+  }
   case ELF::R_AARCH64_CALL26: // fallthrough
   case ELF::R_AARCH64_JUMP26: {
     // Operation: S+A-P. Set Call or B immediate value to bits fff_fffc of the
     // calculation.
     uint64_t BranchImm = Value + Addend - FinalAddress;
 
     // "Check that -2^27 <= result < 2^27".
     assert(isInt<28>(BranchImm));
case ELF::R_AARCH64_LDST64_ABS_LO12_NC:
     or32AArch64Imm(TargetPtr, getBits(Value + Addend, 3, 11));
     break;
   case ELF::R_AARCH64_LDST128_ABS_LO12_NC:
     // Operation: S + A
     // Immediate goes in bits 21:10 of LD/ST instruction, taken
     // from bits 11:4 of X
     or32AArch64Imm(TargetPtr, getBits(Value + Addend, 4, 11));
     break;
+  case ELF::R_AARCH64_LD_PREL_LO19: {
+    // Operation: S + A - P
+    uint64_t Result = Value + Addend - FinalAddress;
+
+    // "Check that -2^20 <= result < 2^20".
+    assert(isInt<21>(Result));
+
+    *TargetPtr &= 0xff00001fU;
+    // Immediate goes in bits 23:5 of LD imm instruction, taken
+    // from bits 20:2 of X
+    *TargetPtr |= ((Result & 0xffc) << (5 - 2));
+    break;
+  }
+  case ELF::R_AARCH64_ADR_PREL_LO21: {
+    // Operation: S + A - P
+    uint64_t Result = Value + Addend - FinalAddress;
+
+    // "Check that -2^20 <= result < 2^20".
+    assert(isInt<21>(Result));
+
+    *TargetPtr &= 0x9f00001fU;
+    // Immediate goes in bits 23:5, 30:29 of ADR imm instruction, taken
+    // from bits 20:0 of X
+    *TargetPtr |= ((Result & 0xffc) << (5 - 2));
+    *TargetPtr |= (Result & 0x3) << 29;
+    break;
+  }
   }
 }
 
 void RuntimeDyldELF::resolveARMRelocation(const SectionEntry &Section,
                                           uint64_t Offset, uint32_t Value,
                                           uint32_t Type, int32_t Addend) {
   // TODO: Add Thumb relocations.
   uint32_t *TargetPtr =