passes/pmgen/pmgen.py

   1 #!/usr/bin/env python3
   2
   3 import re
   4 import sys
   5 import pprint
   6 import getopt
   7
   8 pp = pprint.PrettyPrinter(indent=4)
   9
  10 prefix = None
  11 pmgfiles = list()
  12 outfile = None
  13 debug = False
  14 genhdr = False
  15
  16 opts, args = getopt.getopt(sys.argv[1:], "p:o:dg")
  17
  18 for o, a in opts:
  19     if o == "-p":
  20         prefix = a
  21     elif o == "-o":
  22         outfile = a
  23     elif o == "-d":
  24         debug = True
  25     elif o == "-g":
  26         genhdr = True
  27
  28 if outfile is None:
  29     outfile = "/dev/stdout"
  30
  31 for a in args:
  32     assert a.endswith(".pmg")
  33     if prefix is None and len(args) == 1:
  34         prefix = a[0:-4]
  35         prefix = prefix.split('/')[-1]
  36     pmgfiles.append(a)
  37
  38 assert prefix is not None
  39
  40 current_pattern = None
  41 current_subpattern = None
  42 patterns = dict()
  43 subpatterns = dict()
  44 subpattern_args = dict()
  45 state_types = dict()
  46 udata_types = dict()
  47 blocks = list()
  48 ids = dict()
  49
  50 def rewrite_cpp(s):
  51     t = list()
  52     i = 0
  53     while i < len(s):
  54         if s[i] in ("'", '"') and i + 1 < len(s):
  55             j = i + 1
  56             while j + 1 < len(s) and s[j] != s[i]:
  57                 if s[j] == '\\' and j + 1 < len(s):
  58                     j += 1
  59                 j += 1
  60             t.append(s[i:j+1])
  61             i = j + 1
  62             continue
  63
  64         if s[i] in ('$', '\\') and i + 1 < len(s):
  65             j = i + 1
  66             while True:
  67                 if j == len(s):
  68                     j -= 1
  69                     break
  70                 if ord('a') <= ord(s[j]) <= ord('z'):
  71                     j += 1
  72                     continue
  73                 if ord('A') <= ord(s[j]) <= ord('Z'):
  74                     j += 1
  75                     continue
  76                 if ord('0') <= ord(s[j]) <= ord('9'):
  77                     j += 1
  78                     continue
  79                 if s[j] == '_':
  80                     j += 1
  81                     continue
  82                 j -= 1
  83                 break
  84
  85             n = s[i:j+1]
  86             i = j + 1
  87
  88             if n[0] == '$':
  89                 v = "id_d_" + n[1:]
  90             else:
  91                 v = "id_b_" + n[1:]
  92
  93             if v not in ids:
  94                 ids[v] = n
  95             else:
  96                 assert ids[v] == n
  97
  98             t.append(v)
  99             continue
 100
 101         if s[i] == "\t":
 102             t.append("  ")
 103         else:
 104             t.append(s[i])
 105
 106         i += 1
 107
 108     return "".join(t)
 109
 110 def process_pmgfile(f, filename):
 111     linenr = 0
 112     global current_pattern
 113     global current_subpattern
 114     while True:
 115         linenr += 1
 116         line = f.readline()
 117         if line == "": break
 118         line = line.strip()
 119
 120         cmd = line.split()
 121         if len(cmd) == 0 or cmd[0].startswith("//"): continue
 122         cmd = cmd[0]
 123
 124         if cmd == "pattern":
 125             if current_pattern is not None:
 126                 block = dict()
 127                 block["type"] = "final"
 128                 block["pattern"] = (current_pattern, current_subpattern)
 129                 blocks.append(block)
 130             line = line.split()
 131             assert len(line) == 2
 132             assert line[1] not in patterns
 133             current_pattern = line[1]
 134             current_subpattern = ""
 135             patterns[current_pattern] = len(blocks)
 136             subpatterns[(current_pattern, current_subpattern)] = len(blocks)
 137             subpattern_args[(current_pattern, current_subpattern)] = list()
 138             state_types[current_pattern] = dict()
 139             udata_types[current_pattern] = dict()
 140             continue
 141
 142         assert current_pattern is not None
 143
 144         if cmd == "fallthrough":
 145             block = dict()
 146             block["type"] = "fallthrough"
 147             blocks.append(block)
 148             line = line.split()
 149             assert len(line) == 1
 150             continue
 151
 152         if cmd == "subpattern":
 153             if len(blocks) == 0 or blocks[-1]["type"] != "fallthrough":
 154                 block = dict()
 155                 block["type"] = "final"
 156                 block["pattern"] = (current_pattern, current_subpattern)
 157                 blocks.append(block)
 158             elif len(blocks) and blocks[-1]["type"] == "fallthrough":
 159                 del blocks[-1]
 160             line = line.split()
 161             assert len(line) == 2
 162             current_subpattern = line[1]
 163             subpattern_args[(current_pattern, current_subpattern)] = list()
 164             assert (current_pattern, current_subpattern) not in subpatterns
 165             subpatterns[(current_pattern, current_subpattern)] = len(blocks)
 166             continue
 167
 168         if cmd == "arg":
 169             line = line.split()
 170             assert len(line) > 1
 171             subpattern_args[(current_pattern, current_subpattern)] += line[1:]
 172             continue
 173
 174         if cmd == "state":
 175             m = re.match(r"^state\s+<(.*?)>\s+(([A-Za-z_][A-Za-z_0-9]*\s+)*[A-Za-z_][A-Za-z_0-9]*)\s*$", line)
 176             assert m
 177             type_str = m.group(1)
 178             states_str = m.group(2)
 179             for s in re.split(r"\s+", states_str):
 180                 assert s not in state_types[current_pattern]
 181                 state_types[current_pattern][s] = type_str
 182             continue
 183
 184         if cmd == "udata":
 185             m = re.match(r"^udata\s+<(.*?)>\s+(([A-Za-z_][A-Za-z_0-9]*\s+)*[A-Za-z_][A-Za-z_0-9]*)\s*$", line)
 186             assert m
 187             type_str = m.group(1)
 188             udatas_str = m.group(2)
 189             for s in re.split(r"\s+", udatas_str):
 190                 assert s not in udata_types[current_pattern]
 191                 udata_types[current_pattern][s] = type_str
 192             continue
 193
 194         if cmd == "match":
 195             block = dict()
 196             block["type"] = "match"
 197             block["src"] = "%s:%d" % (filename, linenr)
 198             block["pattern"] = (current_pattern, current_subpattern)
 199
 200             block["genargs"] = None
 201             block["gencode"] = None
 202
 203             line = line.split()
 204             assert len(line) == 2
 205             assert (line[1] not in state_types[current_pattern]) or (state_types[current_pattern][line[1]] == "Cell*")
 206             block["cell"] = line[1]
 207             state_types[current_pattern][line[1]] = "Cell*";
 208
 209             block["if"] = list()
 210             block["setup"] = list()
 211             block["index"] = list()
 212             block["filter"] = list()
 213             block["sets"] = list()
 214             block["optional"] = False
 215             block["semioptional"] = False
 216
 217             while True:
 218                 linenr += 1
 219                 l = f.readline()
 220                 assert l != ""
 221                 a = l.split()
 222                 if len(a) == 0 or a[0].startswith("//"): continue
 223                 if a[0] == "endmatch": break
 224
 225                 if a[0] == "if":
 226                     b = l.lstrip()[2:]
 227                     block["if"].append(rewrite_cpp(b.strip()))
 228                     continue
 229
 230                 if a[0] == "select":
 231                     b = l.lstrip()[6:]
 232                     block["setup"].append(("select", rewrite_cpp(b.strip())))
 233                     continue
 234
 235                 if a[0] == "slice":
 236                     m = re.match(r"^\s*slice\s+(\S+)\s+(.*?)\s*$", l)
 237                     block["setup"].append(("slice", m.group(1), rewrite_cpp(m.group(2))))
 238                     continue
 239
 240                 if a[0] == "choice":
 241                     m = re.match(r"^\s*choice\s+<(.*?)>\s+(\S+)\s+(.*?)\s*$", l)
 242                     block["setup"].append(("choice", m.group(1), m.group(2), rewrite_cpp(m.group(3))))
 243                     continue
 244
 245                 if a[0] == "define":
 246                     m = re.match(r"^\s*define\s+<(.*?)>\s+(\S+)\s+(.*?)\s*$", l)
 247                     block["setup"].append(("define", m.group(1), m.group(2), rewrite_cpp(m.group(3))))
 248                     continue
 249
 250                 if a[0] == "index":
 251                     m = re.match(r"^\s*index\s+<(.*?)>\s+(.*?)\s*===\s*(.*?)\s*$", l)
 252                     assert m
 253                     block["index"].append((m.group(1), rewrite_cpp(m.group(2)), rewrite_cpp(m.group(3))))
 254                     continue
 255
 256                 if a[0] == "filter":
 257                     b = l.lstrip()[6:]
 258                     block["filter"].append(rewrite_cpp(b.strip()))
 259                     continue
 260
 261                 if a[0] == "set":
 262                     m = re.match(r"^\s*set\s+(\S+)\s+(.*?)\s*$", l)
 263                     block["sets"].append((m.group(1), rewrite_cpp(m.group(2))))
 264                     continue
 265
 266                 if a[0] == "optional":
 267                     block["optional"] = True
 268                     continue
 269
 270                 if a[0] == "semioptional":
 271                     block["semioptional"] = True
 272                     continue
 273
 274                 if a[0] == "generate":
 275                     block["genargs"] = list([int(s) for s in a[1:]])
 276                     if len(block["genargs"]) == 0: block["genargs"].append(100)
 277                     if len(block["genargs"]) == 1: block["genargs"].append(0)
 278                     assert len(block["genargs"]) == 2
 279                     block["gencode"] = list()
 280                     while True:
 281                         linenr += 1
 282                         l = f.readline()
 283                         assert l != ""
 284                         a = l.split()
 285                         if len(a) == 1 and a[0] == "endmatch": break
 286                         block["gencode"].append(rewrite_cpp(l.rstrip()))
 287                     break
 288
 289                 raise RuntimeError("'%s' statement not recognised on line %d" % (a[0], linenr))
 290
 291             if block["optional"]:
 292                 assert not block["semioptional"]
 293
 294             blocks.append(block)
 295             continue
 296
 297         if cmd == "code":
 298             block = dict()
 299             block["type"] = "code"
 300             block["src"] = "%s:%d" % (filename, linenr)
 301             block["pattern"] = (current_pattern, current_subpattern)
 302
 303             block["code"] = list()
 304             block["fcode"] = list()
 305             block["states"] = set()
 306
 307             for s in line.split()[1:]:
 308                 if s not in state_types[current_pattern]:
 309                     raise RuntimeError("'%s' not in state_types" % s)
 310                 block["states"].add(s)
 311
 312             codetype = "code"
 313
 314             while True:
 315                 linenr += 1
 316                 l = f.readline()
 317                 assert l != ""
 318                 a = l.split()
 319                 if len(a) == 0: continue
 320                 if a[0] == "endcode": break
 321
 322                 if a[0] == "finally":
 323                     codetype = "fcode"
 324                     continue
 325
 326                 block[codetype].append(rewrite_cpp(l.rstrip()))
 327
 328             blocks.append(block)
 329             continue
 330
 331         raise RuntimeError("'%s' command not recognised" % cmd)
 332
 333 for fn in pmgfiles:
 334     with open(fn, "r") as f:
 335         process_pmgfile(f, fn)
 336
 337 if current_pattern is not None:
 338     block = dict()
 339     block["type"] = "final"
 340     block["pattern"] = (current_pattern, current_subpattern)
 341     blocks.append(block)
 342
 343 current_pattern = None
 344 current_subpattern = None
 345
 346 if debug:
 347     pp.pprint(blocks)
 348
 349 with open(outfile, "w") as f:
 350     for fn in pmgfiles:
 351         print("// Generated by pmgen.py from {}".format(fn), file=f)
 352     print("", file=f)
 353
 354     if genhdr:
 355         print("#include \"kernel/yosys.h\"", file=f)
 356         print("#include \"kernel/sigtools.h\"", file=f)
 357         print("", file=f)
 358         print("YOSYS_NAMESPACE_BEGIN", file=f)
 359         print("", file=f)
 360
 361     print("struct {}_pm {{".format(prefix), file=f)
 362     print("  Module *module;", file=f)
 363     print("  SigMap sigmap;", file=f)
 364     print("  std::function<void()> on_accept;", file=f)
 365     print("  bool setup_done;", file=f)
 366     print("  bool generate_mode;", file=f)
 367     print("  int accept_cnt;", file=f)
 368     print("", file=f)
 369
 370     print("  uint32_t rngseed;", file=f)
 371     print("  int rng(unsigned int n) {", file=f)
 372     print("    rngseed ^= rngseed << 13;", file=f)
 373     print("    rngseed ^= rngseed >> 17;", file=f)
 374     print("    rngseed ^= rngseed << 5;", file=f)
 375     print("    return rngseed % n;", file=f)
 376     print("  }", file=f)
 377     print("", file=f)
 378
 379     for index in range(len(blocks)):
 380         block = blocks[index]
 381         if block["type"] == "match":
 382             index_types = list()
 383             for entry in block["index"]:
 384                 index_types.append(entry[0])
 385             value_types = ["Cell*"]
 386             for entry in block["setup"]:
 387                 if entry[0] == "slice":
 388                     value_types.append("int")
 389                 if entry[0] == "choice":
 390                     value_types.append(entry[1])
 391                 if entry[0] == "define":
 392                     value_types.append(entry[1])
 393             print("  typedef std::tuple<{}> index_{}_key_type;".format(", ".join(index_types), index), file=f)
 394             print("  typedef std::tuple<{}> index_{}_value_type;".format(", ".join(value_types), index), file=f)
 395             print("  dict<index_{}_key_type, vector<index_{}_value_type>> index_{};".format(index, index, index), file=f)
 396     print("  dict<SigBit, pool<Cell*>> sigusers;", file=f)
 397     print("  pool<Cell*> blacklist_cells;", file=f)
 398     print("  pool<Cell*> autoremove_cells;", file=f)
 399     print("  dict<Cell*,int> rollback_cache;", file=f)
 400     print("  int rollback;", file=f)
 401     print("", file=f)
 402
 403     for current_pattern in sorted(patterns.keys()):
 404         print("  struct state_{}_t {{".format(current_pattern), file=f)
 405         for s, t in sorted(state_types[current_pattern].items()):
 406             print("    {} {};".format(t, s), file=f)
 407         print("  }} st_{};".format(current_pattern), file=f)
 408         print("", file=f)
 409
 410         print("  struct udata_{}_t {{".format(current_pattern), file=f)
 411         for s, t in sorted(udata_types[current_pattern].items()):
 412             print("    {} {};".format(t, s), file=f)
 413         print("  }} ud_{};".format(current_pattern), file=f)
 414         print("", file=f)
 415     current_pattern = None
 416
 417     for v, n in sorted(ids.items()):
 418         if n[0] == "\\":
 419             print("  IdString {}{{\"\\{}\"}};".format(v, n), file=f)
 420         else:
 421             print("  IdString {}{{\"{}\"}};".format(v, n), file=f)
 422     print("", file=f)
 423
 424     print("  void add_siguser(const SigSpec &sig, Cell *cell) {", file=f)
 425     print("    for (auto bit : sigmap(sig)) {", file=f)
 426     print("      if (bit.wire == nullptr) continue;", file=f)
 427     print("      sigusers[bit].insert(cell);", file=f)
 428     print("    }", file=f)
 429     print("  }", file=f)
 430     print("", file=f)
 431
 432     print("  void blacklist(Cell *cell) {", file=f)
 433     print("    if (cell != nullptr && blacklist_cells.insert(cell).second) {", file=f)
 434     print("      auto ptr = rollback_cache.find(cell);", file=f)
 435     print("      if (ptr == rollback_cache.end()) return;", file=f)
 436     print("      int rb = ptr->second;", file=f)
 437     print("      if (rollback == 0 || rollback > rb)", file=f)
 438     print("        rollback = rb;", file=f)
 439     print("    }", file=f)
 440     print("  }", file=f)
 441     print("", file=f)
 442
 443     print("  void autoremove(Cell *cell) {", file=f)
 444     print("    if (cell != nullptr) {", file=f)
 445     print("      autoremove_cells.insert(cell);", file=f)
 446     print("      blacklist(cell);", file=f)
 447     print("    }", file=f)
 448     print("  }", file=f)
 449     print("", file=f)
 450
 451     current_pattern = None
 452
 453     print("  SigSpec port(Cell *cell, IdString portname) {", file=f)
 454     print("    try {", file=f)
 455     print("      return sigmap(cell->getPort(portname));", file=f)
 456     print("    } catch(std::out_of_range&) { log_error(\"Accessing non existing port %s\\n\",portname.c_str()); }", file=f)
 457     print("  }", file=f)
 458     print("", file=f)
 459     print("  SigSpec port(Cell *cell, IdString portname, const SigSpec& defval) {", file=f)
 460     print("    return sigmap(cell->connections_.at(portname, defval));", file=f)
 461     print("  }", file=f)
 462     print("", file=f)
 463
 464     print("  Const param(Cell *cell, IdString paramname) {", file=f)
 465     print("    try {", file=f)
 466     print("      return cell->getParam(paramname);", file=f)
 467     print("    } catch(std::out_of_range&) { log_error(\"Accessing non existing parameter %s\\n\",paramname.c_str()); }", file=f)
 468     print("  }", file=f)
 469     print("", file=f)
 470     print("  Const param(Cell *cell, IdString paramname, const Const& defval) {", file=f)
 471     print("    return cell->parameters.at(paramname, defval);", file=f)
 472     print("  }", file=f)
 473     print("", file=f)
 474
 475     print("  int nusers(const SigSpec &sig) {", file=f)
 476     print("    pool<Cell*> users;", file=f)
 477     print("    for (auto bit : sigmap(sig))", file=f)
 478     print("      for (auto user : sigusers[bit])", file=f)
 479     print("        users.insert(user);", file=f)
 480     print("    return GetSize(users);", file=f)
 481     print("  }", file=f)
 482     print("", file=f)
 483
 484     print("  {}_pm(Module *module, const vector<Cell*> &cells) :".format(prefix), file=f)
 485     print("      module(module), sigmap(module), setup_done(false), generate_mode(false), rngseed(12345678) {", file=f)
 486     print("    setup(cells);", file=f)
 487     print("  }", file=f)
 488     print("", file=f)
 489
 490     print("  {}_pm(Module *module) :".format(prefix), file=f)
 491     print("      module(module), sigmap(module), setup_done(false), generate_mode(false), rngseed(12345678) {", file=f)
 492     print("  }", file=f)
 493     print("", file=f)
 494
 495     print("  void setup(const vector<Cell*> &cells) {", file=f)
 496     for current_pattern in sorted(patterns.keys()):
 497         for s, t in sorted(udata_types[current_pattern].items()):
 498             if t.endswith("*"):
 499                 print("    ud_{}.{} = nullptr;".format(current_pattern,s), file=f)
 500             else:
 501                 print("    ud_{}.{} = {}();".format(current_pattern, s, t), file=f)
 502     current_pattern = None
 503     print("    log_assert(!setup_done);", file=f)
 504     print("    setup_done = true;", file=f)
 505     print("    for (auto port : module->ports)", file=f)
 506     print("      add_siguser(module->wire(port), nullptr);", file=f)
 507     print("    for (auto cell : module->cells())", file=f)
 508     print("      for (auto &conn : cell->connections())", file=f)
 509     print("        add_siguser(conn.second, cell);", file=f)
 510     print("    for (auto cell : cells) {", file=f)
 511
 512     for index in range(len(blocks)):
 513         block = blocks[index]
 514         if block["type"] == "match":
 515             print("      do {", file=f)
 516             print("        Cell *{} = cell;".format(block["cell"]), file=f)
 517             print("        index_{}_value_type value;".format(index), file=f)
 518             print("        std::get<0>(value) = cell;", file=f)
 519             loopcnt = 0
 520             valueidx = 1
 521             for item in block["setup"]:
 522                 if item[0] == "select":
 523                     print("        if (!({})) continue;".format(item[1]), file=f)
 524                 if item[0] == "slice":
 525                     print("        int &{} = std::get<{}>(value);".format(item[1], valueidx), file=f)
 526                     print("        for ({} = 0; {} < {}; {}++) {{".format(item[1], item[1], item[2], item[1]), file=f)
 527                     valueidx += 1
 528                     loopcnt += 1
 529                 if item[0] == "choice":
 530                     print("        vector<{}> _pmg_choices_{} = {};".format(item[1], item[2], item[3]), file=f)
 531                     print("        for (const {} &{} : _pmg_choices_{}) {{".format(item[1], item[2], item[2]), file=f)
 532                     print("        std::get<{}>(value) = {};".format(valueidx, item[2]), file=f)
 533                     valueidx += 1
 534                     loopcnt += 1
 535                 if item[0] == "define":
 536                     print("        {} &{} = std::get<{}>(value);".format(item[1], item[2], valueidx), file=f)
 537                     print("        {} = {};".format(item[2], item[3]), file=f)
 538                     valueidx += 1
 539             print("        index_{}_key_type key;".format(index), file=f)
 540             for field, entry in enumerate(block["index"]):
 541                 print("        std::get<{}>(key) = {};".format(field, entry[1]), file=f)
 542             print("        index_{}[key].push_back(value);".format(index), file=f)
 543             for i in range(loopcnt):
 544                 print("        }", file=f)
 545             print("      } while (0);", file=f)
 546
 547     print("    }", file=f)
 548     print("  }", file=f)
 549     print("", file=f)
 550
 551     print("  ~{}_pm() {{".format(prefix), file=f)
 552     print("    for (auto cell : autoremove_cells)", file=f)
 553     print("      module->remove(cell);", file=f)
 554     print("  }", file=f)
 555     print("", file=f)
 556
 557     for current_pattern in sorted(patterns.keys()):
 558         print("  int run_{}(std::function<void()> on_accept_f) {{".format(current_pattern), file=f)
 559         print("    log_assert(setup_done);", file=f)
 560         print("    accept_cnt = 0;", file=f)
 561         print("    on_accept = on_accept_f;", file=f)
 562         print("    rollback = 0;", file=f)
 563         for s, t in sorted(state_types[current_pattern].items()):
 564             if t.endswith("*"):
 565                 print("    st_{}.{} = nullptr;".format(current_pattern, s), file=f)
 566             else:
 567                 print("    st_{}.{} = {}();".format(current_pattern, s, t), file=f)
 568         print("    block_{}(1);".format(patterns[current_pattern]), file=f)
 569         print("    log_assert(rollback_cache.empty());", file=f)
 570         print("    return accept_cnt;", file=f)
 571         print("  }", file=f)
 572         print("", file=f)
 573         print("  int run_{}(std::function<void({}_pm&)> on_accept_f) {{".format(current_pattern, prefix), file=f)
 574         print("    return run_{}([&](){{on_accept_f(*this);}});".format(current_pattern), file=f)
 575         print("  }", file=f)
 576         print("", file=f)
 577         print("  int run_{}() {{".format(current_pattern), file=f)
 578         print("    return run_{}([](){{}});".format(current_pattern, current_pattern), file=f)
 579         print("  }", file=f)
 580         print("", file=f)
 581
 582     if len(subpatterns):
 583         for p, s in sorted(subpatterns.keys()):
 584             print("  void block_subpattern_{}_{}(int recursion) {{ block_{}(recursion); }}".format(p, s, subpatterns[(p, s)]), file=f)
 585         print("", file=f)
 586
 587     current_pattern = None
 588     current_subpattern = None
 589
 590     for index in range(len(blocks)):
 591         block = blocks[index]
 592
 593         if block["type"] in ("match", "code"):
 594             print("  // {}".format(block["src"]), file=f)
 595
 596         print("  void block_{}(int recursion YS_MAYBE_UNUSED) {{".format(index), file=f)
 597         current_pattern, current_subpattern = block["pattern"]
 598
 599         if block["type"] == "final":
 600             print("  }", file=f)
 601             if index+1 != len(blocks):
 602                 print("", file=f)
 603             continue
 604
 605         const_st = set()
 606         nonconst_st = set()
 607         restore_st = set()
 608
 609         for s in subpattern_args[(current_pattern, current_subpattern)]:
 610             const_st.add(s)
 611
 612         for i in range(subpatterns[(current_pattern, current_subpattern)], index):
 613             if blocks[i]["type"] == "code":
 614                 for s in blocks[i]["states"]:
 615                     const_st.add(s)
 616             elif blocks[i]["type"] == "match":
 617                 const_st.add(blocks[i]["cell"])
 618                 for item in blocks[i]["sets"]:
 619                     const_st.add(item[0])
 620             else:
 621                 assert False
 622
 623         if block["type"] == "code":
 624             for s in block["states"]:
 625                 if s in const_st:
 626                     const_st.remove(s)
 627                     restore_st.add(s)
 628                 nonconst_st.add(s)
 629         elif block["type"] == "match":
 630             s = block["cell"]
 631             assert s not in const_st
 632             nonconst_st.add(s)
 633             for item in block["sets"]:
 634                 if item[0] in const_st:
 635                     const_st.remove(item[0])
 636                 nonconst_st.add(item[0])
 637         else:
 638             assert False
 639
 640         for s in sorted(const_st):
 641             t = state_types[current_pattern][s]
 642             if t.endswith("*"):
 643                 print("    {} const &{} YS_MAYBE_UNUSED = st_{}.{};".format(t, s, current_pattern, s), file=f)
 644             else:
 645                 print("    const {} &{} YS_MAYBE_UNUSED = st_{}.{};".format(t, s, current_pattern, s), file=f)
 646
 647         for s in sorted(nonconst_st):
 648             t = state_types[current_pattern][s]
 649             print("    {} &{} YS_MAYBE_UNUSED = st_{}.{};".format(t, s, current_pattern, s), file=f)
 650
 651         for u in sorted(udata_types[current_pattern].keys()):
 652             t = udata_types[current_pattern][u]
 653             print("    {} &{} YS_MAYBE_UNUSED = ud_{}.{};".format(t, u, current_pattern, u), file=f)
 654
 655         if len(restore_st):
 656             print("", file=f)
 657             for s in sorted(restore_st):
 658                 t = state_types[current_pattern][s]
 659                 print("    {} _pmg_backup_{} = {};".format(t, s, s), file=f)
 660
 661         if block["type"] == "code":
 662             print("", file=f)
 663             print("#define reject do { goto rollback_label; } while(0)", file=f)
 664             print("#define accept do { accept_cnt++; on_accept(); if (rollback) goto rollback_label; } while(0)", file=f)
 665             print("#define finish do { rollback = -1; goto rollback_label; } while(0)", file=f)
 666             print("#define branch do {{ block_{}(recursion+1); if (rollback) goto rollback_label; }} while(0)".format(index+1), file=f)
 667             print("#define subpattern(pattern_name) do {{ block_subpattern_{}_ ## pattern_name (recursion+1); if (rollback) goto rollback_label; }} while(0)".format(current_pattern), file=f)
 668
 669             for line in block["code"]:
 670                 print("  " + line, file=f)
 671
 672             print("", file=f)
 673             print("    block_{}(recursion+1);".format(index+1), file=f)
 674
 675             print("#undef reject", file=f)
 676             print("#undef accept", file=f)
 677             print("#undef finish", file=f)
 678             print("#undef branch", file=f)
 679             print("#undef subpattern", file=f)
 680
 681             print("", file=f)
 682             print("rollback_label:", file=f)
 683             print("    YS_MAYBE_UNUSED;", file=f)
 684
 685             if len(block["fcode"]):
 686                 print("#define accept do { accept_cnt++; on_accept(); } while(0)", file=f)
 687                 print("#define finish do { rollback = -1; goto finish_label; } while(0)", file=f)
 688                 for line in block["fcode"]:
 689                     print("  " + line, file=f)
 690                 print("finish_label:", file=f)
 691                 print("    YS_MAYBE_UNUSED;", file=f)
 692                 print("#undef accept", file=f)
 693                 print("#undef finish", file=f)
 694
 695             if len(restore_st) or len(nonconst_st):
 696                 print("", file=f)
 697                 for s in sorted(restore_st):
 698                     t = state_types[current_pattern][s]
 699                     print("    {} = _pmg_backup_{};".format(s, s), file=f)
 700                 for s in sorted(nonconst_st):
 701                     if s not in restore_st:
 702                         t = state_types[current_pattern][s]
 703                         if t.endswith("*"):
 704                             print("    {} = nullptr;".format(s), file=f)
 705                         else:
 706                             print("    {} = {}();".format(s, t), file=f)
 707
 708         elif block["type"] == "match":
 709             assert len(restore_st) == 0
 710
 711             print("    Cell* _pmg_backup_{} = {};".format(block["cell"], block["cell"]), file=f)
 712
 713             if len(block["if"]):
 714                 for expr in block["if"]:
 715                     print("", file=f)
 716                     print("    if (!({})) {{".format(expr), file=f)
 717                     print("      {} = nullptr;".format(block["cell"]), file=f)
 718                     print("      block_{}(recursion+1);".format(index+1), file=f)
 719                     print("      {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f)
 720                     print("      return;", file=f)
 721                     print("    }", file=f)
 722
 723             print("", file=f)
 724             print("    index_{}_key_type key;".format(index), file=f)
 725             for field, entry in enumerate(block["index"]):
 726                 print("    std::get<{}>(key) = {};".format(field, entry[2]), file=f)
 727             print("    auto cells_ptr = index_{}.find(key);".format(index), file=f)
 728
 729             if block["semioptional"] or block["genargs"] is not None:
 730                 print("    bool found_any_match = false;", file=f)
 731
 732             print("", file=f)
 733             print("    if (cells_ptr != index_{}.end()) {{".format(index), file=f)
 734             print("      const vector<index_{}_value_type> &cells = cells_ptr->second;".format(index), file=f)
 735             print("      for (int _pmg_idx = 0; _pmg_idx < GetSize(cells); _pmg_idx++) {", file=f)
 736             print("        {} = std::get<0>(cells[_pmg_idx]);".format(block["cell"]), file=f)
 737             valueidx = 1
 738             for item in block["setup"]:
 739                 if item[0] == "slice":
 740                     print("        const int &{} YS_MAYBE_UNUSED = std::get<{}>(cells[_pmg_idx]);".format(item[1], valueidx), file=f)
 741                     valueidx += 1
 742                 if item[0] == "choice":
 743                     print("        const {} &{} YS_MAYBE_UNUSED = std::get<{}>(cells[_pmg_idx]);".format(item[1], item[2], valueidx), file=f)
 744                     valueidx += 1
 745                 if item[0] == "define":
 746                     print("        const {} &{} YS_MAYBE_UNUSED = std::get<{}>(cells[_pmg_idx]);".format(item[1], item[2], valueidx), file=f)
 747                     valueidx += 1
 748             print("        if (blacklist_cells.count({})) continue;".format(block["cell"]), file=f)
 749             for expr in block["filter"]:
 750                 print("        if (!({})) continue;".format(expr), file=f)
 751             if block["semioptional"] or block["genargs"] is not None:
 752                 print("        found_any_match = true;", file=f)
 753             for item in block["sets"]:
 754                 print("        auto _pmg_backup_{} = {};".format(item[0], item[0]), file=f)
 755                 print("        {} = {};".format(item[0], item[1]), file=f)
 756             print("        auto rollback_ptr = rollback_cache.insert(make_pair(std::get<0>(cells[_pmg_idx]), recursion));", file=f)
 757             print("        block_{}(recursion+1);".format(index+1), file=f)
 758             for item in block["sets"]:
 759                 print("        {} = _pmg_backup_{};".format(item[0], item[0]), file=f)
 760             print("        if (rollback_ptr.second)", file=f)
 761             print("          rollback_cache.erase(rollback_ptr.first);", file=f)
 762             print("        if (rollback) {", file=f)
 763             print("          if (rollback != recursion) {{".format(index+1), file=f)
 764             print("            {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f)
 765             print("            return;", file=f)
 766             print("          }", file=f)
 767             print("          rollback = 0;", file=f)
 768             print("        }", file=f)
 769             print("      }", file=f)
 770             print("    }", file=f)
 771
 772             print("", file=f)
 773             print("    {} = nullptr;".format(block["cell"]), file=f)
 774
 775             if block["optional"]:
 776                 print("    block_{}(recursion+1);".format(index+1), file=f)
 777
 778             if block["semioptional"]:
 779                 print("    if (!found_any_match) block_{}(recursion+1);".format(index+1), file=f)
 780
 781             print("    {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f)
 782
 783             if block["genargs"] is not None:
 784                 print("#define finish do { rollback = -1; return; } while(0)", file=f)
 785                 print("    if (generate_mode && rng(100) < (found_any_match ? {} : {})) {{".format(block["genargs"][1], block["genargs"][0]), file=f)
 786                 for line in block["gencode"]:
 787                     print("      " + line, file=f)
 788                 print("    }", file=f)
 789                 print("#undef finish", file=f)
 790         else:
 791             assert False
 792
 793         current_pattern = None
 794         print("  }", file=f)
 795         print("", file=f)
 796
 797     print("};", file=f)
 798
 799     if genhdr:
 800         print("", file=f)
 801         print("YOSYS_NAMESPACE_END", file=f)