Wednesday, November 09, 2005

GRACE C to VHDL flow

For the MONARCH project, Georgia Tech is tasked with developing the compiler and some productivity utilities. Yesterday, I covered the compiler and the GUI. Today, I'll try to tackle the "rapid prototyping front-end."

For the prototyping environment, I've developed an internal representation, the "Human-Readable Internal Representation" (HumIR), with very Python-like syntax. Due to the need to target the hardware directly, I chose to make it statically typed (for now), but try not to force the user to declare things unnecessarily (so if X & Y are signed 32-bit integers, then Z = X+Y will create Z as a signed 32-bit integer). An example function which adds two streams of numbers is below:

() = function add2streams():
strm_id0 = 0
strm_id1 = 1
strm_id2 = 2
while 1:
x = mon_streamPopF(strm_id0)
y = mon_streamPopF(strm_id1)
mon_streamPush(strm_id2, x + y, 0)

Having developed the IR, I went on to create a flow that "lowers" the IR from the input syntax to the same format the Trimaran front-end uses to hand off to the back-end (the so-called "MONARCH Dataflow Graph", or MDFG for short.) Involved in this process is expression-lowering (so "z=(a+b) * c" becomes "t=a+b; z=t*c", for instance), if-conversion (removing all if/else blocks in the code by adding a "predicate" which can mask the execution of a statement), static single assignment (SSA) formation (which takes a predicated function, inserts select operations and makes all dataflow explicit). Finally, the resulting program is converted to a graph form and sent to the back-end.

The nice thing about this IR and flow (other than the fact that indentation as block structure really rocks) is that it was designed with hardware synthesis in mind (a dataflow machine is remarkably like custom-designed hardware). So I extended the flow with an instruction selection module, a modulo scheduler, and an automated pipelining module to generate nicely pipelined VHDL.

One other thing that's kind of nice about the flow is that HumIR is a high-level language, and as such, it's pretty easy to convert from (a currently very restricted subset of) C to HumIR. Given that I happen to have access to a C parser (EDG's parser is included in Trimaran), I went ahead and wrote a module (very alpha-level) that converts from so-called pcode (which has lisp-like syntax, nice and easy to parse) to HumIR. So now I have a two-headed (C and HumIR), two-tailed (MONARCH and VHDL) beast. With any luck, I'll have a tech report out soon which I can distribute freely, and maybe even some conference or journal papers.

1 comment:

  1. There is also ; which is a great verilog tool.