Skip to content
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

formal mismatch (div) #2508

Closed
drom opened this issue Dec 27, 2020 · 19 comments
Closed

formal mismatch (div) #2508

drom opened this issue Dec 27, 2020 · 19 comments
Labels

Comments

@drom
Copy link

drom commented Dec 27, 2020

Steps to reproduce the issue

The following 2 programs (A/B) reported as mismatched.

A

module top_mod(
  input  [3:0]  inp_e,
  output [24:0] tmp25
);
  wire [24:0] tmp17;
  assign tmp17 = 25'h0;
  assign tmp25 = 25'h5 / tmp17;
endmodule

B

module top_mod(
  input  [3:0]  inp_e,
  output [24:0] tmp25
);
  assign tmp25 = 25'h5 / 25'h0;
endmodule

Expected behavior

Expected to be equivalent.

Actual behavior

Yosys (Yosys 0.9+3755 (git sha1 442d19f, clang 11.0.0 -fPIC -Os)) reports mismatch between current and expected result:

ERROR: Found 25 unproven $equiv cells in 'equiv_status -assert'.

Can be reproduced with the following command:

#!/bin/bash

VFILE1=a_top_mod_old.v
VFILE2=a_top_mod_new.v
DUT=top_mod

../../YosysHQ/yosys/yosys -q -p "
  read_verilog $VFILE1
  rename $DUT top1
  proc
  memory
  flatten top1
  hierarchy -top top1
  read_verilog $VFILE2
  rename $DUT top2
  proc
  memory
  flatten top2
  equiv_make top1 top2 equiv
  hierarchy -top equiv
  clean -purge
  equiv_simple -short
  equiv_induct
  equiv_status -assert
"
@drom drom changed the title formal mismatch div(leq()) formal mismatch (div) Dec 27, 2020
@Ravenslofty
Copy link
Collaborator

Division by constant zero results in tmp25 being 25'bx. By default, neither equiv_simple nor equiv_induct model undefined states, so these are not considered equivalent.

Passing -undef to equiv_{simple,induct} solves the issue:

12. Executing EQUIV_SIMPLE pass.
Found 25 unproven $equiv cells (1 groups) in equiv:
 Grouping SAT models for \tmp25:
  Trying to prove $equiv for \tmp25 [0]: success!
  Trying to prove $equiv for \tmp25 [1]: success!
  Trying to prove $equiv for \tmp25 [2]: success!
  Trying to prove $equiv for \tmp25 [3]: success!
  Trying to prove $equiv for \tmp25 [4]: success!
  Trying to prove $equiv for \tmp25 [5]: success!
  Trying to prove $equiv for \tmp25 [6]: success!
  Trying to prove $equiv for \tmp25 [7]: success!
  Trying to prove $equiv for \tmp25 [8]: success!
  Trying to prove $equiv for \tmp25 [9]: success!
  Trying to prove $equiv for \tmp25 [10]: success!
  Trying to prove $equiv for \tmp25 [11]: success!
  Trying to prove $equiv for \tmp25 [12]: success!
  Trying to prove $equiv for \tmp25 [13]: success!
  Trying to prove $equiv for \tmp25 [14]: success!
  Trying to prove $equiv for \tmp25 [15]: success!
  Trying to prove $equiv for \tmp25 [16]: success!
  Trying to prove $equiv for \tmp25 [17]: success!
  Trying to prove $equiv for \tmp25 [18]: success!
  Trying to prove $equiv for \tmp25 [19]: success!
  Trying to prove $equiv for \tmp25 [20]: success!
  Trying to prove $equiv for \tmp25 [21]: success!
  Trying to prove $equiv for \tmp25 [22]: success!
  Trying to prove $equiv for \tmp25 [23]: success!
  Trying to prove $equiv for \tmp25 [24]: success!
Proved 25 previously unproven $equiv cells.

@drom
Copy link
Author

drom commented Dec 28, 2020

@Ravenslofty when I add -undef flag, this case got fixed, but many otherwise equivalent cases became non-equivalent :(

@Ravenslofty
Copy link
Collaborator

Without seeing your code there's no way for me to tell why that might be.

@drom
Copy link
Author

drom commented Dec 28, 2020

Here is the case which was EQ without -undef option, and now it is NON-EQ.

A

module top_mod(
  input  [14:0] inp_2,
  input  [19:0] inp_6,
  output        tmp19,
  output [14:0] tmp9
);
  wire [19:0] _GEN_0 = {{5'd0}, inp_2};
  assign tmp19 = 1'h0;
  assign tmp9 = _GEN_0 / inp_6;
endmodule

B

module top_mod(
  input  [14:0] inp_2,
  input  [19:0] inp_6,
  output        tmp19,
  output [14:0] tmp9);

  wire [14:0] _T;	// a_top_mod.fir:3:3

  wire [19:0] _T_0 = {{5'd0}, inp_2} / inp_6;	// a_top_mod.fir:8:13
  assign _T = _T_0[14:0];	// a_top_mod.fir:8:{10,13}
  assign tmp19 = 17'h1FFFF < {{2'd0}, _T};	// a_top_mod.fir:3:3, :9:{14,24}
  assign tmp9 = _T;	// a_top_mod.fir:3:3, :9:{14,24}
endmodule

@drom
Copy link
Author

drom commented Dec 28, 2020

How about?

  equiv_simple -short -undef
  equiv_induct -undef

@Ravenslofty
Copy link
Collaborator

I think the answer is actually to use sat not equiv_induct here.

  read_verilog a.v
  rename top_mod top1
  proc
  memory
  flatten top1
  hierarchy -top top1
  read_verilog b.v
  rename top_mod top2
  proc
  memory
  flatten top2
  equiv_make top1 top2 equiv
  hierarchy -top equiv
  clean -purge
  sat -enable_undef -prove-asserts -verify
12. Executing SAT pass (solving SAT problems in the circuit).

Setting up SAT problem:
Final constraint equation: { } = { }
Imported 19 cells to SAT database.

Solving problem with 5279 variables and 15265 clauses..
SAT proof finished - no model found: SUCCESS!

                  /$$$$$$      /$$$$$$$$     /$$$$$$$
                 /$$__  $$    | $$_____/    | $$__  $$
                | $$  \ $$    | $$          | $$  \ $$
                | $$  | $$    | $$$$$       | $$  | $$
                | $$  | $$    | $$__/       | $$  | $$
                | $$/$$ $$    | $$          | $$  | $$
                |  $$$$$$/ /$$| $$$$$$$$ /$$| $$$$$$$//$$
                 \____ $$$|__/|________/|__/|_______/|__/
                       \__/

@drom
Copy link
Author

drom commented Dec 28, 2020

@Ravenslofty thank you, I will try.

@drom
Copy link
Author

drom commented Dec 28, 2020

@Ravenslofty

sat -enable_undef -prove-asserts -verify

or

sat -enable_undef -prove-asserts -verify
equiv_status -assert

?

The second one gives me:

ERROR: Found 16 unproven $equiv cells in 'equiv_status -assert'.

@Ravenslofty
Copy link
Collaborator

Actually, no. I got sat set up using miter, which fails.

Helpfully though, sat -show-public shows an example failing case.

Consider inp_2 = 15'b11111111011111x and inp_6 = 20'b1.

On A, the result of tmp_19 in A is 1'b0 (by direct assignment).

On B, the x bit from inp_2 sets _T_0 to x, _T to x, and then tmp19 to x.

So the reason these are failing as not equivalent is because they are indeed not equivalent in the presence of undefined states.

@Ravenslofty
Copy link
Collaborator

  read_verilog a.v
  rename top_mod top1
  proc
  memory
  flatten top1
  hierarchy -top top1
  read_verilog b.v
  rename top_mod top2
  proc
  memory
  flatten top2
  clean -purge

  miter -equiv -make_assert -flatten top1 top2 miter
  sat -verify -prove-asserts -enable_undef -show-public miter

No equiv_status -assert because sat seems to ignore $equiv cells.

   ______                   ___       ___       _ _            _ _
  (_____ \                 / __)     / __)     (_) |          | | |
   _____) )___ ___   ___ _| |__    _| |__ _____ _| | _____  __| | |
  |  ____/ ___) _ \ / _ (_   __)  (_   __|____ | | || ___ |/ _  |_|
  | |   | |  | |_| | |_| || |       | |  / ___ | | || ____( (_| |_
  |_|   |_|   \___/ \___/ |_|       |_|  \_____|_|\_)_____)\____|_|


  Signal Name              Dec       Hex                     Bin
  ---------------- ----------- --------- -----------------------
  \gate._T_0                --        --    xxxxxxxxxxxxxxxxxxxx
  \gate.inp_2               --        --         11111111011111x
  \gate.inp_6                1         1    00000000000000000001
  \gate.tmp19               --        --                       x
  \gate.tmp9                --        --         xxxxxxxxxxxxxxx
  \gate_tmp19               --        --                       x
  \gate_tmp9                --        --         xxxxxxxxxxxxxxx
  \gold.inp_2               --        --         11111111011111x
  \gold.inp_6                1         1    00000000000000000001
  \gold.tmp19                0         0                       0
  \gold.tmp9                --        --         xxxxxxxxxxxxxxx
  \gold_tmp19                0         0                       0
  \gold_tmp9                --        --         xxxxxxxxxxxxxxx
  \in_inp_2                 --        --         11111111011111x
  \in_inp_6                  1         1    00000000000000000001
  \trigger                   1         1                       1

@Ravenslofty
Copy link
Collaborator

You can go even further with sat -max_undef:

  read_verilog a.v
  rename top_mod top1
  proc
  memory
  flatten top1
  hierarchy -top top1
  read_verilog b.v
  rename top_mod top2
  proc
  memory
  flatten top2
  clean -purge

  miter -equiv -make_assert -flatten top1 top2 miter
  sat -verify -prove-asserts -enable_undef -max_undef -show-public miter
   ______                   ___       ___       _ _            _ _
  (_____ \                 / __)     / __)     (_) |          | | |
   _____) )___ ___   ___ _| |__    _| |__ _____ _| | _____  __| | |
  |  ____/ ___) _ \ / _ (_   __)  (_   __|____ | | || ___ |/ _  |_|
  | |   | |  | |_| | |_| || |       | |  / ___ | | || ____( (_| |_
  |_|   |_|   \___/ \___/ |_|       |_|  \_____|_|\_)_____)\____|_|


  Signal Name              Dec       Hex                     Bin
  ---------------- ----------- --------- -----------------------
  \gate._T_0                --        --    xxxxxxxxxxxxxxxxxxxx
  \gate.inp_2               --        --         xxxxxxxxxxxxxxx
  \gate.inp_6               --        --    xxxxxxxxxxxxxxxxxxxx
  \gate.tmp19               --        --                       x
  \gate.tmp9                --        --         xxxxxxxxxxxxxxx
  \gate_tmp19               --        --                       x
  \gate_tmp9                --        --         xxxxxxxxxxxxxxx
  \gold.inp_2               --        --         xxxxxxxxxxxxxxx
  \gold.inp_6               --        --    xxxxxxxxxxxxxxxxxxxx
  \gold.tmp19                0         0                       0
  \gold.tmp9                --        --         xxxxxxxxxxxxxxx
  \gold_tmp19                0         0                       0
  \gold_tmp9                --        --         xxxxxxxxxxxxxxx
  \in_inp_2                 --        --         xxxxxxxxxxxxxxx
  \in_inp_6                 --        --    xxxxxxxxxxxxxxxxxxxx
  \trigger                   1         1                       1

@drom
Copy link
Author

drom commented Dec 28, 2020

 miter -equiv -make_assert -flatten top1 top2 miter
 sat -verify -prove-asserts -enable_undef -max_undef -show-public miter

Fails 20% of passing cases with error:

ERROR: Called with -verify and proof did fail!

Like this one:

A

module top_mod(
  input  [19:0] inp_0,
  output        tmp6
);
  assign tmp6 = 1'h0;
endmodule

B

module top_mod(
  input  [19:0] inp_0,
  output        tmp6);

  assign tmp6 = {{3'd0}, inp_0} >= 23'h5054FE;	// a_top_mod.fir:3:3, :6:{13,24}
endmodule

@Ravenslofty
Copy link
Collaborator

Once again, when you include undefined states in inp_0, tmp6 is 0 in the first case and x in the second.

@drom
Copy link
Author

drom commented Dec 28, 2020

@Ravenslofty could you explain how 23'h0xxxxx >= 23'h5054FE could result with x?

@Ravenslofty
Copy link
Collaborator

Ravenslofty commented Dec 28, 2020

Because the result of an operation on something with x is x.

@drom
Copy link
Author

drom commented Dec 28, 2020

In Verilog?
image

@Ravenslofty
Copy link
Collaborator

5.1.7 Relational Operators

An expression using these relational operators [>, >=, <, <=] shall yield the scalar value 0 if the specified relation is false or the value 1 if it is true. If either operand of a relational operator contains an unknown (x) or high-
impedance (z) value, then the result shall be a 1-bit unknown value (x).

I read this to mean even a single x bit is enough to make the result of your comparison x.

@drom
Copy link
Author

drom commented Dec 29, 2020

You are right about being X-pessimistic :(

@udif
Copy link
Contributor

udif commented Dec 29, 2020

I was surprised by this, becoming sad and happy at the same time. I was always under the impression that a testcase like this:

module test;
initial
begin
$display("%d", 16'h200x > 16'h1234);
$display("%04x", 16'h7x00 + 16'h1234);
end
endmodule

Would produce:
1
xx34

But instead is produces:
x
xxxx

I'm sad because this level of pessimism is not needed, but I'm happy because it makes 4-state simulation so much easier.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

4 participants