Procedures in Atom

Up next, I want to add the ability to call procedures or functions. This will give me the ability to reuse pieces of code. This will require me to start to divide up memory into various regions, namely somewhere to store the program and somewhere to store the stack. This page describes change between #atom-refactor and #atom-procedure in the git repository.

What is Needed?

The first question I need to answer is, what do I even need? When calling a procedure I need to perform a jump, changing the PC to the instructions of the procedure. What makes this different from a jump is that it needs to be reversible. When the procedure is over, execution should resume where the call was made. This means that I need to be able to save the value of the PC somewhere that can be restored.

I could write the PC to a special register that can be recalled later. This would work for a single procedure call, and for certain types of work it would be sufficient. However, it would not allow nested calls. Instead, I am going to introduce a stack where values of the PC can be written. When a procedure is called, the PC is pushed onto the stack, and when it is finished you restore the PC and pop the value from the stack.

This stack is just a part of memory. I will keep track of a pointer that walks up and down as values are pushed and popped from the stack. This memory will need to be offset from program memory, which starts from from 0x0000. For now, I have made the decision to start the stack from 0x8000, which is halfway through the computers memory. This is enforced by the hardware.

Instructions

As described above, I need a pair of instructions. One to jump to a procedure, and one to return from it. When jumping, I need to save the value of the PC to the stack so that the return instruction can jump back.

For the jump instruction, I want to be able to jump both by a relative offset, and to a value in a register. The immediate value will take 8 bits, and the register identifier will take 4 bits. However, I only need one of them at a time. After taking up four bits for the op code 0b1000, I have 4 bits left over. I can use one of those to switch between an immediate or register jump. For this purpose I will pick bit 11. This leaves me with two variants of the instruction. When jumping with an immediate, it looks like 0b10000XXXIIIIIIII. When jumping to a register, it looks like 0b10001XXXXXXXAAAA.

Both of these have unused bits, and I would like to find something to do with them. For the register jump, I could enable relative jumps, and have enough room to specify two registers or an extra immediate value. The immediate variation has less wiggle room. I could use those three bits to expand the range of the immediate, or could add more flags if I find a use for them.

The return instruction doesn’t require any arguments. Because of this, I am going to use a generic instruction for it. As a reminder, all generic instructions start with 0b0000. Right now, there are only two instructions reserved, 0b0000000000000000 and 0b0000FFFFFFFFFFFF. I am going to simply make the return instruction 0b0000000000000001. This is just the next free instruction, and also makes it really easy to see where procedure returns are memory.

Implementation

First, I need a way to store a stack pointer (SP). In theory, I could reserve one of the 16 general purpose registers as the SP. That would give me a lot of freedom in manipulating it, which could be good for experimentation. However, I need to be able to manipulate the SP register when pushing and popping values, which is not something that I can do right now. Since that would be involved anyways, I am going to add a special SP register. To start, all I need to be able to do is increment and decrement the pointer, which will be used as a value is pushed or popped respectively.

For the actual instructions, I need to figure out what actions need to occur. First up, the push instruction, which needs to: write the value of PC to RAM at address in the SP, increment the SP, and jump to the call address. Primarily, this instruction is very similar to a jump, just with information saved to the stack. The return instruction is also very similar to a jump, except that I need to use a value from memory. More specifically, it needs to: write the value in RAM at the SP to the PC and decrement the stack pointer.

While implementing this, I started to layout how I will identify more general instructions. Right now, I have a simple solution for HALT that just checks if the lower 12 bits are high and the opcode is zero. It only needs to send one signal out, so this is acceptable. However, as I add more instructions which will also be more complex, I need a better solution. This is true of the return instruction, which needs to send a variety of signals and values.

I like what I have for op codes, and I want this new system to tie into that. Each instruction is parallel signal that can branch of into the signals it needs:

For the new return instruction, I want to identify 0b0000000000000001. The circuit on the left checks that bits [4-15] are all zero. If so, the decoder on the right is able to represent instructions0x0000 though 0x000F. This only works because zero is noop and is guaranteed to do nothing. If this was not the case, I would need to be able to disable the decoder.

Testing

I need to test both of these instructions. I want to be sure that the call instruction jumps to a procedure, and that the return instruction returns to the call location. I could just set a value in and after the procedure, but I thought it would be neat to propagate a value through registers. By that, I mean that I will set r0 to some value. Within the procedure, I copy from r0 to r1. After the procedure call, I move r1 to r2. If the call instruction fails, only r0 will contain the value. If the return instruction fails, r0 and r1 will contain the value, but r2 will not.

SETLO r0 0x01

CALL 0x02
MOV r1 r2
HALT

; procedure propagating value
MOV r0 r1
RET

; halt if RET failed
HALT

Another feature of the stack is that a function can call itself, which I also want to test specifically.

SETLO r0 0x05
SETLO r1 0x01

CALL 0x01;>proc
HALT

;=proc
SUB r0 r1
JEQ 0x01
CALL 0xFD;>proc
RET

This test uses a procedure to recursively decrement r0 to zero. Each call decrements it by one. If the value was one, the recursive call is skipped.

Limitations

Being able to nest procedure calls is good, but there is still a fundamental limitation. Since there are finite registers, nested calls will have to share them. That means the procedure making the call (the caller) cannot know that the registers will have the same value after the call is complete. The function been called (the callee) itself does not have the capacity to restore the registers to their original values.

This severely limits the usability of procedures. You could manage some procedures, but it would require the caller to know everything about the callee, including the entire tree of calls it makes. That system is not very flexible. Modifying a function like this would be very difficult as they get large.

Pushing and Popping Data

The solution is to allow arbitrary data to be placed on the stack. This allows for the caller to save data that it can recover after a procedure has completed. It also allows the callee to restore registers as it completes, by saving the values to the stack at the start and restoring them at the end.

Instructions

Like call and ret, I need two instructions: one to push data to the stack and one to pop data from the stack. Each of the instructions needs to identify one register. Combined with an op code, there are 8 bits left over. Because the instructions themselves don’t need that many bits, I am going to put them under the generic instructions op code. I am going to define a new category within generic instructions for single register operations. Those instructions will have 0b0001 in bits [8-11]. Bits [4-7] will identify the target register, and bits [0-3] will select an operation: 00000001TTTTOOOO.

Push will be operation 0b0000 and pop will be operation 0b0001.

Implementation

These instructions will very similar to the call and return instructions. Instead of writing the PC to or from the stack, I use a register. This means there is no jumping, just data. The image below shows the main circuit after adding push and pop, but it looks effectively identical to when call and ret were added. The entirety of the difference between the two sets of instructions is contained within the control unit.

The interesting change in the control unit is the addition of circuitry that can identify single register operations. Single register operations specifically check that the bits [8-15] are 0b00000001. I also cleaned up the circuitry for checking the lower 12 bits, grouping them into fours which let me reuse some of them for the single register operations.

Testing

To test push, I just push a series of values onto the stack. The expectation is that these values will be in memory where the stack stars.

SETHI r0 0xDE
SETLO r0 0xAD
PUSH r0
SETHI r0 0xBE
SETLO r0 0xEF
PUSH r0
SETHI r0 0x12
SETLO r0 0x34
PUSH r0
SETHI r0 0x56
SETLO r0 0x78
PUSH r0
HALT

Popping relies on pushing, so I left it as a separate test. The test for pop itself involves pushing two values onto the stack. Both values were written to r0, and after the values were pushed I zero out r0. After that, the values must be recovered from the stack. The expectation is that I will have the correct values in registers r0 and r1.

SETHI r0 0xDE
SETLO r0 0xAD
PUSH r0
SETHI r0 0xBE
SETLO r0 0xEF
PUSH r0
SUB r0 r0
POP r1
POP r0
HALT

Next up, I am going to be using all these procedure tools and start to see what I can create on Atom.