Page MenuHomePhabricator

[GlobalISel Legalizer][RFC] Legalization artifact combiner

Authored by Petar.Avramovic on Jul 24 2019, 4:28 AM.



Discussion about Legalization artifact combiner and how to make sure it combines everything it can.
Looking for alternatives for D61787.

Legalization artifact combiner currently leaves uncombined artifacts because they :

  1. get legalized and are not in any list, and we don't try to combine again later
  2. we are missing necessary combine
  3. something else ?

Q: What to do with artifact that just failed to combine

Diff Detail

Event Timeline

About 2. we are missing necessary combine
We have some recursive combine attempts with G_TRUNC jumping to its use and attempting the combine from there.
This way both parts, G_TRUNC on one side G_ZEXT, G_SEXT or G_ANYEXT on the other, can perform combine.
But then all of them have to be ALWAYS legal, despite the fact they are not selectable, for artifact combiner to be able to perform combine.
If this is the right way to go, we are missing recursive combines for G_MERGE_VALUES, G_CONCAT_VECTORS, G_BUILD_VECTOR similar to G_TRUNC but then all artifacts have to be legal always.
@dsanders Did you have other combines in mind?

About D61787 : When artifact that just failed to combine we check if there is something in some of the lists (InstList, ArtifactList, AuxiliaryArtifactList) that could create other half that is needed for combine. When there is nothing in the lists that could create other half we have to legalize (most likely legal or narrowScalar).
D61787 Does change order of legalization/combines in the sense that it can delay combine attempt by putting artifact in TryLaterArtifactList instead of legalizing. Also removes recursive combine attempts.

Petar.Avramovic marked 10 inline comments as done.Jul 24 2019, 4:54 AM

Here are two files with -debug outputs from fame input test. One was generated with D61787 other without it. Test file contains:

define void @trunc(i32* %i32_ptr_a, i32* %i32_ptr_b) {
  %0 = load i32, i32* %i32_ptr_a, align 4
  %tobool = trunc i32 %0 to i1
  %frombool2 = sext i1 %tobool to i8
  %fromchar3 = zext i8 %frombool2 to i32
  store i32 %fromchar3, i32* %i32_ptr_b, align 4
  ret void

define i64 @merge(i32 %x, i32 %y, i64 %z) {
  %add = add i32 %y, %x
  %conv = sext i32 %add to i64
  %add1 = add i64 %conv, %z
  ret i64 %add1

In first function zext combine attempt happens first
in "current.txt" we legalize it and thanks to G_TRUNC jumps we get good result.
in "withD61787.txt" we attempt combine twice and succeed second time.

second function has sext narrowscalar
in "current.txt" we fail to combine merges
in "withD61787.txt" we succeed.

Both versions have:
some changes in the way how -debug prints info
narrow scalar for zext and sext
widen scalar for and shifts

differences are:
in "current.txt" artifact are legal except when we want to narrow scalar

getActionDefinitionsBuilder({G_ZEXT, G_SEXT, G_ANYEXT})
    .legalIf([=](const LegalityQuery &Query) {
      if (Query.Types[0].getSizeInBits() == 64 &&
          Query.Types[1].getSizeInBits() == 32)
        return false;
      return true;
    .maxScalar(0, s32);

    .legalIf([=](const LegalityQuery &Query) { return true; });

in "withD61787.txt" artifacts are not legal

getActionDefinitionsBuilder({G_ZEXT, G_SEXT, G_ANYEXT})
    .legalIf([=](const LegalityQuery &Query) { return false; })
    .maxScalar(0, s32);

    .legalIf([=](const LegalityQuery &Query) { return false; });

and D61787 is applied with some additional changes to how -debug prints


This one should wait and try combine later, instead it has to be legal in order to continue.


This artifact has to be legal, but it is not selectable. When other half of combine appears (G_TRUNC) it will jump back to this (at that moment legal) instruction and perform combine.


This is mentioned G_TRUNC jump to legal non-selectable instruction, and successful combine .


Here we could add G_MERGE combine similar to G_TRUNC but then other half (G_UNMERGE) has to be legal or be dealt with in some other way.


We don't legalize, instead we move artifact to TryLaterArtifactList


Back to ArtifactList from TryLaterArtifactList.


Successful combine without asking if artifact was legal.


G_SEXT might create G_MERGE if it gets narrow scalared, try later.


Instruction that defines %5 is legal (%5:_(s32) = G_ADD %1:_, %0:_) and as such cannot produce second half for combine (atm. that is G_TRUNC). We have to perform legalization with narrow scalar.


G_SEXT was legalized in the meantime, combine is successful without asking if G_MERGE/G_UNMERGE is legal.

Petar.Avramovic abandoned this revision.Sep 23 2019, 1:48 AM