Lecture 8

Andreas Moshovos

Spring 2005

Loops and Arrays

In this section we will be implementing in assembly the following C pseudo-code:

short arr[5] = { 1, 2, 3, 4, 5 }; // an array of word values (16 bit)

short n = 5; // the number of elements in the array

short sum = 0;

for (i = 0; i < n; i++)

sum = sum + arr[i];

How are arrays are implemented at the machine level? They are typically implemented by allocating each element one after the other in memory.

So, in our example, if arr[0] is at memory location $30000 then arr[1] will be at $30002, arr[2] at $30004 and in general arr[i] will be at $30000 + i x 2. Generally, if we have a unidimensional array A of elements TYPE, then element a[i] is at address &A[0] + sizeof(TYPE) x i.

Note that the C expression &A[0] is equivalent to the address of the first array element. Instead of &A[0], in C we can typically write A (note: in C if you write &A[0] + i, it will be automatically converted into &A[0] + I x sizeof(a[0]));

Let us first declare our variables:

org $30000

arr dc.w 1, 2, 3, 4, 5 ; note assembler doesn’t like spaces in-between the numbers and commas

n dc.w 5

sum dc.w 0

Focusing now on the code we should review what is the execution semantics of the C for statement. In general, a C statement comprises four parts:

for (INIT; COND; POST)

BODY

and execution is done as follows:

INIT

start

if (NOT COND) exit the loop

BODY

POST

go back to “start”

where start is label. In words, the INIT part is always executed once at the beginning. We then test the condition (COND). If the condition is not TRUE the this is the end of it we skip the for. Otherwise, if the condition is TRUE, we then execute the BODY portion, followed by the POST portion. We then return back to testing the condition and repeat the aforementioned steps until the condition stops being TRUE.

In our loop we have:

INIT à i = 0

COND à i < n

BODY à sum = sum + arr[i]

POST à i = i + 1

Let’s are write each of them in turn.

For starters let us use a register for holding variable i. Let’s use D0 for this.

Then INIT becomes:

clr.l D0 à [D0] = 0

Our condition requires comparing the current value of i and n. Assuming that n does not change in value while our loop executes (and it shouldn’t) then we have the code:

move.w n, D1 à keep n’s value in D1

so now we can test for the reverse condition using a cmp instruction and jump out of the loop as needed.

cmp.w d1, d0

bge endloop

Finally, the POST section becomes:

addq.w #1, d0 à [d0] = [d0] + 1

Notice that we use a variation of add called addq (q = quick). It to does addition, however, it can only be used for small integer values. The advantage is that the whole instruction can be represented with just two bytes.

The almost complete part of our code is then as follows:

org $20000

clr.l d0

move.w n, d1

loop cmp.w d1, d0

bge endloop

BODY GOES HERE

addq.w #1, d0

bra loop

endloop

Let’s us use register d3 to keep the running sum and at the end we will write this value into the sum variable in memory. So, we should initialize d3 to 0 in the beginning and at the end of the loop write its value into the sum variable.

Now we can focus on implementing the BODY part. In 68k the A registers are generally used for calculations on quantities that will be used as addresses and for accessing memory in ways other the ones we have seen.

To implement the statement sum = sum + a[i] we need to be able to access all array elements one after the other. We have seen instructions that access memory but the used a fixed address (e.g., move.w arr, d0). We could use five of these instructions if we knew that the array will always have five elements, but what if the array can have 16K elements? Or what if the number of elements was not known upfront? To deal with we need a mechanism that will allow an instruction to access a program calculate memory location. One such way is as follows:

move.w (a0), d2

The “(a0)” expression signifies a memory access. The memory address is not fixed in the instruction itself. Instead it is taken from the value of register inside the parentheses. Thus, the aforementioned instruction does “[d2] = Mem[[a0]]”.

To access arr[i] we need to access the word at memory location “arr + i x 2”. The code for that is:

movea.l #arr, a0 à [a0] = &arr[0], notes: we have to use movea when the destination register is an a register.

Since this is an address we must use long-word arithmetic

adda.l d0, a0 à [a0] = &arr[0] + i

adda.l d0, a0 à [a0] = &arr[0] + i + i = &arr[0] + 2 x i

add.w (a0), d3 à [d3] = [d3] + arr[i]

The complete code for the for loop is as follows:

org $20000

clr.l d0 ; i = 0, we use the .l since i takes part in .l calculation

clr.l d3 ; sum = 0 (temporarily sum lives in d3)

move.w n, d1 ; d1 = n

loop cmp.w d1, d0

bge endloop ; if (i >= n) goto endloop

movea.l #arr, a0 ; a0 = &arr[0]

adda.l d0, a0

adda.l d0, a0 ; a0 = &arr[0] + 2 x i

add.w (a0), d3 ; d3 = d3 + arr[i]

addq.w #1, d0 ; i = i + 1

bra loop ; repeat loop

endloop

move.w d3, sum ; write the sum into memory

Machine language support for loops

Because loops are so frequent, the 68k designer’s decided to provide an instruction that supports them directly. Note that this instruction does not provide functionality that cannot be synthesized otherwise. At the time it provided an advantage in processing speed and code density thus it was viewed as a good way of utilizing resources (transistors).

The instruction is the Decrement and Branch and takes the form:

DBcc Dn, destination

cc is any branch condition, Dn is a D register and destination in assembly will be label.

The semantics of the instruction are non-trivial:

1. if (not cc) then [Dn] = [Dn] – 1 (word calculation only – only the lower 16 bits of Dn participate)

2. if ([Dn] != -1) then [PC] = [PC] + displacement (essentially execution resumes at the destination)

In the first step, the instruction tests the condition and if the condition is FALSE then it decrements the corresponding D register by 1.

In the second step, the D register is compared to -1. Only if the D register is not -1 this instruction changes control flow. Otherwise, execution fall through. The destination, as in branches is specified as PC relative displacement.

If we always want to decrement the D register then we can use the “dbf” variation, where cc = f = false.

This instruction is useful for implementing do-while loops. It can also be used to implement other loops with the addition of a few instructions to handle the first iteration.

Let’s see an example similar to the one with the for loop:

i = n - 1;

do {

sum = sum + arr[i];

i = i – 1;

} while (i >= 0);

One assembly implementation is:

org $20000

clr.l d3 ; sum = 0 (temporarily sum lives in d3)

clr.l d1

move.w n, d0 ; d0 = n

subq.w #1, d0 ; d0 = n - 1

loop

movea.l #arr, a0 ; a0 = &arr[0]

adda.l d0, a0

adda.l d0, a0 ; a0 = &arr[0] + 2 x i

add.w (a0), d3 ; d3 = d3 + arr[i]

dbf d0, loop ; cc = f = FALSE à always decrement

endloop

move.w d3, sum ; write the sum into memory

Note the this code is not equivalent to the for code. The for code will not execute its BODY is n is 0.