freenode/#sicl - IRC Chatlog
Search
7:09:25
beach
Here is my latest thinking on register allocation. My idea is based on an algorithm for demand paging called OPT. In the context of paging, it is an optimal algorithm, but that can not be implemented because it assumes knowledge of how far in the future a page is going to be used.
7:09:36
beach
In a MIR graph, however, we can estimate how far in the future a lexical variable is going to be used, depending on the estimated probability for certain control branches to be taken. To give an example, we might say that a function call takes 100 instructions and that a loop is executed 10 times. Either way, the estimate of distance is separate from the register-allocation algorithm.
7:09:54
beach
So suppose that for each program point we keep a set. An element of the set represents a lexical variable. Each set contains a distinguished stack location to be used when the lexical variable can not be located in a resister. Each set also contains a likely future distance before that variable is used, and a flag, indicating whether the use of the variable at that distance is beyond a FUNCALL-INSTRUCTION or not.