Using jump for conditional branching

jmp cond ads

cond = EQ, NEQ, LT, LE, GT, GE, ALWAYS

There are four flags in the processor: Sign, Zero, Carry, Overflow (S,Z,C,O).  Each flag is one bit.  They are like global variables.  Flags are set by ALU intructions such as, add, sub, mul, div, and, xor etc.  The ld/st instructions do not change flags.  The condition is decided by flags.  Flags are set by the previous ALU instruction.   To compare two variables, subtract instruction is used and flags S,Z will be affected.  Let two variables be in r1 and r2, "sub r0 r1 r2" will compare these variables and set the Sign and Zero flags without altering any register (because r0 is always zero). For example, EQ is true when Z = 1. LT is true when S = 1.  LE is true when S = 1 or Z = 1.  Subsequently, jump instruction can test the condition to affect the control flow. 

Example of using jump to do if...then...else

if a > b then1
  if b < c then2 e1 else2 e2
else1 
  e3

let r1 = a, r2 = b, r3 = c

	ld r1 a
	ld r2 b
	ld r3 c
	sub r0 r1 r2 ;; compare a b
	jmp GT then1 ;; if a > b then1
	e3           ;; else1
	jmp always exit
:then1 
	sub r0 r2 r3 ;; compare b c
	jmp LT then2
	e2           ;; else2
	jmp always exit
:then2 
	e1
:exit

Function call

The part of program that is reused is made into a function.  When a main program calls a function, the body of that function is executed and then the flow goes back to the main program at the location "after" the line that call that function.  This transfer of flow requires saving of the program counter (PC) which at the time of call pointed to the next instruction.  The return from a function call requires restoring PC.  There are two instructions for implementing a function call:
jump and link, jump register.

jal rx ads

jump and link save PC to rx and jump to ads.

rx = PC; PC = ads.

jr rx

restore PC from rx.

PC = rx.

rx is called a link register.  It stores PC which is called "the return address" for the function call.  It is complicate when the function is recursive because rx must then be save/restore properly.  We will concern here only the non-recursive call.

What is not mentioned here is the passing of parameters of a function call.   It involves a data structure called "activation record".  This data structure is the topic related to compiler contruction.  For simplicity, the parameters can be passed through registers, assuming that the programmer takes responsibility to allocate registers appropriately.

Example of function call.

main(){
  a = 2
  b = sq(a)
}

sq(x){
  return x * x
}

let r1 = a, r2 = b, r3 = x, r4 = retads, r5 = retvalue.

:main
	ld r1 #2
	st a r1		;; a = 2
	add r3 r1 r0 	;;  x = a 
	jal r4 sq	;; call sq()
	add r2 r5 r0 	;; b = sq(a)
	st b r2
	trap print r2
	trap stop r0
:sq
	mul r5 r3 r3
	jr r4		;; return

Note we use "add rx ry r0"  to do rx = ry (moving a value between two registers)

r4 is used as a link register to store the return address.  The passing of a parameter is done by assigning x = a ("add r3 r1 r0").  The return value is stored in r5.

12 June 2003

stack data structure 
to store link register when call hierarchically or recursively.  
saving the registers (locals of function)

stack 

push(x) :
  add sp sp #1
  st @0 sp x

x = pop() :
  ld x @0 sp
  sub sp sp #1

when multiple values are pushed into a stack, the compiler can use displacement to give an offset to the stack pointer.  The stack pointer can be adjusted at the end of the sequence:

  st @1 sp first
  st @2 sp second
  st @3 sp third
  add sp sp #3

and similary for poping multiple values:

  ld third @0 sp
  ld second @-1 sp
  ld first @-2 sp
  sub sp sp #3

Please note that the offset of sp started from 1 when push and 0 when pop due to asymmetric of two operations in terms of the initial position of sp, and the order of operands are reversed.

callee-save

The subroutine takes responsible in saving and restoring link register and all registers local to it in order not to interfere with values of the caller. 

:subroutine
  push link
  push local1
  ....
  do body of subroutine
  ...
  pop localx
  pop link
  jr link

follwing this discipline, the recursive call can be achieved without any additional action.

.s
  sp 5
  link 4
  a 100
.a 0
.c 
:main
  ld sp #200  ;; initialise sp
  ld r2 #3
  jal link fac
  st a r3
  trap stop r0

:fac
  ;; let t1 = n to do 
  ;; n * fac n - 1  is
  ;; t1 = n
  ;; n = n - 1
  ;; retvalue = call fac
  ;; retvalue = t1 * retvalue
  ;; save locals : r6 = t1
  st @1 sp link  ;; push link
  st @2 sp r6  ;; push t1
  add sp sp #2
  sub r0 r2 r0 ;; n <= 0 ?
  jmp GT else
  ld r3 #1
  jmp always ret
:else
  or r6 r2 r0 ;; t1 = n
  sub r2 r2 #1 ;; n - 1
  jal link fac
  mul r3 r6 r3 ;; n * fac n - 1
:ret
  ;; restore
  ld r6 @0 sp  ;; pop t1
  ld link @-1 sp ;; pop link
  sub sp sp #2
  jr link
.e

To elaborate more on how an expression can be transformed into sequence of "quad" instructions.
A quad is "op r1 r2 r3".    
    
How an expression be transformed into sequence of instructions

The instruction in machine language composed of operator and operands.  The number of operands vary from zero (stack instruction), one, two, three.  Our hypothetical S2 processor is a 3-operand machine.  Each instruction has the form "op r1 r2 r3", all operands are registers.  Having three operands mean each operation can take two inputs from two operands and stores the result in the third operand.  It is suitable for binary operation such as; add, sub etc.  To tranform an expression into S2 instruction, each result of a binary operation needs to store in a temporary register.

a * b + c - d

t1 = a * b
t2 = t1 + c
t3 = t2 - d

The input variables (a,b,c,d) and the temporary variables will be assigned registers.

let r1 = a, r2 = b, r3 = c, r4 = d, r5 = t1, r6 = t2, r7 = t3

the above expression can be written in S2 instructions as follows:

mul r5 r1 r2
add r6 r5 r3
sub r7 r6 r4

In fact, at most two temporary variables are needed for any arbitrary long sequence of binary operations as the temporary value can be accumulated using just one register and another register is used to hold one operand of the binary operator.

let use only t1
t1 = a * b
t1 = t1 + c
t1 = t1 - d

for any expression which has parentheses to control the order of evaluation, the expression can be transformed into postfix ordering:

(a * b) + (c * d)  

this expression is transformed into:

t1 = a * b
t2 = c * d
t1 = t1 + t2

((a * b) + (c * d)) / f)

t1 = a * b
t2 = c * d
t1 = t1 + t2
t1 = t1 / f
  
29 August 2003