MIPS Branch Instruction
MIPS 분기 명령어
- 프로그램의 의사 결정 기능을 구현하는데 이용되는 명령어이다. (컴퓨터가 단순 계산기보다 훨씬 강력한 이유이다.)
- 프로그램의 실행 흐름을 프로그래머 임의로 바꾸는 명령어이다.
- Conditional Branch : 테스팅 결과에 따라 분기 여부를 결정하는 분기 명령어이다.
- Unconditional Branch : 무조건적으로 분기를 수행하는 분기 명령어이다.
- \(\texttt{beq, bne}\) (Conditional Branch)
- \(\texttt{j, jal, jr}\) (Unconditional Branch)
- \(\texttt{blt, ble, bgt, bge}\) (Pseudo Branch Instruction)
- \(\texttt{slt, slti, sltu, sltiu}\) (Support of Branch)
Conditional Branch (조건 분기) ; PC-Relative Addressing
\(\texttt{beq, bne}\) Instruction (I-Format)
beq RS, RT, Label # if RS == RT, then go to Label
bne RS, RT, Label # if RS != RT, then go to Label- \(\texttt{RS}\)와 \(\texttt{RT}\)의 값이 같거나(\(\texttt{beq}\)) 다르면(\(\texttt{bne}\)) \(\texttt{Label}\)로 분기한다.(이동한다.)
- \(\texttt{RS}\) : Source 레지스터 (첫 번째 비교대상)
- \(\texttt{RT}\) : Source 레지스터 (두 번째 비교대상)
- \(\texttt{Label}\) : 분기할 레이블 이름 (현재 실행중인 명령어와 분기 목적지 명령어까지의 상대적인 거리 차이 (Word 단위))
Unconditional Branch (무조건 분기)
\(\texttt{j}\) Instruction (J-Format)
j Label # go to Label (jump)- 무조건적으로 \(\texttt{Label}\)로 분기하는 연산을 수행한다.
- \(\texttt{Label}\) : Branch Destination Address에 대응되는 레이블 이름 (BDA는 16Bit로 구성된 주솟값이다.)
* MIPS의 모든 조건 분기 명령어는 PC-Relative Addressing 방식을 사용하는 반면,
무조건 분기 명령어 \(\texttt{j}\)의 Target Address 필드에는 온전한 형태의 타겟 주소가 워드 단위로 저장되어 있다.
즉, 무조건 분기 명령어는 현재 주소와 타겟 주소의 차이(Offset)가 아닌, 타겟 주소가 온전히 쓰인다.
- \(\texttt{Label}\)이 저장하는 주소를 \(\texttt{jump target}\)이라 할 때, BDA는 아래와 같이 Concatenation 된다.
BDA = {(PC+4)[31:28], \(\texttt{jump target}\), 2'b00}
- 26Bit의 \(\texttt{jump target}\) 필드의 앞에는 (PC+4)의 상위 4Bit가 붙고, 뒤에는 2의 보수 체계 숫자 00 2Bit가 붙어 32Bit의 BDA가 만들어진다.
\(\texttt{jal}\) Instruction (J-Format)
jal Label # go to Label and linking (jump and link)
Task ...- 무조건적으로 \(\texttt{Label}\)로 분기하되, 다음 실행할 명령어(\(\texttt{Task...}\))의 주소(PC+4)를 \(\texttt{\$ra}\)에 저장한 다음 분기를 수행한다.
- \(\texttt{Label}\) : Branch Destination Address에 대응되는 레이블 이름 (BDA는 16Bit로 구성된 주솟값이다.)
- Procedure Call 상황에서 많이 사용되는 명령어이며, Caller측에서 사용한다.
- \(\texttt{\$ra}\) 레지스터는 관례적으로 리턴 주솟값을 저장하는데 사용하는 레지스터이다. (Register Usage 참조)
- MIPS R4000(MIPS 2nd Ver.)에서는 PC+4가 아닌, PC+8이 저장된다.
\(\texttt{jr}\) Instruction (R-Format)
jr Rs # jump to register (jump register)- \(\texttt{Rs}\) 레지스터가 가진 주솟값으로 무조건 분기한다.
- \(\texttt{Rs}\) : 특정 레지스터의 이름으로, 어떤 명령어의 주솟값을 저장하고 있는 레지스터이어야 한다.
- Procedure Call 상황에서 많이 사용되는 명령어이며, Callee측에서 사용된다.
- 모든 Task를 수행한 Callee가 Caller에게 제어권을 넘기기 위해 \(\texttt{jr \$ra}\)명령을 사용하는 형태가 일반적이다. (이 때, \(\texttt{\$ra}\)에는 Callee를 호출한 부분의 바로 다음 명령어의 주소가 저장되어 있다.)
Pseudo Branch Instruction (의사 분기 명령어)
\(\texttt{blt}\) Instruction
blt RS, RT, Label # if RS < RT, then go to Label (Branch Less Than)
// Expansion
slt $at, RS, RT # if RS < RT, then $at = true(1)
bne $at, $zero, Label # if $at == true, then go to Label- \(\texttt{RS < RT}\) 비교 연산의 결과(Boolean Type)에 따라 \(\texttt{Label}\)로의 분기 여부를 결정한다.
- \(\texttt{RS}\) : Source 레지스터 (첫 번째 비교대상)
- \(\texttt{RT}\) : Source 레지스터 (두 번째 비교대상)
- \(\texttt{Label}\) : 분기할 레이블 이름 (현재 실행중인 명령어와 분기 목적지 명령어까지의 상대적인 거리 차이 (Word 단위))
\(\texttt{ble}\) Instruction
ble RS, RT, Label # if RS <= RT, then go to Label (Branch Less than or Equal than)
// Expansion
slt $at, RT, RS # if RS > RT, then $at = true(1)
beq $at, $zero, Label # if $at == false, then go to Label- \(\texttt{RS ≤ RT}\) 비교 연산의 결과(Boolean Type)에 따라 \(\texttt{Label}\)로의 분기 여부를 결정한다.
- \(\texttt{RS}\) : Source 레지스터 (첫 번째 비교대상)
- \(\texttt{RT}\) : Source 레지스터 (두 번째 비교대상)
- \(\texttt{Label}\) : 분기할 레이블 이름 (현재 실행중인 명령어와 분기 목적지 명령어까지의 상대적인 거리 차이 (Word 단위))
\(\texttt{bgt}\) Instruction
bgt RS, RT, Label # if RS > RT, then go to Label (Branch Greater Than)
// Expansion
slt $at, RT, RS # if RT < RS, then $at = true(1)
bne $at, $zero, Label # if $at == true, then go to Label- \(\texttt{RS > RT}\) 비교 연산의 결과(Boolean Type)에 따라 \(\texttt{Label}\)로의 분기 여부를 결정한다.
- \(\texttt{RS}\) : Source 레지스터 (첫 번째 비교대상)
- \(\texttt{RT}\) : Source 레지스터 (두 번째 비교대상)
- \(\texttt{Label}\) : 분기할 레이블 이름 (현재 실행중인 명령어와 분기 목적지 명령어까지의 상대적인 거리 차이 (Word 단위))
\(\texttt{bge}\) Instruction
bge RS, RT, Label # if RS >= RT, then go to Label (Branch Greater than or Equal than)
// Expansion
slt $at, RS, RT # if RS < RT, then $at = true(1)
beq $at, $zero, Label # if $at == false, then go to Label- \(\texttt{RS ≥ RT}\) 비교 연산의 결과(Boolean Type)에 따라 \(\texttt{Label}\)로의 분기 여부를 결정한다.
- \(\texttt{RS}\) : Source 레지스터 (첫 번째 비교대상)
- \(\texttt{RT}\) : Source 레지스터 (두 번째 비교대상)
- \(\texttt{Label}\) : 분기할 레이블 이름 (현재 실행중인 명령어와 분기 목적지 명령어까지의 상대적인 거리 차이 (Word 단위))
Support of Branch (보조 분기)
\(\texttt{slt, sltu}\) Instruction (R- Format)
slt RD, RS, RT # Set on Less Than
sltu RD, RS, RT # Set on Less Than (unsigned)- \(\texttt{RS < RT}\) 비교 연산의 결과(Boolean Type)를 \(\texttt{RD}\)에 저장한다.
- \(\texttt{RD}\) : Destination 레지스터
- \(\texttt{RS}\) : Source 레지스터 (첫 번째 비교대상)
- \(\texttt{RT}\) : Source 레지스터 (두 번째 비교대상)
\(\texttt{slti, sltiu}\) Instruction (I-Format)
slti RT, RS, immediateConstant # Set on Less Than Immediate
sltiu RT, RS, immediateConstant # Set on Less Than Immediate (unsigned)- \(\texttt{RS < immediateConstant}\) 비교 연산의 결과(Boolean Type)를 \(\texttt{RT}\)에 저장한다.
- \(\texttt{RT}\) : Destination 레지스터
- \(\texttt{RS}\) : Source 레지스터 (첫 번째 비교대상)
- \(\texttt{immediateConstant}\) : 상숫값 (두 번째 비교대상)
Branch Mechanism (분기 메커니즘)
- 프로그램이 수행하게 될 명령어들은 특정 메모리 공간에 순차적으로 저장되어 있다.
- MIPS에서는 한 명령어가 4Byte(1Word)의 공간을 차지하고 있다.
- 프로그램 실행 순서가 바뀌지 않는 이상, PC 레지스터에 저장되어 있는, 앞으로 실행할 명령어의 주소는 현재 명령어가 수행된 후에 순차적으로 4씩 증가하게 된다.
- MIPS ISA에서는 주솟값에 더해지는 정수는 비트가 아닌, 바이트 단위로 간주된다. (Byte Addressable 특성)
- 분기 명령어가 수행될 경우, PC값은 이에 맞춰서 분기 목적지가 되는 명령어의 주소를 적절하게 계산*해야 한다.
- 분기의 목적지가 되는 레이블 주솟값을 Branch Destination Address(BDA)라고 한다.
* PC-Relative Addressing (Offset)
- MIPS를 포함한 대부분의 시스템에서 채택하고 있는 분기 주소 계산 방식이다.
- 조건 분기 명령어의 address필드에는 BDA와 PC에 저장된 상대적인 주솟값의 차이를 Word 단위(명령어 단위)로 저장하는 필드이다.
- 명령어 Field 중 16Bit의 immediate 부분을 차지하고 있다. (즉, 차이는 16Bit 값으로 표현된다.)
- 16Bit이므로 명령어 간 차잇값은 \(-2^{15} \leq \texttt{BDA} \leq 2^{15} - 1\) 와 같은 범위를 가진다.
- 보통, 프로그램 내에서 분기하고자 하는 레이블은 현재 실행중인 명령어에서 그리 멀리 떨어져 있지 않기 때문에 위와 같은 범위 내에서 커버할 수 있다.
- BDA = (PC + 4) + (Offset << 2) 로 목적지 주솟값을 계산할 수 있다.
- Offset은 Immediate 필드에 저장된 값을 의미하며, Word단위로 저장되어 있으므로 Byte Addressable 특성에 맞추기 위해 4를 곱해서(Twice Left Shift) Byte 단위로 변환하여 계산한다.
- 실제 하드웨어에서 BDA를 계산할 때, PC값은 32Bit이고, Offset값은 16Bit이므로, Offset 값에 대한 Sign-Extension을 수행한 후에 실질적인 BDA 계산이 이루어진다.
※ J-Format을 이용한 분기 명령어들은 PC-Relative Addressing 방식을 사용하지 않는다.
J-Format의 Target 필드에는 목적지 주솟값이 Word단위로 변환되어 저장된다. (Offset을 저장하는 방식이 아니다.)
Branching Far Away (J-Format을 이용한 장거리 분기)
- I-Format의 16Bit Offset 필드의 한계를, J-Format의 26Bit Offset 필드의 도움을 받아 타개하는 방법이다.
- 조건 분기시에, 16Bit 필드로 커버되지 않는 먼 거리를 분기해야 할 때 J-Format을 이용하는 테크닉이다.
Loop Structure using Branch (분기 명령어를 이용한 반복문 구조)
- MIPS 명령어를 통한 \(\texttt{while}\) Loop 구현
- MIPS 명령어를 통한 \(\texttt{for}\) Loop 구현
- MIPS 명령어를 통한 \(\texttt{for}\) Loop 구현
이미지 출처: Computer Organization And Design 5th Edition (David A. Patterson)