passes/fsm/fsm_map.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Claire Xenia Wolf <claire@yosyshq.com>
   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 static bool pattern_is_subset(const RTLIL::Const &super_pattern, const RTLIL::Const &sub_pattern)
  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 }
  44
  45 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)
  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, ID($eq));
  78                         eq_cell->setPort(ID::A, eq_sig_a);
  79                         eq_cell->setPort(ID::B, eq_sig_b);
  80                         eq_cell->setPort(ID::Y, RTLIL::SigSpec(eq_wire));
  81                         eq_cell->parameters[ID::A_SIGNED] = RTLIL::Const(false);
  82                         eq_cell->parameters[ID::B_SIGNED] = RTLIL::Const(false);
  83                         eq_cell->parameters[ID::A_WIDTH] = RTLIL::Const(eq_sig_a.size());
  84                         eq_cell->parameters[ID::B_WIDTH] = RTLIL::Const(eq_sig_b.size());
  85                         eq_cell->parameters[ID::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, ID($reduce_or));
 106                                 or_cell->setPort(ID::A, or_sig);
 107                                 or_cell->setPort(ID::Y, RTLIL::SigSpec(or_wire));
 108                                 or_cell->parameters[ID::A_SIGNED] = RTLIL::Const(false);
 109                                 or_cell->parameters[ID::A_WIDTH] = RTLIL::Const(or_sig.size());
 110                                 or_cell->parameters[ID::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, ID($and));
 122                                 and_cell->setPort(ID::A, and_sig.extract(0, 1));
 123                                 and_cell->setPort(ID::B, and_sig.extract(1, 1));
 124                                 and_cell->setPort(ID::Y, RTLIL::SigSpec(and_wire));
 125                                 and_cell->parameters[ID::A_SIGNED] = RTLIL::Const(false);
 126                                 and_cell->parameters[ID::B_SIGNED] = RTLIL::Const(false);
 127                                 and_cell->parameters[ID::A_WIDTH] = RTLIL::Const(1);
 128                                 and_cell->parameters[ID::B_WIDTH] = RTLIL::Const(1);
 129                                 and_cell->parameters[ID::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(State::S1);
 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, ID($reduce_or));
 145                 or_cell->setPort(ID::A, cases_vector);
 146                 or_cell->setPort(ID::Y, output);
 147                 or_cell->parameters[ID::A_SIGNED] = RTLIL::Const(false);
 148                 or_cell->parameters[ID::A_WIDTH] = RTLIL::Const(cases_vector.size());
 149                 or_cell->parameters[ID::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, State::S0));
 154         }
 155 }
 156
 157 static void map_fsm(RTLIL::Cell *fsm_cell, RTLIL::Module *module)
 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(ID::CTRL_IN);
 165         RTLIL::SigSpec ctrl_out = fsm_cell->getPort(ID::CTRL_OUT);
 166
 167         // create state register
 168
 169         RTLIL::Wire *state_wire = module->addWire(module->uniquify(fsm_cell->parameters[ID::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(ID::ARST).is_fully_const()) {
 174                 state_dff->type = ID($dff);
 175         } else {
 176                 state_dff->type = ID($adff);
 177                 state_dff->parameters[ID::ARST_POLARITY] = fsm_cell->parameters[ID::ARST_POLARITY];
 178                 state_dff->parameters[ID::ARST_VALUE] = fsm_data.state_table[fsm_data.reset_state];
 179                 for (auto &bit : state_dff->parameters[ID::ARST_VALUE].bits)
 180                         if (bit != RTLIL::State::S1)
 181                                 bit = RTLIL::State::S0;
 182                 state_dff->setPort(ID::ARST, fsm_cell->getPort(ID::ARST));
 183         }
 184         state_dff->parameters[ID::WIDTH] = RTLIL::Const(fsm_data.state_bits);
 185         state_dff->parameters[ID::CLK_POLARITY] = fsm_cell->parameters[ID::CLK_POLARITY];
 186         state_dff->setPort(ID::CLK, fsm_cell->getPort(ID::CLK));
 187         state_dff->setPort(ID::D, RTLIL::SigSpec(next_state_wire));
 188         state_dff->setPort(ID::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, ID($eq));
 216                         eq_cell->setPort(ID::A, sig_a);
 217                         eq_cell->setPort(ID::B, sig_b);
 218                         eq_cell->setPort(ID::Y, RTLIL::SigSpec(state_onehot, i));
 219                         eq_cell->parameters[ID::A_SIGNED] = RTLIL::Const(false);
 220                         eq_cell->parameters[ID::B_SIGNED] = RTLIL::Const(false);
 221                         eq_cell->parameters[ID::A_WIDTH] = RTLIL::Const(sig_a.size());
 222                         eq_cell->parameters[ID::B_WIDTH] = RTLIL::Const(sig_b.size());
 223                         eq_cell->parameters[ID::Y_WIDTH] = RTLIL::Const(1);
 224                 }
 225         }
 226
 227         if (encoding_is_onehot)
 228                 state_wire->set_bool_attribute(ID::onehot);
 229
 230         // generate next_state signal
 231
 232         if (GetSize(fsm_data.state_table) == 1)
 233         {
 234                 module->connect(next_state_wire, fsm_data.state_table.front());
 235         }
 236         else
 237         {
 238                 RTLIL::Wire *next_state_onehot = module->addWire(NEW_ID, fsm_data.state_table.size());
 239
 240                 for (size_t i = 0; i < fsm_data.state_table.size(); i++)
 241                 {
 242                         std::map<RTLIL::Const, std::set<int>> pattern_cache;
 243                         std::set<int> fullstate_cache;
 244
 245                         for (size_t j = 0; j < fsm_data.state_table.size(); j++)
 246                                 fullstate_cache.insert(j);
 247
 248                         for (auto &tr : fsm_data.transition_table) {
 249                                 if (tr.state_out == int(i))
 250                                         pattern_cache[tr.ctrl_in].insert(tr.state_in);
 251                                 else
 252                                         fullstate_cache.erase(tr.state_in);
 253                         }
 254
 255                         implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, RTLIL::SigSpec(next_state_onehot, i));
 256                 }
 257
 258                 if (encoding_is_onehot)
 259                 {
 260                         RTLIL::SigSpec next_state_sig(RTLIL::State::Sm, next_state_wire->width);
 261                         for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
 262                                 RTLIL::Const state = fsm_data.state_table[i];
 263                                 int bit_idx = -1;
 264                                 for (size_t j = 0; j < state.bits.size(); j++)
 265                                         if (state.bits[j] == RTLIL::State::S1)
 266                                                 bit_idx = j;
 267                                 if (bit_idx >= 0)
 268                                         next_state_sig.replace(bit_idx, RTLIL::SigSpec(next_state_onehot, i));
 269                         }
 270                         log_assert(!next_state_sig.has_marked_bits());
 271                         module->connect(RTLIL::SigSig(next_state_wire, next_state_sig));
 272                 }
 273                 else
 274                 {
 275                         RTLIL::SigSpec sig_a(RTLIL::State::Sx, next_state_wire->width);
 276                         RTLIL::SigSpec sig_b, sig_s;
 277
 278                         for (size_t i = 0; i < fsm_data.state_table.size(); i++) {
 279                                 RTLIL::Const state = fsm_data.state_table[i];
 280                                 if (int(i) == fsm_data.reset_state) {
 281                                         sig_a = RTLIL::SigSpec(state);
 282                                 } else {
 283                                         sig_b.append(RTLIL::SigSpec(state));
 284                                         sig_s.append(RTLIL::SigSpec(next_state_onehot, i));
 285                                 }
 286                         }
 287
 288                         RTLIL::Cell *mux_cell = module->addCell(NEW_ID, ID($pmux));
 289                         mux_cell->setPort(ID::A, sig_a);
 290                         mux_cell->setPort(ID::B, sig_b);
 291                         mux_cell->setPort(ID::S, sig_s);
 292                         mux_cell->setPort(ID::Y, RTLIL::SigSpec(next_state_wire));
 293                         mux_cell->parameters[ID::WIDTH] = RTLIL::Const(sig_a.size());
 294                         mux_cell->parameters[ID::S_WIDTH] = RTLIL::Const(sig_s.size());
 295                 }
 296         }
 297
 298         // Generate ctrl_out signal
 299
 300         for (int i = 0; i < fsm_data.num_outputs; i++)
 301         {
 302                 std::map<RTLIL::Const, std::set<int>> pattern_cache;
 303                 std::set<int> fullstate_cache;
 304
 305                 for (size_t j = 0; j < fsm_data.state_table.size(); j++)
 306                         fullstate_cache.insert(j);
 307
 308                 for (auto &tr : fsm_data.transition_table) {
 309                         if (tr.ctrl_out.bits[i] == RTLIL::State::S1)
 310                                 pattern_cache[tr.ctrl_in].insert(tr.state_in);
 311                         else
 312                                 fullstate_cache.erase(tr.state_in);
 313                 }
 314
 315                 implement_pattern_cache(module, pattern_cache, fullstate_cache, fsm_data.state_table.size(), state_onehot, ctrl_in, ctrl_out.extract(i, 1));
 316         }
 317
 318         // Remove FSM cell
 319
 320         module->remove(fsm_cell);
 321 }
 322
 323 struct FsmMapPass : public Pass {
 324         FsmMapPass() : Pass("fsm_map", "mapping FSMs to basic logic") { }
 325         void help() override
 326         {
 327                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 328                 log("\n");
 329                 log("    fsm_map [selection]\n");
 330                 log("\n");
 331                 log("This pass translates FSM cells to flip-flops and logic.\n");
 332                 log("\n");
 333         }
 334         void execute(std::vector<std::string> args, RTLIL::Design *design) override
 335         {
 336                 log_header(design, "Executing FSM_MAP pass (mapping FSMs to basic logic).\n");
 337                 extra_args(args, 1, design);
 338
 339                 for (auto mod : design->selected_modules()) {
 340                         std::vector<RTLIL::Cell*> fsm_cells;
 341                         for (auto cell : mod->selected_cells())
 342                                 if (cell->type == ID($fsm))
 343                                         fsm_cells.push_back(cell);
 344                         for (auto cell : fsm_cells)
 345                                         map_fsm(cell, mod);
 346                 }
 347         }
 348 } FsmMapPass;
 349
 350 PRIVATE_NAMESPACE_END