[llvm-dev] GlobalISel round table follow-up: multi-stage legalization

[Dominik Montada via llvm-dev]

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>