Patchwork Improve ifcombine (PR 52005)

login
register
mail settings
Submitter Andrew Pinski
Date July 24, 2012, 5:40 a.m.
Message ID <CA+=Sn1m-fUff_=9T4T9iMkJ_CL-aWZnjXLgVo5F8Cagb_z6mRA@mail.gmail.com>
Download mbox | patch
Permalink /patch/172779/
State New
Headers show

Comments

Andrew Pinski - July 24, 2012, 5:40 a.m.
This patch improves ifcombine by doing two things.  First tries to see
if the then and else are swapped and handles that case.
Also it handles the case where the else or then cases have an empty
basic block instead of just fall through.

OK?  Bootstrapped and tested on x86_64-linux-gnu with no regressions.

Thanks,
Andrew Pinski

ChangeLog:
        * tree-ssa-ifcombine.c (recognize_if_then_else): Handle the case
        where the the then and else are swapped.
        (tree_ssa_ifcombine_bb): Handle the case were we have an empty
basic block
        for either then or else.

        * gcc.dg/tree-ssa/ssa-ifcombine-8.c: New testcase.
        * gcc.dg/tree-ssa/ssa-ifcombine-9.c: New testcase.
Marc Glisse - July 24, 2012, 8:25 a.m.
On Mon, 23 Jul 2012, Andrew Pinski wrote:

> This patch improves ifcombine by doing two things.  First tries to see
> if the then and else are swapped and handles that case.

Just a few hours after I posted:
http://gcc.gnu.org/ml/gcc-patches/2012-07/msg01160.html

Could you check that your patch works on my testcases? (and then we can 
add them to the testsuite and forget about my patch)
Richard Guenther - July 24, 2012, 9:37 a.m.
On Tue, Jul 24, 2012 at 10:25 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Mon, 23 Jul 2012, Andrew Pinski wrote:
>
>> This patch improves ifcombine by doing two things.  First tries to see
>> if the then and else are swapped and handles that case.
>
>
> Just a few hours after I posted:
> http://gcc.gnu.org/ml/gcc-patches/2012-07/msg01160.html
>
> Could you check that your patch works on my testcases? (and then we can add
> them to the testsuite and forget about my patch)

I must say I like Marcs patch more ...

Richard.

> --
> Marc Glisse
Andrew Pinski - July 24, 2012, 3:36 p.m.
On Tue, Jul 24, 2012 at 2:37 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Tue, Jul 24, 2012 at 10:25 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> On Mon, 23 Jul 2012, Andrew Pinski wrote:
>>
>>> This patch improves ifcombine by doing two things.  First tries to see
>>> if the then and else are swapped and handles that case.
>>
>>
>> Just a few hours after I posted:
>> http://gcc.gnu.org/ml/gcc-patches/2012-07/msg01160.html
>>
>> Could you check that your patch works on my testcases? (and then we can add
>> them to the testsuite and forget about my patch)
>
> I must say I like Marcs patch more ...

I agree it is better.  Though I don't have time to test my testcases
on your patch.

Thanks,
Andrew
Marc Glisse - July 24, 2012, 4:59 p.m.
On Tue, 24 Jul 2012, Andrew Pinski wrote:

> On Tue, Jul 24, 2012 at 2:37 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Tue, Jul 24, 2012 at 10:25 AM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>> On Mon, 23 Jul 2012, Andrew Pinski wrote:
>>>
>>>> This patch improves ifcombine by doing two things.  First tries to see
>>>> if the then and else are swapped and handles that case.
>>>
>>>
>>> Just a few hours after I posted:
>>> http://gcc.gnu.org/ml/gcc-patches/2012-07/msg01160.html
>>>
>>> Could you check that your patch works on my testcases? (and then we can add
>>> them to the testsuite and forget about my patch)
>>
>> I must say I like Marcs patch more ...
>
> I agree it is better.  Though I don't have time to test my testcases
> on your patch.

They won't work as is, because I just give up on bit tests in the inverted 
case. I guess replacing invert_tree_comparison with 
fold_build1(TRUTH_NOT_EXPR) at the beginning of the function might bring 
the patches closer (Andrew's patch seems to do more than mine, though I 
haven't studied it in details).

Patch

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,20 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -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" } } */
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,21 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+/* Testcase for PR31657.  */
+int g(void);
+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 = g();
+    else
+      t = 0;
+  return t;
+}
+
+/* { dg-final { scan-tree-dump "& 5" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: tree-ssa-ifcombine.c
===================================================================
--- tree-ssa-ifcombine.c	(revision 189800)
+++ tree-ssa-ifcombine.c	(working copy)
@@ -78,12 +78,34 @@  recognize_if_then_else (basic_block cond
     return false;
 
   /* Check if the edge destinations point to the required block.  */
-  if (*then_bb
-      && t->dest != *then_bb)
-    return false;
-  if (*else_bb
-      && e->dest != *else_bb)
-    return false;
+  if ((*then_bb
+       && t->dest != *then_bb)
+      || (*else_bb
+          && e->dest != *else_bb))
+    {
+      gimple stmt;
+      tree cond;
+      edge ee;
+      if ((*then_bb
+       	   && e->dest != *then_bb)
+          || (*else_bb
+	      && t->dest != *else_bb))
+	return false;
+      stmt = last_stmt (cond_bb);
+      cond = fold_build2 (gimple_cond_code (stmt), boolean_type_node,
+			  gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
+      cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
+      /* The opposite of the condition does not reduce so we cannot flip around the condition. */
+      if (!is_gimple_condexpr (cond))
+	return false;
+      e->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
+      t->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
+      gimple_cond_set_condition_from_tree (stmt, unshare_expr (cond));
+      update_stmt (stmt);
+      ee = e;
+      e = t;
+      t = ee;
+    }
 
   if (!*then_bb)
     *then_bb = t->dest;
@@ -590,6 +612,29 @@  tree_ssa_ifcombine_bb (basic_block inner
 	  return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
 	}
 
+      /* The && form is characterized by a common else_bb with
+	 the two edges leading to it mergable.  The latter is
+	 guaranteed by matching PHI arguments in the else_bb and
+	 the inner cond_bb having no side-effects.  */
+      if (empty_block_p (else_bb)
+	  && single_succ_p (else_bb)
+	  && single_succ_edge (else_bb)->dest == then_bb
+	  && 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 else_bb;
+	       <inner_cond_bb>
+		 if (p) goto ...; else goto else_bb;
+		 ...
+	       <else_bb>
+		 ...
+	   */
+	  return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
+	}
+
       /* 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
@@ -599,6 +644,27 @@  tree_ssa_ifcombine_bb (basic_block inner
 	  && 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);
+	}
+      /* 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 (empty_block_p (then_bb)
+	  && single_succ_p (then_bb)
+	  && single_succ_edge (then_bb)->dest == else_bb
+	  && 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 then_bb; else goto inner_cond_bb;
 	       <inner_cond_bb>