* Re: [RFA][PATCH][PR middle-end/57904][P1 regression] Improve cleanups after copyprop
2014-01-15 22:16 ` Marek Polacek
@ 2014-01-16 5:50 ` Jeff Law
0 siblings, 0 replies; 6+ messages in thread
From: Jeff Law @ 2014-01-16 5:50 UTC (permalink / raw)
To: Marek Polacek; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 79 bytes --]
On 01/15/14 15:15, Marek Polacek wrote:
> -ENOPATCH
>
Nuts.
Patch attached.
[-- Attachment #2: patch --]
[-- Type: text/plain, Size: 44052 bytes --]
* tree-ssa-propagate.c (substitute_and_fold): Add argument for
statement folded notification callbacks. Use it.
* tree-ssa-propagate.h (substitute_and_fold): Update prototype.
* tree-ssa-ccp.c (ccp_finalize): Pass NULL for folded notification
callback to substitute_and_fold.
* tree-vrp.c (vrp_finalize): Likewise.
* tree-ssa-dom.c (remove_stmt_or_phi): Moved into tree-ssa-copy.c
(get_rhs_or_phi_arg, get_lhs_or_phi_result): Likewise.
(propagate_rhs_into_lhs, eliminate_const_or_copy): Likewise.
(eliminate_degenerate_phis, eliminate_degenerate_phis_1): Likewise.
(pass_data_phi_only_cprop, make_pass_phi_only_cprop): Likewise.
* tree-ssa-copy.c: Include gimple-fold.h and tree-eh.h
(interesting_names, need_eh_cleanup): New file scoped bitmaps.
(cfg_altered): New file scoped boolean.
(remove_stmt_or_phi): Moved from tree-ssa-copy.c
(get_rhs_or_phi_arg, get_lhs_or_phi_result): Likewise.
(propagate_rhs_into_lhs, eliminate_const_or_copy): Likewise.
(eliminate_degenerate_phis, eliminate_degenerate_phis_1): Likewise.
(pass_data_phi_only_cprop, make_pass_phi_only_cprop): Likewise.
(eliminate_degenerate_phis_2): New, broken out of
eliminate_degenerate_phis_1.
(stmt_may_generate_copy): Refine to reject binary ops where the
first argument is a constant.
(copy_prop_visit_stmt): Use stmt_may_generate_copy.
(notify_fn): New function.
(fini_copy_prop): Initialize/finalize new file scoped statics.
Pass notify_fn to substitute_and_fold. After substitute_and_fold,
call eliminate_degnerate_phis_2 to do trivial const/copy propagations
enabled by substitute_and_fold. Cleanup the CFG, EH structures, etc
as needed.
testsuite/
* gfortran.dg/pr57904.f90: New test.
diff --git a/gcc/tree-ssa-ccp.c b/gcc/tree-ssa-ccp.c
index 493bbcb..a17a490 100644
--- a/gcc/tree-ssa-ccp.c
+++ b/gcc/tree-ssa-ccp.c
@@ -901,7 +901,7 @@ ccp_finalize (void)
/* Perform substitutions based on the known constant values. */
something_changed = substitute_and_fold (get_constant_value,
- ccp_fold_stmt, true);
+ ccp_fold_stmt, NULL, true);
free (const_val);
const_val = NULL;
diff --git a/gcc/tree-ssa-copy.c b/gcc/tree-ssa-copy.c
index 02f4743..bb7ada5 100644
--- a/gcc/tree-ssa-copy.c
+++ b/gcc/tree-ssa-copy.c
@@ -36,6 +36,8 @@ along with GCC; see the file COPYING3. If not see
#include "gimple-ssa.h"
#include "tree-cfg.h"
#include "tree-phinodes.h"
+#include "gimple-fold.h"
+#include "tree-eh.h"
#include "ssa-iterators.h"
#include "stringpool.h"
#include "tree-ssanames.h"
@@ -83,6 +85,22 @@ typedef struct prop_value_d prop_value_t;
static prop_value_t *copy_of;
static unsigned n_copy_of;
+/* During the substitute_and_fold phase of this optimizer, we get
+ a callback for statement that is simplified. If the statement
+ simplifies to a copy or constant initialization, then we set the
+ bit for the LHS of the statement in this bitmap to seed the
+ trivial propagator. */
+static bitmap interesting_names;
+
+/* Track whether or not we modify the CFG and thus require recomputation
+ of dominators, loop fixups, etc. */
+static bool cfg_altered;
+
+/* Track if we simplify a statement so that it no longer can throw. If
+ so, we'll have to purge dead EH edges when we're done. */
+static bitmap need_eh_cleanup;
+
+static void eliminate_degenerate_phis_2 (bitmap);
/* Return true if this statement may generate a useful copy. */
@@ -106,10 +124,14 @@ stmt_may_generate_copy (gimple stmt)
/* Otherwise, the only statements that generate useful copies are
assignments whose RHS is just an SSA name that doesn't flow
- through abnormal edges. */
- return ((gimple_assign_rhs_code (stmt) == SSA_NAME
+ through abnormal edges or when the RHS is an ADDR_EXPR or converted
+ ADDR_EXPR. */
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ return ((code == SSA_NAME
&& !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
- || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)));
+ || ((get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS
+ || get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
+ && is_gimple_min_invariant (gimple_assign_rhs1 (stmt))));
}
@@ -299,10 +321,7 @@ copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
fprintf (dump_file, "\n");
}
- if (gimple_assign_single_p (stmt)
- && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
- && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
- || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
+ if (stmt_may_generate_copy (stmt))
{
/* If the statement is a copy assignment, evaluate its RHS to
see if the lattice value of its output has changed. */
@@ -540,6 +559,18 @@ get_value (tree name)
return NULL_TREE;
}
+/* Callback when a statement simplifies during the substitute_and_fold
+ phase of this optimizer. */
+static void
+notify_fn (gimple stmt)
+{
+ if (stmt_may_generate_copy (stmt))
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ bitmap_set_bit (interesting_names, SSA_NAME_VERSION (lhs));
+ }
+}
+
/* Deallocate memory used in copy propagation and do final
substitution. */
@@ -595,9 +626,33 @@ fini_copy_prop (void)
}
}
- /* Don't do DCE if SCEV is initialized. It would destroy the scev cache. */
- substitute_and_fold (get_value, NULL, !scev_initialized_p ());
+ interesting_names = BITMAP_ALLOC (NULL);
+ /* Don't do DCE if SCEV is initialized. It would destroy the scev cache.
+ Similarly, don't use the simplification callback in that case as it
+ also does DCE. */
+ substitute_and_fold (get_value, NULL,
+ !scev_initialized_p () ? notify_fn : NULL,
+ !scev_initialized_p ());
+ cfg_altered = false;
+ need_eh_cleanup = BITMAP_ALLOC (NULL);
+ eliminate_degenerate_phis_2 (interesting_names);
+ BITMAP_FREE (interesting_names);
+
+ if (cfg_altered)
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ /* If we changed the CFG schedule loops for fixup by cfgcleanup. */
+ if (current_loops)
+ loops_state_set (LOOPS_NEED_FIXUP);
+ }
+
+ if (!bitmap_empty_p (need_eh_cleanup))
+ {
+ gimple_purge_all_dead_eh_edges (need_eh_cleanup);
+ }
+
+ BITMAP_FREE (need_eh_cleanup);
free (copy_of);
}
@@ -689,3 +744,539 @@ make_pass_copy_prop (gcc::context *ctxt)
{
return new pass_copy_prop (ctxt);
}
+
+/* PHI-ONLY copy and constant propagation. This pass is meant to clean
+ up degenerate PHIs created by or exposed by jump threading. */
+
+/* Given a statement STMT, which is either a PHI node or an assignment,
+ remove it from the IL. */
+
+static void
+remove_stmt_or_phi (gimple stmt)
+{
+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ remove_phi_node (&gsi, true);
+ else
+ {
+ gsi_remove (&gsi, true);
+ release_defs (stmt);
+ }
+}
+
+/* Given a statement STMT, which is either a PHI node or an assignment,
+ return the "rhs" of the node, in the case of a non-degenerate
+ phi, NULL is returned. */
+
+static tree
+get_rhs_or_phi_arg (gimple stmt)
+{
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ return degenerate_phi_result (stmt);
+ else if (is_gimple_assign (stmt))
+ {
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS
+ || get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
+ return gimple_assign_rhs1 (stmt);
+ }
+ gcc_unreachable ();
+}
+
+
+/* Given a statement STMT, which is either a PHI node or an assignment,
+ return the "lhs" of the node. */
+
+static tree
+get_lhs_or_phi_result (gimple stmt)
+{
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ return gimple_phi_result (stmt);
+ else if (is_gimple_assign (stmt))
+ return gimple_assign_lhs (stmt);
+ else
+ 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 (gimple 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;
+ gimple use_stmt;
+ 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_STMT (use_stmt, iter, lhs)
+ {
+ /* Leave debug stmts alone. If we succeed in propagating
+ all non-debug uses, we'll drop the DEF, and propagation
+ into debug stmts will occur then. */
+ if (gimple_debug_bind_p (use_stmt))
+ continue;
+
+ /* It's not always safe to propagate into an ASM_EXPR. */
+ if (gimple_code (use_stmt) == GIMPLE_ASM
+ && ! may_propagate_copy_into_asm (lhs))
+ {
+ all = false;
+ continue;
+ }
+
+ /* It's not ok to propagate into the definition stmt of RHS.
+ <bb 9>:
+ # prephitmp.12_36 = PHI <g_67.1_6(9)>
+ g_67.1_6 = prephitmp.12_36;
+ goto <bb 9>;
+ While this is strictly all dead code we do not want to
+ deal with this here. */
+ if (TREE_CODE (rhs) == SSA_NAME
+ && SSA_NAME_DEF_STMT (rhs) == use_stmt)
+ {
+ all = false;
+ continue;
+ }
+
+ /* Dump details. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Original statement:");
+ print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
+ }
+
+ /* Propagate the RHS into this use of the LHS. */
+ FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+ propagate_value (use_p, rhs);
+
+ /* Special cases to avoid useless calls into the folding
+ routines, operand scanning, etc.
+
+ Propagation into a PHI may cause the PHI to become
+ a degenerate, so mark the PHI as interesting. No other
+ actions are necessary. */
+ if (gimple_code (use_stmt) == GIMPLE_PHI)
+ {
+ tree result;
+
+ /* Dump details. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Updated statement:");
+ print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
+ }
+
+ result = get_lhs_or_phi_result (use_stmt);
+ bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
+ continue;
+ }
+
+ /* From this point onward we are propagating into a
+ real statement. Folding may (or may not) be possible,
+ we may expose new operands, expose dead EH edges,
+ etc. */
+ /* NOTE tuples. In the tuples world, fold_stmt_inplace
+ cannot fold a call that simplifies to a constant,
+ because the GIMPLE_CALL must be replaced by a
+ GIMPLE_ASSIGN, and there is no way to effect such a
+ transformation in-place. We might want to consider
+ using the more general fold_stmt here. */
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
+ fold_stmt_inplace (&gsi);
+ }
+
+ /* Sometimes propagation can expose new operands to the
+ renamer. */
+ update_stmt (use_stmt);
+
+ /* Dump details. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Updated statement:");
+ print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
+ }
+
+ /* If we replaced a variable index with a constant, then
+ we would need to update the invariant flag for ADDR_EXPRs. */
+ if (gimple_assign_single_p (use_stmt)
+ && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
+ recompute_tree_invariant_for_addr_expr
+ (gimple_assign_rhs1 (use_stmt));
+
+ /* If we cleaned up EH information from the statement,
+ mark its containing block as needing EH cleanups. */
+ if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
+ {
+ bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Flagged to clear EH edges.\n");
+ }
+
+ /* Propagation may expose new trivial copy/constant propagation
+ opportunities. */
+ if (stmt_may_generate_copy (use_stmt))
+ {
+ 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 (gimple_code (use_stmt) == GIMPLE_COND
+ || gimple_code (use_stmt) == GIMPLE_SWITCH
+ || gimple_code (use_stmt) == GIMPLE_GOTO)
+ {
+ tree val;
+
+ if (gimple_code (use_stmt) == GIMPLE_COND)
+ val = fold_binary_loc (gimple_location (use_stmt),
+ gimple_cond_code (use_stmt),
+ boolean_type_node,
+ gimple_cond_lhs (use_stmt),
+ gimple_cond_rhs (use_stmt));
+ else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
+ val = gimple_switch_index (use_stmt);
+ else
+ val = gimple_goto_dest (use_stmt);
+
+ if (val && is_gimple_min_invariant (val))
+ {
+ basic_block bb = gimple_bb (use_stmt);
+ edge te = find_taken_edge (bb, val);
+ edge_iterator ei;
+ edge e;
+ gimple_stmt_iterator gsi, psi;
+
+ /* Remove all outgoing edges except TE. */
+ for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
+ {
+ if (e != te)
+ {
+ /* Mark all the PHI nodes at the destination of
+ the unexecutable edge as interesting. */
+ for (psi = gsi_start_phis (e->dest);
+ !gsi_end_p (psi);
+ gsi_next (&psi))
+ {
+ gimple phi = gsi_stmt (psi);
+
+ tree result = gimple_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 = true;
+ }
+ else
+ ei_next (&ei);
+ }
+
+ gsi = gsi_last_bb (gimple_bb (use_stmt));
+ gsi_remove (&gsi, 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;
+ }
+ }
+ }
+
+ /* Ensure there is nothing else to do. */
+ gcc_assert (!all || has_zero_uses (lhs));
+
+ /* If we were able to propagate away all uses of LHS, then
+ we can remove STMT. */
+ if (all)
+ remove_stmt_or_phi (stmt);
+ }
+}
+
+/* STMT is either a PHI node (potentially 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 STMT. */
+
+static void
+eliminate_const_or_copy (gimple stmt, bitmap interesting_names)
+{
+ tree lhs = get_lhs_or_phi_result (stmt);
+ 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 (stmt);
+ return;
+ }
+
+ /* Get the RHS of the assignment or PHI node if the PHI is a
+ degenerate. */
+ rhs = get_rhs_or_phi_arg (stmt);
+ if (!rhs)
+ {
+ bitmap_clear_bit (interesting_names, version);
+ return;
+ }
+
+ if (!virtual_operand_p (lhs))
+ propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
+ else
+ {
+ gimple use_stmt;
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ /* For virtual operands we have to propagate into all uses as
+ otherwise we will create overlapping life-ranges. */
+ FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
+ FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+ SET_USE (use_p, rhs);
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
+ remove_stmt_or_phi (stmt);
+ }
+
+ /* Note that STMT 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)
+{
+ gimple_stmt_iterator gsi;
+ basic_block son;
+
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+
+ 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);
+}
+
+/* Eliminate second order degnerate PHIs as well as trivial
+ copies or constant initializations. INTERESTING_NAMES is a
+ seed of already identified degenerate PHIS, trivial copies
+ or constant initializations. */
+static void
+eliminate_degenerate_phis_2 (bitmap interesting_names)
+{
+ bitmap interesting_names1 = BITMAP_ALLOC (NULL);
+
+ /* Second phase. Eliminate second order degenerate 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 does not like its bitmap
+ changed during the loop. Copy it to another bitmap and
+ use that. */
+ bitmap_copy (interesting_names1, interesting_names);
+
+ EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 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 (name),
+ interesting_names);
+ }
+ }
+ BITMAP_FREE (interesting_names1);
+}
+
+
+/* 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;
+
+ /* Bitmap of blocks which need EH information updated. We can not
+ update it on-the-fly as doing so invalidates the dominator tree. */
+ need_eh_cleanup = BITMAP_ALLOC (NULL);
+
+ /* 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 trivial const/copy propagation
+ opportunity.
+
+ Experiments have show we generally get better compilation
+ time behavior with bitmaps rather than sbitmaps. */
+ interesting_names = BITMAP_ALLOC (NULL);
+
+ calculate_dominance_info (CDI_DOMINATORS);
+ cfg_altered = false;
+
+ /* First phase. Eliminate degenerate PHIs via a dominator
+ 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. */
+ eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (cfun),
+ interesting_names);
+
+ eliminate_degenerate_phis_2 (interesting_names);
+
+ if (cfg_altered)
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ /* If we changed the CFG schedule loops for fixup by cfgcleanup. */
+ if (current_loops)
+ loops_state_set (LOOPS_NEED_FIXUP);
+ }
+
+ /* Propagation of const and copies may make some EH edges dead. Purge
+ such edges from the CFG as needed. */
+ if (!bitmap_empty_p (need_eh_cleanup))
+ {
+ gimple_purge_all_dead_eh_edges (need_eh_cleanup);
+ BITMAP_FREE (need_eh_cleanup);
+ }
+
+ BITMAP_FREE (interesting_names);
+ return 0;
+}
+
+namespace {
+
+const pass_data pass_data_phi_only_cprop =
+{
+ GIMPLE_PASS, /* type */
+ "phicprop", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ false, /* has_gate */
+ true, /* has_execute */
+ TV_TREE_PHI_CPROP, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ ( TODO_cleanup_cfg | TODO_verify_ssa
+ | TODO_verify_stmts
+ | TODO_update_ssa ), /* todo_flags_finish */
+};
+
+class pass_phi_only_cprop : public gimple_opt_pass
+{
+public:
+ pass_phi_only_cprop (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_phi_only_cprop, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_phi_only_cprop (m_ctxt); }
+ unsigned int execute () { return eliminate_degenerate_phis (); }
+
+}; // class pass_phi_only_cprop
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_phi_only_cprop (gcc::context *ctxt)
+{
+ return new pass_phi_only_cprop (ctxt);
+}
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 98cf608..eb713d1 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -2624,529 +2624,3 @@ avail_expr_hash (const void *p)
return val;
}
-
-/* PHI-ONLY copy and constant propagation. This pass is meant to clean
- up degenerate PHIs created by or exposed by jump threading. */
-
-/* Given a statement STMT, which is either a PHI node or an assignment,
- remove it from the IL. */
-
-static void
-remove_stmt_or_phi (gimple stmt)
-{
- gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
-
- if (gimple_code (stmt) == GIMPLE_PHI)
- remove_phi_node (&gsi, true);
- else
- {
- gsi_remove (&gsi, true);
- release_defs (stmt);
- }
-}
-
-/* Given a statement STMT, which is either a PHI node or an assignment,
- return the "rhs" of the node, in the case of a non-degenerate
- phi, NULL is returned. */
-
-static tree
-get_rhs_or_phi_arg (gimple stmt)
-{
- if (gimple_code (stmt) == GIMPLE_PHI)
- return degenerate_phi_result (stmt);
- else if (gimple_assign_single_p (stmt))
- return gimple_assign_rhs1 (stmt);
- else
- gcc_unreachable ();
-}
-
-
-/* Given a statement STMT, which is either a PHI node or an assignment,
- return the "lhs" of the node. */
-
-static tree
-get_lhs_or_phi_result (gimple stmt)
-{
- if (gimple_code (stmt) == GIMPLE_PHI)
- return gimple_phi_result (stmt);
- else if (is_gimple_assign (stmt))
- return gimple_assign_lhs (stmt);
- else
- 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 (gimple 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;
- gimple use_stmt;
- 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_STMT (use_stmt, iter, lhs)
- {
- /* Leave debug stmts alone. If we succeed in propagating
- all non-debug uses, we'll drop the DEF, and propagation
- into debug stmts will occur then. */
- if (gimple_debug_bind_p (use_stmt))
- continue;
-
- /* It's not always safe to propagate into an ASM_EXPR. */
- if (gimple_code (use_stmt) == GIMPLE_ASM
- && ! may_propagate_copy_into_asm (lhs))
- {
- all = false;
- continue;
- }
-
- /* It's not ok to propagate into the definition stmt of RHS.
- <bb 9>:
- # prephitmp.12_36 = PHI <g_67.1_6(9)>
- g_67.1_6 = prephitmp.12_36;
- goto <bb 9>;
- While this is strictly all dead code we do not want to
- deal with this here. */
- if (TREE_CODE (rhs) == SSA_NAME
- && SSA_NAME_DEF_STMT (rhs) == use_stmt)
- {
- all = false;
- continue;
- }
-
- /* Dump details. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Original statement:");
- print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
- }
-
- /* Propagate the RHS into this use of the LHS. */
- FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
- propagate_value (use_p, rhs);
-
- /* Special cases to avoid useless calls into the folding
- routines, operand scanning, etc.
-
- Propagation into a PHI may cause the PHI to become
- a degenerate, so mark the PHI as interesting. No other
- actions are necessary. */
- if (gimple_code (use_stmt) == GIMPLE_PHI)
- {
- tree result;
-
- /* Dump details. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Updated statement:");
- print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
- }
-
- result = get_lhs_or_phi_result (use_stmt);
- bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
- continue;
- }
-
- /* From this point onward we are propagating into a
- real statement. Folding may (or may not) be possible,
- we may expose new operands, expose dead EH edges,
- etc. */
- /* NOTE tuples. In the tuples world, fold_stmt_inplace
- cannot fold a call that simplifies to a constant,
- because the GIMPLE_CALL must be replaced by a
- GIMPLE_ASSIGN, and there is no way to effect such a
- transformation in-place. We might want to consider
- using the more general fold_stmt here. */
- {
- gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
- fold_stmt_inplace (&gsi);
- }
-
- /* Sometimes propagation can expose new operands to the
- renamer. */
- update_stmt (use_stmt);
-
- /* Dump details. */
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Updated statement:");
- print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
- }
-
- /* If we replaced a variable index with a constant, then
- we would need to update the invariant flag for ADDR_EXPRs. */
- if (gimple_assign_single_p (use_stmt)
- && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
- recompute_tree_invariant_for_addr_expr
- (gimple_assign_rhs1 (use_stmt));
-
- /* If we cleaned up EH information from the statement,
- mark its containing block as needing EH cleanups. */
- if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
- {
- bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Flagged to clear EH edges.\n");
- }
-
- /* Propagation may expose new trivial copy/constant propagation
- opportunities. */
- if (gimple_assign_single_p (use_stmt)
- && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
- && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
- || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
- {
- 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 (gimple_code (use_stmt) == GIMPLE_COND
- || gimple_code (use_stmt) == GIMPLE_SWITCH
- || gimple_code (use_stmt) == GIMPLE_GOTO)
- {
- tree val;
-
- if (gimple_code (use_stmt) == GIMPLE_COND)
- val = fold_binary_loc (gimple_location (use_stmt),
- gimple_cond_code (use_stmt),
- boolean_type_node,
- gimple_cond_lhs (use_stmt),
- gimple_cond_rhs (use_stmt));
- else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
- val = gimple_switch_index (use_stmt);
- else
- val = gimple_goto_dest (use_stmt);
-
- if (val && is_gimple_min_invariant (val))
- {
- basic_block bb = gimple_bb (use_stmt);
- edge te = find_taken_edge (bb, val);
- edge_iterator ei;
- edge e;
- gimple_stmt_iterator gsi, psi;
-
- /* Remove all outgoing edges except TE. */
- for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
- {
- if (e != te)
- {
- /* Mark all the PHI nodes at the destination of
- the unexecutable edge as interesting. */
- for (psi = gsi_start_phis (e->dest);
- !gsi_end_p (psi);
- gsi_next (&psi))
- {
- gimple phi = gsi_stmt (psi);
-
- tree result = gimple_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 = true;
- }
- else
- ei_next (&ei);
- }
-
- gsi = gsi_last_bb (gimple_bb (use_stmt));
- gsi_remove (&gsi, 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;
- }
- }
- }
-
- /* Ensure there is nothing else to do. */
- gcc_assert (!all || has_zero_uses (lhs));
-
- /* If we were able to propagate away all uses of LHS, then
- we can remove STMT. */
- if (all)
- remove_stmt_or_phi (stmt);
- }
-}
-
-/* STMT is either a PHI node (potentially 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 STMT. */
-
-static void
-eliminate_const_or_copy (gimple stmt, bitmap interesting_names)
-{
- tree lhs = get_lhs_or_phi_result (stmt);
- 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 (stmt);
- return;
- }
-
- /* Get the RHS of the assignment or PHI node if the PHI is a
- degenerate. */
- rhs = get_rhs_or_phi_arg (stmt);
- if (!rhs)
- {
- bitmap_clear_bit (interesting_names, version);
- return;
- }
-
- if (!virtual_operand_p (lhs))
- propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names);
- else
- {
- gimple use_stmt;
- imm_use_iterator iter;
- use_operand_p use_p;
- /* For virtual operands we have to propagate into all uses as
- otherwise we will create overlapping life-ranges. */
- FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
- FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
- SET_USE (use_p, rhs);
- if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
- SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
- remove_stmt_or_phi (stmt);
- }
-
- /* Note that STMT 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)
-{
- gimple_stmt_iterator gsi;
- basic_block son;
-
- for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple phi = gsi_stmt (gsi);
-
- 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;
- bitmap interesting_names1;
-
- /* Bitmap of blocks which need EH information updated. We can not
- update it on-the-fly as doing so invalidates the dominator tree. */
- need_eh_cleanup = BITMAP_ALLOC (NULL);
-
- /* 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 trivial const/copy propagation
- opportunity.
-
- Experiments have show we generally get better compilation
- time behavior with bitmaps rather than sbitmaps. */
- interesting_names = BITMAP_ALLOC (NULL);
- interesting_names1 = BITMAP_ALLOC (NULL);
-
- calculate_dominance_info (CDI_DOMINATORS);
- cfg_altered = false;
-
- /* First phase. Eliminate degenerate PHIs via a dominator
- 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. */
- eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (cfun),
- interesting_names);
-
- /* Second phase. Eliminate second order degenerate 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 does not like its bitmap
- changed during the loop. Copy it to another bitmap and
- use that. */
- bitmap_copy (interesting_names1, interesting_names);
-
- EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 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);
- }
- }
-
- if (cfg_altered)
- {
- free_dominance_info (CDI_DOMINATORS);
- /* If we changed the CFG schedule loops for fixup by cfgcleanup. */
- if (current_loops)
- loops_state_set (LOOPS_NEED_FIXUP);
- }
-
- /* Propagation of const and copies may make some EH edges dead. Purge
- such edges from the CFG as needed. */
- if (!bitmap_empty_p (need_eh_cleanup))
- {
- gimple_purge_all_dead_eh_edges (need_eh_cleanup);
- BITMAP_FREE (need_eh_cleanup);
- }
-
- BITMAP_FREE (interesting_names);
- BITMAP_FREE (interesting_names1);
- return 0;
-}
-
-namespace {
-
-const pass_data pass_data_phi_only_cprop =
-{
- GIMPLE_PASS, /* type */
- "phicprop", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
- TV_TREE_PHI_CPROP, /* tv_id */
- ( PROP_cfg | PROP_ssa ), /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- ( TODO_cleanup_cfg | TODO_verify_ssa
- | TODO_verify_stmts
- | TODO_update_ssa ), /* todo_flags_finish */
-};
-
-class pass_phi_only_cprop : public gimple_opt_pass
-{
-public:
- pass_phi_only_cprop (gcc::context *ctxt)
- : gimple_opt_pass (pass_data_phi_only_cprop, ctxt)
- {}
-
- /* opt_pass methods: */
- opt_pass * clone () { return new pass_phi_only_cprop (m_ctxt); }
- bool gate () { return gate_dominator (); }
- unsigned int execute () { return eliminate_degenerate_phis (); }
-
-}; // class pass_phi_only_cprop
-
-} // anon namespace
-
-gimple_opt_pass *
-make_pass_phi_only_cprop (gcc::context *ctxt)
-{
- return new pass_phi_only_cprop (ctxt);
-}
diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c
index 840d7e7..71dea6f 100644
--- a/gcc/tree-ssa-propagate.c
+++ b/gcc/tree-ssa-propagate.c
@@ -1026,6 +1026,7 @@ replace_phi_args_in (gimple phi, ssa_prop_get_value_fn get_value)
bool
substitute_and_fold (ssa_prop_get_value_fn get_value_fn,
ssa_prop_fold_stmt_fn fold_fn,
+ ssa_prop_fold_notify_fn fold_notify_fn,
bool do_dce)
{
basic_block bb;
@@ -1194,6 +1195,9 @@ substitute_and_fold (ssa_prop_get_value_fn get_value_fn,
{
stmt = gsi_stmt (oldi);
+ if (fold_notify_fn)
+ (*fold_notify_fn) (stmt);
+
/* If we cleaned up EH information from the statement,
remove EH edges. */
if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h
index 2d8d876..d6f6eed 100644
--- a/gcc/tree-ssa-propagate.h
+++ b/gcc/tree-ssa-propagate.h
@@ -65,6 +65,7 @@ enum ssa_prop_result {
typedef enum ssa_prop_result (*ssa_prop_visit_stmt_fn) (gimple, edge *, tree *);
typedef enum ssa_prop_result (*ssa_prop_visit_phi_fn) (gimple);
typedef bool (*ssa_prop_fold_stmt_fn) (gimple_stmt_iterator *gsi);
+typedef void (*ssa_prop_fold_notify_fn) (gimple);
typedef tree (*ssa_prop_get_value_fn) (tree);
@@ -75,7 +76,7 @@ extern bool update_call_from_tree (gimple_stmt_iterator *, tree);
extern void ssa_propagate (ssa_prop_visit_stmt_fn, ssa_prop_visit_phi_fn);
extern bool stmt_makes_single_store (gimple);
extern bool substitute_and_fold (ssa_prop_get_value_fn, ssa_prop_fold_stmt_fn,
- bool);
+ ssa_prop_fold_notify_fn, bool);
extern bool may_propagate_copy (tree, tree);
extern bool may_propagate_copy_into_stmt (gimple, tree);
extern bool may_propagate_copy_into_asm (tree);
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index f6da192..6b3b692 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -9689,7 +9689,7 @@ vrp_finalize (void)
}
substitute_and_fold (op_with_constant_singleton_value_range,
- vrp_fold_stmt, false);
+ vrp_fold_stmt, NULL, false);
if (warn_array_bounds)
check_all_array_refs ();
^ permalink raw reply [flat|nested] 6+ messages in thread