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.
7:10:07
beach
Finally, each set contains a set (represented as a list probably) of locations in which the value of the lexical variable is present. A member of that latter set is either a register or a special value indicating that it is present in its distinguished stack location.
7:10:18
beach
There is a huge number of cases to handle in the algorithm, so I probably won't list them all here and now. But the main idea is that when an instruction is encountered that makes a new variable V live, we compare its distance to those of other live variables, and we base a decision on this comparison.
7:10:27
beach
If V has a shorter distance that some other variable W, we look at the set of locations of W. If W is present in its distinguished stack location, we just take its register and use it for V instead. If not, we spill it first.
7:10:28
beach
That's the basic idea, but callee-saves registers complicate the situation, as does the fact that many x86 instructions require the first source and the destination to be in the same register.
7:11:41
beach
Obviously, if we have a back arc, we have to adapt the register allocation to the decision already made for the instruction at the head of the arc.
7:13:02
beach
I have seen no indication that this idea is present in any existing algorithm for register allocation.