05. Stack and subroutines

Base lection in Russian

Reprise: arrays

Code reuse task

Program once, use often

Subroutines

Subroutine: continuous part of text section, that

⇒ Hardware solution: 

   1 # text section starts
   2 #    …
   3         li    $t1 5
   4         li    $t2 6
   5         li    $t3 7
   6 # now calling subroutine
   7         jal    treug
   8 # do something else
   9 #    …
  10 # Exit from orpgram
  11         li     $v0 10
  12         syscall
  13 #    …
  14 # Subroutiine
  15 treug:  move   $t0 $zero
  16         add    $t4 $t1 $t2
  17         add    $t5 $t2 $t3
  18         add    $t6 $t3 $t1
  19         bgt    $t3 $t4 not
  20         bgt    $t1 $t5 not
  21         bgt    $t2 $t6 not
  22         li     $t0 1
  23 not:    jr     $ra

What it solves:

What it solves not:

  1. Transparency of reuse:
    • Register integrity
    • Arguments passing
    • Return value gathering

    • /!\ Label names clash (when accidentally using the same name of label in both main code and subroutine)

  2. Subsequent and recursive call (the only $ra)

⇒ All these are matter of convention, except /!\, which needs assembler to support «local» labels or namespaces

Terminal subroutine convention

Terminal subroutine must not call other subroutines.

  1. Subroutine S is terminal

  2. S is called by $jal

  3. Return from S is performed by $jr $ra

  4. Register usage:

    • $t0 - $t9 — temporary, can modify upon return

    • $s0 - $s7 — static, can not modify upon return

    • $a0 - $a3 — arguments

    • $v0 - $v1 — return values

No restriction of memory modification.

This subroutine uses terminal subroutine convention: 

   1 #    …
   2         li    $a0 5
   3         li    $a1 6
   4         li    $a2 7
   5 #    …
   6         jal    treug
   7 # keep the result in static register
   8         move    $s1 $v0
   9 #    …
  10         li     $v0 10
  11         syscall
  12     …
  13 # Subroutine
  14 treug:  move   $v0 $zero
  15         add    $t4 $a0 $a1
  16         add    $t5 $a1 $a2
  17         add    $t6 $a2 $a0
  18         bgt    $a2 $t4 not
  19         bgt    $a0 $t5 not
  20         bgt    $a1 $t6 not
  21         li     $v0 1
  22 not:    jr     $ra

Stack

Requirements and restrictions:

Hardware implementation:

MIPS:

Commands example 

   1 li              $t1,            123          # something
   2 addi            $sp,            $sp,    -4   # push.1
   3 sw              $t1,            ($sp)        # push.2
   4 addi            $t2,            $t1,    100  # another something
   5 addi            $sp,            $sp,    -4   # push.1
   6 sw              $t2,            ($sp)        # push.2
   7 lw              $t3,            ($sp)        # read stack edge
   8 lw              $t4,            4($sp)       # read second stack value
   9 lw              $t0,            ($sp)        # pop.1
  10 addi            $sp,            $sp,    4    # pop.2
  11 addi            $sp,            $sp,    -4   # push.1
  12 sw              $zero,          ($sp)        # push.2

So using stack is:

Universal subroutines

  1. Subsequent and recursive calls ⇒ we need to keep every old $ra values somewhere.

  2. If we need memory in addition to registers, it should be call-specific

  3. If we modify $s-type registers, we need to keep/restore them

It can be done with stack. 

   1 .data
   2 n:      .word 7
   3 res:    .word 0
   4 
   5 .text
   6 # call fact:
   7         lw      $a0 n
   8         jal     fact
   9         sw      $v0 res
  10 
  11 fact:   addiu   $sp $sp -4      # keep $ra
  12         sw      $ra ($sp)
  13         addiu   $sp $sp -4      # keep $s0
  14         sw      $s0 ($sp)
  15 
  16         move    $s0 $a0         # calculate n-1
  17         subi    $a0 $a0, 1
  18         ble     $a0 1 done      # if n<2, done
  19 
  20         jal     fact            # calculate fact(n-1)
  21         mul     $s0 $s0 $v0     # $s0 survives a call
  22 
  23 done:   move    $v0, $s0        # return value
  24         lw      $s0 ($sp)       # restore $s0
  25         addiu   $sp $sp 4
  26         lw      $ra ($sp)       # restore $ra
  27         addiu   $sp $sp 4
  28         jr      $ra

Trace this program by Mars and observe how $sp and stack memory is changed.

Universal simple convention

  1. $a registers for arguments

  2. Call with jal or jalr

  3. Do not write to the stack above the point it was set when the subroutine is called

  4. $ra should be kept in stack

  5. Return value is stored in $v0 (and $v1)

  6. Used $s registers must be kept on stack

  7. All additional memory to use is taken from stack (at any time and actually unlimited)

  8. Program restores $sp to its initial state (pointing to return address) before return (all memory above old $sp is considered free)

  9. Program restores $ra and $s registers from stack

  10. Return with jr $ra

    11. Prologue
    initial part of subroutine code, which stores program state (keeps registers etc.)
    Epilogue
    final part of subroutine code, which restores program state (loads registers etc.)
    Preamble

    part of caller code just before jal subroutine preparing some subroutine-specific environment

Example with preamble, that narrows prologue and epilogue: 

   1 fact:   addiu   $sp $sp -4      # keep $ra
   2         sw      $ra ($sp)
   3 
   4         move    $t0 $a0
   5         subi    $a0 $a0, 1
   6         ble     $a0 1 done
   7 
   8         addiu   $sp $sp -4      # keep N
   9         sw      $t0 ($sp)
  10         jal     fact
  11         lw      $t1 ($sp)       # keep N
  12         addiu   $sp $sp 4
  13         mul     $t0 $t1 $v0
  14 
  15 done:   move    $v0, $t0        # return value
  16         lw      $ra ($sp)       # restore $ra
  17         addiu   $sp $sp 4
  18         jr      $ra

H/W

TODO

HSE/ArchitectureASM/05_StackAndSubroutines (последним исправлял пользователь FrBrGeorge 2019-11-29 18:29:55)