2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Claire Xenia Wolf <claire@yosyshq.com>
6 * Permission to use, copy, modify, and/or distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 #include "kernel/yosys.h"
21 #include "kernel/satgen.h"
24 PRIVATE_NAMESPACE_BEGIN
26 struct EquivSimpleWorker
29 const vector
<Cell
*> &equiv_cells
;
33 dict
<SigBit
, Cell
*> &bit2driver
;
41 pool
<pair
<Cell
*, int>> imported_cells_cache
;
43 EquivSimpleWorker(const vector
<Cell
*> &equiv_cells
, SigMap
&sigmap
, dict
<SigBit
, Cell
*> &bit2driver
, int max_seq
, bool short_cones
, bool verbose
, bool model_undef
) :
44 module(equiv_cells
.front()->module
), equiv_cells(equiv_cells
), equiv_cell(nullptr),
45 sigmap(sigmap
), bit2driver(bit2driver
), satgen(ez
.get(), &sigmap
), max_seq(max_seq
), short_cones(short_cones
), verbose(verbose
)
47 satgen
.model_undef
= model_undef
;
50 bool find_input_cone(pool
<SigBit
> &next_seed
, pool
<Cell
*> &cells_cone
, pool
<SigBit
> &bits_cone
, const pool
<Cell
*> &cells_stop
, const pool
<SigBit
> &bits_stop
, pool
<SigBit
> *input_bits
, Cell
*cell
)
52 if (cells_cone
.count(cell
))
55 cells_cone
.insert(cell
);
57 if (cells_stop
.count(cell
))
60 for (auto &conn
: cell
->connections())
61 if (yosys_celltypes
.cell_input(cell
->type
, conn
.first
))
62 for (auto bit
: sigmap(conn
.second
)) {
63 if (cell
->type
.in(ID($dff
), ID($_DFF_P_
), ID($_DFF_N_
), ID($ff
), ID($_FF_
))) {
64 if (!conn
.first
.in(ID::CLK
, ID::C
))
65 next_seed
.insert(bit
);
67 find_input_cone(next_seed
, cells_cone
, bits_cone
, cells_stop
, bits_stop
, input_bits
, bit
);
72 void find_input_cone(pool
<SigBit
> &next_seed
, pool
<Cell
*> &cells_cone
, pool
<SigBit
> &bits_cone
, const pool
<Cell
*> &cells_stop
, const pool
<SigBit
> &bits_stop
, pool
<SigBit
> *input_bits
, SigBit bit
)
74 if (bits_cone
.count(bit
))
77 bits_cone
.insert(bit
);
79 if (bits_stop
.count(bit
)) {
80 if (input_bits
!= nullptr) input_bits
->insert(bit
);
84 if (!bit2driver
.count(bit
))
87 if (find_input_cone(next_seed
, cells_cone
, bits_cone
, cells_stop
, bits_stop
, input_bits
, bit2driver
.at(bit
)))
88 if (input_bits
!= nullptr) input_bits
->insert(bit
);
93 SigBit bit_a
= sigmap(equiv_cell
->getPort(ID::A
)).as_bit();
94 SigBit bit_b
= sigmap(equiv_cell
->getPort(ID::B
)).as_bit();
95 int ez_context
= ez
->frozen_literal();
97 if (satgen
.model_undef
)
99 int ez_a
= satgen
.importSigBit(bit_a
, max_seq
+1);
100 int ez_b
= satgen
.importDefSigBit(bit_b
, max_seq
+1);
101 int ez_undef_a
= satgen
.importUndefSigBit(bit_a
, max_seq
+1);
103 ez
->assume(ez
->XOR(ez_a
, ez_b
), ez_context
);
104 ez
->assume(ez
->NOT(ez_undef_a
), ez_context
);
108 int ez_a
= satgen
.importSigBit(bit_a
, max_seq
+1);
109 int ez_b
= satgen
.importSigBit(bit_b
, max_seq
+1);
110 ez
->assume(ez
->XOR(ez_a
, ez_b
), ez_context
);
113 pool
<SigBit
> seed_a
= { bit_a
};
114 pool
<SigBit
> seed_b
= { bit_b
};
117 log(" Trying to prove $equiv cell %s:\n", log_id(equiv_cell
));
118 log(" A = %s, B = %s, Y = %s\n", log_signal(bit_a
), log_signal(bit_b
), log_signal(equiv_cell
->getPort(ID::Y
)));
120 log(" Trying to prove $equiv for %s:", log_signal(equiv_cell
->getPort(ID::Y
)));
126 pool
<Cell
*> no_stop_cells
;
127 pool
<SigBit
> no_stop_bits
;
129 pool
<Cell
*> full_cells_cone_a
, full_cells_cone_b
;
130 pool
<SigBit
> full_bits_cone_a
, full_bits_cone_b
;
132 pool
<SigBit
> next_seed_a
, next_seed_b
;
134 for (auto bit_a
: seed_a
)
135 find_input_cone(next_seed_a
, full_cells_cone_a
, full_bits_cone_a
, no_stop_cells
, no_stop_bits
, nullptr, bit_a
);
138 for (auto bit_b
: seed_b
)
139 find_input_cone(next_seed_b
, full_cells_cone_b
, full_bits_cone_b
, no_stop_cells
, no_stop_bits
, nullptr, bit_b
);
142 pool
<Cell
*> short_cells_cone_a
, short_cells_cone_b
;
143 pool
<SigBit
> short_bits_cone_a
, short_bits_cone_b
;
144 pool
<SigBit
> input_bits
;
148 for (auto bit_a
: seed_a
)
149 find_input_cone(next_seed_a
, short_cells_cone_a
, short_bits_cone_a
, full_cells_cone_b
, full_bits_cone_b
, &input_bits
, bit_a
);
150 next_seed_a
.swap(seed_a
);
152 for (auto bit_b
: seed_b
)
153 find_input_cone(next_seed_b
, short_cells_cone_b
, short_bits_cone_b
, full_cells_cone_a
, full_bits_cone_a
, &input_bits
, bit_b
);
154 next_seed_b
.swap(seed_b
);
158 short_cells_cone_a
= full_cells_cone_a
;
159 short_bits_cone_a
= full_bits_cone_a
;
160 next_seed_a
.swap(seed_a
);
162 short_cells_cone_b
= full_cells_cone_b
;
163 short_bits_cone_b
= full_bits_cone_b
;
164 next_seed_b
.swap(seed_b
);
167 pool
<Cell
*> problem_cells
;
168 problem_cells
.insert(short_cells_cone_a
.begin(), short_cells_cone_a
.end());
169 problem_cells
.insert(short_cells_cone_b
.begin(), short_cells_cone_b
.end());
173 log(" Adding %d new cells to the problem (%d A, %d B, %d shared).\n",
174 GetSize(problem_cells
), GetSize(short_cells_cone_a
), GetSize(short_cells_cone_b
),
175 (GetSize(short_cells_cone_a
) + GetSize(short_cells_cone_b
)) - GetSize(problem_cells
));
177 for (auto cell
: short_cells_cone_a
)
178 log(" A-side cell: %s\n", log_id(cell
));
180 for (auto cell
: short_cells_cone_b
)
181 log(" B-side cell: %s\n", log_id(cell
));
185 for (auto cell
: problem_cells
) {
186 auto key
= pair
<Cell
*, int>(cell
, step
+1);
187 if (!imported_cells_cache
.count(key
) && !satgen
.importCell(cell
, step
+1)) {
188 if (RTLIL::builtin_ff_cell_types().count(cell
->type
))
189 log_cmd_error("No SAT model available for async FF cell %s (%s). Consider running `async2sync` or `clk2fflogic` first.\n", log_id(cell
), log_id(cell
->type
));
191 log_cmd_error("No SAT model available for cell %s (%s).\n", log_id(cell
), log_id(cell
->type
));
193 imported_cells_cache
.insert(key
);
196 if (satgen
.model_undef
) {
197 for (auto bit
: input_bits
)
198 ez
->assume(ez
->NOT(satgen
.importUndefSigBit(bit
, step
+1)));
202 log(" Problem size at t=%d: %d literals, %d clauses\n", step
, ez
->numCnfVariables(), ez
->numCnfClauses());
204 if (!ez
->solve(ez_context
)) {
205 log(verbose
? " Proved equivalence! Marking $equiv cell as proven.\n" : " success!\n");
206 equiv_cell
->setPort(ID::B
, equiv_cell
->getPort(ID::A
));
207 ez
->assume(ez
->NOT(ez_context
));
212 log(" Failed to prove equivalence with sequence length %d.\n", max_seq
- step
);
216 log(" Reached sequence limit.\n");
220 if (seed_a
.empty() && seed_b
.empty()) {
222 log(" No nets to continue in previous time step.\n");
226 if (seed_a
.empty()) {
228 log(" No nets on A-side to continue in previous time step.\n");
232 if (seed_b
.empty()) {
234 log(" No nets on B-side to continue in previous time step.\n");
240 log(" Continuing analysis in previous time step with the following nets:\n");
241 for (auto bit
: seed_a
)
242 log(" A: %s\n", log_signal(bit
));
243 for (auto bit
: seed_b
)
244 log(" B: %s\n", log_signal(bit
));
246 log(" Continuing analysis in previous time step with %d A- and %d B-nets.\n", GetSize(seed_a
), GetSize(seed_b
));
254 ez
->assume(ez
->NOT(ez_context
));
260 if (GetSize(equiv_cells
) > 1) {
262 for (auto c
: equiv_cells
)
263 sig
.append(sigmap(c
->getPort(ID::Y
)));
264 log(" Grouping SAT models for %s:\n", log_signal(sig
));
268 for (auto c
: equiv_cells
) {
278 struct EquivSimplePass
: public Pass
{
279 EquivSimplePass() : Pass("equiv_simple", "try proving simple $equiv instances") { }
282 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
284 log(" equiv_simple [options] [selection]\n");
286 log("This command tries to prove $equiv cells using a simple direct SAT approach.\n");
289 log(" verbose output\n");
292 log(" enable modelling of undef states\n");
295 log(" create shorter input cones that stop at shared nodes. This yields\n");
296 log(" simpler SAT problems but sometimes fails to prove equivalence.\n");
299 log(" disabling grouping of $equiv cells by output wire\n");
302 log(" the max. number of time steps to be considered (default = 1)\n");
305 void execute(std::vector
<std::string
> args
, Design
*design
) override
307 bool verbose
= false, short_cones
= false, model_undef
= false, nogroup
= false;
308 int success_counter
= 0;
311 log_header(design
, "Executing EQUIV_SIMPLE pass.\n");
314 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
315 if (args
[argidx
] == "-v") {
319 if (args
[argidx
] == "-short") {
323 if (args
[argidx
] == "-undef") {
327 if (args
[argidx
] == "-nogroup") {
331 if (args
[argidx
] == "-seq" && argidx
+1 < args
.size()) {
332 max_seq
= atoi(args
[++argidx
].c_str());
337 extra_args(args
, argidx
, design
);
340 ct
.setup_internals();
343 for (auto module
: design
->selected_modules())
345 SigMap
sigmap(module
);
346 dict
<SigBit
, Cell
*> bit2driver
;
347 dict
<SigBit
, dict
<SigBit
, Cell
*>> unproven_equiv_cells
;
348 int unproven_cells_counter
= 0;
350 for (auto cell
: module
->selected_cells())
351 if (cell
->type
== ID($equiv
) && cell
->getPort(ID::A
) != cell
->getPort(ID::B
)) {
352 auto bit
= sigmap(cell
->getPort(ID::Y
).as_bit());
353 auto bit_group
= bit
;
354 if (!nogroup
&& bit_group
.wire
)
355 bit_group
.offset
= 0;
356 unproven_equiv_cells
[bit_group
][bit
] = cell
;
357 unproven_cells_counter
++;
360 if (unproven_equiv_cells
.empty())
363 log("Found %d unproven $equiv cells (%d groups) in %s:\n",
364 unproven_cells_counter
, GetSize(unproven_equiv_cells
), log_id(module
));
366 for (auto cell
: module
->cells()) {
367 if (!ct
.cell_known(cell
->type
) && !cell
->type
.in(ID($dff
), ID($_DFF_P_
), ID($_DFF_N_
), ID($ff
), ID($_FF_
)))
369 for (auto &conn
: cell
->connections())
370 if (yosys_celltypes
.cell_output(cell
->type
, conn
.first
))
371 for (auto bit
: sigmap(conn
.second
))
372 bit2driver
[bit
] = cell
;
375 unproven_equiv_cells
.sort();
376 for (auto it
: unproven_equiv_cells
)
381 for (auto it2
: it
.second
)
382 cells
.push_back(it2
.second
);
384 EquivSimpleWorker
worker(cells
, sigmap
, bit2driver
, max_seq
, short_cones
, verbose
, model_undef
);
385 success_counter
+= worker
.run();
389 log("Proved %d previously unproven $equiv cells.\n", success_counter
);
393 PRIVATE_NAMESPACE_END