[컴퓨터 구조] MIPS 아키텍쳐, 재귀함수 구현

 

MIPS 아키텍쳐의 어셈블리어를 사용해서 재귀함수를 구현해보겠습니다.

 

재귀 함수는 자기 자신을 호출하는 함수인데, 스택 메모리가 필요합니다. 스택 메모리는 함수가 호출될 때마다 연산에 필요한 매게 변수, caller의 address 등 필요한 데이터를 저장하는 임시 저장 메모리입니다. 스택 포인터를 직접 다뤄보면 재귀 함수가 실행될 때 스택 메모리가 어떻게 변하는지 이해할 수 있습니다.

 

예제를 살펴보기 전에, 함수를 구현하는 법과 jal instruction에 대해 먼저 알아보고 factorial 함수와 주어진 정수의 각 자리 수의 곱을 구하는 함수를 구현하겠습니다.

---

함수 구현과 jal instruction

...
	sum(a,b);
...
}

int sum (int x, int y) {
    return x + y;
}

합을 구하는 간단한 c언어 함수입니다. a는 s0, b는 s1에 저장돼있고, j sum 다음 명령어의 주소는 1016입니다.

main : 
    add $a0, $s0, $zero # x = a 
    add $a1, $s1, $zero # y = b
    addi $ra, $zero, 1016
    j sum
    
sum :
    add $v0, $a0, $a1
    jr $ra

 

j 는 sum으로 라벨링된 곳으로 이동하라는 명령어이고, jr는 ra에 저장된 곳으로 이동하라는 명령어입니다.

main함수에서 파라미터로 인자를 복사한 뒤에, sum을 호출하여 v0에 값을 저장하고, j sum의 다음 라인으로 이동합니다.

 

main : 
    add $a0, $s0, $zero # x = a 
    add $a1, $s1, $zero # y = b
    jal sum # save ret addr($ra=1012) & jump to sum
    
sum :
    add $v0, $a0, $a1
    jr $ra

 

program counter는 현재 명령어가 실행되는 메모리의 주소를 가지고 있는 레지스터입니다. jal 명령어는 라벨링된 주소로 PC를 이동시키고 (jump), PC + 4를 ra에 저장합니다 (link).

 

jal 명령어를 사용하면, 이 전의 addi, j 두 줄의 코드를 한 줄로 줄일 수 있고, 무엇보다 ra가 가르켜야할 위치를 명시적으로 적어줄 필요가 없습니다.

---

예제1) Factorial 함수 구현

아래 코드는 C언어로 작성된 재귀함수입니다.

int fact(int n)
{
    if (n < 1) return 1;
    return (n * fact(n-1));
}

 

아래는 위 코드를 변환한 어셈블리어입니다.

.data
input: .asciiz "input an integer: "

.text
.main:
	# prompt input
	li $v0, 4
	la $a0, input
	syscall
	
	# get input
	li $v0, 5
	syscall
	move $a0, $v0
	
	jal fact
	
	# print sum (stored in $a0)
	move $a0, $v0
	li $v0, 1
	syscall
	
	# exit program
	li $v0, 10
	syscall

fact:
	addi $sp, $sp, -8
	sw $ra, 4($sp)
	sw $a0, 0($sp)
	
	slti $t0, $a0, 1 	# test for n < 1
	beq $t0, $zero, L1 	# if n >= 1, go to L1
	
	# if n < 1
	addi $v0, $zero, 1
	addi $sp, $sp, 8	# pop 2 items off stack
	jr $ra			# return to caller
	
L1 :
	# if n >= 1
	addi $a0, $a0, -1	# argument gets (n-1)
	jal fact		# call fact(n-1)
	
	# where fact returns
	lw $a0, 0($sp)
	lw $ra, 4($sp)
	addi $sp, $sp, 8
	
	mul $v0, $a0, $v0
	jr $ra

Mars4_5에서 실행한 결과

 

테스트 결과 의도된대로 720을 출력하는 것을 확인할 수 있습니다.

 

n=3으로 입력하고 스택 메모리를 그려가며 단계별로 확인해보겠습니다.

 

 

 

.main에서 처음 jal fact를 만나면, fact:로 이동합니다.

스택 메모리에 8바이트를 할당합니다. 이 때 ra는 line 17을 가르키고 있고, a 레지스터에는 3이 저장돼있습니다.

스택 메모리에 값을 저장합니다. 현재 스택메모리 상태와, 레지스터 상태는 아래와 같습니다.

 

입력 파라미터 n이 0이 될때까지, fact가 호출되고  Line 33을 만날 때마다 L1으로 이동할 것입니다.

n = 0일 때, 스택 메모리에 a0와 ra를 저장한 직후

n = 0일 때, fact: 이후 스택 메모리에 a0와 ra를 저장한 직후입니다.

 

이번에는 a0에 저장된 값이 0이므로, L1으로 이동하는 것이 아니라, 순서대로 진행돼서 Line34로 이동합니다.

스택 메모리에 8바이트만큼 값을 제거하고 return 값인 v0에 1을 저장한 뒤 fact을 호출한 Line 44로 이동합니다.

 

$ra에 처음 fact를 호출한 Line17이 나올 때까지,

# where fact returns로 주석처리 된 Line45부터 Line51를 계속 반복해서

스택에서 값을 꺼내 v0에 곱해줍니다.

 

최초로 fact를 호출한 Line17로 이동합니다.

 

열심히 업데이트해준 v0를 출력하기 위해 a0로 이동시키고, 출력합니다.

그리고 프로그램을 종료합니다.

---

예제2) 주어진 정수의 각 자리수의 곱을 출력

int product(int n) {
    if (n / 10 == 0) return n;
    return (n % 10) * product(n / 10);
}

위 c언어 함수를 어셈블리어로 작성해보겠습니다.

 

.data
input: .asciiz "input an integer: "

.text
.main:
	# prompt input
	li $v0, 4
	la $a0, input
	syscall
	
	# get input
	li $v0, 5
	syscall
	move $a0, $v0
	
	li $s1, 10
	jal product
	
	# print sum (stored in $a0)
	move $a0, $v0
	li $v0, 1
	syscall
	
	# exit program
	li $v0, 10
	syscall
	
product:
	# store ra and modulo in stack
	addi $sp, $sp, -8
	sw $ra, 4($sp)

	div $a0, $s1
	mflo $t1
	mfhi $t2
	sw $t2, 0($sp)
	
	# 인자가 한 자리 수가 될때까지 재귀적으로 호출
	bne $t1, $zero, L1
	
	# 인자가 한 자리 수면 반환값을 t2로 지정
	add $v0, $t2, $zero
	
	# 스택을 해재하고  line 53으로 이동
	addi $sp, $sp, 8
	jr $ra

L1:
	# 호출한 재귀 함수의 인자를 변경하고 함수 호출
	add $a0, $t1, $zero
	jal product
	
	# 반환값에 스택에 저장한 나머지 값들을 계속 곱해줌
	lw $a0, 0($sp)
	lw $ra, 4($sp)
	addi $sp, $sp, 8
	mul $v0, $v0, $a0
	
	# 자리수별로 전부 곱할때까지 line 53으로 이동하고, 전부 계산하면 line 20으로 이동
	jr $ra

 

마찬가지로 종료조건이 나올때까지, 스택 메모리에 호출한 명령어의 주소와, n%10을 저장하고, n/10이 0인 조건이 충족되면 스택 메모리에서 마지막에 저장된 값부터 꺼내서 v0를 업데이트하는 것을 알 수 있습니다.

스택 메모리에 데이터를 push하고 pop할 때 대칭적으로 코드를 작성하는 것을 확인합시다. 

---

평소에 c나 java처럼 하이레벨로 재귀함수를 작성하지, 위처럼 어셈블리어로 재귀함수를 작성할 일은 없을 것 같습니다. 하지만, Mips 어셈블리어로 함수를 구현하고, 재귀함수가 호출될 때, 스택 메모리가 어떻게 변하는지 이해할 수 있기 때문에 정리해 두기 좋은 예제라고 생각해서 포스팅했습니다. 

---

Reference

1. 연세대학교 이경우 교수님 컴퓨터 아키텍쳐 강의

2. Computer Organization And Design, DAVID A.PATTERSON, JOHN L. HENNESSY