On Tue, 9 Jun 2020, Jakub Jelinek wrote:
> Hi!
>
> The following patch implements various optimizations of __builtin_ffs*
> against constants.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
Richard.
> 2020-06-08 Jakub Jelinek <ja...@redhat.com>
>
> PR tree-optimization/95527
> * match.pd (__builtin_ffs (X) cmp CST): New optimizations.
>
> * gcc.dg/tree-ssa/pr95527.c: New test.
>
> --- gcc/match.pd.jj 2020-06-04 09:06:35.760019941 +0200
> +++ gcc/match.pd 2020-06-08 18:06:51.310010377 +0200
> @@ -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
> --- gcc/testsuite/gcc.dg/tree-ssa/pr95527.c.jj 2020-06-08
> 18:10:43.380583335 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr95527.c 2020-06-08 18:34:23.380528853
> +0200
> @@ -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;
> +}
>
> Jakub
>
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)
