Subversion Repositories scarts

@c Copyright (c) 2004, 2005 Free Software Foundation, Inc.

@c Free Software Foundation, Inc.

@c This is part of the GCC manual.

@c For copying conditions, see the file gcc.texi.

@c ---------------------------------------------------------------------

@c Tree SSA

@c ---------------------------------------------------------------------

@node Tree SSA

@chapter Analysis and Optimization of GIMPLE Trees

@cindex Tree SSA

@cindex Optimization infrastructure for GIMPLE

GCC uses three main intermediate languages to represent the program

during compilation: GENERIC, GIMPLE and RTL@.  GENERIC is a

language-independent representation generated by each front end.  It

is used to serve as an interface between the parser and optimizer.

GENERIC is a common representation that is able to represent programs

written in all the languages supported by GCC@.

GIMPLE and RTL are used to optimize the program.  GIMPLE is used for

target and language independent optimizations (e.g., inlining,

constant propagation, tail call elimination, redundancy elimination,

etc).  Much like GENERIC, GIMPLE is a language independent, tree based

representation.  However, it differs from GENERIC in that the GIMPLE

grammar is more restrictive: expressions contain no more than 3

operands (except function calls), it has no control flow structures

and expressions with side-effects are only allowed on the right hand

side of assignments.  See the chapter describing GENERIC and GIMPLE

for more details.

This chapter describes the data structures and functions used in the

GIMPLE optimizers (also known as ``tree optimizers'' or ``middle

end'').  In particular, it focuses on all the macros, data structures,

functions and programming constructs needed to implement optimization

passes for GIMPLE@.

@menu

* GENERIC::             A high-level language-independent representation.

* GIMPLE::              A lower-level factored tree representation.

* Annotations::         Attributes for statements and variables.

* Statement Operands::  Variables referenced by GIMPLE statements.

* SSA::                 Static Single Assignment representation.

* Alias analysis::      Representing aliased loads and stores.

@end menu

@node GENERIC

@section GENERIC

@cindex GENERIC

The purpose of GENERIC is simply to provide a language-independent way of

representing an entire function in trees.  To this end, it was necessary to

add a few new tree codes to the back end, but most everything was already

there.  If you can express it with the codes in @code{gcc/tree.def}, it's

GENERIC@.

Early on, there was a great deal of debate about how to think about

statements in a tree IL@.  In GENERIC, a statement is defined as any

expression whose value, if any, is ignored.  A statement will always

have @code{TREE_SIDE_EFFECTS} set (or it will be discarded), but a

non-statement expression may also have side effects.  A

@code{CALL_EXPR}, for instance.

It would be possible for some local optimizations to work on the

GENERIC form of a function; indeed, the adapted tree inliner works

fine on GENERIC, but the current compiler performs inlining after

lowering to GIMPLE (a restricted form described in the next section).

Indeed, currently the frontends perform this lowering before handing

off to @code{tree_rest_of_compilation}, but this seems inelegant.

If necessary, a front end can use some language-dependent tree codes

in its GENERIC representation, so long as it provides a hook for

converting them to GIMPLE and doesn't expect them to work with any

(hypothetical) optimizers that run before the conversion to GIMPLE@.

The intermediate representation used while parsing C and C++ looks

very little like GENERIC, but the C and C++ gimplifier hooks are

perfectly happy to take it as input and spit out GIMPLE@.

@node GIMPLE

@section GIMPLE

@cindex GIMPLE

GIMPLE is a simplified subset of GENERIC for use in optimization.  The

particular subset chosen (and the name) was heavily influenced by the

SIMPLE IL used by the McCAT compiler project at McGill University,

though we have made some different choices.  For one thing, SIMPLE

doesn't support @code{goto}; a production compiler can't afford that

kind of restriction.

GIMPLE retains much of the structure of the parse trees: lexical

scopes are represented as containers, rather than markers.  However,

expressions are broken down into a 3-address form, using temporary

variables to hold intermediate values.  Also, control structures are

lowered to gotos.

In GIMPLE no container node is ever used for its value; if a

@code{COND_EXPR} or @code{BIND_EXPR} has a value, it is stored into a

temporary within the controlled blocks, and that temporary is used in

place of the container.

The compiler pass which lowers GENERIC to GIMPLE is referred to as the

@samp{gimplifier}.  The gimplifier works recursively, replacing complex

statements with sequences of simple statements.

@c Currently, the only way to

@c tell whether or not an expression is in GIMPLE form is by recursively

@c examining it; in the future there will probably be a flag to help avoid

@c redundant work.  FIXME FIXME

@menu

* Interfaces::

* Temporaries::

* GIMPLE Expressions::

* Statements::

* GIMPLE Example::

* Rough GIMPLE Grammar::

@end menu

@node Interfaces

@subsection Interfaces

@cindex gimplification

The tree representation of a function is stored in

@code{DECL_SAVED_TREE}.  It is lowered to GIMPLE by a call to

@code{gimplify_function_tree}.

If a front end wants to include language-specific tree codes in the tree

representation which it provides to the back end, it must provide a

definition of @code{LANG_HOOKS_GIMPLIFY_EXPR} which knows how to

convert the front end trees to GIMPLE@.  Usually such a hook will involve

much of the same code for expanding front end trees to RTL@.  This function

can return fully lowered GIMPLE, or it can return GENERIC trees and let the

main gimplifier lower them the rest of the way; this is often simpler.

The C and C++ front ends currently convert directly from front end

trees to GIMPLE, and hand that off to the back end rather than first

converting to GENERIC@.  Their gimplifier hooks know about all the

@code{_STMT} nodes and how to convert them to GENERIC forms.  There

was some work done on a genericization pass which would run first, but

the existence of @code{STMT_EXPR} meant that in order to convert all

of the C statements into GENERIC equivalents would involve walking the

entire tree anyway, so it was simpler to lower all the way.  This

might change in the future if someone writes an optimization pass

which would work better with higher-level trees, but currently the

optimizers all expect GIMPLE@.

A front end which wants to use the tree optimizers (and already has

some sort of whole-function tree representation) only needs to provide

a definition of @code{LANG_HOOKS_GIMPLIFY_EXPR}, call

@code{gimplify_function_tree} to lower to GIMPLE, and then hand off to

@code{tree_rest_of_compilation} to compile and output the function.

You can tell the compiler to dump a C-like representation of the GIMPLE

form with the flag @option{-fdump-tree-gimple}.

@node Temporaries

@subsection Temporaries

@cindex Temporaries

When gimplification encounters a subexpression which is too complex, it

creates a new temporary variable to hold the value of the subexpression,

and adds a new statement to initialize it before the current statement.

These special temporaries are known as @samp{expression temporaries}, and are

allocated using @code{get_formal_tmp_var}.  The compiler tries to

always evaluate identical expressions into the same temporary, to simplify

elimination of redundant calculations.

We can only use expression temporaries when we know that it will not be

reevaluated before its value is used, and that it will not be otherwise

modified@footnote{These restrictions are derived from those in Morgan 4.8.}.

Other temporaries can be allocated using

@code{get_initialized_tmp_var} or @code{create_tmp_var}.

Currently, an expression like @code{a = b + 5} is not reduced any

further.  We tried converting it to something like

@smallexample

  T1 = b + 5;

  a = T1;

@end smallexample

but this bloated the representation for minimal benefit.  However, a

variable which must live in memory cannot appear in an expression; its

value is explicitly loaded into a temporary first.  Similarly, storing

the value of an expression to a memory variable goes through a

temporary.

@node GIMPLE Expressions

@subsection Expressions

@cindex GIMPLE Expressions

In general, expressions in GIMPLE consist of an operation and the

appropriate number of simple operands; these operands must either be a

GIMPLE rvalue (@code{is_gimple_val}), i.e.@: a constant or a register

variable.  More complex operands are factored out into temporaries, so

that

@smallexample

  a = b + c + d

@end smallexample

becomes

@smallexample

  T1 = b + c;

  a = T1 + d;

@end smallexample

The same rule holds for arguments to a @code{CALL_EXPR}.

The target of an assignment is usually a variable, but can also be an

@code{INDIRECT_REF} or a compound lvalue as described below.

@menu

* Compound Expressions::

* Compound Lvalues::

* Conditional Expressions::

* Logical Operators::

@end menu

@node Compound Expressions

@subsubsection Compound Expressions

@cindex Compound Expressions

The left-hand side of a C comma expression is simply moved into a separate

statement.

@node Compound Lvalues

@subsubsection Compound Lvalues

@cindex Compound Lvalues

Currently compound lvalues involving array and structure field references

are not broken down; an expression like @code{a.b[2] = 42} is not reduced

any further (though complex array subscripts are).  This restriction is a

workaround for limitations in later optimizers; if we were to convert this

to

@smallexample

  T1 = &a.b;

  T1[2] = 42;

@end smallexample

alias analysis would not remember that the reference to @code{T1[2]} came

by way of @code{a.b}, so it would think that the assignment could alias

another member of @code{a}; this broke @code{struct-alias-1.c}.  Future

optimizer improvements may make this limitation unnecessary.

@node Conditional Expressions

@subsubsection Conditional Expressions

@cindex Conditional Expressions

A C @code{?:} expression is converted into an @code{if} statement with

each branch assigning to the same temporary.  So,

@smallexample

  a = b ? c : d;

@end smallexample

becomes

@smallexample

  if (b)

    T1 = c;

  else

    T1 = d;

  a = T1;

@end smallexample

Tree level if-conversion pass re-introduces @code{?:} expression, if appropriate.

It is used to vectorize loops with conditions using vector conditional operations.

Note that in GIMPLE, @code{if} statements are also represented using

@code{COND_EXPR}, as described below.

@node Logical Operators

@subsubsection Logical Operators

@cindex Logical Operators

Except when they appear in the condition operand of a @code{COND_EXPR},

logical `and' and `or' operators are simplified as follows:

@code{a = b && c} becomes

@smallexample

  T1 = (bool)b;

  if (T1)

    T1 = (bool)c;

  a = T1;

@end smallexample

Note that @code{T1} in this example cannot be an expression temporary,

because it has two different assignments.

@node Statements

@subsection Statements

@cindex Statements

Most statements will be assignment statements, represented by

@code{MODIFY_EXPR}.  A @code{CALL_EXPR} whose value is ignored can

also be a statement.  No other C expressions can appear at statement level;

a reference to a volatile object is converted into a @code{MODIFY_EXPR}.

In GIMPLE form, type of @code{MODIFY_EXPR} is not meaningful.  Instead, use type

of LHS or RHS@.

There are also several varieties of complex statements.

@menu

* Blocks::

* Statement Sequences::

* Empty Statements::

* Loops::

* Selection Statements::

* Jumps::

* Cleanups::

* GIMPLE Exception Handling::

@end menu

@node Blocks

@subsubsection Blocks

@cindex Blocks

Block scopes and the variables they declare in GENERIC and GIMPLE are

expressed using the @code{BIND_EXPR} code, which in previous versions of

GCC was primarily used for the C statement-expression extension.

Variables in a block are collected into @code{BIND_EXPR_VARS} in

declaration order.  Any runtime initialization is moved out of

@code{DECL_INITIAL} and into a statement in the controlled block.  When

gimplifying from C or C++, this initialization replaces the

@code{DECL_STMT}.

Variable-length arrays (VLAs) complicate this process, as their size often

refers to variables initialized earlier in the block.  To handle this, we

currently split the block at that point, and move the VLA into a new, inner

@code{BIND_EXPR}.  This strategy may change in the future.

@code{DECL_SAVED_TREE} for a GIMPLE function will always be a

@code{BIND_EXPR} which contains declarations for the temporary variables

used in the function.

A C++ program will usually contain more @code{BIND_EXPR}s than there are

syntactic blocks in the source code, since several C++ constructs have

implicit scopes associated with them.  On the other hand, although the C++

front end uses pseudo-scopes to handle cleanups for objects with

destructors, these don't translate into the GIMPLE form; multiple

declarations at the same level use the same @code{BIND_EXPR}.

@node Statement Sequences

@subsubsection Statement Sequences

@cindex Statement Sequences

Multiple statements at the same nesting level are collected into a

@code{STATEMENT_LIST}.  Statement lists are modified and traversed

using the interface in @samp{tree-iterator.h}.

@node Empty Statements

@subsubsection Empty Statements

@cindex Empty Statements

Whenever possible, statements with no effect are discarded.  But if they

are nested within another construct which cannot be discarded for some

reason, they are instead replaced with an empty statement, generated by

@code{build_empty_stmt}.  Initially, all empty statements were shared,

after the pattern of the Java front end, but this caused a lot of trouble in

practice.

An empty statement is represented as @code{(void)0}.

@node Loops

@subsubsection Loops

@cindex Loops

At one time loops were expressed in GIMPLE using @code{LOOP_EXPR}, but

now they are lowered to explicit gotos.

@node Selection Statements

@subsubsection Selection Statements

@cindex Selection Statements

A simple selection statement, such as the C @code{if} statement, is

expressed in GIMPLE using a void @code{COND_EXPR}.  If only one branch is

used, the other is filled with an empty statement.

Normally, the condition expression is reduced to a simple comparison.  If

it is a shortcut (@code{&&} or @code{||}) expression, however, we try to

break up the @code{if} into multiple @code{if}s so that the implied shortcut

is taken directly, much like the transformation done by @code{do_jump} in

the RTL expander.

A @code{SWITCH_EXPR} in GIMPLE contains the condition and a

@code{TREE_VEC} of @code{CASE_LABEL_EXPR}s describing the case values

and corresponding @code{LABEL_DECL}s to jump to.  The body of the

@code{switch} is moved after the @code{SWITCH_EXPR}.

@node Jumps

@subsubsection Jumps

@cindex Jumps

Other jumps are expressed by either @code{GOTO_EXPR} or @code{RETURN_EXPR}.

The operand of a @code{GOTO_EXPR} must be either a label or a variable

containing the address to jump to.

The operand of a @code{RETURN_EXPR} is either @code{NULL_TREE} or a

@code{MODIFY_EXPR} which sets the return value.  It would be nice to

move the @code{MODIFY_EXPR} into a separate statement, but the special

return semantics in @code{expand_return} make that difficult.  It may

still happen in the future, perhaps by moving most of that logic into

@code{expand_assignment}.

@node Cleanups

@subsubsection Cleanups

@cindex Cleanups

Destructors for local C++ objects and similar dynamic cleanups are

represented in GIMPLE by a @code{TRY_FINALLY_EXPR}.

@code{TRY_FINALLY_EXPR} has two operands, both of which are a sequence

of statements to execute.  The first sequence is executed.  When it

completes the second sequence is executed.

The first sequence may complete in the following ways:

@enumerate

@item Execute the last statement in the sequence and fall off the

end.

@item Execute a goto statement (@code{GOTO_EXPR}) to an ordinary

label outside the sequence.

@item Execute a return statement (@code{RETURN_EXPR}).

@item Throw an exception.  This is currently not explicitly represented in

GIMPLE.

@end enumerate

The second sequence is not executed if the first sequence completes by

calling @code{setjmp} or @code{exit} or any other function that does

not return.  The second sequence is also not executed if the first

sequence completes via a non-local goto or a computed goto (in general

the compiler does not know whether such a goto statement exits the

first sequence or not, so we assume that it doesn't).

After the second sequence is executed, if it completes normally by

falling off the end, execution continues wherever the first sequence

would have continued, by falling off the end, or doing a goto, etc.

@code{TRY_FINALLY_EXPR} complicates the flow graph, since the cleanup

needs to appear on every edge out of the controlled block; this

reduces the freedom to move code across these edges.  Therefore, the

EH lowering pass which runs before most of the optimization passes

eliminates these expressions by explicitly adding the cleanup to each

edge.  Rethrowing the exception is represented using @code{RESX_EXPR}.

@node GIMPLE Exception Handling

@subsubsection Exception Handling

@cindex GIMPLE Exception Handling

Other exception handling constructs are represented using

@code{TRY_CATCH_EXPR}.  @code{TRY_CATCH_EXPR} has two operands.  The

first operand is a sequence of statements to execute.  If executing

these statements does not throw an exception, then the second operand

is ignored.  Otherwise, if an exception is thrown, then the second

operand of the @code{TRY_CATCH_EXPR} is checked.  The second operand

may have the following forms:

@enumerate

@item A sequence of statements to execute.  When an exception occurs,

these statements are executed, and then the exception is rethrown.

@item A sequence of @code{CATCH_EXPR} expressions.  Each @code{CATCH_EXPR}

has a list of applicable exception types and handler code.  If the

thrown exception matches one of the caught types, the associated

handler code is executed.  If the handler code falls off the bottom,

execution continues after the original @code{TRY_CATCH_EXPR}.

@item An @code{EH_FILTER_EXPR} expression.  This has a list of

permitted exception types, and code to handle a match failure.  If the

thrown exception does not match one of the allowed types, the

associated match failure code is executed.  If the thrown exception

does match, it continues unwinding the stack looking for the next

handler.

@end enumerate

Currently throwing an exception is not directly represented in GIMPLE,

since it is implemented by calling a function.  At some point in the future

we will want to add some way to express that the call will throw an

exception of a known type.

Just before running the optimizers, the compiler lowers the high-level

EH constructs above into a set of @samp{goto}s, magic labels, and EH

regions.  Continuing to unwind at the end of a cleanup is represented

with a @code{RESX_EXPR}.

@node GIMPLE Example

@subsection GIMPLE Example

@cindex GIMPLE Example

@smallexample

struct A @{ A(); ~A(); @};

int i;

int g();

void f()

@{

  A a;

  int j = (--i, i ? 0 : 1);

  for (int x = 42; x > 0; --x)

    @{

      i += g()*4 + 32;

    @}

@}

@end smallexample

becomes

@smallexample

void f()

@{

  int i.0;

  int T.1;

  int iftmp.2;

  int T.3;

  int T.4;

  int T.5;

  int T.6;

  @{

    struct A a;

    int j;

    __comp_ctor (&a);

    try

      @{

        i.0 = i;

        T.1 = i.0 - 1;

        i = T.1;

        i.0 = i;

        if (i.0 == 0)

          iftmp.2 = 1;

        else

          iftmp.2 = 0;

        j = iftmp.2;

        @{

          int x;

          x = 42;

          goto test;

          loop:;

          T.3 = g ();

          T.4 = T.3 * 4;

          i.0 = i;

          T.5 = T.4 + i.0;

          T.6 = T.5 + 32;

          i = T.6;

          x = x - 1;

          test:;

          if (x > 0)

            goto loop;

          else

            goto break_;

          break_:;

        @}

      @}

    finally

      @{

        __comp_dtor (&a);

      @}

  @}

@}

@end smallexample

@node Rough GIMPLE Grammar

@subsection Rough GIMPLE Grammar

@cindex Rough GIMPLE Grammar

@smallexample

   function     : FUNCTION_DECL

                        DECL_SAVED_TREE -> compound-stmt

   compound-stmt: STATEMENT_LIST

                        members -> stmt

   stmt         : block

                | if-stmt

                | switch-stmt

                | goto-stmt

                | return-stmt

                | resx-stmt

                | label-stmt

                | try-stmt

                | modify-stmt

                | call-stmt

   block        : BIND_EXPR

                        BIND_EXPR_VARS -> chain of DECLs

                        BIND_EXPR_BLOCK -> BLOCK

                        BIND_EXPR_BODY -> compound-stmt

   if-stmt      : COND_EXPR

                        op0 -> condition

                        op1 -> compound-stmt

                        op2 -> compound-stmt

   switch-stmt  : SWITCH_EXPR

                        op0 -> val

                        op1 -> NULL

                        op2 -> TREE_VEC of CASE_LABEL_EXPRs

                            The CASE_LABEL_EXPRs are sorted by CASE_LOW,

                            and default is last.

   goto-stmt    : GOTO_EXPR

                        op0 -> LABEL_DECL | val

   return-stmt  : RETURN_EXPR

                        op0 -> return-value

   return-value : NULL

                | RESULT_DECL

                | MODIFY_EXPR

                        op0 -> RESULT_DECL

                        op1 -> lhs

   resx-stmt    : RESX_EXPR

   label-stmt   : LABEL_EXPR

                        op0 -> LABEL_DECL

   try-stmt     : TRY_CATCH_EXPR

                        op0 -> compound-stmt

                        op1 -> handler

                | TRY_FINALLY_EXPR

                        op0 -> compound-stmt

                        op1 -> compound-stmt

   handler      : catch-seq

                | EH_FILTER_EXPR

                | compound-stmt

   catch-seq    : STATEMENT_LIST

                        members -> CATCH_EXPR

   modify-stmt  : MODIFY_EXPR

                        op0 -> lhs

                        op1 -> rhs

   call-stmt    : CALL_EXPR

                        op0 -> val | OBJ_TYPE_REF

                        op1 -> call-arg-list

   call-arg-list: TREE_LIST

                        members -> lhs | CONST

   addr-expr-arg: ID

                | compref

   addressable  : addr-expr-arg

                | indirectref

   with-size-arg: addressable

                | call-stmt

   indirectref  : INDIRECT_REF

                        op0 -> val

   lhs          : addressable

                | bitfieldref

                | WITH_SIZE_EXPR

                        op0 -> with-size-arg

                        op1 -> val

   min-lval     : ID

                | indirectref

   bitfieldref  : BIT_FIELD_REF

                        op0 -> inner-compref

                        op1 -> CONST

                        op2 -> var

   compref      : inner-compref

                | TARGET_MEM_REF

                        op0 -> ID

                        op1 -> val

                        op2 -> val

                        op3 -> CONST

                        op4 -> CONST

                | REALPART_EXPR

                        op0 -> inner-compref

                | IMAGPART_EXPR

                        op0 -> inner-compref

   inner-compref: min-lval

                | COMPONENT_REF

                        op0 -> inner-compref

                        op1 -> FIELD_DECL

                        op2 -> val

                | ARRAY_REF

                        op0 -> inner-compref

                        op1 -> val

                        op2 -> val

                        op3 -> val

                | ARRAY_RANGE_REF

                        op0 -> inner-compref

                        op1 -> val

                        op2 -> val

                        op3 -> val

                | VIEW_CONVERT_EXPR

                        op0 -> inner-compref

   condition    : val

                | RELOP

                        op0 -> val

                        op1 -> val

   val          : ID

                | CONST

   rhs          : lhs

                | CONST

                | call-stmt

                | ADDR_EXPR

                        op0 -> addr-expr-arg

                | UNOP

                        op0 -> val

                | BINOP

                        op0 -> val

                        op1 -> val

                | RELOP

                        op0 -> val

                        op1 -> val

                | COND_EXPR

                        op0 -> condition

                        op1 -> val

                        op2 -> val

@end smallexample

@node Annotations

@section Annotations

@cindex annotations

The optimizers need to associate attributes with statements and

variables during the optimization process.  For instance, we need to

know what basic block a statement belongs to or whether a variable

has aliases.  All these attributes are stored in data structures

called annotations which are then linked to the field @code{ann} in

@code{struct tree_common}.

Presently, we define annotations for statements (@code{stmt_ann_t}),

variables (@code{var_ann_t}) and SSA names (@code{ssa_name_ann_t}).

Annotations are defined and documented in @file{tree-flow.h}.

@node Statement Operands

@section Statement Operands

@cindex operands

@cindex virtual operands

@cindex real operands

@findex update_stmt

Almost every GIMPLE statement will contain a reference to a variable

or memory location.  Since statements come in different shapes and

sizes, their operands are going to be located at various spots inside

the statement's tree.  To facilitate access to the statement's

operands, they are organized into lists associated inside each

statement's annotation.  Each element in an operand list is a pointer

to a @code{VAR_DECL}, @code{PARM_DECL} or @code{SSA_NAME} tree node.

This provides a very convenient way of examining and replacing

operands.

Data flow analysis and optimization is done on all tree nodes

representing variables.  Any node for which @code{SSA_VAR_P} returns

nonzero is considered when scanning statement operands.  However, not

all @code{SSA_VAR_P} variables are processed in the same way.  For the

purposes of optimization, we need to distinguish between references to

local scalar variables and references to globals, statics, structures,

arrays, aliased variables, etc.  The reason is simple, the compiler

can gather complete data flow information for a local scalar.  On the

other hand, a global variable may be modified by a function call, it

may not be possible to keep track of all the elements of an array or

the fields of a structure, etc.

The operand scanner gathers two kinds of operands: @dfn{real} and

@dfn{virtual}.  An operand for which @code{is_gimple_reg} returns true

is considered real, otherwise it is a virtual operand.  We also

distinguish between uses and definitions.  An operand is used if its

value is loaded by the statement (e.g., the operand at the RHS of an

assignment).  If the statement assigns a new value to the operand, the

operand is considered a definition (e.g., the operand at the LHS of

an assignment).

Virtual and real operands also have very different data flow

properties.  Real operands are unambiguous references to the

full object that they represent.  For instance, given

@smallexample

@{

  int a, b;

  a = b

@}

@end smallexample

Since @code{a} and @code{b} are non-aliased locals, the statement

@code{a = b} will have one real definition and one real use because

variable @code{b} is completely modified with the contents of

variable @code{a}.  Real definition are also known as @dfn{killing

definitions}.  Similarly, the use of @code{a} reads all its bits.

In contrast, virtual operands are used with variables that can have

a partial or ambiguous reference.  This includes structures, arrays,

globals, and aliased variables.  In these cases, we have two types of

definitions.  For globals, structures, and arrays, we can determine from

a statement whether a variable of these types has a killing definition.

If the variable does, then the statement is marked as having a

@dfn{must definition} of that variable.  However, if a statement is only

defining a part of the variable (i.e.@: a field in a structure), or if we

know that a statement might define the variable but we cannot say for sure,

then we mark that statement as having a @dfn{may definition}.  For

instance, given

@smallexample

@{

  int a, b, *p;

  if (...)

    p = &a;

  else

    p = &b;

  *p = 5;

  return *p;

@}

@end smallexample

The assignment @code{*p = 5} may be a definition of @code{a} or

@code{b}.  If we cannot determine statically where @code{p} is

pointing to at the time of the store operation, we create virtual

definitions to mark that statement as a potential definition site for

@code{a} and @code{b}.  Memory loads are similarly marked with virtual

use operands.  Virtual operands are shown in tree dumps right before

the statement that contains them.  To request a tree dump with virtual

operands, use the @option{-vops} option to @option{-fdump-tree}:

@smallexample

@{

  int a, b, *p;

  if (...)

    p = &a;

  else

    p = &b;

  # a = V_MAY_DEF <a>

  # b = V_MAY_DEF <b>

  *p = 5;

  # VUSE <a>

  # VUSE <b>

  return *p;

@}

@end smallexample

Notice that @code{V_MAY_DEF} operands have two copies of the referenced

variable.  This indicates that this is not a killing definition of

that variable.  In this case we refer to it as a @dfn{may definition}

or @dfn{aliased store}.  The presence of the second copy of the

variable in the @code{V_MAY_DEF} operand will become important when the

function is converted into SSA form.  This will be used to link all

the non-killing definitions to prevent optimizations from making

incorrect assumptions about them.

Operands are updated as soon as the statement is finished via a call

to @code{update_stmt}.  If statement elements are changed via

@code{SET_USE} or @code{SET_DEF}, then no further action is required

(ie, those macros take care of updating the statement).  If changes

are made by manipulating the statement's tree directly, then a call

must be made to @code{update_stmt} when complete.  Calling one of the

@code{bsi_insert} routines or @code{bsi_replace} performs an implicit

call to @code{update_stmt}.

@subsection Operand Iterators And Access Routines

@cindex Operand Iterators

@cindex Operand Access Routines

Operands are collected by @file{tree-ssa-operands.c}.  They are stored

inside each statement's annotation and can be accessed through either the

operand iterators or an access routine.

The following access routines are available for examining operands:

@enumerate

@item @code{SINGLE_SSA_@{USE,DEF,TREE@}_OPERAND}: These accessors will return

NULL unless there is exactly one operand matching the specified flags.  If

there is exactly one operand, the operand is returned as either a @code{tree},

@code{def_operand_p}, or @code{use_operand_p}.

@smallexample

tree t = SINGLE_SSA_TREE_OPERAND (stmt, flags);

use_operand_p u = SINGLE_SSA_USE_OPERAND (stmt, SSA_ALL_VIRTUAL_USES);

def_operand_p d = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_ALL_DEFS);

@end smallexample

@item @code{ZERO_SSA_OPERANDS}: This macro returns true if there are no

operands matching the specified flags.

@smallexample

if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))

  return;

@end smallexample

@item @code{NUM_SSA_OPERANDS}: This macro Returns the number of operands

matching 'flags'.  This actually executes a loop to perform the count, so

only use this if it is really needed.

@smallexample

int count = NUM_SSA_OPERANDS (stmt, flags)

@end smallexample

@end enumerate

If you wish to iterate over some or all operands, use the

@code{FOR_EACH_SSA_@{USE,DEF,TREE@}_OPERAND} iterator.  For example, to print

all the operands for a statement:

@smallexample

void

print_ops (tree stmt)

@{

  ssa_op_iter;

  tree var;

  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_OPERANDS)

    print_generic_expr (stderr, var, TDF_SLIM);

@}

@end smallexample

How to choose the appropriate iterator:

@enumerate

@item Determine whether you are need to see the operand pointers, or just the

    trees, and choose the appropriate macro: