creduce for Calyx

[rachitnigam]

I was debugging #329 and wrote down a simple script for differential testing. Then, I slowly reduced the program to find a minimal program. A few problems that need to be handled (feel free to add more):

• Handling loops: When reducing a while loops, we can't just remove things from the loop body willy-nilly. Things that affect the condition should probably not be removed.
  • Implement a pass to conservatively detect all loop body groups that can affect the condition. Delay their removal.
• Conditionals: replace the conditional with one of the branches.
• Seq/Par: Remove half of statements.
• Invoke: Replace the outputs with a constant zero.

[rachitnigam]

References:

• bugpoint command in Yosys: http://www.clifford.at/yosys/cmd_bugpoint.html
• bugpoint in LLVM: https://llvm.org/docs/Bugpoint.html

[rachitnigam]

Simple script I wrote:

#!/usr/bin/env sh

set -euf -o pipefail

FILE='trmm.futil'
DATA='trmm.data'

FLAG1='-p validate -p remove-external-memories -p pre-opt -p compile-empty -p compile-control -p post-opt -p lower'
FLAG2='-p validate -p remove-external-memories -p pre-opt -p compile-empty -p top-down-cc -p post-opt -p lower'

fud e $FILE --to dat -s futil.flags "$FLAG1" -s verilog.data $DATA > one
fud e $FILE --to dat -s futil.flags "$FLAG2" -s verilog.data $DATA > two

cmp --silent one two && "outputs were the same" || echo "outputs were different!"

[sampsyo]

Cool. FWIW, it might not be a bad idea to try C-Reduce itself or hacking up LLVM's bugpoint somehow. The philosophy of those tools is often not to be particularly smart—for example, avoiding deleting stuff that influences a while loop's condition. C-Reduce has some C-semantics-aware passes, but it is still fairly effective with those turned off.

Put differently, even a pretty dumb reducer is way better than no reducer. And a smart reducer is likely a bit better than a dumb reducer but the delta is not as big.

[rachitnigam]

For a dumber reducer that might delete conditional-related code: in the first run of the script, calculate the number of cycles (using verilator). Any reduced test case will take no more cycles.

Now, use this cycle number as the bound in future reduction runs.

[rachitnigam]

It just occurred to me that we can actually turn this into a ~creduce~ csmith tool for Verilog—since we can carefully generate programs with particularly funky control flow, maybe we can use this to fuzz edge cases in Verilog synthesizers and simulators.

[rachitnigam]

This is already tracked in our Projects and isn't currently actionable so closing