[InstCombine] Fix bug in canonicalization of Pow2 Tests (From: D152673)

[goldstein.w.n]

Summary

D152673 Incorrectly didn't account for operand position in the icmp,
i.e it treated icmp uge x, y the same as icmp uge y, x which is
incorrect:
https://reviews.llvm.org/rG142f7448e770f25b774b058a7eab1f107c4daad9

The fix takes operand position into account. The new tests
exhaustively cover all operand positions for ule, uge, ult,
ugt (the set of predicates) and all transform verify with the new
commit.

[goldstein.w.n]

I kept this out of the commit message because its a bit too verbose, but heres the alive2 output for all the transforms:

----------------------------------------
define i1 @blsmsk_is_p2_or_z_ule_xy(i8 %xx, i8 %yy) {
%0:
  %x = or i8 %xx, %yy
  %xm1 = add i8 %x, 255
  %y = xor i8 %x, %xm1
  %r = icmp ule i8 %x, %y
  ret i1 %r
}
=>
define i1 @blsmsk_is_p2_or_z_ule_xy(i8 %xx, i8 %yy) nofree willreturn memory(none) {
%0:
  %x = or i8 %yy, %xx
  %1 = ctpop i8 %x
  %1_range = !range i8 %1, i8 0, i8 9
  %r = icmp ult i8 %1_range, 2
  ret i1 %r
}
Transformation seems to be correct!

----------------------------------------
define i1 @blsmsk_is_p2_or_z_ule_yx_fail(i8 %xx, i8 %yy) {
%0:
  %x = or i8 %xx, %yy
  %xm1 = add i8 %x, 255
  %y = xor i8 %x, %xm1
  %r = icmp ule i8 %y, %x
  ret i1 %r
}
=>
define i1 @blsmsk_is_p2_or_z_ule_yx_fail(i8 %xx, i8 %yy) nofree willreturn memory(none) {
%0:
  %x = or i8 %yy, %xx
  %xm1 = add i8 %x, 255
  %y = xor i8 %xm1, %x
  %r = icmp ule i8 %y, %x
  ret i1 %r
}
Transformation seems to be correct!

----------------------------------------
define i1 @blsmsk_is_p2_or_z_uge_yx(i8 %xx, i8 %yy) {
%0:
  %x = or i8 %xx, %yy
  %xm1 = add i8 %x, 255
  %y = xor i8 %x, %xm1
  %r = icmp uge i8 %y, %x
  ret i1 %r
}
=>
define i1 @blsmsk_is_p2_or_z_uge_yx(i8 %xx, i8 %yy) nofree willreturn memory(none) {
%0:
  %x = or i8 %yy, %xx
  %1 = ctpop i8 %x
  %1_range = !range i8 %1, i8 0, i8 9
  %r = icmp ult i8 %1_range, 2
  ret i1 %r
}
Transformation seems to be correct!

----------------------------------------
define i1 @blsmsk_is_p2_or_z_uge_xy_fail(i8 %xx, i8 %yy) {
%0:
  %x = or i8 %xx, %yy
  %xm1 = add i8 %x, 255
  %y = xor i8 %x, %xm1
  %r = icmp uge i8 %x, %y
  ret i1 %r
}
=>
define i1 @blsmsk_is_p2_or_z_uge_xy_fail(i8 %xx, i8 %yy) nofree willreturn memory(none) {
%0:
  %x = or i8 %yy, %xx
  %xm1 = add i8 %x, 255
  %y = xor i8 %xm1, %x
  %r = icmp uge i8 %x, %y
  ret i1 %r
}
Transformation seems to be correct!

----------------------------------------
define i1 @blsmsk_isnt_p2_or_z_ugt_xy(i8 %xx, i8 %yy) {
%0:
  %x = or i8 %xx, %yy
  %xm1 = add i8 %x, 255
  %y = xor i8 %x, %xm1
  %r = icmp ugt i8 %x, %y
  ret i1 %r
}
=>
define i1 @blsmsk_isnt_p2_or_z_ugt_xy(i8 %xx, i8 %yy) nofree willreturn memory(none) {
%0:
  %x = or i8 %yy, %xx
  %1 = ctpop i8 %x
  %1_range = !range i8 %1, i8 0, i8 9
  %r = icmp ugt i8 %1_range, 1
  ret i1 %r
}
Transformation seems to be correct!

----------------------------------------
define i1 @blsmsk_isnt_p2_or_z_ugt_yx_fail(i8 %xx, i8 %yy) {
%0:
  %x = or i8 %xx, %yy
  %xm1 = add i8 %x, 255
  %y = xor i8 %x, %xm1
  %r = icmp ugt i8 %y, %x
  ret i1 %r
}
=>
define i1 @blsmsk_isnt_p2_or_z_ugt_yx_fail(i8 %xx, i8 %yy) nofree willreturn memory(none) {
%0:
  %x = or i8 %yy, %xx
  %xm1 = add i8 %x, 255
  %y = xor i8 %xm1, %x
  %r = icmp ugt i8 %y, %x
  ret i1 %r
}
Transformation seems to be correct!

----------------------------------------
define i1 @blsmsk_isnt_p2_or_z_ult_yx(i8 %xx, i8 %yy) {
%0:
  %x = or i8 %xx, %yy
  %xm1 = add i8 %x, 255
  %y = xor i8 %x, %xm1
  %r = icmp ult i8 %y, %x
  ret i1 %r
}
=>
define i1 @blsmsk_isnt_p2_or_z_ult_yx(i8 %xx, i8 %yy) nofree willreturn memory(none) {
%0:
  %x = or i8 %yy, %xx
  %1 = ctpop i8 %x
  %1_range = !range i8 %1, i8 0, i8 9
  %r = icmp ugt i8 %1_range, 1
  ret i1 %r
}
Transformation seems to be correct!

----------------------------------------
define i1 @blsmsk_isnt_p2_or_z_ult_xy_fail(i8 %xx, i8 %yy) {
%0:
  %x = or i8 %xx, %yy
  %xm1 = add i8 %x, 255
  %y = xor i8 %x, %xm1
  %r = icmp ult i8 %x, %y
  ret i1 %r
}
=>
define i1 @blsmsk_isnt_p2_or_z_ult_xy_fail(i8 %xx, i8 %yy) nofree willreturn memory(none) {
%0:
  %x = or i8 %yy, %xx
  %xm1 = add i8 %x, 255
  %y = xor i8 %xm1, %x
  %r = icmp ult i8 %x, %y
  ret i1 %r
}
Transformation seems to be correct!

Summary:
  8 correct transformations
  0 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors

[goldstein.w.n]

Also for the other two test changes:

----------------------------------------
define i1 @blsmsk_is_p2_or_z_fail(i32 %xx, i32 %yy) {
%0:
  %x = or i32 %xx, %yy
  %xm1 = add i32 %x, 4294967295
  %y = xor i32 %x, %xm1
  %r = icmp ugt i32 %x, %y
  ret i1 %r
}
=>
define i1 @blsmsk_is_p2_or_z_fail(i32 %xx, i32 %yy) nofree willreturn memory(none) {
%0:
  %x = or i32 %yy, %xx
  %1 = ctpop i32 %x
  %1_range = !range i32 %1, i32 0, i32 33
  %r = icmp ugt i32 %1_range, 1
  ret i1 %r
}
Transformation seems to be correct!


----------------------------------------
define i1 @blsmsk_is_p2_or_z(i32 %xx, i32 %yy) {
%0:
  %x = or i32 %xx, %yy
  %xm1 = add i32 %x, 4294967295
  %y = xor i32 %x, %xm1
  %r = icmp uge i32 %x, %y
  ret i1 %r
}
=>
define i1 @blsmsk_is_p2_or_z(i32 %xx, i32 %yy) nofree willreturn memory(none) {
%0:
  %x = or i32 %yy, %xx
  %xm1 = add i32 %x, 4294967295
  %y = xor i32 %xm1, %x
  %r = icmp uge i32 %x, %y
  ret i1 %r
}
Transformation seems to be correct!

Summary:
  2 correct transformations
  0 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors

[nikic]

LG

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

if (I.isEquality()) {
     // (-A & A) != A --> ctpop(A) > 1 (four commuted variants)
     if (match(Op0, m_OneUse(m_c_And(m_Neg(m_Specific(Op1)), m_Specific(Op1)))))
       A = Op1;
     else if (match(Op1,
                    m_OneUse(m_c_And(m_Neg(m_Specific(Op0)), m_Specific(Op0)))))
       A = Op0;
 
     CheckIs = Pred == ICmpInst::ICMP_EQ;
-  } else if (Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_ULT) {
+  } else if (ICmpInst::isUnsigned(Pred)) {
     // (A ^ (A-1)) u>= A --> ctpop(A) < 2 (two commuted variants)
     // ((A-1) ^ A) u< A --> ctpop(A) > 1 (two commuted variants)
-    if (match(Op0, m_OneUse(m_c_Xor(m_Add(m_Specific(Op1), m_AllOnes()),
-                                    m_Specific(Op1)))))
-      A = Op1;
-    else if (match(Op1, m_OneUse(m_c_Xor(m_Add(m_Specific(Op0), m_AllOnes()),
-                                         m_Specific(Op0)))))
-      A = Op0;
 
+    if ((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_ULT) &&
+        match(Op0, m_OneUse(m_c_Xor(m_Add(m_Specific(Op1), m_AllOnes()),
+                                    m_Specific(Op1))))) {
+      A = Op1;
       CheckIs = Pred == ICmpInst::ICMP_UGE;
+    } else if ((Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_ULE) &&
+               match(Op1, m_OneUse(m_c_Xor(m_Add(m_Specific(Op0), m_AllOnes()),
+                                           m_Specific(Op0))))) {
+      A = Op0;
+      CheckIs = Pred == ICmpInst::ICMP_ULE;
+    }
   }
 
   if (A) {
     Type *Ty = A->getType();
     CallInst *CtPop = Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, A);
     return CheckIs ? new ICmpInst(ICmpInst::ICMP_ULT, CtPop,
                                   ConstantInt::get(Ty, 2))
                    : new ICmpInst(ICmpInst::ICMP_UGT, CtPop,

llvm/test/Transforms/InstCombine/ispow2.ll

;
   %x_and_nx = and i32 %x, %nx
   %r = icmp sge i32 %x_and_nx, %x
   ret i1 %r
 }
 
 define i1 @blsmsk_is_p2_or_z(i32 %xx, i32 %yy) {
 ; CHECK-LABEL: @blsmsk_is_p2_or_z(
 ; CHECK-NEXT:    [[X:%.*]] = or i32 [[XX:%.*]], [[YY:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range [[RNG0]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ult i32 [[TMP1]], 2
+; CHECK-NEXT:    [[XM1:%.*]] = add i32 [[X]], -1
+; CHECK-NEXT:    [[Y:%.*]] = xor i32 [[X]], [[XM1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp uge i32 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = or i32 %xx, %yy
   %xm1 = add i32 %x, -1
   %y = xor i32 %x, %xm1
   %r = icmp uge i32 %x, %y
   ret i1 %r
 }
 
 define i1 @blsmsk_isnt_p2_or_z(i32 %x) {
 ; CHECK-LABEL: @blsmsk_isnt_p2_or_z(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X:%.*]]), !range [[RNG0]]
 ; CHECK-NEXT:    [[R:%.*]] = icmp ugt i32 [[TMP1]], 1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xm1 = add i32 %x, -1
   %y = xor i32 %x, %xm1
   %r = icmp ult i32 %y, %x
   ret i1 %r
 }
 
 define i1 @blsmsk_is_p2_or_z_fail(i32 %xx, i32 %yy) {
 ; CHECK-LABEL: @blsmsk_is_p2_or_z_fail(
 ; CHECK-NEXT:    [[X:%.*]] = or i32 [[XX:%.*]], [[YY:%.*]]
-; CHECK-NEXT:    [[XM1:%.*]] = add i32 [[X]], -1
-; CHECK-NEXT:    [[Y:%.*]] = xor i32 [[X]], [[XM1]]
-; CHECK-NEXT:    [[R:%.*]] = icmp ugt i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.ctpop.i32(i32 [[X]]), !range [[RNG0]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i32 [[TMP1]], 1
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = or i32 %xx, %yy
   %xm1 = add i32 %x, -1
   %y = xor i32 %x, %xm1
   %r = icmp ugt i32 %x, %y
   ret i1 %r
 }

 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %xm1 = add i32 %x, -1
   %y = xor i32 %x, %xm1
   %r = icmp uge i32 %y, %z
   ret i1 %r
 }
 
+define i1 @blsmsk_is_p2_or_z_ule_xy(i8 %xx, i8 %yy) {
+; CHECK-LABEL: @blsmsk_is_p2_or_z_ule_xy(
+; CHECK-NEXT:    [[X:%.*]] = or i8 [[XX:%.*]], [[YY:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.ctpop.i8(i8 [[X]]), !range [[RNG1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[TMP1]], 2
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %x = or i8 %xx, %yy
+  %xm1 = add i8 %x, -1
+  %y = xor i8 %x, %xm1
+  %r = icmp ule i8 %x, %y
+  ret i1 %r
+}
+
+
+define i1 @blsmsk_is_p2_or_z_ule_yx_fail(i8 %xx, i8 %yy) {
+; CHECK-LABEL: @blsmsk_is_p2_or_z_ule_yx_fail(
+; CHECK-NEXT:    [[X:%.*]] = or i8 [[XX:%.*]], [[YY:%.*]]
+; CHECK-NEXT:    [[XM1:%.*]] = add i8 [[X]], -1
+; CHECK-NEXT:    [[Y:%.*]] = xor i8 [[X]], [[XM1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ule i8 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %x = or i8 %xx, %yy
+  %xm1 = add i8 %x, -1
+  %y = xor i8 %x, %xm1
+  %r = icmp ule i8 %y, %x
+  ret i1 %r
+}
+
+
+define i1 @blsmsk_is_p2_or_z_uge_yx(i8 %xx, i8 %yy) {
+; CHECK-LABEL: @blsmsk_is_p2_or_z_uge_yx(
+; CHECK-NEXT:    [[X:%.*]] = or i8 [[XX:%.*]], [[YY:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.ctpop.i8(i8 [[X]]), !range [[RNG1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[TMP1]], 2
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %x = or i8 %xx, %yy
+  %xm1 = add i8 %x, -1
+  %y = xor i8 %x, %xm1
+  %r = icmp uge i8 %y, %x
+  ret i1 %r
+}
+
+
+define i1 @blsmsk_is_p2_or_z_uge_xy_fail(i8 %xx, i8 %yy) {
+; CHECK-LABEL: @blsmsk_is_p2_or_z_uge_xy_fail(
+; CHECK-NEXT:    [[X:%.*]] = or i8 [[XX:%.*]], [[YY:%.*]]
+; CHECK-NEXT:    [[XM1:%.*]] = add i8 [[X]], -1
+; CHECK-NEXT:    [[Y:%.*]] = xor i8 [[X]], [[XM1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp uge i8 [[X]], [[Y]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %x = or i8 %xx, %yy
+  %xm1 = add i8 %x, -1
+  %y = xor i8 %x, %xm1
+  %r = icmp uge i8 %x, %y
+  ret i1 %r
+}
+
+define i1 @blsmsk_isnt_p2_or_z_ugt_xy(i8 %xx, i8 %yy) {
+; CHECK-LABEL: @blsmsk_isnt_p2_or_z_ugt_xy(
+; CHECK-NEXT:    [[X:%.*]] = or i8 [[XX:%.*]], [[YY:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.ctpop.i8(i8 [[X]]), !range [[RNG1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[TMP1]], 1
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %x = or i8 %xx, %yy
+  %xm1 = add i8 %x, -1
+  %y = xor i8 %x, %xm1
+  %r = icmp ugt i8 %x, %y
+  ret i1 %r
+}
+
+
+define i1 @blsmsk_isnt_p2_or_z_ugt_yx_fail(i8 %xx, i8 %yy) {
+; CHECK-LABEL: @blsmsk_isnt_p2_or_z_ugt_yx_fail(
+; CHECK-NEXT:    [[X:%.*]] = or i8 [[XX:%.*]], [[YY:%.*]]
+; CHECK-NEXT:    [[XM1:%.*]] = add i8 [[X]], -1
+; CHECK-NEXT:    [[Y:%.*]] = xor i8 [[X]], [[XM1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[Y]], [[X]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %x = or i8 %xx, %yy
+  %xm1 = add i8 %x, -1
+  %y = xor i8 %x, %xm1
+  %r = icmp ugt i8 %y, %x
+  ret i1 %r
+}
+
+
+define i1 @blsmsk_isnt_p2_or_z_ult_yx(i8 %xx, i8 %yy) {
+; CHECK-LABEL: @blsmsk_isnt_p2_or_z_ult_yx(
+; CHECK-NEXT:    [[X:%.*]] = or i8 [[XX:%.*]], [[YY:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.ctpop.i8(i8 [[X]]), !range [[RNG1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ugt i8 [[TMP1]], 1
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %x = or i8 %xx, %yy
+  %xm1 = add i8 %x, -1
+  %y = xor i8 %x, %xm1
+  %r = icmp ult i8 %y, %x
+  ret i1 %r
+}
+
+
+define i1 @blsmsk_isnt_p2_or_z_ult_xy_fail(i8 %xx, i8 %yy) {
+; CHECK-LABEL: @blsmsk_isnt_p2_or_z_ult_xy_fail(
+; CHECK-NEXT:    [[X:%.*]] = or i8 [[XX:%.*]], [[YY:%.*]]
+; CHECK-NEXT:    [[XM1:%.*]] = add i8 [[X]], -1
+; CHECK-NEXT:    [[Y:%.*]] = xor i8 [[X]], [[XM1]]
+; CHECK-NEXT:    [[R:%.*]] = icmp ult i8 [[X]], [[Y]]
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %x = or i8 %xx, %yy
+  %xm1 = add i8 %x, -1
+  %y = xor i8 %x, %xm1
+  %r = icmp ult i8 %x, %y
+  ret i1 %r
+}
+
 declare <2 x i32> @llvm.ctpop.2xi32(<2 x i32>)
 define i1 @is_pow2_nz_known_bits(i32 %xin) {
 ; CHECK-LABEL: @is_pow2_nz_known_bits(
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[XIN:%.*]], -65
 ; CHECK-NEXT:    [[R:%.*]] = icmp eq i32 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %x = or i32 %xin, 64