diff options
Diffstat (limited to 'gcc/doc/tree-ssa.texi')
| -rw-r--r-- | gcc/doc/tree-ssa.texi | 1189 |
1 files changed, 1189 insertions, 0 deletions
diff --git a/gcc/doc/tree-ssa.texi b/gcc/doc/tree-ssa.texi new file mode 100644 index 00000000000..56ccd6109c2 --- /dev/null +++ b/gcc/doc/tree-ssa.texi @@ -0,0 +1,1189 @@ +@c Copyright (c) 2004 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 @code{-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 + +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}. + +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 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}. When the controlled +block exits, the cleanup is run. + +@code{TRY_FINALLY_EXPR} complicates the flow graph, since the cleanup +needs to appear on every edge out of the controlled block; this +reduces our 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. + +@node GIMPLE Exception Handling +@subsubsection Exception Handling +@cindex GIMPLE Exception Handling + +Other exception handling constructs are represented using +@code{TRY_CATCH_EXPR}. The handler operand of a @code{TRY_CATCH_EXPR} +can be a normal statement to be executed if the controlled block throws an +exception, or it can have one of two special forms: + +@enumerate +@item A @code{CATCH_EXPR} executes its handler if the thrown exception + matches one of the allowed types. Multiple handlers can be + expressed by a sequence of @code{CATCH_EXPR} statements. +@item An @code{EH_FILTER_EXPR} executes its handler if the thrown + exception does not match one of the allowed types. +@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 -> block +block: + BIND_EXPR + BIND_EXPR_VARS -> DECL chain + BIND_EXPR_BLOCK -> BLOCK + BIND_EXPR_BODY + -> compound-stmt +compound-stmt: + COMPOUND_EXPR + op0 -> non-compound-stmt + op1 -> stmt +stmt: compound-stmt + | non-compound-stmt +non-compound-stmt: + block + | if-stmt + | switch-stmt + | jump-stmt + | label-stmt + | try-stmt + | modify-stmt + | call-stmt +if-stmt: + COND_EXPR + op0 -> condition + op1 -> stmt + op2 -> stmt +switch-stmt: + SWITCH_EXPR + op0 -> val + op1 -> NULL_TREE + op2 -> TREE_VEC of CASE_LABEL_EXPRs +jump-stmt: + GOTO_EXPR + op0 -> LABEL_DECL | '*' ID + | RETURN_EXPR + op0 -> modify-stmt + | NULL_TREE +label-stmt: + LABEL_EXPR + op0 -> LABEL_DECL +try-stmt: + TRY_CATCH_EXPR + op0 -> stmt + op1 -> handler + | TRY_FINALLY_EXPR + op0 -> stmt + op1 -> stmt +handler: + catch-seq + | EH_FILTER_EXPR + | stmt +catch-seq: + CATCH_EXPR + | COMPOUND_EXPR + op0 -> CATCH_EXPR + op1 -> catch-seq +modify-stmt: + MODIFY_EXPR + op0 -> lhs + op1 -> rhs +call-stmt: CALL_EXPR + op0 -> _DECL | '&' _DECL + op1 -> arglist +arglist: + NULL_TREE + | TREE_LIST + op0 -> val + op1 -> arglist + +varname : compref | _DECL +lhs: varname | '*' _DECL +pseudo-lval: _DECL | '*' _DECL +compref : + COMPONENT_REF + op0 -> compref | pseudo-lval + | ARRAY_REF + op0 -> compref | pseudo-lval + op1 -> val + +condition : val | val relop val +val : _DECL | CONST + +rhs: varname | CONST + | '*' _DECL + | '&' varname + | call_expr + | unop val + | val binop val + | '(' cast ')' val + +unop: '+' | '-' | '!' | '~' + +binop: relop | '-' | '+' | '/' | '*' + | '%' | '&' | '|' | '<<' | '>>' | '^' + +relop: All tree codes of class '<' +@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 does a statement belong 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 get_stmt_operands +@findex modify_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 arrays associated inside each +statement's annotation. Each element in an operand array 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 represent partial or ambiguous +references to a variable. 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 = VDEF <a> + # b = VDEF <b> + *p = 5; + + # VUSE <a> + # VUSE <b> + return *p; +@} +@end smallexample + +Notice that @code{VDEF} 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{VDEF} 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 collected by @file{tree-ssa-operands.c}. They are stored +inside each statement's annotation and can be accessed with +@code{DEF_OPS}, @code{USE_OPS}, @code{VDEF_OPS} and @code{VUSE_OPS}. +The following are all the accessor macros available to access USE +operands. To access all the other operand arrays, just change the +name accordingly: + +@defmac USE_OPS (@var{ann}) +Returns the array of operands used by the statement with annotation +@var{ann}. +@end defmac + +@defmac STMT_USE_OPS (@var{stmt}) +Alternate version of USE_OPS that takes the statement @var{stmt} as +input. +@end defmac + +@defmac NUM_USES (@var{ops}) +Return the number of USE operands in array @var{ops}. +@end defmac + +@defmac USE_OP_PTR (@var{ops}, @var{i}) +Return a pointer to the @var{i}th operand in array @var{ops}. +@end defmac + +@defmac USE_OP (@var{ops}, @var{i}) +Return the @var{i}th operand in array @var{ops}. +@end defmac + +The following function shows how to print all the operands of a given +statement: + +@smallexample +void +print_ops (tree stmt) +@{ + vuse_optype vuses; + vdef_optype vdefs; + def_optype defs; + use_optype uses; + stmt_ann_t ann; + size_t i; + + get_stmt_operands (stmt); + ann = stmt_ann (stmt); + + defs = DEF_OPS (ann); + for (i = 0; i < NUM_DEFS (defs); i++) + print_generic_expr (stderr, DEF_OP (defs, i), 0); + + uses = USE_OPS (ann); + for (i = 0; i < NUM_USES (uses); i++) + print_generic_expr (stderr, USE_OP (uses, i), 0); + + vdefs = VDEF_OPS (ann); + for (i = 0; i < NUM_VDEFS (vdefs); i++) + print_generic_expr (stderr, VDEF_OP (vdefs, i), 0); + + vuses = VUSE_OPS (ann); + for (i = 0; i < NUM_VUSES (vuses); i++) + print_generic_expr (stderr, VUSE_OP (vuses, i), 0); +@} +@end smallexample + +To collect the operands, you first need to call +@code{get_stmt_operands}. Since that is a potentially expensive +operation, statements are only scanned if they have been marked +modified by a call to @code{modify_stmt}. So, if your pass replaces +operands in a statement, make sure to call @code{modify_stmt}. + + +@node SSA +@section Static Single Assignment +@cindex SSA +@cindex static single assignment + +Most of the tree optimizers rely on the data flow information provided +by the Static Single Assignment (SSA) form. We implement the SSA form +as described in @cite{R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and +K. Zadeck. Efficiently Computing Static Single Assignment Form and the +Control Dependence Graph. ACM Transactions on Programming Languages +and Systems, 13(4):451-490, October 1991}. + +The SSA form is based on the premise that program variables are +assigned in exactly one location in the program. Multiple assignments +to the same variable create new versions of that variable. Naturally, +actual programs are seldom in SSA form initially because variables +tend to be assigned multiple times. The compiler modifies the program +representation so that every time a variable is assigned in the code, +a new version of the variable is created. Different versions of the +same variable are distinguished by subscripting the variable name with +its version number. Variables used in the right-hand side of +expressions are renamed so that their version number matches that of +the most recent assignment. + +We represent variable versions using @code{SSA_NAME} nodes. The +renaming process in @file{tree-ssa.c} wraps every real and +virtual operand with an @code{SSA_NAME} node which contains +the version number and the statement that created the +@code{SSA_NAME}. Only definitions and virtual definitions may +create new @code{SSA_NAME} nodes. + +Sometimes, flow of control makes it impossible to determine what is the +most recent version of a variable. In these cases, the compiler +inserts an artificial definition for that variable called +@dfn{PHI function} or @dfn{PHI node}. This new definition merges +all the incoming versions of the variable to create a new name +for it. For instance, + +@smallexample +if (...) + a_1 = 5; +else if (...) + a_2 = 2; +else + a_3 = 13; + +# a_4 = PHI <a_1, a_2, a_3> +return a_4; +@end smallexample + +Since it is not possible to determine which of the three branches +will be taken at runtime, we don't know which of @code{a_1}, +@code{a_2} or @code{a_3} to use at the return statement. So, the +SSA renamer creates a new version @code{a_4} which is assigned +the result of ``merging'' @code{a_1}, @code{a_2} and @code{a_3}. +Hence, PHI nodes mean ``one of these operands. I don't know +which''. + +The following macros can be used to examine PHI nodes + +@defmac PHI_RESULT (@var{phi}) +Returns the @code{SSA_NAME} created by PHI node @var{phi} (i.e., +@var{phi}'s LHS). +@end defmac + +@defmac PHI_NUM_ARGS (@var{phi}) +Returns the number of arguments in @var{phi}. This number is exactly +the number of incoming edges to the basic block holding @var{phi}@. +@end defmac + +@defmac PHI_ARG_ELT (@var{phi}, @var{i}) +Returns a tuple representing the @var{i}th argument of @var{phi}@. +Each element of this tuple contains an @code{SSA_NAME} @var{var} and +the incoming edge through which @var{var} flows. +@end defmac + +@defmac PHI_ARG_EDGE (@var{phi}, @var{i}) +Returns the incoming edge for the @var{i}th argument of @var{phi}. +@end defmac + +@defmac PHI_ARG_DEF (@var{phi}, @var{i}) +Returns the @code{SSA_NAME} for the @var{i}th argument of @var{phi}. +@end defmac + + +@subsection Preserving the SSA form +@findex vars_to_rename +@cindex preserving SSA form +Some optimization passes make changes to the function that +invalidate the SSA property. This can happen when a pass has +added new variables or changed the program so that variables that +were previously aliased aren't anymore. + +Whenever something like this happens, the affected variables must +be renamed into SSA form again. To do this, you should mark the +new variables in the global bitmap @code{vars_to_rename}. Once +your pass has finished, the pass manager will invoke the SSA +renamer to put the program into SSA once more. + +@subsection Examining @code{SSA_NAME} nodes +@cindex examining SSA_NAMEs + +The following macros can be used to examine @code{SSA_NAME} nodes + +@defmac SSA_NAME_DEF_STMT (@var{var}) +Returns the statement @var{s} that creates the @code{SSA_NAME} +@var{var}. If @var{s} is an empty statement (i.e., @code{IS_EMPTY_STMT +(@var{s})} returns @code{true}), it means that the first reference to +this variable is a USE or a VUSE@. +@end defmac + +@defmac SSA_NAME_VERSION (@var{var}) +Returns the version number of the @code{SSA_NAME} object @var{var}. +@end defmac + + +@subsection Walking use-def chains + +@deftypefn {Tree SSA function} void walk_use_def_chains (@var{var}, @var{fn}, @var{data}) + +Walks use-def chains starting at the @code{SSA_NAME} node @var{var}. +Calls function @var{fn} at each reaching definition found. Function +@var{FN} takes three arguments: @var{var}, its defining statement +(@var{def_stmt}) and a generic pointer to whatever state information +that @var{fn} may want to maintain (@var{data}). Function @var{fn} is +able to stop the walk by returning @code{true}, otherwise in order to +continue the walk, @var{fn} should return @code{false}. + +Note, that if @var{def_stmt} is a @code{PHI} node, the semantics are +slightly different. For each argument @var{arg} of the PHI node, this +function will: + +@enumerate +@item Walk the use-def chains for @var{arg}. +@item Call @code{FN (@var{arg}, @var{phi}, @var{data})}. +@end enumerate + +Note how the first argument to @var{fn} is no longer the original +variable @var{var}, but the PHI argument currently being examined. +If @var{fn} wants to get at @var{var}, it should call +@code{PHI_RESULT} (@var{phi}). +@end deftypefn + +@subsection Walking the dominator tree + +@deftypefn {Tree SSA function} void walk_dominator_tree (@var{walk_data}, @var{bb}) + +This function walks the dominator tree for the current CFG calling a +set of callback functions defined in @var{struct dom_walk_data} in +@file{domwalk.h}. The call back functions you need to define give you +hooks to execute custom code at various points during traversal: + +@enumerate +@item Once to initialize any local data needed while processing + @var{bb} and its children. This local data is pushed into an + internal stack which is automatically pushed and popped as the + walker traverses the dominator tree. + +@item Once before traversing all the statements in the @var{bb}. + +@item Once for every statement inside @var{bb}. + +@item Once after traversing all the statements and before recursing + into @var{bb}'s dominator children. + +@item It then recurses into all the dominator children of @var{bb}. + +@item After recursing into all the dominator children of @var{bb} it + can, optionally, traverse every statement in @var{bb} again + (i.e., repeating steps 2 and 3). + +@item Once after walking the statements in @var{bb} and @var{bb}'s + dominator children. At this stage, the block local data stack + is popped. +@end enumerate +@end deftypefn + +@node Alias analysis +@section Alias analysis +@cindex alias +@cindex flow-sensitive alias analysis +@cindex flow-insensitive alias analysis + +Alias analysis proceeds in 3 main phases: + +@enumerate +@item Points-to and escape analysis. + +This phase walks the use-def chains in the SSA web looking for +three things: + + @itemize @bullet + @item Assignments of the form @code{P_i = &VAR} + @item Assignments of the form P_i = malloc() + @item Pointers and ADDR_EXPR that escape the current function. + @end itemize + +The concept of `escaping' is the same one used in the Java world. +When a pointer or an ADDR_EXPR escapes, it means that it has been +exposed outside of the current function. So, assignment to +global variables, function arguments and returning a pointer are +all escape sites. + +This is where we are currently limited. Since not everything is +renamed into SSA, we lose track of escape properties when a +pointer is stashed inside a field in a structure, for instance. +In those cases, we are assuming that the pointer does escape. + +We use escape analysis to determine whether a variable is +call-clobbered. Simply put, if an ADDR_EXPR escapes, then the +variable is call-clobbered. If a pointer P_i escapes, then all +the variables pointed-to by P_i (and its memory tag) also escape. + +@item Compute flow-sensitive aliases + +We have two classes of memory tags. Memory tags associated with +the pointed-to data type of the pointers in the program. These +tags are called ``type memory tag'' (TMT). The other class are +those associated with SSA_NAMEs, called ``name memory tag'' (NMT). +The basic idea is that when adding operands for an INDIRECT_REF +*P_i, we will first check whether P_i has a name tag, if it does +we use it, because that will have more precise aliasing +information. Otherwise, we use the standard type tag. + +In this phase, we go through all the pointers we found in +points-to analysis and create alias sets for the name memory tags +associated with each pointer P_i. If P_i escapes, we mark +call-clobbered the variables it points to and its tag. + + +@item Compute flow-insensitive aliases + +This pass will compare the alias set of every type memory tag and +every addressable variable found in the program. Given a type +memory tag TMT and an addressable variable V@. If the alias sets +of TMT and V conflict (as computed by may_alias_p), then V is +marked as an alias tag and added to the alias set of TMT@. +@end enumerate + +For instance, consider the following function: + +@example +foo (int i) +@{ + int *p, *q, a, b; + + if (i > 10) + p = &a; + else + q = &b; + + *p = 3; + *q = 5; + a = b + 2; + return *p; +@} +@end example + +After aliasing analysis has finished, the type memory tag for +pointer @code{p} will have two aliases, namely variables @code{a} and +@code{b}. +Every time pointer @code{p} is dereferenced, we want to mark the +operation as a potential reference to @code{a} and @code{b}. + +@example +foo (int i) +@{ + int *p, a, b; + + if (i_2 > 10) + p_4 = &a; + else + p_6 = &b; + # p_1 = PHI <p_4(1), p_6(2)>; + + # a_7 = VDEF <a_3>; + # b_8 = VDEF <b_5>; + *p_1 = 3; + + # a_9 = VDEF <a_7> + # VUSE <b_8> + a_9 = b_8 + 2; + + # VUSE <a_9>; + # VUSE <b_8>; + return *p_1; +@} +@end example + +In certain cases, the list of may aliases for a pointer may grow +too large. This may cause an explosion in the number of virtual +operands inserted in the code. Resulting in increased memory +consumption and compilation time. + +When the number of virtual operands needed to represent aliased +loads and stores grows too large (configurable with @option{--param +max-aliased-vops}), alias sets are grouped to avoid severe +compile-time slow downs and memory consumption. The alias +grouping heuristic proceeds as follows: + +@enumerate +@item Sort the list of pointers in decreasing number of contributed +virtual operands. + +@item Take the first pointer from the list and reverse the role +of the memory tag and its aliases. Usually, whenever an +aliased variable Vi is found to alias with a memory tag +T, we add Vi to the may-aliases set for T@. Meaning that +after alias analysis, we will have: + +@smallexample +may-aliases(T) = @{ V1, V2, V3, ..., Vn @} +@end smallexample + +This means that every statement that references T, will get +@code{n} virtual operands for each of the Vi tags. But, when +alias grouping is enabled, we make T an alias tag and add it +to the alias set of all the Vi variables: + +@smallexample +may-aliases(V1) = @{ T @} +may-aliases(V2) = @{ T @} +... +may-aliases(Vn) = @{ T @} +@end smallexample + +This has two effects: (a) statements referencing T will only get +a single virtual operand, and, (b) all the variables Vi will now +appear to alias each other. So, we lose alias precision to +improve compile time. But, in theory, a program with such a high +level of aliasing should not be very optimizable in the first +place. + +@item Since variables may be in the alias set of more than one +memory tag, the grouping done in step (2) needs to be extended +to all the memory tags that have a non-empty intersection with +the may-aliases set of tag T@. For instance, if we originally +had these may-aliases sets: + +@smallexample +may-aliases(T) = @{ V1, V2, V3 @} +may-aliases(R) = @{ V2, V4 @} +@end smallexample + +In step (2) we would have reverted the aliases for T as: + +@smallexample +may-aliases(V1) = @{ T @} +may-aliases(V2) = @{ T @} +may-aliases(V3) = @{ T @} +@end smallexample + +But note that now V2 is no longer aliased with R@. We could +add R to may-aliases(V2), but we are in the process of +grouping aliases to reduce virtual operands so what we do is +add V4 to the grouping to obtain: + +@smallexample +may-aliases(V1) = @{ T @} +may-aliases(V2) = @{ T @} +may-aliases(V3) = @{ T @} +may-aliases(V4) = @{ T @} +@end smallexample + +@item If the total number of virtual operands due to aliasing is +still above the threshold set by max-alias-vops, go back to (2). +@end enumerate |