Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: George Neuner Newsgroups: comp.compilers Subject: Re: Best language for implementing compilers? Date: Sun, 10 Mar 2019 18:58:43 -0400 Organization: A noiseless patient Spider Lines: 35 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <19-03-013@comp.compilers> References: <19-02-002@comp.compilers> <19-02-004@comp.compilers> <19-02-006@comp.compilers> <19-03-009@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="55324"; mail-complaints-to="abuse@iecc.com" Keywords: optimize, tools Posted-Date: 10 Mar 2019 21:10:25 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:2179 Very nice post! On Sun, 10 Mar 2019 04:13:47 -0700 (PDT), Christopher F Clark wrote: >Unless you have written a one-pass compiler, the output of your lexer/parser >combination is usually some form of syntax tree (either a parse tree or an >AST). That may or may not be a convenient intermediate representation (IR). >If it's not you need to "rewrite" it into one. Usually making one of more >passes over the tree to do so. > >This is where ML style pattern matching shines. You have a tree (DAG, graph, >some sort of data structure that has links in it) and you want to modify it. >The ML pattern match allows you to specify the shape of the tree you want to >match and extract the relevant parts into convenient local variables. You can >then use those variables to construct a new tree that has the parts >reconnected (rewritten) into the shape you desire in your IR. It also can be useful to use tree matching for code generation: the basic idea being to map the IR onto the instructions of the target machine (where a target "instruction" might be a sequence of native instructions). You create tree patterns that correspond to target "instructions", treat those patterns as tiles and try to cover the IR tree using a minimum "weight" of tiles [where the tile "weight" could be cycles consumed, registers needed, energy used, etc. ... whatever is useful for the given task]. This works with any ISA, but it is particularly useful for CISC machines that often provide more than one way to perform the same operation. The minimum weight tiling will correspond to an optimal program [for some definition of "optimal"]. George