[Bug tree-optimization/96669] Failure to optimize shift by variable+and by 1 to test for 0

[jakub at gcc dot gnu.org via Gcc-bugs]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96669

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Seems we already since 2014 had a rule for this when the result is compared
against 0.

Anyway, here is a generalization of that plus an attempt at handling this
specific case without the comparison:

--- gcc/match.pd.jj     2021-01-15 14:00:21.567135280 +0100
+++ gcc/match.pd        2021-01-15 16:55:30.658692184 +0100
@@ -3117,13 +3117,33 @@ (define_operator_list COND_TERNARY
       (op @0 { build_int_cst (TREE_TYPE (@1), low); })))))))


-/* ((1 << A) & 1) != 0 -> A == 0
-   ((1 << A) & 1) == 0 -> A != 0 */
+/* Simplify (CST << x) & 1 to 0 if CST is even or to x == 0 if it is odd.  /
+(simplify
+ (bit_and (lshift INTEGER_CST@1 @0) integer_onep)
+  (if ((wi::to_wide (@1) & 1) != 0)
+   (eq @0 { build_zero_cst (TREE_TYPE (@0)); })
+   ({ build_zero_cst (type); })))
+
+/* Simplify ((C << x) & D) != 0 where C and D are power of two constants,
+   either to false if D is smaller (unsigned comparison) than C, or to
+   x == log2 (D) - log2 (C).  Similarly for right shifts.  */
 (for cmp (ne eq)
      icmp (eq ne)
  (simplify
-  (cmp (bit_and (lshift integer_onep @0) integer_onep) integer_zerop)
-  (icmp @0 { build_zero_cst (TREE_TYPE (@0)); })))
+  (cmp (bit_and (lshift integer_pow2p@1 @0) integer_pow2p@2) integer_zerop)
+   (with { int c1 = wi::clz (wi::to_wide (@1));
+          int c2 = wi::clz (wi::to_wide (@2)); }
+    (if (c1 < c2)
+     { constant_boolean_node (cmp == NE_EXPR ? false : true, type); }
+     (icmp @0 { build_int_cst (TREE_TYPE (@0), c1 - c2); }))))
+ (simplify
+  (cmp (bit_and (rshift integer_pow2p@1 @0) integer_pow2p@2) integer_zerop)
+   (if (tree_int_cst_sgn (@1) > 0)
+    (with { int c1 = wi::clz (wi::to_wide (@1));
+           int c2 = wi::clz (wi::to_wide (@2)); }
+     (if (c1 > c2)
+      { constant_boolean_node (cmp == NE_EXPR ? false : true, type); }
+      (icmp @0 { build_int_cst (TREE_TYPE (@0), c2 - c1); }))))))

 /* (CST1 << A) == CST2 -> A == ctz (CST2) - ctz (CST1)
    (CST1 << A) != CST2 -> A != ctz (CST2) - ctz (CST1)
Unfortunately, while that extended second simplification seems to work fine,
have been using:
int
f1 (int a)
{
  return (1 << a) & 1;
}

int
f2 (int a)
{
  return (2 << a) & 1;
}

int
f3 (int a)
{
  return ((1 << a) & 1) != 0;
}

int
f4 (int a)
{
  return ((2 << a) & 1) == 0;
}

int
f5 (int a)
{
  return ((2 << a) & 16) != 0;
}

int
f6 (int a)
{
  return ((16 << a) & 32) == 0;
}

int
f7 (int a)
{
  return (1 >> a) & 1;
}

int
f8 (int a)
{
  return (2 >> a) & 1;
}

int
f9 (int a)
{
  return ((1 >> a) & 1) == 0;
}

int
f10 (int a)
{
  return ((2 >> a) & 1) != 0;
}

int
f11 (int a)
{
  return ((1 >> a) & 2) != 0;
}

int
f12 (int a)
{
  return ((32 >> a) & 16) == 0;
}
as testcase, the first simplification doesn't show up in *-match.c at all.  Any
ideas why?