컴퓨터구조[6]: 함수(프로시저)와 스택 포인터 2 - 재귀함수에서의 어셈블리

모든 프로시저가 다른 프로시저를 호출하지 않는 리프 프로시저는 아니다.

 

main()이 func_A()를 호출하고, func_A()가 func_B()를 호출한다고 가정하자.

 

그러면 func_A()가 호출될 때 $ra에는 main()으로 돌아갈 때 필요한 주소가 들어가 있을 것이다.

그러나 func_B()가 호출될 때 main()으로 돌아갈 때 필요한 주소를 잃게 된다.

 

따라서 $ra 또한 스택에 push 해서 저장해두어야 한다.

 

위와 같은 코드를 어셈블리로 변환한다고 가정하자.

 

위와 같은 코드가 된다. main함수에서는 n($a0)을 사용하고 있었고, fact(3)을 호출했다 가정하자.

 

 

우선 스택에는 main함수를 가리키는 $ra와 3을 갖고 있는 n($a0)를 저장하게 된다.

다음 slti 명령어와 beq 명령어를 통해 L1(1)으로 점프한다.

3이 저장돼있는 $a0에서 1을 빼내고 다시 fact를 호출한다.

이때 $ra에는 jal fact의 다음 명령어의 주소인 L1(1)이 저장된다. 

 

 

재호출된 fact의 스택에는 다음과 같이 값이 들어가게 된다.

다시 slti 명령어와 beq 명령어를 통해 L1(2)으로 점프한다.

2가 저장돼있는 $a0에서 1을 빼내고 다시 fact를 호출한다.

이때 $ra에는 jal fact의 다음 명령어의 주소인 L1(2)가 저장된다.

 

 

 

 

재호출된 fact의 스택에는 다음과 같이 값이 들어가게 된다.

이번엔 $a0이 1보다 크지 않으므로, L1으로 점프하지 않고 addi 라인으로 넘어가게 된다.

$v0에 1을 저장함으로 1을 리턴하고, 스택에서 2칸을 pop한다. (2칸을 제거한다)

 

 

2칸을 pop했으므로 스택은 왼쪽과 같은 상태가 된다.

이 상태로 호출자로 되돌아간다. 현재 $ra에는 L1(2)가 저장돼있으므로, 그곳으로 돌아간다.

돌아간 명령어 라인은 스택에서 값을 빼서 원래 사용중이던 값으로 되돌리는 명령어이다.

스택에서 값을 빼와 $a0에는 2, $ra에는 L1(1)을 넣어주고, 2칸만큼 pop해준다.

 

 

그러면 스택은 왼쪽과 같은 상태가 되고, $v0에 $a0을 곱해준다.

현재 $v0은 원래 1이였으므로, $v0은 2를 곱해 2가 된다.

이후 jr $ra로써 호출자인 L1(1)로 되돌아간다.

위와 같이 스택에서 값을 빼서 원래 사용중이던 값으로 되돌리면

$a0은 3, $ra는 main이 된다.

 

이후 $v0에 $a0을 곱해 6이 되고 jr $ra로 최초 호출자인 main함수로 되돌아간다.

그렇게 fact(3)의 반환값 ($v0)은 6이 된다.