[APInt] Add isSubsetOf method that can check if one APInt is a subset of another without creating temporary APInts

[craig.topper]

Summary

This question comes up in many places in SimplifyDemandedBits. This makes it easy to ask without allocating additional temporary APInts.

The BitVector class provides a similar functionality through its (IMHO badly named) test(const BitVector&) method. Though its output polarity is reversed.

I've provided one example use case in this patch. I plan to do more as a follow up.

[spatel]

LGTM.

include/llvm/ADT/APInt.h

private:
   unsigned countTrailingOnesSlowCase() const LLVM_READONLY;
 
   /// out-of-line slow case for countPopulation
   unsigned countPopulationSlowCase() const LLVM_READONLY;
 
   /// out-of-line slow case for intersects.
   bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY;
 
+  /// out-of-line slow case for isSubsetOf.
+  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 operator&=.
   void AndAssignSlowCase(const APInt& RHS);
public:
   /// between this APInt and RHS that are both set.
   bool intersects(const APInt &RHS) const {
     assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
     if (isSingleWord())
       return (VAL & RHS.VAL) != 0;
     return intersectsSlowCase(RHS);
   }
 
+  /// This operation checks that all bits set in this APInt are also set in RHS.
+  bool isSubsetOf(const APInt &RHS) const {
+    assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+    if (isSingleWord())
+      return (VAL & ~RHS.VAL) == 0;
+    return isSubsetOfSlowCase(RHS);
+  }
+
   /// @}
   /// \name Resizing Operators
   /// @{
 
   /// \brief Truncate to new width.
   ///
   /// Truncate the APInt to a specified width. It is an error to specify a width
   /// that is greater than or equal to the current width.

lib/Support/APInt.cpp

 bool APInt::intersectsSlowCase(const APInt &RHS) const {
   for (unsigned i = 0, e = getNumWords(); i != e; ++i)
     if ((pVal[i] & RHS.pVal[i]) != 0)
       return true;
 
   return false;
 }
 
+bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
+  for (unsigned i = 0, e = getNumWords(); i != e; ++i)
+    if ((pVal[i] & ~RHS.pVal[i]) != 0)
+      return false;
+
+  return true;
+}
+
 APInt APInt::byteSwap() const {
   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
   if (BitWidth == 16)
     return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
   if (BitWidth == 32)
     return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
   if (BitWidth == 48) {
     unsigned Tmp1 = unsigned(VAL >> 16);

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo,
   // The operand must be a constant integer or splat integer.
   Value *Op = I->getOperand(OpNo);
   const APInt *C;
   if (!match(Op, m_APInt(C)))
     return false;
 
   // If there are no bits set that aren't demanded, nothing to do.
   Demanded = Demanded.zextOrTrunc(C->getBitWidth());
-  if ((~Demanded & *C) == 0)
+  if (C->isSubsetOf(Demanded))
     return false;
 
   // This instruction is producing bits that are not demanded. Shrink the RHS.
   Demanded &= *C;
   I->setOperand(OpNo, ConstantInt::get(Op->getType(), Demanded));
 
   return true;
 }

unittests/ADT/APIntTest.cpp

TEST(APIntTest, LeftShift) {
   EXPECT_EQ(255U, i256.countTrailingZeros());
   EXPECT_EQ(1U, i256.countPopulation());
 
   // Ensure we handle large shifts of multi-word.
   const APInt neg_one(128, static_cast<uint64_t>(-1), true);
   EXPECT_EQ(0, neg_one.shl(257));
 }
 
+TEST(APIntTest, isSubsetOf) {
+  APInt i32_1(32, 1);
+  APInt i32_2(32, 2);
+  APInt i32_3(32, 3);
+  EXPECT_FALSE(i32_3.isSubsetOf(i32_1));
+  EXPECT_TRUE(i32_1.isSubsetOf(i32_3));
+  EXPECT_FALSE(i32_2.isSubsetOf(i32_1));
+  EXPECT_FALSE(i32_1.isSubsetOf(i32_2));
+  EXPECT_TRUE(i32_3.isSubsetOf(i32_3));
+
+  APInt i128_1(128, 1);
+  APInt i128_2(128, 2);
+  APInt i128_3(128, 3);
+  EXPECT_FALSE(i128_3.isSubsetOf(i128_1));
+  EXPECT_TRUE(i128_1.isSubsetOf(i128_3));
+  EXPECT_FALSE(i128_2.isSubsetOf(i128_1));
+  EXPECT_FALSE(i128_1.isSubsetOf(i128_2));
+  EXPECT_TRUE(i128_3.isSubsetOf(i128_3));
+
+  i128_1 <<= 64;
+  i128_2 <<= 64;
+  i128_3 <<= 64;
+  EXPECT_FALSE(i128_3.isSubsetOf(i128_1));
+  EXPECT_TRUE(i128_1.isSubsetOf(i128_3));
+  EXPECT_FALSE(i128_2.isSubsetOf(i128_1));
+  EXPECT_FALSE(i128_1.isSubsetOf(i128_2));
+  EXPECT_TRUE(i128_3.isSubsetOf(i128_3));
+}
+
 } // end anonymous namespace