aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRichard-Qin-X <richard.qin.001@gmail.com>2026-08-08 04:14:34 +0800
committerRichard-Qin-X <richard.qin.001@gmail.com>2026-08-08 04:14:34 +0800
commit77884c967d1cbc48afcbaef7e5a35adcb3c5da1b (patch)
tree8cc31c1c5115ed909ec9f8751964bfdc96fbd4ad
parent10b7e69448f866bcd6893b21d7f78d766252eb11 (diff)
downloadrcc-project-77884c967d1cbc48afcbaef7e5a35adcb3c5da1b.tar.gz
rcc-project-77884c967d1cbc48afcbaef7e5a35adcb3c5da1b.tar.xz
[CodeGen] Implement machine SSA exit
Diffstat
-rw-r--r--backend/include/rcc/CodeGen/InstructionDescriptor.h1
-rw-r--r--backend/include/rcc/CodeGen/MachineCFGUpdater.h6
-rw-r--r--backend/include/rcc/CodeGen/MachineOperand.h1
-rw-r--r--backend/include/rcc/CodeGen/MachineSSAExit.h49
-rw-r--r--backend/include/rcc/CodeGen/TargetCodeGen.h34
-rw-r--r--backend/include/rcc/CodeGen/TargetDescription.h7
-rw-r--r--backend/include/rcc/Target/RISCV/RISCVCodeGen.h1
-rw-r--r--backend/lib/CodeGen/CMakeLists.txt4
-rw-r--r--backend/lib/CodeGen/GenericOpcodes.cpp53
-rw-r--r--backend/lib/CodeGen/InstructionDescriptor.cpp8
-rw-r--r--backend/lib/CodeGen/MachineCFGUpdater.cpp381
-rw-r--r--backend/lib/CodeGen/MachineOperand.cpp15
-rw-r--r--backend/lib/CodeGen/MachineSSAExit.cpp1090
-rw-r--r--backend/lib/CodeGen/MachineVerifier.cpp87
-rw-r--r--backend/lib/CodeGen/TargetDescription.cpp8
-rw-r--r--backend/lib/Target/RISCV/RISCVCodeGen.cpp199
-rw-r--r--backend/unittests/CodeGen/CMakeLists.txt11
-rw-r--r--backend/unittests/CodeGen/MachineAnalysesTest.cpp103
-rw-r--r--backend/unittests/CodeGen/MachineSSAExitTest.cpp1113
-rw-r--r--backend/unittests/CodeGen/MachineVerifierTest.cpp126
-rw-r--r--backend/unittests/Target/CMakeLists.txt7
-rw-r--r--backend/unittests/Target/RISCVSSAExitTest.cpp346
22 files changed, 3594 insertions, 56 deletions
diff --git a/backend/include/rcc/CodeGen/InstructionDescriptor.h b/backend/include/rcc/CodeGen/InstructionDescriptor.h
index 7cf598d..ca2c5cf 100644
--- a/backend/include/rcc/CodeGen/InstructionDescriptor.h
+++ b/backend/include/rcc/CodeGen/InstructionDescriptor.h
@@ -226,6 +226,7 @@ struct OperandDescriptor final {
bool Optional = false;
bool VariadicGroup = false;
bool AllowSubReg = false;
+ bool AllowAnyTargetFlags = false;
std::optional<NamedOperandID> Name;
std::optional<TargetOperandTypeID> TargetOperandType;
std::uint32_t AllowedTargetFlags = 0;
diff --git a/backend/include/rcc/CodeGen/MachineCFGUpdater.h b/backend/include/rcc/CodeGen/MachineCFGUpdater.h
index 4359538..70fb9aa 100644
--- a/backend/include/rcc/CodeGen/MachineCFGUpdater.h
+++ b/backend/include/rcc/CodeGen/MachineCFGUpdater.h
@@ -10,6 +10,7 @@ namespace rcc {
class MachineBasicBlock;
class MachineFunction;
+class MachineInstr;
class MachineCFGUpdater final {
public:
@@ -22,11 +23,16 @@ public:
[[nodiscard]] Expected<void> replaceSuccessor(MachineBasicBlock &From,
MachineBasicBlock &OldTarget,
MachineBasicBlock &NewTarget);
+ [[nodiscard]] Expected<void> splitEdge(MachineBasicBlock &From, MachineBasicBlock &To,
+ MachineBasicBlock &EdgeBlock);
[[nodiscard]] Expected<void> updateBranchProbability(MachineBasicBlock &From,
MachineBasicBlock &To,
BranchProbability Probability);
[[nodiscard]] Expected<void> transferSuccessors(MachineBasicBlock &From, MachineBasicBlock &To);
[[nodiscard]] Expected<void> disconnectBlock(MachineBasicBlock &Block);
+ [[nodiscard]] Expected<MachineBasicBlock *> splitBlock(MachineBasicBlock &Block,
+ MachineInstr &SplitBefore);
+ [[nodiscard]] Expected<void> deleteBlock(MachineBasicBlock &Block);
private:
[[nodiscard]] Expected<void> verifyOwnership(const MachineBasicBlock &Block) const;
diff --git a/backend/include/rcc/CodeGen/MachineOperand.h b/backend/include/rcc/CodeGen/MachineOperand.h
index b8a6dcc..31ad7e4 100644
--- a/backend/include/rcc/CodeGen/MachineOperand.h
+++ b/backend/include/rcc/CodeGen/MachineOperand.h
@@ -449,6 +449,7 @@ public:
[[nodiscard]] Expected<void> setRegister(Register Reg);
[[nodiscard]] Expected<void> setRegisterFlags(RegisterOperandFlags Flags);
[[nodiscard]] Expected<void> setSubReg(SubRegIndex SubReg);
+ [[nodiscard]] Expected<void> setBasicBlock(MachineBasicBlock &Block);
[[nodiscard]] std::optional<std::size_t> tiedOperandIndex() const noexcept {
return TiedOperandIndex;
diff --git a/backend/include/rcc/CodeGen/MachineSSAExit.h b/backend/include/rcc/CodeGen/MachineSSAExit.h
new file mode 100644
index 0000000..d98c0b9
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineSSAExit.h
@@ -0,0 +1,49 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINESSAEXIT_H
+#define RCC_CODEGEN_MACHINESSAEXIT_H
+
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/TargetCodeGen.h"
+
+namespace rcc {
+
+class PHIEliminationPass final : public MachineFunctionPass {
+public:
+ PHIEliminationPass() noexcept = default;
+ explicit PHIEliminationPass(const TargetSSAInfo &Info) noexcept : Info(&Info) {}
+
+ [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+ [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineAnalysisManager &Analyses) override;
+
+private:
+ [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineAnalysisManager &Analyses);
+
+ const TargetSSAInfo *Info = nullptr;
+};
+
+class TwoAddressRewritePass final : public MachineFunctionPass {
+public:
+ TwoAddressRewritePass() noexcept = default;
+ explicit TwoAddressRewritePass(const TargetSSAInfo &Info) noexcept : Info(&Info) {}
+
+ [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+ [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineAnalysisManager &Analyses) override;
+
+private:
+ [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineAnalysisManager &Analyses);
+
+ const TargetSSAInfo *Info = nullptr;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINESSAEXIT_H
diff --git a/backend/include/rcc/CodeGen/TargetCodeGen.h b/backend/include/rcc/CodeGen/TargetCodeGen.h
index b1be1f6..f2aac5d 100644
--- a/backend/include/rcc/CodeGen/TargetCodeGen.h
+++ b/backend/include/rcc/CodeGen/TargetCodeGen.h
@@ -7,12 +7,14 @@
#include "rcc/CodeGen/Register.h"
#include "rcc/Support/Error.h"
+#include <cstddef>
#include <cstdint>
#include <optional>
namespace rcc {
class MachineFunction;
+class MachineBasicBlock;
class MachineInstr;
class MachineRegisterInfo;
class TargetDescription;
@@ -89,6 +91,38 @@ public:
}
};
+class TargetSSAInfo {
+public:
+ virtual ~TargetSSAInfo() = default;
+
+ [[nodiscard]] virtual Expected<bool> isFallthroughEdge(const MachineBasicBlock &From,
+ const MachineBasicBlock &To,
+ const MachineFunction &Function,
+ const TargetDescription &Target) const = 0;
+
+ [[nodiscard]] virtual Expected<bool>
+ rewriteBranchTarget(MachineBasicBlock &Block, MachineBasicBlock &OldTarget,
+ MachineBasicBlock &NewTarget, MachineFunction &Function,
+ const TargetDescription &Target) const = 0;
+
+ [[nodiscard]] virtual Expected<void>
+ insertUnconditionalBranch(MachineBasicBlock &Block, MachineBasicBlock &Target,
+ MachineFunction &Function,
+ const TargetDescription &TargetDescription) const = 0;
+
+ [[nodiscard]] virtual Expected<void> validateCopy(Register Destination,
+ SubRegIndex DestinationSubReg, Register Source,
+ SubRegIndex SourceSubReg,
+ const MachineFunction &Function,
+ const TargetDescription &Target) const = 0;
+
+ [[nodiscard]] virtual Expected<bool> tryConvertToThreeAddress(MachineInstr &, std::size_t,
+ std::size_t, MachineFunction &,
+ const TargetDescription &) const {
+ return false;
+ }
+};
+
} // namespace rcc
#endif // RCC_CODEGEN_TARGETCODEGEN_H
diff --git a/backend/include/rcc/CodeGen/TargetDescription.h b/backend/include/rcc/CodeGen/TargetDescription.h
index c2a4133..7e41a58 100644
--- a/backend/include/rcc/CodeGen/TargetDescription.h
+++ b/backend/include/rcc/CodeGen/TargetDescription.h
@@ -72,6 +72,9 @@ public:
std::span<const MachineMemOperand *const> MemOperands) const;
[[nodiscard]] Expected<void> validateInstruction(const MachineInstr &Instruction,
const MachineRegisterInfo &RegInfo) const;
+ [[nodiscard]] Expected<void> validateTieCompatibility(const MachineOperand &Def,
+ const MachineOperand &Use,
+ const MachineRegisterInfo &RegInfo) const;
[[nodiscard]] Expected<void> validateCFIInfo(const MachineCFIInfo &Info) const;
[[nodiscard]] Expected<void> validateFrameInfo(const MachineFrameInfo &Info) const;
[[nodiscard]] Expected<void> validateRegisterInfo(const MachineRegisterInfo &RegInfo) const;
@@ -95,10 +98,6 @@ private:
const VirtualRegisterInfo &Info) const;
[[nodiscard]] std::optional<RegisterClassID>
effectiveRegisterClass(const MachineOperand &Operand, const MachineRegisterInfo &RegInfo) const;
- [[nodiscard]] Expected<void> validateTieCompatibility(const MachineOperand &Def,
- const MachineOperand &Use,
- const MachineRegisterInfo &RegInfo) const;
-
InstructionSet Instructions;
TargetRegisterInfo Registers;
TargetMIRTextInfo MIRText;
diff --git a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
index b06f20d..4db60f7 100644
--- a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
+++ b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
@@ -10,6 +10,7 @@ namespace rcc::riscv {
[[nodiscard]] const TargetLegalizerInfo &legalizerInfo() noexcept;
[[nodiscard]] const TargetRegisterBankInfo &registerBankInfo() noexcept;
[[nodiscard]] const TargetInstructionSelector &instructionSelector() noexcept;
+[[nodiscard]] const TargetSSAInfo &ssaInfo() noexcept;
} // namespace rcc::riscv
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index f2c81f2..5cff572 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -29,6 +29,7 @@ set(
MachinePass.cpp
MachinePipelinePasses.cpp
MachineRegisterInfo.cpp
+ MachineSSAExit.cpp
MachineVerifier.cpp
MachineFunctionProperties.cpp
MachineFunctionRecords.cpp
@@ -71,6 +72,7 @@ set(
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePipelinePasses.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetCodeGen.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineSSAExit.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineVerifier.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionRecords.h"
@@ -141,6 +143,7 @@ rcc_backend_register_format_files(
"${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp"
@@ -182,6 +185,7 @@ rcc_backend_register_tidy_files(
"${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionRecords.cpp"
diff --git a/backend/lib/CodeGen/GenericOpcodes.cpp b/backend/lib/CodeGen/GenericOpcodes.cpp
index 0b0e0fe..1394507 100644
--- a/backend/lib/CodeGen/GenericOpcodes.cpp
+++ b/backend/lib/CodeGen/GenericOpcodes.cpp
@@ -102,7 +102,7 @@ using GO = GenericOpcode;
OperandDescriptor Result;
Result.Kinds = {MachineOperand::Kind::Register};
Result.RegisterRole = Role;
- Result.TypeConstraint = OperandTypeConstraint{std::move(Kinds), Group};
+ Result.TypeConstraint = OperandTypeConstraint{Kinds, Group};
return Result;
}
@@ -146,6 +146,11 @@ using GO = GenericOpcode;
return Descriptor;
}
+[[nodiscard]] OperandDescriptor registeredTargetFlags(OperandDescriptor Descriptor) {
+ Descriptor.AllowAnyTargetFlags = true;
+ return Descriptor;
+}
+
class DescriptorRegistry final {
public:
DescriptorRegistry() {
@@ -158,7 +163,7 @@ public:
#undef RCC_CORE_OPCODE
}
- void configure(std::initializer_list<GO> Opcodes, std::vector<OperandDescriptor> Operands,
+ void configure(std::initializer_list<GO> Opcodes, const std::vector<OperandDescriptor> &Operands,
std::size_t NumDefs, std::initializer_list<InstructionFlag> Flags = {},
bool Variadic = false, std::size_t MinimumRepetitions = 0,
bool RequiresMemoryOperands = false, PseudoOwner Owner = PseudoOwner::None,
@@ -322,9 +327,10 @@ private:
auto Info = RegInfo.virtualRegisterInfo(*Reg);
if (!Info)
return std::unexpected(Info.error());
- if (!Info->get().Type)
+ const std::optional<LLT> &Type = Info->get().Type;
+ if (!Type)
return semanticError("generic virtual register is missing its LLT");
- Types[Index] = *Info->get().Type;
+ Types[Index] = Type.value();
}
const auto TypeAt = [&Types](std::size_t Index) -> LLT { return *Types[Index]; };
@@ -773,7 +779,7 @@ private:
}
case GO::G_INTRINSIC_FPTRUNC_ROUND: {
const auto Rounding = plainImmediate(Operands[2]);
- if (!Rounding || !((*Rounding >= 0 && *Rounding <= 4) || *Rounding == 7))
+ if (!Rounding || *Rounding < 0 || (*Rounding > 4 && *Rounding != 7))
return semanticError("floating truncation rounding mode is invalid");
return VerifyWidthChange(false);
}
@@ -980,14 +986,17 @@ private:
void configureCoreOpcodes(DescriptorRegistry &Registry) {
const auto RegDef = untypedRegister(RegisterOperandRole::Def);
const auto RegUse = untypedRegister(RegisterOperandRole::Use);
+ const auto TransferDef = registeredTargetFlags(RegDef);
+ const auto TransferUse = registeredTargetFlags(RegUse);
const auto Any = anyOperand();
const auto VariadicAny = repeated(Any);
const auto VariadicUse = repeated(RegUse);
- Registry.configure({GO::PHI},
- {RegDef, VariadicUse, repeated(kind(MachineOperand::Kind::BasicBlock))}, 1,
- {InstructionFlag::Phi}, true, 1, false, PseudoOwner::PhiElimination,
- PipelineStage::SSAEliminated);
+ Registry.configure(
+ {GO::PHI},
+ {TransferDef, repeated(TransferUse), repeated(kind(MachineOperand::Kind::BasicBlock))}, 1,
+ {InstructionFlag::Phi}, true, 1, false, PseudoOwner::PhiElimination,
+ PipelineStage::SSAEliminated);
Registry.configure({GO::INLINEASM}, {VariadicAny}, 0,
{InstructionFlag::ProducesCode, InstructionFlag::TerminalEmission,
InstructionFlag::UnmodeledSideEffects},
@@ -1004,10 +1013,11 @@ void configureCoreOpcodes(DescriptorRegistry &Registry) {
Registry.configure({GO::KILL}, {VariadicUse}, 0, {InstructionFlag::Meta}, true);
Registry.configure({GO::EXTRACT_SUBREG}, {RegDef, RegUse, immediate()}, 1, {}, false, 0, false,
PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized);
- Registry.configure({GO::INSERT_SUBREG}, {RegDef, RegUse, RegUse, immediate()}, 1, {}, false, 0,
- false, PseudoOwner::TwoAddressRewrite, PipelineStage::TiedOpsRewritten);
+ Registry.configure({GO::INSERT_SUBREG}, {TransferDef, TransferUse, TransferUse, immediate()}, 1,
+ {}, false, 0, false, PseudoOwner::TwoAddressRewrite,
+ PipelineStage::TiedOpsRewritten);
Registry.tie(GO::INSERT_SUBREG, 0, 1);
- Registry.configure({GO::IMPLICIT_DEF}, {RegDef}, 1,
+ Registry.configure({GO::IMPLICIT_DEF}, {TransferDef}, 1,
{InstructionFlag::Meta, InstructionFlag::Rematerializable});
Registry.configure({GO::INIT_UNDEF}, {RegDef}, 1, {}, false, 0, false,
PseudoOwner::RegisterAllocator, PipelineStage::RegisterAllocated);
@@ -1019,10 +1029,10 @@ void configureCoreOpcodes(DescriptorRegistry &Registry) {
{VariadicAny}, 0, {InstructionFlag::Meta}, true);
Registry.configure({GO::DBG_LABEL}, {kind(MachineOperand::Kind::Metadata)}, 0,
{InstructionFlag::Meta});
- Registry.configure({GO::REG_SEQUENCE}, {RegDef, repeated(RegUse), repeated(immediate())}, 1, {},
- true, 1, false, PseudoOwner::TwoAddressRewrite,
- PipelineStage::TiedOpsRewritten);
- Registry.configure({GO::COPY}, {RegDef, RegUse}, 1, {}, false, 0, false,
+ Registry.configure({GO::REG_SEQUENCE},
+ {TransferDef, repeated(TransferUse), repeated(immediate())}, 1, {}, true, 1,
+ false, PseudoOwner::TwoAddressRewrite, PipelineStage::TiedOpsRewritten);
+ Registry.configure({GO::COPY}, {TransferDef, TransferUse}, 1, {}, false, 0, false,
PseudoOwner::PostRAExpansion, PipelineStage::PostRAFinalized);
Registry.configure({GO::COPY_LANEMASK}, {RegDef, RegUse, kind(MachineOperand::Kind::LaneMask)}, 1,
{}, false, 0, false, PseudoOwner::PostRAExpansion,
@@ -1170,10 +1180,13 @@ void configureGenericOpcodes(DescriptorRegistry &Registry) {
InstructionFlag::Commutable);
Registry.configure({GO::G_SDIVREM, GO::G_UDIVREM}, {IntDef0, IntDef0, IntUse0, IntUse0}, 2);
- Registry.configure({GO::G_IMPLICIT_DEF}, {AnyDef0}, 1);
- Registry.configure({GO::G_PHI},
- {AnyDef0, repeated(AnyUse0), repeated(kind(MachineOperand::Kind::BasicBlock))},
- 1, {InstructionFlag::Phi}, true, 1);
+ const auto TransferDef0 = registeredTargetFlags(AnyDef0);
+ const auto TransferUse0 = registeredTargetFlags(AnyUse0);
+ Registry.configure({GO::G_IMPLICIT_DEF}, {TransferDef0}, 1);
+ Registry.configure(
+ {GO::G_PHI},
+ {TransferDef0, repeated(TransferUse0), repeated(kind(MachineOperand::Kind::BasicBlock))}, 1,
+ {InstructionFlag::Phi}, true, 1);
Registry.configure({GO::G_FRAME_INDEX},
{ScalarPointerDef0, kind(MachineOperand::Kind::FrameIndex)}, 1);
Registry.configure({GO::G_GLOBAL_VALUE},
diff --git a/backend/lib/CodeGen/InstructionDescriptor.cpp b/backend/lib/CodeGen/InstructionDescriptor.cpp
index 57400d6..5aec744 100644
--- a/backend/lib/CodeGen/InstructionDescriptor.cpp
+++ b/backend/lib/CodeGen/InstructionDescriptor.cpp
@@ -420,11 +420,12 @@ Expected<void> InstructionSet::validateExplicitOperands(const InstructionDescrip
auto Info = RegInfo.virtualRegisterInfo(*Reg);
if (!Info)
return std::unexpected(Info.error());
- if (!Info->get().Type) {
+ const std::optional<LLT> &RegisterType = Info->get().Type;
+ if (!RegisterType) {
return makeUnexpected(ErrorCode::VerificationError,
"typed instruction operand virtual register has no LLT");
}
- const LLT Type = *Info->get().Type;
+ const LLT Type = RegisterType.value();
if (!OperandDesc.TypeConstraint->Kinds.contains(Type.kind())) {
return makeUnexpected(ErrorCode::VerificationError,
"instruction operand LLT kind is not permitted by its descriptor");
@@ -587,7 +588,8 @@ Expected<void> InstructionSet::validateOperand(const OperandDescriptor &Descript
return makeUnexpected(ErrorCode::VerificationError,
"instruction operand kind does not match its descriptor");
}
- if ((Operand.targetFlags() & ~Descriptor.AllowedTargetFlags) != 0) {
+ if (!Descriptor.AllowAnyTargetFlags &&
+ (Operand.targetFlags() & ~Descriptor.AllowedTargetFlags) != 0) {
return makeUnexpected(ErrorCode::VerificationError,
"instruction operand uses unregistered target flags");
}
diff --git a/backend/lib/CodeGen/MachineCFGUpdater.cpp b/backend/lib/CodeGen/MachineCFGUpdater.cpp
index c78e318..4aacdf5 100644
--- a/backend/lib/CodeGen/MachineCFGUpdater.cpp
+++ b/backend/lib/CodeGen/MachineCFGUpdater.cpp
@@ -2,18 +2,108 @@
#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/GenericOpcodes.h"
#include "rcc/CodeGen/MachineBasicBlock.h"
#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
#include <algorithm>
#include <cstddef>
#include <optional>
+#include <span>
#include <utility>
#include <vector>
namespace rcc {
namespace {
+struct PhiIncomingEdit final {
+ MachineInstr *Phi = nullptr;
+ std::size_t ValueIndex = 0;
+};
+
+[[nodiscard]] bool isKnownPhi(const MachineInstr &Instruction) noexcept {
+ return Instruction.opcode() == opcode(GenericOpcode::PHI) ||
+ Instruction.opcode() == opcode(GenericOpcode::G_PHI);
+}
+
+[[nodiscard]] bool containsKnownPhi(const MachineBasicBlock &Block) noexcept {
+ for (const MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ if (isKnownPhi(*Instruction))
+ return true;
+ }
+ return false;
+}
+
+[[nodiscard]] Expected<std::vector<PhiIncomingEdit>>
+collectPhiIncomingEdits(MachineBasicBlock &Block, const MachineBasicBlock &Predecessor) {
+ std::vector<PhiIncomingEdit> Result;
+ for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ if (!isKnownPhi(*Instruction))
+ continue;
+ if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "CFG update encountered a malformed PHI instruction");
+ }
+
+ std::optional<std::size_t> Match;
+ for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) {
+ const MachineOperand *Value = Instruction->operandAt(Index);
+ const MachineOperand *BlockOperand = Instruction->operandAt(Index + 1U);
+ const Register *Reg = Value == nullptr ? nullptr : Value->getIf<Register>();
+ const BasicBlockOperand *Incoming =
+ BlockOperand == nullptr ? nullptr : BlockOperand->getIf<BasicBlockOperand>();
+ if (Reg == nullptr || Incoming == nullptr || Incoming->Block == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "CFG update encountered malformed PHI incoming operands");
+ }
+ if (Incoming->Block != &Predecessor)
+ continue;
+ if (Match) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "CFG update encountered duplicate PHI incoming blocks");
+ }
+ Match = Index;
+ }
+ if (!Match) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "CFG edge has no corresponding PHI incoming value");
+ }
+ Result.push_back(PhiIncomingEdit{Instruction, *Match});
+ }
+ return Result;
+}
+
+[[nodiscard]] Expected<void> erasePhiIncoming(std::span<const PhiIncomingEdit> Edits) {
+ for (const PhiIncomingEdit &Edit : Edits) {
+ auto BlockErased = Edit.Phi->eraseOperand(Edit.ValueIndex + 1U);
+ if (!BlockErased)
+ return std::unexpected(BlockErased.error());
+ auto ValueErased = Edit.Phi->eraseOperand(Edit.ValueIndex);
+ if (!ValueErased)
+ return std::unexpected(ValueErased.error());
+ }
+ return {};
+}
+
+[[nodiscard]] Expected<void> rewritePhiIncoming(std::span<const PhiIncomingEdit> Edits,
+ MachineBasicBlock &NewPredecessor) {
+ for (const PhiIncomingEdit &Edit : Edits) {
+ MachineOperand *BlockOperand = Edit.Phi->operandAt(Edit.ValueIndex + 1U);
+ if (BlockOperand == nullptr) {
+ return makeUnexpected(ErrorCode::InternalError,
+ "PHI incoming operand disappeared during CFG update");
+ }
+ auto Rewritten = BlockOperand->setBasicBlock(NewPredecessor);
+ if (!Rewritten)
+ return std::unexpected(Rewritten.error());
+ }
+ return {};
+}
+
[[nodiscard]] std::optional<std::size_t> findSuccessorIndex(const MachineBasicBlock &From,
const MachineBasicBlock &To) {
const auto Successors = From.successors();
@@ -24,6 +114,39 @@ namespace {
return std::nullopt;
}
+[[nodiscard]] Expected<void> validateOutgoingEdges(MachineBasicBlock &From) {
+ for (const MachineSuccessor &Successor : From.successors()) {
+ if (Successor.Block == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError, "CFG successor is null");
+ }
+ if (std::ranges::find(Successor.Block->predecessors(), &From) ==
+ Successor.Block->predecessors().end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "CFG successor has no reciprocal predecessor");
+ }
+ auto PhiEdits = collectPhiIncomingEdits(*Successor.Block, From);
+ if (!PhiEdits)
+ return std::unexpected(PhiEdits.error());
+ }
+ return {};
+}
+
+[[nodiscard]] Expected<void> validateIncomingEdges(MachineBasicBlock &To) {
+ for (MachineBasicBlock *Predecessor : To.predecessors()) {
+ if (Predecessor == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError, "CFG predecessor is null");
+ }
+ if (!findSuccessorIndex(*Predecessor, To)) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "CFG predecessor has no reciprocal successor");
+ }
+ auto PhiEdits = collectPhiIncomingEdits(To, *Predecessor);
+ if (!PhiEdits)
+ return std::unexpected(PhiEdits.error());
+ }
+ return {};
+}
+
} // namespace
Expected<void> MachineCFGUpdater::verifyOwnership(const MachineBasicBlock &Block) const {
@@ -50,6 +173,15 @@ Expected<void> MachineCFGUpdater::addSuccessor(MachineBasicBlock &From, MachineB
return {};
}
+ if (containsKnownPhi(To)) {
+ auto PhiEdits = collectPhiIncomingEdits(To, From);
+ if (!PhiEdits) {
+ return makeUnexpected(
+ ErrorCode::InvalidArgument,
+ "adding a predecessor to a PHI block requires explicit incoming values");
+ }
+ }
+
From.Successors.push_back(MachineSuccessor{&To, Probability});
if (std::ranges::find(To.Predecessors, &From) == To.Predecessors.end())
To.Predecessors.push_back(&From);
@@ -68,13 +200,20 @@ Expected<void> MachineCFGUpdater::removeSuccessor(MachineBasicBlock &From, Machi
if (!Successor) {
return makeUnexpected(ErrorCode::InvalidArgument, "CFG successor edge is not present");
}
- From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Successor));
-
const auto Predecessor = std::ranges::find(To.Predecessors, &From);
if (Predecessor == To.Predecessors.end()) {
return makeUnexpected(ErrorCode::VerificationError,
"CFG successor has no reciprocal predecessor");
}
+
+ auto PhiEdits = collectPhiIncomingEdits(To, From);
+ if (!PhiEdits)
+ return std::unexpected(PhiEdits.error());
+ auto PhiResult = erasePhiIncoming(*PhiEdits);
+ if (!PhiResult)
+ return std::unexpected(PhiResult.error());
+
+ From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Successor));
To.Predecessors.erase(Predecessor);
return {};
}
@@ -101,18 +240,95 @@ Expected<void> MachineCFGUpdater::replaceSuccessor(MachineBasicBlock &From,
}
const BranchProbability Probability = From.Successors[*Existing].Probability;
- auto RemoveResult = removeSuccessor(From, OldTarget);
- if (!RemoveResult)
- return std::unexpected(RemoveResult.error());
- auto AddResult = addSuccessor(From, NewTarget, Probability);
- if (!AddResult) {
- auto RestoreResult = addSuccessor(From, OldTarget, Probability);
- if (!RestoreResult) {
- return makeUnexpected(ErrorCode::InternalError,
- "failed to restore CFG edge after replacement failure");
+ const auto OldPredecessor = std::ranges::find(OldTarget.Predecessors, &From);
+ if (OldPredecessor == OldTarget.Predecessors.end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "replaced CFG successor has no reciprocal predecessor");
+ }
+ auto OldPhiEdits = collectPhiIncomingEdits(OldTarget, From);
+ if (!OldPhiEdits)
+ return std::unexpected(OldPhiEdits.error());
+
+ const auto NewEdge = findSuccessorIndex(From, NewTarget);
+ const auto NewPredecessor = std::ranges::find(NewTarget.Predecessors, &From);
+ if (NewEdge) {
+ if (NewPredecessor == NewTarget.Predecessors.end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "replacement target has no reciprocal predecessor");
+ }
+ auto NewPhiEdits = collectPhiIncomingEdits(NewTarget, From);
+ if (!NewPhiEdits)
+ return std::unexpected(NewPhiEdits.error());
+ } else {
+ if (NewPredecessor != NewTarget.Predecessors.end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "replacement target has a predecessor without a reciprocal edge");
+ }
+ if (containsKnownPhi(NewTarget)) {
+ auto NewPhiEdits = collectPhiIncomingEdits(NewTarget, From);
+ if (!NewPhiEdits) {
+ return makeUnexpected(
+ ErrorCode::InvalidArgument,
+ "redirecting an edge to a PHI block requires explicit incoming values");
+ }
}
- return std::unexpected(AddResult.error());
}
+ auto PhiResult = erasePhiIncoming(*OldPhiEdits);
+ if (!PhiResult)
+ return std::unexpected(PhiResult.error());
+ OldTarget.Predecessors.erase(OldPredecessor);
+ if (NewEdge) {
+ From.Successors[*NewEdge].Probability =
+ From.Successors[*NewEdge].Probability.saturatingAdd(Probability);
+ From.Successors.erase(From.Successors.begin() + static_cast<std::ptrdiff_t>(*Existing));
+ } else {
+ From.Successors[*Existing].Block = &NewTarget;
+ if (std::ranges::find(NewTarget.Predecessors, &From) == NewTarget.Predecessors.end())
+ NewTarget.Predecessors.push_back(&From);
+ }
+ return {};
+}
+
+Expected<void> MachineCFGUpdater::splitEdge(MachineBasicBlock &From, MachineBasicBlock &To,
+ MachineBasicBlock &EdgeBlock) {
+ auto FromOwnership = verifyOwnership(From);
+ if (!FromOwnership)
+ return std::unexpected(FromOwnership.error());
+ auto ToOwnership = verifyOwnership(To);
+ if (!ToOwnership)
+ return std::unexpected(ToOwnership.error());
+ auto EdgeOwnership = verifyOwnership(EdgeBlock);
+ if (!EdgeOwnership)
+ return std::unexpected(EdgeOwnership.error());
+ if (&From == &To || &From == &EdgeBlock || &To == &EdgeBlock) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "edge split requires three distinct basic blocks");
+ }
+ if (!EdgeBlock.isLinked() || EdgeBlock.firstInstruction() != nullptr ||
+ !EdgeBlock.predecessors().empty() || !EdgeBlock.successors().empty()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "edge split block must be linked, empty, and disconnected");
+ }
+
+ const auto Successor = findSuccessorIndex(From, To);
+ if (!Successor)
+ return makeUnexpected(ErrorCode::InvalidArgument, "split CFG edge is not present");
+ auto Predecessor = std::ranges::find(To.Predecessors, &From);
+ if (Predecessor == To.Predecessors.end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "split CFG edge has no reciprocal predecessor");
+ }
+ auto PhiEdits = collectPhiIncomingEdits(To, From);
+ if (!PhiEdits)
+ return std::unexpected(PhiEdits.error());
+
+ auto PhiResult = rewritePhiIncoming(*PhiEdits, EdgeBlock);
+ if (!PhiResult)
+ return std::unexpected(PhiResult.error());
+ From.Successors[*Successor].Block = &EdgeBlock;
+ *Predecessor = &EdgeBlock;
+ EdgeBlock.Predecessors.push_back(&From);
+ EdgeBlock.Successors.push_back(MachineSuccessor{&To, BranchProbability::one()});
return {};
}
@@ -145,15 +361,67 @@ Expected<void> MachineCFGUpdater::transferSuccessors(MachineBasicBlock &From,
if (&From == &To)
return {};
- const std::vector<MachineSuccessor> Successors = From.Successors;
- for (const MachineSuccessor &Successor : Successors) {
- auto RemoveResult = removeSuccessor(From, *Successor.Block);
- if (!RemoveResult)
- return std::unexpected(RemoveResult.error());
- auto AddResult = addSuccessor(To, *Successor.Block, Successor.Probability);
- if (!AddResult)
- return std::unexpected(AddResult.error());
+ struct Transfer final {
+ MachineSuccessor Successor;
+ std::vector<PhiIncomingEdit> PhiEdits;
+ bool MergeExisting = false;
+ };
+ std::vector<Transfer> Transfers;
+ Transfers.reserve(From.Successors.size());
+ for (const MachineSuccessor &Successor : From.Successors) {
+ if (Successor.Block == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError, "transferred CFG successor is null");
+ }
+ if (std::ranges::find(Successor.Block->Predecessors, &From) ==
+ Successor.Block->Predecessors.end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "transferred CFG successor has no reciprocal predecessor");
+ }
+ auto PhiEdits = collectPhiIncomingEdits(*Successor.Block, From);
+ if (!PhiEdits)
+ return std::unexpected(PhiEdits.error());
+ const bool MergeExisting = findSuccessorIndex(To, *Successor.Block).has_value();
+ const auto ToPredecessor = std::ranges::find(Successor.Block->Predecessors, &To);
+ if (MergeExisting) {
+ if (ToPredecessor == Successor.Block->Predecessors.end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "transfer target edge has no reciprocal predecessor");
+ }
+ auto ExistingPhiEdits = collectPhiIncomingEdits(*Successor.Block, To);
+ if (!ExistingPhiEdits)
+ return std::unexpected(ExistingPhiEdits.error());
+ } else if (ToPredecessor != Successor.Block->Predecessors.end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "transfer target is a predecessor without a reciprocal edge");
+ }
+ Transfers.push_back(Transfer{Successor, std::move(*PhiEdits), MergeExisting});
}
+
+ for (Transfer &TransferValue : Transfers) {
+ MachineBasicBlock &Successor = *TransferValue.Successor.Block;
+ auto OldPredecessor = std::ranges::find(Successor.Predecessors, &From);
+ if (TransferValue.MergeExisting) {
+ auto PhiResult = erasePhiIncoming(TransferValue.PhiEdits);
+ if (!PhiResult)
+ return std::unexpected(PhiResult.error());
+ Successor.Predecessors.erase(OldPredecessor);
+ const std::optional<std::size_t> Existing = findSuccessorIndex(To, Successor);
+ if (!Existing) {
+ return makeUnexpected(ErrorCode::InternalError,
+ "preflighted transfer target edge disappeared");
+ }
+ To.Successors[Existing.value()].Probability =
+ To.Successors[Existing.value()].Probability.saturatingAdd(
+ TransferValue.Successor.Probability);
+ } else {
+ auto PhiResult = rewritePhiIncoming(TransferValue.PhiEdits, To);
+ if (!PhiResult)
+ return std::unexpected(PhiResult.error());
+ *OldPredecessor = &To;
+ To.Successors.push_back(TransferValue.Successor);
+ }
+ }
+ From.Successors.clear();
return {};
}
@@ -162,6 +430,13 @@ Expected<void> MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) {
if (!Ownership)
return std::unexpected(Ownership.error());
+ auto Outgoing = validateOutgoingEdges(Block);
+ if (!Outgoing)
+ return std::unexpected(Outgoing.error());
+ auto Incoming = validateIncomingEdges(Block);
+ if (!Incoming)
+ return std::unexpected(Incoming.error());
+
const std::vector<MachineSuccessor> Successors = Block.Successors;
for (const MachineSuccessor &Successor : Successors) {
auto Result = removeSuccessor(Block, *Successor.Block);
@@ -178,4 +453,70 @@ Expected<void> MachineCFGUpdater::disconnectBlock(MachineBasicBlock &Block) {
return {};
}
+Expected<MachineBasicBlock *> MachineCFGUpdater::splitBlock(MachineBasicBlock &Block,
+ MachineInstr &SplitBefore) {
+ auto Ownership = verifyOwnership(Block);
+ if (!Ownership)
+ return std::unexpected(Ownership.error());
+ if (!Block.isLinked() || SplitBefore.parent() != &Block) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "split point is not linked to the requested basic block");
+ }
+ bool MovesPhi = false;
+ for (const MachineInstr *Instruction = &SplitBefore; Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ MovesPhi |= isKnownPhi(*Instruction);
+ }
+ if (MovesPhi) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "a basic block cannot be split inside its PHI region");
+ }
+
+ auto Outgoing = validateOutgoingEdges(Block);
+ if (!Outgoing)
+ return std::unexpected(Outgoing.error());
+
+ auto NewBlockResult = Function->createBasicBlock();
+ if (!NewBlockResult)
+ return std::unexpected(NewBlockResult.error());
+ MachineBasicBlock *NewBlock = *NewBlockResult;
+ Expected<void> Inserted = Block.next() == nullptr
+ ? Function->appendBlock(*NewBlock)
+ : Function->insertBlockBefore(*Block.next(), *NewBlock);
+ if (!Inserted)
+ return std::unexpected(Inserted.error());
+
+ MachineInstr *Instruction = &SplitBefore;
+ while (Instruction != nullptr) {
+ MachineInstr *Next = Instruction->next();
+ auto Removed = Block.removeInstruction(*Instruction);
+ if (!Removed)
+ return std::unexpected(Removed.error());
+ auto Appended = NewBlock->appendInstruction(*Instruction);
+ if (!Appended)
+ return std::unexpected(Appended.error());
+ Instruction = Next;
+ }
+
+ auto Transferred = transferSuccessors(Block, *NewBlock);
+ if (!Transferred)
+ return std::unexpected(Transferred.error());
+ auto Connected = addSuccessor(Block, *NewBlock, BranchProbability::one());
+ if (!Connected)
+ return std::unexpected(Connected.error());
+ return NewBlock;
+}
+
+Expected<void> MachineCFGUpdater::deleteBlock(MachineBasicBlock &Block) {
+ auto Ownership = verifyOwnership(Block);
+ if (!Ownership)
+ return std::unexpected(Ownership.error());
+ if (!Block.isLinked())
+ return makeUnexpected(ErrorCode::InvalidArgument, "deleted CFG block is not linked");
+ auto Disconnected = disconnectBlock(Block);
+ if (!Disconnected)
+ return std::unexpected(Disconnected.error());
+ return Function->removeBlock(Block);
+}
+
} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineOperand.cpp b/backend/lib/CodeGen/MachineOperand.cpp
index ae46505..43a4f91 100644
--- a/backend/lib/CodeGen/MachineOperand.cpp
+++ b/backend/lib/CodeGen/MachineOperand.cpp
@@ -2,6 +2,7 @@
#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
#include "rcc/CodeGen/MachineFunction.h"
#include "rcc/CodeGen/MachineInstr.h"
#include "rcc/CodeGen/MachineRegisterInfo.h"
@@ -172,8 +173,7 @@ std::string IntegerImmediate::toUnsignedDecimal() const {
return "0";
std::vector<std::uint64_t> Remaining = Words;
std::string Digits;
- while (!std::ranges::all_of(Remaining,
- [](std::uint64_t Word) { return Word == 0; })) {
+ while (!std::ranges::all_of(Remaining, [](std::uint64_t Word) { return Word == 0; })) {
unsigned __int128 Remainder = 0;
for (auto Iterator = Remaining.rbegin(); Iterator != Remaining.rend(); ++Iterator) {
const unsigned __int128 Dividend = (Remainder << 64U) | *Iterator;
@@ -537,6 +537,17 @@ Expected<void> MachineOperand::setSubReg(SubRegIndex SubReg) {
return {};
}
+Expected<void> MachineOperand::setBasicBlock(MachineBasicBlock &Block) {
+ if (OperandKind != Kind::BasicBlock)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "setBasicBlock requires a basic-block operand");
+ if (Parent != nullptr && &Block.function() != &Parent->function())
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "basic-block operand references another machine function");
+ std::get<BasicBlockOperand>(Storage).Block = &Block;
+ return {};
+}
+
MachineOperand MachineOperand::cloneDetached() const {
MachineOperand Result(OperandKind, Storage, TargetFlags);
Result.RegFlags = RegFlags;
diff --git a/backend/lib/CodeGen/MachineSSAExit.cpp b/backend/lib/CodeGen/MachineSSAExit.cpp
new file mode 100644
index 0000000..e77bb2a
--- /dev/null
+++ b/backend/lib/CodeGen/MachineSSAExit.cpp
@@ -0,0 +1,1090 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineSSAExit.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionCloner.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 <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <string>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+struct EdgeKey final {
+ const MachineBasicBlock *From = nullptr;
+ const MachineBasicBlock *To = nullptr;
+
+ friend bool operator==(const EdgeKey &, const EdgeKey &) noexcept = default;
+};
+
+struct EdgeKeyHash final {
+ [[nodiscard]] std::size_t operator()(const EdgeKey &Key) const noexcept {
+ const std::size_t FromHash = std::hash<const MachineBasicBlock *>{}(Key.From);
+ const std::size_t ToHash = std::hash<const MachineBasicBlock *>{}(Key.To);
+ return FromHash ^ (ToHash << 1U);
+ }
+};
+
+struct RegisterValue final {
+ Register Reg;
+ SubRegIndex SubReg;
+ RegisterOperandFlags Flags;
+ std::uint32_t TargetFlags = 0;
+};
+
+struct PhiIncoming final {
+ RegisterValue Value;
+ MachineBasicBlock *Predecessor = nullptr;
+ bool IsUndef = false;
+};
+
+struct PhiPlan final {
+ MachineInstr *Instruction = nullptr;
+ RegisterValue Destination;
+ Register FreshIncoming;
+ std::vector<PhiIncoming> IncomingValues;
+};
+
+[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) {
+ Prefix.append(Source.message());
+ return Error(Source.code(), std::move(Prefix));
+}
+
+[[nodiscard]] Expected<void> requireProperties(const MachineFunction &Function,
+ const MachinePassContract &Contract) {
+ const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties());
+ if (Missing.empty())
+ return {};
+ return makeUnexpected(ErrorCode::VerificationError,
+ Contract.Name + " requires properties: " + Missing.toString());
+}
+
+[[nodiscard]] bool isPhi(const MachineInstr &Instruction, const TargetDescription &Target) {
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+ return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Phi);
+}
+
+[[nodiscard]] bool isMeta(const MachineInstr &Instruction, const TargetDescription &Target) {
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+ return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Meta);
+}
+
+[[nodiscard]] MachineInstr *firstTerminator(MachineBasicBlock &Block,
+ const TargetDescription &Target) {
+ for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+ if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator))
+ return Instruction;
+ }
+ return nullptr;
+}
+
+[[nodiscard]] MachineInstr *firstCodeAfterPhiRegion(MachineBasicBlock &Block,
+ const TargetDescription &Target) {
+ for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ if (!isPhi(*Instruction, Target) && !isMeta(*Instruction, Target))
+ return Instruction;
+ }
+ return nullptr;
+}
+
+[[nodiscard]] RegisterOperandFlags generatedDefFlags(RegisterOperandFlags Original) noexcept {
+ RegisterOperandFlags Result;
+ if (Original.has(RegisterOperandFlag::Undef))
+ Result.set(RegisterOperandFlag::Undef);
+ return Result;
+}
+
+[[nodiscard]] Expected<void> copyDebugLocation(MachineInstrBuilder &Builder,
+ const MachineInstr *Source) {
+ if (Source == nullptr || !Source->debugLocation())
+ return {};
+ return Builder.setDebugLocation(*Source->debugLocation());
+}
+
+[[nodiscard]] Expected<Register> cloneRegisterConstraints(MachineFunction &Function,
+ Register Source) {
+ if (!Source.isVirtual()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "SSA deconstruction requires a virtual PHI destination");
+ }
+ auto SourceInfo = Function.registerInfo().virtualRegisterInfo(Source);
+ if (!SourceInfo)
+ return std::unexpected(SourceInfo.error());
+ const VirtualRegisterInfo Info = SourceInfo->get();
+
+ auto Fresh = Function.registerInfo().createVirtualRegister();
+ if (!Fresh)
+ return std::unexpected(Fresh.error());
+ if (Info.Type) {
+ auto SetType = Function.registerInfo().setType(*Fresh, *Info.Type);
+ if (!SetType)
+ return std::unexpected(SetType.error());
+ }
+ if (Info.Bank) {
+ auto SetBank = Function.registerInfo().setRegisterBank(*Fresh, *Info.Bank);
+ if (!SetBank)
+ return std::unexpected(SetBank.error());
+ }
+ if (Info.RegClass) {
+ auto SetClass = Function.registerInfo().setRegisterClass(*Fresh, *Info.RegClass);
+ if (!SetClass)
+ return std::unexpected(SetClass.error());
+ }
+ for (const PhysicalRegister Hint : Info.AllocationHints) {
+ auto AddedHint = Function.registerInfo().addAllocationHint(*Fresh, Hint);
+ if (!AddedHint)
+ return std::unexpected(AddedHint.error());
+ }
+ if (Info.TargetFlags != 0) {
+ auto SetFlags = Function.registerInfo().setTargetRegisterFlags(*Fresh, Info.TargetFlags);
+ if (!SetFlags)
+ return std::unexpected(SetFlags.error());
+ }
+ return *Fresh;
+}
+
+[[nodiscard]] Expected<MachineInstr *>
+buildCopy(MachineFunction &Function, const TargetDescription &Target,
+ const TargetSSAInfo &TargetInfo, MachineBasicBlock &Block, MachineInstr *Before,
+ RegisterValue Destination, RegisterValue Source, const MachineInstr *DebugSource) {
+ auto Legality = TargetInfo.validateCopy(Destination.Reg, Destination.SubReg, Source.Reg,
+ Source.SubReg, Function, Target);
+ if (!Legality)
+ return std::unexpected(prefixedError(Legality.error(), "illegal COPY: "));
+
+ MachineIRBuilder Builder(Function, Target);
+ auto Point =
+ Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Pending = Builder.buildInstr(opcode(GenericOpcode::COPY));
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ auto Def = Pending->addDef(Destination.Reg, generatedDefFlags(Destination.Flags),
+ Destination.SubReg, Destination.TargetFlags);
+ if (!Def)
+ return std::unexpected(Def.error());
+ auto Use = Pending->addUse(Source.Reg, {}, Source.SubReg, Source.TargetFlags);
+ if (!Use)
+ return std::unexpected(Use.error());
+ auto Debug = copyDebugLocation(*Pending, DebugSource);
+ if (!Debug)
+ return std::unexpected(Debug.error());
+ return Pending->build();
+}
+
+[[nodiscard]] Expected<MachineInstr *>
+buildImplicitDef(MachineFunction &Function, const TargetDescription &Target,
+ MachineBasicBlock &Block, MachineInstr *Before, RegisterValue Destination,
+ const MachineInstr *DebugSource) {
+ MachineIRBuilder Builder(Function, Target);
+ auto Point =
+ Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Pending = Builder.buildInstr(opcode(GenericOpcode::IMPLICIT_DEF));
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ auto Def = Pending->addDef(Destination.Reg, generatedDefFlags(Destination.Flags),
+ Destination.SubReg, Destination.TargetFlags);
+ if (!Def)
+ return std::unexpected(Def.error());
+ auto Debug = copyDebugLocation(*Pending, DebugSource);
+ if (!Debug)
+ return std::unexpected(Debug.error());
+ return Pending->build();
+}
+
+[[nodiscard]] bool isImplicitlyUndef(const MachineFunction &Function,
+ const MachineOperand &Operand) {
+ if (Operand.registerFlags().has(RegisterOperandFlag::Undef))
+ return true;
+ const Register *Reg = Operand.getIf<Register>();
+ if (Reg == nullptr || Reg->isNoRegister())
+ return true;
+ if (!Reg->isVirtual())
+ return false;
+ const MachineOperand *Definition = Function.registerInfo().getUniqueVRegDef(*Reg);
+ if (Definition == nullptr || Definition->parent() == nullptr)
+ return false;
+ if (Definition->subReg().value() != 0 && Definition->subReg() != Operand.subReg())
+ return false;
+ const Opcode DefinitionOpcode = Definition->parent()->opcode();
+ return DefinitionOpcode == opcode(GenericOpcode::IMPLICIT_DEF) ||
+ DefinitionOpcode == opcode(GenericOpcode::G_IMPLICIT_DEF) ||
+ Definition->registerFlags().has(RegisterOperandFlag::Undef);
+}
+
+[[nodiscard]] Expected<void> validatePhiValue(const MachineFunction &Function,
+ const TargetDescription &Target,
+ const MachineOperand &Destination,
+ const MachineOperand &Source) {
+ const Register *DestinationReg = Destination.getIf<Register>();
+ const Register *SourceReg = Source.getIf<Register>();
+ if (DestinationReg == nullptr || SourceReg == nullptr)
+ return makeUnexpected(ErrorCode::VerificationError, "PHI operands must name registers");
+ if (SourceReg->isNoRegister())
+ return {};
+
+ if (DestinationReg->isVirtual() && SourceReg->isVirtual()) {
+ auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(*DestinationReg);
+ if (!DestinationInfo)
+ return std::unexpected(DestinationInfo.error());
+ auto SourceInfo = Function.registerInfo().virtualRegisterInfo(*SourceReg);
+ if (!SourceInfo)
+ return std::unexpected(SourceInfo.error());
+ if (DestinationInfo->get().Type && SourceInfo->get().Type &&
+ DestinationInfo->get().Type != SourceInfo->get().Type) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI destination and incoming value types do not match");
+ }
+ }
+ return Target.validateTieCompatibility(Destination, Source, Function.registerInfo());
+}
+
+[[nodiscard]] Expected<std::vector<PhiPlan>> collectPhiPlans(MachineBasicBlock &Block,
+ MachineFunction &Function,
+ const TargetDescription &Target) {
+ std::vector<PhiPlan> Plans;
+ bool SawCode = false;
+ for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+ if (Descriptor == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI elimination encountered an unknown opcode");
+ }
+ if (Instruction->opcode() == opcode(GenericOpcode::G_PHI)) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI elimination requires G_PHI to be selected to PHI");
+ }
+ if (!Descriptor->Flags.has(InstructionFlag::Phi)) {
+ SawCode |= !Descriptor->Flags.has(InstructionFlag::Meta);
+ continue;
+ }
+ if (SawCode) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI instruction appears after the leading PHI/meta region");
+ }
+ if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI must contain a destination and incoming value/block pairs");
+ }
+
+ MachineOperand *DestinationOperand = Instruction->operandAt(0);
+ const Register *Destination =
+ DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+ if (Destination == nullptr || !Destination->isVirtual() || !DestinationOperand->isDef() ||
+ DestinationOperand->isUse() || DestinationOperand->isImplicit()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI destination must be an explicit virtual-register definition");
+ }
+
+ PhiPlan Plan;
+ Plan.Instruction = Instruction;
+ Plan.Destination =
+ RegisterValue{*Destination, DestinationOperand->subReg(),
+ DestinationOperand->registerFlags(), DestinationOperand->targetFlags()};
+ std::unordered_set<MachineBasicBlock *> SeenPredecessors;
+ for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) {
+ MachineOperand *SourceOperand = Instruction->operandAt(Index);
+ MachineOperand *BlockOperand = Instruction->operandAt(Index + 1U);
+ const Register *Source =
+ SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>();
+ const BasicBlockOperand *IncomingBlock =
+ BlockOperand == nullptr ? nullptr : BlockOperand->getIf<BasicBlockOperand>();
+ if (Source == nullptr || SourceOperand == nullptr || !SourceOperand->isUse() ||
+ SourceOperand->isDef() || SourceOperand->isImplicit() || IncomingBlock == nullptr ||
+ IncomingBlock->Block == nullptr || BlockOperand->isImplicit()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI incoming operands must be explicit register/block pairs");
+ }
+ if (std::ranges::find(Block.predecessors(), IncomingBlock->Block) ==
+ Block.predecessors().end()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI incoming block is not a CFG predecessor");
+ }
+ if (!SeenPredecessors.insert(IncomingBlock->Block).second) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI contains duplicate incoming predecessors");
+ }
+ auto Compatibility = validatePhiValue(Function, Target, *DestinationOperand, *SourceOperand);
+ if (!Compatibility)
+ return std::unexpected(Compatibility.error());
+ Plan.IncomingValues.push_back(
+ PhiIncoming{RegisterValue{*Source, SourceOperand->subReg(),
+ SourceOperand->registerFlags(), SourceOperand->targetFlags()},
+ IncomingBlock->Block, isImplicitlyUndef(Function, *SourceOperand)});
+ }
+ if (SeenPredecessors.size() != Block.predecessors().size()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI incoming blocks do not exactly cover CFG predecessors");
+ }
+ Plans.push_back(std::move(Plan));
+ }
+ return Plans;
+}
+
+[[nodiscard]] Expected<void> copyLiveIns(const MachineBasicBlock &Source,
+ MachineBasicBlock &Destination) {
+ for (const MachineBasicBlockLiveIn &LiveIn : Source.liveIns()) {
+ auto Added = Destination.addLiveIn(LiveIn.PhysReg, LiveIn.Lanes);
+ if (!Added)
+ return std::unexpected(Added.error());
+ }
+ return {};
+}
+
+[[nodiscard]] Expected<void> ensurePhysicalLiveIn(MachineBasicBlock &Block, PhysicalRegister Reg,
+ const TargetDescription &Target) {
+ const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Reg);
+ if (Description == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI incoming value references an unknown physical register");
+ }
+ LaneMask Required;
+ for (const RegisterUnitLane &Unit : Description->Units)
+ Required = Required | Unit.Lanes;
+ if (Required.empty()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI incoming physical register has no addressable lanes");
+ }
+
+ for (const MachineBasicBlockLiveIn &LiveIn : Block.liveIns()) {
+ if (LiveIn.PhysReg != Reg)
+ continue;
+ if (LiveIn.Lanes.contains(Required))
+ return {};
+ const LaneMask Combined = LiveIn.Lanes | Required;
+ auto Removed = Block.removeLiveIn(Reg);
+ if (!Removed)
+ return std::unexpected(Removed.error());
+ return Block.addLiveIn(Reg, Combined);
+ }
+ return Block.addLiveIn(Reg, Required);
+}
+
+[[nodiscard]] Expected<MachineBasicBlock *>
+placePhiCopiesOnEdge(MachineFunction &Function, const TargetDescription &Target,
+ const TargetSSAInfo &TargetInfo, MachineBasicBlock &From,
+ MachineBasicBlock &To,
+ std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> &Cache,
+ MachinePassResult &PassResult) {
+ if (From.successors().size() <= 1)
+ return &From;
+
+ const EdgeKey Key{&From, &To};
+ if (const auto Existing = Cache.find(Key); Existing != Cache.end())
+ return Existing->second;
+ if (std::ranges::none_of(From.successors(), [&To](const MachineSuccessor &Successor) {
+ return Successor.Block == &To;
+ })) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "PHI incoming predecessor has no edge to its successor");
+ }
+
+ auto SourceFallthrough = TargetInfo.isFallthroughEdge(From, To, Function, Target);
+ if (!SourceFallthrough)
+ return std::unexpected(SourceFallthrough.error());
+
+ MachineBasicBlock *LayoutPredecessor = To.previous();
+ if (LayoutPredecessor != nullptr && LayoutPredecessor != &From) {
+ auto OtherFallthrough = TargetInfo.isFallthroughEdge(*LayoutPredecessor, To, Function, Target);
+ if (!OtherFallthrough)
+ return std::unexpected(OtherFallthrough.error());
+ if (*OtherFallthrough) {
+ auto Branch = TargetInfo.insertUnconditionalBranch(*LayoutPredecessor, To, Function, Target);
+ if (!Branch)
+ return std::unexpected(Branch.error());
+ PassResult.Changed = true;
+ PassResult.Changes.add(MachinePassChange::Instructions);
+ }
+ }
+
+ auto EdgeBlockResult = Function.createBasicBlock();
+ if (!EdgeBlockResult)
+ return std::unexpected(EdgeBlockResult.error());
+ MachineBasicBlock *EdgeBlock = *EdgeBlockResult;
+ auto Inserted = Function.insertBlockBefore(To, *EdgeBlock);
+ if (!Inserted)
+ return std::unexpected(Inserted.error());
+
+ auto Rewritten = TargetInfo.rewriteBranchTarget(From, To, *EdgeBlock, Function, Target);
+ if (!Rewritten)
+ return std::unexpected(Rewritten.error());
+ if (!*Rewritten && !*SourceFallthrough) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "PHI elimination cannot split an indirect or unmodeled CFG edge");
+ }
+
+ auto Split = Function.cfgUpdater().splitEdge(From, To, *EdgeBlock);
+ if (!Split)
+ return std::unexpected(Split.error());
+ auto LiveIns = copyLiveIns(To, *EdgeBlock);
+ if (!LiveIns)
+ return std::unexpected(LiveIns.error());
+ auto Branch = TargetInfo.insertUnconditionalBranch(*EdgeBlock, To, Function, Target);
+ if (!Branch)
+ return std::unexpected(Branch.error());
+
+ Cache.emplace(Key, EdgeBlock);
+ PassResult.Changed = true;
+ PassResult.Changes.add(MachinePassChange::CFG);
+ PassResult.Changes.add(MachinePassChange::BlockLayout);
+ PassResult.Changes.add(MachinePassChange::Instructions);
+ if (*Rewritten)
+ PassResult.Changes.add(MachinePassChange::Operands);
+ return EdgeBlock;
+}
+
+[[nodiscard]] Expected<bool> clearStaleLivenessFlags(MachineFunction &Function) {
+ bool Changed = false;
+ for (MachineInstr *Instruction : Function.allInstructions()) {
+ if (Instruction->parent() == nullptr)
+ continue;
+ for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+ MachineOperand *Operand = Instruction->operandAt(Index);
+ if (Operand == nullptr || !Operand->isRegister())
+ continue;
+ RegisterOperandFlags Flags = Operand->registerFlags();
+ const bool HadStaleFlag =
+ Flags.has(RegisterOperandFlag::Kill) || Flags.has(RegisterOperandFlag::Dead);
+ if (!HadStaleFlag)
+ continue;
+ Flags.clear(RegisterOperandFlag::Kill);
+ Flags.clear(RegisterOperandFlag::Dead);
+ auto Updated = Operand->setRegisterFlags(Flags);
+ if (!Updated)
+ return std::unexpected(Updated.error());
+ Changed = true;
+ }
+ }
+ return Changed;
+}
+
+[[nodiscard]] Expected<SubRegIndex> subRegIndex(const MachineOperand &Operand,
+ const TargetDescription &Target) {
+ std::uint64_t Value = 0;
+ if (const auto *Immediate = Operand.getIf<std::int64_t>(); Immediate != nullptr) {
+ if (*Immediate <= 0)
+ return makeUnexpected(ErrorCode::VerificationError,
+ "subregister pseudo requires a positive subregister index");
+ Value = static_cast<std::uint64_t>(*Immediate);
+ } else if (const auto *WideImmediate = Operand.getIf<IntegerImmediateOperand>();
+ WideImmediate != nullptr) {
+ if (WideImmediate->Value.isNegative() || WideImmediate->Value.bitWidth() > 64)
+ return makeUnexpected(ErrorCode::VerificationError,
+ "subregister pseudo index does not fit an unsigned integer");
+ Value = WideImmediate->Value.words().front();
+ } else {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "subregister pseudo is missing its immediate index");
+ }
+ if (Value == 0 || Value > std::numeric_limits<std::uint32_t>::max()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "subregister pseudo index is outside the supported range");
+ }
+ const SubRegIndex Result = SubRegIndex::fromValue(static_cast<std::uint32_t>(Value));
+ if (Target.registers().subRegIndex(Result) == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "subregister pseudo references an unknown target index");
+ }
+ return Result;
+}
+
+[[nodiscard]] Expected<SubRegIndex> composeSubReg(SubRegIndex Outer, SubRegIndex Inner,
+ const TargetDescription &Target) {
+ if (Outer.value() == 0)
+ return Inner;
+ if (Inner.value() == 0)
+ return Outer;
+ const auto Composed = Target.registers().composeSubRegIndices(Outer, Inner);
+ if (!Composed) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "target cannot compose the requested subregister indices");
+ }
+ return *Composed;
+}
+
+[[nodiscard]] Expected<void> removeInstruction(MachineInstr &Instruction) {
+ MachineBasicBlock *Block = Instruction.parent();
+ if (Block == nullptr)
+ return makeUnexpected(ErrorCode::InternalError, "rewritten instruction is not linked");
+ return Block->removeInstruction(Instruction);
+}
+
+[[nodiscard]] Expected<void> expandRegSequence(MachineInstr &Instruction, MachineFunction &Function,
+ const TargetDescription &Target,
+ const TargetSSAInfo &TargetInfo) {
+ if (Instruction.operandCount() < 3 || (Instruction.operandCount() - 1U) % 2U != 0) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "REG_SEQUENCE requires a destination and source/subregister pairs");
+ }
+ MachineOperand *DestinationOperand = Instruction.operandAt(0);
+ const Register *Destination =
+ DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+ if (Destination == nullptr || Destination->isNoRegister() || !DestinationOperand->isDef()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "REG_SEQUENCE requires a register destination definition");
+ }
+ MachineBasicBlock *Block = Instruction.parent();
+ if (Block == nullptr)
+ return makeUnexpected(ErrorCode::InternalError, "REG_SEQUENCE is not linked to a block");
+
+ RegisterValue DestinationValue{*Destination, DestinationOperand->subReg(),
+ DestinationOperand->registerFlags(),
+ DestinationOperand->targetFlags()};
+ auto Initial =
+ buildImplicitDef(Function, Target, *Block, &Instruction, DestinationValue, &Instruction);
+ if (!Initial)
+ return std::unexpected(Initial.error());
+
+ for (std::size_t Index = 1; Index < Instruction.operandCount(); Index += 2U) {
+ MachineOperand *SourceOperand = Instruction.operandAt(Index);
+ MachineOperand *IndexOperand = Instruction.operandAt(Index + 1U);
+ const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>();
+ if (Source == nullptr || SourceOperand == nullptr || !SourceOperand->isUse() ||
+ IndexOperand == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "REG_SEQUENCE contains a malformed source/subregister pair");
+ }
+ auto InnerSubReg = subRegIndex(*IndexOperand, Target);
+ if (!InnerSubReg)
+ return std::unexpected(InnerSubReg.error());
+ auto DestinationSubReg = composeSubReg(DestinationOperand->subReg(), *InnerSubReg, Target);
+ if (!DestinationSubReg)
+ return std::unexpected(DestinationSubReg.error());
+
+ RegisterValue LaneDestination{
+ *Destination, *DestinationSubReg, {}, DestinationOperand->targetFlags()};
+ if (isImplicitlyUndef(Function, *SourceOperand)) {
+ auto Undef =
+ buildImplicitDef(Function, Target, *Block, &Instruction, LaneDestination, &Instruction);
+ if (!Undef)
+ return std::unexpected(Undef.error());
+ continue;
+ }
+ RegisterValue SourceValue{*Source, SourceOperand->subReg(), SourceOperand->registerFlags(),
+ SourceOperand->targetFlags()};
+ auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, LaneDestination,
+ SourceValue, &Instruction);
+ if (!Copy)
+ return std::unexpected(Copy.error());
+ }
+ return removeInstruction(Instruction);
+}
+
+[[nodiscard]] Expected<void> expandInsertSubreg(MachineInstr &Instruction,
+ MachineFunction &Function,
+ const TargetDescription &Target,
+ const TargetSSAInfo &TargetInfo) {
+ if (Instruction.operandCount() != 4) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "INSERT_SUBREG requires destination, base, inserted value, and index");
+ }
+ MachineOperand *DestinationOperand = Instruction.operandAt(0);
+ MachineOperand *BaseOperand = Instruction.operandAt(1);
+ MachineOperand *InsertedOperand = Instruction.operandAt(2);
+ MachineOperand *IndexOperand = Instruction.operandAt(3);
+ const Register *Destination =
+ DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>();
+ const Register *Base = BaseOperand == nullptr ? nullptr : BaseOperand->getIf<Register>();
+ const Register *Inserted =
+ InsertedOperand == nullptr ? nullptr : InsertedOperand->getIf<Register>();
+ if (Destination == nullptr || Base == nullptr || Inserted == nullptr ||
+ Destination->isNoRegister() || DestinationOperand == nullptr ||
+ !DestinationOperand->isDef() || BaseOperand == nullptr || !BaseOperand->isUse() ||
+ InsertedOperand == nullptr || !InsertedOperand->isUse() || IndexOperand == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "INSERT_SUBREG contains malformed register operands");
+ }
+ MachineBasicBlock *Block = Instruction.parent();
+ if (Block == nullptr)
+ return makeUnexpected(ErrorCode::InternalError, "INSERT_SUBREG is not linked to a block");
+
+ RegisterValue DestinationValue{*Destination, DestinationOperand->subReg(),
+ DestinationOperand->registerFlags(),
+ DestinationOperand->targetFlags()};
+ if (isImplicitlyUndef(Function, *BaseOperand)) {
+ auto Undef =
+ buildImplicitDef(Function, Target, *Block, &Instruction, DestinationValue, &Instruction);
+ if (!Undef)
+ return std::unexpected(Undef.error());
+ } else if (*Destination != *Base || DestinationOperand->subReg() != BaseOperand->subReg()) {
+ RegisterValue BaseValue{*Base, BaseOperand->subReg(), BaseOperand->registerFlags(),
+ BaseOperand->targetFlags()};
+ auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, DestinationValue,
+ BaseValue, &Instruction);
+ if (!Copy)
+ return std::unexpected(Copy.error());
+ }
+
+ auto InnerSubReg = subRegIndex(*IndexOperand, Target);
+ if (!InnerSubReg)
+ return std::unexpected(InnerSubReg.error());
+ auto DestinationSubReg = composeSubReg(DestinationOperand->subReg(), *InnerSubReg, Target);
+ if (!DestinationSubReg)
+ return std::unexpected(DestinationSubReg.error());
+ RegisterValue LaneDestination{
+ *Destination, *DestinationSubReg, {}, DestinationOperand->targetFlags()};
+ if (isImplicitlyUndef(Function, *InsertedOperand)) {
+ auto Undef =
+ buildImplicitDef(Function, Target, *Block, &Instruction, LaneDestination, &Instruction);
+ if (!Undef)
+ return std::unexpected(Undef.error());
+ } else {
+ RegisterValue InsertedValue{*Inserted, InsertedOperand->subReg(),
+ InsertedOperand->registerFlags(), InsertedOperand->targetFlags()};
+ auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, LaneDestination,
+ InsertedValue, &Instruction);
+ if (!Copy)
+ return std::unexpected(Copy.error());
+ }
+ return removeInstruction(Instruction);
+}
+
+[[nodiscard]] Expected<void> swapRegisterUses(MachineOperand &Left, MachineOperand &Right) {
+ const std::optional<Register> LeftReg = Left.registerValue();
+ const std::optional<Register> RightReg = Right.registerValue();
+ if (!LeftReg || !RightReg || !Left.isUse() || Left.isDef() || !Right.isUse() || Right.isDef()) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "commutation requires two pure register uses");
+ }
+ const SubRegIndex LeftSubReg = Left.subReg();
+ const SubRegIndex RightSubReg = Right.subReg();
+ const RegisterOperandFlags LeftFlags = Left.registerFlags();
+ const RegisterOperandFlags RightFlags = Right.registerFlags();
+ const std::uint32_t LeftTargetFlags = Left.targetFlags();
+ const std::uint32_t RightTargetFlags = Right.targetFlags();
+
+ auto SetLeftReg = Left.setRegister(*RightReg);
+ if (!SetLeftReg)
+ return std::unexpected(SetLeftReg.error());
+ auto SetRightReg = Right.setRegister(*LeftReg);
+ if (!SetRightReg)
+ return std::unexpected(SetRightReg.error());
+ auto SetLeftSubReg = Left.setSubReg(RightSubReg);
+ if (!SetLeftSubReg)
+ return std::unexpected(SetLeftSubReg.error());
+ auto SetRightSubReg = Right.setSubReg(LeftSubReg);
+ if (!SetRightSubReg)
+ return std::unexpected(SetRightSubReg.error());
+ auto SetLeftFlags = Left.setRegisterFlags(RightFlags);
+ if (!SetLeftFlags)
+ return std::unexpected(SetLeftFlags.error());
+ auto SetRightFlags = Right.setRegisterFlags(LeftFlags);
+ if (!SetRightFlags)
+ return std::unexpected(SetRightFlags.error());
+ Left.setTargetFlags(RightTargetFlags);
+ Right.setTargetFlags(LeftTargetFlags);
+ return {};
+}
+
+[[nodiscard]] Expected<bool> tryCommute(MachineInstr &Instruction, std::size_t TiedUseIndex,
+ Register Destination, const TargetDescription &Target,
+ MachineFunction &Function) {
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+ if (Descriptor == nullptr || !Descriptor->Flags.has(InstructionFlag::Commutable))
+ return false;
+ MachineOperand *TiedUse = Instruction.operandAt(TiedUseIndex);
+ if (TiedUse == nullptr)
+ return makeUnexpected(ErrorCode::InternalError, "tied use disappeared during commutation");
+
+ for (std::size_t Index = 0; Index < Instruction.operandCount(); ++Index) {
+ if (Index == TiedUseIndex)
+ continue;
+ MachineOperand *Candidate = Instruction.operandAt(Index);
+ if (Candidate == nullptr || Candidate->isImplicit() || !Candidate->isUse() ||
+ Candidate->isDef() || Candidate->tiedOperandIndex() ||
+ Candidate->registerValue() != Destination || isImplicitlyUndef(Function, *Candidate)) {
+ continue;
+ }
+ auto Swapped = swapRegisterUses(*TiedUse, *Candidate);
+ if (!Swapped)
+ return std::unexpected(Swapped.error());
+ auto Validation = Target.validateInstruction(Instruction, Function.registerInfo());
+ if (Validation)
+ return true;
+ auto Restored = swapRegisterUses(*TiedUse, *Candidate);
+ if (!Restored)
+ return std::unexpected(Restored.error());
+ }
+ return false;
+}
+
+[[nodiscard]] Expected<void> rewriteUndefTie(MachineOperand &Use, const MachineOperand &Def) {
+ const std::optional<Register> Destination = Def.registerValue();
+ if (!Destination)
+ return makeUnexpected(ErrorCode::VerificationError, "tied definition is not a register");
+ auto SetRegister = Use.setRegister(*Destination);
+ if (!SetRegister)
+ return std::unexpected(SetRegister.error());
+ auto SetSubReg = Use.setSubReg(Def.subReg());
+ if (!SetSubReg)
+ return std::unexpected(SetSubReg.error());
+ RegisterOperandFlags Flags = Use.registerFlags();
+ Flags.set(RegisterOperandFlag::Undef);
+ Flags.clear(RegisterOperandFlag::Kill);
+ return Use.setRegisterFlags(Flags);
+}
+
+[[nodiscard]] Expected<void> verifyNoStageTenPseudos(const MachineFunction &Function,
+ const TargetDescription &Target) {
+ for (const MachineInstr *Instruction : Function.allInstructions()) {
+ if (Instruction->parent() == nullptr)
+ continue;
+ if (Instruction->opcode() == opcode(GenericOpcode::G_PHI) ||
+ Instruction->opcode() == opcode(GenericOpcode::PHI) ||
+ Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE) ||
+ Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "SSA exit left a Stage 10 pseudo instruction in MachineIR");
+ }
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+ if (Descriptor == nullptr)
+ return makeUnexpected(ErrorCode::VerificationError,
+ "SSA exit produced an instruction with no descriptor");
+ for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+ const MachineOperand *Operand = Instruction->operandAt(Index);
+ if (Operand == nullptr || !Operand->isUse())
+ continue;
+ const std::optional<std::size_t> Tie = Operand->tiedOperandIndex();
+ if (!Tie)
+ continue;
+ const MachineOperand *Def = Instruction->operandAt(Tie.value());
+ if (Def == nullptr || Def->registerValue() != Operand->registerValue()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "two-address rewrite left an unequal tied register");
+ }
+ }
+ }
+ return {};
+}
+
+} // namespace
+
+const MachinePassContract &PHIEliminationPass::contract() const noexcept {
+ static const MachinePassContract Contract{
+ .Name = "PHIElimination",
+ .Requires = {MachineFunctionProperty::IsSSA, MachineFunctionProperty::Selected,
+ MachineFunctionProperty::RegBankSelected},
+ .Sets = {MachineFunctionProperty::NoPHIs},
+ .Clears = {MachineFunctionProperty::IsSSA},
+ .RequiredAnalyses = {},
+ .VerificationStage = PipelineStage::SSAEliminated,
+ };
+ return Contract;
+}
+
+Expected<MachinePassResult> PHIEliminationPass::run(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineAnalysisManager &Analyses) {
+ if (Info == nullptr) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "PHI elimination has no target SSA behavior interface");
+ }
+ auto Required = requireProperties(Function, contract());
+ if (!Required)
+ return std::unexpected(Required.error());
+
+ auto Trial = cloneMachineFunction(
+ Function, Target,
+ MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+ if (!Trial) {
+ return std::unexpected(
+ prefixedError(Trial.error(), "PHI-elimination transaction setup failed: "));
+ }
+ MachineAnalysisManager TrialAnalyses;
+ auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses);
+ if (!TrialResult)
+ return std::unexpected(TrialResult.error());
+
+ auto Result = runImplementation(Function, Target, Analyses);
+ if (!Result) {
+ return std::unexpected(prefixedError(
+ Result.error(), "PHI elimination diverged after a successful transaction preflight: "));
+ }
+ return Result;
+}
+
+Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineAnalysisManager &) {
+ MachinePassResult Result;
+ std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> SplitEdges;
+ const std::vector<MachineBasicBlock *> Blocks(Function.allBlocks().begin(),
+ Function.allBlocks().end());
+
+ for (MachineBasicBlock *Block : Blocks) {
+ auto Plans = collectPhiPlans(*Block, Function, Target);
+ if (!Plans)
+ return std::unexpected(Plans.error());
+ if (Plans->empty())
+ continue;
+
+ for (PhiPlan &Plan : *Plans) {
+ auto Fresh = cloneRegisterConstraints(Function, Plan.Destination.Reg);
+ if (!Fresh)
+ return std::unexpected(Fresh.error());
+ Plan.FreshIncoming = *Fresh;
+ }
+
+ for (PhiPlan &Plan : *Plans) {
+ for (const PhiIncoming &Incoming : Plan.IncomingValues) {
+ auto EdgeBlock = placePhiCopiesOnEdge(Function, Target, *Info, *Incoming.Predecessor,
+ *Block, SplitEdges, Result);
+ if (!EdgeBlock)
+ return std::unexpected(EdgeBlock.error());
+ if (*EdgeBlock != Incoming.Predecessor) {
+ const std::optional<PhysicalRegister> Physical = Incoming.Value.Reg.physicalRegister();
+ if (Physical) {
+ auto LiveIn = ensurePhysicalLiveIn(**EdgeBlock, *Physical, Target);
+ if (!LiveIn)
+ return std::unexpected(LiveIn.error());
+ }
+ }
+ MachineInstr *Terminator = firstTerminator(**EdgeBlock, Target);
+ RegisterValue Fresh{Plan.FreshIncoming, Plan.Destination.SubReg, Plan.Destination.Flags,
+ Plan.Destination.TargetFlags};
+ Expected<MachineInstr *> Transfer =
+ Incoming.IsUndef ? buildImplicitDef(Function, Target, **EdgeBlock, Terminator, Fresh,
+ Plan.Instruction)
+ : buildCopy(Function, Target, *Info, **EdgeBlock, Terminator, Fresh,
+ Incoming.Value, Plan.Instruction);
+ if (!Transfer)
+ return std::unexpected(Transfer.error());
+ Result.Changed = true;
+ Result.Changes.add(MachinePassChange::Instructions);
+ }
+ }
+
+ MachineInstr *InsertionPoint = firstCodeAfterPhiRegion(*Block, Target);
+ for (PhiPlan &Plan : *Plans) {
+ RegisterValue Fresh{
+ Plan.FreshIncoming, Plan.Destination.SubReg, {}, Plan.Destination.TargetFlags};
+ auto Copy = buildCopy(Function, Target, *Info, *Block, InsertionPoint, Plan.Destination,
+ Fresh, Plan.Instruction);
+ if (!Copy)
+ return std::unexpected(Copy.error());
+ Result.Changed = true;
+ Result.Changes.add(MachinePassChange::Instructions);
+ }
+
+ for (PhiPlan &Plan : *Plans) {
+ auto Removed = Block->removeInstruction(*Plan.Instruction);
+ if (!Removed)
+ return std::unexpected(Removed.error());
+ }
+ Result.Changes.add(MachinePassChange::Registers);
+ }
+
+ if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+ auto Cleared = clearStaleLivenessFlags(Function);
+ if (!Cleared)
+ return std::unexpected(Cleared.error());
+ if (*Cleared)
+ Result.Changes.add(MachinePassChange::Operands);
+ }
+ Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+ return Result;
+}
+
+const MachinePassContract &TwoAddressRewritePass::contract() const noexcept {
+ static const MachinePassContract Contract{
+ .Name = "TwoAddressRewrite",
+ .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs},
+ .Sets = {MachineFunctionProperty::TiedOpsRewritten},
+ .Clears = {MachineFunctionProperty::IsSSA},
+ .RequiredAnalyses = {},
+ .VerificationStage = PipelineStage::TiedOpsRewritten,
+ };
+ return Contract;
+}
+
+Expected<MachinePassResult> TwoAddressRewritePass::run(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineAnalysisManager &Analyses) {
+ if (Info == nullptr) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "two-address rewrite has no target SSA behavior interface");
+ }
+ auto Required = requireProperties(Function, contract());
+ if (!Required)
+ return std::unexpected(Required.error());
+
+ auto Trial = cloneMachineFunction(
+ Function, Target,
+ MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+ if (!Trial) {
+ return std::unexpected(prefixedError(Trial.error(), "two-address transaction setup failed: "));
+ }
+ MachineAnalysisManager TrialAnalyses;
+ auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses);
+ if (!TrialResult)
+ return std::unexpected(TrialResult.error());
+
+ auto Result = runImplementation(Function, Target, Analyses);
+ if (!Result) {
+ return std::unexpected(prefixedError(
+ Result.error(), "two-address rewrite diverged after a successful transaction preflight: "));
+ }
+ return Result;
+}
+
+Expected<MachinePassResult>
+TwoAddressRewritePass::runImplementation(MachineFunction &Function, const TargetDescription &Target,
+ MachineAnalysisManager &) {
+ MachinePassResult Result;
+ const std::vector<MachineInstr *> Instructions(Function.allInstructions().begin(),
+ Function.allInstructions().end());
+ for (MachineInstr *Instruction : Instructions) {
+ if (Instruction->parent() == nullptr)
+ continue;
+ if (Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE)) {
+ auto Expanded = expandRegSequence(*Instruction, Function, Target, *Info);
+ if (!Expanded)
+ return std::unexpected(Expanded.error());
+ Result.Changed = true;
+ Result.Changes.add(MachinePassChange::Instructions);
+ continue;
+ }
+ if (Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) {
+ auto Expanded = expandInsertSubreg(*Instruction, Function, Target, *Info);
+ if (!Expanded)
+ return std::unexpected(Expanded.error());
+ Result.Changed = true;
+ Result.Changes.add(MachinePassChange::Instructions);
+ continue;
+ }
+
+ std::size_t RewriteAttempts = 0;
+ bool Restart = true;
+ while (Restart && Instruction->parent() != nullptr) {
+ Restart = false;
+ if (++RewriteAttempts > Instruction->operandCount() * 2U + 8U) {
+ return makeUnexpected(ErrorCode::InternalError,
+ "two-address target conversion did not make progress");
+ }
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+ if (Descriptor == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "two-address rewrite encountered an unknown opcode");
+ }
+
+ for (std::size_t UseIndex = 0; UseIndex < Instruction->operandCount(); ++UseIndex) {
+ MachineOperand *Use = Instruction->operandAt(UseIndex);
+ if (Use == nullptr || !Use->isUse())
+ continue;
+ const std::optional<std::size_t> TiedDefIndex = Use->tiedOperandIndex();
+ if (!TiedDefIndex)
+ continue;
+ const std::size_t DefIndex = TiedDefIndex.value();
+ MachineOperand *Def = Instruction->operandAt(DefIndex);
+ if (Def == nullptr || !Def->isDef()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "tied use does not reference a definition");
+ }
+ const std::optional<Register> DefReg = Def->registerValue();
+ const std::optional<Register> UseReg = Use->registerValue();
+ if (!DefReg || !UseReg || DefReg->isNoRegister()) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "two-address rewrite requires register ties");
+ }
+ if (*DefReg == *UseReg)
+ continue;
+
+ if (isImplicitlyUndef(Function, *Use)) {
+ auto Rewritten = rewriteUndefTie(*Use, *Def);
+ if (!Rewritten)
+ return std::unexpected(Rewritten.error());
+ Result.Changed = true;
+ Result.Changes.add(MachinePassChange::Operands);
+ continue;
+ }
+
+ auto Commuted = tryCommute(*Instruction, UseIndex, *DefReg, Target, Function);
+ if (!Commuted)
+ return std::unexpected(Commuted.error());
+ if (*Commuted) {
+ Result.Changed = true;
+ Result.Changes.add(MachinePassChange::Operands);
+ continue;
+ }
+
+ auto Converted =
+ Info->tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target);
+ if (!Converted)
+ return std::unexpected(Converted.error());
+ if (*Converted) {
+ Result.Changed = true;
+ Result.Changes.add(MachinePassChange::Instructions);
+ Result.Changes.add(MachinePassChange::Operands);
+ Result.Changes.add(MachinePassChange::Registers);
+ Restart = true;
+ break;
+ }
+
+ MachineBasicBlock *Block = Instruction->parent();
+ if (Block == nullptr)
+ return makeUnexpected(ErrorCode::InternalError,
+ "two-address instruction disappeared before COPY insertion");
+ RegisterValue Destination{*DefReg, Def->subReg(), Def->registerFlags(), Def->targetFlags()};
+ RegisterValue Source{*UseReg, Use->subReg(), Use->registerFlags(), Use->targetFlags()};
+ auto Copy = buildCopy(Function, Target, *Info, *Block, Instruction, Destination, Source,
+ Instruction);
+ if (!Copy)
+ return std::unexpected(Copy.error());
+ auto SetRegister = Use->setRegister(*DefReg);
+ if (!SetRegister)
+ return std::unexpected(SetRegister.error());
+ auto SetSubReg = Use->setSubReg(Def->subReg());
+ if (!SetSubReg)
+ return std::unexpected(SetSubReg.error());
+ RegisterOperandFlags Flags = Use->registerFlags();
+ Flags.clear(RegisterOperandFlag::Kill);
+ auto SetFlags = Use->setRegisterFlags(Flags);
+ if (!SetFlags)
+ return std::unexpected(SetFlags.error());
+ Result.Changed = true;
+ Result.Changes.add(MachinePassChange::Instructions);
+ Result.Changes.add(MachinePassChange::Operands);
+ }
+ }
+ }
+
+ auto FinalState = verifyNoStageTenPseudos(Function, Target);
+ if (!FinalState)
+ return std::unexpected(FinalState.error());
+ if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+ auto Cleared = clearStaleLivenessFlags(Function);
+ if (!Cleared)
+ return std::unexpected(Cleared.error());
+ if (*Cleared)
+ Result.Changes.add(MachinePassChange::Operands);
+ }
+ Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
+ return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp
index f6f5640..8f4809a 100644
--- a/backend/lib/CodeGen/MachineVerifier.cpp
+++ b/backend/lib/CodeGen/MachineVerifier.cpp
@@ -2,6 +2,7 @@
#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/GenericOpcodes.h"
#include "rcc/CodeGen/MachineBasicBlock.h"
#include "rcc/CodeGen/MachineFrameInfo.h"
#include "rcc/CodeGen/MachineFunction.h"
@@ -87,6 +88,9 @@ public:
auto CFGResult = verifyCFG();
if (!CFGResult)
return CFGResult;
+ auto PHIResult = verifyPHIs();
+ if (!PHIResult)
+ return PHIResult;
auto RegisterResult = verifyRegisterInfo();
if (!RegisterResult)
return RegisterResult;
@@ -428,9 +432,8 @@ private:
}
[[nodiscard]] Expected<void> verifyFrameLifetimes() const {
- auto VerifyPoints =
- [this](std::span<const MachineFrameSaveRestorePoint> Points,
- std::string_view Kind) -> Expected<void> {
+ auto VerifyPoints = [this](std::span<const MachineFrameSaveRestorePoint> Points,
+ std::string_view Kind) -> Expected<void> {
for (const MachineFrameSaveRestorePoint &Point : Points) {
if (!LinkedBlockIDs.contains(Point.Block)) {
return fail(std::string("frame ") + std::string(Kind) +
@@ -591,6 +594,8 @@ private:
}
HasPhi |= Descriptor->Flags.has(InstructionFlag::Phi);
+ HasStageTenPseudo |= Instruction.opcode() == opcode(GenericOpcode::REG_SEQUENCE) ||
+ Instruction.opcode() == opcode(GenericOpcode::INSERT_SUBREG);
HasGenericInstruction |= Descriptor->Flags.has(InstructionFlag::Generic);
HasExecutablePseudo |= Descriptor->Flags.has(InstructionFlag::Pseudo) &&
!Descriptor->Flags.has(InstructionFlag::Meta) &&
@@ -708,6 +713,75 @@ private:
return {};
}
+ [[nodiscard]] Expected<void> verifyPHIs() {
+ for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+ Block = Block->next()) {
+ bool SawNonMetaInstruction = false;
+ for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ const InstructionDescriptor *Descriptor =
+ Target.instructionDescriptor(Instruction->opcode());
+ if (Descriptor == nullptr)
+ return fail("PHI verification encountered an unregistered instruction");
+
+ if (!Descriptor->Flags.has(InstructionFlag::Phi)) {
+ SawNonMetaInstruction |= !Descriptor->Flags.has(InstructionFlag::Meta);
+ continue;
+ }
+ if (SawNonMetaInstruction)
+ return fail("PHI instruction appears after a non-meta instruction");
+
+ const std::span<const MachineOperand> Operands = Instruction->operands();
+ if (Operands.size() < 3 || (Operands.size() - 1U) % 2U != 0) {
+ return fail("PHI must contain a destination and at least one incoming pair");
+ }
+ const Register *Destination = Operands.front().getIf<Register>();
+ if (Destination == nullptr || !Destination->isVirtual() || !Operands.front().isDef() ||
+ Operands.front().isUse() || Operands.front().isImplicit()) {
+ return fail("PHI destination must be an explicit virtual-register definition");
+ }
+
+ std::unordered_set<const MachineBasicBlock *> IncomingBlocks;
+ for (std::size_t Index = 1; Index < Operands.size(); Index += 2U) {
+ const MachineOperand &ValueOperand = Operands[Index];
+ const MachineOperand &BlockOperand = Operands[Index + 1U];
+ const Register *Value = ValueOperand.getIf<Register>();
+ const BasicBlockOperand *Incoming = BlockOperand.getIf<BasicBlockOperand>();
+ if (Value == nullptr || !ValueOperand.isUse() || ValueOperand.isDef() ||
+ ValueOperand.isImplicit() || Incoming == nullptr || Incoming->Block == nullptr ||
+ BlockOperand.isImplicit()) {
+ return fail("PHI incoming operands must be explicit register/block pairs");
+ }
+ if (std::ranges::find(Block->predecessors(), Incoming->Block) ==
+ Block->predecessors().end()) {
+ return fail("PHI incoming block is not a CFG predecessor");
+ }
+ if (!IncomingBlocks.insert(Incoming->Block).second)
+ return fail("PHI contains duplicate incoming blocks");
+
+ if (!Value->isNoRegister() && Destination->isVirtual() && Value->isVirtual() &&
+ Operands.front().subReg().value() == 0 && ValueOperand.subReg().value() == 0) {
+ auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(*Destination);
+ auto ValueInfo = Function.registerInfo().virtualRegisterInfo(*Value);
+ if (!DestinationInfo || !ValueInfo)
+ return fail("PHI references an unknown virtual register");
+ if (DestinationInfo->get().Type && ValueInfo->get().Type &&
+ DestinationInfo->get().Type != ValueInfo->get().Type) {
+ return fail("PHI destination and incoming value types do not match");
+ }
+ }
+ auto Compatibility = Target.validateTieCompatibility(Operands.front(), ValueOperand,
+ Function.registerInfo());
+ if (!Compatibility)
+ return failWith("PHI register compatibility", Compatibility.error());
+ }
+ if (IncomingBlocks.size() != Block->predecessors().size())
+ return fail("PHI incoming blocks do not exactly cover CFG predecessors");
+ }
+ }
+ return {};
+ }
+
[[nodiscard]] Expected<void> verifyRegisterInfo() {
const MachineRegisterInfo &RegInfo = Function.registerInfo();
std::unordered_set<PhysicalRegister> FunctionLiveIns;
@@ -767,6 +841,9 @@ private:
if (Has(MachineFunctionProperty::TiedOpsRewritten) && !Has(MachineFunctionProperty::Selected)) {
return fail("TiedOpsRewritten requires Selected");
}
+ if (Has(MachineFunctionProperty::TiedOpsRewritten) && !Has(MachineFunctionProperty::NoPHIs)) {
+ return fail("TiedOpsRewritten requires NoPHIs");
+ }
if (Has(MachineFunctionProperty::FrameFinalized) &&
(!Has(MachineFunctionProperty::NoVRegs) || !Has(MachineFunctionProperty::NoFrameIndices))) {
return fail("FrameFinalized requires NoVRegs and NoFrameIndices");
@@ -797,6 +874,9 @@ private:
if (Has(MachineFunctionProperty::TiedOpsRewritten) && HasUnrewrittenTie) {
return fail("TiedOpsRewritten function has unequal tied registers");
}
+ if (Has(MachineFunctionProperty::TiedOpsRewritten) && HasStageTenPseudo) {
+ return fail("TiedOpsRewritten function contains a Stage 10 pseudo");
+ }
const bool NeedsTypes = Options.Mode == MachineVerifierMode::PreLegalizer ||
Has(MachineFunctionProperty::Legalized) ||
@@ -837,6 +917,7 @@ private:
bool HasExecutablePseudo = false;
bool HasFrameIndex = false;
bool HasUnrewrittenTie = false;
+ bool HasStageTenPseudo = false;
bool HasLiveVirtualRegister = false;
bool MissingVirtualType = false;
bool MissingVirtualBank = false;
diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp
index e2bbe8a..e8c7d79 100644
--- a/backend/lib/CodeGen/TargetDescription.cpp
+++ b/backend/lib/CodeGen/TargetDescription.cpp
@@ -58,7 +58,13 @@ Expected<TargetDescription> TargetDescription::create(InstructionSet Instruction
for (const InstructionDescriptor &Instruction : Instructions.descriptors()) {
for (const OperandDescriptor &Operand : Instruction.Operands) {
- if ((Operand.AllowedTargetFlags & ~MIRText->serializableOperandFlagMask()) != 0) {
+ if (Operand.AllowAnyTargetFlags && Operand.AllowedTargetFlags != 0) {
+ return makeUnexpected(
+ ErrorCode::InvalidArgument,
+ "instruction operand cannot combine unrestricted and explicit target flags");
+ }
+ if (!Operand.AllowAnyTargetFlags &&
+ (Operand.AllowedTargetFlags & ~MIRText->serializableOperandFlagMask()) != 0) {
return makeUnexpected(
ErrorCode::InvalidArgument,
"instruction operand allows a target flag outside the MIR text schema");
diff --git a/backend/lib/Target/RISCV/RISCVCodeGen.cpp b/backend/lib/Target/RISCV/RISCVCodeGen.cpp
index 631ac33..642982a 100644
--- a/backend/lib/Target/RISCV/RISCVCodeGen.cpp
+++ b/backend/lib/Target/RISCV/RISCVCodeGen.cpp
@@ -4,6 +4,7 @@
#include "rcc/CodeGen/GenericOpcodes.h"
#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
#include "rcc/CodeGen/MachineFunction.h"
#include "rcc/CodeGen/MachineIRBuilder.h"
#include "rcc/CodeGen/MachineInstr.h"
@@ -13,6 +14,7 @@
#include "rcc/CodeGen/TargetDescription.h"
#include "rcc/Target/RISCV/RISCVTarget.h"
+#include <algorithm>
#include <array>
#include <bit>
#include <cstdint>
@@ -3219,6 +3221,198 @@ private:
}
};
+class RISCVSSAInfo final : public TargetSSAInfo {
+public:
+ [[nodiscard]] Expected<bool> isFallthroughEdge(const MachineBasicBlock &From,
+ const MachineBasicBlock &To,
+ const MachineFunction &,
+ const TargetDescription &Target) const override {
+ if (From.next() != &To ||
+ std::ranges::none_of(From.successors(), [&To](const MachineSuccessor &Successor) {
+ return Successor.Block == &To;
+ })) {
+ return false;
+ }
+
+ bool CanFallThrough = true;
+ for (const MachineInstr *Instruction = From.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+ if (Descriptor == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "RISC-V fallthrough analysis encountered an unknown opcode");
+ }
+ if (!Descriptor->Flags.has(InstructionFlag::Terminator))
+ continue;
+ CanFallThrough = isConditionalBranch(Instruction->opcode());
+ }
+ return CanFallThrough;
+ }
+
+ [[nodiscard]] Expected<bool> rewriteBranchTarget(MachineBasicBlock &Block,
+ MachineBasicBlock &OldTarget,
+ MachineBasicBlock &NewTarget,
+ MachineFunction &Function,
+ const TargetDescription &Target) const override {
+ if (&Block.function() != &Function || &OldTarget.function() != &Function ||
+ &NewTarget.function() != &Function) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "RISC-V branch rewrite references another machine function");
+ }
+
+ bool Changed = false;
+ 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 rewrite encountered an unknown opcode");
+ }
+ if (!Descriptor->Flags.has(InstructionFlag::Branch) ||
+ Descriptor->Flags.has(InstructionFlag::IndirectBranch)) {
+ continue;
+ }
+ for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+ MachineOperand *Operand = Instruction->operandAt(Index);
+ const BasicBlockOperand *TargetOperand =
+ Operand == nullptr ? nullptr : Operand->getIf<BasicBlockOperand>();
+ if (TargetOperand == nullptr || TargetOperand->Block != &OldTarget)
+ continue;
+ auto Rewritten = Operand->setBasicBlock(NewTarget);
+ if (!Rewritten)
+ return std::unexpected(Rewritten.error());
+ Changed = true;
+ }
+ }
+ return Changed;
+ }
+
+ [[nodiscard]] Expected<void>
+ 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 machine function");
+ }
+ auto Zero = physicalRegister(PhysicalRegisterID::X0);
+ if (!Zero)
+ return std::unexpected(Zero.error());
+ MachineIRBuilder Builder(Function, Target);
+ auto Point = Builder.setInsertPoint(Block);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Branch = Builder.buildInstr(targetOpcode(InstructionOpcode::JAL));
+ if (!Branch)
+ return std::unexpected(Branch.error());
+ auto Link = Branch->addDef(Register::fromPhysical(*Zero));
+ if (!Link)
+ return std::unexpected(Link.error());
+ auto Destination = Branch->addBasicBlock(TargetBlock);
+ if (!Destination)
+ return std::unexpected(Destination.error());
+ auto Built = Branch->build();
+ if (!Built)
+ return std::unexpected(Built.error());
+ return {};
+ }
+
+ [[nodiscard]] Expected<void> validateCopy(Register Destination, SubRegIndex DestinationSubReg,
+ Register Source, SubRegIndex SourceSubReg,
+ const MachineFunction &Function,
+ const TargetDescription &Target) const override {
+ if (Destination.isNoRegister() || Source.isNoRegister()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "RISC-V COPY requires two nonzero registers");
+ }
+ if (DestinationSubReg.value() != 0 || SourceSubReg.value() != 0) {
+ return makeUnexpected(ErrorCode::Unsupported, "RV64GC does not model register subindices");
+ }
+
+ auto DestinationShape = copyShape(Destination, Function, Target);
+ if (!DestinationShape)
+ return std::unexpected(DestinationShape.error());
+ auto SourceShape = copyShape(Source, Function, Target);
+ if (!SourceShape)
+ return std::unexpected(SourceShape.error());
+ if (DestinationShape->Bank == SourceShape->Bank) {
+ if (DestinationShape->Width && SourceShape->Width &&
+ DestinationShape->Width != SourceShape->Width) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "RISC-V same-bank COPY has incompatible register widths");
+ }
+ return {};
+ }
+
+ const RegisterBankID GPR =
+ RegisterBankID::fromValue(static_cast<std::uint32_t>(RegisterBank::GPR));
+ const RegisterBankID FPR =
+ RegisterBankID::fromValue(static_cast<std::uint32_t>(RegisterBank::FPR));
+ const bool IsCrossBankMove = (DestinationShape->Bank == GPR && SourceShape->Bank == FPR) ||
+ (DestinationShape->Bank == FPR && SourceShape->Bank == GPR);
+ if (!IsCrossBankMove) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "RISC-V COPY crosses unsupported register banks");
+ }
+ auto SupportedWidth = [](std::optional<std::uint32_t> Width) {
+ return !Width || *Width == 32 || *Width == 64;
+ };
+ if (!SupportedWidth(DestinationShape->Width) || !SupportedWidth(SourceShape->Width)) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "RISC-V GPR/FPR COPY requires 32-bit or 64-bit values");
+ }
+ return {};
+ }
+
+private:
+ struct CopyShape final {
+ RegisterBankID Bank;
+ std::optional<std::uint32_t> Width;
+ };
+
+ [[nodiscard]] static 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);
+ }
+
+ [[nodiscard]] static Expected<CopyShape> copyShape(Register Reg, const MachineFunction &Function,
+ const TargetDescription &Target) {
+ if (Reg.isVirtual()) {
+ auto Info = Function.registerInfo().virtualRegisterInfo(Reg);
+ if (!Info)
+ return std::unexpected(Info.error());
+ const std::optional<RegisterBankID> &Bank = Info->get().Bank;
+ const std::optional<RegisterClassID> &RegClass = Info->get().RegClass;
+ if (!Bank || !RegClass) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "RISC-V COPY virtual register is not fully constrained");
+ }
+ const RegisterClassDesc *Class = Target.registers().registerClass(RegClass.value());
+ if (Class == nullptr) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "RISC-V COPY references an unknown register class");
+ }
+ return CopyShape{Bank.value(), Class->SizeInBits};
+ }
+
+ const std::optional<PhysicalRegister> Physical = Reg.physicalRegister();
+ if (!Physical || !Target.registers().isKnownPhysicalRegister(*Physical)) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "RISC-V COPY references an unknown physical register");
+ }
+ for (const RegisterBankDesc &Bank : Target.registers().registerBanks()) {
+ if (Target.registers().bankContainsRegister(Bank.ID, *Physical))
+ return CopyShape{Bank.ID, std::nullopt};
+ }
+ return makeUnexpected(ErrorCode::VerificationError,
+ "RISC-V physical register is not assigned to a register bank");
+ }
+};
+
} // namespace
const TargetLegalizerInfo &legalizerInfo() noexcept {
@@ -3236,4 +3430,9 @@ const TargetInstructionSelector &instructionSelector() noexcept {
return Value;
}
+const TargetSSAInfo &ssaInfo() noexcept {
+ static const RISCVSSAInfo Value;
+ return Value;
+}
+
} // namespace rcc::riscv
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index 19beb2f..c8ea9b8 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -21,6 +21,7 @@ set(
MachineOperandTest.cpp
MachinePassTest.cpp
MachinePipelinePassesTest.cpp
+ MachineSSAExitTest.cpp
MachineVerifierTest.cpp
MachineVerifierTargetTest.cpp
MachineValueTypesTest.cpp
@@ -273,6 +274,14 @@ target_link_libraries(
add_test(NAME RCCBackend.CodeGen.MachineAnalyses COMMAND RCCBackendCodeGenMachineAnalysesTests)
+add_executable(RCCBackendCodeGenMachineSSAExitTests MachineSSAExitTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenMachineSSAExitTests)
+target_link_libraries(
+ RCCBackendCodeGenMachineSSAExitTests
+ PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget
+)
+add_test(NAME RCCBackend.CodeGen.MachineSSAExit COMMAND RCCBackendCodeGenMachineSSAExitTests)
+
add_executable(RCCBackendCodeGenTargetConstantTests TargetConstantTest.cpp)
rcc_backend_configure_target(RCCBackendCodeGenTargetConstantTests)
target_link_libraries(RCCBackendCodeGenTargetConstantTests PRIVATE RCCBackend::CodeGen)
@@ -350,6 +359,7 @@ rcc_backend_register_format_files(
"${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTargetTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
@@ -379,6 +389,7 @@ rcc_backend_register_tidy_files(
"${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTargetTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
diff --git a/backend/unittests/CodeGen/MachineAnalysesTest.cpp b/backend/unittests/CodeGen/MachineAnalysesTest.cpp
index 23c5e19..1c9f255 100644
--- a/backend/unittests/CodeGen/MachineAnalysesTest.cpp
+++ b/backend/unittests/CodeGen/MachineAnalysesTest.cpp
@@ -458,6 +458,108 @@ void testCFGUpdaterPHIs(TestContext &Context, const rcc::TargetDescription &Targ
"CFG block deletion must detach a disconnected block cleanly");
}
+void testCFGUpdaterFailureAtomicity(TestContext &Context, const rcc::TargetDescription &Target) {
+ auto SplitFunction =
+ rcc::MachineFunction::create("cfg_split_atomic", rcc::MachineFunctionStableID::fromValue(5));
+ if (!SplitFunction) {
+ Context.expect(false, "CFG split atomicity function creation must succeed");
+ return;
+ }
+ auto Source = appendBlock(**SplitFunction);
+ auto Merge = appendBlock(**SplitFunction);
+ if (!Source || !Merge)
+ return;
+ auto SplitUpdater = (*SplitFunction)->cfgUpdater();
+ if (!SplitUpdater.addSuccessor(**Source, **Merge, rcc::BranchProbability::one()))
+ return;
+
+ auto I64 = rcc::LLT::makeInteger(64);
+ auto Destination = I64 ? (*SplitFunction)->registerInfo().createVirtualRegister(*I64)
+ : rcc::Expected<rcc::Register>{std::unexpected(I64.error())};
+ auto Value = I64 ? (*SplitFunction)->registerInfo().createVirtualRegister(*I64)
+ : rcc::Expected<rcc::Register>{std::unexpected(I64.error())};
+ if (!Destination || !Value)
+ return;
+
+ rcc::MachineIRBuilder Builder(**SplitFunction, Target);
+ if (!Builder.setInsertPoint(**Source))
+ return;
+ auto Branch = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_BR));
+ auto BranchInstruction =
+ Branch && Branch->addBasicBlock(**Merge)
+ ? Branch->build()
+ : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected(
+ rcc::ErrorCode::InternalError, "failed to build CFG split branch")};
+ if (!BranchInstruction || !Builder.setInsertPoint(**Merge))
+ return;
+ auto Phi = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_PHI));
+ auto PhiInstruction =
+ Phi && Phi->addDef(*Destination) && Phi->addUse(*Value) && Phi->addBasicBlock(**Source)
+ ? Phi->build()
+ : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected(
+ rcc::ErrorCode::InternalError, "failed to build CFG split PHI")};
+ if (!PhiInstruction || !(*PhiInstruction)->eraseOperand(2))
+ return;
+
+ const std::size_t LinkedBlocksBefore = (*SplitFunction)->blockCount();
+ const std::size_t AllocatedBlocksBefore = (*SplitFunction)->allBlocks().size();
+ auto FailedSplit = SplitUpdater.splitBlock(**Source, **BranchInstruction);
+ Context.expect(
+ !FailedSplit && (*SplitFunction)->blockCount() == LinkedBlocksBefore &&
+ (*SplitFunction)->allBlocks().size() == AllocatedBlocksBefore &&
+ (*BranchInstruction)->parent() == *Source && (*Source)->successors().size() == 1 &&
+ (*Source)->successors().front().Block == *Merge && (*Merge)->predecessors().size() == 1 &&
+ (*Merge)->predecessors().front() == *Source,
+ "failed block split must not mutate layout, instructions, or CFG edges");
+
+ auto FailedDelete = SplitUpdater.deleteBlock(**Source);
+ Context.expect(!FailedDelete && (*Source)->isLinked() &&
+ (*SplitFunction)->blockCount() == LinkedBlocksBefore &&
+ (*Source)->successors().size() == 1 && (*Merge)->predecessors().size() == 1,
+ "failed block deletion must not partially disconnect CFG edges");
+
+ auto TransferFunction = rcc::MachineFunction::create("cfg_transfer_atomic",
+ rcc::MachineFunctionStableID::fromValue(6));
+ if (!TransferFunction)
+ return;
+ auto From = appendBlock(**TransferFunction);
+ auto To = appendBlock(**TransferFunction);
+ auto Successor = appendBlock(**TransferFunction);
+ if (!From || !To || !Successor)
+ return;
+ auto TransferUpdater = (*TransferFunction)->cfgUpdater();
+ if (!TransferUpdater.addSuccessor(**From, **Successor, rcc::BranchProbability::one()) ||
+ !TransferUpdater.addSuccessor(**To, **Successor, rcc::BranchProbability::one())) {
+ return;
+ }
+ auto TransferDestination = I64 ? (*TransferFunction)->registerInfo().createVirtualRegister(*I64)
+ : rcc::Expected<rcc::Register>{std::unexpected(I64.error())};
+ auto TransferValue = I64 ? (*TransferFunction)->registerInfo().createVirtualRegister(*I64)
+ : rcc::Expected<rcc::Register>{std::unexpected(I64.error())};
+ if (!TransferDestination || !TransferValue)
+ return;
+ rcc::MachineIRBuilder TransferBuilder(**TransferFunction, Target);
+ if (!TransferBuilder.setInsertPoint(**Successor))
+ return;
+ auto TransferPhi = TransferBuilder.buildInstr(rcc::opcode(rcc::GenericOpcode::G_PHI));
+ auto TransferPhiInstruction =
+ TransferPhi && TransferPhi->addDef(*TransferDestination) &&
+ TransferPhi->addUse(*TransferValue) && TransferPhi->addBasicBlock(**From)
+ ? TransferPhi->build()
+ : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected(
+ rcc::ErrorCode::InternalError, "failed to build CFG transfer PHI")};
+ if (!TransferPhiInstruction)
+ return;
+
+ auto FailedTransfer = TransferUpdater.transferSuccessors(**From, **To);
+ Context.expect(
+ !FailedTransfer && (*From)->successors().size() == 1 && (*To)->successors().size() == 1 &&
+ (*Successor)->predecessors().size() == 2 &&
+ (*TransferPhiInstruction)->operandCount() == 3 &&
+ (*TransferPhiInstruction)->operandAt(2)->getIf<rcc::BasicBlockOperand>()->Block == *From,
+ "failed successor transfer must preserve both CFG edges and PHI operands");
+}
+
} // namespace
int main() {
@@ -472,6 +574,7 @@ int main() {
testAliasAnalysis(Context);
testMemoryDependence(Context, *Target);
testCFGUpdaterPHIs(Context, *Target);
+ testCFGUpdaterFailureAtomicity(Context, *Target);
testAtomicStandardRegistration(Context);
return Context.result();
}
diff --git a/backend/unittests/CodeGen/MachineSSAExitTest.cpp b/backend/unittests/CodeGen/MachineSSAExitTest.cpp
new file mode 100644
index 0000000..7c65345
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineSSAExitTest.cpp
@@ -0,0 +1,1113 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineSSAExit.h"
+
+#include "Target/TestTarget.h"
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <optional>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace {
+
+constexpr std::uint32_t DefOpcode = 1024;
+constexpr std::uint32_t UseOpcode = 1025;
+constexpr std::uint32_t ConditionalBranchOpcode = 1026;
+constexpr std::uint32_t JumpOpcode = 1027;
+constexpr std::uint32_t ReturnOpcode = 1028;
+constexpr std::uint32_t MetaOpcode = 1029;
+constexpr std::uint32_t TiedOpcode = 1030;
+constexpr std::uint32_t CommutableTiedOpcode = 1031;
+constexpr std::uint32_t ConvertibleTiedOpcode = 1032;
+constexpr std::uint32_t ThreeAddressOpcode = 1033;
+
+class TestContext final {
+public:
+ void expect(bool Condition, std::string_view Message) {
+ if (Condition)
+ return;
+ std::cerr << Message << '\n';
+ ++Failures;
+ }
+
+ [[nodiscard]] int result() const noexcept {
+ return Failures == 0 ? 0 : 1;
+ }
+
+private:
+ int Failures = 0;
+};
+
+[[nodiscard]] rcc::Opcode testOpcode(std::uint32_t Value) {
+ return rcc::Opcode::fromValue(Value);
+}
+
+[[nodiscard]] rcc::OperandDescriptor registerOperand(rcc::RegisterOperandRole Role,
+ bool AllowSubReg = true) {
+ rcc::OperandDescriptor Result;
+ Result.Kinds = {rcc::MachineOperand::Kind::Register};
+ Result.RegisterRole = Role;
+ Result.AllowSubReg = AllowSubReg;
+ Result.AllowAnyTargetFlags = true;
+ return Result;
+}
+
+[[nodiscard]] rcc::OperandDescriptor blockOperand() {
+ rcc::OperandDescriptor Result;
+ Result.Kinds = {rcc::MachineOperand::Kind::BasicBlock};
+ return Result;
+}
+
+[[nodiscard]] rcc::InstructionDescriptor instruction(std::uint32_t Value, std::string Name) {
+ rcc::InstructionDescriptor Result;
+ Result.InstructionOpcode = testOpcode(Value);
+ Result.Name = std::move(Name);
+ Result.Flags = {rcc::InstructionFlag::ProducesCode};
+ return Result;
+}
+
+[[nodiscard]] rcc::Expected<rcc::TargetDescription> createTarget() {
+ std::vector<rcc::InstructionDescriptor> Descriptors;
+ std::vector<rcc::ImmediatePredicate> Predicates;
+ auto Generic = rcc::appendGenericInstructionInfo(Descriptors, Predicates);
+ if (!Generic)
+ return std::unexpected(Generic.error());
+
+ auto Def = instruction(DefOpcode, "TEST_DEF");
+ Def.Operands = {registerOperand(rcc::RegisterOperandRole::Def)};
+ Def.NumExplicitDefs = 1;
+ Descriptors.push_back(std::move(Def));
+
+ auto Use = instruction(UseOpcode, "TEST_USE");
+ Use.Operands = {registerOperand(rcc::RegisterOperandRole::Use)};
+ Descriptors.push_back(std::move(Use));
+
+ auto Conditional = instruction(ConditionalBranchOpcode, "TEST_BRCOND");
+ Conditional.Operands = {registerOperand(rcc::RegisterOperandRole::Use, false), blockOperand()};
+ Conditional.Flags.set(rcc::InstructionFlag::Branch);
+ Conditional.Flags.set(rcc::InstructionFlag::Terminator);
+ Descriptors.push_back(std::move(Conditional));
+
+ auto Jump = instruction(JumpOpcode, "TEST_JUMP");
+ Jump.Operands = {blockOperand()};
+ Jump.Flags.set(rcc::InstructionFlag::Branch);
+ Jump.Flags.set(rcc::InstructionFlag::Terminator);
+ Jump.Flags.set(rcc::InstructionFlag::Barrier);
+ Descriptors.push_back(std::move(Jump));
+
+ auto Return = instruction(ReturnOpcode, "TEST_RETURN");
+ Return.Flags.set(rcc::InstructionFlag::Return);
+ Return.Flags.set(rcc::InstructionFlag::Terminator);
+ Return.Flags.set(rcc::InstructionFlag::Barrier);
+ Descriptors.push_back(std::move(Return));
+
+ auto Meta = instruction(MetaOpcode, "TEST_META");
+ Meta.Flags = {rcc::InstructionFlag::Pseudo, rcc::InstructionFlag::Meta};
+ Descriptors.push_back(std::move(Meta));
+
+ auto Tied = instruction(TiedOpcode, "TEST_TIED");
+ auto TiedDef = registerOperand(rcc::RegisterOperandRole::Def);
+ auto TiedUse = registerOperand(rcc::RegisterOperandRole::Use);
+ TiedDef.DefaultTiedOperand = 1;
+ TiedUse.DefaultTiedOperand = 0;
+ Tied.Operands = {TiedDef, TiedUse};
+ Tied.NumExplicitDefs = 1;
+ Descriptors.push_back(std::move(Tied));
+
+ auto Commutable = instruction(CommutableTiedOpcode, "TEST_COMMUTABLE_TIED");
+ Commutable.Operands = {TiedDef, TiedUse, registerOperand(rcc::RegisterOperandRole::Use)};
+ Commutable.NumExplicitDefs = 1;
+ Commutable.Flags.set(rcc::InstructionFlag::Commutable);
+ Descriptors.push_back(std::move(Commutable));
+
+ auto Convertible = instruction(ConvertibleTiedOpcode, "TEST_CONVERTIBLE_TIED");
+ Convertible.Operands = {TiedDef, TiedUse};
+ Convertible.NumExplicitDefs = 1;
+ Descriptors.push_back(std::move(Convertible));
+
+ auto ThreeAddress = instruction(ThreeAddressOpcode, "TEST_THREE_ADDRESS");
+ ThreeAddress.Operands = {registerOperand(rcc::RegisterOperandRole::Def),
+ registerOperand(rcc::RegisterOperandRole::Use)};
+ ThreeAddress.NumExplicitDefs = 1;
+ Descriptors.push_back(std::move(ThreeAddress));
+
+ auto Instructions = rcc::InstructionSet::create(std::move(Descriptors), std::move(Predicates));
+ if (!Instructions)
+ return std::unexpected(Instructions.error());
+ return rcc::test::createTestTargetDescription(std::move(*Instructions));
+}
+
+class TestSSAInfo final : public rcc::TargetSSAInfo {
+public:
+ explicit TestSSAInfo(bool RejectCopies = false) : RejectCopies(RejectCopies) {}
+
+ [[nodiscard]] rcc::Expected<bool>
+ isFallthroughEdge(const rcc::MachineBasicBlock &From, const rcc::MachineBasicBlock &To,
+ const rcc::MachineFunction &Function,
+ const rcc::TargetDescription &Target) const override {
+ if (&From.function() != &Function || &To.function() != &Function) {
+ return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument,
+ "fallthrough query references another function");
+ }
+ if (From.next() != &To ||
+ std::ranges::none_of(From.successors(), [&To](const rcc::MachineSuccessor &Successor) {
+ return Successor.Block == &To;
+ })) {
+ return false;
+ }
+
+ bool CanFallThrough = true;
+ for (const rcc::MachineInstr *Instruction = From.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ const rcc::InstructionDescriptor *Descriptor =
+ Target.instructionDescriptor(Instruction->opcode());
+ if (Descriptor == nullptr) {
+ return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+ "fallthrough query encountered an unknown opcode");
+ }
+ if (Descriptor->Flags.has(rcc::InstructionFlag::Terminator))
+ CanFallThrough = Instruction->opcode() == testOpcode(ConditionalBranchOpcode);
+ }
+ return CanFallThrough;
+ }
+
+ [[nodiscard]] rcc::Expected<bool>
+ rewriteBranchTarget(rcc::MachineBasicBlock &Block, rcc::MachineBasicBlock &OldTarget,
+ rcc::MachineBasicBlock &NewTarget, rcc::MachineFunction &Function,
+ const rcc::TargetDescription &Target) const override {
+ if (&Block.function() != &Function || &OldTarget.function() != &Function ||
+ &NewTarget.function() != &Function) {
+ return rcc::makeUnexpected(rcc::ErrorCode::InvalidArgument,
+ "branch rewrite references another function");
+ }
+ bool Changed = false;
+ for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ const rcc::InstructionDescriptor *Descriptor =
+ Target.instructionDescriptor(Instruction->opcode());
+ if (Descriptor == nullptr)
+ return rcc::makeUnexpected(rcc::ErrorCode::VerificationError, "unknown branch opcode");
+ if (!Descriptor->Flags.has(rcc::InstructionFlag::Branch))
+ continue;
+ for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+ rcc::MachineOperand *Operand = Instruction->operandAt(Index);
+ const auto *BlockOperand =
+ Operand == nullptr ? nullptr : Operand->getIf<rcc::BasicBlockOperand>();
+ if (BlockOperand == nullptr || BlockOperand->Block != &OldTarget)
+ continue;
+ auto Rewritten = Operand->setBasicBlock(NewTarget);
+ if (!Rewritten)
+ return std::unexpected(Rewritten.error());
+ Changed = true;
+ }
+ }
+ return Changed;
+ }
+
+ [[nodiscard]] rcc::Expected<void>
+ insertUnconditionalBranch(rcc::MachineBasicBlock &Block, rcc::MachineBasicBlock &TargetBlock,
+ rcc::MachineFunction &Function,
+ const rcc::TargetDescription &Target) const override {
+ rcc::MachineIRBuilder Builder(Function, Target);
+ auto Point = Builder.setInsertPoint(Block);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Pending = Builder.buildInstr(testOpcode(JumpOpcode));
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ auto Destination = Pending->addBasicBlock(TargetBlock);
+ if (!Destination)
+ return std::unexpected(Destination.error());
+ auto Built = Pending->build();
+ if (!Built)
+ return std::unexpected(Built.error());
+ return {};
+ }
+
+ [[nodiscard]] rcc::Expected<void>
+ validateCopy(rcc::Register Destination, rcc::SubRegIndex DestinationSubReg, rcc::Register Source,
+ rcc::SubRegIndex SourceSubReg, const rcc::MachineFunction &Function,
+ const rcc::TargetDescription &Target) const override {
+ if (RejectCopies) {
+ return rcc::makeUnexpected(rcc::ErrorCode::Unsupported,
+ "test target intentionally rejects COPY");
+ }
+ if (Destination.isNoRegister() || Source.isNoRegister()) {
+ return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+ "COPY requires nonzero registers");
+ }
+ if ((Destination.isPhysical() && DestinationSubReg.value() != 0) ||
+ (Source.isPhysical() && SourceSubReg.value() != 0)) {
+ return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+ "physical COPY operands cannot carry subregisters");
+ }
+ auto Def = rcc::MachineOperand::registerOperand(Destination, {rcc::RegisterOperandFlag::Define},
+ DestinationSubReg);
+ auto Use =
+ rcc::MachineOperand::registerOperand(Source, {rcc::RegisterOperandFlag::Use}, SourceSubReg);
+ if (!Def || !Use)
+ return rcc::makeUnexpected(rcc::ErrorCode::InternalError, "failed to model COPY operands");
+ return Target.validateTieCompatibility(*Def, *Use, Function.registerInfo());
+ }
+
+ [[nodiscard]] rcc::Expected<bool>
+ tryConvertToThreeAddress(rcc::MachineInstr &Instruction, std::size_t DefIndex,
+ std::size_t UseIndex, rcc::MachineFunction &,
+ const rcc::TargetDescription &) const override {
+ if (Instruction.opcode() != testOpcode(ConvertibleTiedOpcode))
+ return false;
+ if (DefIndex != 0 || UseIndex != 1)
+ return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+ "unexpected convertible tie indices");
+ auto Untied = Instruction.untieOperand(DefIndex);
+ if (!Untied)
+ return std::unexpected(Untied.error());
+ auto Opcode = Instruction.setOpcode(testOpcode(ThreeAddressOpcode));
+ if (!Opcode)
+ return std::unexpected(Opcode.error());
+ return true;
+ }
+
+private:
+ bool RejectCopies = false;
+};
+
+struct FunctionFixture final {
+ std::unique_ptr<rcc::MachineFunction> Function;
+ std::vector<rcc::MachineBasicBlock *> Blocks;
+};
+
+[[nodiscard]] FunctionFixture createFunction(TestContext &Context, std::string Name,
+ std::uint64_t ID, std::size_t BlockCount) {
+ auto Function =
+ rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID));
+ Context.expect(Function.has_value(), "SSA-exit function creation must succeed");
+ if (!Function)
+ return {};
+
+ FunctionFixture Result{std::move(*Function), {}};
+ for (std::size_t Index = 0; Index < BlockCount; ++Index) {
+ auto Block = Result.Function->createBasicBlock();
+ Context.expect(Block && Result.Function->appendBlock(**Block).has_value(),
+ "SSA-exit block creation must succeed");
+ if (!Block)
+ return {};
+ Result.Blocks.push_back(*Block);
+ }
+ return Result;
+}
+
+[[nodiscard]] rcc::Expected<rcc::Register>
+createVReg(rcc::MachineFunction &Function, rcc::LLT Type, rcc::RegisterBankID Bank,
+ rcc::RegisterClassID Class, std::uint8_t TargetFlags = 0,
+ std::optional<rcc::PhysicalRegister> Hint = std::nullopt) {
+ auto Reg = Function.registerInfo().createVirtualRegister(Type);
+ if (!Reg)
+ return std::unexpected(Reg.error());
+ auto BankResult = Function.registerInfo().setRegisterBank(*Reg, Bank);
+ if (!BankResult)
+ return std::unexpected(BankResult.error());
+ auto ClassResult = Function.registerInfo().setRegisterClass(*Reg, Class);
+ if (!ClassResult)
+ return std::unexpected(ClassResult.error());
+ if (TargetFlags != 0) {
+ auto FlagsResult = Function.registerInfo().setTargetRegisterFlags(*Reg, TargetFlags);
+ if (!FlagsResult)
+ return std::unexpected(FlagsResult.error());
+ }
+ if (Hint) {
+ auto HintResult = Function.registerInfo().addAllocationHint(*Reg, *Hint);
+ if (!HintResult)
+ return std::unexpected(HintResult.error());
+ }
+ return *Reg;
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildRegisterInstruction(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+ rcc::MachineBasicBlock &Block, rcc::Opcode Opcode,
+ std::span<const rcc::Register> Defs, std::span<const rcc::Register> Uses,
+ rcc::RegisterOperandFlags DefFlags = {},
+ rcc::RegisterOperandFlags UseFlags = {}) {
+ rcc::MachineIRBuilder Builder(Function, Target);
+ auto Point = Builder.setInsertPoint(Block);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Pending = Builder.buildInstr(Opcode);
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ for (rcc::Register Reg : Defs) {
+ auto Added = Pending->addDef(Reg, DefFlags);
+ if (!Added)
+ return std::unexpected(Added.error());
+ }
+ for (rcc::Register Reg : Uses) {
+ auto Added = Pending->addUse(Reg, UseFlags);
+ if (!Added)
+ return std::unexpected(Added.error());
+ }
+ return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *> buildJump(rcc::MachineFunction &Function,
+ const rcc::TargetDescription &Target,
+ rcc::MachineBasicBlock &Block,
+ rcc::MachineBasicBlock &Destination) {
+ rcc::MachineIRBuilder Builder(Function, Target);
+ auto Point = Builder.setInsertPoint(Block);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Pending = Builder.buildInstr(testOpcode(JumpOpcode));
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ auto TargetOperand = Pending->addBasicBlock(Destination);
+ if (!TargetOperand)
+ return std::unexpected(TargetOperand.error());
+ return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+ rcc::MachineBasicBlock &Block, rcc::Register Destination,
+ std::span<const std::pair<rcc::Register, rcc::MachineBasicBlock *>> Incoming,
+ rcc::RegisterOperandFlags DestinationFlags = {}, std::uint32_t DestinationTargetFlags = 0,
+ rcc::RegisterOperandFlags IncomingFlags = {}, std::uint32_t IncomingTargetFlags = 0) {
+ rcc::MachineIRBuilder Builder(Function, Target);
+ auto Point = Builder.setInsertPoint(Block);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI));
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ auto Def = Pending->addDef(Destination, DestinationFlags, {}, DestinationTargetFlags);
+ if (!Def)
+ return std::unexpected(Def.error());
+ for (const auto &[Value, Predecessor] : Incoming) {
+ auto Use = Pending->addUse(Value, IncomingFlags, {}, IncomingTargetFlags);
+ if (!Use)
+ return std::unexpected(Use.error());
+ auto IncomingBlock = Pending->addBasicBlock(*Predecessor);
+ if (!IncomingBlock)
+ return std::unexpected(IncomingBlock.error());
+ }
+ return Pending->build();
+}
+
+void setSelectedSSAProperties(rcc::MachineFunction &Function) {
+ for (rcc::MachineFunctionProperty Property :
+ {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness,
+ rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
+ rcc::MachineFunctionProperty::Selected}) {
+ Function.properties().set(Property);
+ }
+}
+
+[[nodiscard]] rcc::Expected<void> runPHIElimination(rcc::MachineFunction &Function,
+ const rcc::TargetDescription &Target,
+ const rcc::TargetSSAInfo &Info) {
+ rcc::MachinePassManager Pipeline;
+ auto Added = Pipeline.addPass(std::make_unique<rcc::PHIEliminationPass>(Info));
+ if (!Added)
+ return std::unexpected(Added.error());
+ rcc::MachineAnalysisManager Analyses;
+ return Pipeline.run(Function, Target, Analyses);
+}
+
+[[nodiscard]] std::vector<rcc::MachineInstr *> linkedInstructions(rcc::MachineBasicBlock &Block) {
+ std::vector<rcc::MachineInstr *> Result;
+ for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ Result.push_back(Instruction);
+ }
+ return Result;
+}
+
+[[nodiscard]] std::vector<rcc::MachineInstr *>
+instructionsWithOpcode(rcc::MachineFunction &Function, rcc::Opcode Opcode) {
+ std::vector<rcc::MachineInstr *> Result;
+ for (rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+ Block = Block->next()) {
+ for (rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ if (Instruction->opcode() == Opcode)
+ Result.push_back(Instruction);
+ }
+ }
+ return Result;
+}
+
+[[nodiscard]] bool hasLiveIn(const rcc::MachineBasicBlock &Block, rcc::PhysicalRegister Reg) {
+ return std::ranges::any_of(Block.liveIns(), [Reg](const rcc::MachineBasicBlockLiveIn &LiveIn) {
+ return LiveIn.PhysReg == Reg;
+ });
+}
+
+void testParallelPHIsAndPlacement(TestContext &Context, const rcc::TargetDescription &Target,
+ const TestSSAInfo &Info) {
+ auto Fixture = createFunction(Context, "parallel_phis", 1, 3);
+ if (!Fixture.Function || Fixture.Blocks.size() != 3)
+ return;
+ auto I64 = rcc::LLT::makeInteger(64);
+ if (!I64)
+ return;
+ auto &Function = *Fixture.Function;
+ rcc::MachineBasicBlock &Preheader = *Fixture.Blocks[0];
+ rcc::MachineBasicBlock &Header = *Fixture.Blocks[1];
+ rcc::MachineBasicBlock &Backedge = *Fixture.Blocks[2];
+ const rcc::PhysicalRegister Hint = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G1);
+
+ auto InitA = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ auto InitB = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ auto DestinationA = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64, 0x1, Hint);
+ auto DestinationB = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ Context.expect(InitA && InitB && DestinationA && DestinationB,
+ "parallel PHI registers must be created");
+ if (!InitA || !InitB || !DestinationA || !DestinationB)
+ return;
+
+ auto CFG = Function.cfgUpdater();
+ Context.expect(
+ CFG.addSuccessor(Preheader, Header, rcc::BranchProbability::one()).has_value() &&
+ CFG.addSuccessor(Header, Backedge, rcc::BranchProbability::one()).has_value() &&
+ CFG.addSuccessor(Backedge, Header, rcc::BranchProbability::one()).has_value(),
+ "parallel PHI loop CFG must be connected");
+
+ const std::array InitADef{*InitA};
+ const std::array InitBDef{*InitB};
+ Context.expect(buildRegisterInstruction(Function, Target, Preheader, testOpcode(DefOpcode),
+ InitADef, {}, {rcc::RegisterOperandFlag::Dead}) &&
+ buildRegisterInstruction(Function, Target, Preheader, testOpcode(DefOpcode),
+ InitBDef, {}) &&
+ buildJump(Function, Target, Preheader, Header),
+ "parallel PHI preheader must be populated");
+
+ const std::array IncomingA{
+ std::pair<rcc::Register, rcc::MachineBasicBlock *>{*InitA, &Preheader},
+ std::pair<rcc::Register, rcc::MachineBasicBlock *>{*DestinationB, &Backedge}};
+ const std::array IncomingB{
+ std::pair<rcc::Register, rcc::MachineBasicBlock *>{*InitB, &Preheader},
+ std::pair<rcc::Register, rcc::MachineBasicBlock *>{*DestinationA, &Backedge}};
+ Context.expect(buildPhi(Function, Target, Header, *DestinationA, IncomingA, {}, 0x4, {}, 0x8) &&
+ buildPhi(Function, Target, Header, *DestinationB, IncomingB),
+ "parallel PHIs must be built");
+
+ rcc::MachineIRBuilder HeaderBuilder(Function, Target);
+ if (!HeaderBuilder.setInsertPoint(Header))
+ return;
+ auto Meta = HeaderBuilder.buildInstr(testOpcode(MetaOpcode));
+ const std::array HeaderUse{*DestinationA};
+ Context.expect(Meta && Meta->build() &&
+ buildRegisterInstruction(Function, Target, Header, testOpcode(UseOpcode), {},
+ HeaderUse) &&
+ buildJump(Function, Target, Header, Backedge),
+ "parallel PHI header must contain meta, code, and terminator instructions");
+
+ const std::array KilledUse{*DestinationA};
+ Context.expect(buildRegisterInstruction(Function, Target, Backedge, testOpcode(UseOpcode), {},
+ KilledUse, {}, {rcc::RegisterOperandFlag::Kill}) &&
+ buildJump(Function, Target, Backedge, Header),
+ "parallel PHI backedge must be populated");
+ setSelectedSSAProperties(Function);
+
+ auto Run = runPHIElimination(Function, Target, Info);
+ Context.expect(Run.has_value(), "parallel PHI elimination must succeed");
+ if (!Run)
+ return;
+ Context.expect(!Function.properties().has(rcc::MachineFunctionProperty::IsSSA) &&
+ Function.properties().has(rcc::MachineFunctionProperty::NoPHIs) &&
+ Function.properties().has(rcc::MachineFunctionProperty::TracksLiveness),
+ "PHI elimination must publish its exact property transition");
+ Context.expect(instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::PHI)).empty(),
+ "PHI elimination must remove every PHI");
+
+ const auto HeaderInstructions = linkedInstructions(Header);
+ Context.expect(HeaderInstructions.size() == 5 &&
+ HeaderInstructions[0]->opcode() == testOpcode(MetaOpcode) &&
+ HeaderInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+ HeaderInstructions[2]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+ HeaderInstructions[3]->opcode() == testOpcode(UseOpcode) &&
+ HeaderInstructions[4]->opcode() == testOpcode(JumpOpcode),
+ "destination COPYs must follow the full leading PHI/meta region");
+ if (HeaderInstructions.size() < 3)
+ return;
+
+ const rcc::Register *FreshA = HeaderInstructions[1]->operandAt(1)->getIf<rcc::Register>();
+ const rcc::Register *FreshB = HeaderInstructions[2]->operandAt(1)->getIf<rcc::Register>();
+ Context.expect(FreshA != nullptr && FreshB != nullptr && *FreshA != *FreshB &&
+ *FreshA != *DestinationA && *FreshB != *DestinationB,
+ "each PHI must receive an independent fresh incoming vreg");
+ if (FreshA == nullptr || FreshB == nullptr)
+ return;
+
+ const auto BackedgeInstructions = linkedInstructions(Backedge);
+ Context.expect(BackedgeInstructions.size() == 4 &&
+ BackedgeInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+ BackedgeInstructions[2]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+ BackedgeInstructions[3]->opcode() == testOpcode(JumpOpcode),
+ "incoming COPYs must be placed together before the first terminator");
+ if (BackedgeInstructions.size() >= 3) {
+ const auto FirstDef = BackedgeInstructions[1]->operandAt(0)->registerValue();
+ const auto FirstUse = BackedgeInstructions[1]->operandAt(1)->registerValue();
+ const auto SecondDef = BackedgeInstructions[2]->operandAt(0)->registerValue();
+ const auto SecondUse = BackedgeInstructions[2]->operandAt(1)->registerValue();
+ Context.expect(FirstDef == *FreshA && FirstUse == *DestinationB && SecondDef == *FreshB &&
+ SecondUse == *DestinationA,
+ "backedge COPYs must read old PHI destinations into distinct temporaries");
+ }
+
+ auto FreshInfo = Function.registerInfo().virtualRegisterInfo(*FreshA);
+ Context.expect(FreshInfo.has_value(), "fresh PHI vreg must remain registered");
+ if (!FreshInfo)
+ return;
+ Context.expect(FreshInfo->get().Type == I64, "fresh PHI vreg must clone its LLT");
+ Context.expect(FreshInfo->get().Bank == rcc::test::TestRegisterBank::GPR,
+ "fresh PHI vreg must clone its register bank");
+ Context.expect(FreshInfo->get().RegClass == rcc::test::TestRegisterClass::GPR64,
+ "fresh PHI vreg must clone its register class");
+ Context.expect(FreshInfo->get().TargetFlags == 0x1,
+ "fresh PHI vreg must clone registered target flags");
+ Context.expect(FreshInfo->get().AllocationHints.size() == 1,
+ "fresh PHI vreg must clone the allocation-hint count");
+ Context.expect(!FreshInfo->get().AllocationHints.empty() &&
+ FreshInfo->get().AllocationHints.front() == Hint,
+ "fresh PHI vreg must clone the allocation-hint register");
+ Context.expect(HeaderInstructions[1]->operandAt(0)->targetFlags() == 0x4 &&
+ HeaderInstructions[1]->operandAt(1)->targetFlags() == 0x4,
+ "successor COPY must preserve registered destination target flags");
+
+ const rcc::MachineInstr *InitDefinition = Preheader.firstInstruction();
+ Context.expect(
+ InitDefinition != nullptr &&
+ !InitDefinition->operandAt(0)->registerFlags().has(rcc::RegisterOperandFlag::Dead) &&
+ !BackedgeInstructions[0]->operandAt(0)->registerFlags().has(
+ rcc::RegisterOperandFlag::Kill),
+ "liveness-preserving PHI elimination must conservatively clear kill/dead flags");
+ Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
+ "parallel PHI result must pass MachineVerifier");
+}
+
+void testCriticalEdgeAndPhysicalLiveIn(TestContext &Context, const rcc::TargetDescription &Target,
+ const TestSSAInfo &Info) {
+ auto Fixture = createFunction(Context, "critical_edge", 2, 4);
+ if (!Fixture.Function || Fixture.Blocks.size() != 4)
+ return;
+ auto I64 = rcc::LLT::makeInteger(64);
+ if (!I64)
+ return;
+ auto &Function = *Fixture.Function;
+ rcc::MachineBasicBlock &From = *Fixture.Blocks[0];
+ rcc::MachineBasicBlock &Side = *Fixture.Blocks[1];
+ rcc::MachineBasicBlock &Other = *Fixture.Blocks[2];
+ rcc::MachineBasicBlock &Merge = *Fixture.Blocks[3];
+ auto Condition = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ auto OtherValue = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ auto Destination = createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ if (!Condition || !OtherValue || !Destination)
+ return;
+
+ auto Half = rcc::BranchProbability::fromFraction(1, 2);
+ auto CFG = Function.cfgUpdater();
+ Context.expect(Half && CFG.addSuccessor(From, Side, *Half) &&
+ CFG.addSuccessor(From, Merge, *Half) &&
+ CFG.addSuccessor(Other, Merge, rcc::BranchProbability::one()),
+ "critical-edge CFG must be connected");
+
+ const std::array ConditionDef{*Condition};
+ Context.expect(
+ buildRegisterInstruction(Function, Target, From, testOpcode(DefOpcode), ConditionDef, {})
+ .has_value(),
+ "critical-edge condition must be defined");
+ rcc::MachineIRBuilder FromBuilder(Function, Target);
+ if (!FromBuilder.setInsertPoint(From))
+ return;
+ auto Branch = FromBuilder.buildInstr(testOpcode(ConditionalBranchOpcode));
+ Context.expect(Branch && Branch->addUse(*Condition) && Branch->addBasicBlock(Merge) &&
+ Branch->build(),
+ "critical-edge conditional branch must be built");
+ const std::array OtherDef{*OtherValue};
+ Context.expect(
+ buildRegisterInstruction(Function, Target, Other, testOpcode(DefOpcode), OtherDef, {})
+ .has_value(),
+ "unrelated fallthrough predecessor must define its incoming value");
+
+ const rcc::PhysicalRegister G0 = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G0);
+ const rcc::PhysicalRegister G1 = *rcc::PhysicalRegister::create(rcc::test::TestRegister::G1);
+ Context.expect(Merge.addLiveIn(G1, rcc::LaneMask::fromRaw(0xF)).has_value(),
+ "merge block live-in setup must succeed");
+ const std::array Incoming{
+ std::pair<rcc::Register, rcc::MachineBasicBlock *>{rcc::Register::fromPhysical(G0), &From},
+ std::pair<rcc::Register, rcc::MachineBasicBlock *>{*OtherValue, &Other}};
+ Context.expect(buildPhi(Function, Target, Merge, *Destination, Incoming).has_value(),
+ "critical-edge PHI must be built");
+ setSelectedSSAProperties(Function);
+
+ auto Run = runPHIElimination(Function, Target, Info);
+ Context.expect(Run.has_value(), "critical-edge PHI elimination must succeed");
+ if (!Run)
+ return;
+
+ rcc::MachineBasicBlock *Edge = Merge.previous();
+ Context.expect(
+ Edge != nullptr && Edge != &Other && Edge->previous() == &Other &&
+ From.successors().size() == 2 &&
+ std::ranges::any_of(From.successors(),
+ [Edge](const rcc::MachineSuccessor &S) { return S.Block == Edge; }) &&
+ Edge->predecessors().size() == 1 && Edge->predecessors()[0] == &From &&
+ Edge->successors().size() == 1 && Edge->successors()[0].Block == &Merge,
+ "critical edge must become a reciprocal From-to-edge-to-Merge CFG path");
+ if (Edge == nullptr || Edge == &Other)
+ return;
+
+ const rcc::MachineOperand *BranchTarget = From.lastInstruction()->operandAt(1);
+ const auto *BranchBlock =
+ BranchTarget == nullptr ? nullptr : BranchTarget->getIf<rcc::BasicBlockOperand>();
+ Context.expect(BranchBlock != nullptr && BranchBlock->Block == Edge,
+ "explicit critical-edge branch must target the split block");
+ const auto OtherInstructions = linkedInstructions(Other);
+ const auto EdgeInstructions = linkedInstructions(*Edge);
+ Context.expect(OtherInstructions.size() == 3 &&
+ OtherInstructions.back()->opcode() == testOpcode(JumpOpcode) &&
+ EdgeInstructions.size() == 2 &&
+ EdgeInstructions[0]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+ EdgeInstructions[1]->opcode() == testOpcode(JumpOpcode),
+ "edge split must preserve unrelated fallthrough and terminator placement");
+ Context.expect(hasLiveIn(*Edge, G0) && hasLiveIn(*Edge, G1),
+ "split edge must inherit successor live-ins and its physical PHI source");
+ Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
+ "critical-edge result must pass MachineVerifier");
+}
+
+void testUndefAndFailureAtomicity(TestContext &Context, const rcc::TargetDescription &Target,
+ const TestSSAInfo &Info) {
+ auto BuildFixture = [&](std::uint64_t ID) {
+ auto Fixture = createFunction(Context, "undef_phi", ID, 2);
+ if (!Fixture.Function || Fixture.Blocks.size() != 2)
+ return Fixture;
+ auto I64 = rcc::LLT::makeInteger(64);
+ if (!I64)
+ return Fixture;
+ auto Source = createVReg(*Fixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ auto Destination = createVReg(*Fixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ if (!Source || !Destination)
+ return Fixture;
+ auto CFG = Fixture.Function->cfgUpdater();
+ if (!CFG.addSuccessor(*Fixture.Blocks[0], *Fixture.Blocks[1], rcc::BranchProbability::one()) ||
+ !buildJump(*Fixture.Function, Target, *Fixture.Blocks[0], *Fixture.Blocks[1])) {
+ return Fixture;
+ }
+ const std::array Incoming{
+ std::pair<rcc::Register, rcc::MachineBasicBlock *>{*Source, Fixture.Blocks[0]}};
+ if (!buildPhi(*Fixture.Function, Target, *Fixture.Blocks[1], *Destination, Incoming, {}, 0,
+ {rcc::RegisterOperandFlag::Undef})) {
+ return Fixture;
+ }
+ setSelectedSSAProperties(*Fixture.Function);
+ return Fixture;
+ };
+
+ auto Undef = BuildFixture(3);
+ if (!Undef.Function)
+ return;
+ auto Run = runPHIElimination(*Undef.Function, Target, Info);
+ Context.expect(Run.has_value(), "undef PHI elimination must succeed");
+ if (Run) {
+ const auto PredecessorInstructions = linkedInstructions(*Undef.Blocks[0]);
+ Context.expect(PredecessorInstructions.size() == 2 &&
+ PredecessorInstructions[0]->opcode() ==
+ rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF) &&
+ PredecessorInstructions[1]->opcode() == testOpcode(JumpOpcode),
+ "undef PHI incoming values must become edge IMPLICIT_DEF instructions");
+ }
+
+ auto Atomic = BuildFixture(4);
+ if (!Atomic.Function)
+ return;
+ const std::size_t BlocksBefore = Atomic.Function->blockCount();
+ const std::size_t InstructionsBefore =
+ instructionsWithOpcode(*Atomic.Function, rcc::opcode(rcc::GenericOpcode::PHI)).size();
+ const std::size_t RegistersBefore = Atomic.Function->registerInfo().virtualRegisters().size();
+ const std::uint64_t PropertiesBefore = Atomic.Function->properties().rawValue();
+ TestSSAInfo RejectingInfo(true);
+ rcc::MachineAnalysisManager Analyses;
+ rcc::PHIEliminationPass FailingPass(RejectingInfo);
+ auto Failed = FailingPass.run(*Atomic.Function, Target, Analyses);
+ Context.expect(!Failed && Failed.error().code() == rcc::ErrorCode::Unsupported,
+ "COPY rejection must produce a structured PHI-elimination failure");
+ Context.expect(
+ Atomic.Function->blockCount() == BlocksBefore &&
+ instructionsWithOpcode(*Atomic.Function, rcc::opcode(rcc::GenericOpcode::PHI)).size() ==
+ InstructionsBefore &&
+ Atomic.Function->registerInfo().virtualRegisters().size() == RegistersBefore &&
+ Atomic.Function->properties().rawValue() == PropertiesBefore,
+ "failed PHI transaction preflight must leave the original function unchanged");
+
+ rcc::PHIEliminationPass MissingBehavior;
+ auto Missing = MissingBehavior.run(*Atomic.Function, Target, Analyses);
+ Context.expect(!Missing && Missing.error().code() == rcc::ErrorCode::InvalidArgument,
+ "PHI elimination without target behavior must fail explicitly");
+}
+
+void testTwoAddressAndSubregisterPseudos(TestContext &Context, const rcc::TargetDescription &Target,
+ const TestSSAInfo &Info) {
+ auto Fixture = createFunction(Context, "two_address", 5, 1);
+ if (!Fixture.Function || Fixture.Blocks.empty())
+ return;
+ auto I64 = rcc::LLT::makeInteger(64);
+ auto I32 = rcc::LLT::makeInteger(32);
+ if (!I64 || !I32)
+ return;
+ auto &Function = *Fixture.Function;
+ rcc::MachineBasicBlock &Block = *Fixture.Blocks[0];
+ auto GPR64 = [&](std::uint8_t Flags = 0) {
+ return createVReg(Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64, Flags);
+ };
+ auto GPR32 = [&]() {
+ return createVReg(Function, *I32, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR32);
+ };
+
+ auto Satisfied = GPR64();
+ auto UndefSource = GPR64();
+ auto UndefDestination = GPR64();
+ auto CommuteSource = GPR64();
+ auto CommuteDestination = GPR64();
+ auto ConvertSource = GPR64();
+ auto ConvertDestination = GPR64();
+ auto FallbackSource = GPR64();
+ auto FallbackDestination = GPR64();
+ auto SequenceDestination = GPR64();
+ auto SequenceLow = GPR32();
+ auto SequenceHigh = GPR32();
+ auto InsertDestination = GPR64();
+ auto InsertBase = GPR64();
+ auto Inserted = GPR32();
+ const bool Complete = Satisfied && UndefSource && UndefDestination && CommuteSource &&
+ CommuteDestination && ConvertSource && ConvertDestination &&
+ FallbackSource && FallbackDestination && SequenceDestination &&
+ SequenceLow && SequenceHigh && InsertDestination && InsertBase && Inserted;
+ Context.expect(Complete, "two-address test registers must be created");
+ if (!Complete)
+ return;
+
+ for (rcc::Register Source : {*CommuteSource, *ConvertSource, *FallbackSource, *SequenceLow,
+ *SequenceHigh, *InsertBase, *Inserted}) {
+ const std::array Def{Source};
+ Context.expect(buildRegisterInstruction(Function, Target, Block, testOpcode(DefOpcode), Def, {},
+ {rcc::RegisterOperandFlag::Dead})
+ .has_value(),
+ "two-address source definition must be built");
+ }
+ const std::array UndefDef{*UndefSource};
+ Context.expect(buildRegisterInstruction(Function, Target, Block,
+ rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF), UndefDef,
+ {})
+ .has_value(),
+ "two-address undef source must be defined by IMPLICIT_DEF");
+
+ auto BuildTied = [&](rcc::Opcode Opcode, rcc::Register Def, rcc::Register Use,
+ std::optional<rcc::Register> Other = std::nullopt) {
+ rcc::MachineIRBuilder Builder(Function, Target);
+ auto Point = Builder.setInsertPoint(Block);
+ if (!Point)
+ return rcc::Expected<rcc::MachineInstr *>{std::unexpected(Point.error())};
+ auto Pending = Builder.buildInstr(Opcode);
+ if (!Pending)
+ return rcc::Expected<rcc::MachineInstr *>{std::unexpected(Pending.error())};
+ auto AddedDef = Pending->addDef(Def);
+ if (!AddedDef)
+ return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedDef.error())};
+ auto AddedUse = Pending->addUse(Use, {rcc::RegisterOperandFlag::Kill});
+ if (!AddedUse)
+ return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedUse.error())};
+ if (Other) {
+ auto AddedOther = Pending->addUse(*Other);
+ if (!AddedOther)
+ return rcc::Expected<rcc::MachineInstr *>{std::unexpected(AddedOther.error())};
+ }
+ return Pending->build();
+ };
+
+ auto AlreadyTied = BuildTied(testOpcode(TiedOpcode), *Satisfied, *Satisfied);
+ auto UndefTied = BuildTied(testOpcode(TiedOpcode), *UndefDestination, *UndefSource);
+ auto Commutable = BuildTied(testOpcode(CommutableTiedOpcode), *CommuteDestination, *CommuteSource,
+ *CommuteDestination);
+ auto Convertible =
+ BuildTied(testOpcode(ConvertibleTiedOpcode), *ConvertDestination, *ConvertSource);
+ auto Fallback = BuildTied(testOpcode(TiedOpcode), *FallbackDestination, *FallbackSource);
+ Context.expect(AlreadyTied && UndefTied && Commutable && Convertible && Fallback,
+ "two-address instruction fixtures must be built");
+ if (!AlreadyTied || !UndefTied || !Commutable || !Convertible || !Fallback)
+ return;
+
+ rcc::MachineIRBuilder Builder(Function, Target);
+ if (!Builder.setInsertPoint(Block))
+ return;
+ auto Sequence = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE));
+ Context.expect(
+ Sequence && Sequence->addDef(*SequenceDestination) && Sequence->addUse(*SequenceLow) &&
+ Sequence->addImmediate(rcc::test::TestSubReg::Low32.value()) &&
+ Sequence->addUse(*SequenceHigh) &&
+ Sequence->addImmediate(rcc::test::TestSubReg::High32.value()) && Sequence->build(),
+ "REG_SEQUENCE fixture must be built");
+ auto Insert = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::INSERT_SUBREG));
+ Context.expect(Insert && Insert->addDef(*InsertDestination) && Insert->addUse(*InsertBase) &&
+ Insert->addUse(*Inserted) &&
+ Insert->addImmediate(rcc::test::TestSubReg::Low32.value()) && Insert->build(),
+ "INSERT_SUBREG fixture must be built");
+ auto Return = Builder.buildInstr(testOpcode(ReturnOpcode));
+ Context.expect(Return && Return->build(), "two-address return must be built");
+
+ setSelectedSSAProperties(Function);
+ Function.properties().set(rcc::MachineFunctionProperty::NoPHIs);
+ rcc::MachinePassManager Pipeline;
+ Context.expect(Pipeline.addPass(std::make_unique<rcc::TwoAddressRewritePass>(Info)).has_value(),
+ "two-address pass must be registered");
+ rcc::MachineAnalysisManager Analyses;
+ auto Run = Pipeline.run(Function, Target, Analyses);
+ Context.expect(Run.has_value(), "two-address rewrite must succeed");
+ if (!Run)
+ return;
+
+ Context.expect(Function.properties().has(rcc::MachineFunctionProperty::TiedOpsRewritten) &&
+ !Function.properties().has(rcc::MachineFunctionProperty::IsSSA),
+ "two-address rewrite must publish TiedOpsRewritten and clear IsSSA");
+ Context.expect(
+ instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE)).empty() &&
+ instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::INSERT_SUBREG)).empty(),
+ "TwoAddressRewrite must consume all Stage 10 subregister pseudos");
+
+ Context.expect((*AlreadyTied)->operandAt(1)->registerValue() == *Satisfied,
+ "an already-satisfied tie must remain unchanged");
+ Context.expect(
+ (*UndefTied)->operandAt(1)->registerValue() == *UndefDestination &&
+ (*UndefTied)->operandAt(1)->registerFlags().has(rcc::RegisterOperandFlag::Undef),
+ "undef tied uses must be rewritten without a COPY");
+ Context.expect((*Commutable)->operandAt(1)->registerValue() == *CommuteDestination &&
+ (*Commutable)->operandAt(2)->registerValue() == *CommuteSource,
+ "commutation must satisfy a tie before COPY fallback");
+ Context.expect((*Convertible)->opcode() == testOpcode(ThreeAddressOpcode) &&
+ !(*Convertible)->operandAt(0)->tiedOperandIndex() &&
+ !(*Convertible)->operandAt(1)->tiedOperandIndex(),
+ "target three-address conversion must run before COPY fallback");
+ Context.expect((*Fallback)->previous() != nullptr &&
+ (*Fallback)->previous()->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+ (*Fallback)->previous()->operandAt(0)->registerValue() ==
+ *FallbackDestination &&
+ (*Fallback)->previous()->operandAt(1)->registerValue() == *FallbackSource &&
+ (*Fallback)->operandAt(1)->registerValue() == *FallbackDestination,
+ "unsatisfied ties must receive a COPY immediately before the instruction");
+
+ const auto Copies = instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::COPY));
+ const auto ImplicitDefs =
+ instructionsWithOpcode(Function, rcc::opcode(rcc::GenericOpcode::IMPLICIT_DEF));
+ Context.expect(Copies.size() >= 5 && ImplicitDefs.size() >= 2,
+ "subregister pseudo expansion must materialize base and lane definitions");
+ Context.expect(
+ std::ranges::any_of(Copies,
+ [InsertDestination](const rcc::MachineInstr *Copy) {
+ return Copy->operandAt(0)->registerValue() == *InsertDestination &&
+ Copy->operandAt(0)->subReg() == rcc::test::TestSubReg::Low32;
+ }),
+ "INSERT_SUBREG must copy its inserted value into the requested destination lane");
+ Context.expect(
+ std::ranges::all_of(Function.allInstructions(),
+ [](const rcc::MachineInstr *MI) {
+ if (MI->parent() == nullptr)
+ return true;
+ return std::ranges::none_of(
+ MI->operands(), [](const rcc::MachineOperand &Op) {
+ return Op.registerFlags().has(rcc::RegisterOperandFlag::Kill) ||
+ Op.registerFlags().has(rcc::RegisterOperandFlag::Dead);
+ });
+ }),
+ "two-address rewrite must conservatively clear stale kill/dead flags");
+ Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
+ "two-address and subregister expansion result must verify");
+
+ auto AtomicFixture = createFunction(Context, "two_address_atomic", 10, 1);
+ if (!AtomicFixture.Function || AtomicFixture.Blocks.empty())
+ return;
+ auto AtomicSource = createVReg(*AtomicFixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ auto AtomicDestination =
+ createVReg(*AtomicFixture.Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ if (!AtomicSource || !AtomicDestination)
+ return;
+ const std::array AtomicSourceDef{*AtomicSource};
+ Context.expect(buildRegisterInstruction(*AtomicFixture.Function, Target, *AtomicFixture.Blocks[0],
+ testOpcode(DefOpcode), AtomicSourceDef, {})
+ .has_value(),
+ "two-address atomicity source definition must build");
+ rcc::MachineIRBuilder AtomicBuilder(*AtomicFixture.Function, Target);
+ if (!AtomicBuilder.setInsertPoint(*AtomicFixture.Blocks[0]))
+ return;
+ auto AtomicPending = AtomicBuilder.buildInstr(testOpcode(TiedOpcode));
+ auto AtomicInstruction =
+ AtomicPending && AtomicPending->addDef(*AtomicDestination) &&
+ AtomicPending->addUse(*AtomicSource, {rcc::RegisterOperandFlag::Kill})
+ ? AtomicPending->build()
+ : rcc::Expected<rcc::MachineInstr *>{rcc::makeUnexpected(
+ rcc::ErrorCode::InternalError, "failed to build atomicity fixture")};
+ Context.expect(AtomicInstruction.has_value(),
+ "two-address atomicity tied instruction must build");
+ if (!AtomicInstruction)
+ return;
+ setSelectedSSAProperties(*AtomicFixture.Function);
+ AtomicFixture.Function->properties().set(rcc::MachineFunctionProperty::NoPHIs);
+ const std::size_t AtomicInstructionsBefore = AtomicFixture.Function->allInstructions().size();
+ const std::size_t AtomicRegistersBefore =
+ AtomicFixture.Function->registerInfo().virtualRegisters().size();
+ const std::uint64_t AtomicPropertiesBefore = AtomicFixture.Function->properties().rawValue();
+
+ TestSSAInfo RejectingInfo(true);
+ rcc::MachineAnalysisManager AtomicAnalyses;
+ rcc::TwoAddressRewritePass FailingPass(RejectingInfo);
+ auto Failed = FailingPass.run(*AtomicFixture.Function, Target, AtomicAnalyses);
+ Context.expect(!Failed && Failed.error().code() == rcc::ErrorCode::Unsupported,
+ "COPY rejection must produce a structured two-address failure");
+ Context.expect(
+ AtomicFixture.Function->allInstructions().size() == AtomicInstructionsBefore &&
+ AtomicFixture.Function->registerInfo().virtualRegisters().size() ==
+ AtomicRegistersBefore &&
+ AtomicFixture.Function->properties().rawValue() == AtomicPropertiesBefore &&
+ (*AtomicInstruction)->operandAt(0)->registerValue() == *AtomicDestination &&
+ (*AtomicInstruction)->operandAt(1)->registerValue() == *AtomicSource &&
+ (*AtomicInstruction)->operandAt(1)->registerFlags().has(rcc::RegisterOperandFlag::Kill),
+ "failed two-address transaction preflight must leave the original function unchanged");
+
+ rcc::TwoAddressRewritePass MissingBehavior;
+ auto Missing = MissingBehavior.run(*AtomicFixture.Function, Target, AtomicAnalyses);
+ Context.expect(!Missing && Missing.error().code() == rcc::ErrorCode::InvalidArgument,
+ "two-address rewrite without target behavior must fail explicitly");
+}
+
+void testVerifierAndPseudoFailures(TestContext &Context, const rcc::TargetDescription &Target) {
+ auto BuildBadPhi = [&](std::uint64_t ID, rcc::LLT DestinationType,
+ rcc::RegisterBankID DestinationBank, rcc::RegisterClassID DestinationClass,
+ rcc::LLT SourceType, rcc::RegisterBankID SourceBank,
+ rcc::RegisterClassID SourceClass, rcc::SubRegIndex SourceSubReg = {}) {
+ auto Fixture = createFunction(Context, "bad_phi", ID, 2);
+ if (!Fixture.Function || Fixture.Blocks.size() != 2)
+ return Fixture;
+ auto Destination =
+ createVReg(*Fixture.Function, DestinationType, DestinationBank, DestinationClass);
+ auto Source = createVReg(*Fixture.Function, SourceType, SourceBank, SourceClass);
+ if (!Destination || !Source)
+ return Fixture;
+ auto CFG = Fixture.Function->cfgUpdater();
+ if (!CFG.addSuccessor(*Fixture.Blocks[0], *Fixture.Blocks[1], rcc::BranchProbability::one())) {
+ return Fixture;
+ }
+ const std::array SourceDef{*Source};
+ if (!buildRegisterInstruction(*Fixture.Function, Target, *Fixture.Blocks[0],
+ testOpcode(DefOpcode), SourceDef, {})) {
+ return Fixture;
+ }
+ rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+ if (!Builder.setInsertPoint(*Fixture.Blocks[1]))
+ return Fixture;
+ auto Phi = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI));
+ if (!Phi || !Phi->addDef(*Destination) || !Phi->addUse(*Source, {}, SourceSubReg) ||
+ !Phi->addBasicBlock(*Fixture.Blocks[0]) || !Phi->build()) {
+ return Fixture;
+ }
+ return Fixture;
+ };
+
+ auto I64 = rcc::LLT::makeInteger(64);
+ auto I32 = rcc::LLT::makeInteger(32);
+ if (!I64 || !I32)
+ return;
+ auto BadType =
+ BuildBadPhi(6, *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64,
+ *I32, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR32);
+ Context.expect(BadType.Function && !rcc::MachineVerifier::verify(*BadType.Function, Target),
+ "MachineVerifier must reject incompatible PHI LLTs");
+
+ auto BadClass =
+ BuildBadPhi(7, *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64,
+ *I64, rcc::test::TestRegisterBank::FPR, rcc::test::TestRegisterClass::FPR64);
+ Context.expect(BadClass.Function && !rcc::MachineVerifier::verify(*BadClass.Function, Target),
+ "MachineVerifier must reject nonoverlapping PHI register classes");
+
+ auto BadSubReg =
+ BuildBadPhi(8, *I32, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR32Low,
+ *I64, rcc::test::TestRegisterBank::GPR, rcc::test::TestRegisterClass::GPR64,
+ rcc::test::TestSubReg::High32);
+ Context.expect(BadSubReg.Function && !rcc::MachineVerifier::verify(*BadSubReg.Function, Target),
+ "MachineVerifier must reject incompatible PHI subregister projections");
+
+ auto Residual = createFunction(Context, "residual_stage10_pseudo", 9, 1);
+ if (!Residual.Function || Residual.Blocks.empty())
+ return;
+ auto Destination = createVReg(*Residual.Function, *I64, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR64);
+ auto Source = createVReg(*Residual.Function, *I32, rcc::test::TestRegisterBank::GPR,
+ rcc::test::TestRegisterClass::GPR32);
+ if (!Destination || !Source)
+ return;
+ rcc::MachineIRBuilder Builder(*Residual.Function, Target);
+ if (!Builder.setInsertPoint(*Residual.Blocks[0]))
+ return;
+ auto Sequence = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::REG_SEQUENCE));
+ Context.expect(Sequence && Sequence->addDef(*Destination) && Sequence->addUse(*Source) &&
+ Sequence->addImmediate(rcc::test::TestSubReg::Low32.value()) &&
+ Sequence->build(),
+ "residual Stage 10 pseudo fixture must be built");
+ for (rcc::MachineFunctionProperty Property :
+ {rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
+ rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::NoPHIs,
+ rcc::MachineFunctionProperty::TiedOpsRewritten}) {
+ Residual.Function->properties().set(Property);
+ }
+ Context.expect(!rcc::MachineVerifier::verify(*Residual.Function, Target),
+ "TiedOpsRewritten must reject residual REG_SEQUENCE/INSERT_SUBREG pseudos");
+}
+
+} // namespace
+
+int main() {
+ TestContext Context;
+ auto Target = createTarget();
+ Context.expect(Target.has_value(), "SSA-exit TestTarget must be created");
+ if (!Target)
+ return Context.result();
+ TestSSAInfo Info;
+ testParallelPHIsAndPlacement(Context, *Target, Info);
+ testCriticalEdgeAndPhysicalLiveIn(Context, *Target, Info);
+ testUndefAndFailureAtomicity(Context, *Target, Info);
+ testTwoAddressAndSubregisterPseudos(Context, *Target, Info);
+ testVerifierAndPseudoFailures(Context, *Target);
+ return Context.result();
+}
diff --git a/backend/unittests/CodeGen/MachineVerifierTest.cpp b/backend/unittests/CodeGen/MachineVerifierTest.cpp
index ca265a7..528ff3b 100644
--- a/backend/unittests/CodeGen/MachineVerifierTest.cpp
+++ b/backend/unittests/CodeGen/MachineVerifierTest.cpp
@@ -102,7 +102,15 @@ private:
auto Phi = instructionDescriptor(PhiOpcode, "TEST_PHI");
Phi.Operands.push_back(registerDescriptor(rcc::RegisterOperandRole::Def));
+ auto PhiValue = registerDescriptor(rcc::RegisterOperandRole::Use);
+ PhiValue.VariadicGroup = true;
+ Phi.Operands.push_back(PhiValue);
+ rcc::OperandDescriptor PhiBlock;
+ PhiBlock.Kinds = {rcc::MachineOperand::Kind::BasicBlock};
+ PhiBlock.VariadicGroup = true;
+ Phi.Operands.push_back(PhiBlock);
Phi.NumExplicitDefs = 1;
+ Phi.Variadic = true;
Phi.Flags.set(rcc::InstructionFlag::Pseudo);
Phi.Flags.set(rcc::InstructionFlag::Phi);
Phi.Owner = rcc::PseudoOwner::PhiElimination;
@@ -302,6 +310,103 @@ void testReachableStructuralFailures(TestContext &Context) {
}
}
+enum class PhiTestShape : std::uint8_t {
+ Valid,
+ MissingPredecessor,
+ DuplicatePredecessor,
+ NonPredecessor,
+ AfterInstruction,
+};
+
+[[nodiscard]] std::unique_ptr<rcc::MachineFunction>
+createPhiTestFunction(TestContext &Context, const rcc::TargetDescription &Target, std::string Name,
+ std::uint64_t ID, PhiTestShape Shape) {
+ auto Function = createFunction(Context, std::move(Name), ID);
+ if (!Function)
+ return nullptr;
+ rcc::MachineBasicBlock *Left = createBlock(Context, *Function);
+ rcc::MachineBasicBlock *Right = createBlock(Context, *Function);
+ rcc::MachineBasicBlock *Merge = createBlock(Context, *Function);
+ rcc::MachineBasicBlock *Other = createBlock(Context, *Function);
+ if (Left == nullptr || Right == nullptr || Merge == nullptr || Other == nullptr)
+ return nullptr;
+
+ auto CFG = Function->cfgUpdater();
+ if (!CFG.addSuccessor(*Left, *Merge, rcc::BranchProbability::one()) ||
+ !CFG.addSuccessor(*Right, *Merge, rcc::BranchProbability::one())) {
+ Context.expect(false, "PHI verifier test CFG must be constructed");
+ return nullptr;
+ }
+
+ auto Type = rcc::LLT::makeInteger(64);
+ auto Destination = Type ? Function->registerInfo().createVirtualRegister(*Type)
+ : rcc::Expected<rcc::Register>{std::unexpected(Type.error())};
+ auto LeftValue = Type ? Function->registerInfo().createVirtualRegister(*Type)
+ : rcc::Expected<rcc::Register>{std::unexpected(Type.error())};
+ auto RightValue = Type ? Function->registerInfo().createVirtualRegister(*Type)
+ : rcc::Expected<rcc::Register>{std::unexpected(Type.error())};
+ if (!Destination || !LeftValue || !RightValue) {
+ Context.expect(false, "PHI verifier test registers must be created");
+ return nullptr;
+ }
+
+ rcc::MachineIRBuilder Builder(*Function, Target);
+ if (!Builder.setInsertPoint(*Merge)) {
+ Context.expect(false, "PHI verifier insertion point must be valid");
+ return nullptr;
+ }
+ if (Shape == PhiTestShape::AfterInstruction &&
+ buildNoOperand(Context, Builder, NopOpcode) == nullptr)
+ return nullptr;
+
+ auto Phi = Builder.buildInstr(rcc::Opcode::fromValue(PhiOpcode));
+ if (!Phi || !Phi->addDef(*Destination) || !Phi->addUse(*LeftValue) ||
+ !Phi->addBasicBlock(*Left)) {
+ Context.expect(false, "PHI verifier instruction prefix must build");
+ return nullptr;
+ }
+ if (Shape == PhiTestShape::DuplicatePredecessor) {
+ if (!Phi->addUse(*RightValue) || !Phi->addBasicBlock(*Left))
+ return nullptr;
+ } else if (Shape == PhiTestShape::NonPredecessor) {
+ if (!Phi->addUse(*RightValue) || !Phi->addBasicBlock(*Other))
+ return nullptr;
+ } else if (Shape != PhiTestShape::MissingPredecessor) {
+ if (!Phi->addUse(*RightValue) || !Phi->addBasicBlock(*Right))
+ return nullptr;
+ }
+ if (!Phi->build()) {
+ Context.expect(false, "PHI verifier test instruction must publish");
+ return nullptr;
+ }
+ return Function;
+}
+
+void testPHIStructure(TestContext &Context) {
+ auto Target = createTarget();
+ if (!Target)
+ return;
+ auto Valid = createPhiTestFunction(Context, *Target, "valid_phi", 60, PhiTestShape::Valid);
+ auto Missing =
+ createPhiTestFunction(Context, *Target, "missing_phi", 61, PhiTestShape::MissingPredecessor);
+ auto Duplicate = createPhiTestFunction(Context, *Target, "duplicate_phi", 62,
+ PhiTestShape::DuplicatePredecessor);
+ auto NonPredecessor =
+ createPhiTestFunction(Context, *Target, "foreign_phi", 63, PhiTestShape::NonPredecessor);
+ auto AfterInstruction =
+ createPhiTestFunction(Context, *Target, "late_phi", 64, PhiTestShape::AfterInstruction);
+ Context.expect(Valid && rcc::MachineVerifier::verify(*Valid, *Target),
+ "PHI with one incoming value per predecessor must verify");
+ Context.expect(Missing && !rcc::MachineVerifier::verify(*Missing, *Target),
+ "PHI missing a predecessor must fail verification");
+ Context.expect(Duplicate && !rcc::MachineVerifier::verify(*Duplicate, *Target),
+ "PHI with duplicate incoming blocks must fail verification");
+ Context.expect(NonPredecessor && !rcc::MachineVerifier::verify(*NonPredecessor, *Target),
+ "PHI naming a non-predecessor must fail verification");
+ Context.expect(AfterInstruction && !rcc::MachineVerifier::verify(*AfterInstruction, *Target),
+ "PHI after a code instruction must fail verification");
+}
+
void testPropertyFailures(TestContext &Context) {
auto Target = createTarget();
if (!Target)
@@ -428,7 +533,8 @@ void testSelectedStateAndPseudoDeadline(TestContext &Context) {
"tied-state instruction must build");
for (const rcc::MachineFunctionProperty Property :
{rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
- rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::TiedOpsRewritten}) {
+ rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::NoPHIs,
+ rcc::MachineFunctionProperty::TiedOpsRewritten}) {
Tied->properties().set(Property);
}
Context.expect(!rcc::MachineVerifier::verify(*Tied, *Target),
@@ -470,6 +576,20 @@ void testSelectedStateAndPseudoDeadline(TestContext &Context) {
Context.expect(!rcc::MachineVerifier::verify(*Dependency, *Target),
"FrameFinalized must require NoVRegs and NoFrameIndices");
}
+
+ auto SSAExitDependency = createFunction(Context, "ssa_exit_property_dependency", 65);
+ if (SSAExitDependency) {
+ for (const rcc::MachineFunctionProperty Property :
+ {rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
+ rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::TiedOpsRewritten}) {
+ SSAExitDependency->properties().set(Property);
+ }
+ Context.expect(!rcc::MachineVerifier::verify(*SSAExitDependency, *Target),
+ "TiedOpsRewritten must require NoPHIs");
+ SSAExitDependency->properties().set(rcc::MachineFunctionProperty::NoPHIs);
+ Context.expect(rcc::MachineVerifier::verify(*SSAExitDependency, *Target).has_value(),
+ "TiedOpsRewritten dependency must be satisfied by NoPHIs");
+ }
}
void testFrameStateFailures(TestContext &Context) {
@@ -523,8 +643,7 @@ void testTableReferenceFailures(TestContext &Context) {
rcc::MachineConstantPoolEntryDesc ConstantDescription;
auto Integer = rcc::IntegerImmediate::fromUnsigned(32, 0x01010101U);
- ConstantDescription.Value =
- std::move(*rcc::GenericConstantData::integer(std::move(*Integer)));
+ ConstantDescription.Value = std::move(*rcc::GenericConstantData::integer(std::move(*Integer)));
ConstantDescription.Size = 4;
ConstantDescription.Align = *rcc::Alignment::create(4);
auto ConstantIndex = ConstantFunction->constantPool().addEntry(std::move(ConstantDescription));
@@ -609,6 +728,7 @@ int main() {
TestContext Context;
testValidFunctionAndModes(Context);
testReachableStructuralFailures(Context);
+ testPHIStructure(Context);
testPropertyFailures(Context);
testSelectedStateAndPseudoDeadline(Context);
testFrameStateFailures(Context);
diff --git a/backend/unittests/Target/CMakeLists.txt b/backend/unittests/Target/CMakeLists.txt
index 98c4426..0bffb47 100644
--- a/backend/unittests/Target/CMakeLists.txt
+++ b/backend/unittests/Target/CMakeLists.txt
@@ -33,11 +33,17 @@ rcc_backend_configure_target(RCCBackendRISCVCodeGenTests)
target_link_libraries(RCCBackendRISCVCodeGenTests PRIVATE RCCBackend::RISCV RCCBackend::CodeGen)
add_test(NAME RCCBackendRISCVCodeGenTests COMMAND RCCBackendRISCVCodeGenTests)
+add_executable(RCCBackendRISCVSSAExitTests RISCVSSAExitTest.cpp)
+rcc_backend_configure_target(RCCBackendRISCVSSAExitTests)
+target_link_libraries(RCCBackendRISCVSSAExitTests PRIVATE RCCBackend::RISCV RCCBackend::CodeGen)
+add_test(NAME RCCBackendRISCVSSAExitTests COMMAND RCCBackendRISCVSSAExitTests)
+
rcc_backend_register_format_files(
"${CMAKE_CURRENT_SOURCE_DIR}/DescriptionGeneratorTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLoweringTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/RISCVTargetTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGenTest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/RISCVSSAExitTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.h"
)
@@ -46,5 +52,6 @@ rcc_backend_register_tidy_files(
"${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLoweringTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/RISCVTargetTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGenTest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/RISCVSSAExitTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.cpp"
)
diff --git a/backend/unittests/Target/RISCVSSAExitTest.cpp b/backend/unittests/Target/RISCVSSAExitTest.cpp
new file mode 100644
index 0000000..1440855
--- /dev/null
+++ b/backend/unittests/Target/RISCVSSAExitTest.cpp
@@ -0,0 +1,346 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/MachineSSAExit.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/Target/RISCV/RISCVCodeGen.h"
+#include "rcc/Target/RISCV/RISCVTarget.h"
+
+#include <algorithm>
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace {
+
+class TestContext final {
+public:
+ void expect(bool Condition, std::string_view Message) {
+ if (Condition)
+ return;
+ std::cerr << Message << '\n';
+ ++Failures;
+ }
+
+ [[nodiscard]] int result() const noexcept {
+ return Failures == 0 ? 0 : 1;
+ }
+
+private:
+ int Failures = 0;
+};
+
+[[nodiscard]] rcc::Opcode targetOpcode(rcc::riscv::InstructionOpcode Opcode) {
+ return rcc::Opcode::fromValue(static_cast<std::uint32_t>(Opcode));
+}
+
+[[nodiscard]] rcc::RegisterBankID bank(rcc::riscv::RegisterBank Bank) {
+ return rcc::RegisterBankID::fromValue(static_cast<std::uint32_t>(Bank));
+}
+
+[[nodiscard]] rcc::RegisterClassID regClass(rcc::riscv::RegisterClass Class) {
+ return rcc::RegisterClassID::fromValue(static_cast<std::uint32_t>(Class));
+}
+
+[[nodiscard]] rcc::Expected<rcc::Register> createVReg(rcc::MachineFunction &Function, rcc::LLT Type,
+ rcc::riscv::RegisterBank Bank,
+ rcc::riscv::RegisterClass Class) {
+ auto Reg = Function.registerInfo().createVirtualRegister(Type);
+ if (!Reg)
+ return std::unexpected(Reg.error());
+ auto BankResult = Function.registerInfo().setRegisterBank(*Reg, bank(Bank));
+ if (!BankResult)
+ return std::unexpected(BankResult.error());
+ auto ClassResult = Function.registerInfo().setRegisterClass(*Reg, regClass(Class));
+ if (!ClassResult)
+ return std::unexpected(ClassResult.error());
+ return *Reg;
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineBasicBlock *> appendBlock(rcc::MachineFunction &Function) {
+ auto Block = Function.createBasicBlock();
+ if (!Block)
+ return std::unexpected(Block.error());
+ auto Appended = Function.appendBlock(**Block);
+ if (!Appended)
+ return std::unexpected(Appended.error());
+ return *Block;
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildAddImmediate(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+ rcc::MachineBasicBlock &Block, rcc::Register Destination, rcc::Register Source,
+ std::int64_t Immediate) {
+ rcc::MachineIRBuilder Builder(Function, Target);
+ auto Point = Builder.setInsertPoint(Block);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Pending = Builder.buildInstr(targetOpcode(rcc::riscv::InstructionOpcode::ADDI));
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ auto Def = Pending->addDef(Destination);
+ if (!Def)
+ return std::unexpected(Def.error());
+ auto Use = Pending->addUse(Source);
+ if (!Use)
+ return std::unexpected(Use.error());
+ auto Value = Pending->addImmediate(Immediate);
+ if (!Value)
+ return std::unexpected(Value.error());
+ return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildBranchEqual(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+ rcc::MachineBasicBlock &Block, rcc::Register Left, rcc::Register Right,
+ rcc::MachineBasicBlock &Destination) {
+ rcc::MachineIRBuilder Builder(Function, Target);
+ auto Point = Builder.setInsertPoint(Block);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Pending = Builder.buildInstr(targetOpcode(rcc::riscv::InstructionOpcode::BEQ));
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ auto LeftUse = Pending->addUse(Left);
+ if (!LeftUse)
+ return std::unexpected(LeftUse.error());
+ auto RightUse = Pending->addUse(Right);
+ if (!RightUse)
+ return std::unexpected(RightUse.error());
+ auto TargetOperand = Pending->addBasicBlock(Destination);
+ if (!TargetOperand)
+ return std::unexpected(TargetOperand.error());
+ return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+ rcc::MachineBasicBlock &Block, rcc::Register Destination,
+ const std::array<std::pair<rcc::Register, rcc::MachineBasicBlock *>, 2> &Incoming) {
+ rcc::MachineIRBuilder Builder(Function, Target);
+ auto Point = Builder.setInsertPoint(Block);
+ if (!Point)
+ return std::unexpected(Point.error());
+ auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI));
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ auto Def = Pending->addDef(Destination);
+ if (!Def)
+ return std::unexpected(Def.error());
+ for (const auto &[Value, Predecessor] : Incoming) {
+ auto Use = Pending->addUse(Value);
+ if (!Use)
+ return std::unexpected(Use.error());
+ auto IncomingBlock = Pending->addBasicBlock(*Predecessor);
+ if (!IncomingBlock)
+ return std::unexpected(IncomingBlock.error());
+ }
+ return Pending->build();
+}
+
+[[nodiscard]] const rcc::BasicBlockOperand *blockOperand(const rcc::MachineInstr &Instruction,
+ std::size_t Index) {
+ const rcc::MachineOperand *Operand = Instruction.operandAt(Index);
+ return Operand == nullptr ? nullptr : Operand->getIf<rcc::BasicBlockOperand>();
+}
+
+[[nodiscard]] std::vector<rcc::MachineInstr *> linkedInstructions(rcc::MachineBasicBlock &Block) {
+ std::vector<rcc::MachineInstr *> Result;
+ for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+ Instruction = Instruction->next()) {
+ Result.push_back(Instruction);
+ }
+ return Result;
+}
+
+void setSelectedSSAProperties(rcc::MachineFunction &Function) {
+ for (rcc::MachineFunctionProperty Property :
+ {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness,
+ rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
+ rcc::MachineFunctionProperty::Selected}) {
+ Function.properties().set(Property);
+ }
+}
+
+void testBehaviorAndCopyLegality(TestContext &Context, const rcc::TargetDescription &Target) {
+ auto Function = rcc::MachineFunction::create("riscv_ssa_behavior",
+ rcc::MachineFunctionStableID::fromValue(1));
+ if (!Function)
+ return;
+ auto First = appendBlock(**Function);
+ auto Second = appendBlock(**Function);
+ auto Third = appendBlock(**Function);
+ if (!First || !Second || !Third)
+ return;
+ auto CFG = (*Function)->cfgUpdater();
+ if (!CFG.addSuccessor(**First, **Second, rcc::BranchProbability::one()))
+ return;
+
+ auto Fallthrough = rcc::riscv::ssaInfo().isFallthroughEdge(**First, **Second, **Function, Target);
+ Context.expect(Fallthrough && *Fallthrough,
+ "RV64GC SSA behavior must recognize an empty layout fallthrough edge");
+ auto Inserted =
+ rcc::riscv::ssaInfo().insertUnconditionalBranch(**First, **Second, **Function, Target);
+ Context.expect(Inserted.has_value(), "RV64GC SSA behavior must insert an unconditional branch");
+ if (!Inserted)
+ return;
+ rcc::MachineInstr *Jump = (*First)->lastInstruction();
+ const auto X0 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X0);
+ Context.expect(Jump != nullptr &&
+ Jump->opcode() == targetOpcode(rcc::riscv::InstructionOpcode::JAL) &&
+ Jump->operandAt(0)->registerValue() == rcc::Register::fromPhysical(*X0) &&
+ blockOperand(*Jump, 1) != nullptr && blockOperand(*Jump, 1)->Block == *Second,
+ "RV64GC unconditional branches must use JAL with x0 as the link destination");
+ auto NoFallthrough =
+ rcc::riscv::ssaInfo().isFallthroughEdge(**First, **Second, **Function, Target);
+ Context.expect(NoFallthrough && !*NoFallthrough, "JAL must terminate RV64GC layout fallthrough");
+ auto Rewritten =
+ rcc::riscv::ssaInfo().rewriteBranchTarget(**First, **Second, **Third, **Function, Target);
+ Context.expect(Rewritten && *Rewritten && blockOperand(*Jump, 1)->Block == *Third,
+ "RV64GC branch target rewriting must update direct JAL operands");
+
+ auto I64 = rcc::LLT::makeInteger(64);
+ auto F64 = rcc::LLT::makeFloat(rcc::FloatSemantics::IEEEDouble);
+ auto F32 = rcc::LLT::makeFloat(rcc::FloatSemantics::IEEESingle);
+ if (!I64 || !F64 || !F32)
+ return;
+ auto GPR =
+ createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR);
+ auto OtherGPR =
+ createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR);
+ auto FPR64 =
+ createVReg(**Function, *F64, rcc::riscv::RegisterBank::FPR, rcc::riscv::RegisterClass::FPR64);
+ auto FPR32 =
+ createVReg(**Function, *F32, rcc::riscv::RegisterBank::FPR, rcc::riscv::RegisterClass::FPR32);
+ auto Unclassified = (*Function)->registerInfo().createVirtualRegister(*I64);
+ if (!GPR || !OtherGPR || !FPR64 || !FPR32 || !Unclassified)
+ return;
+
+ Context.expect(
+ rcc::riscv::ssaInfo().validateCopy(*GPR, {}, *OtherGPR, {}, **Function, Target).has_value(),
+ "RV64GC must allow a compatible GPR COPY");
+ Context.expect(
+ rcc::riscv::ssaInfo().validateCopy(*GPR, {}, *FPR64, {}, **Function, Target).has_value(),
+ "RV64GC must allow supported 64-bit GPR/FPR bit moves");
+ Context.expect(!rcc::riscv::ssaInfo().validateCopy(*FPR64, {}, *FPR32, {}, **Function, Target),
+ "RV64GC must reject incompatible same-bank COPY widths");
+ Context.expect(!rcc::riscv::ssaInfo().validateCopy(*GPR, rcc::SubRegIndex::fromValue(1),
+ *OtherGPR, {}, **Function, Target),
+ "RV64GC must reject unmodeled subregister COPYs");
+ Context.expect(
+ !rcc::riscv::ssaInfo().validateCopy(*GPR, {}, *Unclassified, {}, **Function, Target),
+ "RV64GC must reject COPYs involving an unconstrained virtual register");
+}
+
+void testRV64GCCriticalEdge(TestContext &Context, const rcc::TargetDescription &Target) {
+ auto Function = rcc::MachineFunction::create("riscv_ssa_critical_edge",
+ rcc::MachineFunctionStableID::fromValue(2));
+ if (!Function)
+ return;
+ auto From = appendBlock(**Function);
+ auto Side = appendBlock(**Function);
+ auto Other = appendBlock(**Function);
+ auto Merge = appendBlock(**Function);
+ if (!From || !Side || !Other || !Merge)
+ return;
+ auto I64 = rcc::LLT::makeInteger(64);
+ auto X0 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X0);
+ if (!I64 || !X0)
+ return;
+ auto FromValue =
+ createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR);
+ auto OtherValue =
+ createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR);
+ auto Destination =
+ createVReg(**Function, *I64, rcc::riscv::RegisterBank::GPR, rcc::riscv::RegisterClass::GPR);
+ if (!FromValue || !OtherValue || !Destination)
+ return;
+
+ auto Half = rcc::BranchProbability::fromFraction(1, 2);
+ auto CFG = (*Function)->cfgUpdater();
+ Context.expect(Half && CFG.addSuccessor(**From, **Side, *Half) &&
+ CFG.addSuccessor(**From, **Merge, *Half) &&
+ CFG.addSuccessor(**Other, **Merge, rcc::BranchProbability::one()),
+ "RV64GC critical-edge CFG must be connected");
+ const rcc::Register Zero = rcc::Register::fromPhysical(*X0);
+ Context.expect(buildAddImmediate(**Function, Target, **From, *FromValue, Zero, 1) &&
+ buildBranchEqual(**Function, Target, **From, Zero, Zero, **Merge) &&
+ buildAddImmediate(**Function, Target, **Other, *OtherValue, Zero, 2),
+ "RV64GC critical-edge instructions must be built");
+ const std::array Incoming{
+ std::pair<rcc::Register, rcc::MachineBasicBlock *>{*FromValue, *From},
+ std::pair<rcc::Register, rcc::MachineBasicBlock *>{*OtherValue, *Other}};
+ Context.expect(buildPhi(**Function, Target, **Merge, *Destination, Incoming).has_value(),
+ "RV64GC critical-edge PHI must be built");
+ setSelectedSSAProperties(**Function);
+
+ rcc::MachinePassManager Pipeline;
+ Context.expect(Pipeline.addPass(std::make_unique<rcc::PHIEliminationPass>(rcc::riscv::ssaInfo()))
+ .has_value(),
+ "RV64GC PHI-elimination pass must be registered");
+ rcc::MachineAnalysisManager Analyses;
+ auto Run = Pipeline.run(**Function, Target, Analyses);
+ Context.expect(Run.has_value(), "RV64GC critical-edge PHI elimination must succeed");
+ if (!Run)
+ return;
+
+ rcc::MachineBasicBlock *Edge = (*Merge)->previous();
+ Context.expect(Edge != nullptr && Edge != *Other && Edge->previous() == *Other,
+ "RV64GC critical edge must receive a dedicated layout block");
+ if (Edge == nullptr || Edge == *Other)
+ return;
+ rcc::MachineInstr *Conditional = (*From)->lastInstruction();
+ Context.expect(Conditional != nullptr &&
+ Conditional->opcode() == targetOpcode(rcc::riscv::InstructionOpcode::BEQ) &&
+ blockOperand(*Conditional, 2) != nullptr &&
+ blockOperand(*Conditional, 2)->Block == Edge,
+ "RV64GC BEQ must be redirected to the critical-edge block");
+
+ const auto OtherInstructions = linkedInstructions(**Other);
+ const auto EdgeInstructions = linkedInstructions(*Edge);
+ Context.expect(OtherInstructions.size() == 3 &&
+ OtherInstructions[1]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+ OtherInstructions[2]->opcode() ==
+ targetOpcode(rcc::riscv::InstructionOpcode::JAL) &&
+ blockOperand(*OtherInstructions[2], 1)->Block == *Merge,
+ "RV64GC must materialize an unrelated fallthrough before edge-block insertion");
+ Context.expect(EdgeInstructions.size() == 2 &&
+ EdgeInstructions[0]->opcode() == rcc::opcode(rcc::GenericOpcode::COPY) &&
+ EdgeInstructions[1]->opcode() ==
+ targetOpcode(rcc::riscv::InstructionOpcode::JAL) &&
+ EdgeInstructions[1]->operandAt(0)->registerValue() == Zero &&
+ blockOperand(*EdgeInstructions[1], 1)->Block == *Merge,
+ "RV64GC edge block must transfer the PHI value and jump to the merge");
+ Context.expect((*Function)->properties().has(rcc::MachineFunctionProperty::NoPHIs) &&
+ !(*Function)->properties().has(rcc::MachineFunctionProperty::IsSSA),
+ "RV64GC PHI elimination must publish SSA-exit properties");
+ Context.expect(rcc::MachineVerifier::verify(**Function, Target).has_value(),
+ "RV64GC SSA-exit result must pass MachineVerifier");
+}
+
+} // namespace
+
+int main() {
+ TestContext Context;
+ auto Target = rcc::riscv::createTargetDescription();
+ Context.expect(Target.has_value(), "RV64GC target must be created for SSA-exit tests");
+ if (!Target)
+ return Context.result();
+ testBehaviorAndCopyLegality(Context, *Target);
+ testRV64GCCriticalEdge(Context, *Target);
+ return Context.result();
+}
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 09:36:28 +0000