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>