4 ms·

This is fascinating. For various reasons, WASM is less like a target bytecode format and more like a peculiar IR for compilers. I’m sure this has all sorts of e

This is fascinating. For various reasons, WASM is less like a target bytecode format and more like a peculiar IR for compilers. I’m sure this has all sorts of effects on the tooling.

k__ 7y ago
What's the difference?
- saagarjha 7y ago
  Most bytecode isn’t optimized much.
- klodolph 7y ago
  If you were designing a bytecode as a compilation target, you would provide an easy correspondence in the bytecode to basic blocks. See: https://en.wikipedia.org/wiki/Basic_block https://en.wikipedia.org/wiki/Basic_block WASM instead provides traditional control structures. So the compiler either has to preserve control structures through to the IR, or has to work backwards from basic blocks to control structures. Both options are undesirable, from the perspective of compiler writers, and would be unnecessary if the VM were a greenfield project.
  - MaxBarraclough 7y ago
    I get the impression WASM is really a very clunky representation, far from what any greenfield project would ever have arrived at. That is to say, its decisions aren't just tradeoffs that people disagree about, they're simply inappropriate for what it's trying to do. More than once I've encountered comments and blog-posts lamenting its fundamentals, e.g. [0]. [0] http://troubles.md/wasm-is-not-a-stack-machine/ http://troubles.md/wasm-is-not-a-stack-machine/
    - tedmielczarek 7y ago
      I don't think that's true. It was designed for its purpose by people that knew what they were doing based on experience gathered from implementing previous incremental steps including emscripten's original JavaScript output and asm.js (a formalization of some techniques emscripten employed). The design rationale is right there in the spec repository: https://github.com/WebAssembly/design/blob/master/Rationale.md https://github.com/WebAssembly/design/blob/master/Rationale.... It was built to be a better target than asm.js for compiled languages to run in JavaScript VMs and it seems to have succeeded on that front. That it's not a perfect fully-general bytecode format doesn't seem like a real knock against it, that's a much harder problem to solve. In any event it seems to be getting a lot more traction than any previous entries in the space, which is exciting!
    - klodolph 7y ago
      The criticisms in the linked article are simply not grounded in fact, and the article was obviously written by someone without any expertise in how modern compilers work. There are also a number of basic errors in the article. Liveness information simply doesn’t belong in the bytecode. SSA is trivial to recreate from local mutable variables (it would make a good homework assignment for someone in an undergrad “intro to compilers” class). WebAssembly is obviously a register machine. > With this, it becomes possible to get rid of locals entirely. Both factually incorrect and pointless. There is no tangible benefit in getting rid of locals entirely. You are merely changing out one representation (register machine) for a different one (stack machine). There are valid criticisms of WASM, but the linked article doesn’t have any. The weird part of WASM is the control structures. The rest of it is a fairly sensible, actually rather nice register machine. You can see that older bytecode systems like the JVM are stack machines, but newer ones tend to be register machines. This isn’t because people are getting stupid, it’s because there are legitimate reasons to prefer register machines, and on the balance of things, my observations are that people with experience in the field tend to prefer register machines.
      - MaxBarraclough 7y ago
        Interesting, thanks for the analysis. > You can see that older bytecode systems like the JVM are stack machines, but newer ones tend to be register machines. Like LLVM. Is there a good reason for WebAssembly not being SSA?
        klodolph 7y ago
        There’s no good reason for WebAssembly to be SSA. That is a good enough reason for it not to be. The purpose of SSA is to make it easier to write optimizations. However, you wouldn’t be optimizing WASM anyway, you would necessarily translate it first into some kind of IR suitable for optimization passes. Might as well convert to SSA at that point, rather than bloat the bytecode by exposing implementation details of the target. Remember that WASM’s purpose is to be portable and safe. Making it more complicated just in order to make sophisticated back-ends slightly faster is a net loss. Using SSA would also make naïve/simple backends slower.
      - 7y ago
  - tedmielczarek 7y ago
    The latter is very achievable using the Relooper algorithm developed by Alon Zakai and described in the Emscripten paper: https://dl.acm.org/doi/10.1145/2048147.2048224 https://dl.acm.org/doi/10.1145/2048147.2048224
    - klodolph 7y ago
      Achievable, but extra front-end work that belongs in the backend.
  - kazinator 7y ago
    Nested, structured control can be broken into basic blocks without flattening it into if/goto first. It sounds easier, in fact. In fact, the construction of a basic block from flat code is a form of recovery of control structure. If the original code had nested loops, nesting will emerge in the basic block graph. A recursive traversal of the original structure could produce that graph more directly; it doesn't have to walk a flat list of instructions asking, "does this have a label on it which is the target of a branch". without having to walk a flat list of instructions asking questions like "is this the target of a branch". For instance, if we walk an if/then/else AST node, we can recursively get the basic block graph for the test, the then and else part, and then integrate that into a larger basic block graph according to a rigid pattern.

This is fascinating. For various reasons, WASM is less like a target bytecode format and more like a peculiar IR for compilers. I’m sure this has all sorts of effects on the tooling.

k__ 7y ago

What's the difference?

saagarjha 7y ago
Most bytecode isn’t optimized much.
klodolph 7y ago
If you were designing a bytecode as a compilation target, you would provide an easy correspondence in the bytecode to basic blocks. See: https://en.wikipedia.org/wiki/Basic_block https://en.wikipedia.org/wiki/Basic_block WASM instead provides traditional control structures. So the compiler either has to preserve control structures through to the IR, or has to work backwards from basic blocks to control structures. Both options are undesirable, from the perspective of compiler writers, and would be unnecessary if the VM were a greenfield project.
- MaxBarraclough 7y ago
  I get the impression WASM is really a very clunky representation, far from what any greenfield project would ever have arrived at. That is to say, its decisions aren't just tradeoffs that people disagree about, they're simply inappropriate for what it's trying to do. More than once I've encountered comments and blog-posts lamenting its fundamentals, e.g. [0]. [0] http://troubles.md/wasm-is-not-a-stack-machine/ http://troubles.md/wasm-is-not-a-stack-machine/
  - tedmielczarek 7y ago
    I don't think that's true. It was designed for its purpose by people that knew what they were doing based on experience gathered from implementing previous incremental steps including emscripten's original JavaScript output and asm.js (a formalization of some techniques emscripten employed). The design rationale is right there in the spec repository: https://github.com/WebAssembly/design/blob/master/Rationale.md https://github.com/WebAssembly/design/blob/master/Rationale.... It was built to be a better target than asm.js for compiled languages to run in JavaScript VMs and it seems to have succeeded on that front. That it's not a perfect fully-general bytecode format doesn't seem like a real knock against it, that's a much harder problem to solve. In any event it seems to be getting a lot more traction than any previous entries in the space, which is exciting!
  - klodolph 7y ago
    The criticisms in the linked article are simply not grounded in fact, and the article was obviously written by someone without any expertise in how modern compilers work. There are also a number of basic errors in the article. Liveness information simply doesn’t belong in the bytecode. SSA is trivial to recreate from local mutable variables (it would make a good homework assignment for someone in an undergrad “intro to compilers” class). WebAssembly is obviously a register machine. > With this, it becomes possible to get rid of locals entirely. Both factually incorrect and pointless. There is no tangible benefit in getting rid of locals entirely. You are merely changing out one representation (register machine) for a different one (stack machine). There are valid criticisms of WASM, but the linked article doesn’t have any. The weird part of WASM is the control structures. The rest of it is a fairly sensible, actually rather nice register machine. You can see that older bytecode systems like the JVM are stack machines, but newer ones tend to be register machines. This isn’t because people are getting stupid, it’s because there are legitimate reasons to prefer register machines, and on the balance of things, my observations are that people with experience in the field tend to prefer register machines.
    - MaxBarraclough 7y ago
      Interesting, thanks for the analysis. > You can see that older bytecode systems like the JVM are stack machines, but newer ones tend to be register machines. Like LLVM. Is there a good reason for WebAssembly not being SSA?
      - klodolph 7y ago
        There’s no good reason for WebAssembly to be SSA. That is a good enough reason for it not to be. The purpose of SSA is to make it easier to write optimizations. However, you wouldn’t be optimizing WASM anyway, you would necessarily translate it first into some kind of IR suitable for optimization passes. Might as well convert to SSA at that point, rather than bloat the bytecode by exposing implementation details of the target. Remember that WASM’s purpose is to be portable and safe. Making it more complicated just in order to make sophisticated back-ends slightly faster is a net loss. Using SSA would also make naïve/simple backends slower.
    - 7y ago
- tedmielczarek 7y ago
  The latter is very achievable using the Relooper algorithm developed by Alon Zakai and described in the Emscripten paper: https://dl.acm.org/doi/10.1145/2048147.2048224 https://dl.acm.org/doi/10.1145/2048147.2048224
  - klodolph 7y ago
    Achievable, but extra front-end work that belongs in the backend.
- kazinator 7y ago
  Nested, structured control can be broken into basic blocks without flattening it into if/goto first. It sounds easier, in fact. In fact, the construction of a basic block from flat code is a form of recovery of control structure. If the original code had nested loops, nesting will emerge in the basic block graph. A recursive traversal of the original structure could produce that graph more directly; it doesn't have to walk a flat list of instructions asking, "does this have a label on it which is the target of a branch". without having to walk a flat list of instructions asking questions like "is this the target of a branch". For instance, if we walk an if/then/else AST node, we can recursively get the basic block graph for the test, the then and else part, and then integrate that into a larger basic block graph according to a rigid pattern.