[PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[David Malcolm]

PR rtl-optimization/88423 reports an ICE within sched-ebb.c's
begin_move_insn, failing the assertion at line 175, where there's
no fall-through edge:

171         rtx_insn *x = NEXT_INSN (insn);
172         if (e)
173           gcc_checking_assert (NOTE_P (x) || LABEL_P (x));
174         else
175           gcc_checking_assert (BARRIER_P (x));

"insn" is a jump_insn for a table jump, and its NEXT_INSN is the
placeholder code_label, followed by the jump_table_data.

It's not clear to me if such a jump_insn can be repositioned within
the insn stream, or if the scheduler is able to do so.  I believe a
tablejump is always at the end of such a head/tail insn sub-stream.
Is it a requirement that the placeholder code_label for the jump_insn
is always its NEXT_INSN?

The loop at the start of schedule_ebb adjusts the head and tail
of the insns to be scheduled so that it skips leading and trailing notes
and debug insns.

This patch adjusts that loop to also skip trailing jump_insn instances
that are table jumps, so that we don't attempt to move such table jumps.

This fixes the ICE, but I'm not very familiar with this part of the
compiler - so I have two questions:

(1) What does GCC mean by "ebb" in this context?

My understanding is that the normal definition of an "extended basic
block" (e.g. Muchnick's book pp175-177) is that it's a maximal grouping
of basic blocks where only one BB in each group has multiple in-edges
and all other BBs in the group have a single in-edge (and thus e.g.
there's a tree-like structure of BBs within each EBB).

From what I can tell, schedule_ebbs is iterating over BBs, looking for
runs of BBs joined by next_bb that are connected by fallthrough edges
and don't have labels (and aren't flagged with BB_DISABLE_SCHEDULE).
It uses this run of BBs to generate a run of instructions within the
NEXT_INSN/PREV_INSN doubly-linked list, which it passes as "head"
and "tail" to schedule_ebb.

This sounds like it will be a group of basic blocks with single in-edges
internally, but it isn't a *maximal* group of such BBs - but perhaps
it's "maximal" in the sense of what the NEXT_INSN/PREV_INSN
representation can cope with?

There (presumably) can't be a fallthrough edge after a table jump, so
a table jump could only ever be at the end of such a chain, never in the
middle.

(2) Is it OK to omit "tail" from consideration here, from a dataflow
and insn-dependency point-of-view?  Presumably the scheduler is written
to ensure that data used by subsequent basic blocks will still be available
after the insns within an "EBB" are reordered, so presumably any data
uses *within* the jump_insn are still going to be available - but, as I
said, I'm not very familiar with this part of the code.  (I think I'm also
assuming that the jump_insn can't clobber data, just the PC)

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.

OK for trunk?

gcc/ChangeLog:
	PR rtl-optimization/88423
	* sched-ebb.c (schedule_ebb): Don't move the jump_insn for a table
	jump.

gcc/testsuite/ChangeLog:
	PR rtl-optimization/88423
	* gcc.c-torture/compile/pr88423.c: New test.
---
 gcc/sched-ebb.c                               | 4 ++++
 gcc/testsuite/gcc.c-torture/compile/pr88423.c | 5 +++++
 2 files changed, 9 insertions(+)
 create mode 100644 gcc/testsuite/gcc.c-torture/compile/pr88423.c

diff --git a/gcc/sched-ebb.c b/gcc/sched-ebb.c
index d459e09..1fe0b76 100644
--- a/gcc/sched-ebb.c
+++ b/gcc/sched-ebb.c
@@ -485,6 +485,10 @@ schedule_ebb (rtx_insn *head, rtx_insn *tail, bool modulo_scheduling)
 	tail = PREV_INSN (tail);
       else if (LABEL_P (head))
 	head = NEXT_INSN (head);
+      else if (tablejump_p (tail, NULL, NULL))
+	/* Don't move a jump_insn for a tablejump, to avoid having
+	   to move the placeholder code_label and jump_table_data. */
+	tail = PREV_INSN (tail);
       else
 	break;
     }
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr88423.c b/gcc/testsuite/gcc.c-torture/compile/pr88423.c
new file mode 100644
index 0000000..4948817
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/compile/pr88423.c
@@ -0,0 +1,5 @@
+/* { dg-do compile { target { i?86-*-* x86_64-*-* } } } */
+/* { dg-options "-march=skylake -fPIC -fsched2-use-superblocks -fno-if-conversion" } */
+/* { dg-require-effective-target fpic } */
+
+#include "../../gcc.dg/20030309-1.c"
-- 
1.8.5.3

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[David Malcolm]

On Fri, 2019-01-18 at 12:32 -0500, David Malcolm wrote:

[CCing Abel]

> PR rtl-optimization/88423 reports an ICE within sched-ebb.c's
> begin_move_insn, failing the assertion at line 175, where there's
> no fall-through edge:
> 
> 171         rtx_insn *x = NEXT_INSN (insn);
> 172         if (e)
> 173           gcc_checking_assert (NOTE_P (x) || LABEL_P (x));
> 174         else
> 175           gcc_checking_assert (BARRIER_P (x));
> 
> "insn" is a jump_insn for a table jump, and its NEXT_INSN is the
> placeholder code_label, followed by the jump_table_data.
> 
> It's not clear to me if such a jump_insn can be repositioned within
> the insn stream, or if the scheduler is able to do so.  I believe a
> tablejump is always at the end of such a head/tail insn sub-stream.
> Is it a requirement that the placeholder code_label for the jump_insn
> is always its NEXT_INSN?
> 
> The loop at the start of schedule_ebb adjusts the head and tail
> of the insns to be scheduled so that it skips leading and trailing
> notes
> and debug insns.
> 
> This patch adjusts that loop to also skip trailing jump_insn
> instances
> that are table jumps, so that we don't attempt to move such table
> jumps.
> 
> This fixes the ICE, but I'm not very familiar with this part of the
> compiler - so I have two questions:
> 
> (1) What does GCC mean by "ebb" in this context?
> 
> My understanding is that the normal definition of an "extended basic
> block" (e.g. Muchnick's book pp175-177) is that it's a maximal
> grouping
> of basic blocks where only one BB in each group has multiple in-edges
> and all other BBs in the group have a single in-edge (and thus e.g.
> there's a tree-like structure of BBs within each EBB).
> 
> From what I can tell, schedule_ebbs is iterating over BBs, looking
> for
> runs of BBs joined by next_bb that are connected by fallthrough edges
> and don't have labels (and aren't flagged with BB_DISABLE_SCHEDULE).
> It uses this run of BBs to generate a run of instructions within the
> NEXT_INSN/PREV_INSN doubly-linked list, which it passes as "head"
> and "tail" to schedule_ebb.
> 
> This sounds like it will be a group of basic blocks with single in-
> edges
> internally, but it isn't a *maximal* group of such BBs - but perhaps
> it's "maximal" in the sense of what the NEXT_INSN/PREV_INSN
> representation can cope with?
> 
> There (presumably) can't be a fallthrough edge after a table jump, so
> a table jump could only ever be at the end of such a chain, never in
> the
> middle.
> 
> (2) Is it OK to omit "tail" from consideration here, from a dataflow
> and insn-dependency point-of-view?  Presumably the scheduler is
> written
> to ensure that data used by subsequent basic blocks will still be
> available
> after the insns within an "EBB" are reordered, so presumably any data
> uses *within* the jump_insn are still going to be available - but, as
> I
> said, I'm not very familiar with this part of the code.  (I think I'm
> also
> assuming that the jump_insn can't clobber data, just the PC)
> 
> Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
> 
> OK for trunk?
> 
> gcc/ChangeLog:
> 	PR rtl-optimization/88423
> 	* sched-ebb.c (schedule_ebb): Don't move the jump_insn for a
> table
> 	jump.
> 
> gcc/testsuite/ChangeLog:
> 	PR rtl-optimization/88423
> 	* gcc.c-torture/compile/pr88423.c: New test.
> ---
>  gcc/sched-ebb.c                               | 4 ++++
>  gcc/testsuite/gcc.c-torture/compile/pr88423.c | 5 +++++
>  2 files changed, 9 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.c-torture/compile/pr88423.c
> 
> diff --git a/gcc/sched-ebb.c b/gcc/sched-ebb.c
> index d459e09..1fe0b76 100644
> --- a/gcc/sched-ebb.c
> +++ b/gcc/sched-ebb.c
> @@ -485,6 +485,10 @@ schedule_ebb (rtx_insn *head, rtx_insn *tail,
> bool modulo_scheduling)
>  	tail = PREV_INSN (tail);
>        else if (LABEL_P (head))
>  	head = NEXT_INSN (head);
> +      else if (tablejump_p (tail, NULL, NULL))
> +	/* Don't move a jump_insn for a tablejump, to avoid having
> +	   to move the placeholder code_label and jump_table_data.
> */
> +	tail = PREV_INSN (tail);
>        else
>  	break;
>      }
> diff --git a/gcc/testsuite/gcc.c-torture/compile/pr88423.c
> b/gcc/testsuite/gcc.c-torture/compile/pr88423.c
> new file mode 100644
> index 0000000..4948817
> --- /dev/null
> +++ b/gcc/testsuite/gcc.c-torture/compile/pr88423.c
> @@ -0,0 +1,5 @@
> +/* { dg-do compile { target { i?86-*-* x86_64-*-* } } } */
> +/* { dg-options "-march=skylake -fPIC -fsched2-use-superblocks -fno-
> if-conversion" } */
> +/* { dg-require-effective-target fpic } */
> +
> +#include "../../gcc.dg/20030309-1.c"

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Andrey Belevantsev]

Hi David,

On 18.01.2019 19:58, David Malcolm wrote:
> On Fri, 2019-01-18 at 12:32 -0500, David Malcolm wrote:
> 
> [CCing Abel]
> 
>> PR rtl-optimization/88423 reports an ICE within sched-ebb.c's
>> begin_move_insn, failing the assertion at line 175, where there's
>> no fall-through edge:
>>
>> 171         rtx_insn *x = NEXT_INSN (insn);
>> 172         if (e)
>> 173           gcc_checking_assert (NOTE_P (x) || LABEL_P (x));
>> 174         else
>> 175           gcc_checking_assert (BARRIER_P (x));
>>
>> "insn" is a jump_insn for a table jump, and its NEXT_INSN is the
>> placeholder code_label, followed by the jump_table_data.

This code was added at the time of our work for the speculation support in
ia64.  I would guess it was just never designed to support tablejumps,
rather the jumps to recovery blocks or some such.  But I might be wrong, it
was back in 2006.  If you look at fix_jump_move, which was added about that
time, it doesn't have any traces of tablejumps as well.

>>
>> It's not clear to me if such a jump_insn can be repositioned within
>> the insn stream, or if the scheduler is able to do so.  I believe a
>> tablejump is always at the end of such a head/tail insn sub-stream.
>> Is it a requirement that the placeholder code_label for the jump_insn
>> is always its NEXT_INSN?
>>
>> The loop at the start of schedule_ebb adjusts the head and tail
>> of the insns to be scheduled so that it skips leading and trailing
>> notes
>> and debug insns.
>>
>> This patch adjusts that loop to also skip trailing jump_insn
>> instances
>> that are table jumps, so that we don't attempt to move such table
>> jumps.
>>
>> This fixes the ICE, but I'm not very familiar with this part of the
>> compiler - so I have two questions:
>>
>> (1) What does GCC mean by "ebb" in this context?
>>
>> My understanding is that the normal definition of an "extended basic
>> block" (e.g. Muchnick's book pp175-177) is that it's a maximal
>> grouping
>> of basic blocks where only one BB in each group has multiple in-edges
>> and all other BBs in the group have a single in-edge (and thus e.g.
>> there's a tree-like structure of BBs within each EBB).
>>
>> From what I can tell, schedule_ebbs is iterating over BBs, looking
>> for
>> runs of BBs joined by next_bb that are connected by fallthrough edges
>> and don't have labels (and aren't flagged with BB_DISABLE_SCHEDULE).
>> It uses this run of BBs to generate a run of instructions within the
>> NEXT_INSN/PREV_INSN doubly-linked list, which it passes as "head"
>> and "tail" to schedule_ebb.
>>
>> This sounds like it will be a group of basic blocks with single in-
>> edges
>> internally, but it isn't a *maximal* group of such BBs - but perhaps
>> it's "maximal" in the sense of what the NEXT_INSN/PREV_INSN
>> representation can cope with?

You are right, it's not a tree structure in the sense of classical EBBs but
rather a trace.  There was a code to also perform tail duplication in order
to have better traces for scheduling, but the corresponding option got
deprecated back in 2010.

>>
>> There (presumably) can't be a fallthrough edge after a table jump, so
>> a table jump could only ever be at the end of such a chain, never in
>> the
>> middle.
>>
>> (2) Is it OK to omit "tail" from consideration here, from a dataflow
>> and insn-dependency point-of-view?  Presumably the scheduler is
>> written
>> to ensure that data used by subsequent basic blocks will still be
>> available
>> after the insns within an "EBB" are reordered, so presumably any data
>> uses *within* the jump_insn are still going to be available - but, as
>> I
>> said, I'm not very familiar with this part of the code.  (I think I'm
>> also
>> assuming that the jump_insn can't clobber data, just the PC)

For that, I'm not sure.  Your patch will leave the tablejump unscheduled at
all, i.e. any fields like INSN_TICK would be unfilled and thus the later
passes like bundling on ia64 will not work.  Maybe we can just stop
tablejumps from moving within its block, Alexander?

Andrey

>>
>> Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
>>
>> OK for trunk?
>>
>> gcc/ChangeLog:
>> 	PR rtl-optimization/88423
>> 	* sched-ebb.c (schedule_ebb): Don't move the jump_insn for a
>> table
>> 	jump.
>>
>> gcc/testsuite/ChangeLog:
>> 	PR rtl-optimization/88423
>> 	* gcc.c-torture/compile/pr88423.c: New test.
>> ---
>>  gcc/sched-ebb.c                               | 4 ++++
>>  gcc/testsuite/gcc.c-torture/compile/pr88423.c | 5 +++++
>>  2 files changed, 9 insertions(+)
>>  create mode 100644 gcc/testsuite/gcc.c-torture/compile/pr88423.c
>>
>> diff --git a/gcc/sched-ebb.c b/gcc/sched-ebb.c
>> index d459e09..1fe0b76 100644
>> --- a/gcc/sched-ebb.c
>> +++ b/gcc/sched-ebb.c
>> @@ -485,6 +485,10 @@ schedule_ebb (rtx_insn *head, rtx_insn *tail,
>> bool modulo_scheduling)
>>  	tail = PREV_INSN (tail);
>>        else if (LABEL_P (head))
>>  	head = NEXT_INSN (head);
>> +      else if (tablejump_p (tail, NULL, NULL))
>> +	/* Don't move a jump_insn for a tablejump, to avoid having
>> +	   to move the placeholder code_label and jump_table_data.
>> */
>> +	tail = PREV_INSN (tail);
>>        else
>>  	break;
>>      }
>> diff --git a/gcc/testsuite/gcc.c-torture/compile/pr88423.c
>> b/gcc/testsuite/gcc.c-torture/compile/pr88423.c
>> new file mode 100644
>> index 0000000..4948817
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.c-torture/compile/pr88423.c
>> @@ -0,0 +1,5 @@
>> +/* { dg-do compile { target { i?86-*-* x86_64-*-* } } } */
>> +/* { dg-options "-march=skylake -fPIC -fsched2-use-superblocks -fno-
>> if-conversion" } */
>> +/* { dg-require-effective-target fpic } */
>> +
>> +#include "../../gcc.dg/20030309-1.c"

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Alexander Monakov]

On Wed, 23 Jan 2019, Andrey Belevantsev wrote:

> For that, I'm not sure.  Your patch will leave the tablejump unscheduled at
> all, i.e. any fields like INSN_TICK would be unfilled and thus the later
> passes like bundling on ia64 will not work.  Maybe we can just stop
> tablejumps from moving within its block, Alexander?

On the Bugzilla there's an alternative patch by Segher that adjusts the assert
to accept this situation (there's still a barrier insn after the tablejump insn,
it's just after a jump_table_data insn rather than immediately following the
jump).  That should be a better approach, and David said he was testing it.

That said, I'm really concerned that on this testcase we should not be moving
the tablejump *at all*: we are moving it up past a 'use ax' insn (the use is
for the function's return value). So after the move the use is in an unreachable
block, which makes no sense.

So my concern is that just fixing the assert changes the issue from the ICE to a
(latent) wrong-code issue.

There should have been an anti-dependence between the use and the jump. I'll try
to investigate.

Alexander

[PATCH] Update assertion in sched-ebb.c to cope with table jumps

[David Malcolm]

On Wed, 2019-01-23 at 16:52 +0300, Alexander Monakov wrote:
> On Wed, 23 Jan 2019, Andrey Belevantsev wrote:
> 
> > For that, I'm not sure.  Your patch will leave the tablejump
> > unscheduled at
> > all, i.e. any fields like INSN_TICK would be unfilled and thus the
> > later
> > passes like bundling on ia64 will not work.  Maybe we can just stop
> > tablejumps from moving within its block, Alexander?
> 
> On the Bugzilla there's an alternative patch by Segher that adjusts
> the assert
> to accept this situation (there's still a barrier insn after the
> tablejump insn,
> it's just after a jump_table_data insn rather than immediately
> following the
> jump).  That should be a better approach, and David said he was
> testing it.
> 
> That said, I'm really concerned that on this testcase we should not
> be moving
> the tablejump *at all*: we are moving it up past a 'use ax' insn (the
> use is
> for the function's return value). So after the move the use is in an
> unreachable
> block, which makes no sense.
> 
> So my concern is that just fixing the assert changes the issue from
> the ICE to a
> (latent) wrong-code issue.
> 
> There should have been an anti-dependence between the use and the
> jump. I'll try
> to investigate.
> 
> Alexander

Thanks everyone for their clarifications (this is somewhat outside
my normal comfort zone of diagnostics/frontend stuff...)

Here's Segher's patch to sched-ebb.c, along with a couple of compile-only
testcases I put together (which triggered ICEs on x86_64 and powerpc
without the sched-ebb.c fix).

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu, and this
fixes the ICE in the the powerpc testcase.

That said, I share your concern that this might be papering over a
latent wrong-code issue.

Dave

gcc/ChangeLog:
	PR rtl-optimization/88347
	PR rtl-optimization/88423
	* sched-ebb.c (begin_move_insn): Update assertion to handle table
	jumps.

gcc/testsuite/ChangeLog:
	PR rtl-optimization/88347
	PR rtl-optimization/88423
	* gcc.c-torture/compile/pr88347.c: New test.
	* gcc.c-torture/compile/pr88423.c: New test.
---
 gcc/sched-ebb.c                               | 6 +++++-
 gcc/testsuite/gcc.c-torture/compile/pr88347.c | 4 ++++
 gcc/testsuite/gcc.c-torture/compile/pr88423.c | 5 +++++
 3 files changed, 14 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.c-torture/compile/pr88347.c
 create mode 100644 gcc/testsuite/gcc.c-torture/compile/pr88423.c

diff --git a/gcc/sched-ebb.c b/gcc/sched-ebb.c
index d459e09..76a72b0 100644
--- a/gcc/sched-ebb.c
+++ b/gcc/sched-ebb.c
@@ -172,7 +172,11 @@ begin_move_insn (rtx_insn *insn, rtx_insn *last)
 	if (e)
 	  gcc_checking_assert (NOTE_P (x) || LABEL_P (x));
 	else
-	  gcc_checking_assert (BARRIER_P (x));
+	  {
+	    if (LABEL_P (x) && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
+	      x = NEXT_INSN (NEXT_INSN (x));
+	    gcc_checking_assert (BARRIER_P (x));
+	  }
       }
 
       if (e)
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr88347.c b/gcc/testsuite/gcc.c-torture/compile/pr88347.c
new file mode 100644
index 0000000..4e9b438
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/compile/pr88347.c
@@ -0,0 +1,4 @@
+/* { dg-do compile { target { powerpc-*-* powerpcle-*-* } } } */
+/* { dg-options "-mcpu=603e -fsched-stalled-insns -fsched2-use-superblocks -fschedule-insns2 -fno-dce -fno-guess-branch-probability --param max-cse-insns=4" } */
+
+#include "../../gcc.target/powerpc/ppc-switch-2.c"
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr88423.c b/gcc/testsuite/gcc.c-torture/compile/pr88423.c
new file mode 100644
index 0000000..4948817
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/compile/pr88423.c
@@ -0,0 +1,5 @@
+/* { dg-do compile { target { i?86-*-* x86_64-*-* } } } */
+/* { dg-options "-march=skylake -fPIC -fsched2-use-superblocks -fno-if-conversion" } */
+/* { dg-require-effective-target fpic } */
+
+#include "../../gcc.dg/20030309-1.c"
-- 
1.8.5.3

Re: [PATCH] Update assertion in sched-ebb.c to cope with table jumps

[Jeff Law]

On 1/23/19 8:11 AM, David Malcolm wrote:
> On Wed, 2019-01-23 at 16:52 +0300, Alexander Monakov wrote:
>> On Wed, 23 Jan 2019, Andrey Belevantsev wrote:
>>
>>> For that, I'm not sure.  Your patch will leave the tablejump
>>> unscheduled at
>>> all, i.e. any fields like INSN_TICK would be unfilled and thus the
>>> later
>>> passes like bundling on ia64 will not work.  Maybe we can just stop
>>> tablejumps from moving within its block, Alexander?
>>
>> On the Bugzilla there's an alternative patch by Segher that adjusts
>> the assert
>> to accept this situation (there's still a barrier insn after the
>> tablejump insn,
>> it's just after a jump_table_data insn rather than immediately
>> following the
>> jump).  That should be a better approach, and David said he was
>> testing it.
>>
>> That said, I'm really concerned that on this testcase we should not
>> be moving
>> the tablejump *at all*: we are moving it up past a 'use ax' insn (the
>> use is
>> for the function's return value). So after the move the use is in an
>> unreachable
>> block, which makes no sense.
>>
>> So my concern is that just fixing the assert changes the issue from
>> the ICE to a
>> (latent) wrong-code issue.
>>
>> There should have been an anti-dependence between the use and the
>> jump. I'll try
>> to investigate.
>>
>> Alexander
> 
> Thanks everyone for their clarifications (this is somewhat outside
> my normal comfort zone of diagnostics/frontend stuff...)
> 
> Here's Segher's patch to sched-ebb.c, along with a couple of compile-only
> testcases I put together (which triggered ICEs on x86_64 and powerpc
> without the sched-ebb.c fix).
> 
> Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu, and this
> fixes the ICE in the the powerpc testcase.
> 
> That said, I share your concern that this might be papering over a
> latent wrong-code issue.
> 
> Dave
> 
> gcc/ChangeLog:
> 	PR rtl-optimization/88347
> 	PR rtl-optimization/88423
> 	* sched-ebb.c (begin_move_insn): Update assertion to handle table
> 	jumps.
> 
> gcc/testsuite/ChangeLog:
> 	PR rtl-optimization/88347
> 	PR rtl-optimization/88423
> 	* gcc.c-torture/compile/pr88347.c: New test.
> 	* gcc.c-torture/compile/pr88423.c: New test.
To touch on one of the issues I raised.  AFAICT the schedulers don't use
SCHED_GROUP_P for dealing with tablejumps.  They're used for
cc0-user/setter, fused insns and the like.  That's a bit of a surprise.

Given that the table isn't actually associated with the block with the
tablejump, SCHED_GROUP_P might actually create a whole new set of problems.

Why oh why is the jump table data not actually attached to the tablejump
insn itself.  Nearly 30 years of working on GCC and I can't answer that one.

I slightly prefer Alexander's version since it appears to arrange for a
scheduling barrier at the jump.  The one obvious worry I have is it may
not be safe in the presence of DEBUG_INSNs and/or additional note insns
due to its use of NEXT_INSN.

But given the rest of the compiler should be keeping these 3 insns
together, I suspect if something broke them apart with an ill-placed
DEBUG_INSN or NOTE_INSN_DELETED or whatever we'd be seeing other problems.


Jeff

Re: [PATCH] Update assertion in sched-ebb.c to cope with table jumps

[Segher Boessenkool]

On Mon, Mar 25, 2019 at 05:12:05PM -0600, Jeff Law wrote:
> To touch on one of the issues I raised.  AFAICT the schedulers don't use
> SCHED_GROUP_P for dealing with tablejumps.  They're used for
> cc0-user/setter, fused insns and the like.  That's a bit of a surprise.
> 
> Given that the table isn't actually associated with the block with the
> tablejump, SCHED_GROUP_P might actually create a whole new set of problems.
> 
> Why oh why is the jump table data not actually attached to the tablejump
> insn itself.  Nearly 30 years of working on GCC and I can't answer that one.

It somewhat makes sense for targets where the jump table is emitted in the
text section; we then need to know its size for jumps over it, etc.


Segher

Re: [PATCH] Update assertion in sched-ebb.c to cope with table jumps

[Jeff Law]

On 3/26/19 11:52 AM, Segher Boessenkool wrote:
> On Mon, Mar 25, 2019 at 05:12:05PM -0600, Jeff Law wrote:
>> To touch on one of the issues I raised.  AFAICT the schedulers don't use
>> SCHED_GROUP_P for dealing with tablejumps.  They're used for
>> cc0-user/setter, fused insns and the like.  That's a bit of a surprise.
>>
>> Given that the table isn't actually associated with the block with the
>> tablejump, SCHED_GROUP_P might actually create a whole new set of problems.
>>
>> Why oh why is the jump table data not actually attached to the tablejump
>> insn itself.  Nearly 30 years of working on GCC and I can't answer that one.
> 
> It somewhat makes sense for targets where the jump table is emitted in the
> text section; we then need to know its size for jumps over it, etc.
> 
ISTM if you attach the table to the indirect jump, then you could
include the size of hte table in the size of the indirect jump on
targets where the table is emitted inline in the text section.

I don't think there's anything we're doing now that couldn't be done
with the table attached to the jump.  I would even claim that some
things become notably easier :-)


But none of that is gcc-9 material.

jeff

Re: [PATCH] Update assertion in sched-ebb.c to cope with table jumps

[Segher Boessenkool]

On Tue, Mar 26, 2019 at 12:15:26PM -0600, Jeff Law wrote:
> On 3/26/19 11:52 AM, Segher Boessenkool wrote:
> > On Mon, Mar 25, 2019 at 05:12:05PM -0600, Jeff Law wrote:
> >> To touch on one of the issues I raised.  AFAICT the schedulers don't use
> >> SCHED_GROUP_P for dealing with tablejumps.  They're used for
> >> cc0-user/setter, fused insns and the like.  That's a bit of a surprise.
> >>
> >> Given that the table isn't actually associated with the block with the
> >> tablejump, SCHED_GROUP_P might actually create a whole new set of problems.
> >>
> >> Why oh why is the jump table data not actually attached to the tablejump
> >> insn itself.  Nearly 30 years of working on GCC and I can't answer that one.
> > 
> > It somewhat makes sense for targets where the jump table is emitted in the
> > text section; we then need to know its size for jumps over it, etc.
> > 
> ISTM if you attach the table to the indirect jump, then you could
> include the size of hte table in the size of the indirect jump on
> targets where the table is emitted inline in the text section.
> 
> I don't think there's anything we're doing now that couldn't be done
> with the table attached to the jump.  I would even claim that some
> things become notably easier :-)

I agree; I was musing why it grew this way historically.

> But none of that is gcc-9 material.

Right, but it would be lovely if someone picked it up for GCC 10.  Hint hint.


Segher

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Alexander Monakov]

On Wed, 23 Jan 2019, Alexander Monakov wrote:

> That said, I'm really concerned that on this testcase we should not be moving
> the tablejump *at all*: we are moving it up past a 'use ax' insn (the use is
> for the function's return value). So after the move the use is in an unreachable
> block, which makes no sense.
> 
> So my concern is that just fixing the assert changes the issue from the ICE to a
> (latent) wrong-code issue.
> 
> There should have been an anti-dependence between the use and the jump. I'll try
> to investigate.

It appears that sched-deps tries to take notice of a barrier after a jump, but
similarly to sched-ebb doesn't anticipate that for a tablejump the barrier will
appear after two more insns (a code_label and a jump_table_data).

If so, it needs a fixup just like the posted change for the assert. I'll fire up
a bootstrap/regtest.

Alexander

	* sched-deps.c (sched_analyze_insn): Take into account that for
	tablejumps the barrier appears after a label and a jump_table_data.

--- a/gcc/sched-deps.c
+++ b/gcc/sched-deps.c
@@ -3005,6 +3005,8 @@ sched_analyze_insn (struct deps_desc *deps, rtx x, rtx_insn *insn)
   if (JUMP_P (insn))
     {
       rtx_insn *next = next_nonnote_nondebug_insn (insn);
+      if (LABEL_P (next) && JUMP_TABLE_DATA_P (NEXT_INSN (next)))
+	next = NEXT_INSN (NEXT_INSN (next));
       if (next && BARRIER_P (next))
 	reg_pending_barrier = MOVE_BARRIER;
       else

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Alexander Monakov]

On Wed, 23 Jan 2019, Alexander Monakov wrote:

> It appears that sched-deps tries to take notice of a barrier after a jump, but
> similarly to sched-ebb doesn't anticipate that for a tablejump the barrier will
> appear after two more insns (a code_label and a jump_table_data).
> 
> If so, it needs a fixup just like the posted change for the assert. I'll fire up
> a bootstrap/regtest.

Updated patch below (now taking into account that NEXT_INSN may give NULL)
passes bootstrap/regtest on x86_64, also with -fsched2-use-superblocks.

I'm surprised to learn that a tablejump may be not the final insn in its
containing basic block.  It certainly seems like a ripe ground for logic
bugs like this one.  Is it really intentional?

OK for trunk?

Thanks.
Alexander

	PR rtl-optimization/88347
	PR rtl-optimization/88423
	* sched-deps.c (sched_analyze_insn): Take into account that for
	tablejumps the barrier appears after a label and a jump_table_data.

--- a/gcc/sched-deps.c
+++ b/gcc/sched-deps.c
@@ -3005,6 +3005,11 @@ sched_analyze_insn (struct deps_desc *deps, rtx x, rtx_insn *insn)
   if (JUMP_P (insn))
     {
       rtx_insn *next = next_nonnote_nondebug_insn (insn);
+      /* ??? For tablejumps, the barrier may appear not immediately after
+         the jump, but after a label and a jump_table_data insn.  */
+      if (next && LABEL_P (next) && NEXT_INSN (next)
+	  && JUMP_TABLE_DATA_P (NEXT_INSN (next)))
+	next = NEXT_INSN (NEXT_INSN (next));
       if (next && BARRIER_P (next))
 	reg_pending_barrier = MOVE_BARRIER;
       else

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Segher Boessenkool]

On Thu, Jan 24, 2019 at 06:43:38PM +0300, Alexander Monakov wrote:
> On Wed, 23 Jan 2019, Alexander Monakov wrote:
> 
> > It appears that sched-deps tries to take notice of a barrier after a jump, but
> > similarly to sched-ebb doesn't anticipate that for a tablejump the barrier will
> > appear after two more insns (a code_label and a jump_table_data).
> > 
> > If so, it needs a fixup just like the posted change for the assert. I'll fire up
> > a bootstrap/regtest.
> 
> Updated patch below (now taking into account that NEXT_INSN may give NULL)
> passes bootstrap/regtest on x86_64, also with -fsched2-use-superblocks.
> 
> I'm surprised to learn that a tablejump may be not the final insn in its
> containing basic block.  It certainly seems like a ripe ground for logic
> bugs like this one.  Is it really intentional?

md.texi says

The @samp{tablejump} insn is always the last insn before the jump
table it uses.  Its assembler code normally has no need to use the
second operand, but you should incorporate it in the RTL pattern so
that the jump optimizer will not delete the table as unreachable code.

but rtl.texi says

A @code{jump_table_data} insn is a placeholder for the jump-table data
of a @code{casesi} or @code{tablejump} insn.  They are placed after
a @code{tablejump_p} insn.  A @code{jump_table_data} insn is not part o
a basic blockm but it is associated with the basic block that ends with
the @code{tablejump_p} insn.  The @code{PATTERN} of a @code{jump_table_data}
is always either an @code{addr_vec} or an @code{addr_diff_vec}, and a
@code{jump_table_data} insn is always preceded by a @code{code_label}.
The @code{tablejump_p} insn refers to that @code{code_label} via its
@code{JUMP_LABEL}.

Which of these two is true?


Segher

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Eric Botcazou]

> md.texi says
> 
> The @samp{tablejump} insn is always the last insn before the jump
> table it uses.  Its assembler code normally has no need to use the
> second operand, but you should incorporate it in the RTL pattern so
> that the jump optimizer will not delete the table as unreachable code.
> 
> but rtl.texi says
> 
> A @code{jump_table_data} insn is a placeholder for the jump-table data
> of a @code{casesi} or @code{tablejump} insn.  They are placed after
> a @code{tablejump_p} insn.  A @code{jump_table_data} insn is not part o
> a basic blockm but it is associated with the basic block that ends with
> the @code{tablejump_p} insn.  The @code{PATTERN} of a @code{jump_table_data}
> is always either an @code{addr_vec} or an @code{addr_diff_vec}, and a
> @code{jump_table_data} insn is always preceded by a @code{code_label}. The
> @code{tablejump_p} insn refers to that @code{code_label} via its
> @code{JUMP_LABEL}.
> 
> Which of these two is true?

The latter I'd say, see skip_insns_after_block.

-- 
Eric Botcazou

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Jeff Law]

On 1/24/19 3:10 PM, Eric Botcazou wrote:
>> md.texi says
>>
>> The @samp{tablejump} insn is always the last insn before the jump
>> table it uses.  Its assembler code normally has no need to use the
>> second operand, but you should incorporate it in the RTL pattern so
>> that the jump optimizer will not delete the table as unreachable code.
>>
>> but rtl.texi says
>>
>> A @code{jump_table_data} insn is a placeholder for the jump-table data
>> of a @code{casesi} or @code{tablejump} insn.  They are placed after
>> a @code{tablejump_p} insn.  A @code{jump_table_data} insn is not part o
>> a basic blockm but it is associated with the basic block that ends with
>> the @code{tablejump_p} insn.  The @code{PATTERN} of a @code{jump_table_data}
>> is always either an @code{addr_vec} or an @code{addr_diff_vec}, and a
>> @code{jump_table_data} insn is always preceded by a @code{code_label}. The
>> @code{tablejump_p} insn refers to that @code{code_label} via its
>> @code{JUMP_LABEL}.
>>
>> Which of these two is true?
> 
> The latter I'd say, see skip_insns_after_block.
Hmm, I forgot about the label.  Ugh.  That may muck up the whole
SCHED_GROUP_P thing.  But yes, I think it's supposed to be the
tablejump, label and jump table.   The question in my mind is barriers
and BLOCK_END notes -- where are those supposed to be?

Jeff

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Jeff Law]

On 1/24/19 2:10 PM, Segher Boessenkool wrote:
> On Thu, Jan 24, 2019 at 06:43:38PM +0300, Alexander Monakov wrote:
>> On Wed, 23 Jan 2019, Alexander Monakov wrote:
>>
>>> It appears that sched-deps tries to take notice of a barrier after a jump, but
>>> similarly to sched-ebb doesn't anticipate that for a tablejump the barrier will
>>> appear after two more insns (a code_label and a jump_table_data).
>>>
>>> If so, it needs a fixup just like the posted change for the assert. I'll fire up
>>> a bootstrap/regtest.
>>
>> Updated patch below (now taking into account that NEXT_INSN may give NULL)
>> passes bootstrap/regtest on x86_64, also with -fsched2-use-superblocks.
>>
>> I'm surprised to learn that a tablejump may be not the final insn in its
>> containing basic block.  It certainly seems like a ripe ground for logic
>> bugs like this one.  Is it really intentional?
> 
> md.texi says
> 
> The @samp{tablejump} insn is always the last insn before the jump
> table it uses.  Its assembler code normally has no need to use the
> second operand, but you should incorporate it in the RTL pattern so
> that the jump optimizer will not delete the table as unreachable code.
> 
> but rtl.texi says
> 
> A @code{jump_table_data} insn is a placeholder for the jump-table data
> of a @code{casesi} or @code{tablejump} insn.  They are placed after
> a @code{tablejump_p} insn.  A @code{jump_table_data} insn is not part o
> a basic blockm but it is associated with the basic block that ends with
> the @code{tablejump_p} insn.  The @code{PATTERN} of a @code{jump_table_data}
> is always either an @code{addr_vec} or an @code{addr_diff_vec}, and a
> @code{jump_table_data} insn is always preceded by a @code{code_label}.
> The @code{tablejump_p} insn refers to that @code{code_label} via its
> @code{JUMP_LABEL}.
> 
> Which of these two is true?
I suspect the latter.  The former is likely very old.  Pause... Yup.
You can find it verbatim in 1.42.

Jeff

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Aaron Sawdey]

The code in emit_case_dispatch_table() will very clearly always emit branch/label/jumptable_data/barrier
so this does need to be handled. So, yes tablejump always looks like this, and also yes it seems to be
ripe ground for logic bugs, we have 88308, 88347, 88423 all related to it.

In the long term it might be nice to use a general mechanism (SCHED_GROUP_P?) for handling the label and jump
table data that follow a case branch using jump table.

But for now in stage 4, I think the right way to fix this is with the patch that Segher posted earlier.
If regtest passes (x86_64 and ppc64/ppc32), ok for trunk?

2019-02-18  Aaron Sawdey  <acsawdey@linux.ibm.com>

	PR rtl-optimization/88347
	* schedule-ebb.c (begin_move_insn): Apply Segher's patch to handle
	a jump table before the barrier.


On 1/24/19 9:43 AM, Alexander Monakov wrote:
> On Wed, 23 Jan 2019, Alexander Monakov wrote:
> 
>> It appears that sched-deps tries to take notice of a barrier after a jump, but
>> similarly to sched-ebb doesn't anticipate that for a tablejump the barrier will
>> appear after two more insns (a code_label and a jump_table_data).
>>
>> If so, it needs a fixup just like the posted change for the assert. I'll fire up
>> a bootstrap/regtest.
> 
> Updated patch below (now taking into account that NEXT_INSN may give NULL)
> passes bootstrap/regtest on x86_64, also with -fsched2-use-superblocks.
> 
> I'm surprised to learn that a tablejump may be not the final insn in its
> containing basic block.  It certainly seems like a ripe ground for logic
> bugs like this one.  Is it really intentional?
> 
> OK for trunk?
> 
> Thanks.
> Alexander
> 
> 	PR rtl-optimization/88347
> 	PR rtl-optimization/88423
> 	* sched-deps.c (sched_analyze_insn): Take into account that for
> 	tablejumps the barrier appears after a label and a jump_table_data.
> 
> --- a/gcc/sched-deps.c
> +++ b/gcc/sched-deps.c
> @@ -3005,6 +3005,11 @@ sched_analyze_insn (struct deps_desc *deps, rtx x, rtx_insn *insn)
>    if (JUMP_P (insn))
>      {
>        rtx_insn *next = next_nonnote_nondebug_insn (insn);
> +      /* ??? For tablejumps, the barrier may appear not immediately after
> +         the jump, but after a label and a jump_table_data insn.  */
> +      if (next && LABEL_P (next) && NEXT_INSN (next)
> +	  && JUMP_TABLE_DATA_P (NEXT_INSN (next)))
> +	next = NEXT_INSN (NEXT_INSN (next));
>        if (next && BARRIER_P (next))
>  	reg_pending_barrier = MOVE_BARRIER;
>        else
> 

-- 
Aaron Sawdey, Ph.D.  acsawdey@linux.vnet.ibm.com
050-2/C113  (507) 253-7520 home: 507/263-0782
IBM Linux Technology Center - PPC Toolchain

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Alexander Monakov]

On Mon, 18 Feb 2019, Aaron Sawdey wrote:

> The code in emit_case_dispatch_table() will very clearly always emit branch/label/jumptable_data/barrier
> so this does need to be handled. So, yes tablejump always looks like this, and also yes it seems to be
> ripe ground for logic bugs, we have 88308, 88347, 88423 all related to it.
> 
> In the long term it might be nice to use a general mechanism (SCHED_GROUP_P?) for handling the label and jump
> table data that follow a case branch using jump table.
> 
> But for now in stage 4, I think the right way to fix this is with the patch that Segher posted earlier.
> If regtest passes (x86_64 and ppc64/ppc32), ok for trunk?

How making an assert more permissive is "the right way" here?
As already mentioned, without the assert we'd move a USE of the register with
function return value to an unreachable block, which would be incorrect.

Do you anticipate issues with the sched-deps patch?

Alexander

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Aaron Sawdey]

On 2/18/19 10:41 AM, Alexander Monakov wrote:
> On Mon, 18 Feb 2019, Aaron Sawdey wrote:
> 
>> The code in emit_case_dispatch_table() will very clearly always emit branch/label/jumptable_data/barrier
>> so this does need to be handled. So, yes tablejump always looks like this, and also yes it seems to be
>> ripe ground for logic bugs, we have 88308, 88347, 88423 all related to it.
>>
>> In the long term it might be nice to use a general mechanism (SCHED_GROUP_P?) for handling the label and jump
>> table data that follow a case branch using jump table.
>>
>> But for now in stage 4, I think the right way to fix this is with the patch that Segher posted earlier.
>> If regtest passes (x86_64 and ppc64/ppc32), ok for trunk?
> 
> How making an assert more permissive is "the right way" here?
> As already mentioned, without the assert we'd move a USE of the register with
> function return value to an unreachable block, which would be incorrect.
> 
> Do you anticipate issues with the sched-deps patch?

Alexander,
 I see you are allowing it to see the barrier as if it were right after the tablejump.

Are you saying that the motion of the tablejump is happening because the scheduler does not see
the barrier (because it does not follow immediately after) and thus decides it can move instructions
to the other side of the tablejump? I agree that is incorrect and is asking for other hidden problems.

It would be nice if the tablejump, jump table label, jump table data, and barrier were all one indivisible
unit somehow.

In the meantime, can someone approve Alexander's patch?

Thanks,
   Aaron



-- 
Aaron Sawdey, Ph.D.  acsawdey@linux.vnet.ibm.com
050-2/C113  (507) 253-7520 home: 507/263-0782
IBM Linux Technology Center - PPC Toolchain

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Jeff Law]

On 1/24/19 8:43 AM, Alexander Monakov wrote:
> On Wed, 23 Jan 2019, Alexander Monakov wrote:
> 
>> It appears that sched-deps tries to take notice of a barrier after a jump, but
>> similarly to sched-ebb doesn't anticipate that for a tablejump the barrier will
>> appear after two more insns (a code_label and a jump_table_data).
>>
>> If so, it needs a fixup just like the posted change for the assert. I'll fire up
>> a bootstrap/regtest.
> 
> Updated patch below (now taking into account that NEXT_INSN may give NULL)
> passes bootstrap/regtest on x86_64, also with -fsched2-use-superblocks.
> 
> I'm surprised to learn that a tablejump may be not the final insn in its
> containing basic block.  It certainly seems like a ripe ground for logic
> bugs like this one.  Is it really intentional?
> 
> OK for trunk?
> 
> Thanks.
> Alexander
> 
> 	PR rtl-optimization/88347
> 	PR rtl-optimization/88423
> 	* sched-deps.c (sched_analyze_insn): Take into account that for
> 	tablejumps the barrier appears after a label and a jump_table_data.
I merged this with David's new tests and committed the changes to the trunk.

THanks,
Jeff

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Segher Boessenkool]

On Wed, Jan 23, 2019 at 04:52:24PM +0300, Alexander Monakov wrote:
> On Wed, 23 Jan 2019, Andrey Belevantsev wrote:
> > For that, I'm not sure.  Your patch will leave the tablejump unscheduled at
> > all, i.e. any fields like INSN_TICK would be unfilled and thus the later
> > passes like bundling on ia64 will not work.  Maybe we can just stop
> > tablejumps from moving within its block, Alexander?
> 
> On the Bugzilla there's an alternative patch by Segher that adjusts the assert
> to accept this situation (there's still a barrier insn after the tablejump insn,
> it's just after a jump_table_data insn rather than immediately following the
> jump).  That should be a better approach, and David said he was testing it.
> 
> That said, I'm really concerned that on this testcase we should not be moving
> the tablejump *at all*: we are moving it up past a 'use ax' insn (the use is
> for the function's return value). So after the move the use is in an unreachable
> block, which makes no sense.

Yes, that makes no sense indeed.  Is it acceptable (for performance) to
simply bail out on table jumps here?

> So my concern is that just fixing the assert changes the issue from the ICE to a
> (latent) wrong-code issue.
> 
> There should have been an anti-dependence between the use and the jump. I'll try
> to investigate.

Or that.  Thanks!


Segher

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Jeff Law]

On 1/23/19 12:29 PM, Segher Boessenkool wrote:
> On Wed, Jan 23, 2019 at 04:52:24PM +0300, Alexander Monakov wrote:
>> On Wed, 23 Jan 2019, Andrey Belevantsev wrote:
>>> For that, I'm not sure.  Your patch will leave the tablejump unscheduled at
>>> all, i.e. any fields like INSN_TICK would be unfilled and thus the later
>>> passes like bundling on ia64 will not work.  Maybe we can just stop
>>> tablejumps from moving within its block, Alexander?
>>
>> On the Bugzilla there's an alternative patch by Segher that adjusts the assert
>> to accept this situation (there's still a barrier insn after the tablejump insn,
>> it's just after a jump_table_data insn rather than immediately following the
>> jump).  That should be a better approach, and David said he was testing it.
>>
>> That said, I'm really concerned that on this testcase we should not be moving
>> the tablejump *at all*: we are moving it up past a 'use ax' insn (the use is
>> for the function's return value). So after the move the use is in an unreachable
>> block, which makes no sense.
> 
> Yes, that makes no sense indeed.  Is it acceptable (for performance) to
> simply bail out on table jumps here?
> 
>> So my concern is that just fixing the assert changes the issue from the ICE to a
>> (latent) wrong-code issue.
>>
>> There should have been an anti-dependence between the use and the jump. I'll try
>> to investigate.
> 
> Or that.  Thanks!
Or (as I've indicated to David) investigate if we're getting
SCHED_GROUP_P right -- that's the canonical way to keep two insns
together in the schedule.  It's definitely worth investigating.

Jeff

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Jeff Law]

On 1/23/19 6:52 AM, Alexander Monakov wrote:
> On Wed, 23 Jan 2019, Andrey Belevantsev wrote:
> 
>> For that, I'm not sure.  Your patch will leave the tablejump unscheduled at
>> all, i.e. any fields like INSN_TICK would be unfilled and thus the later
>> passes like bundling on ia64 will not work.  Maybe we can just stop
>> tablejumps from moving within its block, Alexander?
> 
> On the Bugzilla there's an alternative patch by Segher that adjusts the assert
> to accept this situation (there's still a barrier insn after the tablejump insn,
> it's just after a jump_table_data insn rather than immediately following the
> jump).  That should be a better approach, and David said he was testing it.
> 
> That said, I'm really concerned that on this testcase we should not be moving
> the tablejump *at all*: we are moving it up past a 'use ax' insn (the use is
> for the function's return value). So after the move the use is in an unreachable
> block, which makes no sense.
> 
> So my concern is that just fixing the assert changes the issue from the ICE to a
> (latent) wrong-code issue.
> 
> There should have been an anti-dependence between the use and the jump. I'll try
> to investigate.
The first thing I'd do is make sure the jump table has its SCHED_GROUP_P
marker which indicates it must stick with its associated jump.  Then I'd
make sure it's honored in the appropriate places.  It may be awkward
because the jump table data insn is going to have the SCHED_GROUP_P bit
set, but we're likely looking to muck with the actual jump.  That's
probably an artifact of the old backwards scheduling algorithm.

jeff

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Jeff Law]

On 1/18/19 10:32 AM, David Malcolm wrote:
> PR rtl-optimization/88423 reports an ICE within sched-ebb.c's
> begin_move_insn, failing the assertion at line 175, where there's
> no fall-through edge:
> 
> 171         rtx_insn *x = NEXT_INSN (insn);
> 172         if (e)
> 173           gcc_checking_assert (NOTE_P (x) || LABEL_P (x));
> 174         else
> 175           gcc_checking_assert (BARRIER_P (x));
> 
> "insn" is a jump_insn for a table jump, and its NEXT_INSN is the
> placeholder code_label, followed by the jump_table_data.
> 
> It's not clear to me if such a jump_insn can be repositioned within
> the insn stream, or if the scheduler is able to do so.  I believe a
> tablejump is always at the end of such a head/tail insn sub-stream.
> Is it a requirement that the placeholder code_label for the jump_insn
> is always its NEXT_INSN?
> 
> The loop at the start of schedule_ebb adjusts the head and tail
> of the insns to be scheduled so that it skips leading and trailing notes
> and debug insns.
> 
> This patch adjusts that loop to also skip trailing jump_insn instances
> that are table jumps, so that we don't attempt to move such table jumps.
> 
> This fixes the ICE, but I'm not very familiar with this part of the
> compiler - so I have two questions:
> 
> (1) What does GCC mean by "ebb" in this context?
> 
> My understanding is that the normal definition of an "extended basic
> block" (e.g. Muchnick's book pp175-177) is that it's a maximal grouping
> of basic blocks where only one BB in each group has multiple in-edges
> and all other BBs in the group have a single in-edge (and thus e.g.
> there's a tree-like structure of BBs within each EBB).
> 
> From what I can tell, schedule_ebbs is iterating over BBs, looking for
> runs of BBs joined by next_bb that are connected by fallthrough edges
> and don't have labels (and aren't flagged with BB_DISABLE_SCHEDULE).
> It uses this run of BBs to generate a run of instructions within the
> NEXT_INSN/PREV_INSN doubly-linked list, which it passes as "head"
> and "tail" to schedule_ebb.
> 
> This sounds like it will be a group of basic blocks with single in-edges
> internally, but it isn't a *maximal* group of such BBs - but perhaps
> it's "maximal" in the sense of what the NEXT_INSN/PREV_INSN
> representation can cope with?
> 
> There (presumably) can't be a fallthrough edge after a table jump, so
> a table jump could only ever be at the end of such a chain, never in the
> middle.
> 
> (2) Is it OK to omit "tail" from consideration here, from a dataflow
> and insn-dependency point-of-view?  Presumably the scheduler is written
> to ensure that data used by subsequent basic blocks will still be available
> after the insns within an "EBB" are reordered, so presumably any data
> uses *within* the jump_insn are still going to be available - but, as I
> said, I'm not very familiar with this part of the code.  (I think I'm also
> assuming that the jump_insn can't clobber data, just the PC)
> 
> Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
> 
> OK for trunk?
> 
> gcc/ChangeLog:
> 	PR rtl-optimization/88423
> 	* sched-ebb.c (schedule_ebb): Don't move the jump_insn for a table
> 	jump.
> 
> gcc/testsuite/ChangeLog:
> 	PR rtl-optimization/88423
> 	* gcc.c-torture/compile/pr88423.c: New test.
I wonder if this should be generalized for SCHED_GROUP_P which is hte
standard mechanism we use to ensure two insns fire together.

Can you check if SCHED_GROUP_P is set on either the jump or the jump
table (I forget if it belongs on the first or the last insn).

It may make more sense to be checking for SCHED_GROUP_P in sched_ebb
rather than special casing tablejump_p.


I'm not likely to be able to dig further into this for a while.  Vlad
might be able to provide guidance.

jeff

Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)

[Steven Bosscher]

On Fri, Jan 18, 2019 at 5:43 PM David Malcolm wrote:
> (1) What does GCC mean by "ebb" in this context?

In this context, the EBB is what Muchnick would call a trace.

Ciao!
Steven