Thursday, February 24, 2011

Where did the stack go?

[This post doesn't describe things the way I'd like to. Please see the subsequent post.]

The IBM 704 didn't have a stack.

This was not unusual at the time. Although stacks were known about for years before, low-level languages did not make much use of them. Early FORTRAN certainly didn't need a stack, so IBM didn't bother with a hardware implementation.

Not having a stack does make it a bit of a challenge to program. For example, when you call a subroutine, where does the return address go?

The IBM 704 had an instruction TSX (Transfer and Set Index) that was designed for subroutine linkage. TSX would do two things. First, it loaded a register with the two's-complement value of the program counter. (The IBM 704 was much better at subtraction than addition. The two's complement of the program counter made it easier to dispatch because subtracting a two's complement number gives the same result as adding the uncomplemented number.) Second, it loaded the program counter with the subroutine address. Loading the program counter would cause an unconditional jump to the subroutine.

There was obviously a data path from the instruction register to the program counter — that's how the target address got from the instruction stream to the program counter. Likewise, there was a data path from the program counter to the register set. However, there doesn't appear to be a data path from the register set back in the other direction. So we can use the TSX instruction to call a subroutine, but once there we need to do a nasty trick to get back. That trick is to end the subroutine with an unconditional jump (opcode TRA). When we enter the subroutine, we expect the return address to be in one of the registers (by convention, LISP used register 4). The first thing the subroutine does is to save the return address in the target field of the TRA instruction. This modifies the code so that the unconditional jump at the end takes us back to where the subroutine is called.

But what if the subroutine needs to be re-entrant?

Ultimately, you need a stack (or a heap). There are several options for implementing one. The obvious idea of allocating a block of memory and keeping a pointer to the top of stack was not obviously the best idea. Without dedicated hardware, operations like push and pop become quite expensive. You have to fetch the stack pointer from memory, perform an addition or subtraction, do an indirect memory reference, and write the new stack pointer back to memory. (And if you thought the x86 didn't have enough registers, the IBM 704 had only 3 index registers.)

Another method is to use a linked list as a stack. This is not obviously a bad idea. Once the linked list is created at program initialization time, pushing and popping can be done via pointer chasing. This avoids having to use the ALU for adding and subtracting the stack pointer. Furthermore, you didn't have to guess how much stack space to reserve. with only 32,000 words of memory, you didn't want to waste any on unused stack reserve. For these reasons, both IPL and LISP I used a ‘push-down list’ to implement re-entrant subroutines.

3 comments:

John Cowan said...

The PDP-8's subroutine call instruction left the PC in the target address and then jumped to the target address + 1. Return, therefore, was an indirect jump through the target address. By indirect retrieval, one could collect any arguments placed immediately after the call. Alternatively, a single argument could be placed in the accumulator register (effectively the only register).

Most programs weren't recursive, but recursion could be managed by retrieving the return address and pushing it into a stack block, either generic to the whole program or specific to this particular subroutine. With no registers, re-entrant routines weren't practical.

Eddie said...

Good timing, just today I implemented a quasi-stack in a system without one. Had subroutines that I wanted to be re-entrant, and all string or XML variables so I used XML.

carlM said...

IBM 360-370 never had a stack, they used linked list save areas for the registers on subroutine call. A non-program called IEFBR14 was used as a no-op. Postmortem debugging usually involved traceback thru the link list, examining register values to augur the error.