From adb81ba3861d66a94f237fd29a67b8978980cd37 Mon Sep 17 00:00:00 2001
From: Clifford Wolf <clifford@clifford.at>
Date: Fri, 23 Aug 2019 16:15:50 +0200
Subject: Add pmgen slices and choices
Signed-off-by: Clifford Wolf <clifford@clifford.at>
---
CHANGELOG | 1 +
passes/pmgen/README.md | 48 ++++++++++++++++--
passes/pmgen/pmgen.py | 116 ++++++++++++++++++++++++++++++++++++--------
passes/pmgen/test_pmgen.cc | 53 +++++++++++++++++++-
passes/pmgen/test_pmgen.pmg | 87 ++++++++++++++++++++++++++++++++-
5 files changed, 277 insertions(+), 28 deletions(-)
diff --git a/CHANGELOG b/CHANGELOG
index ca42df71e..dd94c76ed 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -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
Yosys 0.8 .. Yosys 0.8-dev
--------------------------
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 18c3bf5a5..c2621393d 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)
@@ -457,12 +489,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)
@@ -535,6 +589,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
@@ -548,6 +604,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
@@ -570,7 +630,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)
@@ -610,7 +670,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]
@@ -622,7 +682,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"]:
@@ -630,7 +690,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)
@@ -645,21 +705,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)
@@ -676,13 +752,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");
@@ -232,6 +251,12 @@ struct TestPmgenPass : public Pass {
log("Demo for recursive pmgen patterns. Map trees of AND/OR/XOR to $reduce_*.\n");
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");
@@ -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
--
cgit v1.2.3