From d27139850b789dbfc7c9c5604432c5d16114528d Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Wed, 12 Aug 2015 07:34:07 +0000 Subject: [PATCH] tree-ssa-pre.c (eliminate_dom_walker::before_dom_children): Eliminate edges marked as not executable by SCCVN. 2015-08-12 Richard Biener * tree-ssa-pre.c (eliminate_dom_walker::before_dom_children): Eliminate edges marked as not executable by SCCVN. * tree-ssa-sccvn.c: Include gimple-iterator.h. (cond_dom_walker): Rename to sccvn_dom_walker. (sccvn_dom_walker::before_dom_children): Value-number defs of all stmts. (run_scc_vn): Remove loop value-numbering all SSA names. Drop not visited SSA names to varying. * gcc.dg/tree-ssa/ssa-fre-43.c: Adjust. From-SVN: r226801 --- gcc/ChangeLog | 11 ++++ gcc/testsuite/ChangeLog | 4 ++ gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-43.c | 6 +- gcc/tree-ssa-pre.c | 26 +++++++- gcc/tree-ssa-sccvn.c | 74 +++++++++++++--------- 5 files changed, 87 insertions(+), 34 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 063513ba0e9..206dc3aa44d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2015-08-12 Richard Biener + + * tree-ssa-pre.c (eliminate_dom_walker::before_dom_children): + Eliminate edges marked as not executable by SCCVN. + * tree-ssa-sccvn.c: Include gimple-iterator.h. + (cond_dom_walker): Rename to sccvn_dom_walker. + (sccvn_dom_walker::before_dom_children): Value-number defs + of all stmts. + (run_scc_vn): Remove loop value-numbering all SSA names. + Drop not visited SSA names to varying. + 2015-08-11 Trevor Saunders * compare-elim.c, dce.c, dse.c, gimple-ssa-isolate-paths.c, diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 8fa89f2fe77..7bb63a5f4ac 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2015-08-12 Richard Biener + + * gcc.dg/tree-ssa/ssa-fre-43.c: Adjust. + 2015-08-12 Tom de Vries PR testsuite/67175 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-43.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-43.c index af6adbda43e..1a837666c25 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-43.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-43.c @@ -21,8 +21,8 @@ L10: goto L10; } -/* We should remove 15 dead loads, fully propagating their replacements - with exactly 4 loads and 4 stores from/to E remaining. */ +/* We should remove 15 dead loads and some related stmts, fully propagating + their replacements with exactly 4 loads and 4 stores from/to E remaining. */ -/* { dg-final { scan-tree-dump-times "Removing dead stmt" 15 "fre1" } } */ +/* { dg-final { scan-tree-dump-times "Removing dead stmt" 19 "fre1" } } */ /* { dg-final { scan-tree-dump-not "Not changing value number" "fre1" } } */ diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 041cb78dc49..697958def0c 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -4291,7 +4291,31 @@ eliminate_dom_walker::before_dom_children (basic_block b) el_to_remove.safe_push (stmt); continue; } - } + } + + /* If this is a control statement value numbering left edges + unexecuted on force the condition in a way consistent with + that. */ + if (gcond *cond = dyn_cast (stmt)) + { + if ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE) + ^ (EDGE_SUCC (b, 1)->flags & EDGE_EXECUTABLE)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Removing unexecutable edge from "); + print_gimple_stmt (dump_file, stmt, 0, 0); + } + if (((EDGE_SUCC (b, 0)->flags & EDGE_TRUE_VALUE) != 0) + == ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE) != 0)) + gimple_cond_make_true (cond); + else + gimple_cond_make_false (cond); + update_stmt (cond); + el_todo |= TODO_cleanup_cfg; + continue; + } + } bool can_make_abnormal_goto = stmt_can_make_abnormal_goto (stmt); bool was_noreturn = (is_gimple_call (stmt) diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index ab4b1100b8c..eca0d44cdaf 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -57,6 +57,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-cfg.h" #include "domwalk.h" #include "cgraph.h" +#include "gimple-iterator.h" /* This algorithm is based on the SCC algorithm presented by Keith Cooper and L. Taylor Simpson in "SCC-Based Value numbering" @@ -4277,18 +4278,20 @@ set_hashtable_value_ids (void) set_value_id_for_result (vr->result, &vr->value_id); } -class cond_dom_walker : public dom_walker +class sccvn_dom_walker : public dom_walker { public: - cond_dom_walker () : dom_walker (CDI_DOMINATORS), fail (false) {} + sccvn_dom_walker () : dom_walker (CDI_DOMINATORS), fail (false) {} virtual void before_dom_children (basic_block); bool fail; }; +/* Value number all statements in BB. */ + void -cond_dom_walker::before_dom_children (basic_block bb) +sccvn_dom_walker::before_dom_children (basic_block bb) { edge e; edge_iterator ei; @@ -4317,6 +4320,34 @@ cond_dom_walker::before_dom_children (basic_block bb) return; } + /* Value-number all defs in the basic-block. */ + for (gphi_iterator gsi = gsi_start_phis (bb); + !gsi_end_p (gsi); gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + tree res = PHI_RESULT (phi); + if (!VN_INFO (res)->visited + && !DFS (res)) + { + fail = true; + return; + } + } + for (gimple_stmt_iterator gsi = gsi_start_bb (bb); + !gsi_end_p (gsi); gsi_next (&gsi)) + { + ssa_op_iter i; + tree op; + FOR_EACH_SSA_TREE_OPERAND (op, gsi_stmt (gsi), i, SSA_OP_ALL_DEFS) + if (!VN_INFO (op)->visited + && !DFS (op)) + { + fail = true; + return; + } + } + + /* Finally look at the last stmt. */ gimple stmt = last_stmt (bb); if (!stmt) return; @@ -4329,8 +4360,7 @@ cond_dom_walker::before_dom_children (basic_block bb) if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, "Value-numbering operands of stmt ending BB %d: ", - bb->index); + fprintf (dump_file, "Visiting stmt ending BB %d: ", bb->index); print_gimple_stmt (dump_file, stmt, 0, 0); } @@ -4338,12 +4368,8 @@ cond_dom_walker::before_dom_children (basic_block bb) ssa_op_iter i; tree op; FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE) - if (VN_INFO (op)->visited == false - && !DFS (op)) - { - fail = true; - return; - } + gcc_assert (VN_INFO (op)->visited + || SSA_NAME_IS_DEFAULT_DEF (op)); /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges if value-numbering can prove they are not reachable. Handling @@ -4427,9 +4453,9 @@ run_scc_vn (vn_lookup_kind default_vn_walk_kind_) e->flags |= EDGE_EXECUTABLE; } - /* Walk all blocks in dominator order, value-numbering the last stmts - SSA uses and decide whether outgoing edges are not executable. */ - cond_dom_walker walker; + /* Walk all blocks in dominator order, value-numbering stmts + SSA defs and decide whether outgoing edges are not executable. */ + sccvn_dom_walker walker; walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); if (walker.fail) { @@ -4437,22 +4463,8 @@ run_scc_vn (vn_lookup_kind default_vn_walk_kind_) return false; } - /* Value-number remaining SSA names. */ - for (i = 1; i < num_ssa_names; ++i) - { - tree name = ssa_name (i); - if (name - && VN_INFO (name)->visited == false - && !has_zero_uses (name)) - if (!DFS (name)) - { - free_scc_vn (); - return false; - } - } - - /* Initialize the value ids. */ - + /* Initialize the value ids and prune out remaining VN_TOPs + from dead code. */ for (i = 1; i < num_ssa_names; ++i) { tree name = ssa_name (i); @@ -4460,6 +4472,8 @@ run_scc_vn (vn_lookup_kind default_vn_walk_kind_) if (!name) continue; info = VN_INFO (name); + if (!info->visited) + info->valnum = name; if (info->valnum == name || info->valnum == VN_TOP) info->value_id = get_next_value_id (); -- 2.30.2