From 8c3f4b395712419f786b2d2bb013d94b7c09986a Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Mon, 25 Nov 2013 04:51:33 +0100 Subject: [PATCH] Started implementing undef handling in satgen --- kernel/satgen.h | 197 +++++++++++++++++++++++++++++++++++++++------ passes/sat/eval.cc | 39 ++++++--- 2 files changed, 202 insertions(+), 34 deletions(-) diff --git a/kernel/satgen.h b/kernel/satgen.h index 3c63f9168..3c19f1740 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 importSigSpec(RTLIL::SigSpec sig, int timestep = -1) + std::vector 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 &vec_a, std::vector &vec_b, RTLIL::Cell *cell, size_t y_width = 0) + std::vector 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 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 &vec_a, std::vector &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 &vec_a, std::vector &vec_b, std::vector &vec_y, RTLIL::Cell *cell) + void extendSignalWidth(std::vector &vec_a, std::vector &vec_b, std::vector &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 &vec_a, std::vector &vec_y, RTLIL::Cell *cell) + void extendSignalWidthUnary(std::vector &vec_a, std::vector &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 undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep); + std::vector undef_b = importUndefSigSpec(cell->connections.at("\\B"), timestep); + std::vector 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 b = importSigSpec(cell->connections.at("\\B"), timestep); + undef_y_bit = ez->OR(undef_y_bit, ez->NOT(ez->expression(ezSAT::OpOr, b))); + } + + std::vector 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 a = importSigSpec(cell->connections.at("\\A"), timestep); std::vector b = importSigSpec(cell->connections.at("\\B"), timestep); std::vector 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 undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep); + std::vector undef_b = importUndefSigSpec(cell->connections.at("\\B"), timestep); + std::vector 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 a0 = ez->vec_and(ez->vec_not(a), ez->vec_not(undef_a)); + std::vector b0 = ez->vec_and(ez->vec_not(b), ez->vec_not(undef_b)); + std::vector 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 a1 = ez->vec_and(a, ez->vec_not(undef_a)); + std::vector b1 = ez->vec_and(b, ez->vec_not(undef_b)); + std::vector 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 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 a = importSigSpec(cell->connections.at("\\A"), timestep); std::vector 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 undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep); + std::vector 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 a = importSigSpec(cell->connections.at("\\A"), timestep); std::vector b = importSigSpec(cell->connections.at("\\B"), timestep); std::vector s = importSigSpec(cell->connections.at("\\S"), timestep); std::vector 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 undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep); + std::vector undef_b = importUndefSigSpec(cell->connections.at("\\B"), timestep); + std::vector undef_s = importUndefSigSpec(cell->connections.at("\\S"), timestep); + std::vector undef_y = importUndefSigSpec(cell->connections.at("\\Y"), timestep); + + std::vector unequal_ab = ez->vec_not(ez->vec_iff(a, b)); + std::vector undef_ab = ez->vec_or(unequal_ab, ez->vec_or(undef_a, undef_b)); + std::vector 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 a = importSigSpec(cell->connections.at("\\A"), timestep); std::vector b = importSigSpec(cell->connections.at("\\B"), timestep); std::vector 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 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 a = importSigSpec(cell->connections.at("\\A"), timestep); std::vector 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 zero(a.size(), ez->FALSE); ez->assume(ez->vec_eq(ez->vec_sub(zero, a), y)); } + + if (model_undef) + { + std::vector undef_a = importUndefSigSpec(cell->connections.at("\\A"), timestep); + std::vector 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 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 a = importSigSpec(cell->connections.at("\\A"), timestep); std::vector 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 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 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 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 a = importSigSpec(cell->connections.at("\\A"), timestep); std::vector 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 a = importSigSpec(cell->connections.at("\\A"), timestep); std::vector b = importSigSpec(cell->connections.at("\\B"), timestep); std::vector 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 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 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 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 473cb41c5..315e5d7c2 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 rec_val_vec = satgen.importSigSpec(recorded_set_vals); ez.assume(ez.vec_eq(rec_var_vec, rec_val_vec)); + std::vector 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 y_vec = satgen.importSigSpec(module->wires.at("\\y")); std::vector y_values; + if (model_undef) { + std::vector 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) -- 2.30.2