MIPS I-format Instructions
이는 immediate instructions들을 위한 포맷입니다. 이는 source가 될 수 있는 자리가 최대 2개가 있다는 점에서 R-format과 차이를 보입니다.
- rs: source register number
- rt: detination or source register number; source가 될 수도 있고, target이 될 수도 있는 자리입니다.
- constant: sign의 경우 -2^15 to +2^15-1까지의 수를 나타낼 수 있고, unsigned의 경우 0 to +2^16-1까지의 수를 나타냅니다.
- address: rs의 base address에 더해지는 offset을 나타냅니다.
r-format과 i-format을 같은 32bit체계로 둠으로써 디코딩하기 쉽게 하였습니다. 즉, 포맷을 달리 하면서 비트의 수도 다르게 한다면 더욱 복잡한 명령도 나타낼 수 있지만 그렇게 하지 않음으로써 RISC구조를 만들었습니다. *Design Principle 4: Good design demands good compromises
MIPS (RISC) Design Principle
이 쯤에서 MIPS의 디자인 철학에 대해 한 번 정리하겠습니다:
- Simplicity favors regularity - fixed size instructions, small number of instruction formats, opcode always the first 6-bit
- Smaller is faster - limited instruction set, limited number of registers in register file, limited number of addressing modes
- Make the common case fast - arithmetic operands from the register file (load-store machine), allow instructions to contain immediate operands (e.g., addi)
- Good design demands good compromises - three instruction formats
MIPS Memory Access Instructions
I-format의 대표적인 예로 데이터 이동이 있습니다. MIPS에서의 기본적인 데이터 이동은 memory 접근과 관련됩니다. (1) 데이터를 cPU로 load하는 명령과 (e.g., lw) (2) CPU의 레지스터로부터 메모리로 데이터를 옮기는 store명령 (e.g., sw)가 있습니다. I-format에서 사용하는 offset의 크기가 16-bit이기 때문에 사용가능한 word단위는 ±2^13 words입니다.
lw $t0, 4($s3) # load word from memory
sw $t0, 8($s3) # store word to memory
*이때 lw같은 경우 word단위의 데이터를 load하는 것이기 때문에 offset도 word단위로, 즉 4의 배수로 나타납니다.
Aside: Loading and Storing Bytes
MIPS는 word단위 뿐만 아니라 다양한 단위의 데이터를 load하거나 store하는 연산들을 갖고 있습니다. 이때 메모리나 레지스터에는 어떻게 저장될까요? 이는 가장 오른쪽 비트들부터 채워넣는 방식으로 저장됩니다.
lb $t0, 1($s3) # load byte from memory
sb $t0, 6($s3) # store byte to memory
*이때 offset은 word단위로 데이터를 저장하는 것이 아니기 때문에 4의 배수가 아님을 알 수 있다.
MIPS Immediate Instructions
작은 상수들은 일반적으로 피연산자로 자주 사용됩니다. (1) 일반적으로 메모리에 해당 상수를 저장하고 연산할 때 CPU로 load하는 방법이 있습니다. 하지만 이 방법은 load후 연산, 즉 두 번의 명령이 필요합니다. (2) 다른 방법으로는 $zero와 같이 hard-wired register를 이용해서 자주 사용되는 상수들을 레지스터에 묶어버리는 것입니다. 하지만 이는 하드웨어의 도움이 많이 필요하기에 구현하기 힘듭니다.
이때 I-format을 사용합니다. constant field를 통해 ±2^15정도의 상수를 load없이 연산에 사용할 수 있습니다.
Aside: How about larger constants?
만약 constant field의 범위를 벗어나는 수를 빠르게 사용하고 싶은 경우, 16-bit를 넘어서는 수, 예를 들어 32-bit수를 사용하고싶은 경우 다음과 같은 방법을 사용할 수 있습니다.
(1) 앞쪽의 16-bit는 lui연산을 통해 저장합니다. (뒤쪽 16-bit는 모두 0)
lui $t0, 1010101010101010
(2) 뒤쪽의 16-bit는 ori연산을 통해 저장합니다. (앞쪽 16-bit는 모두 0)
ori $t0, $t0, 1010101010101010
(3) 두 연산의 결과를 or연산을 통해 하나로 묶어줍니다.
Conditional Operations
조건문은 branch를 통해 구현됩니다.
- beq rs, rt, L1; rs와 rt가 같은 경우 L1이 가르키고 있는 곳으로 이동합니다. (conditional branch)
- bne rs, rt, L1; rs와 rt가 다른 경우 L1이 가크키고 있는 곳으로 이동합니다. (conditional branch)
- j L1; L1이 가르키고 있는 곳으로 무조건 이동합니다. (unconditional jump)
Compliling If statements
// C code:
if (i==j) f = g + h;
else f = g - h;# Compiled MIPS code:
bne $s3, $s4, Else
add $s0, $s1, $s2
j Exit
Else: sub $s0, $s1, $s2
Exit: ...
// C code:
while (save[i] == k) i += 1;# i in $s3, k in $s5, address of save in $s6
# Compiled MIPS code:
Loop: sll $t1, $s3, 2 # i = i * 4; integer는 4byte이니까
add $t1, $t1, $s6
lw $t0, 0($t1)
bne $t0, $s5, Exit
addi $s3, $s3, 1
j Loop
Exit: ...
Basic Blocks
basic block은 명령들의 나열인데 다음과 같은 조건을 따릅니다:
- No embedded branches (except at end)
- No branch targets (except at beginning)
branch가 들어가는 부분도, 나가는 부분도 없는 code block을 basic block이라고 부르며, 이는 complier가 코드 최적화를 하는 대상이 됩니다. 더 우수한 processor일수록 basic block에 들어있는 명령들을 가속하여 수행합니다.
MIPS Constrol Flow Instructions
I-format의 instruction으로 어떻게 branch를 나타낼 수 있을까요? 16-bit address field에 target address를 넣어주는데, 이는 현재 명령 위치로부터 offset입니다.
Specifying Branch Destinations
Program counter, PC를 base address로 하여 offset을 설정합니다. 이때 PC는 다음 연산에서 +4가 된다는 점을 기억해야합니다. 이를 그림으로 나타내면 다음과 같습니다:
이때 명령의 단위는 word이기 때문에, offset또한 word단위로 4의 배수입니다. 하지만 sw나 lw와 달리 최종 address의 가장 오른쪽에는 00이 고정으로 들어갑니다. *sw나 lw는 뒤에 00을 포함하여 16-bit이지만, branch의 경우 뒤에 00을 빼고 16-bit를 offset으로 사용할 수 있습니다.
즉 branch에서 사용할 수 있는 word단위의 범위는 ±2^15정도입니다 (sw, lw는 ±2^13).
In Support of Branch Instructions
하지만 bne, beq만으로는 모든 조건문을 표현할 수 없습니다. 그래서 나온 것이 set on less than, slt입니다. slt는 source1이 source2보다 작은 경우 target이 1로, 반대의 경우는 target이 0으로 설정되는 것입니다.
slt $t0, $s0, $s1 # if $s0 < $s1 then
# $t0 = 1 else
# $t0 = 0
* slt에는 다양한 버전이 존재합니다. (1) immediate 버전인 slti, (2) unsigned 버전인 sltu, (3) immediate unsigned 버전인 sltiu가 있습니다.
More Branch Instructions
slt만으로는 (~보다 작다) 만으로는 ~보다 크거나 같다. 등등의 더 많은 조건문을 표현하기는 어렵습니다. 따라서 $zero와 slt, beq, bne를 이용해서 다양한 조건문을 만듭니다. *~보다 크거나 같다 등등의 조건들을 모두 명령으로 만들면 RISC에 위반...
signed vs. unsigned
slt, slti와 sltu, sltiu는 정말 다른 결과를 만들 수 있습니다.
Other Control Flow Instructions
MIPS에서는 unconditional jump를 위한 명령어 j를 지원합니다.
j label # go to label
이는 MIPS 명령어 포맷중 j-format을 활용합니다. 아래의 그림은 j-format의 형태와 j명령을 통해 최종 address가 나오는 과정을 그림으로 나타낸 것입니다:
*참고로 jump의 경우 현재 PC에서 offset을 더하는 것이 아니므로 branch명령과 달리 PC가 +4되는 경우를 고려하지 않아도 됩니다.
Aside: Branching Far Away
만약 branch를 하는 경우 16-bit보다 먼 범위의 곳으로 이동하고싶을 때는 jump와 branch를 섞어서 사용하면 됩니다.
beq $s0, $s1, L1 # ..! L1 is too far away from this PC
bne $s0, $s1, L2
j L1 # now we can go to L1 by j which has 26-bit field
L2: ...
