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.