요약

요리사는 창고에 있는 재료를 바로 썰지 못한다. 도마에 꺼내 놓고 썰고, 다 되면 다시 창고에 넣는다. 이 기계도 그렇다. 계산은 프로세서 안의 작은 칸 몇 개에서만 하고, 메모리와는 “꺼내 오기”와 “넣어 두기” 두 명령으로만 값을 주고받는다. 명령의 종류가 적고 모양이 단순해서, 컴파일러의 앞 단계가 만든 코드 한 줄을 명령 몇 줄로 기계적으로 옮길 수 있다. 대신 도마가 좁아서 값을 꺼내고 넣는 일이 잦다. 여기서 쓰는 표기는 실제 기계의 것을 단순하게 고친 것이라 실제 어셈블러에 그대로 넣으면 돌지 않는다.

예시로 보기

컴파일러의 마지막 단계인 코드 생성기는 3주소 코드 같은 중간 표현을 기계 수준의 코드로 옮긴다. 할 일은 둘이다. 중간 코드의 명령마다 알맞은 기계 명령을 고르고, 레지스터처럼 수가 정해진 기계 자원을 아껴 나눠 쓴다.

어셈블리어는 기계 수준의 언어이고 기계 구조마다 다르다. 이 문서 모음은 MIPS 기계를 목표로 삼는다. MIPS는 Microprocessor without Interlocked Pipelined Stages를 줄인 이름이다. 90년대에 가장 많이 팔린 프로세서였고 지금도 임베디드 기기에 많이 쓰인다. x86 같은 다른 주류 구조도 비슷하게 돈다.

3주소 코드 a = b + c 한 줄을 옮긴 것이 아래 네 줄이다. b는 메모리의 $sp + 8번지에, c는 $sp + 4번지에, a는 $sp + 12번지에 있다고 하자.

lw  $r0 8($sp)       # 메모리에서 b를 꺼내 $r0에 둔다
lw  $r1 4($sp)       # 메모리에서 c를 꺼내 $r1에 둔다
add $r2 $r0 $r1      # $r2 = $r0 + $r1
sw  $r2 12($sp)      # $r2를 메모리의 a 자리에 넣는다

$r0, $r1, $r2가 프로세서 안의 칸이다. 이런 칸을 레지스터(register)라 부른다. add는 레지스터끼리만 더한다. 메모리에 있는 b와 c를 바로 더하는 명령은 없다. 그래서 꺼내고(lw), 계산하고, 넣는(sw) 세 걸음이 된다.

8($sp)는 “$sp에 든 번지에 8을 더한 곳”이라고 읽는다. 괄호 밖의 수를 오프셋이라 부른다.

검증: 아래 표의 모든 명령을 파이썬 흉내기로 돌려 표에 적은 뜻과 같은지 확인(산술·비교·분기는 −3~3의 모든 쌍), subi가 addi에 음수를 넣은 것과 같음, lw·sw만 메모리를 만짐, 카드 C2 — 51_mips-instructions_impl.py. 실제 MIPS 어셈블러로 돌린 것이 아니다.

기계의 성격과 단순화 가정

MIPS의 성격.

  • 메모리에 닿는 명령은 꺼내 오기(load)와 넣어 두기(store)뿐이다.
  • 나머지 명령(산술 등)은 모두 레지스터를 피연산자로 쓴다.
  • 레지스터는 빨리 읽고 쓸 수 있고 계산을 바로 할 수 있는 전용 저장 칸이다. 하지만 수가 적다. 그래서 레지스터를 알맞게, 아껴서 쓰는 일이 아주 중요하다.
  • MIPS에는 범용 레지스터가 32개 있다.

여기서만 두는 단순화 가정.

  • 32비트 기계다. 모든 객체는 4바이트 정렬이라고 친다. 변수 하나가 4바이트 한 칸이다.
  • 레지스터는 두 종류만 쓴다.
    • $sp: 스택 포인터. 스택 꼭대기 바로 다음 자리(다음에 쓸 빈칸)를 가리킨다.
    • $r0, $r1, …: 값을 잠깐 담는 레지스터.
  • $r0, $r1, …은 끝없이 많다고 친다.
  • 중간 코드의 조각 하나하나를 그대로 어셈블리로 옮긴다.

뒤의 두 가정은 현실과 다르다. 실제 레지스터는 수가 정해져 있다. 조각마다 따로 옮기면 만들기는 쉽지만 쓸데없이 꺼내고 넣는 명령이 생긴다. 이 문제는 그래프 색칠 레지스터 할당에서 푼다.

함수 호출을 옮길 때는 레지스터가 하나 더 나온다. $ra는 돌아갈 주소를 담는 레지스터다.

명령 표

reg1, reg2, reg3은 레지스터, offset과 immediate는 명령에 바로 적는 수, label은 코드의 한 자리에 붙인 이름이다.

메모리와 주고받기.

명령 하는 일
lw reg1 offset(reg2) reg2 + offset번지에서 32비트 값 하나를 꺼내 reg1에 넣는다
sw reg1 offset(reg2) reg1의 32비트 값을 reg2 + offset번지에 넣는다

lw는 load word, sw는 store word를 줄인 것이다. 두 명령 모두 레지스터를 앞에, 번지를 뒤에 쓴다. 값이 움직이는 방향은 반대다.

산술.

명령 하는 일
add reg1 reg2 reg3 reg1 = reg2 + reg3
sub reg1 reg2 reg3 reg1 = reg2 - reg3
mul reg1 reg2 reg3 reg1 = reg2 * reg3
div reg1 reg2 reg3 reg1 = reg2 / reg3

비교. 결과가 참이면 reg1에 1, 거짓이면 0이 들어간다1.

명령 하는 일 명령 하는 일
seq reg1 reg2 reg3 reg1 = reg2 == reg3 sne reg1 reg2 reg3 reg1 = reg2 != reg3
sgt reg1 reg2 reg3 reg1 = reg2 > reg3 sge reg1 reg2 reg3 reg1 = reg2 >= reg3
slt reg1 reg2 reg3 reg1 = reg2 < reg3 sle reg1 reg2 reg3 reg1 = reg2 <= reg3

이름은 set if equal, set if less than처럼 읽는다. s 뒤의 두 글자가 조건이다.

명령에 수를 바로 적는 꼴. 명령에 바로 적는 상수를 즉시값(immediate)이라 부른다. 이름 끝에 i가 붙는다.

명령 하는 일
li reg1 immediate reg1 = immediate
addi reg1 reg2 immediate reg1 = reg2 + immediate. subi, muli, divi도 같은 꼴이다
seqi reg1 reg2 immediate reg1 = reg2 == immediate. snei, sgti, sgei, slti, slei도 같은 꼴이다

흐름 바꾸기.

명령 하는 일
j label 무조건 label로 간다 (goto label)
beq reg1 reg2 label reg1 == reg2면 label로 간다. bne(≠), bgt(>), bge(≥), blt(<), ble(≤)도 같은 꼴이다
beqz reg1 label reg1 == 0이면 label로 간다. bnez는 0이 아니면 간다
beqi reg1 immediate label reg1 == immediate면 label로 간다. bnei, bgti, bgei, blti, blei도 같은 꼴이다
jr reg1 reg1에 든 주소로 간다

조건이 맞지 않으면 바로 다음 줄로 넘어간다. b는 branch, z는 zero다.

실제 MIPS와 다른 점. 위 표기는 실제 MIPS를 단순하게 고친 것이다. 확실한 차이만 적는다2.

  • 실제 MIPS 어셈블리에는 $r0, $r1 같은 이름이 없다. 레지스터는 $0~$31의 번호나 $t0, $s0, $a0, $v0 같은 쓰임새 이름으로 부른다. $sp와 $ra는 실제 이름과 같다.
  • 실제 표기는 피연산자 사이에 쉼표를 쓴다: lw $t0, 8($sp), add $t2, $t0, $t1.
  • 실제 기계 명령에는 subi가 없다. 빼기는 addi에 음수를 적어서 한다.
  • 실제 MIPS의 jal label은 돌아올 주소를 $ra에 넣고 label로 간다. 위 명령 표에는 함수로 뛰는 명령이 없다.

seqi, beqi처럼 표에 있는 나머지 명령이 실제 어셈블러에서 어떻게 받아들여지는지는 어셈블러마다 달라 여기 적지 않는다[확인필요].

연결

과목별 관점

컴퓨터 구조 (2-1학기). 컴퓨터 구조 과목은 실제 MIPS 표기와 기계어를 쓴다. 이 문서의 단순화한 명령을 실제 MIPS로 옮기면 아래와 같다3.

단순화한 표기 실제 MIPS 달라지는 점
lw $r0 8($sp) lw $t0, 8($sp) 레지스터 이름과 쉼표만 다르다: MIPS 레지스터와 메모리 피연산자
add $r2 $r0 $r1 add $t2, $t0, $t1 같다
subi $r1 $r0 2 addi $t1, $t0, -2 기계어에 subi가 없다: MIPS 산술·논리 명령
li $r0 5 addi $t0, $zero, 5 li는 어셈블러가 다른 명령으로 바꿔 주는 의사 명령이다
sgt $r3 $r0 $r1 slt $t3, $t1, $t0 기계어의 비교는 “작다”(slt)뿐이라 재료 순서를 바꾼다
bnez $r3 L bne $t3, $zero, L 0과 견줄 때 $zero를 쓴다: MIPS 분기와 점프
blt $r0 $r1 L slt $t2, $t0, $t1 / bne $t2, $zero, L 기계어의 조건 분기는 beq와 bne뿐이다. blt·bgt·ble·bge는 의사 명령이다
mul $r2 $r0 $r1 mult $t0, $t1 / mflo $t2 곱은 64비트라 Hi·Lo라는 전용 칸에 나오고 mflo로 꺼낸다

이 문서는 레지스터가 끝없이 많다고 쳤지만 실제로는 32개이고 번호마다 쓰임이 정해져 있다. 함수 호출도 다르다. 함수 호출의 코드 생성은 인수와 돌아갈 주소를 모두 스택에 쌓지만, 실제 MIPS 약속은 인수를 $a0~$a3에, 돌아갈 주소를 $ra에 먼저 담는다: MIPS 프로시저 호출.

확인 문제

C1 이 기계에서 메모리에 닿는 명령 둘을 쓰고, lw $r0 8($sp)가 하는 일을 말로 쓰라. 여기서 $sp는 무엇을 가리키는가?

답: lw(꺼내 오기)와 sw(넣어 두기). lw $r0 8($sp)는 $sp에 든 번지에 8을 더한 곳의 32비트 값을 $r0에 넣는다. $sp는 스택 꼭대기 바로 다음 자리, 곧 다음에 쓸 빈칸을 가리킨다.
이유: 나머지 명령은 모두 레지스터나 즉시값만 쓴다. 그래서 메모리에 있는 변수로 계산하려면 반드시 lw가 먼저 나온다.

C2 다음 네 줄을 차례로 실행한 뒤 $r1, $r2, $r3의 값은? li $r0 5 / subi $r1 $r0 2 / slti $r2 $r1 3 / sgt $r3 $r0 $r1

답: $r1 = 3, $r2 = 0, $r3 = 1.
이유: $r0 = 5, $r1 = 5 − 2 = 3. slti는 3 < 3이 거짓이라 0을 넣는다. sgt는 5 > 3이 참이라 1을 넣는다. 흔한 오답은 slti $r2 $r1 3을 “3 이하”로 읽어 1이라 하는 것이다. lt는 작다이고, 작거나 같다는 le다.

C3 $r0에 든 값이 0이 아닐 때 L1으로 가게 하려 한다. ① beqz $r0 L1 ② bnez $r0 L1 ③ bnei $r0 0 L1 ④ j L1 가운데 맞는 것을 모두 고르라.

답: ②와 ③.
이유: ①은 0일 때 가므로 반대다. ④는 값을 보지 않고 늘 간다. ②는 “0이 아니면”, ③은 “즉시값 0과 다르면”이라 같은 일을 한다.

C4 카드 C2의 뒤 세 줄 가운데 subi $r1 $r0 2와 sgt $r3 $r0 $r1, 그리고 bnez $r3 L을 실제 MIPS 명령으로 옮겨라. $r0~$r3은 $t0~$t3으로 적는다.

답: addi $t1, $t0, -2 / slt $t3, $t1, $t0 / bne $t3, $zero, L.
이유: 실제 기계어에는 subi가 없어 addi에 음수를 적는다. “크다”를 묻는 명령이 없어 $t0 > $t1을 $t1 < $t0으로 바꿔 slt에 넣는다. bnez는 bne에 $zero를 넣은 것이다. $t0 = 5에서 돌리면 $t1 = 3, $t3 = 1이고 L로 간다3.

  1. 흉내기는 참을 1로 두었다. ↩

  2. 레지스터 이름과 쉼표 표기, addi만 있고 subi 기계 명령이 없는 것, jal이 $ra에 돌아올 주소를 넣는 것은 MIPS32 명령 집합과 표준 어셈블러 표기에 따른 것이다(Patterson·Hennessy, Computer Organization and Design, MIPS판 2장). ↩ ↩2

  3. 명령의 유무와 의사 명령(blt, bgt, ble, bge, li, move)은 MIPS Reference Data(Green Sheet, https://www.comp.nus.edu.sg/~cs2100/lect/MIPS_Reference_Data_page1.pdf)의 CORE INSTRUCTION SET과 PSEUDOINSTRUCTION SET 표를 따랐다. 카드 C4의 값은 17_mips-branch-jump_verify.py의 MIPS 흉내기로 확인했다. ↩ ↩2