[BOLT] Support PC-relative relocations with addends

[maksfb]

Summary

PC-relative memory operand could reference a different object from
the one located at the target address, e.g. when a negative offset
is used. Check relocations for the real referenced object.

[maksfb]

Update comment.

[ayermolo]

bolt/lib/Core/BinaryFunction.cpp

1359

I think I miss understand something. Why are we subtracting Addend from the Value of relocation? Isn't it S + A - P?
Presumably Relocation.Vaue is the address of the Symbol?

[maksfb]

This comment was removed by maksfb.

[maksfb]

bolt/lib/Core/BinaryFunction.cpp

1359

Value is what the expression S + A - P evaluates to.

[ayermolo]

bolt/lib/Core/BinaryFunction.cpp

1359

Ah, had it backwards in my mind.

[rafauler]

LGTM

[yota9]

bolt/lib/Core/BinaryFunction.cpp

1401

Maybe move this code to smth like replaceMemOperandWithSymbolRef, that will use setOperandToSymbolRef ?

[maksfb]

bolt/lib/Core/BinaryFunction.cpp

1401

That's a reasonable suggestion. However, I'm in the process of refactoring the code to use MCSymbolizer that will render such effort wasteful. The new code will not be replacing the operand but generating the expression in-place.

bolt/include/bolt/Core/BinaryFunction.h

public:
   void addRelocationX86(uint64_t Offset, MCSymbol *Symbol, uint64_t RelType,
                         uint64_t Addend, uint64_t Value) {
     switch (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:
       Relocations[Offset] = Relocation{Offset, Symbol, RelType, Addend, Value};
       return;
-    case ELF::R_X86_64_PC32:
-    case ELF::R_X86_64_PC8:
     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:

bolt/include/bolt/Core/Relocation.h

struct Relocation {
   /// The offset from the \p Symbol base used to compute the final
   /// value of this relocation.
   uint64_t Addend;
 
   /// The computed relocation value extracted from the binary file.
   /// Used to validate relocation correctness.
   uint64_t Value;
 
-  /// Return size of the given relocation \p Type.
+  /// Return size in bytes of the given relocation \p Type.
   static size_t getSizeForType(uint64_t Type);
 
   /// Return size of this relocation.
   size_t getSize() const { return getSizeForType(Type); }
 
   /// Handle special cases when relocation should not be processed by bolt
   static bool skipRelocationProcess(uint64_t Type, uint64_t Contents);
 

bolt/lib/Core/BinaryFunction.cpp

if (MIB->hasEVEXEncoding(Instruction)) {
           errs() << " in function " << *this << '\n';
         }
 
         setIgnored();
         break;
       }
     }
 
-    // Check if there's a relocation associated with this instruction.
-    bool UsedReloc = false;
-    for (auto Itr = Relocations.lower_bound(Offset),
-              ItrE = Relocations.lower_bound(Offset + Size);
-         Itr != ItrE; ++Itr) {
-      const Relocation &Relocation = Itr->second;
-
-      LLVM_DEBUG(dbgs() << "BOLT-DEBUG: replacing immediate 0x"
-                        << Twine::utohexstr(Relocation.Value)
-                        << " with relocation"
-                           " against "
-                        << Relocation.Symbol << "+" << Relocation.Addend
-                        << " in function " << *this
-                        << " for instruction at offset 0x"
-                        << Twine::utohexstr(Offset) << '\n');
-
-      // Process reference to the primary symbol.
-      if (!Relocation.isPCRelative())
-        BC.handleAddressRef(Relocation.Value - Relocation.Addend, *this,
-                            /*IsPCRel*/ false);
-
-      int64_t Value = Relocation.Value;
-      const bool Result = BC.MIB->replaceImmWithSymbolRef(
-          Instruction, Relocation.Symbol, Relocation.Addend, Ctx.get(), Value,
-          Relocation.Type);
-      (void)Result;
-      assert(Result && "cannot replace immediate with relocation");
-
-      // For aarch, if we replaced an immediate with a symbol from a
-      // relocation, we mark it so we do not try to further process a
-      // pc-relative operand. All we need is the symbol.
-      if (BC.isAArch64())
-        UsedReloc = true;
-
-      // Make sure we replaced the correct immediate (instruction
-      // can have multiple immediate operands).
-      if (BC.isX86()) {
-        assert(truncateToSize(static_cast<uint64_t>(Value),
-                              Relocation::getSizeForType(Relocation.Type)) ==
-                   truncateToSize(Relocation.Value, Relocation::getSizeForType(
-                                                        Relocation.Type)) &&
-               "immediate value mismatch in function");
-      }
-    }
-
     if (MIB->isBranch(Instruction) || MIB->isCall(Instruction)) {
       uint64_t TargetAddress = 0;
       if (MIB->evaluateBranch(Instruction, AbsoluteInstrAddr, Size,
                               TargetAddress)) {
         // Check if the target is within the same function. Otherwise it's
         // a call, possibly a tail call.
         //
         // If the target *is* the function address it could be either a branch
if (MIB->isBranch(Instruction) || MIB->isCall(Instruction)) {
           handleIndirectBranch(Instruction, Size, Offset);
         // Indirect call. We only need to fix it if the operand is RIP-relative.
         if (IsSimple && MIB->hasPCRelOperand(Instruction))
           handlePCRelOperand(Instruction, AbsoluteInstrAddr, Size);
 
         if (BC.isAArch64())
           handleAArch64IndirectCall(Instruction, Offset);
       }
-    } else if (MIB->hasPCRelOperand(Instruction) && !UsedReloc) {
+    } else {
+      // Check if there's a relocation associated with this instruction.
+      bool UsedReloc = false;
+      for (auto Itr = Relocations.lower_bound(Offset),
+                ItrE = Relocations.lower_bound(Offset + Size);
+           Itr != ItrE; ++Itr) {
+        const Relocation &Relocation = Itr->second;
+        uint64_t SymbolValue = Relocation.Value - Relocation.Addend;
+        if (Relocation.isPCRelative())
+          SymbolValue += getAddress() + Relocation.Offset;
+
+        // Process reference to the symbol.
+        if (BC.isX86())
+          BC.handleAddressRef(SymbolValue, *this, Relocation.isPCRelative());
+
+        if (BC.isAArch64() || !Relocation.isPCRelative()) {
+          int64_t Value = Relocation.Value;
+          const bool Result = BC.MIB->replaceImmWithSymbolRef(
+              Instruction, Relocation.Symbol, Relocation.Addend, Ctx.get(),
+              Value, Relocation.Type);
+          (void)Result;
+          assert(Result && "cannot replace immediate with relocation");
+
+          if (BC.isX86()) {
+            // Make sure we replaced the correct immediate (instruction
+            // can have multiple immediate operands).
+            assert(
+                truncateToSize(static_cast<uint64_t>(Value),
+                               Relocation::getSizeForType(Relocation.Type)) ==
+                    truncateToSize(Relocation.Value, Relocation::getSizeForType(
+                                                         Relocation.Type)) &&
+                "immediate value mismatch in function");
+          } else if (BC.isAArch64()) {
+            // For aarch, if we replaced an immediate with a symbol from a
+            // relocation, we mark it so we do not try to further process a
+            // pc-relative operand. All we need is the symbol.
+            UsedReloc = true;
+          }
+        } else {
+          // Check if the relocation matches memop's Disp.
+          uint64_t TargetAddress;
+          if (!BC.MIB->evaluateMemOperandTarget(Instruction, TargetAddress,
+                                                AbsoluteInstrAddr, Size)) {
+            errs() << "BOLT-ERROR: PC-relative operand can't be evaluated\n";
+            exit(1);
+          }
+          assert(TargetAddress == Relocation.Value + AbsoluteInstrAddr + Size &&
+                 "Immediate value mismatch detected.");
+
+          const MCExpr *Expr = MCSymbolRefExpr::create(
+              Relocation.Symbol, MCSymbolRefExpr::VK_None, *BC.Ctx);
+          // Real addend for pc-relative targets is adjusted with a delta
+          // from relocation placement to the next instruction.
+          const uint64_t TargetAddend =
+              Relocation.Addend + Offset + Size - Relocation.Offset;
+          if (TargetAddend) {
+            const MCConstantExpr *Offset =
+                MCConstantExpr::create(TargetAddend, *BC.Ctx);
+            Expr = MCBinaryExpr::createAdd(Expr, Offset, *BC.Ctx);
+          }
+          BC.MIB->replaceMemOperandDisp(
+              Instruction, MCOperand::createExpr(BC.MIB->getTargetExprFor(
+                               Instruction, Expr, *BC.Ctx, 0)));
+          UsedReloc = true;
+        }
+      }
+
+      if (MIB->hasPCRelOperand(Instruction) && !UsedReloc)
         handlePCRelOperand(Instruction, AbsoluteInstrAddr, Size);
     }
 
 add_instruction:
     if (getDWARFLineTable()) {
       Instruction.setLoc(findDebugLineInformationForInstructionAt(
           AbsoluteInstrAddr, getDWARFUnit(), getDWARFLineTable()));
     }
 
for (uint64_t Offset = 0; Offset < getSize(); Offset += Size) {
     }
 
     // Create more relocations based on input file relocations.
     bool HasRel = false;
     for (auto Itr = Relocations.lower_bound(Offset),
               ItrE = Relocations.lower_bound(Offset + Size);
          Itr != ItrE; ++Itr) {
       Relocation &Relocation = Itr->second;
+      if (Relocation.isPCRelative() && BC.isX86())
+        continue;
       if (ignoreReference(Relocation.Symbol))
         continue;
 
       int64_t Value = Relocation.Value;
       const bool Result = BC.MIB->replaceImmWithSymbolRef(
           Instruction, Relocation.Symbol, Relocation.Addend,
           Emitter.LocalCtx.get(), Value, Relocation.Type);
       (void)Result;

bolt/lib/Core/Relocation.cpp

case ELF::R_AARCH64_PREL32:
     Value -= PC;
     break;
   }
   return Value;
 }
 
 uint64_t extractValueX86(uint64_t Type, uint64_t Contents, uint64_t PC) {
   if (Type == ELF::R_X86_64_32S)
-    return SignExtend64<32>(Contents & 0xffffffff);
+    return SignExtend64<32>(Contents);
+  if (Relocation::isPCRelative(Type))
+    return SignExtend64(Contents, 8 * Relocation::getSizeForType(Type));
   return Contents;
 }
 
 uint64_t extractValueAArch64(uint64_t Type, uint64_t Contents, uint64_t PC) {
   switch (Type) {
   default:
     errs() << object::getELFRelocationTypeName(ELF::EM_AARCH64, Type) << '\n';
     llvm_unreachable("unsupported relocation type");
bool isPCRelativeX86(uint64_t Type) {
   case ELF::R_X86_64_8:
   case ELF::R_X86_64_TPOFF32:
     return false;
   case ELF::R_X86_64_PC8:
   case ELF::R_X86_64_PC32:
   case ELF::R_X86_64_PC64:
   case ELF::R_X86_64_GOTPCREL:
   case ELF::R_X86_64_PLT32:
+  case ELF::R_X86_64_GOTOFF64:
+  case ELF::R_X86_64_GOTPC32:
   case ELF::R_X86_64_GOTTPOFF:
   case ELF::R_X86_64_GOTPCRELX:
   case ELF::R_X86_64_REX_GOTPCRELX:
     return true;
   }
 }
 
 bool isPCRelativeAArch64(uint64_t Type) {

bolt/lib/Rewrite/RewriteInstance.cpp

if (IsFromCode) {
           outs() << "BOLT-INFO: " << *ContainingBF
                  << " has relocations in padding area\n";
         ContainingBF->setSize(ContainingBF->getMaxSize());
         ContainingBF->setSimple(false);
         continue;
       }
     }
 
+    MCSymbol *ReferencedSymbol = nullptr;
+    if (!IsSectionRelocation) {
+      if (BinaryData *BD = BC->getBinaryDataByName(SymbolName))
+        ReferencedSymbol = BD->getSymbol();
+    }
+
     // PC-relative relocations from data to code are tricky since the original
     // information is typically lost after linking even with '--emit-relocs'.
     // They are normally used by PIC-style jump tables and reference both
     // the jump table and jump destination by computing the difference
     // between the two. If we blindly apply the relocation it will appear
     // that it references an arbitrary location in the code, possibly even
     // in a different function from that containing the jump table.
     if (!IsAArch64 && Relocation::isPCRelative(RType)) {
-      // Just register the fact that we have PC-relative relocation at a given
-      // address. The actual referenced label/address cannot be determined
-      // from linker data alone.
+      // For relocations against non-code sections, just register the fact that
+      // we have a PC-relative relocation at a given address. The actual
+      // referenced label/address cannot be determined from linker data alone.
       if (!IsFromCode)
         BC->addPCRelativeDataRelocation(Rel.getOffset());
-
+      else if (!IsSectionRelocation && ReferencedSymbol)
+        ContainingBF->addRelocation(Rel.getOffset(), ReferencedSymbol, RType,
+                                    Addend, ExtractedValue);
+      else
         LLVM_DEBUG(
             dbgs() << "BOLT-DEBUG: not creating PC-relative relocation at 0x"
                    << Twine::utohexstr(Rel.getOffset()) << " for " << SymbolName
                    << "\n");
       continue;
     }
 
     bool ForceRelocation = BC->forceSymbolRelocations(SymbolName);
     ErrorOr<BinarySection &> RefSection =
         std::make_error_code(std::errc::bad_address);
     if (BC->isAArch64() && Relocation::isGOT(RType)) {
       ForceRelocation = true;
if (IsToCode && ContainingBF && !Relocation::isPCRelative(RType) &&
                     "de-virtualization bug: -1 addend used with "
                     "non-pc-relative relocation against function "
                  << *RogueBF << " in function " << *ContainingBF << '\n';
           continue;
         }
       }
     }
 
-    MCSymbol *ReferencedSymbol = nullptr;
     if (ForceRelocation) {
       std::string Name = Relocation::isGOT(RType) ? "Zero" : SymbolName;
       ReferencedSymbol = BC->registerNameAtAddress(Name, 0, 0, 0);
       SymbolAddress = 0;
       if (Relocation::isGOT(RType))
         Addend = Address;
       LLVM_DEBUG(dbgs() << "BOLT-DEBUG: forcing relocation against symbol "
                         << SymbolName << " with addend " << Addend << '\n');

bolt/test/X86/fptr-addend-pcrel.s

+## Check that BOLT correctly recognizes pc-relative function pointer
+## reference with an addend.
+
+# REQUIRES: system-linux
+
+# RUN: llvm-mc -filetype=obj -triple x86_64-unknown-linux %s -o %t.o
+# RUN: llvm-strip --strip-unneeded %t.o
+# RUN: ld.lld %t.o -o %t.exe -q
+# RUN: llvm-bolt %t.exe -relocs -o /dev/null -print-only=foo -print-disasm \
+# RUN:   | FileCheck %s
+
+  .text
+  .globl _start
+  .type _start,@function
+_start:
+  .cfi_startproc
+  call foo
+  retq
+  .size main, .-main
+  .cfi_endproc
+
+  .globl  foo
+  .type foo,@function
+foo:
+  .cfi_startproc
+
+  leaq  foo-1(%rip), %rax
+## Check that the instruction references foo with a negative addend,
+## not the previous function with a positive addend (_start+X).
+#
+# CHECK: leaq    foo-1(%rip), %rax
+
+  retq
+  .size foo, .-foo
+  .cfi_endproc