[컴퓨터 구조] Lecture 07: Instructions - Language of the Computer

경희대학교 컴퓨터공학부 김정욱 교수님의 컴퓨터 구조 강의 내용을 기반으로 한 정리글

 

Compiled MIPS Code Examples

1. program variables에 registers 할당
2. procedure code 작성
3. 호출되면서 preserve registers

Swap Function

void swap(int v[], int k) {
    int temp;
    temp = v[k];
    v[k] = v[k + 1];
    v[k + 1] = temp;
}

 

1. Allocate registers to program variables

• v[], k -> $a0, $a1에 저장
• temp -> $t0

2. Produce code for the body of the procedure

swap:
    sll $t1, $a1, 2		#k에 byte addressing, offset 계산
    add $t1, $a0, $t1	#base address에 계산된 offset을 더하여 새로운 base address 지정
    
    lw $t0, 0($t1)		#temp에 v[k + 0] 저장
    lw $t2, 4($t1)		#t1값 t2에 저장 -> t1에 저장하면 base address 사용못함
    
    sw $t2, 0($t1)		#swap된 값 저장
    sw $t0, 4($t1)		#swap된 값 저장
    
    jr $ra

-> base address 하나($t1)를 기준으로 바꿔주는 느낌!

 

3. Preserve registers across the procedure invocation

• saved registers 이용하지 않았으므로, preserve할 것이 없다

 

Sort Function

1. 레지스터에 변수 할당

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

2. 함수 코드 작성

    add $s0, $s0, $0	#i = 0
for1tst: 
    slt $t0, $s0, $a1	#i < n 만족하면 t0 = true
    beq $t0, $0, exit1	#false이면 exit으로
        #...
        #(body of first for loop)
        #...
    addi $s0, $s0, 1	#i += 1
    j for1tst		    #jump to test of outer loop
exit1:

 

    addi $s1, $s0, -1
for2tst:
    slti $t0, $s1, $0	#j < 0 true
    bne $t0, $0, exit2	#이중부정 -> j < 0이면 점프
    
    sll $t1, $s1, 2		#j에 byte addressing
    add $t2, $a0, $t1           #t2에 v + (j * 4)
    lw $t3, 0($t2)		#t3 = v[j]
    lw $t4, 4($t2)		#t4 = v[j + 1]
    slt $t0, $t4, $t3	
    beq $t0, $0, exit2
    
    #body of second for loop
    
    addi $s1, $s1, -1
    j for2tst
exit2:

 

• sort의 argument인 v와 n 저장

add $s2, $a0, $0
add $s3, $a1, $0

add $a0, $s2, $0
add $a1, $s1, $0

 

addi $sp, $sp, -20
sw $ra, 16($sp)
sw $s3, 12($sp)
sw $s2, 8($sp)
sw $s1, 4($sp)
sw $s0, 0($sp)

exit1: 
    lw $s0, 0($sp)
    lw $s1, 4($sp)
    lw $s2, 8($sp)
    lw $s3, 12($sp)
    lw $ra, 16($sp)
    addi $sp, $sp, 20

 

 

 

Arrays vs. Pointers

array[]: 배열의 메모리 주소를 담고 있는 포인터, 실제 크기를 알 수 없음, 따라서 다른 매개변수를 통해 배열의 크기를 받아야 한다.

 

 

 

 

---

Swap&Sort Function 복기

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

void swap(int v[], int k) {
    int temp;
    temp = v[k];
    v[k] = v[k + 1];
    v[k + 1] = temp;
}

sll $t1, $a1, 2	#k byte address
add $t1, $a0, $t1	#v[k]
lw $t0 0(t1)	#temp에 v[k] lw
lw $t2 4(t1)	#t2에 v[k + 1] lw
sw $t0 4(t1)	#temp값 v[k + 1]에 sw
sw $t2 0(t1)	#t2값 v[k]에 sw
jr $ra

 

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

void sort(int v[], int n) {
    int i, j;
    for(i = 0; i < n; i += 1) {
        for(j = i - 1; j >= 0 && v[j] > v[j + 1]; j -= 1) {
            swap(v, j);
        }
    }
}

#saving registers
sort: 
    addi $sp, $sp, -20	#sp 5칸 아래로
    sw $ra, 16($sp)	#16(sp)에 ra 저장
    sw $s3, 12($sp)	#12(sp)에 s3(=a1) 저장
    sw $s2, 8($sp)	#8(sp)에 s2(=a0) 저장
    sw $s1, 4($sp)	#4(sp)에 s1 저장
    sw $s0, 0($sp)	#0(sp)에 s0 저장
#procedure body
    #a0, a1 -> s2, s3에 저장
    addi $s2, $a0, $0
    addi $s3, $a1, $0
    #for1sts 초기설정
    add $s0, $s0, $0
for1sts:
    #slt + beq(else면!) -> exit1으로
    slt $t0, $s0, $0
    beq $t0, $0, exit1
    #for2sts 초기설정
    addi $s1, $s0, -1
for2sts:
    #slti + bne(여집합) = slti + beq -> exit2
    slti $t0, $s1, 0
    bne $t0, $0, exit2
    #t1에 j byte addressing 저장
    sll $t1, $s1, 2
    #t2에 v[j] 저장
    add $t2, $a0, $t1
    #t3에 0(t2) 저장
    lw $t3, 0($t2)
    #t4에 4(t2) 저장
    lw $t4, 4($t2)
    #위치 바꾼 slt, beq -> exit2
    slt $t0, $t4, $t3
    beq $t0, $0, exit2
    #swap에 들어가는 파라미터 저장 후, swap 진입
    add $a0, $s2, $0
    add $a1, $s1, $0
    #inner loop 끝
    addi $s1, $s1, -1
    j for2sts
exit2:
    #i += 1 
    addi $s0, $s0, 1
    #for1sts로 점프
    j for1sts
#restoring registers
exit1:
	#resotring
    lw $s0, 0($sp)
    lw $s1, 4($sp)
    lw $s2, 8($sp)
    lw $s3, 12($sp)
    lw $s4, 16($sp)
    #sp 위치 복귀
    addi $sp, $sp, 2
#procedure return
    jr $ra