Machine-Level Programming III - Procedures

Class: CSCE-312

Notes:

Mechanisms in Procedures

• Passing control
  • To beginning of procedure code
  • Back to return point
• Passing data
  • Procedure arguments
  • Return value
• Memory management
  • Allocate during procedure execution
  • Deallocate upon return
  • We have local variables, we use then, and when we leave we want to delete them because if we dont't we eventually run out of memory
• Mechanisms all implemented with machine instructions
• x86-64 implementation of a procedure uses only those mechanisms required

Today

• Procedures
  • Stack Structure
  • Calling Conventions
    • Passing control
    • Passing data
    • Managing local data
  • Illustration of Recursion

Stack Structure

x86-64 Stack

• Region of memory managed with stack discipline

• Grows toward lower addresses

• Register %rsp contains 
lowest stack

  • address of “top” element
  • Always point to the element on top of the stack

• The bottom of the stack is a high address
• The top of the stack is a low address
  • We do not normally as the lowest being the top, but that is the way it is here.

x86-64 Stack: Push

• pushq Src
  • Fetch operand at Src
  • Decrement %rsp by 8
    • After pushq, %rsp is 8 lower (grows down).
  • Write operand at address given by %rsp

x86-64 Stack: Pop

• popq Dest
  • Read value at address given by %rsp
  • Increment %rsp by 8
  • Store value at Dest (must be register)

Calling Conventions: Passing control

• Control is the use of the CPU
  • When we pass that control we have to make sure it is passed back
  • We also have to pass the address where we want to return

Code Examples:

• %rdx might change so we are going to store it in %rbx because it is a calling safe register.
• <mult2> does a return and then we pop that value off the stack so we can continue this procedure.
• Why do we use a stack as opposed to storing a return value somewhere and then jumping back to it?
  • How does this sound like? Sounds like recursion
  • If we want a procedure to be able to be called more than once in chain we need some kind of structure to remember each call.
  • Back in the days you needed to tell the compiler to let it now we want to use recursion in this function (specify as recursive).
  • Now we just use a stack to nativelly support recursion.

Procedure Control Flow

• Use stack to support procedure call and return

• Procedure call: call label

  • Push return address on stack
  • Jump to label
    • We do stuff and then pop that address off the stack.

• Return address:

  • Address of the next instruction right after call
  • Example from disassembly

• Procedure return: ret

  • Pop address from stack
  • Jump to address

Control Flow Example

• The call transfers control to 400550 and at the same time pushes to stack
• Now the top of the stack has the place to return

• Note: Other instruction sets have more support for instruction calls and others have less support for instruction calls.

Calling Conventions: Passing data

Registers:

• First 6 arguments
  • %rdi
  • %rsi
  • %rdx
  • %rcx
  • %r8
  • %r9
• Return value
  • %rax
• Note:
  • On arm instruction sets, all registers are r followed by some number

Stack:

• Only allocate stack space when needed
• If we have more than 6 arguments, the 7th argument is the next argument on the stack and so on.

Data Flow Examples

• Note: we use some other register for floats (these are special)
• Are floats or doubles turing complete?
  • Yes, there is nothing fundamental about them, they are just bits.
  • In the old days we had to emulate floating point sin software.

Calling Conventions: Managing local data

Stack-Based Languages

• Languages that support recursion
  • e.g., C, Pascal, Java
  • Pascal
    • Was designed as a teaching language
    • Not object-oriented
  • Java
    • Safer language, but maybe less performant than C/C++
    • Has garbage collector and other fancy data structures built-in.
  • Code must be “Reentrant”
    • Multiple simultaneous instantiations of single procedure
  • Need some place to store state of each instantiation
    • Arguments
    • Local variables
    • Return pointer
• Stack discipline
  • State for given procedure needed for limited time
    • From when called to when return
  • Callee returns before caller does
• Stack allocated in Frames
  • state for single procedure instantiation

Call Chain Example

Stack Frames

• Contents
  • Return information
  • Local storage (if needed)
  • Temporary space (if needed)
• Management
  • Space allocated when enter procedure
    • “Set-up” code
    • Includes push by call instruction
  • Deallocated when return
    • “Finish” code
    • Includes pop by ret instruction

Example

x86-64/Linux Stack Frame

• Current Stack Frame (“Top” to Bottom)

  • “Argument build:”
Parameters for function about to call
  • Local variables
If can’t keep in registers
  • Saved register context
  • Old frame pointer (optional)

• Caller Stack Frame

  • Return address
    • Pushed by call instruction
      • The call procedure builds the rest of the stack frame
  • Arguments for this call

Example: incr

C Code:

long incr(long *p, long val) {
    long x = *p;
    long y = x + val;
    *p = y;
    return x;
}

Assembly instructions:

incr:
  movq    (%rdi), %rax
  addq    %rax, %rsi
  movq    %rsi, (%rdi)
  ret

Example: Calling incr #1

Example: Calling incr #2

Example: Calling incr #3

Example: Calling incr #4

Example: Calling incr #5

Register Saving Conventions

• When procedure yoo calls who:

  • yoo is the caller
  • who is the callee
    • Receives the call (it is being called)

• Can register be used for temporary storage?

  

  • Is it the same rdx as before?
    • NO, that expectation is wrong, the contents of rdx were changed by who to something else

• Contents of register %rdx overwritten by who

• This could be trouble ➙ something should be done!

  • Need some coordination

• Conventions

  • “Caller Saved”
    • Caller saves temporary values in its frame before the call
  • “Callee Saved”
    • Callee saves temporary values in its frame before using
    • Callee restores them before returning to caller

x86-64 Linux Register Usage #1

• %rax
  • Return value
  • Also caller-saved
    • I want the value of rax to stay the same after the call of a function.
  • Can be modified by procedure
• %rdi, ..., %r9
  • They are arguments
  • Also caller-saved
    • If we are just using it as a general purpose register we should be prepared to expect a register value being changed, so we need to restore it.
  • Can be modified by procedure
• %r10, %r11
  • Caller-saved
  • Can be modified by procedure

x86-64 Linux Register Usage #2

• %rbx, %r12, %r13, %r14
  • Callee-saved
    • Have to be saved by the callee procedure
    • When the procedure comes back we can expect rbx to be the same.
  • Callee must save & restore
• %rbp
  • Callee-saved
  • Callee must save & restore
  • May be used as frame pointer
    • Makes some aspects of programmer easier, but you do not necessarily need to use it as a frame pointer.
  • Can mix & match
• %rsp
  • Special form of callee save
    • When you call a function with a certain value of %rsp, when you return it better be the same value of %rsp but we are using arithmetic and make sure that whenever we come back it is the same
    • Automatically changes %rsp
    • Basically saving the value by incrementing it and decrementing it just the right way
  • Restored to original value upon exit from procedure

Callee-Saved Example #1

• Initially rsp points to the return address
• Remember rbx is a callee-saved register
  • %rdi is subject to change, but %rbx is not.
  • When we come back from a call we can be confident that rbx is the same value as before.
  • This is why we make this move: movq %rdi, %rbx
• sub1 $16, %rsp is reducing the stack pointer by 16, it is setting up the stack frame.
• movq $15213, 8(%rsp) is saying: move 15213 into the address 8 + (stack pointer)
  • Why can't we just represent long v1 with a register like %rcx?
    • A long fits nicely within a 64-bit register.
    • Here instead you can see the compiler is treating memory as v1
    • 8(%rsp) is memory, we are treating memory as the place to store v1, why don't we use a register for that purpose?
    • Here &v1 (address of) operator, an address is a pointer to something in memory
    • We can't keep v1 in a register because we need to take its address, this is why the compiler sets up to be memory location instead of a register.
      • If you wan't your variables to be in register (for more speed) then do not take their address.
• leaq 8(%rsp), %rdi is saying: take the address of v1 and put it into %rdi
  • Remember %rdi is our first parameter (x).
  • Note %esi is %rsi
    • When you modify %esi is like doing the same thing to %rsi
    • %rsi is just the 64-bit version of it.
  • Note the compiler is first setting the second parameter (%rsi) and then then first one (%rdi)
    • It probably doesn't matter at all, there is probably no advantage either way, so it probably chose one
    • Maybe the compiler may know that this change would improve some kind of probability of execution of other instructions and stuff like that
• v2 is returned by incr
  • When we call incr, %rbx won't be changed (is callee-saved)
  • At this point x is represented by %rbx
• addq %rbx, %rax
  • Adding x to v2.
• addq $16, %rsp
  • Go back to the alignment of the stack right after the call

Callee-Saved Example #2

Illustration of Recursion

Recursive Function

C code:

/* Recursive popcount */
long pcount_r(unsigned long x) {
  if (x == 0)
    return 0;
  else
    return (x & 1) 
           + pcount_r(x >> 1);
}

• Defining something in terms of itself, this doesn't normally feel natural
• Counts the number of 1s bits in a long.
  • How many 1s bits are in x?
• Base case:
  • If there is no 1 in x, then return 0.
• Recursive call:
  • Return an integer that has potentially one less 1s bit.
  • Until we reach the point where we have shifted all the bits right, and there are no 1s anymore.

Assembly code:

pcount_r:
  movl    $0, %eax
  testq   %rdi, %rdi
  je      .L6
  pushq   %rbx
  movq    %rdi, %rbx
  andl    $1, %ebx
  shrq    %rdi         # (by 1)
  call    pcount_r
  addq    %rbx, %rax
  popq    %rbx
.L6:
  rep; ret

• The return value is a long but here we are treating it as a 32-bit int, it is just efficient in this case.
• Base case: returns if x is 0
  • Otherwise pushq %rbx
  • We are going to do something with rbx, so we have to push it so that we can restore it at the end.
• rbx is really remembering this (x & 1)
• It is important to push and pop rbx because we have used it all over the place, we need to restore it.

Recursive Function Terminal Case

Recursive Function Register Save

Recursive Function Call Setup

Recursive Function Call

Recursive Function Result

Recursive Function Completion

Observations About Recursion

• Handled Without Special Consideration
  • Stack frames mean that each function call has private storage
    • Saved registers & local variables
    • Saved return pointer
  • Register saving conventions prevent one function call from corrupting another’s data
    • Unless the C code explicitly does so (e.g., buffer overflow in Lecture 9)
  • Stack discipline follows call / return pattern
    • If P calls Q, then Q returns before P
    • Last-In, First-Out
• Also works for mutual recursion
  • P calls Q; Q calls P
    • Everything works out by using the stack and using calle and caller-saved registers

x86-64 Procedure Summary

• Important Points
  • Stack is the right data structure for procedure call / return
    • If P calls Q, then Q returns before P
• Recursion (& mutual recursion) handled by normal calling conventions
  • Can safely store values in local stack frame and in callee-saved registers
  • Put function arguments at top of stack
  • Result return in %rax
• Pointers are addresses of values
  • On stack or global