[CS311] 3. MIPS 명령어 집합 구조

KAIST CS311 전산기조직 (Spring 2023) 교재: Computer Organization and Design: The Hardware/Software Interface (Patterson & Hennessy, MIPS Edition)

ISA (Instruction Set Architecture)

ISA는 **프로그래머와 하드웨어 설계자 사이의 계약(Contract)**이다. 양쪽 관점에서 ISA의 의미가 다르다:

프로그래머 관점: ISA는 프로그램이 어떻게 실행되는지를 나타내는 모델이다.
하드웨어 설계자 관점: ISA는 프로그램을 올바르게 실행하기 위한 형식적 정의(Formal Definition)이다.

ISA가 동일하다면, 하드웨어 구현이 달라도 같은 프로그램을 실행할 수 있다. 이것이 바로 소프트웨어 호환성(Software Compatibility)의 핵심이다.

ISA가 명시하는 것

ISA 명세(Specification)는 다음 세 가지를 정의한다:

Architecturally Visible States: 프로그래머가 볼 수 있는 모든 상태 (레지스터, 메모리, PC 등)
Instruction Format & Behavior: 각 명령어의 인코딩 형식과 동작 방식
Memory Model: 메모리 접근 방식과 주소 체계

핵심 원칙

명령어는 숫자로 표현된다: 데이터와 명령어의 구별이 없다 — 둘 다 이진수일 뿐이다.
Stored-Program 개념: 프로그램도 메모리에 숫자로 저장된다. 이를 통해 프로그램을 데이터처럼 읽고 수정할 수 있다.

Operand 개수에 따른 분류

ISA는 명령어가 명시적으로 취하는 피연산자(Operand) 수에 따라 분류할 수 있다:

유형	설명	예시
3-operand	목적지 + 소스 2개	`add $t0, $t1, $t2`
2-operand	목적지가 소스를 겸함	x86의 `add eax, ebx`
1-operand	Accumulator 기반	Accumulator ISA
0-operand	Stack 기반	Stack ISA (JVM 등)

MIPS는 3-operand ISA로, 명령어에서 목적지와 두 개의 소스를 명시적으로 지정한다.

MIPS-32 ISA

MIPS(Microprocessor without Interlocked Pipelined Stages)는 대표적인 RISC(Reduced Instruction Set Computer) 아키텍처이다. 단순하고 규칙적인 설계 덕분에 컴퓨터 구조 교육에 널리 사용된다.

명령어 분류 (Instruction Categories)

MIPS 명령어는 다음 6가지 범주로 나뉜다:

┌────────────────┬────────────────┬────────────────┐
│ Computational  │  Load / Store  │ Jump & Branch  │
├────────────────┼────────────────┼────────────────┤
│ Floating Point │ Memory Mgmt.   │    Special     │
└────────────────┴────────────────┴────────────────┘

명령어 형식 (Instruction Formats)

모든 MIPS 명령어는 32비트(4바이트) 고정 길이를 가진다. 세 가지 형식이 존재한다:

R-format (Register):
┌──────┬──────┬──────┬──────┬───────┬───────┐
│  op  │  rs  │  rt  │  rd  │ shamt │ funct │
│ 6bit │ 5bit │ 5bit │ 5bit │ 5bit  │ 6bit  │
└──────┴──────┴──────┴──────┴───────┴───────┘
  연산 종류  소스1  소스2  목적지  시프트량  기능 코드

I-format (Immediate):
┌──────┬──────┬──────┬─────────────────────┐
│  op  │  rs  │  rt  │     immediate       │
│ 6bit │ 5bit │ 5bit │       16bit         │
└──────┴──────┴──────┴─────────────────────┘
  연산 종류  소스   목적지    즉시값 / 주소 오프셋

J-format (Jump):
┌──────┬────────────────────────────────────┐
│  op  │           jump target              │
│ 6bit │              26bit                 │
└──────┴────────────────────────────────────┘
  연산 종류         점프 목적지 주소

R-format: add, sub, and, or, slt, sll 등 레지스터 간 연산
I-format: addi, lw, sw, beq, bne 등 즉시값이나 메모리 접근 포함
J-format: j, jal 등 무조건 점프

레지스터 (Register Operands)

MIPS에는 32개의 32비트 범용 레지스터가 있다. 레지스터 번호를 지정하려면 5비트가 필요하다 (2^5 = 32).

레지스터 파일(Register File)은 다음과 같은 포트를 가진다:

              Register File (32 x 32-bit)
         ┌─────────────────────────────────┐
Read 1 ──┤ Read Reg 1 (5-bit)             ├── Read Data 1 (32-bit)
Read 2 ──┤ Read Reg 2 (5-bit)             ├── Read Data 2 (32-bit)
Write  ──┤ Write Reg  (5-bit)             │
         │ Write Data (32-bit)             │
         │ Write Control                   │
         └─────────────────────────────────┘

2개의 Read Port: 한 클럭 사이클에 두 레지스터를 동시에 읽을 수 있다.
1개의 Write Port: 한 클럭 사이클에 하나의 레지스터에 기록할 수 있다.

MIPS 레지스터 규약

이름	번호	용도	Callee-saved?
`$zero`	0	상수 0 (변경 불가)	N/A
`$at`	1	어셈블러 임시값	No
`$v0-$v1`	2-3	함수 반환값 / 수식 결과	No
`$a0-$a3`	4-7	함수 인자 (Arguments)	No
`$t0-$t7`	8-15	임시값 (Temporaries)	No
`$s0-$s7`	16-23	저장값 (Saved Temporaries)	Yes
`$t8-$t9`	24-25	임시값 (Temporaries)	No
`$k0-$k1`	26-27	OS 커널 전용	No
`$gp`	28	Global Pointer	Yes
`$sp`	29	Stack Pointer	Yes
`$fp`	30	Frame Pointer	Yes
`$ra`	31	Return Address	Yes

Caller-saved ($t0-$t9, $a0-$a3, $v0-$v1): 호출자(Caller)가 보존 책임을 진다.
Callee-saved ($s0-$s7, $sp, $fp, $ra): 피호출자(Callee)가 보존 책임을 진다.

Register vs Memory

레지스터와 메모리의 관계를 이해하는 것이 중요하다:

레지스터 접근이 메모리 접근보다 훨씬 빠르다.
메모리에 있는 데이터를 사용하려면 반드시 Load/Store를 거쳐야 한다.
컴파일러는 변수를 최대한 레지스터에 할당한다 (Register Optimization).
자주 사용되지 않는 변수만 메모리로 spill한다.

Memory Operands

Main Memory에는 배열(Array), 구조체(Structure), 동적 데이터(Dynamic Data) 등 **복합 데이터(Composite Data)**가 저장된다.
산술 연산을 수행하려면 Load와 Store를 통해 레지스터를 거쳐야 한다.
Byte Addressed: 각 메모리 주소는 1바이트를 가리킨다.
Word Alignment: Word는 4바이트이므로 Word 주소는 4의 배수이다.
Big Endian: MIPS는 MSB를 가장 낮은 주소에 저장한다.

예: g = A[8]  →  lw $t0, 32($s3)

  배열 A는 4-byte 크기의 데이터를 담으므로,
  8번째 index를 참조하려면 8 × 4 = 32 byte의 offset이 필요하다.

Immediate Operands

명령어의 소스(Source)로서 **즉시값(Immediate)**을 직접 사용할 수 있다. 메모리에서 상수를 로드하는 것보다 빠르다.

addi $s3, $s3, 4    # $s3 = $s3 + 4

설계 원칙: Make the Common Case Fast

Subtract Immediate는 없다: 뺄셈이 필요하면 음수 상수를 사용한다. (addi $s3, $s3, -4)
$zero 레지스터: 항상 0을 담고 있어 변경할 수 없다. 자주 사용되는 0이라는 상수를 레지스터로 빠르게 접근할 수 있다.

move $t0, $s0    →   add $t0, $s0, $zero   # 레지스터 복사
li   $t0, 0      →   add $t0, $zero, $zero  # 0으로 초기화

Signed vs Unsigned, Sign Extension

데이터의 부호 처리

data 또는 immediate: signed일 수도 있고 unsigned일 수도 있다.
비트 수가 다른 값을 저장할 때는 **부호 확장(Sign Extension)**이 필요하다.

Sign Extension이 적용되는 경우

상황	설명
Arithmetic Operation	16-bit immediate → 32-bit 레지스터
Branch Instruction	16-bit immediate → 32-bit PC에 더할 때
`lb` / `lh`	바이트/하프워드 데이터 → 32-bit 레지스터

lbu, lhu는 Zero Extension을 수행한다 (unsigned 버전).

레지스터에서의 부호

레지스터에 저장된 ???-bit data: signed 또는 unsigned
메모리에 저장된 데이터: signed 또는 unsigned
I-format의 16-bit immediate: signed 또는 unsigned

MIPS 핵심 명령어 (Core Instructions)

1. 산술 연산 (Arithmetic: Add & Sub)

명령어	형식	설명
`add rd, rs, rt`	R	부호 있는 덧셈 (overflow 시 예외)
`addu rd, rs, rt`	R	부호 없는 덧셈 (overflow 무시)
`sub rd, rs, rt`	R	부호 있는 뺄셈
`subu rd, rs, rt`	R	부호 없는 뺄셈
`addi rt, rs, imm`	I	부호 있는 즉시값 덧셈
`addiu rt, rs, imm`	I	부호 없는 즉시값 덧셈

결과값을 Sign으로 볼 것인가? / Source를 Sign으로 볼 것인가? 에 따라 사용하는 명령어가 달라진다.
add에 음수 immediate를 사용하면 되므로, subtract immediate 명령어는 따로 없다 — I-format을 아낄 수 있다.

2. 비트 연산 (Bitwise / Logical)

명령어	형식	설명
`and rd, rs, rt`	R	비트 AND
`andi rt, rs, imm`	I	즉시값 AND (Zero Extension)
`or rd, rs, rt`	R	비트 OR
`ori rt, rs, imm`	I	즉시값 OR (Zero Extension)
`nor rd, rs, rt`	R	비트 NOR
`sll rd, rt, shamt`	R	왼쪽 논리 시프트
`srl rd, rt, shamt`	R	오른쪽 논리 시프트 (0 채움)

NOT 연산은 nor로 대체: nor $t0, $t1, $zero → $t0 = ~$t1
Logical Shift: 빈 자리를 0으로 채운다.
sll/srl에서는 rs = 0이다 (shamt 필드를 사용).
Bitwise Operation의 immediate 버전은 Zero Extension을 적용한다.

3. 분기와 점프 (Branch & Jump)

명령어	형식	주소 계산 방식
`beq rs, rt, label`	I	PC-relative: PC+4 + Sign_Extend(imm) « 2
`bne rs, rt, label`	I	PC-relative: PC+4 + Sign_Extend(imm) « 2
`j target`	J	Absolute: {PC+4[31:28], target, 2’b00}
`jal target`	J	Absolute: $ra = PC+4, then jump
`jr rs`	R	Register: PC = rs

Branch (beq/bne): PC-relative 주소 지정. 현재 PC+4에 부호 확장된 offset × 4를 더한다.
Jump (j/jal): PC 상위 4비트를 유지하고 나머지 28비트를 target × 4로 채운다.
jr: 레지스터에 저장된 주소로 점프한다. Switch-Case 구현이나 함수 반환에 사용한다.
PC는 항상 4의 배수이므로 하위 2비트를 인코딩할 필요가 없어 “공짜 비트“를 얻는다.

4. 로드와 스토어 (Load / Store)

명령어	형식	설명
`lw rt, imm(rs)`	I	Word(4B) 로드
`lhu rt, imm(rs)`	I	Half-word(2B) 로드, Zero Extension
`lbu rt, imm(rs)`	I	Byte(1B) 로드, Zero Extension
`lb rt, imm(rs)`	I	Byte(1B) 로드, Sign Extension
`ll rt, imm(rs)`	I	Load Linked (atomic 연산의 전반부)
`lui rt, imm`	I	상위 16비트에 즉시값 로드
`sw rt, imm(rs)`	I	Word(4B) 스토어
`sh rt, imm(rs)`	I	Half-word(2B) 스토어
`sb rt, imm(rs)`	I	Byte(1B) 스토어
`sc rt, imm(rs)`	I	Store Conditional (atomic 연산의 후반부)

모든 Load/Store는 I-format이다. Address mode 계산을 위해 immediate(offset)이 필요하기 때문이다.
주소 계산: address = rs + Sign_Extend(imm)
Load는 address 계산 후 메모리에서 레지스터로 값을 가져온다.
Store는 address 계산 후 레지스터의 값을 메모리에 기록한다.
Store에는 “공짜 비트“가 없다 — Access하는 Address가 4의 배수여야 할 필요가 없으므로.

5. 비교 (Set Less Than)

명령어	형식	설명
`slt rd, rs, rt`	R	rs < rt (signed)이면 rd = 1, 아니면 0
`sltu rd, rs, rt`	R	rs < rt (unsigned)이면 rd = 1, 아니면 0
`slti rt, rs, imm`	I	rs < imm (signed)이면 rt = 1, 아니면 0
`sltiu rt, rs, imm`	I	rs < imm (unsigned)이면 rt = 1, 아니면 0

비교를 Sign으로 할 것인지, Source 중 immediate 여부에 따라 명령어가 나뉜다.
두 값을 비교한 후 레지스터를 1 또는 0으로 설정한다.

프로시저 호출 (Procedure Calls)

프로시저(함수) 호출은 프로그램의 모듈화와 코드 재사용의 기본이다. MIPS에서 프로시저 호출은 다음과 같이 동작한다.

호출과 복귀

Caller                              Callee
  │                                   │
  │  jal ProcedureLabel               │
  │──────────────────────────────────►│
  │  ($ra = PC+4, PC = Label)         │
  │                                   │
  │                                   │  ... 함수 본문 실행 ...
  │                                   │
  │  jr $ra                           │
  │◄──────────────────────────────────│
  │  (PC = $ra, 즉 원래 PC+4)          │

jal (Jump and Link): 현재 PC+4를 $ra에 저장하고, 프로시저 주소로 점프한다.
jr $ra (Jump Register): $ra에 저장된 주소(호출자의 다음 명령어)로 복귀한다.

레지스터 Spilling on Stack

프로시저가 레지스터를 사용하기 전에, 기존 값을 보존해야 할 수 있다. 이를 레지스터 spilling이라 하며, 스택을 사용한다.

호출 전 스택:                호출 후 스택 (callee가 $s0, $s1, $ra를 spill):

   높은 주소                    높은 주소
  ┌──────────┐                ┌──────────┐
  │   ...    │                │   ...    │
  ├──────────┤ ◄─ $sp         ├──────────┤
  │          │                │ saved $s0│
  │          │                ├──────────┤
  │          │                │ saved $s1│
  │          │                ├──────────┤
  │          │                │ saved $ra│
  │          │                ├──────────┤ ◄─ $sp (새 위치)
   낮은 주소                    낮은 주소

Callee-saved 레지스터 ($s0-$s7, $ra): 피호출자(Callee)가 사용 전에 스택에 저장하고, 복귀 전에 복원한다.
Caller-saved 레지스터 ($t0-$t9, $a0-$a3): 호출자(Caller)가 호출 전에 스택에 저장하고, 호출 후 복원한다.

재귀 함수 (Recursive Procedure)

프로시저는 caller인 동시에 callee일 수 있다. 재귀 함수가 대표적인 예이다:

fact(n):
  if (n < 1) return 1;
  return n * fact(n-1);

재귀 호출 시 $ra와 $a0 등이 덮어씌워지므로, 호출 전에 반드시 스택에 저장해야 한다. 이 때문에 callee-saved/caller-saved 규약이 중요하다.

메모리 레이아웃 (Memory Layout)

MIPS 프로그램이 실행될 때의 메모리 구조는 다음과 같다:

  주소 (hex)
  0x7FFF_FFFC ┌──────────────────────┐ ◄─ $sp (초기값)
              │                      │
              │       Stack          │    ↓ 아래로 자람
              │   (Local Variables)  │
              │                      │
              ├──────────────────────┤
              │         ↓            │
              │                      │
              │         ↑            │
              ├──────────────────────┤
              │   Dynamic Data       │    ↑ 위로 자람
              │      (Heap)          │
              │  malloc() / new      │
  0x1000_8000 ├──────────────────────┤ ◄─ $gp
  0x1000_0000 ├──────────────────────┤
              │    Static Data       │
              │ (Global Variables)   │
  0x0040_0000 ├──────────────────────┤
              │       Text           │
              │   (Program Code)     │
  0x0000_0000 ├──────────────────────┤
              │     Reserved         │
              └──────────────────────┘

각 영역의 역할:

영역	시작 주소	설명
Reserved	`0x0000_0000`	OS 전용, 사용자 접근 불가
Text	`0x0040_0000`	프로그램 코드(명령어)가 저장되는 영역
Static Data	`0x1000_0000`	프로그램 실행 동안 지속적으로 남아있는 전역/정적 데이터
Dynamic Data (Heap)	Static 위	`malloc()` / `new`로 할당되는 동적 메모리, 위로 자람
Stack	`0x7FFF_FFFC`	지역 변수와 함수 호출 정보가 저장, 아래로 자람

$gp (Global Pointer) = 0x1000_8000: Static Data 영역의 중간을 가리켜서, 16-bit offset으로 0x1000_0000 ~ 0x1000_FFFF 범위를 접근할 수 있다.
$sp (Stack Pointer): 스택의 현재 top을 가리킨다. 함수 호출 시 감소하고, 복귀 시 증가한다.
Heap과 Stack은 서로 반대 방향으로 자란다: Heap은 위로, Stack은 아래로 자라면서 사이의 빈 공간을 공유한다.

정리

ISA는 소프트웨어와 하드웨어의 경계를 정의하는 핵심 추상화 계층이다. MIPS-32 ISA의 주요 특징을 요약하면:

┌─────────────────────────────────────────────────────────┐
│                    MIPS-32 요약                          │
├─────────────────────────────────────────────────────────┤
│  명령어 길이:  고정 32비트                                │
│  레지스터:     32 × 32-bit 범용 레지스터                   │
│  명령어 형식:  R-format / I-format / J-format            │
│  주소 지정:    Register, Immediate, PC-relative, Pseudo  │
│  메모리 접근:  Load/Store 아키텍처 (레지스터 경유 필수)      │
│  바이트 순서:  Big Endian                                │
│  정렬:        Word는 4바이트 정렬 필수                     │
└─────────────────────────────────────────────────────────┘

단순성(Simplicity): 고정 길이 명령어와 규칙적인 형식으로 하드웨어 설계가 단순해진다.
Make the Common Case Fast: $zero 레지스터, immediate operand 등으로 자주 사용되는 연산을 빠르게 처리한다.
Good Design Demands Good Compromises: R/I/J 세 가지 형식으로 다양한 명령어를 32비트 안에 효율적으로 인코딩한다.

ISA (Instruction Set Architecture)#

ISA가 명시하는 것#

핵심 원칙#

Operand 개수에 따른 분류#

MIPS-32 ISA#

명령어 분류 (Instruction Categories)#

명령어 형식 (Instruction Formats)#

레지스터 (Register Operands)#

MIPS 레지스터 규약#

Register vs Memory#

Memory Operands#

Immediate Operands#

설계 원칙: Make the Common Case Fast#

Signed vs Unsigned, Sign Extension#

데이터의 부호 처리#

Sign Extension이 적용되는 경우#

레지스터에서의 부호#

MIPS 핵심 명령어 (Core Instructions)#

1. 산술 연산 (Arithmetic: Add & Sub)#

2. 비트 연산 (Bitwise / Logical)#

3. 분기와 점프 (Branch & Jump)#

4. 로드와 스토어 (Load / Store)#

5. 비교 (Set Less Than)#

프로시저 호출 (Procedure Calls)#

호출과 복귀#

레지스터 Spilling on Stack#

재귀 함수 (Recursive Procedure)#

메모리 레이아웃 (Memory Layout)#

정리#