+insert_phi_nodes_for (tree var, bitmap phi_insertion_points)
+{
+ unsigned bb_index;
+ edge e;
+ tree phi;
+ basic_block bb;
+ bitmap_iterator bi;
+ struct def_blocks_d *def_map;
+
+ def_map = find_def_blocks_for (var);
+
+ /* Remove the blocks where we already have PHI nodes for VAR. */
+ bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
+
+ /* Now compute global livein for this variable. Note this modifies
+ def_map->livein_blocks. */
+ compute_global_livein (def_map->livein_blocks, def_map->def_blocks);
+
+ /* And insert the PHI nodes. */
+ EXECUTE_IF_AND_IN_BITMAP (phi_insertion_points, def_map->livein_blocks,
+ 0, bb_index, bi)
+ {
+ bb = BASIC_BLOCK (bb_index);
+ phi = create_phi_node (var, bb);
+
+ /* If we are rewriting SSA names, add also the PHI arguments. */
+ if (TREE_CODE (var) == SSA_NAME)
+ {
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ add_phi_arg (phi, var, e);
+ }
+ }
+}
+
+
+/* Helper for insert_phi_nodes. If VAR needs PHI nodes, insert them
+ at the dominance frontier (DFS) of blocks defining VAR. */
+
+static inline void
+insert_phi_nodes_1 (tree var, bitmap *dfs)
+{
+ struct def_blocks_d *def_map;
+ bitmap idf;
+
+ def_map = find_def_blocks_for (var);
+ if (def_map == NULL)
+ return;
+
+ idf = find_idf (def_map->def_blocks, dfs);
+
+ if (get_phi_state (var) != NEED_PHI_STATE_NO)
+ insert_phi_nodes_for (var, idf);
+
+ BITMAP_FREE (idf);
+}
+
+
+/* Insert PHI nodes at the dominance frontier of blocks with variable
+ definitions. DFS contains the dominance frontier information for
+ the flowgraph. PHI nodes will only be inserted at the dominance
+ frontier of definition blocks for variables whose NEED_PHI_STATE
+ annotation is marked as ``maybe'' or ``unknown'' (computed by
+ mark_def_sites). If NAMES_TO_RENAME is not NULL, do the same but
+ for ssa name rewriting. */
+
+static void
+insert_phi_nodes (bitmap *dfs, bitmap names_to_rename)
+{
+ unsigned i;
+ bitmap_iterator bi;
+
+ timevar_push (TV_TREE_INSERT_PHI_NODES);
+
+ /* Iterate over all variables in VARS_TO_RENAME. For each variable, add
+ to the work list all the blocks that have a definition for the
+ variable. PHI nodes will be added to the dominance frontier blocks of
+ each definition block. */
+ if (names_to_rename)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
+ if (ssa_name (i))
+ insert_phi_nodes_1 (ssa_name (i), dfs);
+ }
+ else if (vars_to_rename)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (vars_to_rename, 0, i, bi)
+ insert_phi_nodes_1 (referenced_var (i), dfs);
+ }
+ else
+ {
+ for (i = 0; i < num_referenced_vars; i++)
+ insert_phi_nodes_1 (referenced_var (i), dfs);
+ }
+
+ timevar_pop (TV_TREE_INSERT_PHI_NODES);
+}
+
+
+/* Register DEF (an SSA_NAME) to be a new definition for its underlying
+ variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
+ into the stack pointed by BLOCK_DEFS_P. */
+
+void
+register_new_def (tree def, VEC (tree_on_heap) **block_defs_p)
+{
+ tree var = SSA_NAME_VAR (def);
+ tree currdef;
+
+ /* If this variable is set in a single basic block and all uses are
+ dominated by the set(s) in that single basic block, then there is
+ no reason to record anything for this variable in the block local
+ definition stacks. Doing so just wastes time and memory.
+
+ This is the same test to prune the set of variables which may
+ need PHI nodes. So we just use that information since it's already
+ computed and available for us to use. */
+ if (get_phi_state (var) == NEED_PHI_STATE_NO)
+ {
+ set_current_def (var, def);
+ return;
+ }
+
+ currdef = get_current_def (var);
+
+ /* Push the current reaching definition into *BLOCK_DEFS_P. This stack is
+ later used by the dominator tree callbacks to restore the reaching
+ definitions for all the variables defined in the block after a recursive
+ visit to all its immediately dominated blocks. If there is no current
+ reaching definition, then just record the underlying _DECL node. */
+ VEC_safe_push (tree_on_heap, *block_defs_p, currdef ? currdef : var);
+
+ /* Set the current reaching definition for VAR to be DEF. */
+ set_current_def (var, def);
+}
+
+
+/* Perform a depth-first traversal of the dominator tree looking for
+ variables to rename. BB is the block where to start searching.
+ Renaming is a five step process:
+
+ 1- Every definition made by PHI nodes at the start of the blocks is
+ registered as the current definition for the corresponding variable.
+
+ 2- Every statement in BB is rewritten. USE and VUSE operands are
+ rewritten with their corresponding reaching definition. DEF and
+ VDEF targets are registered as new definitions.
+
+ 3- All the PHI nodes in successor blocks of BB are visited. The
+ argument corresponding to BB is replaced with its current reaching
+ definition.
+
+ 4- Recursively rewrite every dominator child block of BB.
+
+ 5- Restore (in reverse order) the current reaching definition for every
+ new definition introduced in this block. This is done so that when
+ we return from the recursive call, all the current reaching
+ definitions are restored to the names that were valid in the
+ dominator parent of BB. */
+
+/* SSA Rewriting Step 1. Initialization, create a block local stack
+ of reaching definitions for new SSA names produced in this block
+ (BLOCK_DEFS). Register new definitions for every PHI node in the
+ block. */
+
+static void
+rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb)