June

Chapter 2: Instructions - Language of the Computer

Chapter 2: Instructions — Language of the Computer

2.1 Introduction

Instruction Set이란 컴퓨터가 지원하는 명령어의 전체 목록이다. 컴퓨터마다 서로 다른 명령어 세트를 갖지만, 공통 요소가 많다. 초기 컴퓨터는 단순한 명령어 세트를 사용했으며, 현대 컴퓨터도 대부분 단순한 명령어 세트를 채택하고 있다.

MIPS Instruction Set은 교재 전반에서 사용되는 대표 ISA이다.

  • Stanford MIPS → MIPS Technologies에 의해 상용화
  • 임베디드 코어 시장에서 큰 점유율 보유
  • 대부분의 현대 ISA를 대표하는 예시

2.2 Operations of the Computer Hardware

모든 산술 연산은 세 개의 오퍼랜드(소스 2개 + 데스티네이션 1개) 형식을 따른다.

javascript
add a, b, c    # a = b + c
설계 원칙 1: Simplicity favors regularity
규칙성이 구현을 단순하게 하고, 단순성이 더 높은 성능과 낮은 비용을 가능하게 한다.

컴파일 예시: f = (g + h) - (i + j);

javascript
add t0, g, h     # temp t0 = g + h
add t1, i, j     # temp t1 = i + j
sub f, t0, t1    # f = t0 - t1

2.3 Operands of the Computer Hardware

레지스터 오퍼랜드

산술 명령어는 레지스터 오퍼랜드를 사용한다. MIPS는 32 x 32비트 레지스터 파일을 갖는다.

  • 자주 접근하는 데이터 저장용
  • 번호: 0~31, 32비트 데이터 = "word"

어셈블러 이름 규칙:

  • $t0~$t9 : 임시 값 (reg 8~15, 24~25)
  • $s0~$s7 : 저장 변수 (reg 16~23)
  • $a0~$a3 : 인수 (reg 4~7)
  • $v0, $v1 : 반환 값 (reg 2, 3)
  • $sp : 스택 포인터 (reg 29)
  • $ra : 반환 주소 (reg 31)
  • $zero : 항상 0 (reg 0), 덮어쓸 수 없음
설계 원칙 2: Smaller is faster
레지스터 파일은 작을수록 접근 속도가 빠르다.

메모리 오퍼랜드

배열, 구조체, 동적 데이터 등 복합 데이터는 메모리에 저장된다.

  • 산술 연산을 위해 메모리 → 레지스터로 Load, 레지스터 → 메모리로 Store
  • Byte addressed: 각 주소가 8비트를 식별
  • Word aligned: 주소는 반드시 4의 배수
  • MIPS는 Big Endian: 최상위 바이트(MSB)가 가장 작은 주소에 위치

예시: g = h + A[8] (인덱스 8 → 오프셋 32바이트, 4 bytes/word)

javascript
lw  $t0, 32($s3)      # $t0 = Memory[$s3 + 32]
add $s1, $s2, $t0

예시: A[12] = h + A[8]

javascript
lw  $t0, 32($s3)      # $t0 = A[8]
add $t0, $s2, $t0
sw  $t0, 48($s3)      # A[12] = h + A[8]

레지스터 vs. 메모리

  • 레지스터가 메모리보다 접근 속도가 훨씬 빠름
  • 메모리 데이터 연산에는 load/store가 추가로 필요 → 명령어 수 증가
  • 컴파일러는 가능한 한 많은 변수를 레지스터에 할당해야 함 → 레지스터 최적화가 핵심

Immediate 오퍼랜드

명령어에 직접 포함된 상수 데이터이다.

javascript
addi $s3, $s3, 4
addi $s2, $s1, -1     # 음수 상수로 뺄셈 수행
설계 원칙 3: Make the common case fast
작은 상수는 자주 사용되므로, load 없이 즉시 사용 가능하게 하는 것이 유리하다.

$zero (reg 0)는 항상 0이며, 레지스터 간 이동 등에 활용된다.

javascript
add $t2, $s1, $zero    # move $s1 to $t2

2.4 Signed and Unsigned Numbers

Unsigned Binary Integers

  • n비트 범위: 0 ~ 2^n - 1
  • 32비트: 0 ~ 4,294,967,295

2's Complement Signed Integers

  • n비트 범위: -2^(n-1) ~ +2^(n-1) - 1
  • 32비트: -2,147,483,648 ~ +2,147,483,647
  • 비트 31 = 부호 비트 (1이면 음수, 0이면 양수/0)
  • 특수 값: 0 = 0000...0000, -1 = 1111...1111

Signed Negation (부호 반전)

1의 보수(complement)를 구한 뒤 +1

javascript
+2 = 0000 0000 ... 0010
~   = 1111 1111 ... 1101
+1  = 1111 1111 ... 1110  →  -2

Sign Extension (부호 확장)

더 많은 비트로 표현할 때 부호 비트를 왼쪽으로 복제한다.

  • MIPS에서 사용되는 경우: addi, lb, lh, beq, bne
  • +2 (8bit → 16bit): 0000 0010 → 0000 0000 0000 0010
  • -2 (8bit → 16bit): 1111 1110 → 1111 1111 1111 1110
  • Unsigned 값은 0으로 확장

2.5 Representing Instructions in the Computer

명령어는 이진수로 인코딩되며, 이를 Machine Code라 한다. MIPS 명령어는 모두 32비트 워드이다.

R-format 명령어

산술/논리 연산에 사용된다.

oprsrtrdshamtfunct
6 bits5 bits5 bits5 bits5 bits6 bits
  • op : 연산 코드 (opcode)
  • rs : 첫 번째 소스 레지스터
  • rt : 두 번째 소스 레지스터
  • rd : 데스티네이션 레지스터
  • shamt : 시프트 양 (Shift Amount)
  • funct : 함수 코드 (opcode 확장)

예시: add $t0, $s1, $s2

javascript
| 000000 | 10001 | 10010 | 01000 | 00000 | 100000 |
|  op=0  | rs=17 | rt=18 | rd=8  | sh=0  | fn=32  |

= 0x02324020

I-format 명령어

Immediate 산술, Load/Store 명령어에 사용된다.

oprsrtconstant or address
6 bits5 bits5 bits16 bits
  • rt: 데스티네이션 또는 소스 레지스터
  • 상수 범위: -2^15 ~ +2^15 - 1
  • 주소: rs의 베이스 주소에 더해지는 오프셋
설계 원칙 4: Good design demands good compromises
서로 다른 포맷은 디코딩을 복잡하게 하지만, 32비트 명령어 크기를 일정하게 유지할 수 있다.

Hexadecimal (16진수)

비트 문자열의 압축 표현. 4비트당 1자리.

javascript
0=0000  4=0100  8=1000  c=1100
1=0001  5=0101  9=1001  d=1101
2=0010  6=0110  a=1010  e=1110
3=0011  7=0111  b=1011  f=1111

Stored Program Computer

  • 명령어도 데이터와 마찬가지로 이진수로 표현되어 메모리에 저장됨
  • 프로그램이 프로그램을 처리 가능 (컴파일러, 링커 등)
  • 이진 호환성: 표준화된 ISA를 통해 다른 컴퓨터에서도 실행 가능

2.6 Logical Operations

연산CJavaMIPS
Shift left<<<<sll
Shift right>>>>>srl
Bitwise AND&&and, andi
Bitwise OR||or, ori
Bitwise NOT~~nor
  • sll (Shift Left Logical): 왼쪽으로 i비트 시프트 → 2^i 곱셈
  • srl (Shift Right Logical): 오른쪽으로 i비트 시프트 → 2^i 나눗셈 (Unsigned만)
  • sra (Shift Right Arithmetic): 부호 비트를 유지하며 오른쪽 시프트 (Signed용)

특정 비트를 1로 설정하고, 나머지는 그대로 둘 때 사용한다.

javascript
$t2 = 0000 0000 0000 0000 0000 1101 1100 0000
$t1 = 0000 0000 0000 0000 0011 1100 0000 0000
──────────────────────────────────────────────
$t0 = 0000 0000 0000 0000 0011 1101 1100 0000  (or $t0, $t1, $t2)

NOT 연산

2.7 Instructions for Making Decisions

조건 분기 명령어

javascript
beq rs, rt, L1     # if (rs == rt) goto L1
bne rs, rt, L1     # if (rs != rt) goto L1
j L1               # 무조건 분기

if-else 컴파일

c
if (i == j) f = g + h;
else f = g - h;
javascript
      bne $s3, $s4, Else
      add $s0, $s1, $s2
      j Exit
Else: sub $s0, $s1, $s2
Exit: ...

while 루프 컴파일

c
while (save[i] == k) i += 1;
// i in $s3, k in $s5, base addr of save in $s6
javascript
Loop: sll  $t1, $s3, 2       # $t1 = i * 4
      add  $t1, $t1, $s6     # $t1 = addr of save[i]
      lw   $t0, 0($t1)       # $t0 = save[i]
      bne  $t0, $s5, Exit    # if save[i] != k, exit
      addi $s3, $s3, 1       # i += 1
      j    Loop
Exit: ...

for 루프 변환 예시

c
for ($1 = 0; $1 < 10; $1++) $2 += $1;
javascript
      addi $1, $0, 0         # i = 0
L:    slti $3, $1, 10        # $3 = (i < 10) ? 1 : 0
      beq  $3, $0, EXIT      # if i >= 10, exit
      nop
      add  $2, $2, $1        # $2 += i
      addi $1, $1, 1         # i++
      j    L
      nop
EXIT:

Basic Blocks

  • 중간에 분기가 없고(끝에만 있음), 분기 대상이 아닌(시작만 가능) 명령어 연속 구간
  • 컴파일러가 최적화 단위로 식별하며, 프로세서가 실행을 가속할 수 있음

Set on Less Than (slt)

javascript
slt  rd, rs, rt        # if (rs < rt) rd = 1; else rd = 0
slti rt, rs, const     # if (rs < const) rt = 1; else rt = 0
sltu rd, rs, rt        # unsigned 비교
sltiu rt, rs, const    # unsigned immediate 비교

slt + beq/bne 조합으로 대소 비교 분기 구현:

javascript
slt $t0, $s1, $s2      # if ($s1 < $s2) $t0 = 1
bne $t0, $zero, L      # if $t0 != 0, branch to L

blt, bge를 쓰지 않는 이유: <, >= 비교 하드웨어가 ==, !=보다 느리기 때문. 모든 명령어가 느려지는 것보다 beq/bne를 일반적인 경우로 쓰는 것이 더 좋은 설계이다.

Signed vs. Unsigned 비교

javascript
$s0 = 1111 1111 1111 1111 1111 1111 1111 1111

slt  $t0, $s0, $s1    # signed: -1 < +1   → $t0 = 1
sltu $t0, $s0, $s1    # unsigned: 4,294,967,295 > 1  → $t0 = 0
  1. 레지스터에 매개변수 배치 ($a0~$a3)
  2. 프로시저로 제어 이전 (jal)
  3. 프로시저용 저장 공간 확보 (스택)
  4. 프로시저 연산 수행
  5. 결과를 레지스터에 배치 ($v0, $v1)
  6. 호출 지점으로 반환 (jr $ra)

레지스터 사용 규칙

레지스터용도번호
$a0 ~ $a3인수 전달4~7
$v0, $v1반환 값2, 3
$t0 ~ $t9임시 값 (callee가 덮어쓸 수 있음)8~15, 24~25
$s0 ~ $s7저장 변수 (callee가 반드시 보존/복원)16~23
$gp전역 데이터 포인터28
$sp스택 포인터29
$fp프레임 포인터30
$ra반환 주소31

프로시저 호출/반환 명령어

javascript
jal ProcedureLabel     # $ra = PC + 4, jump to label
jr  $ra                # PC = $ra (반환)

메모리 레이아웃

영역설명
Text프로그램 코드
Static Data전역 변수 (static, 상수 배열, 문자열). $gp로 접근
Dynamic Data (Heap)malloc / new 로 할당. 위로 성장
Stack자동 저장소 (지역 변수, 반환 주소 등). 아래로 성장
c
int leaf_example(int g, int h, int i, int j) {
    int f;
    f = (g + h) - (i + j);
    return f;
}
javascript
leaf_example:
    addi $sp, $sp, -4       # 스택에 공간 확보
    sw   $s0, 0($sp)        # $s0 저장
    add  $t0, $a0, $a1      # g + h
    add  $t1, $a2, $a3      # i + j
    sub  $s0, $t0, $t1      # f = (g+h) - (i+j)
    add  $v0, $s0, $zero    # 반환 값 설정
    lw   $s0, 0($sp)        # $s0 복원
    addi $sp, $sp, 4        # 스택 복원
    jr   $ra                # 반환
  • 호출 후 필요한 인수 및 임시 값

예시: Factorial fact(n)

javascript
fact:
    addi $sp, $sp, -8       # 스택에 2개 항목 공간
    sw   $ra, 4($sp)        # 반환 주소 저장
    sw   $a0, 0($sp)        # 인수 n 저장
    slti $t0, $a0, 1        # n < 1 ?
    beq  $t0, $zero, L1     # n >= 1이면 L1으로
    addi $v0, $zero, 1      # return 1 (base case)
    addi $sp, $sp, 8        # 스택 복원
    jr   $ra                # 반환
L1: addi $a0, $a0, -1       # n - 1
    jal  fact               # fact(n-1) 재귀 호출
    lw   $a0, 0($sp)        # 원래 n 복원
    lw   $ra, 4($sp)        # 반환 주소 복원
    addi $sp, $sp, 8        # 스택 복원
    mul  $v0, $a0, $v0      # n * fact(n-1)
    jr   $ra                # 반환

2.9 Communicating with People

문자 인코딩

  • ASCII: 128문자 (95 그래픽 + 33 제어)
  • Latin-1: 256문자 (ASCII + 96 그래픽 문자)

String Copy 예시

c
void strcpy(char x[], char y[]) {
    int i = 0;
    while ((x[i] = y[i]) != '\0')
        i += 1;
}
javascript
strcpy:
    addi $sp, $sp, -4
    sw   $s0, 0($sp)        # $s0 저장
    add  $s0, $zero, $zero   # i = 0
L1: add  $t1, $s0, $a1      # addr of y[i]
    lbu  $t2, 0($t1)        # $t2 = y[i]
    add  $t3, $s0, $a0      # addr of x[i]
    sb   $t2, 0($t3)        # x[i] = y[i]
    beq  $t2, $zero, L2     # y[i] == 0 이면 종료
    addi $s0, $s0, 1        # i++
    j    L1
L2: lw   $s0, 0($sp)        # $s0 복원
    addi $sp, $sp, 4
    jr   $ra

분기 대상은 대부분 현재 명령어 근처에 있으므로, PC 기준 상대 주소를 사용한다.

javascript
Target address = PC + offset x 4

Jump Addressing (Pseudo-direct)

j, jal은 텍스트 세그먼트 내 어디든 점프할 수 있다.

javascript
Target address = PC[31:28] : (address x 4)
모드설명사용 예
Register레지스터의 값을 직접 사용add, sub
Immediate명령어에 포함된 상수addi, ori
Base + Offset레지스터 + 오프셋lw, sw
PC-relativePC + offset x 4beq, bne
Pseudo-directPC 상위 4비트 + 주소 x 4j, jal

분기 거리가 먼 경우

16비트 오프셋으로 인코딩할 수 없을 만큼 멀면, 어셈블러가 코드를 재작성한다.

javascript
beq $s0, $s1, L1
    ↓
bne $s0, $s1, L2
j L1
L2: ...

2.11 Parallelism and Instructions: Synchronization

두 프로세서가 메모리 영역을 공유할 때 동기화 없이 접근하면 Data Race가 발생한다. 이를 위해 하드웨어 수준의 Atomic read/write 연산이 필요하다.

$at (reg 1): 어셈블러가 내부적으로 사용하는 임시 레지스터

Linking

  1. 세그먼트 병합

Loading

  1. 헤더에서 세그먼트 크기 파악
  2. 가상 주소 공간 생성

Dynamic Linking

  • 정적 링크로 인한 이미지 비대 방지
  • Lazy Linkage: 간접 테이블 + 스텁을 통해 첫 호출 시에만 링커/로더 동작

2.13 A C Sort Example

  • "Nothing can fix a dumb algorithm!"
항목ARMMIPS
발표19851985
명령어 크기32 bits32 bits
주소 공간32-bit flat32-bit flat
데이터 정렬AlignedAligned
주소 모드 수9개3개
레지스터15 x 32-bit31 x 32-bit
I/OMemory mappedMemory mapped

Seoul, South Korea

jwsong5160@gmail.com

© 2026 Junwoo Song