4 ms·

Yes. The article is obsessed with the code quality generated by streaming compilers, which is probably the wrong thing to focus on. A real high-performance back

Yes. The article is obsessed with the code quality generated by streaming compilers, which is probably the wrong thing to focus on. A real high-performance backend has no trouble reconstructing SSA form and using it for optimizations. But forcing frontends to emit SSA would be a burden on them. (LLVM bitcode formally requires SSA form as well, but this can be worked around by using allocas.) It might, however, make sense to have another standard "SSA WebAssembly" program representation. There could then be standard tooling to compile vanilla WebAssembly to the SSA form, frontends could choose which variant they want to emit, and backends preferring SSA as input could still be made happy.

pizlonator 8y ago
SSA is a really strange form to send over a wire. It’s got poor space efficiency. It’s also annoying to interpret and not super cheap to turn into machine code. So, I don’t see the point of sending SSA over the wire.
- titzer 8y ago
  Agree. SSA requires deconstruction, which would slow down a streaming compiler.
- nonsince 8y ago
  Author here: I'm not advocating for an SSA register machine like LLVM, I'm just advocating for a format that makes it trivial to reconstruct SSA form on-the-fly. A pure stack machine with a statically-determinable stack depth and type at any given place in the program would give you the same information as SSA form in a more-compact way.
  - pizlonator 8y ago
    I keep forgetting that some people actually like the reducible control flow constraint. To me, if you have that constraint then it’s not really ssa. You literally can’t represent everything that llvm IR or B3 IR could. I think you should make sure you add that caveat when making equivalence claims. That said, the key reason for my push back is the suitability of SSA for fast backends. If you can afford to run some coalescing then SSA is at least perf-neutral. If you can’t then compiling from SSA will result in crappy code. As in, probably worse than block local RA. So your best bet is to somehow avoid having to coalesce. But that probably means using SSA only for extracting liveness and then running the world’s dumbest linear scan. Even that may not be as good as block local RA.
nonsince 8y ago
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

SSA is a really strange form to send over a wire. It’s got poor space efficiency. It’s also annoying to interpret and not super cheap to turn into machine code. So, I don’t see the point of sending SSA over the wire.

titzer 8y ago
Agree. SSA requires deconstruction, which would slow down a streaming compiler.
nonsince 8y ago
Author here: I'm not advocating for an SSA register machine like LLVM, I'm just advocating for a format that makes it trivial to reconstruct SSA form on-the-fly. A pure stack machine with a statically-determinable stack depth and type at any given place in the program would give you the same information as SSA form in a more-compact way.
- pizlonator 8y ago
  I keep forgetting that some people actually like the reducible control flow constraint. To me, if you have that constraint then it’s not really ssa. You literally can’t represent everything that llvm IR or B3 IR could. I think you should make sure you add that caveat when making equivalence claims. That said, the key reason for my push back is the suitability of SSA for fast backends. If you can afford to run some coalescing then SSA is at least perf-neutral. If you can’t then compiling from SSA will result in crappy code. As in, probably worse than block local RA. So your best bet is to somehow avoid having to coalesce. But that probably means using SSA only for extracting liveness and then running the world’s dumbest linear scan. Even that may not be as good as block local RA.

nonsince 8y ago

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.