From 9fe4f60adbda974b46b7fa5fd005adae973f6f80 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Thu, 13 Aug 2015 07:06:10 +0000 Subject: [PATCH] re PR tree-optimization/66502 (SCCVN can't handle PHIs optimistically optimally) 2015-08-13 Richard Biener PR tree-optimization/66502 PR tree-optimization/67167 * 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. From-SVN: r226850 --- gcc/ChangeLog | 12 +++++ gcc/testsuite/ChangeLog | 6 +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c | 21 ++++++++ gcc/tree-ssa-sccvn.c | 59 +++++++++++++--------- 4 files changed, 73 insertions(+), 25 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index ae73d58fb58..6b62396c7af 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2015-08-13 Richard Biener + + PR tree-optimization/66502 + PR tree-optimization/67167 + * 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. + 2015-08-13 Richard Biener * gimple.h (gcall::code_): New constant static member. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 1b49702fd74..79d408e4563 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2015-08-13 Richard Biener + + PR tree-optimization/66502 + PR tree-optimization/67167 + * gcc.dg/tree-ssa/ssa-fre-46.c: New testcase. + 2015-08-12 Paolo Carlini PR c++/53330 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c new file mode 100644 index 00000000000..d6e63518e9f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-46.c @@ -0,0 +1,21 @@ +/* { 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" } } */ diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index 003433ccbc7..73d1070df44 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -2663,17 +2663,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); @@ -2726,16 +2733,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; @@ -2759,15 +2768,18 @@ vn_phi_insert (gimple phi, tree result) { vn_phi_s **slot; vn_phi_t vp1 = current_info->phis_pool->allocate (); - unsigned i; vec 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)); @@ -3252,28 +3264,23 @@ visit_phi (gimple phi) if (def == VN_TOP) continue; if (sameval == VN_TOP) + sameval = def; + else if (!expressions_equal_p (def, sameval)) { - sameval = def; - } - else - { - if (!expressions_equal_p (def, sameval)) - { - allsame = false; - break; - } + allsame = false; + break; } } - /* 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. */ + /* First see if it is equivalent to a phi node in this block. We prefer + this as it allows IV elimination - see PRs 66502 and 67167. */ result = vn_phi_lookup (phi); if (result) changed = set_ssa_val_to (PHI_RESULT (phi), result); + /* Otherwise 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)); @@ -4163,6 +4170,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 (23); -- 2.30.2