Re: Request: references on BURS

<jimy@cae.wisc.edu> writes:
>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.


The papers you want are


    title="Optimal Code Generation for Expression Trees: An Application
                  of {BURS} Theory",
    author="Eduardo {Pelegr\'i}-Llopart and Susan L. Graham",
    booktitle=popl15,
    address="San Diego, California",
    year=1988,
    month=jan,
    pages="294--308"




    title="Simple and Efficient {BURS} Table Generation",
    author="Todd A. Proebsting",
    pages="331--340",
    journal=sigplan,
    year=1992,
    month=jul,
    volume=27,
    number=7,
    note=pldi92




The code you may want is also available in the form of a couple of tools,
burg and iburg.


Iburg and its documentation are available via anonymous ftp from
ftp.cs.princeton.edu (128.112.152.13) in pub/iburg.tar.Z.


Burg and its documentation are available via anonymous ftp from
kaese.cs.wisc.edu. The compressed shar file pub/burg.shar.Z holds the
complete distribution.


>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?


The NP-completeness of achieving optimality in the sense of minimizing
register usage for DAGS is proven in


    title="Complete Register Allocation Problems",
    author="Ravi Sethi",
    journal="SIAM Journal of Computing",
    volume=4,
    number=3,
    year=1975,
    month=sep,
    pages="226--248",


Preston Briggs
--

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