A BBGates Sample

BBGates is actually one of the projects in the EE599/699 Optimizing Compilers course also taught by Prof. Dietz. This compiler takes a C program and literally converts it into an optimized gate-level design. Here's an example of what it does....

Input C Code

Our sample input file, testg.c, is about as simple a test case as is interesting:

int a, b, c;

f()
{
	b = 3;
	a = 10;
	while (a > b) {
		a = a - 1;
	}
	c = a - b;
}

So, what does that generate?

Sequential Output

The sequential output is just text (in gates.seq) that looks like:

0	lab(0)
1	const(0)
2	const(3)
3	st(b{1,1}, 2)
4	const(10)
5	st(a{1,1}, 4)
6	lab(1)
7	const(0)
8	ld(a{1,1})
9	ld(b{1,1})
10	gt(8, 9)
11	sel(10, 3, 2)
12	lab(3)
13	const(0)
14	ld(a{1,1})
15	const(1)
16	sub(14, 15)
17	st(a{1,1}, 16)
18	sel(-1, 1, 1)
19	lab(2)
20	const(0)
21	ld(a{1,1})
22	ld(b{1,1})
23	sub(21, 22)
24	st(c{1,1}, 23)
25	lab(4)

Notice that the final label is actually significant in that reaching that label is what terminates the program.

Gate-Level Textual Output

The gate-level output, generated using the -g command line option, outputs somewhat human-readable text (in gates) at the gate level:

G2 = XOR(_1, STATE_0_0_7)
G3 = XOR(_1, STATE_0_0_6)
G4 = AND(G2, G3)
G5 = XOR(_1, STATE_0_0_5)
G6 = AND(G4, G5)
G7 = XOR(_1, STATE_0_0_4)
G8 = AND(G6, G7)
G9 = XOR(_1, STATE_0_0_3)
G10 = AND(G8, G9)
G11 = XOR(_1, STATE_0_0_2)
G12 = AND(G10, G11)
G13 = XOR(_1, STATE_0_0_1)
G14 = AND(G12, G13)
G15 = XOR(_1, STATE_0_0_0)
G16 = AND(G14, G15)
G17 = XOR(_1, G16)
G18 = AND(G17, b_1_1_0)
G19 = OR(G16, G18)
G20 = AND(G17, b_1_1_1)
G21 = OR(G16, G20)
G22 = AND(G17, b_1_1_2)
G23 = AND(G17, b_1_1_3)
G24 = AND(G17, b_1_1_4)
G25 = AND(G17, b_1_1_5)
G26 = AND(G17, b_1_1_6)
G27 = AND(G17, b_1_1_7)
G28 = AND(G17, a_1_1_0)
G29 = AND(G17, a_1_1_1)
G30 = OR(G16, G29)
G31 = AND(G17, a_1_1_2)
G32 = AND(G17, a_1_1_3)
G33 = OR(G16, G32)
G34 = AND(G17, a_1_1_4)
G35 = AND(G17, a_1_1_5)
G36 = AND(G17, a_1_1_6)
G37 = AND(G17, a_1_1_7)
G38 = AND(G14, STATE_0_0_0)
G39 = XOR(_1, a_1_1_0)
G40 = XOR(_1, a_1_1_1)
G41 = XOR(_1, a_1_1_2)
G42 = XOR(_1, a_1_1_3)
G43 = XOR(_1, a_1_1_4)
G44 = XOR(_1, a_1_1_5)
G45 = XOR(_1, a_1_1_6)
G46 = XOR(_1, a_1_1_7)
G47 = XOR(G39, b_1_1_0)
G48 = AND(G39, b_1_1_0)
G49 = OR(G47, G48)
G50 = XOR(G40, b_1_1_1)
G51 = AND(G40, b_1_1_1)
G52 = AND(G49, G50)
G53 = OR(G51, G52)
G54 = XOR(G41, b_1_1_2)
G55 = AND(G41, b_1_1_2)
G56 = AND(G53, G54)
G57 = OR(G55, G56)
G58 = XOR(G42, b_1_1_3)
G59 = AND(G42, b_1_1_3)
G60 = AND(G57, G58)
G61 = OR(G59, G60)
G62 = XOR(G43, b_1_1_4)
G63 = AND(G43, b_1_1_4)
G64 = AND(G61, G62)
G65 = OR(G63, G64)
G66 = XOR(G44, b_1_1_5)
G67 = AND(G44, b_1_1_5)
G68 = AND(G65, G66)
G69 = OR(G67, G68)
G70 = XOR(G45, b_1_1_6)
G71 = AND(G45, b_1_1_6)
G72 = AND(G69, G70)
G73 = OR(G71, G72)
G74 = XOR(G46, b_1_1_7)
G75 = XOR(G73, G74)
G76 = XOR(_1, G38)
G77 = AND(G16, G76)
G78 = AND(G38, G75)
G79 = OR(G77, G78)
G80 = AND(G12, STATE_0_0_1)
G81 = AND(G80, STATE_0_0_0)
G82 = XOR(_1, _1)
G83 = XOR(_0, _1)
G84 = XOR(G82, a_1_1_0)
G85 = XOR(_1, G84)
G86 = AND(G82, a_1_1_0)
G87 = OR(G84, G86)
G88 = XOR(G83, a_1_1_1)
G89 = XOR(G87, G88)
G90 = AND(G83, a_1_1_1)
G91 = AND(G87, G88)
G92 = OR(G90, G91)
G93 = XOR(G83, a_1_1_2)
G94 = XOR(G92, G93)
G95 = AND(G83, a_1_1_2)
G96 = AND(G92, G93)
G97 = OR(G95, G96)
G98 = XOR(G83, a_1_1_3)
G99 = XOR(G97, G98)
G100 = AND(G83, a_1_1_3)
G101 = AND(G97, G98)
G102 = OR(G100, G101)
G103 = XOR(G83, a_1_1_4)
G104 = XOR(G102, G103)
G105 = AND(G83, a_1_1_4)
G106 = AND(G102, G103)
G107 = OR(G105, G106)
G108 = XOR(G83, a_1_1_5)
G109 = XOR(G107, G108)
G110 = AND(G83, a_1_1_5)
G111 = AND(G107, G108)
G112 = OR(G110, G111)
G113 = XOR(G83, a_1_1_6)
G114 = XOR(G112, G113)
G115 = AND(G83, a_1_1_6)
G116 = AND(G112, G113)
G117 = OR(G115, G116)
G118 = XOR(G83, a_1_1_7)
G119 = XOR(G117, G118)
G120 = XOR(_1, G81)
G121 = AND(G28, G120)
G122 = AND(G81, G85)
G123 = OR(G121, G122)
G124 = AND(G30, G120)
G125 = AND(G81, G89)
G126 = OR(G124, G125)
G127 = AND(G31, G120)
G128 = AND(G81, G94)
G129 = OR(G127, G128)
G130 = AND(G33, G120)
G131 = AND(G81, G99)
G132 = OR(G130, G131)
G133 = AND(G34, G120)
G134 = AND(G81, G104)
G135 = OR(G133, G134)
G136 = AND(G35, G120)
G137 = AND(G81, G109)
G138 = OR(G136, G137)
G139 = AND(G36, G120)
G140 = AND(G81, G114)
G141 = OR(G139, G140)
G142 = AND(G37, G120)
G143 = AND(G81, G119)
G144 = OR(G142, G143)
G145 = AND(G79, G120)
G146 = OR(G81, G145)
G147 = AND(G38, G120)
G148 = AND(G15, G80)
G149 = XOR(_1, b_1_1_0)
G150 = XOR(_1, b_1_1_1)
G151 = XOR(_1, b_1_1_2)
G152 = XOR(_1, b_1_1_3)
G153 = XOR(_1, b_1_1_4)
G154 = XOR(_1, b_1_1_5)
G155 = XOR(_1, b_1_1_6)
G156 = XOR(_1, b_1_1_7)
G157 = XOR(G149, a_1_1_0)
G158 = XOR(_1, G157)
G159 = AND(G149, a_1_1_0)
G160 = OR(G157, G159)
G161 = XOR(G150, a_1_1_1)
G162 = XOR(G160, G161)
G163 = AND(G150, a_1_1_1)
G164 = AND(G160, G161)
G165 = OR(G163, G164)
G166 = XOR(G151, a_1_1_2)
G167 = XOR(G165, G166)
G168 = AND(G151, a_1_1_2)
G169 = AND(G165, G166)
G170 = OR(G168, G169)
G171 = XOR(G152, a_1_1_3)
G172 = XOR(G170, G171)
G173 = AND(G152, a_1_1_3)
G174 = AND(G170, G171)
G175 = OR(G173, G174)
G176 = XOR(G153, a_1_1_4)
G177 = XOR(G175, G176)
G178 = AND(G153, a_1_1_4)
G179 = AND(G175, G176)
G180 = OR(G178, G179)
G181 = XOR(G154, a_1_1_5)
G182 = XOR(G180, G181)
G183 = AND(G154, a_1_1_5)
G184 = AND(G180, G181)
G185 = OR(G183, G184)
G186 = XOR(G155, a_1_1_6)
G187 = XOR(G185, G186)
G188 = AND(G155, a_1_1_6)
G189 = AND(G185, G186)
G190 = OR(G188, G189)
G191 = XOR(G156, a_1_1_7)
G192 = XOR(G190, G191)
G193 = XOR(_1, G148)
G194 = AND(G193, c_1_1_0)
G195 = AND(G148, G158)
G196 = OR(G194, G195)
G197 = AND(G193, c_1_1_1)
G198 = AND(G148, G162)
G199 = OR(G197, G198)
G200 = AND(G193, c_1_1_2)
G201 = AND(G148, G167)
G202 = OR(G200, G201)
G203 = AND(G193, c_1_1_3)
G204 = AND(G148, G172)
G205 = OR(G203, G204)
G206 = AND(G193, c_1_1_4)
G207 = AND(G148, G177)
G208 = OR(G206, G207)
G209 = AND(G193, c_1_1_5)
G210 = AND(G148, G182)
G211 = OR(G209, G210)
G212 = AND(G193, c_1_1_6)
G213 = AND(G148, G187)
G214 = OR(G212, G213)
G215 = AND(G193, c_1_1_7)
G216 = AND(G148, G192)
G217 = OR(G215, G216)
G218 = AND(G146, G193)
G219 = AND(G147, G193)
_a_1_1_0 = G123
_a_1_1_1 = G126
_a_1_1_2 = G129
_a_1_1_3 = G132
_a_1_1_4 = G135
_a_1_1_5 = G138
_a_1_1_6 = G141
_a_1_1_7 = G144
_b_1_1_0 = G19
_b_1_1_1 = G21
_b_1_1_2 = G22
_b_1_1_3 = G23
_b_1_1_4 = G24
_b_1_1_5 = G25
_b_1_1_6 = G26
_b_1_1_7 = G27
_c_1_1_0 = G196
_c_1_1_1 = G199
_c_1_1_2 = G202
_c_1_1_3 = G205
_c_1_1_4 = G208
_c_1_1_5 = G211
_c_1_1_6 = G214
_c_1_1_7 = G217
_STATE_0_0_0 = G218
_STATE_0_0_1 = G219
_STATE_0_0_2 = G148
_STATE_0_0_3 = _0
_STATE_0_0_4 = _0
_STATE_0_0_5 = _0
_STATE_0_0_6 = _0
_STATE_0_0_7 = _0

Notice that each line deals only with a single bit of data. Also, each bit of each variable appears as two nodes: one read at the start of the clock cycle and a second, marked with an _ prefix, which is written at the end of the clock cycle.

Gate-Level Dot Output

The textual gate-level output is difficult to understand because it is so many lines. Thus, bbgates can also generate a graphical gate-level representation. It doesn't do that directly, but creates a Graphviz description suitable for processing by Dot. Rather than looking at the Dot file (in gates.dot), here's what it looks like as a PNG graphic:

Gate-Level Verilog Output

This is not quite standard Verilog code because $dumpfile is missing a file name -- but that's the only change needed to be able to run it through this HTML-form-interfaced Verilog compiler/simulator. Here's the Verilog code (in gates.v):

Trace Output

Notice the sneaky use of `define, which you should appreciate because it makes NAND and NOR gates take an identical representation. In any case, running that through the Verilog simulator generates a pretty big HTML response, which includes:

Trace Browser For VCD Generated By vvp Simulation

   $time     a_1_1    b_1_1    c_1_1 STATE_0_0
       0: xxxxxxxx xxxxxxxx xxxxxxxx  00000000
       1: 00001010 00000011 xxxxxxxx  00000001
       3: 00001010 00000011 xxxxxxxx  00000011
       5: 00001001 00000011 xxxxxxxx  00000001
       7: 00001001 00000011 xxxxxxxx  00000011
       9: 00001000 00000011 xxxxxxxx  00000001
      11: 00001000 00000011 xxxxxxxx  00000011
      13: 00000111 00000011 xxxxxxxx  00000001
      15: 00000111 00000011 xxxxxxxx  00000011
      17: 00000110 00000011 xxxxxxxx  00000001
      19: 00000110 00000011 xxxxxxxx  00000011
      21: 00000101 00000011 xxxxxxxx  00000001
      23: 00000101 00000011 xxxxxxxx  00000011
      25: 00000100 00000011 xxxxxxxx  00000001
      27: 00000100 00000011 xxxxxxxx  00000011
      29: 00000011 00000011 xxxxxxxx  00000001
      31: 00000011 00000011 xxxxxxxx  00000010
      33: 00000011 00000011 00000000  00000100

That's pretty self-explanatory, except for the $time. It takes two simulator time units per clock cycle, one up and one down, with the state machine triggered on positive edges... which is why updates happen only on odd simulation time units.


The C program that generated this page was written by Hank Dietz using the CGIC library to implement the CGI interface.


The Aggregate. Advanced Computer Architecture.