Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS240 Computer Organization / 2017-Fall / Notebooks

5.4 Control Instructions

Control instructions change the sequence of the instructions that are executed. If there were no control instructions, the next instruction fetched after the current instruction finishes would be the instruction located in the next sequential memory location. As you know, this is because the PC is incremented before executing an instruction. We will see momentarily that it is often useful to be able to break that sequence.

The LC-3 has five opcodes that enable this sequential flow to be broken:

• conditional branch
• unconditional jump
• subroutine (sometimes called function) call
• TRAP and return from interrupt.

In this section, we will deal almost exclusively with the most common control instruction, the conditional branch. We will also introduce the unconditional jump and the TRAP instruction. The TRAP instruction is particularly useful because, among other things, it allows a programmer to get information into and out of the computer without fully understanding the intricacies of the input and output devices. However, most of the discussion of the TRAP instruction and all of the discussion of the subroutine call and the return from interrupt we will leave for Chapters 9 and 10.

5.4.1 Conditional Branches

The format of the conditional branch instruction (opcode = 0000) is as follows:

Opcode	[11:9]	[8:0]
0000	NZP	VVVVVVVVV

Bits [11], [10], and [9] correspond to the three condition codes discussed in Section 5.1.7. Recall that in the LC-3, all instructions that write values into the general purpose registers set the three condition codes (i.e., the single-bit registers N, Z, P) in accordance with whether the value written is negative, zero, or positive. These instructions are ADD, AND, NOT, LD, LDI, LDR, and LEA.

The next instruction will be at the address that is computed by adding the incremented PC to the 16-bit value formed by sign-extending bits [8:0] of the BR instruction.

Consider this example: the last value loaded into a general purpose register was 0, and the current instruction (located at x4027) is as shown here:

x4026: ...
x4027: 0000 010 011011001 
x4028: ...

We see that this is a BR opcode (0000) and if the last value loaded into a GPR is a Z (zero), then we will BRANCH to the PC + 011011001.

0 1101 1001 = x0D9 = D * 16 + 9 = 13 * 16 + 9 = 217

  11
x4028
x00D9
------
x4101

So, this would load the PC with x4101, and the next instruction executed would be the one at x4101, rather than the instruction at x4028.

What does each of these do?

Q1:

0000 111 000000000

Q2:

0000 111 000000001

Q3:

0000 111 111111111

Q4:

0000 000 100101101

Algorithm

Suppose we know that the 12 locations x3100 to x310B contain integers, and we wish to compute the sum of these 12 integers.

First, as in all algorithms, we must initialize our variables. That is, we must set up the initial values of the variables that the computer will use in executing the program that solves the problem. There are three such variables: the address of the next integer to be added (assigned to R1), the running sum (assigned to R3), and the number of integers left to be added (assigned to R2). The three variables are initialized as follows: The address of the first integer to be added is put in R1. R3, which will keep track of the running sum, is initialized to 0. R2, which will keep track of the number of integers left to be added, is initialized to 12. Then the process of adding begins.

The program repeats the process of loading into R4 one of the 12 integers, and adding it to R3. Each time we perform the ADD, we increment R1 so it will point to (i.e., contain the address of) the next number to be added and decrement R2 so we will know how many numbers still need to be added. When R2 becomes zero, the Z condition code is set, and we can detect that we are done.

First, let's put the data into the correct places in memory:

.ORIG x3100
0000 0000 0000 0000 ;; x3100
0000 0000 0000 0000 ;; x3101
0000 0000 0000 0000 ;; x3102
0000 0000 0000 0000 ;; x3103
0000 0000 0000 0000 ;; x3104
0000 0000 0000 0000 ;; x3105
0000 0000 0000 0000 ;; x3106
0000 0000 0000 0000 ;; x3107
0000 0000 0000 0000 ;; x3108
0000 0000 0000 0000 ;; x3109
0000 0000 0000 0000 ;; x310A
0000 0000 0000 0000 ;; x310B
.END

Assembled! Use %dis or %dump to examine; use %exe to run.

Now, we convert the above algorithm into machine code.

The details of the program execution are as follows: The program starts with PC = x3000.

x3000: 1110 001 0 1111 1111  
x3001: 0101 011 011 1 00000  
x3002: 0101 010 010 1 00000  
x3003: 0001 010 010 1 01100  
x3004: 0000 010 000000101    
x3005: 0110 100 001 000000   
x3006: 0001 011 011 000100   
x3007: 0001 001 001100001    
x3008: 0001 010 010111111    
x3009: 0000 111 111111010    
x300A: 1111 0000 00100101

The first instruction (at location x3000) loads R1 with the address x3100. (The incremented PC is x3001; the sign-extended PCoffset is xOOFF.)

The instruction at x3001 clears R3. R3 will keep track of the running sum, so it must start off with the value 0. As we said previously, this is called initializing the SUM to zero.

The instructions at x3002 and x3003 set the value of R2 to 12, the number of integers to be added. R2 will keep track of how many numbers have already been added. This will be done (by the instruction contained in x3008) by decrementing R2 after each addition takes place.

The instruction at x3004 is a conditional branch instruction. Note that bit [10] is a 1. That means that the Z condition code will be examined. If it is set, we know R2 must have just been decremented to 0. That means there are no more numbers to be added and we are done. If it is clear, we know we still have work to do and we continue.

The instruction at x3005 loads the contents of x3100 (i.e., the first integer) into R4, and the instruction at x3006 adds it to R3.

The instructions at x3007 and x3008 perform the necessary bookkeeping. The instruction at x3007 increments Rl, so Rl will point to the next location in memory containing an integer to be added (in this case, x3101). The instruction at x3008 decrements R2, which is keeping track of the number of integers still to be added, as we have already explained, and sets the N, Z, and P condition codes. The instruction at x3009 is an unconditional branch, since bits [11:9] are all 1. It loads the PC with x3004. It also does not affect the condition codes, so the next instruction to be executed (the conditional branch at x3004) will be based on the instruction executed at x3008.

This is worth saying again. The conditional branch instruction at x3004 follows the instruction at x3009, which does not affect condition codes, which in turn follows the instruction at x3008. Thus, the conditional branch instruction at x3004 will be based on the condition codes set by the instruction at x3008. The instruction at x3008 sets the condition codes depending on the value produced by decrementing R2. As long as there are still integers to be added, the ADD instruction at x3008 will produce a value greater than zero and therefore clear the Z condition code. The conditional branch instruction at x3004 examines the Z condition code. As long as Z is clear, the PC will not be affected, and the next instruction cycle will start with an instruction fetch from x3005.

.ORIG x3000
1110 001 0 1111 1111  ;; R1 <- 3100   , LEA DST PCOFFSET9
0101 011 011 1 00000  ;; R3 <- 0      , AND DST SRC #0
0101 010 010 1 00000  ;; R2 <- 0      , AND DST SRC #0
0001 010 010 1 01100  ;; R2 <- 12     , ADD DST SRC #12 
0000 010 000000101    ;; BRz x300A    , BRz to HALT 5 below PC + 1 if zero
0110 100 001 000000   ;; R4 <- M[R1]  , LDR DST BAS OFFSET6 
0001 011 011 0 00 100 ;; R3 <- R3+R4  , ADD R3 <= R3 + R4
0001 001 001 1 00001  ;; R1 <- R1 + 1 , ADD R1 <= R1 + 1
0001 010 010 1 11111  ;; R2 <- R2 - 1 , ADD R2 <= R2 + -1
0000 111 111111010    ;; BRnzp x3004  , BRnzp PC+1=x300A + -6, GOTO test
1111 0000 00100101    ;; HALT
.END

Assembled! Use %dis or %dump to examine; use %exe to run.

The conditional branch instruction causes the execution sequence to follow: x3000, x3001, x3002, x3003, x3004, x3005, x3006, x3007, x3008, x3009, x3004, x3005, x3006, x3007, x3008, x3009, x3004, x3005, and so on until the value in R2 becomes 0. The next time the conditional branch instruction at x3004 is executed, the PC is loaded with x300A, and the program continues at x300A with its next activity.

Finally, it is worth noting that we could have written a program to add these 12 integers without any control instructions. We still would have needed the LEA instruction in x3000 to initialize Rl. We would not have needed the instruction at x3001 to initialize the running sum, nor the instructions at x3002, and x3003 to initialize the number of integers left to be added. We could have loaded the contents of x3100 directly into R3, and then repeatedly (by incrementing Rl, loading the next integer into R4, and adding R4 to the running sum in R3) added the remaining 11 integers. After the addition of the twelfth integer, we would go on to the next task, as does the example of Figure 5.13 with the branch instruction in x3004.

Unfortunately, instead of a 10-instruction program, we would have had a 35- instruction program. Moreover, if we had wished to add 100 integers without any control instructions instead of 12, we would have had a 299-instruction program instead of 10. The control instructions in the example of Figure 5.13 permit the reuse of sequences of code by breaking the sequential instruction execution flow.

For Monday:

• 5.4.3 Two Methods for Loop Control
• 5.4.4 Example: Adding a Column of Numbers Using a Sentinel
• Run the example