vlang: Mapping Verilog Netlists to Modern Technologies

The LLVM compilation framework [12] provides a set of toolchains to enable compilation between any supported source-language to any supported target language. Source-languages are compiled into LLVM’s-IR, a strongly-typed RISC instruction-set. The IR is agnostic to the source and target languages. RISC instructions are simple operations such as add, or, xor, store, load, etc. Instructions may have: (a) 0 or more inputs and (b) 0 or 1 outputs. LLVM encodes the IR using single static assignment [13]. Control flow in the LLVM-IR is handled with the use of basic blocks and control flow graphs. A basic-block requires an entry to the block, a set of control-flow-independent instructions, and an termination point. Termination points can either be branch (br) or return (ret) instructions. Connections between basic-blocks are made if a branch exists to some other basic-block or itself. Connections between basic blocks can be represented graphically, which we refer to as a control flow graph (CFG). CFGs represent conditional flow of a program.

A Verilog-netlist encodes a hardware-design (e.g., an $n$-bit Adder, a registered and-gate) in terms of a device’s available programmable logic resources (e.g., DSPs, LUTs, etc.). We will refer to a device’s available programmable logic resources as device-specific primitives. In our work, we consider PLD netlist extraction processes which recover designs and represent them as a Verilog-netlist. We provide an example in Fig. 2. In Fig. 2(a) a registered-AND-gate is behaviourally described with Verilog. The same design is presented in Fig. 2(b); however, it has been encoded in terms of device-specific primitives.

Typical PLD-fabric consists of programmable elements such as look-up tables (LUTs), flip-flops (FFs), digital-signal processing blocks (DSPs) and on-chip memories (RAMs). Routing resources are required to route information to-and-from these hardware-blocks. A Verilog netlist describes the hardware design (which has been configured on the PLD) by structurally representing programmable-hardware resources (i.e., primitives) as Verilog modules. Connections between primitives are explicitly made through the use of wires [14]. For each primitive in the design, vlang will construct an LLVM-function, which we describe below.

vlang remaps a primitive’s inputs into LLVM-software datatypes (e.g., i1, i32, i43) which match the bit-widths of the inputs²²2Both LLVM and Verilog support variable-sized bitwidth datatypes. Since a Verilog module may have more than one output bus/net, vlang remaps output nets to pointers (sized to match the datatype-width of the net) as this provides the ability to obtain more than one output from a software function. Fig. 3, demonstrates this remapping, where Fig. 3(a) provides the original Verilog module and Fig. 3(b) provides the LLVM-function declaration generated by vlang.

Primitives on PLD fabric can either be combinational or clock triggered. We map both classes of primitives to LLVM-functions.

All primitives mapped into LLVM functions may only be executed sequentially and must preserve the functionality of the original hardware design. However, Verilog-netlists are a form of dataflow-graphs (DFGs) which expose explicit parallelism between operators. An example of this encoding is pictured in Fig. 7, where the logic equation:

is encoded as a DFG. Additionally, Verilog-netlists may contain feedback (e.g., a linear-shift feedback register). vlang must determine an ordering of the nodes in the dataflow graph which preserves the data flow between nodes (or synonymously, primitives). Typically, a topological ordering would suffice if the DFG was guaranteed to be acyclic [15]. Since Verilog-netlist DFGs may contain feedback paths, a topological ordering cannot be computed unless feedback paths in the graph can be handled.

Feedback loops in Verilog netlists can be divided into two classes: (a) sequential feedback and (b) combinational feedback. If a feedback edge passes through a clock-triggered element which saves state (i.e., a flip-flop), then this will be referred to as sequential feedback. Otherwise, combinational feedback occurs if all primitives along the feedback edge are a form of combinational logic. Our tool does not support combinational logic loops.

To schedule the execution of primitives, the corresponding DFG must be acyclic. We present a methodology to (a) identify feedback-edges (i.e., cycles) from flip-flops in a DFG, (b) temporarily modify the DFG to be acyclic by removing feedback, (c) schedule the acyclic DFG, and then reintroducing feedback edges to restore the functionality of the original circuit.

First, vlang must identify if there are cycles in the provided DFG. Recall, the DFG is a directed graph. vlang employs Tarjan’s Strongly-Connected Components algorithm [16] to the DFG, to discover any strongly-connected components (SCC), thereby discovering cycles. The vertices in each discovered SCC are inspected to ensure there exists at-least one flip-flop (as this permits valid feedback paths). If there are no flip-flops in any of the strongly-connected components, vlang will abort compilation. Otherwise, the flip-flops within the SCC must be modified to break the cycle/SCC (providing an acyclic graph).

Our procedure for flip-flop modification is outlined in Algorithm 1. For each flip-flop within an SCC, the modules which provide input (i.e., drivers) to the flip flop are inspected to see if the module is within the SCC. If a flip-flop’s driver is within the vertex set of the SCC, the edge (i.e., wire) connecting them is cut. The flip-flop driver pair is noted down in $R$, a key-value data structure, as these modules will need to be reconnected after scheduling has occurred.

Once Algorithm 1 has completed, vlang generates an ILP formulation for an LP solver to serialize the data-flow graph. We used the system of difference constraints ILP formulation from [17], which will provide a solution for an as-soon-as-possible (ASAP) execution schedule. We used the LP solver, lpsolve [18], to compute the schedule. As an example, if we serialized the DFG-encoding of Equation 1 using the ILP, the order of execution would be: $(\texttt{xor},\texttt{inv},\texttt{and},\texttt{or})$. Optimizations to the serialization process could be made by adjusting the SDC-constraint formulation; we have left this as future work.

However, with Algorithm 1, flip-flops will be scheduled to be connected to what it drives. For example, if a flip-flop drives an and gate, the flip-flop will be scheduled to execute just-before the and gate. However, the execution schedule of the modified flip-flops are not guaranteed to have the correct data driving it’s inputs.

Therefore, modifications to the schedule must be made to allow for the flip-flops to (a) propagate data to the necessary consumers and (b) permit the updating of the flip-flops by reattaching their original drivers. We outline this procedure in Algorithm 2. For each modified flip-flop, we make a copy of the flip flop and set the clock to zero (thereby disabling the flip-flop). This allows the consumers of the affected flip-flops to obtain the data at the correct time. However, the affected flip-flops also need to be updated at the correct time. Recall, vlang had stored the cut drivers from the flip-flops in a key-value data structure, $R$. To restore updates to the flip-flops, the original copy of the flip-flop is inserted into the schedule. The insertion point is just-after the latest start-time of all of it’s original inputs. This restores updates to the flip-flop and guarantees the driver’s data to be arriving at the flip-flop at the correct time.

Once the schedule has been generated and modified, the original DFG has been serialized. vlang will iterate through the schedule, and begin inserting call instructions to the the corresponding primitive-modules. Connections between modules are made with local variables, which are known as alloca instructions in LLVM. vlang uses the connection-information collected during it’s parsing stage to determine how may temporary registers (in the LLVM-IR sense) should be instantiated to simulate data-transfer using wires. If a subsection of a bus is set or read, vlang will use and/or logic to set or read from the sub-selected bus.

Upon completion of schedule-implementation, vlang produces a C header-file which provides the function-signature to call the top-level modules as a software function.

OpenCore is an online repository of hardware-designs represented in Verilog or VHDL. A number of designs from OpenCores have been selected to evaluate vlang’s ability to handle: (a) combinational-logic circuits, and (b) sequential-logic circuit with the possibility of feedback.

Recall that vlang produces an LLVM-IR program which reproduces the functionality of a Verilog-netlist, and thereby, the original design. Simultaneously, vlang also produces a C-header file to permit other programs to reference and use this program. The vlang produced LLVM-IR can be linked into a C program using the LLVM framework [24]. Once linked, the corresponding LLVM-IR can either be executed just-in-time [25] or compiled to a binary. To evaluate vlang, we compile the test-bench and vlang-produced LLVM-IR to a binary using llc and gcc [26]. Each C test-bench tests a large subset of all possible test-cases, providing an avenue to validate correctness. The number of unique test-cases issued for each OpenCore benchmark is detailed in Table II. We also compare vlang’s simulation results and times against two open-source tools, Icarus Verilog [20] and Verilator [19] and a commercial simulation tool, Modelsim. All simulators were provided with the same test-cases. For all of the OpenCore benchmarks, Icarus Verilog, Modelsim and vlang produced the correct results. However, Verilator is unable to produce correct results for the addertree and gcd benchmarks. This is due to a software-bug in Verilator, where certain feedback paths in the Verilog netlist are not handled correctly.

Additionally, we compare the execution time for each testbench with all three simulators. The results are outlined in Fig. 8. This figure does not include results for bcdadder, mod3 and andreg, as simulation times were on the order of $10^{-3}$ seconds. For a majority of the benchmarks, vlang is able to achieve a faster simulation time, compared to Icarus Verilog, Verilator and Modelsim. This is expected, as vlang is a compiled simulator [27]; these styles of simulators are known to provide faster execution time compared to event-driven simulators (Icarus Verilog, Verilator and Modelsim are event driven simulators) [28]. Overall vlang is $\sim 37.3\times$ faster than Icarus Verilog, $\sim 3.5\times$ faster than Verilator and $\sim 12.3\times$ faster than Modelsim. Although the focus of this paper is not on simulation, we were able to present vlang’s ability to: (a) produce an executable which reproduces the functionality of a Verilog-netlist with an LLVM-IR program and (b) be used a simulation tool, which is competitive in terms of simulation time and is cycle accurate.

We evaluate vlang’s portability by supplying vlang-produced LLVM-IR to LegUp, an open-source high-level synthesis tool from the University of Toronto [29]. Using LegUp, we compile the vlang-produced LLVM-IR to a Verilog design file, and target two devices, a Xilinx Kintex-7 device (xc7k70t-1fbg484) and an Intel Stratix V device (5SGXEA7N2F45C2), to study if the functionality of these designs are portable. With the Xilinx device, we also measure performance and area differences: the original design files (i.e., not the Verilog-netlists) are compiled with Xilinx’s ISE v14.7 and targeted for the Kintex-7 device. For Xilinx devices, area is gauged in terms of slices and number of LUTs and performance is measure in terms of $F_{\text{max}}$. For the combinational circuits in our OpenCore Benchmark suite, we used the worst-case estimated logic delay as our measure of $F_{\text{max}}$. The post place-and-route (PnR) area-and-performance metrics for the original design files are outlined in Table III.

To compare the HLS-generated circuits (from vlang’s LLVM-IR) to the original design files, we compiled the design’s Verilog-netlists with vlang. The vlang-produced IR was then supplied to LegUp. LegUp was set produce Xilinx-amenable Verilog, with a 1 ns clock-period. The HLS-generated circuit then underwent ISE’s compilation flow, again targeting the Kintex-7 device, with a 1 ns clock-period. The results are tabulated in Table IV. Using our C-test-benches along with vlang-produced IR, we confirmed the functionality of the Verilog-netlist from the Kintex-7 was successfully ported back to the same device using LegUp’s test-bench generation flow [29]. However, supplying vlang’s LLVM-IR to an HLS tool may affect the overall area of HLS-generated design as shown in Table IV. This is demonstrated for all benchmarks, where the number of Slices and LUTs increase. As a general trend, the increase in LUTs follows the complexity of the original design: for example, the gcd benchmark uses 135 Slice-LUTs in the original design and the vlang-mapped design uses 5952 LUTs, whereas the adder benchmark uses 16 LUTs in the original design and vlang-mapped design uses 370. Additionally, the divide benchmark is not route-able on the Kintex-7 device (the design uses 97% of the available slices on this particular device). The increase in area is primarily attributed to the HLS-tool’s ability to produce hardware designs from vlang’s LLVM-Functions. The LLVM-function replicates the behaviour of a low-level device-primitive; there is no guarantee that the HLS tool will remap these LLVM-functions into these same primitive. Instead, the HLS tool may proceed to use additional logic resources to implement the LLVM-function. Additionally, extra logic from: (a) the HLS-compiler will be introduced to the original design (e.g., introducing an FSM-controller to enable switching between functions), thereby adding additional area costs and (b) from duplicateds flip-flops on feedback paths. Another notable difference: the combinational circuits have transformed into sequential circuits. This is expected since HLS-tools will infer a clock-signal (which is propagated throughout the entire design). This allows HLS tools to insert register stages into the design, to improve of upon the performance (i.e., breaking-up the critical path, pipe-lining, etc.). This can be desirable, especially if the combinational circuit need not be combinational with the new device. In our case all combinational benchmarks had a significant improvement in $F_{\text{max}}$. If cycle-latency is a sensitive parameter for design portability, the current flow will not be suitable: the additional register stages may affect the circuit’s cycle-latency. LegUp (or any LLVM-based HLS tool) could be modified to reflect the original design’s clock usage (or lack thereof) in vlang’s IR, but this is left as future work. Introducing register stages into combinational logic also prevents Quartus from inferring the entire logic function into a LUT: several LUTS and register would need to be used to infer the behaviour of this function.

Lastly, we confirm the portability of vlang’s LLVM-IR by using LegUp HLS and targeting a Stratix V device. LegUp was set to target a 1 ns clock-period. The LegUp produced hardware design was then compiled with Quartus Prime 18.0 Standard Edition, where we set a target clock-period of 1 ns, and targeted the Stratix V device 5SGXEA7N2F45C2. We use the Stratix V ALM (adaptive logic module) count as our area metric. We characterize performance through $F_{\text{max}}$. Again, using our C-test-benches we used LegUp’s test-bench generation flow to verify the functionality of the Verilog-netlist from the Kintex-7 was successfully ported to a Stratix V device. Table V tabulates the post place-and-route performance and area metrics for the Intel Device.

We note on the performance and area characteristics on the HLS-generated circuits for both Xilinx and Intel devices. Although there is no direct area comparison between Intel and Xilinx devices, we compare the number of LUTs used in Xilinx device (from Table III) to the number of ALUTs used in the Intel device. As before, we observe an increase in area: this is primarily attributed to the HLS-tool’s inability to recognize the device-specific primitives as LLVM-functions. Lastly, the achieved $F_{\text{max}}$ for the combinational benchmarks when using vlang with LegUp HLS improve upon the baseline. Again, this is due to the HLS tool’s ability to (a) insert a clock signal to the design, and (b) insert register stages to break-up the critical path. Referring to Table IV and Table V, there is a performance difference between the designs on the Intel device versus the Xilinx device. From our investigation, we discovered that Quartus had purposed many LUTs as route-throughs introducing additional logic delay, thereby affecting the $F_{\text{max}}$. This differs from Xilinx’s ISE, where the majority of designs utilized routing tracks versus LUTs as route-throughs, thereby providing a higher $F_{\text{max}}$ overall. From our experiments, vlang’s IR was able to port designs originally intended for a Kintex-7 Xilinx FPGA to an alternative device technology, an Intel Stratix V device. We also demonstrated vlang’s LLVM-IR can be used as a software executable and can be integrated with other software-ecosystems.

High-level synthesis is a compilation flow which compiles a high-level language (e.g., C/C++) to a hardware description language (e.g., Verilog, VHDL) [35]. A number of algorithmic processes are required to map a high-level language to a hardware description language. The program will undergo a number of static and dynamic program analyses to either restructure the program to expose parallelism and make the program amenable for hardware. The restructured program will then undergo allocation, scheduling and binding. Generally, HLS tools take advantage of pre-exising compilation frameworks, such as LLVM or GCC [29, 36]. Our work produced LLVM-IR, to be suitable for usage with HLS compilers built within LLVM frameworks.