Machine Language - Procedures & Recursion

Class: CSCE-312

Notes:

Caller-Saved Example

C code:

long compute(long a, long b)
	long c = a + 5;
	long d = mul(c, b);  // external function
	return d - a;

Assembly code (unsafe):

compute:
	movq %rdi, %rax   # copy a -> %rax
	addq $5, %rax     # c = a + 5
	movq %rax, %rdi   # ...
	movq %rsi, %rsi
	call mul
	subq %rdi, %rax
	ret

• Note whatever comes out of the mul function is inside %rax

Safe option:

compute_safe:
	pushq %rdi        # save 'a'
	movq %rdi, %rax
	addq $5, %rax
	movq %rax, %rdi
	call mul
	popq %rdi         # restore 'a'
	subq %rdi, %rax
	ret

• Push pushes this value of rdi into the stack
• pop just pops the top of the stack which was rdi and stores it into this register.
• It is always best to do this.

Callee-Saved Register

C code:

long calc_sum(long x) {
	long base = 100;
	long y = addn(&base, 2000);
	return y - x;
}

Assembly code:

# long calc_sum(long x)
calc_sum:
	pushq %rbx          # save callee-saved register
	subq $16, %rsp      # allocate 16 bytes for locals (make stack frame)
	movq %rdi, %rbx     # save x in %rbx
	movq $100, 8(%rsp)  # base = 100
	movq $2000, %esi    # 2nd arg: 2000
	leaq 8(%rsp), %rdi  # 1st arg: &base
	call addn           # addn(&base, 2000)
	subq %rbx, %rax     # y - x
	addq $16, %rsp      # deallocate locals
	popq %rbx           # restore callee-saved reg
	ret

• Note: movq $100, 8(%rsp)
  • Is saving 100 inside the stack, not inside of any of our registers
  • Why do you need to put this in memory?
    • Because in the future we want to access the address of this value
    • Basically we are using a reference
      • Whenever you have & you need an address
  • 8 + (stack pointer)
    • Storing 100 in 8 + (stack pointer)
    • Technically pushing into your stack frame
• Whenever you are working with the half of that size you need to use movl
• leaq 8(%rsp), %rdi
  • Load effective address inside %rdi
  • We are calculating that address:
    • That address is stored at the address of %rsp + 8
  • If you want the value of that address you need to use ().
• %rax is the return value register, this is wehre the result will be stored at.
• Why 16 bytes specifically?
  • This is just kind of a rule
  • Avoid internal fragmentation that using 8 bytes has.
  • 1 stack frame is just 16 bytes
    • In some machines it is 8 bytes.

Recursive Function Example

C code:

long fcat(long n) {
	if (n <= 1)
		return 1;
	else
		return n * fact(n - 1);
}

Assembly code:

# long fact(long n)
fact:
	movl $1, %eax        # base return value = 1
	cmpq $1, %rdi        # compare n wiht 1
	jle .Lbase           # if n <= , jump to base case
	
	pushq %rbx           # save callee-saved register
	movq %rdi, %rbx      # store n in %rbx
	subq $1, %rdi        # prepare argument(n - 1)
	call fact            # recursive call fact(n - 1)
	imulq %rbx, %rax     # multiply result * n
	popq %rbx            # restore %rbx
	ret
	
.Lbase:
	ret

• We need to store n somewhere, the register to do this will be %rbx
• Every call to fact will allocate its own stack frame on top.