How was C ported to architectures that had no hardware stack?

Question

Thinking about machines such as the PDP-7, PDP-10, CDC-160 and so on¹, these are machines which do not have a stack pointer which can quickly and easily change to point to a new stack frame, like the x86 or ARM machines we have today.

The C standard does not say anything about a stack, since C actually doesn't need one. I can see that local variables may in most cases be placed somewhere in memory for most functions. The functions for which that doesn't work are the recursive ones and the mutually recursive ones, (which cannot be converted to iterative routines by an optimisation stage). But the linker won't know anything about that, will it?

If there is a known compiler which does anything other than use or implement a stack, my question is to see a description of what it does "instead", ideally with a link to source code.

---

^{1: Yes, the Parallax Propeller also fits in this category of machines, and I'm sure many microcontrollers do, and so this question is not purely about Retrocomputing. But still I think the question belongs here because early C porting efforts will have the answer to the question.}

Answer 1

How was C ported to architectures that had no hardware stack?

Simply by implementing a dynamic memory management for subroutine calling, parameter passing and local memory.

If there is a known compiler which does anything other than use or implement a stack,

Now this is a completely different question than the one made in the headline.

Implementing a stack isn't anything special to porting C, nor is a stack at all an invention of C. C inherited its usage from ALGOL, which was first implemented (*1) by Friedrich Bauer and Klaus Samelson (among others) - the same men who 'invented' the stack in 1955 (*2) and got a related patent in 1957.

A CPU stack as we know it today (and is used by C) is just a very primitive implementation of the stack principle defined by them. It's a variant optimized for subroutine return address handling - not necessarily good for parameter passing or local variables.

All languages that allow local variables and/or reentrant subroutine calling (*3) use some form of stack (*4). This includes such dinosaurs as Fortran or COBOL (*5). Bauer was eventually the most influential single person in early compiler development, writing several papers that defined the foundation for almost every language developed thereafter.

In the beginning the stack was mainly seen as a software issue: a rather complex data structure that needs to suit the language, nothing to be supplied by the hardware. How much this is true can be illuminated by the /360 design. While designed entirely after the stack had been introduced in programming languages and finished in 1965, it does not feature a stack pointer or any auto-indexing instructions that could be used for a stack. The hardware developers didn't think it would be of any good to implement such, especially as it would have been a quite complex instruction (*6), considering the different ways stacks were handled by different languages.

my question is to see a description of what it does "instead", ideally with a link to source code.

In addition, focusing on the stack here is in fact not just about the data structure, but the wider area of calling conventions. So let's split this up a bit between storage and parameter passing.

The /360 is a prime example for a widely used architecture without, so let's use it.

Local Storage for Register Saving and Variables.

Static Storage

The closest that comes to an 'instead' are maybe calling convention used on IBM /360. They were ubiquitous and survived with assembler code way into the 1980s.

Here each subroutine also had a piece of private memory where all register content of the caller (*7) as well as local variables were stored. The register storage area was traditionally called SAVEAREA. There was no separate handling of the return address, as it is stored in one of the /360 registers. On return the registers were restored and program flow was transferred back to the caller. As a side effect, in these implementations all local variables are static and available for the next program run.

Stack Oriented Storage

(To understand this, it is useful to remember that the narrowed down version of a hardware supported word (or byte) orientated stack is just a special case of the general definition.)

Another, more elaborated was the usage of a stack. For example, the COLUMBUS implementation (*8). Here a register, usually R13, called R@STACK, was pointing to the frame of the actual nesting level. It had to be word aligned (*9). The first (lowest) 16 words (64 bytes) where kept free as storage for the register set of the next level, again called SAVEAREA, while everything above was used for local variables (*10). The stack was handled by the callee, not the caller. Thus a subroutine (function) call was simple:

L    R15,=V(FUBAR)           * Linkable address of the function to be called
BALR R14,R15                 * Subroutine call (*11)

The subroutine's entry code depended on the way stack underflow was handled. For this example we assume the usage of guard pages (*12) to issue an addressing error when exceeding the available memory. So everything to be done is saving the caller's register content and establishing a new stack frame:

STM  R14,R13,0(R@STACK)      * Store all registers in the save area (At R13)
SH   R@STACK,=Y(LLOCAL+64)   * Move the stack register down the the amount
                             * needed local storage plus room for a new SAVEAREA

Now the subroutine follows.

At the end, all cleanup is done automagically by restoring the registers of the caller:

LM  R14,R13,LLOCAL+64(R13)   * Restore registers (*13)
BR  R14                      * And return

And we're back.

Parameter Passing

Static Procedures

Conventions for parameter passing and return codes where rather sparse on this and next to every program made up their own variations. In general R0 and R1 where used for parameter passing, often pointing to parameter blocks (*14), then again it was quite common to have a different list of parameters loaded into many registers with no structure at all.

Similar, there were no conventions about parameter returns. Often R15 was used, but not really consistent.

Dynamic, Stack Using

While the COLUMBUS package did introduce a stack to assembler (and other languages), its calling convention was not necessarily stack based. In general, parameters where passed to a function as a memory reference. It was up to the programmer to build up the parameter list (*15), and pass its address in R1.

L     R1,PARLIST_FOR_FUBAR

The called function now can move it wherever needed or address the parameters relative to R1.

Much like the stack frame itself, the parameter list was free form. If it was dynamically build, one would usually reserve some stack space (local variable) to hold it. If static, it could as well be located in some constant area (unless it includes a return value). Or as a combination of both - having a preformatted list in a constant area and move it over to the stack when needed and modified before calling

Not relying on a push/pop mechanic offered a lot more flexibility and performance. In many function calls several, or maybe even all parameters are constant. With preformatted parameter blocks, only real variable parameters need to be stored at their position, reducing the amount of needed instructions thus runtime. The most high performance instruction is still one that doesn't get executed at all :))

If the function was supposed to give a return code, this had to end in R15 of the caller - which was simply done by storing the return code into the save location of R15 within the SAVEAREA. It's like having an automatic declared local return code variable that can be manupulated thruout the function and will be automatic loaded on return without any additional space requirement or runtime cost :=)

---

Remarks:

In real programming the assembly programmer never touched these instructions, as all was covered in macros. A program's structure looked more like this:

@ENTR TYPE=M,NAME=MAIN
...
@PASS NAME=FUBAR,PLIST=(FCB,RECORD)
@IF   NE
LTR   R15,R15         * Return Code Not Zero?
@THEN
@EXIT RC=#UNSATISFIED * Finish Program with Return Code UNSATISFIED
@BEND
...
@EXIT RC=#HAPPYENDING * Finish Program with Return Code HAPPYENDING
@END


@ENTR TYPE=L,NAME=FUBAR,PLIST=(FCB,RECORD)
...
(do whatever needed with FCB and RECORD)
...
@EXIT RC=0            * Finish Function with Return Code Zero
@END

And yes, that's assembly language - real one that is :)))

---

*1 - First named ZMMD on a Zuse Z22 in 1958

*2 - Back then called Kellerspeicher, which may be literally translated as basement-storage. I always guess an American would have called it rather attic-storage as they fill the same niche in the US, where basements are way less common.

*3 - Meaning the same subroutine can be called more than once without prior exiting it.

*4 - With only static variables and non-reentrant calling conventions it is possible to come up with calling conventions using static memory. Here each subroutine gets its own memory to save registers and handle local variables - usually as part of the program memory, right after the code. Which is how FORTRAN or COBOL started out, before quite early switching for stack usage.

*5 - Around 1980 Siemens implemented two different sets of stack instructions in their /370 compatible mainframes (X-CPU). Nothing like a simple wordwise PUSH/PULL and one of them more like hardware implementations of linked list.

*6 - As comments by James Large and T.E.D. have underlined, the situation is a bit more complex, especially with FORTRAN. Recursion and thus reentrant enabled functions and non static local variables (i.e.on a stack) where not part of the language definition until FORTRAN 90 came along. In fact, many programs did rely on function variables to be static between calls. FORTRAN further issued a compile time error if a function was called within itself.

But even before FORTRAN 90 there were compilers that did allow recursion and dynamic allocated variable space. Just not as standard.

Then again, at least since FORTRAN 77, recursion was possible by using function pointers. Here the compiler couldn't check the calling tree and no run time checks did hinder the usage. I have a bookmark of a nice page describing how it was done and what a programmer had to keep in mind.

*7 - At least the ones that were to be overwritten.

*8 - There were others - after all, software is ... well ... soft and allows many ways of implementation.

*9 - At least. Aligning to doublewords of better was standard - and there's a nice story how alignment here did improve performance in a macroscopic way - but that's a different story.

*10 - Depending on the configuration another 32 bytes were reserved for debugging information. In this case the entry consisted of a runtime call where frame information was checked, the new frame was build and debug information like the name of the called function was stored in the additional fields. Having function names as readable EBCDIC at the begin of each stack frame was just great when reading a dump.

We had this feature enabled by default, as it also allows a function to return to some known caller within the calling sequence, bypassing all intermediate ones. Extremely handy in error handling. That way, one doesn't have to schlep some error from a function way down through all the whole calling sequence, with (more or less) specific error handling in each of them.

*11 - Well, BAL R15,FUBAR could as well, if FUBAR is within the address range of the current module. In everything but small demo programs it isn't.

*12 - That's simply one read protected page above and below the available stack page. Accessing this as in case of over- or underrun will result in an address violation which in turn can be handles by the runtime according to what is intended. Like extending the stack memory, or cancelling the program run, or whatsoever.

*13 - This implementation allows only a maximum stack size of 4 KiB minus 64 bytes. Which is natural as stack addressing based on the stack register can only address 4 KiB anyway. There are other implementations that allow more stack, but then again will also require more complex addressing. If a procedure needs that much memory it is more useful to get it from the heap anyway.

*14 - Like having R0 point to a FCB and R1 to a record buffer when doing a READ or WRITE call for a file.

*15 - There where support functions for building parameter lists from an argument list, but that doesn't change the basic workings, so let's skip that for simplicity.

Answer 2

I've seen three common approaches to handling that:

The first approach is to have the compiler statically allocate an area of memory for use as a stack, and maintain a global pointer to the current "stack pointer". On a platform with a subroutine call/return stack that's too small to accommodate expected function nesting, something like:

int foo(int a, int b);
...
foo(1,2);
...
void bar(int);
int foo(int a, int b);
{
  int temp=a+b;
  a>>=1;
  bar(a);
  bar(temp);
}

may be handled, absent optimization as:

    *compilerSP++ = 1; // Push first arg
    *compilerSP++ = 2; // Push second arg
    CALL _foo   // Stores return address in a special register
    compilerSP -= 2; // Remove pushed args
    ...
_foo:
    *compilerSP++ = RETURN_ADDR;  // Get called function
    compilerSP++; // Reserve space for temp
    compilerSP[-1] = compilerSP[-4]+compilerSP[-3]; // temp = a+b
    compilerSP[-4] >>+ 1; // a>>=1;
    *compilerSP++ = compilerSP[-4]; // Push a
    call _bar
    compilerSP--; // Remove pushed arg
    *compilerSP++ = compilerSP[-1]; // Push temp
    call _bar
    compilerSP--; // Remove pushed arg
    compilerSP--; // Remove space for temp
    RETURN_ADDR = *++compilerSP;
    RETURN;

Performance of this approach is generally pretty bad, but it will support recursion and re-entrant functions without difficulty.

A second approach which is not conforming but is generally more useful is to forbid recursion, compute what the worst-case stack usage would be for each function, and then have the linker statically allocate space for all arguments, local variables, and any temporary variables the compiler needed to make things work. Beyond the fact that such an approach greatly improves performance on systems without stacks, it has a second major advantage even for systems with stacks - such a great advantage, in fact, that I think the Standard should have recognized a subset of C without recursion. If recursion is disallowed, programs can be statically guaranteed never to have any kind of "stack overflow" at run-time. If the linker can't produce a static allocation that's guaranteed to work, it will reject program at link time without it running at all. Although some kinds of program need support for recursion and re-entrancy, waiving such support would allow implementations for safety-critical systems to guarantee that combination of inputs could bomb the stack--something that would be useful even on systems that use stacks.

A third approach which is conforming, but still performs better than the first, is to statically allocate space for local variables and arguments whose address isn't taken, but also keep for each function a flag to indicate its level of nested invocations. If the function is being invoked when it is called again, the second invocation should copy all of its associated automatic objects to a compiler-maintained "pseudo-stack" like the one used in the first approach before allowing it to be invoked recursively (variables whose address is taken would need to be allocated on the pseudo-stack whether code is invoked recursively or not). When a function returns after having been invoked recursively, it should restore all saved automatic objects from that pseudo-stack. This approach, unlike the second, conforms to the Standard, but will run slower because of the need to check whether functions are being invoked recursively. Although I've used a compiler (Archimedes V4) that could be configured to employ this approach, I've never enabled it since it adds extra overhead to all code whether or not it uses recursion. The overhead isn't as severe as with the first approach, but unless an application needs recursion, there's no reason to accept any overhead.

Answer 3

Funny enough, some contemporary architectures, like ARMv4 do not have a hardware stack either. Any subroutine call/return is done through the link register that temporarily holds the return address.

However, what would be called a 'software stack' is still present: some other register is assigned the role of stack pointer: you save the link register where it points as soon as the subroutine is entered, you push and pop registers there through the use of multi-register moves that also pre- or post- increment or decrement register used as a stack pointer (however those instructions use equally any other register as a pointer).

Also worth noting is that a 'hardware stack' has also the meaning of a truly hardware, limited-size stack (made of shift registers or small memory block) that is used nowadays in 'big' CPUs as the predictor of the return address within the speculative execution framework.

Answer 4

On very early computers there was no hardware support for a stack, because it was not until they started to program it that they realised that they needed one. The solution was the Wheeler jump — invented by David Wheeler.

The Wheeler jump

This involves modifying the program as it runs. So will work on a Von Neumann architecture, but not Harvard. (Harvard came later, and will always have mechanism to implement a stack).

Before a subroutine is jumped to (branch/goto, type jump), the last instruction of the routine that is called is changed to a branch to the next instruction. This last instruction was left blank, for this use. The programmer, or loading tools, need to know the length of the routine that is called. It is a big pain.

Recursion is impossible, because there is only one place (per routine) where the return address is stored. However it is possible to have a subroutine, call as subroutine, call a subroutine. This is all that most programmers do anyway, and most recursion can be replaced by iteration.

---

This answer is about earlier times, than those mentioned in the question, because it gives some context, and shows what can be done, in relation to the question, with poor hardware support.

Answer 5

A program stack is a very simple data structure that requires only

• indexed or indirect memory addressing (pointers)
• indirect or computed jumps
• a designated register or global variable holding the stack pointer/index
• basic arithmetic, i.e. increment and decrement operations
  
  
  
• Pushing a value means decrement the index, then store.
• Popping is loading a value at the index, then increment the index.

(Of course one can swap decrement and increment to have an upward growing stack)

• Calling a subroutine is pushing the return address (program counter plus some offset). If there is no other way to access the PC, the compiler could emit a direct register load followed by a push, and the linker can fix up the loaded value with the return address.
• Returning from a subroutine is popping the return address from the stack, and jump to it.

Modern processors tend to implement these operations in single instructions simply because they are often used together, and doing so would save code space and speed up execution.

Answer 6

The 6502 has only a stack of 256 bytes, so cc65 implements a stack in software.

Answer 7

Even nasty recursive stuff can be converted to iteration. For example, take a look at this:

• Reflection and refraction impossible without recursive ray tracing?

Which does exactly that on a platform where recursion is not allowed probably due to the same reasons you are asking about (not sure if a GPU have stack pointer or not).

Anyway, if a computer has memory access with variable addressing (like by register) then you can implement a stack on your own. It is easy, just a few lines of code ... For example, you can do basic stack emulation stuff in Z80 assembly like this:

StackPtr: dw 0

push_a:
 ld hl,(StackPtr)
 dec hl
 ld (StackPtr),hl
 ld (hl),a

pop_a:
 ld hl,(StackPtr)
 ld a,(hl)
 inc hl
 ld (StackPtr),hl

If you do not have addressing by register then you need to do it by self-modifying code where you overwrite the memory access instruction address on a fixed memory position which is then used ... The same goes for call,ret jumping.

Ackermann function

As I mentioned before, even nasty recursive stuff can be converted to an iterative process. Here for example, the Ackermann function in C++:

//---------------------------------------------------------------------------
// https://en.wikipedia.org/wiki/Ackermann_function
//---------------------------------------------------------------------------
DWORD ackermann_r(DWORD m,DWORD n)
    {
    if (!m) return n+1;
    if (!n) return ackermann_r(m-1,DWORD(1));
            return ackermann_r(m-1,ackermann_r(m,n-1));
    }
//---------------------------------------------------------------------------
DWORD ackermann_i(DWORD m,DWORD n)
    {
    const int sz=128;               // stack size
    int i=0;                        // stack pointer
    DWORD a[sz];                        // stack
    for (;;)
        {
        if (!m)
            {
            n++;
            if (!i) return n;       // final result
            i--; m=a[i];            // previous recursion level
            continue;
            }
        if (!n) { m--; n=1; continue; }
        if (i>=sz) return 0;        // recursion too deep
        a[i]=m-1; i++;              // new recursion level
        n--;
        }
    }
//---------------------------------------------------------------------------

The _r means recursive and _i means iterative. Of course, without bignum arithmetics we are limited to very small m, n input here comparison of the two functions:

[recursive Ackermann(m,n)]
  m\n      0      1      2      3      4 
    0      1      2      3      4      5 
    1      2      3      4      5      6 
    2      3      5      7      9     11 
    3      5     13     29     61    125 

[iterative Ackermann(m,n)]
  m\n      0      1      2      3      4 
    0      1      2      3      4      5 
    1      2      3      4      5      6 
    2      3      5      7      9     11 
    3      5     13     29     61    125 

The DWORD is an unsigned 32 bit integer... As you can see, I am using my own stack/heap implementation inside the iterative function (but that does not make it recursive!!!) nor is it using stack-related instructions, just memory access ...

The drawback is that you are limited with heap/stack size (this stuff grows really fast), but if you realize you can have a global heap/stack for all the functions even this limitation partially disappears ... But do not befouled; even recursion is limited in the same way as the stack/heap of a commonly compiled program is usually limited too...

Another option is to compute/estimate the needed stack size for example by some series) and use dynamic allocation ... It's also doable without the estimation if we use a dynamic-linked list instead...

While testing, beware this stuff grows crazy. For example:

ackermann_i(4,1) = 65533

took 9.550399 seconds to compute and used sz=65531 DWORDs (while the recursive version stack overflowed already as iterative functions usually need less space than their recursive counterparts).

Answer 8

Firstly the PDP-7 had autoincrement capability for some of its memory registers (addressing was direct or memory indirect); the PDP-11 also has autoincrement registers. Note that many CPUs of that era did not have a stack for subroutine calls but instead used a "frame pointer", saving the old PC as an index to the calling routine's parameter data. Second, hardware features can be implemented in software, both in the original Assembly language version of Unix as well as Unix written in the C language. The Unix clone, Minix, was written for the i8086 originally and has a software Virtual Memory Manager (most newer CPUs have a hardware one). PDP-7 instruction set: http://simh.trailing-edge.com/docs/architecture18b.pdf

Answer 9

Looking at the manual for PDP-7 (1964), it has:

• Jump and copy program counter to accumulator (jsp)
• It also has memory indirect addresses, dac i deposit indirect, lac i load indirect.
• With up to 8 of these being auto incrementing (depending on memory size).

These last two can be used to implement a stack.

The first uses the accumulator as a link register (the arm has a dedicated link register). The link register (accumulator) can be copied to/from the stack.

Answer 10

There is no such thing as a "hardware stack"; what you're calling a hardware stack is presumably just push/pop (and possibly call/ret) instructions that operate on a specific fixed register and memory addressed by it.

Unlike some other answers claim, no "dynamic memory management" is needed in the absence of such instructions. You just do the same thing you always do to implement call frames with a moving stack pointer, choosing a particular register for use as the stack pointer (at least at call time; if you need to support interrupts/asynchronous events, it probably has to be permentantly-reserved rather than just at call time. Then you just increment/decrement it and store/load at addresses based on it just like you would with a register that the ISA specifically designates as a "stack pointer".