Re: [RFC] third liveness pass

[law at redhat dot com]

 In message <20020527120043.GB8249@atrey.karlin.mff.cuni.cz>, Jan Hubicka 
writes:
 > > On Mon, May 27, 2002 at 09:00:44AM +0200, Jan Hubicka wrote:
 > > > 	* basic-block.h (PEOP_SCAN_DEAD_STORES): New.
 > > > 	(PROP_FINAL): Include.
 > > > 	* flow.c (life_analysis, update_life_info,
 > > > 	init_propagate_block_info, mark_set_1, mark_used_rgs):
 > > > 	Support SCAN_DEAD_STORE.
 > > 
 > > Ok.
 > Looking at the code, we still run dead store removal when not
 > optimizing.  That looks like mistake, as the pass really is somewhat
 > expensive.
Agreed.

 > Would be OK to make patch that moves PROP_SCAN_DEAD_STORES out of
 > PROP_FINAL and makes the PROP_FINAL pass to include it conditionally?  I
 > still guess we can include dead code removal as it pays back by avoiding
 > reload/global to work too hard.
Seems reasonable.

Another idea for doing DSE in a much cleaner, potentially less expensive
way would be to look at dependency information.

Look at the dependencies generated when scheduling if we find that a store Y
is a direct descendant of store X in the dependency tree and X and Y are the
same memory location, then Y _may_ be a dead store.

The problem boils down to determining if there is some valid schedule which
could result in X firing resolving the final dependency for Y.  If there is
such a schedule, then Y is a dead store.

So this means that we'd need to prove that none of other descendants of X
reach Y in the dependency tree -- and do so in a reasonable amount of
computation.

So conceptually you could hook in a memory optimizer to run immediately
after we build the dependency graph for scheduling. 

Alternately you can hook right into the scheduler code and detect some of these
as we actually resolve dependencies -- it's fast, but less clean and may
miss some redundant memory operations.

These schemes may or may not be less expensive than the DSE code currently
in flow.c, but it might be worth an investigation.

jeff