12/28 월 ~ 1/3 일 : 6시간 5분 / 10시간
이번주 목표
1. 2장 끝내기
이번주 정리
1. 2.8 까지함
2. 점점 이해하는데 시간 걸리는 중
12/29 화 : 2시간 5분
2.5 명령어의 컴퓨터 내부 표현
레지스터가 명령어에서 참조가 되기 때문에
레지스터 이름을 숫자로 매핑하는 규칙이 있어야 한다.
MIPS에서는 레지스터 $s0에서 $s7까지는 레지스터 번호 16에서 23번까지
$t0부터 $t7까지는 번호 8에서 15번까지에 매핑한다.
[ 예제 : MIPS 어셈블리 언어를 기계어로 변환 ]
다음 어셈블리 명령어의 실제 MIPS 언어 버전을 십진수와 이진수 형태로 표현하라.
add $t0, $s1, $s2
십진수 표현은
|
0 |
17 |
18 |
8 |
0 |
32 |
명령어의 각 부분을 필드(field)라 부른다.
처음과 마지막 필드 (이 경우 0과 32에 해당하는 부분)가 컴퓨터에세 덧셈을 하라고 지시하는 부분
2, 3번째 필드는 피연선자 레지스터 번호를 나타낸다.
4번째 필드는 계산 결과가 들어갈 레지스터 번호
5번째 필드는 사용되지 않으므로 0
이진수 표현은
|
000000 6bits |
10001 5bits |
10010 5bits |
01000 5bits |
00000 5bits |
100000 6bits |
위 예제에서 보인 레이아웃을 명령어 형식(instruction format)이라고 한다.
모든 MIPS 명령어는 예외 없이 32비트이다.
어셈블리 언어와 구별하기 위하여 명령어를 숫자로 표현한 것을 기계어(machine language)라고 하고,
이런 명령어들의 시퀀스를 기계 코드(machine code)라 한다.
[ MIPS 명령어의 필드 ]
R 타입 : Arithmetic instruction format
|
op 6bits |
rs 5bits |
rt 5bits |
rd 5bits |
shamt 5bits |
funct 6bits |
- op : 명령어가 실행할 연산의 종류로서 연산자(opcode)라고 부른다.
- rs : 첫 번째 근원지(source) 피연산자 레지스터.
- rt : 두 번째 근원지 피연산자 레지스터
- rd : 목적지(destination) 레지스터. 연산 결과가 기억된다.
- shamt : 자리이동(shift)량.
- funct : 기능(function). op 필드에서 연산의 종류를 표시하고 funct 필드에서는 그중의 한 연산을 구체적으로 지정
I 타입 : Data transfer format
|
op 6bits |
rs 5bits |
rt 5bits |
constant or address 16bits |
||
2.3 절의 적재 명령을 보자.
lw $t0, 32($s3) # Temporary reg $t0 gets A[8]
rs 필드에는 19($s3의 번호), rt 필드에는 8($t0), 주소 필드에는 32가 들어간다.
이 명령어에서는 rt 필드의 의미가 바뀌어 적재 결과가 들어갈 목적지 레지스터 번호를 표시한다.
[ 요점 정리 ]
오늘날의 컴퓨터는 두 가지 중요한 원리에 바탕을 두고 있다.
1. 명령어는 숫자로 표현된다.
2. 프로그램은 메모리에 기억되어 있어서 숫자처럼 읽고 쓸 수 있다.
이것이 내장 프로그램의 개념이다.
2.6 논리연산 명령어
초기의 컴퓨터는 워드 전체에 대한 처리에만 관심을 가졌으나,
워드 내 일부 비트들에 대한 연산, 심지어는 개개 비트에 대한 연산도 필요하다는 것이 곧 명백해졌다.
이러한 연산 중 첫 번째로 자리이동(shift)을 소개한다.
MIPS 자리이동 명령어의 실제 이름은 s l l (shift left logical)과 s r l (shift right logical)이다.
s l l $t2, $s0, 4 # reg $t2 = reg $s0 << 4 bits
R 형식 명령어의 shamt 필드는 자리이동량(shift amount)을 나타낸다.
위 명령어의 기계어 형식은 다음과 같다.
|
op 0 |
rs 0 |
rt 16 |
rd 10 |
shamt 4 |
funct 0 |
s l l 명령은 또 다른 용도로 사용될 수 있다.
왼쪽으로 i 비트 자리이동하면 2i 을 곱한 것과 같은 결과가 된다.
또 다른 유용한 연산은 AND 이다.
and $t0, $t1, $t2 # reg $t0 = reg $t1 & $t2
AND와 대칭되는 연산으로 OR가 있다.
or $t0, $t1, #t2 # reg $t0 = reg $t1 | $t2
마지막 논리연산은 NOT이다.
피연산자 하나를 받아서 피연산자의 비트가 1이면 결과를 0으로, 0이면 결과를 1로 만든다.
MIPS 설계자들은 3-피연산자 형식을 유지하기 위해 NOT 대신 NOR(NOT OR) 명령어를 포함시켰다.
피연산자 두 개, 두 피연산자를 논리 OR한 값을 다시 NOT하는 비트 대비트 논리연산이다.
nor $t0, $t1, $t3 # reg $t0 = ~ ( reg $t1 | reg $t3 )
2.7 판단을 위한 명령어
컴퓨터가 단순한 계산기와 다른 점은 판단 기능이 있다는 것이다.
입력 데이터나 연산 결과에 따라 다른 명령어를 실행할 수 있다.
beq register1, register2, L1
register1과 register2의 값이 같으면 L1에 해당하는 문장으로 가라는 뜻이다.
beq는 branch if equal을 의미한다.
bne register1, register2, L1
register1과 register2의 값이 같지 않으면 L1으로 가라는 뜻이다.
bne는 branch if not equal을 의미한다.
beq와 bne 두 명령어를 조건부 분기(conditional branch)라 부른다.
[ 예제 : If - then - else를 조건부 분기로 번역 ]
다음 코드에서 f, g, h, i, j는 변수이고, 각각은 레지스터 $s0부터 $s4까지에 해당한다.
아래의 C 언어 if 문장을 컴파일한 코드는 무엇인가?
if ( i == j ) f = g + h ; else f = g - h ;
bne $s3, $s4, Else # go to Else if i ≠ j
add $s0, $s1, $s2 # f = g + h (skipped if i ≠ j)
j Exit # go to Exit
Else : sub $s0, $s1, $s2 # f = g- h (skipped if i = j)
Exit:
[ 예제 : while 순환문의 번역 ]
아래에 전형적인 C 순환문이 있다.
while ( save[i] == k )
i += 1;
i와 k가 레지스터 $s3와 $s5에 할당되었고 배열 save의 시작주소가 $s6에 저장되어 있다.
위 C 문장에 해당하는 MIPS 어셈블리 코드를 보여라.
Loop : s l l $t1, $s3, 2 # Temp reg $t1 = i * 4
add $t1, $t1, $s6 # $t1 = address of save[i]
lw $t0 , 0($t1) # Temp reg $t0 = save[i]
bne $t0, $s5, Exit # go to Exit if save[i] ≠ k
addi $s3, $s3, 1 # i = i + 1
j Loop # go to Loop
Exit :
1/1 금 : 2시간
< 하드웨어 소프트웨어 인터페이스 >
기본 블록(basic block)
- 분기 명령을 포함하지 않으며 (맨 끝에는 있을 수 있다)
분기 목적지나 분기 레이블도 없는 (맨 앞에 있는 것은 허용된다) 명령어 시퀀스.
두 변수 간의 대소 비교가 필요할 때도 있다. (beq, bne는 일치/불일치 여부 판단)
MIPS에서는 두 개의 근원지 레지스터의 값을 비교한 후 목적지 레지스터 값을 설정하는 명령어가 있다.
slt $t0, $s3, $s2 # $t0 = 1 if $s3 < $s4
상수 피연산자를 갖는 slt 명령어는
slti $t0, $s2, 10 # $t0 = 1 if $s2 < 10
< 하드웨어 소프트웨어 인터페이스 >
비교 명령은 부호있는 수와 부호없는 수 사이의 이분법도 다루어야 한다.
부호있는 정수 : slt, slti
부호없는 정수 : sltu, sltiu (unsigned)
[ Case/Switch 문장 ]
switch를 구현하는 가장 간단한 방법은
계속적인 조건 검사를 통해 switch를 if-then-else의 연속으로 바꾸는 것이다.
그러나 여러 코드의 시작 주소를 표로 만들면 더 효율적으로 구현할 수 있다.
이 때 프로그램은 점프 주소 테이블(jump address table) 또는 점프 테이블(jump table)
의 인덱스만 계산해서 해당 루틴으로 점프할 수 있다.
점프 주소 테이블 : 여러 명령어 시퀀스의 주소를 가지고 있는 표.
MIPS에는 이런 상황을 다루기 위해 jr(jump register)이라고 하는 명령어를 갖고 있다.
< 하드웨어 소프트웨어 인터페이스 >
C나 Java 같은 프로그래밍 언어에는 많은 판단문과 순환문이 있지만,
그 명령어 집합계층에서 이것을 구현하는 기반은 조건부 분기이다.
2.8 하드웨어의 프로시저 지원
프로시저(procedure)
제공되는 인수에 따라서 특정 작업을 수행하는 서브 루틴
프로시저(procedure)나 함수는 이해하기 쉽고 재사용이 가능하도록
프로그램을 구조화하는 방법 중의 하나이다.
인수(parameter)는 프로시저에 값을 보내고 결과를 받아오는 일을 하므로,
프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 한다.
프로시저는 소프트웨어에서 추상화를 구현하는 방법이다.
프로그램이 프로시저를 실행할 때 다음과 같은 여섯 단계를 거친다.
1. 프로시저가 접근할 수 있는 곳에 인수를 넣는다.
2. 프로시저로 제어를 넘긴다.
3. 프로시저가 필요로 하는 메모리 자원을 획득한다.
4. 필요한 작업을 수행한다.
5. 호출한 프로그램이 접근할 수 있는 장소에 결과 값을 넣는다.
6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 위치로 제어를 돌려준다.
레지스터는 데이터를 저장하는 가장 빠른 장소이므로 가능한 한 많이 사용하는 것이 바람직하다.
그러므로 MIPS 소프트웨어는 다음의 프로시저 호출 관례에 따라서 레지스터 32개를 할당한다.
- $a0-$a3 : 전달할 인수를 가지고 있는 인수 레지스터 4개
- $v0-$v1 : 반환되는 값을 갖게 되는 값 레지스터 2개
- $ra : 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개
MIPS 어셈블리 언어는 레지스터를 할당할 뿐 아니라 프로시저를 위한 명령어도 제공한다.
jal 명령어 (jump-and-link instruction)
지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 레지스터(MIPS에서는 $ra)에 저장하는 명령어
jal ProcedureAddress
복귀 주소(return address)
프로시저 종료 후 제자리로 돌아갈 수 있게하는 호출 위치에 대한 링크.
MIPS에서는 $ra에 저장된다.
이러한 것을 지원하기 위하여 MIPS는 case문 구현에 사용했던
jr(jump register)명령을 이용한다.
이 명령은 레지스터에 저장된 주소로 무조건 점프하라는 뜻이다.
jr $ra
호출 프로그램(caller)은 $a0-$a3에 전달할 인수 값을 넣은 후
jal X 명령을 이용해서 프로시저 X [피호출 프로그램(callee)이라 부른다]로 점프한다.
피호출 프로그램은 계산을 끝낸 후 계산 결과를 $v0-$v1에 넣은 후
jr $ra 명령을 실행하여 복귀한다.
호출 프로그램 : 프로시저 실행을 시작시키고 필요한 인수 값을 제공하는 프로그램
피호출 프로그램 : 호출 프로그램이 제공하는 인수 값을 이용해서 일련의 명령어를 실행한 후
호출 프로그램으로 제어를 넘기는 프로시저.
내장 프로그램 개념은 현재 수행 중인 명령어의 주소를 기억하는 레지스터를 필요로 한다.
이 레지스터의 이름은 프로그램 카운터(program counter)이다.
[ 더 많은 레지스터의 사용 ]
컴파일러가 프로시저를 번역하는 데
인수 레지스터 4개, 결과 값 레지스터 2개만으로는 부족한 경우를 생각해 보자.
프로시저 호출이 다른 부분에 영향을 미쳐서는 안되므로,
호출 프로그램이 사용하는 모든 레지스터는 복귀하기 전에
프로시저 호출 전의 상태로 되돌려 놓아야 한다.
이 상황은 레지스터 스필링이 필요한 경우의 한 예가 된다.
(레지스터 스필링 : 자주 사용하지 않는 변수들을 메모리에 넣는 일)
레지스터 스필링에 이상적인 자료구조는 스택(stack)이다.
스택 포인터(stack pointer)는 가장 최근에 스택에 할당된 주소를 가리키는 값이다.
레짓터가 스필될 장소 또는 레지스터의 옛날 값을 찾을 수 있는 장소를 표시한다.
MIPS에서는 $sp이다.
# 예제 : 다른 프로시저를 호출하지 않는 C 프로시저의 컴파일
f = ( g + h ) - ( i + j );
이 문장을 C 프로시저로 바꾸면 다음과 같다.
int leaf_example ( int g, int h, int i, int j )
{
int f;
f = ( g + h ) - ( i + j );
return f;
}
위 프로그램을 번역한 MIPS 어셈브리 코드를 보여라.
# 답
프로시저가 사용할 레지스터 값을 저장
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 use afterwards
프로시저 본문은 명령어 세 개로 번역된다.
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
1/2 토 : 1시간 30분
위의 예제에서 임시 레지스터를 사용했는데, 임시 레지스터 값도 저장했다가 원상 복구 해야한다고 가정하였다.
그러나 사용하지도 않는 레지스터 값을 쓸데없이 저장했다 복구하는 일이 생길 수 있다.
이를 예방하기 위해 MIPS 소프트웨어는 레지스터 18개를 두 종류로 나눈다.
- $t0 - $t9 : 프로시저 호출 시, 피호출 프로그램이 값을 보존해 주지 않는 임시 레지스터
- $s0 - $s7 : 프로시저 호출 전과 후의 값이 같에 유지되어야 하는 변수 레지스터.
피호출 프로그램이 이 레지스터를 사용하면 원래 값을 저장했다가 원상 복구한다.
[ 중첩된 프로시저 ]
다른 프로시저를 호출하지 않는 프로시저를 말단(leaf) 프로시저라 한다.
다른 프로시저를 호출하는 프로시저는 다 끝난 상태가 아니기 때문에 인수 레지스터 사용에서 충돌이 발생한다.
또한 레지스터 $ra에 호출된 프로시저의 복귀 주소가 있으므로 $ra 복귀 주소에 대해서도 충돌이 생긴다.
한 가지 방법은 값이 보존되어야 할 모든 레지스터를 스택에 넣는 것이다.
# 예제 : 재귀 프로시저의 컴파일
n 계승을 계산하는 다음 재귀 프로시저에 해당하는 MIPS 어셈블리 코드를 보여라.
int fact (int n)
{
if ( n < 1 ) return ( 1 );
else return ( n * fact( n - 1 ) );
}# 답
fact :
add $sp, $sp, -8 # adjust stack for 2 items
sw $ra, 4($sp) # save the return address
sw $a0, 0($sp) # save the argument n
slti $t0, $a0, 1 # test for n < 1
beq $t0, $zero, L1 # if n >= 1, go to L1
addi $v0, $zero, 1 # return 1
addi $sp, $sp, 8 # pop 2 items off stack
jr $ra # return to caller
L1 : addi $a0, $a0, -1 # n >= 1 : argument gets (n-1)
jal fact # call fact with (n-1)
lw $a0, 0($sp) # return from jal : restore argument n
lw $ra, 4($sp) # restore the return address
addi $sp, $sp, 8 # adjust stack pointer to pop 2 items
mul $v0, $a0, $v0 # return n * fact(n-1)
jr $ra # return to the caller<하드웨어 소프트웨어 인터페이스>
C 변수는 기억장치의 한 장소에 해당한다.
여기에 기억된 내용을 어떻게 해석하는가는 데이터형(type)과 저장유형(storage class)에 따라 달라진다.
C에는 자동(automatic)과 정적(static) 두 가지 저장 유형이 있다.
자동 변수는 프로시저 내에서만 정의되는 것으로 프로시저가 종료되면 없어진다.
정적 변수는 프로시저로 들어간 후나 프로시저에서 빠져나온 후에도 계속 존재한다.
정적 변수에 대한 접근을 단순화하기 위해 MIPS는
전역 포인터(global pointer, $gp)라 불리는 레지스터를 예약해 놓고 있다.
프로시저 호출 전후의 값 보존 관계
|
Preserved |
Not preserved |
|
Saved registers : $s0 - $s7 |
Temporary register : $t0 - $t9 |
|
Stack pointer register : $sp |
Argument registers : $a0 - $a3 |
|
Return address register : $ra |
Return value registers : $v0 - $v1 |
|
Stack above the stack pointer |
Stack below the stack pointer |
[새 데이터를 위한 스택 공간의 할당]
레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는 데도
스택이 사용되기 때문에 문제가 복잡해진다.
프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을
프로시저 프레임(procedure frame) 또는 액티베이션 레코드(activation record)라고 부른다.
1/3 일 : 35분
MIPS 소프트웨어 중에는 프레임 포인터(frame pointer, $fp)가
프로시저 프레임의 첫 번재 워드를 가리키도록 하는 것이 있다.
프레임 포인터를 사용하면 프레임 포인터가
변하지 않는 베이스 레지스터 역할을 하므로 지역 변수 참조가 간단해진다.
프레임 포인터($fp)는 프레임의 첫 번재 워드(저장된 인수 레지스터일 때가 많다.)를 가리키며,
스택 포인터($sp)는 스택의 맨 위를 가리킨다.
스택 포인터는 프로그램이 실행되면서 변할 수 있으므로
변수 참조는 변하지 않는 프레임 포인터를 사용하는 것이 좋다.
스택 포인터를 사용해도 약간의 주소 계산이 추가되면 변수 접근이 가능하다.
[새 데이터를 위한 힙 공간의 할당]
C 프로그래머는 프로시저에만 국한되는 자동 변수 외에도
정적 변수와 동적 자료구조를 위한 메모리 공간이 필요하다.
스택은 최상위 주소에서부터 시작해서 아래쪽으로 자란다.
최하위 주소 부분은 사용이 유보되어 있고,
그 다음은 MIPS 기계어 코드가 들어가는 부분이다.
이 부분은 전통적인 텍스트 세그먼트(text segment)라 부른다.
텍스트 세그먼트 : UNIX 목적 파일에서 소스 파일 루틴의 기계어가 수록된 부분.
코드 위쪽에는 정적 데이터 세그먼트(static data segment)라는 부분이 있다. 상수와 기타 정적 변수들이 여기에 들어간다.
배열은 그 크기가 고정되어 있어서 정적 데이터 세그먼트에 잘 맞는다.
그러나 링크 리스트같은 자료구조는 늘어났다 줄어들었다 한다.
이러한 자료구조를 위한 세그먼트를 전통적으로 힙(heap)이라고 볼러 왔다.
|
Stack ↓ ↑ Dynamic data |
|
Static data |
|
Text |
|
Reserved |
스택과 힙이 서로 마주 보면서 자라도록 할당하기 때문에 메모리를 효율적으로 사용한다.
malloc()는 힙에 공간을 할당한 후 이 공간을 가리키는 포인터를 결과 값으로 보내 준다.
free()는 포인터가 가리키는 힙 공간을 반납한다.
사용이 끝난 공간을 반납하는 것을 잊어버리면 '메모리 누출(memory leak)'이 발생한다.
반면에 공간을 너무 일찍 반납하면 엉뚱한 것을 가리키는 '매달린 포인터(dangling pointer)'가 발생한다.
