From 653ab081391e9e7e38b304f3234323c93693d40c Mon Sep 17 00:00:00 2001 From: Jakub Jelinek Date: Tue, 9 Jun 2020 08:38:19 +0200 Subject: [PATCH] match.pd: Optimize ffs comparisons against constants [PR95527] The following patch implements various optimizations of __builtin_ffs* against constants. 2020-06-09 Jakub Jelinek PR tree-optimization/95527 * match.pd (__builtin_ffs (X) cmp CST): New optimizations. * gcc.dg/tree-ssa/pr95527.c: New test. --- gcc/match.pd | 48 +++++++ gcc/testsuite/gcc.dg/tree-ssa/pr95527.c | 172 ++++++++++++++++++++++++ 2 files changed, 220 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr95527.c diff --git a/gcc/match.pd b/gcc/match.pd index 2b8c37e690e..53ced346bbd 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -6024,6 +6024,54 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (plus (CTZ:type @0) { build_one_cst (type); }))) #endif +(for ffs (BUILT_IN_FFS BUILT_IN_FFSL BUILT_IN_FFSLL + BUILT_IN_FFSIMAX) + /* __builtin_ffs (X) == 0 -> X == 0. + __builtin_ffs (X) == 6 -> (X & 63) == 32. */ + (for cmp (eq ne) + (simplify + (cmp (ffs@2 @0) INTEGER_CST@1) + (with { int prec = TYPE_PRECISION (TREE_TYPE (@0)); } + (switch + (if (integer_zerop (@1)) + (cmp @0 { build_zero_cst (TREE_TYPE (@0)); })) + (if (tree_int_cst_sgn (@1) < 0 || wi::to_widest (@1) > prec) + { constant_boolean_node (cmp == NE_EXPR ? true : false, type); }) + (if (single_use (@2)) + (cmp (bit_and @0 { wide_int_to_tree (TREE_TYPE (@0), + wi::mask (tree_to_uhwi (@1), + false, prec)); }) + { wide_int_to_tree (TREE_TYPE (@0), + wi::shifted_mask (tree_to_uhwi (@1) - 1, 1, + false, prec)); })))))) + + /* __builtin_ffs (X) > 6 -> X != 0 && (X & 63) == 0. */ + (for cmp (gt le) + cmp2 (ne eq) + cmp3 (eq ne) + bit_op (bit_and bit_ior) + (simplify + (cmp (ffs@2 @0) INTEGER_CST@1) + (with { int prec = TYPE_PRECISION (TREE_TYPE (@0)); } + (switch + (if (integer_zerop (@1)) + (cmp2 @0 { build_zero_cst (TREE_TYPE (@0)); })) + (if (tree_int_cst_sgn (@1) < 0) + { constant_boolean_node (cmp == GT_EXPR ? true : false, type); }) + (if (wi::to_widest (@1) >= prec) + { constant_boolean_node (cmp == GT_EXPR ? false : true, type); }) + (if (wi::to_widest (@1) == prec - 1) + (cmp3 @0 { wide_int_to_tree (TREE_TYPE (@0), + wi::shifted_mask (prec - 1, 1, + false, prec)); })) + (if (single_use (@2)) + (bit_op (cmp2 @0 { build_zero_cst (TREE_TYPE (@0)); }) + (cmp3 (bit_and @0 + { wide_int_to_tree (TREE_TYPE (@0), + wi::mask (tree_to_uhwi (@1), + false, prec)); }) + { build_zero_cst (TREE_TYPE (@0)); })))))))) + /* Simplify: a = a1 op a2 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr95527.c b/gcc/testsuite/gcc.dg/tree-ssa/pr95527.c new file mode 100644 index 00000000000..afd763cb245 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr95527.c @@ -0,0 +1,172 @@ +/* PR tree-optimization/95527 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-times "return 0;" 4 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "return 18;" 4 "optimized" } } */ + +/* { dg-final { scan-tree-dump-times "a_\[0-9]*\\\(D\\\) == 0" 1 "optimized" } } */ + +int +f1 (int a) +{ + return __builtin_ffs (a) == 0; +} + +/* { dg-final { scan-tree-dump-times "b_\[0-9]*\\\(D\\\) != 0" 1 "optimized" } } */ + +int +f2 (int b) +{ + return __builtin_ffs (b) != 0; +} + +int +f3 (int x) +{ + return __builtin_ffs (x) == -1; +} + +int +f4 (int x) +{ + return 17 + (__builtin_ffs (x) != -1); +} + +int +f5 (int x) +{ + return __builtin_ffs (x) == __SIZEOF_INT__ * __CHAR_BIT__ + 1; +} + +int +f6 (int x) +{ + return 17 + (__builtin_ffs (x) != __SIZEOF_INT__ * __CHAR_BIT__ + 1); +} + +/* { dg-final { scan-tree-dump-times "c_\[0-9]*\\\(D\\\) & 63" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "== 32" 1 "optimized" } } */ + +int +f7 (int c) +{ + return __builtin_ffs (c) == 6; +} + +/* { dg-final { scan-tree-dump-times "d_\[0-9]*\\\(D\\\) & 16383" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "!= 8192" 1 "optimized" } } */ + +int +f8 (int d) +{ + return __builtin_ffs (d) != 14; +} + +/* { dg-final { scan-tree-dump-times "e_\[0-9]*\\\(D\\\) == -9223372036854775808" 1 "optimized" { target lp64 } } } */ +/* { dg-final { scan-tree-dump-times "e_\[0-9]*\\\(D\\\) == -2147483648" 1 "optimized" { target ilp32 } } } */ + +int +f9 (long int e) +{ + return __builtin_ffsl (e) == __SIZEOF_LONG__ * __CHAR_BIT__; +} + +/* { dg-final { scan-tree-dump-times "f_\[0-9]*\\\(D\\\) != -9223372036854775808" 1 "optimized" } } */ + +int +f10 (long long int f) +{ + return __builtin_ffsll (f) != __SIZEOF_LONG_LONG__ * __CHAR_BIT__; +} + +/* { dg-final { scan-tree-dump-times "g_\[0-9]*\\\(D\\\) != 0" 1 "optimized" } } */ + +int +f11 (long long int g) +{ + return __builtin_ffsll (g) > 0; +} + +/* { dg-final { scan-tree-dump-times "h_\[0-9]*\\\(D\\\) == 0" 1 "optimized" } } */ + +int +f12 (int h) +{ + return __builtin_ffs (h) <= 0; +} + +int +f13 (int x) +{ + return 17 + (__builtin_ffs (x) > -1); +} + +int +f14 (int x) +{ + return __builtin_ffs (x) <= -1; +} + +int +f15 (int x) +{ + return __builtin_ffs (x) > __SIZEOF_INT__ * __CHAR_BIT__; +} + +int +f16 (int x) +{ + return 17 + (__builtin_ffs (x) <= __SIZEOF_INT__ * __CHAR_BIT__); +} + +/* { dg-final { scan-tree-dump-times "i_\[0-9]*\\\(D\\\) & 63" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "i_\[0-9]*\\\(D\\\) != 0" 1 "optimized" } } */ + +int +f17 (int i) +{ + return __builtin_ffs (i) > 6; +} + +/* { dg-final { scan-tree-dump-times "j_\[0-9]*\\\(D\\\) & 4095" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "j_\[0-9]*\\\(D\\\) == 0" 1 "optimized" } } */ + +int +f18 (int j) +{ + return __builtin_ffs (j) <= 12; +} + +/* { dg-final { scan-tree-dump-times "k_\[0-9]*\\\(D\\\) == -2147483648" 1 "optimized" { target int32 } } } */ + +int +f19 (int k) +{ + return __builtin_ffs (k) > __SIZEOF_INT__ * __CHAR_BIT__ - 1; +} + +/* { dg-final { scan-tree-dump-times "l_\[0-9]*\\\(D\\\) != -2147483648" 1 "optimized" { target int32 } } } */ + +int +f20 (int l) +{ + return __builtin_ffs (l) <= __SIZEOF_INT__ * __CHAR_BIT__ - 1; +} + +/* { dg-final { scan-tree-dump-times "m_\[0-9]*\\\(D\\\) & 1073741823" 1 "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump-times "m_\[0-9]*\\\(D\\\) != 0" 1 "optimized" } } */ + +int +f21 (int m) +{ + return __builtin_ffs (m) > __SIZEOF_INT__ * __CHAR_BIT__ - 2; +} + +/* { dg-final { scan-tree-dump-times "n_\[0-9]*\\\(D\\\) & 1073741823" 1 "optimized" { target int32 } } } */ +/* { dg-final { scan-tree-dump-times "n_\[0-9]*\\\(D\\\) == 0" 1 "optimized" } } */ + +int +f22 (int n) +{ + return __builtin_ffs (n) <= __SIZEOF_INT__ * __CHAR_BIT__ - 2; +} -- 2.30.2