Ok, not really predicate aware, but this makes value-numbering
pessimistically handle non-executable edges. In the following
patch groundwork is laid and PHI value-numbering is adjusted
to take advantage of edges known to be not executable.
SCCVN is not well-suited to be control aware, but we still
can see if value-numbering allows us to mark edges as
not executable by looking at control statements. Value-numbering
of PHI nodes is one obvious consumer of such information
and it also gives a natural order to do that (pessimistic)
edge executability computation - dominator order.
Thus the following adds a pass over all control statements,
trying to simplify them after value-numbering their operands
(and all uses recursively, as SCCVN does).
With followup patches I will try to use this information to
reduce the amount of work done (also improving optimization,
of course). One other obvious candidate is the alias walker
which doesn't have to consider unreachable paths when
walking into virtual PHIs.
The patch will likely get some more cleanups (due to the hack
in set_ssa_val_to).
Comments still welcome.
Thanks,
Richard.
2014-05-08 Richard Biener <rguent...@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.
* gcc.dg/tree-ssa/ssa-fre-39.c: New testcase.
Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c.orig 2014-05-08 12:22:58.926026518 +0200
--- gcc/tree-ssa-sccvn.c 2014-05-08 13:42:50.646696614 +0200
*************** along with GCC; see the file COPYING3.
*** 51,56 ****
--- 51,58 ----
#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"
*************** set_ssa_val_to (tree from, tree to)
*** 2661,2666 ****
--- 2663,2687 ----
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)
*************** set_ssa_val_to (tree from, tree to)
*** 2680,2692 ****
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 ");
--- 2701,2706 ----
*************** visit_phi (gimple phi)
*** 3071,3077 ****
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. */
--- 3085,3090 ----
*************** visit_phi (gimple phi)
*** 3080,3106 ****
/* 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);
! 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. */
--- 3093,3122 ----
/* See if all non-TOP arguments have the same value. TOP is
equivalent to everything, so we can ignore it. */
! 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 all value numbered to the same value, the phi node has that
value. */
*************** set_hashtable_value_ids (void)
*** 4098,4103 ****
--- 4114,4218 ----
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. */
*************** set_hashtable_value_ids (void)
*** 4105,4110 ****
--- 4220,4226 ----
bool
run_scc_vn (vn_lookup_kind default_vn_walk_kind_)
{
+ basic_block bb;
size_t i;
tree param;
*************** run_scc_vn (vn_lookup_kind default_vn_wa
*** 4122,4127 ****
--- 4238,4263 ----
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);
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-39.c 2014-05-08 13:17:29.916801314
+0200
***************
*** 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" } } */
