[ARM][AArch64] Implement __cls, __clsl and __clsll intrinsics from ACLE

[vhscampos]

Summary

Writing support for three ACLE functions:

unsigned int __cls(uint32_t x)
unsigned int __clsl(unsigned long x)
unsigned int __clsll(uint64_t x)

CLS stands for "Count number of leading sign bits".

In AArch64, these two intrinsics can be translated into the 'cls'
instruction directly. In AArch32, on the other hand, this functionality
is achieved by implementing it in terms of clz (count number of leading
zeros).

[compnerd]

clang/lib/Headers/arm_acle.h

150

I don't see a pattern match for the cls64 on ARM32, would that not fail to lower?

155

Should we have a __clsll extension, otherwise these two are the same in LLP64? I'm thinking about the LLP64 environments, where long and long long are different (32-bit vs 64-bit).

[vhscampos]

clang/lib/Headers/arm_acle.h

150

Yes. However, for now, I am not enabling support for cls64 on ARM32 as it is not done yet.

155

ACLE does provide a long long version of cls called __clsll. But since the support for cls64 on Arm32 is not done yet, I decided not to write support for __clsll. If I did, it would work for 64-bit but not for 32-bit.

Please let me know what you think.

[compnerd]

clang/lib/Headers/arm_acle.h

150

Is the difference not just the parameter type? I think that implementing it should be a trivial change to the existing implementation. Is there a reason that you are not implementing that?

155

clang supports Windows where long is 4-bytes even on 64-bit targets, and this means that this doesn't work for that target. I think that we need to add __clsll so that 64-bit ARM at least is covered.

[vhscampos]

clang/lib/Headers/arm_acle.h

150

At clang's side, yes, but not in the backend: Arm32 does not have a cls instruction, thus the CLS operations need to be custom lowered. In the llvm.arm.cls(i32) case, lowering is quite simple, and it's been included in this patch. For llvm.arm.cls64(i64), on the other hand, it is not as trivial since it's necessary to break its logic into 32-bit instructions.

So the reason not to implement that (yet) is just to split work in two different efforts.

155

I'm not sure if I am following you. On AArch64-Windows, __clsl will be lowered to llvm.aarch64.cls(i32) which will then be custom lowered correctly. Let me know if I am thinking this wrong.

[compnerd]

clang/lib/Headers/arm_acle.h

150

Would it not be sufficient to do the top half (after a shift right of 32-bits), and if it is exactly 32, then do the bottom 32-bits, otherwise, you're done?

155

Windows is LLP64, __cls and __clsl are the same thing. It needs a __clsll for the 64-bit value.

[vhscampos]

Add support for __clsll.

[vhscampos]

Added support for __clsll as requested.

clang/lib/Headers/arm_acle.h

150

Sort of. How we interpret the bottom half depends on the value of the top half. I've added this custom lowering in the latest revision.

[compnerd]

Thanks for all the adjustments, this looks good.

clang/include/clang/Basic/BuiltinsAArch64.def

 BUILTIN(__builtin_arm_ldaex, "v.", "t")
 BUILTIN(__builtin_arm_strex, "i.", "t")
 BUILTIN(__builtin_arm_stlex, "i.", "t")
 BUILTIN(__builtin_arm_clrex, "v", "")
 
 // Bit manipulation
 BUILTIN(__builtin_arm_rbit, "UiUi", "nc")
 BUILTIN(__builtin_arm_rbit64, "WUiWUi", "nc")
+BUILTIN(__builtin_arm_cls, "UiZUi", "nc")
+BUILTIN(__builtin_arm_cls64, "UiWUi", "nc")
 
 // HINT
 BUILTIN(__builtin_arm_nop, "v", "")
 BUILTIN(__builtin_arm_yield, "v", "")
 BUILTIN(__builtin_arm_wfe, "v", "")
 BUILTIN(__builtin_arm_wfi, "v", "")
 BUILTIN(__builtin_arm_sev, "v", "")
 BUILTIN(__builtin_arm_sevl, "v", "")

clang/include/clang/Basic/BuiltinsARM.def

 BUILTIN(__builtin_arm_smlsldx, "LLiiiLLi", "nc")
 BUILTIN(__builtin_arm_smuad, "iii", "nc")
 BUILTIN(__builtin_arm_smuadx, "iii", "nc")
 BUILTIN(__builtin_arm_smusd, "iii", "nc")
 BUILTIN(__builtin_arm_smusdx, "iii", "nc")
 
 // Bit manipulation
 BUILTIN(__builtin_arm_rbit, "UiUi", "nc")
+BUILTIN(__builtin_arm_cls, "UiZUi", "nc")
+BUILTIN(__builtin_arm_cls64, "UiWUi", "nc")
 
 // Store and load exclusive
 BUILTIN(__builtin_arm_ldrexd, "LLUiv*", "")
 BUILTIN(__builtin_arm_strexd, "iLLUiv*", "")
 
 BUILTIN(__builtin_arm_ldrex, "v.", "t")
 BUILTIN(__builtin_arm_ldaex, "v.", "t")
 BUILTIN(__builtin_arm_strex, "i.", "t")

clang/lib/CodeGen/CGBuiltin.cpp

Value *CodeGenFunction::EmitARMBuiltinExpr(unsigned BuiltinID,
   }
 
   if (BuiltinID == ARM::BI__builtin_arm_rbit) {
     llvm::Value *Arg = EmitScalarExpr(E->getArg(0));
     return Builder.CreateCall(
         CGM.getIntrinsic(Intrinsic::bitreverse, Arg->getType()), Arg, "rbit");
   }
 
+  if (BuiltinID == ARM::BI__builtin_arm_cls) {
+    llvm::Value *Arg = EmitScalarExpr(E->getArg(0));
+    return Builder.CreateCall(CGM.getIntrinsic(Intrinsic::arm_cls), Arg, "cls");
+  }
+  if (BuiltinID == ARM::BI__builtin_arm_cls64) {
+    llvm::Value *Arg = EmitScalarExpr(E->getArg(0));
+    return Builder.CreateCall(CGM.getIntrinsic(Intrinsic::arm_cls64), Arg,
+                              "cls");
+  }
+
   if (BuiltinID == ARM::BI__clear_cache) {
     assert(E->getNumArgs() == 2 && "__clear_cache takes 2 arguments");
     const FunctionDecl *FD = E->getDirectCallee();
     Value *Ops[2];
     for (unsigned i = 0; i < 2; i++)
       Ops[i] = EmitScalarExpr(E->getArg(i));
     llvm::Type *Ty = CGM.getTypes().ConvertType(FD->getType());
     llvm::FunctionType *FTy = cast<llvm::FunctionType>(Ty);
Value *CodeGenFunction::EmitAArch64BuiltinExpr(unsigned BuiltinID,
   if (BuiltinID == AArch64::BI__builtin_arm_rbit64) {
     assert((getContext().getTypeSize(E->getType()) == 64) &&
            "rbit of unusual size!");
     llvm::Value *Arg = EmitScalarExpr(E->getArg(0));
     return Builder.CreateCall(
         CGM.getIntrinsic(Intrinsic::bitreverse, Arg->getType()), Arg, "rbit");
   }
 
+  if (BuiltinID == AArch64::BI__builtin_arm_cls) {
+    llvm::Value *Arg = EmitScalarExpr(E->getArg(0));
+    return Builder.CreateCall(CGM.getIntrinsic(Intrinsic::aarch64_cls), Arg,
+                              "cls");
+  }
+  if (BuiltinID == AArch64::BI__builtin_arm_cls64) {
+    llvm::Value *Arg = EmitScalarExpr(E->getArg(0));
+    return Builder.CreateCall(CGM.getIntrinsic(Intrinsic::aarch64_cls64), Arg,
+                              "cls");
+  }
+
   if (BuiltinID == AArch64::BI__builtin_arm_jcvt) {
     assert((getContext().getTypeSize(E->getType()) == 32) &&
            "__jcvt of unusual size!");
     llvm::Value *Arg = EmitScalarExpr(E->getArg(0));
     return Builder.CreateCall(
         CGM.getIntrinsic(Intrinsic::aarch64_fjcvtzs), Arg);
   }
 

clang/lib/Headers/arm_acle.h

__clzl(unsigned long __t) {
   return __builtin_clzl(__t);
 }
 
 static __inline__ uint64_t __attribute__((__always_inline__, __nodebug__))
 __clzll(uint64_t __t) {
   return __builtin_clzll(__t);
 }
 
+/* CLS */
+static __inline__ uint32_t __attribute__((__always_inline__, __nodebug__))
+__cls(uint32_t __t) {
+  return __builtin_arm_cls(__t);
+}
+
+static __inline__ uint32_t __attribute__((__always_inline__, __nodebug__))
+__clsl(unsigned long __t) {
+#if __SIZEOF_LONG__ == 4
+  return __builtin_arm_cls(__t);
+#else
+  return __builtin_arm_cls64(__t);
+#endif
+}
+
+static __inline__ uint32_t __attribute__((__always_inline__, __nodebug__))
+__clsll(uint64_t __t) {
+  return __builtin_arm_cls64(__t);
+}
+
 /* REV */
 static __inline__ uint32_t __attribute__((__always_inline__, __nodebug__))
 __rev(uint32_t __t) {
   return __builtin_bswap32(__t);
 }
 
 static __inline__ unsigned long __attribute__((__always_inline__, __nodebug__))
 __revl(unsigned long __t) {

clang/test/CodeGen/arm_acle.c

 }
 
 // ARM-LABEL: test_clzll
 // ARM: call i64 @llvm.ctlz.i64(i64 %t, i1 false)
 uint64_t test_clzll(uint64_t t) {
   return __clzll(t);
 }
 
+// ARM-LABEL: test_cls
+// ARM: call i32 @llvm.arm.cls(i32 %t)
+unsigned test_cls(uint32_t t) {
+  return __cls(t);
+}
+
+// ARM-LABEL: test_clsl
+// AArch32: call i32 @llvm.arm.cls(i32 %t)
+// AArch64: call i32 @llvm.arm.cls64(i64 %t)
+unsigned test_clsl(unsigned long t) {
+  return __clsl(t);
+}
+// ARM-LABEL: test_clsll
+// ARM: call i32 @llvm.arm.cls64(i64 %t)
+unsigned test_clsll(uint64_t t) {
+  return __clsll(t);
+}
+
 // ARM-LABEL: test_rev
 // ARM: call i32 @llvm.bswap.i32(i32 %t)
 uint32_t test_rev(uint32_t t) {
   return __rev(t);
 }
 
 // ARM-LABEL: test_revl
 // AArch32: call i32 @llvm.bswap.i32(i32 %t)

clang/test/CodeGen/builtins-arm.c

 }
 
 void wsrp(void *v) {
   // CHECK: [[V0:[%A-Za-z0-9.]+]] = ptrtoint i8* %v to i32
   // CHECK-NEXT: call void @llvm.write_register.i32(metadata ![[M2]], i32 [[V0]])
   __builtin_arm_wsrp("sysreg", v);
 }
 
+unsigned int cls(uint32_t v) {
+  // CHECK: call i32 @llvm.arm.cls(i32 %v)
+  return __builtin_arm_cls(v);
+}
+
+unsigned int clsl(unsigned long v) {
+  // CHECK: call i32 @llvm.arm.cls(i32 %v)
+  return __builtin_arm_cls(v);
+}
+
+unsigned int clsll(uint64_t v) {
+  // CHECK: call i32 @llvm.arm.cls64(i64 %v)
+  return __builtin_arm_cls64(v);
+}
+
 // CHECK: ![[M0]] = !{!"cp1:2:c3:c4:5"}
 // CHECK: ![[M1]] = !{!"cp1:2:c3"}
 // CHECK: ![[M2]] = !{!"sysreg"}

clang/test/CodeGen/builtins-arm64.c

 }
 
 void wsrp(void *v) {
   // CHECK: [[V0:[%A-Za-z0-9.]+]] = ptrtoint i8* %v to i64
   // CHECK-NEXT: call void @llvm.write_register.i64(metadata ![[M0:[0-9]]], i64 [[V0]])
   __builtin_arm_wsrp("1:2:3:4:5", v);
 }
 
+unsigned int cls(uint32_t v) {
+  // CHECK: call i32 @llvm.aarch64.cls(i32 %v)
+  return __builtin_arm_cls(v);
+}
+
+unsigned int clsl(unsigned long v) {
+  // CHECK-WIN: [[V64:%[^ ]+]] = zext i32 %v to i64
+  // CHECK-WIN: call i32 @llvm.aarch64.cls64(i64 [[V64]]
+  // CHECK-LINUX: call i32 @llvm.aarch64.cls64(i64 %v)
+  return __builtin_arm_cls64(v);
+}
+
+unsigned int clsll(uint64_t v) {
+  // CHECK: call i32 @llvm.aarch64.cls64(i64 %v)
+  return __builtin_arm_cls64(v);
+}
+
 // CHECK: ![[M0]] = !{!"1:2:3:4:5"}

llvm/include/llvm/IR/IntrinsicsAArch64.td

 
 def int_aarch64_sdiv : Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>,
                                 LLVMMatchType<0>], [IntrNoMem]>;
 def int_aarch64_udiv : Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>,
                                 LLVMMatchType<0>], [IntrNoMem]>;
 
 def int_aarch64_fjcvtzs : Intrinsic<[llvm_i32_ty], [llvm_double_ty], [IntrNoMem]>;
 
+def int_aarch64_cls: Intrinsic<[llvm_i32_ty], [llvm_i32_ty], [IntrNoMem]>;
+def int_aarch64_cls64: Intrinsic<[llvm_i32_ty], [llvm_i64_ty], [IntrNoMem]>;
+
 //===----------------------------------------------------------------------===//
 // HINT
 
 def int_aarch64_hint : Intrinsic<[], [llvm_i32_ty]>;
 
 //===----------------------------------------------------------------------===//
 // Data Barrier Instructions
 

llvm/include/llvm/IR/IntrinsicsARM.td

 
 def int_arm_mve_vld2q: Intrinsic<[llvm_anyvector_ty, LLVMMatchType<0>], [llvm_anyptr_ty], [IntrReadMem]>;
 def int_arm_mve_vld4q: Intrinsic<[llvm_anyvector_ty, LLVMMatchType<0>, LLVMMatchType<0>, LLVMMatchType<0>], [llvm_anyptr_ty], [IntrReadMem]>;
 
 def int_arm_mve_vst2q: Intrinsic<[], [llvm_anyptr_ty, llvm_anyvector_ty, LLVMMatchType<1>, llvm_i32_ty], [IntrWriteMem]>;
 def int_arm_mve_vst4q: Intrinsic<[], [llvm_anyptr_ty, llvm_anyvector_ty, LLVMMatchType<1>, LLVMMatchType<1>, LLVMMatchType<1>, llvm_i32_ty], [IntrWriteMem]
 >;
 
+def int_arm_cls: Intrinsic<[llvm_i32_ty], [llvm_i32_ty], [IntrNoMem]>;
+def int_arm_cls64: Intrinsic<[llvm_i32_ty], [llvm_i64_ty], [IntrNoMem]>;
+
 } // end TargetPrefix

llvm/lib/Target/AArch64/AArch64InstrInfo.td

 def : Pat<(cttz GPR64:$Rn),
           (CLZXr (RBITXr GPR64:$Rn))>;
 def : Pat<(ctlz (or (shl (xor (sra GPR32:$Rn, (i64 31)), GPR32:$Rn), (i64 1)),
                 (i32 1))),
           (CLSWr GPR32:$Rn)>;
 def : Pat<(ctlz (or (shl (xor (sra GPR64:$Rn, (i64 63)), GPR64:$Rn), (i64 1)),
                 (i64 1))),
           (CLSXr GPR64:$Rn)>;
+def : Pat<(int_aarch64_cls GPR32:$Rn), (CLSWr GPR32:$Rn)>;
+def : Pat<(int_aarch64_cls64 GPR64:$Rm), (EXTRACT_SUBREG (CLSXr GPR64:$Rm), sub_32)>;
 
 // Unlike the other one operand instructions, the instructions with the "rev"
 // mnemonic do *not* just different in the size bit, but actually use different
 // opcode bits for the different sizes.
 def REVWr   : OneWRegData<0b010, "rev", bswap>;
 def REVXr   : OneXRegData<0b011, "rev", bswap>;
 def REV32Xr : OneXRegData<0b010, "rev32",
                                  UnOpFrag<(rotr (bswap node:$LHS), (i64 32))>>;

llvm/lib/Target/ARM/ARMISelLowering.cpp

ARMTargetLowering::LowerINTRINSIC_WO_CHAIN(SDValue Op, SelectionDAG &DAG,
   unsigned IntNo = cast<ConstantSDNode>(Op.getOperand(0))->getZExtValue();
   SDLoc dl(Op);
   switch (IntNo) {
   default: return SDValue();    // Don't custom lower most intrinsics.
   case Intrinsic::thread_pointer: {
     EVT PtrVT = getPointerTy(DAG.getDataLayout());
     return DAG.getNode(ARMISD::THREAD_POINTER, dl, PtrVT);
   }
+  case Intrinsic::arm_cls: {
+    const SDValue &Operand = Op.getOperand(1);
+    const EVT VTy = Op.getValueType();
+    SDValue SRA =
+        DAG.getNode(ISD::SRA, dl, VTy, Operand, DAG.getConstant(31, dl, VTy));
+    SDValue XOR = DAG.getNode(ISD::XOR, dl, VTy, SRA, Operand);
+    SDValue SHL =
+        DAG.getNode(ISD::SHL, dl, VTy, XOR, DAG.getConstant(1, dl, VTy));
+    SDValue OR =
+        DAG.getNode(ISD::OR, dl, VTy, SHL, DAG.getConstant(1, dl, VTy));
+    SDValue Result = DAG.getNode(ISD::CTLZ, dl, VTy, OR);
+    return Result;
+  }
+  case Intrinsic::arm_cls64: {
+    // cls(x) = if cls(hi(x)) != 31 then cls(hi(x))
+    //          else 31 + clz(if hi(x) == 0 then lo(x) else not(lo(x)))
+    const SDValue &Operand = Op.getOperand(1);
+    const EVT VTy = Op.getValueType();
+
+    SDValue Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VTy, Operand,
+                             DAG.getConstant(1, dl, VTy));
+    SDValue Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, VTy, Operand,
+                             DAG.getConstant(0, dl, VTy));
+    SDValue Constant0 = DAG.getConstant(0, dl, VTy);
+    SDValue Constant1 = DAG.getConstant(1, dl, VTy);
+    SDValue Constant31 = DAG.getConstant(31, dl, VTy);
+    SDValue SRAHi = DAG.getNode(ISD::SRA, dl, VTy, Hi, Constant31);
+    SDValue XORHi = DAG.getNode(ISD::XOR, dl, VTy, SRAHi, Hi);
+    SDValue SHLHi = DAG.getNode(ISD::SHL, dl, VTy, XORHi, Constant1);
+    SDValue ORHi = DAG.getNode(ISD::OR, dl, VTy, SHLHi, Constant1);
+    SDValue CLSHi = DAG.getNode(ISD::CTLZ, dl, VTy, ORHi);
+    SDValue CheckLo =
+        DAG.getSetCC(dl, MVT::i1, CLSHi, Constant31, ISD::CondCode::SETEQ);
+    SDValue HiIsZero =
+        DAG.getSetCC(dl, MVT::i1, Hi, Constant0, ISD::CondCode::SETEQ);
+    SDValue AdjustedLo =
+        DAG.getSelect(dl, VTy, HiIsZero, Lo, DAG.getNOT(dl, Lo, VTy));
+    SDValue CLZAdjustedLo = DAG.getNode(ISD::CTLZ, dl, VTy, AdjustedLo);
+    SDValue Result =
+        DAG.getSelect(dl, VTy, CheckLo,
+                      DAG.getNode(ISD::ADD, dl, VTy, CLZAdjustedLo, Constant31), CLSHi);
+    return Result;
+  }
   case Intrinsic::eh_sjlj_lsda: {
     MachineFunction &MF = DAG.getMachineFunction();
     ARMFunctionInfo *AFI = MF.getInfo<ARMFunctionInfo>();
     unsigned ARMPCLabelIndex = AFI->createPICLabelUId();
     EVT PtrVT = getPointerTy(DAG.getDataLayout());
     SDValue CPAddr;
     bool IsPositionIndependent = isPositionIndependent();
     unsigned PCAdj = IsPositionIndependent ? (Subtarget->isThumb() ? 4 : 8) : 0;

llvm/test/CodeGen/AArch64/cls.ll

+; RUN: llc -mtriple=aarch64 %s -o - | FileCheck %s
+
+; @llvm.aarch64.cls must be directly translated into the 'cls' instruction
+
+; CHECK-LABEL: cls
+; CHECK: cls [[REG:w[0-9]+]], [[REG]]
+define i32 @cls(i32 %t) {
+  %cls.i = call i32 @llvm.aarch64.cls(i32 %t)
+  ret i32 %cls.i
+}
+
+; CHECK-LABEL: cls64
+; CHECK: cls [[REG:x[0-9]+]], [[REG]]
+define i32 @cls64(i64 %t) {
+  %cls.i = call i32 @llvm.aarch64.cls64(i64 %t)
+  ret i32 %cls.i
+}
+
+declare i32 @llvm.aarch64.cls(i32) nounwind
+declare i32 @llvm.aarch64.cls64(i64) nounwind

llvm/test/CodeGen/ARM/cls.ll

+; RUN: llc -mtriple=armv5 %s -o - | FileCheck %s
+
+; CHECK:      eor [[T:r[0-9]+]], [[T]], [[T]], asr #31
+; CHECK-NEXT: mov [[C1:r[0-9]+]], #1
+; CHECK-NEXT: orr [[T]], [[C1]], [[T]], lsl #1
+; CHECK-NEXT: clz [[T]], [[T]]
+define i32 @cls(i32 %t) {
+  %cls.i = call i32 @llvm.arm.cls(i32 %t)
+  ret i32 %cls.i
+}
+
+; CHECK: cmp r1, #0
+; CHECK: mvnne [[ADJUSTEDLO:r[0-9]+]], r0
+; CHECK: clz [[CLZLO:r[0-9]+]], [[ADJUSTEDLO]]
+; CHECK: eor [[A:r[0-9]+]], r1, r1, asr #31
+; CHECK: mov r1, #1
+; CHECK: orr [[A]], r1, [[A]], lsl #1
+; CHECK: clz [[CLSHI:r[0-9]+]], [[A]]
+; CHECK: cmp [[CLSHI]], #31
+; CHECK: addeq r0, [[CLZLO]], #31
+define i32 @cls64(i64 %t) {
+  %cls.i = call i32 @llvm.arm.cls64(i64 %t)
+  ret i32 %cls.i
+}
+
+declare i32 @llvm.arm.cls(i32) nounwind
+declare i32 @llvm.arm.cls64(i64) nounwind