[컴퓨터 구조] Decision Instruction

 

 

---

앞의 글을 읽으시면 이해에 도움이 됩니다.


2022.10.01 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] RISC-V 명령어 작동 과정 (RISC-V Instruction Operation Process)

[컴퓨터 구조] RISC-V 명령어 작동 과정 (RISC-V Instruction Operation Process)

2022.10.01 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Type of Instruction (명령어의 타입)

[컴퓨터 구조] Type of Instruction (명령어의 타입)

---

1. Decision Instruciton이란?

Decision Instruction은 말 그대로 결정을 위한 명령어로 while, if, else 등이 있습니다.

우선 기준이 되는 설명은 32bit architecture이 기준이므로 word가 4Byte임을 감안하고 보셔야 합니다.
(만약 64bit architecture이라면 word가 8Byte이므로 명령어가 lw가 아닌 ld가 됩니다.)

---

2. bne, beq

bne는 branch not equal의 줄임말이고,
beq는 branch equal의 줄임말입니다.

이해를 돕기 위해 예시를 들겠습니다.

코딩을 하면 쉽게 접할 수 있는 if-else 구문이 있습니다.

if(조건문)에서 조건문이 True라면 if문 안의 명령어를 실행하고, 조건문이 False라면 else문 안의 명령어를 실행하거나, if문을 탈출합니다.

이때 탈출한다는 조건이 중요한데, 탈출을 한다는 것은 다음 명령어의 위치를 바꿈을 의미합니다.

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

라는 명령어가 있다고 가정해봅시다.

만약 i와 j가 같다면 바로 아래의 명령어를 실행할 것이고, 그게 아니라면 else문의 명령어를 실행할 것입니다.

이를 간략한 그래프로 나타내면,

와 같습니다.

분기를 위한 명령어를 Conditional Branches라고 합니다.

조건에 따라 branch를 옮긴다는 뜻으로 이해하면 됩니다.

따라서 bne 명령어는 명령어 안에 포함되어 있는 두 개의 레지스터가 같지 않는다면 특정 Label로 이동합니다.

또한 beq 명령어는 명령어 안에 포함되어 있는 두 개의 레지스터가 같다면 특정 Label로 이동합니다.

위의 c언어 명령어를 어셈블리어로 나타내면 다음과 같습니다.

	bne x22, x23, Else		## x22 != x23이라면 Else로 이동
	add x19, x20, x21
	beq x0, x0, Exit		## Unconditional branch
Else : sub x19, x20, x21
Exit :

이해가 되시나요?

bne x22, x23, Else는 x22 레지스터의 값과 x23 레지스터 값이 같지 않으면 Else로 이동합니다.

그러면 add는 이해가 되는데, beq x0, x0는 뭐죠?

항상 x0는 x0와 같기 때문에 Exit로 이동하지 않을까요?

해당 명령어는 Unconditional branch 명령어로 항상 branch를 움직이게 하는 명령어입니다.

만약 Unconditional branch를 사용하지 않는다면, Else로 이동하지 않음에도 불구하고, 순차적으로 명령어를 실행하기 때문에 결국엔 Else 명령어를 실행하게 됩니다

이해가 됐다면 조금 더 어려운 while문에 대해 보겠습니다.

---

2.1 while

 

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

이런 명령어가 있고, save의 시작 주소는 register x25에 저장되어 있다고 가정합시다.

i, k는 각각 x22, x24에 저장되어 있다고 가정합니다.

이를 어셈블리어로 나타내면,

Loop  : slli x10, x22, 2	
	add x10, x10, x25
        lw x9, 0(x10)
        bne x9, x24, Exit
        addi x22, x22, 1
        beq x0, x0, Loop
Exit  :

slli 명령어를 사용해서 x22를 왼쪽으로 2bit shift 하는 이유는 x22는 i이기 때문에, 이를 실제 메모리 주소와 매핑하기 위해서는 4를 곱해줘야 합니다.
그래야 실제 메모리 주소를 가리키기 때문입니다.
(save[0]은 x25 위치에 있지만, save[1]은 x25에 저장된 address + x22 * 4임)

그 다음 add x10, x10, x25를 하는 이유는 배열의 base address의 offset을 더하기 위한 것입니다.

따라서 lw를 통해 x10에 있는 주소만 가지고 값을 가져올 수 있습니다.
(lw의 offset은 상수만 가능함. 따라서 lw x9, x10(x25) 같은 명령어는 불가능함)

bne를 통해 save[i]와 k를 비교하여 Exit로 보내고 있고,

마지막에 beq를 통해 Unconditiaon Branch를 하는 모습을 볼 수 있습니다.

---

3. blt(u), bge(u)

마지막으로 소개해드릴 Conditional Branch 명령어는 blt와 bge입니다.

blt는 branch less than의 약자이고,
bge는 branch greater equal의 약자입니다.
뒤에 u가 붙는다면 레지스터 값을 unsigned로 간주한 후 명령어를 실행합니다.

따라서 blt는 두 개의 레지스터 값을 비교한 후 rs1이 rs2보다 작다면 branch를 변경합니다.

반대로 bge는 두 개의 레지스터 값을 비교한 후 rs1이 rs2보다 크거나 같다면 branch를 변경합니다.

해당 레지스터 값이 있을 때,
blt rs1, rs2, L을 한다면 rs2가 크기 때문에 L로 이동합니다.
(rs1은 음수, rs2는 양수)

하지만 만약 bltu rs1, rs2, L을 한다면 rs1이 더 크기 때문에 L로 이동하지 않습니다.

case/switch statement는 명령어가 바로바로 이동할 수 있게 Label을 정하고 Table을 만들어 놓습니다.

---

4. SB-Type

SB-type을 알기 전에 우선 PC를 알아야 하는데, PC는 현재 명령어의 주소를 지정하고 있는 레지스터입니다.

branch instruction들은 모두 SB-type이라고 합니다.

SB-type은 신기하게도 짝수로만 이동이 가능합니다.

해당 타입의 format은 아래와 같습니다.

왜 짝수로만 이동이 가능할까요?

명령어의 format을 보면 imm이 1부터 12인 것을 볼 수 있습니다.

이는 실제로 명령어의 imm의 0번째는 '0'으로 취급한다는 것과 마찬가지입니다.

그렇기 때문에 사실상 imm을 13개를 쓰는 것과 마찬가지고,
따라서 명령어의 범위는 -4096 ~ 4094입니다.
(실제로 뒤에서 보겠지만 imm gen같은 경우 왼쪽으로 한 칸 shift하여 사용함. 따라서 imm은 13비트가 됨)

아래는 그 이유인데, 보셔도 되고 안 보셔도 됩니다.

 

32bit architecture이므로 word가 4Byte이다.
따라서 하나의 명령어가 저장되어 있는 공간은 4Byte이므로,
4의 배수가 아닌 숫자로 명령어 위치를 바꾸는 것은 불가능하다.
(첫 번째 명령어는 0~3, 두 번째는 4~7 ... )

4의 배수는 항상 비트의 끝자리가 00으로 끝나므로, 끝의 두 자리는 따로 명시하지 않아도 된다.
따라서 imm은 2~13까지만 명시하는 게 정상이지만, RISC-V 개발 당시 2Byte 명령어도 지원할 계획이 있어서 끝에 0 하나만 없앴다.
(여기서 없앴다의 뜻은 무조건 0이 들어가기 때문에 확장성을 위하여 format에는 따로 명시하지 않았다는 뜻)

그렇기 때문에 기존의 1~12비트에 해당하는 \(-2^{11}\sim2^{11}-1\)에서 2를 곱하여 위의 범위가 된다.

 

SB-type은 PC를 기반으로 움직입니다.

따라서 현재 PC의 위치에 따라서 움직일 branch의 주소를 지정하는데 이를 PC-relative addressing이라고 합니다.

즉 PC가 branch를 위한 base register이라고 생각하시면 될 것 같습니다.

그렇기 때문에 실제로 SB-type이 움직일 수 있는 범위는 현재 명령어를 기준으로
(만약 4Byte 명령어만 지원한다면) \(\pm 2^{10}\)이 됩니다.


이 정도면 얼추 conditional branch에 대한 내용은 끝난 것 같습니다.

다음 글에서는 procedure calls를 위한 명령어에 대해 알아보겠습니다.

2022.10.21 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Procedure call, jal, jalr (프로시저 콜을 위한 명령어들)

[컴퓨터 구조] Procedure call, jal, jalr (프로시저 콜을 위한 명령어들)

감사합니다.

지적 환영합니다.