Re: [PATCH] Simplify (B * v + C) * D -> BD* v + CD when B, C, D are all INTEGER_CST.

[Andrew MacLeod <amacleod@redhat.com>]

On 6/15/22 04:24, Richard Biener wrote:
>
>> diff --git a/gcc/match.pd b/gcc/match.pd
>> index 44a385b912d..54f53a1f988 100644
>> --- a/gcc/match.pd
>> +++ b/gcc/match.pd
>> @@ -489,6 +489,88 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>>     (if (!overflow || TYPE_OVERFLOW_WRAPS (type))
>>      (mult @0 { wide_int_to_tree (type, mul); }))))
>>
>> +/* Similar to above, but there could be an extra add/sub between
>> +   successive multuiplications.  */
>> +(simplify
>> + (mult (plus:s (mult:s@4 @0 INTEGER_CST@1) INTEGER_CST@2) INTEGER_CST@3)
>> + (with {
>> +   bool overflowed = true;
>> +   wi::overflow_type ovf1, ovf2;
>> +   wide_int mul = wi::mul (wi::to_wide (@1), wi::to_wide (@3),
>> +                          TYPE_SIGN (type), &ovf1);
>> +   wide_int add = wi::mul (wi::to_wide (@2), wi::to_wide (@3),
>> +                          TYPE_SIGN (type), &ovf2);
>> +  if (TYPE_OVERFLOW_UNDEFINED (type))
>> +    {
>> +#if GIMPLE
>> +      value_range vr0;
>> +      if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE
>> +         && get_global_range_query ()->range_of_expr (vr0, @4)
>> +         && vr0.kind () == VR_RANGE)
>> +       {
>> +         wide_int wmin0 = vr0.lower_bound ();
>> +         wide_int wmax0 = vr0.upper_bound ();
>> +         wmin0 = wi::mul (wmin0, wi::to_wide (@3), TYPE_SIGN (type), &ovf1);
>> +         wmax0 = wi::mul (wmax0, wi::to_wide (@3), TYPE_SIGN (type), &ovf2);
>> +         if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE)
>> +           {
>> +             wi::add (wmin0, add, TYPE_SIGN (type), &ovf1);
>> +             wi::add (wmax0, add, TYPE_SIGN (type), &ovf2);
>> +             if (ovf1 == wi::OVF_NONE && ovf2 == wi::OVF_NONE)
>> +               overflowed = false;
> I wonder if we have an API available for these kind of queries already?
> Possibly value_range expr_range (MULT_EXPR, vr0, vr1, &ovf),
> computing the result range of the operation on ranges vr0 and vr1
> indicating overflow behavior in 'ovf' (similar as to the wide_int APIs)?
>
> Andrew?
>
> I see match.pd already has similar code in a few places.

The overflow characteristic is currently "hidden" in the API. ie, you 
can do

   range_op_handler (MULT_EXPR, type).fold_range (r, type, vr0, vr1);

and get the result in 'r', which typcically if it overflows for MULT is 
varying I think.  (we give up easily :-)  BUt the fact than an overflow 
may have happened is not explicitly provided.

If this was something generally useful, we could consider adding an 
optional flag to the API which indicates is an overflow may happen.  
Then you'd have something like:
   range_op_handler (MULT_EXPR, type).fold_range (r, type, vr0, vr1, &ovf);

The original range-ops implementation way back when did carry an 
overflow around, but it was removed early on.  Someone would have to go 
in and tweak all the fold_range routines to set the flag correctly, if 
it was passed in. If its going to work for one it would have to work for 
all.

I do believe the information is all contained in every relevant range-op 
routine, we just don't propagate it back to the caller. Most of the 
"generic" routines have a wi_op_overflows () method which determines 
whether any pair of wide-ints overflow the operation, we'd just have to 
return the  flag in those cases.  The rest of the cases would have to be 
audited.

And in todays multi-type environment, we'd have to handle it for the 
other types as well.. so an integer specific value like wi::OVF_*  may 
not be appropriate.   Perhaps just a boolean flag indicating if the 
result is an accurate calculation, or integrates possibly out of range 
values.

Andrew

PS.  We could also simplify the API slightly for general consumption via 
the gimple-range-fold.h routines. they currently support just gimple 
statements:
      bool fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2);
but we could probably also manage something like:
     bool fold_range (vrange &r, MULT_EXPR, vrange &r1, vrange &r2);
where we key off the types of r1 and r2 when possible... and return 
false otherwise.   Then if we have extended the range-ops API to include 
an overflow, we could attach it here too.

Andrew