Non-Recursive Verilog Generator

[gkelly]

We used Kaze as part of our intern's hardware fuzzing project to generate lock-like structures--state machines that require a sequence of clocked inputs to reach a goal state. If you take a look at how the linked generator works it builds mux chains to construct an FSM, specifically https://github.com/googleinterns/hw-fuzzing/blob/master/hw/lock/hdl_generator/locksmith/src/main.rs#L78. When lowering to Verilog the approach that Kaze takes currently is to recursively generate expressions. Since this is a deeply nested expression this ends up running out of stack if the depth is too large.

Now, this isn't really an issue for the the hw-fuzzing projcet as the shallow locks are more than sufficient to prove the approach, but it did get me thinking about possible solutions. The recursive generation is very easy to understand, so maybe it makes more sense to take a page from nmigen and expose some sort of FSM construct: https://github.com/nmigen/nmigen/blob/master/examples/basic/fsm.py. Lowering can then be iterative over the conditions.

Module-level iterative lowering also seems like it could be an approach, but that seems like a lot of hassle. Either way, if you have opinions I'm happy to spend some cycles implementing.

Thanks for the Kaze project!

[yupferris]

Hi, very cool! I hope it was an enjoyable experience :) . Here are my thoughts:

I believe that if user code generates mux chains like this, it's not really unreasonable to expect that the compiler handles this by recursively visiting the graph - this is a natural way to do it (though ofc there are ways to do this without compiler recursion - it's probably worth keeping this ticket around to consider doing that throughout the compiler; I think that's a good idea).

I think the more pressing issue here is, as you point out, that kaze doesn't really have a good way to describe this kind of FSM in the first place. This is definitely something I want to improve. I've already added some toy syntax for if-like expressions, and I'd like to finalize that (#12). I can also imagine a similar one for match/switch or similar which I'd like to look into.

That leads us to some options for FSMs. A match/switch construct would cover these nicely (so I'd probably want to implement that first), but it might still make sense to have a dedicated FSM construct (perhaps implemented by lowering to reg/match), and it's something I would like to look into. Both of these alternatives give the user a better way to construct these structures on a more semantically-rich level, as well as giving the compiler more opportunity to both check for errors (eg. the same value checked in multiple case arms, which is likely an error) and generate better code (scaling breadth-wise instead of depth-wise, which is more natural), so it's hard to turn down.

When it comes to implementations/possible APIs for this, I think a good approach is to first try and design something that can be expressed by existing constructs internally, again like the if_ syntax today - this way we could iterate quickly without adding more semantics to the compiler at first. I've also done that with reg_next/reg_next_with_default in xenowing, which I'm playing with after seeing these in chisel.

I'm not sure what you mean by module-level iterative lowering, could you elaborate?

[yupferris]

It would seem this is practically a bigger problem than I had anticipated. Unrelated to FSM's, I just hit this issue with one of the build scripts I use to generate Rust sim code for the xenowing project (particularly, this one). I though it might be something strange/perhaps a bug I introduced in the compiler that didn't terminate properly, but it seems this is not the case: copying the build script code to a fresh Rust project and running in release it works fine, but hits a stack overflow in debug. Everything looks reasonably sane in a debugger, and it crashes in __chkstk as expected.

It's a bit odd that I haven't hit this before; I recall building this project just fine a few months ago, but I did make the GPU more complex since then, so it's possible that it's simply a result of the graph now being more complex and uncovering the issue. I was also under the impression that build scripts were built using the same profile as the rest of the build, so I would have expected that the build script code is built in release which I would imagine would avoid the issue, but it seems that's not the case (or it uses more stack for some other reason, not entirely sure).

In any case, it seems that this stack overflow is indeed legit, and this issue needs to be addressed sooner than I had anticipated.