LC-3 control instructions: BR, JMP, TRAP and loops

Last week the instructions always ran in order: every FETCH incremented the PC by one. Real programs, however, make decisions (if) and repeat (loops). For this there are control instructions: by writing a new value into the PC, they change the next instruction. In the LC-3 these are BR, JMP, JSR, TRAP and RTI. On this page you see BR, JMP and TRAP, and then the loop and if patterns built with them.

Exam questions: encode or decode a BR (offset calculation), decode and trace a program given in hex, find how many times a loop runs and the register values at the end.

BR: conditional branch

0000 | n | z | p | PCoffset9
15-12  11  10   9   8-0

BR looks at the condition codes. If one of the bits that is 1 in the instruction matches the current condition code, it branches: PC ← (incremented PC) + SEXT(PCoffset9). If it does not match, it does nothing, and the program moves on to the next instruction.

TIP · What does BR look at? BR looks at the result of the last instruction that wrote to a register for the condition code. In between there can be instructions that do not change the CC, like ST, STR, BR; they do not count. If you want to test a register, first write it somewhere: ADD R1, R1, #0 sets the CC according to R1.

Offset calculation

$\text{PCoffset9} = \text{target} - (\text{address of the BR} + 1)$

The range is -256..+255. When branching backward (to the start of a loop), the offset is negative.

Encoding example: BRn LOOP at x3008, LOOP = x3002.

offset = x3002 - x3009 = -7
-7 (9 bits) = 1 1111 1001
0000 100 111111001 = x09F9

Decoding example: x0BFC, at x3020.

0000 101 111111100
n=1 z=0 p=1  → BRnp
offset = 1 1111 1100 = -4
target = x3021 - 4 = x301D

JMP and RET

1100 | 000 | BaseR | 000000

PC ← BaseR. Because the target is in a register, it can jump anywhere in memory (BR reaches only ±256). JMP R2 = xC080. RET is an alias of JMP R7 (xC1C0); it is used to return from a subroutine or a TRAP routine.

TRAP

1111 | 0000 | trapvect8

1. R7 ← PC (the incremented PC, the return address).
2. PC ← M[ZEXT(trapvect8)]: take the address of the routine from the trap vector table between x0000-x00FF.

Loop patterns

Counter loop (counter-controlled)

How many times to loop is known from the start. The counter is kept in a register, decreased in every round, and the loop exits when it reaches zero.

Worked example: multiplication. There is no MUL in the LC-3; 6 × 4 = 6 + 6 + 6 + 6.

        .ORIG x3000
        AND  R3, R3, #0    ; R3 = 0 (result)
        LD   R1, X         ; R1 = 6
        LD   R2, Y         ; R2 = 4 (counter)
LOOP    ADD  R3, R3, R1    ; R3 += 6
        ADD  R2, R2, #-1   ; counter--
        BRp  LOOP          ; repeat if counter > 0
        HALT
X       .FILL #6
Y       .FILL #4
        .END

round R3    R2   CC   BRp
 1     6     3    P   loop back
 2    12     2    P   loop back
 3    18     1    P   loop back
 4    24     0    Z   fall through

The result is R3 = 24. The machine code:

x3000 x56E0  AND R3, R3, #0
x3001 x2205  LD  R1, X       (x3002 + 5 = x3007)
x3002 x2405  LD  R2, Y       (x3003 + 5 = x3008)
x3003 x16C1  ADD R3, R3, R1
x3004 x14BF  ADD R2, R2, #-1
x3005 x03FD  BRp x3003       (x3006 - 3)
x3006 xF025  HALT

PITFALL · one round too many. If you write BRzp instead of BRp, it also loops back when R2 = 0, runs 5 rounds, and the result is 30. If you want the counter to end at 0, use BRp.

Sentinel loop

The number of elements is not known; at the end of the list there is a special value (the sentinel, usually 0). Each element is loaded, and if it is the sentinel the loop exits.

Worked example: count the negatives.

        AND  R2, R2, #0     ; counter = 0
        LEA  R1, DATA       ; R1 = address of the array
LOOP    LDR  R3, R1, #0     ; R3 = *R1, the CC is set
        BRz  DONE           ; 0 → finished
        BRp  NEXT           ; positive → do not count
        ADD  R2, R2, #1     ; negative → count
NEXT    ADD  R1, R1, #1     ; next element
        BRnzp LOOP
DONE    ST   R2, RESULT
        HALT
RESULT  .BLKW 1
DATA    .FILL #5
        .FILL #-3
        .FILL #-8
        .FILL #2
        .FILL #-1
        .FILL #0

The result is RESULT = 3. BRz and BRp back to back look at the same CC, because BR does not change the CC.

if and if/else

The pattern: skip with the opposite of the condition. To write “if x is negative do this”, you write “if x is not negative (zp) skip”.

Absolute value:

        LD   R1, V          ; CC = the sign of V
        BRzp DONE           ; skip if not negative
        NOT  R1, R1         ; R1 = -R1
        ADD  R1, R1, #1
DONE    ST   R1, V
        HALT
V       .FILL #-25

The result is V = 25.

if/else: the larger of two numbers.

        LD   R1, A
        LD   R2, B
        NOT  R3, R2
        ADD  R3, R3, #1
        ADD  R3, R1, R3     ; R3 = A - B, the CC is set
        BRn  BBIG           ; if A < B go to the else part
        ADD  R4, R1, #0     ; then: R4 = A
        BRnzp END           ; skip the else
BBIG    ADD  R4, R2, #0     ; else: R4 = B
END     HALT
A       .FILL #-4
B       .FILL #9

The result is R4 = 9. Without the unconditional BRnzp END at the end of the then block, the program would fall into the else block too.

Reading a program from hex

In the exam sometimes only the machine code is given. The recipe:

1. Expand each word to 16 bits, look at the opcode.
2. Write the instruction in assembly; compute the BR targets with addresses.
3. Set up a trace table (registers, CC, branches).

x3000 x5020  AND R0, R0, #0
x3001 x1225  ADD R1, R0, #5
x3002 x1001  ADD R0, R0, R1
x3003 x127E  ADD R1, R1, #-2
x3004 x03FD  BRp x3002
x3005 xF025  HALT

R1: 5 → 3 → 1 → -1     R0: 5 → 8 → 9     result R0 = 9

Common mistakes

        AND  R3, R3, #0
        LD   R1, X
        LD   R2, Y
LOOP    ADD  R3, R3, R1
        ADD  R2, R2, #-1
        BRp  LOOP
        HALT
X       .FILL #6
Y       .FILL #4

        AND  R2, R2, #0
        LEA  R1, DATA
LOOP    LDR  R3, R1, #0
        BRz  DONE
        BRp  NEXT
        ADD  R2, R2, #1
NEXT    ADD  R1, R1, #1
        BRnzp LOOP
DONE    ST   R2, RESULT
        HALT
RESULT  .BLKW 1
DATA    .FILL #5
        .FILL #-3
        .FILL #-8
        .FILL #2
        .FILL #-1
        .FILL #0