A C Compiler for Stack Machines (2006) [pdf]

From the thesis abstract:

>"Included with this thesis is a portable C compiler for stack machines, which incorporates these new register allocation methods. The C compiler and associated tools (assembler, linker and simulator) are included in the CD."

I looked at Mark Shannon's page below but didn't find a link to an ISO image of the mentioned CD.

http://www.dcs.gla.ac.uk/~marks/

As far as I can tell from a quick (and very casual) skimming, Mark's lcc-s is implemented as a backend for lcc.

http://www.cs.princeton.edu/software/lcc/

https://sites.google.com/site/lccretargetablecompiler/

https://github.com/drh/lcc/tree/master

If anyone has found the mentioned lcc-s code, please post a link.

What timing - I just read "Stack Computers: the new wave" by Philip Koopman (http://users.ece.cmu.edu/~koopman/stack_computers/contents.h...). I'm pretty sure it was recommended by someone on HN, but it's quite a nice mid\late 1980s take on a tech which never really took off. I wonder what Koopman would have thought about how things turned out.

What is missed here is space optimization like what human do in Forth.

Zero-operand instructions tend to have the same layout for same semantics. This contrasts them with three-operand or even one operand instructions sets, where adding two values can have several encodings. add r1,r2,r2 (for r1 := r2+r3) is different in encoding than add r2,r3,r4. The precise indices of registers depend on the surrounding - how they are allocated elsewhere. Thus the probability that two semantically identical instruction sequences would have same encoding quickly goes to zero as instruction sequence increase. x[i] = y[j] can have 31^4 encodings for MIPS as upper bound even without considering instruction order.

For stack-based zero-address instructions you will have ADD wherever you need to add two values. x[i] = y[i] will have same encoding up to reordering (compute x[i] address first or second). The number of reorderings is finite and here we come to the salient part: we can abstract away operations like compute address of x[i] into their own definitions. We will have one call for, say, three instructions and RET.

This call is also a target for reductions. Instead of long sequence of stack operations we can now have two calls to COMPUTE_X_I and something like ROT between them. Are there sequences like this somewhere? Of course there will be. Repeat till the fixed point. It is pretty much like LZ78 algorithm - encode string into it's own symbol.

The closest thing to this I saw was a paper about compiler for VLIW DSP that generated stack code for most of program and VLIW code for the performance critical parts. They created opcodes for most frequently used opcode sequences, but that's all. They still demonstrated significant code size reduction, but nowhere close to Forth-style compressed code that produced by Forth programmers.

An interesting topic, did not know there is such a comprehensive work on it. My initial (lazy) take was to reconstruct expression trees out of an SSA, reordering where appropriate (with no side effect order changes). I only did "register allocation" for the remaining stack-allocated slots then.