[InstCombine] Add transform `(icmp eq/ne bitreverse(x), C)` -> `(icmp eq/ne x, bitreverse(C))`

[goldstein.w.n]

Summary

EQ: https://alive2.llvm.org/ce/z/TESofr
NE: https://alive2.llvm.org/ce/z/mwloaT

[nikic]

LGTM

[goldstein.w.n]

Rebase

[reames]

Just to note, the basic idea in this patch is generalizable. For any function F for which we can compute the inverse function F' such that F'(F(x)) == x, replacing F(x) == C with x == F'(C) is legal. Bitreverse (and the existing bswap) just happen to be cases where F == F'.

Not saying you have to implement the generalization, but might be worth some thought.

You applied this to the case where RHS is a constant, but we could also do it when F'(RHS) folds (e.g. InstSimpliy) or RHS is loop invariant when LHS isn't.

See also getInvertibleOperands from ValueTracking.cpp. It implements basically the same idea, just with a different application.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (C.isZero() || C.isMinSignedValue())
       return new ICmpInst(Pred, II->getArgOperand(0), ConstantInt::get(Ty, C));
     break;
 
   case Intrinsic::bswap:
     // bswap(A) == C  ->  A == bswap(C)
     return new ICmpInst(Pred, II->getArgOperand(0),
                         ConstantInt::get(Ty, C.byteSwap()));
 
+  case Intrinsic::bitreverse:
+    // bitreverse(A) == C  ->  A == bitreverse(C)
+    return new ICmpInst(Pred, II->getArgOperand(0),
+                        ConstantInt::get(Ty, C.reverseBits()));
+
   case Intrinsic::ctlz:
   case Intrinsic::cttz: {
     // ctz(A) == bitwidth(A)  ->  A == 0 and likewise for !=
     if (C == BitWidth)
       return new ICmpInst(Pred, II->getArgOperand(0),
                           ConstantInt::getNullValue(Ty));
 
     // ctz(A) == C -> A & Mask1 == Mask2, where Mask2 only has bit C set

llvm/test/Transforms/InstCombine/cmp-intrinsic.ll

;
   %tz = tail call i33 @llvm.cttz.i33(i33 %x, i1 false)
   %trunc = trunc i33 %tz to i4
   %cmp = icmp ult i4 %trunc, 7
   ret i1 %cmp
 }
 
 define i1 @bitreverse_ne_22(i8 %x) {
 ; CHECK-LABEL: @bitreverse_ne_22(
-; CHECK-NEXT:    [[Y:%.*]] = call i8 @llvm.bitreverse.i8(i8 [[X:%.*]])
-; CHECK-NEXT:    [[Z:%.*]] = icmp ne i8 [[Y]], 22
+; CHECK-NEXT:    [[Z:%.*]] = icmp ne i8 [[X:%.*]], 104
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = call i8 @llvm.bitreverse.i8(i8 %x)
   %z = icmp ne i8 %y, 22
   ret i1 %z
 }
 
 define i1 @bitreverse_ult_22_fail_not_equality_pred(i8 %x) {
 ; CHECK-LABEL: @bitreverse_ult_22_fail_not_equality_pred(
 ; CHECK-NEXT:    [[Y:%.*]] = call i8 @llvm.bitreverse.i8(i8 [[X:%.*]])
 ; CHECK-NEXT:    [[Z:%.*]] = icmp ult i8 [[Y]], 22
 ; CHECK-NEXT:    ret i1 [[Z]]
 ;
   %y = call i8 @llvm.bitreverse.i8(i8 %x)
   %z = icmp ult i8 %y, 22
   ret i1 %z
 }
 
 
 define <2 x i1> @bitreverse_vec_eq_2_2(<2 x i8> %x) {
 ; CHECK-LABEL: @bitreverse_vec_eq_2_2(
-; CHECK-NEXT:    [[Y:%.*]] = call <2 x i8> @llvm.bitreverse.v2i8(<2 x i8> [[X:%.*]])
-; CHECK-NEXT:    [[Z:%.*]] = icmp eq <2 x i8> [[Y]], <i8 2, i8 2>
+; CHECK-NEXT:    [[Z:%.*]] = icmp eq <2 x i8> [[X:%.*]], <i8 64, i8 64>
 ; CHECK-NEXT:    ret <2 x i1> [[Z]]
 ;
   %y = call <2 x i8> @llvm.bitreverse.v2i8(<2 x i8> %x)
   %z = icmp eq <2 x i8> %y, <i8 2, i8 2>
   ret <2 x i1> %z
 }
 
 define <2 x i1> @bitreverse_vec_eq_1_2_todo_no_splat(<2 x i8> %x) {