libera/#sicl - IRC Chatlog
Search
7:28:18
beach
The static part of the thesis is looking more and more like exactly what we are doing.
7:55:31
hayley
<https://gitlab.common-lisp.net/cmucl/cmucl/-/wikis/CmuclDesign> says "The scarcity-oriented aspect of “register allocation” is handled by a greedy algorithm in pack." and it sounds like the same register allocator is used in SBCL.
7:58:35
hayley
I am not sure of that. At least LLVM has separate "greedy" and "linear scan" register allocators.
8:00:33
hayley
According to <https://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html>, a greedy register allocator is called greedy because it gives priority to locations which live the longest.
8:23:59
beach
I guess we are not addressing the "where to put the spills" issue at all. That issue reminds me of partial redundancy elimination.
10:46:32
scymtym
i couldn't follow the entire discussion, but in case it hasn't been said already: SBCL has two register allocators: the "greedy" one and another one based graph coloring. the latter is selected for high-ish optimize speed policy
11:01:01
hayley
Righteo. Out of curiosity, where can I find the graph colouring allocator in the SBCL sources?
13:12:58
hayley
Okay. I must have missed it while skimming, as I didn't find the word "graph" in it, and there was a lot to go through.
13:15:09
shka
well, maybe it is not graph coloring algorithm, but it certainly is register allocator
13:17:23
beach
The only way I could think of to make graph coloring work reasonably well was to run it for each loop from the innermost to the outermost. Otherwise, as described in the literature, it either allocates a variable to a register permanently, or to a stack location permanently. That doesn't seem like a great idea.
13:20:37
hayley
https://www.snellman.net/blog/archive/2004-10-17.html mentions just that for a greedy allocator.
13:28:47
shka
https://pvk.ca/images/2014-03-23-what-i-look-for-in-gsoc-proposals/regalloc-abarch.pdf
15:15:51
jcowan
Reynolds has a historical paper called "The Discoveries of Continuations, detailing the 8 times that continuations were discovered before everybody in the research community knew about them.
15:18:19
jcowan
Two of the authors had different surnames and turned out to be distantly related, but did not know of each other's work, or even each other.