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                 assert False
 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                 assert s in state_types[current_pattern]
 309                 block["states"].add(s)
 310
 311             codetype = "code"
 312
 313             while True:
 314                 linenr += 1
 315                 l = f.readline()
 316                 assert l != ""
 317                 a = l.split()
 318                 if len(a) == 0: continue
 319                 if a[0] == "endcode": break
 320
 321                 if a[0] == "finally":
 322                     codetype = "fcode"
 323                     continue
 324
 325                 block[codetype].append(rewrite_cpp(l.rstrip()))
 326
 327             blocks.append(block)
 328             continue
 329
 330         assert False
 331
 332 for fn in pmgfiles:
 333     with open(fn, "r") as f:
 334         process_pmgfile(f, fn)
 335
 336 if current_pattern is not None:
 337     block = dict()
 338     block["type"] = "final"
 339     block["pattern"] = (current_pattern, current_subpattern)
 340     blocks.append(block)
 341
 342 current_pattern = None
 343 current_subpattern = None
 344
 345 if debug:
 346     pp.pprint(blocks)
 347
 348 with open(outfile, "w") as f:
 349     for fn in pmgfiles:
 350         print("// Generated by pmgen.py from {}".format(fn), file=f)
 351     print("", file=f)
 352
 353     if genhdr:
 354         print("#include \"kernel/yosys.h\"", file=f)
 355         print("#include \"kernel/sigtools.h\"", file=f)
 356         print("", file=f)
 357         print("YOSYS_NAMESPACE_BEGIN", file=f)
 358         print("", file=f)
 359
 360     print("struct {}_pm {{".format(prefix), file=f)
 361     print("  Module *module;", file=f)
 362     print("  SigMap sigmap;", file=f)
 363     print("  std::function<void()> on_accept;", file=f)
 364     print("  bool generate_mode;", file=f)
 365     print("  int accept_cnt;", file=f)
 366     print("", file=f)
 367
 368     print("  uint32_t rngseed;", file=f)
 369     print("  int rng(unsigned int n) {", file=f)
 370     print("    rngseed ^= rngseed << 13;", file=f)
 371     print("    rngseed ^= rngseed >> 17;", file=f)
 372     print("    rngseed ^= rngseed << 5;", file=f)
 373     print("    return rngseed % n;", file=f)
 374     print("  }", file=f)
 375     print("", file=f)
 376
 377     for index in range(len(blocks)):
 378         block = blocks[index]
 379         if block["type"] == "match":
 380             index_types = list()
 381             for entry in block["index"]:
 382                 index_types.append(entry[0])
 383             value_types = ["Cell*"]
 384             for entry in block["setup"]:
 385                 if entry[0] == "slice":
 386                     value_types.append("int")
 387                 if entry[0] == "choice":
 388                     value_types.append(entry[1])
 389                 if entry[0] == "define":
 390                     value_types.append(entry[1])
 391             print("  typedef std::tuple<{}> index_{}_key_type;".format(", ".join(index_types), index), file=f)
 392             print("  typedef std::tuple<{}> index_{}_value_type;".format(", ".join(value_types), index), file=f)
 393             print("  dict<index_{}_key_type, vector<index_{}_value_type>> index_{};".format(index, index, index), file=f)
 394     print("  dict<SigBit, pool<Cell*>> sigusers;", file=f)
 395     print("  pool<Cell*> blacklist_cells;", file=f)
 396     print("  pool<Cell*> autoremove_cells;", file=f)
 397     print("  dict<Cell*,int> rollback_cache;", file=f)
 398     print("  int rollback;", file=f)
 399     print("", file=f)
 400
 401     for current_pattern in sorted(patterns.keys()):
 402         print("  struct state_{}_t {{".format(current_pattern), file=f)
 403         for s, t in sorted(state_types[current_pattern].items()):
 404             print("    {} {};".format(t, s), file=f)
 405         print("  }} st_{};".format(current_pattern), file=f)
 406         print("", file=f)
 407
 408         print("  struct udata_{}_t {{".format(current_pattern), file=f)
 409         for s, t in sorted(udata_types[current_pattern].items()):
 410             print("    {} {};".format(t, s), file=f)
 411         print("  }} ud_{};".format(current_pattern), file=f)
 412         print("", file=f)
 413     current_pattern = None
 414
 415     for v, n in sorted(ids.items()):
 416         if n[0] == "\\":
 417             print("  IdString {}{{\"\\{}\"}};".format(v, n), file=f)
 418         else:
 419             print("  IdString {}{{\"{}\"}};".format(v, n), file=f)
 420     print("", file=f)
 421
 422     print("  void add_siguser(const SigSpec &sig, Cell *cell) {", file=f)
 423     print("    for (auto bit : sigmap(sig)) {", file=f)
 424     print("      if (bit.wire == nullptr) continue;", file=f)
 425     print("      sigusers[bit].insert(cell);", file=f)
 426     print("    }", file=f)
 427     print("  }", file=f)
 428     print("", file=f)
 429
 430     print("  void blacklist(Cell *cell) {", file=f)
 431     print("    if (cell != nullptr && blacklist_cells.insert(cell).second) {", file=f)
 432     print("      auto ptr = rollback_cache.find(cell);", file=f)
 433     print("      if (ptr == rollback_cache.end()) return;", file=f)
 434     print("      int rb = ptr->second;", file=f)
 435     print("      if (rollback == 0 || rollback > rb)", file=f)
 436     print("        rollback = rb;", file=f)
 437     print("    }", file=f)
 438     print("  }", file=f)
 439     print("", file=f)
 440
 441     print("  void autoremove(Cell *cell) {", file=f)
 442     print("    if (cell != nullptr) {", file=f)
 443     print("      autoremove_cells.insert(cell);", file=f)
 444     print("      blacklist(cell);", file=f)
 445     print("    }", file=f)
 446     print("  }", file=f)
 447     print("", file=f)
 448
 449     current_pattern = None
 450
 451     print("  SigSpec port(Cell *cell, IdString portname) {", file=f)
 452     print("    return sigmap(cell->getPort(portname));", file=f)
 453     print("  }", file=f)
 454     print("", file=f)
 455
 456     print("  Const param(Cell *cell, IdString paramname) {", file=f)
 457     print("    return cell->getParam(paramname);", file=f)
 458     print("  }", file=f)
 459     print("", file=f)
 460
 461     print("  int nusers(const SigSpec &sig) {", file=f)
 462     print("    pool<Cell*> users;", file=f)
 463     print("    for (auto bit : sigmap(sig))", file=f)
 464     print("      for (auto user : sigusers[bit])", file=f)
 465     print("        users.insert(user);", file=f)
 466     print("    return GetSize(users);", file=f)
 467     print("  }", file=f)
 468     print("", file=f)
 469
 470     print("  {}_pm(Module *module, const vector<Cell*> &cells) :".format(prefix), file=f)
 471     print("      module(module), sigmap(module), generate_mode(false), rngseed(12345678) {", file=f)
 472     for current_pattern in sorted(patterns.keys()):
 473         for s, t in sorted(udata_types[current_pattern].items()):
 474             if t.endswith("*"):
 475                 print("    ud_{}.{} = nullptr;".format(current_pattern,s), file=f)
 476             else:
 477                 print("    ud_{}.{} = {}();".format(current_pattern, s, t), file=f)
 478     current_pattern = None
 479     print("    for (auto port : module->ports)", file=f)
 480     print("      add_siguser(module->wire(port), nullptr);", file=f)
 481     print("    for (auto cell : module->cells())", file=f)
 482     print("      for (auto &conn : cell->connections())", file=f)
 483     print("        add_siguser(conn.second, cell);", file=f)
 484     print("    for (auto cell : cells) {", file=f)
 485
 486     for index in range(len(blocks)):
 487         block = blocks[index]
 488         if block["type"] == "match":
 489             print("      do {", file=f)
 490             print("        Cell *{} = cell;".format(block["cell"]), file=f)
 491             print("        index_{}_value_type value;".format(index), file=f)
 492             print("        std::get<0>(value) = cell;", file=f)
 493             loopcnt = 0
 494             valueidx = 1
 495             for item in block["setup"]:
 496                 if item[0] == "select":
 497                     print("        if (!({})) continue;".format(item[1]), file=f)
 498                 if item[0] == "slice":
 499                     print("        int &{} = std::get<{}>(value);".format(item[1], valueidx), file=f)
 500                     print("        for ({} = 0; {} < {}; {}++) {{".format(item[1], item[1], item[2], item[1]), file=f)
 501                     valueidx += 1
 502                     loopcnt += 1
 503                 if item[0] == "choice":
 504                     print("        vector<{}> _pmg_choices_{} = {};".format(item[1], item[2], item[3]), file=f)
 505                     print("        for (const {} &{} : _pmg_choices_{}) {{".format(item[1], item[2], item[2]), file=f)
 506                     print("        std::get<{}>(value) = {};".format(valueidx, item[2]), file=f)
 507                     valueidx += 1
 508                     loopcnt += 1
 509                 if item[0] == "define":
 510                     print("        {} &{} = std::get<{}>(value);".format(item[1], item[2], valueidx), file=f)
 511                     print("        {} = {};".format(item[2], item[3]), file=f)
 512                     valueidx += 1
 513             print("        index_{}_key_type key;".format(index), file=f)
 514             for field, entry in enumerate(block["index"]):
 515                 print("        std::get<{}>(key) = {};".format(field, entry[1]), file=f)
 516             print("        index_{}[key].push_back(value);".format(index), file=f)
 517             for i in range(loopcnt):
 518                 print("        }", file=f)
 519             print("      } while (0);", file=f)
 520
 521     print("    }", file=f)
 522     print("  }", file=f)
 523     print("", file=f)
 524
 525     print("  ~{}_pm() {{".format(prefix), file=f)
 526     print("    for (auto cell : autoremove_cells)", file=f)
 527     print("      module->remove(cell);", file=f)
 528     print("  }", file=f)
 529     print("", file=f)
 530
 531     for current_pattern in sorted(patterns.keys()):
 532         print("  int run_{}(std::function<void()> on_accept_f) {{".format(current_pattern), file=f)
 533         print("    accept_cnt = 0;", file=f)
 534         print("    on_accept = on_accept_f;", file=f)
 535         print("    rollback = 0;", file=f)
 536         for s, t in sorted(state_types[current_pattern].items()):
 537             if t.endswith("*"):
 538                 print("    st_{}.{} = nullptr;".format(current_pattern, s), file=f)
 539             else:
 540                 print("    st_{}.{} = {}();".format(current_pattern, s, t), file=f)
 541         print("    block_{}(1);".format(patterns[current_pattern]), file=f)
 542         print("    log_assert(rollback_cache.empty());", file=f)
 543         print("    return accept_cnt;", file=f)
 544         print("  }", file=f)
 545         print("", file=f)
 546         print("  int run_{}(std::function<void({}_pm&)> on_accept_f) {{".format(current_pattern, prefix), file=f)
 547         print("    return run_{}([&](){{on_accept_f(*this);}});".format(current_pattern), file=f)
 548         print("  }", file=f)
 549         print("", file=f)
 550         print("  int run_{}() {{".format(current_pattern), file=f)
 551         print("    return run_{}([](){{}});".format(current_pattern, current_pattern), file=f)
 552         print("  }", file=f)
 553         print("", file=f)
 554
 555     if len(subpatterns):
 556         for p, s in sorted(subpatterns.keys()):
 557             print("  void block_subpattern_{}_{}(int recursion) {{ block_{}(recursion); }}".format(p, s, subpatterns[(p, s)]), file=f)
 558         print("", file=f)
 559
 560     current_pattern = None
 561     current_subpattern = None
 562
 563     for index in range(len(blocks)):
 564         block = blocks[index]
 565
 566         if block["type"] in ("match", "code"):
 567             print("  // {}".format(block["src"]), file=f)
 568
 569         print("  void block_{}(int recursion YS_ATTRIBUTE(unused)) {{".format(index), file=f)
 570         current_pattern, current_subpattern = block["pattern"]
 571
 572         if block["type"] == "final":
 573             print("  }", file=f)
 574             if index+1 != len(blocks):
 575                 print("", file=f)
 576             continue
 577
 578         const_st = set()
 579         nonconst_st = set()
 580         restore_st = set()
 581
 582         for s in subpattern_args[(current_pattern, current_subpattern)]:
 583             const_st.add(s)
 584
 585         for i in range(subpatterns[(current_pattern, current_subpattern)], index):
 586             if blocks[i]["type"] == "code":
 587                 for s in blocks[i]["states"]:
 588                     const_st.add(s)
 589             elif blocks[i]["type"] == "match":
 590                 const_st.add(blocks[i]["cell"])
 591                 for item in blocks[i]["sets"]:
 592                     const_st.add(item[0])
 593             else:
 594                 assert False
 595
 596         if block["type"] == "code":
 597             for s in block["states"]:
 598                 if s in const_st:
 599                     const_st.remove(s)
 600                     restore_st.add(s)
 601                 nonconst_st.add(s)
 602         elif block["type"] == "match":
 603             s = block["cell"]
 604             assert s not in const_st
 605             nonconst_st.add(s)
 606             for item in block["sets"]:
 607                 if item[0] in const_st:
 608                     const_st.remove(item[0])
 609                 nonconst_st.add(item[0])
 610         else:
 611             assert False
 612
 613         for s in sorted(const_st):
 614             t = state_types[current_pattern][s]
 615             if t.endswith("*"):
 616                 print("    {} const &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 617             else:
 618                 print("    const {} &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 619
 620         for s in sorted(nonconst_st):
 621             t = state_types[current_pattern][s]
 622             print("    {} &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 623
 624         for u in sorted(udata_types[current_pattern].keys()):
 625             t = udata_types[current_pattern][u]
 626             print("    {} &{} YS_ATTRIBUTE(unused) = ud_{}.{};".format(t, u, current_pattern, u), file=f)
 627
 628         if len(restore_st):
 629             print("", file=f)
 630             for s in sorted(restore_st):
 631                 t = state_types[current_pattern][s]
 632                 print("    {} _pmg_backup_{} = {};".format(t, s, s), file=f)
 633
 634         if block["type"] == "code":
 635             print("", file=f)
 636             print("#define reject do { goto rollback_label; } while(0)", file=f)
 637             print("#define accept do { accept_cnt++; on_accept(); if (rollback) goto rollback_label; } while(0)", file=f)
 638             print("#define finish do { rollback = -1; goto rollback_label; } while(0)", file=f)
 639             print("#define branch do {{ block_{}(recursion+1); if (rollback) goto rollback_label; }} while(0)".format(index+1), file=f)
 640             print("#define subpattern(pattern_name) do {{ block_subpattern_{}_ ## pattern_name (recursion+1); if (rollback) goto rollback_label; }} while(0)".format(current_pattern), file=f)
 641
 642             for line in block["code"]:
 643                 print("  " + line, file=f)
 644
 645             print("", file=f)
 646             print("    block_{}(recursion+1);".format(index+1), file=f)
 647
 648             print("#undef reject", file=f)
 649             print("#undef accept", file=f)
 650             print("#undef finish", file=f)
 651             print("#undef branch", file=f)
 652             print("#undef subpattern", file=f)
 653
 654             print("", file=f)
 655             print("rollback_label:", file=f)
 656             print("    YS_ATTRIBUTE(unused);", file=f)
 657
 658             if len(block["fcode"]):
 659                 print("#define accept do { accept_cnt++; on_accept(); } while(0)", file=f)
 660                 print("#define finish do { rollback = -1; goto finish_label; } while(0)", file=f)
 661                 for line in block["fcode"]:
 662                     print("  " + line, file=f)
 663                 print("finish_label:", file=f)
 664                 print("    YS_ATTRIBUTE(unused);", file=f)
 665                 print("#undef accept", file=f)
 666                 print("#undef finish", file=f)
 667
 668             if len(restore_st) or len(nonconst_st):
 669                 print("", file=f)
 670                 for s in sorted(restore_st):
 671                     t = state_types[current_pattern][s]
 672                     print("    {} = _pmg_backup_{};".format(s, s), file=f)
 673                 for s in sorted(nonconst_st):
 674                     if s not in restore_st:
 675                         t = state_types[current_pattern][s]
 676                         if t.endswith("*"):
 677                             print("    {} = nullptr;".format(s), file=f)
 678                         else:
 679                             print("    {} = {}();".format(s, t), file=f)
 680
 681         elif block["type"] == "match":
 682             assert len(restore_st) == 0
 683
 684             print("    Cell* _pmg_backup_{} = {};".format(block["cell"], block["cell"]), file=f)
 685
 686             if len(block["if"]):
 687                 for expr in block["if"]:
 688                     print("", file=f)
 689                     print("    if (!({})) {{".format(expr), file=f)
 690                     print("      {} = nullptr;".format(block["cell"]), file=f)
 691                     print("      block_{}(recursion+1);".format(index+1), file=f)
 692                     print("      {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f)
 693                     print("      return;", file=f)
 694                     print("    }", file=f)
 695
 696             print("", file=f)
 697             print("    index_{}_key_type key;".format(index), file=f)
 698             for field, entry in enumerate(block["index"]):
 699                 print("    std::get<{}>(key) = {};".format(field, entry[2]), file=f)
 700             print("    auto cells_ptr = index_{}.find(key);".format(index), file=f)
 701
 702             if block["semioptional"] or block["genargs"] is not None:
 703                 print("    bool found_any_match = false;", file=f)
 704
 705             print("", file=f)
 706             print("    if (cells_ptr != index_{}.end()) {{".format(index), file=f)
 707             print("      const vector<index_{}_value_type> &cells = cells_ptr->second;".format(index), file=f)
 708             print("      for (int _pmg_idx = 0; _pmg_idx < GetSize(cells); _pmg_idx++) {", file=f)
 709             print("        {} = std::get<0>(cells[_pmg_idx]);".format(block["cell"]), file=f)
 710             valueidx = 1
 711             for item in block["setup"]:
 712                 if item[0] == "slice":
 713                     print("        const int &{} YS_ATTRIBUTE(unused) = std::get<{}>(cells[_pmg_idx]);".format(item[1], valueidx), file=f)
 714                     valueidx += 1
 715                 if item[0] == "choice":
 716                     print("        const {} &{} YS_ATTRIBUTE(unused) = std::get<{}>(cells[_pmg_idx]);".format(item[1], item[2], valueidx), file=f)
 717                     valueidx += 1
 718                 if item[0] == "define":
 719                     print("        const {} &{} YS_ATTRIBUTE(unused) = std::get<{}>(cells[_pmg_idx]);".format(item[1], item[2], valueidx), file=f)
 720                     valueidx += 1
 721             print("        if (blacklist_cells.count({})) continue;".format(block["cell"]), file=f)
 722             for expr in block["filter"]:
 723                 print("        if (!({})) continue;".format(expr), file=f)
 724             if block["semioptional"] or block["genargs"] is not None:
 725                 print("        found_any_match = true;", file=f)
 726             for item in block["sets"]:
 727                 print("        auto _pmg_backup_{} = {};".format(item[0], item[0]), file=f)
 728                 print("        {} = {};".format(item[0], item[1]), file=f)
 729             print("        auto rollback_ptr = rollback_cache.insert(make_pair(std::get<0>(cells[_pmg_idx]), recursion));", file=f)
 730             print("        block_{}(recursion+1);".format(index+1), file=f)
 731             for item in block["sets"]:
 732                 print("        {} = _pmg_backup_{};".format(item[0], item[0]), file=f)
 733             print("        if (rollback_ptr.second)", file=f)
 734             print("          rollback_cache.erase(rollback_ptr.first);", file=f)
 735             print("        if (rollback) {", file=f)
 736             print("          if (rollback != recursion) {{".format(index+1), file=f)
 737             print("            {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f)
 738             print("            return;", file=f)
 739             print("          }", file=f)
 740             print("          rollback = 0;", file=f)
 741             print("        }", file=f)
 742             print("      }", file=f)
 743             print("    }", file=f)
 744
 745             print("", file=f)
 746             print("    {} = nullptr;".format(block["cell"]), file=f)
 747
 748             if block["optional"]:
 749                 print("    block_{}(recursion+1);".format(index+1), file=f)
 750
 751             if block["semioptional"]:
 752                 print("    if (!found_any_match) block_{}(recursion+1);".format(index+1), file=f)
 753
 754             print("    {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f)
 755
 756             if block["genargs"] is not None:
 757                 print("#define finish do { rollback = -1; return; } while(0)", file=f)
 758                 print("    if (generate_mode && rng(100) < (found_any_match ? {} : {})) {{".format(block["genargs"][1], block["genargs"][0]), file=f)
 759                 for line in block["gencode"]:
 760                     print("      " + line, file=f)
 761                 print("    }", file=f)
 762                 print("#undef finish", file=f)
 763         else:
 764             assert False
 765
 766         current_pattern = None
 767         print("  }", file=f)
 768         print("", file=f)
 769
 770     print("};", file=f)
 771
 772     if genhdr:
 773         print("", file=f)
 774         print("YOSYS_NAMESPACE_END", file=f)