+
+/* Call back for walk_dominator_tree used to collect definition sites
+ for every variable in the function. For every statement S in block
+ BB:
+
+ 1- Variables defined by S in the DEFS of S are marked in the bitmap
+ WALK_DATA->GLOBAL_DATA->KILLS.
+
+ 2- If S uses a variable VAR and there is no preceding kill of VAR,
+ then it is marked in marked in the LIVEIN_BLOCKS bitmap
+ associated with VAR.
+
+ This information is used to determine which variables are live
+ across block boundaries to reduce the number of PHI nodes
+ we create. */
+
+static void
+mark_def_sites (struct dom_walk_data *walk_data,
+ basic_block bb,
+ block_stmt_iterator bsi)
+{
+ struct mark_def_sites_global_data *gd = walk_data->global_data;
+ bitmap kills = gd->kills;
+ tree stmt, def;
+ use_operand_p use_p;
+ def_operand_p def_p;
+ ssa_op_iter iter;
+
+ stmt = bsi_stmt (bsi);
+ update_stmt_if_modified (stmt);
+
+ REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
+ REWRITE_THIS_STMT (stmt) = 0;
+
+ /* If a variable is used before being set, then the variable is live
+ across a block boundary, so mark it live-on-entry to BB. */
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
+ SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTKILL)
+ {
+ tree sym = USE_FROM_PTR (use_p);
+ gcc_assert (DECL_P (sym));
+ if (!bitmap_bit_p (kills, var_ann (sym)->uid))
+ set_livein_block (sym, bb);
+ REWRITE_THIS_STMT (stmt) = 1;
+ }
+
+ /* Note that virtual definitions are irrelevant for computing KILLS
+ because a V_MAY_DEF does not constitute a killing definition of the
+ variable. However, the operand of a virtual definitions is a use
+ of the variable, so it may cause the variable to be considered
+ live-on-entry. */
+ FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
+ {
+ tree sym = USE_FROM_PTR (use_p);
+ gcc_assert (DECL_P (sym));
+ set_livein_block (sym, bb);
+ set_def_block (sym, bb, false);
+ REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
+ REWRITE_THIS_STMT (stmt) = 1;
+ }
+
+ /* Now process the defs and must-defs made by this statement. */
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
+ {
+ gcc_assert (DECL_P (def));
+ set_def_block (def, bb, false);
+ bitmap_set_bit (kills, var_ann (def)->uid);
+ REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
+ }
+
+ /* If we found the statement interesting then also mark the block BB
+ as interesting. */
+ if (REWRITE_THIS_STMT (stmt) || REGISTER_DEFS_IN_THIS_STMT (stmt))
+ SET_BIT (gd->interesting_blocks, bb->index);
+}
+
+
+/* Given a set of blocks with variable definitions (DEF_BLOCKS),
+ return a bitmap with all the blocks in the iterated dominance
+ frontier of the blocks in DEF_BLOCKS. DFS contains dominance
+ frontier information as returned by compute_dominance_frontiers.
+
+ The resulting set of blocks are the potential sites where PHI nodes
+ are needed. The caller is responsible from freeing the memory
+ allocated for the return value. */
+
+static bitmap
+find_idf (bitmap def_blocks, bitmap *dfs)
+{
+ bitmap_iterator bi;
+ unsigned bb_index;
+ VEC(int,heap) *work_stack;
+ bitmap phi_insertion_points;
+
+ work_stack = VEC_alloc (int, heap, n_basic_blocks);
+ phi_insertion_points = BITMAP_ALLOC (NULL);
+
+ /* Seed the work list with all the blocks in DEF_BLOCKS. */
+ EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
+ /* We use VEC_quick_push here for speed. This is safe because we
+ know that the number of definition blocks is no greater than
+ the number of basic blocks, which is the initial capacity of
+ WORK_STACK. */
+ VEC_quick_push (int, work_stack, bb_index);
+
+ /* Pop a block off the worklist, add every block that appears in
+ the original block's DF that we have not already processed to
+ the worklist. Iterate until the worklist is empty. Blocks
+ which are added to the worklist are potential sites for
+ PHI nodes. */
+ while (VEC_length (int, work_stack) > 0)
+ {
+ bb_index = VEC_pop (int, work_stack);
+
+ /* Since the registration of NEW -> OLD name mappings is done
+ separately from the call to update_ssa, when updating the SSA
+ form, the basic blocks where new and/or old names are defined
+ may have disappeared by CFG cleanup calls. In this case,
+ we may pull a non-existing block from the work stack. */
+ gcc_assert (bb_index < (unsigned) last_basic_block);
+
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
+ 0, bb_index, bi)
+ {
+ /* Use a safe push because if there is a definition of VAR
+ in every basic block, then WORK_STACK may eventually have
+ more than N_BASIC_BLOCK entries. */
+ VEC_safe_push (int, heap, work_stack, bb_index);
+ bitmap_set_bit (phi_insertion_points, bb_index);
+ }
+ }
+
+ VEC_free (int, heap, work_stack);
+
+ return phi_insertion_points;
+}
+
+
+/* Return the set of blocks where variable VAR is defined and the blocks
+ where VAR is live on entry (livein). Return NULL, if no entry is
+ found in DEF_BLOCKS. */
+
+static inline struct def_blocks_d *
+find_def_blocks_for (tree var)
+{
+ struct def_blocks_d dm;
+ dm.var = var;
+ return (struct def_blocks_d *) htab_find (def_blocks, &dm);
+}
+
+
+/* Retrieve or create a default definition for symbol SYM. */
+
+static inline tree
+get_default_def_for (tree sym)
+{
+ tree ddef = default_def (sym);
+
+ if (ddef == NULL_TREE)
+ {
+ ddef = make_ssa_name (sym, build_empty_stmt ());
+ set_default_def (sym, ddef);
+ }
+
+ return ddef;
+}
+
+
+/* Insert PHI nodes for variable VAR using the iterated dominance
+ frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
+ function assumes that the caller is incrementally updating the SSA
+ form, in which case (1) VAR is assumed to be an SSA name, (2) a new
+ SSA name is created for VAR's symbol, and, (3) all the arguments
+ for the newly created PHI node are set to VAR.
+
+ PHI_INSERTION_POINTS is updated to reflect nodes that already had a
+ PHI node for VAR. On exit, only the nodes that received a PHI node
+ for VAR will be present in PHI_INSERTION_POINTS. */
+
+static void
+insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
+{
+ 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);
+ gcc_assert (def_map);
+
+ /* 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);
+
+ if (update_p && TREE_CODE (var) == SSA_NAME)
+ {
+ /* If we are rewriting SSA names, create the LHS of the PHI
+ node by duplicating VAR. This is useful in the case of
+ pointers, to also duplicate pointer attributes (alias
+ information, in particular). */
+ edge_iterator ei;
+ tree new_lhs;
+
+ phi = create_phi_node (var, bb);
+ new_lhs = duplicate_ssa_name (var, phi);
+ SET_PHI_RESULT (phi, new_lhs);
+ add_new_name_mapping (new_lhs, var);
+
+ /* Add VAR to every argument slot of PHI. We need VAR in
+ every argument so that rewrite_update_phi_arguments knows
+ which name is this PHI node replacing. If VAR is a
+ symbol marked for renaming, this is not necessary, the
+ renamer will use the symbol on the LHS to get its
+ reaching definition. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ add_phi_arg (phi, var, e);
+ }
+ else
+ {
+ tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
+ phi = create_phi_node (sym, bb);
+ }
+
+ /* Mark this PHI node as interesting for update_ssa. */
+ REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
+ REWRITE_THIS_STMT (phi) = 1;
+ }
+}
+
+
+/* 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). */
+
+static void
+insert_phi_nodes (bitmap *dfs)
+{
+ unsigned i;
+
+ timevar_push (TV_TREE_INSERT_PHI_NODES);
+
+ for (i = 0; i < num_referenced_vars; i++)
+ {
+ struct def_blocks_d *def_map;
+ bitmap idf;
+ tree var = referenced_var (i);
+
+ def_map = find_def_blocks_for (var);
+ if (def_map == NULL)
+ continue;
+
+ if (get_phi_state (var) != NEED_PHI_STATE_NO)
+ {
+ idf = find_idf (def_map->def_blocks, dfs);
+ insert_phi_nodes_for (var, idf, false);
+ BITMAP_FREE (idf);
+ }
+ }
+
+ 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,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, 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)
+{
+ 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);
+ register_new_def (result, &block_defs_stack);
+ }
+}
+
+
+/* Return the current definition for variable VAR. If none is found,
+ create a new SSA name to act as the zeroth definition for VAR. If VAR
+ is call clobbered and there exists a more recent definition of
+ GLOBAL_VAR, return the definition for GLOBAL_VAR. This means that VAR
+ has been clobbered by a function call since its last assignment. */
+
+static tree
+get_reaching_def (tree var)
+{
+ tree currdef_var, avar;
+
+ /* Lookup the current reaching definition for VAR. */
+ currdef_var = get_current_def (var);
+
+ /* If there is no reaching definition for VAR, create and register a
+ default definition for it (if needed). */
+ if (currdef_var == NULL_TREE)
+ {
+ avar = DECL_P (var) ? var : SSA_NAME_VAR (var);
+ currdef_var = get_default_def_for (avar);
+ set_current_def (var, currdef_var);
+ }
+
+ /* Return the current reaching definition for VAR, or the default
+ definition, if we had to create one. */
+ return currdef_var;
+}
+
+
+/* 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. */
+ 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 and VUSES in the statement. */
+ if (REWRITE_THIS_STMT (stmt))
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
+ SSA_OP_ALL_USES|SSA_OP_ALL_KILLS)
+ {
+ 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 and VDEF operands. */
+ if (REGISTER_DEFS_IN_THIS_STMT (stmt))
+ FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
+ {
+ 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), &block_defs_stack);
+ }
+}
+
+
+/* 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 basic block BB. 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 we recorded an SSA_NAME, then make the SSA_NAME the current
+ definition of its underlying variable. If we recorded anything
+ else, it must have been an _DECL node and its current reaching
+ definition must have been NULL. */
+ if (TREE_CODE (tmp) == SSA_NAME)
+ {
+ saved_def = tmp;
+ var = SSA_NAME_VAR (saved_def);
+ }
+ else
+ {
+ saved_def = NULL;
+ var = tmp;
+ }
+
+ set_current_def (var, saved_def);
+ }
+}
+
+
+/* Dump SSA information to FILE. */
+
+void
+dump_tree_ssa (FILE *file)
+{
+ basic_block bb;
+ const char *funcname
+ = lang_hooks.decl_printable_name (current_function_decl, 2);
+
+ fprintf (file, "SSA information for %s\n\n", funcname);
+
+ FOR_EACH_BB (bb)
+ {
+ dump_bb (bb, file, 0);
+ fputs (" ", file);
+ print_generic_stmt (file, phi_nodes (bb), dump_flags);
+ fputs ("\n\n", 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)
+{
+ fprintf (file, "\nHash table statistics:\n");
+
+ fprintf (file, " def_blocks: ");
+ htab_statistics (file, def_blocks);
+
+ 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 = 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 ATTRIBUTE_UNUSED)
+{
+ struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
+
+ fprintf (stderr, "VAR: ");
+ print_generic_expr (stderr, db_p->var, dump_flags);
+ bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
+ bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
+
+ return 1;
+}
+
+
+/* Dump the DEF_BLOCKS hash table on stderr. */
+
+void
+debug_def_blocks (void)
+{
+ htab_traverse (def_blocks, debug_def_blocks_r, NULL);
+}
+
+
+/* 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_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. */
+ 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. */