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.
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
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.
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
The called function now can move it wherever needed or address the parameters relative to
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 :=)
In real programming the assembly programmer never touched these instructions, as all was covered in macros. A program's structure looked more like this:
LTR R15,R15 * Return Code Not Zero?
@EXIT RC=#UNSATISFIED * Finish Program with Return Code UNSATISFIED
@EXIT RC=#HAPPYENDING * Finish Program with Return Code HAPPYENDING
(do whatever needed with FCB and RECORD)
@EXIT RC=0 * Finish Function with Return Code Zero
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
R1 to a record buffer when doing a
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.