From 1eea06bcc0750de02a460f3e949df2f68f800382 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Marcelina=20Ko=C5=9Bcielnicka?= Date: Mon, 15 Mar 2021 15:38:45 +0100 Subject: [PATCH] Add new helper class for merging FFs into cells, use for memory_dff. Fixes #1854. --- Makefile | 2 +- kernel/ff.h | 2 +- kernel/ffinit.h | 1 - kernel/ffmerge.cc | 332 +++++++++++++++++++++++++++++++++++ kernel/ffmerge.h | 141 +++++++++++++++ passes/memory/memory_dff.cc | 341 +++++++++++------------------------- tests/opt/bug1854.ys | 17 ++ 7 files changed, 596 insertions(+), 240 deletions(-) create mode 100644 kernel/ffmerge.cc create mode 100644 kernel/ffmerge.h create mode 100644 tests/opt/bug1854.ys diff --git a/Makefile b/Makefile index b8ef9343a..b35a11d53 100644 --- a/Makefile +++ b/Makefile @@ -622,7 +622,7 @@ ifneq ($(ABCEXTERNAL),) kernel/yosys.o: CXXFLAGS += -DABCEXTERNAL='"$(ABCEXTERNAL)"' endif endif -OBJS += kernel/cellaigs.o kernel/celledges.o kernel/satgen.o kernel/mem.o +OBJS += kernel/cellaigs.o kernel/celledges.o kernel/satgen.o kernel/mem.o kernel/ffmerge.o kernel/log.o: CXXFLAGS += -DYOSYS_SRC='"$(YOSYS_SRC)"' kernel/yosys.o: CXXFLAGS += -DYOSYS_DATDIR='"$(DATDIR)"' -DYOSYS_PROGRAM_PREFIX='"$(PROGRAM_PREFIX)"' 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 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> 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 + * + * 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> &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> &bits) { + ff = FfData(); + sigmap->apply(sig); + + bool found = false; + + pool 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> &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> &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 + * + * 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> dff_driver; + dict>> dff_sink; + dict 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> &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> &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> &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> &bits); + + void set(FfInitVals *initvals_, RTLIL::Module *module_); + + void clear(); + + FfMergeHelper(FfInitVals *initvals, RTLIL::Module *module) { + set(initvals, module); + } + + FfMergeHelper() {} +}; + +YOSYS_NAMESPACE_END + +#endif diff --git a/passes/memory/memory_dff.cc b/passes/memory/memory_dff.cc index 3698092b4..3248d4e9f 100644 --- a/passes/memory/memory_dff.cc +++ b/passes/memory/memory_dff.cc @@ -17,11 +17,12 @@ * */ -#include #include "kernel/yosys.h" #include "kernel/sigtools.h" #include "kernel/ffinit.h" #include "kernel/mem.h" +#include "kernel/ff.h" +#include "kernel/ffmerge.h" USING_YOSYS_NAMESPACE PRIVATE_NAMESPACE_BEGIN @@ -30,270 +31,136 @@ struct MemoryDffWorker { Module *module; SigMap sigmap; - - vector dff_cells; - dict invbits; - dict sigbit_users_count; FfInitVals initvals; + FfMergeHelper merger; MemoryDffWorker(Module *module) : module(module), sigmap(module) { initvals.set(&sigmap, module); + merger.set(&initvals, module); } - bool find_sig_before_dff(RTLIL::SigSpec &sig, RTLIL::SigSpec &clk, bool &clk_polarity) + void handle_rd_port(Mem &mem, int idx) { - sigmap.apply(sig); - - dict cache; - - for (auto &bit : sig) - { - if (cache.count(bit)) { - bit = cache[bit]; - continue; - } - - if (bit.wire == NULL) - continue; - - if (initvals(bit) != State::Sx) - return false; - - for (auto cell : dff_cells) - { - SigSpec this_clk = cell->getPort(ID::CLK); - bool this_clk_polarity = cell->parameters[ID::CLK_POLARITY].as_bool(); - - if (invbits.count(this_clk)) { - this_clk = invbits.at(this_clk); - this_clk_polarity = !this_clk_polarity; - } - - if (clk != RTLIL::SigSpec(RTLIL::State::Sx)) { - if (this_clk != clk) - continue; - if (this_clk_polarity != clk_polarity) - continue; - } - - RTLIL::SigSpec q_norm = cell->getPort(ID::Q); - sigmap.apply(q_norm); - - RTLIL::SigSpec d = q_norm.extract(bit, &cell->getPort(ID::D)); - if (d.size() != 1) - continue; - - if (cell->type == ID($sdffce)) { - SigSpec rval = cell->parameters[ID::SRST_VALUE]; - SigSpec rbit = q_norm.extract(bit, &rval); - if (cell->parameters[ID::SRST_POLARITY].as_bool()) - d = module->Mux(NEW_ID, d, rbit, cell->getPort(ID::SRST)); - else - d = module->Mux(NEW_ID, rbit, d, cell->getPort(ID::SRST)); - } - - if (cell->type.in(ID($dffe), ID($sdffe), ID($sdffce))) { - if (cell->parameters[ID::EN_POLARITY].as_bool()) - d = module->Mux(NEW_ID, bit, d, cell->getPort(ID::EN)); - else - d = module->Mux(NEW_ID, d, bit, cell->getPort(ID::EN)); - } - - if (cell->type.in(ID($sdff), ID($sdffe))) { - SigSpec rval = cell->parameters[ID::SRST_VALUE]; - SigSpec rbit = q_norm.extract(bit, &rval); - if (cell->parameters[ID::SRST_POLARITY].as_bool()) - d = module->Mux(NEW_ID, d, rbit, cell->getPort(ID::SRST)); - else - d = module->Mux(NEW_ID, rbit, d, cell->getPort(ID::SRST)); - } - - cache[bit] = d; - bit = d; - clk = this_clk; - clk_polarity = this_clk_polarity; - goto replaced_this_bit; - } + auto &port = mem.rd_ports[idx]; + log("Checking read port `%s'[%d] in module `%s': ", mem.memid.c_str(), idx, module->name.c_str()); - return false; - replaced_this_bit:; + FfData ff; + pool> bits; + if (!merger.find_output_ff(port.data, ff, bits)) { + log("no output FF found.\n"); + return; } - - return true; - } - - bool find_sig_after_dffe(RTLIL::SigSpec &sig, RTLIL::SigSpec &clk, bool &clk_polarity, RTLIL::SigSpec &en, bool &en_polarity) - { - sigmap.apply(sig); - - for (auto &bit : sig) - { - if (bit.wire == NULL) - continue; - - for (auto cell : dff_cells) - { - if (!cell->type.in(ID($dff), ID($dffe))) - continue; - - SigSpec this_clk = cell->getPort(ID::CLK); - bool this_clk_polarity = cell->parameters[ID::CLK_POLARITY].as_bool(); - SigSpec this_en = State::S1; - bool this_en_polarity = true; - - if (cell->type == ID($dffe)) { - this_en = cell->getPort(ID::EN); - this_en_polarity = cell->parameters[ID::EN_POLARITY].as_bool(); - } - - if (invbits.count(this_clk)) { - this_clk = invbits.at(this_clk); - this_clk_polarity = !this_clk_polarity; - } - - if (invbits.count(this_en)) { - this_en = invbits.at(this_en); - this_en_polarity = !this_en_polarity; - } - - if (clk != RTLIL::SigSpec(RTLIL::State::Sx)) { - if (this_clk != clk) - continue; - if (this_clk_polarity != clk_polarity) - continue; - if (this_en != en) - continue; - if (this_en_polarity != en_polarity) - continue; - } - - RTLIL::SigSpec q_norm = cell->getPort(ID::D); - sigmap.apply(q_norm); - - RTLIL::SigSpec d = q_norm.extract(bit, &cell->getPort(ID::Q)); - if (d.size() != 1) - continue; - - if (initvals(d) != State::Sx) - return false; - - bit = d; - clk = this_clk; - clk_polarity = this_clk_polarity; - en = this_en; - en_polarity = this_en_polarity; - goto replaced_this_bit; - } - - return false; - replaced_this_bit:; + if (!ff.has_clk) { + log("output latches are not supported.\n"); + return; } - - return true; - } - - void disconnect_dff(RTLIL::SigSpec sig) - { - sigmap.apply(sig); - sig.sort_and_unify(); - - std::stringstream sstr; - sstr << "$memory_dff_disconnected$" << (autoidx++); - - RTLIL::SigSpec new_sig = module->addWire(sstr.str(), sig.size()); - - for (auto cell : module->cells()) - if (cell->type.in(ID($dff), ID($dffe))) { - RTLIL::SigSpec new_q = cell->getPort(ID::Q); - new_q.replace(sig, new_sig); - cell->setPort(ID::Q, new_q); - } + if (ff.has_sr) { + // Latches and FFs with SR are not supported. + log("output FF has both set and reset, not supported.\n"); + return; + } + if (ff.has_srst || ff.has_arst || !ff.val_init.is_fully_undef()) { + // TODO: not supported yet + log("output FF has reset and/or init value, not supported yet.\n"); + return; + } + merger.remove_output_ff(bits); + if (ff.has_en && !ff.pol_en) + ff.sig_en = module->LogicNot(NEW_ID, ff.sig_en); + if (ff.has_arst && !ff.pol_arst) + ff.sig_arst = module->LogicNot(NEW_ID, ff.sig_arst); + if (ff.has_srst && !ff.pol_srst) + ff.sig_srst = module->LogicNot(NEW_ID, ff.sig_srst); + port.clk = ff.sig_clk; + port.clk_enable = true; + port.clk_polarity = ff.pol_clk; + if (ff.has_en) + port.en = ff.sig_en; + else + port.en = State::S1; +#if 0 + if (ff.has_arst) { + port.arst = ff.sig_arst; + port.arst_value = ff.val_arst; + } else { + port.arst = State::S0; + } + if (ff.has_srst) { + port.srst = ff.sig_srst; + port.srst_value = ff.val_srst; + port.ce_over_srst = ff.ce_over_srst; + } else { + port.srst = State::S0; + } + port.init_value = ff.val_init; +#endif + port.data = ff.sig_q; + mem.emit(); + log("merged output FF to cell.\n"); } - void handle_rd_port(Mem &mem, int idx) + void handle_rd_port_addr(Mem &mem, int idx) { auto &port = mem.rd_ports[idx]; - log("Checking read port `%s'[%d] in module `%s': ", mem.memid.c_str(), idx, module->name.c_str()); - - bool clk_polarity = 0; - bool en_polarity = 0; + log("Checking read port address `%s'[%d] in module `%s': ", mem.memid.c_str(), idx, module->name.c_str()); - RTLIL::SigSpec clk_data = RTLIL::SigSpec(RTLIL::State::Sx); - RTLIL::SigSpec en_data; - RTLIL::SigSpec sig_data = port.data; - - for (auto bit : sigmap(sig_data)) - if (sigbit_users_count[bit] > 1) - goto skip_ff_after_read_merging; - - if (find_sig_after_dffe(sig_data, clk_data, clk_polarity, en_data, en_polarity) && clk_data != RTLIL::SigSpec(RTLIL::State::Sx)) - { - if (!en_polarity) - en_data = module->LogicNot(NEW_ID, en_data); - disconnect_dff(sig_data); - port.clk = clk_data; - port.en = en_data; - port.data = sig_data; - port.clk_enable = true; - port.clk_polarity = clk_polarity; - port.transparent = false; - mem.emit(); - log("merged data $dff to cell.\n"); + FfData ff; + pool> bits; + if (!merger.find_input_ff(port.addr, ff, bits)) { + log("no address FF found.\n"); return; } - - skip_ff_after_read_merging:; - RTLIL::SigSpec clk_addr = RTLIL::SigSpec(RTLIL::State::Sx); - RTLIL::SigSpec sig_addr = port.addr; - if (find_sig_before_dff(sig_addr, clk_addr, clk_polarity) && - clk_addr != RTLIL::SigSpec(RTLIL::State::Sx)) - { - port.clk = clk_addr; - port.en = State::S1; - port.addr = sig_addr; - port.clk_enable = true; - port.clk_polarity = clk_polarity; - port.transparent = true; - mem.emit(); - log("merged address $dff to cell.\n"); + if (!ff.has_clk) { + log("address latches are not supported.\n"); return; } - - log("no (compatible) $dff found.\n"); + if (ff.has_sr || ff.has_arst) { + log("address FF has async set and/or reset, not supported.\n"); + return; + } + // Trick part: this transform is invalid if the initial + // value of the FF is fully-defined. However, we + // cannot simply reject FFs with any defined init bit, + // as this is often the result of merging a const bit. + if (ff.val_init.is_fully_def()) { + log("address FF has fully-defined init value, not supported.\n"); + return; + } + for (int i = 0; i < GetSize(mem.wr_ports); i++) { + auto &wport = mem.wr_ports[i]; + if (!wport.clk_enable || wport.clk != ff.sig_clk || wport.clk_polarity != ff.pol_clk) { + log("address FF clock is not compatible with write clock.\n"); + return; + } + } + // Now we're commited to merge it. + merger.mark_input_ff(bits); + // If the address FF has enable and/or sync reset, unmap it. + ff.unmap_ce_srst(module); + port.clk = ff.sig_clk; + port.en = State::S1; + port.addr = ff.sig_d; + port.clk_enable = true; + port.clk_polarity = ff.pol_clk; + port.transparent = true; + mem.emit(); + log("merged address FF to cell.\n"); } void run() { - for (auto wire : module->wires()) { - if (wire->port_output) - for (auto bit : sigmap(wire)) - sigbit_users_count[bit]++; - } - - for (auto cell : module->cells()) { - if (cell->type.in(ID($dff), ID($dffe), ID($sdff), ID($sdffe), ID($sdffce))) - dff_cells.push_back(cell); - if (cell->type.in(ID($not), ID($_NOT_)) || (cell->type == ID($logic_not) && GetSize(cell->getPort(ID::A)) == 1)) { - SigSpec sig_a = cell->getPort(ID::A); - SigSpec sig_y = cell->getPort(ID::Y); - if (cell->type == ID($not)) - sig_a.extend_u0(GetSize(sig_y), cell->getParam(ID::A_SIGNED).as_bool()); - if (cell->type == ID($logic_not)) - sig_y.extend_u0(1); - for (int i = 0; i < GetSize(sig_y); i++) - invbits[sig_y[i]] = sig_a[i]; + std::vector memories = Mem::get_selected_memories(module); + for (auto &mem : memories) { + for (int i = 0; i < GetSize(mem.rd_ports); i++) { + if (!mem.rd_ports[i].clk_enable) + handle_rd_port(mem, i); } - for (auto &conn : cell->connections()) - if (!cell->known() || cell->input(conn.first)) - for (auto bit : sigmap(conn.second)) - sigbit_users_count[bit]++; } - - for (auto &mem : Mem::get_selected_memories(module)) { + for (auto &mem : memories) { for (int i = 0; i < GetSize(mem.rd_ports); i++) { if (!mem.rd_ports[i].clk_enable) - handle_rd_port(mem, i); + handle_rd_port_addr(mem, i); } } } diff --git a/tests/opt/bug1854.ys b/tests/opt/bug1854.ys new file mode 100644 index 000000000..00a36ae94 --- /dev/null +++ b/tests/opt/bug1854.ys @@ -0,0 +1,17 @@ +read_verilog << EOT +module top(input clk, input [3:0] addr, output reg [0:0] dout); + reg [1:0] mem[0:15]; + initial begin + mem[0] = 2'b00; + mem[1] = 2'b01; + mem[2] = 2'b10; + mem[3] = 2'b11; + end + always @(posedge clk) + dout <= mem[addr]; +endmodule +EOT + +prep -rdff + +select -assert-none t:$dff -- 2.30.2