[InstCombine] recognize bitreverse disguised as shufflevector

[Chenbing.Zheng]

Summary

This patch complete TODO left in D66965, and achieve related pattern for bitreverse.

[RKSimon]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

if (Shuf->hasOneUse() && DestTy->isVectorTy() &&
         Value *LHS = Builder.CreateBitCast(ShufOp0, DestTy);
         Value *RHS = Builder.CreateBitCast(ShufOp1, DestTy);
         // Return a new shuffle vector.  Use the same element ID's, as we
         // know the vector types match #elts.
         return new ShuffleVectorInst(LHS, RHS, Shuf->getShuffleMask());
       }
     }
 
-    // A bitcasted-to-scalar and byte-reversing shuffle is better recognized as
-    // a byte-swap:
-    // bitcast <N x i8> (shuf X, undef, <N, N-1,...0>) --> bswap (bitcast X)
-    // TODO: We should match the related pattern for bitreverse.
-    if (DestTy->isIntegerTy() &&
-        DL.isLegalInteger(DestTy->getScalarSizeInBits()) &&
-        SrcTy->getScalarSizeInBits() == 8 &&
-        ShufElts.getKnownMinValue() % 2 == 0 && Shuf->hasOneUse() &&
-        Shuf->isReverse()) {
+    // A bitcasted-to-scalar and byte/bit reversing shuffle is better recognized
+    // as a byte/bit swap:
+    // bitcast <N x i8> (shuf X, undef, <N, N-1,...0>) -> bswap (bitcast X)
+    // bitcast <N x i1> (shuf X, undef, <N, N-1,...0>) -> bitreverse (bitcast X)
+    if (DestTy->isIntegerTy() && ShufElts.getKnownMinValue() % 2 == 0 &&
+        Shuf->hasOneUse() && Shuf->isReverse()) {
+      unsigned IntrinsicNum = 0;
+      if (DL.isLegalInteger(DestTy->getScalarSizeInBits()) &&
+          SrcTy->getScalarSizeInBits() == 8) {
+        IntrinsicNum = Intrinsic::bswap;
+      } else if (SrcTy->getScalarSizeInBits() == 1) {
+        IntrinsicNum = Intrinsic::bitreverse;
+      }
+      if (IntrinsicNum != 0) {
         assert(ShufOp0->getType() == SrcTy && "Unexpected shuffle mask");
         assert(match(ShufOp1, m_Undef()) && "Unexpected shuffle op");
-      Function *Bswap =
-          Intrinsic::getDeclaration(CI.getModule(), Intrinsic::bswap, DestTy);
+        Function *BswapOrBitreverse =
+            Intrinsic::getDeclaration(CI.getModule(), IntrinsicNum, DestTy);
         Value *ScalarX = Builder.CreateBitCast(ShufOp0, DestTy);
-      return CallInst::Create(Bswap, { ScalarX });
+        return CallInst::Create(BswapOrBitreverse, {ScalarX});
+      }
     }
   }
 
   // Handle the A->B->A cast, and there is an intervening PHI node.
   if (PHINode *PN = dyn_cast<PHINode>(Src))
     if (Instruction *I = optimizeBitCastFromPhi(CI, PN))
       return I;
 

llvm/test/Transforms/InstCombine/bitreverse.ll

;
   %8 = mul nuw nsw i64 %7, 65793
   %9 = lshr i64 %8, 16
   %10 = trunc i64 %9 to i8
   ret i8 %10
 }
 
 define i4 @shuf_4bits(<4 x i1> %x) {
 ; CHECK-LABEL: @shuf_4bits(
-; CHECK-NEXT:    [[BITREVERSE:%.*]] = shufflevector <4 x i1> [[X:%.*]], <4 x i1> undef, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
-; CHECK-NEXT:    [[CAST:%.*]] = bitcast <4 x i1> [[BITREVERSE]] to i4
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <4 x i1> [[X:%.*]] to i4
+; CHECK-NEXT:    [[CAST:%.*]] = call i4 @llvm.bitreverse.i4(i4 [[TMP1]])
 ; CHECK-NEXT:    ret i4 [[CAST]]
 ;
   %bitreverse = shufflevector <4 x i1> %x, <4 x i1> undef, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
   %cast = bitcast <4 x i1> %bitreverse to i4
   ret i4 %cast
 }
 
 define i4 @shuf_load_4bits(<4 x i1> * %p) {
 ; CHECK-LABEL: @shuf_load_4bits(
-; CHECK-NEXT:    [[X:%.*]] = load <4 x i1>, <4 x i1>* [[P:%.*]], align 1
-; CHECK-NEXT:    [[BITREVERSE:%.*]] = shufflevector <4 x i1> [[X]], <4 x i1> undef, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
-; CHECK-NEXT:    [[CAST:%.*]] = bitcast <4 x i1> [[BITREVERSE]] to i4
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <4 x i1>* [[P:%.*]] to i4*
+; CHECK-NEXT:    [[X1:%.*]] = load i4, i4* [[TMP1]], align 1
+; CHECK-NEXT:    [[CAST:%.*]] = call i4 @llvm.bitreverse.i4(i4 [[X1]])
 ; CHECK-NEXT:    ret i4 [[CAST]]
 ;
   %x = load <4 x i1>, <4 x i1>* %p
   %bitreverse = shufflevector <4 x i1> %x, <4 x i1> undef, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
   %cast = bitcast <4 x i1> %bitreverse to i4
   ret i4 %cast
 }
 
 define i4 @shuf_bitcast_twice_4bits(i4 %x) {
 ; CHECK-LABEL: @shuf_bitcast_twice_4bits(
-; CHECK-NEXT:    [[CAST1:%.*]] = bitcast i4 [[X:%.*]] to <4 x i1>
-; CHECK-NEXT:    [[BITREVERSE:%.*]] = shufflevector <4 x i1> [[CAST1]], <4 x i1> undef, <4 x i32> <i32 undef, i32 2, i32 1, i32 0>
-; CHECK-NEXT:    [[CAST2:%.*]] = bitcast <4 x i1> [[BITREVERSE]] to i4
+; CHECK-NEXT:    [[CAST2:%.*]] = call i4 @llvm.bitreverse.i4(i4 [[X:%.*]])
 ; CHECK-NEXT:    ret i4 [[CAST2]]
 ;
   %cast1 = bitcast i4 %x to <4 x i1>
   %bitreverse = shufflevector <4 x i1> %cast1, <4 x i1> undef, <4 x i32> <i32 undef, i32 2, i32 1, i32 0>
   %cast2 = bitcast <4 x i1> %bitreverse to i4
   ret i4 %cast2
 }