diff options
| -rw-r--r-- | CHANGELOG | 1 | ||||
| -rw-r--r-- | passes/pmgen/README.md | 48 | ||||
| -rw-r--r-- | passes/pmgen/pmgen.py | 125 | ||||
| -rw-r--r-- | passes/pmgen/test_pmgen.cc | 53 | ||||
| -rw-r--r-- | passes/pmgen/test_pmgen.pmg | 87 |
5 files changed, 280 insertions, 34 deletions
@@ -27,6 +27,7 @@ Yosys 0.9 .. Yosys 0.9-dev - Added "opt_share" pass, run as part of "opt -full" - Added "ice40_wrapcarry" to encapsulate SB_LUT+SB_CARRY pairs for techmapping - Removed "ice40_unlut" + - Improvements in pmgen: slices, choices, define, generate - Added "xilinx_srl" for Xilinx shift register extraction - Removed "shregmap -tech xilinx" diff --git a/passes/pmgen/README.md b/passes/pmgen/README.md index 5f6a8ab1b..27ed77091 100644 --- a/passes/pmgen/README.md +++ b/passes/pmgen/README.md @@ -178,6 +178,45 @@ evaluates to `false`. The `semioptional` statement marks matches that must match if at least one matching cell exists, but if no matching cell exists it is set to `nullptr`. +Slices and choices +------------------ + +Cell matches can contain "slices" and "choices". Slices can be used to +create matches for different sections of a cell. For example: + + state <int> pmux_slice + + match pmux + select pmux->type == $pmux + slice idx GetSize(port(pmux, \S)) + index <SigBit> port(pmux, \S)[idx] === port(eq, \Y) + set pmux_slice idx + endmatch + +The first argument to `slice` is the local variable name used to identify the +slice. The second argument is the number of slices that should be created for +this cell. The `set` statement can be used to copy that index indo a state +variable so that later matches and/or code blocks can refer to it. + +A similar mechanism is "choices", where a list of options is given as +second argument, and the matcher will iterate over those options: + + state <SigSpec> foo bar + state <IdString> eq_ab eq_ba + + match eq + select eq->type == $eq + choice <IdString> AB {\A, \B} + define <IdString> BA (AB == \A ? \B : \A) + index <SigSpec> port(eq, AB) === foo + index <SigSpec> port(eq, BA) === bar + set eq_ab AB + set eq_ba BA + generate + +Notice how `define` can be used to define additional local variables similar +to the loop variables defined by `slice` and `choice`. + Additional code --------------- @@ -326,7 +365,7 @@ test-case generation. For example: match mul ... - generate 10 + generate 10 0 SigSpec Y = port(ff, \D); SigSpec A = module->addWire(NEW_ID, GetSize(Y) - rng(GetSize(Y)/2)); SigSpec B = module->addWire(NEW_ID, GetSize(Y) - rng(GetSize(Y)/2)); @@ -335,8 +374,11 @@ test-case generation. For example: The expression `rng(n)` returns a non-negative integer less than `n`. -The argument to `generate` is the chance of this generate block being executed -when the match block did not match anything, in percent. +The first argument to `generate` is the chance of this generate block being +executed when the match block did not match anything, in percent. + +The second argument to `generate` is the chance of this generate block being +executed when the match block did match something, in percent. The special statement `finish` can be used within generate blocks to terminate the current pattern matcher run. diff --git a/passes/pmgen/pmgen.py b/passes/pmgen/pmgen.py index 8944ac2bf..573722d68 100644 --- a/passes/pmgen/pmgen.py +++ b/passes/pmgen/pmgen.py @@ -207,9 +207,10 @@ def process_pmgfile(f, filename): state_types[current_pattern][line[1]] = "Cell*"; block["if"] = list() - block["select"] = list() + block["setup"] = list() block["index"] = list() block["filter"] = list() + block["sets"] = list() block["optional"] = False block["semioptional"] = False @@ -228,7 +229,22 @@ def process_pmgfile(f, filename): if a[0] == "select": b = l.lstrip()[6:] - block["select"].append(rewrite_cpp(b.strip())) + block["setup"].append(("select", rewrite_cpp(b.strip()))) + continue + + if a[0] == "slice": + m = re.match(r"^\s*slice\s+(\S+)\s+(.*?)\s*$", l) + block["setup"].append(("slice", m.group(1), rewrite_cpp(m.group(2)))) + continue + + if a[0] == "choice": + m = re.match(r"^\s*choice\s+<(.*?)>\s+(\S+)\s+(.*?)\s*$", l) + block["setup"].append(("choice", m.group(1), m.group(2), rewrite_cpp(m.group(3)))) + continue + + if a[0] == "define": + m = re.match(r"^\s*define\s+<(.*?)>\s+(\S+)\s+(.*?)\s*$", l) + block["setup"].append(("define", m.group(1), m.group(2), rewrite_cpp(m.group(3)))) continue if a[0] == "index": @@ -242,6 +258,11 @@ def process_pmgfile(f, filename): block["filter"].append(rewrite_cpp(b.strip())) continue + if a[0] == "set": + m = re.match(r"^\s*set\s+(\S+)\s+(.*?)\s*$", l) + block["sets"].append((m.group(1), rewrite_cpp(m.group(2)))) + continue + if a[0] == "optional": block["optional"] = True continue @@ -252,14 +273,16 @@ def process_pmgfile(f, filename): if a[0] == "generate": block["genargs"] = list([int(s) for s in a[1:]]) + if len(block["genargs"]) == 0: block["genargs"].append(100) + if len(block["genargs"]) == 1: block["genargs"].append(0) + assert len(block["genargs"]) == 2 block["gencode"] = list() - assert len(block["genargs"]) < 2 while True: linenr += 1 l = f.readline() assert l != "" a = l.split() - if a[0] == "endmatch": break + if len(a) == 1 and a[0] == "endmatch": break block["gencode"].append(rewrite_cpp(l.rstrip())) break @@ -357,8 +380,17 @@ with open(outfile, "w") as f: index_types = list() for entry in block["index"]: index_types.append(entry[0]) + value_types = ["Cell*"] + for entry in block["setup"]: + if entry[0] == "slice": + value_types.append("int") + if entry[0] == "choice": + value_types.append(entry[1]) + if entry[0] == "define": + value_types.append(entry[1]) print(" typedef std::tuple<{}> index_{}_key_type;".format(", ".join(index_types), index), file=f) - print(" dict<index_{}_key_type, vector<Cell*>> index_{};".format(index, index), file=f) + print(" typedef std::tuple<{}> index_{}_value_type;".format(", ".join(value_types), index), file=f) + print(" dict<index_{}_key_type, vector<index_{}_value_type>> index_{};".format(index, index, index), file=f) print(" dict<SigBit, pool<Cell*>> sigusers;", file=f) print(" pool<Cell*> blacklist_cells;", file=f) print(" pool<Cell*> autoremove_cells;", file=f) @@ -444,14 +476,11 @@ with open(outfile, "w") as f: else: print(" ud_{}.{} = {}();".format(current_pattern, s, t), file=f) current_pattern = None - print(" for (auto cell : module->cells()) {", file=f) - print(" for (auto &conn : cell->connections())", file=f) - print(" add_siguser(conn.second, cell);", file=f) - print(" }", file=f) print(" for (auto port : module->ports)", file=f) print(" add_siguser(module->wire(port), nullptr);", file=f) - print(" ", file=f) - + print(" for (auto cell : module->cells())", file=f) + print(" for (auto &conn : cell->connections())", file=f) + print(" add_siguser(conn.second, cell);", file=f) print(" for (auto cell : cells) {", file=f) for index in range(len(blocks)): @@ -459,12 +488,34 @@ with open(outfile, "w") as f: if block["type"] == "match": print(" do {", file=f) print(" Cell *{} = cell;".format(block["cell"]), file=f) - for expr in block["select"]: - print(" if (!({})) break;".format(expr), file=f) + print(" index_{}_value_type value;".format(index), file=f) + print(" std::get<0>(value) = cell;", file=f) + loopcnt = 0 + valueidx = 1 + for item in block["setup"]: + if item[0] == "select": + print(" if (!({})) continue;".format(item[1]), file=f) + if item[0] == "slice": + print(" int &{} = std::get<{}>(value);".format(item[1], valueidx), file=f) + print(" for ({} = 0; {} < {}; {}++) {{".format(item[1], item[1], item[2], item[1]), file=f) + valueidx += 1 + loopcnt += 1 + if item[0] == "choice": + print(" vector<{}> _pmg_choices_{} = {};".format(item[1], item[2], item[3]), file=f) + print(" for (const {} &{} : _pmg_choices_{}) {{".format(item[1], item[2], item[2]), file=f) + print(" std::get<{}>(value) = {};".format(valueidx, item[2]), file=f) + valueidx += 1 + loopcnt += 1 + if item[0] == "define": + print(" {} &{} = std::get<{}>(value);".format(item[1], item[2], valueidx), file=f) + print(" {} = {};".format(item[2], item[3]), file=f) + valueidx += 1 print(" index_{}_key_type key;".format(index), file=f) for field, entry in enumerate(block["index"]): print(" std::get<{}>(key) = {};".format(field, entry[1]), file=f) - print(" index_{}[key].push_back(cell);".format(index), file=f) + print(" index_{}[key].push_back(value);".format(index), file=f) + for i in range(loopcnt): + print(" }", file=f) print(" } while (0);", file=f) print(" }", file=f) @@ -537,6 +588,8 @@ with open(outfile, "w") as f: const_st.add(s) elif blocks[i]["type"] == "match": const_st.add(blocks[i]["cell"]) + for item in blocks[i]["sets"]: + const_st.add(item[0]) else: assert False @@ -550,6 +603,10 @@ with open(outfile, "w") as f: s = block["cell"] assert s not in const_st nonconst_st.add(s) + for item in block["sets"]: + if item[0] in const_st: + const_st.remove(item[0]) + nonconst_st.add(item[0]) else: assert False @@ -572,7 +629,7 @@ with open(outfile, "w") as f: print("", file=f) for s in sorted(restore_st): t = state_types[current_pattern][s] - print(" {} backup_{} = {};".format(t, s, s), file=f) + print(" {} _pmg_backup_{} = {};".format(t, s, s), file=f) if block["type"] == "code": print("", file=f) @@ -612,7 +669,7 @@ with open(outfile, "w") as f: print("", file=f) for s in sorted(restore_st): t = state_types[current_pattern][s] - print(" {} = backup_{};".format(s, s), file=f) + print(" {} = _pmg_backup_{};".format(s, s), file=f) for s in sorted(nonconst_st): if s not in restore_st: t = state_types[current_pattern][s] @@ -624,7 +681,7 @@ with open(outfile, "w") as f: elif block["type"] == "match": assert len(restore_st) == 0 - print(" Cell* backup_{} = {};".format(block["cell"], block["cell"]), file=f) + print(" Cell* _pmg_backup_{} = {};".format(block["cell"], block["cell"]), file=f) if len(block["if"]): for expr in block["if"]: @@ -632,7 +689,7 @@ with open(outfile, "w") as f: print(" if (!({})) {{".format(expr), file=f) print(" {} = nullptr;".format(block["cell"]), file=f) print(" block_{}(recursion+1);".format(index+1), file=f) - print(" {} = backup_{};".format(block["cell"], block["cell"]), file=f) + print(" {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f) print(" return;", file=f) print(" }", file=f) @@ -647,21 +704,37 @@ with open(outfile, "w") as f: print("", file=f) print(" if (cells_ptr != index_{}.end()) {{".format(index), file=f) - print(" const vector<Cell*> &cells = cells_ptr->second;".format(index), file=f) - print(" for (int idx = 0; idx < GetSize(cells); idx++) {", file=f) - print(" {} = cells[idx];".format(block["cell"]), file=f) + print(" const vector<index_{}_value_type> &cells = cells_ptr->second;".format(index), file=f) + print(" for (int _pmg_idx = 0; _pmg_idx < GetSize(cells); _pmg_idx++) {", file=f) + print(" {} = std::get<0>(cells[_pmg_idx]);".format(block["cell"]), file=f) + valueidx = 1 + for item in block["setup"]: + if item[0] == "slice": + print(" const int &{} YS_ATTRIBUTE(unused) = std::get<{}>(cells[_pmg_idx]);".format(item[1], valueidx), file=f) + valueidx += 1 + if item[0] == "choice": + print(" const {} &{} YS_ATTRIBUTE(unused) = std::get<{}>(cells[_pmg_idx]);".format(item[1], item[2], valueidx), file=f) + valueidx += 1 + if item[0] == "define": + print(" const {} &{} YS_ATTRIBUTE(unused) = std::get<{}>(cells[_pmg_idx]);".format(item[1], item[2], valueidx), file=f) + valueidx += 1 print(" if (blacklist_cells.count({})) continue;".format(block["cell"]), file=f) for expr in block["filter"]: print(" if (!({})) continue;".format(expr), file=f) if block["semioptional"] or block["genargs"] is not None: print(" found_any_match = true;", file=f) - print(" auto rollback_ptr = rollback_cache.insert(make_pair(cells[idx], recursion));", file=f) + for item in block["sets"]: + print(" auto _pmg_backup_{} = {};".format(item[0], item[0]), file=f) + print(" {} = {};".format(item[0], item[1]), file=f) + print(" auto rollback_ptr = rollback_cache.insert(make_pair(std::get<0>(cells[_pmg_idx]), recursion));", file=f) print(" block_{}(recursion+1);".format(index+1), file=f) + for item in block["sets"]: + print(" {} = _pmg_backup_{};".format(item[0], item[0]), file=f) print(" if (rollback_ptr.second)", file=f) print(" rollback_cache.erase(rollback_ptr.first);", file=f) print(" if (rollback) {", file=f) print(" if (rollback != recursion) {{".format(index+1), file=f) - print(" {} = backup_{};".format(block["cell"], block["cell"]), file=f) + print(" {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f) print(" return;", file=f) print(" }", file=f) print(" rollback = 0;", file=f) @@ -678,13 +751,11 @@ with open(outfile, "w") as f: if block["semioptional"]: print(" if (!found_any_match) block_{}(recursion+1);".format(index+1), file=f) - print(" {} = backup_{};".format(block["cell"], block["cell"]), file=f) + print(" {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f) if block["genargs"] is not None: print("#define finish do { rollback = -1; return; } while(0)", file=f) - print(" if (generate_mode && !found_any_match) {", file=f) - if len(block["genargs"]) == 1: - print(" if (rng(100) >= {}) return;".format(block["genargs"][0]), file=f) + print(" if (generate_mode && rng(100) < (found_any_match ? {} : {})) {{".format(block["genargs"][1], block["genargs"][0]), file=f) for line in block["gencode"]: print(" " + line, file=f) print(" }", file=f) diff --git a/passes/pmgen/test_pmgen.cc b/passes/pmgen/test_pmgen.cc index 9f42a95d0..0ad769dfd 100644 --- a/passes/pmgen/test_pmgen.cc +++ b/passes/pmgen/test_pmgen.cc @@ -99,6 +99,24 @@ void reduce_tree(test_pmgen_pm &pm) log(" -> %s (%s)\n", log_id(c), log_id(c->type)); } +void opt_eqpmux(test_pmgen_pm &pm) +{ + auto &st = pm.st_eqpmux; + + SigSpec Y = st.pmux->getPort(ID::Y); + int width = GetSize(Y); + + SigSpec EQ = st.pmux->getPort(ID::B).extract(st.pmux_slice_eq*width, width); + SigSpec NE = st.pmux->getPort(ID::B).extract(st.pmux_slice_ne*width, width); + + log("Found eqpmux circuit driving %s (eq=%s, ne=%s, pmux=%s).\n", + log_signal(Y), log_id(st.eq), log_id(st.ne), log_id(st.pmux)); + + pm.autoremove(st.pmux); + Cell *c = pm.module->addMux(NEW_ID, NE, EQ, st.eq->getPort(ID::Y), Y); + log(" -> %s (%s)\n", log_id(c), log_id(c->type)); +} + #define GENERATE_PATTERN(pmclass, pattern) \ generate_pattern<pmclass>([](pmclass &pm, std::function<void()> f){ return pm.run_ ## pattern(f); }, #pmclass, #pattern, design) @@ -149,16 +167,17 @@ void generate_pattern(std::function<void(pm&,std::function<void()>)> run, const log("Generating \"%s\" patterns for pattern matcher \"%s\".\n", pattern, pmclass); int modcnt = 0; + int maxmodcnt = 100; int maxsubcnt = 4; int timeout = 0; vector<Module*> mods; - while (modcnt < 100) + while (modcnt < maxmodcnt) { int submodcnt = 0, itercnt = 0, cellcnt = 0; Module *mod = design->addModule(NEW_ID); - while (modcnt < 100 && submodcnt < maxsubcnt && itercnt++ < 1000) + while (modcnt < maxmodcnt && submodcnt < maxsubcnt && itercnt++ < 1000) { if (timeout++ > 10000) log_error("pmgen generator is stuck: 10000 iterations an no matching module generated.\n"); @@ -233,6 +252,12 @@ struct TestPmgenPass : public Pass { log("\n"); log("\n"); + log(" test_pmgen -eqpmux [options] [selection]\n"); + log("\n"); + log("Demo for recursive pmgen patterns. Optimize EQ/NE/PMUX circuits.\n"); + log("\n"); + + log("\n"); log(" test_pmgen -generate [options] <pattern_name>\n"); log("\n"); log("Create modules that match the specified pattern.\n"); @@ -277,6 +302,25 @@ struct TestPmgenPass : public Pass { test_pmgen_pm(module, module->selected_cells()).run_reduce(reduce_tree); } + void execute_eqpmux(std::vector<std::string> args, RTLIL::Design *design) + { + log_header(design, "Executing TEST_PMGEN pass (-eqpmux).\n"); + + size_t argidx; + for (argidx = 2; argidx < args.size(); argidx++) + { + // if (args[argidx] == "-singleton") { + // singleton_mode = true; + // continue; + // } + break; + } + extra_args(args, argidx, design); + + for (auto module : design->selected_modules()) + test_pmgen_pm(module, module->selected_cells()).run_eqpmux(opt_eqpmux); + } + void execute_generate(std::vector<std::string> args, RTLIL::Design *design) { log_header(design, "Executing TEST_PMGEN pass (-generate).\n"); @@ -299,6 +343,9 @@ struct TestPmgenPass : public Pass { if (pattern == "reduce") return GENERATE_PATTERN(test_pmgen_pm, reduce); + if (pattern == "eqpmux") + return GENERATE_PATTERN(test_pmgen_pm, eqpmux); + if (pattern == "ice40_dsp") return GENERATE_PATTERN(ice40_dsp_pm, ice40_dsp); @@ -319,6 +366,8 @@ struct TestPmgenPass : public Pass { return execute_reduce_chain(args, design); if (args[1] == "-reduce_tree") return execute_reduce_tree(args, design); + if (args[1] == "-eqpmux") + return execute_eqpmux(args, design); if (args[1] == "-generate") return execute_generate(args, design); } diff --git a/passes/pmgen/test_pmgen.pmg b/passes/pmgen/test_pmgen.pmg index 211477a62..287ed97d8 100644 --- a/passes/pmgen/test_pmgen.pmg +++ b/passes/pmgen/test_pmgen.pmg @@ -60,8 +60,8 @@ code portname endcode match next - select nusers(port(next, \Y)) == 2 select next->type.in($_AND_, $_OR_, $_XOR_) + select nusers(port(next, \Y)) == 2 index <IdString> next->type === first->type index <SigSpec> port(next, \Y) === port(first, portname) endmatch @@ -77,8 +77,8 @@ arg first match next semioptional - select nusers(port(next, \Y)) == 2 select next->type.in($_AND_, $_OR_, $_XOR_) + select nusers(port(next, \Y)) == 2 index <IdString> next->type === chain.back().first->type index <SigSpec> port(next, \Y) === port(chain.back().first, chain.back().second) generate 10 @@ -104,3 +104,86 @@ finally if (next) chain.pop_back(); endcode + +// ================================================================== + +pattern eqpmux + +state <bool> eq_ne_signed +state <SigSpec> eq_inA eq_inB +state <int> pmux_slice_eq pmux_slice_ne + +match eq + select eq->type == $eq + choice <IdString> AB {\A, \B} + define <IdString> BA AB == \A ? \B : \A + set eq_inA port(eq, \A) + set eq_inB port(eq, \B) + set eq_ne_signed param(eq, \A_SIGNED).as_bool() +generate 100 10 + SigSpec A = module->addWire(NEW_ID, rng(7)+1); + SigSpec B = module->addWire(NEW_ID, rng(7)+1); + SigSpec Y = module->addWire(NEW_ID); + module->addEq(NEW_ID, A, B, Y, rng(2)); +endmatch + +match pmux + select pmux->type == $pmux + slice idx GetSize(port(pmux, \S)) + index <SigBit> port(pmux, \S)[idx] === port(eq, \Y) + set pmux_slice_eq idx +generate 100 10 + int width = rng(7) + 1; + int numsel = rng(4) + 1; + int idx = rng(numsel); + + SigSpec A = module->addWire(NEW_ID, width); + SigSpec Y = module->addWire(NEW_ID, width); + + SigSpec B, S; + for (int i = 0; i < numsel; i++) { + B.append(module->addWire(NEW_ID, width)); + S.append(i == idx ? port(eq, \Y) : module->addWire(NEW_ID)); + } + + module->addPmux(NEW_ID, A, B, S, Y); +endmatch + +match ne + select ne->type == $ne + choice <IdString> AB {\A, \B} + define <IdString> BA (AB == \A ? \B : \A) + index <SigSpec> port(ne, AB) === eq_inA + index <SigSpec> port(ne, BA) === eq_inB + index <int> param(ne, \A_SIGNED).as_bool() === eq_ne_signed +generate 100 10 + SigSpec A = eq_inA, B = eq_inB, Y; + if (rng(2)) { + std::swap(A, B); + } + if (rng(2)) { + for (auto bit : port(pmux, \S)) { + if (nusers(bit) < 2) + Y.append(bit); + } + if (GetSize(Y)) + Y = Y[rng(GetSize(Y))]; + else + Y = module->addWire(NEW_ID); + } else { + Y = module->addWire(NEW_ID); + } + module->addNe(NEW_ID, A, B, Y, rng(2)); +endmatch + +match pmux2 + select pmux2->type == $pmux + slice idx GetSize(port(pmux2, \S)) + index <Cell*> pmux2 === pmux + index <SigBit> port(pmux2, \S)[idx] === port(ne, \Y) + set pmux_slice_ne idx +endmatch + +code + accept; +endcode |