[GISel]:Add Opcodes for CTLZ/CTTZ/CTPOP

[aditya_nandakumar]

Summary

Add IRTranslator support to translate these known intrinsics into GISel opcodes.

[arsenm]

include/llvm/Support/TargetOpcodes.def

470–471

Should we really preserve this SelectionDAGism or just make the zero is undef bit be an immediate operand to the instruction like the intrinsic?

[aditya_nandakumar]

include/llvm/Support/TargetOpcodes.def

470–471

I think having two opcodes is explicit and is a little easier to work with - we don't usually have immediates in GISel instructions - and constants are encoded through a reg defining G_CONSTANT which makes it a little inconvenient to use. It probably also might make importing tablegen patterns slightly easier.
I'm okay with either way if someone has a strong enough opinion.

[aemerson]

test/TableGen/trydecode-emission.td

37

Why are these tests changing?

[aditya_nandakumar]

test/TableGen/trydecode-emission.td

37

I believe these changes are due to increase in the number of opcodes.

[dsanders]

include/llvm/Support/TargetOpcodes.def

470–471

We'll need it for legalization. Typically only one or the other is legal and we can't do context-dependent legalization.

test/TableGen/trydecode-emission.td

37

We hit this out-of-tree a couple weeks ago, most of the changes are because the TryDecode/Decode are one byte larger and those are one byte larger because there are more opcodes before InstA.

39–40

The new bytes should be checked with {{[0-9]+}}

[aditya_nandakumar]

Ping?

[rtereshin]

LGTM

[aditya_nandakumar]

Submitted in r338944

include/llvm/Support/TargetOpcodes.def

 HANDLE_TARGET_OPCODE(G_INSERT_VECTOR_ELT)
 
 /// Generic extractelement.
 HANDLE_TARGET_OPCODE(G_EXTRACT_VECTOR_ELT)
 
 /// Generic shufflevector.
 HANDLE_TARGET_OPCODE(G_SHUFFLE_VECTOR)
 
+/// Generic count trailing zeroes.
+HANDLE_TARGET_OPCODE(G_CTTZ)
+
+/// Same as above, undefined for zero inputs.
+HANDLE_TARGET_OPCODE(G_CTTZ_ZERO_UNDEF)
+
+/// Generic count leading zeroes.
+HANDLE_TARGET_OPCODE(G_CTLZ)
+
+/// Same as above, undefined for zero inputs.
+HANDLE_TARGET_OPCODE(G_CTLZ_ZERO_UNDEF)
+
+/// Generic count bits.
+HANDLE_TARGET_OPCODE(G_CTPOP)
+
 /// Generic byte swap.
 HANDLE_TARGET_OPCODE(G_BSWAP)
 
 /// Generic AddressSpaceCast.
 HANDLE_TARGET_OPCODE(G_ADDRSPACE_CAST)
 
 // TODO: Add more generic opcodes as we move along.
 
 /// Marker for the end of the generic opcode.
 /// This is used to check if an opcode is in the range of the
 /// generic opcodes.
 HANDLE_TARGET_OPCODE_MARKER(PRE_ISEL_GENERIC_OPCODE_END, G_ADDRSPACE_CAST)
 
 /// BUILTIN_OP_END - This must be the last enum value in this list.
 /// The target-specific post-isel opcode values start here.
 HANDLE_TARGET_OPCODE_MARKER(GENERIC_OP_END, PRE_ISEL_GENERIC_OPCODE_END)

include/llvm/Target/GenericOpcodes.td

 def G_VAARG : GenericInstruction {
   let OutOperandList = (outs type0:$val);
   let InOperandList = (ins type1:$list, unknown:$align);
   let hasSideEffects = 0;
   let mayLoad = 1;
   let mayStore = 1;
 }
 
+def G_CTLZ : GenericInstruction {
+  let OutOperandList = (outs type0:$dst);
+  let InOperandList = (ins type0:$src);
+  let hasSideEffects = 0;
+}
+
+def G_CTLZ_ZERO_UNDEF : GenericInstruction {
+  let OutOperandList = (outs type0:$dst);
+  let InOperandList = (ins type0:$src);
+  let hasSideEffects = 0;
+}
+
+def G_CTTZ : GenericInstruction {
+  let OutOperandList = (outs type0:$dst);
+  let InOperandList = (ins type0:$src);
+  let hasSideEffects = 0;
+}
+
+def G_CTTZ_ZERO_UNDEF : GenericInstruction {
+  let OutOperandList = (outs type0:$dst);
+  let InOperandList = (ins type0:$src);
+  let hasSideEffects = 0;
+}
+
+def G_CTPOP : GenericInstruction {
+  let OutOperandList = (outs type0:$dst);
+  let InOperandList = (ins type0:$src);
+  let hasSideEffects = 0;
+}
+
 def G_BSWAP : GenericInstruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins type0:$src);
   let hasSideEffects = 0;
 }
 
 def G_ADDRSPACE_CAST : GenericInstruction {
   let OutOperandList = (outs type0:$dst);

lib/CodeGen/GlobalISel/IRTranslator.cpp

MIRBuilder.buildStore(
         GuardVal, getOrCreateVReg(*Slot),
         *MF->getMachineMemOperand(
             MachinePointerInfo::getFixedStack(*MF,
                                               getOrCreateFrameIndex(*Slot)),
             MachineMemOperand::MOStore | MachineMemOperand::MOVolatile,
             PtrTy.getSizeInBits() / 8, 8));
     return true;
   }
+  case Intrinsic::cttz:
+  case Intrinsic::ctlz: {
+    ConstantInt *Cst = cast<ConstantInt>(CI.getArgOperand(1));
+    bool isTrailing = ID == Intrinsic::cttz;
+    unsigned Opcode = isTrailing
+                          ? Cst->isZero() ? TargetOpcode::G_CTTZ
+                                          : TargetOpcode::G_CTTZ_ZERO_UNDEF
+                          : Cst->isZero() ? TargetOpcode::G_CTLZ
+                                          : TargetOpcode::G_CTLZ_ZERO_UNDEF;
+    MIRBuilder.buildInstr(Opcode)
+        .addDef(getOrCreateVReg(CI))
+        .addUse(getOrCreateVReg(*CI.getArgOperand(0)));
+    return true;
+  }
+  case Intrinsic::ctpop: {
+    MIRBuilder.buildInstr(TargetOpcode::G_CTPOP)
+        .addDef(getOrCreateVReg(CI))
+        .addUse(getOrCreateVReg(*CI.getArgOperand(0)));
+    return true;
+  }
   }
   return false;
 }
 
 bool IRTranslator::translateInlineAsm(const CallInst &CI,
                                       MachineIRBuilder &MIRBuilder) {
   const InlineAsm &IA = cast<InlineAsm>(*CI.getCalledValue());
   if (!IA.getConstraintString().empty())

test/CodeGen/AArch64/GlobalISel/arm64-irtranslator.ll

 ; CHECK-LABEL: name: test_fabs_intrin
 ; CHECK: [[A:%[0-9]+]]:_(s32) = COPY $s0
 ; CHECK: [[RES:%[0-9]+]]:_(s32) = G_FABS [[A]]
 ; CHECK: $s0 = COPY [[RES]]
   %res = call float @llvm.fabs.f32(float %a)
   ret float %res
 }
 
+declare i32 @llvm.ctlz.i32(i32, i1)
+define i32 @test_ctlz_intrinsic_zero_not_undef(i32 %a) {
+; CHECK-LABEL: name: test_ctlz_intrinsic_zero_not_undef
+; CHECK: [[A:%[0-9]+]]:_(s32) = COPY $w0
+; CHECK: [[RES:%[0-9]+]]:_(s32) = G_CTLZ [[A]]
+; CHECK: $w0 = COPY [[RES]]
+  %res = call i32 @llvm.ctlz.i32(i32 %a, i1 0)
+  ret i32 %res
+}
+
+declare i32 @llvm.cttz.i32(i32, i1)
+define i32 @test_cttz_intrinsic_zero_undef(i32 %a) {
+; CHECK-LABEL: name: test_cttz_intrinsic_zero_undef
+; CHECK: [[A:%[0-9]+]]:_(s32) = COPY $w0
+; CHECK: [[RES:%[0-9]+]]:_(s32) = G_CTTZ_ZERO_UNDEF [[A]]
+; CHECK: $w0 = COPY [[RES]]
+  %res = call i32 @llvm.cttz.i32(i32 %a, i1 1)
+  ret i32 %res
+}
+
+declare i32 @llvm.ctpop.i32(i32)
+define i32 @test_ctpop_intrinsic(i32 %a) {
+; CHECK-LABEL: name: test_ctpop
+; CHECK: [[A:%[0-9]+]]:_(s32) = COPY $w0
+; CHECK: [[RES:%[0-9]+]]:_(s32) = G_CTPOP [[A]]
+; CHECK: $w0 = COPY [[RES]]
+  %res = call i32 @llvm.ctpop.i32(i32 %a)
+  ret i32 %res
+}
+
 declare void @llvm.lifetime.start.p0i8(i64, i8*)
 declare void @llvm.lifetime.end.p0i8(i64, i8*)
 define void @test_lifetime_intrin() {
 ; CHECK-LABEL: name: test_lifetime_intrin
 ; CHECK: RET_ReallyLR
   %slot = alloca i8, i32 4
   call void @llvm.lifetime.start.p0i8(i64 0, i8* %slot)
   call void @llvm.lifetime.end.p0i8(i64 0, i8* %slot)

test/CodeGen/AArch64/GlobalISel/legalizer-info-validation.mir

 # DEBUG:      .. type index coverage check SKIPPED: no rules defined
 #
 # DEBUG-NEXT: G_EXTRACT_VECTOR_ELT (opcode {{[0-9]+}}): 3 type indices
 # DEBUG:      .. type index coverage check SKIPPED: no rules defined
 #
 # DEBUG-NEXT: G_SHUFFLE_VECTOR (opcode {{[0-9]+}}): 3 type indices
 # DEBUG:      .. type index coverage check SKIPPED: no rules defined
 #
+# DEBUG-NEXT: G_CTTZ (opcode {{[0-9]+}}): 1 type index
+# DEBUG:      .. type index coverage check SKIPPED: no rules defined
+#
+# DEBUG-NEXT: G_CTTZ_ZERO_UNDEF (opcode {{[0-9]+}}): 1 type index
+# DEBUG:      .. type index coverage check SKIPPED: no rules defined
+#
+# DEBUG-NEXT: G_CTLZ (opcode {{[0-9]+}}): 1 type index
+# DEBUG:      .. type index coverage check SKIPPED: no rules defined
+#
+# DEBUG-NEXT: G_CTLZ_ZERO_UNDEF (opcode {{[0-9]+}}): 1 type index
+# DEBUG:      .. type index coverage check SKIPPED: no rules defined
+#
+# DEBUG-NEXT: G_CTPOP (opcode {{[0-9]+}}): 1 type index
+# DEBUG:      .. type index coverage check SKIPPED: no rules defined
+#
 # DEBUG-NEXT: G_BSWAP (opcode {{[0-9]+}}): 1 type index
 # DEBUG:      .. the first uncovered type index: 1, OK
 
 # CHECK-NOT: ill-defined
 
 ---
 name: dummy
 body: |
   bb.0:
 ...

test/TableGen/trydecode-emission.td

 def InstB : TestInstruction {
   let Inst = {0,0,0,0,0,0,?,?};
   let AsmString = "InstB";
   let DecoderMethod = "DecodeInstB";
   let hasCompleteDecoder = 0;
 }
 
 // CHECK:      /* 0 */       MCD::OPC_ExtractField, 4, 4,  // Inst{7-4} ...
-// CHECK-NEXT: /* 3 */       MCD::OPC_FilterValue, 0, 14, 0, // Skip to: 21
-// CHECK-NEXT: /* 7 */       MCD::OPC_CheckField, 2, 2, 0, 5, 0, // Skip to: 18
-// CHECK-NEXT: /* 13 */      MCD::OPC_TryDecode, {{[0-9]+}}, 0, 0, 0, // Opcode: InstB, skip to: 18
-// CHECK-NEXT: /* 18 */      MCD::OPC_Decode, {{[0-9]+}}, 1, // Opcode: InstA
-// CHECK-NEXT: /* 21 */      MCD::OPC_Fail,
+// CHECK-NEXT: /* 3 */       MCD::OPC_FilterValue, 0, 16, 0, // Skip to: 23
+// CHECK-NEXT: /* 7 */       MCD::OPC_CheckField, 2, 2, 0, 6, 0, // Skip to: 19
+// CHECK-NEXT: /* 13 */      MCD::OPC_TryDecode, {{[0-9]+}}, 1, 0, 0, 0, // Opcode: InstB, skip to: 19
+// CHECK-NEXT: /* 19 */      MCD::OPC_Decode, {{[0-9]+}}, 1, 1, // Opcode: InstA
+// CHECK-NEXT: /* 23 */      MCD::OPC_Fail,
 
 // CHECK: if (DecodeInstB(MI, insn, Address, Decoder) == MCDisassembler::Fail) { DecodeComplete = false; return MCDisassembler::Fail; }

test/TableGen/trydecode-emission2.td

 def InstB : TestInstruction {
   let Inst = {0,0,0,?,?,0,1,1};
   let AsmString = "InstB";
   let DecoderMethod = "DecodeInstB";
   let hasCompleteDecoder = 0;
 }
 
 // CHECK:      /* 0 */       MCD::OPC_ExtractField, 2, 1,  // Inst{2} ...
-// CHECK-NEXT: /* 3 */       MCD::OPC_FilterValue, 0, 29, 0, // Skip to: 36
+// CHECK-NEXT: /* 3 */       MCD::OPC_FilterValue, 0, 31, 0, // Skip to: 38
 // CHECK-NEXT: /* 7 */       MCD::OPC_ExtractField, 5, 3,  // Inst{7-5} ...
-// CHECK-NEXT: /* 10 */      MCD::OPC_FilterValue, 0, 22, 0, // Skip to: 36
-// CHECK-NEXT: /* 14 */      MCD::OPC_CheckField, 0, 2, 3, 5, 0, // Skip to: 25
-// CHECK-NEXT: /* 20 */      MCD::OPC_TryDecode, {{[0-9]+}}, 0, 0, 0, // Opcode: InstB, skip to: 25
-// CHECK-NEXT: /* 25 */      MCD::OPC_CheckField, 3, 2, 0, 5, 0, // Skip to: 36
-// CHECK-NEXT: /* 31 */      MCD::OPC_TryDecode, {{[0-9]+}}, 1, 0, 0, // Opcode: InstA, skip to: 36
-// CHECK-NEXT: /* 36 */      MCD::OPC_Fail,
+// CHECK-NEXT: /* 10 */      MCD::OPC_FilterValue, 0, 24, 0, // Skip to: 38
+// CHECK-NEXT: /* 14 */      MCD::OPC_CheckField, 0, 2, 3, 6, 0, // Skip to: 26
+// CHECK-NEXT: /* 20 */      MCD::OPC_TryDecode, {{[0-9]+}}, 1, 0, 0, 0, // Opcode: InstB, skip to: 26
+// CHECK-NEXT: /* 26 */      MCD::OPC_CheckField, 3, 2, 0, 6, 0, // Skip to: 38
+// CHECK-NEXT: /* 32 */      MCD::OPC_TryDecode, {{[0-9]+}}, 1, 1, 0, 0, // Opcode: InstA, skip to: 38
+// CHECK-NEXT: /* 38 */      MCD::OPC_Fail,
 
 // CHECK: if (DecodeInstB(MI, insn, Address, Decoder) == MCDisassembler::Fail) { DecodeComplete = false; return MCDisassembler::Fail; }
 // CHECK: if (DecodeInstA(MI, insn, Address, Decoder) == MCDisassembler::Fail) { DecodeComplete = false; return MCDisassembler::Fail; }

test/TableGen/trydecode-emission3.td

def InstB : TestInstruction {
   bits<2> op;
   let Inst{7-2} = {0,0,0,0,0,0};
   let Inst{1-0} = op;
   let OutOperandList = (outs InstBOp:$op);
   let AsmString = "InstB";
 }
 
 // CHECK:      /* 0 */       MCD::OPC_ExtractField, 4, 4,  // Inst{7-4} ...
-// CHECK-NEXT: /* 3 */       MCD::OPC_FilterValue, 0, 14, 0, // Skip to: 21
-// CHECK-NEXT: /* 7 */       MCD::OPC_CheckField, 2, 2, 0, 5, 0, // Skip to: 18
-// CHECK-NEXT: /* 13 */      MCD::OPC_TryDecode, {{[0-9]+}}, 0, 0, 0, // Opcode: InstB, skip to: 18
-// CHECK-NEXT: /* 18 */      MCD::OPC_Decode, {{[0-9]+}}, 1, // Opcode: InstA
-// CHECK-NEXT: /* 21 */      MCD::OPC_Fail,
+// CHECK-NEXT: /* 3 */       MCD::OPC_FilterValue, 0, 16, 0, // Skip to: 23
+// CHECK-NEXT: /* 7 */       MCD::OPC_CheckField, 2, 2, 0, 6, 0, // Skip to: 19
+// CHECK-NEXT: /* 13 */      MCD::OPC_TryDecode, {{[0-9]+}}, 1, 0, 0, 0, // Opcode: InstB, skip to: 19
+// CHECK-NEXT: /* 19 */      MCD::OPC_Decode, {{[0-9]+}}, 1, 1, // Opcode: InstA
+// CHECK-NEXT: /* 23 */      MCD::OPC_Fail,
 
 // CHECK: if (DecodeInstBOp(MI, tmp, Address, Decoder) == MCDisassembler::Fail) { DecodeComplete = false; return MCDisassembler::Fail; }