Ch2. Instructions

• 2단원은 컴퓨터가 **어떤 명령어 집합(ISA, Instruction Set Architecture)**을 가지는지, 그리고 고급언어로 쓴 프로그램이 어떻게 MIPS assembly와 machine code로 내려가는지를 설명하는 단원이다.

• 여기서 핵심은 단순히 MIPS 문법을 외우는 게 아니다. 이 단원은

  • 컴퓨터가 왜 이런 명령어 형태를 택했는지
  • register와 memory를 어떻게 구분해서 쓰는지
  • 조건문, 반복문, 함수 호출이 기계 수준에서 어떻게 구현되는지
  • instruction encoding이 왜 그런 비트 구조를 가지는지

  를 전체적으로 이해하게 하는 단원이다.

• 슬라이드도 초반에 instruction set을 “컴퓨터가 수행할 수 있는 명령들의 repertoire"라고 설명하고, MIPS를 예시 ISA로 사용한다고 소개한다.

The MIPS Instruction Set

• MIPS는 이 책 전체에서 예시로 쓰는 ISA다.
• 중요한 건 “MIPS 자체"보다도, MIPS가 현대적인 RISC 스타일 ISA의 전형적인 예시라는 점이다.
• 슬라이드는 MIPS가 단순하고 규칙적인 구조를 가지며, 이런 단순성이 구현을 쉽게 하고 성능과 비용 면에서 이점을 준다고 본다.
• 즉 2단원 내내 나오는 설계 철학은 대충 이런 흐름이다.
  • 규칙적이면 하드웨어가 단순해진다.
  • 하드웨어가 단순하면 빠르고 싸게 만들 수 있다.
  • 그래서 instruction form도 최대한 일정하게 맞춘다.

1. Arithmetic Operations

기본 산술 명령의 형태

• MIPS의 기본 산술 명령은 보통 세 개의 피연산자를 가진다.

add a, b, c

• 의미는 a = b + c 이다.
• 즉
  • 하나는 destination
  • 두 개는 source다.
• C 코드

a = b + c;
d = a - e;

• 는 MIPS에서

add a, b, c
sub d, a, e

• 처럼 내려간다.
• 이건 “연산 결과를 다시 어떤 operand 위치에 덮어쓰는가"를 헷갈리지 않게 해 준다.
• 슬라이드가 여기서 강조하는 설계 원칙이 Simplicity favors regularity 다. 즉 형식을 일정하게 맞추는 게 좋다는 뜻이다.

산술 예시 해석

• 예를 들어

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

• 를 바로 한 번에 계산할 수는 없으니, 임시값이 필요하다.

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

• 여기서 흐름은
  • $t0 = g + h
  • $t1 = i + j
  • f = $t0 - $t1
• 이다.
• 즉 assembly에서는 고급언어의 한 식이 여러 개의 단순한 instruction으로 쪼개져 내려온다.

2. Register Operands

왜 register를 쓰는가

• MIPS 산술 연산은 기본적으로 register operand를 사용한다.

• MIPS에는 32개의 32-bit register가 있고, 자주 접근하는 값은 memory보다 register에 두는 것이 훨씬 빠르다.

• 슬라이드는

  • $t0 ~ $t9 는 temporary
  • $s0 ~ $s7 는 saved variable

  로 소개한다.

• 여기서 또 나오는 설계 원칙이 Smaller is faster 다.

• register file은 작고 빠르지만, main memory는 크고 느리다.

• 그래서 compiler는 가능하면 변수를 register에 두고, 꼭 필요할 때만 memory에 spill한다.

자주 나오는 레지스터 감각

• t는 임시 계산용이라고 생각하면 편하다.
• s는 함수 호출 전후로 값이 유지되어야 하는 쪽이라고 생각하면 편하다.
• 이 감각은 뒤의 procedure calling에서 아주 중요해진다.

3. Memory Operands

register만으로는 부족한 이유

• 배열, 구조체, 동적 할당 데이터처럼 큰 데이터는 register에 다 넣을 수 없다.

• 그래서 실제 데이터는 main memory에 있고, 연산을 하려면

  • memory → register 로 가져오고(lw)
  • 계산한 뒤
  • register → memory 로 다시 저장(sw)

  해야 한다.

byte addressing과 alignment

• MIPS memory는 byte addressed다.
• 즉 주소 하나가 1 byte를 가리킨다.
• 32-bit word는 4 byte이므로, word를 읽는 주소는 보통 4의 배수여야 한다.
• 이것이 alignment다.

배열 예시

g = h + A[8];

• A의 base address가 $s3에 있고, h가 $s2, g가 $s1이라면

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

• 가 된다.

• 왜 32냐면

  • A[8]
  • word 배열
  • 한 원소가 4 byte

  이므로 8 × 4 = 32 byte offset이기 때문이다.

저장 예시

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

• 는

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

• 가 된다.
• A[12]의 offset은 12 × 4 = 48이다.
• 여기서 꼭 익숙해져야 하는 건 MIPS의 memory operand 형식이

offset(base)

• 라는 점이다. 즉 “주소 = base + offset"이다.

Registers vs. Memory

• register가 빠르기 때문에, memory에 있는 데이터를 직접 더하는 식의 instruction은 없다.

• 항상

  1. load
  2. register 연산
  3. store

  흐름으로 간다.

• 그래서 load/store architecture라는 말이 나온다.

4. Immediate Operands와 Constant Zero

immediate가 필요한 이유

• 상수는 매우 자주 나온다.
• 예를 들어 반복문 인덱스 증가:

addi $s3, $s3, 4

• 이런 경우 굳이 4를 memory에서 읽어올 필요가 없다.
• instruction 안에 상수를 바로 넣는 게 빠르다.
• 이것이 Make the common case fast라는 설계 원칙의 예다.

subtract immediate가 없는 이유

• MIPS에는 subi가 없다.
• 대신 음수 immediate를 쓰면 된다.

addi $s2, $s1, -1

$zero

• $zero 레지스터는 항상 0이다.
• 덮어쓸 수 없다.
• 예를 들어 register move를

add $t2, $s1, $zero

• 처럼 표현할 수 있다.
• 즉 실제 machine instruction 개수를 최소화하려는 식의 설계다.

5. Signed / Unsigned Numbers

unsigned integer

• n비트 unsigned는 0 \sim 2^n - 1 범위를 가진다.
• 32비트면 0 \sim 4{,}294{,}967{,}295 다.

2의 보수 signed integer

• signed integer는 two’s complement로 표현한다.
• n비트 signed 범위는 -2^{n-1} \sim 2^{n-1}-1 이다.
• 예를 들어 4비트면 -8 \sim 7 이다.

왜 2의 보수를 쓰는가

• 덧셈 회로 하나로 양수/음수 연산을 같이 처리하기 쉽기 때문이다.
• 음수는 “비트 반전 후 1 더하기"로 만들 수 있다.
• 예를 들어 +2를 음수화하면
  • 000...0010
  • 반전 → 111...1101
  • +1 → 111...1110
• 즉 -2가 된다.

sign bit와 sign extension

• 최상위 비트가 sign bit다.
  • 0이면 non-negative
  • 1이면 negative
• 더 작은 비트수 값을 더 큰 비트수로 확장할 때 signed 값은 sign extension을 해야 한다.
• 즉 맨 왼쪽 부호 비트를 복제해서 채운다.

예:

• 0000 0010 → 0000 0000 0000 0010
• 1111 1110 → 1111 1111 1111 1110
• addi, lb, lh, beq, bne 등에서 sign extension이 중요하다.

hex의 의미

• hex는 4비트씩 보기 위한 압축 표기다.
• machine code를 읽거나 instruction encoding을 볼 때 거의 필수다.
• 예를 들어 32비트는 hex 8자리로 깔끔하게 표현된다.

6. Representing Instructions

instruction도 결국 bit pattern이다

• MIPS instruction은 32-bit fixed length로 인코딩된다.
• 이게 중요하다.
• 길이가 일정하면 instruction fetch와 decode가 단순해진다.
• 다만 모든 instruction을 한 형식으로 담기 어렵기 때문에 몇 가지 형식이 있다.

R-format

• R-format은 register-register 연산용이다.

op | rs | rt | rd | shamt | funct

• rs, rt: source
• rd: destination
• shamt: shift amount
• funct: 세부 연산 종류
• 예를 들어

add $t0, $s1, $s2

• 는 op=0인 special 형태에서 funct=add로 구분된다.

I-format

• I-format은 immediate 연산과 load/store, branch에 쓰인다.

op | rs | rt | immediate/address

• addi, lw, sw, beq, bne 등이 여기에 속한다.
• immediate 필드는 16비트라서 모든 큰 상수를 한 번에 담을 수는 없다.
• 대신 흔한 경우를 빠르게 처리할 수 있다.
• 이게 슬라이드가 말하는 Good design demands good compromises다.

stored-program concept

• instruction도 data처럼 memory에 저장된다.
• 그래서 프로그램이 프로그램을 다룰 수도 있다.
• compiler, assembler, linker 같은 것들이 다 이 원리 위에서 돌아간다.

7. Logical Operations

왜 bitwise 연산이 필요한가

• 실제 시스템 프로그래밍에서는 비트 단위 조작이 자주 필요하다.
• 플래그 추출, 특정 비트 켜기/끄기, 마스크 생성 등에 쓰인다.

주요 명령

• sll: shift left logical
• srl: shift right logical
• and, andi
• or, ori
• nor

shift의 의미

• sll은 왼쪽으로 밀고 빈 자리를 0으로 채운다.
• unsigned 값 기준으로 2^i 배와 비슷하다.
• srl은 오른쪽으로 밀고 빈 자리를 0으로 채운다.
• unsigned 값 기준으로 2^i 로 나누는 효과와 비슷하다.

and / or / nor 감각

• and는 특정 비트만 남기고 나머지를 0으로 지울 때 쓴다. 즉 masking.
• or는 특정 비트를 1로 켜고 싶을 때 쓴다.
• nor는 NOT(OR)이라서 MIPS의 bitwise NOT 대체로 자주 나온다.

nor $t0, $t1, $zero

• 는 사실상 $t1의 비트를 뒤집는 효과다.

8. Conditional Operations

branch의 기본

• MIPS에서 조건 분기는 기본적으로
  • beq
  • bne
  • j
• 정도를 중심으로 배운다.

beq rs, rt, L1
bne rs, rt, L1
j   L1

• 즉 “같으면 가라”, “다르면 가라”, “무조건 가라"다.

if statement 번역

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

• 는 대충

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

• 가 된다.
• 중요한 점은 MIPS가 “if"를 직접 지원하는 게 아니라, 분기 + 순차 실행 흐름으로 조건문을 만든다는 것이다.

loop statement 번역

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

• 는

  • i*4 해서 byte offset 계산
  • save[i] load
  • k와 비교
  • 다르면 탈출
  • 같으면 i++
  • 다시 loop

  로 구현된다.

• 여기서 꼭 익숙해져야 하는 패턴은

  • 배열 접근에는 sll이 자주 등장한다
  • 비교 후 탈출 조건에는 bne/beq가 자주 등장한다

  는 점이다.

basic block

• basic block은

  • 중간에 branch target이 없고
  • 끝부분 외에는 branch가 없는
  • 연속된 instruction 묶음

  이다.

• compiler 최적화와 processor 실행 단위에서 중요하다.

< 비교는 어떻게 하나

• MIPS에는 기본적으로 blt 같은 진짜 기계 명령보다 slt 중심 구조가 더 중요하다.

slt $t0, $s1, $s2
bne $t0, $zero, L

• 즉
  1. 먼저 $s1 < $s2인지 검사해서
  2. 참이면 1, 거짓이면 0 저장
  3. 그 결과를 branch에 사용한다.
• 슬라이드는 왜 blt, bge 같은 걸 기본 명령으로 두지 않느냐고 묻고, 비교 하드웨어를 branch에 직접 엮으면 clock이 느려질 수 있으니 흔한 beq, bne 중심으로 타협한 것이라고 설명한다.

signed vs unsigned comparison

• signed 비교는 slt, slti

• unsigned 비교는 sltu, sltiu

• 같은 bit pattern도 signed로 보느냐 unsigned로 보느냐에 따라 결과가 달라진다.

• 예를 들어 111...1111은

  • signed면 -1
  • unsigned면 4294967295

  다.

9. Procedures

함수 호출이 기계 수준에서 필요한 것

• 슬라이드는 procedure call에 필요한 일을 6단계로 정리한다.
  1. 인자를 register에 넣는다.
  2. procedure로 control을 넘긴다.
  3. procedure가 쓸 storage를 확보한다.
  4. procedure body를 수행한다.
  5. 결과를 caller가 볼 수 있게 둔다.
  6. 원래 자리로 돌아간다.

register convention

• $a0 ~ $a3: argument
• $v0, $v1: return value
• $t0 ~ $t9: temporary
• $s0 ~ $s7: saved
• $sp: stack pointer
• $fp: frame pointer
• $ra: return address
• 이건 정말 중요하다. 2단원에서 함수 문제는 사실상 이 convention을 이해했는지 묻는 문제다.

jal과 jr

jal ProcedureLabel
jr  $ra

• jal은
  • 다음 instruction 주소를 $ra에 저장하고
  • 함수로 jump한다.
• jr $ra는
  • $ra에 저장된 주소로 돌아간다.

leaf procedure

• leaf procedure는 다른 procedure를 호출하지 않는 함수다.
• 예시 leaf_example에서는
  • 인자들이 $a0 ~ $a3에 들어오고
  • 지역 변수 역할의 $s0를 쓰기 때문에 stack에 save했다가
  • 마지막에 restore하고
  • $v0에 결과를 둔 뒤 돌아간다.

addi $sp, $sp, -4
sw   $s0, 0($sp)
...
lw   $s0, 0($sp)
addi $sp, $sp, 4
jr   $ra

• 즉 stack은 “필요한 레지스터를 잠깐 보관하는 장소"다.

non-leaf procedure

• non-leaf procedure는 다른 함수를 호출하는 함수다.

• 이 경우 더 조심해야 한다.

• 왜냐하면 내가 또 jal을 하면 $ra가 덮어써질 수 있기 때문이다.

• 그래서 fact 예시에서는

  • $ra 저장
  • $a0 저장
  • recursive call
  • 복구
  • 곱셈 후 return

  흐름으로 간다.

• 즉 non-leaf의 핵심은 내가 나중에도 필요할 값들을 call 전에 stack에 저장해야 한다는 것이다.

stack frame / activation record

• 함수가 실행되는 동안 필요한 지역 데이터, 저장 레지스터 등을 묶어둔 영역을 procedure frame이라고 한다.
• 각 함수 호출은 자기 stack frame을 가질 수 있다.
• recursive call이 가능한 이유도 이 구조 덕분이다.

memory layout

• 프로그램 메모리 구조는 대체로

  • Text
  • Static data
  • Heap
  • Stack

  으로 나뉜다.

• malloc/new는 heap

• 함수 호출의 자동 변수와 saved register는 stack 쪽이다.

10. Character Data와 Byte/Halfword

문자 표현

• 문자는 byte 단위 인코딩으로 다룬다.

• 슬라이드는

  • ASCII
  • Latin-1
  • Unicode
  • UTF-8 / UTF-16

  를 소개한다.

• 즉 “문자"도 결국 메모리 속 bit pattern일 뿐이며, 어떤 인코딩 규칙으로 해석하느냐의 문제다.

byte / halfword load-store

• word만 있는 게 아니라

  • lb, lh
  • lbu, lhu
  • sb, sh

  도 있다.

• lb, lh는 sign extension

• lbu, lhu는 zero extension

• 을 한다.

• 문자열 처리는 byte 기반이므로 이런 명령이 특히 중요하다.

strcpy 예시의 의미

• strcpy 예시는 결국
  • y[i]를 byte로 읽고
  • x[i]에 byte로 저장하고
  • null character인지 검사하면서 반복하는 코드다.
• 즉 C의 문자열이 왜 byte array + null terminator 기반인지, assembly 수준에서도 그대로 보인다.

11. 32-bit Constants와 Addressing

16비트 immediate의 한계

• 대부분의 상수는 작아서 16-bit immediate면 충분하지만, 가끔 32-bit 상수가 필요하다.
• 이때 lui를 쓴다.

lui $s0, upper16
ori $s0, $s0, lower16

• lui는 upper 16비트를 왼쪽에 넣고, 아래 16비트는 0으로 채운다.
• 그다음 ori로 아래쪽을 채운다.

branch addressing

• branch는 보통 가까운 곳으로 가므로 PC-relative addressing을 쓴다.

• 왜 ×4냐면 instruction이 4 byte 단위이기 때문이다.
• 즉 offset은 “instruction 개수 단위"에 가깝다.

jump addressing

• j, jal은 더 먼 곳으로 갈 수도 있으므로 26비트 target field를 사용한다.
• 완전한 32비트를 다 싣는 건 아니고, 상위 비트는 현재 PC의 일부를 이용하는 방식이다.
• 그래서 pseudo-direct addressing이라 부른다.

branching far away

• branch target이 너무 멀면 16비트 offset으로는 못 간다.

• 그러면 assembler가 코드를 바꿔서

  • 반대 조건 branch
  • 그 뒤 j

  형태로 재작성할 수 있다.

decoding machine code

• instruction은 bit field로 나뉘므로, 기계어를 보면 다시 assembly로 해석할 수 있다.
• 예를 들어 opcode, rs, rt, rd, funct를 읽어 add $s0, $a1, $t7 식으로 복원할 수 있다.
• 시험에서 종종 나오는 포인트다.

12. Synchronization

왜 동기화가 필요한가

• 두 processor가 같은 memory를 공유하면, 접근 순서에 따라 결과가 달라질 수 있다.
• 이것이 data race다.
• 단순 read/write만으로는 안전한 synchronization이 어렵기 때문에 atomic operation이 필요하다.

ll / sc

• MIPS는

  • ll (load linked)
  • sc (store conditional)

  쌍으로 atomic update를 지원한다.

• 흐름은 대충

  1. ll로 읽고
  2. 값 바꾸려 시도
  3. 중간에 다른 쓰기가 없었으면 sc 성공
  4. 아니면 실패해서 다시 시도

• 다.

• lock 구현 같은 데 쓰인다.

13. Pseudoinstructions와 Translation / Linking / Loading

pseudoinstruction이란

• pseudoinstruction은 “assembler가 편의를 위해 만들어주는 가짜 instruction"이다.
• 실제 하드웨어 instruction 하나와 1:1 대응되지 않을 수 있다.

예:

move $t0, $t1

• 실제로는

add $t0, $zero, $t1

• 로 바뀔 수 있다.

또는

blt $t0, $t1, L

• 는 실제로는

slt $at, $t0, $t1
bne $at, $zero, L

• 식으로 풀린다.

object module

• assembler/compiler는 기계어만 뽑는 게 아니라 object module을 만든다.

• 여기에는

  • text segment
  • static data
  • relocation info
  • symbol table
  • debug info

  등이 들어간다.

linking

• linker는 여러 object module을 합쳐 실행 파일을 만든다.

• 하는 일은

  1. segment 병합
  2. label 주소 결정
  3. location-dependent reference patch

  다.

loading

• loader는 실행 파일을 memory에 올리고
  • 주소 공간 만들고
  • text/data 복사하고
  • stack과 register 초기화하고
  • startup routine으로 jump한다.
• 결국 main이 실행되기 전에 이미 꽤 많은 준비 작업이 있다.

dynamic linking

• 모든 library를 미리 다 합치는 static linking과 달리, dynamic linking은 필요할 때 로드한다.

• 장점은

  • 실행 파일이 덜 비대해지고
  • 라이브러리 업데이트 반영이 쉽다

  는 점이다.

Java startup

• JVM은 bytecode를 해석하다가, hot method는 native code로 컴파일하기도 한다.
• 즉 machine-level execution으로 내려가는 방식도 언어/런타임에 따라 다양하다.

14. Sort Example: 전부 연결해서 보기

왜 이 예제가 중요한가

• bubble sort 예제는 2단원 개념을 한 번에 묶는다.

• 여기에는

  • array indexing
  • loop
  • comparison
  • procedure call
  • stack save/restore

  가 전부 들어 있다.

swap

• swap(v, k)는 leaf procedure다.

• k * 4 해서 v[k] 주소 계산 후,

  • v[k]
  • v[k+1]

  를 읽고 서로 바꿔 저장한다.

sort

• sort는 non-leaf procedure다.

• 왜냐하면 내부에서 swap을 호출하기 때문이다.

• 그래서 $ra, $s0, $s1, $s2, $s3 등을 stack에 save하고 restore한다.

• 이 예제는

  • leaf면 최소한만 save하면 되고
  • non-leaf면 call 이후에도 필요한 값들을 반드시 보존해야 한다

  는 점을 아주 잘 보여 준다.

15. Arrays vs. Pointers

array indexing

• 배열 인덱싱은 매번

  • index × 원소크기
  • • base address

  계산이 필요하다.

pointer version

• 포인터는 이미 “현재 주소"를 직접 들고 있으니, 그냥 다음 원소 주소로 4씩 증가시키면 된다.
• 그래서 표면적으로는 pointer 방식이 더 단순해 보인다.

하지만 결론은

• compiler가 잘 최적화하면 배열 코드도 pointer 코드처럼 바꿀 수 있다.

• 슬라이드는 명시적으로

  • induction variable elimination
  • strength reduction

  등을 통해 compiler가 비슷한 효과를 낼 수 있다고 말한다.

• 그래서 무조건 pointer를 수동으로 쓰는 것보다, 더 명확하고 안전한 코드를 쓰는 게 낫다고 정리한다.

16. ARM, x86와의 비교

ARM

• ARM도 MIPS와 비슷한 기본 철학을 가진다.
• 특히 ARM v8은 64-bit로 넘어오면서 MIPS와 더 닮아진 부분이 많다고 슬라이드가 설명한다.

x86

• x86은 역사적으로 계속 확장되면서 복잡해진 ISA다.
• backward compatibility를 유지하면서 기능이 계속 누적되었다.
• variable-length encoding, 다양한 addressing mode 같은 특성이 있고, 전형적인 CISC 쪽 예시다.

여기서 얻는 포인트

• MIPS는 단순성과 규칙성의 예시

• x86은 역사적 호환성과 복잡성의 예시

  로 보면 된다.

• 시험에서는 세부 역사보다 “왜 MIPS를 가르치는가” 쪽 이해가 더 중요하다.

17. Fallacies, Pitfalls, Lessons

fallacy 1: 강력한 instruction이면 성능도 좋다

• 꼭 그렇지 않다.
• instruction이 복잡하면 구현이 어려워지고, 오히려 전체 clock이 느려질 수 있다.
• 단순한 instruction 여러 개가 더 낫기도 하다.

fallacy 2: assembly가 무조건 빠르다

• 현대 compiler는 현대 processor 구조를 꽤 잘 안다.
• 사람이 직접 assembly를 쓰는 것이 항상 더 낫지는 않다.

pitfall 1: sequential words는 sequential addresses가 아니다

• word는 4 byte이므로 다음 word 주소는 +1이 아니라 +4다.
• 이건 배열 주소 계산에서 매우 자주 실수하는 부분이다.

pitfall 2: 자동 변수의 주소를 함수 종료 뒤에도 계속 쥐고 있기

• stack frame이 사라지면 그 주소는 더 이상 유효하지 않다.
• dangling pointer 문제다.

마지막 교훈

• instruction count와 CPI만 따로 보면 충분하지 않다.
• compiler optimization은 algorithm에 민감하다.
• Java/JIT도 경우에 따라 꽤 빠르다.
• 하지만 슬라이드의 제일 직설적인 결론은 이거다.

Nothing can fix a dumb algorithm.

• 결국 알고리즘이 제일 중요하다는 말이다.