[11] CH2 명령어:컴퓨터 언어 < MIPS 버전 4 >

하드웨어 프로시저 지원 

 프로시저(procedure)나 함수는 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중 하나입니다. 프로시저는 프로그래머가 한 번에 한 부분씩 집중해서 처리할 수 있게 해줍니다. 인수(parameter)는 프로시저에 값을 보내고 결과를 받아 오는 일을 하므로, 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 합니다. 프로시저는 소프트웨어에서 추상화를 구현하는 방법중 하나입니다. 

 

프로그램이 프로시저를 실행할 때도 다음과 같이 여섯단계를 거칩니다. 

1. 프로시저가 접근할 수 있는 곳에 인수를 넣는다.

2. 프로시저로 제어를 넘긴다.

3. 프로시저가 필요로 하는 메모리 자원을 획득한다. 

4. 필요한 작업을 수행한다. 

5. 호출한 프로그램이 접근할 수 있는 장소에 결과값을 넣는다. 

6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 위치로 제어를 돌려준다. 

 

앞서 언급한 바와 같이 레지스터는 데이터를 저장하는 가장 빠른 장소이므로 가능한 한 많이 사용하는 것이 바람직하다. 그러므로 MIPS 소프트웨어는 다음의 프로시저 호출 관례에 따라서 레지스터를 할당한다. 

 - $a0 ~ $a3 : 전달할 인수를 가지고 있는 인수 레지스터 4개 

 - $v0 ~ $v1 : 반환되는 값을 갖게 되는 값 레지스터 2개 

 - $ra : 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터1개 

 

MIPS 어셈블리 언어는 레지스터를 할당할 뿐 아니라 프로시저를 위한 명령어도 제공합니다.ja1(jump and link)명령어는 지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra 레지스터에 저장하며 모양은 다음과 같습니다. 

ja1  ProcedureAddress

jump and link에서 link는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻입니다. 레지스터 $ra(31번 레지스터)에 기억되는 이 "링크"를 복귀주소(return address)라고 부릅니다. 한 프로시저가 여러 곳에서 호출될 수 있으므로 복귀 주소는 꼭 필요합니다. 

MIPS는 프로시저에서 복귀할 때 case문 구현에서 사용했던 jr(jump register)명령을 이용합니다. 알다시피 jr은 레지스터에서 저장된 주소를 무조건 점프하라는 명령어입니다. 

jr $ra 

위 명령어는 레지스터 $ra에 저장되어 있는 주소로 점프하라는 듯입니다. 이것이 바로 우리가 원하는 것입니다. 호출 프로그램(cller)은 $a0~$a3에 전달할 인수값을 넣은 후 ja1 X 명령을 이용해서 프로시저 X[피호출 프로그램(callee)]로 점프합니다. 피호출 프로그램은 계산을 다 끝낸 후 계산 결과를 $v0~$v1에 넣은 후 jr $ra명령을 실행시켜 복귀합니다. 

 

내장 프로그램 개념은 현재 실행 중인 명령어의 주소를 기억하는 레지스터를 필요로 합니다. 이 레지스터의 이름은 명령어 주소 레지스터(instruction address register)라고 하는것이 타당하겠지만 보통 프로그램 카운터(program counter)라고 하며 줄여서 PC라고 많이 부릅니다. ja1명령은 프로시저에서 복귀할때 다음 명령어로부터 실행하도록 PC + 4를 레지스터 $ra에 저장합니다. 

 

더 많은 레지스터 사용 

컴파일러가 프로시저를 번역하는 데 인수 레지스터 4개, 결과값 레지스터 2개만으로는 부족한 경우를 생각해 보자. 프로시저 호출이 다른 부분에 영향을 미쳐서는 안되므로, 호출  프로그램이 사용하는 모든 레지스터는 복귀하기 전에 프로시저 호출전의 상태로 되돌려 놓아야 합니다. 

 레지스터 스필링에 이상적인 자료구조는 스택(stack)입니다. 스택은 나중에 들어것이 먼저 나오는 구조입니다. 스택에는 다음 프로시저가 스필할 레지스터를 저장할장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가리키는 포인터가 필요합니다. 이 스택 포인터(stack pointer)는 레지스터 값 하나가 스택에 저장되거나 스택에서 복구될 때마다 한 워드씩 조정됩니다. MIPS소프트웨어는 스택 포인터를 위해 29번 레지스터를 할당해 놓고 있는데 이름은 당연히 $sp입니다. 스택에 데이터를 넣는 작업을 푸시(push), 스택에서 데이터를 꺼내는 작업을 팝(pop)라 합니다. 

역사적 선례에 따라 스택은 높은 주소에서 낮은 주소 쪽으로 성장한다. 즉, 스택에 푸시할대는 스택 포인터 값을 감소시켜야 하고, 스택에서 팝할 때는 스택 포인터 값을 증가시켜야한다. 

 

다른 프로시저를 호출하지 않는 C프로시저의 컴파일 예)

int leaf_example (int g, h, i, j)
{
 	int f;

	f = (g + h) - (i + j);

	return f;

}

위의 프로그램을 번역한 MIPS 어셈블리 코드를 보여라.

인수 g, h, i, j는 인수 레지스터 $a0, …, $a에 해당하고 f는 $0에 해당한다.컴파일된 프로그램은 다음과 같은 프로시저 레이블로부터 시작된다. 

leaf_example : 

다음 단계는 프로시저가 사용할 레지스터 값을 저장하는 것입니다. 임시레지스터 2개를 사용해 저장해야 할 레지스터는 총 3개 입니다. 스택에 세 워드를 저장할 자리를 만든 후 값을 저장합니다. 

addi $sp, $sp, -12 

sw $t1, 8($sp)  # t1 

sw $t1, 4($sp)  # t0

sw $t1, 0($sp)  # s0

밑 그림은 프로시저 호출 전후와 프로시저 실행 중의 스택 상태를 보여줍니다. 

프로시저 본문은 명령어 3개로 번역됩니다. 

add $t0 , $a0 , $a1  #  register $t0 contain g+h

add $t1 , $a2 , $a3  #  register $t0 contain i+j

sub $s0 , $t0 , $t1  #  f = $t0 - $t1 which is (g+h) - (i+j)

계산 결과 f를 보내주기 위해 f를 결과값 레지스터에 복사합니다. 

add $v0, $s0 , $zero # returns f ($v0 = $s0 + 0)

호출 프로그램으로 되돌아가기 전에 저장해 두었던 값을 스택에서 꺼내 레지스터를 원상 복구합니다. 

lw $s0, 0($sp) 

lw $t0, 4($sp) 

lw $t1, 8($sp) 

addi $sp, $sp, 12 

이 프로시저는 복귀 주소를 사용하는 점프 명령 jr로 끝납니다. 

jr $ra # jump back to calling routine 

 

중첩된 프로시저 

 다른 프로시저를 호출하지 않는 프로시저를 말단(leaf)프로시저라 부릅니다. 말단 프로시저만 있다면 일이 쉽겠지만 실제는 그렇지 못합니다. 프로시저도 다른 프로시저를 호출할 수 있습니다. 심지어 자기 자신을 호출하는 재귀(recursive)프로시저도 있습니다. 프로시저에서 레지스터를 사용할 때 조심해야 하는 것처럼 말단 프로시저가 아니라면 더더욱 조심해야 합니다. 

 

예를들어 주 프로그램이 인수값 3을 가지고 프로시저 A를 호출했다고 가정합시자.이때 레지스터 $a0에 3을 넣고 ja1 A명령을 실행 할 것입니다. 프로시저 A가 다시 인수7(이것 역시 $a0에 들어간다.)을 가지고 ja1 B를 통해 프로시저 B를 호출했다고 합시다. 아직 A가 다 끝난 것이 아니기 때문에 레지스터 $a0 사용해서 충돌이 발생합니다. 마찬가지로 레지스터 $ra에 지금은 B의 복귀 주소가 있으므로 $ra의 복귀 주소에 대해서도 충돌이 생깁니다. 이러한 문제를 예방하기 위해 조치를 취하지 않는다면, 충돌로 인하여 프로시저 A가 호출 프로그램으로 돌아가지 못합니다. 

 

한가지 방법은 값이 보존되어야 할 모든 레지스터를 스택에 넣는 것입니다. 호출 프로그램은 인수 레지스터($a0 ~ $a3)와 임시 레지스터 ($t0~$t9)중 프로시저 호출 후에도 계속 사용해야 하는것은 모두 스태겡 넣습니다. 피호출 프로그램은 복귀 주소 레지스터 $ra와 저장 레지스터($s0~$s7)중에서 피호출 프로그램이 상요하는 레지스터를 모두 저장합니다. 스택 포인터 $sp는 스태겡 저장되는 레지스터 개수에 맞추어 조정됩니다. 복귀한 후에는 메모리에서 값을 꺼내 레지스터를 원상 복구하고 이에 맞추어 스택 포인터를 다시 조정합니다. 

 

재귀 프로시저의 컴파일 예 

n계승을 계산하는 다음 재귀 프로시저에 해당하는 MIPS어셈블리 코드를 보여라.

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

인수 n은 인수 레지스터 $a0에 해당합니다. 번역된 프로그램은 프로시저 레이블로 시작하며, 뒤이어 복귀 주소와 $a0를 스택에 저장하는 명령어가 나옵니다. 

fact :

      addi $sp, $sp, -8  

      sw $ra, 4($sp)

      sw $a0, 0($sp)

fact가 처음 호출되었을때 sw는 fact를 호출한 프로그램의 주소를 저장합니다. 다음은 n이 1보다 작은지 검사해서 n이 1보다 크면 L1으로 가게하는 명령어들입니다. 

slti $t0, $a0, 1 # test for n < 1

beq $t0, $zero, L1  # if n>=1, go to L1 

n이 1보다 작으면 1을 결과값 레지스터에 넣습니다. 이때 0에다 1을 더해서 $v0에 넣습니다. 복귀하기 전에 스택에 저장된 값 2개를 버리고 복귀 주소로 점프합니다. 

addi $v0, $zero, 1 # return 1 

addi $sp, $sp, 8 $ pop 2 items off stack 

jr $ra #return caller 

스택에서 값 2개를 꺼내서 $a0와 $ra에 넣을 수도 있으나, n이 1보다 작을때 $a0와 $ra는 변하지 않으므로 그럴 필요가 없습니다. n이 1보다 작지 않으면, 인수 n을 감소시키고 이 감소된 값으로 다시 fact를 호출합니다. 

L1 :

    addi $a0, $a0, -1 

    ja1 fact

다음은 호출한 프로그램이 되돌아가는 부분입니다. 먼저 스택 포인터를 사용해서 이전의 복귀 주소와 인수값을 복구합니다. 

lw $a0, 0($sp)

lw $ra, 4($sp)

addi $sp, $sp, 8

다음으로 인수 $a0와 결과값 레지스터의 현재 값을 곱해서 $v0에 넣습니다. 곱셈 명령어는 다음장에서 소개되지만 우선 설명없이 사용합시다. 

mul $v0, $a0 , $vo # return n*fact(n-1)

마지막으로 복귀 주소를 이용해 되돌아갑니다. 

jr $ra #return to caller 

 

 

새 데이터를 위한 스택 공간의 할당 

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역변수를 저장하는데도 스택이 사용되기 때문에 문제가 복잡해집니다. 프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을 프로시저 프레임(procedure frame)또는 액티베이션 레코드(activation record)라고 부릅니다. 다음 그림은 프로시저 호출 전, 중 , 후의 스택 상태를 보여줍니다. 

MIPS소프트웨어 중에는 프레임포인터(frame pointer, $fp)가 프로시저 프레임의 첫 번째 워드를 가리키도록 하는 것이 있다. 스택 포인터 값이 프로시저 내에서 바뀔 수도 있으므로 메모리 내 지역변수에 대한 변위는 변수가 프로시저 어느 부분에서 사용되는냐에 따라 달라질 수 있습니다. 이제까지는 프로시저 내에서 $sp가 변하지 않게 했기 때문에 $fp를 사용하지 않아도 되었습니다. 

 

새 데이터를 위한 힙 공간의 할당 

C 프로그래머는 프로시저 내에서만 정의되는 자동 변수 외에도 정적 변수와 동적 자료구조를 위한 메모리 공간이 필요합니다. 다음 그림은 MIPS의 메모리 할당 방식입니다. 

스택은 최상위 주소에서부터 시작해서 아래쪽으로 자랍니다. 최하위 주소 부분은 사용이 유보되어 있고, 그다음은 MIPS 기계어 코드가 들어가는 부분입니다. 이 부분은 전통적으로 텍스트 세그먼트(text segment)라 부릅니다. 코드 위쪽에는 정적데이터  세그멐트(static data segment)라는 부분이 있는데 상수와 기타 정적 변수들이 여기에 들어갑니다. 배열은 크기가 고정되어 있엉서 정적 데이터 세그먼트에 잘 맞습니다. 그러나 링크 리스트(linked list)같은 자료구조는 늘어났다 줄어들었다 합니다. 이러한 자료구조를 위한 세그먼트를 힙(heap)이라 불러왔습니다. 이것이 메모리의 그 다음 부분에 들어갑니다. 스택과 힙이 서로 마주보면서 자라도록 할당하기 때문에 메모리를 효율적으로 사용할 수 있습니다. 

 

C는 함수를 사용해서 힙의 공간을 할당받기도 하고 사용하지 않는 공간을 되돌려주기도 합니다. malloc()은 힙의 공간을 할당받기도 하고 사용하지 않는 공간은 되돌려주기도 합니다. malloc()은 힙에 공간을 할당한 후 이 공간을 가리키는 포인터를 결과값으로 보내 줍니다. free()는 포인터가 가리키는 힙 공간을 반납합니다. C에서는 메모리 할당을 프로그램이 통제하는데, 이 부분이 흔하고도 까다로운 여러 버그의 근원입니다. 사용이 끝난 공간을 반납하는 것을 잊어버리면 메모리 누출(memory leak)이 발생하여 결국은 메모리 부족으로 운영체제가 붕괴될 수 있습니다. 

 

MIPS레지스터 사용 관례

Name

Register number

Usage

Preserved on call ?

 

$zero	0	the constant value 0	n.a.
$v0 ~ $v1	2~3	Values for results and expression evaluation	no
$a0 ~ $a3	4~7	Arguments	no
$t0 ~ $t7	8~15	Temporaries	no
$s0 ~ $s7	16~23	Saved	yes
$t8 ~ $t9	24~25	More temporaries	no
$gp	28	Global pointer	yes
$sp	29	Stack pointer	yes
$fp	30	Frame pointer	yes
$ra	31	Return address	yes