Lecture 07: Instructions - Language of the Computer - 4

경희대학교 김정욱 교수님의 컴퓨터 구조 수업을 기반으로 정리한 글입니다.

Compilde MIPS Code Examples

Compiling steps

1. Allocate registers to program variables

변수마다 레지스터를 할당한다.

 

2. Produce code for the body of the procedure

함수의 코드를 직접 컴파일, 즉 assembly code를 작성한다.

 

3. Preserve registers across the procedure invocation(호출)

레지스터 보존 여부, 즉 callee로 가기 전, 레지스터에 저장된 값을 메모리에 저장할지 말지를 결정한다.

ex) 레지스터 보존 - $s0, $ra

▶ Compiling steps

Compilde MIPS Code Examples - (1) Swap

Swap Function

▶ C code

 

1. Allocate registers to program variables

 

• v[ ] -> $a0
• k -> $a1
• temp -> $t0

※ v[ ]는 base address, 즉 array의 시작 지점 주소값을 의미한다.

▶ Register과 Memory

 

2. Produce code for the body of the procedure

▶ MIPS code - 1

sll $t1, $a1, 2

▶ sll (Shift left logical)

 

$a1이 만약 0000 1001 이라면, $t1은 0010 0100으로, $a1 값을 2칸 외쪽으로 민 것이다.

즉, 왼쪽으로 i bits shift 하는 것은 2의 i승만큼 곱하는 것과 같다.

 

때문에 첫 번째 줄에서 $t1에는 k × 4가 담긴 것이다.

 

※ 이와 반대로 srl (Shift right logical)은 오른쪽으로 shift하는 만큼 2의 i승만큼 나눈 것과 같다.

▶ Register과 Memory - 1

▶ MIPS code - 2

 

v[k] -> $a0 + k × 4 -> $t1 이므로, ($t1 = 0($t1))

v[k+1] -> 4($t1) 이다. 

 

이렇게 swap 함수 수행이 완료되면 $ra로, 즉 caller로 돌아간다.

 

※ 이때 $t1은 새로운 base address이다.

▶ Register과 Memory - 2

 

3. Preserve registers across the procedure invocation(호출)

saved registers를 함수에서 사용하지 않았기 때문에, 보존해야 할 것이 없다. (새로운 callee 함수가 없음)

Compilde MIPS Code Examples - (2) Sort

Sort Function (정렬)

▶ C code

• caller: sort
• callee: swap

1. Allocate registers to program variables

• v[ ] -> $a0
• n -> $a1
• i -> $s0
• j -> $s1

⭐ i, j는 callee 함수 수행 후에도 for문 수행을 위해 값이 변하면 안 되기에  t가 아닌 s에 저장해야 한다.

 

2. Produce code for the body of the procedure

▶ MIPS code - 1

 

이때 move는 존재하는 instruction이 아니라 상징적으로 써 놓은 것이다.

addi $s0, $0, 0

▶ move instruction 구현 code (실제 구현 코드)

▶ MIPS code - 2

▶ MIPS code - 3

 

이때, $a0 -> $s2를 수행한 뒤 다시 $s2 -> $a0를 수행하는데 그 이유는,

callee로 진입하기 전 저장하는 과정, callee에 인자를 넣는 과정으로 나눠 진행한 것이기 때문이다.

 

만약, $a0를 사용하고 싶지 않다면 $s2를 그냥 사용해도 된다.

 

3. Preserve registers across the procedure invocation(호출)

▶ saved registers

 

sort 함수의 caller 입장에서는 sort 함수가 $s0 ~ $s3를 사용하기 때문에, 이를 위해 먼저 저장해 주어야 한다.

이때, sort 함수에서 사용하는 $s0 ~ $s3뿐만 아니라, sort 함수의 caller로 돌아갈 $ra도 저장해야 한다.

swap에서 sort로 갈 때도 $ra를 사용하기에 저장해놓지 않으면 안 된다.

 

이렇게 다 끝나면, lw를 통해 다시 caller로 돌아가는 과정을 수행한다.

 

※ 값 저장시 먼저 스택 포인터를 내린 후 저장하고, 값 꺼낼시 값을 먼저 꺼낸후 스택 포인터를 올린다. 만약 스택 포인터를 먼저 올린 후, 값을 꺼내려 하면 프레임 포인터가 범위를 멋어나 에러가 발생한다.

 

Full Procedure

▶ Full Procedure

Less than comparison

Arrays vs. Pointers

Arrays

▶ Arrays

 

※ main(): caller / clear1(int array[ ], int size): callee

Arrays - Example (Clear 1 procedure)

▶ C code

 

(1) Allocate registers to program variables

$a0: base address of array, $a1: size, $t0: i

 

이때, i를 $s0이 아닌 $t0에 저장하는 이유는, i가 오직 clear1 함수에서만 사용되기 때문이다.

다시 말해, for문 안에 다른 callee로 넘어가는 코드가 없기에 i를 보존할 필요가 없다.

 

(2) Produce code for the body of the procedure 

       addi $t0, $0, 0     # i = 0
       slt  $t4, $t0, $a1  # i < size이면, $t4 = 1
       beq  $t4, $0, Exit  # i >= size이면 Exit으로 이동
loop1: sll  $t1, $t0, 2    # i * 4
       add  $t2, $a0, $t1  #  $t2 = address of array[i], 새로운 base address
       sw   $zero, 0($t2)  # array[i] = 0
       addi $t0, $t0, 1    # i = i + 1
       slt  $t3, $t0, $al  # $t3 = (i < size)
       bne  $t3, $0, loop1 # if (i < size) go to loop1
Exit:

▶ MIPS code

 

※ 이때 loop1, Exit은 address를 의미한다.

 

※ $zero는 값을 옮길 때도 사용하지만, 0으로 초기화할 때도 사용한다.

 

※ 만약 array[i] = 0이 아니라, 1을 넣어야 한다면?

addi $t7, $0, 1 # $t7 = 0 + 1 = 1
sw $t7, 0($t2)

▶ sw로 상수값 저장하는 방법

 

sw는 상수 값을 넣는 게 아니라, 레지스터에 있는 값을 넣기로 약속하였기 때문에,

$0가 있는 0을 제외한 상수를 저장할 때는 다 이런 식의 과정으로 해주어야 한다.

 

(3) Preserve registers across the procedure invocation

저장할 값이 없다.

Pointers - Example (Clear 2 procedure) 

▶ C code

• p: array의 주소를 가리키는 포인터
• *p: 포인터가 가리키는 주소의 값

※ 이 코드에선 하지 않았지만, array와 달리 pointer를 사용하면 주소를 미리 계산할 수도 있다. 

 

(1) Allocate registers to program variables

$a0: base address of array, $a1: size, $t0: p

 

(2) Produce code for the body of the procedure

       addi $t0, $a0, 0    # p = base address of array[0] (시작 지점)
       sll $t1, $a1, 2     # $t1 = size * 4 (byte addressing)
       add $t2, $a0, $t1   # $t2 = end address of array[size] (끝 지점)
       slt  $t4, $t0, $t2  # p < end address of array[size]이면, $t4 = 1
       beq  $t4, $0, Exit  # p >= end address of array[size]이면 Exit으로 이동
loop2: sw   $zero, 0($t0)  # Memory[p] = 0
       addi $t0, $t0, 4    # p = p + 4 (byte addressing)
       slt  $t3, $t0, $t2  # $t3 = (p < $array[size])
       bne  $t3, $0, loop2 # if ((p < $array[size]) go to loop2
Exit:

▶ MIPS code

 

add 이후에 비교를 거치지 않고 바로 loop2로 들어가면,

배열의 size가 0 or 음수인 경우, 즉 배열의 크기가 없거나 유효하지 않은 크기인 경우를 확인하지 못해,

잘못된 메모리 접근이 발생할 수 있다.

 

때문에 비교하는 과정은 꼭 필요하다.

Arrays vs. Pointers

▶ Arrays and Pointers (Comparisons)

 

Pointer가 더 효율적이기에 퍼포먼스(속도)가 더 좋다.

 

array는 매번 loop에서 인덱스 i를 사용해 주소값을 계산,

즉 매번 base address를 새로 만들어야 한다. (한 개의 loop마다 instruction 6개)

매번 돌 때 주소 계산

 

pointer는 lopp 시작 전 끝 지점을 이용해 미리 주소를 다 계산을 할 수 있기에,

즉 loop 내부에서 별도의 주소 계단이 필요하지 않다. (한 개의 loop마다 instruction 4개)

 

이때, 2 instruction 차이가 별거 아니게 보일 수 있지만, for문을 반복하면 결국 큰 차이가 나게 된다.