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.
7:13:37
beach
If someone thinks otherwise, I would be interested in knowing where I can find the information.
7:15:21
beach
The ASSIGNMENT-INSTRUCTION is treated specially, because it can turn into a MOV between memory and register.
7:17:56
beach
Also, MIR instructions where the resulting lexical location is the same as the first input location are treated specially. Then we just remove the distinguished stack location from the set in the resulting register configuration.
7:24:19
no-defun-allowed
Irrelevant, but I found some "fundamental rules of writing, editing and publishing" in otherwise blank space in a Lisp journal.
7:24:27
no-defun-allowed
ACTION uploaded an image: Screenshot_2020-02-18_18-11-51.png (96KB) < https://matrix.org/_matrix/media/r0/download/matrix.org/AwlybMFmTPDfpTNWLTzdxtBG >
7:47:35
beach
The French TV news is full of bad grammar. The other day, I heard (in French): Being 4 months pregnant, the fire fighters took her to the hospital.
8:37:34
shka_
do you happen to have adaline implementation laying around? I remotely remember that you were working on neural networks.
8:39:44
no-defun-allowed
I didn't have anything very serious or readable; I still have nightmares of my backwards propagation loop.
8:47:16
no-defun-allowed
I don't have any testing data, but do you want something like https://plaster.tymoon.eu/view/1675?
11:53:06
heisig
Getting SICL to run is much more important than squeezing out the final 2% of a register allocation algorithm.
12:33:50
shka_
well, more importantly, register allocation will be useless unless SICL actually runs
13:10:02
heisig
Phew. Although I'm looking forward to working on such things - once there is a way to run SICL on my machine (or better, my browser).
13:13:17
heisig
By the way, we also booked a room in the Sorell Hotel Seefeld, from April 25 to May 1.
13:29:22
heisig
shka_: SICL is very portable. So its sounds like a natural thing to bootstrap it into WASM at some point.
13:31:44
heisig
I should also mention that I didn't do a lot of proofreading yet. I will upload a better version this weekend.