yosys-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Data Structures | Functions | Variables
fsm_map.cc File Reference
#include "kernel/log.h"
#include "kernel/register.h"
#include "kernel/sigtools.h"
#include "kernel/consteval.h"
#include "kernel/celltypes.h"
#include "fsmdata.h"
#include <string.h>
+ Include dependency graph for fsm_map.cc:

Go to the source code of this file.

Data Structures

struct  FsmMapPass
 

Functions

USING_YOSYS_NAMESPACE static
PRIVATE_NAMESPACE_BEGIN bool 		pattern_is_subset (const RTLIL::Const &super_pattern, const RTLIL::Const &sub_pattern)
 
static void implement_pattern_cache (RTLIL::Module *module, std::map< RTLIL::Const, std::set< int >> &pattern_cache, std::set< int > &fullstate_cache, int num_states, RTLIL::Wire *state_onehot, RTLIL::SigSpec &ctrl_in, RTLIL::SigSpec output)
 
static void map_fsm (RTLIL::Cell *fsm_cell, RTLIL::Module *module)
 

Variables

FsmMapPass FsmMapPass
 

Function Documentation

static void implement_pattern_cache ( RTLIL::Module *  module,
std::map< RTLIL::Const, std::set< int >> &  pattern_cache,
std::set< int > &  fullstate_cache,
int  num_states,
RTLIL::Wire *  state_onehot,
RTLIL::SigSpec &  ctrl_in,
RTLIL::SigSpec  output 
)
static

Definition at line 45 of file fsm_map.cc.

46 {
47  RTLIL::SigSpec cases_vector;
48 
49  for (int in_state : fullstate_cache)
50  cases_vector.append(RTLIL::SigSpec(state_onehot, in_state));
51 
52  for (auto &it : pattern_cache)
53  {
54  RTLIL::Const pattern = it.first;
55  RTLIL::SigSpec eq_sig_a, eq_sig_b, or_sig;
56 
57  for (size_t j = 0; j < pattern.bits.size(); j++)
58  if (pattern.bits[j] == RTLIL::State::S0 || pattern.bits[j] == RTLIL::State::S1) {
59  eq_sig_a.append(ctrl_in.extract(j, 1));
60  eq_sig_b.append(RTLIL::SigSpec(pattern.bits[j]));
61  }
62 
63  for (int in_state : it.second)
64  if (fullstate_cache.count(in_state) == 0)
65  or_sig.append(RTLIL::SigSpec(state_onehot, in_state));
66 
67  if (or_sig.size() == 0)
68  continue;
69 
70  RTLIL::SigSpec and_sig;
71 
72  if (eq_sig_a.size() > 0)
73  {
74  RTLIL::Wire *eq_wire = module->addWire(NEW_ID);
75  and_sig.append(RTLIL::SigSpec(eq_wire));
76 
77  RTLIL::Cell *eq_cell = module->addCell(NEW_ID, "$eq");
78  eq_cell->setPort("\\A", eq_sig_a);
79  eq_cell->setPort("\\B", eq_sig_b);
80  eq_cell->setPort("\\Y", RTLIL::SigSpec(eq_wire));
81  eq_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
82  eq_cell->parameters["\\B_SIGNED"] = RTLIL::Const(false);
83  eq_cell->parameters["\\A_WIDTH"] = RTLIL::Const(eq_sig_a.size());
84  eq_cell->parameters["\\B_WIDTH"] = RTLIL::Const(eq_sig_b.size());
85  eq_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
86  }
87 
88  std::set<int> complete_in_state_cache = it.second;
89 
90  for (auto &it2 : pattern_cache)
91  if (pattern_is_subset(pattern, it2.first))
92  complete_in_state_cache.insert(it2.second.begin(), it2.second.end());
93 
94  if (GetSize(complete_in_state_cache) < num_states)
95  {
96  if (or_sig.size() == 1)
97  {
98  and_sig.append(or_sig);
99  }
100  else
101  {
102  RTLIL::Wire *or_wire = module->addWire(NEW_ID);
103  and_sig.append(RTLIL::SigSpec(or_wire));
104 
105  RTLIL::Cell *or_cell = module->addCell(NEW_ID, "$reduce_or");
106  or_cell->setPort("\\A", or_sig);
107  or_cell->setPort("\\Y", RTLIL::SigSpec(or_wire));
108  or_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
109  or_cell->parameters["\\A_WIDTH"] = RTLIL::Const(or_sig.size());
110  or_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
111  }
112  }
113 
114  switch (and_sig.size())
115  {
116  case 2:
117  {
118  RTLIL::Wire *and_wire = module->addWire(NEW_ID);
119  cases_vector.append(RTLIL::SigSpec(and_wire));
120 
121  RTLIL::Cell *and_cell = module->addCell(NEW_ID, "$and");
122  and_cell->setPort("\\A", and_sig.extract(0, 1));
123  and_cell->setPort("\\B", and_sig.extract(1, 1));
124  and_cell->setPort("\\Y", RTLIL::SigSpec(and_wire));
125  and_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
126  and_cell->parameters["\\B_SIGNED"] = RTLIL::Const(false);
127  and_cell->parameters["\\A_WIDTH"] = RTLIL::Const(1);
128  and_cell->parameters["\\B_WIDTH"] = RTLIL::Const(1);
129  and_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
130  break;
131  }
132  case 1:
133  cases_vector.append(and_sig);
134  break;
135  case 0:
136  cases_vector.append(RTLIL::SigSpec(1, 1));
137  break;
138  default:
139  log_abort();
140  }
141  }
142 
143  if (cases_vector.size() > 1) {
144  RTLIL::Cell *or_cell = module->addCell(NEW_ID, "$reduce_or");
145  or_cell->setPort("\\A", cases_vector);
146  or_cell->setPort("\\Y", output);
147  or_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
148  or_cell->parameters["\\A_WIDTH"] = RTLIL::Const(cases_vector.size());
149  or_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
150  } else if (cases_vector.size() == 1) {
151  module->connect(RTLIL::SigSig(output, cases_vector));
152  } else {
153  module->connect(RTLIL::SigSig(output, RTLIL::SigSpec(0, 1)));
154  }
155 }
RTLIL::Module::addCell
RTLIL::Cell * addCell(RTLIL::IdString name, RTLIL::IdString type)
Definition: rtlil.cc:1353
RTLIL::Cell::setPort
void setPort(RTLIL::IdString portname, RTLIL::SigSpec signal)
Definition: rtlil.cc:1789
RTLIL::Cell::parameters
std::map< RTLIL::IdString, RTLIL::Const > parameters
Definition: rtlil.h:856
RTLIL::SigSpec::size
int size() const
Definition: rtlil.h:1019
log_abort
#define log_abort()
Definition: log.h:84
pattern_is_subset
USING_YOSYS_NAMESPACE static PRIVATE_NAMESPACE_BEGIN bool pattern_is_subset(const RTLIL::Const &super_pattern, const RTLIL::Const &sub_pattern)
Definition: fsm_map.cc:31
RTLIL::Module::connect
void connect(const RTLIL::SigSig &conn)
Definition: rtlil.cc:1278
GetSize
int GetSize(RTLIL::Wire *wire)
Definition: yosys.cc:334
RTLIL::Module::addWire
RTLIL::Wire * addWire(RTLIL::IdString name, int width=1)
Definition: rtlil.cc:1331
NEW_ID
#define NEW_ID
Definition: yosys.h:166
RTLIL::SigSpec::extract
RTLIL::SigSpec extract(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec *other=NULL) const
Definition: rtlil.cc:2414
RTLIL::Const::bits
std::vector< RTLIL::State > bits
Definition: rtlil.h:438
RTLIL::SigSpec::append
void append(const RTLIL::SigSpec &signal)
Definition: rtlil.cc:2523
RTLIL::SigSig
std::pair< SigSpec, SigSpec > SigSig
Definition: rtlil.h:71

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

static void map_fsm ( RTLIL::Cell *  fsm_cell,
RTLIL::Module *  module 
)
static

Definition at line 157 of file fsm_map.cc.

158 {
159  log("Mapping FSM `%s' from module `%s'.\n", fsm_cell->name.c_str(), module->name.c_str());
160 
161  FsmData fsm_data;
162  fsm_data.copy_from_cell(fsm_cell);
163 
164  RTLIL::SigSpec ctrl_in = fsm_cell->getPort("\\CTRL_IN");
165  RTLIL::SigSpec ctrl_out = fsm_cell->getPort("\\CTRL_OUT");
166 
167  // create state register
168 
169  RTLIL::Wire *state_wire = module->addWire(module->uniquify(fsm_cell->parameters["\\NAME"].decode_string()), fsm_data.state_bits);
170  RTLIL::Wire *next_state_wire = module->addWire(NEW_ID, fsm_data.state_bits);
171 
172  RTLIL::Cell *state_dff = module->addCell(NEW_ID, "");
173  if (fsm_cell->getPort("\\ARST").is_fully_const()) {
174  state_dff->type = "$dff";
175  } else {
176  state_dff->type = "$adff";
177  state_dff->parameters["\\ARST_POLARITY"] = fsm_cell->parameters["\\ARST_POLARITY"];
178  state_dff->parameters["\\ARST_VALUE"] = fsm_data.state_table[fsm_data.reset_state];
179  for (auto &bit : state_dff->parameters["\\ARST_VALUE"].bits)
180  if (bit != RTLIL::State::S1)
181  bit = RTLIL::State::S0;
182  state_dff->setPort("\\ARST", fsm_cell->getPort("\\ARST"));
183  }
184  state_dff->parameters["\\WIDTH"] = RTLIL::Const(fsm_data.state_bits);
185  state_dff->parameters["\\CLK_POLARITY"] = fsm_cell->parameters["\\CLK_POLARITY"];
186  state_dff->setPort("\\CLK", fsm_cell->getPort("\\CLK"));
187  state_dff->setPort("\\D", RTLIL::SigSpec(next_state_wire));
188  state_dff->setPort("\\Q", RTLIL::SigSpec(state_wire));
189 
190  // decode state register
191 
192  bool encoding_is_onehot = true;
193 
194  RTLIL::Wire *state_onehot = module->addWire(NEW_ID, fsm_data.state_table.size());
195 
196  for (size_t i = 0; i < fsm_data.state_table.size(); i++)
197  {
198  RTLIL::Const state = fsm_data.state_table[i];
199  RTLIL::SigSpec sig_a, sig_b;
200 
201  for (size_t j = 0; j < state.bits.size(); j++)
202  if (state.bits[j] == RTLIL::State::S0 || state.bits[j] == RTLIL::State::S1) {
203  sig_a.append(RTLIL::SigSpec(state_wire, j));
204  sig_b.append(RTLIL::SigSpec(state.bits[j]));
205  }
206 
207  if (sig_b == RTLIL::SigSpec(RTLIL::State::S1))
208  {
209  module->connect(RTLIL::SigSig(RTLIL::SigSpec(state_onehot, i), sig_a));
210  }
211  else
212  {
213  encoding_is_onehot = false;
214 
215  RTLIL::Cell *eq_cell = module->addCell(NEW_ID, "$eq");
216  eq_cell->setPort("\\A", sig_a);
217  eq_cell->setPort("\\B", sig_b);
218  eq_cell->setPort("\\Y", RTLIL::SigSpec(state_onehot, i));
219  eq_cell->parameters["\\A_SIGNED"] = RTLIL::Const(false);
220  eq_cell->parameters["\\B_SIGNED"] = RTLIL::Const(false);
221  eq_cell->parameters["\\A_WIDTH"] = RTLIL::Const(sig_a.size());
222  eq_cell->parameters["\\B_WIDTH"] = RTLIL::Const(sig_b.size());
223  eq_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
224  }
225  }
226 
227  // generate next_state signal
228 
229  if (GetSize(fsm_data.state_table) == 1)
230  {
231  module->connect(next_state_wire, fsm_data.state_table.front());
232  }
233  else
234  {
235  RTLIL::Wire *next_state_onehot = module->addWire(NEW_ID, fsm_data.state_table.size());
236 
237  for (size_t i = 0; i < fsm_data.state_table.size(); i++)
238  {
239  std::map<RTLIL::Const, std::set<int>> pattern_cache;
240  std::set<int> fullstate_cache;
241 
242  for (size_t j = 0; j < fsm_data.state_table.size(); j++)
243  fullstate_cache.insert(j);
244 
245  for (auto &tr : fsm_data.transition_table) {
246  if (tr.state_out == int(i))
247  pattern_cache[tr.ctrl_in].insert(tr.state_in);
248  else
249  fullstate_cache.erase(tr.state_in);
250  }
251 
252  implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, RTLIL::SigSpec(next_state_onehot, i));
253  }
254 
255  if (encoding_is_onehot)
256  {
257  RTLIL::SigSpec next_state_sig(RTLIL::State::Sm, next_state_wire->width);
258  for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
259  RTLIL::Const state = fsm_data.state_table[i];
260  int bit_idx = -1;
261  for (size_t j = 0; j < state.bits.size(); j++)
262  if (state.bits[j] == RTLIL::State::S1)
263  bit_idx = j;
264  if (bit_idx >= 0)
265  next_state_sig.replace(bit_idx, RTLIL::SigSpec(next_state_onehot, i));
266  }
267  log_assert(!next_state_sig.has_marked_bits());
268  module->connect(RTLIL::SigSig(next_state_wire, next_state_sig));
269  }
270  else
271  {
272  RTLIL::SigSpec sig_a, sig_b, sig_s;
273  int reset_state = fsm_data.reset_state;
274  if (reset_state < 0)
275  reset_state = 0;
276 
277  for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
278  RTLIL::Const state = fsm_data.state_table[i];
279  if (int(i) == fsm_data.reset_state) {
280  sig_a = RTLIL::SigSpec(state);
281  } else {
282  sig_b.append(RTLIL::SigSpec(state));
283  sig_s.append(RTLIL::SigSpec(next_state_onehot, i));
284  }
285  }
286 
287  RTLIL::Cell *mux_cell = module->addCell(NEW_ID, "$pmux");
288  mux_cell->setPort("\\A", sig_a);
289  mux_cell->setPort("\\B", sig_b);
290  mux_cell->setPort("\\S", sig_s);
291  mux_cell->setPort("\\Y", RTLIL::SigSpec(next_state_wire));
292  mux_cell->parameters["\\WIDTH"] = RTLIL::Const(sig_a.size());
293  mux_cell->parameters["\\S_WIDTH"] = RTLIL::Const(sig_s.size());
294  }
295  }
296 
297  // Generate ctrl_out signal
298 
299  for (int i = 0; i < fsm_data.num_outputs; i++)
300  {
301  std::map<RTLIL::Const, std::set<int>> pattern_cache;
302  std::set<int> fullstate_cache;
303 
304  for (size_t j = 0; j < fsm_data.state_table.size(); j++)
305  fullstate_cache.insert(j);
306 
307  for (auto &tr : fsm_data.transition_table) {
308  if (tr.ctrl_out.bits[i] == RTLIL::State::S1)
309  pattern_cache[tr.ctrl_in].insert(tr.state_in);
310  else
311  fullstate_cache.erase(tr.state_in);
312  }
313 
314  implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, ctrl_out.extract(i, 1));
315  }
316 
317  // Remove FSM cell
318 
319  module->remove(fsm_cell);
320 }
RTLIL::IdString::c_str
const char * c_str() const
Definition: rtlil.h:178
RTLIL::Module::addCell
RTLIL::Cell * addCell(RTLIL::IdString name, RTLIL::IdString type)
Definition: rtlil.cc:1353
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
RTLIL::Wire::width
int width
Definition: rtlil.h:826
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::Module::connect
void connect(const RTLIL::SigSig &conn)
Definition: rtlil.cc:1278
RTLIL::Cell::getPort
const RTLIL::SigSpec & getPort(RTLIL::IdString portname) const
Definition: rtlil.cc:1809
GetSize
int GetSize(RTLIL::Wire *wire)
Definition: yosys.cc:334
log_assert
#define log_assert(_assert_expr_)
Definition: log.h:85
RTLIL::SigSpec::is_fully_const
bool is_fully_const() const
Definition: rtlil.cc:2763
RTLIL::Module::addWire
RTLIL::Wire * addWire(RTLIL::IdString name, int width=1)
Definition: rtlil.cc:1331
RTLIL::Module::name
RTLIL::IdString name
Definition: rtlil.h:599
NEW_ID
#define NEW_ID
Definition: yosys.h:166
RTLIL::Module::remove
void remove(const std::set< RTLIL::Wire * > &wires)
Definition: rtlil.cc:1158
RTLIL::Module::uniquify
RTLIL::IdString uniquify(RTLIL::IdString name)
Definition: rtlil.cc:1244
log
void log(const char *format,...)
Definition: log.cc:180
FsmData::copy_from_cell
void copy_from_cell(RTLIL::Cell *cell)
Definition: fsmdata.h:79
RTLIL::SigSpec::extract
RTLIL::SigSpec extract(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec *other=NULL) const
Definition: rtlil.cc:2414
RTLIL::Const::bits
std::vector< RTLIL::State > bits
Definition: rtlil.h:438
RTLIL::SigSpec::append
void append(const RTLIL::SigSpec &signal)
Definition: rtlil.cc:2523
RTLIL::SigSig
std::pair< SigSpec, SigSpec > SigSig
Definition: rtlil.h:71
implement_pattern_cache
static void implement_pattern_cache(RTLIL::Module *module, std::map< RTLIL::Const, std::set< int >> &pattern_cache, std::set< int > &fullstate_cache, int num_states, RTLIL::Wire *state_onehot, RTLIL::SigSpec &ctrl_in, RTLIL::SigSpec output)
Definition: fsm_map.cc:45

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

USING_YOSYS_NAMESPACE static PRIVATE_NAMESPACE_BEGIN bool pattern_is_subset ( const RTLIL::Const &  super_pattern,
const RTLIL::Const &  sub_pattern 
)
static

Definition at line 31 of file fsm_map.cc.

32 {
33  log_assert(GetSize(super_pattern.bits) == GetSize(sub_pattern.bits));
34  for (int i = 0; i < GetSize(super_pattern.bits); i++)
35  if (sub_pattern.bits[i] == RTLIL::State::S0 || sub_pattern.bits[i] == RTLIL::State::S1) {
36  if (super_pattern.bits[i] == RTLIL::State::S0 || super_pattern.bits[i] == RTLIL::State::S1) {
37  if (super_pattern.bits[i] != sub_pattern.bits[i])
38  return false;
39  } else
40  return false;
41  }
42  return true;
43 }
GetSize
int GetSize(RTLIL::Wire *wire)
Definition: yosys.cc:334
log_assert
#define log_assert(_assert_expr_)
Definition: log.h:85
RTLIL::Const::bits
std::vector< RTLIL::State > bits
Definition: rtlil.h:438

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Variable Documentation

FsmMapPass FsmMapPass