| Message ID | 1322845466.2548.23.camel@gnopaine |
|---|---|
| State | New |
| Headers | show |
Hi, On Fri, 2 Dec 2011, William J. Schmidt wrote: > It seems like a fair amount of rip-up to avoid keeping the PHI state > around between blocks, so I just check to ensure the PHI definitions > occur in the same block before recording their equivalence. Then you should at least mix the BB number into the hash value (and possibly also check it already in hashable_expr_equal_p) in order to reduce number of collissions. But I wonder why it's not enough to just do a push/pop sequence on avail_exprs_stack around your new PHI processing in dom_opt_enter_block, ala + VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); /* Create equivalences from redundant PHIs. */ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) eliminate_redundant_computations (&gsi); + remove_local_expressions_from_table (); on top of your current version. That ought to remove the added PHI expressions (and only them) from the hash table but retain the information of equality in the const_or_copies_stack. Checking the BB wouldn't be required then. Ciao, Michael.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 12/02/11 10:40, Michael Matz wrote: > Hi, > > On Fri, 2 Dec 2011, William J. Schmidt wrote: > >> It seems like a fair amount of rip-up to avoid keeping the PHI >> state around between blocks, so I just check to ensure the PHI >> definitions occur in the same block before recording their >> equivalence. > > Then you should at least mix the BB number into the hash value (and > possibly also check it already in hashable_expr_equal_p) in order > to reduce number of collissions. > > But I wonder why it's not enough to just do a push/pop sequence on > avail_exprs_stack around your new PHI processing in > dom_opt_enter_block, ala > > + VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); > /* Create equivalences from redundant PHIs. */ for (gsi = > gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > eliminate_redundant_computations (&gsi); + > remove_local_expressions_from_table (); > > on top of your current version. That ought to remove the added PHI > expressions (and only them) from the hash table but retain the > information of equality in the const_or_copies_stack. Checking the > BB wouldn't be required then. Sorry, I haven't been following this thread and there isn't much discussion about what problem we're trying to solve using DOM within the PR. I see a mention of creating equivalences for redundant PHIs? Are we just trying to determine that two PHIs are going to result in the same value? jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJO2RB6AAoJEBRtltQi2kC7niIIAJDgImG8IWhtIDjF7t7blUNj uR8KCppurbvTkHgfuCSrn4hLRdRa14vZrY/FvP7pCaRmQ5KPBghu1IumXujVvb2i bLtwZBggjox9mVnUjv5CizURAwJcmvPhJE5axTpEACrafzI+AuADNW8qQwO2MQmF Ay3EXEPh27DbQi4E7IiytWQpuBsmFprh6Xu7nzW7YaK8zOGuGOEVdK5kDrZRPhLk etq2AY4OISwClyXZHGhPqCsC4haxo80F8qzRVJ2c2EbxEMTu45CNm4fRNutR/pA4 Ly/d0WKs1YF4yTjMSEL6w5VTIFQNk1RyDAyh1OA/M01UAMWP8BHdr9tw01s4Bws= =4X0z -----END PGP SIGNATURE-----
On Fri, 2011-12-02 at 10:52 -0700, Jeff Law wrote: > On 12/02/11 10:40, Michael Matz wrote: > > Hi, > > > > On Fri, 2 Dec 2011, William J. Schmidt wrote: > > > >> It seems like a fair amount of rip-up to avoid keeping the PHI > >> state around between blocks, so I just check to ensure the PHI > >> definitions occur in the same block before recording their > >> equivalence. > > > > Then you should at least mix the BB number into the hash value (and > > possibly also check it already in hashable_expr_equal_p) in order > > to reduce number of collissions. > > > > But I wonder why it's not enough to just do a push/pop sequence on > > avail_exprs_stack around your new PHI processing in > > dom_opt_enter_block, ala > > > > + VEC_safe_push (expr_hash_elt_t, heap, avail_exprs_stack, NULL); > > /* Create equivalences from redundant PHIs. */ for (gsi = > > gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > > eliminate_redundant_computations (&gsi); + > > remove_local_expressions_from_table (); > > > > on top of your current version. That ought to remove the added PHI > > expressions (and only them) from the hash table but retain the > > information of equality in the const_or_copies_stack. Checking the > > BB wouldn't be required then. > Sorry, I haven't been following this thread and there isn't much > discussion about what problem we're trying to solve using DOM within > the PR. > > I see a mention of creating equivalences for redundant PHIs? Are we > just trying to determine that two PHIs are going to result in the same > value? Jeff, see comment #37 in http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39976. The issue is that we have two PHIs in the same block as follows: # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> The coalescing algorithm in tree-outof-ssa doesn't handle this well and ends up splitting the back arc of a simple loop as a result. I'm creating an equivalence between prephitmp.35_322 and prephitmp.35_225 in this case so that one PHI goes dead and is removed. As pointed out in the comments, this needs to be restricted to occur only in the same block since the PHIs aren't necessarily equivalent otherwise. Michael, you're quite right, I think using the extra marker and stack pop should work quite well and would be more elegant and efficient. I'll try it out. I was initially thinking the PHI copies and existing copies would be intermingled, but that's not the case. Thanks, Bill > > jeff
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 12/02/11 11:10, William J. Schmidt wrote: > >> >> I see a mention of creating equivalences for redundant PHIs? Are >> we just trying to determine that two PHIs are going to result in >> the same value? > > Jeff, see comment #37 in > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39976. The issue is > that we have two PHIs in the same block as follows: > > # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> > # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> OK. Make sure you has the phi argument & its edge... Simlarly the equality comparison needs to check args & edges. Or s/edge/edge->src/ if that's easier. > > The coalescing algorithm in tree-outof-ssa doesn't handle this well > and ends up splitting the back arc of a simple loop as a result. > I'm creating an equivalence between prephitmp.35_322 and > prephitmp.35_225 in this case so that one PHI goes dead and is > removed. Right. I don't think I bothered with this because I didn't see it happening and the comparison of the PHIs with each other gets potentially expensive. As pointed out in > the comments, this needs to be restricted to occur only in the > same block since the PHIs aren't necessarily equivalent otherwise. I must be missing something -- why is the equivalence only valid in the same block? Conceptually this situation isn't any different replacing the second PHI with a copy blah_225 = blah_322 And the equivalence is valid for the entire dominator subtree. If you really need to create a temporary equiv, pushing the marker, create the equiv and pop the marker when equiv dies is simple and easy. Jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJO2RjmAAoJEBRtltQi2kC7I7YH/RTVZF6jzBpyg+68kMTZuHDH hETg03jnqhSXhWOzBoALZwtR9iCJ/UehCCcnjQ3eV7o1AqsImLMnap+VrS6lYfI3 hYQXtdb2F770H70yY/fgEX/VDAdGlyduXfMqHl4mLw7Apz3mpvyBucqHqECHJ+xj AtZf3duGXp3Fpvhm3PZ7wQa+Pl0qnJU3VxqU6xkGWn9A8et8U1IdYs/wnHPR/HPY KP7oY3JWxwR6kpzNkFJM1OZ+Nn9XWGgScAp1uBXJhK2RLgIuxaLiM5wl6VAJR1Fs EuMBnQbHELA1ugtqC26UsDCTkjDpLGgs02ID7ArySsVgmIYvXCVzEi0cdJA42V4= =NKrB -----END PGP SIGNATURE-----
On Fri, 2011-12-02 at 11:28 -0700, Jeff Law wrote: > On 12/02/11 11:10, William J. Schmidt wrote: > > > >> > >> I see a mention of creating equivalences for redundant PHIs? Are > >> we just trying to determine that two PHIs are going to result in > >> the same value? > > > > Jeff, see comment #37 in > > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39976. The issue is > > that we have two PHIs in the same block as follows: > > > > # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> > > # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> > OK. Make sure you has the phi argument & its edge... Simlarly the > equality comparison needs to check args & edges. Or s/edge/edge->src/ > if that's easier. > OK, this is what I was missing. Including edge->src->index in the hash and equality test to get the actual origin of the arguments should allow the PHIs to match when they're truly equivalent. Thanks! > > > > The coalescing algorithm in tree-outof-ssa doesn't handle this well > > and ends up splitting the back arc of a simple loop as a result. > > I'm creating an equivalence between prephitmp.35_322 and > > prephitmp.35_225 in this case so that one PHI goes dead and is > > removed. > Right. I don't think I bothered with this because I didn't see it > happening and the comparison of the PHIs with each other gets > potentially expensive. > > As pointed out in > > the comments, this needs to be restricted to occur only in the > > same block since the PHIs aren't necessarily equivalent otherwise. > I must be missing something -- why is the equivalence only valid in > the same block? > > Conceptually this situation isn't any different replacing the second > PHI with a copy > blah_225 = blah_322 > > And the equivalence is valid for the entire dominator subtree. Yes, once the origin of the PHI arguments is correctly taken into account, then equivalent PHIs can be eliminated within the subtree. > > If you really need to create a temporary equiv, pushing the marker, > create the equiv and pop the marker when equiv dies is simple and easy. > > Jeff Much obliged, Bill
On Fri, 2011-12-02 at 13:08 -0600, William J. Schmidt wrote: > > On Fri, 2011-12-02 at 11:28 -0700, Jeff Law wrote: > > On 12/02/11 11:10, William J. Schmidt wrote: > > > > > >> > > >> I see a mention of creating equivalences for redundant PHIs? Are > > >> we just trying to determine that two PHIs are going to result in > > >> the same value? > > > > > > Jeff, see comment #37 in > > > http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39976. The issue is > > > that we have two PHIs in the same block as follows: > > > > > > # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> > > > # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)> > > OK. Make sure you has the phi argument & its edge... Simlarly the > > equality comparison needs to check args & edges. Or s/edge/edge->src/ > > if that's easier. > > > > OK, this is what I was missing. Including edge->src->index in the hash > and equality test to get the actual origin of the arguments should allow > the PHIs to match when they're truly equivalent. Thanks! Erm, wait. How are PHIs in different blocks going to have the same incoming edges? (I was thinking of control dependence edges, but these are just regular control flow incoming edges, right?) So this really isn't going to help. > > > > > > > The coalescing algorithm in tree-outof-ssa doesn't handle this well > > > and ends up splitting the back arc of a simple loop as a result. > > > I'm creating an equivalence between prephitmp.35_322 and > > > prephitmp.35_225 in this case so that one PHI goes dead and is > > > removed. > > Right. I don't think I bothered with this because I didn't see it > > happening and the comparison of the PHIs with each other gets > > potentially expensive. > > > > As pointed out in > > > the comments, this needs to be restricted to occur only in the > > > same block since the PHIs aren't necessarily equivalent otherwise. > > I must be missing something -- why is the equivalence only valid in > > the same block? > > > > Conceptually this situation isn't any different replacing the second > > PHI with a copy > > blah_225 = blah_322 > > > > And the equivalence is valid for the entire dominator subtree. If you go back a couple of posts in this thread, I have an example of control flow where two control-equivalent blocks contain PHIs with identical constant arguments. But the constants are "defined" in different blocks with different control dependence, so while the constants are equivalent, the PHIs aren't. I originally replaced this with a copy as suggested, which broke things. > > Yes, once the origin of the PHI arguments is correctly taken into > account, then equivalent PHIs can be eliminated within the subtree. ...but none will be found... > > > > > If you really need to create a temporary equiv, pushing the marker, > > create the equiv and pop the marker when equiv dies is simple and easy. > > Yes, this still seems like the most promising thing to do. > > Jeff > > Much obliged, > Bill
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 12/02/11 12:27, William J. Schmidt wrote: > > Erm, wait. How are PHIs in different blocks going to have the > same incoming edges? (I was thinking of control dependence edges, > but these are just regular control flow incoming edges, right?) So > this really isn't going to help. They're not. But if we find an equivalence between phi_1 and phi_2, then we can replace every reference to phi_2 with phi_1. This is safe because any reference to phi_2 must be dominated by the assignment to phi_2 which is in the same block as phi_1. So while continuing to have the phis in the available expression table is not useful beyond the current block, the equivalency created when a redundant PHI is encountered is useful to keep. I may have not made the distinction clearly in prior messages. If that's what your patch does, then you're golden. Jeff -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJO2TktAAoJEBRtltQi2kC7hUsH/iWomNPVNnGw00FhLVBuiIVC c/Tsirdu256H07v1yZBemoh65EEOiqy6gHbKV2ZgL8MADJYm4i17Ii/0CEJyXHt2 YpplJmVY905WKqs2KN/qWHXAo7YFQwAj2MRWSksi2VMlq0YBHL+OA0qVlPLcNRUK 3e92nyERJAHgNlQqBLzGpeMLw8ozs8ognVZj9L/fbRWf4Jgnh5v5oPu50n9pWshO ipq+J5Qbovli9c8lHq6etFZ3EVCCxahnZ4FF1rxI3mVOKnL90xFPprBB1jL6qcqx 8O79yTLK6M7u3CTmnD8KoociAMWOhoe34o8PQIYEtJC5Pops1jKViEIbsOQg9s0= =NXbN -----END PGP SIGNATURE-----
On Fri, 2011-12-02 at 13:46 -0700, Jeff Law wrote: > On 12/02/11 12:27, William J. Schmidt wrote: > > > > > Erm, wait. How are PHIs in different blocks going to have the > > same incoming edges? (I was thinking of control dependence edges, > > but these are just regular control flow incoming edges, right?) So > > this really isn't going to help. > They're not. But if we find an equivalence between phi_1 and phi_2, > then we can replace every reference to phi_2 with phi_1. This is safe > because any reference to phi_2 must be dominated by the assignment to > phi_2 which is in the same block as phi_1. > > So while continuing to have the phis in the available expression table > is not useful beyond the current block, the equivalency created when a > redundant PHI is encountered is useful to keep. > > I may have not made the distinction clearly in prior messages. If > that's what your patch does, then you're golden. Ah, yes. This is what I'm doing. Sorry for the confusion! And thanks for the clarification. Bill > > Jeff >
Hi, On Fri, 2 Dec 2011, Jeff Law wrote: > So while continuing to have the phis in the available expression table > is not useful beyond the current block, the equivalency created when a > redundant PHI is encountered is useful to keep. That's why I said to only clear the avail_exprs stack/vect not the const_or_copies one. Ciao, Michael.
Index: gcc/tree-ssa-dom.c =================================================================== --- gcc/tree-ssa-dom.c (revision 181928) +++ 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,12 +1877,16 @@ eliminate_redundant_computations (gimple_stmt_iter { tree expr_type; tree cached_lhs; + tree def; bool insert = true; bool assigns_var_p = false; gimple stmt = gsi_stmt (*gsi); - tree def = gimple_get_lhs (stmt); + 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. */ @@ -1857,6 +1920,21 @@ 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, provided they are in the same block. + This should be sufficient to kill the redundant phi. */ + { + if (def && cached_lhs && TREE_CODE (cached_lhs) == SSA_NAME) + { + basic_block def_bb = gimple_bb (stmt); + basic_block cached_bb = gimple_bb (SSA_NAME_DEF_STMT (cached_lhs)); + if (def_bb == cached_bb) + record_const_or_copy (def, cached_lhs); + } + return; + } else gcc_unreachable (); @@ -2299,8 +2377,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);