On Thu, 18 Nov 2004 08:13:02 +0100, Leopold Toetsch <[EMAIL PROTECTED]> wrote:
> Bill Coffman <[EMAIL PROTECTED]> wrote:
> > ps: I'm making progress on grokking the cfg and register renaming
> > stuff. Will let you know.
>
> This needs an SSA graph of the data flow?
Static Single-Assignment (I had to look it up). My approach is to
consider something you once said, which was to the effect of ensuring
the accuracy of the analysis. I've got some code to do a fairly
simple depth first search per symbol. It is slower (I presume), but
easier to understand. Later, I plan to (or someone else could)
implement the data flow stuff with bit vectors and SSA to determine
reachability, etc. In this way, I can compare the simple analysis
with the complex analysis, and convince myself, and anyone else that
the code is correct. All this will be done even before verifying the
program runs correctly (passing "make test").
"Advanced_Compiler_Design_&_Implementation" by Muchnick is my main
resource. Register renaming is easy enough when you have DU (def-use
("def" means value is written, "use" means value read) and UD chains,
and especifically "webs" (which connect defs to uses). Webs are
components of def-use chains (using graph theory language). They are
effectively different variables, and can be provided with separate
symbol names, which is actually very similar to what is done during a
spill. My depth first search algorithm finds these too. Like I said,
I wanted to start with something simple that is correct, and move
forward with the more optimized forms later.
Another thing I'd like to do, is throw in is a randomizer, to change
the way the allocator assigns registers. Considering all the cruft
that was uncovered when the algorithm was changed, it might be a good
idea to have a debug feature that selects registers differently each
time it runs (each allocation should be valid, of course). This could
help flesh out any other faulty assumptions in the parrot compiler.
> BTW, looking at analyse_life_block() it seems that this allocates
> unconditionally a Life_range structure. As these are O2 in (n_symbols *
> n_basic_blocks) we could safe huge amounts of memory, by defining that a
> missing life block propagates the previous one. Dunno if its possible,
> though.
That's definitely not very efficient. Plus it's mallocing each
Life_Range, which is usually at least another 8 bytes per chunk, and
then a lot of potential thrashing when freed. It seems I've seen a
lot of less than optimum code like this, and I suspect there's a lot
more like it.
Solving these things will bring me that much closer to the ultimate
goal of defeating Dan's evil code. ;)
> leo
>
Bill
