[Python-Dev] Rattlesnake progress (original) (raw)

Tim Peters tim.one@comcast.net
Tue, 19 Feb 2002 15:01:28 -0500

[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 .

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