The following patch fixes a preference that causes SCCVN to fail to
eliminate redundant IVs. It will prefer to try eliminating IVs to
eliminating degenerate PHIs (if the degenerate PHI has a backedge).
I failed to create a testcase for that - the one below is essentially
what the vectorizer can end up generating (bah). I believe it
will still work out in the end, just FRE itself won't remove the
PHI node in a single pass iteration but just value-number to
a degenerate PHI (a testcase would still be nice - I'm still trying).
Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.
Richard.
2015-06-10 Richard Biener <rguent...@suse.de>
* tree-ssa-sccvn.c (vn_phi_compute_hash): Do not include
backedge arguments.
(vn_phi_lookup): Adjust.
(vn_phi_insert): Likewise.
(visit_phi): Prefer to value-number to another PHI node
over value-numbering to a PHI argument.
(init_scc_vn): Mark DFS back edges.
* gcc.dg/tree-ssa/ssa-fre-46.c: New testcase.
Index: gcc/tree-ssa-sccvn.c
===================================================================
--- gcc/tree-ssa-sccvn.c (revision 224324)
+++ gcc/tree-ssa-sccvn.c (working copy)
@@ -2682,17 +2679,24 @@ static inline hashval_t
vn_phi_compute_hash (vn_phi_t vp1)
{
inchash::hash hstate (vp1->block->index);
- int i;
tree phi1op;
tree type;
+ edge e;
+ edge_iterator ei;
/* If all PHI arguments are constants we need to distinguish
the PHI node via its type. */
type = vp1->type;
hstate.merge_hash (vn_hash_type (type));
- FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
+ FOR_EACH_EDGE (e, ei, vp1->block->preds)
{
+ /* Don't hash backedge values they need to be handled as VN_TOP
+ for optimistic value-numbering. */
+ if (e->flags & EDGE_DFS_BACK)
+ continue;
+
+ phi1op = vp1->phiargs[e->dest_idx];
if (phi1op == VN_TOP)
continue;
inchash::add_expr (phi1op, hstate);
@@ -2745,16 +2749,18 @@ vn_phi_lookup (gimple phi)
{
vn_phi_s **slot;
struct vn_phi_s vp1;
- unsigned i;
+ edge e;
+ edge_iterator ei;
shared_lookup_phiargs.truncate (0);
+ shared_lookup_phiargs.safe_grow (gimple_phi_num_args (phi));
/* Canonicalize the SSA_NAME's to their value number. */
- for (i = 0; i < gimple_phi_num_args (phi); i++)
+ FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
{
- tree def = PHI_ARG_DEF (phi, i);
+ tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
- shared_lookup_phiargs.safe_push (def);
+ shared_lookup_phiargs[e->dest_idx] = def;
}
vp1.type = TREE_TYPE (gimple_phi_result (phi));
vp1.phiargs = shared_lookup_phiargs;
@@ -2778,15 +2784,18 @@ vn_phi_insert (gimple phi, tree result)
{
vn_phi_s **slot;
vn_phi_t vp1 = current_info->phis_pool->allocate ();
- unsigned i;
vec<tree> args = vNULL;
+ edge e;
+ edge_iterator ei;
+
+ args.safe_grow (gimple_phi_num_args (phi));
/* Canonicalize the SSA_NAME's to their value number. */
- for (i = 0; i < gimple_phi_num_args (phi); i++)
+ FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)
{
- tree def = PHI_ARG_DEF (phi, i);
+ tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
- args.safe_push (def);
+ args[e->dest_idx] = def;
}
vp1->value_id = VN_INFO (result)->value_id;
vp1->type = TREE_TYPE (gimple_phi_result (phi));
@@ -3284,15 +3293,14 @@ visit_phi (gimple phi)
}
}
- /* If all value numbered to the same value, the phi node has that
- value. */
- if (allsame)
- return set_ssa_val_to (PHI_RESULT (phi), sameval);
-
/* Otherwise, see if it is equivalent to a phi node in this block. */
result = vn_phi_lookup (phi);
if (result)
changed = set_ssa_val_to (PHI_RESULT (phi), result);
+ /* If all value numbered to the same value, the phi node has that
+ value. */
+ else if (allsame)
+ changed = set_ssa_val_to (PHI_RESULT (phi), sameval);
else
{
vn_phi_insert (phi, PHI_RESULT (phi));
@@ -4182,6 +4190,8 @@ init_scc_vn (void)
int *rpo_numbers_temp;
calculate_dominance_info (CDI_DOMINATORS);
+ mark_dfs_back_edges ();
+
sccstack.create (0);
constant_to_value_id = new hash_table<vn_constant_hasher> (23);
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c (working copy)
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-fre1-details" } */
+
+int x[1024];
+int foo (int a, int s, unsigned int k)
+{
+ int i = a, j = a;
+ int sum = 0;
+ do
+ {
+ sum += x[i];
+ sum += x[j];
+ i += s;
+ j += s;
+ }
+ while (k--);
+ return sum;
+}
+
+/* We want to remove the redundant induction variable and thus its PHI node.
*/
+
+/* { dg-final { scan-tree-dump "Removing dead stmt \[^\r\n\]*PHI" "fre1" } } */
