aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--backend/include/rcc/CodeGen/MachineRegisterInfo.h4
-rw-r--r--backend/include/rcc/CodeGen/MachineVerifier.h36
-rw-r--r--backend/lib/CodeGen/CMakeLists.txt4
-rw-r--r--backend/lib/CodeGen/MachineRegisterInfo.cpp22
-rw-r--r--backend/lib/CodeGen/MachineVerifier.cpp504
-rw-r--r--backend/unittests/CodeGen/CMakeLists.txt15
-rw-r--r--backend/unittests/CodeGen/MachineVerifierTest.cpp459
7 files changed, 1044 insertions, 0 deletions
diff --git a/backend/include/rcc/CodeGen/MachineRegisterInfo.h b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
index 495853a..da0f530 100644
--- a/backend/include/rcc/CodeGen/MachineRegisterInfo.h
+++ b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
@@ -108,6 +108,9 @@ public:
[[nodiscard]] Expected<void> eraseVirtualRegister(Register Reg);
[[nodiscard]] bool isKnownVirtualRegister(Register Reg) const noexcept;
+ [[nodiscard]] std::span<const VirtualRegisterInfo> virtualRegisters() const noexcept {
+ return VirtualRegisters;
+ }
[[nodiscard]] Expected<std::reference_wrapper<VirtualRegisterInfo>>
virtualRegisterInfo(Register Reg);
[[nodiscard]] Expected<std::reference_wrapper<const VirtualRegisterInfo>>
@@ -146,6 +149,7 @@ public:
[[nodiscard]] Expected<std::size_t> replaceRegWith(Register OldReg, Register NewReg);
[[nodiscard]] Expected<void> verifyDefUseChains() const;
+ [[nodiscard]] bool isLinkedOperand(const MachineOperand &Operand) const noexcept;
private:
struct RegOperandListHead final {
diff --git a/backend/include/rcc/CodeGen/MachineVerifier.h b/backend/include/rcc/CodeGen/MachineVerifier.h
new file mode 100644
index 0000000..b1035a2
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineVerifier.h
@@ -0,0 +1,36 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_MACHINEVERIFIER_H
+#define RCC_CODEGEN_MACHINEVERIFIER_H
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+#include <optional>
+
+namespace rcc {
+
+class MachineFunction;
+
+enum class MachineVerifierMode : std::uint8_t {
+ Generic,
+ PreLegalizer,
+};
+
+struct MachineVerifierOptions final {
+ MachineVerifierMode Mode = MachineVerifierMode::Generic;
+ std::optional<PipelineStage> Stage;
+ bool VerifyProperties = true;
+};
+
+class MachineVerifier final {
+public:
+ [[nodiscard]] static Expected<void> verify(const MachineFunction &Function,
+ const InstructionSet &Instructions,
+ MachineVerifierOptions Options = {});
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_MACHINEVERIFIER_H
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index deaacb1..273ef9c 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -13,6 +13,7 @@ set(
MachineMemOperand.cpp
MachineOperand.cpp
MachineRegisterInfo.cpp
+ MachineVerifier.cpp
MachineFunctionProperties.cpp
Register.cpp
RegisterMask.cpp
@@ -30,6 +31,7 @@ set(
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOperand.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.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/Register.h"
"${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h"
@@ -76,6 +78,7 @@ rcc_backend_register_format_files(
"${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
@@ -93,6 +96,7 @@ rcc_backend_register_tidy_files(
"${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
diff --git a/backend/lib/CodeGen/MachineRegisterInfo.cpp b/backend/lib/CodeGen/MachineRegisterInfo.cpp
index cc0955e..c31b38b 100644
--- a/backend/lib/CodeGen/MachineRegisterInfo.cpp
+++ b/backend/lib/CodeGen/MachineRegisterInfo.cpp
@@ -2,6 +2,8 @@
#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
#include "rcc/CodeGen/MachineOperand.h"
#include <algorithm>
@@ -312,6 +314,16 @@ Expected<void> MachineRegisterInfo::verifyDefUseChains() const {
std::unordered_set<const MachineOperand *> SeenOperands;
for (const auto &[Reg, HeadStorage] : DefUseHeads) {
+ if (!HeadStorage) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "register def-use table contains null head storage");
+ }
+ if (HeadStorage->Head == nullptr)
+ continue;
+ if (Reg.isNoRegister() || (Reg.isVirtual() && !isKnownVirtualRegister(Reg))) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "register def-use chain is keyed by an invalid register");
+ }
MachineOperand *const *ExpectedPreviousLink = &HeadStorage->Head;
for (MachineOperand *Operand = HeadStorage->Head; Operand != nullptr;
Operand = Operand->NextRegOperand) {
@@ -327,6 +339,12 @@ Expected<void> MachineRegisterInfo::verifyDefUseChains() const {
return makeUnexpected(ErrorCode::VerificationError,
"register def-use chain back-link is corrupt");
}
+ if (Operand->Parent == nullptr || !Operand->Parent->isLinked() ||
+ &Operand->Parent->function().registerInfo() != this) {
+ return makeUnexpected(
+ ErrorCode::VerificationError,
+ "register def-use chain contains an operand outside its function layout");
+ }
ExpectedPreviousLink = &Operand->NextRegOperand;
}
}
@@ -334,6 +352,10 @@ Expected<void> MachineRegisterInfo::verifyDefUseChains() const {
return {};
}
+bool MachineRegisterInfo::isLinkedOperand(const MachineOperand &Operand) const noexcept {
+ return Operand.LinkedRegInfo == this && Operand.PreviousRegLink != nullptr;
+}
+
MachineOperand *MachineRegisterInfo::headFor(Register Reg) const noexcept {
const auto Position = DefUseHeads.find(Reg);
if (Position == DefUseHeads.end())
diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp
new file mode 100644
index 0000000..450f8e3
--- /dev/null
+++ b/backend/lib/CodeGen/MachineVerifier.cpp
@@ -0,0 +1,504 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineVerifier.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionProperties.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <ranges>
+#include <string>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+
+namespace rcc {
+namespace {
+
+class FunctionVerifier final {
+public:
+ FunctionVerifier(const MachineFunction &Function, const InstructionSet &Instructions,
+ MachineVerifierOptions Options) noexcept
+ : Function(Function), Instructions(Instructions), Options(Options) {}
+
+ [[nodiscard]] Expected<void> run() {
+ if (Function.name().empty() || !Function.stableID().isValid())
+ return fail("function identity is invalid");
+
+ auto CatalogResult = catalogArenaObjects();
+ if (!CatalogResult)
+ return CatalogResult;
+ auto LayoutResult = verifyBlockLayout();
+ if (!LayoutResult)
+ return LayoutResult;
+ auto CFGResult = verifyCFG();
+ if (!CFGResult)
+ return CFGResult;
+ auto RegisterResult = verifyRegisterInfo();
+ if (!RegisterResult)
+ return RegisterResult;
+ auto DefUseResult = Function.registerInfo().verifyDefUseChains();
+ if (!DefUseResult)
+ return failWith("register info", DefUseResult.error());
+ if (Options.VerifyProperties) {
+ auto PropertyResult = verifyProperties();
+ if (!PropertyResult)
+ return PropertyResult;
+ }
+ return {};
+ }
+
+private:
+ [[nodiscard]] Expected<void> fail(std::string Message) const {
+ return makeUnexpected(ErrorCode::VerificationError, "machine function '" +
+ std::string(Function.name()) +
+ "': " + std::move(Message));
+ }
+
+ [[nodiscard]] Expected<void> failWith(std::string_view Context, const Error &Nested) const {
+ return fail(std::string(Context) + ": " + std::string(Nested.message()));
+ }
+
+ [[nodiscard]] static bool hasMatchingStorage(const MachineOperand &Operand) noexcept {
+ switch (Operand.kind()) {
+ case MachineOperand::Kind::Register:
+ return Operand.getIf<Register>() != nullptr;
+ case MachineOperand::Kind::Immediate:
+ return Operand.getIf<std::int64_t>() != nullptr;
+ case MachineOperand::Kind::FloatingImmediate:
+ return Operand.getIf<FloatingImmediateOperand>() != nullptr;
+ case MachineOperand::Kind::BasicBlock:
+ return Operand.getIf<BasicBlockOperand>() != nullptr;
+ case MachineOperand::Kind::FrameIndex:
+ return Operand.getIf<FrameIndexOperand>() != nullptr;
+ case MachineOperand::Kind::ConstantPoolIndex:
+ return Operand.getIf<ConstantPoolOperand>() != nullptr;
+ case MachineOperand::Kind::JumpTableIndex:
+ return Operand.getIf<JumpTableOperand>() != nullptr;
+ case MachineOperand::Kind::GlobalSymbol:
+ return Operand.getIf<GlobalSymbolOperand>() != nullptr;
+ case MachineOperand::Kind::ExternalSymbol:
+ return Operand.getIf<ExternalSymbolOperand>() != nullptr;
+ case MachineOperand::Kind::BlockAddress:
+ return Operand.getIf<BlockAddressOperand>() != nullptr;
+ case MachineOperand::Kind::RegisterMask:
+ return Operand.getIf<RegisterMaskOperand>() != nullptr;
+ case MachineOperand::Kind::Metadata:
+ return Operand.getIf<MetadataOperand>() != nullptr;
+ case MachineOperand::Kind::TargetIndex:
+ return Operand.getIf<TargetIndexOperand>() != nullptr;
+ case MachineOperand::Kind::MCSymbol:
+ return Operand.getIf<MCSymbolOperand>() != nullptr;
+ case MachineOperand::Kind::Count:
+ return false;
+ }
+ return false;
+ }
+
+ [[nodiscard]] Expected<void> catalogArenaObjects() {
+ std::unordered_set<MachineBlockStableID> BlockIDs;
+ for (const MachineBasicBlock *Block : Function.allBlocks()) {
+ if (Block == nullptr || !RegisteredBlocks.insert(Block).second)
+ return fail("arena block registry contains a null or duplicate pointer");
+ if (&Block->function() != &Function)
+ return fail("arena block registry contains a foreign block");
+ if (!Block->stableID().isValid() || !BlockIDs.insert(Block->stableID()).second) {
+ return fail("arena block registry contains an invalid or duplicate StableID");
+ }
+ }
+
+ std::unordered_set<MachineInstrStableID> InstructionIDs;
+ for (const MachineInstr *Instruction : Function.allInstructions()) {
+ if (Instruction == nullptr || !RegisteredInstructions.insert(Instruction).second) {
+ return fail("arena instruction registry contains a null or duplicate pointer");
+ }
+ if (&Instruction->function() != &Function)
+ return fail("arena instruction registry contains a foreign instruction");
+ if (!Instruction->stableID().isValid() ||
+ !InstructionIDs.insert(Instruction->stableID()).second) {
+ return fail("arena instruction registry contains an invalid or duplicate StableID");
+ }
+ }
+
+ for (const MachineMemOperand *MemOperand : Function.allMemOperands()) {
+ if (MemOperand == nullptr || !RegisteredMemOperands.insert(MemOperand).second) {
+ return fail("arena MMO registry contains a null or duplicate pointer");
+ }
+ }
+ return {};
+ }
+
+ [[nodiscard]] Expected<void> verifyBlockLayout() {
+ const MachineBasicBlock *Previous = nullptr;
+ const MachineBasicBlock *Block = Function.firstBlock();
+ std::uint32_t LayoutIndex = 0;
+ while (Block != nullptr) {
+ if (!RegisteredBlocks.contains(Block))
+ return fail("block layout references an unregistered block");
+ if (!LinkedBlocks.insert(Block).second)
+ return fail("block layout contains a cycle or duplicate block");
+ if (!Block->isLinked() || Block->previous() != Previous)
+ return fail("block layout ownership or previous link is inconsistent");
+ if (Block->denseNumber() != LayoutIndex || Block->layoutIndex() != LayoutIndex) {
+ return fail("block dense number or layout index is stale");
+ }
+
+ auto InstructionResult = verifyInstructionLayout(*Block);
+ if (!InstructionResult)
+ return InstructionResult;
+ Previous = Block;
+ Block = Block->next();
+ ++LayoutIndex;
+ }
+
+ if (Previous != Function.lastBlock())
+ return fail("function last-block pointer is inconsistent");
+ if ((Function.firstBlock() == nullptr) != (Function.lastBlock() == nullptr)) {
+ return fail("function has only one of its first/last block pointers");
+ }
+
+ for (const MachineBasicBlock *Registered : RegisteredBlocks) {
+ if (LinkedBlocks.contains(Registered)) {
+ if (!Registered->isLinked())
+ return fail("reachable block is not marked linked");
+ continue;
+ }
+ if (Registered->isLinked())
+ return fail("unreachable arena block is marked linked");
+ if (Registered->previous() != nullptr || Registered->next() != nullptr ||
+ Registered->firstInstruction() != nullptr || Registered->lastInstruction() != nullptr ||
+ !Registered->predecessors().empty() || !Registered->successors().empty() ||
+ Registered->denseNumber() || Registered->layoutIndex()) {
+ return fail("detached block retains layout, instruction, or CFG state");
+ }
+ }
+
+ for (const MachineInstr *Instruction : RegisteredInstructions) {
+ auto LocalResult = verifyInstructionLocalState(*Instruction);
+ if (!LocalResult)
+ return LocalResult;
+ if (Instruction->parent() != nullptr) {
+ if (!LinkedInstructions.contains(Instruction))
+ return fail("instruction has a parent but is absent from block layout");
+ } else {
+ if (Instruction->previous() != nullptr || Instruction->next() != nullptr) {
+ return fail("detached instruction retains layout links");
+ }
+ for (const MachineOperand &Operand : Instruction->operands()) {
+ if (Function.registerInfo().isLinkedOperand(Operand))
+ return fail("detached instruction operand remains in a def-use chain");
+ }
+ }
+ }
+ return {};
+ }
+
+ [[nodiscard]] Expected<void> verifyInstructionLayout(const MachineBasicBlock &Block) {
+ const MachineInstr *Previous = nullptr;
+ const MachineInstr *Instruction = Block.firstInstruction();
+ while (Instruction != nullptr) {
+ if (!RegisteredInstructions.contains(Instruction))
+ return fail("block layout references an unregistered instruction");
+ if (!LinkedInstructions.insert(Instruction).second)
+ return fail("instruction layout contains a cycle or duplicate instruction");
+ if (Instruction->parent() != &Block || Instruction->previous() != Previous) {
+ return fail("instruction parent or previous link is inconsistent");
+ }
+
+ auto LiveResult = verifyLiveInstruction(*Instruction);
+ if (!LiveResult)
+ return LiveResult;
+ Previous = Instruction;
+ Instruction = Instruction->next();
+ }
+ if (Previous != Block.lastInstruction())
+ return fail("block last-instruction pointer is inconsistent");
+ if ((Block.firstInstruction() == nullptr) != (Block.lastInstruction() == nullptr)) {
+ return fail("block has only one of its first/last instruction pointers");
+ }
+ return {};
+ }
+
+ [[nodiscard]] Expected<void> verifyInstructionLocalState(const MachineInstr &Instruction) {
+ if (Instruction.sourceLocation() && !Instruction.sourceLocation()->isValid()) {
+ return fail("instruction has an invalid source location");
+ }
+ if (Instruction.origin() && Instruction.origin()->value() == 0)
+ return fail("instruction has an invalid origin ID");
+
+ for (const MachineOperand &Operand : Instruction.operands()) {
+ if (Operand.parent() != &Instruction || !hasMatchingStorage(Operand))
+ return fail("instruction operand parent or tagged storage is inconsistent");
+ if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); Mask != nullptr && !Mask->Mask) {
+ return fail("register-mask operand contains a null mask");
+ }
+ if (const auto *Global = Operand.getIf<GlobalSymbolOperand>();
+ Global != nullptr && Global->Name.empty()) {
+ return fail("global symbol operand has an empty name");
+ }
+ if (const auto *External = Operand.getIf<ExternalSymbolOperand>();
+ External != nullptr && External->Name.empty()) {
+ return fail("external symbol operand has an empty name");
+ }
+ if (const auto *Address = Operand.getIf<BlockAddressOperand>();
+ Address != nullptr && (Address->FunctionName.empty() || Address->BlockName.empty())) {
+ return fail("block-address operand has an incomplete name");
+ }
+ if (const auto *Metadata = Operand.getIf<MetadataOperand>();
+ Metadata != nullptr && Metadata->Marker.empty()) {
+ return fail("metadata operand has an empty marker");
+ }
+ if (const auto *Symbol = Operand.getIf<MCSymbolOperand>();
+ Symbol != nullptr && Symbol->Name.empty()) {
+ return fail("MC symbol operand has an empty name");
+ }
+ }
+
+ for (const MachineMemOperand *MemOperand : Instruction.memOperands()) {
+ if (MemOperand == nullptr || !RegisteredMemOperands.contains(MemOperand)) {
+ return fail("instruction references a foreign or null MMO");
+ }
+ }
+ return {};
+ }
+
+ [[nodiscard]] Expected<void> verifyLiveInstruction(const MachineInstr &Instruction) {
+ auto LocalResult = verifyInstructionLocalState(Instruction);
+ if (!LocalResult)
+ return LocalResult;
+
+ const InstructionDescriptor *Descriptor = Instructions.descriptor(Instruction.opcode());
+ if (Descriptor == nullptr)
+ return fail("live instruction uses an unregistered opcode");
+ auto DescriptorResult = Instructions.validateInstruction(Instruction, Function.registerInfo());
+ if (!DescriptorResult)
+ return failWith("instruction descriptor", DescriptorResult.error());
+
+ if (Options.Stage && Descriptor->Flags.has(InstructionFlag::Pseudo) &&
+ static_cast<std::uint8_t>(*Options.Stage) >
+ static_cast<std::uint8_t>(Descriptor->Deadline)) {
+ return fail("pseudo instruction survives beyond its expansion deadline");
+ }
+
+ HasPhi |= Descriptor->Flags.has(InstructionFlag::Phi);
+ HasGenericInstruction |= Descriptor->Flags.has(InstructionFlag::Generic);
+ HasExecutablePseudo |= Descriptor->Flags.has(InstructionFlag::Pseudo) &&
+ !Descriptor->Flags.has(InstructionFlag::Meta) &&
+ !Descriptor->Flags.has(InstructionFlag::TerminalEmission);
+
+ const auto Operands = Instruction.operands();
+ for (std::size_t Index = 0; Index < Operands.size(); ++Index) {
+ const MachineOperand &Operand = Operands[Index];
+ if (Operand.kind() == MachineOperand::Kind::FrameIndex)
+ HasFrameIndex = true;
+
+ if (const auto *Block = Operand.getIf<BasicBlockOperand>();
+ Block != nullptr &&
+ (Block->Block == nullptr || &Block->Block->function() != &Function ||
+ !RegisteredBlocks.contains(Block->Block) || !Block->Block->isLinked())) {
+ return fail("basic-block operand references a foreign or detached block");
+ }
+
+ const Register *Reg = Operand.getIf<Register>();
+ if (Reg == nullptr)
+ continue;
+ const bool ShouldBeLinked = !Reg->isNoRegister();
+ if (Function.registerInfo().isLinkedOperand(Operand) != ShouldBeLinked) {
+ return fail("live register operand has incorrect def-use linkage");
+ }
+ if (Reg->isVirtual()) {
+ if (!Function.registerInfo().isKnownVirtualRegister(*Reg))
+ return fail("instruction references an unknown virtual register");
+ if (Operand.isDef())
+ ++VirtualDefCounts[*Reg];
+ }
+
+ if (Operand.tiedOperandIndex() && Index < *Operand.tiedOperandIndex()) {
+ const MachineOperand *Other = Instruction.operandAt(*Operand.tiedOperandIndex());
+ const Register *OtherReg = Other == nullptr ? nullptr : Other->getIf<Register>();
+ if (OtherReg == nullptr || *OtherReg != *Reg)
+ HasUnrewrittenTie = true;
+ }
+ }
+ return {};
+ }
+
+ [[nodiscard]] Expected<void> verifyCFG() {
+ for (const MachineBasicBlock *Block : LinkedBlocks) {
+ std::unordered_set<const MachineBasicBlock *> Successors;
+ for (const MachineSuccessor &Successor : Block->successors()) {
+ if (Successor.Block == nullptr || !LinkedBlocks.contains(Successor.Block) ||
+ !Successors.insert(Successor.Block).second) {
+ return fail("CFG successor list contains a null, detached, or duplicate block");
+ }
+ if (std::ranges::count(Successor.Block->predecessors(), Block) != 1)
+ return fail("CFG successor lacks one reciprocal predecessor");
+ }
+
+ std::unordered_set<const MachineBasicBlock *> Predecessors;
+ for (const MachineBasicBlock *Predecessor : Block->predecessors()) {
+ if (Predecessor == nullptr || !LinkedBlocks.contains(Predecessor) ||
+ !Predecessors.insert(Predecessor).second) {
+ return fail("CFG predecessor list contains a null, detached, or duplicate block");
+ }
+ const auto Matches = std::ranges::count_if(
+ Predecessor->successors(),
+ [Block](const MachineSuccessor &Successor) { return Successor.Block == Block; });
+ if (Matches != 1)
+ return fail("CFG predecessor lacks one reciprocal successor");
+ }
+
+ std::unordered_set<PhysicalRegister> LiveIns;
+ for (const MachineBasicBlockLiveIn &LiveIn : Block->liveIns()) {
+ if (!LiveIn.PhysReg.isValid() || LiveIn.Lanes.empty() ||
+ !LiveIns.insert(LiveIn.PhysReg).second) {
+ return fail("block live-in list contains invalid or duplicate entries");
+ }
+ }
+ }
+ return {};
+ }
+
+ [[nodiscard]] Expected<void> verifyRegisterInfo() {
+ const MachineRegisterInfo &RegInfo = Function.registerInfo();
+ std::unordered_set<PhysicalRegister> FunctionLiveIns;
+ for (const PhysicalRegisterLiveIn &LiveIn : RegInfo.liveIns()) {
+ if (!LiveIn.PhysReg.isValid() || !FunctionLiveIns.insert(LiveIn.PhysReg).second) {
+ return fail("function live-in list contains invalid or duplicate entries");
+ }
+ if (LiveIn.InitialVirtualRegister &&
+ !RegInfo.isKnownVirtualRegister(*LiveIn.InitialVirtualRegister)) {
+ return fail("function live-in references an unknown virtual register");
+ }
+ }
+
+ std::unordered_set<PhysicalRegister> Reserved;
+ for (const PhysicalRegister Reg : RegInfo.reservedRegisters()) {
+ if (!Reg.isValid() || !Reserved.insert(Reg).second)
+ return fail("reserved-register list contains invalid or duplicate entries");
+ }
+
+ for (const VirtualRegisterInfo &Info : RegInfo.virtualRegisters()) {
+ if (Info.IsTombstone) {
+ if (Info.Type || Info.Bank || Info.RegClass || !Info.AllocationHints.empty()) {
+ return fail("virtual-register tombstone retains semantic state");
+ }
+ continue;
+ }
+ HasLiveVirtualRegister = true;
+ MissingVirtualType |= !Info.Type;
+ MissingVirtualBank |= !Info.Bank;
+ MissingVirtualClass |= !Info.RegClass;
+ if (Info.Type && !Info.Type->isValid())
+ return fail("virtual register has an invalid LLT");
+
+ std::unordered_set<PhysicalRegister> Hints;
+ for (const PhysicalRegister Hint : Info.AllocationHints) {
+ if (!Hint.isValid() || !Hints.insert(Hint).second)
+ return fail("virtual register has an invalid or duplicate allocation hint");
+ }
+ }
+ return {};
+ }
+
+ [[nodiscard]] Expected<void> verifyProperties() {
+ const MachineFunctionProperties &Properties = Function.properties();
+ auto Has = [&Properties](MachineFunctionProperty Property) { return Properties.has(Property); };
+
+ if (Has(MachineFunctionProperty::RegBankSelected) && !Has(MachineFunctionProperty::Legalized)) {
+ return fail("RegBankSelected requires Legalized");
+ }
+ if (Has(MachineFunctionProperty::Selected) && !Has(MachineFunctionProperty::RegBankSelected)) {
+ return fail("Selected requires RegBankSelected");
+ }
+ if (Has(MachineFunctionProperty::TiedOpsRewritten) && !Has(MachineFunctionProperty::Selected)) {
+ return fail("TiedOpsRewritten requires Selected");
+ }
+ if (Has(MachineFunctionProperty::FrameFinalized) &&
+ (!Has(MachineFunctionProperty::NoVRegs) || !Has(MachineFunctionProperty::NoFrameIndices))) {
+ return fail("FrameFinalized requires NoVRegs and NoFrameIndices");
+ }
+
+ if (Has(MachineFunctionProperty::IsSSA)) {
+ for (const auto &[Reg, DefinitionCount] : VirtualDefCounts) {
+ if (DefinitionCount > 1)
+ return fail("IsSSA function has a multiply-defined virtual register");
+ }
+ }
+ if (Has(MachineFunctionProperty::NoPHIs) && HasPhi)
+ return fail("NoPHIs function contains a PHI instruction");
+ if (Has(MachineFunctionProperty::NoVRegs) && HasLiveVirtualRegister) {
+ return fail("NoVRegs function retains a live virtual register");
+ }
+ if (Has(MachineFunctionProperty::NoFrameIndices) && HasFrameIndex)
+ return fail("NoFrameIndices function contains a frame-index operand");
+ if (Has(MachineFunctionProperty::NoExecutablePseudos) && HasExecutablePseudo) {
+ return fail("NoExecutablePseudos function contains an executable pseudo");
+ }
+ if (Has(MachineFunctionProperty::RegBankSelected) && MissingVirtualBank) {
+ return fail("RegBankSelected function has a virtual register without a bank");
+ }
+ if (Has(MachineFunctionProperty::Selected) && (HasGenericInstruction || MissingVirtualClass)) {
+ return fail("Selected function contains generic code or an unclassified virtual register");
+ }
+ if (Has(MachineFunctionProperty::TiedOpsRewritten) && HasUnrewrittenTie) {
+ return fail("TiedOpsRewritten function has unequal tied registers");
+ }
+
+ const bool NeedsTypes = Options.Mode == MachineVerifierMode::PreLegalizer ||
+ Has(MachineFunctionProperty::Legalized) ||
+ Has(MachineFunctionProperty::RegBankSelected);
+ if (NeedsTypes && MissingVirtualType)
+ return fail("typed pipeline stage has a virtual register without LLT");
+
+ if (Options.Mode == MachineVerifierMode::PreLegalizer) {
+ if (!Has(MachineFunctionProperty::IsSSA) || !Has(MachineFunctionProperty::TracksLiveness)) {
+ return fail("pre-legalizer input requires IsSSA and TracksLiveness");
+ }
+ if (Has(MachineFunctionProperty::Legalized) ||
+ Has(MachineFunctionProperty::RegBankSelected) || Has(MachineFunctionProperty::Selected) ||
+ Has(MachineFunctionProperty::TiedOpsRewritten) || Has(MachineFunctionProperty::NoVRegs) ||
+ Has(MachineFunctionProperty::FrameFinalized)) {
+ return fail("pre-legalizer input carries a later-stage property");
+ }
+ }
+ return {};
+ }
+
+ const MachineFunction &Function;
+ const InstructionSet &Instructions;
+ MachineVerifierOptions Options;
+ std::unordered_set<const MachineBasicBlock *> RegisteredBlocks;
+ std::unordered_set<const MachineBasicBlock *> LinkedBlocks;
+ std::unordered_set<const MachineInstr *> RegisteredInstructions;
+ std::unordered_set<const MachineInstr *> LinkedInstructions;
+ std::unordered_set<const MachineMemOperand *> RegisteredMemOperands;
+ std::unordered_map<Register, std::size_t> VirtualDefCounts;
+ bool HasPhi = false;
+ bool HasGenericInstruction = false;
+ bool HasExecutablePseudo = false;
+ bool HasFrameIndex = false;
+ bool HasUnrewrittenTie = false;
+ bool HasLiveVirtualRegister = false;
+ bool MissingVirtualType = false;
+ bool MissingVirtualBank = false;
+ bool MissingVirtualClass = false;
+};
+
+} // namespace
+
+Expected<void> MachineVerifier::verify(const MachineFunction &Function,
+ const InstructionSet &Instructions,
+ MachineVerifierOptions Options) {
+ return FunctionVerifier(Function, Instructions, Options).run();
+}
+
+} // namespace rcc
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index ddba86a..6f17fc0 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -6,6 +6,7 @@ set(
InstructionDescriptorTest.cpp
MachineIRBuilderTest.cpp
MachineIRCoreTest.cpp
+ MachineVerifierTest.cpp
MachineValueTypesTest.cpp
)
@@ -42,6 +43,18 @@ add_test(
COMMAND RCCBackendCodeGenMachineIRBuilderTests
)
+add_executable(RCCBackendCodeGenMachineVerifierTests MachineVerifierTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenMachineVerifierTests)
+target_link_libraries(
+ RCCBackendCodeGenMachineVerifierTests
+ PRIVATE RCCBackend::CodeGen
+)
+
+add_test(
+ NAME RCCBackend.CodeGen.MachineVerifier
+ COMMAND RCCBackendCodeGenMachineVerifierTests
+)
+
add_executable(RCCBackendCodeGenMachineValueTypesTests MachineValueTypesTest.cpp)
rcc_backend_configure_target(RCCBackendCodeGenMachineValueTypesTests)
target_link_libraries(RCCBackendCodeGenMachineValueTypesTests PRIVATE RCCBackend::CodeGen)
@@ -65,6 +78,7 @@ rcc_backend_register_format_files(
"${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptorTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilderTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
)
rcc_backend_register_tidy_files(
@@ -72,5 +86,6 @@ rcc_backend_register_tidy_files(
"${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptorTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineIRBuilderTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifierTest.cpp"
"${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
)
diff --git a/backend/unittests/CodeGen/MachineVerifierTest.cpp b/backend/unittests/CodeGen/MachineVerifierTest.cpp
new file mode 100644
index 0000000..b8b985e
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineVerifierTest.cpp
@@ -0,0 +1,459 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineVerifier.h"
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionProperties.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace {
+
+constexpr std::uint32_t GenericDefOpcode = 1;
+constexpr std::uint32_t GenericUseOpcode = 2;
+constexpr std::uint32_t CopyOpcode = 3;
+constexpr std::uint32_t BranchOpcode = 4;
+constexpr std::uint32_t PhiOpcode = 5;
+constexpr std::uint32_t FrameOpcode = 6;
+constexpr std::uint32_t PseudoOpcode = 7;
+constexpr std::uint32_t NopOpcode = 8;
+
+class TestContext final {
+public:
+ void expect(bool Condition, std::string_view Message) {
+ if (Condition)
+ return;
+ std::cerr << Message << '\n';
+ ++FailureCount;
+ }
+
+ [[nodiscard]] int result() const noexcept {
+ return FailureCount == 0 ? 0 : 1;
+ }
+
+private:
+ int FailureCount = 0;
+};
+
+[[nodiscard]] rcc::OperandDescriptor registerDescriptor(rcc::RegisterOperandRole Role) {
+ rcc::OperandDescriptor Descriptor;
+ Descriptor.Kinds = {rcc::MachineOperand::Kind::Register};
+ Descriptor.RegisterRole = Role;
+ return Descriptor;
+}
+
+[[nodiscard]] rcc::InstructionDescriptor instructionDescriptor(std::uint32_t OpcodeValue,
+ std::string Name) {
+ rcc::InstructionDescriptor Descriptor;
+ Descriptor.InstructionOpcode = rcc::Opcode::fromValue(OpcodeValue);
+ Descriptor.Name = std::move(Name);
+ Descriptor.Flags = {rcc::InstructionFlag::ProducesCode};
+ return Descriptor;
+}
+
+[[nodiscard]] rcc::Expected<rcc::InstructionSet> createInstructionSet() {
+ auto GenericDef = instructionDescriptor(GenericDefOpcode, "TEST_GENERIC_DEF");
+ GenericDef.Operands.push_back(registerDescriptor(rcc::RegisterOperandRole::Def));
+ GenericDef.NumExplicitDefs = 1;
+ GenericDef.Flags.set(rcc::InstructionFlag::Generic);
+ GenericDef.Flags.set(rcc::InstructionFlag::AllowedPreLegalizer);
+
+ auto GenericUse = instructionDescriptor(GenericUseOpcode, "TEST_GENERIC_USE");
+ GenericUse.Operands.push_back(registerDescriptor(rcc::RegisterOperandRole::Use));
+ GenericUse.Flags.set(rcc::InstructionFlag::Generic);
+ GenericUse.Flags.set(rcc::InstructionFlag::AllowedPreLegalizer);
+
+ auto Copy = instructionDescriptor(CopyOpcode, "TEST_COPY");
+ auto CopyDef = registerDescriptor(rcc::RegisterOperandRole::Def);
+ auto CopyUse = registerDescriptor(rcc::RegisterOperandRole::Use);
+ CopyDef.DefaultTiedOperand = 1;
+ CopyUse.DefaultTiedOperand = 0;
+ Copy.Operands.push_back(CopyDef);
+ Copy.Operands.push_back(CopyUse);
+ Copy.NumExplicitDefs = 1;
+
+ auto Branch = instructionDescriptor(BranchOpcode, "TEST_BRANCH");
+ rcc::OperandDescriptor Block;
+ Block.Kinds = {rcc::MachineOperand::Kind::BasicBlock};
+ Branch.Operands.push_back(Block);
+ Branch.Flags.set(rcc::InstructionFlag::Terminator);
+ Branch.Flags.set(rcc::InstructionFlag::Branch);
+
+ auto Phi = instructionDescriptor(PhiOpcode, "TEST_PHI");
+ Phi.Operands.push_back(registerDescriptor(rcc::RegisterOperandRole::Def));
+ Phi.NumExplicitDefs = 1;
+ Phi.Flags.set(rcc::InstructionFlag::Pseudo);
+ Phi.Flags.set(rcc::InstructionFlag::Phi);
+ Phi.Owner = rcc::PseudoOwner::PhiElimination;
+ Phi.Deadline = rcc::PipelineStage::SSAEliminated;
+
+ auto Frame = instructionDescriptor(FrameOpcode, "TEST_FRAME");
+ rcc::OperandDescriptor FrameIndex;
+ FrameIndex.Kinds = {rcc::MachineOperand::Kind::FrameIndex};
+ Frame.Operands.push_back(FrameIndex);
+
+ auto Pseudo = instructionDescriptor(PseudoOpcode, "TEST_PSEUDO");
+ Pseudo.Flags.set(rcc::InstructionFlag::Pseudo);
+ Pseudo.Owner = rcc::PseudoOwner::InstructionSelect;
+ Pseudo.Deadline = rcc::PipelineStage::Selected;
+
+ auto Nop = instructionDescriptor(NopOpcode, "TEST_NOP");
+
+ std::vector<rcc::InstructionDescriptor> Descriptors;
+ Descriptors.push_back(std::move(GenericDef));
+ Descriptors.push_back(std::move(GenericUse));
+ Descriptors.push_back(std::move(Copy));
+ Descriptors.push_back(std::move(Branch));
+ Descriptors.push_back(std::move(Phi));
+ Descriptors.push_back(std::move(Frame));
+ Descriptors.push_back(std::move(Pseudo));
+ Descriptors.push_back(std::move(Nop));
+ return rcc::InstructionSet::create(std::move(Descriptors));
+}
+
+[[nodiscard]] std::unique_ptr<rcc::MachineFunction>
+createFunction(TestContext &Context, std::string Name, std::uint64_t ID) {
+ auto Function =
+ rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID));
+ Context.expect(Function.has_value(), "machine function creation must succeed");
+ if (!Function)
+ return nullptr;
+ return std::move(*Function);
+}
+
+[[nodiscard]] rcc::MachineBasicBlock *createBlock(TestContext &Context,
+ rcc::MachineFunction &Function) {
+ auto Block = Function.createBasicBlock();
+ Context.expect(Block.has_value(), "machine basic block creation must succeed");
+ if (!Block)
+ return nullptr;
+ Context.expect(Function.appendBlock(**Block).has_value(),
+ "machine basic block linking must succeed");
+ return *Block;
+}
+
+[[nodiscard]] rcc::MachineInstr *
+buildNoOperand(TestContext &Context, rcc::MachineIRBuilder &Builder, std::uint32_t OpcodeValue) {
+ auto Pending = Builder.buildInstr(rcc::Opcode::fromValue(OpcodeValue));
+ Context.expect(Pending.has_value(), "pending no-operand instruction must be created");
+ if (!Pending)
+ return nullptr;
+ auto Result = Pending->build();
+ Context.expect(Result.has_value(), "no-operand instruction must build");
+ if (!Result)
+ return nullptr;
+ return *Result;
+}
+
+[[nodiscard]] bool populateValidPreLegalizer(TestContext &Context, rcc::MachineFunction &Function,
+ const rcc::InstructionSet &InstructionSet) {
+ rcc::MachineBasicBlock *Entry = createBlock(Context, Function);
+ rcc::MachineBasicBlock *Exit = createBlock(Context, Function);
+ if (Entry == nullptr || Exit == nullptr)
+ return false;
+
+ auto Type = rcc::LLT::makeInteger(64);
+ auto Value = Function.registerInfo().createVirtualRegister(*Type);
+ Context.expect(Value.has_value(), "typed verifier virtual register must be allocated");
+ if (!Value)
+ return false;
+
+ rcc::MachineIRBuilder Builder(Function, InstructionSet);
+ Context.expect(Builder.setInsertPoint(*Entry).has_value(), "entry insertion point must be valid");
+ auto Def = Builder.buildInstr(rcc::Opcode::fromValue(GenericDefOpcode));
+ Context.expect(Def && Def->addDef(*Value).has_value(), "generic definition must be assembled");
+ if (!Def || !Def->build())
+ return false;
+
+ auto Branch = Builder.buildInstr(rcc::Opcode::fromValue(BranchOpcode));
+ Context.expect(Branch && Branch->addBasicBlock(*Exit).has_value(),
+ "branch operand must be assembled");
+ if (!Branch || !Branch->build())
+ return false;
+
+ Context.expect(
+ Function.cfgUpdater().addSuccessor(*Entry, *Exit, rcc::BranchProbability::one()).has_value(),
+ "valid verifier CFG edge must be created");
+
+ Context.expect(Builder.setInsertPoint(*Exit).has_value(), "exit insertion point must be valid");
+ auto Use = Builder.buildInstr(rcc::Opcode::fromValue(GenericUseOpcode));
+ Context.expect(Use && Use->addUse(*Value).has_value(), "generic use must be assembled");
+ if (!Use || !Use->build())
+ return false;
+
+ Function.properties().set(rcc::MachineFunctionProperty::IsSSA);
+ Function.properties().set(rcc::MachineFunctionProperty::TracksLiveness);
+ return true;
+}
+
+void testValidFunctionAndModes(TestContext &Context) {
+ auto InstructionSet = createInstructionSet();
+ auto Function = createFunction(Context, "valid", 1);
+ if (!InstructionSet || !Function ||
+ !populateValidPreLegalizer(Context, *Function, *InstructionSet)) {
+ return;
+ }
+
+ Context.expect(rcc::MachineVerifier::verify(*Function, *InstructionSet).has_value(),
+ "well-formed function must pass generic verification");
+ Context.expect(
+ rcc::MachineVerifier::verify(
+ *Function, *InstructionSet,
+ rcc::MachineVerifierOptions{rcc::MachineVerifierMode::PreLegalizer, std::nullopt, true})
+ .has_value(),
+ "typed SSA input must pass pre-legalizer verification");
+
+ auto DetachedBlock = Function->createBasicBlock();
+ auto DetachedInstruction = Function->createInstruction(rcc::Opcode::fromValue(NopOpcode));
+ Context.expect(DetachedBlock && DetachedInstruction,
+ "detached arena history must be allocatable");
+ Context.expect(rcc::MachineVerifier::verify(*Function, *InstructionSet).has_value(),
+ "empty detached arena objects must not invalidate live layout");
+
+ Function->properties().set(rcc::MachineFunctionProperty::Legalized);
+ Context.expect(
+ !rcc::MachineVerifier::verify(
+ *Function, *InstructionSet,
+ rcc::MachineVerifierOptions{rcc::MachineVerifierMode::PreLegalizer, std::nullopt, true}),
+ "pre-legalizer mode must reject later-stage properties");
+}
+
+void testReachableStructuralFailures(TestContext &Context) {
+ auto InstructionSet = createInstructionSet();
+ if (!InstructionSet)
+ return;
+
+ auto Unknown = createFunction(Context, "unknown_opcode", 2);
+ rcc::MachineBasicBlock *UnknownBlock = Unknown ? createBlock(Context, *Unknown) : nullptr;
+ if (Unknown && UnknownBlock != nullptr) {
+ auto Instruction = Unknown->createInstruction(rcc::Opcode::fromValue(999));
+ Context.expect(Instruction && UnknownBlock->appendInstruction(**Instruction).has_value(),
+ "unknown opcode negative test must be linked");
+ Context.expect(!rcc::MachineVerifier::verify(*Unknown, *InstructionSet),
+ "live unregistered opcode must fail verification");
+ }
+
+ auto WrongOperands = createFunction(Context, "wrong_operands", 3);
+ rcc::MachineBasicBlock *WrongBlock =
+ WrongOperands ? createBlock(Context, *WrongOperands) : nullptr;
+ if (WrongOperands && WrongBlock != nullptr) {
+ auto Instruction = WrongOperands->createInstruction(rcc::Opcode::fromValue(GenericDefOpcode));
+ Context.expect(Instruction && WrongBlock->appendInstruction(**Instruction).has_value(),
+ "wrong-operand negative test must be linked");
+ Context.expect(!rcc::MachineVerifier::verify(*WrongOperands, *InstructionSet),
+ "descriptor operand-count mismatch must fail verification");
+ }
+
+ auto DetachedChild = createFunction(Context, "detached_child", 4);
+ if (DetachedChild) {
+ auto Block = DetachedChild->createBasicBlock();
+ auto Instruction = DetachedChild->createInstruction(rcc::Opcode::fromValue(NopOpcode));
+ Context.expect(Block && Instruction && (*Block)->appendInstruction(**Instruction).has_value(),
+ "detached block negative test must contain an instruction");
+ Context.expect(!rcc::MachineVerifier::verify(*DetachedChild, *InstructionSet),
+ "detached block retaining instructions must fail verification");
+ }
+
+ auto DetachedCFG = createFunction(Context, "detached_cfg", 5);
+ rcc::MachineBasicBlock *Linked = DetachedCFG ? createBlock(Context, *DetachedCFG) : nullptr;
+ if (DetachedCFG && Linked != nullptr) {
+ auto Detached = DetachedCFG->createBasicBlock();
+ Context.expect(Detached && DetachedCFG->cfgUpdater()
+ .addSuccessor(**Detached, *Linked, rcc::BranchProbability::one())
+ .has_value(),
+ "detached CFG negative test edge must be created");
+ Context.expect(!rcc::MachineVerifier::verify(*DetachedCFG, *InstructionSet),
+ "detached block retaining CFG state must fail verification");
+ }
+}
+
+void testPropertyFailures(TestContext &Context) {
+ auto InstructionSet = createInstructionSet();
+ if (!InstructionSet)
+ return;
+ auto Type = rcc::LLT::makeInteger(64);
+
+ auto SSA = createFunction(Context, "ssa", 6);
+ rcc::MachineBasicBlock *SSABlock = SSA ? createBlock(Context, *SSA) : nullptr;
+ if (SSA && SSABlock != nullptr) {
+ auto Value = SSA->registerInfo().createVirtualRegister(*Type);
+ rcc::MachineIRBuilder Builder(*SSA, *InstructionSet);
+ Context.expect(Value && Builder.setInsertPoint(*SSABlock).has_value(),
+ "SSA negative test setup must succeed");
+ for (int Index = 0; Index != 2 && Value; ++Index) {
+ auto Def = Builder.buildInstr(rcc::Opcode::fromValue(GenericDefOpcode));
+ Context.expect(Def && Def->addDef(*Value).has_value() && Def->build(),
+ "SSA negative test definition must build");
+ }
+ SSA->properties().set(rcc::MachineFunctionProperty::IsSSA);
+ Context.expect(!rcc::MachineVerifier::verify(*SSA, *InstructionSet),
+ "IsSSA must reject a multiply-defined virtual register");
+ }
+
+ auto PHI = createFunction(Context, "phi", 7);
+ rcc::MachineBasicBlock *PHIBlock = PHI ? createBlock(Context, *PHI) : nullptr;
+ if (PHI && PHIBlock != nullptr) {
+ auto Value = PHI->registerInfo().createVirtualRegister(*Type);
+ rcc::MachineIRBuilder Builder(*PHI, *InstructionSet);
+ Context.expect(Value && Builder.setInsertPoint(*PHIBlock).has_value(),
+ "PHI negative test setup must succeed");
+ auto Pending = Builder.buildInstr(rcc::Opcode::fromValue(PhiOpcode));
+ Context.expect(Pending && Pending->addDef(*Value).has_value() && Pending->build(),
+ "PHI negative test instruction must build");
+ PHI->properties().set(rcc::MachineFunctionProperty::NoPHIs);
+ Context.expect(!rcc::MachineVerifier::verify(*PHI, *InstructionSet),
+ "NoPHIs must reject a PHI instruction");
+ }
+
+ auto NoVRegs = createFunction(Context, "no_vregs", 8);
+ if (NoVRegs) {
+ rcc::MachineBasicBlock *Block = createBlock(Context, *NoVRegs);
+ auto Value = NoVRegs->registerInfo().createVirtualRegister(*Type);
+ rcc::MachineIRBuilder Builder(*NoVRegs, *InstructionSet);
+ Context.expect(Block != nullptr && Builder.setInsertPoint(*Block).has_value(),
+ "NoVRegs negative test setup must succeed");
+ auto Pending = Builder.buildInstr(rcc::Opcode::fromValue(GenericDefOpcode));
+ Context.expect(Value && Pending && Pending->addDef(*Value).has_value(),
+ "NoVRegs linked history must be assembled");
+ if (!Value || !Pending || Block == nullptr)
+ return;
+ auto Built = Pending->build();
+ NoVRegs->properties().set(rcc::MachineFunctionProperty::NoVRegs);
+ Context.expect(Value && Built && !rcc::MachineVerifier::verify(*NoVRegs, *InstructionSet),
+ "NoVRegs must reject a live virtual register");
+ Context.expect(Value && Built && Block != nullptr &&
+ Block->removeInstruction(**Built).has_value() &&
+ NoVRegs->registerInfo().eraseVirtualRegister(*Value).has_value() &&
+ rcc::MachineVerifier::verify(*NoVRegs, *InstructionSet).has_value(),
+ "NoVRegs must accept tombstoned def-use history");
+ }
+
+ auto Frame = createFunction(Context, "frame_index", 9);
+ rcc::MachineBasicBlock *FrameBlock = Frame ? createBlock(Context, *Frame) : nullptr;
+ if (Frame && FrameBlock != nullptr) {
+ rcc::MachineIRBuilder Builder(*Frame, *InstructionSet);
+ Context.expect(Builder.setInsertPoint(*FrameBlock).has_value(),
+ "frame-index negative test setup must succeed");
+ auto Pending = Builder.buildInstr(rcc::Opcode::fromValue(FrameOpcode));
+ Context.expect(Pending && Pending->addFrameIndex(rcc::FrameIndex::fromValue(0)).has_value() &&
+ Pending->build(),
+ "frame-index negative test instruction must build");
+ Frame->properties().set(rcc::MachineFunctionProperty::NoFrameIndices);
+ Context.expect(!rcc::MachineVerifier::verify(*Frame, *InstructionSet),
+ "NoFrameIndices must reject a frame-index operand");
+ }
+
+ auto Pseudo = createFunction(Context, "pseudo", 10);
+ rcc::MachineBasicBlock *PseudoBlock = Pseudo ? createBlock(Context, *Pseudo) : nullptr;
+ if (Pseudo && PseudoBlock != nullptr) {
+ rcc::MachineIRBuilder Builder(*Pseudo, *InstructionSet);
+ Context.expect(Builder.setInsertPoint(*PseudoBlock).has_value() &&
+ buildNoOperand(Context, Builder, PseudoOpcode) != nullptr,
+ "pseudo negative test instruction must build");
+ Pseudo->properties().set(rcc::MachineFunctionProperty::NoExecutablePseudos);
+ Context.expect(!rcc::MachineVerifier::verify(*Pseudo, *InstructionSet),
+ "NoExecutablePseudos must reject an executable pseudo");
+ }
+}
+
+void testSelectedStateAndPseudoDeadline(TestContext &Context) {
+ auto InstructionSet = createInstructionSet();
+ auto Type = rcc::LLT::makeInteger(64);
+ if (!InstructionSet)
+ return;
+
+ auto Tied = createFunction(Context, "tied", 11);
+ rcc::MachineBasicBlock *TiedBlock = Tied ? createBlock(Context, *Tied) : nullptr;
+ if (Tied && TiedBlock != nullptr) {
+ auto Def = Tied->registerInfo().createVirtualRegister(*Type);
+ auto Use = Tied->registerInfo().createVirtualRegister(*Type);
+ if (!Def || !Use)
+ return;
+ for (const rcc::Register Reg : {*Def, *Use}) {
+ Context.expect(Tied->registerInfo()
+ .setRegisterBank(Reg, rcc::RegisterBankID::fromValue(1))
+ .has_value() &&
+ Tied->registerInfo()
+ .setRegisterClass(Reg, rcc::RegisterClassID::fromValue(1))
+ .has_value(),
+ "selected-state register constraints must be recorded");
+ }
+
+ rcc::MachineIRBuilder Builder(*Tied, *InstructionSet);
+ Context.expect(Builder.setInsertPoint(*TiedBlock).has_value(),
+ "tied-state insertion point must be valid");
+ auto Pending = Builder.buildInstr(rcc::Opcode::fromValue(CopyOpcode));
+ Context.expect(Pending && Pending->addDef(*Def).has_value() &&
+ Pending->addUse(*Use).has_value() && Pending->build(),
+ "tied-state instruction must build");
+ for (const rcc::MachineFunctionProperty Property :
+ {rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
+ rcc::MachineFunctionProperty::Selected, rcc::MachineFunctionProperty::TiedOpsRewritten}) {
+ Tied->properties().set(Property);
+ }
+ Context.expect(!rcc::MachineVerifier::verify(*Tied, *InstructionSet),
+ "TiedOpsRewritten must reject unequal tied registers");
+ rcc::MachineInstr *Instruction = TiedBlock->firstInstruction();
+ Context.expect(Instruction != nullptr &&
+ Instruction->operandAt(1)->setRegister(*Def).has_value() &&
+ rcc::MachineVerifier::verify(*Tied, *InstructionSet).has_value(),
+ "equal tied registers must satisfy TiedOpsRewritten");
+ }
+
+ auto Pseudo = createFunction(Context, "pseudo_deadline", 12);
+ rcc::MachineBasicBlock *Block = Pseudo ? createBlock(Context, *Pseudo) : nullptr;
+ if (Pseudo && Block != nullptr) {
+ rcc::MachineIRBuilder Builder(*Pseudo, *InstructionSet);
+ Context.expect(Builder.setInsertPoint(*Block).has_value() &&
+ buildNoOperand(Context, Builder, PseudoOpcode) != nullptr,
+ "deadline pseudo must build");
+ Context.expect(
+ rcc::MachineVerifier::verify(*Pseudo, *InstructionSet,
+ rcc::MachineVerifierOptions{rcc::MachineVerifierMode::Generic,
+ rcc::PipelineStage::Selected})
+ .has_value(),
+ "pseudo may remain at its declared deadline");
+ Context.expect(!rcc::MachineVerifier::verify(
+ *Pseudo, *InstructionSet,
+ rcc::MachineVerifierOptions{rcc::MachineVerifierMode::Generic,
+ rcc::PipelineStage::RegisterAllocated}),
+ "pseudo must not survive beyond its declared deadline");
+ }
+
+ auto Dependency = createFunction(Context, "property_dependency", 13);
+ if (Dependency) {
+ Dependency->properties().set(rcc::MachineFunctionProperty::Selected);
+ Context.expect(!rcc::MachineVerifier::verify(*Dependency, *InstructionSet),
+ "Selected must require prior pipeline properties");
+ Dependency->properties().clear(rcc::MachineFunctionProperty::Selected);
+ Dependency->properties().set(rcc::MachineFunctionProperty::FrameFinalized);
+ Context.expect(!rcc::MachineVerifier::verify(*Dependency, *InstructionSet),
+ "FrameFinalized must require NoVRegs and NoFrameIndices");
+ }
+}
+
+} // namespace
+
+int main() {
+ TestContext Context;
+ testValidFunctionAndModes(Context);
+ testReachableStructuralFailures(Context);
+ testPropertyFailures(Context);
+ testSelectedStateAndPseudoDeadline(Context);
+ return Context.result();
+}
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 06:31:04 +0000