yeolyi.com성열의 컴퓨터공학

만약에 그동안 내가 점프를 하면

조건과 반복

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

어셈블리어에서는 조건에 따라 다른 줄을 실행하거나 같은 줄을 반복하려면 JZ와 JUMP를 썼습니다. 고급 언어에서는 이를 if와 while로 적습니다. 그런데 JZ는 두 값이 같은지만 알려 줍니다. a > b처럼 크기를 비교하려면 어떻게 해야 할까요?

크기 비교

A − B에서 빌림이 생기면 A가 B보다 작다는 뜻입니다. 식 글에서 이 빌림을 C 플래그에 남겼으니 크기 비교에 그대로 씁니다.

조건 점프도 넷으로 늘립니다. Z가 1이면(JZ), 0이면(JNZ), C가 1이면(JC), 0이면(JNC) 점프합니다. JC와 JNC도 하드웨어 구현은 살펴보지 않습니다.

음수 비교

short는 음수도 담습니다. −1은 16비트로 1111111111111111이라, 빌림만 보면 1보다 큰 수로 비교됩니다. 그래서 컴파일러는 두 수의 위 8비트에 128을 더한 뒤 뺍니다. 맨 앞 비트가 뒤집혀 −32768~32767이 순서 그대로 0~65535로 옮겨 가니, 빌림이 다시 크기를 알려 줍니다.

if와 else

컴파일러는 if를 늘 같은 템플릿으로 옮깁니다. 조건을 계산해 거짓이면 else 쪽 첫 줄(else1)로 점프하고, 참인 쪽 끝에서는 JUMP로 else 쪽을 건너뛰어 end1로 갑니다.

C
1int main(void) {
2 short a = 7;
3 short b = 3;
4 short m;
5 if (a > b)
6 m = a;
7 else
8 m = b;
9}
어셈블리어
0–1LDI R0, 7
2–3LDI R1, 0
4–5STORE R0, a
6–7STORE R1, a+1
8–9LDI R0, 3
10–11LDI R1, 0
12–13STORE R0, b
14–15STORE R1, b+1
16–17LOAD R0, b
18–19LOAD R1, b+1
20–21ADDI R1, 128
22–23LOAD R2, a
24–25LOAD R3, a+1
26–27ADDI R3, 128
28–29SUB R0, R2
30–31SBC R1, R3
32–33JNC else1
34–35LOAD R0, a
36–37LOAD R1, a+1
38–39STORE R0, m
40–41STORE R1, m+1
42–43JUMP end1
44–45else1: LOAD R0, b
46–47LOAD R1, b+1
48–49STORE R0, m
50–51STORE R1, m+1
52–53end1: HALT
54–55a: 0, 0
56–57b: 0, 0
58–59m: 0, 0
R0 0R1 0R2 0R3 0Z 0C 0
a@54 0b@56 0m@58 0
  1. 재생해 C 플래그와 건너뛰는 줄을 봅시다.
  2. a를 -2로 고치고 다시 실행해 봅시다.

크기 비교는 C로, ==와 !=는 Z로 봅니다. SBC는 앞 바이트의 Z가 1이고 자기 결과도 0일 때만 Z를 1로 남기니, 두 바이트가 다 같아야 Z가 1입니다.

while

while도 늘 같은 템플릿으로 옮깁니다. 맨 위(loop1)에서 조건을 계산해 거짓이면 반복 밖(done1)으로 점프하고, 안쪽 끝에서는 JUMP로 loop1로 돌아갑니다.

n != 0처럼 0과 비교할 때는 빼지 않고 두 바이트를 OR합니다. 비트마다 OR를 하는 OR 명령어를 더합시다. 두 바이트가 모두 0일 때만 결과가 0이라 Z가 1이 됩니다. 같은 방식으로 AND와 XOR도 더합니다. 분량상 하드웨어로 어떻게 만드는지는 살펴보지 않습니다.

C
1int main(void) {
2 short n = 4;
3 short s = 0;
4 while (n != 0) {
5 s = s + n;
6 n = n - 1;
7 }
8}
어셈블리어
0–1LDI R2, 4
2–3LDI R3, 0
4–5LDI R0, 0
6–7LDI R1, 0
8–9STORE R0, s
10–11STORE R1, s+1
12–13loop1: MOVE R0, R2
14–15OR R0, R3
16–17JZ done1
18–19LOAD R0, s
20–21LOAD R1, s+1
22–23ADD R0, R2
24–25ADC R1, R3
26–27STORE R0, s
28–29STORE R1, s+1
30–31SUBI R2, 1
32–33SBCI R3, 0
34–35JUMP loop1
36–37done1: HALT
38–39s: 0, 0
R0 0R1 0R2 0R3 0Z 0C 0
n@R3:R2 0s@38 0

재생해 봅시다. 4번 줄의 명령어로 몇 번 돌아오나요?

구조적 프로그래밍

언어는 왜 if와 while만 둘까요?

어셈블리어처럼 아무 곳으로나 점프하면, 어떤 줄을 이해하려 할 때 그 줄로 점프해 들어오는 곳을 프로그램 전체에서 모두 찾아야 합니다. if와 while로 만든 덩어리는 늘 위에서 들어와 아래로 나가니 따로 떼어 읽어도 됩니다.

1966년 뵘과 야코피니는 점프로 짠 어떤 프로그램이든 순차적으로 실행하기, if, while 셋만으로 같은 일을 하게 다시 쓸 수 있음을 증명했습니다. 이를 구조적 프로그램 정리(structured program theorem)라 합니다.

그런데 당시 언어에는 아무 줄로나 점프하는 goto도 있었습니다. 1968년 다익스트라는 「Go To 문은 해롭다」라는 글에서 goto를 많이 쓸수록 프로그램을 이해하기 어려워진다며 쓰지 말자고 주장했습니다.

이렇게 셋으로만 짜는 방식을 구조적 프로그래밍(structured programming)이라 합니다.

마무리

다음 글에서는 값 여러 개를 한 이름에 담아 번호로 꺼내 쓰게 해 주는 배열을 살펴봅시다.

도전 문제

아래 프로그램을 이 글의 규칙대로 컴파일해 실행하면, 점프 명령어(JUMP, JZ, JNZ, JC, JNC)가 실제로 PC를 바꾼 것은 모두 몇 번일까요? 조건이 맞지 않아 그대로 다음 줄로 간 것은 세지 않습니다. 숫자로 답하세요.

int main(void) {
  short n = 5;
  short s = 0;
  while (n != 0) {
    if (n > 2)
      s = s + n;
    n = n - 1;
  }
}