Re: Flow analysis and optimization with computed gotos

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

Oliver Ruething, one of the original authors of LCM, has written
a paper on how to do LCM in the presence of critical edges (in
particular, with GCC's computed gotos).  The paper can
be found at

http://sunshine.cs.uni-dortmund.de/~ruething/

and its title is

Bidirectional Data Flow Analysis in Code Motion: Myth and Reality

The title may be misleading---the paper is really about how
to do this with unidirectional data flow analysis.  The algorithm
he gives is a modification of the algorithm already implemented in GCC.

One particularly interesting aspect of the algorithm is that it
puts into a kind of superblock all computed gotos that have
the same targets, so in a typical finite-state machine, where
there is one global array of targets, the number of abnormal
edges one must deal with is reduced from G*T (where G is the
number of gotos and T is the number of target labels) to T.
This is not operating on subgraphs, but it is operating on
a greatly reduced representation of the flow graph.

I would very much like to have this algorithm in GCC 3.0;  it would
help my code and perhaps some other types of important code (JVM
implementations, for example).

Brad

> 
> On Tue, Dec 05, 2000 at 03:26:38PM +0000, Joern Rennecke wrote:
> > We can still pretend to work on the entire graph, and thus get all
> > subgraphs.
> 
> But part of the problem with Brad's test cases is the relatively
> complete connectivity of the graph.  For such examples it would
> seem to be most efficient to actually operate on the subgraphs.
> 
> 
> r~
>