Verilog Compiler project

Verilog Compiler

This was a large project I did for Pittsburgh Simulation Incorporated during 2002 and 2003. The Verilog language specification is available as IEEE standard 1364. Verilog is used to specify the interconnection of cells and modules that comprise digital logic circuits.

  module CLKBUF ( A, Z );
    input  A;
    output Z;
    wire NET_1;
    CBN11M4V15L DRV2S3 ( .A(NET_1), .Z(Z) );
    CBN11M4V15L DRV2S2 ( .A(NET_1), .Z(Z) );
    CBN11M4V15L DRV2S1 ( .A(NET_1), .Z(Z) );
    SBNSV15L DRV1S1 ( .A(A), .Z(NET_1) );
  endmodule

These circuits can have millions of cells and the files to be compiled can be tens to hundreds of megabytes in size. Pitsim makes a simulator accelerator and needed a compiler to produce the binary data for their V400 machine.

After some research, I concluded that doing the compiler in Java using the JavaCC parser generator tool and the Purdue JTB (Java Tree Builder) tool would be the best solution. There were concerns that Java would be too slow but that has not been the case. The Java Hotspot compiler does an amazing job at producing fast running code. I used Borland's JBuilder IDE for all my development.

One of the most important design decisions was what intermediate representation to use within the compiler. I chose a graph with two kinds of vertices, cells and net vertices. I used a free java graph package developed by David Goldschmidt at RPI. I was not sure what graph algorithms might be useful and it has turned out that we have not needed anything tricky. Choosing a graph intermediate structure was a good move. It turned out that the compiler was required to modify the graph in many ways to make the circuits fit into the simulation capabilities of the V400. Many kinds of "no output" cells such as pull ups, and capacitors, had to be removed. Wired-or connections, on the other hand, required "node resolution cells" to be inserted into the graph. Special primary input cells had to be inserted. There were also larger clock spines that had to removed. After parsing and graph manipulation, the Verilog compiler has a large number of graphs, one for each module. Walking over these graphs recursively using a stack or modules to keep track of where in the hierarchy we are is used to emit two text files.

Graphs are the main data structure that are needed to emit the fanout information. The new Java JDK1.4 provides a facility for saving Java Beans and other data structures into an XML file for long term persistence. I have written custom persistence delegates for the Goldschmidt Graph package that allow the Verilog compiler to save and restore module graphs as needed. I believe this will allow us to handle very large circuit designs by swapping graphs to disk as needed. I wrote a paper on this technique for the June 2003 issue of JavaPro magazine.

The Verilog compiler emits two files in text format. One lists all cell instance names with the cell type and a fanout count. e.g.

   u_glue_spare1.u_spare_flop FL1S2KQV15L   2

The other describes the netlist interconnections with the from instance name and output pin with the module name in the first line followed by lines describing the target connections.

   B24.Z CKT_TOP
    A2 on U2
    A on U1.U14
    A on U5
    A on U3

The files are used by a Resolver and a Mapper program which ultimately emits the binary code that is loaded into the V400. There are cooresponding SDF (Standard Delay Format) files that are compiled by an SDF compiler. SDF 3.0 is specified by Open Verilog International. I used JavaCC for the SDF too, but abandoned the JTB and placed the semantic actions directly into the grammar. The SDF files are huge but simple; building an AST was too slow and took to much memory.

This was a large and complex project. Using Java and the JavaCC and JTB tools was a good choice. We are now working on scaling everything up to larger and larger circuit designs. Memory usage and managment is a key issue but Java, particularly JDK1.4, seems up to the task.