On Thu, Dec 1, 2011 at 11:13 PM, William J. Schmidt
<[email protected]> 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 <[email protected]>
>
> 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)?
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);
>
>
>
