3.7.Procedure
\(3.7.\)Procedure
1.Procedure in A High Prospective
- Procedures are a key abstraction in software. They provide a way to package code that implements some functionality with a designated set of arguments and an optional return value.
Well-designed software uses procedures as an abstraction mechanism, hiding the detailed implementation of some action while providing a clear and concise interface definition of what values will be computed and what effects the procedure will have on the program state.
To provide machine-level support for procedures, we need to take the following aspect into consideration:
Passing control.
Passing data.
Allocating and deallocating memory.
2.The Run-time Stack
A program can manage the storage required by its procedures using a stack, where the stack and the program registers store the information required for passing control and data, and for allocating memory. As P calls Q, control and data information are added to the end of the stack. This information gets deallocated when P returns.
When an x86-64 procedure requires storage beyond what it can hold in registers, it allocates space on the stack. This region is referred to as the procedure's stack frame.
- When procedure P calls procedure Q, it will push the return address onto the stack, indicating where within P the program should resume execution once Q returns. We consider the return address to be part of P's stack frame, since it holds state relevant to P.
The stack frames for most procedures are of fixed size, allocated at the beginning of the procedure. Some procedures, however, require variable-size frames.
3.Control Transfer
Passing control from function P to function Q involves simply setting the program counter (PC) to the starting address of the code for Q. This information is recorded in x86-64 machines by invoking procedure Q with the instruction
call Q
.- This instruction pushes an address A onto the stack and sets the PC to the beginning of Q. The pushed address A is referred to as the return address and is computed as the address of the instruction immediately following the call instruction.
The general forms of the call
and ret
instructions are as below:
4.Data Transfer
In x86-64, data passing to and from a procedure takes place via registers.
Up to six integral (i.e., integer and pointer) arguments can be passed via registers. The registers are used in a specified order:
Arguments are allocated to these registers according to their ordering in the argument list, and arguments smaller than 64 bits can be accessed using the appropriate subsection of the 64-bit register.
When a function has more than six integral arguments, the other ones are passed on the stack. When passing parameters on the stack, all data size are rounded up to be multiples of 8.
Let's take the following code as an example:
1 | # void proc(a1, a1p, a2, a2p, a3, a3p, a4, a4p) |
5.Local Storage on the Stack
In most cases, local data is stored in registers. However, there are cases that local data must be stored in memory:
There are not enough registers to hold all of the local data.
The address operator '&' is applied to a local variable, and hence we must be able to generate an address for it. However, data that is stored in register doesn't have unique address.
Some of the local variables are arrays or structures and hence must be accessed by array or structure references.
Take the following program as an example:
1 | long swap_add(long *xp, long *yp) |
1 | # long caller() |
Because we need to use the address of arg1
and
arg2
, we need to store them in memory. We do this by
leaving enough place in the stack and push the arguments onto the
stack:
1 | subq $16, %rsp # Allocate 16 bytes for stack frame |
Once we need to use the value, we fetch it from the stacK:
1 | leaq 8(%rsp), %rsi # Compute &arg2 as second argument |
The following program is a more complicated one. It includes the details of setting up the stack frame for the local variables and function parameters:
1 | call_proc: |
6.Local Storage in Registers
When calling another procedure, we must make sure that the callee does not overwrite some register value that the caller planned to use later.
By convention, registers
%rbx
,%rbp
, and%r12�C%r15
are classified as callee saved registers.- When procedure P calls procedure Q, Q must preserve the values of these registers, ensuring that they have the same values when Q returns to P as they did when Q was called.
Procedure Q can preserve a register value by either not changing it at all or by pushing the original value on the stack, altering it, and then popping the old value from the stack before returning.
1 | pushq %rbp # Save %rbp |
Note how they are popped is in the reverse order from how they were pushed, to account for the last-in, first-out discipline of a stack.
- All other registers, except for the stack pointer
%rsp
, are classified as caller saved registers.
7.Recursive Procedures
The stack discipline of allocation and deallocation naturally matches the call-return ordering of functions. So the recursive procedures is the same as other procedures:
1 | long rfact(long n) |
1 | rfact: |