[globalisel][tablegen] Add control-flow to the MatchTable.
ClosedPublic

Authored by dsanders on Fri, Jul 7, 4:03 AM.

Details

Summary

This will allow us to merge the various sub-tables into a single table. This is a
compile-time saving at this point. However, this will also enable the optimization
of a table so that similar instructions can be tested together, reducing the time
spent on the matching the code.

The bulk of this patch is a mechanical conversion to the new MatchTable object
which is responsible for tracking label definitions and filling in the index of
the jump targets. It is also responsible for nicely formatting the table.

This was necessary to support the new GIM_Try opcode which takes the index to
jump to if the match should fail. This value is unknown during table
construction and is filled in during emission. To support nesting try-blocks
(although we currently don't emit tables with nested try-blocks), GIM_Reject
has been re-introduced to explicitly exit a try-block or fail the overall match
if there are no active try-blocks.

dsanders created this revision.Fri, Jul 7, 4:03 AM
rovka added a comment.Mon, Jul 17, 4:46 AM

I think the commit message should elaborate a bit on why we want a single table.
Other nits:

include/llvm/CodeGen/GlobalISel/InstructionSelector.h
118

Unrelated change, please commit separately.

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h
33

I think omitting the return type for a lambda with more than one return statement is C++14, you might run into trouble with some of the buildbots.

250

Both the comment on this and the summary say that this either exists the current try block or completely fails to match if there is no try block. That's not what this does, this just completely fails. Your lambda seems to take care of the logic for exiting the current block or bailing out, so it seems like this state is really unnecessary - it would be enough to just not generate a Try block at all for the last instruction that you're matching (so you wouldn't actually need to generate a Try/Reject pair for any of the current tests). Am I missing something?

test/TableGen/GlobalISelEmitter.td
102

The spaces in the comments are really unrelated, can you get rid of them for this patch?

utils/TableGen/GlobalISelEmitter.cpp
234

This comment sounds weird, can you rephrase?

255

How do the other TableGen backends handle indentation? Personally I preferred your previous patch which just ran clang-format on the generated files, since that kept the backends simple. But if other people don't like that approach, we should at least try to share some of this stuff between backends (if it wouldn't be too convoluted).

454

Unrelated change, please commit separately.

dsanders added inline comments.Tue, Jul 18, 5:34 AM
include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h
33

You're right. Apparently some compilers will silently accept it but I expect there will be some that don't. I'll fix this.

250

Good point. I think I missed this one because at the moment it only appears as the last opcode of a table to prevent executeMatchTable() from falling off the end.

I'm going to need it inside GIM_Try blocks once I start nesting them so I'll correct this one to use handleReject() too.

it would be enough to just not generate a Try block at all for the last instruction that
you're matching (so you wouldn't actually need to generate a Try/Reject pair for any of
the current tests)

I'd prefer not to special case the last block since this will get quite confusing once GIM_Try blocks start nesting. I think it's an optimization we should leave until late in development if we do it.

test/TableGen/GlobalISelEmitter.td
102

Sure, they're part of the formatting that MatchTable::Comment() so I can make that format without the spaces.

utils/TableGen/GlobalISelEmitter.cpp
234

The last word was supposed to be 'table' but it's still not particularly clear after that either.

The main thing I'm trying to convey is that there's no inheritance hierarchy (the MatchTableRecord class supports all the quirks of each kind of record such as adding comment characters and indenting) so that the table can be a simple vector. How about this:

This class represents any and all output that may be required to emit the MatchTable. Instances  are most often configured to represent an opcode or value that will be emitted to the table with some formatting but it can also represent commas, comments, and other formatting instructions.
255

Most of them do it on an ad-hoc basis when they need it and hard-code the whitespace if they don't need anything special. The closest example is SelectionDAG which indents its table in a similar way so that it's easy for a human to see the structure of the decisions being made by the state machine.

Unfortunately, the clang-format approach won't help in this case because it's not aware of the meaning of the data. It's not aware that it ought to keep opcodes and arguments on the same line or that GIM_Try/GIM_Reject should affect indentation to help a human follow the decisions the state machine will make. It would be neat if it was possible to teach clang-format about special cases like this table but that will be more complicated.

454

Ok

dsanders edited the summary of this revision. (Show Details)Tue, Jul 18, 5:39 AM
dsanders updated this revision to Diff 107137.Tue, Jul 18, 10:42 AM
dsanders marked 7 inline comments as done.

Rebased.
Fixed accidental usage of C++14
Fixed GIM_Reject always rejecting instead of exiting the current GIM_Try block when appropriate.
Remove whitespace around generated comments.

rovka accepted this revision.Wed, Jul 19, 3:03 AM

LGTM with minor nits.

include/llvm/CodeGen/GlobalISel/InstructionSelector.h
65

but and

118

This is marked as done, but the change is still in the patch...

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h
94

This break looks redundant.

123

Redundant.

140

Redundant.

157

Redundant.

177

Redundant.

193

Redundant.

209

Redundant.

217

This one doesn't print the CurrentIdx when debugging.

234

Redundant.

246

Redundant.

250

Ok.

test/TableGen/GlobalISelEmitter.td
213

This is also an unrelated whitespace change (I guess it's not as bad as the previous one though, since it only shows up in a couple of places).

utils/TableGen/GlobalISelEmitter.cpp
234

That sounds much better.

255

Ok, I don't think it makes sense to burden clang-format with this kind of knowledge.

281

You should make NumElements private and use this instead of accessing it directly (e.g. in MatchTable::push_back).

This revision is now accepted and ready to land.Wed, Jul 19, 3:03 AM
dsanders marked 6 inline comments as done.Wed, Jul 19, 3:19 AM

Thanks. I'll fix these for the commit.

include/llvm/CodeGen/GlobalISel/InstructionSelector.h
118

I marked it done because I'd pulled it out into my svn working copy ready to commit this morning (r308424). It will drop out after another rebase

test/TableGen/GlobalISelEmitter.td
213

This one is a consequence of standardizing it in the handling of MatchTable::Comment()

dsanders closed this revision.Thu, Jul 20, 2:26 AM
dsanders marked 19 inline comments as done.