Example 3
---------

Here is a very short example program that shows
the execution of an incorrectly-predicted branch.
It builds on the last example, so it also has the
load-use interlock between the load and the add.
Then the BEQ instruction enters the pipeline, and
we predict that it will branch backwards to the 
add instruction, so we fetch from that point, not
from the instruction after the BEQ (the HALT).
However, the branch is NOT taken, so we need to
"squash" the instructions that should not execute.

	lw	1	0	data1	$1= mem[data1]
	add	2	1	1
	beq	1	2	-2
	halt
data1	.fill	12345

This assembles to the following LC-897 machine-code:

4084
04a0
857e
c000
3039

When executed, we get the following output.  Note
that the ADD instruction re-enters the pipeline right
after the BEQ instruction.  However, in the following
cycle, we determine at the end of the execute stage
that we have mispredicted the branch.  Because of this,
we need to squash the instructions currently in the 
pipeline (the ADD and the BEQ following it, though 
the BEQ does not show up -- it is squashed before it
is printed out).  This places two NOP instructions
in the pipe after the BEQ, followed by the correct
branch target -- the HALT instruction.

memory[0]=4084
memory[1]=4a0
memory[2]=857e
memory[3]=c000
memory[4]=3039
5 memory words
	instruction memory:
		instrMem[ 0 ] = lw 1 0 4
		instrMem[ 1 ] = add 2 1 1
		instrMem[ 2 ] = beq 2 1 -2
		instrMem[ 3 ] = halt
		instrMem[ 4 ] = nand 3 4 0
@@@
state before cycle 0 starts
	pc 0
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 0
		reg[ 2 ] 0
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction nop
		pcPlus1 0
	IDEX:
		instruction nop
		pcPlus1 0
		readRegA 0
		readRegB 0
		offset 0
	EXMEM:
		instruction nop
		branchTarget 0
		aluResult 0
		readRegB 0
	MEMWB:
		instruction nop
		writeData 0
	WBEND:
		instruction nop
		writeData 0
@@@
state before cycle 1 starts
	pc 1
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 0
		reg[ 2 ] 0
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction lw 1 0 4
		pcPlus1 1
	IDEX:
		instruction nop
		pcPlus1 0
		readRegA 0
		readRegB 0
		offset 0
	EXMEM:
		instruction nop
		branchTarget 0
		aluResult 0
		readRegB 0
	MEMWB:
		instruction nop
		writeData 0
	WBEND:
		instruction nop
		writeData 0
@@@
state before cycle 2 starts
	pc 2
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 0
		reg[ 2 ] 0
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction add 2 1 1
		pcPlus1 2
	IDEX:
		instruction lw 1 0 4
		pcPlus1 1
		readRegA 0
		readRegB 0
		offset 4
	EXMEM:
		instruction nop
		branchTarget 0
		aluResult 0
		readRegB 0
	MEMWB:
		instruction nop
		writeData 0
	WBEND:
		instruction nop
		writeData 0
@@@
state before cycle 3 starts
	pc 2
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 0
		reg[ 2 ] 0
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction add 2 1 1
		pcPlus1 2
	IDEX:
		instruction nop
		pcPlus1 0
		readRegA 0
		readRegB 0
		offset 0
	EXMEM:
		instruction lw 1 0 4
		branchTarget 5
		aluResult 4
		readRegB 0
	MEMWB:
		instruction nop
		writeData 0
	WBEND:
		instruction nop
		writeData 0
@@@
state before cycle 4 starts
	pc 1
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 0
		reg[ 2 ] 0
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction beq 2 1 -2
		pcPlus1 3
	IDEX:
		instruction add 2 1 1
		pcPlus1 2
		readRegA 0
		readRegB 0
		offset 32
	EXMEM:
		instruction nop
		branchTarget 0
		aluResult 0
		readRegB 0
	MEMWB:
		instruction lw 1 0 4
		writeData 12345
	WBEND:
		instruction nop
		writeData 0
@@@
state before cycle 5 starts
	pc 2
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 12345
		reg[ 2 ] 0
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction add 2 1 1
		pcPlus1 2
	IDEX:
		instruction beq 2 1 -2
		pcPlus1 3
		readRegA 0
		readRegB 0
		offset -2
	EXMEM:
		instruction add 2 1 1
		branchTarget 34
		aluResult 24690
		readRegB 12345
	MEMWB:
		instruction nop
		writeData 0
	WBEND:
		instruction lw 1 0 4
		writeData 12345
@@@
state before cycle 6 starts
	pc 3
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 12345
		reg[ 2 ] 0
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction nop
		pcPlus1 0
	IDEX:
		instruction nop
		pcPlus1 0
		readRegA 0
		readRegB 0
		offset 0
	EXMEM:
		instruction beq 2 1 -2
		branchTarget 1
		aluResult 0
		readRegB 24690
	MEMWB:
		instruction add 2 1 1
		writeData 24690
	WBEND:
		instruction nop
		writeData 0
@@@
state before cycle 7 starts
	pc 4
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 12345
		reg[ 2 ] 24690
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction halt
		pcPlus1 4
	IDEX:
		instruction nop
		pcPlus1 0
		readRegA 0
		readRegB 0
		offset 0
	EXMEM:
		instruction nop
		branchTarget 0
		aluResult 0
		readRegB 0
	MEMWB:
		instruction beq 2 1 -2
		writeData 0
	WBEND:
		instruction add 2 1 1
		writeData 24690
@@@
state before cycle 8 starts
	pc 5
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 12345
		reg[ 2 ] 24690
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction nand 3 4 0
		pcPlus1 5
	IDEX:
		instruction halt
		pcPlus1 4
		readRegA 0
		readRegB 0
		offset 0
	EXMEM:
		instruction nop
		branchTarget 0
		aluResult 0
		readRegB 0
	MEMWB:
		instruction nop
		writeData 0
	WBEND:
		instruction beq 2 1 -2
		writeData 0
@@@
state before cycle 9 starts
	pc 6
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 12345
		reg[ 2 ] 24690
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction add 0 0 0
		pcPlus1 6
	IDEX:
		instruction nand 3 4 0
		pcPlus1 5
		readRegA 0
		readRegB 0
		offset 57
	EXMEM:
		instruction halt
		branchTarget 4
		aluResult 0
		readRegB 0
	MEMWB:
		instruction nop
		writeData 0
	WBEND:
		instruction nop
		writeData 0
@@@
state before cycle 10 starts
	pc 7
	data memory:
		dataMem[ 0 ] 16516
		dataMem[ 1 ] 1184
		dataMem[ 2 ] -31362
		dataMem[ 3 ] -16384
		dataMem[ 4 ] 12345
	registers:
		reg[ 0 ] 0
		reg[ 1 ] 12345
		reg[ 2 ] 24690
		reg[ 3 ] 0
		reg[ 4 ] 0
		reg[ 5 ] 0
		reg[ 6 ] 0
		reg[ 7 ] 0
	IFID:
		instruction add 0 0 0
		pcPlus1 7
	IDEX:
		instruction add 0 0 0
		pcPlus1 6
		readRegA 0
		readRegB 0
		offset 0
	EXMEM:
		instruction nand 3 4 0
		branchTarget 62
		aluResult -1
		readRegB 0
	MEMWB:
		instruction halt
		writeData 0
	WBEND:
		instruction nop
		writeData 0
machine halted
total of 10 cycles executed