gcc/doc/gccint/analysis-and-optimization-of-gimple-tuples/static-single-assignment.rst

   1 ..
   2   Copyright 1988-2022 Free Software Foundation, Inc.
   3   This is part of the GCC manual.
   4   For copying conditions, see the copyright.rst file.
   5
   6 .. index:: SSA, static single assignment
   7
   8 .. _ssa:
   9
  10 Static Single Assignment
  11 ************************
  12
  13 Most of the tree optimizers rely on the data flow information provided
  14 by the Static Single Assignment (SSA) form.  We implement the SSA form
  15 as described in R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and
  16 K. Zadeck.  Efficiently Computing Static Single Assignment Form and the
  17 Control Dependence Graph.  ACM Transactions on Programming Languages
  18 and Systems, 13(4):451-490, October 1991.
  19
  20 The SSA form is based on the premise that program variables are
  21 assigned in exactly one location in the program.  Multiple assignments
  22 to the same variable create new versions of that variable.  Naturally,
  23 actual programs are seldom in SSA form initially because variables
  24 tend to be assigned multiple times.  The compiler modifies the program
  25 representation so that every time a variable is assigned in the code,
  26 a new version of the variable is created.  Different versions of the
  27 same variable are distinguished by subscripting the variable name with
  28 its version number.  Variables used in the right-hand side of
  29 expressions are renamed so that their version number matches that of
  30 the most recent assignment.
  31
  32 We represent variable versions using ``SSA_NAME`` nodes.  The
  33 renaming process in :samp:`tree-ssa.cc` wraps every real and
  34 virtual operand with an ``SSA_NAME`` node which contains
  35 the version number and the statement that created the
  36 ``SSA_NAME``.  Only definitions and virtual definitions may
  37 create new ``SSA_NAME`` nodes.
  38
  39 .. index:: PHI nodes
  40
  41 Sometimes, flow of control makes it impossible to determine the
  42 most recent version of a variable.  In these cases, the compiler
  43 inserts an artificial definition for that variable called
  44 :dfn:`PHI function` or :dfn:`PHI node`.  This new definition merges
  45 all the incoming versions of the variable to create a new name
  46 for it.  For instance,
  47
  48 .. code-block:: c++
  49
  50   if (...)
  51     a_1 = 5;
  52   else if (...)
  53     a_2 = 2;
  54   else
  55     a_3 = 13;
  56
  57   # a_4 = PHI <a_1, a_2, a_3>
  58   return a_4;
  59
  60 Since it is not possible to determine which of the three branches
  61 will be taken at runtime, we don't know which of ``a_1``,
  62 ``a_2`` or ``a_3`` to use at the return statement.  So, the
  63 SSA renamer creates a new version ``a_4`` which is assigned
  64 the result of 'merging' ``a_1``, ``a_2`` and ``a_3``.
  65 Hence, PHI nodes mean 'one of these operands.  I don't know
  66 which'.
  67
  68 The following functions can be used to examine PHI nodes
  69
  70 .. function:: gimple_phi_result (phi)
  71
  72   Returns the ``SSA_NAME`` created by PHI node :samp:`{phi}` (i.e., :samp:`{phi}` 's LHS).
  73
  74 .. function:: gimple_phi_num_args (phi)
  75
  76   Returns the number of arguments in :samp:`{phi}`.  This number is exactly
  77   the number of incoming edges to the basic block holding :samp:`{phi}`.
  78
  79 .. function:: gimple_phi_arg (phi, i)
  80
  81   Returns :samp:`{i}` th argument of :samp:`{phi}`.
  82
  83 .. function:: gimple_phi_arg_edge (phi, i)
  84
  85   Returns the incoming edge for the :samp:`{i}` th argument of :samp:`{phi}`.
  86
  87 .. function:: gimple_phi_arg_def (phi, i)
  88
  89   Returns the ``SSA_NAME`` for the :samp:`{i}` th argument of :samp:`{phi}`.
  90
  91 .. index:: update_ssa, preserving SSA form
  92
  93 Preserving the SSA form
  94 ^^^^^^^^^^^^^^^^^^^^^^^
  95
  96 Some optimization passes make changes to the function that
  97 invalidate the SSA property.  This can happen when a pass has
  98 added new symbols or changed the program so that variables that
  99 were previously aliased aren't anymore.  Whenever something like this
 100 happens, the affected symbols must be renamed into SSA form again.
 101 Transformations that emit new code or replicate existing statements
 102 will also need to update the SSA form.
 103
 104 Since GCC implements two different SSA forms for register and virtual
 105 variables, keeping the SSA form up to date depends on whether you are
 106 updating register or virtual names.  In both cases, the general idea
 107 behind incremental SSA updates is similar: when new SSA names are
 108 created, they typically are meant to replace other existing names in
 109 the program.
 110
 111 For instance, given the following code:
 112
 113 .. code-block:: c++
 114
 115        1  L0:
 116        2  x_1 = PHI (0, x_5)
 117        3  if (x_1 < 10)
 118        4    if (x_1 > 7)
 119        5      y_2 = 0
 120        6    else
 121        7      y_3 = x_1 + x_7
 122        8    endif
 123        9    x_5 = x_1 + 1
 124        10   goto L0;
 125        11 endif
 126
 127 Suppose that we insert new names ``x_10`` and ``x_11`` (lines
 128 ``4`` and ``8``).
 129
 130 .. code-block:: c++
 131
 132        1  L0:
 133        2  x_1 = PHI (0, x_5)
 134        3  if (x_1 < 10)
 135        4    x_10 = ...
 136        5    if (x_1 > 7)
 137        6      y_2 = 0
 138        7    else
 139        8      x_11 = ...
 140        9      y_3 = x_1 + x_7
 141        10   endif
 142        11   x_5 = x_1 + 1
 143        12   goto L0;
 144        13 endif
 145
 146 We want to replace all the uses of ``x_1`` with the new definitions
 147 of ``x_10`` and ``x_11``.  Note that the only uses that should
 148 be replaced are those at lines ``5``, ``9`` and ``11``.
 149 Also, the use of ``x_7`` at line ``9`` should *not* be
 150 replaced (this is why we cannot just mark symbol ``x`` for
 151 renaming).
 152
 153 Additionally, we may need to insert a PHI node at line ``11``
 154 because that is a merge point for ``x_10`` and ``x_11``.  So the
 155 use of ``x_1`` at line ``11`` will be replaced with the new PHI
 156 node.  The insertion of PHI nodes is optional.  They are not strictly
 157 necessary to preserve the SSA form, and depending on what the caller
 158 inserted, they may not even be useful for the optimizers.
 159
 160 Updating the SSA form is a two step process.  First, the pass has to
 161 identify which names need to be updated and/or which symbols need to
 162 be renamed into SSA form for the first time.  When new names are
 163 introduced to replace existing names in the program, the mapping
 164 between the old and the new names are registered by calling
 165 ``register_new_name_mapping`` (note that if your pass creates new
 166 code by duplicating basic blocks, the call to ``tree_duplicate_bb``
 167 will set up the necessary mappings automatically).
 168
 169 After the replacement mappings have been registered and new symbols
 170 marked for renaming, a call to ``update_ssa`` makes the registered
 171 changes.  This can be done with an explicit call or by creating
 172 ``TODO`` flags in the ``tree_opt_pass`` structure for your pass.
 173 There are several ``TODO`` flags that control the behavior of
 174 ``update_ssa`` :
 175
 176 * ``TODO_update_ssa``.  Update the SSA form inserting PHI nodes
 177   for newly exposed symbols and virtual names marked for updating.
 178   When updating real names, only insert PHI nodes for a real name
 179   ``O_j`` in blocks reached by all the new and old definitions for
 180   ``O_j``.  If the iterated dominance frontier for ``O_j``
 181   is not pruned, we may end up inserting PHI nodes in blocks that
 182   have one or more edges with no incoming definition for
 183   ``O_j``.  This would lead to uninitialized warnings for
 184   ``O_j`` 's symbol.
 185
 186 * ``TODO_update_ssa_no_phi``.  Update the SSA form without
 187   inserting any new PHI nodes at all.  This is used by passes that
 188   have either inserted all the PHI nodes themselves or passes that
 189   need only to patch use-def and def-def chains for virtuals
 190   (e.g., DCE).
 191
 192 * ``TODO_update_ssa_full_phi``.  Insert PHI nodes everywhere
 193   they are needed.  No pruning of the IDF is done.  This is used
 194   by passes that need the PHI nodes for ``O_j`` even if it
 195   means that some arguments will come from the default definition
 196   of ``O_j`` 's symbol (e.g., ``pass_linear_transform``).
 197
 198   WARNING: If you need to use this flag, chances are that your
 199   pass may be doing something wrong.  Inserting PHI nodes for an
 200   old name where not all edges carry a new replacement may lead to
 201   silent codegen errors or spurious uninitialized warnings.
 202
 203 * ``TODO_update_ssa_only_virtuals``.  Passes that update the
 204   SSA form on their own may want to delegate the updating of
 205   virtual names to the generic updater.  Since FUD chains are
 206   easier to maintain, this simplifies the work they need to do.
 207   NOTE: If this flag is used, any OLD->NEW mappings for real names
 208   are explicitly destroyed and only the symbols marked for
 209   renaming are processed.
 210
 211 .. index:: examining SSA_NAMEs
 212
 213 Examining SSA_NAME nodes
 214 ^^^^^^^^^^^^^^^^^^^^^^^^
 215
 216 The following macros can be used to examine ``SSA_NAME`` nodes
 217
 218 .. c:macro:: SSA_NAME_DEF_STMT (var)
 219
 220   Returns the statement :samp:`{s}` that creates the ``SSA_NAME``
 221   :samp:`{var}`.  If :samp:`{s}` is an empty statement (i.e., ``IS_EMPTY_STMT
 222   (s)`` returns ``true``), it means that the first reference to
 223   this variable is a USE or a VUSE.
 224
 225 .. c:macro:: SSA_NAME_VERSION (var)
 226
 227   Returns the version number of the ``SSA_NAME`` object :samp:`{var}`.
 228
 229 Walking the dominator tree
 230 ^^^^^^^^^^^^^^^^^^^^^^^^^^
 231
 232 .. function:: void walk_dominator_tree (walk_data, bb)
 233
 234   This function walks the dominator tree for the current CFG calling a
 235   set of callback functions defined in :samp:`{struct dom_walk_data}` in
 236   :samp:`domwalk.h`.  The call back functions you need to define give you
 237   hooks to execute custom code at various points during traversal:
 238
 239   * Once to initialize any local data needed while processing
 240     :samp:`{bb}` and its children.  This local data is pushed into an
 241     internal stack which is automatically pushed and popped as the
 242     walker traverses the dominator tree.
 243
 244   * Once before traversing all the statements in the :samp:`{bb}`.
 245
 246   * Once for every statement inside :samp:`{bb}`.
 247
 248   * Once after traversing all the statements and before recursing
 249     into :samp:`{bb}` 's dominator children.
 250
 251   * It then recurses into all the dominator children of :samp:`{bb}`.
 252
 253   * After recursing into all the dominator children of :samp:`{bb}` it
 254     can, optionally, traverse every statement in :samp:`{bb}` again
 255     (i.e., repeating steps 2 and 3).
 256
 257   * Once after walking the statements in :samp:`{bb}` and :samp:`{bb}` 's
 258     dominator children.  At this stage, the block local data stack
 259     is popped.