Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)
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)
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)
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)
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)
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)
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. acsaw...@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)
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)
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
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. acsaw...@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)
> 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)
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)
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)
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)
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)
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
Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)
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,
Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)
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
Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423)
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)
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 000..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"
