Re: [dataflow] PATCH removal of more of flow.c.

[Joern RENNECKE <joern dot rennecke at st dot com>]

Kenneth Zadeck wrote:

> This is the kind of time bomb that the back end is just filled with.
This one is more than 10 years old.

>  
> If your pass depends on a datastructure computed some earlier pass it
> should make damn sure, in big bold type, that nothing better move it
> around. 
It's not really my pass; Jim Wilson contributed it before I joined Cygnus.
And the LOG_LINKS are only the starting point; validity is checked with 
manual
scanning and REG_DEAD notes.  The freshness of the LOG_LINKs is really the
least of your worries there...

> A better way is to just recompute it.
>
> The code that (on the dataflow branch) just was added by zdenek to
> combine, to be pulled out and made public.
I suppose you mean create_log_links?
At the moment, it's file static, although that should be easy to change.

>  This is much cheaper that
> computing both ru and du.
>
>  
But right now we need LOG_LINKS and REG_DEAD notes, plus linear scanning
from def to use to REG_DEAD note.  To make the code robust to pass-ordering,
REG_DEAD notes need to be recomputed.  Plus, this code predates exception
handling, cross-block scheduling, and PRE, so it misses optimizations when
control and/or data flows merge, and I suspect it doesn't work quite 
right in the
presence of exception handling.  When there are sequences with lots of calls
using the same address, the scanning complexity gets quadratic.
If this code has to be reworked, I'd rather have it reworked properly so 
that it
interacts sanely with modern infrastructure and passes.
Since exception handling causes a BB end at each call site, I can't see how
we could sanely and safely handle more than one call using the same 
value for the
address without more or less solving the reaching uses problem when 
exception
handling is enabled.
We could do without the reaching definitions if we continue to require the
definition and all its uses to be in a linear insn stream without 
labels, but
it'd keep this pass falling back as we add more cross-block optimizers 
which separate
the definitions from the uses, and IIUC RD is much cheaper than RU, so if we
already do RU, we might as well also do RD and do a proper job.

I suppose one way to reduce the cost of RU generally would be to find 
first scan
the insns backwards to quickly get rid of all the uses that have a 
dominating
definition in the same extended basic block.  (We can have a list of 
pending uses
for each reg; if we reach a definition, these uses of the defined 
register are tied to
that definition; if we reach a label or EH handler start (can these 
come without
 labels?), all the pending lists are flushed.)
Only the remaining uses need space in the bitvectors used in propagating 
reaching
uses across blocks.  (We can build a list of these uses by concatenating 
the pending
list we flush at labels/EH handler starts).