cfallin

Oh goodness, that name is so good!

(And thanks!)

Thanks! I haven't studied Graal's IR in detail, no. I'll add it to my reading list...

OK, cool. I was assuming "escape analysis and type inference" implied a JS JIT -- straight from your comment, no other assumptions intended. But you've got a lot of interesting experience here and thanks for your thoughts.

All the best!

Hi Fil -- thanks for the comment!

I think we may be playing in slightly different spaces: unlike a JS JIT, Cranelift doesn't have "super fancy escape/type analysis". We're really targeting the core optimizations (GVN, LICM, cprop, RLE, STLF, various algebraic rules) in a fast compile pass. The RLE+GVN interaction was pretty real in our case, as are interactions between the algebraic rewrites and GVN.

You'll note that my main point is that the single fixpoint loop for all of the core rewrites is what we wanted, and what the sea-of-nodes-with-CFG gets us; the egraph (multiple versions of one value) is kind of an aside. One could say: well sure but I could just do a single pass with that fixpoint loop without all the egraph stuff; and, yes, that's what our single rewrite pass is.

We have two: fuel and epochs. Fuel (analogous to "gas" as it appears in many VM platforms) is a deterministic count and epochs check an always-increasing counter in shared memory meant to be periodically bumped by another thread. In either case, hitting the limit can be configured to either async-yield back to the event loop (in async mode) or to trap/terminate the Wasm instance. Both are based on instrumentation, i.e., extra code inserted during Wasm-to-machine-code compilation to do these checks at the start of loops and at the top of each function. Epoch instrumentation is cheaper because it's checking a mostly-read-only value in memory (so usually cached) while fuel loads and stores that value constantly from the VMContext.

(Core Wasmtime maintainer here, and I built our epochs mechanism when I realized we could do better than fuel if one doesn't need the determinism, only periodic yields)

No, it's still behind a flag (and so transitively, exceptions are too, because we built exception objects on top of GC).

Our docs (https://docs.wasmtime.dev/stability-tiers.html) put GC at tier 2 with reason "production quality" and I believe the remaining concerns there are that we want to do a semi-space copying implementation rather than current DRC eventually. Nick could say more. But we're spec-compliant as-is and the question was whether we've implemented these features -- which we have :-)

It'll be interesting to see what the second non-browser-based WASM runtime to fully support 3.0 will be (I'm guessing wasmtime will be first; ...)

Wasmtime already supports every major feature in the Wasm 3.0 release, I believe. Of the big ones: garbage collection was implemented by my colleague Nick Fitzgerald a few years ago; tail calls by Jamey Sharp and Trevor Elliott last year (with full generality, any signature to any signature, no trampolines required!); and I built our exceptions support which merged last month and is about to go out in Wasmtime 37 in 3 days.

The "3.0" release of the Wasm spec is meant to show progress and provide a shorthand for a level of features, I think, but the individual proposals have been in progress for a long time so all the engine maintainers have known about them, given their feedback, and built their implementations for the most part already.

(Obligatory: I'm a core maintainer of Wasmtime and its compiler Cranelift)

They're hitting another design point on the compile time vs. code-quality tradeoff curve, which is interesting. They compile 4.27x faster than Cranelift with default (higher quality) regalloc, but Cranelift produces code that runs 1.64x faster (section 6.2.2).

This isn't too surprising to me, as the person who wrote Cranelift's current regalloc (hi!) -- regalloc is super important to run-time perf, so for Wasmtime's use-case at least, we've judged that it's worth the compile time.

TPDE is pretty cool and it's great to see more exploration in compiler architectures!

Indeed; the tl;dr is "yes it works on SpiderMonkey, and was designed to do so". Blog post in a few months, I promise!

That is, if x and y are determined only at runtime for power(x, y) then I don't see what can be optimized.

Yes, the example in Max's post is specifically assuming one wants to generate a specialized version of `power` where `y` is fixed.

To take it back to weval: we can know what the bytecode input to the interpreter is; we provide an intrinsic (part of the "wevaling" request) to indicate that some function argument is a pointer to memory with constant, guaranteed-not-to-change content. That, together with context specialization on PC (another intrinsic), allows us to unroll the interpreter loop and branch-fold it so we get the equivalent of a template method compiler that reconstitutes the CFG embedded in the bytecode.

This is indeed a good point and something I want to write about when I eventually do a blog post on weval.

A few counterpoints that I'd offer (and what led me to still take this approach):

- If the target has sub-par debugging infrastructure, it can be easier to debug an interpreter (which is portable) then apply the semantics-preserving PE. In particular when targeting Wasm outside the browser, there is... not really a good debug experience, anywhere, for that. It was way easier to get an interpreter right by developing on native with gdb/rr/whatever, and then separately ensure weval preserves semantics (which I tested with lockstep differential execution).

- Maintenance: if one is going to have an interpreter and a compiler anyway (and one often wants this or needs this e.g. to handle eval()), easier for them both to come from the same source.

- Amortized cost: in the Wasm world we want AOT compilers for many languages eventually; there are interpreter ports with no Wasm backends; developing weval was a one-time cost and we can eventually apply it multiple times.

- If the semantics of the existing interpreter are quite nontrivial, that can push the balance the other way. I designed weval as part of my work on SpiderMonkey; extremely nontrivial interpreter with all sorts of edge cases; replicating that in a from-scratch compiler seemed a far harder path. (It's since been done by someone else and you can find the "wasm32 codegen" patchset in Bugzilla but there are other phasing issues with it from our use-case's PoV; it's not true AOT, it requires codegen at runtime.)

I don't think the tradeoff is always clear and if one is building a language from scratch, and targeting a simple ISA, by all means write a direct compiler! But other interesting use-cases do exist.

weval author here (thanks Max for the blog post!). Also AMA!

The talk about weval that Max mentions was at NEU and also CMU; the latter was recorded and is here: https://vimeo.com/940568191

I also plan to write up a blog post on weval in depth, plus its application to SpiderMonkey-on-Wasm, in a few months; it's pretty exciting though, currently getting 4-5x speedups on some benchmarks on a decidedly nontrivial interpreter!

The approach that Cranelift uses is what we call the "aegraph" (talk I gave about it: slides https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf, video https://vimeo.com/843540328). The basic idea is that eclasses hold sets of operator expressions (think sea-of-node IR), and we keep that alongside the CFG with a "skeleton" of side-effecting ops. We build that, do rewrites, then extract out of it back to a conventional CFG-of-basic-blocks for lowering. The "equivalence" part comes in when doing rewrites: the main difference between an egraph and a conventional sea-of-nodes IR with rewrite rules is that one keeps all representations in the equivalence class around, then chooses the best one later.

We had to solve a few novel problems in working out how to handle control flow, and we're still polishing off some rough edges (search recent issues in the repo for egraphs); but we're mostly happy how it turned out!

(Disclosure: tech lead of CL for a while; the e-graphs optimizer is "my fault")

We actually take a fairly unconventional approach to e-graphs: we have a few linear passes and we do all rewrites eagerly, so we use them to provide a general framework for the fixpoint problem into which we plug in all our rewrites, but we don't have the usual "apply as much CPU time as you want to get better results" property of conventional equality saturation.

I gave a talk about this approach, aegraphs (acyclic e-graphs), here: slides (https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf), video (https://vimeo.com/843540328)

(disclosure: Cranelift tech lead 2020-2022 and main author of the e-graphs mid-end, as well as regalloc, isel and its custom DSL, and other bits, along with the excellent team)

Right, it's about algorithmic tradeoffs throughout. A good example I wrote about is here: https://cfallin.org/blog/2021/01/22/cranelift-isel-2/ where we use a single-pass algorithm to solve a problem that LLVM has a multi-part fixpoint loop to solve.

Most CPU time during compile is in the register allocator and I took a really careful approach to optimization when I rewrote it a few years ago (more details https://cfallin.org/blog/2022/06/09/cranelift-regalloc2/). We generally try to pay close attention to algorithmic efficiency and avoid altogether the fixpoint loops, etc that one often finds elsewhere. (RA2 does backtrack and have a worklist loop, though it's pretty minimal, and also we're planning to add a single-pass mode.)

(disclosure: I was Cranelift tech lead in 2020-2022)

There are some benchmarks of Cranelift-based Wasm VMs (Wasmtime) vs. LLVM-based Wasm VMs here: https://00f.net/2023/01/04/webassembly-benchmark-2023/

The (perhaps slightly exaggerated but encouraging to me at least!) money quote there is:

That’s right. The cranelift code generator has become as fast as LLVM. This is extremely impressive considering the fact that cranelift is a relatively young project, written from scratch by a very small (but obviously very talented) team.

In practice anywhere from 10%-30% slower maybe is reasonable to expect. Compiler microbenchmarks are interesting because they're very "quantized": for any particular benchmark, often either you get the right transforms and achieve the correct optimized inner loop, or you don't. So the game is about getting more and more cases right and we're slowly getting there.

(disclosure: I was tech lead of Cranelift in 2020-2022)

A small correction re: Cranelift -- I had originally prototyped with egg, but we're currently using a variant of egraphs I invented called "acyclic egraphs" after working through performance and productionization issues, with our own implementation. Egg is great for what it is; a production compiler is just a really particular and demanding environment. I'll be giving a talk about it at EGRAPHS 2023 (in the meantime there are details in the RFC you linked). E-graphs are cool! :-)

The perf blogpost actually uses SpiderMonkey-compiled-to-Wasm as a benchmark rather than a comparison (peer) of Wasmtime. However, there are some good comparisons done by a third party in this paper:

https://arxiv.org/pdf/2011.13127.pdf

See Figs. 20-22 on page 19. They found Wasmtime to be quite competitive to V8 and others.

(disclosure: I work on Wasmtime + Cranelift)

That's a good question for bjorn3, the leader of that effort; they periodically publish status updates. Over on the Reddit discussion someone pointed to this GitHub issue too: https://github.com/rust-lang/rust/pull/81746#issuecomment-10...

That's the goal at least! We explicitly do not have a notion of "undef" or "poison" values in our IR, and to the largest degree possible we want determinism (modulo e.g. some NaN-related stuff right now). Our current discussion with some researchers wanting to formally verify our lowerings will likely push us toward the start of some formal spec for the IR as well, though exactly how that will work or be maintained is not yet decided.

I'm not super-familiar with the pointer provenance work in Rust but I'll read more about this; thanks for the mention!

One can do optimal regalloc over SSA if one doesn't have to spill, or split to make the spilling better, but spilling and splitting are the most interesting and relevant part of practical register allocation -- so in practice this isn't quite true.

Cranelift is a general-purpose compiler like LLVM is, but its goals are different: it is targeted toward applications like JITs where faster compilation is important. It is intended to be a peer of browser JITs' optimizing tiers. In our README [0] we link some results where we're ~14% slower than LLVM but with ~10x faster compilation.

We also have an explicit focus on correctness, simplicity, and verification. One could argue that in practice LLVM is used everywhere and has dozens of active core contributors, that bugs and missed optimizations are shallow at that scale, and it's hard to compete with that; and there is some merit in that... but our codebase is two orders of magnitude smaller, and we're actively engaging with academics and designing things -- our lowering DSL, our regalloc's symbolic verifier, our fuzzing-first approach -- to get the most mileage we can out of our efforts. It seems to be working OK so far!

[0] https://github.com/bytecodealliance/wasmtime/blob/main/crane...

Ah, yes, that is indeed experimental, though it seems to be coming along nicely (I'm not involved but talk with the main author to support it).

That said, cranelift is still experimental.

Echoing everyone else in this thread that Cranelift might work well for this case; just wanted to add: Cranelift is definitely not "experimental" anymore, though it is still young. It's in production in a number of places (my employer and others) and we test thoroughly, including differential fuzzing against other engines/compilers. It just got a new register allocator, and we even have some academics working on formal verification!

We'd be happy to help with any issues that arise; our Zulip instance (bytecodealliance.zulipchat.com) is probably the best place to find us.

(Disclosure: I work full-time on Cranelift, and have a ton of fun doing it)

You're not alone -- I recently had a heck of a time trying to get a T14s AMD 2nd gen to work well in Linux (mostly same CPU/chipset/hardware as your X13).

I never got wakeup from S3 suspend to work, it just froze; wakeup from S0ix actually worked ok for a while with a recent kernel (5.16 iirc), with a random kernel commandline addition (iommu=pt) to avoid a random 14-second pause on lid open (always exactly 14 seconds!). But wireless was still flaky on wakeup.

I played a bunch with powertop and different settings to try to get reasonable efficiency. Tried getting hardware video decode to work with YouTube/Firefox (vdpau / va-api); it sort of did, except when it crashed.

Then one day a week into the adventure, it just stopped waking up from suspend, after I-don't-know-what changed. Needed a hardware reset each time I opened the lid. I returned the laptop and bought an M1 Air instead; I love my Thinkpads and open systems but I also love good engineering.

System integration / QA / getting quality polished firmware is an underappreciated art it seems!

The way this clicked for me (it took some thought!) was to see it as a lever, or at least an analogue to one.

Imagine a lever with the fulcrum on one end, attached to the ground. Wind pushes on the middle, and the car is at the other end of the lever. So wind exerts more force with less speed, and the car moves forward with more speed but less force.

That's basically what the linkage and gear ratio between the wheels and propeller do; it's the counterintuitive power flow that makes it so confusing...

The explanation in the book is that neutron-star life is based on nuclear chemistry, whose reactions move much more quickly than our (electron-shell-based) chemistry, so everything happens much more quickly as a result.

For anyone looking for a documentary on the Manhattan Project, I'd highly highly recommend The Day After Trinity, a documentary by Jon Else with a bunch of interviews of the original participants (it was made in 1980). Really fantastic look at the personalities behind all the science.

Indeed; footnote 3 on the sentence you quoted links to exactly that paper :-) This came up in the Reddit discussion on the post a few days ago. Specifically it works for reducible control flow. In the general case (irreducible control flow) I think it is still NP-hard, but I could be mistaken. (Regardless, the algorithms are nontrivial, hence the need for fuzzing!)

I had sort of the same problem when jumping into Cranelift work -- this stuff is really not well-documented outside of the code itself. Happy to hear you found the posts useful!