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 void apply_attrs(RTLIL::Cell *cell, const RTLIL::SwitchRule *sw, const RTLIL::CaseRule *cs)
 148 {
 149         cell->attributes = sw->attributes;
 150         cell->add_strpool_attribute(ID::src, cs->get_strpool_attribute(ID::src));
 151 }
 152
 153 RTLIL::SigSpec gen_cmp(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector<RTLIL::SigSpec> &compare, RTLIL::SwitchRule *sw, RTLIL::CaseRule *cs, bool ifxmode)
 154 {
 155         std::stringstream sstr;
 156         sstr << "$procmux$" << (autoidx++);
 157
 158         RTLIL::Wire *cmp_wire = mod->addWire(sstr.str() + "_CMP", 0);
 159
 160         for (auto comp : compare)
 161         {
 162                 RTLIL::SigSpec sig = signal;
 163
 164                 // get rid of don't-care bits
 165                 log_assert(sig.size() == comp.size());
 166                 for (int i = 0; i < comp.size(); i++)
 167                         if (comp[i] == RTLIL::State::Sa) {
 168                                 sig.remove(i);
 169                                 comp.remove(i--);
 170                         }
 171                 if (comp.size() == 0)
 172                         return RTLIL::SigSpec();
 173
 174                 if (sig.size() == 1 && comp == RTLIL::SigSpec(1,1) && !ifxmode)
 175                 {
 176                         mod->connect(RTLIL::SigSig(RTLIL::SigSpec(cmp_wire, cmp_wire->width++), sig));
 177                 }
 178                 else
 179                 {
 180                         // create compare cell
 181                         RTLIL::Cell *eq_cell = mod->addCell(stringf("%s_CMP%d", sstr.str().c_str(), cmp_wire->width), ifxmode ? ID($eqx) : ID($eq));
 182                         apply_attrs(eq_cell, sw, cs);
 183
 184                         eq_cell->parameters[ID::A_SIGNED] = RTLIL::Const(0);
 185                         eq_cell->parameters[ID::B_SIGNED] = RTLIL::Const(0);
 186
 187                         eq_cell->parameters[ID::A_WIDTH] = RTLIL::Const(sig.size());
 188                         eq_cell->parameters[ID::B_WIDTH] = RTLIL::Const(comp.size());
 189                         eq_cell->parameters[ID::Y_WIDTH] = RTLIL::Const(1);
 190
 191                         eq_cell->setPort(ID::A, sig);
 192                         eq_cell->setPort(ID::B, comp);
 193                         eq_cell->setPort(ID::Y, RTLIL::SigSpec(cmp_wire, cmp_wire->width++));
 194                 }
 195         }
 196
 197         RTLIL::Wire *ctrl_wire;
 198         if (cmp_wire->width == 1)
 199         {
 200                 ctrl_wire = cmp_wire;
 201         }
 202         else
 203         {
 204                 ctrl_wire = mod->addWire(sstr.str() + "_CTRL");
 205
 206                 // reduce cmp vector to one logic signal
 207                 RTLIL::Cell *any_cell = mod->addCell(sstr.str() + "_ANY", ID($reduce_or));
 208                 apply_attrs(any_cell, sw, cs);
 209
 210                 any_cell->parameters[ID::A_SIGNED] = RTLIL::Const(0);
 211                 any_cell->parameters[ID::A_WIDTH] = RTLIL::Const(cmp_wire->width);
 212                 any_cell->parameters[ID::Y_WIDTH] = RTLIL::Const(1);
 213
 214                 any_cell->setPort(ID::A, cmp_wire);
 215                 any_cell->setPort(ID::Y, RTLIL::SigSpec(ctrl_wire));
 216         }
 217
 218         return RTLIL::SigSpec(ctrl_wire);
 219 }
 220
 221 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, RTLIL::CaseRule *cs, bool ifxmode)
 222 {
 223         log_assert(when_signal.size() == else_signal.size());
 224
 225         std::stringstream sstr;
 226         sstr << "$procmux$" << (autoidx++);
 227
 228         // the trivial cases
 229         if (compare.size() == 0 || when_signal == else_signal)
 230                 return when_signal;
 231
 232         // compare results
 233         RTLIL::SigSpec ctrl_sig = gen_cmp(mod, signal, compare, sw, cs, ifxmode);
 234         if (ctrl_sig.size() == 0)
 235                 return when_signal;
 236         log_assert(ctrl_sig.size() == 1);
 237
 238         // prepare multiplexer output signal
 239         RTLIL::Wire *result_wire = mod->addWire(sstr.str() + "_Y", when_signal.size());
 240
 241         // create the multiplexer itself
 242         RTLIL::Cell *mux_cell = mod->addCell(sstr.str(), ID($mux));
 243         apply_attrs(mux_cell, sw, cs);
 244
 245         mux_cell->parameters[ID::WIDTH] = RTLIL::Const(when_signal.size());
 246         mux_cell->setPort(ID::A, else_signal);
 247         mux_cell->setPort(ID::B, when_signal);
 248         mux_cell->setPort(ID::S, ctrl_sig);
 249         mux_cell->setPort(ID::Y, RTLIL::SigSpec(result_wire));
 250
 251         last_mux_cell = mux_cell;
 252         return RTLIL::SigSpec(result_wire);
 253 }
 254
 255 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, RTLIL::CaseRule *cs, bool ifxmode)
 256 {
 257         log_assert(last_mux_cell != NULL);
 258         log_assert(when_signal.size() == last_mux_cell->getPort(ID::A).size());
 259
 260         if (when_signal == last_mux_cell->getPort(ID::A))
 261                 return;
 262
 263         RTLIL::SigSpec ctrl_sig = gen_cmp(mod, signal, compare, sw, cs, ifxmode);
 264         log_assert(ctrl_sig.size() == 1);
 265         last_mux_cell->type = ID($pmux);
 266
 267         RTLIL::SigSpec new_s = last_mux_cell->getPort(ID::S);
 268         new_s.append(ctrl_sig);
 269         last_mux_cell->setPort(ID::S, new_s);
 270
 271         RTLIL::SigSpec new_b = last_mux_cell->getPort(ID::B);
 272         new_b.append(when_signal);
 273         last_mux_cell->setPort(ID::B, new_b);
 274
 275         last_mux_cell->parameters[ID::S_WIDTH] = last_mux_cell->getPort(ID::S).size();
 276 }
 277
 278 const pool<SigBit> &get_full_case_bits(SnippetSwCache &swcache, RTLIL::SwitchRule *sw)
 279 {
 280         if (!swcache.full_case_bits_cache.count(sw))
 281         {
 282                 pool<SigBit> bits;
 283
 284                 if (sw->get_bool_attribute(ID::full_case))
 285                 {
 286                         bool first_case = true;
 287
 288                         for (auto cs : sw->cases)
 289                         {
 290                                 pool<SigBit> case_bits;
 291
 292                                 for (auto it : cs->actions) {
 293                                         for (auto bit : it.first)
 294                                                 case_bits.insert(bit);
 295                                 }
 296
 297                                 for (auto it : cs->switches) {
 298                                         for (auto bit : get_full_case_bits(swcache, it))
 299                                                 case_bits.insert(bit);
 300                                 }
 301
 302                                 if (first_case) {
 303                                         first_case = false;
 304                                         bits = case_bits;
 305                                 } else {
 306                                         pool<SigBit> new_bits;
 307                                         for (auto bit : bits)
 308                                                 if (case_bits.count(bit))
 309                                                         new_bits.insert(bit);
 310                                         bits.swap(new_bits);
 311                                 }
 312                         }
 313                 }
 314
 315                 bits.swap(swcache.full_case_bits_cache[sw]);
 316         }
 317
 318         return swcache.full_case_bits_cache.at(sw);
 319 }
 320
 321 RTLIL::SigSpec signal_to_mux_tree(RTLIL::Module *mod, SnippetSwCache &swcache, dict<RTLIL::SwitchRule*, bool, hash_ptr_ops> &swpara,
 322                 RTLIL::CaseRule *cs, const RTLIL::SigSpec &sig, const RTLIL::SigSpec &defval, bool ifxmode)
 323 {
 324         RTLIL::SigSpec result = defval;
 325
 326         for (auto &action : cs->actions) {
 327                 sig.replace(action.first, action.second, &result);
 328                 action.first.remove2(sig, &action.second);
 329         }
 330
 331         for (auto sw : cs->switches)
 332         {
 333                 if (!swcache.check(sw))
 334                         continue;
 335
 336                 // detect groups of parallel cases
 337                 std::vector<int> pgroups(sw->cases.size());
 338                 bool is_simple_parallel_case = true;
 339
 340                 if (!sw->get_bool_attribute(ID::parallel_case)) {
 341                         if (!swpara.count(sw)) {
 342                                 pool<Const> case_values;
 343                                 for (size_t i = 0; i < sw->cases.size(); i++) {
 344                                         RTLIL::CaseRule *cs2 = sw->cases[i];
 345                                         for (auto pat : cs2->compare) {
 346                                                 if (!pat.is_fully_def())
 347                                                         goto not_simple_parallel_case;
 348                                                 Const cpat = pat.as_const();
 349                                                 if (case_values.count(cpat))
 350                                                         goto not_simple_parallel_case;
 351                                                 case_values.insert(cpat);
 352                                         }
 353                                 }
 354                                 if (0)
 355                         not_simple_parallel_case:
 356                                         is_simple_parallel_case = false;
 357                                 swpara[sw] = is_simple_parallel_case;
 358                         } else {
 359                                 is_simple_parallel_case = swpara.at(sw);
 360                         }
 361                 }
 362
 363                 if (!is_simple_parallel_case) {
 364                         BitPatternPool pool(sw->signal.size());
 365                         bool extra_group_for_next_case = false;
 366                         for (size_t i = 0; i < sw->cases.size(); i++) {
 367                                 RTLIL::CaseRule *cs2 = sw->cases[i];
 368                                 if (i != 0) {
 369                                         pgroups[i] = pgroups[i-1];
 370                                         if (extra_group_for_next_case) {
 371                                                 pgroups[i] = pgroups[i-1]+1;
 372                                                 extra_group_for_next_case = false;
 373                                         }
 374                                         for (auto pat : cs2->compare)
 375                                                 if (!pat.is_fully_const() || !pool.has_all(pat))
 376                                                         pgroups[i] = pgroups[i-1]+1;
 377                                         if (cs2->compare.empty())
 378                                                 pgroups[i] = pgroups[i-1]+1;
 379                                         if (pgroups[i] != pgroups[i-1])
 380                                                 pool = BitPatternPool(sw->signal.size());
 381                                 }
 382                                 for (auto pat : cs2->compare)
 383                                         if (!pat.is_fully_const())
 384                                                 extra_group_for_next_case = true;
 385                                         else if (!ifxmode)
 386                                                 pool.take(pat);
 387                         }
 388                 }
 389
 390                 // mask default bits that are irrelevant because the output is driven by a full case
 391                 const pool<SigBit> &full_case_bits = get_full_case_bits(swcache, sw);
 392                 for (int i = 0; i < GetSize(sig); i++)
 393                         if (full_case_bits.count(sig[i]))
 394                                 result[i] = State::Sx;
 395
 396                 // evaluate in reverse order to give the first entry the top priority
 397                 RTLIL::SigSpec initial_val = result;
 398                 RTLIL::Cell *last_mux_cell = NULL;
 399                 for (size_t i = 0; i < sw->cases.size(); i++) {
 400                         int case_idx = sw->cases.size() - i - 1;
 401                         RTLIL::CaseRule *cs2 = sw->cases[case_idx];
 402                         RTLIL::SigSpec value = signal_to_mux_tree(mod, swcache, swpara, cs2, sig, initial_val, ifxmode);
 403                         if (last_mux_cell && pgroups[case_idx] == pgroups[case_idx+1])
 404                                 append_pmux(mod, sw->signal, cs2->compare, value, last_mux_cell, sw, cs2, ifxmode);
 405                         else
 406                                 result = gen_mux(mod, sw->signal, cs2->compare, value, result, last_mux_cell, sw, cs2, ifxmode);
 407                 }
 408         }
 409
 410         return result;
 411 }
 412
 413 void proc_mux(RTLIL::Module *mod, RTLIL::Process *proc, bool ifxmode)
 414 {
 415         log("Creating decoders for process `%s.%s'.\n", mod->name.c_str(), proc->name.c_str());
 416
 417         SigSnippets sigsnip;
 418         sigsnip.insert(&proc->root_case);
 419
 420         SnippetSwCache swcache;
 421         swcache.snippets = &sigsnip;
 422         swcache.insert(&proc->root_case);
 423
 424         dict<RTLIL::SwitchRule*, bool, hash_ptr_ops> swpara;
 425
 426         int cnt = 0;
 427         for (int idx : sigsnip.snippets)
 428         {
 429                 swcache.current_snippet = idx;
 430                 RTLIL::SigSpec sig = sigsnip.sigidx[idx];
 431
 432                 log("%6d/%d: %s\n", ++cnt, GetSize(sigsnip.snippets), log_signal(sig));
 433
 434                 RTLIL::SigSpec value = signal_to_mux_tree(mod, swcache, swpara, &proc->root_case, sig, RTLIL::SigSpec(RTLIL::State::Sx, sig.size()), ifxmode);
 435                 mod->connect(RTLIL::SigSig(sig, value));
 436         }
 437 }
 438
 439 struct ProcMuxPass : public Pass {
 440         ProcMuxPass() : Pass("proc_mux", "convert decision trees to multiplexers") { }
 441         void help() override
 442         {
 443                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 444                 log("\n");
 445                 log("    proc_mux [options] [selection]\n");
 446                 log("\n");
 447                 log("This pass converts the decision trees in processes (originating from if-else\n");
 448                 log("and case statements) to trees of multiplexer cells.\n");
 449                 log("\n");
 450                 log("    -ifx\n");
 451                 log("        Use Verilog simulation behavior with respect to undef values in\n");
 452                 log("        'case' expressions and 'if' conditions.\n");
 453                 log("\n");
 454         }
 455         void execute(std::vector<std::string> args, RTLIL::Design *design) override
 456         {
 457                 bool ifxmode = false;
 458                 log_header(design, "Executing PROC_MUX pass (convert decision trees to multiplexers).\n");
 459
 460                 size_t argidx;
 461                 for (argidx = 1; argidx < args.size(); argidx++)
 462                 {
 463                         if (args[argidx] == "-ifx") {
 464                                 ifxmode = true;
 465                                 continue;
 466                         }
 467                         break;
 468                 }
 469                 extra_args(args, argidx, design);
 470
 471                 for (auto mod : design->modules())
 472                         if (design->selected(mod))
 473                                 for (auto &proc_it : mod->processes)
 474                                         if (design->selected(mod, proc_it.second))
 475                                                 proc_mux(mod, proc_it.second, ifxmode);
 476         }
 477 } ProcMuxPass;
 478
 479 PRIVATE_NAMESPACE_END