diff options
Diffstat (limited to 'backend/lib/CodeGen/MachineSSAExit.cpp')
| -rw-r--r-- | backend/lib/CodeGen/MachineSSAExit.cpp | 1090 |
1 files changed, 1090 insertions, 0 deletions
diff --git a/backend/lib/CodeGen/MachineSSAExit.cpp b/backend/lib/CodeGen/MachineSSAExit.cpp new file mode 100644 index 0000000..e77bb2a --- /dev/null +++ b/backend/lib/CodeGen/MachineSSAExit.cpp @@ -0,0 +1,1090 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MachineSSAExit.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineFunctionCloner.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <limits> +#include <optional> +#include <ranges> +#include <string> +#include <unordered_map> +#include <unordered_set> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +struct EdgeKey final { + const MachineBasicBlock *From = nullptr; + const MachineBasicBlock *To = nullptr; + + friend bool operator==(const EdgeKey &, const EdgeKey &) noexcept = default; +}; + +struct EdgeKeyHash final { + [[nodiscard]] std::size_t operator()(const EdgeKey &Key) const noexcept { + const std::size_t FromHash = std::hash<const MachineBasicBlock *>{}(Key.From); + const std::size_t ToHash = std::hash<const MachineBasicBlock *>{}(Key.To); + return FromHash ^ (ToHash << 1U); + } +}; + +struct RegisterValue final { + Register Reg; + SubRegIndex SubReg; + RegisterOperandFlags Flags; + std::uint32_t TargetFlags = 0; +}; + +struct PhiIncoming final { + RegisterValue Value; + MachineBasicBlock *Predecessor = nullptr; + bool IsUndef = false; +}; + +struct PhiPlan final { + MachineInstr *Instruction = nullptr; + RegisterValue Destination; + Register FreshIncoming; + std::vector<PhiIncoming> IncomingValues; +}; + +[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) { + Prefix.append(Source.message()); + return Error(Source.code(), std::move(Prefix)); +} + +[[nodiscard]] Expected<void> requireProperties(const MachineFunction &Function, + const MachinePassContract &Contract) { + const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties()); + if (Missing.empty()) + return {}; + return makeUnexpected(ErrorCode::VerificationError, + Contract.Name + " requires properties: " + Missing.toString()); +} + +[[nodiscard]] bool isPhi(const MachineInstr &Instruction, const TargetDescription &Target) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Phi); +} + +[[nodiscard]] bool isMeta(const MachineInstr &Instruction, const TargetDescription &Target) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Meta); +} + +[[nodiscard]] MachineInstr *firstTerminator(MachineBasicBlock &Block, + const TargetDescription &Target) { + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator)) + return Instruction; + } + return nullptr; +} + +[[nodiscard]] MachineInstr *firstCodeAfterPhiRegion(MachineBasicBlock &Block, + const TargetDescription &Target) { + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (!isPhi(*Instruction, Target) && !isMeta(*Instruction, Target)) + return Instruction; + } + return nullptr; +} + +[[nodiscard]] RegisterOperandFlags generatedDefFlags(RegisterOperandFlags Original) noexcept { + RegisterOperandFlags Result; + if (Original.has(RegisterOperandFlag::Undef)) + Result.set(RegisterOperandFlag::Undef); + return Result; +} + +[[nodiscard]] Expected<void> copyDebugLocation(MachineInstrBuilder &Builder, + const MachineInstr *Source) { + if (Source == nullptr || !Source->debugLocation()) + return {}; + return Builder.setDebugLocation(*Source->debugLocation()); +} + +[[nodiscard]] Expected<Register> cloneRegisterConstraints(MachineFunction &Function, + Register Source) { + if (!Source.isVirtual()) { + return makeUnexpected(ErrorCode::VerificationError, + "SSA deconstruction requires a virtual PHI destination"); + } + auto SourceInfo = Function.registerInfo().virtualRegisterInfo(Source); + if (!SourceInfo) + return std::unexpected(SourceInfo.error()); + const VirtualRegisterInfo Info = SourceInfo->get(); + + auto Fresh = Function.registerInfo().createVirtualRegister(); + if (!Fresh) + return std::unexpected(Fresh.error()); + if (Info.Type) { + auto SetType = Function.registerInfo().setType(*Fresh, *Info.Type); + if (!SetType) + return std::unexpected(SetType.error()); + } + if (Info.Bank) { + auto SetBank = Function.registerInfo().setRegisterBank(*Fresh, *Info.Bank); + if (!SetBank) + return std::unexpected(SetBank.error()); + } + if (Info.RegClass) { + auto SetClass = Function.registerInfo().setRegisterClass(*Fresh, *Info.RegClass); + if (!SetClass) + return std::unexpected(SetClass.error()); + } + for (const PhysicalRegister Hint : Info.AllocationHints) { + auto AddedHint = Function.registerInfo().addAllocationHint(*Fresh, Hint); + if (!AddedHint) + return std::unexpected(AddedHint.error()); + } + if (Info.TargetFlags != 0) { + auto SetFlags = Function.registerInfo().setTargetRegisterFlags(*Fresh, Info.TargetFlags); + if (!SetFlags) + return std::unexpected(SetFlags.error()); + } + return *Fresh; +} + +[[nodiscard]] Expected<MachineInstr *> +buildCopy(MachineFunction &Function, const TargetDescription &Target, + const TargetSSAInfo &TargetInfo, MachineBasicBlock &Block, MachineInstr *Before, + RegisterValue Destination, RegisterValue Source, const MachineInstr *DebugSource) { + auto Legality = TargetInfo.validateCopy(Destination.Reg, Destination.SubReg, Source.Reg, + Source.SubReg, Function, Target); + if (!Legality) + return std::unexpected(prefixedError(Legality.error(), "illegal COPY: ")); + + MachineIRBuilder Builder(Function, Target); + auto Point = + Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(opcode(GenericOpcode::COPY)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Destination.Reg, generatedDefFlags(Destination.Flags), + Destination.SubReg, Destination.TargetFlags); + if (!Def) + return std::unexpected(Def.error()); + auto Use = Pending->addUse(Source.Reg, {}, Source.SubReg, Source.TargetFlags); + if (!Use) + return std::unexpected(Use.error()); + auto Debug = copyDebugLocation(*Pending, DebugSource); + if (!Debug) + return std::unexpected(Debug.error()); + return Pending->build(); +} + +[[nodiscard]] Expected<MachineInstr *> +buildImplicitDef(MachineFunction &Function, const TargetDescription &Target, + MachineBasicBlock &Block, MachineInstr *Before, RegisterValue Destination, + const MachineInstr *DebugSource) { + MachineIRBuilder Builder(Function, Target); + auto Point = + Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(opcode(GenericOpcode::IMPLICIT_DEF)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Destination.Reg, generatedDefFlags(Destination.Flags), + Destination.SubReg, Destination.TargetFlags); + if (!Def) + return std::unexpected(Def.error()); + auto Debug = copyDebugLocation(*Pending, DebugSource); + if (!Debug) + return std::unexpected(Debug.error()); + return Pending->build(); +} + +[[nodiscard]] bool isImplicitlyUndef(const MachineFunction &Function, + const MachineOperand &Operand) { + if (Operand.registerFlags().has(RegisterOperandFlag::Undef)) + return true; + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || Reg->isNoRegister()) + return true; + if (!Reg->isVirtual()) + return false; + const MachineOperand *Definition = Function.registerInfo().getUniqueVRegDef(*Reg); + if (Definition == nullptr || Definition->parent() == nullptr) + return false; + if (Definition->subReg().value() != 0 && Definition->subReg() != Operand.subReg()) + return false; + const Opcode DefinitionOpcode = Definition->parent()->opcode(); + return DefinitionOpcode == opcode(GenericOpcode::IMPLICIT_DEF) || + DefinitionOpcode == opcode(GenericOpcode::G_IMPLICIT_DEF) || + Definition->registerFlags().has(RegisterOperandFlag::Undef); +} + +[[nodiscard]] Expected<void> validatePhiValue(const MachineFunction &Function, + const TargetDescription &Target, + const MachineOperand &Destination, + const MachineOperand &Source) { + const Register *DestinationReg = Destination.getIf<Register>(); + const Register *SourceReg = Source.getIf<Register>(); + if (DestinationReg == nullptr || SourceReg == nullptr) + return makeUnexpected(ErrorCode::VerificationError, "PHI operands must name registers"); + if (SourceReg->isNoRegister()) + return {}; + + if (DestinationReg->isVirtual() && SourceReg->isVirtual()) { + auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(*DestinationReg); + if (!DestinationInfo) + return std::unexpected(DestinationInfo.error()); + auto SourceInfo = Function.registerInfo().virtualRegisterInfo(*SourceReg); + if (!SourceInfo) + return std::unexpected(SourceInfo.error()); + if (DestinationInfo->get().Type && SourceInfo->get().Type && + DestinationInfo->get().Type != SourceInfo->get().Type) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI destination and incoming value types do not match"); + } + } + return Target.validateTieCompatibility(Destination, Source, Function.registerInfo()); +} + +[[nodiscard]] Expected<std::vector<PhiPlan>> collectPhiPlans(MachineBasicBlock &Block, + MachineFunction &Function, + const TargetDescription &Target) { + std::vector<PhiPlan> Plans; + bool SawCode = false; + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI elimination encountered an unknown opcode"); + } + if (Instruction->opcode() == opcode(GenericOpcode::G_PHI)) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI elimination requires G_PHI to be selected to PHI"); + } + if (!Descriptor->Flags.has(InstructionFlag::Phi)) { + SawCode |= !Descriptor->Flags.has(InstructionFlag::Meta); + continue; + } + if (SawCode) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI instruction appears after the leading PHI/meta region"); + } + if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI must contain a destination and incoming value/block pairs"); + } + + MachineOperand *DestinationOperand = Instruction->operandAt(0); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + if (Destination == nullptr || !Destination->isVirtual() || !DestinationOperand->isDef() || + DestinationOperand->isUse() || DestinationOperand->isImplicit()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI destination must be an explicit virtual-register definition"); + } + + PhiPlan Plan; + Plan.Instruction = Instruction; + Plan.Destination = + RegisterValue{*Destination, DestinationOperand->subReg(), + DestinationOperand->registerFlags(), DestinationOperand->targetFlags()}; + std::unordered_set<MachineBasicBlock *> SeenPredecessors; + for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) { + MachineOperand *SourceOperand = Instruction->operandAt(Index); + MachineOperand *BlockOperand = Instruction->operandAt(Index + 1U); + const Register *Source = + SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>(); + const BasicBlockOperand *IncomingBlock = + BlockOperand == nullptr ? nullptr : BlockOperand->getIf<BasicBlockOperand>(); + if (Source == nullptr || SourceOperand == nullptr || !SourceOperand->isUse() || + SourceOperand->isDef() || SourceOperand->isImplicit() || IncomingBlock == nullptr || + IncomingBlock->Block == nullptr || BlockOperand->isImplicit()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming operands must be explicit register/block pairs"); + } + if (std::ranges::find(Block.predecessors(), IncomingBlock->Block) == + Block.predecessors().end()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming block is not a CFG predecessor"); + } + if (!SeenPredecessors.insert(IncomingBlock->Block).second) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI contains duplicate incoming predecessors"); + } + auto Compatibility = validatePhiValue(Function, Target, *DestinationOperand, *SourceOperand); + if (!Compatibility) + return std::unexpected(Compatibility.error()); + Plan.IncomingValues.push_back( + PhiIncoming{RegisterValue{*Source, SourceOperand->subReg(), + SourceOperand->registerFlags(), SourceOperand->targetFlags()}, + IncomingBlock->Block, isImplicitlyUndef(Function, *SourceOperand)}); + } + if (SeenPredecessors.size() != Block.predecessors().size()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming blocks do not exactly cover CFG predecessors"); + } + Plans.push_back(std::move(Plan)); + } + return Plans; +} + +[[nodiscard]] Expected<void> copyLiveIns(const MachineBasicBlock &Source, + MachineBasicBlock &Destination) { + for (const MachineBasicBlockLiveIn &LiveIn : Source.liveIns()) { + auto Added = Destination.addLiveIn(LiveIn.PhysReg, LiveIn.Lanes); + if (!Added) + return std::unexpected(Added.error()); + } + return {}; +} + +[[nodiscard]] Expected<void> ensurePhysicalLiveIn(MachineBasicBlock &Block, PhysicalRegister Reg, + const TargetDescription &Target) { + const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Reg); + if (Description == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming value references an unknown physical register"); + } + LaneMask Required; + for (const RegisterUnitLane &Unit : Description->Units) + Required = Required | Unit.Lanes; + if (Required.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming physical register has no addressable lanes"); + } + + for (const MachineBasicBlockLiveIn &LiveIn : Block.liveIns()) { + if (LiveIn.PhysReg != Reg) + continue; + if (LiveIn.Lanes.contains(Required)) + return {}; + const LaneMask Combined = LiveIn.Lanes | Required; + auto Removed = Block.removeLiveIn(Reg); + if (!Removed) + return std::unexpected(Removed.error()); + return Block.addLiveIn(Reg, Combined); + } + return Block.addLiveIn(Reg, Required); +} + +[[nodiscard]] Expected<MachineBasicBlock *> +placePhiCopiesOnEdge(MachineFunction &Function, const TargetDescription &Target, + const TargetSSAInfo &TargetInfo, MachineBasicBlock &From, + MachineBasicBlock &To, + std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> &Cache, + MachinePassResult &PassResult) { + if (From.successors().size() <= 1) + return &From; + + const EdgeKey Key{&From, &To}; + if (const auto Existing = Cache.find(Key); Existing != Cache.end()) + return Existing->second; + if (std::ranges::none_of(From.successors(), [&To](const MachineSuccessor &Successor) { + return Successor.Block == &To; + })) { + return makeUnexpected(ErrorCode::VerificationError, + "PHI incoming predecessor has no edge to its successor"); + } + + auto SourceFallthrough = TargetInfo.isFallthroughEdge(From, To, Function, Target); + if (!SourceFallthrough) + return std::unexpected(SourceFallthrough.error()); + + MachineBasicBlock *LayoutPredecessor = To.previous(); + if (LayoutPredecessor != nullptr && LayoutPredecessor != &From) { + auto OtherFallthrough = TargetInfo.isFallthroughEdge(*LayoutPredecessor, To, Function, Target); + if (!OtherFallthrough) + return std::unexpected(OtherFallthrough.error()); + if (*OtherFallthrough) { + auto Branch = TargetInfo.insertUnconditionalBranch(*LayoutPredecessor, To, Function, Target); + if (!Branch) + return std::unexpected(Branch.error()); + PassResult.Changed = true; + PassResult.Changes.add(MachinePassChange::Instructions); + } + } + + auto EdgeBlockResult = Function.createBasicBlock(); + if (!EdgeBlockResult) + return std::unexpected(EdgeBlockResult.error()); + MachineBasicBlock *EdgeBlock = *EdgeBlockResult; + auto Inserted = Function.insertBlockBefore(To, *EdgeBlock); + if (!Inserted) + return std::unexpected(Inserted.error()); + + auto Rewritten = TargetInfo.rewriteBranchTarget(From, To, *EdgeBlock, Function, Target); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + if (!*Rewritten && !*SourceFallthrough) { + return makeUnexpected(ErrorCode::Unsupported, + "PHI elimination cannot split an indirect or unmodeled CFG edge"); + } + + auto Split = Function.cfgUpdater().splitEdge(From, To, *EdgeBlock); + if (!Split) + return std::unexpected(Split.error()); + auto LiveIns = copyLiveIns(To, *EdgeBlock); + if (!LiveIns) + return std::unexpected(LiveIns.error()); + auto Branch = TargetInfo.insertUnconditionalBranch(*EdgeBlock, To, Function, Target); + if (!Branch) + return std::unexpected(Branch.error()); + + Cache.emplace(Key, EdgeBlock); + PassResult.Changed = true; + PassResult.Changes.add(MachinePassChange::CFG); + PassResult.Changes.add(MachinePassChange::BlockLayout); + PassResult.Changes.add(MachinePassChange::Instructions); + if (*Rewritten) + PassResult.Changes.add(MachinePassChange::Operands); + return EdgeBlock; +} + +[[nodiscard]] Expected<bool> clearStaleLivenessFlags(MachineFunction &Function) { + bool Changed = false; + for (MachineInstr *Instruction : Function.allInstructions()) { + if (Instruction->parent() == nullptr) + continue; + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isRegister()) + continue; + RegisterOperandFlags Flags = Operand->registerFlags(); + const bool HadStaleFlag = + Flags.has(RegisterOperandFlag::Kill) || Flags.has(RegisterOperandFlag::Dead); + if (!HadStaleFlag) + continue; + Flags.clear(RegisterOperandFlag::Kill); + Flags.clear(RegisterOperandFlag::Dead); + auto Updated = Operand->setRegisterFlags(Flags); + if (!Updated) + return std::unexpected(Updated.error()); + Changed = true; + } + } + return Changed; +} + +[[nodiscard]] Expected<SubRegIndex> subRegIndex(const MachineOperand &Operand, + const TargetDescription &Target) { + std::uint64_t Value = 0; + if (const auto *Immediate = Operand.getIf<std::int64_t>(); Immediate != nullptr) { + if (*Immediate <= 0) + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo requires a positive subregister index"); + Value = static_cast<std::uint64_t>(*Immediate); + } else if (const auto *WideImmediate = Operand.getIf<IntegerImmediateOperand>(); + WideImmediate != nullptr) { + if (WideImmediate->Value.isNegative() || WideImmediate->Value.bitWidth() > 64) + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo index does not fit an unsigned integer"); + Value = WideImmediate->Value.words().front(); + } else { + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo is missing its immediate index"); + } + if (Value == 0 || Value > std::numeric_limits<std::uint32_t>::max()) { + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo index is outside the supported range"); + } + const SubRegIndex Result = SubRegIndex::fromValue(static_cast<std::uint32_t>(Value)); + if (Target.registers().subRegIndex(Result) == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "subregister pseudo references an unknown target index"); + } + return Result; +} + +[[nodiscard]] Expected<SubRegIndex> composeSubReg(SubRegIndex Outer, SubRegIndex Inner, + const TargetDescription &Target) { + if (Outer.value() == 0) + return Inner; + if (Inner.value() == 0) + return Outer; + const auto Composed = Target.registers().composeSubRegIndices(Outer, Inner); + if (!Composed) { + return makeUnexpected(ErrorCode::Unsupported, + "target cannot compose the requested subregister indices"); + } + return *Composed; +} + +[[nodiscard]] Expected<void> removeInstruction(MachineInstr &Instruction) { + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "rewritten instruction is not linked"); + return Block->removeInstruction(Instruction); +} + +[[nodiscard]] Expected<void> expandRegSequence(MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &Target, + const TargetSSAInfo &TargetInfo) { + if (Instruction.operandCount() < 3 || (Instruction.operandCount() - 1U) % 2U != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "REG_SEQUENCE requires a destination and source/subregister pairs"); + } + MachineOperand *DestinationOperand = Instruction.operandAt(0); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + if (Destination == nullptr || Destination->isNoRegister() || !DestinationOperand->isDef()) { + return makeUnexpected(ErrorCode::VerificationError, + "REG_SEQUENCE requires a register destination definition"); + } + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "REG_SEQUENCE is not linked to a block"); + + RegisterValue DestinationValue{*Destination, DestinationOperand->subReg(), + DestinationOperand->registerFlags(), + DestinationOperand->targetFlags()}; + auto Initial = + buildImplicitDef(Function, Target, *Block, &Instruction, DestinationValue, &Instruction); + if (!Initial) + return std::unexpected(Initial.error()); + + for (std::size_t Index = 1; Index < Instruction.operandCount(); Index += 2U) { + MachineOperand *SourceOperand = Instruction.operandAt(Index); + MachineOperand *IndexOperand = Instruction.operandAt(Index + 1U); + const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>(); + if (Source == nullptr || SourceOperand == nullptr || !SourceOperand->isUse() || + IndexOperand == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "REG_SEQUENCE contains a malformed source/subregister pair"); + } + auto InnerSubReg = subRegIndex(*IndexOperand, Target); + if (!InnerSubReg) + return std::unexpected(InnerSubReg.error()); + auto DestinationSubReg = composeSubReg(DestinationOperand->subReg(), *InnerSubReg, Target); + if (!DestinationSubReg) + return std::unexpected(DestinationSubReg.error()); + + RegisterValue LaneDestination{ + *Destination, *DestinationSubReg, {}, DestinationOperand->targetFlags()}; + if (isImplicitlyUndef(Function, *SourceOperand)) { + auto Undef = + buildImplicitDef(Function, Target, *Block, &Instruction, LaneDestination, &Instruction); + if (!Undef) + return std::unexpected(Undef.error()); + continue; + } + RegisterValue SourceValue{*Source, SourceOperand->subReg(), SourceOperand->registerFlags(), + SourceOperand->targetFlags()}; + auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, LaneDestination, + SourceValue, &Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + } + return removeInstruction(Instruction); +} + +[[nodiscard]] Expected<void> expandInsertSubreg(MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target, + const TargetSSAInfo &TargetInfo) { + if (Instruction.operandCount() != 4) { + return makeUnexpected(ErrorCode::VerificationError, + "INSERT_SUBREG requires destination, base, inserted value, and index"); + } + MachineOperand *DestinationOperand = Instruction.operandAt(0); + MachineOperand *BaseOperand = Instruction.operandAt(1); + MachineOperand *InsertedOperand = Instruction.operandAt(2); + MachineOperand *IndexOperand = Instruction.operandAt(3); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + const Register *Base = BaseOperand == nullptr ? nullptr : BaseOperand->getIf<Register>(); + const Register *Inserted = + InsertedOperand == nullptr ? nullptr : InsertedOperand->getIf<Register>(); + if (Destination == nullptr || Base == nullptr || Inserted == nullptr || + Destination->isNoRegister() || DestinationOperand == nullptr || + !DestinationOperand->isDef() || BaseOperand == nullptr || !BaseOperand->isUse() || + InsertedOperand == nullptr || !InsertedOperand->isUse() || IndexOperand == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "INSERT_SUBREG contains malformed register operands"); + } + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "INSERT_SUBREG is not linked to a block"); + + RegisterValue DestinationValue{*Destination, DestinationOperand->subReg(), + DestinationOperand->registerFlags(), + DestinationOperand->targetFlags()}; + if (isImplicitlyUndef(Function, *BaseOperand)) { + auto Undef = + buildImplicitDef(Function, Target, *Block, &Instruction, DestinationValue, &Instruction); + if (!Undef) + return std::unexpected(Undef.error()); + } else if (*Destination != *Base || DestinationOperand->subReg() != BaseOperand->subReg()) { + RegisterValue BaseValue{*Base, BaseOperand->subReg(), BaseOperand->registerFlags(), + BaseOperand->targetFlags()}; + auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, DestinationValue, + BaseValue, &Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + } + + auto InnerSubReg = subRegIndex(*IndexOperand, Target); + if (!InnerSubReg) + return std::unexpected(InnerSubReg.error()); + auto DestinationSubReg = composeSubReg(DestinationOperand->subReg(), *InnerSubReg, Target); + if (!DestinationSubReg) + return std::unexpected(DestinationSubReg.error()); + RegisterValue LaneDestination{ + *Destination, *DestinationSubReg, {}, DestinationOperand->targetFlags()}; + if (isImplicitlyUndef(Function, *InsertedOperand)) { + auto Undef = + buildImplicitDef(Function, Target, *Block, &Instruction, LaneDestination, &Instruction); + if (!Undef) + return std::unexpected(Undef.error()); + } else { + RegisterValue InsertedValue{*Inserted, InsertedOperand->subReg(), + InsertedOperand->registerFlags(), InsertedOperand->targetFlags()}; + auto Copy = buildCopy(Function, Target, TargetInfo, *Block, &Instruction, LaneDestination, + InsertedValue, &Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + } + return removeInstruction(Instruction); +} + +[[nodiscard]] Expected<void> swapRegisterUses(MachineOperand &Left, MachineOperand &Right) { + const std::optional<Register> LeftReg = Left.registerValue(); + const std::optional<Register> RightReg = Right.registerValue(); + if (!LeftReg || !RightReg || !Left.isUse() || Left.isDef() || !Right.isUse() || Right.isDef()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "commutation requires two pure register uses"); + } + const SubRegIndex LeftSubReg = Left.subReg(); + const SubRegIndex RightSubReg = Right.subReg(); + const RegisterOperandFlags LeftFlags = Left.registerFlags(); + const RegisterOperandFlags RightFlags = Right.registerFlags(); + const std::uint32_t LeftTargetFlags = Left.targetFlags(); + const std::uint32_t RightTargetFlags = Right.targetFlags(); + + auto SetLeftReg = Left.setRegister(*RightReg); + if (!SetLeftReg) + return std::unexpected(SetLeftReg.error()); + auto SetRightReg = Right.setRegister(*LeftReg); + if (!SetRightReg) + return std::unexpected(SetRightReg.error()); + auto SetLeftSubReg = Left.setSubReg(RightSubReg); + if (!SetLeftSubReg) + return std::unexpected(SetLeftSubReg.error()); + auto SetRightSubReg = Right.setSubReg(LeftSubReg); + if (!SetRightSubReg) + return std::unexpected(SetRightSubReg.error()); + auto SetLeftFlags = Left.setRegisterFlags(RightFlags); + if (!SetLeftFlags) + return std::unexpected(SetLeftFlags.error()); + auto SetRightFlags = Right.setRegisterFlags(LeftFlags); + if (!SetRightFlags) + return std::unexpected(SetRightFlags.error()); + Left.setTargetFlags(RightTargetFlags); + Right.setTargetFlags(LeftTargetFlags); + return {}; +} + +[[nodiscard]] Expected<bool> tryCommute(MachineInstr &Instruction, std::size_t TiedUseIndex, + Register Destination, const TargetDescription &Target, + MachineFunction &Function) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); + if (Descriptor == nullptr || !Descriptor->Flags.has(InstructionFlag::Commutable)) + return false; + MachineOperand *TiedUse = Instruction.operandAt(TiedUseIndex); + if (TiedUse == nullptr) + return makeUnexpected(ErrorCode::InternalError, "tied use disappeared during commutation"); + + for (std::size_t Index = 0; Index < Instruction.operandCount(); ++Index) { + if (Index == TiedUseIndex) + continue; + MachineOperand *Candidate = Instruction.operandAt(Index); + if (Candidate == nullptr || Candidate->isImplicit() || !Candidate->isUse() || + Candidate->isDef() || Candidate->tiedOperandIndex() || + Candidate->registerValue() != Destination || isImplicitlyUndef(Function, *Candidate)) { + continue; + } + auto Swapped = swapRegisterUses(*TiedUse, *Candidate); + if (!Swapped) + return std::unexpected(Swapped.error()); + auto Validation = Target.validateInstruction(Instruction, Function.registerInfo()); + if (Validation) + return true; + auto Restored = swapRegisterUses(*TiedUse, *Candidate); + if (!Restored) + return std::unexpected(Restored.error()); + } + return false; +} + +[[nodiscard]] Expected<void> rewriteUndefTie(MachineOperand &Use, const MachineOperand &Def) { + const std::optional<Register> Destination = Def.registerValue(); + if (!Destination) + return makeUnexpected(ErrorCode::VerificationError, "tied definition is not a register"); + auto SetRegister = Use.setRegister(*Destination); + if (!SetRegister) + return std::unexpected(SetRegister.error()); + auto SetSubReg = Use.setSubReg(Def.subReg()); + if (!SetSubReg) + return std::unexpected(SetSubReg.error()); + RegisterOperandFlags Flags = Use.registerFlags(); + Flags.set(RegisterOperandFlag::Undef); + Flags.clear(RegisterOperandFlag::Kill); + return Use.setRegisterFlags(Flags); +} + +[[nodiscard]] Expected<void> verifyNoStageTenPseudos(const MachineFunction &Function, + const TargetDescription &Target) { + for (const MachineInstr *Instruction : Function.allInstructions()) { + if (Instruction->parent() == nullptr) + continue; + if (Instruction->opcode() == opcode(GenericOpcode::G_PHI) || + Instruction->opcode() == opcode(GenericOpcode::PHI) || + Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE) || + Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) { + return makeUnexpected(ErrorCode::VerificationError, + "SSA exit left a Stage 10 pseudo instruction in MachineIR"); + } + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "SSA exit produced an instruction with no descriptor"); + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + const MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isUse()) + continue; + const std::optional<std::size_t> Tie = Operand->tiedOperandIndex(); + if (!Tie) + continue; + const MachineOperand *Def = Instruction->operandAt(Tie.value()); + if (Def == nullptr || Def->registerValue() != Operand->registerValue()) { + return makeUnexpected(ErrorCode::VerificationError, + "two-address rewrite left an unequal tied register"); + } + } + } + return {}; +} + +} // namespace + +const MachinePassContract &PHIEliminationPass::contract() const noexcept { + static const MachinePassContract Contract{ + .Name = "PHIElimination", + .Requires = {MachineFunctionProperty::IsSSA, MachineFunctionProperty::Selected, + MachineFunctionProperty::RegBankSelected}, + .Sets = {MachineFunctionProperty::NoPHIs}, + .Clears = {MachineFunctionProperty::IsSSA}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::SSAEliminated, + }; + return Contract; +} + +Expected<MachinePassResult> PHIEliminationPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + if (Info == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "PHI elimination has no target SSA behavior interface"); + } + auto Required = requireProperties(Function, contract()); + if (!Required) + return std::unexpected(Required.error()); + + auto Trial = cloneMachineFunction( + Function, Target, + MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); + if (!Trial) { + return std::unexpected( + prefixedError(Trial.error(), "PHI-elimination transaction setup failed: ")); + } + MachineAnalysisManager TrialAnalyses; + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses); + if (!TrialResult) + return std::unexpected(TrialResult.error()); + + auto Result = runImplementation(Function, Target, Analyses); + if (!Result) { + return std::unexpected(prefixedError( + Result.error(), "PHI elimination diverged after a successful transaction preflight: ")); + } + return Result; +} + +Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &) { + MachinePassResult Result; + std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> SplitEdges; + const std::vector<MachineBasicBlock *> Blocks(Function.allBlocks().begin(), + Function.allBlocks().end()); + + for (MachineBasicBlock *Block : Blocks) { + auto Plans = collectPhiPlans(*Block, Function, Target); + if (!Plans) + return std::unexpected(Plans.error()); + if (Plans->empty()) + continue; + + for (PhiPlan &Plan : *Plans) { + auto Fresh = cloneRegisterConstraints(Function, Plan.Destination.Reg); + if (!Fresh) + return std::unexpected(Fresh.error()); + Plan.FreshIncoming = *Fresh; + } + + for (PhiPlan &Plan : *Plans) { + for (const PhiIncoming &Incoming : Plan.IncomingValues) { + auto EdgeBlock = placePhiCopiesOnEdge(Function, Target, *Info, *Incoming.Predecessor, + *Block, SplitEdges, Result); + if (!EdgeBlock) + return std::unexpected(EdgeBlock.error()); + if (*EdgeBlock != Incoming.Predecessor) { + const std::optional<PhysicalRegister> Physical = Incoming.Value.Reg.physicalRegister(); + if (Physical) { + auto LiveIn = ensurePhysicalLiveIn(**EdgeBlock, *Physical, Target); + if (!LiveIn) + return std::unexpected(LiveIn.error()); + } + } + MachineInstr *Terminator = firstTerminator(**EdgeBlock, Target); + RegisterValue Fresh{Plan.FreshIncoming, Plan.Destination.SubReg, Plan.Destination.Flags, + Plan.Destination.TargetFlags}; + Expected<MachineInstr *> Transfer = + Incoming.IsUndef ? buildImplicitDef(Function, Target, **EdgeBlock, Terminator, Fresh, + Plan.Instruction) + : buildCopy(Function, Target, *Info, **EdgeBlock, Terminator, Fresh, + Incoming.Value, Plan.Instruction); + if (!Transfer) + return std::unexpected(Transfer.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + } + } + + MachineInstr *InsertionPoint = firstCodeAfterPhiRegion(*Block, Target); + for (PhiPlan &Plan : *Plans) { + RegisterValue Fresh{ + Plan.FreshIncoming, Plan.Destination.SubReg, {}, Plan.Destination.TargetFlags}; + auto Copy = buildCopy(Function, Target, *Info, *Block, InsertionPoint, Plan.Destination, + Fresh, Plan.Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + } + + for (PhiPlan &Plan : *Plans) { + auto Removed = Block->removeInstruction(*Plan.Instruction); + if (!Removed) + return std::unexpected(Removed.error()); + } + Result.Changes.add(MachinePassChange::Registers); + } + + if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) { + auto Cleared = clearStaleLivenessFlags(Function); + if (!Cleared) + return std::unexpected(Cleared.error()); + if (*Cleared) + Result.Changes.add(MachinePassChange::Operands); + } + Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); + return Result; +} + +const MachinePassContract &TwoAddressRewritePass::contract() const noexcept { + static const MachinePassContract Contract{ + .Name = "TwoAddressRewrite", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs}, + .Sets = {MachineFunctionProperty::TiedOpsRewritten}, + .Clears = {MachineFunctionProperty::IsSSA}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::TiedOpsRewritten, + }; + return Contract; +} + +Expected<MachinePassResult> TwoAddressRewritePass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + if (Info == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "two-address rewrite has no target SSA behavior interface"); + } + auto Required = requireProperties(Function, contract()); + if (!Required) + return std::unexpected(Required.error()); + + auto Trial = cloneMachineFunction( + Function, Target, + MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); + if (!Trial) { + return std::unexpected(prefixedError(Trial.error(), "two-address transaction setup failed: ")); + } + MachineAnalysisManager TrialAnalyses; + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses); + if (!TrialResult) + return std::unexpected(TrialResult.error()); + + auto Result = runImplementation(Function, Target, Analyses); + if (!Result) { + return std::unexpected(prefixedError( + Result.error(), "two-address rewrite diverged after a successful transaction preflight: ")); + } + return Result; +} + +Expected<MachinePassResult> +TwoAddressRewritePass::runImplementation(MachineFunction &Function, const TargetDescription &Target, + MachineAnalysisManager &) { + MachinePassResult Result; + const std::vector<MachineInstr *> Instructions(Function.allInstructions().begin(), + Function.allInstructions().end()); + for (MachineInstr *Instruction : Instructions) { + if (Instruction->parent() == nullptr) + continue; + if (Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE)) { + auto Expanded = expandRegSequence(*Instruction, Function, Target, *Info); + if (!Expanded) + return std::unexpected(Expanded.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + continue; + } + if (Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) { + auto Expanded = expandInsertSubreg(*Instruction, Function, Target, *Info); + if (!Expanded) + return std::unexpected(Expanded.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + continue; + } + + std::size_t RewriteAttempts = 0; + bool Restart = true; + while (Restart && Instruction->parent() != nullptr) { + Restart = false; + if (++RewriteAttempts > Instruction->operandCount() * 2U + 8U) { + return makeUnexpected(ErrorCode::InternalError, + "two-address target conversion did not make progress"); + } + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "two-address rewrite encountered an unknown opcode"); + } + + for (std::size_t UseIndex = 0; UseIndex < Instruction->operandCount(); ++UseIndex) { + MachineOperand *Use = Instruction->operandAt(UseIndex); + if (Use == nullptr || !Use->isUse()) + continue; + const std::optional<std::size_t> TiedDefIndex = Use->tiedOperandIndex(); + if (!TiedDefIndex) + continue; + const std::size_t DefIndex = TiedDefIndex.value(); + MachineOperand *Def = Instruction->operandAt(DefIndex); + if (Def == nullptr || !Def->isDef()) { + return makeUnexpected(ErrorCode::VerificationError, + "tied use does not reference a definition"); + } + const std::optional<Register> DefReg = Def->registerValue(); + const std::optional<Register> UseReg = Use->registerValue(); + if (!DefReg || !UseReg || DefReg->isNoRegister()) { + return makeUnexpected(ErrorCode::Unsupported, + "two-address rewrite requires register ties"); + } + if (*DefReg == *UseReg) + continue; + + if (isImplicitlyUndef(Function, *Use)) { + auto Rewritten = rewriteUndefTie(*Use, *Def); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Operands); + continue; + } + + auto Commuted = tryCommute(*Instruction, UseIndex, *DefReg, Target, Function); + if (!Commuted) + return std::unexpected(Commuted.error()); + if (*Commuted) { + Result.Changed = true; + Result.Changes.add(MachinePassChange::Operands); + continue; + } + + auto Converted = + Info->tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target); + if (!Converted) + return std::unexpected(Converted.error()); + if (*Converted) { + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + Result.Changes.add(MachinePassChange::Operands); + Result.Changes.add(MachinePassChange::Registers); + Restart = true; + break; + } + + MachineBasicBlock *Block = Instruction->parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "two-address instruction disappeared before COPY insertion"); + RegisterValue Destination{*DefReg, Def->subReg(), Def->registerFlags(), Def->targetFlags()}; + RegisterValue Source{*UseReg, Use->subReg(), Use->registerFlags(), Use->targetFlags()}; + auto Copy = buildCopy(Function, Target, *Info, *Block, Instruction, Destination, Source, + Instruction); + if (!Copy) + return std::unexpected(Copy.error()); + auto SetRegister = Use->setRegister(*DefReg); + if (!SetRegister) + return std::unexpected(SetRegister.error()); + auto SetSubReg = Use->setSubReg(Def->subReg()); + if (!SetSubReg) + return std::unexpected(SetSubReg.error()); + RegisterOperandFlags Flags = Use->registerFlags(); + Flags.clear(RegisterOperandFlag::Kill); + auto SetFlags = Use->setRegisterFlags(Flags); + if (!SetFlags) + return std::unexpected(SetFlags.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Instructions); + Result.Changes.add(MachinePassChange::Operands); + } + } + } + + auto FinalState = verifyNoStageTenPseudos(Function, Target); + if (!FinalState) + return std::unexpected(FinalState.error()); + if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) { + auto Cleared = clearStaleLivenessFlags(Function); + if (!Cleared) + return std::unexpected(Cleared.error()); + if (*Cleared) + Result.Changes.add(MachinePassChange::Operands); + } + Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); + return Result; +} + +} // namespace rcc |