2. MIPS : Control Instruction

Control Instructions

= Branch instruction, Jump instrucition

 

Instruction의 20%가 control instruction일 정도로 common case이다.

때문에 이를 single instruction으로 표현할 필요가 있기에 만들어졌다.

 

Control instruction은 control flow(program execution flow)을 바꾼다.

즉 PC(Program Counter)의 값을 변경한다.

 

언제 jump하는지에 따라서 다음과 같이 구분된다.

• Conditional jump
  • 조건이 충족할 때만 jump 수행
  • beq, bne
• Unconditional jump
  • 항상 jump을 수행
  • 무엇을 이용하여 jump하는지에 따라 구분
    • jump
      • target address를 이용하여 jump
      • j, jal
    • jump register 
      • register에 들어있는 주소로 jump
      • jr, jalr

 

다음과 같은 종류가 있다.

<pre>

bne  $t4,  $t5,  16-bit-offset

beq  $t4,  $t5,  16-bit-offset

j       26-bit-address
jal    26-bit-address
jr     $s4
jalr  $s4

</pre>

 

---

Conditional Jump

조건을 충족할 때 jump을 수행한다.

 

Conditional branch instruction, Decision making instruction이라고도 한다.

 

---

동일 여부 비교를 통한 Branch

두 값이 같거나 다를 경우 branch를 수행한다.

<pre>beq, bne</pre>가 있다.

 

Operation

<pre>beq, bne</pre>

<pre>

bne   $t0,   $t1,   jump-distance         // t0와 t1이 같지 않으면 jump-distance만큼 떨어진 곳으로 jump

beq   $t0,   $t1,   jump-distance         // t0와 t1이 같으면 jump-distance만큼 떨어진 곳으로 jump

</pre>

 

Jump Distance

$PC(destination) \; \leftarrow \; current PC \, + \, offset \, \times \, 4$

 

조건을 충족하면 jump-distance만큼 떨어진 곳으로 jump한다.

jump-distance는 현재 PC값(다음 instruction 지정)과 얼만큼 떨어져 있는가를 word 단위로 나타낸 것이다.

이를 PC-relative addressing mode라고 한다.

 

음의 방향으로 이동할수도 있기 때문에 offset은 signed number이다.

따라서 $-2^{15} \; ~ \; 2^{15} -1$까지 담을 수 있다.

 

Conditional jump instruction은 두 개의 register와 offset을 표현하기 위해 I-format을 사용한다.

(Keep format as similar as possible)

 

Jump distance을 Register로 표현하지 않는 이유?

만약 jump를 R-format을 이용해서 jump distance을 register에 담아 이용할 수도 있다.

그러나 이 경우에는 register에 넣는데 instruction을 더 소모하게 되기 때문에 비효율적이다.

더구나 벤치마크 분석 결과 conditional jump는 주로 가까운 거리를 jump하기 때문에 I-format의 16bit로도 충분하다.

 

Jump distance가 16bit인 이유?

bne, beq는 I format을 사용하고 이에 immeidate는 16bit의 공간을 사용하게 된다.

만약 target address를 32bit로 넣는다면 fetch를 2번해야 하므로 성능이 떨어지게 된다.

벤치마크를 분석하면 bne, beq는 주로 가까운 거리를 사용하기 때문에 PC-relative distance을 16bit으로 표현 가능하다.

 

Jump distance가 Word 단위인 이유?

Instruction은 word 단위이기 때문에 instruction을 jump를 하는 offset은 항상 4의 배수이므로 맨 마지막 2bit는 00이다.

이는 2개의 bit가 항상 낭비되는 것이므로, 낭비를 없애고 더 나은 표현 범위를 위해 byte offset이 아닌 word offset을 이용한다.

따라서 jump distance는 $2^{18}$bit의 표현범위를 갖는다.

 

Relative jump의 장점

Relative jump는 position-independent이다.

 

Dynamic library등으로 사용될 때 compiler가 link하는 과정에서 code의 주소가 바뀔 수 있다.

Absolute jump을 사용한다면 code의 주소가 바뀌면 jump target을 다시 지정을 해야 한다.

그러나 relative jump는 code block을 한꺼번에 옮기면 offset을 다시 변경하지 않아도 된다.

즉, linking하는 과정에서의 보정을 없앤다.

 

예시

C 코드에서 <pre>if(i == j) h = i + j;</pre>와 같다면, 다음과 같이 변환된다.

<pre>

bne   $s0,  $s1,  1

add   $s2,  $s0,  $s1

...

</pre>

 

i와 j가 다르다면 add을 수행하지 않고 그 다음 instruction으로 jump 해야 한다.

PC는 다음에 실행할 instruction을 담고있기 때문에 bne 기준에서의 PC는 add을 가리키고 있다.

따라서 i와 j가 다르다면 add 다음의 instruction을 실행해야 하므로 jump distance는 1이 된다.

 

---

대소 비교를 통한 Branch

slt, slti, sge, sle, slti 등을 통해 대소 비교를 한 후 bne를 통해 branch 해야 한다.

때문에 기능 구현을 위한 instruction의 개수가 증가한다.

 

slt, slti / sltu, sltui

<pre>slt   rd,  rs,  rt</pre>

<pre>slti  rd,  rs,  constant</pre>

 

Set Less Then으로, rs가 rt보다 작으면 rd를 1로 set 한다. 크거나 같다면 0으로 set 한다.

<pre>slt, sltu</pre>는 R-format을 사용한다.

 

<pre>slti, sltui</pre>는 rt 대신 constant와 비교하기 위한 것으로 I-format을 사용한다.

 

<pre>sltu</pre>와 <pre>sltui</pre>는 unsigned comparison을 위한 것이다.

주소 등과 같은 값들은 unsigned number이기 때문에 signed number comparison인 slt, slti로 비교할 경우 기대했던 값과는 다른 결과를 나타낸다.

때문에 signed comparison과 unsigned comparison을 분리해야 한다.

 

예를 들어 

<pre>$s0 = 1111 1111 1111 1111 1111 1111 1111 1111

$s1 = 0000 0000 0000 0000 0000 0000 0000 0001</pre>

와 같은 값을 가진 레지스터들이 있다면,

 

<pre>slt  $t0,  $s0,  $s1</pre>을 수행하면 -1 < +1이기 때문에 $t0 = 1이 된다.

그러나 <pre>sltu $t0,  $s0,  $s1</pre>을 수행하면 4,294,967,295 > 1 이기 때문에 $t0 = 0이 된다.

 

Single Instruction으로 하지 않는 이유?

<, <=, >=, >들을 수행하는 하드웨어는 =, ≠ 을 수행하는 하드웨어에 비해 속도가 느리다.

=, ≠ 는 각 비트끼리 비교하면 되기 때문에 연산을 병렬로 하여 빠르게 처리할 수 있지만, <, > 들은 뒤에서부터 차례로 sequential하게 carry가 발생하고 이 carry가 연산에 다시 사용되기 때문에 빠르게 처리할 수 없다.

 

이 때문에 single instruction으로 처리하게 되면 instruction의 clock cycle time(cct)가 증가하게 된다.

이로 인해 모든 instruction들의 cct가 길어지고 성능이 안좋아지게 된다.

따라서 comparison과 branch를 분리하는 것이다.

 

비록 분리하게 되면 IC(Instruction Count)가 증가하게 되지만, 벤치마킹 결과 IC의 증가가 cct의 증가보다 유리하다.

 

---

Unconditional Jump

조건과 관계 없이 항상 jump를 수행한다.

무엇을 이용하여 jump하는지에 따라 다음과 같이 구분된다.

• jump
  • target address를 이용하여 jump
  • j, jal
• jump register 
  • register에 들어있는 주소로 jump
  • jr, jalr

 

j

Target address로 무조건 jump한다.

J-format을 이용한다.

 

J-format은 6bit operation(opcode)과 26bit target address(immediate)로 이루어져있다.

jump는 instruction 단위(word 단위)로 이루어지기 때문에 beq, bne와 마찬가지로 맨 마지막 2개 bit을 생략하여 28bit 범위를 표현할 수 있다.

Address의 맨 상위 4비트는 생략하고, 현재 PC의 상위 4비트를 사용한다.

이를 pseudo-direct addressing이라 한다.

 

24bit -> 26bit... 오타 ㅜㅜ

 

beq를 이용하지 않고 새로운 instruction을 만든 이유?

<pre>beq $r1, $r1, offset</pre>과 같이 beq를 이용해서 jump하게 될 경우 offset은 16bit로 제한된다.

그러나 procedure call, long GOTO 등 많은 경우에서 16bit(사실은 18bit의 범위)보다 더 먼 거리로 jump 해야 한다.

 

따라서 이를 표현할 새로운 format과 instruction이 필요하다.

 

Target address 상위 4bit을 0000으로 사용하지 않는 이유?

Dynamic library는 프로그램 실행 중에 들어오는 부분으로, address의 시작주소 4bit는 0000이 아니다.

따라서 target address 상위 4bit을 0000으로 제한하게 되면 dynamic library로써는 사용할 수 없다.

 

따라서 dynamic library를 포함하여 더 넓은 범위에서 사용하기 위해서 상위 4bit을 current PC의 상위 4bit로 사용한다.

 

28bit을 이용하면 text segment에서 어디든지 jump 할 수 있다.

다만 code에서 dynamic library로의 jump는 불가능하다.

이는 jr(jump register)을 이용해야한다.

 

 

---

jr

jump register로, register의 값의 위치로 jump을 수행한다.

 

jr은 1개의 register만 operand로 사용하기 때문에 어떤 종류의 format을 사용해도 된다.

그러나 R-format의 function code에 여유가 있기 때문에 R-format을 사용한다.

 

jr은 다음과 같은 경우에 사용된다.

• target address가 runtime 정보 일 때(Dynamic binding)
  • Switch-Case 문
  • OOP에서 virtual function
    • polymorphism, dynamic binding
  • Dynamically shared libraries(DLL)
  • Return from procedure call
• full 32-bit jump address가 필요할 때

 

Runtime Information

프로그램 실행의 흐름(runtime)에 따라 jump 할 위치가 결정될 경우 컴파일러는 프로그램 실행 전에는 어디로 jump 할 지 모른다.

따라서 beq, bne를 사용하지 못한다.

이렇게 jump 할 위치가 runtime information 일 경우 jr을 사용한다.

 

Switch-Case

Switch-case 문일 경우 jump 할 위치는 runtime 정보이다.

때문에 항상 특정 위치로 jump하는 j operation을 이용할 수 없다.

switch (k) {
	case 0 :
    	...
        break;
    case 1 :
    	...
        break;
    
    ...
    
    case n :
    	...
        break;   
}

 

jr operation은 jump table과 compiled code을 이용한다.

jump table은 각 case 별 실행할 코드의 시작 주소를 모아 놓은 table 구조이고, compiled code는 각 case 별 실행할 코드를 모아 놓은 것이다.

 

Runtime 정보에 대한 jump에서 bne, beq를 이용하지 않는 이유?

switch 대신 if-else를 반복하여 사용할 수 있다. 그러나 case의 가지수가 많을 경우 비교 횟수가 많아지기 때문에 실행 속도가 느려진다.

때문에 switch-case가 필요하다.

 

Indirection

jump table로 갔다가 compiled table로 이동하는 것 처럼 실행할 코드로 직접 가지 못하고 들렀다 가는 것을 Indirection이라 한다.

비록 instruction이 더 필요하기 때문에 약간 더 느려지지만 direction으로 할 수 없는 경우에 강력하다.

 

OOP and Dynamic Binding

Object-oriented programming에서는 상속을 통해 조상보다 필요한 특성한 추가할 수 있다.

따라서 upcasting(is-a relationship)을 통해 조상 type 대신 자손 type이 사용될 수 있다.

이 때 dynamic binding(runtime binding), polymorphsim에서 runtime information으로 jump를 수행해야 할 경우가 발생한다.

 

예를 들어 아래와 같은 클래스 상속 구조를 가진 객체를 이용하여 ArrayList<Instrument>을 만든다고 하자.

OBJECT.print_type()을 한다면 해당 type을 print하는 코드로 jump 해야 한다.

이 때 어떤 type인가에 대한 것은 runtime information이 된다.

 

Dynamically Shared Library

Dynamic library는 프로그램 실행 중에 들어오기 때문에 어디로 들어올지는 runtime에 의해 결정이 된다.

때문에 jump address를 확정할 수 없다.

 

또한 code와 dynamic library는 다른 text segment이기 때문에 code에서 dynamic library로 jump는 PC의 상위 4bit가 다르기 때문에 불가능 하다.

 

이를 해결하기 위해 jr을 이용하여 32bit address를 register에 담아서 jump를 한다.

 

 

Return from Procedure Call

컴파일러는 누가 어디서 call을 할 지 모른다.

따라서 호출 후 돌아갈 장소는 runtime information이다.

 

Procedure call 실행 후 return을 위해서, caller는 이동하기 전에 return address를 return address register($ra)에 저장한다.

MIPS에서는 r31을 $ra로 사용한다.

return address는 current PC 값을 사용하면 된다.

 

이를 통해 함수 실행이 끝나면 다시 호출했던 다음 주소로 다시 돌아갈 수 있다.

 

<pre>jr   $ra</pre>을 통해 호출했던 다음 주소로 return 한다.

 

---

Procedure Call : <pre>jal, jalr</pre>

return address를 저장하는 것을 link라고 한다.

unconditional jump + return address를 같이 하는 것은 common case이기 때문에 <pre>jal, jalr</pre>을 통해 single instruction으로 지원한다.

• <pre>jal</pre>
  • jump and link
  • link($ra <- return address) 후 jump
  • 같은 text segment에서의 procedure call을 위해 사용
• <pre>jalr</pre>
  • jump and link register
  • link($ra <- return address) 후 register의 값으로 jump
  • 다른 text segment까지 procedure call을 커버 가능

 

---

Basic Block

한 번 시작되면 무조건 실행되는 부분이다.

중간에 끼어드는 branch가 없고, 중간에 다른 곳으로 branch 되지 않는 코드 블럭이다.

branch 여부를 따질 때 basic block의 시작과 끝은 따지지 않는다.

 

 

---

예제

bne, beq 1

 

bne, beq 2