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