* [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) @ 2019-01-18 16:43 David Malcolm 2019-01-18 16:58 ` David Malcolm ` (2 more replies) 0 siblings, 3 replies; 24+ messages in thread From: David Malcolm @ 2019-01-18 16:43 UTC (permalink / raw) To: gcc-patches; +Cc: 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-18 16:43 [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) David Malcolm @ 2019-01-18 16:58 ` David Malcolm 2019-01-23 11:30 ` Andrey Belevantsev 2019-01-21 18:02 ` Jeff Law 2019-01-22 8:59 ` Steven Bosscher 2 siblings, 1 reply; 24+ messages in thread From: David Malcolm @ 2019-01-18 16:58 UTC (permalink / raw) To: gcc-patches; +Cc: Andrey Belevantsev 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" ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-18 16:58 ` David Malcolm @ 2019-01-23 11:30 ` Andrey Belevantsev 2019-01-23 13:54 ` Alexander Monakov 0 siblings, 1 reply; 24+ messages in thread From: Andrey Belevantsev @ 2019-01-23 11:30 UTC (permalink / raw) To: David Malcolm, gcc-patches; +Cc: Alexander Monakov 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" ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-23 11:30 ` Andrey Belevantsev @ 2019-01-23 13:54 ` Alexander Monakov 2019-01-23 14:26 ` [PATCH] Update assertion in sched-ebb.c to cope with table jumps David Malcolm ` (3 more replies) 0 siblings, 4 replies; 24+ messages in thread From: Alexander Monakov @ 2019-01-23 13:54 UTC (permalink / raw) To: Andrey Belevantsev; +Cc: David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* [PATCH] Update assertion in sched-ebb.c to cope with table jumps 2019-01-23 13:54 ` Alexander Monakov @ 2019-01-23 14:26 ` David Malcolm 2019-03-25 23:21 ` Jeff Law 2019-01-23 16:23 ` [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) Alexander Monakov ` (2 subsequent siblings) 3 siblings, 1 reply; 24+ messages in thread From: David Malcolm @ 2019-01-23 14:26 UTC (permalink / raw) To: Alexander Monakov, Andrey Belevantsev Cc: gcc-patches, Segher Boessenkool, 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] Update assertion in sched-ebb.c to cope with table jumps 2019-01-23 14:26 ` [PATCH] Update assertion in sched-ebb.c to cope with table jumps David Malcolm @ 2019-03-25 23:21 ` Jeff Law 2019-03-26 18:02 ` Segher Boessenkool 0 siblings, 1 reply; 24+ messages in thread From: Jeff Law @ 2019-03-25 23:21 UTC (permalink / raw) To: David Malcolm, Alexander Monakov, Andrey Belevantsev Cc: gcc-patches, Segher Boessenkool 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] Update assertion in sched-ebb.c to cope with table jumps 2019-03-25 23:21 ` Jeff Law @ 2019-03-26 18:02 ` Segher Boessenkool 2019-03-26 18:42 ` Jeff Law 0 siblings, 1 reply; 24+ messages in thread From: Segher Boessenkool @ 2019-03-26 18:02 UTC (permalink / raw) To: Jeff Law Cc: David Malcolm, Alexander Monakov, Andrey Belevantsev, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] Update assertion in sched-ebb.c to cope with table jumps 2019-03-26 18:02 ` Segher Boessenkool @ 2019-03-26 18:42 ` Jeff Law 2019-03-26 19:05 ` Segher Boessenkool 0 siblings, 1 reply; 24+ messages in thread From: Jeff Law @ 2019-03-26 18:42 UTC (permalink / raw) To: Segher Boessenkool Cc: David Malcolm, Alexander Monakov, Andrey Belevantsev, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] Update assertion in sched-ebb.c to cope with table jumps 2019-03-26 18:42 ` Jeff Law @ 2019-03-26 19:05 ` Segher Boessenkool 0 siblings, 0 replies; 24+ messages in thread From: Segher Boessenkool @ 2019-03-26 19:05 UTC (permalink / raw) To: Jeff Law Cc: David Malcolm, Alexander Monakov, Andrey Belevantsev, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-23 13:54 ` Alexander Monakov 2019-01-23 14:26 ` [PATCH] Update assertion in sched-ebb.c to cope with table jumps David Malcolm @ 2019-01-23 16:23 ` Alexander Monakov 2019-01-24 16:31 ` Alexander Monakov 2019-01-23 19:44 ` Segher Boessenkool 2019-02-21 20:12 ` Jeff Law 3 siblings, 1 reply; 24+ messages in thread From: Alexander Monakov @ 2019-01-23 16:23 UTC (permalink / raw) To: Andrey Belevantsev; +Cc: David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-23 16:23 ` [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) Alexander Monakov @ 2019-01-24 16:31 ` Alexander Monakov 2019-01-24 21:13 ` Segher Boessenkool ` (2 more replies) 0 siblings, 3 replies; 24+ messages in thread From: Alexander Monakov @ 2019-01-24 16:31 UTC (permalink / raw) To: Andrey Belevantsev; +Cc: David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-24 16:31 ` Alexander Monakov @ 2019-01-24 21:13 ` Segher Boessenkool 2019-01-24 22:13 ` Eric Botcazou 2019-03-25 23:12 ` Jeff Law 2019-02-18 16:30 ` Aaron Sawdey 2019-03-26 0:56 ` Jeff Law 2 siblings, 2 replies; 24+ messages in thread From: Segher Boessenkool @ 2019-01-24 21:13 UTC (permalink / raw) To: Alexander Monakov; +Cc: Andrey Belevantsev, David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-24 21:13 ` Segher Boessenkool @ 2019-01-24 22:13 ` Eric Botcazou 2019-02-21 20:27 ` Jeff Law 2019-03-25 23:12 ` Jeff Law 1 sibling, 1 reply; 24+ messages in thread From: Eric Botcazou @ 2019-01-24 22:13 UTC (permalink / raw) To: Segher Boessenkool Cc: gcc-patches, Alexander Monakov, Andrey Belevantsev, David Malcolm > 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-24 22:13 ` Eric Botcazou @ 2019-02-21 20:27 ` Jeff Law 0 siblings, 0 replies; 24+ messages in thread From: Jeff Law @ 2019-02-21 20:27 UTC (permalink / raw) To: Eric Botcazou, Segher Boessenkool Cc: gcc-patches, Alexander Monakov, Andrey Belevantsev, David Malcolm 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-24 21:13 ` Segher Boessenkool 2019-01-24 22:13 ` Eric Botcazou @ 2019-03-25 23:12 ` Jeff Law 1 sibling, 0 replies; 24+ messages in thread From: Jeff Law @ 2019-03-25 23:12 UTC (permalink / raw) To: Segher Boessenkool, Alexander Monakov Cc: Andrey Belevantsev, David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-24 16:31 ` Alexander Monakov 2019-01-24 21:13 ` Segher Boessenkool @ 2019-02-18 16:30 ` Aaron Sawdey 2019-02-18 16:41 ` Alexander Monakov 2019-03-26 0:56 ` Jeff Law 2 siblings, 1 reply; 24+ messages in thread From: Aaron Sawdey @ 2019-02-18 16:30 UTC (permalink / raw) To: Alexander Monakov, Andrey Belevantsev Cc: David Malcolm, gcc-patches, Segher Boessenkool, David Edelsohn, Bill Schmidt, law, ebotcazou, rguenther 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-02-18 16:30 ` Aaron Sawdey @ 2019-02-18 16:41 ` Alexander Monakov 2019-02-18 18:34 ` Aaron Sawdey 0 siblings, 1 reply; 24+ messages in thread From: Alexander Monakov @ 2019-02-18 16:41 UTC (permalink / raw) To: Aaron Sawdey Cc: Andrey Belevantsev, David Malcolm, gcc-patches, Segher Boessenkool, David Edelsohn, Bill Schmidt, law, ebotcazou, rguenther 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-02-18 16:41 ` Alexander Monakov @ 2019-02-18 18:34 ` Aaron Sawdey 0 siblings, 0 replies; 24+ messages in thread From: Aaron Sawdey @ 2019-02-18 18:34 UTC (permalink / raw) To: Alexander Monakov Cc: Andrey Belevantsev, David Malcolm, gcc-patches, Segher Boessenkool, David Edelsohn, Bill Schmidt, law, ebotcazou, rguenther 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-24 16:31 ` Alexander Monakov 2019-01-24 21:13 ` Segher Boessenkool 2019-02-18 16:30 ` Aaron Sawdey @ 2019-03-26 0:56 ` Jeff Law 2 siblings, 0 replies; 24+ messages in thread From: Jeff Law @ 2019-03-26 0:56 UTC (permalink / raw) To: Alexander Monakov, Andrey Belevantsev; +Cc: David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-23 13:54 ` Alexander Monakov 2019-01-23 14:26 ` [PATCH] Update assertion in sched-ebb.c to cope with table jumps David Malcolm 2019-01-23 16:23 ` [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) Alexander Monakov @ 2019-01-23 19:44 ` Segher Boessenkool 2019-02-21 19:59 ` Jeff Law 2019-02-21 20:12 ` Jeff Law 3 siblings, 1 reply; 24+ messages in thread From: Segher Boessenkool @ 2019-01-23 19:44 UTC (permalink / raw) To: Alexander Monakov; +Cc: Andrey Belevantsev, David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-23 19:44 ` Segher Boessenkool @ 2019-02-21 19:59 ` Jeff Law 0 siblings, 0 replies; 24+ messages in thread From: Jeff Law @ 2019-02-21 19:59 UTC (permalink / raw) To: Segher Boessenkool, Alexander Monakov Cc: Andrey Belevantsev, David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-23 13:54 ` Alexander Monakov ` (2 preceding siblings ...) 2019-01-23 19:44 ` Segher Boessenkool @ 2019-02-21 20:12 ` Jeff Law 3 siblings, 0 replies; 24+ messages in thread From: Jeff Law @ 2019-02-21 20:12 UTC (permalink / raw) To: Alexander Monakov, Andrey Belevantsev; +Cc: David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-18 16:43 [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) David Malcolm 2019-01-18 16:58 ` David Malcolm @ 2019-01-21 18:02 ` Jeff Law 2019-01-22 8:59 ` Steven Bosscher 2 siblings, 0 replies; 24+ messages in thread From: Jeff Law @ 2019-01-21 18:02 UTC (permalink / raw) To: David Malcolm, gcc-patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
* Re: [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) 2019-01-18 16:43 [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) David Malcolm 2019-01-18 16:58 ` David Malcolm 2019-01-21 18:02 ` Jeff Law @ 2019-01-22 8:59 ` Steven Bosscher 2 siblings, 0 replies; 24+ messages in thread From: Steven Bosscher @ 2019-01-22 8:59 UTC (permalink / raw) To: David Malcolm; +Cc: GCC Patches 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 ^ permalink raw reply [flat|nested] 24+ messages in thread
end of thread, other threads:[~2019-03-26 18:42 UTC | newest] Thread overview: 24+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-01-18 16:43 [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) David Malcolm 2019-01-18 16:58 ` David Malcolm 2019-01-23 11:30 ` Andrey Belevantsev 2019-01-23 13:54 ` Alexander Monakov 2019-01-23 14:26 ` [PATCH] Update assertion in sched-ebb.c to cope with table jumps David Malcolm 2019-03-25 23:21 ` Jeff Law 2019-03-26 18:02 ` Segher Boessenkool 2019-03-26 18:42 ` Jeff Law 2019-03-26 19:05 ` Segher Boessenkool 2019-01-23 16:23 ` [PATCH] sched-ebb.c: avoid moving table jumps (PR rtl-optimization/88423) Alexander Monakov 2019-01-24 16:31 ` Alexander Monakov 2019-01-24 21:13 ` Segher Boessenkool 2019-01-24 22:13 ` Eric Botcazou 2019-02-21 20:27 ` Jeff Law 2019-03-25 23:12 ` Jeff Law 2019-02-18 16:30 ` Aaron Sawdey 2019-02-18 16:41 ` Alexander Monakov 2019-02-18 18:34 ` Aaron Sawdey 2019-03-26 0:56 ` Jeff Law 2019-01-23 19:44 ` Segher Boessenkool 2019-02-21 19:59 ` Jeff Law 2019-02-21 20:12 ` Jeff Law 2019-01-21 18:02 ` Jeff Law 2019-01-22 8:59 ` Steven Bosscher
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).