Slide 5

📌 Programming Styles

• 용어
  • caller = main function = main routine
  • callee = procedure
• main function은 procedure에게 연산에 필요한 변수들 넘겨줌(argument)
• procedure가 특정한 코딩된 연산을 함
• 그 결과(output)를 다시 main function에게
• 이때의 variable들은 result variable이라 함

✔️ Six Steps in Execution of a Procedure

1. Main routine이 연산에 필요한 parameter를 procedure, function이 access 할 수 있는 위치에 저장하게 됨
   • $a0 (4) - $a3 (7) : 필요한 parameter 넘겨주기 위해 MIPS 연산에 사용하고 있는 총 4개의 register
2. caller가 function 실행 될 수 있게 control 넘김, procedure수행
3. callee가 필요한 storage resource들을 확보
4. 코딩된 task를 수행함
5. 수행된 결과 값은 caller가 access 할 수 있는 위치에 저장
   • $v0 (2) - $v1(3)
6. 연산을 마치고 output을 저장한 후에 function은 control을 main routine에게
   • $ra (31) : return address, main routine으로 돌아가기 위한 메모리 주소를 다시 PC에 업데이트 함으로써 돌아감

✔️ Instruction for Calling a Procedure

jal $ra // jump and link, MIPS instruction에서 procedure call 위해 쓰임

-> $ra에 PC+4 값 저장, 다시 main routine으로 return

📌 Basic Procedure Flow

• GCD는 i($t0)와 j($t1)의 최대공약수를 의미한다.

gcd (i,j);

-> MIPS

jal gcd // jump to routine gcd, caller는 i와 j를 procedure에 저장하기 위해 $a0와 $a1에 저장한다.
gcd: '''   // code to compute gcd, callee는 결과값을 $v0에 저장
	jr $ra   // return, caller $ra에 저장된 PC+4 주소값을 통해 main으로 돌아온다

📌 Spilling Registers

• callee가 할당된 argument register나 result register나 그 이상의 연산할 때 더 많은 레지스터가 필요하게 되면?
• callee 는 stack을 사용
• 일반 레지스터 중 하나인 $sp($29)는 스택(높은 주소에서 낮은 주소로 down)을 주소 지정하기 위해 사용된다.
  • data 추가 - push $sp = $sp - 4, data는 새로운 $sp위에 있다
    
  • data 제거 - pop $sp = $sp + 4
    

📌 Compiling a C Leaf Procedure - 가장 말단의 function

//C 코드
int leaf_ex (int g, int h, int i, int j)
{
	inf f;
	f = (g+h) - (i+j);
	return f;
}

//MIPS - g,h,i,j는 $a0, $a1, $a2, $a3에 저장
leaf_ex: addi $sp, $sp, -8
				 sw   $t1, 4($sp)
				 sw   $t0, 0($sp)
				 add  $t0, $a0, $a1
				 add  $t1, $a2, $a3
				 sub  $v0, $t0, $tq
				 lw   $t0, 0($sp)
				 lw   $t1, 4($sp)
				 addi $sp, $sp, 8
				 jr   $ra

📌 Nested Procedures

• procedure 내에 또 procedure가 호출 될 수 있는 nestes procedure 구조

//C 코드
int rt_1 (int i) {
	if (i == 0)
		return 0;
	else
		return rt_2(i-1); //인자값 1만큼 감소
}

//MIPS
caller: jal rt_1 //main routine으로부터 rt_1 호출, 이때 PC+4 -> $ra
next:
rt_1:   bne $a0, $zero, to_2
				add $v0, $zero, $zero // $v0에 0을 세팅해서 main routine으로 jump
				jr $ra
to_2:   addi $a0, $a0, -1
				jal rt_2 // 새로운 procedure로 jump
				jr $ra // PC+4 -> $ra
rt_2:   '''

✔️ Nested Procedures Outcome

• rt_2 수행 후 $ra에 새로운 주소값이 쓰여짐
• main routine으로의 link를 잃은 상황

📌 Saving the Return Address

• 따라서 procedure 내에 다른 procedure가 호출 됐을 때, return address나 변경된 인자값 모두 stack에 저장되어야

rt_1:bne  $a0, $zero, to_2
		 add  $v0, $zero, $zero
		 jr   $ra
to_2:addi $sp, $sp, -8
		 sw   $ra, 4($sp)
		 sw   $a0, 0($sp)
		 addi $a0, $a0, -1
		 jal  rt_2
bk_2:lw   $a0, 0($sp)
     lw   $ra, 4($sp)
     addi $sp, $sp, 8
		 jr   $ra

📌 Compiling a Recursive Procedure

• Nested procedure의 특수한 형태

int fact (int n) {
	if (n < 1)
		return 1;
	else
		return (n * fact(n-1));
}
// factorial 정의되어 있으면 이 코드는 procedure 내에서 다시 한번 이 procedure가 똑같이 호출되는 상황

이 가정에서 n은 argument register $a0을 통해 전달이 되고, 각 procedure의 output은 $v0으로 전달됨

✔️ A Look at the Stack for $a0 = 2

fact:
addi  $sp, $sp, -8
sw    $ra, 4($sp)
sw    $a0, 0($sp)
slti  $t0, $a0, 1
beq   $t0, $zero, L1
addi  $v0, $zero, 1
addi  $sp, $sp, 8
jr    $ra

L1:
addi  $a0, $a0, -1
jal fact

bk_f:
lw    $a0, 0($sp)
lw    $ra, 4($sp)
addi  $sp, $sp, 8
mul   $v0, $a0, $v0
jr    $ra

📌 Allocating Space on the Stack

📌 Allocating Space on the Heap

📌 MIPS Addressing Modes