diff options
Diffstat (limited to 'gcc/doc/tree-ssa.texi')
| -rw-r--r-- | gcc/doc/tree-ssa.texi | 826 |
1 files changed, 0 insertions, 826 deletions
diff --git a/gcc/doc/tree-ssa.texi b/gcc/doc/tree-ssa.texi deleted file mode 100644 index f962ef9..0000000 --- a/gcc/doc/tree-ssa.texi +++ /dev/null @@ -1,826 +0,0 @@ -@c Copyright (C) 2004-2022 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 tuples -@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 -* Annotations:: Attributes for variables. -* SSA Operands:: SSA names referenced by GIMPLE statements. -* SSA:: Static Single Assignment representation. -* Alias analysis:: Representing aliased loads and stores. -* Memory model:: Memory model used by the middle-end. -@end menu - -@node Annotations -@section Annotations -@cindex annotations - -The optimizers need to associate attributes with variables during the -optimization process. For instance, we need to know 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}. - - -@node SSA Operands -@section SSA 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{a} is completely modified with the contents of -variable @code{b}. Real definition are also known as @dfn{killing -definitions}. Similarly, the use of @code{b} reads all its bits. - -In contrast, virtual operands are used with variables that can have -a partial or ambiguous reference. This includes structures, arrays, -globals, and aliased variables. In these cases, we have two types of -definitions. For globals, structures, and arrays, we can determine from -a statement whether a variable of these types has a killing definition. -If the variable does, then the statement is marked as having a -@dfn{must definition} of that variable. However, if a statement is only -defining a part of the variable (i.e.@: a field in a structure), or if we -know that a statement might define the variable but we cannot say for sure, -then we mark that statement as having a @dfn{may definition}. For -instance, given - -@smallexample -@{ - int a, b, *p; - - if (@dots{}) - p = &a; - else - p = &b; - *p = 5; - return *p; -@} -@end smallexample - -The assignment @code{*p = 5} may be a definition of @code{a} or -@code{b}. If we cannot determine statically where @code{p} is -pointing to at the time of the store operation, we create virtual -definitions to mark that statement as a potential definition site for -@code{a} and @code{b}. Memory loads are similarly marked with virtual -use operands. Virtual operands are shown in tree dumps right before -the statement that contains them. To request a tree dump with virtual -operands, use the @option{-vops} option to @option{-fdump-tree}: - -@smallexample -@{ - int a, b, *p; - - if (@dots{}) - p = &a; - else - p = &b; - # a = VDEF <a> - # b = VDEF <b> - *p = 5; - - # VUSE <a> - # VUSE <b> - return *p; -@} -@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 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.cc}. 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_VDEF 0x08 /* @r{VDEF operands.} */ - -/* @r{These are commonly grouped operand flags.} */ -#define SSA_OP_VIRTUAL_USES (SSA_OP_VUSE) -#define SSA_OP_VIRTUAL_DEFS (SSA_OP_VDEF) -#define SSA_OP_ALL_VIRTUALS (SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_DEFS) -#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) - @{ - print_generic_expr (stderr, var, TDF_SLIM); - @} -@end smallexample - -@code{VDEF}s are broken into two flags, one for the -@code{DEF} portion (@code{SSA_OP_VDEF}) and one for the USE portion -(@code{SSA_OP_VUSE}). - -There are many examples in the code, in addition to the documentation -in @file{tree-ssa-operands.h} and @file{ssa-iterators.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 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; a destructor takes care of that when leaving the -@code{FOR_EACH_IMM_USE_STMT} scope. - -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{gimple_set_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.cc} 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. - -@cindex PHI nodes -Sometimes, flow of control makes it impossible to determine 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 (@dots{}) - a_1 = 5; -else if (@dots{}) - 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 functions can be used to examine PHI nodes - -@defun gimple_phi_result (@var{phi}) -Returns the @code{SSA_NAME} created by PHI node @var{phi} (i.e., -@var{phi}'s LHS)@. -@end defun - -@defun gimple_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 defun - -@defun gimple_phi_arg (@var{phi}, @var{i}) -Returns @var{i}th argument of @var{phi}@. -@end defun - -@defun gimple_phi_arg_edge (@var{phi}, @var{i}) -Returns the incoming edge for the @var{i}th argument of @var{phi}. -@end defun - -@defun gimple_phi_arg_def (@var{phi}, @var{i}) -Returns the @code{SSA_NAME} for the @var{i}th argument of @var{phi}. -@end defun - - -@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 = @dots{} - 5 if (x_1 > 7) - 6 y_2 = 0 - 7 else - 8 x_11 = @dots{} - 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). - -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 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 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 in GIMPLE SSA form consists of two pieces. First -the virtual SSA web ties conflicting memory accesses and provides -a SSA use-def chain and SSA immediate-use chains for walking -possibly dependent memory accesses. Second an alias-oracle can -be queried to disambiguate explicit and implicit memory references. - -@enumerate -@item Memory SSA form. - -All statements that may use memory have exactly one accompanied use of -a virtual SSA name that represents the state of memory at the -given point in the IL. - -All statements that may define memory have exactly one accompanied -definition of a virtual SSA name using the previous state of memory -and defining the new state of memory after the given point in the IL. - -@smallexample -int i; -int foo (void) -@{ - # .MEM_3 = VDEF <.MEM_2(D)> - i = 1; - # VUSE <.MEM_3> - return i; -@} -@end smallexample - -The virtual SSA names in this case are @code{.MEM_2(D)} and -@code{.MEM_3}. The store to the global variable @code{i} -defines @code{.MEM_3} invalidating @code{.MEM_2(D)}. The -load from @code{i} uses that new state @code{.MEM_3}. - -The virtual SSA web serves as constraints to SSA optimizers -preventing illegitimate code-motion and optimization. It -also provides a way to walk related memory statements. - -@item Points-to and escape analysis. - -Points-to analysis builds a set of constraints from the GIMPLE -SSA IL representing all pointer operations and facts we do -or do not know about pointers. Solving this set of constraints -yields a conservatively correct solution for each pointer -variable in the program (though we are only interested in -SSA name pointers) as to what it may possibly point to. - -This points-to solution for a given SSA name pointer is stored -in the @code{pt_solution} sub-structure of the -@code{SSA_NAME_PTR_INFO} record. The following accessor -functions are available: - -@itemize @bullet -@item @code{pt_solution_includes} -@item @code{pt_solutions_intersect} -@end itemize - -Points-to analysis also computes the solution for two special -set of pointers, @code{ESCAPED} and @code{CALLUSED}. Those -represent all memory that has escaped the scope of analysis -or that is used by pure or nested const calls. - -@item Type-based alias analysis - -Type-based alias analysis is frontend dependent though generic -support is provided by the middle-end in @code{alias.cc}. TBAA -code is used by both tree optimizers and RTL optimizers. - -Every language that wishes to perform language-specific alias analysis -should define a function that computes, given a @code{tree} -node, an alias set for the node. Nodes in different alias sets are not -allowed to alias. For an example, see the C front-end function -@code{c_get_alias_set}. - -@item Tree alias-oracle - -The tree alias-oracle provides means to disambiguate two memory -references and memory references against statements. The following -queries are available: - -@itemize @bullet -@item @code{refs_may_alias_p} -@item @code{ref_maybe_used_by_stmt_p} -@item @code{stmt_may_clobber_ref_p} -@end itemize - -In addition to those two kind of statement walkers are available -walking statements related to a reference ref. -@code{walk_non_aliased_vuses} walks over dominating memory defining -statements and calls back if the statement does not clobber ref -providing the non-aliased VUSE. The walk stops at -the first clobbering statement or if asked to. -@code{walk_aliased_vdefs} walks over dominating memory defining -statements and calls back on each statement clobbering ref -providing its aliasing VDEF. The walk stops if asked to. - -@end enumerate - - -@node Memory model -@section Memory model -@cindex memory model - -The memory model used by the middle-end models that of the C/C++ -languages. The middle-end has the notion of an effective type -of a memory region which is used for type-based alias analysis. - -The following is a refinement of ISO C99 6.5/6, clarifying the block copy case -to follow common sense and extending the concept of a dynamic effective -type to objects with a declared type as required for C++. - -@smallexample -The effective type of an object for an access to its stored value is -the declared type of the object or the effective type determined by -a previous store to it. If a value is stored into an object through -an lvalue having a type that is not a character type, then the -type of the lvalue becomes the effective type of the object for that -access and for subsequent accesses that do not modify the stored value. -If a value is copied into an object using @code{memcpy} or @code{memmove}, -or is copied as an array of character type, then the effective type -of the modified object for that access and for subsequent accesses that -do not modify the value is undetermined. For all other accesses to an -object, the effective type of the object is simply the type of the -lvalue used for the access. -@end smallexample - |