[APInt] Add a concat method, use LLVM_UNLIKELY to help optimizer.

[lattner]

Summary

Three unrelated changes:

1. Add a concat method as a convenience to help write bitvector use cases in a nicer way.
2. Use LLVM_UNLIKELY as suggested by @xbolva00 in a previous patch.
3. Fix casing of some "slow" methods to follow naming standards.

[lattner]

Capitalize identifiers to follow prevailing convention, and fix a comment typo. NFC.

[craig.topper]

llvm/include/llvm/ADT/APInt.h

350–351

This is may be too subtle, but we can avoid a branch here if we use.

U.VAL == WORDTYPE_MAX >> ((APINT_BITS_PER_WORD - BitWidth) & 0x3f);

That will alias 64 and 0 to both use WORD_TYPE for the compare. Since U.VAL should always be 0 for BitWidth == 0. The compare would always fail.

llvm/lib/Support/APInt.cpp

344

I was wondering if insertBits would be better here, but the last resort code in that resorts to copying bit by bit. But it would avoid a second heap allocation for widening the LSB. So maybe worth improving insertBits.

[lattner]

llvm/include/llvm/ADT/APInt.h

350–351

I like it, I'll pull this in.

llvm/lib/Support/APInt.cpp

344

I didn't spend much time worrying about this, but I'll look at improving this. Thanks!

[lattner]

Incorporate Craig's feedback: Optimize isAllOnes and concatSlowCase

Also change more variable names to appease clang-tidy.

[foad]

llvm/include/llvm/ADT/APInt.h

884

Is there a reason for the argument to be NewLSB instead of NewMSB?

If there was a non-member form would it be static APInt concat(const APInt &MSB, const APInt &LSB)? I would slightly prefer a (LSB, MSB) argument order, but I guess there is no real consistency in existing APIs.

llvm/lib/Support/APInt.cpp

345

Larger than what? Did you mean "large"?

[lattner]

llvm/include/llvm/ADT/APInt.h

884

Yes, check out the unit tests. I actually started this way, but it was too weird for:

APInt(0xA).concat(APInt(0xB)).concat(APInt(0xC)) == 0xCBA

Given how dot syntax works, it is better for this to be NewLSB.

llvm/lib/Support/APInt.cpp

345

Yes, thank you for catching that. Fixed to "large".

[lattner]

Comment typo fix, NFC.

[lattner]

I don't hear any concerns, I'll plan to land this later today unless anyone has an objection - thanks!

llvm/include/llvm/ADT/APInt.h

public:
 
   /// Determine if this APInt Value is non-positive (<= 0).
   ///
   /// \returns true if this APInt is non-positive.
   bool isNonPositive() const { return !isStrictlyPositive(); }
 
   /// Determine if all bits are set.
   bool isAllOnes() const {
     if (isSingleWord()) {
-      if (BitWidth == 0)
-        return false;
-      return U.VAL == WORDTYPE_MAX >> (APINT_BITS_PER_WORD - BitWidth);
+      // Calculate the shift amount, handling the zero-bit wide case without UB.
+      unsigned ShiftAmt =
+          (APINT_BITS_PER_WORD - BitWidth) % APINT_BITS_PER_WORD;
+      return U.VAL == WORDTYPE_MAX >> ShiftAmt;
     }
     return countTrailingOnesSlowCase() == BitWidth;
   }
 
   /// NOTE: This is soft-deprecated.  Please use `isAllOnes()` instead.
   bool isAllOnesValue() const { return isAllOnes(); }
 
   /// Determine if this value is zero, i.e. all bits are clear.
APInt &operator=(const APInt &RHS) {
     // The common case (both source or dest being inline) doesn't require
     // allocation or deallocation.
     if (isSingleWord() && RHS.isSingleWord()) {
       U.VAL = RHS.U.VAL;
       BitWidth = RHS.BitWidth;
       return *this;
     }
 
-    AssignSlowCase(RHS);
+    assignSlowCase(RHS);
     return *this;
   }
 
   /// Move assignment operator.
   APInt &operator=(APInt &&that) {
 #ifdef EXPENSIVE_CHECKS
     // Some std::shuffle implementations still do self-assignment.
     if (this == &that)
#endif
   /// assigned to *this.
   ///
   /// \returns *this after ANDing with RHS.
   APInt &operator&=(const APInt &RHS) {
     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     if (isSingleWord())
       U.VAL &= RHS.U.VAL;
     else
-      AndAssignSlowCase(RHS);
+      andAssignSlowCase(RHS);
     return *this;
   }
 
   /// Bitwise AND assignment operator.
   ///
   /// Performs a bitwise AND operation on this APInt and RHS. RHS is
   /// logically zero-extended or truncated to match the bit-width of
   /// the LHS.
#endif
   /// assigned *this;
   ///
   /// \returns *this after ORing with RHS.
   APInt &operator|=(const APInt &RHS) {
     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     if (isSingleWord())
       U.VAL |= RHS.U.VAL;
     else
-      OrAssignSlowCase(RHS);
+      orAssignSlowCase(RHS);
     return *this;
   }
 
   /// Bitwise OR assignment operator.
   ///
   /// Performs a bitwise OR operation on this APInt and RHS. RHS is
   /// logically zero-extended or truncated to match the bit-width of
   /// the LHS.
#endif
   /// assigned to *this.
   ///
   /// \returns *this after XORing with RHS.
   APInt &operator^=(const APInt &RHS) {
     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     if (isSingleWord())
       U.VAL ^= RHS.U.VAL;
     else
-      XorAssignSlowCase(RHS);
+      xorAssignSlowCase(RHS);
     return *this;
   }
 
   /// Bitwise XOR assignment operator.
   ///
   /// Performs a bitwise XOR operation on this APInt and RHS. RHS is
   /// logically zero-extended or truncated to match the bit-width of
   /// the LHS.
#endif
   }
 
   /// Rotate left by rotateAmt.
   APInt rotl(const APInt &rotateAmt) const;
 
   /// Rotate right by rotateAmt.
   APInt rotr(const APInt &rotateAmt) const;
 
+  /// Concatenate the bits from "NewLSB" onto the bottom of *this.  This is
+  /// equivalent to:
+  ///   (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth)
+  APInt concat(const APInt &NewLSB) const {
+    /// If the result will be small, then both the merged values are small.
+    unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth();
+    if (NewWidth <= APINT_BITS_PER_WORD)
+      return APInt(NewWidth, (U.VAL << NewLSB.getBitWidth()) | NewLSB.U.VAL);
+    return concatSlowCase(NewLSB);
+  }
+
   /// Unsigned division operation.
   ///
   /// Perform an unsigned divide operation on this APInt by RHS. Both this and
   /// RHS are treated as unsigned quantities for purposes of this division.
   ///
   /// \returns a new APInt value containing the division result, rounded towards
   /// zero.
   APInt udiv(const APInt &RHS) const;
#endif
   /// Equality operator.
   ///
   /// Compares this APInt with RHS for the validity of the equality
   /// relationship.
   bool operator==(const APInt &RHS) const {
     assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
     if (isSingleWord())
       return U.VAL == RHS.U.VAL;
-    return EqualSlowCase(RHS);
+    return equalSlowCase(RHS);
   }
 
   /// Equality operator.
   ///
   /// Compares this APInt with a uint64_t for the validity of the equality
   /// relationship.
   ///
   /// \returns true if *this == Val
#endif
   /// This function is an APInt version of the countLeadingOnes
   /// functions in MathExtras.h. It counts the number of ones from the most
   /// significant bit to the first zero bit.
   ///
   /// \returns 0 if the high order bit is not set, otherwise returns the number
   /// of 1 bits from the most significant to the least
   unsigned countLeadingOnes() const {
     if (isSingleWord()) {
-      if (BitWidth == 0)
+      if (LLVM_UNLIKELY(BitWidth == 0))
         return 0;
       return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
     }
     return countLeadingOnesSlowCase();
   }
 
   /// Computes the number of leading bits of this APInt that are equal to its
   /// sign bit.
private:
   union {
     uint64_t VAL;   ///< Used to store the <= 64 bits integer value.
     uint64_t *pVal; ///< Used to store the >64 bits integer value.
   } U;
 
   unsigned BitWidth; ///< The number of bits in this APInt.
 
   friend struct DenseMapInfo<APInt>;
-
   friend class APSInt;
 
   /// This constructor is used only internally for speed of construction of
   /// temporaries. It is unsafe since it takes ownership of the pointer, so it
   /// is not public.
   APInt(uint64_t *val, unsigned bits) : BitWidth(bits) { U.pVal = val; }
 
   /// Determine which word a bit is in.
private:
   /// significant word is assigned a value to ensure that those bits are
   /// zero'd out.
   APInt &clearUnusedBits() {
     // Compute how many bits are used in the final word.
     unsigned WordBits = ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1;
 
     // Mask out the high bits.
     uint64_t mask = WORDTYPE_MAX >> (APINT_BITS_PER_WORD - WordBits);
-    if (BitWidth == 0)
+    if (LLVM_UNLIKELY(BitWidth == 0))
       mask = 0;
 
     if (isSingleWord())
       U.VAL &= mask;
     else
       U.pVal[getNumWords() - 1] &= mask;
     return *this;
   }
private:
 
   /// out-of-line slow case for lshr.
   void lshrSlowCase(unsigned ShiftAmt);
 
   /// out-of-line slow case for ashr.
   void ashrSlowCase(unsigned ShiftAmt);
 
   /// out-of-line slow case for operator=
-  void AssignSlowCase(const APInt &RHS);
+  void assignSlowCase(const APInt &RHS);
 
   /// out-of-line slow case for operator==
-  bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY;
+  bool equalSlowCase(const APInt &RHS) const LLVM_READONLY;
 
   /// out-of-line slow case for countLeadingZeros
   unsigned countLeadingZerosSlowCase() const LLVM_READONLY;
 
   /// out-of-line slow case for countLeadingOnes.
   unsigned countLeadingOnesSlowCase() const LLVM_READONLY;
 
   /// out-of-line slow case for countTrailingZeros.
private:
   bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY;
 
   /// out-of-line slow case for setBits.
   void setBitsSlowCase(unsigned loBit, unsigned hiBit);
 
   /// out-of-line slow case for flipAllBits.
   void flipAllBitsSlowCase();
 
+  /// out-of-line slow case for concat.
+  APInt concatSlowCase(const APInt &NewLSB) const;
+
   /// out-of-line slow case for operator&=.
-  void AndAssignSlowCase(const APInt &RHS);
+  void andAssignSlowCase(const APInt &RHS);
 
   /// out-of-line slow case for operator|=.
-  void OrAssignSlowCase(const APInt &RHS);
+  void orAssignSlowCase(const APInt &RHS);
 
   /// out-of-line slow case for operator^=.
-  void XorAssignSlowCase(const APInt &RHS);
+  void xorAssignSlowCase(const APInt &RHS);
 
   /// Unsigned comparison. Returns -1, 0, or 1 if this APInt is less than, equal
   /// to, or greater than RHS.
   int compare(const APInt &RHS) const LLVM_READONLY;
 
   /// Signed comparison. Returns -1, 0, or 1 if this APInt is less than, equal
   /// to, or greater than RHS.
   int compareSigned(const APInt &RHS) const LLVM_READONLY;

llvm/lib/Support/APInt.cpp

void APInt::reallocate(unsigned NewBitWidth) {
   // Update BitWidth.
   BitWidth = NewBitWidth;
 
   // If we are supposed to have an allocation, create it.
   if (!isSingleWord())
     U.pVal = getMemory(getNumWords());
 }
 
-void APInt::AssignSlowCase(const APInt& RHS) {
+void APInt::assignSlowCase(const APInt &RHS) {
   // Don't do anything for X = X
   if (this == &RHS)
     return;
 
   // Adjust the bit width and handle allocations as necessary.
   reallocate(RHS.getBitWidth());
 
   // Copy the data.
if (isSingleWord())
     return APInt(BitWidth, U.VAL * RHS.U.VAL);
 
   APInt Result(getMemory(getNumWords()), getBitWidth());
   tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());
   Result.clearUnusedBits();
   return Result;
 }
 
-void APInt::AndAssignSlowCase(const APInt &RHS) {
+void APInt::andAssignSlowCase(const APInt &RHS) {
   WordType *dst = U.pVal, *rhs = RHS.U.pVal;
   for (size_t i = 0, e = getNumWords(); i != e; ++i)
     dst[i] &= rhs[i];
 }
 
-void APInt::OrAssignSlowCase(const APInt &RHS) {
+void APInt::orAssignSlowCase(const APInt &RHS) {
   WordType *dst = U.pVal, *rhs = RHS.U.pVal;
   for (size_t i = 0, e = getNumWords(); i != e; ++i)
     dst[i] |= rhs[i];
 }
 
-void APInt::XorAssignSlowCase(const APInt &RHS) {
+void APInt::xorAssignSlowCase(const APInt &RHS) {
   WordType *dst = U.pVal, *rhs = RHS.U.pVal;
   for (size_t i = 0, e = getNumWords(); i != e; ++i)
     dst[i] ^= rhs[i];
 }
 
 APInt &APInt::operator*=(const APInt &RHS) {
   *this = *this * RHS;
   return *this;
 }
 
 APInt& APInt::operator*=(uint64_t RHS) {
   if (isSingleWord()) {
     U.VAL *= RHS;
   } else {
     unsigned NumWords = getNumWords();
     tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
   }
   return clearUnusedBits();
 }
 
-bool APInt::EqualSlowCase(const APInt& RHS) const {
+bool APInt::equalSlowCase(const APInt &RHS) const {
   return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
 }
 
 int APInt::compare(const APInt& RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
   if (isSingleWord())
     return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;
 

 }
 
 /// Toggle every bit to its opposite value.
 void APInt::flipAllBitsSlowCase() {
   tcComplement(U.pVal, getNumWords());
   clearUnusedBits();
 }
 
+/// Concatenate the bits from "NewLSB" onto the bottom of *this.  This is
+/// equivalent to:
+///   (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth)
+/// In the slow case, we know the result is large.
+APInt APInt::concatSlowCase(const APInt &NewLSB) const {
+  unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth();
+  APInt Result = NewLSB.zext(NewWidth);
+  Result.insertBits(*this, NewLSB.getBitWidth());
+  return Result;
+}
+
 /// Toggle a given bit to its opposite value whose position is given
 /// as "bitPosition".
 /// Toggles a given bit to its opposite value.
 void APInt::flipBit(unsigned bitPosition) {
   assert(bitPosition < BitWidth && "Out of the bit-width range!");
   setBitVal(bitPosition, !(*this)[bitPosition]);
 }
 

 
 void APInt::shlSlowCase(unsigned ShiftAmt) {
   tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
   clearUnusedBits();
 }
 
 // Calculate the rotate amount modulo the bit width.
 static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
-  if (BitWidth == 0)
+  if (LLVM_UNLIKELY(BitWidth == 0))
     return 0;
   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);
   }
   rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
   return rot.getLimitedValue(BitWidth);
 }
 
 APInt APInt::rotl(const APInt &rotateAmt) const {
   return rotl(rotateModulo(BitWidth, rotateAmt));
 }
 
 APInt APInt::rotl(unsigned rotateAmt) const {
-  if (BitWidth == 0)
+  if (LLVM_UNLIKELY(BitWidth == 0))
     return *this;
   rotateAmt %= BitWidth;
   if (rotateAmt == 0)
     return *this;
   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
 }
 
 APInt APInt::rotr(const APInt &rotateAmt) const {

llvm/unittests/ADT/APIntTest.cpp

 
 TEST(APIntTest, truncOrSelf) {
   APInt val(32, 0xFFFFFFFF);
   EXPECT_EQ(0xFFFF, val.truncOrSelf(16));
   EXPECT_EQ(0xFFFFFFFF, val.truncOrSelf(32));
   EXPECT_EQ(0xFFFFFFFF, val.truncOrSelf(64));
 }
 
+TEST(APIntTest, concatMSB) {
+  APInt Int1(4, 0x1ULL);
+  APInt Int3(4, 0x3ULL);
+
+  EXPECT_EQ(0x31, Int3.concat(Int1));
+  EXPECT_EQ(APInt(12, 0x313), Int3.concat(Int1).concat(Int3));
+  EXPECT_EQ(APInt(16, 0x3313), Int3.concat(Int3).concat(Int1).concat(Int3));
+
+  APInt I64(64, 0x3ULL);
+  EXPECT_EQ(I64, I64.concat(I64).lshr(64).trunc(64));
+}
+
 TEST(APIntTest, multiply) {
   APInt i64(64, 1234);
 
   EXPECT_EQ(7006652, i64 * 5678);
   EXPECT_EQ(7006652, 5678 * i64);
 
   APInt i128 = APInt::getOneBitSet(128, 64);
   APInt i128_1234(128, 1234);