passes/techmap/extract_fa.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/sigtools.h"
  22 #include "kernel/consteval.h"
  23
  24 USING_YOSYS_NAMESPACE
  25 PRIVATE_NAMESPACE_BEGIN
  26
  27 struct ExtractFaConfig
  28 {
  29         bool enable_fa = false;
  30         bool enable_ha = false;
  31 };
  32
  33 // http://svn.clifford.at/handicraft/2016/bindec/bindec.c
  34 int bindec(unsigned char v)
  35 {
  36         int r = v & 1;
  37         r += (~((v & 2) - 1)) & 10;
  38         r += (~((v & 4) - 1)) & 100;
  39         r += (~((v & 8) - 1)) & 1000;
  40         r += (~((v & 16) - 1)) & 10000;
  41         r += (~((v & 32) - 1)) & 100000;
  42         r += (~((v & 64) - 1)) & 1000000;
  43         r += (~((v & 128) - 1)) & 10000000;
  44         return r;
  45 }
  46
  47 struct ExtractFaWorker
  48 {
  49         const ExtractFaConfig &config;
  50         Module *module;
  51         ConstEval ce;
  52         SigMap &sigmap;
  53
  54         dict<SigBit, Cell*> driver;
  55         pool<SigBit> handled_bits;
  56
  57         pool<tuple<SigBit, SigBit>> xorxnor2;
  58         pool<tuple<SigBit, SigBit, SigBit>> xorxnor3;
  59
  60         dict<tuple<SigBit, SigBit>, dict<int, pool<SigBit>>> func2;
  61         dict<tuple<SigBit, SigBit, SigBit>, dict<int, pool<SigBit>>> func3;
  62
  63         ExtractFaWorker(const ExtractFaConfig &config, Module *module) :
  64                         config(config), module(module), ce(module), sigmap(ce.assign_map)
  65         {
  66                 for (auto cell : module->selected_cells())
  67                 {
  68                         if (cell->type.in( "$_BUF_", "$_NOT_", "$_AND_", "$_NAND_", "$_OR_", "$_NOR_",
  69                                         "$_XOR_", "$_XNOR_", "$_ANDNOT_", "$_ORNOT_", "$_MUX_",
  70                                         "$_AOI3_", "$_OAI3_", "$_AOI4_", "$_OAI4_"))
  71                         {
  72                                 SigBit y = sigmap(SigBit(cell->getPort("\\Y")));
  73                                 log_assert(driver.count(y) == 0);
  74                                 driver[y] = cell;
  75                         }
  76                 }
  77         }
  78
  79         void check_partition(SigBit root, pool<SigBit> &leaves)
  80         {
  81                 if (GetSize(leaves) == 2)
  82                 {
  83                         leaves.sort();
  84
  85                         SigBit A = SigSpec(leaves)[0];
  86                         SigBit B = SigSpec(leaves)[1];
  87
  88                         int func = 0;
  89                         for (int i = 0; i < 4; i++)
  90                         {
  91                                 bool a_value = (i & 1) != 0;
  92                                 bool b_value = (i & 2) != 0;
  93
  94                                 ce.push();
  95                                 ce.set(A, a_value ? State::S1 : State::S0);
  96                                 ce.set(B, b_value ? State::S1 : State::S0);
  97
  98                                 SigSpec sig = root;
  99
 100                                 if (!ce.eval(sig))
 101                                         log_abort();
 102
 103                                 if (sig == State::S1)
 104                                         func |= 1 << i;
 105
 106                                 ce.pop();
 107                         }
 108
 109                         // log("%04d %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(root));
 110
 111                         if (func == 0x6 || func == 0x9)
 112                                 xorxnor2.insert(tuple<SigBit, SigBit>(A, B));
 113
 114                         func2[tuple<SigBit, SigBit>(A, B)][func].insert(root);
 115                 }
 116
 117                 if (GetSize(leaves) == 3)
 118                 {
 119                         leaves.sort();
 120
 121                         SigBit A = SigSpec(leaves)[0];
 122                         SigBit B = SigSpec(leaves)[1];
 123                         SigBit C = SigSpec(leaves)[2];
 124
 125                         int func = 0;
 126                         for (int i = 0; i < 8; i++)
 127                         {
 128                                 bool a_value = (i & 1) != 0;
 129                                 bool b_value = (i & 2) != 0;
 130                                 bool c_value = (i & 4) != 0;
 131
 132                                 ce.push();
 133                                 ce.set(A, a_value ? State::S1 : State::S0);
 134                                 ce.set(B, b_value ? State::S1 : State::S0);
 135                                 ce.set(C, c_value ? State::S1 : State::S0);
 136
 137                                 SigSpec sig = root;
 138
 139                                 if (!ce.eval(sig))
 140                                         log_abort();
 141
 142                                 if (sig == State::S1)
 143                                         func |= 1 << i;
 144
 145                                 ce.pop();
 146                         }
 147
 148                         // log("%08d %s %s %s -> %s\n", bindec(func), log_signal(A), log_signal(B), log_signal(C), log_signal(root));
 149
 150                         if (func == 0x69 || func == 0x96)
 151                                 xorxnor3.insert(tuple<SigBit, SigBit, SigBit>(A, B, C));
 152
 153                         func3[tuple<SigBit, SigBit, SigBit>(A, B, C)][func].insert(root);
 154                 }
 155         }
 156
 157         void find_partitions(SigBit root, pool<SigBit> &leaves, pool<pool<SigBit>> &cache, int maxdepth, int maxbreadth)
 158         {
 159                 if (cache.count(leaves))
 160                         return;
 161
 162                 cache.insert(leaves);
 163                 check_partition(root, leaves);
 164
 165                 if (maxdepth == 0)
 166                         return;
 167
 168                 for (SigBit bit : leaves)
 169                 {
 170                         if (driver.count(bit) == 0)
 171                                 continue;
 172
 173                         Cell *cell = driver.at(bit);
 174                         pool<SigBit> new_leaves = leaves;
 175
 176                         new_leaves.erase(bit);
 177                         if (cell->hasPort("\\A")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\A"))));
 178                         if (cell->hasPort("\\B")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\B"))));
 179                         if (cell->hasPort("\\C")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\C"))));
 180                         if (cell->hasPort("\\D")) new_leaves.insert(sigmap(SigBit(cell->getPort("\\D"))));
 181
 182                         if (GetSize(new_leaves) > maxbreadth)
 183                                 continue;
 184
 185                         find_partitions(root, new_leaves, cache, maxdepth-1, maxbreadth);
 186                 }
 187         }
 188
 189         void run()
 190         {
 191                 for (auto it : driver)
 192                 {
 193                         SigBit root = it.first;
 194                         pool<SigBit> leaves = { root };
 195                         pool<pool<SigBit>> cache;
 196
 197                         find_partitions(root, leaves, cache, 5, 10);
 198                 }
 199
 200                 for (auto &key : xorxnor3)
 201                 {
 202                         SigBit A = get<0>(key);
 203                         SigBit B = get<1>(key);
 204                         SigBit C = get<2>(key);
 205
 206                         log("3-Input XOR/XNOR %s %s %s:\n", log_signal(A), log_signal(B), log_signal(C));
 207
 208                         for (auto &it : func3.at(key)) {
 209                                 log("    %08d ->", bindec(it.first));
 210                                 for (auto bit : it.second)
 211                                         log(" %s", log_signal(bit));
 212                                 log("\n");
 213                         }
 214                 }
 215
 216                 for (auto &key : xorxnor2)
 217                 {
 218                         SigBit A = get<0>(key);
 219                         SigBit B = get<1>(key);
 220
 221                         log("2-Input XOR/XNOR %s %s:\n", log_signal(A), log_signal(B));
 222
 223                         for (auto &it : func2.at(key)) {
 224                                 log("    %04d ->", bindec(it.first));
 225                                 for (auto bit : it.second)
 226                                         log(" %s", log_signal(bit));
 227                                 log("\n");
 228                         }
 229                 }
 230         }
 231 };
 232
 233 struct ExtractFaPass : public Pass {
 234         ExtractFaPass() : Pass("extract_fa", "find and extract full/half adders") { }
 235         virtual void help()
 236         {
 237                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 238                 log("\n");
 239                 log("    extract_fa [options] [selection]\n");
 240                 log("\n");
 241                 log("This pass extracts full/half adders from a gate-level design.\n");
 242                 log("\n");
 243                 log("    -fa, -ha\n");
 244                 log("        Enable cell types (fa=full adder, ha=half adder)\n");
 245                 log("        All types are enabled if none of this options is used\n");
 246                 log("\n");
 247         }
 248         virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
 249         {
 250                 ExtractFaConfig config;
 251
 252                 log_header(design, "Executing EXTRACT_FA pass (find and extract full/half adders).\n");
 253                 log_push();
 254
 255                 size_t argidx;
 256                 for (argidx = 1; argidx < args.size(); argidx++)
 257                 {
 258                         if (args[argidx] == "-fa") {
 259                                 config.enable_fa = true;
 260                                 continue;
 261                         }
 262                         if (args[argidx] == "-ha") {
 263                                 config.enable_ha = true;
 264                                 continue;
 265                         }
 266                         break;
 267                 }
 268                 extra_args(args, argidx, design);
 269
 270                 if (!config.enable_fa && !config.enable_ha) {
 271                         config.enable_fa = true;
 272                         config.enable_ha = true;
 273                 }
 274
 275                 for (auto module : design->selected_modules())
 276                 {
 277                         ExtractFaWorker worker(config, module);
 278                         worker.run();
 279                 }
 280
 281                 log_pop();
 282         }
 283 } ExtractFaPass;
 284
 285 PRIVATE_NAMESPACE_END