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.