Improve ifcombine

Hi!

This patch fixes the ssa-ifcombine-10.c regression.
The thing is that the uselessly added ASSERT_EXPR makes vrp1 change
the cfg slightly like this:
   <bb 2>:
   _4 = x_3(D) & 1;
   if (_4 == 0)
     goto <bb 5>;
   else
     goto <bb 3>;
 
   <bb 3>:
   _5 = x_3(D) & 4;
   if (_5 != 0)
-    goto <bb 5>;
-  else
     goto <bb 4>;
+  else
+    goto <bb 5>;
 
   <bb 4>:
 
   <bb 5>:
-  # t_1 = PHI <0(2), 3(3), 0(4)>
+  # t_1 = PHI <0(2), 3(4), 0(3)>
   return t_1;
(addition of the ASSERT_EXPR resulted in creation of a new bb to insert
it into and that bb is then removed again during cfg cleanup, but
it ends up effectively swapping the forwarder block from one edge of the
gimple cond to the other with corresponding phi arg change).
Now, tree_ssa_ifcombine_bb apparently only groks the latter form (the one
with + lines), but not the equivalent form the testcase had before VRP
(and with the PR60482 fix also has after VRP, the one with - lines).

This patch teaches tree_ssa_ifcombine_bb to handle both forms.

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

Note, the phi-opt-2.c change is there because the patch made the
test fail, as for LOGICAL_OP_NON_SHORT_CIRCUIT we now generate even
better code, return a && b.  So, I've added ssa-ifcombine-13.c test
which is phi-opt-2.c and test that for -mbranch-cost=2 we have no ifs,
and phi-opt-2.c now checks that for -mbranch-cost=1 we do have one if
(ifcombine then doesn't do anything and we verify that phiopt does what it
should).

2014-03-11  Jakub Jelinek  <jakub@redhat.com>

	* tree-ssa-ifcombine.c (forwarder_block_to): New function.
	(tree_ssa_ifcombine_bb): Handle also cases where else_bb is
	an empty forwarder block to then_bb or vice versa and then_bb
	and else_bb are effectively swapped.

	* gcc.dg/tree-ssa/ssa-ifcombine-12.c: New test.
	* gcc.dg/tree-ssa/ssa-ifcombine-13.c: New test.
	* gcc.dg/tree-ssa/phi-opt-2.c: Pass -mbranch-cost=1 if
	possible, only test for exactly one if if -mbranch-cost=1
	has been passed.


	Jakub

On Tue, 11 Mar 2014, Jakub Jelinek wrote:

> Hi!
> 
> This patch fixes the ssa-ifcombine-10.c regression.
> The thing is that the uselessly added ASSERT_EXPR makes vrp1 change
> the cfg slightly like this:
>    <bb 2>:
>    _4 = x_3(D) & 1;
>    if (_4 == 0)
>      goto <bb 5>;
>    else
>      goto <bb 3>;
>  
>    <bb 3>:
>    _5 = x_3(D) & 4;
>    if (_5 != 0)
> -    goto <bb 5>;
> -  else
>      goto <bb 4>;
> +  else
> +    goto <bb 5>;
>  
>    <bb 4>:
>  
>    <bb 5>:
> -  # t_1 = PHI <0(2), 3(3), 0(4)>
> +  # t_1 = PHI <0(2), 3(4), 0(3)>
>    return t_1;
> (addition of the ASSERT_EXPR resulted in creation of a new bb to insert
> it into and that bb is then removed again during cfg cleanup, but
> it ends up effectively swapping the forwarder block from one edge of the
> gimple cond to the other with corresponding phi arg change).
> Now, tree_ssa_ifcombine_bb apparently only groks the latter form (the one
> with + lines), but not the equivalent form the testcase had before VRP
> (and with the PR60482 fix also has after VRP, the one with - lines).
> 
> This patch teaches tree_ssa_ifcombine_bb to handle both forms.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok in principle, but is there a possibility to factor this a bit?
It looks like a lot of cut&paste (without looking too close for subtle
differences).

Thanks,
Richard.

> Note, the phi-opt-2.c change is there because the patch made the
> test fail, as for LOGICAL_OP_NON_SHORT_CIRCUIT we now generate even
> better code, return a && b.  So, I've added ssa-ifcombine-13.c test
> which is phi-opt-2.c and test that for -mbranch-cost=2 we have no ifs,
> and phi-opt-2.c now checks that for -mbranch-cost=1 we do have one if
> (ifcombine then doesn't do anything and we verify that phiopt does what it
> should).
> 
> 2014-03-11  Jakub Jelinek  <jakub@redhat.com>
> 
> 	* tree-ssa-ifcombine.c (forwarder_block_to): New function.
> 	(tree_ssa_ifcombine_bb): Handle also cases where else_bb is
> 	an empty forwarder block to then_bb or vice versa and then_bb
> 	and else_bb are effectively swapped.
> 
> 	* gcc.dg/tree-ssa/ssa-ifcombine-12.c: New test.
> 	* gcc.dg/tree-ssa/ssa-ifcombine-13.c: New test.
> 	* gcc.dg/tree-ssa/phi-opt-2.c: Pass -mbranch-cost=1 if
> 	possible, only test for exactly one if if -mbranch-cost=1
> 	has been passed.
> 
> --- gcc/tree-ssa-ifcombine.c.jj	2014-03-11 12:13:53.012618098 +0100
> +++ gcc/tree-ssa-ifcombine.c	2014-03-11 16:15:29.084329709 +0100
> @@ -135,6 +135,16 @@ bb_no_side_effects_p (basic_block bb)
>    return true;
>  }
>  
> +/* Return true if BB is an empty forwarder block to TO_BB.  */
> +
> +static bool
> +forwarder_block_to (basic_block bb, basic_block to_bb)
> +{
> +  return empty_block_p (bb)
> +	 && single_succ_p (bb)
> +	 && single_succ (bb) == to_bb;
> +}
> +
>  /* Verify if all PHI node arguments in DEST for edges from BB1 or
>     BB2 to DEST are the same.  This makes the CFG merge point
>     free from side-effects.  Return true in this case, else false.  */
> @@ -660,6 +670,102 @@ tree_ssa_ifcombine_bb (basic_block inner
>  	  return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false,
>  				    true);
>  	}
> +
> +      if (forwarder_block_to (else_bb, then_bb))
> +	{
> +	  /* Other possibilities for the && form, if else_bb is
> +	     empty forwarder block to then_bb.  Compared to the above simpler
> +	     forms this can be treated as if then_bb and else_bb were swapped,
> +	     and the corresponding inner_cond_bb not inverted because of that.
> +	     For same_phi_args_p we look at equality of arguments between
> +	     edge from outer_cond_bb and the forwarder block.  */
> +	  if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
> +	      && same_phi_args_p (outer_cond_bb, else_bb, then_bb)
> +	      && bb_no_side_effects_p (inner_cond_bb))
> +	    {
> +	      /* We have
> +		   <outer_cond_bb>
> +		     if (q) goto inner_cond_bb; else goto then_bb;
> +		   <inner_cond_bb>
> +		     if (p) goto then_bb; else goto else_bb;
> +		   <else_bb>
> +		     # empty fallthru
> +		   <then_bb>
> +		     # x = PHI <y(outer), z(inner), y(else)>
> +		     ...
> +	       */
> +	      return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb,
> +					false, false);
> +	    }
> +
> +	  /* And a version where the outer condition is negated.  */
> +	  if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
> +	      && same_phi_args_p (outer_cond_bb, else_bb, then_bb)
> +	      && bb_no_side_effects_p (inner_cond_bb))
> +	    {
> +	      /* We have
> +		   <outer_cond_bb>
> +		     if (q) goto then_bb; else goto inner_cond_bb;
> +		   <inner_cond_bb>
> +		     if (p) goto then_bb; else goto else_bb;
> +		   <else_bb>
> +		     # empty fallthru
> +		   <then_bb>
> +		     # x = PHI <y(outer), z(inner), y(else)>
> +		     ...
> +	       */
> +	      return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb,
> +					true, false);
> +	    }
> +	}
> +
> +      if (forwarder_block_to (then_bb, else_bb))
> +	{
> +	  /* Other possibilities for the || form, if then_bb is
> +	     empty forwarder block to else_bb.  Compared to the above simpler
> +	     forms this can be treated as if then_bb and else_bb were swapped,
> +	     and the corresponding inner_cond_bb not inverted because of that.
> +	     For same_phi_args_p we look at equality of arguments between
> +	     edge from outer_cond_bb and the forwarder block.  */
> +	  if (recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
> +	      && same_phi_args_p (outer_cond_bb, then_bb, else_bb)
> +	      && bb_no_side_effects_p (inner_cond_bb))
> +	    {
> +	      /* We have
> +		   <outer_cond_bb>
> +		     if (q) goto else_bb; else goto inner_cond_bb;
> +		   <inner_cond_bb>
> +		     if (q) goto then_bb; else goto else_bb;
> +		   <then_bb>
> +		     # empty fallthru
> +		   <else_bb>
> +		     # x = PHI <y(outer), z(inner), y(then)>
> +		     ...
> +	       */
> +	      return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb,
> +					true, true);
> +	    }
> +
> +	  /* And a version where the outer condition is negated.  */
> +	  if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
> +	      && same_phi_args_p (outer_cond_bb, then_bb, else_bb)
> +	      && bb_no_side_effects_p (inner_cond_bb))
> +	    {
> +	      /* We have
> +		   <outer_cond_bb>
> +		     if (q) goto inner_cond_bb; else goto else_bb;
> +		   <inner_cond_bb>
> +		     if (q) goto then_bb; else goto else_bb;
> +		   <then_bb>
> +		     # empty fallthru
> +		   <else_bb>
> +		     # x = PHI <y(outer), z(inner), y(then)>
> +		     ...
> +	       */
> +	      return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb,
> +					false, true);
> +	    }
> +	}
>      }
>  
>    return false;
> --- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c.jj	2014-03-11 16:15:29.085329698 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c	2014-03-11 16:15:29.085329698 +0100
> @@ -0,0 +1,20 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-optimized" } */
> +
> +/* Testcase for PR31657.  */
> +
> +int f(int x, int a, int b)
> +{
> +  int t = 0;
> +  int c = 1 << a;
> +  if (!(x & 1))
> +    t = 0;
> +  else
> +    if (x & (1 << 2))
> +      t = 3;
> +    else
> +      t = 0;
> +  return t;
> +}
> +/* { dg-final { scan-tree-dump "& 5" "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> --- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c.jj	2014-03-11 16:28:49.506695564 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c	2014-03-11 16:31:11.426884506 +0100
> @@ -0,0 +1,21 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O1 -fdump-tree-optimized" } */
> +/* { dg-additional-options "-mbranch-cost=2" { target { i?86-*-* x86_64-*-* mips*-*-* s390*-*-* avr*-*-* } } } */
> +
> +_Bool f1(_Bool a, _Bool b)
> +{
> +  if (a)
> +   {
> +     if (b)
> +      return 1;
> +     else
> +      return 0;
> +   }
> +  return 0;
> +}
> +
> +
> +/* For LOGICAL_OP_NON_SHORT_CIRCUIT, this should be optimized
> +   into return a & b;, with no ifs.  */
> +/* { dg-final { scan-tree-dump-not "if" "optimized" { target { i?86-*-* x86_64-*-* mips*-*-* s390*-*-* avr*-*-* } } } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
> --- gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c.jj	2008-09-05 12:54:30.000000000 +0200
> +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c	2014-03-11 16:28:21.693848143 +0100
> @@ -1,5 +1,6 @@
>  /* { dg-do compile } */
>  /* { dg-options "-O1 -fdump-tree-optimized" } */
> +/* { dg-additional-options "-mbranch-cost=1" { target { i?86-*-* x86_64-*-* mips*-*-* s390*-*-* avr*-*-* } } } */
>  
>  _Bool f1(_Bool a, _Bool b)
>  {
> @@ -17,6 +18,8 @@ _Bool f1(_Bool a, _Bool b)
>  /* There should be only one if, the outer one; the inner one
>     should have been changed to straight line code with the
>     value of b (except that we don't fold ! (b != 0) into b
> -   which can be fixed in a different patch).  */
> -/* { dg-final { scan-tree-dump-times "if" 1 "optimized"} } */
> +   which can be fixed in a different patch).
> +   Test this only when known to be !LOGICAL_OP_NON_SHORT_CIRCUIT,
> +   otherwise ifcombine may convert this into return a & b;.  */
> +/* { dg-final { scan-tree-dump-times "if" 1 "optimized" { target { i?86-*-* x86_64-*-* mips*-*-* s390*-*-* avr*-*-* } } } } */
>  /* { dg-final { cleanup-tree-dump "optimized" } } */
> 
> 	Jakub
> 
>