I took a course on compilers in my undergraduate studies in which we wrote a compiler that compiles source programs in a toy Java-like language to a toy assembly language (for which we had an interpreter). In the project we made some assumptions about the target machine closely related to "real" native executables, including:
- a run-time stack, tracked by a dedicated stack pointer ("SP") register
- a heap for dynamic object allocation, tracked by a dedicated heap pointer ("HP") register
- a dedicated program counter register ("PC")
- the target machine has 16 registers
- operations on data (as opposed to, e.g., jumps) are register-to-register operations
When we got to the unit on using register allocation as an optimization, it made me wonder: What is the theoretical minimum number of registers for such a machine? You can see by our assumptions that we made use of five registers (SP, HP, PC, plus two for use as storage for binary operations) in our compiler. While optimizations like register allocation certainly can make use of more registers, is there a way to get by with fewer while still retaining structures like the stack and heap? I suppose with register addressing (register-to-register operations) we need at least two registers, but do we need more than two?