[Python-Dev] Rattlesnake progress

[Neil Schemenauer]

Tim Peters wrote:
> Within a basic block, "the obvious" greedy scheme is provably optimal wrt
> minimizing the # of temp registers needed by the block

I already had this part of the plan mostly figured out.  Thanks for
verifying my thinking however.

> What's hard (too expensive to be practical, in general) is provably
> minimizing the overall number of temps *across* basic blocks.

This was the part that was worrying me.

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

Okay, that's easy.  I suspect it will work fairly well in practice since
most functions have a small number of basic blocks and that increasing
the number of registers is cheap.

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

I'm planning to keep this idea.  There seems to be no good reason to
treat local variables any differently than registers.  I suppose it
would be fairly easy to add a simple peep-hole optimizer that would
clean out the redundant stores.  When you talked about flexible
intermediate code did you have anything in mind?

Hmm, perhaps constants can be handled in a similar way.  The only way I
can think of doing it at the moment is to copy the list of constants
into registers when the frame is created.  That seems like it could
easily end up as a net loss though.

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

But is there really any freedom to do reordering?  For example, a
BINARY_ADD opcode to end up doing practically anything.

  Neil