About

Cyclic Redundancy Check (CRC) is a standardized way to implement a degree of data validation and is used in various over the wire protocols, data checksums, etc. Naive implementations are a bitwise loop over an input message and highly inefficient. Detection of a CRC loop and transformation into either a table lookup or a combination of clmul + shift operations can speed up such code by 2X or more. This would include the CRC loop in the Coremark benchmark – detecting and optimizing that idiom results in about a 10% improvement in Coremark scores.

The detection of a CRC loop is a complex optimization with elements of vectorization, feedback loops, pattern matching, etc. It is further complicated by function inlining. At this time we have patches for LLVM which can detect the CRC in Coremark and generate a clmul optimized version. The detection is not as strong as the GCC patches, nor does it have the ability to generate table variants if the target processor does not have clmul.

We recently discussed this optimization with the wider LLVM RISC-V community. The takeaway was this work probably should be done in the generic optimizer rather than in a RISC-V specific pass.

RFC for Joe's implementation and merge request.

Stakeholders/Partners

RISE:

Imagination Technologies: Joe Faulls

Ventana: Mikhail Gudim

Ventana: Jeff Law

External:

Dependencies

Status

Development	IN PROGRESS
Development Timeline	NA
Upstreaming	IN PROGRESS
Upstream Version
Contacts	Jeff Law (Ventana)
Dependencies	None

Updates

12 Feb 2025

Moved to 1H2025

11 Jul 2024

Moved to 2H2024

05 Jun 2024

Last update to MR was late April. Unsure of status

27 Mar 2024

Joe Faulls (Imagination Technologies) seems to have picked up this work, which is greatly appreciated. Links to the discussion and MR provided above.

13 Jul 2023

After generally positive reception in RISC-V LLVM coordination meeting, Misha is looking to generalize the implementation so that it fits into the regular LLVM optimization pipeline
Review of relevant documentation and GCC's implementation for validation that a given loop is computing a CRC (linear feedback shift register)

28 Jun 2023

Project reported as priority for 1H2024

Browser not supported