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

[RKSimon]

Summary

D108992 added KnownBits handling for 'Quadratic Reciprocity' self-multiplication patterns (bit[1] == 0).

This patch adds selfmultiply handling to value tracking so demanded bits patterns can make use of it.

[lebedev.ri]

Seems fine to me.

[efriedma]

alive2 says the following is invalid:

define i5 @src(i5 %x) {
  %a = mul i5 %x, %x
  %b = and i5 %a, -3
  ret i5 %b
}

define i5 @tgt(i5 %x) {
  %a = mul i5 %x, %x
  ret i5 %a
}

Transformation doesn't verify!

ERROR: Value mismatch

Example:
i5 %x = undef

Source:
i5 %a = any
i5 %b = #x00 (0)	[based on undef value]

Target:
i5 %a = #x02 (2)
Source value: #x00 (0)
Target value: #x02 (2)

[RKSimon]

Updated with check for undef operand

[spatel]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

if (Op0 == Op1) {
       if (!isKnownNonNegative)
         isKnownNegative =
             (isKnownNegativeOp1 && isKnownNonNegativeOp0 &&
              Known2.isNonZero()) ||
             (isKnownNegativeOp0 && isKnownNonNegativeOp1 && Known.isNonZero());
     }
   }
 
-  Known = KnownBits::mul(Known, Known2);
+  bool SelfMultiply = Op0 == Op1;
+  // TODO: SelfMultiply can be poison, but not undef.
+  SelfMultiply &=
+      isGuaranteedNotToBeUndefOrPoison(Op0, Q.AC, Q.CxtI, Q.DT, Depth + 1);
+  Known = KnownBits::mul(Known, Known2, SelfMultiply);
 
   // Only make use of no-wrap flags if we failed to compute the sign bit
   // directly.  This matters if the multiplication always overflows, in
   // which case we prefer to follow the result of the direct computation,
   // though as the program is invoking undefined behaviour we can choose
   // whatever we like here.
   if (isKnownNonNegative && !Known.isNegative())
     Known.makeNonNegative();

llvm/test/Transforms/InstCombine/mul-masked-bits.ll

;
   %2 = and i64 %1, -3
   ret i64 %2
 }
 
 define <4 x i32> @combine_mul_self_demandedbits_vector(<4 x i32> %x) {
 ; CHECK-LABEL: @combine_mul_self_demandedbits_vector(
 ; CHECK-NEXT:    [[TMP1:%.*]] = freeze <4 x i32> [[X:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = mul <4 x i32> [[TMP1]], [[TMP1]]
-; CHECK-NEXT:    [[TMP3:%.*]] = and <4 x i32> [[TMP2]], <i32 -3, i32 -3, i32 -3, i32 -3>
-; CHECK-NEXT:    ret <4 x i32> [[TMP3]]
+; CHECK-NEXT:    ret <4 x i32> [[TMP2]]
 ;
   %1 = freeze <4 x i32> %x
   %2 = mul <4 x i32> %1, %1
   %3 = and <4 x i32> %2, <i32 -3, i32 -3, i32 -3, i32 -3>
   ret <4 x i32> %3
 }
 
 define i8 @one_demanded_bit(i8 %x) {