@c Copyright (C) 1988, 1989, 1992, 1994, 1997, 1998, 1999, 2000, 2001
@c Free Software Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.

@node RTL
@chapter RTL Representation
@cindex RTL representation
@cindex representation of RTL
@cindex Register Transfer Language (RTL)

Most of the work of the compiler is done on an intermediate representation
called register transfer language.  In this language, the instructions to be
output are described, pretty much one by one, in an algebraic form that
describes what the instruction does.

RTL is inspired by Lisp lists.  It has both an internal form, made up of
structures that point at other structures, and a textual form that is used
in the machine description and in printed debugging dumps.  The textual
form uses nested parentheses to indicate the pointers in the internal form.

@menu
* RTL Objects::       Expressions vs vectors vs strings vs integers.
* RTL Classes::       Categories of RTL expression objects, and their structure.
* Accessors::         Macros to access expression operands or vector elts.
* Flags::             Other flags in an RTL expression.
* Machine Modes::     Describing the size and format of a datum.
* Constants::         Expressions with constant values.
* Regs and Memory::   Expressions representing register contents or memory.
* Arithmetic::        Expressions representing arithmetic on other expressions.
* Comparisons::       Expressions representing comparison of expressions.
* Bit-Fields::        Expressions representing bit-fields in memory or reg.
* Vector Operations:: Expressions involving vector datatypes.
* Conversions::       Extending, truncating, floating or fixing.
* RTL Declarations::  Declaring volatility, constancy, etc.
* Side Effects::      Expressions for storing in registers, etc.
* Incdec::            Embedded side-effects for autoincrement addressing.
* Assembler::         Representing @code{asm} with operands.
* Insns::             Expression types for entire insns.
* Calls::             RTL representation of function call insns.
* Sharing::           Some expressions are unique; others *must* be copied.
* Reading RTL::       Reading textual RTL from a file.
@end menu

@node RTL Objects
@section RTL Object Types
@cindex RTL object types

@cindex RTL integers
@cindex RTL strings
@cindex RTL vectors
@cindex RTL expression
@cindex RTX (See RTL)
RTL uses five kinds of objects: expressions, integers, wide integers,
strings and vectors.  Expressions are the most important ones.  An RTL
expression (``RTX'', for short) is a C structure, but it is usually
referred to with a pointer; a type that is given the typedef name
@code{rtx}.

An integer is simply an @code{int}; their written form uses decimal digits.
A wide integer is an integral object whose type is @code{HOST_WIDE_INT}
(@pxref{Config}); their written form uses decimal digits.

A string is a sequence of characters.  In core it is represented as a
@code{char *} in usual C fashion, and it is written in C syntax as well.
However, strings in RTL may never be null.  If you write an empty string in
a machine description, it is represented in core as a null pointer rather
than as a pointer to a null character.  In certain contexts, these null
pointers instead of strings are valid.  Within RTL code, strings are most
commonly found inside @code{symbol_ref} expressions, but they appear in
other contexts in the RTL expressions that make up machine descriptions.

A vector contains an arbitrary number of pointers to expressions.  The
number of elements in the vector is explicitly present in the vector.
The written form of a vector consists of square brackets
(@samp{[@dots{}]}) surrounding the elements, in sequence and with
whitespace separating them.  Vectors of length zero are not created;
null pointers are used instead.

@cindex expression codes
@cindex codes, RTL expression
@findex GET_CODE
@findex PUT_CODE
Expressions are classified by @dfn{expression codes} (also called RTX
codes).  The expression code is a name defined in @file{rtl.def}, which is
also (in upper case) a C enumeration constant.  The possible expression
codes and their meanings are machine-independent.  The code of an RTX can
be extracted with the macro @code{GET_CODE (@var{x})} and altered with
@code{PUT_CODE (@var{x}, @var{newcode})}.

The expression code determines how many operands the expression contains,
and what kinds of objects they are.  In RTL, unlike Lisp, you cannot tell
by looking at an operand what kind of object it is.  Instead, you must know
from its context---from the expression code of the containing expression.
For example, in an expression of code @code{subreg}, the first operand is
to be regarded as an expression and the second operand as an integer.  In
an expression of code @code{plus}, there are two operands, both of which
are to be regarded as expressions.  In a @code{symbol_ref} expression,
there is one operand, which is to be regarded as a string.

Expressions are written as parentheses containing the name of the
expression type, its flags and machine mode if any, and then the operands
of the expression (separated by spaces).

Expression code names in the @samp{md} file are written in lower case,
but when they appear in C code they are written in upper case.  In this
manual, they are shown as follows: @code{const_int}.

@cindex (nil)
@cindex nil
In a few contexts a null pointer is valid where an expression is normally
wanted.  The written form of this is @code{(nil)}.

@node RTL Classes
@section RTL Classes and Formats
@cindex RTL classes
@cindex classes of RTX codes
@cindex RTX codes, classes of
@findex GET_RTX_CLASS

The various expression codes are divided into several @dfn{classes},
which are represented by single characters.  You can determine the class
of an RTX code with the macro @code{GET_RTX_CLASS (@var{code})}.
Currently, @file{rtx.def} defines these classes:

@table @code
@item o
An RTX code that represents an actual object, such as a register
(@code{REG}) or a memory location (@code{MEM}, @code{SYMBOL_REF}).
Constants and basic transforms on objects (@code{ADDRESSOF},
@code{HIGH}, @code{LO_SUM}) are also included.  Note that @code{SUBREG}
and @code{STRICT_LOW_PART} are not in this class, but in class @code{x}.

@item <
An RTX code for a comparison, such as @code{NE} or @code{LT}.

@item 1
An RTX code for a unary arithmetic operation, such as @code{NEG},
@code{NOT}, or @code{ABS}.  This category also includes value extension
(sign or zero) and conversions between integer and floating point.

@item c
An RTX code for a commutative binary operation, such as @code{PLUS} or
@code{AND}.  @code{NE} and @code{EQ} are comparisons, so they have class
@code{<}.

@item 2
An RTX code for a non-commutative binary operation, such as @code{MINUS},
@code{DIV}, or @code{ASHIFTRT}.

@item b
An RTX code for a bit-field operation.  Currently only
@code{ZERO_EXTRACT} and @code{SIGN_EXTRACT}.  These have three inputs
and are lvalues (so they can be used for insertion as well).
@xref{Bit-Fields}.

@item 3
An RTX code for other three input operations.  Currently only
@code{IF_THEN_ELSE}.

@item i
An RTX code for an entire instruction:  @code{INSN}, @code{JUMP_INSN}, and
@code{CALL_INSN}. @xref{Insns}.

@item m
An RTX code for something that matches in insns, such as
@code{MATCH_DUP}.  These only occur in machine descriptions.

@item a
An RTX code for an auto-increment addressing mode, such as
@code{POST_INC}.

@item x
All other RTX codes.  This category includes the remaining codes used
only in machine descriptions (@code{DEFINE_*}, etc.).  It also includes
all the codes describing side effects (@code{SET}, @code{USE},
@code{CLOBBER}, etc.) and the non-insns that may appear on an insn
chain, such as @code{NOTE}, @code{BARRIER}, and @code{CODE_LABEL}.
@end table

@cindex RTL format
For each expression type @file{rtl.def} specifies the number of
contained objects and their kinds, with four possibilities: @samp{e} for
expression (actually a pointer to an expression), @samp{i} for integer,
@samp{w} for wide integer, @samp{s} for string, and @samp{E} for vector
of expressions.  The sequence of letters for an expression code is
called its @dfn{format}.  For example, the format of @code{subreg} is
@samp{ei}.@refill

@cindex RTL format characters
A few other format characters are used occasionally:

@table @code
@item u
@samp{u} is equivalent to @samp{e} except that it is printed differently
in debugging dumps.  It is used for pointers to insns.

@item n
@samp{n} is equivalent to @samp{i} except that it is printed differently
in debugging dumps.  It is used for the line number or code number of a
@code{note} insn.

@item S
@samp{S} indicates a string which is optional.  In the RTL objects in
core, @samp{S} is equivalent to @samp{s}, but when the object is read,
from an @samp{md} file, the string value of this operand may be omitted.
An omitted string is taken to be the null string.

@item V
@samp{V} indicates a vector which is optional.  In the RTL objects in
core, @samp{V} is equivalent to @samp{E}, but when the object is read
from an @samp{md} file, the vector value of this operand may be omitted.
An omitted vector is effectively the same as a vector of no elements.

@item 0
@samp{0} means a slot whose contents do not fit any normal category.
@samp{0} slots are not printed at all in dumps, and are often used in
special ways by small parts of the compiler.
@end table

There are macros to get the number of operands and the format
of an expression code:

@table @code
@findex GET_RTX_LENGTH
@item GET_RTX_LENGTH (@var{code})
Number of operands of an RTX of code @var{code}.

@findex GET_RTX_FORMAT
@item GET_RTX_FORMAT (@var{code})
The format of an RTX of code @var{code}, as a C string.
@end table

Some classes of RTX codes always have the same format.  For example, it
is safe to assume that all comparison operations have format @code{ee}.

@table @code
@item 1
All codes of this class have format @code{e}.

@item <
@itemx c
@itemx 2
All codes of these classes have format @code{ee}.

@item b
@itemx 3
All codes of these classes have format @code{eee}.

@item i
All codes of this class have formats that begin with @code{iuueiee}.
@xref{Insns}.  Note that not all RTL objects linked onto an insn chain
are of class @code{i}.

@item o
@itemx m
@itemx x
You can make no assumptions about the format of these codes.
@end table

@node Accessors
@section Access to Operands
@cindex accessors
@cindex access to operands
@cindex operand access

@findex XEXP
@findex XINT
@findex XWINT
@findex XSTR
Operands of expressions are accessed using the macros @code{XEXP},
@code{XINT}, @code{XWINT} and @code{XSTR}.  Each of these macros takes
two arguments: an expression-pointer (RTX) and an operand number
(counting from zero).  Thus,@refill

@example
XEXP (@var{x}, 2)
@end example

@noindent
accesses operand 2 of expression @var{x}, as an expression.

@example
XINT (@var{x}, 2)
@end example

@noindent
accesses the same operand as an integer.  @code{XSTR}, used in the same
fashion, would access it as a string.

Any operand can be accessed as an integer, as an expression or as a string.
You must choose the correct method of access for the kind of value actually
stored in the operand.  You would do this based on the expression code of
the containing expression.  That is also how you would know how many
operands there are.

For example, if @var{x} is a @code{subreg} expression, you know that it has
two operands which can be correctly accessed as @code{XEXP (@var{x}, 0)}
and @code{XINT (@var{x}, 1)}.  If you did @code{XINT (@var{x}, 0)}, you
would get the address of the expression operand but cast as an integer;
that might occasionally be useful, but it would be cleaner to write
@code{(int) XEXP (@var{x}, 0)}.  @code{XEXP (@var{x}, 1)} would also
compile without error, and would return the second, integer operand cast as
an expression pointer, which would probably result in a crash when
accessed.  Nothing stops you from writing @code{XEXP (@var{x}, 28)} either,
but this will access memory past the end of the expression with
unpredictable results.@refill

Access to operands which are vectors is more complicated.  You can use the
macro @code{XVEC} to get the vector-pointer itself, or the macros
@code{XVECEXP} and @code{XVECLEN} to access the elements and length of a
vector.

@table @code
@findex XVEC
@item XVEC (@var{exp}, @var{idx})
Access the vector-pointer which is operand number @var{idx} in @var{exp}.

@findex XVECLEN
@item XVECLEN (@var{exp}, @var{idx})
Access the length (number of elements) in the vector which is
in operand number @var{idx} in @var{exp}.  This value is an @code{int}.