2. MIPS : Non-Leaf Procedure

Non-Leaf Procedure

• 자신도 어떤 함수에서 call되는 callee이며, return 되기 전에 다른 함수를 호출한다.
  • => Nested call을 수행한다.
  • => callee이면서 caller인 procedure
• 다른 procedure을 call하기 전에 자신의 caller에게 받았던 <pre>$a, $ra</pre>을 stack에 저장하고, call이 끝나면 다시 복원해야 한다.

 

<pre>$a, $ra</pre>

<pre>$a, $ra, $s, local variables</pre>의 각 개수는 컴파일러가 알고 있다.

1. Caller
   1. (선택) <pre>$a</pre> : argument register 저장 → 자신에게 넘어온 것만 저장
   2. (필수) <pre>$ra</pre> : return address 저장 → 무조건 저장
2. Callee
   1. (선택) <pre>$s</pre> : saved register 저장 → 사용한 것만 저장
   2. (선택) callee procedure의 local variables : local arrays and structures 저장 → 있는 것만 저장

 

<pre>$fp</pre>

<pre>$fp</pre> : frame pointer, frame의 시작 주소를 담고 있는 레지스터

1. 새로운 frame을 push할 때 stack에 이전의 <pre>$fp</pre>를 같이 저장
2. callee의 수행이 끝나고 pop할 때 <pre>$fp</pre>을 pop 하여 복원

 

 

Program Execution

프로그램 실행은 굉장히 dynamic하게 진행됨

 

---

Runtime Stack

Non-leaf procedure은 runtime stack에 frame을 push/pop 하면서 call/return 된다.

Runtime stack은 process virtual address space에 위치한다.

 

Local variables

Runtime stack에 만들어진다.(allocate/deallocate)

Dynamic allocation되지만, procedure과 동기된다.

 

Procedure call/return과 동기되서 allocate/deallocate 된다.

즉, Procedure가 call 될 때 동기되서 allocate되고, return 할 때 동기되서 deallocate된다.

따라서 local variable은 automatic variable이라 한다.

 

Compiler는 local variable에 base addressing mode을 이용해서, $sp에서 얼마만큼 떨어져있는가로 접근한다.

예를 들어, <pre>lw $t0, 32($sp)</pre>와 같이 접근한다.

 

<pre>$sp + offset</pre>을 통해 모든 local variable에 접근 가능하다.

이 또한 load instruction에서 offset operand의 길이가 16it인 이유 중 하나이다.

 

Stack pointer는 stack의 최상단(주소상으로는 가장 작음)을 가리키고 있으므로 unsigned number이다.

 

Local vriable이 stack에 allocate 되는 이유?

Procedurer과 동기되어 allocate/deallocate 되기 때문에 frame에 만드는 것이 가장 자연스럽다.

 

Storage efficiency

Stack을 이용해서 runtime에 만들지 않고 compile time에 만든다면,

Local variable은 많이 존재하기 때문에 모든 local variable을 할당하기 위해서는 많은 공간이 필요하다.

많은 공간을 할애해서 compile time에 만든다 하더라도 동시에 사용되는 공간을 별로 없다.

이는 저장 공간이 낭비되고 비효율 적이다.

 

Recursion

Recursion은 동일한 procedure가 자신을 여러번 호출하는 것이다.

몇번 불려지는지는 runtime information이기 때문에 compiler는 알지 못한다.

따라서 여러 set의 local variable을 만들어야 하는데 몇 set 만들지를 모르기 때문에 stack을 이용해야 한다.

 

참고 : Heap

Fully danamic memory allocation

프로그래머가 원할 때 allocate/deallcoate 된다.

 

Stack Trace (Procedure Call Trace)

만약 프로그램 실행 중에 에러가 발생해서 core dump가 일어난다면, 컴파일러는 core dump에 관한 파일을 준다.

이 파일 안의 stack을 확인하여 어느 함수를 실행 중이다가 에러가 발생했는지 확인할 수 있다.

거기서부터 에러 원인을 파악할 수 있다.

이렇게 에러가 났을 때 stack을 확인하여 원인을 파악하는 것을 stack trace(procedure call trace)라고 한다.

 

---

Recursion

Recursion

Procedure가 자기 자신을 여러 번 호출하는 것을 말한다.

 

그러나 CPU 입장에서는 procedure는 self-call 인지 모른다.

즉, 호출하는 procedure가 자신과 같은 위치에 있는 procedure인지 모른다.

그저 다른 non-leaf procedure과 동일하게 수행할 뿐이다.

 

In C

다음과 같이 펙토리얼을 구하는 C 프로그램이 있다고 하자.

int fact (int n) {					// n!
	if (n < 1) return 1;			// 0! = 1
    else return (n * fact(n-1));	// n! = n * (n-1)!
}

 

fact(3)은 다음과 같이 연산이 이루어진다.

fact(3) = 3 * fact(2)

                    fact(2) = 2 * fact(1)

                                        fact(1) = 1 * fact(0)

                                                           fact(0) = 1

 

Recursion

펙토리얼은 recursion하게 구현하는 것 보다는 loop(iterator)을 이용하여 구현하는 것이 성능적으로 더 적합하다.

Recursion은 data structure가 tree 구조로 recursive 할 때 이용하는 것이 좋다.

 

In MIPS Code

위 C 코드는 다음과 같은 MIPS code로 변환된다.

 

Argument n은 <pre>$a0</pre>을 사용하고, result는 <pre>$v0</pre>에 담긴다.

Local variable이 없고, $s을 사용하지 않는다.

따라서 frame의 크기는 2 word 임을 알 수 있다.

 

n < 1 인 경우, <pre>$a0, $ra</pre>을 restore하기 위해 lw을 해야 하지만 코드 상 <pre>$a0, $ra</pre>을 변화시키지 않았으므로 생략 가능하다.

 

Runtime Stack

Argument n은 <pre>$a0</pre>을 사용하고, result는 <pre>$v0</pre>에 담긴다.

Local variable이 없고, $s을 사용하지 않는다.

따라서 frame의 크기는 2 word 가 된다.

 

fact(3)의 경우 recursion을 통해 다음과 같은 runtime stack의 변화가 생긴다.