Re: [PATCH] Optimize certain end of loop conditions into min/max operation

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Jul 27, 2015 at 6:20 PM, Jeff Law <law@redhat.com> wrote:
> On 07/27/2015 03:25 AM, Richard Biener wrote:
>>
>> On Mon, Jul 27, 2015 at 5:41 AM, Michael Collison
>> <michael.collison@linaro.org> wrote:
>>>
>>> This patch is designed to optimize end of loop conditions involving of
>>> the
>>> form
>>>   i < x && i < y into i < min (x, y). Loop condition involving '>' are
>>> handled similarly using max(x,y).
>>> As an example:
>>>
>>> #define N 1024
>>>
>>> int  a[N], b[N], c[N];
>>>
>>> void add (unsignedint  m, unsignedint  n)
>>> {
>>>    unsignedint  i, bound = (m < n) ? m : n;
>>>    for  (i = 0; i < m && i < n; ++i)
>>>      a[i] = b[i] + c[i];
>>> }
>>>
>>>
>>> Performed bootstrap and make check on: x86_64_unknown-linux-gnu,
>>> arm-linux-gnueabihf, and aarch64-linux-gnu.
>>> Okay for trunk?
>>
>>
>> So this works only for && that has been lowered to non-CFG form
>> (I suppose phiopt would catch that?  If not, ifcombine would be the
>> place to implement it I guess).
>
> phiopt is supposed to be generating MIN/MAX expressions for us.  If it isn't
> it'd be good to see any testcases where it isn't.
>
> I think that raises a general question though.  Does it make more sense to
> capture MIN/MAX (and others) in phiopt or in the match.pd framework?

match.pd is good for pattern recognition - patterns of fixed size.  There are
cases that are done in fold-const.c for example that doesn't fit very well
and should be done as separate pass, like for example figuring out whether
an expression can be easily negated or whether there are sign-changes that
can be stripped.  Basically all cases where fold currently recurses (unbound).

The above case is a corner case I think - the number of && you can change
into (multiple) MIN/MAX is unbound but we might only care about the case
where there will be one MIN/MAX operation.

Generally phiopt and other patterns that match the CFG are not yet well
supported by match.pd (though I outlined how matching PHI nodes when
facing (simplify (cond ...) ...) would be possible).

So while putting something into match.pd is easy I'd like people to
think if doing the same thing elsewhere is better - that is, if this is really
a pattern transform operation or if you are just implementing a special-case
of a general transform as a pattern.

Richard.

> Jeff
>