MIPS Instruction set

Registers

레지스터	사용처
$a0 ~ $a3	argument값을 저장할 때 사용
$v0, $v1	return값을 저장할 때 사용 (long 타입의 경우 두 레지스터를 사용하기 위함)
$t0 ~ $t9	임시로 값을 저장할 때 사용
$s0 ~ $s7	사용빈도가 높은 값을 저장할 때 사용
$gp	global pointer (for stack data)
$sp	stack pointer
$fp	frame pointer
$ra	return address
$zero	0 상수값을 갖고있음. 덮어쓰기 불가

 

 

Instructions

명령어	읽기	기능
add A, B, C	add	A = B + C
addi A, B, c	add immediate	A = B + c  // c는 상수. (subi는 없고 대신 음수 상수를 이용)
sub A, B, C	substract	A = B - C
mul A, B, C	multiplication	A = B * C
lw A, c(B)	load word	A = *(&B + c)  // 메모리 B에서 c offset에 저장된 값 불러오기
sw A, c(B)	save word	*(&B + c) = A  // 메모리 B에서 c offset에 값 저장하기
sll A, B, c	shift left	A = B << c
srl A, B, c	shift right	A = B >> c
and A, B, C	and	A = B & C
andi A, B, c	and immediate	A = B & c  // c는 상수.
or A, B, C	or	A = B | C
ori A, B, c	or immediate	A = B | c  // c는 상수.
nor A, B, C	not or	A = !(B | C)
slt A, B, C	statement lesser then	if (B < C): A = 1 else A = 0
slti A, B, c	statement lesser then immediate	if (A < c): A = 1 else A = 0  // c는 상수.
sltu A, B, C	statement lesser then unsigned	if (B < C): A = 1 else A = 0  // A, B: unsigned value
sltui A, B, c	statement lesser then immediate unsigned	if (A < c): A = 1 else A = 0  // c는 상수, A, B: unsigned value
beq A, B, L	branch equal	A == B: jump to L
bne A, B, L	branch not equal	A != B: jump to L
jal L	jump and link	리턴 주소를 $ra 레지스터에 저장하고, L로 jump함.
j L	jump	jump to L
jr $ra	jump return	$ra 레지스터의 값을 program counter에 복사하고, 리턴 주소로 jump함.
lb A, c(B)	load byte	lw와 동일, 단 읽어오는 단위가 작음
lh A, c(B)	load halfword	lw와 동일, 단 읽어오는 단위가 작음
sb A, c(B)	save byte	sw와 동일, 단 저장하는 단위가 작음
sh A, c(B)	save halfword	sw와 동일, 단 저장하는 단위가 작음
lbu A, c(B)	load byte unsigned	lw와 동일, 단 읽어오는 단위가 작음, A: unsigned value
lhu A, c(B)	load halfword unsigned	lw와 동일, 단 읽어오는 단위가 작음, A: unsigned value
lui A, c	load upper immediate	상수 c의 상위 16 bits를 A 레지스터에 load하고 나머지 하위 16 bits는 0으로 채운다.

 

* Tips

subi A, B, c -> addi A, B, -c

move A, B   -> add A, B, $zero

not A, B       -> nor A, B, $zero

 

s0에 0x12345678 (32 bits constant) load하기 ->

lui $s0, 0x1234

ori $s0, $s0, 0x5678

 

 

 

Memory Operands

1 Word = 4 Bytes = 32 bits

 

메모리에 데이터가 저장되는 단위는 Byte지만, 처리되는 단위는 Word 단위이다.

따라서 메모리 인덱스는 메모리 오프셋의 4배 만큼 씩 계산을 해주어야 한다.

A[9] = h + A[8];

h = s2, A = s3

lw $t0, 32($s3)
add $t0, $s2, $t0
sw $t0, 36($s3)

 

헷갈리지 말아야 할 점은 memory operands에서 사용되는 offset 값은 word 단위로 지정된다.

하지만, j, beq와 같이 명령어의 주소(태그)에 사용되는 값은 bit 단위로 저장된다.

그렇기에 2진수 코드로 변환했을 때, address는 bit 단위로 표기해야 하지만,

offset은 word 단위로 표기해야 한다. (아래 PC 그림 참고)

 

 

Signed Negation

* 2's complement

$$  -x = \bar{x} + 1 $$

  2 = 0000 0010
-2 = 1111 1101 + 1
     = 1111 1110

 

 

Program Counter (PC)

pc는 현재 프로그램이 수행하고 있는 명령어의 위치를 저장하는 레지스터이다.

따라서 대부분의 주소 지정은 pc에 offest를 더하거나 빼는 상대 주소로 지정하게 되는데,

아래서 살펴볼 J-format Instruction (j, jal)의 경우에는 절대 주소로 지정한다는 특징이 있다.

 

pc가 가리키고 있는 명령어를 수행하기 전, pc는 값이 1 word가 증가된 상태로 명령어를 수행하게 된다.

(오타 정정) 80000 주소의 shamt 값은 4 가 아닌 2다.

따라서 R, I-format의 주소 지정에는 원하는 index offset보다 1작게 지정해야만 한다.

 

 

MIPS format Instructions

- R-format (Register)

op: operation code (opcode)

rs: first source register number

rt: second source register number

rd: destination register number

shamt: shift amount (보통 00000)

funct: function code (extends opcode)

 

 

- I-format (Immediate)

 

- J-Format (Jump)

다른 포멧과 다르게 주소 지정방식이 절대 주소로 지정된다.

따라서 코드상에서 아주 멀리 떨어진 부분까지 이동해야 하는 경우 j, jal 명령어를 사용하게 된다.

L1 이 현재 pc로 부터 16 bits만으로 표현할 수 없을 만큼
멀리 (18 bits addressing) 떨어져 있는 경우

// from
        beq $s0, $s1, L1
// to
        bne $s0, $s1, L2
        j L1
L2:   ...

 

 

Compiled MIPS code examples

* 강조 표시는 대부분의 상황에서 많이 쓰이는 유용한 테크닉을 의미

 

- 기본적인 분기문 사용법

if (i==j) f = g + h;
else f = g - h;

f = s0, g = s1, h = s2, i = s3, j = s4

        beq $s3 $s4 Eql
        sub $s0, $s1, $s2
        j Exit
Eql: add $s0, $s1, $s2
Exit: ...

 

- 기본적인 반복문 사용법

while (save[i] == k) i += 1;

i = s3, k = s5, save = s6

loop: sll $t0, $s3, 2  // Word단위 이기에 offset은 4배
        add $t0, $t0, $s6
        lw $t1, 0($t0)
        beq $t1, $s5, Exit
        addi $s3, $s3, 1
        j loop
Exit: ...

 

- 기본적인 leaf 함수 호출 사용법 (다른 함수를 호출하지 않는 함수)

int leaf_example (int g, h, i, j) {
    int f;
    f = (g + h) - (i + j);
    return f;
}

g = a0, h = a1, i = a2, j = a3
f = s0, result in v0

leaf_example:
       addi $sp, $sp, -4
        sw $s0, 0($sp)
       add $t0, $a0, $a1
       add $t1, $a2, $a3
       sub $s0, $t0, $t1
       add $v0, $s0, $zero
       lw $s0, 0($sp)
       addi $sp, $sp, 4
       jr $ra

* stack의 메모리는 offset이 작아지는 방향으로 확장된다.

  따라서 메모리 공간을 확보할 때 -4를 해줘서 인덱스 1개 만큼의 공간을 확보하여 s0를 저장한 것이다.

 

- Non-leaf 함수 호출 사용법 (다른 함수를 호출하는 함수)

int fact (int n) {
    if (n < 1) return 1;
    else return n * fact(n-1);
}

n = a0, result in v0

fact: addi $sp, $sp, -8
         sw $a0, 0($sp)  // save n
        sw $ra, 4($sp)  // save return address
        slti $t0, $s0, 1
        beq $t0, $zero, L1  // n >= 1: jump to L1
        addi $v0, $zero, 1  // case n < 1
        addi $sp, $sp, 4
        jr $ra
L1:   addi $a0, $a0, -1  // case n >= 1
        jal fact
        lw $a0, 0($sp)  // load n
        lw $ra, 4($sp)  // load return address
        addi $sp, $sp, 8
       mul $v0, $a0, $v0
       jr $ra

* 일단 함수를 벗어나면 그 이후에 레지스터에 무슨 값이 들어있는지는 신경쓰지 않는다.

  단, 리턴 후 사용해야 할 값은 적절하게 sp에 저장했다가 다시 불러와야 한다.

 

- strcpy

void strcpy (char x[], char y[]) {
    int i;
    i = 0;
    while ((x[i] = y[i]) != '\0')
        i += 1;
}

x = a0, y = a1, i = s0

strcpy:
        addi $sp, $sp, -4
        sw $s0, 0($sp)
        add $s0, $zero, $zero
L1:   add $t0, $a1, $s0
         lbu $t1, 0($t0)  // load byte는 별도로 4를 곱하여 인덱싱 할 필요 없음
        add $t0, $a0, $s0
         sb $t1, 0($t0)  // save byte는 별도로 4를 곱하여 인덱실 할 필요 없음
        beq $t1, $zero, L2
        addi $s0, $s0, 1
        j L1
L2:  lw $s0, 0($sp)
       addi $sp, $sp, 4
       jr $ra

 

- sort

void sort (int v[], int n) {
   int i, j;
   for (i = 0; i < n; i += 1) {
      for (j = i-1; j >= 0 && v[j] > v[j+1]; j -= 1) {
          swap(v, j);
      }
   }
}

void swap (int v[], int k) {
   int tmp;
   tmp = v[k];
   v[k] = v[k+1];
   v[k+1] = tmp;
}

v = a0, n = a1, i = s0, j = s1,
v = a0, k = a1, tmp = t1

sort:
        addi $sp, $sp, -20
        sw $s0, 0($sp)
        sw $s1, 4($sp)
        sw $s2, 8($sp)
        sw $s3, 12($sp)
        sw $ra, 16($sp)  // Non-leaf 함수의 경우 return address를 저장해야 함.
        add $s2, $a0, $zero  // swap에서도 a0이 쓰임. 따라서 상위 함수에서 별도 공간(s2)에 a0를 저장하여 사용
        add $s3, $a1, $zero  // swap에서도 a1이 쓰임. 따라서 상위 함수에서 별도 공간(s3)에 a1를 저장하여 사용
        add $s0, $zero, $zero
for1: slt $t0, $s0, $s3  // i < n -> t0 = 1
        beq $t0, $zero, Exit1  // t0 = 0 (i >= n) -> exit1
        addi $s1, $s0, -1
for2: slt $t0, $s1, $zero  // j < 0 -> t0 = 1
        bne $t0, $zero, Exit2   // t0 != 0 (j < 0) -> exit2
        sll $t1, $s1, 2
        add $t1, $s2, $t1
        lw $t2, 0($t1)
        lw $t3, 4($t2)
        slt $t0, $t3, $t2  // v[j+1] < v[j] -> t0 = 1
        beq $t0, $zero, Exit2  // t0 = 0 (v[j+1] >= v[j]) -> exit2
        add $a0, $s2, $zero  // swap 함수 호출 전 a0의 값을 지정
        add $a1, $s1, $zero  // swap 함수 호출 전 a1의 값을 지정
        jal swap
        addi $s1, $s1, -1
        j for2
Exit2: addi $s0, $s0, 1
        j for1
Exit1: lw $s0, 0($sp)
        lw $s1, 4($sp)
        lw $s2, 8($sp)
        lw $s3, 12($sp)
        lw $ra, 16($sp)
        addi $sp, $sp, 20
        jr $ra
...
swap:
        sll $t0, $a1, 2
        add $t0, $a0, $t0
        lw $t1, 0($t0)
        lw $t2, 4($t0)
        sw $t2, 0($t0)
        sw $t1, 4($t0)
        jr $ra

* 긴 코드 작성 팁

  - 우선 코드에 맞도록 작성한다.

  - 필요한 경우에만 s 레지스터를 사용하고, 사용한 경우에 함수 시작과 끝에 sp에 저장한다.

  - Non-leaf 함수의 경우 a 레지스터의 값을 s 레지스터에 옮겨 사용하는 것이 편하다.

  - Non-leaf 함수의 경우 반드시 ra 레지스터의 값을 sp에 저장한다.

 

 

Instruction Architecture 참고사항

MIPS는 reduced instruction set (RISK)에 속한다.

따라서 하드웨어 구현이 쉽다는 장점이 있지만,

그만큼 강력한 instruction이 없어 성능이 떨어질 수 있다.

(반대로 CISK는 구현은 어렵지만, 복잡한 명령어를 하드웨어 수준에서 구현했기에 파워풀한 성능을 기대할 수 있다.

하지만, 특정 명령어가 너무 많은 클럭에 명령이 수행될 경우 전체적인 성능 하락이 있을 수 있다.)

 

또한 IA 설계시 이전 명령어와의 호환성 역시 고려하여 설계해야 한다.