We found these ideas very useful for doing micropatches, post hoc intrafunction binary patches, using off the shelf compilers. At the least, a voice of support that these kinds of calling convention control is useful.
This is interesting. I came up with a very similar idea in the late 1990s to JIT a lazy functional language. The idea was to only compile the code that you needed to execute next, so you could run lazy code without needing to compile it (recursing across infinite lists, etc). It had templates with holes (for things like cons etc.)
I stuck my paper on it under Prof Phil Wadler's office door and ran away. I have no idea if he ever read it :D
It’s kind of annoying how static compilers insist on figuring out everything from scratch. Even in an LTO build, the amount of code that changes between two consecutive commits is typically minimal - rather than the very coarse ccache-style, it would be nice if compilers had nicer ways to cache state across execution so that unchanged code constructs could just emit the same assembly as last time without needing to do anything else.
The very first objection that immediately have sprung up to my mind it that this approach gives up on (chances of) inlining a lot of stuff (or de-inlining, for that matter). The second thought is that it also heavily interferes with any code motion transformations, including instruction scheduling, loop unrolling and auto-vectorization. Granted, this second objection can probably be dealt with by using some clever fine-guided techniques... but at this point I'd wager they'd be both a) about as slow as doing all the work it from the clean slate; b) have incredibly large surface for obscure bugs — and those steps are already one of the most finicky ones.
And back in the 70s, when the microcomputers and interactive computing were becoming the norm, and people really cared about the compilation times — still nobody bothered to implement that kind caching, AFAIK, even when the compiler performed way less complex kinds optimizations than they do today (heck, even register allocation was not done as graph colouring back then).
> The very first objection that immediately have sprung up to my mind it that this approach gives up on (chances of) inlining a lot of stuff (or de-inlining, for that matter). The second thought is that it also heavily interferes with any code motion transformations, including instruction scheduling, loop unrolling and auto-vectorization.
I feel like a lot of these sorts of optimization are best done at the language level, before it gets to the instruction level, eg. fusion, supercompilation, partial evaluation are all more general than and far more effective optimizations than these low-level rewrites. If you've already done those optimizations, then you just want to spit out code as fast as possible.
The low-level transformation that matters the most is probably register allocation. Good register allocation is responsible for a lot of OCaml's speed. I'm not clear whether that would be significantly impacted with copy and patch.
No matter how you slice it almost time spent in a compiler is wasted by recreating optimizations for things that haven't changed. Back in the 70s disk IO was slow and memory was scarce. Compilers couldn't cache much for that reason. Compilers today are designed for constraints that no longer exist.
> Back in the 70s disk IO was slow and memory was scarce. Compilers couldn't cache much for that reason.
That's... not exactly true? Yes, memory was scarce but that's precisely why the compilers in the 70s used disk I/O for temporary storage way more extensively than the modern ones do. Let's take Unix V6, for example: the C compiler used two temporary disk files to keep data between its three passes, the assembler used three temporary files to keep data between its two passes, and I can't quite wrap my head around how many temporaries its linker used but it's at least 4. Nobody bothered to try to keep and reuse those temporaries, however.
Compilers today, instead, keep almost everything in memory and don't generally bother with temporary files at all because why would they? The growth of the computing speed has outpaced the memory/disk speeds anyhow.
If you’re going for very fast codegen, sure. But in a production build typically you have problems like “this shifted by one instruction so every non-relative branch beyond it needs to be patched”.
Rust's incremental compilation does this. Unfortunately, it doesn't help with linking, but it speeds up compilation by reusing everything that didn't change.
I could be wrong but I think Rust’s incremental compilation is still pretty coarse. LLVM is where this would need to be implemented and that’s a tall ask (i.e. skipping expensive computation when the AST is the same or close enough to a previously computed result). And Rust’s incremental compilation doesn’t apply to LTO. There’s only so much you can do from outside the compiler toolchain.
I would still call this a traditional template jit. The new things have nothing to do with copy&paste, but with using continuations and TCE (tail-call elimination), which I haven't seen in a simple template jit (or sometimes called method jit) before. Plus the register variants, to avoid moving them too much, but this is also very pedestrian, low tech. Low tech is good!
Do you have any links to the traditional ones for those interested (i.e. me)?
I only found out about the approach due to the author's articles a few months ago.
I wonder if the comparisons with Cranelift would still show the same build-time/run-time gap four years later.
From what I understand, Cranelift's current instruction selector is very close to copy-and-patch conceptually (it maps patterns of bytecode instructions to sequences of machine instructions), and the pass Cranelift spends the most time in, register allocation, still has to happen in copy-and-patch.
So if copy-and-patch still has a meaningful advantage over Cranelift, I'm very curious to know where it comes from.
The same as with any other JIT runtime: you do your transformations first, and then you do the `mprotect` call that turns write permissions off and execution permissions on. The only caveats I can think of (`pledge`d not to use `mprotect`, marked most of the address space with `mimmutable`) apply to all other JITs too. The gist is that you operate on a copy of code, and that copy is in a writable page until it's ready to run, so you never violate the W^X rule.
Does that even work in W^X platforms? Context for my response has that assumption, we can't simply throw it out the window, right?
I think I read somewhere about making two mappings to the same physical page (one W, one X), are you referring to that?
(I'd still need to know how that works as it kinda defeats the protection, the OS should prohibit that, right?)
The question was about OSes with hardened runtime protections. The most basic of them all is W^X. All BSDs use it, and IIRC Linux is able to enforce it as well. I'd be surprised if it isn't the default in most distros, but I guess it's not impossible. I need to go for lunch so I won't check right now.
Aren't you just better off using GNU Lightning? It's basically a set of binary stencils defined by C macros, except because they're macros, your interpreter/compiler will only embed the stencils you actually use.
I mailed the authors a few months ago and indeed, it lives there but is independent-ish. They don't consider it ready to use for anything else other than experiments, though.
Sure but from looking at the patches, it seems like theirs is tied into the CPython build and infrastructure. I am talking about a dedicated library which can be dropped into a variety of superprojects to help them implement a JIT.
I don't think this counts as threading, though it makes use of it. Threading mostly removes the dispatch overhead, but you still have a general function per instruction, a function call, and an inability to inline constants. Copy and patch could be thought of as a generalization of threading in the sense that you still precompile code for your instructions, but instead of calling that code you poke holes in it to replace constants you only know at runtime, then make a single callable program out of those instead of jumping around for every instruction.
There is a prior, very similar approach in GNU Jitter, but it uses only the compiler and some magic rather than the linker for marking spots to replace. I read about it by mention of moonchild in a thread[0] linked by foota here.
Threading doesn't necessarily mean following the full function-call convention on every transition. A switch/case approach is one way, but it's also possible to jump intra-function without following the calling convention, i.e. a goto with a pointer-based target.
I say possible in the sense that hardware supports it. The standard C language doesn't support this, but GCC's GNU C does support it as one of its extensions.
That is not the point though. I know threading allows using a custom convention and just jumping. What it doesn't, IIUC, is allow specializing your code for runtime data. Copy-and-patch and Jitter do. It's essentially static vs dynamic.
I'm new to this so I may very well be misunderstanding threading, but I don't think it allows for modifying the functions on runtime by itself.
There's bit of a mushy terminology problem here. Generally when we say threading we mean schemes that don't rely on generation of new native-code sequences, sure, but people who are serious about efficient threading don't necessarily view it that way.
The term context threading refers to generation of native code that behaves much like conventional threaded-code interpretation, except specialised to the particular input code. [0][1]
See also dynamic superinstructions, a term used by gforth to refer to its runtime generation of native code for input Forth code. [2]
Disclaimer: I'm no Forth expert. I should give [1] a proper read, it looks interesting.
I see. I'll try to read the links over the weekend, they seem really interesting.
It's sad that the terms are so overloaded though, as it makes it hard to reach preexisting approaches and leads to rediscoveries of the same idea (I see that both Jitter and C&P seem to implement this very same idea, except maybe in the way the templates are created, and both seem to believe their invention is novel).
Regarding threaded-code strategies I think the terminology is reasonable. There's a real sense in which context threading is just another kind of threaded code, although it does make it awkward to describe conventional direct or indirect threading.
The creator of Jitter has read a lot about Gforth, as evidenced in [0][1].
You're not the only one to suspect there's some reinvention going on here somewhere though. [2] I'm not familiar enough with these topics (copy-and-patch and Jitter) to weigh in.
They are both super close in the latent space. I think you could design for threading, but then copy into place and NOP out what you don't need, or wire in the right constants, etc.
- Copy and Micropatch: Writing Binary Patches in C with Clang preserve_none https://www.philipzucker.com/permutation_compile/
- https://github.com/purseclab/Patcherex2/pull/31 A pull request to the PatcherEx2 library