In my last post, I explained a bit about how to retrofit| Max Bernstein
bernsteinbear.com search| bernsteinbear.com
The sprintf family of functions (sprintf, snprintf, vsnprintf, …) have this little-known feature to what size your buffer should be. In cases where you don’t have a fixed upper bound, this is really useful.| Max Bernstein
After publishing Linear scan register allocation on SSA, I had a nice call with Waleed Khan where he showed me how to Datalog. He thought it might be useful to try implementing liveness analysis as a Datalog problem. We started off with the Wimmer2010 CFG example from that post, sketching out manually which variables were live out of each block: R10 out of B1, R12 out of B2, etc. The graph from Wimmer2010 has come back! Remember, we’re using block arguments instead of phis, so B1(R10, R11) ...| Max Bernstein's Blog
Much of the code and education that resulted in this post happened with Aaron Patterson. The fundamental problem in register allocation is to take an IR that uses a virtual registers (as many as you like) and rewrite it to use a finite amount of physical registers and stack space1. This is an example of a code snippet using virtual registers: add R1, R2 -> R3 add R1, R3 -> R4 ret R4 And here is the same example after it has been passed through a register allocator (note that Rs changed to Ps)...| Max Bernstein's Blog
first – previous EDIT: /u/thunderseethe correctly points out that this is closure conversion, not lambda lifting, so I have adjusted the post title from “lambda lifting” to “closure conversion” accordingly. Thanks! I didn’t think this day would come, but I picked up the Ghuloum tutorial (PDF) again and I got a little bit further. There’s just one caveat: I have rewritten the implementation in Python. It’s available in the same repo in compiler.py. It’s brief, coming in at a ...| Max Bernstein's Blog
A linear scan through the history of… linear scan register allocation.| Max Bernstein
One unassuming week of September 2022, Google DeepMind dropped a fully-fledged CPython JIT called S6 squashed to one commit. I had heard nothing of its development even though I was working on Cinder at the time and generally heard about new JIT efforts. I started poking at it.| Max Bernstein
I went to PLDI in Seoul, South Korea. I had a nice time. Here are some unstructured thoughts.| Max Bernstein
Please do not take anything you read in any of my posts (but especially not this post) as engineering advice. My parents’ house has an on-demand water heater for energy efficiency reasons. This has a small drawback: you have to press a button to prime the water heater and then wait 2-5 minutes before showering. This turns into a somewhat bigger drawback for the one room for which it’s just Not Possible to wire up a button. The water heater company hypothetically sells a plug-and-play wire...| Max Bernstein's Blog
I just saw this post and it reminded me of a time when we had a similar situation, but with string operations in our VM. The project is now defunct but the code is open. Let’s go back in time.| Max Bernstein
I have a lot of thoughts about the design of compiler intermediate representations (IRs). In this post I’m going to try and communicate some of those ideas and why I think they are important. The overarching idea is being able to make decisions with only local information. That comes in a couple of different flavors. We’ll assume that we’re compiling a method at a time, instead of a something more trace-like (tracing, tracelets, basic block versioning, etc). Control-flow graphs A functi...| Max Bernstein's Blog
Imagine you have a virtual machine for a dynamic language. It supports starting multiple threads from within the guest language via some API. This is immediately challenging right out the gate because it requires keeping some key runtime-internal state in sync: memory allocator / garbage collector compiler other bookkeeping Instead of locking these components so that only one thread can use those shared resources at a time, runtime implementors tend to shard them: each thread gets its own sli...| Max Bernstein's Blog
I wrote previously about different slices of life in the various implementations of the Scrapscript programming language. Until two weeks ago, the most interesting implementation was a so-called “baseline compiler” directly from the AST to C. Now we have an intermediate representation—an IR.| Max Bernstein
I have a lot of thoughts about the design of compiler intermediate representations (IRs). In this post I’m going to try and communicate some of those ideas and why I think they are important.| Max Bernstein
Every so often I come across a paper, blog post, or (occasionally) video that completely changes how I think about a topic in programming languages and compilers. For some of these posts, I can’t even remember how I thought about the idea before reading it—it was that impactful.| Max Bernstein
Matt Keeter put up The Prospero Challenge, which is like catnip for me. It’s a well-scoped project: we have a slow program. Make it faster within these constraints. In this post, I will describe two very small changes that can speed up his sample program with minimal effort.| Max Bernstein
Static Single Assignment is a program representation where each “variable” (though this term can be misleading) is assigned exactly once. Mostly the variables aren’t variables at all, but instead names for values—for expressions. SSA is used a lot in compilers. See this lesson from Cornell for converting Bril to SSA, which also has some good background. I’m making this page to catalog the papers I have found interesting and leave a couple of comments on them.| Max Bernstein
CF Bolz-Tereick wrote some excellent posts in which they introduce a small IR and optimizer and extend it with allocation removal. We also did a live stream together in which we did some more heap optimizations.| Max Bernstein
Scrapscript is a small, pure, functional, content-addressable, network-first programming language. fact 5 . fact = | 0 -> 1 | n -> n * fact (n - 1)| Max Bernstein
Scrapscript is a small, pure, functional, content-addressable, network-first programming language. It’s designed to allow creating small, simply shareable programs. The language was created by Taylor Troesh and the main implementation was created by me and Chris.| Max Bernstein
Picture this: you’re sitting there, writing a compiler, when all of a sudden you have to generate assembly. You have some intermediate representation (IR) but now you have to turn virtual registers into machine registers. This is called register allocation.| Max Bernstein
With a little effort, you can make your mypy-typed Python go zoom.| Max Bernstein
