[컴퓨터구조]-MIPS(2)

오늘은 MIPS의 format, Operations,

그리고 몇 가지 Instruction(명령어)과 Procedure Calling(PC)에 대해서 정리해보려고 한다.

​

<Representing Instructions>

MIPS에서는 Instruction들은 이진수로 인코딩돼있다.

저번에 레지스터는 번호마다 고유의 역할이 정해져 있다는 것을 공부했다.

그중 거의 항상 사용되는 saved 와 temporary register은 번호를 외워두는 것이 편하다.

그리고 명령어의 번호 또한 외워야 이진수 format으로 변경할 수 있다.

register number

instruction op, shamt, funct, address

크게 R,I,J format으로 구분할 수 있다.

​

• R-format

Arithmetic Instruction (산술연산)에서 사용된다.

opcode는 모두 0이고 funct 는 add와 sub가 각각 32, 34다.

저번에 정리했던 add, sub에서는 피연산자 register 을 3개 사용한다.

rs와 rt를 연산하여 결과값을 rd에 넣는 방식이다.

R-format 의 구조

예를 들어

add $t0, $s1, $s2 를 R-format이진수로 변환해보자.

2진수를 16진수로 바꾸는 법은 여러 번 해서 따로 정리는 안 해도 될 것 같다.

​

• I-format

I-format은 addi 와 load/store 연산에 활용된다.

addi는 피연산자 중 하나가 상수이므로 피연산자 register이 2개이고

load/store 연산은 피연산자 대신 offset이 필요하다.

addi, load, store 각각 opcode 는 8, 35,43이다.

Design Principle #4 : Good design demands good compromises

(어느 정도의 절충은 좋은 디자인 방법이다)

​

MIPS 에서는 register 의 format에 상관없이 32 bit을 사용한다.

32 bit를 사용한다는 점은 통일시키자는 거다.

그래서 필요하지 않은 피연산자를 빼고 필요한 constant나 address를 넣는다.

여기서 constant는 16 bit를 사용할 수 있으므로 -2^15~2^15-1까지 표현 가능하다.

I-format의 구조

예를 들어 A[300] = h + A[300] 은 다음과 같다.($t1: A의 base address, $s2: h)

​

lw $t0, 1200($t1)

add $t0, $s2, $t0

sw $t0, 1200($t1)

op	rs	rt	rd	addr/shamt	funct
35	9	8	1200
0	18	8	8	0	32
43	9	8	1200

​

• J-format

​

어느 주소로 무조건 jump하라는 명령어에서는 J-format을 사용한다.

J-format 의 구조

​

이렇게 이진수로 변환함으로써 같은 MIPS 체계를 사용하는 컴퓨터 간 이식이 가능하다.

(binary compatibility: 이진이식성)

​

<Logic Operations>

비트단위의 조작을 위한 명령어다.

Operation	C	JAVA	MIPS
Bitwise And	&	&	and, andi
Bitwise Or	|	|	or, ori
Bitwise Not	~	~	nor

<Shift Opertions>

=> 이진 코드에서 "shamt"와 관련 있는 부분이다.

실제로 shamt에는 얼마나 shift를 해야 하는지에 대한 정보를 담는다.

shift 연산을 하면 multiply와 division 연산을 처리할 수 있다.

shift하고 비게 되는 칸은 0으로 채운다.

Operation	C	JAVA	MIPS
Shift Left	<<	<<	sll
Shift Right	>>	>>>	srl

• shift left logical

=> 왼쪽으로 한 칸씩 이동 -> 2배 연산

=> rs 자리는 비운다. rt가 중간에 비게 되는 경우를 막기 위해 rs 대신 rt에 들어간다.

예를 들어

sll $t2, $s0, 4 는

• shift right logial

=> 오른쪽으로 한 칸씩 이동 -> 2로 나누는 연산

​

<AND Operation>

=> mask bits 하기 위해서 사용(비트 제외 연산)

<OR Operation>

=> include bits 하기 위해서 사용(비트 포함 연산)

<NOT Operation>

=> invert bits 하기 위해서 사용

=> NOR 이라는 명령어로 사용(register 개수 맞추기 위해)

a NOR b = NOT (a OR b)

​

nor $t0, $t1, $zero 는

$t1 과 $zero 의 OR 연산을 먼저 한 다음

그 결과값을 NOT 하여 $t0 에 넣는다.

<Conditional Operations>

=> 조건 분기 명령어

​

• Branch EQual

beq rs, rt, L1 => if(rs=rt) 이면 L1으로 분기해라

​

• Branch Not Equal

bne rs, rt, L1 => if(rs!=rt)이면 L1으로 분기해라

​

<Unconditional Operation>

• Jump

j L1 => 무조건 L1으로 분기해라

​

<Compiling If Statements>

​

다음 C 코드를

​

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

else f = g - h;

​

f,g,h,i,j 가 각각 $s0~$s4에 있다고 생각하고 MIPS 코드로 변경해보자.

​

bne $s3, $s4, Else

add $s0, $s1, $s2

j Exit

sub $s0, $s1, $s2 : Else

...... : Exit

​

<Compiling Loop Statements>

​

다음 C 코드를

​

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

​

i,k,save 배열의 base address가 각각 $s3, $s5, $s6에 있다고 생각하고 MIPS 코드로 변경해보자.

​

sll $t1, $s3, 2 : Loop ...(1)

add $t1, $s6, $t1 ...(2)

lw $t0, 0($t1) ...(3)

bne $t1, $s5, Exit

addi $s3, $s3, 1

j Loop

.... : Exit

​

(1) 정수는 4byte를 사용하므로 배열을 생성할 때에는 i=i+4 해주어야 한다.

(2) 배열을 만들고

(3) 배열이기 때문에 load word 꼭 해줘야 한다

​

<Basic Blocks>

• 맨 마지막을 제외하고 어딘가로 branch 하여 갔다 오는 것 안됨(no embedded branches)
• 맨 처음을 제외하고 다른쪽에서 끼어들어오면 안됨(no branch targets)

​

<More Conditional Operations>

• Set on Less Than (slt)

slt rd, rs, rt => if(rs<rt)이면 rd=1, 아니면 rd=0

​

• Set on Less Than Immediate(slti)

slti rd, rs, constant => if(rs<constant)이면 rd=1, 아니면 rd=0

​

bne, beq는 앞에꺼 두개를, slt, slti는 뒤에꺼 두개를 비교한다는 점이 다르다.

​

하지만 unsigned 를 다룰 때에는 다음과 같은 명령어 쓴다.

• Set on Less Than Unsigned(sltu)
• Set on Less Than Unsigned Immediate(sltui)

​

예를 들어

$s0 = 1111 1111 1111 1111 1111 1111 1111 1111

$s1 = 0000 0000 0000 0000 0000 0000 0000 0001

일 때 signed 에서는 $s0에서 overflow가 일어나 $s0 = -1, $s1 = 1

unsigned 에서는 $s0 = max value, $s1 = 1이다. 따라서

​

slt $t0, $s0, $s1 => $t0 = 1

sltu $t0, $s0, $s1 => $t0 = 0

이렇게 다른 결과가 나올 수 있음에 주의해야 한다.

​

<Procedure Calling : jump and link(jal)/jump return(jr)>

• caller : 호출하는 쪽
• callee : 호출되는 쪽

​

*단계*

1. register들에 parameter를 지정
2. 제어권을 호출한 명령어(PC)의 다음 명령어(PC+4)에게 넘김
3. register spilling(callee가 caller을 위해 원래 사용하고 있던 register에 있는 값 memory에 저장해둠)
4. procedure operations 수행
5. result register($v0, $v1)에 결과값 저장
6. 호출된 쪽으로 복귀(PC+4) => jr $ra

​

이때 레지스터가 구체적으로 어떻게 사용되는지를 살펴보면

$a0~$a3 : arguments

$v0, $v1 : result values => caller 가 callee를 위해 결과값 저장하는 자리 마련해둠

$t0~$t9 : temporaries => callee에 의해 overwritten될 수 있음

(basic block처럼 한 번 호출되고 끝나는 경우)

$s0~$s7 : saved => callee가 register spilling을 해야 함 => return할 때 restore까지 해야 함

(재귀함수처럼 프로시저 안에서 다른 프로시저 호출할 경우)

$gp : global pointer => 전역 변수 주소 저장

$sp : stack pointer => stack의 top 부분을 가리키는 포인터

$fp : frame pointer => stack의 처음부분을 가리키는 포인터

$ra : return address => 호출될 때 끝나고 돌아갈 주소를 저장

​

컴퓨터는 이런 식으로 함수 이름(label)마다 어디로 jump할건지(target address) 대응시켜 놓는다.

• Procedure Call(jal)

jal에서 jump는 target address로 옮겨가는 것, link는 다음 명령어 주소(PC+4)를 $ra에 넣는 것을 말한다.

jal ProcedureLabel1 => $ra=PC+4 그리고 ProcedureLabel1의 주소로 jump

​

• Procedure Return(jr)

jr은 jump register

program counter로 $ra 값 복사 => case/switch 문에도 사용 가능

​

<예제-Leaf Procedure>

Leaf-Procedure은 procedure 안에서 다른 procedure을 호출하지 않는 procedure다.

다음 C코드를

​

int leaf_example(int g, h, i, j) {

int f;

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

return f;

}

​

g,h,i,j가 각각 $a0~$a3 에, f가 $s0에 있다고 생각하고 MIPS 코드로 변경해보자.

​

$s0은 꼭 save 해놨다가 result까지 저장해두고 다시 restore하는 작업을 거쳐야 한다.

​

<예제-Non-Leaf Procedure>

​

Non-Leaf Procedure은 procedure 안에서 다른 procedure를 호출하는 procedure다.

Leaf Procedure에서는 saved register 만 save/restore 했다면

여기서는 return address($ra)와 호출된 후에도 필요한 argument와 temporary register 또한

save/restore 해줘야 한다.

​

다음 c코드를

​

int fact (int n) {

if(n < 1) return 1;

else return n * fact(n-1);

}

​

n은 $a0에, result는 $v0에 저장된다고 생각하고 MIPS 코드로 변경해보자.

​

​

return 할 때 상수가 아닌 변수나 함수이름이 있으면 lw 한다 !!

(return 1 => lw 안 함 / return f, return n*fact(n-1) => lw 함)

​

memory layout은 다음과 같다.

stack은 위에서 아래로 쌓여간다.

그래서 스택의 처음인 $fp는 고정돼있고 top 을 가리키는 $sp는 아래로 쌓여갈수록 내려간다.