libera/#sicl - IRC Chatlog
Search
6:55:42
beach
hayley: Did you ever write those toy functions and read the generated LIR to get an idea of how well register allocation is performing?
6:58:56
hayley
Everything I could think of involved function calls, which don't provide a lot to look at.
7:00:05
beach
Only if you have time and feel like it. I am just curious since the technique is presumably new.
7:02:00
hayley
Are you aware of Ivan Burrough's PhD thesis "Register allocation and spilling using the expected distance heuristic"?
7:03:26
hayley
https://dspace.library.uvic.ca/bitstream/handle/1828/7107/Burroughs_Ivan_PhD_2016.pdf
7:09:05
hayley
It also references "The Power of Belady's Algorithm in Register Allocation for Long Basic Blocks" which is in my browser history but I don't remember reading it.
7:10:28
hayley
Funny that the latter uses a fast Fourier transform program for performance evaluation.
7:11:40
beach
Yeah. It is fairly easy to write a program that generates a special version of the FFT for a particular size. And then the code is completely linear with no branches.
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.