Zephyr RTL Creation Interface

Intro

RTL Creation Interface

Assembly Language Interface

VPO Code Generation Interface

RTL Creation Interface

RTL Creation Interface

Introduction
Basic kinds of RTL nodes
Expression Node Generation Functions

Constant Expressions

Numeric Constants
Relocatable Addresses

Fetch Expression
RTL operators

Location Node Generation Functions
Effect (RTL) Node Generation Functions

Assignment Effect
Guard Effect
Kill Effect
List of Effects

Example Usage
Index of identifiers
List of code chunks

Introduction

This interface is for producing Register Transfer Lists (RTLs). A Register Transfer List is an architecture-independent representation of a machine instruction.

This RTL interface is intended to be very general purpose, so that it can be incorporated into a variety of higher level interfaces. For example, the VPOi interface to the VPO code improver uses this RTL interface to generate RTL trees. Throughout this document VPOi is mentioned in examples of how the RTL interface is actually used.

The interface defines types, values, and functions. Tables [->] and [->] summarize the types and functions.

<rtl.h>=
<type and value definitions>
<prototypes of interface functions>

Type	Abbreviation Meaning
`Rtl_ty_rtl`	rtl	A register transfer list (RTL), or effect.
`Rtl_ty_expr`	expr	An expression node in an RTL.
`Rtl_ty_oper`	oper	An RTL operator (used within an expression).
`Rtl_ty_loc`	loc	A location node in an RTL.
`Rtl_ty_const`	const	A machine-dependent constant.
`Rtl_ty_relAddr`	relAddr	A relocatable address. See the assembly-language interface.
`Rtl_ty_storage`	storage	A character representing a storage space (registers, memory, etc.).

Types used in this interface [*]

Expressions
expr Rtl_int(long n) Signed constant.

expr Rtl_uint(unsigned long value) Unsigned constant.

expr Rtl_const(const cnst) Machine-dependent constant.

expr Rtl_relAddr(relAddr addr) Relocatable address.

expr Rtl_fetch(loc loc, int size) Fetch.

expr Rtl_apply(oper oper, ...) Apply an RTL operator of any arity.

expr Rtl_unary(oper oper, expr arg) Apply a unary RTL operator.

expr Rtl_binary(oper o, expr l, expr r) Apply a binary RTL operator.

Locations
loc Rtl_location(storage s, expr addr) Location at an arbitrary address.

loc Rtl_constLoc(storage s, long addr) Location at a a constant, known address.

Effects
rtl Rtl_assign(loc l, int size, expr e) Store operation.

rtl Rtl_guard(expr expr, rtl effect) Guarded (predicated) effect.

rtl Rtl_kill(loc loc1, ...) Kill effect.

rtl Rtl_list(rtl rtl1, ... ) Simultaneous execution of multiple effects.

Functions defined in this interface [*]

Basic kinds of RTL nodes

An RTL is represented as a tree which is constructed using the functions in this interface. There are three basic types of nodes in an RTL tree.

Expression (Rtl_ty_expr) - a value that can be computed and stored.
Location (Rtl_ty_loc) - storage in the machine such as a general purpose register or word of memory.
Effect (Rtl_ty_rtl) - a change in the contents of one or more locations.

<type and value definitions>= (<-U) [D->]
typedef struct Rtl_st_expr *Rtl_ty_expr;
typedef struct Rtl_st_loc  *Rtl_ty_loc;
typedef struct Rtl_st_rtl  *Rtl_ty_rtl;

Defines Rtl_ty_expr, Rtl_ty_loc, Rtl_ty_rtl (links are to index).

The root of a RTL tree is always a Rtl_ty_rtl node.

Some RTL expressions are formed by applying RTL operators to other expressions:

<type and value definitions>+= (<-U) [<-D->]
typedef struct Rtl_st_oper *Rtl_ty_oper;

Defines Rtl_ty_oper (links are to index).

The following sections describe the functions for producing RTLs.

Expression Node Generation Functions

An expression may be a constant, a value stored in a location, or the result of an operation.

Constant Expressions

RTL trees support two types of constants: numeric constants and relocatable addresses. A numeric constant is typically an integral or floating point value. A relocatable address stands for an integer constant (or address) whose value is not known when the RTL is constructed.

Numeric Constants

The RTL interface provides rudimentary support for integer constants. The following functions return an expression node containing a signed integer constant or and unsigned integer constant, respectively.

<prototypes of interface functions>= (<-U) [D->]
Rtl_ty_expr Rtl_int(long value);
Rtl_ty_expr Rtl_uint(unsigned long value);

Defines Rtl_int, Rtl_uint (links are to index).

Few architectures support floating point-constants in their instruction set. Occasionally, however, an RTL must be expressed using the floating point constants 0.0, 1.0, or NaN (not a number). A machine might have an instruction that compares with 0.0, or compares with NaN, or increments a floating point register. In such a situation, the processor supplement will define suitable RTL operators to be used to produce +/-0.0, 1.0, or various NaNs.

In order to provide completely general support for constants, a RTL expression node may contain a constant of type Rtl_ty_const.

<type and value definitions>+= (<-U) [<-D->]
typedef struct Rtl_st_const *Rtl_ty_const;

Defines Rtl_ty_const (links are to index).

The definition of struct Rtl_st_const is not part of the RTL interface. It is a target-dependent data structure that should provide whatever additional support for constants is needed on the target.

The following function constructs an expression node that contains such a numeric constant.

<prototypes of interface functions>+= (<-U) [<-D->]
Rtl_ty_expr Rtl_const(Rtl_ty_const cnst);

Defines Rtl_const (links are to index).

The RTL interface provides no way to construct objects of type Rtl_ty_const. This task is left to other interfaces.

Relocatable Addresses

A relocatable address is an integral constant whose value is not known at the time that the RTL is created, and may not be known until the program is linked. In a RTL tree a relocatable address is a symbol that stands for a constant. In the VPOi interface, relocatable addresses denote the addresses of global variables, the entry points of functions, statement addresses (i.e., labels), and offsets from the stack pointer to local variables and function parameters.

A relocatable address is stored in a RTL tree as a Rtl_ty_relAddr.

<type and value definitions>+= (<-U) [<-D->]
typedef struct relAddr_st *Rtl_ty_relAddr;

Defines Rtl_ty_relAddr (links are to index).

The definition of relAddr_st is not part of the RTL interface; Rtl_ty_relAddr is an abstract type.

The following function constructs an expression node that contains a relocatable address.

<prototypes of interface functions>+= (<-U) [<-D->]
Rtl_ty_expr Rtl_relAddr(Rtl_ty_relAddr addr);

Defines Rtl_relAddr (links are to index).

The RTL interface provides no way to create objects of type Rtl_ty_relAddr. This task is handled outside of this interface. For example, various functions in the Assembly Language interface return objects of type AsmSymbol, which contains a pointer to struct relAddr_st.

Fetch Expression

Using the following function, an expression can be created to represent a value stored in a location.

<prototypes of interface functions>+= (<-U) [<-D->]
Rtl_ty_expr Rtl_fetch(Rtl_ty_loc loc, int size);

Defines Rtl_fetch (links are to index).

loc is the location and size is the number of bits being fetched.

RTL operators

An expression may consist of an operator applied to operands. The operands must also be expressions. The operator is represented by the opaque structure pointer Rtl_ty_oper, as defined above.

The RTL interface defines a set of standard operators. When possible, an operator on the target should be represented by the corresponding standard operator. For example, most targets support integer addition, and this should be represented with the standard operator Rtl_op_add. Many targets provide operators that do not correspond to a single standard operator. Often these can be represented as a combination of a few standard operators in a simple expression node. For example, Sun's SPARC processor provides an ANDNOT (bit clear) instruction. The operation A ANDNOT B can be represented by a simple RTL expression node that uses the standard operators Rtl_op_and and Rtl_op_not. More complex target specific operators can be defined outside the RTL interface. For example, Sun's SPARC processor has an instruction that saves all registers. This is not easily represented as an expression consisting of standard operators, so it is best handled by defining a SPARC specific operator. For example, the VPOi interface for the SPARC defines such an operator.

Expect some standard operators to have no equivalent on the target machine. The goal is to realize the target machine using the standard RTL operators, not vice versa.

In the current interface, it is impossible to specify the sizes of operators' operands and results, because VPO infers all sizes from the sizes used in Rtl_fetch and Rtl_assign. A future version of VPO will not only support sizes; it will require that RTL operators be specialized with size parameters. For example, the add operator will take one size parameter, used to indicate the number of bits in its operands (and result). The types of the standard operators are therefore expected to change in a future version of this interface.

The following standard operators are binary except those indicated to be unary.

<type and value definitions>+= (<-U) [<-D->]
extern Rtl_ty_oper
  /**************** ADDITION AND SUBTRACTION ****************/
  Rtl_op_add,     /* two's-complement integer addition */
  Rtl_op_addF,    /* floating point addition */
  Rtl_op_sub,     /* two's-complement integer subtraction */
  Rtl_op_subF,    /* floating point subtraction */
  Rtl_op_mul,     /* signed integer multiplication */
  Rtl_op_mulUn,   /* unsigned integer multiplication */
  Rtl_op_mulF,    /* floating point multiplication */

<type and value definitions>+= (<-U) [<-D->]
  /**************** MULTIPLICATION AND DIVISION ****************/
  Rtl_op_divRz,   /* signed integer division, round toward zero,
                     eg, -25 / 7 == -3  */
  Rtl_op_divRn,   /* signed integer division, round negative,
                     eg, -25 / 7 == -4  */
  Rtl_op_divUn,   /* unsigned integer division */
  Rtl_op_divF,    /* floating point division */
  Rtl_op_modRz,   /* signed integer modulus, round toward zero
                     A modRz B == A - ((A divRz B) * B)
                     eg, -25 modRz 7 == -4  */
  Rtl_op_modRn,   /* signed integer modulus, round negative,
                     A modRn B == A - ((A divRn B) * B)
                     eg, -25 modRn 7 == 3   */
  Rtl_op_modUn,   /* unsigned integer modulus */

  Rtl_op_neg,     /* integer negation, two's complement (unary) */
  Rtl_op_negF,    /* floating point negation (unary) */

<type and value definitions>+= (<-U) [<-D->]
  /**************** BIT OPERATORS ****************/
  Rtl_op_not,     /* bitwise NOT (unary) */
  Rtl_op_and,     /* bitwise AND */
  Rtl_op_or,      /* bitwise OR */
  Rtl_op_xor,     /* bitwise exclusive OR */
  Rtl_op_lshift,  /* bitwise left shift */
  Rtl_op_rshift,  /* bitwise right shift, zero fill */
  Rtl_op_rshiftA, /* bitwise right shift, arithmetic,
                     extend sign bit */
  Rtl_op_lrot,    /* bitwise left rotate */
  Rtl_op_rrot,    /* bitwise right rotate */

<type and value definitions>+= (<-U) [<-D->]
  /**************** COMPARISONS ****************/
  Rtl_op_cmp,     /* signed integer compare */
  Rtl_op_cmpUn,   /* unsigned integer compare */
  Rtl_op_cmpF,    /* floating point compare */
  Rtl_op_eq,      /* integer equality */
  Rtl_op_eqF,     /* floating point equality */
  Rtl_op_ne,      /* integer inequality */
  Rtl_op_neF,     /* floating point inequality */
  Rtl_op_gt,      /* signed integer greater than */
  Rtl_op_gtUn,    /* unsigned integer greater than */
  Rtl_op_gtF,     /* floating point greater than */
  Rtl_op_ge,      /* signed integer greater than or equal to */
  Rtl_op_geUn,    /* unsigned integer greater than or equal to */
  Rtl_op_geF,     /* floating point greater than or equal to */
  Rtl_op_lt,      /* signed integer less than */
  Rtl_op_ltUn,    /* unsigned integer less than */
  Rtl_op_ltF,     /* floating point less than */
  Rtl_op_le,      /* signed integer less than or equal to */
  Rtl_op_leUn,    /* unsigned integer less than or equal to */
  Rtl_op_leF,     /* floating point less than or equal to */

<type and value definitions>+= (<-U) [<-D->]
  /**************** CONVERSIONS ****************/
  Rtl_op_cvtIF,    /* convert integer to float   (unary) */
  Rtl_op_cvtID,    /* convert integer to double  (unary) */
  Rtl_op_cvtFI,    /* convert float   to integer (unary) */
  Rtl_op_cvtFD,    /* convert float   to double  (unary) */
  Rtl_op_cvtDI,    /* convert double  to integer (unary) */
  Rtl_op_cvtDF;    /* convert double  to float   (unary) */

Each of the following functions constructs an expression node from an operator and zero or more operands.

<prototypes of interface functions>+= (<-U) [<-D->]
Rtl_ty_expr Rtl_unary (Rtl_ty_oper oper, Rtl_ty_expr arg);
Rtl_ty_expr Rtl_binary(Rtl_ty_oper oper, Rtl_ty_expr left, Rtl_ty_expr right);
Rtl_ty_expr Rtl_apply (Rtl_ty_oper oper, Rtl_ty_expr arg1, ...);

Defines Rtl_apply, Rtl_binary, Rtl_unary (links are to index).

The oper argument is the operator. Rtl_apply() may be used for operators of any arity, but its argument list must be terminated by a NULL argument. Rtl_unary() and Rtl_binary() are for unary and binary operators, respectively; they provide better compile time checking and should suffice in most all cases. Use Rtl_apply() only if your operator has no operands [Note that for nullary operators, the value of the arg1 parameter is NULL.] or more than two operands. Rtl_unary(op, arg) is the same as Rtl_apply(op, arg, NULL) and Rtl_binary(op, left, right) is the same as Rtl_apply(op, left, right, NULL).

Location Node Generation Functions

The following function constructs a location node.

<prototypes of interface functions>+= (<-U) [<-D->]
Rtl_ty_loc Rtl_location(Rtl_ty_storage space, Rtl_ty_expr addr);

Defines Rtl_location (links are to index).

The space argument identifies the (machine-dependent) storage space in which the location is found. It indicates if the location is memory, a general-purpose register, a floating-point register, a special register, etc. The addr argument is the ``address'' of the location, which may be a traditional address, a register number, etc.

Storage spaces are represented by characters.

<type and value definitions>+= (<-U) [<-D]
typedef char Rtl_ty_storage;

Defines Rtl_ty_storage (links are to index).

In typical VPO optimizers, memory is 'm', hardware registers are 'r', and temporary pseudo registers are 't'. The full list of storage spaces for a particular optimizer is target-specific and may be found in the Processor Supplement.

For memory locations in VPO, addr is an expression node that evaluates to the memory address. For register locations in VPO, addr is an constant expression node that gives the register number.

The following convenience function constructs a ``constant location'', a location whose address is an integer constant.

<prototypes of interface functions>+= (<-U) [<-D->]
Rtl_ty_loc Rtl_constLoc(Rtl_ty_storage space, unsigned long addr);

Defines Rtl_constLoc (links are to index).

Rtl_constLoc(s, k) is the same as Rtl_location(s, Rtl_uint(k)).

Effect (RTL) Node Generation Functions

A RTL may be an assignment of an expression to a location, or an assignment with a guard expression, or a kill of a location, or a list of RTLs.

Assignment Effect

The following function constructs a RTL node that is an assignment of an expression node to a location node. The size argument is the number of bits being assigned.

<prototypes of interface functions>+= (<-U) [<-D->]
Rtl_ty_rtl Rtl_assign(Rtl_ty_loc loc, int size, Rtl_ty_expr expr);

Defines Rtl_assign (links are to index).

Guard Effect

The following function constructs a guard effect node. A guard consists of an expression and an assignment effect. If the expression evaluates to true, the assignment happens, otherwise nothing happens. Guarded effects are used to represent such instructions as conditional branches and predicated arithmetic.

<prototypes of interface functions>+= (<-U) [<-D->]
Rtl_ty_rtl Rtl_guard(Rtl_ty_expr expr,  Rtl_ty_rtl effect);

Defines Rtl_guard (links are to index).

Kill Effect

The following function constructs a kill effect, which indicates that one or more locations become undefined. A kill effect is usually a side effect of another RTL, so the other RTL and the kill RTL are typically joined with Rtl_list() below. The argument list must be terminated by a NULL argument.

<prototypes of interface functions>+= (<-U) [<-D->]
Rtl_ty_rtl Rtl_kill(Rtl_ty_loc loc1, ...);

Defines Rtl_kill (links are to index).

List of Effects

Some machine instructions cannot be represnted as single effects, e.g., they modify more than one location. Such instructions are represented by lists of effects (the L in RTL). The following function combines zero or more effects. (The combination of zero effects is the RTL way to write a no-op.) The argument list must be terminated by a NULL argument.

<prototypes of interface functions>+= (<-U) [<-D]
Rtl_ty_rtl Rtl_list(Rtl_ty_rtl rtl1, ... );

Defines Rtl_list (links are to index).

The resulting RTL denotes an instruction in which all the right-hand sides are evaluated, then all the assignments take place simultaneously. It is an unchecked run-time error to create an RTL in which two different effects may assign to the same location.

Example Usage

Let's construct the following RTL: t[5] = t[4] + 1. We need a few temporary variables.

<example>= [D->]
Rtl_ty_expr expr;
Rtl_ty_rtl  rtl;

Defines expr, rtl (links are to index).

We'll start on the right hand side of the assignment by fetching the contents of register t[4].

<example>+= [<-D->]
expr = Rtl_fetch(Rtl_constLoc('t', 4), 32);

The fetch is necessary to create a Rtl_ty_expr node; a Rtl_ty_loc node is not a legal operand for an operator.

Now we can add the constant 1 to it.

<example>+= [<-D->]
expr = Rtl_binary(Rtl_op_add, expr, Rtl_int(1));

We have completed the right hand side of the assignment. Let's finish the tree:

<example>+= [<-D]
rtl = Rtl_assign(Rtl_constLoc('t', 5), 32, expr);

Index of identifiers

expr: U1, U2, D3, U4, U5, U6
rtl: D1, U2
Rtl_apply: D1
Rtl_assign: U1, D2, U3
Rtl_binary: D1, U2
Rtl_const: D1
Rtl_constLoc: D1, U2, U3
Rtl_fetch: D1, U2, U3
Rtl_guard: D1
Rtl_int: D1, U2
Rtl_kill: D1
Rtl_list: D1
Rtl_location: D1
Rtl_relAddr: D1
Rtl_ty_const: U1, D2, U3
Rtl_ty_expr: U1, D2, U3, U4, U5, U6, U7, U8, U9, U10, U11
Rtl_ty_loc: U1, D2, U3, U4, U5, U6, U7
Rtl_ty_oper: D1, U2, U3, U4
Rtl_ty_relAddr: U1, D2, U3
Rtl_ty_rtl: U1, D2, U3, U4, U5, U6, U7
Rtl_ty_storage: U1, D2, U3
Rtl_uint: D1
Rtl_unary: D1

List of code chunks

<example>: D1, D2, D3, D4
<prototypes of interface functions>: U1, D2, D3, D4, D5, D6, D7, D8, D9, D10, D11, D12
<rtl.h>: D1
<type and value definitions>: U1, D2, D3, D4, D5, D6, D7, D8, D9, D10, D11

Intro RTL Creation Interface Assembly Language Interface VPO Code Generation Interface

This document is designed to be viewed using Cascading Style Sheets. If you can see this text, your browser does not support them. Please consider upgrading to Netscape 4, to Internet Explorer 3 or 4, or one of the other browsers recommended by the W3 Consortium.

Expressions
expr `Rtl_int(long n)`	Signed constant.
expr `Rtl_uint(unsigned long value)`	Unsigned constant.
expr `Rtl_const(`const `cnst)`	Machine-dependent constant.
expr `Rtl_relAddr(`relAddr `addr)`	Relocatable address.
expr `Rtl_fetch(`loc `loc, int size)`	Fetch.
expr `Rtl_apply(`oper `oper, ...)`	Apply an RTL operator of any arity.
expr `Rtl_unary(`oper `oper,` expr `arg)`	Apply a unary RTL operator.
expr `Rtl_binary(`oper `o,` expr `l,` expr `r)`	Apply a binary RTL operator.
Locations
loc `Rtl_location(`storage `s,` expr `addr)`	Location at an arbitrary address.
loc `Rtl_constLoc(`storage `s, long addr)`	Location at a a constant, known address.
Effects
rtl `Rtl_assign(`loc `l, int size,` expr `e)`	Store operation.
rtl `Rtl_guard(`expr `expr,` rtl `effect)`	Guarded (predicated) effect.
rtl `Rtl_kill(`loc `loc1, ...)`	Kill effect.
rtl `Rtl_list(`rtl `rtl1, ... )`	Simultaneous execution of multiple effects.