[PATCH] match.pd: Fix up A % (cast) (pow2cst << B) simplification [PR99079]
Richard Biener
rguenther@suse.de
Mon Feb 15 08:12:02 GMT 2021
On Sat, 13 Feb 2021, Jakub Jelinek wrote:
> Hi!
>
> The (mod @0 (convert?@3 (power_of_two_cand@1 @2))) simplification
> uses tree_nop_conversion_p (type, TREE_TYPE (@3)) condition, but I believe
> it doesn't check what it was meant to check. On convert?@3
> TREE_TYPE (@3) is not the type of what it has been converted from, but
> what it has been converted to, which needs to be (because it is operand
> of normal binary operation) equal or compatible to type of the modulo
> result and first operand - type.
> I could fix that by using && tree_nop_conversion_p (type, TREE_TYPE (@1))
> and be done with it, but actually most of the non-nop conversions are IMHO
> ok and so we would regress those optimizations.
> In particular, if we have say narrowing conversions (foo5 and foo6 in
> the new testcase), I think we are fine, either the shift of the power of two
> constant after narrowing conversion is still that power of two (or negation
> of that) and then it will still work, or the result of narrowing conversion
> is 0 and then we would have UB which we can ignore.
> Similarly, widening conversions where the shift result is unsigned are fine,
> or even widening conversions where the shift result is signed, but we sign
> extend to a signed wider divisor, the problematic case of INT_MIN will
> become x % (long long) INT_MIN and we can still optimize that to
> x & (long long) INT_MAX.
> What doesn't work is the case in the pr99079.c testcase, widening conversion
> of a signed shift result to wider unsigned divisor, where if the shift
> is negative, we end up with x % (unsigned long long) INT_MIN which is
> x % 0xffffffff80000000ULL where the divisor is not a power of two and
> we can't optimize that to x & 0x7fffffffULL.
>
> So, the patch rejects only the single problematic case.
>
> Furthermore, when the shift result is signed, we were introducing UB into
> a program which previously didn't have one (well, left shift into the sign
> bit is UB in some language/version pairs, but it is definitely valid in
> C++20 - wonder if I shouldn't move the gcc.c-torture/execute/pr99079.c
> testcase to g++.dg/torture/pr99079.C and use -std=c++20), by adding that
> subtraction of 1, x % (1 << 31) in C++20 is well defined, but
> x & ((1 << 31) - 1) triggers UB on the subtraction.
> So, the patch performs the subtraction in the unsigned type if it isn't
> wrapping.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
Thanks,
Richard.
> 2021-02-13 Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/99079
> * match.pd (A % (pow2pcst << N) -> A & ((pow2pcst << N) - 1)): Remove
> useless tree_nop_conversion_p (type, TREE_TYPE (@3)) check. Instead
> require both type and TREE_TYPE (@1) to be integral types and either
> type having smaller or equal precision, or TREE_TYPE (@1) being
> unsigned type, or type being signed type. If TREE_TYPE (@1)
> doesn't have wrapping overflow, perform the subtraction of one in
> unsigned type.
>
> * gcc.dg/fold-modpow2-2.c: New test.
> * gcc.c-torture/execute/pr99079.c: New test.
>
> --- gcc/match.pd.jj 2021-01-28 16:11:30.000000000 +0100
> +++ gcc/match.pd 2021-02-12 20:17:26.656857183 +0100
> @@ -619,12 +619,23 @@ (define_operator_list COND_TERNARY
> (shift @0 (bit_and @1 (minus @2 { build_int_cst (TREE_TYPE (@2),
> 1); }))))))
> (simplify
> - (mod @0 (convert?@3 (power_of_two_cand@1 @2)))
> - (if ((TYPE_UNSIGNED (type)
> - || tree_expr_nonnegative_p (@0))
> - && tree_nop_conversion_p (type, TREE_TYPE (@3))
> - && integer_pow2p (@2) && tree_int_cst_sgn (@2) > 0)
> - (bit_and @0 (convert (minus @1 { build_int_cst (TREE_TYPE (@1), 1); }))))))
> + (mod @0 (convert? (power_of_two_cand@1 @2)))
> + (if ((TYPE_UNSIGNED (type) || tree_expr_nonnegative_p (@0))
> + /* Allow any integral conversions of the divisor, except
> + conversion from narrower signed to wider unsigned type
> + where if @1 would be negative power of two, the divisor
> + would not be a power of two. */
> + && INTEGRAL_TYPE_P (type)
> + && INTEGRAL_TYPE_P (TREE_TYPE (@1))
> + && (TYPE_PRECISION (type) <= TYPE_PRECISION (TREE_TYPE (@1))
> + || TYPE_UNSIGNED (TREE_TYPE (@1))
> + || !TYPE_UNSIGNED (type))
> + && integer_pow2p (@2) && tree_int_cst_sgn (@2) > 0)
> + (with { tree utype = TREE_TYPE (@1);
> + if (!TYPE_OVERFLOW_WRAPS (utype))
> + utype = unsigned_type_for (utype); }
> + (bit_and @0 (convert (minus (convert:utype @1)
> + { build_one_cst (utype); })))))))
>
> /* Simplify (unsigned t * 2)/2 -> unsigned t & 0x7FFFFFFF. */
> (simplify
> --- gcc/testsuite/gcc.dg/fold-modpow2-2.c.jj 2021-02-12 19:36:45.833237766 +0100
> +++ gcc/testsuite/gcc.dg/fold-modpow2-2.c 2021-02-12 20:03:20.413315445 +0100
> @@ -0,0 +1,47 @@
> +/* PR tree-optimization/99079 */
> +/* { dg-do compile { target { lp64 || ilp32 } } } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +unsigned int
> +foo1 (unsigned int a, unsigned int b)
> +{
> + return a % (1 << b);
> +}
> +
> +int
> +foo2 (int b)
> +{
> + return 371 % (1U << b);
> +}
> +
> +long long
> +foo3 (int b)
> +{
> + return 371LL % (1U << b);
> +}
> +
> +unsigned long long
> +foo4 (unsigned long long a, int b)
> +{
> + return a % (1U << b);
> +}
> +
> +unsigned
> +foo5 (unsigned a, int b)
> +{
> + return a % (unsigned) (1ULL << b);
> +}
> +
> +int
> +foo6 (int b)
> +{
> + return 371 % (int) (1ULL << b);
> +}
> +
> +long long
> +foo7 (int b)
> +{
> + return 371LL % (1 << b);
> +}
> +
> +/* { dg-final { scan-tree-dump-not " % " "optimized" } } */
> --- gcc/testsuite/gcc.c-torture/execute/pr99079.c.jj 2021-02-12 19:29:25.021196283 +0100
> +++ gcc/testsuite/gcc.c-torture/execute/pr99079.c 2021-02-12 19:16:31.761892858 +0100
> @@ -0,0 +1,18 @@
> +/* PR tree-optimization/99079 */
> +
> +__attribute__((noipa)) unsigned long long
> +foo (int x)
> +{
> + unsigned long long s = 1 << x;
> + return 4897637220ULL % s;
> +}
> +
> +int
> +main ()
> +{
> + if (__SIZEOF_INT__ * __CHAR_BIT__ != 32)
> + return 0;
> + if (foo (31) != 4897637220ULL)
> + __builtin_abort ();
> + return 0;
> +}
>
> Jakub
>
>
--
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)
More information about the Gcc-patches
mailing list