Example 3: Machine Language for the RiSC-16

This example explains how an assembler takes an assembly file and resolves symbolic addresses to turn the assembly code into machine language. It also hints at the translation from C code to assembly code that a compiler would perform, but it does not go into detailed explanation of that -- it is mostly hand-waving, since high-level language compilers are a huge topic for another course.

In this example, we will trace a piece of C code to assembly code and then to machine language. We are mostly interested in the translation from assembly to machine language, but the C code helps to show exactly what the purpose of each instruction is. We will use the RiSC Level-0 assembly code in this example, since it is far simpler than the MIPS assembly code, and since your first assignment is to build a RiSC Level-0 assembler, to build a RiSC Level-0 simulator, and to write a short piece of code in RiSC Level-0 assembly code. Once you understand this (relatively) simple language, we will move into the slightly more complex MIPS assembly code.

The following is a piece of C code that simply moves through an array A, one item at a time. It compares the value found at the ith element of array A to the constant k -- if they are equal, we move to the next element; if they are not, we exit the loop.

```	int A[10];
int i=0;
int j=1;
int k=0;

while (A[i] == k) {
i = i + j;
}
```
First, remember that an "integer" in the world of the RiSC is a 16-bit (2-byte) quantity. Also remember that the RiSC is a word-addressed machine, not a byte-addressed machine, therefore memory address 0 refers to the first 2-byte word in memory, address 1 refers to the second 2-byte word in memory, etc.

The following is an equivalent piece of RiSC assembly code.

```		lw	1, 0, i		# reg 1 <- value of i
lw	2, 0, j		# reg 2 <- value of j
lw	3, 0, k		# reg 3 <- value of k
loop:	lw	4, 1, A		# reg 4 <- i + A (A [i])
beq	4, 3, 1		# if A[i] == k, jump ahead to PC+1+1
add	1, 1, 2		# i = i + j
exit:	halt			# when while-loop finishes, halt
i:	.fill	0		# int i = 0;
j:	.fill	1		# int j = 1;
k:	.fill	0		# int k = 0;
A:	.fill	0		# int A[10];  (this is A[0])
.fill	0		# int A[10];  (this is A[1])
.fill	0		# int A[10];  (this is A[2])
.fill	0		# int A[10];  (this is A[3])
.fill	0		# int A[10];  (this is A[4])
.fill	0		# int A[10];  (this is A[5])
.fill	0		# int A[10];  (this is A[6])
.fill	0		# int A[10];  (this is A[7])
.fill	0		# int A[10];  (this is A[8])
.fill	0		# int A[10];  (this is A[9])
```

How the assembly code relates to the C code

The individual integers i, j, and k are each created by a .fill directive, which tells the assembler to create a (2-byte) word-sized value and place it at this spot, rather than an instruction. The array A is created by a whole bunch of .fill directives; since there are 10 items in the array, there are 10 .fill directives. By default, we have initialized the values in the array to zero.

Note that in RiSC code, we place the data at the end of the program; this is simply a convention that allows the RiSC to start executing at location 0 as soon as the program is loaded. However, real-world machines might not behave this way; it is not a rule, it is just the convention that we use in this simple computer.

The first thing that the assembly code does is load all of the variables: i, j, and k. This is done with the load-word instruction, lw. Each of the first three lines adds the value of the label i, j, or k to the value found in register 0 (it will always contain zero) and loads the value from memory found at this address; therefore the first three loads simply load values found at memory locations i, j, and k.

```		lw	1, 0, i		# reg 1 <- value of i
lw	2, 0, j		# reg 2 <- value of j
lw	3, 0, k		# reg 3 <- value of k
```
After the variables are loaded, at the "loop" label, we load a value from array A. The instruction says to add the location of A to the value found in register 1 (variable i, which at this point has the value 0), and use the sum as a memory address.
```	loop:	lw	4, 1, A		# reg 4 <- i + A (A [i])
```
This gives us the address for A[0] (the first item in A) -- we load the value found at this address and place it into register 4. Register 4 now contains the value A[i], and in this instance i=0, so register 4 has A[0]. The next time we execute the loop, we will branch back to this instruction, which will again load A[i], but in later instances the value of i might have changed; in particular, the next time around, the value in register 1 will be 1 (i=1), therefore when we execute this instruction, we will load the value A[1].

Back to the present -- we have just loaded the value A[0] into register 4. Using the branch-if-equal instruction, beq, we compare the value of A[0] (in register 4) to the value of k (in register 3):

```		beq	4, 3, 1		# if A[i] == k, jump ahead to PC+1+1
```
and if they are equal we branch over the following instruction:
```		beq	0, 0, exit	# otherwise, unconditional jump to exit
```
which exits the while-loop. If the value in k is not equal to the value in A[i], the first branch is not taken and control falls through to the second branch, which is an unconditional jump to the label exit. It is considered unconditional because the jump occurs if the value in register 0 is equal to itself (it always will be).

If A[i] == k, then the first branch instruction succeeds and we jump past the jump-to-exit instruction to the following two instructions:

```		add	1, 1, 2		# i = i + j
```
The add increments register 1 (variable i) by the value in register 2 (variable j), or i = i + j. The following beq instruction is an unconditional jump to the beginning of the loop, where the process starts again at the point of loading the next entry in array A.

How the assembler translates the assembly code to machine code

On the first pass, the assembler assigns addresses to each of the instructions and labels. For instance, the following addresses work perfectly well:
```	0:		lw	1, 0, i
1:		lw	2, 0, j
2:		lw	3, 0, k
3:	loop:	lw	4, 1, A
4:		beq	4, 3, 1
5:		beq	0, 0, exit
7:		beq	0, 0, loop
8:	exit:	halt
9:	i:	.fill	0
10:	j:	.fill	1
11:	k:	.fill	0
12:	A:	.fill	0
13:		.fill	0
14:		.fill	0
15:		.fill	0
16:		.fill	0
17:		.fill	0
18:		.fill	0
19:		.fill	0
20:		.fill	0
21:		.fill	0
```
At this point, the assembler has made the following connections:
```	loop ->  address 3
A    ->  starts at address 12
```
Aside: Here is a subtle point that is interesting, but it is not necessary for understanding how assemblers work. The assembler does not realize that A is in fact an array; it merely knows where the label A is, and that it is followed by a whole bunch of integers. The assembler does not need to know how A is being used; that is up to the compiler, or the writer of the assembly code. The assembler just does what it is told (create an integer with label A and follow it with 9 more integers), and it assumes that the author of the assembly code (either a compiler or a human) knows what it is doing.

On the second pass over the code, the assembler replaces the labels:

```	0:		lw	1, 0, 9
1:		lw	2, 0, 10
2:		lw	3, 0, 11
3:		lw	4, 1, 12
4:		beq	4, 3, immed(1)
5:		beq	0, 0, 8
7:		beq	0, 0, 3
8:		halt
9:		0
10:		1
11:		0
12:		0
13:		0
14:		0
15:		0
16:		0
17:		0
18:		0
19:		0
20:		0
21:		0
```
We will get to the "immed(1)" in a moment.

Each lw assembly-code instruction has the following format:

```	lw     regA, regB, immed
```
and the first four instructions get translated to the Load-Type machine-code instruction format:
```        opcode:3 regA:3 regB:3 immed:7
```
Here are the first four loads:
```	0:		lw	1, 0, 9
1:		lw	2, 0, 10
2:		lw	3, 0, 11
3:		lw	4, 1, 12
```
The binary opcode for lw is 101; its decimal value is 5. This gives us the following fields that make up the first four instructions (in decimal first, then in binary to show the widths of the fields):
```	5   1   0   9
5   2   0   10
5   3   0   11
5   4   1   12

101 001 000 0001001
101 010 000 0001010
101 011 000 0001011
101 100 001 0001100
```
The next two instructions are beq instructions, which have the following assembly-code format:
```	beq     regA, regB, target-address
```
and these beq instructions get translated to the CondBranch-Type machine-code instruction format:
```        opcode:3 regA:3 regB:3 immed:7
```
Here are the two beq instructions:
```	4:		beq	4, 3, immed(1)
5:		beq	0, 0, 8
```
Note that the target-address must be translated to the immediate value; the immediate value that goes into the machine-code instruction must be PC-relative. Therefore, for the instruction at address 4, the PC is 4 and the target-address is "immed(1)", which simply means that the assembly-language programmer used a constant value rather than a symbolic address (a label). So in this case, we can just put the constant right into the instruction field (assuming that it is within the bounds of -64 and 63).

The instruction at address 5 is different: it used a label for its target-address, which has resolved to the absolute location 8. We solve the following equation for immediate:

```	8 = PC + 1 + immediate
```
The PC at this address is 5, the target address is 8, therefore the immediate value that should go into the instruction is the value 2.

The binary opcode for beq is 110; its decimal value is 6. This gives us the following fields that make up the two beq instructions at addresses 4 and 5 (in decimal first, then in binary to show the widths of the fields):

```	6   4   3   1
6   0   0   2

110 100 011 0000001
110 000 000 0000010
```
The next instruction, add, has the following assembly-code format:
```	add     regA, regB, regC
```
and an add instruction gets translated to the Register-type machine-code instruction format:
```        opcode:3 regA:3 regB:3 0000 dest:3
```
Note that the middle four bits of an add instruction are unused and are therefore set to zero.

This is the add instruction to translate:

```	6:		add	1, 1, 2
```
The binary opcode for add is 000, decimal 0. This gives us the following fields that make up the add instruction (decimal first, then binary):
```	0   1   1   0    2

000 001 001 0000 010
```
The next instruction to translate is another beq instruction:
```	7:		beq	0, 0, 3
```
Like the beq instruction at address 5, this one used a label for its target address, and the label resolved to the absolute address 3. We solve the following for immediate:
```	3 = PC + 1 + immediate
```
The PC at this address is 7, so the immediate value is -5. The instruction therefore has the following machine-language encoding (decimal, then binary):
```	6   0   0   -5

110 000 000 1111011
```
In general, forward branches have positive immediate values, and backward branches have negative immediate values.

Lastly, we encode the halt instruction at location 8.

```	8:		halt
```
As described in the project description, the encoding for HALT looks like the following (decimal & binary):
```	jalr	0, 0, 0x71

111 000 000 1110001
```
Thus, we have the following for the instructions:
```	0:	101 001 000 0001001
1:	101 010 000 0001010
2:	101 011 000 0001011
3:	101 100 001 0001100
4:	110 100 011 0000001
5:	110 000 000 0000010
6:	000 001 001 0000 010
7:	110 000 000 1111011
8:	111 000 000 1110001
```
Next come the pieces of data, which are pretty simple. They resolve to the following:
```	9:	0000000000000000
10:	0000000000000001
11:	0000000000000000
12:	0000000000000000
13:	0000000000000000
14:	0000000000000000
15:	0000000000000000
16:	0000000000000000
17:	0000000000000000
18:	0000000000000000
19:	0000000000000000
20:	0000000000000000
21:	0000000000000000
```
The final output, in binary, looks like the following:
```	1010010000001001
1010100000001010
1010110000001011
1011000010001100
1101000110000001
1100000000000010
0000010010000010
1100000001111011
1110000001110001
0000000000000000
0000000000000001
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
```
```	1010 0100 0000 1001
1010 1000 0000 1010
1010 1100 0000 1011
1011 0000 1000 1100
1101 0001 1000 0001
1100 0000 0000 0010
0000 0100 1000 0010
1100 0000 0111 1011
1110 0000 0111 0001
0000 0000 0000 0000
0000 0000 0000 0001
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
```
And looks like the following in hex:
```	a409
a80a
ac0b
b08c
d181
c002
0482
c07b
e071
0000
0001
0000
0000
0000
0000
0000
0000
0000
0000
0000
0000
0000
```

Hope this helps,
Prof. Jacob