[Python-Dev] Rattlesnake progress

[Tim Peters]

[Neil Schemenauer]
> I'm not going to be using hardware registers.  Bytecode will be
> generated to run on a virtual machine.  I can use a many registers as I
> want.  However, I suspect it would be better to reuse registers rather
> than have one for every intermediate result.

I think your intuition there is darned good.

Within a basic block, "the obvious" greedy scheme is provably optimal wrt
minimizing the # of temp registers needed by the block:  start the block
with an initially empty set of temp registers.  March down the instructions
one at a time.  For each input temp register whose contained value's last
use is in the current instruction, return that temp register to the set of
free temp registers.  Then for each output temp register needed by the
current instruction, take one (any) from the set of free temp registers;
else if the set is empty invent a new temp register out of thin air (bumping
a block high-water mark is an easy way to do this).

That part is easy.  What's hard (too expensive to be practical, in general)
is provably minimizing the overall number of temps *across* basic blocks.
Still, look up "graph coloring register assignment" on google and you'll
find lots of effective heuristics.  For a first cut, punt:  just store
everything still alive into memory at the end of a basic block.  If you're
retaining Rattlesnake's idea of treating "the register file" as a superset
of the local vrbl vector, mounds of such "stores" will be nops.

What's also hard is selecting instructions in such a way as to minimize the
number of temp registers needed, ditto ordering instructions toward that
end.  When you think about those, you realize that minimizing the number of
temps is actually a tradeoff, not an absolute good, both affecting and
affected by other decisions.  A mountain of idiosyncratic heuristics follows
soon after <wink>.

but=you-don't-have-to-solve-everything-at-the-start-ly y'rs  - tim