13.3.1 Preserving the 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:

     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

Suppose that we insert new names x_10 and x_11 (lines 4 and 8).

     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

We want to replace all the uses of x_1 with the new definitions of x_10 and x_11. Note that the only uses that should be replaced are those at lines 5, 9 and 11. Also, the use of x_7 at line 9 should not be replaced (this is why we cannot just mark symbol x for renaming).

Additionally, we may need to insert a PHI node at line 11 because that is a merge point for x_10 and x_11. So the use of x_1 at line 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 register_new_name_mapping (note that if your pass creates new code by duplicating basic blocks, the call to 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 update_ssa makes the registered changes. This can be done with an explicit call or by creating TODO flags in the tree_opt_pass structure for your pass. There are several TODO flags that control the behavior of update_ssa:

• 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 O_j in blocks reached by all the new and old definitions for O_j. If the iterated dominance frontier for 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 O_j. This would lead to uninitialized warnings for O_j’s symbol.
• 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).
• 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 O_j even if it means that some arguments will come from the default definition of O_j’s symbol (e.g., 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.

• 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.

13.3.2 Examining SSA_NAME nodes ¶

The following macros can be used to examine SSA_NAME nodes

Macro: SSA_NAME_DEF_STMT (var) ¶

Returns the statement s that creates the SSA_NAME var. If s is an empty statement (i.e., IS_EMPTY_STMT (s) returns true), it means that the first reference to this variable is a USE or a VUSE.

Macro: SSA_NAME_VERSION (var) ¶

Returns the version number of the SSA_NAME object var.

13.3.3 Walking the dominator tree ¶

Tree SSA function: void walk_dominator_tree (walk_data, bb) ¶

This function walks the dominator tree for the current CFG calling a set of callback functions defined in struct dom_walk_data in domwalk.h. The call back functions you need to define give you hooks to execute custom code at various points during traversal:

1. Once to initialize any local data needed while processing 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.
2. Once before traversing all the statements in the bb.
3. Once for every statement inside bb.
4. Once after traversing all the statements and before recursing into bb’s dominator children.
5. It then recurses into all the dominator children of bb.
6. After recursing into all the dominator children of bb it can, optionally, traverse every statement in bb again (i.e., repeating steps 2 and 3).
7. Once after walking the statements in bb and bb’s dominator children. At this stage, the block local data stack is popped.