Re: [PATCH V4] Optimize '(X - N * M) / N' to 'X / N - M' if valid

[Jiufu Guo <guojiufu@linux.ibm.com>]

Hi,

Andrew MacLeod <amacleod@redhat.com> writes:

> On 7/17/23 09:45, Jiufu Guo wrote:
>>
>>>> Should we decide we would like it in general, it wouldnt be hard to add to
>>>> irange.  wi_fold() cuurently returns null, it could easily return a bool
>>>> indicating if an overflow happened, and wi_fold_in_parts and fold_range would
>>>> simply OR the results all together of the compoent wi_fold() calls.  It would
>>>> require updating/audfiting  a number of range-op entries and adding an
>>>> overflowed_p()  query to irange.
>>> Ah, yeah - the folding APIs would be a good fit I guess.  I was
>>> also looking to have the "new" helpers to be somewhat consistent
>>> with the ranger API.
>>>
>>> So if we had a fold_range overload with either an output argument
>>> or a flag that makes it return false on possible overflow that
>>> would work I guess?  Since we have a virtual class setup we
>>> might be able to provide a default failing method and implement
>>> workers for plus and mult (as needed for this patch) as the need
>>> arises?
>> Thanks for your comments!
>> Here is a concern.  The patterns in match.pd may be supported by
>> 'vrp' passes. At that time, the range info would be computed (via
>> the value-range machinery) and cached for each SSA_NAME. In the
>> patterns, when range_of_expr is called for a capture, the range
>> info is retrieved from the cache, and no need to fold_range again.
>> This means the overflow info may also need to be cached together
>> with other range info.  There may be additional memory and time
>> cost.
>>
>
> I've been thinking about this a little bit, and how to make the info available in a useful way.
>
> I wonder if maybe we just add another entry point  to range-ops that looks a bit like fold_range ..
>
>   Attached is an (untested) patch which ads overflow_free_p(op1, op2,
> relation)  to rangeops.   It defaults to returning false.  If you want
> to implement it for say plus,  you'd add to operator_plus in
> range-ops.cc  something like
>
> operator_plus::overflow_free_p (irange&op1, irange& op2, relation_kind)
> {
>    // stuff you do in plus_without_overflow
> }
>
> I added relation_kind as  param, but you can ignore it.  maybe it wont
> ever help, but it seems like if we know there is a relation between
> op1 and op2 we might be able to someday determine something else?    
> if not, remove it.
>
> Then all you need to do too access it is to go thru range-op_handler.. so for instance:
>
> range_op_handler (PLUS_EXPR).overflow_free_p (op1, op2)
>
> It'll work for all types an all tree codes. the dispatch machinery
> will return false unless both op1 and op2 are integral ranges, and
> then it will invoke the appropriate handler, defaulting to returning
> FALSE.

Very good suggestions! Thanks so much for your great guide!

>
> I also am not a fan of the get_range  routine.  It would be better to
> generally just call range_of_expr, get the results, then handle
> undefined in the new overflow_free_p() routine and return false. 
> varying should not need anything special since it will trigger the
> overflow when you do the calculation.

The general code in the trunk is just like you said: range_of_expr is
used when querying a range for an expr.
I am also aware that: a range with varying([min, max]) may be ok if the
range is computed from other ranges, especially if there is no overflow.
For example, '[MAX-100, MAX] - [0, 100]' generates a varying range, but
it would be ok for some case.
And a varying range will trigger overflow if it takes part in a
calculation as your said.
So, I agree that varying would not be specially for some patterns.

>
> The auxillary routines could go in vr-values.h/cc.  They seem like
> things that simplify_using_ranges could utilize, and when we get to
> integrating simplify_using_ranges better,  what you are doing may end
> up there anyway

Thanks for your suggestion!  Or maybe we could just use the APIs 
in match.pd directly.

>
> Does that work?

I believe this would work!
I will submit a new version patch!  Thanks again for your comments!

BR,
Jeff (Jiufu Guo)

>
> Andrew