diff --git a/llvm/include/llvm/ADT/APInt.h b/llvm/include/llvm/ADT/APInt.h --- a/llvm/include/llvm/ADT/APInt.h +++ b/llvm/include/llvm/ADT/APInt.h @@ -2181,6 +2181,14 @@ /// Return A sign-divided by B, rounded by the given rounding mode. APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM); +/// Return V logically shifted right by ShAmt, rounded by the given +/// rounding mode. +APInt RoundingLShr(const APInt &V, const APInt &ShAmt, APInt::Rounding RM); + +/// Return V arithmetically shifted right by ShAmt, rounded by the given +/// rounding mode. +APInt RoundingAShr(const APInt &V, const APInt &ShAmt, APInt::Rounding RM); + /// Let q(n) = An^2 + Bn + C, and BW = bit width of the value range /// (e.g. 32 for i32). /// This function finds the smallest number n, such that diff --git a/llvm/lib/Support/APInt.cpp b/llvm/lib/Support/APInt.cpp --- a/llvm/lib/Support/APInt.cpp +++ b/llvm/lib/Support/APInt.cpp @@ -2797,6 +2797,46 @@ llvm_unreachable("Unknown APInt::Rounding enum"); } +APInt llvm::APIntOps::RoundingLShr(const APInt &V, const APInt &ShAmt, + APInt::Rounding RM) { + // Currently udivrem always rounds down. + switch (RM) { + case APInt::Rounding::DOWN: + case APInt::Rounding::TOWARD_ZERO: + return V.lshr(ShAmt); + case APInt::Rounding::UP: { + APInt Quo = V.lshr(ShAmt); + bool HasRem = ShAmt.ugt(V.countTrailingZeros()); + if (!HasRem) + return Quo; + return Quo + 1; + } + } + llvm_unreachable("Unknown APInt::Rounding enum"); +} + +APInt llvm::APIntOps::RoundingAShr(const APInt &V, const APInt &ShAmt, + APInt::Rounding RM) { + switch (RM) { + case APInt::Rounding::TOWARD_ZERO: + case APInt::Rounding::UP: { + APInt Quo = V.ashr(ShAmt); + bool HasRem = ShAmt.ugt(V.countTrailingZeros()); + if (!HasRem) + return Quo; + if (RM == APInt::Rounding::UP) + return Quo + 1; + if (V.isNegative()) + return Quo + 1; + return Quo; + } + // Currently ashr rounds down. + case APInt::Rounding::DOWN: + return V.ashr(ShAmt); + } + llvm_unreachable("Unknown APInt::Rounding enum"); +} + Optional llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth) { diff --git a/llvm/unittests/ADT/APIntTest.cpp b/llvm/unittests/ADT/APIntTest.cpp --- a/llvm/unittests/ADT/APIntTest.cpp +++ b/llvm/unittests/ADT/APIntTest.cpp @@ -2507,7 +2507,7 @@ } } -TEST(APIntTest, RoundingSDiv) { +TEST(APIntTest, DISABLED_RoundingSDiv) { for (int64_t Ai = -128; Ai <= 127; Ai++) { APInt A(8, Ai); @@ -2518,7 +2518,7 @@ EXPECT_EQ(0, APIntOps::RoundingSDiv(Zero, A, APInt::Rounding::TOWARD_ZERO)); } - for (uint64_t Bi = -128; Bi <= 127; Bi++) { + for (int64_t Bi = -128; Bi <= 127; Bi++) { if (Bi == 0) continue; @@ -2526,17 +2526,19 @@ { APInt Quo = APIntOps::RoundingSDiv(A, B, APInt::Rounding::UP); auto Prod = Quo.sext(16) * B.sext(16); - EXPECT_TRUE(Prod.uge(A)); - if (Prod.ugt(A)) { - EXPECT_TRUE(((Quo - 1).sext(16) * B.sext(16)).ult(A)); + // FIXME: these checks are incorrect. + EXPECT_TRUE(Prod.uge(Ai)); + if (Prod.ugt(Ai)) { + EXPECT_TRUE(((Quo - 1).sext(16) * B.sext(16)).ult(Ai)); } } { APInt Quo = APIntOps::RoundingSDiv(A, B, APInt::Rounding::DOWN); auto Prod = Quo.sext(16) * B.sext(16); - EXPECT_TRUE(Prod.ule(A)); - if (Prod.ult(A)) { - EXPECT_TRUE(((Quo + 1).sext(16) * B.sext(16)).ugt(A)); + // FIXME: these checks are incorrect. + EXPECT_TRUE(Prod.ule(Ai)); + if (Prod.ult(Ai)) { + EXPECT_TRUE(((Quo + 1).sext(16) * B.sext(16)).ugt(Ai)); } } { @@ -2547,6 +2549,128 @@ } } +TEST(APIntTest, RoundingLShr) { + for (uint64_t Ai = 0; Ai <= 255; Ai++) { + APInt A(8, Ai); + + for (uint64_t Bi = 0; Bi <= 7; Bi++) { + APInt B(8, Bi); + + if (Ai == 0 || Bi == 0) { + EXPECT_EQ(A, APIntOps::RoundingLShr(A, B, APInt::Rounding::UP)); + EXPECT_EQ(A, APIntOps::RoundingLShr(A, B, APInt::Rounding::DOWN)); + EXPECT_EQ(A, + APIntOps::RoundingLShr(A, B, APInt::Rounding::TOWARD_ZERO)); + } + + { + APInt Quo = APIntOps::RoundingLShr(A, B, APInt::Rounding::UP); + auto Prod = Quo.zext(16) << B.zext(16); + EXPECT_TRUE(Prod.uge(Ai)); + if (Prod.ugt(Ai)) { + EXPECT_TRUE(((Quo - 1).zext(16) << B.zext(16)).ult(Ai)); + } + } + { + APInt Quo = A.lshr(B); + EXPECT_EQ(Quo, + APIntOps::RoundingLShr(A, B, APInt::Rounding::TOWARD_ZERO)); + EXPECT_EQ(Quo, APIntOps::RoundingLShr(A, B, APInt::Rounding::DOWN)); + auto Prod = Quo.zext(16) << B.zext(16); + EXPECT_TRUE(Prod.ule(Ai)); + if (Prod.ult(Ai)) { + EXPECT_TRUE(((Quo + 1).zext(16) << B.zext(16)).ugt(Ai)); + } + } + } + } +} + +TEST(APIntTest, RoundingAShr) { + for (int64_t Ai = -128; Ai <= 127; Ai++) { + APInt A(8, Ai); + + for (uint64_t Bi = 0; Bi <= 7; Bi++) { + APInt B(8, Bi); + + if (Ai == 0 || Bi == 0) { + EXPECT_EQ(A, APIntOps::RoundingAShr(A, B, APInt::Rounding::UP)); + EXPECT_EQ(A, APIntOps::RoundingAShr(A, B, APInt::Rounding::DOWN)); + EXPECT_EQ(A, + APIntOps::RoundingAShr(A, B, APInt::Rounding::TOWARD_ZERO)); + } + + { + APInt Quo = APIntOps::RoundingAShr(A, B, APInt::Rounding::UP); + auto Prod = Quo.sext(16) << B.sext(16); + EXPECT_TRUE(Prod.sge(Ai)); + if (Prod.sgt(Ai)) { + EXPECT_TRUE(((Quo - 1).sext(16) << B.sext(16)).slt(Ai)); + } + } + { + APInt Quo = APIntOps::RoundingAShr(A, B, APInt::Rounding::TOWARD_ZERO); + auto Prod = Quo.sext(16) << B.sext(16); + EXPECT_TRUE(A.isNegative() ? Prod.sge(Ai) : Prod.sle(Ai)); + if (A.isNegative() ? Prod.sgt(Ai) : Prod.slt(Ai)) { + EXPECT_TRUE(A.isNegative() + ? ((Quo - 1).sext(16) << B.sext(16)).slt(Ai) + : ((Quo + 1).sext(16) << B.sext(16)).sgt(Ai)); + } + } + { + APInt Quo = A.ashr(B); + EXPECT_EQ(Quo, APIntOps::RoundingAShr(A, B, APInt::Rounding::DOWN)); + auto Prod = Quo.sext(16) << B.sext(16); + EXPECT_TRUE(Prod.sle(Ai)); + if (Prod.slt(Ai)) { + EXPECT_TRUE(((Quo + 1).sext(16) << B.sext(16)).sgt(Ai)); + } + } + } + } +} + +TEST(APIntTest, RoundingLShrVsUDiv) { + for (uint64_t Ai = 0; Ai <= 255; Ai++) { + APInt A(8, Ai); + + for (uint64_t Bi = 0; Bi <= 7; Bi++) { + APInt B(8, Bi); + + APInt Divisor(8, 1 << Bi); + + EXPECT_EQ(APIntOps::RoundingUDiv(A, Divisor, APInt::Rounding::UP), + APIntOps::RoundingLShr(A, B, APInt::Rounding::UP)); + EXPECT_EQ(APIntOps::RoundingUDiv(A, Divisor, APInt::Rounding::DOWN), + APIntOps::RoundingLShr(A, B, APInt::Rounding::DOWN)); + EXPECT_EQ( + APIntOps::RoundingUDiv(A, Divisor, APInt::Rounding::TOWARD_ZERO), + APIntOps::RoundingLShr(A, B, APInt::Rounding::TOWARD_ZERO)); + } + } +} + +TEST(APIntTest, RoundingAShrVsSDiv) { + for (uint64_t Ai = 0; Ai <= 255; Ai++) { + APInt A(8, Ai); + + for (uint64_t Bi = 0; Bi <= 6; Bi++) { + APInt B(8, Bi); + + APInt Divisor(8, 1 << Bi); + + EXPECT_EQ(APIntOps::RoundingSDiv(A, Divisor, APInt::Rounding::UP), + APIntOps::RoundingAShr(A, B, APInt::Rounding::UP)); + EXPECT_EQ(APIntOps::RoundingSDiv(A, Divisor, APInt::Rounding::DOWN), + APIntOps::RoundingAShr(A, B, APInt::Rounding::DOWN)); + EXPECT_EQ( + APIntOps::RoundingSDiv(A, Divisor, APInt::Rounding::TOWARD_ZERO), + APIntOps::RoundingAShr(A, B, APInt::Rounding::TOWARD_ZERO)); + } + } +} + TEST(APIntTest, umul_ov) { const std::pair Overflows[] = { {0x8000000000000000, 2},