[컴퓨터 구조] MIPS Branch

October 13, 2023

Branch란?

프로그램은 if문과 같이 조건에 따라 동작을 다르게 수행할 수 있어야 합니다. 이를 구현하기 위해서는 분기를 나눌 수 있는 branch에 관련한 연산자가 필요합니다.

분기를 나누는 방식으로는 조건에 따라 분기하는 conditional과 무조건으로 이동하는 unconditional이 있습니다.

Conditional branch

동일성 비교

bne $s0, $s1, Lbl   // if $s0 is not $s1, go to "Lbl"
beq $s0, $s1, Lbl   // if $s0 is     $s1, go to "Lbl"

명령어	의미	동작
`bne`	branch not equal	피연산항 2개가 동일하지 않을 때, Lbl( 분기점 )으로 이동하라는 연산
`beq`	branch equal	피연산항 2개가 일치할 때, Lbl( 분기점 )으로 이동하라는 연산

동일성 비교로 분기 이동

if (i == j) {
    h = i + j;
    ...
}

이를 MIPS 어셈블리어로 나타내면 다음과 같습니다.

bne $s0, $s1, Lbl1  // 같지 않으면 Lbl1로 이동해서 거기부터 실행
add $s3, $s0, $s1   // h = i + j
...

Lbl1: ...

특이하게 high-level에서 == 연산이 어셈블리 레벨에서는 같지 않음으로 컴파일됩니다. 이는 위의 코드에서 같으면 분기할 필요없이 평소처럼 그대로 다음 명령어를 실행하고, 같지 않을 때만 분기를 이동하기 때문입니다.

내부 동작 기술

Label은 offset을 나타냅니다. 현재 수행 중인 명령문에서 이동하고자 하는 목표 주소까지의 오프셋을 의미합니다. bne / beq 명령어는 I 포맷을 사용하며, 이 상수 값으로 해당 오프셋에 따라 목표 주소로 이동할 수 있습니다.

offset의 비트수가 16이라서 이동할 수 있는 범위는 -2^15 ~ 2^15 -1입니다.

program counter 레지스터의 값과 16-bit offset인 immediate 값을 더해서 이동할 주소값을 구합니다.

여기서 주의해야 할 점은 단위가 byte가 아닌 word입니다. 왜 byte단위로 이동하지 않고 word단위로 이동할까요?

이는 MIPS가 한 명령어의 크기가 32-bit로 고정되어 있어서 4 bytes인 1 word 만큼 이동해야 하기 때문입니다.

또한, 단위가 word이기 때문에 끝의 2자리 비트가 모두 00입니다. 더 많은 범위를 표현하기 위해서 뒤의 00을 생략하고 immediate 값에 저장합니다.

주소 계산 과정 따라가기

주소값 계산

이동할 주소값을 계산하기 위해, program counter(PC)의 값과 offset을 의미하는 immediate 값을 더해야 합니다.
1. 이전에 4의 배수라서 생략했던 하위 00, 2-bit를 원래의 위치에 붙입니다.
  
  즉, 이 26비트 값에 4를 곱하는 것과 동일한 의미입니다.
  
  하지만 immediate는 16-bit라서 sign-extend를 하고 32-bit와 더해야 합니다.
2. immediate를 sign-extend
3. 나온 결과 값을 PC+4와 더하기
4. 얻은 명령어 주소로 이동하기

대소 비교

C언어에서 <, >처럼 대소 비교를 하는 연산입니다.

slt은 set less than입니다. R 포맷이며 레지스터 3개를 사용합니다.

slt $t0, $s0, $s1   // if $s0 < $s1 이면, $t0에 1을 대입, 아니면 0을 대입

slti는 I 포맷으로 상수와 대소 비교를 할 때 사용합니다.

slti $t0, $s0, 10   // if $s0 < 10 이면,  $t0에 1을 대입, 아니면 0을 대입

대소 비교로 분기 이동

이제 만들어 놓은 slt, beq, bne와 고정된 상수 $zero로 다양한 상태일 때의 조건 분기가 가능합니다.

분기할 조건	High-level	설명
less than	<	`blt $s1, $s2, Label`
less than or equal to	<=	`ble $s1, $s2, Label`
greater than	>	`bgt $s1, $s2, Label`
greater than or equal to	>=	`bge $s1, $s2, Label`

분기할 조건에 따라 분기를 할지 말지를 정할 수 있습니다.

사실 없는 명령어?

그런데 사실, 위의 4 명령어들은 MIPS ISA에 없고 pseudo 분기 명령어입니다.

명령어 blt $s1, $s2, Label는 어셈블러가 아래의 명령어들로 자동으로 변환합니다.

slt $at, $s1, $s2       // if $s1 < $s2, $at set to 1
bne $at, $zero, Label   // if $at is NOT $zero, go to "Label"

$at 레지스터는 어셈블러가 사용하는 레지스터로 프로그래머가 아닌 어셈블러와 컴파일러가 임시적으로 사용하기 위한 목적으로 예약되어 있습니다.

명령어가 1개 수행되는 것보다 2개로 수행해서 더 느리지만 MIPS의 철학인 Make the common case fast를 상기하면, 이는 common case가 아니라서 명령어를 더 추가하는 대신, 기존의 명령어를 여러 번 재사용하도록 설계한 것을 볼 수 있습니다.

Unconditional branch

exit나 return과 같이 무조건 명령어를 이동해야하는 경우가 있습니다.

이런 경우, J 포멧인 j 명령어로 무조건 이동할 수 있습니다.

j   Lbl     // go to Lbl

무조건 이동 예시

if (i != j)
    h = i + j;
else
    h = i - j;

        beq     $s0, $s1,  Else
        add     $s3, $s0,  $s1  // i != j
        j       Exit
Else:   sub     $s3, $s0,  $s1  // i == j

26 bits

점프 명령의 경우 MIPS는 점프 위치를 결정하는 데 26비트만 있습니다. 점프는 MIPS의 PC와 관련이 있습니다.

branch와 마찬가지로, immediate 점프 값은 word로 되어야 합니다. 따라서, 우리는 26 비트 주소에 생략한 2 비트를 원상 복구하기 위해서 4를 곱해야(하위에 00를 넣기) 합니다.

26비트 때, 주소값 계산 과정

program counter(PC)의 값과 offset을 의미하는 immediate 값을 더해야 합니다.
1. 이전에 4의 배수라서 생략했던 하위 00, 2-bit를 원래의 위치에 붙입니다.
  
  즉, 이 26비트 값에 4를 곱하는 것과 동일한 의미입니다. 그러면 이제 28-bit 입니다.
2. PC+4 값에 대해 점프하고 있기 때문에, PC+4 값의 상위 4 비트를 점프 주소의 왼쪽에 연결
3. 나온 결과 값을 PC+4와 더하기
4. 얻은 명령어 주소로 이동하기

2번에서 PC+4와 연결하는 이유에 대해 설명하겠습니다.

MIPS 체계에서 이동할 수 있는 메모리 주소 범위는 32-bit입니다. 그런데 26-bit + 생략한 2-bit는 28-bit 입니다. 32-bit로 만들어 이동하기 위해서, PC+4의 상위 4 비트를 28비트 주소값의 상위 4비트에 덧붙여서 32 비트 주소값을 만듭니다.

주소 계산 과정 따라가기

문제에서 beq 명령어 주소가 0x00 40 00 20, exit의 주소는 0x00 40 00 30라고 합니다.

        beq $s0, $s1, Else
        add $s3, $s0, $s1
        j   Exit
Else:   sub $s3, $s0, $s1
Exit:   ...

왜 exit의 주소가 30으로 끝날까요? 그 이유는 다음과 같습니다.

j에서 Else로 가기 위한 값은 0x2, 이진수로는 1100
하위 2-bit인 00 추가
0x00 11 00 00은 십진수로 30

Loop

C 언어에서 while문과 같이 반복이 필요한 경우에 쓰이는 분기 명령어 입니다.

조건을 만족시 초기 시작 위치로 이동합니다.

while (i != k)
    i = i + j;

Loop:   beq $s0, $s2, Exit
        add $s0, $s0, $s1
        j   Loop
Exit:   ...

Basic block : 중간에 분기를 하지 않는 명령어 집합입니다.

분기 명령어 정리

word일 때, 18-bit 범위를 벗어나는 주소를 이동하고 싶다면?

→ j 포맷 사용(26-bit)

beq $s0, $s1, L1

어셈블러가 위의 코드를 동일한 동작을 하는 아래의 코드로 바꿉니다.

    bne $s0, $s1, L2
    j   L1
L2: next ins. of beq

beq를 bne로 바꾸고 j 명령어를 추가해서 26-bit 범위까지 이동할 수 있습니다.

만약 26-bit 범위를 넘는 주소 이동이 필요하다면, jr 명령어를 사용할 수 있습니다.

Procedure

Procedure 설명

다시 간단히 말하자면, 특정 task를 수행하는 명령어 집합을 의미합니다.

jr 명령어

case나 switch같이 다중 분기를 해야할 때 사용합니다.

jump register라는 의미

jr  $t1     // go to address in $t1

jal 명령어

jump and register

PC+4 값을 $ra에 저장
Procedure address로 이동
Procedure이 끝난다면, 저장한 $ra로 돌아옴

jal ProcedureAddress        // jump and link

참고

https://stackoverflow.com/questions/6950230/how-to-calculate-jump-target-address-and-branch-target-address

Bilkent University CS 224 Course Slides