[top]

Advanced Topics for HMMM
(Harvey Mudd Miniature Machine)

Computer Science Department
Harvey Mudd College

Last updated 23rd February 2018

Table of Contents

Introduction

This document aims at suggesting methods for implementing common programming constructs in HMMM. It also includes an example which demonstrates these concepts in action.

Loops

Loops are often useful, but implementing them can be tricky in assembly languages. In particular, it is critical to make sure that the loop jumps back to the proper point and has a means of exiting. The best strategy when implementing a loop is to reserve several registers beforehand as loop variables, and then enter the loop. Be careful not to initialize all of the loop variables in the loop, because this will most likely result in an infinite loop. The format of a basic loop is shown below:
  1 # Initialize the start condition of the loop. May not be necessary in a
    # while-type loop
  2 # Initialize the end condition of the loop. This will usually be a value to
    # compare against, but may not be necessary if two values within the loop
    # are compared against each other.
  3 # The first line of the loop. Put the loop code here, and it will be
    # executed multiple times. This line is the loop repeat target.
  4 # After the loop code, some sort of comparison must be made to decide
    # whether to jump to the loop escape target or the loop repeat target.
    # in many cases, there is no loop escape target, and the code either
    # jumps back or simply continues. In other cases, the code escapes on
    # some condition, in which case this line jumps conditionally to the
    # loop escape target.
  5 # This line jumps unconditionally to the target not referenced in the
    # previous line. In many cases, this line is unnecessary.
Here is an example loop that is the equivalent of:
for i in range(3) :
  pass
Example code:
  0 loadn r1 0    # r1 will be the register which holds i
  1 loadn r2 3    # r2 is the end condition (for a subtract)

  2 nop           # This line would be the start of the loop body
  3 addn r1 1     # increment i
  4 sub r3 r1 r2  # compare i with end condition
  5 jnez r3 2     # if the end condition is not met, loop

  6               # This is the continuing code

Register Conventions

By convention, several registers are reserved for special purposes. Register r15 is used as the stack pointer. Unlike most modern machines, the Hmmm stack grows upwards (the pushr and popr instructions use enforce this convention. Register r14 is conventionally used for function return addresses, and r13 is reserved for return values from functions. Registers r1 through r4 can be used for scratch purposes, but when calling functions they contain the function arguments. All other registers can be used at will.

Also by convention, Hmmm is a caller-save machine. That means that a called function has the right to clobber any register except r14 and r15. When you call a function, you are responsible for saving any "precious possessions" (usually on the stack) and later restoring them.

Function Calling Sequences

Although HMMM does not enforce any specific method for calling functions, the following method is recommended:

Function Entry Sequences

If you follow the function calling sequence just above, your function won't need to do anything special when it is entered. Your arguments will be in registers r1, r2, ... and your return address will be in r14. If you don't call any functions yourself, you don't need to do anything special; you are free to destroy any register except r14 and r15.

If you do call another function, you should save your own "precious possessions" (most emphatically including r14) on the stack before calling it. Often, the "precious possessions" will include your own arguments (registers r1 and up). They may also include other registers that contain intermediate results.

Function Exit Sequences

When your function is finished, put the return value in r13. Then you can return to your caller with jumpi r14. Note that you have to use jumpi, not jump, to indicate that the return address is in a register (and thus not known a priori).

Implementing a Stack

The easiest way to implement a stack is to use r15 as a stack pointer throughout the program and use pushr and popr to push and pop data. (Older Hmmm code might use storer, loadr, and addn, but that approach is much more painful.) Your stack operations should look something like this:

Note that pushr adds 1 to r15 after you push, but popr subtracts 1 before it pops. That means that the stack pointer (r15) always points to an available memory location.

Remember that multiple pops must be executed in reverse order. The following code preserves the values of registers r1, r2, and r3 on a stack that starts at address 20:

  0     loadn r15, 20
  1     pushr r1, r15
  2     pushr r2, r15
  3     pushr r3, r15
  #     use r1-r3 for other things here
  4     popr  r3, r15
  5     popr  r2, r15
  6     popr  r1, r15
Note that before the stack pointer can be used, it must be initialized with loadn to point to an empty area of memory. Although you could use a value as low as 7 (the first available empty space), it's often better to leave yourself a bit of wiggle room for later modifications, so here we chose 20.

Example

This is an example HMMM program that uses various advanced techniques. The function uses a stack for function calls, but is not recursive. The stack starts at address 40. The program also stores a list in memory, starting at address 50.

The program accepts a sequence of numbers, terminated with a 0. It then outputs each of the numbers in the same order that they were given, modulo the first number. Thus, inputs of 5, 11, 27, 3, and 8, would generate outputs of 1, 2, 3, and 3, which are 11 % 5, 27 % 5, 3 % 5, and 8 % 5. Here is the code for the program:

# mods
# created by Peter Mawhorter on 16.6.2006
# Modified by Geoff Kuenning for new Hmmm architecture, 23.2.2018
#
# The user enters a sequence of numbers, and the program prints each of those
# numbers modulo the first number.

# This Hmmm program illustrates several techniques, including:
#       1. Argument passing in registers
#       2. Function return values in registers
#       3. Saving precious registers on a stack
#       4. Storing lists of numbers in memory
#       5. Functions with no return value

# Roughly equivalent python code:

# def getNums():
#   """Returns a list of user-provided numbers until the user enters a 0."""
#   num = int(raw_input("Enter a number: "))
#   if num == 0: return []
#   else: return [num] + getNums(L)

# def printMods(base, L):
#   """Prints the list L modded by the base."""
#   if L == []: return []
#   print L[0] % base
#   calcMods(base, L[1:])

# def mods():
#   """Takes a number and a list of numbers, and prints the list mod the
#   first number. List entry ends on an input of 0."""
#   base = int(raw_input("Enter a number: "))
#   numbers = getNums([])
#   numbers = calcMods(base, numbers)
#   print numbers

# Register usage:
#
#       r1              First function argument
#       r2              Second function argument
#       r5              Address of L (for printing)
#       r13             Function return value
#       r14             Function return address
#       r15             Stack pointer

# Function "mods"
0       loadn   r15, 40 # Initialize the stack
1       read    r1      # Read base

2       pushr   r1, r15 # Save base on stack
3       loadn   r1, 50  # Tell getNums where to read numbers
4       calln   r14, 11 # Call getNums
                        # ..returns address of first number in R13
5       popr    r1, r15 # Recover base from stack

6       copy    r2, r13 # Address of L is second argument to calcMods
7       calln   r14, 17 # Print mods
8       halt            # End of mods function
9       nop             # Space for expansion
10      nop             # Space for expansion

# getNums function
#       r1: where to store the numbers read
#       Returns r1 in r13
11      copy    r13, r1 # Save start of list for return purposes
# Loop:
12      read    r2      # Read a number into r2
13      storer  r2, r1  # Save number in list
14      addn    r1, 1   # Step to next position in list
15      jnezn   r2, 12  # If number entered was nonzero, loop for more
16      jumpr   r14     # Otherwise, return to our caller

# calcMods function
#       r1: modulus to use
#       r2: address of list of numbers to modify
#       No return value
17      loadr   r3, r2  # Get a number
18      jeqzn   r3, 23  # If it's zero, we're done
19      mod     r3, r3, r1 # Calculate remainder
20      write   r3      # Print the result
21      addn    r2, 1   # Move to next number in list
22      jumpn   17      # ..and loop for more
23      jumpr   r14     # End of calcMods, return to caller
Here is the assembler output when given this program:
----------------------
| ASSEMBLY SUCCESSFUL |
----------------------

0 : 0010 1111 0010 1000             0       loadn   r15, 40 # Initialize the s
1 : 0000 0001 0000 0001             1       read    r1      # Read base
2 : 0100 0001 1111 0011             2       pushr   r1, r15 # Save base on sta
3 : 0010 0001 0011 0010             3       loadn   r1, 50  # Tell getNums whe
4 : 1011 1110 0000 1011             4       calln   r14, 11 # Call getNums
5 : 0100 0001 1111 0010             5       popr    r1, r15 # Recover base fro
6 : 0110 0010 1101 0000             6       copy    r2, r13 # Address of L is 
7 : 1011 1110 0001 0001             7       calln   r14, 17 # Print mods
8 : 0000 0000 0000 0000             8       halt            # End of mods func
9 : 0110 0000 0000 0000             9       nop             # Space for expans
10: 0110 0000 0000 0000             10      nop             # Space for expans
11: 0110 1101 0001 0000             11      copy    r13, r1 # Save start of li
12: 0000 0010 0000 0001             12      read    r2      # Read a number in
13: 0100 0010 0001 0001             13      storer  r2, r1  # Save number in l
14: 0101 0001 0000 0001             14      addn    r1, 1   # Step to next pos
15: 1101 0010 0000 1100             15      jnezn   r2, 12  # If number entere
16: 0000 1110 0000 0011             16      jumpr   r14     # Otherwise, retur
17: 0100 0011 0010 0000             17      loadr   r3, r2  # Get a number
18: 1100 0011 0001 0111             18      jeqzn   r3, 23  # If it's zero, we
19: 1010 0011 0011 0001             19      mod     r3, r3, r1 # Calculate rem
20: 0000 0011 0000 0010             20      write   r3      # Print the result
21: 0101 0010 0000 0001             21      addn    r2, 1   # Move to next num
22: 1011 0000 0001 0001             22      jumpn   17      # ..and loop for m
23: 0000 1110 0000 0011             23      jumpr   r14     # End of calcMods,
After the successful assembly, the program will automatically run. Here is an example of runnin it:
Enter number (q to quit): 12
Enter number (q to quit): 15
Enter number (q to quit): 27
Enter number (q to quit): 36
Enter number (q to quit): 74
Enter number (q to quit): 9
Enter number (q to quit): 0
3
3
0
2
9
(2)%

Contact Information

If this document is inaccurate or you believe that you have found a bug in either the assembler or the simulator, or even if you think that something should be added to any of these, please contact the CS5 staff at the usual cs5help address.