
Example 3
---------

Here is a very short example program that shows
the execution of two incorrectly-predicted branches.
It builds on the last example, so it also has the
load-use interlock between the load and the add.
Then the BNE instructions enter the pipeline, and
we predict that the first will branch backwards to
the add instruction, so we fetch from that point, not
from the instruction after the BNE (the next BNE).
However, the branch is NOT taken, so we need to
"squash" the instructions that should not execute.
And then it happens again with the second BNE ...

top:	lw	1, 0, data1	# $1= mem[data1]
	add	2, 1, 1
	bne	1, 1, top
	bne	0, 0, bad
	halt
bad:	bne	1, 2, top
data1:	.fill	12345

This assembles to the following machine-code:

a406
0881
c4fd
c001
e071
c57a
3039

When executed, we get the following output.  Note
that the ADD instruction re-enters the pipeline right
after the BNE 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 BNE following it, though 
the BNE does not show up -- it is squashed before it
is printed out).  This places two NOP instructions
in the pipe after the BNE, followed by the correct
branch target -- the next BNE ... and so forth.

memory[0]=a406
memory[1]=881
memory[2]=c4fd
memory[3]=c001
memory[4]=e071
memory[5]=c57a
memory[6]=3039
7 memory words
	instruction memory:
		instrMem[ 0 ] = lw 1 0 6
		instrMem[ 1 ] = add 2 1 1
		instrMem[ 2 ] = bne 1 1 -3
		instrMem[ 3 ] = bne 0 0 1
		instrMem[ 4 ] = halt
		instrMem[ 5 ] = bne 1 2 -6
		instrMem[ 6 ] = addi 4 0 57
@@@
state before cycle 0 starts
	pc 0
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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
		pc 0
	IDEX:
		instruction: nop
		pc 0
		operand0 0
		operand1 0
		operand2 0
	EXMEM:
		instruction: nop
		pc 0
		storeData 0
		aluResult 0
		branchTarget 0
	MEMWB:
		instruction: nop
		pc 0
		writeData 0
	WBEND:
		instruction: nop
		writeData 0
@@@
state before cycle 1 starts
	pc 1
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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 6
		pc 0
	IDEX:
		instruction: nop
		pc 0
		operand0 0
		operand1 0
		operand2 0
	EXMEM:
		instruction: nop
		pc 0
		storeData 0
		aluResult 0
		branchTarget 0
	MEMWB:
		instruction: nop
		pc 0
		writeData 0
	WBEND:
		instruction: nop
		writeData 0
@@@
state before cycle 2 starts
	pc 2
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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
		pc 1
	IDEX:
		instruction: lw 1 0 6
		pc 0
		operand0 6
		operand1 0
		operand2 0
	EXMEM:
		instruction: nop
		pc 0
		storeData 0
		aluResult 0
		branchTarget 0
	MEMWB:
		instruction: nop
		pc 0
		writeData 0
	WBEND:
		instruction: nop
		writeData 0
@@@
state before cycle 3 starts
	pc 2
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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
		pc 1
	IDEX:
		instruction: nop
		pc 0
		operand0 0
		operand1 0
		operand2 0
	EXMEM:
		instruction: lw 1 0 6
		pc 0
		storeData 0
		aluResult 6
		branchTarget 0
	MEMWB:
		instruction: nop
		pc 0
		writeData 0
	WBEND:
		instruction: nop
		writeData 0
@@@
state before cycle 4 starts
	pc 0
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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: bne 1 1 -3
		pc 2
	IDEX:
		instruction: add 2 1 1
		pc 1
		operand0 1
		operand1 0
		operand2 0
	EXMEM:
		instruction: nop
		pc 0
		storeData 0
		aluResult 0
		branchTarget 0
	MEMWB:
		instruction: lw 1 0 6
		pc 0
		writeData 12345
	WBEND:
		instruction: nop
		writeData 0
@@@
state before cycle 5 starts
	pc 1
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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: lw 1 0 6
		pc 0
	IDEX:
		instruction: bne 1 1 -3
		pc 2
		operand0 -3
		operand1 0
		operand2 0
	EXMEM:
		instruction: add 2 1 1
		pc 1
		storeData 12345
		aluResult 24690
		branchTarget 0
	MEMWB:
		instruction: nop
		pc 0
		writeData 0
	WBEND:
		instruction: lw 1 0 6
		writeData 12345
@@@
state before cycle 6 starts
	pc 3
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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
		pc 0
	IDEX:
		instruction: nop
		pc 0
		operand0 0
		operand1 0
		operand2 0
	EXMEM:
		instruction: bne 1 1 -3
		pc 2
		storeData 12345
		aluResult 1
		branchTarget 0
	MEMWB:
		instruction: add 2 1 1
		pc 1
		writeData 24690
	WBEND:
		instruction: nop
		writeData 0
@@@
state before cycle 7 starts
	pc 4
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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: bne 0 0 1
		pc 3
	IDEX:
		instruction: nop
		pc 0
		operand0 0
		operand1 0
		operand2 0
	EXMEM:
		instruction: nop
		pc 0
		storeData 0
		aluResult 0
		branchTarget 0
	MEMWB:
		instruction: bne 1 1 -3
		pc 2
		writeData 1
	WBEND:
		instruction: add 2 1 1
		writeData 24690
@@@
state before cycle 8 starts
	pc 5
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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
		pc 4
	IDEX:
		instruction: bne 0 0 1
		pc 3
		operand0 1
		operand1 0
		operand2 0
	EXMEM:
		instruction: nop
		pc 0
		storeData 0
		aluResult 0
		branchTarget 0
	MEMWB:
		instruction: nop
		pc 0
		writeData 0
	WBEND:
		instruction: bne 1 1 -3
		writeData 1
@@@
state before cycle 9 starts
	pc 0
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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: bne 1 2 -6
		pc 5
	IDEX:
		instruction: halt
		pc 4
		operand0 -15
		operand1 0
		operand2 0
	EXMEM:
		instruction: bne 0 0 1
		pc 3
		storeData 0
		aluResult 1
		branchTarget 5
	MEMWB:
		instruction: nop
		pc 0
		writeData 0
	WBEND:
		instruction: nop
		writeData 0
@@@
state before cycle 10 starts
	pc 1
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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: lw 1 0 6
		pc 0
	IDEX:
		instruction: bne 1 2 -6
		pc 5
		operand0 -6
		operand1 24690
		operand2 12345
	EXMEM:
		instruction: halt
		pc 4
		storeData 0
		aluResult 0
		branchTarget 0
	MEMWB:
		instruction: bne 0 0 1
		pc 3
		writeData 1
	WBEND:
		instruction: nop
		writeData 0
@@@
state before cycle 11 starts
	pc 2
	data memory:
		dataMem[ 0 ] -23546
		dataMem[ 1 ] 2177
		dataMem[ 2 ] -15107
		dataMem[ 3 ] -16383
		dataMem[ 4 ] -8079
		dataMem[ 5 ] -14982
		dataMem[ 6 ] 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 2 1 1
		pc 1
	IDEX:
		instruction: lw 1 0 6
		pc 0
		operand0 6
		operand1 0
		operand2 0
	EXMEM:
		instruction: bne 1 2 -6
		pc 5
		storeData 12345
		aluResult 0
		branchTarget 0
	MEMWB:
		instruction: halt
		pc 4
		writeData 0
	WBEND:
		instruction: bne 0 0 1
		writeData 1
machine halted
total of 11 cycles executed
