The Solid-State Register Allocator(mattkeeter.com)
mattkeeter.com
The Solid-State Register Allocator
https://www.mattkeeter.com/blog/2022-10-04-ssra/
4 comments
Hi Mike,
I promise that this was a genuine case of parallel evolution – I didn't read any LuaJIT source or documentation while writing the code or article.
Afterwards, I searched for "reverse linear scan register allocation", discovered the blog post which referenced LuaJIT, and linked it in the text.
I've updated the article to move the LuaJIT reference to the top, and adjusted the phrasing to be clear that this is not an invention, it's simply an interesting implementation. What you call "naive", others may consider didactic :)
Let me know if you have other feedback or suggested changes, either here or via email (in my profile).
I promise that this was a genuine case of parallel evolution – I didn't read any LuaJIT source or documentation while writing the code or article.
Afterwards, I searched for "reverse linear scan register allocation", discovered the blog post which referenced LuaJIT, and linked it in the text.
I've updated the article to move the LuaJIT reference to the top, and adjusted the phrasing to be clear that this is not an invention, it's simply an interesting implementation. What you call "naive", others may consider didactic :)
Let me know if you have other feedback or suggested changes, either here or via email (in my profile).
You may want to clarify that in the GitHub repo, too. See my issue there.
If you want to go the didactic route, then consider documenting the improvements over the naive implementation: register hinting, register priorities (PHI), two-headed register picking, fixed register picking, optimized register picking for 2-operand instructions (x86/x64), register pair picking, ABI calling-conventions, weak allocations, cost heuristics, eviction heuristics, lazy/eager spill/restore, rematerialization, register shuffling (PHI) with cycle breaking, register renaming, etc. That's all in ~2000 lines of lj_asm.c.
If you want to go the didactic route, then consider documenting the improvements over the naive implementation: register hinting, register priorities (PHI), two-headed register picking, fixed register picking, optimized register picking for 2-operand instructions (x86/x64), register pair picking, ABI calling-conventions, weak allocations, cost heuristics, eviction heuristics, lazy/eager spill/restore, rematerialization, register shuffling (PHI) with cycle breaking, register renaming, etc. That's all in ~2000 lines of lj_asm.c.
Done, I've added the same disclaimer to the Github repo.
Given that your Github issue [1] was originally titled "Take Down Notice", I'm now hesitant to read any LuaJIT code.
If I read lj_asm.c and learn from it, will you try to take down any register allocation code that I write in the future?
[1] https://github.com/mkeeter/ssra/issues/1
Given that your Github issue [1] was originally titled "Take Down Notice", I'm now hesitant to read any LuaJIT code.
If I read lj_asm.c and learn from it, will you try to take down any register allocation code that I write in the future?
[1] https://github.com/mkeeter/ssra/issues/1
I had already changed the title after your reply. The objection is about the naming, which implies an invention claim without further explanation. It's not about the code.
Wait,
Are you demanding that independent implementations of an idea you explicitly dedicated to the public domain must then describe the various ways your version is “superior”?
Who hurt you?
Are you demanding that independent implementations of an idea you explicitly dedicated to the public domain must then describe the various ways your version is “superior”?
Who hurt you?
This is such an amazingly uncharitable response.
> I cannot possibly know all of the literature
Maybe this applies to other people too?
> I cannot possibly know all of the literature
Maybe this applies to other people too?
I think he gets dead code elimination for free. When you write to a variable that has no register allocated, it must be dead. Exception is whatever values leave the program or instructions with a side effect.
Scanning basic blocks in reverse is how you calculate liveness. This is ancient, documentedin texts like the Dragon Book, 1988 (from whose perspective it is already old hat).
Liveness extends from definition to use, so you can think about it in the ordinary forward direction. Like when you read code in a high level language, you see some variable definitions near the top of the scope and then look for uses below.
But one problem is that scanning in the forward direction, you don't know that a definition is actually used. A definition of the temporary isn't what makes it live; the uses of the definition is what makes it live. Liveness flows backwards from uses to definitions. The uses say "looking backwards, there is the definition I'm using."
Another problem is, where does the lifetime end? It ends with the last use. Scanning forward, we don't know whether any given use we have seen so far is the last use.
In reverse, the events are in the right order. See a use, the temporary is live there and in prior instructions. If it was live already, nothing changes. See a definition, and it is dead prior to that definition.
This is directly relevant to assigning the temporaries to a smaller set of physical registers.
For that matter, you can use a backward scan to simply reduce the temporaries to a minimal set. So that is to say, take some code that keeps using new temporaries throughout, and do this backward allocation algorithm, using unlimited temporaries (no need to spill). You end up with a version of the code using a smaller set of temporaries.
Liveness extends from definition to use, so you can think about it in the ordinary forward direction. Like when you read code in a high level language, you see some variable definitions near the top of the scope and then look for uses below.
But one problem is that scanning in the forward direction, you don't know that a definition is actually used. A definition of the temporary isn't what makes it live; the uses of the definition is what makes it live. Liveness flows backwards from uses to definitions. The uses say "looking backwards, there is the definition I'm using."
Another problem is, where does the lifetime end? It ends with the last use. Scanning forward, we don't know whether any given use we have seen so far is the last use.
In reverse, the events are in the right order. See a use, the temporary is live there and in prior instructions. If it was live already, nothing changes. See a definition, and it is dead prior to that definition.
This is directly relevant to assigning the temporaries to a smaller set of physical registers.
For that matter, you can use a backward scan to simply reduce the temporaries to a minimal set. So that is to say, take some code that keeps using new temporaries throughout, and do this backward allocation algorithm, using unlimited temporaries (no need to spill). You end up with a version of the code using a smaller set of temporaries.
t1 = a(b, c)
t2 = d(t1)
t3 = e(t1)
t4 = f(t2)
t5 = g(t4)
t5 = g(t4)
t'1 = g(t'2)
t'2 = f(t'2)
t'1 = g(t'2)
t'1 = e(t'1)
t'2 = f(t'2)
t'1 = g(t'2)
t'2 = d(t'1)
t'1 = e(t'1)
t'2 = f(t'2)
t'1 = g(t'2)
t'1 = a(b, c)
t'2 = d(t'1)
t'1 = e(t'1)
t'2 = f(t'2)
t'1 = g(t'2)
t1 = a(b, c)
t2 = d(t1)
t1 = e(t1)
t2 = f(t2)
t1 = g(t2)
Just skimmed, central idea is to linear scan in reverse?
Yep. Allocate in opposite order to execution, assume no branches / control flow / phi nodes. Single pass.
Code published 2009. Description published here: https://lua-users.org/lists/lua-l/2009-11/msg00089.html (ignore the TLS cert error).
Coming up with a silly markting name, writing a naive implementation and then claiming it's their invention is impertinent. Especially since they mention LuaJIT itself in the text ...