yeolyi.com성열의 컴퓨터공학

계산식 나무로 만들기

식

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

16비트 덧셈 글에서는 a + b처럼 연산이 하나인 식을 옮겼습니다. short c = a - b + 1;처럼 연산이 여럿 섞인 줄은 어떤 명령어로 옮기면 될까요?

식 트리

a - b + 1처럼 값과 연산을 엮은 것을 식(expression)이라 합니다. 컴파일러는 식을 트리(tree)로 바꿉니다. +나 - 같은 연산이 노드가 되고, 그 연산의 왼쪽 값과 오른쪽 값이 자식이 됩니다. 괄호로 묶은 부분은 서브트리 하나가 됩니다.

c =
+−ab1

괄호를 넣어 a - (b + 1)로 바꿔 봅시다.

아래부터 계산하기

short c = a - b + 1;을 맨 아래부터 계산해 봅시다.

  1. a를 LOAD 두 번으로 R1:R0에 가져옵니다.
  2. −는 b의 아래 8비트를 R2에 가져와 SUB로, 위 8비트를 가져와 SBC로 뺍니다.
  3. +1은 ADDI R0, 1과 ADCI R1, 0입니다. 위 8비트에는 올림만 보탭니다.
  4. STORE 두 번으로 c에 씁니다.
c =
+−ab1
컴파일한 명령어
1LOAD R0, a
2LOAD R1, a+1
3LOAD R2, b
4SUB R0, R2
5LOAD R2, b+1
6SBC R1, R2
7ADDI R0, 1
8ADCI R1, 0
9STORE R0, c
10STORE R1, c+1

식 끝의 1을 d로 바꿔 봅시다. ADDI·ADCI가 LOAD·ADD·LOAD·ADC 네 줄이 됩니다.

레지스터 나눠 쓰기

레지스터 넷으로는 값을 둘(R1:R0, R3:R2)만 들 수 있습니다. 왼쪽 자식은 부모와 같은 짝에 둡니다. 오른쪽 자식을 계산하는 동안 왼쪽 값을 들고 있어야 하니 오른쪽 자식은 다음 짝을 씁니다.

c =
−R1:R0+R1:R0aR1:R0b없음−R3:R2aR3:R21값
컴파일한 명령어
1LOAD R0, a
2LOAD R1, a+1
3LOAD R2, b
4ADD R0, R2
5LOAD R2, b+1
6ADC R1, R2
7LOAD R2, a
8LOAD R3, a+1
9SUBI R2, 1
10SBCI R3, 0
11SUB R0, R2
12SBC R1, R3
13STORE R0, c
14STORE R1, c+1

트리 옆의 R1:R0, R3:R2가 그 값이 놓일 레지스터입니다. 괄호 안을 계산하는 동안 R3:R2를 씁니다.

레지스터가 모자랄 때

a - (b - c)에서는 a가 R1:R0에서, b가 R3:R2에서 기다리니 c를 가져올 레지스터가 없습니다.

R1을 메모리의 임시 칸 tmp1에 내려놓고, 빈 R1로 c를 가져와 b에서 뺀 뒤 tmp1을 다시 R1로 가져옵니다. 이렇게 레지스터 값을 메모리에 내려놓는 것을 스필(spill)이라 합니다.

c =
−R1:R0aR1:R0−R3:R2bR3:R2c없음
컴파일한 명령어
1LOAD R0, a
2LOAD R1, a+1
3LOAD R2, b
4LOAD R3, b+1
5STORE R1, tmp1
6LOAD R1, c
7SUB R2, R1
8LOAD R1, c+1
9SBC R3, R1
10LOAD R1, tmp1
11SUB R0, R2
12SBC R1, R3
13STORE R0, c
14STORE R1, c+1

명령어에서 R1을 tmp1에 내려놓고 다시 가져오는 두 줄을 찾아봅시다.

컴파일한 프로그램 실행

C
1int main(void) {
2 short a = 2;
3 short b = 3;
4 short c = a + b - (a - 1);
5}
어셈블리어와 기계어
0–1LDI R0, 201100000 00000010
2–3LDI R1, 001100100 00000000
4–5STORE R0, a10010000 00101110
6–7STORE R1, a+110010100 00101111
8–9LDI R0, 301100000 00000011
10–11LDI R1, 001100100 00000000
12–13STORE R0, b10010000 00110000
14–15STORE R1, b+110010100 00110001
16–17LOAD R0, a10000000 00101110
18–19LOAD R1, a+110000100 00101111
20–21LOAD R2, b10001000 00110000
22–23ADD R0, R200010010 00000000
24–25LOAD R2, b+110001000 00110001
26–27ADC R1, R200010110 00000001
28–29LOAD R2, a10001000 00101110
30–31LOAD R3, a+110001100 00101111
32–33SUBI R2, 101011000 00000001
34–35SBCI R3, 001011101 00000000
36–37SUB R0, R200100010 00000000
38–39SBC R1, R300100111 00000001
40–41STORE R0, c10010000 00110010
42–43STORE R1, c+110010100 00110011
44–45HALT11110000 00000000
46–47a: 0, 0
48–49b: 0, 0
50–51c: 0, 0
R0 0R1 0R2 0R3 0Z 0
a@46 0b@48 0c@50 0
  1. 다음을 누르며 레지스터에 값이 모였다가 합쳐지는 것을 봅시다.
  2. 코드 줄에 커서를 두면 그 줄의 명령어가 칠해집니다.
  3. 식을 마음대로 고쳐 봅시다. 고치는 대로 다시 컴파일됩니다.

마무리

다음 글에서는 자주 쓰는 변수를 레지스터에 두어 메모리를 덜 오가게 해 주는 레지스터 할당을 살펴봅시다.

도전 문제

다음 식을 이 글의 컴파일러로 옮길 때 스필이 생기는 것은?