Index: include/llvm/ADT/APInt.h =================================================================== --- include/llvm/ADT/APInt.h +++ include/llvm/ADT/APInt.h @@ -1451,6 +1451,10 @@ /// \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; Index: lib/Analysis/ConstantFolding.cpp =================================================================== --- lib/Analysis/ConstantFolding.cpp +++ lib/Analysis/ConstantFolding.cpp @@ -1277,6 +1277,7 @@ 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: @@ -1609,6 +1610,8 @@ 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()); Index: lib/Support/APInt.cpp =================================================================== --- lib/Support/APInt.cpp +++ lib/Support/APInt.cpp @@ -787,6 +787,36 @@ return Result; } +APInt APInt::reverseBits() const { + switch (BitWidth) { + case 64: + return APInt(BitWidth, llvm::reverseBits(VAL)); + case 32: + return APInt(BitWidth, llvm::reverseBits(VAL)); + case 16: + return APInt(BitWidth, llvm::reverseBits(VAL)); + case 8: + return APInt(BitWidth, llvm::reverseBits(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; Index: test/Transforms/InstCombine/bitreverse-fold.ll =================================================================== --- test/Transforms/InstCombine/bitreverse-fold.ll +++ test/Transforms/InstCombine/bitreverse-fold.ll @@ -1,11 +1,96 @@ ; 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> +define <2 x i1> @reverse_true_v2i1() { + %x = call <2 x i1> @llvm.bitreverse.v2i1(<2 x i1> ) + ret <2 x i1> %x +} + +; CHECK-LABEL: @bitreverse_920_1234_v2i32( +; CHECK-NEXT: ret <2 x i32> +define <2 x i32> @bitreverse_920_1234_v2i32() { + %x = call <2 x i32> @llvm.bitreverse.v2i32(<2 x i32> ) + 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> +define <2 x i3> @reverse_6_3_v2i3() { + %x = call <2 x i3> @llvm.bitreverse.v2i3(<2 x i3> ) + 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 Index: unittests/ADT/APIntTest.cpp =================================================================== --- unittests/ADT/APIntTest.cpp +++ unittests/ADT/APIntTest.cpp @@ -1023,3 +1023,45 @@ #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()); + } + } +}