[Support] Add KnownBits::concat method

[RKSimon]

Summary

Add a method for the various cases where we need to concatenate 2 KnownBits together (BUILD_PAIR and SHIFT_PARTS in particular) - uses the existing APInt::concat 'HiBits.concat(LoBits)' convention

[foad]

Seems reasonable. The API is a bit different from APInt::concat, but I never particularly liked that API anyway :)

llvm/include/llvm/Support/KnownBits.h

316

Maybe just return { Hi.Zero.concat(Lo.Zero), Hi.One.concat(Lo.One) }?

[RKSimon]

llvm/include/llvm/Support/KnownBits.h

316

Hmm - I'd forgotten about APInt::concat - I guess we should try to make a similar KnownBits::concat ? We do tend to make them match where possible

[foad]

llvm/include/llvm/Support/KnownBits.h

316

I guess we should try to make a similar KnownBits::concat ?

Dunno. @lattner gave reasons for the API of the member function APInt::concat in D109620. I'm not sure if those reasons also apply to a non-member version - i.e. should it take (hi, lo) instead of (lo, hi)? Personally I prefer the (lo, hi) order.

[lattner]

Yeah, I strongly think we should keep these consistent. At the same time, I don't care which design wins, feel free to pick which approach makes most sense to you.

[RKSimon]

Refactor to match APInt::concat

llvm/include/llvm/Support/KnownBits.h

public:
   }
 
   /// Return a subset of the known bits from [bitPosition,bitPosition+numBits).
   KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
     return KnownBits(Zero.extractBits(NumBits, BitPosition),
                      One.extractBits(NumBits, BitPosition));
   }
 
+  /// Concatenate the bits from \p Lo onto the bottom of *this.  This is
+  /// equivalent to:
+  ///   (this->zext(NewWidth) << Lo.getBitWidth()) | Lo.zext(NewWidth)
+  KnownBits concat(const KnownBits &Lo) const {
+    return KnownBits(Zero.concat(Lo.Zero), One.concat(Lo.One));
+  }
+
   /// Return KnownBits based on this, but updated given that the underlying
   /// value is known to be greater than or equal to Val.
   KnownBits makeGE(const APInt &Val) const;
 
   /// Returns the minimum number of trailing zero bits.
   unsigned countMinTrailingZeros() const {
     return Zero.countTrailingOnes();
   }
public:
 
   /// Create known bits from a known constant.
   static KnownBits makeConstant(const APInt &C) {
     return KnownBits(~C, C);
   }
 
   /// Compute known bits common to LHS and RHS.
   static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) {
     return KnownBits(LHS.Zero & RHS.Zero, LHS.One & RHS.One);
   }
 
   /// Return true if LHS and RHS have no common bits set.
   static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) {
     return (LHS.Zero | RHS.Zero).isAllOnes();
   }
 
   /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

case ISD::FSHR:
     }
     break;
   case ISD::SHL_PARTS:
   case ISD::SRA_PARTS:
   case ISD::SRL_PARTS: {
     assert((Op.getResNo() == 0 || Op.getResNo() == 1) && "Unknown result");
 
     // Collect lo/hi source values and concatenate.
-    // TODO: Would a KnownBits::concatBits helper be useful?
     unsigned LoBits = Op.getOperand(0).getScalarValueSizeInBits();
     unsigned HiBits = Op.getOperand(1).getScalarValueSizeInBits();
     Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
     Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
-    Known = Known.anyext(LoBits + HiBits);
-    Known.insertBits(Known2, LoBits);
+    Known = Known2.concat(Known);
 
     // Collect shift amount.
     Known2 = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
 
     if (Opcode == ISD::SHL_PARTS)
       Known = KnownBits::shl(Known, Known2);
     else if (Opcode == ISD::SRA_PARTS)
       Known = KnownBits::ashr(Known, Known2);

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

case ISD::BUILD_PAIR: {
     KnownBits KnownLo, KnownHi;
 
     if (SimplifyDemandedBits(Op.getOperand(0), MaskLo, KnownLo, TLO, Depth + 1))
       return true;
 
     if (SimplifyDemandedBits(Op.getOperand(1), MaskHi, KnownHi, TLO, Depth + 1))
       return true;
 
-    Known.Zero = KnownLo.Zero.zext(BitWidth) |
-                 KnownHi.Zero.zext(BitWidth).shl(HalfBitWidth);
-
-    Known.One = KnownLo.One.zext(BitWidth) |
-                KnownHi.One.zext(BitWidth).shl(HalfBitWidth);
+    Known = KnownHi.concat(KnownLo);
     break;
   }
   case ISD::ZERO_EXTEND:
   case ISD::ZERO_EXTEND_VECTOR_INREG: {
     SDValue Src = Op.getOperand(0);
     EVT SrcVT = Src.getValueType();
     unsigned InBits = SrcVT.getScalarSizeInBits();
     unsigned InElts = SrcVT.isVector() ? SrcVT.getVectorNumElements() : 1;

llvm/unittests/Support/KnownBitsTest.cpp

ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
         });
       });
       EXPECT_EQ(!HasCommonBitsSet,
                 KnownBits::haveNoCommonBitsSet(Known1, Known2));
     });
   });
 }
 
+TEST(KnownBitsTest, ConcatBits) {
+  unsigned Bits = 4;
+  for (unsigned LoBits = 1; LoBits < Bits; ++LoBits) {
+    unsigned HiBits = Bits - LoBits;
+    ForeachKnownBits(LoBits, [&](const KnownBits &KnownLo) {
+      ForeachKnownBits(HiBits, [&](const KnownBits &KnownHi) {
+        KnownBits KnownAll = KnownHi.concat(KnownLo);
+
+        EXPECT_EQ(KnownLo.countMinPopulation() + KnownHi.countMinPopulation(),
+                  KnownAll.countMinPopulation());
+        EXPECT_EQ(KnownLo.countMaxPopulation() + KnownHi.countMaxPopulation(),
+                  KnownAll.countMaxPopulation());
+
+        KnownBits ExtractLo = KnownAll.extractBits(LoBits, 0);
+        KnownBits ExtractHi = KnownAll.extractBits(HiBits, LoBits);
+
+        EXPECT_EQ(KnownLo.One.getZExtValue(), ExtractLo.One.getZExtValue());
+        EXPECT_EQ(KnownHi.One.getZExtValue(), ExtractHi.One.getZExtValue());
+        EXPECT_EQ(KnownLo.Zero.getZExtValue(), ExtractLo.Zero.getZExtValue());
+        EXPECT_EQ(KnownHi.Zero.getZExtValue(), ExtractHi.Zero.getZExtValue());
+      });
+    });
+  }
+}
+
 } // end anonymous namespace