[Computer architecture] MIPS Instructions

Design Principle

(1) Simplicity favors Regularity

(2) Smaller is Faster

(3) Make the common case fast

(4) Good design demands good compromises

Types

1. Arithmetic Operations

a = b + c + d;

add a, b, c
add a, a, d

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

add t0, g, h
add t1, i, j
sub f, t0, t1

MIPS에는 32개의 '32-비트 레지스터'(0번~31번)이 있다.

워드 사이즈 : 32비트 아키텍쳐에서 프로세서는 32비트 청크로 데이터와 명령어를 처리할 수 있다.

Temporary Registers (10개) : $t0, $t1, ... , $t9

Saved Registers (8개) : $s0, $s1, ..., $s7

// f, ..., j stored in $s0, ..., $s4

f = (g+h)-(i+j)

add $t0, $s1, $s2
add $t1, $s3, $s4
sub $s0, $t0, $t1

Immediate Instructions

: There is no immediate instruction for subtract, Use negative constant for addi

addi $s3, $s3, 4

addi $s2, $s1, -1

$zero

overwritten이 불가능하다

레지스터 사이에서 데이터를 옮길 때 유용하다

add $t2, $s1, $zero

2. Memory Instructions

메인 메모리 - 컴포지트 데이터(배열, 구조체, 동적데이터..)에 사용됨

메모리에 접근하기 위하여 메모리 주소를 알아야 한다, 각각의 주소는 1바이트(8비트)로 나타내어진다.

워드(32비트)는 메모리에 정렬되어 있다 : 주소는 반드시 4의 배수이어야 한다.

빅엔디안 : MSB가 가장 낮은 메모리 주소에 저장된다.

리틀엔디안 : LSB가 가장 낮은 메모리 주소에 저장된다.

lw (load word), sw(store word)

lw dest, offset(base address)

// for inedx 8, it requires an offset of 32(4 bytes per word)

g = h + A[8]

lw $t0, 32($s3)
add $s1, $s2, $t0


A[12] = h + A[8]

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

레지스터에서 스필(Spill)

레시트어에 저장할 수 있는 데이터가 넘칠 때, 사용 중인 데이터를 레지스터에서 메모리로 옮기는 과정

적게 사용되는 변수들에 대해서만 메모리로 스필한다

레지스터 최적화는 효율성을 위해 중요하다

MIPS에서 signed extension은 부호 비트를 유지하면서 더 큰 데이터 형식으로 확장하는 과정을 말한다.

ex) lb $t0, 0($t1)

# $t1 주소에서 1바이트를 읽고, 부호 확장하여 $t0에 저장

addi : addi에서 사용되는 즉시 값은 16비트이기 때문에, 그 값을 32비트로 변활 할 때 signed extension을 수행한다

lb, lh : extend loaded byte / halfword

ex) beq $rs, $rt, offset

ex) bne $rs, $rt, offset

여기서 offset은 16비트이므로 signed extenstion을 통해 32비트로 확장한다.

3. Logical Instructions

shamt : how many positions to shift

sll (Shift Left Logical) : 왼쪽으로 쉬프트하고 0을 채운다, 2^i 곱한 것과 동일

srl (Shift Right Logical) : 오른쪽으로 쉬프트하고 0을 채운다, 2^i로 나눈 것과 동일(unsigned 만)

and : Useful to mask

1로 and한 부분의 결과만 나오고 나머지는 0으로 만든다

or : Useful to include

1로 or한 부분을 1로 만든다, 나머지는 변화 없는 상태에서

nor : 두 비트가 모두 0일 때만 1을 반환하며, 그 외의 경우는 0을 반환

nor $t0, $t1, $zero

$t1 레지스터에 저장된 값과 0을 nor 연산한 후 $t0에 저장

4. Conditional Instructions

beq rs, rt, L1

만약에 rs == rt이면 L1블록으로 이동

bne rs, rt, L1

만약에 rs != rt이면 L1블록으로 이동

j L1

무조건적으로 L1블록으로 점프

if(i==j)
	f = g + h;
else
	f = g - h;
// f,g ...는 $s0, $s1, ...


bne $s3, $s4, Else
add $s0, $s1, $s2
j Exit
Else: sub $s0, $s1, $s2
Exit: ...

while(save[i] == k)
	i += 1
# i는 $s3, k는 $s5, address는 $s6에 저장됨


Loop : sll $t1, $s3, 2
       add $t1, $t1, $s9
	   lw $t0, $0($t1)
       bne $t0, $s5 Exit
       addi $s3, $s3, 1
       j Loop
Exit: ...

slt rd, rs, rt

slti rt, rs, constant

Use in combination with beq, bne

• To create all relative conditions { ==, !=, <, <=, >, >= }

• Example : slt $t0, $s1, $s2

bne $t0, $zero, L

* blt(Branch on Less Than) 이나 bge(Branch on Greater than or Equal)을 사용하지 않는 이유

<, > 는 !=, =보다 느리다

slt, slti는 signed로 비교

sltu, sltui는 unsigned로 비교

5. Branch/Jump Instructions

* MIPS 프로시저 호출

레지스터에 매개변수 배치: 호출할 프로시저에 필요한 매개변수를 레지스터에 저장합니다. MIPS에서는 일반적으로 $a0부터 $a3까지의 레지스터를 사용하여 최대 4개의 매개변수를 전달합니다.
프로시저로 제어 이동: 프로시저를 호출하기 위해 점프 명령어(jal)를 사용하여 제어를 해당 프로시저로 이동시킵니다. 이때 현재 명령어의 주소는 $ra 레지스터에 저장되어, 호출이 끝난 후 복귀할 수 있게 됩니다.
프로시저를 위한 저장공간 확보: 프로시저의 지역 변수를 저장하기 위해 스택에 메모리를 할당합니다. 이는 보통 스택 포인터($sp)를 조정하여 이루어집니다.
프로시저의 작업 수행: 프로시저가 필요한 연산을 수행합니다. 이 단계에서 주어진 매개변수를 사용하여 계산하거나 작업을 진행합니다.
결과를 호출자용 레지스터에 배치: 프로시저가 수행한 결과를 레지스터에 저장합니다. 일반적으로 반환 값은 $v0 레지스터에 저장됩니다.
호출한 위치로 반환: 프로시저의 작업이 끝난 후, jr $ra 명령어를 사용하여 $ra에 저장된 주소로 돌아가며, 호출이 완료됩니다.

jal ProcedureLabel

// jump and link
// Address of following instruction (PC+4) put in $ra
// Jumps to target address
// 돌아올 주소를 $ra에 저장하고 프로시저 실행


jr $ra

// jump-register
// copies $ra to PC
// can also be used for computed jumps

$sp (Stack Pointer)

역할: 현재 스택의 최상위 주소를 가리킵니다. 함수 호출 시 지역 변수, 매개변수 및 반환 주소를 저장하기 위해 스택을 관리하는 데 사용됩니다.
변화: 함수 호출 또는 반환 시 스택 포인터는 변동이 있습니다. 새로운 지역 변수를 할당할 때 $sp는 줄어들고, 변수 해제 시 다시 증가합니다.
사용 예: 스택에 값을 푸시(push)하거나 팝(pop)할 때 사용됩니다.

$fp (Frame Pointer)

역할: 현재 함수의 스택 프레임의 시작 주소를 가리킵니다. 각 함수가 호출될 때마다 스택 프레임이 생성되며, $fp는 이 프레임의 기준점을 제공합니다.
변화: 함수 호출 시 $fp는 새로운 함수의 스택 프레임을 가리키도록 업데이트되며, 함수가 반환될 때는 이전 프레임의 주소로 복원됩니다.
사용 예: 지역 변수 및 매개변수에 접근할 때 상대 주소를 계산하는 데 유용합니다.

$sp는 스택의 현재 위치를 가리키며, 스택의 동적 변화를 반영합니다.
$fp는 특정 함수의 고정된 프레임 위치를 가리키며, 해당 함수의 지역 변수와 매개변수에 접근하는 데 사용됩니다.

스택은 높은 메모리 주소에서 낮은 메모리 주소로 내려가면서 커진다

int leaf_example (int g, h, i, j){
	int f;
    f = ( g + h ) - ( i + j );
    return f;
}
// Arguments g, ..., j in $a0, ..., $a3
// f in $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

int fact(int n){
	if(n < 1) return f;
    else return n*fact(n-1);
}
// Argument n in $a0
// Result in $v0

fact:
	addi $sp, $sp, -8
    sw $ra 4($sp)
    sw $a0 0($a0)
    slti $t0, $a0, 1
    beq $t0, $zero, L1
    addi $v0 $zero, 1
    addi $sp, $sp, 8
    jr $ra
L1: addi $a0, $a0, -1
	jal fact
   	lw $a0, 0($sp)
    lw $ra, 4($sp)
    addi $sp, $sp, 8
    mul $v0, $v0, $a0
    jr $ra

MIPS에서 beq 명령어는 두 레지스터의 값이 같을 때 지정된 주소로 분기합니다. $ra는 주로 함수의 리턴 주소를 저장하는 데 사용되며, 일반적으로 jal 명령어를 통해 함수 호출 시 사용됩니다.

beq 명령어가 실행될 때, 분기가 발생하면 프로그램 카운터(PC)가 업데이트되어 지정된 주소로 이동하게 됩니다. 이때 $ra는 영향을 받지 않습니다.

즉, $ra는 함수 호출 시에만 사용되고, beq와는 직접적으로 관련이 없습니다. beq에서 분기할 때 바로 다음 명령어의 주소가 $ra에 저장되지는 않습니다.

lb rt, offset(rs)
// 최상위 비트가 부호비트로 확장되어 32비트로 변환된 후 rt에 저장된다

lh rt, offset(rs)
// 최상위 비트가 부호비트로 확장되어 32비트로 변환된 후 rt에 저장된다 

lbu rt, offset(rs)
// 나머지는 0으로 채워 32비트로 변환한 후 rt에 저장한다

lhu rt, offset(rs)
// 나머지는 0으로 채워 32비트로 변환한 후 rt에 저장한다

sb rt, offset(rs) 
//최하위 8비트를 rs가 가리키는 주소에서 offset 만큼 떨어진 위치에 저장한다
// 이때, 다른 바이트는 영향을 받지 않는다

sh rt, offset(rs)
//최하위 16비트를 rs가 가리키는 주소에서 offset 만큼 떨어진 위치에 저장한다
// 이때, 다른 바이트는 영향을 받지 않는다

void strcpy(char x[], char y[]){
	int i; i = 0;
    while((x[i]=y[i]) != '\0') i += 1;
}
// Address of x, y in $a0, $a1
// i in $s0




strcpy:
	addi $sp, $sp, -4
    sw $s0, 0($sp)
    addi $s0, $zero, $zero
L1: add $t1, $a1, $s0
	lbu $t2, 0($t1)
    add $t3, $a0, $s0
    sb $t2, 0($t3)
    beq $t2, $zero, L2
	addi $s0, $s0, 1
    j L1 
L2: lw $s0, 0($sp)
	addi $sp, $sp, 4
   	jr $ra

32비트 상수를 처리하는 방법

일반적으로 사용하는 상수는 작기 때문에 16비트 즉시값이 충분하고, I-format 명령어를 사용하여 처리

32비트 상수가 필요한 경우에는 다음과 같은 방법을 사용

lui (load upper immediate)

lui rt, constant

- 16비트 상수를 rt 레지스터의 상위 16비트에 복사하고 하위 16비트는 0으로 초기화

- 예를 들어, lui $t0, 0x1234를 실행하면 $t0는 0x12340000

Combining with ori

상위 16비트가 로드된 후, 하위 16비트를 설정하기 위해 ori 명령어를 사용

ori rt, rt, immediate

- lui로 상위 16비트를 설정한 후, ori를 사용하여 하위 16비트를 설정

- 예를 들어, 상위 16비트가 0x1234인 $t0에 ori $t0, $t0, 0x5678를 실행하면 $t0는 0x12345678

1. 16비트 즉시값의 제한

addi 명령어의 즉시값 크기: addi 명령어는 -32768에서 32767까지의 범위 내에서만 16비트 즉시값을 사용할 수 있다. 이는 32비트 상수를 처리하기에는 매우 제한적 예를 들어, 0x8000(32768) 이상의 값은 addi로 직접 표현할 수 없다

2. 상위 및 하위 비트 설정

lui 사용의 필요성: 32비트 상수를 설정하려면 먼저 lui 명령어를 사용하여 상위 16비트를 로드한 다음, ori 명령어를 사용하여 하위 16비트를 설정해야함. 이 방법은 32비트 상수를 안전하게 설정할 수 있는 유일한 방법

3. 이전 레지스터 값 손실

OR 연산의 사용: ori 명령어는 기존의 상위 16비트 값을 유지한 채 하위 16비트만 변경할 수 있다. 만약 잘못된 명령어를 사용하면 기존의 데이터가 손실될 수 있다

4. 명령어의 조합

순서의 중요성: 반드시 lui 명령어로 상위 16비트를 설정한 후 ori를 사용하여 하위 16비트를 설정해야 한다. 이 순서를 지키지 않으면, 하위 비트가 올바르게 설정되지 않아 원하는 값이 저장되지 않을 수 있다

Formats

$t0 - $t7 : reg's 8-15

$t8 - $t9 : reg's 24-25

$s0 - $s7 : reg's 16-23

1. R-format

op(6) + rs(5) + rt(5) + rd(5) + shamt(5) + funct(6)

• op : operation code (opcode) – always 0 in R-format because the operation is determined by ‘funct’.

• 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)

R-format 명령어에서 op 필드가 항상 0인 이유는 R-format 명령어임을 식별하기 위한 것이며, 구체적인 연산은 funct 필드를 통해 지정된다

add $t0, $s1, $s2

000000(0) 10001(17) 10010(18) 01000(8) 00000(0) 100000(32)

=> 00000010001100100100000000100000

주요 R-포맷 명령어 : add, sub, and, or, xor, sll, srl, slt, jr

2. I-format

op(6) + rs(5) + rt(5) + constant or address(16)

• rt : destination or source register number

• constant : -2 15 to +215 -1

• address : offset added to base address in rs (e.g., lw, sw)

주요 I-포맷 명령어 : addi, lw, sw, beq, bne, slti(즉시 값과 레지스터 값 비교), andi, ori, lui(Load Upper Immediate)

A[300] = h + A[300]
# A의 base는 $t1, h는 $s2

lw $t0, 1200($t1)
add $t0, $s2, $t0
sw $t0, 1200($t1)

35(lw) 9($t1) 8($t0) 1200
0 18($s2) 8($t0) 8($t0) 0 32(add)
43(sw) 9($t1) 8($t0) 1200

Branch Addressing

분기 명령어는 i-format 형식으로 되어 있다

대부분의 분기 대상은 근처에 있다

PC-relative addressing : 분기할 주소는 현재 프로그램 카운터 값을 기준으로 계산된다

Target Address=(PC+4)+(offset×4)

분기 범위 : MIPS 분기 명령어는 ±215 워드(±215 명령어 = ±217 바이트) 범위 내에서 분기가 가능하다

Jump Addressing

점프 명령어는 텍스트 세그먼트의 어떤 주로로도 점프할 수 있다. (현재 PC에서 멀리 떨어져 있을 수 있다)

점프 명령어는 j-format으로 인코딩되어 있다,

(Pseudo) Direct jump addressing

3. J-foramt : j and jal

op(6) + constant or address(26)

여기서 주소는 절대 주소로 인코딩된다.

Target Address=address×4

점프 가능 범위 : 점프 명령어는 2^26 워드(2^28 바이트) 범위 내의 주소로 점프할 수 있다.

분기 명령어는 16비트 오프셋을 사용하므로 , 거리제한이 있고 이 한계를 넘는 경우에

어셈블러는 코드를 재구성하여 점프를 구현한다

beq $s0, $s1, L1   


beq $s0, $s1, L2  
L2: j L1

* jr 명령어는 R-format으로 되어 있다

Immediate

상수 값을 직접 사용

addi $t0, $t1, 5

Register

레지스터의 값을 직접 사용

add $t0, $t1, $t2

Base

레지스터의 주소와 오프셋을 사용

lw $t0, 4($t1)

PC-Relative

현재 PC와 오프셋을 사용

beq $s0, $s1, label

Pseudodirect

26비트 절대 주소를 사용

j label

Non-Leaf-Procedure

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



Fact:
addi $sp, $sp, -8
sw $ra 4($sp)
sw $a0 0($sp)
slti $t0, $a0, 1
beq $t0, $zero, L1
addi $v0, $zero, 1
addi $sp, $sp, 8
jr $ra
L1:
addi $a0, $a0, -1
jal fact
lw $a0, 0(sp)
lw $ra, 4(sp)
addi $sp, sp, 8
mul $v0, $v0, $a0
jr $ra

$sp (Stack Pointer)

$fp (Frame Pointer)

티스토리툴바