passes/proc/proc_dlatch.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/sigtools.h"
  22 #include "kernel/consteval.h"
  23 #include "kernel/log.h"
  24 #include <sstream>
  25 #include <stdlib.h>
  26 #include <stdio.h>
  27
  28 USING_YOSYS_NAMESPACE
  29 PRIVATE_NAMESPACE_BEGIN
  30
  31 struct proc_dlatch_db_t
  32 {
  33         Module *module;
  34         SigMap sigmap;
  35
  36         pool<Cell*> generated_dlatches;
  37         dict<Cell*, vector<SigBit>> mux_srcbits;
  38         dict<SigBit, pair<Cell*, int>> mux_drivers;
  39         dict<SigBit, int> sigusers;
  40
  41         proc_dlatch_db_t(Module *module) : module(module), sigmap(module)
  42         {
  43                 for (auto cell : module->cells())
  44                 {
  45                         if (cell->type.in(ID($mux), ID($pmux)))
  46                         {
  47                                 auto sig_y = sigmap(cell->getPort(ID::Y));
  48                                 for (int i = 0; i < GetSize(sig_y); i++)
  49                                         mux_drivers[sig_y[i]] = pair<Cell*, int>(cell, i);
  50
  51                                 pool<SigBit> mux_srcbits_pool;
  52                                 for (auto bit : sigmap(cell->getPort(ID::A)))
  53                                         mux_srcbits_pool.insert(bit);
  54                                 for (auto bit : sigmap(cell->getPort(ID::B)))
  55                                         mux_srcbits_pool.insert(bit);
  56
  57                                 vector<SigBit> mux_srcbits_vec;
  58                                 for (auto bit : mux_srcbits_pool)
  59                                         if (bit.wire != nullptr)
  60                                                 mux_srcbits_vec.push_back(bit);
  61
  62                                 mux_srcbits[cell].swap(mux_srcbits_vec);
  63                         }
  64
  65                         for (auto &conn : cell->connections())
  66                                 if (!cell->known() || cell->input(conn.first))
  67                                         for (auto bit : sigmap(conn.second))
  68                                                 sigusers[bit]++;
  69                 }
  70
  71                 for (auto wire : module->wires())
  72                         if (wire->port_input)
  73                                 for (auto bit : sigmap(wire))
  74                                         sigusers[bit]++;
  75         }
  76
  77         bool quickcheck(const SigSpec &haystack, const SigSpec &needle)
  78         {
  79                 pool<SigBit> haystack_bits = sigmap(haystack).to_sigbit_pool();
  80                 pool<SigBit> needle_bits = sigmap(needle).to_sigbit_pool();
  81
  82                 pool<Cell*> cells_queue, cells_visited;
  83                 pool<SigBit> bits_queue, bits_visited;
  84
  85                 bits_queue = haystack_bits;
  86                 while (!bits_queue.empty())
  87                 {
  88                         for (auto &bit : bits_queue) {
  89                                 auto it = mux_drivers.find(bit);
  90                                 if (it != mux_drivers.end())
  91                                         if (!cells_visited.count(it->second.first))
  92                                                 cells_queue.insert(it->second.first);
  93                                 bits_visited.insert(bit);
  94                         }
  95
  96                         bits_queue.clear();
  97
  98                         for (auto c : cells_queue) {
  99                                 for (auto bit : mux_srcbits[c]) {
 100                                         if (needle_bits.count(bit))
 101                                                 return true;
 102                                         if (!bits_visited.count(bit))
 103                                                 bits_queue.insert(bit);
 104                                 }
 105                         }
 106
 107                         cells_queue.clear();
 108                 }
 109
 110                 return false;
 111         }
 112
 113         struct rule_node_t
 114         {
 115                 // a node is true if "signal" equals "match" and [any
 116                 // of the child nodes is true or "children" is empty]
 117                 SigBit signal, match;
 118                 vector<int> children;
 119
 120                 bool operator==(const rule_node_t &other) const {
 121                         return signal == other.signal && match == other.match && children == other.children;
 122                 }
 123
 124                 unsigned int hash() const {
 125                         unsigned int h = mkhash_init;
 126                         mkhash(h, signal.hash());
 127                         mkhash(h, match.hash());
 128                         for (auto i : children) mkhash(h, i);
 129                         return h;
 130                 }
 131         };
 132
 133         enum tf_node_types_t : int {
 134                 true_node = 1,
 135                 false_node = 2
 136         };
 137
 138         idict<rule_node_t, 3> rules_db;
 139         dict<int, SigBit> rules_sig;
 140
 141         int make_leaf(SigBit signal, SigBit match)
 142         {
 143                 rule_node_t node;
 144                 node.signal = signal;
 145                 node.match = match;
 146                 return rules_db(node);
 147         }
 148
 149         int make_inner(SigBit signal, SigBit match, int child)
 150         {
 151                 rule_node_t node;
 152                 node.signal = signal;
 153                 node.match = match;
 154                 node.children.push_back(child);
 155                 return rules_db(node);
 156         }
 157
 158         int make_inner(const pool<int> &children)
 159         {
 160                 rule_node_t node;
 161                 node.signal = State::S0;
 162                 node.match = State::S0;
 163                 node.children = vector<int>(children.begin(), children.end());
 164                 std::sort(node.children.begin(), node.children.end());
 165                 return rules_db(node);
 166         }
 167
 168         int find_mux_feedback(SigBit haystack, SigBit needle, bool set_undef)
 169         {
 170                 if (sigusers[haystack] > 1)
 171                         set_undef = false;
 172
 173                 if (haystack == needle)
 174                         return true_node;
 175
 176                 auto it = mux_drivers.find(haystack);
 177                 if (it == mux_drivers.end())
 178                         return false_node;
 179
 180                 Cell *cell = it->second.first;
 181                 int index = it->second.second;
 182
 183                 SigSpec sig_a = sigmap(cell->getPort(ID::A));
 184                 SigSpec sig_b = sigmap(cell->getPort(ID::B));
 185                 SigSpec sig_s = sigmap(cell->getPort(ID::S));
 186                 int width = GetSize(sig_a);
 187
 188                 pool<int> children;
 189
 190                 int n = find_mux_feedback(sig_a[index], needle, set_undef);
 191                 if (n != false_node) {
 192                         if (set_undef && sig_a[index] == needle) {
 193                                 SigSpec sig = cell->getPort(ID::A);
 194                                 sig[index] = State::Sx;
 195                                 cell->setPort(ID::A, sig);
 196                         }
 197                         for (int i = 0; i < GetSize(sig_s); i++)
 198                                 n = make_inner(sig_s[i], State::S0, n);
 199                         children.insert(n);
 200                 }
 201
 202                 for (int i = 0; i < GetSize(sig_s); i++) {
 203                         n = find_mux_feedback(sig_b[i*width + index], needle, set_undef);
 204                         if (n != false_node) {
 205                                 if (set_undef && sig_b[i*width + index] == needle) {
 206                                         SigSpec sig = cell->getPort(ID::B);
 207                                         sig[i*width + index] = State::Sx;
 208                                         cell->setPort(ID::B, sig);
 209                                 }
 210                                 children.insert(make_inner(sig_s[i], State::S1, n));
 211                         }
 212                 }
 213
 214                 if (children.empty())
 215                         return false_node;
 216
 217                 return make_inner(children);
 218         }
 219
 220         SigBit make_hold(int n, string &src)
 221         {
 222                 if (n == true_node)
 223                         return State::S1;
 224
 225                 if (n == false_node)
 226                         return State::S0;
 227
 228                 if (rules_sig.count(n))
 229                         return rules_sig.at(n);
 230
 231                 const rule_node_t &rule = rules_db[n];
 232                 SigSpec and_bits;
 233
 234                 if (rule.signal != rule.match) {
 235                         if (rule.match == State::S1)
 236                                 and_bits.append(rule.signal);
 237                         else if (rule.match == State::S0)
 238                                 and_bits.append(module->Not(NEW_ID, rule.signal, false, src));
 239                         else
 240                                 and_bits.append(module->Eq(NEW_ID, rule.signal, rule.match, false, src));
 241                 }
 242
 243                 if (!rule.children.empty()) {
 244                         SigSpec or_bits;
 245                         for (int k : rule.children)
 246                                 or_bits.append(make_hold(k, src));
 247                         and_bits.append(module->ReduceOr(NEW_ID, or_bits, false, src));
 248                 }
 249
 250                 if (GetSize(and_bits) == 2)
 251                         and_bits = module->And(NEW_ID, and_bits[0], and_bits[1], false, src);
 252                 log_assert(GetSize(and_bits) == 1);
 253
 254                 rules_sig[n] = and_bits[0];
 255                 return and_bits[0];
 256         }
 257
 258         void fixup_mux(Cell *cell)
 259         {
 260                 SigSpec sig_a = cell->getPort(ID::A);
 261                 SigSpec sig_b = cell->getPort(ID::B);
 262                 SigSpec sig_s = cell->getPort(ID::S);
 263                 SigSpec sig_any_valid_b;
 264
 265                 SigSpec sig_new_b, sig_new_s;
 266                 for (int i = 0; i < GetSize(sig_s); i++) {
 267                         SigSpec b = sig_b.extract(i*GetSize(sig_a), GetSize(sig_a));
 268                         if (!b.is_fully_undef()) {
 269                                 sig_any_valid_b = b;
 270                                 sig_new_b.append(b);
 271                                 sig_new_s.append(sig_s[i]);
 272                         }
 273                 }
 274
 275                 if (sig_new_s.empty()) {
 276                         sig_new_b = sig_a;
 277                         sig_new_s = State::S0;
 278                 }
 279
 280                 if (sig_a.is_fully_undef() && !sig_any_valid_b.empty())
 281                         cell->setPort(ID::A, sig_any_valid_b);
 282
 283                 if (GetSize(sig_new_s) == 1) {
 284                         cell->type = ID($mux);
 285                         cell->unsetParam(ID::S_WIDTH);
 286                 } else {
 287                         cell->type = ID($pmux);
 288                         cell->setParam(ID::S_WIDTH, GetSize(sig_new_s));
 289                 }
 290
 291                 cell->setPort(ID::B, sig_new_b);
 292                 cell->setPort(ID::S, sig_new_s);
 293         }
 294
 295         void fixup_muxes()
 296         {
 297                 pool<Cell*> visited, queue;
 298                 dict<Cell*, pool<SigBit>> upstream_cell2net;
 299                 dict<SigBit, pool<Cell*>> upstream_net2cell;
 300
 301                 CellTypes ct;
 302                 ct.setup_internals();
 303
 304                 for (auto cell : module->cells())
 305                 for (auto conn : cell->connections()) {
 306                         if (cell->input(conn.first))
 307                                 for (auto bit : sigmap(conn.second))
 308                                         upstream_cell2net[cell].insert(bit);
 309                         if (cell->output(conn.first))
 310                                 for (auto bit : sigmap(conn.second))
 311                                         upstream_net2cell[bit].insert(cell);
 312                 }
 313
 314                 queue = generated_dlatches;
 315                 while (!queue.empty())
 316                 {
 317                         pool<Cell*> next_queue;
 318
 319                         for (auto cell : queue) {
 320                                 if (cell->type.in(ID($mux), ID($pmux)))
 321                                         fixup_mux(cell);
 322                                 for (auto bit : upstream_cell2net[cell])
 323                                         for (auto cell : upstream_net2cell[bit])
 324                                                 next_queue.insert(cell);
 325                                 visited.insert(cell);
 326                         }
 327
 328                         queue.clear();
 329                         for (auto cell : next_queue) {
 330                                 if (!visited.count(cell) && ct.cell_known(cell->type))
 331                                         queue.insert(cell);
 332                         }
 333                 }
 334         }
 335 };
 336
 337 void proc_dlatch(proc_dlatch_db_t &db, RTLIL::Process *proc)
 338 {
 339         std::vector<RTLIL::SyncRule*> new_syncs;
 340         RTLIL::SigSig latches_bits, nolatches_bits;
 341         dict<SigBit, SigBit> latches_out_in;
 342         dict<SigBit, int> latches_hold;
 343         std::string src = proc->get_src_attribute();
 344
 345         for (auto sr : proc->syncs)
 346         {
 347                 if (sr->type != RTLIL::SyncType::STa) {
 348                         new_syncs.push_back(sr);
 349                         continue;
 350                 }
 351
 352                 if (proc->get_bool_attribute(ID::always_ff))
 353                         log_error("Found non edge/level sensitive event in always_ff process `%s.%s'.\n",
 354                                         db.module->name.c_str(), proc->name.c_str());
 355
 356                 for (auto ss : sr->actions)
 357                 {
 358                         db.sigmap.apply(ss.first);
 359                         db.sigmap.apply(ss.second);
 360
 361                         if (!db.quickcheck(ss.second, ss.first)) {
 362                                 nolatches_bits.first.append(ss.first);
 363                                 nolatches_bits.second.append(ss.second);
 364                                 continue;
 365                         }
 366
 367                         for (int i = 0; i < GetSize(ss.first); i++)
 368                                 latches_out_in[ss.first[i]] = ss.second[i];
 369                 }
 370
 371                 delete sr;
 372         }
 373
 374         latches_out_in.sort();
 375         for (auto &it : latches_out_in) {
 376                 int n = db.find_mux_feedback(it.second, it.first, true);
 377                 if (n == db.false_node) {
 378                         nolatches_bits.first.append(it.first);
 379                         nolatches_bits.second.append(it.second);
 380                 } else {
 381                         latches_bits.first.append(it.first);
 382                         latches_bits.second.append(it.second);
 383                         latches_hold[it.first] = n;
 384                 }
 385         }
 386
 387         int offset = 0;
 388         for (auto chunk : nolatches_bits.first.chunks()) {
 389                 SigSpec lhs = chunk, rhs = nolatches_bits.second.extract(offset, chunk.width);
 390                 if (proc->get_bool_attribute(ID::always_latch))
 391                         log_error("No latch inferred for signal `%s.%s' from always_latch process `%s.%s'.\n",
 392                                         db.module->name.c_str(), log_signal(lhs), db.module->name.c_str(), proc->name.c_str());
 393                 else
 394                         log("No latch inferred for signal `%s.%s' from process `%s.%s'.\n",
 395                                         db.module->name.c_str(), log_signal(lhs), db.module->name.c_str(), proc->name.c_str());
 396                 db.module->connect(lhs, rhs);
 397                 offset += chunk.width;
 398         }
 399
 400         offset = 0;
 401         while (offset < GetSize(latches_bits.first))
 402         {
 403                 int width = 1;
 404                 int n = latches_hold[latches_bits.first[offset]];
 405                 Wire *w = latches_bits.first[offset].wire;
 406
 407                 if (w != nullptr)
 408                 {
 409                         while (offset+width < GetSize(latches_bits.first) &&
 410                                         n == latches_hold[latches_bits.first[offset+width]] &&
 411                                         w == latches_bits.first[offset+width].wire)
 412                                 width++;
 413
 414                         SigSpec lhs = latches_bits.first.extract(offset, width);
 415                         SigSpec rhs = latches_bits.second.extract(offset, width);
 416
 417                         Cell *cell = db.module->addDlatch(NEW_ID, db.module->Not(NEW_ID, db.make_hold(n, src)), rhs, lhs);
 418                         cell->set_src_attribute(src);
 419                         db.generated_dlatches.insert(cell);
 420
 421                         if (proc->get_bool_attribute(ID::always_comb))
 422                                 log_error("Latch inferred for signal `%s.%s' from always_comb process `%s.%s'.\n",
 423                                                 db.module->name.c_str(), log_signal(lhs), db.module->name.c_str(), proc->name.c_str());
 424                         else
 425                                 log("Latch inferred for signal `%s.%s' from process `%s.%s': %s\n",
 426                                                 db.module->name.c_str(), log_signal(lhs), db.module->name.c_str(), proc->name.c_str(), log_id(cell));
 427                 }
 428
 429                 offset += width;
 430         }
 431
 432         new_syncs.swap(proc->syncs);
 433 }
 434
 435 struct ProcDlatchPass : public Pass {
 436         ProcDlatchPass() : Pass("proc_dlatch", "extract latches from processes") { }
 437         void help() YS_OVERRIDE
 438         {
 439                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 440                 log("\n");
 441                 log("    proc_dlatch [selection]\n");
 442                 log("\n");
 443                 log("This pass identifies latches in the processes and converts them to\n");
 444                 log("d-type latches.\n");
 445                 log("\n");
 446         }
 447         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 448         {
 449                 log_header(design, "Executing PROC_DLATCH pass (convert process syncs to latches).\n");
 450
 451                 extra_args(args, 1, design);
 452
 453                 for (auto module : design->selected_modules()) {
 454                         proc_dlatch_db_t db(module);
 455                         for (auto &proc_it : module->processes)
 456                                 if (design->selected(module, proc_it.second))
 457                                         proc_dlatch(db, proc_it.second);
 458                         db.fixup_muxes();
 459                 }
 460         }
 461 } ProcDlatchPass;
 462
 463 PRIVATE_NAMESPACE_END