Lineiform, a meta-JIT library for Rust interpreters | Hacker News Reader

Lineiform, a meta-JIT library for Rust interpreters

redvice.org

13 pointsnemo16188 comments

Very interesting.

The last paragraph is unfortunate though:

> And if it works, and if it’s fast, and if it’s useful? Who knows. I’d like if Apple or Facebook paid me a lot of money for this library in order to make things fast (think being able to JIT compile build scripts or DSLs), so I’m not sure if I’ll opensource or source-available it or not; if you want access to the repo to play around, or even just to ask how things are going or talk about various compiler things, feel free to reach out.

> Lineiform is just a wrapper function that takes a closure as input, and returns a closure as output. In the middle however, it will dynamically inline calls to other closures that the input might be doing, using dynamic recompilation to lift, optimize, and then lower x86 instructions to a set of x86 instructions with the same operational semantics, but hopefully doing less work such as inlining small closure snippets so there isn’t call/ret and ABI overhead, or folding constants like 3+5.

Isn't a magic step missing here? In order to "lift, optimize, and then lower x86 instructions" you need x86 instructions to start with. How does the leap from having a Rust closure object to a snippet of baseline machine code work?

(I'm the author) Rust closures store a function pointer for the closure body. I'm using yaxpeax, which is a fast x86 disassembler made by one of my friends, in order to turn the function pointer into an x86 instruction stream. There's some junk that we have to do with parsing /proc/self/exe in order to get the symbol it points to so we know how big the function is, as well.

It's kinda complex, because Rust closure internals aren't documented all that well, but it works fine and isn't UB (as far as I know). The bigger issue is actually that Rust closures use the Rust ABI, which is not stable, and so Lineiform shouldn't really assume which arguments are in which registers since it could (technically) change at any point: we end up having the disassembly entry point be a C ABI trampoline that calls the rust-call ABI so that rustc emits the cross-ABI register shuffling for us as a prelude, and emit a C ABI function to call as an output.

The relevant code is https://github.com/chc4/lineiform/blob/4a104c994561282318179.... It is very messy, sorry.

I see, thanks for the explanation. That's a neat trick!

Really interesting idea. What is used for the optimization pass? Most optimizers work on an IR AFAIK. Is there one that operates on x86 directly?

(I'm the author) As part of lifting you convert the x86 instructions into an IR so you can do optimization passes. This is how I was using Cranelift as a codegen backend; there is essentially an abstract interpreter over x86 that feeds into their function builder API. Cranelift then has optimizations for constant folding and things, along with redoing register allocation from the virtual registers that their IR uses internally before lowering to x86 again.

This is how qemu and DynamoRIO and things work too, where they have an IR which allows them to more abstract transform the code than having to keep it normalize to x86 or some other assembly the entire time.

As part of switching to my own IR I'm going to have to write my own optimization passes for it as well instead of being able to piggyback off Cranelift.

Why was cranelift not a good fit as an optimizer?

I go into a bit in https://github.com/chc4/lineiform/issues/19, but it's less a problem with its optimizer and more a problem with its IR constraints. Cranelift specifically has some rules about `iflags`, the type they use to conceptualize processor flags effects (e.g. add's carryout or overflow). You can only have one `iflags` value live at a time, and it can't overlap with any other math operation. This is a problem because the x86 we're lifting doesn't always follow that rule, so if we just emit Cranelift as we go it will panic and say we built an invalid function.

The iflags design in general is kinda awkward too, and was being rethought a few months ago when I was first getting this working; I think they're planning on redesigning the add carryout interface and things to be slightly more streamlined. I suspect that any redesigned interface will have similar problems with mismatch between what I want from Cranelift and what 90% of other uses of Cranelfit want, though, and so I decided to just make my own IR instead.

Reply on news.ycombinator.com