[BOLT][RISCV] Add support for linker relaxation

[jobnoorman]

Summary

Calls on RISC-V are typically compiled to auipc/jalr pairs to allow
a maximum target range (32-bit pc-relative). In order to optimize calls
to near targets, linker relaxation may replace those pairs with, for
example, single jal instructions.

To allow BOLT to freely reassign function addresses in relaxed binaries,
this patch proposes the following approach:

• Expand all relaxed calls back to auipc/jalr;
• Rely on JITLink to relax those back to shorter forms where possible.

This is implemented by detecting all possible call instructions and
replacing them with PseudoCALL (or PseudoTAIL) instructions. The
RISC-V backend then expands those and adds the necessary relocations for
relaxation.

Since BOLT generally ignores pseudo instruction, this patch makes
MCPlusBuilder::isPseudo virtual so that RISCVMCPlusBuilder can
override it to exclude PseudoCALL and PseudoTAIL.

To ensure JITLink knows about the correct section addresses while
relaxing, reassignment of addresses has been moved to a post-allocation
pass. Note that this is probably the time it had to be done in the
first place since in notifyResolved (where it was done before), all
symbols are supposed to be resolved already.

Depends on D159082

[jobnoorman]

Note that since this relies on a fix in lld (D159082), this patch will probably cause CI problems again (since the system's clang is used there).

[jobnoorman]

Ping.

[Amir]

In D159089#4624694, @jobnoorman wrote:

Note that since this relies on a fix in lld (D159082), this patch will probably cause CI problems again (since the system's clang is used there).

Pre-merge checks here and in GitHub PRs use trunk lld [1], so if you replace clang with lld in test then it should pass.

[1]: https://buildkite.com/llvm-project/phabricator-run-tests/builds/173788#018a4173-32e6-4d74-9871-6c0bff371c9c/117-120

bolt/test/RISCV/relax.s

2

[jobnoorman]

Use llvm-mc+ld.lld instead of clang.

[jobnoorman]

In D159089#4645382, @Amir wrote:

In D159089#4624694, @jobnoorman wrote:

Note that since this relies on a fix in lld (D159082), this patch will probably cause CI problems again (since the system's clang is used there).

Pre-merge checks here and in GitHub PRs use trunk lld [1], so if you replace clang with lld in test then it should pass.

Thanks @Amir, I completely missed that.

[maksfb]

Thanks for the patch, Job! Do you know what's the effect of changing the reassignSectionAddress() invocation on other platforms? Everything else LGTM.

[jobnoorman]

In D159089#4646164, @maksfb wrote:

Thanks for the patch, Job! Do you know what's the effect of changing the reassignSectionAddress() invocation on other platforms? Everything else LGTM.

It shouldn't have any effect on other platforms. The change will call reassignSectionAddress() a bit earlier in the JITLink pipeline (notifyResolved is called right after running the PostAllocationPasses, see this) but this shouldn't matter from BOLT's perspective.

Just to be sure, I'll run llvm-bolt-wrapper in the morning to verify (I'm pretty sure I already did this but it has been a while).

[maksfb]

Awesome. Let me also check this change internally just in case.

[yota9]

It seems to be that on some of the buildbots the test is failing for some reason e.g. https://lab.llvm.org/buildbot/#/builders/221/builds/19162/steps/8/logs/FAIL__BOLT__relax_s

[jobnoorman]

In D159089#4653401, @yota9 wrote:

It seems to be that on some of the buildbots the test is failing for some reason e.g. https://lab.llvm.org/buildbot/#/builders/221/builds/19162/steps/8/logs/FAIL__BOLT__relax_s

Welp, that test has been broken for a while it seems... Looks like the first failing commit is c1ce21b450fd9607c3b44acd520f4e449c6a9a89 but I don't see why that could be relevant. Did something else change on the build bot (e.g., clang/lld version?). Do you have a way to reproduce this? (It works locally for me.) If you do, it would be very helpful if you could send me all the intermediary files of that test so that I can try to debug this.

[yota9]

I believe some patches could be tested together, so probably the reason is nearby patch. But I could not help you, probably @Amir might help you more with the investigation. For now I suggest to mark the test as invalid. Probably adding something like "UNRESOLVED: *" might help, I don't think XFAIL could fit since on some of the node the test is passed.

[jobnoorman]

In D159089#4653414, @yota9 wrote:

I believe some patches could be tested together, so probably the reason is nearby patch.

In this case, it really seems to be just one patch: this is the last good build (at 0b0ed8f76a264c3677b8254d8d334de43600568f), this the first bad (at c1ce21b450fd9607c3b44acd520f4e449c6a9a89).

$ git log --oneline 0b0ed8f76a264c3677b8254d8d334de43600568f..c1ce21b450fd9607c3b44acd520f4e449c6a9a89
c1ce21b450fd cmake: allow disabling building with the install name directory

That's why I feel something must have changed on the build bot. fwiw, the issue seems to be that relaxation is not performed properly. So that suggests either an llvm-mc issue (unlikely since it's built from tree and hence should be locally reproducible) or an lld issue (seems more likely since the system one is used in the build bots).

bolt/include/bolt/Core/MCPlusBuilder.h

virtual bool isBranchOnReg(const MCInst &Inst) const {
     llvm_unreachable("not implemented");
     return false;
   }
 
   /// Check whether we support inverting this branch
   virtual bool isUnsupportedBranch(const MCInst &Inst) const { return false; }
 
   /// Return true of the instruction is of pseudo kind.
-  bool isPseudo(const MCInst &Inst) const {
+  virtual bool isPseudo(const MCInst &Inst) const {
     return Info->get(Inst.getOpcode()).isPseudo();
   }
 
   /// Return true if the relocation type needs to be registered in the function.
   /// These code relocations are used in disassembly to better understand code.
   ///
   /// For ARM, they help us decode instruction operands unambiguously, but
   /// sometimes we might discard them because we already have the necessary

bolt/include/bolt/Passes/FixRISCVCallsPass.h

 //===- bolt/Passes/FixRISCVCallsPass.h --------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// This file declares the FixRISCVCallsPass class, which sets the JALR immediate
-// to 0 for AUIPC/JALR pairs with a R_RISCV_CALL(_PLT) relocation. This is
-// necessary since MC expects it to be zero in order to or-in fixups.
+// This file declares the FixRISCVCallsPass class, which replaces all types of
+// calls with PseudoCALL pseudo instructions. This ensures that relaxed calls
+// get expanded to auipc/jalr pairs so that BOLT can freely reassign function
+// addresses without having to worry about the limited range of relaxed calls.
+// Using PseudoCALL also ensures that the RISC-V backend inserts the necessary
+// relaxation-related relocations to allow JITLink to relax instruction back to
+// shorter versions where possible.
 //===----------------------------------------------------------------------===//
 
 #ifndef BOLT_PASSES_FIXRISCVCALLSPASS_H
 #define BOLT_PASSES_FIXRISCVCALLSPASS_H
 
 #include "bolt/Passes/BinaryPasses.h"
 
 namespace llvm {

bolt/lib/Core/BinaryContext.cpp

case llvm::Triple::x86_64:
     break;
   case llvm::Triple::aarch64:
     ArchName = "aarch64";
     FeaturesStr = "+all";
     break;
   case llvm::Triple::riscv64:
     ArchName = "riscv64";
     // RV64GC
-    FeaturesStr = "+m,+a,+f,+d,+zicsr,+zifencei,+c";
+    FeaturesStr = "+m,+a,+f,+d,+zicsr,+zifencei,+c,+relax";
     break;
   default:
     return createStringError(std::errc::not_supported,
                              "BOLT-ERROR: Unrecognized machine in ELF file");
   }
 
   auto TheTriple = std::make_unique<Triple>(File->makeTriple());
   const std::string TripleName = TheTriple->str();

bolt/lib/Passes/FixRISCVCallsPass.cpp

 #include "bolt/Passes/FixRISCVCallsPass.h"
 #include "bolt/Core/ParallelUtilities.h"
 
 #include <iterator>
 
 using namespace llvm;
 
 namespace llvm {
 namespace bolt {
 
 void FixRISCVCallsPass::runOnFunction(BinaryFunction &BF) {
   auto &BC = BF.getBinaryContext();
+  auto &MIB = BC.MIB;
+  auto *Ctx = BC.Ctx.get();
 
   for (auto &BB : BF) {
-    for (auto II = BB.begin(), IE = BB.end(); II != IE; ++II) {
+    for (auto II = BB.begin(); II != BB.end();) {
+      if (MIB->isCall(*II) && !MIB->isIndirectCall(*II)) {
+        auto *Target = MIB->getTargetSymbol(*II);
+        assert(Target && "Cannot find call target");
+
+        auto L = BC.scopeLock();
+
+        if (MIB->isTailCall(*II))
+          MIB->createTailCall(*II, Target, Ctx);
+        else
+          MIB->createCall(*II, Target, Ctx);
+
+        ++II;
+        continue;
+      }
+
       auto NextII = std::next(II);
 
-      if (NextII == IE)
+      if (NextII == BB.end())
         break;
 
-      if (!BC.MIB->isRISCVCall(*II, *NextII))
-        continue;
+      if (MIB->isRISCVCall(*II, *NextII)) {
+        auto *Target = MIB->getTargetSymbol(*II);
+        assert(Target && "Cannot find call target");
 
         auto L = BC.scopeLock();
+        MIB->createCall(*II, Target, Ctx);
+        II = BB.eraseInstruction(NextII);
+        continue;
+      }
 
-      // The MC layer handles R_RISCV_CALL_PLT but assumes that the immediate
-      // in the JALR is zero (fixups are or'ed into instructions). Note that
-      // NextII is guaranteed to point to a JALR by isRISCVCall.
-      NextII->getOperand(2).setImm(0);
+      ++II;
     }
   }
 }
 
 void FixRISCVCallsPass::runOnFunctions(BinaryContext &BC) {
   if (!BC.isRISCV() || !BC.HasRelocations)
     return;
 

bolt/lib/Rewrite/JITLinkLinker.cpp

 //===- bolt/Rewrite/JITLinkLinker.cpp - BOLTLinker using JITLink ----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "bolt/Rewrite/JITLinkLinker.h"
 #include "bolt/Core/BinaryData.h"
 #include "bolt/Rewrite/RewriteInstance.h"
+#include "llvm/ExecutionEngine/JITLink/ELF_riscv.h"
 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
 #include "llvm/ExecutionEngine/Orc/Shared/ExecutorAddress.h"
 #include "llvm/ExecutionEngine/Orc/Shared/ExecutorSymbolDef.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "bolt"
 
 namespace llvm {
bool shouldAddDefaultTargetPasses(const Triple &TT) const override {
     // TODO check if we can actually use these passes to remove some of the
     // DWARF manipulation done in BOLT.
     return false;
   }
 
   Error modifyPassConfig(jitlink::LinkGraph &G,
                          jitlink::PassConfiguration &Config) override {
     Config.PrePrunePasses.push_back(markSectionsLive);
+    Config.PostAllocationPasses.push_back([this](auto &G) {
+      MapSections([&G](const BinarySection &Section, uint64_t Address) {
+        reassignSectionAddress(G, Section, Address);
+      });
+      return Error::success();
+    });
+
+    if (G.getTargetTriple().isRISCV()) {
+      Config.PostAllocationPasses.push_back(
+          jitlink::createRelaxationPass_ELF_riscv());
+    }
+
     return Error::success();
   }
 
   void notifyFailed(Error Err) override {
     errs() << "BOLT-ERROR: JITLink failed: " << Err << '\n';
     exit(1);
   }
 
for (const auto &Symbol : Symbols) {
       AllResults[Symbol.first] =
           orc::ExecutorSymbolDef(orc::ExecutorAddr(0), JITSymbolFlags());
     }
 
     LC->run(std::move(AllResults));
   }
 
   Error notifyResolved(jitlink::LinkGraph &G) override {
-    MapSections([&G](const BinarySection &Section, uint64_t Address) {
-      reassignSectionAddress(G, Section, Address);
-    });
-
     for (auto *Symbol : G.defined_symbols()) {
       SymbolInfo Info{Symbol->getAddress().getValue(), Symbol->getSize()};
       Linker.Symtab.insert({Symbol->getName().str(), Info});
     }
 
     return Error::success();
   }
 

bolt/lib/Target/RISCV/RISCVMCPlusBuilder.cpp

public:
   bool isCNop(const MCInst &Inst) const {
     return Inst.getOpcode() == RISCV::C_NOP;
   }
 
   bool isNoop(const MCInst &Inst) const override {
     return isNop(Inst) || isCNop(Inst);
   }
 
+  bool isPseudo(const MCInst &Inst) const override {
+    switch (Inst.getOpcode()) {
+    default:
+      return MCPlusBuilder::isPseudo(Inst);
+    case RISCV::PseudoCALL:
+    case RISCV::PseudoTAIL:
+      return false;
+    }
+  }
+
+  bool isIndirectCall(const MCInst &Inst) const override {
+    if (!isCall(Inst))
+      return false;
+
+    switch (Inst.getOpcode()) {
+    default:
+      return false;
+    case RISCV::JALR:
+    case RISCV::C_JALR:
+      return true;
+    }
+  }
+
   bool hasPCRelOperand(const MCInst &Inst) const override {
     switch (Inst.getOpcode()) {
     default:
       return false;
     case RISCV::JAL:
     case RISCV::AUIPC:
       return true;
     }
Inst.addOperand(MCOperand::createExpr(
         MCSymbolRefExpr::create(TBB, MCSymbolRefExpr::VK_None, *Ctx)));
     return true;
   }
 
   StringRef getTrapFillValue() const override {
     return StringRef("\0\0\0\0", 4);
   }
 
+  bool createCall(unsigned Opcode, MCInst &Inst, const MCSymbol *Target,
+                  MCContext *Ctx) {
+    Inst.setOpcode(Opcode);
+    Inst.clear();
+    Inst.addOperand(MCOperand::createExpr(RISCVMCExpr::create(
+        MCSymbolRefExpr::create(Target, MCSymbolRefExpr::VK_None, *Ctx),
+        RISCVMCExpr::VK_RISCV_CALL, *Ctx)));
+    return true;
+  }
+
+  bool createCall(MCInst &Inst, const MCSymbol *Target,
+                  MCContext *Ctx) override {
+    return createCall(RISCV::PseudoCALL, Inst, Target, Ctx);
+  }
+
+  bool createTailCall(MCInst &Inst, const MCSymbol *Target,
+                      MCContext *Ctx) override {
+    return createCall(RISCV::PseudoTAIL, Inst, Target, Ctx);
+  }
+
   bool analyzeBranch(InstructionIterator Begin, InstructionIterator End,
                      const MCSymbol *&TBB, const MCSymbol *&FBB,
                      MCInst *&CondBranch,
                      MCInst *&UncondBranch) const override {
     auto I = End;
 
     while (I != Begin) {
       --I;
public:
 
   bool getSymbolRefOperandNum(const MCInst &Inst, unsigned &OpNum) const {
     switch (Inst.getOpcode()) {
     default:
       return false;
     case RISCV::C_J:
       OpNum = 0;
       return true;
+    case RISCV::AUIPC:
     case RISCV::JAL:
     case RISCV::C_BEQZ:
     case RISCV::C_BNEZ:
       OpNum = 1;
       return true;
     case RISCV::BEQ:
     case RISCV::BGE:
     case RISCV::BGEU:
const MCSymbol *getTargetSymbol(const MCInst &Inst,
                                   unsigned OpNum = 0) const override {
     if (!OpNum && !getSymbolRefOperandNum(Inst, OpNum))
       return nullptr;
 
     const MCOperand &Op = Inst.getOperand(OpNum);
     if (!Op.isExpr())
       return nullptr;
 
-    return MCPlusBuilder::getTargetSymbol(Op.getExpr());
+    return getTargetSymbol(Op.getExpr());
   }
 
   bool lowerTailCall(MCInst &Inst) override {
     removeAnnotation(Inst, MCPlus::MCAnnotation::kTailCall);
     if (getConditionalTailCall(Inst))
       unsetConditionalTailCall(Inst);
     return true;
   }

bolt/test/RISCV/internal-func-reloc.s

 1:
   j 1b
   .size _start, .-_start
 
   .globl f
   .p2align 1
 // CHECK: <f>:
 // CHECK-NEXT: auipc a0, 0
-// CHECK-NEXT: addi a0, a0, 12
+// CHECK-NEXT: addi a0, a0, 64
 f:
   nop
 1:
   /// Same as "la a0, g" but more explicit
   auipc a0, %pcrel_hi(g)
   addi  a0, a0, %pcrel_lo(1b)
   ret
   .size f, .-f
 
   .globl g
   .p2align 1
 g:
   ret
   .size g, .-g

bolt/test/RISCV/lit.local.cfg

 if 'RISCV' not in config.root.targets:
     config.unsupported = True
 
-flags = '--target=riscv64 -nostdlib -ffreestanding -Wl,--no-relax,--emit-relocs'
+flags = '--target=riscv64 -nostdlib -ffreestanding -Wl,--emit-relocs'
 
 config.substitutions.insert(0, ('%cflags', f'%cflags {flags}'))
 config.substitutions.insert(0, ('%cxxflags', f'%cxxflags {flags}'))

bolt/test/RISCV/relax.s

+// RUN: llvm-mc -triple riscv64 -mattr=+c,+relax -filetype obj -o %t.o %s
+// RUN: ld.lld --emit-relocs -o %t %t.o
+// RUN: llvm-bolt --print-cfg --print-fix-riscv-calls --print-only=_start \
+// RUN:     -o %t.bolt %t | FileCheck %s
+// RUN: llvm-objdump -d %t.bolt | FileCheck --check-prefix=OBJDUMP %s
+
+// CHECK:      Binary Function "_start" after building cfg {
+// CHECK:      jal ra, near_f
+// CHECK-NEXT: auipc ra, far_f@plt
+// CHECK-NEXT: jalr ra, 12(ra)
+// CHECK-NEXT: j near_f
+
+// CHECK:      Binary Function "_start" after fix-riscv-calls {
+// CHECK:      call near_f
+// CHECK-NEXT: call far_f
+// CHECK-NEXT: tail near_f
+
+// OBJDUMP:      0000000000600000 <_start>:
+// OBJDUMP-NEXT:     jal 0x600040 <near_f>
+// OBJDUMP-NEXT:     auipc ra, 512
+// OBJDUMP-NEXT:     jalr 124(ra)
+// OBJDUMP-NEXT:     j 0x600040 <near_f>
+// OBJDUMP:      0000000000600040 <near_f>:
+// OBJDUMP:      0000000000800080 <far_f>:
+
+  .text
+  .globl _start
+  .p2align 1
+_start:
+  call near_f
+  call far_f
+  tail near_f
+  .size _start, .-_start
+
+  .global near_f
+  .p2align 1
+near_f:
+  ret
+  .size near_f, .-near_f
+
+  .skip (1 << 21)
+
+  .global far_f
+  .p2align 1
+far_f:
+  ret
+  .size far_f, .-far_f

bolt/test/RISCV/reloc-call.s

 // RUN: %clang %cflags -o %t %s
 // RUN: llvm-bolt --print-fix-riscv-calls --print-only=_start -o /dev/null %t \
 // RUN:    | FileCheck %s
 
   .text
 
   .global f
   .p2align 1
 f:
   ret
   .size f, .-f
 
 // CHECK: Binary Function "_start" after fix-riscv-calls {
   .globl _start
   .p2align 1
 _start:
-// CHECK: auipc ra, f
-// CHECK-NEXT: jalr ra
+// CHECK: call f
   call f
   ret
   .size _start, .-_start