Optimizing an IR for Hardware Design. Innovation in Verification

Intermediate representations (IRs) between high level languages (C++, AI, etc.) and machine language are both commonplace (witness LLVM) and a continuing active area of research. Paul Cunningham (GM, Verification at Cadence), Raúl Camposano (Silicon Catalyst, entrepreneur, former Synopsys CTO and lecturer at Stanford, EE292A) and I continue our series on research ideas. As always, feedback welcome.

The Innovation

This month’s pick LLHD: A Multi-level Intermediate Representation for Hardware Description Languages, was published in PLDI 2020 and has 24 citations. The authors were all from ETH Zurich (University), Tobias Grosser is now an associate professor at Cambridge (UK).

We wrote recently on optimizing simulation performance through ML-trained compiler options. This paper instead looks at whether performance (or net design flow throughput) can be improved if the compiler generates an IR (intermediate representation) better optimized to needs across the design flow. This is in-line with ongoing compiler research for software in other domains such as AI. Simulation compilers already apply such methods. Optimization techniques here may suggest addition opportunities for performance tuning?

Paul’s view

I am often asked what Cadence’s view is on leveraging innovations from the open-source compiler community in our logic simulator, especially from the LLVM community. This month’s paper is on “LLHD”, an LLVM-like intermediate representation (“IR”) for hardware design. It’s the first work I’ve seen that describes an IR for hardware design that covers both the testbench as well as the DUT. The authors have also built a SystemVerilog frontend and a backend into LLVM which enables native code logic simulation on any platform already supported by LLVM. Nice!

Overall, this is a meaty paper with some significant contributions. For example, LLHD includes a crisp notation and associated semantics for handling concurrency and event time windows. Another contribution is a well thought out system for progressively refining behavioral constructs in the IR into structural/synthesizable constructs wherever possible, essentially mirroring some of the “RTL rewriting” optimizations that commercial logic synthesis and simulation tools do under the hood.

As a framework for stimulating more academic investment into logic simulation and logic synthesis, LLHD looks awesome. It can enable research into high level optimizations (IR rewrites) to improve logic synthesis PPA and logic simulation performance. As to the question of rewriting our tools at Cadence to use LLHD rather than their existing proprietary IRs, these would be massive projects with very long tails to reach maturity. Probably, any interesting innovations by the LLHD community in the future would be best commercialized simply by re-implementing them on our existing proprietary IRs. We’ll keep watching this space and do what we can to support more academic investment into any area that could potentially lead to innovations that improve synthesis PPA or logic simulation performance for our customers.

Raúl’s view

The evolution of software compilation has been remarkable in recent years, partly due to the existence of an open-source framework that includes LLVM (originally meaning Low Level Virtual Machine) as a central component, specifically its language independent intermediate representation (IR). Conversely, the authors of the reviewed paper argue that “hardware design flow remains isolated and vendor-locked”. To address this issue, they are developing LLHD, a multi-level IR for hardware description languages. The framework also includes Moore, a compiler that translates SystemVerilog and VHDL to LLHD, LLHD-Blaze, a simulator leveraging just-in-time (JIT) code generation, and compiling a structural form of LLHD (with some optimizations) to support vendor-specific tools such as simulation, synthesis and verification. This approach aims to eliminate redundancy in compilation and tool-specific IRs and serve as a platform for interoperability and new tool development.

The paper provides an in-depth description of LLHD, defining a multi-level IR that captures current HDLs in an SSA (Single Static Assignment) based form compatible with modern compilers while incorporating extensions to represent digital hardware and the testbench. It demonstrates how SystemVerilog and VHDL map to LLHD. LLHD consists of three levels: behavioral, structural, and netlist, explicitly omitting layout. The paper shows transformations from behavioral LLHD to structural LLHD, encompassing typical high-level synthesis and compile techniques such as code motion, complexity reduction of operations, arithmetic optimization, identification of flip-flops and latches, and de-sequentialization.

Furthermore, the authors illustrate the integration of existing EDA tool flows by providing a simple structural Verilog equivalent. They evaluate their framework on ten small designs, with the most complex being a RISC-V core comprising 3479 lines of code, in terms of memory usage and simulation time on LLHD-Blaze.

The paper elicits mixed reactions. The paper is certainly rich in content. Although multi-level IRs for HW have been previously explored, for instance by the high-level synthesis community (e.g., Gajski-Kuhn, 1983, Y-chart with behavior-structure-geometry), the emphasis here is on making an implementation publicly available. In terms of results, size comparisons gain significance primarily at the layout stage (geometry), which LLHD does not address, thereby reducing the relevance of these comparisons. The simulator achieves performance improvements up to 2.4 times faster (though 5.2 times slower for the largest example) compared to commercial simulators with full features, which may not be representative.

Nevertheless, the fundamental argument that open-source infrastructure and common IRs have been instrumental in the advancement of software compilers remains persuasive. The question arises: can a similar impact be realized for EDA tools? Could LLHD serve as a catalyst for research and development, despite common claim that hardware design and automation tool development involve far fewer individuals than software development? Undoubtedly, significant work remains to be done.

Also Read:

LLMs Raise Game in Assertion Gen. Innovation in Verification

High-speed PCB Design Flow

Perspectives from Cadence on Data Center Challenges and Trends