tree-ssa.texi

理解和实践操作系统的一本好书

@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 -> val

   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
                | invariant ADDR_EXPR
                        op0 -> addr-expr-arg
                | 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 (@dots{})
    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 (@dots{})
    p = &a;
  else
    p = &b;
  # a = VDEF <a>
  # b = VDEF <b>
  *p = 5;

  # VUSE <a>
  # VUSE <b>
  return *p;
@}