Lecture 6
Andreas Moshovos
Spring 2005
Simple Control Flow
We have seen how “straight-line” instruction sequencing works. Let’s us now see how the CPU can implement simple control-flow (instruction sequencing) structures such as the if-then-else. Let’s use the following pseudo-C code as a starting point:
unsigned int a = 0x00000000;
unsigned int b = 0x11223344;
unsigned int c = 0x22334455;
if (b == 0)
then a = b + c;
else a = b – c;
An implementation of this program in assembly is as follows:
org $20000
va dc.l 0
vb dc.l $11223344
vc dc.l $22334455
org $10000
start move.l vb, d0
beq then
else
sub.l vc, d0
move.l d0, va
bra after
then
add.l vc, d0
move.l d0, va
after
There are a few new instructions here. SUB is for subtraction. The other two instructions take the form:
Bcc Destination
B is for branch and cc is a condition. These instructions change the execution flow depending on whether the condition is met.
Their operation is:
If (cc is TRUE) then PC = Destination
EQ uses the condition EQUAL while BRA uses the condition ALWAYS. Always is simple to understand, BRA always changes the control flow, so instruction execution continues at the Destination.
But what are these conditions and how can we influence them?
These conditions refer to combinations of the bits stored inside the SR register. These bits are called CONDITION CODES and are set as a side-effect by almost all instructions. The condition codes in 68k are the following:
Please ignore the system byte for the time being and focus on the CCR part (lower 8 bits). The condition codes are:
EXTEND, NEGATIVE, ZERO, OVERFLOW and CARRY.
Whenever an instruction is executed in the 68k, as a by-product it sets the CCR bits to reflect its outcome. So, if the outcome was zero, the the Z bit will be set to 1. if this was an addition and there was an overflow the overflow bit will be set. Not all instructions set the CCR bits. Moreover, even when they set the CCR bits they may not set all of them. For the most part, however, what you expect is what happens. To be sure you need to consult the 68k instruction set manual or the corresponding appendix in the book.
The definition of the move.l instruction specifies that it sets the Z and N bits. That is if the long word value read is zero then the Z bit will be set to 1 and if the most significant bit is 1 then the N bit will be set to 1 in either case if the conditions do not hold the corresponding bits are set to 0.
Here are the various conditions that branches can test for:
So, in our code the BEQ simply tests whether the result of the previous operation was zero. Hence the sequence:
move.l vb, d0
beq then
diverts execution to address “then” only when the value read from vn is zero. If the value read from vb is non-zero then the instruction following the branch is executed (the one at label “else”).
The following flow diagram shows the various control flow sequences possible:
There are two possible paths through the code:
ABD and ACD. The first correspond to executing the ELSE part while the second to executing the THEN part.
An equivalent implementation is as follows:
org $20000
va dc.l 0
vb dc.l $11223344
vc dc.l $22334455
org $10000
start move.l vb, d0
bne else
then
add.l vc, d0
move.l d0, va
bra after
else
sub.l vc, d0
move.l d0, va
after
Here we reversed the order of the THEN and ELSE code sections and hence we also reversed the condition in our first brach. That is, we replaced the “BEQ then” with a “BNE else” which tests whether the result of the previous operation was non-zero. Hence the sequence:
move.l vb, d0
bne else
then diverts execution to address “else” only when the value read from vn is non-zero. If the value read from vb is zero then the instruction following the branch is executed (the one at label then).
The following flow diagram shows the various control flow sequences possible:
There are two possible paths through the code:
ABD and ACD. The first correspond to executing the then part while the second to executing the else part.
Encoding –
Limitations
While in assembly branch instructions take the form Bcc Label in the actual machine the destination is encoded relatively to the location of the instruction. An 8-bit or 16-bit displacement constant is used. That is the destination is calculated as [PC] + 2 + displacement where PC is the address where the branch instruction is placed in memory.. The displacement is a signed constant. When the 8-bit variation is used, the destination can be an address that is at distance -126 to +128 (not +129 because instructions start at even addresses) from where the branch starts. For the 16-bit displacement we have a range of -32766 to +32768. The assembler will automatically chose the smaller possible format and will complaint if a branch is impossible to implement.
The encoding of branch instructions is as follows:
The last two bytes are used only if the 16-bit displacement form is used. To use the 16-bit displacement the 8-bit displacement must be $00. Thus a branch to the immediately next instruction can only be represented using the 16-bit displacement format.
The various conditions can be split into two categories depending on how the interpret the result of the previous instruction that set the condition codes. The instruction can be interpreted as operating on unsigned numbers or on signed numbers. Accordingly the conditions are:
Examples of other
conditions being tested:
Let us now look at various examples of C conditions and how they can be implemented in 68k assembly:
if (a == b) then …
move.l va, d0
cmp.l vb, d0
beq then
bra else
then
…
bra after
else
…
after
The cmp.l vb, d0 instruction subtracts the value store at memory location va from the value in register d0 and sets the condition codes accordingly. It does not change the value in d0.
Note that if we have
CMP A, B where A and B two arguments then a bgt
branch following it tests for B > A not for A > B.
The above code goes through two branch instructions to execute the then part (beq and bra). There is a more efficient implementation. It relies on testing the opposite condition:
move.l va, d0
cmp.l vb, d0
bne else
then
…
bra after
else
…
after
Here’s another example where we compare two different memory
variables.
if (a > b) then …
move.l va, d0
cmp.l vb, d0
ble else
then
…
bra after
else
…
after
Note that in the previous example we used a signed condition. Note that we also used the reverse condition in the branch instruction since we want to execute the instruction that follows (the then part) if a is greater than b. Thus we test for the opposite condition which is less or equal.
if (va == 1) then
…
move.l va, d0
cmpi.l #1, d0
bne else
then
…
bra after
else
…
after
Note that we use the cmpi = compare immediate instruction. Also note that we use the symbol # in front of the constant 1. The # is used for constants that are encoded within the instruction. This instruction compares d0 with the constant 1. It does not access memory. Similar variations exist for other instructions. For example, there is an addi instruction that adds a constant to a d register.
We could also “simply” write:
cmpi.l #1, va
bne else
then
…
bra after
else
…
after
Let’s now look at a combined condition (&& = AND):
if (va == 1
&& vb == 2) then … else …
cmpi.l #1, va
bne else
cmpi.l #2, vb
bne else
then
…
bra after
else
…
after
Since all conditions must be met for the then part to get executed we test the opposite condition and branch to the else part as soon as one of these opposite conditions is met. Only if none of the opposite conditions is met we reach the then part.
cmpi.l #1, va
beq test2
bra else
test2 cmpi.l #2, vb
beq then
bra else
then
…
bra after
else
…
after
An alternative implementation that is simpler to understand but less efficient is the following:
Let’s now look at a combined condition (|| = OR):
if (va == 1 || vb == 2) then … else …
cmpi.l #1, va
beq then
cmpi.l #2, vb
bne else
then
…
bra after
else
…
after
Since the then part is executed as long as at least one condition is met, we first test for the condition as specified (not the opposite) and branch to then part if this is met. If not we proceed to test the opposite of the second condition and branch to the else part if it is met.