프로시저의 6가지 실행 단계

- 본 문서는 kocw [컴퓨터구조 - 영남대학교 최규상 교수님] 강의를 보고 작성하였습니다

Procedure 의 6가지 실행 단계

1. 어떤 함수를 부르는 caller, 불려지는 함수 callee -> caller가 callee 에게 액세스 할 수 있는 곳에 아규먼트를 갖다둔다
   • $a0 ~ $a3 : 4개의 아규먼트 레지스터
2. caller 가 callee 에게 프로그램 컨트롤을 넘긴다
3. callee 는 필요한 메모리 공간을 할당받는다
4. callee 가 해야할 일을 한다
5. callee 가 할 일을 다한 후 caller가 액세스할 수 있는 위치에 return 값을 저장한다
   • $v0 ~ $v1 : 리턴 값을 저장하기 위한 레지스터
6. callee 가 caller 에게 프로그램 컨트롤을 넘긴다
   • $ra : 리턴 주소가 저장되어있는 레지스터

 

레지스터의 사용

• $a0 ~ $a3 : arguments (아규먼트) -- reg's 4 ~ 7
• $v0, $v1 : result values (결과값, 리턴 값) -- reg's 2 and 3
• $t0 ~ $t9 : 임시 값 저장
  • callee 에 의해 덮어쓰기 가능
• $s0 ~ $s7 : 변수 저장
  • callee 에 의해 저장
• $gp : global pointer for static data (전역 변수 저장 공간을 가리키는 변수 저장) -- reg 28
• $sp : stack pointer -- reg 29
• $fp : frame pointer -- reg 30
• $ra : return address -- reg 31

 

Procedure Call Instructions(프로시저 호출 명령)

• Procedure call : jump and link

  • jal procedureLabel

    • 다음 명령어의 주소를 $ra 에 넣어둔다
    • target address (procedureLabel) 로 jump 한다
• Procedure return : jump register

  • jr $ra

    • $ra 레지스터로 프로그램 컨트롤이 바뀐다 ($ra 의 값을 program counter 로 복사한다)
      • program counter : 현재 실행하고 있는 명령어의 메모리 주소값을 가리키는 레지스터
• ex) 
  • Leaf Procedure Example : 다른 함수를 호출하지 않는 함수 

  • C code
    
    int leaf_example (int g, h, i, j) {
        int f;
        f = (g + h) - (i + j);
        return f;
    }

    • Argumens g, ..., j in $a0, ..., $a3
    • f in $s0 
    • result in $v0

  • MIPS code
    
    leaf_example:
        addi $sp, $sp, 04       -> 4바이트만큼 스택에 할당한다 (allocation)
        sw   $s0, 0($sp)        Save $s0 on stack
       ----------------------
        add  $t0, $a0, $a1      -> $a0 과 $a1 을 더해서 $t0 에 넣는다
        add  $t1, $a2, $a3      -> $a2 와 $a3 을 더해서 $t1 에 넣는다
        sub  $s0, $t0, $t1      -> $t0 에서 $t1 을 빼서 $s0에 넣는다     => Procedure body
       ----------------------
        add  $v0, $s0, $zero    -> $s0에 $zero를 더해서 $v0에 넣는다 -> move => Result
       ----------------------
        lw   $s0, 0($sp)
        addi $sp, $sp, 4        -> deallocation       => Restore $s0
       ----------------------
        jr   $ra                Return

 

Non-Leaf Procedures

• 다른 함수에서 호출하는 함수
• caller 가 스택에 저장해야 하는 것
  • return 주소
  • 함수에서 사용하고 있는 아규먼트(argument)
• 반한 후 다시 restore 해야 한다
• -> caller, callee 가 존재하기 때문에 Non-leaf procedure 가 더 복잡하다
• ex)

  • C code
    
    int fact (int n) {
        if (n < 1) return f;
        else return n * fact(n - 1);
    }

    • Argument n in $a0
    • Result in $v0

  • MIPS code
    
    fact:
        addi $sp, $sp, -8     # adjust stack for 2 items
        sw   $ra, 4($sp)      # save return address
        sw   $a0, 0($sp)      # save argument
       ---------------------
        slti $t0, $a0, 1      # test for n < 1
        beq  $t0, $zero, L1   
       ---------------------
        addi $v0, $zero, 1    # if so, result is 1
        addi $sp, $sp, 8      #     pop 2 items from stack
        jr   $ra              #     and return
       ---------------------
    L1: addi $a0, $a0, -1     # else decrement n
        jal  fact             # recursive call
       ---------------------
        lw   $a0, 0($sp)      # restore original n
        lw   $ra, 4($sp)      #     and return address
        addi $sp, $sp, 8      # pop 2 items from stack
       ---------------------
        mul  $v0, $a0, $v0    # mltiply to get result
       ---------------------
        jr   $ra              # and return

    • leaf-procedure 에 비해 훨씬 복잡한 MIPS 코드를 얻을 수 있다.

 

Local Data on the Stack

• 프로그램에서 함수(function)를 사용할 때 메모리가 어떤식으로 할당되는지 보여주는 그림
• $sp : stack pointer
  • 현재 스택이 있는 top 위치
• activation record : 하나의 function 을 실행할 때 할당되는 메모리 공간
• $fp : activation record 를 시작하는 처음 위치

 

Memory Layout

• Text : 프로그램 코드들(명령어)
• Static data : 전역 변수
• Dynamic data : heap
• Stack : automatic storage

 

Character Data

• Byte-encoded character sets -> 문자가 무조건 8비트에 저장
  • ASCII : 128 문자
    • 95 graphic, 33 control
  • Latin : 256 문자
    • ASCII 코드보다 96자 더 많은 문자를 가진다
• Unicode : 32-bit character set
  • java, C++ 등에서 사용
  • 세계에서 사용되는 대부분의 문자 커버 가능
  • UTF-8, UTF-16 : 다양한 길이

 

Byte/Halfword Operations

• 비트 연산에 사용
• MIPS byte/halfword load/store

  • - sign extend to 32bits in rt
    lb rt, offset(rs)         lh rt, offset(rs)
    
    - zero extend to 32bits in rt (unsigned)
    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
    • leaf-procedure
    • '\0' : null
    • char y[] 값을 char x[]에 복사

  • 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      # addr of y[i] in $t1
        lbu  $t2, 0($t3)        # x[i] = y[i]
       ------------------------
        add  $t3, $s0, $a0      # addr of x[i] in $t3
        sb   $t2, 0($t3)        # x[i] = y[i]
       ------------------------
        beq  $t2, $zero, L2     # 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