Oh waw, I had totally forgotten about the handkerchiefs. But this is indeed how I was first thaught juggling when I was a kid. Thanks for the trip down the memory lane!
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.
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).
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.
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.
Hum, IIRC, using your definition of an AOT compiler, then V8 is an AOT compiler. V8 never interprets code. It immediately compiles it to machine code. It improves it later, but it's never slow.
V8 is a JIT compiler that uses the Ignition [1] interpreter and only compiles sections of code down to machine instructions once they've been marked as hot via TurboFan [2].
V8 can also go back and forth from machine instructions back to bytecode if it identifies that certain optimization assumptions no longer hold.
Interesting. When compiling Scala.js to ECMAScript 5, we still have an implementation of bitwise floating point conversions based on double operations and integer shifts. [1] We also use a lookup table for powers of 2, and don't use anything but primitives (no log or pow, notably). We do have a few divisions, but I see now how I could turn them into multiplications. Dealing with subnormals is tricky because the inverse of the subnormal powers of 2 are not representable.
We have one loop: a binary search in the table of powers of 2 for the double-to-bits conversion. It has a fixed number of iterations. I had tried to unroll it, but that did not perform any better.
I'll have to dig more to understand how they got rid of the comparisons, though.
I wonder whether their implementation would be faster than ours. At the time I wrote our conversions, they beat every previous implementation I was aware of hands down.
Hi, author here. My version definitely shouldn't be faster unless something very weird is going on with the runtime (though I think with the benefit of hindsight some further optimisation of it is possible). I have never seen a good use for this, aside from as a proof that it is possible, but I can imagine it coming up if, say, you wanted to write an exploit for an esoteric programming language runtime.
If you still maintain this code and want to optimise it, I don't think you should need a full powers-of-two table, just having log(n) powers of two should do in a pattern like:
if (v > 2**1024) { v *= 2**-1024; e += 1024; }
if (v > 2**512) { v *= 2**-512; e += 512; }
...
That's a straightforward memory saving and also leaves v normalised, so gives you your fraction bits with a single multiplication or division. This is a little less simple than I'm making it look, because in reality you end up moving v to near the subnormal range, or having to use a different code path if v < 1 vs if v >= 2 or something. But otherwise, yeah, the code looks good.
Thanks for the feedback, and congrats on your achievement.
We do still maintain this code, although it is deprecated now.
Even with the unrolled tests, we would still keep the table for the decoding operation, I believe. But it's true that it would at the same time provide the normalized value. That could be beneficial.
I genuinely did that a few times. Using an ssh client to fix a commit failing CI, for example. Even launching release builds remotely. Notably once when I was on vacation and half the Scala ecosystem was waiting for me.
JavaScript engines do optimize integers. They usually represent integers up to +-2^30 as integers and apply integer operations to them. But of course that's not observable.
You are half correct about 2^53-1 being used (around 9 quadrillion). It is the largest integer representable with 64-bit float. JS even includes a `Number.MAX_SAFE_INTEGER`.
That said, these only get used in the rare cases where your number exceeds around 1 billion which is fairly rare.
JS engines use floats only when they cannot prove/speculate that a number can be an i32. They only use 31 of the 32 bits for the number itself with the last bit used for tagging. i32 takes fewer cycles to do calculations with (even with the need to deal with the tag bit) compared to f64. You fit twice as many i32 in a cache line (affects prefetching). i32 uses half the RAM (and using half the cache increases the hit rate). Finally, it takes way more energy to load two numbers into the ALU/FPU than it does to perform the calculation, so cutting the size in half also reduces power consumption. The max allowable size of a JS array is also 2^32.
JS also has BigInt available for arbitrary precision integers and these are probably what someone should be using if they expect to go over that 2^31-1 limit because hitting a number that big generally means you have something unbounded and might go over that 2^53-1 limit.
In Scala you can do it, because you can define your own operators (which are nothing but method names), and you can extend types you don't control. You are a bit constrained by the operator precedence rules, but it's usually good enough.
It's bad practice to make DSLs left and right, obviously. But when one is warranted, you can.
Technically its type inference is not HM but it's as expressive. In particular it has GADTs and HKTs, which I saw in your docs.
I wonder what you feel is missing from Scala (its .js/Wasm version) that Lumina provides?
[1] https://laminar.dev/
reply