[top]

Advanced Topics for HMMM
(Harvey Mudd Miniature Machine)

Computer Science Department
Harvey Mudd College

Last updated 7th October 2007

Note: Not updated for 2012 HMMM rewrite.
To run code successfully in the style used below, use "OldDict" in HmmmAssembler.py.

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:
  0 # Initialize the start condition of the loop. May not be necessary in a
    # while-type loop
  1 # 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.
  2 # 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.
  3 # 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.
  4 # 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, although the hardware does not 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 store, load, and addn instructions to push and pop data. Your stack operations should look something like this:

Note that you add 1 to r15 after you push, but before you pop. 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	storei r1, r15
  2	addn r15, 1
  3	storei r2, r15
  4	addn r15, 1
  5	storei r3, r15
  6	addn r15, 1
  #	use r1-r3 for other things here
  7	addn r15, -1
  8	loadi r3, r15
  9	addn r15, -1
  10	loadi r2, r15
  11	addn r15, -1
  12	loadi 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 13 (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, 7.10.2007
#
# 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	storei	r1, r15	# Save base on stack
3	addn	r15, 1	# ..and bump stack poiinter
4	loadn	r1, 50	# Tell getNums where to read numbers
5	call	r14, 11	# Call getNums
			# ..returns address of first number in R13
6	addn	r15, -1	# Recover base from stack (fix stack pointer first!)
7	loadi	r1, r15	# ...

8	mov	r2, r13	# Address of L is second argument to calcMods
9	call	r14, 17	# Print mods
10	halt		# End of mods function

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

# calcMods function
#	r1: modulus to use
#	r2: address of list of numbers to modify
#	No return value
17	loadi	r3, r2	# Get a number
18	jeqz	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	jump	17	# ..and loop for more
23	jumpi	r14	# End of calcMods, return to caller
Here is the assembler output when given this program:
----------------------
| ASSEMBLY SUCCESSFUL |
----------------------

0  : 0001 1111 0010 1000        0       loadn   r15, 40 # Initialize the
1  : 0000 0001 0000 0001        1       read    r1      # Read base
2  : 0100 0001 1111 0001        2       storei  r1, r15 # Save base on stack
3  : 0101 1111 0000 0001        3       addn    r15, 1  # ..and bump stack
4  : 0001 0001 0011 0010        4       loadn   r1, 50  # Tell getNums where
5  : 1011 1110 0000 1011        5       call    r14, 11 # Call getNums
6  : 0101 1111 1111 1111        6       addn    r15, -1 # Recover base from
7  : 0100 0001 1111 0000        7       loadi   r1, r15 # ...
8  : 0110 0010 1101 0000        8       mov     r2, r13 # Address of L is
9  : 1011 1110 0001 0001        9       call    r14, 17 # Print mods
10 : 0000 0000 0000 0000        10      halt            # End of mods
11 : 0110 1101 0001 0000        11      mov     r13, r1 # Save start of list
12 : 0000 0010 0000 0001        12      read    r2      # Read a number into
13 : 0100 0010 0001 0001        13      storei  r2, r1  # Save number in
14 : 0101 0001 0000 0001        14      addn    r1, 1   # Step to next
15 : 1101 0010 0000 1100        15      jnez    r2, 12  # If number entered
16 : 0000 1110 0000 0011        16      jumpi   r14     # Otherwise, return
17 : 0100 0011 0010 0000        17      loadi   r3, r2  # Get a number
18 : 1100 0011 0001 0111        18      jeqz    r3, 23  # If it's zero,
19 : 1010 0011 0011 0001        19      mod     r3, r3, r1 # Calculate
20 : 0000 0011 0000 0010        20      write   r3      # Print the result
21 : 0101 0010 0000 0001        21      addn    r2, 1   # Move to next
22 : 1011 0000 0001 0001        22      jump    17      # ..and loop for
23 : 0000 1110 0000 0011        23      jumpi   r14     # End of calcMods,
This is an example of the program being run:
(1)% ./hmmmSimulator -f mods.hb -n > t
Enter number: 12
Enter number: 15
Enter number: 27
Enter number: 36
Enter number: 74
Enter number: 9
Enter number: 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.