Chapter 2

MIPS

MIPS는 million instructions per second가 아니라 Microprocessor without Interlocked Pipeline Stages로 MIPS Technologies에서 개발한 RISC 계열의 명령어 집합 체계이다.

 

※RISC, CISC?

RISC - Reduced Instruction Set Computer라는 뜻으로 CPU 명령어 개수를 줄여 하드웨어 구조를 좀 더 간단하게 만들었다.

CISC - Complex Instruction Set Computer라는 뜻으로 복잡한 명령어 집합을 갖는 CPU 아키텍쳐이다.

 

---

 

Arithmetic Operations

 

Add, subtract은 3개의 operand가 필요하다.

두 개의 operand는 source이고 나머지 하나는 destination이다.

add a, b, c // a gets b+c

모든 arithmatic operation은 위와 같은 형태를 가진다.

 

※예시

Code : f = (g+h)-(i+j);

Compiled MIPS code:
add t0, g, h #temp t0 = g+h
add t1, i, j #temp t1 = i+j
sub f, t0, t1 #f = t0-t1

 

---

 

Register Operands

 

Arithmetic instruction은 register operand를 사용한다.

MIPS는 32*32-bit register file을 사용하도록 설계되어 있다. 32-bit data를 word라고 부른다.

 

$t0, $t1, ... , $t9은 temporary value라 부른다.

$s0, $s1, ... , $s7은 saved variable라 부른다.

 

※예시

C code:
f = (g+h) - (i+j); //f,...,j는 $s0,...,$s4에 저장되어 있다.

Compiled MIPS code:
add $t0, $s1, $s2
add $t1, $s3, $s4
add $s0, $t0, $t1

 

---

 

Memory Operands

 

Main memory는 arrays, structures, dynamic data 등에 사용된다.

 

Arithmetic operation을 위해 register operand를 사용하려면 memory operand를 통해 main memory에 있는 data를 먼저 load 해줘야 한다. 또 저장된 register를 memory에 store해줘야 한다. 이러한 구조를 Load-Store 구조라고 한다.

 

Memory는 1byte로 나누어진다. Word는 32-bit이므로 memory에서는 4byte를 사용하게 된다.

 

MIPS는 Big Endian이다.

 

Big Endian, Little Endian이란?

 

 

컴퓨터가 주소를 저장할 때 순서에 따라 little endian과 big endian으로 구분한다.

위는 0x01234567를 저장할 때 예시를 든 것인데 big endian은 낮은 주소부터 높은 주소까지 순차적으로 값을 저장한 반면에 little endian은 높은 주소부터 낮은 주소 순으로 값을 저장하였다.

 

※예시

C code:
g = h+A[8]; #g는 $s1, h는 $s2, A의 base address는 $s3에 저장되어 있다.

Compiled MIPS code:
lw $t0, 32($s3) #32는 offset으로 8(index) * 4(address size)=32
add $s1, $s2, $t0

 

※예시2

C code:
A[12]=h+A[8]; // h는 $s2에 있고 A의 base address는 $s3에 있다.

Compiled MIPS code:
lw $t0, 32($s3) //load
add $t0, $s2, $t0
sw $t0, 48($s3) //store

 

---

Register vs Memory

Register는 Memory에 비해 접근이 빠르다.

Memory는 항상 Load와 Store를 해줘야 하기 때문에 더 많은 실행 시간을 소모한다.

 

따라서 Compiler는 가능하다면 register를 많이 사용해야 한다. Register optimization이 중요하다.

 

---

 

Immediate Operands

 

Immediate operand에는 상수가 들어간다.

음수를 넣을 수 있기 때문에 subtract immediate instruction은 없다.

 

addi $s2, $s1, -1

 

Immediate operand는 load instruction이 필요없으므로 빠르다.

 

0은 값을 옮길 때 유용하게 사용된다.

addi $t2, $s1, $zero // $s1값을 $t2로 복사

 

---

 

Sign Extension

 

숫자를 더 많은 bit로 나타낼 수 있어야 하는데 값은 보존되어야 한다.

 

addi : extend immediate value

lb, lh : extend loaded byte/halfword

beq, bne : extend the displacement

 

sign interger을 늘릴 때는 sign bit를 왼쪽으로 복제해주면 된다.(unsign은 0을 복제)

 

※예시 8-bit to 16-bit

2 : 0000 0010 -> 0000 0000 0000 0010

-2 : 1111 11110 -> 1111 1111 1111 1110

 

---

 

MIPS R-format Instructions

Register number

• $t0~$t7 : 8~15
• $t8~$t9 : 24~25
• $s0~$s7 : 16~23

 

Instruction fields

• op : operation code (opcode)
• rs : first source register number
• rt : second source register number
• rd : destination register number
• shamt : shift amount (00000 for now)
• funct : function code (extends opcode)

rs, rt, rd가 5bit인 이유는 MIP가 32*32 bit register를 사용하기 때문이다. (log32=5)

 

※예시

값이 너무 길기 때문에 hexadecimal(16진법)으로 표현 할 수 있다.

 

---

 

MIPS I-format Instructions

 

 

R-format instruction의 단점은 5bit 이상 주소나 수를 표현하지 못한다는 것이다.

따라서 main memory 주소나 큰 수를 더하거나 뺄 때는 I-format instruction을 사용해야 한다.

 주소값을 가져오는 bne, beq, lw, sw 등의 분기문과 상수연산을 하는 addi, addiu, andi 등에 사용한다.

 

 

---

 

Logical Operations

 

MIPS에서도 Logical operation을 지원한다.

 

Shift operation은 R-format에서 shamt를 통해 표현 할 수 있다.

sll(shift left logical)은 왼쪽으로 한 칸 움직이라는 의미이며 곱하기 2와 같은 의미이다. 왼쪽의 빈 공간은 0으로 채운다.

srl(shift right logical)은 오른쪽으로 한 칸 움직이라는 의미이며 나누기 2와 같은 의미이다. 오른쪽의 빈 공간은 sign bit로 채운다.

 

MIPS는 NOR(3-operand instruction)을 지원한다.

 

---

Conditional Operations

 

beq rs, rt, L1 - 만약 rs==rt이면 labeled L1으로 가라

bne rs, rt, L1 - 만약 rs!=rt이면 labeled L1으로 가라

j L1 - 조건 없이 labeled L1으로 가라

 

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		//offset
	add	$t1, $t1, $s6	//offset+base address of save
       lw	$t0, 0($t1)		//load save[i]
       bne	$t0, $s5, Exit	//compare save[i] and k
       addi	$s3, $s3, 1
       j	Loop
Exit:....

여기서 봐야 할 것은 왼쪽으로 두 칸 움직인 것인데(sll) 이는 곱하기 4와 같은 의미이고 element의 size가 4byte라는 것을 가정했다는 것이다.

 

---

 

Basic Blocks

 

Basic block이란 embedded branch와 branch target이 없는 instruction sequence를 의미한다.(beginning과 end는 존재)

 

Compiler는 최적화를 위해 basic block를 인지해야 한다.

 

 

---

 

More Conditional Operations

 

conditioin이 true라면 result를 1로, false라면 result를 0으로 한다.

 

slt rd, rs, rt // if (rs<rt) rd=1; else rd =0;
slti rt, rs, constant // if(rs<constant) rt=1; else rt = 0;

slt $t0, $s1, $s2 // if ($s1 < $s2)
bne $t0, $zero, L // branch to L

 

slt, slti를 기억하자.

Signed comparison : slt, slti

Unsigned comparison : sltu, sltui

 

---

 

Procedure Calling

1. 매개변수를 register에 넣는다.
2. 호출되는 procedure로 control을 바꾼다.
3. procedure에 대한 저장공간을 얻는다.
4. procedure에 연산을 수행한다.
5. Caller에게 연산 결과를 넘긴다.
6. call이 발생한 곳을로 돌아간다.

 

---

Register Usage

 

• $a0~$a4 : argument (reg's 4~7)
• $v0,$v1 : result values (reg's 2 and 3)
• $t0~$t9 : temporaries (reg's 8~15). Can be overwritten by callee
• $s0~$s7 : saved(reg's 16~23). Must be saved/restored by callee
• $gp : global pointer for static data (reg 28)
• $sp : stack pointer (reg 29)
• $fp : frame pointer (reg 30)
• $ra : return pointer (reg 31)

 

---

 

Procedure Call Instructions

 

Procedure call : jump and link

jal ProcedureLabel

• jal 다음에 오는 instruction의 주소를 $ra에 저장한다.
• target address로 jump한다.

 

Procedure return : jump register

jr $ra

• $ra를 PC(program counter)에 저장한다.