[APInt] Move isMask and isShiftedMask out of APIntOps and into the APInt class. Implement them without memory allocation for multiword

[craig.topper]

Summary

This moves the isMask and isShiftedMask functions to be class methods. They now use the MathExtras.h function for single word size and leading/trailing zeros/ones or countPopulation for the multiword size. The previous implementation made multiple temorary memory allocations to do the bitwise arithmetic operations to match the MathExtras.h implementation.

[grandinj]

include/llvm/ADT/APInt.h

429

comment looks wrong ? doesn't mention the numBits argument?

[craig.topper]

Adjust comment to include numBits parameter

[hans]

lgtm with a nit about the comment

include/llvm/ADT/APInt.h

428

drop "argument"

include/llvm/ADT/APInt.h

public:
 
   /// \brief Check if the APInt consists of a repeated bit pattern.
   ///
   /// e.g. 0x01010101 satisfies isSplat(8).
   /// \param SplatSizeInBits The size of the pattern in bits. Must divide bit
   /// width without remainder.
   bool isSplat(unsigned SplatSizeInBits) const;
 
+  /// \returns true if the argument APInt value is a sequence of \param numBits
+  /// ones starting at the least significant bit with the remainder zero.
+  bool isMask(unsigned numBits) const {
+    assert(numBits != 0 && "numBits must be non-zero");
+    assert(numBits <= BitWidth && "numBits out of range");
+    if (isSingleWord())
+      return VAL == (UINT64_MAX >> (APINT_BITS_PER_WORD - numBits));
+    unsigned Ones = countTrailingOnes();
+    return (numBits == Ones) && ((Ones + countLeadingZeros()) == BitWidth);
+  }
+
+  /// \returns true if the argument is a non-empty sequence of ones starting at
+  /// the least significant bit with the remainder zero.
+  /// Ex. isMask(0x0000FFFFU) == true.
+  bool isMask() const {
+    if (isSingleWord())
+      return isMask_64(VAL);
+    unsigned Ones = countTrailingOnes();
+    return (Ones > 0) && ((Ones + countLeadingZeros()) == BitWidth);
+  }
+
+  /// \brief Return true if the argument APInt value contains a sequence of ones
+  /// with the remainder zero.
+  bool isShiftedMask() const {
+    if (isSingleWord())
+      return isShiftedMask_64(VAL);
+    unsigned Ones = countPopulation();
+    return (Ones + countTrailingZeros() + countLeadingZeros()) == BitWidth;
+  }
+
   /// @}
   /// \name Value Generators
   /// @{
 
   /// \brief Gets maximum unsigned value of APInt for specific bit width.
   static APInt getMaxValue(unsigned numBits) {
     return getAllOnesValue(numBits);
   }
inline const APInt &umin(const APInt &A, const APInt &B) {
   return A.ult(B) ? A : B;
 }
 
 /// \brief Determine the larger of two APInts considered to be unsigned.
 inline const APInt &umax(const APInt &A, const APInt &B) {
   return A.ugt(B) ? A : B;
 }
 
-/// \returns true if the argument APInt value is a sequence of ones starting at
-/// the least significant bit with the remainder zero.
-inline bool isMask(unsigned numBits, const APInt &APIVal) {
-  return numBits <= APIVal.getBitWidth() &&
-         APIVal == APInt::getLowBitsSet(APIVal.getBitWidth(), numBits);
-}
-
-/// \returns true if the argument is a non-empty sequence of ones starting at
-/// the least significant bit with the remainder zero (32 bit version).
-/// Ex. isMask(0x0000FFFFU) == true.
-inline bool isMask(const APInt &Value) {
-  return (Value != 0) && ((Value + 1) & Value) == 0;
-}
-
-/// \brief Return true if the argument APInt value contains a sequence of ones
-/// with the remainder zero.
-inline bool isShiftedMask(const APInt &APIVal) {
-  return (APIVal != 0) && isMask((APIVal - 1) | APIVal);
-}
-
 /// \brief Compute GCD of two APInt values.
 ///
 /// This function returns the greatest common divisor of the two APInt values
 /// using Euclid's algorithm.
 ///
 /// \returns the greatest common divisor of Val1 and Val2
 APInt GreatestCommonDivisor(const APInt &Val1, const APInt &Val2);
 

lib/Analysis/ScalarEvolution.cpp

case Instruction::Xor:
                 Type *UTy = BO->LHS->getType();
                 const SCEV *Z0 = Z->getOperand();
                 Type *Z0Ty = Z0->getType();
                 unsigned Z0TySize = getTypeSizeInBits(Z0Ty);
 
                 // If C is a low-bits mask, the zero extend is serving to
                 // mask off the high bits. Complement the operand and
                 // re-apply the zext.
-                if (APIntOps::isMask(Z0TySize, CI->getValue()))
+                if (CI->getValue().isMask(Z0TySize))
                   return getZeroExtendExpr(getNotSCEV(Z0), UTy);
 
                 // If C is a single bit, it may be in the sign-bit position
                 // before the zero-extend. In this case, represent the xor
                 // using an add, which is equivalent, and re-apply the zext.
                 APInt Trunc = CI->getValue().trunc(Z0TySize);
                 if (Trunc.zext(getTypeSizeInBits(UTy)) == CI->getValue() &&
                     Trunc.isSignBit())

lib/CodeGen/CodeGenPrepare.cpp

bool CodeGenPrepare::optimizeLoadExt(LoadInst *Load) {
   // (and (load x) 1) is not matched as a single instruction, rather as a LDR
   // followed by an AND.
   // TODO: Look into removing this restriction by fixing backends to either
   // return false for isLoadExtLegal for i1 or have them select this pattern to
   // a single instruction.
   //
   // Also avoid hoisting if we didn't see any ands with the exact DemandBits
   // mask, since these are the only ands that will be removed by isel.
-  if (ActiveBits <= 1 || !APIntOps::isMask(ActiveBits, DemandBits) ||
+  if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
       WidestAndBits != DemandBits)
     return false;
 
   LLVMContext &Ctx = Load->getType()->getContext();
   Type *TruncTy = Type::getIntNTy(Ctx, ActiveBits);
   EVT TruncVT = TLI->getValueType(*DL, TruncTy);
 
   // Reject cases that won't be matched as extloads.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (ConstantSDNode *CAnd = dyn_cast<ConstantSDNode>(N1)) {
 
         // Bail out, this node will probably disappear anyway.
         if (ShiftBits == 0)
           return SDValue();
 
         unsigned MaskBits = AndMask.countTrailingOnes();
         EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), Size / 2);
 
-        if (APIntOps::isMask(AndMask) &&
+        if (AndMask.isMask() &&
             // Required bits must not span the two halves of the integer and
             // must fit in the half size type.
             (ShiftBits + MaskBits <= Size / 2) &&
             TLI.isNarrowingProfitable(VT, HalfVT) &&
             TLI.isTypeDesirableForOp(ISD::AND, HalfVT) &&
             TLI.isTypeDesirableForOp(ISD::SRL, HalfVT) &&
             TLI.isTruncateFree(VT, HalfVT) &&
             TLI.isZExtFree(HalfVT, VT)) {
SDValue DAGCombiner::visitANDLike(SDValue N0, SDValue N1, SDNode *N) {
   return SDValue();
 }
 
 bool DAGCombiner::isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
                                    EVT LoadResultTy, EVT &ExtVT, EVT &LoadedVT,
                                    bool &NarrowLoad) {
   uint32_t ActiveBits = AndC->getAPIntValue().getActiveBits();
 
-  if (ActiveBits == 0 || !APIntOps::isMask(ActiveBits, AndC->getAPIntValue()))
+  if (ActiveBits == 0 || !AndC->getAPIntValue().isMask(ActiveBits))
     return false;
 
   ExtVT = EVT::getIntegerVT(*DAG.getContext(), ActiveBits);
   LoadedVT = LoadN->getMemoryVT();
 
   if (ExtVT == LoadedVT &&
       (!LegalOperations ||
        TLI.isLoadExtLegal(ISD::ZEXTLOAD, LoadResultTy, ExtVT))) {

lib/Target/Hexagon/HexagonGenExtract.cpp

bool HexagonGenExtract::convert(Instruction *In) {
   // and-ed with. The extract operation will copy these bits, and so the
   // mask cannot any holes in it that would clear any of the bits of the
   // extracted field.
   if (!LogicalSR) {
     // If the shift right was arithmetic, it could have included some 1 bits.
     // It is still ok to generate extract, but only if the mask eliminates
     // those bits (i.e. M does not have any bits set beyond U).
     APInt C = APInt::getHighBitsSet(BW, BW-U);
-    if (M.intersects(C) || !APIntOps::isMask(W, M))
+    if (M.intersects(C) || !M.isMask(W))
       return false;
   } else {
     // Check if M starts with a contiguous sequence of W times 1 bits. Get
     // the low U bits of M (which eliminates the 0 bits shifted in on the
     // left), and check if the result is APInt's "mask":
-    if (!APIntOps::isMask(W, M.getLoBits(U)))
+    if (!M.getLoBits(U).isMask(W))
       return false;
   }
 
   IRBuilder<> IRB(In);
   Intrinsic::ID IntId = (BW == 32) ? Intrinsic::hexagon_S2_extractu
                                    : Intrinsic::hexagon_S2_extractup;
   Module *Mod = BB->getParent()->getParent();
   Value *ExtF = Intrinsic::getDeclaration(Mod, IntId);

lib/Target/X86/X86ISelLowering.cpp

static SDValue combineAndMaskToShift(SDNode *N, SelectionDAG &DAG,
   EVT VT0 = Op0.getValueType();
   EVT VT1 = Op1.getValueType();
 
   if (VT0 != VT1 || !VT0.isSimple() || !VT0.isInteger())
     return SDValue();
 
   APInt SplatVal;
   if (!ISD::isConstantSplatVector(Op1.getNode(), SplatVal) ||
-      !APIntOps::isMask(SplatVal))
+      !SplatVal.isMask())
     return SDValue();
 
   if (!SupportedVectorShiftWithImm(VT0.getSimpleVT(), Subtarget, ISD::SRL))
     return SDValue();
 
   unsigned EltBitWidth = VT0.getScalarSizeInBits();
   if (EltBitWidth != DAG.ComputeNumSignBits(Op0))
     return SDValue();
static SDValue detectUSatPattern(SDValue In, EVT VT) {
   //Saturation with truncation. We truncate from InVT to VT.
   assert(In.getScalarValueSizeInBits() > VT.getScalarSizeInBits() &&
     "Unexpected types for truncate operation");
 
   APInt C;
   if (ISD::isConstantSplatVector(In.getOperand(1).getNode(), C)) {
     // C should be equal to UINT32_MAX / UINT16_MAX / UINT8_MAX according
     // the element size of the destination type.
-    return APIntOps::isMask(VT.getScalarSizeInBits(), C) ? In.getOperand(0) :
+    return C.isMask(VT.getScalarSizeInBits()) ? In.getOperand(0) :
       SDValue();
   }
   return SDValue();
 }
 
 /// Detect a pattern of truncation with saturation:
 /// (truncate (umin (x, unsigned_max_of_dest_type)) to dest_type).
 /// The types should allow to use VPMOVUS* instruction on AVX512.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 
 /// Returns true iff Val consists of one contiguous run of 1s with any number
 /// of 0s on either side.  The 1s are allowed to wrap from LSB to MSB,
 /// so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
 /// not, since all 1s are not contiguous.
 static bool isRunOfOnes(ConstantInt *Val, uint32_t &MB, uint32_t &ME) {
   const APInt& V = Val->getValue();
   uint32_t BitWidth = Val->getType()->getBitWidth();
-  if (!APIntOps::isShiftedMask(V)) return false;
+  if (!V.isShiftedMask()) return false;
 
   // look for the first zero bit after the run of ones
   MB = BitWidth - ((V - 1) ^ V).countLeadingZeros();
   // look for the first non-zero bit
   ME = V.getActiveBits();
   return true;
 }
 

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

case Instruction::Call: {
     case Intrinsic::x86_sse4a_extrq:
     case Intrinsic::x86_sse4a_extrqi:
     case Intrinsic::x86_sse4a_insertq:
     case Intrinsic::x86_sse4a_insertqi:
       UndefElts.setHighBits(VWidth / 2);
       break;
     case Intrinsic::amdgcn_buffer_load:
     case Intrinsic::amdgcn_buffer_load_format: {
-      if (VWidth == 1 || !APIntOps::isMask(DemandedElts))
+      if (VWidth == 1 || !DemandedElts.isMask())
         return nullptr;
 
       // TODO: Handle 3 vectors when supported in code gen.
       unsigned NewNumElts = PowerOf2Ceil(DemandedElts.countTrailingOnes());
       if (NewNumElts == VWidth)
         return nullptr;
 
       Module *M = II->getParent()->getParent()->getParent();

unittests/ADT/APIntTest.cpp

TEST(APIntTest, IsSplat) {
   EXPECT_TRUE(E.isSplat(2));
   EXPECT_TRUE(E.isSplat(4));
   EXPECT_TRUE(E.isSplat(8));
   EXPECT_TRUE(E.isSplat(16));
   EXPECT_TRUE(E.isSplat(32));
 }
 
 TEST(APIntTest, isMask) {
-  EXPECT_FALSE(APIntOps::isMask(APInt(32, 0x01010101)));
-  EXPECT_FALSE(APIntOps::isMask(APInt(32, 0xf0000000)));
-  EXPECT_FALSE(APIntOps::isMask(APInt(32, 0xffff0000)));
-  EXPECT_FALSE(APIntOps::isMask(APInt(32, 0xff << 1)));
+  EXPECT_FALSE(APInt(32, 0x01010101).isMask());
+  EXPECT_FALSE(APInt(32, 0xf0000000).isMask());
+  EXPECT_FALSE(APInt(32, 0xffff0000).isMask());
+  EXPECT_FALSE(APInt(32, 0xff << 1).isMask());
 
   for (int N : { 1, 2, 3, 4, 7, 8, 16, 32, 64, 127, 128, 129, 256 }) {
-    EXPECT_FALSE(APIntOps::isMask(APInt(N, 0)));
+    EXPECT_FALSE(APInt(N, 0).isMask());
 
     APInt One(N, 1);
     for (int I = 1; I <= N; ++I) {
       APInt MaskVal = One.shl(I) - 1;
-      EXPECT_TRUE(APIntOps::isMask(MaskVal));
+      EXPECT_TRUE(MaskVal.isMask());
+      EXPECT_TRUE(MaskVal.isMask(I));
     }
   }
 }
 
 TEST(APIntTest, isShiftedMask) {
-  EXPECT_FALSE(APIntOps::isShiftedMask(APInt(32, 0x01010101)));
-  EXPECT_TRUE(APIntOps::isShiftedMask(APInt(32, 0xf0000000)));
-  EXPECT_TRUE(APIntOps::isShiftedMask(APInt(32, 0xffff0000)));
-  EXPECT_TRUE(APIntOps::isShiftedMask(APInt(32, 0xff << 1)));
+  EXPECT_FALSE(APInt(32, 0x01010101).isShiftedMask());
+  EXPECT_TRUE(APInt(32, 0xf0000000).isShiftedMask());
+  EXPECT_TRUE(APInt(32, 0xffff0000).isShiftedMask());
+  EXPECT_TRUE(APInt(32, 0xff << 1).isShiftedMask());
 
   for (int N : { 1, 2, 3, 4, 7, 8, 16, 32, 64, 127, 128, 129, 256 }) {
-    EXPECT_FALSE(APIntOps::isShiftedMask(APInt(N, 0)));
+    EXPECT_FALSE(APInt(N, 0).isShiftedMask());
 
     APInt One(N, 1);
     for (int I = 1; I < N; ++I) {
       APInt MaskVal = One.shl(I) - 1;
-      EXPECT_TRUE(APIntOps::isShiftedMask(MaskVal));
+      EXPECT_TRUE(MaskVal.isShiftedMask());
     }
     for (int I = 1; I < N - 1; ++I) {
       APInt MaskVal = One.shl(I);
-      EXPECT_TRUE(APIntOps::isShiftedMask(MaskVal));
+      EXPECT_TRUE(MaskVal.isShiftedMask());
     }
     for (int I = 1; I < N; ++I) {
       APInt MaskVal = APInt::getHighBitsSet(N, I);
-      EXPECT_TRUE(APIntOps::isShiftedMask(MaskVal));
+      EXPECT_TRUE(MaskVal.isShiftedMask());
     }
   }
 }
 
 #if defined(__clang__)
 // Disable the pragma warning from versions of Clang without -Wself-move
 #pragma clang diagnostic push
 #pragma clang diagnostic ignored "-Wunknown-pragmas"