diff options
| -rw-r--r-- | backend/include/rcc/CodeGen/MIRPrinter.h | 13 | ||||
| -rw-r--r-- | backend/include/rcc/CodeGen/ReachingDefAnalysis.h | 52 | ||||
| -rw-r--r-- | backend/include/rcc/MIR/ReachingDefPrinter.h | 26 | ||||
| -rw-r--r-- | backend/lib/CodeGen/CMakeLists.txt | 2 | ||||
| -rw-r--r-- | backend/lib/CodeGen/LiveVariables.cpp | 13 | ||||
| -rw-r--r-- | backend/lib/CodeGen/MIRPrinter.cpp | 141 | ||||
| -rw-r--r-- | backend/lib/CodeGen/ReachingDefAnalysis.cpp | 252 | ||||
| -rw-r--r-- | backend/lib/MIR/CMakeLists.txt | 4 | ||||
| -rw-r--r-- | backend/lib/MIR/ReachingDefPrinter.cpp | 81 | ||||
| -rw-r--r-- | backend/lib/Tooling/PipelineDriver.cpp | 13 |
10 files changed, 554 insertions, 43 deletions
diff --git a/backend/include/rcc/CodeGen/MIRPrinter.h b/backend/include/rcc/CodeGen/MIRPrinter.h index 4c20bed..ea58434 100644 --- a/backend/include/rcc/CodeGen/MIRPrinter.h +++ b/backend/include/rcc/CodeGen/MIRPrinter.h @@ -13,6 +13,8 @@ namespace rcc { class MachineFunction; class MachineBasicBlock; +class MachineInstr; +class MachineOperand; class TargetDescription; namespace mir { @@ -36,6 +38,17 @@ struct MIPrinterOptions final { const MIParserContext &Context = {}, MIPrinterOptions Options = {}); +[[nodiscard]] Expected<MIParserContext> +createMachineFunctionPrintContext(const MachineFunction &Function); +[[nodiscard]] Expected<std::string> printMachineInstruction(const MachineInstr &Instruction, + const TargetDescription &Target, + const MIParserContext &Context, + MIPrinterOptions Options = {}); +[[nodiscard]] Expected<std::string> printMachineOperand(const MachineOperand &Operand, + const TargetDescription &Target, + const MIParserContext &Context, + MIPrinterOptions Options = {}); + struct MIRDocumentPrinterOptions final { MIPrintMode Mode = MIPrintMode::Complete; bool EmitEmbeddedIR = true; diff --git a/backend/include/rcc/CodeGen/ReachingDefAnalysis.h b/backend/include/rcc/CodeGen/ReachingDefAnalysis.h new file mode 100644 index 0000000..64eb462 --- /dev/null +++ b/backend/include/rcc/CodeGen/ReachingDefAnalysis.h @@ -0,0 +1,52 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_REACHINGDEFANALYSIS_H +#define RCC_CODEGEN_REACHINGDEFANALYSIS_H + +#include "rcc/CodeGen/MachineFunctionAnalysisManager.h" +#include "rcc/Support/Error.h" + +#include <cstddef> +#include <span> +#include <string_view> +#include <unordered_map> +#include <vector> + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class MachineOperand; +class TargetDescription; + +class ReachingDefAnalysis final { +public: + using DefinitionSet = std::vector<const MachineInstr *>; + + class Result final { + public: + [[nodiscard]] std::span<const MachineInstr *const> + reachingDefinitions(const MachineOperand &Operand) const noexcept; + [[nodiscard]] std::size_t instructionNumber(const MachineInstr &Instruction) const noexcept; + [[nodiscard]] bool invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept; + + private: + std::unordered_map<const MachineOperand *, DefinitionSet> OperandDefinitions; + std::unordered_map<const MachineInstr *, std::size_t> InstructionNumbers; + + friend class ReachingDefAnalysis; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "ReachingDefAnalysis"; + } + + [[nodiscard]] static Expected<Result> run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses); +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_REACHINGDEFANALYSIS_H diff --git a/backend/include/rcc/MIR/ReachingDefPrinter.h b/backend/include/rcc/MIR/ReachingDefPrinter.h new file mode 100644 index 0000000..8b4d1e0 --- /dev/null +++ b/backend/include/rcc/MIR/ReachingDefPrinter.h @@ -0,0 +1,26 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_MIR_REACHINGDEFPRINTER_H +#define RCC_MIR_REACHINGDEFPRINTER_H + +#include "rcc/CodeGen/MachinePassManager.h" + +#include <string_view> + +namespace rcc::mir { + +class ReachingDefPrinterPass final : public MachineFunctionPass { +public: + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "print<reaching-def>"; + } + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) override; +}; + +} // namespace rcc::mir + +#endif // RCC_MIR_REACHINGDEFPRINTER_H diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index b30479e..795fb40 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -61,6 +61,7 @@ set( PrologueEpilogueInsertion.cpp PostRAScheduler.cpp RegisterPressure.cpp + ReachingDefAnalysis.cpp RegisterScavenger.cpp MacroFusion.cpp ScheduleDAG.cpp @@ -150,6 +151,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePseudoExpansion.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PrologueEpilogueInsertion.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterPressure.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/ReachingDefAnalysis.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterScavenger.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/ScheduleDAG.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/ScheduleHazardRecognizer.h" diff --git a/backend/lib/CodeGen/LiveVariables.cpp b/backend/lib/CodeGen/LiveVariables.cpp index 601fd05..3c91cfb 100644 --- a/backend/lib/CodeGen/LiveVariables.cpp +++ b/backend/lib/CodeGen/LiveVariables.cpp @@ -9,6 +9,7 @@ #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/ReachingDefAnalysis.h" #include "rcc/CodeGen/RegisterMask.h" #include "rcc/CodeGen/SlotIndexes.h" #include "rcc/CodeGen/TargetDescription.h" @@ -992,6 +993,7 @@ Expected<void> registerStage11MachineAnalyses(MachineFunctionAnalysisManager &An MachineFunctionAnalysisManager::id<LiveVariablesAnalysis>(), MachineFunctionAnalysisManager::id<LiveIntervalsAnalysis>(), MachineFunctionAnalysisManager::id<VirtRegMapAnalysis>(), + MachineFunctionAnalysisManager::id<ReachingDefAnalysis>(), }; const std::size_t Registered = static_cast<std::size_t>( std::ranges::count_if(IDs, [&Analyses](AnalysisID ID) { return Analyses.isRegistered(ID); })); @@ -1043,6 +1045,17 @@ Expected<void> registerStage11MachineAnalyses(MachineFunctionAnalysisManager &An }); if (!Mapping) return std::unexpected(Mapping.error()); + auto ReachingDefinitions = Staging.registerAnalysis<ReachingDefAnalysis>({ + .Name = "ReachingDefAnalysis", + .Dependencies = {}, + .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers, MachinePassChange::CFG, + MachinePassChange::BlockLayout, MachinePassChange::Frame, + MachinePassChange::TargetState}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!ReachingDefinitions) + return std::unexpected(ReachingDefinitions.error()); return Analyses.replaceRegistrations(std::move(Staging)); } diff --git a/backend/lib/CodeGen/MIRPrinter.cpp b/backend/lib/CodeGen/MIRPrinter.cpp index 2a6ddb4..774f322 100644 --- a/backend/lib/CodeGen/MIRPrinter.cpp +++ b/backend/lib/CodeGen/MIRPrinter.cpp @@ -473,48 +473,12 @@ MIRDocumentPrinter::verifyOmittedEmbeddedIRLayout(const MachineFunction &Functio Expected<MIParserContext> MIRDocumentPrinter::createBodyContext(const MachineFunction &Function) const { - MIParserContext Context; + auto Created = createMachineFunctionPrintContext(Function); + if (!Created) + return std::unexpected(Created.error()); + MIParserContext Context = std::move(*Created); Context.SyncScopes.assign(Document.syncScopes().begin(), Document.syncScopes().end()); - const auto VirtualRegisters = Function.registerInfo().virtualRegisters(); - for (std::size_t Index = 0; Index < VirtualRegisters.size(); ++Index) { - if (VirtualRegisters[Index].IsTombstone) - continue; - auto Reg = Register::makeVirtual(Index); - if (!Reg) - return std::unexpected(Reg.error()); - if (Index > std::numeric_limits<std::uint32_t>::max()) { - return makeUnexpected(ErrorCode::Unsupported, - "MIR cannot represent more than 2^32 virtual registers"); - } - Context.VirtualRegisters.push_back({.TextID = static_cast<std::uint32_t>(Index), .Reg = *Reg}); - } - - std::uint32_t StackID = 0; - std::uint32_t FixedID = 0; - for (const StackObject &Object : Function.frameInfo().objects()) { - const StackObjectDesc *Description = Object.description(); - if (Description == nullptr || Description->IsDead) - continue; - MIFrameObjectSlot Slot{ - .TextID = Object.isFixed() ? FixedID++ : StackID++, - .Index = Object.index(), - .Name = Description->AllocaName, - }; - (Object.isFixed() ? Context.FixedStackObjects : Context.StackObjects) - .push_back(std::move(Slot)); - } - - std::uint32_t ConstantID = 0; - for (const MachineConstantPoolEntry &Entry : Function.constantPool().entries()) { - if (Entry.description() != nullptr) - Context.ConstantPoolItems.push_back({.TextID = ConstantID++, .Index = Entry.index()}); - } - std::uint32_t JumpTableID = 0; - for (const MachineJumpTableEntry &Entry : Function.jumpTableInfo().tables()) { - if (Entry.description() != nullptr) - Context.JumpTables.push_back({.TextID = JumpTableID++, .Index = Entry.index()}); - } - + Context.Metadata.clear(); std::unordered_set<std::uint32_t> EmbeddedMetadataSlots; if (const EmbeddedIRReferenceIndex *Embedded = Document.embeddedIR()) { for (const EmbeddedIRMetadataDefinition &Definition : Embedded->metadataDefinitions()) { @@ -1680,6 +1644,8 @@ public: : Function(Function), Target(Target), Context(Context), Options(Options) {} [[nodiscard]] Expected<std::string> run(); + [[nodiscard]] Expected<std::string> runInstruction(const MachineInstr &Instruction); + [[nodiscard]] Expected<std::string> runOperand(const MachineOperand &Operand); private: [[nodiscard]] Expected<void> initialize(); @@ -3127,8 +3093,101 @@ Expected<std::string> BodyPrinter::run() { return std::move(Output); } +Expected<std::string> BodyPrinter::runInstruction(const MachineInstr &Instruction) { + if (&Instruction.function() != &Function) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine instruction belongs to a different function"); + } + if (auto Initialized = initialize(); !Initialized) + return std::unexpected(Initialized.error()); + if (auto Printed = printInstruction(Instruction); !Printed) + return std::unexpected(Printed.error()); + if (!Output.starts_with(" ")) + return makeUnexpected(ErrorCode::InternalError, "machine instruction printer lost indentation"); + Output.erase(0, 2); + return std::move(Output); +} + +Expected<std::string> BodyPrinter::runOperand(const MachineOperand &Operand) { + if (Operand.parent() != nullptr && &Operand.parent()->function() != &Function) { + return makeUnexpected(ErrorCode::InvalidArgument, + "machine operand belongs to a different function"); + } + if (auto Initialized = initialize(); !Initialized) + return std::unexpected(Initialized.error()); + if (auto Printed = printOperand(Operand, false); !Printed) + return std::unexpected(Printed.error()); + return std::move(Output); +} + } // namespace +Expected<MIParserContext> createMachineFunctionPrintContext(const MachineFunction &Function) { + MIParserContext Context; + const auto VirtualRegisters = Function.registerInfo().virtualRegisters(); + for (std::size_t Index = 0; Index < VirtualRegisters.size(); ++Index) { + if (VirtualRegisters[Index].IsTombstone) + continue; + if (Index > std::numeric_limits<std::uint32_t>::max()) { + return makeUnexpected(ErrorCode::Unsupported, + "MIR cannot represent more than 2^32 virtual registers"); + } + auto Reg = Register::makeVirtual(Index); + if (!Reg) + return std::unexpected(Reg.error()); + Context.VirtualRegisters.push_back({.TextID = static_cast<std::uint32_t>(Index), .Reg = *Reg}); + } + + std::uint32_t StackID = 0; + std::uint32_t FixedID = 0; + for (const StackObject &Object : Function.frameInfo().objects()) { + const StackObjectDesc *Description = Object.description(); + if (Description == nullptr || Description->IsDead) + continue; + MIFrameObjectSlot Slot{ + .TextID = Object.isFixed() ? FixedID++ : StackID++, + .Index = Object.index(), + .Name = Description->AllocaName, + }; + (Object.isFixed() ? Context.FixedStackObjects : Context.StackObjects) + .push_back(std::move(Slot)); + } + + std::uint32_t ConstantID = 0; + for (const MachineConstantPoolEntry &Entry : Function.constantPool().entries()) { + if (Entry.description() != nullptr) + Context.ConstantPoolItems.push_back({.TextID = ConstantID++, .Index = Entry.index()}); + } + std::uint32_t JumpTableID = 0; + for (const MachineJumpTableEntry &Entry : Function.jumpTableInfo().tables()) { + if (Entry.description() != nullptr) + Context.JumpTables.push_back({.TextID = JumpTableID++, .Index = Entry.index()}); + } + for (const MachineMetadataNode &Node : Function.metadata().nodes()) { + Context.Metadata.push_back( + {.TextID = Node.Slot, .Reference = MachineMetadataReference::machineFunction(Node.Slot)}); + } + return Context; +} + +Expected<std::string> printMachineInstruction(const MachineInstr &Instruction, + const TargetDescription &Target, + const MIParserContext &Context, + MIPrinterOptions Options) { + return BodyPrinter(Instruction.function(), Target, Context, Options).runInstruction(Instruction); +} + +Expected<std::string> printMachineOperand(const MachineOperand &Operand, + const TargetDescription &Target, + const MIParserContext &Context, + MIPrinterOptions Options) { + if (Operand.parent() == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "standalone machine operand has no owning function"); + } + return BodyPrinter(Operand.parent()->function(), Target, Context, Options).runOperand(Operand); +} + Expected<void> guessSuccessors(const MachineBasicBlock &Block, const TargetDescription &Target, std::vector<MachineBasicBlock *> &Result, bool &IsFallthrough) { Result.clear(); diff --git a/backend/lib/CodeGen/ReachingDefAnalysis.cpp b/backend/lib/CodeGen/ReachingDefAnalysis.cpp new file mode 100644 index 0000000..cac69c4 --- /dev/null +++ b/backend/lib/CodeGen/ReachingDefAnalysis.cpp @@ -0,0 +1,252 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/ReachingDefAnalysis.h" + +#include "rcc/CodeGen/LiveRegUnits.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include <algorithm> +#include <cstddef> +#include <ranges> +#include <unordered_map> +#include <unordered_set> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +using DefinitionSet = ReachingDefAnalysis::DefinitionSet; + +struct ReachingDefState final { + std::unordered_map<RegisterUnitID, DefinitionSet> Registers; + std::unordered_map<FrameIndex, DefinitionSet> FrameObjects; + + friend bool operator==(const ReachingDefState &, const ReachingDefState &) = default; +}; + +void sortAndUnique(DefinitionSet &Definitions, + const std::unordered_map<const MachineInstr *, std::size_t> &Numbers) { + std::ranges::sort(Definitions, [&Numbers](const MachineInstr *Left, const MachineInstr *Right) { + return Numbers.at(Left) < Numbers.at(Right); + }); + Definitions.erase(std::ranges::unique(Definitions).begin(), Definitions.end()); +} + +void mergeDefinitions(DefinitionSet &Destination, const DefinitionSet &Source, + const std::unordered_map<const MachineInstr *, std::size_t> &Numbers) { + Destination.insert(Destination.end(), Source.begin(), Source.end()); + sortAndUnique(Destination, Numbers); +} + +void mergeState(ReachingDefState &Destination, const ReachingDefState &Source, + const std::unordered_map<const MachineInstr *, std::size_t> &Numbers) { + for (const auto &[Unit, Definitions] : Source.Registers) + mergeDefinitions(Destination.Registers[Unit], Definitions, Numbers); + for (const auto &[Index, Definitions] : Source.FrameObjects) + mergeDefinitions(Destination.FrameObjects[Index], Definitions, Numbers); +} + +[[nodiscard]] Expected<void> definePhysicalOperand(ReachingDefState &State, + const MachineOperand &Operand, + const MachineInstr &Instruction, + const TargetDescription &Target) { + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + for (const PhysicalUnitAccess &Access : *Units) + State.Registers[Access.Unit] = {&Instruction}; + return {}; +} + +void defineRegisterMask(ReachingDefState &State, const RegisterMask &Mask, + const MachineInstr &Instruction, const TargetDescription &Target) { + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { + if (!Mask.clobbers(Register.Reg)) + continue; + for (const RegisterUnitLane &Unit : Register.Units) + State.Registers[Unit.Unit] = {&Instruction}; + } +} + +[[nodiscard]] bool instructionMayStore(const MachineInstr &Instruction) noexcept { + return std::ranges::any_of(Instruction.memOperands(), [](const MachineMemOperand *Memory) { + return Memory != nullptr && Memory->isStore(); + }); +} + +[[nodiscard]] std::unordered_set<FrameIndex> storedFrameObjects(const MachineInstr &Instruction) { + std::unordered_set<FrameIndex> Result; + for (const MachineMemOperand *Memory : Instruction.memOperands()) { + if (Memory == nullptr || !Memory->isStore()) + continue; + const std::optional<FrameIndex> Index = Memory->description().Base.frameIndex(); + if (Index) + Result.insert(*Index); + } + return Result; +} + +[[nodiscard]] Expected<void> transferInstruction(ReachingDefState &State, + const MachineInstr &Instruction, + const TargetDescription &Target) { + if (Instruction.isDebugInstr()) + return {}; + + for (const MachineOperand &Operand : Instruction.operands()) { + if (Operand.isRegister()) { + const std::optional<Register> Reg = Operand.registerValue(); + if (!Operand.isDef() || !Reg || Reg->isNoRegister()) + continue; + if (!Reg->isPhysical()) { + return makeUnexpected(ErrorCode::VerificationError, + "reaching-def analysis requires physical registers"); + } + auto Defined = definePhysicalOperand(State, Operand, Instruction, Target); + if (!Defined) + return std::unexpected(Defined.error()); + continue; + } + const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>(); + if (MaskOperand == nullptr) + continue; + if (!MaskOperand->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "reaching-def analysis encountered a null register mask"); + } + defineRegisterMask(State, *MaskOperand->Mask, Instruction, Target); + } + + if (!instructionMayStore(Instruction)) + return {}; + const std::unordered_set<FrameIndex> ExplicitStores = storedFrameObjects(Instruction); + for (const MachineOperand &Operand : Instruction.operands()) { + const auto *Frame = Operand.getIf<FrameIndexOperand>(); + if (Frame == nullptr || (!ExplicitStores.empty() && !ExplicitStores.contains(Frame->Index))) + continue; + State.FrameObjects[Frame->Index] = {&Instruction}; + } + return {}; +} + +[[nodiscard]] Expected<DefinitionSet> +registerDefinitions(const ReachingDefState &State, const MachineOperand &Operand, + const TargetDescription &Target, + const std::unordered_map<const MachineInstr *, std::size_t> &Numbers) { + DefinitionSet Result; + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + for (const PhysicalUnitAccess &Access : *Units) { + const auto Position = State.Registers.find(Access.Unit); + if (Position != State.Registers.end()) + mergeDefinitions(Result, Position->second, Numbers); + } + return Result; +} + +} // namespace + +std::span<const MachineInstr *const> +ReachingDefAnalysis::Result::reachingDefinitions(const MachineOperand &Operand) const noexcept { + const auto Position = OperandDefinitions.find(&Operand); + if (Position == OperandDefinitions.end()) + return {}; + return Position->second; +} + +std::size_t +ReachingDefAnalysis::Result::instructionNumber(const MachineInstr &Instruction) const noexcept { + const auto Position = InstructionNumbers.find(&Instruction); + return Position == InstructionNumbers.end() ? 0 : Position->second; +} + +bool ReachingDefAnalysis::Result::invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept { + return !Preserved.preserves(MachineFunctionAnalysisManager::id<ReachingDefAnalysis>()); +} + +Expected<ReachingDefAnalysis::Result> ReachingDefAnalysis::run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &) { + Result Analysis; + std::size_t Number = 0; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Analysis.InstructionNumbers.emplace(Instruction, Number++); + } + } + + std::unordered_map<const MachineBasicBlock *, ReachingDefState> Inputs; + std::unordered_map<const MachineBasicBlock *, ReachingDefState> Outputs; + bool Changed = false; + do { + Changed = false; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + ReachingDefState Input; + for (MachineBasicBlock *Predecessor : Block->predecessors()) { + const auto Position = Outputs.find(Predecessor); + if (Position != Outputs.end()) + mergeState(Input, Position->second, Analysis.InstructionNumbers); + } + + ReachingDefState Output = Input; + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + auto Transferred = transferInstruction(Output, *Instruction, Target); + if (!Transferred) + return std::unexpected(Transferred.error()); + } + if (Inputs[Block] != Input || Outputs[Block] != Output) { + Inputs[Block] = std::move(Input); + Outputs[Block] = std::move(Output); + Changed = true; + } + } + } while (Changed); + + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + ReachingDefState State = Inputs[Block]; + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + if (Operand.isRegister()) { + const std::optional<Register> Reg = Operand.registerValue(); + if (Operand.isDef() || !Reg || Reg->isNoRegister()) + continue; + if (!Reg->isPhysical()) { + return makeUnexpected(ErrorCode::VerificationError, + "reaching-def analysis requires physical registers"); + } + auto Definitions = + registerDefinitions(State, Operand, Target, Analysis.InstructionNumbers); + if (!Definitions) + return std::unexpected(Definitions.error()); + Analysis.OperandDefinitions.emplace(&Operand, std::move(*Definitions)); + continue; + } + const auto *Frame = Operand.getIf<FrameIndexOperand>(); + if (Frame == nullptr) + continue; + const auto Position = State.FrameObjects.find(Frame->Index); + Analysis.OperandDefinitions.emplace( + &Operand, Position == State.FrameObjects.end() ? DefinitionSet{} : Position->second); + } + auto Transferred = transferInstruction(State, *Instruction, Target); + if (!Transferred) + return std::unexpected(Transferred.error()); + } + } + return Analysis; +} + +} // namespace rcc diff --git a/backend/lib/MIR/CMakeLists.txt b/backend/lib/MIR/CMakeLists.txt index cbdf201..a93917b 100644 --- a/backend/lib/MIR/CMakeLists.txt +++ b/backend/lib/MIR/CMakeLists.txt @@ -3,6 +3,7 @@ set( RCCBackendMIRSources EmbeddedIR.cpp + ReachingDefPrinter.cpp "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MILexer.cpp" "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MIParser.cpp" "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MIRParser.cpp" @@ -16,6 +17,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MIRPrinter.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MIRYamlMapping.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/EmbeddedIR.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/MIR/ReachingDefPrinter.h" ) add_library(RCCBackendMIR ${RCCBackendMIRSources}) @@ -54,6 +56,7 @@ install( rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIR.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/ReachingDefPrinter.cpp" "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MILexer.cpp" "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MILexer.h" "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MIParser.cpp" @@ -64,6 +67,7 @@ rcc_backend_register_format_files( ) rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/EmbeddedIR.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/ReachingDefPrinter.cpp" "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MILexer.cpp" "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MIParser.cpp" "${RCC_BACKEND_SOURCE_DIR}/lib/CodeGen/MIRParser/MIRParser.cpp" diff --git a/backend/lib/MIR/ReachingDefPrinter.cpp b/backend/lib/MIR/ReachingDefPrinter.cpp new file mode 100644 index 0000000..5687590 --- /dev/null +++ b/backend/lib/MIR/ReachingDefPrinter.cpp @@ -0,0 +1,81 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/MIR/ReachingDefPrinter.h" + +#include "rcc/CodeGen/MIRPrinter.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/ReachingDefAnalysis.h" + +#include <iostream> +#include <optional> + +namespace rcc::mir { + +const MachinePassContract &ReachingDefPrinterPass::contract() const noexcept { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = std::string(name()), + .Requires = {MachineFunctionProperty::NoVRegs}, + .Sets = {}, + .Clears = {}, + .RequiredAnalyses = {MachineFunctionAnalysisManager::id<ReachingDefAnalysis>()}, + .VerificationStage = std::nullopt, + }; + Value.DeclaredChanges = {}; + return Value; + }(); + return Contract; +} + +Expected<MachinePassResult> ReachingDefPrinterPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) { + auto ReachingDefinitions = Analyses.getResult<ReachingDefAnalysis>(Function, Target); + if (!ReachingDefinitions) + return std::unexpected(ReachingDefinitions.error()); + auto Context = createMachineFunctionPrintContext(Function); + if (!Context) + return std::unexpected(Context.error()); + + std::cerr << "Reaching definitions for for machine function: " << Function.name() << '\n'; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + std::cerr << "%bb." << Block->denseNumber().value_or(0) << ":\n"; + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + if (Operand.isRegister()) { + const std::optional<Register> Reg = Operand.registerValue(); + if (Operand.isDef() || !Reg || Reg->isNoRegister()) + continue; + } else if (Operand.kind() != MachineOperand::Kind::FrameIndex) { + continue; + } + + auto PrintedOperand = printMachineOperand(Operand, Target, *Context); + if (!PrintedOperand) + return std::unexpected(PrintedOperand.error()); + std::cerr << *PrintedOperand << ":{ "; + for (const MachineInstr *Definition : + (*ReachingDefinitions)->reachingDefinitions(Operand)) { + std::cerr << (*ReachingDefinitions)->instructionNumber(*Definition) << ' '; + } + std::cerr << "}\n"; + } + + auto PrintedInstruction = printMachineInstruction(*Instruction, Target, *Context); + if (!PrintedInstruction) + return std::unexpected(PrintedInstruction.error()); + std::cerr << (*ReachingDefinitions)->instructionNumber(*Instruction) << ": " + << *PrintedInstruction << "\n\n"; + } + } + + MachinePassResult Result; + Result.Preserved = PreservedAnalyses::all(); + return Result; +} + +} // namespace rcc::mir diff --git a/backend/lib/Tooling/PipelineDriver.cpp b/backend/lib/Tooling/PipelineDriver.cpp index b247326..72c7dd2 100644 --- a/backend/lib/Tooling/PipelineDriver.cpp +++ b/backend/lib/Tooling/PipelineDriver.cpp @@ -9,6 +9,7 @@ #include "rcc/CodeGen/MachineOutliner.h" #include "rcc/CodeGen/MachineStripDebug.h" #include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/MIR/ReachingDefPrinter.h" #include "rcc/Target/RISCV/RISCVPipeline.h" #include <algorithm> @@ -121,6 +122,14 @@ struct FunctionRunResult final { return std::nullopt; } +[[nodiscard]] Expected<std::unique_ptr<MachineFunctionPass>> +createNamedMachinePass(std::string_view Name, const riscv::RISCVSubtarget &Subtarget, + riscv::RISCVPipelineOptions Options = {}) { + if (Name == mir::ReachingDefPrinterPass::name()) + return std::make_unique<mir::ReachingDefPrinterPass>(); + return riscv::createCanonicalPipelinePass(Name, Subtarget, Options); +} + [[nodiscard]] Expected<MachineFunctionPassManager::PassList> createPasses(const MachineFunction &Function, const BackendInvocation &Invocation, const riscv::RISCVSubtarget &Subtarget, MachinePassManagerOptions Options) { @@ -156,7 +165,7 @@ createPasses(const MachineFunction &Function, const BackendInvocation &Invocatio const bool UseTargetCopyInstructions = TargetCopyOption != Invocation.TargetOptions.end() && TargetCopyOption->Value == "true"; for (const std::string &Name : Invocation.PassPipeline) { - auto Pass = riscv::createCanonicalPipelinePass( + auto Pass = createNamedMachinePass( Name, Subtarget, riscv::RISCVPipelineOptions{.Optimization = Invocation.Optimization, .UseTargetCopyInstructions = UseTargetCopyInstructions, @@ -183,7 +192,7 @@ createPasses(const MachineFunction &Function, const BackendInvocation &Invocatio if (Name.empty()) return makeUnexpected(ErrorCode::InvalidInvocation, "empty pipeline pass selector"); if (Name != "machine-outliner") { - auto Pass = riscv::createCanonicalPipelinePass(Name, Subtarget); + auto Pass = createNamedMachinePass(Name, Subtarget); if (!Pass) return std::unexpected(Pass.error()); } |