freenode/#sicl - IRC Chatlog
Search
6:19:37
beach
Random ideas about register allocation. I have been pondering how to express the x86 constraint that for a typical operation, the first operand must be in the same register as the result. I think I can express that constraint by introducing anonymous registers with an identity. So if I have z <- op(x, y), I can express that as R <- x, R <- op(R, y), z <- R.
6:20:06
beach
Then the problem of register allocation is reduced to assigning anonymous registers to real ones.
6:20:56
beach
I would have a mix between anonymous and real registers in LIR because instructions such as the FUNCALL-INSTRUCTION require arguments to be assigned to specific registers.
6:29:41
beach
Also, it is not quite correct to say that a lexical variable is "assigned to a register", because at any program point, several registers can contain the value of that variable. Take my previous example. A valid solution might have x in some register R' /= R before the operation. Then R <- x will make both R and R' contain the value of x.
6:30:30
beach
I mention that because I think some published techniques for register allocation assume at most one register for each variable.
6:35:00
beach
Hmm. So I think I can make it such that lexical variables appear only as either input or output (but not both) of ASSIGNMENT-INSTRUCTIONs.
6:38:11
beach
Then I can determine a cost of the assignment instruction for different cases. Let's say we have an ASSIGNMENT-INSTRUCTION R <- v. Then if before that instruction v is already in R, then the cost is 0. If v is in a register other than R, the cost is (say) 1. Finally if v is in memory, the cost is higher, say 10.
6:39:33
beach
Not sure this information will help me find a complete technique for register allocation, but it might be a valuable observation.