diff options
Diffstat (limited to 'backend/lib/CodeGen/TwoAddressInstructionPass.cpp')
| -rw-r--r-- | backend/lib/CodeGen/TwoAddressInstructionPass.cpp | 661 |
1 files changed, 661 insertions, 0 deletions
diff --git a/backend/lib/CodeGen/TwoAddressInstructionPass.cpp b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp new file mode 100644 index 0000000..1959b90 --- /dev/null +++ b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp @@ -0,0 +1,661 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/TwoAddressInstructionPass.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineFunctionCloner.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetInstrInfo.h" + +#include <cstddef> +#include <cstdint> +#include <limits> +#include <optional> +#include <string> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +struct RegisterValue final { + Register Reg; + SubRegIndex SubReg; + RegisterOperandFlags Flags; + std::uint32_t TargetFlags = 0; +}; + +[[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]] 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<MachineInstr *> +buildCopy(MachineFunction &Function, const TargetDescription &Target, + const TargetInstrInfo &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> repairTrackedLiveness(MachineFunction &Function, + const TargetDescription &Target, + MachinePassResult &Result) { + if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) { + return {}; + } + auto Rebuilt = rebuildMachineLiveness(Function, Target); + if (!Rebuilt) + return std::unexpected(Rebuilt.error()); + if (*Rebuilt) + Result.Changes.add(MachinePassChange::Operands); + return {}; +} + +[[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 TargetInstrInfo &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 TargetInstrInfo &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 &TwoAddressInstructionPass::contract() const noexcept { + static const MachinePassContract Contract{ + .Name = "twoaddressinstruction", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs}, + .Sets = {MachineFunctionProperty::TiedOpsRewritten}, + .Clears = {MachineFunctionProperty::IsSSA}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::TiedOpsRewritten, + }; + return Contract; +} + +Expected<MachinePassResult> TwoAddressInstructionPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + 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: ")); + } + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); + if (!TrialResult) + return std::unexpected(TrialResult.error()); + + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); + if (!Result) { + return std::unexpected(prefixedError( + Result.error(), "two-address rewrite diverged after a successful transaction preflight: ")); + } + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); + return Result; +} + +Expected<MachinePassResult> TwoAddressInstructionPass::runImplementation( + MachineFunction &Function, const TargetDescription &Target, MachineActionReplay &Actions) { + 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 Accepted = Actions.request("expand-reg-sequence", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::VerificationError, + "required REG_SEQUENCE expansion action was rejected"); + 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 Accepted = Actions.request("expand-insert-subreg", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::VerificationError, + "required INSERT_SUBREG expansion action was rejected"); + 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 Accepted = Actions.request("rewrite-undef-tie", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return makeUnexpected(ErrorCode::VerificationError, + "required undef tie rewrite action was rejected"); + auto Rewritten = rewriteUndefTie(*Use, *Def); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + Result.Changed = true; + Result.Changes.add(MachinePassChange::Operands); + continue; + } + + auto AllowCommute = + Actions.request("commute-tied-operands", Function, Instruction->stableID()); + if (!AllowCommute) + return std::unexpected(AllowCommute.error()); + if (*AllowCommute) { + 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 AllowConversion = + Actions.request("convert-three-address", Function, Instruction->stableID()); + if (!AllowConversion) + return std::unexpected(AllowConversion.error()); + if (*AllowConversion) { + 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; + } + } + + auto AllowCopy = Actions.request("insert-tied-copy", Function, Instruction->stableID()); + if (!AllowCopy) + return std::unexpected(AllowCopy.error()); + if (!*AllowCopy) + return makeUnexpected(ErrorCode::VerificationError, + "required tied COPY insertion action was rejected"); + 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 Repaired = repairTrackedLiveness(Function, Target, Result); + if (!Repaired) + return std::unexpected( + prefixedError(Repaired.error(), "two-address liveness repair failed: ")); + } + Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); + return Result; +} + +} // namespace rcc |