This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Fix PR middle-end/39976, 200.sixtrack degradation
On Fri, 2011-12-02 at 10:24 +0100, Richard Guenther wrote:
> On Thu, Dec 1, 2011 at 11:13 PM, William J. Schmidt
> <wschmidt@linux.vnet.ibm.com> wrote:
> > Greetings,
> >
> > Bug 39976 reported a degradation to 200.sixtrack wherein a hot
> > single-block loop is broken into two blocks. Investigation showed the
> > cause to be a redundant PHI statement in the block, which the
> > tree-outof-ssa logic doesn't handle well. Currently we don't have code
> > following the introduction of the redundant PHI that can clean it up.
> >
> > This patch modifies the dom pass to include redundant PHIs in the logic
> > that removes redundant computations. With the patch applied, the extra
> > block is no longer created and the 200.sixtrack degradation is removed.
> > This improves its performance by 7.3% on PowerPC64 32-bit and by 5.0% on
> > PowerPC64 64-bit.
> >
> > Bootstrapped and regtested on powerpc64-linux. OK for trunk?
> >
> > Thanks,
> > Bill
> >
> >
> > 2011-11-29 Bill Schmidt <wschmidt@linux.vnet.ibm.com>
> >
> > PR middle-end/39976
> > * tree-ssa-dom.c (enum expr_kind): Add EXPR_PHI.
> > (struct hashable_expr): Add struct phi field.
> > (initialize_hash_element): Handle phis.
> > (hashable_expr_equal_p): Likewise.
> > (iterative_hash_hashable_expr): Likewise.
> > (print_expr_hash_elt): Likewise.
> > (dom_opt_enter_block): Create equivalences from redundant phis.
> > (eliminate_redundant_computations): Handle redundant phis.
> >
> >
> > Index: gcc/tree-ssa-dom.c
> > ===================================================================
> > --- gcc/tree-ssa-dom.c (revision 181501)
> > +++ gcc/tree-ssa-dom.c (working copy)
> > @@ -52,7 +52,8 @@ enum expr_kind
> > EXPR_UNARY,
> > EXPR_BINARY,
> > EXPR_TERNARY,
> > - EXPR_CALL
> > + EXPR_CALL,
> > + EXPR_PHI
> > };
> >
> > struct hashable_expr
> > @@ -65,6 +66,7 @@ struct hashable_expr
> > struct { enum tree_code op; tree opnd0, opnd1; } binary;
> > struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary;
> > struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call;
> > + struct { size_t nargs; tree *args; } phi;
> > } ops;
> > };
> >
> > @@ -281,6 +283,19 @@ initialize_hash_element (gimple stmt, tree lhs,
> > expr->kind = EXPR_SINGLE;
> > expr->ops.single.rhs = gimple_goto_dest (stmt);
> > }
> > + else if (code == GIMPLE_PHI)
> > + {
> > + size_t nargs = gimple_phi_num_args (stmt);
> > + size_t i;
> > +
> > + expr->type = TREE_TYPE (gimple_phi_result (stmt));
> > + expr->kind = EXPR_PHI;
> > + expr->ops.phi.nargs = nargs;
> > + expr->ops.phi.args = (tree *) xcalloc (nargs, sizeof (tree));
> > +
> > + for (i = 0; i < nargs; i++)
> > + expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i);
> > + }
> > else
> > gcc_unreachable ();
> >
> > @@ -439,6 +454,21 @@ hashable_expr_equal_p (const struct hashable_expr
> > return true;
> > }
> >
> > + case EXPR_PHI:
> > + {
> > + size_t i;
> > +
> > + if (expr0->ops.phi.nargs != expr1->ops.phi.nargs)
> > + return false;
> > +
> > + for (i = 0; i < expr0->ops.phi.nargs; i++)
> > + if (! operand_equal_p (expr0->ops.phi.args[i],
> > + expr1->ops.phi.args[i], 0))
> > + return false;
> > +
> > + return true;
> > + }
> > +
> > default:
> > gcc_unreachable ();
> > }
> > @@ -516,6 +546,15 @@ iterative_hash_hashable_expr (const struct hashabl
> > }
> > break;
> >
> > + case EXPR_PHI:
> > + {
> > + size_t i;
> > +
> > + for (i = 0; i < expr->ops.phi.nargs; i++)
> > + val = iterative_hash_expr (expr->ops.phi.args[i], val);
> > + }
> > + break;
> > +
> > default:
> > gcc_unreachable ();
> > }
> > @@ -588,6 +627,22 @@ print_expr_hash_elt (FILE * stream, const struct e
> > fprintf (stream, ")");
> > }
> > break;
> > +
> > + case EXPR_PHI:
> > + {
> > + size_t i;
> > + size_t nargs = element->expr.ops.phi.nargs;
> > +
> > + fprintf (stream, "PHI <");
> > + for (i = 0; i < nargs; i++)
> > + {
> > + print_generic_expr (stream, element->expr.ops.phi.args[i], 0);
> > + if (i + 1 < nargs)
> > + fprintf (stream, ", ");
> > + }
> > + fprintf (stream, ">");
> > + }
> > + break;
> > }
> > fprintf (stream, "\n");
> >
> > @@ -1688,6 +1743,10 @@ dom_opt_enter_block (struct dom_walk_data *walk_da
> > /* PHI nodes can create equivalences too. */
> > record_equivalences_from_phis (bb);
> >
> > + /* Create equivalences from redundant PHIs. */
> > + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> > + eliminate_redundant_computations (&gsi);
> > +
> > for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> > optimize_stmt (bb, gsi);
> >
> > @@ -1818,13 +1877,27 @@ eliminate_redundant_computations (gimple_stmt_iter
> > {
> > tree expr_type;
> > tree cached_lhs;
> > + tree def;
> > bool insert = true;
> > bool assigns_var_p = false;
> > + size_t i;
> >
> > gimple stmt = gsi_stmt (*gsi);
> >
> > - tree def = gimple_get_lhs (stmt);
> > + /* If this is a PHI, we only want to consider it if all of its
> > + arguments are SSA names (which are known to be defined in a
> > + single place). This avoids errors when dealing with if-temps,
> > + for example. */
> > + if (gimple_code (stmt) == GIMPLE_PHI)
> > + for (i = 0; i < gimple_phi_num_args (stmt); i++)
> > + if (TREE_CODE (gimple_phi_arg_def (stmt, i)) != SSA_NAME)
> > + return;
>
> Can you elaborate on this? Why are for example constants not ok
> (which are the only things besides SSA names that should occur
> here)?
I ran into a bootstrap problem in gengtype.c without this that took me a
while to track down. Control flow was like this:
10
/ |
11 |
\ |
12
/ |
13 |
\ |
14
Blocks 12 and 14 contained iftmp PHI statements of constants that looked
identical, but the constants were "defined" in different blocks. Blocks
11 and 13 were empty.
In block 12:
iftmp.132_1 = PHI<", "(10), ""(11)>;
In block 14:
iftmp.133_7 = PHI<", "(12), ""(13)>;
These kinds of PHIs are redundant when in the same block with the same
predecessors, but aren't redundant in this situation (they effectively
depend upon comparisons in blocks 10 and 12). The constants don't have
the "defined-once" property. Without the extra check, the last
statement became a copy "iftmp.133_7 = iftmp.132_1", which was
incorrect.
The alternative would be to add some extra logic to avoid the copy
replacement when constants are involved and the PHIs aren't in the same
block, but I wasn't sure that was worth messing with the rest of the
machinery. Thoughts?
Thanks,
Bill
>
> Thanks,
> Richard.
>
> >
> > + if (gimple_code (stmt) == GIMPLE_PHI)
> > + def = gimple_phi_result (stmt);
> > + else
> > + def = gimple_get_lhs (stmt);
> > +
> > /* Certain expressions on the RHS can be optimized away, but can not
> > themselves be entered into the hash tables. */
> > if (! def
> > @@ -1857,6 +1930,16 @@ eliminate_redundant_computations (gimple_stmt_iter
> > }
> > else if (gimple_code (stmt) == GIMPLE_SWITCH)
> > expr_type = TREE_TYPE (gimple_switch_index (stmt));
> > + else if (gimple_code (stmt) == GIMPLE_PHI)
> > + /* We can't propagate into a phi, so the logic below doesn't apply.
> > + Instead record an equivalence between the cached LHS and the
> > + PHI result of this statement. This should be sufficient to
> > + kill the redundant phi. */
> > + {
> > + if (def && cached_lhs)
> > + record_const_or_copy (def, cached_lhs);
> > + return;
> > + }
> > else
> > gcc_unreachable ();
> >
> > @@ -2299,8 +2382,11 @@ lookup_avail_expr (gimple stmt, bool insert)
> > tree temp;
> > struct expr_hash_elt element;
> >
> > - /* Get LHS of assignment or call, else NULL_TREE. */
> > - lhs = gimple_get_lhs (stmt);
> > + /* Get LHS of phi, assignment, or call; else NULL_TREE. */
> > + if (gimple_code (stmt) == GIMPLE_PHI)
> > + lhs = gimple_phi_result (stmt);
> > + else
> > + lhs = gimple_get_lhs (stmt);
> >
> > initialize_hash_element (stmt, lhs, &element);
> >
> >
> >
>