summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--kernel/satgen.h197
-rw-r--r--passes/sat/eval.cc39
2 files changed, 202 insertions, 34 deletions
diff --git a/kernel/satgen.h b/kernel/satgen.h
index 3c63f916..3c19f174 100644
--- a/kernel/satgen.h
+++ b/kernel/satgen.h
@@ -40,9 +40,10 @@ struct SatGen
std::string prefix;
SigPool initial_state;
bool ignore_div_by_zero;
+ bool model_undef;
SatGen(ezSAT *ez, RTLIL::Design *design, SigMap *sigmap, std::string prefix = std::string()) :
- ez(ez), design(design), sigmap(sigmap), prefix(prefix), ignore_div_by_zero(false)
+ ez(ez), design(design), sigmap(sigmap), prefix(prefix), ignore_div_by_zero(false), model_undef(false)
{
}
@@ -53,9 +54,9 @@ struct SatGen
this->prefix = prefix;
}
- std::vector<int> importSigSpec(RTLIL::SigSpec sig, int timestep = -1)
+ std::vector<int> importSigSpecWorker(RTLIL::SigSpec &sig, std::string &pf, bool undef_mode)
{
- assert(timestep < 0 || timestep > 0);
+ assert(!undef_mode || model_undef);
sigmap->apply(sig);
sig.expand();
@@ -64,20 +65,33 @@ struct SatGen
for (auto &c : sig.chunks)
if (c.wire == NULL) {
- vec.push_back(c.data.as_bool() ? ez->TRUE : ez->FALSE);
+ vec.push_back(c.data.bits.at(0) == (undef_mode ? RTLIL::State::Sx : RTLIL::State::S1) ? ez->TRUE : ez->FALSE);
} else {
- std::string name = prefix;
- name += timestep == -1 ? "" : stringf("@%d:", timestep);
- name += stringf(c.wire->width == 1 ? "%s" : "%s [%d]", RTLIL::id2cstr(c.wire->name), c.offset);
+ std::string name = pf + stringf(c.wire->width == 1 ? "%s" : "%s [%d]", RTLIL::id2cstr(c.wire->name), c.offset);
vec.push_back(ez->literal(name));
}
return vec;
}
- void extendSignalWidth(std::vector<int> &vec_a, std::vector<int> &vec_b, RTLIL::Cell *cell, size_t y_width = 0)
+ std::vector<int> importSigSpec(RTLIL::SigSpec sig, int timestep = -1)
+ {
+ assert(timestep != 0);
+ std::string pf = prefix + (timestep == -1 ? "" : stringf("@%d:", timestep));
+ return importSigSpecWorker(sig, pf, false);
+ }
+
+ std::vector<int> importUndefSigSpec(RTLIL::SigSpec sig, int timestep = -1)
+ {
+ assert(timestep != 0);
+ std::string pf = "undef:" + prefix + (timestep == -1 ? "" : stringf("@%d:", timestep));
+ return importSigSpecWorker(sig, pf, true);
+ }
+
+ void extendSignalWidth(std::vector<int> &vec_a, std::vector<int> &vec_b, RTLIL::Cell *cell, size_t y_width = 0, bool undef_mode = false)
{
- bool is_signed = false;
- if (cell->parameters.count("\\A_SIGNED") > 0 && cell->parameters.count("\\B_SIGNED") > 0)
+ assert(!undef_mode || model_undef);
+ bool is_signed = undef_mode;
+ if (!undef_mode && cell->parameters.count("\\A_SIGNED") > 0 && cell->parameters.count("\\B_SIGNED") > 0)
is_signed = cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool();
while (vec_a.size() < vec_b.size() || vec_a.size() < y_width)
vec_a.push_back(is_signed && vec_a.size() > 0 ? vec_a.back() : ez->FALSE);
@@ -85,16 +99,18 @@ struct SatGen
vec_b.push_back(is_signed && vec_b.size() > 0 ? vec_b.back() : ez->FALSE);
}
- void extendSignalWidth(std::vector<int> &vec_a, std::vector<int> &vec_b, std::vector<int> &vec_y, RTLIL::Cell *cell)
+ void extendSignalWidth(std::vector<int> &vec_a, std::vector<int> &vec_b, std::vector<int> &vec_y, RTLIL::Cell *cell, bool undef_mode = false)
{
- extendSignalWidth(vec_a, vec_b, cell, vec_y.size());
+ assert(!undef_mode || model_undef);
+ extendSignalWidth(vec_a, vec_b, cell, vec_y.size(), undef_mode);
while (vec_y.size() < vec_a.size())
vec_y.push_back(ez->literal());
}
- void extendSignalWidthUnary(std::vector<int> &vec_a, std::vector<int> &vec_y, RTLIL::Cell *cell)
+ void extendSignalWidthUnary(std::vector<int> &vec_a, std::vector<int> &vec_y, RTLIL::Cell *cell, bool undef_mode = false)
{
- bool is_signed = cell->parameters.count("\\A_SIGNED") > 0 && cell->parameters["\\A_SIGNED"].as_bool();
+ assert(!undef_mode || model_undef);
+ bool is_signed = undef_mode || (cell->parameters.count("\\A_SIGNED") > 0 && cell->parameters["\\A_SIGNED"].as_bool());
while (vec_a.size() < vec_y.size())
vec_a.push_back(is_signed && vec_a.size() > 0 ? vec_a.back() : ez->FALSE);
while (vec_y.size() < vec_a.size())
@@ -103,9 +119,37 @@ struct SatGen
bool importCell(RTLIL::Cell *cell, int timestep = -1)
{
+ bool arith_undef_handled = false;
+ bool is_compare = cell->type == "$lt" || cell->type == "$le" || cell->type == "$eq" || cell->type == "$ne" || cell->type == "$ge" || cell->type == "$gt";
+
+ if (model_undef && (cell->type == "$add" || cell->type == "$sub" || cell->type == "$mul" || cell->type == "$div" || cell->type == "$mod" || is_compare))
+ {
+ std::vector<int> undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep);
+ std::vector<int> undef_b = importUndefSigSpec(cell->connections.at("\\B"), timestep);
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ if (is_compare)
+ extendSignalWidth(undef_a, undef_b, cell, true);
+ else
+ extendSignalWidth(undef_a, undef_b, undef_y, cell, true);
+
+ int undef_any_a = ez->expression(ezSAT::OpOr, undef_a);
+ int undef_any_b = ez->expression(ezSAT::OpOr, undef_b);
+ int undef_y_bit = ez->OR(undef_any_a, undef_any_b);
+
+ if (cell->type == "$div" || cell->type == "$mod") {
+ std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
+ undef_y_bit = ez->OR(undef_y_bit, ez->NOT(ez->expression(ezSAT::OpOr, b)));
+ }
+
+ std::vector<int> undef_y_bits(undef_y.size(), undef_y_bit);
+ ez->assume(ez->vec_eq(undef_y_bits, undef_y));
+ arith_undef_handled = true;
+ }
+
if (cell->type == "$_AND_" || cell->type == "$_OR_" || cell->type == "$_XOR_" ||
cell->type == "$and" || cell->type == "$or" || cell->type == "$xor" || cell->type == "$xnor" ||
- cell->type == "$add" || cell->type == "$sub") {
+ cell->type == "$add" || cell->type == "$sub")
+ {
std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
@@ -122,27 +166,75 @@ struct SatGen
ez->assume(ez->vec_eq(ez->vec_add(a, b), y));
if (cell->type == "$sub")
ez->assume(ez->vec_eq(ez->vec_sub(a, b), y));
+
+ if (model_undef && !arith_undef_handled)
+ {
+ std::vector<int> undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep);
+ std::vector<int> undef_b = importUndefSigSpec(cell->connections.at("\\B"), timestep);
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ extendSignalWidth(undef_a, undef_b, undef_y, cell, true);
+
+ if (cell->type == "$and" || cell->type == "$_AND_") {
+ std::vector<int> a0 = ez->vec_and(ez->vec_not(a), ez->vec_not(undef_a));
+ std::vector<int> b0 = ez->vec_and(ez->vec_not(b), ez->vec_not(undef_b));
+ std::vector<int> yX = ez->vec_and(ez->vec_or(undef_a, undef_b), ez->vec_not(ez->vec_or(a0, b0)));
+ ez->assume(ez->vec_eq(yX, undef_y));
+ }
+ else if (cell->type == "$or" || cell->type == "$_OR_") {
+ std::vector<int> a1 = ez->vec_and(a, ez->vec_not(undef_a));
+ std::vector<int> b1 = ez->vec_and(b, ez->vec_not(undef_b));
+ std::vector<int> yX = ez->vec_and(ez->vec_or(undef_a, undef_b), ez->vec_not(ez->vec_or(a1, b1)));
+ ez->assume(ez->vec_eq(yX, undef_y));
+ }
+ else /* xor, xnor */ {
+ std::vector<int> yX = ez->vec_or(undef_a, undef_b);
+ ez->assume(ez->vec_eq(yX, undef_y));
+ }
+ }
return true;
}
- if (cell->type == "$_INV_" || cell->type == "$not") {
+ if (cell->type == "$_INV_" || cell->type == "$not")
+ {
std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
extendSignalWidthUnary(a, y, cell);
ez->assume(ez->vec_eq(ez->vec_not(a), y));
+
+ if (model_undef) {
+ std::vector<int> undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep);
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ extendSignalWidthUnary(undef_a, undef_y, cell, true);
+ ez->assume(ez->vec_eq(undef_a, undef_y));
+ }
return true;
}
- if (cell->type == "$_MUX_" || cell->type == "$mux") {
+ if (cell->type == "$_MUX_" || cell->type == "$mux")
+ {
std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
std::vector<int> s = importSigSpec(cell->connections.at("\\S"), timestep);
std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
ez->assume(ez->vec_eq(ez->vec_ite(s.at(0), b, a), y));
+
+ if (model_undef)
+ {
+ std::vector<int> undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep);
+ std::vector<int> undef_b = importUndefSigSpec(cell->connections.at("\\B"), timestep);
+ std::vector<int> undef_s = importUndefSigSpec(cell->connections.at("\\S"), timestep);
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+
+ std::vector<int> unequal_ab = ez->vec_not(ez->vec_iff(a, b));
+ std::vector<int> undef_ab = ez->vec_or(unequal_ab, ez->vec_or(undef_a, undef_b));
+ std::vector<int> yX = ez->vec_ite(undef_s.at(0), undef_ab, ez->vec_ite(s.at(0), undef_b, undef_a));
+ ez->assume(ez->vec_eq(yX, undef_y));
+ }
return true;
}
- if (cell->type == "$pmux" || cell->type == "$safe_pmux") {
+ if (cell->type == "$pmux" || cell->type == "$safe_pmux")
+ {
std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
std::vector<int> s = importSigSpec(cell->connections.at("\\S"), timestep);
@@ -155,24 +247,48 @@ struct SatGen
if (cell->type == "$safe_pmux")
tmp = ez->vec_ite(ez->onehot(s, true), tmp, a);
ez->assume(ez->vec_eq(tmp, y));
+
+ if (model_undef) {
+ log("FIXME: No SAT undef model cell type %s!\n", RTLIL::id2cstr(cell->type));
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ ez->assume(ez->NOT(ez->expression(ezSAT::OpOr, undef_y)));
+ }
return true;
}
- if (cell->type == "$pos" || cell->type == "$neg") {
+ if (cell->type == "$pos" || cell->type == "$neg")
+ {
std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
extendSignalWidthUnary(a, y, cell);
+
if (cell->type == "$pos") {
ez->assume(ez->vec_eq(a, y));
} else {
std::vector<int> zero(a.size(), ez->FALSE);
ez->assume(ez->vec_eq(ez->vec_sub(zero, a), y));
}
+
+ if (model_undef)
+ {
+ std::vector<int> undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep);
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ extendSignalWidthUnary(undef_a, undef_y, cell, true);
+
+ if (cell->type == "$pos") {
+ ez->assume(ez->vec_eq(undef_a, undef_y));
+ } else {
+ log("FIXME: No SAT undef model cell type %s!\n", RTLIL::id2cstr(cell->type));
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ ez->assume(ez->NOT(ez->expression(ezSAT::OpOr, undef_y)));
+ }
+ }
return true;
}
if (cell->type == "$reduce_and" || cell->type == "$reduce_or" || cell->type == "$reduce_xor" ||
- cell->type == "$reduce_xnor" || cell->type == "$reduce_bool" || cell->type == "$logic_not") {
+ cell->type == "$reduce_xnor" || cell->type == "$reduce_bool" || cell->type == "$logic_not")
+ {
std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
if (cell->type == "$reduce_and")
@@ -187,10 +303,17 @@ struct SatGen
ez->SET(ez->NOT(ez->expression(ez->OpOr, a)), y.at(0));
for (size_t i = 1; i < y.size(); i++)
ez->SET(ez->FALSE, y.at(i));
+
+ if (model_undef) {
+ log("FIXME: No SAT undef model cell type %s!\n", RTLIL::id2cstr(cell->type));
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ ez->assume(ez->NOT(ez->expression(ezSAT::OpOr, undef_y)));
+ }
return true;
}
- if (cell->type == "$logic_and" || cell->type == "$logic_or") {
+ if (cell->type == "$logic_and" || cell->type == "$logic_or")
+ {
int a = ez->expression(ez->OpOr, importSigSpec(cell->connections.at("\\A"), timestep));
int b = ez->expression(ez->OpOr, importSigSpec(cell->connections.at("\\B"), timestep));
std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
@@ -200,10 +323,17 @@ struct SatGen
ez->SET(ez->expression(ez->OpOr, a, b), y.at(0));
for (size_t i = 1; i < y.size(); i++)
ez->SET(ez->FALSE, y.at(i));
+
+ if (model_undef) {
+ log("FIXME: No SAT undef model cell type %s!\n", RTLIL::id2cstr(cell->type));
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ ez->assume(ez->NOT(ez->expression(ezSAT::OpOr, undef_y)));
+ }
return true;
}
- if (cell->type == "$lt" || cell->type == "$le" || cell->type == "$eq" || cell->type == "$ne" || cell->type == "$ge" || cell->type == "$gt") {
+ if (cell->type == "$lt" || cell->type == "$le" || cell->type == "$eq" || cell->type == "$ne" || cell->type == "$ge" || cell->type == "$gt")
+ {
bool is_signed = cell->parameters["\\A_SIGNED"].as_bool() && cell->parameters["\\B_SIGNED"].as_bool();
std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
@@ -223,10 +353,12 @@ struct SatGen
ez->SET(is_signed ? ez->vec_gt_signed(a, b) : ez->vec_gt_unsigned(a, b), y.at(0));
for (size_t i = 1; i < y.size(); i++)
ez->SET(ez->FALSE, y.at(i));
+ assert(!model_undef || arith_undef_handled);
return true;
}
- if (cell->type == "$shl" || cell->type == "$shr" || cell->type == "$sshl" || cell->type == "$sshr") {
+ if (cell->type == "$shl" || cell->type == "$shr" || cell->type == "$sshl" || cell->type == "$sshr")
+ {
std::vector<int> a = importSigSpec(cell->connections.at("\\A"), timestep);
std::vector<int> b = importSigSpec(cell->connections.at("\\B"), timestep);
std::vector<int> y = importSigSpec(cell->connections.at("\\Y"), timestep);
@@ -247,6 +379,12 @@ struct SatGen
tmp = ez->vec_ite(b.at(i), tmp_shifted, tmp);
}
ez->assume(ez->vec_eq(tmp, y));
+
+ if (model_undef) {
+ log("FIXME: No SAT undef model cell type %s!\n", RTLIL::id2cstr(cell->type));
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ ez->assume(ez->NOT(ez->expression(ezSAT::OpOr, undef_y)));
+ }
return true;
}
@@ -264,6 +402,7 @@ struct SatGen
tmp = ez->vec_ite(b.at(i), ez->vec_add(tmp, shifted_a), tmp);
}
ez->assume(ez->vec_eq(tmp, y));
+ assert(!model_undef || arith_undef_handled);
return true;
}
@@ -337,10 +476,12 @@ struct SatGen
ez->assume(ez->vec_eq(y, ez->vec_ite(ez->expression(ezSAT::OpOr, b), y_tmp, div_zero_result)));
}
+ assert(!model_undef || arith_undef_handled);
return true;
}
- if (timestep > 0 && (cell->type == "$dff" || cell->type == "$_DFF_N_" || cell->type == "$_DFF_P_")) {
+ if (timestep > 0 && (cell->type == "$dff" || cell->type == "$_DFF_N_" || cell->type == "$_DFF_P_"))
+ {
if (timestep == 1) {
initial_state.add((*sigmap)(cell->connections.at("\\Q")));
} else {
@@ -348,10 +489,16 @@ struct SatGen
std::vector<int> q = importSigSpec(cell->connections.at("\\Q"), timestep);
ez->assume(ez->vec_eq(d, q));
}
+
+ if (model_undef) {
+ log("FIXME: No SAT undef model cell type %s!\n", RTLIL::id2cstr(cell->type));
+ std::vector<int> undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep);
+ ez->assume(ez->NOT(ez->expression(ezSAT::OpOr, undef_y)));
+ }
return true;
}
- // Unsupported internal cell types: $div $mod $pow
+ // Unsupported internal cell types: $pow $lut
// .. and all sequential cells except $dff and $_DFF_[NP]_
return false;
}
diff --git a/passes/sat/eval.cc b/passes/sat/eval.cc
index 473cb41c..315e5d7c 100644
--- a/passes/sat/eval.cc
+++ b/passes/sat/eval.cc
@@ -142,13 +142,14 @@ struct VlogHammerReporter
return list;
}
- void sat_check(RTLIL::Module *module, RTLIL::SigSpec recorded_set_vars, RTLIL::Const recorded_set_vals, RTLIL::SigSpec expected_y)
+ void sat_check(RTLIL::Module *module, RTLIL::SigSpec recorded_set_vars, RTLIL::Const recorded_set_vals, RTLIL::SigSpec expected_y, bool model_undef)
{
- log("Verifying SAT model..\n");
+ log("Verifying SAT model (%s)..\n", model_undef ? "with undef" : "without undef");
ezDefaultSAT ez;
SigMap sigmap(module);
SatGen satgen(&ez, design, &sigmap);
+ satgen.model_undef = model_undef;
for (auto &c : module->cells)
if (!satgen.importCell(c.second))
@@ -158,9 +159,21 @@ struct VlogHammerReporter
std::vector<int> rec_val_vec = satgen.importSigSpec(recorded_set_vals);
ez.assume(ez.vec_eq(rec_var_vec, rec_val_vec));
+ std::vector<int> rec_undef_var_vec, rec_undef_val_vec;
+ if (model_undef) {
+ rec_undef_var_vec = satgen.importUndefSigSpec(recorded_set_vars);
+ rec_undef_val_vec = satgen.importUndefSigSpec(recorded_set_vals);
+ ez.assume(ez.vec_eq(rec_undef_var_vec, rec_undef_val_vec));
+ }
+
std::vector<int> y_vec = satgen.importSigSpec(module->wires.at("\\y"));
std::vector<bool> y_values;
+ if (model_undef) {
+ std::vector<int> y_undef_vec = satgen.importUndefSigSpec(module->wires.at("\\y"));
+ y_vec.insert(y_vec.end(), y_undef_vec.begin(), y_undef_vec.end());
+ }
+
log(" Created SAT problem with %d variables and %d clauses.\n",
ez.numCnfVariables(), ez.numCnfClauses());
@@ -168,12 +181,19 @@ struct VlogHammerReporter
log_error("Failed to find solution to SAT problem.\n");
expected_y.expand();
- assert(expected_y.chunks.size() == y_vec.size());
- for (size_t i = 0; i < y_vec.size(); i++) {
- RTLIL::State bit = expected_y.chunks.at(i).data.bits.at(0);
- if ((bit == RTLIL::State::S0 || bit == RTLIL::State::S1) && ((bit == RTLIL::State::S1) != y_values.at(i)))
- log_error("Found error in SAT model: y[%d] = %d, should be %d.\n",
- int(i), int(y_values.at(i)), int(bit == RTLIL::State::S1));
+ for (int i = 0; i < expected_y.width; i++) {
+ RTLIL::State solution_bit = y_values.at(i) ? RTLIL::State::S1 : RTLIL::State::S0;
+ RTLIL::State expected_bit = expected_y.chunks.at(i).data.bits.at(0);
+ if (model_undef) {
+ if (y_values.at(expected_y.width+i))
+ solution_bit = RTLIL::State::Sx;
+ } else {
+ if (expected_bit == RTLIL::State::Sx)
+ continue;
+ }
+ if (solution_bit != expected_bit)
+ log_error("Found error in SAT model: y[%d] = %s, should be %s.\n",
+ int(i), log_signal(solution_bit), log_signal(expected_bit));
}
log(" SAT model verified.\n");
@@ -230,7 +250,8 @@ struct VlogHammerReporter
if (module_name == "rtl") {
rtl_sig = sig;
rtl_sig.expand();
- sat_check(module, recorded_set_vars, recorded_set_vals, sig);
+ sat_check(module, recorded_set_vars, recorded_set_vals, sig, false);
+ // sat_check(module, recorded_set_vars, recorded_set_vals, sig, true);
} else if (rtl_sig.width > 0) {
sig.expand();
if (rtl_sig.width != sig.width)
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-20 04:20:43 +0000