johnson@cs.uiuc.edu (Ralph Johnson) (08/10/90)
My experience is that register transfers are a very nice intermediate
language. My compiler uses two intermediate languages, abstract syntax trees
for language dependent optimizations, and register transfers for language
independent optimizations. I learned about RTL from the papers by Davidson
and Fraser. Also, the GNU compilers use a register transfer language.
Register transfers are very compatible with static single assignment form,
which is a data structure for representing programs developed by a group at
IBM. You could use SSA without RTL, or RTL without SSA, but I have had good
success using them together.
The end of the message has some references for your reading pleasure. The
ones on SSA all have Zadeck as a co-author.
Ralph Johnson - University of Illinois at Urbana-Champaign
_______
@InProceedings{alpern88,
author="Bowen Alpern and Mark N. Wegman and F. Kenneth Zadeck",
title="Detecting Equality of Variables in Programs",
booktitle=popl88,
year=1988,
pages="1-11"
}
@InProceedings{cytron86,
author = "Ron Cytron and Andy Lowry and Kenneth Zadeck",
title = "Code Motion of Control Structures in High-Level Languages",
booktitle = popl86,
year = 1986,
pages = "70-85"
}
@InProceedings{cytron89,
author = "Ron Cytron and Jeanne Ferrante and Barry Rosen
and Mark Wegman and Kenneth Zadeck",
title = "An Efficient Method of Computing Static Single Assignment Form",
booktitle = popl89,
year = 1989,
pages = "25-35"
}
@ARTICLE{davidson80,
author="Jack W. Davidson and Christopher W. Fraser",
title="The Design and Application of a Retargetable Peephole Optimizer",
journal=toplas,
volume=2,
number=2,
month=apr,
year=1980,
pages="191--202"
}
@phdthesis{davidson81,
author="Jack W. Davidson",
title="Simplifying Code Generation Through Peephole Optimizations",
school="University of Arizona",
year="1981"}
@article{davidson84,
author="Jack W. Davidson and Christopher W. Fraser",
title="Code Selection through Object Code Optimization",
journal=toplas,
volume=6,
number=4,
year=1984,
pages="505-526"}
@inproceedings{davidson84a,
author="Jack W. Davidson and Christopher W. Fraser",
title="Automatic Generation of Peephole Optimizations",
booktitle="Proceedings of the ACM SIGPLAN '84 Symposiom on
Compiler Construction",
year="1984",
pages="111-116"}
@article{davidson84b,
author="Jack W. Davidson and Christopher W. Fraser",
journal="Software - Practice and Experience",
title="Register Allocation and Exhaustive Peephole Optimization",
volume=14,
number=9,
month=sep,
year=1984,
pages="857-865"}
@techreport{davidson85,
author="Jack W. Davidson",
title="Simple Machine Description Grammars",
institution="Department of Computer Science, University of Virgina",
year="1985"}
@InProceedings{davidson86,
author="Jack W. Davidson",
title="A Retargetable Instruction Reorganizer",
booktitle=sigplan86,
year=1986,
pages="234-241"
}
@article{davidson87,
author="Jack W. Davidson and Christopher W. Fraser",
title="Automatic Interence and Fast Interpretation of Peephole
Optimization Rules",
journal="Software - Practice and Experience",
volume=17,
number=11,
pages="801-812",
month=nov,
year=1987}
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue. Meta-mail to compilers-request@esegue.farnum@sequoia.Berkeley.EDU (Charlie Farnum) (08/10/90)
A Scheme-like IL is the way to go. Guy Steele suggested this many moons ago
(like before 1980, in one of the ``Lambda: the ultimate
{imperative,declarative}'' papers), and evidence has been steadily
accumulating since then. A recent reference you might want to look at is
``Compilation by Program Transformation'', Richard Kelsey's 1989 dissertation
from Yale, which presents a Pascal compiler using a Scheme-ish IL.
The Scheme IL community emphasizes continuation-passing style (CPS), which is
convenient (but not necessary) for many of the things you need to do for
Scheme and a royal pain for traditional bread-and-butter optimizations. This
is unfortunate, because the non-CPS style code is perfect for many of the
tree-transformation systems that are popping up, e.g., the pattern-matching
code generators that have been around for several years now. (Which, by the
way, don't deal very well with loop instructions; loops are very hard to
canonicalize, and most IL trees don't include control flow. Of course, if
people would only use Scheme style ILs... :-) )
If you would like a rough ten pages of arguments on why a Scheme-like IL is
wonderful, let me know. If you'ld rather wait for the finished version, look
for ``Prototyping Optimizing Compilers'', coming this December to a Tech
Report list near you.
/charlie
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue. Meta-mail to compilers-request@esegue.