passes/tests/test_abcloop.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2014  Clifford Wolf <clifford@clifford.at>
   5  *  Copyright (C) 2014  Johann Glaser <Johann.Glaser@gmx.at>
   6  *
   7  *  Permission to use, copy, modify, and/or distribute this software for any
   8  *  purpose with or without fee is hereby granted, provided that the above
   9  *  copyright notice and this permission notice appear in all copies.
  10  *
  11  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  12  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  13  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  14  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  15  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  16  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  17  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  18  *
  19  */
  20
  21 #include "kernel/yosys.h"
  22 #include "kernel/satgen.h"
  23
  24 static uint32_t xorshift32_state = 123456789;
  25
  26 static uint32_t xorshift32(uint32_t limit) {
  27         xorshift32_state ^= xorshift32_state << 13;
  28         xorshift32_state ^= xorshift32_state >> 17;
  29         xorshift32_state ^= xorshift32_state << 5;
  30         return xorshift32_state % limit;
  31 }
  32
  33 static RTLIL::Wire *getw(std::vector<RTLIL::Wire*> &wires, RTLIL::Wire *w)
  34 {
  35         while (1) {
  36                 int idx = xorshift32(SIZE(wires));
  37                 if (wires[idx] != w && !wires[idx]->port_output)
  38                         return wires[idx];
  39         }
  40 }
  41
  42 static void test_abcloop()
  43 {
  44         log("Rng seed value: %u\n", int(xorshift32_state));
  45
  46         RTLIL::Design *design = new RTLIL::Design;
  47         RTLIL::Module *module = nullptr;
  48         RTLIL::SigSpec in_sig, out_sig;
  49
  50         bool truthtab[16][4];
  51         int create_cycles = 0;
  52
  53         while (1)
  54         {
  55                 module = design->addModule("\\uut");
  56                 create_cycles++;
  57
  58                 in_sig = {};
  59                 out_sig = {};
  60
  61                 std::vector<RTLIL::Wire*> wires;
  62
  63                 for (int i = 0; i < 4; i++) {
  64                         RTLIL::Wire *w = module->addWire(stringf("\\i%d", i));
  65                         w->port_input = true;
  66                         wires.push_back(w);
  67                         in_sig.append(w);
  68                 }
  69
  70                 for (int i = 0; i < 4; i++) {
  71                         RTLIL::Wire *w = module->addWire(stringf("\\o%d", i));
  72                         w->port_output = true;
  73                         wires.push_back(w);
  74                         out_sig.append(w);
  75                 }
  76
  77                 for (int i = 0; i < 16; i++) {
  78                         RTLIL::Wire *w = module->addWire(stringf("\\t%d", i));
  79                         wires.push_back(w);
  80                 }
  81
  82                 for (auto w : wires)
  83                         if (!w->port_input)
  84                                 switch (xorshift32(12))
  85                                 {
  86                                 case 0:
  87                                         module->addNotGate(w->name.str() + "g", getw(wires, w), w);
  88                                         break;
  89                                 case 1:
  90                                         module->addAndGate(w->name.str() + "g", getw(wires, w), getw(wires, w), w);
  91                                         break;
  92                                 case 2:
  93                                         module->addNandGate(w->name.str() + "g", getw(wires, w), getw(wires, w), w);
  94                                         break;
  95                                 case 3:
  96                                         module->addOrGate(w->name.str() + "g", getw(wires, w), getw(wires, w), w);
  97                                         break;
  98                                 case 4:
  99                                         module->addNorGate(w->name.str() + "g", getw(wires, w), getw(wires, w), w);
 100                                         break;
 101                                 case 5:
 102                                         module->addXorGate(w->name.str() + "g", getw(wires, w), getw(wires, w), w);
 103                                         break;
 104                                 case 6:
 105                                         module->addXnorGate(w->name.str() + "g", getw(wires, w), getw(wires, w), w);
 106                                         break;
 107                                 case 7:
 108                                         module->addMuxGate(w->name.str() + "g", getw(wires, w), getw(wires, w), getw(wires, w), w);
 109                                         break;
 110                                 case 8:
 111                                         module->addAoi3Gate(w->name.str() + "g", getw(wires, w), getw(wires, w), getw(wires, w), w);
 112                                         break;
 113                                 case 9:
 114                                         module->addOai3Gate(w->name.str() + "g", getw(wires, w), getw(wires, w), getw(wires, w), w);
 115                                         break;
 116                                 case 10:
 117                                         module->addAoi4Gate(w->name.str() + "g", getw(wires, w), getw(wires, w), getw(wires, w), getw(wires, w), w);
 118                                         break;
 119                                 case 11:
 120                                         module->addOai4Gate(w->name.str() + "g", getw(wires, w), getw(wires, w), getw(wires, w), getw(wires, w), w);
 121                                         break;
 122                                 }
 123
 124                 module->fixup_ports();
 125                 Pass::call(design, "clean");
 126
 127                 ezDefaultSAT ez;
 128                 SigMap sigmap(module);
 129                 SatGen satgen(&ez, &sigmap);
 130
 131                 for (auto c : module->cells()) {
 132                         bool ok = satgen.importCell(c);
 133                         log_assert(ok);
 134                 }
 135
 136                 std::vector<int> in_vec = satgen.importSigSpec(in_sig);
 137                 std::vector<int> inverse_in_vec = ez.vec_not(in_vec);
 138
 139                 std::vector<int> out_vec = satgen.importSigSpec(out_sig);
 140
 141                 for (int i = 0; i < 16; i++)
 142                 {
 143                         std::vector<int> assumptions;
 144                         for (int j = 0; j < SIZE(in_vec); j++)
 145                                 assumptions.push_back((i & (1 << j)) ? in_vec.at(j) : inverse_in_vec.at(j));
 146
 147                         std::vector<bool> results;
 148                         if (!ez.solve(out_vec, results, assumptions)) {
 149                                 log("No stable solution for input %d found -> recreate module.\n", i);
 150                                 goto recreate_module;
 151                         }
 152
 153                         for (int j = 0; j < 4; j++)
 154                                 truthtab[i][j] = results[j];
 155
 156                         assumptions.push_back(ez.vec_ne(out_vec, ez.vec_const(results)));
 157
 158                         std::vector<bool> results2;
 159                         if (ez.solve(out_vec, results2, assumptions)) {
 160                                 log("Two stable solutions for input %d found -> recreate module.\n", i);
 161                                 goto recreate_module;
 162                         }
 163                 }
 164                 break;
 165
 166         recreate_module:
 167                 design->remove(module);
 168         }
 169
 170         log("Found viable UUT after %d cycles:\n", create_cycles);
 171         Pass::call(design, "write_ilang");
 172         Pass::call(design, "abc");
 173
 174         log("\n");
 175         log("Pre- and post-abc truth table:\n");
 176
 177         ezDefaultSAT ez;
 178         SigMap sigmap(module);
 179         SatGen satgen(&ez, &sigmap);
 180
 181         for (auto c : module->cells()) {
 182                 bool ok = satgen.importCell(c);
 183                 log_assert(ok);
 184         }
 185
 186         std::vector<int> in_vec = satgen.importSigSpec(in_sig);
 187         std::vector<int> inverse_in_vec = ez.vec_not(in_vec);
 188
 189         std::vector<int> out_vec = satgen.importSigSpec(out_sig);
 190
 191         bool found_error = false;
 192         bool truthtab2[16][4];
 193
 194         for (int i = 0; i < 16; i++)
 195         {
 196                 std::vector<int> assumptions;
 197                 for (int j = 0; j < SIZE(in_vec); j++)
 198                         assumptions.push_back((i & (1 << j)) ? in_vec.at(j) : inverse_in_vec.at(j));
 199
 200                 for (int j = 0; j < 4; j++)
 201                         truthtab2[i][j] = truthtab[i][j];
 202
 203                 std::vector<bool> results;
 204                 if (!ez.solve(out_vec, results, assumptions)) {
 205                         log("No stable solution for input %d found.\n", i);
 206                         found_error = true;
 207                         continue;
 208                 }
 209
 210                 for (int j = 0; j < 4; j++)
 211                         truthtab2[i][j] = results[j];
 212
 213                 assumptions.push_back(ez.vec_ne(out_vec, ez.vec_const(results)));
 214
 215                 std::vector<bool> results2;
 216                 if (ez.solve(out_vec, results2, assumptions)) {
 217                         log("Two stable solutions for input %d found -> recreate module.\n", i);
 218                         found_error = true;
 219                 }
 220         }
 221
 222         for (int i = 0; i < 16; i++) {
 223                 log("%3d ", i);
 224                 for (int j = 0; j < 4; j++)
 225                         log("%c", truthtab[i][j] ? '1' : '0');
 226                 log(" ");
 227                 for (int j = 0; j < 4; j++)
 228                         log("%c", truthtab2[i][j] ? '1' : '0');
 229                 for (int j = 0; j < 4; j++)
 230                         if (truthtab[i][j] != truthtab2[i][j]) {
 231                                 found_error = true;
 232                                 log(" !");
 233                                 break;
 234                         }
 235                 log("\n");
 236         }
 237
 238         log_assert(found_error == false);
 239         log("\n");
 240 }
 241
 242 struct TestAbcloopPass : public Pass {
 243         TestAbcloopPass() : Pass("test_abcloop", "automatically test handling of loops in abc command") { }
 244         virtual void help()
 245         {
 246                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 247                 log("\n");
 248                 log("    test_abcloop [options]\n");
 249                 log("\n");
 250                 log("Test handling of logic loops in ABC.\n");
 251                 log("\n");
 252                 log("    -n {integer}\n");
 253                 log("        create this number of circuits and test them (default = 100).\n");
 254                 log("\n");
 255                 log("    -s {positive_integer}\n");
 256                 log("        use this value as rng seed value (default = unix time).\n");
 257                 log("\n");
 258         }
 259         virtual void execute(std::vector<std::string> args, RTLIL::Design*)
 260         {
 261                 int num_iter = 100;
 262                 xorshift32_state = 0;
 263
 264                 int argidx;
 265                 for (argidx = 1; argidx < SIZE(args); argidx++)
 266                 {
 267                         if (args[argidx] == "-n" && argidx+1 < SIZE(args)) {
 268                                 num_iter = atoi(args[++argidx].c_str());
 269                                 continue;
 270                         }
 271                         if (args[argidx] == "-s" && argidx+1 < SIZE(args)) {
 272                                 xorshift32_state = atoi(args[++argidx].c_str());
 273                                 continue;
 274                         }
 275                         break;
 276                 }
 277
 278                 if (xorshift32_state == 0)
 279                         xorshift32_state = time(NULL) & 0x7fffffff;
 280
 281                 for (int i = 0; i < num_iter; i++)
 282                         test_abcloop();
 283         }
 284 } TestAbcloopPass;
 285