patternModerate
Theoretical minimum number of registers for a modern computer?
Viewed 0 times
numberminimumtheoreticalregistersforcomputermodern
Problem
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:
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?
- 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?
Solution
If you allow direct memory access by memory address, then you do not need any "registers" because you can use memory locations instead. For example, memory at location 0 can be the program counter, at location 1 we have the stack pointer, etc. But that is cheating.
So to prevent ourselves from cheating, let us assume there is no direct memory access, because we could use fixed memory locations as registers. Then we can get away with two registers, a program counter and a stack pointer, as explained in the Wikipedia article on stack machines. The stack is only accessible through the stack pointer, and the program is only accessible through the program counter.
Another possibility is to use counter machines. A two-counter machine is Turing complete, i.e., it can compute whatever Turing machine can. This again is nicely explained in the Wikipedia article on counter machines.
So to prevent ourselves from cheating, let us assume there is no direct memory access, because we could use fixed memory locations as registers. Then we can get away with two registers, a program counter and a stack pointer, as explained in the Wikipedia article on stack machines. The stack is only accessible through the stack pointer, and the program is only accessible through the program counter.
Another possibility is to use counter machines. A two-counter machine is Turing complete, i.e., it can compute whatever Turing machine can. This again is nicely explained in the Wikipedia article on counter machines.
Context
StackExchange Computer Science Q#8941, answer score: 13
Revisions (0)
No revisions yet.