passes/fsm/fsm_expand.cc

   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         bool full_mode;
  36
  37         SigMap assign_map;
  38         SigSet<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> sig2driver, sig2user;
  39         CellTypes ct;
  40
  41         std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> merged_set;
  42         std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> current_set;
  43         std::set<RTLIL::Cell*, RTLIL::sort_by_name_id<RTLIL::Cell>> no_candidate_set;
  44
  45         bool already_optimized;
  46         int limit_transitions;
  47
  48         bool is_cell_merge_candidate(RTLIL::Cell *cell)
  49         {
  50                 if (full_mode || cell->type == ID($_MUX_))
  51                         return true;
  52
  53                 if (cell->type.in(ID($mux), ID($pmux)))
  54                         if (cell->getPort(ID::A).size() < 2)
  55                                 return true;
  56
  57                 int in_bits = 0;
  58                 RTLIL::SigSpec new_signals;
  59
  60                 if (cell->hasPort(ID::A)) {
  61                         in_bits += GetSize(cell->getPort(ID::A));
  62                         new_signals.append(assign_map(cell->getPort(ID::A)));
  63                 }
  64
  65                 if (cell->hasPort(ID::B)) {
  66                         in_bits += GetSize(cell->getPort(ID::B));
  67                         new_signals.append(assign_map(cell->getPort(ID::B)));
  68                 }
  69
  70                 if (cell->hasPort(ID::S)) {
  71                         in_bits += GetSize(cell->getPort(ID::S));
  72                         new_signals.append(assign_map(cell->getPort(ID::S)));
  73                 }
  74
  75                 if (in_bits > 8)
  76                         return false;
  77
  78                 if (cell->hasPort(ID::Y))
  79                         new_signals.append(assign_map(cell->getPort(ID::Y)));
  80
  81                 new_signals.sort_and_unify();
  82                 new_signals.remove_const();
  83
  84                 new_signals.remove(assign_map(fsm_cell->getPort(ID::CTRL_IN)));
  85                 new_signals.remove(assign_map(fsm_cell->getPort(ID::CTRL_OUT)));
  86
  87                 if (new_signals.size() > 3)
  88                         return false;
  89
  90                 return true;
  91         }
  92
  93         void create_current_set()
  94         {
  95                 std::vector<RTLIL::Cell*> cell_list;
  96
  97                 for (auto c : sig2driver.find(assign_map(fsm_cell->getPort(ID::CTRL_IN))))
  98                         cell_list.push_back(c);
  99
 100                 for (auto c : sig2user.find(assign_map(fsm_cell->getPort(ID::CTRL_OUT))))
 101                         cell_list.push_back(c);
 102
 103                 current_set.clear();
 104                 for (auto c : cell_list)
 105                 {
 106                         if (merged_set.count(c) > 0 || current_set.count(c) > 0 || no_candidate_set.count(c) > 0)
 107                                 continue;
 108                         for (auto &p : c->connections()) {
 109                                 if (p.first != ID::A && p.first != ID::B && p.first != ID::S && p.first != ID::Y)
 110                                         goto next_cell;
 111                         }
 112                         if (!is_cell_merge_candidate(c)) {
 113                                 no_candidate_set.insert(c);
 114                                 continue;
 115                         }
 116                         current_set.insert(c);
 117                 next_cell:;
 118                 }
 119         }
 120
 121         void optimze_as_needed()
 122         {
 123                 if (already_optimized)
 124                         return;
 125
 126                 int trans_num = fsm_cell->parameters[ID::TRANS_NUM].as_int();
 127                 if (trans_num > limit_transitions)
 128                 {
 129                         log("  grown transition table to %d entries -> optimize.\n", trans_num);
 130                         FsmData::optimize_fsm(fsm_cell, module);
 131                         already_optimized = true;
 132
 133                         trans_num = fsm_cell->parameters[ID::TRANS_NUM].as_int();
 134                         log("  transition table size after optimizaton: %d\n", trans_num);
 135                         limit_transitions = 16 * trans_num;
 136                 }
 137         }
 138
 139         void merge_cell_into_fsm(RTLIL::Cell *cell)
 140         {
 141                 optimze_as_needed();
 142
 143                 log("  merging %s cell %s.\n", cell->type.c_str(), cell->name.c_str());
 144                 merged_set.insert(cell);
 145                 already_optimized = false;
 146
 147                 RTLIL::SigSpec input_sig, output_sig;
 148
 149                 for (auto &p : cell->connections())
 150                         if (ct.cell_output(cell->type, p.first))
 151                                 output_sig.append(assign_map(p.second));
 152                         else
 153                                 input_sig.append(assign_map(p.second));
 154                 input_sig.sort_and_unify();
 155                 input_sig.remove_const();
 156
 157                 std::vector<RTLIL::Const> truth_tab;
 158
 159                 for (int i = 0; i < (1 << input_sig.size()); i++) {
 160                         RTLIL::Const in_val(i, input_sig.size());
 161                         RTLIL::SigSpec A, B, S;
 162                         if (cell->hasPort(ID::A))
 163                                 A = assign_map(cell->getPort(ID::A));
 164                         if (cell->hasPort(ID::B))
 165                                 B = assign_map(cell->getPort(ID::B));
 166                         if (cell->hasPort(ID::S))
 167                                 S = assign_map(cell->getPort(ID::S));
 168                         A.replace(input_sig, RTLIL::SigSpec(in_val));
 169                         B.replace(input_sig, RTLIL::SigSpec(in_val));
 170                         S.replace(input_sig, RTLIL::SigSpec(in_val));
 171                         log_assert(A.is_fully_const());
 172                         log_assert(B.is_fully_const());
 173                         log_assert(S.is_fully_const());
 174                         truth_tab.push_back(ct.eval(cell, A.as_const(), B.as_const(), S.as_const()));
 175                 }
 176
 177                 FsmData fsm_data;
 178                 fsm_data.copy_from_cell(fsm_cell);
 179
 180                 fsm_data.num_inputs += input_sig.size();
 181                 RTLIL::SigSpec new_ctrl_in = fsm_cell->getPort(ID::CTRL_IN);
 182                 new_ctrl_in.append(input_sig);
 183                 fsm_cell->setPort(ID::CTRL_IN, new_ctrl_in);
 184
 185                 fsm_data.num_outputs += output_sig.size();
 186                 RTLIL::SigSpec new_ctrl_out = fsm_cell->getPort(ID::CTRL_OUT);
 187                 new_ctrl_out.append(output_sig);
 188                 fsm_cell->setPort(ID::CTRL_OUT, new_ctrl_out);
 189
 190                 if (GetSize(input_sig) > 10)
 191                         log_warning("Cell %s.%s (%s) has %d input bits, merging into FSM %s.%s might be problematic.\n",
 192                                         log_id(cell->module), log_id(cell), log_id(cell->type),
 193                                         GetSize(input_sig), log_id(fsm_cell->module), log_id(fsm_cell));
 194
 195                 if (GetSize(fsm_data.transition_table) > 10000)
 196                         log_warning("Transition table for FSM %s.%s already has %d rows, merging more cells "
 197                                         "into this FSM might be problematic.\n", log_id(fsm_cell->module), log_id(fsm_cell),
 198                                         GetSize(fsm_data.transition_table));
 199
 200                 std::vector<FsmData::transition_t> new_transition_table;
 201                 for (auto &tr : fsm_data.transition_table) {
 202                         for (int i = 0; i < (1 << input_sig.size()); i++) {
 203                                 FsmData::transition_t new_tr = tr;
 204                                 RTLIL::Const in_val(i, input_sig.size());
 205                                 RTLIL::Const out_val = truth_tab[i];
 206                                 RTLIL::SigSpec ctrl_in = new_tr.ctrl_in;
 207                                 RTLIL::SigSpec ctrl_out = new_tr.ctrl_out;
 208                                 ctrl_in.append(in_val);
 209                                 ctrl_out.append(out_val);
 210                                 new_tr.ctrl_in = ctrl_in.as_const();
 211                                 new_tr.ctrl_out = ctrl_out.as_const();
 212                                 new_transition_table.push_back(new_tr);
 213                         }
 214                 }
 215                 fsm_data.transition_table.swap(new_transition_table);
 216                 new_transition_table.clear();
 217
 218                 fsm_data.copy_to_cell(fsm_cell);
 219         }
 220
 221         FsmExpand(RTLIL::Cell *cell, RTLIL::Design *design, RTLIL::Module *mod, bool full)
 222         {
 223                 module = mod;
 224                 fsm_cell = cell;
 225                 full_mode = full;
 226
 227                 assign_map.set(module);
 228                 ct.setup_internals();
 229                 ct.setup_stdcells();
 230
 231                 for (auto &cell_it : module->cells_) {
 232                         RTLIL::Cell *c = cell_it.second;
 233                         if (ct.cell_known(c->type) && design->selected(mod, c))
 234                                 for (auto &p : c->connections()) {
 235                                         if (ct.cell_output(c->type, p.first))
 236                                                 sig2driver.insert(assign_map(p.second), c);
 237                                         else
 238                                                 sig2user.insert(assign_map(p.second), c);
 239                                 }
 240                 }
 241         }
 242
 243         void execute()
 244         {
 245                 log("\n");
 246                 log("Expanding FSM `%s' from module `%s':\n", fsm_cell->name.c_str(), module->name.c_str());
 247
 248                 already_optimized = false;
 249                 limit_transitions =  16 * fsm_cell->parameters[ID::TRANS_NUM].as_int();
 250
 251                 for (create_current_set(); current_set.size() > 0; create_current_set()) {
 252                         for (auto c : current_set)
 253                                 merge_cell_into_fsm(c);
 254                 }
 255
 256                 for (auto c : merged_set)
 257                         module->remove(c);
 258
 259                 if (merged_set.size() > 0 && !already_optimized)
 260                         FsmData::optimize_fsm(fsm_cell, module);
 261
 262                 log("  merged %d cells into FSM.\n", GetSize(merged_set));
 263         }
 264 };
 265
 266 struct FsmExpandPass : public Pass {
 267         FsmExpandPass() : Pass("fsm_expand", "expand FSM cells by merging logic into it") { }
 268         void help() override
 269         {
 270                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 271                 log("\n");
 272                 log("    fsm_expand [-full] [selection]\n");
 273                 log("\n");
 274                 log("The fsm_extract pass is conservative about the cells that belong to a finite\n");
 275                 log("state machine. This pass can be used to merge additional auxiliary gates into\n");
 276                 log("the finite state machine.\n");
 277                 log("\n");
 278                 log("By default, fsm_expand is still a bit conservative regarding merging larger\n");
 279                 log("word-wide cells. Call with -full to consider all cells for merging.\n");
 280                 log("\n");
 281         }
 282         void execute(std::vector<std::string> args, RTLIL::Design *design) override
 283         {
 284                 bool full_mode = false;
 285
 286                 log_header(design, "Executing FSM_EXPAND pass (merging auxiliary logic into FSMs).\n");
 287
 288                 size_t argidx;
 289                 for (argidx = 1; argidx < args.size(); argidx++) {
 290                         if (args[argidx] == "-full") {
 291                                 full_mode = true;
 292                                 continue;
 293                         }
 294                         break;
 295                 }
 296                 extra_args(args, argidx, design);
 297
 298                 for (auto mod : design->selected_modules()) {
 299                         std::vector<RTLIL::Cell*> fsm_cells;
 300                         for (auto cell : mod->selected_cells())
 301                                 if (cell->type == ID($fsm))
 302                                         fsm_cells.push_back(cell);
 303                         for (auto c : fsm_cells) {
 304                                 FsmExpand fsm_expand(c, design, mod, full_mode);
 305                                 fsm_expand.execute();
 306                         }
 307                 }
 308         }
 309 } FsmExpandPass;
 310
 311 PRIVATE_NAMESPACE_END