Re: local data flow

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

Kenneth Zadeck wrote:

> From that description I assumed that you really did care which uses
> actually reached which other uses.  The reaching uses problem tracks
> each use separately.  If this isn't what you need then you are free to
> use LR which is certainly much cheaper than RU.
>  
Yes, LR is perfectly adequate.  I was thinking in terms of def-use 
chains only
because these can be kept more comprehensively up-to-date - i.e. when a 
register
is live in a loop solely because it is used afterwards, and the use 
after the loop
goes away, def-use chains won't keep a lingering livenes of the register 
in the
loop.
But since the exiting def-use chains don't actually fit the problem, 
there is no
point in trying to use them here.

So, in summary, the plan is:
- Use LR (Live Registers) information for if-conversion / cross-jumping.
- Update the information after each transformation to keep a correct, 
but not necessarily
 minimal solution.
- After traversing the entire flowgraph, if anything changed, re-compute 
LR from scratch.
- After re-computing LR, we need to traverse the flowgraph again.  This 
might mean we
 end up doing more if-conversion / cross-jumping checks than with the 
current scheme, but
 since these checks are local, this should be generally cheaper than 
trying to keep a minimal
 LR solution all the time.

I'm not sure how to best handle splitting blocks when doing cross-jumping.
propagate_block can produce inconsistant liveness information for stack 
regs after
reg_stack.  Currently this is handled by zeroing out all the stack reg 
liveness information.
Maybe we shouldn't even try to update LR for the split upper parts of 
the original BBs.
The live-at-end information for the joined lower part should be 
bassically the same as both
blocks original BBs had, and doing further optimizations with a partial 
or fully joined block
appears not unlikely; however, the remaining unjoined upper parts of the 
original BBs
are somehow differentfrom each other, so any further cross-jumping for 
them, while not
impossible, seems unlikely - AFAICT it would require a complete 
corss-jumping of the joined
lower part with some other block.  So maybe we could mark them has 
having no valid LR
information, and not consider them again till the next global LR 
recomputation.