yosys-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fsm_expand.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 #include <string.h>
27 
28 USING_YOSYS_NAMESPACE
29 PRIVATE_NAMESPACE_BEGIN
30 
31 struct FsmExpand
32 {
33  RTLIL::Module *module;
34  RTLIL::Cell *fsm_cell;
35  SigMap assign_map;
36  SigSet<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> sig2driver, sig2user;
37  CellTypes ct;
38 
39  std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> merged_set;
40  std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> current_set;
41  std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> no_candidate_set;
42 
43  bool already_optimized;
44  int limit_transitions;
45 
46  bool is_cell_merge_candidate(RTLIL::Cell *cell)
47  {
48  if (cell->type == "$mux" || cell->type == "$pmux")
49  if (cell->getPort("\\A").size() < 2)
50  return true;
51 
52  RTLIL::SigSpec new_signals;
53  if (cell->hasPort("\\A"))
54  new_signals.append(assign_map(cell->getPort("\\A")));
55  if (cell->hasPort("\\B"))
56  new_signals.append(assign_map(cell->getPort("\\B")));
57  if (cell->hasPort("\\S"))
58  new_signals.append(assign_map(cell->getPort("\\S")));
59  if (cell->hasPort("\\Y"))
60  new_signals.append(assign_map(cell->getPort("\\Y")));
61 
62  new_signals.sort_and_unify();
63  new_signals.remove_const();
64 
65  new_signals.remove(assign_map(fsm_cell->getPort("\\CTRL_IN")));
66  new_signals.remove(assign_map(fsm_cell->getPort("\\CTRL_OUT")));
67 
68  if (new_signals.size() > 3)
69  return false;
70 
71  if (cell->hasPort("\\Y")) {
72  new_signals.append(assign_map(cell->getPort("\\Y")));
73  new_signals.sort_and_unify();
74  new_signals.remove_const();
75  new_signals.remove(assign_map(fsm_cell->getPort("\\CTRL_IN")));
76  new_signals.remove(assign_map(fsm_cell->getPort("\\CTRL_OUT")));
77  }
78 
79  if (new_signals.size() > 2)
80  return false;
81 
82  return true;
83  }
84 
85  void create_current_set()
86  {
87  std::vector<RTLIL::Cell*> cell_list;
88 
89  for (auto c : sig2driver.find(assign_map(fsm_cell->getPort("\\CTRL_IN"))))
90  cell_list.push_back(c);
91 
92  for (auto c : sig2user.find(assign_map(fsm_cell->getPort("\\CTRL_OUT"))))
93  cell_list.push_back(c);
94 
95  current_set.clear();
96  for (auto c : cell_list)
97  {
98  if (merged_set.count(c) > 0 || current_set.count(c) > 0 || no_candidate_set.count(c) > 0)
99  continue;
100  for (auto &p : c->connections()) {
101  if (p.first != "\\A" && p.first != "\\B" && p.first != "\\S" && p.first != "\\Y")
102  goto next_cell;
103  }
104  if (!is_cell_merge_candidate(c)) {
105  no_candidate_set.insert(c);
106  continue;
107  }
108  current_set.insert(c);
109  next_cell:;
110  }
111  }
112 
113  void optimze_as_needed()
114  {
115  if (already_optimized)
116  return;
117 
118  int trans_num = fsm_cell->parameters["\\TRANS_NUM"].as_int();
119  if (trans_num > limit_transitions)
120  {
121  log(" grown transition table to %d entries -> optimize.\n", trans_num);
122  FsmData::optimize_fsm(fsm_cell, module);
123  already_optimized = true;
124 
125  trans_num = fsm_cell->parameters["\\TRANS_NUM"].as_int();
126  log(" transition table size after optimizaton: %d\n", trans_num);
127  limit_transitions = 16 * trans_num;
128  }
129  }
130 
131  void merge_cell_into_fsm(RTLIL::Cell *cell)
132  {
133  optimze_as_needed();
134 
135  log(" merging %s cell %s.\n", cell->type.c_str(), cell->name.c_str());
136  merged_set.insert(cell);
137  already_optimized = false;
138 
139  RTLIL::SigSpec input_sig, output_sig;
140 
141  for (auto &p : cell->connections())
142  if (ct.cell_output(cell->type, p.first))
143  output_sig.append(assign_map(p.second));
144  else
145  input_sig.append(assign_map(p.second));
146  input_sig.sort_and_unify();
147  input_sig.remove_const();
148 
149  std::vector<RTLIL::Const> truth_tab;
150 
151  for (int i = 0; i < (1 << input_sig.size()); i++) {
152  RTLIL::Const in_val(i, input_sig.size());
153  RTLIL::SigSpec A, B, S;
154  if (cell->hasPort("\\A"))
155  A = assign_map(cell->getPort("\\A"));
156  if (cell->hasPort("\\B"))
157  B = assign_map(cell->getPort("\\B"));
158  if (cell->hasPort("\\S"))
159  S = assign_map(cell->getPort("\\S"));
160  A.replace(input_sig, RTLIL::SigSpec(in_val));
161  B.replace(input_sig, RTLIL::SigSpec(in_val));
162  S.replace(input_sig, RTLIL::SigSpec(in_val));
163  log_assert(A.is_fully_const());
164  log_assert(B.is_fully_const());
165  log_assert(S.is_fully_const());
166  truth_tab.push_back(ct.eval(cell, A.as_const(), B.as_const(), S.as_const()));
167  }
168 
169  FsmData fsm_data;
170  fsm_data.copy_from_cell(fsm_cell);
171 
172  fsm_data.num_inputs += input_sig.size();
173  RTLIL::SigSpec new_ctrl_in = fsm_cell->getPort("\\CTRL_IN");
174  new_ctrl_in.append(input_sig);
175  fsm_cell->setPort("\\CTRL_IN", new_ctrl_in);
176 
177  fsm_data.num_outputs += output_sig.size();
178  RTLIL::SigSpec new_ctrl_out = fsm_cell->getPort("\\CTRL_OUT");
179  new_ctrl_out.append(output_sig);
180  fsm_cell->setPort("\\CTRL_OUT", new_ctrl_out);
181 
182  std::vector<FsmData::transition_t> new_transition_table;
183  for (auto &tr : fsm_data.transition_table) {
184  for (int i = 0; i < (1 << input_sig.size()); i++) {
185  FsmData::transition_t new_tr = tr;
186  RTLIL::Const in_val(i, input_sig.size());
187  RTLIL::Const out_val = truth_tab[i];
188  RTLIL::SigSpec ctrl_in = new_tr.ctrl_in;
189  RTLIL::SigSpec ctrl_out = new_tr.ctrl_out;
190  ctrl_in.append(in_val);
191  ctrl_out.append(out_val);
192  new_tr.ctrl_in = ctrl_in.as_const();
193  new_tr.ctrl_out = ctrl_out.as_const();
194  new_transition_table.push_back(new_tr);
195  }
196  }
197  fsm_data.transition_table.swap(new_transition_table);
198  new_transition_table.clear();
199 
200  fsm_data.copy_to_cell(fsm_cell);
201  }
202 
203  FsmExpand(RTLIL::Cell *cell, RTLIL::Design *design, RTLIL::Module *mod)
204  {
205  module = mod;
206  fsm_cell = cell;
207 
208  assign_map.set(module);
209  ct.setup_internals();
210 
211  for (auto &cell_it : module->cells_) {
212  RTLIL::Cell *c = cell_it.second;
213  if (ct.cell_known(c->type) && design->selected(mod, c))
214  for (auto &p : c->connections()) {
215  if (ct.cell_output(c->type, p.first))
216  sig2driver.insert(assign_map(p.second), c);
217  else
218  sig2user.insert(assign_map(p.second), c);
219  }
220  }
221  }
222 
223  void execute()
224  {
225  log("\n");
226  log("Expanding FSM `%s' from module `%s':\n", fsm_cell->name.c_str(), module->name.c_str());
227 
228  already_optimized = false;
229  limit_transitions = 16 * fsm_cell->parameters["\\TRANS_NUM"].as_int();
230 
231  for (create_current_set(); current_set.size() > 0; create_current_set()) {
232  for (auto c : current_set)
233  merge_cell_into_fsm(c);
234  }
235 
236  for (auto c : merged_set)
237  module->remove(c);
238 
239  if (merged_set.size() > 0 && !already_optimized)
240  FsmData::optimize_fsm(fsm_cell, module);
241 
242  log(" merged %d cells into FSM.\n", GetSize(merged_set));
243  }
244 };
245 
246 struct FsmExpandPass : public Pass {
247  FsmExpandPass() : Pass("fsm_expand", "expand FSM cells by merging logic into it") { }
248  virtual void help()
249  {
250  // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
251  log("\n");
252  log(" fsm_expand [selection]\n");
253  log("\n");
254  log("The fsm_extract pass is conservative about the cells that belong to a finite\n");
255  log("state machine. This pass can be used to merge additional auxiliary gates into\n");
256  log("the finate state machine.\n");
257  log("\n");
258  }
259  virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
260  {
261  log_header("Executing FSM_EXPAND pass (merging auxiliary logic into FSMs).\n");
262  extra_args(args, 1, design);
263 
264  for (auto &mod_it : design->modules_) {
265  if (!design->selected(mod_it.second))
266  continue;
267  std::vector<RTLIL::Cell*> fsm_cells;
268  for (auto &cell_it : mod_it.second->cells_)
269  if (cell_it.second->type == "$fsm" && design->selected(mod_it.second, cell_it.second))
270  fsm_cells.push_back(cell_it.second);
271  for (auto c : fsm_cells) {
272  FsmExpand fsm_expand(c, design, mod_it.second);
273  fsm_expand.execute();
274  }
275  }
276  }
277 } FsmExpandPass;
278 
279 PRIVATE_NAMESPACE_END
RTLIL::IdString::c_str
const char * c_str() const
Definition: rtlil.h:178
RTLIL::Design::selected
bool selected(T1 *module) const
Definition: rtlil.h:551
FsmExpand::assign_map
SigMap assign_map
Definition: fsm_expand.cc:35
FsmData::transition_table
std::vector< transition_t > transition_table
Definition: fsmdata.h:31
FsmExpand::merge_cell_into_fsm
void merge_cell_into_fsm(RTLIL::Cell *cell)
Definition: fsm_expand.cc:131
FsmExpandPass
FsmExpandPass FsmExpandPass
FsmExpand::limit_transitions
int limit_transitions
Definition: fsm_expand.cc:44
log_header
void log_header(const char *format,...)
Definition: log.cc:188
RTLIL::SigSpec::as_const
RTLIL::Const as_const() const
Definition: rtlil.cc:2857
FsmData::transition_t
Definition: fsmdata.h:30
FsmExpand::fsm_cell
RTLIL::Cell * fsm_cell
Definition: fsm_expand.cc:34
FsmExpand::already_optimized
bool already_optimized
Definition: fsm_expand.cc:43
RTLIL::Cell::name
RTLIL::IdString name
Definition: rtlil.h:853
RTLIL::Cell::setPort
void setPort(RTLIL::IdString portname, RTLIL::SigSpec signal)
Definition: rtlil.cc:1789
FsmData::copy_to_cell
void copy_to_cell(RTLIL::Cell *cell)
Definition: fsmdata.h:34
RTLIL::Cell::type
RTLIL::IdString type
Definition: rtlil.h:854
RTLIL::Cell::parameters
std::map< RTLIL::IdString, RTLIL::Const > parameters
Definition: rtlil.h:856
RTLIL::SigSpec::size
int size() const
Definition: rtlil.h:1019
RTLIL::SigSpec::remove
void remove(const RTLIL::SigSpec &pattern)
Definition: rtlil.cc:2342
FsmExpand::create_current_set
void create_current_set()
Definition: fsm_expand.cc:85
FsmData::transition_t::ctrl_out
RTLIL::Const ctrl_out
Definition: fsmdata.h:30
FsmExpandPass::help
virtual void help()
Definition: fsm_expand.cc:248
FsmExpand::no_candidate_set
std::set< RTLIL::Cell *, RTLIL::sort_by_name_id< RTLIL::Cell > > no_candidate_set
Definition: fsm_expand.cc:41
FsmExpandPass::execute
virtual void execute(std::vector< std::string > args, RTLIL::Design *design)
Definition: fsm_expand.cc:259
FsmData::optimize_fsm
static void optimize_fsm(RTLIL::Cell *cell, RTLIL::Module *module)
Definition: fsm_opt.cc:317
FsmExpand::sig2user
SigSet< RTLIL::Cell *, RTLIL::sort_by_name_id< RTLIL::Cell > > sig2user
Definition: fsm_expand.cc:36
SigMap::set
void set(RTLIL::Module *module)
Definition: sigtools.h:273
CellTypes::cell_known
bool cell_known(RTLIL::IdString type)
Definition: celltypes.h:188
FsmExpand::sig2driver
SigSet< RTLIL::Cell *, RTLIL::sort_by_name_id< RTLIL::Cell > > sig2driver
Definition: fsm_expand.cc:36
FsmExpand::optimze_as_needed
void optimze_as_needed()
Definition: fsm_expand.cc:113
FsmData::transition_t::ctrl_in
RTLIL::Const ctrl_in
Definition: fsmdata.h:30
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
FsmData::num_inputs
int num_inputs
Definition: fsmdata.h:29
FsmExpand::is_cell_merge_candidate
bool is_cell_merge_candidate(RTLIL::Cell *cell)
Definition: fsm_expand.cc:46
GetSize
int GetSize(RTLIL::Wire *wire)
Definition: yosys.cc:334
CellTypes::eval
static RTLIL::Const eval(RTLIL::IdString type, const RTLIL::Const &arg1, const RTLIL::Const &arg2, bool signed1, bool signed2, int result_len)
Definition: celltypes.h:219
log_assert
#define log_assert(_assert_expr_)
Definition: log.h:85
FsmExpand::execute
void execute()
Definition: fsm_expand.cc:223
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::SigSpec::remove_const
void remove_const()
Definition: rtlil.cc:2464
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::SigSpec::sort_and_unify
void sort_and_unify()
Definition: rtlil.cc:2291
RTLIL::Module::cells_
std::map< RTLIL::IdString, RTLIL::Cell * > cells_
Definition: rtlil.h:596
RTLIL::Module::remove
void remove(const std::set< RTLIL::Wire * > &wires)
Definition: rtlil.cc:1158
log
void log(const char *format,...)
Definition: log.cc:180
FsmExpand::current_set
std::set< RTLIL::Cell *, RTLIL::sort_by_name_id< RTLIL::Cell > > current_set
Definition: fsm_expand.cc:40
CellTypes::setup_internals
void setup_internals()
Definition: celltypes.h:83
FsmData::copy_from_cell
void copy_from_cell(RTLIL::Cell *cell)
Definition: fsmdata.h:79
FsmData::num_outputs
int num_outputs
Definition: fsmdata.h:29
RTLIL::SigSpec::append
void append(const RTLIL::SigSpec &signal)
Definition: rtlil.cc:2523
FsmExpand::ct
CellTypes ct
Definition: fsm_expand.cc:37
FsmExpand::merged_set
std::set< RTLIL::Cell *, RTLIL::sort_by_name_id< RTLIL::Cell > > merged_set
Definition: fsm_expand.cc:39
Pass::extra_args
void extra_args(std::vector< std::string > args, size_t argidx, RTLIL::Design *design, bool select=true)
Definition: register.cc:128
FsmExpand::FsmExpand
FsmExpand(RTLIL::Cell *cell, RTLIL::Design *design, RTLIL::Module *mod)
Definition: fsm_expand.cc:203
RTLIL::Cell::connections
const std::map< RTLIL::IdString, RTLIL::SigSpec > & connections() const
Definition: rtlil.cc:1814
FsmExpand::module
RTLIL::Module * module
Definition: fsm_expand.cc:33
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