From 1ff4fb953820c823ae8d5035c75bf43bf85e9c3c Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sat, 15 Aug 2026 04:23:23 +0800 Subject: [RISCV][GlobalISel] Legalize scalar bit count operations --- backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp | 527 +++++++++++++++++++++ 1 file changed, 527 insertions(+) (limited to 'backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp') diff --git a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp index 485bb43..592d704 100644 --- a/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp +++ b/backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp @@ -109,6 +109,50 @@ struct ScalarLayout final { return resultRegister(**Built); } +[[nodiscard]] Expected +buildFlaggedBinaryInstruction(MachineIRBuilder &Builder, GenericOpcode Generic, LowLevelType Type, + Register Left, Register Right, MachineInstrFlags Flags) { + auto Destination = Builder.function().registerInfo().createVirtualRegister(Type); + if (!Destination) + return std::unexpected(Destination.error()); + auto Pending = Builder.buildInstr(opcode(Generic)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Added = Pending->addDef(*Destination); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(Left); !Added) + return std::unexpected(Added.error()); + if (auto Added = Pending->addUse(Right); !Added) + return std::unexpected(Added.error()); + if (auto Set = Pending->setFlags(Flags); !Set) + return std::unexpected(Set.error()); + if (auto Built = Pending->build(); !Built) + return std::unexpected(Built.error()); + return *Destination; +} + +[[nodiscard]] Expected repeatedByte(std::uint32_t BitWidth, std::uint8_t Byte) { + if (BitWidth == 0 || BitWidth > APInt::MaxBitWidth || BitWidth % 8U != 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "repeated-byte integer has an invalid bit width"); + constexpr std::uint64_t ByteSplat = 0x0101010101010101ULL; + std::vector Words((static_cast(BitWidth) + 63U) / 64U, + ByteSplat * Byte); + const std::uint32_t HighBits = BitWidth % 64U; + if (HighBits != 0) + Words.back() &= (std::uint64_t{1} << HighBits) - 1U; + return APInt::create(BitWidth, Words); +} + +[[nodiscard]] Expected oneBitSet(std::uint32_t BitWidth, std::uint32_t Bit) { + if (BitWidth == 0 || BitWidth > APInt::MaxBitWidth || Bit >= BitWidth) + return makeUnexpected(ErrorCode::InvalidArgument, + "single-bit integer has an invalid bit position"); + std::vector Words((static_cast(BitWidth) + 63U) / 64U, 0); + Words[Bit / 64U] = std::uint64_t{1} << (Bit % 64U); + return APInt::create(BitWidth, Words); +} + [[nodiscard]] Expected buildICmpRegister(MachineIRBuilder &Builder, IntegerPredicate Predicate, LowLevelType ResultType, Register Left, @@ -1119,6 +1163,109 @@ Expected LegalizerHelper::widenScalar(MachineInstr &Instruction, std::size return Result; break; + case GenericOpcode::G_CTTZ: + case GenericOpcode::G_CTTZ_ZERO_POISON: + case GenericOpcode::G_CTLZ: + case GenericOpcode::G_CTLZ_ZERO_POISON: + case GenericOpcode::G_CTLS: + case GenericOpcode::G_CTPOP: { + const GenericOpcode Generic = static_cast(Instruction.opcode().value()); + if (TypeIndex == 0) { + if (auto Result = Apply(WidenDestination()); !Result) + return Result; + break; + } + if (TypeIndex != 1) + return makeUnexpected(ErrorCode::VerificationError, + "bit-count widening has an invalid type index"); + + 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 makeUnexpected(ErrorCode::VerificationError, + "bit-count widening requires register operands"); + auto SourceType = MRI.getType(*Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + + GenericOpcode ExtensionOpcode = GenericOpcode::G_ZEXT; + switch (Generic) { + case GenericOpcode::G_CTTZ: + case GenericOpcode::G_CTTZ_ZERO_POISON: + case GenericOpcode::G_CTLZ_ZERO_POISON: + ExtensionOpcode = GenericOpcode::G_ANYEXT; + break; + case GenericOpcode::G_CTLS: + ExtensionOpcode = GenericOpcode::G_SEXT; + break; + default: + break; + } + + auto WideSource = buildResultInstruction(MIRBuilder, ExtensionOpcode, WideType, {*Source}); + if (!WideSource) + return std::unexpected(WideSource.error()); + GenericOpcode WideOpcode = Generic; + if (Generic == GenericOpcode::G_CTTZ) { + auto TopBitValue = oneBitSet(WideType.scalarBitWidth(), SourceType->scalarBitWidth()); + if (!TopBitValue) + return std::unexpected(TopBitValue.error()); + auto TopBit = buildConstantRegister(MIRBuilder, WideType, std::move(*TopBitValue)); + if (!TopBit) + return std::unexpected(TopBit.error()); + auto NonZeroSource = + buildResultInstruction(MIRBuilder, GenericOpcode::G_OR, WideType, {*WideSource, *TopBit}); + if (!NonZeroSource) + return std::unexpected(NonZeroSource.error()); + WideSource = *NonZeroSource; + WideOpcode = GenericOpcode::G_CTTZ_ZERO_POISON; + } + + const std::uint32_t SizeDifference = WideType.scalarBitWidth() - SourceType->scalarBitWidth(); + if (Generic == GenericOpcode::G_CTLZ_ZERO_POISON) { + auto ShiftAmount = + buildConstantRegister(MIRBuilder, WideType, static_cast(SizeDifference)); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); + auto Shifted = buildResultInstruction(MIRBuilder, GenericOpcode::G_SHL, WideType, + {*WideSource, *ShiftAmount}); + if (!Shifted) + return std::unexpected(Shifted.error()); + WideSource = *Shifted; + } + + auto Result = buildResultInstruction(MIRBuilder, WideOpcode, WideType, {*WideSource}); + if (!Result) + return std::unexpected(Result.error()); + if (Generic == GenericOpcode::G_CTLZ || Generic == GenericOpcode::G_CTLS) { + auto Difference = + buildConstantRegister(MIRBuilder, WideType, static_cast(SizeDifference)); + if (!Difference) + return std::unexpected(Difference.error()); + if (Generic == GenericOpcode::G_CTLZ) { + Result = buildFlaggedBinaryInstruction(MIRBuilder, GenericOpcode::G_SUB, WideType, *Result, + *Difference, + MachineInstrFlags{MachineInstrFlag::NoUnsignedWrap}); + } else { + Result = buildResultInstruction(MIRBuilder, GenericOpcode::G_SUB, WideType, + {*Result, *Difference}); + } + if (!Result) + return std::unexpected(Result.error()); + } + + if (auto Built = MIRBuilder.buildZExtOrTrunc(*Destination, *Result); !Built) + return std::unexpected(Built.error()); + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "bit-count instruction became detached during widening"); + return Block->removeInstruction(Instruction); + } + case GenericOpcode::G_BSWAP: { if (TypeIndex != 0) return makeUnexpected(ErrorCode::VerificationError, @@ -3007,6 +3154,13 @@ Expected LegalizerHelper::lower(MachineInstr &Instruction, case GenericOpcode::G_SDIVREM: case GenericOpcode::G_UDIVREM: return lowerDivRem(Instruction); + case GenericOpcode::G_CTLZ_ZERO_POISON: + case GenericOpcode::G_CTTZ_ZERO_POISON: + case GenericOpcode::G_CTLZ: + case GenericOpcode::G_CTTZ: + case GenericOpcode::G_CTPOP: + case GenericOpcode::G_CTLS: + return lowerBitCount(Instruction); case GenericOpcode::G_BSWAP: return lowerBswap(Instruction); case GenericOpcode::G_ROTL: @@ -3572,6 +3726,379 @@ Expected LegalizerHelper::lowerDivRem(MachineInstr &Instruction) { return Block->removeInstruction(Instruction); } +Expected LegalizerHelper::lowerBitCount(MachineInstr &Instruction) { + const GenericOpcode Generic = static_cast(Instruction.opcode().value()); + MachineOperand *DestinationOperand = Instruction.operandAt(0); + 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 makeUnexpected(ErrorCode::VerificationError, + "bit-count lowering requires register operands"); + auto DestinationType = MRI.getType(*Destination); + if (!DestinationType) + return std::unexpected(DestinationType.error()); + auto SourceType = MRI.getType(*Source); + if (!SourceType) + return std::unexpected(SourceType.error()); + if (!DestinationType->isCategoryNeutralScalar() || !SourceType->isCategoryNeutralScalar()) + return makeUnexpected(ErrorCode::Unsupported, + "non-scalar bit-count lowering is not implemented"); + if (auto Point = MIRBuilder.setInsertPointBefore(Instruction); !Point) + return std::unexpected(Point.error()); + + const auto IsSupported = [this](GenericOpcode Opcode, LowLevelType ResultType, + LowLevelType OperandType) -> Expected { + auto Decision = Info.getDecision(LegalizationQuery(opcode(Opcode), {ResultType, OperandType})); + if (!Decision) + return std::unexpected(Decision.error()); + return Decision->Action == LegalizationAction::Legal || + Decision->Action == LegalizationAction::Libcall || + Decision->Action == LegalizationAction::Custom; + }; + const auto EraseOriginal = [&Instruction]() -> Expected { + MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr) + return makeUnexpected(ErrorCode::InternalError, + "bit-count instruction became detached during lowering"); + return Block->removeInstruction(Instruction); + }; + + switch (Generic) { + case GenericOpcode::G_CTLZ_ZERO_POISON: + case GenericOpcode::G_CTTZ_ZERO_POISON: { + const GenericOpcode Replacement = Generic == GenericOpcode::G_CTLZ_ZERO_POISON + ? GenericOpcode::G_CTLZ + : GenericOpcode::G_CTTZ; + Observer.changingInstr(Instruction); + if (auto Changed = Instruction.setOpcode(opcode(Replacement)); !Changed) + return std::unexpected(Changed.error()); + Observer.changedInstr(Instruction); + return {}; + } + + case GenericOpcode::G_CTLZ: { + const std::uint32_t Size = SourceType->scalarBitWidth(); + auto PoisonSupported = + IsSupported(GenericOpcode::G_CTLZ_ZERO_POISON, *DestinationType, *SourceType); + if (!PoisonSupported) + return std::unexpected(PoisonSupported.error()); + if (*PoisonSupported) { + auto PoisonCount = buildResultInstruction(MIRBuilder, GenericOpcode::G_CTLZ_ZERO_POISON, + *DestinationType, {*Source}); + if (!PoisonCount) + return std::unexpected(PoisonCount.error()); + auto Zero = buildConstantRegister(MIRBuilder, *SourceType, 0); + if (!Zero) + return std::unexpected(Zero.error()); + auto ConditionType = booleanTypeFor(*SourceType); + if (!ConditionType) + return std::unexpected(ConditionType.error()); + auto IsZero = + buildICmpRegister(MIRBuilder, IntegerPredicate::Equal, *ConditionType, *Source, *Zero); + if (!IsZero) + return std::unexpected(IsZero.error()); + auto SizeConstant = + buildConstantRegister(MIRBuilder, *DestinationType, static_cast(Size)); + if (!SizeConstant) + return std::unexpected(SizeConstant.error()); + if (auto Built = MIRBuilder.buildInstr(opcode(GenericOpcode::G_SELECT), {*Destination}, + {*IsZero, *SizeConstant, *PoisonCount}); + !Built) { + return std::unexpected(Built.error()); + } + return EraseOriginal(); + } + + Register Value = *Source; + const std::uint32_t ExpandedSize = std::bit_ceil(Size); + for (std::uint32_t Shift = 1; Shift <= ExpandedSize / 2U; Shift <<= 1U) { + auto ShiftAmount = + buildConstantRegister(MIRBuilder, *SourceType, static_cast(Shift)); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); + auto Shifted = buildResultInstruction(MIRBuilder, GenericOpcode::G_LSHR, *SourceType, + {Value, *ShiftAmount}); + if (!Shifted) + return std::unexpected(Shifted.error()); + auto Propagated = + buildResultInstruction(MIRBuilder, GenericOpcode::G_OR, *SourceType, {Value, *Shifted}); + if (!Propagated) + return std::unexpected(Propagated.error()); + Value = *Propagated; + } + auto Population = + buildResultInstruction(MIRBuilder, GenericOpcode::G_CTPOP, *DestinationType, {Value}); + if (!Population) + return std::unexpected(Population.error()); + auto SizeConstant = + buildConstantRegister(MIRBuilder, *DestinationType, static_cast(Size)); + if (!SizeConstant) + return std::unexpected(SizeConstant.error()); + if (auto Built = MIRBuilder.buildSub(*Destination, *SizeConstant, *Population); !Built) + return std::unexpected(Built.error()); + return EraseOriginal(); + } + + case GenericOpcode::G_CTTZ: { + const std::uint32_t Size = SourceType->scalarBitWidth(); + auto PoisonSupported = + IsSupported(GenericOpcode::G_CTTZ_ZERO_POISON, *DestinationType, *SourceType); + if (!PoisonSupported) + return std::unexpected(PoisonSupported.error()); + if (*PoisonSupported) { + auto PoisonCount = buildResultInstruction(MIRBuilder, GenericOpcode::G_CTTZ_ZERO_POISON, + *DestinationType, {*Source}); + if (!PoisonCount) + return std::unexpected(PoisonCount.error()); + auto Zero = buildConstantRegister(MIRBuilder, *SourceType, 0); + if (!Zero) + return std::unexpected(Zero.error()); + auto ConditionType = booleanTypeFor(*DestinationType); + if (!ConditionType) + return std::unexpected(ConditionType.error()); + auto IsZero = + buildICmpRegister(MIRBuilder, IntegerPredicate::Equal, *ConditionType, *Source, *Zero); + if (!IsZero) + return std::unexpected(IsZero.error()); + auto SizeConstant = + buildConstantRegister(MIRBuilder, *DestinationType, static_cast(Size)); + if (!SizeConstant) + return std::unexpected(SizeConstant.error()); + if (auto Built = MIRBuilder.buildInstr(opcode(GenericOpcode::G_SELECT), {*Destination}, + {*IsZero, *SizeConstant, *PoisonCount}); + !Built) { + return std::unexpected(Built.error()); + } + return EraseOriginal(); + } + + auto MinusOne = buildConstantRegister(MIRBuilder, *SourceType, -1); + if (!MinusOne) + return std::unexpected(MinusOne.error()); + auto Inverted = + buildResultInstruction(MIRBuilder, GenericOpcode::G_XOR, *SourceType, {*Source, *MinusOne}); + if (!Inverted) + return std::unexpected(Inverted.error()); + auto Decremented = + buildResultInstruction(MIRBuilder, GenericOpcode::G_ADD, *SourceType, {*Source, *MinusOne}); + if (!Decremented) + return std::unexpected(Decremented.error()); + auto Masked = buildResultInstruction(MIRBuilder, GenericOpcode::G_AND, *SourceType, + {*Inverted, *Decremented}); + if (!Masked) + return std::unexpected(Masked.error()); + + auto PopulationSupported = IsSupported(GenericOpcode::G_CTPOP, *SourceType, *SourceType); + if (!PopulationSupported) + return std::unexpected(PopulationSupported.error()); + auto LeadingZeroSupported = IsSupported(GenericOpcode::G_CTLZ, *SourceType, *SourceType); + if (!LeadingZeroSupported) + return std::unexpected(LeadingZeroSupported.error()); + if (!*PopulationSupported && *LeadingZeroSupported) { + auto SizeConstant = + buildConstantRegister(MIRBuilder, *SourceType, static_cast(Size)); + if (!SizeConstant) + return std::unexpected(SizeConstant.error()); + auto LeadingZeros = + buildResultInstruction(MIRBuilder, GenericOpcode::G_CTLZ, *SourceType, {*Masked}); + if (!LeadingZeros) + return std::unexpected(LeadingZeros.error()); + if (auto Built = MIRBuilder.buildSub(*Destination, *SizeConstant, *LeadingZeros); !Built) + return std::unexpected(Built.error()); + return EraseOriginal(); + } + + Observer.changingInstr(Instruction); + if (auto Changed = Instruction.setOpcode(opcode(GenericOpcode::G_CTPOP)); !Changed) + return std::unexpected(Changed.error()); + if (auto Changed = SourceOperand->setRegister(*Masked); !Changed) + return std::unexpected(Changed.error()); + Observer.changedInstr(Instruction); + return {}; + } + + case GenericOpcode::G_CTPOP: { + const std::uint32_t Size = SourceType->scalarBitWidth(); + if (Size > 128 || Size % 8U != 0) + return makeUnexpected( + ErrorCode::Unsupported, + "population-count lowering requires a byte-sized scalar up to 128 bits"); + + auto One = buildConstantRegister(MIRBuilder, *SourceType, 1); + if (!One) + return std::unexpected(One.error()); + auto ShiftedByOne = + buildResultInstruction(MIRBuilder, GenericOpcode::G_LSHR, *SourceType, {*Source, *One}); + if (!ShiftedByOne) + return std::unexpected(ShiftedByOne.error()); + auto PairMaskValue = repeatedByte(Size, 0x55); + if (!PairMaskValue) + return std::unexpected(PairMaskValue.error()); + auto PairMask = buildConstantRegister(MIRBuilder, *SourceType, std::move(*PairMaskValue)); + if (!PairMask) + return std::unexpected(PairMask.error()); + auto HighPairBits = buildResultInstruction(MIRBuilder, GenericOpcode::G_AND, *SourceType, + {*ShiftedByOne, *PairMask}); + if (!HighPairBits) + return std::unexpected(HighPairBits.error()); + auto PairCounts = buildResultInstruction(MIRBuilder, GenericOpcode::G_SUB, *SourceType, + {*Source, *HighPairBits}); + if (!PairCounts) + return std::unexpected(PairCounts.error()); + + auto Two = buildConstantRegister(MIRBuilder, *SourceType, 2); + if (!Two) + return std::unexpected(Two.error()); + auto ShiftedPairs = + buildResultInstruction(MIRBuilder, GenericOpcode::G_LSHR, *SourceType, {*PairCounts, *Two}); + if (!ShiftedPairs) + return std::unexpected(ShiftedPairs.error()); + auto NibbleMaskValue = repeatedByte(Size, 0x33); + if (!NibbleMaskValue) + return std::unexpected(NibbleMaskValue.error()); + auto NibbleMask = buildConstantRegister(MIRBuilder, *SourceType, std::move(*NibbleMaskValue)); + if (!NibbleMask) + return std::unexpected(NibbleMask.error()); + auto HighNibbleCounts = buildResultInstruction(MIRBuilder, GenericOpcode::G_AND, *SourceType, + {*ShiftedPairs, *NibbleMask}); + if (!HighNibbleCounts) + return std::unexpected(HighNibbleCounts.error()); + auto LowNibbleCounts = buildResultInstruction(MIRBuilder, GenericOpcode::G_AND, *SourceType, + {*PairCounts, *NibbleMask}); + if (!LowNibbleCounts) + return std::unexpected(LowNibbleCounts.error()); + auto NibbleCounts = buildResultInstruction(MIRBuilder, GenericOpcode::G_ADD, *SourceType, + {*HighNibbleCounts, *LowNibbleCounts}); + if (!NibbleCounts) + return std::unexpected(NibbleCounts.error()); + + auto Four = buildConstantRegister(MIRBuilder, *SourceType, 4); + if (!Four) + return std::unexpected(Four.error()); + auto ShiftedNibbles = buildResultInstruction(MIRBuilder, GenericOpcode::G_LSHR, *SourceType, + {*NibbleCounts, *Four}); + if (!ShiftedNibbles) + return std::unexpected(ShiftedNibbles.error()); + auto DirtyByteCounts = buildResultInstruction(MIRBuilder, GenericOpcode::G_ADD, *SourceType, + {*ShiftedNibbles, *NibbleCounts}); + if (!DirtyByteCounts) + return std::unexpected(DirtyByteCounts.error()); + auto ByteMaskValue = repeatedByte(Size, 0x0f); + if (!ByteMaskValue) + return std::unexpected(ByteMaskValue.error()); + auto ByteMask = buildConstantRegister(MIRBuilder, *SourceType, std::move(*ByteMaskValue)); + if (!ByteMask) + return std::unexpected(ByteMask.error()); + auto ByteCounts = buildResultInstruction(MIRBuilder, GenericOpcode::G_AND, *SourceType, + {*DirtyByteCounts, *ByteMask}); + if (!ByteCounts) + return std::unexpected(ByteCounts.error()); + + if (Size == 16) { + auto Eight = buildConstantRegister(MIRBuilder, *SourceType, 8); + if (!Eight) + return std::unexpected(Eight.error()); + auto HighByteCount = buildResultInstruction(MIRBuilder, GenericOpcode::G_LSHR, *SourceType, + {*ByteCounts, *Eight}); + if (!HighByteCount) + return std::unexpected(HighByteCount.error()); + auto Sum = buildResultInstruction(MIRBuilder, GenericOpcode::G_ADD, *SourceType, + {*ByteCounts, *HighByteCount}); + if (!Sum) + return std::unexpected(Sum.error()); + auto ResultMaskValue = APInt::fromUnsigned(Size, 0xff); + if (!ResultMaskValue) + return std::unexpected(ResultMaskValue.error()); + auto ResultMask = buildConstantRegister(MIRBuilder, *SourceType, std::move(*ResultMaskValue)); + if (!ResultMask) + return std::unexpected(ResultMask.error()); + if (auto Built = MIRBuilder.buildAnd(*Destination, *Sum, *ResultMask); !Built) + return std::unexpected(Built.error()); + return EraseOriginal(); + } + + auto MultiplyMaskValue = repeatedByte(Size, 0x01); + if (!MultiplyMaskValue) + return std::unexpected(MultiplyMaskValue.error()); + auto MultiplyMask = + buildConstantRegister(MIRBuilder, *SourceType, std::move(*MultiplyMaskValue)); + if (!MultiplyMask) + return std::unexpected(MultiplyMask.error()); + auto FinalShift = + buildConstantRegister(MIRBuilder, *SourceType, static_cast(Size - 8U)); + if (!FinalShift) + return std::unexpected(FinalShift.error()); + + auto MultiplyDecision = + Info.getDecision(LegalizationQuery(opcode(GenericOpcode::G_MUL), {*SourceType})); + if (!MultiplyDecision) + return std::unexpected(MultiplyDecision.error()); + const bool IsMultiplySupported = MultiplyDecision->Action == LegalizationAction::Legal || + MultiplyDecision->Action == LegalizationAction::WidenScalar || + MultiplyDecision->Action == LegalizationAction::Custom; + if (IsMultiplySupported) { + auto Product = buildResultInstruction(MIRBuilder, GenericOpcode::G_MUL, *SourceType, + {*ByteCounts, *MultiplyMask}); + if (!Product) + return std::unexpected(Product.error()); + if (auto Built = MIRBuilder.buildLShr(*Destination, *Product, *FinalShift); !Built) + return std::unexpected(Built.error()); + } else { + Register Sum = *ByteCounts; + for (std::uint32_t Shift = 8; Shift < Size; Shift *= 2U) { + auto ShiftAmount = + buildConstantRegister(MIRBuilder, *SourceType, static_cast(Shift)); + if (!ShiftAmount) + return std::unexpected(ShiftAmount.error()); + auto Shifted = buildResultInstruction(MIRBuilder, GenericOpcode::G_SHL, *SourceType, + {Sum, *ShiftAmount}); + if (!Shifted) + return std::unexpected(Shifted.error()); + auto NewSum = + buildResultInstruction(MIRBuilder, GenericOpcode::G_ADD, *SourceType, {Sum, *Shifted}); + if (!NewSum) + return std::unexpected(NewSum.error()); + Sum = *NewSum; + } + if (auto Built = MIRBuilder.buildLShr(*Destination, Sum, *FinalShift); !Built) + return std::unexpected(Built.error()); + } + return EraseOriginal(); + } + + case GenericOpcode::G_CTLS: { + auto SignIndex = buildConstantRegister( + MIRBuilder, *SourceType, static_cast(SourceType->scalarBitWidth() - 1U)); + if (!SignIndex) + return std::unexpected(SignIndex.error()); + auto One = buildConstantRegister(MIRBuilder, *DestinationType, 1); + if (!One) + return std::unexpected(One.error()); + auto Sign = buildResultInstruction(MIRBuilder, GenericOpcode::G_ASHR, *SourceType, + {*Source, *SignIndex}); + if (!Sign) + return std::unexpected(Sign.error()); + auto DifferentBits = + buildResultInstruction(MIRBuilder, GenericOpcode::G_XOR, *SourceType, {*Source, *Sign}); + if (!DifferentBits) + return std::unexpected(DifferentBits.error()); + auto LeadingZeros = buildResultInstruction(MIRBuilder, GenericOpcode::G_CTLZ, *DestinationType, + {*DifferentBits}); + if (!LeadingZeros) + return std::unexpected(LeadingZeros.error()); + if (auto Built = MIRBuilder.buildSub(*Destination, *LeadingZeros, *One); !Built) + return std::unexpected(Built.error()); + return EraseOriginal(); + } + + default: + return makeUnexpected(ErrorCode::Unsupported, + "bit-count lowering received an unexpected opcode"); + } +} + Expected LegalizerHelper::lowerBswap(MachineInstr &Instruction) { const Register Destination = *Instruction.operandAt(0)->getIf(); const Register Source = *Instruction.operandAt(1)->getIf(); -- cgit v1.2.3