[llvm-dev] matchertable document

[Min-Yih Hsu via llvm-dev]

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 <https://github.com/bytecodealliance/wasmtime/tree/main/cranelift/peepmatic> 
[2] https://github.com/bytecodealliance/wasmtime/tree/main/cranelift <https://github.com/bytecodealliance/wasmtime/tree/main/cranelift> 

> On Feb 5, 2021, at 1:47 AM, ye janboe via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> hi,Gabriel
> 
> Thanks for this information.
> 
> Janboe
> 
> On Fri, Feb 5, 2021 at 2:46 PM Gabriel Hjort Åkerlund
> <gabriel.hjort.akerlund at ericsson.com> wrote:
>> 
>> 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
>> 
>> -----Original Message-----
>> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of ye janboe via
>> llvm-dev
>> Sent: den 5 februari 2021 04:08
>> To: llvm-dev at lists.llvm.org
>> Subject: [llvm-dev] 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
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://protect2.fireeye.com/v1/url?k=fdaefe94-a235c791-fdaebe0f-86d2114eab2f-66d5fe93dc952857&q=1&e=f48943dd-62b6-412a-845f-0b502e82239d&u=https%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210205/83f69b4b/attachment.html>