[InstCombine] cttz(abs(x)) -> cttz(x)

[xbolva00]

Summary

Signedness does not change number of trailing zeros.

[lebedev.ri]

It is generally helpful to write some patch descriptions (you want those for git log anyway),
and provide alive proofs, since you likely had to come up with one when developing anyway.

[xbolva00]

In D63546#1550291, @lebedev.ri wrote:

It is generally helpful to write some patch descriptions (you want those for git log anyway),
and provide alive proofs, since you likely had to come up with one when developing anyway.

I would like to, but I think https://rise4fun.com/Alive does not support @llvm.cttz (intrinsics at all), or am I wrong?

Edit: please see https://reviews.llvm.org/D63534

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1200 ↗

(On Diff #205561)

I'm not sure why we're limiting to single-use?

1202 ↗

(On Diff #205561)

So since for cttz the sub is transparent, we should be ok with SPF_NABS too?

[xbolva00]

Removed OneUse check.
Added vector tests.
Added support for NABS, added tests for NABS.

Thanks for review, @lebedev.ri

[lebedev.ri]

(Please precommit all the tests)

[xbolva00]

Precommited tests, rebased.

[lebedev.ri]

Looks ok.

[xbolva00]

Thanks

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

static Instruction *foldCttzCtlz(IntrinsicInst &II, InstCombiner &IC) {
   // ctlz(bitreverse(x)) -> cttz(x)
   // cttz(bitreverse(x)) -> ctlz(x)
   if (match(Op0, m_BitReverse(m_Value(X)))) {
     Intrinsic::ID ID = IsTZ ? Intrinsic::ctlz : Intrinsic::cttz;
     Function *F = Intrinsic::getDeclaration(II.getModule(), ID, II.getType());
     return CallInst::Create(F, {X, II.getArgOperand(1)});
   }
 
+  if (IsTZ) {
     // cttz(-x) -> cttz(x)
-  if (IsTZ && match(Op0, m_Neg(m_Value(X)))) {
+    if (match(Op0, m_Neg(m_Value(X)))) {
       II.setOperand(0, X);
       return ⅈ
     }
 
+    // cttz(abs(x)) -> cttz(x)
+    // cttz(nabs(x)) -> cttz(x)
+    Value *Y;
+    SelectPatternFlavor SPF = matchSelectPattern(Op0, X, Y).Flavor;
+    if (SPF == SPF_ABS || SPF == SPF_NABS) {
+      II.setOperand(0, X);
+      return ⅈ
+    }
+  }
+
   KnownBits Known = IC.computeKnownBits(Op0, 0, &II);
 
   // Create a mask for bits above (ctlz) or below (cttz) the first known one.
   unsigned PossibleZeros = IsTZ ? Known.countMaxTrailingZeros()
                                 : Known.countMaxLeadingZeros();
   unsigned DefiniteZeros = IsTZ ? Known.countMinTrailingZeros()
                                 : Known.countMinLeadingZeros();
 

llvm/trunk/test/Transforms/InstCombine/cttz-abs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 define i32 @cttz_abs(i32 %x) {
 ; CHECK-LABEL: @cttz_abs(
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[S:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[S]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[D]], i1 true), !range !0
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 true), !range !0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %c = icmp slt i32 %x, 0
   %s = sub i32 0, %x
   %d = select i1 %c, i32 %s, i32 %x
   %r = tail call i32 @llvm.cttz.i32(i32 %d, i1 true)
   ret i32 %r
 }
 
 define <2 x i64> @cttz_abs_vec(<2 x i64> %x) {
 ; CHECK-LABEL: @cttz_abs_vec(
-; CHECK-NEXT:    [[C:%.*]] = icmp slt <2 x i64> [[X:%.*]], zeroinitializer
-; CHECK-NEXT:    [[S:%.*]] = sub <2 x i64> zeroinitializer, [[X]]
-; CHECK-NEXT:    [[D:%.*]] = select <2 x i1> [[C]], <2 x i64> [[S]], <2 x i64> [[X]]
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i64> @llvm.cttz.v2i64(<2 x i64> [[D]], i1 false)
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i64> @llvm.cttz.v2i64(<2 x i64> [[X:%.*]], i1 false)
 ; CHECK-NEXT:    ret <2 x i64> [[R]]
 ;
   %c = icmp slt <2 x i64> %x, zeroinitializer
   %s = sub <2 x i64> zeroinitializer, %x
   %d = select <2 x i1> %c, <2 x i64> %s, <2 x i64> %x
   %r = tail call <2 x i64> @llvm.cttz.v2i64(<2 x i64> %d)
   ret <2 x i64> %r
 }
 
 define i32 @cttz_abs2(i32 %x) {
 ; CHECK-LABEL: @cttz_abs2(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @use_cond(i1 [[C]])
-; CHECK-NEXT:    [[S:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[S]]
-; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[D]], i1 true), !range !0
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true), !range !0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %c = icmp sgt i32 %x, 0
   call void @use_cond(i1 %c)
   %s = sub i32 0, %x
   %d = select i1 %c, i32 %x, i32 %s
   %r = tail call i32 @llvm.cttz.i32(i32 %d, i1 true)
   ret i32 %r
 }
 
 define i32 @cttz_abs3(i32 %x) {
 ; CHECK-LABEL: @cttz_abs3(
 ; CHECK-NEXT:    [[C:%.*]] = icmp sgt i32 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use_cond(i1 [[C]])
-; CHECK-NEXT:    [[S:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[S]]
-; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[D]], i1 true), !range !0
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true), !range !0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %c = icmp sgt i32 %x, -1
   call void @use_cond(i1 %c)
   %s = sub i32 0, %x
   %d = select i1 %c, i32 %x, i32 %s
   %r = tail call i32 @llvm.cttz.i32(i32 %d, i1 true)
   ret i32 %r
 }
 
 define i32 @cttz_abs4(i32 %x) {
 ; CHECK-LABEL: @cttz_abs4(
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[S:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[S]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[D]], i1 true), !range !0
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 true), !range !0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %c = icmp slt i32 %x, 1
   %s = sub i32 0, %x
   %d = select i1 %c, i32 %s, i32 %x
   %r = tail call i32 @llvm.cttz.i32(i32 %d, i1 true)
   ret i32 %r
 }
 
 define i32 @cttz_nabs(i32 %x) {
 ; CHECK-LABEL: @cttz_nabs(
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[S:%.*]] = sub i32 0, [[X]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[S]]
-; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[D]], i1 false), !range !0
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 false), !range !0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %c = icmp slt i32 %x, 0
   %s = sub i32 0, %x
   %d = select i1 %c, i32 %x, i32 %s
   %r = tail call i32 @llvm.cttz.i32(i32 %d, i1 false)
   ret i32 %r
 }
 
 define <2 x i64> @cttz_nabs_vec(<2 x i64> %x) {
 ; CHECK-LABEL: @cttz_nabs_vec(
-; CHECK-NEXT:    [[C:%.*]] = icmp slt <2 x i64> [[X:%.*]], zeroinitializer
-; CHECK-NEXT:    [[S:%.*]] = sub <2 x i64> zeroinitializer, [[X]]
-; CHECK-NEXT:    [[D:%.*]] = select <2 x i1> [[C]], <2 x i64> [[X]], <2 x i64> [[S]]
-; CHECK-NEXT:    [[R:%.*]] = call <2 x i64> @llvm.cttz.v2i64(<2 x i64> [[D]], i1 false)
+; CHECK-NEXT:    [[R:%.*]] = call <2 x i64> @llvm.cttz.v2i64(<2 x i64> [[X:%.*]], i1 false)
 ; CHECK-NEXT:    ret <2 x i64> [[R]]
 ;
   %c = icmp slt <2 x i64> %x, zeroinitializer
   %s = sub <2 x i64> zeroinitializer, %x
   %d = select <2 x i1> %c, <2 x i64> %x, <2 x i64> %s
   %r = tail call <2 x i64> @llvm.cttz.v2i64(<2 x i64> %d)
   ret <2 x i64> %r
 }
 
 define i64 @cttz_abs_64(i64 %x) {
 ; CHECK-LABEL: @cttz_abs_64(
-; CHECK-NEXT:    [[C:%.*]] = icmp slt i64 [[X:%.*]], 0
-; CHECK-NEXT:    [[S:%.*]] = sub i64 0, [[X]]
-; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i64 [[S]], i64 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = call i64 @llvm.cttz.i64(i64 [[D]], i1 false), !range !1
+; CHECK-NEXT:    [[R:%.*]] = call i64 @llvm.cttz.i64(i64 [[X:%.*]], i1 false), !range !1
 ; CHECK-NEXT:    ret i64 [[R]]
 ;
   %c = icmp slt i64 %x, 0
   %s = sub i64 0, %x
   %d = select i1 %c, i64 %s, i64 %x
   %r = tail call i64 @llvm.cttz.i64(i64 %d)
   ret i64 %r
 }
 
 define i32 @cttz_abs_multiuse(i32 %x) {
 ; CHECK-LABEL: @cttz_abs_multiuse(
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[S:%.*]] = sub i32 0, [[X]]
 ; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[S]], i32 [[X]]
 ; CHECK-NEXT:    call void @use_abs(i32 [[D]])
-; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[D]], i1 true), !range !0
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true), !range !0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %c = icmp slt i32 %x, 1
   %s = sub i32 0, %x
   %d = select i1 %c, i32 %s, i32 %x
   call void @use_abs(i32 %d)
   %r = tail call i32 @llvm.cttz.i32(i32 %d, i1 true)
   ret i32 %r
 }
 
 define i32 @cttz_nabs_multiuse(i32 %x) {
 ; CHECK-LABEL: @cttz_nabs_multiuse(
 ; CHECK-NEXT:    [[C:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[S:%.*]] = sub i32 0, [[X]]
 ; CHECK-NEXT:    [[D:%.*]] = select i1 [[C]], i32 [[X]], i32 [[S]]
 ; CHECK-NEXT:    call void @use_abs(i32 [[D]])
-; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[D]], i1 true), !range !0
+; CHECK-NEXT:    [[R:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[X]], i1 true), !range !0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %c = icmp slt i32 %x, 1
   %s = sub i32 0, %x
   %d = select i1 %c, i32 %x, i32 %s
   call void @use_abs(i32 %d)
   %r = tail call i32 @llvm.cttz.i32(i32 %d, i1 true)
   ret i32 %r