Subroutine and procedure call support

Mark Smotherman
Last updated: March 2004

Summary: TBD

.. portions under construction ..

Early history

Linkage considerations

Depending on language and architecture, registers may hold:

- uplevel addressing link
- exception handler pointer (for Ada)
- frame pointer
- program counter
- stack pointer
- actual parameters 
- return values
- constant pool pointer
- spare space for called routines to trash
- registers reserved for link-time-generated code to use
(list from Don Lindsay usenet post)

Memory-based linkages

Early subroutine linkages stored the return address in memory, e.g., as the first word of subroutine.

Example linkages

Other systems with memory-based linkage include the EDSAC (using the Wheeler jump), (check Ferranti Mark 1 / Atlas used extracodes for subroutine calls), Univac I, Bull Gamma 60, IBM Stretch, CDC 160 and 6600 PPU, and Univac 1103A.

Register-based linkages

The IBM 704 appears to be the first computer to store the return address in a register. This approach, popular for many years because of the in-line passing of parameters, fell out of favor when memory stack linkages became popular in the 1970s. It then regained favor when RISC architects wanted to avoid traffic to a memory stack on each call and return.

Example linkages

The Cray-1 also used a register-based linkage.

Stack-based linkages

... store return address in a memory stack ...

Typical procedure support in 1970s

   dedicated registers

        sp - stack pointer, top of stack
        fp - frame pointer, anchors the stack frame for this subroutine
           invocation (will not change as things are pushed onto the stack)

   memory stack frame (subroutine call activation record)

            | / / / / / /|
      sp -->|    ...     |
            |   locals   |  fp-c is usually an address of a local variable
            |    ...     |
      fp -->|   old fp   |
            | saved regs |
            |  rtn addr  |
            |    ...     |
            | parameters |  fp+k is usually an address of a parameter
            |    ...     |
            | / / / / / /|

   calling program

        push parameter2 on stack       ! typically done in reverse order
        push parameter1 on stack
        call subroutine                ! pushes return address onto the stack
        clean parameters off stack     ! add constant to stack pointer after
                                       !    return

   subroutine (callee save convention to save registers)

        /* prologue */
           push registers to save
           push old fp
           set new fp as current sp
           subtract from sp to make room for locals

        /* body */
           ... body of subroutine, in which you access parameters with memory
               addresses fp+k and local vars with memory addresses fp-c ...

        /* epilogue */
           set sp to current fp
           pop fp
           pop registers to restore
           return                      ! pops return address from stack

S.C. Johnson and D.M. Ritchie, "The C Language Calling Sequence," Bell Labs, CS Tech. Rept. No. 102, September, 1981.

Example linkages - stack machines

Other stack machines include the ICL 2900 series and the HP-3000 (pcal and scal).

Example linkages - general-register machines

See also the Turing ACE.

Register-window-based linkages

... desire to reduce memory traffic ...

   SPARC designers wanted to eliminate as many memory accesses as possible

   memory-stack-based call requires at least four memory accesses
      1. the return address (pc) is pushed by the call instruction
      2. the old fp is pushed at the top of the subroutine
      3. the old fp is popped at the bottom of the subroutine, and
      4. the return address is popped by the return instruction

   then there are two memory accesses for each register saved (push to save
      and then pop to restore).

   the SPARC designers provided overlapped register windows instead

... design choices:
fixed size vs. variable size
overlapping vs. non-overlapping

Some folks see the idea of register windows in the scratchpad registers of the Fairchild F8 (you changed which of its 64 8-bit registers you could easily access by changing the contents of a 6-bit indirect scratchpad address register) and in the memory-mapped registers of the TI TMS-9900 (you changed the memory mapping of its 16 general registers by changing the contents of the workspace pointer register).

... also Pyramid 90x and Celerity C12000 ...

John Mashey's comments on register windows (Usenet posting to comp.arch)

Example linkages

Call-gate-based linkages

TO DO ... desire to provide different protection domains ...
Intel x86 call gates

Capability-based linkages

TO DO ... desire to provide different protection domains ...
M68020 callm and retm
Intel 432 call and call_thru_domain
Plessey 250, S/38 (AS/400), ...

Hank Levy's Capability-Based Computer Systems book


My thanks go to several folks who helped me understand the subroutine linkages on the described machines: John Ahlstrom, Bill Findlay, Jim Hull, and Doug Jones. (My apologies to these individuals for any misunderstandings on my part about the information they have shared with me; the errors in the descriptions are entirely mine.)

[History page] [Mark's homepage] [CPSC homepage] [Clemson Univ. homepage]