diff options
Diffstat (limited to 'backend/lib/CodeGen/GlobalISel')
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp | 199 | ||||
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/LegalizerHelper.cpp | 527 |
2 files changed, 726 insertions, 0 deletions
diff --git a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp index f6a0a87..6e045b0 100644 --- a/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp +++ b/backend/lib/CodeGen/GlobalISel/GISelValueTracking.cpp @@ -55,6 +55,73 @@ namespace { return Left.bitwiseAnd(Right); } +[[nodiscard]] Expected<APInt> addMasks(const APInt &Left, const APInt &Right) { + if (Left.bitWidth() == 0 || Left.bitWidth() != Right.bitWidth()) + return makeUnexpected(ErrorCode::InvalidArgument, + "known-bits add operands must have the same nonzero width"); + std::vector<std::uint64_t> Words(Left.words().size(), 0); + unsigned __int128 Carry = 0; + for (std::size_t Index = 0; Index != Words.size(); ++Index) { + const unsigned __int128 Sum = static_cast<unsigned __int128>(Left.word(Index)) + + static_cast<unsigned __int128>(Right.word(Index)) + Carry; + Words[Index] = static_cast<std::uint64_t>(Sum); + Carry = Sum >> 64U; + } + return APInt::create(Left.bitWidth(), Words); +} + +struct MaskProduct final { + APInt Value; + bool Overflow = false; +}; + +[[nodiscard]] Expected<MaskProduct> multiplyMasks(const APInt &Left, const APInt &Right) { + if (Left.bitWidth() == 0 || Left.bitWidth() != Right.bitWidth()) + return makeUnexpected(ErrorCode::InvalidArgument, + "known-bits multiply operands must have the same nonzero width"); + + const std::size_t WordCount = Left.words().size(); + std::vector<std::uint64_t> Product(WordCount * 2U, 0); + for (std::size_t LeftIndex = 0; LeftIndex != WordCount; ++LeftIndex) { + for (std::size_t RightIndex = 0; RightIndex != WordCount; ++RightIndex) { + const std::size_t ProductIndex = LeftIndex + RightIndex; + const unsigned __int128 Partial = static_cast<unsigned __int128>(Left.word(LeftIndex)) * + static_cast<unsigned __int128>(Right.word(RightIndex)); + unsigned __int128 Sum = static_cast<unsigned __int128>(Product[ProductIndex]) + + static_cast<std::uint64_t>(Partial); + Product[ProductIndex] = static_cast<std::uint64_t>(Sum); + unsigned __int128 Carry = (Partial >> 64U) + (Sum >> 64U); + for (std::size_t Index = ProductIndex + 1U; Carry != 0 && Index != Product.size(); ++Index) { + Sum = static_cast<unsigned __int128>(Product[Index]) + static_cast<std::uint64_t>(Carry); + Product[Index] = static_cast<std::uint64_t>(Sum); + Carry = (Carry >> 64U) + (Sum >> 64U); + } + } + } + + bool Overflow = false; + for (std::size_t Index = WordCount; Index != Product.size(); ++Index) + Overflow |= Product[Index] != 0; + const std::uint32_t HighBits = Left.bitWidth() % 64U; + if (HighBits != 0) { + const std::uint64_t HighMask = (std::uint64_t{1} << HighBits) - 1U; + Overflow |= (Product[WordCount - 1U] & ~HighMask) != 0; + Product[WordCount - 1U] &= HighMask; + } + Product.resize(WordCount); + auto Value = APInt::create(Left.bitWidth(), Product); + if (!Value) + return std::unexpected(Value.error()); + return MaskProduct{.Value = std::move(*Value), .Overflow = Overflow}; +} + +[[nodiscard]] std::uint32_t countTrailingOnes(const APInt &Value) noexcept { + std::uint32_t Count = 0; + while (Count != Value.bitWidth() && Value.testBit(Count)) + ++Count; + return Count; +} + [[nodiscard]] Expected<APInt> constantAtWidth(const APInt &Value, std::uint32_t BitWidth) { return resizeMask(Value, BitWidth); } @@ -325,6 +392,138 @@ Expected<GISelValueTracking::KnownBits> GISelValueTracking::getKnownBits(Registe return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; } + if (Opcode == GenericOpcode::G_ADD) { + const auto Right = registerOperand(*Definition, 2); + if (!Right) + return Unknown; + auto LeftBits = getKnownBits(*Source, Depth + 1U); + if (!LeftBits) + return std::unexpected(LeftBits.error()); + auto RightBits = getKnownBits(*Right, Depth + 1U); + if (!RightBits) + return std::unexpected(RightBits.error()); + + auto LeftMaximum = LeftBits->Zero.bitwiseNot(); + if (!LeftMaximum) + return std::unexpected(LeftMaximum.error()); + auto RightMaximum = RightBits->Zero.bitwiseNot(); + if (!RightMaximum) + return std::unexpected(RightMaximum.error()); + auto PossibleSumZero = addMasks(*LeftMaximum, *RightMaximum); + if (!PossibleSumZero) + return std::unexpected(PossibleSumZero.error()); + auto PossibleSumOne = addMasks(LeftBits->One, RightBits->One); + if (!PossibleSumOne) + return std::unexpected(PossibleSumOne.error()); + + auto CarryKnownZero = PossibleSumZero->bitwiseXor(LeftBits->Zero); + if (!CarryKnownZero) + return std::unexpected(CarryKnownZero.error()); + CarryKnownZero = CarryKnownZero->bitwiseXor(RightBits->Zero); + if (!CarryKnownZero) + return std::unexpected(CarryKnownZero.error()); + CarryKnownZero = CarryKnownZero->bitwiseNot(); + if (!CarryKnownZero) + return std::unexpected(CarryKnownZero.error()); + auto CarryKnownOne = PossibleSumOne->bitwiseXor(LeftBits->One); + if (!CarryKnownOne) + return std::unexpected(CarryKnownOne.error()); + CarryKnownOne = CarryKnownOne->bitwiseXor(RightBits->One); + if (!CarryKnownOne) + return std::unexpected(CarryKnownOne.error()); + + auto LeftKnown = mergeMasks(LeftBits->Zero, LeftBits->One); + if (!LeftKnown) + return std::unexpected(LeftKnown.error()); + auto RightKnown = mergeMasks(RightBits->Zero, RightBits->One); + if (!RightKnown) + return std::unexpected(RightKnown.error()); + auto CarryKnown = mergeMasks(*CarryKnownZero, *CarryKnownOne); + if (!CarryKnown) + return std::unexpected(CarryKnown.error()); + auto Known = intersectMasks(*LeftKnown, *RightKnown); + if (!Known) + return std::unexpected(Known.error()); + Known = intersectMasks(*Known, *CarryKnown); + if (!Known) + return std::unexpected(Known.error()); + + auto NotPossibleSumZero = PossibleSumZero->bitwiseNot(); + if (!NotPossibleSumZero) + return std::unexpected(NotPossibleSumZero.error()); + auto KnownZero = intersectMasks(*NotPossibleSumZero, *Known); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = intersectMasks(*PossibleSumOne, *Known); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + + if (Opcode == GenericOpcode::G_MUL) { + const auto Right = registerOperand(*Definition, 2); + if (!Right) + return Unknown; + auto LeftBits = getKnownBits(*Source, Depth + 1U); + if (!LeftBits) + return std::unexpected(LeftBits.error()); + auto RightBits = getKnownBits(*Right, Depth + 1U); + if (!RightBits) + return std::unexpected(RightBits.error()); + + auto LeftMaximum = LeftBits->Zero.bitwiseNot(); + if (!LeftMaximum) + return std::unexpected(LeftMaximum.error()); + auto RightMaximum = RightBits->Zero.bitwiseNot(); + if (!RightMaximum) + return std::unexpected(RightMaximum.error()); + auto MaximumProduct = multiplyMasks(*LeftMaximum, *RightMaximum); + if (!MaximumProduct) + return std::unexpected(MaximumProduct.error()); + const std::uint32_t LeadingZeroes = + MaximumProduct->Overflow + ? 0 + : BitWidth - static_cast<std::uint32_t>(MaximumProduct->Value.activeBitWidth()); + + auto LeftKnown = mergeMasks(LeftBits->Zero, LeftBits->One); + if (!LeftKnown) + return std::unexpected(LeftKnown.error()); + auto RightKnown = mergeMasks(RightBits->Zero, RightBits->One); + if (!RightKnown) + return std::unexpected(RightKnown.error()); + const std::uint32_t LeftTrailingKnown = countTrailingOnes(*LeftKnown); + const std::uint32_t RightTrailingKnown = countTrailingOnes(*RightKnown); + const std::uint32_t LeftTrailingZeroes = countTrailingOnes(LeftBits->Zero); + const std::uint32_t RightTrailingZeroes = countTrailingOnes(RightBits->Zero); + const std::uint32_t TrailingZeroes = LeftTrailingZeroes + RightTrailingZeroes; + const std::uint32_t SmallestOperand = + std::min(LeftTrailingKnown - LeftTrailingZeroes, RightTrailingKnown - RightTrailingZeroes); + const std::uint32_t ResultBitsKnown = std::min(SmallestOperand + TrailingZeroes, BitWidth); + + auto BottomKnown = multiplyMasks(LeftBits->One, RightBits->One); + if (!BottomKnown) + return std::unexpected(BottomKnown.error()); + auto LowMask = APInt::getLowBitsSet(BitWidth, ResultBitsKnown); + if (!LowMask) + return std::unexpected(LowMask.error()); + auto NotBottomKnown = BottomKnown->Value.bitwiseNot(); + if (!NotBottomKnown) + return std::unexpected(NotBottomKnown.error()); + auto KnownZero = intersectMasks(*NotBottomKnown, *LowMask); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto HighZero = highBitsMask(BitWidth, BitWidth - LeadingZeroes); + if (!HighZero) + return std::unexpected(HighZero.error()); + KnownZero = mergeMasks(*KnownZero, *HighZero); + if (!KnownZero) + return std::unexpected(KnownZero.error()); + auto KnownOne = intersectMasks(BottomKnown->Value, *LowMask); + if (!KnownOne) + return std::unexpected(KnownOne.error()); + return KnownBits{.Zero = std::move(*KnownZero), .One = std::move(*KnownOne)}; + } + if (Opcode == GenericOpcode::G_SHL || Opcode == GenericOpcode::G_LSHR || Opcode == GenericOpcode::G_ASHR) { const auto AmountReg = registerOperand(*Definition, 2); 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<Register> +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<APInt> 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<std::uint64_t> Words((static_cast<std::size_t>(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<APInt> 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<std::uint64_t> Words((static_cast<std::size_t>(BitWidth) + 63U) / 64U, 0); + Words[Bit / 64U] = std::uint64_t{1} << (Bit % 64U); + return APInt::create(BitWidth, Words); +} + [[nodiscard]] Expected<Register> buildICmpRegister(MachineIRBuilder &Builder, IntegerPredicate Predicate, LowLevelType ResultType, Register Left, @@ -1119,6 +1163,109 @@ Expected<void> 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<GenericOpcode>(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<Register>(); + const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>(); + 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<std::int64_t>(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<std::int64_t>(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<void> 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<void> LegalizerHelper::lowerDivRem(MachineInstr &Instruction) { return Block->removeInstruction(Instruction); } +Expected<void> LegalizerHelper::lowerBitCount(MachineInstr &Instruction) { + const GenericOpcode Generic = static_cast<GenericOpcode>(Instruction.opcode().value()); + MachineOperand *DestinationOperand = Instruction.operandAt(0); + MachineOperand *SourceOperand = Instruction.operandAt(1); + const Register *Destination = + DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<Register>(); + const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf<Register>(); + 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<bool> { + 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<void> { + 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<std::int64_t>(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<std::int64_t>(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<std::int64_t>(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<std::int64_t>(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<std::int64_t>(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<std::int64_t>(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<std::int64_t>(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<std::int64_t>(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<void> LegalizerHelper::lowerBswap(MachineInstr &Instruction) { const Register Destination = *Instruction.operandAt(0)->getIf<Register>(); const Register Source = *Instruction.operandAt(1)->getIf<Register>(); |