Re: Analysis of Brad's GCSE problem with computed gotos

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

Sorry, misspelled the mail list address.

----- Begin Included Message -----

From lucier@math.purdue.edu  Tue Dec  5 16:50:50 2000
Date: Tue, 5 Dec 2000 16:50:34 -0500 (EST)
From: Brad Lucier <lucier@math.purdue.edu>
To: law@redhat.com
Subject: Re: Analysis of Brad's GCSE problem with computed gotos
Cc: lucier@math.purdue.edu, matzmich@cs.tu-berlin.de, hosking@cs.purdue.edu,
   gcc@gnu.org, feeley@iro.umontreal.ca

Jeff Law writes:

> It's fairly simple to prevent unsafe movement across an abnormal edge.
> 
> Just consider any expression which might trap dead at the start of any block
> which is the destination for an abnormal edge.
> 
> It's not perfect (in the sense that we can lose some optimization), but
> it is simple and will always generate correct code.

Tony Hosking explained to me yesterday that to prevent incorrect code
generation one needs to make either a precise flow analysis (which may
be effectively impossible with abnormal critical edges), which allows
the most optimization, or an imprecise but conservative flow analysis,
which allows correct but imperfect optimization.

I like your suggestion, which seems less conservative than having all
expressions killed on abnormal critical edges, and so could lead to
better optimization.  On the other hand, if you have 10,000 basic
blocks and several million edges, one cannot do gcse on that flow graph
at all because of the memory requirements of the current data
structures in gcse.c.

So perhaps the best thing would be to use your approach with medium
sized flow graphs (either <= 1000 basic blocks or < 20 edges/basic
block) and to use, for more extreme flow graphs, the more conservative
flow analysis of having everything killed on abnormal critical edges
that might allow one to ignore abnormal critical edges entirely during
some parts of PRE and LCM.

Brad


----- End Included Message -----