Re: [PATCH] phiopt: Improve value_replacement [PR104645]

[Richard Biener <rguenther@suse.de>]

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
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Ivo Totev; HRB 36809 (AG Nuernberg)