[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #12 from abel at gcc dot gnu dot org 2010-08-24 08:57 --- Subject: Bug 42245 Author: abel Date: Tue Aug 24 08:57:18 2010 New Revision: 163504 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=163504 Log: Backport from mainline: 2010-01-14 Andrey Belevantsev a...@ispras.ru Alexander Monakov amona...@ispras.ru PR middle-end/42245 * sel-sched-ir.c (sel_recompute_toporder): New. Use it... (maybe_tidy_empty_bb): ... here. Make static. Add new argument. Update all callers. (tidy_control_flow): ... and here. Recompute topological order of basic blocks in region if necessary. (sel_redirect_edge_and_branch): Change return type. Return true if topological order might have been invalidated. (purge_empty_blocks): Export and move from... * sel-sched.c (purge_empty_blocks): ... here. * sel-sched-ir.h (sel_redirect_edge_and_branch): Update prototype. (maybe_tidy_empty_bb): Delete prototype. (purge_empty_blocks): Declare. Modified: branches/gcc-4_4-branch/gcc/ChangeLog branches/gcc-4_4-branch/gcc/sel-sched-ir.c branches/gcc-4_4-branch/gcc/sel-sched-ir.h branches/gcc-4_4-branch/gcc/sel-sched.c branches/gcc-4_4-branch/gcc/testsuite/ChangeLog -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #9 from amonakov at gcc dot gnu dot org 2010-01-14 10:29 --- Subject: Bug 42245 Author: amonakov Date: Thu Jan 14 10:28:47 2010 New Revision: 155890 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=155890 Log: 2010-01-14 Andrey Belevantsev a...@ispras.ru Alexander Monakov amona...@ispras.ru PR middle-end/42245 * sel-sched-ir.c (sel_recompute_toporder): New. Use it... (maybe_tidy_empty_bb): ... here. Make static. Add new argument. Update all callers. (tidy_control_flow): ... and here. Recompute topological order of basic blocks in region if necessary. (sel_redirect_edge_and_branch): Change return type. Return true if topological order might have been invalidated. (purge_empty_blocks): Export and move from... * sel-sched.c (purge_empty_blocks): ... here. * sel-sched-ir.h (sel_redirect_edge_and_branch): Update prototype. (maybe_tidy_empty_bb): Delete prototype. (purge_empty_blocks): Declare. * gcc.dg/pr42245.c: New. * gcc.dg/pr42245-2.c: New. Modified: trunk/gcc/ChangeLog trunk/gcc/sel-sched-ir.c trunk/gcc/sel-sched-ir.h trunk/gcc/sel-sched.c trunk/gcc/testsuite/ChangeLog -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #10 from amonakov at gcc dot gnu dot org 2010-01-14 10:38 --- Subject: Bug 42245 Author: amonakov Date: Thu Jan 14 10:38:14 2010 New Revision: 155891 URL: http://gcc.gnu.org/viewcvs?root=gccview=revrev=155891 Log: Add tests missing from previous commit. PR middle-end/42245 * gcc.dg/pr42245.c: New. * gcc.dg/pr42245-2.c: New. Added: trunk/gcc/testsuite/gcc.dg/pr42245-2.c trunk/gcc/testsuite/gcc.dg/pr42245.c -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #11 from amonakov at gcc dot gnu dot org 2010-01-14 10:41 --- Fixed by revision 155890 -- amonakov at gcc dot gnu dot org changed: What|Removed |Added Status|ASSIGNED|RESOLVED Resolution||FIXED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #7 from amonakov at gcc dot gnu dot org 2010-01-11 15:04 --- Our previous patch (http://gcc.gnu.org/ml/gcc-patches/2009-12/msg01215.html) failed to correctly fix the problem, and the new testcase uncovers a flaw in that implementation. We 'forgot' to recompute topological order if it was invalidated in tidy_control_flow but not in maybe_tidy_empty_bb called from that function. Fixed by passing recompute_toporder_p to the latter on top of the mentioned previous patch as below (the patch also makes maybe_tidy_empty_bb static by moving the only caller into the same file). * sel-sched-ir.c (maybe_tidy_empty_bb): Make static. Add new argument. Update all callers. (purge_empty_blocks): Export and move from... * sel-sched.c (purge_empty_blocks): ... here. Delete. * sel-sched-ir.h (maybe_tidy_empty_bb): Delete prototype. (purge_empty_blocks): Declare. diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c index cffee1c..e20df17 100644 --- a/gcc/sel-sched-ir.c +++ b/gcc/sel-sched-ir.c @@ -3538,13 +3538,13 @@ sel_recompute_toporder (void) } /* Tidy the possibly empty block BB. */ -bool -maybe_tidy_empty_bb (basic_block bb) +static bool +maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p) { basic_block succ_bb, pred_bb; edge e; edge_iterator ei; - bool rescan_p, recompute_toporder_p = false; + bool rescan_p; /* Keep empty bb only if this block immediately precedes EXIT and has incoming non-fallthrough edge, or it has no predecessors or @@ -3630,7 +3630,7 @@ tidy_control_flow (basic_block xbb, bool full_tidying) insn_t first, last; /* First check whether XBB is empty. */ - changed = maybe_tidy_empty_bb (xbb); + changed = maybe_tidy_empty_bb (xbb, false); if (changed || !full_tidying) return changed; @@ -3694,7 +3694,7 @@ tidy_control_flow (basic_block xbb, bool full_tidying) that contained that jump, becomes empty too. In such case remove it too. */ if (sel_bb_empty_p (xbb-prev_bb)) -changed = maybe_tidy_empty_bb (xbb-prev_bb); +changed = maybe_tidy_empty_bb (xbb-prev_bb, recompute_toporder_p); else if (recompute_toporder_p) sel_recompute_toporder (); } @@ -3702,6 +3702,24 @@ tidy_control_flow (basic_block xbb, bool full_tidying) return changed; } +/* Purge meaningless empty blocks in the middle of a region. */ +void +purge_empty_blocks (void) +{ + /* Do not attempt to delete preheader. */ + int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0; + + while (i current_nr_blocks) +{ + basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i)); + + if (maybe_tidy_empty_bb (b, false)) + continue; + + i++; +} +} + /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true, do not delete insn's data, because it will be later re-emitted. Return true if we have removed some blocks afterwards. */ diff --git a/gcc/sel-sched-ir.h b/gcc/sel-sched-ir.h index 317258c..b5121c0 100644 --- a/gcc/sel-sched-ir.h +++ b/gcc/sel-sched-ir.h @@ -1619,7 +1619,7 @@ extern bool tidy_control_flow (basic_block, bool); extern void free_bb_note_pool (void); extern void sel_remove_empty_bb (basic_block, bool, bool); -extern bool maybe_tidy_empty_bb (basic_block bb); +extern void purge_empty_blocks (void); extern basic_block sel_split_edge (edge); extern basic_block sel_create_recovery_block (insn_t); extern void sel_merge_blocks (basic_block, basic_block); diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c index 37be754..9271b80 100644 --- a/gcc/sel-sched.c +++ b/gcc/sel-sched.c @@ -6790,24 +6790,6 @@ setup_current_loop_nest (int rgn) gcc_assert (LOOP_MARKED_FOR_PIPELINING_P (current_loop_nest)); } -/* Purge meaningless empty blocks in the middle of a region. */ -static void -purge_empty_blocks (void) -{ - /* Do not attempt to delete preheader. */ - int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0; - - while (i current_nr_blocks) -{ - basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i)); - - if (maybe_tidy_empty_bb (b)) - continue; - - i++; -} -} - /* Compute instruction priorities for current region. */ static void sel_compute_priorities (int rgn) -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #8 from janis at gcc dot gnu dot org 2010-01-11 22:10 --- I bootstrapped on powerpc64-linux c,c++,fortran with the earlier big selective-scheduling patch plus the patch in comment #7 of this PR and the patch in comment #4 of PR42246. The resulting GCC gets no failures for SPEC CPU2000 using several combinations of selective-scheduling options. Thanks for being so responsive! -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #6 from janis at gcc dot gnu dot org 2010-01-06 18:44 --- With the patch at http://gcc.gnu.org/ml/gcc-patches/2009-12/msg01209.html the testcase in the submitter's description no longer fails, but there is other code in 197.parser that gets the same ICE with the same options. Here's a minimized testcase for that: int strictly_smaller_name (char *s, char *t) { int ss, tt; while ((*s != '\0') || (*t != '\0')) { if (*s == '\0') ss = '*'; else ss = *s++; if (*t != '\0') tt = *t; if (ss == tt) return 0; } } This failure occurs with and without the patch cited above. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #3 from abel at gcc dot gnu dot org 2009-12-28 12:06 --- The patch mentioned by Alexander is not enough to fix the bug after applying all other patches for sel-sched bugs. The actual problem is that when redirecting an edge, the topological order of blocks in the currently scheduling region may be broken. I had a patch to fix this, but didn't apply it to trunk so got beaten by it. We will post it shortly. * sel-sched-ir.c (sel_redirect_edge_and_branch): Recompute topological order after redirecting an edge if needed. diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c index 645093a..2baa461 100644 --- a/gcc/sel-sched-ir.c +++ b/gcc/sel-sched-ir.c @@ -5394,6 +5394,27 @@ sel_redirect_edge_and_branch (edge e, basic_block to) gcc_assert (loop_latch_edge (current_loop_nest)); } + /* In rare situations, the topological relation between the blocks connected + by the redirected edge can change. Update block_to_bb/bb_to_block. */ + if (CONTAINING_RGN (e-src-index) == CONTAINING_RGN (to-index) + BLOCK_TO_BB (e-src-index) BLOCK_TO_BB (to-index)) +{ + int i, n, rgn; + int *postorder, n_blocks; + + postorder = XALLOCAVEC (int, n_basic_blocks); + n_blocks = post_order_compute (postorder, false, false); + + rgn = CONTAINING_RGN (e-src-index); + for (n = 0, i = n_blocks - 1; i = 0; i--) +if (CONTAINING_RGN (postorder[i]) == rgn) + { +BLOCK_TO_BB (postorder[i]) = n; +BB_TO_BLOCK (n) = postorder[i]; +n++; + } +} + jump = find_new_jump (src, NULL, prev_max_uid); if (jump) sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP); -- abel at gcc dot gnu dot org changed: What|Removed |Added CC||abel at gcc dot gnu dot org http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #4 from steven at gcc dot gnu dot org 2009-12-28 12:34 --- Re. comment #3 - do you have an example of when/how this can happen? Perhaps you can add it to the comment. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #5 from amonakov at gcc dot gnu dot org 2009-12-28 14:23 --- (In reply to comment #4) Re. comment #3 - do you have an example of when/how this can happen? Perhaps you can add it to the comment. Here, we are scheduling a loop that looks like this: +---+ | 4 |--+ +-+-+ | | | v | +---+ | | 5 +-+ | +-+-+ | | | | | v | | +---+ | | exit-+ 6 | | | +---+ | | | | | v | | +---+ | | +-+ 7 | | | | +---+ | | | | | | | | | +---+ | | | | 8 |+ | | +-+-+ | | | | | v | | +---+ | -| 9 +---+ +---+ The order of blocks as given by prev_bb/next_bb corresponds to the figure, but in rev_top_order_index BB8 goes before BB6 (which is OK since they are topologically independent). When BB8 becomes empty in the process of scheduling, in the preparation to delete it we redirect BB7-BB9 branch to BB8 (essentially eliminating a now unneeded jump instruction in the end of BB7). The corresponding comment reads in sel-sched-ir.c reads: /* Check if there is an unnecessary jump in previous basic block leading to next basic block left after removing INSN from stream. If it is so, remove that jump and redirect edge to current basic block (where there was INSN before deletion). This way when NOP will be deleted several instructions later with its basic block we will not get a jump to next instruction, which can be harmful. */ This makes BB6 and BB8 topologically dependent. We then merge BB7 and BB8, creating BB6-BB8 branch, which appears to be a backedge (since topological order has not been recomputed). Since the explanation is quite lengthy, we'd prefer to just leave a reference to this PR in the comment. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #2 from amonakov at gcc dot gnu dot org 2009-12-04 18:00 --- (In reply to comment #0) Janis, Thank you for the testcase. This bug and PR42249 are fixed by Andrey's old patch: http://gcc.gnu.org/ml/gcc-patches/2008-09/msg01930.html The patch in that message still applies cleanly. I'm working on re-testing it with current mainline. If you could test that patch in your environment, it would be very appreciated. -- amonakov at gcc dot gnu dot org changed: What|Removed |Added CC||amonakov at gcc dot gnu dot ||org AssignedTo|unassigned at gcc dot gnu |amonakov at gcc dot gnu dot |dot org |org Status|UNCONFIRMED |ASSIGNED Ever Confirmed|0 |1 Last reconfirmed|-00-00 00:00:00 |2009-12-04 18:00:57 date|| http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245
[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched
--- Comment #1 from rguenth at gcc dot gnu dot org 2009-12-02 12:04 --- actually selective scheduling is new, so not a regression -- rguenth at gcc dot gnu dot org changed: What|Removed |Added CC||abel at ispras dot ru Priority|P1 |P3 Summary|[4.5 Regression] ICE in |ICE in verify_backedges for |verify_backedges for|197.parser with sel-sched |197.parser with sel-sched | Target Milestone|4.5.0 |--- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42245