passes/cmds/ltp.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/yosys.h"
  21 #include "kernel/celltypes.h"
  22 #include "kernel/sigtools.h"
  23
  24 USING_YOSYS_NAMESPACE
  25 PRIVATE_NAMESPACE_BEGIN
  26
  27 struct LtpWorker
  28 {
  29         RTLIL::Design *design;
  30         RTLIL::Module *module;
  31         SigMap sigmap;
  32
  33         dict<SigBit, tuple<int, SigBit, Cell*>> bits;
  34         dict<SigBit, dict<SigBit, Cell*>> bit2bits;
  35         dict<SigBit, tuple<SigBit, Cell*>> bit2ff;
  36
  37         int maxlvl;
  38         SigBit maxbit;
  39         pool<SigBit> busy;
  40
  41         LtpWorker(RTLIL::Module *module, bool noff) : design(module->design), module(module), sigmap(module)
  42         {
  43                 CellTypes ff_celltypes;
  44
  45                 if (noff) {
  46                         ff_celltypes.setup_internals_mem();
  47                         ff_celltypes.setup_stdcells_mem();
  48                 }
  49
  50                 for (auto wire : module->selected_wires())
  51                         for (auto bit : sigmap(wire))
  52                                 bits[bit] = tuple<int, SigBit, Cell*>(-1, State::Sx, nullptr);
  53
  54                 for (auto cell : module->selected_cells())
  55                 {
  56                         pool<SigBit> src_bits, dst_bits;
  57
  58                         for (auto &conn : cell->connections())
  59                                 for (auto bit : sigmap(conn.second)) {
  60                                         if (cell->input(conn.first))
  61                                                 src_bits.insert(bit);
  62                                         if (cell->output(conn.first))
  63                                                 dst_bits.insert(bit);
  64                                 }
  65
  66                         if (noff && ff_celltypes.cell_known(cell->type)) {
  67                                 for (auto s : src_bits)
  68                                         for (auto d : dst_bits) {
  69                                                 bit2ff[s] = tuple<SigBit, Cell*>(d, cell);
  70                                                 break;
  71                                         }
  72                                 continue;
  73                         }
  74
  75                         for (auto s : src_bits)
  76                                 for (auto d : dst_bits)
  77                                         bit2bits[s][d] = cell;
  78                 }
  79
  80                 maxlvl = -1;
  81                 maxbit = State::Sx;
  82         }
  83
  84         void runner(SigBit bit, int level, SigBit from, Cell *via)
  85         {
  86                 auto &bitinfo = bits.at(bit);
  87
  88                 if (get<0>(bitinfo) >= level)
  89                         return;
  90
  91                 if (busy.count(bit) > 0) {
  92                         log_warning("Detected loop at %s in %s\n", log_signal(bit), log_id(module));
  93                         return;
  94                 }
  95
  96                 busy.insert(bit);
  97                 get<0>(bitinfo) = level;
  98                 get<1>(bitinfo) = from;
  99                 get<2>(bitinfo) = via;
 100
 101                 if (level > maxlvl) {
 102                         maxlvl = level;
 103                         maxbit = bit;
 104                 }
 105
 106                 if (bit2bits.count(bit)) {
 107                         for (auto &it : bit2bits.at(bit))
 108                                 runner(it.first, level+1, bit, it.second);
 109                 }
 110
 111                 busy.erase(bit);
 112         }
 113
 114         void printpath(SigBit bit)
 115         {
 116                 auto &bitinfo = bits.at(bit);
 117                 if (get<2>(bitinfo)) {
 118                         printpath(get<1>(bitinfo));
 119                         log("%5d: %s (via %s)\n", get<0>(bitinfo), log_signal(bit), log_id(get<2>(bitinfo)));
 120                 } else {
 121                         log("%5d: %s\n", get<0>(bitinfo), log_signal(bit));
 122                 }
 123         }
 124
 125         void run()
 126         {
 127                 for (auto &it : bits)
 128                         if (get<0>(it.second) < 0)
 129                                 runner(it.first, 0, State::Sx, nullptr);
 130
 131                 log("\n");
 132                 log("Longest topological path in %s (length=%d):\n", log_id(module), maxlvl);
 133
 134                 if (maxlvl >= 0)
 135                         printpath(maxbit);
 136
 137                 if (bit2ff.count(maxbit))
 138                         log("%5s: %s (via %s)\n", "ff", log_signal(get<0>(bit2ff.at(maxbit))), log_id(get<1>(bit2ff.at(maxbit))));
 139         }
 140 };
 141
 142 struct LtpPass : public Pass {
 143         LtpPass() : Pass("ltp", "print longest topological path") { }
 144         void help() YS_OVERRIDE
 145         {
 146                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 147                 log("\n");
 148                 log("    ltp [options] [selection]\n");
 149                 log("\n");
 150                 log("This command prints the longest topological path in the design. (Only considers\n");
 151                 log("paths within a single module, so the design must be flattened.)\n");
 152                 log("\n");
 153                 log("    -noff\n");
 154                 log("        automatically exclude FF cell types\n");
 155                 log("\n");
 156         }
 157         void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
 158         {
 159                 bool noff = false;
 160
 161                 log_header(design, "Executing LTP pass (find longest path).\n");
 162
 163                 size_t argidx;
 164                 for (argidx = 1; argidx < args.size(); argidx++) {
 165                         if (args[argidx] == "-noff") {
 166                                 noff = true;
 167                                 continue;
 168                         }
 169                         break;
 170                 }
 171
 172                 extra_args(args, argidx, design);
 173
 174                 for (Module *module : design->selected_modules())
 175                 {
 176                         if (module->has_processes_warn())
 177                                 continue;
 178
 179                         LtpWorker worker(module, noff);
 180                         worker.run();
 181                 }
 182         }
 183 } LtpPass;
 184
 185 PRIVATE_NAMESPACE_END