diff options
author | Richard Biener <rguenther@suse.de> | 2014-05-16 08:05:50 +0000 |
---|---|---|
committer | Richard Biener <rguenth@gcc.gnu.org> | 2014-05-16 08:05:50 +0000 |
commit | a764d66099b476db7d59829da1b86fd4a701523f (patch) | |
tree | 6b4c7eeefda2e10dbce6363164cd1f14df8d78f7 /gcc | |
parent | a27c386001166cec7abc12d54e96413022bcc747 (diff) | |
download | gcc-a764d66099b476db7d59829da1b86fd4a701523f.zip gcc-a764d66099b476db7d59829da1b86fd4a701523f.tar.gz gcc-a764d66099b476db7d59829da1b86fd4a701523f.tar.bz2 |
tree-ssa-sccvn.c: Include tree-cfg.h and domwalk.h.
2014-05-16 Richard Biener <rguenther@suse.de>
* tree-ssa-sccvn.c: Include tree-cfg.h and domwalk.h.
(set_ssa_val_to): Handle unexpected sets to VN_TOP.
(visit_phi): Ignore edges marked as not executable.
(class cond_dom_walker): New.
(cond_dom_walker::before_dom_children): Value-number
control statements and mark successor edges as not
executable if possible.
(run_scc_vn): First walk all control statements in
dominator order, marking edges as not executable.
* tree-inline.c (copy_edges_for_bb): Be not confused
about random edge flags.
* gcc.dg/tree-ssa/ssa-fre-39.c: New testcase.
* gcc.dg/tree-ssa/ssa-fre-40.c: Likewise.
* gcc.dg/tree-ssa/ssa-pre-8.c: One more elimination.
* gcc.dg/tree-ssa/struct-aliasing-2.c: Scan cddce1 dump.
From-SVN: r210492
Diffstat (limited to 'gcc')
-rw-r--r-- | gcc/ChangeLog | 14 | ||||
-rw-r--r-- | gcc/testsuite/ChangeLog | 7 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c | 19 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-40.c | 16 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c | 4 | ||||
-rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c | 10 | ||||
-rw-r--r-- | gcc/tree-inline.c | 3 | ||||
-rw-r--r-- | gcc/tree-ssa-sccvn.c | 192 |
8 files changed, 230 insertions, 35 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 3df0bb4..cc0d973 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,5 +1,19 @@ 2014-05-16 Richard Biener <rguenther@suse.de> + * tree-ssa-sccvn.c: Include tree-cfg.h and domwalk.h. + (set_ssa_val_to): Handle unexpected sets to VN_TOP. + (visit_phi): Ignore edges marked as not executable. + (class cond_dom_walker): New. + (cond_dom_walker::before_dom_children): Value-number + control statements and mark successor edges as not + executable if possible. + (run_scc_vn): First walk all control statements in + dominator order, marking edges as not executable. + * tree-inline.c (copy_edges_for_bb): Be not confused + about random edge flags. + +2014-05-16 Richard Biener <rguenther@suse.de> + * tree-ssa-sccvn.c (visit_use): Also constant-fold calls. 2014-05-15 Peter Bergner <bergner@vnet.ibm.com> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 8c52f8c..66d0694 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,5 +1,12 @@ 2014-05-16 Richard Biener <rguenther@suse.de> + * gcc.dg/tree-ssa/ssa-fre-39.c: New testcase. + * gcc.dg/tree-ssa/ssa-fre-40.c: Likewise. + * gcc.dg/tree-ssa/ssa-pre-8.c: One more elimination. + * gcc.dg/tree-ssa/struct-aliasing-2.c: Scan cddce1 dump. + +2014-05-16 Richard Biener <rguenther@suse.de> + * gcc.dg/tree-ssa/ssa-fre-41.c: New testcase. 2014-05-15 Martin Jambor <mjambor@suse.cz> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c new file mode 100644 index 0000000..a30926c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c @@ -0,0 +1,19 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-fre1" } */ + +int foo (int i) +{ + int k = i + 1; + int j = i + 1; + if (k != j) + k = k + 1; + if (k != j) + k = k + 1; + k = k - i; + return k; +} + +/* We should be able to value-number the final assignment to k to 1. */ + +/* { dg-final { scan-tree-dump "k_. = 1;" "fre1" } } */ +/* { dg-final { cleanup-tree-dump "fre1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-40.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-40.c new file mode 100644 index 0000000..dd085a0 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-40.c @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-fre1" } */ + +int x; +int foo (int *p) +{ + x = 0; + if (x) + *p = 1; + return x; +} + +/* The final load of x should be replaced as well as the + aliasing store via *p is not reachable. */ + +/* { dg-final { scan-tree-dump-not "= x;" "fre1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c index f08ef7f..dab57fa 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-8.c @@ -17,7 +17,9 @@ foo (__SIZE_TYPE__ i, struct s *array) return 0; } /* We should eliminate two address calculations, and one load. */ +/* We also elimiate the PHI node feeding the return because the case + returning 1 is unreachable. */ /* We used to eliminate a cast but that was before POINTER_PLUS_EXPR was added. */ -/* { dg-final { scan-tree-dump-times "Eliminated: 3" 1 "fre1"} } */ +/* { dg-final { scan-tree-dump-times "Eliminated: 4" 1 "fre1"} } */ /* { dg-final { cleanup-tree-dump "fre1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c b/gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c index c348bdf..66a5442 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/struct-aliasing-2.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-fre1" } */ +/* { dg-options "-O2 -fdump-tree-cddce1" } */ struct S { unsigned f; }; @@ -12,8 +12,8 @@ foo ( struct S *p) } -/* There should only be one load of p->f because fwprop can change - *(int *)&p->f into just (int)p->f. */ -/* { dg-final { scan-tree-dump-times "= \[^\n\]*p_.\\\(D\\\)" 1 "fre1" } } */ -/* { dg-final { cleanup-tree-dump "fre1" } } */ +/* There should only be one load of p->f because FRE removes the redundancy + by realizing it can cast the result of either to the other. */ +/* { dg-final { scan-tree-dump-times "= \[^\n\]*p_.\\\(D\\\)" 1 "cddce1" } } */ +/* { dg-final { cleanup-tree-dump "cddce1" } } */ diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c index 9207e9f..bc2b271 100644 --- a/gcc/tree-inline.c +++ b/gcc/tree-inline.c @@ -1984,7 +1984,8 @@ copy_edges_for_bb (basic_block bb, gcov_type count_scale, basic_block ret_bb, flags = old_edge->flags; /* Return edges do get a FALLTHRU flag when the get inlined. */ - if (old_edge->dest->index == EXIT_BLOCK && !old_edge->flags + if (old_edge->dest->index == EXIT_BLOCK + && !(old_edge->flags & (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE|EDGE_FAKE)) && old_edge->dest->aux != EXIT_BLOCK_PTR_FOR_FN (cfun)) flags |= EDGE_FALLTHRU; new_edge = make_edge (new_bb, (basic_block) old_edge->dest->aux, flags); diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index 93a7e30..84c0d6e 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -51,6 +51,8 @@ along with GCC; see the file COPYING3. If not see #include "params.h" #include "tree-ssa-propagate.h" #include "tree-ssa-sccvn.h" +#include "tree-cfg.h" +#include "domwalk.h" /* This algorithm is based on the SCC algorithm presented by Keith Cooper and L. Taylor Simpson in "SCC-Based Value numbering" @@ -2661,6 +2663,25 @@ set_ssa_val_to (tree from, tree to) tree currval = SSA_VAL (from); HOST_WIDE_INT toff, coff; + /* The only thing we allow as value numbers are ssa_names + and invariants. So assert that here. We don't allow VN_TOP + as visiting a stmt should produce a value-number other than + that. + ??? Still VN_TOP can happen for unreachable code, so force + it to varying in that case. Not all code is prepared to + get VN_TOP on valueization. */ + if (to == VN_TOP) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Forcing value number to varying on " + "receiving VN_TOP\n"); + to = from; + } + + gcc_assert (to != NULL_TREE + && (TREE_CODE (to) == SSA_NAME + || is_gimple_min_invariant (to))); + if (from != to) { if (currval == from) @@ -2680,13 +2701,6 @@ set_ssa_val_to (tree from, tree to) to = from; } - /* The only thing we allow as value numbers are VN_TOP, ssa_names - and invariants. So assert that here. */ - gcc_assert (to != NULL_TREE - && (to == VN_TOP - || TREE_CODE (to) == SSA_NAME - || is_gimple_min_invariant (to))); - if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "Setting value number of "); @@ -3071,7 +3085,6 @@ visit_phi (gimple phi) tree result; tree sameval = VN_TOP; bool allsame = true; - unsigned i; /* TODO: We could check for this in init_sccvn, and replace this with a gcc_assert. */ @@ -3080,27 +3093,30 @@ visit_phi (gimple phi) /* See if all non-TOP arguments have the same value. TOP is equivalent to everything, so we can ignore it. */ - for (i = 0; i < gimple_phi_num_args (phi); i++) - { - tree def = PHI_ARG_DEF (phi, i); + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds) + if (e->flags & EDGE_EXECUTABLE) + { + tree def = PHI_ARG_DEF_FROM_EDGE (phi, e); - if (TREE_CODE (def) == SSA_NAME) - def = SSA_VAL (def); - if (def == VN_TOP) - continue; - if (sameval == VN_TOP) - { - sameval = def; - } - else - { - if (!expressions_equal_p (def, sameval)) - { - allsame = false; - break; - } - } - } + if (TREE_CODE (def) == SSA_NAME) + def = SSA_VAL (def); + if (def == VN_TOP) + continue; + if (sameval == VN_TOP) + { + sameval = def; + } + else + { + if (!expressions_equal_p (def, sameval)) + { + allsame = false; + break; + } + } + } /* If all value numbered to the same value, the phi node has that value. */ @@ -4140,6 +4156,105 @@ set_hashtable_value_ids (void) set_value_id_for_result (vr->result, &vr->value_id); } +class cond_dom_walker : public dom_walker +{ +public: + cond_dom_walker () : dom_walker (CDI_DOMINATORS), fail (false) {} + + virtual void before_dom_children (basic_block); + + bool fail; +}; + +void +cond_dom_walker::before_dom_children (basic_block bb) +{ + edge e; + edge_iterator ei; + + if (fail) + return; + + /* If any of the predecessor edges are still marked as possibly + executable consider this block reachable. */ + bool reachable = bb == ENTRY_BLOCK_PTR_FOR_FN (cfun); + FOR_EACH_EDGE (e, ei, bb->preds) + reachable |= (e->flags & EDGE_EXECUTABLE); + + /* If the block is not reachable all outgoing edges are not + executable. */ + if (!reachable) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Marking all outgoing edges of unreachable " + "BB %d as not executable\n", bb->index); + + FOR_EACH_EDGE (e, ei, bb->succs) + e->flags &= ~EDGE_EXECUTABLE; + return; + } + + gimple stmt = last_stmt (bb); + if (!stmt) + return; + + /* Value-number the last stmts SSA uses. */ + 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; + } + + /* ??? We can even handle stmts with outgoing EH or ABNORMAL edges + if value-numbering can prove they are not reachable. Handling + computed gotos is also possible. */ + tree val; + switch (gimple_code (stmt)) + { + case GIMPLE_COND: + { + tree lhs = gimple_cond_lhs (stmt); + tree rhs = gimple_cond_rhs (stmt); + /* Work hard in computing the condition and take into account + the valueization of the defining stmt. */ + if (TREE_CODE (lhs) == SSA_NAME) + lhs = vn_get_expr_for (lhs); + if (TREE_CODE (rhs) == SSA_NAME) + rhs = vn_get_expr_for (rhs); + val = fold_binary (gimple_cond_code (stmt), + boolean_type_node, lhs, rhs); + break; + } + case GIMPLE_SWITCH: + val = gimple_switch_index (stmt); + break; + case GIMPLE_GOTO: + val = gimple_goto_dest (stmt); + break; + default: + val = NULL_TREE; + break; + } + if (!val) + return; + + edge taken = find_taken_edge (bb, vn_valueize (val)); + if (!taken) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Marking all edges out of BB %d but (%d -> %d) as " + "not executable\n", bb->index, bb->index, taken->dest->index); + + FOR_EACH_EDGE (e, ei, bb->succs) + if (e != taken) + e->flags &= ~EDGE_EXECUTABLE; +} + /* Do SCCVN. Returns true if it finished, false if we bailed out due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies how we use the alias oracle walking during the VN process. */ @@ -4147,6 +4262,7 @@ set_hashtable_value_ids (void) bool run_scc_vn (vn_lookup_kind default_vn_walk_kind_) { + basic_block bb; size_t i; tree param; @@ -4164,6 +4280,26 @@ run_scc_vn (vn_lookup_kind default_vn_walk_kind_) VN_INFO (def)->valnum = def; } + /* Mark all edges as possibly executable. */ + FOR_ALL_BB_FN (bb, cfun) + { + edge_iterator ei; + edge e; + FOR_EACH_EDGE (e, ei, bb->succs) + 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; + walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + if (walker.fail) + { + free_scc_vn (); + return false; + } + + /* Value-number remaining SSA names. */ for (i = 1; i < num_ssa_names; ++i) { tree name = ssa_name (i); |