calyxir/calyx

Intermediate Language (IL) for Hardware Accelerator Generators

A Compiler Infrastructure for Accelerator Generators

Calyx is an intermediate language and infrastructure for building compilers that generate custom hardware accelerators.

See the Calyx website, language documentation and the documentation for the source code for more information. Calyx's design is based on our paper.

Installation

Quick

If you want to try out the compiler, install it using cargo:

cargo install calyx

This will install the calyx binary can optimize and compile Calyx programs to Verilog or CIRCT.

Recommended

Follow the getting started instructions.

Organization

This repository contains the source code for the following:

• calyx-utils: Utilities for the Calyx compiler
• calyx-frontend: Parser and frontend AST for the Calyx language.
• calyx-ir: The Calyx intermediate language.
• calyx-opt: Optimizations for the Calyx intermediate language.
• calyx: The Calyx compiler driver.

You can also use the Calyx compiler as a library and implement your own optimizations. To do this, check out the example provided by the calyx-opt crate.

calyx's Issues

Replace the syntax wrapper for ast structure creation

I have various syntax wrappers for structure creation. I thought I needed this, but I guess I don't. I can probably fix this myself but I thought I should still write it down.

Testing infrastructure

Sooner rather than later we should set up some test infrastructure. I think for now we should focus on tests for passes that take one futil program to another futil program. For this we can use Adrian's turnt or maybe rusts module level tests. The advantage of Rusts test infrastructure is that we can write the equality in rust which would make testing robust to trivial changes to printing.

Instructions for compiler development in README

The README instructions are very sparse right now. Can someone add instructions on how to continuously build and test the compiler while development?

Things to Look Into

HLS Optimization

• Zhiru's papers?
• HeteroCL
• LegUp

RTL Backends

• Yosys
• SystemVerilog
• PyMTL (Rachit)
• HardCAML (Rachit)
• CLASH (Sam)
• CoreIR (Ken)
• FIRRTL (Ken)

Goals for Futil

• Can we generate RTL from it?
  • Can it be compiled fast (unlike HLS)?
  • Hardware support for Futil
• Can we write optimization passes on Futil?
  • Inlining
  • Scheduling/Timing
• Can we compile other languages to Futil?
  • Interoperation between multiple languages through Futil?
• Dahlia -> Futil Soundness

Consider using animations instead of GUI

It might be easier to have a simple looping animation to show all of the computations instead of a GUI (or maybe have both for debugging!)

Here is a simple example with all the code to make a GIF from an input set of images. It uses the animation functions from the pict library.

#lang racket

(require pict
         mrlib/gif
         slideshow/play)

(define (do-fade n)
  (fade-pict n (rectangle 30 30) (disk 30)))

(write-animated-gif
  (for/list ([n (in-range 0 1.2 0.2)])
    (pict->bitmap (scale (do-fade n) 3)))
  30
  "animated.gif"
  #:loop? true)

Make all the component functions immutable

inactive should be a set rather than a list

If a port is empty, default value to #f

Configurable control

From a conversation I just with @sampsyo.

I would be cool if the control could have statically configurable portions. This would be useful for cases when we want to build something like a CGRA. In it's simplest form, this configuration can be a sequence of bits stores somewhere that statically enable a mux somewhere and change the architectural behavior.

Add license

Add Futil documentation to the Cucapra website

Overlapping constants

It would be convenient to be able to have multiple constants with the same name and the same value. The second time you declare a constant with a same name, then it checks to make sure that the values and widths are the same, if so it just creates two wires from the same constant module.

ast_examples/counter.futil cannot be parsed

On running

./target/debug/calyx ast_examples/counter.futil

I get:

Error: 0: at line 43:
         (enable lt1 i0 const3)
         ^
expected ')', found (

Is the example broken? In order to make examples always work with the current compiler, I recommend turning them in tests: https://github.com/cucapra/dahlia/tree/master/src/test/should-run

Also, add the example to the README (#56) if it's meant to be introductory.

Probably don't need mutable control for visitor

Because we have Action::Change to change control nodes, I don't think that we need to give each visitor function a mutable reference to its control statement.

Update readme to be accurate

Library Declaration Proposal

I don't know if this is the best idea, but...

Maybe we should introduce syntax for library declarations that declare the interface for primitive components:

The reason to do this explicitly so that we have a well defined source where primitives are defined that is not just documentation + implementation, and maybe this would also be useful if different backends supported different sets of primitives.

The syntax would look something like this:

(library
  (declare-component (name params ...)
    ((port in-a 32) ...)   ; inputs
    ((port out-a 32) ...) ; output ports
   ; maybe more flags, like whether it increments the time stamp
  )

  ...
)

@kwf37 Let me know what you think

Reducing the size of generated verilog file

The verilog file we generated is very large. It is because of two issues we might want to optimize for:

First is compiler analysis to remove redundant components. For example,

let x: bit<32> = 0;
---
x := 1;
---
x := 2;
---
x := 3;

only needs to create structure for the last component.

Another issue is

let a = 10;
let b = 1;

creates 3 FSMs:

     (par
      (enable a0 const0)
      (enable b0 const1))

We actually want merge the 2 assignments to 1 component and enable it, which only creates 1 FSM.

Loan System Proposal

This proposes a system of statically "loaning" components to other components. This enables component reuse while providing a way of statically checking if the loan is legal. It also acts as a sort of dual to inlining, where a component can swallow another component for some amount of time and control the stepping of that component.

We propose both "caller" and "callee" syntax:

callee:

(define/component foo
  ([left 32] [right 32])
  ([out 32])
  ([X ([in 32]) ([out 32]) ()]) ; take some component matching this signature and call it X
  ( ; structure can use X as a component )
; control can enable X
)

caller:

(define/component bar
  ...
  (; structure
   [new foo1 (foo std_id)] ; pass std_id as the loaned component to foo when instantiating
   ...)
...)

A component is only loaned when the component that it is passed to is enabled. A component can not be loaned to multiple components in the same logical time step.

This proposal enables global memory reuse as well as a way to make FSM generation not break the semantics of Futil.

Syntax class for specifying port on submodule

Right now I have this nonsense:

    (pattern (u:id @ uport:id -> v:id @ vport:id)
             #:with fun #'(connect 'u 'uport 'v 'vport))
    (pattern (u:id -> v:id @ vport:id)
             #:with fun #'(connect 'u 'inf# 'v 'vport))
    (pattern (u:id @ uport:id -> v:id)
             #:with fun #'(connect 'u 'uport 'v 'inf#))
    (pattern (u:id -> v:id)
             #:with fun #'(connect 'u 'inf# 'v 'inf#))

It really seems like I should be able to factor out a syntax class that has two forms:
(x:id @ port:id) -> 'x , 'port and (x:id) -> 'x, 'inf#
and then rewrite the above in a single line. However, I wasn't able to do this without
needing parenthesis around the syntax class. In other words, I could factor it out, but then I would need to write (define/module ..... [(sub @ left) -> (out)] instead of [sub @ left -> out].
I wanted to avoid more parenthesis. I know, blasphemy.

Reorganize repo

We should archive the older interpreter written in Racket and move the calyx folder to be top-level. This will also involve a change to the github action to build the toplevel repo rather than a subdirectory.

CI for Calyx

If to Enable pass can result in data harzard

Current implementation of RemoveIf pass can result in data hazard. This pass changes

(if (@ gt0 out) (gt0 a0 const2)  [condition line]
         (enable y0 const3)  [true branch]
         (enable z0 const4)))))  [false branch]

to

(enable gt0 a0 const2 y0 const3 z0 const4)))

However, if some register, say a0, is enabled at both the condition line and true/false branch, then we cannot what value is updated to a0.
The solution to this can be 1) change the one step enable to two steps.
However, the fundamental problem is, 2) registers have both read enable and write enable. We should either assume read is always enabled, or create split the enable semantic.

To fix 1): We should Without backend, at the high-level futil, we should assume RemoveIf pass always change if to two steps, not one.
For 2): This actually depends on backend.
For example, MIPS32 has half clock cycle read and half clock cycle updates. Then merging two steps into one is no longer a problem as long as gt0 has a latency smaller than half of the clock cycle.
Or for register read and components that can be also enabled, we can always assume no control signal goes to them.

Improve error handling system

• move everything over to the monadic style
• explore adding richer stack information for debugging purposes so that it is easier to figure out where errors come from. We get this from panic!, but panic! just crashes the program, making it hard to have centralized error messages
• think about keeping track of source locations in Ast so that we can point to the code in error messages. this might prove to be harder than it's worth because the Ast will be changing so much.

Paper list

This is an issue to keep track of relevant papers:

• Competition, Micro IR
• Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine
• HLS Optimization Survey

Scheduling Papers:

• Dynamically Scheduled High-level Synthesis
  • Synthesis of Synchronous Elastic Architectures
• Combining Dynamic & Static Scheduling in High-level Synthesis

Resource Sharing Optimization

Implement a Futil optimization that reduces resource usage by reusing components

Lowered Futil Requirements

Here are some things I would like in Futil to make RTL generation easier. I will track these properties here:

• Each input port is only driven by a single output port
• No cyclic dependencies on components
• Single top-level Seq statement in control (no nesting)

Implement HLS scheduling

We need to demonstrate the viability and expressibility of Futil by showing that it can represent traditional HLS scheduling. We should implement this as a series of passes to lower general Futil control into a global schedule.

A global_schedule is a subset of Futil control that only has a top level seq and enables.

The way to attack this is to implement passes for each Futil control construct that removes it and replaces it with (seq (enable A ...) ...). Once we have a form of Futil with only seqs (arbitrarily nested) and enable, we can flatten the schedule.

comp/counter-up stops 1 to early

Add the enable/disable mux as new primitive

As we discussed in the meeting, let's add an enable/disable mux so that we can more easily get rid of these implicit enable bits on wires. Practically, these will be a way of inlining component level enable/disable.

Timing, Area and Energy Backend Information

We need to standardize how we pass information that the backend provides about the primitives up to the Futil pass framework so that we can implement binding and scheduling passes.

I think that this should probably be implemented through the library interface files. We should also consider having explicit annotations for Timing, Area, and Energy (maybe others?)

Parse empty sequentional composition to empty deactivation statment

At ast.rkt:247 I match on (par-comp '()) and just convert this to (deact-stmts '()) so that computation is triggered. It would be nice to do this in syntax rather than have a special case.

Utility syntax for unpacking several structs

This is not actually that necessary, but might be an interesting challenge.
Basically I'm looking for a nice way to extract all the values from a struct at once because it can get verbose to get just the field that you need of a struct.

I'm thinking something like this:
you have a structure: (struct my-fancy-struct (field-1 field-2 field-3) #:transparent)
Suppose a, b, c are all my-fancy-structs.
then

(let-struct-unwrap my-fancy-struct (a b c)
  (body ...)
)

would bind the names a-field-1, b-field-1, c-field-1, a-field-2, ... in the body.

I think this might not be possible because I couldn't find a way to get the field names from a struct.

Verilog backend validation broken

the Verilog backend should accept control that is just a single enable. right now, it only accepts programs that have a top-level seq and enables.

Better logging system

@rachitnigam Do you have experience with the racket logging system? I have a janky implementation in util.rkt atm, but I'm sure there is a better way.

Fail on warnings for github action

We should not allow code that produces warnings into the repository. To this end, we should update the github action to fail if there are warnings on a build.

ifseq and while-seq examples are broken

The files do not parse with the current compiler.

Rough CSP-style Futil Proposal

As we discussed last time, it seems clear that we need something like this. I'm not entirely happy with the following proposal, but at least it's something concrete to work with.

The idea is to change the semantics so that each component is always 'running' in a loop. Each component would have two special channels named something like start and done. Each component could additionally declare some number of named channels. We would introduce two new control primitives for dealing with channels, (send <channel>) and (recv <channel>). send waits until a component is recving on the other end of the channel. similarly for recv. For now, I think channel connections should be statically declared (presumably in the structure).

By default, a components control will be wrapped in a loop surrounded with send, and recv. So

(<control> ...)

becomes

(loop
  (seq (recv start)
          (<control> ...)
          (send done)))

Components additionally could manage the start and done signals explicitly to enable more granular control over the behaviour of the component.

Named backends

We should add a naming systems for backends so that we can select different backends from the cli. I think this will involve adding a name to the Backend trait in src/backends/traits.rs and updating the cli with a flag to choose the backend. We should also rename the rtl backend to verilog.

Use contracts everywhere!

I don't use contracts in any of my structures. I probably should? I just haven't bothered to look into how they work yet. I'll do that soon.

generate and install command line completion files

The structopt library that we use for the command line has an option to install completion files for bash, zsh, fish, and I think other shells. It would be nice to have a way to install these files. I've already played a little bit with this using rust's build.rs feature. The documentation for this is here: https://docs.rs/clap/2.33.0/clap/enum.Shell.html

Structural representation design problem

In Futil, a component can instantiate any number of subcomponents and each subcomponent has some list of input ports and output ports. A component can also connect the ports of subcomponents to ports of other subcomponents.

Suppose you have three subcomponents, A, B, C. Component A has to out ports, left and right. B and C both have one input port, called in. Suppose A.left is connected to B.in and A.right is connected to C.in. If you represent each subcomponent as a node and the connections as edges, then you don't know whether A.left is connected to B or A.right is connected to B. All that you know is that A is somehow connected to B. So you have to keep the port information somewhere. You can put it on the edges or keep pointer in the node to which edge matches to which ports.

To be concrete, the issue is to come up with a design for this problem and then implement it into the existing structure graph which is here.

Cycles in the computation graph cause subtle problems

I use a topological sort on the graph to figure out the order to process nodes. However, topological sorts are only well defined on DAGs, but computation graphs are not limited to DAGs. I think that I need to implement the worklist algorithm + some careful routing of the memory variables to get this working properly.

get rid of constants and replace with constant module

Add CLI option to output to file

It would be nice to easily control what gets printed out where from the command line. For example, maybe i want to see the debug output from the passes but I want to put the generated verilog into a file. This would look something like

calyx <futil file> -l <library> -d -o output.v`

(assuming that the default backend is Verilog)

Automated Futil AST generation

Automatically generate valid Futil AST for automated testing.

Refactoring

We want to reorganize some thins to clean things up.

Syntax: Structure Ast * Control Ast

parse : String -> Syntax
in memory representation : Syntax -> Structure Graph * Control Ast
identifier resolution : build map from identifiers to component definitions

some kind of validation : checks that structure is valid: port widths match, each component instance has a corresponding definition, wires reference actual ports, probably more stuff

Pretty Printer

Building a pretty printer for the Futil AST with nice indententation would be a nice QOL improvement. Here is the beginning of an implementation. In order to get nice indentation, doing something along the lines of this seems like a good idea. [Here](https://github.com/cucapra/dahlia/blob/master/src/main/scala/backends/futil/FutilAst.scala} is how I use that library in the Dahlia backend.

Workshop Conference List

Thread for figuring what workshops to submit Futil/Calyx to.

Cleanup unused code

There's a fair amount of old code left hanging in the repository. We should go through and remove everything that is not being used