[PATCH] resubmitted for review to fix modulo scheduling. COMMITTED

[Kenneth Zadeck]

Bernd Schmidt wrote:
> I think I have an idea where our misunderstanding arises.  Absent any
> documentation on these problems in the gcc source I had looked into
> one of my books, which had a few lines describing upwards exposed use
> as an algorithm which connects uses with the definitions that can
> reach them.  However, now that I've looked for that, I can't actually
> find any code that produces per-use information.  AFAICT, the RU code
> in df-problems only produces some per-block, not per-use, bit vectors.
>
> So, there's a potential source of misunderstandings - I was thinking
> about values, while it seems to me now that you were thinking about
> liveness information, which is indeed more or less unaffected by
> partial stores.
>
> Let me know if I've understood this correctly now.  I still object to
> the special-casing of partial refs, but I'll cut that argument from
> this mail and send it once we've resolved where we misunderstand each
> other.
>
>
> Bernd
Flow is a uniquely bad way to learn about what dataflow really should
be.  One of the reasons that df is (in your opinion) so poorly
documented was that I just assumed that everyone had a textbook (almost
any compiler textbook) understanding of dataflow analysis.  I know that
this is not true which is why I volunteered to do a dataflow tutorial at
the summit, but in terms of where to put my effort on the doc, it was to
document the things that were obscure and visible to the client. 

The way that dataflow works everywhere else in the world is that it
computes sets of facts at the beginning and end of each basic block, the
in and out sets. 

To do this it first builds a set of transfer functions, one set for each
basic block, that describe the effects of this block.  For the textbook
problems, the transfer function can be implemented with two bit vectors,
gen and kill.  Flow does not do this, it re examines the basic block
each time the iteration reaches the block.

These gen and kill sets are not well documented in my code, but then
again they are fairly useless to anyone once the in and out sets have
been computed.  And the sparse_kill sets would be really hard for
someone to use, but again it is just there to make the processing of the
transfer functions work efficiently and they are of no use to any client.

Then the control flow graph and those transfer functions are used to
produce the correct values in and out sets.  The in and out sets are
what people use and if they need to look inside a block, they do have to
interpret from either the beginning or end of the block them selves. 

On the dataflow branch I have some functions to help with this for the
simple liveness.  I use these in ifcvt to replace the propagate block
code, but in general the client is on his own.
Building these kinds of functions for the other problems might be
helpful but so far I have not seen the need or have the time.

Kenny