컴퓨터 구조 및 설계 6판 내용정리 Chapter2. 명령어: 컴퓨터언어(96P -121P)

수업에서 다룬 내용 위주로 정리

컴퓨터 구조 및 설계 6판 chapter2. 명령어: 컴퓨터 언어 96P -121P

 

목차

명령어의 컴퓨터 내부 표현

MIPS R-format

MIPS I-format

논리 연산 명령어

조건부 연산

프로시저

Leaf 프로시저

Non-Leaf 프로시저

새 데이터를 위한 스택의 공간 할당

새 데이터를 위한 힙의 공간 할당

---

명령어의 컴퓨터 내부 표현

• 명령어는 이진수로 인코딩 되어 있고, 기계 코드라고 불림
• 모든 명령어는 레지스터를 사용해서, 레지스터 이름을 숫자로 매핑하는 규칙이 있어야 함
• MIPS 명령어의 길이는 데이터 워드와 마찬가지로 32bit
  • MIPS에서는 레지스터 $s0 ~ $s7 : 레지스터 번호 16~23
  • $t0 ~ $t7: 레지스터 번호 8~15
  • $t8 ~ $t9: 레지스터 번호 24-25
  • $zero : 레지스터 0

16진수 Hexadecimal

• 모든 컴퓨터의 데이터 길이는 4의 배수이므로 16진수가 많이 사용됨
• 16진수를 2진수로 변환하면 다음과 같음

1	0001	5	0101	9	1001	d	1101
2	0010	6	0110	a	1010	e	1110
3	0011	7	0111	b	1011	f	1111

MIPS R-format 명령어

• op: operation code (opcode) 명령어가 실행할 연산의 종류, 연산자
• rs: 첫번째 근원지(source) 피연산자 레지스터 주소
• rt: 두번째 근원지 피연산자 레지스터 주소
• rd: 목적지(destination) 레지스터 주소, 연산 결과가 기억됨
• shamt: shift amount 자리이동 량 (사용전에는 00000 으로 채움)
• funct: 기능(function) code, op 필드에서 연산의 종류를 표시하고 funct 필드에서 그중의 한 연산을 구체적으로 지정. 기능코드 (function code) 라고 부르기도함

Example

 

MIPS I-format 명령어

• 수치 연산과 데이터 전송 명령어에서 사용 (load, store)
• rt: 목적지(destination)나 근원지(source)의 레지스터 번호
• constant: 범위가 (-2의 15승) ~ (2의 15승 -1)
• address: rs의 base register에 offset을 더한 값

모든 명령어의 길이는 같게 하되, 명령어 종류에 따라 형식을 다르게 함

⇒ 설계 원칙 4: 좋은 설계에는 적당한 절충안이 필요함

Example

A[300] = h + A[300];

($t1에 배열 A의 시작 주소가 기억되어 있고, $s2는 변수 h에 대응됨)

컴파일 하면, 다음과 같음

lw $t0, 1200($t1) # 임시변수 $t0에 A[300] 넣기 
add $t0, $s2, $t0 # $t0에 h + A[300] 넣기
sw $t0, 1200($t1) # h + A[300]을 A[300]에 다시 넣기

위를 차례로 십진수로 표현하면 다음과 같음

한줄씩 살펴보면

line 1. lw op 필드 값은 35, rs 필드에는 베이스 레지스터 번호 9($t1), rt 필드에는 목적지 레지스터 번호 8($t0), A[300]을 선택하기 위한 변위값 (300*4=1200)은 마지막 필드 adress.

line 2. add op 필드 값은 0, funct 필드 값은 32, 레지스터 피연산자 3개 (각 18, 8, 8) 각각 2,3,4 번째 필드에서 $s2, $t0, $t0에 대응됨

line 3. sw op 필드 값은 43, 나머지는 lw와 동일함

위 명령어를 이진수로 표현하면 다음과 같음

명령어에 따른 표 https://opencores.org/projects/plasma/opcodes

Stored Program Computers 내장 프로그램 컴퓨터

오늘날의 컴퓨터는 두가지 원리에 바탕을 두고 있음

• 명령어는 숫자로 표현됨
• 프로그램(명령어, 데이터)은 메모리에 기억되어 있어서 데이터처럼 읽고 쓸 수 있음

+) 프로그램은 프로그램에서 작동 가능 (컴파일러, 링커 ,,,) , ㅏ이너리 호환성을 통해 컴파일된 프로그램이 다른 컴퓨터에서 작동가능 (표준화된 ISA,,)

Logical Operations 논리 연산 명령어

비트를 워드로 묶는 packing 작업과 워드를 비트 단위로 나누는 unpacking 작업을 간단하게 하는 명령어들이 프로그래밍 언어와 명령어 집합에 추가됨 → 논리 연산 명령어

C와 Java의 논리 연산자와 이에 해당하는 MIPS 명령어

MIPS 자리 이동 (shift) 명령어

워드 내의 모든 비트를 왼쪽 또는 오른쪽으로 이동시키고, 이동 후 빈자리는 0으로 채움

R 형식 명령어의 shamt: 자리이동량 shift amount

sll: shift left logical 왼쪽 자리 이동

• 왼쪽으로 자리 이동, 0으로 채움
• 왼쪽으로 i비트 자리이동하면 2의 i승을 곱한것과 같음

srl: shift right logical 오른쪽 자리 이동

• 오른쪽으로 자리 이동, 0으로 채움
• 오른쪽으로 i비트 자리이동하면 2의 i승으로 나눈것과 같음

Example

sll $t2, $s0, 4 (원래 값은 $s0에 있고, 결과는 $t2 레지스터에 저장된다고 가정)

위의 명령어는 reg $t2 = reg $s0 << 4bits

sll은 op 코드와 funct 필드가 0, rd는 10($t2), rt는 16($s0), shamt는 4, rs는 사용하지 않으므로 0

0 (op)0 (rs)16 (rt)10 (rd)4 (shamt)0 (funct)

---

AND 연산

비트 대 비트 연산자로서, 비트값이 모두 1일 경우만 결과가 1, 나머지는 0으로 처리함 → 일부 비트를 감추는 역할을 하기에 마스크(mask) 라고 부름

Example

and $t0, $t1, $t2 # reg $t0 = reg $t1 & reg $t2

$t2 0000 1101 1100

$t1 0011 1100 0000

레지스터가 위와 같은 값이 있을 때, 위의 and 연산을 수행하면 $t0은 다음과 같은 결과가 된다.

$t0 0000 1100 0000

---

OR 연산

비트 대 비트 연산자로 두 비트 중 하나만 1이면 결과가 1이 되는 것, 나머지는 그대로 냅둠

Example

or $t0, $t1, $t2 # reg $t0 = reg $t1 | reg $t2

$t2 0000 1101 1100

$t1 0011 1100 0000

레지스터 값이 위와 같을 때, 위의 연산을 수행시 $t0은 다음과 같음

$t0 0011 1101 1100

---

NOT 연산

피연산자 하나를 받아서 피연산자의 비트가 1이면 결과비트를 0으로, 0이면 1로 만듬 → 거꾸로

• MIPS의 3-피연산자 형식 유지를 위해 NOT 대신 NOR(NOT OR) 명령어를 포함시킴
  • 피 연산자 하나가 0이면 NOT과 같아짐.
  • ex) a NOR b = NOT (a OR b)

NOR : 피연산자 2개, 두 피연산자를 논리 OR한 값을 다시 NOT함

Example

$t1 0011 1100 0000

$t1이 위와 같을때

nor $t0, $t1, $zero # reg $t0 ~ ($t1 | $zero )

nor 연산 수행시

$t1 or $zero 수행시 0011 1100 0000

위의 연산 not 수행시 1100 0011 1111

즉, $t0 1100 0011 1111

Conditional Operations 조건부 연산

컴퓨터는 단순한 계산기와 다르게 판단 기능이 있음. 프로그래밍 언어에서는 보통 if 문으로 표현함.

• beq rs(register1), rt(register2), l1
  • 조건 분기, rs == rt 값이 같으면 l1으로 가라
  • branch if equal
• bne rs, rt, l1
  • 조건 분기, rs != rt 값이 다르면 l1으로 가라
  • branch if not equal
• j l1
  • 무조건 분기, 그냥 l1으로 가라

If-then-else 조건부 분기로 번역

• C code

( f, g, ... 는 각각 레지스터 $s0, $s1, ... 에 해당함)

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

• Compiled MIPS code

beq를 쓰는 것 처럼 보이지만, 조건을 반대로 검사해서 then 부분을 건너뛰는 것이 효율적이므로 bne를 사용

bne $s3, $s4, Else  # i≠j 이면 Else로 이동
add $s0, $s1, $s2  # f = g+h
j Exit 
Else: sub $s0, $s1, $s2 # f = g-h (if i==j 이면 스킵)

While 순환문

• C code

i, k 는 각각 $s3, $s5,에 할당되어 있고, 배열 save의 주소가 $s6에 저장되어 있음

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

• Compiled MIPS code

제일 먼저 할일은 save[i]를 임시 레지스터로 가져오는 것임. save[i]를 임시 레지스터로 load 하기 위해서는 그 주소를 먼저 구해야 함. 인덱스 i에 4를 곱해서 save의 시작 주소에 더해야 주소가 만들어짐.

→ 2bit씩 왼쪽으로 자리이동을 하면 4를 곱한 것과 같으므로 sll 연산을 사용하여 해결할 수 있음

순환의 끝에서 처음 명령어로 되돌아 갈 수 있도록 loop 레이블 추가

Loop:  sll  $t1, $s3, 2
	     add  $t1, $t1, $s6 #save[i]주소 계산을 위해 시작주소 값을 더함
	     lw   $t0, 0($t1) #이 주소를 활용하여 save[i]를 임시 레지스터에 넣음
	     bne  $t0, $s5, Exit #반복검사 수행하여 순환에서 빠져나가는 부분
	     addi $s3, $s3, 1 # i에 1을 더하는 명령어
	     j    Loop # 순환문의 끝에서 맨 앞으로 다시 돌아감
Exit: ...

Basic block 기본 블록

• 분기 명령을 포함하지 않으며 (맨 끝에는 있을 수 잇음) 분기 목적지나 분기 레이블도 없는 (맨 앞에 있는 것은 허용됨) 시퀀스
• 컴파일러는 최적화를 위해 초기 단계 중 하나로 기본 블록을 식별함
• 고급 프로세서는 기본 블록의 실행을 가속화할 수 있음

더 많은 조건부 연산들

slt (set on less then)

두 레지스터의 값을 비교 후, 첫 번째 레지스터 값이 두번째 레지스터 값보다 작으면 세번째 레지스터 값을 1, 아니면 0으로 하는 명령어

slt rd, rs, rt → if(rs<rt) rd=1; else rd=0;

slti (set on less then immediate)상수 피연산자를 갖는 slt 명령어

slti rt, rs, constant → if(rs<constant) rt=1; else rt=0;

분기 명령 디자인

• 하드웨어에서는 < , ≤ 등이 =, ≠ 보다 느림
  • 해당 명령을 구현하면 클럭 속도가 느려지거나 별도의 클럭 사이클이 필요함
  • 빠른 명령어를 2개 쓰는게 유리함

부호있는 수의 비교 , 부호 없는 수의 비교

부호 있는 수의 비교에 사용

• slt, slti

부호 없는 수의 비교에 사용

• sltu (set on less then unsigned), sltui (set on less then unsigned immediate)

Example

• $s0= 1111 1111 1111 1111 1111 1111 1111 1111

(부호있는 정수로 보면 -1, 부호 없는 정수로 보면 4,294,967,295)

• $s1= 0000 0000 0000 0000 0000 0000 0000 0001

(부호있는 정수로 보면 1, 부호 없는 정수로 보면 1)

• slt $t0, $s0, $s1 # signed • –1<+1 → $t0=1
• sltu $t0, $s0, $s1 # unsigned • +4,294,967,295 > +1 ⇒ $t0 = 0

---

Procedure Calling 프로시저

프로시저: 제공되는 인수에 따라서 특정 작업을 수행하는 서브루틴, 이해하기 쉽고 재사용이 가능하도록 프로그램을 조회하는 방법 중 하나.

인수(parameter)는 프로시저에 값을 보내고 결과를 받아오는 일을 하므로, 프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 함.

---

프로그램이 프로시저를 실행할 때 단계

1. 프로시저가 접근할 수 있는 곳에 인수를 넣는다 (레지스터 안에)
2. 프로시저로 제어를 넘긴다
3. 프로시저가 필요로 하는 메모리 자원을 획득한다
4. 필요한 작업을 수행한다
5. 호출한 프로그램이 접근할 수 있는 장소에 결과값을 넣는다 (레지스터 안에)
6. 프로시저는 프로그램 내의 여러 곳에서 호출될 수 있으므로 원래 위치로 제어를 돌려준다

---

레지스터는 데이터를 저장하는 가장 빠른 장소이므로 가능한 한 많이 사용하는 것이 바람직하고, MIPS는 프로시저 호출 관례에 따라 레지스터를 할당함

• $a0 - $a3: 전달한 인수를 가지고 있는 인수 레지스터 4개
• $v0 - $v1: 반환되는 값을 갖게 되는 값 레지스터 2개
• $ra: 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개

MIPS 어셈블리 언어는 레지스터 할당 뿐 아니라 프로시저를 위한 명령어도 제공함

• 프로시저 호출 명령어: jal (jump and link)
  • jal procedureLabel
  • 지정된 주소로 점프하면서 동시에 다음 명령어의 주소(PC+4)를 $ra 레지스터에 저장함
  • jump and link 에서 link는 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 주소 또는 링크를 형성한다는 뜻. 레지스터 $ra(31번)에 해당되는 이 링크를 복귀주소(return adress)라고 부름
• 프로시저 복귀 명령어: jr (jump register)
  • jr $ra
  • $ra 에 저장된 주소로 무조건 점프하라는 뜻
  • $ra를 프로그램 카운터로 복사

호출 프로그램(caller)은 $a0-$a3에 전달할 인수값을 넣은 후 jal x 명령을 이용해여 프로시저 x[피호출 프로그램 (caller)]로 점프한다. 피호출 프로그램은 계산을 끝낸 후 계산 결과를 $v0-$v1에 넣은 후 jr $ra 명령을 실행하여 복귀함

이때, 내장 프로그램 개념은 현재 실행 중인 명령어의 주소를 기억하는 레지스터를 필요로 하는데 이는 명령어 주소 레지스터 (Instruction address register)로 보통 프로그램 카운터(Program counter)라고 줄여서 PC라고 부른다. jal 명령은 프로시저에서 복귀할 때 다음 명령어 부터 실행하도록 PC+4를 레지스터 $ra에 저장함.

Register Usage 레지스터 할당

• $a0 – $a3: arguments (register 4 – 7)
  • 전달한 인수를 가지고 있는 인수 레지스터 4개
• $v0, $v1: result values (register 2 and 3)
• $t0 – $t9: temporary registers
  • Can be overwritten by callee
• $s0 – $s7: saved registers
  • Must be saved/restored by callee
• $gp: global pointer for static data (register 28)
  • $sp: stack pointer (register 29)
    • 가장 최근에 스택에 할당된 주소를 가리키는 값
  • $fp: frame pointer (register 30)
  • $ra: return address (register 31)

컴파일러가 프로시저를 번역하는 데 인수 레지스터 4개, 결과 레지스터 2개로 부족한 경우를 생각해보자. 프로시저 호출이 다른 부분에 영향을 미치면 안되므로 호출 프로그램이 사용하는 모든 레지스터는 복귀하기 전에 프로시저 호출 전 상태로 되돌려 놓아야 함. → 레지스터 스필링 필요

레지스터 스필링에 이상적인 자료구조 : stack

스택은 다음 프로시저가 스필할 레지스터를 저장할 장소나 레지스터의 옛날 값이 저장된 장소를 표시하기 위해 최근에 할당된 주소를 가리키는 포인터가 필요

스택포인터는 레지스터 값 하나가 스택에 저장되거나 스택에서 복구될때 마다 한 워드씩 조정됨

MIPS 소프트웨어는 스택 포인터를 위해 29번($sp) 레지스터를 할당해 놓음

스택은 높은 주소 → 낮은 주소! 스택에 푸시를 할 때는 스택 포인터 값을 감소시키고, 팝할때는 스택 포인터 값을 증가시킴

Leaf Procedure 다른 프로시저를 호출하지 않는 C 프로시저 컴파일

• C code

g, h, i, j 는 $a0 ~ 3에 해당됨, f는 $s0에 해당됨

int leaf_example (int g, h, i, j) {
   int f;
	 f = (g + h) - (i + j);
	 return f; 
}

• Compiled MIPS code

1. 컴파일된 프로그램은 ‘leaf_example’ 이라는 이름의 프로시저 레이블로부터 시작됨
   1. leaf_example:
2. 프로시저가 사용할 레지스터 값 저장. 임시 레지스터 2개 사용 총 $s0, $t0, $t1 3개
   1. addi $sp, $sp, -12 # 3개의 레지스터를 위한 공간
   2. sw $t1, 8($sp) #하나씩 값 저장해주기
   3. sw $t0, 4($sp)
   4. sw $s0, 0($sp)
   • **스택포인터는 항상 스택의 맨위, 마지막 스택을 가리킴 ***
3. 프로시저 본문
   1. add $t0, $a0, $a1
   2. add $t1, $a2, $a3
   3. sub $s0, $t0, $t1
4. f를 결과값 레지스터에 보내줌
   1. add $v0, $s0, $zero
5. 호출프로그램으로 돌아가기 전에 저장해 두었던 값을 스택에서 꺼내 레지스터 원상복귀
   1. lw $s0, 0($sp)
   2. lw $t0, 4($sp)
   3. lw $t1, 8($sp)
   4. addi $sp, $sp, 12
6. 복귀 주소 jr을 사용하여 끝내기
   1. jr $ra

---

위의 예제에서는 임시레지스터를 사용했으나 사용하지도 않는 레지스터 값을 쓸데없이 저장했다 복구했다 하는 일을 예방하기 위해 MIPS 소프트웨어는 레지스터 18개를 두 종류로 나눔.

• $t0-$t9: 프로시저 호출 시, 피호출 프로그램이 값을 보존해 주지 않는 임시 레지스터
• $s0-$s7: 프로시저 호출 전과 후 값이 같게 유지되어야 하는 변수 레지스터(피호출 프로그램이 이 레지스터를 사용하면 원래 값을 저장했다가 원상 복구함)

이런 간단한 관례로 레지스터 스필링을 많이 줄일 수 있고, 위의 예시에서 $t0, $t1 값이 호출 전후에 같은 값을 유지할 필요가 없기 때문에 저장 명령 2개와 적재 명령 2개를 없앨 수 있음. 그러나 $s0은 피호출 프로그램 입장에서 호출 프로그램이 필요로 할 것으로 가정하기 때문에 저장했다가 원상복귀해야함.

---

위의 예제를 관례에 맞게 다시 정리하면 아래와 같음

leaf_example:

addi $sp, $sp, -4 #레지스터 1개($s0)의 공간을 위함(f가 해당됨)
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 #f를 결과값 레지스터에 보내줌

lw $s0, 0($sp) # 레지스터 복구 
addi $sp, $sp, 4 # 스택 복구

jr $ra #복귀주소로 return

---

Non-Leaf Procedures 중첩된 프로시저

다른 프로시저를 호출하지 않는 프로시저 = 말단 프로시저 (leaf procedure) 라고함. 그렇다면 리프가 아닌 프로시저는?

리프가 아닌 프로시저

• 다른 프로시저를 호출하는 프로시저
  • 자기 자신을 호출하는 recursive 프로시저도 있음
• 중첩 호출의 경우 호출자는 스택에 저장해야 함
  • 반송 주소
  • 호출 후 필요한 모든 인수 및 임시
• 호출 후 스택에서 복원

말단 프로시저가 아닌 프로시저를 호출할 때는 조심해야 함!!

예를 들어 주 프로그램이 인수값 3을 가지고 프로시저 A를 실행한다고 가정하면, 레지스터 $a0에 3을 넣고 jal A명령어를 실행한다. 프로시저 A가 다시 인수 7(이것도 $a0에 들어감)을 가지고 jal B를 통해 프로시저 B를 호출했다고 하면, 아직 A가 끝나지 않아서 $a0 사용에서 충돌이 발생한다. 마찬가지로 레지스터 $ra는 아직 B의 복귀 주소가 있으므로 $ra 복귀주소에 대해서도 충돌이생김. 이렇게 되면 프로시저 A가 호출 프로그램으로 돌아가지 못함.

그렇다면 ,, 한가지 방법은! 값이 보존되어야 할 모든 레지스터를 스택에 넣는 것!

호출 프로그램은 인수 레지스터 ($a0 ~ $a3) 와 임시 레지스터 ($t0 ~ $t9) 중 프로시저 호출 후에도 계속 사용해야 하는 것은 모두 스택에 넣음.

피호출 프로그램은 복귀주소 레지스터 $ra와 저장 레지스터($s0 ~ $s7) 중에서 피호출 프로그램이 사용하는 레지스터를 모두 저장함.

스택포인터 $sp는 스택에 저장되는 레지스터 개수에 맞추어 조정됨.

복귀한 후에는 메모리에서 값을 꺼내 레지스터를 원상 복구하고 이에 맞추어 스택 포인터를 다시 조정함.

---

Example

• C code

n 계승을 계산하는 재귀 프로시저를 컴파일해보자

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

• MIPS compiled code

1. 인수 n은 레지스터 $a0에 해당됨. 번역된 프로그램은 프로시저 레이블로 시작하고, 뒤이어 복귀 주소와 $a0를 스택에 저장함
   1. fact:
   2. addi $sp, $sp, -8 # 스택에 2개 공간 할당 sw $ra, 4($sp) # 복귀주소 저장 sw $a0, 0($sp) # 인수 0 저장
2. fact가 처음 호출되었을때 sw는 fact를 호출한 프로그램의 주소를 저장한다. 다음은 n이 1보다 작은지 검사해서 n≥1이면 l1으로 가게 하는 명령어.
   1. slti $t0, $a1, 1 # n<1 검사함
   2. beq $t0, $zero, L1 # n≥1일 경우 L1으로 이동
3. n이 1보다 작을시 1을 결과값 레지스터에 넣는다. 이때 0에다가 1을 더해서 $v0에 넣는다. 복귀하기 전에 스택에 저장된 값 2개를 버리고 복귀 주소로 점프함
   1. addi $v0, $zero, 1 #1을 반환함
   2. addi $sp, $sp, 8 # stack에서 2개 pop
   3. jr $ra # caller로 점프(복귀주소로)
4. 스택에서 값 2개를 꺼내서 $a0과 $ra에 넣을수도 있으나, n이 1보다 작을때 $a0와 $ra는 변하지 않으므로 그럴 필요가 없음. n이 1보다 작지 않으면, 인수 n을 감소시키고 이 감소된 값으로 다시 fact를 호출함
   1. L1: addi $a0, $a0, -1 # n≥ 1: arguments gets(n-1)
   2. jal fact #call fact with(n-1)
5. 다음은 호출한 프로그램으로 되돌아 가는 부분. 먼저 스택포인터를 사용해서 이전의 복귀 주소와 인수값을 복구함
   1. lw $a0, 0($sp) # return from jal: restore argument n
   2. lw $ra, 4($sp) # resotre the return address
   3. addi $sp, $sp, 8 # adjust stack pointer to pop 2 items
6. 다음으로 인수 $a0과 결과값 레지스터의 현재 값을 곱해서 $v0에 넣음. 곱셈 명령어는 다음장에서 배우지만 우선 씀
   1. mul $v0, $a0, $v0 # return n * fact(n-1)
7. 마지막으로 복귀 주소를 이용해 되돌아감
   1. jr $ra #return to the caller

정리하면 다음과 같음

fact:
	addi $sp, $sp, -8 #스택에 2개 공간 할당
	sw $ra, 4($sp) #복귀주소 저장
	sw $a0, 0($sp) #n 인수값 저장
	
	slti $t0, $a0, 1 # n<1 검사 a0 < 1 보다 작으면 t0=1 아니면 t0=0
	beq $t0, $zero, L1 # if n>=1 이면 L1 이동
	
	addi $v0, $zero, 1 # 결과값에 1 저장 (return 1이기 떄문)
	addi $sp, $sp, 8 # 스택에서 2개 만큼 뽑기
	jr $ra # 복귀주소로 점프함

L1: 
	addi $a0, $a0, -1 # n<1이 아니라면 n = n-1
	jal fact #recursive
	
	lw $a0, 0($sp) #n 복구
	lw $ra, 4($sp) #주소 복구
	addi $sp, $sp, 8 # stack 에서 2개 pop
	
	mul $v0, $a0, $v0 # else: n * (n-1)
	jr $ra #복귀주소로 복귀

이해하느라 죽는줄 알았던,, 시험은 어떻게 볼까,,? ㅜㅜ

---

새 데이터를 위한 스택의 공간 할당

레지스터에 들어가지 못할 만큼 큰 배열이나 구조체 같은 지역 변수를 저장하는 데도 스택이 사용되기 때문에 문제가 복잡해짐. 프로시저의 저장된 레지스터와 지역 변수를 가지고 있는 스택 영역을 프로시저 프레임 또는 액터베이션 레코드라고 부름.

보존 preserved보존안됨 not preserved

saved register $s0-$s7	temporary register $t0-$t7
stack pointer register $sp	argument register $a0-$a3
return adress register $ra	return value registers $v0-$v1
stack above the stack pointer	stack below the stack pointer

MIPS 소프트웨어 중에는 프레임 포인터($fp)가 프로시저 프레임의 첫번쨰 워드를 가리키도록 하는 것이 있다. 스택 포인터 값이 프로시저 내에서 바뀔 수도 있으므로 메모리 내 지역 변수에 대한 변위는 변수가 프로시저 어느 부분에서 사용되느냐에 따라 달라질 수 있음. → 프레임 포인터를 사용하면 프레임 포인터가 변하지 않는 베이스 레지스터 역할을 하여 지역참조 역할이 간단해짐.

---

새 데이터를 위한 힙 공간의 할당

C 프로그래머는 프로시저 내에서만 정의되는 자동 변수 외에도 정적 변수와 동적 자료구조를 위한 메모리 공간이 필요함. 아래 그림은 MIPS 메모리 할당 방식이다. 스택은 최상위 주소에서 시작하여 아래쪽으로 자란다. 최하위 주소 부분은 사용이 유보되어 있고, 그 다음은 MIPS 기계어가 들어가는 부분이다. 이 부분은 text segment라고 부름. 코드 위쪽에는 static data segment 부분이 있는데, 상수와 기타 정적 변수들이 여기에 들어감. 그다음은 heap (dynamic data)

배열: 크기 고정되어 있음 → 정적 데이터 세그먼트에 잘 맞음

링크드 리스트: 늘었다 줄었다 함 → 이를 위한 데이터 세그먼트는 heap (정적 데이터 다음 부분)

스택과 힙이 서로 마주보면서 자라도록 할당하여 메모리를 효율적으로 사용가능함