5 ms·

Author here: I'm obsessed with the quality of streaming compiler-emitted code for a few reasons. Firstly, I'm working on an optimising streaming compiler. Seco

Author here: I'm obsessed with the quality of streaming compiler-emitted code for a few reasons. Firstly, I'm working on an optimising streaming compiler. Secondly, I work for a blockchain company and we can realistically only allow linear-time compilation, this doesn't necessarily mean streaming compilation but we might as well make it both (I explain why we need linear-time compilation in a different article http://troubles.md/posts/why-wasm/ http://troubles.md/posts/why-wasm/). Thirdly, anything that gives streaming compilers more information also means that non-streaming compilers have to reconstruct less information, and lastly in this particular case there is no reason (except for backwards compatibility constraints) why we can't preserve more of the information from the front-end and have streaming compilers emit better code.

pizlonator 8y ago
A streaming compiler can emit really great code even without liveness. It’s not clear to me what optimizations you’re hoping to get from this. To do most SSA optimizations you need a backend that can lower from SSA, which is not linear afaik. Register allocation might be helped a bit by liveness, but you can get block-local liveness information in linear time already - so for your thing to be better you’d have to prove that there is something sweet about having a non-SSA compiler that does register allocation using imperfect liveness information, which was provided by an adversary. Then you’d have to prove that this is ok - that an adversary can’t force you to do more work than you want by lying about liveness. It’s probably not ok; for worst case perf you’re almost certainly better off not trusting provided liveness info and reconstructing it yourself on a block-local basis. Anyway. I could tell you a lot more about how to design compilers but I have to take my kid to school.
- nonsince 8y ago
  A statically-typed stack machine like Wasm is homomorphic to SSA form with liveness, and it's impossible to lie about liveness in this format. Most of the complexity in the streaming compiler that I'm working on is around producing good code for locals when we have no liveness information for them. I explain why this is in the article.
  - pizlonator 8y ago
    It’s not guaranteed that using the liveness implicit in the SSA that falls out of a stack language is going to give you better code in less time than a block-local register allocation with locals live at block boundaries spilled to the stack.
    - titzer 8y ago
      Indeed, and for good spilling decisions, you'll want to have next-use distance information for values. While a stack machine gives you an approximation of this (deeper in the stack is farther in the future), for best results I imagine you'll want to do two passes anyway, so locals are no worse for this, other than at block boundaries, if you lack liveness you have to spill them.
titzer 8y ago
Years ago, I thought a single-tier design of an (offline) compiler was best (OVM). And then I thought a heavy offline compiler and two tiers of of the same JIT was best (Jikes). Then I thought an interpreter with an an optimizing JIT was best (HotSpot server). Then I thought a slightly less optimizing JIT was best (HotSpot client). Then I thought that two JITs were best (V8 w/ Crankshaft). Then two JITs with a super heavy optimizing JIT was best (V8 w/ TurboFan). Then I thought a single tier for Wasm was best (V8 w/ TurboFan). Then I thought an interpreter and a heavy optimizing JIT was best (V8 w/ Ignition and TurboFan). Then I thought two JITs for Wasm was best (V8 w/ Liftoff and TurboFan). I've seen a single baseline compiler go through a metamorphosis from essentially streaming (HotSpot client V1) to full SSA-based with register allocation (HotSpot client today). In other words, prepare for change. A single tier is probably not going to be your final design.

pizlonator 8y ago

A streaming compiler can emit really great code even without liveness. It’s not clear to me what optimizations you’re hoping to get from this. To do most SSA optimizations you need a backend that can lower from SSA, which is not linear afaik. Register allocation might be helped a bit by liveness, but you can get block-local liveness information in linear time already - so for your thing to be better you’d have to prove that there is something sweet about having a non-SSA compiler that does register allocation using imperfect liveness information, which was provided by an adversary. Then you’d have to prove that this is ok - that an adversary can’t force you to do more work than you want by lying about liveness. It’s probably not ok; for worst case perf you’re almost certainly better off not trusting provided liveness info and reconstructing it yourself on a block-local basis. Anyway. I could tell you a lot more about how to design compilers but I have to take my kid to school.

nonsince 8y ago
A statically-typed stack machine like Wasm is homomorphic to SSA form with liveness, and it's impossible to lie about liveness in this format. Most of the complexity in the streaming compiler that I'm working on is around producing good code for locals when we have no liveness information for them. I explain why this is in the article.
- pizlonator 8y ago
  It’s not guaranteed that using the liveness implicit in the SSA that falls out of a stack language is going to give you better code in less time than a block-local register allocation with locals live at block boundaries spilled to the stack.
  - titzer 8y ago
    Indeed, and for good spilling decisions, you'll want to have next-use distance information for values. While a stack machine gives you an approximation of this (deeper in the stack is farther in the future), for best results I imagine you'll want to do two passes anyway, so locals are no worse for this, other than at block boundaries, if you lack liveness you have to spill them.

titzer 8y ago

Years ago, I thought a single-tier design of an (offline) compiler was best (OVM). And then I thought a heavy offline compiler and two tiers of of the same JIT was best (Jikes). Then I thought an interpreter with an an optimizing JIT was best (HotSpot server). Then I thought a slightly less optimizing JIT was best (HotSpot client). Then I thought that two JITs were best (V8 w/ Crankshaft). Then two JITs with a super heavy optimizing JIT was best (V8 w/ TurboFan). Then I thought a single tier for Wasm was best (V8 w/ TurboFan). Then I thought an interpreter and a heavy optimizing JIT was best (V8 w/ Ignition and TurboFan). Then I thought two JITs for Wasm was best (V8 w/ Liftoff and TurboFan). I've seen a single baseline compiler go through a metamorphosis from essentially streaming (HotSpot client V1) to full SSA-based with register allocation (HotSpot client today). In other words, prepare for change. A single tier is probably not going to be your final design.