2 ms·
We will store that intermediate value in the stack, and read it back after the right term is done computing. If we take care that the code we generate for the r
by userbinator 3y ago
We will store that intermediate value in the stack, and read it back after the right term is done computing. If we take care that the code we generate for the right term doesn't write into the same stack slot, then we can be sure that the value will be preserved.
There are push and pop instructions which are perfectly suited to this nested value use. In the past, lamenting how many compilers don't seem to realise that (and the fact that push/pop are specially optimised on x86 via hardware known as the stack engine), I wrote a piece of a code generator with similar capabilities to the one in this article as a proof-of-concept, and with the addition of some trivial (rotating FIFO-like) register allocation, was able to generate surprisingly compact and fast code that looks like it could've been written by a human Asm programmer.
I believe Crenshaw's famous compiler tutorial also makes the same simplification, and it's also a powerful generalisation since it means that arbitrarily deep nested expressions can be compiled, as long as there is sufficient stack space.
- kragen 3y agocrenshaw mostly just emits pushes and pops; he recommends a simpler version of that rotating fifo technique (just spilling deeply nested values onto the stack so you get a performance cliff, instead of pushing old values out of the fifo) but doesn't actually show it in ur-scheme i just pushed and popped, getting performance much less terrible than i expected, but still probably a third of the performance the rotating fifo register allocator would give
- sebastianmestre 3y ago> There are push and pop instructions which are perfectly suited to this nested value use. In the past, lamenting how many compilers don't seem to realise that (and the fact that push/pop are specially optimised on x86 via hardware known as the stack engine) That's fair, but in the article I also store local variables relative to %rsp, so I wouldn't want it changing at all I could use %rbp for that instead, but then I'd have to explain it in the article :^)
- userbinator 3y agoThat's fair, but in the article I also store local variables relative to %rsp, so I wouldn't want it changing at all You only need to keep track of how much you've put on the stack (which can be a single counter) and adjust the offsets appropriately. But then you'd have to explain that too...