[RFC v2] "Alternative" matches for TableGen DAG patterns
ClosedPublic

Authored by uweigand on Jun 25 2018, 6:02 AM.

Details

Summary

This is an alternative approach to implement the same goal as described here:
https://reviews.llvm.org/D48326
See the summary of that patch for more information.

The difference of this approach is that instead of using a new keyword ("alternative"), we rather extend the PatFrag class to allow specifying multiple alternative match patterns -- this approach was suggested by Krzysztof in comments to D48326.

As an example, the z_sadd fragment mentioned in D48326 would instead be written as follows:

def z_sadd : PatFrags<(ops node:$src1, node:$src2),
                      [(z_saddo node:$src1, node:$src2),
                       (add node:$src1, node:$src2)]>;

Implementation-wise, the major difference is that instead of expanding "alternative" nodes in a separate pass over the PatternsToMatch vector after instruction/pattern parsing was completed, we now directly expand multiple alternatives when inlining pattern fragments. That is, the InlinePatterFragments routine no longer performs an in-place update of one single pattern, but instead maps one input pattern to a set of output patterns.

However, a number of other implementation differences follow from that. This mostly results from the fact that there doesn't seem to be a good way to handle multiple alternatives for the "set" nodes in the main instruction pattern. The approach in D48326 would continue to fully inline pattern fragments before parsing main instructions patterns -- this would inline the "alternative" nodes, but still retain a single "set" node. Instead, with the new approach we now defer inlining pattern fragments until after the initial parsing of the instruction pattern, and only inline fragments on the resulting "PatternToMatch". However, this doesn't fully work, since before inlining we may no longer recognize all input/output nodes; therefore, FindPatternInputsAndOutputs will now do a partial inlining just on named nodes (that serve as inputs) and set destination nodes (that serve as outputs). Since type resolution only works after pattern inlining, this is likewise defered. As an effect, parsing of the DAG pattern now shares a lot more code between the Instruction and the Pattern case, which should be a good thing in any case ...

As a follow-on, we also need to update the two other places that currently still refer to the full instruction pattern (including the "set" and "implicit" nodes): these are InferFromPattern and EmitResultInstructionAsOperand. The former currently infers flags separately from Instruction and Pattern nodes; now it just uses the PatternToMatch list, which contains both. This required rewriting the way the "isBitcast" flag is inferred. The latter uses the instruction pattern to search for SDNPHasChain property flags. This is now moved to InferFromPattern as well (since it basically is the same operation).

Note that in order to avoid spurious changes to other targets, I've for now still restricted the new inference code for the isBitcast and hasChain flags to patterns that originated from Instruction nodes. In general, it would probably be better to remove this final difference between instruction patterns and "regular" patterns, but that should IMO only be done after analysing the specific impacts on existing targets, so this should be done as a follow-on patch.

For now, this patch should be NFC for all targets:

  • for SystemZ I've verified that identical machine code is generated
  • for all other targets except Sparc, all TableGen generated files are identical, so machine code must be identical too
  • for Sparc, the TableGen generated file does change, because we're now running more type inference logic on Instruction patterns (which we used to run only on Pattern patterns), which allows TableGen to infer that the "iPTR:$dst" operand of LEAX_ADDri must actually have type i64. Since the pattern is only active when generating 64-bit code, this should likewise not cause any codegen changes.

A few open questions:

  1. I've renamed the PatFrag class to PatFrags, holding a "list<dag> Fragments" instead of a "dag Fragment". Does the name make sense? Or should this be called something like MultiPatFrag, or PatFragAlternatives, or ...?
  2. The original PatFrag is now a subclass of PatFrags, specialized to a single fragment. This required some changes to two targets (Hexagon and NVPTX) that directly accessed implementation details of PatFrag (specifically, the "Fragment" member). Should we instead leave PatFrag as is and and a nonrelated PatFrags class? This would make the implementation in TableGen a bit wordier ...
  3. Theoretically, a PatFrags instance can now have an empty Fragments list -- this would simply never match anything. Should this be explicitly forbidden? On the other hand, we might also use this to implement "null_frag" without hardcoding its name in TableGen ...

Diff Detail

Repository
rL LLVM
uweigand created this revision.Jun 25 2018, 6:02 AM
kpn added a subscriber: kpn.Jun 25 2018, 7:08 AM
tra added a subscriber: tra.Jun 25 2018, 11:17 AM

NVPTX changes look good. I should probably revisit that code and see if can be simplified after latest improvements in TableGen.

I haven't looked at this in detail yet, but it's looking great. Thanks for tackling this!

hfinkel accepted this revision.Jul 12 2018, 11:57 AM

LGTM (there are a lot of changes here, but given that it produces no changes to existing matching tables, that seems like pretty good test coverage).

As a follow-on, we also need to update the two other places that currently still refer to the full instruction pattern (including the "set" and "implicit" nodes): these are InferFromPattern and EmitResultInstructionAsOperand. The former currently infers flags separately from Instruction and Pattern nodes; now it just uses the PatternToMatch list, which contains both. This required rewriting the way the "isBitcast" flag is inferred. The latter uses the instruction pattern to search for SDNPHasChain property flags. This is now moved to InferFromPattern as well (since it basically is the same operation).

Note that in order to avoid spurious changes to other targets, I've for now still restricted the new inference code for the isBitcast and hasChain flags to patterns that originated from Instruction nodes. In general, it would probably be better to remove this final difference between instruction patterns and "regular" patterns, but that should IMO only be done after analysing the specific impacts on existing targets, so this should be done as a follow-on patch.

I definitely encourage resolving these in follow up. I think it will be better if this works uniformly.

  1. I've renamed the PatFrag class to PatFrags, holding a "list<dag> Fragments" instead of a "dag Fragment". Does the name make sense? Or should this be called something like MultiPatFrag, or PatFragAlternatives, or ...?

I think that PatFrags is good.

  1. The original PatFrag is now a subclass of PatFrags, specialized to a single fragment. This required some changes to two targets (Hexagon and NVPTX) that directly accessed implementation details of PatFrag (specifically, the "Fragment" member). Should we instead leave PatFrag as is and and a nonrelated PatFrags class? This would make the implementation in TableGen a bit wordier ...

I think that it should be logically organized as you have in the patch. After this goes in, we should make sure to update the release notes and send a "heads up" email to llvm-dev for out-of-tree targets with instructions on how to update.

  1. Theoretically, a PatFrags instance can now have an empty Fragments list -- this would simply never match anything. Should this be explicitly forbidden? On the other hand, we might also use this to implement "null_frag" without hardcoding its name in TableGen ...

I don't see any reason to disallow it. Getting rid of null_frag as a special case seems nice.

utils/TableGen/CodeGenDAGPatterns.cpp
3624 ↗(On Diff #152669)

Are you saying that, if we have clobber nodes after the pattern, then this will mistakenly take the last clobber node as the pattern?

This revision is now accepted and ready to land.Jul 12 2018, 11:57 AM

LGTM (there are a lot of changes here, but given that it produces no changes to existing matching tables, that seems like pretty good test coverage).

Thanks for the review!

Note that in order to avoid spurious changes to other targets, I've for now still restricted the new inference code for the isBitcast and hasChain flags to patterns that originated from Instruction nodes. In general, it would probably be better to remove this final difference between instruction patterns and "regular" patterns, but that should IMO only be done after analysing the specific impacts on existing targets, so this should be done as a follow-on patch.

I definitely encourage resolving these in follow up. I think it will be better if this works uniformly.

OK, I'll work on this as a follow-up.

  1. Theoretically, a PatFrags instance can now have an empty Fragments list -- this would simply never match anything. Should this be explicitly forbidden? On the other hand, we might also use this to implement "null_frag" without hardcoding its name in TableGen ...

I don't see any reason to disallow it. Getting rid of null_frag as a special case seems nice.

OK, I'll continue to allow empty Fragments. Unfortunately, getting rid of null_frag is more difficult than I expected: since current code checks for null_frag so very early, many backends get away with patterns that are actually invalid even structurally (number of results don't match number of users; use of some TableGen operators inside a pattern that aren't even dag nodes at all) as long as there's a null_frag anywhere in there as well. Trying to define a null_frag as a PatFrags with empty fragment list means that TableGen would still ignore the pattern, but only after doing a structural parse first -- which now errors out.

Now, possibly we should still do it, and clean up those backends first. But that again should be a follow-on patch.

Are you saying that, if we have clobber nodes after the pattern, then this will mistakenly take the last clobber node as the pattern?

First of all, note that I just copied this piece of code including its FIXME from one place to another, so my patch doesn't change anything substantive here.

The actual problem that the FIXME calls out is simply this: An original instruction can be a list including (set) statements, (implicit) statements, and plain source patterns (like e.g. stores). Now, some code is currently written as if to allow any sequence of any of these (e.g. more than one set, an implict followed by a set, etc). But other code already imposes a much more strict ordering: the first element must be either a set or a plain source pattern, and any subsequent elements must all be implicits. The code following the FIXME is one place where this more strict assumption is made.

I assume the reason for calling out a FIXME was that at some point, it was thought that this restriction was unreasonably harsh, and we should actually allow more generic sequences? But as the code stands today, I'd rather take the opposite position: we should make the restrictive assumption, because only under this assumption can we actually transform the instruction pattern into a "Pat" style pattern. (What should it even mean, exactly, to have two set nodes? ) But if this is true, then it would make more sense to fix the other pieces of code, and simply enforce the strict rules everywhere ...

LGTM (there are a lot of changes here, but given that it produces no changes to existing matching tables, that seems like pretty good test coverage).

Thanks for the review!

Note that in order to avoid spurious changes to other targets, I've for now still restricted the new inference code for the isBitcast and hasChain flags to patterns that originated from Instruction nodes. In general, it would probably be better to remove this final difference between instruction patterns and "regular" patterns, but that should IMO only be done after analysing the specific impacts on existing targets, so this should be done as a follow-on patch.

I definitely encourage resolving these in follow up. I think it will be better if this works uniformly.

OK, I'll work on this as a follow-up.

  1. Theoretically, a PatFrags instance can now have an empty Fragments list -- this would simply never match anything. Should this be explicitly forbidden? On the other hand, we might also use this to implement "null_frag" without hardcoding its name in TableGen ...

I don't see any reason to disallow it. Getting rid of null_frag as a special case seems nice.

OK, I'll continue to allow empty Fragments. Unfortunately, getting rid of null_frag is more difficult than I expected: since current code checks for null_frag so very early, many backends get away with patterns that are actually invalid even structurally (number of results don't match number of users; use of some TableGen operators inside a pattern that aren't even dag nodes at all) as long as there's a null_frag anywhere in there as well. Trying to define a null_frag as a PatFrags with empty fragment list means that TableGen would still ignore the pattern, but only after doing a structural parse first -- which now errors out.

Ah, okay. That makes sense.

Now, possibly we should still do it, and clean up those backends first. But that again should be a follow-on patch.

Given the constraints, allowing empty patterns still seems potentially useful, but it might not replace null_frag. I think that's okay too. I'd consider this particular item to be low priority.

Are you saying that, if we have clobber nodes after the pattern, then this will mistakenly take the last clobber node as the pattern?

First of all, note that I just copied this piece of code including its FIXME from one place to another, so my patch doesn't change anything substantive here.

The actual problem that the FIXME calls out is simply this: An original instruction can be a list including (set) statements, (implicit) statements, and plain source patterns (like e.g. stores). Now, some code is currently written as if to allow any sequence of any of these (e.g. more than one set, an implict followed by a set, etc). But other code already imposes a much more strict ordering: the first element must be either a set or a plain source pattern, and any subsequent elements must all be implicits. The code following the FIXME is one place where this more strict assumption is made.

I assume the reason for calling out a FIXME was that at some point, it was thought that this restriction was unreasonably harsh, and we should actually allow more generic sequences? But as the code stands today, I'd rather take the opposite position: we should make the restrictive assumption, because only under this assumption can we actually transform the instruction pattern into a "Pat" style pattern. (What should it even mean, exactly, to have two set nodes? ) But if this is true, then it would make more sense to fix the other pieces of code, and simply enforce the strict rules everywhere ...

Thanks for explaining, and I agree. I see nothing limiting about the stricter ordering.

This revision was automatically updated to reflect the committed changes.