reassoc: Improve maybe_optimize_range_tests [PR96480]

Hi!

On the following testcase, if the IL before reassoc would be:
...
  <bb 4> [local count: 354334800]:
  if (x_3(D) == 2)
    goto <bb 7>; [34.00%]
  else
    goto <bb 5>; [66.00%]

  <bb 5> [local count: 233860967]:
  if (x_3(D) == 3)
    goto <bb 7>; [34.00%]
  else
    goto <bb 6>; [66.00%]

  <bb 6> [local count: 79512730]:

  <bb 7> [local count: 1073741824]:
  # prephitmp_7 = PHI <1(3), 1(4), 1(5), 1(2), 0(6)>
then we'd optimize it properly, but as bb 5-7 is instead:
  <bb 5> [local count: 233860967]:
  if (x_3(D) == 3)
    goto <bb 6>; [34.00%]
  else
    goto <bb 7>; [66.00%]

  <bb 6> [local count: 79512730]:

  <bb 7> [local count: 1073741824]:
  # prephitmp_7 = PHI <1(3), 1(4), 0(5), 1(2), 1(6)>
(i.e. the true/false edges on the last bb with condition swapped
and ditto for the phi args), we don't recognize it.  If bb 6
is empty, there should be no functional difference between the two IL
representations.

This patch handles those special cases.

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

2020-08-06  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/96480
	* tree-ssa-reassoc.c (suitable_cond_bb): Add TEST_SWAPPED_P argument.
	If TEST_BB ends in cond and has one edge to *OTHER_BB and another
	through an empty bb to that block too, if PHI args don't match, retry
	them through the other path from TEST_BB.
	(maybe_optimize_range_tests): Adjust callers.  Handle such LAST_BB
	through inversion of the condition.

	* gcc.dg/tree-ssa/pr96480.c: New test.


	Jakub

On Thu, 6 Aug 2020, Jakub Jelinek wrote:

> Hi!
> 
> On the following testcase, if the IL before reassoc would be:
> ...
>   <bb 4> [local count: 354334800]:
>   if (x_3(D) == 2)
>     goto <bb 7>; [34.00%]
>   else
>     goto <bb 5>; [66.00%]
> 
>   <bb 5> [local count: 233860967]:
>   if (x_3(D) == 3)
>     goto <bb 7>; [34.00%]
>   else
>     goto <bb 6>; [66.00%]
> 
>   <bb 6> [local count: 79512730]:
> 
>   <bb 7> [local count: 1073741824]:
>   # prephitmp_7 = PHI <1(3), 1(4), 1(5), 1(2), 0(6)>
> then we'd optimize it properly, but as bb 5-7 is instead:
>   <bb 5> [local count: 233860967]:
>   if (x_3(D) == 3)
>     goto <bb 6>; [34.00%]
>   else
>     goto <bb 7>; [66.00%]
> 
>   <bb 6> [local count: 79512730]:
> 
>   <bb 7> [local count: 1073741824]:
>   # prephitmp_7 = PHI <1(3), 1(4), 0(5), 1(2), 1(6)>
> (i.e. the true/false edges on the last bb with condition swapped
> and ditto for the phi args), we don't recognize it.  If bb 6
> is empty, there should be no functional difference between the two IL
> representations.
> 
> This patch handles those special cases.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

OK.

Thanks,
Richard.

> 2020-08-06  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/96480
> 	* tree-ssa-reassoc.c (suitable_cond_bb): Add TEST_SWAPPED_P argument.
> 	If TEST_BB ends in cond and has one edge to *OTHER_BB and another
> 	through an empty bb to that block too, if PHI args don't match, retry
> 	them through the other path from TEST_BB.
> 	(maybe_optimize_range_tests): Adjust callers.  Handle such LAST_BB
> 	through inversion of the condition.
> 
> 	* gcc.dg/tree-ssa/pr96480.c: New test.
> 
> --- gcc/tree-ssa-reassoc.c.jj	2020-07-30 15:04:38.000000000 +0200
> +++ gcc/tree-ssa-reassoc.c	2020-08-06 11:19:30.942825436 +0200
> @@ -4127,11 +4127,14 @@ final_range_test_p (gimple *stmt)
>     of TEST_BB, and *OTHER_BB is either NULL and filled by the routine,
>     or compared with to find a common basic block to which all conditions
>     branch to if true resp. false.  If BACKWARD is false, TEST_BB should
> -   be the only predecessor of BB.  */
> +   be the only predecessor of BB.  *TEST_SWAPPED_P is set to true if
> +   TEST_BB is a bb ending in condition where the edge to non-*OTHER_BB
> +   block points to an empty block that falls through into *OTHER_BB and
> +   the phi args match that path.  */
>  
>  static bool
>  suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb,
> -		  bool backward)
> +		  bool *test_swapped_p, bool backward)
>  {
>    edge_iterator ei, ei2;
>    edge e, e2;
> @@ -4196,6 +4199,7 @@ suitable_cond_bb (basic_block bb, basic_
>    /* Now check all PHIs of *OTHER_BB.  */
>    e = find_edge (bb, *other_bb);
>    e2 = find_edge (test_bb, *other_bb);
> + retry:;
>    for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
>      {
>        gphi *phi = gsi.phi ();
> @@ -4221,11 +4225,52 @@ suitable_cond_bb (basic_block bb, basic_
>  	  else
>  	    {
>  	      gimple *test_last = last_stmt (test_bb);
> -	      if (gimple_code (test_last) != GIMPLE_COND
> -		  && gimple_phi_arg_def (phi, e2->dest_idx)
> -		     == gimple_assign_lhs (test_last)
> -		  && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx))
> -		      || integer_onep (gimple_phi_arg_def (phi, e->dest_idx))))
> +	      if (gimple_code (test_last) == GIMPLE_COND)
> +		{
> +		  if (backward ? e2->src != test_bb : e->src != bb)
> +		    return false;
> +
> +		  /* For last_bb, handle also:
> +		     if (x_3(D) == 3)
> +		       goto <bb 6>; [34.00%]
> +		     else
> +		       goto <bb 7>; [66.00%]
> +
> +		     <bb 6> [local count: 79512730]:
> +
> +		     <bb 7> [local count: 1073741824]:
> +		     # prephitmp_7 = PHI <1(3), 1(4), 0(5), 1(2), 1(6)>
> +		     where bb 7 is *OTHER_BB, but the PHI values from the
> +		     earlier bbs match the path through the empty bb
> +		     in between.  */
> +		  edge e3;
> +		  if (backward)
> +		    e3 = EDGE_SUCC (test_bb,
> +				    e2 == EDGE_SUCC (test_bb, 0) ? 1 : 0);
> +		  else
> +		    e3 = EDGE_SUCC (bb,
> +				    e == EDGE_SUCC (bb, 0) ? 1 : 0);
> +		  if (empty_block_p (e3->dest)
> +		      && single_succ_p (e3->dest)
> +		      && single_succ (e3->dest) == *other_bb
> +		      && single_pred_p (e3->dest)
> +		      && single_succ_edge (e3->dest)->flags == EDGE_FALLTHRU)
> +		    {
> +		      if (backward)
> +			e2 = single_succ_edge (e3->dest);
> +		      else
> +			e = single_succ_edge (e3->dest);
> +		      if (test_swapped_p)
> +			*test_swapped_p = true;
> +		      goto retry;
> +		    }
> +		}
> +	      else if (gimple_phi_arg_def (phi, e2->dest_idx)
> +		       == gimple_assign_lhs (test_last)
> +		       && (integer_zerop (gimple_phi_arg_def (phi,
> +							      e->dest_idx))
> +			   || integer_onep (gimple_phi_arg_def (phi,
> +								e->dest_idx))))
>  		continue;
>  	    }
>  
> @@ -4414,7 +4459,7 @@ maybe_optimize_range_tests (gimple *stmt
>    while (single_pred_p (first_bb))
>      {
>        basic_block pred_bb = single_pred (first_bb);
> -      if (!suitable_cond_bb (pred_bb, first_bb, &other_bb, true))
> +      if (!suitable_cond_bb (pred_bb, first_bb, &other_bb, NULL, true))
>  	break;
>        if (!no_side_effect_bb (first_bb))
>  	break;
> @@ -4444,7 +4489,8 @@ maybe_optimize_range_tests (gimple *stmt
>  		&& gimple_code (stmt) == GIMPLE_COND
>  		&& EDGE_COUNT (e->dest->succs) == 2)
>  	      {
> -		if (suitable_cond_bb (first_bb, e->dest, &other_bb, true))
> +		if (suitable_cond_bb (first_bb, e->dest, &other_bb,
> +				      NULL, true))
>  		  break;
>  		else
>  		  other_bb = NULL;
> @@ -4472,7 +4518,7 @@ maybe_optimize_range_tests (gimple *stmt
>  	break;
>        if (!single_pred_p (e->dest))
>  	break;
> -      if (!suitable_cond_bb (e->dest, last_bb, &other_bb, false))
> +      if (!suitable_cond_bb (e->dest, last_bb, &other_bb, NULL, false))
>  	break;
>        if (!no_side_effect_bb (e->dest))
>  	break;
> @@ -4583,6 +4629,28 @@ maybe_optimize_range_tests (gimple *stmt
>  	  bbinfo.safe_push (bb_ent);
>  	  continue;
>  	}
> +      else if (bb == last_bb)
> +	{
> +	  /* For last_bb, handle also:
> +	     if (x_3(D) == 3)
> +	       goto <bb 6>; [34.00%]
> +	     else
> +	       goto <bb 7>; [66.00%]
> +
> +	     <bb 6> [local count: 79512730]:
> +
> +	     <bb 7> [local count: 1073741824]:
> +	     # prephitmp_7 = PHI <1(3), 1(4), 0(5), 1(2), 1(6)>
> +	     where bb 7 is OTHER_BB, but the PHI values from the
> +	     earlier bbs match the path through the empty bb
> +	     in between.  */
> +	  bool test_swapped_p = false;
> +	  bool ok = suitable_cond_bb (single_pred (last_bb), last_bb,
> +				      &other_bb, &test_swapped_p, true);
> +	  gcc_assert (ok);
> +	  if (test_swapped_p)
> +	    e = EDGE_SUCC (bb, e == EDGE_SUCC (bb, 0) ? 1 : 0);
> +	}
>        /* Otherwise stmt is GIMPLE_COND.  */
>        code = gimple_cond_code (stmt);
>        lhs = gimple_cond_lhs (stmt);
> --- gcc/testsuite/gcc.dg/tree-ssa/pr96480.c.jj	2020-08-05 16:08:30.625614787 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr96480.c	2020-08-05 16:02:32.498832099 +0200
> @@ -0,0 +1,23 @@
> +/* PR tree-optimization/96480 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* { dg-final { scan-tree-dump " = _\[0-9]* <= 3;" "optimized" } } */
> +
> +int v[4];
> +
> +int
> +foo (int x)
> +{
> +  int *p;
> +  if (x == 0)
> +    p = &v[0];
> +  else if (x == 1)
> +    p = &v[1];
> +  else if (x == 2)
> +    p = &v[2];
> +  else if (x == 3)
> +    p = &v[3];
> +  else
> +    p = &v[4];
> +  return p != &v[4];
> +}
> 
> 	Jakub
> 
>