diff options
Diffstat (limited to 'passes/pmgen')
| -rw-r--r-- | passes/pmgen/.gitignore | 1 | ||||
| -rw-r--r-- | passes/pmgen/Makefile.inc | 39 | ||||
| -rw-r--r-- | passes/pmgen/README.md | 384 | ||||
| -rw-r--r-- | passes/pmgen/ice40_dsp.cc | 235 | ||||
| -rw-r--r-- | passes/pmgen/ice40_dsp.pmg | 163 | ||||
| -rw-r--r-- | passes/pmgen/ice40_wrapcarry.cc | 90 | ||||
| -rw-r--r-- | passes/pmgen/ice40_wrapcarry.pmg | 11 | ||||
| -rw-r--r-- | passes/pmgen/peepopt.cc | 69 | ||||
| -rw-r--r-- | passes/pmgen/peepopt_dffmux.pmg | 113 | ||||
| -rw-r--r-- | passes/pmgen/peepopt_muldiv.pmg | 36 | ||||
| -rw-r--r-- | passes/pmgen/peepopt_shiftmul.pmg | 96 | ||||
| -rw-r--r-- | passes/pmgen/pmgen.py | 774 | ||||
| -rw-r--r-- | passes/pmgen/test_pmgen.cc | 385 | ||||
| -rw-r--r-- | passes/pmgen/test_pmgen.pmg | 189 | ||||
| -rw-r--r-- | passes/pmgen/xilinx_srl.cc | 258 | ||||
| -rw-r--r-- | passes/pmgen/xilinx_srl.pmg | 326 |
16 files changed, 3169 insertions, 0 deletions
diff --git a/passes/pmgen/.gitignore b/passes/pmgen/.gitignore new file mode 100644 index 000000000..6b319b8c3 --- /dev/null +++ b/passes/pmgen/.gitignore @@ -0,0 +1 @@ +/*_pm.h
\ No newline at end of file diff --git a/passes/pmgen/Makefile.inc b/passes/pmgen/Makefile.inc new file mode 100644 index 000000000..98691d0fe --- /dev/null +++ b/passes/pmgen/Makefile.inc @@ -0,0 +1,39 @@ +%_pm.h: passes/pmgen/pmgen.py %.pmg + $(P) mkdir -p passes/pmgen && python3 $< -o $@ -p $(subst _pm.h,,$(notdir $@)) $(filter-out $<,$^) + +# -------------------------------------- + +OBJS += passes/pmgen/test_pmgen.o +passes/pmgen/test_pmgen.o: passes/pmgen/test_pmgen_pm.h passes/pmgen/ice40_dsp_pm.h passes/pmgen/peepopt_pm.h passes/pmgen/xilinx_srl_pm.h +$(eval $(call add_extra_objs,passes/pmgen/test_pmgen_pm.h)) + +# -------------------------------------- + +OBJS += passes/pmgen/ice40_dsp.o +passes/pmgen/ice40_dsp.o: passes/pmgen/ice40_dsp_pm.h +$(eval $(call add_extra_objs,passes/pmgen/ice40_dsp_pm.h)) + +# -------------------------------------- + +OBJS += passes/pmgen/ice40_wrapcarry.o +passes/pmgen/ice40_wrapcarry.o: passes/pmgen/ice40_wrapcarry_pm.h +$(eval $(call add_extra_objs,passes/pmgen/ice40_wrapcarry_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)) + +PEEPOPT_PATTERN = passes/pmgen/peepopt_shiftmul.pmg +PEEPOPT_PATTERN += passes/pmgen/peepopt_muldiv.pmg +PEEPOPT_PATTERN += passes/pmgen/peepopt_dffmux.pmg + +passes/pmgen/peepopt_pm.h: passes/pmgen/pmgen.py $(PEEPOPT_PATTERN) + $(P) mkdir -p passes/pmgen && python3 $< -o $@ -p peepopt $(filter-out $<,$^) + +# -------------------------------------- + +OBJS += passes/pmgen/xilinx_srl.o +passes/pmgen/xilinx_srl.o: passes/pmgen/xilinx_srl_pm.h +$(eval $(call add_extra_objs,passes/pmgen/xilinx_srl_pm.h)) diff --git a/passes/pmgen/README.md b/passes/pmgen/README.md new file mode 100644 index 000000000..2f5b8d0b2 --- /dev/null +++ b/passes/pmgen/README.md @@ -0,0 +1,384 @@ +Pattern Matcher Generator +========================= + +The program `pmgen.py` reads a `.pmg` (Pattern Matcher Generator) file and +writes a header-only C++ library that implements that pattern matcher. + +The "patterns" in this context are subgraphs in a Yosys RTLIL netlist. + +The algorithm used in the generated pattern matcher is a simple recursive +search with backtracking. It is left to the author of the `.pmg` file to +determine an efficient cell order for the search that allows for maximum +use of indices and early backtracking. + + +API of Generated Matcher +======================== + +When `pmgen.py` reads a `foobar.pmg` file, it writes `foobar_pm.h` containing +a class `foobar_pm`. That class is instantiated with an RTLIL module and a +list of cells from that module: + + foobar_pm pm(module, module->selected_cells()); + +The caller must make sure that none of the cells in the 2nd argument are +deleted for as long as the patter matcher instance is used. + +At any time it is possible to disable cells, preventing them from showing +up in any future matches: + + pm.blacklist(some_cell); + +The `.run_<pattern_name>(callback_function)` method searches for all matches +for the pattern`<pattern_name>` and calls the callback function for each found +match: + + pm.run_foobar([&](){ + log("found matching 'foo' cell: %s\n", log_id(pm.st.foo)); + log(" with 'bar' cell: %s\n", log_id(pm.st.bar)); + }); + +The `.pmg` file declares matcher state variables that are accessible via the +`.st_<pattern_name>.<state_name>` members. (The `.st_<pattern_name>` member is +of type `foobar_pm::state_<pattern_name>_t`.) + +Similarly the `.pmg` file declares user data variables that become members of +`.ud_<pattern_name>`, a struct of type `foobar_pm::udata_<pattern_name>_t`. + +There are three versions of the `run_<pattern_name>()` method: Without callback, +callback without arguments, and callback with reference to `pm`. All versions +of the `run_<pattern_name>()` method return the number of found matches. + + +The .pmg File Format +==================== + +The `.pmg` file format is a simple line-based file format. For the most part +lines consist of whitespace-separated tokens. + +Lines in `.pmg` files starting with `//` are comments. + +Declaring a pattern +------------------- + +A `.pmg` file contains one or more patterns. Each pattern starts with a line +with the `pattern` keyword followed by the name of the pattern. + +Declaring state variables +------------------------- + +One or more state variables can be declared using the `state` statement, +followed by a C++ type in angle brackets, followed by a whitespace separated +list of variable names. For example: + + state <bool> flag1 flag2 happy big + state <SigSpec> sigA sigB sigY + +State variables are automatically managed by the generated backtracking algorithm +and saved and restored as needed. + +They are automatically initialized to the default constructed value of their type +when `.run_<pattern_name>(callback_function)` is called. + +Declaring udata variables +------------------------- + +Udata (user-data) variables can be used for example to configure the matcher or +the callback function used to perform actions on found matches. + +There is no automatic management of udata variables. For this reason it is +recommended that the user-supplied matcher code treats them as read-only +variables. + +They are declared like state variables, just using the `udata` statement: + + udata <int> min_data_width max_data_width + udata <IdString> data_port_name + +They are automatically initialized to the default constructed value of their type +when the pattern matcher object is constructed. + +Embedded C++ code +----------------- + +Many statements in a `.pmg` file contain C++ code. However, there are some +slight additions to regular C++/Yosys/RTLIL code that make it a bit easier to +write matchers: + +- Identifiers starting with a dollar sign or backslash are automatically + converted to special IdString variables that are initialized when the + matcher object is constructed. + +- The `port(<cell>, <portname>)` function is a handy alias for + `sigmap(<cell>->getPort(<portname>))`. + +- Similarly `param(<cell>, <paramname>)` looks up a parameter on a cell. + +- The function `nusers(<sigspec>)` returns the number of different cells + connected to any of the given signal bits, plus one if any of the signal + bits is also a primary input or primary output. + +- In `code..endcode` blocks there exist `accept`, `reject`, `branch`, + `finish`, and `subpattern` statements. + +- In `index` statements there is a special `===` operator for the index + lookup. + +Matching cells +-------------- + +Cells are matched using `match..endmatch` blocks. For example: + + match mul + if ff + select mul->type == $mul + select nusers(port(mul, \Y) == 2 + index <SigSpec> port(mul, \Y) === port(ff, \D) + filter some_weird_function(mul) < other_weird_function(ff) + optional + endmatch + +A `match` block starts with `match <statevar>` and implicitly generates +a state variable `<statevar>` of type `RTLIL::Cell*`. + +All statements in the match block are optional. (An empty match block +would simply match each and every cell in the module.) + +The `if <expression>` statement makes the match block conditional. If +`<expression>` evaluates to `false` then the match block will be ignored +and the corresponding state variable is set to `nullptr`. In our example +we only try to match the `mul` cell if the `ff` state variable points +to a cell. (Presumably `ff` is provided by a prior `match` block.) + +The `select` lines are evaluated once for each cell when the matcher is +initialized. A `match` block will only consider cells for which all `select` +expressions evaluated to `true`. Note that the state variable corresponding to +the match (in the example `mul`) is the only state variable that may be used +in `select` lines. + +Index lines are using the `index <type> expr1 === expr2` syntax. `expr1` is +evaluated during matcher initialization and the same restrictions apply as for +`select` expressions. `expr2` is evaluated when the match is calulated. It is a +function of any state variables assigned to by previous blocks. Both expression +are converted to the given type and compared for equality. Only cells for which +all `index` statements in the block pass are considered by the match. + +Note that `select` and `index` are fast operations. Thus `select` and `index` +should be used whenever possible to create efficient matchers. + +Finally, `filter <expression>` narrows down the remaining list of cells. For +performance reasons `filter` statements should only be used for things that +can't be done using `select` and `index`. + +The `optional` statement marks optional matches. That is, the matcher will also +explore the case where `mul` is set to `nullptr`. Without the `optional` +statement a match may only be assigned nullptr when one of the `if` expressions +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 into 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 +--------------- + +Interleaved with `match..endmatch` blocks there may be `code..endcode` blocks. +Such a block starts with the keyword `code` followed by a list of state variables +that the block may modify. For example: + + code addAB sigS + if (addA) { + addAB = addA; + sigS = port(addA, \B); + } + if (addB) { + addAB = addB; + sigS = port(addB, \A); + } + endcode + +The special keyword `reject` can be used to reject the current state and +backtrack. For example: + + code + if (ffA && ffB) { + if (port(ffA, \CLK) != port(ffB, \CLK)) + reject; + if (param(ffA, \CLK_POLARITY) != param(ffB, \CLK_POLARITY)) + reject; + } + endcode + +Similarly, the special keyword `accept` can be used to accept the current +state. (`accept` will not backtrack. This means it continues with the current +branch and may accept a larger match later.) + +The special keyword `branch` can be used to explore different cases. Note that +each code block has an implicit `branch` at the end. So most use-cases of the +`branch` keyword need to end the block with `reject` to avoid the implicit +branch at the end. For example: + + state <int> mode + + code mode + for (mode = 0; mode < 8; mode++) + branch; + reject; + endcode + +But in some cases it is more natural to utilize the implicit branch statement: + + state <IdString> portAB + + code portAB + portAB = \A; + branch; + portAB = \B; + endcode + +There is an implicit `code..endcode` block at the end of each (sub)pattern +that just rejects. + +A `code..finally..endcode` block executes the code after `finally` during +back-tracking. This is useful for maintaining user data state or printing +debug messages. For example: + + udata <vector<Cell*>> stack + + code + stack.push_back(addAB); + ... + finally + stack.pop_back(); + endcode + +`accept` and `finish` statements can be used inside the `finally` section, +but not `reject`, `branch`, or `subpattern`. + +Declaring a subpattern +---------------------- + +A subpattern starts with a line containing the `subpattern` keyword followed +by the name of the subpattern. Subpatterns can be called from a `code` block +using a `subpattern(<subpattern_name>);` C statement. + +Arguments may be passed to subpattern via state variables. The `subpattern` +line must be followed by a `arg <arg1> <arg2> ...` line that lists the +state variables used to pass arguments. + + state <IdString> foobar_type + state <bool> foobar_state + + code foobar_type foobar_state + foobar_state = false; + foobar_type = $add; + subpattern(foo); + foobar_type = $sub; + subpattern(bar); + endcode + + subpattern foo + arg foobar_type foobar_state + + match addsub + index <IdString> addsub->type === foobar_type + ... + endmatch + + code + if (foobar_state) { + subpattern(tail); + } else { + foobar_state = true; + subpattern(bar); + } + endcode + + subpattern bar + arg foobar_type foobar_state + + match addsub + index <IdString> addsub->type === foobar_type + ... + endmatch + + code + if (foobar_state) { + subpattern(tail); + } else { + foobar_state = true; + subpattern(foo); + } + endcode + + subpattern tail + ... + +Subpatterns can be called recursively. + +If a `subpattern` statement is preceded by a `fallthrough` statement, this is +equivalent to calling the subpattern at the end of the preceding block. + +Generate Blocks +--------------- + +Match blocks may contain an optional `generate` section that is used for automatic +test-case generation. For example: + + match mul + ... + 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)); + module->addMul(NEW_ID, A, B, Y, rng(2)); + endmatch + +The expression `rng(n)` returns a non-negative integer less than `n`. + +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/ice40_dsp.cc b/passes/pmgen/ice40_dsp.cc new file mode 100644 index 000000000..16bfe537f --- /dev/null +++ b/passes/pmgen/ice40_dsp.cc @@ -0,0 +1,235 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * 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/ice40_dsp_pm.h" + +void create_ice40_dsp(ice40_dsp_pm &pm) +{ + auto &st = pm.st_ice40_dsp; + +#if 0 + log("\n"); + log("ffA: %s\n", log_id(st.ffA, "--")); + log("ffB: %s\n", log_id(st.ffB, "--")); + log("mul: %s\n", log_id(st.mul, "--")); + log("ffY: %s\n", log_id(st.ffY, "--")); + log("addAB: %s\n", log_id(st.addAB, "--")); + log("muxAB: %s\n", log_id(st.muxAB, "--")); + log("ffS: %s\n", log_id(st.ffS, "--")); +#endif + + log("Checking %s.%s for iCE40 DSP inference.\n", log_id(pm.module), log_id(st.mul)); + + if (GetSize(st.sigA) > 16) { + log(" input A (%s) is too large (%d > 16).\n", log_signal(st.sigA), GetSize(st.sigA)); + return; + } + + if (GetSize(st.sigB) > 16) { + log(" input B (%s) is too large (%d > 16).\n", log_signal(st.sigB), GetSize(st.sigB)); + return; + } + + if (GetSize(st.sigS) > 32) { + log(" accumulator (%s) is too large (%d > 32).\n", log_signal(st.sigS), GetSize(st.sigS)); + return; + } + + if (GetSize(st.sigY) > 32) { + log(" output (%s) is too large (%d > 32).\n", log_signal(st.sigY), GetSize(st.sigY)); + return; + } + + bool mul_signed = st.mul->getParam("\\A_SIGNED").as_bool(); + + log(" replacing $mul with SB_MAC16 cell.\n"); + + Cell *cell = pm.module->addCell(NEW_ID, "\\SB_MAC16"); + pm.module->swap_names(cell, st.mul); + + // SB_MAC16 Input Interface + + SigSpec A = st.sigA; + A.extend_u0(16, mul_signed); + + SigSpec B = st.sigB; + B.extend_u0(16, mul_signed); + + SigSpec CD; + if (st.muxA) + CD = st.muxA->getPort("\\B"); + if (st.muxB) + CD = st.muxB->getPort("\\A"); + CD.extend_u0(32, mul_signed); + + cell->setPort("\\A", A); + cell->setPort("\\B", B); + cell->setPort("\\C", CD.extract(0, 16)); + cell->setPort("\\D", CD.extract(16, 16)); + + cell->setParam("\\A_REG", st.ffA ? State::S1 : State::S0); + cell->setParam("\\B_REG", st.ffB ? State::S1 : State::S0); + + cell->setPort("\\AHOLD", State::S0); + cell->setPort("\\BHOLD", State::S0); + cell->setPort("\\CHOLD", State::S0); + cell->setPort("\\DHOLD", State::S0); + + cell->setPort("\\IRSTTOP", State::S0); + cell->setPort("\\IRSTBOT", State::S0); + + if (st.clock_vld) + { + cell->setPort("\\CLK", st.clock); + cell->setPort("\\CE", State::S1); + cell->setParam("\\NEG_TRIGGER", st.clock_pol ? State::S0 : State::S1); + + log(" clock: %s (%s)", log_signal(st.clock), st.clock_pol ? "posedge" : "negedge"); + + if (st.ffA) + log(" ffA:%s", log_id(st.ffA)); + + if (st.ffB) + log(" ffB:%s", log_id(st.ffB)); + + if (st.ffY) + log(" ffY:%s", log_id(st.ffY)); + + if (st.ffS) + log(" ffS:%s", log_id(st.ffS)); + + log("\n"); + } + else + { + cell->setPort("\\CLK", State::S0); + cell->setPort("\\CE", State::S0); + cell->setParam("\\NEG_TRIGGER", State::S0); + } + + // SB_MAC16 Cascade Interface + + cell->setPort("\\SIGNEXTIN", State::Sx); + cell->setPort("\\SIGNEXTOUT", pm.module->addWire(NEW_ID)); + + cell->setPort("\\CI", State::Sx); + cell->setPort("\\CO", pm.module->addWire(NEW_ID)); + + cell->setPort("\\ACCUMCI", State::Sx); + cell->setPort("\\ACCUMCO", pm.module->addWire(NEW_ID)); + + // SB_MAC16 Output Interface + + SigSpec O = st.ffS ? st.sigS : st.sigY; + if (GetSize(O) < 32) + O.append(pm.module->addWire(NEW_ID, 32-GetSize(O))); + + cell->setPort("\\O", O); + + if (st.addAB) { + log(" accumulator %s (%s)\n", log_id(st.addAB), log_id(st.addAB->type)); + cell->setPort("\\ADDSUBTOP", st.addAB->type == "$add" ? State::S0 : State::S1); + cell->setPort("\\ADDSUBBOT", st.addAB->type == "$add" ? State::S0 : State::S1); + } else { + cell->setPort("\\ADDSUBTOP", State::S0); + cell->setPort("\\ADDSUBBOT", State::S0); + } + + cell->setPort("\\ORSTTOP", State::S0); + cell->setPort("\\ORSTBOT", State::S0); + + cell->setPort("\\OHOLDTOP", State::S0); + cell->setPort("\\OHOLDBOT", State::S0); + + SigSpec acc_reset = State::S0; + if (st.muxA) + acc_reset = st.muxA->getPort("\\S"); + if (st.muxB) + acc_reset = pm.module->Not(NEW_ID, st.muxB->getPort("\\S")); + + cell->setPort("\\OLOADTOP", acc_reset); + cell->setPort("\\OLOADBOT", acc_reset); + + // SB_MAC16 Remaining Parameters + + cell->setParam("\\C_REG", State::S0); + cell->setParam("\\D_REG", State::S0); + + cell->setParam("\\TOP_8x8_MULT_REG", st.ffY ? State::S1 : State::S0); + cell->setParam("\\BOT_8x8_MULT_REG", st.ffY ? State::S1 : State::S0); + cell->setParam("\\PIPELINE_16x16_MULT_REG1", st.ffY ? State::S1 : State::S0); + cell->setParam("\\PIPELINE_16x16_MULT_REG2", State::S0); + + cell->setParam("\\TOPOUTPUT_SELECT", Const(st.ffS ? 1 : 3, 2)); + cell->setParam("\\TOPADDSUB_LOWERINPUT", Const(2, 2)); + cell->setParam("\\TOPADDSUB_UPPERINPUT", State::S0); + cell->setParam("\\TOPADDSUB_CARRYSELECT", Const(3, 2)); + + cell->setParam("\\BOTOUTPUT_SELECT", Const(st.ffS ? 1 : 3, 2)); + cell->setParam("\\BOTADDSUB_LOWERINPUT", Const(2, 2)); + cell->setParam("\\BOTADDSUB_UPPERINPUT", State::S0); + cell->setParam("\\BOTADDSUB_CARRYSELECT", Const(0, 2)); + + cell->setParam("\\MODE_8x8", State::S0); + cell->setParam("\\A_SIGNED", mul_signed ? State::S1 : State::S0); + cell->setParam("\\B_SIGNED", mul_signed ? State::S1 : State::S0); + + pm.autoremove(st.mul); + pm.autoremove(st.ffY); + pm.autoremove(st.ffS); +} + +struct Ice40DspPass : public Pass { + Ice40DspPass() : Pass("ice40_dsp", "iCE40: map multipliers") { } + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" ice40_dsp [options] [selection]\n"); + log("\n"); + log("Map multipliers and multiply-accumulate blocks to iCE40 DSP resources.\n"); + log("\n"); + } + void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE + { + log_header(design, "Executing ICE40_DSP pass (map multipliers).\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()) + ice40_dsp_pm(module, module->selected_cells()).run_ice40_dsp(create_ice40_dsp); + } +} Ice40DspPass; + +PRIVATE_NAMESPACE_END diff --git a/passes/pmgen/ice40_dsp.pmg b/passes/pmgen/ice40_dsp.pmg new file mode 100644 index 000000000..7003092bb --- /dev/null +++ b/passes/pmgen/ice40_dsp.pmg @@ -0,0 +1,163 @@ +pattern ice40_dsp + +state <SigBit> clock +state <bool> clock_pol clock_vld +state <SigSpec> sigA sigB sigY sigS +state <Cell*> addAB muxAB + +match mul + select mul->type.in($mul) + select GetSize(mul->getPort(\A)) + GetSize(mul->getPort(\B)) > 10 + select GetSize(mul->getPort(\Y)) > 10 +endmatch + +match ffA + select ffA->type.in($dff) + // select nusers(port(ffA, \Q)) == 2 + index <SigSpec> port(ffA, \Q) === port(mul, \A) + optional +endmatch + +code sigA clock clock_pol clock_vld + sigA = port(mul, \A); + + if (ffA) { + sigA = port(ffA, \D); + + clock = port(ffA, \CLK).as_bit(); + clock_pol = param(ffA, \CLK_POLARITY).as_bool(); + clock_vld = true; + } +endcode + +match ffB + select ffB->type.in($dff) + // select nusers(port(ffB, \Q)) == 2 + index <SigSpec> port(ffB, \Q) === port(mul, \B) + optional +endmatch + +code sigB clock clock_pol clock_vld + sigB = port(mul, \B); + + if (ffB) { + sigB = port(ffB, \D); + SigBit c = port(ffB, \CLK).as_bit(); + bool cp = param(ffB, \CLK_POLARITY).as_bool(); + + if (clock_vld && (c != clock || cp != clock_pol)) + reject; + + clock = c; + clock_pol = cp; + clock_vld = true; + } +endcode + +match ffY + select ffY->type.in($dff) + select nusers(port(ffY, \D)) == 2 + index <SigSpec> port(ffY, \D) === port(mul, \Y) + optional +endmatch + +code sigY clock clock_pol clock_vld + sigY = port(mul, \Y); + + if (ffY) { + sigY = port(ffY, \Q); + SigBit c = port(ffY, \CLK).as_bit(); + bool cp = param(ffY, \CLK_POLARITY).as_bool(); + + if (clock_vld && (c != clock || cp != clock_pol)) + reject; + + clock = c; + clock_pol = cp; + clock_vld = true; + } +endcode + +match addA + select addA->type.in($add) + select nusers(port(addA, \A)) == 2 + index <SigSpec> port(addA, \A) === sigY + optional +endmatch + +match addB + if !addA + select addB->type.in($add, $sub) + select nusers(port(addB, \B)) == 2 + index <SigSpec> port(addB, \B) === sigY + optional +endmatch + +code addAB sigS + if (addA) { + addAB = addA; + sigS = port(addA, \B); + } + if (addB) { + addAB = addB; + sigS = port(addB, \A); + } + if (addAB) { + int natural_mul_width = GetSize(sigA) + GetSize(sigB); + int actual_mul_width = GetSize(sigY); + int actual_acc_width = GetSize(sigS); + + if ((actual_acc_width > actual_mul_width) && (natural_mul_width > actual_mul_width)) + reject; + if ((actual_acc_width != actual_mul_width) && (param(mul, \A_SIGNED).as_bool() != param(addAB, \A_SIGNED).as_bool())) + reject; + } +endcode + +match muxA + if addAB + select muxA->type.in($mux) + select nusers(port(muxA, \A)) == 2 + index <SigSpec> port(muxA, \A) === port(addAB, \Y) + optional +endmatch + +match muxB + if addAB + if !muxA + select muxB->type.in($mux) + select nusers(port(muxB, \B)) == 2 + index <SigSpec> port(muxB, \B) === port(addAB, \Y) + optional +endmatch + +code muxAB + muxAB = addAB; + if (muxA) + muxAB = muxA; + if (muxB) + muxAB = muxB; +endcode + +match ffS + if muxAB + select ffS->type.in($dff) + select nusers(port(ffS, \D)) == 2 + index <SigSpec> port(ffS, \D) === port(muxAB, \Y) + index <SigSpec> port(ffS, \Q) === sigS +endmatch + +code clock clock_pol clock_vld + if (ffS) { + SigBit c = port(ffS, \CLK).as_bit(); + bool cp = param(ffS, \CLK_POLARITY).as_bool(); + + if (clock_vld && (c != clock || cp != clock_pol)) + reject; + + clock = c; + clock_pol = cp; + clock_vld = true; + } + accept; +endcode diff --git a/passes/pmgen/ice40_wrapcarry.cc b/passes/pmgen/ice40_wrapcarry.cc new file mode 100644 index 000000000..69ef3cd82 --- /dev/null +++ b/passes/pmgen/ice40_wrapcarry.cc @@ -0,0 +1,90 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * 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/ice40_wrapcarry_pm.h" + +void create_ice40_wrapcarry(ice40_wrapcarry_pm &pm) +{ + auto &st = pm.st_ice40_wrapcarry; + +#if 0 + log("\n"); + log("carry: %s\n", log_id(st.carry, "--")); + log("lut: %s\n", log_id(st.lut, "--")); +#endif + + log(" replacing SB_LUT + SB_CARRY with $__ICE40_CARRY_WRAPPER cell.\n"); + + Cell *cell = pm.module->addCell(NEW_ID, "$__ICE40_CARRY_WRAPPER"); + pm.module->swap_names(cell, st.carry); + + cell->setPort("\\A", st.carry->getPort("\\I0")); + cell->setPort("\\B", st.carry->getPort("\\I1")); + cell->setPort("\\CI", st.carry->getPort("\\CI")); + cell->setPort("\\CO", st.carry->getPort("\\CO")); + + cell->setPort("\\I0", st.lut->getPort("\\I0")); + cell->setPort("\\I3", st.lut->getPort("\\I3")); + cell->setPort("\\O", st.lut->getPort("\\O")); + cell->setParam("\\LUT", st.lut->getParam("\\LUT_INIT")); + + pm.autoremove(st.carry); + pm.autoremove(st.lut); +} + +struct Ice40WrapCarryPass : public Pass { + Ice40WrapCarryPass() : Pass("ice40_wrapcarry", "iCE40: wrap carries") { } + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" ice40_wrapcarry [selection]\n"); + log("\n"); + log("Wrap manually instantiated SB_CARRY cells, along with their associated SB_LUTs,\n"); + log("into an internal $__ICE40_CARRY_WRAPPER cell for preservation across technology\n"); + log("mapping."); + log("\n"); + } + void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE + { + log_header(design, "Executing ICE40_WRAPCARRY pass (wrap carries).\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()) + ice40_wrapcarry_pm(module, module->selected_cells()).run_ice40_wrapcarry(create_ice40_wrapcarry); + } +} Ice40WrapCarryPass; + +PRIVATE_NAMESPACE_END diff --git a/passes/pmgen/ice40_wrapcarry.pmg b/passes/pmgen/ice40_wrapcarry.pmg new file mode 100644 index 000000000..9e64c7467 --- /dev/null +++ b/passes/pmgen/ice40_wrapcarry.pmg @@ -0,0 +1,11 @@ +pattern ice40_wrapcarry + +match carry + select carry->type.in(\SB_CARRY) +endmatch + +match lut + select lut->type.in(\SB_LUT4) + index <SigSpec> port(lut, \I1) === port(carry, \I0) + index <SigSpec> port(lut, \I2) === port(carry, \I1) +endmatch diff --git a/passes/pmgen/peepopt.cc b/passes/pmgen/peepopt.cc new file mode 100644 index 000000000..72b02127a --- /dev/null +++ b/passes/pmgen/peepopt.cc @@ -0,0 +1,69 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * 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 + +bool did_something; + +#include "passes/pmgen/peepopt_pm.h" + +struct PeepoptPass : public Pass { + PeepoptPass() : Pass("peepopt", "collection of peephole optimizers") { } + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" peepopt [options] [selection]\n"); + log("\n"); + log("This pass applies a collection of peephole optimizers to the current design.\n"); + log("\n"); + } + void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE + { + log_header(design, "Executing PEEPOPT pass (run peephole optimizers).\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()) { + did_something = true; + while (did_something) { + did_something = false; + peepopt_pm pm(module, module->selected_cells()); + pm.run_shiftmul(); + pm.run_muldiv(); + pm.run_dffmux(); + } + } + } +} PeepoptPass; + +PRIVATE_NAMESPACE_END diff --git a/passes/pmgen/peepopt_dffmux.pmg b/passes/pmgen/peepopt_dffmux.pmg new file mode 100644 index 000000000..c88a52226 --- /dev/null +++ b/passes/pmgen/peepopt_dffmux.pmg @@ -0,0 +1,113 @@ +pattern dffmux + +state <IdString> cemuxAB rstmuxBA +state <SigSpec> sigD + +match dff + select dff->type == $dff + select GetSize(port(dff, \D)) > 1 +endmatch + +match rstmux + select rstmux->type == $mux + select GetSize(port(rstmux, \Y)) > 1 + index <SigSpec> port(rstmux, \Y) === port(dff, \D) + choice <IdString> BA {\B, \A} + select port(rstmux, BA).is_fully_const() + set rstmuxBA BA + optional +endmatch + +code sigD + if (rstmux) + sigD = port(rstmux, rstmuxBA == \B ? \A : \B); + else + sigD = port(dff, \D); +endcode + +match cemux + select cemux->type == $mux + select GetSize(port(cemux, \Y)) > 1 + index <SigSpec> port(cemux, \Y) === sigD + choice <IdString> AB {\A, \B} + index <SigSpec> port(cemux, AB) === port(dff, \Q) + set cemuxAB AB +endmatch + +code + SigSpec D = port(cemux, cemuxAB == \A ? \B : \A); + SigSpec Q = port(dff, \Q); + Const rst; + if (rstmux) + rst = port(rstmux, rstmuxBA).as_const(); + int width = GetSize(D); + + SigSpec &ceA = cemux->connections_.at(\A); + SigSpec &ceB = cemux->connections_.at(\B); + SigSpec &ceY = cemux->connections_.at(\Y); + SigSpec &dffD = dff->connections_.at(\D); + SigSpec &dffQ = dff->connections_.at(\Q); + + if (D[width-1] == D[width-2]) { + did_something = true; + + SigBit sign = D[width-1]; + bool is_signed = sign.wire; + int i; + for (i = width-1; i >= 2; i--) { + if (!is_signed) { + module->connect(Q[i], sign); + if (D[i-1] != sign || (rst.size() && rst[i-1] != rst[width-1])) + break; + } + else { + module->connect(Q[i], Q[i-1]); + if (D[i-2] != sign || (rst.size() && rst[i-1] != rst[width-1])) + break; + } + } + + ceA.remove(i, width-i); + ceB.remove(i, width-i); + ceY.remove(i, width-i); + cemux->fixup_parameters(); + dffD.remove(i, width-i); + dffQ.remove(i, width-i); + dff->fixup_parameters(); + + log("dffcemux pattern in %s: dff=%s, cemux=%s; removed top %d bits.\n", log_id(module), log_id(dff), log_id(cemux), width-i); + accept; + } + else { + int count = 0; + for (int i = width-1; i >= 0; i--) { + if (D[i].wire) + continue; + Wire *w = Q[i].wire; + auto it = w->attributes.find(\init); + State init; + if (it != w->attributes.end()) + init = it->second[Q[i].offset]; + else + init = State::Sx; + + if (init == State::Sx || init == D[i].data) { + count++; + module->connect(Q[i], D[i]); + ceA.remove(i); + ceB.remove(i); + ceY.remove(i); + dffD.remove(i); + dffQ.remove(i); + } + } + if (count > 0) { + did_something = true; + cemux->fixup_parameters(); + dff->fixup_parameters(); + log("dffcemux pattern in %s: dff=%s, cemux=%s; removed %d constant bits.\n", log_id(module), log_id(dff), log_id(cemux), count); + } + + accept; + } +endcode diff --git a/passes/pmgen/peepopt_muldiv.pmg b/passes/pmgen/peepopt_muldiv.pmg new file mode 100644 index 000000000..7cad759d0 --- /dev/null +++ b/passes/pmgen/peepopt_muldiv.pmg @@ -0,0 +1,36 @@ +pattern muldiv + +state <SigSpec> t x y + +match mul + select mul->type == $mul + select GetSize(port(mul, \A)) + GetSize(port(mul, \B)) <= GetSize(port(mul, \Y)) +endmatch + +code t x y + t = port(mul, \Y); + x = port(mul, \A); + y = port(mul, \B); + branch; + std::swap(x, y); +endcode + +match div + select div->type.in($div) + index <SigSpec> port(div, \A) === t + index <SigSpec> port(div, \B) === x +endmatch + +code + SigSpec div_y = port(div, \Y); + SigSpec val_y = y; + + if (GetSize(div_y) != GetSize(val_y)) + val_y.extend_u0(GetSize(div_y), param(div, \A_SIGNED).as_bool()); + + did_something = true; + log("muldiv pattern in %s: mul=%s, div=%s\n", log_id(module), log_id(mul), log_id(div)); + module->connect(div_y, val_y); + autoremove(div); + accept; +endcode diff --git a/passes/pmgen/peepopt_shiftmul.pmg b/passes/pmgen/peepopt_shiftmul.pmg new file mode 100644 index 000000000..d4748ae19 --- /dev/null +++ b/passes/pmgen/peepopt_shiftmul.pmg @@ -0,0 +1,96 @@ +pattern shiftmul +// +// Optimize mul+shift pairs that result from expressions such as foo[s*W+:W] +// + +state <SigSpec> shamt + +match shift + select shift->type.in($shift, $shiftx, $shr) +endmatch + +code shamt + shamt = port(shift, \B); + if (shamt.empty()) + reject; + if (shamt[GetSize(shamt)-1] == State::S0) { + do { + shamt.remove(GetSize(shamt)-1); + if (shamt.empty()) + reject; + } while (shamt[GetSize(shamt)-1] == State::S0); + } else + if (shift->type.in($shift, $shiftx) && param(shift, \B_SIGNED).as_bool()) { + reject; + } + if (GetSize(shamt) > 20) + reject; +endcode + +match mul + select mul->type.in($mul) + select port(mul, \A).is_fully_const() || port(mul, \B).is_fully_const() + index <SigSpec> port(mul, \Y) === shamt +endmatch + +code +{ + IdString const_factor_port = port(mul, \A).is_fully_const() ? \A : \B; + IdString const_factor_signed = const_factor_port == \A ? \A_SIGNED : \B_SIGNED; + Const const_factor_cnst = port(mul, const_factor_port).as_const(); + int const_factor = const_factor_cnst.as_int(); + + if (GetSize(const_factor_cnst) == 0) + reject; + + if (const_factor_cnst.bits[GetSize(const_factor_cnst)-1] != State::S0 && + param(mul, const_factor_signed).as_bool()) + reject; + + if (GetSize(const_factor_cnst) > 20) + reject; + + if (GetSize(port(shift, \Y)) > const_factor) + reject; + + int factor_bits = ceil_log2(const_factor); + SigSpec mul_din = port(mul, const_factor_port == \A ? \B : \A); + + if (GetSize(shamt) < factor_bits+GetSize(mul_din)) + reject; + + did_something = true; + log("shiftmul pattern in %s: shift=%s, mul=%s\n", log_id(module), log_id(shift), log_id(mul)); + + int new_const_factor = 1 << factor_bits; + SigSpec padding(State::Sx, new_const_factor-const_factor); + SigSpec old_a = port(shift, \A), new_a; + int trunc = 0; + + if (GetSize(old_a) % const_factor != 0) { + trunc = const_factor - GetSize(old_a) % const_factor; + old_a.append(SigSpec(State::Sx, trunc)); + } + + for (int i = 0; i*const_factor < GetSize(old_a); i++) { + SigSpec slice = old_a.extract(i*const_factor, const_factor); + new_a.append(slice); + new_a.append(padding); + } + + if (trunc > 0) + new_a.remove(GetSize(new_a)-trunc, trunc); + + SigSpec new_b = {mul_din, SigSpec(State::S0, factor_bits)}; + if (param(shift, \B_SIGNED).as_bool()) + new_b.append(State::S0); + + shift->setPort(\A, new_a); + shift->setParam(\A_WIDTH, GetSize(new_a)); + shift->setPort(\B, new_b); + shift->setParam(\B_WIDTH, GetSize(new_b)); + + blacklist(shift); + accept; +} +endcode diff --git a/passes/pmgen/pmgen.py b/passes/pmgen/pmgen.py new file mode 100644 index 000000000..573722d68 --- /dev/null +++ b/passes/pmgen/pmgen.py @@ -0,0 +1,774 @@ +#!/usr/bin/env python3 + +import re +import sys +import pprint +import getopt + +pp = pprint.PrettyPrinter(indent=4) + +prefix = None +pmgfiles = list() +outfile = None +debug = False +genhdr = False + +opts, args = getopt.getopt(sys.argv[1:], "p:o:dg") + +for o, a in opts: + if o == "-p": + prefix = a + elif o == "-o": + outfile = a + elif o == "-d": + debug = True + elif o == "-g": + genhdr = True + +if outfile is None: + outfile = "/dev/stdout" + +for a in args: + assert a.endswith(".pmg") + if prefix is None and len(args) == 1: + prefix = a[0:-4] + prefix = prefix.split('/')[-1] + pmgfiles.append(a) + +assert prefix is not None + +current_pattern = None +current_subpattern = None +patterns = dict() +subpatterns = dict() +subpattern_args = dict() +state_types = dict() +udata_types = dict() +blocks = list() +ids = dict() + +def rewrite_cpp(s): + t = list() + i = 0 + while i < len(s): + if s[i] in ("'", '"') and i + 1 < len(s): + j = i + 1 + while j + 1 < len(s) and s[j] != s[i]: + if s[j] == '\\' and j + 1 < len(s): + j += 1 + j += 1 + t.append(s[i:j+1]) + i = j + 1 + continue + + if s[i] in ('$', '\\') and i + 1 < len(s): + j = i + 1 + while True: + if j == len(s): + j -= 1 + break + if ord('a') <= ord(s[j]) <= ord('z'): + j += 1 + continue + if ord('A') <= ord(s[j]) <= ord('Z'): + j += 1 + continue + if ord('0') <= ord(s[j]) <= ord('9'): + j += 1 + continue + if s[j] == '_': + j += 1 + continue + j -= 1 + break + + n = s[i:j+1] + i = j + 1 + + if n[0] == '$': + v = "id_d_" + n[1:] + else: + v = "id_b_" + n[1:] + + if v not in ids: + ids[v] = n + else: + assert ids[v] == n + + t.append(v) + continue + + if s[i] == "\t": + t.append(" ") + else: + t.append(s[i]) + + i += 1 + + return "".join(t) + +def process_pmgfile(f, filename): + linenr = 0 + global current_pattern + global current_subpattern + while True: + linenr += 1 + line = f.readline() + if line == "": break + line = line.strip() + + cmd = line.split() + if len(cmd) == 0 or cmd[0].startswith("//"): continue + cmd = cmd[0] + + if cmd == "pattern": + if current_pattern is not None: + block = dict() + block["type"] = "final" + block["pattern"] = (current_pattern, current_subpattern) + blocks.append(block) + line = line.split() + assert len(line) == 2 + assert line[1] not in patterns + current_pattern = line[1] + current_subpattern = "" + patterns[current_pattern] = len(blocks) + subpatterns[(current_pattern, current_subpattern)] = len(blocks) + subpattern_args[(current_pattern, current_subpattern)] = list() + state_types[current_pattern] = dict() + udata_types[current_pattern] = dict() + continue + + assert current_pattern is not None + + if cmd == "fallthrough": + block = dict() + block["type"] = "fallthrough" + blocks.append(block) + line = line.split() + assert len(line) == 1 + continue + + if cmd == "subpattern": + if len(blocks) == 0 or blocks[-1]["type"] != "fallthrough": + block = dict() + block["type"] = "final" + block["pattern"] = (current_pattern, current_subpattern) + blocks.append(block) + elif len(blocks) and blocks[-1]["type"] == "fallthrough": + del blocks[-1] + line = line.split() + assert len(line) == 2 + current_subpattern = line[1] + subpattern_args[(current_pattern, current_subpattern)] = list() + assert (current_pattern, current_subpattern) not in subpatterns + subpatterns[(current_pattern, current_subpattern)] = len(blocks) + continue + + if cmd == "arg": + line = line.split() + assert len(line) > 1 + subpattern_args[(current_pattern, current_subpattern)] += line[1:] + continue + + if cmd == "state": + 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) + assert m + type_str = m.group(1) + states_str = m.group(2) + for s in re.split(r"\s+", states_str): + assert s not in state_types[current_pattern] + state_types[current_pattern][s] = type_str + continue + + if cmd == "udata": + 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) + assert m + type_str = m.group(1) + udatas_str = m.group(2) + for s in re.split(r"\s+", udatas_str): + assert s not in udata_types[current_pattern] + udata_types[current_pattern][s] = type_str + continue + + if cmd == "match": + block = dict() + block["type"] = "match" + block["src"] = "%s:%d" % (filename, linenr) + block["pattern"] = (current_pattern, current_subpattern) + + block["genargs"] = None + block["gencode"] = None + + line = line.split() + assert len(line) == 2 + assert (line[1] not in state_types[current_pattern]) or (state_types[current_pattern][line[1]] == "Cell*") + block["cell"] = line[1] + state_types[current_pattern][line[1]] = "Cell*"; + + block["if"] = list() + block["setup"] = list() + block["index"] = list() + block["filter"] = list() + block["sets"] = list() + block["optional"] = False + block["semioptional"] = False + + while True: + linenr += 1 + l = f.readline() + assert l != "" + a = l.split() + if len(a) == 0 or a[0].startswith("//"): continue + if a[0] == "endmatch": break + + if a[0] == "if": + b = l.lstrip()[2:] + block["if"].append(rewrite_cpp(b.strip())) + continue + + if a[0] == "select": + b = l.lstrip()[6:] + 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": + m = re.match(r"^\s*index\s+<(.*?)>\s+(.*?)\s*===\s*(.*?)\s*$", l) + assert m + block["index"].append((m.group(1), rewrite_cpp(m.group(2)), rewrite_cpp(m.group(3)))) + continue + + if a[0] == "filter": + b = l.lstrip()[6:] + 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 + + if a[0] == "semioptional": + block["semioptional"] = True + continue + + 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() + while True: + linenr += 1 + l = f.readline() + assert l != "" + a = l.split() + if len(a) == 1 and a[0] == "endmatch": break + block["gencode"].append(rewrite_cpp(l.rstrip())) + break + + assert False + + if block["optional"]: + assert not block["semioptional"] + + blocks.append(block) + continue + + if cmd == "code": + block = dict() + block["type"] = "code" + block["src"] = "%s:%d" % (filename, linenr) + block["pattern"] = (current_pattern, current_subpattern) + + block["code"] = list() + block["fcode"] = list() + block["states"] = set() + + for s in line.split()[1:]: + assert s in state_types[current_pattern] + block["states"].add(s) + + codetype = "code" + + while True: + linenr += 1 + l = f.readline() + assert l != "" + a = l.split() + if len(a) == 0: continue + if a[0] == "endcode": break + + if a[0] == "finally": + codetype = "fcode" + continue + + block[codetype].append(rewrite_cpp(l.rstrip())) + + blocks.append(block) + continue + + assert False + +for fn in pmgfiles: + with open(fn, "r") as f: + process_pmgfile(f, fn) + +if current_pattern is not None: + block = dict() + block["type"] = "final" + block["pattern"] = (current_pattern, current_subpattern) + blocks.append(block) + +current_pattern = None +current_subpattern = None + +if debug: + pp.pprint(blocks) + +with open(outfile, "w") as f: + for fn in pmgfiles: + print("// Generated by pmgen.py from {}".format(fn), file=f) + print("", file=f) + + if genhdr: + print("#include \"kernel/yosys.h\"", file=f) + print("#include \"kernel/sigtools.h\"", file=f) + print("", file=f) + print("YOSYS_NAMESPACE_BEGIN", file=f) + print("", file=f) + + print("struct {}_pm {{".format(prefix), file=f) + print(" Module *module;", file=f) + print(" SigMap sigmap;", file=f) + print(" std::function<void()> on_accept;", file=f) + print(" bool generate_mode;", file=f) + print(" int accept_cnt;", file=f) + print("", file=f) + + print(" uint32_t rngseed;", file=f) + print(" int rng(unsigned int n) {", file=f) + print(" rngseed ^= rngseed << 13;", file=f) + print(" rngseed ^= rngseed >> 17;", file=f) + print(" rngseed ^= rngseed << 5;", file=f) + print(" return rngseed % n;", file=f) + print(" }", file=f) + print("", file=f) + + for index in range(len(blocks)): + block = blocks[index] + if block["type"] == "match": + 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(" 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) + print(" dict<Cell*,int> rollback_cache;", file=f) + print(" int rollback;", file=f) + print("", file=f) + + for current_pattern in sorted(patterns.keys()): + print(" struct state_{}_t {{".format(current_pattern), file=f) + for s, t in sorted(state_types[current_pattern].items()): + print(" {} {};".format(t, s), file=f) + print(" }} st_{};".format(current_pattern), file=f) + print("", file=f) + + print(" struct udata_{}_t {{".format(current_pattern), file=f) + for s, t in sorted(udata_types[current_pattern].items()): + print(" {} {};".format(t, s), file=f) + print(" }} ud_{};".format(current_pattern), file=f) + print("", file=f) + current_pattern = None + + for v, n in sorted(ids.items()): + if n[0] == "\\": + print(" IdString {}{{\"\\{}\"}};".format(v, n), file=f) + else: + print(" IdString {}{{\"{}\"}};".format(v, n), file=f) + print("", file=f) + + print(" void add_siguser(const SigSpec &sig, Cell *cell) {", file=f) + print(" for (auto bit : sigmap(sig)) {", file=f) + print(" if (bit.wire == nullptr) continue;", file=f) + print(" sigusers[bit].insert(cell);", file=f) + print(" }", file=f) + print(" }", file=f) + print("", file=f) + + print(" void blacklist(Cell *cell) {", file=f) + print(" if (cell != nullptr && blacklist_cells.insert(cell).second) {", file=f) + print(" auto ptr = rollback_cache.find(cell);", file=f) + print(" if (ptr == rollback_cache.end()) return;", file=f) + print(" int rb = ptr->second;", file=f) + print(" if (rollback == 0 || rollback > rb)", file=f) + print(" rollback = rb;", file=f) + print(" }", file=f) + print(" }", file=f) + print("", file=f) + + print(" void autoremove(Cell *cell) {", file=f) + print(" if (cell != nullptr) {", file=f) + print(" autoremove_cells.insert(cell);", file=f) + print(" blacklist(cell);", file=f) + print(" }", file=f) + print(" }", file=f) + print("", file=f) + + current_pattern = None + + print(" SigSpec port(Cell *cell, IdString portname) {", file=f) + print(" return sigmap(cell->getPort(portname));", file=f) + print(" }", file=f) + print("", file=f) + + print(" Const param(Cell *cell, IdString paramname) {", file=f) + print(" return cell->getParam(paramname);", file=f) + print(" }", file=f) + print("", file=f) + + print(" int nusers(const SigSpec &sig) {", file=f) + print(" pool<Cell*> users;", file=f) + print(" for (auto bit : sigmap(sig))", file=f) + print(" for (auto user : sigusers[bit])", file=f) + print(" users.insert(user);", file=f) + print(" return GetSize(users);", file=f) + print(" }", file=f) + print("", file=f) + + print(" {}_pm(Module *module, const vector<Cell*> &cells) :".format(prefix), file=f) + print(" module(module), sigmap(module), generate_mode(false), rngseed(12345678) {", file=f) + for current_pattern in sorted(patterns.keys()): + for s, t in sorted(udata_types[current_pattern].items()): + if t.endswith("*"): + print(" ud_{}.{} = nullptr;".format(current_pattern,s), file=f) + else: + print(" ud_{}.{} = {}();".format(current_pattern, s, t), file=f) + current_pattern = None + print(" for (auto port : module->ports)", file=f) + print(" add_siguser(module->wire(port), nullptr);", 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)): + block = blocks[index] + if block["type"] == "match": + print(" do {", file=f) + print(" Cell *{} = cell;".format(block["cell"]), 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(value);".format(index), file=f) + for i in range(loopcnt): + print(" }", file=f) + print(" } while (0);", file=f) + + print(" }", file=f) + print(" }", file=f) + print("", file=f) + + print(" ~{}_pm() {{".format(prefix), file=f) + print(" for (auto cell : autoremove_cells)", file=f) + print(" module->remove(cell);", file=f) + print(" }", file=f) + print("", file=f) + + for current_pattern in sorted(patterns.keys()): + print(" int run_{}(std::function<void()> on_accept_f) {{".format(current_pattern), file=f) + print(" accept_cnt = 0;", file=f) + print(" on_accept = on_accept_f;", file=f) + print(" rollback = 0;", file=f) + for s, t in sorted(state_types[current_pattern].items()): + if t.endswith("*"): + print(" st_{}.{} = nullptr;".format(current_pattern, s), file=f) + else: + print(" st_{}.{} = {}();".format(current_pattern, s, t), file=f) + print(" block_{}(1);".format(patterns[current_pattern]), file=f) + print(" log_assert(rollback_cache.empty());", file=f) + print(" return accept_cnt;", file=f) + print(" }", file=f) + print("", file=f) + print(" int run_{}(std::function<void({}_pm&)> on_accept_f) {{".format(current_pattern, prefix), file=f) + print(" return run_{}([&](){{on_accept_f(*this);}});".format(current_pattern), file=f) + print(" }", file=f) + print("", file=f) + print(" int run_{}() {{".format(current_pattern), file=f) + print(" return run_{}([](){{}});".format(current_pattern, current_pattern), file=f) + print(" }", file=f) + print("", file=f) + + if len(subpatterns): + for p, s in sorted(subpatterns.keys()): + print(" void block_subpattern_{}_{}(int recursion) {{ block_{}(recursion); }}".format(p, s, subpatterns[(p, s)]), file=f) + print("", file=f) + + current_pattern = None + current_subpattern = None + + for index in range(len(blocks)): + block = blocks[index] + + if block["type"] in ("match", "code"): + print(" // {}".format(block["src"]), file=f) + + print(" void block_{}(int recursion YS_ATTRIBUTE(unused)) {{".format(index), file=f) + current_pattern, current_subpattern = block["pattern"] + + if block["type"] == "final": + print(" }", file=f) + if index+1 != len(blocks): + print("", file=f) + continue + + const_st = set() + nonconst_st = set() + restore_st = set() + + for s in subpattern_args[(current_pattern, current_subpattern)]: + const_st.add(s) + + for i in range(subpatterns[(current_pattern, current_subpattern)], index): + if blocks[i]["type"] == "code": + for s in blocks[i]["states"]: + 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 + + if block["type"] == "code": + for s in block["states"]: + if s in const_st: + const_st.remove(s) + restore_st.add(s) + nonconst_st.add(s) + elif block["type"] == "match": + 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 + + for s in sorted(const_st): + t = state_types[current_pattern][s] + if t.endswith("*"): + print(" {} const &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f) + else: + print(" const {} &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f) + + for s in sorted(nonconst_st): + t = state_types[current_pattern][s] + print(" {} &{} YS_ATTRIBUTE(unused) = st_{}.{};".format(t, s, current_pattern, s), file=f) + + for u in sorted(udata_types[current_pattern].keys()): + t = udata_types[current_pattern][u] + print(" {} &{} YS_ATTRIBUTE(unused) = ud_{}.{};".format(t, u, current_pattern, u), file=f) + + if len(restore_st): + print("", file=f) + for s in sorted(restore_st): + t = state_types[current_pattern][s] + print(" {} _pmg_backup_{} = {};".format(t, s, s), file=f) + + if block["type"] == "code": + print("", file=f) + print("#define reject do { goto rollback_label; } while(0)", file=f) + print("#define accept do { accept_cnt++; on_accept(); if (rollback) goto rollback_label; } while(0)", file=f) + print("#define finish do { rollback = -1; goto rollback_label; } while(0)", file=f) + print("#define branch do {{ block_{}(recursion+1); if (rollback) goto rollback_label; }} while(0)".format(index+1), file=f) + print("#define subpattern(pattern_name) do {{ block_subpattern_{}_ ## pattern_name (recursion+1); if (rollback) goto rollback_label; }} while(0)".format(current_pattern), file=f) + + for line in block["code"]: + print(" " + line, file=f) + + print("", file=f) + print(" block_{}(recursion+1);".format(index+1), file=f) + + print("#undef reject", file=f) + print("#undef accept", file=f) + print("#undef finish", file=f) + print("#undef branch", file=f) + print("#undef subpattern", file=f) + + print("", file=f) + print("rollback_label:", file=f) + print(" YS_ATTRIBUTE(unused);", file=f) + + if len(block["fcode"]): + print("#define accept do { accept_cnt++; on_accept(); } while(0)", file=f) + print("#define finish do { rollback = -1; goto finish_label; } while(0)", file=f) + for line in block["fcode"]: + print(" " + line, file=f) + print("finish_label:", file=f) + print(" YS_ATTRIBUTE(unused);", file=f) + print("#undef accept", file=f) + print("#undef finish", file=f) + + if len(restore_st) or len(nonconst_st): + print("", file=f) + for s in sorted(restore_st): + t = state_types[current_pattern][s] + 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] + if t.endswith("*"): + print(" {} = nullptr;".format(s), file=f) + else: + print(" {} = {}();".format(s, t), file=f) + + elif block["type"] == "match": + assert len(restore_st) == 0 + + print(" Cell* _pmg_backup_{} = {};".format(block["cell"], block["cell"]), file=f) + + if len(block["if"]): + for expr in block["if"]: + print("", file=f) + print(" if (!({})) {{".format(expr), file=f) + print(" {} = nullptr;".format(block["cell"]), file=f) + print(" block_{}(recursion+1);".format(index+1), file=f) + print(" {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f) + print(" return;", file=f) + print(" }", file=f) + + print("", file=f) + print(" index_{}_key_type key;".format(index), file=f) + for field, entry in enumerate(block["index"]): + print(" std::get<{}>(key) = {};".format(field, entry[2]), file=f) + print(" auto cells_ptr = index_{}.find(key);".format(index), file=f) + + if block["semioptional"] or block["genargs"] is not None: + print(" bool found_any_match = false;", file=f) + + print("", file=f) + print(" if (cells_ptr != index_{}.end()) {{".format(index), 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) + 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(" {} = _pmg_backup_{};".format(block["cell"], block["cell"]), file=f) + print(" return;", file=f) + print(" }", file=f) + print(" rollback = 0;", file=f) + print(" }", file=f) + print(" }", file=f) + print(" }", file=f) + + print("", file=f) + print(" {} = nullptr;".format(block["cell"]), file=f) + + if block["optional"]: + print(" block_{}(recursion+1);".format(index+1), file=f) + + if block["semioptional"]: + print(" if (!found_any_match) block_{}(recursion+1);".format(index+1), 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 && 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) + print("#undef finish", file=f) + else: + assert False + + current_pattern = None + print(" }", file=f) + print("", file=f) + + print("};", file=f) + + if genhdr: + print("", file=f) + print("YOSYS_NAMESPACE_END", file=f) diff --git a/passes/pmgen/test_pmgen.cc b/passes/pmgen/test_pmgen.cc new file mode 100644 index 000000000..4f3eec935 --- /dev/null +++ b/passes/pmgen/test_pmgen.cc @@ -0,0 +1,385 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * + * 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 + +// for peepopt_pm +bool did_something; + +#include "passes/pmgen/test_pmgen_pm.h" +#include "passes/pmgen/ice40_dsp_pm.h" +#include "passes/pmgen/xilinx_srl_pm.h" +#include "passes/pmgen/peepopt_pm.h" + +void reduce_chain(test_pmgen_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)); +} + +void reduce_tree(test_pmgen_pm &pm) +{ + auto &st = pm.st_reduce; + auto &ud = pm.ud_reduce; + + if (ud.longest_chain.empty()) + return; + + SigSpec A = ud.leaves; + SigSpec Y = st.first->getPort(ID(Y)); + pm.autoremove(st.first); + + log("Found %s tree with %d leaves for %s (%s).\n", log_id(st.first->type), + GetSize(A), log_signal(Y), log_id(st.first)); + + Cell *c; + + if (st.first->type == ID($_AND_)) + c = pm.module->addReduceAnd(NEW_ID, A, Y); + else if (st.first->type == ID($_OR_)) + c = pm.module->addReduceOr(NEW_ID, A, Y); + else if (st.first->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)); +} + +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) + +void pmtest_addports(Module *module) +{ + pool<SigBit> driven_bits, used_bits; + SigMap sigmap(module); + int icnt = 0, ocnt = 0; + + for (auto cell : module->cells()) + for (auto conn : cell->connections()) + { + if (cell->input(conn.first)) + for (auto bit : sigmap(conn.second)) + used_bits.insert(bit); + if (cell->output(conn.first)) + for (auto bit : sigmap(conn.second)) + driven_bits.insert(bit); + } + + for (auto wire : vector<Wire*>(module->wires())) + { + SigSpec ibits, obits; + for (auto bit : sigmap(wire)) { + if (!used_bits.count(bit)) + obits.append(bit); + if (!driven_bits.count(bit)) + ibits.append(bit); + } + if (!ibits.empty()) { + Wire *w = module->addWire(stringf("\\i%d", icnt++), GetSize(ibits)); + w->port_input = true; + module->connect(ibits, w); + } + if (!obits.empty()) { + Wire *w = module->addWire(stringf("\\o%d", ocnt++), GetSize(obits)); + w->port_output = true; + module->connect(w, obits); + } + } + + module->fixup_ports(); +} + +template <class pm> +void generate_pattern(std::function<void(pm&,std::function<void()>)> run, const char *pmclass, const char *pattern, Design *design) +{ + 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 < maxmodcnt) + { + int submodcnt = 0, itercnt = 0, cellcnt = 0; + Module *mod = design->addModule(NEW_ID); + + while (modcnt < maxmodcnt && submodcnt < maxsubcnt && itercnt++ < 1000) + { + if (timeout++ > 10000) + log_error("pmgen generator is stuck: 10000 iterations with no matching module generated.\n"); + + pm matcher(mod, mod->cells()); + + matcher.rng(1); + matcher.rngseed += modcnt; + matcher.rng(1); + matcher.rngseed += submodcnt; + matcher.rng(1); + matcher.rngseed += itercnt; + matcher.rng(1); + matcher.rngseed += cellcnt; + matcher.rng(1); + + if (GetSize(mod->cells()) != cellcnt) + { + bool found_match = false; + run(matcher, [&](){ found_match = true; }); + cellcnt = GetSize(mod->cells()); + + if (found_match) { + Module *m = design->addModule(stringf("\\pmtest_%s_%s_%05d", + pmclass, pattern, modcnt++)); + log("Creating module %s with %d cells.\n", log_id(m), cellcnt); + mod->cloneInto(m); + pmtest_addports(m); + mods.push_back(m); + submodcnt++; + timeout = 0; + } + } + + matcher.generate_mode = true; + run(matcher, [](){}); + } + + if (submodcnt && maxsubcnt < (1 << 16)) + maxsubcnt *= 2; + + design->remove(mod); + } + + Module *m = design->addModule(stringf("\\pmtest_%s_%s", pmclass, pattern)); + log("Creating module %s with %d cells.\n", log_id(m), GetSize(mods)); + for (auto mod : mods) { + Cell *c = m->addCell(mod->name, mod->name); + for (auto port : mod->ports) { + Wire *w = m->addWire(NEW_ID, GetSize(mod->wire(port))); + c->setPort(port, w); + } + } + pmtest_addports(m); +} + +struct TestPmgenPass : public Pass { + TestPmgenPass() : Pass("test_pmgen", "test pass for pmgen") { } + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" test_pmgen -reduce_chain [options] [selection]\n"); + log("\n"); + log("Demo for recursive pmgen patterns. Map chains of AND/OR/XOR to $reduce_*.\n"); + log("\n"); + + log("\n"); + log(" test_pmgen -reduce_tree [options] [selection]\n"); + log("\n"); + 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"); + log("Create modules that match the specified pattern.\n"); + log("\n"); + } + + void execute_reduce_chain(std::vector<std::string> args, RTLIL::Design *design) + { + log_header(design, "Executing TEST_PMGEN pass (-reduce_chain).\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()) + while (test_pmgen_pm(module, module->selected_cells()).run_reduce(reduce_chain)) {} + } + + void execute_reduce_tree(std::vector<std::string> args, RTLIL::Design *design) + { + log_header(design, "Executing TEST_PMGEN pass (-reduce_tree).\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_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"); + + size_t argidx; + for (argidx = 2; argidx < args.size(); argidx++) + { + // if (args[argidx] == "-singleton") { + // singleton_mode = true; + // continue; + // } + break; + } + + if (argidx+1 != args.size()) + log_cmd_error("Expected exactly one pattern.\n"); + + string pattern = args[argidx]; + + 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); + + if (pattern == "xilinx_srl.fixed") + return GENERATE_PATTERN(xilinx_srl_pm, fixed); + if (pattern == "xilinx_srl.variable") + return GENERATE_PATTERN(xilinx_srl_pm, variable); + + if (pattern == "peepopt-muldiv") + return GENERATE_PATTERN(peepopt_pm, muldiv); + + if (pattern == "peepopt-shiftmul") + return GENERATE_PATTERN(peepopt_pm, shiftmul); + + log_cmd_error("Unknown pattern: %s\n", pattern.c_str()); + } + + void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE + { + if (GetSize(args) > 1) + { + if (args[1] == "-reduce_chain") + 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); + } + help(); + log_cmd_error("Missing or unsupported mode parameter.\n"); + } +} TestPmgenPass; + +PRIVATE_NAMESPACE_END diff --git a/passes/pmgen/test_pmgen.pmg b/passes/pmgen/test_pmgen.pmg new file mode 100644 index 000000000..287ed97d8 --- /dev/null +++ b/passes/pmgen/test_pmgen.pmg @@ -0,0 +1,189 @@ +pattern reduce + +state <IdString> portname +udata <vector<pair<Cell*, IdString>>> chain longest_chain +udata <pool<Cell*>> non_first_cells +udata <SigSpec> leaves + +code + non_first_cells.clear(); + subpattern(setup); +endcode + +match first + select first->type.in($_AND_, $_OR_, $_XOR_) + filter !non_first_cells.count(first) +generate + SigSpec A = module->addWire(NEW_ID); + SigSpec B = module->addWire(NEW_ID); + SigSpec Y = module->addWire(NEW_ID); + switch (rng(3)) + { + case 0: + module->addAndGate(NEW_ID, A, B, Y); + break; + case 1: + module->addOrGate(NEW_ID, A, B, Y); + break; + case 2: + module->addXorGate(NEW_ID, A, B, Y); + break; + } +endmatch + +code + leaves = SigSpec(); + 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()); + if (GetSize(longest_chain) > 1) + accept; +endcode + +// ------------------------------------------------------------------ + +subpattern setup + +match first + select first->type.in($_AND_, $_OR_, $_XOR_) +endmatch + +code portname + portname = \A; + branch; + portname = \B; +endcode + +match next + 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 + +code + non_first_cells.insert(next); +endcode + +// ------------------------------------------------------------------ + +subpattern tail +arg first + +match next + semioptional + 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 + SigSpec A = module->addWire(NEW_ID); + SigSpec B = module->addWire(NEW_ID); + SigSpec Y = port(chain.back().first, chain.back().second); + Cell *c = module->addAndGate(NEW_ID, A, B, Y); + c->type = chain.back().first->type; +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; + leaves.append(port(chain.back().first, chain.back().second)); + } +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 diff --git a/passes/pmgen/xilinx_srl.cc b/passes/pmgen/xilinx_srl.cc new file mode 100644 index 000000000..3d264e8d4 --- /dev/null +++ b/passes/pmgen/xilinx_srl.cc @@ -0,0 +1,258 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> + * (C) 2019 Eddie Hung <eddie@fpgeh.com> + * + * 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/xilinx_srl_pm.h" + +void run_fixed(xilinx_srl_pm &pm) +{ + auto &st = pm.st_fixed; + auto &ud = pm.ud_fixed; + log("Found fixed chain of length %d (%s):\n", GetSize(ud.longest_chain), log_id(st.first->type)); + + SigSpec initval; + for (auto cell : ud.longest_chain) { + log_debug(" %s\n", log_id(cell)); + if (cell->type.in(ID($_DFF_N_), ID($_DFF_P_), ID($_DFFE_NN_), ID($_DFFE_NP_), ID($_DFFE_PN_), ID($_DFFE_PP_))) { + SigBit Q = cell->getPort(ID(Q)); + log_assert(Q.wire); + auto it = Q.wire->attributes.find(ID(init)); + if (it != Q.wire->attributes.end()) { + auto &i = it->second[Q.offset]; + initval.append(i); + i = State::Sx; + } + else + initval.append(State::Sx); + } + else if (cell->type.in(ID(FDRE), ID(FDRE_1))) { + if (cell->parameters.at(ID(INIT), State::S0).as_bool()) + initval.append(State::S1); + else + initval.append(State::S0); + } + else + log_abort(); + pm.autoremove(cell); + } + + auto first_cell = ud.longest_chain.back(); + auto last_cell = ud.longest_chain.front(); + Cell *c = pm.module->addCell(NEW_ID, ID($__XILINX_SHREG_)); + pm.module->swap_names(c, first_cell); + + if (first_cell->type.in(ID($_DFF_N_), ID($_DFF_P_), ID($_DFFE_NN_), ID($_DFFE_NP_), ID($_DFFE_PN_), ID($_DFFE_PP_), ID(FDRE), ID(FDRE_1))) { + c->setParam(ID(DEPTH), GetSize(ud.longest_chain)); + c->setParam(ID(INIT), initval.as_const()); + if (first_cell->type.in(ID($_DFF_P_), ID($_DFFE_PN_), ID($_DFFE_PP_))) + c->setParam(ID(CLKPOL), 1); + else if (first_cell->type.in(ID($_DFF_N_), ID($DFFE_NN_), ID($_DFFE_NP_), ID(FDRE_1))) + c->setParam(ID(CLKPOL), 0); + else if (first_cell->type.in(ID(FDRE))) { + if (!first_cell->parameters.at(ID(IS_C_INVERTED), State::S0).as_bool()) + c->setParam(ID(CLKPOL), 1); + else + c->setParam(ID(CLKPOL), 0); + } + else + log_abort(); + if (first_cell->type.in(ID($_DFFE_NP_), ID($_DFFE_PP_))) + c->setParam(ID(ENPOL), 1); + else if (first_cell->type.in(ID($_DFFE_NN_), ID($_DFFE_PN_))) + c->setParam(ID(ENPOL), 0); + else + c->setParam(ID(ENPOL), 2); + + c->setPort(ID(C), first_cell->getPort(ID(C))); + c->setPort(ID(D), first_cell->getPort(ID(D))); + c->setPort(ID(Q), last_cell->getPort(ID(Q))); + c->setPort(ID(L), GetSize(ud.longest_chain)-1); + if (first_cell->type.in(ID($_DFF_N_), ID($_DFF_P_))) + c->setPort(ID(E), State::S1); + else if (first_cell->type.in(ID($_DFFE_NN_), ID($_DFFE_NP_), ID($_DFFE_PN_), ID($_DFFE_PP_))) + c->setPort(ID(E), first_cell->getPort(ID(E))); + else if (first_cell->type.in(ID(FDRE), ID(FDRE_1))) + c->setPort(ID(E), first_cell->getPort(ID(CE))); + else + log_abort(); + } + else + log_abort(); + + log(" -> %s (%s)\n", log_id(c), log_id(c->type)); +} + +void run_variable(xilinx_srl_pm &pm) +{ + auto &st = pm.st_variable; + auto &ud = pm.ud_variable; + + log("Found variable chain of length %d (%s):\n", GetSize(ud.chain), log_id(st.first->type)); + + SigSpec initval; + for (const auto &i : ud.chain) { + auto cell = i.first; + auto slice = i.second; + log_debug(" %s\n", log_id(cell)); + if (cell->type.in(ID($_DFF_N_), ID($_DFF_P_), ID($_DFFE_NN_), ID($_DFFE_NP_), ID($_DFFE_PN_), ID($_DFFE_PP_), ID($dff), ID($dffe))) { + SigBit Q = cell->getPort(ID(Q))[slice]; + log_assert(Q.wire); + auto it = Q.wire->attributes.find(ID(init)); + if (it != Q.wire->attributes.end()) { + auto &i = it->second[Q.offset]; + initval.append(i); + i = State::Sx; + } + else + initval.append(State::Sx); + } + else + log_abort(); + } + pm.autoremove(st.shiftx); + + auto first_cell = ud.chain.back().first; + auto first_slice = ud.chain.back().second; + + Cell *c = pm.module->addCell(NEW_ID, ID($__XILINX_SHREG_)); + pm.module->swap_names(c, first_cell); + + if (first_cell->type.in(ID($_DFF_N_), ID($_DFF_P_), ID($_DFFE_NN_), ID($_DFFE_NP_), ID($_DFFE_PN_), ID($_DFFE_PP_), ID($dff), ID($dffe))) { + c->setParam(ID(DEPTH), GetSize(ud.chain)); + c->setParam(ID(INIT), initval.as_const()); + Const clkpol, enpol; + if (first_cell->type.in(ID($_DFF_P_), ID($_DFFE_PN_), ID($_DFFE_PP_))) + clkpol = 1; + else if (first_cell->type.in(ID($_DFF_N_), ID($DFFE_NN_), ID($_DFFE_NP_))) + clkpol = 0; + else if (first_cell->type.in(ID($dff), ID($dffe))) + clkpol = first_cell->getParam(ID(CLK_POLARITY)); + else + log_abort(); + if (first_cell->type.in(ID($_DFFE_NP_), ID($_DFFE_PP_))) + enpol = 1; + else if (first_cell->type.in(ID($_DFFE_NN_), ID($_DFFE_PN_))) + enpol = 0; + else if (first_cell->type.in(ID($dffe))) + enpol = first_cell->getParam(ID(EN_POLARITY)); + else + enpol = 2; + c->setParam(ID(CLKPOL), clkpol); + c->setParam(ID(ENPOL), enpol); + + if (first_cell->type.in(ID($_DFF_N_), ID($_DFF_P_), ID($_DFFE_NN_), ID($_DFFE_NP_), ID($_DFFE_PN_), ID($_DFFE_PP_))) + c->setPort(ID(C), first_cell->getPort(ID(C))); + else if (first_cell->type.in(ID($dff), ID($dffe))) + c->setPort(ID(C), first_cell->getPort(ID(CLK))); + else + log_abort(); + c->setPort(ID(D), first_cell->getPort(ID(D))[first_slice]); + c->setPort(ID(Q), st.shiftx->getPort(ID(Y))); + c->setPort(ID(L), st.shiftx->getPort(ID(B))); + if (first_cell->type.in(ID($_DFF_N_), ID($_DFF_P_), ID($dff))) + c->setPort(ID(E), State::S1); + else if (first_cell->type.in(ID($_DFFE_NN_), ID($_DFFE_NP_), ID($_DFFE_PN_), ID($_DFFE_PP_))) + c->setPort(ID(E), first_cell->getPort(ID(E))); + else if (first_cell->type.in(ID($dffe))) + c->setPort(ID(E), first_cell->getPort(ID(EN))); + else + log_abort(); + } + else + log_abort(); + + log(" -> %s (%s)\n", log_id(c), log_id(c->type)); +} + +struct XilinxSrlPass : public Pass { + XilinxSrlPass() : Pass("xilinx_srl", "Xilinx shift register extraction") { } + void help() YS_OVERRIDE + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" xilinx_srl [options] [selection]\n"); + log("\n"); + log("This pass converts chains of built-in flops (bit-level: $_DFF_[NP]_, $_DFFE_*\n"); + log("and word-level: $dff, $dffe) as well as Xilinx flops (FDRE, FDRE_1) into a\n"); + log("$__XILINX_SHREG cell. Chains must be of the same cell type, clock, clock polarity,\n"); + log("enable, and enable polarity (where relevant).\n"); + log("Flops with resets cannot be mapped to Xilinx devices and will not be inferred."); + log("\n"); + log(" -minlen N\n"); + log(" min length of shift register (default = 3)\n"); + log("\n"); + log(" -fixed\n"); + log(" infer fixed-length shift registers.\n"); + log("\n"); + log(" -variable\n"); + log(" infer variable-length shift registers (i.e. fixed-length shifts where\n"); + log(" each element also fans-out to a $shiftx cell).\n"); + log("\n"); + } + + void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE + { + log_header(design, "Executing XILINX_SRL pass (Xilinx shift register extraction).\n"); + + bool fixed = false; + bool variable = false; + int minlen = 3; + + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) + { + if (args[argidx] == "-minlen" && argidx+1 < args.size()) { + minlen = atoi(args[++argidx].c_str()); + continue; + } + if (args[argidx] == "-fixed") { + fixed = true; + continue; + } + if (args[argidx] == "-variable") { + variable = true; + continue; + } + break; + } + extra_args(args, argidx, design); + + if (!fixed && !variable) + log_cmd_error("'-fixed' and/or '-variable' must be specified.\n"); + + for (auto module : design->selected_modules()) { + auto pm = xilinx_srl_pm(module, module->selected_cells()); + pm.ud_fixed.minlen = minlen; + pm.ud_variable.minlen = minlen; + + if (fixed) + pm.run_fixed(run_fixed); + if (variable) + pm.run_variable(run_variable); + } + } +} XilinxSrlPass; + +PRIVATE_NAMESPACE_END diff --git a/passes/pmgen/xilinx_srl.pmg b/passes/pmgen/xilinx_srl.pmg new file mode 100644 index 000000000..b18119b87 --- /dev/null +++ b/passes/pmgen/xilinx_srl.pmg @@ -0,0 +1,326 @@ +pattern fixed + +state <IdString> clk_port en_port +udata <vector<Cell*>> chain longest_chain +udata <pool<Cell*>> non_first_cells +udata <int> minlen + +code + non_first_cells.clear(); + subpattern(setup); +endcode + +match first + select first->type.in($_DFF_N_, $_DFF_P_, $_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_, \FDRE, \FDRE_1) + select !first->has_keep_attr() + select !first->type.in(\FDRE) || !first->parameters.at(\IS_R_INVERTED, State::S0).as_bool() + select !first->type.in(\FDRE) || !first->parameters.at(\IS_D_INVERTED, State::S0).as_bool() + select !first->type.in(\FDRE, \FDRE_1) || first->connections_.at(\R, State::S0).is_fully_zero() + filter !non_first_cells.count(first) +generate + SigSpec C = module->addWire(NEW_ID); + SigSpec D = module->addWire(NEW_ID); + SigSpec Q = module->addWire(NEW_ID); + auto r = rng(8); + Cell* cell; + switch (r) + { + case 0: + case 1: + cell = module->addCell(NEW_ID, \FDRE); + cell->setPort(\C, C); + cell->setPort(\D, D); + cell->setPort(\Q, Q); + cell->setPort(\CE, module->addWire(NEW_ID)); + if (r & 1) + cell->setPort(\R, module->addWire(NEW_ID)); + else { + if (rng(2) == 0) + cell->setPort(\R, State::S0); + } + break; + case 2: + case 3: + cell = module->addDffGate(NEW_ID, C, D, Q, r & 1); + break; + case 4: + case 5: + case 6: + case 7: + cell = module->addDffeGate(NEW_ID, C, module->addWire(NEW_ID), D, Q, r & 1, r & 2); + break; + default: log_abort(); + } +endmatch + +code clk_port en_port + if (first->type.in($_DFF_N_, $_DFF_P_, $_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_, \FDRE, \FDRE_1)) + clk_port = \C; + else log_abort(); + if (first->type.in($_DFF_N_, $_DFF_P_)) + en_port = IdString(); + else if (first->type.in($_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_)) + en_port = \E; + else if (first->type.in(\FDRE, \FDRE_1)) + en_port = \CE; + else log_abort(); + + longest_chain.clear(); + chain.push_back(first); + subpattern(tail); +finally + chain.pop_back(); + log_assert(chain.empty()); + if (GetSize(longest_chain) >= minlen) + accept; +endcode + +// ------------------------------------------------------------------ + +subpattern setup +arg clk_port +arg en_port + +match first + select first->type.in($_DFF_N_, $_DFF_P_, $_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_, \FDRE, \FDRE_1) + select !first->has_keep_attr() + select !first->type.in(\FDRE) || !first->parameters.at(\IS_R_INVERTED, State::S0).as_bool() + select !first->type.in(\FDRE) || !first->parameters.at(\IS_D_INVERTED, State::S0).as_bool() + select !first->type.in(\FDRE, \FDRE_1) || first->connections_.at(\R, State::S0).is_fully_zero() +endmatch + +code clk_port en_port + if (first->type.in($_DFF_N_, $_DFF_P_, $_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_, \FDRE, \FDRE_1)) + clk_port = \C; + else log_abort(); + if (first->type.in($_DFF_N_, $_DFF_P_)) + en_port = IdString(); + else if (first->type.in($_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_)) + en_port = \E; + else if (first->type.in(\FDRE, \FDRE_1)) + en_port = \CE; + else log_abort(); +endcode + +match next + select next->type.in($_DFF_N_, $_DFF_P_, $_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_, \FDRE, \FDRE_1) + select !next->has_keep_attr() + select port(next, \D)[0].wire && !port(next, \D)[0].wire->get_bool_attribute(\keep) + select nusers(port(next, \Q)) == 2 + index <IdString> next->type === first->type + index <SigBit> port(next, \Q) === port(first, \D) + filter port(next, clk_port) == port(first, clk_port) + filter en_port == IdString() || port(next, en_port) == port(first, en_port) + filter !first->type.in(\FDRE) || next->parameters.at(\IS_C_INVERTED, State::S0).as_bool() == first->parameters.at(\IS_C_INVERTED, State::S0).as_bool() + filter !first->type.in(\FDRE) || next->parameters.at(\IS_D_INVERTED, State::S0).as_bool() == first->parameters.at(\IS_D_INVERTED, State::S0).as_bool() + filter !first->type.in(\FDRE) || next->parameters.at(\IS_R_INVERTED, State::S0).as_bool() == first->parameters.at(\IS_R_INVERTED, State::S0).as_bool() + filter !first->type.in(\FDRE, \FDRE_1) || next->connections_.at(\R, State::S0).is_fully_zero() +endmatch + +code + non_first_cells.insert(next); +endcode + +// ------------------------------------------------------------------ + +subpattern tail +arg first +arg clk_port +arg en_port + +match next + semioptional + select next->type.in($_DFF_N_, $_DFF_P_, $_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_, \FDRE, \FDRE_1) + select !next->has_keep_attr() + select port(next, \D)[0].wire && !port(next, \D)[0].wire->get_bool_attribute(\keep) + select nusers(port(next, \Q)) == 2 + index <IdString> next->type === chain.back()->type + index <SigBit> port(next, \Q) === port(chain.back(), \D) + filter port(next, clk_port) == port(first, clk_port) + filter en_port == IdString() || port(next, en_port) == port(first, en_port) + filter !first->type.in(\FDRE) || next->parameters.at(\IS_C_INVERTED, State::S0).as_bool() == first->parameters.at(\IS_C_INVERTED, State::S0).as_bool() + filter !first->type.in(\FDRE) || next->parameters.at(\IS_D_INVERTED, State::S0).as_bool() == first->parameters.at(\IS_D_INVERTED, State::S0).as_bool() + filter !first->type.in(\FDRE) || next->parameters.at(\IS_R_INVERTED, State::S0).as_bool() == first->parameters.at(\IS_R_INVERTED, State::S0).as_bool() + filter !first->type.in(\FDRE, \FDRE_1) || next->connections_.at(\R, State::S0).is_fully_zero() +generate + Cell *cell = module->addCell(NEW_ID, chain.back()->type); + cell->setPort(\C, chain.back()->getPort(\C)); + cell->setPort(\D, module->addWire(NEW_ID)); + cell->setPort(\Q, chain.back()->getPort(\D)); + if (cell->type == \FDRE) { + if (rng(2) == 0) + cell->setPort(\R, chain.back()->connections_.at(\R, State::S0)); + cell->setPort(\CE, chain.back()->getPort(\CE)); + } + else if (cell->type.begins_with("$_DFFE_")) + cell->setPort(\E, chain.back()->getPort(\E)); +endmatch + +code + if (next) { + chain.push_back(next); + subpattern(tail); + } else { + if (GetSize(chain) > GetSize(longest_chain)) + longest_chain = chain; + } +finally + if (next) + chain.pop_back(); +endcode + +// ----------- + +pattern variable + +state <IdString> clk_port en_port +state <int> shiftx_width +state <int> slice +udata <int> minlen +udata <vector<pair<Cell*,int>>> chain +udata <pool<SigBit>> chain_bits + +code + chain_bits.clear(); +endcode + +match shiftx + select shiftx->type.in($shiftx) + select !shiftx->has_keep_attr() + select param(shiftx, \Y_WIDTH).as_int() == 1 + filter param(shiftx, \A_WIDTH).as_int() >= minlen +generate + minlen = 3; + module->addShiftx(NEW_ID, module->addWire(NEW_ID, rng(6)+minlen), module->addWire(NEW_ID, 3), module->addWire(NEW_ID)); +endmatch + +code shiftx_width + shiftx_width = param(shiftx, \A_WIDTH).as_int(); +endcode + +match first + select first->type.in($_DFF_N_, $_DFF_P_, $_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_, $dff, $dffe) + select !first->has_keep_attr() + select port(first, \Q)[0].wire && !port(first, \Q)[0].wire->get_bool_attribute(\keep) + slice idx GetSize(port(first, \Q)) + select nusers(port(first, \Q)[idx]) <= 2 + index <SigBit> port(first, \Q)[idx] === port(shiftx, \A)[shiftx_width-1] + set slice idx +generate + SigSpec C = module->addWire(NEW_ID); + auto WIDTH = rng(3)+1; + SigSpec D = module->addWire(NEW_ID, WIDTH); + SigSpec Q = module->addWire(NEW_ID, WIDTH); + auto r = rng(8); + Cell *cell = nullptr; + switch (r) + { + case 0: + case 1: + cell = module->addDff(NEW_ID, C, D, Q, r & 1); + break; + case 2: + case 3: + case 4: + case 5: + //cell = module->addDffe(NEW_ID, C, module->addWire(NEW_ID), D, Q, r & 1, r & 4); + //break; + case 6: + case 7: + WIDTH = 1; + cell = module->addDffGate(NEW_ID, C, D[0], Q[0], r & 1); + break; + default: log_abort(); + } + shiftx->connections_.at(\A)[shiftx_width-1] = port(cell, \Q)[rng(WIDTH)]; +endmatch + +code clk_port en_port + if (first->type.in($_DFF_N_, $_DFF_P_, $_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_)) + clk_port = \C; + else if (first->type.in($dff, $dffe)) + clk_port = \CLK; + else log_abort(); + if (first->type.in($_DFF_N_, $_DFF_P_, $dff)) + en_port = IdString(); + else if (first->type.in($_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_)) + en_port = \E; + else if (first->type.in($dffe)) + en_port = \EN; + else log_abort(); + + chain_bits.insert(port(first, \Q)[slice]); + chain.emplace_back(first, slice); + subpattern(tail); +finally + if (GetSize(chain) == shiftx_width) + accept; + chain.clear(); +endcode + +// ------------------------------------------------------------------ + +subpattern tail +arg first +arg shiftx +arg shiftx_width +arg slice +arg clk_port +arg en_port + +match next + semioptional + select next->type.in($_DFF_N_, $_DFF_P_, $_DFFE_NN_, $_DFFE_NP_, $_DFFE_PN_, $_DFFE_PP_, $dff, $dffe) + select !next->has_keep_attr() + select port(next, \D)[0].wire && !port(next, \D)[0].wire->get_bool_attribute(\keep) + slice idx GetSize(port(next, \Q)) + select nusers(port(next, \Q)[idx]) <= 3 + index <IdString> next->type === chain.back().first->type + index <SigBit> port(next, \Q)[idx] === port(chain.back().first, \D)[chain.back().second] + index <SigBit> port(next, \Q)[idx] === port(shiftx, \A)[shiftx_width-1-GetSize(chain)] + filter port(next, clk_port) == port(first, clk_port) + filter en_port == IdString() || port(next, en_port) == port(first, en_port) + filter !next->type.in($dff, $dffe) || param(next, \CLK_POLARITY).as_bool() == param(first, \CLK_POLARITY).as_bool() + filter !next->type.in($dffe) || param(next, \EN_POLARITY).as_bool() == param(first, \EN_POLARITY).as_bool() + filter !chain_bits.count(port(next, \D)[idx]) + set slice idx +generate + if (GetSize(chain) < shiftx_width) { + auto back = chain.back().first; + auto slice = chain.back().second; + if (back->type.in($dff, $dffe)) { + auto WIDTH = GetSize(port(back, \D)); + if (rng(2) == 0 && slice < WIDTH-1) { + auto new_slice = slice + rng(WIDTH-1-slice); + back->connections_.at(\D)[slice] = port(back, \Q)[new_slice]; + } + else { + auto D = module->addWire(NEW_ID, WIDTH); + if (back->type == $dff) + module->addDff(NEW_ID, port(back, \CLK), D, port(back, \D), param(back, \CLK_POLARITY).as_bool()); + else if (back->type == $dffe) + module->addDffe(NEW_ID, port(back, \CLK), port(back, \EN), D, port(back, \D), param(back, \CLK_POLARITY).as_bool(), param(back, \EN_POLARITY).as_bool()); + else + log_abort(); + } + } + else if (back->type.begins_with("$_DFF_")) { + Cell *cell = module->addCell(NEW_ID, back->type); + cell->setPort(\C, back->getPort(\C)); + cell->setPort(\D, module->addWire(NEW_ID)); + cell->setPort(\Q, back->getPort(\D)); + } + else + log_abort(); + shiftx->connections_.at(\A)[shiftx_width-1-GetSize(chain)] = port(back, \D)[slice]; + } +endmatch + +code + if (next) { + chain_bits.insert(port(next, \Q)[slice]); + chain.emplace_back(next, slice); + if (GetSize(chain) < shiftx_width) + subpattern(tail); + } +endcode |