The HercuLeS high-level synthesis tool

HercuLeS is a high-level synthesis tool that automatically generates RTL VHDL for non-programmable hardware. HercuLeS translates programs in NAC (a bit-accurate typed-assembly language) to extended FSMDs (Finite-State Machines with Datapath) in VHDL. HercuLeS can also be used for direct synthesis of ANSI C code to VHDL with the help of a prototype translator from GIMPLE (GCC's) new intermediate representation to NAC.

Internally, HercuLeS comprises of two main components: a frontend (nac2cdfg) and a graph-based backend (cdfg2hdl):

• nac2cdfg: translator from NAC (N-Address Code) IR, to flat CDFGs represented in Graphviz
• cdfg2hdl: the actual HLS tool for automatic FSMD hardware and self-checking testbench generation from Graphviz files to VHDL

HercuLeS also has an additional ANSI C backend, allowing comparison of NAC programs to reference ANSI C application code and the rapid prototyping of applications (VHDL simulation can be slow depending on design complexity, input data and the simulator used).

VHDL code generated by HercuLeS can be simulated with GHDL and the industry-standard Modelsim. It is possible to generate VHDL using either the Synopsys packages (the "old" de-facto standard) or the official IEEE library packages.

HercuLeS supports IEEE-754 floating-point arithmetic (32-bit single and 64-bit double precisions) using the VHDL-2008 floating-point arithmetic package.

Further, HercuLeS supports fixed-point arithmetic via sfixed and ufixed vectors as defined by the great VHDL-2008 fixed-point arithmetic packages by David Bishop. For this option, HercuLeS should be notified (via command-line option) to use the IEEE packages.

A recent presentation of HercuLeS can be found here (UPDATED: 2012-12-21). It is also mentioned in the Downloads section.

• Multiple subprograms (procedures) and procedure calls
• GIMPLE-to-NAC prototype frontend
• NAC (N-address code) parsing and semantic analysis
• Support for SSA form IR (in-to-SSA and out-of-SSA translations) based on Appel's "really-crude" method and Aycock-Horspool's iteratively eliminating algorithms for minimal SSA
• Translation of NAC input programs to Graphviz CDFGs
• CDFG (organized as Graphviz graphs) parsing and semantic analysis
• Support of:
• IEEE-754 compliant floating-point arithmetic
• multi-precision integer (std_logic_vector) and fixed-point (sfixed, ufixed) arithmetic
• basic low-level IR operators
• extended FSMD model of computation
• "scalar" and "streamed" (emitting a series of result values over time) outputs
• single-dimensional arrays (Multidimensional arrays can always be reduced to single-dimensional ones via matrix flattening)
• parameter passing through array procedure arguments
• automatic inference of block-RAM storage (for FPGAs)
• Scheduling engines
• Sequential scheduling
• Control-aware ASAP scheduling
• Control-aware ASAP scheduling with operation chaining (2x-4x better performance)
• Optimizations
• Register optimization using linear-scan register allocation
• Source-to-source C code optimizer
• Integration of constant multiplication and division optimizations
• Polynomial expression optimizer (WIP)
• Integration of peephole-based optimizer
• Data flow analysis (conservative custom method using on-demand graph reachability checks)
• Interface to a graph matching (graph and subgraph isomorphism) engine
• Various APIs:
• Common abstract data types
• Combinatorial objects generator
• Interval arithmetic
• Data flow analysis
• Simple graphs (undirected and directed)
• Attributed graphs (undirected and directed)
• Generators
• VHDL design code (FSMD datapath and control)
• Self-checking VHDL testbench
• Various script files (Makefiles, shell scripts) for GHDL/Modelsim simulations
• Generation of Makefiles and scripts for running logic synthesis tools
• Hardware operator library (Configurable multipliers, Logarithm functions, Variable shifters, Dividers and modulo extractors)
• TODO list [UPDATED: 2013-02-05]
• New C frontend
• Multi-port memory synthesis (external tool available)
• Access to global data from any procedure. Currently only the "root" procedure can access globals
• Support of dynamically allocated data
• Support of record data types (WIP: supported by new C frontend under development)
• List scheduling with operation chaining optimizations
• Graph-based optimization engine (WIP: prototype development)
• Enhanced data flow analysis
• Recursive procedure support [UPDATE: currently supported in the C backend]

The current version (0.0.4) of the NAC programming language manual can be found here in HTML form and can be downloaded from here as a PDF file.

An ANSI C frontend, namely gimple2nac is under development for translating GIMPLE dumps from GCC compilation to NAC translation units. It is currently in usable state, provided that the current liminations of the GCC GIMPLE front end infrastructure are accounted. The GIMPLE front end is under heavy development; a future release of GCC will support the final textual GIMPLE grammar). The gimple-front-end branch is aiming to this purpose: to provide a fixed textual IR.

The textual GIMPLE IR will bare some similarities to the current format of GIMPLE dumps. As input, gimple2nac currently accepts the non-official grammar of GIMPLE files with the .004t.gimple suffix.

I am currently writing a document highlighting issues with code generation from GIMPLE dumps. You can find it here in HTML form and can be downloaded from here as a PDF file.

gimple2nac will be released under GPL, version 3 when the gimple-front-end branch will be merged to GCC mainline, and the corresponding grammar and semantic changes will propagate to my GIMPLE-to-NAC translator.

The following set of examples illustrates the high-level synthesis of NAC programs. They have been generated with SSA (Static Single Assignment) disabled and using the sequential scheduler. The examples have been selected so that the hardware operator library is not required. In the future, an obfuscated or encrypted version of the library will be included.
A self-contained ZIP file with these examples is available: nac-examples.zip
To run a simulation from this package, unzip the package, cd to the corresponding directory (e.g. fibo) and run:
./fibo.sh
provided that you have GHDL installed on your system. You will also need a Windows/Cygwin installation or gnuwin32 versions of standard Unix utilities: make, bash.
The simulation will need two files providing some IEEE extension functions/procedures. They are required only for running the simulations. These files are provided in the 00contrib subdirectory.
Each example (e.g. NAC program "design.nac") includes the following source files:

• NAC program: design.nac
• Reference vectors: design_test_data.txt

• VHDL design: design.vhd for the root procedure and any other VHDL files for each one of the called procedures (from root or from lower in the call tree hierarchy).
• Testbench: design_tb.vhd
• CDFG visualization: design.dot.png
• CFG visualization: design_cfg.dot.png
• GHDL Makefile: design.mk
• Bash script for VHDL simulation with GHDL: design.sh
• Diagnostic output: design_alg_test_results.txt (only in the ZIP file).

The files included in nac-examples.zip are also available for separate viewing from here:

• loop1 (a single loop for-loop counting from 0 to a configurable limit. The easiest example)
  Files: loop1.nac, loop1_test_data.txt, loop1.vhd, loop1_tb.vhd, loop1 CDFG, loop1 CFG, Makefile for GHDL simulation of loop1, Bash script for automating the simulation of loop1.
• fibo (iterative version of Fibonacci sequence generation)
  Files: fibo.nac, fibo_test_data.txt, fibo.vhd, fibo_tb.vhd, fibo CDFG, fibo CFG, Makefile for GHDL simulation of fibo, Bash script for automating the simulation of fibo.
• divider (sequential divider producing both quotient and remainder)
  Files: divider.nac, divider_test_data.txt, divider.vhd, divider_tb.vhd, divider CDFG, divider CFG, Makefile for GHDL simulation of divider, Bash script for automating the simulation of divider.
• isqrt (integer square root calculation)
  Files: isqrt.nac, isqrt_test_data.txt, isqrt.vhd, isqrt_tb.vhd, isqrt CDFG, isqrt CFG, Makefile for GHDL simulation of isqrt, Bash script for automating the simulation of isqrt.

The following set of examples illustrates the high-level synthesis of ANSI C programs. The overall process involves translation of C programs to GIMPLE, followed by processing from gimple2nac, nac2cdfg, and cdfg2hdl.
This set of examples has been generated with SSA (Static Single Assignment) enabled, using the ASAP scheduler and with block RAMs enabled.
A self-contained ZIP file with these examples is available: ansic-examples.zip
gcc-4.5.1 has been used for producing the .gimple files. From these files, the corresponding .nac is generated with "gimple2nac". The same rules apply (as above) for running a GHDL simulation.
The sieve design requires a full multiplier. An implementation of the mul operator is provided in file operpack_ieee.vhd. Its implementation is subject to change in the future (e.g. for better performance). Further, the simulation will need two files providing some IEEE extension functions/procedures. They are required only for running the simulations. These files are provided in the 00contrib subdirectory.
Each example (e.g. C program "design_generic.c") includes the following source files:

• ANSI C program: design_generic.c
• Reference vectors: design_test_data.txt

• GIMPLE file: design_generic.c.004t.gimple
• NAC file: design.nac
• VHDL design: design.vhd for the root procedure and any other VHDL files for each one of the called procedures (from root or from lower in the call tree hierarchy).
• Testbench: design_tb.vhd
• CDFG visualization: design.dot.png
• CFG visualization: design_cfg.dot.png
• GHDL Makefile: design.mk
• Bash script for VHDL simulation with GHDL: design.sh
• Diagnostic output: design_alg_test_results.txt (only in the ZIP file).
• NOTE: For the case of the "sieve" example, more design files are generated, since it comprises of two procedures: sieve (the root procedure) and isqrt (which is called by root).

The files included in ansic-examples.zip are also available for separate viewing from here:

• fibo (iterative version of Fibonacci sequence generation)
  Files: Input C file for fibo, GIMPLE file for fibo generated by gcc, fibo.nac, fibo_test_data.txt, fibo.vhd, fibo_tb.vhd, fibo CDFG, fibo CFG, Makefile for GHDL simulation of fibo, Bash script for automating the simulation of fibo.
• gcd (greatest common divisor)
  Files: Input C file for gcd, GIMPLE file for gcd generated by gcc, gcd.nac, gcd_test_data.txt, gcd.vhd, gcd_tb.vhd, gcd CDFG, gcd CFG, Makefile for GHDL simulation of gcd, Bash script for automating the simulation of gcd.
• linedraw (Bresenham's line drawing algorithm. Illustrates the use of streaming outputs)
  Files: Input C file for linedraw, GIMPLE file for linedraw generated by gcc, linedraw.nac, linedraw_test_data.txt, linedraw.vhd, linedraw_tb.vhd, linedraw CDFG, linedraw CFG, Makefile for GHDL simulation of linedraw, Bash script for automating the simulation of linedraw.
• sieve (sieve of Eratosthenes. Illustrates the use of global arrays and procedure calls)
  Files: Input C file for sieve, GIMPLE file for sieve generated by gcc, sieve.nac, sieve_test_data.txt, VHDL package containing array data type definitions for sieve, RAM memory model for block RAM inference, sieve.vhd, isqrt.vhd, sieve_tb.vhd, sieve CDFG, sieve CFG, isqrt CDFG, isqrt CFG, Makefile for GHDL simulation of sieve, Bash script for automating the simulation of sieve.

1. A recent (December 2012) presentation of the HercuLeS hardware compiler.
2. The HercuLeS reference manual in PDF and HTML. Chapter 8 describes the HercuLeS GUI
3. HercuLeS feature matrix in PDF and HTML
4. EBNF NAC grammar
5. NAC yacc/bison grammar
6. NAC lex/flex scanner
7. Basic flex/bison parser for NAC (nacparser)
8. NAC grammar for the GOLD Parsing System. The GOLD Parsing System is a parser generation framework.
9. TXL grammar for NAC. TXL is a source transformation language.
10. TXL pretty printer for NAC
11. [OLD] Sample test sets of software applications. The set include binaries generated by GHDL running on Fedora 8. These binaries are self-contained and can be run under any recent Linux distribution. Feel FREE to download this OLD demo: hls-demo-linux-0.0.1.tar.gz
    You should run this from a Linux command prompt. A slightly-different version (with interpreted and not built models) was also tested successfully on Cygwin/Windows XP.
    [UPDATED: 05-June-2010]
    
12. Preliminary documentation for nac2cdfg in HTML and PDF formats (covering command-line options).
13. Preliminary documentation for cdfg2hdl in HTML and PDF formats (covering command-line options).
14. [TBR] A complete example of a multi-function CORDIC.
15. [TBR] Performance comparison to other high-level synthesis tools.
16. [TBR] Self-contained peephole optimizer for NAC programs.