Our computer uses simple pipelining: while the current instruction is stable in the IR and D registers and executing, the next instruction is already being fetched from program memory.
This makes high speeds possible, but comes with an artefact: when a branch is executing, the instruction immediately behind the branch has already been fetched. This instruction will be executed before the branch takes effect and we continue from the new program location. Or worded more properly: the effect of branches is always delayed by 1 clock cycle.
When you don't want to think about these spurious instructions you just place a nop (no-operation) behind every branch instruction. Well, our instruction set doesn't have an explicit nop, but ld ac will do. My disassembler even shows that instruction as a nop. The Fibonacci program uses this all over:
address | encoding | | instruction | | | operands | | | | V V V V 0000 0000 ld $00 0001 c200 st [$00] 0002 0001 ld $01 0003 fc0a bra $0a 0004 0200 nop 0005 0100 ld [$00] 0006 c202 st [$02] 0007 0101 ld [$01] 0008 c200 st [$00] 0009 8102 adda [$02] 000a c201 st [$01] 000b 1a00 ld ac,out 000c f405 bge $05 000d 0200 nop 000e fc00 bra $00 000f 0200 nop
If you don't want to waste those cycles, usually you can let the extra slot do something useful instead. There are two common folding methods. The first is jumping to a position one step ahead of where you want to go, and copy the missed instruction after the branch instruction. In the example above, look at the branch on address $000e, it can be rewritten as follows:
000e fc01 bra $01 # was: bra $00 000f 0000 ld $00 # instruction on address 0
The second method is to exchange the branch with the previous instruction. Look for example at the branch on address $0003. The snippet can be rewritten as follows:
0002 0001 bra $0a # was: ld $01 0003 fc0a ld $01 # was: bra $0a 0004 0200 nop # will not be executed and can be removed
One of these folding methods is often possible, but not always. Needless to say, applying this throughout can lead to code that is both very fast and very difficult to follow. Here is a delay loop that runs for 13 cycles:
address | encoding | | instruction | | | operands | | | | V V V V 0125 0005 ld $05 # load 5 into AC 0126 ec26 bne $26 # jump to $0126 if AC not equal to 0 0127 a001 suba $01 # decrement AC by 1
This looks like nonsense: the branch is jumping to its own address and the countdown is in the instruction behind. But due to the pipelining this is just how it works.
Advanced pipelining: lookup tables
The mind really boggles when the extra instruction is a branch itself. But there is a useful application for that: the single-instruction subroutine, a technique to implement efficient inline lookup tables.
Here we jump to an address that depends on a register value. Then immediately following we put another branch instruction to where we want to continue. On the target location of the first branch we now have room for "subroutines" that can execute exactly one instruction (typically loading a value). These subroutines don't need to be followed by a return sequence, because the caller conveniently just provided that... With this trick we can make compact and fast lookup tables. The LED sequencer from yesterday's video uses this to implement a state machine:
address | encoding | | instruction | | | operands | | | | V V V V 0105 0009 ld $09 # Start of lookup table (we stay in the same code page $0100) 0106 8111 adda [$11] # Add current state to it (a value from 0-15) 0107 fe00 bra ac # "Jump subroutine" 0108 fc19 bra $19 # "Return" !!! 0109 0010 ld $10 # table Exactly one of these is executed 010a 002f ld $2f # table 010b 0037 ld $37 # table 010c 0047 ld $47 # table 010d 0053 ld $53 # table 010e 0063 ld $63 # table 010f 0071 ld $71 # table 0110 0081 ld $81 # table 0111 0090 ld $90 # table 0112 00a0 ld $a0 # table 0113 00b1 ld $b1 # table 0114 00c2 ld $c2 # table 0115 00d4 ld $d4 # table 0116 00e8 ld $e8 # table 0117 00f4 ld $f4 # table 0118 00a2 ld $a2 # table 0119 c207 st [$07] # Program continues here
At runtime 6 instructions get executed: ld, adda, bra, bra, ld, st
(Note: The values in this example are not important. If interested: the high 4 bits are the new state in the state machine, and the low 4 bits are the 4 LED outputs. This snippet of code implements the startup sequence and moving scanner lights from the video.)
Hyper advanced pipelining: the ternary operator
The pipeline gives a nice idiom for a ternary operator. With that I mean constructs like these:
V = A if C else B # Python V = C ? A : B # C if C then V=A else V=B # BASIC
The simple way to do this is as follows:
ld [C] beq done ld [B] ld [A] done: st [V]
The folding methods are already applied. In the false case (C == 0), B gets stored and this takes 4 cycles. In the true case B gets loaded first but is then replaced with A, which gets stored. This takes 5 cycles.
If you are in a time-critical part, such as in the video loop of this computer, this timing difference is quite annoying because we have to keep each path exactly in sync. The naive way to make both branches equally fast is something like this:
ld [C] beq label ld [B] bra done ld [A] label: nop nop done: st [V]
Now each path takes 6 cycles and doesn't mess up our timing. But it is clumsy and inelegant. Fortunately there is a much better way, again by placing two branch instructions immediately in sequence:
ld [C] beq label bra done ld [A] label: ld [B] done: st [V]
There we are: 5 cycles along each path! Figuring this one out is left as an exercise to the reader.
Note: This idiom has become so common in the Gigatron kernel that we don't bother to define labels for it any more. In the source code you therefore see something like this instead:
ld [C] beq *+3 bra *+3 ld [A] ld [B] st [V]
A final frequent "use" of the branch delay slot is when we care more about space than about speed. In those cases, we can sometimes squeeze out a word.
For example, vCPU uses that in a couple of places. For technical reasons, each vCPU instruction must take an even number of cycles. That means that sometimes a nop() has to be inserted anyway. Instead of adding the nop(), we can also have the function overlap with the first instruction of the next routine.
We can see this applied in the overlap between LDI and LDWI:
0318 00f6 ld $f6 1469 ld(-20//2) 0319 fc01 bra NEXT 1470 bra('NEXT') 1471 #dummy() 1474 label('LD') LD: 031a 1200 ld ac,x 1475 ld(AC,X) 031b 0500 ld [x] 1476 ld([X])
Obviously, this only works if that instruction doesn't do something that interferes with the operation.