[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

1273–1276

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 *simplifyMaskedScatter(IntrinsicInst &II, InstCombiner &IC) {
 
   return nullptr;
 }
 
 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_bitreverse(i32) {
+; CHECK-LABEL: @ctlz_bitreverse(
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0:%.*]], i1 true), !range !0
+; CHECK-NEXT:    ret i32 [[TMP2]]
+;
+  %2 = tail call i32 @llvm.bitreverse.i32(i32 %0)
+  %3 = tail call i32 @llvm.ctlz.i32(i32 %2, i1 true)
+  ret i32 %3
+}
+
+define i32 @cttz_bitreverse(i32) {
+; CHECK-LABEL: @cttz_bitreverse(
+; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.ctlz.i32(i32 [[TMP0:%.*]], i1 true), !range !0
+; CHECK-NEXT:    ret i32 [[TMP2]]
+;
+  %2 = tail call i32 @llvm.bitreverse.i32(i32 %0)
+  %3 = tail call i32 @llvm.cttz.i32(i32 %2, i1 true)
+  ret i32 %3
+}
+
+declare i32 @llvm.bitreverse.i32(i32)
+declare i32 @llvm.ctlz.i32(i32, i1)
+declare i32 @llvm.cttz.i32(i32, i1)