RTL

Several recent postings have discussed RTL, the register transfer
language used in GCC.


>Why was the GNU C compiler implemented using RTL as opposed to 4-tuples or quads?


GCC is based in part on PO, a retargetable peephole optimizer that Jack
Davidson and I developed at the University of Arizona starting in 1978.
If you're asking why GCC's developers chose this particular model, then
you'll have to ask them. If you're asking why the model uses register
transfers, then perhaps I can help.


Most peephole optimizers operate on machine instructions, and they need to
know what the instructions do. A machine-specific peephole optimizer can
use a machine-specific representation for instructions, and the programmer
can burn into the optimizer machine-specific information about the effects
of instructions. A retargetable peephole optimizer, however, needs a
machine-independent way to represent the effects of machine-specific
instructions. (If that sounds like a contradiction, consider C: one can
write machine-specific C programs, but the language itself is machine
independent.) Register transfers are such a representation.


A quad can't represent an arbitrary machine instruction. Each quad
generally specifies one operation (eg, one addition), but even RISC
instructions can specify multiple operations. Also, quads generally
manipulate machine-independent temporaries, but peephole optimizers
operate on instructions, and instructions operate on machine-specific
cells like registers and memory.


That's why retargetable peephole optimizers use register transfers, but
perhaps the real question was: why base a compiler on a retargetable
peephole optimizer in the first place? A proper answer would take too
much space here. See the 10/84 TOPLAS. Related papers appeared in the
4/80 TOPLAS and the 9/84 SP&E. Two preliminary papers appeared in POPL
(1/79 and 1/82), but the later journal papers dominate them. All papers
but the first are joint with Davidson. There have been other papers and
other collaborators since, but they address other issues, like other
optimizations and speeding up the compiler.


>Is there an interpreter or simulator available for RTL?


I don't know about GCC's particular RTL, but Jack wrote a simulator for
PO's after he graduated and moved to the University of Virginia. This
simulator has not been maintained and is not "available". Jack has also
augmented his machine descriptions with C code to simulate the target
instructions; this approach simulates faster. I prefer the middle ground
--- compiling the register transfers into C code --- because it's fast and
requires nothing extra in the machine descriptions.


>To your knowledge, has anyone done a study comparing quads and RTL?


No, but in my experience, many optimizations traditionally performed on
quads can also be performed on register transfers, and by
machine-independent code if one has access to a machine description. For
example, PO eliminated common subexpressions on register transfers. The
job is easier on quads, but if it's done then, one misses any common
subexpressions that are introduced when the quads are later expanded into
target code. How much is lost by this "early" optimization depends on the
particular optimization and machine.


>The idea of using RTL came from the U. of Arizona Portable Optimizer,
>written by Jack Davidson and Christopher Fraser. This is described in
>"Register Allocation and Exhaustive Peephole Optimization",
>Software Practice and Experience 14 (9), Sept. 1984, pp. 857-866


This statement has two minor flaws. "U. of Arizona Portable Optimizer"
appears to be a proper name, but the correct name is "PO". The "P"
abbreviated "peephole", not "portable", although PO was portable as well.
Also, PO itself is better described in the TOPLAS papers. The SP&E paper
focusses on PO's interaction with register allocation.


Chris Fraser
AT&T Bell Laboratories
cwf@research.att.com
--

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