yosys-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fsm_detect.cc
Go to the documentation of this file.
1 /*
2  * yosys -- Yosys Open SYnthesis Suite
3  *
4  * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
5  *
6  * Permission to use, copy, modify, and/or distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  *
18  */
19 
20 #include "kernel/log.h"
21 #include "kernel/register.h"
22 #include "kernel/sigtools.h"
23 #include "kernel/consteval.h"
24 #include "kernel/celltypes.h"
25 #include "fsmdata.h"
26 
27 USING_YOSYS_NAMESPACE
28 PRIVATE_NAMESPACE_BEGIN
29 
30 static RTLIL::Module *module;
31 static SigMap assign_map;
32 typedef std::pair<RTLIL::Cell*, RTLIL::IdString> sig2driver_entry_t;
33 static SigSet<sig2driver_entry_t> sig2driver, sig2user;
34 static std::set<RTLIL::Cell*> muxtree_cells;
35 static SigPool sig_at_port;
36 
37 static bool check_state_mux_tree(RTLIL::SigSpec old_sig, RTLIL::SigSpec sig, SigPool &recursion_monitor)
38 {
39  if (sig_at_port.check_any(assign_map(sig)))
40  return false;
41 
42  if (sig.is_fully_const() || old_sig == sig)
43  return true;
44 
45  if (recursion_monitor.check_any(sig)) {
46  log_warning("logic loop in mux tree at signal %s in module %s.\n",
47  log_signal(sig), RTLIL::id2cstr(module->name));
48  return false;
49  }
50 
51  recursion_monitor.add(sig);
52 
53  std::set<sig2driver_entry_t> cellport_list;
54  sig2driver.find(sig, cellport_list);
55  for (auto &cellport : cellport_list) {
56  if ((cellport.first->type != "$mux" && cellport.first->type != "$pmux") || cellport.second != "\\Y")
57  return false;
58  RTLIL::SigSpec sig_a = assign_map(cellport.first->getPort("\\A"));
59  RTLIL::SigSpec sig_b = assign_map(cellport.first->getPort("\\B"));
60  if (!check_state_mux_tree(old_sig, sig_a, recursion_monitor))
61  return false;
62  for (int i = 0; i < sig_b.size(); i += sig_a.size())
63  if (!check_state_mux_tree(old_sig, sig_b.extract(i, sig_a.size()), recursion_monitor))
64  return false;
65  muxtree_cells.insert(cellport.first);
66  }
67 
68  recursion_monitor.del(sig);
69 
70  return true;
71 }
72 
73 static bool check_state_users(RTLIL::SigSpec sig)
74 {
75  if (sig_at_port.check_any(assign_map(sig)))
76  return false;
77 
78  std::set<sig2driver_entry_t> cellport_list;
79  sig2user.find(sig, cellport_list);
80  for (auto &cellport : cellport_list) {
81  RTLIL::Cell *cell = cellport.first;
82  if (muxtree_cells.count(cell) > 0)
83  continue;
84  if (cellport.second != "\\A" && cellport.second != "\\B")
85  return false;
86  if (!cell->hasPort("\\A") || !cell->hasPort("\\B") || !cell->hasPort("\\Y"))
87  return false;
88  for (auto &port_it : cell->connections())
89  if (port_it.first != "\\A" && port_it.first != "\\B" && port_it.first != "\\Y")
90  return false;
91  if (assign_map(cell->getPort("\\A")) == sig && cell->getPort("\\B").is_fully_const())
92  continue;
93  if (assign_map(cell->getPort("\\B")) == sig && cell->getPort("\\A").is_fully_const())
94  continue;
95  return false;
96  }
97 
98  return true;
99 }
100 
101 static void detect_fsm(RTLIL::Wire *wire)
102 {
103  if (wire->attributes.count("\\fsm_encoding") > 0 || wire->width <= 1)
104  return;
105  if (sig_at_port.check_any(assign_map(RTLIL::SigSpec(wire))))
106  return;
107 
108  std::set<sig2driver_entry_t> cellport_list;
109  sig2driver.find(RTLIL::SigSpec(wire), cellport_list);
110  for (auto &cellport : cellport_list) {
111  if ((cellport.first->type != "$dff" && cellport.first->type != "$adff") || cellport.second != "\\Q")
112  continue;
113  muxtree_cells.clear();
114  SigPool recursion_monitor;
115  RTLIL::SigSpec sig_q = assign_map(cellport.first->getPort("\\Q"));
116  RTLIL::SigSpec sig_d = assign_map(cellport.first->getPort("\\D"));
117  if (sig_q == RTLIL::SigSpec(wire) && check_state_mux_tree(sig_q, sig_d, recursion_monitor) && check_state_users(sig_q)) {
118  log("Found FSM state register %s in module %s.\n", wire->name.c_str(), module->name.c_str());
119  wire->attributes["\\fsm_encoding"] = RTLIL::Const("auto");
120  return;
121  }
122  }
123 }
124 
125 struct FsmDetectPass : public Pass {
126  FsmDetectPass() : Pass("fsm_detect", "finding FSMs in design") { }
127  virtual void help()
128  {
129  // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
130  log("\n");
131  log(" fsm_detect [selection]\n");
132  log("\n");
133  log("This pass detects finite state machines by identifying the state signal.\n");
134  log("The state signal is then marked by setting the attribute 'fsm_encoding'\n");
135  log("on the state signal to \"auto\".\n");
136  log("\n");
137  log("Existing 'fsm_encoding' attributes are not changed by this pass.\n");
138  log("\n");
139  log("Signals can be protected from being detected by this pass by setting the\n");
140  log("'fsm_encoding' attribute to \"none\".\n");
141  log("\n");
142  }
143  virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
144  {
145  log_header("Executing FSM_DETECT pass (finding FSMs in design).\n");
146  extra_args(args, 1, design);
147 
148  CellTypes ct;
149  ct.setup_internals();
150  ct.setup_internals_mem();
151  ct.setup_stdcells();
152  ct.setup_stdcells_mem();
153 
154  for (auto &mod_it : design->modules_)
155  {
156  if (!design->selected(mod_it.second))
157  continue;
158 
159  module = mod_it.second;
160  assign_map.set(module);
161 
162  sig2driver.clear();
163  sig2user.clear();
164  sig_at_port.clear();
165  for (auto &cell_it : module->cells_)
166  for (auto &conn_it : cell_it.second->connections()) {
167  if (ct.cell_output(cell_it.second->type, conn_it.first) || !ct.cell_known(cell_it.second->type)) {
168  RTLIL::SigSpec sig = conn_it.second;
169  assign_map.apply(sig);
170  sig2driver.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
171  }
172  if (!ct.cell_known(cell_it.second->type) || ct.cell_input(cell_it.second->type, conn_it.first)) {
173  RTLIL::SigSpec sig = conn_it.second;
174  assign_map.apply(sig);
175  sig2user.insert(sig, sig2driver_entry_t(cell_it.second, conn_it.first));
176  }
177  }
178 
179  for (auto &wire_it : module->wires_)
180  if (wire_it.second->port_id != 0)
181  sig_at_port.add(assign_map(RTLIL::SigSpec(wire_it.second)));
182 
183  for (auto &wire_it : module->wires_)
184  if (design->selected(module, wire_it.second))
185  detect_fsm(wire_it.second);
186  }
187 
188  assign_map.clear();
189  sig2driver.clear();
190  sig2user.clear();
191  muxtree_cells.clear();
192  }
193 } FsmDetectPass;
194 
195 PRIVATE_NAMESPACE_END
RTLIL::IdString::c_str
const char * c_str() const
Definition: rtlil.h:178
FsmDetectPass
FsmDetectPass FsmDetectPass
RTLIL::Design::selected
bool selected(T1 *module) const
Definition: rtlil.h:551
CellTypes::setup_stdcells
void setup_stdcells()
Definition: celltypes.h:132
log_warning
void log_warning(const char *format,...)
Definition: log.cc:196
CellTypes::setup_internals_mem
void setup_internals_mem()
Definition: celltypes.h:115
log_header
void log_header(const char *format,...)
Definition: log.cc:188
ct
CellTypes ct
Definition: opt_clean.cc:33
RTLIL::Module::wires_
std::map< RTLIL::IdString, RTLIL::Wire * > wires_
Definition: rtlil.h:595
log_signal
const char * log_signal(const RTLIL::SigSpec &sig, bool autoint)
Definition: log.cc:269
SigMap::clear
void clear()
Definition: sigtools.h:263
RTLIL::Wire::width
int width
Definition: rtlil.h:826
sig_at_port
static SigPool sig_at_port
Definition: fsm_detect.cc:35
RTLIL::SigSpec::size
int size() const
Definition: rtlil.h:1019
SigPool::clear
void clear()
Definition: sigtools.h:36
sig2driver_entry_t
std::pair< RTLIL::Cell *, RTLIL::IdString > sig2driver_entry_t
Definition: fsm_detect.cc:32
SigMap::apply
void apply(RTLIL::SigBit &bit) const
Definition: sigtools.h:383
check_state_users
static bool check_state_users(RTLIL::SigSpec sig)
Definition: fsm_detect.cc:73
SigMap::set
void set(RTLIL::Module *module)
Definition: sigtools.h:273
FsmDetectPass::execute
virtual void execute(std::vector< std::string > args, RTLIL::Design *design)
Definition: fsm_detect.cc:143
CellTypes::cell_known
bool cell_known(RTLIL::IdString type)
Definition: celltypes.h:188
SigPool::check_any
bool check_any(RTLIL::SigSpec sig)
Definition: sigtools.h:100
assign_map
static SigMap assign_map
Definition: fsm_detect.cc:31
PRIVATE_NAMESPACE_BEGIN
#define PRIVATE_NAMESPACE_BEGIN
Definition: yosys.h:97
RTLIL::Cell::hasPort
RTLIL_ATTRIBUTE_MEMBERS bool hasPort(RTLIL::IdString portname) const
Definition: rtlil.cc:1766
CellTypes::cell_output
bool cell_output(RTLIL::IdString type, RTLIL::IdString port)
Definition: celltypes.h:193
RTLIL::Cell::getPort
const RTLIL::SigSpec & getPort(RTLIL::IdString portname) const
Definition: rtlil.cc:1809
SigSet::clear
void clear()
Definition: sigtools.h:147
RTLIL::SigSpec::is_fully_const
bool is_fully_const() const
Definition: rtlil.cc:2763
detect_fsm
static void detect_fsm(RTLIL::Wire *wire)
Definition: fsm_detect.cc:101
RTLIL::Module::name
RTLIL::IdString name
Definition: rtlil.h:599
PRIVATE_NAMESPACE_END
#define PRIVATE_NAMESPACE_END
Definition: yosys.h:98
Pass
Definition: register.h:27
RTLIL::Wire::name
RTLIL::IdString name
Definition: rtlil.h:825
RTLIL::id2cstr
static const char * id2cstr(const RTLIL::IdString &str)
Definition: rtlil.h:267
SigPool::add
void add(RTLIL::SigSpec sig)
Definition: sigtools.h:41
USING_YOSYS_NAMESPACE
#define USING_YOSYS_NAMESPACE
Definition: yosys.h:102
RTLIL::Design::modules_
std::map< RTLIL::IdString, RTLIL::Module * > modules_
Definition: rtlil.h:507
RTLIL::Module::cells_
std::map< RTLIL::IdString, RTLIL::Cell * > cells_
Definition: rtlil.h:596
log
void log(const char *format,...)
Definition: log.cc:180
CellTypes::setup_internals
void setup_internals()
Definition: celltypes.h:83
RTLIL::SigSpec::extract
RTLIL::SigSpec extract(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec *other=NULL) const
Definition: rtlil.cc:2414
CellTypes::setup_stdcells_mem
void setup_stdcells_mem()
Definition: celltypes.h:149
sig2driver
static SigSet< sig2driver_entry_t > sig2driver
Definition: fsm_detect.cc:33
sig2user
static SigSet< sig2driver_entry_t > sig2user
Definition: fsm_detect.cc:33
muxtree_cells
static std::set< RTLIL::Cell * > muxtree_cells
Definition: fsm_detect.cc:34
CellTypes::cell_input
bool cell_input(RTLIL::IdString type, RTLIL::IdString port)
Definition: celltypes.h:199
SigPool::del
void del(RTLIL::SigSpec sig)
Definition: sigtools.h:54
Pass::extra_args
void extra_args(std::vector< std::string > args, size_t argidx, RTLIL::Design *design, bool select=true)
Definition: register.cc:128
FsmDetectPass::help
virtual void help()
Definition: fsm_detect.cc:127
RTLIL::Cell::connections
const std::map< RTLIL::IdString, RTLIL::SigSpec > & connections() const
Definition: rtlil.cc:1814
SigSet::find
void find(RTLIL::SigSpec sig, std::set< T > &result)
Definition: sigtools.h:187
SigSet::insert
void insert(RTLIL::SigSpec sig, T data)
Definition: sigtools.h:152
check_state_mux_tree
static bool check_state_mux_tree(RTLIL::SigSpec old_sig, RTLIL::SigSpec sig, SigPool &recursion_monitor)
Definition: fsm_detect.cc:37
module
USING_YOSYS_NAMESPACE static PRIVATE_NAMESPACE_BEGIN RTLIL::Module * module
Definition: fsm_detect.cc:30