Re: Request: references on BURS (Chris DONAWA)
Wed, 28 Jul 1993 21:24:07 GMT

          From comp.compilers

Related articles
Request: references on BURS (1993-07-28)
Re: Request: references on BURS (1993-07-28)
Re: Request: references on BURS (1993-07-28)
Re: Request: references on BURS (1993-07-29)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Chris DONAWA)
Keywords: optimize, tools
Organization: Compilers Central
References: 93-07-076
Date: Wed, 28 Jul 1993 21:24:07 GMT 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: 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. 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
( 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

Post a followup to this message

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