5 ms·
I'm unclear, why transform to a bytecode as a first step? Wouldn't it be simpler to instead to transform to an AST and work against that for everything? Woul
by cogman10 7y ago
I'm unclear, why transform to a bytecode as a first step?
Wouldn't it be simpler to instead to transform to an AST and work against that for everything? Wouldn't it make sense to generate the bytecode as sort of a last step before doing heavy duty optimizations?
Seems like with JS you would be constantly transforming from bytecode -> AST -> bytecode -> machine code, such as every time a method adds a new field to an object or some optimization assumption is violated. It doesn't seem like it would be easier or faster to work with. I'm guessing there wouldn't be a whole lot of memory benefits either.
Would someone mind illuminating me on this design choice? (Granted, I've not taken a compilers course, so feel free to call me an idiot for not knowing something basic about how compilers work).
- steveklabnik 7y agoA bytecode is easier to keep stable than an AST is; an AST changes as the language changes, but that doesn't mean you have to change the bytecode, only change the transformation from the AST to the bytecode. I have no idea if this is the reason, but it's a possible one.
- pizlonator 7y agoThat’s a pretty good reason also.
- mhh__ 7y agoIt's a bit of a micro-optimisation but ASTs are also usually represented fairly sparsely, so processing on bytecode could be much faster due to more efficient cache utilisation etc - some benefits from memory locality and also from bytecode usually being smaller in memory) (I don't know JSC does it so that could be wrong)
- deleted 7y ago[deleted]
- pizlonator 7y agoAST is less transformable. We transform our bytecode as if it was just an IR. ASTs are a pretty annoying form to use as a source of shared truth for OSR. JSC has 4 tiers so we need a convenient-to-use shared truth IR. That’s what bytecode is for. For example, bytecode offers high-scalability answers to questions like “where should I exit” and “what is live when I get there”.
- fouc 7y agoIsn't bytecode essentially a machine language for a simplified VM? Why would it be more transformable than a tree?
- pizlonator 7y agoBecause it’s not a tree. Compiler IRs tend to have the property that operands are not themselves expressions; they can only be variables or maybe constants. That makes it easy to identify sequence points, which makes it easier to insert code or reshape the control flow graph.
- deleted 7y ago[deleted]
- fpoling 7y agoBesides already mentioned benefits the new bytecode is serializable so it is very easy to cache it. Serializable format of AST is a hard problem. WASM was supposed to be like that, but in the final design it became a stack machine.
- wahern 7y ago* Adding a new field or method to an object at runtime doesn't change the AST. * You don't translate from bytecode to AST. * In tiered JIT architectures--typical for dynamically-typed languages like JavaScript where as you point out effective types can mutate at runtime--most code is executed by an interpreter, not as compiled machine code.[1] Interpreters are more efficient when executing a bytecode than walking an AST. * Translating an AST straight to machine code is much more difficult than translating a low-level intermediate representation, and such representations are often easy to express as simple bytecodes. Compilers like GCC and LLVM use intermediate representations: RTL and IR. Both are effectively assembly languages, and like all assembly languages trivial to express as bytecode. GCC also has GIMPLE, a higher-level intermediate representation earlier in the pipeline which expresses a generic AST. The fact that GIMPLE and RTL coexist drives home the point that you don't want to be translating tree-like representations straight to machine code. * You don't need to take my word for this, or the word of anyone else. Every programmer should have experience writing parsers, compilers, and interpreters, regardless of whether they took a class or even went to university. By doing this most of the reasons for the way things are done will become immediately clear to you. Note that splitting strings with regular expressions does not count as parsing, not for these purposes. A good project, however, would be to write a regular expression parser, compiler, and interpreter. There are many examples to follow and you can copy their designs exactly; just don't copy+paste as actually going through the motions and understanding the complexities inherent in the implementations is how everything will become clear. [1] How this mutation is handled and why tiered architectures are preferable is another topic entirely.
- eridius 7y agoSwift and Rust also have their own higher-level intermediate representations that they translate their AST to before even going to LLVM IR (SIL and MIR respectively). Rust used to translate their AST directly into LLVM IR but they switched to going through MIR first because it unlocks a lot of optimizations as well as improved user-facing functionality such as non-lexical lifetimes in the borrow checker.
- steveklabnik 7y ago
- olliej 7y agoThere are a slew of problems. For a very long time JSC did use an AST, and interpreting and executing an AST is expensive. The very first version of the byte code interpreter (all hail squirrelfish) was in the order of twice the speed of the AST, and the AST had been extensively micro-optimized at that point, to the extent that the dispatch cost itself (a single indirect call) was more than 10% of execution time. There were also a bunch of correctness issues: * Handling exceptions required manually check call results everywhere. There was an unending stream of minor correctness bugs caused by this. Looping semantics were similarly exciting. Because every call technically required those checks there was a significant cost there, even though there were numerous cases they were missed. * Changes in language semantics required duplicate changes in many different places * New language features require a lot of very similar behaviour, with minor variations that resulted in duplicated code, introducing new places to accidentally miss exception and loop checks. * Memory overhead was massive, both in terms of actual usage, and also allocation costs. * Significant reductions in maximum recursion depth. Back in the days of the AST interpreter JSC had a hard limit of 500 levels of recursion, with plenty of checks, and it would still periodically blow the system stack and crash. The cost of producing the byte code in the first place is super low, and because the byte code is all essentially the most primitive of JS operations, new language features generally don't require the optimizing passes to be aware of any changes, because they're mostly just syntax around existing primitive operations.
- deleted 7y ago[deleted]