UVa CS Zephyr Register Transfer Lists (RTLs)

Compiling with Register Transfer Lists (RTLs)

We prescribe a form of RTLs that is designed to be used by tools, not by people. To simplify analysis, we make the form simple, and we insist that as much information as possible be explicit in the RTL itself. We don't care if individual RTLs grow large, as long as they are composed from simple parts using only a few cases. This choice distinguishes CSDL RTLs from earlier work, which has used smaller RTLs that make implicit assumptions about details like operand sizes and byte order.

In Zephyr,

• RTLs are represented as trees.
• All operators are fully disambiguated, e.g., as to type and size.
• There is no covert aliasing of locations---locations with different spaces or offsets are always distinct.
• Fetches are explicit, as are changes in the size or type of data.
• Stores are annotated with the size of the data stored.
• Explicit tree nodes specify byte order. More generally, they specify how to transfer data between storage spaces with different cell sizes.

A register transfer list is a list of guarded effects. Each effect represents the transfer of a value into a storage location, i.e., a store operation. The transfer takes place only if the guard (an expression) evaluates to true. Effects in a list take place simultaneously, as in Dijkstra's multiple-assignment statement---an RTL represents a single change of state, and we can specify swap instructions without introducing phony temporaries. Values are computed by expressions without side effects. Eliminating side effects simplifies analysis and transformation. Expressions may be integer constants, fetches from locations, or applications of RTL operators to lists of expressions.

Our paper Machine Descriptions to Build Tools for Embedded Systems describes Zephyr RTLs in more detail.