From ee50c09117a54fe1ff66603ef21ba6afe07b8b53 Mon Sep 17 00:00:00 2001
From: Noah Goldstein <goldstein.w.n@gmail.com>
Date: Sun, 23 Jul 2023 11:26:20 -0500
Subject: [PATCH] [InstCombine] Fix bug in canonicalization of Pow2 Tests
 (From: D152673)

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.

Reviewed By: nikic

Differential Revision: https://reviews.llvm.org/D156058
---
 .../Transforms/InstCombine/InstCombineCompares.cpp |  18 +--
 llvm/test/Transforms/InstCombine/ispow2.ll         | 132 ++++++++++++++++++++-
 2 files changed, 138 insertions(+), 12 deletions(-)

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
index a79cc6b..9b3a661 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
@@ -5040,17 +5040,21 @@ static Instruction *foldICmpPow2Test(ICmpInst &I,
       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)))))
+
+    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;
-    else if (match(Op1, m_OneUse(m_c_Xor(m_Add(m_Specific(Op0), m_AllOnes()),
-                                         m_Specific(Op0)))))
+      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_UGE;
+      CheckIs = Pred == ICmpInst::ICMP_ULE;
+    }
   }
 
   if (A) {
diff --git a/llvm/test/Transforms/InstCombine/ispow2.ll b/llvm/test/Transforms/InstCombine/ispow2.ll
index 4d6e432..a67a3fd 100644
--- a/llvm/test/Transforms/InstCombine/ispow2.ll
+++ b/llvm/test/Transforms/InstCombine/ispow2.ll
@@ -1157,8 +1157,9 @@ define i1 @is_pow2_fail_pr63327(i32 %x) {
 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
@@ -1183,9 +1184,8 @@ define i1 @blsmsk_isnt_p2_or_z(i32 %x) {
 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
@@ -1266,6 +1266,128 @@ define i1 @blsmsk_is_p2_or_z_fail_bad_cmp(i32 %x, i32 %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(
-- 
2.7.4