[Chapter 2. 명령어: 컴퓨터 언어] 판단을 위한 명령어, MIPS 명령어 형식 : J-format

* 본 글은 '컴퓨터 구조 및 설계: 하드웨어/소프트웨어 인터페이스(Computer Organization and Design: The Hardware/Software Interface) 5th edition'의 내용과 2021학년도 1학기에 수강한 '컴퓨터 구조' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

조건 명령어 (Conditional Operations)

---

조건부 분기 (Conditional Branch)

컴퓨터는 판단 기능이 있어, 입력 데이터나 연산 결과에 따라 다른 명령어를 실행할 수 있다.

우리가 프로그래밍을 할 때 if 문이나 go to 문과 같은 조건문을 사용하여 판단 기능을 표한다.

 

 

MIPS 명령어로는 아래의 2가지가 존재하며, 이 두 명령어를 조건부 분기(conditional branch)라 부른다.

 

* 조건부 분기 (conditional branch)

: 두 값의 비교가 필요한 명령어로, 비교 결과에 따라 프로그램 내의 새로운 주소로 제어를 넘길 수 있게 한다.

 

1. beq(branch on equal)

bne rs, rt, L1	  # if (rs != rt) branch to instruction labeled L1

레지스터 rs와 rt의 값이 같으면 L1에 해당하는 문장으로 가라는 뜻이다.

 

2. bne(branch on not equal)

beq rs, rt, L1	  # if (rs == rt) branch to instruction labeled L1

레지스터 rs와 rt의 값이 다르면 L1에 해당하는 문장으로 가라는 뜻이다.

 

 

beq와 bne는 I-format을 따르며, 16비트 주소 필드에는 target address가 들어간다.

* target address : 현재 읽고 있는 명령어에서부터의 상대적인 거리

 

 

무조건 분기 (Unconditional Branch)

무조건 분기(unconditional branch)로는 jump 명령어가 있다. (jump라는 이름을 붙이고 간략하게 j로 사용)

이 명령어는 프로세서에게 항상 분기하라고 말한다.

 

jump는 J-format을 따른다. (자세한 설명은 후에 할 예정)

 

 

 

예를 들어, 다음과 같은 C 코드가 있다고 하자.

if (i == j) f = g + h;
else f = g - h;

 

이를 MIPS 어셈블리 언어로 컴파일한다면 다음과 같을 것이다.

bne $s3, $s4, Else		# go to Else if i
add $s0, $s1, $s2		# f = g + h (skipped if i != j)
j Exit				# go to Exit
Else: sub $s0, $s1, $s2		# f = g - h (skipped if i = j)
Exit: ...

Else나 Exit으로의 분기 주소 계산은 어셈블러가 한다.

 

 

순환문은 어떻게 컴파일될까?

while (save[i] == k) i += 1;

 

배열 save의 시작 주소가 $s6에 저장되어 있고, i와 k는 각각 레지스터 $s3와 $s5에 할당되었다고 할 때

MIPS 어셈블리 언어는 다음과 같을 것이다.

Loop: sll  $t1, $s3, 2		# Temp reg $t1 = i * 4
      add  $t1, $t1, $s6	# $t1 = address of save[i]
      lw   $t0, 0($t1)		# Temp reg $t0 = save[i]
      bne  $t0, $s5, Exit	# go to Exit if save[i] != k
      addi $s3, $s3, 1		# i = i + 1
      j    Loop			# go to Loop
Exit: ...

 

1. sll $t1, $s3, 2 → add $t1, $t1, $s6

순환의 끝에서 처음 명령어로 되돌아갈 수 있도록 Loop이라는 레이블을 추가한다.

 

save[i]의 값을 가져오기 위해서는 먼저 그 주소를 구해야 한다.

바이트 주소 문제 때문에 인덱스 i에 4를 곱해서 save의 시작 주소에 더해야 주소가 만들어진다.

 

2비트씩 왼쪽 자리이동(shift left)을 하면 4를 곱한 것과 같기 때문에

sll 연산을 사용하여 임시 레지스터 $t1에 값을 저장한다. (상대 주소)

 

그 후 $t1 값과 save의 시작 주소를 더하여 save[i]의 주소를 구한다. (절대 주소)

 

2. lw $t0, 0($t1)

$t1에 저장된 주소를 통해 save[i]에 저장된 값을 임시 레지스터 $t0에 저장한다.

 

3. bne $t0, $s5, Exit

반복 검사를 수행해서 save[i] != k이면 순환에서 빠져나가는 부분이다.

 

4. addi $s3, $s3, 1

i에 1을 더하는 명령어이다.

 

5. j Loop

순환문의 끝에서는 맨 앞의 while 조건 검사로 되돌아가야 한다.

 

---

그렇다면 명령어 실행 중, 다음 라벨 혹은 분기점으로 어떻게 넘어가는 것일까?

 

 

PC(Program Counter) 레지스터는 명령어의 주소를 담고 있는 레지스터이다.

원래는 한 사이클마다 PC 레지스터의 값에 4를 더해서 다음 명령어를 실행한다.

 

4를 더하는 이유는 워드(word) address이기 때문이다. (1 word = 4 byte)

 

 

만약 beq 또는 bne가 발생하여 상수값(offset)이 들어오게 된다면

offset+4의 값을 부호 확장(sign extend)하여 PC+4의 값에 더해준다.

 

이때 부호 확장을 하는 이유는 PC가 32비트 값을 가지고 있는 레지스터이기 때문에 비트 수를 맞추기 위해서이다.

 

따라서 다음 명령어의 주소는 PC+4가 아닌, PC+4에 offset*4를 더한 값이 되므로

조건문이 원하는 명령어를 실행하게 되는 것이다.

 

 

이렇게 명령어 내 상수의 합이 실제 주소가 되는 주소 지정을 PC 상대 주소 지정(PC-relative addressing) 방식이라고 한다.

 

 

---

경우에 따라서는 두 변수 간의 대소 비교가 필요할 수 있다.

 

이때는 slt(set on less than)이라는 명령어를 사용한다.

slt $t0, $s0, $s1	# if $s0 < $s1 then
			# $t0 = 1      else
                    	# $t0 = 0

 

두 레지스터의 값을 비교한 후

$s0 < $s1이라면 $t0 =  1, 반대의 경우에는 $t0 = 0이 되는 것이다.

 

이 명령어는 피연산자가 2개이기 때문에 R-format을 따른다.

 

 

slt 명령어에는 여러 가지 대안 버전이 존재한다.

stli  $t0, $s0, 25	# i : immediate           - if $s0 < 25 then $t0 = 1 ...
sltu  $t0, $s0, $s1	# u : unsigned            - if $s0 < $s1 then $t0 = 1 ...
sltiu $t0, $s0, 25	# iu : immediate unsigned - if $s0 < 25 then $t0 = 1 ...

* 부호가 없는 수 : slt, stli

* 부호가 있는 수 : sltu, sltiu

 

부호가 있는 수와 없는 수를 구분해야 하는 이유는

1111 1111 1111 1111가 부호가 없을 때 매우 큰 수이지만, 부호가 있을 때에는 -1인 것처럼 큰 차이가 존재하기 때문이다.

 

 

slt, beq, bne 명령어들과 $zero를 통해 다양한 비교 조건문을 구현할 수 있다.

 

1. blt (branch less than)

blt $s1, $s2, L		# if $s1 < $s2 go to L

slt $at, $s1, $s2	# if $s1 < $s2 then $at = 1
bne $at, $zero, L	# if $at != 0 go to L

 

2. ble (branch less than or equal to)

ble $s1, $s2, L		# if $s1 <= $s2 go to L

slt $at, $s2, $s1	# if $s2 >= $s1 then $at = 0
beq $at, $zero, L	# if $at == 0 go to L

 

3. bgt (branch greater than)

bgt $s1, $s2, L		# if $s1 > $s2 go to L

slt $at, $s2, $s1	# if $s2 < $s1 then $at = 1
bne $at, $zero, L	# if $at != 0 go to L

 

4. bge (branch greater than or equal)

bge $s1, $s2, L		# if $s1 >= $s2 go to L

slt $at, $s1, $s2	# if $s1 >= $s2 then $at = 0
beq $at, $zero, L	# if $at == 0 go to L

 

 

위의 명령어들은 왜 따로 만들지 않고 slt와  beq, bne를 통해서 구현할까?

 

위 명령어들을 직접 만든다면 이들은 너무 복잡해서 별도의 클럭 사이클이 발생하고, 이에 따라 수행 속도가 느려지게 된다.

간단한 설계를 지키기 위해, 그리고 자주 생기는 일을 더 빠르게 만들기 위해 빠른 명령어 두 개를 대신 사용하는 것이다.

 

 

기본 블록 (Basic Block)

분기 명령을 포함하지 않으며 (맨 끝에는 존재 가능)

분기 목적지나 분기 테이블도 없는 (맨 앞에는 존재 가능) 명령어 시퀀스를 말한다.

 

 

컴파일의 초기 단계 작업 중 하나는 프로그램을 기본 블록으로 나누는 일이다.

 

MIPS J-format Instruction

J : Jump

 

 

• op : 명령어가 실행할 연산의 종류로서 연산자(opcode)라고 부른다.
• jump target : jump 할 타겟 주소(상대 주소) 값이 저장된다.

 

무조건 분기 명령어

원하는 명령어로 주소를 바꾸고 싶을 때 사용한다.

j L	# go to L

 

똑같이 PC+4에 26비트의 offset+4 값이 더해져서 다음 명령어의 주소가 바뀌게 된다.

 

 

 

만약 branch 타겟 주소가 16비트로 표현할 수 없는 먼 주소라면 어떻게 해야 할까?

beq $s0, $s1, L1	# L1이 16비트로 나타낼 수 없는 수일 경우

 

j 명령어를 활용하여 다음과 같이 해결할 수 있다.

    bne $s0, $s1, L2	# L2 : L1보다 가까운 주소
    j   L1
 L2: