From b85a348ab7bdd878fd975121fc2501625eceec95 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Fri, 14 Aug 2026 22:37:46 +0800 Subject: [GlobalISel] Legalize G_ABS --- .../lib/CodeGen/GlobalISel/GISelValueTracking.cpp | 29 ++++--- backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp | 99 ++++++++++++++++++++++ backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp | 4 + backend/lib/CodeGen/GlobalISel/Utils.cpp | 85 +++++++++++++++++++ backend/lib/CodeGen/MachineIRBuilder.cpp | 5 ++ backend/lib/CodeGen/MachineOperand.cpp | 9 ++ 6 files changed, 221 insertions(+), 10 deletions(-) (limited to 'backend/lib/CodeGen') diff --git a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp index fe694ab..f6a0a87 100644 --- a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp +++ b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp @@ -3,6 +3,7 @@ #include "rcc/CodeGen/GlobalISel/GISelValueTracking.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/Utils.h" #include "rcc/CodeGen/LowLevelType.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" @@ -60,15 +61,10 @@ namespace { [[nodiscard]] std::optional constantShiftAmount(Register Reg, const MachineRegisterInfo &MRI, std::uint32_t BitWidth) { - const MachineInstr *Definition = MRI.getVRegDef(Reg); - if (Definition == nullptr || Definition->opcode() != opcode(GenericOpcode::G_CONSTANT)) - return std::nullopt; - const MachineOperand *ValueOperand = Definition->operandAt(1); - const auto *Immediate = - ValueOperand == nullptr ? nullptr : ValueOperand->getIf(); - if (Immediate == nullptr || Immediate->Value.activeBitWidth() > 32) + const auto Constant = getIConstantVRegValWithLookThrough(Reg, MRI); + if (!Constant || Constant->Value.activeBitWidth() > 32) return std::nullopt; - const std::uint64_t Amount = Immediate->Value.word(0); + const std::uint64_t Amount = Constant->Value.word(0); if (Amount >= BitWidth) return std::nullopt; return static_cast(Amount); @@ -400,6 +396,7 @@ Expected GISelValueTracking::computeNumSignBits(Register Reg, uns if (Definition == nullptr) return 1U; const auto Opcode = static_cast(Definition->opcode().value()); + std::uint32_t FirstAnswer = 1U; if (Opcode == GenericOpcode::G_CONSTANT) { const MachineOperand *ValueOperand = Definition->operandAt(1); @@ -451,11 +448,23 @@ Expected GISelValueTracking::computeNumSignBits(Register Reg, uns if (!RightSignBits) return std::unexpected(RightSignBits.error()); if (*RightSignBits != 1) - return std::min(*LeftSignBits, *RightSignBits); + FirstAnswer = std::min(*LeftSignBits, *RightSignBits); } } } + if (Opcode == GenericOpcode::G_ASHR && Source) { + const auto Right = registerOperand(*Definition, 2); + if (Right) { + auto SourceSignBits = computeNumSignBits(*Source, Depth + 1U); + if (!SourceSignBits) + return std::unexpected(SourceSignBits.error()); + FirstAnswer = *SourceSignBits; + if (const auto Amount = constantShiftAmount(*Right, MRI, BitWidth)) + FirstAnswer = std::min(BitWidth, FirstAnswer + *Amount); + } + } + if (Opcode == GenericOpcode::G_TRUNC && Source) { auto SourceType = MRI.getType(*Source); if (!SourceType) @@ -508,7 +517,7 @@ Expected GISelValueTracking::computeNumSignBits(Register Reg, uns KnownSignBits = static_cast(Known->Zero.countlOne()); else if (Known->One.testBit(BitWidth - 1U)) KnownSignBits = static_cast(Known->One.countlOne()); - return std::max(1U, KnownSignBits); + return std::max(FirstAnswer, std::max(1U, KnownSignBits)); } } // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp index 0ea3783..a3f3342 100644 --- a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp +++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp @@ -780,6 +780,35 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size return Result; break; + case GenericOpcode::G_CONSTANT: { + if (TypeIndex != 0) + return makeUnexpected(ErrorCode::VerificationError, + "constant widening has an invalid type index"); + MachineOperand *SourceOperand = Instruction.operandAt(1); + const auto *Immediate = + SourceOperand == nullptr ? nullptr : SourceOperand->getIf(); + if (Immediate == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "G_CONSTANT widening requires an integer immediate"); + const GenericOpcode ExtensionOpcode = + Info.getExtOpcodeForWideningConstant(Query->Types[TypeIndex]); + if (ExtensionOpcode != GenericOpcode::G_SEXT && ExtensionOpcode != GenericOpcode::G_ZEXT && + ExtensionOpcode != GenericOpcode::G_ANYEXT) { + return makeUnexpected(ErrorCode::InternalError, + "constant widening selected an invalid extension opcode"); + } + auto Extended = ExtensionOpcode == GenericOpcode::G_SEXT + ? Immediate->Value.sext(WideType.scalarBitWidth()) + : Immediate->Value.zext(WideType.scalarBitWidth()); + if (!Extended) + return std::unexpected(Extended.error()); + if (auto Replaced = SourceOperand->setIntegerImmediate(std::move(*Extended)); !Replaced) + return std::unexpected(Replaced.error()); + if (auto Result = apply(widenDestination()); !Result) + return Result; + break; + } + case GenericOpcode::G_ADD: case GenericOpcode::G_SUB: case GenericOpcode::G_MUL: @@ -1314,6 +1343,42 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, return makeUnexpected(ErrorCode::InvalidArgument, "lower received a non-lower legalization action"); switch (static_cast(Instruction.opcode().value())) { + case GenericOpcode::G_ABS: + return lowerAbsToAddXor(Instruction); + case GenericOpcode::G_SEXT_INREG: { + const Register Destination = *Instruction.operandAt(0)->getIf(); + const Register Source = *Instruction.operandAt(1)->getIf(); + auto SizeInBits = signedImmediate(*Instruction.operandAt(2)); + if (!SizeInBits) + return std::unexpected(SizeInBits.error()); + auto Type = MRI.getType(Destination); + if (!Type) + return std::unexpected(Type.error()); + + auto ShiftAmount = MRI.createVirtualRegister(*Type); + auto Temporary = MRI.createVirtualRegister(*Type); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); + if (!Temporary) + return std::unexpected(Temporary.error()); + + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + const std::int64_t Shift = static_cast(Type->scalarBitWidth()) - *SizeInBits; + if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, Shift); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildShl(*Temporary, Source, *ShiftAmount); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildAShr(Destination, *Temporary, *ShiftAmount); !Built) + return std::unexpected(Built.error()); + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) { + return makeUnexpected(ErrorCode::InternalError, + "G_SEXT_INREG became detached during lowering"); + } + return Block->removeInstruction(Instruction); + } case GenericOpcode::G_VAARG: return lowerVAArg(Instruction); case GenericOpcode::G_UADDO: { @@ -1488,6 +1553,40 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, } } +Expected LegalizerHelper::lowerAbsToAddXor(MachineInstr &Instruction) { + const Register Destination = *Instruction.operandAt(0)->getIf(); + const Register Source = *Instruction.operandAt(1)->getIf(); + auto Type = MRI.getType(Destination); + if (!Type) + return std::unexpected(Type.error()); + + auto ShiftAmount = MRI.createVirtualRegister(*Type); + auto Shift = MRI.createVirtualRegister(*Type); + auto Add = MRI.createVirtualRegister(*Type); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); + if (!Shift) + return std::unexpected(Shift.error()); + if (!Add) + return std::unexpected(Add.error()); + + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + if (auto Built = MIRBuilder.buildConstant(*ShiftAmount, Type->scalarBitWidth() - 1U); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildAShr(*Shift, Source, *ShiftAmount); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildAdd(*Add, Source, *Shift); !Built) + return std::unexpected(Built.error()); + if (auto Built = MIRBuilder.buildXor(Destination, *Add, *Shift); !Built) + return std::unexpected(Built.error()); + + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, "G_ABS became detached during lowering"); + return Block->removeInstruction(Instruction); +} + Expected LegalizerHelper::legalize(MachineInstr &Instruction, const LegalizationDecision &Decision) { if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp index 7d9e6ff..c4cf946 100644 --- a/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp +++ b/backend/lib/CodeGen/GlobalISel/LegalizerInfo.cpp @@ -474,4 +474,8 @@ Expected LegalizerInfo::isUnsupported(const LegalizationQuery &Query) cons return Decision->Action == LegalizationAction::Unsupported; } +GenericOpcode LegalizerInfo::getExtOpcodeForWideningConstant(LowLevelType SmallType) const { + return SmallType.minimumBitWidth() % 8U == 0 ? GenericOpcode::G_SEXT : GenericOpcode::G_ZEXT; +} + } // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/Utils.cpp b/backend/lib/CodeGen/GlobalISel/Utils.cpp index 6640694..7e594ce 100644 --- a/backend/lib/CodeGen/GlobalISel/Utils.cpp +++ b/backend/lib/CodeGen/GlobalISel/Utils.cpp @@ -13,6 +13,7 @@ #include #include +#include #include namespace rcc { @@ -145,6 +146,90 @@ namespace { } // namespace +std::optional getIConstantVRegValWithLookThrough(Register VReg, + const MachineRegisterInfo &MRI, + bool LookThroughInstrs) { + std::vector> SeenOpcodes; + const MachineInstr *Instruction = nullptr; + + while ((Instruction = MRI.getVRegDef(VReg)) != nullptr && + Instruction->opcode() != opcode(GenericOpcode::G_CONSTANT) && LookThroughInstrs) { + const GenericOpcode Generic = static_cast(Instruction->opcode().value()); + switch (Generic) { + case GenericOpcode::G_ANYEXT: + return std::nullopt; + case GenericOpcode::G_TRUNC: + case GenericOpcode::G_SEXT: + case GenericOpcode::G_ZEXT: { + const MachineOperand *DestinationOperand = Instruction->operandAt(0); + const MachineOperand *SourceOperand = Instruction->operandAt(1); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf(); + const Register *Source = + SourceOperand == nullptr ? nullptr : SourceOperand->getIf(); + if (Destination == nullptr || Source == nullptr) + return std::nullopt; + auto Type = MRI.getType(*Destination); + if (!Type) + return std::nullopt; + SeenOpcodes.emplace_back(Generic, Type->scalarBitWidth()); + VReg = *Source; + break; + } + case GenericOpcode::COPY: { + const MachineOperand *SourceOperand = Instruction->operandAt(1); + const Register *Source = + SourceOperand == nullptr ? nullptr : SourceOperand->getIf(); + if (Source == nullptr || Source->isPhysical()) + return std::nullopt; + VReg = *Source; + break; + } + case GenericOpcode::G_INTTOPTR: { + const MachineOperand *SourceOperand = Instruction->operandAt(1); + const Register *Source = + SourceOperand == nullptr ? nullptr : SourceOperand->getIf(); + if (Source == nullptr) + return std::nullopt; + VReg = *Source; + break; + } + default: + return std::nullopt; + } + } + + if (Instruction == nullptr || Instruction->opcode() != opcode(GenericOpcode::G_CONSTANT)) + return std::nullopt; + const MachineOperand *ValueOperand = Instruction->operandAt(1); + const auto *Immediate = + ValueOperand == nullptr ? nullptr : ValueOperand->getIf(); + if (Immediate == nullptr) + return std::nullopt; + + APInt Value = Immediate->Value; + for (auto Iterator = SeenOpcodes.rbegin(); Iterator != SeenOpcodes.rend(); ++Iterator) { + Expected Transformed = [&]() -> Expected { + switch (Iterator->first) { + case GenericOpcode::G_TRUNC: + return Value.trunc(Iterator->second); + case GenericOpcode::G_ANYEXT: + case GenericOpcode::G_SEXT: + return Value.sext(Iterator->second); + case GenericOpcode::G_ZEXT: + return Value.zext(Iterator->second); + default: + return makeUnexpected(ErrorCode::InternalError, + "unexpected opcode in constant look-through chain"); + } + }(); + if (!Transformed) + return std::nullopt; + Value = std::move(*Transformed); + } + return ValueAndVReg{.Value = std::move(Value), .VReg = VReg}; +} + bool isTriviallyDead(const MachineInstr &Instruction, const MachineRegisterInfo &MRI, const TargetDescription &Target) noexcept { for (const MachineOperand &Operand : Instruction.operands()) { diff --git a/backend/lib/CodeGen/MachineIRBuilder.cpp b/backend/lib/CodeGen/MachineIRBuilder.cpp index d5be3af..e3ac0bf 100644 --- a/backend/lib/CodeGen/MachineIRBuilder.cpp +++ b/backend/lib/CodeGen/MachineIRBuilder.cpp @@ -873,6 +873,11 @@ Expected MachineIRBuilder::buildOr(Register Destination, Registe return buildBinary(opcode(GenericOpcode::G_OR), Destination, Left, Right); } +Expected MachineIRBuilder::buildXor(Register Destination, Register Left, + Register Right) const { + return buildBinary(opcode(GenericOpcode::G_XOR), Destination, Left, Right); +} + Expected MachineIRBuilder::buildAdd(Register Destination, Register Left, Register Right) const { return buildBinary(opcode(GenericOpcode::G_ADD), Destination, Left, Right); diff --git a/backend/lib/CodeGen/MachineOperand.cpp b/backend/lib/CodeGen/MachineOperand.cpp index 9b54bb9..92b09dc 100644 --- a/backend/lib/CodeGen/MachineOperand.cpp +++ b/backend/lib/CodeGen/MachineOperand.cpp @@ -335,6 +335,15 @@ Expected MachineOperand::setImmediate(std::int64_t Value) { return {}; } +Expected MachineOperand::setIntegerImmediate(APInt Value) { + if (OperandKind != Kind::IntegerImmediate) { + return makeUnexpected(ErrorCode::InvalidArgument, + "setIntegerImmediate requires an integer-immediate operand"); + } + Storage = IntegerImmediateOperand{std::move(Value)}; + return {}; +} + Expected MachineOperand::setRegisterFlags(RegisterOperandFlags Flags) { if (!isRegister()) { return makeUnexpected(ErrorCode::InvalidArgument, "register flags require a register operand"); -- cgit v1.2.3