[APInt] add wrapping support for APInt::setBits

[shchenz]

Summary

This was supportted before https://reviews.llvm.org/rL301769.

In rL301769, It removed this support for no uses for this feature.
But getBitsSet which calls setBits still comment If hiBit is less than loBit then the set bits "wrap". . This is a little confusing.

I add this feature back because in PowerPC, I need it to combine two PPC::RLWINM which will be posted later. In PPC::RLWINM wrapping set bits is supportted.

[lebedev.ri]

I'd prefer to see the actual patch that makes use of this.
This doesn't address the cost issue noted in rL301769.

[lebedev.ri]

(just marking as reviewed)

[shchenz]

Use new function setBitsWithWrap to avoid setBits can not be inlined to setLowBits, setHighBits, and setBitsFrom

[shchenz]

Sorry for the delay. I use the method suggested in https://reviews.llvm.org/rL301769. The patch using this feature is https://reviews.llvm.org/D70374.
We want to set bits for mask of PPC instruciton rlwinm. That instruction supports wrap masks.

[shchenz]

fix one formatting issue.

[lebedev.ri]

llvm/include/llvm/ADT/APInt.h

606–611

These changes are still there

[lebedev.ri]

llvm/include/llvm/ADT/APInt.h

606–611

To reword, the suggestion is to

static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
  APInt Res(numBits, 0);
  Res.setBits(loBit, hiBit);
  return Res;
}

static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit, unsigned hiBit) {
  APInt Res(numBits, 0);
  Res.setBitsWithWrap(loBit, hiBit);
  return Res;
}

[shchenz]

llvm/include/llvm/ADT/APInt.h

606–611

I think if we want to avoid recursion in setBits, we just need to split setBits for wrap and non-wrap. I am not sure the benifit of spliting getBitsSet, could you point it out to me?

[lebedev.ri]

llvm/include/llvm/ADT/APInt.h

606–611

Presumably all existing users of getBitsSet() satisfy loBit <= hiBit precondition,
and don't need the new setBitsWithWrap() behaviour. Which means the getBitsSet()
change as-is will likely affect the performance of every current getBitsSet() user.
It may be best to simply not touch existing getBitsSet(), but add getBitsSetWithWrap().

[shchenz]

llvm/include/llvm/ADT/APInt.h

606–611

Now, after the change, every user of getBitsSet will check if (loBit <= hiBit) and all users will not go into new added setBitsWithWrap.

The perf impact mentioned in rL301769 is setBits can not call setLowBits or setHighBits. If we do, setBits will become a recurive function, and setBits can not be inlined to setLowBits or setHighBits. So we add another setBitsWithWrap function to avoid such case. For getBitsSet, there is no such issue?

And if we use getBitsSet and getBitsSetWithWrap, we have to call getBitsSet outside of APInt, like:

if (loBit > hiBit)
  getBitsSetWithWrap()
else
  getBitsSet()

This does not match the comment for getBitsSet.

[craig.topper]

I think setBitsWithWrap should call setBits if there is no wrap and call setLowBits and setHighBits if there is wrap. Matching the behavior setBits used to have. Any incorrect comments on setBits or getBitsSet should be fixed.

This gives places that want wrap the support they need inside of a APInt but doesn’t slow down or increase the code size of any of the existing callers of setBits.

[lebedev.ri]

llvm/include/llvm/ADT/APInt.h

606–611

Ah wait, i missed that we still need the check that there is a wrap, right.
Then i'd +1 to what @craig.topper said, and my original suggestion getBitsSetWithWrap() is applicable again.

[shchenz]

address @lebedev.ri and @craig.topper comments.

[lebedev.ri]

llvm/include/llvm/ADT/APInt.h

606–611

... and now you can actually do

static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
  APInt Res(numBits, 0);
  Res.setBits(loBit, hiBit);
  return Res;
}

static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit, unsigned hiBit) {
  APInt Res(numBits, 0);
  Res.setBitsWithWrap(loBit, hiBit);
  return Res;
}

1451–1456

Let's just go other way around, and early-return if no-wrap?

[shchenz]

Use two interface getBitsSet and getBitsSetWithWrap.

To be honest, I don't like this fix, it is a patch-like fix. In order to protect legacy usage, we create two functionally overlapping interfaces for both getBitsSet and setBits. But I can not find another better way to not change legacy usage for these functions, so let it be like now.

[lebedev.ri]

LGTM, thank you.

[craig.topper]

LGTM too

llvm/include/llvm/ADT/APInt.h

static APInt getOneBitSet(unsigned numBits, unsigned BitNo) {
     return Res;
   }
 
   /// Get a value with a block of bits set.
   ///
   /// Constructs an APInt value that has a contiguous range of bits set. The
   /// bits from loBit (inclusive) to hiBit (exclusive) will be set. All other
   /// bits will be zero. For example, with parameters(32, 0, 16) you would get
-  /// 0x0000FFFF. If hiBit is less than loBit then the set bits "wrap". For
-  /// example, with parameters (32, 28, 4), you would get 0xF000000F.
+  /// 0x0000FFFF. Please call getBitsSetWithWrap if \p loBit may be greater than
+  /// \p hiBit.
   ///
   /// \param numBits the intended bit width of the result
   /// \param loBit the index of the lowest bit set.
   /// \param hiBit the index of the highest bit set.
   ///
   /// \returns An APInt value with the requested bits set.
   static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit) {
+    assert(loBit <= hiBit && "loBit greater than hiBit");
     APInt Res(numBits, 0);
     Res.setBits(loBit, hiBit);
     return Res;
   }
 
+  /// Wrap version of getBitsSet.
+  /// If \p hiBit is no less than \p loBit, this is same with getBitsSet.
+  /// If \p hiBit is less than \p loBit, the set bits "wrap". For example, with
+  /// parameters (32, 28, 4), you would get 0xF000000F.
+  static APInt getBitsSetWithWrap(unsigned numBits, unsigned loBit,
+                                  unsigned hiBit) {
+    APInt Res(numBits, 0);
+    Res.setBitsWithWrap(loBit, hiBit);
+    return Res;
+  }
+
   /// Get a value with upper bits starting at loBit set.
   ///
   /// Constructs an APInt value that has a contiguous range of bits set. The
   /// bits from loBit (inclusive) to numBits (exclusive) will be set. All other
   /// bits will be zero. For example, with parameters(32, 12) you would get
   /// 0xFFFFF000.
   ///
   /// \param numBits the intended bit width of the result
#endif
   }
 
   /// Set the sign bit to 1.
   void setSignBit() {
     setBit(BitWidth - 1);
   }
 
   /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
+  /// This function handles "wrap" case when \p loBit > \p hiBit, and calls
+  /// setBits when \p loBit <= \p hiBit.
+  void setBitsWithWrap(unsigned loBit, unsigned hiBit) {
+    assert(hiBit <= BitWidth && "hiBit out of range");
+    assert(loBit <= BitWidth && "loBit out of range");
+    if (loBit <= hiBit) {
+      setBits(loBit, hiBit);
+      return;
+    }
+    setLowBits(hiBit);
+    setHighBits(BitWidth - loBit);
+  }
+
+  /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
+  /// This function handles case when \p loBit <= \p hiBit.
   void setBits(unsigned loBit, unsigned hiBit) {
     assert(hiBit <= BitWidth && "hiBit out of range");
     assert(loBit <= BitWidth && "loBit out of range");
     assert(loBit <= hiBit && "loBit greater than hiBit");
     if (loBit == hiBit)
       return;
     if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
       uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));

llvm/unittests/ADT/APIntTest.cpp

TEST(APIntTest, getBitsSet) {
   EXPECT_EQ(0u, i127hi1lo1.countLeadingOnes());
   EXPECT_EQ(1u, i127hi1lo1.countLeadingZeros());
   EXPECT_EQ(126u, i127hi1lo1.getActiveBits());
   EXPECT_EQ(1u, i127hi1lo1.countTrailingZeros());
   EXPECT_EQ(0u, i127hi1lo1.countTrailingOnes());
   EXPECT_EQ(125u, i127hi1lo1.countPopulation());
 }
 
+TEST(APIntTest, getBitsSetWithWrap) {
+  APInt i64hi1lo1 = APInt::getBitsSetWithWrap(64, 1, 63);
+  EXPECT_EQ(0u, i64hi1lo1.countLeadingOnes());
+  EXPECT_EQ(1u, i64hi1lo1.countLeadingZeros());
+  EXPECT_EQ(63u, i64hi1lo1.getActiveBits());
+  EXPECT_EQ(1u, i64hi1lo1.countTrailingZeros());
+  EXPECT_EQ(0u, i64hi1lo1.countTrailingOnes());
+  EXPECT_EQ(62u, i64hi1lo1.countPopulation());
+
+  APInt i127hi1lo1 = APInt::getBitsSetWithWrap(127, 1, 126);
+  EXPECT_EQ(0u, i127hi1lo1.countLeadingOnes());
+  EXPECT_EQ(1u, i127hi1lo1.countLeadingZeros());
+  EXPECT_EQ(126u, i127hi1lo1.getActiveBits());
+  EXPECT_EQ(1u, i127hi1lo1.countTrailingZeros());
+  EXPECT_EQ(0u, i127hi1lo1.countTrailingOnes());
+  EXPECT_EQ(125u, i127hi1lo1.countPopulation());
+
+  APInt i64hi1lo1wrap = APInt::getBitsSetWithWrap(64, 63, 1);
+  EXPECT_EQ(1u, i64hi1lo1wrap.countLeadingOnes());
+  EXPECT_EQ(0u, i64hi1lo1wrap.countLeadingZeros());
+  EXPECT_EQ(64u, i64hi1lo1wrap.getActiveBits());
+  EXPECT_EQ(0u, i64hi1lo1wrap.countTrailingZeros());
+  EXPECT_EQ(1u, i64hi1lo1wrap.countTrailingOnes());
+  EXPECT_EQ(2u, i64hi1lo1wrap.countPopulation());
+
+  APInt i127hi1lo1wrap = APInt::getBitsSetWithWrap(127, 126, 1);
+  EXPECT_EQ(1u, i127hi1lo1wrap.countLeadingOnes());
+  EXPECT_EQ(0u, i127hi1lo1wrap.countLeadingZeros());
+  EXPECT_EQ(127u, i127hi1lo1wrap.getActiveBits());
+  EXPECT_EQ(0u, i127hi1lo1wrap.countTrailingZeros());
+  EXPECT_EQ(1u, i127hi1lo1wrap.countTrailingOnes());
+  EXPECT_EQ(2u, i127hi1lo1wrap.countPopulation());
+}
+
 TEST(APIntTest, getHighBitsSet) {
   APInt i64hi32 = APInt::getHighBitsSet(64, 32);
   EXPECT_EQ(32u, i64hi32.countLeadingOnes());
   EXPECT_EQ(0u, i64hi32.countLeadingZeros());
   EXPECT_EQ(64u, i64hi32.getActiveBits());
   EXPECT_EQ(32u, i64hi32.countTrailingZeros());
   EXPECT_EQ(0u, i64hi32.countTrailingOnes());
   EXPECT_EQ(32u, i64hi32.countPopulation());