From 6dc798fbdbef20670317742a8c1d12f47e9d1c05 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Tue, 25 Aug 2026 01:50:02 +0800 Subject: [RISCV] Implement base offset merging --- backend/lib/Target/RISCV/RISCVMergeBaseOffset.cpp | 516 ++++++++++++++++++++++ 1 file changed, 516 insertions(+) create mode 100644 backend/lib/Target/RISCV/RISCVMergeBaseOffset.cpp (limited to 'backend/lib/Target/RISCV/RISCVMergeBaseOffset.cpp') diff --git a/backend/lib/Target/RISCV/RISCVMergeBaseOffset.cpp b/backend/lib/Target/RISCV/RISCVMergeBaseOffset.cpp new file mode 100644 index 0000000..d9b2f4b --- /dev/null +++ b/backend/lib/Target/RISCV/RISCVMergeBaseOffset.cpp @@ -0,0 +1,516 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "RISCV.h" +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachinePassManager.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVRegisters.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace rcc::riscv { +namespace { + +constexpr std::uint32_t PCRelativeHighFlag = 2; +constexpr std::uint32_t PCRelativeLowFlag = 4; +constexpr std::uint32_t AbsoluteHighFlag = 32; +constexpr std::uint32_t AbsoluteLowFlag = 64; + +struct AddressPair final { + MachineInstr *High = nullptr; + MachineInstr *Low = nullptr; +}; + +[[nodiscard]] bool isInt32(std::int64_t Value) noexcept { + return Value >= std::numeric_limits::min() && + Value <= std::numeric_limits::max(); +} + +[[nodiscard]] std::int64_t signExtend32(std::uint64_t Value) noexcept { + return static_cast(static_cast(Value)); +} + +[[nodiscard]] bool isZeroRegister(Register Reg) noexcept { + const auto Physical = Reg.physicalRegister(); + return Physical && Physical->number() == static_cast(PhysicalRegisterID::X0); +} + +[[nodiscard]] std::optional addressOffset(const MachineOperand &Operand) noexcept { + if (const auto *Constant = Operand.getIf()) + return Constant->Offset; + if (const auto *Global = Operand.getIf()) + return Global->Offset; + if (const auto *Block = Operand.getIf()) + return Block->Offset; + if (const auto *Symbol = Operand.getIf()) + return Symbol->Offset; + return std::nullopt; +} + +[[nodiscard]] bool isFoldableAddress(const MachineOperand &Operand) noexcept { + return Operand.getIf() != nullptr || + Operand.getIf() != nullptr || + Operand.getIf() != nullptr; +} + +[[nodiscard]] Expected addressWithOffset(const MachineOperand &Operand, + std::int64_t Offset) { + if (const auto *Constant = Operand.getIf()) + return MachineOperand::constantPool(Constant->Index, Offset, Operand.targetFlags()); + if (const auto *Global = Operand.getIf()) { + return MachineOperand::globalSymbol(Global->Name, Offset, Operand.targetFlags(), + Global->Properties); + } + if (const auto *Block = Operand.getIf()) { + return MachineOperand::blockAddress(Block->FunctionName, Block->BlockName, Offset, + Operand.targetFlags()); + } + if (const auto *Symbol = Operand.getIf()) + return MachineOperand::mcSymbol(Symbol->Name, Offset, Operand.targetFlags()); + return makeUnexpected(ErrorCode::InvalidArgument, + "RISC-V base-offset folding requires a symbolic address operand"); +} + +[[nodiscard]] Expected replaceOperand(MachineInstr &Instruction, std::size_t Index, + MachineOperand Operand) { + auto Erased = Instruction.eraseOperand(Index); + if (!Erased) + return std::unexpected(Erased.error()); + return Instruction.insertOperand(Index, std::move(Operand)); +} + +[[nodiscard]] MachineInstr *uniqueUseInstruction(MachineRegisterInfo &Registers, + Register Reg) noexcept { + if (!Registers.hasOneUse(Reg, false)) + return nullptr; + for (MachineOperand &Use : Registers.useOperands(Reg, false)) + return Use.parent(); + return nullptr; +} + +[[nodiscard]] std::optional detectFoldable(MachineInstr &High, + MachineRegisterInfo &Registers) { + const bool IsLUI = High.opcode() == instructionOpcode(InstructionOpcode::LUI); + const bool IsAUIPC = High.opcode() == instructionOpcode(InstructionOpcode::AUIPC); + if (!IsLUI && !IsAUIPC) + return std::nullopt; + MachineOperand *HighAddress = High.operandAt(1); + if (HighAddress == nullptr || !isFoldableAddress(*HighAddress) || + addressOffset(*HighAddress) != 0 || + HighAddress->targetFlags() != (IsAUIPC ? PCRelativeHighFlag : AbsoluteHighFlag)) { + return std::nullopt; + } + MachineOperand *HighDefinition = High.operandAt(0); + const auto HighRegister = + HighDefinition == nullptr ? std::nullopt : HighDefinition->registerValue(); + if (!HighRegister) + return std::nullopt; + MachineInstr *Low = uniqueUseInstruction(Registers, *HighRegister); + if (Low == nullptr || Low->opcode() != instructionOpcode(InstructionOpcode::ADDI)) + return std::nullopt; + const auto LowBase = + Low->operandAt(1) == nullptr ? std::nullopt : Low->operandAt(1)->registerValue(); + MachineOperand *LowAddress = Low->operandAt(2); + if (!LowBase || *LowBase != *HighRegister || LowAddress == nullptr) + return std::nullopt; + if (IsLUI) { + if (!isFoldableAddress(*LowAddress) || addressOffset(*LowAddress) != 0 || + LowAddress->targetFlags() != AbsoluteLowFlag) { + return std::nullopt; + } + } else if (LowAddress->getIf() == nullptr || + LowAddress->targetFlags() != PCRelativeLowFlag) { + return std::nullopt; + } + return AddressPair{.High = &High, .Low = Low}; +} + +[[nodiscard]] Expected foldOffset(AddressPair Pair, MachineInstr &Tail, std::int64_t Offset, + MachineRegisterInfo &Registers) { + if (!isInt32(Offset)) + return false; + MachineOperand *HighAddress = Pair.High->operandAt(1); + MachineOperand *LowAddress = Pair.Low->operandAt(2); + MachineOperand *LowDefinition = Pair.Low->operandAt(0); + MachineOperand *TailDefinition = Tail.operandAt(0); + if (HighAddress == nullptr || LowAddress == nullptr || LowDefinition == nullptr || + TailDefinition == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V base-offset sequence has incomplete operands"); + } + auto LowRegister = LowDefinition->registerValue(); + auto TailRegister = TailDefinition->registerValue(); + if (!LowRegister || !TailRegister) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V base-offset sequence has non-register definitions"); + auto NewHighAddress = addressWithOffset(*HighAddress, Offset); + if (!NewHighAddress) + return std::unexpected(NewHighAddress.error()); + std::optional NewLowAddress; + if (Pair.High->opcode() != instructionOpcode(InstructionOpcode::AUIPC)) { + auto Address = addressWithOffset(*LowAddress, Offset); + if (!Address) + return std::unexpected(Address.error()); + NewLowAddress.emplace(std::move(*Address)); + } + auto ReplacedHigh = replaceOperand(*Pair.High, 1, std::move(*NewHighAddress)); + if (!ReplacedHigh) + return std::unexpected(ReplacedHigh.error()); + if (NewLowAddress) { + auto ReplacedLow = replaceOperand(*Pair.Low, 2, std::move(*NewLowAddress)); + if (!ReplacedLow) + return std::unexpected(ReplacedLow.error()); + } + auto ReplacedRegisters = Registers.replaceRegWith(*TailRegister, *LowRegister); + if (!ReplacedRegisters) + return std::unexpected(ReplacedRegisters.error()); + MachineBasicBlock *Block = Tail.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "RISC-V offset tail is not linked"); + auto Removed = Block->removeInstruction(Tail); + if (!Removed) + return std::unexpected(Removed.error()); + return true; +} + +[[nodiscard]] Expected foldLargeOffset(AddressPair Pair, MachineInstr &Tail, + Register GlobalAddress, + MachineRegisterInfo &Registers) { + MachineOperand *LeftOperand = Tail.operandAt(1); + MachineOperand *RightOperand = Tail.operandAt(2); + const auto Left = LeftOperand == nullptr ? std::nullopt : LeftOperand->registerValue(); + const auto Right = RightOperand == nullptr ? std::nullopt : RightOperand->registerValue(); + if (!Left || !Right) + return false; + const Register OffsetRegister = *Left == GlobalAddress ? *Right : *Left; + if (!OffsetRegister.isVirtual() || !Registers.hasOneUse(OffsetRegister, false)) + return false; + MachineInstr *OffsetTail = Registers.getVRegDef(OffsetRegister); + if (OffsetTail == nullptr) + return false; + + const bool IsADDI = OffsetTail->opcode() == instructionOpcode(InstructionOpcode::ADDI); + const bool IsADDIW = OffsetTail->opcode() == instructionOpcode(InstructionOpcode::ADDIW); + if (IsADDI || IsADDIW) { + MachineOperand *BaseOperand = OffsetTail->operandAt(1); + MachineOperand *ImmediateOperand = OffsetTail->operandAt(2); + const auto Base = BaseOperand == nullptr ? std::nullopt : BaseOperand->registerValue(); + const auto *Low = + ImmediateOperand == nullptr ? nullptr : ImmediateOperand->getIf(); + if (!Base || Low == nullptr || ImmediateOperand->targetFlags() != 0) + return false; + if (isZeroRegister(*Base)) { + auto Folded = foldOffset(Pair, Tail, *Low, Registers); + if (!Folded || !*Folded) + return Folded; + MachineBasicBlock *Block = OffsetTail->parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "RISC-V offset instruction is not linked"); + auto Removed = Block->removeInstruction(*OffsetTail); + if (!Removed) + return std::unexpected(Removed.error()); + return true; + } + MachineInstr *OffsetHigh = Registers.getVRegDef(*Base); + if (OffsetHigh == nullptr || + OffsetHigh->opcode() != instructionOpcode(InstructionOpcode::LUI) || + !Registers.hasOneUse(*Base, false)) { + return false; + } + MachineOperand *HighImmediate = OffsetHigh->operandAt(1); + const auto *High = HighImmediate == nullptr ? nullptr : HighImmediate->getIf(); + if (High == nullptr || HighImmediate->targetFlags() != 0) + return false; + std::int64_t Offset = signExtend32(static_cast(*High) << 12U) + *Low; + if (IsADDIW) + Offset = signExtend32(static_cast(Offset)); + auto Folded = foldOffset(Pair, Tail, Offset, Registers); + if (!Folded || !*Folded) + return Folded; + MachineBasicBlock *Block = OffsetTail->parent(); + MachineBasicBlock *HighBlock = OffsetHigh->parent(); + if (Block == nullptr || HighBlock == nullptr) + return makeUnexpected(ErrorCode::InternalError, "RISC-V offset instructions are not linked"); + auto Removed = Block->removeInstruction(*OffsetTail); + if (!Removed) + return std::unexpected(Removed.error()); + Removed = HighBlock->removeInstruction(*OffsetHigh); + if (!Removed) + return std::unexpected(Removed.error()); + return true; + } + + if (OffsetTail->opcode() != instructionOpcode(InstructionOpcode::LUI)) + return false; + MachineOperand *ImmediateOperand = OffsetTail->operandAt(1); + const auto *High = + ImmediateOperand == nullptr ? nullptr : ImmediateOperand->getIf(); + if (High == nullptr || ImmediateOperand->targetFlags() != 0) + return false; + const std::int64_t Offset = signExtend32(static_cast(*High) << 12U); + auto Folded = foldOffset(Pair, Tail, Offset, Registers); + if (!Folded || !*Folded) + return Folded; + MachineBasicBlock *Block = OffsetTail->parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "RISC-V offset instruction is not linked"); + auto Removed = Block->removeInstruction(*OffsetTail); + if (!Removed) + return std::unexpected(Removed.error()); + return true; +} + +[[nodiscard]] Expected foldShiftedOffset(AddressPair Pair, MachineInstr &Tail, + Register GlobalAddress, + MachineRegisterInfo &Registers) { + if (Tail.operandAt(2) == nullptr || Tail.operandAt(2)->registerValue() != GlobalAddress) + return false; + unsigned Shift = 0; + if (Tail.opcode() == instructionOpcode(InstructionOpcode::SH1ADD)) + Shift = 1; + else if (Tail.opcode() == instructionOpcode(InstructionOpcode::SH2ADD)) + Shift = 2; + else if (Tail.opcode() == instructionOpcode(InstructionOpcode::SH3ADD)) + Shift = 3; + else + return false; + const auto Shifted = + Tail.operandAt(1) == nullptr ? std::nullopt : Tail.operandAt(1)->registerValue(); + if (!Shifted || !Shifted->isVirtual() || !Registers.hasOneUse(*Shifted, false)) + return false; + MachineInstr *OffsetTail = Registers.getVRegDef(*Shifted); + if (OffsetTail == nullptr || OffsetTail->opcode() != instructionOpcode(InstructionOpcode::ADDI)) { + return false; + } + const auto Base = OffsetTail->operandAt(1) == nullptr ? std::nullopt + : OffsetTail->operandAt(1)->registerValue(); + const auto *Immediate = OffsetTail->operandAt(2) == nullptr + ? nullptr + : OffsetTail->operandAt(2)->getIf(); + if (!Base || !isZeroRegister(*Base) || Immediate == nullptr) + return false; + const std::int64_t Offset = + static_cast(static_cast(*Immediate) << Shift); + auto Folded = foldOffset(Pair, Tail, Offset, Registers); + if (!Folded || !*Folded) + return Folded; + MachineBasicBlock *Block = OffsetTail->parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "RISC-V offset instruction is not linked"); + auto Removed = Block->removeInstruction(*OffsetTail); + if (!Removed) + return std::unexpected(Removed.error()); + return true; +} + +[[nodiscard]] Expected foldArithmeticOffset(AddressPair Pair, + MachineRegisterInfo &Registers) { + MachineOperand *LowDefinition = Pair.Low->operandAt(0); + const auto LowRegister = LowDefinition == nullptr ? std::nullopt : LowDefinition->registerValue(); + if (!LowRegister) + return false; + MachineInstr *Tail = uniqueUseInstruction(Registers, *LowRegister); + if (Tail == nullptr) + return false; + if (Tail->opcode() == instructionOpcode(InstructionOpcode::ADDI)) { + const auto *Immediate = + Tail->operandAt(2) == nullptr ? nullptr : Tail->operandAt(2)->getIf(); + if (Immediate == nullptr) + return false; + MachineOperand *TailDefinition = Tail->operandAt(0); + const auto TailRegister = + TailDefinition == nullptr ? std::nullopt : TailDefinition->registerValue(); + MachineInstr *SecondTail = + TailRegister ? uniqueUseInstruction(Registers, *TailRegister) : nullptr; + if (SecondTail != nullptr && + SecondTail->opcode() == instructionOpcode(InstructionOpcode::ADDI)) { + const auto *SecondImmediate = SecondTail->operandAt(2) == nullptr + ? nullptr + : SecondTail->operandAt(2)->getIf(); + if (SecondImmediate != nullptr) { + auto Folded = foldOffset(Pair, *SecondTail, *Immediate + *SecondImmediate, Registers); + if (!Folded || !*Folded) + return Folded; + MachineBasicBlock *Block = Tail->parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "RISC-V offset instruction is not linked"); + auto Removed = Block->removeInstruction(*Tail); + if (!Removed) + return std::unexpected(Removed.error()); + return true; + } + } + return foldOffset(Pair, *Tail, *Immediate, Registers); + } + if (Tail->opcode() == instructionOpcode(InstructionOpcode::ADD)) + return foldLargeOffset(Pair, *Tail, *LowRegister, Registers); + if (Tail->opcode() == instructionOpcode(InstructionOpcode::SH1ADD) || + Tail->opcode() == instructionOpcode(InstructionOpcode::SH2ADD) || + Tail->opcode() == instructionOpcode(InstructionOpcode::SH3ADD)) { + return foldShiftedOffset(Pair, *Tail, *LowRegister, Registers); + } + return false; +} + +[[nodiscard]] bool isOffsetMemoryInstruction(const MachineInstr &Instruction, + const TargetDescription &Target) noexcept { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + if (Descriptor == nullptr || (!Descriptor->Flags.has(InstructionFlag::MayLoad) && + !Descriptor->Flags.has(InstructionFlag::MayStore))) { + return false; + } + return Instruction.operandAt(0) != nullptr && Instruction.operandAt(1) != nullptr && + Instruction.operandAt(2) != nullptr; +} + +[[nodiscard]] Expected foldIntoMemoryOperations(AddressPair Pair, + MachineRegisterInfo &Registers, + const TargetDescription &Target) { + MachineOperand *LowDefinition = Pair.Low->operandAt(0); + const auto LowRegister = LowDefinition == nullptr ? std::nullopt : LowDefinition->registerValue(); + if (!LowRegister) + return false; + std::vector Uses; + for (MachineOperand &Use : Registers.useOperands(*LowRegister, false)) { + MachineInstr *Instruction = Use.parent(); + if (Instruction != nullptr && std::ranges::find(Uses, Instruction) == Uses.end()) + Uses.push_back(Instruction); + } + if (Uses.empty()) + return false; + + std::optional CommonOffset; + for (MachineInstr *Use : Uses) { + if (!isOffsetMemoryInstruction(*Use, Target)) + return false; + const auto Value = Use->operandAt(0)->registerValue(); + const auto Base = Use->operandAt(1)->registerValue(); + const auto *Offset = Use->operandAt(2)->getIf(); + if (!Base || *Base != *LowRegister || (Value && *Value == *LowRegister) || Offset == nullptr) + return false; + if (CommonOffset && *CommonOffset != *Offset) + return false; + CommonOffset = *Offset; + } + + MachineOperand *HighAddress = Pair.High->operandAt(1); + MachineOperand *LowAddress = Pair.Low->operandAt(2); + MachineOperand *HighDefinition = Pair.High->operandAt(0); + if (HighAddress == nullptr || LowAddress == nullptr || HighDefinition == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "RISC-V base-offset sequence has incomplete address operands"); + const auto HighRegister = HighDefinition->registerValue(); + const auto OldOffset = addressOffset(*HighAddress); + if (!HighRegister || !OldOffset) + return false; + const std::int64_t NewOffset = *OldOffset + *CommonOffset; + if (!isInt32(NewOffset)) + return false; + + auto NewHighAddress = addressWithOffset(*HighAddress, NewOffset); + if (!NewHighAddress) + return std::unexpected(NewHighAddress.error()); + auto NewLowAddress = Pair.High->opcode() == instructionOpcode(InstructionOpcode::AUIPC) + ? Expected(LowAddress->cloneDetached()) + : addressWithOffset(*LowAddress, NewOffset); + if (!NewLowAddress) + return std::unexpected(NewLowAddress.error()); + auto ReplacedHigh = replaceOperand(*Pair.High, 1, std::move(*NewHighAddress)); + if (!ReplacedHigh) + return std::unexpected(ReplacedHigh.error()); + if (Pair.High->opcode() != instructionOpcode(InstructionOpcode::AUIPC)) { + auto ReplacedLow = replaceOperand(*Pair.Low, 2, NewLowAddress->cloneDetached()); + if (!ReplacedLow) + return std::unexpected(ReplacedLow.error()); + } + for (MachineInstr *Use : Uses) { + auto SetBase = Use->operandAt(1)->setRegister(*HighRegister); + if (!SetBase) + return std::unexpected(SetBase.error()); + auto ReplacedOffset = replaceOperand(*Use, 2, NewLowAddress->cloneDetached()); + if (!ReplacedOffset) + return std::unexpected(ReplacedOffset.error()); + } + MachineBasicBlock *Block = Pair.Low->parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "RISC-V low address instruction is not linked"); + auto Removed = Block->removeInstruction(*Pair.Low); + if (!Removed) + return std::unexpected(Removed.error()); + return true; +} + +class RISCVMergeBaseOffsetPass final : public MachineFunctionPass { +public: + [[nodiscard]] const MachinePassContract &contract() const noexcept override { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = "riscv-merge-base-offset", + .Requires = {MachineFunctionProperty::IsSSA}, + .Sets = {}, + .Clears = {}, + .RequiredAnalyses = {}, + .VerificationStage = std::nullopt, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers}; + return Value; + }(); + return Contract; + } + + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &) override { + MachinePassResult Result; + Result.Preserved = PreservedAnalyses::all(); + MachineRegisterInfo &Registers = Function.registerInfo(); + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;) { + auto Pair = detectFoldable(*Instruction, Registers); + if (!Pair) { + Instruction = Instruction->next(); + continue; + } + auto Arithmetic = foldArithmeticOffset(*Pair, Registers); + if (!Arithmetic) + return std::unexpected(Arithmetic.error()); + Result.Changed |= *Arithmetic; + auto Memory = foldIntoMemoryOperations(*Pair, Registers, Target); + if (!Memory) + return std::unexpected(Memory.error()); + Result.Changed |= *Memory; + Instruction = Pair->High->next(); + } + } + if (Result.Changed) { + Result.Changes = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers}; + Result.Preserved = PreservedAnalyses::none(); + } + return Result; + } +}; + +} // namespace + +std::unique_ptr createMergeBaseOffsetPass() { + return std::make_unique(); +} + +} // namespace rcc::riscv -- cgit v1.2.3