sbysrc/sby_engine_smtbmc.py

   1 #
   2 # SymbiYosys (sby) -- Front-end for Yosys-based formal verification flows
   3 #
   4 # Copyright (C) 2016  Claire Xenia Wolf <claire@yosyshq.com>
   5 #
   6 # Permission to use, copy, modify, and/or distribute this software for any
   7 # purpose with or without fee is hereby granted, provided that the above
   8 # copyright notice and this permission notice appear in all copies.
   9 #
  10 # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11 # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12 # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13 # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15 # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16 # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17 #
  18
  19 import re, os, getopt
  20 from sby_core import SbyProc
  21
  22 def run(mode, task, engine_idx, engine):
  23     smtbmc_opts = []
  24     nomem_opt = False
  25     presat_opt = True
  26     unroll_opt = None
  27     syn_opt = False
  28     stbv_opt = False
  29     stdt_opt = False
  30     dumpsmt2 = False
  31     progress = False
  32     basecase_only = False
  33     induction_only = False
  34     keep_going = False
  35     random_seed = None
  36     task.precise_prop_status = True
  37
  38     opts, args = getopt.getopt(engine[1:], "", ["nomem", "syn", "stbv", "stdt", "presat",
  39             "nopresat", "unroll", "nounroll", "dumpsmt2", "progress", "basecase", "induction", "keep-going", "seed="])
  40
  41     for o, a in opts:
  42         if o == "--nomem":
  43             nomem_opt = True
  44         elif o == "--syn":
  45             syn_opt = True
  46         elif o == "--stbv":
  47             stbv_opt = True
  48         elif o == "--stdt":
  49             stdt_opt = True
  50         elif o == "--presat":
  51             presat_opt = True
  52         elif o == "--nopresat":
  53             presat_opt = False
  54         elif o == "--unroll":
  55             unroll_opt = True
  56         elif o == "--nounroll":
  57             unroll_opt = False
  58         elif o == "--dumpsmt2":
  59             dumpsmt2 = True
  60         elif o == "--progress":
  61             progress = True
  62         elif o == "--basecase":
  63             if induction_only:
  64                 task.error("smtbmc options --basecase and --induction are exclusive.")
  65             basecase_only = True
  66         elif o == "--induction":
  67             if basecase_only:
  68                 task.error("smtbmc options --basecase and --induction are exclusive.")
  69             induction_only = True
  70         elif o == "--keep-going":
  71             if mode not in ("bmc", "prove", "prove_basecase", "prove_induction"):
  72                 task.error("smtbmc option --keep-going is only supported in bmc and prove mode.")
  73             keep_going = True
  74         elif o == "--seed":
  75             random_seed = a
  76         else:
  77             task.error(f"Invalid smtbmc options {o}.")
  78
  79     xtra_opts = False
  80     for i, a in enumerate(args):
  81         if i == 0 and a == "z3" and unroll_opt is None:
  82                 unroll_opt = False
  83         if a == "--":
  84             xtra_opts = True
  85             continue
  86         if xtra_opts:
  87             smtbmc_opts.append(a)
  88         else:
  89             smtbmc_opts += ["-s" if i == 0 else "-S", a]
  90
  91     if presat_opt:
  92         smtbmc_opts += ["--presat"]
  93
  94     if unroll_opt is None or unroll_opt:
  95         smtbmc_opts += ["--unroll"]
  96
  97     if task.opt_smtc is not None:
  98         smtbmc_opts += ["--smtc", f"src/{task.opt_smtc}"]
  99
 100     if task.opt_tbtop is not None:
 101          smtbmc_opts += ["--vlogtb-top", task.opt_tbtop]
 102
 103     model_name = "smt2"
 104     if syn_opt: model_name += "_syn"
 105     if nomem_opt: model_name += "_nomem"
 106     if stbv_opt: model_name += "_stbv"
 107     if stdt_opt: model_name += "_stdt"
 108
 109     if mode == "prove":
 110         if not induction_only:
 111             run("prove_basecase", task, engine_idx, engine)
 112         if not basecase_only:
 113             run("prove_induction", task, engine_idx, engine)
 114         return
 115
 116     procname = f"engine_{engine_idx}"
 117     trace_prefix = f"engine_{engine_idx}/trace"
 118     logfile_prefix = f"{task.workdir}/engine_{engine_idx}/logfile"
 119
 120     if mode == "prove_basecase":
 121         procname += ".basecase"
 122         logfile_prefix += "_basecase"
 123
 124     if mode == "prove_induction":
 125         procname += ".induction"
 126         trace_prefix += "_induct"
 127         logfile_prefix += "_induction"
 128         smtbmc_opts.append("-i")
 129
 130     if mode == "cover":
 131         smtbmc_opts.append("-c")
 132         trace_prefix += "%"
 133
 134     if keep_going:
 135         smtbmc_opts.append("--keep-going")
 136         trace_prefix += "%"
 137
 138     if dumpsmt2:
 139         smtbmc_opts += ["--dump-smt2", trace_prefix.replace("%", "") + ".smt2"]
 140
 141     if not progress:
 142         smtbmc_opts.append("--noprogress")
 143
 144
 145     if task.opt_skip is not None:
 146         t_opt = "{}:{}".format(task.opt_skip, task.opt_depth)
 147     else:
 148         t_opt = "{}".format(task.opt_depth)
 149
 150     random_seed = f"--info \"(set-option :random-seed {random_seed})\"" if random_seed else ""
 151     proc = SbyProc(
 152         task,
 153         procname,
 154         task.model(model_name),
 155         f"""cd {task.workdir}; {task.exe_paths["smtbmc"]} {" ".join(smtbmc_opts)} -t {t_opt} {random_seed} --append {task.opt_append} --dump-vcd {trace_prefix}.vcd --dump-vlogtb {trace_prefix}_tb.v --dump-smtc {trace_prefix}.smtc model/design_{model_name}.smt2""",
 156         logfile=open(logfile_prefix + ".txt", "w"),
 157         logstderr=(not progress)
 158     )
 159
 160     if mode == "prove_basecase":
 161         task.basecase_procs.append(proc)
 162
 163     if mode == "prove_induction":
 164         task.induction_procs.append(proc)
 165
 166     proc_status = None
 167     last_prop = []
 168
 169     def output_callback(line):
 170         nonlocal proc_status
 171         nonlocal last_prop
 172         smt2_trans = {'\\':'/', '|':'/'}
 173
 174         match = re.match(r"^## [0-9: ]+ Status: FAILED", line)
 175         if match:
 176             proc_status = "FAIL"
 177             return line.replace("FAILED", "failed")
 178
 179         match = re.match(r"^## [0-9: ]+ Status: PASSED", line)
 180         if match:
 181             proc_status = "PASS"
 182             return line.replace("PASSED", "passed")
 183
 184         match = re.match(r"^## [0-9: ]+ Status: PREUNSAT", line)
 185         if match:
 186             proc_status = "ERROR"
 187             return line
 188
 189         match = re.match(r"^## [0-9: ]+ Unexpected response from solver:", line)
 190         if match:
 191             proc_status = "ERROR"
 192             return line
 193
 194         match = re.match(r"^## [0-9: ]+ Assert failed in (\S+): (\S+) \((\S+)\)", line)
 195         if match:
 196             cell_name = match[3]
 197             prop = task.design_hierarchy.find_property_by_cellname(cell_name, trans_dict=smt2_trans)
 198             prop.status = "FAIL"
 199             last_prop.append(prop)
 200             return line
 201
 202         match = re.match(r"^## [0-9: ]+ Reached cover statement at (\S+) \((\S+)\) in step \d+.", line)
 203         if match:
 204             cell_name = match[2]
 205             prop = task.design_hierarchy.find_property_by_cellname(cell_name, trans_dict=smt2_trans)
 206             prop.status = "PASS"
 207             last_prop.append(prop)
 208             return line
 209
 210         match = re.match(r"^## [0-9: ]+ Writing trace to VCD file: (\S+)", line)
 211         if match and last_prop:
 212             for p in last_prop:
 213                 if not p.tracefile:
 214                     p.tracefile = match[1]
 215             last_prop = []
 216             return line
 217
 218         match = re.match(r"^## [0-9: ]+ Unreached cover statement at (\S+) \((\S+)\).", line)
 219         if match:
 220             cell_name = match[2]
 221             prop = task.design_hierarchy.find_property_by_cellname(cell_name, trans_dict=smt2_trans)
 222             prop.status = "FAIL"
 223
 224         return line
 225
 226     def exit_callback(retcode):
 227         if proc_status is None:
 228             task.error(f"engine_{engine_idx}: Engine terminated without status.")
 229
 230         if mode == "bmc" or mode == "cover":
 231             task.update_status(proc_status)
 232             proc_status_lower = proc_status.lower() if proc_status == "PASS" else proc_status
 233             task.log(f"engine_{engine_idx}: Status returned by engine: {proc_status_lower}")
 234             task.summary.append(f"""engine_{engine_idx} ({" ".join(engine)}) returned {proc_status_lower}""")
 235
 236             if proc_status == "FAIL" and mode != "cover":
 237                 if os.path.exists(f"{task.workdir}/engine_{engine_idx}/trace.vcd"):
 238                     task.summary.append(f"counterexample trace: {task.workdir}/engine_{engine_idx}/trace.vcd")
 239             elif proc_status == "PASS" and mode == "cover":
 240                 print_traces_max = 5
 241                 for i in range(print_traces_max):
 242                     if os.path.exists(f"{task.workdir}/engine_{engine_idx}/trace{i}.vcd"):
 243                         task.summary.append(f"trace: {task.workdir}/engine_{engine_idx}/trace{i}.vcd")
 244                     else:
 245                         break
 246                 else:
 247                     excess_traces = 0
 248                     while os.path.exists(f"{task.workdir}/engine_{engine_idx}/trace{print_traces_max + excess_traces}.vcd"):
 249                         excess_traces += 1
 250                     if excess_traces > 0:
 251                         task.summary.append(f"""and {excess_traces} further trace{"s" if excess_traces > 1 else ""}""")
 252             elif proc_status == "PASS" and mode == "bmc":
 253                 for prop in task.design_hierarchy:
 254                     if prop.type == prop.Type.ASSERT and prop.status == "UNKNOWN":
 255                         prop.status = "PASS"
 256
 257             task.terminate()
 258
 259         elif mode in ["prove_basecase", "prove_induction"]:
 260             proc_status_lower = proc_status.lower() if proc_status == "PASS" else proc_status
 261             task.log(f"""engine_{engine_idx}: Status returned by engine for {mode.split("_")[1]}: {proc_status_lower}""")
 262             task.summary.append(f"""engine_{engine_idx} ({" ".join(engine)}) returned {proc_status_lower} for {mode.split("_")[1]}""")
 263
 264             if mode == "prove_basecase":
 265                 for proc in task.basecase_procs:
 266                     proc.terminate()
 267
 268                 if proc_status == "PASS":
 269                     task.basecase_pass = True
 270
 271                 else:
 272                     task.update_status(proc_status)
 273                     if os.path.exists(f"{task.workdir}/engine_{engine_idx}/trace.vcd"):
 274                         task.summary.append(f"counterexample trace: {task.workdir}/engine_{engine_idx}/trace.vcd")
 275                     task.terminate()
 276
 277             elif mode == "prove_induction":
 278                 for proc in task.induction_procs:
 279                     proc.terminate()
 280
 281                 if proc_status == "PASS":
 282                     task.induction_pass = True
 283
 284             else:
 285                 assert False
 286
 287             if task.basecase_pass and task.induction_pass:
 288                 for prop in task.design_hierarchy:
 289                     if prop.type == prop.Type.ASSERT and prop.status == "UNKNOWN":
 290                         prop.status = "PASS"
 291                 task.update_status("PASS")
 292                 task.summary.append("successful proof by k-induction.")
 293                 task.terminate()
 294
 295         else:
 296             assert False
 297
 298     proc.output_callback = output_callback
 299     proc.exit_callback = exit_callback