llvm dev - Oct 2020 - GlobalISel round table follow-up: multi-stage legalization

Hi all,

first of all thanks to Matt for hosting the round table yesterday and to 
everyone else for their time and the valuable discussions. As promised 
in the chat yesterday, here is the email regarding the legalizer / 
artifact combiner issue we talked about. I will send a separate email 
regarding the regbankselect discussion.

In case someone on the list didn't attend the round table yesterday, 
here is quick summary:

One problem that some of us are seeing in the legalizer is that 
sometimes instructions get expanded before they get folded away in the 
combiner. IIRC Matt sees this happening with division, while I am seeing 
something similar with unmerge.

To my particular problem: due to the nature of the architecture I'm 
working with, we have pretty strict legalization rules. One example is 
that we only allow unmerges from 64 to 32 bit. Unmerges of 32-bit or 
less get lowered to bit-arithmetic. However if we would do the same for 
anything bigger than 64-bit, the legalization of the resulting bit 
arithmetic would introduce illegal unmerges again, which then cause an 
endless loop in the legalizer.

So our rules are carefully designed to create exactly the unmerges we 
can handle and let everything else get handled by the artifact combiner.

The artifact combiner usually cannot get rid of the illegal unmerges on 
the first go and must do some intermediary combines first. Some of those 
try to create other illegal unmerges but ask the legalizer whether those 
are supported. If we only provide rules which work on the unmerges that 
we can handle, then this query would return false and the combine would 
not work. But we also cannot create a rule for those unmerges without 
causing endless loops through legalization.

The way we get around this problem is to add a custom rule, in which we 
simply return false (i.e. UnableToLegalize). This is enough for the 
combiner to produce the intermediary unmerge (because it is now support 
through the custom rule), while also getting around the problem of 
expanding something we don't want in the legalizer (because we say we 
didn't legalize anything). This is obviously a hack.

One of the ideas that was floated around yesterday sounded quite 
interesting to me: multi-stage legalization where you could specify 
which of your rules apply at which stage. I'm pretty sure this would 
solve our problem. In our case we would declare all artifacts as legal 
in the first stage to not hinder the combiner and in the second stage we 
could then focus on actually legalizing any left-over artifacts we have.

I do however see the problem that this could clutter up the existing 
legalization info. Due to the amount of instructions and rules, it 
already is quite complex and if rules could apply to different stages in 
the same file, it could make it quite difficult to understand what 
exactly is happening now.

I think Aditya pointed out that multi-stage legalization might be 
already possible by just having two legalizer passes with different 
legalization info and I feel like this might be the better approach of 
the two. I guess this would still require some tweeks as currently in 
llc we can only say `-stop-before/after=legalizer` but not which one of 
those.

Another thing I was thinking of when I implemented this hack for our 
use-case was that we need some kind of rule which tells the combiner 
that something is supported but is actually not doing any legalization 
in the legalizer (something like a `.combine()`, `.combineFor({s96})`).

Cheers,

Dominik

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 6822 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201007/a0f38a43/attachment.bin>

> On 7 Oct 2020, at 05:07, Dominik Montada <dominik.montada at
hightec-rt.com> wrote:
> 
> Hi all,
> 
> first of all thanks to Matt for hosting the round table yesterday and to
everyone else for their time and the valuable discussions. As promised in the
chat yesterday, here is the email regarding the legalizer / artifact combiner
issue we talked about. I will send a separate email regarding the regbankselect
discussion.
> 
> In case someone on the list didn't attend the round table yesterday,
here is quick summary:
> 
> One problem that some of us are seeing in the legalizer is that sometimes
instructions get expanded before they get folded away in the combiner. IIRC Matt
sees this happening with division, while I am seeing something similar with
unmerge.
IIRC there were two main manifestations of it. For one it ends up at the same
MIR but takes a slower-than-necessary route to get there. For the other it ends
up with worse code which potentially can't be folded post-legalization.
> To my particular problem: due to the nature of the architecture I'm
working with, we have pretty strict legalization rules. One example is that we
only allow unmerges from 64 to 32 bit. Unmerges of 32-bit or less get lowered to
bit-arithmetic. However if we would do the same for anything bigger than 64-bit,
the legalization of the resulting bit arithmetic would introduce illegal
unmerges again, which then cause an endless loop in the legalizer.
Are there particular >s64 cases that are the problem or is it all of them?
I'd expect s128, s256, etc. to G_UNMERGE fairly simply but non-powers-of-2
are more likely to be tricky
> So our rules are carefully designed to create exactly the unmerges we can
handle and let everything else get handled by the artifact combiner.
> 
> The artifact combiner usually cannot get rid of the illegal unmerges on the
first go and must do some intermediary combines first. Some of those try to
create other illegal unmerges but ask the legalizer whether those are supported.
If we only provide rules which work on the unmerges that we can handle, then
this query would return false and the combine would not work. But we also cannot
create a rule for those unmerges without causing endless loops through
legalization.
> 
> The way we get around this problem is to add a custom rule, in which we
simply return false (i.e. UnableToLegalize). This is enough for the combiner to
produce the intermediary unmerge (because it is now support through the custom
rule), while also getting around the problem of expanding something we don't
want in the legalizer (because we say we didn't legalize anything). This is
obviously a hack.
> 
> One of the ideas that was floated around yesterday sounded quite
interesting to me: multi-stage legalization where you could specify which of
your rules apply at which stage. I'm pretty sure this would solve our
problem. In our case we would declare all artifacts as legal in the first stage
to not hinder the combiner and in the second stage we could then focus on
actually legalizing any left-over artifacts we have.
> 
> I do however see the problem that this could clutter up the existing
legalization info. Due to the amount of instructions and rules, it already is
quite complex and if rules could apply to different stages in the same file, it
could make it quite difficult to understand what exactly is happening now.
It would definitely add some clutter but I suspect it would be manageable.
Essentially it would be a common ruleset for most operations and each pass would
add its own version of the merge/unmerge rules.
> I think Aditya pointed out that multi-stage legalization might be already
possible by just having two legalizer passes with different legalization info
and I feel like this might be the better approach of the two. I guess this would
still require some tweeks as currently in llc we can only say
`-stop-before/after=legalizer` but not which one of those.
That's right. Each legalizer pass owns it's own ruleset so two passes is
a possibility. The -stop-before/after bit has been solved for some other passes
but it does need a bit of boilerplate. Each subclass needs it's own pass id
and INITIALIZE_* macros and getPassName() needs to be overridable.
> Another thing I was thinking of when I implemented this hack for our
use-case was that we need some kind of rule which tells the combiner that
something is supported but is actually not doing any legalization in the
legalizer (something like a `.combine()`, `.combineFor({s96})`).
I'm not quite sure what you mean here. Are you thinking of legalization
rules for combining or something like legalization rules but for the combiner?
Are you thinking of artifact combines in particular or more generally for
combines?
> Cheers,
> 
> Dominik
>

Hi Daniel,

thanks for the follow-up! I left inline comments down below.

Am 12.10.20 um 20:55 schrieb Daniel Sanders:
>> One problem that some of us are seeing in the legalizer is that
sometimes instructions get expanded before they get folded away in the combiner.
IIRC Matt sees this happening with division, while I am seeing something similar
with unmerge.
> IIRC there were two main manifestations of it. For one it ends up at the
same MIR but takes a slower-than-necessary route to get there. For the other it
ends up with worse code which potentially can't be folded post-legalization.
I see. In our case it is definitely the latter: we end with with 
worse-code, or rather we end up with code which cannot be legalized 
further and therefore stops the compilation.
>> To my particular problem: due to the nature of the architecture I'm
working with, we have pretty strict legalization rules. One example is that we
only allow unmerges from 64 to 32 bit. Unmerges of 32-bit or less get lowered to
bit-arithmetic. However if we would do the same for anything bigger than 64-bit,
the legalization of the resulting bit arithmetic would introduce illegal
unmerges again, which then cause an endless loop in the legalizer.
> Are there particular >s64 cases that are the problem or is it all of
them? I'd expect s128, s256, etc. to G_UNMERGE fairly simply but
non-powers-of-2 are more likely to be tricky
I only noticed this problem with non-power-of-2 cases. Particularly s96, 
which we often encounter for some reason.
>> One of the ideas that was floated around yesterday sounded quite
interesting to me: multi-stage legalization where you could specify which of
your rules apply at which stage. I'm pretty sure this would solve our
problem. In our case we would declare all artifacts as legal in the first stage
to not hinder the combiner and in the second stage we could then focus on
actually legalizing any left-over artifacts we have.
>>
>> I do however see the problem that this could clutter up the existing
legalization info. Due to the amount of instructions and rules, it already is
quite complex and if rules could apply to different stages in the same file, it
could make it quite difficult to understand what exactly is happening now.
> It would definitely add some clutter but I suspect it would be manageable.
Essentially it would be a common ruleset for most operations and each pass would
add its own version of the merge/unmerge rules.
I think as long as most operations would use the common ruleset, it 
would indeed be manageable. But I suspect it would blow up significantly 
when the rule sets would largely differ. In those cases it would 
probably be better to allow a backend to define different legalization 
infos per stage. To be fair, I don't see a use-case for such a blown-up 
case at the moment, but if its fairly trivial, we shouldn't restrict 
backends too much here IMO.
>> I think Aditya pointed out that multi-stage legalization might be
already possible by just having two legalizer passes with different legalization
info and I feel like this might be the better approach of the two. I guess this
would still require some tweeks as currently in llc we can only say
`-stop-before/after=legalizer` but not which one of those.
> That's right. Each legalizer pass owns it's own ruleset so two
passes is a possibility. The -stop-before/after bit has been solved for some
other passes but it does need a bit of boilerplate. Each subclass needs it's
own pass id and INITIALIZE_* macros and getPassName() needs to be overridable.
Is there an existing example that I could look at? I would be fairly 
interested to try this out in our backend.
>> Another thing I was thinking of when I implemented this hack for our
use-case was that we need some kind of rule which tells the combiner that
something is supported but is actually not doing any legalization in the
legalizer (something like a `.combine()`, `.combineFor({s96})`).
> I'm not quite sure what you mean here. Are you thinking of legalization
rules for combining or something like legalization rules but for the combiner?
Are you thinking of artifact combines in particular or more generally for
combines?
Here I was only thinking about artifact combines. So in your 
legalization info you would define your rule set for e.g. 
G_UNMERGE_VALUES like so: `.legalFor({...})[...].combine()` The 
`.combine()` would have no effect on the legalizer itself, i.e. it would 
only return something equivalent to `UnableToLegalize` when 
`legalizeInstrStep(MI)` is called. However it would have an effect on 
the LegalizationArtifactCombiner: when the artifact combiner asks 
whether the resulting instruction of some combine is supported (which 
only checks whether there is some legalization rule covering the 
resulting instruction), it would return true and therefore enable the 
combine. I hope that makes it a bit clearer what I meant by
this.
>> Cheers,
>>
>> Dominik
>>
>>
-- 
----------------------------------------------------------------------
Dominik Montada                   Email: dominik.montada at hightec-rt.com
HighTec EDV-Systeme GmbH          Phone: +49 681 92613 19
Europaallee 19                    Fax:   +49-681-92613-26
D-66113 Saarbrücken               WWW: http://www.hightec-rt.com

Managing Director: Vera Strothmann
Register Court: Saarbrücken, HRB 10445, VAT ID: DE 138344222

This e-mail may contain confidential and/or privileged information. If
you are not the intended recipient please notify the sender immediately
and destroy this e-mail. Any unauthorised copying, disclosure or
distribution of the material in this e-mail is strictly forbidden.
---

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 6822 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20201013/cec4e12e/attachment.bin>