[CodeGen] Implement machine optimization and scheduling

1 files changed, 731 insertions, 0 deletions

diff --git a/backend/lib/Target/RISCV/RISCVBranchInfo.cpp b/backend/lib/Target/RISCV/RISCVBranchInfo.cpp
new file mode 100644
index 0000000..18812d8
--- /dev/null
+++ b/backend/lib/Target/RISCV/RISCVBranchInfo.cpp
@@ -0,0 +1,731 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/Target/RISCV/RISCVCodeGen.h"
+#include "rcc/Target/RISCV/RISCVInstructions.h"
+#include "rcc/Target/RISCV/RISCVRegisters.h"
+#include "rcc/Target/RISCV/RISCVTarget.h"
+
+#include <algorithm>
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace rcc::riscv {
+namespace {
+
+constexpr std::uint32_t PCRelativeHighFlag = 2;
+constexpr std::uint32_t PCRelativeLowFlag = 4;
+
+[[nodiscard]] constexpr Opcode targetOpcode(InstructionOpcode Value) noexcept {
+  return Opcode::fromValue(static_cast<std::uint32_t>(Value));
+}
+
+[[nodiscard]] bool isConditionalBranch(Opcode Value) noexcept {
+  return Value == targetOpcode(InstructionOpcode::BEQ) ||
+         Value == targetOpcode(InstructionOpcode::BNE) ||
+         Value == targetOpcode(InstructionOpcode::BLT) ||
+         Value == targetOpcode(InstructionOpcode::BGE) ||
+         Value == targetOpcode(InstructionOpcode::BLTU) ||
+         Value == targetOpcode(InstructionOpcode::BGEU) ||
+         Value == targetOpcode(InstructionOpcode::C_BEQZ) ||
+         Value == targetOpcode(InstructionOpcode::C_BNEZ);
+}
+
+[[nodiscard]] std::optional<Opcode> reversedOpcode(Opcode Value) noexcept {
+  constexpr std::array<std::pair<InstructionOpcode, InstructionOpcode>, 4> Pairs = {{
+      {InstructionOpcode::BEQ, InstructionOpcode::BNE},
+      {InstructionOpcode::BLT, InstructionOpcode::BGE},
+      {InstructionOpcode::BLTU, InstructionOpcode::BGEU},
+      {InstructionOpcode::C_BEQZ, InstructionOpcode::C_BNEZ},
+  }};
+  for (const auto &[Left, Right] : Pairs) {
+    if (Value == targetOpcode(Left))
+      return targetOpcode(Right);
+    if (Value == targetOpcode(Right))
+      return targetOpcode(Left);
+  }
+  return std::nullopt;
+}
+
+[[nodiscard]] bool isZeroRegister(const MachineOperand *Operand) noexcept {
+  const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>();
+  const std::optional<PhysicalRegister> Physical =
+      Reg == nullptr ? std::nullopt : Reg->physicalRegister();
+  return Physical && Physical->number() == static_cast<std::uint32_t>(PhysicalRegisterID::X0);
+}
+
+[[nodiscard]] bool sameRegister(const MachineOperand *Left, const MachineOperand *Right) noexcept {
+  const Register *LeftReg = Left == nullptr ? nullptr : Left->getIf<Register>();
+  const Register *RightReg = Right == nullptr ? nullptr : Right->getIf<Register>();
+  return LeftReg != nullptr && RightReg != nullptr && *LeftReg == *RightReg &&
+         Left->subReg() == Right->subReg();
+}
+
+[[nodiscard]] bool isUnconditionalBranch(const MachineInstr &Instruction) noexcept {
+  if (Instruction.opcode() == targetOpcode(InstructionOpcode::C_J))
+    return true;
+  return Instruction.opcode() == targetOpcode(InstructionOpcode::JAL) &&
+         isZeroRegister(Instruction.operandAt(0));
+}
+
+[[nodiscard]] std::size_t branchTargetIndex(Opcode Value) noexcept {
+  if (Value == targetOpcode(InstructionOpcode::C_J))
+    return 0;
+  if (Value == targetOpcode(InstructionOpcode::C_BEQZ) ||
+      Value == targetOpcode(InstructionOpcode::C_BNEZ)) {
+    return 1;
+  }
+  if (Value == targetOpcode(InstructionOpcode::JAL))
+    return 1;
+  return 2;
+}
+
+[[nodiscard]] Expected<MachineBasicBlock *> directTarget(MachineInstr &Instruction) {
+  if (!isConditionalBranch(Instruction.opcode()) &&
+      Instruction.opcode() != targetOpcode(InstructionOpcode::JAL) &&
+      Instruction.opcode() != targetOpcode(InstructionOpcode::C_J)) {
+    return static_cast<MachineBasicBlock *>(nullptr);
+  }
+  MachineOperand *Operand = Instruction.operandAt(branchTargetIndex(Instruction.opcode()));
+  const BasicBlockOperand *Block =
+      Operand == nullptr ? nullptr : Operand->getIf<BasicBlockOperand>();
+  if (Block == nullptr || Block->Block == nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V direct branch has no basic-block target");
+  }
+  return Block->Block;
+}
+
+[[nodiscard]] Expected<void> setDirectTarget(MachineInstr &Instruction,
+                                             MachineBasicBlock &TargetBlock) {
+  MachineOperand *Operand = Instruction.operandAt(branchTargetIndex(Instruction.opcode()));
+  if (Operand == nullptr || Operand->kind() != MachineOperand::Kind::BasicBlock) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V direct branch has no mutable basic-block target");
+  }
+  return Operand->setBasicBlock(TargetBlock);
+}
+
+[[nodiscard]] Expected<void> removeInstruction(MachineInstr &Instruction) {
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "RISC-V branch instruction is not linked to a block");
+  }
+  return Block->removeInstruction(Instruction);
+}
+
+[[nodiscard]] Expected<PhysicalRegister> physical(PhysicalRegisterID ID) {
+  auto Reg = physicalRegister(ID);
+  if (!Reg)
+    return std::unexpected(Reg.error());
+  return *Reg;
+}
+
+[[nodiscard]] Expected<MachineInstr *>
+buildJAL(MachineFunction &Function, const TargetDescription &Target, MachineBasicBlock &Block,
+         MachineInstr *Before, PhysicalRegister Destination, MachineBasicBlock &TargetBlock) {
+  MachineIRBuilder Builder(Function, Target);
+  Expected<void> Point =
+      Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(targetOpcode(InstructionOpcode::JAL));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto Def = Pending->addDef(Register::fromPhysical(Destination));
+  if (!Def)
+    return std::unexpected(Def.error());
+  auto TargetOperand = Pending->addBasicBlock(TargetBlock);
+  if (!TargetOperand)
+    return std::unexpected(TargetOperand.error());
+  return Pending->build();
+}
+
+[[nodiscard]] Expected<void> copySourceIdentity(const MachineInstr &Source,
+                                                MachineInstr &Destination) {
+  if (Source.sourceLocation())
+    Destination.setSourceLocation(*Source.sourceLocation());
+  if (Source.debugLocation()) {
+    auto Debug = Destination.setDebugLocation(*Source.debugLocation());
+    if (!Debug)
+      return std::unexpected(Debug.error());
+  }
+  if (Source.origin())
+    Destination.setOrigin(*Source.origin());
+  return {};
+}
+
+[[nodiscard]] Expected<void> copyTrailingAnnotations(const MachineInstr &Source,
+                                                     MachineInstr &Destination) {
+  if (Source.debugInstrNumber() != 0) {
+    auto DebugNumber = Destination.setDebugInstrNumber(Source.debugInstrNumber());
+    if (!DebugNumber)
+      return std::unexpected(DebugNumber.error());
+  }
+  if (Source.postInstrSymbol()) {
+    auto Symbol = Destination.setPostInstrSymbol(std::string(*Source.postInstrSymbol()));
+    if (!Symbol)
+      return std::unexpected(Symbol.error());
+  }
+  if (Source.heapAllocMarker()) {
+    auto Marker = Destination.setHeapAllocMarker(*Source.heapAllocMarker());
+    if (!Marker)
+      return std::unexpected(Marker.error());
+  }
+  if (Source.pcSections()) {
+    auto Sections = Destination.setPCSections(*Source.pcSections());
+    if (!Sections)
+      return std::unexpected(Sections.error());
+  }
+  if (Source.mmra()) {
+    auto Metadata = Destination.setMMRA(*Source.mmra());
+    if (!Metadata)
+      return std::unexpected(Metadata.error());
+  }
+  if (Source.cfiType()) {
+    auto Type = Destination.setCFIType(*Source.cfiType());
+    if (!Type)
+      return std::unexpected(Type.error());
+  }
+  if (Source.deactivationSymbol()) {
+    auto Symbol = Destination.setDeactivationSymbol(std::string(*Source.deactivationSymbol()));
+    if (!Symbol)
+      return std::unexpected(Symbol.error());
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> copySingleInstructionAnnotations(const MachineInstr &Source,
+                                                              MachineInstr &Destination) {
+  Destination.setFlags(Source.flags());
+  auto Identity = copySourceIdentity(Source, Destination);
+  if (!Identity)
+    return std::unexpected(Identity.error());
+  if (Source.preInstrSymbol()) {
+    auto Symbol = Destination.setPreInstrSymbol(std::string(*Source.preInstrSymbol()));
+    if (!Symbol)
+      return std::unexpected(Symbol.error());
+  }
+  return copyTrailingAnnotations(Source, Destination);
+}
+
+[[nodiscard]] bool isZeroPhysicalRegister(PhysicalRegister Reg) noexcept {
+  return Reg.number() == static_cast<std::uint32_t>(PhysicalRegisterID::X0);
+}
+
+[[nodiscard]] Expected<PhysicalRegister>
+selectLongBranchScratch(const MachineInstr &Instruction, const MachineBasicBlock &TargetBlock,
+                        const MachineFunction &Function, const TargetDescription &Target) {
+  const MachineOperand *DestinationOperand = Instruction.operandAt(0);
+  const Register *Destination =
+      DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+  const std::optional<PhysicalRegister> DestinationPhysical =
+      Destination == nullptr ? std::nullopt : Destination->physicalRegister();
+  if (!DestinationPhysical) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V long JAL has no physical destination");
+  }
+  if (!isZeroPhysicalRegister(*DestinationPhysical))
+    return *DestinationPhysical;
+
+  const auto GPRClass =
+      RegisterClassID::fromValue(static_cast<std::uint32_t>(RegisterClass::GPR_NX0));
+  const RegisterClassDesc *Candidates = Target.registers().registerClass(GPRClass);
+  if (Candidates == nullptr) {
+    return makeUnexpected(ErrorCode::InternalError, "RISC-V target has no nonzero GPR class");
+  }
+  for (const PhysicalRegister Candidate : Candidates->AllocationOrder) {
+    if (Target.registers().isReservedRegister(Candidate) ||
+        Function.registerInfo().isReserved(Candidate)) {
+      continue;
+    }
+    const bool LiveAtTarget =
+        std::ranges::any_of(TargetBlock.liveIns(), [&](const MachineBasicBlockLiveIn &LiveIn) {
+          return Target.registers().regsOverlap(Candidate, LiveIn.PhysReg);
+        });
+    if (!LiveAtTarget)
+      return Candidate;
+  }
+  return makeUnexpected(ErrorCode::BranchRelaxationFailed,
+                        "RISC-V long branch has no dead physical scratch register");
+}
+
+[[nodiscard]] Expected<bool> expandCompressedBranch(MachineInstr &Instruction,
+                                                    MachineFunction &Function,
+                                                    const TargetDescription &Target) {
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "compressed branch is not linked");
+  auto TargetBlock = directTarget(Instruction);
+  if (!TargetBlock)
+    return std::unexpected(TargetBlock.error());
+  MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPointBefore(Instruction);
+  if (!Point)
+    return std::unexpected(Point.error());
+
+  if (Instruction.opcode() == targetOpcode(InstructionOpcode::C_J)) {
+    auto Zero = physical(PhysicalRegisterID::X0);
+    if (!Zero)
+      return std::unexpected(Zero.error());
+    auto Replacement = buildJAL(Function, Target, *Block, &Instruction, *Zero, **TargetBlock);
+    if (!Replacement)
+      return std::unexpected(Replacement.error());
+    auto Annotations = copySingleInstructionAnnotations(Instruction, **Replacement);
+    if (!Annotations)
+      return std::unexpected(Annotations.error());
+    auto Removed = removeInstruction(Instruction);
+    if (!Removed)
+      return std::unexpected(Removed.error());
+    return true;
+  }
+
+  const MachineOperand *SourceOperand = Instruction.operandAt(0);
+  const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>();
+  if (Source == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "compressed conditional branch has no source register");
+  auto Zero = physical(PhysicalRegisterID::X0);
+  if (!Zero)
+    return std::unexpected(Zero.error());
+  const InstructionOpcode Expanded = Instruction.opcode() == targetOpcode(InstructionOpcode::C_BEQZ)
+                                         ? InstructionOpcode::BEQ
+                                         : InstructionOpcode::BNE;
+  auto Pending = Builder.buildInstr(targetOpcode(Expanded));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto First = Pending->addUse(*Source);
+  if (!First)
+    return std::unexpected(First.error());
+  auto Second = Pending->addUse(Register::fromPhysical(*Zero));
+  if (!Second)
+    return std::unexpected(Second.error());
+  auto Destination = Pending->addBasicBlock(**TargetBlock);
+  if (!Destination)
+    return std::unexpected(Destination.error());
+  auto Replacement = Pending->build();
+  if (!Replacement)
+    return std::unexpected(Replacement.error());
+  auto Annotations = copySingleInstructionAnnotations(Instruction, **Replacement);
+  if (!Annotations)
+    return std::unexpected(Annotations.error());
+  auto Removed = removeInstruction(Instruction);
+  if (!Removed)
+    return std::unexpected(Removed.error());
+  return true;
+}
+
+[[nodiscard]] Expected<bool> relaxConditionalBranch(MachineInstr &Instruction,
+                                                    MachineFunction &Function,
+                                                    const TargetDescription &Target) {
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "conditional branch is not linked");
+  auto TrueTarget = directTarget(Instruction);
+  if (!TrueTarget)
+    return std::unexpected(TrueTarget.error());
+  MachineBasicBlock *FalseTarget = Block->next();
+  if (FalseTarget == nullptr || FalseTarget == *TrueTarget ||
+      std::ranges::none_of(Block->successors(), [FalseTarget](const MachineSuccessor &Successor) {
+        return Successor.Block == FalseTarget;
+      })) {
+    return makeUnexpected(ErrorCode::BranchRelaxationFailed,
+                          "RISC-V conditional relaxation requires its false edge as fallthrough");
+  }
+
+  auto Reversed = reversedOpcode(Instruction.opcode());
+  if (!Reversed)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V conditional branch cannot be inverted");
+  auto SetOpcode = Instruction.setOpcode(*Reversed);
+  if (!SetOpcode)
+    return std::unexpected(SetOpcode.error());
+  auto SetTarget = setDirectTarget(Instruction, *FalseTarget);
+  if (!SetTarget)
+    return std::unexpected(SetTarget.error());
+
+  MachineInstr *Following = Instruction.next();
+  if (Following != nullptr && isUnconditionalBranch(*Following)) {
+    auto Retargeted = setDirectTarget(*Following, **TrueTarget);
+    if (!Retargeted)
+      return std::unexpected(Retargeted.error());
+    return true;
+  }
+  auto Zero = physical(PhysicalRegisterID::X0);
+  if (!Zero)
+    return std::unexpected(Zero.error());
+  MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPointAfter(Instruction);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(targetOpcode(InstructionOpcode::JAL));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto Def = Pending->addDef(Register::fromPhysical(*Zero));
+  if (!Def)
+    return std::unexpected(Def.error());
+  auto Destination = Pending->addBasicBlock(**TrueTarget);
+  if (!Destination)
+    return std::unexpected(Destination.error());
+  auto LongJump = Pending->build();
+  if (!LongJump)
+    return std::unexpected(LongJump.error());
+  auto Identity = copySourceIdentity(Instruction, **LongJump);
+  if (!Identity)
+    return std::unexpected(Identity.error());
+  MachineInstrFlags OriginalFlags = Instruction.flags();
+  const bool HadBundledSuccessor = OriginalFlags.has(MachineInstrFlag::BundledWithSucc);
+  OriginalFlags.set(MachineInstrFlag::BundledWithSucc);
+  Instruction.setFlags(OriginalFlags);
+  MachineInstrFlags LongFlags;
+  LongFlags.set(MachineInstrFlag::BundledWithPred);
+  if (HadBundledSuccessor)
+    LongFlags.set(MachineInstrFlag::BundledWithSucc);
+  if (OriginalFlags.has(MachineInstrFlag::NoMerge))
+    LongFlags.set(MachineInstrFlag::NoMerge);
+  (*LongJump)->setFlags(LongFlags);
+  return true;
+}
+
+[[nodiscard]] Expected<bool> relaxJAL(MachineInstr &Instruction, std::int64_t Offset,
+                                      MachineFunction &Function, const TargetDescription &Target) {
+  MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "RISC-V JAL is not linked");
+  if (Offset < std::numeric_limits<std::int32_t>::min() ||
+      Offset > std::numeric_limits<std::int32_t>::max()) {
+    return makeUnexpected(ErrorCode::BranchRelaxationFailed,
+                          "RISC-V PC-relative long branch exceeds the signed 32-bit range");
+  }
+  auto DestinationBlock = directTarget(Instruction);
+  if (!DestinationBlock)
+    return std::unexpected(DestinationBlock.error());
+  const MachineOperand *DestinationOperand = Instruction.operandAt(0);
+  const Register *Destination =
+      DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+  if (Destination == nullptr || !Destination->isPhysical()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V long JAL requires a physical destination register");
+  }
+  auto Scratch = selectLongBranchScratch(Instruction, **DestinationBlock, Function, Target);
+  if (!Scratch)
+    return std::unexpected(Scratch.error());
+  const std::string Anchor = Instruction.preInstrSymbol()
+                                 ? std::string(*Instruction.preInstrSymbol())
+                                 : ".Lrcc_long_" + std::to_string(Function.stableID().value()) +
+                                       "_" + std::to_string(Instruction.stableID().value());
+  const MachineInstrFlags OriginalFlags = Instruction.flags();
+
+  MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPointBefore(Instruction);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto HighPending = Builder.buildInstr(targetOpcode(InstructionOpcode::AUIPC));
+  if (!HighPending)
+    return std::unexpected(HighPending.error());
+  auto HighDef = HighPending->addDef(Register::fromPhysical(*Scratch));
+  if (!HighDef)
+    return std::unexpected(HighDef.error());
+  auto HighTarget = HighPending->addBasicBlock(**DestinationBlock, PCRelativeHighFlag);
+  if (!HighTarget)
+    return std::unexpected(HighTarget.error());
+  auto High = HighPending->build();
+  if (!High)
+    return std::unexpected(High.error());
+  auto HighSymbol = (*High)->setPreInstrSymbol(Anchor);
+  if (!HighSymbol)
+    return std::unexpected(HighSymbol.error());
+  auto HighIdentity = copySourceIdentity(Instruction, **High);
+  if (!HighIdentity)
+    return std::unexpected(HighIdentity.error());
+
+  auto LowPending = Builder.buildInstr(targetOpcode(InstructionOpcode::JALR));
+  if (!LowPending)
+    return std::unexpected(LowPending.error());
+  auto LowDef = LowPending->addDef(*Destination);
+  if (!LowDef)
+    return std::unexpected(LowDef.error());
+  auto LowBase = LowPending->addUse(Register::fromPhysical(*Scratch));
+  if (!LowBase)
+    return std::unexpected(LowBase.error());
+  auto LowSymbol = LowPending->addMCSymbol(Anchor, 0, PCRelativeLowFlag);
+  if (!LowSymbol)
+    return std::unexpected(LowSymbol.error());
+  auto Low = LowPending->build();
+  if (!Low)
+    return std::unexpected(Low.error());
+  auto LowIdentity = copySourceIdentity(Instruction, **Low);
+  if (!LowIdentity)
+    return std::unexpected(LowIdentity.error());
+  auto LowAnnotations = copyTrailingAnnotations(Instruction, **Low);
+  if (!LowAnnotations)
+    return std::unexpected(LowAnnotations.error());
+
+  MachineInstrFlags HighFlags;
+  if (OriginalFlags.has(MachineInstrFlag::BundledWithPred))
+    HighFlags.set(MachineInstrFlag::BundledWithPred);
+  HighFlags.set(MachineInstrFlag::BundledWithSucc);
+  if (OriginalFlags.has(MachineInstrFlag::NoMerge))
+    HighFlags.set(MachineInstrFlag::NoMerge);
+  (*High)->setFlags(HighFlags);
+  MachineInstrFlags LowFlags = OriginalFlags;
+  LowFlags.clear(MachineInstrFlag::BundledWithPred);
+  LowFlags.set(MachineInstrFlag::BundledWithPred);
+  (*Low)->setFlags(LowFlags);
+  auto Removed = removeInstruction(Instruction);
+  if (!Removed)
+    return std::unexpected(Removed.error());
+  return true;
+}
+
+class RISCVBranchInfo final : public TargetBranchInfo {
+public:
+  [[nodiscard]] Expected<MachineBranchAnalysis>
+  analyzeBranch(MachineBasicBlock &Block, MachineFunction &Function,
+                const TargetDescription &Target) const override {
+    if (&Block.function() != &Function)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V branch analysis references another function");
+    std::vector<MachineInstr *> Terminators;
+    for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+      if (Descriptor == nullptr)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "RISC-V branch analysis encountered an unknown opcode");
+      if (Descriptor->Flags.has(InstructionFlag::Terminator))
+        Terminators.push_back(Instruction);
+    }
+
+    MachineBranchAnalysis Result;
+    if (Terminators.empty())
+      return Result;
+    if (Terminators.size() > 2) {
+      Result.HasUnanalyzableTerminator = true;
+      return Result;
+    }
+    MachineInstr *First = Terminators.front();
+    if (isConditionalBranch(First->opcode())) {
+      auto TrueTarget = directTarget(*First);
+      if (!TrueTarget)
+        return std::unexpected(TrueTarget.error());
+      Result.Conditional = First;
+      Result.TrueTarget = *TrueTarget;
+      if (Terminators.size() == 2) {
+        MachineInstr *Second = Terminators.back();
+        if (!isUnconditionalBranch(*Second)) {
+          Result.HasUnanalyzableTerminator = true;
+          return Result;
+        }
+        auto FalseTarget = directTarget(*Second);
+        if (!FalseTarget)
+          return std::unexpected(FalseTarget.error());
+        Result.Unconditional = Second;
+        Result.FalseTarget = *FalseTarget;
+      } else {
+        for (const MachineSuccessor &Successor : Block.successors()) {
+          if (Successor.Block == nullptr || Successor.Block == Result.TrueTarget)
+            continue;
+          if (Result.FalseTarget != nullptr) {
+            Result.HasUnanalyzableTerminator = true;
+            return Result;
+          }
+          Result.FalseTarget = Successor.Block;
+        }
+        if (Result.FalseTarget == nullptr)
+          Result.FalseTarget = Block.next();
+      }
+      return Result;
+    }
+    if (Terminators.size() == 1 && isUnconditionalBranch(*First)) {
+      auto TargetBlock = directTarget(*First);
+      if (!TargetBlock)
+        return std::unexpected(TargetBlock.error());
+      Result.Unconditional = First;
+      Result.TrueTarget = *TargetBlock;
+      return Result;
+    }
+    Result.HasUnanalyzableTerminator = true;
+    return Result;
+  }
+
+  [[nodiscard]] Expected<void> reverseBranchCondition(MachineInstr &Branch,
+                                                      MachineBasicBlock &NewTarget,
+                                                      MachineFunction &Function,
+                                                      const TargetDescription &) const override {
+    if (&Branch.function() != &Function || &NewTarget.function() != &Function)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V branch reversal references another function");
+    const std::optional<Opcode> Reversed = reversedOpcode(Branch.opcode());
+    if (!Reversed)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V branch opcode has no inverse condition");
+    auto OpcodeResult = Branch.setOpcode(*Reversed);
+    if (!OpcodeResult)
+      return std::unexpected(OpcodeResult.error());
+    return setDirectTarget(Branch, NewTarget);
+  }
+
+  [[nodiscard]] Expected<void> removeBranch(MachineInstr &Branch, MachineFunction &Function,
+                                            const TargetDescription &) const override {
+    if (&Branch.function() != &Function)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V branch removal references another function");
+    return removeInstruction(Branch);
+  }
+
+  [[nodiscard]] Expected<bool> rewriteBranchTarget(MachineBasicBlock &Block,
+                                                   MachineBasicBlock &OldTarget,
+                                                   MachineBasicBlock &NewTarget,
+                                                   MachineFunction &Function,
+                                                   const TargetDescription &) const override {
+    if (&Block.function() != &Function || &OldTarget.function() != &Function ||
+        &NewTarget.function() != &Function) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V branch rewrite references another function");
+    }
+    bool Changed = false;
+    for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      if (!isConditionalBranch(Instruction->opcode()) && !isUnconditionalBranch(*Instruction)) {
+        continue;
+      }
+      auto CurrentTarget = directTarget(*Instruction);
+      if (!CurrentTarget)
+        return std::unexpected(CurrentTarget.error());
+      if (*CurrentTarget != &OldTarget)
+        continue;
+      auto Rewritten = setDirectTarget(*Instruction, NewTarget);
+      if (!Rewritten)
+        return std::unexpected(Rewritten.error());
+      Changed = true;
+    }
+    return Changed;
+  }
+
+  [[nodiscard]] Expected<MachineInstr *>
+  insertUnconditionalBranch(MachineBasicBlock &Block, MachineBasicBlock &TargetBlock,
+                            MachineFunction &Function,
+                            const TargetDescription &Target) const override {
+    if (&Block.function() != &Function || &TargetBlock.function() != &Function)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V branch insertion references another function");
+    auto Zero = physical(PhysicalRegisterID::X0);
+    if (!Zero)
+      return std::unexpected(Zero.error());
+    return buildJAL(Function, Target, Block, nullptr, *Zero, TargetBlock);
+  }
+
+  [[nodiscard]] Expected<std::uint32_t>
+  instructionSize(const MachineInstr &Instruction, const MachineFunction &,
+                  const TargetDescription &Target) const override {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+    if (Descriptor == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V instruction-size query encountered an unknown opcode");
+    if (!Descriptor->Flags.has(InstructionFlag::ProducesCode))
+      return 0;
+    const auto Category =
+        std::ranges::find_if(encodingCategories(), [Descriptor](const EncodingCategoryInfo &Info) {
+          return Info.ID == Descriptor->EncodingCategory;
+        });
+    if (Category == encodingCategories().end() || Category->SizeInBytes == 0)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V producing instruction has no exact encoding size");
+    return Category->SizeInBytes;
+  }
+
+  [[nodiscard]] Expected<MachineBasicBlock *>
+  branchTarget(MachineInstr &Instruction, MachineFunction &Function,
+               const TargetDescription &) const override {
+    if (&Instruction.function() != &Function)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V branch target query references another function");
+    return directTarget(Instruction);
+  }
+
+  [[nodiscard]] Expected<std::optional<bool>>
+  evaluateBranchCondition(const MachineInstr &Instruction, const MachineFunction &Function,
+                          const TargetDescription &) const override {
+    if (&Instruction.function() != &Function) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V branch evaluation references another function");
+    }
+    const Opcode Value = Instruction.opcode();
+    if (!isConditionalBranch(Value))
+      return std::optional<bool>{};
+    if (Value == targetOpcode(InstructionOpcode::C_BEQZ) ||
+        Value == targetOpcode(InstructionOpcode::C_BNEZ)) {
+      if (!isZeroRegister(Instruction.operandAt(0)))
+        return std::optional<bool>{};
+      return std::optional<bool>{Value == targetOpcode(InstructionOpcode::C_BEQZ)};
+    }
+    if (!sameRegister(Instruction.operandAt(0), Instruction.operandAt(1)))
+      return std::optional<bool>{};
+    if (Value == targetOpcode(InstructionOpcode::BEQ) ||
+        Value == targetOpcode(InstructionOpcode::BGE) ||
+        Value == targetOpcode(InstructionOpcode::BGEU)) {
+      return std::optional<bool>{true};
+    }
+    return std::optional<bool>{false};
+  }
+
+  [[nodiscard]] bool isBranchOffsetInRange(const MachineInstr &Instruction,
+                                           std::int64_t Offset) const noexcept override {
+    if ((Offset & 1) != 0)
+      return false;
+    const Opcode Value = Instruction.opcode();
+    if (Value == targetOpcode(InstructionOpcode::C_BEQZ) ||
+        Value == targetOpcode(InstructionOpcode::C_BNEZ)) {
+      return Offset >= -256 && Offset <= 254;
+    }
+    if (Value == targetOpcode(InstructionOpcode::C_J))
+      return Offset >= -2048 && Offset <= 2046;
+    if (isConditionalBranch(Value))
+      return Offset >= -4096 && Offset <= 4094;
+    if (Value == targetOpcode(InstructionOpcode::JAL))
+      return Offset >= -1048576 && Offset <= 1048574;
+    return true;
+  }
+
+  [[nodiscard]] Expected<bool> relaxBranch(MachineInstr &Instruction, std::int64_t Offset,
+                                           MachineFunction &Function,
+                                           const TargetDescription &Target) const override {
+    if (&Instruction.function() != &Function)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V branch relaxation references another function");
+    if (Instruction.opcode() == targetOpcode(InstructionOpcode::C_J) ||
+        Instruction.opcode() == targetOpcode(InstructionOpcode::C_BEQZ) ||
+        Instruction.opcode() == targetOpcode(InstructionOpcode::C_BNEZ)) {
+      return expandCompressedBranch(Instruction, Function, Target);
+    }
+    if (isConditionalBranch(Instruction.opcode()))
+      return relaxConditionalBranch(Instruction, Function, Target);
+    if (Instruction.opcode() == targetOpcode(InstructionOpcode::JAL))
+      return relaxJAL(Instruction, Offset, Function, Target);
+    return false;
+  }
+};
+
+} // namespace
+
+const TargetBranchInfo &branchInfo() noexcept {
+  static const RISCVBranchInfo Value;
+  return Value;
+}
+
+} // namespace rcc::riscv