This is an archive of the discontinued LLVM Phabricator instance.

[TableGen] Examine entire subreg compositions to detect ambiguity
ClosedPublic

Authored by kparzysz on Aug 20 2018, 10:14 AM.

Details

Summary

This is to avoid warnings from TableGen when a user-defined subregister index composition conflicts with an inferred one. This is a follow-up to D50725.

The comments in the testcase describe how this situation occurs.

Diff Detail

Repository
rL LLVM

Event Timeline

kparzysz created this revision.Aug 20 2018, 10:14 AM

The conflict between user-defined and inferred compositions causes a warning in the SystemZ build:

warning: SubRegIndex SystemZ::subreg_h64 and SystemZ::subreg_h32 compose ambiguously as SystemZ::subreg_hh32 or SystemZ::subreg_h32

This patch eliminates the warning in cases where such a conflict is legitimate (by resolving it in favor of user-defined compositions).

bjope added a subscriber: bjope.Sep 18 2018, 11:54 AM

I like the idea. I can take a closer look at the patch when I'm at the office tomorrow.

bjope added a comment.EditedSep 19 2018, 10:04 AM

I see one problem with this.

If you take a look at for example SystemZRegisterInfo.td we got

let Namespace = "SystemZ" in {
def subreg_l32   : SubRegIndex<32, 0>;  // Also acts as subreg_ll32.
def subreg_h32   : SubRegIndex<32, 32>; // Also acts as subreg_lh32.
def subreg_l64   : SubRegIndex<64, 0>;
def subreg_h64   : SubRegIndex<64, 64>;
def subreg_hh32  : ComposedSubRegIndex<subreg_h64, subreg_h32>;
def subreg_hl32  : ComposedSubRegIndex<subreg_h64, subreg_l32>;
}

And those compositions are quite nice to be able to specify manually (giving them a custom name).

But in the past we have also gotten warning if trying to add a composition like this

def subreg_ll32  : ComposedSubRegIndex<subreg_l64, subreg_l32>;

I kind of liked that warning, because if you add such a composition (that happens to clash with the uncomposed subreg_l32) you would end up with identical, but different subregister indices. They will occupy space in the lane masks and will not be identified as being identical when for example comparing the subregister index enum values in the code.

Maybe it is a slightly different problem, but the above is the reason why we are using the same name as tablegen when creating the composed subregister indices in our out-of-tree target.
So you could also get rid of the warning by doing:

def subreg_h64_then_subreg_h32  : ComposedSubRegIndex<subreg_h64, subreg_h32>;

Although that won't give you the possibility to choose a custom name.

It would be nice to find a solution where we still could give a warning/error for the subreg_ll32 composition, while still being able to use a custom name (without a warning) for the subreg_hh32 composition.

Another idea is to allow some kind of aliases (I was thinking about that some time ago). Such as

def subreg_ll32  : AliasedSubRegIndex<subreg_l32>;

or maybe

def subreg_ll32  : ComposedSubRegIndexAlias<subreg_l64, subreg_l32>;

making it possible to use subreg_ll32 as a name in mir-files, td-files etc. But having subreg_ll32 and subreg_l32 mapping to the same enum value in subregister idx enum.
I guess debug/mir-printouts would pick the default name and not the alias. So that might be confusing of course.

I've looked into this and there is no way to distinguish the case of hh (no warning) and ll (emit a warning). They are both equivalent: a user-defined composition vs. pre-existing subreg.

I don't think we can easily handle this right now, and I don't really want to be implementing a whole new functionality in TableGen for this (although I'm not opposed to the concept).

I think a difference is that the ll composition clash with a user-defined subreg, while the hh composition clashes with a tablegen synthesized subreg.
And we do not get the extra synthesized subreg index for hh when there is a user defined composition.

Maybe we can give a warning/error if the user tries to define a subreg like ComposedSubRegIndex<X, Y> and the result is an alias/duplicate for Y.
Those are the subregs that I think we want to avoid, because they result in duplicate subregs, and additional lane masks.
What do you think about that?

Btw, the ideas about adding support for aliases was just to plant a seed. I did not see it as a quick fix here, but maybe a future feature.

The warning seem to be plain wrong. The warning claims that

warning: SubRegIndex SystemZ::subreg_h64 and SystemZ::subreg_h32 compose ambiguously as SystemZ::subreg_hh32 or SystemZ::subreg_h32

This is based on V0: subreg_h64(V0) = F0D, subreg_h32(F0D) = F0S. So the composition (and subreg_hh32, user-defined as that composition) maps V0 to F0S. Now subreg_h32(V0) = F0S, so for V0 these two indeed agree. This is the cause for the warning.
However, for F0Q, subreg_h32(subreg_h64(F0Q)) = subreg_h32(F0D) = F0S, while subreg_h32(F0Q) = F2S. So, while these compositions agree on at least one register, they are not equal in general.

For illustration, here are all subregs as maps Register->Register, where subreg: R -> R:subreg.

subreg_h64: { V0->F0D V1->F1D V2->F2D V3->F3D V4->F4D V5->F5D V6->F6D V7->F7D
              V8->F8D V9->F9D V10->F10D V11->F11D V12->F12D V13->F13D V14->F14D V15->F15D
              V16->F16D V17->F17D V18->F18D V19->F19D V20->F20D V21->F21D V22->F22D V23->F23D
              V24->F24D V25->F25D V26->F26D V27->F27D V28->F28D V29->F29D V30->F30D V31->F31D
              F0Q->F0D F1Q->F1D F4Q->F4D F5Q->F5D F8Q->F8D F9Q->F9D F12Q->F12D F13Q->F13D
              R0Q->R0D R2Q->R2D R4Q->R4D R6Q->R6D R8Q->R8D R10Q->R10D R12Q->R12D R14Q->R14D }
subreg_h32: { V0->F0S V1->F1S V2->F2S V3->F3S V4->F4S V5->F5S V6->F6S V7->F7S
              V8->F8S V9->F9S V10->F10S V11->F11S V12->F12S V13->F13S V14->F14S V15->F15S
              V16->F16S V17->F17S V18->F18S V19->F19S V20->F20S V21->F21S V22->F22S V23->F23S
              V24->F24S V25->F25S V26->F26S V27->F27S V28->F28S V29->F29S V30->F30S V31->F31S
              F0D->F0S F1D->F1S F2D->F2S F3D->F3S F4D->F4S F5D->F5S F6D->F6S F7D->F7S
              F8D->F8S F9D->F9S F10D->F10S F11D->F11S F12D->F12S F13D->F13S F14D->F14S F15D->F15S
              F16D->F16S F17D->F17S F18D->F18S F19D->F19S F20D->F20S F21D->F21S F22D->F22S F23D->F23S
              F24D->F24S F25D->F25S F26D->F26S F27D->F27S F28D->F28S F29D->F29S F30D->F30S F31D->F31S
              F0Q->F2S F1Q->F3S F4Q->F6S F5Q->F7S F8Q->F10S F9Q->F11S F12Q->F14S F13Q->F15S
              R0D->R0H R1D->R1H R2D->R2H R3D->R3H R4D->R4H R5D->R5H R6D->R6H R7D->R7H
              R8D->R8H R9D->R9H R10D->R10H R11D->R11H R12D->R12H R13D->R13H R14D->R14H R15D->R15H
              R0Q->R1H R2Q->R3H R4Q->R5H R6Q->R7H R8Q->R9H R10Q->R11H R12Q->R13H R14Q->R15H }
subreg_l64: { F0Q->F2D F1Q->F3D F4Q->F6D F5Q->F7D F8Q->F10D F9Q->F11D F12Q->F14D F13Q->F15D
              R0Q->R1D R2Q->R3D R4Q->R5D R6Q->R7D R8Q->R9D R10Q->R11D R12Q->R13D R14Q->R15D }
subreg_hh32: { F0Q->F0S F1Q->F1S F4Q->F4S F5Q->F5S F8Q->F8S F9Q->F9S F12Q->F12S F13Q->F13S
               R0Q->R0H R2Q->R2H R4Q->R4H R6Q->R6H R8Q->R8H R10Q->R10H R12Q->R12H R14Q->R14H }
subreg_l32: { R0D->R0L R1D->R1L R2D->R2L R3D->R3L R4D->R4L R5D->R5L R6D->R6L R7D->R7L
              R8D->R8L R9D->R9L R10D->R10L R11D->R11L R12D->R12L R13D->R13L R14D->R14L R15D->R15L
              R0Q->R1L R2Q->R3L R4Q->R5L R6Q->R7L R8Q->R9L R10Q->R11L R12Q->R13L R14Q->R15L }
subreg_hl32: { R0Q->R0L R2Q->R2L R4Q->R4L R6Q->R6L R8Q->R8L R10Q->R10L R12Q->R12L R14Q->R14L }

The FPR64 and VR128 classes are a little bit unusual(?) as they only have one subreg, that maps to the high part of the register.

For VR128 (that isn't CoveredBySubregs only the high part should be accessible using subregs afaict. So it should not be possible to do subreg_h32(V0), right?
To be able to access bit 32-63 you need to say that VR128 has two subregs,SubRegIndices = [subreg_h32, subreg_h64].

So it should not be possible to do subreg_h32(V0), right?

Tablegen makes registers "inherit" some subregister indices from their subregisters, so you can end up with a h32 of a register that didn't initially have it.

So it should not be possible to do subreg_h32(V0), right?

Tablegen makes registers "inherit" some subregister indices from their subregisters, so you can end up with a h32 of a register that didn't initially have it.

Well, I think tablgen messed up things here. Not sure where you got those tables, but I would have expected to find

subreg_hh32: { V0->F0S V1->F1S V2->F2S V3->F3S V4->F4S V5->F5S V6->F6S V7->F7S
              V8->F8S V9->F9S V10->F10S V11->F11S V12->F12S V13->F13S V14->F14S V15->F15S
              V16->F16S V17->F17S V18->F18S V19->F19S V20->F20S V21->F21S V22->F22S V23->F23S
              V24->F24S V25->F25S V26->F26S V27->F27S V28->F28S V29->F29S V30->F30S V31->F31S

instead of

subreg_h32: { V0->F0S V1->F1S V2->F2S V3->F3S V4->F4S V5->F5S V6->F6S V7->F7S
              V8->F8S V9->F9S V10->F10S V11->F11S V12->F12S V13->F13S V14->F14S V15->F15S
              V16->F16S V17->F17S V18->F18S V19->F19S V20->F20S V21->F21S V22->F22S V23->F23S
              V24->F24S V25->F25S V26->F26S V27->F27S V28->F28S V29->F29S V30->F30S V31->F31S

as that would make sense when doing subreg_h32(subreg_h64(V0)). But you got no such entries in your maps. Instead you got these entries for doing subreg_h32 on the V<n> registers, which is something that isn't defined in the definitions in SystemZRegisterInfo.td.

Right at the beginning of CodeGenRegBank::computeComposites, I added

  // The map being the result of applying a subregister to registers.
  using SubRegApp = std::map<const CodeGenRegister*, const CodeGenRegister*>;

  std::map<const CodeGenSubRegIndex*, SubRegApp> SubRegImages;
  for (const CodeGenRegister &R : Registers) {
    const CodeGenRegister::SubRegMap &SM = R.getSubRegs();
    for (std::pair<const CodeGenSubRegIndex*, const CodeGenRegister*> P : SM)
      SubRegImages[P.first].insert({&R, P.second});
  }

  // The equivalence map of subregisters.
  std::map<SubRegApp, std::set<const CodeGenSubRegIndex*>> SubRegEq;
  for (std::pair<const CodeGenSubRegIndex*, const SubRegApp&> P : SubRegImages)
    SubRegEq[P.second].insert(P.first);

  for (auto &I : SubRegEq) {
//    if (I.second.size() <= 1)
//      continue;
//    dbgs() << "Equivalent subregs:";
//    for (const CodeGenSubRegIndex *S : I.second)
//      dbgs() << ' ' << S->getName();
//    dbgs() << "\n                  {";
for (const CodeGenSubRegIndex *S : I.second) dbgs() << S->getName() << ": {";
    for (std::pair<const CodeGenRegister*, const CodeGenRegister*> P : I.first)
      dbgs() << ' ' << P.first->getName() << "->" << P.second->getName();
    dbgs() << " }\n";
  }

I was originally trying to calculate the sets of equivalent subregisters, but they all ended up unique (i.e. the sets all had only one element).

kparzysz updated this revision to Diff 175318.Nov 26 2018, 1:00 PM
kparzysz retitled this revision from [TableGen] Prefer user-defined subregister compositions over inferred ones to [TableGen] Examine entire subreg compositions to detect ambiguity.

Examine subregister (and composition) actions on all registers when detecting ambiguities. This eliminates the warning from the SystemZ build, but keeps the warning in the subreg_ll32 from earlier comments.

bjope added inline comments.Nov 27 2018, 6:53 AM
test/TableGen/ambiguous-composition.td
16 ↗(On Diff #175318)

I assume this should be

def subreg_l32  : SubRegIndex<32, 0>;

or

def subreg_l32  : SubRegIndex<32>;

(I think the tested scenario still should be valid, but we avoid the possible confusion with subreg_h32 and subreg_l32 having the same definition)

37 ↗(On Diff #175318)

Isn't this ambiguity still making the register/subregister definitions for SystemZ a little bit dubious. I do not have an example where it actually is causing any problems, but it feels weird.
Anyway, if there is no better way to describe the SystemZ registers I guess we have to live with this oddity.

kparzysz marked 2 inline comments as done.Nov 27 2018, 7:21 AM
kparzysz added inline comments.
test/TableGen/ambiguous-composition.td
16 ↗(On Diff #175318)

The numbers don't matter at all, except for debug information, but you're right---they should be correct regardless.

37 ↗(On Diff #175318)

With the current handling of subregisters by TableGen there is no way to completely avoid partially overlapping compositions. If we disallow partial overlaps, we get the warning that people have been complaining about (i.e. more or less the current state of things). If we allow them, we end up with the undiagnosed subreg_ll32 issue (discussed earlier).
This solution is ugly and it is a hack to avoid the false-positive warning, but it should work as long as subregister composition is done consistently in the same manner on the overlapping parts.

kparzysz updated this revision to Diff 175481.Nov 27 2018, 7:23 AM

Fixed the definition of subreg_l32 in the testcase.

I must have missed the earlier discussion, but I agree with @bjope 's comment earlier that subreg_h32(V0) -> F0S is actually wrong; there should not be any subreg_h32(V0) at all!

For 128-bit registers, I understood that subreg_h32(Reg) should be inherited as subreg_h32(subreg_l64(Reg)), but there is no actual subreg_l64 of V registers.

Can you explain why tablegen comes up with that implicit definition? Is this because V registers have a subreg_h64 as first and only subreg?

If so, maybe we can fix this by swapping around the low and high subregs of all other register definitions, so that then subreg_h32 *always* maps to subreg_h32(subreg_h64)), and instead of explicit subreg_hh32 and subreg_hl32 we have rather subreg_lh32 and subreg_ll32 ?

I must have missed the earlier discussion, but I agree with @bjope 's comment earlier that subreg_h32(V0) -> F0S is actually wrong; there should not be any subreg_h32(V0) at all!

V0 has a subregister F0D, which has a subregister index subreg_h32 mapping F0D to F0S. TableGen applies the same index with the same result to the super-register, giving subreg_h32(V0) = F0S. This is just how TableGen does it. In the long term it's probably TableGen that needs to be fixed, but I don't know what impact that will have on other backends.

Here's the original testcase with the comment explaining how the conflict happens. It's less nuanced than the current testcase, but the comment should still apply.

include "llvm/Target/Target.td"

def TestInstrInfo : InstrInfo {
}

def Test : Target {
  let InstructionSet = TestInstrInfo;
}

let Namespace = "Test" in {
  def subreg_h32  : SubRegIndex<32, 32>;
  def subreg_h64  : SubRegIndex<64, 64>;
  def subreg_hh32 : ComposedSubRegIndex<subreg_h64, subreg_h32>;
}

class TestReg<string n, list<Register> s> : RegisterWithSubRegs<n, s> {
  let Namespace = "Test";
}

class FPR32<string n> : TestReg<n, []> {
}

class FPR64<string n, FPR32 high> : TestReg<n, [high]> {
  let SubRegIndices = [subreg_h32];
}

class FPR128<string n, FPR64 high> : TestReg<n, [high]> {
  let SubRegIndices = [subreg_h64];
}

def F0S : FPR32<"f0s">;
def F0D : FPR64<"f0d",  F0S>;
def F0Q : FPR128<"f0q", F0D>;

// 1. Because of the explicitly defined composition for subreg_hh32,
//    subreg_hh32.updateComponents will add to subreg_h64 a composition:
//    subreg_h64+subreg_h32 -> subreg_hh32.
// 2. computeSubRegs will add to F0Q a subreg F0D (subreg_h64), and then
//    transitively F0D's subregs (subreg_h32). It will update F0Q's subreg
//    map that F0S is a subreg of F0Q reachable via subreg_h32.
// 3. computeComposites will iterate over subreg maps of each register to
//    determine subregister index compositions. The composition map already
//    contains the user-defined composition from (1). Because of (2), i.e.
//    F0Q.subreg_h32 = F0S, which is also F0Q.subreg_h64.subreg_h32, it is
//    assumed that subreg_h64+subreg_h32 -> subreg_h32. This creates a
//    conflict and results in a warning.

def FP32  : RegisterClass<"FP32",  [f32],   32,  (add F0S)>;
def FP64  : RegisterClass<"FP64",  [f64],   64,  (add F0D)>;
def FP128 : RegisterClass<"FP128", [v2f64], 128, (add F0Q)>;

If so, maybe we can fix this by swapping around the low and high subregs of all other register definitions, so that then subreg_h32 *always* maps to subreg_h32(subreg_h64)), and instead of explicit subreg_hh32 and subreg_hl32 we have rather subreg_lh32 and subreg_ll32 ?

To elaborate on this, I've now implemented this here: https://reviews.llvm.org/D54962 (with a more detailed explanation)

This does indeed eliminate the warning, without any changes in code generation. (And it is a back-end only patch with no TableGen changes required.)

@kparzysz, does that make sense to you?

@kparzysz, does that make sense to you?

If it works, then it sounds great to me.

bjope added a comment.Nov 29 2018, 7:16 AM

Got a feeling that I'm the one who has been questioning this solution. And I guess I also kind of blocked the progress in D54962.
Anyway, I haven't really got any better alternative right now (at least not that is easy to implement).

If we land this we at least get rid of what seems to be "false" warnings for SystemZRegisterInfo.td.
And then:

  • If we find a SystemZ internal solution (continuation of D54962) we can always revert this later when it isn't needed any longer.
  • If we find a better way to deal with syntesized/composed subregisters etc in tablegen, then we can work on that (in peace) without rushing anything.

Does that sound good to you @kparzysz and @uweigand ?
(If you agree, then I can accept this solution for now.)

This sounds good to me. I hope a better solution is developed later, but at least we get rid of the warning.

bjope accepted this revision.Nov 29 2018, 7:48 AM

LGTM!

Might wait a little before you land this to see if @uweigand got anything more to say. But afaict this only removes the warning without affecting the result in any way, so it should not make anything worse.

This revision is now accepted and ready to land.Nov 29 2018, 7:48 AM

LGTM!

Might wait a little before you land this to see if @uweigand got anything more to say. But afaict this only removes the warning without affecting the result in any way, so it should not make anything worse.

Well, I'm fine with this patch as well. I haven't found any other way to fix it in the back-end without introducing other problems ...

This revision was automatically updated to reflect the committed changes.