[sjrd]

It seems to me that there's a certain "blindness" between two compiler worlds.

Compiler engineers for mostly linear-memory languages tend to only think in terms of SSA, and assume it's the only reasonable way to perform optimizations. That transpires in this particular article: the only difference between an AST and what they call IR is that the latter is SSA-based. So it's like for them something that's not SSA is not a "serious" data structure in which you can perform optimizations, i.e., it can't be an IR.

On the other side, you actually have a bunch of languages, typically GC-based for some reason, whose compilers use expression-based structures. Either in the form of an AST or stack-based IR. These compilers don't lack any optimization opportunities compared to SSA-based ones. However it often happens that compiler authors for those (I am one of them) don't always realize all the optimization set that SSA compilers do, although they could very well be applied in their AST/stack-based IR as well.

[gobdovan]

I think the WASM world is a clear example that bridges the gap you're describing.

You usually compile from SSA to WASM bytecode, and then immediately JIT (Cranelift) by reconstructing an SSA-like graph IR. If you look at the flow, it's basically:

Graph IR -> WASM (stack-based bytecode) -> Graph IR

So the stack-based IR is used as a kind of IR serialization layer. Then I realized that this works well because a stack-based IR is just a linearized encoding of a dataflow graph. The data dependencies are implicit in the stack discipline, but they can be recovered mechanically. Once you see that, the blindness mostly disappears, since the difference between SSA/graph IRs and expression/stack-based IRs is about how the dataflow (mostly around def-use chains) is represented rather than about what optimizations are possible.

Fom there it becomes fairly obvious that graph IR techniques can be applied to expression-based structures as well, since the underlying information is the same, just represented differently.

Didn't look close enough to JSIR, but from looking around (and from building a restricted Source <-> Graph IR on JS for some code transforms), it basically shows you have at least a homomorphic mapping between expression-oriented JS and graph IR, if not even a proper isomorphism (at least in a structured and side-effect-constrained subsets).

[sjrd]

Only compilers that already had an SSA-based pipeline transform SSA to stack-based for Wasm. And several don't like that they have to comply with Wasm structured control flow (which, granted, is independent from SSA). Compilers that have been using an expression-based IR directly compile to Wasm without using an SSA intermediary.

[gobdovan]

I was imprecise, I was specifically thinking of already SSA-based tech.

My broader point is that for SSA-based pipelines targeting Wasm, translation between SSA/graph IR and stack-based IR is largely mechanical and efficient. Whether a compiler uses SSA as an intermediary or goes straight from an AST to Wasm, the fact remains that you can round-trip between a SSA-like IR and a stack-based IR without losing the underlying dataflow information.

Yeah, mapping is not canonical and some non-semantic structure is not preserved (evaluation order, materialization points, join encoding, CFG reshaping for structured control and probably some more structure I'm not familiar with), but optimization power is unaffected.

And JSIR seems to be based on an even stronger assumption.

Would appreciate corrections if you see things differently.

[sjrd]

Right. I believe we are in agreement on that.