From 03f98d9176357b73455cf0b2c44ec3897864e893 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Thu, 15 Aug 2019 18:35:00 +0200 Subject: [PATCH] Add demo_reduce pass to demonstrace recursive pattern matching Signed-off-by: Clifford Wolf --- passes/pmgen/.gitignore | 1 + passes/pmgen/Makefile.inc | 6 +++ passes/pmgen/demo_reduce.cc | 99 ++++++++++++++++++++++++++++++++++++ passes/pmgen/demo_reduce.pmg | 81 +++++++++++++++++++++++++++++ 4 files changed, 187 insertions(+) create mode 100644 passes/pmgen/demo_reduce.cc create mode 100644 passes/pmgen/demo_reduce.pmg diff --git a/passes/pmgen/.gitignore b/passes/pmgen/.gitignore index 0ad36ea2c..a1fe9a7dc 100644 --- a/passes/pmgen/.gitignore +++ b/passes/pmgen/.gitignore @@ -1,2 +1,3 @@ +/demo_reduce_pm.h /ice40_dsp_pm.h /peepopt_pm.h diff --git a/passes/pmgen/Makefile.inc b/passes/pmgen/Makefile.inc index 0d977635b..3aaee4047 100644 --- a/passes/pmgen/Makefile.inc +++ b/passes/pmgen/Makefile.inc @@ -9,6 +9,12 @@ $(eval $(call add_extra_objs,passes/pmgen/ice40_dsp_pm.h)) # -------------------------------------- +OBJS += passes/pmgen/demo_reduce.o +passes/pmgen/demo_reduce.o: passes/pmgen/demo_reduce_pm.h +$(eval $(call add_extra_objs,passes/pmgen/demo_reduce_pm.h)) + +# -------------------------------------- + OBJS += passes/pmgen/peepopt.o passes/pmgen/peepopt.o: passes/pmgen/peepopt_pm.h $(eval $(call add_extra_objs,passes/pmgen/peepopt_pm.h)) diff --git a/passes/pmgen/demo_reduce.cc b/passes/pmgen/demo_reduce.cc new file mode 100644 index 000000000..dd8c66f56 --- /dev/null +++ b/passes/pmgen/demo_reduce.cc @@ -0,0 +1,99 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/yosys.h" +#include "kernel/sigtools.h" + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +#include "passes/pmgen/demo_reduce_pm.h" + +void create_reduce(demo_reduce_pm &pm) +{ + auto &st = pm.st_reduce; + auto &ud = pm.ud_reduce; + + if (ud.longest_chain.empty()) + return; + + log("Found chain of length %d (%s):\n", GetSize(ud.longest_chain), log_id(st.first->type)); + + SigSpec A; + SigSpec Y = ud.longest_chain.front().first->getPort(ID(Y)); + auto last_cell = ud.longest_chain.back().first; + + for (auto it : ud.longest_chain) { + auto cell = it.first; + if (cell == last_cell) { + A.append(cell->getPort(ID(A))); + A.append(cell->getPort(ID(B))); + } else { + A.append(cell->getPort(it.second == ID(A) ? ID(B) : ID(A))); + } + log(" %s\n", log_id(cell)); + pm.autoremove(cell); + } + + Cell *c; + + if (last_cell->type == ID($_AND_)) + c = pm.module->addReduceAnd(NEW_ID, A, Y); + else if (last_cell->type == ID($_OR_)) + c = pm.module->addReduceOr(NEW_ID, A, Y); + else if (last_cell->type == ID($_XOR_)) + c = pm.module->addReduceXor(NEW_ID, A, Y); + else + log_abort(); + + log(" -> %s (%s)\n", log_id(c), log_id(c->type)); +} + +struct DemoReducePass : public Pass { + DemoReducePass() : Pass("demo_reduce", "map chains of AND/OR/XOR") { } + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" demo_reduce [options] [selection]\n"); + log("\n"); + log("Demo for recursive pmgen patterns. Map chains of AND/OR/XOR to $reduce_*.\n"); + log("\n"); + } + void execute(std::vector args, RTLIL::Design *design) YS_OVERRIDE + { + log_header(design, "Executing DEMO_REDUCE pass.\n"); + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + // if (args[argidx] == "-singleton") { + // singleton_mode = true; + // continue; + // } + break; + } + extra_args(args, argidx, design); + + for (auto module : design->selected_modules()) + demo_reduce_pm(module, module->selected_cells()).run_reduce(create_reduce); + } +} DemoReducePass; + +PRIVATE_NAMESPACE_END diff --git a/passes/pmgen/demo_reduce.pmg b/passes/pmgen/demo_reduce.pmg new file mode 100644 index 000000000..ddc932de5 --- /dev/null +++ b/passes/pmgen/demo_reduce.pmg @@ -0,0 +1,81 @@ +pattern reduce + +state portname +udata >> chain longest_chain +udata > non_first_cells + +code + non_first_cells.clear(); + subpattern(setup); +endcode + +match first + select first->type.in($_AND_, $_OR_, $_XOR_) + filter !non_first_cells.count(first) +endmatch + +code + longest_chain.clear(); + chain.push_back(make_pair(first, \A)); + subpattern(tail); + chain.back().second = \B; + subpattern(tail); +finally + chain.pop_back(); + log_assert(chain.empty()); +endcode + +// ------------------------------------------------------------------ + +subpattern setup + +match first + select first->type.in($_AND_, $_OR_, $_XOR_) +endmatch + +code portname + portname = \A; + branch; + portname = \B; +endcode + +match next + select nusers(port(next, \Y)) == 2 + select next->type.in($_AND_, $_OR_, $_XOR_) + index next->type === first->type + index port(next, \Y) === port(first, portname) +endmatch + +code + non_first_cells.insert(next); + reject; +endcode + +// ------------------------------------------------------------------ + +subpattern tail +arg first + +match next + semioptional + select nusers(port(next, \Y)) == 2 + select next->type.in($_AND_, $_OR_, $_XOR_) + index next->type === chain.back().first->type + index port(next, \Y) === port(chain.back().first, chain.back().second) +endmatch + +code + if (next) { + chain.push_back(make_pair(next, \A)); + subpattern(tail); + chain.back().second = \B; + subpattern(tail); + } else { + if (GetSize(chain) > GetSize(longest_chain)) + longest_chain = chain; + } + reject; +finally + if (next) + chain.pop_back(); +endcode -- 2.30.2