CDC detection with yosys

[ldoolitt]

For years, I've wished for a tool that can probe an HDL design for CDC (clock-domain-crossings), but never talked anyone into doing that work for me. Now I finally tried it myself with yosys, and I'm glad I did. I learned a few things, and it's already helping me find defects in my $DAYJOB code base.

Attached for your amusement is a 260-line python program that sifts through a yosys-output json file, looking for bad or unexpected CDC. Its strategy is to iterate through all the DFF, tracing backwards from a D port, through all combinational logic, looking for DFF Q source terms. It can collect all the C net indices from those source terms, compare them with the C net used for the original DFF, and draw conclusions about CDC. It handles block memories, too; it assues that they're used intentionally as part of a CDC mechanism.

Well, yes, of course it has issues. One need is to choose a real name (not "magic_cdc") for a Verilog attribute marking intentional CDC regs. And most fundamentally, it needs to move beyond the it-works-for-me stage. Maybe some people would like a less-strict handling of top-level-module input pins.

Before special-casing memories, the yosys commands I used would explode block memory into individual DFF plus decoders. When used to cross clock domains (e.g., in a FIFO), the output register of such an exploded block-memory depends on all the data bits of its slice (in the clka domain), and all the readout address decoders (in the clkb domain). Bad, by definition. Also, the data structures were huge.

I am still learning about yosys's capabilities of transforming the design. The yosys commands I use are given in the comments of the attached python.

Here's how to demo / replicate my work so far. Download the two attachments, sift8.py and hw_netlist.ys (and rename them from the txt suffix that github likes).
sift8.txt
hw_netlist.txt
On a general-issue Linux box (I use Debian Stable) with development tools, python3, iverilog, and yosys installed, do:

  SIFTD=wherever_you_downloaded_the_attachments
  git clone https://github.com/BerkeleyLab/Bedrock
  cd Bedrock
  make -C badger/tests hw_test_tb
  yosys -s $SIFTD/hw_netlist.ys
  python3 $SIFTD/sift8.py hw_test.test.json

Expected output is one status line per DFF, followed by an index of clocks, and

OK1: 1752  CDC: 0  OKX: 33  BAD: 1

If accessing the git repo and other tools involved are somehow a hardship for someone out there, I can provide a 36K tarball containing all the relevant files, preprocessed and ready for the yosys step.

Note that I use yosys 0.23 (comes with Debian Stable). It Would Be Nice if I could keep doing that, but I'd understand if you point me to a newer version.

And of course, if there's already a native yosys one-liner that does this, please tell me about it. Or features could be added to let yosys take over some of this functionality? Efficiency wouldn't be the motivation for such work. For a larger design (14K LOC), I spend 98% of my CPU time in yosys, 2% in the post-processor. I have no particular love for python+json.

In general, please treat this as a request-for-comments. Improvements? Criticisms? Pointers to related (open-source) work?

[ldoolitt]

I'm disappointed this post didn't get any responses. Don't other people care about linting their designs?
Or is there some much better/easier way to get this result?

Here sift9.txt is an updated post-processing script. It separates the inputs of DFF, which squelched a couple of false-positives compared to the previous approach of combining them. It only applies the magic_cdc attribute to the D input. It also lists clocks by their net names instead of net number.

[ldoolitt]

Oh, I also confirmed this process works on yosys-0.33.
Congrats to the yosys team for sticking to a stable json format.

[nakengelhardt]

I'm also currently working on implementing CDC detection, but as a yosys plugin. I saw this and was very interested in looking at your code but just didn't find the time yet! We might consider integrating some infrastructure for detecting clock domains upstream, it seems like something that would find a variety of uses.

[ldoolitt]

I've been using this tool for a while now. Even with its limitations, I've found its analysis helpful in cleaning up a big design.

The time spent in yosys seems excessive: 10 minutes on a pretty fast computer, working on a 14K LOC code base.
Not counting the read_verilog at the beginning and the write_json at the end, my steps are

hierarchy -simcheck -auto-top
select t:$meminit_v2
delete
select -clear
proc
stat
select t:$memrd t:$memrd_v2 t:$memwr_v2
setattr -set keep_hierarchy 1
select -clear
flatten -wb
opt -fast -purge
synth -run :coarse
techmap
opt -fast -purge
hierarchy -check
stat
check

For the purposes of understanding where the time is spent, I processed stdout from yosys with a simple awk command

awk '/^[0-9.]+/{now=systime(); if (start==0) start=now; print now-start, $0}'

So the result is cumulative time (in seconds) vs. step. Ignoring the many sub-steps, my result was

0 1-145. Executing Verilog-2005 frontend ..
0 146. Executing HIERARCHY pass (managing design hierarchy).
1 147. Executing PROC pass (convert processes to netlists).
1 148. Printing statistics.
4 149. Executing FLATTEN pass (flatten design).
7 150. Executing OPT pass (performing simple optimizations).
28 151. Executing SYNTH pass.
28 152. Executing TECHMAP pass (map to technology primitives).
134 153. Executing OPT pass (performing simple optimizations).
634 154. Executing HIERARCHY pass (managing design hierarchy).
634 155. Printing statistics.
634 156. Executing CHECK pass (checking for obvious problems).
634 157. Executing JSON backend.

.. showing that 79% of the time is spent in the OPT pass -- specifically opt -fast -purge.
I argue that the choice of processing steps is at least conceptually orthogonal to the implementation as a json-analyzer vs. yosys-plugin.
@nakengelhardt, which TECHMAP-ish step do you use? Are there less aggressive OPT steps that could give equivalent results?

[nakengelhardt]

In my approach I'm not running on gate level at all, as I am doing it for linting-type analysis want to make sure I can provide information on every wire mentioned in the RTL so I stay pretty early in the flow (just hierarchy -top foo; proc; opt -fast; flatten). What would really matter here is not so much line count as number of gates; but absent other information 10min does sound a bit on the long side. You'd need to do a deep-dive into your design and script to figure out where the time goes. I wonder if there's a lot of cases of things that could be optimized by the passes you've omitted (e.g. are there perhaps a lot of integer constants and so everything is 32 bit operators, but you're not running wreduce, so opt later on has to painstakingly discover each bit of unused width at gate level)?

[ldoolitt]

The python program is now called cdc_snitch, and has grown to 282 lines. It seems useful in its current state. We even have it deployed for a couple of CI regression checks.

Documentation is posted at
https://berkeleylab.github.io/Bedrock/_gen_md/build-tools/cdc_snitch_md.html
and is also visible at
https://github.com/BerkeleyLab/Bedrock/blob/master/build-tools/cdc_snitch.md

I did mess with the yosys OPT steps, and reduced compute time by about 3X.
There's more optimization before the flatten, and less after the techmap.
Maybe that can still be improved, but I'm the wrong person to look at it.

Comments and discussion are welcome.
@nakengelhardt, I'd be curious to hear how its results compare with what you're working on.

[chili-chips-ba]

#4493 (comment)