Recursion in machine-level

Recursive function 예제 코드

// recursive function in C
long pcount_r(unsigned long x)
{
	if (x==0) return 0;
    else return (x&1) + pcount_r(x >> 1)
}

// recursive function in Assembly
pcount_r:
	movl $0, %eax
    testq %rdi, %rdi
    je .L6
    pushq %rbx
    movq %rdi, %rbx
    andl $1, %ebx
    shrq %rdi
    call pcount_r
    addq %rbx, %rax
    popq %rbx
.L6:
	rep; ret

종료 조건

pcount_r:
	movl $0, %eax
    testq %rdi, %rdi
    je .L6
    .
    .
    .
.L6:
	rep; ret

Register	Use(s)	Type
%rdi	x	Argument
%rax	Return value	Return value

Register 백업

// recursive function in Assembly
pcount_r:
	.
    .
    .
    pushq %rbx
    .
    .
    .
.L6:
	rep; ret

pushq %rbx: %rsp에 %rbx값 저장

Register	Use(s)	Type
%rdi	x	Argument

Function call 준비

// recursive function in Assembly
pcount_r:
    .
    .
    .
    movq %rdi, %rbx
    andl $1, %ebx
    shrq %rdi
    call pcount_r
    addq %rbx, %rax
    popq %rbx
.L6:
	rep; ret

movq %rdi, %rbx: %rbx에 x 복사
andl $1, %ebx: %rbx 하위 1바이트 & 1 연산
shrq %rdi: x >> 1

Register	Use(s)	Type
%rdi	x >> 1	Argument
%rbx	x & 1	Callee-saved

Function call

// recursive function in Assembly
pcount_r:
	.
    .
    .
    call pcount_r
    addq %rbx, %rax
    popq %rbx
.L6:
	rep; ret

call pcount_r: 재귀호출

Register	Use(s)	Type
%rbx	x & 1	Callee-saved
%rax	재귀호출 리턴값

Recursive Function call
$\rarr$ terminal case 나올 때 까지 계속 실행함.
내부적으로 계속 stack에 %rbx 백업하고 %rdi랑 레지스터들 돌려씀.
귀찮아서 급하게 말로만 설명하는게 아님.

Recursive Function return

// recursive function in Assembly
pcount_r:
    .
    .
    .
    addq %rbx, %rax
    popq %rbx
.L6:
	rep; ret

add %rbx, %rax: return value에 %rbx 값 더함
popq %rbx: stack에서 백업해둔 %rbx값 반환

이 짓도 호출한 거 다 리턴할 때 까지 반복함.

---

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
안성용, "시스템소프트웨어", 부산대학교