diff options
Diffstat (limited to 'backend/lib/CodeGen')
| -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 |
4 files changed, 367 insertions, 41 deletions
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 |