MIPS 제어 명령어와 J-type — 분기, 점프, if와 while

1. PC를 바꾸는 명령어

앞 글에서 본 명령어는 전부 위에서 아래로 한 줄씩 실행됐습니다. 다음 줄이 어디인지는 PC, 프로그램 카운터가 들고 있습니다. 명령어 하나가 4바이트이니 PC는 보통 4씩 늘어납니다. 그런데 if와 while은 다음 줄로 안 가고 다른 곳으로 뜁니다. 그러려면 PC에 다른 값을 넣어야 합니다. PC를 바꾸는 명령어가 제어 명령어입니다. 이 글에서는 조건 분기와 무조건 점프 두 종류를 보고, 문제 다섯 개를 풉니다.

2. 조건 분기 beq · bne

beq $s1, $s2, label. 두 레지스터가 같으면 label로 뜁니다. bne는 반대로, 다르면 뜁니다. 둘 다 I-type입니다. 뒤쪽 16비트가 통째로 상수 칸인 형식입니다. 맨 앞 6비트 op가 어떤 명령어인지 정하고, 뒤따르는 rs와 rt 칸이 레지스터를 가리킵니다.

beq의 op는 4, bne는 5입니다. rs와 rt에 비교할 레지스터 둘이 들어가고, 남은 16비트에 label까지의 거리가 들어갑니다. 거리는 바이트가 아니라 명령어 개수입니다. 명령어 하나가 4바이트이니, 목적지 주소는 PC에 거리 곱하기 4를 더한 값입니다. 거리가 25이면 PC에서 100바이트 뒤로 뜁니다.

3. 작다는 없다 — slt · slti

같다, 다르다는 있는데 작으면 뛰는 명령어는 따로 없습니다. 대신 set less than, slt가 있습니다. slt $s1, $s2, $s3. $s2가 $s3보다 작으면 $s1에 1을, 아니면 0을 넣습니다. 뛰지 않고 값만 만듭니다.

그 값을 항상 0이 들어 있는 $zero와 beq나 bne로 비교하면 작을 때 뛰는 분기가 만들어집니다. 한 줄로 하던 일을 두 줄로 나눈 것입니다. slti는 레지스터 대신 상수와 비교하는 I-type 버전입니다.

4. 무조건 점프 j · jr · jal

남은 것은 조건 없이 뛰는 쪽입니다. 그 명령어가 j, 무조건 점프입니다. 조건을 보지 않고 PC에 새 값을 넣습니다. 세 번째 형식 J-type이 여기서 나옵니다.

J-type:  op (6비트) | 목적지 (26비트)

레지스터 칸이 없으니 26비트가 통째로 주소입니다. jr은 명령어에 주소를 적는 대신 레지스터에 든 주소로 뜁니다. 주소가 레지스터에 있으니 형식은 R-type입니다.

짝이 되는 명령어가 jal, jump and link입니다. 뛰기 전에 돌아올 주소인 PC 더하기 4를 $ra에 남깁니다. $ra는 돌아올 주소를 담아 두는 레지스터입니다. 함수를 부를 때 jal로 가고, 끝나면 jr $ra로 돌아옵니다.

5. 문제 1 — if x < y

x가 y보다 작으면 z는 x 더하기 y, 아니면 x 빼기 y입니다. x, y, z는 $s0, $s1, $s2입니다.

      slt $t0, $s0, $s1     # x < y 이면 $t0 = 1
      beq $t0, $zero, Less  # $t0가 0이면 Less로
      add $s2, $s0, $s1
      j   Exit              # 뺄셈을 건너뜀
Less: sub $s2, $s0, $s1
Exit:

이름이 Less인데 0일 때 뜁니다. 여기서는 뛰는 쪽에 뺄셈을 두기로 했기 때문입니다. Exit에서 두 경로가 다시 만납니다. 경로가 둘이니 건너뛰는 점프가 하나 필요하고, 방금 본 j가 여기에 쓰입니다.

6. 문제 2 — 26비트로 32비트 주소 만들기

j의 목적지 칸은 26비트뿐인데 주소는 32비트입니다. 모자란 6비트를 어디선가 채워야 합니다. 채워 오는 곳이 두 군데입니다.

1. 아래쪽 2비트 — 명령어는 4바이트 경계에 있으니 주소의 마지막 두 비트는 항상 0입니다. 늘 0인 자리를 명령어에 담을 이유가 없습니다. 26비트를 왼쪽으로 2칸 밀면 28비트가 됩니다.
2. 위쪽 4비트 — PC 더하기 4에서 그대로 가져옵니다.

숫자로 해 봅니다. PC는 0xa7f8001c, 26비트 칸의 값은 0x1fe0004입니다. 16진수는 네 비트를 한 글자로 묶어 적는 방법입니다. 26비트 칸의 값을 왼쪽으로 2칸 밀면 0x7f80010, 이것이 목적지의 아래 28비트입니다. 상위 4비트는 PC 더하기 4의 맨 앞 한 글자에서 가져옵니다. 그 글자는 16진수로 a, 2진수로 1010입니다. 앞에 붙이면 목적지는 0xa7f80010입니다.

두 가지를 확인합니다. 마지막 두 비트가 0이니 4바이트 경계가 맞습니다. 그리고 상위 4비트는 PC와 같은 a 그대로입니다. 점프는 이 4비트를 바꿀 수 없습니다.

7. 문제 3 — 뛸 수 있는 거리

칸이 모자라 어딘가에서 채워 온다는 것은, 뛸 수 있는 거리에 한계가 있다는 뜻입니다.

• beq — 16비트 거리는 부호가 있어 −2¹⁵부터 2¹⁵−1까지입니다. 명령어로 32768개, 바이트로는 앞뒤 128킬로바이트입니다. 어떤 PC에서 출발하든 앞뒤로 128킬로바이트 안입니다.
• j — 28비트를 채우고 상위 4비트는 PC에서 오니, PC와 상위 4비트가 같은 블록 안이면 어디든 갑니다. 그 블록의 크기는 2²⁸, 256메가바이트입니다. 앞의 예라면 상위 4비트가 a인 0xa0000000부터 0xafffffff까지입니다.
• jr — 그보다 멀리 가야 하면 씁니다. 레지스터에는 32비트가 통째로 들어가니 제한이 없습니다.

8. 문제 4 — goto가 섞인 if

i와 j가 같으면 L0로 가고, 아니면 i가 j 이상일 때 F는 G 더하기 H, 작을 때 G 빼기 H입니다. i, j는 $s3, $s4, G, H, F는 $s0, $s1, $s2로 둡니다. 이상은 작지 않다는 뜻이니 slt로 작은지 먼저 만듭니다.

      beq $s3, $s4, L0
      slt $t0, $s3, $s4
      bne $t0, $zero, Else  # 작을 때만 뺄셈으로
      add $s2, $s0, $s1
      j   Exit
Else: sub $s2, $s0, $s1
Exit:

앞 문제와 뼈대가 같습니다. slt 한 줄, 분기 한 줄, 두 경로, 점프 하나입니다.

9. 문제 5 — while

i는 0에서 시작하고, A[i]가 0인 동안 i를 1씩 올립니다. 반복은 위로 되돌아가는 점프입니다. i를 $s3, A의 시작 주소를 $s6에 둡니다. A[i]를 읽으려면 인덱스에 4를 곱해야 합니다. 왼쪽으로 2칸 밀면 4를 곱한 것입니다.

Loop: sll  $t1, $s3, 2      # i × 4
      add  $t1, $t1, $s6    # A[i]의 주소
      lw   $t0, 0($t1)
      bne  $t0, $zero, Exit # 0이 아니면 빠져나감
      addi $s3, $s3, 1
      j    Loop
Exit:

조건이 0이 아니라 다른 값과 비교하는 경우도 뼈대는 같습니다. $zero 자리에 그 값이 든 레지스터를 넣으면 끝입니다.

10. &와 &&

C의 &와 &&는 명령어로 어떻게 다를까요. &는 비트 연산이니 and 명령어 한 줄입니다. &&는 참과 거짓입니다. 앞이 거짓이면 뒤는 보지도 않습니다. 그래서 beq로 앞 조건을 검사해 거짓이면 뒤를 건너뛰는 분기가 됩니다. 하나는 산술 논리 명령어, 하나는 제어 명령어로 바뀝니다.

정리

이것으로 형식 세 가지가 다 모였습니다. 레지스터끼리는 R, 상수와 오프셋과 분기 거리는 I, 멀리 뛰는 주소는 J입니다. beq와 bne는 PC에 거리를 더하고, j와 jal은 PC를 통째로 바꿉니다. if는 slt 더하기 분기, 반복은 위로 돌아가는 j입니다. 여기까지가 명령어를 읽는 법입니다. add 한 줄이 프로세서 안에서 실제로 어떻게 계산되는지는 다음 글에서 봅니다.