diff options
Diffstat (limited to 'backends/smt2/smtbmc.py')
| -rw-r--r-- | backends/smt2/smtbmc.py | 136 |
1 files changed, 128 insertions, 8 deletions
diff --git a/backends/smt2/smtbmc.py b/backends/smt2/smtbmc.py index 10875f523..d8b47504c 100644 --- a/backends/smt2/smtbmc.py +++ b/backends/smt2/smtbmc.py @@ -36,6 +36,7 @@ vlogtbfile = None inconstr = list() outconstr = None gentrace = False +covermode = False tempind = False dumpall = False assume_skipped = None @@ -61,6 +62,9 @@ yosys-smtbmc [options] <yosys_smt2_output> -i instead of BMC run temporal induction + -c + instead of regular BMC run cover analysis + -m <module_name> name of the top module @@ -120,7 +124,7 @@ yosys-smtbmc [options] <yosys_smt2_output> try: - opts, args = getopt.getopt(sys.argv[1:], so.shortopts + "t:igm:", so.longopts + + opts, args = getopt.getopt(sys.argv[1:], so.shortopts + "t:igcm:", so.longopts + ["final-only", "assume-skipped=", "smtc=", "cex=", "aig=", "aig-noheader", "dump-vcd=", "dump-vlogtb=", "dump-smtc=", "dump-all", "noinfo", "append="]) except: @@ -173,6 +177,8 @@ for o, a in opts: tempind = True elif o == "-g": gentrace = True + elif o == "-c": + covermode = True elif o == "-m": topmod = a elif so.handle(o, a): @@ -183,6 +189,8 @@ for o, a in opts: if len(args) != 1: usage() +if sum([tempind, gentrace, covermode]) > 1: + usage() constr_final_start = None constr_asserts = defaultdict(list) @@ -705,30 +713,40 @@ def write_trace(steps_start, steps_stop, index): write_constr_trace(steps_start, steps_stop, index) -def print_failed_asserts_worker(mod, state, path): +def print_failed_asserts_worker(mod, state, path, extrainfo): assert mod in smt.modinfo + found_failed_assert = False if smt.get("(|%s_a| %s)" % (mod, state)) in ["true", "#b1"]: return for cellname, celltype in smt.modinfo[mod].cells.items(): - print_failed_asserts_worker(celltype, "(|%s_h %s| %s)" % (mod, cellname, state), path + "." + cellname) + if print_failed_asserts_worker(celltype, "(|%s_h %s| %s)" % (mod, cellname, state), path + "." + cellname, extrainfo): + found_failed_assert = True for assertfun, assertinfo in smt.modinfo[mod].asserts.items(): if smt.get("(|%s| %s)" % (assertfun, state)) in ["false", "#b0"]: - print_msg("Assert failed in %s: %s" % (path, assertinfo)) + print_msg("Assert failed in %s: %s%s" % (path, assertinfo, extrainfo)) + found_failed_assert = True + return found_failed_assert -def print_failed_asserts(state, final=False): + +def print_failed_asserts(state, final=False, extrainfo=""): if noinfo: return loc_list, expr_list, value_list = get_constr_expr(constr_asserts, state, final=final, getvalues=True) + found_failed_assert = False for loc, expr, value in zip(loc_list, expr_list, value_list): if smt.bv2int(value) == 0: - print_msg("Assert %s failed: %s" % (loc, expr)) + print_msg("Assert %s failed: %s%s" % (loc, expr, extrainfo)) + found_failed_assert = True if not final: - print_failed_asserts_worker(topmod, "s%d" % state, topmod) + if print_failed_asserts_worker(topmod, "s%d" % state, topmod, extrainfo): + found_failed_assert = True + + return found_failed_assert def print_anyconsts_worker(mod, state, path): @@ -746,6 +764,24 @@ def print_anyconsts(state): print_anyconsts_worker(topmod, "s%d" % state, topmod) +def get_cover_list(mod, base): + assert mod in smt.modinfo + + cover_expr = list() + cover_desc = list() + + for expr, desc in smt.modinfo[mod].covers.items(): + cover_expr.append("(ite (|%s| %s) #b1 #b0)" % (expr, base)) + cover_desc.append(desc) + + for cell, submod in smt.modinfo[mod].cells.items(): + e, d = get_cover_list(submod, "(|%s_h %s| %s)" % (mod, cell, base)) + cover_expr += e + cover_desc += d + + return cover_expr, cover_desc + + if tempind: retstatus = False skip_counter = step_size @@ -793,8 +829,92 @@ if tempind: retstatus = True break +elif covermode: + cover_expr, cover_desc = get_cover_list(topmod, "state") + cover_mask = "1" * len(cover_desc) + + if len(cover_expr) > 1: + cover_expr = "(concat %s)" % " ".join(cover_expr) + elif len(cover_expr) == 1: + cover_expr = cover_expr[0] + else: + cover_expr = "#b0" + + coveridx = 0 + smt.write("(define-fun covers_0 ((state |%s_s|)) (_ BitVec %d) %s)" % (topmod, len(cover_desc), cover_expr)) + + step = 0 + retstatus = False + found_failed_assert = False + + assert step_size == 1 + + 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)) + smt.write("(assert %s)" % get_constr_expr(constr_assumes, step)) + + if step == 0: + smt.write("(assert (|%s_i| s0))" % (topmod)) + smt.write("(assert (|%s_is| s0))" % (topmod)) + + else: + smt.write("(assert (|%s_t| s%d s%d))" % (topmod, step-1, step)) + smt.write("(assert (not (|%s_is| s%d)))" % (topmod, step)) + + while "1" in cover_mask: + print_msg("Checking cover reachability in step %d.." % (step)) + smt.write("(push 1)") + smt.write("(assert (distinct (covers_%d s%d) #b%s))" % (coveridx, step, "0" * len(cover_desc))) + + if smt.check_sat() == "unsat": + smt.write("(pop 1)") + break + + reached_covers = smt.bv2bin(smt.get("(covers_%d s%d)" % (coveridx, step))) + assert len(reached_covers) == len(cover_desc) + + new_cover_mask = [] + + for i in range(len(reached_covers)): + if reached_covers[i] == "0": + new_cover_mask.append(cover_mask[i]) + continue + + print_msg("Reached cover statement at %s in step %d." % (cover_desc[i], step)) + new_cover_mask.append("0") + + cover_mask = "".join(new_cover_mask) + + for i in range(step+1): + if print_failed_asserts(i, extrainfo=" (step %d)" % i): + found_failed_assert = True + + write_trace(0, step+1, "%d" % coveridx) + + if found_failed_assert: + break + + coveridx += 1 + smt.write("(pop 1)") + smt.write("(define-fun covers_%d ((state |%s_s|)) (_ BitVec %d) (bvand (covers_%d state) #b%s))" % (coveridx, topmod, len(cover_desc), coveridx-1, cover_mask)) + + if found_failed_assert: + break + + if "1" not in cover_mask: + retstatus = True + break + + step += 1 + + if "1" in cover_mask: + for i in range(len(cover_mask)): + if cover_mask[i] == "1": + print_msg("Unreached cover statement at %s." % cover_desc[i]) -else: # not tempind +else: # not tempind, covermode step = 0 retstatus = True while step < num_steps: |