[PowerPC][Power10] Implement Count Leading/Trailing Zeroes Builtins under bit Mask in LLVM/Clang

[amyk]

Summary

This patch implements builtins for the following prototypes:

unsigned long long __builtin_cntlzdm (unsigned long long, unsigned long long)
unsigned long long __builtin_cnttzdm (unsigned long long, unsigned long long)
vector unsigned long long vec_cntlzm (vector unsigned long long, vector unsigned long long)
vector unsigned long long vec_cnttzm (vector unsigned long long, vector unsigned long long)

Depends on D80935

[lebedev.ri]

Why not lower it to @llvm.cttz(and(a, b))?

[nemanjai]

In D80941#2066931, @lebedev.ri wrote:

Why not lower it to @llvm.cttz(and(a, b))?

That's a great idea. Particularly in the back end where this pattern can appear irrespective of the use of the builtins.

[amyk]

Addressed review comment of lowering the function prototypes to use @llvm.ct[t|l]z and and.

[nemanjai]

Amy, I am really sorry. I initially did not read the description of the instructions in the ISA carefully. The semantics of these instructions are not actually (op (and a, b)). The mask is used to determine if a leading/trailing zero is counted or skipped.
Take for example the following two binary values:

Mask:  1001111
Value: 0010011

the result of cntlzdm Value, Mask should be 3 whereas the result of (ctlz (and Value, Mask)) would be 5. Namely, the instruction will count the first leading zero, ignore the next two bits and then count the next two zeros.

So you will need to revert back to the initial implementation. I am so sorry about going back and forth like this.

[amyk]

Revert back to the initial implementation of the patch. Thanks Nemanja for clarifying.

[nemanjai]

LGTM. Thanks Amy.

clang/include/clang/Basic/BuiltinsPPC.def

 // P10 Vector Parallel Bits built-ins.
 BUILTIN(__builtin_altivec_vpdepd, "V2ULLiV2ULLiV2ULLi", "")
 BUILTIN(__builtin_altivec_vpextd, "V2ULLiV2ULLiV2ULLi", "")
 
 // P10 Vector Clear Bytes built-ins.
 BUILTIN(__builtin_altivec_vclrlb, "V16cV16cUi", "")
 BUILTIN(__builtin_altivec_vclrrb, "V16cV16cUi", "")
 
+// P10 Vector Count Leading / Trailing Zeroes under bit Mask built-ins.
+BUILTIN(__builtin_altivec_vclzdm, "V2ULLiV2ULLiV2ULLi", "")
+BUILTIN(__builtin_altivec_vctzdm, "V2ULLiV2ULLiV2ULLi", "")
+
 // VSX built-ins.
 
 BUILTIN(__builtin_vsx_lxvd2x, "V2divC*", "")
 BUILTIN(__builtin_vsx_lxvw4x, "V4iivC*", "")
 BUILTIN(__builtin_vsx_lxvd2x_be, "V2dSLLivC*", "")
 BUILTIN(__builtin_vsx_lxvw4x_be, "V4iSLLivC*", "")
 
 BUILTIN(__builtin_vsx_stxvd2x, "vV2div*", "")

 // Scalar built-ins
 BUILTIN(__builtin_divwe, "SiSiSi", "")
 BUILTIN(__builtin_divweu, "UiUiUi", "")
 BUILTIN(__builtin_divde, "SLLiSLLiSLLi", "")
 BUILTIN(__builtin_divdeu, "ULLiULLiULLi", "")
 BUILTIN(__builtin_bpermd, "SLLiSLLiSLLi", "")
 BUILTIN(__builtin_pdepd, "ULLiULLiULLi", "")
 BUILTIN(__builtin_pextd, "ULLiULLiULLi", "")
+BUILTIN(__builtin_cntlzdm, "ULLiULLiULLi", "")
+BUILTIN(__builtin_cnttzdm, "ULLiULLiULLi", "")
 
 // Vector int128 (un)pack
 BUILTIN(__builtin_unpack_vector_int128, "ULLiV1LLLii", "")
 BUILTIN(__builtin_pack_vector_int128, "V1LLLiULLiULLi", "")
 
 // Set the floating point rounding mode
 BUILTIN(__builtin_setrnd, "di", "")
 
 // Cache built-ins
 BUILTIN(__builtin_dcbf, "vvC*", "")
 
 // FIXME: Obviously incomplete.
 
 #undef BUILTIN

clang/lib/Headers/altivec.h

 static __inline__ vector unsigned char __ATTRS_o_ai
 vec_clrr(vector unsigned char __a, unsigned int __n) {
 #ifdef __LITTLE_ENDIAN__
   return __builtin_altivec_vclrlb((vector signed char)__a, __n);
 #else
   return __builtin_altivec_vclrrb((vector signed char)__a, __n);
 #endif
 }
+
+/* vec_cntlzm */
+
+static __inline__ vector unsigned long long __ATTRS_o_ai
+vec_cntlzm(vector unsigned long long __a, vector unsigned long long __b) {
+  return __builtin_altivec_vclzdm(__a, __b);
+}
+
+/* vec_cnttzm */
+
+static __inline__ vector unsigned long long __ATTRS_o_ai
+vec_cnttzm(vector unsigned long long __a, vector unsigned long long __b) {
+  return __builtin_altivec_vctzdm(__a, __b);
+}
+
 #endif /* __POWER10_VECTOR__ */
 
 #undef __ATTRS_o_ai
 
 #endif /* __ALTIVEC_H */

clang/test/CodeGen/builtins-ppc-p10.c

 // REQUIRES: powerpc-registered-target
 // RUN: %clang_cc1 -triple powerpc64-unknown-unknown -target-cpu pwr10 \
 // RUN: -emit-llvm %s -o - | FileCheck %s
 
 unsigned long long ulla, ullb;
 
 unsigned long long test_pdepd(void) {
   // CHECK: @llvm.ppc.pdepd
   return __builtin_pdepd(ulla, ullb);
 }
 
 unsigned long long test_pextd(void) {
   // CHECK: @llvm.ppc.pextd
   return __builtin_pextd(ulla, ullb);
 }
+
+unsigned long long test_cntlzdm(void) {
+  // CHECK: @llvm.ppc.cntlzdm
+  return __builtin_cntlzdm(ulla, ullb);
+}
+
+unsigned long long test_cnttzdm(void) {
+  // CHECK: @llvm.ppc.cnttzdm
+  return __builtin_cnttzdm(ulla, ullb);
+}

clang/test/CodeGen/builtins-ppc-p10vector.c

 
 vector unsigned char test_vec_clrr_uc(void) {
   // CHECK-BE: @llvm.ppc.altivec.vclrrb(<16 x i8>
   // CHECK-BE-NEXT: ret <16 x i8>
   // CHECK-LE: @llvm.ppc.altivec.vclrlb(<16 x i8>
   // CHECK-LE-NEXT: ret <16 x i8>
   return vec_clrr(vuca, uia);
 }
+
+vector unsigned long long test_vclzdm(void) {
+  // CHECK: @llvm.ppc.altivec.vclzdm(<2 x i64>
+  // CHECK-NEXT: ret <2 x i64>
+  return vec_cntlzm(vulla, vullb);
+}
+
+vector unsigned long long test_vctzdm(void) {
+  // CHECK: @llvm.ppc.altivec.vctzdm(<2 x i64>
+  // CHECK-NEXT: ret <2 x i64>
+  return vec_cnttzm(vulla, vullb);
+}

llvm/include/llvm/IR/IntrinsicsPowerPC.td

let TargetPrefix = "ppc" in {  // All intrinsics start with "llvm.ppc.".
   // Parallel Bits Deposit/Extract Doubleword Builtins.
   def int_ppc_pdepd
       : GCCBuiltin<"__builtin_pdepd">,
         Intrinsic <[llvm_i64_ty], [llvm_i64_ty, llvm_i64_ty], [IntrNoMem]>;
   def int_ppc_pextd
       : GCCBuiltin<"__builtin_pextd">,
         Intrinsic <[llvm_i64_ty], [llvm_i64_ty, llvm_i64_ty], [IntrNoMem]>;
 
+  // Count Leading / Trailing Zeroes under bit Mask Builtins.
+  def int_ppc_cntlzdm
+      : GCCBuiltin<"__builtin_cntlzdm">,
+        Intrinsic <[llvm_i64_ty], [llvm_i64_ty, llvm_i64_ty], [IntrNoMem]>;
+  def int_ppc_cnttzdm
+      : GCCBuiltin<"__builtin_cnttzdm">,
+        Intrinsic <[llvm_i64_ty], [llvm_i64_ty, llvm_i64_ty], [IntrNoMem]>;
+
   def int_ppc_truncf128_round_to_odd
       : GCCBuiltin<"__builtin_truncf128_round_to_odd">,
         Intrinsic <[llvm_double_ty], [llvm_f128_ty], [IntrNoMem]>;
   def int_ppc_sqrtf128_round_to_odd
       : GCCBuiltin<"__builtin_sqrtf128_round_to_odd">,
         Intrinsic <[llvm_f128_ty], [llvm_f128_ty], [IntrNoMem]>;
   def int_ppc_addf128_round_to_odd
       : GCCBuiltin<"__builtin_addf128_round_to_odd">,
let TargetPrefix = "ppc" in {  // All PPC intrinsics start with "llvm.ppc.".
   def int_ppc_altivec_vsubeuqm : GCCBuiltin<"__builtin_altivec_vsubeuqm">,
               Intrinsic<[llvm_v1i128_ty],
                         [llvm_v1i128_ty, llvm_v1i128_ty, llvm_v1i128_ty],
                         [IntrNoMem]>;
   def int_ppc_altivec_vsubecuq : GCCBuiltin<"__builtin_altivec_vsubecuq">,
               Intrinsic<[llvm_v1i128_ty],
                         [llvm_v1i128_ty, llvm_v1i128_ty, llvm_v1i128_ty],
                         [IntrNoMem]>;
+
+  // P10 Vector Count Leading / Trailing Zeroes under bit Mask Builtins.
+  def int_ppc_altivec_vclzdm : GCCBuiltin<"__builtin_altivec_vclzdm">,
+              Intrinsic<[llvm_v2i64_ty], [llvm_v2i64_ty, llvm_v2i64_ty],
+                        [IntrNoMem]>;
+  def int_ppc_altivec_vctzdm : GCCBuiltin<"__builtin_altivec_vctzdm">,
+              Intrinsic<[llvm_v2i64_ty], [llvm_v2i64_ty, llvm_v2i64_ty],
+                        [IntrNoMem]>;
 }
 
 def int_ppc_altivec_vsl   : PowerPC_Vec_WWW_Intrinsic<"vsl">;
 def int_ppc_altivec_vslo  : PowerPC_Vec_WWW_Intrinsic<"vslo">;
 
 def int_ppc_altivec_vslb  : PowerPC_Vec_BBB_Intrinsic<"vslb">;
 def int_ppc_altivec_vslv  : PowerPC_Vec_BBB_Intrinsic<"vslv">;
 def int_ppc_altivec_vsrv  : PowerPC_Vec_BBB_Intrinsic<"vsrv">;

llvm/lib/Target/PowerPC/PPCInstrPrefix.td

def VPEXTD : VXForm_1<1421, (outs vrrc:$vD), (ins vrrc:$vA, vrrc:$vB),
                          [(set v2i64:$vD,
                          (int_ppc_altivec_vpextd v2i64:$vA, v2i64:$vB))]>;
    def PDEPD : XForm_6<31, 156, (outs g8rc:$rA), (ins g8rc:$rS, g8rc:$rB),
                        "pdepd $rA, $rS, $rB", IIC_IntGeneral,
                        [(set i64:$rA, (int_ppc_pdepd i64:$rS, i64:$rB))]>;
    def PEXTD : XForm_6<31, 188, (outs g8rc:$rA), (ins g8rc:$rS, g8rc:$rB),
                        "pextd $rA, $rS, $rB", IIC_IntGeneral,
                        [(set i64:$rA, (int_ppc_pextd i64:$rS, i64:$rB))]>;
+   def VCLZDM : VXForm_1<1924, (outs vrrc:$vD), (ins vrrc:$vA, vrrc:$vB),
+                         "vclzdm $vD, $vA, $vB", IIC_VecGeneral,
+                         [(set v2i64:$vD,
+                         (int_ppc_altivec_vclzdm v2i64:$vA, v2i64:$vB))]>;
+   def VCTZDM : VXForm_1<1988, (outs vrrc:$vD), (ins vrrc:$vA, vrrc:$vB),
+                         "vctzdm $vD, $vA, $vB", IIC_VecGeneral,
+                         [(set v2i64:$vD,
+                         (int_ppc_altivec_vctzdm v2i64:$vA, v2i64:$vB))]>;
+   def CNTLZDM : XForm_6<31, 59, (outs g8rc:$rA), (ins g8rc:$rS, g8rc:$rB),
+                         "cntlzdm $rA, $rS, $rB", IIC_IntGeneral,
+                         [(set i64:$rA,
+                         (int_ppc_cntlzdm i64:$rS, i64:$rB))]>;
+   def CNTTZDM : XForm_6<31, 571, (outs g8rc:$rA), (ins g8rc:$rS, g8rc:$rB),
+                         "cnttzdm $rA, $rS, $rB", IIC_IntGeneral,
+                         [(set i64:$rA,
+                         (int_ppc_cnttzdm i64:$rS, i64:$rB))]>;
    def XXGENPCVBM :
      XForm_XT6_IMM5_VB5<60, 916, (outs vsrc:$XT), (ins vrrc:$VRB, s5imm:$IMM),
                         "xxgenpcvbm $XT, $VRB, $IMM", IIC_VecGeneral, []>;
    def XXGENPCVHM :
      XForm_XT6_IMM5_VB5<60, 917, (outs vsrc:$XT), (ins vrrc:$VRB, s5imm:$IMM),
                         "xxgenpcvhm $XT, $VRB, $IMM", IIC_VecGeneral, []>;
    def XXGENPCVWM :
      XForm_XT6_IMM5_VB5<60, 948, (outs vsrc:$XT), (ins vrrc:$VRB, s5imm:$IMM),

llvm/test/CodeGen/PowerPC/p10-bit-manip-ops.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu \
 ; RUN:   -mcpu=pwr10 -ppc-asm-full-reg-names -ppc-vsr-nums-as-vr < %s | \
 ; RUN:   FileCheck %s
 
 ; These test cases aim to test the bit manipulation operations on Power10.
 
 declare <2 x i64> @llvm.ppc.altivec.vpdepd(<2 x i64>, <2 x i64>)
 declare <2 x i64> @llvm.ppc.altivec.vpextd(<2 x i64>, <2 x i64>)
 declare i64 @llvm.ppc.pdepd(i64, i64)
 declare i64 @llvm.ppc.pextd(i64, i64)
+declare <2 x i64> @llvm.ppc.altivec.vclzdm(<2 x i64>, <2 x i64>)
+declare <2 x i64> @llvm.ppc.altivec.vctzdm(<2 x i64>, <2 x i64>)
+declare i64 @llvm.ppc.cntlzdm(i64, i64)
+declare i64 @llvm.ppc.cnttzdm(i64, i64)
 
 define <2 x i64> @test_vpdepd(<2 x i64> %a, <2 x i64> %b) {
 ; CHECK-LABEL: test_vpdepd:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    vpdepd v2, v2, v3
 ; CHECK-NEXT:    blr
 entry:
   %tmp = tail call <2 x i64> @llvm.ppc.altivec.vpdepd(<2 x i64> %a, <2 x i64> %b)

 ; CHECK-LABEL: test_pextd:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK-NEXT:    pextd r3, r3, r4
 ; CHECK-NEXT:    blr
 entry:
   %tmp = tail call i64 @llvm.ppc.pextd(i64 %a, i64 %b)
   ret i64 %tmp
 }
+
+define <2 x i64> @test_vclzdm(<2 x i64> %a, <2 x i64> %b) {
+; CHECK-LABEL: test_vclzdm:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    vclzdm v2, v2, v3
+; CHECK-NEXT:    blr
+entry:
+  %tmp = tail call <2 x i64> @llvm.ppc.altivec.vclzdm(<2 x i64> %a, <2 x i64> %b)
+  ret <2 x i64> %tmp
+}
+
+define <2 x i64> @test_vctzdm(<2 x i64> %a, <2 x i64> %b) {
+; CHECK-LABEL: test_vctzdm:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    vctzdm v2, v2, v3
+; CHECK-NEXT:    blr
+entry:
+  %tmp = tail call <2 x i64> @llvm.ppc.altivec.vctzdm(<2 x i64> %a, <2 x i64> %b)
+  ret <2 x i64> %tmp
+}
+
+define i64 @test_cntlzdm(i64 %a, i64 %b) {
+; CHECK-LABEL: test_cntlzdm:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    cntlzdm r3, r3, r4
+; CHECK-NEXT:    blr
+entry:
+  %tmp = tail call i64 @llvm.ppc.cntlzdm(i64 %a, i64 %b)
+  ret i64 %tmp
+}
+
+define i64 @test_cnttzdm(i64 %a, i64 %b) {
+; CHECK-LABEL: test_cnttzdm:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    cnttzdm r3, r3, r4
+; CHECK-NEXT:    blr
+entry:
+  %tmp = tail call i64 @llvm.ppc.cnttzdm(i64 %a, i64 %b)
+  ret i64 %tmp
+}

llvm/test/MC/Disassembler/PowerPC/p10insts.txt

 # RUN: llvm-mc --disassemble %s -triple powerpc64-unknown-linux-gnu \
 # RUN:   -mcpu=pwr10 | FileCheck %s
 
 # CHECK: vpdepd 1, 2, 0
 0x10 0x22 0x05 0xcd
 
 # CHECK: vpextd 1, 2, 0
 0x10 0x22 0x05 0x8d
 
 # CHECK: pdepd 1, 2, 4
 0x7c 0x41 0x21 0x38
 
 # CHECK: pextd 1, 2, 4
 0x7c 0x41 0x21 0x78
 
+# CHECK: vclzdm 1, 2, 3
+0x10 0x22 0x1f 0x84
+
+# CHECK: vctzdm 1, 2, 3
+0x10 0x22 0x1f 0xc4
+
+# CHECK: cntlzdm 1, 3, 2
+0x7c 0x61 0x10 0x76
+
+# CHECK: cnttzdm 1, 3, 2
+0x7c 0x61 0x14 0x76
+
 # CHECK xxgenpcvbm 0, 1, 2
 0xf0 0x02 0x0f 0x28
 
 # CHECK xxgenpcvhm 0, 1, 2
 0xf0 0x02 0x0f 0x2a
 
 # CHECK xxgenpcvwm 0, 1, 2
 0xf0 0x02 0x0f 0x68

llvm/test/MC/PowerPC/p10.s

 # CHECK-LE: vpextd 1, 2, 0                        # encoding: [0x8d,0x05,0x22,0x10]
             vpextd 1, 2, 0
 # CHECK-BE: pdepd 1, 2, 4                         # encoding: [0x7c,0x41,0x21,0x38]
 # CHECK-LE: pdepd 1, 2, 4                         # encoding: [0x38,0x21,0x41,0x7c]
             pdepd 1, 2, 4
 # CHECK-BE: pextd 1, 2, 4                         # encoding: [0x7c,0x41,0x21,0x78]
 # CHECK-LE: pextd 1, 2, 4                         # encoding: [0x78,0x21,0x41,0x7c]
             pextd 1, 2, 4
+# CHECK-BE: vclzdm 1, 2, 3                        # encoding: [0x10,0x22,0x1f,0x84]
+# CHECK-LE: vclzdm 1, 2, 3                        # encoding: [0x84,0x1f,0x22,0x10]
+            vclzdm 1, 2, 3
+# CHECK-BE: vctzdm 1, 2, 3                        # encoding: [0x10,0x22,0x1f,0xc4]
+# CHECK-LE: vctzdm 1, 2, 3                        # encoding: [0xc4,0x1f,0x22,0x10]
+            vctzdm 1, 2, 3
+# CHECK-BE: cntlzdm 1, 3, 2                       # encoding: [0x7c,0x61,0x10,0x76]
+# CHECK-LE: cntlzdm 1, 3, 2                       # encoding: [0x76,0x10,0x61,0x7c]
+            cntlzdm 1, 3, 2
+# CHECK-BE: cnttzdm 1, 3, 2                       # encoding: [0x7c,0x61,0x14,0x76]
+# CHECK-LE: cnttzdm 1, 3, 2                       # encoding: [0x76,0x14,0x61,0x7c]
+            cnttzdm 1, 3, 2
 # CHECK-BE: xxgenpcvbm 0, 1, 2                    # encoding: [0xf0,0x02,0x0f,0x28]
 # CHECK-LE: xxgenpcvbm 0, 1, 2                    # encoding: [0x28,0x0f,0x02,0xf0]
             xxgenpcvbm 0, 1, 2
 # CHECK-BE: xxgenpcvhm 0, 1, 2                    # encoding: [0xf0,0x02,0x0f,0x2a]
 # CHECK-LE: xxgenpcvhm 0, 1, 2                    # encoding: [0x2a,0x0f,0x02,0xf0]
             xxgenpcvhm 0, 1, 2
 # CHECK-BE: xxgenpcvwm 0, 1, 2                    # encoding: [0xf0,0x02,0x0f,0x68]
 # CHECK-LE: xxgenpcvwm 0, 1, 2                    # encoding: [0x68,0x0f,0x02,0xf0]