Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 6 down vote favorite
1

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?

share|improve this question

1 Answer

up vote 11 down vote

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.

share|improve this answer
Thank you for the reply! The article on stack machines mentions, though, that the machine is capable of direct memory access (to perform operations on the topmost stack elements and push the result back on), so that is still cheating, right? As for the counter machine, I read that article. I also have read a similar proof of T.C. of a 2-CM, but both effectively involve storing all of RAM in two registers, which seems even more like cheating to me. – BlueBomber Jan 15 at 18:24
Well, at some point it is not cheating anymore. The stack operations are not cheating, as long as they disallow direct access to a fixed location in memory. It is ok to be able to, say, rotate the three topmost elements of the stack. Your question is a bit strange, anyhow, so it doesn't pay of to obsess over what is and is not cheating. – Andrej Bauer Jan 15 at 21:49
Thanks again for the reply. Anytime the topic relates to theoretical bounds, cheating is even less acceptable! That doesn't mean it's not instructive, though. The point when it's not cheating is when, well, there is no cheating, I guess. I found your initial answer informative, but the problem is that our model overlaps all of the Turing Machine, Counter Machine, and Stack Machine models, and given our assumptions (including finitely many finite registers and no direct memory access), can we get by with only two registers? – BlueBomber Jan 15 at 22:24
1  
I find the question strange because it is hard to pin down real-world concepts such as processor, register, memory access, etc, but you need those pinned down in order to be able to prove anything. So the end result will be that whatever you prove is easy to prove, but it depends very much on how you formalize the question (what your theoretical notion of "processor", "register", "memory", etc., is). – Andrej Bauer Jan 16 at 8:37
1  
A compiler textbook does not allow us to prove much, at least not in the mathematical sense of the word "prove". You need to go one step further in formalization of hardware to arrive at something that will allow proof. Anyhow, we're splitting hairs, and I already gave you my best answer. – Andrej Bauer Jan 21 at 7:15
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.