11
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ A "heap pointer" seems a weird idea. Because contrary to the stack, the heap is not LIFO and doesn't reduce to push/pop semantics. You should rather see dynamic memory allocation as calls to malloc/free routines. $\endgroup$
    – user16034
    Commented Sep 12, 2019 at 13:52

2 Answers 2

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – BlueBomber
    Commented Jan 15, 2013 at 18:24
  • $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Commented Jan 15, 2013 at 21:49
  • $\begingroup$ 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? $\endgroup$
    – BlueBomber
    Commented Jan 15, 2013 at 22:24
  • 1
    $\begingroup$ 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). $\endgroup$
    – Andrej Bauer
    Commented Jan 16, 2013 at 8:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrej Bauer
    Commented Jan 21, 2013 at 7:15
1
$\begingroup$

The PIC architecture which was introduced by General Instruments in the 1970s and is still in use today had the following registers:

W register (not addressible)
01    Timer/Counter
02    Program Counter
03    Status
04    File-Select Register
05-07 One register for each I/O port
08-1F General-purpose registers/"memory"

A typical instruction will read a register, perform a computation using the value read and W, and then store the result of the computation either to W or to the register that was read. One of the available computations yields "the value read, ignoring W"; another is "take W, ignoring the value read". The bit patterns that would correspond to "read XX, then take W, ignoring the value read, and store the result in W" are used for NOP as well as a variety of special instructions.

To allow address computations, the processor's execution unit will watch for instructions that encode an address of 00, and substitute the contents of the File Select Register for the address.

Although having to feed all values through the W register can be a bottleneck, the PIC architecture has as a larger working set than other architectures using the same length instruction word. On the PIC16C54 (still made today, and very similar to the 1970's PICs) instructions are 12 bits long. On many other 16Cxx or 16Fxx parts, instructions are 14 bits long and can directly access a 128-byte address space. If the working set of a program fits well with the working set of the instruction set, a statement like "total += value", where "total" and "value" are of type unsigned char, would compile to:

movf  value,w
addwf total,f

On something like the ARM, even if one has a register pre-loaded with the base address of one's variables, the code would be more like:

ldr    r0,[r7+value]
ldr    r1,[r7+total]
add    r1,r1,r0
str    r1,[r7+total]

In many cases, a compiler would be able to avoid doing loads and stores with every operation, but on something like the PIC, the benefits of the larger working set can sometimes outweigh the limitations of having to go through W all the time.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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