On Thu, Dec 1, 2011 at 11:13 PM, William J. Schmidt <wschm...@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 <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;
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); > > >