From 771c5fe0009cf2195e12be40b242662380681624 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sun, 10 Jul 2016 18:11:25 +0200 Subject: [PATCH] Support for hierarchical designs in smt2 back-end --- backends/smt2/smt2.cc | 148 +++++++++++++++++++++++++++++++++++----- backends/smt2/smtbmc.py | 20 ++++-- 2 files changed, 144 insertions(+), 24 deletions(-) diff --git a/backends/smt2/smt2.cc b/backends/smt2/smt2.cc index e869f78cd..1ff1cdbf5 100644 --- a/backends/smt2/smt2.cc +++ b/backends/smt2/smt2.cc @@ -35,9 +35,9 @@ struct Smt2Worker bool bvmode, memmode, regsmode, wiresmode, verbose; int idcounter; - std::vector decls, trans; + std::vector decls, trans, hier; std::map bit_driver; - std::set exported_cells; + std::set exported_cells, hiercells; pool recursive_cells, registers; std::map> fcache; @@ -465,6 +465,63 @@ struct Smt2Worker return; } + Module *m = module->design->module(cell->type); + + if (m != nullptr) + { + decls.push_back(stringf("; yosys-smt2-cell %s %s\n", log_id(cell->type), log_id(cell->name))); + string cell_state = stringf("(|%s_h %s| state)", log_id(module), log_id(cell->name)); + + for (auto &conn : cell->connections()) + { + Wire *w = m->wire(conn.first); + SigSpec sig = sigmap(conn.second); + + if (w->port_output && !w->port_input) { + if (GetSize(w) > 1) { + if (bvmode) { + decls.push_back(stringf("(declare-fun |%s#%d| (|%s_s|) (_ BitVec %d)) ; %s\n", + log_id(module), idcounter, log_id(module), GetSize(w), log_signal(sig))); + register_bv(sig, idcounter++); + } else { + for (int i = 0; i < GetSize(w); i++) { + decls.push_back(stringf("(declare-fun |%s#%d| (|%s_s|) Bool) ; %s\n", + log_id(module), idcounter, log_id(module), log_signal(sig[i]))); + register_bool(sig[i], idcounter++); + } + } + } else { + decls.push_back(stringf("(declare-fun |%s#%d| (|%s_s|) Bool) ; %s\n", + log_id(module), idcounter, log_id(module), log_signal(sig))); + register_bool(sig, idcounter++); + } + } + } + + decls.push_back(stringf("(declare-fun |%s_h %s| (|%s_s|) |%s_s|)\n", + log_id(module), log_id(cell->name), log_id(module), log_id(cell->type))); + + hiercells.insert(cell); + recursive_cells.erase(cell); + + for (auto &conn : cell->connections()) + { + Wire *w = m->wire(conn.first); + SigSpec sig = sigmap(conn.second); + + if (bvmode || GetSize(w) == 1) { + hier.push_back(stringf(" (= %s (|%s_n %s| %s)) ; %s.%s\n", (GetSize(w) > 1 ? get_bv(sig) : get_bool(sig)).c_str(), + log_id(cell->type), log_id(w), cell_state.c_str(), log_id(cell->type), log_id(w))); + } else { + for (int i = 0; i < GetSize(w); i++) + hier.push_back(stringf(" (= %s (|%s_n %s %d| %s)) ; %s.%s[%d]\n", get_bool(sig[i]).c_str(), + log_id(cell->type), log_id(w), i, cell_state.c_str(), log_id(cell->type), log_id(w), i)); + } + } + + return; + } + log_error("Unsupported cell type %s for cell %s.%s. (Maybe this cell type would be supported in -bv or -mem mode?)\n", log_id(cell->type), log_id(module), log_id(cell)); } @@ -532,7 +589,7 @@ struct Smt2Worker if (verbose) log("=> export logic driving asserts\n"); - vector assert_list, assume_list; + vector assert_list, assume_list; for (auto cell : module->cells()) if (cell->type.in("$assert", "$assume")) { string name_a = get_bool(cell->getPort("\\A")); @@ -540,9 +597,9 @@ struct Smt2Worker decls.push_back(stringf("(define-fun |%s#%d| ((state |%s_s|)) Bool (or %s (not %s))) ; %s\n", log_id(module), idcounter, log_id(module), name_a.c_str(), name_en.c_str(), log_id(cell))); if (cell->type == "$assert") - assert_list.push_back(idcounter++); + assert_list.push_back(stringf("(|%s#%d| state)", log_id(module), idcounter++)); else - assume_list.push_back(idcounter++); + assume_list.push_back(stringf("(|%s#%d| state)", log_id(module), idcounter++)); } for (int iter = 1; !registers.empty(); iter++) @@ -598,20 +655,29 @@ struct Smt2Worker } } + for (auto c : hiercells) + assert_list.push_back(stringf("(|%s_a| (|%s_h %s| state))", log_id(c->type), log_id(module), log_id(c->name))); + + for (auto c : hiercells) + assume_list.push_back(stringf("(|%s_u| (|%s_h %s| state))", log_id(c->type), log_id(module), log_id(c->name))); + + for (auto c : hiercells) + init_list.push_back(stringf("(|%s_i| (|%s_h %s| state))", log_id(c->type), log_id(module), log_id(c->name))); + string assert_expr = assert_list.empty() ? "true" : "(and"; if (!assert_list.empty()) { - for (int i : assert_list) - assert_expr += stringf(" (|%s#%d| state)", log_id(module), i); - assert_expr += ")"; + for (auto &str : assert_list) + assert_expr += stringf("\n %s", str.c_str()); + assert_expr += "\n)"; } decls.push_back(stringf("(define-fun |%s_a| ((state |%s_s|)) Bool %s)\n", log_id(module), log_id(module), assert_expr.c_str())); string assume_expr = assume_list.empty() ? "true" : "(and"; if (!assume_list.empty()) { - for (int i : assume_list) - assume_expr += stringf(" (|%s#%d| state)", log_id(module), i); - assume_expr += ")"; + for (auto &str : assume_list) + assume_expr += stringf("\n %s", str.c_str()); + assume_expr += "\n)"; } decls.push_back(stringf("(define-fun |%s_u| ((state |%s_s|)) Bool %s)\n", log_id(module), log_id(module), assume_expr.c_str())); @@ -619,7 +685,7 @@ struct Smt2Worker string init_expr = init_list.empty() ? "true" : "(and"; if (!init_list.empty()) { for (auto &str : init_list) - init_expr += stringf("\n\t%s", str.c_str()); + init_expr += stringf("\n %s", str.c_str()); init_expr += "\n)"; } decls.push_back(stringf("(define-fun |%s_i| ((state |%s_s|)) Bool %s)\n", @@ -628,10 +694,23 @@ struct Smt2Worker void write(std::ostream &f) { + f << stringf("; yosys-smt2-module %s\n", log_id(module)); + for (auto it : decls) f << it; - f << stringf("; yosys-smt2-module %s\n", log_id(module)); + f << stringf("(define-fun |%s_h| ((state |%s_s|)) Bool ", log_id(module), log_id(module)); + if (GetSize(hier) > 1) { + f << "(and\n"; + for (auto it : hier) + f << it; + f << "))\n"; + } else + if (GetSize(hier) == 1) + f << "\n" + hier.front() + ")\n"; + else + f << "true)\n"; + f << stringf("(define-fun |%s_t| ((state |%s_s|) (next_state |%s_s|)) Bool ", log_id(module), log_id(module), log_id(module)); if (GetSize(trans) > 1) { f << "(and\n"; @@ -661,10 +740,10 @@ struct Smt2Backend : public Backend { log("\n"); log("The '_s' sort represents a module state. Additional '_n' functions\n"); log("are provided that can be used to access the values of the signals in the module.\n"); - log("Only ports, and signals with the 'keep' attribute set are made available via\n"); - log("such functions. Without the -bv option, multi-bit wires are exported as\n"); - log("separate functions of type Bool for the individual bits. With the -bv option\n"); - log("multi-bit wires are exported as single functions of type BitVec.\n"); + log("By default only ports, and signals with the 'keep' attribute set are made\n"); + log("available via such functions. Without the -bv option, multi-bit wires are\n"); + log("exported as separate functions of type Bool for the individual bits. With the\n"); + log("-bv option multi-bit wires are exported as single functions of type BitVec.\n"); log("\n"); log("The '_t' function evaluates to 'true' when the given pair of states\n"); log("describes a valid state transition.\n"); @@ -678,6 +757,10 @@ struct Smt2Backend : public Backend { log("The '_i' function evaluates to 'true' when the given state conforms\n"); log("to the initial state.\n"); log("\n"); + log("For hierarchical designs, the '_h' function must be asserted for each\n"); + log("state to establish the design hierarchy. The '_h ' function\n"); + log("evaluates to the state corresponding to the given cell within .\n"); + log("\n"); log(" -verbose\n"); log(" this will print the recursive walk used to export the modules.\n"); log("\n"); @@ -808,7 +891,36 @@ struct Smt2Backend : public Backend { *f << stringf("; SMT-LIBv2 description generated by %s\n", yosys_version_str); - for (auto module : design->modules()) + std::vector sorted_modules; + + // extract module dependencies + std::map> module_deps; + for (auto &mod_it : design->modules_) { + module_deps[mod_it.second] = std::set(); + for (auto &cell_it : mod_it.second->cells_) + if (design->modules_.count(cell_it.second->type) > 0) + module_deps[mod_it.second].insert(design->modules_.at(cell_it.second->type)); + } + + // simple good-enough topological sort + // (O(n*m) on n elements and depth m) + while (module_deps.size() > 0) { + size_t sorted_modules_idx = sorted_modules.size(); + for (auto &it : module_deps) { + for (auto &dep : it.second) + if (module_deps.count(dep) > 0) + goto not_ready_yet; + // log("Next in topological sort: %s\n", RTLIL::id2cstr(it.first->name)); + sorted_modules.push_back(it.first); + not_ready_yet:; + } + if (sorted_modules_idx == sorted_modules.size()) + log_error("Cyclic dependency between modules found! Cycle includes module %s.\n", RTLIL::id2cstr(module_deps.begin()->first->name)); + while (sorted_modules_idx < sorted_modules.size()) + module_deps.erase(sorted_modules.at(sorted_modules_idx++)); + } + + for (auto module : sorted_modules) { if (module->get_bool_attribute("\\blackbox") || module->has_memories_warn() || module->has_processes_warn()) continue; diff --git a/backends/smt2/smtbmc.py b/backends/smt2/smtbmc.py index f2911b3e7..057776f6d 100644 --- a/backends/smt2/smtbmc.py +++ b/backends/smt2/smtbmc.py @@ -95,32 +95,37 @@ smt = smtio(opts=so) print("%s Solver: %s" % (smt.timestamp(), so.solver)) smt.setup("QF_AUFBV") -debug_nets = set() +debug_nets = dict() debug_nets_re = re.compile(r"^; yosys-smt2-(input|output|register|wire) (\S+) (\d+)") +current_module = None with open(args[0], "r") as f: for line in f: match = debug_nets_re.match(line) if match: - debug_nets.add(match.group(2)) - if line.startswith("; yosys-smt2-module") and topmod is None: - topmod = line.split()[2] + debug_nets[current_module].add(match.group(2)) + if line.startswith("; yosys-smt2-module"): + current_module = line.split()[2] + debug_nets[current_module] = set() smt.write(line) + if topmod is None: + topmod = current_module assert topmod is not None +assert topmod in debug_nets def write_vcd_model(steps): print("%s Writing model to VCD file." % smt.timestamp()) vcd = mkvcd(open(vcdfile, "w")) - for netname in sorted(debug_nets): + for netname in sorted(debug_nets[topmod]): width = len(smt.get_net_bin(topmod, netname, "s0")) vcd.add_net(netname, width) for i in range(steps): vcd.set_time(i) - for netname in debug_nets: + for netname in debug_nets[topmod]: vcd.set_net(netname, smt.get_net_bin(topmod, netname, "s%d" % i)) vcd.set_time(steps) @@ -132,6 +137,7 @@ if tempind: for step in range(num_steps, -1, -1): smt.write("(declare-fun s%d () %s_s)" % (step, topmod)) smt.write("(assert (%s_u s%d))" % (topmod, step)) + smt.write("(assert (%s_h s%d))" % (topmod, step)) if step == num_steps: smt.write("(assert (not (%s_a s%d)))" % (topmod, step)) @@ -170,6 +176,7 @@ else: # not tempind while step < num_steps: smt.write("(declare-fun s%d () %s_s)" % (step, topmod)) smt.write("(assert (%s_u s%d))" % (topmod, step)) + smt.write("(assert (%s_h s%d))" % (topmod, step)) if step == 0: smt.write("(assert (%s_i s0))" % (topmod)) @@ -191,6 +198,7 @@ else: # not tempind if step+i < num_steps: smt.write("(declare-fun s%d () %s_s)" % (step+i, topmod)) smt.write("(assert (%s_u s%d))" % (topmod, step+i)) + smt.write("(assert (%s_h s%d))" % (topmod, step+i)) smt.write("(assert (%s_t s%d s%d))" % (topmod, step+i-1, step+i)) last_check_step = step+i -- 2.30.2