Re: Request: references on BURS

jimy@cae.wisc.edu wrote:


: Could someone please post some references on papers on BURS (Bottom Up
: Rewrite Systems). Any work that uses BURS is welcome. I'm particularly
: interested in how BURS compares with TWIG.


Check out Burg and Iburg. Iburg is much faster and more robust than TWIG


There are two articles of interest:


burg.ps PostScript for
                            C. W. Fraser, R. R. Henry and T. A. Proebsting,
                            `BURG -- Fast optimal instruction selection and tree parsing,'
                            SIGPLAN Notices 27, 4 (Apr. 1992), 68-76. 9 pages.
iburg.ps PostScript for
                            C. W. Fraser, D. R. Hanson and T. A. Proebsting,
                            `Engineering a simple, efficient code generator generator,'
                            ACM Letters on Programming Languages and Systems, 1993,
                            to appear. 14 pages.


The second one has a comparison of BURG with TWIG, and BURG uses BURS.


They are available (along with iburg) from ftp.cs.princeton.edu
(128.112.152.13) in pub/iburg.tar.Z.


: Also, I was told that there is a well known paper that proved optimal code
: generation for dags is NP-complete. Does anyone know its reference?


Look in the Dragon book, I seem to remember something there (although
my memory is fading....)


Burg and Iburg claim to be able to generate
an optimal cover for given patterns. A pattern would correspond to
an AST whose root node is a modify statement e.g.


a := a +b -c *d;


so it works quite well for CISC architectures, but it's fast pattern matching
ability isn't so advantageous for RISC (we just use it as a portable high
level tool for code generation).


Chris Donawa
donawa@acaps.cs.mcgill.ca
--

Return to the comp.compilers page.
Search the comp.compilers archives again.