A call stack (also known as a control stack or run-time stack) is a data structure (a stack or stack) that is maintained in a computer’s memory during the execution of a program.
The call stack is used to store two types of data:
- Data used in the program, such as local variables.
- Administrative data necessary during the implementation of the program, such as the old contents of registers that are temporarily reused.
A program’s call stack is maintained by the program itself. The machine code responsible for this is generated by the compiler during compilation. The programmer who writes a program does not have to take this into account.
Some assembler statements manipulate the call stack explicitly (for example with POP and PUSH instructions) or implicitly (for example CALL and RET, which put the return address on the stack and take it off again).
Activation frames
The call stack (or stack for short) consists of activation frames (also called activation records or stack frames) of varying sizes. The stack contains an activation frame for each active instance of a subroutine (or function, or procedure). An active instance of a subroutine arises when the subroutine is called and ends when the subroutine ends. The subroutine, in turn, can call other subroutines. Since there may be more active instances of the same subroutine, for example in the case of recursion, the stack may have multiple activation frames associated with the same subroutine (but with different active instances of that subroutine).
Several active instances of subroutines are non-overlapping or nested. Two active subroutines are non-overlapping if they are not active at any one time. Two active subroutines ‘a’ and ‘b’ are nested, if ‘a’ becomes active before ‘b’ becomes active, ‘b’ ends earlier than ‘a’.
When a program starts, the stack is empty. Each time a subroutine is called, a new frame is placed on top of the stack. The frame that belongs to the most recently started subroutine is therefore always on top of the stack. When a subroutine ends, its frame is removed from the top of the stack. Now the frame of the calling subroutine, which now continues with its execution, is at the top of the stack. This works because subroutines are always non-overlapping or nested: the last started subroutine is always the first to finish, so its frame is always on top of the stack.
One or more special registers are present in the processor to access the stack and the current frame. How many these are and which they are varies per processor architecture, but usually a stack pointer and a frame pointer (also known as base pointer or local base pointer). The registers SP (stackpointer) and BP (basepointer) are available for this in the Intel x86 architecture. The stack pointer SP always points to the top of the stack (and is automatically increased or decreased by some machine instructions such as POP and PUSH). The frame pointer BP points to the beginning of the current activation frame. The current frame then always consists of the part of the stack that is between the address in SP (the top) and the address in BP.
Prologue, epilogue, context changes and stack pointers
When the compiler compiles a subroutine, it adds extra code at the beginning and at the end of the subroutine: a ‘prologue’ (or function prologue) at the beginning and an epilogue (or function epilogue) at the end of the routine. In addition, additional code is generated before and after each subroutine call. The code that is executed before a new subroutine becomes active is called the calling sequence and the code that is executed after the subroutine is finished is called the return sequence. Together, these four code fragments take care of all the administrative tasks that need to be performed when a new subroutine is called or a running routine is finished and the program returns to where it left off in the calling code.
The moment a new subroutine becomes active and the moment a subroutine is ready and the program returns to the calling code are called context changes. How the work is divided between the calling code (in the calling sequence and the returning sequence) and the invoked routine (in the prologue and the epilogue) differs per architecture and the programming language in which the program is written. In general, the following happens:
When a subroutine is called, the calling sequence in the calling code becomes active. This ensures:
- calculating the actual values of the parameters to be passed and putting them in the right place (on the stack or in registers),
- looking up the address of the code of the routine to be called,
- storing the content registers that are still in use,
- storing the address of the instruction where the program continues on return (the return address)
- and handing control to the subroutine by, for example, a CALL instruction.
The address of the subroutine code is now placed in the instruction register with which the called subroutine becomes active. This starts by performing the prologue, which
- save the current frame pointer value and point the new frame pointer to the top of the stack (which is now also the start of the new frame),
- and calculates the new value of the stack pointer and places it in the stack register with which the new frame is ready for use.
Now the subroutine itself becomes active. After this has done its work, the epilogue is then performed. This one
- put any return value in the right place (on the stack or in a register),
- copies the value of the frame pointer to the stack pointer and restores the old, saved, value of the frame pointer,
- gets the return address from the stack and puts it in the instruction pointer.
The calling code is now active again and the return sequence is executed. This one
- restores the old values of registers used and
- retrieves the return value for subsequent use.
Some processors have special instructions, which perform some of the work in the prologue and epilogue. For example, Intel processors have an ENTER and LEAVE instruction for the prologue and epilogue, respectively, and Motorola processors have the LINK and UNLK instructions for this.