[APFloat] Fix rotl/rotr when the shift amount is greater than the total bit width.

[joey]

Summary

As per the title, fix the rotation by not truncating the shift amount to the bit width.

Add a unit test to check that 1 << 33 produces 2.

[efriedma]

There are two problems with the rotl() proposed by this patch:

1. getZExtValue() will cause an assertion failure if the shift amount is greater than 2^64.
2. Truncation doesn't work correctly if the bitwidth of the APInt isn't a power of two; you need to use urem or something like that.

[joey]

Updated the code to use 'urem' to get the remainder, rather than calling getZExtValue.

Should the APInt rotateAmt need to have the same bitwidth as the APInt the rotl is being called on? urem and a few other methods need that.

[efriedma]

Should the APInt rotateAmt need to have the same bitwidth as the APInt the rotl is being called on?

I don't see any reason to add that restriction. (Please add a test for this.)

---

Please add a testcase for a very large rotate amount (greater than 2^64). Please add testcases for rotating an integer whose bit-width is not a power of two.

lib/Support/APInt.cpp

1261

"APInt(rotBitWidth, BitWidth)" could be zero. (For example, APInt(32, 1).rotl(APInt(1, 1)). Please add this as a testcase.)

[joey]

Added a test case using the 'Big' number in the unit test.
Added a test case for a 7-bit number.
Added cases where the previous code would assert due to RHS being 0.

[joey]

lib/Support/APInt.cpp

1261

I've changed this to declare 'rem' where it's first assigned (line 1253). I'll upload again once Eli has taken another look.

[efriedma]

lib/Support/APInt.cpp

1265

Please factor out the common code from rotl and rotr into a helper function. Maybe also add a comment describing why it's implemented in this particular way, since it's a bit subtle.

[joey]

Created a helper function with some comments.

[efriedma]

lib/Support/APInt.cpp

1273

Please move the call to getLimitedValue() into the helper.

[joey]

Moved the getLimitedValue call into the helper function.

Sorry for the delay.

[efriedma]

LGTM.

[efriedma]

Do you need me to commit this for you?

lib/Support/APInt.cpp

APInt APInt::shlSlowCase(unsigned shiftAmt) const {
   val[offset] = pVal[0] << wordShift;
   for (i = 0; i < offset; ++i)
     val[i] = 0;
   APInt Result(val, BitWidth);
   Result.clearUnusedBits();
   return Result;
 }
 
+// Calculate the rotate amount modulo the bit width.
+static APInt rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
+  unsigned rotBitWidth = rotateAmt.getBitWidth();
+  APInt rot = rotateAmt;
+  if (rotBitWidth < BitWidth) {
+    // Extend the rotate APInt, so that the urem doesn't divide by 0.
+    // e.g. APInt(1, 32) would give APInt(1, 0).
+    rot = rotateAmt.zext(BitWidth);
+  }
+  return rot.urem(APInt(rot.getBitWidth(), BitWidth));
+}
+
 APInt APInt::rotl(const APInt &rotateAmt) const {
-  return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
+  APInt rem = rotateModulo(BitWidth, rotateAmt);
+  return rotl((unsigned)rem.getLimitedValue(BitWidth));
 }
 
 APInt APInt::rotl(unsigned rotateAmt) const {
   rotateAmt %= BitWidth;
   if (rotateAmt == 0)
     return *this;
   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
 }
 
 APInt APInt::rotr(const APInt &rotateAmt) const {
-  return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
+  APInt rem = rotateModulo(BitWidth, rotateAmt);
+  return rotr((unsigned)rem.getLimitedValue(BitWidth));
 }
 
 APInt APInt::rotr(unsigned rotateAmt) const {
   rotateAmt %= BitWidth;
   if (rotateAmt == 0)
     return *this;
   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
 }

unittests/ADT/APIntTest.cpp

TEST(APIntTest, Rotate) {
   EXPECT_EQ(APInt(8, 1),  APInt(8, 1).rotl(8));
 
   EXPECT_EQ(APInt(8, 16), APInt(8, 16).rotl(0));
   EXPECT_EQ(APInt(8, 32), APInt(8, 16).rotl(1));
   EXPECT_EQ(APInt(8, 64), APInt(8, 16).rotl(2));
   EXPECT_EQ(APInt(8, 1),  APInt(8, 16).rotl(4));
   EXPECT_EQ(APInt(8, 16), APInt(8, 16).rotl(8));
 
+  EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(33));
+  EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(APInt(32, 33)));
+  EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(APInt(33, 33)));
+  EXPECT_EQ(APInt(32, (1 << 8)), APInt(32, 1).rotl(APInt(32, 40)));
+  EXPECT_EQ(APInt(32, (1 << 30)), APInt(32, 1).rotl(APInt(31, 30)));
+  EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotl(APInt(31, 31)));
+
+  EXPECT_EQ(APInt(32, 1), APInt(32, 1).rotl(APInt(1, 0)));
+  EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(APInt(1, 1)));
+
+  EXPECT_EQ(APInt(32, 16), APInt(32, 1).rotl(APInt(3, 4)));
+
+  EXPECT_EQ(APInt(32, 1), APInt(32, 1).rotl(APInt(64, 64)));
+  EXPECT_EQ(APInt(32, 2), APInt(32, 1).rotl(APInt(64, 65)));
+
+  EXPECT_EQ(APInt(7, 24), APInt(7, 3).rotl(APInt(7, 3)));
+  EXPECT_EQ(APInt(7, 24), APInt(7, 3).rotl(APInt(7, 10)));
+  EXPECT_EQ(APInt(7, 24), APInt(7, 3).rotl(APInt(5, 10)));
+  EXPECT_EQ(APInt(7, 6), APInt(7, 3).rotl(APInt(12, 120)));
+
   EXPECT_EQ(APInt(8, 16), APInt(8, 16).rotr(0));
   EXPECT_EQ(APInt(8, 8),  APInt(8, 16).rotr(1));
   EXPECT_EQ(APInt(8, 4),  APInt(8, 16).rotr(2));
   EXPECT_EQ(APInt(8, 1),  APInt(8, 16).rotr(4));
   EXPECT_EQ(APInt(8, 16), APInt(8, 16).rotr(8));
 
   EXPECT_EQ(APInt(8, 1),   APInt(8, 1).rotr(0));
   EXPECT_EQ(APInt(8, 128), APInt(8, 1).rotr(1));
   EXPECT_EQ(APInt(8, 64),  APInt(8, 1).rotr(2));
   EXPECT_EQ(APInt(8, 16),  APInt(8, 1).rotr(4));
   EXPECT_EQ(APInt(8, 1),   APInt(8, 1).rotr(8));
 
-  APInt Big(256, "00004000800000000000000000003fff8000000000000000", 16);
-  APInt Rot(256, "3fff80000000000000000000000000000000000040008000", 16);
+  EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(33));
+  EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(APInt(32, 33)));
+  EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(APInt(33, 33)));
+  EXPECT_EQ(APInt(32, (1 << 24)), APInt(32, 1).rotr(APInt(32, 40)));
+
+  EXPECT_EQ(APInt(32, (1 << 2)), APInt(32, 1).rotr(APInt(31, 30)));
+  EXPECT_EQ(APInt(32, (1 << 1)), APInt(32, 1).rotr(APInt(31, 31)));
+
+  EXPECT_EQ(APInt(32, 1), APInt(32, 1).rotr(APInt(1, 0)));
+  EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(APInt(1, 1)));
+
+  EXPECT_EQ(APInt(32, (1 << 28)), APInt(32, 1).rotr(APInt(3, 4)));
+
+  EXPECT_EQ(APInt(32, 1), APInt(32, 1).rotr(APInt(64, 64)));
+  EXPECT_EQ(APInt(32, (1 << 31)), APInt(32, 1).rotr(APInt(64, 65)));
+
+  EXPECT_EQ(APInt(7, 48), APInt(7, 3).rotr(APInt(7, 3)));
+  EXPECT_EQ(APInt(7, 48), APInt(7, 3).rotr(APInt(7, 10)));
+  EXPECT_EQ(APInt(7, 48), APInt(7, 3).rotr(APInt(5, 10)));
+  EXPECT_EQ(APInt(7, 65), APInt(7, 3).rotr(APInt(12, 120)));
+
+  APInt Big(256, "00004000800000000000000000003fff8000000000000003", 16);
+  APInt Rot(256, "3fff80000000000000030000000000000000000040008000", 16);
   EXPECT_EQ(Rot, Big.rotr(144));
+
+  EXPECT_EQ(APInt(32, 8), APInt(32, 1).rotl(Big));
+  EXPECT_EQ(APInt(32, (1 << 29)), APInt(32, 1).rotr(Big));
 }
 
 TEST(APIntTest, Splat) {
   APInt ValA(8, 0x01);
   EXPECT_EQ(ValA, APInt::getSplat(8, ValA));
   EXPECT_EQ(APInt(64, 0x0101010101010101ULL), APInt::getSplat(64, ValA));
 
   APInt ValB(3, 5);