path: root/gcc/cp/ir.texi

\input texinfo

@c ---------------------------------------------------------------------
@c This file is part of GNU CC.
@c 
@c GNU CC is free software; you can redistribute it and/or modify
@c it under the terms of the GNU General Public License as published by
@c the Free Software Foundation; either version 2, or (at your option)
@c any later version.
@c
@c GNU CC is distributed in the hope that it will be useful,
@c but WITHOUT ANY WARRANTY; without even the implied warranty of
@c MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
@c GNU General Public License for more details.
@c 
@c You should have received a copy of the GNU General Public License
@c along with GNU CC; see the file COPYING.  If not, write to
@c the Free Software Foundation, 59 Temple Place - Suite 330,
@c Boston, MA 02111-1307, USA.
@c ---------------------------------------------------------------------

@c ---------------------------------------------------------------------
@c Prologue
@c ---------------------------------------------------------------------

@setfilename ir.info
@settitle G++ Internal Representation
@setchapternewpage on

@ifinfo
This manual documents the internal representation used by G++ to represent
C++ source programs.

Copyright (c) 1999 Free Software Foundation, Inc.
@end ifinfo

@c ---------------------------------------------------------------------
@c Title page
@c ---------------------------------------------------------------------

@titlepage
@title G++ Internal Representation
@author CodeSourcery, LLC <info@@codesourcery.com>
@page
@vskip 0pt plus 1filll
Copyright @copyright{} 1999 Free Software Foundation, Inc.
@end titlepage

@c ---------------------------------------------------------------------
@c Top
@c ---------------------------------------------------------------------

@node Top
@top G++ Internal Representation

This manual documents the internal representation used by G++ to
represent C++ source programs.  When presented with a C++ source
program, G++ parses the program, performs semantic analysis (including
the generation of error messages), and then produces the internal
representation described here.  This representation contains a complete
representation for the entire translation unit provided as input to the
G++ front-end.  This representation is then typically processed by a
code-generator in order to produce machine code, but could also be used
in the creation of source browsers, intelligent editors, automatic
documentation generators, interpreters, and any other programs needing
the ability to process C++ code.

This manual explains the internal representation.  In particular, this
manual documents the internal representation for C++ source constructs,
and the macros, functions, and variables that can be used to access
these constructs.

If you are developing a ``back-end'', be it is a code-generator or some
other tool, that uses this representation, you may occasionally find
that you need to ask questions not easily answered by the functions and
macros available here.  If that situation occurs, it is quite likely
that G++ already supports the functionality you desire, but that the
interface is simply not documented here.  In that case, you should ask
the G++ maintainers (via mail to @url{mailto:gcc@@gcc.gnu.org}) about
documenting the functionality you require.  Similarly, if you find
yourself writing functions that do not deal directly with your back-end,
but instead might be useful to other people using the G++ front-end, you
should submit your patches for inclusion in G++.

@menu
* Deficiencies::        Topics net yet covered in this document.
* Overview::            All about @code{tree}s.
* Types::               Fundamental and aggregate types.        
* Scopes::              Namespaces and classes.
* Functions::           Overloading, function bodies, and linkage.
* Declarations::        Type declarations and variables.
* Expressions::         From @code{typeid} to @code{throw}.
* Node Index::          The various types of tree nodes.
* Function Index::      Functions and macros described in this manual.
* Concept Index::       Index.
@end menu

@c ---------------------------------------------------------------------
@c Deficiencies
@c ---------------------------------------------------------------------

@node Deficiencies
@chapter Deficiencies

There are many places in which this document is incomplet and incorrekt.
It is, as of yet, only @emph{preliminary} documentation.

@c ---------------------------------------------------------------------
@c Overview
@c ---------------------------------------------------------------------

@node Overview
@chapter Overview
@cindex tree
@findex TREE_CODE

The central data structure used by the internal representation is the
@code{tree}.  These nodes, while all of the C type @code{tree}, are of
many varieties.  A @code{tree} is a pointer type, but the object to
which it points may be of a variety of types.  From this point forward,
we will refer to trees in ordinary type, rather than in @code{this
font}, except when talking about the actual C type @code{tree}.

You can tell what kind of node a particular tree is by using the
@code{TREE_CODE} macro.  Many, many macros take a trees as input and
return trees as output.  However, most macros require a certain kinds of
tree node as input.  In other words, there is a type-system for trees,
but it is not reflected in the C type-system.

For safety, it is useful to configure G++ with @code{--enable-checking}.
Although this results in a significant performance penalty (since all
tree types are checked at run-time), and is therefore inappropriate in a
release version, it is extremely helpful during the development process.

Many macros behave as predicates.  Many, although not all, of these
predicates end in @samp{_P}.  Do not rely on the result type of these
macros being of any particular type.  You may, however, rely on the fact
that the type can be compared to @code{0}, so that statements like
@example
if (TEST_P (t) && !TEST_P (y))
  x = 1;
@end example
@noindent
and
@example
int i = (TEST_P (t) != 0);
@end example
@noindent
are legal.  Macros that return @code{int} values now may be changed to
return @code{tree} values, or other pointers in the future.  Even those
that continue to return @code{int} may return multiple non-zero codes
where previously they returned only zero and one.  Therefore, you should
not write code like
@example
if (TEST_P (t) == 1)
@end example
@noindent
as this code is not guaranteed to work correctly in the future.

You should not take the address of values returned by the macros or
functions described here.  In particular, no guarantee is given that the
values are lvalues.

In general, the names of macros are all in uppercase, while the names of
functions are entirely in lower case.  There are rare exceptions to this
rule.  You should assume that any macro or function whose name is made
up entirely of uppercase letters may evaluate its arguments more than
once.  You may assume that a macro or function whose name is made up
entirely of lowercase letters will evaluate its arguments only once.

The @code{error_mark_node} is a special tree.  Its tree code is
@code{ERROR_MARK}, but since there is only ever one node with that code,
the usual practice is to compare the tree against
@code{error_mark_node}.  (This test is just a test for pointer
equality.)  If an error has occurred during front-end processing the
flag @code{errorcount} will be set.  If the front-end has encountered
code it cannot handle, it will issue a message to the user and set
@code{sorrycount}.  When these flags are set, any macro or function
which normally returns a tree of a particular kind may instead return
the @code{error_mark_node}.  Thus, if you intend to do any processing of
erroneous code, you must be prepared to deal with the
@code{error_mark_node}.

Occasionally, a particular tree slot (like an operand to an expression,
or a particular field in a declaration) will be referred to as
``reserved for the back-end.''  These slots are used to store RTL when
the tree is converted to RTL for use by the GCC back-end.  However, if
that process is not taking place (e.g., if the front-end is being hooked
up to an intelligent editor), then those slots may be used by the
back-end presently in use.

If you encounter situations that do not match this documentation, such
as tree nodes of types not mentioned here, or macros documented to
return entities of a particular kind that instead return entities of
some different kind, you have found a bug, either in the front-end or in
the documentation.  Please report these bugs as you would any other
bug.

@menu
* Trees::               Macros and functions that can be used with all trees.
* Identifiers::         The names of things.
* Containers::          Lists and vectors.
@end menu

@c ---------------------------------------------------------------------
@c Trees
@c ---------------------------------------------------------------------

@node Trees
@section Trees
@cindex tree

This section is not here yet.

@c ---------------------------------------------------------------------
@c Identifiers
@c ---------------------------------------------------------------------

@node Identifiers
@section Identifiers
@cindex identifier
@cindex name
@tindex IDENTIFIER_NODE

An @code{IDENTIFIER_NODE} represents a slightly more general concept
that the standard C or C++ concept of identifier.  In particular, an
@code{IDENTIFIER_NODE} may contain a @samp{$}, or other extraordinary
characters.

There are never two distinct @code{IDENTIFIER_NODE}s representing the
same identifier.  Therefore, you may use pointer equality to compare
@code{IDENTIFIER_NODE}s, rather than using a routine like @code{strcmp}.

You can use the following macros to access identifiers:
@ftable @code
@item IDENTIFIER_POINTER
The string represented by the identifier, represented as a
@code{char*}.  This string is always @code{NUL}-terminated, and contains
no embedded @code{NUL} characters.

@item IDENTIFIER_LENGTH
The length of the string returned by @code{IDENTIFIER_POINTER}, not
including the trailing @code{NUL}.  This value of
@code{IDENTIFIER_POINTER (x)} is always the same as @code{strlen
(IDENTIFIER_POINTER (x))}.

@item IDENTIFIER_OPNAME_P
This predicate holds if the identifier represents the name of an
overloaded operator.  In this case, you should not depend on the
contents of either the @code{IDENTIFIER_POINTER} or the
@code{IDENTIFIER_LENGTH}.

@item IDENTIFIER_TYPENAME_P
This predicate holds if the identifier represents the name of a
user-defined conversion operator.  In this case, the @code{TREE_TYPE} of
the @code{IDENTIFIER_NODE} holds the type to which the conversion
operator converts.

@end ftable

@c ---------------------------------------------------------------------
@c Containers
@c ---------------------------------------------------------------------

@node Containers
@section Containers
@cindex container
@cindex list
@cindex vector
@tindex TREE_LIST
@tindex TREE_VEC
@findex TREE_PURPOSE
@findex TREE_VALUE
@findex TREE_VEC_LENGTH
@findex TREE_VEC_ELT

Two common container data structures can be represented directly with
tree nodes.  A @code{TREE_LIST} is a singly linked list containing two
trees per node.  These are the @code{TREE_PURPOSE} and @code{TREE_VALUE}
of each node.  (Often, the @code{TREE_PURPOSE} contains some kind of
tag, or additional information, while the @code{TREE_VALUE} contains the
majority of the payload.  In other cases, the @code{TREE_PURPOSE} is
simply @code{NULL_TREE}, while in still others both the
@code{TREE_PURPOSE} and @code{TREE_VALUE} are of equal stature.)  Given
one @code{TREE_LIST} node, the next node is found by following the
@code{TREE_CHAIN}.  If the @code{TREE_CHAIN} is @code{NULL_TREE}, then
you have reached the end of the list.

A @code{TREE_VEC} is a simple vector.  The @code{TREE_VEC_LENGTH} is an
integer (not a tree) giving the number of nodes in the vector.  The
nodes themselves are accessed using the @code{TREE_VEC_ELT} macro, which
takes two arguments.  The first is the @code{TREE_VEC} in question; the
second is an integer indicating which element in the vector is desired.
The elements are indexed from zero.

@c ---------------------------------------------------------------------
@c Types
@c ---------------------------------------------------------------------

@node Types
@chapter Types
@cindex type
@cindex pointer
@cindex reference
@cindex fundamental type
@cindex array
@tindex VOID_TYPE
@tindex INTEGER_TYPE
@tindex TYPE_MIN_VALUE
@tindex TYPE_MAX_VALUE
@tindex REAL_TYPE
@tindex COMPLEX_TYPE
@tindex ENUMERAL_TYPE
@tindex BOOLEAN_TYPE
@tindex POINTER_TYPE
@tindex REFERENCE_TYPE
@tindex FUNCTION_TYPE
@tindex METHOD_TYPE
@tindex ARRAY_TYPE
@tindex RECORD_TYPE
@tindex UNION_TYPE
@findex CP_TYPE_QUALS
@findex TYPE_UNQUALIFIED
@findex TYPE_QUAL_CONST
@findex TYPE_QUAL_VOLATILE
@findex TYPE_QUAL_RESTRICT
@cindex qualified type
@findex TYPE_SIZE
@findex TYPE_ALIGN
@findex TYPE_PRECISION
@findex TYPE_ARG_TYPES
@findex TYPE_METHOD_BASETYPE
@findex TYPE_PTRMEM_P

All C++ types have corresponding tree nodes.  However, you should not
assume that there is exactly one tree node corresponding to each C++
type.  There are often several.

For the most part, different kinds of types have different tree codes.
(For example, pointer types use a @code{POINTER_TYPE} code while arrays
use an @code{ARRAY_TYPE} code.)  However, pointers to member functions
use the @code{RECORD_TYPE} code.  Therefore, when writing a
@code{switch} statement that depends on the code associated with a
particular type, you should take care to handle pointers to member
functions under the @code{RECORD_TYPE} case label.

In C++, an array type is not qualified; rather the type of the array
elements is qualified.  This situation is reflected in the intermediate
representation.  The macros described here will always examine the
qualification of the underlying element type when applied to an array
type.  (If the element type is itself an array, then the recursion
continues until a non-array type is found, and the qualification of this
type is examined.)  So, for example, @code{CP_TYPE_CONST_P} will hold of
the type @code{const int ()[7]}, denoting an array of seven @code{int}s.

The following functions and macros deal with cv-qualification of types:
@ftable @code
@item CP_TYPE_QUALS
This macro returns the set of type qualifiers applied to this type.
This value is @code{TYPE_UNQUALIFIED} if no qualifiers have been
applied.  The @code{TYPE_QUAL_CONST} bit is set if the type is
@code{const}-qualified.  The @code{TYPE_QUAL_VOLATILE} bit is set if the
type is @code{volatile}-qualified.  The @code{TYPE_QUAL_RESTRICT} bit is
set if the type is @code{restrict}-qualified.

@item CP_TYPE_CONST_P
This macro holds if the type is @code{const}-qualified.

@item CP_TYPE_VOLATILE_P
This macro holds if the type is @code{volatile}-qualified.

@item CP_TYPE_RESTRICT_P
This macro holds if the type is @code{restrict}-qualified.

@item TYPE_MAIN_VARIANT
This macro returns the unqualified version of a type.  It may be applied
to an unqualified type, but it is not always the identity function in
that case.
@end ftable

A few other macros and functions are usable with all types:
@ftable @code
@item TYPE_SIZE
The number of bits required to represent the type, represented as an
@code{INTEGER_CST}.  For an incomplete type, @code{TYPE_SIZE} will be
@code{NULL_TREE}.

@item TYPE_ALIGN
The alignment of the type, in bits, represented as an @code{int}.

@item TYPE_NAME
This macro returns a declaration (in the form of a @code{TYPE_DECL}) for
the type.  (Note this macro does @emph{not} return a
@code{IDENTIFIER_NODE}, as you might expect, given its name!)  You can
look at the @code{DECL_NAME} of the @code{TYPE_DECL} to obtain the
actual name of the type.  The @code{TYPE_NAME} will be @code{NULL_TREE}
for a type that is not a builtin type, the result of a typedef, or a
named class type.

@item same_type_p
This predicate takes two types as input, and holds if they are the same
type.  For example, if one type is a @code{typedef} for the other, or
both are @code{typedef}s for the same type.  This predicate also holds if
the two trees given as input are simply copies of one another; i.e.,
there is no difference between them at the source level, but, for
whatever reason, a duplicate has been made in the representation.  You
should never use @code{==} (pointer equality) to compare types; always
use @code{same_type_p} instead.
@end ftable

Detailed below are the various kinds of types, and the macros that can
be used to access them.  Although other kinds of types are used
elsewhere in G++, the types described here are the only ones that you
will encounter while examining the intermediate representation.

@table @code
@item VOID_TYPE
Used to represent the @code{void} type.

@item INTEGER_TYPE
Used to represent the various integral types, including @code{char},
@code{short}, @code{int}, @code{long}, and @code{long long}.  This code
is not used for enumeration types, nor for the @code{bool} type.  Note
that GCC's @code{CHAR_TYPE} node is @emph{not} used to represent
@code{char}.  The @code{TYPE_PRECISION} is the number of bits used in
the representation, represented as an @code{unsigned int}.  (Note that
in the general case this is not the same value as @code{TYPE_SIZE};
suppose that there were a 24-bit integer type, but that alignment
requirements for the ABI required 32-bit alignment.  Then,
@code{TYPE_SIZE} would be an @code{INTEGER_CST} for 32, while
@code{TYPE_PRECISION} would be 24.)  The integer type is unsigned if
@code{TREE_UNSIGNED} holds; otherwise, it is signed.

The @code{TYPE_MIN_VALUE} is an @code{INTEGER_CST} for the smallest
integer that may be represented by this type.  Similarly, the
@code{TYPE_MAX_VALUE} is an @code{INTEGER_CST} for the largest integer
that may be represented by this type.

@item REAL_TYPE
Used to represent the @code{float}, @code{double}, and @code{long
double} types.  The number of bits in the floating-point representation
is given by @code{TYPE_PRECISION}, as in the @code{INTEGER_TYPE} case.

@item COMPLEX_TYPE
FIXME: The __complex__ extension is supported in G++.  Document.

@item ENUMERAL_TYPE
Used to represent an enumeration type.  The @code{TYPE_PRECISION} gives
(as an @code{int}), the number of bits used to represent the type.  If
there are no negative enumeration constants, @code{TREE_UNSIGNED} will
hold.  The minimum and maximum enumeration constants may be obtained
with @code{TYPE_MIN_VALUE} and @code{TYPE_MAX_VALUE}, respectively; each
of these macros returns an @code{INTEGER_CST}.

The actual enumeration constants themselves may be obtained by looking
at the @code{TYPE_VALUES}.  This macro will return a @code{TREE_LIST},
containing the constants.  The @code{TREE_PURPOSE} of each node will be
an @code{IDENTIFIER_NODE} giving the name of the constant; the
@code{TREE_VALUE} will be an @code{INTEGER_CST} giving the value
assigned to that constant.  These constants will appear in the order in
which they were declared.  The @code{TREE_TYPE} of each of these
constants will be the type of enumeration type itself.

@item BOOLEAN_TYPE
Used to represent the @code{bool} type.

@item POINTER_TYPE
Used to represent pointer types, and pointer to data member types.  The
@code{TREE_TYPE} gives the type to which this type points.  If the type
is a pointer to data member type, then @code{TYPE_PTRMEM_P} will hold.
For a pointer to data member type of the form @samp{T X::*},
@code{TYPE_PTRMEM_CLASS_TYPE} will be the type @code{X}, while
@code{TYPE_PTRMEM_POINTED_TO_TYPE} will be the type @code{T}.

@item REFERENCE_TYPE
Used to represent reference types.  The @code{TREE_TYPE} gives the type
to which this type refers.

@item FUNCTION_TYPE
Used to represent the type of non-member functions and of static member
functions.  The @code{TREE_TYPE} gives the return type of the function.
The @code{TYPE_ARG_TYPES} are a @code{TREE_LIST} of the argument types.
The @code{TREE_VALUE} of each node in this list is the type of the
corresponding argument; the @code{TREE_PURPOSE} is an expression for the
default argument value, if any.  If the last node in the list is
@code{void_list_node} (a @code{TREE_LIST} node whose @code{TREE_VALUE}
is the @code{void_type_node}), then functions of this type do not take
variable arguments.  Otherwise, they do take a variable number of
arguments.

@item METHOD_TYPE
Used to represent the type of a non-static member function.  Like a
@code{FUNCTION_TYPE}, the return type is given by the @code{TREE_TYPE}.
The type of @code{*this}, i.e., the class of which functions of this
type are a member, is given by the @code{TYPE_METHOD_BASETYPE}.  The
@code{TYPE_ARG_TYPES} is the parameter list, as for a
@code{FUNCTION_TYPE}, and includes the @code{this} argument.

@item ARRAY_TYPE
Used to represent array types.  The @code{TREE_TYPE} gives the type of
the elements in the array.  If the array-bound is present in the type,
the @code{TYPE_DOMAIN} is an @code{INTEGER_TYPE} whose
@code{TYPE_MIN_VALUE} and @code{TYPE_MAX_VALUE} will be the lower and
upper bounds of the array, respectively.  The @code{TYPE_MIN_VALUE} will
always be an @code{INTEGER_CST} for zero, while the
@code{TYPE_MAX_VALUE} will be one less than the number of elements in
the array, i.e., the highest value which may be used to index an element
in the array.

@item RECORD_TYPE
Used to represent @code{struct} and @code{class} types, as well as
pointers to member functions.  If @code{TYPE_PTRMEMFUNC_P} holds, then
this type is a pointer-to-member type.  In that case, the
@code{TYPE_PTRMEMFUNC_FN_TYPE} is a @code{POINTER_TYPE} pointing to a
@code{METHOD_TYPE}.  The @code{METHOD_TYPE} is the type of a function
pointed to by the pointer-to-member function.  If
@code{TYPE_PTRMEMFUNC_P} does not hold, this type is a class type.  For
more information, see @pxref{Classes}.

@item UNION_TYPE
Used to represent @code{union} types.  For more information, @pxref{Classes}.
@end table

There are variables whose values represent some of the basic types.
These include:
@table @code
@item void_type_node
A node for @code{void}.

@item integer_type_node
A node for @code{int}.

@item unsigned_type_node.
A node for @code{unsigned int}.

@item char_type_node.
A node for @code{char}.
@end table
@noindent
It may sometimes be useful to compare one of these variables with a type
in hand, using @code{same_type_p}.

@c ---------------------------------------------------------------------
@c Scopes
@c ---------------------------------------------------------------------

@node Scopes
@chapter Scopes
@cindex namespace, class, scope

The root of the entire intermediate representation is the variable
@code{global_namespace}.  This is the namespace specified with @code{::}
in C++ source code.  All other namespaces, types, variables, functions,
and so forth can be found starting with this namespace.

Besides namespaces, the other high-level scoping construct in C++ is the
class.  (Throughout this manual the term @dfn{class} is used to mean the
types referred to in the ANSI/ISO C++ Standard as classes; these include
types defined with the @code{class}, @code{struct}, and @code{union}
keywords.)

@menu
* Namespaces::          Member functions, types, etc.
* Classes::             Members, bases, friends, etc.
@end menu

@c ---------------------------------------------------------------------
@c Namespaces
@c ---------------------------------------------------------------------

@node Namespaces
@section Namespaces
@cindex namespace
@tindex NAMESPACE_DECL

A namespace is represented by a @code{NAMESPACE_DECL} node.

However, except for the fact that it is distinguished as the root of the
representation, the global namespace is no different from any other
namespace.  Thus, in what follows, we describe namespaces generally,
rather than the global namespace in particular.

The @code{::std} namespace, however, @emph{is} special, unless
@code{flag_honor_std} is set.  This variable is set by the use
@samp{-fhonor-std} (or an option that implies it, like
@samp{-fnew-abi}), when invoking G++.  When @code{flag_honor_std} is
set, the @code{std} namespace is just like any other namespace.  When
@code{flag_honor_std} is not set, however, the @code{::std} namespace is
treated as a synonym for the global namespace, thereby allowing users to
write code that will work with compilers that put the standard library
in the @code{::std} namespace, even though the library supplied with G++
does not do so, as of GCC 2.95.  The @code{std} namespace is represented
by the variable @code{std_node}.  Although @code{std_node} is a
@code{NAMESPACE_DECL}, it does not have all the fields required of a
real namespace, and the macros and functions described here do not work,
in general.  It is safest simply to ignore @code{std_node} should you
encounter it while examining the internal representation.  In
particular, you will encounter @code{std_node} while looking at the
members of the global namespace.  Just skip it without attempting to
examine its members.

The following macros and functions can be used on a @code{NAMESPACE_DECL}:

@ftable @code
@item DECL_NAME
This macro is used to obtain the @code{IDENTIFIER_NODE} corresponding to
the unqualified name of the name of the namespace (@pxref{Identifiers}).
The name of the global namespace is @samp{::}, even though in C++ the
global namespace is unnamed.  However, you should use comparison with
@code{global_namespace}, rather than @code{DECL_NAME} to determine
whether or not a namespaces is the global one.  An unnamed namespace
will have a @code{DECL_NAME} equal to @code{anonymous_namespace_name}.
Within a single translation unit, all unnamed namespaces will have the
same name.

@item DECL_CONTEXT
This macro returns the enclosing namespace.  The @code{DECL_CONTEXT} for
the @code{global_namespace} is @code{NULL_TREE}.

@item cp_namespace_decls
This function will return the declarations contained in the namespace,
including types, overloaded functions, other namespaces, and so forth.
If there are no declarations, this function will return
@code{NULL_TREE}.  The declarations are connected through their
@code{TREE_CHAIN} fields.  

Although most entries on this list will be declarations,
@code{TREE_LIST} nodes may also appear.  In this case, the
@code{TREE_VALUE} will be an @code{OVERLOAD}.  The value of the
@code{TREE_PURPOSE} is unspecified; back-ends should ignore this value.
As with the other kinds of declarations returned by
@code{cp_namespace_decls}, the @code{TREE_CHAIN} will point to the next
declaration in this list.

For more information on the kinds of declarations that can occur on this
list, @xref{Declarations}.  Some declarations will not appear on this
list.  In particular, no @code{FIELD_DECL}, @code{LABEL_DECL}, or
@code{PARM_DECL} nodes will appear here.

@end ftable

@c ---------------------------------------------------------------------
@c Classes
@c ---------------------------------------------------------------------

@node Classes
@section Classes
@cindex class
@tindex RECORD_TYPE
@tindex UNION_TYPE
@findex CLASSTYPE_DECLARED_CLASS
@findex TYPE_BINFO
@findex BINFO_TYPE
@findex TREE_VIA_PUBLIC
@findex TREE_VIA_PROTECTED
@findex TREE_VIA_PRIVATE
@findex TYPE_FIELDS
@findex TYPE_METHODS

A class type is represented by either a @code{RECORD_TYPE} or a
@code{UNION_TYPE}.  A class declared with the @code{union} tag is
represented by a @code{UNION_TYPE}, while classes declared with either
the @code{struct} or the @code{class} tag are represented by
@code{RECORD_TYPE}s.  You can use the @code{CLASSTYPE_DECLARED_CLASS}
macro to discern whether or not a particular type is a @code{class} as
opposed to a @code{struct}.  This macro will be true only for classes
declared with the @code{class} tag.

All non-function members are available on the @code{TYPE_FIELDS} list.
Given one member, the next can be found by following the
@code{TREE_CHAIN}.  You should not depend in any way on the order in
which fields appear on this list.  All nodes on this list will be
@samp{DECL} nodes. A @code{FIELD_DECL} is used to represent a non-static
data member, a @code{VAR_DECL} is used to represent a static data
member, and a @code{TYPE_DECL} is used to represent a type.  Note that
the @code{CONST_DECL} for an enumeration constant will appear on this
list, if the enumeration type was declared in the class.  (Of course,
the @code{TYPE_DECL} for the enumeration type will appear here as well.)
There are no entries for base classes on this list.  In particular,
there is no @code{FIELD_DECL} for the ``base-class portion'' of an
object.

The function members are available on the @code{TYPE_METHODS} list.
Again, subsequent members are found by following the @code{TREE_CHAIN}
field.  If a function is overloaded, each of the overloaded functions
appears; no @code{OVERLOAD} nodes appear on the @code{TYPE_METHODS}
list.  Implicitly declared functions (including default constructors,
copy constructors, assignment operators, and destructors) will appear on
this list as well.

Every class has an associated @dfn{binfo}, which can be obtained with
@code{TYPE_BINFO}.  Binfos are used to represent base-classes.  The
binfo given by @code{TYPE_BINFO} is the degenerate case, whereby every
class is considered to be its own base-class.  The base classes for a
particular binfo can be obtained with @code{BINFO_BASETYPES}.  These
base-classes are themselves binfos.  The class type associated with a
binfo is given by @code{BINFO_TYPE}.  It is always the case that
@code{BINFO_TYPE (TYPE_BINFO (x))} is the same type as @code{x}, up to
qualifiers.  However, it is not always the case that @code{TYPE_BINFO
(BINFO_TYPE (y))} is always the same binfo as @code{y}.  The reason is
that if @code{y} is a binfo representing a base-class @code{B} of a
derived class @code{D}, then @code{BINFO_TYPE (y)} will be @code{B}, and
@code{TYPE_INFO (BINFO_TYPE (y))} will be @code{B} as its own
base-class, rather than as a base-class of @code{D}.

The @code{BINFO_BASETYPES} is a @code{TREE_VEC} (@pxref{Containers}).
Base types appear in left-to-right order in this vector.  You can tell
whether or @code{public}, @code{protected}, or @code{private}
inheritance was used by using the @code{TREE_VIA_PUBLIC},
@code{TREE_VIA_PROTECTED}, and @code{TREE_VIA_PRIVATE} macros.  Each of
these macros takes a @code{BINFO} and is true if and only if the
indicated kind of inheritance was used.  If @code{TREE_VIA_VIRTUAL}
holds of a binfo, then its @code{BINFO_TYPE} was inherited from
virtually.

FIXME: Talk about @code{TYPE_NONCOPIED_PARTS}.

@c ---------------------------------------------------------------------
@c Declarations
@c ---------------------------------------------------------------------

@node Declarations
@chapter Declarations
@cindex declaration
@cindex variable
@cindex type declaration
@tindex LABEL_DECL
@tindex CONST_DECL
@tindex TYPE_DECL
@tindex VAR_DECL
@tindex PARM_DECL
@tindex FIELD_DECL
@tindex NAMESPACE_DECL
@tindex RESULT_DECL
@tindex TEMPLATE_DECL
@tindex THUNK_DECL
@findex THUNK_DELTA
@tindex USING_DECL
@findex DECL_INITIAL
@findex DECL_SIZE
@findex DECL_ALIGN
@findex DECL_EXTERNAL

This chapter covers the various kinds of declarations that appear in the
internal representation, except for declarations of functions
(represented by @code{FUNCTION_DECL} nodes), which are described in
@ref{Functions}.

Some macros can be used with any kind of declaration.  These include:
@ftable @code
@item DECL_NAME
This macro returns an @code{IDENTIFIER_NODE} giving the name of the
entity.

@item TREE_TYPE
This macro returns the type of the entity declared.

@item DECL_SOURCE_FILE
This macro returns the name of the file in which the entity was
declared, as a @code{char*}.  For an entity declared implicitly by the
compiler (like @code{__builtin_memcpy}), this will be the string
@code{"<internal>"}.

@item DECL_SOURCE_LINE
This macro returns the line number at which the entity was declared, as
an @code{int}.

@item DECL_ARTIFICIAL 
This predicate holds if the declaration was implicitly generated by the
compiler.  For example, this predicate will hold of an implicitly
declared member function, or of the @code{TYPE_DECL} implicitly
generated for a class type.  Recall that in C++ code like:
@example
struct S @{@};
@end example
@noindent
is roughly equivalent to C code like:
@example
struct S @{@};
typedef struct S S;
@end example
The implicitly generated @code{typedef} declaration is represented by a
@code{TYPE_DECL} for which @code{DECL_ARTIFICIAL} holds.
@end ftable

The various kinds of declarations include:
@table @code
@item LABEL_DECL
These nodes are used to represent labels in function bodies.  For more
information, see @ref{Functions}.  These nodes only appear in block
scopes.

@item CONST_DECL
These nodes are used to represent enumeration constants.  The value of
the constant is given by @code{DECL_INITIAL} which will be an
@code{INTEGER_CST} with the same type as the @code{TREE_TYPE} of the
@code{CONST_DECL}, i.e., an @code{ENUMERAL_TYPE}.

@item RESULT_DECL
These nodes represent the value returned by a function.  When a value is
assigned to a @code{RESULT_DECL}, that indicates that the value should
be returned, via bitwise copy, by the function.  You can use
@code{DECL_SIZE} and @code{DECL_ALIGN} on a @code{RESULT_DECL}, just as
with a @code{VAR_DECL}.

@item TYPE_DECL
These nodes represent @code{typedef} declarations.  The @code{TREE_TYPE}
is the type declared to have the name given by @code{DECL_NAME}.  In
some cases, there is no associated name.

@item VAR_DECL
These nodes represent variables with namespace or block scope, as well
as static data members.  The @code{DECL_SIZE} and @code{DECL_ALIGN} are
analogous to @code{TYPE_SIZE} and @code{TYPE_ALIGN}.  For a declaration,
you should always use the @code{DECL_SIZE} and @code{DECL_ALIGN} rather
than the @code{TYPE_SIZE} and @code{TYPE_ALIGN} given by the
@code{TREE_TYPE}, since special attributes may have been applied to the
variable to give it a particular size and alignment.

If this variable is initialized (but does not require a constructor),
the @code{DECL_INITIAL} will be an expression for the initializer.  The
initializer should be evaluated, and a bitwise copy into the variable
performed.  If the @code{DECL_INITIAL} is the @code{error_mark_node},
there is an initializer, but it is given by an explicit statement later
in the code; no bitwise copy is required.

@item PARM_DECL
Used to represent a parameter to a function.  Treat these nodes
similarly to @code{VAR_DECL} nodes.  These nodes only appear in the
@code{DECL_ARGUMENTS} for a @code{FUNCTION_DECL}.

The @code{DECL_ARG_TYPE} for a @code{PARM_DECL} is the type that will
actually be used when a value is passed to this function.  It may be a
wider type than the @code{TREE_TYPE} of the parameter; for example, the
ordinary type might be @code{short} while the @code{DECL_ARG_TYPE} is
@code{int}.

@item FIELD_DECL
These nodes represent non-static data members.  The @code{DECL_SIZE} and
@code{DECL_ALIGN} behave as for @code{VAR_DECL} nodes.  The
@code{DECL_FIELD_BITPOS} gives the first bit used for this field, as an
@code{INTEGER_CST}.  These values are indexed from zero, where zero
indicates the first bit in the object.

FIXME: Talk about bitfields.

@item NAMESPACE_DECL
@xref{Namespaces}.

@item TEMPLATE_DECL

These nodes are used to represent class, function, and variable (static
data member) templates.  The @code{DECL_TEMPLATE_SPECIALIZATIONS} are a
@code{TREE_LIST}.  The @code{TREE_VALUE} of each node in the lst is a
@code{TEMPLATE_DECL}s or @code{FUNCTION_DECL}s representing
specializations (including instantiations) of this template.  Back-ends
can safely ignore @code{TEMPLATE_DECL}s, but should examine
@code{FUNCTION_DECL} nodes on the specializations list just as they
would ordinary @code{FUNCTION_DECL} nodes.

@item THUNK_DECL

These nodes represent stub code that adjusts the @code{this} pointer and
then jumps to another function.  When the jumped-to function returns,
control is transferred directly to the caller, without returning to the
thunk.  The first parameter to the thunk is always the @code{this}
pointer; the thunk should add @code{THUNK_DELTA} to this value.  (The
@code{THUNK_DELTA} is an @code{int}, not an @code{INTEGER_CST}.)  Then,
the thunk should jump to the location given by @code{DECL_INITIAL}; this
will always be an expression for the address of a function.  

You can use @code{DECL_ASSEMBLER_NAME}, @code{TREE_PUBLIC}, and
@code{DECL_ARGUMENTS} with a @code{THUNK_DECL}, just as with a
@code{FUNCTION_DECL}.

@item USING_DECL

Back-ends can safely ignore these nodes.

@end table

@c ---------------------------------------------------------------------
@c Functions
@c ---------------------------------------------------------------------

@node Functions
@chapter Functions
@cindex function
@tindex FUNCTION_DECL
@tindex OVERLOAD
@findex OVL_CURRENT
@findex OVL_NEXT

A function is represented by a @code{FUNCTION_DECL} node.  A set of
overloaded functions is sometimes represented by a @code{OVERLOAD} node.

An @code{OVERLOAD} node is not a declaration, so none of the
@samp{DECL_} macros should be used on an @code{OVERLOAD}.  An
@code{OVERLOAD} node is similar to a @code{TREE_LIST}.  Use
@code{OVL_CURRENT} to get the function associated with an
@code{OVERLOAD} node; use @code{OVL_NEXT} to get the next
@code{OVERLOAD} node in the list of overloaded functions.  The macros
@code{OVL_CURRENT} and @code{OVL_NEXT} are actually polymorphic; you can
use them to work with @code{FUNCTION_DECL} nodes as well as with
overlods.  In the case of a @code{FUNCTION_DECL}, @code{OVL_CURRENT}
will always return the function itself, and @code{OVL_NEXT} will always
be @code{NULL_TREE}.

To determine the scope of a function, you can use the
@code{DECL_REAL_CONTEXT} macro.  This macro will return the class
(either a @code{RECORD_TYPE} or a @code{UNION_TYPE}) or namespace (a
@code{NAMESPACE_DECL}) of which the function is a member.  For a virtual
function, this macro returns the class in which the function was
actually defined, not the base class in which the virtual declaration
occurred.  If a friend function is defined in a class scope, the
@code{DECL_CLASS_CONTEXT} macro can be used to determine the class in
which it was defined.  For example, in
@example
class C @{ friend void f() @{@} @};
@end example
the @code{DECL_REAL_CONTEXT} for @code{f} will be the
@code{global_namespace}, but the @code{DECL_CLASS_CONTEXT} will be the
@code{RECORD_TYPE} for @code{C}.

@menu
* Function Basics::     Function names, linkage, and so forth.
* Function Bodies::     The statements that make up a function body.
@end menu

@c ---------------------------------------------------------------------
@c Function Basics
@c ---------------------------------------------------------------------

@node Function Basics
@section Function Basics
@cindex constructor
@cindex destructor
@cindex copy constructor
@cindex assignment operator
@cindex linkage
@findex DECL_NAME
@findex DECL_ASSEMBLER_NAME
@findex TREE_PUBLIC
@findex DECL_LINKONCE_P
@findex DECL_FUNCTION_MEMBER_P
@findex DECL_CONSTRUCTOR_P
@findex DECL_DESTRUCTOR_P
@findex DECL_OVERLOADED_OPERATOR_P
@findex DECL_CONV_FN_P
@findex DECL_ARTIFIICIAL

The following macros and functions can be used on a @code{FUNCTION_DECL}:
@ftable @code
@item DECL_NAME
This macro returns the unqualified name of the function, as an
@code{IDENTIFIER_NODE}.  For an instantiation of a function template,
the @code{DECL_NAME} is the unqualified name of the template, not
something like @code{f<int>}.  The value of @code{DECL_NAME} is
undefined when used on a constructor, destructor, overloaded operator,
or type-conversion operator, or any function that is implicitly
generated by the compiler.  See below for macros that can be used to
distinguish these cases.

@item DECL_ASSEMBLER_NAME
This macro returns the mangled name of the function, also an
@code{IDENTIFIER_NODE}.  This name does not contain leading underscores
on systems that prefix all identifiers with underscores.  The mangled
name is computed in the same way on all platforms; if special processing
is required to deal with the object file format used on a particular
platform, it is the responsibility of the back-end to perform those
modifications.  (Of course, the back-end should not modify
@code{DECL_ASSEMBLER_NAME} itself.)

@item DECL_EXTERNAL
This predicate holds if the function is undefined.

@item TREE_PUBLIC
This predicate holds if the function has external linkage.

@item DECL_LINKONCE_P
This macro holds if multiple copies of this function may be emitted in
various translation units.  It is the responsibility of the linker to
merge the various copies.  Template instantiations are the most common
example of functions for which @code{DECL_LINKONCE_P} holds; G++
instantiates needed templates in all translation units which require them,
and then relies on the linker to remove duplicate instantiations.

FIXME: This macro is not yet implemented.

@item DECL_FUNCTION_MEMBER_P
This macro holds if the function is a member of a class, rather than a
member of a namespace.

@item DECL_NONSTATIC_MEMBER_FUNCTION_P
This macro holds for a non-static member function.

@item DECL_CONSTRUCTOR_P
This macro holds if the function is a constructor.

@item DECL_DESTRUCTOR_P
This macro holds if the function is a destructor.

@item DECL_OVERLOADED_OPERATOR_P
This macro holds if the function is an overloaded operator.

@item DECL_CONV_FN_P
This macro holds if the function is a type-conversion operator.

@item DECL_ARTIFICIAL
This macro holds if the function was implicitly generated by the
compiler, rather than explicitly declared.  In addition to implicitly
generated class member functions, this macro holds for the special
functions created to implement static initialization and destruction, to
compute run-time type information, and so forth.

@item DECL_ARGUMENTS
This macro returns the @code{PARM_DECL} for the first argument to the
function.  Subsequent @code{PARM_DECL} nodes can be obtained by
following the @code{TREE_CHAIN} links.

@item DECL_RESULT
This macro returns the @code{RESULT_DECL} for the function.

@item TREE_TYPE
This macro returns the @code{FUNCTION_TYPE} or @code{METHOD_TYPE} for
the function.

@end ftable

@c ---------------------------------------------------------------------
@c Function Bodies
@c ---------------------------------------------------------------------

@node Function Bodies
@section Function Bodies
@cindex function body
@cindex statements
@tindex ASM_STMT
@findex ASM_STRING
@findex ASM_CV_QUAL
@findex ASM_INPUTS
@findex ASM_OUTPUTS
@findex ASM_CLOBBERS
@tindex BREAK_STMT
@tindex CLEANUP_STMT
@findex CLEANUP_DECL
@findex CLEANUP_EXPR
@tindex COMPOUND_STMT
@findex COMPOUND_BODY
@tindex CONTINUE_STMT
@tindex DECL_STMT
@findex DECL_STMT_DECL
@tindex DO_STMT
@findex DO_BODY
@findex DO_COND
@tindex EXPR_STMT
@findex EXPR_STMT_EXPR
@tindex FOR_STMT
@findex FOR_INIT_STMT
@findex FOR_COND
@findex FOR_EXPR
@findex FOR_BODY
@tindex GOTO_STMT
@findex GOTO_DESTINATION
@tindex HANDLER
@tindex IF_STMT
@findex IF_COND
@findex THEN_CLAUSE
@findex ELSE_CLAUSE
@tindex LABEL_STMT
@tindex LABEL_STMT_LABEL
@tindex RETURN_INIT
@tindex RETURN_STMT
@findex RETURN_EXPR
@tindex SCOPE_STMT
@findex SCOPE_BEGIN_P
@findex SCOPE_END_P
@findex SCOPE_NULLIFIED_P
@tindex START_CATCH_STMT
@findex START_CATCH_TYPE
@tindex SUBOBJECT
@findex SUBOBJECT_CLEANUP
@tindex SWITCH_STMT
@findex SWITCH_COND
@findex SWITCH_BODY
@tindex TRY_BLOCK
@findex TRY_STMTS
@findex TRY_HANDLERS
@findex HANDLER_PARMS
@findex HANDLER_BODY
@tindex WHILE_STMT
@findex WHILE_BODY
@findex WHILE_COND

A function that has a definition in the current translation unit will
have a non-NULL @code{DECL_INITIAL}.  However, back-ends should not make
use of the particular value given by @code{DECL_INITIAL}.

The @code{DECL_SAVED_TREE} macro will give the complete body of the
function.  This node will usually be a @code{COMPOUND_STMT} representing
the outermost block of the function, but it may also be a
@code{TRY_BLOCK} or a @code{RETURN_INIT}.

If the function has a function try-block, the @code{DECL_SAVED_TREE}
will be a @code{TRY_BLOCK}.  The @code{TRY_STMTS} will then be either a
@code{RETURN_INIT}, or a @code{COMPOUND_STMT}.

If the function uses the G++ ``named return value'' extension, meaning
that the function has been defined like:
@example
S f(int) return s @{...@}
@end example
the @code{DECL_SAVED_TREE} will be a @code{RETURN_INIT}.  The
@code{TREE_CHAIN} of the @code{RETURN_INIT} will be the
@code{COMPOUND_STMT} representing the body of the function.  There is
never a named returned value for a constructor.  FIXME: Document how the
@code{RETURN_INIT} can be used.

@subsection Statements

There are tree nodes corresponding to all of the source-level statement
constructs.  These are enumerated here, together with a list of the
various macros that can be used to obtain information about them.  There
are a few macros that can be used with all statements:

@ftable @code
@item STMT_LINENO
This macro returns the line number for the statement.  If the statement
spans multiple lines, this value will be the number of the first line on
which the statement occurs.  Although we mention @code{CASE_LABEL} below
as if it were a statement, they do not allow the use of
@code{STMT_LINENO}.  There is no way to obtain the line number for a
@code{CASE_LABEL}.

Statements do not contain information about
the file from which they came; that information is implicit in the
@code{FUNCTION_DECL} from which the statements originate.

@item STMT_IS_FULL_EXPR_P
In C++, statements normally constitute ``full expressions''; temporaries
created during a statement are destroyed when the statement is complete.
However, G++ sometimes represents expressions by statements; these
statements will not have @code{STMT_IS_FULL_EXPR_P} set.  Temporaries
created during such statements should be destroyed when the innermost
enclosing statement with @code{STMT_IS_FULL_EXPR_P} set is exited.

@end ftable

Here is the list of the various statement nodes, and the macros used to
access them.  This documentation describes the use of these nodes in
non-template functions (including instantiations of template functions).
In template functions, the same nodes are used, but sometimes in
slightly different ways.  

Many of the statements have substatements.  For example, a @code{while}
loop will have a body, which is itself a statement.  If the substatement
is @code{NULL_TREE}, it is considered equivalent to a statement
consisting of a single @code{;}, i.e., an expression statement in which
the expression has been omitted.  A substatement may in fact be a list
of statements, connected via their @code{TREE_CHAIN}s.  So, you should
always process the statement tree by looping over substatements, like
this:
@example
void process_stmt (stmt)
     tree stmt;
@{
  while (stmt)
    @{
      switch (TREE_CODE (stmt))
        @{
        case IF_STMT:
          process_stmt (THEN_CLAUSE (stmt));
          /* More processing here.  */
          break;
        
        ...
        @}

      stmt = TREE_CHAIN (stmt);
    @}
@}
@end example
In other words, while the @code{then} clause of an @code{if} statement
in C++ can be only one statement (although that one statement may be a
compound statement), the intermediate representation will sometimes use
several statements chained together.

@table @code
@item ASM_STMT

Used to represent an inline assembly statement.  For an inline assembly
statement like:
@example
asm ("mov x, y");
@end example
The @code{ASM_STRING} macro will return a @code{STRING_CST} node for
@code{"mov x, y"}.  If the original statement made use of G++'s
extended-assembly syntax, then @code{ASM_OUTPUTS},
@code{ASM_INPUTS}, and @code{ASM_CLOBBERS} will be the outputs, inputs,
and clobbers for the statement, represented as @code{STRING_CST} nodes.
The extended-assembly syntax looks like:
@example
asm ("fsinx %1,%0" : "=f" (result) : "f" (angle));
@end example
The first string is the @code{ASM_STRING}, containing the instruction
template.  The next two strings are the output and inputs, respectively;
this statement has no clobbers.  As this example indicates, ``plain''
assembly statements are merely a special case of extended assembly
statements; they have no cv-qualifiers, outputs, inputs, or clobbers.
All of the strings will be @code{NUL}-terminated, and will contain no
embedded @code{NUL}-characters.

If the assembly statement is declared @code{volatile}, or if the
statement was not an extended assembly statement, and is therefore
implicitly volatile, then the predicate @code{ASM_VOLATILE_P} will hold
of the @code{ASM_STMT}.

@item BREAK_STMT

Used to represent a @code{break} statement.  There are no additional
fields.

@item CASE_LABEL

Use to represent a @code{case} label, range of @code{case} labels, or a
@code{default} label.  If @code{CASE_LOW} is NULL_TREE, then this is a a
@code{default} label.  Otherwise, if @code{CASE_HIGH} is NULL_TREE, then
this is an ordinary @code{case} label.  In this case, @code{CASE_LOW} is
an expression giving the value of the label.  Both @code{CASE_LOW} and
@code{CASE_HIGH} are @code{INTEGER_CST} nodes.  These values will have
the same type as the condition expression in the switch statement.

Otherwise, if both @code{CASE_LOW} and @code{CASE_HIGH} are defined, the
statement is a range of case labels.  Such statements originate with the
G++ extension that allows users to write things of the form:
@example
case 2 ... 5:
@end example
The first value will be @code{CASE_LOW}, while the second will be
@code{CASE_HIGH}.

@item CLEANUP_STMT

Used to represent an action that should take place upon exit from the
enclosing scope.  Typically, these actions are calls to destructors for
local objects, but back-ends cannot rely on this fact.  If these nodes
are in fact representing such destructors, @code{CLEANUP_DECL} will be
the @code{VAR_DECL} destroyed.  Otherwise, @code{CLEANUP_DECL} will be
@code{NULL_TREE}.  In any case, the @code{CLEANUP_EXPR} is the
expression to execute.  The cleanups executed on exit from a scope
should be run in the reverse order of the order in which the associated
@code{CLEANUP_STMT}s were encountered.

@item COMPOUND_STMT

Used to represent a brace-enclosed block.  The first substatement is
given by @code{COMPOUND_BODY}.  Subsequent substatements are found by
following the @code{TREE_CHAIN} link from one substatement to the next.

@item CONTINUE_STMT

Used to represent a @code{continue} statement.  There are no additional
fields.

@item DECL_STMT

Used to represent a local declaration.  The @code{DECL_STMT_DECL} macro
can be used to obtain the entity declared.  This declaration may be a
@code{LABEL_DECL}, indicating that the label declared is a local label.
(As an extension, GCC allows the declaration of labels with scope.)

@item DO_STMT

Used to represent a @code{do} loop.  The body of the loop is given by
@code{DO_BODY} while the termination condition for the loop is given by
@code{DO_COND}.  The condition for a @code{do}-statement is always an
expression.

@item EXPR_STMT

Used to represent an expression statement.  Use @code{EXPR_STMT_EXPR} to
obtain the expression.

@item FOR_STMT

Used to represent a @code{for} statement.  The @code{FOR_INIT_STMT} is
the initialization statement for the loop.  The @code{FOR_COND} is the
termination condition.  The @code{FOR_EXPR} is the expression executed
right before the @code{FOR_COND} on each loop iteration; often, this
expression increments a counter.  The body of the loop is given by
@code{FOR_BODY}.  Note that @code{FOR_INIT_STMT} and @code{FOR_BODY}
return statements, while @code{FOR_COND} and @code{FOR_EXPR} return
expressions.

@item GOTO_STMT

Used to represent a @code{goto} statement.  The @code{GOTO_DESTINATION}
will usually be a @code{LABEL_DECL}.  However, if G++'s ``computed
goto'' extension has been used, the @code{GOTO_DESTINATION} will be an
arbitrary expression indicating the destination.  This expression will
always have pointer type.

@item IF_STMT

Used to represent an @code{if} statement.  The @code{IF_COND} is the
expression or statement used as the condition.  If the condition is a
statement, it will always be a @code{DECL_STMT}; the variable will then
be used as the condition.

The @code{THEN_CLAUSE} represents the statement given by the @code{then}
condition, while the @code{ELSE_CLAUSE} represents the statement given
by the @code{else} condition.

@item LABEL_STMT

Used to represent a label.  The @code{LABEL_DECL} declared by this
statement can be obtained with the @code{LABEL_STMT_LABEL} macro.  The
@code{IDENTIFIER_NODE} giving the name of the label can be obtained from
the @code{LABEL_DECL} with @code{DECL_NAME}.

@item RETURN_STMT

Used to represent a @code{return} statement.  The @code{RETURN_EXPR} is
the expression returned; it will be @code{NULL_TREE} if the statement
was just
@example
return;
@end example

@item SCOPE_STMT

A scope-statement represents the beginning or end of a scope.  If
@code{SCOPE_BEGIN_P} holds, this statement represents the beginning of a
scope; if @code{SCOPE_END_P} holds this statement represents the end of
a scope.  On exit from a scope, all cleanups from @code{CLEANUP_STMT}s
occurring in the scope must be run, in reverse order to the order in
which they were encountered.  If @code{SCOPE_NULLIFIED_P} holds of the
scope, back-ends should behave as if the @code{SCOPE_STMT} were not
present at all.

@item START_CATCH_STMT

These statements represent the location to which control is transferred
when an exception is thrown.  The @code{START_CATCH_TYPE} is the type of
exception that will be caught by this handler; it is equal (by pointer
equalit) to @code{CATCH_ALL_TYPE} if this handler is for all types.

@item SUBOBJECT

In a constructor, these nodes are used to mark the point at which a
subobject of @code{this} is fully constructed.  If, after this point, an
exception is thrown before the constructor finishes executing, the
@code{SUBOBJECT_CLEANUP} must be executed.  The cleanups must be
executed in the reverse order in which they appear.

@item SWITCH_STMT

Used to represent a @code{switch} statement.  The @code{SWITCH_COND} is
the expression on which the switch is occurring.  (It may be either a
statement, or an expression.)  The @code{SWITCH_BODY} is the body of the
switch statement.

@item TRY_BLOCK
Used to represent a @code{try} block.  The body of the try block is
given by @code{TRY_STMTS}.  Each of the catch blocks is a @code{HANDLER}
node.  The first handler is given by @code{TRY_HANDLERS}.  Subsequent
handlers are obtained by following the @code{TREE_CHAIN} link from one
handler to the next.  The body of the handler is given by
@code{HANDLER_BODY}.

If @code{CLEANUP_P} holds of the @code{TRY_BLOCK}, then the
@code{TRY_HANDLERS} will not be a @code{HANDLER} node.  Instead, it will
be an expression that should be executed if an exception is thrown in
the try block.  It must rethrow the exception after executing that code.
And, if an exception is thrown while the expression is executing,
@code{terminate} must be called.

@item WHILE_STMT

Used to represent a @code{while} loop.  The @code{WHILE_COND} is the
termination condition for the loop.  This condition may be either a
statement or an expression.  If the condition is a statement, it will
always be a @code{DECL_STMT}; see @code{IF_STMT} for more information.

The @code{WHILE_BODY} is the body of the loop.

@end table

@c ---------------------------------------------------------------------
@c Expressions
@c ---------------------------------------------------------------------

@node Expressions
@chapter Expressions
@cindex expression
@findex TREE_OPERAND
@tindex INTEGER_CST
@findex TREE_INT_CST_HIGH
@findex TREE_INT_CST_LOW
@findex tree_int_cst_lt
@findex tree_int_cst_equal
@tindex REAL_CST
@tindex STRING_CST
@findex TREE_STRING_LENGTH
@findex TREE_STRING_POINTER
@tindex PTRMEM_CST
@findex PTRMEM_CST_CLASS
@findex PTRMEM_CST_MEMBER
@tindex VAR_DECL
@tindex NEGATE_EXPR
@tindex BIT_NOT_EXPR
@tindex TRUTH_NOT_EXPR
@tindex ADDR_EXPR
@tindex INDIRECT_REF
@tindex FIX_TRUNC_EXPR
@tindex FLOAT_EXPR
@tindex NOP_EXPR
@tindex CONVERT_EXPR
@tindex THROW_EXPR
@tindex LSHIFT_EXPR
@tindex RSHIFT_EXPR
@tindex BIT_IOR_EXPR
@tindex BIT_XOR_EXPR
@tindex BIT_AND_EXPR
@tindex TRUTH_ANDIF_EXPR
@tindex TRUTH_ORIF_EXPR
@tindex TRUTH_AND_EXPR
@tindex TRUTH_OR_EXPR
@tindex TRUTH_XOR_EXPR
@tindex PLUS_EXPR
@tindex MINUS_EXPR
@tindex MULT_EXPR
@tindex TRUNC_DIV_EXPR
@tindex TRUNC_MOD_EXPR
@tindex RDIV_EXPR
@tindex LT_EXPR
@tindex LE_EXPR
@tindex GT_EXPR
@tindex GE_EXPR
@tindex EQ_EXPR
@tindex NE_EXPR
@tindex INIT_EXPR
@tindex MODIFY_EXPR
@tindex COMPONENT_REF
@tindex COMPOUND_EXPR
@tindex COND_EXPR
@tindex CALL_EXPR
@tindex CONSTRUCTOR
@tindex STMT_EXPR
@tindex ARRAY_REF

The internal representation for expressions is for the most part quite
straightforward.  However, there are a few facts that one must bear in
mind.  In particular, the expression ``tree'' is actually a directed
acyclic graph.  (For example there may be many references to the integer
constant zero throughout the source program; many of these will be
represented by the same expression node.)  You should not rely on
certain kinds of node being shared, nor should rely on certain kinds of
nodes being unshared.

The following macros can be used with all expression nodes:
@ftable @code
@item TREE_TYPE
Returns the type of the expression.  This value may not be precisely the
same type that would be given the expression in the original C++
program.
@end ftable

In what follows, some nodes that one might expect to always have type
@code{bool} are documented to have either integral or boolean type.  At
some point in the future, the C front-end may also make use of this same
intermediate representation, and at this point these nodes will
certainly have integral type.  The previous sentence is not meant to
imply that the C++ front-end does not or will not give these nodes
integral type.

Below, we list the various kinds of expression nodes.  Except where
noted otherwise, the operands to an expression are accessed using the
@code{TREE_OPERAND} macro.  For example, to access the first operand to
a binary plus expression @code{expr}, use:
@example
TREE_OPERAND (expr, 0)
@end example
@noindent
As this example indicates, the operands are zero-indexed.

The table below begins with constants, moves on to unary expressions,
then proceeds to binary expressions, and concludes with various other
kinds of expressions:
@table @code
@item INTEGER_CST
These nodes represent integer constants.  Note that the type of these
constants is obtained with @code{TREE_TYPE}; they are not always of type
@code{int}.  In particular, @code{char} constants are represented with
@code{INTEGER_CST} nodes.  The value of the integer constant @code{e} is
given by @example
((TREE_INT_CST_HIGH (e) << HOST_BITS_PER_WIDE_INT) 
+ TREE_INST_CST_LOW (e))
@end example
@noindent
HOST_BITS_PER_WIDE_INT is at least thirty-two on all platforms.  Both
@code{TREE_INT_CST_HIGH} and @code{TREE_INT_CST_LOW} return a
@code{HOST_WIDE_INT}.  The value of an @code{INTEGER_CST} is interpreted
as a signed or unsigned quantity depending on the type of the constant.
In general, the expression given above will overflow, so it should not
be used to calculate the value of the constant.

The variable @code{integer_zero_node} is a integer constant with value
zero.  Similarly, @code{integer_one_node} is an integer constant with
value one.  The @code{size_zero_node} and @code{size_one_node} variables
are analogous, but have type @code{size_t} rather than @code{int}.

The function @code{tree_int_cst_lt} is a predicate which holds if its
first argument is less than its second.  Both constants are assumed to
have the same signedness (i.e., either both should be signed or both
should be unsigned.)  The full width of the constant is used when doing
the comparison; the usual rules about promotions and conversions are
ignored.  Similarly, @code{tree_int_cst_equal} holds if the two
constants are equal.  The @code{tree_int_cst_sgn} function returns the
sign of a constant.  The value is @code{1}, @code{0}, or @code{-1}
according on whether the constant is greater than, equal to, or less
than zero.  Again, the signedness of the constant's type is taken into
account; an unsigned constant is never less than zero, no matter what
its bit-pattern.

@item REAL_CST

FIXME: Talk about how to obtain representations of this constant, do
comparisons, and so forth.

@item STRING_CST
These nodes represent string-constants.  The @code{TREE_STRING_LENGTH}
returns the length of the string, as an @code{int}.  The
@code{TREE_STRING_POINTER} is a @code{char*} containing the string
itself.  The string may not be @code{NUL}-terminated, and it may contain
embedded @code{NUL} characters.  Therefore, the
@code{TREE_STRING_LENGTH} includes the trailing @code{NUL} if it is
present.

FIXME: How are wide strings represented?

@item PTRMEM_CST
These nodes are used to represent pointer-to-member constants.  The
@code{PTRMEM_CST_CLASS} is the class type (either a @code{RECORD_TYPE}
or @code{UNION_TYPE} within which the pointer points), and the
@code{PTRMEM_CST_MEMBER} is the declaration for the pointed to object.
Note that the @code{DECL_CONTEXT} for the @code{PTRMEM_CST_MEMBER} is in
general different from from the @code{PTRMEM_CST_CLASS}.  For example,
given:
@example
struct B @{ int i; @};
struct D : public B @{@};
int D::*dp = &D::i;
@end example
@noindent
The @code{PTRMEM_CST_CLASS} for @code{&D::I} is @code{D}, even though
the @code{DECL_CONTEXT} for the @code{PTRMEM_CST_MEMBER} is @code{B},
since @code{B::I} is a member of @code{B}, not @code{D}.

@item VAR_DECL

These nodes represent variables, including static data members.  For
more information, @pxref{Declarations}.

@item NEGATE_EXPR
These nodes represent unary negation of the single operand, for both
integer and floating-point types.  The type of negation can be
determined by looking at the type of the expression.

@item BIT_NOT_EXPR
These nodes represent bitwise complement, and will always have integral
type.  The only operand is the value to be complemented.

@item TRUTH_NOT_EXPR
These nodes represent logical negation, and will always have integral
(or boolean) type.  The operand is the value being negated.

@item PREDECREMENT_EXPR
@itemx PREINCREMENT_EXPR
@itemx POSTDECREMENT_EXPR
@itemx POSTINCREMENT_EXPR
These nodes represent increment and decrement expressions.  The value of
the single operand is computed, and the operand incremented or
decremented.  In the case of @code{PREDECREMENT_EXPR} and
@code{PREINCREMENT_EXPR}, the value of the expression is the value
resulting after the increment or decrement; in the case of
@code{POSTDECREMENT_EXPR} and @code{POSTINCREMENT_EXPR} is the value
before the increment or decrement occurs.  The type of the operand, like
that of the result, will be either integral, boolean, or floating-point.

@item ADDR_EXPR
These nodes are used to represent the address of an object.  (These
expression will always have pointer or reference type.)  The operand may
be another expression, or it may be a declaration.

As an extension, G++ allows users to take the address of a label.  In
this case, the operand of the @code{ADDR_EXPR} will be a
@code{LABEL_DECL}.  The type of such an expression is @code{void*}.

@item INDIRECT_REF 
These nodes are used to represent the object pointed to by a pointer.
The operand is the pointer being dereferenced; it will always have
pointer or reference type.

@item FIX_TRUNC_EXPR
These nodes represent conversion of a floating-point value to an
integer.  The single operand will have a floating-point type, while the
the complete expression will have an integral (or boolean) type.  The
operand is rounded towards zero.

@item FLOAT_EXPR
These nodes represent conversion of an integral (or boolean) value to a
floating-point value.  The single operand will have integral type, while
the complete expression will have a floating-point type.  

FIXME: How is the operand supposed to be rounded?  Is this dependent on
-mieee?

@item NON_LVALUE_EXPR
These nodes indicate that their one and only operand is not an lvalue.
A back-end can treat these identically to the single operand.

@item NOP_EXPR
These nodes are used to represent conversions that do not require any
code-generation.  For example, conversion of a @code{char*} to an
@code{int*} does not require any code be generated; such a conversion is
represented by a @code{NOP_EXPR}.  The single operand is the expression
to be converted.  The conversion from a pointer to a reference is also
represented with a @code{NOP_EXPR}.

@item CONVERT_EXPR
These nodes are similar to @code{NOP_EXPR}s, but are used in those
situations where code may need to be generated.  For example, if an
@code{int*} is converted to an @code{int} code may need to be generated
on some platforms.  These nodes are never used for C++-specific
conversions, like conversions between pointers to different classes in
an inheritance hierarchy.  Any adjustments that need to be made in such
cases are always indicated explicitly.  Similarly, a user-defined
conversion is never represented by a @code{CONVERT_EXPR}; instead, the
function calls are made explicit.

@item THROW_EXPR
These nodes represent @code{throw} expressions.  The single operand is
an expression for the code that should be executed to throw the
exception.  However, there is one implicit action not represented in
that expression; namely the call to @code{__throw}.  This function takes
no arguments.  If @code{setjmp}/@code{longjmp} exceptions are used, the
function @code{__sjthrow} is called instead.  The normal G++ back-end
uses the function @code{emit_throw} to generate this code; you can
examine this function to see what needs to be done.

@item LSHIFT_EXPR
@itemx RSHIFT_EXPR
These nodes represent left and right shifts, respectively.  The first
operand is the value to shift; it will always be of integral type.  The
second operand is an expression for the number of bits by which to
shift.  Right shift should be treated as arithmetic, i.e., the
high-order bits should be zero-filled when the expression has unsigned
type and filled with the sign bit when the expression has signed type.

@item BIT_IOR_EXPR
@itemx BIT_XOR_EXPR
@itemx BIT_AND_EXPR
These nodes represent bitwise inclusive or, bitwise exclusive or, and
bitwise and, respectively.  Both operands will always have integral
type.

@item TRUTH_ANDIF_EXPR
@itemx TRUTH_ORIF_EXPR
These nodes represent logical and and logical or, respectively.  These
operators are not strict; i.e., the second operand is evaluated only if
the value of the expression is not determined by evaluation of the first
operand.  The type of the operands, and the result type, is always of
boolean or integral type.

@item TRUTH_AND_EXPR
@itemx TRUTH_OR_EXPR
@itemx TRUTH_XOR_EXPR
These nodes represent logical and, logical or, and logical exclusive or.
They are strict; both arguments are always evaluated.  There are no
corresponding operators in C++, but the front-end will sometimes
generate these expressions anyhow, if it can tell that strictness does
not matter.

@itemx PLUS_EXPR
@itemx MINUS_EXPR
@itemx MULT_EXPR
@itemx TRUNC_DIV_EXPR
@itemx TRUNC_MOD_EXPR
@itemx RDIV_EXPR
These nodes represent various binary arithmetic operations.
Respectively, these operations are addition, subtraction (of the second
operand from the first), multiplication, integer division, integer
remainder, and floating-point division.  The operands to the first three
of these may have either integral or floating type, but there will never
be case in which one operand is of floating type and the other is of
integral type.

The result of a @code{TRUNC_DIV_EXPR} is always rounded towards zero.
The @code{TRUNC_MOD_EXPR} of two operands @code{a} and @code{b} is
always @code{a - a/b} where the division is as if computed by a
@code{TRUNC_DIV_EXPR}.

@item ARRAY_REF
These nodes represent array accesses.  The first operand is the array;
the second is the index.  To calculate the address of the memory
accessed, you must scale the index by the size of the type of the array
elements.

@item EXACT_DIV_EXPR
Document.

@item LT_EXPR
@itemx LE_EXPR
@itemx GT_EXPR
@itemx GE_EXPR
@itemx EQ_EXPR
@itemx NE_EXPR

These nodes represent the less than, less than or equal to, greater
than, greater than or equal to, equal, and not equal comparison
operators.  The first and second operand with either be both of integral
type or both of floating type.  The result type of these expressions
will always be of integral or boolean type.

@item MODIFY_EXPR
These nodes represent assignment.  The left-hand side is the first
operand; the right-hand side is the second operand.  The left-hand side
will be a @code{VAR_DECL}, @code{INDIRECT_REF}, @code{COMPONENT_REF}, or
other lvalue.

These nodes are used to represent not only assignment with @samp{=} but
also compount assignments (like @samp{+=}), by reduction to @samp{=}
assignment.  In other words, the representation for @samp{i += 3} looks
just like that for @samp{i = i + 3}.

@item INIT_EXPR
These nodes are just like @code{MODIFY_EXPR}, but are used only when a
variable is initialized, rather than assigned to subsequently.

@item COMPONENT_REF
These nodes represent non-static data member accesses.  The first
operand is the object (rather than a pointer to it); the second operand
is the @code{FIELD_DECL} for the data member.

@item COMPOUND_EXPR
These nodes represent C or C++ comma-expressions.  The first operand is
an expression whose value is computed and thrown away prior to the
evaluation of the second operand.  The value of the entire expression is
the value of the second operand.

@item COND_EXPR
These nodes represent C or C++ @code{?:} expressions.  The first operand
is of boolean or integral type.  If it evaluates to a non-zero value,
the second operand should be evaluated, and returned as the value of the
expression.  Otherwise, the third operand is evaluated, and returned as
the value of the expression.  As a GNU extension, the middle operand of
the @code{?:} operator may be omitted in the source, like this:
@example
x ? : 3
@end example
@noindent
which is equivalent to 
@example
x ? x : 3
@end example
assuming that @code{x} is an expression without side-effects.  However,
in the case that the first operation causes side effects, the
side-effects occur only once.  Consumers of the internal representation
do not need to worry about this oddity; the second operand will be
always be present in the internal representation.

@item CALL_EXPR
These nodes are used to represent calls to functions, including
non-static member functions.  The first operand is a pointer to the
function to call; it is always an expresion whose type is a
@code{POINTER_TYPE}.  The second argument is a @code{TREE_LIST}.  The
arguments to the call appear left-to-right in the list.  The
@code{TREE_VALUE} of each list node contains the expression
corresponding to that argument.  (The value of @code{TREE_PURPOSE} for
these nodes is unspecified, and should be ignored.)  For non-static
member functions, there will be an operand corresponding to the
@code{this} pointer.  There will always be expressions corresponding to
all of the arguments, even if the function is declared with default
arguments and some arguments are not explicitly provided at the call
sites.

@item STMT_EXPR
These nodes are used to represent G++'s statement-expression extension.
The statement-expression extension allows code like this:
@example
int f() @{ return (@{ int j; j = 3; j + 7; @}); @}
@end example
In other words, an sequence of statements may occur where a single
expression would normally appear.  The @code{STMT_EXPR} node represents
such an expression.  The @code{STMT_EXPR_STMT} gives the statement
contained in the expression; this is always a @code{COMPOUND_STMT}.  The
value of the expression is the value of the last sub-statement in the
@code{COMPOUND_STMT}.

@item CONSTRUCTOR
These nodes represent the brace-enclosed initializers for a structure or
array.  The first operand is reserved for use by the back-end.  The
second operand is a @code{TREE_LIST}.  If the @code{TREE_TYPE} of the
@code{CONSTRUCTOR} is a @code{RECORD_TYPE} or @code{UNION_TYPE}, then
the @code{TREE_PURPOSE} of each node in the @code{TREE_LIST} will be a
@code{FIELD_DECL} and the @code{TREE_VALUE} of each node will be the
expression used to initialize that field.  You should not depend on the
fields appearing in any particular order, nor should you assume that all
fields will be represented.  Unrepresented fields may be assigned any
value.

If the @code{TREE_TYPE} of the @code{CONSTRUCTOR} is an
@code{ARRAY_TYPE}, then the @code{TREE_PURPOSE} of each element in the
@code{TREE_LIST} will be an @code{INTEGER_CST}.  This constant indicates
which element of the array (indexed from zero) is being assigned to;
again, the @code{TREE_VALUE} is the corresponding initializer.  If the
@code{TREE_PURPOSE} is @code{NULL_TREE}, then the initializer is for the
next available array element.

Conceptually, before any initialization is done, the entire area of
storage is initialized to zero.

@item SAVE_EXPR

FIXME: Describe.

@item TARGET_EXPR
A @code{TARGET_EXPR} represents a temporary object.  The first operand
is a @code{VAR_DECL} for the temporary variable.  The second operand is
the initializer for the temporary.  The initializer is evaluated, and
copied (bitwise) into the temporary.

Often, a @code{TARGET_EXPR} occurs on the right-hand side of an
assignment, or as the second operand to a comma-expression which is
itself the right-hand side of an assignment, etc.  In this case, we say
that the @code{TARGET_EXPR} is ``normal''; otherwise, we say it is
``orphaned''.  For a normal @code{TARGET_EXPR} the temporary variable
should be treated as an alias for the left-hand side of the assignment,
rather than as a new temporary variable.

The third operand to the @code{TARGET_EXPR}, if present, is a
cleanup-expression (i.e., destructor call) for the temporary.  If this
expression is orphaned, then this expression must be executed when the
statement containing this expression is complete.  These cleanups must
always be executed in the order opposite to that in which they were
encountered.  Note that if a temporary is created on one branch of a
conditional operator (i.e., in the second or third operand to a
@code{COND_EXPR}), the cleanup must be run only if that branch is
actually executed.

See @code{STMT_IS_FULL_EXPR_P} for more information about running these
cleanups.

@item AGGR_INIT_EXPR
An @code{AGGR_INIT_EXPR} represents the initialization as the return
value of a function call, or as the result of a constructor.  An
@code{AGGR_INIT_EXPR} will only appear as the second operand of a
@code{TARGET_EXPR}.  The first operand to the @code{AGGR_INIT_EXPR} is
the address of a function to call, just as in a @code{CALL_EXPR}.  The
second operand are the arguments to pass that function, as a
@code{TREE_LIST}, again in a manner similar to that of a
@code{CALL_EXPR}.  The value of the expression is that returned by the
function.

If @code{AGGR_INIT_VIA_CTOR_P} holds of the @code{AGGR_INIT_EXPR}, then
the initialization is via a constructor call.  The address of the third
operand of the @code{AGGR_INIT_EXPR}, which is always a @code{VAR_DECL},
is taken, and this value replaces the first argument in the argument
list.  In this case, the value of the expression is the @code{VAR_DECL}
given by the third operand to the @code{AGGR_INIT_EXPR}; constructors do
not return a value.

@end table

@c ---------------------------------------------------------------------
@c Node Index
@c ---------------------------------------------------------------------

@node Node Index
@unnumbered Node Index

@printindex tp

@c ---------------------------------------------------------------------
@c Function Index
@c ---------------------------------------------------------------------

@node Function Index
@unnumbered Function Index

@printindex fn

@c ---------------------------------------------------------------------
@c Concept Index
@c ---------------------------------------------------------------------

@node Concept Index
@unnumbered Concept Index

@printindex cp

@c ---------------------------------------------------------------------
@c Epilogue
@c ---------------------------------------------------------------------

@summarycontents
@contents
@contents
@bye