diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/doc/tree-ssa.texi')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/doc/tree-ssa.texi | 1723 |
1 files changed, 0 insertions, 1723 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/doc/tree-ssa.texi b/gcc-4.2.1-5666.3/gcc/doc/tree-ssa.texi deleted file mode 100644 index 4ed5a33f2..000000000 --- a/gcc-4.2.1-5666.3/gcc/doc/tree-ssa.texi +++ /dev/null @@ -1,1723 +0,0 @@ -@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. -GIMPLE that is not fully lowered is known as ``high GIMPLE'' and -consists of the IL before the pass @code{pass_lower_cf}. High GIMPLE -still contains lexical scopes and nested expressions, while low GIMPLE -exposes all of the implicit jumps for control expressions like -@code{COND_EXPR}. - -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}, -@code{RESULT_DECL}, 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 -(i.e., 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: - -@smallexample -Need Macro: ----- ------- -use_operand_p FOR_EACH_SSA_USE_OPERAND -def_operand_p FOR_EACH_SSA_DEF_OPERAND -tree FOR_EACH_SSA_TREE_OPERAND -@end smallexample - -@item You need to declare a variable of the type you are interested - in, and an ssa_op_iter structure which serves as the loop - controlling variable. - -@item Determine which operands you wish to use, and specify the flags of - those you are interested in. They are documented in - @file{tree-ssa-operands.h}: - -@smallexample -#define SSA_OP_USE 0x01 /* @r{Real USE operands.} */ -#define SSA_OP_DEF 0x02 /* @r{Real DEF operands.} */ -#define SSA_OP_VUSE 0x04 /* @r{VUSE operands.} */ -#define SSA_OP_VMAYUSE 0x08 /* @r{USE portion of V_MAY_DEFS.} */ -#define SSA_OP_VMAYDEF 0x10 /* @r{DEF portion of V_MAY_DEFS.} */ -#define SSA_OP_VMUSTDEF 0x20 /* @r{V_MUST_DEF definitions.} */ - -/* @r{These are commonly grouped operand flags.} */ -#define SSA_OP_VIRTUAL_USES (SSA_OP_VUSE | SSA_OP_VMAYUSE) -#define SSA_OP_VIRTUAL_DEFS (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF) -#define SSA_OP_ALL_USES (SSA_OP_VIRTUAL_USES | SSA_OP_USE) -#define SSA_OP_ALL_DEFS (SSA_OP_VIRTUAL_DEFS | SSA_OP_DEF) -#define SSA_OP_ALL_OPERANDS (SSA_OP_ALL_USES | SSA_OP_ALL_DEFS) -@end smallexample -@end enumerate - -So if you want to look at the use pointers for all the @code{USE} and -@code{VUSE} operands, you would do something like: - -@smallexample - use_operand_p use_p; - ssa_op_iter iter; - - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, (SSA_OP_USE | SSA_OP_VUSE)) - @{ - process_use_ptr (use_p); - @} -@end smallexample - -The @code{TREE} macro is basically the same as the @code{USE} and -@code{DEF} macros, only with the use or def dereferenced via -@code{USE_FROM_PTR (use_p)} and @code{DEF_FROM_PTR (def_p)}. Since we -aren't using operand pointers, use and defs flags can be mixed. - -@smallexample - tree var; - ssa_op_iter iter; - - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_VUSE | SSA_OP_VMUSTDEF) - @{ - print_generic_expr (stderr, var, TDF_SLIM); - @} -@end smallexample - -@code{V_MAY_DEF}s are broken into two flags, one for the -@code{DEF} portion (@code{SSA_OP_VMAYDEF}) and one for the USE portion -(@code{SSA_OP_VMAYUSE}). If all you want to look at are the -@code{V_MAY_DEF}s together, there is a fourth iterator macro for this, -which returns both a def_operand_p and a use_operand_p for each -@code{V_MAY_DEF} in the statement. Note that you don't need any flags for -this one. - -@smallexample - use_operand_p use_p; - def_operand_p def_p; - ssa_op_iter iter; - - FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter) - @{ - my_code; - @} -@end smallexample - -@code{V_MUST_DEF}s are broken into two flags, one for the -@code{DEF} portion (@code{SSA_OP_VMUSTDEF}) and one for the kill portion -(@code{SSA_OP_VMUSTKILL}). If all you want to look at are the -@code{V_MUST_DEF}s together, there is a fourth iterator macro for this, -which returns both a def_operand_p and a use_operand_p for each -@code{V_MUST_DEF} in the statement. Note that you don't need any flags for -this one. - -@smallexample - use_operand_p kill_p; - def_operand_p def_p; - ssa_op_iter iter; - - FOR_EACH_SSA_MUSTDEF_OPERAND (def_p, kill_p, stmt, iter) - @{ - my_code; - @} -@end smallexample - - -There are many examples in the code as well, as well as the -documentation in @file{tree-ssa-operands.h}. - -There are also a couple of variants on the stmt iterators regarding PHI -nodes. - -@code{FOR_EACH_PHI_ARG} Works exactly like -@code{FOR_EACH_SSA_USE_OPERAND}, except it works over @code{PHI} arguments -instead of statement operands. - -@smallexample -/* Look at every virtual PHI use. */ -FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_VIRTUAL_USES) -@{ - my_code; -@} - -/* Look at every real PHI use. */ -FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_USES) - my_code; - -/* Look at every every PHI use. */ -FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_ALL_USES) - my_code; -@end smallexample - -@code{FOR_EACH_PHI_OR_STMT_@{USE,DEF@}} works exactly like -@code{FOR_EACH_SSA_@{USE,DEF@}_OPERAND}, except it will function on -either a statement or a @code{PHI} node. These should be used when it is -appropriate but they are not quite as efficient as the individual -@code{FOR_EACH_PHI} and @code{FOR_EACH_SSA} routines. - -@smallexample -FOR_EACH_PHI_OR_STMT_USE (use_operand_p, stmt, iter, flags) - @{ - my_code; - @} - -FOR_EACH_PHI_OR_STMT_DEF (def_operand_p, phi, iter, flags) - @{ - my_code; - @} -@end smallexample - -@subsection Immediate Uses -@cindex Immediate Uses - -Immediate use information is now always available. Using the immediate use -iterators, you may examine every use of any @code{SSA_NAME}. For instance, -to change each use of @code{ssa_var} to @code{ssa_var2} and call fold_stmt on -each stmt after that is done: - -@smallexample - use_operand_p imm_use_p; - imm_use_iterator iterator; - tree ssa_var, stmt; - - - FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var) - @{ - FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator) - SET_USE (imm_use_p, ssa_var_2); - fold_stmt (stmt); - @} -@end smallexample - -There are 2 iterators which can be used. @code{FOR_EACH_IMM_USE_FAST} is -used when the immediate uses are not changed, i.e., you are looking at the -uses, but not setting them. - -If they do get changed, then care must be taken that things are not changed -under the iterators, so use the @code{FOR_EACH_IMM_USE_STMT} and -@code{FOR_EACH_IMM_USE_ON_STMT} iterators. They attempt to preserve the -sanity of the use list by moving all the uses for a statement into -a controlled position, and then iterating over those uses. Then the -optimization can manipulate the stmt when all the uses have been -processed. This is a little slower than the FAST version since it adds a -placeholder element and must sort through the list a bit for each statement. -This placeholder element must be also be removed if the loop is -terminated early. The macro @code{BREAK_FROM_IMM_USE_SAFE} is provided -to do this : - -@smallexample - FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var) - @{ - if (stmt == last_stmt) - BREAK_FROM_SAFE_IMM_USE (iter); - - FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator) - SET_USE (imm_use_p, ssa_var_2); - fold_stmt (stmt); - @} -@end smallexample - -There are checks in @code{verify_ssa} which verify that the immediate use list -is up to date, as well as checking that an optimization didn't break from the -loop without using this macro. It is safe to simply 'break'; from a -@code{FOR_EACH_IMM_USE_FAST} traverse. - -Some useful functions and macros: -@enumerate -@item @code{has_zero_uses (ssa_var)} : Returns true if there are no uses of -@code{ssa_var}. -@item @code{has_single_use (ssa_var)} : Returns true if there is only a -single use of @code{ssa_var}. -@item @code{single_imm_use (ssa_var, use_operand_p *ptr, tree *stmt)} : -Returns true if there is only a single use of @code{ssa_var}, and also returns -the use pointer and statement it occurs in in the second and third parameters. -@item @code{num_imm_uses (ssa_var)} : Returns the number of immediate uses of -@code{ssa_var}. It is better not to use this if possible since it simply -utilizes a loop to count the uses. -@item @code{PHI_ARG_INDEX_FROM_USE (use_p)} : Given a use within a @code{PHI} -node, return the index number for the use. An assert is triggered if the use -isn't located in a @code{PHI} node. -@item @code{USE_STMT (use_p)} : Return the statement a use occurs in. -@end enumerate - -Note that uses are not put into an immediate use list until their statement is -actually inserted into the instruction stream via a @code{bsi_*} routine. - -It is also still possible to utilize lazy updating of statements, but this -should be used only when absolutely required. Both alias analysis and the -dominator optimizations currently do this. - -When lazy updating is being used, the immediate use information is out of date -and cannot be used reliably. Lazy updating is achieved by simply marking -statements modified via calls to @code{mark_stmt_modified} instead of -@code{update_stmt}. When lazy updating is no longer required, all the -modified statements must have @code{update_stmt} called in order to bring them -up to date. This must be done before the optimization is finished, or -@code{verify_ssa} will trigger an abort. - -This is done with a simple loop over the instruction stream: -@smallexample - block_stmt_iterator bsi; - basic_block bb; - FOR_EACH_BB (bb) - @{ - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - update_stmt_if_modified (bsi_stmt (bsi)); - @} -@end smallexample - -@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 update_ssa -@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 symbols or changed the program so that variables that -were previously aliased aren't anymore. Whenever something like this -happens, the affected symbols must be renamed into SSA form again. -Transformations that emit new code or replicate existing statements -will also need to update the SSA form@. - -Since GCC implements two different SSA forms for register and virtual -variables, keeping the SSA form up to date depends on whether you are -updating register or virtual names. In both cases, the general idea -behind incremental SSA updates is similar: when new SSA names are -created, they typically are meant to replace other existing names in -the program@. - -For instance, given the following code: - -@smallexample - 1 L0: - 2 x_1 = PHI (0, x_5) - 3 if (x_1 < 10) - 4 if (x_1 > 7) - 5 y_2 = 0 - 6 else - 7 y_3 = x_1 + x_7 - 8 endif - 9 x_5 = x_1 + 1 - 10 goto L0; - 11 endif -@end smallexample - -Suppose that we insert new names @code{x_10} and @code{x_11} (lines -@code{4} and @code{8})@. - -@smallexample - 1 L0: - 2 x_1 = PHI (0, x_5) - 3 if (x_1 < 10) - 4 x_10 = ... - 5 if (x_1 > 7) - 6 y_2 = 0 - 7 else - 8 x_11 = ... - 9 y_3 = x_1 + x_7 - 10 endif - 11 x_5 = x_1 + 1 - 12 goto L0; - 13 endif -@end smallexample - -We want to replace all the uses of @code{x_1} with the new definitions -of @code{x_10} and @code{x_11}. Note that the only uses that should -be replaced are those at lines @code{5}, @code{9} and @code{11}. -Also, the use of @code{x_7} at line @code{9} should @emph{not} be -replaced (this is why we cannot just mark symbol @code{x} for -renaming)@. - -Additionally, we may need to insert a PHI node at line @code{11} -because that is a merge point for @code{x_10} and @code{x_11}. So the -use of @code{x_1} at line @code{11} will be replaced with the new PHI -node. The insertion of PHI nodes is optional. They are not strictly -necessary to preserve the SSA form, and depending on what the caller -inserted, they may not even be useful for the optimizers@. - -Updating the SSA form is a two step process. First, the pass has to -identify which names need to be updated and/or which symbols need to -be renamed into SSA form for the first time. When new names are -introduced to replace existing names in the program, the mapping -between the old and the new names are registered by calling -@code{register_new_name_mapping} (note that if your pass creates new -code by duplicating basic blocks, the call to @code{tree_duplicate_bb} -will set up the necessary mappings automatically). On the other hand, -if your pass exposes a new symbol that should be put in SSA form for -the first time, the new symbol should be registered with -@code{mark_sym_for_renaming}. - -After the replacement mappings have been registered and new symbols -marked for renaming, a call to @code{update_ssa} makes the registered -changes. This can be done with an explicit call or by creating -@code{TODO} flags in the @code{tree_opt_pass} structure for your pass. -There are several @code{TODO} flags that control the behavior of -@code{update_ssa}: - -@itemize @bullet -@item @code{TODO_update_ssa}. Update the SSA form inserting PHI nodes - for newly exposed symbols and virtual names marked for updating. - When updating real names, only insert PHI nodes for a real name - @code{O_j} in blocks reached by all the new and old definitions for - @code{O_j}. If the iterated dominance frontier for @code{O_j} - is not pruned, we may end up inserting PHI nodes in blocks that - have one or more edges with no incoming definition for - @code{O_j}. This would lead to uninitialized warnings for - @code{O_j}'s symbol@. - -@item @code{TODO_update_ssa_no_phi}. Update the SSA form without - inserting any new PHI nodes at all. This is used by passes that - have either inserted all the PHI nodes themselves or passes that - need only to patch use-def and def-def chains for virtuals - (e.g., DCE)@. - - -@item @code{TODO_update_ssa_full_phi}. Insert PHI nodes everywhere - they are needed. No pruning of the IDF is done. This is used - by passes that need the PHI nodes for @code{O_j} even if it - means that some arguments will come from the default definition - of @code{O_j}'s symbol (e.g., @code{pass_linear_transform})@. - - WARNING: If you need to use this flag, chances are that your - pass may be doing something wrong. Inserting PHI nodes for an - old name where not all edges carry a new replacement may lead to - silent codegen errors or spurious uninitialized warnings@. - -@item @code{TODO_update_ssa_only_virtuals}. Passes that update the - SSA form on their own may want to delegate the updating of - virtual names to the generic updater. Since FUD chains are - easier to maintain, this simplifies the work they need to do. - NOTE: If this flag is used, any OLD->NEW mappings for real names - are explicitly destroyed and only the symbols marked for - renaming are processed@. -@end itemize - -@subsection Preserving the virtual SSA form -@cindex preserving virtual SSA form - -The virtual SSA form is harder to preserve than the non-virtual SSA form -mainly because the set of virtual operands for a statement may change at -what some would consider unexpected times. In general, any time you -have modified a statement that has virtual operands, you should verify -whether the list of virtual operands has changed, and if so, mark the -newly exposed symbols by calling @code{mark_new_vars_to_rename}. - -There is one additional caveat to preserving virtual SSA form. When the -entire set of virtual operands may be eliminated due to better -disambiguation, a bare SMT will be added to the list of virtual -operands, to signify the non-visible aliases that the are still being -referenced. If the set of bare SMT's may change, -@code{TODO_update_smt_usage} should be added to the todo flags. - -With the current pruning code, this can only occur when constants are -propagated into array references that were previously non-constant, or -address expressions are propagated into their uses. - -@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 4 main phases: - -@enumerate -@item Structural alias analysis. - -This phase walks the types for structure variables, and determines which -of the fields can overlap using offset and size of each field. For each -field, a ``subvariable'' called a ``Structure field tag'' (SFT)@ is -created, which represents that field as a separate variable. All -accesses that could possibly overlap with a given field will have -virtual operands for the SFT of that field. - -@smallexample -struct foo -@{ - int a; - int b; -@} -struct foo temp; -int bar (void) -@{ - int tmp1, tmp2, tmp3; - SFT.0_2 = V_MUST_DEF <SFT.0_1> - temp.a = 5; - SFT.1_4 = V_MUST_DEF <SFT.1_3> - temp.b = 6; - - VUSE <SFT.1_4> - tmp1_5 = temp.b; - VUSE <SFT.0_2> - tmp2_6 = temp.a; - - tmp3_7 = tmp1_5 + tmp2_6; - return tmp3_7; -@} -@end smallexample - -If you copy the symbol tag for a variable for some reason, you probably -also want to copy the subvariables for that variable. - -@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 ``symbol memory tag'' (SMT)@. 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 symbol 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 symbol memory tag and -every addressable variable found in the program. Given a symbol -memory tag SMT and an addressable variable V@. If the alias sets -of SMT and V conflict (as computed by may_alias_p), then V is -marked as an alias tag and added to the alias set of SMT@. -@end enumerate - -For instance, consider the following function: - -@smallexample -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 smallexample - -After aliasing analysis has finished, the symbol 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}. - -@smallexample -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 = V_MAY_DEF <a_3>; - # b_8 = V_MAY_DEF <b_5>; - *p_1 = 3; - - # a_9 = V_MAY_DEF <a_7> - # VUSE <b_8> - a_9 = b_8 + 2; - - # VUSE <a_9>; - # VUSE <b_8>; - return *p_1; -@} -@end smallexample - -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 |