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