KOCW 최규상 교수님 컴퓨터구조 강의 정리
이 글은 공부한 것을 복습 및 기록하기 위한 게시물입니다.
잘못된 정보가 기입되어 있을 수 있으니 주의해주시기 바랍니다.
참고 : 컴퓨터 구조 및 설계 - David A. Patterson,John L. Hennessy
강의 링크 : http://www.kocw.net/home/cview.do?lid=f64448266743ced9
1. Six steps in Execution of a procedure(Procedure Calling)
procedure 실행의 6단계를 뜻한다.
caller는 어떠한 함수를 부르는 것이고 callee는 불리여지는 함수를 뜻한다.
claller는 callee가 엑세스 할 수 있는 곳에 argument를 가져다 놓게 된다.
MIPS의 argument register는 $a0~$a3가 있다.caller는 callee로 프로그램의 control을 넘기게 된다.
callee는 필요한 메모리 공간을 할당 받게 된다.
callee가 해야될 일을 하게 된다.
callee가 일을 다한 후에는 caller가 엑세스할 수 있는 위치에 return value를 저장하게 된다.
MIPS에서는 return value로 $v0, $v1이 있으며 callee가 해당 register를 통해 caller로 return value를 전달하게 된다.callee가 다시 caller에게 프로그램의 control을 넘기게 된다.
이 때 retrun address를 알고 있어야 한다.
return address는 $ra register에 저장되어 있다.
이 값을 통해 caller로 프로그램 control이 넘어가게 된다.
2. Register Usage
MIPS에서 제공되는 레지스터이다.
3. Procedure Call Instructions
Procedure Call관련 명령어이다.
jal ProcedureLabel
이 명령어는 2가지를 동시에 하게 된다.
- jal 다음 명령어의 주소를 ra에 넣음
- 해당 ProcedureLabel의 target address로 점프 하게 됨
그 다음 callee로 갔으니 caller로 가야한다.
jr $ra
- $ra register에 들어있는 값으로 프로그램 control이 바뀌게 된다.
- $ra에 값을 Program Counter에 저장하게 되며 $ra에 있는 값으로 점프하게 되는 것이다.
3-1. Leaf Procedure Example
Leaf Procedure는 해당 함수에서 다른 함수를 부르지 않는 것을 뜻한다.
해당 C코드를 MIPS코드로 컴파일 하게 되면 아래와 같다.
addi $sp, $sp, -4 (allocation)
스택 포인터를 4만큼 감소시킨다.
스택은 위에서 부터 아래로 감소하게 된다.
-4를 한다는 것은 4byte만큼 스택에 할당한다는 뜻이다.
sw $s0, 0($sp)
할당 된 공간에 기존에 $s0 값이 어떤 값이 저장되있을 수도 있으니 $s0 레지스터를 스택에 저장해 놓는다.
그리고 이 $s0를 f변수로 사용한다.
add $t0, $a0, $a1
그 다음 $a0와 $a1을 더한 후 $t0에 넣는다.
add $t1, $a2, $a3
그리고 $a2와 $a3을 더해서 $t1에 넣는다.
sub $s0, $t0, $t1
그리고 나서 $t1과 $t0를 뺀 후 $s0에 넣는다.
add $v0, $s0, $zero
연산된 결과 값($s0)을 zero와 더한 후 $v0에 넣는다.
move 명령어와 같은 역할을 하게 된다.
lw $s0, 0($sp)
스택에 있는 값을 다시 $s0에 넣는다.
$s0를 로컬 변수로 사용했으며 다 사용한 후에는 원래 값으로 복원시켜 놓아야 한다.
addi $sp, $sp, 4 (deallocation)
그 다음 4byte만큼 할당받은 메모리를 반납해야한다.jr $ra
마지막으로 $ra에있는 레지스터 값으로 점프하게 된다.
caller가 jal leaf_example라는 명령어를 실행한다.
이 순간에 jal 명령어 다음에 오는 명령어 주소가 $ra에 들어가게 된다.
그 다음 leaf_example를 다 실행한 후 $ra에 있는 주소로 점프하게 되는 것이다.
즉, jal leaf_example 다음 명령어가 실행 되는 것이다.
3-2. Non-Leaf Procedures
Leaf Procedures는 그 함수에서 다른 함수를 호출하지 않아 함수를 처리하는데 아주 수훨하다.
하지만 하나의 함수가 또 다른 함수를 부를 수 있다.
이런 경우는 처리가 복잡해진다.
caller가 그 안에서 다른 것을 부르게 되면 $ra레지스터 값을 다른 곳에 저장해두어야 한다.
또한 arguments나 temporaries 등 또한 스택에 저장해두어야 한다.
그 다음 callee에서 caller로 온 후 스택에 저장된 값을 복원해야 한다.
Non-Leaf Procedures는 Leaf Procedures보다 처리가 복잡하다.
3-2-1. Non-Leaf Procedure Example
C코드는 Leaf Procedure와 비슷하지만 어셈블리 코드는 매우 복잡하다.
MIPS 코드로 컴파일 한것은 아래와 같다.
*fact:
addi $sp, $sp, -8
sw $ra, 4($sp)
sw $a0, 0($sp)
스택을 -8을 하게 된다.
2가지 값을 저장하기 위해서이다.
바로 retrun address와 argument이다.
slti $t0, $a0, 1
$a0와 1을 비교한다.
$a0가 1보다 작으면 $t0가 1이 된다.
만약 $a0가 1보다 크다면 $t0는 0이 된다.
beq $t0, $zero, L1
$t0와 zero가 같으면 L1 label로 점프하게 된다.
그러나 $t0가 zero와 같지 않다면 그 다음 명령어로 점프하게 된다.
addi $v0, $zero, 1
$a0가 1보다 작다면 $t0가 0이 되어서 $t0와 zero가 같아지고 해당 명령어를 실행하게 된다.
1을 $v0에 넣게 된다.
addi $sp, $sp, 8
스택 값을 다시 8만큼 증가한다.
할당 받은 것을 deallocation하기 위함이다.
jr $ra
그다음 $ra의 있는 값으로 점프하게 된다.
만약 L1 label을 실행했다면 lw $a0, 0($sp) 명령어를 실행하게 되는 것이다.
L1 :
addi $a0, $a0, -1
만약 $a0의 값이 2라고 가정하면 해당 명령어를 실행하게 된다.
$a0의 값을 1만큼 감소한다.
그리고 그 다음 명령어를 실행한다.
jal fact
fact label로 점프한다.
해당 명령어를 실행할 때 이 명령어의 다음 명령어가 있는 메모리 주소 값이 $ra register로 들어가게 된다.lw $a0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
mul $v0, $a0, $v0
jr $ra
해당 fact label을 부른 caller로 가게 된다.
4. Local Data on the Stack
실제 프로그램에서 함수를 사용할 때 메모리가 어떤 식으로 할당 되는지 보여주는 그림이다.
frame pointer와 stack pointer가 있다.
stack pointer는 현재 스택에 있는 top의 위치를 가리키는 포인터이다.(register)
하나의 함수를 실행할 때 할당되는 메모리 공간을 activation record라고 부른다.
activation record의 처음 시작하는 위치를 가리키는 것을 frame pointer라 한다.
activation record의 시작을 가리키는 것을 frame pointer, 끝을 가리키는 것을 stack pointer라 한다.
activation record는 argument, return address, 필요한 register, 로컬 변수들이 저장 된다.
함수가 끝나게 되면 activation record는 deallocation이 된다.
그렇게 되면 frame pointer와 stack pointer는 조정이 된다.
다시 바로 위에 activation record 관련 시작 주소와 끝 주소를 가리키게 된다.
5. Memory Layout
실제 우리가 사용하는 메모리는 그림과 같은 구조로 할당이 된다.
맨 아래 주소 공간은 예약 되어있다.
그 위에는 Text가 저장 된다.
Text는 명령어들이다.(프로그램 코드)
그리고 그 다음 전역변수인 static 변수가 저장된다.
메모리 제일 끝 공간을 stack이라고 한다.
이 공간에는 activation record들이 할당이 된다
그리고 동적데이터(malloc)가 할당되는 heep이 있다.
static data 위에 있게 된다.
stack은 아래 아래방향으로 할당되며 Danymic data는 위 방향으로 할당이 된다.
프로그램을 실행하다보면 stack overflow가 생길때가 있다.
이 경우는 stack이 계속 증가하여 heap공간을 침범하게 되면 stack overflow가 발생하게 되는 것이다.
Program Coutner값은 Text 안에서 움직이게 된다.
global pointer는 static data를 엑세스하기 쉽게 하기 위해서 사용되는 포인터로
Text가 할당이 되고 그 위를 가리키게 된다.
MIPS에서는 static data가 0x1000 ffff와 0x1000 0000사이에 할당된다.
global pointer는 해당 값의 중간 값을 갖게 된다.
6. Character Data
char은 byte이다.
처음에는 알파벳만 저장할 수 있도록 정의가 되었다.
하지만 아시아는 다양한 문자들이 있어서 Unicode라는 것이 제정이 된다.
유니코드는 32bit Character set이다.
ASCII, Latin-1은 문자를 무조건 8bit로 표현한다.
하지만 variable-length(UTF-8, UTF-16)는 여러 byte를 사용해서 표현할 수 있다.
7. Byte/Halfword Operations
1byte, 2byte데이터를 엑세스할 때가 있다.
lb는 1byte만큼 로딩하며 lbu는 unsigend로 로딩한다.
lb와 lbu는 byte 또는 2byte를 읽는다 하더라도 32bit로 extend를 해서 레지스터에 넣게 된다.
sb는 1byte만큼 store한다.
이런 경우 rightmost에 저장이 된다.
혹은 halfword에 저장이 된다.
7-1. String Copy Example
strcpy는 Leaf Procedure이다.
String에서 null이 존재하면 String은 끝이 나게 된다.
해당 C코드를 MIPS 코드로 컴파일하게 되면 아래와 같다.
addi $sp, $sp, -4
i 로컬 변수를 사용하기 위해 스택을 4만큼 감소시킨다.
sw $s0, 0($sp)
거기에 기존에 있던 $s0값을 저장한다.
L1 :
add $t1, $s0, $a1
그 다음 $s0에다가 $a1을 더하게 된다.
lbu $t2, 0($t1)
1byte만큼 읽는다.
즉, y[i] index 값을 $t2에 넣는 것이다.
add $t3, $s0, $a0
x[i]의 주소를 계산한다.
sb $t2, 0($t3)
y[i]의 값을 x[i]에 저장한다.
beq $t2, $zero, L2
y[i]가 0과 같은지 아닌지를 체크한다.
같다면 L2레이블로 점프하며
같지 않다면 다음 명령어를 실행한다.
addi $s0, $s0, 1
i 값을 1만큼 증가한다.
j L1
L1으로 점프한다.
점프는 무조건 실행하게 된다.
해당 라인은 loop에 해당된다.
L2 :
lw $s0, 0($sp)
기존에 $s0에 있던 값을 복원한다.addi $sp, $sp, 4
스택값을 조정한다.
jr $ra
caller로 점프하게 된다.
'Computer Science > 컴퓨터 구조' 카테고리의 다른 글
| 8. Instructions: Language of the Computer 4 (0) | 2021.04.14 |
|---|---|
| 6. Instructions: Language of the Computer 2 (0) | 2021.04.10 |
| 5. Instructions: Language of the Computer 1 (0) | 2021.04.08 |
| 4. Computer Avstractions and Technology 4 (0) | 2021.04.03 |
| 3. Computer Avstractions and Technology 3 (0) | 2021.03.31 |
