(转)RTL

The Register Transfer Language

Why is an intermediate representation necessary?
It is of course possible to write a compiler that creates an abstract syntax tree and generates machine code directly from the tree. A compiler like GCC that supports many front- and back-ends would require geometrically many code generators, one for every combination of AST (for each source input langauge) and target machine. When portability and flexibility are paramount, then, it makes sense to translate all ASTs into some intermediate format that can then be used uniformly to generate code for any number of targets.

Furthermore, many compiler optimizations are dependent neither on the specifics of a particular abstract syntax nor on a specific type of hardware, but rather on program semantics. These optimizations need only be implemented just once by operating on the intermediate representation.

The Register Transfer Language
GCC's RTL representation must be generic enough to handle a host of front-ends: C, C++, Java, Fortran, etc. At the same time it cannot be so low-level that it can't be mapped to a particular machine description. Therefore it manifests itself as a suitably expressive abstract machine, with native support for several basic data types, and a simplified mechanism for making function calls. All of these data types can be modified as necessary to fit the specific vagaries of a given architecture. Below we analyze its structure in detail.

Expressions and Operands
The primary RTL object type is expression. Expressions are represented internally as C structures and can take on one of several different machine-independent types, each with a specified number of operands. These types can be extracted by the use of certain macros; furthermore, an expression's type is the only indication of what the operands are (it is impossible to ascertain an operand's type by examining it itself). Both of these issues would likely have been resolved if GCC were written in a object-oriented or strongly-typed language.

Expressions are divided into several classes from which you can derive the number and type of their component operands. For instance, an expression in the class '<' is generally some type of comparison operator and hence has operand format 'ee', representing the two expressions to compare. Certain expressions can have arbitrarily many operands, stored in a vector.

Operands can themselves be expressions, strings, or integers. To extract a particular operand, you invoke a macro corresponding to its type and position. For example, if the second operand of an expression e is an integer, extract it with the macro XINT(e, 2).

Expressions can contain several flags that refer to their status during optimizations or with respect to memory locations. For instance, the INSN_DEAD_CODE flag is true if the instruction has been marked dead during a dead-code elimination pass.

Each expression also has associated with it a machine mode class that describes its size and the physical method of representation that will be used to store it. The simplest machine description must only support one or two classes, and the compiler will use them to represent everything; of course, the more classes supported, the more likely an efficient representation will be used.

Constants, then, are represented as a value/mode pair.

Accessing Memory
Since the RTL has to be translated to actual machine instructions, it needs to differentiate between register accesses and main memory accesses. To this end, there are RTL expression types that correspond to registers and memory addresses. Since many machines can access the same register in different modes (full word, half word, etc.) even register expressions have modes associated with them. Of course, the RTL is not limited to any specific number of registers or it wouldn't be able to take advantage of machine architectures that have more than that number of registers; therefore RTL code is generated assuming an infinite number of registers, which will be later allocated to physical registers or spilled into main memory as necessary by the register allocator.

Furthermore, there are several custom registers: scratch registers that can be used with the understanding that their results will not be used after the execution of the current instruction; the program counter register; and the condition code register.

Memory is accessed in the standard way, with an address and a size of memory to retrieve. There is also an address of instruction that can force data to the stack if it is not counteracted by a corresponding dereference instruction.

RTL Capabilities
The RTL has a fairly simple instruction set. It has the usual arithmetic and comparison operations plus some interesting ones like sqrt and parity (which are supported by almost all architectures anyway). Forcing any input tree to a simple intermediate representation might forego optimization opportunities for some sophisticated architectures (such as one that has an FFT instruction, or something); however, the hope is that these cases will be recovered by the instruction selector/code generator as it tries to cover the RTL tree with as few instructions as possible. And the downside of supporting those instructions in the RTL is obvious: simple machine descriptions will have to painstakingly recreate each of the complex functions themselves. The RTL does have special support for reading and writing to bit-fields and vectors.

The RTL enforces a modicum of low-level type safety by requiring that any change in machine mode between expressions must be represented by an explicit conversion, for instance between fixed and floating point, or between a large integer size and a small one.

Side Effects
RTL has a couple of expression codes corresponding to side effects. For instance, set(lval, x) stores the value represented by x into the location represented by the lval (a register, memory location, etc.). The most interesting of these are

• the use(x) code that simply tells the compiler that a variable is being used here in some unspecified fashion; the compiler will then preserve any immediately previous instructions that just write to x
• the sequence code that stores a sequence of instructions
• the prefetch code that attempts to retrieve data before it is needed (so it will be available at the right time). In additional it has temporal locality hints. Obviously the idea is to reduce cache misses, but this seems like an awfully target-specific instruction, or at least one that should carried out at a lower level when registers have been allocated and the physical location of all memory items is known
• the parallel code that details instructions to be performed simultanously.
• the call code for performing function calls. This code has different effects w.r.t the registers it uses, etc. based on the target architecture.

In additional, there are several pre- and post-increment side effect instructions that must be used carefully, as not all instruction patterns may use them.

Finally, there is an asm code for hard-coded assembly. The assumption is that the source program was written for a specific target architecture.