diff options
Diffstat (limited to 'gcc/tree-into-ssa.c')
| -rw-r--r-- | gcc/tree-into-ssa.c | 204 |
1 files changed, 119 insertions, 85 deletions
diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c index 972bec9..079065e 100644 --- a/gcc/tree-into-ssa.c +++ b/gcc/tree-into-ssa.c @@ -379,13 +379,13 @@ mark_def_sites (struct dom_walk_data *walk_data, /* 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) + FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTDEFKILL) { if (prepare_use_operand_for_rename (use_p, &uid) && !TEST_BIT (kills, uid)) set_livein_block (USE_FROM_PTR (use_p), bb); } - + /* 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 @@ -438,7 +438,7 @@ ssa_mark_def_sites (struct dom_walk_data *walk_data, /* 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_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES) + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) { uid = SSA_NAME_VERSION (use); @@ -1077,7 +1077,7 @@ rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, gcc_assert (!ann->modified); /* Step 1. Rewrite USES and VUSES in the statement. */ - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) + FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) rewrite_operand (use_p); /* Step 2. Register the statement's DEF and VDEF operands. */ @@ -1121,7 +1121,7 @@ ssa_rewrite_stmt (struct dom_walk_data *walk_data, gcc_assert (!ann->modified); /* Step 1. Rewrite USES and VUSES in the statement. */ - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) + FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) { if (TEST_BIT (names_to_rename, SSA_NAME_VERSION (USE_FROM_PTR (use_p)))) SET_USE (use_p, get_reaching_def (USE_FROM_PTR (use_p))); @@ -1382,7 +1382,105 @@ invalidate_name_tags (bitmap vars_to_rename) } } +/* Rewrite the actual blocks, statements, and phi arguments, to be in SSA + form. ADD_PHI_ARGS is true if we should be adding arguments to phi nodes, + because they may have been just inserted. */ + +static void +rewrite_blocks (bool add_phi_args) +{ + 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. */ + 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 = rewrite_initialize_block; + walk_data.before_dom_children_walk_stmts = rewrite_stmt; + walk_data.before_dom_children_after_stmts = NULL; + if (add_phi_args) + walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments; + walk_data.after_dom_children_before_stmts = NULL; + walk_data.after_dom_children_walk_stmts = NULL; + walk_data.after_dom_children_after_stmts = rewrite_finalize_block; + walk_data.global_data = NULL; + walk_data.block_local_data_size = 0; + + VARRAY_TREE_INIT (block_defs_stack, 10, "Block DEFS Stack"); + + /* 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_BLOCK_PTR); + + /* Finalize the dominator walker. */ + fini_walk_dominator_tree (&walk_data); + + htab_delete (def_blocks); + + timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS); +} + +/* Mark the definition site blocks for each variable, so that we know where + the variable is actually live. */ + +static void +mark_def_site_blocks (void) +{ + size_t i; + struct dom_walk_data walk_data; + struct mark_def_sites_global_data mark_def_sites_global_data; + + /* Allocate memory for the DEF_BLOCKS hash table. */ + def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars), + def_blocks_hash, def_blocks_eq, def_blocks_free); + + for (i = 0; i < num_referenced_vars; i++) + set_current_def (referenced_var (i), NULL_TREE); + + /* Ensure that the dominance information is OK. */ + calculate_dominance_info (CDI_DOMINATORS); + + /* 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; + + /* 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 = sbitmap_alloc (num_referenced_vars); + 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. */ + sbitmap_free (mark_def_sites_global_data.kills); + +} /* Main entry point into the SSA builder. The renaming process proceeds in five main phases: @@ -1395,13 +1493,11 @@ invalidate_name_tags (bitmap vars_to_rename) order. 3- Find and mark all the blocks that define variables - (mark_def_sites). + (mark_def_site_blocks). 4- Insert PHI nodes at dominance frontiers (insert_phi_nodes). - 5- Rename all the blocks (rewrite_initialize_block, - rewrite_add_phi_arguments) and statements in the program - (rewrite_stmt). + 5- Rename all the blocks (rewrite_blocks) and statements in the program. Steps 3 and 5 are done using the dominator tree walker (walk_dominator_tree). @@ -1414,10 +1510,7 @@ rewrite_into_ssa (bool all) { bitmap *dfs; basic_block bb; - struct dom_walk_data walk_data; - struct mark_def_sites_global_data mark_def_sites_global_data; bitmap old_vars_to_rename = vars_to_rename; - unsigned i; timevar_push (TV_TREE_SSA_OTHER); @@ -1441,9 +1534,7 @@ rewrite_into_ssa (bool all) remove_all_phi_nodes_for (vars_to_rename); } - /* Allocate memory for the DEF_BLOCKS hash table. */ - def_blocks = htab_create (VARRAY_ACTIVE_SIZE (referenced_vars), - def_blocks_hash, def_blocks_eq, def_blocks_free); + mark_def_site_blocks (); /* Initialize dominance frontier and immediate dominator bitmaps. Also count the number of predecessors for each block. Doing so @@ -1452,80 +1543,13 @@ rewrite_into_ssa (bool all) FOR_EACH_BB (bb) dfs[bb->index] = BITMAP_XMALLOC (); - for (i = 0; i < num_referenced_vars; i++) - set_current_def (referenced_var (i), NULL_TREE); - - /* Ensure that the dominance information is OK. */ - calculate_dominance_info (CDI_DOMINATORS); - /* Compute dominance frontiers. */ compute_dominance_frontiers (dfs); - /* 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; - - /* 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 = sbitmap_alloc (num_referenced_vars); - 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. */ - sbitmap_free (mark_def_sites_global_data.kills); - /* Insert PHI nodes at dominance frontiers of definition blocks. */ insert_phi_nodes (dfs, NULL); - /* Rewrite all the basic blocks in the program. */ - timevar_push (TV_TREE_SSA_REWRITE_BLOCKS); - - /* Setup callbacks for the generic dominator tree walker. */ - 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 = rewrite_initialize_block; - walk_data.before_dom_children_walk_stmts = rewrite_stmt; - walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments; - walk_data.after_dom_children_before_stmts = NULL; - walk_data.after_dom_children_walk_stmts = NULL; - walk_data.after_dom_children_after_stmts = rewrite_finalize_block; - walk_data.global_data = NULL; - walk_data.block_local_data_size = 0; - - VARRAY_TREE_INIT (block_defs_stack, 10, "Block DEFS Stack"); - - /* 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_BLOCK_PTR); - - /* Finalize the dominator walker. */ - fini_walk_dominator_tree (&walk_data); - - timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS); + rewrite_blocks (true); /* Debugging dumps. */ if (dump_file && (dump_flags & TDF_STATS)) @@ -1539,12 +1563,22 @@ rewrite_into_ssa (bool all) BITMAP_XFREE (dfs[bb->index]); free (dfs); - htab_delete (def_blocks); - vars_to_rename = old_vars_to_rename; timevar_pop (TV_TREE_SSA_OTHER); } +/* Rewrite the def-def chains so that they have the correct reaching + definitions. */ + +void +rewrite_def_def_chains (void) +{ + /* Ensure that the dominance information is OK. */ + calculate_dominance_info (CDI_DOMINATORS); + mark_def_site_blocks (); + rewrite_blocks (false); + +} /* The marked ssa names may have more than one definition; add phi nodes and rewrite them to fix this. */ |