명령어(Instructions)[3]

하드웨어의 프로시저 지원 Procedure Calling

procedure?
In computer programming, a subroutine is a sequence of program instructions that perform a specific task, packaged as a unit. In different programming languages a subroutine may be called a procedure, a function, a routine, a method, or a subprogram.
'특정 작업을 수행하기 위한 instruction들의 연속'

• 프로시저(procedure)나 함수는 이해하기 쉽고 재사용이 가능하도록 프로그램을 구조화하는 방법 중 하나이다.

• 인수(parameter)는 프로시저에 값을 보내고 결과를 받아오는 일을 하므로,
  프로그램의 다른 부분 및 데이터와 프로시저 사이의 인터페이스 역할을 한다.

  • 프로시저 = 스파이
    스파이는 비밀 계획을 가지고 출발해서, 필요한 자원 획득하여 임무 완수하고, 흔적을 없앤 후 원하는 결과를 가지고 출발 장소로 되돌아온다.
    지정된 임무 수행하는 것 외에 다른 것은 아무것도 건드리지 말아야 한다.

• Steps

  1. Place paramters in registers
     프로시저가 접근할 수 있는 곳에 인수를 넣는다
  2. Transfer control to procedure
     프로시저로 제어를 넘긴다
  3. Acquire storage for procedure
     프로시저가 필요로 하는 메모리 자원을 획득한다
  4. Perform procedure's operations
     필요한 작업을 수행한다
  5. Place result in register for caller
     호출한 프로그램이 접근할 수 있는 장소에 결과 값을 넣는다
  6. Return to place of call
     원레 위치로 제어를 돌려준다

• Register Usage

  • $a0 - $a3 : arguments
    : 전달할 인수를 가지고 있는 인수 레지스터 4개
  • $v0, $v1 : result values
    : 반환되는 값을 갖게 되는 값 레지스터 2개
  • $t0 - $t9 : temporaries
    • can be overwritten by callee
  • $s0 - $s7 : saved
    • must be saved/restored by callee
  • $gp : global pointer for static data
  • $sp : stack pointer
  • $fp : frame pointer
  • $ra : return address
    : 호출한 곳으로 되돌아가기 위한 복귀 주소를 가지고 있는 레지스터 1개

---

Procedure Call Instructions

• Procedure call : jump and link
  : 지정된 주소로 점프하면서 동시에 다음 주소를 $ra 레지스터에 저장한다.<
  jal ProcedureLabel
  • Address of following instruction put in $ra
  • Jumps to target address

    link : 프로시저 종료 후 올바른 주소로 되돌아올 수 있도록 호출한 곳과 프로시저 사이에 링크를 형성한다.

• Procedure return : jump register
  jr $ra
  • Copies $ra to program counter

    프로그램 카운터(Program counter, PC) : 실행 중인 명령어의 주소를 가지고 있는 레지스터

  • Can also be used for computed jumps. (for case/switch statements)

---

Leaf Procedure Example

• C code :

int leaf_example (int g, h, i, j) {
	int f;
    f = (g + h) - (i +  j);
    return f;
}
// Arguments g, ..., j in $a0, ..., $a3
// f in $s0 (hence, need to save $s0 on stack)
// Result in $v0

• MIPS code :

leaf_example : // 프로시저 레이블
	addi $sp, $sp, -4 // 스택에 $s0를 저장할 자리를 만든다
    sw $s0, 0($sp) // save $s0 on stack for use afterwards
    add $t0, $a0, $a1 // Procedure body
    add $t1, $a2, $a3
    sub $s0, $t0, $t1  // f = t0 - t1
    add $v0, $s0, $zero // return f. f를 결과 값 레지스터에 복사한다.
    lw $s0, 0($sp) // restore $s0. 전에 저장해 두었던 값을 스택에서 꺼내 레지스터를 원상 복귀한다
    addi $sp, $sp, 4 // adjust stack to delete 1 item
    jr $ra // jump back to calling routine

---

• 스파이는 때로 다른 스파이를 고용하여 일의 일부를 맡기고, 그 스파이는 또 다른 스파이를 고용할 수 있다.
• 이처럼 프로시저도 다른 프로시저를 호출할 수 있고, 심지어는 자기 자신을 호출하는 recursive 프로시저도 있다.

• 여러 프로시저를 호출하면서 생기는 문제를 피하기 위해,
  값이 보존되어야 할 모든 레지스터를 스택에 넣는다.
• 호출 프로그램은 인수 레지스터(a0 - a3)와 임시 레지스터(t0 - t9) 중
  프로시저 호출 후에도 계속 사용해야 하는 것을 모두 스택에 넣는다
• 피호출 프로그램은 복귀 레지스터(ra)와 저장 레지스터(s0 - s7) 중
  피호출 프로그램이 사용하는 레지스터를 모두 저장한다.
• 스택 포인터 $sp는 스택에 저장되는 레지스터 개수에 맞추어 조정된다.
• 복귀 후에는 메모리에서 값을 꺼내 레지스터를 원상 복구하고, 이에 맞추어 스택 포인터를 다시 조정한다.

Non-Leaf Procedure Example (가장 어렵다)

• C code :

int fact(int n) {
	if (n < 1)
    	return 1;
    else
    	return n * fact(n - 1);
}
// Argument n in $a0
// Result in $v0

인수(argument) vs 인자( = 매개변수. parameter)

• MIPS code :

fact :
	addi $sp, $sp, -8 // adjust stack for 2 items
    sw $ra, 4($sp) // save the return address
    sw $a0, 0($sp) // save the argument n
    
    slti $t0, $a0, 1 // test for n < 1 => n < 1이면 t0 = 1
    beq $t0, $zero, L1 // t0 == 1이면 (즉, n >= 1이면) go to L1
    
    addi $v0, $zero, 1 // 넘어왔다는 건, n < 1일 때. return 1
    addi $sp, $sp, 8 // pop 2 items off stack
    jr $ra // return to caller
    
L1 :
	addi $a0, $a0, -1 // argument gets n-1
    jal fact // call fact with n-1
    
    lw $a0, 0($sp) // return from jal : restore argument n
    lw $ra, 4($sp) // restore the return address
    addi $sp, $sp, 8 // adjust stack pointer to pop 2items
    
    mul $v0, $a0, $v0 // return n * fact(n-1)
    
    jr $ra // return to the caller

---

데이터를 위한 스택 공간의 할당 Local Data on the Stack

• 레지스터에 들어가지 못할 만큼 큰 배열/구조체 같은 local 변수를 저장하는 데도 스택이 사용된다.
• 프로시저의 저장된 레지스터와 local 변수를 가지고 있는 스택 영역을 프로시저 프레임(procedure frame)이라고 한다.

• 프로시저 호출 전, 중, 후의 스택 상태이다.
• fp (frame pointer) : 프로시저 프레임의 첫 번째 워드를 가리킨다.

---

Memory Layout

• Stack : 스택은 최상위 주소에서부터 시작해서 아래쪽으로 자란다
• Reserved : 최하위 주소 부분은 사용이 유보되어 있다.
• Text : MIPS 기계어 코드가 들어간다.
• Static data : global variables, constant array, string. 상수와 기타 정적 변수들.
• Dynamic data : linked list와 같은 자료구조를 위한 세그먼트. 전통적으로 힙(heap)이라고 불린다.

• Stack과 Heap이 마주보며 자라도록 할당하기 때문에 메모리를 효율적으로 사용한다.

---

Byte / Halfword Operations

MIPS byte/halfword load/store

• Sign extend to 32 bits in rt
  lb rt, offset(rs)
lh rt, offset(rs)

• Zero extend to 32 bits in rt
  lbu rt, offset(rs)
lhu rt, offset(rs)

• Store just rightmost byte/halfword
  sb rt, offset(rs)
sh rt, offset(rs)

String Copy Example

• C code :

void strcpy (char x[], char y[]) {
	int i;
    i = 0;
    while ( (x[i] = y[i]) != '\0' )
    	i += 1;
}
// addresses of x, y in $a0, $a1
// i in $s0

• MIPS code :

strcpy :
	addi $sp, $sp, -4 // adjust stack for 1 item
    sw $s0, 0($sp) // save $s0
    add $s0, $zero, $zero // i = 0;
    
L1 :
	add $t1, $s0, $a1 // address of y[i] in $t1
    lbu $t2, 0($t1) // $t2 = y[i]
    add $t3, $s0, $a0 // address of x[i] in $t3
    sb $t2, 0($t3) // exit loop if y[i] == 0
    addi $s0, $s0, 1 // i = i + 1
    j L1 // next iteration of loop
    
L2 : 
	lw $s0, 0($sp) // restore saved $s0
    addi $sp, $sp, 4 // pop 1 item from stack
    jr $ra // and return

---