[PATCH] tree-optimization: Improve spaceship_replacement [PR94589]
Richard Biener
rguenther@suse.de
Thu May 20 11:48:06 GMT 2021
On Thu, 20 May 2021, Jakub Jelinek wrote:
> On Wed, May 19, 2021 at 01:30:31PM -0400, Jason Merrill via Gcc-patches wrote:
> > Here, when genericizing lexicographical_compare_three_way, we haven't yet
> > walked the operands, so (a == a) still sees ADDR_EXPR <a>, but this is after
> > we've changed the type of a to REFERENCE_TYPE. When we try to fold (a == a)
> > by constexpr evaluation, the constexpr code doesn't understand trying to
> > take the address of a reference, and we end up crashing.
> >
> > Fixed by avoiding constexpr evaluation in genericize_spaceship, by using
> > fold_build2 instead of build_new_op on scalar operands. Class operands
> > should have been expanded during parsing.
>
> Unfortunately this slightly changed the IL and spaceship_replacement no
> longer pattern matches it.
>
> Here are 3 improvements that make it match:
>
> 1) as mentioned in the comment above spaceship_replacement, for
> strong_ordering, we are pattern matching something like:
> x == y ? 0 : x < y ? -1 : 1;
> and for partial_ordering
> x == y ? 0 : x < y ? -1 : x > y ? 1 : 2;
> but given the == comparison done first and the other comparisons only
> if == was false, we actually don't care if the other comparisons
> are < vs. <= (or > vs. >=), provided the operands of the comparison
> are the same; we know == is false when doing those and < vs. <= or
> > vs. >= have the same behavior for NaNs too
> 2) when y is an integral constant, we should treat x < 5 equivalently
> to x <= 4 etc.
> 3) the code punted if cond2_phi_edge wasn't a EDGE_TRUE_VALUE edge, but
> as the new IL shows, that isn't really needed; given 1) that
> > and >= are equivalent in the code, any of swapping the comparison
> operands, changing L[TE]_EXPR to G[TE]_EXPR or vice versa or
> swapping the EDGE_TRUE_VALUE / EDGE_FALSE_VALUE bits on the edges
> reverses one of the two comparisons
>
> Ok for trunk if it passes bootstrap/regtest?
OK.
Richard.
> 2021-05-20 Jakub Jelinek <jakub@redhat.com>
>
> PR tree-optimization/94589
> * tree-ssa-phiopt.c (spaceship_replacement): For integral rhs1 and
> rhs2, treat x <= 4 equivalently to x < 5 etc. In cmp1 and cmp2 (if
> not the same as cmp3) treat <= the same as < and >= the same as >.
> Don't require that cond2_phi_edge is true edge, instead take
> false/true edges into account based on cmp1/cmp2 comparison kinds.
>
> --- gcc/tree-ssa-phiopt.c.jj 2021-05-18 10:08:43.858591341 +0200
> +++ gcc/tree-ssa-phiopt.c 2021-05-20 13:09:28.046448559 +0200
> @@ -1988,8 +1988,16 @@ spaceship_replacement (basic_block cond_
>
> gcond *cond1 = as_a <gcond *> (last_stmt (cond_bb));
> enum tree_code cmp1 = gimple_cond_code (cond1);
> - if (cmp1 != LT_EXPR && cmp1 != GT_EXPR)
> - return false;
> + switch (cmp1)
> + {
> + case LT_EXPR:
> + case LE_EXPR:
> + case GT_EXPR:
> + case GE_EXPR:
> + break;
> + default:
> + return false;
> + }
> tree lhs1 = gimple_cond_lhs (cond1);
> tree rhs1 = gimple_cond_rhs (cond1);
> /* The optimization may be unsafe due to NaNs. */
> @@ -2029,7 +2037,42 @@ spaceship_replacement (basic_block cond_
> if (lhs2 == lhs1)
> {
> if (!operand_equal_p (rhs2, rhs1, 0))
> - return false;
> + {
> + if ((cmp2 == EQ_EXPR || cmp2 == NE_EXPR)
> + && TREE_CODE (rhs1) == INTEGER_CST
> + && TREE_CODE (rhs2) == INTEGER_CST)
> + {
> + /* For integers, we can have cond2 x == 5
> + and cond1 x < 5, x <= 4, x <= 5, x < 6,
> + x > 5, x >= 6, x >= 5 or x > 4. */
> + if (tree_int_cst_lt (rhs1, rhs2))
> + {
> + if (wi::ne_p (wi::to_wide (rhs1) + 1, wi::to_wide (rhs2)))
> + return false;
> + if (cmp1 == LE_EXPR)
> + cmp1 = LT_EXPR;
> + else if (cmp1 == GT_EXPR)
> + cmp1 = GE_EXPR;
> + else
> + return false;
> + }
> + else
> + {
> + gcc_checking_assert (tree_int_cst_lt (rhs2, rhs1));
> + if (wi::ne_p (wi::to_wide (rhs2) + 1, wi::to_wide (rhs1)))
> + return false;
> + if (cmp1 == LT_EXPR)
> + cmp1 = LE_EXPR;
> + else if (cmp1 == GE_EXPR)
> + cmp1 = GT_EXPR;
> + else
> + return false;
> + }
> + rhs1 = rhs2;
> + }
> + else
> + return false;
> + }
> }
> else if (lhs2 == rhs1)
> {
> @@ -2061,20 +2104,30 @@ spaceship_replacement (basic_block cond_
> || absu_hwi (tree_to_shwi (arg0)) != 1
> || wi::to_widest (arg0) == wi::to_widest (arg1))
> return false;
> - if (cmp2 != LT_EXPR && cmp2 != GT_EXPR)
> - return false;
> + switch (cmp2)
> + {
> + case LT_EXPR:
> + case LE_EXPR:
> + case GT_EXPR:
> + case GE_EXPR:
> + break;
> + default:
> + return false;
> + }
> /* if (x < y) goto phi_bb; else fallthru;
> if (x > y) goto phi_bb; else fallthru;
> bbx:;
> phi_bb:;
> is ok, but if x and y are swapped in one of the comparisons,
> or the comparisons are the same and operands not swapped,
> - or second goto phi_bb is not the true edge, it is not. */
> + or the true and false edges are swapped, it is not. */
> if ((lhs2 == lhs1)
> - ^ (cmp2 == cmp1)
> - ^ ((e1->flags & EDGE_TRUE_VALUE) != 0))
> - return false;
> - if ((cond2_phi_edge->flags & EDGE_TRUE_VALUE) == 0)
> + ^ (((cond2_phi_edge->flags
> + & ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
> + ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0)
> + != ((e1->flags
> + & ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
> + ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE)) != 0)))
> return false;
> if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
> return false;
> @@ -2124,7 +2177,7 @@ spaceship_replacement (basic_block cond_
>
> /* lhs1 one_cmp rhs1 results in phires of 1. */
> enum tree_code one_cmp;
> - if ((cmp1 == LT_EXPR)
> + if ((cmp1 == LT_EXPR || cmp1 == LE_EXPR)
> ^ (!integer_onep ((e1->flags & EDGE_TRUE_VALUE) ? arg1 : arg0)))
> one_cmp = LT_EXPR;
> else
>
>
> Jakub
>
>
--
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)
More information about the Gcc-patches
mailing list