Programming the Universal Machine

Fall 2012


For the assembly-language programmer, the most salient facts about the Universal Machine are these:

With these limitations in mind, I have recommended some best practices for programming the Universal Machine. The most important of these practices is a convention for implementing procedure calls, known here as the UM Stack Convention.

A note on efficiency

With only 13 instructions and 8 registers, the Universal Machine is can be somewhat difficult to program. You should not try to make your assembly code efficient:

Instead, write code that is clear and correct, with no regard for efficiency.

The stack

The UM Stack convention uses a stack just like the AMD64. Register 2 is reserved for use as a stack pointer, and stack space is allocated in array zero by the following code, found in file stack.ums: Could not read file /home/nr/cs/40/www/solutions/um/stack.ums This code also initializes the stack pointer to point to the old end of the stack. The stack grows downward, toward smaller addresses. Most assembly-language programmers will take their chances with stack overflow.

Register usage calls and returns

At the start of a procedure,

At the end of a procedure,

Programming idioms for call sites

To implement a call that in C would look like

  x = f(a, b, c);
I recommend that you write
  push c on stack r2
  push b on stack r2
  push a on stack r2
  goto f linking r1
  x := r1
  r2 := r2 + 3 // pop a, b, and c off the stack
After this sequence you should remember that values in r5, r6, and r7 may have been destroyed.

Idioms for use of registers

Many of the interesting macro instructions require at least two temporaries; some of the conditional branches can require four or more. As a matter of convention, I suggest that you reserve r0 to be zero and r6 and r7 as temporaries. You can do this by

  .zero r0
  .temps r6, r7
If you need more temporaries, the Macro Assembler will work just as well if r0 is a temporary:
  .zero off
  .temps r0, r6, r7
But this tactic creates an additional obligation; before returning from a procedure, you must restore r0:
  .temps r6, r7
  r0 := 0
  .zero r0

Finally, for a conditional branch, you might need extra temporaries:

  if (r3 <s a[r0][r2+1]) goto next using r1, r4, r5;
The using clause applies only to that instruction, but values in r1, r4, and r5 will be lost.

Programming idiom for a big procedure

If you're writing a big procedure, you'll want maximum use of all the registers. Here's a very general idiom for a procedure f that returns a result called result:

  .zero r0
  .temps r6, r7
  f: // entry point for the function f
  push r1 on stack r2 // save return address
  push r3 on stack r2
  push r4 on stack r2
  // first argument is now in a[r0][r2+3]

  ... body of procedure f, which computes results ...

  r1 := result
  pop r4 off stack r2
  pop r3 off stack r2
  pop r5 off stack r2 // restore return address into r5
  goto r5
If you need even more registers, you can make r0 a temporary and end with
  pop r5 off stack r2
  r0 := 0
  .zero r0
  goto r5

Idiomatic use for sections

Most programs will get by with four sections: