Hi! This patch adds some ctz simplifications (e.g. ctz (x) >= 3 can be done by testing if the low 3 bits are zero, etc.).
In addition, I've noticed that in the CLZ case, the #ifdef CLZ_DEFINED_VALUE_AT_ZERO don't really work as intended, they are evaluated during genmatch and the macro is not defined then (but, because of the missing tm.h includes it isn't defined in gimple-match.c or generic-match.c either). And when tm.h is included, defaults.h is included which defines a fallback version of that macro. For GCC 12, I wonder if it wouldn't be better to say in addition to __builtin_c[lt]z* is always UB at zero that it would be undefined for .C[LT]Z ifn too if it has just one operand and use a second operand to be the constant we expect at zero. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? 2021-01-16 Jakub Jelinek <ja...@redhat.com> PR tree-optimization/95527 * generic-match-head.c: Include tm.h. * gimple-match-head.c: Include tm.h. * match.pd (CLZ == INTEGER_CST): Don't use #ifdef CLZ_DEFINED_VALUE_AT_ZERO, only test CLZ_DEFINED_VALUE_AT_ZERO if clz == CFN_CLZ. Add missing val declaration. (CTZ cmp CST): New simplifications. * gcc.dg/tree-ssa/pr95527-2.c: New test. --- gcc/generic-match-head.c.jj 2021-01-04 10:25:39.146230280 +0100 +++ gcc/generic-match-head.c 2021-01-16 13:12:51.783210820 +0100 @@ -37,6 +37,7 @@ along with GCC; see the file COPYING3. #include "gimplify.h" #include "optabs-tree.h" #include "dbgcnt.h" +#include "tm.h" /* Routine to determine if the types T1 and T2 are effectively the same for GENERIC. If T1 or T2 is not a type, the test --- gcc/gimple-match-head.c.jj 2021-01-04 10:25:39.764223282 +0100 +++ gcc/gimple-match-head.c 2021-01-16 13:13:11.675984551 +0100 @@ -43,6 +43,7 @@ along with GCC; see the file COPYING3. #include "optabs-tree.h" #include "tree-eh.h" #include "dbgcnt.h" +#include "tm.h" /* Forward declarations of the private auto-generated matchers. They expect valueized operands in canonical order and do not --- gcc/match.pd.jj 2021-01-16 09:21:36.586239939 +0100 +++ gcc/match.pd 2021-01-16 14:47:03.265769066 +0100 @@ -6307,30 +6307,97 @@ (define_operator_list COND_TERNARY (op (clz:s @0) INTEGER_CST@1) (if (integer_zerop (@1)) /* clz(X) == 0 is (int)X < 0 and clz(X) != 0 is (int)X >= 0. */ - (with { tree stype = signed_type_for (TREE_TYPE (@0)); + (with { tree type0 = TREE_TYPE (@0); + tree stype = signed_type_for (type0); HOST_WIDE_INT val = 0; -#ifdef CLZ_DEFINED_VALUE_AT_ZERO /* Punt on hypothetical weird targets. */ - if (CLZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (TREE_TYPE (@0)), - val) == 2 + if (clz == CFN_CLZ + && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_TYPE_MODE (type0), + val) == 2 && val == 0) stype = NULL_TREE; -#endif } (if (stype) (cmp (convert:stype @0) { build_zero_cst (stype); }))) /* clz(X) == (prec-1) is X == 1 and clz(X) != (prec-1) is X != 1. */ (with { bool ok = true; -#ifdef CLZ_DEFINED_VALUE_AT_ZERO + HOST_WIDE_INT val = 0; + tree type0 = TREE_TYPE (@0); /* Punt on hypothetical weird targets. */ - if (CLZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (TREE_TYPE (@0)), - val) == 2 - && val == TYPE_PRECISION (TREE_TYPE (@0)) - 1) + if (clz == CFN_CLZ + && CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_TYPE_MODE (type0), + val) == 2 + && val == TYPE_PRECISION (type0) - 1) ok = false; -#endif } - (if (ok && wi::to_wide (@1) == (TYPE_PRECISION (TREE_TYPE (@0)) - 1)) - (op @0 { build_one_cst (TREE_TYPE (@0)); }))))))) + (if (ok && wi::to_wide (@1) == (TYPE_PRECISION (type0) - 1)) + (op @0 { build_one_cst (type0); }))))))) + +/* CTZ simplifications. */ +(for ctz (CTZ) + (for op (ge gt le lt) + cmp (eq eq ne ne) + (simplify + /* __builtin_ctz (x) >= C -> (x & ((1 << C) - 1)) == 0. */ + (op (ctz:s @0) INTEGER_CST@1) + (with { bool ok = true; + HOST_WIDE_INT val = 0; + if (!tree_fits_shwi_p (@1)) + ok = false; + else + { + val = tree_to_shwi (@1); + /* Canonicalize to >= or <. */ + if (op == GT_EXPR || op == LE_EXPR) + { + if (val == HOST_WIDE_INT_MAX) + ok = false; + else + val++; + } + } + bool zero_res = false; + HOST_WIDE_INT zero_val = 0; + tree type0 = TREE_TYPE (@0); + int prec = TYPE_PRECISION (type0); + if (ctz == CFN_CTZ + && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_TYPE_MODE (type0), + zero_val) == 2) + zero_res = true; + } + (if (val <= 0) + (if (ok && (!zero_res || zero_val >= val)) + { constant_boolean_node (cmp == EQ_EXPR ? true : false, type); }) + (if (val >= prec) + (if (ok && (!zero_res || zero_val < val)) + { constant_boolean_node (cmp == EQ_EXPR ? false : true, type); }) + (if (ok && (!zero_res || zero_val < 0 || zero_val >= prec)) + (cmp (bit_and @0 { wide_int_to_tree (type0, + wi::mask (val, false, prec)); }) + { build_zero_cst (type0); }))))))) + (for op (eq ne) + (simplify + /* __builtin_ctz (x) == C -> (x & ((1 << (C + 1)) - 1)) == (1 << C). */ + (op (ctz:s @0) INTEGER_CST@1) + (with { bool zero_res = false; + HOST_WIDE_INT zero_val = 0; + tree type0 = TREE_TYPE (@0); + int prec = TYPE_PRECISION (type0); + if (ctz == CFN_CTZ + && CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_TYPE_MODE (type0), + zero_val) == 2) + zero_res = true; + } + (if (tree_int_cst_sgn (@1) < 0 || wi::to_widest (@1) >= prec) + (if (!zero_res || zero_val != wi::to_widest (@1)) + { constant_boolean_node (op == EQ_EXPR ? false : true, type); }) + (if (!zero_res || zero_val < 0 || zero_val >= prec) + (op (bit_and @0 { wide_int_to_tree (type0, + wi::mask (tree_to_uhwi (@1) + 1, + false, prec)); }) + { wide_int_to_tree (type0, + wi::shifted_mask (tree_to_uhwi (@1), 1, + false, prec)); }))))))) /* POPCOUNT simplifications. */ /* popcount(X) + popcount(Y) is popcount(X|Y) when X&Y must be zero. */ --- gcc/testsuite/gcc.dg/tree-ssa/pr95527-2.c.jj 2021-01-16 14:56:36.206260767 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/pr95527-2.c 2021-01-16 14:56:06.598597091 +0100 @@ -0,0 +1,57 @@ +/* PR tree-optimization/95527 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-original" } */ +/* { dg-final { scan-tree-dump "a & 7\\) == 0" "original" } } */ +/* { dg-final { scan-tree-dump "b & 63\\) != 0" "original" } } */ +/* { dg-final { scan-tree-dump-times "return 0;" 2 "original" } } */ +/* { dg-final { scan-tree-dump-times "return 1;" 2 "original" } } */ +/* { dg-final { scan-tree-dump "g & 15\\) == 8" "original" } } */ +/* { dg-final { scan-tree-dump "h & 255\\) != 128" "original" } } */ + +int +f1 (int a) +{ + return __builtin_ctz (a) >= 3; +} + +int +f2 (int b) +{ + return __builtin_ctz (b) < 6; +} + +int +f3 (int c) +{ + return __builtin_ctz (c) < 0; +} + +int +f4 (int d) +{ + return __builtin_ctz (d) >= 0; +} + +int +f5 (int e) +{ + return __builtin_ctz (e) >= __SIZEOF_INT__ * __CHAR_BIT__; +} + +int +f6 (int f) +{ + return __builtin_ctz (f) < __SIZEOF_INT__ * __CHAR_BIT__; +} + +int +f7 (int g) +{ + return __builtin_ctz (g) == 3; +} + +int +f8 (int h) +{ + return __builtin_ctz (h) != 7; +} Jakub