Re: [PATCH] Don't bypass blocks with multiple latch edges (PR middle-end/54838)

[Marek Polacek <polacek@redhat.com>]

On Thu, Nov 29, 2012 at 04:50:19PM +0100, Steven Bosscher wrote:
> > 2012-11-29  Marek Polacek  <>
> >
> >         PR middle-end/54838
> >         * cprop.c (bypass_block): Set header and latch to NULL when
> >         BB has more than one latch edge.
> >         (n_latches): New variable.
> 
> You don't have to mention a new local variable in the ChangeLog.

Ok.

> But FWIW, not all DFS back edges are latches. Maybe name it n_back_edges?

Yeah, sure.

> > @@ -1605,7 +1605,8 @@ bypass_block (basic_block bb, rtx setcc,
> >               && dest != EXIT_BLOCK_PTR)
> >              {
> >               if (current_loops != NULL
> > -                 && e->src->loop_father->latch == e->src)
> > +                 && (e->src->loop_father->latch == e->src
> > +                     || n_latch_edges > 1))
> >                 {
> >                   /* ???  Now we are creating (or may create) a loop
> >                      with multiple entries.  Simply mark it for
> 
> It seems to me that this threading should just not happen. Creating
> loops with multiple entries is something to be avoided because most
> loop-based optimizations don't work on irreducible regions. So this
> affects all passes that run after CPROP, including unrolling, IRA, the
> scheduler, etc.
> 
> There is already code that tries to avoid creating multi-entry loops:
> 
>       /* The irreducible loops created by redirecting of edges entering the
>          loop from outside would decrease effectiveness of some of the
>          following optimizations, so prevent this.  */
>       if (may_be_loop_header
>           && !(e->flags & EDGE_DFS_BACK))
>         {
>           ei_next (&ei);
>           continue;
>         }
> 
> Apparently your test case manages to slip through, and I wonder why.

That's probably because even though BB 4 is a header, 3->4 and 9->4
are back edges (in the condition there's !(e->flags & EDGE_DFS_BACK),
which in this case is 0).  Note that the comment speaks about
edges coming from outside of the loop.

Updated patch:

2012-11-29  Marek Polacek  <polacek@redhat.com>

	PR middle-end/54838
	* cprop.c (bypass_block): Set header and latch to NULL when
	BB has more than one latch edge.

	* gcc.dg/pr54838.c: New test.

--- gcc/cprop.c.mp	2012-11-29 15:49:53.120524295 +0100
+++ gcc/cprop.c	2012-11-29 17:45:03.004041242 +0100
@@ -1499,6 +1499,7 @@ bypass_block (basic_block bb, rtx setcc,
   int may_be_loop_header;
   unsigned removed_p;
   unsigned i;
+  unsigned n_back_edges;
   edge_iterator ei;
 
   insn = (setcc != NULL) ? setcc : jump;
@@ -1510,13 +1511,12 @@ bypass_block (basic_block bb, rtx setcc,
   if (note)
     find_used_regs (&XEXP (note, 0), NULL);
 
-  may_be_loop_header = false;
+  n_back_edges = 0;
   FOR_EACH_EDGE (e, ei, bb->preds)
     if (e->flags & EDGE_DFS_BACK)
-      {
-	may_be_loop_header = true;
-	break;
-      }
+      n_back_edges++;
+
+  may_be_loop_header = n_back_edges > 0;
 
   change = 0;
   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
@@ -1605,7 +1605,8 @@ bypass_block (basic_block bb, rtx setcc,
 	      && dest != EXIT_BLOCK_PTR)
             {
 	      if (current_loops != NULL
-		  && e->src->loop_father->latch == e->src)
+		  && (e->src->loop_father->latch == e->src
+		      || n_back_edges > 1))
 		{
 		  /* ???  Now we are creating (or may create) a loop
 		     with multiple entries.  Simply mark it for
--- gcc/testsuite/gcc.dg/pr54838.c.mp	2012-11-26 14:48:43.783980854 +0100
+++ gcc/testsuite/gcc.dg/pr54838.c	2012-11-29 17:43:19.397737779 +0100
@@ -0,0 +1,24 @@
+/* PR middle-end/54838 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-forward-propagate -ftracer" } */
+
+void bar (void);
+
+void
+foo (void *b, int *c)
+{
+again:
+  switch (*c)
+    {
+    case 1:
+      if (!b)
+	{
+	  bar ();
+	  return;
+	}
+      goto again;
+    case 3:
+      if (!b)
+	goto again;
+    }
+}

	Marek