Page MenuHomePhabricator

[globalisel] Re-factor ISel matchers into a hierarchy. NFC
ClosedPublic

Authored by dsanders on Jan 20 2017, 2:53 AM.

Details

Summary

This should make it possible to easily add everything needed to import all
the existing SelectionDAG rules. It should also serve the likely
kinds of GlobalISel rules (some of which are not currently representable
in SelectionDAG) once we've nailed down the tablegen definition for that.

The hierarchy is as follows:

MatcherRule - A matching rule. Currently used to emit C++ ISel code but will
|             also be used to emit test cases and tablegen definitions in the
|             near future.
|- Instruction(s) - Represents the instruction to be matched.
   |- Instruction Predicate(s) - Test the opcode, arithmetic flags, etc. of an
   |                             instruction.
   \- Operand(s) - Represents a particular operand of the instruction. In the
      |            future, there may be subclasses to test the same predicates
      |            on multiple operands (including for variadic instructions).
      \ Operand Predicate(s) - Test the type, register bank, etc. of an operand.
                               This is where the ComplexPattern equivalent
                               will be represented. It's also
                               nested-instruction matching will live as a
                               predicate that follows the DefUse chain to the
                               Def and tests a MatcherRule from that position.

Support for multiple instruction matchers in a rule has been retained from
the existing code but has been adjusted to assert when it is used.
Previously it would silently drop all but the first instruction matcher.

The tablegen-erated file is not functionally changed but has more
parentheses and no longer attempts to format the if-statements since
keeping track of the indentation is tricky in the presence of the matcher
hierarchy. It would be nice to have CMakes tablegen() run the output
through clang-format (when available) so we don't have to complicate
TableGen with pretty-printing.

It's also worth mentioning that this hierarchy will also be able to emit
TableGen definitions and test cases in the near future. This is the reason
for favouring explicit emit*() calls rather than the << operator.

Event Timeline

dsanders created this revision.Jan 20 2017, 2:53 AM
dsanders edited the summary of this revision. (Show Details)Jan 20 2017, 2:54 AM
dsanders updated this revision to Diff 85121.Jan 20 2017, 4:24 AM

Fix a silly mistake. RegisterOperandPredicate is testing the LLT for the register not the register itself.

kristof.beyls added inline comments.Jan 20 2017, 7:52 AM
utils/TableGen/GlobalISelEmitter.cpp
283

s/that// ?

285–287

Comments like this help to understand the code at least a little bit to someone like me who hasn't looked at tablegen much before. Please keep them :)

326–329

It stood out to me that the method with the same name on class OperandMatcher has the following, slightly different implementation:

template <class Kind, class... Args>
Kind &addPredicate(Args... args) {
  Predicates.emplace_back(make_unique<Kind>(std::forward<Args...>(args)...));
  return *static_cast<Kind *>(Predicates.back().get());
}

Any reason it has to be different?
Any reasonable way possible to not have to repeat this implementation, but be able to share a single implementation between both classes?

341–346

I think this needs a comment to explain what a MatcherRule is/does.
I think the comments on the classes above are really helpful to be able to understand the code and intent quickly.

342–353

To make the generated code more efficient, we'd probably want to play heuristics here so that the most discriminating predicate gets checked first?
Although I guess that's an optimization that can wait for later, until this design has proven to work well?

349–352

My guess it'd make sense for Matchers and Actions to either both be private or both be public?
My personal preference would be both private, but I'm not sure if the coding standard has anything to say on this.

ab edited edge metadata.Jan 20 2017, 10:14 AM

This seems reasonable to me. One quick question: how do you envision nested patterns/instructions? Would one of the parent's OperandMatchers have some sort of "instruction" predicate?

One quick question: how do you envision nested patterns/instructions? Would one of the parent's OperandMatchers have some sort of "instruction" predicate?

That's right. I'm expecting to have an OperandPredicateMatcher subclass that follows the DefUse chain to the def. It will then use an InstructionMatcher to match the nested instruction.

I'm still thinking through a couple details of the generated code that this case will need but it doesn't affect the representation of within tablegen. One issue is that it's possible for side-effects/memory/etc. between the matched instructions to prevent the match. I don't want to implement that by walking the intervening instructions since that's likely to be slow and might involve traversing the CFG in the long-run. The other one is what to do if the nested instruction has multiple uses since there's no single good answer for all situations. It depends on the target and whether the priority is performance/size/energy.

utils/TableGen/GlobalISelEmitter.cpp
326–329

Any reason it has to be different?

Well spotted. They're not supposed to be different.

Any reasonable way possible to not have to repeat this implementation, but be able to share a single implementation between both classes?

I think I can have InstructionMatcher and OperandMatcher subclass a template that defines the predicates and predicate-related methods. I'll take a look

341–346

Ok. I'll also rename it to RuleMatcher to make it consistent with InstructionMatcher/OperandMatcher

342–353

I agree. I think we should do that once we're successfully importing most of the SelectionDAG rules since there's likely to be a fair bit of iteration as we gain support for the more complicated ones.

Another optimization that will be important when we get to that will be hoisting common predicates out of the rules to reduce the amount that need to be checked. The main one will be the opcode check since implementing that as a switch that picks between different rule sets will dramatically cut down on the number of rules to check.

349–352

I think they should both be private but I wanted to stick to the matchers for this patch.

I'm also not sure we need support for multiple actions, since they aren't as easy to compose as the matchers are. My initial thoughts on the actions were to have a mutate operation (to just change the opcode), a simple replacement operation, an arbitrary C++ operation, and maybe a couple other common special cases.

dsanders updated this revision to Diff 85377.Jan 23 2017, 6:44 AM
  • Moved predicate handling from OperandMatcher and InstructionMatcher to a common base class template WithPredicates. I don't seem to be able to factor out the emitCxxPredicateExpr() loop though. I should be able to use the same technique as for addPredicate() but it doesn't work. I'm looking into it.
  • Add missing const's
  • Fix comment typos
  • Rename MatcherRule to RuleMatcher for consistency
dsanders marked 5 inline comments as done.Jan 23 2017, 6:45 AM
ab accepted this revision.Jan 24 2017, 6:35 PM

I should be able to use the same technique as for addPredicate() but it doesn't work. I'm looking into it.

Have you figured that out? Other than that, LGTM;

utils/TableGen/GlobalISelEmitter.cpp
124

The name is cryptic ...but I don't have a better idea ¯\_(ツ)_/¯

PredicateList? PredicateVector? PredicateHolder?

This revision is now accepted and ready to land.Jan 24 2017, 6:35 PM
dsanders updated this revision to Diff 85755.Jan 25 2017, 7:56 AM

Move appropriate emitCxxPredicatesExpr() methods into WithPredicates.

The '#if 0' block is just to provide an example of the version that doesn't
work. It's not intended for commit.

kristof.beyls added inline comments.Jan 25 2017, 8:24 AM
utils/TableGen/GlobalISelEmitter.cpp
124

I'm not entirely sure, but would PredicateMatcher be more in line with the terminology of the other classes used here?
And maybe the class hierarchy becomes a bit more simple to understand if the inheritance went roughly like follows:

class PredicateMatcher; /* rename of current WithPredicates. */
class OperandPredicateMatcher : PredicateMatcher<OperandPredicateMatcher>;
class InstructionPredicateMatcher : PredicateMatcher<InstructionPredicateMatcher>;
class OperandMatcher;
class InstructionMatcher;

rather than the current

class WithPredicates; /* rename of current WithPredicates. */
class OperandPredicateMatcher : PredicateMatcher<OperandPredicateMatcher>;
class InstructionPredicateMatcher : PredicateMatcher<InstructionPredicateMatcher>;
class OperandMatcher : WithPredicates<OperandPredicateMatcher>;
class InstructionMatcher : WithPredicates<InstructionPredicateMatcher>;

I'm afraid I haven't had much thought about this, but the first seems a bit more intuitive/easier to understand to me, assuming it's possible at all to define the class hierarchy like that.

Anyway, as I think we're still in the exploring phase for how the tablegen-generator will work, I don't think it's worthwhile to obsess too much on the last polishing touches of the OO-design of this part of the tablegen-generator right now, if it would be delaying further exploration of the tablegen-generator.

In D28942#655757, @ab wrote:

I should be able to use the same technique as for addPredicate() but it doesn't work. I'm looking into it.

Have you figured that out?

Not entirely. I've updated the patch to one that has a workaround that's ok-ish but I don't understand why the version of the code in the #if 0 block doesn't work. I've have thought that addPredicate() and emitCxxPredicates() would either both work or both fail.

utils/TableGen/GlobalISelEmitter.cpp
124

I struggled with ideas for the name too. The only reason I went with 'WithPredicates' is because it made the subclass declaration read nicely:

class OperandMatcher : public WithPredicates<OperandPredicateMatcher>

which defines an matcher with predicates.

I'll have another think on naming.

dsanders added inline comments.Jan 25 2017, 8:46 AM
utils/TableGen/GlobalISelEmitter.cpp
124

I'm not entirely sure, but would PredicateMatcher be more in line with the terminology of the other classes used here?

It would need to be PredicatesMatcher since it provides functions to add and emit code for multiple predicates.

And maybe the class hierarchy becomes a bit more simple to understand if the inheritance went roughly like follows:

class PredicateMatcher; /* rename of current WithPredicates. */
class OperandPredicateMatcher : PredicateMatcher<OperandPredicateMatcher>;
class InstructionPredicateMatcher : PredicateMatcher<InstructionPredicateMatcher>;
class OperandMatcher;
class InstructionMatcher;

In this hierarchy, each predicate would contain a list of predicates.

kristof.beyls added inline comments.Jan 25 2017, 11:06 PM
utils/TableGen/GlobalISelEmitter.cpp
124

Ah yes. PredicatesMatcher as a name is more clear to me than "WithPredicates". The hierarchy you have in your most recent patch also seems to make sense to me. Thanks for explaining!

dsanders added inline comments.Jan 26 2017, 3:20 AM
utils/TableGen/GlobalISelEmitter.cpp
124

Thinking about it a bit more this morning. It's easy to mis-read PredicatesMatcher as PredicateMatcher which then makes the hierarchy look wrong. I'll go with PredicateListMatcher to make that a bit clearer.

dsanders closed this revision.Jan 26 2017, 3:21 AM
ab added inline comments.Jan 26 2017, 2:20 PM
utils/TableGen/GlobalISelEmitter.cpp
124

SGTM; maybe rename emitCxxPredicatesExpr to emitCxxPredicateListExpr, for the same reason?

BTW, this naming scheme has an interesting quirk: how should we call top-level Predicates (non-instruction, as in, the actual Predicate class in Target.td). Locally, I went with the terrible but consistent PredicatePredicateMatcher. Any ideas?

163

I attempted to merge these into one in r293214; was that what you had in mind? Looks like std::forward<Args...> should have been std::forward<Args> ?

dsanders added inline comments.Jan 26 2017, 3:05 PM
utils/TableGen/GlobalISelEmitter.cpp
124

maybe rename emitCxxPredicatesExpr to emitCxxPredicateListExpr, for the same reason?

Good point. I'll do that in the morning.

BTW, this naming scheme has an interesting quirk: how should we call top-level Predicates (non-
instruction, as in, the actual Predicate class in Target.td). Locally, I went with the terrible but consistent
PredicatePredicateMatcher. Any ideas?

I'd suggest RulePredicateMatcher since they control whether we should attempt to apply a RuleMatcher.

PatternPredicateMatcher would also make sense if we go by the existing SelectionDAG classes.

163

Yep, that's what I was aiming for.

Given that I had it wrong there, it will also be wrong in addPredicate(). Maybe I got away with it there because no caller has >=2 arguments.