Patchwork Fix CDDCE miscompilation (PR tree-optimization/55018)

login
register
mail settings
Submitter Jakub Jelinek
Date Oct. 22, 2012, 9:09 p.m.
Message ID <20121022210936.GJ1752@tucnak.redhat.com>
Download mbox | patch
Permalink /patch/193289/
State New
Headers show

Comments

Jakub Jelinek - Oct. 22, 2012, 9:09 p.m.
On Mon, Oct 22, 2012 at 10:51:43PM +0200, Steven Bosscher wrote:
> On Mon, Oct 22, 2012 at 10:39 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> > dominance.c doesn't use cfgloop.h (can it?  Isn't it used before loops are
> > computed, perhaps after loops destroyed, etc.), so there is no guarantee
> > that loop->latch of endless loop will have the fake edge added and no other
> > bb before it.  As 7 and 8 are bigger than 4 or 6, the above loop
> > starts with bb 8, finds that its predecessor has already been searched and
> > stops there, similarly for 7, then goes on with 6 with another fake edge to
> > exit.
> 
> At least it looks like some of the cfganal DFS code could be used in
> dominance.c. I will have a look.
> 
> A hack like the following should result in no fake edges for bb7 and bb8.

Wouldn't it be way cheaper to just export dfs_find_deadend from cfganal.c
and call it in calc_dfs_tree on each unconnected bb?
I.e. (untested with the exception of the testcase):

2012-10-22  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/55018
	* cfganal.c (dfs_find_deadend): No longer static.
	* basic-block.h (dfs_find_deadend): New prototype.
	* dominance.c (calc_dfs_tree): If saw_unconnected,
	traverse from dfs_find_deadend of unconnected b
	instead of b directly.

	* gcc.dg/torture/pr55018.c: New test.


	Jakub
Steven Bosscher - Oct. 22, 2012, 9:18 p.m.
On Mon, Oct 22, 2012 at 11:09 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Wouldn't it be way cheaper to just export dfs_find_deadend from cfganal.c
> and call it in calc_dfs_tree on each unconnected bb?
> I.e. (untested with the exception of the testcase):

Better yet, I have a patch in testing now to use cfganal's machinery
to compute the DFS forest.

Hold on a bit, I'll post it ASAP (probably Wednesday) if that's early
enough for you.
(Oh, and feel free to assign the PR to me ;-)

Ciao!
Steven
Steven Bosscher - Oct. 28, 2012, 6:33 p.m.
On Mon, Oct 22, 2012 at 11:09 PM, Jakub Jelinek wrote:
> On Mon, Oct 22, 2012 at 10:51:43PM +0200, Steven Bosscher wrote:
> Wouldn't it be way cheaper to just export dfs_find_deadend from cfganal.c
> and call it in calc_dfs_tree on each unconnected bb?
> I.e. (untested with the exception of the testcase):
>
> 2012-10-22  Jakub Jelinek  <jakub@redhat.com>
>
>         PR tree-optimization/55018
>         * cfganal.c (dfs_find_deadend): No longer static.
>         * basic-block.h (dfs_find_deadend): New prototype.
>         * dominance.c (calc_dfs_tree): If saw_unconnected,
>         traverse from dfs_find_deadend of unconnected b
>         instead of b directly.
>
>         * gcc.dg/torture/pr55018.c: New test.

I have no better solution than this for the moment. I thought there
was a common DFS machinery in cfganal.c but there are actually many of
them, but unfortunately all doing things slightly different. Something
for the cleanup list for GCC 4.9...

We should use dfs_find_deadend in flow_dfs_compute_reverse_execute
also. This results in fewer fake edges created in
connect_infinite_loops_to_exit, especially for loops with multiple
dead ends.

(BTW, connect_infinite_loops_to_exit also connects other
reverse-unreachable points in the CFG to EXIT, so that calling
add_noreturn_fake_exit_edges and connect_infinite_loops_to_exit is
doing a bit of duplicate work -- another thing for the cleanup
list...)

Attached patch was bootstrapped&tested on
{powerpc64,x86_64}-unknown-linux-gnu. OK?

Ciao!
Steven
Richard Guenther - Oct. 29, 2012, 2:06 p.m.
On Sun, Oct 28, 2012 at 7:33 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Mon, Oct 22, 2012 at 11:09 PM, Jakub Jelinek wrote:
>> On Mon, Oct 22, 2012 at 10:51:43PM +0200, Steven Bosscher wrote:
>> Wouldn't it be way cheaper to just export dfs_find_deadend from cfganal.c
>> and call it in calc_dfs_tree on each unconnected bb?
>> I.e. (untested with the exception of the testcase):
>>
>> 2012-10-22  Jakub Jelinek  <jakub@redhat.com>
>>
>>         PR tree-optimization/55018
>>         * cfganal.c (dfs_find_deadend): No longer static.
>>         * basic-block.h (dfs_find_deadend): New prototype.
>>         * dominance.c (calc_dfs_tree): If saw_unconnected,
>>         traverse from dfs_find_deadend of unconnected b
>>         instead of b directly.
>>
>>         * gcc.dg/torture/pr55018.c: New test.
>
> I have no better solution than this for the moment. I thought there
> was a common DFS machinery in cfganal.c but there are actually many of
> them, but unfortunately all doing things slightly different. Something
> for the cleanup list for GCC 4.9...
>
> We should use dfs_find_deadend in flow_dfs_compute_reverse_execute
> also. This results in fewer fake edges created in
> connect_infinite_loops_to_exit, especially for loops with multiple
> dead ends.
>
> (BTW, connect_infinite_loops_to_exit also connects other
> reverse-unreachable points in the CFG to EXIT, so that calling
> add_noreturn_fake_exit_edges and connect_infinite_loops_to_exit is
> doing a bit of duplicate work -- another thing for the cleanup
> list...)
>
> Attached patch was bootstrapped&tested on
> {powerpc64,x86_64}-unknown-linux-gnu. OK?

Ok.

Thanks,
Richard.

> Ciao!
> Steven
Jakub Jelinek - Nov. 1, 2012, 8:58 p.m.
On Thu, Nov 01, 2012 at 09:26:25PM +0100, Hans-Peter Nilsson wrote:
> > Attached patch was bootstrapped&tested on
> 
> gcc/
> 	PR tree-optimization/55018
> 	* basic-block.h (dfs_find_deadend): New prototype.
> 	* cfganal.c (dfs_find_deadend): No longer static.  Use bitmap
> 	instead of sbitmap for visited.
> 	(flow_dfs_compute_reverse_execute): Use dfs_find_deadend here, too.
> 	* dominance.c (calc_dfs_tree): If saw_unconnected,
> 	traverse from dfs_find_deadend of unconnected b
> 	instead of b directly.
> 
> It seems this caused PR55168, ICE.

As Honza said, it was likely latent, and furthermore seems to be related to
the flow_dfs_compute_reverse_execute change from Steven (mentioning it
primarily what should we consider backporting if anything to release
branches).

	Jakub
Jan Hubicka - Nov. 1, 2012, 9:28 p.m.
> On Thu, Nov 01, 2012 at 09:26:25PM +0100, Hans-Peter Nilsson wrote:
> > > Attached patch was bootstrapped&tested on
> > 
> > gcc/
> > 	PR tree-optimization/55018
> > 	* basic-block.h (dfs_find_deadend): New prototype.
> > 	* cfganal.c (dfs_find_deadend): No longer static.  Use bitmap
> > 	instead of sbitmap for visited.
> > 	(flow_dfs_compute_reverse_execute): Use dfs_find_deadend here, too.
> > 	* dominance.c (calc_dfs_tree): If saw_unconnected,
> > 	traverse from dfs_find_deadend of unconnected b
> > 	instead of b directly.
> > 
> > It seems this caused PR55168, ICE.
> 
> As Honza said, it was likely latent, and furthermore seems to be related to
> the flow_dfs_compute_reverse_execute change from Steven (mentioning it
> primarily what should we consider backporting if anything to release
> branches).

Indeed, this patch should not affect loop predictions.  Perhaps it prevents
CD-DCE from removing a loop that it previously removed and thus the loop survives
till predict.c and triggers the previously latent bugs?

The patch I attached to the PR is actually incorrect -
estimated_stmt_executions_int already adds the +1 and thus should never return
0.  I am looking into proper fix.   There is obvious overflow on the other
computation patch, so my best guess is that fixing it will cure the issue.

Honza
> 
> 	Jakub

Patch

--- gcc/cfganal.c.jj	2012-08-14 08:45:00.000000000 +0200
+++ gcc/cfganal.c	2012-10-22 23:04:29.620117666 +0200
@@ -593,7 +593,7 @@  post_order_compute (int *post_order, boo
    that all blocks in the region are reachable
    by starting an inverted traversal from the returned block.  */
 
-static basic_block
+basic_block
 dfs_find_deadend (basic_block bb)
 {
   sbitmap visited = sbitmap_alloc (last_basic_block);
--- gcc/basic-block.h.jj	2012-10-17 17:18:21.000000000 +0200
+++ gcc/basic-block.h	2012-10-17 17:18:21.000000000 +0200
@@ -787,6 +787,7 @@  extern void remove_fake_exit_edges (void
 extern void add_noreturn_fake_exit_edges (void);
 extern void connect_infinite_loops_to_exit (void);
 extern int post_order_compute (int *, bool, bool);
+extern basic_block dfs_find_deadend (basic_block);
 extern int inverted_post_order_compute (int *);
 extern int pre_and_rev_post_order_compute (int *, int *, bool);
 extern int dfs_enumerate_from (basic_block, int,
--- gcc/dominance.c.jj	2012-08-15 10:55:26.000000000 +0200
+++ gcc/dominance.c	2012-10-22 23:07:00.941220792 +0200
@@ -377,14 +377,18 @@  calc_dfs_tree (struct dom_info *di, bool
 	{
 	  FOR_EACH_BB_REVERSE (b)
 	    {
+	      basic_block b2;
 	      if (di->dfs_order[b->index])
 		continue;
-	      bitmap_set_bit (di->fake_exit_edge, b->index);
-	      di->dfs_order[b->index] = di->dfsnum;
-	      di->dfs_to_bb[di->dfsnum] = b;
+	      b2 = dfs_find_deadend (b);
+	      gcc_checking_assert (di->dfs_order[b2->index] == 0);
+	      bitmap_set_bit (di->fake_exit_edge, b2->index);
+	      di->dfs_order[b2->index] = di->dfsnum;
+	      di->dfs_to_bb[di->dfsnum] = b2;
 	      di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
 	      di->dfsnum++;
-	      calc_dfs_tree_nonrec (di, b, reverse);
+	      calc_dfs_tree_nonrec (di, b2, reverse);
+	      gcc_checking_assert (di->dfs_order[b->index]);
 	    }
 	}
     }
--- gcc/testsuite/gcc.dg/torture/pr55018.c.jj	2012-10-22 16:53:56.623083723 +0200
+++ gcc/testsuite/gcc.dg/torture/pr55018.c	2012-10-22 16:54:21.278934668 +0200
@@ -0,0 +1,22 @@ 
+/* PR tree-optimization/55018 */
+/* { dg-do compile } */
+/* { dg-options "-fdump-tree-optimized" } */
+
+void
+foo (int x)
+{
+  unsigned int a = 0;
+  int b = 3;
+  if (x)
+    b = 0;
+lab:
+  if (x)
+    goto lab;
+  a++;
+  if (b != 2)
+    __builtin_printf ("%u", a);
+  goto lab;
+}
+
+/* { dg-final { scan-tree-dump "printf" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */