C2G'07 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'07 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 c2g07.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 ITEs for the current code structure.

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 "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().

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;

For your project, you should submit the usual type of tarball, generating an executable file named c2g07 as the output of your make file. The c2g07.c program can be compiled by something as simple as cc c2g07.c -o c2g07.