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 patterns = dict()
  42 state_types = dict()
  43 udata_types = dict()
  44 blocks = list()
  45 ids = dict()
  46
  47 def rewrite_cpp(s):
  48     t = list()
  49     i = 0
  50     while i < len(s):
  51         if s[i] in ("'", '"') and i + 1 < len(s):
  52             j = i + 1
  53             while j + 1 < len(s) and s[j] != s[i]:
  54                 if s[j] == '\\' and j + 1 < len(s):
  55                     j += 1
  56                 j += 1
  57             t.append(s[i:j+1])
  58             i = j + 1
  59             continue
  60
  61         if s[i] in ('$', '\\') and i + 1 < len(s):
  62             j = i + 1
  63             while True:
  64                 if j == len(s):
  65                     j -= 1
  66                     break
  67                 if ord('a') <= ord(s[j]) <= ord('z'):
  68                     j += 1
  69                     continue
  70                 if ord('A') <= ord(s[j]) <= ord('Z'):
  71                     j += 1
  72                     continue
  73                 if ord('0') <= ord(s[j]) <= ord('9'):
  74                     j += 1
  75                     continue
  76                 if s[j] == '_':
  77                     j += 1
  78                     continue
  79                 j -= 1
  80                 break
  81
  82             n = s[i:j+1]
  83             i = j + 1
  84
  85             if n[0] == '$':
  86                 v = "id_d_" + n[1:]
  87             else:
  88                 v = "id_b_" + n[1:]
  89
  90             if v not in ids:
  91                 ids[v] = n
  92             else:
  93                 assert ids[v] == n
  94
  95             t.append(v)
  96             continue
  97
  98         if s[i] == "\t":
  99             t.append("  ")
 100         else:
 101             t.append(s[i])
 102
 103         i += 1
 104
 105     return "".join(t)
 106
 107 def process_pmgfile(f):
 108     global current_pattern
 109     while True:
 110         line = f.readline()
 111         if line == "": break
 112         line = line.strip()
 113
 114         cmd = line.split()
 115         if len(cmd) == 0 or cmd[0].startswith("//"): continue
 116         cmd = cmd[0]
 117
 118         if cmd == "pattern":
 119             if current_pattern is not None:
 120                 block = dict()
 121                 block["type"] = "final"
 122                 block["pattern"] = current_pattern
 123                 blocks.append(block)
 124             line = line.split()
 125             assert len(line) == 2
 126             assert line[1] not in patterns
 127             current_pattern = line[1]
 128             patterns[current_pattern] = len(blocks)
 129             state_types[current_pattern] = dict()
 130             udata_types[current_pattern] = dict()
 131             continue
 132
 133         assert current_pattern is not None
 134
 135         if cmd == "state":
 136             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)
 137             assert m
 138             type_str = m.group(1)
 139             states_str = m.group(2)
 140             for s in re.split(r"\s+", states_str):
 141                 assert s not in state_types[current_pattern]
 142                 state_types[current_pattern][s] = type_str
 143             continue
 144
 145         if cmd == "udata":
 146             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)
 147             assert m
 148             type_str = m.group(1)
 149             udatas_str = m.group(2)
 150             for s in re.split(r"\s+", udatas_str):
 151                 assert s not in udata_types[current_pattern]
 152                 udata_types[current_pattern][s] = type_str
 153             continue
 154
 155         if cmd == "match":
 156             block = dict()
 157             block["type"] = "match"
 158             block["pattern"] = current_pattern
 159
 160             line = line.split()
 161             assert len(line) == 2
 162             assert line[1] not in state_types[current_pattern]
 163             block["cell"] = line[1]
 164             state_types[current_pattern][line[1]] = "Cell*";
 165
 166             block["if"] = list()
 167             block["select"] = list()
 168             block["index"] = list()
 169             block["filter"] = list()
 170             block["optional"] = False
 171
 172             while True:
 173                 l = f.readline()
 174                 assert l != ""
 175                 a = l.split()
 176                 if len(a) == 0 or a[0].startswith("//"): continue
 177                 if a[0] == "endmatch": break
 178
 179                 if a[0] == "if":
 180                     b = l.lstrip()[2:]
 181                     block["if"].append(rewrite_cpp(b.strip()))
 182                     continue
 183
 184                 if a[0] == "select":
 185                     b = l.lstrip()[6:]
 186                     block["select"].append(rewrite_cpp(b.strip()))
 187                     continue
 188
 189                 if a[0] == "index":
 190                     m = re.match(r"^\s*index\s+<(.*?)>\s+(.*?)\s*===\s*(.*?)\s*$", l)
 191                     assert m
 192                     block["index"].append((m.group(1), rewrite_cpp(m.group(2)), rewrite_cpp(m.group(3))))
 193                     continue
 194
 195                 if a[0] == "filter":
 196                     b = l.lstrip()[6:]
 197                     block["filter"].append(rewrite_cpp(b.strip()))
 198                     continue
 199
 200                 if a[0] == "optional":
 201                     block["optional"] = True
 202                     continue
 203
 204                 assert False
 205
 206             blocks.append(block)
 207             continue
 208
 209         if cmd == "code":
 210             block = dict()
 211             block["type"] = "code"
 212             block["pattern"] = current_pattern
 213
 214             block["code"] = list()
 215             block["states"] = set()
 216
 217             for s in line.split()[1:]:
 218                 assert s in state_types[current_pattern]
 219                 block["states"].add(s)
 220
 221             while True:
 222                 l = f.readline()
 223                 assert l != ""
 224                 a = l.split()
 225                 if len(a) == 0: continue
 226                 if a[0] == "endcode": break
 227
 228                 block["code"].append(rewrite_cpp(l.rstrip()))
 229
 230             blocks.append(block)
 231             continue
 232
 233         assert False
 234
 235 for fn in pmgfiles:
 236     with open(fn, "r") as f:
 237         process_pmgfile(f)
 238
 239 if current_pattern is not None:
 240     block = dict()
 241     block["type"] = "final"
 242     block["pattern"] = current_pattern
 243     blocks.append(block)
 244
 245 current_pattern = None
 246
 247 if debug:
 248     pp.pprint(blocks)
 249
 250 with open(outfile, "w") as f:
 251     for fn in pmgfiles:
 252         print("// Generated by pmgen.py from {}".format(fn), file=f)
 253     print("", file=f)
 254
 255     if genhdr:
 256         print("#include \"kernel/yosys.h\"", file=f)
 257         print("#include \"kernel/sigtools.h\"", file=f)
 258         print("", file=f)
 259         print("YOSYS_NAMESPACE_BEGIN", file=f)
 260         print("", file=f)
 261
 262     print("struct {}_pm {{".format(prefix), file=f)
 263     print("  Module *module;", file=f)
 264     print("  SigMap sigmap;", file=f)
 265     print("  std::function<void()> on_accept;".format(prefix), file=f)
 266     print("", file=f)
 267
 268     for index in range(len(blocks)):
 269         block = blocks[index]
 270         if block["type"] == "match":
 271             index_types = list()
 272             for entry in block["index"]:
 273                 index_types.append(entry[0])
 274             print("  typedef std::tuple<{}> index_{}_key_type;".format(", ".join(index_types), index), file=f)
 275             print("  dict<index_{}_key_type, vector<Cell*>> index_{};".format(index, index), file=f)
 276     print("  dict<SigBit, pool<Cell*>> sigusers;", file=f)
 277     print("  pool<Cell*> blacklist_cells;", file=f)
 278     print("  pool<Cell*> autoremove_cells;", file=f)
 279     print("  bool blacklist_dirty;", file=f)
 280     print("  int rollback;", file=f)
 281     print("", file=f)
 282
 283     for current_pattern in sorted(patterns.keys()):
 284         print("  struct state_{}_t {{".format(current_pattern), file=f)
 285         for s, t in sorted(state_types[current_pattern].items()):
 286             print("    {} {};".format(t, s), file=f)
 287         print("  }} st_{};".format(current_pattern), file=f)
 288         print("", file=f)
 289
 290         print("  struct udata_{}_t {{".format(current_pattern), file=f)
 291         for s, t in sorted(udata_types[current_pattern].items()):
 292             print("    {} {};".format(t, s), file=f)
 293         print("  }} ud_{};".format(current_pattern), file=f)
 294         print("", file=f)
 295     current_pattern = None
 296
 297     for v, n in sorted(ids.items()):
 298         if n[0] == "\\":
 299             print("  IdString {}{{\"\\{}\"}};".format(v, n), file=f)
 300         else:
 301             print("  IdString {}{{\"{}\"}};".format(v, n), file=f)
 302     print("", file=f)
 303
 304     print("  void add_siguser(const SigSpec &sig, Cell *cell) {", file=f)
 305     print("    for (auto bit : sigmap(sig)) {", file=f)
 306     print("      if (bit.wire == nullptr) continue;", file=f)
 307     print("      if (sigusers.count(bit) == 0 && bit.wire->port_id)", file=f)
 308     print("        sigusers[bit].insert(nullptr);", file=f)
 309     print("      sigusers[bit].insert(cell);", file=f)
 310     print("    }", file=f)
 311     print("  }", file=f)
 312     print("", file=f)
 313
 314     print("  void blacklist(Cell *cell) {", file=f)
 315     print("    if (cell != nullptr) {", file=f)
 316     print("      if (blacklist_cells.insert(cell).second)", file=f)
 317     print("        blacklist_dirty = true;", file=f)
 318     print("    }", file=f)
 319     print("  }", file=f)
 320     print("", file=f)
 321
 322     print("  void autoremove(Cell *cell) {", file=f)
 323     print("    if (cell != nullptr) {", file=f)
 324     print("      if (blacklist_cells.insert(cell).second)", file=f)
 325     print("        blacklist_dirty = true;", file=f)
 326     print("      autoremove_cells.insert(cell);", file=f)
 327     print("    }", file=f)
 328     print("  }", file=f)
 329     print("", file=f)
 330
 331     for current_pattern in sorted(patterns.keys()):
 332         print("  void check_blacklist_{}() {{".format(current_pattern), file=f)
 333         print("    if (!blacklist_dirty)", file=f)
 334         print("      return;", file=f)
 335         print("    blacklist_dirty = false;", file=f)
 336         for index in range(len(blocks)):
 337             block = blocks[index]
 338             if block["pattern"] != current_pattern:
 339                 continue
 340             if block["type"] == "match":
 341                 print("    if (st_{}.{} != nullptr && blacklist_cells.count(st_{}.{})) {{".format(current_pattern, block["cell"], current_pattern, block["cell"]), file=f)
 342                 print("      rollback = {};".format(index+1), file=f)
 343                 print("      return;", file=f)
 344                 print("    }", file=f)
 345         print("    rollback = 0;", file=f)
 346         print("  }", file=f)
 347         print("", file=f)
 348     current_pattern = None
 349
 350     print("  SigSpec port(Cell *cell, IdString portname) {", file=f)
 351     print("    return sigmap(cell->getPort(portname));", file=f)
 352     print("  }", file=f)
 353     print("", file=f)
 354
 355     print("  Const param(Cell *cell, IdString paramname) {", file=f)
 356     print("    return cell->getParam(paramname);", file=f)
 357     print("  }", file=f)
 358     print("", file=f)
 359
 360     print("  int nusers(const SigSpec &sig) {", file=f)
 361     print("    pool<Cell*> users;", file=f)
 362     print("    for (auto bit : sigmap(sig))", file=f)
 363     print("      for (auto user : sigusers[bit])", file=f)
 364     print("        users.insert(user);", file=f)
 365     print("    return GetSize(users);", file=f)
 366     print("  }", file=f)
 367     print("", file=f)
 368
 369     print("  {}_pm(Module *module, const vector<Cell*> &cells) :".format(prefix), file=f)
 370     print("      module(module), sigmap(module) {", file=f)
 371     for current_pattern in sorted(patterns.keys()):
 372         for s, t in sorted(udata_types[current_pattern].items()):
 373             if t.endswith("*"):
 374                 print("    ud_{}.{} = nullptr;".format(current_pattern,s), file=f)
 375             else:
 376                 print("    ud_{}.{} = {}();".format(current_pattern, s, t), file=f)
 377     current_pattern = None
 378     print("    for (auto cell : module->cells()) {", file=f)
 379     print("      for (auto &conn : cell->connections())", file=f)
 380     print("        add_siguser(conn.second, cell);", file=f)
 381     print("    }", file=f)
 382     print("    for (auto cell : cells) {", file=f)
 383
 384     for index in range(len(blocks)):
 385         block = blocks[index]
 386         if block["type"] == "match":
 387             print("      do {", file=f)
 388             print("        Cell *{} = cell;".format(block["cell"]), file=f)
 389             for expr in block["select"]:
 390                 print("        if (!({})) break;".format(expr), file=f)
 391             print("        index_{}_key_type key;".format(index), file=f)
 392             for field, entry in enumerate(block["index"]):
 393                 print("        std::get<{}>(key) = {};".format(field, entry[1]), file=f)
 394             print("        index_{}[key].push_back(cell);".format(index), file=f)
 395             print("      } while (0);", file=f)
 396
 397     print("    }", file=f)
 398     print("  }", file=f)
 399     print("", file=f)
 400
 401     print("  ~{}_pm() {{".format(prefix), file=f)
 402     print("    for (auto cell : autoremove_cells)", file=f)
 403     print("      module->remove(cell);", file=f)
 404     print("  }", file=f)
 405     print("", file=f)
 406
 407     for current_pattern in sorted(patterns.keys()):
 408         print("  void run_{}(std::function<void()> on_accept_f) {{".format(current_pattern), file=f)
 409         print("    on_accept = on_accept_f;", file=f)
 410         print("    rollback = 0;", file=f)
 411         print("    blacklist_dirty = false;", file=f)
 412         for s, t in sorted(state_types[current_pattern].items()):
 413             if t.endswith("*"):
 414                 print("    st_{}.{} = nullptr;".format(current_pattern, s), file=f)
 415             else:
 416                 print("    st_{}.{} = {}();".format(current_pattern, s, t), file=f)
 417         print("    block_{}();".format(patterns[current_pattern]), file=f)
 418         print("  }", file=f)
 419         print("", file=f)
 420         print("  void run_{}(std::function<void({}_pm&)> on_accept_f) {{".format(current_pattern, prefix), file=f)
 421         print("    run_{}([&](){{on_accept_f(*this);}});".format(current_pattern), file=f)
 422         print("  }", file=f)
 423         print("", file=f)
 424         print("  void run_{}(std::function<void(state_{}_t&)> on_accept_f) {{".format(current_pattern, current_pattern), file=f)
 425         print("    run_{}([&](){{on_accept_f(st_{});}});".format(current_pattern, current_pattern), file=f)
 426         print("  }", file=f)
 427         print("", file=f)
 428         print("  void run_{}() {{".format(current_pattern), file=f)
 429         print("    run_{}([](){{}});".format(current_pattern, current_pattern), file=f)
 430         print("  }", file=f)
 431         print("", file=f)
 432     current_pattern = None
 433
 434     for index in range(len(blocks)):
 435         block = blocks[index]
 436
 437         print("  void block_{}() {{".format(index), file=f)
 438         current_pattern = block["pattern"]
 439
 440         if block["type"] == "final":
 441             print("    on_accept();", file=f)
 442             print("    check_blacklist_{}();".format(current_pattern), file=f)
 443             print("  }", file=f)
 444             if index+1 != len(blocks):
 445                 print("", file=f)
 446             continue
 447
 448         const_st = set()
 449         nonconst_st = set()
 450         restore_st = set()
 451
 452         for i in range(patterns[current_pattern], index):
 453             if blocks[i]["type"] == "code":
 454                 for s in blocks[i]["states"]:
 455                     const_st.add(s)
 456             elif blocks[i]["type"] == "match":
 457                 const_st.add(blocks[i]["cell"])
 458             else:
 459                 assert False
 460
 461         if block["type"] == "code":
 462             for s in block["states"]:
 463                 if s in const_st:
 464                     const_st.remove(s)
 465                     restore_st.add(s)
 466                 nonconst_st.add(s)
 467         elif block["type"] == "match":
 468             s = block["cell"]
 469             assert s not in const_st
 470             nonconst_st.add(s)
 471         else:
 472             assert False
 473
 474         for s in sorted(const_st):
 475             t = state_types[current_pattern][s]
 476             if t.endswith("*"):
 477                 print("    {} const &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 478             else:
 479                 print("    const {} &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 480
 481         for s in sorted(nonconst_st):
 482             t = state_types[current_pattern][s]
 483             print("    {} &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f)
 484
 485         if len(restore_st):
 486             print("", file=f)
 487             for s in sorted(restore_st):
 488                 t = state_types[current_pattern][s]
 489                 print("    {} backup_{} = {};".format(t, s, s), file=f)
 490
 491         if block["type"] == "code":
 492             print("", file=f)
 493             print("    do {", file=f)
 494             print("#define reject do {{ check_blacklist_{}(); goto rollback_label; }} while(0)".format(current_pattern), file=f)
 495             print("#define accept do {{ on_accept(); check_blacklist_{}(); if (rollback) goto rollback_label; }} while(0)".format(current_pattern), file=f)
 496             print("#define branch do {{ block_{}(); if (rollback) goto rollback_label; }} while(0)".format(index+1), file=f)
 497
 498             for line in block["code"]:
 499                 print("    " + line, file=f)
 500
 501             print("", file=f)
 502             print("      block_{}();".format(index+1), file=f)
 503             print("#undef reject", file=f)
 504             print("#undef accept", file=f)
 505             print("#undef branch", file=f)
 506             print("    } while (0);", file=f)
 507             print("", file=f)
 508             print("rollback_label:", file=f)
 509             print("    YS_ATTRIBUTE(unused);", file=f)
 510
 511             if len(restore_st) or len(nonconst_st):
 512                 print("", file=f)
 513                 for s in sorted(restore_st):
 514                     t = state_types[current_pattern][s]
 515                     print("    {} = backup_{};".format(s, s), file=f)
 516                 for s in sorted(nonconst_st):
 517                     if s not in restore_st:
 518                         t = state_types[current_pattern][s]
 519                         if t.endswith("*"):
 520                             print("    {} = nullptr;".format(s), file=f)
 521                         else:
 522                             print("    {} = {}();".format(s, t), file=f)
 523
 524         elif block["type"] == "match":
 525             assert len(restore_st) == 0
 526
 527             if len(block["if"]):
 528                 for expr in block["if"]:
 529                     print("", file=f)
 530                     print("    if (!({})) {{".format(expr), file=f)
 531                     print("      {} = nullptr;".format(block["cell"]), file=f)
 532                     print("      block_{}();".format(index+1), file=f)
 533                     print("      return;", file=f)
 534                     print("    }", file=f)
 535
 536             print("", file=f)
 537             print("    index_{}_key_type key;".format(index), file=f)
 538             for field, entry in enumerate(block["index"]):
 539                 print("    std::get<{}>(key) = {};".format(field, entry[2]), file=f)
 540             print("    const vector<Cell*> &cells = index_{}[key];".format(index), file=f)
 541
 542             print("", file=f)
 543             print("    for (int idx = 0; idx < GetSize(cells); idx++) {", file=f)
 544             print("      {} = cells[idx];".format(block["cell"]), file=f)
 545             print("      if (blacklist_cells.count({})) continue;".format(block["cell"]), file=f)
 546             for expr in block["filter"]:
 547                 print("      if (!({})) continue;".format(expr), file=f)
 548             print("      block_{}();".format(index+1), file=f)
 549             print("      if (rollback) {", file=f)
 550             print("        if (rollback != {}) {{".format(index+1), file=f)
 551             print("          {} = nullptr;".format(block["cell"]), file=f)
 552             print("          return;", file=f)
 553             print("        }", file=f)
 554             print("        rollback = 0;", file=f)
 555             print("      }", file=f)
 556             print("    }", file=f)
 557
 558             print("", file=f)
 559             print("    {} = nullptr;".format(block["cell"]), file=f)
 560
 561             if block["optional"]:
 562                 print("    block_{}();".format(index+1), file=f)
 563
 564         else:
 565             assert False
 566
 567         current_pattern = None
 568         print("  }", file=f)
 569         print("", file=f)
 570
 571     print("};", file=f)
 572
 573     if genhdr:
 574         print("", file=f)
 575         print("YOSYS_NAMESPACE_END", file=f)