Implement constant folding for bitreverse

[arsenm]

ping

[jmolloy]

Hi Matt,

LGTM, thanks!

James

[arsenm]

r263945

include/llvm/ADT/APInt.h

   /// Note that this is an inefficient method.  It is better to pass in a
   /// SmallVector/SmallString to the methods above to avoid thrashing the heap
   /// for the string.
   std::string toString(unsigned Radix, bool Signed) const;
 
   /// \returns a byte-swapped representation of this APInt Value.
   APInt LLVM_ATTRIBUTE_UNUSED_RESULT byteSwap() const;
 
+  /// \returns the value with the bit representation reversed of this APInt
+  /// Value.
+  APInt LLVM_ATTRIBUTE_UNUSED_RESULT reverseBits() const;
+
   /// \brief Converts this APInt to a double value.
   double roundToDouble(bool isSigned) const;
 
   /// \brief Converts this unsigned APInt to a double value.
   double roundToDouble() const { return roundToDouble(false); }
 
   /// \brief Converts this signed APInt to a double value.
   double signedRoundToDouble() const { return roundToDouble(true); }

lib/Analysis/ConstantFolding.cpp

bool llvm::canConstantFoldCallTo(const Function *F) {
   case Intrinsic::sadd_with_overflow:
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::ssub_with_overflow:
   case Intrinsic::usub_with_overflow:
   case Intrinsic::smul_with_overflow:
   case Intrinsic::umul_with_overflow:
   case Intrinsic::convert_from_fp16:
   case Intrinsic::convert_to_fp16:
+  case Intrinsic::bitreverse:
   case Intrinsic::x86_sse_cvtss2si:
   case Intrinsic::x86_sse_cvtss2si64:
   case Intrinsic::x86_sse_cvttss2si:
   case Intrinsic::x86_sse_cvttss2si64:
   case Intrinsic::x86_sse2_cvtsd2si:
   case Intrinsic::x86_sse2_cvtsd2si64:
   case Intrinsic::x86_sse2_cvttsd2si:
   case Intrinsic::x86_sse2_cvttsd2si64:
if (Operands.size() == 1) {
     }
 
     if (ConstantInt *Op = dyn_cast<ConstantInt>(Operands[0])) {
       switch (IntrinsicID) {
       case Intrinsic::bswap:
         return ConstantInt::get(Ty->getContext(), Op->getValue().byteSwap());
       case Intrinsic::ctpop:
         return ConstantInt::get(Ty, Op->getValue().countPopulation());
+      case Intrinsic::bitreverse:
+        return ConstantInt::get(Ty->getContext(), Op->getValue().reverseBits());
       case Intrinsic::convert_from_fp16: {
         APFloat Val(APFloat::IEEEhalf, Op->getValue());
 
         bool lost = false;
         APFloat::opStatus status = Val.convert(
             Ty->getFltSemantics(), APFloat::rmNearestTiesToEven, &lost);
 
         // Conversion is always precise.

lib/Support/APInt.cpp

APInt APInt::byteSwap() const {
   if (Result.BitWidth != BitWidth) {
     lshrNear(Result.pVal, Result.pVal, getNumWords(),
              Result.BitWidth - BitWidth);
     Result.BitWidth = BitWidth;
   }
   return Result;
 }
 
+APInt APInt::reverseBits() const {
+  switch (BitWidth) {
+  case 64:
+    return APInt(BitWidth, llvm::reverseBits<uint64_t>(VAL));
+  case 32:
+    return APInt(BitWidth, llvm::reverseBits<uint32_t>(VAL));
+  case 16:
+    return APInt(BitWidth, llvm::reverseBits<uint16_t>(VAL));
+  case 8:
+    return APInt(BitWidth, llvm::reverseBits<uint8_t>(VAL));
+  default:
+    break;
+  }
+
+  APInt Val(*this);
+  APInt Reversed(*this);
+  int S = BitWidth - 1;
+
+  const APInt One(BitWidth, 1);
+
+  for ((Val = Val.lshr(1)); Val != 0; (Val = Val.lshr(1))) {
+    Reversed <<= 1;
+    Reversed |= (Val & One);
+    --S;
+  }
+
+  Reversed <<= S;
+  return Reversed;
+}
+
 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
                                             const APInt& API2) {
   APInt A = API1, B = API2;
   while (!!B) {
     APInt T = B;
     B = APIntOps::urem(A, B);
     A = T;
   }

test/Transforms/InstCombine/bitreverse-fold.ll

 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
-define i32 @test1(i32 %p) {
-; CHECK-LABEL: @test1
+define i32 @identity_bitreverse_i32(i32 %p) {
+; CHECK-LABEL: @identity_bitreverse_i32(
 ; CHECK-NEXT: ret i32 %p
   %a = call i32 @llvm.bitreverse.i32(i32 %p)
   %b = call i32 @llvm.bitreverse.i32(i32 %a)
   ret i32 %b
 }
 
+; CHECK-LABEL: @identity_bitreverse_v2i32(
+; CHECK-NEXT: ret <2 x i32> %p
+define <2 x i32> @identity_bitreverse_v2i32(<2 x i32> %p) {
+  %a = call <2 x i32> @llvm.bitreverse.v2i32(<2 x i32> %p)
+  %b = call <2 x i32> @llvm.bitreverse.v2i32(<2 x i32> %a)
+  ret <2 x i32> %b
+}
+
+; CHECK-LABEL: @reverse_0_i32(
+; CHECK-NEXT: ret i32 0
+define i32 @reverse_0_i32() {
+  %x = call i32 @llvm.bitreverse.i32(i32 0)
+  ret i32 %x
+}
+
+; CHECK-LABEL: @reverse_1_i32(
+; CHECK-NEXT: ret i32 -2147483648
+define i32 @reverse_1_i32() {
+  %x = call i32 @llvm.bitreverse.i32(i32 1)
+  ret i32 %x
+}
+
+; CHECK-LABEL: @reverse_neg1_i32(
+; CHECK-NEXT: ret i32 -1
+define i32 @reverse_neg1_i32() {
+  %x = call i32 @llvm.bitreverse.i32(i32 -1)
+  ret i32 %x
+}
+
+; CHECK-LABEL: @reverse_false_i1(
+; CHECK-NEXT: ret i1 false
+define i1 @reverse_false_i1() {
+  %x = call i1 @llvm.bitreverse.i1(i1 false)
+  ret i1 %x
+}
+
+; CHECK-LABEL: @reverse_true_i1(
+; CHECK-NEXT: ret i1 true
+define i1 @reverse_true_i1() {
+  %x = call i1 @llvm.bitreverse.i1(i1 true)
+  ret i1 %x
+}
+
+; CHECK-LABEL: @reverse_false_v2i1(
+; CHECK-NEXT: ret <2 x i1> zeroinitializer
+define <2 x i1> @reverse_false_v2i1() {
+  %x = call <2  x i1> @llvm.bitreverse.v2i1(<2 x i1> zeroinitializer)
+  ret <2 x i1> %x
+}
+
+; CHECK-LABEL: @reverse_true_v2i1(
+; CHECK-NEXT: ret <2 x i1> <i1 true, i1 true>
+define <2 x i1> @reverse_true_v2i1() {
+  %x = call <2 x i1> @llvm.bitreverse.v2i1(<2 x i1> <i1 true, i1 true>)
+  ret <2 x i1> %x
+}
+
+; CHECK-LABEL: @bitreverse_920_1234_v2i32(
+; CHECK-NEXT: ret <2 x i32> <i32 432013312, i32 1260388352>
+define <2 x i32> @bitreverse_920_1234_v2i32() {
+  %x = call <2 x i32> @llvm.bitreverse.v2i32(<2 x i32> <i32 920, i32 1234>)
+  ret <2 x i32> %x
+}
+
+; CHECK-LABEL: @reverse_100_i3(
+; CHECK-NEXT: ret i3 1
+define i3 @reverse_100_i3() {
+  %x = call i3 @llvm.bitreverse.i3(i3 100)
+  ret i3 %x
+}
+
+; CHECK-LABEL: @reverse_6_3_v2i3(
+; CHECK-NEXT: ret <2 x i3> <i3 3, i3 -2>
+define <2 x i3> @reverse_6_3_v2i3() {
+  %x = call <2  x i3> @llvm.bitreverse.v2i3(<2 x i3> <i3 6, i3 3>)
+  ret <2 x i3> %x
+}
+
+declare i1 @llvm.bitreverse.i1(i1) readnone
+declare <2 x i1> @llvm.bitreverse.v2i1(<2 x i1>) readnone
+
+declare i3 @llvm.bitreverse.i3(i3) readnone
+declare <2 x i3> @llvm.bitreverse.v2i3(<2 x i3>) readnone
+
 declare i32 @llvm.bitreverse.i32(i32) readnone
+declare <2 x i32> @llvm.bitreverse.v2i32(<2 x i32>) readnone

unittests/ADT/APIntTest.cpp

TEST(APIntTest, SelfMoveAssignment) {
   EXPECT_EQ(0xdeadbeefdeadbeefULL, Raw[0]);
   EXPECT_EQ(0xdeadbeefdeadbeefULL, Raw[1]);
 }
 #if defined(__clang__)
 #pragma clang diagnostic pop
 #pragma clang diagnostic pop
 #endif
 }
+
+TEST(APIntTest, reverseBits) {
+  EXPECT_EQ(1, APInt(1, 1).reverseBits());
+  EXPECT_EQ(0, APInt(1, 0).reverseBits());
+
+  EXPECT_EQ(3, APInt(2, 3).reverseBits());
+  EXPECT_EQ(3, APInt(2, 3).reverseBits());
+
+  EXPECT_EQ(0xb, APInt(4, 0xd).reverseBits());
+  EXPECT_EQ(0xd, APInt(4, 0xb).reverseBits());
+  EXPECT_EQ(0xf, APInt(4, 0xf).reverseBits());
+
+  EXPECT_EQ(0x30, APInt(7, 0x6).reverseBits());
+  EXPECT_EQ(0x5a, APInt(7, 0x2d).reverseBits());
+
+  EXPECT_EQ(0x0f, APInt(8, 0xf0).reverseBits());
+  EXPECT_EQ(0xf0, APInt(8, 0x0f).reverseBits());
+
+  EXPECT_EQ(0x0f0f, APInt(16, 0xf0f0).reverseBits());
+  EXPECT_EQ(0xf0f0, APInt(16, 0x0f0f).reverseBits());
+
+  EXPECT_EQ(0x0f0f0f0f, APInt(32, 0xf0f0f0f0).reverseBits());
+  EXPECT_EQ(0xf0f0f0f0, APInt(32, 0x0f0f0f0f).reverseBits());
+
+  EXPECT_EQ(0x402880a0 >> 1, APInt(31, 0x05011402).reverseBits());
+
+  EXPECT_EQ(0x0f0f0f0f, APInt(32, 0xf0f0f0f0).reverseBits());
+  EXPECT_EQ(0xf0f0f0f0, APInt(32, 0x0f0f0f0f).reverseBits());
+
+  EXPECT_EQ(0x0f0f0f0f0f0f0f0f, APInt(64, 0xf0f0f0f0f0f0f0f0).reverseBits());
+  EXPECT_EQ(0xf0f0f0f0f0f0f0f0, APInt(64, 0x0f0f0f0f0f0f0f0f).reverseBits());
+
+  for (unsigned N : { 1, 8, 16, 24, 31, 32, 33,
+                      63, 64, 65, 127, 128, 257, 1024 }) {
+    for (unsigned I = 0; I < N; ++I) {
+      APInt X = APInt::getOneBitSet(N, I);
+      APInt Y = APInt::getOneBitSet(N, N - (I + 1));
+      EXPECT_EQ(Y, X.reverseBits());
+      EXPECT_EQ(X, Y.reverseBits());
+    }
+  }
+}