New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
ROM model not friendly for SymbiYosys K-Induction mode #3378
Comments
Thank you for this detailed bug report, I agree that this could be very relevant and quite hard to debug performance issue for some designs. Regarding potential solutions, I can think of a few approaches:
Regarding simple path constraints, I don't think they are particularly useful as a workaround for this specific problem. In general, however, looking into simple path constraints for sby/smtbmc is already on my TODO list. Also, the btormc solver already does support K-induction with simple path constraints. Currently sby only has BMC support for btormc, though, but adding a btormc prove mode is already planned. |
FYI, fixing this annoyance is on my TODO list |
This avoids provability regressions now that we infer more ROMs. This fixes YosysHQ#3378
Thanks for sorting this so quickly. It's probably no great suprise that this affects a few other places as well, and I just noticed that it's causing similar cases to fail for |
This approach sadly does not work well in cases where the ROM content is not fully defined and breaks existing formal tests in worse ways than regressing provability. Therefore I'm going to revert the change that automatically calls this from Trying to make it work better also uncovered some other issues in the formal flow that need to be resolved for this. I'm currently working on that. Even then, There are also some use cases with large, completely uninitialized ROMs where |
Steps to reproduce the issue
I've noticed that recently a simple testbench I wrote to check a combinational circuit using SymbiYosys'
prove
mode has started to observe a failing inductive case. While this isnt super relevant for a purely combinational circuit (as there should be no sequential element soprove
is unecessary), I think it is worth raising as an issue as this could affect similar cases. Below is a minimal SymbiYosys test case that exhibits the same behaviour.Expected behavior
As this is a basic combinational equivalence, I expect both the basecase and inductive case to prove easily for a depth of 1.
Actual behavior
The basecase proves easily, but the inductive case does not prove for any depth. This seems to be because
out
is being detected as a ROM (byproc_rom
) in recent versions of Yosys, and thus being substituted for a$mem_v2
ROM cell. This seems to be inplemented by backends with a pattern like the following (this is adapted fromwrite_verilog
output but it seemswrite_smt2
is doing something similar).This is modelling a ROM inductively, by declaring its values in the initial state, and then by
reg
semantics the values in each new clock cycle are equal to those in the previous.The inductive case in sby does not use the initial conditions, as it is considering traces from an arbitrary starting point that lead to a property violation. Thus using the above model, ROM values are left unconstrained for the inductive case which makes it hard for the inductive case to prove (k-induction needs a K sufficient to exclude all traces of valid states leading to a bad state).
Potential Solution
A potential solution is to replace the ROM model at least for formal focused backends (like
write_smt2
) with a continuous assignment model (like the original verilog code), so the values of the ROM values are clear on every timestep and present in the transition relation as well as the initial conditions. There is also an argument that could be made that the current implementation is fine as it reduces the number of clauses fed to the smt solver, particularly for a large ROM.I've submitted this as an issue rather than a PR changing this as it is my understanding that a lot of this memory inference code is quite new and thus subject to change/improvements etc.
An aside about completeness
Not entirely relevant for the above, but in smtbmc's current implementation of K-Induction (at least as far as I am aware, I may be wrong) there is no K sufficiently large to prove the inductive case for the above example, because it does not implement a complete (in the logic sense) proof algorithm. This is because it cannot determine when it has checked all possible induction traces, as it admits infinite length induction traces. This can be remedied by applying a simple path/loop free constraint to the induction trace, as described in https://www.di.ens.fr/~pouzet/cours/mpri/bib/sheeran-FMCAD00.pdf to determine the required K. If this were done it would have been able to prove the above example correct, even with the inductive ROM model, although inefficiently.
The text was updated successfully, but these errors were encountered: