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