Analysis of Brad's GCSE problem with computed gotos.

[Michael Matz <matzmich at cs dot tu-berlin dot de>]

Hi,

after some battling with RTL dumps > 18 Mb I guess I know, where the
problem with computed goto's and GCSE lies, which manifests for Brad's
_io.i file (see also optimization/732 and the thread there). The problem
are memory accesses hoisted over abnormal edges (like in computed
jumps). The program below demonstrates that (see below):

------ snip ------
extern void abort (void);
extern int ei;
extern int * get_ip ();
 
int main(void)
{
  static void * table[] = {
    &&jump ,&&L0, &&L1, &&L2
  };
  int *ip;
  int e = 0, f = 0, state = 3;
 
  goto jump;
 
L0:
  f = ip[35];
  goto L1;
L1:
  e = ip[35];
  goto end;
L2:  ip = (int*)4;
  goto end;
 
jump:
  ei = 23;
  ip = get_ip ();
  goto *table[state];
 
end:
  if (ip != (int*) 4 || (e+f) != 0) abort();
  return 0;
}

int ei;
 
int * get_ip ()
{
  return 0 /*&ei*/ ;
}
-------- snap --------

This program crashes when compiled with -O2 but not with "-O2 -fno-gcse".
The reason is, that the second "ip[35]" is partial redundant. Normally
this would be eliminated, and instead a ip[35] evaluation placed on the
edge <jump,L1>. As this is a abnormal edge, which can't be split that
easily, GCSE simply adds this instruction to the end of the source block.
Of course nothing could be more wrong, if the instruction in question is a
trapping one (like memory access) which wouldn't be called in normal flow
(like in the above program, where ip==0, which traps, when placed before
the table jump). There is also some commentary in pre_edge_insert()
regarding this situation.

Basically the same situation also happens with Brads testcase. There a
redundant memory access is moved up from some (around 37) blocks to
the dispatch block, without noticing, that now there is the possibility,
that this memory access is reached by a def which is invalid for mem
access (basically something like:
"int* i=12; goto L; ...; L: a=*i; table-jump;" )

We could either disable the moving of (mem:...) over abnormal edges (which
then would mean, that we would have to undelete the PR instruction), or we
could avoid to mark these instructions as deleted from the beginning
(which is not that easy, as we only want to disable them, if there are any
disturbing abnormal edges). Suggestions?


Ciao,
Michael.