This is an archive of the discontinued LLVM Phabricator instance.

[GlobalISel] Legalizer: Retry combining illegal artifacts as long as there new artifacts
ClosedPublic

Authored by volkan on Aug 7 2019, 10:51 AM.

Details

Summary

Currently, Legalizer aborts if it’s unable to legalize artifacts. However, it’s
possible to combine them after processing the rest of the instruction because
the legalization is likely to generate more artifacts that allow ArtifactCombiner
to combine away them.

Instead, move illegal artifacts to another list called RetryList and wait until all of the
instruction in InstList are legalized. After that, check if there is any new artifacts and
try to combine them again if that’s the case. If not, abort. The idea is similar to D59339,
but the approach is a bit different.

This patch fixes the issue described above, but the legalizer still may be unable to handle
some cases depending on when to legalize artifacts. So, in the long run, we probably need
a different legalization strategy that handles this dependency in a better way.

Diff Detail

Event Timeline

volkan created this revision.Aug 7 2019, 10:51 AM

I'm not keen on this patch but I prefer it to D61787. Both patches have issues with not fully solving the problem (more on this below) but this one doesn't require new concepts, still has a simple processing order, and is closer to the principle of the legalizer focusing on correctness and not optimization (i.e. it does just enough to make the MIR legal and no more). On that basis I'm going to say LGTM for now but we need to fix the core problem soon.

A big problem is that we're minimizing the number of combine attempts without honouring the ordering requirements that permit this minimization. That's fixable by better ordering or by more repetition but I think the core problem is deeper than that. I think the core problem is the division of instructions into artifacts and non-artifacts and treating them differently. As long as we have special cases I think we'll find increasingly obscure situations where the division doesn't quite work. Back when we introduced artifacts, we were still figuring out legality w.r.t context but since then we've distinguished between context-sensitive legality (forbidden) and context-sensitive legalization (permitted). I think we can exploit this to remove the artifact concept, simplify the legalizer, and resolve the problem with the algorithm getting stuck.

The key principles are:

  • All instructions have legalization rules (including artifacts)
  • So long as something legalizes, individual UnableToLegalize results aren't fatal
  • Legalization actions can use the context to legalize. In the case of artifacts like G_ANYEXT/G_TRUNC, using the context is the _only_ way they can legalize

The algorithm would then simply be:

until fully legal do:
    for each MI (bottom-up order for efficiency) do:
        legalize(MI)
    if no progress made (i.e. every legalize() returned UnableToLegalize):
        abort()

The overall behaviour of this is that the first pass will introduce islands of instructions that report UnableToLegalize, these are the artifacts we have today minus the ones that were able to combine on the first try. The second and subsequent passes will resolve some of the artifacts and maybe introduce some new legalizable instructions get legalized on the next pass. We repeat that until we converge or fail to make progress.

The key thing here is what the artifacts do to legalize and they essentially do the current combines. For example:

getActionDefinitionsBuilder(G_ANYEXT)
    .legalFor({s32, s32})
    .clampScalar({s32, s32});

we would sometimes widenScalar and narrowScalar a G_ANYEXT but that isn't possible by replacing it with something else. Instead widenScalar(0, s32) would do:

%0:(s16) = G_ANYEXT %1:(s8)
=>
%0:(s32) = G_ANYEXT %1:(s8)

which is trivial, but widenScalar(1, s32) would (among other things) do:

%1:(s16) = G_TRUNC %2:(s32)
%0:(s32) = G_ANYEXT %1:(s16)
=>
%0:(s32) = %2:(s32)
%1:(s8) = G_TRUNC %2:(s16)
%0:(s32) = G_ANYEXT %1:(s8)
=>
%0:(s32) = G_ANYEXT %2:(s16) // We improved matters but can't return Legalized as we didn't quite get there with this change alone. Maybe we need a NotQuiteLegalized for this case

essentially all the existing artifact combines would be moved to the appropriate action and be context-sensitive legalizations.

Even if that doesn't pan out, one thing I think we should do is make G_ZEXT/G_SEXT normal instructions that legalize using G_ANYEXT, G_TRUNC, G_AND, and G_SEXT_IN_REG as required. This is because they're the only artifacts that change bits in the value (as opposed to leaving some undefined) and limiting the artifacts to bit-copying operations (with some undefined bits) makes it easier to ensure we cover all the combinations and avoids the temptation to veer into optimization.

dsanders accepted this revision.Aug 22 2019, 3:13 PM
This revision is now accepted and ready to land.Aug 22 2019, 3:13 PM

@arsenm Could you take a look at the AMDGPU tests?

The test changes look fine. They all look like 16-bit unmerges now getting correctly expanded

This revision was automatically updated to reflect the committed changes.