C2G'12 Compiler

The c2g (C to Gates) compiler project is finally here, in greatly simplified form.

The real trick to compiling into hardware is simply to take things one bit at a time. Each value in the C2G'12 language is unsigned and 8 bits wide. Within the compiler, each value's computation is represented by a vector of 8 pointers (or index values) describing where each bit comes from. The source for each bit can be the constant 0 (ground), the constant 1 (Vcc), an input bit, or the output from a gate.

Fortunately for you, the code that does all that work is given to you. All that you need to do is to modify the c2g12.c source code so that it uses only a single type of gate for all designs. The single type can be any of:

• ITE (If-Then-Else): a one-of-two multiplexor
• NAND
• NOR

Because NAND and NOR are binary operators, they are slightly easier to implement than ITE for the current code structure. Note that C2G'12 supports either textual or dot output, and must make sure that your program generates valid code for both textual and dot output. You should use a function-like notation for the text output: something like NAND(a, b) rather than ~(a & b). For the dot output, label nodes with the operation name, e.g., NAND.

Focus your attention around mkgate(). There are currently helper routines that implement and(), or(), xor(), and not() by calling mkgate(); think in terms of modifying these to generate the equivalent gates using only the gate type that you have selected. There is also a small part of the main() which might need to be modified to print the resulting design, although there is already code there for this purpose.

Interestingly, the compiler as written already incorporates some basic optimizations which should be slightly more effective once you have implemented the "partial normalization" of always using the same gate type. A variety of simplifications, mostly based on identity relationships, are implemented in the routines that call mkgate(). Common subexpression elimination (CSE) is implemented very straightforwardly in mkgate() itself. Finally, dead code elimination is implemented by recursively marking needed gates using recurmark() and then skipping the unmarked ones in the printing code within main().

Conversion to a true normal form is somewhat complex, and hence not expected in this project. I prefer using Karplus method (PDF -- with the figures!) to normalize to Bryant's normal form, commonly known as a reduced ordered binary decision diagram, or ROBDD.

Grammar and Sample Input

The grammar for the language accepted is:

prog: (decl)* (stat)* EOF
    ;

decl: "INPUT" WORD ';'
    | "OUTPUT" WORD ';'
    | "SIGNAL" WORD ';'
    ;

stat: WORD '=' expr ';'
    ;

expr: expr1 (('&' | '|' | '^') expr1)*
    ;

expr1: expr2 (('<' | '>') expr2)*
     ;

expr2: expr3 (('+' | '-') expr3)*
     ;

expr3: expr4 ('*' expr4)*
     ;

expr4: NUMBER
     | WORD
     | '-' expr4
     | '!' expr4
     | '~' expr4
     | '(' expr ')'
     ;

The inputs, outputs, and signals are all assumed to be 8 bits wide. Inputs cannot be assigned to; outputs and signals can be assigned to just once each. Inputs are essentially externally driven busses, and bus lines that are not used may be omitted from the gate level design; i.e., an input that is not used is not really an input. Signals are essentially internal busses, which may be eliminated from the design if the compiler's analysis finds them unnecessary. Outputs are busses delivering the output signals; as such, it always must be specified how each is driven in any design. A really simple example input is:

INPUT a;
SIGNAL b;
OUTPUT c;
b = (a & 5);
c = !b;

Submitting Your Project

For your project, you should submit the usual type of tarball, containing:

• The complete C source code for your project.
• A make file called Makefile. This file should be configured such that "make" by itself will make the executable, "make run" will run the parser accepting input from stdin and generating textual (not dot) output to stdout, and "make clean" will remove the executable and any temporary files.
• An HTML "implementor's notes" file called c2g.html. The notes should be simple discussion of implementation concepts you used that are not obvious from the project sepcification nor from the C code and comments; it should document any errors you are aware of (half credit from documented errors). The HTML should be self-contained in that nothing should be referenced from other than the current directory (i.e., you may include an image, which would also be included in the tarball).

After you have registered with the server, submit the tarball here:

Your email address is .

Your password is .

Which type of student are you?
Undergraduate registered for EE599-004
Graduate registered for EE699-001

Although this is not a secure server, users are bound by the UK code of conduct not to abuse the system. Any abuses will be dealt with as serious offenses.