Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!think.com!mintaka!spdcc!iecc!compilers-sender From: cwf@research.att.com Newsgroups: comp.compilers Subject: RTL Keywords: GCC, RTL Message-ID: <9012052213.AA20917@ursa-major.spdcc.com> Date: 5 Dec 90 22:13:00 GMT Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: cwf@research.att.com Organization: Compilers Central Lines: 76 Approved: compilers@iecc.cambridge.ma.us 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 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. Brought to you by Super Global Mega Corp .com