diff options
| -rw-r--r-- | gcc/ChangeLog | 62 | ||||
| -rw-r--r-- | gcc/Makefile.in | 8 | ||||
| -rw-r--r-- | gcc/domwalk.c | 63 | ||||
| -rw-r--r-- | gcc/domwalk.h | 55 | ||||
| -rw-r--r-- | gcc/graphite.c | 1 | ||||
| -rw-r--r-- | gcc/passes.c | 2 | ||||
| -rw-r--r-- | gcc/tree-into-ssa.c | 418 | ||||
| -rw-r--r-- | gcc/tree-ssa-alias.c | 10 | ||||
| -rw-r--r-- | gcc/tree-ssa-dom.c | 319 | ||||
| -rw-r--r-- | gcc/tree-ssa-dse.c | 50 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-im.c | 4 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-unswitch.c | 1 | ||||
| -rw-r--r-- | gcc/tree-ssa-phiopt.c | 10 | ||||
| -rw-r--r-- | gcc/tree-ssa-threadedge.c | 1 | ||||
| -rw-r--r-- | gcc/tree-ssa-uncprop.c | 30 |
15 files changed, 463 insertions, 571 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 66a48c10795..5517f3706ce 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,65 @@ +2009-06-27 Paolo Bonzini <bonzini@gnu.org> + + * domwalk.h (struct dom_walk_data): Remove all callbacks except + before_dom_children_before_stmts and after_dom_children_after_stmts. + Rename the two remaining callbacks to just before_dom_children and + after_dom_children. Remove other GIMPLE statement walking bits. + * domwalk.c (walk_dominator_tree): Remove now unsupported features. + * graphite.c: Do not include domwalk.h. + * tree-into-ssa.c (interesting_blocks): New global. + (struct mark_def_sites_global_data): Remove it and names_to_rename. + (mark_def_sites, rewrite_stmt, rewrite_add_phi_arguments, + rewrite_update_stmt, rewrite_update_phi_arguments): Simplify + now that they're not domwalk callbacks. + (rewrite_initialize_block): Rename to... + (rewrite_enter_block): ... this, place after called functions. Test + interesting_blocks, call rewrite_stmt and rewrite_add_phi_arguments. + (rewrite_finalize_block): Rename to... + (rewrite_leave_block): ... this, place after called functions. + (rewrite_update_init_block): Rename to... + (rewrite_update_enter_block): ... this, place after called functions. + Test interesting_blocks, call rewrite_update_stmt and + rewrite_update_phi_arguments. + (rewrite_update_fini_block): Rename to... + (rewrite_leave_block): ... this, place after called functions. + (rewrite_blocks): Remove last argument, simplify initialization of + walk_data. + (mark_def_sites_initialize_block): Rename to... + (mark_def_sites_block): ... this, call mark_def_sites. + (mark_def_sites_blocks): Remove argument, simplify initialization of + walk_data. + (rewrite_into_ssa): Adjust for interesting_blocks_being a global. + (update_ssa): Likewise. + * tree-ssa-dom.c (optimize_stmt): Simplify now that it's not a domwalk + callback. + (tree_ssa_dominator_optimize): Simplify initialization of walk_data. + (dom_opt_initialize_block): Rename to... + (dom_opt_enter_block): ... this, place after called functions. Walk + statements here, inline propagate_to_outgoing_edges. + (dom_opt_finalize_block): Rename to... + (dom_opt_leave_block): ... this, place after called functions. + * tree-ssa-dse.c (dse_optimize_stmt): Simplify now that it's not a + domwalk callback. + (dse_enter_block, dse_record_phi): New. + (dse_record_phis): Delete. + (dse_finalize_block): Rename to... + (dse_leave_block): ... this. + (tree_ssa_dse): Simplify initialization of walk_data. + * tree-ssa-loop-im.c (determine_invariantness, move_computations): + Adjust initialization of walk_data. + * tree-ssa-loop-unswitch.c: Do not include domwalk.h. + * tree-ssa-loop-phiopt.c (get_non_trapping): + Adjust initialization of walk_data. + * tree-ssa-loop-threadedge.c: Do not include domwalk.h. + * tree-ssa-uncprop.c (uncprop_into_successor_phis): Simplify now that + it's not a domwalk callback. + (uncprop_initialize_block): Rename to... + (dse_enter_block): ... this, call uncprop_into_successor_phis. + (dse_finalize_block): Rename to... + (dse_leave_block): ... this. + (tree_ssa_uncprop): Simplify initialization of walk_data. + * Makefile.in: Adjust dependencies. + 2009-06-27 Richard Earnshaw <rearnsha@arm.com> * arm.md (casesi): Fix test for Thumb1. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index d215e0fb258..d621d7fb52f 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -2221,7 +2221,7 @@ tree-ssa-threadedge.o : tree-ssa-threadedge.c $(TREE_FLOW_H) $(CONFIG_H) \ $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) $(FLAGS_H) $(RTL_H) $(TM_P_H) $(GGC_H) \ $(BASIC_BLOCK_H) $(CFGLOOP_H) output.h $(EXPR_H) \ $(FUNCTION_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TREE_DUMP_H) $(TREE_FLOW_H) \ - domwalk.h $(REAL_H) $(TREE_PASS_H) tree-ssa-propagate.h langhooks.h \ + $(REAL_H) $(TREE_PASS_H) tree-ssa-propagate.h langhooks.h \ $(PARAMS_H) tree-ssa-threadupdate.o : tree-ssa-threadupdate.c $(TREE_FLOW_H) $(CONFIG_H) \ $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) output.h \ @@ -2233,7 +2233,7 @@ tree-phinodes.o : tree-phinodes.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ $(TM_H) $(TREE_H) $(VARRAY_H) $(GGC_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) \ gt-tree-phinodes.h $(RTL_H) $(TOPLEV.H) $(GIMPLE_H) domwalk.o : domwalk.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ - $(TREE_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) domwalk.h $(GGC_H) + $(BASIC_BLOCK_H) domwalk.h $(GGC_H) tree-ssa-live.o : tree-ssa-live.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ $(TREE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ $(TREE_SSA_LIVE_H) $(BITMAP_H) $(TOPLEV_H) debug.h $(FLAGS_H) @@ -2310,7 +2310,7 @@ tree-ssa-loop.o : tree-ssa-loop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(CFGLOOP_H) $(FLAGS_H) $(TREE_INLINE_H) tree-scalar-evolution.h tree-ssa-loop-unswitch.o : tree-ssa-loop-unswitch.c $(TREE_FLOW_H) \ $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \ - domwalk.h $(PARAMS_H) output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) \ + $(PARAMS_H) output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) \ coretypes.h $(TREE_DUMP_H) $(TREE_PASS_H) $(BASIC_BLOCK_H) hard-reg-set.h \ $(TREE_INLINE_H) tree-ssa-address.o : tree-ssa-address.c $(TREE_FLOW_H) $(CONFIG_H) \ @@ -2425,7 +2425,7 @@ tree-data-ref.o: tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(TREE_DATA_REF_H) $(SCEV_H) $(TREE_PASS_H) tree-chrec.h langhooks.h graphite.o: graphite.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) $(TOPLEV_H) \ - $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) $(GIMPLE_H) domwalk.h \ + $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) $(GIMPLE_H) \ $(TREE_DATA_REF_H) $(SCEV_H) $(TREE_PASS_H) tree-chrec.h graphite.h \ pointer-set.h value-prof.h tree-vect-loop.o: tree-vect-loop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \ diff --git a/gcc/domwalk.c b/gcc/domwalk.c index 8f779225432..b70a807e7a4 100644 --- a/gcc/domwalk.c +++ b/gcc/domwalk.c @@ -23,9 +23,7 @@ along with GCC; see the file COPYING3. If not see #include "system.h" #include "coretypes.h" #include "tm.h" -#include "tree.h" #include "basic-block.h" -#include "tree-flow.h" #include "domwalk.h" #include "ggc.h" @@ -144,8 +142,6 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) { void *bd = NULL; basic_block dest; - gimple_stmt_iterator gsi; - bool is_interesting; basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks * 2); int sp = 0; @@ -156,13 +152,6 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) || bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) { - /* If block BB is not interesting to the caller, then none of the - callbacks that walk the statements in BB are going to be - executed. */ - is_interesting = walk_data->interesting_blocks == NULL - || TEST_BIT (walk_data->interesting_blocks, - bb->index); - /* Callback to initialize the local data structure. */ if (walk_data->initialize_block_local_data) { @@ -192,27 +181,8 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) /* Callback for operations to execute before we have walked the dominator children, but before we walk statements. */ - if (walk_data->before_dom_children_before_stmts) - (*walk_data->before_dom_children_before_stmts) (walk_data, bb); - - /* Statement walk before walking dominator children. */ - if (is_interesting && walk_data->before_dom_children_walk_stmts) - { - if (walk_data->walk_stmts_backward) - for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi); - gsi_prev (&gsi)) - (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, - gsi); - else - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - (*walk_data->before_dom_children_walk_stmts) (walk_data, bb, - gsi); - } - - /* Callback for operations to execute before we have walked the - dominator children, and after we walk statements. */ - if (walk_data->before_dom_children_after_stmts) - (*walk_data->before_dom_children_after_stmts) (walk_data, bb); + if (walk_data->before_dom_children) + (*walk_data->before_dom_children) (walk_data, bb); /* Mark the current BB to be popped out of the recursion stack once children are processed. */ @@ -223,37 +193,16 @@ walk_dominator_tree (struct dom_walk_data *walk_data, basic_block bb) dest; dest = next_dom_son (walk_data->dom_direction, dest)) worklist[sp++] = dest; } - /* NULL is used to signalize pop operation in recursion stack. */ + /* NULL is used to mark pop operations in the recursion stack. */ while (sp > 0 && !worklist[sp - 1]) { --sp; bb = worklist[--sp]; - is_interesting = walk_data->interesting_blocks == NULL - || TEST_BIT (walk_data->interesting_blocks, - bb->index); - /* Callback for operations to execute after we have walked the - dominator children, but before we walk statements. */ - if (walk_data->after_dom_children_before_stmts) - (*walk_data->after_dom_children_before_stmts) (walk_data, bb); - - /* Statement walk after walking dominator children. */ - if (is_interesting && walk_data->after_dom_children_walk_stmts) - { - if (walk_data->walk_stmts_backward) - for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi); - gsi_prev (&gsi)) - (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, - gsi); - else - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - (*walk_data->after_dom_children_walk_stmts) (walk_data, bb, - gsi); - } /* Callback for operations to execute after we have walked the - dominator children and after we have walked statements. */ - if (walk_data->after_dom_children_after_stmts) - (*walk_data->after_dom_children_after_stmts) (walk_data, bb); + dominator children, but before we walk statements. */ + if (walk_data->after_dom_children) + (*walk_data->after_dom_children) (walk_data, bb); if (walk_data->initialize_block_local_data) { diff --git a/gcc/domwalk.h b/gcc/domwalk.h index 6589c0fdead..63aeec233a3 100644 --- a/gcc/domwalk.h +++ b/gcc/domwalk.h @@ -34,15 +34,6 @@ struct dom_walk_data dominator tree. */ ENUM_BITFIELD (cdi_direction) dom_direction : 2; - /* Nonzero if the statement walker should walk the statements from - last to first within a basic block instead of first to last. - - Note this affects both statement walkers. We haven't yet needed - to use the second statement walker for anything, so it's hard to - predict if we really need the ability to select their direction - independently. */ - BOOL_BITFIELD walk_stmts_backward : 1; - /* Function to initialize block local data. Note that the dominator walker infrastructure may provide a new @@ -55,41 +46,11 @@ struct dom_walk_data void (*initialize_block_local_data) (struct dom_walk_data *, basic_block, bool); - /* Function to call before the statement walk occurring before the - recursive walk of the dominator children. - - This typically initializes a block local data and pushes that - data onto BLOCK_DATA_STACK. */ - void (*before_dom_children_before_stmts) (struct dom_walk_data *, - basic_block); - - /* Function to call to walk statements before the recursive walk - of the dominator children. */ - void (*before_dom_children_walk_stmts) (struct dom_walk_data *, - basic_block, gimple_stmt_iterator); - - /* Function to call after the statement walk occurring before the - recursive walk of the dominator children. */ - void (*before_dom_children_after_stmts) (struct dom_walk_data *, - basic_block); + /* Function to call before the recursive walk of the dominator children. */ + void (*before_dom_children) (struct dom_walk_data *, basic_block); - /* Function to call before the statement walk occurring after the - recursive walk of the dominator children. */ - void (*after_dom_children_before_stmts) (struct dom_walk_data *, - basic_block); - - /* Function to call to walk statements after the recursive walk - of the dominator children. */ - void (*after_dom_children_walk_stmts) (struct dom_walk_data *, - basic_block, gimple_stmt_iterator); - - /* Function to call after the statement walk occurring after the - recursive walk of the dominator children. - - This typically finalizes any block local data and pops - that data from BLOCK_DATA_STACK. */ - void (*after_dom_children_after_stmts) (struct dom_walk_data *, - basic_block); + /* Function to call after the recursive walk of the dominator children. */ + void (*after_dom_children) (struct dom_walk_data *, basic_block); /* Global data for a walk through the dominator tree. */ void *global_data; @@ -108,14 +69,6 @@ struct dom_walk_data /* Stack of available block local structures. */ VEC(void_p,heap) *free_block_data; - - /* Interesting blocks to process. If this field is not NULL, this - set is used to determine which blocks to walk. If we encounter - block I in the dominator traversal, but block I is not present in - INTERESTING_BLOCKS, then none of the callback functions are - invoked on it. This is useful when a particular traversal wants - to filter out non-interesting blocks from the dominator tree. */ - sbitmap interesting_blocks; }; void walk_dominator_tree (struct dom_walk_data *, basic_block); diff --git a/gcc/graphite.c b/gcc/graphite.c index 90e11acb3cc..a87bca867c9 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -50,7 +50,6 @@ along with GCC; see the file COPYING3. If not see #include "tree-data-ref.h" #include "tree-scalar-evolution.h" #include "tree-pass.h" -#include "domwalk.h" #include "value-prof.h" #include "pointer-set.h" #include "gimple.h" diff --git a/gcc/passes.c b/gcc/passes.c index 36ffd222135..5ae2a7ef343 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -1259,7 +1259,7 @@ execute_one_pass (struct opt_pass *pass) if (pass->gate && !pass->gate ()) return false; - if (!quiet_flag && !cfun) + if (!quiet_flag) fprintf (stderr, " <%s>", pass->name ? pass->name : ""); if (pass->todo_flags_start & TODO_set_props) diff --git a/gcc/tree-into-ssa.c b/gcc/tree-into-ssa.c index d1f0ff7820e..ab827eadc57 100644 --- a/gcc/tree-into-ssa.c +++ b/gcc/tree-into-ssa.c @@ -112,6 +112,7 @@ static sbitmap old_ssa_names; the operations done on them are presence tests. */ static sbitmap new_ssa_names; +sbitmap interesting_blocks; /* Set of SSA names that have been marked to be released after they were registered in the replacement table. They will be finally @@ -168,13 +169,6 @@ struct mark_def_sites_global_data /* This bitmap contains the variables which are set before they are used in a basic block. */ bitmap kills; - - /* Bitmap of names to rename. */ - sbitmap names_to_rename; - - /* Set of blocks that mark_def_sites deems interesting for the - renamer to process. */ - sbitmap interesting_blocks; }; @@ -731,7 +725,7 @@ add_new_name_mapping (tree new_tree, tree old) BB: 1- Variables defined by S in the DEFS of S are marked in the bitmap - WALK_DATA->GLOBAL_DATA->KILLS. + KILLS. 2- If S uses a variable VAR and there is no preceding kill of VAR, then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR. @@ -741,24 +735,16 @@ add_new_name_mapping (tree new_tree, tree old) we create. */ static void -mark_def_sites (struct dom_walk_data *walk_data, basic_block bb, - gimple_stmt_iterator gsi) +mark_def_sites (basic_block bb, gimple stmt, bitmap kills) { - struct mark_def_sites_global_data *gd; - bitmap kills; tree def; - gimple stmt; use_operand_p use_p; ssa_op_iter iter; /* Since this is the first time that we rewrite the program into SSA form, force an operand scan on every statement. */ - stmt = gsi_stmt (gsi); update_stmt (stmt); - gd = (struct mark_def_sites_global_data *) walk_data->global_data; - kills = gd->kills; - gcc_assert (blocks_to_update == NULL); set_register_defs (stmt, false); set_rewrite_uses (stmt, false); @@ -787,7 +773,7 @@ mark_def_sites (struct dom_walk_data *walk_data, basic_block bb, /* If we found the statement interesting then also mark the block BB as interesting. */ if (rewrite_uses_p (stmt) || register_defs_p (stmt)) - SET_BIT (gd->interesting_blocks, bb->index); + SET_BIT (interesting_blocks, bb->index); } /* Structure used by prune_unused_phi_nodes to record bounds of the intervals @@ -1243,39 +1229,6 @@ register_new_def (tree def, tree sym) 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) -{ - gimple phi; - gimple_stmt_iterator gsi; - - 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 (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - tree result; - - phi = gsi_stmt (gsi); - result = gimple_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. */ @@ -1307,16 +1260,12 @@ get_reaching_def (tree var) 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, gimple_stmt_iterator si) +rewrite_stmt (gimple stmt) { - gimple stmt; use_operand_p use_p; def_operand_p def_p; ssa_op_iter iter; - stmt = gsi_stmt (si); - /* If mark_def_sites decided that we don't need to rewrite this statement, ignore it. */ gcc_assert (blocks_to_update == NULL); @@ -1357,8 +1306,7 @@ rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, that definition is reaching the PHI node. */ static void -rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, - basic_block bb) +rewrite_add_phi_arguments (basic_block bb) { edge e; edge_iterator ei; @@ -1379,13 +1327,59 @@ rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, } } +/* 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_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, + basic_block bb) +{ + gimple phi; + gimple_stmt_iterator gsi; + + 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 (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + tree result; + + phi = gsi_stmt (gsi); + result = gimple_phi_result (phi); + gcc_assert (is_gimple_reg (result)); + register_new_def (result, SSA_NAME_VAR (result)); + } + + /* 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. */ + if (TEST_BIT (interesting_blocks, bb->index)) + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + rewrite_stmt (gsi_stmt (gsi)); + + /* 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. */ + rewrite_add_phi_arguments (bb); +} + + /* 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) +rewrite_leave_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) @@ -1740,103 +1734,6 @@ register_new_update_set (tree new_name, bitmap old_names) } -/* 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; - bool is_abnormal_phi; - gimple_stmt_iterator gsi; - - 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 (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - tree lhs, lhs_sym; - gimple phi = gsi_stmt (gsi); - - if (!register_defs_p (phi)) - continue; - - lhs = gimple_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 @@ -1905,19 +1802,12 @@ maybe_register_def (def_operand_p def_p, gimple stmt) in OLD_SSA_NAMES. */ static void -rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, - basic_block bb ATTRIBUTE_UNUSED, - gimple_stmt_iterator si) +rewrite_update_stmt (gimple stmt) { - gimple stmt; use_operand_p use_p; def_operand_p def_p; ssa_op_iter iter; - stmt = gsi_stmt (si); - - gcc_assert (bitmap_bit_p (blocks_to_update, bb->index)); - /* Only update marked statements. */ if (!rewrite_uses_p (stmt) && !register_defs_p (stmt)) return; @@ -1950,8 +1840,7 @@ rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, definition, replace it. */ static void -rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, - basic_block bb) +rewrite_update_phi_arguments (basic_block bb) { edge e; edge_iterator ei; @@ -2005,6 +1894,114 @@ rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, } +/* 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_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, + basic_block bb) +{ + edge e; + edge_iterator ei; + bool is_abnormal_phi; + gimple_stmt_iterator gsi; + + 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 (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + tree lhs, lhs_sym; + gimple phi = gsi_stmt (gsi); + + if (!register_defs_p (phi)) + continue; + + lhs = gimple_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; + } + + /* Step 2. Rewrite every variable used in each statement in the block. */ + if (TEST_BIT (interesting_blocks, bb->index)) + { + gcc_assert (bitmap_bit_p (blocks_to_update, bb->index)); + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + rewrite_update_stmt (gsi_stmt (gsi)); + } + + /* Step 3. Update PHI nodes. */ + rewrite_update_phi_arguments (bb); +} + +/* 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_leave_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_enter_block). */ + if (var == NULL) + return; + + saved_def = VEC_pop (tree, block_defs_stack); + set_current_def (var, saved_def); + } +} + + /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA form. @@ -2020,7 +2017,7 @@ rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, are not present in BLOCKS are ignored. */ static void -rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks) +rewrite_blocks (basic_block entry, enum rewrite_mode what) { struct dom_walk_data walk_data; @@ -2031,31 +2028,17 @@ rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks) 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; + { + walk_data.before_dom_children = rewrite_enter_block; + walk_data.after_dom_children = rewrite_leave_block; + } else if (what == REWRITE_UPDATE) - walk_data.after_dom_children_after_stmts = rewrite_update_fini_block; + { + walk_data.before_dom_children = rewrite_update_enter_block; + walk_data.after_dom_children = rewrite_update_leave_block; + } else gcc_unreachable (); @@ -2085,53 +2068,49 @@ rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks) } -/* Block initialization routine for mark_def_sites. Clear the - KILLS bitmap at the start of each block. */ +/* Block processing routine for mark_def_sites. Clear the KILLS bitmap + at the start of each block, and call mark_def_sites for each statement. */ static void -mark_def_sites_initialize_block (struct dom_walk_data *walk_data, - basic_block bb ATTRIBUTE_UNUSED) +mark_def_sites_block (struct dom_walk_data *walk_data, basic_block bb) { struct mark_def_sites_global_data *gd; + bitmap kills; + gimple_stmt_iterator gsi; + gd = (struct mark_def_sites_global_data *) walk_data->global_data; - bitmap_clear (gd->kills); + kills = gd->kills; + + bitmap_clear (kills); + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + mark_def_sites (bb, gsi_stmt (gsi), 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. */ + The INTERESTING_BLOCKS global will be filled in with all the blocks + that should be processed by the renamer. It is assumed that the + caller has already initialized and zeroed it. */ static void -mark_def_site_blocks (sbitmap interesting_blocks) +mark_def_site_blocks (void) { 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; + walk_data.before_dom_children = mark_def_sites_block; + walk_data.after_dom_children = 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. */ @@ -2207,7 +2186,6 @@ rewrite_into_ssa (void) { bitmap *dfs; basic_block bb; - sbitmap interesting_blocks; timevar_push (TV_TREE_SSA_OTHER); @@ -2233,19 +2211,18 @@ rewrite_into_ssa (void) compute_dominance_frontiers (dfs); /* 2- Find and mark definition sites. */ - mark_def_site_blocks (interesting_blocks); + mark_def_site_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); + rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL); /* Free allocated memory. */ FOR_EACH_BB (bb) BITMAP_FREE (dfs[bb->index]); free (dfs); - sbitmap_free (interesting_blocks); fini_ssa_renamer (); @@ -3079,7 +3056,6 @@ update_ssa (unsigned update_flags) basic_block bb, start_bb; bitmap_iterator bi; unsigned i = 0; - sbitmap tmp; bool insert_phi_p; sbitmap_iterator sbi; @@ -3235,14 +3211,14 @@ update_ssa (unsigned update_flags) set_current_def (referenced_var (i), NULL_TREE); /* Now start the renaming process at START_BB. */ - tmp = sbitmap_alloc (last_basic_block); - sbitmap_zero (tmp); + interesting_blocks = sbitmap_alloc (last_basic_block); + sbitmap_zero (interesting_blocks); EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi) - SET_BIT (tmp, i); + SET_BIT (interesting_blocks, i); - rewrite_blocks (start_bb, REWRITE_UPDATE, tmp); + rewrite_blocks (start_bb, REWRITE_UPDATE); - sbitmap_free (tmp); + sbitmap_free (interesting_blocks); /* Debugging dumps. */ if (dump_file) diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index 14733675262..f14fa090268 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -1358,13 +1358,10 @@ walk_non_aliased_vuses (ao_ref *ref, tree vuse, bitmap visited = NULL; void *res; - timevar_push (TV_ALIAS_STMT_WALK); - do { gimple def_stmt; - /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */ res = (*walker) (ref, vuse, data); if (res) break; @@ -1400,8 +1397,6 @@ walk_non_aliased_vuses (ao_ref *ref, tree vuse, if (visited) BITMAP_FREE (visited); - timevar_pop (TV_ALIAS_STMT_WALK); - return res; } @@ -1445,7 +1440,6 @@ walk_aliased_vdefs_1 (tree ref, tree vdef, return cnt; } - /* ??? Do we want to account this to TV_ALIAS_STMT_WALK? */ cnt++; if ((!ref || stmt_may_clobber_ref_p (def_stmt, ref)) @@ -1465,15 +1459,11 @@ walk_aliased_vdefs (tree ref, tree vdef, bitmap local_visited = NULL; unsigned int ret; - timevar_push (TV_ALIAS_STMT_WALK); - ret = walk_aliased_vdefs_1 (ref, vdef, walker, data, visited ? visited : &local_visited, 0); if (local_visited) BITMAP_FREE (local_visited); - timevar_pop (TV_ALIAS_STMT_WALK); - return ret; } diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index 55a13b9d012..0a2c4900e8e 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -183,9 +183,7 @@ struct opt_stats_d static struct opt_stats_d opt_stats; /* Local functions. */ -static void optimize_stmt (struct dom_walk_data *, - basic_block, - gimple_stmt_iterator); +static void optimize_stmt (basic_block, gimple_stmt_iterator); static tree lookup_avail_expr (gimple, bool); static hashval_t avail_expr_hash (const void *); static hashval_t real_avail_expr_hash (const void *); @@ -199,9 +197,8 @@ static void record_equivalences_from_incoming_edge (basic_block); static bool eliminate_redundant_computations (gimple_stmt_iterator *); static void record_equivalences_from_stmt (gimple, int); static void dom_thread_across_edge (struct dom_walk_data *, edge); -static void dom_opt_finalize_block (struct dom_walk_data *, basic_block); -static void dom_opt_initialize_block (struct dom_walk_data *, basic_block); -static void propagate_to_outgoing_edges (struct dom_walk_data *, basic_block); +static void dom_opt_leave_block (struct dom_walk_data *, basic_block); +static void dom_opt_enter_block (struct dom_walk_data *, basic_block); static void remove_local_expressions_from_table (void); static void restore_vars_to_original_value (void); static edge single_incoming_edge_ignoring_loop_edges (basic_block); @@ -630,21 +627,15 @@ tree_ssa_dominator_optimize (void) need_eh_cleanup = BITMAP_ALLOC (NULL); /* 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 = dom_opt_initialize_block; - walk_data.before_dom_children_walk_stmts = optimize_stmt; - walk_data.before_dom_children_after_stmts = propagate_to_outgoing_edges; - walk_data.after_dom_children_before_stmts = NULL; - walk_data.after_dom_children_walk_stmts = NULL; - walk_data.after_dom_children_after_stmts = dom_opt_finalize_block; + walk_data.before_dom_children = dom_opt_enter_block; + walk_data.after_dom_children = dom_opt_leave_block; /* Right now we only attach a dummy COND_EXPR to the global data pointer. When we attach more stuff we'll need to fill this out with a real structure. */ walk_data.global_data = NULL; walk_data.block_local_data_size = 0; - walk_data.interesting_blocks = NULL; /* Now initialize the dominator walker. */ init_walk_dominator_tree (&walk_data); @@ -827,24 +818,6 @@ canonicalize_comparison (gimple condstmt) upon entry to BB. Equivalences can come from the edge traversed to reach BB or they may come from PHI nodes at the start of BB. */ -static void -dom_opt_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, - basic_block bb) -{ - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); - - /* Push a marker on the stacks of local information so that we know how - far to unwind when we finalize this block. */ - VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); - VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); - - record_equivalences_from_incoming_edge (bb); - - /* PHI nodes can create equivalences too. */ - record_equivalences_from_phis (bb); -} - /* Remove all the expressions in LOCALS from TABLE, stopping when there are LIMIT entries left in LOCALs. */ @@ -935,131 +908,6 @@ dom_thread_across_edge (struct dom_walk_data *walk_data, edge e) simplify_stmt_for_jump_threading); } -/* We have finished processing the dominator children of BB, perform - any finalization actions in preparation for leaving this node in - the dominator tree. */ - -static void -dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb) -{ - gimple last; - - /* If we have an outgoing edge to a block with multiple incoming and - outgoing edges, then we may be able to thread the edge, i.e., we - may be able to statically determine which of the outgoing edges - will be traversed when the incoming edge from BB is traversed. */ - if (single_succ_p (bb) - && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0 - && potentially_threadable_block (single_succ (bb))) - { - dom_thread_across_edge (walk_data, single_succ_edge (bb)); - } - else if ((last = last_stmt (bb)) - && gimple_code (last) == GIMPLE_COND - && EDGE_COUNT (bb->succs) == 2 - && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0 - && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0) - { - edge true_edge, false_edge; - - extract_true_false_edges_from_block (bb, &true_edge, &false_edge); - - /* Only try to thread the edge if it reaches a target block with - more than one predecessor and more than one successor. */ - if (potentially_threadable_block (true_edge->dest)) - { - struct edge_info *edge_info; - unsigned int i; - - /* Push a marker onto the available expression stack so that we - unwind any expressions related to the TRUE arm before processing - the false arm below. */ - VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); - VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); - - edge_info = (struct edge_info *) true_edge->aux; - - /* If we have info associated with this edge, record it into - our equivalence tables. */ - if (edge_info) - { - struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; - tree lhs = edge_info->lhs; - tree rhs = edge_info->rhs; - - /* If we have a simple NAME = VALUE equivalence, record it. */ - if (lhs && TREE_CODE (lhs) == SSA_NAME) - record_const_or_copy (lhs, rhs); - - /* If we have 0 = COND or 1 = COND equivalences, record them - into our expression hash tables. */ - if (cond_equivalences) - for (i = 0; i < edge_info->max_cond_equivalences; i++) - record_cond (&cond_equivalences[i]); - } - - dom_thread_across_edge (walk_data, true_edge); - - /* And restore the various tables to their state before - we threaded this edge. */ - remove_local_expressions_from_table (); - } - - /* Similarly for the ELSE arm. */ - if (potentially_threadable_block (false_edge->dest)) - { - struct edge_info *edge_info; - unsigned int i; - - VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); - edge_info = (struct edge_info *) false_edge->aux; - - /* If we have info associated with this edge, record it into - our equivalence tables. */ - if (edge_info) - { - struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; - tree lhs = edge_info->lhs; - tree rhs = edge_info->rhs; - - /* If we have a simple NAME = VALUE equivalence, record it. */ - if (lhs && TREE_CODE (lhs) == SSA_NAME) - record_const_or_copy (lhs, rhs); - - /* If we have 0 = COND or 1 = COND equivalences, record them - into our expression hash tables. */ - if (cond_equivalences) - for (i = 0; i < edge_info->max_cond_equivalences; i++) - record_cond (&cond_equivalences[i]); - } - - /* Now thread the edge. */ - dom_thread_across_edge (walk_data, false_edge); - - /* No need to remove local expressions from our tables - or restore vars to their original value as that will - be done immediately below. */ - } - } - - remove_local_expressions_from_table (); - restore_vars_to_original_value (); - - /* If we queued any statements to rescan in this block, then - go ahead and rescan them now. */ - while (VEC_length (gimple, stmts_to_rescan) > 0) - { - gimple stmt = VEC_last (gimple, stmts_to_rescan); - basic_block stmt_bb = gimple_bb (stmt); - - if (stmt_bb != bb) - break; - - VEC_pop (gimple, stmts_to_rescan); - update_stmt (stmt); - } -} - /* PHI nodes can create equivalences too. Ignoring any alternatives which are the same as the result, if @@ -1787,20 +1635,158 @@ record_edge_info (basic_block bb) } } -/* Propagate information from BB to its outgoing edges. - - This can include equivalence information implied by control statements - at the end of BB and const/copy propagation into PHIs in BB's - successor blocks. */ - static void -propagate_to_outgoing_edges (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, - basic_block bb) +dom_opt_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, + basic_block bb) { + gimple_stmt_iterator gsi; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); + + /* Push a marker on the stacks of local information so that we know how + far to unwind when we finalize this block. */ + VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); + VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); + + record_equivalences_from_incoming_edge (bb); + + /* PHI nodes can create equivalences too. */ + record_equivalences_from_phis (bb); + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + optimize_stmt (bb, gsi); + + /* Now prepare to process dominated blocks. */ record_edge_info (bb); cprop_into_successor_phis (bb); } +/* We have finished processing the dominator children of BB, perform + any finalization actions in preparation for leaving this node in + the dominator tree. */ + +static void +dom_opt_leave_block (struct dom_walk_data *walk_data, basic_block bb) +{ + gimple last; + + /* If we have an outgoing edge to a block with multiple incoming and + outgoing edges, then we may be able to thread the edge, i.e., we + may be able to statically determine which of the outgoing edges + will be traversed when the incoming edge from BB is traversed. */ + if (single_succ_p (bb) + && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0 + && potentially_threadable_block (single_succ (bb))) + { + dom_thread_across_edge (walk_data, single_succ_edge (bb)); + } + else if ((last = last_stmt (bb)) + && gimple_code (last) == GIMPLE_COND + && EDGE_COUNT (bb->succs) == 2 + && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0 + && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0) + { + edge true_edge, false_edge; + + extract_true_false_edges_from_block (bb, &true_edge, &false_edge); + + /* Only try to thread the edge if it reaches a target block with + more than one predecessor and more than one successor. */ + if (potentially_threadable_block (true_edge->dest)) + { + struct edge_info *edge_info; + unsigned int i; + + /* Push a marker onto the available expression stack so that we + unwind any expressions related to the TRUE arm before processing + the false arm below. */ + VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); + VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); + + edge_info = (struct edge_info *) true_edge->aux; + + /* If we have info associated with this edge, record it into + our equivalence tables. */ + if (edge_info) + { + struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; + tree lhs = edge_info->lhs; + tree rhs = edge_info->rhs; + + /* If we have a simple NAME = VALUE equivalence, record it. */ + if (lhs && TREE_CODE (lhs) == SSA_NAME) + record_const_or_copy (lhs, rhs); + + /* If we have 0 = COND or 1 = COND equivalences, record them + into our expression hash tables. */ + if (cond_equivalences) + for (i = 0; i < edge_info->max_cond_equivalences; i++) + record_cond (&cond_equivalences[i]); + } + + dom_thread_across_edge (walk_data, true_edge); + + /* And restore the various tables to their state before + we threaded this edge. */ + remove_local_expressions_from_table (); + } + + /* Similarly for the ELSE arm. */ + if (potentially_threadable_block (false_edge->dest)) + { + struct edge_info *edge_info; + unsigned int i; + + VEC_safe_push (tree, heap, const_and_copies_stack, NULL_TREE); + edge_info = (struct edge_info *) false_edge->aux; + + /* If we have info associated with this edge, record it into + our equivalence tables. */ + if (edge_info) + { + struct cond_equivalence *cond_equivalences = edge_info->cond_equivalences; + tree lhs = edge_info->lhs; + tree rhs = edge_info->rhs; + + /* If we have a simple NAME = VALUE equivalence, record it. */ + if (lhs && TREE_CODE (lhs) == SSA_NAME) + record_const_or_copy (lhs, rhs); + + /* If we have 0 = COND or 1 = COND equivalences, record them + into our expression hash tables. */ + if (cond_equivalences) + for (i = 0; i < edge_info->max_cond_equivalences; i++) + record_cond (&cond_equivalences[i]); + } + + /* Now thread the edge. */ + dom_thread_across_edge (walk_data, false_edge); + + /* No need to remove local expressions from our tables + or restore vars to their original value as that will + be done immediately below. */ + } + } + + remove_local_expressions_from_table (); + restore_vars_to_original_value (); + + /* If we queued any statements to rescan in this block, then + go ahead and rescan them now. */ + while (VEC_length (gimple, stmts_to_rescan) > 0) + { + gimple stmt = VEC_last (gimple, stmts_to_rescan); + basic_block stmt_bb = gimple_bb (stmt); + + if (stmt_bb != bb) + break; + + VEC_pop (gimple, stmts_to_rescan); + update_stmt (stmt); + } +} + /* Search for redundant computations in STMT. If any are found, then replace them with the variable holding the result of the computation. @@ -2114,8 +2100,7 @@ cprop_into_stmt (gimple stmt) the variable in the LHS in the CONST_AND_COPIES table. */ static void -optimize_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, - basic_block bb, gimple_stmt_iterator si) +optimize_stmt (basic_block bb, gimple_stmt_iterator si) { gimple stmt, old_stmt; bool may_optimize_p; diff --git a/gcc/tree-ssa-dse.c b/gcc/tree-ssa-dse.c index 5df1aa16841..9559b4cb2f5 100644 --- a/gcc/tree-ssa-dse.c +++ b/gcc/tree-ssa-dse.c @@ -89,11 +89,8 @@ static unsigned int tree_ssa_dse (void); static void dse_initialize_block_local_data (struct dom_walk_data *, basic_block, bool); -static void dse_optimize_stmt (struct dom_walk_data *, - basic_block, - gimple_stmt_iterator); -static void dse_record_phis (struct dom_walk_data *, basic_block); -static void dse_finalize_block (struct dom_walk_data *, basic_block); +static void dse_enter_block (struct dom_walk_data *, basic_block); +static void dse_leave_block (struct dom_walk_data *, basic_block); static void record_voperand_set (bitmap, bitmap *, unsigned int); /* Returns uid of statement STMT. */ @@ -267,15 +264,10 @@ dse_possible_dead_store_p (gimple stmt, gimple *use_stmt) post dominates the first store, then the first store is dead. */ static void -dse_optimize_stmt (struct dom_walk_data *walk_data, - basic_block bb ATTRIBUTE_UNUSED, +dse_optimize_stmt (struct dse_global_data *dse_gd, + struct dse_block_local_data *bd, gimple_stmt_iterator gsi) { - struct dse_block_local_data *bd - = (struct dse_block_local_data *) - VEC_last (void_p, walk_data->block_data_stack); - struct dse_global_data *dse_gd - = (struct dse_global_data *) walk_data->global_data; gimple stmt = gsi_stmt (gsi); /* If this statement has no virtual defs, then there is nothing @@ -351,27 +343,33 @@ dse_optimize_stmt (struct dom_walk_data *walk_data, /* Record that we have seen the PHIs at the start of BB which correspond to virtual operands. */ static void -dse_record_phis (struct dom_walk_data *walk_data, basic_block bb) +dse_record_phi (struct dse_global_data *dse_gd, + struct dse_block_local_data *bd, + gimple phi) +{ + if (!is_gimple_reg (gimple_phi_result (phi))) + record_voperand_set (dse_gd->stores, &bd->stores, get_stmt_uid (phi)); +} + +static void +dse_enter_block (struct dom_walk_data *walk_data, basic_block bb) { struct dse_block_local_data *bd = (struct dse_block_local_data *) VEC_last (void_p, walk_data->block_data_stack); struct dse_global_data *dse_gd = (struct dse_global_data *) walk_data->global_data; - gimple phi; gimple_stmt_iterator gsi; + for (gsi = gsi_last (bb_seq (bb)); !gsi_end_p (gsi); gsi_prev (&gsi)) + dse_optimize_stmt (dse_gd, bd, gsi); for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - { - phi = gsi_stmt (gsi); - if (!is_gimple_reg (gimple_phi_result (phi))) - record_voperand_set (dse_gd->stores, &bd->stores, get_stmt_uid (phi)); - } + dse_record_phi (dse_gd, bd, gsi_stmt (gsi)); } static void -dse_finalize_block (struct dom_walk_data *walk_data, - basic_block bb ATTRIBUTE_UNUSED) +dse_leave_block (struct dom_walk_data *walk_data, + basic_block bb ATTRIBUTE_UNUSED) { struct dse_block_local_data *bd = (struct dse_block_local_data *) @@ -409,16 +407,10 @@ tree_ssa_dse (void) /* Dead store elimination is fundamentally a walk of the post-dominator tree and a backwards walk of statements within each block. */ - walk_data.walk_stmts_backward = true; walk_data.dom_direction = CDI_POST_DOMINATORS; walk_data.initialize_block_local_data = dse_initialize_block_local_data; - walk_data.before_dom_children_before_stmts = NULL; - walk_data.before_dom_children_walk_stmts = dse_optimize_stmt; - walk_data.before_dom_children_after_stmts = dse_record_phis; - walk_data.after_dom_children_before_stmts = NULL; - walk_data.after_dom_children_walk_stmts = NULL; - walk_data.after_dom_children_after_stmts = dse_finalize_block; - walk_data.interesting_blocks = NULL; + walk_data.before_dom_children = dse_enter_block; + walk_data.after_dom_children = dse_leave_block; walk_data.block_local_data_size = sizeof (struct dse_block_local_data); diff --git a/gcc/tree-ssa-loop-im.c b/gcc/tree-ssa-loop-im.c index 3cdabd6bbc5..d8ee787cc47 100644 --- a/gcc/tree-ssa-loop-im.c +++ b/gcc/tree-ssa-loop-im.c @@ -999,7 +999,7 @@ determine_invariantness (void) memset (&walk_data, 0, sizeof (struct dom_walk_data)); walk_data.dom_direction = CDI_DOMINATORS; - walk_data.before_dom_children_before_stmts = determine_invariantness_stmt; + walk_data.before_dom_children = determine_invariantness_stmt; init_walk_dominator_tree (&walk_data); walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); @@ -1073,7 +1073,7 @@ move_computations (void) memset (&walk_data, 0, sizeof (struct dom_walk_data)); walk_data.dom_direction = CDI_DOMINATORS; - walk_data.before_dom_children_before_stmts = move_computations_stmt; + walk_data.before_dom_children = move_computations_stmt; init_walk_dominator_tree (&walk_data); walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index b42c70d8152..8f200be81c1 100644 --- a/gcc/tree-ssa-loop-unswitch.c +++ b/gcc/tree-ssa-loop-unswitch.c @@ -32,7 +32,6 @@ along with GCC; see the file COPYING3. If not see #include "tree-dump.h" #include "timevar.h" #include "cfgloop.h" -#include "domwalk.h" #include "params.h" #include "tree-pass.h" #include "tree-inline.h" diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index 3cdb9b35335..8c3f71d32b6 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -1139,18 +1139,12 @@ get_non_trapping (void) /* Setup callbacks for the generic dominator tree walker. */ nontrap_set = nontrap; - 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 = nt_init_block; - walk_data.before_dom_children_walk_stmts = NULL; - 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 = nt_fini_block; + walk_data.before_dom_children = nt_init_block; + walk_data.after_dom_children = nt_fini_block; walk_data.global_data = NULL; walk_data.block_local_data_size = 0; - walk_data.interesting_blocks = NULL; init_walk_dominator_tree (&walk_data); walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c index 473bc9b90b4..f503ffc9271 100644 --- a/gcc/tree-ssa-threadedge.c +++ b/gcc/tree-ssa-threadedge.c @@ -36,7 +36,6 @@ along with GCC; see the file COPYING3. If not see #include "timevar.h" #include "tree-dump.h" #include "tree-flow.h" -#include "domwalk.h" #include "real.h" #include "tree-pass.h" #include "tree-ssa-propagate.h" diff --git a/gcc/tree-ssa-uncprop.c b/gcc/tree-ssa-uncprop.c index 59c9b44c617..1efea61bae0 100644 --- a/gcc/tree-ssa-uncprop.c +++ b/gcc/tree-ssa-uncprop.c @@ -289,9 +289,9 @@ struct equiv_hash_elt VEC(tree,heap) *equivalences; }; -static void uncprop_initialize_block (struct dom_walk_data *, basic_block); -static void uncprop_finalize_block (struct dom_walk_data *, basic_block); -static void uncprop_into_successor_phis (struct dom_walk_data *, basic_block); +static void uncprop_enter_block (struct dom_walk_data *, basic_block); +static void uncprop_leave_block (struct dom_walk_data *, basic_block); +static void uncprop_into_successor_phis (basic_block); /* Hashing and equality routines for the hash table. */ @@ -381,18 +381,12 @@ tree_ssa_uncprop (void) calculate_dominance_info (CDI_DOMINATORS); /* 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 = uncprop_initialize_block; - walk_data.before_dom_children_walk_stmts = NULL; - walk_data.before_dom_children_after_stmts = uncprop_into_successor_phis; - walk_data.after_dom_children_before_stmts = NULL; - walk_data.after_dom_children_walk_stmts = NULL; - walk_data.after_dom_children_after_stmts = uncprop_finalize_block; + walk_data.before_dom_children = uncprop_enter_block; + walk_data.after_dom_children = uncprop_leave_block; walk_data.global_data = NULL; walk_data.block_local_data_size = 0; - walk_data.interesting_blocks = NULL; /* Now initialize the dominator walker. */ init_walk_dominator_tree (&walk_data); @@ -432,8 +426,8 @@ tree_ssa_uncprop (void) the dominator tree. */ static void -uncprop_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, - basic_block bb ATTRIBUTE_UNUSED) +uncprop_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, + basic_block bb ATTRIBUTE_UNUSED) { /* Pop the topmost value off the equiv stack. */ tree value = VEC_pop (tree, equiv_stack); @@ -447,8 +441,7 @@ uncprop_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, /* Unpropagate values from PHI nodes in successor blocks of BB. */ static void -uncprop_into_successor_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, - basic_block bb) +uncprop_into_successor_phis (basic_block bb) { edge e; edge_iterator ei; @@ -476,7 +469,6 @@ uncprop_into_successor_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, /* Walk over the PHI nodes, unpropagating values. */ for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi)) { - /* Sigh. We'll have more efficient access to this one day. */ gimple phi = gsi_stmt (gsi); tree arg = PHI_ARG_DEF (phi, e->dest_idx); struct equiv_hash_elt equiv_hash_elt; @@ -556,8 +548,8 @@ single_incoming_edge_ignoring_loop_edges (basic_block bb) } static void -uncprop_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, - basic_block bb) +uncprop_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, + basic_block bb) { basic_block parent; edge e; @@ -583,6 +575,8 @@ uncprop_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, if (!recorded) VEC_safe_push (tree, heap, equiv_stack, NULL_TREE); + + uncprop_into_successor_phis (bb); } static bool |