<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">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). <div class="">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).</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">Hope this help.</div><div class=""><br class=""></div><div class="">Best,</div><div class="">-Min</div><div class=""><br class=""></div><div class="">[1] <a href="https://github.com/bytecodealliance/wasmtime/tree/main/cranelift/peepmatic" class="">https://github.com/bytecodealliance/wasmtime/tree/main/cranelift/peepmatic</a> </div><div class="">[2] <a href="https://github.com/bytecodealliance/wasmtime/tree/main/cranelift" class="">https://github.com/bytecodealliance/wasmtime/tree/main/cranelift</a> <br class=""><div class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Feb 5, 2021, at 1:47 AM, ye janboe via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="">hi,Gabriel<br class=""><br class="">Thanks for this information.<br class=""><br class="">Janboe<br class=""><br class="">On Fri, Feb 5, 2021 at 2:46 PM Gabriel Hjort Åkerlund<br class=""><<a href="mailto:gabriel.hjort.akerlund@ericsson.com" class="">gabriel.hjort.akerlund@ericsson.com</a>> wrote:<br class=""><blockquote type="cite" class=""><br class="">Hi Janboe,<br class=""><br class="">As far as I know, there is no such document. The closest thing I have found<br class="">which explains how the matchtable works is a blog post:<br class=""><a href="https://eli.thegreenplace.net/2013/02/25/a-deeper-look-into-the-llvm-code-generator-part-1" class="">https://eli.thegreenplace.net/2013/02/25/a-deeper-look-into-the-llvm-code-generator-part-1</a><br class=""><br class="">It's dated, but the core of it is still applies today.<br class=""><br class="">Cheers,<br class="">Gabriel<br class=""><br class="">-----Original Message-----<br class="">From: llvm-dev <llvm-dev-bounces@lists.llvm.org> On Behalf Of ye janboe via<br class="">llvm-dev<br class="">Sent: den 5 februari 2021 04:08<br class="">To: llvm-dev@lists.llvm.org<br class="">Subject: [llvm-dev] matchertable document<br class=""><br class="">hi,<br class="">I want to understand how instruction is matched, but I could not find any<br class="">document about martchertable by googling.<br class=""><br class="">Is there any document about how it is generated by tablegen and how it works<br class="">for instruction selection?<br class=""><br class="">Thanks<br class=""><br class="">Janboe<br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class="">llvm-dev@lists.llvm.org<br class="">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<br class=""></blockquote>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></div></blockquote></div><br class=""></div></div></body></html>