Patchwork Tree tail merging breaks __builtin_unreachable optimization

login
register
mail settings
Submitter Tom de Vries
Date July 6, 2012, 4:36 p.m.
Message ID <4FF71421.3050704@mentor.com>
Download mbox | patch
Permalink /patch/169492/
State New
Headers show

Comments

Tom de Vries - July 6, 2012, 4:36 p.m.
On 06/07/12 13:01, Richard Guenther wrote:
> On Thu, Jul 5, 2012 at 8:45 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> On 05/07/12 15:30, Michael Matz wrote:
>>> Hi,
>>>
>>> On Thu, 5 Jul 2012, Tom de Vries wrote:
>>>
>>>> The asserts allow the return result to be optimized, but not the cfg
>>>> conditions.
>>>>
>>>> AFAIU, we can insert the asserts earlier. F.i., we can insert
>>>>   aD.1711_6 = ASSERT_EXPR <aD.1711_1(D), aD.1711_1(D) > 0>
>>>> before the GIMPLE_COND in bb2.
>>>
>>> Nope.  That would require some more checks, in particular that the BB
>>> containing builtin_unreachable doesn't contain any other side-effects.
>>> Given this:
>>>
>>> if (i < 0)
>>>   { do_something_interesting();
>>>     __builtin_unreachable();
>>>   }
>>>
>>> moving the assert before the if would remove the if condition, hence
>>> the call to do_something_interesting.  You need to retain side-effects if
>>> there are any.
>>>
>>
>> Michael,
>>
>> Thanks for pointing that out.
>>
>> I tried a first stab at your suggestion of implementing the optimization in
>> pass_fold_builtins, it works for the test-case.
> 
> +static bool
> +optimize_unreachable (gimple_stmt_iterator i)
> +{
> +  gimple stmt;
> +  basic_block bb;
> +  edge_iterator ei;
> +  edge e;
> +
> +  for (gsi_prev (&i); !gsi_end_p (i); gsi_prev (&i))
> +    {
> +      stmt = gsi_stmt (i);
> +      if (gimple_has_side_effects (stmt))
> +       return false;
> +    }
> 
> I think we should rely on DCE to remove stmts without side-effects before
> __builtin_unreachable.  Thus I'd make this
> 
>   basic_block bb = gsi_bb (i);
>   for (gsi = gsi_start (bb); !gsi_end_p (i); gsi_next (&gsi))
>     {
>       if (is_gimple_debug ())
>        continue;
>       if (gimple_code () == GIMPLE_LABEL)
>         /* Verify we do not need to preserve the label.  */;
>       if (gsi_stmt () != gsi_stmt (i))
>         return false;
>     }
> 
>   ...
> 
> thus simply require the builtin be the first statement in the block.

Done.

> 
> As for the label I'm concerned about
> 
> void foo (int b, int c)
> {
>   void *x = &&lab;
>   if (b)
>     {
> lab:
>       __builtin_unreachable ();
>     }
> lab2:
>   if (c)
>     x = &&lab2;
>   goto *x;
> }
> 
> non-sensical, of course, but "valid".
> 

Added this example as test-case.

Bootstrapped and reg-tested (ada inclusive) on x86_64.

OK for trunk?

Thanks,
- Tom


2012-07-06  Tom de Vries  <tom@codesourcery.com>
	    Richard Guenther  <rguenther@suse.de>

	* tree-ssa-ccp.c (optimize_unreachable): New function.
	(execute_fold_all_builtins): Use optimize_unreachable to optimize
	BUILT_IN_UNREACHABLE.  Don't optimize after BUILT_IN_UNREACHABLE.

	* gcc.dg/builtin-unreachable-6.c: New test.
	* gcc.dg/builtin-unreachable-5.c: New test.
Richard Guenther - July 9, 2012, 8:10 a.m.
On Fri, Jul 6, 2012 at 6:36 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 06/07/12 13:01, Richard Guenther wrote:
>> On Thu, Jul 5, 2012 at 8:45 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>> On 05/07/12 15:30, Michael Matz wrote:
>>>> Hi,
>>>>
>>>> On Thu, 5 Jul 2012, Tom de Vries wrote:
>>>>
>>>>> The asserts allow the return result to be optimized, but not the cfg
>>>>> conditions.
>>>>>
>>>>> AFAIU, we can insert the asserts earlier. F.i., we can insert
>>>>>   aD.1711_6 = ASSERT_EXPR <aD.1711_1(D), aD.1711_1(D) > 0>
>>>>> before the GIMPLE_COND in bb2.
>>>>
>>>> Nope.  That would require some more checks, in particular that the BB
>>>> containing builtin_unreachable doesn't contain any other side-effects.
>>>> Given this:
>>>>
>>>> if (i < 0)
>>>>   { do_something_interesting();
>>>>     __builtin_unreachable();
>>>>   }
>>>>
>>>> moving the assert before the if would remove the if condition, hence
>>>> the call to do_something_interesting.  You need to retain side-effects if
>>>> there are any.
>>>>
>>>
>>> Michael,
>>>
>>> Thanks for pointing that out.
>>>
>>> I tried a first stab at your suggestion of implementing the optimization in
>>> pass_fold_builtins, it works for the test-case.
>>
>> +static bool
>> +optimize_unreachable (gimple_stmt_iterator i)
>> +{
>> +  gimple stmt;
>> +  basic_block bb;
>> +  edge_iterator ei;
>> +  edge e;
>> +
>> +  for (gsi_prev (&i); !gsi_end_p (i); gsi_prev (&i))
>> +    {
>> +      stmt = gsi_stmt (i);
>> +      if (gimple_has_side_effects (stmt))
>> +       return false;
>> +    }
>>
>> I think we should rely on DCE to remove stmts without side-effects before
>> __builtin_unreachable.  Thus I'd make this
>>
>>   basic_block bb = gsi_bb (i);
>>   for (gsi = gsi_start (bb); !gsi_end_p (i); gsi_next (&gsi))
>>     {
>>       if (is_gimple_debug ())
>>        continue;
>>       if (gimple_code () == GIMPLE_LABEL)
>>         /* Verify we do not need to preserve the label.  */;
>>       if (gsi_stmt () != gsi_stmt (i))
>>         return false;
>>     }
>>
>>   ...
>>
>> thus simply require the builtin be the first statement in the block.
>
> Done.
>
>>
>> As for the label I'm concerned about
>>
>> void foo (int b, int c)
>> {
>>   void *x = &&lab;
>>   if (b)
>>     {
>> lab:
>>       __builtin_unreachable ();
>>     }
>> lab2:
>>   if (c)
>>     x = &&lab2;
>>   goto *x;
>> }
>>
>> non-sensical, of course, but "valid".
>>
>
> Added this example as test-case.
>
> Bootstrapped and reg-tested (ada inclusive) on x86_64.
>
> OK for trunk?

Ok.
Thanks,
Richard.

> Thanks,
> - Tom
>
>
> 2012-07-06  Tom de Vries  <tom@codesourcery.com>
>             Richard Guenther  <rguenther@suse.de>
>
>         * tree-ssa-ccp.c (optimize_unreachable): New function.
>         (execute_fold_all_builtins): Use optimize_unreachable to optimize
>         BUILT_IN_UNREACHABLE.  Don't optimize after BUILT_IN_UNREACHABLE.
>
>         * gcc.dg/builtin-unreachable-6.c: New test.
>         * gcc.dg/builtin-unreachable-5.c: New test.
Richard Guenther - July 16, 2012, 2:11 p.m.
On Mon, Jul 16, 2012 at 3:55 PM, Ulrich Weigand <uweigand@de.ibm.com> wrote:
> Richard Guenther wrote:
>> On Fri, Jul 6, 2012 at 6:36 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> > Bootstrapped and reg-tested (ada inclusive) on x86_64.
>> >
>> > OK for trunk?
>>
>> Ok.
>> Thanks,
>> Richard.
>>
>> > 2012-07-06  Tom de Vries  <tom@codesourcery.com>
>> >             Richard Guenther  <rguenther@suse.de>
>> >
>> >         * tree-ssa-ccp.c (optimize_unreachable): New function.
>> >         (execute_fold_all_builtins): Use optimize_unreachable to optimize
>> >         BUILT_IN_UNREACHABLE.  Don't optimize after BUILT_IN_UNREACHABLE.
>> >
>> >         * gcc.dg/builtin-unreachable-6.c: New test.
>> >         * gcc.dg/builtin-unreachable-5.c: New test.
>
>
> When attempting to backport this patch to our 4.7 branch, I ran into
> segmentation faults.  It turns out that at least in 4.7, gsi_stmt
> crashes when passed an empty gsi (for which gsi_end_p is true);
> on mainline, gsi_stmt simply returns NULL instead.
>
> Now I understand that even on mainline, we're still supposed to check
> gsi_end_p before calling gsi_stmt.  The patch below updates
> tree-ssa-ccp.c:optimize_unreachable to do that.  In the backport
> this fixes the crashes.
>
> This doesn't really have any effect on behaviour on mainline.  Should
> it be installed anyway?

Yes please.

> (Tested on mainline on i386-linux with no regressions.)
>
> In addition, I was wondering whether we should backport Tom's patch
> (including the fix below) to the FSF 4.7 branch: it does fix a
> (performance) regression, in the sense that the original testcase
> calling __builtin_unreachable multiple times was optimized well
> until 4.6, and is now again optimized well on mainline, but it
> generates quite bad code on 4.7 at the moment ...

I'm not sure.

Thanks,
Richard.

> Bye,
> Ulrich
>
>
> ChangeLog:
>
>         * tree-ssa-ccp.c (optimize_unreachable): Check gsi_end_p
>         before calling gsi_stmt.
>
> Index: gcc/tree-ssa-ccp.c
> ===================================================================
> *** gcc/tree-ssa-ccp.c  (revision 189459)
> --- gcc/tree-ssa-ccp.c  (working copy)
> *************** optimize_unreachable (gimple_stmt_iterat
> *** 2358,2366 ****
>     FOR_EACH_EDGE (e, ei, bb->preds)
>       {
>         gsi = gsi_last_bb (e->src);
> !       stmt = gsi_stmt (gsi);
>
> !       if (stmt && gimple_code (stmt) == GIMPLE_COND)
>         {
>           if (e->flags & EDGE_TRUE_VALUE)
>             gimple_cond_make_false (stmt);
> --- 2358,2368 ----
>     FOR_EACH_EDGE (e, ei, bb->preds)
>       {
>         gsi = gsi_last_bb (e->src);
> !       if (gsi_end_p (gsi))
> !       continue;
>
> !       stmt = gsi_stmt (gsi);
> !       if (gimple_code (stmt) == GIMPLE_COND)
>         {
>           if (e->flags & EDGE_TRUE_VALUE)
>             gimple_cond_make_false (stmt);
>
>
> --
>   Dr. Ulrich Weigand
>   GNU Toolchain for Linux on System z and Cell BE
>   Ulrich.Weigand@de.ibm.com
>

Patch

Index: gcc/tree-ssa-ccp.c
===================================================================
--- gcc/tree-ssa-ccp.c (revision 189007)
+++ gcc/tree-ssa-ccp.c (working copy)
@@ -2318,6 +2318,69 @@  optimize_stdarg_builtin (gimple call)
     }
 }
 
+/* Attemp to make the block of __builtin_unreachable I unreachable by changing
+   the incoming jumps.  Return true if at least one jump was changed.  */
+
+static bool
+optimize_unreachable (gimple_stmt_iterator i)
+{
+  basic_block bb = gsi_bb (i);
+  gimple_stmt_iterator gsi;
+  gimple stmt;
+  edge_iterator ei;
+  edge e;
+  bool ret;
+
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      stmt = gsi_stmt (gsi);
+
+      if (is_gimple_debug (stmt))
+       continue;
+
+      if (gimple_code (stmt) == GIMPLE_LABEL)
+	{
+	  /* Verify we do not need to preserve the label.  */
+	  if (FORCED_LABEL (gimple_label_label (stmt)))
+	    return false;
+
+	  continue;
+	}
+
+      /* Only handle the case that __builtin_unreachable is the first statement
+	 in the block.  We rely on DCE to remove stmts without side-effects
+	 before __builtin_unreachable.  */
+      if (gsi_stmt (gsi) != gsi_stmt (i))
+        return false;
+    }
+
+  ret = false;
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      gsi = gsi_last_bb (e->src);
+      stmt = gsi_stmt (gsi);
+
+      if (stmt && gimple_code (stmt) == GIMPLE_COND)
+	{
+	  if (e->flags & EDGE_TRUE_VALUE)
+	    gimple_cond_make_false (stmt);
+	  else if (e->flags & EDGE_FALSE_VALUE)
+	    gimple_cond_make_true (stmt);
+	  else
+	    gcc_unreachable ();
+	}
+      else
+	{
+	  /* Todo: handle other cases, f.i. switch statement.  */
+	  continue;
+	}
+
+      ret = true;
+    }
+
+  return ret;
+}
+
 /* A simple pass that attempts to fold all builtin functions.  This pass
    is run after we've propagated as many constants as we can.  */
 
@@ -2379,6 +2442,11 @@  execute_fold_all_builtins (void)
 		gsi_next (&i);
 		continue;
 
+	      case BUILT_IN_UNREACHABLE:
+		if (optimize_unreachable (i))
+		  cfg_changed = true;
+		break;
+
 	      case BUILT_IN_VA_START:
 	      case BUILT_IN_VA_END:
 	      case BUILT_IN_VA_COPY:
@@ -2393,6 +2461,9 @@  execute_fold_all_builtins (void)
 		continue;
 	      }
 
+	  if (result == NULL_TREE)
+	    break;
+
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    {
 	      fprintf (dump_file, "Simplified\n  ");
Index: gcc/testsuite/gcc.dg/builtin-unreachable-6.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/builtin-unreachable-6.c (revision 0)
@@ -0,0 +1,21 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fab" } */
+
+void
+foo (int b, int c)
+{
+  void *x = &&lab;
+  if (b)
+    {
+lab:
+      __builtin_unreachable ();
+    }
+lab2:
+  if (c)
+    x = &&lab2;
+  goto *x;
+}
+
+/* { dg-final { scan-tree-dump-times "lab:" 1 "fab" } } */
+/* { dg-final { scan-tree-dump-times "__builtin_unreachable" 1 "fab" } } */
+/* { dg-final { cleanup-tree-dump "fab" } } */
Index: gcc/testsuite/gcc.dg/builtin-unreachable-5.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/builtin-unreachable-5.c (revision 0)
@@ -0,0 +1,23 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-fab" } */
+
+int
+foo (int a)
+{
+  if (a <= 0)
+    {
+    L1:
+      __builtin_unreachable ();
+    }
+
+  if (a > 2)
+    goto L1;
+
+  return a > 0;
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(" 0 "fab" } } */
+/* { dg-final { scan-tree-dump-times "goto" 0 "fab" } } */
+/* { dg-final { scan-tree-dump-times "L1:" 0 "fab" } } */
+/* { dg-final { scan-tree-dump-times "__builtin_unreachable" 0 "fab" } } */
+/* { dg-final { cleanup-tree-dump "fab" } } */