2. Instruction

Intro

컴퓨터가 알아들을 수 있는 명령을 우리는 Instruction이라고 한다. 그렇다면, 이들을 모아놓은 단어장(Vocabulary)는 Instruction set이 되는 것이다. 이런 의미에서 현대의 computer는 이를 기반으로 동작하도록 설계되었기 때문에, 이를 Instruction set architecture라고 부른다. 해당 책에서는 MIPS를 기준으로 하기 때문에 똑같이 MIPS를 기준으로 설명합니다. 이는 다른 processor들과 매우 유사하니 이를 배우면 쉽게 다른 것도 이해할 수 있을 것이다.

그렇다면, Instruction이란 무엇일까? 이는 기계어(0과 1로 이루어진 이진수 체계)의 형태로 표현된다. 따라서, 이를 Assembly Instruction이라고도 한다. 이는 hardware에게 특정 동작을 수행하도록 하는 명령어라고 할 수 있다. 그렇기에 우리가 실행하거나 작성하는 모든 program들은 사실 Instruction들의 집합이라고 볼 수 있다. 실제로 Computer에서 Program이 동작할 때, 이는 Computer는 memory에 program의 내용과 program에서 사용할 data들을 위한 공간을 배정해준다. 그런 후에 실제로 실행될 때에는 program의 Instruction을 차례차례 읽어가면서 실행하는 것이다.

Assembly Instruction의 구성요소

기본적으로 MIPS는 32bit(=4Bytes) 시스템을 사용한다. 따라서, 하나의 Instruction은 4 Bytes로 표현된다. 이를 하나의 가장 단위라고 여겨서 word라고도 부른다. 따라서, 64bit(=8Bytes) CPU에서는 1 word가 8 Bytes가 될 수도 있다. 결국 모든 Instruction이 0과 1로 이루어진다. 하지만, 이는 너무 읽기 어렵기 때문에 우선 Assembly(기계어보다는 사람의 언어에 가깝지만 아주 원초적인 형태의 언어) Instruction을 알아볼 것이다. 이를 기계어로 바꾸는 것은 해당 포스팅의 밑에서 다룬다.

1. Operand

연산을 위해서 필요한 것은 연산자와 피연산자이다. 보통의 programming 언어에서는 이를 변수라고 한다.

MIPS에서는 총 두 가지의 변수 type이 존재한다.

Constant
하나의 상수로써 동작하는 변수이다. 주어진 범위 내에서 자유롭게 상수로 사용가능하다.
Register No
하드웨어 상의 register들과 programming에서의 변수와 차이점이 있다면, 바로 갯수의 제한이 있다는 것이다. 보통은 갯수를 32개로 제한한다. 그렇게 하는 것이 효율적이라고 찾아냈다고 한다. 더 많이 써도 Clock Cycle이 더 소모될 뿐이고, 적다면 표현력이 부족해지 수도 있다. 또한, 하나의 register의 크기 또한 우리는 대게 32bit(1 word)로 제한한다. 이를 표현할 때에는 보통 $ 표시를 활용하고, register는 특정 목적을 위해서 지정되어 있다. (밑에 표를 참고)
Instruction에서는 Register를 가르키기 위해서 5bit를 사용한다. $2^5$ 이면 모든 Register를 구분할 수 있기 때문이다.
Memory Address
해당 공간에는 기본적으로 register에 담기진 못한 모든 정보가 저장된다. 왜냐하면, register 가 하나의 변수를 표현할 수 있는데 만약, 변수가 32개를 넘어간다면, 이를 처리하는 것이 매우 버거워진다. 따라서, 이를 임시로 저장해두어야 한다. 따라서, 이를 memory에 잠깐 저장하는데 이를 spilling register라고 부른다.
좀 더 복잡한 데이터 구조를 가지는 경우에도 이를 모두 register에 담는 것은 불가능하다. 따라서, 우리는 Memory라는 것을 활용한다. Memory는 8bit 단위로 한 칸으로 나누어 4개의 칸을 합친 것을 하나의 단위로 봅니다. (왜냐하면 이것이 4x8bit = 32bit = 1word가 되기 때문이다.) 따라서, 우리가 특정 값에 접근할 때에는 4의 배수로 접근하는 것이 올바른 접근이다. 또한, 하나의 데이터가 4개의 칸으로 쪼개지기 때문에 저장 방법에 차이가 있을 수 있다. 어떤 사람들은 앞 자리부터 차곡차곡 넣을 수도 있지만, 누구는 역순으로도 넣을 수 있기 때문에 이를 유의해야 한다. MIPS에서는 앞에서붙터 차곡차곡 넣는 Big Endian 방식을 사용한다. (즉, 4개 중 가장 낮은 주소값에 높은 값을 의미하는 값(MSB)이 쓰인다.)
하나의 Memory address를 가르키기 위해서는 32bit가 필요하다. 이렇게 하여 $2^{32}$ = 4GB 이하까지의 Memory는 가르킬 수 있는 것이다. Instruction 자체가 32bit인데, 이를 Instruction에 바로 넣을 수는 없기 때문에 특정 Memory address를 가르키기 위해서 별도의 register에 해당 Memory의 address를 저장해두고 해당 지점부터 offset을 constant로 전달하는 식으로 표기한다.(여기서 4의 배수로 memory가 표현되므로, 2bit를 뺀다고 해도 30bit로 여전히 많다.)

다음은 MIPS의 Register와 Memory를 나타낸 것이다.

registers

상식적으로 알아두고 갈 부분은 reigster는 직접적으로 연산이 이루어지는 곳이기 때문에, register에 접근하는 비용이 memory에 접근하는 부분보다 확연하게 비용이 싸다.(시간이 짧게 걸린다.) 따라서, 이를 효율적으로 다루어주는 것이 효율 향상에 도움이 된다.

2. Operation

모든 computer는 기본적인 연산을 수행할 수 있어야 한다. MIPS에서는 다음과 같은 표기법을 사용한다.


11. <명령어(operation)> <연산자(operand) 1> <연산자(operand) 2> <연산자(operand) 3>
2
32. <명령어(operation)> <연산자(operand) 1> <연산자(operand) 2>
4
53. <명령어(operation)> <연산자(operand)>

마치 우리가 영어를 처음 배울 때, 1형식, 2형식 배우는 형태랑 유사하다. 그리고 여기서는 모든 문장이 명령형으로 구성된다는 점을 유의하자. 이에 따라서, 다음 MIPS의 피연산자(operand)와 주요 Operation을 살펴보자.

Add / Substract

add [연산자1] [연산자2] [연산자3]

모든 연산의 기본으로 위의 형태 중에서 첫번째에 해당한다. 이를 수학 기호로 나타내면 다음과 같다.

[연산자1] = [연산자2] + [연산자3]

Substraction 연산도 이와 동일하게 동작한다.

Load / Save

우리가 Register에 특정 데이터를 저장하기를 원한다면, $zero register 에 저장하기를 원하는 값 또는 register를 add해서 해당 register에 저장하면 된다.

add [저장을 원하는 register No] [$zero] [1234]

하지만, Memory에 데이터를 저장하기 위해서는 별도의 명령어가 필요하다. 그것이 save 명령어 입니다. 앞 서 말한 것과 같이 memory address를 직접적으로 Instruction에 표현할 수는 없기 때문에 특정 register에 주소값을 저장하고, 해당 주소를 base로 해서 offset을 더해서 주소를 찾는 형태로 수행한다.

sw [불러올 register No] [Memory의 Base Address를 가진 register No] offset

이와 반대로 Memory에서 데이터를 register로 불러올 때에도 별도의 명령어가 필요하다.

lw [불러올 register No] [Memory의 Base Address를 가진 register No] offset

Jump

Instruction 역시 Memory에 상주하고 있는데, 만약 필요에 따라 이전 Instruction으로 돌아가거나 Instruction을 뛰어넘어야 한다면, 그때 사용할 수 있는 Instruction이다.

j [이동할 instruction offset]

Branch

Branch(분기)는 특정 조건의 부합 여부를 확인하고, Jump를 수행하는 Instruction이다. 이를 위한 operator가 beq, bne가 있다.

beq [비교할 register1] [비교할 register2] [이동할 instruction offset]

register1과 2가 서로 동일하다면, 해당 instruction offset으로 이동하라는 의미이다. bne는 반대로 두 register가 다를 때에 이동할 수 있다.

기타 주요 명령어

instruction

* PC : Program Counter의 줄임말로 현재 실행하고 있는 Program에서 어느 위치의 Instruction을 실행시키고 있는지를 나타낸다. 이를 이용해서 CPU는 다음 Instruction을 불러온다.

* offset : offset은 대게 instruction 단위로 나타내기 때문에 1 offset은 4Bytes를 의미한다. 따라서, offset을 실제 주소에 더할 때에는 곱하기 4(실제로는 shift left 2)를 해야한다. 이로 인해서, 현재 Instruction의 다음 Instruction의 주소를 PC+4 라고 한다.

Instruction를 이용한 Programming 언어 기본 요소 구현

1. 조건문 (if / else)


1if (i == j) 
2 f = g + h;
3else
4 f = g - h;

다음과 같은 c의 조건문 코드를 아래와 같은 Instruction들로 변환이 가능하다.


1bne $s3, $s4, Else # go to Else if i != j
2add $s0, $s1, $s2 # f = g + h (skipped if i != j)
3j Exit # go to Exit
4
5Else: 
6sub $s0, $s1, $s2 # f = g - h (skipped if i = j)
7
8Exit:

여기서 Else는 임의의 offset을 나타낸다. 따라서, "Else:"라고 표시된 부분에 해당하는 offset이라고 생각하면 된다.

Switch/Case 문 같은 경우는 if/else로 변환해서 나타내기도 하고, 아니면 Switching 위치를 적어놓은 Table을 만들어서 해당 위치로 바로 이동하는 식으로 구현하기도 한다.

2. 반복문 (while)


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

다음과 같은 c의 반복문을 아래와 같은 Instruction들로 변환이 가능하다.


1# $t1 : save[i] address pointer
2# $t0 : save[i] value
3# $s3 : i
4# $s6 : save의 base address (save[0] address pointer)
5# $s5 : k
6
7# sll shift left "<<" 를 의미합니다. 
8# 즉, 아래에서는 두 번하므로, *2^2를 의미합니다.
9Loop: 
10sll $t1, $s3, 2 # temp reg $t1 = i * 4
11add $t1, $t1, $s6 # $t1 = address of save[i]
12lw $t0, 0($t1) # temp reg $t0 = save[i]
13bne $t0, $s5, Exit # go to Exit if save[i] != k
14addi $s3, $s3, 1 # i = i + 1
15j Loop # go to Loop
16
17Exit:

3. 함수 (function)

procedure는 대게 function(함수)이라고도 불린다. 함수를 우리는 하나의 예시를 통해서 설명할 수 있다.

procedure를 비밀 작전을 맡고 떠난 spy라고 하자. 작전은 자원을 습득하여, 특정 작업을 수행하고, 흔적을 감춘 뒤에, 바람직한 결과를 들고 돌아오는 것을 의미한다. 즉, spy는 작업을 마치고, 원하는 결과를 갖고 왔지만, 해당 결과 외에는 아무것도 바뀌지 않기를 기대한다. (누군가한테 의심받지 않아야하기 때문에)

이러한 과정이 똑같이 함수의 호출마다 발생한다. 아래는 이를 다소 축약한 형태입니다.

parameter를 procedure가 접근할 수 있는 곳에 위치시킵니다.
control을 procedure(callee)로 옮깁니다.
procedure는 해당하는 자원(parameter)을 습득합니다.
목표한 바를 수행합니다.
결과값을 자신을 호출한 program(caller)이 접근할 수 있는 곳에 위치시킵니다.
control을 호출한 곳(caller)으로 넘깁니다.

* 여기서 control이 이동했다는 것은 PC값이 PC+4가 아닌 함수의 주소로 이동했다는 것을 의미합니다.

이를 구현하기 위해서 우리는 다음과 같은 별도의 register를 사용합니다.


1$a0 - $a3 : 4 argument(=parameter) registers.
2$v0 - $v1 : 2 return value registers.
3$ra : 1 return address register. 원래 위치를 기억하기 위한 register.

$a와 $v는 사실 함수 사용에서 필수적이기 때문에 쉽게 받아들일 수 있지만, $ra가 의아할 수 있을 것이다. 이는 procedure를 호출했던 시점으로 다시 돌아오기 위해서 호출한 시점의 주소(실제로는 호출한 시점에서 다음 Instruction의 주소)를 저장하고 있는 것이다. 이러한 과정 즉, $ra에 저장과 jump를 동시에 해주는 것이 jal instruction이다. 이는 바로 다음 instruction을 가르키도록 하여 PC+4로 저장하고, 특정 지점으로 이동한다. 그리고 돌아올 때에는 jr instruction을 이용해서 $ra로 돌아올 수 있다.

만약, 더 많은 변수를 return value, argument로 쓰고 싶다면 우리는 이를 memory로 옮기는 과정을 수행해야 한다. 이때, computer 에서는 stack이라는 구조를 사용한다. (실제로 구현하는 것은 아니고, 마치 stack 처럼 사용하기에 이렇게 부른다.) Stack pointer라는 register($sp)를 이용하여 현재 사용하고자 하는 data가 stack의 어디를 가르키고 있는지를 저장한다.

실제 예제


1int leaf_example (int g, int h, int i, int j) {
2 int f;
3 
4 f = (g + h) - (i + j);
5 return f;
6}


1leaf_example:
2addi $sp, $sp, –12 # adjust stack to make room for 3 items
3sw $t1, 8($sp) # save register $t1 for use afterwards
4sw $t0, 4($sp) # save register $t0 for use afterwards
5sw $s0, 0($sp) # save register $s0 for use afterwards
6
7add $t0,$a0,$a1 # register $t0 contains g + h
8add $t1,$a2,$a3 # register $t1 contains i + j
9sub $s0,$t0,$t1 # f = $t0 – $t1, which is (g + h)–(i + j)
10
11add $v0,$s0,$zero # returns f ($v0 = $s0 + 0)
12
13lw $s0, 0($sp)  # restore register $s0 for caller
14lw $t0, 4($sp)  # restore register $t0 for caller
15lw $t1, 8($sp)  # restore register $t1 for caller
16addi $sp,$sp,12 # adjust stack to delete 3 items
17
18jr $ra # jump back to calling routine

해당 방식을 통해서, 만약 우리가 argument를 각 argument register 채워주고, "jal leaf_example"를 수행하게 되면, 해당 함수를 실행하는 것과 같은 동작을 하게 되는 것이다.

하지만, 더 고민해야 하는 경우가 있다. 바로 함수 안에서 또 함수를 호출하는 경우이다.

Nested Function call(Function 내부에서 Function의 호출)

procedure가 또 procedure를 호출하는 경우에는 어떻게 해야할까? 이 때에는 간단한게 stack의 retuern address를 저장해놓고, $ra를 덮어씌우는 식으로 작동한다. 아래는 recursive call을 수행한 경우를 담은 내용이다.


1int fact (int n) {
2 if (n < 1) 
3  return 1;
4 else
5  return n * fact(n-1); 
6}


1fact:
2addi  $sp, $sp, –8    # adjust stack for 2 items
3sw    $ra, 4($sp)     # save the return address
4sw    $a0, 0($sp)     # save the argument n
5# slti 는 $a0의 값이 상수보다 작다면, 0 크다면 1이 저장됩니다.
6slti  $t0, $a0, 1     # test for n < 1
7beq   $t0, $zero, L1  # if n >= 1, go to L1
8
9addi  $sp, $sp, 8     # pop 2 items off stack
10
11addi  $v0, $zero, 1   # return 1
12jr    $ra             # return to caller
13
14L1: addi $a0,$a0,–1   # n >= 1: argument gets (n – 1)
15jal fact              # call fact with (n –1)
16
17lw $a0, 0($sp)        # return from jal: restore argument n 
18lw $ra, 4($sp)        # restore the return address
19addi $sp, $sp, 8      # adjust stack pointer to pop 2 items
20
21mul $v0,$a0,$v0       # return n * fact (n – 1)
22jr   $ra              # return to the caller

이제 끝일 거 같지만, 마지막으로 생각해야 할 게 있다. 바로 내부에서 또 local variable을 선언한 경우이다. 이 경우에도 memory에 공간에 저장해야 하는데 이때에도 stack pointer를 이동 시켜서 구현하는 것은 후에 동작에 혼란을 야기할 수 있다. 따라서, frame pointer라는 것을 추가로 할당하였다. 이는 함수의 진입 시점에 stack pointer의 초기 위치를 가르킨다. 따라서, 쉽게 후에 돌아올 지점을 알 수 있기에 stack pointer를 더 유동적으로 움직일 수 있다.

여러 변수 형태 표현법

Signed Numbers

일반적으로 unsigned number라고 하면, 0과 양수를 포함하는 범위이다. 하지만, signed number는 음수까지 포함한다. 그렇다면, 컴퓨터에서는 음수를 어떻게 표현할 수 있을까?

사람의 머리로 가장 쉽게 생각할 수 있는 방법은 부호를 나타내기 위한 별도의 표시 bit를 하나 넣어주면 될 거 같다는 생각을 할 것이다. 이것이 정확하다. 바로 오른쪽 끝에 있는 bit가 1이면 음수 0이면 양수로 보는 방식이다. 1이 맨 앞에 올 때는 0이 원래 1의 역할을 대신한다. 그리고 0이 앞에 올 때는 원래 계산하던대로 수행하면 된다. 그러면 놀랍게도 우리가 생각하는 것처럼 덧셈 뺄셈 연산이 동작한다. 그리고 오른쪽 끝에 있는 수를 우리는 MST 라고 하고, 이를 sign bit라고 부른다.


10000 0000 0000 0000 0000 0000 0000 0000(two) = 0(ten) 
20000 0000 0000 0000 0000 0000 0000 0001(two) = 1(ten)
30000 0000 0000 0000 0000 0000 0000 0010(two) = 2(ten)
4...
50111 1111 1111 1111 1111 1111 1111 1101(two) = 2,147,483,645(ten)
60111 1111 1111 1111 1111 1111 1111 1110(two) = 2,147,483,646(ten)
70111 1111 1111 1111 1111 1111 1111 1111(two) = 2,147,483,647(ten)
81000 0000 0000 0000 0000 0000 0000 0000(two) = –2,147,483,648(ten)
91000 0000 0000 0000 0000 0000 0000 0001(two) = –2,147,483,647(ten)
101000 0000 0000 0000 0000 0000 0000 0010(two) = –2,147,483,646(ten)
11...
121111 1111 1111 1111 1111 1111 1111 1101(two) = –3(ten)
131111 1111 1111 1111 1111 1111 1111 1110(two) = –2(ten)
141111 1111 1111 1111 1111 1111 1111 1111(two) = –1(ten)

Proof


1# 덧셈
2  1111 1111 1111 1110 (-2)
3+                   1 (+1)
4----------------------
5  1111 1111 1111 1111 (-1)
6
7
8                   11  (+3)
9+ 1111 1111 1111 1000  (-8)
10----------------------
11  1111 1111 1111 1011  (-5)
12
13
14# 뺄셈 1
15  1111 1111 1111 1110 (-2)
16-                   1 (+1)
17----------------------
18  1111 1111 1111 1101 (-3)
19
20
21# 뺄셈 2
22                   11  (+3)
23- 1111 1111 1111 1000  (-8)
24----------------------
25                   11  (+3)
26+ 0000 0000 0000 1000  (+8)
27----------------------
28  0000 0000 0000 1011  (+11)

연산을 하다보면, 당연히 너무 큰 양수를 더하게 되면 overflow가 발생할 수 있는데 이 경우 운영체제마다 compiler마다 처리 방식이 상이하다. C에서는 overflow가 되면 그대로 값을 내놓기 때문에, 대게 굉장히 큰 음수가 나오게 된다.

Character

computer에서 수가 아닌 값을 어떻게 표현할 수 있는가는 ASCII code 표가 답해줄 수 있을 것이다. 하나의 문자를 우리는 character라고 부르고, ASCII code 표와 같은 방식을 통해서 수를 글자로 변환하여 표현한다. 또한, 하나의 문자가 아닌 단어, 문장에 이르게 되면 이를 우리는 string이라고 하며, 이는 이 데이터의 길이를 표기하기 위해서 다음 3가지 중 하나를 선택하게 된다.

string의 가장 앞에 길이를 나타내는 값을 넣어준다.
string을 구조체로 만들어서 길이를 나타내는 값을 따로 넣는다.
string의 가장 끝 문자를 구분자로 채워서 구분할 수 있도록 한다. ⇒ C에서는 \0 을 사용하여 구분한다.

Representing Instruction with Machine Language

위에 나온 MIPS Assembly code를 이제 MIPS의 기계어로 변환하는 과정을 수행할 것이다.

다시 한 번 설명하자면, 우리의 program들은 사실상 instruction의 집합이라고 볼 수 있다. 또한, 현대의 컴퓨터는 이러한 instruction들을 memory에 마치 데이터처럼 쌓아서 실행시킨다. 그래서 우리는 이러한 프로그램 실행 방식을 stored program 이라고 부른다. 우리는 위에서 memory에 데이터를 저장하기 위해서 하나의 word 즉 32bit를 사용했다. 따라서, 우리의 instruction도 하나의 word 단위로 표현한다.

아래 그림은 32bit의 각 각 부분이 무엇을 의미하는지를 표현한 것이다. 위의 연산을 표시하기 위해서 다음과 같이 word를 구분한다. 이때 주의할 점은 큰 값을 처리할 때에는 I-Type을 사용하기 때문에 형태가 기본형인 R-Type과는 다소 다른 것을 볼 수 있다.

R-Type

r-type

op : opcode라고 불리며, instruction의 동작이 무엇인지를 정의한다. (ex. add, jump, ...)
rs : first source register
rt : second source register
rd : destination register. 연산의 결과값이 저장되는 위치를 의미한다.
shamt : shift amount라는 의미로 shift 연산을 사용할 때 이용된다.
funct : op field에서 구체적인 동작을 정의할 때 사용한다.

I-Type

i-type

op : opcode라고 불리며, instruction의 동작이 무엇인지를 정의한다. (ex. addi, jump, ...)
rs : first source register
rt : second source register
constraint or address : 긴 값이 필요한 연산에서는 다음과 같은 형태로 표현한다.

Addressing

MIPS는 여러가지 instruction을 가지고 있기 때문에, 주소를 targeting하는 방식도 여러가지이다. 또한, 따른 instruction set architecture에서도 다양한 방법을 통해서 memory의 주소를 가르킨다.

Immediate addressing : 상수를 통해 직접 address를 지정하는 방식이다.
Register addressing : register로 address를 지정하는 방식이다.
Base addressing : 상수에 특정 register값을 더해서 구하는 방식이다.(MIPS → Load Word, Save Word)
PC-relative addressing : PC 값에 상수 값을 더해서 구하는 방식이다. (MIPS → Branch)
Psedodirect addressing : PC의 맨앞 내자리를 가져와서 쓰는 방식이다. (MIPS → Jump)

Reference

David A. Patterson, John L. Hennessy, Computer Organization and Design