Bad code generated by inter-block scheduling

[Ulrich Weigand <weigand@i1.informatik.uni-erlangen.de>]

Hello,

current mainline miscompiles gcc.c-torture/execute/loop-14.c with -Os
due to what I believe to be a bug in inter-block scheduling in sched-rgn.c.

The test case is:

void f(int *a)
{
  int i;

  for (i=3; --i;)
    a[i] = 42 / i;
}

which gets transformed into (before scheduling):

basic block 0:
  reg51 = 3
  reg61 = 42
  reg66 = a + 12
  goto basic block 2

basic block 1:
  reg62 = reg61 divmod reg50       [*]
  mem(reg66) = subreg(reg62)
  fall through to basic block 2

basic block 2:
  reg50 = reg51 - 1
  reg51 = reg50
  reg66 = reg66 - 4
  if (reg50 != 0) goto basic block 1

Now, interblock scheduling goes and moves the divmod instruction [*]
into basic block 2.  This causes a division by zero to happen at
runtime.

While sched-rgn.c correctly detects that [*] is an insn that may
trap, it ignores this fact, because it considers this move to be
a regular interblock motion, *not* a speculative motion, i.e. it
thinks the divmod instruction would have been executed in any case
even before the move, so trapping doesn't matter.

The task of distiguishing between interblock and speculative motion
is done using the notion of 'potential-split-edges', as computed
by compute_dom_prob_ps in sched-rgn.c.  As I understand this code,
it looks for (generalized versions of) situations like this:

      [A]
     /   \
  [B]     [C]

If it finds such an edge A -> C, then a move from B to A would be
speculative, else it is a regular interblock motion.

Now, in this particular case, we obviously *do* have exactly that
situation, with [A] = bb2, [B] = bb 1, [C] = exit block.

However, the data structures available to compute_dom_prob_ps simply
do not contain the 'bb2 -> exit' edge in the first place!  This is
because where the private structures in sched-rgn.c are built
(build_control_flow), all edges leading to the exit block are 
completely ignored:

  nr_edges = 0;
  for (i = 0; i < num_edges; i++)
    {
      edge e = INDEX_EDGE (edge_list, i);

      if (e->dest != EXIT_BLOCK_PTR
          && e->src != ENTRY_BLOCK_PTR)
        new_edge (e->src->index, e->dest->index);
    }

From what I see from the revision histories, the behaviour apparently
has been the same since forever, so I don't know why this suddenly
shows up as a problem ...

Simply adding entry/exit edges to the sched-rgn.c tables is not completely
trivial due to the negative block index numbers; several global arrays in
sched-rgn.c are indexed by block number.  Any suggestions how to fix this?

Thanks,
Ulrich

-- 
  Dr. Ulrich Weigand
  weigand@informatik.uni-erlangen.de