Computer Architecture/컴퓨터구조[01]

[컴퓨터구조] 2. Instructions: Language of the Computer (6)

leziwn.cs 2023. 10. 8. 18:39
The jr Instruction
jr  $ra    // $ra(return address)에 저장된 주소로 jump
  • Returns control to the caller.
  • Copies the contents of $ra into the PC.

 

Calling Convention 
jal  ProcedureLabel    // 서브루틴을 호출하고, 현재의 호출 주소를 $ra에 넣는다.
jr   $ra               // The subroutine returns to its caller.

Registers

 

Main Calling Mysub Example

Main Calling Mysub Example

move  $a0, $t1     // $t1 값을 $a0로 move
li    $a1, 4       // $a1에 4를 load_integer
jal   mysub        // mysub 서브루틴을 호출하고, 현재의 주소를 $ra에 넣는다.
nop

jr    $ra          // mysub 서브루틴이 caller로 돌아온다.

 

Example 5
# Bo Cheng -- 02/08/05
# ex5.asm -- A program that exercises the function calls
            .data
            in_main_msg1: .asciiz "Before The Call\n"
            in_sub_msg: .asciiz "In Sub Program\n"
            in_main_msg2: .asciiz "After the Call\n"
            .text
main:
# Print the "before" message
            la  $a0, in_main_msg1
            li  $v0, 4    // print string
            syscall
# Call the subroutine sub_pro
            jal sub_pro
            nop          // no operation
# Print "after" message
            la  $a0, in_main_msg2
            li  $v0, 4
            syscall
# Exit the program
            li  $v0, 10    // exit
            syscall
# End of add.asm

# the subroutine body    // subroutine
sub_pro:
        la  $a0, in_sub_msg
        li  $v0, 4
        syscall
# Return the call
        jr  $ra
        nop
  • nop (no operation)
    : 'jal  subroutine' 다음에 쓰는 것
    - 사용 목적: jal과 같이 돌아와서 수행할 다음 instruction이 있는 경우, PC <- PC+4 로 먼저 수행된 상태에서, 그 다음 instruction 주소를 $ra에 저장하게 되기 때문에, jal 바로 다음에 뭔가 place hoder로 넣어두는 것이 필요하기 때문이다.

 

Example 6 - Sum
main:
     li    $s0, 0x06    // load_integer 6 to $s0
     li    $s1, 0x10    // 16
     move  $a0, $s0   // move from $s0 to $a0
     move  $a1, $s1
     jal   sum_it       // call subroutine sum_it
     nop
     
# the subroutine sum_it      // subroutine
sum_it:
       add  $t1, $a0, $a1    // $t1 = $a0 + $a1
       move $v0, $t1         // move from $t1 to $v0
       jr   $r1
       nop
       
# Get the result
     move  $s3, $v0  // move from $v0 to $s3
# Print the sum
     move  $a0, $s3  // move from $s3 to $a0
     li    $v0, 1    // $a0의 값 print
     syscall
# Exit the program
     li    $v0, 10
     syscall
# End of sum_example.asm

 

Pushing the Return Address ($ra)

: $ra의 값을 stack에 저장하고, 필요할 때 꺼내 쓴다.

Pushing the Return Address ($ra)

 

 

Chain of Subroutine Calls
  1. Push the return address in the stack.
  2. When it returns to its caller, it pops the stack to get the return address.

Chain of Subroutine Calls

 

 

Stack

Stack

  • LIFO (Last In First Out)
  • Grows from larger memory address to smaller memory address.
  • Use stack pointer ($sp = $29) to point the top of stack.

 

Push
  1. Push 연산을 수행할 때, 현재 주소보다 4 byte만큼 낮은 주소로 push하고, 메모리의 $sp를 4만큼 줄여서, 스택포인터가 push한 데이터를 가리키도록 한다.
  2. $ra 레지스터에 저장된 데이터로 메모리의 $sp가 가리키는 주소로 sw한다.
subi  $sp, $sp, 4    // subtract_immediate $sp = $sp - 4
sw    $ra, ($sp)     // store_word $ra to ($sp), $ra 값을 스택 포인터에 저장하는 것

Push

 

Pop
  1. 메모리의 $sp가 가리키는 곳에 있는 데이터를 $ra 레지스터로 lw한다.
  2. 메모리의 $sp 값을 4만큼 늘려서, $sp가 Push하기 전의 주소를 가리키도록 한다.
lw   $ra, ($sp)    // load_word ($sp) to $ra
addi $sp, $sp, 4   // add_integer $sp = $sp + 4

Pop

 

Leaf Procedure Example
// C code

int leaf_example (int g, h, i, j)
 { int f;
   f = (g+h) - (i+j);
   return f;
 }
 
// Argument g~j in $a0~$a3
// f in $s0 --> Need to save $s0 on stack
// Return in $v0
// MIPS code

leaf_example:
  addi  $sp, $sp, -4    // $sp = $sp-4
  sw    $s0, 0($sp)     // $sp에 $s0에 저장된 데이터를 sw (push)
  
  add   $t0, $a0, $a1  
  add   $t1, $a2, $a3
  sub   $s0, $t0, $t1
  
  add   $v0, $s0, $zero     // 결과를 $v0에 저장한다.
  
  lw    $s0, 0($sp)     // $sp에 저장된 데이터를 $s0에 lw (pop)
  addi  $sp, $sp, 4
  
  jr    $ra             // caller에게 return (서브루틴 수행을 마치고 돌아온다.)

 

Nested Procedure Calls (중첩된 프로시저 호출)

Nested Procedure Calls (중첩된 프로시저 호출)

 

 

Stack-based Linkage Convention

▶ Subroutine Call 

  1. Prolog of Subroutine
    - 서브루틴이 call되면: $sp값을 4만큼 줄이고, push $ra onto the stack ($sp).
  2. Subroutine Body
    - 서브루틴을 수행한다. 
    - If the soubroutine calls another subroutine, then it does by following rules.
  3. Subroutine Epilog (done by the subroutine just before it returns to the caller).
    - Put return value in $v0~$v1.

▶ Regaining control from a subroutine 

  • Pop from the stack
    : $sp가 가리키는 주소에 저장되어 있던 $ra(return address)를 pop하고, $sp를 4만큼 늘려 원래 자리로 돌려놓는다.
    - caller에 의해 수행된다.

Q. Regaining control from a subroutine == Pop from the stack이 caller에 의해 수행된다? Pop 연산은 caller가 아닌 callee에 의해 수행되며, 이 pop 연산까지 마무리되었을 때 서브루틴에서 메인 함수로 돌아가게 되고, 비로소 caller가 다시 주도권을 갖게 되는 거 아닌가요?

A. 중요한 부분 잘 질문했습니다. 우선 push한 쪽이 꺼낼 수도 있겠지요? 어디서 push했나요? caller가 push했지요? 그러니, 빼 쓰고 싶은데... 무엇을 넣었는지는 caller가 알죠. Caller가 넣은 순서대로 빼내서 사용할 수 있으므로 caller가 제어권을 갖고, stack으로부터 pop하는 주체도 caller라고 할 수 있습니다.

 

 

Pushing and Popping Registers
  • Push: If a subroutine is expected to alter any of the "S" registers, it must first push their values onto the stack.
  • Pop: Just before returning to the caller, it must pop these values from the stack back into the registers they came from.

 

The Call Chain Example
subB:
   subi  $sp, $sp, 4    // push $ra into $sp
   sw   $ra, ($sp)
   ...
   jal  subC            // call subC
   nop
   ...
   lw   $ra, ($sp)      // pop $ra from $sp
   addi $sp, $sp, 4
   
   jr   $ra             // return to caller
   nop
   
   
// SubC expects to use $s0 and $s1
// SubC does not call another subroutine
SubC:
   subi $sp, $sp, 4     // push $s0
   sw   $s0, ($sp)      // $sp에 $s0 sw
   subi $sp, $sp, 4     // push $s0
   sw   $s1, ($sp)      // $sp에 $s1 sw
   ...
   lw   $s1, ($sp)      // pop $s1
   addi $sp, $sp, 4
   lw   $s0, ($sp)
   addi $sp, $sp, 4
   
   jr   $ra             // return to subB
   nop

 

Example 7 - Find Min
main:
   li   $a0, 3     // $a0 = 3
   li   $a1, 4     
   li   $a2, 5
   jal  findMin3
   move $t0, $v0   // $v0값을 $t0로 move

// Print out the min
   move $a0, $t0   // $t0값을 $a0로 move
   li   $v0, 1
   syscall         // $a0에 저장된 값($t0: min)을 print

// Exit the program
   li   $v0, 10
   syscall
   

findMin3:
   move $t0, $a0        // $a0값을 $t0로 move
   bge  $a1, $t0, IF2   // if($a1 >= $t0), branch to IF2
   move $t0, $a1        // if($a1 < $t0), $a1값을 $t0로 move ($t0에는 min을 저장함)
   
IF2:
   bge  $a2, $t0, END   // if($a2 >= $t0), branch to END
   move $t0, $a2        // if($a2 < $t0), $a2값을 $t0로 move
   
END:
   move $v0, $t0        // $t0값을 $v0로 move (return address 저장하는 레지스터
   jr   $ra

 

Non-Leaf Procedure Example
// 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
   sw   $ra, 4($sp)
   sw   $a0, 0($sp)
   
   slti $t0, $a0, 1     // Set on Less Than Immediate, if($a0 < 1), $t0 = 1; else $t0 = 0;
   beq  $t0, $zero, L1  // if($t0 == 0) 즉 if($a0 >= 1), branch to L1
   
   addi $v0, $zero, 1   // if($t0 == 1) 즉 if($a0 < 1), result is 1
   addi $sp, $sp, 8
   jr   $ra             // 끝!
   
   
// 서브루틴 L1   
L1:
   addi $a0, $a0, -1
   jal  fact            // recursive call (재귀 호출)
   
   
   lw   $a0, 0($sp)     // restore orignal n
   lw   $ra, 4($sp)
   addi $sp, $sp, 8
   
   mul  $v0, $a0, $v0   // $v0 = $a0 *  $v0 to get result
   jr   $ra

 

 

Local Data on the Stack

Local Data on the Stack

 

 

Memory Layout

Memory Layout

  • Stack: automatic storage
  • Dynamic data: heap
    - 예) malloc in C
  • Static data: Global variables
  • Text: Program code

 

Byte/Halfword Operations

▶ MIPS byte/halfword load/store

// rs에 offset을 더한 레지스터 주소에서 1 byte 데이터를 load하고, 이를 rt에 저장한다.

// Sign extended to 32-bit in rt
lb  rt, offset(rs)     
1h  rt, offset(rs)

// Zero extended to 32-bit 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
   sw   $s0, 0($sp)           // save s[0]
   
   add  $s0, $zero, $zero     // i = 0
   
   
L1:
   add  $t1, $s0, $a1          // address of y[i] in $t1
   lbu  $t2, 0($t1)            // $t0 = y[i]
   
   add  $t3, $s0, $a0          // address of x[i] in $t3
   sb   $t2, 0($t3)            // store_byte, $t2의 가장 하위 byte 값을 $t3에 저장한다.
   
   beq  $t2, $zero, Eixt       // if(y[i]==0), branch to Exit
   
   addi $s0, $s0, 1            // i = i+1
   j    L1
   
   
L2:
   lw   $s0, 0($sp)            // restore saved $s0
   addi $sp, $sp, 4            // pop 1 item from stack
   jr   $ra

 

Brach Addressing
  • beq   $t1, $t2, L1
  • bne   $t1, $t2, L1

Most branch targets are near branch. Forward or backword.

I-type

▶ PC-relative addressing

  • Target address = PC + offset*4
  • PC already incremented by 4 by this time.

 

 

Jump Addressing
  • jal   subProcedure
  • j      $ra

Jump targets could be anywhere in text segment. 

J-format

▶ Direct jump addressing

  • Target address = PC31...28 : (address * 4)

 

Target Addressing Example
// Assume Loop at location 80000

Loop:
   sll  $t1, $s3, 2     // shift left logical, $t1 = $s3을 왼쪽으로 2번 shift
   add  $t1, $t1, $s6   // $t1 = $t1 + $s6
   lw   $t0, 0($t1)     // load $t1 값을 $t0로
   bne  $t0, $s5, Exit  // if($t0 != $s5), branch to Exit
   addi $s3, $s3, 1     // $s3 = $s3+1
   j    Loop
   
Exit: ...

 

SBY 5-1
1. When you program with a chain of subroutine calls in MIPS assembly, what is the most important thing that you should take care of?

: We should remember to save the return address in register $ra in order to go back to the main function.

  1. Place parameters(매개변수) in registers. --> $a0, $a1, $a2...
  2. Transfer control to the subroutine. --> jal  sum
  3. Acquire storage for the subroutine. (Push)
    --> addi  $sp, $sp, -4
    --> sw  $ra, 0($sp)
  4. Perform operations in the subroutine.
  5. Place results in register for the caller.
    --> $v0에 저장
  6. Pull
    --> lw  $ra 0($sp)
    --> addi  $sp, $sp, 4
  7. Perfrom the caller.
    --> jr  $ra

 

2. Can you convert the following C code to a MIPS code?
// C code

void main(){
   int a=3;     // a in $s0
   int b=4;     // b in $s1
   int c;
   
   c = sum(a,b);
}
// MIPS code

main:
   li   $s0, 3
   li   $s1, 4
   move $a0, $s0     // $s0 값을 $a0로 move
   move $a1, $s1
   
   jal  sum
   nop
   
   move $s2, $v0     // Get the result
   
   li   $v0, 10      // Exit
   syscall
   
   
sum:         
   add  $v0, $a0, $a1
   jr   $ra
   nop

 

저작자표시 (새창열림)