22C:18, Lecture 7, Fall 1996

Douglas W. Jones
University of Iowa Department of Computer Science

Some More Hawk Instructions

The Hawk machine includes the following basic arithmetic instructions:

MOVE dst,x -- r[dst] = r[x]: The move instruction moves the contents of one register to another. See the writeup on HAWK Short Memory Reference Instructions for more detail.
ADD dst,s1,s2 -- r[dst] = r[s1] + r[s2]
SUB dst,s1,s2 -- r[dst] = r[s1] - r[s2]: The add and subtract instructions operate register-to-register, computing the 32 bit binary sum and difference of their operands. If either source register is 0, the value 0 is used. If the destination register is 0, the result is discarded. In the case of subtraction with s1=0, the result is that r[dst] gets the two's complement of r[s2]. See the writeup on HAWK Three Register Arithmetic Format Instructions for more detail.
ADDSL dst,s1,s2 -- r[dst] = r[dst]<<s2 + r[s1]: The add and shift left instruction may seem a bit odd! It shifts r[dst] to the left, equivalent to multiplying it by a power of 2, and then adds r[s1] to it. Sequences of ADDSL instructions, with a few ADD instructions thrown in, can be used to multiply by almost any common constant multiplier. See the writeup on HAWK Three Register Arithmetic Format Instructions for more detail.
ADDI dst,x,disp -- r[dst] = r[x] + sxt(disp): The add immediate instruction takes disp, a 16 bit constant, and sign-extends it to 32 bits before adding it to r[x] and putting the sum in r[dst]. Because of the sign extension, this can be used to add any two's complement integer between -32768 and 32767 to a register. See the writeup on HAWK Memory Reference Instructions for more detail. Note that this instruction is a renaming of the LEACC instruction.
ADDSI dst,const -- r[dst] = r[dst] + sxt(const): The add short immediate instruction takes disp, a 4 bit constant, sign extended to 32 bits, and adds it to r[dst], the destination register. This is the preferred way to add small constants between -8 and +7, since the instruction takes only one halfword. See the writeup on HAWK Two Register Format Instructions for more detail.

The ADDSL may be the least intuitive of these instructions. It is included in the instruction set of the Hawk computer to allow for efficient multiplication by small constants. The following examples illustrate this:

	ADDSL	R1,0,1		; R1 = R1*2
	ADDSL	R1,R1,1		; R1 = R1*3
	ADDSL	R1,0,2		; R1 = R1*4
	ADDSL	R1,R1,2		; R1 = R1*5
	ADDSL	R1,0,3		; R1 = R1*8
	ADDSL	R1,R1,3		; R1 = R1*9

To multiply by an arbitrary constant, if that number can be factored into numbers you can multiply by using individual ADDSL instructions, simply use those individual ADDSL instructions in sequence. For example:

	ADDSL	R1,0,1		;
	ADDSL	R1,R1,1		; - gives *6

	ADDSL	R1,R1,2		;
	ADDSL	R1,0,1		; - gives *10

	ADDSL	R1,R1,2		;
	ADDSL	R1,R1,2		;
	ADDSL	R1,0,2		; - gives *100

Multiplying by prime arbitrary constants are more difficult. For these, you need two registers. Consider:

	MOVE	R2,R1
	ADDSL	R2,R1,1
	ADDSL	R2,R1,1		; - gives *7

	MOVE	R2,R1
	ADDSL	R2,R1,2
	ADDSL	R2,R1,1		; - gives *11

	MOVE	R2,R1
	ADDSL	R2,R1,1
	ADDSL	R2,R1,2		; - gives *13

As a general rule, multiplication by an arbitary prime constants with x one bits in the binary representation of that constant never takes more than x+1 instructions, and when the number can be factored, it almost always takes fewer!

Note that, on machines with hardware multiplication, assembly language programmers (and compiler writers) should almost always prefer simple add or shift instructions to multiply instructions when multiplying by constants! Hardware multiply instructions almost always "break the flow" of instructions through the CPU, so they do not necessarily execute faster than a sequence of simple instructions, even when that sequence looks longer on paper.

A Programming Example

Between them, these instructions allow a wide range of computations. For example, consider writing a Hawk program to compute:

a = 5*x + 3*y + 12;

Assuming that the variable a is already in R1, x is in R2 and y is supposed to be computed in R3, this can be coded as follows in the SMAL Hawk assembly language as follows:

	ADDSL	R1,R1,2		; R1 = R1 + (4*R1)
	ADDSL	R2,R2,1		; R2 = R2 + (2*R2)
	ADD	R3,R2,R1	; R3 = R2 + R1
	ADDI	R3,R3,12	; R3 = R3 + 12

Assembling the Program

What does this look like in the memory of the Hawk computer? To translate this code to machine language, look in the HAWK Instruction Set Summary or at the more detailed writeups on these instructions in the HAWK Manual. There, you will find the bit patterns associated with each instruction:

 _______________________________________________________________
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|       |  dst  |       |   x   |              disp             |

 1 1 1 1         1 1 0 1          ADDI   r[dst] = setcc(  sxt(disp)+r[x] )
 _______________________________
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|       |  dst  |  s1   |  s2   |

 1 0 1 0                          ADDSL  r[dst] = setcc((r[dst]<<s2)+r[s1])
 0 0 1 1                          ADD    r[dst] = setcc(r[s1]+r[s2])

Translating this to hexadecimal, and putting the translation of each instruction by that instruction in our small program fragment, we get:

	A...	ADDSL	R1,R1,2		; R1 = R1 + (4*R1)
	A...	ADDSL	R2,R2,1		; R2 = R2 + (2*R2)
	3...	ADD	R3,R2,R1	; R3 = R2 + R1
	F.D.	ADDI	R3,R3,12	; R3 = R3 + 12
        ....

Here, dots have been used to indicate fields that were blank in the table. The ADDI instruction took two halfwords, so an extra row of dots has been added for the second halfword it requires.

Finally, fill in the fields shown as dots above using the arguments to each instruction, giving:

	A112	ADDSL	R1,R1,2		; R1 = R1 + (4*R1)
	A221	ADDSL	R2,R2,1		; R2 = R2 + (2*R2)
	3321	ADD	R3,R2,R1	; R3 = R2 + R1
	F3D3	ADDI	R3,R3,12	; R3 = R3 + 12
        000C

If this was loaded into the Hawk memory starting at location 1000 (hexadecimal), the result would be:

	001000: A221A112
	001004: F3D33221
	001008: ....000C

Loading this in the Hawk memory starting at locaton 1002 would give:

	001000: A112....
	001004: 3221A221
	001008: 000CF3D3

SMAL and the Hawk Macros

To use the SMAL assembly language to place these instructions in memory starting at 1000 (hexadecimal), one approach would be as follows:

	. = #001000
	W #A221A112
	W #F3D33221
	H #000C

This is unreadable! A better approach would be:

	. = #001000
	H #A112		;ADDSL	R1,R1,2	; R1 = R1 + (4*R1)
	H #A221		;ADDSL	R2,R2,1	; R2 = R2 + (2*R2)
	H #3221 	;ADD	R3,R2,R1; R3 = R2 + R1
	W #F3D3,#000C	;ADDI	R3,R3,12; R3 = R3 + 12

Here, each halfword is clearly related to the instruction that it represents, using comments to give those instructions.

An even better solution is provided by the macro feature of the SMAL language. This allows new assembler operations to be defined. As a small example, consider the followng bit of SMAL code:

	MACRO	BHW x,y,z
	  B	x
	  H	y
	  W	z
	ENDMAC

Once this fairly useless macro is defined, the code:

	BHW	5,6,7

becomes equivalent to:

	B	5
	H	6
	W	7

Similarly, we can define:

	R1 = 1
	R2 = 2

	MACRO ADDSL dst,s1,s2
	  H #A000 ! (dst << 8) ! (s1 << 4) ! s2
	ENDMAC

Having done this, we can write:

	ADDSL	R1,R2,2

When the assembler sees this, it first uses the macro definition to construct:

	  H #A000 ! (R1 << 8) ! (R2 << 4) ! 2

Formally, what it did is substitute the macro actual parameters into the macro formal parameters in the macro body. Having done this, it then substituted the values of each indentifier for those identifiers, and then evaluated the expression. Conceptually, this results in the following chain of substitutions:

	  H #A000 ! (1 << 8) ! (2 << 4) ! 2
	  H #A000 !   #100   !   #20    ! 2
	  H #A122

Note that the << operator means shift left, as in C, while the exclamation point in SMAL means or because it looks quite a bit like a vertical bar mark.

The file /group/22c018/hawk.macs/ contains macro definitions for all of the Hawk instructions.

Further documentation of macro assembly is contained in the SMAL manual section on macro assembly. In looking at this material, note that the #define mechanism in C is also a macro mechanism.