\(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:

1. Passing control.

2. Passing data.

3. 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:

# void proc(a1, a1p, a2, a2p, a3, a3p, a4, a4p)
# Arguments passed as follows:
# a1 in %rdi (64 bits)
# a1p in %rsi (64 bits)
# a2 in %edx (32 bits)
# a2p in %rcx (64 bits)
# a3 in %r8w (16 bits)
# a3p in %r9 (64 bits)
# a4 at %rsp+8 ( 8 bits)
# a4p at %rsp+16 (64 bits)

proc:
    movq 16(%rsp), %rax # Fetch a4p (64 bits)
    addq %rdi, (%rsi)   # *a1p += a1 (64 bits)
    addl %edx, (%rcx)   # *a2p += a2 (32 bits)
    addw %r8w, (%r9)    # *a3p += a3 (16 bits)
    movl 8(%rsp), %edx  # Fetch a4 (8 bits)
    addb %dl, (%rax)    # *a4p += a4 (8 bits)
    ret                 # Return

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:

1. There are not enough registers to hold all of the local data.

2. 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.

3. 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:

long swap_add(long *xp, long *yp)
{
    long x = *xp;
    long y = *yp;
    *xp = y;
    *yp = x;
    return x + y;
}

long caller()
{
    long arg1 = 534;
    long arg2 = 1057;
    long sum = swap_add(&arg1, &arg2);
    long diff = arg1 - arg2;
    return sum * diff;
}

# long caller()
caller:
subq $16, %rsp       # Allocate 16 bytes for stack frame
movq $534, (%rsp)    # Store 534 in arg1
movq $1057, 8(%rsp)  # Store 1057 in arg2
leaq 8(%rsp), %rsi   # Compute &arg2 as second argument
movq %rsp, %rdi      # Compute &arg1 as first argument
call swap_add        # Call swap_add(&arg1, &arg2)
movq (%rsp), %rdx    # Get arg1
subq 8(%rsp), %rdx   # Compute diff = arg1 - arg2
imulq %rdx, %rax     # Compute sum * diff
addq $16, %rsp       # Deallocate stack frame
ret                  # Return

  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:

subq $16, %rsp       # Allocate 16 bytes for stack frame
movq $534, (%rsp)    # Store 534 in arg1
movq $1057, 8(%rsp)  # Store 1057 in arg2

  Once we need to use the value, we fetch it from the stacK:

leaq 8(%rsp), %rsi   # Compute &arg2 as second argument
movq %rsp, %rdi      # Compute &arg1 as first 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:

call_proc:

    # set up arguments to proc
    subq $32, %rsp          # Allocate 32-byte stack frame
    movq $1, 24(%rsp)       # Store 1 in &x1
    movl $2, 20(%rsp)       # Store 2 in &x2
    movw $3, 18(%rsp)       # Store 3 in &x3
    movb $4, 17(%rsp)       # Store 4 in &x4
    leaq 17(%rsp), %rax     # Create &x4
    movq %rax, 8(%rsp)      # Store &x4 as argument 8
    movl $4, (%rsp)         # Store 4 as argument 7
    leaq 18(%rsp), %r9      # Pass &x3 as argument 6
    movl $3, %r8d           # Pass 3 as argument 5
    leaq 20(%rsp), %rcx     # Pass &x2 as argument 4
    movl $2, %edx           # Pass 2 as argument 3
    leaq 24(%rsp), %rsi     # Pass &x1 as argument 2
    movl $1, %edi           # Pass 1 as argument 1

    # call proc
    call proc               # Call proc

    # retrieve changes to memory
    movslq 20(%rsp), %rdx   # Get x2 and convert to long
    addq 24(%rsp), %rdx     # Compute x1+x2
    movswl 18(%rsp), %eax   # Get x3 and convert to int
    movsbl 17(%rsp), %ecx   # Get x4 and convert to int
    subl %ecx, %eax         # Compute x3-x4
    cltq                    # Convert to long
    imulq %rdx, %rax        # Compute (x1+x2) * (x3-x4)
    addq $32, %rsp          # Deallocate stack frame
    ret                     # Return

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.

pushq %rbp  # Save %rbp
pushq %rbx  # Save %rbx
...
popq %rbx   # Restore %rbx
popq %rbp   # Restore %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:

long rfact(long n)
{
    long result;
    if (n <= 1)
        result = 1;
    else
        result = n * rfact(n - 1);
    return result;
}

rfact:
    pushq %rbx              # Save %rbx
    movq %rdi, %rbx         # Store n in callee-saved register
    movl $1, %eax           # Set return value = 1
    cmpq $1, %rdi           # Compare n:1
    jle .L35                # If <=, goto done
    leaq -1(%rdi), %rdi     # Compute n-1
    call rfact              # Call rfact(n-1)
    imulq %rbx, %rax        # Multiply result by n
.L35: done:
    popq %rbx               # Restore %rbx
    ret                     # Return