서랍에 든 서류로 일하려면 꺼내서 책상에 놓고, 고치고, 다시 서랍에 넣는다. 컴파일러가 계산 한 줄을 기계 명령으로 옮길 때도 이 세 걸음을 그대로 찍어 낸다. 변수의 값을 메모리에서 꺼내고, 계산하고, 결과를 메모리에 넣는다. 조건에 따라 건너뛰는 줄은 조건 값을 꺼내서 0인지 보고 뛰는 두 걸음이 된다. 줄마다 따로 옮기니 만들기는 아주 쉽다. 대신 방금 넣은 값을 바로 다음 줄에서 다시 꺼내는 헛일이 많이 생긴다.
예시로 보기
코드 생성용 MIPS 명령어에서 본 것처럼 이 기계는 메모리에 있는 값끼리 바로 계산하지 못한다. 그런데 3주소 코드의 변수는 모두 메모리에 있다. 지금 도는 함수의 지역 변수이므로 그 함수의 활성 레코드, 곧 스택에 이미 자리가 있다.
3주소 코드 a = b + c를 옮긴다. 스택은 이런 모습이다. $sp는 스택 꼭대기 바로 다음의 빈칸을 가리킨다.
높은 번지 | ... |
+---------+
$sp + 12 | a |
+---------+
$sp + 8 | b |
+---------+
$sp + 4 | c |
+---------+
$sp ---> | (빈칸) |
낮은 번지 +---------+
변수마다 $sp에서 몇 바이트 떨어져 있는지는 심벌 테이블에 적혀 있다. 옮기는 걸음은 셋이다.
| 걸음 | 하는 일 | 명령 |
|---|---|---|
| 1 | 변수를 메모리에서 레지스터로 꺼낸다 | lw $r0 8($sp) (b), lw $r1 4($sp) (c) |
| 2 | 레지스터끼리 더한다 | add $r2 $r0 $r1 |
| 3 | 결과를 메모리에 넣는다 | sw $r2 12($sp) (a) |
b = 2, c = 5로 돌리면 $r0 = 2, $r1 = 5, $r2 = 7이 되고 $sp + 12번지에 7이 들어간다.
a = b + c는 −3~3의 모든 쌍, 반복문은 x, y가 −2~5인 모든 쌍, 무작위 직선 코드 500개), 메모리 읽기·쓰기 횟수 — 52_codegen-simple-operations_impl.py. 실제 MIPS 어셈블러로 돌린 것이 아니다.옮기는 규칙
3주소 코드의 줄 모양마다 찍어 낼 명령이 정해져 있다. off(x)는 심벌 테이블에 적힌 변수 x의 오프셋이다. 줄마다 레지스터 번호를 $r0부터 새로 쓴다.
| 3주소 코드 | 찍어 내는 명령 |
|---|---|
x = y op z (둘 다 변수) |
lw $r0 off(y)($sp) / lw $r1 off(z)($sp) / (op 명령) $r2 $r0 $r1 / sw $r2 off(x)($sp) |
x = y op 상수 |
lw $r0 off(y)($sp) / (op 명령)i $r1 $r0 상수 / sw $r1 off(x)($sp) |
if x goto L |
lw $r0 off(x)($sp) / bnez $r0 L |
ifnot x goto L |
lw $r0 off(x)($sp) / beqz $r0 L |
goto L |
j L |
L: |
L: |
op 명령은 연산자에 맞는 명령이다. +는 add, -는 sub, *는 mul, /는 div, <는 slt, <=는 sle, >는 sgt, >=는 sge, ==는 seq, !=는 sne다. 오른쪽이 상수면 끝에 i가 붙은 즉시값 명령을 써서 꺼내 오기 한 번을 아낀다.
비교. a = b < 3은 a가 $sp + 8, b가 $sp + 4에 있을 때 이렇게 된다.
lw $r0 4($sp) # b를 꺼낸다
slti $r1 $r0 3 # $r1 = ($r0 < 3)
sw $r1 8($sp) # a에 넣는다
조건 분기. 조건이 참이면 뛰는 줄은 “0이 아니면 뛴다”가 된다. 참을 0이 아닌 값으로 적어 두었기 때문이다. t0가 $sp + 8, b가 $sp + 4에 있다.
[3주소 코드] [어셈블리]
t0 = b < 3 lw $r0 4($sp)
slti $r1 $r0 3
sw $r1 8($sp)
if t0 goto L0 lw $r0 8($sp)
bnez $r0 L0
L0: L0:
예제
반복문. t0는 $sp + 12, x는 $sp + 8, y는 $sp + 4에 있다.
[3주소 코드] [어셈블리]
L0: L0:
t0 = x < y lw $r0 8($sp) # x
lw $r1 4($sp) # y
slt $r2 $r0 $r1
sw $r2 12($sp) # t0
ifnot t0 goto L1 lw $r0 12($sp) # t0
beqz $r0 L1
x = x + 1 lw $r0 8($sp) # x
addi $r1 $r0 1
sw $r1 8($sp) # x
goto L0 j L0
L1: L1:
x = 0, y = 3으로 돌린 흐름이다1.
| 바퀴 | 들어올 때 x | t0 = x < y |
beqz |
나갈 때 x |
|---|---|---|---|---|
| 1 | 0 | 1 | 안 뛴다 | 1 |
| 2 | 1 | 1 | 안 뛴다 | 2 |
| 3 | 2 | 1 | 안 뛴다 | 3 |
| 4 | 3 | 0 | L1로 뛴다 |
3 |
세 바퀴 돌고 넷째 검사에서 나온다. 그동안 메모리 읽기(lw)가 15번, 쓰기(sw)가 7번 일어난다. 한 바퀴에 읽기 4번과 쓰기 2번이고, 마지막 검사에 읽기 3번과 쓰기 1번이다.
헛일이 생기는 곳. 위 어셈블리의 넷째와 다섯째 명령을 보면 sw $r2 12($sp)로 t0를 메모리에 넣자마자 lw $r0 12($sp)로 다시 꺼낸다. 값은 방금까지 $r2에 있었다. 줄마다 따로 옮기기 때문에 생기는 일이다. 이 방식의 문제는 둘이다.
- 레지스터가 끝없이 많다고 쳤는데 실제로는 수가 정해져 있다.
- 조각마다 그대로 옮기면 만들기는 간단하지만 효율을 잃는다. 필요 없는 꺼내 오기와 넣어 두기가 나온다.
둘 다 레지스터를 더 잘 나눠 써서 푼다(레지스터 간섭 그래프, 그래프 색칠 레지스터 할당).
활용
- 구현: 52_codegen-simple-operations_impl.py. 연습: 코드 생성 연습
- 비용: 3주소 코드 한 줄이 명령 2~4줄이 된다. 줄 수에 비례하는 시간에 끝난다. 앞뒤 줄을 보지 않으므로 한 줄씩 읽으면서 바로 찍어 낼 수 있다.
- 흔한 실수: 오프셋을 변수의 순서로 착각한다. 오프셋은
$sp에서 떨어진 바이트 수이고, 그림에서 위에 있는(높은 번지의) 변수일수록 크다. - 흔한 실수:
if x goto L에beqz를 쓴다. 참일 때 뛰어야 하므로 “0이 아니면”인bnez다.ifnot이beqz다. - 흔한 실수:
x = x + 1에서 결과를 넣는sw를 빼먹는다.addi는 레지스터만 바꾼다. 메모리의 x는sw를 해야 바뀐다.
연결
- 선수: 코드 생성용 MIPS 명령어, 3주소 코드, 활성 레코드
- 변수의 오프셋을 적어 두는 곳: 심벌 테이블과 스코프 검사
- 함수 호출 줄(
param,call,return)을 옮기는 법: 함수 호출의 코드 생성 - x86에서 같은 일을 하는 명령: 비교한 뒤 플래그를 보고 뛰는 조건 점프, 값을 담는 x86 레지스터
확인 문제
C1 예제의 반복문 어셈블리를 x = 1, y = 3으로 돌린다. 끝났을 때 메모리의 x와 t0는? lw와 sw는 각각 몇 번 실행되는가?
답: x = 3, t0 = 0. lw 11번, sw 5번.
이유: 두 바퀴를 돈다(x가 1 → 2 → 3). 한 바퀴에 lw 4번(x, y, t0, x)과 sw 2번(t0, x)이다. 마지막 검사에서 lw 3번(x, y, t0)과 sw 1번(t0)이 더 나온다. 4 × 2 + 3 = 11, 2 × 2 + 1 = 5. 흔한 오답은 마지막 검사를 빼고 8번, 4번이라 답하는 것이다.
C2 lw $r0 8($sp) / addi $r1 $r0 1 / sw $r1 8($sp) 세 줄이 하는 일을 한 문장으로 쓰라. 가운데 줄만 있으면 왜 안 되는가?
답: $sp + 8번지에 있는 변수의 값을 1 늘린다(x = x + 1). addi는 레지스터끼리만 계산하므로, 앞의 lw가 없으면 $r0에 x가 들어 있지 않고, 뒤의 sw가 없으면 늘어난 값이 메모리의 x에 닿지 않는다.
C3 d가 $sp + 16, a가 $sp + 12에 있다. 3주소 코드 d = a * 4를 옮기라. 메모리 읽기는 몇 번인가?
답: lw $r0 12($sp) / muli $r1 $r0 4 / sw $r1 16($sp). 읽기 1번, 쓰기 1번.
이유: 오른쪽 4가 상수라서 즉시값 명령 muli를 쓴다. 4를 레지스터에 따로 넣을 필요가 없어 명령이 넷이 아니라 셋이다.
C4 3주소 코드 if x goto L과 ifnot x goto L을 옮길 때 각각 bnez와 beqz 가운데 무엇을 쓰는가? 반대로 쓰면 반복문 예제는 어떻게 되는가?
답: if x goto L은 bnez(0이 아니면 뛴다), ifnot x goto L은 beqz(0이면 뛴다)다.
이유: 참은 0이 아닌 값이다. if는 참일 때 뛰어야 하므로 “0이 아니면”을 쓴다. 반대로 쓰면 조건이 참일 때 반복문을 빠져나가고 거짓일 때 몸통을 돌아, 원래 코드와 정반대로 움직인다.
-
파이썬 흉내기로 돌려 확인했다. ↩