Index: include/llvm/CodeGen/GlobalISel/LegalizerHelper.h =================================================================== --- include/llvm/CodeGen/GlobalISel/LegalizerHelper.h +++ include/llvm/CodeGen/GlobalISel/LegalizerHelper.h @@ -49,6 +49,7 @@ }; LegalizerHelper(MachineFunction &MF); + LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI); /// Replace \p MI by a sequence of legal instructions that can implement the /// same operation. Note that this means \p MI may be deleted, so any iterator @@ -112,6 +113,8 @@ void extractParts(unsigned Reg, LLT Ty, int NumParts, SmallVectorImpl &VRegs); + LegalizeResult lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty); + MachineRegisterInfo &MRI; const LegalizerInfo &LI; }; Index: include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h =================================================================== --- include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h +++ include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h @@ -664,6 +664,11 @@ /// \return a MachineInstrBuilder for the newly created instruction. MachineInstrBuilder buildICmp(CmpInst::Predicate Pred, unsigned Res, unsigned Op0, unsigned Op1); + template + MachineInstrBuilder buildICmp(CmpInst::Predicate Pred, DstTy &&Dst, + UseArgsTy &&... UseArgs) { + return buildICmp(Pred, getDestFromArg(Dst), getRegFromArg(UseArgs)...); + } /// Build and insert a \p Res = G_FCMP \p Pred\p Op0, \p Op1 /// @@ -692,6 +697,10 @@ /// \return a MachineInstrBuilder for the newly created instruction. MachineInstrBuilder buildSelect(unsigned Res, unsigned Tst, unsigned Op0, unsigned Op1); + template + MachineInstrBuilder buildSelect(DstTy &&Dst, UseArgsTy &&... UseArgs) { + return buildSelect(getDestFromArg(Dst), getRegFromArg(UseArgs)...); + } /// Build and insert \p Res = G_INSERT_VECTOR_ELT \p Val, /// \p Elt, \p Idx Index: include/llvm/Target/GlobalISel/SelectionDAGCompat.td =================================================================== --- include/llvm/Target/GlobalISel/SelectionDAGCompat.td +++ include/llvm/Target/GlobalISel/SelectionDAGCompat.td @@ -83,6 +83,11 @@ def : GINodeEquiv; def : GINodeEquiv; def : GINodeEquiv; +def : GINodeEquiv; +def : GINodeEquiv; +def : GINodeEquiv; +def : GINodeEquiv; +def : GINodeEquiv; // Broadly speaking G_LOAD is equivalent to ISD::LOAD but there are some // complications that tablegen must take care of. For example, Predicates such Index: lib/CodeGen/GlobalISel/LegalizerHelper.cpp =================================================================== --- lib/CodeGen/GlobalISel/LegalizerHelper.cpp +++ lib/CodeGen/GlobalISel/LegalizerHelper.cpp @@ -17,6 +17,7 @@ #include "llvm/CodeGen/GlobalISel/CallLowering.h" #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetLowering.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/Support/Debug.h" @@ -33,6 +34,10 @@ MIRBuilder.setMF(MF); } +LegalizerHelper::LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI) + : MRI(MF.getRegInfo()), LI(LI) { + MIRBuilder.setMF(MF); +} LegalizerHelper::LegalizeResult LegalizerHelper::legalizeInstrStep(MachineInstr &MI) { LLVM_DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs())); @@ -984,6 +989,12 @@ return UnableToLegalize; } + case TargetOpcode::G_CTLZ_ZERO_UNDEF: + case TargetOpcode::G_CTTZ_ZERO_UNDEF: + case TargetOpcode::G_CTLZ: + case TargetOpcode::G_CTTZ: + case TargetOpcode::G_CTPOP: + return lowerBitCount(MI, TypeIdx, Ty); } } @@ -1024,3 +1035,111 @@ } } } + +LegalizerHelper::LegalizeResult +LegalizerHelper::lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty) { + unsigned Opc = MI.getOpcode(); + auto &TII = *MI.getMF()->getSubtarget().getInstrInfo(); + auto isLegalOrCustom = [this](const LegalityQuery &Q) { + auto QAction = LI.getAction(Q).Action; + return QAction == Legal || QAction == Custom; + }; + switch (Opc) { + default: + return UnableToLegalize; + case TargetOpcode::G_CTLZ_ZERO_UNDEF: { + // This trivially expands to CTLZ. + MI.setDesc(TII.get(TargetOpcode::G_CTLZ)); + MIRBuilder.recordInsertion(&MI); + return Legalized; + } + case TargetOpcode::G_CTLZ: { + unsigned SrcReg = MI.getOperand(1).getReg(); + unsigned Len = Ty.getSizeInBits(); + if (isLegalOrCustom({TargetOpcode::G_CTLZ_ZERO_UNDEF, {Ty}})) { + // If CTLZ_ZERO_UNDEF is legal or custom, emit that and a select with + // zero. + auto MIBCtlzZU = + MIRBuilder.buildInstr(TargetOpcode::G_CTLZ_ZERO_UNDEF, Ty, SrcReg); + auto MIBZero = MIRBuilder.buildConstant(Ty, 0); + auto MIBLen = MIRBuilder.buildConstant(Ty, Len); + auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1), + SrcReg, MIBZero); + MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen, + MIBCtlzZU); + MI.eraseFromParent(); + return Legalized; + } + // for now, we do this: + // x = x | (x >> 1); + // x = x | (x >> 2); + // ... + // x = x | (x >>16); + // x = x | (x >>32); // for 64-bit input + // return popcount(~x); + // + // Ref: "Hacker's Delight" by Henry Warren + unsigned Op = SrcReg; + for (unsigned i = 0; (1U << i) <= (Len / 2); ++i) { + auto MIBTmp3 = MIRBuilder.buildConstant(Ty, 1ULL << i); + auto MIBOp = MIRBuilder.buildInstr( + TargetOpcode::G_OR, Ty, Op, + MIRBuilder.buildInstr(TargetOpcode::G_LSHR, Ty, Op, MIBTmp3)); + Op = MIBOp->getOperand(0).getReg(); + } + auto MIBNot = MIRBuilder.buildInstr(TargetOpcode::G_XOR, Ty, Op, + MIRBuilder.buildConstant(Ty, -1)); + MIRBuilder.buildInstr(TargetOpcode::G_CTPOP, MI.getOperand(0).getReg(), + MIBNot); + MI.eraseFromParent(); + return Legalized; + } + case TargetOpcode::G_CTTZ_ZERO_UNDEF: { + // This trivially expands to CTTZ. + MI.setDesc(TII.get(TargetOpcode::G_CTTZ)); + MIRBuilder.recordInsertion(&MI); + return Legalized; + } + case TargetOpcode::G_CTTZ: { + unsigned SrcReg = MI.getOperand(1).getReg(); + unsigned Len = Ty.getSizeInBits(); + if (isLegalOrCustom({TargetOpcode::G_CTTZ_ZERO_UNDEF, {Ty}})) { + // If CTTZ_ZERO_UNDEF is legal or custom, emit that and a select with + // zero. + auto MIBCttzZU = + MIRBuilder.buildInstr(TargetOpcode::G_CTTZ_ZERO_UNDEF, Ty, SrcReg); + auto MIBZero = MIRBuilder.buildConstant(Ty, 0); + auto MIBLen = MIRBuilder.buildConstant(Ty, Len); + auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1), + SrcReg, MIBZero); + MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen, + MIBCttzZU); + MI.eraseFromParent(); + return Legalized; + } + // for now, we use: { return popcount(~x & (x - 1)); } + // unless the target has ctlz but not ctpop, in which case we use: + // { return 32 - nlz(~x & (x-1)); } + // Ref: "Hacker's Delight" by Henry Warren + auto MIBNot = MIRBuilder.buildInstr(TargetOpcode::G_XOR, Ty, SrcReg, + MIRBuilder.buildConstant(Ty, -1)); + auto MIBTmp = MIRBuilder.buildInstr( + TargetOpcode::G_AND, Ty, MIBNot, + MIRBuilder.buildInstr(TargetOpcode::G_SUB, Ty, SrcReg, + MIRBuilder.buildConstant(Ty, 1))); + if (!isLegalOrCustom({TargetOpcode::G_CTPOP, {Ty}}) && + isLegalOrCustom({TargetOpcode::G_CTLZ, {Ty}})) { + MIRBuilder.buildInstr( + TargetOpcode::G_SUB, MI.getOperand(0).getReg(), + MIRBuilder.buildConstant(Ty, Len), + MIRBuilder.buildInstr(TargetOpcode::G_CTLZ, Ty, MIBTmp)); + MI.eraseFromParent(); + return Legalized; + } + MIRBuilder.buildInstr(TargetOpcode::G_CTPOP, MI.getOperand(0).getReg(), + MIBTmp); + MI.eraseFromParent(); + return Legalized; + } + } +} Index: unittests/CodeGen/GlobalISel/CMakeLists.txt =================================================================== --- unittests/CodeGen/GlobalISel/CMakeLists.txt +++ unittests/CodeGen/GlobalISel/CMakeLists.txt @@ -12,4 +12,5 @@ add_llvm_unittest(GlobalISelTests LegalizerInfoTest.cpp PatternMatchTest.cpp + LegalizerHelperTest.cpp ) Index: unittests/CodeGen/GlobalISel/LegalizerHelperTest.h =================================================================== --- /dev/null +++ unittests/CodeGen/GlobalISel/LegalizerHelperTest.h @@ -0,0 +1,188 @@ +//===- LegalizerHelperTest.h +//-----------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/GlobalISel/LegalizerHelper.h" +#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h" +#include "llvm/CodeGen/GlobalISel/MIPatternMatch.h" +#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" +#include "llvm/CodeGen/GlobalISel/Utils.h" +#include "llvm/CodeGen/MIRParser/MIRParser.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/TargetFrameLowering.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/CodeGen/TargetLowering.h" +#include "llvm/CodeGen/TargetSubtargetInfo.h" +#include "llvm/Support/FileCheck.h" +#include "llvm/Support/SourceMgr.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Target/TargetOptions.h" +#include "gtest/gtest.h" + +using namespace llvm; +using namespace MIPatternMatch; + +void initLLVM() { + InitializeAllTargets(); + InitializeAllTargetMCs(); + InitializeAllAsmPrinters(); + InitializeAllAsmParsers(); + + PassRegistry *Registry = PassRegistry::getPassRegistry(); + initializeCore(*Registry); + initializeCodeGen(*Registry); +} + +/// Create a TargetMachine. As we lack a dedicated always available target for +/// unittests, we go for "AArch64". +std::unique_ptr createTargetMachine() { + Triple TargetTriple("aarch64--"); + std::string Error; + const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error); + if (!T) + return nullptr; + + TargetOptions Options; + return std::unique_ptr(T->createTargetMachine( + "AArch64", "", "", Options, None, None, CodeGenOpt::Aggressive)); +} + +std::unique_ptr parseMIR(LLVMContext &Context, + std::unique_ptr &MIR, + const TargetMachine &TM, StringRef MIRCode, + const char *FuncName, MachineModuleInfo &MMI) { + SMDiagnostic Diagnostic; + std::unique_ptr MBuffer = MemoryBuffer::getMemBuffer(MIRCode); + MIR = createMIRParser(std::move(MBuffer), Context); + if (!MIR) + return nullptr; + + std::unique_ptr M = MIR->parseIRModule(); + if (!M) + return nullptr; + + M->setDataLayout(TM.createDataLayout()); + + if (MIR->parseMachineFunctions(*M, MMI)) + return nullptr; + + return M; +} + +std::pair, std::unique_ptr> +createDummyModule(LLVMContext &Context, const TargetMachine &TM, + StringRef MIRFunc) { + SmallString<512> S; + StringRef MIRString = (Twine(R"MIR( +--- +... +name: func +registers: + - { id: 0, class: _ } + - { id: 1, class: _ } + - { id: 2, class: _ } + - { id: 3, class: _ } +body: | + bb.1: + %0(s64) = COPY $x0 + %1(s64) = COPY $x1 + %2(s64) = COPY $x2 +)MIR") + Twine(MIRFunc) + Twine("...\n")) + .toNullTerminatedStringRef(S); + std::unique_ptr MIR; + auto MMI = make_unique(&TM); + std::unique_ptr M = + parseMIR(Context, MIR, TM, MIRString, "func", *MMI); + return make_pair(std::move(M), std::move(MMI)); +} + +static MachineFunction *getMFFromMMI(const Module *M, + const MachineModuleInfo *MMI) { + Function *F = M->getFunction("func"); + auto *MF = MMI->getMachineFunction(*F); + return MF; +} + +static void collectCopies(SmallVectorImpl &Copies, + MachineFunction *MF) { + for (auto &MBB : *MF) + for (MachineInstr &MI : MBB) { + if (MI.getOpcode() == TargetOpcode::COPY) + Copies.push_back(MI.getOperand(0).getReg()); + } +} + +class LegalizerHelperTest : public ::testing::Test { +protected: + LegalizerHelperTest() : ::testing::Test() { + TM = createTargetMachine(); + if (!TM) + return; + ModuleMMIPair = createDummyModule(Context, *TM, ""); + MF = getMFFromMMI(ModuleMMIPair.first.get(), ModuleMMIPair.second.get()); + collectCopies(Copies, MF); + EntryMBB = &*MF->begin(); + B.setMF(*MF); + MRI = &MF->getRegInfo(); + B.setInsertPt(*EntryMBB, EntryMBB->end()); + } + LLVMContext Context; + std::unique_ptr TM; + MachineFunction *MF; + std::pair, std::unique_ptr> + ModuleMMIPair; + SmallVector Copies; + MachineBasicBlock *EntryMBB; + MachineIRBuilder B; + MachineRegisterInfo *MRI; +}; + +#define LInfoBuilder(Name, x) \ + class Name##Info : public LegalizerInfo { \ + public: \ + Name##Info(const TargetSubtargetInfo &ST) { \ + using namespace TargetOpcode; \ + const LLT s8 = LLT::scalar(8); \ + (void)s8; \ + const LLT s16 = LLT::scalar(16); \ + (void)s16; \ + const LLT s32 = LLT::scalar(32); \ + (void)s32; \ + const LLT s64 = LLT::scalar(64); \ + (void)s64; \ + x; \ + computeTables(); \ + } \ + }; + +static bool CheckMachineFunction(const MachineFunction &MF, + StringRef CheckStr) { + SmallString<512> Msg; + raw_svector_ostream OS(Msg); + MF.print(OS); + auto OutputBuf = MemoryBuffer::getMemBuffer(Msg, "Output", false); + auto CheckBuf = MemoryBuffer::getMemBuffer(CheckStr, ""); + SmallString<4096> CheckFileBuffer; + FileCheckRequest Req; + FileCheck FC(Req); + StringRef CheckFileText = + FC.CanonicalizeFile(*CheckBuf.get(), CheckFileBuffer); + SourceMgr SM; + SM.AddNewSourceBuffer(MemoryBuffer::getMemBuffer(CheckFileText, "CheckFile"), + SMLoc()); + Regex PrefixRE = FC.buildCheckPrefixRegex(); + std::vector CheckStrings; + FC.ReadCheckFile(SM, CheckFileText, PrefixRE, CheckStrings); + auto OutBuffer = OutputBuf->getBuffer(); + SM.AddNewSourceBuffer(std::move(OutputBuf), SMLoc()); + return FC.CheckInput(SM, OutBuffer, CheckStrings); +} Index: unittests/CodeGen/GlobalISel/LegalizerHelperTest.cpp =================================================================== --- /dev/null +++ unittests/CodeGen/GlobalISel/LegalizerHelperTest.cpp @@ -0,0 +1,191 @@ +//===- PatternMatchTest.cpp -----------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "LegalizerHelperTest.h" + +namespace { + +// Test CTTZ expansion when CTTZ_ZERO_UNDEF is legal or custom, +// in which case it becomes CTTZ_ZERO_UNDEF with select. +TEST_F(LegalizerHelperTest, LowerBitCountingCTTZ0) { + if (!TM) + return; + + // Declare your legalization info + LInfoBuilder(A, + getActionDefinitionsBuilder(G_CTTZ_ZERO_UNDEF).legalFor({s64});); + // Build Instr + auto MIBCTTZ = B.buildInstr(TargetOpcode::G_CTTZ, LLT::scalar(64), Copies[0]); + AInfo Info(MF->getSubtarget()); + LegalizerHelper Helper(*MF, Info); + // Perform Legalization + ASSERT_TRUE(Helper.lower(*MIBCTTZ, 0, LLT::scalar(64)) == + LegalizerHelper::LegalizeResult::Legalized); + + auto CheckStr = R"( + CHECK: [[CZU:%[0-9]+]]:_(s64) = G_CTTZ_ZERO_UNDEF + CHECK: [[ZERO:%[0-9]+]]:_(s64) = G_CONSTANT i64 0 + CHECK: [[SIXTY4:%[0-9]+]]:_(s64) = G_CONSTANT i64 64 + CHECK: [[CMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), %0:_(s64), [[ZERO]] + CHECK: [[SEL:%[0-9]+]]:_(s64) = G_SELECT [[CMP]]:_(s1), [[SIXTY4]]:_, [[CZU]] + )"; + + // Check + ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr)); +} + +// CTTZ expansion in terms of CTLZ +TEST_F(LegalizerHelperTest, LowerBitCountingCTTZ1) { + if (!TM) + return; + + // Declare your legalization info + LInfoBuilder(A, getActionDefinitionsBuilder(G_CTLZ).legalFor({s64});); + // Build Instr + auto MIBCTTZ = B.buildInstr(TargetOpcode::G_CTTZ, LLT::scalar(64), Copies[0]); + AInfo Info(MF->getSubtarget()); + LegalizerHelper Helper(*MF, Info); + // Perform Legalization + ASSERT_TRUE(Helper.lower(*MIBCTTZ, 0, LLT::scalar(64)) == + LegalizerHelper::LegalizeResult::Legalized); + + auto CheckStr = R"( + CHECK: [[NEG1:%[0-9]+]]:_(s64) = G_CONSTANT i64 -1 + CHECK: [[NOT:%[0-9]+]]:_(s64) = G_XOR %0:_, [[NEG1]] + CHECK: [[ONE:%[0-9]+]]:_(s64) = G_CONSTANT i64 1 + CHECK: [[SUB1:%[0-9]+]]:_(s64) = G_SUB %0:_, [[ONE]] + CHECK: [[AND1:%[0-9]+]]:_(s64) = G_AND [[NOT]]:_, [[SUB1]]:_ + CHECK: [[CST64:%[0-9]+]]:_(s64) = G_CONSTANT i64 64 + CHECK: [[CTLZ:%[0-9]+]]:_(s64) = G_CTLZ [[AND1]]:_ + CHECK: G_SUB [[CST64]]:_, [[CTLZ]]:_ + )"; + + // Check + ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr)); +} + +// CTTZ expansion in terms of CTPOP +TEST_F(LegalizerHelperTest, LowerBitCountingCTTZ2) { + if (!TM) + return; + + // Declare your legalization info + LInfoBuilder(A, getActionDefinitionsBuilder(G_CTPOP).legalFor({s64});); + // Build + auto MIBCTTZ = B.buildInstr(TargetOpcode::G_CTTZ, LLT::scalar(64), Copies[0]); + AInfo Info(MF->getSubtarget()); + LegalizerHelper Helper(*MF, Info); + ASSERT_TRUE(Helper.lower(*MIBCTTZ, 0, LLT::scalar(64)) == + LegalizerHelper::LegalizeResult::Legalized); + + auto CheckStr = R"( + CHECK: [[NEG1:%[0-9]+]]:_(s64) = G_CONSTANT i64 -1 + CHECK: [[NOT:%[0-9]+]]:_(s64) = G_XOR %0:_, [[NEG1]] + CHECK: [[ONE:%[0-9]+]]:_(s64) = G_CONSTANT i64 1 + CHECK: [[SUB1:%[0-9]+]]:_(s64) = G_SUB %0:_, [[ONE]] + CHECK: [[AND1:%[0-9]+]]:_(s64) = G_AND [[NOT]]:_, [[SUB1]]:_ + CHECK: [[POP:%[0-9]+]]:_(s64) = G_CTPOP [[AND1]] + )"; + + // Check + ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr)); +} + +// CTTZ_ZERO_UNDEF expansion in terms of CTTZ +TEST_F(LegalizerHelperTest, LowerBitCountingCTTZ3) { + if (!TM) + return; + + // Declare your legalization info + LInfoBuilder(A, getActionDefinitionsBuilder(G_CTTZ).legalFor({s64});); + // Build + auto MIBCTTZ = + B.buildInstr(TargetOpcode::G_CTTZ_ZERO_UNDEF, LLT::scalar(64), Copies[0]); + AInfo Info(MF->getSubtarget()); + LegalizerHelper Helper(*MF, Info); + ASSERT_TRUE(Helper.lower(*MIBCTTZ, 0, LLT::scalar(64)) == + LegalizerHelper::LegalizeResult::Legalized); + + auto CheckStr = R"( + CHECK: CTTZ + )"; + + // Check + ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr)); +} + +// CTLZ expansion in terms of CTLZ_ZERO_UNDEF +TEST_F(LegalizerHelperTest, LowerBitCountingCTLZ0) { + if (!TM) + return; + + // Declare your legalization info + LInfoBuilder(A, + getActionDefinitionsBuilder(G_CTLZ_ZERO_UNDEF).legalFor({s64});); + // Build + auto MIBCTLZ = B.buildInstr(TargetOpcode::G_CTLZ, LLT::scalar(64), Copies[0]); + AInfo Info(MF->getSubtarget()); + LegalizerHelper Helper(*MF, Info); + ASSERT_TRUE(Helper.lower(*MIBCTLZ, 0, LLT::scalar(64)) == + LegalizerHelper::LegalizeResult::Legalized); + + auto CheckStr = R"( + CHECK: [[CZU:%[0-9]+]]:_(s64) = G_CTLZ_ZERO_UNDEF + CHECK: [[ZERO:%[0-9]+]]:_(s64) = G_CONSTANT i64 0 + CHECK: [[SIXTY4:%[0-9]+]]:_(s64) = G_CONSTANT i64 64 + CHECK: [[CMP:%[0-9]+]]:_(s1) = G_ICMP intpred(eq), %0:_(s64), [[ZERO]] + CHECK: [[SEL:%[0-9]+]]:_(s64) = G_SELECT [[CMP]]:_(s1), [[SIXTY4]]:_, [[CZU]] + )"; + + // Check + ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr)); +} + +// CTLZ expansion +TEST_F(LegalizerHelperTest, LowerBitCountingCTLZ1) { + if (!TM) + return; + + // Declare your legalization info + LInfoBuilder(A, getActionDefinitionsBuilder(G_CTPOP).legalFor({s64});); + // Build + auto MIBCTLZ = B.buildInstr(TargetOpcode::G_CTLZ, LLT::scalar(64), Copies[0]); + AInfo Info(MF->getSubtarget()); + LegalizerHelper Helper(*MF, Info); + ASSERT_TRUE(Helper.lower(*MIBCTLZ, 0, LLT::scalar(64)) == + LegalizerHelper::LegalizeResult::Legalized); + + auto CheckStr = R"( + CHECK: G_CONSTANT i64 1 + CHECK: G_LSHR + CHECK: G_OR + CHECK: G_CONSTANT i64 2 + CHECK: G_LSHR + CHECK: G_OR + CHECK: G_CONSTANT i64 4 + CHECK: G_LSHR + CHECK: G_OR + CHECK: G_CONSTANT i64 8 + CHECK: G_LSHR + CHECK: G_OR + CHECK: G_CONSTANT i64 16 + CHECK: G_LSHR + CHECK: G_OR + CHECK: G_CONSTANT i64 32 + CHECK: G_LSHR + CHECK: G_OR + CHECK: G_CONSTANT i64 -1 + CHECK: G_XOR + CHECK: G_CTPOP + )"; + + // Check + ASSERT_TRUE(CheckMachineFunction(*MF, CheckStr)); +} +} // namespace