From 1434312fdd1290ac21eb57c79c1999e775cdba54 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sat, 8 Jun 2013 14:11:50 +0200 Subject: [PATCH] Various improvements in sat_solve pass and SAT generator --- kernel/satgen.h | 112 +++++++++++++++++++++++++++++----------- passes/sat/example.v | 62 +++++++++++++++++++++- passes/sat/example.ys | 6 ++- passes/sat/sat_solve.cc | 16 +++--- 4 files changed, 155 insertions(+), 41 deletions(-) diff --git a/kernel/satgen.h b/kernel/satgen.h index 7535c7532..90e69ad29 100644 --- a/kernel/satgen.h +++ b/kernel/satgen.h @@ -73,29 +73,6 @@ struct SatGen return vec; } - // ** cell types to be done: ** - // cell_types.insert("$pos"); - // cell_types.insert("$neg"); - // cell_types.insert("$xnor"); - // cell_types.insert("$reduce_and"); - // cell_types.insert("$reduce_or"); - // cell_types.insert("$reduce_xor"); - // cell_types.insert("$reduce_xnor"); - // cell_types.insert("$reduce_bool"); - // cell_types.insert("$shl"); - // cell_types.insert("$shr"); - // cell_types.insert("$sshl"); - // cell_types.insert("$sshr"); - // cell_types.insert("$mul"); - // cell_types.insert("$div"); - // cell_types.insert("$mod"); - // cell_types.insert("$pow"); - // cell_types.insert("$logic_not"); - // cell_types.insert("$logic_and"); - // cell_types.insert("$logic_or"); - // cell_types.insert("$pmux"); - // cell_types.insert("$safe_pmux"); - void extendSignalWidth(std::vector &vec_a, std::vector &vec_b, RTLIL::Cell *cell) { bool is_signed_a = false, is_signed_b = false; @@ -116,10 +93,10 @@ struct SatGen vec_y.push_back(ez->literal()); } - virtual void importCell(RTLIL::Cell *cell) + virtual bool importCell(RTLIL::Cell *cell) { if (cell->type == "$_AND_" || cell->type == "$_OR_" || cell->type == "$_XOR_" || - 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") { std::vector a = importSigSpec(cell->connections.at("\\A")); std::vector b = importSigSpec(cell->connections.at("\\B")); @@ -131,23 +108,91 @@ struct SatGen ez->assume(ez->vec_eq(ez->vec_or(a, b), y)); if (cell->type == "$xor" || cell->type == "$_XOR") ez->assume(ez->vec_eq(ez->vec_xor(a, b), y)); + if (cell->type == "$xnor") + ez->assume(ez->vec_eq(ez->vec_not(ez->vec_xor(a, b)), y)); if (cell->type == "$add") 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)); - } else + return true; + } + if (cell->type == "$_INV_" || cell->type == "$not") { std::vector a = importSigSpec(cell->connections.at("\\A")); std::vector y = importSigSpec(cell->connections.at("\\Y")); ez->assume(ez->vec_eq(ez->vec_not(a), y)); - } else + return true; + } + if (cell->type == "$_MUX_" || cell->type == "$mux") { std::vector a = importSigSpec(cell->connections.at("\\A")); std::vector b = importSigSpec(cell->connections.at("\\B")); std::vector s = importSigSpec(cell->connections.at("\\S")); std::vector y = importSigSpec(cell->connections.at("\\Y")); - ez->assume(ez->vec_eq(ez->vec_ite(s, b, a), y)); - } else + ez->assume(ez->vec_eq(ez->vec_ite(s.at(0), b, a), y)); + return true; + } + + if (cell->type == "$pmux" || cell->type == "$safe_pmux") { + std::vector a = importSigSpec(cell->connections.at("\\A")); + std::vector b = importSigSpec(cell->connections.at("\\B")); + std::vector s = importSigSpec(cell->connections.at("\\S")); + std::vector y = importSigSpec(cell->connections.at("\\Y")); + std::vector tmp = a; + for (size_t i = 0; i < s.size(); i++) { + std::vector part_of_b(b.begin()+i*a.size(), b.begin()+(i+1)*a.size()); + tmp = ez->vec_ite(s.at(i), part_of_b, tmp); + } + if (cell->type == "$safe_pmux") + tmp = ez->vec_ite(ez->onehot(s, true), tmp, a); + ez->assume(ez->vec_eq(tmp, y)); + return true; + } + + if (cell->type == "$pos" || cell->type == "$neg") { + std::vector a = importSigSpec(cell->connections.at("\\A")); + std::vector y = importSigSpec(cell->connections.at("\\Y")); + 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)); + } + 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") { + std::vector a = importSigSpec(cell->connections.at("\\A")); + std::vector y = importSigSpec(cell->connections.at("\\Y")); + if (cell->type == "$reduce_and") + ez->SET(ez->expression(ez->OpAnd, a), y.at(0)); + if (cell->type == "$reduce_or" || cell->type == "$reduce_bool") + ez->SET(ez->expression(ez->OpOr, a), y.at(0)); + if (cell->type == "$reduce_xor") + ez->SET(ez->expression(ez->OpXor, a), y.at(0)); + if (cell->type == "$reduce_xnor") + ez->SET(ez->NOT(ez->expression(ez->OpXor, a)), y.at(0)); + if (cell->type == "$logic_not") + ez->SET(ez->NOT(ez->expression(ez->OpOr, a)), y.at(0)); + for (size_t i = 1; i < y.size(); i++) + ez->SET(0, y.at(0)); + return true; + } + + if (cell->type == "$logic_and" || cell->type == "$logic_or") { + int a = ez->expression(ez->OpOr, importSigSpec(cell->connections.at("\\A"))); + int b = ez->expression(ez->OpOr, importSigSpec(cell->connections.at("\\B"))); + std::vector y = importSigSpec(cell->connections.at("\\Y")); + if (cell->type == "$logic_and") + ez->SET(ez->expression(ez->OpAnd, a, b), y.at(0)); + else + ez->SET(ez->expression(ez->OpOr, a, b), y.at(0)); + for (size_t i = 1; i < y.size(); i++) + ez->SET(0, y.at(0)); + return true; + } + 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")); @@ -166,8 +211,13 @@ struct SatGen ez->SET(is_signed ? ez->vec_ge_signed(a, b) : ez->vec_ge_unsigned(a, b), y.at(0)); if (cell->type == "$gt") ez->SET(is_signed ? ez->vec_gt_signed(a, b) : ez->vec_gt_unsigned(a, b), y.at(0)); - } else - log_error("Can't handle cell type %s in SAT generator yet.\n", RTLIL::id2cstr(cell->type)); + for (size_t i = 1; i < y.size(); i++) + ez->SET(0, y.at(0)); + return true; + } + + // Unsupported internal cell types: $shl $shr $sshl $sshr $mul $div $mod $pow + return false; } }; diff --git a/passes/sat/example.v b/passes/sat/example.v index 45011f70d..9e8c94b73 100644 --- a/passes/sat/example.v +++ b/passes/sat/example.v @@ -1,5 +1,5 @@ -module example(a, y); +module example001(a, y); input [15:0] a; output y; @@ -10,3 +10,63 @@ assign y = !gt && !lt; endmodule +// ------------------------------------ + +module example002(a, y); + +input [3:0] a; +output y; +reg [1:0] t1, t2; + +always @* begin + casex (a) + 16'b1xxx: + t1 <= 1; + 16'bx1xx: + t1 <= 2; + 16'bxx1x: + t1 <= 3; + 16'bxxx1: + t1 <= 4; + default: + t1 <= 0; + endcase + casex (a) + 16'b1xxx: + t2 <= 1; + 16'b01xx: + t2 <= 2; + 16'b001x: + t2 <= 3; + 16'b0001: + t2 <= 4; + default: + t2 <= 0; + endcase +end + +assign y = t1 != t2; + +endmodule + +// ------------------------------------ + +module example003(clk, rst, y); + +input clk, rst; +output y; + +reg [3:0] counter; + +always @(posedge clk) + case (1) + rst, counter == 9: + counter <= 0; + default: + counter <= counter+1; + endcase + +assign y = counter == 12; + +endmodule + diff --git a/passes/sat/example.ys b/passes/sat/example.ys index b6d131c91..d4037f781 100644 --- a/passes/sat/example.ys +++ b/passes/sat/example.ys @@ -1,3 +1,5 @@ read_verilog example.v -techmap; opt; abc; opt -sat_solve -set y 1'b1 +proc; opt_clean +sat_solve -set y 1'b1 example001 +sat_solve -set y 1'b1 example002 +sat_solve -set y 1'b1 example003 diff --git a/passes/sat/sat_solve.cc b/passes/sat/sat_solve.cc index a7605b443..b71d0507a 100644 --- a/passes/sat/sat_solve.cc +++ b/passes/sat/sat_solve.cc @@ -211,14 +211,16 @@ struct SatSolvePass : public Pass { int import_cell_counter = 0; for (auto &c : module->cells) if (design->selected(module, c.second) && ct.cell_known(c.second->type)) { - for (auto &p : c.second->connections) - if (ct.cell_output(c.second->type, p.first)) - show_drivers.insert(sigmap(p.second), c.second); - else - show_driven[c.second].append(sigmap(p.second)); // log("Import cell: %s\n", RTLIL::id2cstr(c.first)); - satgen.importCell(c.second); - import_cell_counter++; + if (satgen.importCell(c.second)) { + for (auto &p : c.second->connections) + if (ct.cell_output(c.second->type, p.first)) + show_drivers.insert(sigmap(p.second), c.second); + else + show_driven[c.second].append(sigmap(p.second)); + import_cell_counter++; + } else + log("Warning: failed to import cell %s (type %s) to SAT database.\n", RTLIL::id2cstr(c.first), RTLIL::id2cstr(c.second->type)); } log("Imported %d cells to SAT database.\n", import_cell_counter); -- 2.30.2