[APInt] Add setLowBits/setHighBits methods to APInt.

[craig.topper]

Summary

There are quite a few places in the code base that do something like the following to set the high or low bits in an APInt.

KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);

For BitWidths larger than 64 this creates a short lived APInt with malloced storage. I think it might even call malloc twice. Its better to just provide methods that can set the necessary bits without the temporary APInt.

I'll update usages that benefit in a separate patch.

[craig.topper]

Fixed a copy/paste mistake

[craig.topper]

Add a clearUpperBits call to the fast part of setHighBits along with a test case.

[davide]

Reducing malloc() traffic is generally a good thing, so is this patch. It's particularly slow on some systems (Windows), and FWIW, not great also on Linux with the default allocator (I ended up replacing my malloc() with tcmalloc everywhere, but that's a story for another day). That said, I'm curious if you're actually able to measure any compile time reduction with this change on the cases you plan to switch.

[davide]

include/llvm/ADT/APInt.h

1253 ↗

(On Diff #90287)

Please end comments with a full stop (here and everywhere else). I know we're a bit inconsistent in this file, but we should get this right for newly introduced code.

[craig.topper]

Add periods at the end of comments.

[craig.topper]

I haven't tried to measure any compile time differences. I was just inspired by Simon's patch for setBits and observing that ORing getLowBits/getHighBits was a common idiom in some places like ValueTracking. I assume we aren't often dealing larger than 64-bit numbers there on most types of compiled code.

[RKSimon]

Wouldn't the getHighBitsSet/getLowBitsSet statics benefit from using this?

[craig.topper]

@RKSimon , yes I think getLowBitsSet/getHighBitsSet would also benefit. I think they are mallocing twice due to the getAllOnes and then shifting. So I think we should be able to just create an all 0s APInt then call setLowBits/setHighBits instead and save one of the mallocs.

[hans]

The code looks fine to me, but I wonder if this buys much compared to APInt::setBits, which can easily be used to set only low or high bits. (The single-word case of that should probably be provided in an inline method actually?)

[craig.topper]

I'm definitely going to look at moving some of setBits inline. I'm also planning to fix getBitsSet to use setBits. I might even fix setBits to support loBit > hiBit like getBitsSet supports.

I think it at least makes sense to have setLowBits/setHighBits as convenience methods. Particularly for setHighBits the caller shouldn't have to write setBits(BitWidth, BitWidth - hiBitsToSet).

[hans]

In D30525#691195, @craig.topper wrote:

I think it at least makes sense to have setLowBits/setHighBits as convenience methods. Particularly for setHighBits the caller shouldn't have to write setBits(BitWidth, BitWidth - hiBitsToSet).

Yes, agreed.

[craig.topper]

Make some portions of setBits inline. Use it to implement setLowBits and setHighBits.

[RKSimon]

In D30525#691195, @craig.topper wrote:

I might even fix setBits to support loBit > hiBit like getBitsSet supports.

I'm not sure about this, which is why I didn't implement that way originally. Uses of getBitsSet are quite rare (and often could be replaced with simpler alternatives) - I'm still not sure if there are any uses of the 'wraparound' ability (or whether they are intentional....).

[hans]

lib/Support/APInt.cpp

575 ↗

(On Diff #90428)

This comment isn't really true anymore since you're only creating loMask (and when it gets left-shifted later, the name loMask isn't really appropriate anymore).

It might make sense to keep these two cases separate and let the compiler handle the redundant instructions.

I see the logic is changing a little, with hiWord now referring to whichWord(hiBit) instead of whichWord(hiBit - 1). Did you find a bug, or is this just trying to make the code clearer?

[craig.topper]

lib/Support/APInt.cpp

575 ↗

(On Diff #90428)

No bug. Was just trying to see if I could do it with less -1. I'll change it back to replicating the redundant instructions again.

[craig.topper]

Cleanup the comments in setBitsSlowCase. Modify the implementation to just AND the low and high masks together when loWord and hiWord are the same.

[hans]

lgtm

include/llvm/ADT/APInt.h

226 ↗

(On Diff #90562)

Nit: the other methods use /// to get doxygen comments.

unittests/ADT/APIntTest.cpp

1664 ↗

(On Diff #90562)

Nit: looks like an extra newline here.

llvm/trunk/include/llvm/ADT/APInt.h

class LLVM_NODISCARD APInt {
   unsigned countLeadingZerosSlowCase() const;
 
   /// out-of-line slow case for countTrailingOnes
   unsigned countTrailingOnesSlowCase() const;
 
   /// out-of-line slow case for countPopulation
   unsigned countPopulationSlowCase() const;
 
+  /// out-of-line slow case for setBits.
+  void setBitsSlowCase(unsigned loBit, unsigned hiBit);
+
 public:
   /// \name Constructors
   /// @{
 
   /// \brief Create a new APInt of numBits width, initialized as val.
   ///
   /// If isSigned is true then val is treated as if it were a signed value
   /// (i.e. as an int64_t) and the appropriate sign extension to the bit width
public:
   }
 
   /// \brief Set a given bit to 1.
   ///
   /// Set the given bit to 1 whose position is given as "bitPosition".
   void setBit(unsigned bitPosition);
 
   /// Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
-  void setBits(unsigned loBit, unsigned hiBit);
+  void setBits(unsigned loBit, unsigned hiBit) {
+    assert(hiBit <= BitWidth && "hiBit out of range");
+    assert(loBit <= hiBit && "loBit out of range");
+    if (loBit == hiBit)
+      return;
+    if (loBit < APINT_BITS_PER_WORD && hiBit <= APINT_BITS_PER_WORD) {
+      uint64_t mask = UINT64_MAX >> (APINT_BITS_PER_WORD - (hiBit - loBit));
+      mask <<= loBit;
+      if (isSingleWord())
+        VAL |= mask;
+      else
+        pVal[0] |= mask;
+    } else {
+      setBitsSlowCase(loBit, hiBit);
+    }
+  }
+
+  /// Set the bottom loBits bits.
+  void setLowBits(unsigned loBits) {
+    return setBits(0, loBits);
+  }
+
+  /// Set the top hiBits bits.
+  void setHighBits(unsigned hiBits) {
+    return setBits(BitWidth - hiBits, BitWidth);
+  }
 
   /// \brief Set every bit to 0.
   void clearAllBits() {
     if (isSingleWord())
       VAL = 0;
     else
       memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
   }

llvm/trunk/lib/Support/APInt.cpp

 
 void APInt::setBit(unsigned bitPosition) {
   if (isSingleWord())
     VAL |= maskBit(bitPosition);
   else
     pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
 }
 
-void APInt::setBits(unsigned loBit, unsigned hiBit) {
-  assert(hiBit <= BitWidth && "hiBit out of range");
-  assert(loBit <= hiBit && loBit <= BitWidth && "loBit out of range");
-
-  if (loBit == hiBit)
-    return;
-
-  if (isSingleWord())
-    *this |= APInt::getBitsSet(BitWidth, loBit, hiBit);
-  else {
-    unsigned hiBit1 = hiBit - 1;
-    unsigned loWord = whichWord(loBit);
-    unsigned hiWord = whichWord(hiBit1);
-    if (loWord == hiWord) {
-      // Set bits are all within the same word, create a [loBit,hiBit) mask.
-      uint64_t mask = UINT64_MAX;
-      mask >>= (APINT_BITS_PER_WORD - (hiBit - loBit));
-      mask <<= whichBit(loBit);
-      pVal[loWord] |= mask;
-    } else {
-      // Set bits span multiple words, create a lo mask with set bits starting
-      // at loBit, a hi mask with set bits below hiBit and set all bits of the
-      // words in between.
-      uint64_t loMask = UINT64_MAX << whichBit(loBit);
-      uint64_t hiMask = UINT64_MAX >> (64 - whichBit(hiBit1) - 1);
-      pVal[loWord] |= loMask;
+void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
+  unsigned hiWord = whichWord(hiBit);
+
+  // Create an initial mask for the low word with zeroes below loBit.
+
+  // If hiBit is not aligned, we need a high mask.
+  unsigned hiShiftAmt = whichBit(hiBit);
+  if (hiShiftAmt != 0) {
+    // Create a high mask with zeros above hiBit.
+    uint64_t hiMask = UINT64_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);
+    // If loWord and hiWord are equal, then we combine the masks. Otherwise,
+    // set the bits in hiWord.
+    if (hiWord == loWord)
+      loMask &= hiMask;
+    else
       pVal[hiWord] |= hiMask;
-      for (unsigned word = loWord + 1; word < hiWord; ++word)
-        pVal[word] = UINT64_MAX;
-    }
-  }
-}
+  }
+  // Apply the mask to the low word.
+  pVal[loWord] |= loMask;
+
+  // Fill any words between loWord and hiWord with all ones.
 
 /// Set the given bit to 0 whose position is given as "bitPosition".
 /// @brief Set a given bit to 0.
 void APInt::clearBit(unsigned bitPosition) {
   if (isSingleWord())
     VAL &= ~maskBit(bitPosition);
   else
     pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);

llvm/trunk/unittests/ADT/APIntTest.cpp

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());
 }
+
+TEST(APIntTest, setLowBits) {
+  APInt i64lo32(64, 0);
+  i64lo32.setLowBits(32);
+  EXPECT_EQ(0u, i64lo32.countLeadingOnes());
+  EXPECT_EQ(32u, i64lo32.countLeadingZeros());
+  EXPECT_EQ(32u, i64lo32.getActiveBits());
+  EXPECT_EQ(0u, i64lo32.countTrailingZeros());
+  EXPECT_EQ(32u, i64lo32.countTrailingOnes());
+  EXPECT_EQ(32u, i64lo32.countPopulation());
+
+  APInt i128lo64(128, 0);
+  i128lo64.setLowBits(64);
+  EXPECT_EQ(0u, i128lo64.countLeadingOnes());
+  EXPECT_EQ(64u, i128lo64.countLeadingZeros());
+  EXPECT_EQ(64u, i128lo64.getActiveBits());
+  EXPECT_EQ(0u, i128lo64.countTrailingZeros());
+  EXPECT_EQ(64u, i128lo64.countTrailingOnes());
+  EXPECT_EQ(64u, i128lo64.countPopulation());
+
+  APInt i128lo24(128, 0);
+  i128lo24.setLowBits(24);
+  EXPECT_EQ(0u, i128lo24.countLeadingOnes());
+  EXPECT_EQ(104u, i128lo24.countLeadingZeros());
+  EXPECT_EQ(24u, i128lo24.getActiveBits());
+  EXPECT_EQ(0u, i128lo24.countTrailingZeros());
+  EXPECT_EQ(24u, i128lo24.countTrailingOnes());
+  EXPECT_EQ(24u, i128lo24.countPopulation());
+
+  APInt i128lo104(128, 0);
+  i128lo104.setLowBits(104);
+  EXPECT_EQ(0u, i128lo104.countLeadingOnes());
+  EXPECT_EQ(24u, i128lo104.countLeadingZeros());
+  EXPECT_EQ(104u, i128lo104.getActiveBits());
+  EXPECT_EQ(0u, i128lo104.countTrailingZeros());
+  EXPECT_EQ(104u, i128lo104.countTrailingOnes());
+  EXPECT_EQ(104u, i128lo104.countPopulation());
+
+  APInt i128lo0(128, 0);
+  i128lo0.setLowBits(0);
+  EXPECT_EQ(0u, i128lo0.countLeadingOnes());
+  EXPECT_EQ(128u, i128lo0.countLeadingZeros());
+  EXPECT_EQ(0u, i128lo0.getActiveBits());
+  EXPECT_EQ(128u, i128lo0.countTrailingZeros());
+  EXPECT_EQ(0u, i128lo0.countTrailingOnes());
+  EXPECT_EQ(0u, i128lo0.countPopulation());
+
+  APInt i80lo79(80, 0);
+  i80lo79.setLowBits(79);
+  EXPECT_EQ(0u, i80lo79.countLeadingOnes());
+  EXPECT_EQ(1u, i80lo79.countLeadingZeros());
+  EXPECT_EQ(79u, i80lo79.getActiveBits());
+  EXPECT_EQ(0u, i80lo79.countTrailingZeros());
+  EXPECT_EQ(79u, i80lo79.countTrailingOnes());
+  EXPECT_EQ(79u, i80lo79.countPopulation());
+}
+
+TEST(APIntTest, setHighBits) {
+  APInt i64hi32(64, 0);
+  i64hi32.setHighBits(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());
+
+  APInt i128hi64(128, 0);
+  i128hi64.setHighBits(64);
+  EXPECT_EQ(64u, i128hi64.countLeadingOnes());
+  EXPECT_EQ(0u, i128hi64.countLeadingZeros());
+  EXPECT_EQ(128u, i128hi64.getActiveBits());
+  EXPECT_EQ(64u, i128hi64.countTrailingZeros());
+  EXPECT_EQ(0u, i128hi64.countTrailingOnes());
+  EXPECT_EQ(64u, i128hi64.countPopulation());
+
+  APInt i128hi24(128, 0);
+  i128hi24.setHighBits(24);
+  EXPECT_EQ(24u, i128hi24.countLeadingOnes());
+  EXPECT_EQ(0u, i128hi24.countLeadingZeros());
+  EXPECT_EQ(128u, i128hi24.getActiveBits());
+  EXPECT_EQ(104u, i128hi24.countTrailingZeros());
+  EXPECT_EQ(0u, i128hi24.countTrailingOnes());
+  EXPECT_EQ(24u, i128hi24.countPopulation());
+
+  APInt i128hi104(128, 0);
+  i128hi104.setHighBits(104);
+  EXPECT_EQ(104u, i128hi104.countLeadingOnes());
+  EXPECT_EQ(0u, i128hi104.countLeadingZeros());
+  EXPECT_EQ(128u, i128hi104.getActiveBits());
+  EXPECT_EQ(24u, i128hi104.countTrailingZeros());
+  EXPECT_EQ(0u, i128hi104.countTrailingOnes());
+  EXPECT_EQ(104u, i128hi104.countPopulation());
+
+  APInt i128hi0(128, 0);
+  i128hi0.setHighBits(0);
+  EXPECT_EQ(0u, i128hi0.countLeadingOnes());
+  EXPECT_EQ(128u, i128hi0.countLeadingZeros());
+  EXPECT_EQ(0u, i128hi0.getActiveBits());
+  EXPECT_EQ(128u, i128hi0.countTrailingZeros());
+  EXPECT_EQ(0u, i128hi0.countTrailingOnes());
+  EXPECT_EQ(0u, i128hi0.countPopulation());
+
+  APInt i80hi1(80, 0);
+  i80hi1.setHighBits(1);
+  EXPECT_EQ(1u, i80hi1.countLeadingOnes());
+  EXPECT_EQ(0u, i80hi1.countLeadingZeros());
+  EXPECT_EQ(80u, i80hi1.getActiveBits());
+  EXPECT_EQ(79u, i80hi1.countTrailingZeros());
+  EXPECT_EQ(0u, i80hi1.countTrailingOnes());
+  EXPECT_EQ(1u, i80hi1.countPopulation());
+
+  APInt i32hi16(32, 0);
+  i32hi16.setHighBits(16);
+  EXPECT_EQ(16u, i32hi16.countLeadingOnes());
+  EXPECT_EQ(0u, i32hi16.countLeadingZeros());
+  EXPECT_EQ(32u, i32hi16.getActiveBits());
+  EXPECT_EQ(16u, i32hi16.countTrailingZeros());
+  EXPECT_EQ(0u, i32hi16.countTrailingOnes());
+  EXPECT_EQ(16u, i32hi16.countPopulation());
+}