[MIPS] MIPS 스택을 활용한 반복문

스택을 사용하기 위해서 아래와 같은 MIPS 명령어를 이해해야 한다.

 

명령어	피연산자 1	피연산자 2	의미
lw (load word)	$t0	변수 이름	메모리에서 t0 레지스터로 값을 저장한다.
sw (store word)	$t0	변수 이름	t0 레지스터의 값을 메모리에 저장한다.
jal	loop	없음	jal loop 다음 명령어의 주소를 $ra에 저장하고loop로 jump 한다
jr	$ra	없음	$ra 레지스터에 담긴 주소로 이동한다.

이전 포스팅에서 조건부 점프, 무조건 점프에 대해서 공부했었는데

https://growth-coder.tistory.com/34

 

jal과 jr 명령어는 무조건 점프에 해당한다.

 

jal loop를 실행하게 되면 loop로 점프하기 전에 다음에 실행할 명령어의 주소를 $ra 레지스터에 저장한다.

 

이렇게 저장한 명령어의 주소는 jr $ra를 사용하여 실행할 수 있다.

 

여기서 중요한 점은 "명령어의 주소"를 저장한다는 점이다.

 

 

 

이제 스택을 이용하여 입력받은 수 만큼 별을 출력하는 코드를 만들어보려고 한다.

 

코드를 작성하기 전에 흐름을 먼저 이해하는 것이 좋다.

 

스택에 데이터를 저장하는 순서는 위에서 아래로 저장한다.

 

저장할 때는 $sp 레지스터의 값을 4씩 감소시키면서 저장을 하고

 

값을 꺼내올 때는 4씩 증가시키면서 꺼내오면 된다.

 

이제 이 스택을 반복문에 활용할 예정인데 스택에 저장하고 꺼내오는 순서는 다음과 같다.

1. jal 명령어를 사용하여 $ra 레지스터에 다음 명령어의 주소를 저장한다.
2. $sp에 해당하는 스택 위치에 $ra 레지스터의 값을 저장한다. (다음 명령어의 주소)
3. $sp 레지스터의 값을 4 감소시킨다. (스택 포인터를 다음으로 이동시킨다.)
4. 특정 조건을 만족할 때까지 1번으로 돌아간다.

4번의 특정 조건을 만족했다는 뜻은 스택에 실행할 모든 명령어가 저장되었다는 뜻이다.

 

이제 스택에서 명령어를 하나씩 꺼내와서 실행하면 된다.

 

지금까지는 $ra 레지스터에서 스택으로 옮겼지만 실행할 때는 스택으로부터 $ra 레지스터로 가져와서 실행한다.

1. $ra 레지스터에 $sp에 해당하는 스택의 값을 저장한다.
2. jr 명령어를 사용하여 $ra에 해당하는 명령어로 이동한다.
3. 해당 명령어를 실행한다.
4. $sp 레지스터의 값을 4 증가시킨다. (스택 포인터를 이전으로 이동시킨다. 다음 명령어를 실행할 준비)
5. 6번으로 돌아간다.

참고로 $ra는 $31과 같고 $sp는 $29와 같다.

 

이제 본격적으로 코드를 짤 차례이다.

 

먼저 기본으로 "*"문자를 메모리에 저장하고 main 함수에서 lw를 사용하여 레지스터에 저장한다.

 

그리고 정수를 하나 입력받아 t0 레지스터에 저장한다.

    .data
star : .asciiz "*"
    .text

main :
    la $s0, star
    li $v0, 5
    syscall
    move $t0, $v0

스택의 첫 위치에는 종료 코드를 넣어둔다. 마지막에는 코드를 종료해야하기 때문이다.

 

    .data
star : .asciiz "*"
    .text

main :
    la $s0, star
    li $v0, 5
    syscall
    move $t0, $v0
    jal loop
    li $v0, 10
    syscall

loop :
    bne $t0, 0, func
    beq $t0, 0, res

loop 함수의 역할은 조건에 따라 특정 함수를 실행한다.

 

이전 포스팅과 다르게 loop에서 바로 명령어를 저장하지 고 func 함수를 따로 만들어서 사용하는 이유는

 

jal을 사용하여 점프하기 전에 다음 명령어의 주소를 저장해야 하기 때문이다.

 

우리는 특정 조건을 만족할때까지 반복을 해야한다.

 

그러기 위해서는 bne와 beq 명령어를 실행해야 하는데 이 명령어들은 점프를 하긴 하지만

 

점프하기 전에 다음 명령어의 주소를 저장하지 않기 때문이다.

 

우리는 $t0 레지스터의 값이 0이 아니라면 다시 반복문으로 돌아가서 계속 다음 명령어의 주소를 저장하려고 한다.

 

그렇기 때문에 $t0 레지스터의 값이 0이 아니라면 func 함수로 이동한다.

 

func 함수가 실행되었다는 것은 $t0 레지스터의 값이 0이 아니라는 사실이 확정된 것이다.

 

그렇기에 func 함수에서는 jal을 이용하여 다음 명령어의 주소를 저장하고 점프하는 것이다.

 

func 함수는 스택에 실행할 명령어를 전부 저장하고, res 함수는 스택에 저장되어있는 명령어를 전부 실행한다.

 

포스팅 초반에 적어둔 진행 순서에 맞게 코드를 짤 예정이다.

 

func :
    sub $sp, $sp, 4
    sub $t0, $t0, 1
    sw $ra, 0 ($sp)
    
    
    jal loop

    move $a0, $s0
    li $v0, 4
    syscall

    
    lw $ra, 0 ($sp)
    addi $sp, $sp, 4
    jr $ra

스택의 첫 위치는 종료 코드가 저장되어있어 다음 스택의 위치에 저장해야하므로 $sp에서 4를 뺀다.

 

$t0를 하나 뺀다. (0이 되면 종료)

 

$ra의 값을 $sp의 값에 0을 더한 곳에 저장한다. (현재 스택 포인터 위치에 저장한다는 뜻)

 

 

 

 

 

jal loop 다음에는 move $a0, $s0 명령어가 있는데 이 명령어의 주소를 $ra에 저장하고 다시 loop로 돌아간다.

 

$t0가 0이 되기 전가지는 func 함수의 jal loop 다음의 명령어는 실행되지 않는다.

 

입력받은 값이 3이고 모든 명령어의 주소를 저장하고 나면 스택의 상태는 아래와 같다.

위와 같은 상태라면 $t0의 값은 0일 것이고 loop로 이동하면 res로 이동하라고 할 것이다.

 

res 함수는 간단하다.

 

res : 
    jr $ra

위의 스택 그림을 보고 천천히 이해해보자.

 

func :
    sub $sp, $sp, 4
    sub $t0, $t0, 1
    sw $ra, 0 ($sp)
    
    
    jal loop

    move $a0, $s0
    li $v0, 4
    syscall

    
    lw $ra, 0 ($sp)
    addi $sp, $sp, 4
    jr $ra 

 

$ra의 값은 우리가 스택에 마지막에 저장한 값이다.

 

그렇기에 $ra 명령어의 위치로 이동한다면 위 코드의 파란색과 빨간색을 순차적으로 실행한다.

 

파란색 코드는 별을 출력하는 코드이고 중요한 코드는 빨간색 코드이다.

 

현재 sp는 스택의 마지막을 가리키고 있으므로 해당 명령어를 $ra 레지스터로 가지고 온다.

 

그리고 스택 포인터를 증가시킨다. (다음 명령어를 실행하기 위해)

 

그러면 또 별을 출력하고 스택 포인터를 계속 감소시키다가 마지막으로 종료 코드를 실행하고 코드가 끝나게 된다.