Computer Architecture_MIPS Code Examples(1)

DP 프로그래밍에서 재귀함수를 이용했어요. 재귀함수 호출이 메모리에 어떻게 할당되는지 단계들을 살펴보면 복습에도 좋을 것 같아서! 다뤄보고자 합니다. 

큰 그림은 다음 4 단계로 이루어집니다. 

(1) High level language to assmebly
(2) Pipeline에서 어셈블리어의 실행
(3) CPU에서 Cache Memory 이용
(4) TLB와 Page Table의 실행 과정  

기회가 된다면 File system 실행도 다뤄보고 싶어요! (먼 산)

---

1. Translating from C to assembly language

High level 언어를 어셈블리어로 변형해주어야 하는데요. 기계는 binary data를 읽고 쓸 수 있기 때문에 '문 열려있으면 닫아줘'를 01011010101로 바꾸어줘야 합니다. 그때 사용되는 것이 어셈블리어입니다. 

• 적절한 예시인지 헷갈리지만.. 예를 들자면 한국어를 일본어로 바꿔야 합니다.
  저는 한국인이니까 한국어를 쓰겠죠. 근데 일본인은 한국어를 이해하지 못합니다. 근데 한국어를 계란으로 바위 내려치듯이 일본어로 번역하는 것은 상당히 복잡한 과정입니다. 그래서 일단 한본어로 한번 바꿔주는 것입니다. 강유미의 한본어는 한국어도, 일본어도 아니지만 양국 모두에게 이해될 수 있다는 점에서 의미가 있습니다.
  결론: text data 가 0101로 가기 위한 가공 과정이라고 이해하면 되겠습니다.
• Source file > Assembler > Object file 과정으로 binary file이 생성되고 이를 Linker가 합쳐서 Executable file이 된다. 

이제 코드를 보시죠! 재귀 호출 함수구요. 

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

fact (n-1) 에 진입한 순간에 다시 fact 함수로 들어오는 함수입니다. 레지스터는 하난데 동일 함수를 clone으로 만들면 $ra와 $a0의 값이 충돌이 일어날 수 있기 때문에 주의해주어야 하는데요. 

첫 번째 함수에서 쓴 n의 값이, 2번 clone에서  사용되는 n의 값과 차이가 있잖아요. 근데 동일 레지스터를 쓰니까 값의 충돌이 있을 수 있어요. 같은 맥락으로 $ra(복귀할 주소)도 마찬가지

 

그래서 각 cycle에서 저장해놔야 하는 return address랑 n의 값은 stack에 저장해 놓는데요. 간략하게 보면

#지금 3rd recursive 함수에 있다는 가정

fact:
#지금 cycle이 끝나고 다시 사용해야 할 $ra와 $a0를 저장하기 위한 공간을 할당하는 중입니다.
	addi $sp, $sp, -8 
	sw $ra, 4($sp)
	sw $a0, 0($sp) 
#$ra와 $a0을 저장했어요

#if (n>1) 부분
	slti 작으면 1, 크면 0
	beq 크면 Loop 부분 코드로 이동

#else 지금 3rd가 아니라 마지막 단계라 return 1을 해야하는 경우
	addi $v0에다가 return용 1을 넣고요
	addi $sp, $s, 8 
    #이번 cycle은 return 되었으니 $a0과 $ra가 들어있는 $sp 공간은 원상복구해줍니다.
	jr $ra
    #int fact를 호출한 위치로 jump

(Q. 코드 내부에서 $ra 와 $a0 변경하는 부분이 없는데 왜 따로 저장했을까요?) 그건 L1을 다중진입한 경우에 이해가 됩니다. 

전체 어셈블리어 코드를 보면서 흐름을 파악해 봅시다. 

fact:
    addi $sp, $sp, -8
    sw $ra, 4($sp)
    sw $a0, 0($sp)
    slti $t0, $a0, 1
    beq $t0, 0, L1
    addi $v0, $zero, 1
    addi $sp, $sp, 8
    jr $ra #return to caller
L1: 
    addi $a0, $a0, -1 #n >= 1: argument gets (n-1)
    jal fact
    lw $a0, 0($sp) #return form jal : restore argument n
    lw $ra, 4($sp) #restore the return address
    addi $sp, $sp, 8 #adjust stack pointer to pop 2 items
    mul $v0, $a0, $v0 # return n * fact (n-1)
    jr $ra # return to the caller

if (n >= 1) 이라 L1 부분으로 들어가야 한다면, fact (n-1) 이니까 n이 변경되죠. 그래서 (변경된) n-1 값을 stack pointer을 옮겨 저장해 줍니다. 

jal 부분은 fact 부분에 다녀왔다가 바로 jal fact 밑으로 되돌아오는 기능이 있는데요. 그래서 callee 진입 시 사용한다고 하는 겁니다. 만약에 fact(n-1)를 타고 타고 가다가 결국에 fact(0)까지 왔다고 해봅시다. $v0에 1을 넣고 jr $ra 하는 부분에 return 1을 해버리는 것이 아니라 L1:의 jal fact 다음 부분으로 돌아와 fact(0)이 되기 전 모든 주소(calle)로 돌아가게 됩니다.

• jal (jump and link) (calle 진입 시 사용) jal의 다음 명령어 주소를 $ra에 저장하고 [addr]로 점프. 

 fact 첫 부분에서 $sp - 8 하면서 재사용할 값인 $a0 ( = n-1)과 $ra를 저장했던 부분 값을 받아옵니다. 지금 값을 받아왔으니 $sp는 +8 해서 원상복구 해주시구. 지금 막 $v0에 1을 저장했다는 것은 fact (0)까지 왔다는 것이니 fact (1)부터 차근차근 가봅시다. 

fact (1)는 $v0의 1과 $a0의 n (1)을 곱해서 L1; jal fact 밑 코드를 찾아갑니다. 그럼 또 $a0은 n=2일 때의 값을 가집니다. fact(1)은 방금 곱해서 얻은 f(0)과 2를 곱한 (1*2) 2을 주겠죠. 이런 식으로 $sp 가 할당했던 만큼 $v0에 다 곱해 놓고, $sp 공간도 반환합니다. 모든 과정이 끝나면 정말로 int fact를 호출했던 caller로 돌아가게 되면서 끝이 나겠네요. 

총정리

int fact는 같은 공간을 여러 데이터로 사용되는 함수이기 때문에, fact의 각 cycle에서 사용되는 레지스터의 값은 $sp을 늘려가면서 각각 따로 저장해 놓습니다. 그리고 이를 함수에 들어갈 때마다 사용하는 것이 아니라, 마지막에 return 할 때 한 번에 $sp + 8 하면서 모든 저장된 $ra와 $a0를 loading해서 반환하는 형식을 택합니다. 이를 통해 레지스터에 저장되는 값의 충돌을 막는 것이죠. 

• $ra 와 $a0가 stack에 저장되는 것이 매 cycle 마다 독립된 공간에서 이뤄지고, 이를 마지막 return에 한 번에 연산하면서 값의 충돌을 막습니다. 

 

Stack이 뭔가요?

 Stack이란 함수 내에서 생성된 변수를 저장하는 공간인데요. 예를 들어 local arrays 등을 저장하는 공간입니다. 함수가 종료되면 같이 사라진다는 특징이 있어요. 

저희가 계속 $sp를 옮겨가면서 변수 값을 저장했잖아요. 그게 어떻게 가능하나면, Stack pointer은 저장되는 값을 채우거나(push) 꺼낼 때(pop) 변화하기 때문에 가능한 겁니다. 그런데 말입니다.. $sp가 변수가 생성될 때마다 위치가 변경되면 초기 시작 위치랑 달라질 수도 있잖아요. 그걸 막고자 $fp (Frame pointer) 개념도 같이 쓰입니다. 

• MIPS에서 jr이나 beq처럼 이동할 때, base register에 address를 더해서 이동하는 방식이 있어요. 그때 $sp가 오류가 나서 처음 시작값과 다른 위치를 가지게 되면 오류가 나잖아요. local variables(주소나 데이터)를 가진 레지스터가 필요한데 엉뚱한 곳을 가리키면 안 되니까요. 그래서 Frame pointer로 procedure frame의 첫 word 값을 가리키는 $fp를 가집니다. 

 

*word와 frame은 나중에 더 자세히 설명할게요. (된다면요..) word는 데이터의 단위 (주로 명령어를 읽는 단위)이고 frame은 physicla memory에서 효율적인 사용을 위해 사용된 개념이에요. block을 이용한 메모리의 단위입니다. 이는 이후 virtual memory (OS)와 연관됩니다.