[InstCombine] Simplify ctlz/cttz with bitreverse

[xbolva00]

Summary

Fixes PR41273

[spatel]

We don't need a full permutation of the possibilities, but can you add at least a few test variations and improvements:

1. The 2nd param is 'false'.
2. The type is a vector.
3. Run '-instnamer' or manually add variable names, so we don't have nameless values.
4. Pre-commit the baseline versions of the tests.
5. Add a comment/link for PR41273 (should also mention that in the description/commit message).

[xbolva00]

• Added and precommited more tests

[spatel]

LGTM - thanks!

lib/Transforms/InstCombine/InstCombineCalls.cpp

1333–1336

Might be less hassle to not to use the builder directly:

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) });

[xbolva00]

Do not use builder.

lib/Transforms/InstCombine/InstCombineCalls.cpp

static Instruction *simplifyInvariantGroupIntrinsic(IntrinsicInst &II,
 
   return cast<Instruction>(Result);
 }
 
 static Instruction *foldCttzCtlz(IntrinsicInst &II, InstCombiner &IC) {
   assert((II.getIntrinsicID() == Intrinsic::cttz ||
           II.getIntrinsicID() == Intrinsic::ctlz) &&
          "Expected cttz or ctlz intrinsic");
+  bool IsTZ = II.getIntrinsicID() == Intrinsic::cttz;
   Value *Op0 = II.getArgOperand(0);
+  Value *X;
+  // ctlz(bitreverse(x)) -> cttz(x)
+  // cttz(bitreverse(x)) -> ctlz(x)
+  if (match(Op0, m_BitReverse(m_Value(X)))) {
+    return IC.replaceInstUsesWith(
+        II,
+        IC.Builder.CreateBinaryIntrinsic(
+            IsTZ ? Intrinsic::ctlz : Intrinsic::cttz, X, II.getArgOperand(1)));
+  }
 
   KnownBits Known = IC.computeKnownBits(Op0, 0, &II);
 
   // Create a mask for bits above (ctlz) or below (cttz) the first known one.
-  bool IsTZ = II.getIntrinsicID() == Intrinsic::cttz;
   unsigned PossibleZeros = IsTZ ? Known.countMaxTrailingZeros()
                                 : Known.countMaxLeadingZeros();
   unsigned DefiniteZeros = IsTZ ? Known.countMinTrailingZeros()
                                 : Known.countMinLeadingZeros();
 
   // If all bits above (ctlz) or below (cttz) the first known one are known
   // zero, this value is constant.
   // FIXME: This should be in InstSimplify because we're replacing an

test/Transforms/InstCombine/ctlz-cttz-bitreverse.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 define i32 @ctlz_true_bitreverse(i32 %x) {
 ; CHECK-LABEL: @ctlz_true_bitreverse(
-; CHECK-NEXT:    [[A:%.*]] = tail call i32 @llvm.bitreverse.i32(i32 [[X:%.*]])
-; CHECK-NEXT:    [[B:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[A]], i1 true), !range !0
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 true), !range !0
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %a = tail call i32 @llvm.bitreverse.i32(i32 %x)
   %b = tail call i32 @llvm.ctlz.i32(i32 %a, i1 true)
   ret i32 %b
 }
 
 define <2 x i64> @ctlz_true_bitreverse_vec(<2 x i64> %x) {
 ; CHECK-LABEL: @ctlz_true_bitreverse_vec(
-; CHECK-NEXT:    [[A:%.*]] = tail call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> [[X:%.*]])
-; CHECK-NEXT:    [[B:%.*]] = tail call <2 x i64> @llvm.ctlz.v2i64(<2 x i64> [[A]], i1 true)
-; CHECK-NEXT:    ret <2 x i64> [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i64> @llvm.cttz.v2i64(<2 x i64> [[X:%.*]], i1 true)
+; CHECK-NEXT:    ret <2 x i64> [[TMP1]]
 ;
   %a = tail call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> %x)
   %b = tail call <2 x i64> @llvm.ctlz.v2i64(<2 x i64> %a, i1 true)
   ret <2 x i64> %b
 }
 
 define i32 @ctlz_false_bitreverse(i32 %x) {
 ; CHECK-LABEL: @ctlz_false_bitreverse(
-; CHECK-NEXT:    [[A:%.*]] = tail call i32 @llvm.bitreverse.i32(i32 [[X:%.*]])
-; CHECK-NEXT:    [[B:%.*]] = tail call i32 @llvm.ctlz.i32(i32 [[A]], i1 false), !range !0
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.cttz.i32(i32 [[X:%.*]], i1 false), !range !0
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %a = tail call i32 @llvm.bitreverse.i32(i32 %x)
   %b = tail call i32 @llvm.ctlz.i32(i32 %a, i1 false)
   ret i32 %b
 }
 
 define i32 @cttz_true_bitreverse(i32 %x) {
 ; CHECK-LABEL: @cttz_true_bitreverse(
-; CHECK-NEXT:    [[A:%.*]] = tail call i32 @llvm.bitreverse.i32(i32 [[X:%.*]])
-; CHECK-NEXT:    [[B:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[A]], i1 true), !range !0
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 true), !range !0
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %a = tail call i32 @llvm.bitreverse.i32(i32 %x)
   %b = tail call i32 @llvm.cttz.i32(i32 %a, i1 true)
   ret i32 %b
 }
 
 define <2 x i64> @cttz_true_bitreverse_vec(<2 x i64> %x) {
 ; CHECK-LABEL: @cttz_true_bitreverse_vec(
-; CHECK-NEXT:    [[A:%.*]] = tail call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> [[X:%.*]])
-; CHECK-NEXT:    [[B:%.*]] = tail call <2 x i64> @llvm.cttz.v2i64(<2 x i64> [[A]], i1 true)
-; CHECK-NEXT:    ret <2 x i64> [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i64> @llvm.ctlz.v2i64(<2 x i64> [[X:%.*]], i1 true)
+; CHECK-NEXT:    ret <2 x i64> [[TMP1]]
 ;
   %a = tail call <2 x i64> @llvm.bitreverse.v2i64(<2 x i64> %x)
   %b = tail call <2 x i64> @llvm.cttz.v2i64(<2 x i64> %a, i1 true)
   ret <2 x i64> %b
 }
 
 define i32 @cttz_false_bitreverse(i32 %x) {
 ; CHECK-LABEL: @cttz_false_bitreverse(
-; CHECK-NEXT:    [[A:%.*]] = tail call i32 @llvm.bitreverse.i32(i32 [[X:%.*]])
-; CHECK-NEXT:    [[B:%.*]] = tail call i32 @llvm.cttz.i32(i32 [[A]], i1 false), !range !0
-; CHECK-NEXT:    ret i32 [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 false), !range !0
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %a = tail call i32 @llvm.bitreverse.i32(i32 %x)
   %b = tail call i32 @llvm.cttz.i32(i32 %a, i1 false)
   ret i32 %b
 }
 
 declare i32 @llvm.bitreverse.i32(i32)
 declare <2 x i64> @llvm.bitreverse.v2i64(<2 x i64>)
 declare i32 @llvm.ctlz.i32(i32, i1)
 declare i32 @llvm.cttz.i32(i32, i1)
 declare <2 x i64> @llvm.ctlz.v2i64(<2 x i64>, i1)
 declare <2 x i64> @llvm.cttz.v2i64(<2 x i64>, i1)