From d1d2af7d413943e01d6a8216c9564d6651ca4474 Mon Sep 17 00:00:00 2001 From: law Date: Tue, 21 Mar 2006 05:07:37 +0000 Subject: [PATCH] * tree-pass.h (pass_phi_only_copy_prop): Delete. (pass_phi_only_cprop): Declare. * passes.c (init_optimization_passes): Replace pass_phi_only_copy_prop with phi_only_cprop * tree-ssa-dom.c (degenerate_phi_result): New function. (remove_stmt_or_phi, get_lhs_or_phi_result): Likewise. (get_rhs_or_phi_arg, propagate_rhs_into_lhs): Likewise. (eliminate_const_or_copy, eliminate_degenerate_phis_1): Likewise. (eliminate_degenerate_phis): Likewise. (pass_phi_only_cprop): New pass descriptor. * tree-ssa-copy.c (init_copy_prop): Lose PHIS_ONLY argument and support code. Callers updated. (execute_copy_prop, do_copy_prop): Likewise and corresponding changes. (store_copy_prop): Likewise. (do_phi_only_copy_prop, pass_phi_only_copy_prop): Remove. * gcc.dg/tree-ssa/pr21829.c: New test. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@112242 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 18 ++ gcc/passes.c | 33 +-- gcc/testsuite/ChangeLog | 2 + gcc/testsuite/gcc.dg/tree-ssa/pr21829.c | 21 ++ gcc/tree-pass.h | 2 +- gcc/tree-ssa-copy.c | 42 +--- gcc/tree-ssa-dom.c | 422 ++++++++++++++++++++++++++++++++ 7 files changed, 488 insertions(+), 52 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr21829.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index fb19e1f51eb..20c32c30cc9 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,21 @@ +2006-03-20 Jeff Law + + * tree-pass.h (pass_phi_only_copy_prop): Delete. + (pass_phi_only_cprop): Declare. + * passes.c (init_optimization_passes): Replace pass_phi_only_copy_prop + with phi_only_cprop + * tree-ssa-dom.c (degenerate_phi_result): New function. + (remove_stmt_or_phi, get_lhs_or_phi_result): Likewise. + (get_rhs_or_phi_arg, propagate_rhs_into_lhs): Likewise. + (eliminate_const_or_copy, eliminate_degenerate_phis_1): Likewise. + (eliminate_degenerate_phis): Likewise. + (pass_phi_only_cprop): New pass descriptor. + * tree-ssa-copy.c (init_copy_prop): Lose PHIS_ONLY argument and + support code. Callers updated. + (execute_copy_prop, do_copy_prop): Likewise and corresponding changes. + (store_copy_prop): Likewise. + (do_phi_only_copy_prop, pass_phi_only_copy_prop): Remove. + 2006-03-20 Jason Merrill PR c++/21764 diff --git a/gcc/passes.c b/gcc/passes.c index 4dd4ac8d8d8..ab37f20798f 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -505,11 +505,12 @@ init_optimization_passes (void) NEXT_PASS (pass_dce); NEXT_PASS (pass_dominator); - /* The only copy propagation opportunities left after DOM - should be due to degenerate PHI nodes. So rather than - run the full copy propagator, just discover and copy - propagate away the degenerate PHI nodes. */ - NEXT_PASS (pass_phi_only_copy_prop); + /* The only const/copy propagation opportunities left after + DOM should be due to degenerate PHI nodes. So rather than + run the full propagators, run a specialized pass which + only examines PHIs to discover const/copy propagation + opportunities. */ + NEXT_PASS (pass_phi_only_cprop); NEXT_PASS (pass_phiopt); NEXT_PASS (pass_may_alias); @@ -526,11 +527,12 @@ init_optimization_passes (void) NEXT_PASS (pass_rename_ssa_copies); NEXT_PASS (pass_dominator); - /* The only copy propagation opportunities left after DOM - should be due to degenerate PHI nodes. So rather than - run the full copy propagator, just discover and copy - propagate away the degenerate PHI nodes. */ - NEXT_PASS (pass_phi_only_copy_prop); + /* The only const/copy propagation opportunities left after + DOM should be due to degenerate PHI nodes. So rather than + run the full propagators, run a specialized pass which + only examines PHIs to discover const/copy propagation + opportunities. */ + NEXT_PASS (pass_phi_only_cprop); NEXT_PASS (pass_reassoc); NEXT_PASS (pass_dce); @@ -556,11 +558,12 @@ init_optimization_passes (void) NEXT_PASS (pass_vrp); NEXT_PASS (pass_dominator); - /* The only copy propagation opportunities left after DOM - should be due to degenerate PHI nodes. So rather than - run the full copy propagator, just discover and copy - propagate away the degenerate PHI nodes. */ - NEXT_PASS (pass_phi_only_copy_prop); + /* The only const/copy propagation opportunities left after + DOM should be due to degenerate PHI nodes. So rather than + run the full propagators, run a specialized pass which + only examines PHIs to discover const/copy propagation + opportunities. */ + NEXT_PASS (pass_phi_only_cprop); NEXT_PASS (pass_cd_dce); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index bdb9512c139..8b5095299b4 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,5 +1,7 @@ 2006-03-20 Jeff Law + * gcc.dg/tree-ssa/pr21829.c: New test. + * gcc.dg/tree-ssa/20030807-2.c: Make sure to run VRP. 2006-03-20 Richard Sandiford diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr21829.c b/gcc/testsuite/gcc.dg/tree-ssa/pr21829.c new file mode 100644 index 00000000000..4c723f3ff86 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr21829.c @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-phicprop-details" } */ + +int test(int v) +{ + int x = 0; + int u; + for (u=0;u<2;u++) + { + if (u>v) + { + if (u%2==1) + x++; + } + } + return x; +} + +/* { dg-final { scan-tree-dump-times "Original statement:.*% 2\[ \t\n]*Updated statement.*=1" 0 "phicprop3" } } */ +/* { dg-final { cleanup-tree-dump "phicprop3" } } */ + diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 5e0b9233e1c..6a457cabf63 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -257,6 +257,7 @@ extern struct tree_opt_pass pass_iv_optimize; extern struct tree_opt_pass pass_tree_loop_done; extern struct tree_opt_pass pass_ch; extern struct tree_opt_pass pass_ccp; +extern struct tree_opt_pass pass_phi_only_cprop; extern struct tree_opt_pass pass_build_ssa; extern struct tree_opt_pass pass_del_ssa; extern struct tree_opt_pass pass_dominator; @@ -295,7 +296,6 @@ extern struct tree_opt_pass pass_sink_code; extern struct tree_opt_pass pass_fre; extern struct tree_opt_pass pass_linear_transform; extern struct tree_opt_pass pass_copy_prop; -extern struct tree_opt_pass pass_phi_only_copy_prop; extern struct tree_opt_pass pass_store_ccp; extern struct tree_opt_pass pass_store_copy_prop; extern struct tree_opt_pass pass_vrp; diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c index e0e2a4faf1f..ea8a39e6ab8 100644 --- a/gcc/tree-ssa-copy.c +++ b/gcc/tree-ssa-copy.c @@ -843,7 +843,7 @@ copy_prop_visit_phi_node (tree phi) opportunities. */ static void -init_copy_prop (bool phis_only) +init_copy_prop (void) { basic_block bb; @@ -868,7 +868,7 @@ init_copy_prop (bool phis_only) lists of the propagator. */ if (stmt_ends_bb_p (stmt)) DONT_SIMULATE_AGAIN (stmt) = false; - else if (!phis_only && stmt_may_generate_copy (stmt)) + else if (stmt_may_generate_copy (stmt)) DONT_SIMULATE_AGAIN (stmt) = false; else { @@ -1027,10 +1027,10 @@ fini_copy_prop (void) x_53 and x_54 are both copies of x_898. */ static void -execute_copy_prop (bool store_copy_prop, bool phis_only) +execute_copy_prop (bool store_copy_prop) { do_store_copy_prop = store_copy_prop; - init_copy_prop (phis_only); + init_copy_prop (); ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node); fini_copy_prop (); } @@ -1045,7 +1045,7 @@ gate_copy_prop (void) static unsigned int do_copy_prop (void) { - execute_copy_prop (false, false); + execute_copy_prop (false); return 0; } @@ -1070,36 +1070,6 @@ struct tree_opt_pass pass_copy_prop = 0 /* letter */ }; - -static unsigned int -do_phi_only_copy_prop (void) -{ - execute_copy_prop (false, true); - return 0; -} - -struct tree_opt_pass pass_phi_only_copy_prop = -{ - "phionlycopyprop", /* name */ - gate_copy_prop, /* gate */ - do_phi_only_copy_prop, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - TV_TREE_COPY_PROP, /* tv_id */ - PROP_ssa | PROP_alias | PROP_cfg, /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_cleanup_cfg - | TODO_dump_func - | TODO_ggc_collect - | TODO_verify_ssa - | TODO_update_ssa, /* todo_flags_finish */ - 0 /* letter */ -}; - - static bool gate_store_copy_prop (void) { @@ -1114,7 +1084,7 @@ static unsigned int store_copy_prop (void) { /* If STORE-COPY-PROP is not enabled, we just run regular COPY-PROP. */ - execute_copy_prop (flag_tree_store_copy_prop != 0, false); + execute_copy_prop (flag_tree_store_copy_prop != 0); return 0; } diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index 5a28e7830e2..daa2f0ea81d 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -2020,3 +2020,425 @@ avail_expr_eq (const void *p1, const void *p2) return false; } + +/* PHI-ONLY copy and constant propagation. This pass is meant to clean + up degenerate PHIs created by or exposed by jump threading. */ + +/* Given PHI, return its RHS if the PHI is a degenerate, otherwise return + NULL. */ + +static tree +degenerate_phi_result (tree phi) +{ + tree lhs = PHI_RESULT (phi); + tree val = NULL; + int i; + + /* Ignoring arguments which are the same as LHS, if all the remaining + arguments are the same, then the PHI is a degenerate and has the + value of that common argument. */ + for (i = 0; i < PHI_NUM_ARGS (phi); i++) + { + tree arg = PHI_ARG_DEF (phi, i); + + if (arg == lhs) + continue; + else if (!val) + val = arg; + else if (!operand_equal_p (arg, val, 0)) + break; + } + return (i == PHI_NUM_ARGS (phi) ? val : NULL); +} + +/* Given a tree node T, which is either a PHI_NODE or MODIFY_EXPR, + remove it from the IL. */ + +static void +remove_stmt_or_phi (tree t) +{ + if (TREE_CODE (t) == PHI_NODE) + remove_phi_node (t, NULL); + else + { + block_stmt_iterator bsi = bsi_for_stmt (t); + bsi_remove (&bsi, true); + } +} + +/* Given a tree node T, which is either a PHI_NODE or MODIFY_EXPR, + return the "rhs" of the node, in the case of a non-degenerate + PHI, NULL is returned. */ + +static tree +get_rhs_or_phi_arg (tree t) +{ + if (TREE_CODE (t) == PHI_NODE) + return degenerate_phi_result (t); + else if (TREE_CODE (t) == MODIFY_EXPR) + return TREE_OPERAND (t, 1); + gcc_unreachable (); +} + + +/* Given a tree node T, which is either a PHI_NODE or a MODIFY_EXPR, + return the "lhs" of the node. */ + +static tree +get_lhs_or_phi_result (tree t) +{ + if (TREE_CODE (t) == PHI_NODE) + return PHI_RESULT (t); + else if (TREE_CODE (t) == MODIFY_EXPR) + return TREE_OPERAND (t, 0); + gcc_unreachable (); +} + +/* Propagate RHS into all uses of LHS (when possible). + + RHS and LHS are derived from STMT, which is passed in solely so + that we can remove it if propagation is successful. + + When propagating into a PHI node or into a statement which turns + into a trivial copy or constant initialization, set the + appropriate bit in INTERESTING_NAMEs so that we will visit those + nodes as well in an effort to pick up secondary optimization + opportunities. */ + +static void +propagate_rhs_into_lhs (tree stmt, tree lhs, tree rhs, bitmap interesting_names) +{ + /* First verify that propagation is valid and isn't going to move a + loop variant variable outside its loop. */ + if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) + && (TREE_CODE (rhs) != SSA_NAME + || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) + && may_propagate_copy (lhs, rhs) + && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs)) + { + use_operand_p use_p; + imm_use_iterator iter; + bool all = true; + + /* Dump details. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Replacing '"); + print_generic_expr (dump_file, lhs, dump_flags); + fprintf (dump_file, "' with %s '", + (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable")); + print_generic_expr (dump_file, rhs, dump_flags); + fprintf (dump_file, "'\n"); + } + + /* Walk over every use of LHS and try to replace the use with RHS. + At this point the only reason why such a propagation would not + be successful would be if the use occurs in an ASM_EXPR. */ + FOR_EACH_IMM_USE_SAFE (use_p, iter, lhs) + { + tree use_stmt = USE_STMT (use_p); + + /* It's not always safe to propagate into an ASM_EXPR. */ + if (TREE_CODE (use_stmt) == ASM_EXPR + && ! may_propagate_copy_into_asm (lhs)) + { + all = false; + continue; + } + + /* Dump details. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Original statement:"); + print_generic_expr (dump_file, use_stmt, dump_flags); + fprintf (dump_file, "\n"); + } + + /* Propagate, fold and update the statement. Note this may + expose new const/copy propagation opportunities as well + collapse control statements. */ + propagate_value (use_p, rhs); + fold_stmt_inplace (use_stmt); + update_stmt (use_stmt); + + /* Dump details. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " Updated statement:"); + print_generic_expr (dump_file, use_stmt, dump_flags); + fprintf (dump_file, "\n"); + } + + /* Sometimes propagation can expose new operands to the + renamer. */ + mark_new_vars_to_rename (use_stmt); + + /* If we replaced a variable index with a constant, then + we would need to update the invariant flag for ADDR_EXPRs. */ + if (TREE_CODE (use_stmt) == MODIFY_EXPR + && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (TREE_OPERAND (use_stmt, 1)); + + /* If we cleaned up EH information from the statement, + remove EH edges. I'm not sure if this happens in + practice with this code, but better safe than sorry. */ + if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt)) + tree_purge_dead_eh_edges (bb_for_stmt (use_stmt)); + + /* Propagation may expose new degenerate PHIs or + trivial copy/constant propagation opportunities. */ + if (TREE_CODE (use_stmt) == PHI_NODE + || (TREE_CODE (use_stmt) == MODIFY_EXPR + && TREE_CODE (TREE_OPERAND (use_stmt, 0)) == SSA_NAME + && (TREE_CODE (TREE_OPERAND (use_stmt, 1)) == SSA_NAME + || is_gimple_min_invariant (TREE_OPERAND (use_stmt, 1))))) + { + tree result = get_lhs_or_phi_result (use_stmt); + bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); + } + + /* Propagation into these nodes may make certain edges in + the CFG unexecutable. We want to identify them as PHI nodes + at the destination of those unexecutable edges may become + degenerates. */ + else if (TREE_CODE (use_stmt) == COND_EXPR + || TREE_CODE (use_stmt) == SWITCH_EXPR + || TREE_CODE (use_stmt) == GOTO_EXPR) + { + tree val; + + if (TREE_CODE (use_stmt) == COND_EXPR) + val = COND_EXPR_COND (use_stmt); + else if (TREE_CODE (use_stmt) == SWITCH_EXPR) + val = SWITCH_COND (use_stmt); + else + val = GOTO_DESTINATION (use_stmt); + + if (is_gimple_min_invariant (val)) + { + basic_block bb = bb_for_stmt (use_stmt); + edge te = find_taken_edge (bb, val); + edge_iterator ei; + edge e; + block_stmt_iterator bsi; + + /* Remove all outgoing edges except TE. */ + for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));) + { + if (e != te) + { + tree phi; + + /* Mark all the PHI nodes at the destination of + the unexecutable edge as interesting. */ + for (phi = phi_nodes (e->dest); + phi; + phi = PHI_CHAIN (phi)) + { + tree result = PHI_RESULT (phi); + int version = SSA_NAME_VERSION (result); + + bitmap_set_bit (interesting_names, version); + } + + te->probability += e->probability; + + te->count += e->count; + remove_edge (e); + cfg_altered = 1; + } + else + ei_next (&ei); + } + + bsi = bsi_last (bb_for_stmt (use_stmt)); + bsi_remove (&bsi, true); + + /* And fixup the flags on the single remaining edge. */ + te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); + te->flags &= ~EDGE_ABNORMAL; + te->flags |= EDGE_FALLTHRU; + if (te->probability > REG_BR_PROB_BASE) + te->probability = REG_BR_PROB_BASE; + } + } + } + + /* If we were able to propagate away all uses of LHS, then + we can remove STMT. */ + if (all) + remove_stmt_or_phi (stmt); + } +} + +/* T is either a PHI node (potentally a degenerate PHI node) or + a statement that is a trivial copy or constant initialization. + + Attempt to eliminate T by propagating its RHS into all uses of + its LHS. This may in turn set new bits in INTERESTING_NAMES + for nodes we want to revisit later. + + All exit paths should clear INTERESTING_NAMES for the result + of T. */ + +static void +eliminate_const_or_copy (tree t, bitmap interesting_names) +{ + tree lhs = get_lhs_or_phi_result (t); + tree rhs; + int version = SSA_NAME_VERSION (lhs); + + /* If the LHS of this statement or PHI has no uses, then we can + just eliminate it. This can occur if, for example, the PHI + was created by block duplication due to threading and its only + use was in the conditional at the end of the block which was + deleted. */ + if (has_zero_uses (lhs)) + { + bitmap_clear_bit (interesting_names, version); + remove_stmt_or_phi (t); + return; + } + + /* Get the RHS of the assignment or PHI node if the PHI is a + degenerate. */ + rhs = get_rhs_or_phi_arg (t); + if (!rhs) + { + bitmap_clear_bit (interesting_names, version); + return; + } + + propagate_rhs_into_lhs (t, lhs, rhs, interesting_names); + + /* Note that T may well have been deleted by now, so do + not access it, instead use the saved version # to clear + T's entry in the worklist. */ + bitmap_clear_bit (interesting_names, version); +} + +/* The first phase in degenerate PHI elimination. + + Eliminate the degenerate PHIs in BB, then recurse on the + dominator children of BB. */ + +static void +eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names) +{ + tree phi, next; + basic_block son; + + for (phi = phi_nodes (bb); phi; phi = next) + { + next = PHI_CHAIN (phi); + eliminate_const_or_copy (phi, interesting_names); + } + + /* Recurse into the dominator children of BB. */ + for (son = first_dom_son (CDI_DOMINATORS, bb); + son; + son = next_dom_son (CDI_DOMINATORS, son)) + eliminate_degenerate_phis_1 (son, interesting_names); +} + + +/* A very simple pass to eliminate degenerate PHI nodes from the + IL. This is meant to be fast enough to be able to be run several + times in the optimization pipeline. + + Certain optimizations, particularly those which duplicate blocks + or remove edges from the CFG can create or expose PHIs which are + trivial copies or constant initializations. + + While we could pick up these optimizations in DOM or with the + combination of copy-prop and CCP, those solutions are far too + heavy-weight for our needs. + + This implementation has two phases so that we can efficiently + eliminate the first order degenerate PHIs and second order + degenerate PHIs. + + The first phase performs a dominator walk to identify and eliminate + the vast majority of the degenerate PHIs. When a degenerate PHI + is identified and eliminated any affected statements or PHIs + are put on a worklist. + + The second phase eliminates degenerate PHIs and trivial copies + or constant initializations using the worklist. This is how we + pick up the secondary optimization opportunities with minimal + cost. */ + +static unsigned int +eliminate_degenerate_phis (void) +{ + bitmap interesting_names; + + /* INTERESTING_NAMES is effectively our worklist, indexed by + SSA_NAME_VERSION. + + A set bit indicates that the statement or PHI node which + defines the SSA_NAME should be (re)examined to determine if + it has become a degenerate PHI or trival const/copy propagation + opportunity. + + Experiments have show we generally get better compilation + time behavior with bitmaps rather than sbitmaps. */ + interesting_names = BITMAP_ALLOC (NULL); + + /* First phase. Elimiante degenerate PHIs via a domiantor + walk of the CFG. + + Experiments have indicated that we generally get better + compile-time behavior by visiting blocks in the first + phase in dominator order. Presumably this is because walking + in dominator order leaves fewer PHIs for later examination + by the worklist phase. */ + calculate_dominance_info (CDI_DOMINATORS); + eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names); + + /* Second phase. Eliminate second order degnerate PHIs as well + as trivial copies or constant initializations identified by + the first phase or this phase. Basically we keep iterating + until our set of INTERESTING_NAMEs is empty. */ + while (!bitmap_empty_p (interesting_names)) + { + unsigned int i; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (interesting_names, 0, i, bi) + { + tree name = ssa_name (i); + + /* Ignore SSA_NAMEs that have been released because + their defining statement was deleted (unreachable). */ + if (name) + eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)), + interesting_names); + } + } + + BITMAP_FREE (interesting_names); + if (cfg_altered) + free_dominance_info (CDI_DOMINATORS); + return 0; +} + +struct tree_opt_pass pass_phi_only_cprop = +{ + "phicprop", /* name */ + gate_dominator, /* gate */ + eliminate_degenerate_phis, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_CCP, /* tv_id */ + PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ + 0, /* properties_provided */ + PROP_smt_usage, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_cleanup_cfg | TODO_dump_func + | TODO_ggc_collect | TODO_verify_ssa + | TODO_verify_stmts | TODO_update_smt_usage + | TODO_update_ssa, /* todo_flags_finish */ + 0 /* letter */ +}; -- 2.11.0