Fri, 27 Sep 2013, 20:30

A student writes:

> For the first program I have encountered an issue. Is there any way that it
> is possible to use the Branch operation to return the Program Counter to an
> earlier instruction?
> <<name withheld to protect the student who wants to branch back>>

I had hoped to finish our absolute value problem in class on Wednesday,
which would have included the conditional branch instruction (BR).

Per usual, I overestimated what I thought I could explain carefully
in the time we had together.  So, I will explain it in class on Monday.
Meanwhile, I understand that most of you are eager to work on the program
and indeed, branches need to be able to go forward and backward.  So, I will
do it here, for those who don't want to wait until Monday.

By the way, there is a textbook, which as you know is incredibly beautifully 
written. :-)   It includes discussion of the conditional branch instruction 
(starting on page 150, Section 5.4).  Also, Appendix A has a page devoted to 
the conditional branch instruction.  The acronym is BR.

In any case:

The conditional branch instruction has three fields:

[15:12] contains the opcode, in this case 0000.
[11:9] determine which of the three condition codes (N,Z,P) are checked.
[8:0] contains a nine-bit offset, like the LD and ST we did Wednesday in class.

The computer carries out the work of the branch instruction as follows:

As a result of the branch instruction, the next instruction to be processed
must come from the memory location immediately after the branch instruction or 
from some other memory location specified in the branch instruction.

To know which is the case, the computer examines bits [11:9] and the three
condition codes N, Z, and P.  If bit[11] is 1 and N is 1, or if bit[10] is 1 
and Z is 1, or if bit[9] is 1 and P is 1, the PC is overwritten with the
address of the next instruction to be processed.

That is, bits [11:9] instruct the computer as to which condition codes must
be examined.  A "1" says examine the corresponding condition code, a "0" says
don't examine it.  If any condition code that is examined is 1, the computer
will overwrite the PC.  If all condition codes that are examined are 0, then
the PC will not be overwritten, resulting in the computer processing the
next sequential instruction, since the PC was incremented during the FETCH
phase of the instruction cycle.

In summary, the computer overwrites the contents of PC if and only if:

(bit[11] AND N) OR (bit[10] AND Z) OR (bit[9] AND P) is 1.

Step 2 (I am finally getting to the question you asked): What do we write into
the PC during the EXECUTE phase of the instruction cycle.  Answer: We use 
bits[8:0] of the instruction as a nine-bit offset, SIGN-extend it to 16 bits
and add the result to the current contents of the PC.  THAT is what we write
into the PC, and THAT is where the computer looks for the next instruction
during the FETCH phase of the next instruction cycle.

If the nine-bit offset is negative, the computer will branch back.

An example:  At location x3059, we have: 0000 010 111111000.

If the PC = x3059, the branch instruction will be executed.  During the
FETCH phase of the instruction, PC is incremented to x305A.  Bits[11:9]
instruct the computer to examine ONLY the Z bit.  If Z=0, the next instruction
to be processed is the instruction at location x305A.  If Z=1, we sign-extend
111111000 (-8) to 16 bits: 1111111111111000, add that to x305A, and write the
result into the PC.

0011 0000 0101 1010    x305A
1111 1111 1111 1000    xFFF8
-    -
0011 0000 0101 0010    x3051

So, the next instruction executed will be the one at x3051.

You have just branched backward!


Good luck getting the first program done in time.

Yale Patt