+ 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 (sym) == NEED_PHI_STATE_NO)
+ {
+ set_current_def (sym, def);
+ return;
+ }
+
+ currdef = get_current_def (sym);
+
+ /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
+ SSA_NAME_VAR is not necessarily SYM. In this case, also push SYM
+ in the stack so that we know which symbol is being defined by
+ this SSA name when we unwind the stack. */
+ if (currdef && !is_gimple_reg (sym))
+ VEC_safe_push (tree, heap, block_defs_stack, sym);
+
+ /* Push the current reaching definition into BLOCK_DEFS_STACK. 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, heap, block_defs_stack, currdef ? currdef : sym);
+
+ /* Set the current reaching definition for SYM to be DEF. */
+ set_current_def (sym, 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)
+{
+ tree phi;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
+
+ /* Mark the unwind point for this block. */
+ VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
+
+ /* Step 1. Register new definitions for every PHI node in the block.
+ Conceptually, all the PHI nodes are executed in parallel and each PHI
+ node introduces a new version for the associated variable. */
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ tree result = PHI_RESULT (phi);
+ gcc_assert (is_gimple_reg (result));
+ register_new_def (result, SSA_NAME_VAR (result));
+ }
+}
+
+
+/* Return the current definition for variable VAR. If none is found,
+ create a new SSA name to act as the zeroth definition for VAR. */
+
+static tree
+get_reaching_def (tree var)
+{
+ tree currdef;
+
+ /* Lookup the current reaching definition for VAR. */
+ currdef = get_current_def (var);
+
+ /* If there is no reaching definition for VAR, create and register a
+ default definition for it (if needed). */
+ if (currdef == NULL_TREE)
+ {
+ tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
+ currdef = get_default_def_for (sym);
+ set_current_def (var, currdef);
+ }
+
+ /* Return the current reaching definition for VAR, or the default
+ definition, if we had to create one. */
+ return currdef;
+}
+
+
+/* SSA Rewriting Step 2. Rewrite every variable used in each statement in
+ the block with its immediate reaching definitions. Update the current
+ definition of a variable when a new real or virtual definition is found. */
+
+static void
+rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb ATTRIBUTE_UNUSED, block_stmt_iterator si)
+{
+ tree stmt;
+ use_operand_p use_p;
+ def_operand_p def_p;
+ ssa_op_iter iter;
+
+ stmt = bsi_stmt (si);
+
+ /* If mark_def_sites decided that we don't need to rewrite this
+ statement, ignore it. */
+ gcc_assert (blocks_to_update == NULL);
+ if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
+ return;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Renaming statement ");
+ print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+
+ /* Step 1. Rewrite USES in the statement. */
+ if (REWRITE_THIS_STMT (stmt))
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ {
+ tree var = USE_FROM_PTR (use_p);
+ gcc_assert (DECL_P (var));
+ SET_USE (use_p, get_reaching_def (var));
+ }
+
+ /* Step 2. Register the statement's DEF operands. */
+ if (REGISTER_DEFS_IN_THIS_STMT (stmt))
+ FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
+ {
+ tree var = DEF_FROM_PTR (def_p);
+ gcc_assert (DECL_P (var));
+ SET_DEF (def_p, make_ssa_name (var, stmt));
+ register_new_def (DEF_FROM_PTR (def_p), var);
+ }
+}
+
+
+/* SSA Rewriting Step 3. Visit all the successor blocks of BB looking for
+ PHI nodes. For every PHI node found, add a new argument containing the
+ current reaching definition for the variable and the edge through which
+ that definition is reaching the PHI node. */
+
+static void
+rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ tree phi;
+
+ for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
+ {
+ tree currdef;
+ currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
+ add_phi_arg (phi, currdef, e);
+ }
+ }
+}
+
+
+/* Called after visiting all the statements in basic block BB and all
+ of its dominator children. Restore CURRDEFS to its original value. */
+
+static void
+rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb ATTRIBUTE_UNUSED)
+{
+ /* Restore CURRDEFS to its original state. */
+ while (VEC_length (tree, block_defs_stack) > 0)
+ {
+ tree tmp = VEC_pop (tree, block_defs_stack);
+ tree saved_def, var;
+
+ if (tmp == NULL_TREE)
+ break;
+
+ if (TREE_CODE (tmp) == SSA_NAME)
+ {
+ /* If we recorded an SSA_NAME, then make the SSA_NAME the
+ current definition of its underlying variable. Note that
+ if the SSA_NAME is not for a GIMPLE register, the symbol
+ being defined is stored in the next slot in the stack.
+ This mechanism is needed because an SSA name for a
+ non-register symbol may be the definition for more than
+ one symbol (e.g., SFTs, aliased variables, etc). */
+ saved_def = tmp;
+ var = SSA_NAME_VAR (saved_def);
+ if (!is_gimple_reg (var))
+ var = VEC_pop (tree, block_defs_stack);
+ }
+ else
+ {
+ /* If we recorded anything else, it must have been a _DECL
+ node and its current reaching definition must have been
+ NULL. */
+ saved_def = NULL;
+ var = tmp;
+ }
+
+ set_current_def (var, saved_def);
+ }
+}
+
+
+/* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
+
+void
+dump_decl_set (FILE *file, bitmap set)
+{
+ if (set)
+ {
+ bitmap_iterator bi;
+ unsigned i;
+
+ fprintf (file, "{ ");
+
+ EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
+ {
+ print_generic_expr (file, referenced_var (i), 0);
+ fprintf (file, " ");
+ }
+
+ fprintf (file, "}\n");
+ }
+ else
+ fprintf (file, "NIL\n");
+}
+
+
+/* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE. */
+
+void
+debug_decl_set (bitmap set)
+{
+ dump_decl_set (stderr, set);
+}
+
+
+/* Dump the renaming stack (block_defs_stack) to FILE. Traverse the
+ stack up to a maximum of N levels. If N is -1, the whole stack is
+ dumped. New levels are created when the dominator tree traversal
+ used for renaming enters a new sub-tree. */
+
+void
+dump_defs_stack (FILE *file, int n)
+{
+ int i, j;
+
+ fprintf (file, "\n\nRenaming stack");
+ if (n > 0)
+ fprintf (file, " (up to %d levels)", n);
+ fprintf (file, "\n\n");
+
+ i = 1;
+ fprintf (file, "Level %d (current level)\n", i);
+ for (j = (int) VEC_length (tree, block_defs_stack) - 1; j >= 0; j--)
+ {
+ tree name, var;
+
+ name = VEC_index (tree, block_defs_stack, j);
+ if (name == NULL_TREE)
+ {
+ i++;
+ if (n > 0 && i > n)
+ break;
+ fprintf (file, "\nLevel %d\n", i);
+ continue;
+ }
+
+ if (DECL_P (name))
+ {
+ var = name;
+ name = NULL_TREE;
+ }
+ else
+ {
+ var = SSA_NAME_VAR (name);
+ if (!is_gimple_reg (var))
+ {
+ j--;
+ var = VEC_index (tree, block_defs_stack, j);
+ }
+ }
+
+ fprintf (file, " Previous CURRDEF (");
+ print_generic_expr (file, var, 0);
+ fprintf (file, ") = ");
+ if (name)
+ print_generic_expr (file, name, 0);
+ else
+ fprintf (file, "<NIL>");
+ fprintf (file, "\n");
+ }
+}
+
+
+/* Dump the renaming stack (block_defs_stack) to stderr. Traverse the
+ stack up to a maximum of N levels. If N is -1, the whole stack is
+ dumped. New levels are created when the dominator tree traversal
+ used for renaming enters a new sub-tree. */
+
+void
+debug_defs_stack (int n)
+{
+ dump_defs_stack (stderr, n);
+}
+
+
+/* Dump the current reaching definition of every symbol to FILE. */
+
+void
+dump_currdefs (FILE *file)
+{
+ referenced_var_iterator i;
+ tree var;
+
+ fprintf (file, "\n\nCurrent reaching definitions\n\n");
+ FOR_EACH_REFERENCED_VAR (var, i)
+ if (syms_to_rename == NULL || bitmap_bit_p (syms_to_rename, DECL_UID (var)))
+ {
+ fprintf (file, "CURRDEF (");
+ print_generic_expr (file, var, 0);
+ fprintf (file, ") = ");
+ if (get_current_def (var))
+ print_generic_expr (file, get_current_def (var), 0);
+ else
+ fprintf (file, "<NIL>");
+ fprintf (file, "\n");
+ }
+}
+
+
+/* Dump the current reaching definition of every symbol to stderr. */
+
+void
+debug_currdefs (void)
+{
+ dump_currdefs (stderr);
+}
+
+
+/* Dump SSA information to FILE. */
+
+void
+dump_tree_ssa (FILE *file)
+{
+ const char *funcname
+ = lang_hooks.decl_printable_name (current_function_decl, 2);
+
+ fprintf (file, "SSA renaming information for %s\n\n", funcname);
+
+ dump_def_blocks (file);
+ dump_defs_stack (file, -1);
+ dump_currdefs (file);
+ dump_tree_ssa_stats (file);
+}
+
+
+/* Dump SSA information to stderr. */
+
+void
+debug_tree_ssa (void)
+{
+ dump_tree_ssa (stderr);
+}
+
+
+/* Dump statistics for the hash table HTAB. */
+
+static void
+htab_statistics (FILE *file, htab_t htab)
+{
+ fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
+ (long) htab_size (htab),
+ (long) htab_elements (htab),
+ htab_collisions (htab));
+}
+
+
+/* Dump SSA statistics on FILE. */
+
+void
+dump_tree_ssa_stats (FILE *file)
+{
+ if (def_blocks || repl_tbl)
+ fprintf (file, "\nHash table statistics:\n");
+
+ if (def_blocks)
+ {
+ fprintf (file, " def_blocks: ");
+ htab_statistics (file, def_blocks);
+ }
+
+ if (repl_tbl)
+ {
+ fprintf (file, " repl_tbl: ");
+ htab_statistics (file, repl_tbl);
+ }
+
+ if (def_blocks || repl_tbl)
+ fprintf (file, "\n");
+}
+
+
+/* Dump SSA statistics on stderr. */
+
+void
+debug_tree_ssa_stats (void)
+{
+ dump_tree_ssa_stats (stderr);
+}
+
+
+/* Hashing and equality functions for DEF_BLOCKS. */
+
+static hashval_t
+def_blocks_hash (const void *p)
+{
+ return htab_hash_pointer
+ ((const void *)((const struct def_blocks_d *)p)->var);
+}
+
+static int
+def_blocks_eq (const void *p1, const void *p2)
+{
+ return ((const struct def_blocks_d *)p1)->var
+ == ((const struct def_blocks_d *)p2)->var;
+}
+
+
+/* Free memory allocated by one entry in DEF_BLOCKS. */
+
+static void
+def_blocks_free (void *p)
+{
+ struct def_blocks_d *entry = (struct def_blocks_d *) p;
+ BITMAP_FREE (entry->def_blocks);
+ BITMAP_FREE (entry->phi_blocks);
+ BITMAP_FREE (entry->livein_blocks);
+ free (entry);
+}
+
+
+/* Callback for htab_traverse to dump the DEF_BLOCKS hash table. */
+
+static int
+debug_def_blocks_r (void **slot, void *data)
+{
+ FILE *file = (FILE *) data;
+ struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
+
+ fprintf (file, "VAR: ");
+ print_generic_expr (file, db_p->var, dump_flags);
+ bitmap_print (file, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
+ bitmap_print (file, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}");
+ bitmap_print (file, db_p->phi_blocks, ", PHI_BLOCKS: { ", "}\n");
+
+ return 1;
+}
+
+
+/* Dump the DEF_BLOCKS hash table on FILE. */
+
+void
+dump_def_blocks (FILE *file)
+{
+ fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
+ if (def_blocks)
+ htab_traverse (def_blocks, debug_def_blocks_r, file);
+}
+
+
+/* Dump the DEF_BLOCKS hash table on stderr. */
+
+void
+debug_def_blocks (void)
+{
+ dump_def_blocks (stderr);
+}
+
+
+/* Register NEW_NAME to be the new reaching definition for OLD_NAME. */
+
+static inline void
+register_new_update_single (tree new_name, tree old_name)
+{
+ tree currdef = get_current_def (old_name);
+
+ /* Push the current reaching definition into BLOCK_DEFS_STACK.
+ 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. */
+ VEC_reserve (tree, heap, block_defs_stack, 2);
+ VEC_quick_push (tree, block_defs_stack, currdef);
+ VEC_quick_push (tree, block_defs_stack, old_name);
+
+ /* Set the current reaching definition for OLD_NAME to be
+ NEW_NAME. */
+ set_current_def (old_name, new_name);
+}
+
+
+/* Register NEW_NAME to be the new reaching definition for all the
+ names in OLD_NAMES. Used by the incremental SSA update routines to
+ replace old SSA names with new ones. */
+
+static inline void
+register_new_update_set (tree new_name, bitmap old_names)
+{
+ bitmap_iterator bi;
+ unsigned i;
+
+ EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
+ register_new_update_single (new_name, ssa_name (i));
+}
+
+
+/* Initialization of block data structures for the incremental SSA
+ update pass. 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_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+ tree phi;
+ bool is_abnormal_phi;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
+ bb->index);
+
+ /* Mark the unwind point for this block. */
+ VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
+
+ if (!bitmap_bit_p (blocks_to_update, bb->index))
+ return;
+
+ /* Mark the LHS if any of the arguments flows through an abnormal
+ edge. */
+ is_abnormal_phi = false;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ is_abnormal_phi = true;
+ break;
+ }
+
+ /* If any of the PHI nodes is a replacement for a name in
+ OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
+ register it as a new definition for its corresponding name. Also
+ register definitions for names whose underlying symbols are
+ marked for renaming. */
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ tree lhs, lhs_sym;
+
+ if (!REGISTER_DEFS_IN_THIS_STMT (phi))
+ continue;
+
+ lhs = PHI_RESULT (phi);
+ lhs_sym = SSA_NAME_VAR (lhs);
+
+ if (symbol_marked_for_renaming (lhs_sym))
+ register_new_update_single (lhs, lhs_sym);
+ else
+ {
+
+ /* If LHS is a new name, register a new definition for all
+ the names replaced by LHS. */
+ if (is_new_name (lhs))
+ register_new_update_set (lhs, names_replaced_by (lhs));
+
+ /* If LHS is an OLD name, register it as a new definition
+ for itself. */
+ if (is_old_name (lhs))
+ register_new_update_single (lhs, lhs);
+ }
+
+ if (is_abnormal_phi)
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
+ }
+}
+
+
+/* Called after visiting block BB. Unwind BLOCK_DEFS_STACK to restore
+ the current reaching definition of every name re-written in BB to
+ the original reaching definition before visiting BB. This
+ unwinding must be done in the opposite order to what is done in
+ register_new_update_set. */
+
+static void
+rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb ATTRIBUTE_UNUSED)
+{
+ while (VEC_length (tree, block_defs_stack) > 0)
+ {
+ tree var = VEC_pop (tree, block_defs_stack);
+ tree saved_def;
+
+ /* NULL indicates the unwind stop point for this block (see
+ rewrite_update_init_block). */
+ if (var == NULL)
+ return;
+
+ saved_def = VEC_pop (tree, block_defs_stack);
+ set_current_def (var, saved_def);
+ }
+}
+
+
+/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
+ it is a symbol marked for renaming, replace it with USE_P's current
+ reaching definition. */
+
+static inline void
+maybe_replace_use (use_operand_p use_p)
+{
+ tree rdef = NULL_TREE;
+ tree use = USE_FROM_PTR (use_p);
+ tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
+
+ if (symbol_marked_for_renaming (sym))
+ rdef = get_reaching_def (sym);
+ else if (is_old_name (use))
+ rdef = get_reaching_def (use);
+
+ if (rdef && rdef != use)
+ SET_USE (use_p, rdef);
+}
+
+
+/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
+ or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
+ register it as the current definition for the names replaced by
+ DEF_P. */
+
+static inline void
+maybe_register_def (def_operand_p def_p, tree stmt)
+{
+ tree def = DEF_FROM_PTR (def_p);
+ tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
+
+ /* If DEF is a naked symbol that needs renaming, create a new
+ name for it. */
+ if (symbol_marked_for_renaming (sym))
+ {
+ if (DECL_P (def))
+ {
+ def = make_ssa_name (def, stmt);
+ SET_DEF (def_p, def);
+ }
+
+ register_new_update_single (def, sym);
+ }
+ else
+ {
+ /* If DEF is a new name, register it as a new definition
+ for all the names replaced by DEF. */
+ if (is_new_name (def))
+ register_new_update_set (def, names_replaced_by (def));
+
+ /* If DEF is an old name, register DEF as a new
+ definition for itself. */
+ if (is_old_name (def))
+ register_new_update_single (def, def);
+ }
+}
+
+
+/* Update every variable used in the statement pointed-to by SI. The
+ statement is assumed to be in SSA form already. Names in
+ OLD_SSA_NAMES used by SI will be updated to their current reaching
+ definition. Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
+ will be registered as a new definition for their corresponding name
+ in OLD_SSA_NAMES. */
+
+static void
+rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb ATTRIBUTE_UNUSED,
+ block_stmt_iterator si)
+{
+ stmt_ann_t ann;
+ tree stmt;
+ use_operand_p use_p;
+ def_operand_p def_p;
+ ssa_op_iter iter;
+
+ stmt = bsi_stmt (si);