[MIPS] MIPS instruction의 예제와 프로시저 콜링(함수 호출)

우리가 짜는 코드의  실행흐름 함수의 이동, 라이브러리의 사용, 반복문과 조건문의 사용으로 인해 단순히 순차적으로 내려가는것이 아니다..

즉, 요리조리 왔다갔다 한다. 그럼 이걸 MIPS에서는 어떻게 적용시키고 어떻게 동작하는지 알아보자.

 

제일 많이 사용하는것은 함수일것이다. 코드를 보다 보기쉽고 간결하게 나타내는 함수의 사용을 우린 빼놓을 수 없을것이다.

 

이런 함수를 호출하는것을 프로시저 콜링 이라고 하고 함수 내부에서 MIPS instruction이 어떻게 동작하는지 살펴보자

 

우선 지난번 글에 적었던

 

[MIPS] MIPS연산자, 레지스터 정리

레지스터 Set을 보고 이중 프로시저 콜링에 사용되는 레지스터들을 기억하자.

a0~a3: arguments
v0,v1: return value
t0~t9, s0~s7
sp: stack pointer
ra: return address

 

함수는 이름, 자료형, argument, body, returnValue 로 구성된다. 

그리고 stack을 적절히 사용해야한다. 

 

 

---

caller 와 callee

콜러와 콜리, 브로콜리이다.

우리는 메인함수나 다른함수에서 instruction을 수행하다가. 

또 다른 함수를 호출 할 것이다. (ex, F(3), 함수 이름이 F일때)

 

이때, 메인함수에서 호출하면 메인함수가 caller 가 된다.
그리고 불려진 함수(F)는 callee 가 된다.

caller는 callee 에게 Parameter(변수) 를 전달.

이때 함수를 호출하면서 return address를 저장하게 된다.
parameter 를 레지스터에 저장한다. 

1. 레지스터에 parameter에 저장한다.
이때 사용되는 레지스터는 $a0 ~ $a3까지 총 4개의 레지스터 이다.

2. 컨트롤을 callee 에 넘긴다.
제어권을 caller -> callee 로 넘긴다.

3. callee에게 메모리를 할당 해 준다

4. callee의 instruction을 수행한다.

5. return 값을 레지스터에 저장한다.
이때 사용되는 레지스터는 $v0, $v1 이다.

6. caller로 return한다.
caller instruction의 주소를 알고 그곳으로 점프해야한다 $ra 에 저장한다.

 

아래에서 조금더 자세히 알아보자.

---

jal 과 jr 을 통한 함수 호출, 탈출

함수의 접근

우선 F 라는 함수가 존재한다 가정하자, argument 는 n이다. n은 5라고 가정하겠다.

main함수...	C code	MIPS code	비고
함수 실행	F(5);	jal F(5)
$ra	...	...	return address 가 할당됨.

우리는 C에서 F(5)라고 가정했지만 MIPS에서는 jal을 통해 호출한다.

jal F(5)가 실행되면, $ra값은 jal F 아랫줄을 참조한다. 즉 $ra값은 함수가 실행된 줄 아랫줄 값인 것이다.

 

함수 F(n)	C code	MIPS code
리턴값	return $v0	add $v0, ..., ...
		jr $ra

이후 F함수 내부에서는 함수의 동작이 끝난뒤 C code기준 v0값을 반환한다. 이경우 MIPS에서는 $v0를 재정의해주면 된다.

그리고 함수가 끝날때 jr $ra 를 통해 Jump register return address 한다.

이경우 아까 main함수에서 지정했던 $ra값이 정하는 줄로 점프한다.

 

아무튼 MIPS 에서 함수의 호출과 return 을 위해 jal (jump and link) jr, $ra 값이 사용된다는 것을 알 수 있다.

 

---

프로시저 콜링의 스택 메모리 동작

우리가 caller가 callee를 사용할 때, 모두 tempReg, saveReg(&t, &s)를 사용할 수 있다. 

근데 caller가 쓰던 레지스터를 callee가 똑같이 쓸수 있는 문제가 발생한다.(덮어쓸 수 있다.) 

(main 에서 사용되던 $s1 이 , 함수에서 업데이트 되는경우 함수종료시 $s1 은 새로운 값이 된다.(곤란))

그래서 기존에 쓰는 값들을 스택 메모리에 저장해 주어야 한다.
->saved register의 경우 callee 가 저장해준다.(s1, s2를 쓰면 기존값은 다른데 저장해준다. 스택에다 해줌)
->temp register의 경우 caller가 저장해준다.(스택에 저장)

 

우린 이렇게 스택에 기존에 사용하던 값을 저장해야하는데 $sp를 통해 접근해서 스텍 메모리에 저장할 수 있다.

Leaf proceduer 예제를 통해 살펴보자.

Leaf proceduer

이 경우 Main 함수에서 $s0 레지스터를 이미 사용하고 있어서, 저장이 필요하다는 가정을 하고있다.

C code

int leaf_ex(int g, h, i, j)
{
	int f;				//f -> s0, s0를 스택에 넣어주어야 한다.(기존의 값을 저장해주고..)
	f = (g+h) - (i+j);		//g~j -> a0~a3
	return f;			//return val -> v0
}

 

MIPS code

leaf_example:

addi $sp, $sp, -4	//할당을 위해 stack pointer를 4만큼 뺴준다. 왜? word는 4bits니까.
sw $s0, 0($sp)		//sp위치에다 Main함수에서 사용하던 s0를 저장해준다.

add $t0, $a0, $a1 	//계산부분
add $t1, $a2, $a3 
sub $s0, $t0, $t1

add  $v0, $s0, $zero	//v0설정(v0는 return값이다.)

lw   $s0, 0($sp)		//s0 레지스터의 값을 다시 복구해준다.(기존 메인함수에서 사용하던 값으로)
addi $sp, $sp, 4		//stack pointer 를 4만큼 더해준다.(스택포인터 위치 초기화)

jr $ra				//callee 에서 caller로 제어권이동, caller의 ra값으로 이동​

addi $sp, $sp, -4: stack pointer 는 메모리의 최상위부터 내려오므로 -4를하여 공간을 할당해 준다.

add $v0, $s0, $zero: $s0의 값을 return 하기위해 $v0로 초기화해준다. (0을 더해서)

lw $s0, 0($sp): $s0의 값을 다시 기존 stack 에 넣어놓았던 값으로 초기화 해준다.

addi $sp, $sp, 4: sp에 4를 더해서 다시 원래의 위치로 돌려놓는다.

 

Non-Leaf proceduer

재귀함수나, 함수내부에서 또다른 함수의 호출이 발생할때의 경우이다. 

Factorial값을 구하는 fact함수를 예시로 들었다.

C code:
int fact(int n)
{
	if(n<1) 
		return 1;
	else 
		return n * fact(n-1);
}​

 

fact:				//jal(fact)를 수행하면 &ra값은 jal(fact)아래줄의 값이 된다.
addi $sp, $sp, -8		//우리는 ra레지스터와 기존에 쓰던 a0 레지스터를 저장 해야함 그래서 -8(바이트 할당)
sw $ra, 4($sp) 			//ra레지스터를 sp(-8)에서 4만큼 올려서 저장
sw $a0, 0($sp)			//sp에 ra 레지스터 저장.

slti $t0, $a0, 1     		//a0 < 1 => 1 nor 0 을 t0에 저장
beq  $t0, $zero, L1		//t0가 0이면 거짓, else이므로 L1으로 이동

addi $v0, $zero, 1		//return value(n값) v0에 저장
addi $sp, $sp, 8		//sp 값을 다시 8만큼 증가시켜 확보
jr   $ra			//return address 리턴


L1: 				//else의 경우... 
addi $a0, $a0, -1		//n = n-1  
jal  fact			//fact 호출하면... ra레지스터값이 아랫줄(lw문)으로 변경된다.

lw   $a0, 0($sp)		//새로 변경된 ra레지스터 값
lw   $ra, 4($sp)		//다음 sp의 값을 ra에 저장		
	
addi $sp, $sp, 8		//스택포인터 공간 확보
mul  $v0, $a0, $v0		//곱셈연산해서 v0에 저장
jr   $ra          		//return address 리턴 -> 함수의 깊이가 1이상이면 lw문으로 간다.

n=2 이고 최초에 $a0에 저장된다고 한다.

이제 위 코드를 이해해보자.

 

함수의 깊이는 0, 1, 2... 로 세겠다.

 

1. 스택 공간을 확보하고 최초 argument와 최초 retrun address(메인함수에 있는) 를 저장한다.

addi $sp, $sp, -8
sw $ra, 4($sp)  
sw $a0, 0($sp)

 

2. n=2 이므로 조건문을 통과했을때 false 가 나오고 L1 으로 이동한다.

slti $t0, $a0, 1      
beq  $t0, $zero, L1

 

3. L1은 else문이다, L1에서 n = n-1 해준다. 이후 fact를 호출 해준다.

L1:  
addi $a0, $a0, -1 
jal  fact       //이때 $ra의 새로운 값이 지정된다.

***** // lw   $a0, 0($sp)  //실행되지는 않지만 이 줄은 이제 깊이 1에서의 $ra값이다.

 

4.

깊이1, 다시 반복한다. 스택공간을 확보하고 깊이 $ra값과 $a0(1)값을 저장한다.

이후 n==1 이므로  다시 L1으로 이동한다.

addi $sp, $sp, -8
sw $ra, 4($sp)  
sw $a0, 0($sp)

 

slti $t0, $a0, 1      
beq  $t0, $zero, L1

 

5. 위와 마찬가지로  L1에서 n = n-1 해준다. 이후 fact를 호출 해준다. (n=0)

L1:  
addi $a0, $a0, -1 
jal  fact       //이때 $ra의 새로운 값이 지정된다.

***** // lw   $a0, 0($sp)  //실행되지는 않지만 이 줄은 이제 깊이 2에서의 $ra값이다.

 

6. 다시 스택 메모리 공간을 확보하고 기존의 $ra와 $a0(0)을 넣는다.

이후 조건문을 돌린다, beq문은 거짓이다. (n==0 이므로 n<1 이다.) 그럼 우린 이제 그냥 내려간다.

addi $sp, $sp, -8
sw $ra, 4($sp)  
sw $a0, 0($sp)

slti $t0, $a0, 1      
beq  $t0, $zero, L1

 

7. 이제 깊이 2의 함수에서 탈출을 하면 된다.

$v0(리턴값) 에 1을 더해준다.(0이면 곱셈 X), 이후 스택포인터를 2칸 위로 옮긴다.(깊이 1에서의 값들을 참조할수 있게)

addi $v0, $zero, 1 

addi $sp, $sp, 8 

 

8. 

jr   $ra

 

 

 

---

STR copy 함수

 

void strcpy (char x[], char y[]) 
{ 
    int i;
    i = 0;
    while ((x[i]=y[i])!='\0')
    i += 1; 
}

 

strcpy:
addi $sp, $sp, -4      //s0 저장을 위한 sp 이동
sw   $s0, 0($sp)       //s0 저장
add  $s0, $zero, $zero //s0 0으로 초기화

L1: 
add  $t1, $s0, $a1     //a1 은 y의 base address이므로, &y+i 해서 배열에 접근
lbu  $t2, 0($t1)       //character는 1byte이므로 lbu를 통해 1char 로드, 이후 t2에 저장
add  $t3, $s0, $a0     //t3 는 x의 base address이므로, &x+i 해서 배열에 접근
sb   $t2, 0($t3)       //이후 우리는 t3를 t2에 1바이트 만큼 저장한다(1글자). lbu $t2, 0($t1)과 같음
beq  $t2, $zero, L2    //이후 아까 옮겨간 값이 0이면 L2로 이동(탈출)
addi $s0, $s0, 1       //i값이었던 s0를 1만큼 증가시킨다. i++;
j    L1                //루프를 반복한다.

L2: 
lw   $s0, 0($sp)       //sp 가 가리키는 공간에 저장되었던 s0값을 다시 로드해서 재정의한다.
addi $sp, $sp, 4       //sp값을 초기화한다.
jr   $ra               //return 한다.