computed gotos and memory requirements.

[Brad Lucier <lucier at math dot purdue dot edu>]

After some more experiments, it seems that the threaded state machine
code, with a computed goto in each block, goes significantly faster on
a Pentium II than code where you have a single "computed goto" block,
and you explicitly jump to that block whenever you want to jump to the
next block in the thread.

One problem I'm having is the amount of memory that flow.c allocates for
these kinds of codes.  One test case that I cannot compile on a RH 6.1
intel box with 192 Mbytes of real memory and 128 Mbytes of swap has 3003
possible target labels, and at least 1220 computed gotos.  When I examine
the code in flow.c, it appears that this results in 3003*1220=3663660
edge structures allocated just for the computed gotos.  (Please correct
me if I'm wrong.)  By my count in basic-block.h, each edge_def struct
contains 6 pointers and two ints, or 32 bytes per edge_def on a PII, or 56
bytes per edge_def on the alpha, so we're talking 117,237,120 bytes for
this information on the PII, 205,164,960 bytes on the alpha.  Otherwise,
there are about 4173 regular gotos, each of which requires one edge_def,
plus some fall-throughs, etc., so that part of it is insignificant.

I'm wondering what you get for all this information for the computed
gotos.  Can you split one of these edges?  I can't see how.  Can you add
instructions to one of these edges and not to another edge from the same
goto, or to the same label?  I can't see how either.

Wouldn't it be much more efficient, and give you the same amount
of useful information, to have one more type of edge information,
an EDGE_COMPUTED edge, that would point to a single array of possible
label addresses, with their information stored only once and shared by
all the EDGE_COMPUTED edges?

Long run times are an annoyance, but allocating too much memory can make
it impossible to compile something.

This is important to me, so I'm going to look into it, but I obviously
don't know now all the uses to which the edge information is put.
If someone can tell me in two seconds that sharing all the information
for computed gotos won't work, I'd appreciate it if you could tell me now.

Brad Lucier