Bug 24232 - [4.1 Regression] ICE: segmentation fault in sched-ebb.c:220 add_missing_bbs
Summary: [4.1 Regression] ICE: segmentation fault in sched-ebb.c:220 add_missing_bbs
Alias: None
Product: gcc
Classification: Unclassified
Component: target (show other bugs)
Version: 4.1.0
: P2 normal
Target Milestone: 4.1.0
Assignee: Jim Wilson
Keywords: ice-on-valid-code
: 23857 (view as bug list)
Depends on:
Blocks: 23478 23579
  Show dependency treegraph
Reported: 2005-10-06 10:27 UTC by Richard Biener
Modified: 2005-10-15 17:29 UTC (History)
4 users (show)

See Also:
Target: ia64-*-linux-gnu
Known to work: 4.0.3
Known to fail: 4.1.0
Last reconfirmed: 2005-10-15 16:55:14

testcase (21.20 KB, text/plain)
2005-10-06 10:28 UTC, Richard Biener
shorter testcase (13.56 KB, text/plain)
2005-10-06 10:33 UTC, Richard Biener
trivial hack to make the reduced testcase work (566 bytes, patch)
2005-10-11 06:26 UTC, wilson@specifix.com
Details | Diff
Untested patch to fix problems with dependency serialization. (2.61 KB, patch)
2005-10-12 03:07 UTC, Jim Wilson
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Biener 2005-10-06 10:27:34 UTC
/usr/lib/gcc/ia64-suse-linux/4.1.0/cc1 -fpreprocessed ellcc.i -quiet -dumpbase ellcc.c -auxbase ellcc -g -O2 -Wall -Wno-switch -Wundef -Wsign-compare -Wno-char-subscripts -Wpacked -Wshadow -Wmissing-declarations -Wmissing-prototypes -Wstrict-prototypes -Wall -Wall -Wno-switch -version -fmessage-length=0 -fno-strict-aliasing -o ellcc.s
/usr/src/packages/BUILD/xemacs-21.5.22/lib-src/ellcc.c: In function ‘add_to_argv’:
/usr/src/packages/BUILD/xemacs-21.5.22/lib-src/ellcc.c:579: internal compiler error: Segmentation fault
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://www.suse.de/feedback> for instructions.

Program received signal SIGSEGV, Segmentation fault.
add_missing_bbs (before=0x2000000000684240, first=0x200000000087bf00, last=0x0)
    at sched-ebb.c:220
220           BB_HEAD (last) = before;
(gdb) bt
#0  add_missing_bbs (before=0x2000000000684240, first=0x200000000087bf00,
    last=0x0) at sched-ebb.c:220
#1  0x40000000012f99e0 in fix_basic_block_boundaries (bb=0x200000000087bf00,
    last=0x200000000087bf00, head=0x2000000000673a80, tail=0x2000000000866d10)
    at sched-ebb.c:329
#2  0x40000000012fad80 in schedule_ebb (head=0x20000000006a1180,
    tail=0x2000000000866d10) at sched-ebb.c:548
#3  0x40000000012fb580 in schedule_ebbs (dump_file=0x0) at sched-ebb.c:618
#4  0x4000000000f34880 in ia64_reorg () at ia64.c:7808
#5  0x40000000012ec220 in rest_of_handle_machine_reorg () at reorg.c:3865
#6  0x4000000000e5ac80 in execute_one_pass (pass=0x600000000000e3d8)
    at passes.c:827
(gdb) up 6
#6  0x4000000000e5ac80 in execute_one_pass (pass=0x600000000000e3d8)
    at passes.c:827
827         pass->execute ();
(gdb) print *pass
$1 = {name = 0x40000000015f6808 "mach",
  gate = @0x4000000001605fe0: 0x40000000012ec170 <gate_handle_machine_reorg>,
  execute = @0x40000000016073f0: 0x40000000012ec1c0 <rest_of_handle_machine_reorg>, sub = 0x0, next = 0x600000000000b2d0, static_pass_number = 155,
  tv_id = 112, properties_required = 256, properties_provided = 256,
  properties_destroyed = 0, todo_flags_start = 0, todo_flags_finish = 3,
  letter = 77 'M'}
Comment 1 Richard Biener 2005-10-06 10:28:07 UTC
Created attachment 9907 [details]

Preprocessed testcase.
Comment 2 Richard Biener 2005-10-06 10:33:56 UTC
Created attachment 9908 [details]
shorter testcase

I have at least three dups of this bug.  Shortest one attached.
Comment 3 Richard Biener 2005-10-06 10:46:05 UTC
Comment 4 Richard Biener 2005-10-06 10:58:32 UTC
Reduced testcase:

RkDefineLine(cx_num, name, line) int cx_num;
  unsigned int linelen = strlen(line);
  char *buf = (char *)malloc(linelen + 1), *sp, *dp;
  while (*sp) {
    while (*sp && ( *sp != ' ' && *sp != '\t' )) {
      if (*sp == '\\' && *(sp+1) )
        *dp++ = *sp++ ;
      *dp++ = *sp++;
Comment 5 Andrew Pinski 2005-10-06 13:24:59 UTC
This happens during ia64_reorg so this is a target bug.
Comment 6 Andrew Pinski 2005-10-06 13:28:03 UTC
I think this is related to PR 23579 and if that is the case then this is caused by PR 23478.  I am going to say this is a regression, even though I don't know for sure.
Comment 7 Andrew Pinski 2005-10-06 17:20:22 UTC
Comment 8 Jim Wilson 2005-10-11 03:20:43 UTC
The patch in PR 23478 has no effect on this testcase.  I tracked the origin of the problem for this testcase down to
        2005-07-31  Jan Hubicka  <jh@suse.cz>                                                         
        * tree-outof-ssa.c (coalesce_ssa_name): Use coalesce_cost.
        (coalesce_vars): Likewise.
        * tree-ssa-live.c (coalesce_cost): New.
        (build_tree_conflict_graph): Use coalesce_cost.
        * tree-ssa-live.h (coalesce_cost): Declare.
But this patch did not cause the problem.  It just exposed a latent problem.  

I noticed that the testcase works if I compile with -fno-reorder-blocks, however, I'm not sure if that is part of the problem, or just hiding the latent bug again.

I am not very familiar with the sched_ebbs code, so this is taking some time.  The insn stream does look funny in the middle of sched_ebb though, while scheduling a region contains basic blocks 1 through 3.  Right before the fix_basic_block_boundaries call, we have
   ...insns from block 1...
   ...insns from block 2...
   branch for block 2 exit
   ...insns from block 1...
   branch for block 1 exit
   ...insns from block 2...
   ...insns from block 3...
   branch for block 3 exit
Note that the branch that ends block 2 has been moved before the branch that ends block 1.  Somehow I don't think that can be quite right.  That confuses fix_basic_block_boundaries, which implicitly assumes that block exits will occur in numerical order.  So after processing the block 2 branch exit, bb becomes block 3.  Then when we process the block 1 branch exit, we have curr_bb as block 1, and curr_bb->prev_bb is block 0, so we call add_missing_bbs with block 3 as first and block 0 as last.  The code then tries to scan backwards from block 0 to block 3 which of course does not work.

I'm guessing a problem with instruction dependencies.  In particular, it may be a problem with insn deps in the presense of COND_EXEC, as there is a COND_EXEC insn between the two branches.  There was a patch in July that changed how this works.

I'll look at this some more tomorrow.
Comment 9 wilson@specifix.com 2005-10-11 06:20:44 UTC
Or maybe I will look at it later tonight.

The problem seems to be that we have no code that will make a jump insn dependent on the previous jump insn when we are scheduling a region that contains multiple basic blocks.  For a target with a single condition code register things will just work out OK, but for IA-64, with multiple predicate registers and conditional execution, we can end up with pairs of branches that aren't dependent on each other, which means that they can be scheduled across each other, which is bad.

With a trivial hack to force a dependency for branches, I no longer get an ICE.
Comment 10 wilson@specifix.com 2005-10-11 06:26:35 UTC
Created attachment 9960 [details]
trivial hack to make the reduced testcase work

Actually, come to think of it, other targets don't use schedule_ebbs unless the -fsched2-use-superblocks option is used, which is probably why others haven't run into this problem.  I haven't checked to see if schedule_ebbs has other ways of preventing jump_insns from scheduling across each other.
Comment 11 Jim Wilson 2005-10-12 02:52:36 UTC
My earlier guess was correct.  It is a problem with the sched_insn_condition_mutex_p code.  Also, there is the problem that the code for handling serialization points for dependencies is confused.

sched-deps creates dependencies for a jump_insn by making it a serialization point.  It is added to last_pending_memory_flush.  This insn will depend on all previous instructions that use memory, and the previous memory flush insn.  All following instructions that use memory will depend on this insn.  This effectively serializes insn dependencies at this point.

The code that fails looks like this
   (jump_insn ... (eq p6 0) ...)
   (note ... NOTE_INSN_LOOP_BEG)
   (cond_exec (eq p8 0) ...)
   (jump_insn ... (ne p8 0) ...)

The first jump_insn goes in last_pending_memory_flush because it is a serialization point for dependencies.

An instruction immediately after a LOOP_BEG note is treated as a serialization point, so we can preserve reg_n_refs info.  So we create a dependency from the
cond_exec to the jump_insn, remove the jump_insn from last_pending_memory_flush, and then put the cond_exec in last_pending_memory_flush.

The second jump is another another serialization point, but it is mutex on the cond_exec insn, so we don't create any dependencies.  And now we have a problem, because the the second jump insn has no dependencies, there is nothing to prevent it from being scheduled before the first jump insn.  This would result in bad code, but fortunately (so to speak) we ICE before we finish because this corrupts the basic block info.

So there are two problems here.

The first problem is that we aren't handling serialization points correctly.  We must always create a dependency for a serialization point, even if the two instructions are mutex.  Otherwise, it will not function correctly as a serialization point.  Thus there must be a dependency between the second jump insn and the cond_exec.

The second problem is that the current code tries to create a list of serialization points, which makes no sense.  Since all instructions before the last serialization point depend on the last serialization point, there is no point in keeping track of more than one of them.  Only the last one is useful.  However, the code is trying to maintain a list of branch instructions as our serialization points.  This can not work.  While it does make some sense to keep a list of branch insns for the purposes of handling dependencies, it does not make sense to also make them serialization points.  The code is trying to use last_pending_memory_flush for too different incompatible purposes.

I've got a patch that fixes this, though I am not entirely happy with it.  I added a "uncond" argument to add_dependence_list so I can force dependencies to be emitted for last_pending_memory_flush.  I also removed the code that was handling last_pending_memory_flush as if it was a list.  It is not possible for this to be a list and still work correctly as a serialization point.  In theory, this makes the field pending_flush_length obsolete.  Unfortunately, sched-rgn.c is using it in a strange way I don't understand.  It is trying to concatenate lists of last_pending_memory_flush, but we can never have more than one from sched-deps.c's point of view.  I left it alone.  Maybe this does work if you call sched-dep separately for individual basic blocks.  Another downside to my patch is that it creates more serialization points than is necessary or ideal, but this can't be fixed without more work.

Ideally, the code for handling jump_insns should be a separate list from last_pending_memory_flush.  Just like we have a list of pending reads and a list for pending writes, we can have a list for pending jump_insns.  And then when we need a serialization point for real, because the lists got too big or whatever, then we use last_pending_memory_flush, and there is only ever one entry in last_pending_memory_flush.
Comment 12 Jim Wilson 2005-10-12 03:07:17 UTC
Created attachment 9975 [details]
Untested patch to fix problems with dependency serialization.

This adds an UNCOND argument to add_dependence_list, so that all structural dependencies can be made unconditionally.  Examples of structural dependencies are serialization dependencies on last_pending_memory_flush, dependencies added to preserve REG_N_CALLS_CROSSED==0, and dependencies for clobbers.  All other dependencies are still created only if the two instructions are not mutex.

This also eliminates some redundant JUMP_INSN dependency handling, as both sched_analyze and sched_analyze_insn were creating dependencies for JUMP_INSNs.  I deleted the former one.

This also stops trying to treat last_pending_memory_flush as a list.  It can not function both as a list and as a serialization point.

This patch effectively makes pending_flush_length obsolete, but I can't delete it because sched-rgn.c is using it in a strange way I don't understand.

This patch probably makes more dependencies than is necessary or desirable, but some development work will be needed to fix that.  I believe that we can keep a list of pending branch insns by keeping a list parallel to the pending read and pending write lists.  This would help reduce the number of dependencies, and help with cross block scheduling.  This will be a bit of work though, and may not be reasonable to attempt at this late point.
Comment 13 CVS Commits 2005-10-15 16:34:18 UTC
Subject: Bug 24232

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	wilson@gcc.gnu.org	2005-10-15 16:34:13

Modified files:
	gcc            : ChangeLog sched-deps.c 

Log message:
	Fix IA-64 sched-ebb failure due to missing dependencies.
	PR target/24232
	* sched-deps.c (add_dependence_list): New arg UNCOND.  Fix all callers.
	(add_dependence_list_and_free): Likewise.
	(sched_analyze_2, case MEM): Delete sched_insns_conditions_mutex_p


Comment 14 Jim Wilson 2005-10-15 16:55:14 UTC
Mine.  IA-64.
Comment 15 Jim Wilson 2005-10-15 16:56:44 UTC
Fixed.  Simplified patch added to mainline here:
Comment 16 Steven Bosscher 2005-10-15 17:26:18 UTC
*** Bug 23948 has been marked as a duplicate of this bug. ***
Comment 17 Steven Bosscher 2005-10-15 17:29:19 UTC
*** Bug 23857 has been marked as a duplicate of this bug. ***