diff mbox series

phiopt: Fix up spaceship_replacement [PR126564]

Message ID anGWsrujg1YejBlk@tucnak
State New
Headers
Series phiopt: Fix up spaceship_replacement [PR126564] |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_simplebootstrap_build--master-arm-bootstrap success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-arm fail Patch failed to apply

Commit Message

Jakub Jelinek Aug. 4, 2026, 7:37 a.m. UTC 
  Hi!

spaceship_replacement is for optimization of code like
    <bb 2> :  // cond3_bb
    if (a_3(D) == b_5(D))
      goto <bb 6>; [50.00%]
    else
      goto <bb 3>; [50.00%]

    <bb 3> [local count: 536870913]:  // cond2_bb
    if (a_3(D) < b_5(D))
      goto <bb 6>; [50.00%]
    else
      goto <bb 4>; [50.00%]

    <bb 4> [local count: 268435456]:  // cond_bb
    if (a_3(D) > b_5(D))
      goto <bb 6>; [50.00%]
    else
      goto <bb 5>; [50.00%]

    <bb 5> [local count: 134217728]:  // middle_bb

    <bb 6> [local count: 1073741824]:  // phi_bb
    # SR.27_4 = PHI <0(2), -1(3), 1(4), -128(5)>
    _2 = SR.27_4 > 0;
to a single comparison (i.e. say (a <=> b) > 0 in C++) (it handles
also just 2 comparisons instead of 3, but this bug is about the 3
comparisons).
In
      if (e1->flags & EDGE_TRUE_VALUE)
        {
          if (tree_to_shwi (arg0) != -128
              || absu_hwi (tree_to_shwi (arg1)) != 1
              || wi::to_widest (arg1) == wi::to_widest (arg2))
            return false;
        }
      else if (tree_to_shwi (arg1) != -128
               || absu_hwi (tree_to_shwi (arg0)) != 1
               || wi::to_widest (arg0) == wi::to_widest (arg2))
        return false;
(where e1 is 4->6 edge above, arg0 is -128(5), arg1 is 1(4),
arg2 is -1(3), cond2_phi_edge is 3->6 edge above) we deal with
the different cases of whether the TRUE edge goes directly to
phi_bb or through the empty middle_bb in between.
Right above the above checks is
      if ((cond2_phi_edge->flags & EDGE_FALSE_VALUE)
          && HONOR_NANS (TREE_TYPE (lhs1)))
        return false;
so for HONOR_NANS, cond2_phi_edge must be TRUE edge, otherwise
it can be either.  The problematic check that causes the miscompilation
of the testcase below wants to verify that the two comparisons
(cmp1 being code of a_3(D) > b_5(D) and cmp2 a_3(D) < b_5(D)))
are actually different, not just non-removed useless duplications
(which is what causes miscompilation of the testcase below).
The lhs2 == lhs1 xored case is whether the 2 comparisons are
x cmp1 y vs. x cmp2 y or x cmp1 y vs. y cmp2 x (earlier code verifies
the operands aren't different in other way with the exception of
integral comparisons and < 4 vs. <= 3 etc.).
For the HONOR_NANS case where we know cond2_phi_edge is TRUE
the other xor operand is whether both cmp2 and cmp1 are </<= or
>/>= (note, we can treat LT_EXPR and LE_EXPR the same because
the optimization requires an equality comparison first, so
LT_EXPR vs. LE_EXPR doesn't matter).  But for !HONOR_NANS I wrote
a condition checking both the comparison codes and corresponding
edge flags.  That is wrong because whether e1 is TRUE or FALSE
edge has been accounted already in the if (e1->flags & EDGE_TRUE_VALUE)
code above, all we care about is whether cond2_phi_edge is EDGE_TRUE_VALUE
or EDGE_FALSE_VALUE or the comparison codes of the two comparisons
(and order of their arguments).
So, instead this xors lhs2 == lhs1 with whether cmp{1,2} are the same
with whether cond2_phi_edge is EDGE_FALSE_VALUE.
For HONOR_NANS there is no difference because the last term will be false.
The pr94589*.c tests already cover quite a lot of different cases that
should or shouldn't be matched.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

For 15 and older the testcase will need to be tweaked slightly (see the PR),
so that it tests miscompilation in those releases.

2026-08-04  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/126564
	* tree-ssa-phiopt.cc (spaceship_replacement): Fix up condition
	when to punt because of redundant cmp1 with cmp2, xor in
	lhs1 == lhs2 with difference of cmp2 from cmp1 (ignoring
	LT_EXPR vs. LE_EXPR and GT_EXPR vs. GE_EXPR differences) and
	1 if cond2_phi_edge is EDGE_FALSE_VALUE.

	* gcc.dg/torture/pr126564.c: New test.


	Jakub

Comments

Richard Biener Aug. 4, 2026, 8:14 a.m. UTC | #1 
> Am 04.08.2026 um 09:53 schrieb Jakub Jelinek <jakub@redhat.com>:
> 
> Hi!
> 
> spaceship_replacement is for optimization of code like
>    <bb 2> :  // cond3_bb
>    if (a_3(D) == b_5(D))
>      goto <bb 6>; [50.00%]
>    else
>      goto <bb 3>; [50.00%]
> 
>    <bb 3> [local count: 536870913]:  // cond2_bb
>    if (a_3(D) < b_5(D))
>      goto <bb 6>; [50.00%]
>    else
>      goto <bb 4>; [50.00%]
> 
>    <bb 4> [local count: 268435456]:  // cond_bb
>    if (a_3(D) > b_5(D))
>      goto <bb 6>; [50.00%]
>    else
>      goto <bb 5>; [50.00%]
> 
>    <bb 5> [local count: 134217728]:  // middle_bb
> 
>    <bb 6> [local count: 1073741824]:  // phi_bb
>    # SR.27_4 = PHI <0(2), -1(3), 1(4), -128(5)>
>    _2 = SR.27_4 > 0;
> to a single comparison (i.e. say (a <=> b) > 0 in C++) (it handles
> also just 2 comparisons instead of 3, but this bug is about the 3
> comparisons).
> In
>      if (e1->flags & EDGE_TRUE_VALUE)
>        {
>          if (tree_to_shwi (arg0) != -128
>              || absu_hwi (tree_to_shwi (arg1)) != 1
>              || wi::to_widest (arg1) == wi::to_widest (arg2))
>            return false;
>        }
>      else if (tree_to_shwi (arg1) != -128
>               || absu_hwi (tree_to_shwi (arg0)) != 1
>               || wi::to_widest (arg0) == wi::to_widest (arg2))
>        return false;
> (where e1 is 4->6 edge above, arg0 is -128(5), arg1 is 1(4),
> arg2 is -1(3), cond2_phi_edge is 3->6 edge above) we deal with
> the different cases of whether the TRUE edge goes directly to
> phi_bb or through the empty middle_bb in between.
> Right above the above checks is
>      if ((cond2_phi_edge->flags & EDGE_FALSE_VALUE)
>          && HONOR_NANS (TREE_TYPE (lhs1)))
>        return false;
> so for HONOR_NANS, cond2_phi_edge must be TRUE edge, otherwise
> it can be either.  The problematic check that causes the miscompilation
> of the testcase below wants to verify that the two comparisons
> (cmp1 being code of a_3(D) > b_5(D) and cmp2 a_3(D) < b_5(D)))
> are actually different, not just non-removed useless duplications
> (which is what causes miscompilation of the testcase below).
> The lhs2 == lhs1 xored case is whether the 2 comparisons are
> x cmp1 y vs. x cmp2 y or x cmp1 y vs. y cmp2 x (earlier code verifies
> the operands aren't different in other way with the exception of
> integral comparisons and < 4 vs. <= 3 etc.).
> For the HONOR_NANS case where we know cond2_phi_edge is TRUE
> the other xor operand is whether both cmp2 and cmp1 are </<= or
>> />= (note, we can treat LT_EXPR and LE_EXPR the same because
> the optimization requires an equality comparison first, so
> LT_EXPR vs. LE_EXPR doesn't matter).  But for !HONOR_NANS I wrote
> a condition checking both the comparison codes and corresponding
> edge flags.  That is wrong because whether e1 is TRUE or FALSE
> edge has been accounted already in the if (e1->flags & EDGE_TRUE_VALUE)
> code above, all we care about is whether cond2_phi_edge is EDGE_TRUE_VALUE
> or EDGE_FALSE_VALUE or the comparison codes of the two comparisons
> (and order of their arguments).
> So, instead this xors lhs2 == lhs1 with whether cmp{1,2} are the same
> with whether cond2_phi_edge is EDGE_FALSE_VALUE.
> For HONOR_NANS there is no difference because the last term will be false.
> The pr94589*.c tests already cover quite a lot of different cases that
> should or shouldn't be matched.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok

Richard 

> For 15 and older the testcase will need to be tweaked slightly (see the PR),
> so that it tests miscompilation in those releases.
> 
> 2026-08-04  Jakub Jelinek  <jakub@redhat.com>
> 
>    PR tree-optimization/126564
>    * tree-ssa-phiopt.cc (spaceship_replacement): Fix up condition
>    when to punt because of redundant cmp1 with cmp2, xor in
>    lhs1 == lhs2 with difference of cmp2 from cmp1 (ignoring
>    LT_EXPR vs. LE_EXPR and GT_EXPR vs. GE_EXPR differences) and
>    1 if cond2_phi_edge is EDGE_FALSE_VALUE.
> 
>    * gcc.dg/torture/pr126564.c: New test.
> 
> --- gcc/tree-ssa-phiopt.cc.jj    2026-08-03 11:25:36.517969862 +0200
> +++ gcc/tree-ssa-phiopt.cc    2026-08-03 15:58:02.050898704 +0200
> @@ -2429,15 +2429,9 @@ spaceship_replacement (basic_block cond_
>     must be different for non-swapped operands and same for swapped
>     operands.  */
>       if ((lhs2 == lhs1)
> -      ^ (HONOR_NANS (TREE_TYPE (lhs1))
> -         ? ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
> -        != (cmp1 == LT_EXPR || cmp1 == LE_EXPR))
> -         : (((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))))
> +      ^ ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
> +         != (cmp1 == LT_EXPR || cmp1 == LE_EXPR))
> +      ^ ((cond2_phi_edge->flags & EDGE_FALSE_VALUE) != 0))
>    return false;
>       if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
>    return false;
> --- gcc/testsuite/gcc.dg/torture/pr126564.c.jj    2026-08-03 16:14:35.167489718 +0200
> +++ gcc/testsuite/gcc.dg/torture/pr126564.c    2026-08-03 16:15:02.877143694 +0200
> @@ -0,0 +1,25 @@
> +/* PR tree-optimization/126564 */
> +/* { dg-do run } */
> +
> +[[gnu::noipa]] int
> +foo (int x, int y)
> +{
> +  int c = -128;
> +  if (x == y)
> +    c = 0;
> +  else if (x < y)
> +    c = -1;
> +  else if (x <= y)
> +    c = 1;
> +  return c > 0;
> +}
> +
> +int
> +main ()
> +{
> +  int i, j;
> +  for (i = -3; i <= 3; i++)
> +    for (j = -3; j <= 3; j++)
> +      if (foo (i, j) != 0)
> +    __builtin_abort ();
> +}
> 
>    Jakub
>
diff mbox series

Patch

--- gcc/tree-ssa-phiopt.cc.jj	2026-08-03 11:25:36.517969862 +0200
+++ gcc/tree-ssa-phiopt.cc	2026-08-03 15:58:02.050898704 +0200
@@ -2429,15 +2429,9 @@  spaceship_replacement (basic_block cond_
 	 must be different for non-swapped operands and same for swapped
 	 operands.  */
       if ((lhs2 == lhs1)
-	  ^ (HONOR_NANS (TREE_TYPE (lhs1))
-	     ? ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
-		!= (cmp1 == LT_EXPR || cmp1 == LE_EXPR))
-	     : (((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))))
+	  ^ ((cmp2 == LT_EXPR || cmp2 == LE_EXPR)
+	     != (cmp1 == LT_EXPR || cmp1 == LE_EXPR))
+	  ^ ((cond2_phi_edge->flags & EDGE_FALSE_VALUE) != 0))
 	return false;
       if (!single_pred_p (cond2_bb) || !cond_only_block_p (cond2_bb))
 	return false;
--- gcc/testsuite/gcc.dg/torture/pr126564.c.jj	2026-08-03 16:14:35.167489718 +0200
+++ gcc/testsuite/gcc.dg/torture/pr126564.c	2026-08-03 16:15:02.877143694 +0200
@@ -0,0 +1,25 @@ 
+/* PR tree-optimization/126564 */
+/* { dg-do run } */
+
+[[gnu::noipa]] int
+foo (int x, int y)
+{
+  int c = -128;
+  if (x == y)
+    c = 0;
+  else if (x < y)
+    c = -1;
+  else if (x <= y)
+    c = 1;
+  return c > 0;
+}
+
+int
+main ()
+{
+  int i, j;
+  for (i = -3; i <= 3; i++)
+    for (j = -3; j <= 3; j++)
+      if (foo (i, j) != 0)
+	__builtin_abort ();
+}