mirrors/yosys
3
0
Fork 0
mirror of https://github.com/YosysHQ/yosys synced 2025-10-28 18:29:25 +00:00
Code Activity
yosys/passes/opt/opt_dff.cc
Anhijkt b3ca5ee0f1 opt_dff: fix timeout issue
2025-08-13 01:48:59 +03:00

994 lines
32 KiB
C++
Raw Permalink Blame History

/*
* yosys -- Yosys Open SYnthesis Suite
*
* Copyright (C) 2012 Claire Xenia Wolf <claire@yosyshq.com>
* Copyright (C) 2020 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/log.h"
#include "kernel/register.h"
#include "kernel/rtlil.h"
#include "kernel/qcsat.h"
#include "kernel/modtools.h"
#include "kernel/sigtools.h"
#include "kernel/ffinit.h"
#include "kernel/ff.h"
#include "passes/techmap/simplemap.h"
#include <stdio.h>
#include <stdlib.h>
USING_YOSYS_NAMESPACE
PRIVATE_NAMESPACE_BEGIN
struct OptDffOptions
{
bool nosdff;
bool nodffe;
bool simple_dffe;
bool sat;
bool keepdc;
};
struct OptDffWorker
{
const OptDffOptions &opt;
Module *module;
typedef std::pair<RTLIL::Cell*, int> cell_int_t;
SigMap sigmap;
FfInitVals initvals;
dict<SigBit, int> bitusers;
dict<SigBit, cell_int_t> bit2mux;
typedef std::map<RTLIL::SigBit, bool> pattern_t;
typedef std::set<pattern_t> patterns_t;
typedef std::pair<RTLIL::SigBit, bool> ctrl_t;
typedef std::set<ctrl_t> ctrls_t;
// Used as a queue.
std::vector<Cell *> dff_cells;
OptDffWorker(const OptDffOptions &opt, Module *mod) : opt(opt), module(mod), sigmap(mod), initvals(&sigmap, mod) {
// Gathering two kinds of information here for every sigmapped SigBit:
//
// - bitusers: how many users it has (muxes will only be merged into FFs if this is 1, making the FF the only user)
// - bit2mux: the mux cell and bit index that drives it, if any
for (auto wire : module->wires())
{
if (wire->port_output)
for (auto bit : sigmap(wire))
bitusers[bit]++;
}
for (auto cell : module->cells()) {
if (cell->type.in(ID($mux), ID($pmux), ID($_MUX_))) {
RTLIL::SigSpec sig_y = sigmap(cell->getPort(ID::Y));
for (int i = 0; i < GetSize(sig_y); i++)
bit2mux[sig_y[i]] = cell_int_t(cell, i);
}
for (auto conn : cell->connections()) {
bool is_output = cell->output(conn.first);
if (!is_output || !cell->known()) {
for (auto bit : sigmap(conn.second))
bitusers[bit]++;
}
}
if (module->design->selected(module, cell) && RTLIL::builtin_ff_cell_types().count(cell->type))
dff_cells.push_back(cell);
}
}
State combine_const(State a, State b) {
if (a == State::Sx && !opt.keepdc)
return b;
if (b == State::Sx && !opt.keepdc)
return a;
if (a == b)
return a;
return State::Sm;
}
patterns_t find_muxtree_feedback_patterns(RTLIL::SigBit d, RTLIL::SigBit q, pattern_t path)
{
patterns_t ret;
if (d == q) {
ret.insert(path);
return ret;
}
if (bit2mux.count(d) == 0 || bitusers[d] > 1)
return ret;
cell_int_t mbit = bit2mux.at(d);
RTLIL::SigSpec sig_a = sigmap(mbit.first->getPort(ID::A));
RTLIL::SigSpec sig_b = sigmap(mbit.first->getPort(ID::B));
RTLIL::SigSpec sig_s = sigmap(mbit.first->getPort(ID::S));
int width = GetSize(sig_a), index = mbit.second;
for (int i = 0; i < GetSize(sig_s); i++)
if (path.count(sig_s[i]) && path.at(sig_s[i]))
{
ret = find_muxtree_feedback_patterns(sig_b[i*width + index], q, path);
if (sig_b[i*width + index] == q) {
RTLIL::SigSpec s = mbit.first->getPort(ID::B);
s[i*width + index] = RTLIL::Sx;
mbit.first->setPort(ID::B, s);
}
return ret;
}
pattern_t path_else = path;
for (int i = 0; i < GetSize(sig_s); i++)
{
if (path.count(sig_s[i]))
continue;
pattern_t path_this = path;
path_else[sig_s[i]] = false;
path_this[sig_s[i]] = true;
for (auto &pat : find_muxtree_feedback_patterns(sig_b[i*width + index], q, path_this))
ret.insert(pat);
if (sig_b[i*width + index] == q) {
RTLIL::SigSpec s = mbit.first->getPort(ID::B);
s[i*width + index] = RTLIL::Sx;
mbit.first->setPort(ID::B, s);
}
}
for (auto &pat : find_muxtree_feedback_patterns(sig_a[index], q, path_else))
ret.insert(pat);
if (sig_a[index] == q) {
RTLIL::SigSpec s = mbit.first->getPort(ID::A);
s[index] = RTLIL::Sx;
mbit.first->setPort(ID::A, s);
}
return ret;
}
void simplify_patterns(patterns_t& patterns)
{
auto new_patterns = patterns;
auto find_comp = [](const auto& left, const auto& right) -> std::optional<RTLIL::SigBit> {
std::optional<RTLIL::SigBit> ret;
for (const auto &pt: left)
if (right.count(pt.first) == 0)
return {};
else if (right.at(pt.first) == pt.second)
continue;
else
if (ret)
return {};
else
ret = pt.first;
return ret;
};
// remove complimentary patterns
bool optimized;
do {
optimized = false;
for (auto i = patterns.begin(); i != patterns.end(); i++) {
for (auto j = std::next(i, 1); j != patterns.end(); j++) {
const auto& left = (GetSize(*j) <= GetSize(*i)) ? *j : *i;
auto right = (GetSize(*i) < GetSize(*j)) ? *j : *i;
const auto complimentary_var = find_comp(left, right);
if (complimentary_var && new_patterns.count(right)) {
new_patterns.erase(right);
right.erase(complimentary_var.value());
new_patterns.insert(right);
optimized = true;
}
}
}
patterns = new_patterns;
} while(optimized);
// remove redundant patterns
for (auto i = patterns.begin(); i != patterns.end(); ++i) {
for (auto j = std::next(i, 1); j != patterns.end(); ++j) {
const auto& left = (GetSize(*j) <= GetSize(*i)) ? *j : *i;
const auto& right = (GetSize(*i) < GetSize(*j)) ? *j : *i;
bool redundant = true;
for (const auto& pt : left)
if (right.count(pt.first) == 0 || right.at(pt.first) != pt.second)
redundant = false;
if (redundant)
new_patterns.erase(right);
}
}
patterns = std::move(new_patterns);
}
ctrl_t make_patterns_logic(const patterns_t &patterns, const ctrls_t &ctrls, bool make_gates)
{
if (patterns.empty() && GetSize(ctrls) == 1) {
return *ctrls.begin();
}
RTLIL::SigSpec or_input;
for (auto pat : patterns)
{
RTLIL::SigSpec s1, s2;
for (auto it : pat) {
s1.append(it.first);
s2.append(it.second);
}
RTLIL::SigSpec y = module->addWire(NEW_ID);
RTLIL::Cell *c = module->addNe(NEW_ID, s1, s2, y);
if (make_gates) {
simplemap(module, c);
module->remove(c);
}
or_input.append(y);
}
for (auto item : ctrls) {
if (item.second)
or_input.append(item.first);
else if (make_gates)
or_input.append(module->NotGate(NEW_ID, item.first));
else
or_input.append(module->Not(NEW_ID, item.first));
}
if (GetSize(or_input) == 0)
return ctrl_t(State::S1, true);
if (GetSize(or_input) == 1)
return ctrl_t(or_input, true);
RTLIL::SigSpec y = module->addWire(NEW_ID);
RTLIL::Cell *c = module->addReduceAnd(NEW_ID, or_input, y);
if (make_gates) {
simplemap(module, c);
module->remove(c);
}
return ctrl_t(y, true);
}
ctrl_t combine_resets(const ctrls_t &ctrls, bool make_gates)
{
if (GetSize(ctrls) == 1) {
return *ctrls.begin();
}
RTLIL::SigSpec or_input;
bool final_pol = false;
for (auto item : ctrls) {
if (item.second)
final_pol = true;
}
for (auto item : ctrls) {
if (item.second == final_pol)
or_input.append(item.first);
else if (make_gates)
or_input.append(module->NotGate(NEW_ID, item.first));
else
or_input.append(module->Not(NEW_ID, item.first));
}
RTLIL::SigSpec y = module->addWire(NEW_ID);
RTLIL::Cell *c = final_pol ? module->addReduceOr(NEW_ID, or_input, y) : module->addReduceAnd(NEW_ID, or_input, y);
if (make_gates) {
simplemap(module, c);
module->remove(c);
}
return ctrl_t(y, final_pol);
}
bool run() {
// We have all the information we need, and the list of FFs to process as well. Do it.
bool did_something = false;
while (!dff_cells.empty()) {
Cell *cell = dff_cells.back();
dff_cells.pop_back();
// Break down the FF into pieces.
FfData ff(&initvals, cell);
bool changed = false;
if (!ff.width) {
ff.remove();
did_something = true;
continue;
}
if (ff.has_sr) {
bool sr_removed = false;
std::vector<int> keep_bits;
// Check for always-active S/R bits.
for (int i = 0; i < ff.width; i++) {
if (ff.sig_clr[i] == (ff.pol_clr ? State::S1 : State::S0) || (!opt.keepdc && ff.sig_clr[i] == State::Sx)) {
// Always-active clear — connect Q bit to 0.
initvals.remove_init(ff.sig_q[i]);
module->connect(ff.sig_q[i], State::S0);
log("Handling always-active CLR at position %d on %s (%s) from module %s (changing to const driver).\n",
i, log_id(cell), log_id(cell->type), log_id(module));
sr_removed = true;
} else if (ff.sig_set[i] == (ff.pol_set ? State::S1 : State::S0) || (!opt.keepdc && ff.sig_set[i] == State::Sx)) {
// Always-active set — connect Q bit to 1 if clear inactive, 0 if reset active.
initvals.remove_init(ff.sig_q[i]);
if (!ff.pol_clr) {
module->connect(ff.sig_q[i], ff.sig_clr[i]);
} else if (ff.is_fine) {
module->addNotGate(NEW_ID, ff.sig_clr[i], ff.sig_q[i]);
} else {
module->addNot(NEW_ID, ff.sig_clr[i], ff.sig_q[i]);
}
log("Handling always-active SET at position %d on %s (%s) from module %s (changing to combinatorial circuit).\n",
i, log_id(cell), log_id(cell->type), log_id(module));
sr_removed = true;
} else {
keep_bits.push_back(i);
}
}
if (sr_removed) {
if (keep_bits.empty()) {
module->remove(cell);
did_something = true;
continue;
}
ff = ff.slice(keep_bits);
ff.cell = cell;
changed = true;
}
if (ff.pol_clr ? ff.sig_clr.is_fully_zero() : ff.sig_clr.is_fully_ones()) {
// CLR is useless, try to kill it.
bool failed = false;
for (int i = 0; i < ff.width; i++)
if (ff.sig_set[i] != ff.sig_set[0])
failed = true;
if (!failed) {
log("Removing never-active CLR on %s (%s) from module %s.\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_sr = false;
ff.has_arst = true;
ff.pol_arst = ff.pol_set;
ff.sig_arst = ff.sig_set[0];
ff.val_arst = Const(State::S1, ff.width);
changed = true;
}
} else if (ff.pol_set ? ff.sig_set.is_fully_zero() : ff.sig_set.is_fully_ones()) {
// SET is useless, try to kill it.
bool failed = false;
for (int i = 0; i < ff.width; i++)
if (ff.sig_clr[i] != ff.sig_clr[0])
failed = true;
if (!failed) {
log("Removing never-active SET on %s (%s) from module %s.\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_sr = false;
ff.has_arst = true;
ff.pol_arst = ff.pol_clr;
ff.sig_arst = ff.sig_clr[0];
ff.val_arst = Const(State::S0, ff.width);
changed = true;
}
} else if (ff.pol_clr == ff.pol_set) {
// Try a more complex conversion to plain async reset.
State val_neutral = ff.pol_set ? State::S0 : State::S1;
Const val_arst;
SigBit sig_arst;
if (ff.sig_clr[0] == val_neutral)
sig_arst = ff.sig_set[0];
else
sig_arst = ff.sig_clr[0];
bool failed = false;
for (int i = 0; i < ff.width; i++) {
if (ff.sig_clr[i] == sig_arst && ff.sig_set[i] == val_neutral)
val_arst.bits().push_back(State::S0);
else if (ff.sig_set[i] == sig_arst && ff.sig_clr[i] == val_neutral)
val_arst.bits().push_back(State::S1);
else
failed = true;
}
if (!failed) {
log("Converting CLR/SET to ARST on %s (%s) from module %s.\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_sr = false;
ff.has_arst = true;
ff.val_arst = val_arst;
ff.sig_arst = sig_arst;
ff.pol_arst = ff.pol_clr;
changed = true;
}
}
}
if (ff.has_aload) {
if (ff.sig_aload == (ff.pol_aload ? State::S0 : State::S1) || (!opt.keepdc && ff.sig_aload == State::Sx)) {
// Always-inactive enable — remove.
log("Removing never-active async load on %s (%s) from module %s.\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_aload = false;
changed = true;
} else if (ff.sig_aload == (ff.pol_aload ? State::S1 : State::S0)) {
// Always-active enable. Make a comb circuit, nuke the FF/latch.
log("Handling always-active async load on %s (%s) from module %s (changing to combinatorial circuit).\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.remove();
if (ff.has_sr) {
SigSpec tmp;
if (ff.is_fine) {
if (ff.pol_set)
tmp = module->MuxGate(NEW_ID, ff.sig_ad, State::S1, ff.sig_set);
else
tmp = module->MuxGate(NEW_ID, State::S1, ff.sig_ad, ff.sig_set);
if (ff.pol_clr)
module->addMuxGate(NEW_ID, tmp, State::S0, ff.sig_clr, ff.sig_q);
else
module->addMuxGate(NEW_ID, State::S0, tmp, ff.sig_clr, ff.sig_q);
} else {
if (ff.pol_set)
tmp = module->Or(NEW_ID, ff.sig_ad, ff.sig_set);
else
tmp = module->Or(NEW_ID, ff.sig_ad, module->Not(NEW_ID, ff.sig_set));
if (ff.pol_clr)
module->addAnd(NEW_ID, tmp, module->Not(NEW_ID, ff.sig_clr), ff.sig_q);
else
module->addAnd(NEW_ID, tmp, ff.sig_clr, ff.sig_q);
}
} else if (ff.has_arst) {
if (ff.is_fine) {
if (ff.pol_arst)
module->addMuxGate(NEW_ID, ff.sig_ad, ff.val_arst[0], ff.sig_arst, ff.sig_q);
else
module->addMuxGate(NEW_ID, ff.val_arst[0], ff.sig_ad, ff.sig_arst, ff.sig_q);
} else {
if (ff.pol_arst)
module->addMux(NEW_ID, ff.sig_ad, ff.val_arst, ff.sig_arst, ff.sig_q);
else
module->addMux(NEW_ID, ff.val_arst, ff.sig_ad, ff.sig_arst, ff.sig_q);
}
} else {
module->connect(ff.sig_q, ff.sig_ad);
}
did_something = true;
continue;
} else if (ff.sig_ad.is_fully_const() && !ff.has_arst && !ff.has_sr) {
log("Changing const-value async load to async reset on %s (%s) from module %s.\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_arst = true;
ff.has_aload = false;
ff.sig_arst = ff.sig_aload;
ff.pol_arst = ff.pol_aload;
ff.val_arst = ff.sig_ad.as_const();
changed = true;
}
}
if (ff.has_arst) {
if (ff.sig_arst == (ff.pol_arst ? State::S0 : State::S1)) {
// Always-inactive reset — remove.
log("Removing never-active ARST on %s (%s) from module %s.\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_arst = false;
changed = true;
} else if (ff.sig_arst == (ff.pol_arst ? State::S1 : State::S0) || (!opt.keepdc && ff.sig_arst == State::Sx)) {
// Always-active async reset — change to const driver.
log("Handling always-active ARST on %s (%s) from module %s (changing to const driver).\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.remove();
module->connect(ff.sig_q, ff.val_arst);
did_something = true;
continue;
}
}
if (ff.has_srst) {
if (ff.sig_srst == (ff.pol_srst ? State::S0 : State::S1)) {
// Always-inactive reset — remove.
log("Removing never-active SRST on %s (%s) from module %s.\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_srst = false;
changed = true;
} else if (ff.sig_srst == (ff.pol_srst ? State::S1 : State::S0) || (!opt.keepdc && ff.sig_srst == State::Sx)) {
// Always-active sync reset — connect to D instead.
log("Handling always-active SRST on %s (%s) from module %s (changing to const D).\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_srst = false;
if (!ff.ce_over_srst)
ff.has_ce = false;
ff.sig_d = ff.val_srst;
changed = true;
}
}
if (ff.has_ce) {
if (ff.sig_ce == (ff.pol_ce ? State::S0 : State::S1) || (!opt.keepdc && ff.sig_ce == State::Sx)) {
// Always-inactive enable — remove.
if (ff.has_srst && !ff.ce_over_srst) {
log("Handling never-active EN on %s (%s) from module %s (connecting SRST instead).\n",
log_id(cell), log_id(cell->type), log_id(module));
// FF with sync reset — connect the sync reset to D instead.
ff.pol_ce = ff.pol_srst;
ff.sig_ce = ff.sig_srst;
ff.has_srst = false;
ff.sig_d = ff.val_srst;
changed = true;
} else if (!opt.keepdc || ff.val_init.is_fully_def()) {
log("Handling never-active EN on %s (%s) from module %s (removing D path).\n",
log_id(cell), log_id(cell->type), log_id(module));
// The D input path is effectively useless, so remove it (this will be a D latch, SR latch, or a const driver).
ff.has_ce = ff.has_clk = ff.has_srst = false;
changed = true;
} else {
// We need to keep the undefined initival around as such
ff.sig_d = ff.sig_q;
ff.has_ce = ff.has_srst = false;
changed = true;
}
} else if (ff.sig_ce == (ff.pol_ce ? State::S1 : State::S0)) {
// Always-active enable. Just remove it.
// For FF, just remove the useless enable.
log("Removing always-active EN on %s (%s) from module %s.\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_ce = false;
changed = true;
}
}
if (ff.has_clk && ff.sig_clk.is_fully_const()) {
if (!opt.keepdc || ff.val_init.is_fully_def()) {
// Const clock — the D input path is effectively useless, so remove it (this will be a D latch, SR latch, or a const driver).
log("Handling const CLK on %s (%s) from module %s (removing D path).\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_ce = ff.has_clk = ff.has_srst = false;
changed = true;
} else {
// Const clock, but we need to keep the undefined initval around as such
if (ff.has_ce || ff.has_srst || ff.sig_d != ff.sig_q) {
ff.sig_d = ff.sig_q;
ff.has_ce = ff.has_srst = false;
changed = true;
}
}
}
if ((ff.has_clk || ff.has_gclk) && ff.sig_d == ff.sig_q) {
// Q wrapped back to D, can be removed.
if (ff.has_clk && ff.has_srst) {
// FF with sync reset — connect the sync reset to D instead.
log("Handling D = Q on %s (%s) from module %s (conecting SRST instead).\n",
log_id(cell), log_id(cell->type), log_id(module));
if (ff.has_ce && ff.ce_over_srst) {
if (!ff.pol_ce) {
if (ff.is_fine)
ff.sig_ce = module->NotGate(NEW_ID, ff.sig_ce);
else
ff.sig_ce = module->Not(NEW_ID, ff.sig_ce);
}
if (!ff.pol_srst) {
if (ff.is_fine)
ff.sig_srst = module->NotGate(NEW_ID, ff.sig_srst);
else
ff.sig_srst = module->Not(NEW_ID, ff.sig_srst);
}
if (ff.is_fine)
ff.sig_ce = module->AndGate(NEW_ID, ff.sig_ce, ff.sig_srst);
else
ff.sig_ce = module->And(NEW_ID, ff.sig_ce, ff.sig_srst);
ff.pol_ce = true;
} else {
ff.pol_ce = ff.pol_srst;
ff.sig_ce = ff.sig_srst;
}
ff.has_ce = true;
ff.has_srst = false;
ff.sig_d = ff.val_srst;
changed = true;
} else if (!opt.keepdc || ff.val_init.is_fully_def()) {
// The D input path is effectively useless, so remove it (this will be a const-input D latch, SR latch, or a const driver).
log("Handling D = Q on %s (%s) from module %s (removing D path).\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_gclk = ff.has_clk = ff.has_ce = false;
changed = true;
}
}
if (ff.has_aload && !ff.has_clk && ff.sig_ad == ff.sig_q) {
log("Handling AD = Q on %s (%s) from module %s (removing async load path).\n",
log_id(cell), log_id(cell->type), log_id(module));
ff.has_aload = false;
changed = true;
}
// The cell has been simplified as much as possible already. Now try to spice it up with enables / sync resets.
if (ff.has_clk && ff.sig_d != ff.sig_q) {
if (!ff.has_arst && !ff.has_sr && (!ff.has_srst || !ff.has_ce || ff.ce_over_srst) && !opt.nosdff) {
// Try to merge sync resets.
std::map<ctrls_t, std::vector<int>> groups;
std::vector<int> remaining_indices;
Const val_srst;
for (int i = 0 ; i < ff.width; i++) {
ctrls_t resets;
State reset_val = State::Sx;
if (ff.has_srst)
reset_val = ff.val_srst[i];
while (bit2mux.count(ff.sig_d[i]) && bitusers[ff.sig_d[i]] == 1) {
cell_int_t mbit = bit2mux.at(ff.sig_d[i]);
if (GetSize(mbit.first->getPort(ID::S)) != 1)
break;
SigBit s = mbit.first->getPort(ID::S);
SigBit a = mbit.first->getPort(ID::A)[mbit.second];
SigBit b = mbit.first->getPort(ID::B)[mbit.second];
// Workaround for funny memory WE pattern.
if ((a == State::S0 || a == State::S1) && (b == State::S0 || b == State::S1))
break;
if ((b == State::S0 || b == State::S1) && (b == reset_val || reset_val == State::Sx)) {
// This is better handled by CE pattern.
if (a == ff.sig_q[i])
break;
reset_val = b.data;
resets.insert(ctrl_t(s, true));
ff.sig_d[i] = a;
} else if ((a == State::S0 || a == State::S1) && (a == reset_val || reset_val == State::Sx)) {
// This is better handled by CE pattern.
if (b == ff.sig_q[i])
break;
reset_val = a.data;
resets.insert(ctrl_t(s, false));
ff.sig_d[i] = b;
} else {
break;
}
}
if (!resets.empty()) {
if (ff.has_srst)
resets.insert(ctrl_t(ff.sig_srst, ff.pol_srst));
groups[resets].push_back(i);
} else
remaining_indices.push_back(i);
val_srst.bits().push_back(reset_val);
}
for (auto &it : groups) {
FfData new_ff = ff.slice(it.second);
new_ff.val_srst = Const();
for (int i = 0; i < new_ff.width; i++) {
int j = it.second[i];
new_ff.val_srst.bits().push_back(val_srst[j]);
}
ctrl_t srst = combine_resets(it.first, ff.is_fine);
new_ff.has_srst = true;
new_ff.sig_srst = srst.first;
new_ff.pol_srst = srst.second;
if (new_ff.has_ce)
new_ff.ce_over_srst = true;
Cell *new_cell = new_ff.emit();
if (new_cell)
dff_cells.push_back(new_cell);
log("Adding SRST signal on %s (%s) from module %s (D = %s, Q = %s, rval = %s).\n",
log_id(cell), log_id(cell->type), log_id(module), log_signal(new_ff.sig_d), log_signal(new_ff.sig_q), log_signal(new_ff.val_srst));
}
if (remaining_indices.empty()) {
module->remove(cell);
did_something = true;
continue;
} else if (GetSize(remaining_indices) != ff.width) {
ff = ff.slice(remaining_indices);
ff.cell = cell;
changed = true;
}
}
if ((!ff.has_srst || !ff.has_ce || !ff.ce_over_srst) && !opt.nodffe) {
// Try to merge enables.
std::map<std::pair<patterns_t, ctrls_t>, std::vector<int>> groups;
std::vector<int> remaining_indices;
for (int i = 0 ; i < ff.width; i++) {
// First, eat up as many simple muxes as possible.
ctrls_t enables;
while (bit2mux.count(ff.sig_d[i]) && bitusers[ff.sig_d[i]] == 1) {
cell_int_t mbit = bit2mux.at(ff.sig_d[i]);
if (GetSize(mbit.first->getPort(ID::S)) != 1)
break;
SigBit s = mbit.first->getPort(ID::S);
SigBit a = mbit.first->getPort(ID::A)[mbit.second];
SigBit b = mbit.first->getPort(ID::B)[mbit.second];
if (a == ff.sig_q[i]) {
enables.insert(ctrl_t(s, true));
ff.sig_d[i] = b;
} else if (b == ff.sig_q[i]) {
enables.insert(ctrl_t(s, false));
ff.sig_d[i] = a;
} else {
break;
}
}
patterns_t patterns;
if (!opt.simple_dffe)
patterns = find_muxtree_feedback_patterns(ff.sig_d[i], ff.sig_q[i], pattern_t());
if (!patterns.empty() || !enables.empty()) {
if (ff.has_ce)
enables.insert(ctrl_t(ff.sig_ce, ff.pol_ce));
simplify_patterns(patterns);
groups[std::make_pair(patterns, enables)].push_back(i);
} else
remaining_indices.push_back(i);
}
for (auto &it : groups) {
FfData new_ff = ff.slice(it.second);
ctrl_t en = make_patterns_logic(it.first.first, it.first.second, ff.is_fine);
new_ff.has_ce = true;
new_ff.sig_ce = en.first;
new_ff.pol_ce = en.second;
new_ff.ce_over_srst = false;
Cell *new_cell = new_ff.emit();
if (new_cell)
dff_cells.push_back(new_cell);
log("Adding EN signal on %s (%s) from module %s (D = %s, Q = %s).\n",
log_id(cell), log_id(cell->type), log_id(module), log_signal(new_ff.sig_d), log_signal(new_ff.sig_q));
}
if (remaining_indices.empty()) {
module->remove(cell);
did_something = true;
continue;
} else if (GetSize(remaining_indices) != ff.width) {
ff = ff.slice(remaining_indices);
ff.cell = cell;
changed = true;
}
}
}
if (changed) {
// Rebuild the FF.
ff.emit();
did_something = true;
}
}
return did_something;
}
bool run_constbits() {
ModWalker modwalker(module->design, module);
QuickConeSat qcsat(modwalker);
// Defer mutating cells by removing them/emiting new flip flops so that
// cell references in modwalker are not invalidated
std::vector<RTLIL::Cell*> cells_to_remove;
std::vector<FfData> ffs_to_emit;
bool did_something = false;
for (auto cell : module->selected_cells()) {
if (!RTLIL::builtin_ff_cell_types().count(cell->type))
continue;
FfData ff(&initvals, cell);
// Now check if any bit can be replaced by a constant.
pool<int> removed_sigbits;
for (int i = 0; i < ff.width; i++) {
State val = ff.val_init[i];
if (ff.has_arst)
val = combine_const(val, ff.val_arst[i]);
if (ff.has_srst)
val = combine_const(val, ff.val_srst[i]);
if (ff.has_sr) {
if (ff.sig_clr[i] != (ff.pol_clr ? State::S0 : State::S1))
val = combine_const(val, State::S0);
if (ff.sig_set[i] != (ff.pol_set ? State::S0 : State::S1))
val = combine_const(val, State::S1);
}
if (val == State::Sm)
continue;
if (ff.has_clk || ff.has_gclk) {
if (!ff.sig_d[i].wire) {
val = combine_const(val, ff.sig_d[i].data);
if (val == State::Sm)
continue;
} else {
if (!opt.sat)
continue;
// For each register bit, try to prove that it cannot change from the initial value. If so, remove it
if (!modwalker.has_drivers(ff.sig_d.extract(i)))
continue;
if (val != State::S0 && val != State::S1)
continue;
int init_sat_pi = qcsat.importSigBit(val);
int q_sat_pi = qcsat.importSigBit(ff.sig_q[i]);
int d_sat_pi = qcsat.importSigBit(ff.sig_d[i]);
qcsat.prepare();
// Try to find out whether the register bit can change under some circumstances
bool counter_example_found = qcsat.ez->solve(qcsat.ez->IFF(q_sat_pi, init_sat_pi), qcsat.ez->NOT(qcsat.ez->IFF(d_sat_pi, init_sat_pi)));
// If the register bit cannot change, we can replace it with a constant
if (counter_example_found)
continue;
}
}
if (ff.has_aload) {
if (!ff.sig_ad[i].wire) {
val = combine_const(val, ff.sig_ad[i].data);
if (val == State::Sm)
continue;
} else {
if (!opt.sat)
continue;
// For each register bit, try to prove that it cannot change from the initial value. If so, remove it
if (!modwalker.has_drivers(ff.sig_ad.extract(i)))
continue;
if (val != State::S0 && val != State::S1)
continue;
int init_sat_pi = qcsat.importSigBit(val);
int q_sat_pi = qcsat.importSigBit(ff.sig_q[i]);
int d_sat_pi = qcsat.importSigBit(ff.sig_ad[i]);
qcsat.prepare();
// Try to find out whether the register bit can change under some circumstances
bool counter_example_found = qcsat.ez->solve(qcsat.ez->IFF(q_sat_pi, init_sat_pi), qcsat.ez->NOT(qcsat.ez->IFF(d_sat_pi, init_sat_pi)));
// If the register bit cannot change, we can replace it with a constant
if (counter_example_found)
continue;
}
}
log("Setting constant %d-bit at position %d on %s (%s) from module %s.\n", val ? 1 : 0,
i, log_id(cell), log_id(cell->type), log_id(module));
initvals.remove_init(ff.sig_q[i]);
module->connect(ff.sig_q[i], val);
removed_sigbits.insert(i);
}
if (!removed_sigbits.empty()) {
std::vector<int> keep_bits;
for (int i = 0; i < ff.width; i++)
if (!removed_sigbits.count(i))
keep_bits.push_back(i);
if (keep_bits.empty()) {
cells_to_remove.emplace_back(cell);
did_something = true;
continue;
}
ff = ff.slice(keep_bits);
ff.cell = cell;
ffs_to_emit.emplace_back(ff);
did_something = true;
}
}
for (auto* cell : cells_to_remove)
module->remove(cell);
for (auto& ff : ffs_to_emit)
ff.emit();
return did_something;
}
};
struct OptDffPass : public Pass {
OptDffPass() : Pass("opt_dff", "perform DFF optimizations") { }
void help() override
{
// |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
log("\n");
log(" opt_dff [-nodffe] [-nosdff] [-keepdc] [-sat] [selection]\n");
log("\n");
log("This pass converts flip-flops to a more suitable type by merging clock enables\n");
log("and synchronous reset multiplexers, removing unused control inputs, or\n");
log("potentially removes the flip-flop altogether, converting it to a constant\n");
log("driver.\n");
log("\n");
log(" -nodffe\n");
log(" disables dff -> dffe conversion, and other transforms recognizing clock\n");
log(" enable\n");
log("\n");
log(" -nosdff\n");
log(" disables dff -> sdff conversion, and other transforms recognizing sync\n");
log(" resets\n");
log("\n");
log(" -simple-dffe\n");
log(" only enables clock enable recognition transform for obvious cases\n");
log("\n");
log(" -sat\n");
log(" additionally invoke SAT solver to detect and remove flip-flops (with\n");
log(" non-constant inputs) that can also be replaced with a constant driver\n");
log("\n");
log(" -keepdc\n");
log(" some optimizations change the behavior of the circuit with respect to\n");
log(" don't-care bits. for example in 'a+0' a single x-bit in 'a' will cause\n");
log(" all result bits to be set to x. this behavior changes when 'a+0' is\n");
log(" replaced by 'a'. the -keepdc option disables all such optimizations.\n");
log("\n");
}
void execute(std::vector<std::string> args, RTLIL::Design *design) override
{
log_header(design, "Executing OPT_DFF pass (perform DFF optimizations).\n");
OptDffOptions opt;
opt.nodffe = false;
opt.nosdff = false;
opt.simple_dffe = false;
opt.keepdc = false;
opt.sat = false;
size_t argidx;
for (argidx = 1; argidx < args.size(); argidx++) {
if (args[argidx] == "-nodffe") {
opt.nodffe = true;
continue;
}
if (args[argidx] == "-nosdff") {
opt.nosdff = true;
continue;
}
if (args[argidx] == "-simple-dffe") {
opt.simple_dffe = true;
continue;
}
if (args[argidx] == "-keepdc") {
opt.keepdc = true;
continue;
}
if (args[argidx] == "-sat") {
opt.sat = true;
continue;
}
break;
}
extra_args(args, argidx, design);
bool did_something = false;
for (auto mod : design->selected_modules()) {
OptDffWorker worker(opt, mod);
if (worker.run())
did_something = true;
if (worker.run_constbits())
did_something = true;
}
if (did_something)
design->scratchpad_set_bool("opt.did_something", true);
}
} OptDffPass;
PRIVATE_NAMESPACE_END
View git blame Copy permalink