Linear scan register allocation in Datalog 0 ▲ Max Bernstein's Blog 28 minutes ago · 9 min read1708 words · Tech · hide Note: This was supposed to be published basically immediately after PLDI 2026 but I got hung up on posting it because I am not a Datalog native like Yannis is and I like understanding everything I post. But I guess that’s what expert co-authors are for, right? It’s a little rough but it’s been so long that the editing is holding up the posting. Happy reading. Last year I wrote my first register allocator: a small linear scan implementation in Ruby on SSA. Immediately after publishing the post, I had a call with Waleed Khan where he walked me through implementing the liveness fixpoint algorithm in Datalog. We talked about doing the whole register allocator in Datalog—how hard could it be?—but it never materialized. This year, though, I met Yannis Smaragdakis at PLDI. I did my usual thing, which is to nerd snipe other people into doing interesting projects: in this case, full linear scan in Datalog. Several short hours and several beers later, we have an implementation that I only… Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town