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 == "subpattern":
 145             block = dict()
 146             block["type"] = "final"
 147             block["pattern"] = (current_pattern, current_subpattern)
 148             blocks.append(block)
 149             line = line.split()
 150             assert len(line) == 2
 151             current_subpattern = line[1]
 152             subpattern_args[(current_pattern, current_subpattern)] = list()
 153             assert (current_pattern, current_subpattern) not in subpatterns
 154             subpatterns[(current_pattern, current_subpattern)] = len(blocks)
 155             continue
 156
 157         if cmd == "arg":
 158             line = line.split()
 159             assert len(line) > 1
 160             subpattern_args[(current_pattern, current_subpattern)] += line[1:]
 161             continue
 162
 163         if cmd == "state":
 164             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)
 165             assert m
 166             type_str = m.group(1)
 167             states_str = m.group(2)
 168             for s in re.split(r"\s+", states_str):
 169                 assert s not in state_types[current_pattern]
 170                 state_types[current_pattern][s] = type_str
 171             continue
 172
 173         if cmd == "udata":
 174             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)
 175             assert m
 176             type_str = m.group(1)
 177             udatas_str = m.group(2)
 178             for s in re.split(r"\s+", udatas_str):
 179                 assert s not in udata_types[current_pattern]
 180                 udata_types[current_pattern][s] = type_str
 181             continue
 182
 183         if cmd == "match":
 184             block = dict()
 185             block["type"] = "match"
 186             block["src"] = "%s:%d" % (filename, linenr)
 187             block["pattern"] = (current_pattern, current_subpattern)
 188
 189             block["genargs"] = None
 190             block["gencode"] = None
 191
 192             line = line.split()
 193             assert len(line) == 2
 194             assert (line[1] not in state_types[current_pattern]) or (state_types[current_pattern][line[1]] == "Cell*")
 195             block["cell"] = line[1]
 196             state_types[current_pattern][line[1]] = "Cell*";
 197
 198             block["if"] = list()
 199             block["select"] = list()
 200             block["index"] = list()
 201             block["filter"] = list()
 202             block["optional"] = False
 203             block["semioptional"] = False
 204
 205             while True:
 206                 linenr += 1
 207                 l = f.readline()
 208                 assert l != ""
 209                 a = l.split()
 210                 if len(a) == 0 or a[0].startswith("//"): continue
 211                 if a[0] == "endmatch": break
 212
 213                 if a[0] == "if":
 214                     b = l.lstrip()[2:]
 215                     block["if"].append(rewrite_cpp(b.strip()))
 216                     continue
 217
 218                 if a[0] == "select":
 219                     b = l.lstrip()[6:]
 220                     block["select"].append(rewrite_cpp(b.strip()))
 221                     continue
 222
 223                 if a[0] == "index":
 224                     m = re.match(r"^\s*index\s+<(.*?)>\s+(.*?)\s*===\s*(.*?)\s*$", l)
 225                     assert m
 226                     block["index"].append((m.group(1), rewrite_cpp(m.group(2)), rewrite_cpp(m.group(3))))
 227                     continue
 228
 229                 if a[0] == "filter":
 230                     b = l.lstrip()[6:]
 231                     block["filter"].append(rewrite_cpp(b.strip()))
 232                     continue
 233
 234                 if a[0] == "optional":
 235                     block["optional"] = True
 236                     continue
 237
 238                 if a[0] == "semioptional":
 239                     block["semioptional"] = True
 240                     continue
 241
 242                 if a[0] == "generate":
 243                     block["genargs"] = list([int(s) for s in a[1:]])
 244                     block["gencode"] = list()
 245                     assert len(block["genargs"]) < 2
 246                     while True:
 247                         linenr += 1
 248                         l = f.readline()
 249                         assert l != ""
 250                         a = l.split()
 251                         if a[0] == "endmatch": break
 252                         block["gencode"].append(rewrite_cpp(l.rstrip()))
 253                     break
 254
 255                 assert False
 256
 257             if block["optional"]:
 258                 assert not block["semioptional"]
 259
 260             blocks.append(block)
 261             continue
 262
 263         if cmd == "code":
 264             block = dict()
 265             block["type"] = "code"
 266             block["src"] = "%s:%d" % (filename, linenr)
 267             block["pattern"] = (current_pattern, current_subpattern)
 268
 269             block["code"] = list()
 270             block["fcode"] = list()
 271             block["states"] = set()
 272
 273             for s in line.split()[1:]:
 274                 assert s in state_types[current_pattern]
 275                 block["states"].add(s)
 276
 277             codetype = "code"
 278
 279             while True:
 280                 linenr += 1
 281                 l = f.readline()
 282                 assert l != ""
 283                 a = l.split()
 284                 if len(a) == 0: continue
 285                 if a[0] == "endcode": break
 286
 287                 if a[0] == "finally":
 288                     codetype = "fcode"
 289                     continue
 290
 291                 block[codetype].append(rewrite_cpp(l.rstrip()))
 292
 293             blocks.append(block)
 294             continue
 295
 296         assert False
 297
 298 for fn in pmgfiles:
 299     with open(fn, "r") as f:
 300         process_pmgfile(f, fn)
 301
 302 if current_pattern is not None:
 303     block = dict()
 304     block["type"] = "final"
 305     block["pattern"] = (current_pattern, current_subpattern)
 306     blocks.append(block)
 307
 308 current_pattern = None
 309 current_subpattern = None
 310
 311 if debug:
 312     pp.pprint(blocks)
 313
 314 with open(outfile, "w") as f:
 315     for fn in pmgfiles:
 316         print("// Generated by pmgen.py from {}".format(fn), file=f)
 317     print("", file=f)
 318
 319     if genhdr:
 320         print("#include \"kernel/yosys.h\"", file=f)
 321         print("#include \"kernel/sigtools.h\"", file=f)
 322         print("", file=f)
 323         print("YOSYS_NAMESPACE_BEGIN", file=f)
 324         print("", file=f)
 325
 326     print("struct {}_pm {{".format(prefix), file=f)
 327     print("  Module *module;", file=f)
 328     print("  SigMap sigmap;", file=f)
 329     print("  std::function<void()> on_accept;", file=f)
 330     print("  bool generate_mode;", file=f)
 331     print("  int accept_cnt;", file=f)
 332     print("", file=f)
 333
 334     print("  uint32_t rngseed;", file=f)
 335     print("  int rng(unsigned int n) {", file=f)
 336     print("    rngseed ^= rngseed << 13;", file=f)
 337     print("    rngseed ^= rngseed >> 17;", file=f)
 338     print("    rngseed ^= rngseed << 5;", file=f)
 339     print("    return rngseed % n;", file=f)
 340     print("  }", file=f)
 341     print("", file=f)
 342
 343     for index in range(len(blocks)):
 344         block = blocks[index]
 345         if block["type"] == "match":
 346             index_types = list()
 347             for entry in block["index"]:
 348                 index_types.append(entry[0])
 349             print("  typedef std::tuple<{}> index_{}_key_type;".format(", ".join(index_types), index), file=f)
 350             print("  dict<index_{}_key_type, vector<Cell*>> index_{};".format(index, index), file=f)
 351     print("  dict<SigBit, pool<Cell*>> sigusers;", file=f)
 352     print("  pool<Cell*> blacklist_cells;", file=f)
 353     print("  pool<Cell*> autoremove_cells;", file=f)
 354     print("  bool blacklist_dirty;", file=f)
 355     print("  vector<pair<Cell*,int>> rollback_stack;", file=f)
 356     print("  int rollback;", file=f)
 357     print("", file=f)
 358
 359     for current_pattern in sorted(patterns.keys()):
 360         print("  struct state_{}_t {{".format(current_pattern), file=f)
 361         for s, t in sorted(state_types[current_pattern].items()):
 362             print("    {} {};".format(t, s), file=f)
 363         print("  }} st_{};".format(current_pattern), file=f)
 364         print("", file=f)
 365
 366         print("  struct udata_{}_t {{".format(current_pattern), file=f)
 367         for s, t in sorted(udata_types[current_pattern].items()):
 368             print("    {} {};".format(t, s), file=f)
 369         print("  }} ud_{};".format(current_pattern), file=f)
 370         print("", file=f)
 371     current_pattern = None
 372
 373     for v, n in sorted(ids.items()):
 374         if n[0] == "\\":
 375             print("  IdString {}{{\"\\{}\"}};".format(v, n), file=f)
 376         else:
 377             print("  IdString {}{{\"{}\"}};".format(v, n), file=f)
 378     print("", file=f)
 379
 380     print("  void add_siguser(const SigSpec &sig, Cell *cell) {", file=f)
 381     print("    for (auto bit : sigmap(sig)) {", file=f)
 382     print("      if (bit.wire == nullptr) continue;", file=f)
 383     print("      if (sigusers.count(bit) == 0 && bit.wire->port_id)", file=f)
 384     print("        sigusers[bit].insert(nullptr);", file=f)
 385     print("      sigusers[bit].insert(cell);", file=f)
 386     print("    }", file=f)
 387     print("  }", file=f)
 388     print("", file=f)
 389
 390     print("  void blacklist(Cell *cell) {", file=f)
 391     print("    if (cell != nullptr) {", file=f)
 392     print("      if (blacklist_cells.insert(cell).second)", file=f)
 393     print("        blacklist_dirty = true;", file=f)
 394     print("    }", file=f)
 395     print("  }", file=f)
 396     print("", file=f)
 397
 398     print("  void check_blacklist() {", file=f)
 399     print("    if (!blacklist_dirty)", file=f)
 400     print("      return;", file=f)
 401     print("    blacklist_dirty = false;", file=f)
 402     print("    for (int i = 0; i < GetSize(rollback_stack); i++)", file=f)
 403     print("      if (blacklist_cells.count(rollback_stack[i].first)) {", file=f)
 404     print("        rollback = rollback_stack[i].second;", file=f)
 405     print("        rollback_stack.resize(i);", file=f)
 406     print("        return;", file=f)
 407     print("      }", file=f)
 408     print("  }", file=f)
 409     print("", file=f)
 410
 411     print("  void autoremove(Cell *cell) {", file=f)
 412     print("    if (cell != nullptr) {", file=f)
 413     print("      if (blacklist_cells.insert(cell).second)", file=f)
 414     print("        blacklist_dirty = true;", file=f)
 415     print("      autoremove_cells.insert(cell);", file=f)
 416     print("    }", file=f)
 417     print("  }", file=f)
 418     print("", file=f)
 419
 420     current_pattern = None
 421
 422     print("  SigSpec port(Cell *cell, IdString portname) {", file=f)
 423     print("    return sigmap(cell->getPort(portname));", file=f)
 424     print("  }", file=f)
 425     print("", file=f)
 426
 427     print("  Const param(Cell *cell, IdString paramname) {", file=f)
 428     print("    return cell->getParam(paramname);", file=f)
 429     print("  }", file=f)
 430     print("", file=f)
 431
 432     print("  int nusers(const SigSpec &sig) {", file=f)
 433     print("    pool<Cell*> users;", file=f)
 434     print("    for (auto bit : sigmap(sig))", file=f)
 435     print("      for (auto user : sigusers[bit])", file=f)
 436     print("        users.insert(user);", file=f)
 437     print("    return GetSize(users);", file=f)
 438     print("  }", file=f)
 439     print("", file=f)
 440
 441     print("  {}_pm(Module *module, const vector<Cell*> &cells) :".format(prefix), file=f)
 442     print("      module(module), sigmap(module), generate_mode(false), rngseed(12345678) {", file=f)
 443     for current_pattern in sorted(patterns.keys()):
 444         for s, t in sorted(udata_types[current_pattern].items()):
 445             if t.endswith("*"):
 446                 print("    ud_{}.{} = nullptr;".format(current_pattern,s), file=f)
 447             else:
 448                 print("    ud_{}.{} = {}();".format(current_pattern, s, t), file=f)
 449     current_pattern = None
 450     print("    for (auto cell : module->cells()) {", file=f)
 451     print("      for (auto &conn : cell->connections())", file=f)
 452     print("        add_siguser(conn.second, cell);", file=f)
 453     print("    }", file=f)
 454     print("    for (auto cell : cells) {", file=f)
 455
 456     for index in range(len(blocks)):
 457         block = blocks[index]
 458         if block["type"] == "match":
 459             print("      do {", file=f)
 460             print("        Cell *{} = cell;".format(block["cell"]), file=f)
 461             for expr in block["select"]:
 462                 print("        if (!({})) break;".format(expr), file=f)
 463             print("        index_{}_key_type key;".format(index), file=f)
 464             for field, entry in enumerate(block["index"]):
 465                 print("        std::get<{}>(key) = {};".format(field, entry[1]), file=f)
 466             print("        index_{}[key].push_back(cell);".format(index), file=f)
 467             print("      } while (0);", file=f)
 468
 469     print("    }", file=f)
 470     print("  }", file=f)
 471     print("", file=f)
 472
 473     print("  ~{}_pm() {{".format(prefix), file=f)
 474     print("    for (auto cell : autoremove_cells)", file=f)
 475     print("      module->remove(cell);", file=f)
 476     print("  }", file=f)
 477     print("", file=f)
 478
 479     for current_pattern in sorted(patterns.keys()):
 480         print("  int run_{}(std::function<void()> on_accept_f) {{".format(current_pattern), file=f)
 481         print("    accept_cnt = 0;", file=f)
 482         print("    on_accept = on_accept_f;", file=f)
 483         print("    rollback = 0;", file=f)
 484         print("    blacklist_dirty = false;", file=f)
 485         for s, t in sorted(state_types[current_pattern].items()):
 486             if t.endswith("*"):
 487                 print("    st_{}.{} = nullptr;".format(current_pattern, s), file=f)
 488             else:
 489                 print("    st_{}.{} = {}();".format(current_pattern, s, t), file=f)
 490         print("    block_{}(1);".format(patterns[current_pattern]), file=f)
 491         print("    log_assert(rollback_stack.empty());", file=f)
 492         print("    return accept_cnt;", file=f)
 493         print("  }", file=f)
 494         print("", file=f)
 495         print("  int run_{}(std::function<void({}_pm&)> on_accept_f) {{".format(current_pattern, prefix), file=f)
 496         print("    return run_{}([&](){{on_accept_f(*this);}});".format(current_pattern), file=f)
 497         print("  }", file=f)
 498         print("", file=f)
 499         print("  int run_{}() {{".format(current_pattern), file=f)
 500         print("    return run_{}([](){{}});".format(current_pattern, current_pattern), file=f)
 501         print("  }", file=f)
 502         print("", file=f)
 503
 504     if len(subpatterns):
 505         for p, s in sorted(subpatterns.keys()):
 506             print("  void block_subpattern_{}_{}(int recursion) {{ block_{}(recursion); }}".format(p, s, subpatterns[(p, s)]), file=f)
 507         print("", file=f)
 508
 509     current_pattern = None
 510     current_subpattern = None
 511
 512     for index in range(len(blocks)):
 513         block = blocks[index]
 514
 515         if block["type"] in ("match", "code"):
 516             print("  // {}".format(block["src"]), file=f)
 517
 518         print("  void block_{}(int recursion YS_ATTRIBUTE(unused)) {{".format(index), file=f)
 519         current_pattern, current_subpattern = block["pattern"]
 520
 521         if block["type"] == "final":
 522             print("  }", file=f)
 523             if index+1 != len(blocks):
 524                 print("", file=f)
 525             continue
 526
 527         const_st = set()
 528         nonconst_st = set()
 529         restore_st = set()
 530
 531         for s in subpattern_args[(current_pattern, current_subpattern)]:
 532             const_st.add(s)
 533
 534         for i in range(subpatterns[(current_pattern, current_subpattern)], index):
 535             if blocks[i]["type"] == "code":
 536                 for s in blocks[i]["states"]:
 537                     const_st.add(s)
 538             elif blocks[i]["type"] == "match":
 539                 const_st.add(blocks[i]["cell"])
 540             else:
 541                 assert False
 542
 543         if block["type"] == "code":
 544             for s in block["states"]:
 545                 if s in const_st:
 546                     const_st.remove(s)
 547                     restore_st.add(s)
 548                 nonconst_st.add(s)
 549         elif block["type"] == "match":
 550             s = block["cell"]
 551             assert s not in const_st
 552             nonconst_st.add(s)
 553         else:
 554             assert False
 555
 556         for s in sorted(const_st):
 557             t = state_types[current_pattern][s]
 558             if t.endswith("*"):
 559                 print("    {} const &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 560             else:
 561                 print("    const {} &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 562
 563         for s in sorted(nonconst_st):
 564             t = state_types[current_pattern][s]
 565             print("    {} &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 566
 567         for u in sorted(udata_types[current_pattern].keys()):
 568             t = udata_types[current_pattern][u]
 569             print("    {} &{} YS_ATTRIBUTE(unused) = ud_{}.{};".format(t, u, current_pattern, u), file=f)
 570
 571         if len(restore_st):
 572             print("", file=f)
 573             for s in sorted(restore_st):
 574                 t = state_types[current_pattern][s]
 575                 print("    {} backup_{} = {};".format(t, s, s), file=f)
 576
 577         if block["type"] == "code":
 578             print("", file=f)
 579             print("#define reject do { check_blacklist(); goto rollback_label; } while(0)", file=f)
 580             print("#define accept do { accept_cnt++; on_accept(); check_blacklist(); if (rollback) goto rollback_label; } while(0)", file=f)
 581             print("#define finish do { rollback = -1; rollback_stack.clean(); goto rollback_label; } while(0)", file=f)
 582             print("#define branch do {{ block_{}(recursion+1); if (rollback) goto rollback_label; }} while(0)".format(index+1), file=f)
 583             print("#define subpattern(pattern_name) do {{ block_subpattern_{}_ ## pattern_name (recursion+1); if (rollback) goto rollback_label; }} while(0)".format(current_pattern), file=f)
 584
 585             for line in block["code"]:
 586                 print("  " + line, file=f)
 587
 588             print("", file=f)
 589             print("    block_{}(recursion+1);".format(index+1), file=f)
 590
 591             print("#undef reject", file=f)
 592             print("#undef accept", file=f)
 593             print("#undef finish", file=f)
 594             print("#undef branch", file=f)
 595             print("#undef subpattern", file=f)
 596
 597             print("", file=f)
 598             print("rollback_label:", file=f)
 599             print("    YS_ATTRIBUTE(unused);", file=f)
 600
 601             if len(block["fcode"]):
 602                 print("#define accept do { accept_cnt++; on_accept(); check_blacklist(); } while(0)", file=f)
 603                 print("#define finish do { rollback = -1; rollback_stack.clean(); return; } while(0)", file=f)
 604                 for line in block["fcode"]:
 605                     print("  " + line, file=f)
 606                 print("#undef accept", file=f)
 607                 print("#undef finish", file=f)
 608
 609             if len(restore_st) or len(nonconst_st):
 610                 print("", file=f)
 611                 for s in sorted(restore_st):
 612                     t = state_types[current_pattern][s]
 613                     print("    {} = backup_{};".format(s, s), file=f)
 614                 for s in sorted(nonconst_st):
 615                     if s not in restore_st:
 616                         t = state_types[current_pattern][s]
 617                         if t.endswith("*"):
 618                             print("    {} = nullptr;".format(s), file=f)
 619                         else:
 620                             print("    {} = {}();".format(s, t), file=f)
 621
 622         elif block["type"] == "match":
 623             assert len(restore_st) == 0
 624
 625             print("    Cell* backup_{} = {};".format(block["cell"], block["cell"]), file=f)
 626
 627             if len(block["if"]):
 628                 for expr in block["if"]:
 629                     print("", file=f)
 630                     print("    if (!({})) {{".format(expr), file=f)
 631                     print("      {} = nullptr;".format(block["cell"]), file=f)
 632                     print("      block_{}(recursion+1);".format(index+1), file=f)
 633                     print("      {} = backup_{};".format(block["cell"], block["cell"]), file=f)
 634                     print("      return;", file=f)
 635                     print("    }", file=f)
 636
 637             print("", file=f)
 638             print("    index_{}_key_type key;".format(index), file=f)
 639             for field, entry in enumerate(block["index"]):
 640                 print("    std::get<{}>(key) = {};".format(field, entry[2]), file=f)
 641             print("    auto cells_ptr = index_{}.find(key);".format(index), file=f)
 642
 643             if block["semioptional"] or block["genargs"] is not None:
 644                 print("    bool found_any_match = false;", file=f)
 645
 646             print("", file=f)
 647             print("    if (cells_ptr != index_{}.end()) {{".format(index), file=f)
 648             print("      const vector<Cell*> &cells = cells_ptr->second;".format(index), file=f)
 649             print("      for (int idx = 0; idx < GetSize(cells); idx++) {", file=f)
 650             print("        {} = cells[idx];".format(block["cell"]), file=f)
 651             print("        if (blacklist_cells.count({})) continue;".format(block["cell"]), file=f)
 652             for expr in block["filter"]:
 653                 print("        if (!({})) continue;".format(expr), file=f)
 654             if block["semioptional"] or block["genargs"] is not None:
 655                 print("        found_any_match = true;", file=f)
 656             print("        rollback_stack.push_back(make_pair(cells[idx], recursion));", file=f)
 657             print("        block_{}(recursion+1);".format(index+1), file=f)
 658             print("        if (rollback == 0) {", file=f)
 659             print("          rollback_stack.pop_back();", file=f)
 660             print("        } else {", file=f)
 661             print("          if (rollback != recursion) {{".format(index+1), file=f)
 662             print("            {} = backup_{};".format(block["cell"], block["cell"]), file=f)
 663             print("            return;", file=f)
 664             print("          }", file=f)
 665             print("          rollback = 0;", file=f)
 666             print("        }", file=f)
 667             print("      }", file=f)
 668             print("    }", file=f)
 669
 670             print("", file=f)
 671             print("    {} = nullptr;".format(block["cell"]), file=f)
 672
 673             if block["optional"]:
 674                 print("    block_{}(recursion+1);".format(index+1), file=f)
 675
 676             if block["semioptional"]:
 677                 print("    if (!found_any_match) block_{}(recursion+1);".format(index+1), file=f)
 678
 679             print("    {} = backup_{};".format(block["cell"], block["cell"]), file=f)
 680
 681             if block["genargs"] is not None:
 682                 print("#define finish do { rollback = -1; rollback_stack.clean(); return; } while(0)", file=f)
 683                 print("    if (generate_mode && !found_any_match) {", file=f)
 684                 if len(block["genargs"]) == 1:
 685                     print("    if (rng(100) >= {}) return;".format(block["genargs"][0]), file=f)
 686                 for line in block["gencode"]:
 687                     print("      " + line, file=f)
 688                 print("    }", file=f)
 689                 print("#undef finish", file=f)
 690         else:
 691             assert False
 692
 693         current_pattern = None
 694         print("  }", file=f)
 695         print("", file=f)
 696
 697     print("};", file=f)
 698
 699     if genhdr:
 700         print("", file=f)
 701         print("YOSYS_NAMESPACE_END", file=f)