WebAssembly binary format in relation to LLVM-IR

[parasyte]

According to the MVP, the WebAssembly binary format has a striking similarity to the LLVM-IR.

Quotes for comparison from the sources given above:

WebAssembly Minimum Viable Product:

• A binary format provides efficiency: it reduces download size and accelerates decoding, thus enabling even very large codebases to have quick startup times. Towards that goal, the binary format will be natively decoded by browsers.
• The binary format has an equivalent and isomorphic text format. Conversion from one format to the other is both straightforward and causes no loss of information in either direction.

LLVM Language Reference:

The LLVM code representation is designed to be used in three different forms: as an in-memory compiler IR, as an on-disk bitcode representation (suitable for fast loading by a Just-In-Time compiler), and as a human readable assembly language representation.

The LLVM bitcode accomplishes the goals of the MVP binary format. The LLVM human readable assembly language accomplishes the goals of the MVP text format.

Another point to mention is that LLVM-IR can already be compiled to native code for dozens of platforms using any (already existing) LLVM backend, including JavaScript, which accomplishes the Polyfill's goals.

That said, what are the pure advantages (if any) of a new binary and text format over an existing spec and implementation? And second, if there are any compelling advantages at all, how are the two related? Are they in direct competition?

I looked around for any prior recommendations for using LLVM-IR directly, and came up empty. So here it is: Use LLVM-IR directly! It's already built, already compiles into native code for dozens of platforms, already has several front ends including C/C++, it's free, covers many or all of the desired goals, and has a huge community of developers supporting it.

[dschuff]

I'm guessing you are unfamiliar with PNaCl. This is more or less the approach taken by PNaCl; i.e. use LLVM as the starting point for a wire format. It turns out that LLVM IR/bitcode by itself is neither portable nor stable enough to be used for this purpose, and because it is designed for compiler optimizations, it has a huge surface area, much more than is needed for this purpose. PNaCl solves these problems by defining a portable target triple (an architecture called "le32" used instead of e.g. i386 or arm), a subset of LLVM IR, and a stable frozen wire format based on LLVM's bitcode. So this approach (while not as simple as "use LLVM-IR directly") does work. However LLVM's IR and bitcode formats were designed (respectively) for use as a compiler IR and for temporary file serialization for link-time optimization. They were not designed for the goals we have, in particular a small compressed distribution format and fast decoding. We think we can do much better for wasm, with the experience we've gained from PNaCl.

[parasyte]

@dschuff I'm familiar with PNaCl, and also passively subscribed to llvmdev (http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-June/086881.html)

I agree the IR is not a perfect fit outside of its target environment. Given the parallels, it would be advantageous to leverage much of the necessary work that has already been done in the area of virtual ISAs. Considering the same toolset will be used, it ought to be an appropriate suggestion. In particular, if the IR bitcode could benefit from a small/compressed distribution representation or fast decoding characteristics, even deriving from LLVM-IR would provide a good starting point.

[titzer]

Hi Jay,

Two important goals of the binary format are that it is easily polyfillable to asm.js and that it's easily translatable to the internal compiler IRs of different compilers, in particular IonMonkey and TurboFan. LLVM-IR doesn't satisfy these goals for a number of reasons and that's why we're exploring this new direction. We don't yet have a set binary format for the WebAssembly language, but we've experimented in several promising directions with good results that give us good indication that this IR could yield real space savings and speed savings while being simple and approachable for many wasm producers.

On Wed, Jun 17, 2015 at 4:24 PM, Jay Oster notifications@github.com wrote:

According to the MVP https://github.com/WebAssembly/design/blob/master/MVP.md#binary-format, the WebAssembly binary format has a striking similarity to the LLVM-IR http://llvm.org/docs/LangRef.html#introduction.

Quotes for comparison from the sources given above:

WebAssembly Minimum Viable Product:

• A binary format https://github.com/WebAssembly/design/blob/master/BinaryEncoding.md provides efficiency: it reduces download size and accelerates decoding, thus enabling even very large codebases to have quick startup times. Towards that goal, the binary format will be natively decoded by browsers.

• The binary format has an equivalent and isomorphic text format https://github.com/WebAssembly/design/blob/master/MVP.md#text-format. Conversion from one format to the other is both straightforward and causes no loss of information in either direction.

  LLVM Language Reference:

The LLVM code representation is designed to be used in three different forms: as an in-memory compiler IR, as an on-disk bitcode representation (suitable for fast loading by a Just-In-Time compiler), and as a human readable assembly language representation.

The LLVM bitcode accomplishes the goals of the MVP binary format. The LLVM human readable assembly language accomplishes the goals of the MVP text format.

Another point to mention is that LLVM-IR can already be compiled to native code for dozens of platforms using any (already existing) LLVM backend, including JavaScript https://github.com/kripken/emscripten, which accomplishes the Polyfill https://github.com/WebAssembly/design/blob/master/Polyfill.md's goals.

That said, what are the pure advantages (if any) of a new binary and text format over an existing spec and implementation? And second, if there are any compelling advantages at all, how are the two related? Are they in direct competition?

I looked around for any prior recommendations for using LLVM-IR directly, and came up empty. So here it is: Use LLVM-IR directly! It's already built, already compiles into native code for dozens of platforms, already has several front ends including C/C++, it's free http://llvm.org/docs/DeveloperPolicy.html#license, covers many or all of the desired goals, and has a huge community of developers supporting it.

— Reply to this email directly or view it on GitHub https://github.com/WebAssembly/design/issues/188.

[pizlonator]

Even for WebKit, which uses LLVM for its top tier optimizing JIT, a LLVM IR-based assembly as input would be pretty bad. We want to be able to baseline JIT or interpret wasm at a reasonable level of performance for cold start situations while the optimizer is still spoiling up, and our experience shows that LLVM IR is prohibitively expensive to interpret or baseline compile.

I like that wasm has baseline JITability as a first class goal, and I don't think that would be achievable if we used LLVM as a starting point.

-Fil

On Jun 17, 2015, at 5:38 PM, titzer notifications@github.com wrote:

Hi Jay,

Two important goals of the binary format are that it is easily polyfillable to asm.js and that it's easily translatable to the internal compiler IRs of different compilers, in particular IonMonkey and TurboFan. LLVM-IR doesn't satisfy these goals for a number of reasons and that's why we're exploring this new direction. We don't yet have a set binary format for the WebAssembly language, but we've experimented in several promising directions with good results that give us good indication that this IR could yield real space savings and speed savings while being simple and approachable for many wasm producers.

On Wed, Jun 17, 2015 at 4:24 PM, Jay Oster notifications@github.com wrote:

According to the MVP https://github.com/WebAssembly/design/blob/master/MVP.md#binary-format, the WebAssembly binary format has a striking similarity to the LLVM-IR http://llvm.org/docs/LangRef.html#introduction.

Quotes for comparison from the sources given above:

WebAssembly Minimum Viable Product:

• A binary format https://github.com/WebAssembly/design/blob/master/BinaryEncoding.md provides efficiency: it reduces download size and accelerates decoding, thus enabling even very large codebases to have quick startup times. Towards that goal, the binary format will be natively decoded by browsers.
• The binary format has an equivalent and isomorphic text format https://github.com/WebAssembly/design/blob/master/MVP.md#text-format. Conversion from one format to the other is both straightforward and causes no loss of information in either direction.

LLVM Language Reference:

The LLVM code representation is designed to be used in three different forms: as an in-memory compiler IR, as an on-disk bitcode representation (suitable for fast loading by a Just-In-Time compiler), and as a human readable assembly language representation.

The LLVM bitcode accomplishes the goals of the MVP binary format. The LLVM human readable assembly language accomplishes the goals of the MVP text format.

Another point to mention is that LLVM-IR can already be compiled to native code for dozens of platforms using any (already existing) LLVM backend, including JavaScript https://github.com/kripken/emscripten, which accomplishes the Polyfill https://github.com/WebAssembly/design/blob/master/Polyfill.md's goals.

That said, what are the pure advantages (if any) of a new binary and text format over an existing spec and implementation? And second, if there are any compelling advantages at all, how are the two related? Are they in direct competition?

I looked around for any prior recommendations for using LLVM-IR directly, and came up empty. So here it is: Use LLVM-IR directly! It's already built, already compiles into native code for dozens of platforms, already has several front ends including C/C++, it's free http://llvm.org/docs/DeveloperPolicy.html#license, covers many or all of the desired goals, and has a huge community of developers supporting it.

― Reply to this email directly or view it on GitHub https://github.com/WebAssembly/design/issues/188.

― Reply to this email directly or view it on GitHub.

[dschuff]

I actually don't consider "easy" polyfilling to JS to be a goal of the binary format. The polyfill will be important for maybe a year; the binary format much longer. (Clearly LLVM IR can be acceptably polyfilled because emscripten does exactly that already).

But as @pizlonator said, acceptably fast compilation/interpretation is another significant problem with LLVM IR (a problem for PNaCl as well that I missed in my first list) because it's very low-level.

Most of our exploration for the binary format has been with AST-style IR; I would actually like to see a little more exploration of a CFG-style IR before finalizing something. It's possible that there's something in the CFG-style space that's higher-level (e.g. more machine operations per VM operation) and so can compile fast enough, and can also compress well and express the constructs that a variety of non-JS-style languages need.

[jfbastien]

This is a great question to answer on the FAQ.

[reduz]

Not my field, but as someone interested in bringing a large codebase (www.godotengine.org) to this platform, and based on my experiments with asm.js and PNaCL, I would say that having a bytecode that can be compiled AOT, as fast as possible, and with as little resource usage and generating as few internal structures as possible would be very desired.

JIT sounds nice in theory, but you want your high performance code to run with as little stalls and as deterministic as possible. This should be much more of a priority than having your code "start quickly". Letting videogames aside, Imagine if in the future you want to do tasks such as audio mixing, video decoding, or anything that requires as little latency as possible. JIT would mean potential stuttering and random stalls, which is highly undesired. So, please go the AOT path and completely forget JIT, or at least allow developers to choose AOT over JIT for our applications and make it part of the MVP.

TLDR; Please go AOT route, as for many applications it's much better to wait a few seconds at first than having random stalls later.

[dschuff]

We expect that the choice of JIT vs AOT will not be specified but be up to the implementation, as it is today for both asm.js and PNaCl. If I recall correctly, Firefox and Chrome compile asm.js code AOT (and PNaCl in the case of Chrome), whereas Safari does not. Not sure about Edge.

[reduz]

@dschuff That's fine and I understand it's a fair requirement for having something out of the door as soon as possible, but my point is that whatever bytecode format is chosen is as close to native as possible (in number of steps and resources required to generate it), so implementations can eventually do AOT efficiently.

[dschuff]

Correction: TurboFan (the engine V8 uses for asm.js) has no baseline JIT or interpreter, but it doesn't compile the whole module AOT, just function-by-function on-demand. So in that sense it's really a JIT.

[reduz]

@dschuff ok, I can understand if it's too much of a task to adapt existing JIT engines right now to AOT for it to be included in MVP, but my point stands in the sense that you might have to switch to this approach in the future. I think the Firefox guys already made their point about how well AOT works, and I'm sure that heavy users of wasm (ie, Unity or Unreal) will eventually demand this (compile times as fast as possible, and eventually AOT) in order for their software to work smoothly from the start.

[pizlonator]

On Jun 18, 2015, at 9:34 AM, Juan Linietsky notifications@github.com wrote:

@dschuff That's fine and I understand it's a fair requirement for having something out of the door as soon as possible, but my point is that whatever bytecode format is chosen is as close to native as possible (in number of steps and resources required to generate it), so implementations can eventually do AOT efficiently.

Let's separate out two parts that you are conflating: whether the format is sufficiently close to the metal that you can efficiently compile it to efficient code, and whether an implementation does what Firefox calls AOT or JIT.

Wasm is very close to the metal and is deliberately designed to enable rapid conversion to a low level compiler IR. In this regard it is better than other representations including LLVM IR. LLVM IR is only a good low level representation of you have a specific CPU in mind and the implementation used LLVM as the compiler. Wasm is more portable and easily supports multiple CPUs. It's also very easy to convert back into LLVM IR if your compiler is LLVM based. So, on that point, you're preaching to the choir. We've already engineered it to fit your requirements.

An entirely separate question is the scheduling and caching policy that the implementation uses for compiling wasm. This is independent of the format; even if we chose LLVM IR or any other extant format, the implementations could still choose from a bunch of different strategies. This is largely out of scope of the wasm discussion and I don't think that the spec should mandate anything in particular.

As an aside, the bet that WebKit is making is that a low power JIT for fast start up, paired with a heavy optimizing JIT once a function eats up more than a handful of microseconds of CPU time, is exactly what you need if you care about applications loading quickly and running efficiently. It will be fun to see how this compares to the approaches that the other engines take.

-Filip

― Reply to this email directly or view it on GitHub.

[johnku1]

194 codifies the ideas mentioned here.

[titzer]

Hi Juan,

On Thu, Jun 18, 2015 at 9:25 AM, Juan Linietsky notifications@github.com wrote:

Not my field, but as someone interested in bringing a large codebase ( www.godotengine.org) to this platform, and based on my experiments with asm.js and PNaCL, I would say that having a bytecode that can be compiled AOT, as fast as possible, and with as little resource usage and generating as few internal structures as possible would be very desired.

Yes, we've thought about this very hard and done a lot of work to validate the approach going forward. Compile speed has been a high priority. In the v8-native-prototype directory there is a patch that decodes an example binary format (not a final one) to TurboFan internal IR in a single pass, performing verification and SSA renaming as it goes. I measured decode speed (validation only) at 60mb/s on a single thread; so even large modules should be pretty fast to AOT.

JIT sounds nice in theory, but you want your high performance code to run with as little stalls and as deterministic as possible. This should be much more of a priority than having your code "start quickly". Letting videogames aside, Imagine if in the future you want to do tasks such as audio mixing, video decoding, or anything that requires as little latency as possible. JIT would mean potential stuttering and random stalls, which is highly undesired. So, please go the AOT path and completely forget JIT, or at least allow developers to choose AOT for our applications.

— Reply to this email directly or view it on GitHub https://github.com/WebAssembly/design/issues/188#issuecomment-113208626.

[titzer]

On Thu, Jun 18, 2015 at 9:34 AM, Derek Schuff notifications@github.com wrote:

Correction: TurboFan (the engine V8 uses for asm.js) has no baseline JIT or interpreter, but it doesn't compile the whole module AOT, just function-by-function on-demand. So in that sense it's really a JIT.

Almost. For Chrome 41 and 42, TurboFan would compile each asm.js function the first time it was executed. Since 43, asm.js code warms up like normal JS in the unoptimized compiler and then gets optimized with TurboFan when it becomes hot.

As for WebAssembly, we're still prototyping and want to leave some room for dynamic optimization in the future, but the quick and dirty plan is to make the v8-native prototype AOT compile the entire module (or load from cache).

—

Reply to this email directly or view it on GitHub https://github.com/WebAssembly/design/issues/188#issuecomment-113211791.

[lukewagner]

With #194 merged, seems like we can close this out.

[reduz]

After talking to some other developers, and before it's too late on this matter.

I realize for some implementations, JIT makes more sense because you get much higher intial response time, but for others AOT makes much more sense (games and audio). I honestly am not so sure it's possible to use an hybrid methodology (aot first, optimize later) that works flawlessly as described above. I have never seen this implemented before and used in real-time scenarios, despite the claims. I know sounds like it will work but I have my doubts.

So, would it be possible to add in the webassembly specification a hint about preferred compilation method, AOT or JIT? Implementations are free to ignore it, but at least developers can make sure to tell how they prefer their software to work.

EDIT: Will file a separate issue about this, so i don' t flood this unrelated one.

[MikeHolman]

Yes, actually we have toyed with the idea of adding such hints at a per-function level. For example, you can imagine using PGO you might determine hot functions that should be AOT compiled. I suppose under such a scheme you could hint to AOT compile everything.

[jfbastien]

We've also discussed hints for hot / cold code. We could even avoid compiling or downloading cold code!