phiopt: Improve value_replacement [PR104645]

Hi!

The following patch fixes the P1 regression by reusing existing
value_replacement code.  That function already has code to
handle simple preparation statements (casts, and +,&,|,^ binary
assignments) before a final binary assignment (which can be
much wider range of ops).  When we have e.g.
      if (y_3(D) == 0)
        goto <bb 4>;
      else
        goto <bb 3>;
     <bb 3>:
      y_4 = y_3(D) & 31;
      _1 = (int) y_4;
      _6 = x_5(D) r<< _1;
     <bb 4>:
      # _2 = PHI <x_5(D)(2), _6(3)>
the preparation statements y_4 = y_3(D) & 31; and
_1 = (int) y_4; are handled by constant evaluation, passing through
y_3(D) = 0 initially and propagating that through the assignments
with checking that UB isn't invoked.  But the final
_6 = x_5(D) r<< _1; assign is handled differently, either through
neutral_element_p or absorbing_element_p.
In the first function below we now have:
  <bb 2> [local count: 1073741824]:
  if (i_2(D) != 0)
    goto <bb 3>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 3> [local count: 536870913]:
  _3 = i_2(D) & 1;
  iftmp.0_4 = (int) _3;

  <bb 4> [local count: 1073741824]:
  # iftmp.0_1 = PHI <iftmp.0_4(3), 0(2)>
where in GCC 11 we had:
  <bb 2> :
  if (i_3(D) != 0)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  i.1_1 = (int) i_3(D);
  iftmp.0_5 = i.1_1 & 1;

  <bb 4> :
  # iftmp.0_2 = PHI <iftmp.0_5(3), 0(2)>
Current value_replacement can handle the latter as the last
stmt of middle_bb is a binary op that in this case satisfies
absorbing_element_p.
But the former we can't handle, as the last stmt in middle_bb
is a cast.

The patch makes it work in that case by pretending all of middle_bb
are the preparation statements and there is no binary assign at the
end, so everything is handled through the constant evaluation.
We simply set at the start of middle_bb the lhs of comparison
virtually to the rhs, propagate it through and at the end
see if virtually the arg0 of the PHI is equal to arg1 of it.

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

For GCC 13, I think we just should throw away all the neutral/absorbing
element stuff and do the constant evaluation of the whole middle_bb
and handle that way all the ops we currently handle in neutral/absorbing
element.

2022-04-01  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/104645
	* tree-ssa-phiopt.cc (value_replacement): If assign has
	CONVERT_EXPR_CODE_P rhs_code, treat it like a preparation
	statement with constant evaluation.

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


	Jakub

On Fri, 1 Apr 2022, Jakub Jelinek wrote:

> Hi!
> 
> The following patch fixes the P1 regression by reusing existing
> value_replacement code.  That function already has code to
> handle simple preparation statements (casts, and +,&,|,^ binary
> assignments) before a final binary assignment (which can be
> much wider range of ops).  When we have e.g.
>       if (y_3(D) == 0)
>         goto <bb 4>;
>       else
>         goto <bb 3>;
>      <bb 3>:
>       y_4 = y_3(D) & 31;
>       _1 = (int) y_4;
>       _6 = x_5(D) r<< _1;
>      <bb 4>:
>       # _2 = PHI <x_5(D)(2), _6(3)>
> the preparation statements y_4 = y_3(D) & 31; and
> _1 = (int) y_4; are handled by constant evaluation, passing through
> y_3(D) = 0 initially and propagating that through the assignments
> with checking that UB isn't invoked.  But the final
> _6 = x_5(D) r<< _1; assign is handled differently, either through
> neutral_element_p or absorbing_element_p.
> In the first function below we now have:
>   <bb 2> [local count: 1073741824]:
>   if (i_2(D) != 0)
>     goto <bb 3>; [50.00%]
>   else
>     goto <bb 4>; [50.00%]
> 
>   <bb 3> [local count: 536870913]:
>   _3 = i_2(D) & 1;
>   iftmp.0_4 = (int) _3;
> 
>   <bb 4> [local count: 1073741824]:
>   # iftmp.0_1 = PHI <iftmp.0_4(3), 0(2)>
> where in GCC 11 we had:
>   <bb 2> :
>   if (i_3(D) != 0)
>     goto <bb 3>; [INV]
>   else
>     goto <bb 4>; [INV]
> 
>   <bb 3> :
>   i.1_1 = (int) i_3(D);
>   iftmp.0_5 = i.1_1 & 1;
> 
>   <bb 4> :
>   # iftmp.0_2 = PHI <iftmp.0_5(3), 0(2)>
> Current value_replacement can handle the latter as the last
> stmt of middle_bb is a binary op that in this case satisfies
> absorbing_element_p.
> But the former we can't handle, as the last stmt in middle_bb
> is a cast.
> 
> The patch makes it work in that case by pretending all of middle_bb
> are the preparation statements and there is no binary assign at the
> end, so everything is handled through the constant evaluation.
> We simply set at the start of middle_bb the lhs of comparison
> virtually to the rhs, propagate it through and at the end
> see if virtually the arg0 of the PHI is equal to arg1 of it.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

OK.

> For GCC 13, I think we just should throw away all the neutral/absorbing
> element stuff and do the constant evaluation of the whole middle_bb
> and handle that way all the ops we currently handle in neutral/absorbing
> element.

Agreed - that would be a nice cleanup.

Thanks,
Richard.

> 2022-04-01  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/104645
> 	* tree-ssa-phiopt.cc (value_replacement): If assign has
> 	CONVERT_EXPR_CODE_P rhs_code, treat it like a preparation
> 	statement with constant evaluation.
> 
> 	* gcc.dg/tree-ssa/pr104645.c: New test.
> 
> --- gcc/tree-ssa-phiopt.cc.jj	2022-01-18 11:59:00.089974814 +0100
> +++ gcc/tree-ssa-phiopt.cc	2022-03-31 14:38:27.537149245 +0200
> @@ -1395,11 +1395,22 @@ value_replacement (basic_block cond_bb,
>  
>    gimple *assign = gsi_stmt (gsi);
>    if (!is_gimple_assign (assign)
> -      || gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS
>        || (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
>  	  && !POINTER_TYPE_P (TREE_TYPE (arg0))))
>      return 0;
>  
> +  if (gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS)
> +    {
> +      /* If last stmt of the middle_bb is a conversion, handle it like
> +	 a preparation statement through constant evaluation with
> +	 checking for UB.  */
> +      enum tree_code sc = gimple_assign_rhs_code (assign);
> +      if (CONVERT_EXPR_CODE_P (sc))
> +	assign = NULL;
> +      else
> +	return 0;
> +    }
> +
>    /* Punt if there are (degenerate) PHIs in middle_bb, there should not be.  */
>    if (!gimple_seq_empty_p (phi_nodes (middle_bb)))
>      return 0;
> @@ -1430,7 +1441,8 @@ value_replacement (basic_block cond_bb,
>    int prep_cnt;
>    for (prep_cnt = 0; ; prep_cnt++)
>      {
> -      gsi_prev_nondebug (&gsi);
> +      if (prep_cnt || assign)
> +	gsi_prev_nondebug (&gsi);
>        if (gsi_end_p (gsi))
>  	break;
>  
> @@ -1450,7 +1462,8 @@ value_replacement (basic_block cond_bb,
>  	  || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
>  	  || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
>  	  || !single_imm_use (lhs, &use_p, &use_stmt)
> -	  || use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign))
> +	  || ((prep_cnt || assign)
> +	      && use_stmt != (prep_cnt ? prep_stmt[prep_cnt - 1] : assign)))
>  	return 0;
>        switch (gimple_assign_rhs_code (g))
>  	{
> @@ -1483,10 +1496,6 @@ value_replacement (basic_block cond_bb,
>  	 >= 3 * estimate_num_insns (cond, &eni_time_weights))
>      return 0;
>  
> -  tree lhs = gimple_assign_lhs (assign);
> -  tree rhs1 = gimple_assign_rhs1 (assign);
> -  tree rhs2 = gimple_assign_rhs2 (assign);
> -  enum tree_code code_def = gimple_assign_rhs_code (assign);
>    tree cond_lhs = gimple_cond_lhs (cond);
>    tree cond_rhs = gimple_cond_rhs (cond);
>  
> @@ -1516,16 +1525,39 @@ value_replacement (basic_block cond_bb,
>  	return 0;
>      }
>  
> +  tree lhs, rhs1, rhs2;
> +  enum tree_code code_def;
> +  if (assign)
> +    {
> +      lhs = gimple_assign_lhs (assign);
> +      rhs1 = gimple_assign_rhs1 (assign);
> +      rhs2 = gimple_assign_rhs2 (assign);
> +      code_def = gimple_assign_rhs_code (assign);
> +    }
> +  else
> +    {
> +      gcc_assert (prep_cnt > 0);
> +      lhs = cond_lhs;
> +      rhs1 = NULL_TREE;
> +      rhs2 = NULL_TREE;
> +      code_def = ERROR_MARK;
> +    }
> +
>    if (((code == NE_EXPR && e1 == false_edge)
>  	|| (code == EQ_EXPR && e1 == true_edge))
>        && arg0 == lhs
> -      && ((arg1 == rhs1
> -	   && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
> -	   && neutral_element_p (code_def, cond_rhs, true))
> -	  || (arg1 == rhs2
> +      && ((assign == NULL
> +	   && operand_equal_for_phi_arg_p (arg1, cond_rhs))
> +	  || (assign
> +	      && arg1 == rhs1
> +	      && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
> +	      && neutral_element_p (code_def, cond_rhs, true))
> +	  || (assign
> +	      && arg1 == rhs2
>  	      && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
>  	      && neutral_element_p (code_def, cond_rhs, false))
> -	  || (operand_equal_for_phi_arg_p (arg1, cond_rhs)
> +	  || (assign
> +	      && operand_equal_for_phi_arg_p (arg1, cond_rhs)
>  	      && ((operand_equal_for_phi_arg_p (rhs2, cond_lhs)
>  		   && absorbing_element_p (code_def, cond_rhs, true, rhs2))
>  		  || (operand_equal_for_phi_arg_p (rhs1, cond_lhs)
> @@ -1555,8 +1587,11 @@ value_replacement (basic_block cond_bb,
>  	  gsi_from = gsi_for_stmt (prep_stmt[i]);
>  	  gsi_move_before (&gsi_from, &gsi);
>  	}
> -      gsi_from = gsi_for_stmt (assign);
> -      gsi_move_before (&gsi_from, &gsi);
> +      if (assign)
> +	{
> +	  gsi_from = gsi_for_stmt (assign);
> +	  gsi_move_before (&gsi_from, &gsi);
> +	}
>        replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
>        return 2;
>      }
> --- gcc/testsuite/gcc.dg/tree-ssa/pr104645.c.jj	2022-03-31 15:02:15.116389726 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/pr104645.c	2022-03-31 15:01:45.674817966 +0200
> @@ -0,0 +1,28 @@
> +/* PR tree-optimization/104645 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +/* { dg-final { scan-tree-dump-not " = PHI <" "optimized" } } */
> +
> +int
> +foo (unsigned i)
> +{
> +  return i ? i % 2 : 0;
> +}
> +
> +int
> +bar (unsigned i)
> +{
> +  int b = 0;
> +  if (i)
> +    {
> +      unsigned a = i & 1;
> +      b = a;
> +    }
> +  return b;
> +}
> +
> +int
> +baz (unsigned i)
> +{
> +  return i ? i + 4 : 4;
> +}
> 
> 	Jakub
> 
>