Patchwork PR 51938: extend ifcombine

login
register
mail settings
Submitter Marc Glisse
Date July 23, 2012, 8:58 p.m.
Message ID <alpine.DEB.2.02.1207232222550.4140@laptop-mg.saclay.inria.fr>
Download mbox | patch
Permalink /patch/172744/
State New
Headers show

Comments

Marc Glisse - July 23, 2012, 8:58 p.m.
On Wed, 20 Jun 2012, Richard Guenther wrote:

> On Sun, Jun 10, 2012 at 4:16 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> Hello,
>>
>> currently, tree-ssa-ifcombine handles pairs of imbricated "if"s that share
>> the same then branch, or the same else branch. There is no particular reason
>> why it couldn't also handle the case where the then branch of one is the
>> else branch of the other, which is what I do here.
>>
>> Any comments?
>
> The general idea looks good, but I think the patch is too invasive.  As far
> as I can see the only callers with a non-zero 'inv' argument come from
> ifcombine_ifnotorif and ifcombine_ifnotandif (and both with inv == 2).
> I would rather see a more localized patch that makes use of
> invert_tree_comparison to perform the inversion on the call arguments
> of maybe_fold_and/or_comparisons.

Hello,

I finally went back to this version (which is where I started from, as 
shown in the PR). It is not very satisfying because:

* some bit tests could also be optimized (more generally, grouping a&&b 
and !a&&b on one side and a||b and !a||b on the other side is rather 
arbitrary),

* -ftrapping-math makes it useless for floating point,

but I guess it is better than nothing. Handling traps correctly is 
complicated because the current code is already a bit bogus (see 
http://gcc.gnu.org/ml/gcc-patches/2012-07/msg00924.html for an example), 
and even the definition of -ftrapping-math is not clear 
( http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53805 ).

If defaults are ever reconsidered, my default flags include 
-frounding-math -fno-trapping-math.


2012-06-10  Marc Glisse  <marc.glisse@inria.fr>

gcc/
 	PR tree-optimization/51938
 	* tree-ssa-ifcombine.c (ifcombine_ifandif): New parameter for
 	inverted outer condition.
 	(ifcombine_iforif): Likewise.
 	(tree_ssa_ifcombine_bb): Update calls to the above. Detect !a&&b
 	and !a||b patterns.

gcc/testsuite/
 	PR tree-optimization/51938
 	* gcc.dg/tree-ssa/ssa-ifcombine-8.c: New testcase.
 	* gcc.dg/tree-ssa/ssa-ifcombine-9.c: New testcase.
Richard Guenther - July 24, 2012, 8:44 a.m.
On Mon, Jul 23, 2012 at 10:58 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Wed, 20 Jun 2012, Richard Guenther wrote:
>
>> On Sun, Jun 10, 2012 at 4:16 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>>
>>> Hello,
>>>
>>> currently, tree-ssa-ifcombine handles pairs of imbricated "if"s that
>>> share
>>> the same then branch, or the same else branch. There is no particular
>>> reason
>>> why it couldn't also handle the case where the then branch of one is the
>>> else branch of the other, which is what I do here.
>>>
>>> Any comments?
>>
>>
>> The general idea looks good, but I think the patch is too invasive.  As
>> far
>> as I can see the only callers with a non-zero 'inv' argument come from
>> ifcombine_ifnotorif and ifcombine_ifnotandif (and both with inv == 2).
>> I would rather see a more localized patch that makes use of
>> invert_tree_comparison to perform the inversion on the call arguments
>> of maybe_fold_and/or_comparisons.
>
>
> Hello,
>
> I finally went back to this version (which is where I started from, as shown
> in the PR). It is not very satisfying because:
>
> * some bit tests could also be optimized (more generally, grouping a&&b and
> !a&&b on one side and a||b and !a||b on the other side is rather arbitrary),
>
> * -ftrapping-math makes it useless for floating point,
>
> but I guess it is better than nothing. Handling traps correctly is
> complicated because the current code is already a bit bogus (see
> http://gcc.gnu.org/ml/gcc-patches/2012-07/msg00924.html for an example), and
> even the definition of -ftrapping-math is not clear (
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53805 ).
>
> If defaults are ever reconsidered, my default flags include -frounding-math
> -fno-trapping-math.
>

This patch is ok if bootstrapped / regtested properly.

Thanks,
Richard.

>
> 2012-06-10  Marc Glisse  <marc.glisse@inria.fr>
>
> gcc/
>         PR tree-optimization/51938
>         * tree-ssa-ifcombine.c (ifcombine_ifandif): New parameter for
>         inverted outer condition.
>         (ifcombine_iforif): Likewise.
>         (tree_ssa_ifcombine_bb): Update calls to the above. Detect !a&&b
>         and !a||b patterns.
>
>
> gcc/testsuite/
>         PR tree-optimization/51938
>         * gcc.dg/tree-ssa/ssa-ifcombine-8.c: New testcase.
>         * gcc.dg/tree-ssa/ssa-ifcombine-9.c: New testcase.
>
> --
> Marc Glisse
Marc Glisse - July 24, 2012, 8:53 a.m.
On Tue, 24 Jul 2012, Richard Guenther wrote:

> On Mon, Jul 23, 2012 at 10:58 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> On Wed, 20 Jun 2012, Richard Guenther wrote:
>>
>>> On Sun, Jun 10, 2012 at 4:16 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>>>
>>>> Hello,
>>>>
>>>> currently, tree-ssa-ifcombine handles pairs of imbricated "if"s that
>>>> share
>>>> the same then branch, or the same else branch. There is no particular
>>>> reason
>>>> why it couldn't also handle the case where the then branch of one is the
>>>> else branch of the other, which is what I do here.
>>>>
>>>> Any comments?
>>>
>>>
>>> The general idea looks good, but I think the patch is too invasive.  As
>>> far
>>> as I can see the only callers with a non-zero 'inv' argument come from
>>> ifcombine_ifnotorif and ifcombine_ifnotandif (and both with inv == 2).
>>> I would rather see a more localized patch that makes use of
>>> invert_tree_comparison to perform the inversion on the call arguments
>>> of maybe_fold_and/or_comparisons.
>>
>>
>> Hello,
>>
>> I finally went back to this version (which is where I started from, as shown
>> in the PR). It is not very satisfying because:
>>
>> * some bit tests could also be optimized (more generally, grouping a&&b and
>> !a&&b on one side and a||b and !a||b on the other side is rather arbitrary),
>>
>> * -ftrapping-math makes it useless for floating point,
>>
>> but I guess it is better than nothing. Handling traps correctly is
>> complicated because the current code is already a bit bogus (see
>> http://gcc.gnu.org/ml/gcc-patches/2012-07/msg00924.html for an example), and
>> even the definition of -ftrapping-math is not clear (
>> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53805 ).
>>
>> If defaults are ever reconsidered, my default flags include -frounding-math
>> -fno-trapping-math.
>>
>
> This patch is ok if bootstrapped / regtested properly.

Thanks. And sorry for forgetting to mention it was bootstrapped and 
regtested.

Note that Andrew Pinski posted a patch:
http://gcc.gnu.org/ml/gcc-patches/2012-07/msg01167.html

which does something quite similar, so I will wait a bit before committing 
anything.

Patch

Index: tree-ssa-ifcombine.c

===================================================================
--- tree-ssa-ifcombine.c	(revision 189779)

+++ tree-ssa-ifcombine.c	(working copy)

@@ -288,45 +288,48 @@  recognize_bits_test (gimple cond, tree *

       || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
     return false;
 
   *name = get_name_for_bit_test (gimple_assign_rhs1 (stmt));
   *bits = gimple_assign_rhs2 (stmt);
 
   return true;
 }
 
 /* If-convert on a and pattern with a common else block.  The inner
-   if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.

+   if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB,

+   negated if outer_inv is true.

    Returns true if the edges to the common else basic-block were merged.  */
 
 static bool
-ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)

+ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb,

+		   bool outer_inv)

 {
   gimple_stmt_iterator gsi;
   gimple inner_cond, outer_cond;
   tree name1, name2, bit1, bit2;
 
   inner_cond = last_stmt (inner_cond_bb);
   if (!inner_cond
       || gimple_code (inner_cond) != GIMPLE_COND)
     return false;
 
   outer_cond = last_stmt (outer_cond_bb);
   if (!outer_cond
       || gimple_code (outer_cond) != GIMPLE_COND)
     return false;
 
   /* See if we test a single bit of the same name in both tests.  In
      that case remove the outer test, merging both else edges,
      and change the inner one to test for
      name & (bit1 | bit2) == (bit1 | bit2).  */
-  if (recognize_single_bit_test (inner_cond, &name1, &bit1)

+  if (!outer_inv

+      && recognize_single_bit_test (inner_cond, &name1, &bit1)

       && recognize_single_bit_test (outer_cond, &name2, &bit2)
       && name1 == name2)
     {
       tree t, t2;
 
       /* Do it.  */
       gsi = gsi_for_stmt (inner_cond);
       t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 		       build_int_cst (TREE_TYPE (name1), 1), bit1);
       t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
@@ -360,76 +363,86 @@  ifcombine_ifandif (basic_block inner_con

 	}
 
       return true;
     }
 
   /* See if we have two comparisons that we can merge into one.  */
   else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
 	   && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
     {
       tree t;
+      enum tree_code outer_cond_code = gimple_cond_code (outer_cond);

+      if (outer_inv)

+	outer_cond_code = invert_tree_comparison (outer_cond_code,

+	  HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond)))));

+      if (outer_cond_code == ERROR_MARK)

+	return false;

 
       if (!(t = maybe_fold_and_comparisons (gimple_cond_code (inner_cond),
 					    gimple_cond_lhs (inner_cond),
 					    gimple_cond_rhs (inner_cond),
-					    gimple_cond_code (outer_cond),

+					    outer_cond_code,

 					    gimple_cond_lhs (outer_cond),
 					    gimple_cond_rhs (outer_cond))))
 	return false;
       t = canonicalize_cond_expr_cond (t);
       if (!t)
 	return false;
       gimple_cond_set_condition_from_tree (inner_cond, t);
       update_stmt (inner_cond);
 
       /* Leave CFG optimization to cfg_cleanup.  */
-      gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);

+      gimple_cond_set_condition_from_tree (outer_cond,

+	outer_inv ? boolean_false_node : boolean_true_node);

       update_stmt (outer_cond);
 
       if (dump_file)
 	{
 	  fprintf (dump_file, "optimizing two comparisons to ");
 	  print_generic_expr (dump_file, t, 0);
 	  fprintf (dump_file, "\n");
 	}
 
       return true;
     }
 
   return false;
 }
 
 /* If-convert on a or pattern with a common then block.  The inner
-   if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.

+   if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB,

+   negated if outer_inv is true.

    Returns true, if the edges leading to the common then basic-block
    were merged.  */
 
 static bool
-ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)

+ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb,

+		  bool outer_inv)

 {
   gimple inner_cond, outer_cond;
   tree name1, name2, bits1, bits2;
 
   inner_cond = last_stmt (inner_cond_bb);
   if (!inner_cond
       || gimple_code (inner_cond) != GIMPLE_COND)
     return false;
 
   outer_cond = last_stmt (outer_cond_bb);
   if (!outer_cond
       || gimple_code (outer_cond) != GIMPLE_COND)
     return false;
 
   /* See if we have two bit tests of the same name in both tests.
      In that case remove the outer test and change the inner one to
      test for name & (bits1 | bits2) != 0.  */
-  if (recognize_bits_test (inner_cond, &name1, &bits1)

+  if (!outer_inv

+      && recognize_bits_test (inner_cond, &name1, &bits1)

       && recognize_bits_test (outer_cond, &name2, &bits2))
     {
       gimple_stmt_iterator gsi;
       tree t;
 
       /* Find the common name which is bit-tested.  */
       if (name1 == name2)
 	;
       else if (bits1 == bits2)
 	{
@@ -508,36 +521,43 @@  ifcombine_iforif (basic_block inner_cond

       return true;
     }
 
   /* See if we have two comparisons that we can merge into one.
      This happens for C++ operator overloading where for example
      GE_EXPR is implemented as GT_EXPR || EQ_EXPR.  */
     else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
 	   && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
     {
       tree t;
+      enum tree_code outer_cond_code = gimple_cond_code (outer_cond);

+      if (outer_inv)

+	outer_cond_code = invert_tree_comparison (outer_cond_code,

+	  HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond)))));

+      if (outer_cond_code == ERROR_MARK)

+	return false;

 
       if (!(t = maybe_fold_or_comparisons (gimple_cond_code (inner_cond),
 					   gimple_cond_lhs (inner_cond),
 					   gimple_cond_rhs (inner_cond),
-					   gimple_cond_code (outer_cond),

+					   outer_cond_code,

 					   gimple_cond_lhs (outer_cond),
 					   gimple_cond_rhs (outer_cond))))
 	return false;
       t = canonicalize_cond_expr_cond (t);
       if (!t)
 	return false;
       gimple_cond_set_condition_from_tree (inner_cond, t);
       update_stmt (inner_cond);
 
       /* Leave CFG optimization to cfg_cleanup.  */
-      gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);

+      gimple_cond_set_condition_from_tree (outer_cond,

+	outer_inv ? boolean_true_node : boolean_false_node);

       update_stmt (outer_cond);
 
       if (dump_file)
 	{
 	  fprintf (dump_file, "optimizing two comparisons to ");
 	  print_generic_expr (dump_file, t, 0);
 	  fprintf (dump_file, "\n");
 	}
 
       return true;
@@ -580,40 +600,73 @@  tree_ssa_ifcombine_bb (basic_block inner

 	{
 	  /* We have
 	       <outer_cond_bb>
 		 if (q) goto inner_cond_bb; else goto else_bb;
 	       <inner_cond_bb>
 		 if (p) goto ...; else goto else_bb;
 		 ...
 	       <else_bb>
 		 ...
 	   */
-	  return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);

+	  return ifcombine_ifandif (inner_cond_bb, outer_cond_bb, false);

+	}

+

+      /* And a version where the outer condition is negated.  */

+      if (recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)

+	  && same_phi_args_p (outer_cond_bb, inner_cond_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 (p) goto ...; else goto else_bb;

+		 ...

+	       <else_bb>

+		 ...

+	   */

+	  return ifcombine_ifandif (inner_cond_bb, outer_cond_bb, true);

 	}
 
       /* The || form is characterized by a common then_bb with the
 	 two edges leading to it mergable.  The latter is guaranteed
          by matching PHI arguments in the then_bb and the inner cond_bb
 	 having no side-effects.  */
       if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
 	  && same_phi_args_p (outer_cond_bb, inner_cond_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 (q) goto then_bb; else goto ...;
 	       <then_bb>
 		 ...
 	   */
-	  return ifcombine_iforif (inner_cond_bb, outer_cond_bb);

+	  return ifcombine_iforif (inner_cond_bb, outer_cond_bb, false);

+	}

+

+      /* And a version where the outer condition is negated.  */

+      if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)

+	  && same_phi_args_p (outer_cond_bb, inner_cond_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 (q) goto then_bb; else goto ...;

+	       <then_bb>

+		 ...

+	   */

+	  return ifcombine_iforif (inner_cond_bb, outer_cond_bb, true);

 	}
     }
 
   return false;
 }
 
 /* Main entry for the tree if-conversion pass.  */
 
 static unsigned int
 tree_ssa_ifcombine (void)
Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c

===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c	(revision 0)

+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c	(revision 0)

@@ -0,0 +1,22 @@ 

+/* { dg-do compile } */

+/* { dg-options "-O2 -fno-trapping-math -fdump-tree-ifcombine" } */

+

+void f ();

+enum Sign { NEG=-1, ZERO, POS };

+

+static inline enum Sign sign (double x)

+{

+  if (x > 0) return POS;

+  if (x < 0) return NEG;

+  return ZERO;

+}

+void g (double x)

+{

+  if (sign (x) == NEG) f();

+}

+

+/* The above should be optimized to x < 0 by ifcombine.

+   The transformation would also be legal with -ftrapping-math.  */

+

+/* { dg-final { scan-tree-dump "optimizing.* < " "ifcombine" } } */

+/* { dg-final { cleanup-tree-dump "ifcombine" } } */


Property changes on: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
___________________________________________________________________
Added: svn:keywords
   + Author Date Id Revision URL
Added: svn:eol-style
   + native

Index: testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c

===================================================================
--- testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c	(revision 0)

+++ testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c	(revision 0)

@@ -0,0 +1,25 @@ 

+/* { dg-do compile } */

+/* { dg-options "-O -fno-trapping-math -fdump-tree-ifcombine" } */

+

+double test1 (double i, double j)

+{

+  if (i >= j)

+    if (i <= j)

+      goto plif;

+    else

+      goto plouf;

+  else

+    goto plif;

+

+plif:

+  return 0;

+plouf:

+  return -1;

+}

+

+/* The above should be optimized to a i > j test by ifcombine.

+   The transformation would also be legal with -ftrapping-math.

+   Instead we get u<=, which is acceptable with -fno-trapping-math.  */

+

+/* { dg-final { scan-tree-dump " u<= " "ifcombine" } } */

+/* { dg-final { cleanup-tree-dump "ifcombine" } } */