7:09:05hayleyIt 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:28hayleyFunny that the latter uses a fast Fourier transform program for performance evaluation.
7:11:40beachYeah. 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:12:38hayleyOh, right, that would indeed be a long basic block.
7:55:31hayley<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:57:06beachSo that one might not be that great. "Greedy" sounds like "linear scan" to me.
7:58:35hayleyI am not sure of that. At least LLVM has separate "greedy" and "linear scan" register allocators.
7:59:04beachI see. Well "greedy" is usually a very general term.
7:59:29beachAs I recall, linear scan is sort of like LRU for page eviction.
8:00:33hayleyAccording 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.