컴퓨터 구조 및 설계 2장

2장 명령어: 컴퓨터 언어

2.2 하드웨어 연산

MIPS 산술 명령어

반드시 한 종류의 연산만 지시한다.
항상 변수 세 개를 갖는 형식을 지킨다.

ex) b,c,d,e의 합을 a에 넣기

add a, b, c     # a = b + c
add a, a, d     # a = a + d
add a, a, e     # a = a + e

한 줄에 명령어 하나만 쓸 수 있다.
줄이 끝나면 주석도 끝난다.

하드웨어 설계 원칙 1
간단하게 하기 위해서는 규칙적인 것이 좋다.

2.3 피연산자

산술 명령어의 피연산자에는 제약이 있다.
- 레지스터(register)라고 하는 하드웨어로 직접 구현된 특수 위치 몇 곳에 있는 것만을 사용할 수 있다.
  - MIPS 구조에서 레지스터의 크기는 32비트 = 워드(word)
- MIPS 언어를 단계적으로 구체화할 때, 산술 명령어의 각 피연산자는 32개의 32비트 레지스터 중 하나이어야 한다.
  - 레지스터는 개수가 한정되어 있다.
  - 레지스터의 개수를 32개로 제한하는 이유?
    - 레지스터가 아주 많아지면, 전기 신호가 더 멀리까지 전달되어야 하므로 클럭 사이클 시간이 길어진다.
    - 레지스터가 사용하는 비트 수와 관련 있다.

하드웨어 설계 원칙 2
작은 것이 더 빠르다.

하지만, “작은 것이 더 빠르다”가 절대적인 것은 아니다. 예를 들어 레지스터를 31개로 한다고 해서 32개보다 빨라지지는 않는다.

레지스터 번호 0부터 31까지를 사용하여 명령어를 작성하지만 레지스터를 나타내기 위해서 MIPS 관례는 달러 기호 뒤에 두 글자가 따라 나오는 이름을 사용한다.

ex) f = (g + h) - (i + j); 에서 컴파일러가 변수 f,g,h,i,j를 레지스터 $s0,$s1,$s2,$s3,$s4에 각각 할당했다고 할 때, 컴파일된 MIPS 코드는?

add $t0, $s1, $s2       # t0 = g + h
add $t1, $s3, $s4       # t1 = i + j
sub $s0, $t0, $t1       # f = t0 - t1

메모리 피연산자

프로세서는 소량의 데이터만을 레지스터에 저장할 수 있다. 하지만, 컴퓨터 메모리는 수십억 개의 데이터를 저장할 수 있다. 그러므로 배열이나 구조체 같은 자료 구조는 메모리에 보관한다.

MIPS의 산술연산은 레지스터에서만 실행되기 때문에 메모리와 레짓터 간에 데이터를 주고 받는 명령가 있어야 한다. 이를 데이터 전송 명령어(data transfer instruction)이라 한다.
메모리에 기억된 데이터 워드에 접근하기 위해서는 명령어가 메모리 주소를 지정해야한다.
메모리에서 레지스터로 데이터를 복사해 오는 데이터 전송 명령을 적재(load)라 한다. 이때, 적재 명령은 연산자 이름, 메모리에서 읽어 온 값을 저장할 레지스터, 메모리 접근에 사용할 상수와 레지스터로 구성된다. MIPS에서 이 명령어의 실제 이름은 lw(load word)이다.

ex) A는 100워드 배열이고, 변수 g,h는 레지스터 $s1, $s2에 할당되었다고 가정한다. 또 배열 A의 시작 주소(base address)가 $s3에 기억되어있다고 할 때, g = h + A[8] 컴파일하라.

lw $t0, 32($s3)          # t0에 A[8]값을 넣는다.
add $s1, $s2, $t0       # g = h + t0

여기서 데이터 전송 명령어의 상수 부분을 변위(offset)라 하고, 주소 계산을 위해 여기에 더해지는 레지스터를 베이스 레지스터(base register)라고 한다.

워드 주소는 워드를 구성하는 4바이트 주소 중 하나를 사용한다. 그러므로 연속된 워드의 주소는 4씩 차이가 난다. 즉, MIPS에서 워드의 시작 주소는 항상 4의 배수이어야 한다. 이는 정렬 제약(alignment restriction)이라고 한다.

MIPS는 최상위 바이트 주소를 워드 주소로 사용하는 빅엔디안(big-endian) 계열에 속한다.

레지스터에서 메모리로 데이터를 보내는 명령을 저장(store)이라 한다. 저장 명령도 적재 명령과 동일하게 연산자 이름, 메모리에서 읽어 온 값을 저장할 레지스터, 메모리 접근에 사용할 상수와 레지스터로 구성된다. MIPS에서 이 명령어의 실제 이름은 sw(store word)이다.

ex) 변수 h가 레지스터 $s2에 할당되어 있으며 배열 A의 시작 주소는 $s3에 들어 있다고 가정하자. A[12] = h + A[8]을 MIPS 어셈블리 프로그램으로 바꾸어라.

lw $t0, 32($s3)         # t0에 A[8]값을 넣는다. 이때, 워드 주소는 4씩 차이나기 때문에 4*8 = 32를 활용한다.
add $t0, $s2, $t0       # t0 = h + t0
sw $t0, 48($s3)         # A[12] = t0

컴퓨터가 가지고 있는 레지스터보다 프로그램에서 사용하는 변수가 더 많은 경우가 있다. 그렇기 때문에 컴파일러는 자주 사용되는 변수를 가능한 많이 레지스터에 넣고 나머지 변수는 메모리에 저장했다가 필요할 때 꺼내서 레지스터에 넣는다. 자주 사용하지 않는 변수를 메모리에 넣는 것을 레지스터 스필링(spilling)이라고 한다.

레지스터는 메모리보다 접근시간이 짧고 처리량도 많으므로, 레지스터에 저장된 데이터를 사용하면 시간이 절약되고 사용하기도 간편한다. 또한, 레지스터 접근은 메모리 접근보다 에너지도 적게 든다.

상수 또는 수치 피연산자

상수는 프로그램이 적재될 때 메모리에 넣어진다. 그래서 상수를 사용하려면 메모리에서 상수를 읽어와야한다.
이때, 적재 명령을 사용하지 않는 방법 중 하나는 상수 필드를 갖는 산술 명령어를 제공하는 것이다. 여기서 상수를 수치(immediate) 피연산자라고 한다. 이는 매번 메모리에서 상수를 가져오는 것보다 연산이 빨라지고 에너지 소모가 줄어든다.

ex) 레지스터 $s3에 4를 더하기

addi $s3, $s3, 4

상수 0은 유용한 여러 변형을 제공함으로써 단순한 명령어 집합을 가능케 한다. 예를 들면, 복사(move) 연산은 피연산자 중 하나가 0인 add 명령어이다.

2.4 부호있는 수와 부호없는 수

LSB(Least Significant bit): 워드의 가장 오른쪽의 비트 0
MSB(Most Significant bit): 워드의 가장 왼쪽의 비트 31 MIPS 워드의 길이는 32비트이기 때문에 0부터 2^32-1까지의 숫자를 표시하게 된다.

이진 비트 패턴을 더하고 빼고 곱하고 나누는 하드웨어를 설계할 수 있다. 이때, 연산 결과가 하드웨어에 구현된 오른쪽 비트만으로는 표현이 불가능하면, 오버플로(overflow)가 발생했다고 한다. 오버플로가 발생했을 때 어떻게 대처해야 할지는 프로그래밍 언어와 운영체제 및 프로그램의 몫이다.

부호와 크기(sign and magnitude) 표현법

양수와 음수를 구별하기 위해서는 부호를 덧붙이는 것인데, 이는 한 비트로 표현할 수 있다.

단점

어디에 부호 비트를 붙여야 하는지가 명확하지 않다.
덧셈기는 부호를 결정하기 위해 한 단계가 더 필요하다.
- 최종 부호가 무엇이 될지를 미리 알 수 없기 때문이다.
부호 비트가 따로 붙기 때문에 양의 0과 음의 0을 갖는다.

2의 보수(two’s complement) 표현법

0이 앞에 나오면 양수
1이 앞에 나오면 음수
전체의 절반인 양수는 0~2^31-1까지는 앞서 같은 표현법을 사용한다.
1000…000은 가장 큰 음수(-2^31)을 나타내고 계속 작은 음수가 이어져 1111…111(-1)까지 감소한다.
대응되는 양수가 없는 음수가 존재한다.
MSB를 부호 비트(sign bit)라고 부른다.
- 양수/음수인지 알기 위해서는 MSB만 검사하면 된다.
부호 비트에는 -2^31을 곱하고 나머지 비트들은 각각의 위치에 해당하는 양의 기수 값을 곱한다.
- (x31 * -2^31) + (x30 * 2^30) + (x29 * 2 ^29) + … + (x1 * 2^1) + (x0 * 2^0)
2의 보수 연산에서도 오버플로가 발생한다.
- 왼쪽에 무수히 나타날 비트와 실제 이진 비트 패턴의 제일 왼쪽 비트가 서로 다를 때

역부호화

모든 0을 1로, 1은 0으로 바꾸고 거기에 1을 더한다.
00…00와 이를 모두 역전시킨 수 11…111의 합이 -1이라는데 기초한다.
- x + x’ = -1 즉, x’ + 1 = -x

부호확장(sign extension)

n비트로 표현된 이진수를 n비트보다 큰 수로 바꾸는 방법
최상위 비트를 취해서 비어 있는 왼쪽 부분에 채우고, 원래의 비트값은 오른쪽 부분에 그대로 복사한다.
실제로는 양수가 왼쪽에 끝없이 많은 0을 가지고 있고, 음수는 끝없이 많은 1을 가지고 있기 때문에 가능하다.

부호있는 수와 부호없는 수의 차이(적재)

부호있는 수
- 레지스터의 남는 곳을 채우기 위해 부호를 반복하여 복사한다. = 부호 확장(sign extension)
  - 레지스터 내부에 정확한 값을 적재하기 위함이다.
부호없는 수
- 단순히 데이터의 왼쪽을 0으로 채운다.
MIPS는 바이트 적재를 위해 2가지 명령어를 제공한다.
1. lb(load byte)
  - 바이트를 부호있는 수로 간주하고 남은 24비트를 부호확장하여 채운다.
2. lbu(load byte unsigned)
  - 부호없는 정수를 다룬다.
  - 실제적으로 바이트 적재를 위해서만 사용된다.

1의 보수법(one’s compelement)

모든 비트의 0과 1을 맞바꾸어 음수를 만든다.
x의 보수는 2^n - x - 1이다.
0이 두가지로 표현되는 것을 제외하면, 2의 보숫법과 비슷하다.
00…000은 양의 0이고 11…111은 음의 0이다.
양수와 음수의 갯수가 같다.
1의 보수 덧셈기는 맨 끝의 올림수를 처리하기 위해 한 단계를 더 필요로 한다.
- 캐리(carry)값이 발생하면 LSB에 1을 더해줘야한다.

2.5 명령어의 컴퓨터 내부 표현

MIPS에서 레지스터 $s0 ~ $s7까지는 레지스터 번호 16 ~ 23번까지, $t0 ~ $t7까지는 8 ~ 15번을 매핑한다.

ex) add $t0, $s1, $s2 어셈블리 명령어의 실제 MIPS 언어 버전을 십진수와 이진수 형태로 표현하라.

10진수와 2진수

명령어의 각 부분을 필드(field)라고 부른다. 처음과 마지막 필드는 컴퓨터에게 덧셈을 하라고 지시하는 부분이다.
두번째 필드는 덧셈에서 사용할 첫번째 피연산자 레지스터 번호(17 = $s1)
세번째 필드는 두번째 피연산자 레지스터 번호(18 = $s2)
네번째 필드는 계산 결과가 들어갈 레지스터 번호(8 = $t0)
다섯번째 필드는 사용하지 않기 때문에 0으로 표시한다.

위에서 보인 레이아웃을 명령어 형식(instruction format)이라고 한다.

MIPS 명령어 필드

MIPS R타입 명령어 형식

op: 명령어가 실행할 연산자의 종류 = 연산자(opcode)
rs: 첫 번째 근원지(source) 피연산자 레지스터
rt: 두 번째 근원지 피연산자 레지스터
rd: 목적지(destination) 레지스터. 연산 결과가 기억된다.
shamt: 자리이동(shift)량
funct: 그중의 한 연산을 구체적으로 지정한다. 기능 코드(function code)라고 부르기도 한다.

이것보다 필드 길이가 더 길어야 하는 경우에는 문제가 생길 수 있다.
ex) lw 명령어는 레지스터 필드 두 개와 상수 필드 하나가 필요하다. 만약 5비트 필드 중 하나를 주소로 쓴다면, 2^5 = 32보다 작은 값만 사용할 수 있다.

하드웨어 설계 원칙 3
좋은 설계에는 적당한 절충이 필요하다.

모든 명령어의 길이를 같게 하되, 명령어 종류에 따라 형식은 다르게 하는 것이다. 명령어의 형식은 첫 번째 필드 값을 보면 구분할 수 있다.
위의 명령어 형식은 R 타입/형식(Register)이라 한다.
하지만, 이것만으로는 불충분하기 때문에 I 타입/형식(Immediate)이라는 두 번째 명령어 형식을 만들었다. 이는 수치 연산과 데이터 전송 명령어에서 사용된다.

MIPS I타입 명령어 형식

이 명령에서는 rt 필드의 의미가 바뀌어 적재 결과가 들어갈 목적지 레지스터 번호를 표시하는 것으로 바뀌었다.

내장 프로그램

오늘날의 컴퓨터는 두 가지 중요한 원리에 바탕을 두고 있다.

명령어는 숫자로 표현된다.
프로그램은 메모리에 기억되어 있어서 숫자처럼 읽고 쓸 수 있다.

2.6 논리연산 명령어

자리이동(shit) 연산

워드 내의 모든 비트를 왼쪽 또는 오른쪽으로 이동시키고, 이동 후 빈 자리는 0으로 채운다.
MIPS 자리이동 명령어의 실제 이름은 sll(shift left logical)과 srl(shift right logical)이다.

ex) 원래 값은 $s0에 있고 결과는 $t2 레지스터에 저장된다고 가정한다.

sll $t2, $s0, 4     # reg $t2 = reg $s0 << 4 bits

MIPS shift

rs 필드는 사용하지 않으므로 0이 된다.

sll 명령은 다른 용도로 사용될 수 있다. 왼쪽으로 i비트 자리이동하면 2^i을 곱한 것과 같은 결과가 된다.

AND 연산

비트 대 비트 연산자
두 비트 값이 모두 1일 경우에만 결과가 1이 된다.
ex) and $t0, $t1, $t2: $t0 = $t1 & $t2
일부 비트를 감추는 역할을 하기 때문에 마스크(mask)라고 한다.
- 어떤 비트 패턴에서 0의 위치에 해당하는 비트들을 강제로 0으로 만드는데 사용할 수 있다.
상수 피연산자를 사용할 때는 andi(and immediate) 명령어를 사용한다.

OR 연산

비트 대 비트 연산자
두 비트 중 하나만 1이면 결과가 1이 된다.
ex) or $t0, $t1, $t2: $t0 = $t1 $t2
상수 피연산자를 사용할 때는 ori(or immediate) 명령어를 사용한다.

NOT 연산

피연산자 하나를 받아서 피연산자의 비트가 1이면 0으로, 0이면 1로 만든다.
MIPS 설계자들은 3-피연산자 형식을 유지하기 위해 NOR(NOT OR) 명령어를 포함시켰다.
- 피연산자 하나가 0이면 NOT과 같아진다.
  - ex) NOR 0 = NOT (A OR 0) = NOT (A)
ex) nor $t0, $t1, $t3: $t0 = ~ ($t1 $t3)

2.7 판단을 위한 명령어

조건부 분기(conditional branch)

beq(branch if equal)
- beq register 1, register 2, L1: register 1과 register 2의 값이 같으면 L1에 해당하는 문장으로 가라는 뜻이다.
bne(branch if not equal)
- bne register 1, register 2, L1: register 1과 register 2의 값이 같지 않으면 L1에 해당하는 문장으로 가라는 뜻이다.

ex) f,g,h,i,j는 변수이고, 각각은 레지스터 $s0부터 $s4까지에 해당한다. 아래의 C언어 if 문장을 컴파일한 코드는 무엇인가?

if (i == j) {
    f = g + h;
} else {
    f = g - h;
}

같은지 비교하는 것보다는 조건을 반대로 검사해서 then 부분을 건너뛰게 하는 것이 더 효율적이므로 bne을 사용하자.

bne $s3, $s4, Else      # go to Else if i !== j
add $s0, $s1, $s2       # f = g + h
j Exit                  # go to Exit
Else: sub $s0, $s1, $s2 # f = g - h
Exit:

if 문장의 끝 부분으로 가기 위해서는 무조건 분기(unconditional branch)라는 새로운 종류의 분기 명령으로 해결한다. 이 명령어는 프로세서에게 항상 분기하라고 말한다. MIPS에서는 이 같은 명령에 ump라는 이름을 붙이고 간략하게 j로 사용한다.

순환문

ex) 아래에 전형적인 C순환문이 있다. i와 k가 레지스터 $s3, $s5에 할당되었고 배열 save의 시작주소가 $s6에 저장되어 있다고 할 때 MIPS 어셈블리 코드를 보여라.

while (save[i] == k) {
    i += 1;
}

Loop: sll $t1, $s3, 2       # $t1 = i * 4
add $t1, $t1, $s6           # $t1 = address of save[i]
lw $t0, 0($t1)              # $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:

기본 블록(basic block)

분기 명령을 포함하지 않으며 분기 목적지나 분기 레이블도 없는 시퀀스이다.
컴파일의 초기 단계 작업 중 하나는 프로그램을 기본 블록으로 나누는 일이다.

대소 비교

slt(set on less than)
- 부호 있는 정수일 때 사용한다.
- slt $t0, $s3, $s4: 레지스터 $s3의 값이 레지스터 $s4의 값보다 작으면 레지스터 $t0를 1로, 아니면 0으로 한다.
- slti $t0, $s2, 10: 레지스터 $s2의 값이 10보다 작으면 레지스터 $t0를 1로, 아니면 0으로 한다.
sltu(set on less than unsigned) / sltiu(set on less than immediate unsigned)
- 부호 없는 정수에 사용한다.

부호 없는 비교 x < y를 하면, x가 y보다 작은지뿐만 아니라 x가 음수인지도 검사할 수 있다.
2의 보수로 표현된 음수가 부호없는 정수에서는 큰 수처럼 보이기 때문이다.

ex) 위 방법을 이용해 $s1 >= $t2이거나 $s1이 음수이면 IndeOutOfBounds로 분기하라

sltu $t0, $s1, $t2
beq $t0, $zero, IndexOutOfBounds

Case/Switch 문장

swtich를 계속적인 조건 검사를 통해 if-then-else의 연속으로 바꾸면서 구현할 수 있다.
점프 주소 테이블(jump address table) 또는 점프 테이블(jump table)의 인덱스만 계산해서 해당 루틴으로 점프할 수 있다.
- 점프 테이블은 프로그램상의 레이블에 해당하는 주소를 저장하고 있는 배열이다.
- MIPS에는 jr(jump register)라는 명령어를 가지고 있고, 이는 레지스터에 명시된 주소로 무조건 점프한다.

2.8 하드웨어의 프로시저 지원

프로시저는 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중 하나이다. 즉, 소프트웨어에서 추상화를 구현하는 방법이다. 이는 프로그래머가 한 번에 한 부분씩 집중해서 처리할 수 있게 해준다.

프로시저 실행 단계

프로시저가 접근할 수 있는 곳에 인수를 넣는다.
프로시저로 제어를 넘긴다.
프로시저가 필요로 하는 메모리 자원을 획득한다.
필요한 작업을 수행한다.
호출한 프로그램이 접근할 수 있는 장소에 결과 값을 넣는다.
프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 위치로 제어를 돌려준다.

레지스터

$a0 ~ $a3: 전달할 인수를 가지고 있는 인수 레지스터 4개
$v0 ~ $v1: 반환되는 값을 갖게 되는 값 레지스터 2개
$ra: 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개

jal(jump-and-link) 명령어

지정된 주소로 점프하면서 동시에 다음 명령어의 주소를 $ra 레지스터에 저장하는 명령
jal ProcedureAddress
jal에서 l(link)는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻이다.
복귀 주소(return address): 레지스터 $ra에 기억되는 링크
- 한 프로시저가 여러 곳에서 호출될 수 있기 때문에 복귀 주소가 필요하다.
- jr $ra
- 내장 프로그램 개념은 현재 수행 중인 명령어 주소를 기억하는 레지스터를 필요로 한다. 이는 프로그램 카운터(PC = Program Counter)라고 부른다.
  jal명령은 프로시저에서 복귀할 때 다음 명령어부터 실행하도록 PC+4를 레지스터 $ra에 저장한다.
순서
- 호출 프로그램(caller)은 $a0~$a3에 전달할 인수 값을 넣는다.
- jal X 명령을 통해 프로시저 X로 점프한다. 이때 프로시저 X를 피호출 프로그램(callee)라고 부른다.
- 피호출 프로그램은 계산을 끝낸 후 계산 결과를 $v0~$v1에 넣는다.
- jr $ra 명령을 실행해 복귀한다.

더 많은 레지스터의 사용

프로시저 호출이 다른 부분에 영향을 미쳐서는 안되므로, 호출 프로그램이 사용하는 모든 레지스터는 복귀하기 전에 프로시저 호출 전의 상태로 되돌려 놓아야 한다.
이것은 레지스터 스필링이 필요한 경우의 한 예가 된다.

레지스터 스필링에 이상적인 자료구조는 스택(stack)이다. 스택은 최근에 할당된 주소를 가리키는 포인터인 스택 포인터(stack pointer)가 필요하다. 이는 레지스터 값 하나가 스택에 저장되거나 스택에서 복구될 때마다 한 워드씩 조정된다.
스택은 높은 주소에서 낮은 주소 쪽으로 성장한다. 즉, push할 때는 스택 포인터 값을 감소시켜야 하고, pop할 경우에는 스택 포인터 값을 증가시켜야 한다.

ex) 다음 아래 프로그램을 번역한 MIPS 어셈블리 코드를 보여라. 이때, g,h,i,j는 레지스터 $a0,$a1,$a2,$a3에 해당하고 f는 $s0에 해당한다.

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

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

[1] 컴파일된 프로그램은 프로시저 레이블로부터 시작된다.
[2] 프로시저가 사용할 레지스터 값을 저장하는데 2.3절의 예제와 동일하게 임시 레지스터 두 개를 사용한다. 따라서 $s0, $t0, $t1 레지스터를 사용하고 스택에 세 워드를 저장할 자리를 만든 후 값을 저장한다. 이때, 포인터가 감소한다.(높은 주소 -> 낮은 주소)
[3] 프로시저가 계산과정을 처리한다.
[4] 계산한 결과값은 보내주기 위해 $v0에 복사한다.
[5] 호출 프로그램으로 돌아가기 전에 저장해 두었던 값을 스택에서 꺼내 레지스터를 원상 복구한다. 이때, 포인터가 증가한다.(낮은 주소 -> 높은 주소) [6] 복귀 주소를 사용해 jump한다.

# [1]
leaf_example:
    # [2]
    addi $sp, $sp, -12          # 3개 레지스터를 저장할 자리를 만든다. => sub $sp, $sp, 12와 같이 하지 않는 이유는?
    sw $t1, 8($sp)              # 나중에 사용하기 위한 $t1 저장
    sw $t0, 4($sp)              # 나중에 사용하기 위한 $t0 저장
    sw $s0, 0($sp)              # 나중에 사용하기 위한 $s0 저장
    # [3]
    add $t0, $a0, $a1           # $t0 = g + h
    add $t1, $a2, $a3           # $t1 = i + j
    sub $s0, $t0, $t1           # f = $t0 - $t1 = (g + h) - (i + j)
    # [4]
    add $v0, $s0, $zero         # return f
    # [5]
    lw $s0, 0($sp)              # caller를 위해 $s0을 load한다.
    lw $t0, 4($sp)              # caller를 위해 $t0을 load한다.
    lw $t1, 8($sp)              # caller를 위해 $t1을 load한다.
    addi $sp, $sp, 12           # 3개 레지스터를 저장한 자리를 지운다.
    #[6]
    jr $ra                      # 호출한 곳으로 돌아간다.

위 예제에서 임시 레지스터를 사용했는데, 사용하지도 않는 레지스터 값을 쓸데없이 저장했다 복구하는 일이 생길 수 있다. 이를 예방하기 위해 MIPS 소프트웨어는 레지스터 18개를 두 종류로 나눈다.

$t0 ~ $t9: 프로시저 호출 시, 피호출 프로그램이 값을 보존해 주지 않는 임시 레지스터
$s0 ~ $s7: 프로시저 호출 전과 후의 값이 같게 유지되어야 하는 변수 레지스터 8개

이런 관례는 레지스터 스필링을 많이 줄일 수 있다. $t0 ~ $t9는 호출 전후 같은 값을 유지할 필요가 없기 때문에 저장/적재 명령을 하지 않아도 된다.

중첩된 프로시저

말단(leaf) 프로시저는 다른 프로시저를 호출하지 않는 프로시저를 말한다. 말단 프로시저만 있다면 일이 쉽겠지만 실제는 그렇지 않다.
프로시저는 다른 프로시저를 호출할 수 있다. 심지어 자기 자신을 호출하는 재귀 프로시저도 존재한다.

해결방법

값이 보존되어야 할 모든 레지스터를 스택에 넣는 것이다.
이때, 스택 포인터 $sp는 스택에 저장되는 레지스터 개수에 맞추어 조정된다. 복귀한 후에는 메모리에서 값을 꺼내 레지스터를 원상 복구하고 이에 맞추어 스택 포인터를 다시 조정한다.

ex) n 계승을 계산하는 다음 재귀 프로시저에 해당하는 MIPS 어셈블리 코드를 보여라. 이때, 인수 n은 인수 레지스터 $a0에 해당한다.

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

fact:
    addi $sp, $sp, -8       # 2개 레지스터를 저장할 공간 확보
    sw $ra, 4($sp)          # 복귀 주소를 저장
    sw $a0, 0($sp)          # 인수 n 저장

    slti $t0, $a0, 1        # if n < 1 then $t0 = 1, else $t0 = 0
    beq $t0, $zero, L1      # if $t0 = 0 (n > = 1) then go to L1

    addi $v0, $zero, 1      # return 1
    addi $sp, $sp, 8        # 2개 레지스터를 스택에서 pop
    jr $ra

L1:
    addi $a0, $a0, -1       # n = n - 1
    jal fact                # fact를 호출한다.

    lw $a0, 0($sp)          # 호출한 곳의 인수 n 가져오기
    lw $ra, 4($sp)          # 호출 주소 가져오기
    addi $sp, $sp, 8        # 2개 레지스터를 스택에서 pop

    mul $v0, $a0, $v0       # $v0 = n * funct(n - 1)

    jr $ra                  # 호출한 곳으로 돌아간다.

https://docs.google.com/presentation/d/1tgzucRMf4tEcKBc07_rnui6C6fHr3-SbT4esg-Boo38/edit?usp=sharing

C에는 자동과 정적 두가지 저장 유형이 있다.

자동 변수
- 프로시저 내에서만 정의되는 것
- 프로시저가 종료되면 없어진다.
정적 변수
- 프로시저로 들어간 후나 빠져나온 후에도 계속 존재한다.
- ex) 프로시저 외부에서 선언된 C변수, static 키워드를 사용해 선언된 변수
- 정적 변수에 대한 접근을 단순화하기 위해 MIPS는 전역 포인터($gp)라 불리는 레지스터를 예약해 놓고 있다.

스택을 보존해 호출 프로그램이 스택에 저장한 값과 같은 값을 꺼낼 수있게 보장하고 있다.
피호출 프로그램이 $sp보다 위쪽에 있는 값을 쓰지 못하기 함으로써, $sp 윗부분의 스택을 원상태로 유지한다.

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

프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을 프로시저 프레임(procedure frame) 또는 액티베이션 레코드(activation record)라고 부른다.

MIPS 소프트웨어 중에는 프레임 포인터($fp)가 프로시저 프레임의 첫 번째 워드를 가리키도록 하는 것이 있다.
스택 포인터 값이 프로시저 내에서 바뀔 수도 있으므로 메모리 내 지역 변수에 대한 변위는 변수가 프로시저 어느 부분에서 사용되느냐에 따라 달라질 수 있다.
만약 프레임 포인터를 사용하면, 프레임 포인터가 변하지 않는 베이스 레지스터 역할을 하므로 지역 변수 참조가 간단해진다. 별도의 프레임 포인터 사용 여부와 상관없이 액티베이션 레코드는 항상 스택에 존재함에 유의해야 한다.

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

MIPS 메모리 할당 방식

Stack
- 최상위 주소에서부터 시작해 아래쪽으로 자란다.
Dynamic Data
- Heap을 사용한다.
Static Data
- 정적 데이터 세그먼트(static data segment)
- 상수와 기타 정적 변수들이 여기에 들어간다.
- 크기가 고정되어 있는 배열을 사용한다.
Text
- MIPS 기계어 코드가 들어가는 부분이다.
- 텍스트 세그먼트(text segment)라 부른다.
Reserved
- 최하위 주소부분은 사용이 유보되어 있다.

유동적인 메모리 할당

장점
- 메모리를 효율적으로 사용한다.
단점
- 메모리 누출(memory leak): 사용이 끝난 공간을 반납하는 것을 잊어버리는 경우
  - 메모리 부족으로 운영체제가 붕괴될 수 있다.
- 매달린 포인터(dangling pointer): 공간을 너무 일찍 반납하면 프로그램 의도와 상관없이 엉뚱한 것을 가리키는 경우

Java에서는 이러한 버그를 피하기 위해 자동 메모리 할당과 가비지 컬렉션(garbage collection)을 사용한다.

2.9 MIPS의 32비트 수치를 위한 주소지정 및 복잡한 주소지정 방식

32비트 수치 피연산자

lui(load upper immediate) 명령어

레지스터의 상위 16비트에 상수를 넣는 명령어
하위 16비트는 그 다음에 나오는 다른 명령으로 채울 수 있다.
대부분 상수는 작은 16비트 필드면 충분하지만, 때에 따라서는 더 큰 상수가 필요한 경우에 사용한다.
16비트 수치 상수 필드 값을 레지스터의 왼쪽 16비트에 넣고 오른쪽 16비트는 0으로 채운다.

ex) 레지스터 $s0에 다음 32비트 상수를 채우는 MIPS 어셈블리 코드를 작성하라. 0000 0000 0011 1101 0000 1001 0000 0000

lui $s0, 61             # 61 = 0000 0000 0011 110
ori $s0, $s0, 2304      # 2304 = 0000 1001 0000 0000

lui $s0, 61을 실행한 후 $s0의 값은 0000 0000 0011 1101 0000 0000 0000 0000이 된다.
그렇기 때문에 그 다음 16비트를 저장하기 위해서는 or를 사용한다.

분기와 점프 명령에서의 주소지정

J 타입 명령어
- 점프 명령
- 6비트의 op 코드와 26비트의 주소 필드로 구성된다.
- 긴 주소를 사용할 수 있다.
  - 프로시저들은 가까이 붙어 있어야 할 이유가 없다.
bne 명령어
- 조건부 분기 병령
- 분기 주소 외에 두 개의 피연산자가 더 있다.
- 분기 주소로 16비트만 쓸 수 있다.

만약 프로그램에서 사용하는 모든 주소가 16비트 필드에 들어가야 한다면, 어떤 프로그램도 2^16보다 더 커질 수는 없다.
이를 해결하기 위한 대안으로는 어떤 레지스터를 지정해 그 값을 분기 주소와 더하도록 하는 것이다. PC = 레지스터 + 분기 주소
해당 방식은 프로그램 크기가 2^32까지 커지는 것을 허용하면서 조건부 분기도 지원한다. 이때, 어떤 레지스터를 사용하는지에 대한 문제는 아래에서 알아보자.

PC 상대 주소지정(PC-relative addressing) 방식

분기 주소를 더할 레지스터로 PC를 선택한다.
- 현 위치에서 2^15워드 이내 떨어진 곳은 어디든지 분기할 수 있다.
- 조건부 분기는 주로 순환문이나 if문에서 사용되므로 가까이 있는 명령어로 분기하는 경향이 있다.
분기할 거리를 워드 수로 나타내면 더 먼 거리까지 분기할 수 있다.

16비트로 나타낼 수 없는 먼 곳으로 분기하는 경우, 해결방법

분기 목적지로 가는 무조건 점프를 삽입한 후, 분기 조건을 반대로 만들어서 이 점프를 건너뛸 것인지 말 것인지를 결정하게 한다.

ex) 레지스터 $s0가 레지스터 $s1가 같으면 분기하는 코드를 L1이 아주 멀어도 분기가 가능하도록 바꾸자.

beq $s0, $s1, L1

    bne $s0, $s1, L2
    j L1
L2:

MIPS 주소지정 방식 요약

수치(immediate) 주소지정
- 피연산자는 명령어 내에 있는 상수이다.
레지스터 주소지정
- 피연산자는 레지스터이다.
베이스(base)/변위(displacement) 주소지정
- 메모리 내용이 피연산자이다.
- 메모리 주소는 레지스터와 명령어 내의 상수를 더해서 구한다.
PC 상대 주소지정
- PC값과 명령어 내 상수의 합을 더해서 주소를 구한다.
- 16비트 주소를 2비트 좌측 자리이동한 후 PC에 더한다.
의사직접(pseudodirect) 주소지정
- 명령어 내의 26비트를 PC의 상위 비트들과 연접하여 점프 주소를 구한다.
- 26비트 주소를 2비트 좌측 자리이동한 후 PC 상위 4비트와 연접한다.

2.10 병렬성과 명령어: 동기화

Share on

Twitter Facebook LinkedIn

MINDOCK