gccint: SSA Operands
1
1 13.2 SSA Operands
1 =================
1
1 Almost every GIMPLE statement will contain a reference to a variable or
1 memory location. Since statements come in different shapes and sizes,
1 their operands are going to be located at various spots inside the
1 statement's tree. To facilitate access to the statement's operands,
1 they are organized into lists associated inside each statement's
1 annotation. Each element in an operand list is a pointer to a
1 'VAR_DECL', 'PARM_DECL' or 'SSA_NAME' tree node. This provides a very
1 convenient way of examining and replacing operands.
1
1 Data flow analysis and optimization is done on all tree nodes
1 representing variables. Any node for which 'SSA_VAR_P' returns nonzero
1 is considered when scanning statement operands. However, not all
1 'SSA_VAR_P' variables are processed in the same way. For the purposes
1 of optimization, we need to distinguish between references to local
1 scalar variables and references to globals, statics, structures, arrays,
1 aliased variables, etc. The reason is simple, the compiler can gather
1 complete data flow information for a local scalar. On the other hand, a
1 global variable may be modified by a function call, it may not be
1 possible to keep track of all the elements of an array or the fields of
1 a structure, etc.
1
1 The operand scanner gathers two kinds of operands: "real" and
1 "virtual". An operand for which 'is_gimple_reg' returns true is
1 considered real, otherwise it is a virtual operand. We also distinguish
1 between uses and definitions. An operand is used if its value is loaded
1 by the statement (e.g., the operand at the RHS of an assignment). If
1 the statement assigns a new value to the operand, the operand is
1 considered a definition (e.g., the operand at the LHS of an assignment).
1
1 Virtual and real operands also have very different data flow
1 properties. Real operands are unambiguous references to the full object
1 that they represent. For instance, given
1
1 {
1 int a, b;
1 a = b
1 }
1
1 Since 'a' and 'b' are non-aliased locals, the statement 'a = b' will
1 have one real definition and one real use because variable 'a' is
1 completely modified with the contents of variable 'b'. Real definition
1 are also known as "killing definitions". Similarly, the use of 'b'
1 reads all its bits.
1
1 In contrast, virtual operands are used with variables that can have a
1 partial or ambiguous reference. This includes structures, arrays,
1 globals, and aliased variables. In these cases, we have two types of
1 definitions. For globals, structures, and arrays, we can determine from
1 a statement whether a variable of these types has a killing definition.
1 If the variable does, then the statement is marked as having a "must
1 definition" of that variable. However, if a statement is only defining
1 a part of the variable (i.e. a field in a structure), or if we know that
1 a statement might define the variable but we cannot say for sure, then
1 we mark that statement as having a "may definition". For instance,
1 given
1
1 {
1 int a, b, *p;
1
1 if (...)
1 p = &a;
1 else
1 p = &b;
1 *p = 5;
1 return *p;
1 }
1
1 The assignment '*p = 5' may be a definition of 'a' or 'b'. If we
1 cannot determine statically where 'p' is pointing to at the time of the
1 store operation, we create virtual definitions to mark that statement as
1 a potential definition site for 'a' and 'b'. Memory loads are similarly
1 marked with virtual use operands. Virtual operands are shown in tree
1 dumps right before the statement that contains them. To request a tree
1 dump with virtual operands, use the '-vops' option to '-fdump-tree':
1
1 {
1 int a, b, *p;
1
1 if (...)
1 p = &a;
1 else
1 p = &b;
1 # a = VDEF <a>
1 # b = VDEF <b>
1 *p = 5;
1
1 # VUSE <a>
1 # VUSE <b>
1 return *p;
1 }
1
1 Notice that 'VDEF' operands have two copies of the referenced variable.
1 This indicates that this is not a killing definition of that variable.
1 In this case we refer to it as a "may definition" or "aliased store".
1 The presence of the second copy of the variable in the 'VDEF' operand
1 will become important when the function is converted into SSA form.
1 This will be used to link all the non-killing definitions to prevent
1 optimizations from making incorrect assumptions about them.
1
1 Operands are updated as soon as the statement is finished via a call to
1 'update_stmt'. If statement elements are changed via 'SET_USE' or
1 'SET_DEF', then no further action is required (i.e., those macros take
1 care of updating the statement). If changes are made by manipulating
1 the statement's tree directly, then a call must be made to 'update_stmt'
1 when complete. Calling one of the 'bsi_insert' routines or
1 'bsi_replace' performs an implicit call to 'update_stmt'.
1
1 13.2.1 Operand Iterators And Access Routines
1 --------------------------------------------
1
1 Operands are collected by 'tree-ssa-operands.c'. They are stored inside
1 each statement's annotation and can be accessed through either the
1 operand iterators or an access routine.
1
1 The following access routines are available for examining operands:
1
1 1. 'SINGLE_SSA_{USE,DEF,TREE}_OPERAND': These accessors will return
1 NULL unless there is exactly one operand matching the specified
1 flags. If there is exactly one operand, the operand is returned as
1 either a 'tree', 'def_operand_p', or 'use_operand_p'.
1
1 tree t = SINGLE_SSA_TREE_OPERAND (stmt, flags);
1 use_operand_p u = SINGLE_SSA_USE_OPERAND (stmt, SSA_ALL_VIRTUAL_USES);
1 def_operand_p d = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_ALL_DEFS);
1
1 2. 'ZERO_SSA_OPERANDS': This macro returns true if there are no
1 operands matching the specified flags.
1
1 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1 return;
1
1 3. 'NUM_SSA_OPERANDS': This macro Returns the number of operands
1 matching 'flags'. This actually executes a loop to perform the
1 count, so only use this if it is really needed.
1
1 int count = NUM_SSA_OPERANDS (stmt, flags)
1
1 If you wish to iterate over some or all operands, use the
1 'FOR_EACH_SSA_{USE,DEF,TREE}_OPERAND' iterator. For example, to print
1 all the operands for a statement:
1
1 void
1 print_ops (tree stmt)
1 {
1 ssa_op_iter;
1 tree var;
1
1 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_OPERANDS)
1 print_generic_expr (stderr, var, TDF_SLIM);
1 }
1
1 How to choose the appropriate iterator:
1
1 1. Determine whether you are need to see the operand pointers, or just
1 the trees, and choose the appropriate macro:
1
1 Need Macro:
1 ---- -------
1 use_operand_p FOR_EACH_SSA_USE_OPERAND
1 def_operand_p FOR_EACH_SSA_DEF_OPERAND
1 tree FOR_EACH_SSA_TREE_OPERAND
1
1 2. You need to declare a variable of the type you are interested in,
1 and an ssa_op_iter structure which serves as the loop controlling
1 variable.
1
1 3. Determine which operands you wish to use, and specify the flags of
1 those you are interested in. They are documented in
1 'tree-ssa-operands.h':
1
1 #define SSA_OP_USE 0x01 /* Real USE operands. */
1 #define SSA_OP_DEF 0x02 /* Real DEF operands. */
1 #define SSA_OP_VUSE 0x04 /* VUSE operands. */
1 #define SSA_OP_VDEF 0x08 /* VDEF operands. */
1
1 /* These are commonly grouped operand flags. */
1 #define SSA_OP_VIRTUAL_USES (SSA_OP_VUSE)
1 #define SSA_OP_VIRTUAL_DEFS (SSA_OP_VDEF)
1 #define SSA_OP_ALL_VIRTUALS (SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_DEFS)
1 #define SSA_OP_ALL_USES (SSA_OP_VIRTUAL_USES | SSA_OP_USE)
1 #define SSA_OP_ALL_DEFS (SSA_OP_VIRTUAL_DEFS | SSA_OP_DEF)
1 #define SSA_OP_ALL_OPERANDS (SSA_OP_ALL_USES | SSA_OP_ALL_DEFS)
1
1 So if you want to look at the use pointers for all the 'USE' and 'VUSE'
1 operands, you would do something like:
1
1 use_operand_p use_p;
1 ssa_op_iter iter;
1
1 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, (SSA_OP_USE | SSA_OP_VUSE))
1 {
1 process_use_ptr (use_p);
1 }
1
1 The 'TREE' macro is basically the same as the 'USE' and 'DEF' macros,
1 only with the use or def dereferenced via 'USE_FROM_PTR (use_p)' and
1 'DEF_FROM_PTR (def_p)'. Since we aren't using operand pointers, use and
1 defs flags can be mixed.
1
1 tree var;
1 ssa_op_iter iter;
1
1 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_VUSE)
1 {
1 print_generic_expr (stderr, var, TDF_SLIM);
1 }
1
1 'VDEF's are broken into two flags, one for the 'DEF' portion
1 ('SSA_OP_VDEF') and one for the USE portion ('SSA_OP_VUSE').
1
1 There are many examples in the code, in addition to the documentation
1 in 'tree-ssa-operands.h' and 'ssa-iterators.h'.
1
1 There are also a couple of variants on the stmt iterators regarding PHI
1 nodes.
1
1 'FOR_EACH_PHI_ARG' Works exactly like 'FOR_EACH_SSA_USE_OPERAND',
1 except it works over 'PHI' arguments instead of statement operands.
1
1 /* Look at every virtual PHI use. */
1 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_VIRTUAL_USES)
1 {
1 my_code;
1 }
1
1 /* Look at every real PHI use. */
1 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_USES)
1 my_code;
1
1 /* Look at every PHI use. */
1 FOR_EACH_PHI_ARG (use_p, phi_stmt, iter, SSA_OP_ALL_USES)
1 my_code;
1
1 'FOR_EACH_PHI_OR_STMT_{USE,DEF}' works exactly like
1 'FOR_EACH_SSA_{USE,DEF}_OPERAND', except it will function on either a
1 statement or a 'PHI' node. These should be used when it is appropriate
1 but they are not quite as efficient as the individual 'FOR_EACH_PHI' and
1 'FOR_EACH_SSA' routines.
1
1 FOR_EACH_PHI_OR_STMT_USE (use_operand_p, stmt, iter, flags)
1 {
1 my_code;
1 }
1
1 FOR_EACH_PHI_OR_STMT_DEF (def_operand_p, phi, iter, flags)
1 {
1 my_code;
1 }
1
1 13.2.2 Immediate Uses
1 ---------------------
1
1 Immediate use information is now always available. Using the immediate
1 use iterators, you may examine every use of any 'SSA_NAME'. For
1 instance, to change each use of 'ssa_var' to 'ssa_var2' and call
1 fold_stmt on each stmt after that is done:
1
1 use_operand_p imm_use_p;
1 imm_use_iterator iterator;
1 tree ssa_var, stmt;
1
1
1 FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var)
1 {
1 FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator)
1 SET_USE (imm_use_p, ssa_var_2);
1 fold_stmt (stmt);
1 }
1
1 There are 2 iterators which can be used. 'FOR_EACH_IMM_USE_FAST' is
1 used when the immediate uses are not changed, i.e., you are looking at
1 the uses, but not setting them.
1
1 If they do get changed, then care must be taken that things are not
1 changed under the iterators, so use the 'FOR_EACH_IMM_USE_STMT' and
1 'FOR_EACH_IMM_USE_ON_STMT' iterators. They attempt to preserve the
1 sanity of the use list by moving all the uses for a statement into a
1 controlled position, and then iterating over those uses. Then the
1 optimization can manipulate the stmt when all the uses have been
1 processed. This is a little slower than the FAST version since it adds
1 a placeholder element and must sort through the list a bit for each
1 statement. This placeholder element must be also be removed if the loop
1 is terminated early. The macro 'BREAK_FROM_IMM_USE_SAFE' is provided to
1 do this :
1
1 FOR_EACH_IMM_USE_STMT (stmt, iterator, ssa_var)
1 {
1 if (stmt == last_stmt)
1 BREAK_FROM_SAFE_IMM_USE (iter);
1
1 FOR_EACH_IMM_USE_ON_STMT (imm_use_p, iterator)
1 SET_USE (imm_use_p, ssa_var_2);
1 fold_stmt (stmt);
1 }
1
1 There are checks in 'verify_ssa' which verify that the immediate use
1 list is up to date, as well as checking that an optimization didn't
1 break from the loop without using this macro. It is safe to simply
1 'break'; from a 'FOR_EACH_IMM_USE_FAST' traverse.
1
1 Some useful functions and macros:
1 1. 'has_zero_uses (ssa_var)' : Returns true if there are no uses of
1 'ssa_var'.
1 2. 'has_single_use (ssa_var)' : Returns true if there is only a single
1 use of 'ssa_var'.
1 3. 'single_imm_use (ssa_var, use_operand_p *ptr, tree *stmt)' :
1 Returns true if there is only a single use of 'ssa_var', and also
1 returns the use pointer and statement it occurs in, in the second
1 and third parameters.
1 4. 'num_imm_uses (ssa_var)' : Returns the number of immediate uses of
1 'ssa_var'. It is better not to use this if possible since it
1 simply utilizes a loop to count the uses.
1 5. 'PHI_ARG_INDEX_FROM_USE (use_p)' : Given a use within a 'PHI' node,
1 return the index number for the use. An assert is triggered if the
1 use isn't located in a 'PHI' node.
1 6. 'USE_STMT (use_p)' : Return the statement a use occurs in.
1
1 Note that uses are not put into an immediate use list until their
1 statement is actually inserted into the instruction stream via a 'bsi_*'
1 routine.
1
1 It is also still possible to utilize lazy updating of statements, but
1 this should be used only when absolutely required. Both alias analysis
1 and the dominator optimizations currently do this.
1
1 When lazy updating is being used, the immediate use information is out
1 of date and cannot be used reliably. Lazy updating is achieved by
1 simply marking statements modified via calls to 'gimple_set_modified'
1 instead of 'update_stmt'. When lazy updating is no longer required, all
1 the modified statements must have 'update_stmt' called in order to bring
1 them up to date. This must be done before the optimization is finished,
1 or 'verify_ssa' will trigger an abort.
1
1 This is done with a simple loop over the instruction stream:
1 block_stmt_iterator bsi;
1 basic_block bb;
1 FOR_EACH_BB (bb)
1 {
1 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1 update_stmt_if_modified (bsi_stmt (bsi));
1 }
1