[APInt] Add compare/compareSigned methods that return -1, 0, 1. Reimplement slt/ult and friends using them

[craig.topper]

Summary

Currently sle and ule have to call slt/ult and eq to get the proper answer. This results in extra code for both calls and additional scans of multiword APInts.

This patch replaces slt/ult with a compareSigned/compare that can return -1, 0, or 1 so we can cover all the comparison functions with a single call.

While I was there I removed the activeBits calls and other checks at the start of the slow part of ult. Both of the activeBits calls potentially scan through each of the APInts separately. I can't imagine that's any better than just scanning them in parallel and doing the compares.

These changes seem to be good for about a 7-8k reduction on the size of the opt binary on my local x86-64 build.

[craig.topper]

Just use tcCompare to implement the slow case compare code.

[RKSimon]

lib/Support/APInt.cpp

392 ↗

(On Diff #96102)

Better to call tcCompare directly?

[craig.topper]

Address Simon's comment.

[hans]

lgtm

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

private:
   void AndAssignSlowCase(const APInt& RHS);
 
   /// out-of-line slow case for operator|=.
   void OrAssignSlowCase(const APInt& RHS);
 
   /// out-of-line slow case for operator^=.
   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;
+
 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:
   bool ne(const APInt &RHS) const { return !((*this) == RHS); }
 
   /// \brief Unsigned less than comparison
   ///
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// the validity of the less-than relationship.
   ///
   /// \returns true if *this < RHS when both are considered unsigned.
-  bool ult(const APInt &RHS) const LLVM_READONLY;
+  bool ult(const APInt &RHS) const { return compare(RHS) < 0; }
 
   /// \brief Unsigned less than comparison
   ///
   /// Regards both *this as an unsigned quantity and compares it with RHS for
   /// the validity of the less-than relationship.
   ///
   /// \returns true if *this < RHS when considered unsigned.
   bool ult(uint64_t RHS) const {
     // Only need to check active bits if not a single word.
     return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
   }
 
   /// \brief Signed less than comparison
   ///
   /// Regards both *this and RHS as signed quantities and compares them for
   /// validity of the less-than relationship.
   ///
   /// \returns true if *this < RHS when both are considered signed.
-  bool slt(const APInt &RHS) const LLVM_READONLY;
+  bool slt(const APInt &RHS) const { return compareSigned(RHS) < 0; }
 
   /// \brief Signed less than comparison
   ///
   /// Regards both *this as a signed quantity and compares it with RHS for
   /// the validity of the less-than relationship.
   ///
   /// \returns true if *this < RHS when considered signed.
   bool slt(int64_t RHS) const {
     return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative()
                                                         : getSExtValue() < RHS;
   }
 
   /// \brief Unsigned less or equal comparison
   ///
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// validity of the less-or-equal relationship.
   ///
   /// \returns true if *this <= RHS when both are considered unsigned.
-  bool ule(const APInt &RHS) const { return ult(RHS) || eq(RHS); }
+  bool ule(const APInt &RHS) const { return compare(RHS) <= 0; }
 
   /// \brief Unsigned less or equal comparison
   ///
   /// Regards both *this as an unsigned quantity and compares it with RHS for
   /// the validity of the less-or-equal relationship.
   ///
   /// \returns true if *this <= RHS when considered unsigned.
   bool ule(uint64_t RHS) const { return !ugt(RHS); }
 
   /// \brief Signed less or equal comparison
   ///
   /// Regards both *this and RHS as signed quantities and compares them for
   /// validity of the less-or-equal relationship.
   ///
   /// \returns true if *this <= RHS when both are considered signed.
-  bool sle(const APInt &RHS) const { return slt(RHS) || eq(RHS); }
+  bool sle(const APInt &RHS) const { return compareSigned(RHS) <= 0; }
 
   /// \brief Signed less or equal comparison
   ///
   /// Regards both *this as a signed quantity and compares it with RHS for the
   /// validity of the less-or-equal relationship.
   ///
   /// \returns true if *this <= RHS when considered signed.
   bool sle(uint64_t RHS) const { return !sgt(RHS); }
 
   /// \brief Unsigned greather than comparison
   ///
   /// Regards both *this and RHS as unsigned quantities and compares them for
   /// the validity of the greater-than relationship.
   ///
   /// \returns true if *this > RHS when both are considered unsigned.
-  bool ugt(const APInt &RHS) const { return !ult(RHS) && !eq(RHS); }
+  bool ugt(const APInt &RHS) const { return !ule(RHS); }
 
   /// \brief Unsigned greater than comparison
   ///
   /// Regards both *this as an unsigned quantity and compares it with RHS for
   /// the validity of the greater-than relationship.
   ///
   /// \returns true if *this > RHS when considered unsigned.
   bool ugt(uint64_t RHS) const {
     // Only need to check active bits if not a single word.
     return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
   }
 
   /// \brief Signed greather than comparison
   ///
   /// Regards both *this and RHS as signed quantities and compares them for the
   /// validity of the greater-than relationship.
   ///
   /// \returns true if *this > RHS when both are considered signed.
-  bool sgt(const APInt &RHS) const { return !slt(RHS) && !eq(RHS); }
+  bool sgt(const APInt &RHS) const { return !sle(RHS); }
 
   /// \brief Signed greater than comparison
   ///
   /// Regards both *this as a signed quantity and compares it with RHS for
   /// the validity of the greater-than relationship.
   ///
   /// \returns true if *this > RHS when considered signed.
   bool sgt(int64_t RHS) const {

llvm/trunk/lib/Support/APInt.cpp

APInt APInt::operator*(const APInt& RHS) const {
   Result *= RHS;
   return Result;
 }
 
 bool APInt::EqualSlowCase(const APInt& RHS) const {
   return std::equal(pVal, pVal + getNumWords(), RHS.pVal);
 }
 
-bool APInt::ult(const APInt& RHS) const {
+int APInt::compare(const APInt& RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
   if (isSingleWord())
-    return VAL < RHS.VAL;
+    return VAL < RHS.VAL ? -1 : VAL > RHS.VAL;
 
-  // Get active bit length of both operands
-  unsigned n1 = getActiveBits();
-  unsigned n2 = RHS.getActiveBits();
-
-  // If magnitude of LHS is less than RHS, return true.
-  if (n1 < n2)
-    return true;
-
-  // If magnitude of RHS is greater than LHS, return false.
-  if (n2 < n1)
-    return false;
-
-  // If they both fit in a word, just compare the low order word
-  if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
-    return pVal[0] < RHS.pVal[0];
-
-  // Otherwise, compare all words
-  unsigned topWord = whichWord(std::max(n1,n2)-1);
-  for (int i = topWord; i >= 0; --i) {
-    if (pVal[i] > RHS.pVal[i])
-      return false;
-    if (pVal[i] < RHS.pVal[i])
-      return true;
-  }
-  return false;
+  return tcCompare(pVal, RHS.pVal, getNumWords());
 }
 
-bool APInt::slt(const APInt& RHS) const {
+int APInt::compareSigned(const APInt& RHS) const {
   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
   if (isSingleWord()) {
     int64_t lhsSext = SignExtend64(VAL, BitWidth);
     int64_t rhsSext = SignExtend64(RHS.VAL, BitWidth);
-    return lhsSext < rhsSext;
+    return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
   }
 
   bool lhsNeg = isNegative();
   bool rhsNeg = RHS.isNegative();
 
   // If the sign bits don't match, then (LHS < RHS) if LHS is negative
   if (lhsNeg != rhsNeg)
-    return lhsNeg;
+    return lhsNeg ? -1 : 1;
 
   // Otherwise we can just use an unsigned comparison, because even negative
   // numbers compare correctly this way if both have the same signed-ness.
-  return ult(RHS);
+  return tcCompare(pVal, RHS.pVal, getNumWords());
 }
 
 void APInt::setBit(unsigned bitPosition) {
   if (isSingleWord())
     VAL |= maskBit(bitPosition);
   else
     pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
 }
for (unsigned i = 0; i < parts; i++)
     dst[i] = ~dst[i];
 }
 
 /* Comparison (unsigned) of two bignums.  */
 int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
                      unsigned parts) {
   while (parts) {
     parts--;
-    if (lhs[parts] == rhs[parts])
-      continue;
-
+    if (lhs[parts] != rhs[parts])
       return (lhs[parts] > rhs[parts]) ? 1 : -1;
   }
 
   return 0;
 }
 
 /* Set the least significant BITS bits of a bignum, clear the
    rest.  */
 void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,