matchertable document

hi,
I want to understand how instruction is matched, but I could not find
any document about martchertable by googling.

Is there any document about how it is generated by tablegen and how it
works for instruction selection?

Thanks

Janboe

Hi Janboe,

As far as I know, there is no such document. The closest thing I have found
which explains how the matchtable works is a blog post:
https://eli.thegreenplace.net/2013/02/25/a-deeper-look-into-the-llvm-code-generator-part-1

It's dated, but the core of it is still applies today.

Cheers,
Gabriel

hi,Gabriel

Thanks for this information.

Janboe

Here is a TLDR version of how MatchTable in SelectionDAG ISel and GlobalISel will works: The entire isel process is transformed into a state machine where each state performs some checks to see if certain region of DAG (a single node most of the time) fulfill some conditions (e.g. what is the opcode? what are the operand types?). If any of those (checks) fail, it will jump to another state. Otherwise target-specific node will be generated (via the MorphNode action, for example).
In addition, this process is done in a top-down fashion. That is, it starts from the root of the expressions and descending to its children (i.e. operands of an expression). So actually it will start from the last instruction of a BB (or function).

Personally I found this process resemble to some peephole optimization (InstCombine in LLVM) works that are implemented using finite state automata. For example, peepmatic [1] in the Cranelift [2] code generator. The figure in peepmatic’s README basically outline MatchTable’s mechanism as described here. Nevertheless MatchTable also uses more advanced and complex techniques like scopes and stack to manage its matching state.

Hope this help.

Best,
-Min

[1] https://github.com/bytecodealliance/wasmtime/tree/main/cranelift/peepmatic
[2] https://github.com/bytecodealliance/wasmtime/tree/main/cranelift

hi, Min

Thanks a lot for your explanation, and it is very helpful.