[컴퓨터 구조] 명령어(Instruction)[5] - 의사 결정 명령어

 

 

 

 

 

🧐 의사 결정 명령어

컴퓨터는 단순히 산술 연산만을 진행하지 않습니다.

입력 데이터나 연산 결과에 따라 다른 명령어를 실행할 수 있습니다. 

 

프로그래밍 언어에서는 보통 if 문장을 통해서 판단 기능을 표현합니다.

 

RISC-V 어셈블리어에서는 go to 가 있는 if 문과 비슷한 판단 명령어를 가집니다.

 

 

두개의 명령어를 본 후 넘어가도록 하겠습니다.

 

⭐️ beq - 같으면 분기한다.

beq rs1, rs2, L1

위 명령어는 rs1의 값이 rs2의 값과 같은 경우 L1으로 이동하라는 뜻입니다.

 

 

 

⭐️ bne - 같지 않으면 분기한다.

bne rs1, rs2, L1

위 명령어는 rs1의 값이 rs2의 값과 같지 않은 경우 L1으로 이동하라는 뜻입니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 조건부 분기 (Conditional branch)

조건부 분기 명령어의 Format은 다음과 같습니다.

 

 

⭐️ SB - format

imm[12]	imm[10:5]	rs2	rs1	funct3	imm[4:1]	imm[11]	opcode
1 bit	6 bit	5 bit	5 bit	3 bit	4 bit	1 bit	7 bit

SB - Format의 B는 Branch를 의미합니다.

 

위 형식은 S-Format과 비슷하지만, 차이점이 있습니다.

 

 

 

S-format과 함께 봐보도록 하겠습니다.

 

SB -	imm[12]	imm[10:5]	rs2	rs1	funct3	imm[4:1]	imm[11]	opcode
	1 bit	6 bit	5 bit	5 bit	3 bit	4 bit	1 bit	7 bit
S -	imm[11:5]		rs2	rs1	funct3	imm[4:0]		opcode
	7 bit		5 bit	5 bit	3 bit	5 bit		7 bit

 

 

 

 

 

 

⭐️ SB - format이 가지는 형태에 대하여

위와 같은 형태를 띄는 이유는 다음과 같습니다.

 

조건부 분기 명령어의 경우 immediate 필드에는 PC(Program counter)에 더해질 offset(다음 instruction과의 주소 차이)이 들어갑니다.

 

instruction은 항상 32비트(4바이트)로 고정되어 있습니다.

 

RISC-V는 Byte Address를 사용하므로, instruction 사이의 간격은 항상 4(byte)의 배수입니다.

 

4의 배수라는 것은, instruction의 주소가 항상 00으로 끝난다는 것을 의미합니다. (4가 100 이므로)

 

즉 뒷자리가 항상 00으로 고정이므로 00을 굳이 표시할 필요가 없어집니다.

 

따라서 00을 표현하기 위한 2비트를 아낄 수 있어서 immediate는 [13 : 2]의 범위를 가질 수 있습니다.

 

그런데 위를 살펴보면 immediate의 범위는 [13 : 2] 가 아닌 [12 : 1] 인 것을 알 수 있습니다.

 

(여기부터는 기억이 잘 안나요.. ㅠㅠ 지송지송 다음에 정리해서 다시 할게요, 일단 그냥 그런갑다 하고 넘기세요 ㅠㅠ)

이는 RISC-V의 명령어가 잘 정렬되어 있기에 2바이트로 압축하여 표현이 가능해지기 때문입니다.

 

명령어를 압축하여 길이를 줄였지만, 그만큼 간격이 줄어들어 아낄 수 있는 비트는 00에서 0으로 바뀝니다.

 

즉 1비트를 아낄 수 있기에 immediate의 범위는 [12 : 1]가 되는 것입니다.

(뇌피셜 끝)

 

 

그럼 두번째 의문으로는 왜 [12 : 6] [5 : 1] 이 아니라 [12] [10 : 5] [4 : 1] [11] 이냐 입니다.

 

기존 S- format에서는 [11 : 5] [4 : 0]을 사용하였습니다.

이를 [12 : 6] [5 : 1]로 표현하면 모든 자리수에 대하여 의미가 바뀝니다.

 

의미를 바꾸지 않고 기존 S-format과 최대한 유사하게 맞추기 위해 [10 : 5] [4 : 1] 을 사용한 것입니다.

 

그럼 [11 : 5] [4 : 1] [12] 가 제일 유사한거 아니냐? 하실 수 있는데, 유사도로만 따지면 맞습니다만, [12]는 MSB라는 것에 집중할 필요가 있습니다.

 

양수인지 음수인지를 판단하는 등의 여러 판단에서, MSB 하나만 보고도 판단 가능한 조건들이 많습니다.

 

이러한 경우 MSB가 뒤에 위치하는 것 보다는, 맨 앞에 위치하여 곧바로 확인할 수 있도록 하는 것이 더 간편합니다.

 

따라서 MSB를 맨 앞으로 오게끔 하며, S- format과 최대한 유사하도록 명령어를 표현하기 위해 위의 형태를 사용하는 것입니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 조건부 분기 번역

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

위의 C 코드를 어셈블리어로 번역해 보도록 하겠습니다.

 

 

 

f는 x19,   g는 x20,   h는 x21,  i는 x22,  j는 x23이 할당됩니다.

         bne x22, x23, Eles  // i(x22)랑 j(x23)랑 같지 않으면 Else로 이동해라
         add x19, x20, x21   // f(x19) = g(x20) + h(x21)
         beq x0, x0, Exit     // 무조건 Exit (무조건 분기 - unconditional branch)
Else:   sub x19, x20, x21   // f(x19) = g(x20) - h(x21)
Exit:   ...

 

 

중요한 점은 조건으로는 i == j 였던 것이 어셈블리어로는 같지 않음(bne)로 번역되었다는 것과,

Else문 위에서 beq x0, x0 Exit을 통해 항상 Exit으로 이동하도록 번역된 점입니다.

 

add 명령을 한 뒤에는 Else : sub ... 가 실행되면 안되기 때문에 beq x0, x0, Exit를 써서 if 문장의 끝부분으로 이동하게 해주었습니다.

이때 사용된 명령을 무조건 분기(unconditional branch)라고 합니다.

 

RISC-V에서는 위와 같은 무조건 분기를 표현하기 위한 한가지 방법으로 조건이 항상 참인 조건부 분기 명령어를 사용합니다.

 

 

 

 

 

 

 

 

 

 

🧐 순환문

판단 기능은 둘 중 하나를 선택(if문장)하는 데에도 중요하지만,

계산의 반복에도 중요합니다.

 

두 경우에 모두 같은 어셈블리 명령어가 사용됩니다.

 

예시는 다음과 같습니다.

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

 

i는 x22, k는 x24에 할당되었으며,

배열 save의 시작 주소는 x25에 저장되어 있다고 할 때, 위 C 문장에 해당하는 RISC-V 어셈블리 코드는 다음과 같습니다.

Loop: slli x10, x22, 3 // 임시 레지스터 x10에 i * 8의 결과 저장 (8바이트)

      add x10, x10, x25 // save(x25)의 시작 주소에 x10이 가진 값(i * 8)를 더한다.

      ld x9, 0(x10) // save[i] 값을 임시 레지스터 x9에 저장

      bne x9, x24, Exit // save[i]와 k(x24)가 다르면 Exit로 이동
      
      addi x22, x22, 1 // i = i + 1;
      
      beq x0, x0, Loop //Loop로 무조건 분기
      
Exit: ...

 

이를 좀 더 빠르게 최적화하면 다음과 같습니다.

      slli x10, x22, 3   // 임시 레지스터 x10에 i * 8의 결과 저장 (8바이트)

      add x10, x10, x25  // save(x25)의 시작 주소에 x10이 가진 값(i * 8)를 더한다.

      ld x9, 0(x10)      // save[i] 값을 임시 레지스터 x9에 저장

      bne x9, x24, Exit  // save[i]와 k(x24)가 다르면 Exit로 이동
      
Loop: addi x22, x22, 1   // i = i + 1;

      slli x10, x22, 3   // 임시 레지스터 x10에 i * 8의 결과 저장 (8바이트)

      add x10, x10, x25  // save(x25)의 시작 주소에 x10이 가진 값(i * 8)를 더한다.
      
      ld x9, 0(x10)      // save[i] 값을 임시 레지스터 x9에 저장

      beq x9, x24, Loop  
      
Exit: ...

 

 

 

 

 

 

 

 

 

 

 

 

🧐 다른 조건부 명령어

같은지 다른지를 비교하는 명령어(beq, bne) 이외에도, 두 변수 간의 대소 비교가 필요한 경우도 종종 존재합니다.

 

필요한 비교는 다음과 같습니다.

less than ( $<$ )

less than or equal ( $\leq$ )

greater than ( $>$ )

greater than orr equal ( $\geq$ )

equal ( $=$ )

not equal ( $\neq$ )

 

비교 명령은 부호있는 수와 부호없는 수를 모두 다룰 수 있어야 합니다.
어떤 때에는 MSB가 1인 수가 음수를 나타내는데, 이때는 당연히 MSB가 0인 어떤 양수보다도 작습니다.
하지만 부호없는 정수의 경우에는 MSB가 1인 수가 MSB가 0인 어떤 수보다도 더 큽니다.
이러한 MSB의 이중적 의미를 이용하여, 배열 경계 검사 비용을 줄이는 방법을 곧 살펴보겠습니다.

 

 

 

 

RISC-V 에서 제공되는 명령어는 다음과 같습니다.

 

blt - branch if less than

bltu - branch if less than, unsigned 

bge - branch if greter than or equal

begu - branch if greter than or equal, unsigned 

 

나머지 비교는 $<$ 과 $\geq$, $=$,  $\neq$ 를 통해서 표현할 수 있으므로 따로 제공하지 않습니다.

 

예를 들어 $a \; > \; b$ 는 $a\; \leq \;b$ 가 아닌 경우로 표현이 가능한데, 예시는 다음과 같습니다.

if ( a > b ) a += 1;

 

a는 x22, b는 x23이 할당되었을 때, 다음과 같이 번역됩니다.

bge x23, x22, Exit // b(x23) >= a(x22) 인 경우 Exit
addi x22, x22, 1 // b >= a 가 아닌 경우에 실행된다.

 

또 다른 방법은 명령어 실행 결과를 요약하여 표시하는 별도의 비트들을 두는 방법으로, Intel x86-64의 경우 해당 방식을 사용합니다.
이 별도의 비트들은 조건 코드(condition code) 또는 플래그(flag)라 불립니다.

 

 

 

 

 

 

⭐️ 빠른 경계 검사 방법

부호있는 정수를 부호없는 정수처럼 다루면 $0 \leq x < y$ 검사 비용을 낮출 수 있습니다.

 

이 검사는 인덱스가 배열의 한계를 벗어났는지 확인하는 검사에 유용합니다.

 

 

2의 보수로 표현된 음수가 부호없는 정수에서의 큰 수처럼 보이는 것이 핵심인데, 

즉 2의 보수 표현에서는 MSB가 부호 비트이지만, 부호없는 정수에서는 큰 값을 의미합니다.

 

따라서 부호없는 비교 x < y를 하면, x가 y보다 작은지 뿐만 아니라, x가 음수인지도 검사할 수 있습니다.

 

추가적으로 설명하면 다음과 같습니다.

$0 \leq x < y$ 를 보면, y는 항상 0보다 큰 수, 즉 양수임을 알 수 있습니다.
따라서 y의 MSB는 0인 것이 자명합니다.

이제 부호없는 비교 x < y를 하게 된다면 다음 상황이 나올 수 있습니다.

1. x가 음수인 경우
 -> x의 MSB가 1이므로, 부호없는 비교에서는 x < y의 결과가 false입니다.

2. x가 y와 같거나 큰 양수인 경우
 -> 마찬가지로 x $\geq$ y이므로 x < y의 결과가 false 입니다.

3. x가 y보다 작은 경우
 -> x < y인 경우이므로 결과가 true입니다.

즉 x가 음수이거나 x $\geq$ y 인 경우를 한번의 검사로 진행할 수 있습니다.