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

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

[Marek Polacek]

In this PR, for the C testcase, in .cse1 we have:

            ENTRY    
             |   
             |   
             2   
             |   
             |   
   +-------- 4 ----------+
   |        / \          |   
   |       /   \         |   
   |      6     5        |   
   |     /\     |\       |   
   |    /  \    | \      |   
   |   7    3   |  8     |   
   |   |    |   |  /\    /   
   +---|----|   | /  \  /
       |      --10    9/  
       |    -/  
      EXIT-/

(3->4 and 9->4 are back edges).  Now, in bypass_block, when we're
trying to bypass BB 4, we iterate over BB 4's incoming edges,
then we're iterating over reg_use_table (registers used in
insn).  Here we call
set = find_bypass_set (regno, e->src->index);
but since it returns non-NULL value, redirect_edge_and_branch_force 
later redirects edges and BB 4 is gone.
We then end up with
Redirecting fallthru edge 3->4 to 6
JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 1 [0x1])
Bypass edge from 3->4 to 6
Redirecting fallthru edge 9->4 to 5
JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 3 [0x3])
Bypass edge from 9->4 to 5
i.e., it is assumed that in one reg there "are" two constants, that can't
be right, right?!  I've tried to fix this by not redirecting edges (thus
bypassing block) if BB has more
incoming latch edges and the hash table has more different SRC rtxs with
the same hash value.
FWIW, the table looks like the below:
SET hash table (11 buckets, 3 entries)
Index 0 (hash value 4)
  (reg:SI 59 [ D.1735 ]) := (const_int 1 [0x1])
Index 1 (hash value 5)
  (reg/v/f:DI 60 [ b ]) := (const_int 0 [0])
Index 2 (hash value 4)
  (reg:SI 59 [ D.1735 ]) := (const_int 3 [0x3])

(Only not bypassing BB when it has more latch edges would work too,
but I'm afraid it could pessimize stuff somewhere else.)
I've also changed some zeros into NULLs for pointers.
Also, as folowup, we could get rid of may_be_loop_header variable 
completely, at one place where it is used we can use just 'n_latches > 0'.
And add the C++ TC as well.
Regtested/bootstrapped on x86_64-linux, ok for trunk?

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

	PR middle-end/54838
	* cprop.c (only_one_const_p): New function.
	(find_bypass_set): New parameter.  Conditionally call
	only_one_const_p.  Use NULL instead of 0.
	(bypass_block): Adjust caller.  Determine number of latch edges.
	(n_latches): New variable.

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

--- gcc/cprop.c.mp	2012-11-26 12:13:08.631193625 +0100
+++ gcc/cprop.c	2012-11-26 14:41:32.864034283 +0100
@@ -1429,14 +1429,26 @@ find_implicit_sets (void)
 
 static int bypass_last_basic_block;
 
+/* Determine whether there is only one constant SRC rtx in the hash table
+   for REGNO.  Here we assume that for the same hash value there won't be
+   more entries with the same SRC rtx.  Return true if there is only one
+   constant, false otherwise.  */
+
+static bool
+only_one_const_p (int regno)
+{
+  struct expr *set = lookup_set (regno, &set_hash_table);
+  return next_set (regno, set) == NULL;
+}
+
 /* Find a set of REGNO to a constant that is available at the end of basic
    block BB.  Return NULL if no such set is found.  Based heavily upon
    find_avail_set.  */
 
 static struct expr *
-find_bypass_set (int regno, int bb)
+find_bypass_set (int regno, int bb, bool multiple_latches)
 {
-  struct expr *result = 0;
+  struct expr *result = NULL;
 
   for (;;)
     {
@@ -1450,9 +1462,15 @@ find_bypass_set (int regno, int bb)
 	  set = next_set (regno, set);
 	}
 
-      if (set == 0)
+      if (set == NULL)
 	break;
 
+      /* If there are more latch edges coming to the BB, we need to
+	 make sure that for the same hash value there aren't
+	 more constants.  */
+      if (multiple_latches && !only_one_const_p (regno))
+	return NULL;
+
       src = set->src;
       if (cprop_constant_p (src))
 	result = set;
@@ -1502,6 +1520,7 @@ bypass_block (basic_block bb, rtx setcc,
   int may_be_loop_header;
   unsigned removed_p;
   unsigned i;
+  unsigned n_latches;
   edge_iterator ei;
 
   insn = (setcc != NULL) ? setcc : jump;
@@ -1514,12 +1533,12 @@ bypass_block (basic_block bb, rtx setcc,
     find_used_regs (&XEXP (note, 0), NULL);
 
   may_be_loop_header = false;
+  n_latches = 0;
   FOR_EACH_EDGE (e, ei, bb->preds)
     if (e->flags & EDGE_DFS_BACK)
-      {
-	may_be_loop_header = true;
-	break;
-      }
+      n_latches++;
+
+  may_be_loop_header = n_latches > 0;
 
   change = 0;
   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
@@ -1557,7 +1576,7 @@ bypass_block (basic_block bb, rtx setcc,
 	  struct expr *set;
 	  rtx src, new_rtx;
 
-	  set = find_bypass_set (regno, e->src->index);
+	  set = find_bypass_set (regno, e->src->index, n_latches > 1);
 
 	  if (! set)
 	    continue;
--- gcc/testsuite/gcc.dg/pr54838.c.mp	2012-11-26 14:48:43.783980854 +0100
+++ gcc/testsuite/gcc.dg/pr54838.c	2012-11-26 14:49:51.051158719 +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

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

[Eric Botcazou]

> We then end up with
> Redirecting fallthru edge 3->4 to 6
> JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 1
> [0x1]) Bypass edge from 3->4 to 6
> Redirecting fallthru edge 9->4 to 5
> JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 3
> [0x3]) Bypass edge from 9->4 to 5
> i.e., it is assumed that in one reg there "are" two constants, that can't
> be right, right?!

No, I don't think that's the problem.  The above messages are admittedly a bit 
terse, they should say:

JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 3 [0x3])
             when BB 4 is entered from BB 9.  Redirect edge 9->4 to 5.

so you can have different constants for BB 3 and BB 9.  The patch to tweak the 
dump messages along these lines is pre-approved.

The ICE in merge_latch_edges means that the loop structure and the CFG aren't 
in sync anymore.  Does the cprop pass modify the former without declaring it?

-- 
Eric Botcazou

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

[Marek Polacek]

On Wed, Nov 28, 2012 at 10:52:17AM +0100, Eric Botcazou wrote:
> No, I don't think that's the problem.  The above messages are admittedly a bit 
> terse, they should say:
> 
> JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 3 [0x3])
>              when BB 4 is entered from BB 9.  Redirect edge 9->4 to 5.
> 
> so you can have different constants for BB 3 and BB 9.  The patch to tweak the 
> dump messages along these lines is pre-approved.

Ouch.  Okay, I'll post a separate patch for improving the message.

> The ICE in merge_latch_edges means that the loop structure and the CFG aren't 
> in sync anymore.  Does the cprop pass modify the former without declaring it?

I admit I'm not sure what to look at, maybe cprop should have in
properties_destroyed PROP_loops?  Well, then we need to remove one
assert in loop-init.c.  So something like:

--- gcc/cprop.c.mp	2012-11-28 16:55:03.520375191 +0100
+++ gcc/cprop.c	2012-11-28 16:55:35.992246623 +0100
@@ -1927,7 +1927,7 @@ struct rtl_opt_pass pass_rtl_cprop =
   TV_CPROP,                             /* tv_id */
   PROP_cfglayout,                       /* properties_required */
   0,                                    /* properties_provided */
-  0,                                    /* properties_destroyed */
+  PROP_loops,                           /* properties_destroyed */
   0,                                    /* todo_flags_start */
   TODO_df_finish | TODO_verify_rtl_sharing |
   TODO_verify_flow | TODO_ggc_collect   /* todo_flags_finish */
--- gcc/loop-init.c.mp	2012-11-28 16:55:08.924398879 +0100
+++ gcc/loop-init.c	2012-11-28 16:55:17.684437276 +0100
@@ -54,8 +54,6 @@ loop_optimizer_init (unsigned flags)
     }
   else
     {
-      gcc_assert (cfun->curr_properties & PROP_loops);
-
       /* Ensure that the dominators are computed, like flow_loops_find does.  */
       calculate_dominance_info (CDI_DOMINATORS);
 
This quashes the ICE.  I've regtested it, it caused one
regression though:
FAIL: gcc.dg/unroll_5.c scan-rtl-dump-times loop2_unroll "realistic
bound: 2999999" 1

But there probably is something else.

Thanks for the review,

	Marek

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

[Richard Biener]

On Wed, Nov 28, 2012 at 7:24 PM, Marek Polacek <polacek@redhat.com> wrote:
> On Wed, Nov 28, 2012 at 10:52:17AM +0100, Eric Botcazou wrote:
>> No, I don't think that's the problem.  The above messages are admittedly a bit
>> terse, they should say:
>>
>> JUMP-BYPASS: Proved reg 59 in jump_insn 15 equals constant (const_int 3 [0x3])
>>              when BB 4 is entered from BB 9.  Redirect edge 9->4 to 5.
>>
>> so you can have different constants for BB 3 and BB 9.  The patch to tweak the
>> dump messages along these lines is pre-approved.
>
> Ouch.  Okay, I'll post a separate patch for improving the message.
>
>> The ICE in merge_latch_edges means that the loop structure and the CFG aren't
>> in sync anymore.  Does the cprop pass modify the former without declaring it?
>
> I admit I'm not sure what to look at, maybe cprop should have in
> properties_destroyed PROP_loops?  Well, then we need to remove one
> assert in loop-init.c.  So something like:

Definitely not - that means to not preserve loops until after cprop.  The goal
is to preserve loops everywhere!

Richard.

> --- gcc/cprop.c.mp      2012-11-28 16:55:03.520375191 +0100
> +++ gcc/cprop.c 2012-11-28 16:55:35.992246623 +0100
> @@ -1927,7 +1927,7 @@ struct rtl_opt_pass pass_rtl_cprop =
>    TV_CPROP,                             /* tv_id */
>    PROP_cfglayout,                       /* properties_required */
>    0,                                    /* properties_provided */
> -  0,                                    /* properties_destroyed */
> +  PROP_loops,                           /* properties_destroyed */
>    0,                                    /* todo_flags_start */
>    TODO_df_finish | TODO_verify_rtl_sharing |
>    TODO_verify_flow | TODO_ggc_collect   /* todo_flags_finish */
> --- gcc/loop-init.c.mp  2012-11-28 16:55:08.924398879 +0100
> +++ gcc/loop-init.c     2012-11-28 16:55:17.684437276 +0100
> @@ -54,8 +54,6 @@ loop_optimizer_init (unsigned flags)
>      }
>    else
>      {
> -      gcc_assert (cfun->curr_properties & PROP_loops);
> -
>        /* Ensure that the dominators are computed, like flow_loops_find does.  */
>        calculate_dominance_info (CDI_DOMINATORS);
>
> This quashes the ICE.  I've regtested it, it caused one
> regression though:
> FAIL: gcc.dg/unroll_5.c scan-rtl-dump-times loop2_unroll "realistic
> bound: 2999999" 1
>
> But there probably is something else.
>
> Thanks for the review,
>
>         Marek

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

[Steven Bosscher]

On Thu, Nov 29, 2012 at 9:34 AM, Richard Biener wrote:
> On Wed, Nov 28, 2012 at 7:24 PM, Marek Polacek wrote:
>> I admit I'm not sure what to look at, maybe cprop should have in
>> properties_destroyed PROP_loops?  Well, then we need to remove one
>> assert in loop-init.c.  So something like:
>
> Definitely not - that means to not preserve loops until after cprop.  The goal
> is to preserve loops everywhere!

It'd be nice if this was documented somewhere...

Ciao!
Steven

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

[Richard Biener]

On Thu, Nov 29, 2012 at 9:56 AM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Thu, Nov 29, 2012 at 9:34 AM, Richard Biener wrote:
>> On Wed, Nov 28, 2012 at 7:24 PM, Marek Polacek wrote:
>>> I admit I'm not sure what to look at, maybe cprop should have in
>>> properties_destroyed PROP_loops?  Well, then we need to remove one
>>> assert in loop-init.c.  So something like:
>>
>> Definitely not - that means to not preserve loops until after cprop.  The goal
>> is to preserve loops everywhere!
>
> It'd be nice if this was documented somewhere...

On my TODO list for stage3 ;)

Richard.

> Ciao!
> Steven

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

[Marek Polacek]

On Thu, Nov 29, 2012 at 09:34:31AM +0100, Richard Biener wrote:
> Definitely not - that means to not preserve loops until after cprop.  The goal
> is to preserve loops everywhere!

Yikes, sorry, it wasn't clear to me what PROP_loops really does.  Anyway,
I think I have a better fix now.  The problem is just that when removing
BB 4 (which was a header), we have to zap ->header and ->latch.  We
already have code for this:

  if (current_loops != NULL
      && e->src->loop_father->latch == e->src)
    {
      /* ???  Now we are creating (or may create) a loop
         with multiple entries.  Simply mark it for
         removal.  Alternatively we could not do this
         threading.  */
      e->src->loop_father->header = NULL;
      e->src->loop_father->latch = NULL;
    }

but the thing is that when there are multiple latch edges, then
->latch is NULL.  So we need to keep track of how many latch edges
the header has.  Regtested/bootstrapped on x86_64, ok for trunk?

Can I get rid of may_be_loop_header (and just use n_latch_edges > 0
instead at that one place) in a followup?

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.
	(n_latches): New variable.

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

--- gcc/cprop.c.mp	2012-11-29 15:49:53.120524295 +0100
+++ gcc/cprop.c	2012-11-29 15:50:01.421547832 +0100
@@ -1499,6 +1499,7 @@ bypass_block (basic_block bb, rtx setcc,
   int may_be_loop_header;
   unsigned removed_p;
   unsigned i;
+  unsigned n_latch_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_latch_edges = 0;
   FOR_EACH_EDGE (e, ei, bb->preds)
     if (e->flags & EDGE_DFS_BACK)
-      {
-	may_be_loop_header = true;
-	break;
-      }
+      n_latch_edges++;
+
+  may_be_loop_header = n_latch_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_latch_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-26 14:49:51.051158719 +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

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

[Marek Polacek]

On Thu, Nov 29, 2012 at 04:38:52PM +0100, Marek Polacek wrote:
> 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.
> 	(n_latches): New variable.

Of course here should be (n_latch_edges).

	Marek

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

[Steven Bosscher]

On Thu, Nov 29, 2012 at 4:38 PM, Marek Polacek wrote:
> On Thu, Nov 29, 2012 at 09:34:31AM +0100, Richard Biener wrote:
>> Definitely not - that means to not preserve loops until after cprop.  The goal
>> is to preserve loops everywhere!
>
> Yikes, sorry, it wasn't clear to me what PROP_loops really does.  Anyway,
> I think I have a better fix now.  The problem is just that when removing
> BB 4 (which was a header), we have to zap ->header and ->latch.  We
> already have code for this:
>
>   if (current_loops != NULL
>       && e->src->loop_father->latch == e->src)
>     {
>       /* ???  Now we are creating (or may create) a loop
>          with multiple entries.  Simply mark it for
>          removal.  Alternatively we could not do this
>          threading.  */
>       e->src->loop_father->header = NULL;
>       e->src->loop_father->latch = NULL;
>     }
>
> but the thing is that when there are multiple latch edges, then
> ->latch is NULL.  So we need to keep track of how many latch edges
> the header has.  Regtested/bootstrapped on x86_64, ok for trunk?
>
> Can I get rid of may_be_loop_header (and just use n_latch_edges > 0
> instead at that one place) in a followup?
>
> 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.

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



>         * gcc.dg/pr54838.c: New test.
>
> --- gcc/cprop.c.mp      2012-11-29 15:49:53.120524295 +0100
> +++ gcc/cprop.c 2012-11-29 15:50:01.421547832 +0100
> @@ -1499,6 +1499,7 @@ bypass_block (basic_block bb, rtx setcc,
>    int may_be_loop_header;
>    unsigned removed_p;
>    unsigned i;
> +  unsigned n_latch_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_latch_edges = 0;
>    FOR_EACH_EDGE (e, ei, bb->preds)
>      if (e->flags & EDGE_DFS_BACK)
> -      {
> -       may_be_loop_header = true;
> -       break;
> -      }
> +      n_latch_edges++;
> +
> +  may_be_loop_header = n_latch_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_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.

Ciao!
Steven

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

[Marek Polacek]

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

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

[Eric Botcazou]

> Yikes, sorry, it wasn't clear to me what PROP_loops really does.  Anyway,
> I think I have a better fix now.  The problem is just that when removing
> BB 4 (which was a header), we have to zap ->header and ->latch.  We
> already have code for this:
> 
>   if (current_loops != NULL
>       && e->src->loop_father->latch == e->src)
>     {
>       /* ???  Now we are creating (or may create) a loop
>          with multiple entries.  Simply mark it for
>          removal.  Alternatively we could not do this
>          threading.  */
>       e->src->loop_father->header = NULL;
>       e->src->loop_father->latch = NULL;
>     }
> 
> but the thing is that when there are multiple latch edges, then
> ->latch is NULL.  So we need to keep track of how many latch edges
> the header has.  Regtested/bootstrapped on x86_64, ok for trunk?
> 
> Can I get rid of may_be_loop_header (and just use n_latch_edges > 0
> instead at that one place) in a followup?
> 
> 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.
> 	(n_latches): New variable.

This looks good on principle, but can't we do better now that we have the loop 
structure?   Can't we compute is_loop_header instead of may_be_loop_header and 
simplify the condition under which we mark the loop for removal?  Or maybe we 
should call disambiguate_loops_with_multiple_latches on entry of the pass?

Richard, what would be the "modern" approach to solving the problem here?

-- 
Eric Botcazou

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

[Richard Biener]

On Thu, Nov 29, 2012 at 6:43 PM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> Yikes, sorry, it wasn't clear to me what PROP_loops really does.  Anyway,
>> I think I have a better fix now.  The problem is just that when removing
>> BB 4 (which was a header), we have to zap ->header and ->latch.  We
>> already have code for this:
>>
>>   if (current_loops != NULL
>>       && e->src->loop_father->latch == e->src)
>>     {
>>       /* ???  Now we are creating (or may create) a loop
>>          with multiple entries.  Simply mark it for
>>          removal.  Alternatively we could not do this
>>          threading.  */
>>       e->src->loop_father->header = NULL;
>>       e->src->loop_father->latch = NULL;
>>     }
>>
>> but the thing is that when there are multiple latch edges, then
>> ->latch is NULL.  So we need to keep track of how many latch edges
>> the header has.  Regtested/bootstrapped on x86_64, ok for trunk?
>>
>> Can I get rid of may_be_loop_header (and just use n_latch_edges > 0
>> instead at that one place) in a followup?
>>
>> 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.
>>       (n_latches): New variable.
>
> This looks good on principle, but can't we do better now that we have the loop
> structure?   Can't we compute is_loop_header instead of may_be_loop_header and
> simplify the condition under which we mark the loop for removal?  Or maybe we
> should call disambiguate_loops_with_multiple_latches on entry of the pass?
>
> Richard, what would be the "modern" approach to solving the problem here?

RTL cprop seems to run both before and after RTL loop optimizers (currently
after RTL loop optimizers we throw away loops - an arbitrary chosen point
before IRA across which I could not get things to work).  Thus you could do

  if (current_loops)
    is_loop_header = bb == bb->loop_father->header;
  else
    {
  may_be_loop_header = false;
  FOR_EACH_EDGE (e, ei, bb->preds)
    if (e->flags & EDGE_DFS_BACK)
      {
        may_be_loop_header = true;
        break;
      }
    }

I don't understand

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

why isn't this simply

      if (may_be_loop_header)
        {
          ei_next (&ei);
          continue;
        }

?  It looks like the code tries to allow "rotating" a loop - but that's only
good if bb has exactly two predecessors (one entry and one latch edge).
And even then it requires to manually update the loop structures (update
what the new header and latch blocks are).

That said, removing the !(e->flags & EDGE_DFS_BACK) condition seems
to fix the ICE.  Threading across a loop header is in fact complicated
(see the special routine tree-ssa-threadupdate.c:thread_through_loop_header
necessary for that).  Let's declare the GIMPLE level did all interesting
threadings through headers.

Btw, if a pass wants to look at anything loop related _besides_ loop headers
it has to call loop_optimizer_init.  The only thing that is guaranteed
to be kept
up-to-date when PROP_loops is set (and thus current_loops != NULL) is
the header field in the loop tree.

Richard.

> --
> Eric Botcazou

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

[Marek Polacek]

On Fri, Nov 30, 2012 at 10:01:37AM +0100, Richard Biener wrote:
> RTL cprop seems to run both before and after RTL loop optimizers (currently
> after RTL loop optimizers we throw away loops - an arbitrary chosen point
> before IRA across which I could not get things to work).  Thus you could do
> 
>   if (current_loops)
>     is_loop_header = bb == bb->loop_father->header;
>   else
>     {
>   may_be_loop_header = false;
>   FOR_EACH_EDGE (e, ei, bb->preds)
>     if (e->flags & EDGE_DFS_BACK)
>       {
>         may_be_loop_header = true;
>         break;
>       }
>     }

I can do this as a followup.
 
> I don't understand
> 
>       /* 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;
>         }
> 
> why isn't this simply
> 
>       if (may_be_loop_header)
>         {
>           ei_next (&ei);
>           continue;
>         }
> 
> ?  It looks like the code tries to allow "rotating" a loop - but that's only
> good if bb has exactly two predecessors (one entry and one latch edge).
> And even then it requires to manually update the loop structures (update
> what the new header and latch blocks are).
> 
> That said, removing the !(e->flags & EDGE_DFS_BACK) condition seems
> to fix the ICE.  Threading across a loop header is in fact complicated
> (see the special routine tree-ssa-threadupdate.c:thread_through_loop_header
> necessary for that).  Let's declare the GIMPLE level did all interesting
> threadings through headers.

Agreed.  This is the fix I had some time ago, but at that time it
didn't seem like such a great idea.  Done this time around.
Regtested/bootstrapped on x86_64-linux, ok for trunk?

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

	PR middle-end/54838
	* cprop.c (bypass_block): Skip header edges.

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

--- gcc/cprop.c.mp	2012-11-29 15:49:53.120524295 +0100
+++ gcc/cprop.c	2012-11-30 10:30:23.509501957 +0100
@@ -1539,8 +1539,7 @@ bypass_block (basic_block bb, rtx setcc,
       /* 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))
+      if (may_be_loop_header)
 	{
 	  ei_next (&ei);
 	  continue;
--- 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

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

[Eric Botcazou]

> RTL cprop seems to run both before and after RTL loop optimizers (currently
> after RTL loop optimizers we throw away loops - an arbitrary chosen point
> before IRA across which I could not get things to work).  Thus you could do
> 
>   if (current_loops)
>     is_loop_header = bb == bb->loop_father->header;
>   else
>     {
>   may_be_loop_header = false;
>   FOR_EACH_EDGE (e, ei, bb->preds)
>     if (e->flags & EDGE_DFS_BACK)
>       {
>         may_be_loop_header = true;
>         break;
>       }
>     }

OK, let's do something like this then:

  if (current_loops)
    may_be_loop_header = (bb == bb->loop_father->header);
  else
    {
       may_be_loop_header = false;
       FOR_EACH_EDGE (e, ei, bb->preds)
       if (e->flags & EDGE_DFS_BACK)
         {
          may_be_loop_header = true;
          break;
         }
    }

since we cannot always be sure that it's a header.

> I don't understand
> 
>       /* 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;
>         }
> 
> why isn't this simply
> 
>       if (may_be_loop_header)
>         {
>           ei_next (&ei);
>           continue;
>         }
> 
> ?  It looks like the code tries to allow "rotating" a loop - but that's only
> good if bb has exactly two predecessors (one entry and one latch edge). And
> even then it requires to manually update the loop structures (update what
> the new header and latch blocks are).

That's the bug.  We have a loop with 2 latch edges, but the loop fixup code in 
bypass_block only handles one.

> That said, removing the !(e->flags & EDGE_DFS_BACK) condition seems
> to fix the ICE.  Threading across a loop header is in fact complicated
> (see the special routine tree-ssa-threadupdate.c:thread_through_loop_header
> necessary for that).

Scary enough indeed.  But this seems to work fine here if the loop has exactly 
one latch edge, so we don't need to change that.  Removing the above condition 
is equivalent to early returning from bypass_block for all potential headers.

> Let's declare the GIMPLE level did all interesting threadings through
> headers.

The testcase is precisely a counterexample with 2 latch edges.

But OK, let's punt if there is more than a single (potential) latch edge.

-- 
Eric Botcazou

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

[Eric Botcazou]

> Yikes, sorry, it wasn't clear to me what PROP_loops really does.  Anyway,
> I think I have a better fix now.  The problem is just that when removing
> BB 4 (which was a header), we have to zap ->header and ->latch.  We
> already have code for this:
> 
>   if (current_loops != NULL
>       && e->src->loop_father->latch == e->src)
>     {
>       /* ???  Now we are creating (or may create) a loop
>          with multiple entries.  Simply mark it for
>          removal.  Alternatively we could not do this
>          threading.  */
>       e->src->loop_father->header = NULL;
>       e->src->loop_father->latch = NULL;
>     }
> 
> but the thing is that when there are multiple latch edges, then
> ->latch is NULL.  So we need to keep track of how many latch edges
> the header has.  Regtested/bootstrapped on x86_64, ok for trunk?
> 
> Can I get rid of may_be_loop_header (and just use n_latch_edges > 0
> instead at that one place) in a followup?
> 
> 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.
> 	(n_latches): New variable.

OK, let's tweak the patch as follows:
 1) when current_loops is not NULL, we compute may_be_loop_header and whether 
the loop has more than 1 latch edge exactly,
 2) when current_loops is NULL, we use your above method to do the same,
 3) once this is done, we return from the function before entering the loop if 
this is a (potential) header with more than 1 (potential) latch edge.  The 
comment can say that threading through a loop header with more than 1 latch 
edge is delicate and cite tree-threadupdate.c:thread_through_loop_header.

-- 
Eric Botcazou

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

[Marek Polacek]

On Fri, Nov 30, 2012 at 11:00:28PM +0100, Eric Botcazou wrote:
> OK, let's tweak the patch as follows:
>  1) when current_loops is not NULL, we compute may_be_loop_header and whether 
> the loop has more than 1 latch edge exactly,
>  2) when current_loops is NULL, we use your above method to do the same,
>  3) once this is done, we return from the function before entering the loop if 
> this is a (potential) header with more than 1 (potential) latch edge.  The 
> comment can say that threading through a loop header with more than 1 latch 
> edge is delicate and cite tree-threadupdate.c:thread_through_loop_header.

Like this?  Regtested/bootstrapped on x86_64-linux, ok for trunk?

2012-12-01  Marek Polacek  <polacek@redhat.com>

	PR middle-end/54838
	* cprop.c (bypass_block): Determine number of latches.  Return
	when there is 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-12-01 16:14:59.387335461 +0100
@@ -1510,13 +1510,28 @@ bypass_block (basic_block bb, rtx setcc,
   if (note)
     find_used_regs (&XEXP (note, 0), NULL);
 
-  may_be_loop_header = false;
-  FOR_EACH_EDGE (e, ei, bb->preds)
-    if (e->flags & EDGE_DFS_BACK)
-      {
-	may_be_loop_header = true;
-	break;
-      }
+  /* Determine whether there are more latch edges.  Threading through
+     a loop header with more than one latch is delicate, see e.g.
+     tree-ssa-threadupdate.c:thread_through_loop_header.  */
+  if (current_loops)
+    {
+      may_be_loop_header = bb == bb->loop_father->header;
+      if (may_be_loop_header
+	  && bb->loop_father->latch == NULL)
+	return 0;
+    }
+  else
+    {
+      unsigned n_back_edges = 0;
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	if (e->flags & EDGE_DFS_BACK)
+	  n_back_edges++;
+
+      may_be_loop_header = n_back_edges > 0;
+
+      if (n_back_edges > 1)
+        return 0;
+    }
 
   change = 0;
   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
--- gcc/testsuite/gcc.dg/pr54838.c.mp	2012-11-26 14:48:43.783980854 +0100
+++ gcc/testsuite/gcc.dg/pr54838.c	2012-11-26 14:49:51.051158719 +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

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

[Eric Botcazou]

> Like this?  Regtested/bootstrapped on x86_64-linux, ok for trunk?
> 
> 2012-12-01  Marek Polacek  <polacek@redhat.com>
> 
> 	PR middle-end/54838
> 	* cprop.c (bypass_block): Determine number of latches.  Return
> 	when there is more than one latch edge.
> 
> 	* gcc.dg/pr54838.c: New test.

That's fine, thanks for your patience.

-- 
Eric Botcazou