05. Stack and subroutines

Base lection in Russian

Reprise: arrays

Code reuse task

Program once, use often

• Subtasks (printing, sorting, function evaluation etc.)
• Subtask parameters (variable number, text, array size, function arguments etc.)
• Interface / implementation separation
• → Subroutine call conventions:
  • Registers integrity (before end after call, incl. PC )
  • Arguments passing
  • Result gathering

Subroutines

Subroutine: continuous part of text section, that

• Can be executed more than once
• Can be reached by jumping to from any other address of text section
• Restores caller address (jumps «back») ti continue execution

⇒ Hardware solution:

• jalr keeper_register, address_register

• jal address_offset (type i, usually it's enough; use $ra as keeper)

• jr keeper_register

   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

• When calling $ra (rarely other) keeps the address of the next cell

• Subroutine should keep $ra intact

• To return, subroutine executes jr $ra (just normal indirect jump)

What it solves:

• Atomic call
• Arbitrary call and return

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

• Stack abstraction: operations, top access, LIFO, empty/overfull states

Requirements and restrictions:

• Object is constant-sized (preferably word)
• Stack memory is «actually half-infinite»
• Stack Pointer (preferably register)

Hardware implementation:

• Super fast small stack (just a lot of registers)
• Atomic push an pop (PDP11 ++/--)
• Indirect addressing (double Indirect addressing?)

MIPS:

• Stack pointer: $sp

• Stack settles in common memory, grows from 0x7ffffffc downwards

  • Just under kernel space, so stack underflow is exception

• Stack initial pointer is 0x7fffeffc (hence 0x7ffffffc-0x7fffeffc is buffer)

• Stack lowest edge is 0x10040000 (this address is used for «heap», so it may be higher)

  • No hardware check of stack/heap overlap

• push/pop are not atomic:

  • push: first decrement $sp by 4, then store a value

  • pop: first load a value, then increment stack by 4

  • ⇒ this convention leaves 0x7fffeffc unused

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

• To read N-th item of stack we just provide N*4 offset from $sp

  • (so positive offset is easier to read)
• There's no «automatic erasing» of popped stack items, they're still there, but no guarantee in that
• No single pseudoinstruction is used!

So using stack is:

• more effective than direct lw/sw because of no pseudoinstructions

• using relative addressing over $sp and $sp is changing, so beware!

• providing constant offsets instead of labels
• fragile on stack corruption / overflow / underflow

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

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

• EJudge: CheckTriangles 'Check triangles'

  Write a subroutine check, which inputs 3 integers and checks if they can form a triangle (a=b+c is valid). Subroutine returns 1 if they can. 2 if not, and 0 if they were 0, 0, 0. Write a program that calls check and prints 'Y' on 1, or 'N'on 2, until check returns 0; then program must exit.

  Input:

  1
  2
  3
  4
  5
  6
  1
  4
  8
  0
  0
  0

  Output:

  Y
  Y
  N

• EJudge: LeftDigits 'Lefty digits'

  Write a program that inputs a cardinal N, an then inputs N numbers (may be negative). After that it outputs only first digits of these numbers (in one line). You inclined to write a subroutine "first", that accepts a number (via $a0) and returns last digit (via $v0).

  Input:

  5
  -2345
  7345623
  -4321
  2 
  7543

  Output:

  27427

• EJudge: FuncSort 'Just sort'

  Write a program, that inputs N, then N numbers, and then outputs them sorted in one line. You may write a sort subroutine, but it is not mandatory here.

  Input:

  5
  -123
  34
  546
  0
  -100500

  Output:

  -100500 -123 0 34 546

• EJudge: RecursiveGCD 'Greatest common divisor'

  Write a program that inputs two numbers and output its' Greatest_common_divisor. You must write a recursive subroutine gcd to complete this task.

  Input:

  2467080
  49360080

  Output:

  9240