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 <wschm...@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;
+ 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);
