+/* 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);
+ ann = stmt_ann (stmt);
+
+ gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
+
+ /* Only update marked statements. */
+ if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
+ return;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Updating SSA information for statement ");
+ print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+
+ /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
+ symbol is marked for renaming. */
+ if (REWRITE_THIS_STMT (stmt))
+ {
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+ maybe_replace_use (use_p);
+
+ if (need_to_update_vops_p)
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
+ maybe_replace_use (use_p);
+ }
+
+ /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
+ Also register definitions for names whose underlying symbol is
+ marked for renaming. */
+ if (REGISTER_DEFS_IN_THIS_STMT (stmt))
+ {
+ FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
+ maybe_register_def (def_p, stmt);
+
+ if (need_to_update_vops_p)
+ FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+ maybe_register_def (def_p, stmt);
+ }
+}
+
+
+/* Visit all the successor blocks of BB looking for PHI nodes. For
+ every PHI node found, check if any of its arguments is in
+ OLD_SSA_NAMES. If so, and if the argument has a current reaching
+ definition, replace it. */
+
+static void
+rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb)
+{
+ edge e;
+ edge_iterator ei;
+ unsigned i;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ tree phi;
+ tree_vec phis;
+
+ if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
+ continue;
+
+ phis = VEC_index (tree_vec, phis_to_rewrite, e->dest->index);
+ for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
+ {
+ tree arg, lhs_sym;
+ use_operand_p arg_p;
+
+ gcc_assert (REWRITE_THIS_STMT (phi));
+
+ arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
+ arg = USE_FROM_PTR (arg_p);
+
+ if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
+ continue;
+
+ lhs_sym = SSA_NAME_VAR (PHI_RESULT (phi));
+
+ if (arg == NULL_TREE)
+ {
+ /* When updating a PHI node for a recently introduced
+ symbol we may find NULL arguments. That's why we
+ take the symbol from the LHS of the PHI node. */
+ SET_USE (arg_p, get_reaching_def (lhs_sym));
+ }
+ else
+ {
+ tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
+
+ if (symbol_marked_for_renaming (sym))
+ SET_USE (arg_p, get_reaching_def (sym));
+ else if (is_old_name (arg))
+ SET_USE (arg_p, get_reaching_def (arg));
+ }
+
+ if (e->flags & EDGE_ABNORMAL)
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
+ }
+ }
+}
+
+
+/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
+ form.
+
+ ENTRY indicates the block where to start. Every block dominated by
+ ENTRY will be rewritten.
+
+ WHAT indicates what actions will be taken by the renamer (see enum
+ rewrite_mode).
+
+ BLOCKS are the set of interesting blocks for the dominator walker
+ to process. If this set is NULL, then all the nodes dominated
+ by ENTRY are walked. Otherwise, blocks dominated by ENTRY that
+ are not present in BLOCKS are ignored. */
+
+static void
+rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
+{
+ struct dom_walk_data walk_data;
+
+ /* Rewrite all the basic blocks in the program. */
+ timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
+
+ /* Setup callbacks for the generic dominator tree walker. */
+ memset (&walk_data, 0, sizeof (walk_data));
+
+ walk_data.dom_direction = CDI_DOMINATORS;
+ walk_data.interesting_blocks = blocks;
+
+ if (what == REWRITE_ALL)
+ walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
+ else
+ walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
+
+ if (what == REWRITE_ALL)
+ walk_data.before_dom_children_walk_stmts = rewrite_stmt;
+ else if (what == REWRITE_UPDATE)
+ walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
+ else
+ gcc_unreachable ();
+
+ if (what == REWRITE_ALL)
+ walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
+ else if (what == REWRITE_UPDATE)
+ walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
+ else
+ gcc_unreachable ();
+
+ if (what == REWRITE_ALL)
+ walk_data.after_dom_children_after_stmts = rewrite_finalize_block;
+ else if (what == REWRITE_UPDATE)
+ walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
+ else
+ gcc_unreachable ();
+
+ block_defs_stack = VEC_alloc (tree, heap, 10);
+
+ /* Initialize the dominator walker. */
+ init_walk_dominator_tree (&walk_data);
+
+ /* Recursively walk the dominator tree rewriting each statement in
+ each basic block. */
+ walk_dominator_tree (&walk_data, entry);
+
+ /* Finalize the dominator walker. */
+ fini_walk_dominator_tree (&walk_data);
+
+ /* Debugging dumps. */
+ if (dump_file && (dump_flags & TDF_STATS))
+ {
+ dump_dfa_stats (dump_file);
+ if (def_blocks)
+ dump_tree_ssa_stats (dump_file);
+ }
+
+ VEC_free (tree, heap, block_defs_stack);
+
+ timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
+}
+
+
+/* Block initialization routine for mark_def_sites. Clear the
+ KILLS bitmap at the start of each block. */
+
+static void
+mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
+ basic_block bb ATTRIBUTE_UNUSED)
+{
+ struct mark_def_sites_global_data *gd;
+ gd = (struct mark_def_sites_global_data *) walk_data->global_data;
+ bitmap_clear (gd->kills);
+}
+
+
+/* Mark the definition site blocks for each variable, so that we know
+ where the variable is actually live.
+
+ INTERESTING_BLOCKS will be filled in with all the blocks that
+ should be processed by the renamer. It is assumed to be
+ initialized and zeroed by the caller. */
+
+static void
+mark_def_site_blocks (sbitmap interesting_blocks)
+{
+ struct dom_walk_data walk_data;
+ struct mark_def_sites_global_data mark_def_sites_global_data;
+
+ /* Setup callbacks for the generic dominator tree walker to find and
+ mark definition sites. */
+ walk_data.walk_stmts_backward = false;
+ walk_data.dom_direction = CDI_DOMINATORS;
+ walk_data.initialize_block_local_data = NULL;
+ walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
+ walk_data.before_dom_children_walk_stmts = mark_def_sites;
+ walk_data.before_dom_children_after_stmts = NULL;
+ walk_data.after_dom_children_before_stmts = NULL;
+ walk_data.after_dom_children_walk_stmts = NULL;
+ walk_data.after_dom_children_after_stmts = NULL;
+ walk_data.interesting_blocks = NULL;
+
+ /* Notice that this bitmap is indexed using variable UIDs, so it must be
+ large enough to accommodate all the variables referenced in the
+ function, not just the ones we are renaming. */
+ mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
+
+ /* Create the set of interesting blocks that will be filled by
+ mark_def_sites. */
+ mark_def_sites_global_data.interesting_blocks = interesting_blocks;
+ walk_data.global_data = &mark_def_sites_global_data;
+
+ /* We do not have any local data. */
+ walk_data.block_local_data_size = 0;
+
+ /* Initialize the dominator walker. */
+ init_walk_dominator_tree (&walk_data);
+
+ /* Recursively walk the dominator tree. */
+ walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+
+ /* Finalize the dominator walker. */
+ fini_walk_dominator_tree (&walk_data);
+
+ /* We no longer need this bitmap, clear and free it. */
+ BITMAP_FREE (mark_def_sites_global_data.kills);
+}
+
+
+/* Initialize internal data needed during renaming. */
+
+static void
+init_ssa_renamer (void)
+{
+ tree var;
+ referenced_var_iterator rvi;
+
+ cfun->gimple_df->in_ssa_p = false;
+
+ /* Allocate memory for the DEF_BLOCKS hash table. */
+ gcc_assert (def_blocks == NULL);
+ def_blocks = htab_create (num_referenced_vars, def_blocks_hash,
+ def_blocks_eq, def_blocks_free);
+
+ FOR_EACH_REFERENCED_VAR(var, rvi)
+ set_current_def (var, NULL_TREE);
+}
+
+
+/* Deallocate internal data structures used by the renamer. */
+
+static void
+fini_ssa_renamer (void)
+{
+ if (def_blocks)
+ {
+ htab_delete (def_blocks);
+ def_blocks = NULL;
+ }
+
+ cfun->gimple_df->in_ssa_p = true;
+}
+
+
+/* Main entry point into the SSA builder. The renaming process
+ proceeds in four main phases:
+
+ 1- Compute dominance frontier and immediate dominators, needed to
+ insert PHI nodes and rename the function in dominator tree
+ order.
+
+ 2- Find and mark all the blocks that define variables
+ (mark_def_site_blocks).
+
+ 3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
+
+ 4- Rename all the blocks (rewrite_blocks) and statements in the program.
+
+ Steps 3 and 4 are done using the dominator tree walker
+ (walk_dominator_tree). */
+
+static unsigned int
+rewrite_into_ssa (void)
+{
+ bitmap *dfs;
+ basic_block bb;
+ sbitmap interesting_blocks;
+
+ timevar_push (TV_TREE_SSA_OTHER);
+
+ /* Initialize operand data structures. */
+ init_ssa_operands ();
+
+ /* Initialize internal data needed by the renamer. */
+ init_ssa_renamer ();
+
+ /* Initialize the set of interesting blocks. The callback
+ mark_def_sites will add to this set those blocks that the renamer
+ should process. */
+ interesting_blocks = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (interesting_blocks);
+
+ /* Initialize dominance frontier. */
+ dfs = XNEWVEC (bitmap, last_basic_block);
+ FOR_EACH_BB (bb)
+ dfs[bb->index] = BITMAP_ALLOC (NULL);
+
+ /* 1- Compute dominance frontiers. */
+ calculate_dominance_info (CDI_DOMINATORS);
+ compute_dominance_frontiers (dfs);
+
+ /* 2- Find and mark definition sites. */
+ mark_def_site_blocks (interesting_blocks);
+
+ /* 3- Insert PHI nodes at dominance frontiers of definition blocks. */
+ insert_phi_nodes (dfs);
+
+ /* 4- Rename all the blocks. */
+ rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
+
+ /* Free allocated memory. */
+ FOR_EACH_BB (bb)
+ BITMAP_FREE (dfs[bb->index]);
+ free (dfs);
+ sbitmap_free (interesting_blocks);
+
+ fini_ssa_renamer ();
+
+ timevar_pop (TV_TREE_SSA_OTHER);
+ return 0;
+}
+
+
+struct gimple_opt_pass pass_build_ssa =
+{
+ {
+ GIMPLE_PASS,
+ "ssa", /* name */
+ NULL, /* gate */
+ rewrite_into_ssa, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_cfg | PROP_referenced_vars, /* properties_required */
+ PROP_ssa, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func
+ | TODO_verify_ssa
+ | TODO_remove_unused_locals /* todo_flags_finish */
+ }
+};
+
+
+/* Mark the definition of VAR at STMT and BB as interesting for the
+ renamer. BLOCKS is the set of blocks that need updating. */
+
+static void
+mark_def_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
+{
+ gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
+ REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
+
+ if (insert_phi_p)
+ {
+ bool is_phi_p = TREE_CODE (stmt) == PHI_NODE;
+
+ set_def_block (var, bb, is_phi_p);
+
+ /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
+ site for both itself and all the old names replaced by it. */
+ if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
+ {
+ bitmap_iterator bi;
+ unsigned i;
+ bitmap set = names_replaced_by (var);
+ if (set)
+ EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
+ set_def_block (ssa_name (i), bb, is_phi_p);
+ }
+ }
+}
+
+
+/* Mark the use of VAR at STMT and BB as interesting for the
+ renamer. INSERT_PHI_P is true if we are going to insert new PHI
+ nodes. */
+
+static inline void
+mark_use_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
+{
+ basic_block def_bb = bb_for_stmt (stmt);
+
+ mark_block_for_update (def_bb);
+ mark_block_for_update (bb);
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ mark_phi_for_rewrite (def_bb, stmt);
+ else
+ REWRITE_THIS_STMT (stmt) = 1;
+
+ /* If VAR has not been defined in BB, then it is live-on-entry
+ to BB. Note that we cannot just use the block holding VAR's
+ definition because if VAR is one of the names in OLD_SSA_NAMES,
+ it will have several definitions (itself and all the names that
+ replace it). */
+ if (insert_phi_p)
+ {
+ struct def_blocks_d *db_p = get_def_blocks_for (var);
+ if (!bitmap_bit_p (db_p->def_blocks, bb->index))
+ set_livein_block (var, bb);
+ }
+}
+
+
+/* Do a dominator walk starting at BB processing statements that
+ reference symbols in SYMS_TO_RENAME. This is very similar to
+ mark_def_sites, but the scan handles statements whose operands may
+ already be SSA names.
+
+ If INSERT_PHI_P is true, mark those uses as live in the
+ corresponding block. This is later used by the PHI placement
+ algorithm to make PHI pruning decisions.
+
+ FIXME. Most of this would be unnecessary if we could associate a
+ symbol to all the SSA names that reference it. But that
+ sounds like it would be expensive to maintain. Still, it
+ would be interesting to see if it makes better sense to do
+ that. */
+
+static void
+prepare_block_for_update (basic_block bb, bool insert_phi_p)
+{
+ basic_block son;
+ block_stmt_iterator si;
+ tree phi;
+ edge e;
+ edge_iterator ei;
+
+ mark_block_for_update (bb);
+
+ /* Process PHI nodes marking interesting those that define or use
+ the symbols that we are interested in. */
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ tree lhs_sym, lhs = PHI_RESULT (phi);
+
+ lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
+
+ if (!symbol_marked_for_renaming (lhs_sym))
+ continue;
+ mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
+
+ /* Mark the uses in phi nodes as interesting. It would be more correct
+ to process the arguments of the phi nodes of the successor edges of
+ BB at the end of prepare_block_for_update, however, that turns out
+ to be significantly more expensive. Doing it here is conservatively
+ correct -- it may only cause us to believe a value to be live in a
+ block that also contains its definition, and thus insert a few more
+ phi nodes for it. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
+ }
+ }
+
+ /* Process the statements. */
+ for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ {
+ tree stmt;
+ ssa_op_iter i;
+ use_operand_p use_p;
+ def_operand_p def_p;
+
+ stmt = bsi_stmt (si);
+
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
+ {
+ tree use = USE_FROM_PTR (use_p);
+ tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
+ if (symbol_marked_for_renaming (sym))
+ mark_use_interesting (sym, stmt, bb, insert_phi_p);
+ }
+
+ FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_ALL_DEFS)
+ {
+ tree def = DEF_FROM_PTR (def_p);
+ tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
+ if (symbol_marked_for_renaming (sym))
+ mark_def_interesting (sym, stmt, bb, insert_phi_p);
+ }
+ }
+
+ /* Now visit all the blocks dominated by BB. */
+ for (son = first_dom_son (CDI_DOMINATORS, bb);
+ son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ prepare_block_for_update (son, insert_phi_p);
+}
+
+
+/* Helper for prepare_names_to_update. Mark all the use sites for
+ NAME as interesting. BLOCKS and INSERT_PHI_P are as in
+ prepare_names_to_update. */
+
+static void
+prepare_use_sites_for (tree name, bool insert_phi_p)
+{
+ use_operand_p use_p;
+ imm_use_iterator iter;
+
+ FOR_EACH_IMM_USE_FAST (use_p, iter, name)
+ {
+ tree stmt = USE_STMT (use_p);
+ basic_block bb = bb_for_stmt (stmt);
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ {
+ int ix = PHI_ARG_INDEX_FROM_USE (use_p);
+ edge e = PHI_ARG_EDGE (stmt, ix);
+ mark_use_interesting (name, stmt, e->src, insert_phi_p);
+ }
+ else
+ {
+ /* For regular statements, mark this as an interesting use
+ for NAME. */
+ mark_use_interesting (name, stmt, bb, insert_phi_p);
+ }
+ }
+}
+
+
+/* Helper for prepare_names_to_update. Mark the definition site for
+ NAME as interesting. BLOCKS and INSERT_PHI_P are as in
+ prepare_names_to_update. */
+
+static void
+prepare_def_site_for (tree name, bool insert_phi_p)
+{
+ tree stmt;
+ basic_block bb;
+
+ gcc_assert (names_to_release == NULL
+ || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
+
+ stmt = SSA_NAME_DEF_STMT (name);
+ bb = bb_for_stmt (stmt);
+ if (bb)
+ {
+ gcc_assert (bb->index < last_basic_block);
+ mark_block_for_update (bb);
+ mark_def_interesting (name, stmt, bb, insert_phi_p);
+ }
+}
+
+
+/* Mark definition and use sites of names in NEW_SSA_NAMES and
+ OLD_SSA_NAMES. INSERT_PHI_P is true if the caller wants to insert
+ PHI nodes for newly created names. */
+
+static void
+prepare_names_to_update (bool insert_phi_p)
+{
+ unsigned i = 0;
+ bitmap_iterator bi;
+ sbitmap_iterator sbi;
+
+ /* If a name N from NEW_SSA_NAMES is also marked to be released,
+ remove it from NEW_SSA_NAMES so that we don't try to visit its
+ defining basic block (which most likely doesn't exist). Notice
+ that we cannot do the same with names in OLD_SSA_NAMES because we
+ want to replace existing instances. */
+ if (names_to_release)
+ EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
+ RESET_BIT (new_ssa_names, i);
+
+ /* First process names in NEW_SSA_NAMES. Otherwise, uses of old
+ names may be considered to be live-in on blocks that contain
+ definitions for their replacements. */
+ EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
+ prepare_def_site_for (ssa_name (i), insert_phi_p);
+
+ /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
+ OLD_SSA_NAMES, but we have to ignore its definition site. */
+ EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
+ {
+ if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
+ prepare_def_site_for (ssa_name (i), insert_phi_p);
+ prepare_use_sites_for (ssa_name (i), insert_phi_p);
+ }
+}
+
+
+/* Dump all the names replaced by NAME to FILE. */
+
+void
+dump_names_replaced_by (FILE *file, tree name)
+{
+ unsigned i;
+ bitmap old_set;
+ bitmap_iterator bi;
+
+ print_generic_expr (file, name, 0);
+ fprintf (file, " -> { ");
+
+ old_set = names_replaced_by (name);
+ EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
+ {
+ print_generic_expr (file, ssa_name (i), 0);
+ fprintf (file, " ");
+ }
+
+ fprintf (file, "}\n");
+}
+
+
+/* Dump all the names replaced by NAME to stderr. */
+
+void
+debug_names_replaced_by (tree name)
+{
+ dump_names_replaced_by (stderr, name);
+}
+
+
+/* Dump SSA update information to FILE. */
+
+void
+dump_update_ssa (FILE *file)
+{
+ unsigned i = 0;
+ bitmap_iterator bi;
+
+ if (!need_ssa_update_p ())
+ return;
+
+ if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
+ {
+ sbitmap_iterator sbi;
+
+ fprintf (file, "\nSSA replacement table\n");
+ fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
+ "O_1, ..., O_j\n\n");
+
+ EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
+ dump_names_replaced_by (file, ssa_name (i));
+
+ fprintf (file, "\n");
+ fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
+ update_ssa_stats.num_virtual_mappings);
+ fprintf (file, "Number of real NEW -> OLD mappings: %7u\n",
+ update_ssa_stats.num_total_mappings
+ - update_ssa_stats.num_virtual_mappings);
+ fprintf (file, "Number of total NEW -> OLD mappings: %7u\n",
+ update_ssa_stats.num_total_mappings);
+
+ fprintf (file, "\nNumber of virtual symbols: %u\n",
+ update_ssa_stats.num_virtual_symbols);
+ }
+
+ if (syms_to_rename && !bitmap_empty_p (syms_to_rename))
+ {
+ fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
+ dump_decl_set (file, syms_to_rename);
+ }
+
+ if (names_to_release && !bitmap_empty_p (names_to_release))
+ {
+ fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
+ EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
+ {
+ print_generic_expr (file, ssa_name (i), 0);
+ fprintf (file, " ");
+ }
+ }
+
+ fprintf (file, "\n\n");
+}
+
+
+/* Dump SSA update information to stderr. */
+
+void
+debug_update_ssa (void)
+{
+ dump_update_ssa (stderr);
+}
+
+
+/* Initialize data structures used for incremental SSA updates. */
+
+static void
+init_update_ssa (void)
+{
+ /* Reserve more space than the current number of names. The calls to
+ add_new_name_mapping are typically done after creating new SSA
+ names, so we'll need to reallocate these arrays. */
+ old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
+ sbitmap_zero (old_ssa_names);
+
+ new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
+ sbitmap_zero (new_ssa_names);
+
+ repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
+ need_to_initialize_update_ssa_p = false;
+ need_to_update_vops_p = false;
+ syms_to_rename = BITMAP_ALLOC (NULL);
+ regs_to_rename = BITMAP_ALLOC (NULL);
+ mem_syms_to_rename = BITMAP_ALLOC (NULL);
+ names_to_release = NULL;
+ memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
+ update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
+}
+
+
+/* Deallocate data structures used for incremental SSA updates. */
+
+void
+delete_update_ssa (void)
+{
+ unsigned i;
+ bitmap_iterator bi;
+
+ sbitmap_free (old_ssa_names);
+ old_ssa_names = NULL;
+
+ sbitmap_free (new_ssa_names);
+ new_ssa_names = NULL;
+
+ htab_delete (repl_tbl);
+ repl_tbl = NULL;
+
+ need_to_initialize_update_ssa_p = true;
+ need_to_update_vops_p = false;
+ BITMAP_FREE (syms_to_rename);
+ BITMAP_FREE (regs_to_rename);
+ BITMAP_FREE (mem_syms_to_rename);
+ BITMAP_FREE (update_ssa_stats.virtual_symbols);
+
+ if (names_to_release)
+ {
+ EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
+ release_ssa_name (ssa_name (i));
+ BITMAP_FREE (names_to_release);
+ }
+
+ clear_ssa_name_info ();
+
+ fini_ssa_renamer ();
+
+ if (blocks_with_phis_to_rewrite)
+ EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
+ {
+ tree_vec phis = VEC_index (tree_vec, phis_to_rewrite, i);
+
+ VEC_free (tree, heap, phis);
+ VEC_replace (tree_vec, phis_to_rewrite, i, NULL);
+ }
+
+ BITMAP_FREE (blocks_with_phis_to_rewrite);
+ BITMAP_FREE (blocks_to_update);
+}
+
+
+/* Create a new name for OLD_NAME in statement STMT and replace the
+ operand pointed to by DEF_P with the newly created name. Return
+ the new name and register the replacement mapping <NEW, OLD> in
+ update_ssa's tables. */
+
+tree
+create_new_def_for (tree old_name, tree stmt, def_operand_p def)
+{
+ tree new_name = duplicate_ssa_name (old_name, stmt);
+
+ SET_DEF (def, new_name);
+
+ if (TREE_CODE (stmt) == PHI_NODE)
+ {
+ edge e;
+ edge_iterator ei;
+ basic_block bb = bb_for_stmt (stmt);
+
+ /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
+ break;
+ }
+ }
+
+ register_new_name_mapping (new_name, old_name);
+
+ /* For the benefit of passes that will be updating the SSA form on
+ their own, set the current reaching definition of OLD_NAME to be
+ NEW_NAME. */
+ set_current_def (old_name, new_name);
+
+ return new_name;
+}
+
+
+/* Register name NEW to be a replacement for name OLD. This function
+ must be called for every replacement that should be performed by
+ update_ssa. */
+
+void
+register_new_name_mapping (tree new, tree old)
+{
+ if (need_to_initialize_update_ssa_p)
+ init_update_ssa ();
+
+ add_new_name_mapping (new, old);
+}
+
+
+/* Register symbol SYM to be renamed by update_ssa. */
+
+void
+mark_sym_for_renaming (tree sym)
+{
+ if (need_to_initialize_update_ssa_p)
+ init_update_ssa ();
+
+ bitmap_set_bit (syms_to_rename, DECL_UID (sym));
+
+ if (!is_gimple_reg (sym))
+ {
+ need_to_update_vops_p = true;
+ if (memory_partition (sym))
+ bitmap_set_bit (syms_to_rename, DECL_UID (memory_partition (sym)));
+ }
+}
+
+
+/* Register all the symbols in SET to be renamed by update_ssa. */