Re: [PATCH][combine] PR rtl-optimization/68651 Try changing rtx from (r + r) to (r << 1) to aid recognition

[Jeff Law <law@redhat.com>]

On 12/16/2015 10:00 AM, Kyrill Tkachov wrote:
>
> On 16/12/15 12:18, Bernd Schmidt wrote:
>> On 12/15/2015 05:21 PM, Kyrill Tkachov wrote:
>>> Then for the shift pattern in the MD file we'd have to
>>> dynamically select the scheduling type depending on whether or
>>> not the shift amount is 1 and the costs line up?
>>
>> Yes. This isn't unusual, take a look at i386.md where you have a
>> lot of switches on attr type to decide which string to print.
>>
>
> I'm just worried that if we take this idea to its logical conclusion,
> we have to add a new canonicalisation rule: "all (plus x x)
> expressions shall be expressed as (ashift x 1)". Such a rule seems
> too specific to me and all targets would have to special-case it in
> their MD patterns and costs if they ever wanted to treat an add and a
> shift differently. In this particular case we'd have to
> conditionalise the scheduling string selection on a particular CPU
> tuning and the shift amount, which will make the pattern much harder
> to read. To implement this properly we'd also have to
That's not terribly unusual.  And we've done those kind of 
canonicalization rules before -- most recently to deal with issues in 
combine we settled on canonicalization rules for ashift vs mult.  While 
there was fallout, it's manageable.


>
>>> The price we pay when trying these substitutions is an iteration
>>> over the rtx with FOR_EACH_SUBRTX_PTR. recog gets called only if
>>> that iteration actually performed a substitution of x + x into x
>>> << 1. Is that too high a price to pay? (I'm not familiar with the
>>> performance characteristics of the FOR_EACH_SUBRTX machinery)
>>
>> It depends on how many of these transforms we are going to try; it
>>  also feels very hackish, trying to work around the core design of
>> the combiner. IMO it would be better for machine descriptions to
>> work with the pass rather than against it.
>>
>
> Perhaps I'm lacking the historical context, but what is the core
> design of the combiner? Why should the backend have to jump through
> these hoops if it already communicates to the midend (through correct
> rtx costs) that a shift is more expensive than a plus? I'd be more
> inclined to agree that this is perhaps a limitation in recog rather
> than combine, but still not a backend problem.
The historical design of combine is pretty simple.

Use data dependence to substitute the definition of an operand in a use
of the operand. Essentially create bigger blobs of RTL. Canonicalize and
simplify that larger blob of RTL, then try to match it with a pattern in
the backend.

Note that costing didn't enter the picture. The assumption was that if
the combination succeeds, then it's profitable (fewer insns).  We 
haven't generally encouraged trying to match multiple forms of 
equivalent expressions, instead we declare a canonical form and make 
sure combine uses it.


>
>> If you can somehow arrange for the (plus x x) to be turned into a
>> shift while substituting that might be yet another approach to
>> try.
>>
>
> I did investigate where else we could make this transformation. For
> the zero_extend+shift case (the ubfiz instruction from the testcase
> in my original submission) we could fix this by modifying
> make_extraction to convert its argument to a shift from (plus x x)
> as, in that context, shifts are undoubtedly more likely to simplify
> with the various extraction operations that it's trying to perform.
Note that canonicalizing (plus x x) to (ashift x 1) is consistent with 
the canonicalization we do for (mult x C) to (ashift x log2 (C)) where C 
is an exact power of two.

When we made that change consistently (there were cases where we instead 
preferred MULT in the past), we had to fix some backends, but the 
fallout wasn't terrible.

I would think from a representational standpoint canonicalizing (plus x 
x) to (ashift x 1) would be generally a good thing.


jeff