[PATCH] check_cfg assert fix

[PATCH] check_cfg assert fix

[Tom de Vries]

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

Hi,

During testing the approved-for-commit middle-end patch for bug 43864 on ARM, I
ran into a gcc.dg/torture/pr46068.c ICE.

The following assert in haifa-sched.c:check_cfg triggered:
...
		  else if (any_condjump_p (head))
		    gcc_assert (/* Usual case.  */
                                (EDGE_COUNT (bb->succs) > 1
                                 && !BARRIER_P (NEXT_INSN (head)))
                                /* Or jump to the next instruction.  */
                                || (EDGE_COUNT (bb->succs) == 1
                                    && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
                                        == JUMP_LABEL (head))));
...

It triggered on this rtl, a conditional return followed by a barrier:
...
(jump_insn 44 43 93 7 (set (pc)
	(if_then_else (ne (reg:CC 24 cc)
                (const_int 0 [0]))
            (return)
            (pc))) gcc/testsuite/gcc.dg/builtin-unreachable-4.c:13 249
{*cond_return}
     (expr_list:REG_DEAD (reg:CC 24 cc)
        (expr_list:REG_BR_PROB (const_int 9996 [0x270c])
            (nil)))
 -> return)

(barrier 93 44 92)
...

Although this insn sequence is non-optimal (the conditional return can be
optimized to an unconditional one, given that it's followed by a barrier), it's
not incorrect. The patch fixes this ICE by removing the check for the
'EDGE_COUNT (bb->succs) == 1' case.

Bootstrapped and reg-tested on x86_64 and build and reg-tested on arm.

OK for trunk?

Thanks,
- Tom

2011-09-05  Tom de Vries  <tom@codesourcery.com>

	* haifa-sched.c (check_cfg): Remove restriction on conditional jump if
	the containing block has only 1 outgoing edge.

[-- Attachment #2: check_cfg-fix.patch --]
[-- Type: text/x-patch, Size: 1074 bytes --]

Index: gcc/haifa-sched.c
===================================================================
--- gcc/haifa-sched.c (revision 178145)
+++ gcc/haifa-sched.c (working copy)
@@ -6065,13 +6065,12 @@ check_cfg (rtx head, rtx tail)
 		    gcc_assert (EDGE_COUNT (bb->succs) == 1
 				&& BARRIER_P (NEXT_INSN (head)));
 		  else if (any_condjump_p (head))
-		    gcc_assert (/* Usual case.  */
-                                (EDGE_COUNT (bb->succs) > 1
-                                 && !BARRIER_P (NEXT_INSN (head)))
-                                /* Or jump to the next instruction.  */
-                                || (EDGE_COUNT (bb->succs) == 1
-                                    && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
-                                        == JUMP_LABEL (head))));
+		    gcc_assert (/* Weird case, like jump to the next insn
+				   or use of __builtin_unreachable ().  */
+				EDGE_COUNT (bb->succs) == 1
+				/* Normal case, one path falls through.  */
+				|| !BARRIER_P (NEXT_INSN (head)));
+
 		}
 	      if (BB_END (bb) == head)
 		{

Re: [PATCH] check_cfg assert fix

[Steven Bosscher]

On Tue, Sep 6, 2011 at 11:14 AM, Tom de Vries <vries@codesourcery.com> wrote:
> Hi,
>
> During testing the approved-for-commit middle-end patch for bug 43864 on ARM, I
> ran into a gcc.dg/torture/pr46068.c ICE.
>
> The following assert in haifa-sched.c:check_cfg triggered:
> ...
>                  else if (any_condjump_p (head))
>                    gcc_assert (/* Usual case.  */
>                                (EDGE_COUNT (bb->succs) > 1
>                                 && !BARRIER_P (NEXT_INSN (head)))
>                                /* Or jump to the next instruction.  */
>                                || (EDGE_COUNT (bb->succs) == 1
>                                    && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
>                                        == JUMP_LABEL (head))));
> ...
>
> It triggered on this rtl, a conditional return followed by a barrier:
> ...
> (jump_insn 44 43 93 7 (set (pc)
>        (if_then_else (ne (reg:CC 24 cc)
>                (const_int 0 [0]))
>            (return)
>            (pc))) gcc/testsuite/gcc.dg/builtin-unreachable-4.c:13 249
> {*cond_return}
>     (expr_list:REG_DEAD (reg:CC 24 cc)
>        (expr_list:REG_BR_PROB (const_int 9996 [0x270c])
>            (nil)))
>  -> return)
>
> (barrier 93 44 92)
> ...
>
> Although this insn sequence is non-optimal (the conditional return can be
> optimized to an unconditional one, given that it's followed by a barrier), it's
> not incorrect. The patch fixes this ICE by removing the check for the
> 'EDGE_COUNT (bb->succs) == 1' case.
>
> Bootstrapped and reg-tested on x86_64 and build and reg-tested on arm.
>
> OK for trunk?

No. If the conditional return is not taken, you should not fall into a
barrier. It looks like the CFG somehow got corrupted, and if that's
indeed the case then your patch just papers over the problem. That
follows after the barrier?

Ciao!
Steven

Re: [PATCH] check_cfg assert fix

[Maxim Kuvyrkov]

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


On 7/09/2011, at 3:13 AM, Steven Bosscher wrote:

> On Tue, Sep 6, 2011 at 11:14 AM, Tom de Vries <vries@codesourcery.com> wrote:
>> Hi,
>> 
>> During testing the approved-for-commit middle-end patch for bug 43864 on ARM, I
>> ran into a gcc.dg/torture/pr46068.c ICE.
>> 
>> The following assert in haifa-sched.c:check_cfg triggered:
>> ...
>>                  else if (any_condjump_p (head))
>>                    gcc_assert (/* Usual case.  */
>>                                (EDGE_COUNT (bb->succs) > 1
>>                                 && !BARRIER_P (NEXT_INSN (head)))
>>                                /* Or jump to the next instruction.  */
>>                                || (EDGE_COUNT (bb->succs) == 1
>>                                    && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
>>                                        == JUMP_LABEL (head))));
>> 
...
>> Bootstrapped and reg-tested on x86_64 and build and reg-tested on arm.
>> 
>> OK for trunk?
> 
> No. If the conditional return is not taken, you should not fall into a
> barrier. It looks like the CFG somehow got corrupted, and if that's
> indeed the case then your patch just papers over the problem. That
> follows after the barrier?

Initially, I thought so too, that is why I wrote the above assert in the first place.  However, __builtin_unreachable() adds a whole new spin on where a BARRIER can occur; after all, this built-in expands directly to BARRIER.

Before Tom's optimization the fall-through path of conditional jump was followed by an unconditional jump to a label directly followed by a barrier.  Tom's patch removed the middle-man in the face of unconditional jump so that the barrier now follows a conditional jump.  This is very odd, but, given the initial test case, is a valid case.

For reference, the test case in question:

/* { dg-do compile } */

void
foo ()
{
  asm goto (""::::l1);
  __builtin_unreachable ();
l1:;
}

void
bar ()
{
  foo ();
  foo ();
}

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics



[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 1795 bytes --]

Re: [PATCH] check_cfg assert fix

[Steven Bosscher]

On Tue, Sep 6, 2011 at 8:00 PM, Maxim Kuvyrkov <maxim@codesourcery.com> wrote:
>
> On 7/09/2011, at 3:13 AM, Steven Bosscher wrote:
>
>> On Tue, Sep 6, 2011 at 11:14 AM, Tom de Vries <vries@codesourcery.com> wrote:
>>> Hi,
>>>
>>> During testing the approved-for-commit middle-end patch for bug 43864 on ARM, I
>>> ran into a gcc.dg/torture/pr46068.c ICE.
>>>
>>> The following assert in haifa-sched.c:check_cfg triggered:
>>> ...
>>>                  else if (any_condjump_p (head))
>>>                    gcc_assert (/* Usual case.  */
>>>                                (EDGE_COUNT (bb->succs) > 1
>>>                                 && !BARRIER_P (NEXT_INSN (head)))
>>>                                /* Or jump to the next instruction.  */
>>>                                || (EDGE_COUNT (bb->succs) == 1
>>>                                    && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
>>>                                        == JUMP_LABEL (head))));
>>>
> ...
>>> Bootstrapped and reg-tested on x86_64 and build and reg-tested on arm.
>>>
>>> OK for trunk?
>>
>> No. If the conditional return is not taken, you should not fall into a
>> barrier. It looks like the CFG somehow got corrupted, and if that's
>> indeed the case then your patch just papers over the problem. That
>> follows after the barrier?
>
> Initially, I thought so too, that is why I wrote the above assert in the first place.  However, __builtin_unreachable() adds a whole new spin on where a BARRIER can occur; after all, this built-in expands directly to BARRIER.
>
> Before Tom's optimization the fall-through path of conditional jump was followed by an unconditional jump to a label directly followed by a barrier.  Tom's patch removed the middle-man in the face of unconditional jump so that the barrier now follows a conditional jump.  This is very odd, but, given the initial test case, is a valid case.

Well, shouldn't the assert be changed then to handle !onlyjump_p and
returnjump_p cases separately? Tom's patch removes a valid check for
all but these corner cases. Perhaps something like this:

Index: haifa-sched.c
===================================================================
--- haifa-sched.c	(revision 178601)
+++ haifa-sched.c	(working copy)
@@ -6071,7 +6071,10 @@ check_cfg (rtx head, rtx tail)
                                 /* Or jump to the next instruction.  */
                                 || (EDGE_COUNT (bb->succs) == 1
                                     && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
-                                        == JUMP_LABEL (head))));
+                                        == JUMP_LABEL (head)))
+				/* Or the jump is not just a jump.  */
+				|| (!onlyjump_p (head)
+				    || returnjump_p (head)));
 		}
 	      if (BB_END (bb) == head)
 		{


Ciao!
Steven

Re: [PATCH] check_cfg assert fix

[Steven Bosscher]

On Tue, Sep 6, 2011 at 11:31 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Index: haifa-sched.c
> ===================================================================
> --- haifa-sched.c       (revision 178601)
> +++ haifa-sched.c       (working copy)
> @@ -6071,7 +6071,10 @@ check_cfg (rtx head, rtx tail)
>                                 /* Or jump to the next instruction.  */
>                                 || (EDGE_COUNT (bb->succs) == 1
>                                     && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
> -                                        == JUMP_LABEL (head))));
> +                                        == JUMP_LABEL (head)))
> +                               /* Or the jump is not just a jump.  */
> +                               || (!onlyjump_p (head)
> +                                   || returnjump_p (head)));
>                }
>              if (BB_END (bb) == head)
>                {
>

BTW that's one ugly gcc_assert. Candidate for gcc_checking_assert?

Ciao!
Steven

Re: [PATCH] check_cfg assert fix

[Maxim Kuvyrkov]

On 7/09/2011, at 9:32 AM, Steven Bosscher wrote:

> On Tue, Sep 6, 2011 at 11:31 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
>> Index: haifa-sched.c
>> ===================================================================
>> --- haifa-sched.c       (revision 178601)
>> +++ haifa-sched.c       (working copy)
>> @@ -6071,7 +6071,10 @@ check_cfg (rtx head, rtx tail)
>>                                 /* Or jump to the next instruction.  */
>>                                 || (EDGE_COUNT (bb->succs) == 1
>>                                     && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
>> -                                        == JUMP_LABEL (head))));
>> +                                        == JUMP_LABEL (head)))
>> +                               /* Or the jump is not just a jump.  */
>> +                               || (!onlyjump_p (head)
>> +                                   || returnjump_p (head)));
>>                }
>>              if (BB_END (bb) == head)
>>                {
>> 
> 
> BTW that's one ugly gcc_assert. Candidate for gcc_checking_assert?

I agree.  I would rather remove the entirety of haifa-sched.c: check_cfg(); scheduler is not the right place for checking consistency of CFG.  Check_cfg() was useful for debugging scheduler patches, but now it is more of maintainance overhead.

Do I have a second vote for removal of check_cfg()?

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics

Re: [PATCH] check_cfg assert fix

[Bernd Schmidt]

On 09/06/11 23:56, Maxim Kuvyrkov wrote:
> I agree.  I would rather remove the entirety of haifa-sched.c:
> check_cfg(); scheduler is not the right place for checking
> consistency of CFG.  Check_cfg() was useful for debugging scheduler
> patches, but now it is more of maintainance overhead.
> 
> Do I have a second vote for removal of check_cfg()?

I'd be OK with that. Saves me some time adapting it to some scheduler
patches I'll be submitting soon...


Bernd

Re: [PATCH] check_cfg assert fix

[Maxim Kuvyrkov]

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

On 9/09/2011, at 6:54 AM, Bernd Schmidt wrote:

> On 09/06/11 23:56, Maxim Kuvyrkov wrote:
>> I agree.  I would rather remove the entirety of haifa-sched.c:
>> check_cfg(); scheduler is not the right place for checking
>> consistency of CFG.  Check_cfg() was useful for debugging scheduler
>> patches, but now it is more of maintainance overhead.
>> 
>> Do I have a second vote for removal of check_cfg()?
> 
> I'd be OK with that. Saves me some time adapting it to some scheduler
> patches I'll be submitting soon...

OK then, attached is the trivial patch that removes haifa-sched.c:check_cfg().  Please let me know if you have strong feelings towards keeping check_cfg().

Tested on x86_64-linux-gnu.  Absent any requests to the contrary, I will check in this patch in 2 days.

Thank you,

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics


[-- Attachment #2: fsf-gcc-check-cfg.ChangeLog --]
[-- Type: application/octet-stream, Size: 193 bytes --]

2011-09-14  Maxim Kuvyrkov  <maxim@codesourcery.com>

	* haifa-sched.c (has_edge_p, prev_non_location_insn, check_cfg):
	Remove maintenance overhead.
	(haifa_sched_init, sched_finish): Update.

[-- Attachment #3: fsf-gcc-check-cfg.patch --]
[-- Type: application/octet-stream, Size: 4984 bytes --]

Index: gcc/haifa-sched.c
===================================================================
--- gcc/haifa-sched.c	(revision 178820)
+++ gcc/haifa-sched.c	(working copy)
@@ -717,10 +717,6 @@ static void sched_remove_insn (rtx);
 static void clear_priorities (rtx, rtx_vec_t *);
 static void calc_priorities (rtx_vec_t);
 static void add_jump_dependencies (rtx, rtx);
-#ifdef ENABLE_CHECKING
-static int has_edge_p (VEC(edge,gc) *, int);
-static void check_cfg (rtx, rtx);
-#endif
 
 #endif /* INSN_SCHEDULING */
 \f
@@ -4303,13 +4299,6 @@ haifa_sched_init (void)
   sched_create_empty_bb = sched_create_empty_bb_1;
   haifa_recovery_bb_ever_added_p = false;
 
-#ifdef ENABLE_CHECKING
-  /* This is used preferably for finding bugs in check_cfg () itself.
-     We must call sched_bbs_init () before check_cfg () because check_cfg ()
-     assumes that the last insn in the last bb has a non-null successor.  */
-  check_cfg (0, 0);
-#endif
-
   nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
   before_recovery = 0;
   after_recovery = 0;
@@ -4378,12 +4367,6 @@ sched_finish (void)
   regstat_free_calls_crossed ();
 
   dfa_finish ();
-
-#ifdef ENABLE_CHECKING
-  /* After reload ia64 backend clobbers CFG, so can't check anything.  */
-  if (!reload_completed)
-    check_cfg (0, 0);
-#endif
 }
 
 /* Free all delay_pair structures that were recorded.  */
@@ -5970,131 +5953,6 @@ bb_note (basic_block bb)
   return note;
 }
 
-#ifdef ENABLE_CHECKING
-/* Helper function for check_cfg.
-   Return nonzero, if edge vector pointed to by EL has edge with TYPE in
-   its flags.  */
-static int
-has_edge_p (VEC(edge,gc) *el, int type)
-{
-  edge e;
-  edge_iterator ei;
-
-  FOR_EACH_EDGE (e, ei, el)
-    if (e->flags & type)
-      return 1;
-  return 0;
-}
-
-/* Search back, starting at INSN, for an insn that is not a
-   NOTE_INSN_VAR_LOCATION.  Don't search beyond HEAD, and return it if
-   no such insn can be found.  */
-static inline rtx
-prev_non_location_insn (rtx insn, rtx head)
-{
-  while (insn != head && NOTE_P (insn)
-	 && NOTE_KIND (insn) == NOTE_INSN_VAR_LOCATION)
-    insn = PREV_INSN (insn);
-
-  return insn;
-}
-
-/* Check few properties of CFG between HEAD and TAIL.
-   If HEAD (TAIL) is NULL check from the beginning (till the end) of the
-   instruction stream.  */
-static void
-check_cfg (rtx head, rtx tail)
-{
-  rtx next_tail;
-  basic_block bb = 0;
-  int not_first = 0, not_last;
-
-  if (head == NULL)
-    head = get_insns ();
-  if (tail == NULL)
-    tail = get_last_insn ();
-  next_tail = NEXT_INSN (tail);
-
-  do
-    {
-      not_last = head != tail;
-
-      if (not_first)
-	gcc_assert (NEXT_INSN (PREV_INSN (head)) == head);
-      if (not_last)
-	gcc_assert (PREV_INSN (NEXT_INSN (head)) == head);
-
-      if (LABEL_P (head)
-	  || (NOTE_INSN_BASIC_BLOCK_P (head)
-	      && (!not_first
-		  || (not_first && !LABEL_P (PREV_INSN (head))))))
-	{
-	  gcc_assert (bb == 0);
-	  bb = BLOCK_FOR_INSN (head);
-	  if (bb != 0)
-	    gcc_assert (BB_HEAD (bb) == head);
-	  else
-	    /* This is the case of jump table.  See inside_basic_block_p ().  */
-	    gcc_assert (LABEL_P (head) && !inside_basic_block_p (head));
-	}
-
-      if (bb == 0)
-	{
-	  gcc_assert (!inside_basic_block_p (head));
-	  head = NEXT_INSN (head);
-	}
-      else
-	{
-	  gcc_assert (inside_basic_block_p (head)
-		      || NOTE_P (head));
-	  gcc_assert (BLOCK_FOR_INSN (head) == bb);
-
-	  if (LABEL_P (head))
-	    {
-	      head = NEXT_INSN (head);
-	      gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head));
-	    }
-	  else
-	    {
-	      if (control_flow_insn_p (head))
-		{
-		  gcc_assert (prev_non_location_insn (BB_END (bb), head)
-			      == head);
-
-		  if (any_uncondjump_p (head))
-		    gcc_assert (EDGE_COUNT (bb->succs) == 1
-				&& BARRIER_P (NEXT_INSN (head)));
-		  else if (any_condjump_p (head))
-		    gcc_assert (/* Usual case.  */
-                                (EDGE_COUNT (bb->succs) > 1
-                                 && !BARRIER_P (NEXT_INSN (head)))
-                                /* Or jump to the next instruction.  */
-                                || (EDGE_COUNT (bb->succs) == 1
-                                    && (BB_HEAD (EDGE_I (bb->succs, 0)->dest)
-                                        == JUMP_LABEL (head))));
-		}
-	      if (BB_END (bb) == head)
-		{
-		  if (EDGE_COUNT (bb->succs) > 1)
-		    gcc_assert (control_flow_insn_p (prev_non_location_insn
-						     (head, BB_HEAD (bb)))
-				|| has_edge_p (bb->succs, EDGE_COMPLEX));
-		  bb = 0;
-		}
-
-	      head = NEXT_INSN (head);
-	    }
-	}
-
-      not_first = 1;
-    }
-  while (head != next_tail);
-
-  gcc_assert (bb == 0);
-}
-
-#endif /* ENABLE_CHECKING */
-
 /* Extend data structures for logical insn UID.  */
 void
 sched_extend_luids (void)

Re: [PATCH] check_cfg assert fix

[Maxim Kuvyrkov]

On 14/09/2011, at 7:40 AM, Maxim Kuvyrkov wrote:
> 
> OK then, attached is the trivial patch that removes haifa-sched.c:check_cfg().  Please let me know if you have strong feelings towards keeping check_cfg().
> 
> Tested on x86_64-linux-gnu.  Absent any requests to the contrary, I will check in this patch in 2 days.

Checked in.

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics