A large part of our algorithm is the dependency checker, which compares two instructions and controls a dependency bit for the second instruction.  It checks the register and memory usage between the two to determine if the second instruction can potentially be moved above the first. It handles special jump cases as well, making sure that jump destinations aren’t relocatable, and that jump sources don’t cross store boundaries. This site section is taken from a report on the Dependency Checker Logic.  Update: The dependency checker logic has been tested and revised. The modified report is located here.

We have created a table of the dependencies that extends the dependency checking portion of Milestone 3.  The OpCodes for each instruction have been selected to exploit the similarity between dependencies.  Each unique type of dependency has a letter associated with it, and you’ll notice that several dependencies between unrelated instructions share the same letter, or type.  We then grouped the dependencies by type and register usage  to create the table on page 3.  This allowed us to fairly easily create a set of equations describing the entire dependency checker. These equations have been plugged directly into a PLA generator to create the actual layout for our dependency checker subcell.  In addition, the dependency checker logic has been implemented in LabVIEW (see the Simulation section) and has been verified to work on a few select test cases.  Update: A full test of the dependency checker has been completely (with the help of LabVIEW-generated test cases). Visit the section on testing for more details.  The logic equations are fomulated below.

Brush up on your Instruction Set familiarity here.
 

	0	1	r1	m1	0	load sink, m1
a	0	1	r1	x	1	store sink, x
b	0	1	r1	x	0	load sink, x
c	0	1	x	m1	1	store, x, m1
d	1	0	r1	x	x	unop sink, x, x
e	1	0	x	r1	x	unop x, sink, x
f	1	1	r1	x	x	binop sink, x, x
g	1	1	x	r1	x	binop x, sink, x
h	1	1	x	x	r1	binop x, x, sink
	0	1	r1	m1	1	store source, m1
b	0	1	r1	x	0	load source, x
j	0	1	x	m1	0	load x, m1
c	0	1	x	m1	1	store x, m1
d	1	0	r1	x	x	unop source, x, x
f	1	1	r1	x	x	binop source, x, x
k	0	0	x	x	0	jump x (where current not equal latency instruction)
	1	0	r1	r2	x	unop sink, source, x
a	0	1	r1	x	1	store sink, x
e	1	0	x	r1	x	unop x, sink, x
l	1	0	r2	x	x	unop source, x, x
d	1	0	r1	x	x	unop sink, x, x
f	1	1	r1	x	x	binop sink, x, x
g	1	1	x	r1	x	binop x, sink, x
h	1	1	x	x	r1	binop x, x, sink
m	1	1	r2	x	x	binop source, x, x
n	0	1	r2	x	0	load source, x
b	0	1	r1	x	0	load sink, x
	1	1	r1	r2	r3	binop sink, source1, source2
a	0	1	r1	x	1	store sink, x
n	0	1	r2	x	0	load source1, x
p	0	1	r3	x	0	load source2, x
b	0	1	r1	x	0	load sink, x
d	1	0	r1	x	x	unop sink, x, x
f	1	1	r1	x	x	binop sink, x, x
g	1	1	x	r1	x	binop x, sink, x
h	1	1	x	x	r1	binop x, x, sink
m	1	1	r2	x	x	binop source1, x, x
q	1	1	r3	x	x	binop source2, x, x
e	1	0	x	r1	x	unop x, sink, x
l	1	0	r2	x	x	unop source1, x, x
r	1	0	r3	x	x	unop source2, x, x
	0	0	x		1	jd
s	x	x	x	x	x	any instruction
	x	x	x	x	x	any instruction
t	0	0	x		1	jd
	0	0	10000		0	j  10000
v	x	x	x		x	any instruction
w	0	1	x	x	1	store x, x
y	0	0	x		0	j x

Grouped dependencies: