Gaffe concept notes

gistfile1.txt

My concept is to create a generic graph traversal / dataflow infrastructure, and then define 3-4 concrete types depending on where we are in the flow.

At the core of this we have a general graph struct:

struct Graph<T> {
  root: GraphNode<T>,
  ...
}

And a GraphNode trait:

trait GraphNode<T> {
  fn children() -> &mut [&mut GraphNode<T>;
  fn parent() -> &mut GraphNode<T>;
  fn value() -> &mut T;
}

We provide iterators over particular GraphNode types, using downcasting to reject nodes which are not of that type, and the Visitor pattern to walk the entire graph. We also provide generic dataflow analysis support - given a domain, direction, transfer function, meet operation, and boundary condition, execute a query and return a response.

Passes map from Graph<T> to Graph<J>. Usually T == J, but for passes transforming into another representation, T != J. Eventually we can get more clever by having restricted pass types that we can schedule more efficiently or parallelize over. We can choose to save earlier graph representations or not - graphs should be serializable, ideally into both a human-readable format and an in-memory format (probably adjacency-list-based) for FFI purposes. However, graphs should be complete representations of the gateware - knowledge of a previous graph state should not be required for future graphs.

The synthesis flow from Verilog to XC7 bitstream would look approximately like this:
Verilog source file->VerilogIR, or Graph<VerilogASTNode>->many passes on the Verilog IR->GaffeIR (described below)->many generic optimization passes->XC7IR, or Graph<XC7Primitive>->many machine-specific optimization passes->placement passes->routing passes->XC7Bitstream

We would define VerilogIR and other language-specific IRs and XC7IR and other machine-specific IRs as needed,  perhaps with generic LanguageIR and MachineIR traits. GaffeIR serves as our LLIR equivalent, the lingua franca which all other tools hook into.

GaffeIR would be a Graph<Module>, where Module is a struct that looks something like this:

struct Module {
  inputs: Vec<Port>
  outputs: Vec<Port>
  structure: Graph<Box<ModuleType>>
}

Module implements ModuleType, as do (for example) AIGModule, BDDModule, a SLICEM struct, and so on. This allows a heterogeneous netlist representation for partial computing. Most of these types would implement Into and From for each other - for instance, an AIGModule can convert into a BDDModule, and a SLICEM can convert into an AIGModule model or vice versa. The exact functions defined on ModuleType will depend on what we're doing.