๐Ÿค– ์ปดํ“จํ„ฐ๊ฐ€ ์ฝ”๋“œ๋ฅผ ์ฝ๋Š” ์•„์ฃผ ๊ตฌ์ฒด์ ์ธ ์›๋ฆฌ

MIPS ์–ด์…ˆ๋ธ”๋ฆฌ์–ด ํ›‘์–ด๋ณด๊ธฐ

์ง€๋‚œ ํ•™๊ธฐ ์šด์˜์ฒด์ œ ๊ณต๋ถ€๋ฅผ ํ•˜๋ฉด์„œ ๋” ๋‚ฎ์€ ๋ ˆ๋ฒจ์€ ์–ด๋–ป๊ฒŒ ๋™์ž‘ํ•˜๋Š”์ง€ ๊ถ๊ธˆํ•ด์กŒ๋‹ค. David A. Patterson๊ณผ John L. Hennessy์˜ Computer Organization and Design 5th Edition์˜ ์ „๋ฐ˜๋ถ€๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ MIPS instruction set์— ๋Œ€ํ•ด ์ •๋ฆฌํ–ˆ๋‹ค.

Computer Abstractions and Technology

์ปดํ“จํ„ฐ ์•„ํ‚คํ…์ฒ˜๋ฅผ ๊ณต๋ถ€ํ•œ๋‹ค๋Š” ๊ฒƒ์€ ์ปดํ“จํ„ฐ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ํ•˜๋“œ์›จ์–ด์™€ ๋ช…๋ น์–ด๊ฐ€ ์–ด๋–ป๊ฒŒ ํ•จ๊ป˜ ๋™์ž‘ํ•˜๋Š”์ง€ ์•Œ์•„๋ณด๋Š” ๊ฒƒ์ด๋‹ค. ํ•˜๋“œ์›จ์–ด๋ฅผ ๋‹ค๋ฃจ๊ธฐ๋Š” ํ•˜์ง€๋งŒ ํšŒ๋กœ์— ๋Œ€ํ•œ ๋ถ€๋ถ„์„ ์ž์„ธํžˆ ๋‹ค๋ฃจ์ง€๋Š” ์•Š๋Š”๋‹ค. ํšŒ๋กœ๋Š” ๋กœ์šฐ๋ ˆ๋ฒจ ์•„ํ‚คํ…์ฒ˜์ด๊ณ , ์•ž์œผ๋กœ ๋‹ค๋ฃฐ ๋‚ด์šฉ์€ ํšŒ๋กœ(ํ•˜๋“œ์›จ์–ด)์™€ ์šด์˜์ฒด์ œ(์†Œํ”„ํŠธ์›จ์–ด) ์‚ฌ์ด์— ์žˆ๋Š” ISA(Instruction Set Architecture), microarchitecture์™€ ๊ฐ™์€ ํ•˜์ด๋ ˆ๋ฒจ ์•„ํ‚คํ…์ฒ˜๋‹ค.

Instructions: Language of the Computer

ISA๋Š” add, load์™€ ๊ฐ™์€ ๋ช…๋ น์˜ ์ง‘ํ•ฉ์œผ๋กœ, ํ•˜๋“œ์›จ์–ด์™€ ์†Œํ”„ํŠธ์›จ์–ด ์‚ฌ์ด์˜ ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์ •์˜ํ•œ๋‹ค. microarchitecture๋Š” ISA์˜ ๊ตฌํ˜„์ฒด๋กœ, ํ”„๋กœ์„ธ์„œ์™€ ์ž…์ถœ๋ ฅ subsystem์˜ ์กฐ์ง์ด๋‹ค. ํŒŒ์ดํ”„๋ผ์ธ์˜ ๊นŠ์ด๋‚˜ ์บ์‹œ ์‚ฌ์ด์ฆˆ๊ฐ€ microarchitecture๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค.

๋จธ์‹  ์„ค๊ณ„์—๋Š” ๋‘ ๊ฐ€์ง€ ์ค‘์š”ํ•œ ์›์น™์ด ์žˆ๋‹ค. ์ฒซ์งธ๋Š” ์ปดํ“จํ„ฐ๋Š” ๋ชจ๋“  ๊ฒƒ์„ bit๋กœ ์ดํ•ดํ•˜๊ธฐ ๋•Œ๋ฌธ์— instruction๊ณผ ๋ฐ์ดํ„ฐ๋ฅผ ๊ตฌ๋ถ„ํ•˜์ง€ ๋ชปํ•œ๋‹ค๋Š” ๊ฒƒ์ด๊ณ , ๋‘˜์งธ๋Š” ํ”„๋กœ๊ทธ๋žจ๋„ ๋ฐ์ดํ„ฐ์™€ ๋˜‘๊ฐ™์ด ๋ฉ”๋ชจ๋ฆฌ์— ์ €์žฅ๋œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์—ฌ๋Ÿฌ ๊ตฌํš์œผ๋กœ ๊ตฌ๋ถ„ํ•œ ๊ฒƒ์€ ์ธ๊ฐ„์˜ ์ž…์žฅ์ด์ง€, ์ปดํ“จํ„ฐ๋Š” ๊ฒฐ๊ตญ ๋ฐ”์ด๋„ˆ๋ฆฌ๋กœ ๋ฐ›์•„๋“ค์ธ๋‹ค.

From a High-Level Language to the Language of Hardware

int main(int argc, char *argv[]) {
  int s0 = 0, s1 = 1, s2 = 2;
  s0 = s1 + s2;
  return 0;
}

ํ•˜์ด๋ ˆ๋ฒจ ์–ธ์–ด๋Š” ์ž์—ฐ์–ด์™€ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด๋‹ค. ๋†’์€ ์ƒ์‚ฐ์„ฑ์„ ์ œ๊ณตํ•˜๋ฉฐ, C, C++, Java ๋“ฑ ํ”ํžˆ ์‚ฌ์šฉ๋˜๋Š” ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด๋“ค์€ ๋Œ€๋ถ€๋ถ„ ํ•˜์ด๋ ˆ๋ฒจ ์–ธ์–ด๋‹ค. ํ•˜์ด๋ ˆ๋ฒจ ์–ธ์–ด๋Š” ์ปดํŒŒ์ผ๋Ÿฌ๋ฅผ ํ†ตํ•ด ์–ด์…ˆ๋ธ”๋ฆฌ์–ด๋กœ ๋ณ€ํ™˜๋œ๋‹ค.

  .data
  .text
main:
  add $s0, $s1, $s2

์–ด์…ˆ๋ธ”๋ฆฌ์–ด๋Š” ์ปดํ“จํ„ฐ์˜ ๊ตฌ์ฒด์ ์ธ ๋™์ž‘์„ ํ…์ŠคํŠธ๋กœ ํ‘œํ˜„ํ•œ ๊ฒƒ์œผ๋กœ, instruction์˜ ์ง‘ํ•ฉ์ด๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด ๋‹จ๊ณ„์—์„œ ํ•˜์ด๋ ˆ๋ฒจ ์ฝ”๋“œ๋Š” ๋ช…๋ น์ค„ ์‚ฌ์ด์˜ ์ ํ”„ ์ˆ˜์ค€๊นŒ์ง€ ๋‚ด๋ ค๊ฐ„๋‹ค. ์–ด์…ˆ๋ธ”๋ฆฌ์–ด๋Š” ์–ด์…ˆ๋ธ”๋Ÿฌ์— ์˜ํ•ด ๊ธฐ๊ณ„์–ด๋กœ ๋ณ€ํ™˜๋œ๋‹ค.

00000000000000000000000000000100
00000000000000000000000000000000
00000010001100101000000000100000

๊ธฐ๊ณ„์–ด๋Š” ์ปดํ“จํ„ฐ๊ฐ€ ์ดํ•ดํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐ”์ด๋„ˆ๋ฆฌ ์ˆซ์ž๋งŒ์œผ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋‹ค. ์ปดํ“จํ„ฐ๋Š” ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ๊ฐ„ ๋ฐ”์ด๋„ˆ๋ฆฌ ์ฝ”๋“œ๋ฅผ CPU๋กœ ๊ฐ€์ ธ์™€ instruction์„ ์ˆ˜ํ–‰ํ•œ๋‹ค.

Operations of the Computer Hardware

ISA์—๋Š” ์—ฌ๋Ÿฌ ์ข…๋ฅ˜๊ฐ€ ์žˆ๋Š”๋ฐ, ๋Œ€ํ‘œ์ ์œผ๋กœ Intel๊ณผ AMD์—์„œ ๋งŒ๋“  'x86โ€™์ด ์žˆ๋Š”๋ฐ, CPU ์•„ํ‚คํ…์ฒ˜๊ฐ€ CISC(Complex Instruction Set Computer) ๊ธฐ๋ฐ˜์ด๊ธฐ ๋•Œ๋ฌธ์— ๊ต‰์žฅํžˆ ๋ณต์žกํ•˜๋‹ค. ํ•œํŽธ 'ARM Architectureโ€™๋Š” ์Šค๋งˆํŠธํฐ์ด๋‚˜ ํƒœ๋ธ”๋ฆฟ๊ณผ ๊ฐ™์€ ๋ชจ๋ฐ”์ผ ๊ธฐ๊ธฐ์— ์‚ฌ์šฉ๋œ๋‹ค. ์šฐ๋ฆฌ๊ฐ€ ์‚ฌ์šฉํ•  ISA๋Š” MIPS(Microprocessor without Interlocked Pipeline Stages)์ด๋ฉฐ, ์‹œ์Šคํ…œ์ด ๊ฐ„๋‹จํ•ด ์ปดํ“จํ„ฐ ์•„ํ‚คํ…์ฒ˜๋ฅผ ๊ณต๋ถ€ํ•˜๋Š” ๋ชฉ์ ์œผ๋กœ ์ ํ•ฉํ•˜๋‹ค. ์‹ค์ œ๋กœ๋Š” ๋ธ”๋ฃจ๋ ˆ์ด ๊ธฐ๊ธฐ๋‚˜ ํ”Œ๋ ˆ์ด์Šคํ…Œ์ด์…˜๊ณผ ๊ฐ™์€ ๋””์ง€ํ„ธ ํ™ˆ, ๋„คํŠธ์›Œํ‚น ์žฅ๋น„์— ์‚ฌ์šฉ๋œ๋‹ค.

MIPS Instructions

์•ž์„œ ํ•˜์ด๋ ˆ๋ฒจ ์–ธ์–ด๊ฐ€ ์–ด์…ˆ๋ธ”๋ฆฌ์–ด๋กœ, ์–ด์…ˆ๋ธ”๋ฆฌ์–ด๊ฐ€ ์ตœ์ข…์ ์œผ๋กœ ๊ธฐ๊ณ„์–ด๋กœ ๋ณ€ํ™˜๋œ๋‹ค๋Š” ๊ฒƒ์„ ๋ณด์•˜๋‹ค. ํ•˜์ด๋ ˆ๋ฒจ ์–ธ์–ด๋Š” ์•Œ๊ณ  ์žˆ๋‹ค๋Š” ๊ฐ€์ •ํ•˜์—, ์‹ค์ œ MIPS์—์„œ instruction์ด ์–ด๋–ป๊ฒŒ ์ž‘์„ฑ๋˜๋Š”์ง€, ๊ทธ instruction์ด ์–ด๋–ค ๊ทœ์น™์— ๋”ฐ๋ผ ๊ธฐ๊ณ„์–ด๋กœ ๋ณ€ํ™˜๋˜๋Š” ์ง€ ์•Œ์•„๋ณด์ž.

๋จผ์ € CPU๊ฐ€ ๋งค๋ฒˆ ๋ฉ”์ธ๋ฉ”๋ชจ๋ฆฌ์—์„œ ๊ฐ’์„ ์ฝ์–ด์˜ค๋Š” ๊ฒƒ์€ ์˜ค๋ฒ„ํ—ค๋“œ๊ฐ€ ํฐ ์ผ์ด๊ธฐ ๋•Œ๋ฌธ์— CPU๋Š” ๋ ˆ์ง€์Šคํ„ฐ๋ผ๋Š” ์ž‘๊ณ  ๋น ๋ฅธ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ํฌ๊ธฐ๋Š” ์ž‘์ง€๋งŒ ์†๋„๊ฐ€ ๋นจ๋ผ์„œ ๋ ˆ์ง€์Šคํ„ฐ์— ๋ฐ์ดํ„ฐ๋ฅผ ๋‘๋ฉด instruction์„ ๋น ๋ฅด๊ฒŒ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ๋‹ค. MIPS์˜ ์—ฐ์‚ฐ์€ 32x32bit ๋ ˆ์ง€์Šคํ„ฐ๋ฅผ ์‚ฌ์šฉํ•˜๋ฉฐ, 32bit ๋ฐ์ดํ„ฐ๋ฅผ word๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. ๋ ˆ์ง€์Šคํ„ฐ์˜ ์ผ๋ถ€์—๋Š” ๋ฏธ๋ฆฌ ์ด๋ฆ„์„ ๋ถ™์—ฌ ๋†“์•˜๋Š”๋ฐ, $t0๋ถ€ํ„ฐ $t9๊นŒ์ง€๋Š” ์ž„์‹œ ๋ ˆ์ง€์Šคํ„ฐ(temporary register)๋ฅผ ์˜๋ฏธํ•˜๋ฉฐ, $s0๋ถ€ํ„ฐ $s7๊นŒ์ง€๋Š” ๊ณ„์† ์‚ฌ์šฉ๋˜๋Š” ๋ ˆ์ง€์Šคํ„ฐ(saved register)๋ฅผ ์˜๋ฏธํ•œ๋‹ค.

Arithmetic Operations

์‚ฐ์ˆ  ์—ฐ์‚ฐ์€ ๊ทธ๋ฆฌ ๋ณต์žกํ•˜์ง€ ์•Š๋‹ค.

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

a, b, c, d, e๊ฐ€ ๊ฐ๊ฐ ๋ ˆ์ง€์Šคํ„ฐ $s0, $s1, $s2, $s3, $s4์— ๋Œ€์‘๋œ๋‹ค๊ณ  ํ•˜๋ฉด MIPS ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

add $t0, $s1, $s2 # $t0 = $s1 + $s2
add $t1, $s3, $s4 # $t1 = $s3 + $s3
sub $s0, $t0, $t1 # $s0 = $t0 - $t1

add๋Š” ๊ฐ’์„ ๋ง์…ˆ์„, sub๋Š” ๋บ„์…ˆ์„ ์ˆ˜ํ–‰ํ•œ๋‹ค.

Memory Operations

MIPS์˜ ๋ฉ”๋ชจ๋ฆฌ ์—ฐ์‚ฐ์€ ๋ฉ”๋ชจ๋ฆฌ์—์„œ ๋ ˆ์ง€์Šคํ„ฐ๋กœ, ๋ ˆ์ง€์Šคํ„ฐ์—์„œ ๋ฉ”๋ชจ๋ฆฌ๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ์˜ฎ๊ธฐ๋Š” ์ผ์„ ํ•œ๋‹ค.

a = b + A[8]

a, b์€ ๊ฐ๊ฐ $s1, $s2์— ๋Œ€์‘๋˜๊ณ , A์˜ base address๊ฐ€ $s3์— ๋Œ€์‘๋œ๋‹ค๊ณ  ํ•˜๋ฉด MIPS ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

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

lw๋Š” ๋ฉ”๋ชจ๋ฆฌ์—์„œ ๋ ˆ์ง€์Šคํ„ฐ๋กœ ๊ฐ’์„ ๊ฐ€์ ธ์˜จ๋‹ค. ์ •์ˆ˜ ๋ฐฐ์—ด์˜ ์›์†Œ๋“ค์€ ๋ฉ”๋ชจ๋ฆฌ์ƒ์— ๊ฐ์ž 1word(4bytes)์”ฉ ์ฐจ์ง€ํ•˜๋ฉฐ ์ €์žฅ๋œ๋‹ค. ์ฆ‰, A[8]๋Š” ๋ฉ”๋ชจ๋ฆฌ ์ƒ์— ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์กด์žฌํ•œ๋‹ค.

4byte   4byte     4byte          4byte
A[0],   A[1],     A[2],    ...,  A[8]
$s3,    4($s3),   8($s3),  ...,  32($s3)

๋”ฐ๋ผ 32($s3)์€ base address $s3์—์„œ 32bytes ๋–จ์–ด์ง„ ์œ„์น˜์— ์ ‘๊ทผํ•œ๋‹ค๋Š” ์˜๋ฏธ๊ฐ€ ๋œ๋‹ค. ์ด๋•Œ ์•ž์— ๋ถ™๋Š” ์ˆซ์ž๋ฅผ offset์ด๋ผ๊ณ  ํ•˜๋ฉฐ, base address๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋ ˆ์ง€์Šคํ„ฐ(์œ„ ๊ฒฝ์šฐ $s3)๋Š” base register๋ผ๊ณ  ํ•œ๋‹ค.

A[12] = a + A[8]

a๊ฐ€ $s2, A์˜ base address๊ฐ€ $s3์— ๋Œ€์‘๋œ๋‹ค๊ณ  ํ•˜๋ฉด MIPS ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

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

sw๋Š” ๋ ˆ์ง€์Šคํ„ฐ์—์„œ ๋ฉ”๋ชจ๋ฆฌ๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ์˜ฎ๊ธด๋‹ค. ์œ„์—์„œ๋Š” lw๋กœ ๋ฉ”๋ชจ๋ฆฌ์—์„œ 32($s3) ๊ฐ’์„ ๊ฐ€์ ธ์™€ ๋ ˆ์ง€์Šคํ„ฐ์˜ $t0์— ์ €์žฅํ–ˆ๊ณ , ์•„๋ž˜์—์„œ๋Š” $t0์˜ ๊ฐ’์„ ๋ฉ”๋ชจ๋ฆฌ์˜ 48($s3) ์œ„์น˜์— ์ €์žฅํ–ˆ๋‹ค.

Immediate Instructions

์ƒ์ˆ˜๋ฅผ ๋”ํ•  ๋•Œ๋Š” addi๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.

addi $s3, $s3, 4 # $s3 = $s3 + 4
addi $s2, $s2, -1 # $s2 = $s2 + (-1)

์ƒ์ˆ˜์— ๋Œ€ํ•œ ๋บ„์…ˆ ์—ฐ์‚ฐ์€ ๋”ฐ๋กœ ์—†๊ธฐ ๋•Œ๋ฌธ์— ์Œ์ˆ˜๋ฅผ ๋”ํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

Constant

MIPS ๋ ˆ์ง€์Šคํ„ฐ $zero๋Š” ์ƒ์ˆ˜ 0์„ ์˜๋ฏธํ•œ๋‹ค.

add $t0, $s1, $zero # $t0 = $s1 + 0

์œ„ ์ฒ˜๋Ÿผ ๋‹ค๋ฅธ ๋ ˆ์ง€์Šคํ„ฐ๋กœ ๊ฐ’์„ ๊ทธ๋Œ€๋กœ ๋Œ€์ž…ํ•  ๋•Œ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

Conditional Statement

if (i == j) {
  a = b + c;
} else {
  a = b - c;
}

a, b, c, i, j๊ฐ€ ๊ฐ๊ฐ $s0๋ถ€ํ„ฐ $s4์— ๋Œ€์‘๋œ๋‹ค๊ณ  ํ•˜๋ฉด MIPS ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

  bne $s3, $s4, Else # if ($s3 == $s4)
  add $s0, $s1, $s2 # { $s0 = $s1 + $s2 }
  j Exit
Else:
  sub $s0, $s1, $s2 # else { $s0 = $s1 - $s2 }
Exit:
  ...

bne๋Š” ๋‘ ๋ ˆ์ง€์Šคํ„ฐ ๊ฐ’์ด ๊ฐ™์€์ง€ ๋น„๊ตํ•ด ๊ฐ™๋‹ค๋ฉด ๋‹ค์Œ ๊ตฌ๋ฌธ์„, ๋‹ค๋ฅด๋‹ค๋ฉด ์ง€์ •๋œ ๋ผ๋ฒจ๋กœ ์ ํ”„ํ•œ๋‹ค. ์œ„์—์„œ๋Š” bne๋ฅผ ํ†ตํ•ด $s3์™€ $s4๊ฐ€ ๊ฐ™์€์ง€ ๋น„๊ตํ•œ ๋’ค, ๋‹ค๋ฅด๋‹ค๋ฉด Else ๋ผ๋ฒจ๋กœ ์ ํ”„ํ•ด sub $s0, $s1, $s2๋ฅผ ์‹คํ–‰ํ•˜๋„๋ก ํ–ˆ๋‹ค. ๋ผ๋ฒจ ์ด๋ฆ„์€ ๊ฐœ๋ฐœ์ž๊ฐ€ ์ž„์˜๋กœ ์ •ํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ผญ Else๋‚˜ Exit๋ผ๋Š” ์ด๋ฆ„์ผ ํ•„์š”๋Š” ์—†๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. ๋˜ํ•œ ๋ผ๋ฒจ์˜ ์œ„์น˜๋Š” ์–ด์…ˆ๋ธ”๋Ÿฌ๊ฐ€ ๊ณ„์‚ฐํ•œ๋‹ค.

Loop

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

i, k๊ฐ€ ๊ฐ๊ฐ $s3, $s5์—, save์˜ base address๊ฐ€ $s6์— ๋Œ€์‘๋œ๋‹ค๊ณ  ํ•˜๋ฉด MIPS ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

Loop:
  sll $t1, $s3, 2 # $t1 = $s3 << 2
  add $t1, $t1, $s6 # $t1 = $t1($s6)
  lw $t0, 0($t1) # $t0 = 0($t1)
  bne $t0, $s5, Exit # if ($t0 != $s5) { goto Exit }
  addi $s3, $s3, 1 # $s3 += 1
  j Loop
Exit:
  ...

์ƒ๋‹นํžˆ ๋ณต์žกํ•œ๋ฐ, ํฌ๊ฒŒ ๋‘ ๋ถ€๋ถ„์œผ๋กœ ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๋‹ค. bne๋ถ€ํ„ฐ j ๋ผ์ธ๊นŒ์ง€๋Š” ๋ฃจํ”„์˜ ์กฐ๊ฑด์„ ํ™•์ธํ•˜๊ณ  i ๊ฐ’์„ ์ฆ๊ฐ€์‹œํ‚ค๋Š” ๋ถ€๋ถ„์ด๋‹ค. ๊ทธ ์œ„์˜ sll๋ถ€ํ„ฐ lw ๋ผ์ธ๊นŒ์ง€๋Š” ๋ ˆ์ง€์Šคํ„ฐ์— save[i] ๊ฐ’์„ ๊ฐ€์ ธ์˜ค๋Š” ๋ถ€๋ถ„์ด๋‹ค.

sll ์ž์ฒด๋Š” control flow์— ์ค‘์š”ํ•œ instruction์ด ์•„๋‹ˆ๊ณ , ๋‹จ์ˆœํžˆ ๊ฐ’์„ left shiftํ•˜๋Š” ๊ธฐ๋Šฅ์„ ํ•œ๋‹ค. $s3์˜ ๊ฐ’์„ 2๋งŒํผ left shiftํ•˜๋ฉด 4๋ฅผ ๊ณฑํ•˜๋Š” ๊ฒƒ๊ณผ ๊ฐ™๋‹ค. ์ด๋Š” $s3 ๊ฐ’์ด 1์ฆ๊ฐ€ํ•  ๋•Œ๋งˆ๋‹ค 4๋ฅผ ๊ณฑํ•จ์œผ๋กœ์จ $s6์— ์ ‘๊ทผํ•˜๋Š” ์ฃผ์†Œ๊ฐ’์„ 4bytes์”ฉ ์˜ฎ๊ธฐ๊ธฐ ์œ„ํ•œ ์ฝ”๋“œ๋‹ค. right shift๋ฅผ ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” srl์„ ์‚ฌ์šฉํ•œ๋‹ค.

MIPS Procedure

procedure๋Š” ํ•จ์ˆ˜๋ฅผ ์˜๋ฏธํ•œ๋‹ค. ์–ด์…ˆ๋ธ”๋ฆฌ ๋ ˆ๋ฒจ์—์„œ ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค๊ณ  ํ˜ธ์ถœํ•˜๋Š” ๊ฒƒ์€ ํ•˜์ด๋ ˆ๋ฒจ ์–ธ์–ด์—์„œ ํ•˜๋˜ ๊ฒƒ๊ณผ๋Š” ๋งŽ์ด ๋‹ค๋ฅด๋‹ค. ์—ฌ๊ธฐ์„œ ๊ฐ€์žฅ ์ค‘์š”ํ•œ ๊ฒƒ์€ ๋ ˆ์ง€์Šคํ„ฐ์˜ ๋ฐฑ์—…๊ณผ ์ ํ”„๋‹ค.

Leaf Procedure

ํ˜ธ์ถœ๋œ ํ•จ์ˆ˜์—์„œ ๋‹ค๋ฅธ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜์ง€ ์•Š๋Š” ํ•จ์ˆ˜, ์ฆ‰ leaf procedure๋ฅผ ๊ฐ€์ •ํ•ด๋ณด์ž:

int leaf_procedure(int a, b, c, d) {
  int e;
  e = (a + b) - (c -d);
  return e;
}

a๋ถ€ํ„ฐ d๊นŒ์ง€๊ฐ€ $a0๋ถ€ํ„ฐ $a3์— ๋Œ€์‘๋˜๊ณ , e๋Š” $s0์— ๋Œ€์‘๋œ๋‹ค๊ณ  ํ•˜๋ฉด MIPS ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

main:
  jal leaf_procedure # leaf_procedure ํ˜ธ์ถœ
  j exit
leaf_procedure:
  addi $sp, $sp, -12 # 4bytes ๋ ˆ์ง€์Šคํ„ฐ 3๊ฐœ ๋ฐฑ์—…์„ ์œ„ํ•ด stack pointer ์œ„์น˜ -12 ์ด๋™
  sw $t1, 8($sp) # 8($sp) = $t1
  sw $t0, 4($sp) # 4($sp) = $t0
  sw $s0, 0($sp) # 0($sp) = $s0
  add $t0, $a0, $a1
  add $t1, $a2, $a3
  sub $s0, $t0, $t1
  add $v0, $s0, $zero
  lw $s0, 0($sp) # $s0 = 0($sp)
  lw $t0, 4($sp) # $t0 = 4($sp)
  lw $t1, 8($sp) # $t1 = 8($sp)
  addi $sp, $sp, 12 # stack pointer ์œ„์น˜ ๋ณต์›
  jr $ra # $ra ์œ„์น˜๋กœ ์ ํ”„
exit:
  ...

โ€ฆ์™œ ์ด๋Ÿฐ ์ง“์„ ํ•˜๋Š”๊ฑธ๊นŒ? ํ•˜๋‚˜์”ฉ ์‚ดํŽด๋ณด์ž.

main:
  jal leaf_procedure # leaf_procedure ํ˜ธ์ถœ
  j exit

๋จผ์ € jal์„ ํ†ตํ•ด leaf_procedure ๋ผ๋ฒจ๋กœ ์ด๋™ํ•œ๋‹ค. ์ด๋•Œ, ๋ ˆ์ง€์Šคํ„ฐ์˜ $ra(return address)๋Š” program counter์˜ ๊ฐ’์„ ๊ฐ€์ ธ์˜จ๋‹ค. program counter๋Š” ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž์‹ ์˜ instruction์„ ์–ด๋””๊นŒ์ง€ ์‹คํ–‰ํ–ˆ๋Š”์ง€ ์ฒดํฌํ•˜๊ธฐ ์œ„ํ•œ ๊ฐ’์ด๋‹ค. ์ด ๊ฒฝ์šฐ $ra๋Š” jal leaf_procedure ๋ฐ”๋กœ ๋‹ค์Œ ๋ผ์ธ j exit๋ฅผ ๊ฐ€๋ฆฌํ‚จ๋‹ค.

leaf_procedure:
  addi $sp, $sp, -12 # 4bytes ๋ ˆ์ง€์Šคํ„ฐ 3๊ฐœ ๋ฐฑ์—…์„ ์œ„ํ•ด stack pointer ์œ„์น˜ -12 ์ด๋™

leaf_proceduer์—์„œ๋Š” ๋จผ์ € ๋ ˆ์ง€์Šคํ„ฐ์˜ $sp(stack pointer)์— 4bytes ๋ ˆ์ง€์Šคํ„ฐ 3๊ฐœ๋ฅผ ๋ฐฑ์—…ํ•˜๊ธฐ ์œ„ํ•ด $sp์— -12๋ฅผ ๋”ํ–ˆ๋‹ค. $sp๋Š” ๋ฉ”๋ชจ๋ฆฌ์˜ ์Šคํƒ์˜ ํŠน์ • ์ฃผ์†Œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋ ˆ์ง€์Šคํ„ฐ์ด๋ฉฐ, ์ด ์œ„์น˜๋ฅผ ์˜ฎ๊ธฐ๋Š” ๊ฒƒ์€ ๋ฐฑ์—…์„ ์œ„ํ•œ ๊ณต๊ฐ„์„ ํ™•๋ณดํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

sw $t1, 8($sp) # 8($sp) = $t1
sw $t0, 4($sp) # 4($sp) = $t0
sw $s0, 0($sp) # 0($sp) = $s0

๊ทธ๋ฆฌ๊ณ  sw๋ฅผ ํ†ตํ•ด $t1, $t0, $s0๋ฅผ $sp์˜ ๊ฐ ๊ณต๊ฐ„์— ๋‹ด์•˜๋‹ค. (ํฐ ๊ฐ’๋ถ€ํ„ฐ ์ ‘๊ทผํ•˜๋Š” ์ด์œ ๋Š” ๋ฉ”๋ชจ๋ฆฌ์˜ ์Šคํƒ ์ฃผ์†Œ๊ฐ€ ํฐ ์ชฝ์—์„œ ์ž‘์€ ์ชฝ์œผ๋กœ ํ–ฅํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.) ์ด๋ ‡๊ฒŒ ํ•˜๋Š” ์ด์œ ๋Š” leaf_procedure๋ฅผ ํ˜ธ์ถœํ•œ caller์ธก(์ด ๊ฒฝ์šฐ main)์—์„œ $t1์ด๋‚˜ $t0, $s0 ๋ ˆ์ง€์Šคํ„ฐ๋ฅผ ์‚ฌ์šฉํ•˜๊ณ  ์žˆ์„ ์ˆ˜๋„ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ๋งŒ์•ฝ ์Šคํƒ์— ๋ฐฑ์—…ํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด caller์—์„œ ์‚ฌ์šฉํ•˜๋˜ ๊ฐ’์„ ๋ฎ์–ด์”Œ์›Œ ๋ฒ„๋ฆด ๊ฒƒ์ด๋‹ค.

add $t0, $a0, $a1
add $t1, $a2, $a3
sub $s0, $t0, $t1
add $v0, $s0, $zero

e = (a + b) - (c -d)์— ํ•ด๋‹นํ•˜๋Š” ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•œ๋‹ค.

lw $s0, 0($sp) # $s0 = 0($sp)
lw $t0, 4($sp) # $t0 = 4($sp)
lw $t1, 8($sp) # $t1 = 8($sp)

lw๋ฅผ ํ†ตํ•ด $sp์— ์ €์žฅํ•œ ๊ฐ’์„ ๋‹ค์‹œ ๋ถˆ๋Ÿฌ์™”๋‹ค. stack pointer๋„ ๋‹ค์‹œ 12bytes ๋‹น๊ฒผ๋‹ค.

jr $ra # $ra ์œ„์น˜๋กœ ์ ํ”„

jr์„ ํ†ตํ•ด caller์— ์œ„์น˜ํ•œ $ra๋กœ ๋Œ์•„๊ฐ€ j exit๋ฅผ ์‹คํ–‰ํ•œ๋‹ค.

์—ฌ๊ธฐ์„œ๋Š” $t1๊ณผ $t0๋„ ๋ฐฑ์—…์„ ํ–ˆ๋Š”๋ฐ, ์‚ฌ์‹ค ์ด๋Ÿด ํ•„์š”๋Š” ์—†๋‹ค. $t ๋ ˆ์ง€์Šคํ„ฐ๋Š” temporary register์ด๊ธฐ ๋•Œ๋ฌธ์— ์–ธ์ œ๋‚˜ ์ž„์‹œ ๊ฐ’๋งŒ ์ €์žฅํ•˜๋„๋ก ์•ฝ์†๋˜์–ด์žˆ๋‹ค. ๋”ฐ๋ผ์„œ $t ๋ ˆ์ง€์Šคํ„ฐ์—๋Š” ๊ฐ’์ด ๋ฎ์–ด์”Œ์›Œ์ ธ๋„ ๋ฌธ์ œ๊ฐ€ ์—†๋„๋ก ์ฝ”๋“œ๋ฅผ ์งœ์•ผํ•œ๋‹ค.

Non-Leaf Procedure

ํ•จ์ˆ˜ ์•ˆ์—์„œ ๋‹ค๋ฅธ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๋Š” non-leaf procedure๋Š” ์–ด๋–จ๊นŒ? ์ด๋ ‡๊ฒŒ ํ˜ธ์ถœ์ด ์ค‘์ฒฉ๋œ ๊ฒฝ์šฐ์—๋Š” $ra์— ์ €์žฅ๋œ callr์˜ ์œ„์น˜๊ฐ€ ๋ฎ์–ด ์”Œ์›Œ์ ธ ๋ฌดํ•œ ๋ฃจํ”„์— ๋น ์งˆ ์œ„ํ—˜์ด ์žˆ๋‹ค. ์ผ๋‹จ ํ•˜์ด๋ ˆ๋ฒจ ์ฝ”๋“œ๋ฅผ ๋ณด์ž:

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

recursiveํ•˜๊ฒŒ ๋™์ž‘ํ•˜๋Š” ํŒฉํ† ๋ฆฌ์–ผ ํ•จ์ˆ˜๋‹ค. n์ด $a0์—, ๊ฒฐ๊ณผ๊ฐ’์ด $v0์— ๋Œ€์‘๋œ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๋ฉด MIPS ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

factorial:
  addi $sp, $sp, -8 # stack pointer ์œ„์น˜ -8 ์ด๋™
  sw $ra, 4($sp)
  sw $a0, 0($sp)
  slti $t0, $a0, 1 # $t0 = ($a0 < 1)
  beq $t0, $zero, L1 # if ($t0 == 0) { goto L1 }
  addi $v0, $zero, 1
  addi $sp, $sp, 8 # stack pointer ์œ„์น˜ 8 ์ด๋™
  jr $ra
L1:
  addi $a0, $a0, -1 # $a -= 1
  jal factorial # factorial($a0)
  lw $a0, 0($sp)
  lw $ra, 4($sp)
  addi $sp, $sp, 8 # stack pointer ์œ„์น˜ 8 ์ด๋™
  mul $v0, $a0, $v0 # $v0 = $a0 * $v0
  jr $ra

๊ต‰์žฅํžˆ ๋ณต์žกํ•ด๋ณด์ด์ง€๋งŒ, ํ•˜๋‚˜์”ฉ ๋œฏ์–ด๋ณด๋ฉดโ€ฆ ์ง„์งœ ๋ณต์žกํ•˜๋‹ค. ์ž‘๋™ ๋ฐฉ์‹์€ ๋Œ€๋žต ์žฌ๊ท€์ ์œผ๋กœ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•˜๋ฉด์„œ stack pointer๋ฅผ ๋ฐ€์–ด๋‚ด๋ฉฐ ๊ฐ’์„ ๋ฐฑ์—…ํ•˜๋‹ค๊ฐ€, ์ดํ›„ ๋‹ค์‹œ stack pointer๋ฅผ ๋‹น๊ธฐ๋ฉฐ ๊ฐ’์„ ๊ฐ€์ ธ์™€ ๊ฒฐ๊ณผ๋ฅผ ๋‚ด๋Š” ์‹์ด๋‹ค. $a0๊ฐ€ 3์ด๋ผ๊ณ  ๊ฐ€์ •ํ•˜๊ณ  ๋ชจ๋“  instruction ๋‹จ๊ณ„๋ฅผ step by step์œผ๋กœ ํ•œ ๋‹จ๊ณ„ ํ•œ ๋‹จ๊ณ„ ์‚ดํŽด๋ณด์ž.

factorial:
  addi $sp, $sp, -8 # stack pointer ์œ„์น˜ -8 ์ด๋™
  sw $ra, 4($sp)
  sw $a0, 0($sp)

๋จผ์ € factorial ํ•จ์ˆ˜์— ์ง„์ž…ํ•ด stack pointer๋ฅผ ์ด๋™์‹œํ‚ค๊ณ  $ra์™€ $a0 ๋ ˆ์ง€์Šคํ„ฐ๋ฅผ ๋ฐฑ์—…ํ–ˆ๋‹ค. ์ด๋•Œ $ra๋Š” factorial ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•œ ์œ„์น˜๊ฐ€ ๋  ๊ฒƒ์ด๊ณ , $a0๋Š” ์•ž์„œ ๊ฐ€์ •ํ•œ 3์ด ๋œ๋‹ค. ์Šคํƒ์˜ ๋ชจ์Šต์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

+--------+------------+
| $a = 3 | caller $ra |
+--------+------------+

์ด์ œ ๋‹ค์Œ ๋ผ์ธ์„ ๋ณด์ž:

slti $t0, $a0, 1 # $t0 = ($a0 < 1)
beq $t0, $zero, L1 # if ($t0 == 0) { goto L1 }

$a0๊ฐ€ 1๋ณด๋‹ค ์ž‘์€์ง€ ํ™•์ธํ•˜๊ณ , ๊ทธ ๋ฐ˜ํ™˜ ๊ฐ’์„ $t0์— ์ €์žฅํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  $t0๊ฐ€ $zero์™€ ๊ฐ™์€์ง€ ํ™•์ธํ•ด ๊ฐ’์ด ๊ฐ™๋‹ค๋ฉด L1 ๋ผ๋ฒจ๋กœ ์ด๋™ํ•œ๋‹ค. ์ด๋•Œ $a0๋Š” 3์ด๊ธฐ ๋•Œ๋ฌธ์— 1๋ณด๋‹ค ์ž‘์ง€ ์•Š๋‹ค. ๋”ฐ๋ผ์„œ $t0๋Š” 0์ด ๋˜๊ณ , beq๋ฅผ ๋งŒ์กฑํ•ด L1์œผ๋กœ ๋„˜์–ด๊ฐ„๋‹ค.

L1:
  addi $a0, $a0, -1 # $a -= 1
  jal factorial # factorial($a0)

L1์€ ํ•˜์ด๋ ˆ๋ฒจ ์ฝ”๋“œ์—์„œ return n * factorial(n - 1);์— ํ•ด๋‹นํ•˜๋Š” ๋™์ž‘์„ ์ •์˜ํ•œ๋‹ค. ๋จผ์ € $a0์—์„œ 1์„ ๋บ€๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‹ค์‹œ factorial ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•œ๋‹ค.

factorial:
  addi $sp, $sp, -8 # stack pointer ์œ„์น˜ -8 ์ด๋™
  sw $ra, 4($sp)
  sw $a0, 0($sp)

factorial์€ $sp๋ฅผ ๋‹ค์‹œ -8 ์ด๋™ํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  $ra์™€ $a0๋ฅผ ๋ฐฑ์—…ํ•œ๋‹ค. ์ด๋•Œ $ra๋Š” ์•ž์„œ ์‹คํ–‰ํ•œ L1์˜ jal factorial์˜ ๋ฐ”๋กœ ๋‹ค์Œ ๋ผ์ธ์ด๊ณ , $a0๋Š” 2๊ฐ€ ๋œ๋‹ค. ํ˜„์žฌ ์Šคํƒ์— ์ €์žฅ๋œ ๋ ˆ์ง€์Šคํ„ฐ ๊ฐ’์„ ํ‘œํ˜„ํ•˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

+--------+------------+--------+--------+
| $a = 3 | caller $ra | $a = 2 | L1 $ra |
+--------+------------+--------+--------+

์ด์–ด์„œ ๋‹ค์Œ ๋ผ์ธ์„ ์‚ดํŽด๋ณด์ž:

slti $t0, $a0, 1 # $t0 = ($a0 < 1)
beq $t0, $zero, L1 # if ($t0 == 0) { goto L1 }

$a0๊ฐ€ 2์ด๋ฏ€๋กœ 1๋ณด๋‹ค ์ž‘์ง€ ์•Š๋‹ค. $t0๊ฐ€ 0์ด ๋˜๊ณ , beq๋ฅผ ๋งŒ์กฑํ•ด ๋‹ค์‹œ L1์œผ๋กœ ๋„˜์–ด๊ฐ„๋‹ค.

L1:
  addi $a0, $a0, -1 # $a -= 1
  jal factorial # factorial($a0)

L1์€ ์•„๊นŒ์™€ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ $a์—์„œ 1์„ ๋นผ 1๋กœ ๋งŒ๋“ค๊ณ , ๋‹ค์‹œ factorial๋กœ ๋„˜์–ด๊ฐ„๋‹ค.

factorial:
  addi $sp, $sp, -8 # stack pointer ์œ„์น˜ -8 ์ด๋™
  sw $ra, 4($sp)
  sw $a0, 0($sp)

factorial์—์„œ๋Š” $sp๋ฅผ ๋‹ค์‹œ -8 ์ด๋™ํ•œ๋‹ค. ์ด๋•Œ ๋ฐฑ์—…๋˜๋Š” $ra๋Š” ์•ž์„œ ์‹คํ–‰ํ•œ L1์˜ jal factorial์˜ ๋ฐ”๋กœ ๋‹ค์Œ ๋ผ์ธ์ด๊ณ , $a0๋Š” 1์ด๋‹ค. ํ˜„์žฌ ์Šคํƒ์— ์ €์žฅ๋œ ๋ ˆ์ง€์Šคํ„ฐ ๊ฐ’์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

+--------+------------+--------+--------+--------+--------+
| $a = 3 | caller $ra | $a = 2 | L1 $ra | $a = 1 | L1 $ra |
+--------+------------+--------+--------+--------+--------+

๋‹ค์Œ ๋ผ์ธ์œผ๋กœ ๋„˜์–ด๊ฐ€์ž:

slti $t0, $a0, 1 # $t0 = ($a0 < 1)
beq $t0, $zero, L1 # if ($t0 == 0) { goto L1 }

์—ฌ์ „ํžˆ $a0๊ฐ€ 1์ด๋ฏ€๋กœ 1๋ณด๋‹ค ์ž‘์ง€ ์•Š๊ณ , beq๋ฅผ ๋งŒ์กฑํ•ด L1์œผ๋กœ ๋„˜์–ด๊ฐ„๋‹ค.

L1:
  addi $a0, $a0, -1 # $a -= 1
  jal factorial # factorial($a0)

L1์€ $a์—์„œ 1์„ ๋นผ 0์œผ๋กœ ๋งŒ๋“ค๊ณ , factorial๋กœ ๋„˜์–ด๊ฐ„๋‹ค.

factorial:
  addi $sp, $sp, -8 # stack pointer ์œ„์น˜ -8 ์ด๋™
  sw $ra, 4($sp)
  sw $a0, 0($sp)

factorial์—์„œ๋Š” ๋˜ ๋‹ค์‹œ $sp๋ฅผ -8 ์ด๋™ํ•œ๋‹ค. ์ด๋•Œ ๋ฐฑ์—…๋˜๋Š” $ra๋Š” ์•ž์„œ ์‹คํ–‰ํ•œ L1์˜ jal factorial์˜ ๋ฐ”๋กœ ๋‹ค์Œ ๋ผ์ธ์ด๊ณ , $a0๋Š” 0์ด๋‹ค. ํ˜„์žฌ ์Šคํƒ์— ์ €์žฅ๋œ ๋ ˆ์ง€์Šคํ„ฐ ๊ฐ’์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

+--------+------------+--------+--------+--------+--------+--------+--------+
| $a = 3 | caller $ra | $a = 2 | L1 $ra | $a = 1 | L1 $ra | $a = 0 | L1 $ra |
+--------+------------+--------+--------+--------+--------+--------+--------+

๋‹ค์Œ ๋ผ์ธ์„ ๋ณด์ž:

slti $t0, $a0, 1 # $t0 = ($a0 < 1)
beq $t0, $zero, L1 # if ($t0 == 0) { goto L1 }

์ด์   $a0๊ฐ€ 0์ด๋ฏ€๋กœ 1๋ณด๋‹ค ์ž‘์•„ $t0๊ฐ€ 1์ด ๋œ๋‹ค. beq๋ฅผ ๋งŒ์กฑํ•˜์ง€ ์•Š์œผ๋ฏ€๋กœ L1์œผ๋กœ ๋„˜์–ด๊ฐ€์ง€ ์•Š๊ณ  ๋‹ค์Œ ๋ผ์ธ์„ ์‹คํ–‰ํ•œ๋‹ค. (์—ฌ๊ธฐ๊นŒ์ง€ ํ˜ธ์ถœ ๊ณผ์ •์ด์—ˆ๊ณ , ์ด์ œ๋Š” ๋ฐ˜ํ™˜ ๊ฐ’์„ ๋ฐ›์•„์˜ค๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.)

addi $v0, $zero, 1
addi $sp, $sp, 8 # stack pointer ์œ„์น˜ 8 ์ด๋™
jr $ra

$v0์— 0์— 1์„ ๋”ํ•œ ๊ฐ’, ์ฆ‰ 1์„ ์ €์žฅํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  stack pointer ์œ„์น˜๋ฅผ 8๋งŒํผ ๋‹น๊ธฐ๊ณ  $ra ์œ„์น˜๋กœ ๋„˜์–ด๊ฐ„๋‹ค. ์ด๋•Œ $ra๋Š” L1 $ra ์œ„์น˜๋‹ค.

+--------+------------+--------+--------+--------+--------+
| $a = 3 | caller $ra | $a = 2 | L1 $ra | $a = 1 | L1 $ra |
+--------+------------+--------+--------+--------+--------+

stack pointer ์œ„์น˜๋ฅผ 8๋งŒํผ ๋‹น๊ฒผ์œผ๋‹ˆ ์Šคํƒ์˜ ๋ชจ์Šต์€ ์œ„์™€ ๊ฐ™์ด ๋œ๋‹ค.

lw $a0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8 # stack pointer ์œ„์น˜ 8 ์ด๋™
mul $v0, $a0, $v0 # $v0 = $a0 * $v0
jr $ra

์Šคํƒ์—์„œ $a0 ๊ฐ’๊ณผ $ra ๊ฐ’์„ ๊ฐ€์ ธ์˜จ๋‹ค. ์•ž์„  ์Šคํƒ์˜ ๋ชจ์Šต์„ ํ™•์ธํ•ด๋ณด๋ฉด $a0๊ฐ€ 1์ด๊ณ  $ra๋Š” L1 $ra ์œ„์น˜๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‹ค์‹œ stack pointer์˜ ์œ„์น˜๋ฅผ 8 ์›€์ง์ธ๋‹ค.

+--------+------------+--------+--------+
| $a = 3 | caller $ra | $a = 2 | L1 $ra |
+--------+------------+--------+--------+

์ด์–ด์„œ $v0์— $a0 * $v0, ์ฆ‰ 2 * 1 ๊ฐ’์„ ์ €์žฅํ•˜๊ณ , $ra ์œ„์น˜๋กœ ๋„˜์–ด๊ฐ„๋‹ค. $ra๋Š” ์—ฌ์ „ํžˆ L1 $ra ์œ„์น˜๋‹ค.

lw $a0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8 # stack pointer ์œ„์น˜ 8 ์ด๋™
mul $v0, $a0, $v0 # $v0 = $a0 * $v0
jr $ra

์•ž์„  ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค. $a0์™€ $ra๋ฅผ ๋ณต์›ํ•œ๋‹ค. ์ด์ œ $a0๊ฐ€ 2์ด๊ณ  $ra๋Š” L1 $ra ์œ„์น˜๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‹ค์‹œ stack pointer์˜ ์œ„์น˜๋ฅผ 8 ์›€์ง์ธ๋‹ค.

+--------+------------+
| $a = 3 | caller $ra |
+--------+------------+

๊ทธ๋ฆฌ๊ณ  $v0์— $a0 * $v0, ์ฆ‰ 2 * 2 ๊ฐ’์„ ์ €์žฅํ•˜๊ณ , $ra ์œ„์น˜๋กœ ๋„˜์–ด๊ฐ„๋‹ค. $ra ๋Š” L1 $ra ์œ„์น˜๋‹ค.

lw $a0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8 # stack pointer ์œ„์น˜ 8 ์ด๋™
mul $v0, $a0, $v0 # $v0 = $a0 * $v0
jr $ra

์ด์ œ ๋งˆ์ง€๋ง‰ ๋‹จ๊ณ„๋‹ค. ์Šคํƒ์—์„œ $a0์™€ $ra๋ฅผ ๊ฐ€์ ธ์˜จ๋‹ค. ์ด์ œ $a0๊ฐ€ 3์ด๊ณ  $ra๋Š” caller $ra ์œ„์น˜๋‹ค. ๋‹ค์‹œ stack pointer์˜ ์œ„์น˜๋ฅผ 8 ์›€์ง์ด๋ฉด ์ด์ œ stack pointer๋ฅผ ์ดˆ๊ธฐ ๊ฐ’์œผ๋กœ ๋Œ๋ ค๋†“๊ฒŒ ๋œ๋‹ค.

$v0์— $a0 * $v0, ์ฆ‰ 3 * 2 ๊ฐ’์„ ์ €์žฅํ•˜๊ณ , $ra ์œ„์น˜๋กœ ๋„˜์–ด๊ฐ„๋‹ค. ์ด๋•Œ $ra๋Š” caller ์œ„์น˜์ด๋ฉฐ, caller์—์„œ $v0์— ์ ‘๊ทผํ•˜๋ฉด 6์„ ์–ป์„ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค. factorial์ด ์ œ๋Œ€๋กœ ๋™์ž‘ํ–ˆ๋‹ค.

๋งˆ์น˜ ์ธ๊ฐ„ ์ปดํ“จํ„ฐ๊ฐ€ ๋œ ๊ธฐ๋ถ„์ด๋‹ค.

Memory Layout

์ปดํ“จํ„ฐ ๋ฉ”๋ชจ๋ฆฌ ๋ ˆ์ด์•„์›ƒ. ์Šคํƒ, ํž™, ๋ฐ์ดํ„ฐ ์„ธ๊ทธ๋จผํŠธ, ์ฝ”๋“œ ์„ธ๊ทธ๋จผํŠธ.

๊ทธ๋ฆผ์˜ Code Segment๋Š” Text๋ผ๊ณ  ๋ถˆ๋ฆฌ๋ฉฐ, ์‹ค์ œ ํ”„๋กœ๊ทธ๋žจ ์ฝ”๋“œ๊ฐ€ ์ €์žฅ๋œ๋‹ค. Data Segment๋Š” Static Data๋ผ๊ณ  ๋ถˆ๋ฆฌ๋ฉฐ, ์ƒ์ˆ˜ ๋ฐฐ์—ด์ด๋‚˜ ๋ฌธ์ž์—ด, static ๋ณ€์ˆ˜๊ฐ€ ์ €์žฅ๋œ๋‹ค. Heap์—๋Š” ๋™์ ํ• ๋‹น๋œ ๋ฐฐ์—ด ์š”์†Œ๋‚˜ ๊ฐ์ฒด๊ฐ€ ์ €์žฅ๋˜๋ฉฐ, Stack์—๋Š” ํ•จ์ˆ˜๋‚˜ ๋ฉ”์†Œ๋“œ, ์ง€์—ญ๋ณ€์ˆ˜ ๋“ฑ์ด ์ €์žฅ๋œ๋‹ค.

์•ž์„œ ์Šคํƒ์— ๊ฐ’์„ ์ €์žฅํ•˜๊ณ  ๋ถˆ๋Ÿฌ์˜ค๋Š” ๊ณผ์ •์ด ์œ„์™€ ๊ฐ™์€ ๋ฉ”๋ชจ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ์ด๋ค„์ง„๋‹ค. ์Šคํƒ์€ ๋†’์€ ๊ณณ์—์„œ ๋‚ฎ์€ ๊ณณ์œผ๋กœ ์ž๋ผ๊ธฐ ๋•Œ๋ฌธ์— addi $sp, $sp, -8์ฒ˜๋Ÿผ stack poniter๋ฅผ ์Œ์˜ ๋ฐฉํ–ฅ์œผ๋กœ ์›€์ง์—ฌ์ค€ ๊ฒƒ์ด๋‹ค. ๊ฐ’์„ ์ €์žฅํ•  ๋•Œ๋„ sw $ra 4($sp)๋‹ค์Œ sw $a0, 0($sp)๋ฅผ ํ–ˆ๋‹ค. ์Šคํƒ๊ณผ ๋‹ฌ๋ฆฌ heap์€ ๋‚ฎ์€ ๊ณณ์—์„œ ๋†’์€ ๊ณณ์œผ๋กœ ์ž๋ž€๋‹ค.

MIPS Instruction Formats

MIPS์—์„œ ์–ด์…ˆ๋ธ”๋Ÿฌ๊ฐ€ ํ•œ ์ค„์”ฉ instruction์„ ์ฝ๊ณ  ์ด๋ฅผ ๊ธฐ๊ณ„์–ด๋กœ ๋ณ€ํ™˜ํ•  ๋•Œ, ๊ธฐ๊ณ„์–ด๋ฅผ ํ‘œํ˜„ํ•˜๋Š” ์„ธ๊ฐ€์ง€ ํ˜•์‹ R(Register), I(Immediate), J(Jump)๊ฐ€ ์žˆ๋‹ค.

R-format

R-format์€ ๋ ˆ์ง€์Šคํ„ฐ๋ฅผ ์ด์šฉํ•ด ์—ฐ์‚ฐํ•˜๋Š” instruction์„ ๋‹ด๋Š” ํ˜•์‹์ด๋‹ค.

+----+----+----+----+-------+-------+
| op | rs | rt | rd | shamt | funct | 
+----+----+----+----+-------+-------+
  • op(6bits): ํฌ๋งท๊ณผ ๋™์ž‘์„ ๊ตฌ๋ถ„ํ•˜๋Š” ํ•„๋“œ.
  • rs(5bits): first source register number
  • rt(5bits): second source register number
  • rd(5bits): destination register number
  • shamt(5bits): shift ์—ฐ์‚ฐ์— ์‚ฌ์šฉ๋˜๋Š” ํ•„๋“œ.
  • funct(6bits): op๋ณด๋‹ค ๊ตฌ์ฒด์ ์ธ ์ •๋ณด๋ฅผ ๋‹ด์€ ํ•„๋“œ.

๋งŒ์•ฝ ๋‹ค์Œ๊ณผ ๊ฐ™์€ MIPS ์ฝ”๋“œ๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•ด๋ณด์ž:

add $t0, $s1, $s2

์ด๋ฅผ R-format์œผ๋กœ ํ‘œํ˜„ํ•˜๋ฉด ์ด๋ ‡๊ฒŒ ๋  ๊ฒƒ์ด๋‹ค:

+---------+-----+-----+-----+---+-----+
| special | $s1 | $s2 | $t0 | 0 | add | 
+---------+-----+-----+-----+---+-----+

register table์— ๋”ฐ๋ผ ์ด๊ฒƒ์„ 10์ง„์ˆ˜๋กœ ๋ณ€ํ™˜ํ•˜๋ฉด:

+---+----+----+---+---+----+
| 0 | 17 | 18 | 8 | 0 | 32 | 
+---+----+----+---+---+----+

๊ฐ ๋ ˆ์ง€์Šคํ„ฐ์˜ ๊ฐ’๊ณผ add instruction์˜ opcode, funct ๊ฐ’, rs, rt, rd ์œ„์น˜ ๋“ฑ์€ ๋ชจ๋‘ ์‚ฌ์ „์— ์ •์˜๋œ ๊ฒƒ์œผ๋กœ, MIPS Green Sheet๋ฅผ ์ฐธ๊ณ ํ•˜๋ฉด ๋œ๋‹ค. ์ด์–ด์„œ ๊ฐ ํ•„๋“œ๋ฅผ 2์ง„์ˆ˜๋กœ ๋ฐ”๊พธ๋ฉด ์‹ค์ œ ๋ฉ”๋ชจ๋ฆฌ์— ๋“ค์–ด๊ฐ€๋Š” ๊ฐ’์ด ๋œ๋‹ค:

00000010001100100100000000100000

์ปดํ“จํ„ฐ๋Š” ์ด๋ ‡๊ฒŒ ๋ณ€ํ™˜๋œ ๋ฐ”์ด๋„ˆ๋ฆฌ ์ˆซ์ž๋ฅผ ๋ณด๊ณ  ๋ช…๋ น์„ ์ˆ˜ํ–‰ํ•œ๋‹ค.

์ด๋ ‡๊ฒŒ ๋ณด๋ฉด ๋ฐ”๋กœ funct๋ฅผ ํ™•์ธํ•˜๋ฉด ๋˜๋‹ˆ๊นŒ op๊ฐ€ ํ•„์š”ํ•˜์ง€ ์•Š์„ ๊ฒƒ ๊ฐ™๋‹ค. ์‚ฌ์‹ค 32bit ์‹œ์Šคํ…œ์—์„œ ์‰ฝ๊ฒŒ instruction์„ ์ฝ๊ธฐ ์œ„ํ•ด 32๋น„ํŠธ๋ฅผ ๋งž์ถ”๋Š” ๊ฒƒ์ด ๋ณต์žก๋„๋ฅผ ์ค„์ด๋Š” ๋ฐ ๋„์›€์ด ๋˜๊ธฐ ๋•Œ๋ฌธ์— ๋ฉ”๋ชจ๋ฆฌ ์†ํ•ด๋ฅผ ๊ฐ์•ˆํ•œ ๊ฒƒ์ด๋‹ค.

I-format

I-format์€ ์ƒ์ˆ˜ ์—ฐ์‚ฐ๊ณผ ๋ฉ”๋ชจ๋ฆฌ ์—ฐ์‚ฐ์„ ์œ„ํ•ด ์‚ฌ์šฉ๋œ๋‹ค.

+----+----+----+-----+
| op | rs | rt | IMM |  
+----+----+----+-----+
  • op(6bits): ํฌ๋งท๊ณผ ๋™์ž‘์„ ๊ตฌ๋ถ„ํ•˜๋Š” ํ•„๋“œ.
  • rs(5bits), rt(5bits): source or destination register number
  • IMM(16bits): constant๋‚˜ address๊ฐ€ ๋‹ด๊ธด๋‹ค. constant์˜ ๊ฒฝ์šฐ -215๋ถ€ํ„ฐ 215 - 1๊นŒ์ง€์˜ ์ƒ์ˆ˜๋ฅผ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋‹ค. address์˜ ๊ฒฝ์šฐ rs์˜ base address์— offset์œผ๋กœ ๊ธฐ๋Šฅํ•˜๊ฑฐ๋‚˜ ์ ํ”„ํ•ด์•ผ ํ•˜๋Š” instruction๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ €์žฅํ•œ๋‹ค.

J-format

J-format์€ ๋‹ค๋ฅธ ์œ„์น˜๋กœ ์ ํ”„ํ•  ๋•Œ ์‚ฌ์šฉ๋˜๋Š” ํฌ๋งท์ด๋‹ค.

+----+----------------+
| op | pseudo-address |
+----+----------------+
  • op(6bits): ํฌ๋งท๊ณผ ๋™์ž‘์„ ๊ตฌ๋ถ„ํ•˜๋Š” ํ•„๋“œ.
  • pseudo-address(26bits): ์ ํ”„ํ•  instruction์˜ ๋ณ€ํ™˜๋œ ์ฃผ์†Œ๊ฐ€ ๋‹ด๊ธฐ๋Š” ํ•„๋“œ.

MIPS Addressing for 32-bit Immediates and Addresses

MIPS instruction format ์ค‘ I-format์€ bne $t0, $s5, Exit์™€ ๊ฐ™์€ ๊ตฌ๋ฌธ์„ ํ‘œํ˜„ํ•  ๋•Œ๋„ ์‚ฌ์šฉ๋œ๋‹ค. ๊ทธ๋Ÿฐ๋ฐ I-foramt์˜ ๋งˆ์ง€๋ง‰ ํ•„๋“œ์ธ constant or address๋Š” 16bits๋ฐ–์— ๋˜์ง€ ์•Š์•„ Exit์—์„œ ์ˆ˜ํ–‰๋  ๋™์ž‘ ์ „์ฒด๋ฅผ ๋‹ด๋Š” ๊ฒƒ์€ ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค. ๋”ฐ๋ผ์„œ ์ด๊ณณ์—๋Š” Exit๊ฐ€ ๋ช‡ ์ค„ ๋–จ์–ด์ ธ ์žˆ๋Š”์ง€๋ฅผ ์ €์žฅํ•œ๋‹ค. ์•ž์„œ ํ™œ์šฉํ•œ Loop ์ฝ”๋“œ๋ฅผ ๋‹ค์‹œ ๋ณด์ž:

Loop:                 # address: 8000
  sll $t1, $s3, 2     # R-format: | 0  | 0  | 19 | 9 | 4 | 0  |
  add $t1, $t1, $s6   # R-format: | 0  | 9  | 22 | 9 | 0 | 32 |
  lw $t0, 0($t1)      # I-format: | 35 | 9  | 8  |     0      |
  bne $t0, $s5, Exit  # I-format: | 5  | 8  | 21 |     2      |
  addi $s3, $s3, 1    # I-format: | 8  | 19 | 19 |     1      |
  j Loop              # J-format: | 2  |         2000         |
Exit:
  ...

์—ฌ๊ธฐ์„œ bne $t0, $s5, Exit ๋ผ์ธ์˜ I-format์„ ๋ณด์ž. constant or address์— 2๊ฐ€ ์žˆ๋Š” ๊ฒƒ์„ ๋ณผ ์ˆ˜ ์žˆ๋Š”๋ฐ, ์ด๋Š” Exit๊ฐ€ ํ•ด๋‹น ๋ผ์ธ์—์„œ 2์นธ ๋–จ์–ด์ ธ ์žˆ๋‹ค๋Š” ์˜๋ฏธ๋‹ค.

J-format์˜ ๊ฒฝ์šฐ๋„ pseudo-address ํ•„๋“œ๊ฐ€ 26bits๋ฐ–์— ๋˜์ง€ ์•Š์•„ ๋ชจ๋“  instruction์„ ๋‹ด์„ ์ˆ˜ ์—†๋‹ค. J-format์˜ pseudo-address ํ•„๋“œ์—๋Š” ์ ํ”„ํ•ด์•ผ ํ•˜๋Š” ์œ„์น˜์˜ ์ฃผ์†Œ๋ฅผ 2๋งŒํผ right shiftํ•œ ๊ฐ’์ด ๋“ค์–ด๊ฐ„๋‹ค. ์œ„ ์ฝ”๋“œ์—์„œ j Loop ๋ผ์ธ์˜ J-format์„ ๋ณด์ž. pseudo-address ํ•„๋“œ์— 2000์ด ์žˆ๋Š”๋ฐ, ์ ํ”„ํ•ด์•ผ ํ•˜๋Š” Loop์˜ address๋Š” 8000์ด๋‹ค. ์ด๋•Œ 2000์— 2๋งŒํผ left shift(2000 << 2)ํ•˜๋ฉด 8000์„ ์–ป์„ ์ˆ˜ ์žˆ๋‹ค.

์œ„์™€ ๊ฐ™์€ ๋งค์ปค๋‹ˆ์ฆ˜์„ ์ˆ˜ํ–‰ํ•˜๊ธฐ ์œ„ํ•ด ์–ด์…ˆ๋ธ”๋Ÿฌ๋Š” ๊ตฌ์ฒด์ ์ธ instruction์„ ๊ธฐ๊ณ„์–ด๋กœ ๋ณ€ํ™˜ํ•˜๊ธฐ ์ „ ์ฝ”๋“œ ์ „์ฒด๋ฅผ ์Šค์บ”ํ•ด ๋ผ๋ฒจ์˜ ์œ„์น˜๋ฅผ ํŒŒ์•…ํ•œ๋‹ค. ์ดํ›„ ์ˆœ์„œ๋Œ€๋กœ instruction์„ ์ฝ์œผ๋ฉฐ ๊ธฐ๊ณ„์–ด๋กœ ๋ณ€ํ™˜ํ•˜๋‹ค๊ฐ€ ์ ํ”„ํ•ด์•ผ ํ•˜๋Š” ๋ถ€๋ถ„์ด ๋‚˜์˜ค๋ฉด ๊ทธ ๋ถ€๋ถ„์˜ instruction์„ ๊ธฐ๊ณ„์–ด๋กœ ๋ณ€ํ™˜ํ•œ๋‹ค. ์ด๋Ÿฐ ์‹์œผ๋กœ ๋ชจ๋“  instruction์„ ์ˆœ์„œ์— ๋งž์ถฐ ๊ธฐ๊ณ„์–ด๋กœ ๋ณ€ํ™˜ํ•˜๋ฉด ๋น„๋กœ์†Œ ์ปดํ“จํ„ฐ๊ฐ€ ์ดํ•ดํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฐ๊ณผ๋ฌผ์ด ๋‚˜์˜จ๋‹ค.

์—ฌ๊ธฐ๊นŒ์ง€๊ฐ€ MIPS instruction์— ๋Œ€ํ•œ ๊ธฐ๋ณธ์ ์ธ ๋‚ด์šฉ์ด๋‹ค. ๋” ๋“ค์–ด๊ฐ€๋ฉด ํ”„๋กœ์„ธ์„œ, ๋ฉ”๋ชจ๋ฆฌ์˜ ๋™์ž‘์ด๋‚˜ ๋””์ง€ํ„ธ ํšŒ๋กœ๋ฅผ ์ด์šฉํ•œ ๋ฐ”์ด๋„ˆ๋ฆฌ ์—ฐ์‚ฐ์— ๋Œ€ํ•œ ๋‚ด์šฉ๋„ ๋‹ค๋ฃฐ ์ˆ˜ ์žˆ์„ ๊ฒƒ ๊ฐ™์€๋ฐ, ์ผ๋‹จ์€ ์ปดํ“จํ„ฐ ์•„ํ‚คํ…์ฒ˜์˜ ๊ฐœ์š”์™€ ์ปดํ“จํ„ฐ๊ฐ€ ์ฝ”๋“œ๋ฅผ ํ•ด์„ํ•˜๊ณ  ์‹คํ–‰ํ•˜๋Š” ๊ณผ์ •๋งŒ์„ ์‚ดํŽด๋ดค๋‹ค.