[PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Jakub Jelinek]

Hi!

On the following testcase we have two endless loops before cddce2:

Sender_signal (int Connect)
{
  int State;
  unsigned int occurrence;

  <bb 2>:
  if (Connect_6(D) != 0)
    goto <bb 8>;
  else
    goto <bb 7>;

  <bb 3>:
  # occurrence_8 = PHI <0(7), occurrence_12(4)>
  occurrence_12 = occurrence_8 + 1;
  __builtin_printf ("Sender_Signal occurrence %u\n", occurrence_12);

  <bb 4>:
  goto <bb 3>;

  <bb 5>:

  <bb 6>:
  goto <bb 5>;

  <bb 7>:
  goto <bb 3>;

  <bb 8>:
  goto <bb 5>;

}

The problem are the two empty bbs on the path from the conditional
at the end of bb2 and the endless loops (i.e. bb7 and bb8).
In presence of infinite loops dominance.c adds fake edges to exit pretty
arbitrarily (it uses FOR_EACH_BB_REVERSE and for unconnected bbs
computes post-dominance and adds fake edges to exit), so with the above
testcases both bb7 and bb8 have exit block as immediate post-dominator,
so find_control_dependence stops at those bb's when starting from the
2->7 resp. 2->8 edges.  bb7/bb8 don't have a control stmt at the end,
so mark_last_stmt_necessary doesn't mark any stmt as necessary in them
and thus if (Connect_6(D) != 0) GIMPLE_COND is never marked as necessary
and the whole endless loop with printfs in it is removed.

The following patch fixes it by detecting such problematic blocks
and recursing on them in mark_control_dependence_edges_necessary.

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

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

	PR tree-optimization/55018
	* tree-ssa-dce.c (mark_last_stmt_necessary): Return bool whether
	mark_stmt_necessary was called.
	(mark_control_dependence_edges_necessary): Recurse on cd_bb if
	mark_last_stmt_necessary hasn't marked a control stmt, cd_bb
	has exit block as immediate dominator and a single succ edge.

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

--- gcc/tree-ssa-dce.c.jj	2012-08-15 10:55:33.000000000 +0200
+++ gcc/tree-ssa-dce.c	2012-10-22 16:50:03.011497546 +0200
@@ -381,7 +381,7 @@ mark_stmt_if_obviously_necessary (gimple
 
 /* Mark the last statement of BB as necessary.  */
 
-static void
+static bool
 mark_last_stmt_necessary (basic_block bb)
 {
   gimple stmt = last_stmt (bb);
@@ -391,7 +391,11 @@ mark_last_stmt_necessary (basic_block bb
 
   /* We actually mark the statement only if it is a control statement.  */
   if (stmt && is_ctrl_stmt (stmt))
-    mark_stmt_necessary (stmt, true);
+    {
+      mark_stmt_necessary (stmt, true);
+      return true;
+    }
+  return false;
 }
 
 
@@ -423,8 +427,18 @@ mark_control_dependent_edges_necessary (
 	  continue;
 	}
 
-      if (!TEST_BIT (last_stmt_necessary, cd_bb->index))
-	mark_last_stmt_necessary (cd_bb);
+      if (!TEST_BIT (last_stmt_necessary, cd_bb->index)
+	  && !mark_last_stmt_necessary (cd_bb))
+	{
+	  /* In presence of infinite loops, some bbs on a path
+	     to an infinite loop might not end with a control stmt,
+	     but due to a fake edge to exit stop find_control_dependence.
+	     Recurse for those.  */
+	  if (get_immediate_dominator (CDI_POST_DOMINATORS, cd_bb)
+	      == EXIT_BLOCK_PTR
+	      && single_succ_p (cd_bb))
+	    mark_control_dependent_edges_necessary (cd_bb, el, false);
+	}
     }
 
   if (!skipped)
--- 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" } } */

	Jakub

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Steven Bosscher]

On Mon, Oct 22, 2012 at 9:35 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> On the following testcase we have two endless loops before cddce2:
>
> Sender_signal (int Connect)
> {
>   int State;
>   unsigned int occurrence;
>
>   <bb 2>:
>   if (Connect_6(D) != 0)
>     goto <bb 8>;
>   else
>     goto <bb 7>;
>
>   <bb 3>:
>   # occurrence_8 = PHI <0(7), occurrence_12(4)>
>   occurrence_12 = occurrence_8 + 1;
>   __builtin_printf ("Sender_Signal occurrence %u\n", occurrence_12);
>
>   <bb 4>:
>   goto <bb 3>;
>
>   <bb 5>:
>
>   <bb 6>:
>   goto <bb 5>;
>
>   <bb 7>:
>   goto <bb 3>;
>
>   <bb 8>:
>   goto <bb 5>;
>
> }
>
> The problem are the two empty bbs on the path from the conditional
> at the end of bb2 and the endless loops (i.e. bb7 and bb8).
> In presence of infinite loops dominance.c adds fake edges to exit pretty
> arbitrarily (it uses FOR_EACH_BB_REVERSE and for unconnected bbs
> computes post-dominance and adds fake edges to exit), so with the above
> testcases both bb7 and bb8 have exit block as immediate post-dominator,
> so find_control_dependence stops at those bb's when starting from the
> 2->7 resp. 2->8 edges.  bb7/bb8 don't have a control stmt at the end,
> so mark_last_stmt_necessary doesn't mark any stmt as necessary in them
> and thus if (Connect_6(D) != 0) GIMPLE_COND is never marked as necessary
> and the whole endless loop with printfs in it is removed.

I'm not sure I'm following this alright, but AFAICT bb7 and bb8 are
control-dependent on the "if" in bb2. To preserve the infinite-loop
semantics the control parent of the infinite loop must be inherently
preserved (because empty infinite loops can't mark any feeding
statements). So shouldn't the code in find_obviously_necessary_stmts
that handles infinite loops mark the last statement of control parents
necessary?

Ciao!
Steven

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Jakub Jelinek]

On Mon, Oct 22, 2012 at 09:48:16PM +0200, Steven Bosscher wrote:
> On Mon, Oct 22, 2012 at 9:35 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> > On the following testcase we have two endless loops before cddce2:
> >
> > Sender_signal (int Connect)
> > {
> >   int State;
> >   unsigned int occurrence;
> >
> >   <bb 2>:
> >   if (Connect_6(D) != 0)
> >     goto <bb 8>;
> >   else
> >     goto <bb 7>;
> >
> >   <bb 3>:
> >   # occurrence_8 = PHI <0(7), occurrence_12(4)>
> >   occurrence_12 = occurrence_8 + 1;
> >   __builtin_printf ("Sender_Signal occurrence %u\n", occurrence_12);
> >
> >   <bb 4>:
> >   goto <bb 3>;
> >
> >   <bb 5>:
> >
> >   <bb 6>:
> >   goto <bb 5>;
> >
> >   <bb 7>:
> >   goto <bb 3>;
> >
> >   <bb 8>:
> >   goto <bb 5>;
> >
> > }
> >
> > The problem are the two empty bbs on the path from the conditional
> > at the end of bb2 and the endless loops (i.e. bb7 and bb8).
> > In presence of infinite loops dominance.c adds fake edges to exit pretty
> > arbitrarily (it uses FOR_EACH_BB_REVERSE and for unconnected bbs
> > computes post-dominance and adds fake edges to exit), so with the above
> > testcases both bb7 and bb8 have exit block as immediate post-dominator,
> > so find_control_dependence stops at those bb's when starting from the
> > 2->7 resp. 2->8 edges.  bb7/bb8 don't have a control stmt at the end,
> > so mark_last_stmt_necessary doesn't mark any stmt as necessary in them
> > and thus if (Connect_6(D) != 0) GIMPLE_COND is never marked as necessary
> > and the whole endless loop with printfs in it is removed.
> 
> I'm not sure I'm following this alright, but AFAICT bb7 and bb8 are
> control-dependent on the "if" in bb2. To preserve the infinite-loop
> semantics the control parent of the infinite loop must be inherently
> preserved (because empty infinite loops can't mark any feeding
> statements). So shouldn't the code in find_obviously_necessary_stmts
> that handles infinite loops mark the last statement of control parents
> necessary?

If bb7 and bb8 aren't there and bb2 branches directly to bb3 and bb5,
then things work correctly, find_control_dependence then says that
the 2->3 edge is control parent of bb3 and bb4 (bb3 immediate post-dominator
is bb4, bb4 is immediately post-dominated through fake edge by exit) and
similarly 2->5 edge is control parent of bb5 and bb6.  Then
find_obviously_necessary_stmts does:
      FOR_EACH_LOOP (li, loop, 0)
        if (!finite_loop_p (loop))
          {
            if (dump_file)
              fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
            mark_control_dependent_edges_necessary (loop->latch, el, false);
          }
and that marks the control stmt in bb2 as necessary, because edge 2->3 is
in bb3 and bb4 bitmap and edge 2->5 is in bb5 and bb6 control dependence
bitmap.  The problem with bb7/bb8 is that because they have fake edges to
exit too, find_control_dependence stops at them, thus 2->7 is considered
control parent of bb7 and 2->8 control parent of bb8, and 7->3 is considered
control parent of bb3 and bb4 and 8->5 of bb5 and bb6.  Thus,
mark_control_dependent_edges_necessary called on say the bb4 latch calls
marks_last_stmt_necessary on bb7, but, there is no last stmt in that bb,
nothing to mark necessary and it silently stops there.

What my patch does is change it so that in that case it doesn't stop there,
but recurses.

	Jakub

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Steven Bosscher]

On Mon, Oct 22, 2012 at 9:58 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Mon, Oct 22, 2012 at 09:48:16PM +0200, Steven Bosscher wrote:
>> On Mon, Oct 22, 2012 at 9:35 PM, Jakub Jelinek <jakub@redhat.com> wrote:
>> > On the following testcase we have two endless loops before cddce2:
>> >
>> > Sender_signal (int Connect)
>> > {
>> >   int State;
>> >   unsigned int occurrence;
>> >
>> >   <bb 2>:
>> >   if (Connect_6(D) != 0)
>> >     goto <bb 8>;
>> >   else
>> >     goto <bb 7>;
>> >
>> >   <bb 3>:
>> >   # occurrence_8 = PHI <0(7), occurrence_12(4)>
>> >   occurrence_12 = occurrence_8 + 1;
>> >   __builtin_printf ("Sender_Signal occurrence %u\n", occurrence_12);
>> >
>> >   <bb 4>:
>> >   goto <bb 3>;
>> >
>> >   <bb 5>:
>> >
>> >   <bb 6>:
>> >   goto <bb 5>;
>> >
>> >   <bb 7>:
>> >   goto <bb 3>;
>> >
>> >   <bb 8>:
>> >   goto <bb 5>;
>> >
>> > }
>> >
>> > The problem are the two empty bbs on the path from the conditional
>> > at the end of bb2 and the endless loops (i.e. bb7 and bb8).
>> > In presence of infinite loops dominance.c adds fake edges to exit pretty
>> > arbitrarily (it uses FOR_EACH_BB_REVERSE and for unconnected bbs
>> > computes post-dominance and adds fake edges to exit), so with the above
>> > testcases both bb7 and bb8 have exit block as immediate post-dominator,
>> > so find_control_dependence stops at those bb's when starting from the
>> > 2->7 resp. 2->8 edges.  bb7/bb8 don't have a control stmt at the end,
>> > so mark_last_stmt_necessary doesn't mark any stmt as necessary in them
>> > and thus if (Connect_6(D) != 0) GIMPLE_COND is never marked as necessary
>> > and the whole endless loop with printfs in it is removed.
>>
>> I'm not sure I'm following this alright, but AFAICT bb7 and bb8 are
>> control-dependent on the "if" in bb2. To preserve the infinite-loop
>> semantics the control parent of the infinite loop must be inherently
>> preserved (because empty infinite loops can't mark any feeding
>> statements). So shouldn't the code in find_obviously_necessary_stmts
>> that handles infinite loops mark the last statement of control parents
>> necessary?
>
> If bb7 and bb8 aren't there and bb2 branches directly to bb3 and bb5,
> then things work correctly, find_control_dependence then says that
> the 2->3 edge is control parent of bb3 and bb4 (bb3 immediate post-dominator
> is bb4, bb4 is immediately post-dominated through fake edge by exit) and
> similarly 2->5 edge is control parent of bb5 and bb6.  Then
> find_obviously_necessary_stmts does:
>       FOR_EACH_LOOP (li, loop, 0)
>         if (!finite_loop_p (loop))
>           {
>             if (dump_file)
>               fprintf (dump_file, "can not prove finiteness of loop %i\n", loop->num);
>             mark_control_dependent_edges_necessary (loop->latch, el, false);
>           }
> and that marks the control stmt in bb2 as necessary, because edge 2->3 is
> in bb3 and bb4 bitmap and edge 2->5 is in bb5 and bb6 control dependence
> bitmap.  The problem with bb7/bb8 is that because they have fake edges to
> exit too, find_control_dependence stops at them, thus 2->7 is considered
> control parent of bb7 and 2->8 control parent of bb8, and 7->3 is considered
> control parent of bb3 and bb4 and 8->5 of bb5 and bb6.  Thus,
> mark_control_dependent_edges_necessary called on say the bb4 latch calls
> marks_last_stmt_necessary on bb7, but, there is no last stmt in that bb,
> nothing to mark necessary and it silently stops there.
>
> What my patch does is change it so that in that case it doesn't stop there,
> but recurses.

I understand what your patch does, but I don't understand why it is correct.

Why are there fake edges from bb7 and bb8 to exit when both are
reverse-reachable from exit via the infinite loops? The infinite loops
should be connected to exit, and bb7 and bb8 should be found by the
DFS from the really dead ends in the cfg.

Ciao!
Steven

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Jakub Jelinek]

On Mon, Oct 22, 2012 at 10:27:52PM +0200, Steven Bosscher wrote:
> I understand what your patch does, but I don't understand why it is correct.
> 
> Why are there fake edges from bb7 and bb8 to exit when both are
> reverse-reachable from exit via the infinite loops? The infinite loops
> should be connected to exit, and bb7 and bb8 should be found by the
> DFS from the really dead ends in the cfg.

See what dominance.c does:
      if (saw_unconnected)
        {
          FOR_EACH_BB_REVERSE (b)
            {
              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;
              di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
              di->dfsnum++;
              calc_dfs_tree_nonrec (di, b, reverse);
            }
        }
bb7/bb8 (i.e. all bbs that are always in the end followed by infinite loops)
as well as all the bbs on the infinite loops are processed the above way,
they have no real path to exit, so aren't processed on the first iteration,
they aren't processed even after adding fake edges from zero successor bbs.
calc_dfs_tree then picks pretty much random bbs (one with highest index),
adds fake edge to it, walks it, then goes on with other bbs that are still
unconnected.
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.

	Jakub

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Steven Bosscher]

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.

Ciao!
Steven


Index: dominance.c
===================================================================
--- dominance.c	(revision 192517)
+++ dominance.c	(working copy)
@@ -353,12 +353,15 @@
 	 pretend that there is an edge to the exit block.  In the second
 	 case, we wind up with a forest.  We need to process all noreturn
 	 blocks before we know if we've got any infinite loops.  */
-
+      int *revcfg_postorder = XNEWVEC (int, n_basic_blocks);
+      int n = inverted_post_order_compute (revcfg_postorder);
+      unsigned int i = (unsigned) n;
       basic_block b;
       bool saw_unconnected = false;

-      FOR_EACH_BB_REVERSE (b)
+      while (i)
 	{
+	  basic_block b = revcfg_postorder[--i];
 	  if (EDGE_COUNT (b->succs) > 0)
 	    {
 	      if (di->dfs_order[b->index] == 0)
@@ -375,8 +378,10 @@

       if (saw_unconnected)
 	{
-	  FOR_EACH_BB_REVERSE (b)
+	  i = n;
+	  while (i)
 	    {
+	      basic_block b = revcfg_postorder[--i];
 	      if (di->dfs_order[b->index])
 		continue;
 	      bitmap_set_bit (di->fake_exit_edge, b->index);

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Jakub Jelinek]

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.

--- 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" } } */

	Jakub

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Steven Bosscher]

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

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Steven Bosscher]

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):

FWIW, dfs_find_deadend looks broken to me for this usage case. It
could return a self-loop block with more than one successor. For a
pre-order search like dominance.c needs, you'd have to look as deep as
possible, something like this:

Index: cfganal.c
===================================================================
--- cfganal.c   (revision 192696)
+++ cfganal.c   (working copy)
@@ -598,18 +598,26 @@ dfs_find_deadend (basic_block bb)
 {
   sbitmap visited = sbitmap_alloc (last_basic_block);
   sbitmap_zero (visited);
+  basic_block next_bb = NULL;
+  edge_iterator ei;
+  edge e;

   for (;;)
     {
       SET_BIT (visited, bb->index);
-      if (EDGE_COUNT (bb->succs) == 0
-          || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
+      /* Look for any not yet visited successors.
+        If all successors have been visited then
+        this is the dead end we're looking for.  */
+      FOR_EACH_EDGE (e, ei, bb->succs)
+       if (! TEST_BIT (visited, e->dest->index))
+         break;
+      if (e == NULL)
         {
           sbitmap_free (visited);
           return bb;
         }

-      bb = EDGE_SUCC (bb, 0)->dest;
+      bb = e->dest;
     }

   gcc_unreachable ();


(And the (EDGE_COUNT(bb->succs) == 0) is unnecessary for
inverted_post_order_compute because it already puts all such blocks on
the initial work list :-)

Ciao!
Steven

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Jakub Jelinek]

On Tue, Oct 23, 2012 at 12:49:44AM +0200, Steven Bosscher wrote:
> 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):
> 
> FWIW, dfs_find_deadend looks broken to me for this usage case. It
> could return a self-loop block with more than one successor. For a
> pre-order search like dominance.c needs, you'd have to look as deep as
> possible, something like this:

I've bootstrapped overnight the patch I posted (without your
dfs_find_deadend change (next_bb is unused var there btw)), and there is a
new FAIL with it - ssa-dce-3.c (and your dfs_find_deadend change doesn't
change anything on it).

Before cddce1 we have:

  <bb 2>:
  goto <bb 6>;

  <bb 3>:
  j_8 = j_3 + 501;
  goto <bb 5>;

  <bb 4>:
  j_9 = j_3 + 499;

  <bb 5>:
  # j_2 = PHI <j_8(3), j_9(4)>
  i_10 = i_1 + 2;

  <bb 6>:
  # i_1 = PHI <1(2), i_10(5)>
  # j_3 = PHI <0(2), j_2(5)>
  j_6 = j_3 + 500;
  _7 = j_6 % 7;
  if (_7 != 0)
    goto <bb 3>;
  else
    goto <bb 4>;

and before the dominance.c change bb6 has fake edge to exit,
bb3 and bb4 are immediately post-dominated by bb5 and bb5 is immediately
post-dominated by bb6, thus when mark_control_dependent_edges_necessary
is called on the latch (bb5) of the infinite loop, it marks the _7 != 0
statement as necessary and the j_N and _7 assignments stay,
as 6->3 and 6->4 edges are recorded as control parents for bb3, bb4 and bb5.

With the patch bb5 is instead the bb with fake edge to exit,
and bb6, bb3 and bb4 are all immediate post-dominated by bb5 and
edge 5->6 is control parent of bb5.  So with the patch this is optimized
into just:
  <bb 2>:

  <bb 3>:
  goto <bb 3>;

I guess it is fine that way and the testcase needs adjustment, just wanted
to point to the differences.

> (And the (EDGE_COUNT(bb->succs) == 0) is unnecessary for
> inverted_post_order_compute because it already puts all such blocks on
> the initial work list :-)

And so does dominance.c:
      FOR_EACH_BB_REVERSE (b)
        {
          if (EDGE_COUNT (b->succs) > 0)
            {
              if (di->dfs_order[b->index] == 0)
                saw_unconnected = true;
              continue;
            }
          bitmap_set_bit (di->fake_exit_edge, b->index);

	Jakub

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Steven Bosscher]

[-- Attachment #1: Type: text/plain, Size: 1521 bytes --]

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

[-- Attachment #2: PR55018.diff --]
[-- Type: application/octet-stream, Size: 4257 bytes --]

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.

testsuite/
	PR tree-optimization/55018
	* gcc.dg/torture/pr55018.c: New test.

Index: basic-block.h
===================================================================
--- basic-block.h	(revision 192893)
+++ basic-block.h	(working copy)
@@ -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,
Index: cfganal.c
===================================================================
--- cfganal.c	(revision 192893)
+++ cfganal.c	(working copy)
@@ -573,7 +573,9 @@ post_order_compute (int *post_order, bool include_
 }
 
 
-/* Helper routine for inverted_post_order_compute.
+/* Helper routine for inverted_post_order_compute
+   flow_dfs_compute_reverse_execute, and the reverse-CFG
+   deapth first search in dominance.c.
    BB has to belong to a region of CFG
    unreachable by inverted traversal from the exit.
    i.e. there's no control flow path from ENTRY to EXIT
@@ -593,19 +595,17 @@ post_order_compute (int *post_order, bool include_
    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);
-  sbitmap_zero (visited);
+  bitmap visited = BITMAP_ALLOC (NULL);
 
   for (;;)
     {
-      SET_BIT (visited, bb->index);
       if (EDGE_COUNT (bb->succs) == 0
-          || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
+	  || ! bitmap_set_bit (visited, bb->index))
         {
-          sbitmap_free (visited);
+          BITMAP_FREE (visited);
           return bb;
         }
 
@@ -958,7 +958,7 @@ flow_dfs_compute_reverse_execute (depth_first_sear
   /* Determine if there are unvisited basic blocks.  */
   FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
     if (!TEST_BIT (data->visited_blocks, bb->index))
-      return bb;
+      return dfs_find_deadend (bb);
 
   return NULL;
 }
Index: dominance.c
===================================================================
--- dominance.c	(revision 192893)
+++ dominance.c	(working copy)
@@ -377,14 +377,18 @@ calc_dfs_tree (struct dom_info *di, bool reverse)
 	{
 	  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]);
 	    }
 	}
     }
Index: testsuite/gcc.dg/torture/pr55018.c
===================================================================
--- testsuite/gcc.dg/torture/pr55018.c	(revision 0)
+++ testsuite/gcc.dg/torture/pr55018.c	(revision 0)
@@ -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" } } */

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Richard Biener]

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

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Hans-Peter Nilsson]

> From: Steven Bosscher <stevenb.gcc@gmail.com>
> Date: Sun, 28 Oct 2012 19:33:29 +0100

> 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.

> 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.

brgds, H-P

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Jakub Jelinek]

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

Re: [PATCH] Fix CDDCE miscompilation (PR tree-optimization/55018)

[Jan Hubicka]

> 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