passes/proc/proc_mux.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/register.h"
  21 #include "kernel/bitpattern.h"
  22 #include "kernel/log.h"
  23 #include <sstream>
  24 #include <stdlib.h>
  25 #include <stdio.h>
  26
  27 USING_YOSYS_NAMESPACE
  28 PRIVATE_NAMESPACE_BEGIN
  29
  30 struct SigSnippets
  31 {
  32         idict<SigSpec> sigidx;
  33         dict<SigBit, int> bit2snippet;
  34         pool<int> snippets;
  35
  36         void insert(SigSpec sig)
  37         {
  38                 if (sig.empty())
  39                         return;
  40
  41                 int key = sigidx(sig);
  42                 if (snippets.count(key))
  43                         return;
  44
  45                 SigSpec new_sig;
  46
  47                 for (int i = 0; i < GetSize(sig); i++)
  48                 {
  49                         int other_key = bit2snippet.at(sig[i], -1);
  50
  51                         if (other_key < 0) {
  52                                 new_sig.append(sig[i]);
  53                                 continue;
  54                         }
  55
  56                         if (!new_sig.empty()) {
  57                                 int new_key = sigidx(new_sig);
  58                                 snippets.insert(new_key);
  59                                 for (auto bit : new_sig)
  60                                         bit2snippet[bit] = new_key;
  61                                 new_sig = SigSpec();
  62                         }
  63
  64                         SigSpec other_sig = sigidx[other_key];
  65                         int k = 0, n = 1;
  66
  67                         while (other_sig[k] != sig[i]) {
  68                                 k++;
  69                                 log_assert(k < GetSize(other_sig));
  70                         }
  71
  72                         while (i+n < GetSize(sig) && k+n < GetSize(other_sig) && sig[i+n] == other_sig[k+n])
  73                                 n++;
  74
  75                         SigSpec sig1 = other_sig.extract(0, k);
  76                         SigSpec sig2 = other_sig.extract(k, n);
  77                         SigSpec sig3 = other_sig.extract(k+n, GetSize(other_sig)-k-n);
  78
  79                         for (auto bit : other_sig)
  80                                 bit2snippet.erase(bit);
  81                         snippets.erase(other_key);
  82
  83                         insert(sig1);
  84                         insert(sig2);
  85                         insert(sig3);
  86
  87                         i += n-1;
  88                 }
  89
  90                 if (!new_sig.empty()) {
  91                         int new_key = sigidx(new_sig);
  92                         snippets.insert(new_key);
  93                         for (auto bit : new_sig)
  94                                 bit2snippet[bit] = new_key;
  95                 }
  96         }
  97
  98         void insert(const RTLIL::CaseRule *cs)
  99         {
 100                 for (auto &action : cs->actions)
 101                         insert(action.first);
 102
 103                 for (auto sw : cs->switches)
 104                 for (auto cs2 : sw->cases)
 105                         insert(cs2);
 106         }
 107 };
 108
 109 struct SnippetSwCache
 110 {
 111         dict<RTLIL::SwitchRule*, pool<RTLIL::SigBit>, hash_ptr_ops> full_case_bits_cache;
 112         dict<RTLIL::SwitchRule*, pool<int>, hash_ptr_ops> cache;
 113         const SigSnippets *snippets;
 114         int current_snippet;
 115
 116         bool check(RTLIL::SwitchRule *sw)
 117         {
 118                 return cache[sw].count(current_snippet) != 0;
 119         }
 120
 121         void insert(const RTLIL::CaseRule *cs, vector<RTLIL::SwitchRule*> &sw_stack)
 122         {
 123                 for (auto &action : cs->actions)
 124                 for (auto bit : action.first) {
 125                         int sn = snippets->bit2snippet.at(bit, -1);
 126                         if (sn < 0)
 127                                 continue;
 128                         for (auto sw : sw_stack)
 129                                 cache[sw].insert(sn);
 130                 }
 131
 132                 for (auto sw : cs->switches) {
 133                         sw_stack.push_back(sw);
 134                         for (auto cs2 : sw->cases)
 135                                 insert(cs2, sw_stack);
 136                         sw_stack.pop_back();
 137                 }
 138         }
 139
 140         void insert(const RTLIL::CaseRule *cs)
 141         {
 142                 vector<RTLIL::SwitchRule*> sw_stack;
 143                 insert(cs, sw_stack);
 144         }
 145 };
 146
 147 RTLIL::SigSpec gen_cmp(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector<RTLIL::SigSpec> &compare, RTLIL::SwitchRule *sw, bool ifxmode)
 148 {
 149         std::stringstream sstr;
 150         sstr << "$procmux$" << (autoidx++);
 151
 152         RTLIL::Wire *cmp_wire = mod->addWire(sstr.str() + "_CMP", 0);
 153
 154         for (auto comp : compare)
 155         {
 156                 RTLIL::SigSpec sig = signal;
 157
 158                 // get rid of don't-care bits
 159                 log_assert(sig.size() == comp.size());
 160                 for (int i = 0; i < comp.size(); i++)
 161                         if (comp[i] == RTLIL::State::Sa) {
 162                                 sig.remove(i);
 163                                 comp.remove(i--);
 164                         }
 165                 if (comp.size() == 0)
 166                         return RTLIL::SigSpec();
 167
 168                 if (sig.size() == 1 && comp == RTLIL::SigSpec(1,1) && !ifxmode)
 169                 {
 170                         mod->connect(RTLIL::SigSig(RTLIL::SigSpec(cmp_wire, cmp_wire->width++), sig));
 171                 }
 172                 else
 173                 {
 174                         // create compare cell
 175                         RTLIL::Cell *eq_cell = mod->addCell(stringf("%s_CMP%d", sstr.str().c_str(), cmp_wire->width), ifxmode ? "$eqx" : "$eq");
 176                         eq_cell->attributes = sw->attributes;
 177
 178                         eq_cell->parameters["\\A_SIGNED"] = RTLIL::Const(0);
 179                         eq_cell->parameters["\\B_SIGNED"] = RTLIL::Const(0);
 180
 181                         eq_cell->parameters["\\A_WIDTH"] = RTLIL::Const(sig.size());
 182                         eq_cell->parameters["\\B_WIDTH"] = RTLIL::Const(comp.size());
 183                         eq_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
 184
 185                         eq_cell->setPort("\\A", sig);
 186                         eq_cell->setPort("\\B", comp);
 187                         eq_cell->setPort("\\Y", RTLIL::SigSpec(cmp_wire, cmp_wire->width++));
 188                 }
 189         }
 190
 191         RTLIL::Wire *ctrl_wire;
 192         if (cmp_wire->width == 1)
 193         {
 194                 ctrl_wire = cmp_wire;
 195         }
 196         else
 197         {
 198                 ctrl_wire = mod->addWire(sstr.str() + "_CTRL");
 199
 200                 // reduce cmp vector to one logic signal
 201                 RTLIL::Cell *any_cell = mod->addCell(sstr.str() + "_ANY", "$reduce_or");
 202                 any_cell->attributes = sw->attributes;
 203
 204                 any_cell->parameters["\\A_SIGNED"] = RTLIL::Const(0);
 205                 any_cell->parameters["\\A_WIDTH"] = RTLIL::Const(cmp_wire->width);
 206                 any_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1);
 207
 208                 any_cell->setPort("\\A", cmp_wire);
 209                 any_cell->setPort("\\Y", RTLIL::SigSpec(ctrl_wire));
 210         }
 211
 212         return RTLIL::SigSpec(ctrl_wire);
 213 }
 214
 215 RTLIL::SigSpec gen_mux(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector<RTLIL::SigSpec> &compare, RTLIL::SigSpec when_signal, RTLIL::SigSpec else_signal, RTLIL::Cell *&last_mux_cell, RTLIL::SwitchRule *sw, bool ifxmode)
 216 {
 217         log_assert(when_signal.size() == else_signal.size());
 218
 219         std::stringstream sstr;
 220         sstr << "$procmux$" << (autoidx++);
 221
 222         // the trivial cases
 223         if (compare.size() == 0 || when_signal == else_signal)
 224                 return when_signal;
 225
 226         // compare results
 227         RTLIL::SigSpec ctrl_sig = gen_cmp(mod, signal, compare, sw, ifxmode);
 228         if (ctrl_sig.size() == 0)
 229                 return when_signal;
 230         log_assert(ctrl_sig.size() == 1);
 231
 232         // prepare multiplexer output signal
 233         RTLIL::Wire *result_wire = mod->addWire(sstr.str() + "_Y", when_signal.size());
 234
 235         // create the multiplexer itself
 236         RTLIL::Cell *mux_cell = mod->addCell(sstr.str(), "$mux");
 237         mux_cell->attributes = sw->attributes;
 238
 239         mux_cell->parameters["\\WIDTH"] = RTLIL::Const(when_signal.size());
 240         mux_cell->setPort("\\A", else_signal);
 241         mux_cell->setPort("\\B", when_signal);
 242         mux_cell->setPort("\\S", ctrl_sig);
 243         mux_cell->setPort("\\Y", RTLIL::SigSpec(result_wire));
 244
 245         last_mux_cell = mux_cell;
 246         return RTLIL::SigSpec(result_wire);
 247 }
 248
 249 void append_pmux(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector<RTLIL::SigSpec> &compare, RTLIL::SigSpec when_signal, RTLIL::Cell *last_mux_cell, RTLIL::SwitchRule *sw, bool ifxmode)
 250 {
 251         log_assert(last_mux_cell != NULL);
 252         log_assert(when_signal.size() == last_mux_cell->getPort("\\A").size());
 253
 254         if (when_signal == last_mux_cell->getPort("\\A"))
 255                 return;
 256
 257         RTLIL::SigSpec ctrl_sig = gen_cmp(mod, signal, compare, sw, ifxmode);
 258         log_assert(ctrl_sig.size() == 1);
 259         last_mux_cell->type = "$pmux";
 260
 261         RTLIL::SigSpec new_s = last_mux_cell->getPort("\\S");
 262         new_s.append(ctrl_sig);
 263         last_mux_cell->setPort("\\S", new_s);
 264
 265         RTLIL::SigSpec new_b = last_mux_cell->getPort("\\B");
 266         new_b.append(when_signal);
 267         last_mux_cell->setPort("\\B", new_b);
 268
 269         last_mux_cell->parameters["\\S_WIDTH"] = last_mux_cell->getPort("\\S").size();
 270 }
 271
 272 const pool<SigBit> &get_full_case_bits(SnippetSwCache &swcache, RTLIL::SwitchRule *sw)
 273 {
 274         if (!swcache.full_case_bits_cache.count(sw))
 275         {
 276                 pool<SigBit> bits;
 277
 278                 if (sw->get_bool_attribute("\\full_case"))
 279                 {
 280                         bool first_case = true;
 281
 282                         for (auto cs : sw->cases)
 283                         {
 284                                 pool<SigBit> case_bits;
 285
 286                                 for (auto it : cs->actions) {
 287                                         for (auto bit : it.first)
 288                                                 case_bits.insert(bit);
 289                                 }
 290
 291                                 for (auto it : cs->switches) {
 292                                         for (auto bit : get_full_case_bits(swcache, it))
 293                                                 case_bits.insert(bit);
 294                                 }
 295
 296                                 if (first_case) {
 297                                         first_case = false;
 298                                         bits = case_bits;
 299                                 } else {
 300                                         pool<SigBit> new_bits;
 301                                         for (auto bit : bits)
 302                                                 if (case_bits.count(bit))
 303                                                         new_bits.insert(bit);
 304                                         bits.swap(new_bits);
 305                                 }
 306                         }
 307                 }
 308
 309                 bits.swap(swcache.full_case_bits_cache[sw]);
 310         }
 311
 312         return swcache.full_case_bits_cache.at(sw);
 313 }
 314
 315 RTLIL::SigSpec signal_to_mux_tree(RTLIL::Module *mod, SnippetSwCache &swcache, dict<RTLIL::SwitchRule*, bool, hash_ptr_ops> &swpara,
 316                 RTLIL::CaseRule *cs, const RTLIL::SigSpec &sig, const RTLIL::SigSpec &defval, bool ifxmode)
 317 {
 318         RTLIL::SigSpec result = defval;
 319
 320         for (auto &action : cs->actions) {
 321                 sig.replace(action.first, action.second, &result);
 322                 action.first.remove2(sig, &action.second);
 323         }
 324
 325         for (auto sw : cs->switches)
 326         {
 327                 if (!swcache.check(sw))
 328                         continue;
 329
 330                 // detect groups of parallel cases
 331                 std::vector<int> pgroups(sw->cases.size());
 332                 bool is_simple_parallel_case = true;
 333
 334                 if (!sw->get_bool_attribute("\\parallel_case")) {
 335                         if (!swpara.count(sw)) {
 336                                 pool<Const> case_values;
 337                                 for (size_t i = 0; i < sw->cases.size(); i++) {
 338                                         RTLIL::CaseRule *cs2 = sw->cases[i];
 339                                         for (auto pat : cs2->compare) {
 340                                                 if (!pat.is_fully_def())
 341                                                         goto not_simple_parallel_case;
 342                                                 Const cpat = pat.as_const();
 343                                                 if (case_values.count(cpat))
 344                                                         goto not_simple_parallel_case;
 345                                                 case_values.insert(cpat);
 346                                         }
 347                                 }
 348                                 if (0)
 349                         not_simple_parallel_case:
 350                                         is_simple_parallel_case = false;
 351                                 swpara[sw] = is_simple_parallel_case;
 352                         } else {
 353                                 is_simple_parallel_case = swpara.at(sw);
 354                         }
 355                 }
 356
 357                 if (!is_simple_parallel_case) {
 358                         BitPatternPool pool(sw->signal.size());
 359                         bool extra_group_for_next_case = false;
 360                         for (size_t i = 0; i < sw->cases.size(); i++) {
 361                                 RTLIL::CaseRule *cs2 = sw->cases[i];
 362                                 if (i != 0) {
 363                                         pgroups[i] = pgroups[i-1];
 364                                         if (extra_group_for_next_case) {
 365                                                 pgroups[i] = pgroups[i-1]+1;
 366                                                 extra_group_for_next_case = false;
 367                                         }
 368                                         for (auto pat : cs2->compare)
 369                                                 if (!pat.is_fully_const() || !pool.has_all(pat))
 370                                                         pgroups[i] = pgroups[i-1]+1;
 371                                         if (cs2->compare.empty())
 372                                                 pgroups[i] = pgroups[i-1]+1;
 373                                         if (pgroups[i] != pgroups[i-1])
 374                                                 pool = BitPatternPool(sw->signal.size());
 375                                 }
 376                                 for (auto pat : cs2->compare)
 377                                         if (!pat.is_fully_const())
 378                                                 extra_group_for_next_case = true;
 379                                         else if (!ifxmode)
 380                                                 pool.take(pat);
 381                         }
 382                 }
 383
 384                 // mask default bits that are irrelevant because the output is driven by a full case
 385                 const pool<SigBit> &full_case_bits = get_full_case_bits(swcache, sw);
 386                 for (int i = 0; i < GetSize(sig); i++)
 387                         if (full_case_bits.count(sig[i]))
 388                                 result[i] = State::Sx;
 389
 390                 // evaluate in reverse order to give the first entry the top priority
 391                 RTLIL::SigSpec initial_val = result;
 392                 RTLIL::Cell *last_mux_cell = NULL;
 393                 for (size_t i = 0; i < sw->cases.size(); i++) {
 394                         int case_idx = sw->cases.size() - i - 1;
 395                         RTLIL::CaseRule *cs2 = sw->cases[case_idx];
 396                         RTLIL::SigSpec value = signal_to_mux_tree(mod, swcache, swpara, cs2, sig, initial_val, ifxmode);
 397                         if (last_mux_cell && pgroups[case_idx] == pgroups[case_idx+1])
 398                                 append_pmux(mod, sw->signal, cs2->compare, value, last_mux_cell, sw, ifxmode);
 399                         else
 400                                 result = gen_mux(mod, sw->signal, cs2->compare, value, result, last_mux_cell, sw, ifxmode);
 401                 }
 402         }
 403
 404         return result;
 405 }
 406
 407 void proc_mux(RTLIL::Module *mod, RTLIL::Process *proc, bool ifxmode)
 408 {
 409         log("Creating decoders for process `%s.%s'.\n", mod->name.c_str(), proc->name.c_str());
 410
 411         SigSnippets sigsnip;
 412         sigsnip.insert(&proc->root_case);
 413
 414         SnippetSwCache swcache;
 415         swcache.snippets = &sigsnip;
 416         swcache.insert(&proc->root_case);
 417
 418         dict<RTLIL::SwitchRule*, bool, hash_ptr_ops> swpara;
 419
 420         int cnt = 0;
 421         for (int idx : sigsnip.snippets)
 422         {
 423                 swcache.current_snippet = idx;
 424                 RTLIL::SigSpec sig = sigsnip.sigidx[idx];
 425
 426                 log("%6d/%d: %s\n", ++cnt, GetSize(sigsnip.snippets), log_signal(sig));
 427
 428                 RTLIL::SigSpec value = signal_to_mux_tree(mod, swcache, swpara, &proc->root_case, sig, RTLIL::SigSpec(RTLIL::State::Sx, sig.size()), ifxmode);
 429                 mod->connect(RTLIL::SigSig(sig, value));
 430         }
 431 }
 432
 433 struct ProcMuxPass : public Pass {
 434         ProcMuxPass() : Pass("proc_mux", "convert decision trees to multiplexers") { }
 435         void help() YS_OVERRIDE
 436         {
 437                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 438                 log("\n");
 439                 log("    proc_mux [options] [selection]\n");
 440                 log("\n");
 441                 log("This pass converts the decision trees in processes (originating from if-else\n");
 442                 log("and case statements) to trees of multiplexer cells.\n");
 443                 log("\n");
 444                 log("    -ifx\n");
 445                 log("        Use Verilog simulation behavior with respect to undef values in\n");
 446                 log("        'case' expressions and 'if' conditions.\n");
 447                 log("\n");
 448         }
 449         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 450         {
 451                 bool ifxmode = false;
 452                 log_header(design, "Executing PROC_MUX pass (convert decision trees to multiplexers).\n");
 453
 454                 size_t argidx;
 455                 for (argidx = 1; argidx < args.size(); argidx++)
 456                 {
 457                         if (args[argidx] == "-ifx") {
 458                                 ifxmode = true;
 459                                 continue;
 460                         }
 461                         break;
 462                 }
 463                 extra_args(args, argidx, design);
 464
 465                 for (auto mod : design->modules())
 466                         if (design->selected(mod))
 467                                 for (auto &proc_it : mod->processes)
 468                                         if (design->selected(mod, proc_it.second))
 469                                                 proc_mux(mod, proc_it.second, ifxmode);
 470         }
 471 } ProcMuxPass;
 472
 473 PRIVATE_NAMESPACE_END