passes/fsm/fsm_opt.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 FsmOpt
  32 {
  33         FsmData fsm_data;
  34         RTLIL::Cell *cell;
  35         RTLIL::Module *module;
  36
  37         void opt_unreachable_states()
  38         {
  39                 while (1)
  40                 {
  41                         std::set<int> unreachable_states;
  42                         std::vector<FsmData::transition_t> new_transition_table;
  43                         std::vector<RTLIL::Const> new_state_table;
  44                         std::map<int, int> old_to_new_state;
  45
  46                         for (int i = 0; i < GetSize(fsm_data.state_table); i++)
  47                                 if (i != fsm_data.reset_state)
  48                                         unreachable_states.insert(i);
  49
  50                         for (auto &trans : fsm_data.transition_table)
  51                                 unreachable_states.erase(trans.state_out);
  52
  53                         if (unreachable_states.empty())
  54                                 break;
  55
  56                         for (int i = 0; i < GetSize(fsm_data.state_table); i++) {
  57                                 if (unreachable_states.count(i)) {
  58                                         log("  Removing unreachable state %s.\n", log_signal(fsm_data.state_table[i]));
  59                                         continue;
  60                                 }
  61                                 old_to_new_state[i] = GetSize(new_state_table);
  62                                 new_state_table.push_back(fsm_data.state_table[i]);
  63                         }
  64
  65                         for (auto trans : fsm_data.transition_table) {
  66                                 if (unreachable_states.count(trans.state_in))
  67                                         continue;
  68                                 trans.state_in = old_to_new_state.at(trans.state_in);
  69                                 trans.state_out = old_to_new_state.at(trans.state_out);
  70                                 new_transition_table.push_back(trans);
  71                         }
  72
  73                         new_transition_table.swap(fsm_data.transition_table);
  74                         new_state_table.swap(fsm_data.state_table);
  75                         fsm_data.reset_state = old_to_new_state.at(fsm_data.reset_state);
  76                 }
  77         }
  78
  79         bool signal_is_unused(RTLIL::SigSpec sig)
  80         {
  81                 RTLIL::SigBit bit = sig.to_single_sigbit();
  82
  83                 if (bit.wire == NULL || bit.wire->attributes.count("\\unused_bits") == 0)
  84                         return false;
  85
  86                 char *str = strdup(bit.wire->attributes["\\unused_bits"].decode_string().c_str());
  87                 for (char *tok = strtok(str, " "); tok != NULL; tok = strtok(NULL, " ")) {
  88                         if (tok[0] && bit.offset == atoi(tok)) {
  89                                 free(str);
  90                                 return true;
  91                         }
  92                 }
  93                 free(str);
  94
  95                 return false;
  96         }
  97
  98         void opt_const_and_unused_inputs()
  99         {
 100                 RTLIL::SigSpec ctrl_in = cell->getPort("\\CTRL_IN");
 101                 std::vector<bool> ctrl_in_used(ctrl_in.size());
 102
 103                 std::vector<FsmData::transition_t> new_transition_table;
 104                 for (auto &tr : fsm_data.transition_table) {
 105                         for (int i = 0; i < ctrl_in.size(); i++) {
 106                                 RTLIL::SigSpec ctrl_bit = ctrl_in.extract(i, 1);
 107                                 if (ctrl_bit.is_fully_const()) {
 108                                         if (tr.ctrl_in.bits[i] <= RTLIL::State::S1 && RTLIL::SigSpec(tr.ctrl_in.bits[i]) != ctrl_bit)
 109                                                 goto delete_this_transition;
 110                                         continue;
 111                                 }
 112                                 if (tr.ctrl_in.bits[i] <= RTLIL::State::S1)
 113                                         ctrl_in_used[i] = true;
 114                         }
 115                         new_transition_table.push_back(tr);
 116                 delete_this_transition:;
 117                 }
 118
 119                 for (int i = int(ctrl_in_used.size())-1; i >= 0; i--) {
 120                         if (!ctrl_in_used[i]) {
 121                                 log("  Removing unused input signal %s.\n", log_signal(cell->getPort("\\CTRL_IN").extract(i, 1)));
 122                                 for (auto &tr : new_transition_table) {
 123                                         RTLIL::SigSpec tmp(tr.ctrl_in);
 124                                         tmp.remove(i, 1);
 125                                         tr.ctrl_in = tmp.as_const();
 126                                 }
 127                                 RTLIL::SigSpec new_ctrl_in = cell->getPort("\\CTRL_IN");
 128                                 new_ctrl_in.remove(i, 1);
 129                                 cell->setPort("\\CTRL_IN", new_ctrl_in);
 130                                 fsm_data.num_inputs--;
 131                         }
 132                 }
 133
 134                 fsm_data.transition_table.swap(new_transition_table);
 135                 new_transition_table.clear();
 136         }
 137
 138         void opt_unused_outputs()
 139         {
 140                 for (int i = 0; i < fsm_data.num_outputs; i++) {
 141                         RTLIL::SigSpec sig = cell->getPort("\\CTRL_OUT").extract(i, 1);
 142                         if (signal_is_unused(sig)) {
 143                                 log("  Removing unused output signal %s.\n", log_signal(sig));
 144                                 RTLIL::SigSpec new_ctrl_out = cell->getPort("\\CTRL_OUT");
 145                                 new_ctrl_out.remove(i, 1);
 146                                 cell->setPort("\\CTRL_OUT", new_ctrl_out);
 147                                 for (auto &tr : fsm_data.transition_table) {
 148                                         RTLIL::SigSpec tmp(tr.ctrl_out);
 149                                         tmp.remove(i, 1);
 150                                         tr.ctrl_out = tmp.as_const();
 151                                 }
 152                                 fsm_data.num_outputs--;
 153                                 i--;
 154                         }
 155                 }
 156         }
 157
 158         void opt_alias_inputs()
 159         {
 160                 RTLIL::SigSpec &ctrl_in = cell->connections_["\\CTRL_IN"];
 161
 162                 for (int i = 0; i < ctrl_in.size(); i++)
 163                 for (int j = i+1; j < ctrl_in.size(); j++)
 164                         if (ctrl_in.extract(i, 1) == ctrl_in.extract(j, 1))
 165                         {
 166                                 log("  Optimize handling of signal %s that is connected to inputs %d and %d.\n", log_signal(ctrl_in.extract(i, 1)), i, j);
 167                                 std::vector<FsmData::transition_t> new_transition_table;
 168
 169                                 for (auto tr : fsm_data.transition_table)
 170                                 {
 171                                         RTLIL::State &si = tr.ctrl_in.bits[i];
 172                                         RTLIL::State &sj = tr.ctrl_in.bits[j];
 173
 174                                         if (si > RTLIL::State::S1)
 175                                                 si = sj;
 176                                         else if (sj > RTLIL::State::S1)
 177                                                 sj = si;
 178
 179                                         if (si == sj) {
 180                                                 RTLIL::SigSpec tmp(tr.ctrl_in);
 181                                                 tmp.remove(j, 1);
 182                                                 tr.ctrl_in = tmp.as_const();
 183                                                 new_transition_table.push_back(tr);
 184                                         }
 185                                 }
 186
 187                                 ctrl_in.remove(j--, 1);
 188                                 fsm_data.num_inputs--;
 189
 190                                 fsm_data.transition_table.swap(new_transition_table);
 191                                 new_transition_table.clear();
 192                         }
 193         }
 194
 195         void opt_feedback_inputs()
 196         {
 197                 RTLIL::SigSpec &ctrl_in = cell->connections_["\\CTRL_IN"];
 198                 RTLIL::SigSpec &ctrl_out = cell->connections_["\\CTRL_OUT"];
 199
 200                 for (int j = 0; j < ctrl_out.size(); j++)
 201                 for (int i = 0; i < ctrl_in.size(); i++)
 202                         if (ctrl_in.extract(i, 1) == ctrl_out.extract(j, 1))
 203                         {
 204                                 log("  Optimize handling of signal %s that is connected to input %d and output %d.\n", log_signal(ctrl_in.extract(i, 1)), i, j);
 205                                 std::vector<FsmData::transition_t> new_transition_table;
 206
 207                                 for (auto tr : fsm_data.transition_table)
 208                                 {
 209                                         RTLIL::State &si = tr.ctrl_in.bits[i];
 210                                         RTLIL::State &sj = tr.ctrl_out.bits[j];
 211
 212                                         if (si > RTLIL::State::S1 || si == sj) {
 213                                                 RTLIL::SigSpec tmp(tr.ctrl_in);
 214                                                 tmp.remove(i, 1);
 215                                                 tr.ctrl_in = tmp.as_const();
 216                                                 new_transition_table.push_back(tr);
 217                                         }
 218                                 }
 219
 220                                 ctrl_in.remove(i--, 1);
 221                                 fsm_data.num_inputs--;
 222
 223                                 fsm_data.transition_table.swap(new_transition_table);
 224                                 new_transition_table.clear();
 225                         }
 226         }
 227
 228         void opt_find_dont_care_worker(std::set<RTLIL::Const> &set, int bit, FsmData::transition_t &tr, bool &did_something)
 229         {
 230                 std::set<RTLIL::Const> new_set;
 231
 232                 for (auto &pattern : set)
 233                 {
 234                         if (pattern.bits[bit] > RTLIL::State::S1) {
 235                                 new_set.insert(pattern);
 236                                 continue;
 237                         }
 238
 239                         RTLIL::Const other_pattern = pattern;
 240
 241                         if (pattern.bits[bit] == RTLIL::State::S1)
 242                                 other_pattern.bits[bit] = RTLIL::State::S0;
 243                         else
 244                                 other_pattern.bits[bit] = RTLIL::State::S1;
 245
 246                         if (set.count(other_pattern) > 0) {
 247                                 log("  Merging pattern %s and %s from group (%d %d %s).\n", log_signal(pattern), log_signal(other_pattern),
 248                                                 tr.state_in, tr.state_out, log_signal(tr.ctrl_out));
 249                                 other_pattern.bits[bit] = RTLIL::State::Sa;
 250                                 new_set.insert(other_pattern);
 251                                 did_something = true;
 252                                 continue;
 253                         }
 254
 255                         new_set.insert(pattern);
 256                 }
 257
 258                 set.swap(new_set);
 259         }
 260
 261         void opt_find_dont_care()
 262         {
 263                 typedef std::pair<std::pair<int, int>, RTLIL::Const> group_t;
 264                 std::map<group_t, std::set<RTLIL::Const>> transitions_by_group;
 265
 266                 for (auto &tr : fsm_data.transition_table) {
 267                         group_t group(std::pair<int, int>(tr.state_in, tr.state_out), tr.ctrl_out);
 268                         transitions_by_group[group].insert(tr.ctrl_in);
 269                 }
 270
 271                 fsm_data.transition_table.clear();
 272                 for (auto &it : transitions_by_group)
 273                 {
 274                         FsmData::transition_t tr;
 275                         tr.state_in = it.first.first.first;
 276                         tr.state_out = it.first.first.second;
 277                         tr.ctrl_out = it.first.second;
 278
 279                         bool did_something = true;
 280                         while (did_something) {
 281                                 did_something = false;
 282                                 for (int i = 0; i < fsm_data.num_inputs; i++)
 283                                         opt_find_dont_care_worker(it.second, i, tr, did_something);
 284                         }
 285
 286                         for (auto &ci : it.second) {
 287                                 tr.ctrl_in = ci;
 288                                 fsm_data.transition_table.push_back(tr);
 289                         }
 290                 }
 291         }
 292
 293         FsmOpt(RTLIL::Cell *cell, RTLIL::Module *module)
 294         {
 295                 log("Optimizing FSM `%s' from module `%s'.\n", cell->name.c_str(), module->name.c_str());
 296
 297                 fsm_data.copy_from_cell(cell);
 298                 this->cell = cell;
 299                 this->module = module;
 300
 301                 opt_unreachable_states();
 302
 303                 opt_unused_outputs();
 304
 305                 opt_alias_inputs();
 306                 opt_feedback_inputs();
 307                 opt_find_dont_care();
 308
 309                 opt_const_and_unused_inputs();
 310
 311                 fsm_data.copy_to_cell(cell);
 312         }
 313 };
 314
 315 PRIVATE_NAMESPACE_END
 316
 317 void YOSYS_NAMESPACE_PREFIX FsmData::optimize_fsm(RTLIL::Cell *cell, RTLIL::Module *module)
 318 {
 319         FsmOpt fsmopt(cell, module);
 320 }
 321
 322 PRIVATE_NAMESPACE_BEGIN
 323
 324 struct FsmOptPass : public Pass {
 325         FsmOptPass() : Pass("fsm_opt", "optimize finite state machines") { }
 326         virtual void help()
 327         {
 328                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 329                 log("\n");
 330                 log("    fsm_opt [selection]\n");
 331                 log("\n");
 332                 log("This pass optimizes FSM cells. It detects which output signals are actually\n");
 333                 log("not used and removes them from the FSM. This pass is usually used in\n");
 334                 log("combination with the 'opt_clean' pass (see also 'help fsm').\n");
 335                 log("\n");
 336         }
 337         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 338         {
 339                 log_header("Executing FSM_OPT pass (simple optimizations of FSMs).\n");
 340                 extra_args(args, 1, design);
 341
 342                 for (auto &mod_it : design->modules_) {
 343                         if (design->selected(mod_it.second))
 344                                 for (auto &cell_it : mod_it.second->cells_)
 345                                         if (cell_it.second->type == "$fsm" && design->selected(mod_it.second, cell_it.second))
 346                                                 FsmData::optimize_fsm(cell_it.second, mod_it.second);
 347                 }
 348         }
 349 } FsmOptPass;
 350
 351 PRIVATE_NAMESPACE_END