match.pd: reassociate multiplications with constants

Hi,

This is a followup to https://gcc.gnu.org/ml/gcc-patches/2017-05/msg01545.html

Recently due to a fix for PR 80800 GCC has lost the ability to reassociate
signed multiplications chains to go from 'X * CST1 * Y * CST2'
to 'X * Y * (CST1 * CST2)'.  The fix to that PR prevents extract_muldiv from
introducing '(X * (CST1 * CST2)) * Y', which was wrong because it may cause
intermediate signed overflow (unexpected if Y == 0).

As mentioned in that thread, we can reassociate constants to outermost operands
instead: this is safe because CST1 cannot be 0 or -1, since those are handled
by other match.pd rules.

(in fact it's possible to reassociate negates too, and go from '(-X) * Y * CST'
to '(X * Y) * (-CST)' if (-CST) doesn't overflow (again, we know that CST != 1),
but I'm not sure how valuable that is in practice, so opted not to do that yet)

The following patch reinstates folding by adding a new match.pd rule that moves
constants to outermost operands, where they can be merged by fold_binary
machinery if their product doesn't overflow.  Bootstrapped and regtested on
amd64, OK for trunk?

	* match.pd ((X * CST) * Y): Reassociate to (X * Y) * CST.

On Thu, 13 Jul 2017, Alexander Monakov wrote:

> This is a followup to https://gcc.gnu.org/ml/gcc-patches/2017-05/msg01545.html
>
> Recently due to a fix for PR 80800 GCC has lost the ability to reassociate
> signed multiplications chains to go from 'X * CST1 * Y * CST2'
> to 'X * Y * (CST1 * CST2)'.  The fix to that PR prevents extract_muldiv from
> introducing '(X * (CST1 * CST2)) * Y', which was wrong because it may cause
> intermediate signed overflow (unexpected if Y == 0).
>
> As mentioned in that thread, we can reassociate constants to outermost operands
> instead: this is safe because CST1 cannot be 0 or -1, since those are handled
> by other match.pd rules.
>
> (in fact it's possible to reassociate negates too, and go from '(-X) * Y * CST'
> to '(X * Y) * (-CST)' if (-CST) doesn't overflow (again, we know that CST != 1),
> but I'm not sure how valuable that is in practice, so opted not to do that yet)
>
> The following patch reinstates folding by adding a new match.pd rule that moves
> constants to outermost operands, where they can be merged by fold_binary
> machinery if their product doesn't overflow.  Bootstrapped and regtested on
> amd64, OK for trunk?
>
> 	* match.pd ((X * CST) * Y): Reassociate to (X * Y) * CST.
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 4c64b21..e49f879 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -2139,6 +2139,15 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>  (mult @0 integer_minus_onep)
>  (negate @0))
>
> +/* Reassociate (X * CST) * Y to (X * Y) * CST.  This does not introduce
> +   signed overflow: previous rules handle CST being -1 or 0, and for
> +   the rest we know that if X * Y overflows, so does (X * CST) * Y.  */
> +(if (!TYPE_OVERFLOW_SANITIZED (type) && !TYPE_SATURATING (type))
> + (simplify
> +  (mult:c (mult @0 INTEGER_CST@1) @2)
> +  (if (TREE_CODE (@2) != INTEGER_CST)
> +   (mult (mult @0 @2) @1))))
> +
> /* True if we can easily extract the real and imaginary parts of a complex
>    number.  */
> (match compositional_complex

Thanks. I guess it makes sense as a canonicalization (there are always 
cases where those make it harder to optimize, but hopefully fewer than 
those where they help).

I notice that we do not turn (X*10)*10 into X*100 in GIMPLE. X*big*big 
where abs(big*big)>abs(INT_MIN) can be optimized to 0, the only hard case 
is when the product of the constants is -INT_MIN, which we could turn into 
X<<31 for instance (sadly loses range info), or (-X)*INT_MIN or whatever. 
That would make a nice follow-up, if you are interested.

Relying on inner expressions being folded can be slightly dangerous, 
especially for generic IIRC. It seems easy enough to check that @1 is 
neither 0 nor -1 for safety.

Probably needs :s on the inner multiplication.

Unless the test on TYPE_OVERFLOW_SANITIZED etc is shared with adjacent 
transformations, I'd rather put it inside, with the other if, but that's a 
matter of taste.

One small testcase please? Or is there already one that is currently 
failing?

(I cannot ok patches, only comment)

On Thu, 13 Jul 2017, Marc Glisse wrote:
> I notice that we do not turn (X*10)*10 into X*100 in GIMPLE.

Sorry, could you clarify what you mean here?  I think we certainly do that,
just not via match.pd, but in 'associate:' case of fold_binary_loc.

> Relying on inner expressions being folded can be slightly dangerous,
> especially for generic IIRC. It seems easy enough to check that @1 is neither
> 0 nor -1 for safety.

I wanted to add a gcc_checking_assert to that effect, but it's not used in
match.pd anywhere.  Is there a nice way to do that?

Thanks!
Alexander

On Thu, 13 Jul 2017, Alexander Monakov wrote:

> On Thu, 13 Jul 2017, Marc Glisse wrote:
>> I notice that we do not turn (X*10)*10 into X*100 in GIMPLE.
>
> Sorry, could you clarify what you mean here?  I think we certainly do that,
> just not via match.pd, but in 'associate:' case of fold_binary_loc.

fold_binary_loc is for GENERIC, so mostly for front-end time optimization 
of expressions.

int f(int a){
   int b=a*10;
   return b*10;
}

$ gcc-snapshot -O3 -S -fdump-tree-optimized a.c
$ cat a.c.228t.optimized
[...]
   b_2 = a_1(D) * 10;
   _3 = b_2 * 10;
   return _3;

>> Relying on inner expressions being folded can be slightly dangerous,
>> especially for generic IIRC. It seems easy enough to check that @1 is neither
>> 0 nor -1 for safety.
>
> I wanted to add a gcc_checking_assert to that effect, but it's not used in
> match.pd anywhere.  Is there a nice way to do that?

You can use (with { arbitrary C++ code } ... ) to add an assertion (you 
can use @0 in the block of C++ code).

I was more thinking of an "if" than an assertion though.

On Fri, Jul 14, 2017 at 7:59 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Thu, 13 Jul 2017, Alexander Monakov wrote:
>
>> On Thu, 13 Jul 2017, Marc Glisse wrote:
>>>
>>> I notice that we do not turn (X*10)*10 into X*100 in GIMPLE.
>>
>>
>> Sorry, could you clarify what you mean here?  I think we certainly do
>> that,
>> just not via match.pd, but in 'associate:' case of fold_binary_loc.
>
>
> fold_binary_loc is for GENERIC, so mostly for front-end time optimization of
> expressions.
>
> int f(int a){
>   int b=a*10;
>   return b*10;
> }
>
> $ gcc-snapshot -O3 -S -fdump-tree-optimized a.c
> $ cat a.c.228t.optimized
> [...]
>   b_2 = a_1(D) * 10;
>   _3 = b_2 * 10;
>   return _3;

Yeah, but I think we best address this by adding support to re-associate
expressions with !TYPE_OVERFLOW_WRAPS to the reassoc pass.
It's not going to be an easy task if you want to avoid re-writing everything
to unsigned arithmetic.

Simple cases might be worth doing with patterns (like the case above).

Richard.

>>> Relying on inner expressions being folded can be slightly dangerous,
>>> especially for generic IIRC. It seems easy enough to check that @1 is
>>> neither
>>> 0 nor -1 for safety.
>>
>>
>> I wanted to add a gcc_checking_assert to that effect, but it's not used in
>> match.pd anywhere.  Is there a nice way to do that?
>
>
> You can use (with { arbitrary C++ code } ... ) to add an assertion (you can
> use @0 in the block of C++ code).
>
> I was more thinking of an "if" than an assertion though.
>
> --
> Marc Glisse