[KnownBits] Add support for X*X self-multiplication

[RKSimon]

Summary

Add KnownBits handling and unit tests for X*X self-multiplication cases which guarantee that bit1 of their results will be zero - see PR48683.

https://alive2.llvm.org/ce/z/NN_eaR

The next step will be to add suitable test coverage so this can be enabled in ValueTracking/DAG/GlobalISel - currently only a single Analysis/ScalarEvolution test is affected.

[nikic]

Isn't "self add" just a left shift by one? I don't think it makes sense to use computeForAddSub() for that.

[nikic]

Though InstCombine already canonicalizes add x, x to shl x, 1, so it probably doesn't make sense to explicitly handle that case at all.

[RKSimon]

Clean up the selfadd cases to just perform a shl-by-one.

InstCombine does canonicalize X+X to X<<1, but we have cases in DAG where this is reversed - such as the cases being addressed in PR50468/D108139 etc.

[foad]

llvm/lib/Support/KnownBits.cpp

61

I'm not a huge fan of making this part of the existing computeForAddSub function, since it's a completely separate code path. How about a new computeForSelfAdd instead?

[RKSimon]

llvm/lib/Support/KnownBits.cpp

61

I'm going to drop the X+X case for now - and handle it as part of PR50468

[RKSimon]

remove X+X handling - we'll address this later on

[foad]

Looks OK to me.

[RKSimon]

OK, I'll add isGuaranteedNotToBeUndefOrPoison handling

[craig.topper]

In D108992#3264899, @RKSimon wrote:

OK, I'll add isGuaranteedNotToBeUndefOrPoison handling

Is the "The product of a number with itself is non-negative." case in ValueTracking.cpp's computeKnownBitsMul also broken for the same reason?

[RKSimon]

In D108992#3264920, @craig.topper wrote:

In D108992#3264899, @RKSimon wrote:

OK, I'll add isGuaranteedNotToBeUndefOrPoison handling

Is the "The product of a number with itself is non-negative." case in ValueTracking.cpp's computeKnownBitsMul also broken for the same reason?

Looks OK, Alive2:

----------------------------------------
define i8 @src(i8 %x) {
  %m = mul nsw i8 %x, %x
  %s = lshr i8 %m, 7
  ret i8 %s
}
=>
define i8 @tgt(i8 %x) {
  ret i8 0
}
Transformation seems to be correct!

llvm/include/llvm/Support/KnownBits.h

public:
   static KnownBits computeForAddCarry(
       const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
 
   /// Compute known bits resulting from adding LHS and RHS.
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
                                     KnownBits RHS);
 
   /// Compute known bits resulting from multiplying LHS and RHS.
-  static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS);
+  static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS,
+                       bool SelfMultiply = false);
 
   /// Compute known bits from sign-extended multiply-hi.
   static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
 
   /// Compute known bits from zero-extended multiply-hi.
   static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
 
   /// Compute known bits for udiv(LHS, RHS).

llvm/lib/Support/KnownBits.cpp

KnownBits KnownBits::computeForAddCarry(
   return ::computeForAddCarry(
       LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue());
 }
 
 KnownBits KnownBits::computeForAddSub(bool Add, bool NSW,
                                       const KnownBits &LHS, KnownBits RHS) {
   KnownBits KnownOut;
   if (Add) {
     // Sum = LHS + RHS + 0
     KnownOut = ::computeForAddCarry(
         LHS, RHS, /*CarryZero*/true, /*CarryOne*/false);
   } else {
     // Sum = LHS + ~RHS + 1
     std::swap(RHS.Zero, RHS.One);
     KnownOut = ::computeForAddCarry(
         LHS, RHS, /*CarryZero*/false, /*CarryOne*/true);
   }
KnownBits KnownBits::abs(bool IntMinIsPoison) const {
   if (IntMinIsPoison || (!One.isNullValue() && !One.isMinSignedValue()))
     KnownAbs.Zero.setSignBit();
 
   // FIXME: Handle known negative input?
   // FIXME: Calculate the negated Known bits and combine them?
   return KnownAbs;
 }
 
-KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS) {
+KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS,
+                         bool SelfMultiply) {
   unsigned BitWidth = LHS.getBitWidth();
   assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
          !RHS.hasConflict() && "Operand mismatch");
+  assert((!SelfMultiply || (LHS.One == RHS.One && LHS.Zero == RHS.Zero)) &&
+         "Self multiplication knownbits mismatch");
 
   // Compute a conservative estimate for high known-0 bits.
   unsigned LeadZ =
       std::max(LHS.countMinLeadingZeros() + RHS.countMinLeadingZeros(),
                BitWidth) -
       BitWidth;
   LeadZ = std::min(LeadZ, BitWidth);
 
KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS,
 
   APInt BottomKnown =
       Bottom0.getLoBits(TrailBitsKnown0) * Bottom1.getLoBits(TrailBitsKnown1);
 
   KnownBits Res(BitWidth);
   Res.Zero.setHighBits(LeadZ);
   Res.Zero |= (~BottomKnown).getLoBits(ResultBitsKnown);
   Res.One = BottomKnown.getLoBits(ResultBitsKnown);
+
+  // If we're self-multiplying then bit[1] is guaranteed to be zero.
+  if (SelfMultiply && BitWidth > 1) {
+    assert(Res.One[1] == 0 &&
+           "Self-multiplication failed Quadratic Reciprocity!");
+    Res.Zero.setBit(1);
+  }
+
   return Res;
 }
 
 KnownBits KnownBits::mulhs(const KnownBits &LHS, const KnownBits &RHS) {
   unsigned BitWidth = LHS.getBitWidth();
   assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
          !RHS.hasConflict() && "Operand mismatch");
   KnownBits WideLHS = LHS.sext(2 * BitWidth);

llvm/unittests/Support/KnownBitsTest.cpp

ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
       EXPECT_TRUE(ComputedLShr.Zero.isSubsetOf(KnownLShr.Zero));
       EXPECT_TRUE(ComputedLShr.One.isSubsetOf(KnownLShr.One));
 
       KnownBits ComputedAShr = KnownBits::ashr(Known1, Known2);
       EXPECT_TRUE(ComputedAShr.Zero.isSubsetOf(KnownAShr.Zero));
       EXPECT_TRUE(ComputedAShr.One.isSubsetOf(KnownAShr.One));
     });
   });
+
+  // Also test 'unary' binary cases where the same argument is repeated.
+  ForeachKnownBits(Bits, [&](const KnownBits &Known) {
+    KnownBits KnownMul(Bits);
+    KnownMul.Zero.setAllBits();
+    KnownMul.One.setAllBits();
+
+    ForeachNumInKnownBits(Known, [&](const APInt &N) {
+      APInt Res = N * N;
+      KnownMul.One &= Res;
+      KnownMul.Zero &= ~Res;
+    });
+
+    KnownBits ComputedMul = KnownBits::mul(Known, Known, /*SelfMultiply*/ true);
+    EXPECT_TRUE(ComputedMul.Zero.isSubsetOf(KnownMul.Zero));
+    EXPECT_TRUE(ComputedMul.One.isSubsetOf(KnownMul.One));
+  });
 }
 
 TEST(KnownBitsTest, UnaryExhaustive) {
   unsigned Bits = 4;
   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
     KnownBits KnownAbs(Bits);
     KnownAbs.Zero.setAllBits();
     KnownAbs.One.setAllBits();