[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;
+  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/Analysis/ScalarEvolution/solve-quadratic-overflow.ll

 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" -S < %s 2>&1 | FileCheck %s
 
 ; The exit value from this loop was originally calculated as 0.
 ; The actual exit condition is 256*256 == 0 (in i16).
 
 ; CHECK: Printing analysis 'Scalar Evolution Analysis' for function 'f0':
 ; CHECK-NEXT: Classifying expressions for: @f0
 ; CHECK-NEXT:   %v1 = phi i16 [ 0, %b0 ], [ %v2, %b1 ]
 ; CHECK-NEXT:   -->  {0,+,-1}<%b1> U: [-255,1) S: [-255,1)            Exits: -255            LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v2 = add i16 %v1, -1
 ; CHECK-NEXT:   -->  {-1,+,-1}<%b1> U: [-256,0) S: [-256,0)           Exits: -256            LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v3 = mul i16 %v2, %v2
 ; CHECK-NEXT:   -->  {1,+,3,+,2}<%b1> U: full-set S: full-set         Exits: 0               LoopDispositions: { %b1: Computable }
 ; CHECK-NEXT:   %v5 = phi i16 [ %v2, %b1 ]
-; CHECK-NEXT:   -->  %v5 U: [-256,0) S: [-256,0)
+; CHECK-NEXT:   -->  %v5 U: [-256,0) S: [-256,0)  -->  -256 U: [-256,-255) S: [-256,-255)
 ; CHECK-NEXT:   %v6 = phi i16 [ %v3, %b1 ]
-; CHECK-NEXT:   -->  %v6 U: full-set S: full-set
+; CHECK-NEXT:   -->  %v6 U: [0,-2) S: [0,-2)  -->  0 U: [0,1) S: [0,1)
 ; CHECK-NEXT:   %v7 = sext i16 %v5 to i32
-; CHECK-NEXT:   -->  (sext i16 %v5 to i32) U: [-256,0) S: [-256,0)
+; CHECK-NEXT:   -->  (sext i16 %v5 to i32) U: [-256,0) S: [-256,0)  -->  -256 U: [-256,-255) S: [-256,-255)
 ; CHECK-NEXT: Determining loop execution counts for: @f0
 ; CHECK-NEXT: Loop %b1: backedge-taken count is 255
 ; CHECK-NEXT: Loop %b1: max backedge-taken count is 255
 ; CHECK-NEXT: Loop %b1: Predicated backedge-taken count is 255
 ; CHECK-NEXT:  Predicates:
 ; CHECK-EMPTY:
 ; CHECK-NEXT: Loop %b1: Trip multiple is 256
 

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

;
   %e = ashr i32 %d, 26
   ret i32 %e
 }
 
 ; PR48683 'Quadratic Reciprocity' - and(mul(x,x),2) -> 0
 
 define i1 @PR48683(i32 %x) {
 ; CHECK-LABEL: @PR48683(
-; CHECK-NEXT:    [[A:%.*]] = mul i32 [[X:%.*]], [[X]]
-; CHECK-NEXT:    [[B:%.*]] = and i32 [[A]], 2
-; CHECK-NEXT:    [[C:%.*]] = icmp ne i32 [[B]], 0
-; CHECK-NEXT:    ret i1 [[C]]
+; CHECK-NEXT:    ret i1 false
 ;
   %a = mul i32 %x, %x
   %b = and i32 %a, 2
   %c = icmp ne i32 %b, 0
   ret i1 %c
 }
 
 define <4 x i1> @PR48683_vec(<4 x i32> %x) {
 ; CHECK-LABEL: @PR48683_vec(
-; CHECK-NEXT:    [[A:%.*]] = mul <4 x i32> [[X:%.*]], [[X]]
-; CHECK-NEXT:    [[B:%.*]] = and <4 x i32> [[A]], <i32 2, i32 2, i32 2, i32 2>
-; CHECK-NEXT:    [[C:%.*]] = icmp ne <4 x i32> [[B]], zeroinitializer
-; CHECK-NEXT:    ret <4 x i1> [[C]]
+; CHECK-NEXT:    ret <4 x i1> zeroinitializer
 ;
   %a = mul <4 x i32> %x, %x
   %b = and <4 x i32> %a, <i32 2, i32 2, i32 2, i32 2>
   %c = icmp ne <4 x i32> %b, zeroinitializer
   ret <4 x i1> %c
 }
 
 define <4 x i1> @PR48683_vec_undef(<4 x i32> %x) {