diff options
Diffstat (limited to 'kernel')
| -rw-r--r-- | kernel/ff.h | 2 | ||||
| -rw-r--r-- | kernel/ffinit.h | 1 | ||||
| -rw-r--r-- | kernel/ffmerge.cc | 332 | ||||
| -rw-r--r-- | kernel/ffmerge.h | 141 |
4 files changed, 474 insertions, 2 deletions
diff --git a/kernel/ff.h b/kernel/ff.h index 0aecbaa2a..3e83db678 100644 --- a/kernel/ff.h +++ b/kernel/ff.h @@ -57,7 +57,7 @@ struct FfData { int width; dict<IdString, Const> attributes; - FfData(FfInitVals *initvals, Cell *cell = nullptr) : initvals(initvals) { + FfData(FfInitVals *initvals = nullptr, Cell *cell = nullptr) : initvals(initvals) { width = 0; has_d = true; has_clk = false; diff --git a/kernel/ffinit.h b/kernel/ffinit.h index 025b0c862..9d33ac572 100644 --- a/kernel/ffinit.h +++ b/kernel/ffinit.h @@ -28,7 +28,6 @@ YOSYS_NAMESPACE_BEGIN struct FfInitVals { const SigMap *sigmap; - RTLIL::Module *module; dict<SigBit, std::pair<State,SigBit>> initbits; void set(const SigMap *sigmap_, RTLIL::Module *module) diff --git a/kernel/ffmerge.cc b/kernel/ffmerge.cc new file mode 100644 index 000000000..6a29acc96 --- /dev/null +++ b/kernel/ffmerge.cc @@ -0,0 +1,332 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2021 Marcelina Kościelnicka <mwk@0x04.net> + * + * 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/ffmerge.h" + +USING_YOSYS_NAMESPACE + +bool FfMergeHelper::is_output_unused(RTLIL::SigSpec sig) { + for (auto bit : (*sigmap)(sig)) + if (sigbit_users_count[bit] != 0) + return false; + return true; +} + +bool FfMergeHelper::find_output_ff(RTLIL::SigSpec sig, FfData &ff, pool<std::pair<Cell *, int>> &bits) { + ff = FfData(); + sigmap->apply(sig); + + bool found = false; + + for (auto bit : sig) + { + if (bit.wire == NULL || sigbit_users_count[bit] == 0) { + ff.width++; + ff.sig_q.append(bit); + ff.sig_d.append(bit); + ff.sig_clr.append(State::Sx); + ff.sig_set.append(State::Sx); + ff.val_init.bits.push_back(State::Sx); + ff.val_srst.bits.push_back(State::Sx); + ff.val_arst.bits.push_back(State::Sx); + continue; + } + + if (sigbit_users_count[bit] != 1) + return false; + + auto &sinks = dff_sink[bit]; + if (sinks.size() != 1) + return false; + + Cell *cell; + int idx; + std::tie(cell, idx) = *sinks.begin(); + bits.insert(std::make_pair(cell, idx)); + + FfData cur_ff(initvals, cell); + + log_assert(cur_ff.has_d); + log_assert((*sigmap)(cur_ff.sig_d[idx]) == bit); + + if (!found) { + ff.sig_clk = cur_ff.sig_clk; + ff.sig_en = cur_ff.sig_en; + ff.sig_srst = cur_ff.sig_srst; + ff.sig_arst = cur_ff.sig_arst; + ff.has_clk = cur_ff.has_clk; + ff.has_en = cur_ff.has_en; + ff.has_srst = cur_ff.has_srst; + ff.has_arst = cur_ff.has_arst; + ff.has_sr = cur_ff.has_sr; + ff.ce_over_srst = cur_ff.ce_over_srst; + ff.pol_clk = cur_ff.pol_clk; + ff.pol_en = cur_ff.pol_en; + ff.pol_arst = cur_ff.pol_arst; + ff.pol_srst = cur_ff.pol_srst; + ff.pol_clr = cur_ff.pol_clr; + ff.pol_set = cur_ff.pol_set; + } else { + if (ff.has_clk != cur_ff.has_clk) + return false; + if (ff.has_en != cur_ff.has_en) + return false; + if (ff.has_srst != cur_ff.has_srst) + return false; + if (ff.has_arst != cur_ff.has_arst) + return false; + if (ff.has_sr != cur_ff.has_sr) + return false; + if (ff.has_clk) { + if (ff.sig_clk != cur_ff.sig_clk) + return false; + if (ff.pol_clk != cur_ff.pol_clk) + return false; + } + if (ff.has_en) { + if (ff.sig_en != cur_ff.sig_en) + return false; + if (ff.pol_en != cur_ff.pol_en) + return false; + } + if (ff.has_srst) { + if (ff.sig_srst != cur_ff.sig_srst) + return false; + if (ff.pol_srst != cur_ff.pol_srst) + return false; + if (ff.has_en && ff.ce_over_srst != cur_ff.ce_over_srst) + return false; + } + if (ff.has_arst) { + if (ff.sig_arst != cur_ff.sig_arst) + return false; + if (ff.pol_arst != cur_ff.pol_arst) + return false; + } + if (ff.has_sr) { + if (ff.pol_clr != cur_ff.pol_clr) + return false; + if (ff.pol_set != cur_ff.pol_set) + return false; + } + } + + ff.width++; + ff.sig_d.append(cur_ff.sig_d[idx]); + ff.sig_q.append(cur_ff.sig_q[idx]); + ff.sig_clr.append(ff.has_sr ? cur_ff.sig_clr[idx] : State::S0); + ff.sig_set.append(ff.has_sr ? cur_ff.sig_set[idx] : State::S0); + ff.val_arst.bits.push_back(ff.has_arst ? cur_ff.val_arst[idx] : State::Sx); + ff.val_srst.bits.push_back(ff.has_srst ? cur_ff.val_srst[idx] : State::Sx); + ff.val_init.bits.push_back(cur_ff.val_init[idx]); + found = true; + } + + return found; +} + +bool FfMergeHelper::find_input_ff(RTLIL::SigSpec sig, FfData &ff, pool<std::pair<Cell *, int>> &bits) { + ff = FfData(); + sigmap->apply(sig); + + bool found = false; + + pool<int> const_bits; + + for (auto bit : sig) + { + if (bit.wire == NULL) { + const_bits.insert(ff.width); + ff.width++; + ff.sig_q.append(bit); + ff.sig_d.append(bit); + // These two will be fixed up later. + ff.sig_clr.append(State::Sx); + ff.sig_set.append(State::Sx); + ff.val_init.bits.push_back(bit.data); + ff.val_srst.bits.push_back(bit.data); + ff.val_arst.bits.push_back(bit.data); + continue; + } + + if (!dff_driver.count(bit)) + return false; + + Cell *cell; + int idx; + std::tie(cell, idx) = dff_driver[bit]; + bits.insert(std::make_pair(cell, idx)); + + FfData cur_ff(initvals, cell); + + log_assert((*sigmap)(cur_ff.sig_q[idx]) == bit); + + if (!found) { + ff.sig_clk = cur_ff.sig_clk; + ff.sig_en = cur_ff.sig_en; + ff.sig_srst = cur_ff.sig_srst; + ff.sig_arst = cur_ff.sig_arst; + ff.has_d = cur_ff.has_d; + ff.has_clk = cur_ff.has_clk; + ff.has_en = cur_ff.has_en; + ff.has_srst = cur_ff.has_srst; + ff.has_arst = cur_ff.has_arst; + ff.has_sr = cur_ff.has_sr; + ff.ce_over_srst = cur_ff.ce_over_srst; + ff.pol_clk = cur_ff.pol_clk; + ff.pol_en = cur_ff.pol_en; + ff.pol_arst = cur_ff.pol_arst; + ff.pol_srst = cur_ff.pol_srst; + ff.pol_clr = cur_ff.pol_clr; + ff.pol_set = cur_ff.pol_set; + } else { + if (ff.has_d != cur_ff.has_d) + return false; + if (ff.has_clk != cur_ff.has_clk) + return false; + if (ff.has_en != cur_ff.has_en) + return false; + if (ff.has_srst != cur_ff.has_srst) + return false; + if (ff.has_arst != cur_ff.has_arst) + return false; + if (ff.has_sr != cur_ff.has_sr) + return false; + if (ff.has_clk) { + if (ff.sig_clk != cur_ff.sig_clk) + return false; + if (ff.pol_clk != cur_ff.pol_clk) + return false; + } + if (ff.has_en) { + if (ff.sig_en != cur_ff.sig_en) + return false; + if (ff.pol_en != cur_ff.pol_en) + return false; + } + if (ff.has_srst) { + if (ff.sig_srst != cur_ff.sig_srst) + return false; + if (ff.pol_srst != cur_ff.pol_srst) + return false; + if (ff.has_en && ff.ce_over_srst != cur_ff.ce_over_srst) + return false; + } + if (ff.has_arst) { + if (ff.sig_arst != cur_ff.sig_arst) + return false; + if (ff.pol_arst != cur_ff.pol_arst) + return false; + } + if (ff.has_sr) { + if (ff.pol_clr != cur_ff.pol_clr) + return false; + if (ff.pol_set != cur_ff.pol_set) + return false; + } + } + + ff.width++; + ff.sig_d.append(ff.has_d ? cur_ff.sig_d[idx] : State::Sx); + ff.sig_q.append(cur_ff.sig_q[idx]); + ff.sig_clr.append(ff.has_sr ? cur_ff.sig_clr[idx] : State::S0); + ff.sig_set.append(ff.has_sr ? cur_ff.sig_set[idx] : State::S0); + ff.val_arst.bits.push_back(ff.has_arst ? cur_ff.val_arst[idx] : State::Sx); + ff.val_srst.bits.push_back(ff.has_srst ? cur_ff.val_srst[idx] : State::Sx); + ff.val_init.bits.push_back(cur_ff.val_init[idx]); + found = true; + } + + if (found && ff.has_sr) { + for (auto i: const_bits) { + if (ff.sig_d[i] == State::S0) { + ff.sig_set[i] = ff.pol_set ? State::S0 : State::S1; + } else if (ff.sig_d[i] == State::S1) { + ff.sig_clr[i] = ff.pol_clr ? State::S0 : State::S1; + } + } + } + + return found; +} + + +void FfMergeHelper::remove_output_ff(const pool<std::pair<Cell *, int>> &bits) { + for (auto &it : bits) { + Cell *cell = it.first; + int idx = it.second; + SigSpec q = cell->getPort(ID::Q); + initvals->remove_init(q[idx]); + dff_driver.erase((*sigmap)(q[idx])); + q[idx] = module->addWire(stringf("$ffmerge_disconnected$%d", autoidx++)); + cell->setPort(ID::Q, q); + } +} + +void FfMergeHelper::mark_input_ff(const pool<std::pair<Cell *, int>> &bits) { + for (auto &it : bits) { + Cell *cell = it.first; + int idx = it.second; + if (cell->hasPort(ID::D)) { + SigSpec d = cell->getPort(ID::D); + // The user count was already at least 1 + // (for the D port). Bump it as it is now connected + // to the merged-to cell as well. This suffices for + // it to not be considered for output merging. + sigbit_users_count[d[idx]]++; + } + } +} + +void FfMergeHelper::set(FfInitVals *initvals_, RTLIL::Module *module_) +{ + clear(); + initvals = initvals_; + sigmap = initvals->sigmap; + module = module_; + + for (auto wire : module->wires()) { + if (wire->port_output) + for (auto bit : (*sigmap)(wire)) + sigbit_users_count[bit]++; + } + + for (auto cell : module->cells()) { + if (RTLIL::builtin_ff_cell_types().count(cell->type)) { + if (cell->hasPort(ID::D)) { + SigSpec d = (*sigmap)(cell->getPort(ID::D)); + for (int i = 0; i < GetSize(d); i++) + dff_sink[d[i]].insert(std::make_pair(cell, i)); + } + SigSpec q = (*sigmap)(cell->getPort(ID::Q)); + for (int i = 0; i < GetSize(q); i++) + dff_driver[q[i]] = std::make_pair(cell, i); + } + for (auto &conn : cell->connections()) + if (!cell->known() || cell->input(conn.first)) + for (auto bit : (*sigmap)(conn.second)) + sigbit_users_count[bit]++; + } +} + +void FfMergeHelper::clear() { + dff_driver.clear(); + dff_sink.clear(); + sigbit_users_count.clear(); +} diff --git a/kernel/ffmerge.h b/kernel/ffmerge.h new file mode 100644 index 000000000..5428da324 --- /dev/null +++ b/kernel/ffmerge.h @@ -0,0 +1,141 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2021 Marcelina Kościelnicka <mwk@0x04.net> + * + * 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. + * + */ + +#ifndef FFMERGE_H +#define FFMERGE_H + +#include "kernel/ffinit.h" +#include "kernel/ff.h" + +YOSYS_NAMESPACE_BEGIN + +// A helper class for passes that want to merge FFs on the input or output +// of a cell into the cell itself. +// +// The procedure is: +// +// 1. Construct this class (at beginning of processing for a given module). +// 2. For every considered cell: +// +// a. Call find_output_ff for every considered output. +// b. Call find_input_ff for every considered input. +// c. Look at the FF description returned (if any) from each call, reject +// results that cannot be merged into given cell for any reason. +// If both inputs and outputs are being merged, take care of FF bits that +// are returned in both input and output results (a FF bit cannot be +// merged to both). Decide on the final set of FF bits to merge. +// d. Call remove_output_ff for every find_output_ff result that will be used +// for merging. This removes the actual FF bits from design and from index. +// e. Call mark_input_ff for every find_input_ff result that will be used +// for merging. This updates the index disallowing further usage of these +// FF bits for output FF merging, if they were eligible before. The actual +// FF bits are still left in the design and can be merged into other inputs. +// If the FF bits are not otherwise used, they will be removed by later +// opt passes. +// f. Merge the FFs into the cell. +// +// Note that, if both inputs and outputs are being considered for merging in +// a single pass, the result may be nondeterministic (depending on cell iteration +// order) because a given FF bit could be eligible for both input and output merge, +// perhaps in different cells. For this reason, it may be a good idea to separate +// input and output merging. + +struct FfMergeHelper +{ + const SigMap *sigmap; + RTLIL::Module *module; + FfInitVals *initvals; + + dict<SigBit, std::pair<Cell*, int>> dff_driver; + dict<SigBit, pool<std::pair<Cell*, int>>> dff_sink; + dict<SigBit, int> sigbit_users_count; + + // Returns true if all bits in sig are completely unused. + bool is_output_unused(RTLIL::SigSpec sig); + + // Finds the FF to merge into a given cell output. Takes sig, which + // is the current cell output — it will be the sig_d of the found FF. + // If found, returns true, and fills the two output arguments. + // + // For every bit of sig, this function finds a FF bit that has + // the same sig_d, and fills the output FfData according to the FF + // bits found. This function will only consider FF bits that are + // the only user of the given sig bits — if any bit in sig is used + // by anything other than a single FF, this function will return false. + // + // The returned FfData structure does not correspond to any actual FF + // cell in the design — it is the amalgamation of extracted FF bits, + // possibly coming from several FF cells. + // + // If some of the bits in sig have no users at all, this function + // will accept them as well (and fill returned FfData with dummy values + // for the given bit, effectively synthesizing an unused FF bit of the + // appropriate type). However, if all bits in sig are completely + // unused, this function will fail and return false (having no idea + // what kind of FF to produce) — use the above helper if that case + // is important to handle. + // + // Note that this function does not remove the FF bits returned from + // the design — this is so that the caller can decide whether to accept + // this FF for merging or not. If the result is accepted, + // remove_output_ff should be called on the second output argument. + bool find_output_ff(RTLIL::SigSpec sig, FfData &ff, pool<std::pair<Cell *, int>> &bits); + + // Like above, but returns a FF to merge into a given cell input. Takes + // sig_q, which is the current cell input — it will search for FFs with + // matching sig_q. + // + // As opposed to find_output_ff, this function doesn't care about usage + // counts, and may return FF bits that also have other fanout. This + // should not be a problem for input FF merging. + // + // As a special case, if some of the bits in sig_q are constant, this + // function will accept them as well, by synthesizing in-place + // a constant-input FF bit (with matching initial value and reset value). + // However, this will not work if the input is all-constant — if the caller + // cares about this case, it needs to check for it explicitely. + bool find_input_ff(RTLIL::SigSpec sig, FfData &ff, pool<std::pair<Cell *, int>> &bits); + + // To be called on find_output_ff result that will be merged. This + // marks the given FF bits as used up (and not to be considered for + // further merging as inputs), and reconnects their Q ports to a dummy + // wire (since the wire previously connected there will now be driven + // by the merged-to cell instead). + void remove_output_ff(const pool<std::pair<Cell *, int>> &bits); + + // To be called on find_input_ff result that will be merged. This + // marks the given FF bits as used, and disallows merging them as + // outputs. They can, however, still be merged as inputs again + // (perhaps for another cell). + void mark_input_ff(const pool<std::pair<Cell *, int>> &bits); + + void set(FfInitVals *initvals_, RTLIL::Module *module_); + + void clear(); + + FfMergeHelper(FfInitVals *initvals, RTLIL::Module *module) { + set(initvals, module); + } + + FfMergeHelper() {} +}; + +YOSYS_NAMESPACE_END + +#endif |