2.8 하드웨어 프로시저 지원
프로시저 함수는 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중의 하나이다. 프로시저는 프로그래머가 한 번에 한 부분씩 집중해서 처리할 수 있게 해준다. 인수는 프로시저에 값을 보내고 결과를 받아오는 일을 하므로, 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 한다. Java에서 프로시저에 해당되는 것을 2.13절에서 설명하겠지만 Java도 C가 필요로 하는 모든 것을 필요로 한다. 프로시저는 소프트웨어에서 추상화를 구현하는 방법이다.
프로시저는 스파이에 비교 가능. 스파이는 비밀 계획을 지니고 출발해서 필요한 자원을 획득하여 임무를 완수하고, 흔적은 없앤 후 원하는 결과를 가지고 출발 장소로 되돌아온다. 지정된 임무를 수행하는 것 외에 다른 것은 아무것도 건드리지 말아야 한다.
마찬가지로 프로그램이 프로시저를 실행할 때도 다음과 같이 여섯 단계를 거친다.
- 프로시저가 접근할 수 있는 곳에 인수를 넣는다.
- 프로시저로 제어를 넘긴다.
- 프로시저가 필요로 하는 메모리 자원을 획득한다.
- 필요한 작업을 수행한다.
- 호출한 프로그램이 접근할 수 있는 장소에 결과 값을 넣는다.
- 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 위치로 제어를 돌려준다.
MIPS 소프트웨어는 다음의 프로시저 호출 관례에 따라서 레지스터 32개를 할당한다.
- $a0 ~ $a3 : 전달할 인수를 가지고 있는 인수 레지스터 4개
- $v0 ~ $v1 : 반환되는 값을 갖게 되는 값 레지스터 2개
- $ra : 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개
MIPS 어셈블리 언어는 레지스터를 할당할 뿐 아니라 프로시저를 위한 명령어도 제공한다.** 지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra 레지스터에 저장하는 명령으로 jal 명령어라 부른다.**
jal ProcedureAddress
이름에서 link는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻이다. 레지스터 $ra (레지스터31)에 기억되는 이 링크를 복귀 주소(return address)라고 부른다. 한 프로시저가 여러 곳에서 호출될 수 있으므로 복귀 주소는 꼭 필요하다.
이러한 것을 지원하기 위하여 MIPS는 case 문 구현에 사용했던 jr(jump regiter)명령을 이용한다. 이 명령은 레지스터에 저장된 주소로 무조건 점프하라는 뜻이다.
jr $ra
위 명령어는 레지스터 $ra에 저장되어 있는 주소로 점프하라는 뜻이다. 이것이 바로 우리가 원하는 것이다. 호출 프로그램은 $a0 - $a3에 전달할 인수 값을 넣은 후 jal X 명령을 이용해서 프로시저 X [피호출 프로그램(callee)]로 점프한다. 피호출 프로그램은 계산을 끝낸 후 계산 결과를 $v0 - $v1 에 넣은 후 jr $ra명령을 실행하여 복귀한다.
내장 프로그램 개념은 현재 수행 중인 명령어의 주소를 기억하는 레지스터를 필요로 한다. 이 레지스터의 이름은 명령어 주소 레지스터라고 하는 것이 타당하겠지만, 역사적인 이유로 보통 프로그램 카운터(program counter)라고 부른다. MIPS에서는 약어를 사용하여 PC라고 부른다. jal 명령은 프로시저에서 복귀할 때 다음 명령어부터 실행하도록 PC + 4를 레지스터 $ra에 저장한다.
더 많은 레지스터의 사용
컴파일러가 프로시저를 번역하는 데 인수 레지스터4개, 결과값 레지스터 2개만으로는 부족한 경우를 생각해보자. 프로시저 호출이 다른 부분에 영향을 미쳐서는 안되므로, 호출 프로그램이 사용하는 모든 레지스터는 복귀하기 전에 프로시저 호출 전의 상태로 되돌려 놓아야 한다. 이 상황은 2.3절의 마지막 “하드웨어/소프트웨어 인터페이스”에서 설명한 레지스터 스필링이 필요한 경우의 한 예가 된다. ※ 레지스터 스필링이란 자주 사용하지 않는 변수들을 메모리에 저장하는 일을 말한다.
레지스터 스필링에 이상적인 자료구조 -> 스택(stack) 스택은 나중에 들어간 것이 먼저 나오는 큐이다. 스택에는 다음 프로시저가 스필할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가리키는 포인터가 필요하다. 이 스택 포인터(stack pointer)는 레지스터 값 하나가 스택에 저장되거나 스택에 복구될 때마다 한 워드씩 조정된다. MIPS는 소프트웨어는 스택 포인터를 위해 레지스터 29를 할당해 놓고 있는데 이름은 당연히 $sp이다. 스택에 데이터를 넣는 작ㅈ업을 푸시(push), 스택에서 데이터를 꺼내는 작업을 팝{pop)이라고 한다. 역사적 선례에 따라 스택은 높은 주소에서 낮은 주소 쪽으로 성장한다. 그러므로 스택에 푸시를 할 때는 스택 포인터 값을 감소시켜야 하고, 스택에서 팝을 할 때는 스택 포인터 값을 증가시켜야 한다.
ex) 다른 프로시저를 호출하지 않는 C 프로시저의 컴파일
2.2절의 두 번째 예제를 C 프로시저로 바꾸면 다음과 같다.
int leaf_example (int g, int h, int i, int j)
{
int f;
f = (g + h) - (i + j);
return f;
}
위 프로그램을 번역한 MIPS 어셈블리 코드를 보여라.
답: 인수 g, h, i, j는 인수 레지스터 $a0, $a1, $a2, $a3에 해당하고 f는 $s0에 해당한다. 컴파일된 프로그램은 다음과 같은 프로시저 레이블로부터 시작된다.
leaf_example:
다음 단계는 프로시저가 사용할 레지스터 값을 저장하는 것이다. 프로시저 본문의 C 치환문은 2.3절 예제와 같으므로 임시 레지스터 두 개를 사용한다. 따라서 저장해야 할 레지스터는 $s0, $t0, $t1 세 개이다. 스텍에 세 워드를 저장할 자리를 만든 후 값을 저장한다.
addi $sp, $sp, -12 #adjust stack to make room for 3 items
sw $t1, 8($sp) #save register $t1 for use afterwards
sw $t0, 4($sp) #save register $t0 for use afterwards
sw $s0, 0($sp) #save register $s0 for user afterwards
그림 2.10 은 프로시저 호출 전후와 프로시저 실행 중의 스택 상태를 보여준다.
프로시저 본문은 2.3절 예제에서와 같이 명령어 세 개로 번역된다.
add $t0, $a0, $a1 # register $t0 contains g + h
add $t1, $a2, $a3 # register $t1 contains 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) $ restore register $s0 for caller
lw $t0, 4($sp) # restore register $t0 for caller
lw $t1, 8($sp) $ restore register $t1 for caller
addi $sp, $sp, 12 # adjust stack to delete 3 items
이 프로시저는 복귀 주소를 사용하는 jr 명령으로 끝난다.
jr $ra # jump back to calling routine
위의 예제에서 임시 레지스터를 사용했는데, 임시 레지스터 값도 저장했다가 원상 복구해야 한다고 가정하였다. 그러나 사용하지도 않는 레지스터 값을 쓸데없이 저장했다 복구하는 일이 생길 수 있다. 특히 임시 레지스터에 대해 이런 일이 발생할 가능성이 크다. 이를 예방하기 위해 MIPS 소프트웨어는 레지스터 18개를 두 종류로 나눈다.
- $t0 - $t9: 프로시저 호출 시, 피호출 프로그램의 값이 보존해 주지 않는 임시 레지스터
- $s9 - $s7 : 프로시저 호출 전과 후의 값이 같게 유지되어야 하는 변수 레지스터 8개(피호출 프로그램이 이 레지스터를 사용하면 원래 값을 저장했다가 원상 복구한다.)
이런 간단한 관례를 정함으로써 레지스터 스필링을 많이 줄일 수 있다. 위 예에서 $t0와 $t1 값이 호출 전후에 같은 값을 유지할 필요가 없기 때문에 저장 명령 두개와 적재 명령 두개를 없앨 수 있다. 그러나 $s0는 피호출 프로그램 입장에서는 호출 프로그램이 이 값을 필요로 할 것이라고 가정하기 때문에 저장했다가 원상 복구해야 한다.
중첩된 프로시저
다른 프로시저를 호출하지 않는 프로시저를 말단(leaf) 프로시저라 한다. 말단 프로시저만 있다면 일이 쉽겠지만 그렇지 않다. 프로시저는 다른 프로시저를 호출할 수 있고, 자기 자신을 호출하는 재귀(recursive) 프로시저도 있다.
ex)
- 주 프로그램이 인수값 3을 가지고 프로시저 A를 호출
- 이 때 레지스터 $a0에 3을 넣고 jal A 명령을 실행할 것.
- 프로시저 A가 다시 인수 7(이것도 역시 $a0에 들어간다)을 가지고 jal B를 통해 프로시저 B를 호출
- 아직 A가 다 끝난 것이 아니기 떄문에 레지스터 $a0 사용에서 충돌이 발생.
- 마찬가지로 레지스터 $ra에 지금은 B의 복귀 주소가 있으므로 $radml 복귀 주소에 대해서도 충돌이 생김. 이러한 문제 예방을 위해 조치를 취해야 함.
한 가지 방법 -> 값이 보존되어야 할 모든 레지스터를 스택에 넣는 것이다.호출 프로그램은 인수 레지스터($a0 - $ a3)와 임시 레지스터($t0-$t9) 중 프로시저 호출 후에도 계속 사용해야 하는 것은 모두 스택에 넣는다. 피호출 프로그램은 복귀 주소레지스터 $ra와 저장 레지스터($s0-$s7)중에서 피호출 프로그래밍 사용하는 레지스터 모두 저장한다. 스택포인터 $sp는 스택에 저장되는 레지스터 개수에 맞추어 조정된다. 복귀한 후에는 메모리에서 값을 꺼내 레지스터를 원상 복구하고 이에 맞추어 스택 포인터를 다시 조정한다.
재귀 프로시저의 컴파일 예제
어려워서 생략 (수업시간에도 짤막하게 다룸)
C 변수는 기억장치의 한 장소에 해당한다. 기억된 내용을 어떻게 해석하는 가는 데이터형(type)과 저장유형(storage class)에 따라 달라진다. c에는 자동과 정적 두 가지 저장 유형이 있다. 자동 변수는 프로시저 내에서만 정의되는 것으로 프로시저가 중료되면 없어진다. 정적 변수는 프로시저로 돌아간 후나 프로시저에서 빠져나온 후에도 계속 존재한다. 모든 프로시저 외부에서 선언된 c변수는 정적 변수로 간주되며, static이라는 키워드를 사용해서 선언된 변수도 마찬가지이다. 정적 변수에 대한 접근을 단순화 하기 위해 MIPS는 전역 포인터(global pointer, $gp)라 불리는 레지스터를 예약해 두놓고 있다.
새 데이터를 위한 스택 공간의 할당
프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을 프로시저 프레임 (procedure frame) 또는 액티베이션 레코드(activation record)라고 부른다.
MIPS 소프트웨어 중에는 프레임 포인터(frame pointer $fp)가 프로시저 프레임의 첫 번째 워드를 가리키도록 하는 것이 있다. 스택 포인터 값이 프로시저 내에서 바뀔 수도 있으므로 메모리 내 지역 변수에 대한 변위는 변수가 프로시저 어느 부분에서 사용되느냐에 따라 달라질 수 있다. 이런 이유로 프로시저가 더 이해하기 어려워지는데, 프레임 포인터를 사용하면 프레임 포인터가 변하지 않는 베이스 레지스터 역할을 하므로, 지역 변수 참조가 간단해진다. 이제까지는 프로시저 내에서 $sp가 변하지 않게 했기 때문에 $fp를 사용하지 않아도 되었다. 예를 들면 앞의 예제는 프로시저에 들어갈 때와 나올 때만 스택을 변화시킨다. 별도의 프레임 포인터 사용 여부와 상관없이 액티베이션 레코드는 항상 스택에 존재함에 유의하라.
새 데이터를 위한 힙 공간의 할당
C프로그래머 -> 자동 변수 외에도 동적 자료구조를 위한 메모리 공간이 필요. 그림2.13추가하기 MIPS의 메모리 할당 방식. 스택은 최상위 주소에서부터 시작해서 아래쪽을 자란다. 최하위 주소부분은 사용이 유보되어 있고, 그 다음은 MIPS 기계어 코드가 들어가는 부분이다. 이 부분은 전통적으로 텍스트 세그먼트(text segment)라 부른다. 코드 위쪽에는 정적 데이터 세그먼트(static data segment)라는 부분이 있는데, 상수와 기타 정적 변수들이 여기에 들어간다. 배열은 그 크기가 고정되어 있어서 정적 데이터 세그먼트에 잘 맞는다. 그러나 링크 리스트(linked list)같은 자료구조는 늘어났다 줄어들었다 한다. 이러한 자료구조를 전통적으로 힙이라고 불러 왔다. 이것이 메모리의 그 다음 부분에 들어간다. 스택과 힙이 서로 마주보면서 자라도록 할당하기 때문에 메모리를 효율적으로 사용한다. c는 함수를 사용해서 힙의 공간을 할당받기도 하고 사용하지 않는 공간은 되돌려주기도 한다. malloc()는 힙에 공간을 할당한 후 이 공간을 가리키는 포인터를 결과 값으로 보내준다. free()는 포인터가 가리키는 힙 공간을 반납한다. C에서는 메모리 할당을 프로그램이 통제하는데, 이 부분이 흔하고도 까다로운 여러 버그의 근원이다. 사용이 끝난 공간을 반납하는 것을 잊어버리면 ‘메모리 누출’이 발생하여 결국은 메모리 부족으로 운영체제가 붕괴될 수 있다. 반면에 공간을 너무 일찍 반납하면 프로그램 의도와 상관없이 엉뚱한 것을 가리키는 ‘매달린 포인터’가 발생한다. Java에서는 이러한 버그를 피하기 위해서 자동 메모리 할당과 가비지 컬렉션을 사용한다.
2.9 MIPS 32비트 수치를 위한 주소 지정 및 복잡한 주소지정 방식
32비트 수치 피연산자
프로그램에서 사용하는 상수는 대체로 크기가 작다. 그러므로 대부분 작은 16비트 필드면 충분하지만 때에 따라서는 더 큰 상수가 필요한 경우도 있다. 이럴 때를 위해 MIPS는 레지스터의 상위 16비트에 상수를 넣는 lui(load upper immediate)명령어를 제공한다.
2.9 MIPS 32비트 수치를 위한 주소 지정 및 복잡한 주소 지정 방식
MIPS 명령어의 길이를 32비트로 고정한 덕택에 하드웨어가 간단해지기는 했지만, 32비트 상수나 32비트 주소를 사용하게 되면 편한 경우가 많다. 이 절에서는 32비트 상수를 지원하는 방법과 분기 명령어나 점프 명령어에서 사용되는 명령어 주소의 최적화를 알아본다.
32비트 수치 피연산자
때때로 16비트보다 더 큰 상수가 필요할 수도. 이 때 MIPS 에서는 레지스터의 상위 16비트에 상수를 넣는 lui(load upper immediate)명령어를 제공
ex) 32비트 상수의 로딩
레지스터 $s0에 다음 32비트 상수를 채우는 MIPS 어셈블리 코드를 작성하라. ` 0000 0000 0011 1101 0000 1001 0000 0000`
먼저 lui를 이용해서 상위 16비트를 채운다. 상위 16비트의 값은 십진수로 61이다.
lui $s0, 61 #61 decimal = 0000 0000 0011 1101 binary
이 명령을 실행한 후 레지스터 $s0의 값은 다음과 같다.
0000 0000 0011 1101 0000 0000 0000 0000
다음은 하위 16비트를 더하면 된다. 하위 16비트의 값은 십진수로 2304이다.
ori $s0. $s0, 2304 #2304 decimal = 0000 1001 0000 0000
원하는 대로 $s0에는 다음 값이 들어간다.
0000 0000 0011 1101 0000 1001 0000 0000
컴파일러나 어셈블러는 큰 숫자르 직접 다를 수 없기 때문에 몇 조각을 나눈 후 레지스터에서 재조립해야 한다. 수치 명령어의 상수는 물론 load나 store의 메모리 주소도 상수 필드 크기의 제약이 문제가 된다. MIPS 소프트웨어처럼 이 문제를 어셈블러가 해결하도록 하려면 큰 값을 만드는데 사용할 임시 레지스터를 제공해야 한다. 이 어셈블러를 위해 예약된 $at가 이런 용도로 사용된다. 그러므로 MIPS 기계어의 기호 표현은 하드웨어에 의해 제한되기보다는 어셈블러를 만든 사람이 어떤 것을 포함시키기로 했느냐에 달려있다. 본서는 컴퓨터 구조를 설명하기 위해 하드웨어를 더 따르되, 하드웨어에는 없지만 어셈블러가 제공하는 확장된 언어를 사용할 때는 별도로 표시하고 쓰기로 한다.
분기 점프 명령어에서의 주소 지정
MIPS에서 가장 간단한 주소 지정 방식 -> 점프 명령에서 사용. 점프 명령은 6비트의 op코드와 26비트의 주소 필드로 구성되는 J타입의 명령어 형식을 사용 그러므로
j 10000 # go to location 10000
을 어셈블하면 다음과 같아 진다.
조건부 분기 명령에는 분기 주소 외에 두 개의 피연산자가 더 있다. 그러므로
bne $s0, $s1, Exit $ go to Exit if $s0 ≠ $s1
만일 프로그램에서 사용하는 모든 주소가 이 16비트 필드에만 들어가야 한다면 어떤 프로그램도 2의 16승보다 커질 수는 없다. 그러나 이것은 현실적으로 너무 작은 크기. 대안은 어떤 레지스터를 지정해서 그 값을 분기 주소와 더하도록 하는 것이다. 이렇게 했을 때 분기 주소는 다음과 같이 구해진다.
PC = 레지스터 + 분기주소
이 방식은 프로그램 크기가 2의 32승까지 커지는 것을 허용하면서 조건부 분기도 지원함으로써 분기 주소의 크기 제한을 극복한다. 그러면 이제 남은 문제는 어떤 레지스터를 사용하느냐 하는 것이다.
기계어에서의 분기 예제 생략
아주 먼거리로의 분기 예제 생략
MIPS 주소 지정 방식 요약
여러 형태의 주소 표현을 일반적으로 주소지정 방식(addressing mode)이라 한다.
MIPS에서 사용되는 주소지정 방식
- 수치(immediate) 주소 지정: 피연산자는 명령어 내에 있는 상수이다.
- 레지스터 주소 지정 : 피연산자는 레지스터이다.
- 베이스 또는 변위 주소 지정 : 메모리 내용이 피연산자이다. 메모리 주소는 레지스터와 명령어 내의 상수를 더해서 구한다.
- PC 상대 주소 지정 : PC 값과 명령어 내 상수의 합을 더해서 주소를 구한다.
- 의사직접 주소 지정: 명령어 내의 26비트를 PC의 상위 비트들과 연접하여 점프 주소를 구한다.
나머지 생략
참고자료
컴퓨터 구조 및 설계 지음 DAVID A.PATTERSON, JOHN L>HENNESSY