passes/proc/proc_rmdead.cc

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2012  Claire Xenia Wolf <claire@yosyshq.com>
   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 #include <set>
  27
  28 USING_YOSYS_NAMESPACE
  29 PRIVATE_NAMESPACE_BEGIN
  30
  31 static bool can_use_fully_defined_pool(RTLIL::SwitchRule *sw)
  32 {
  33         if (!GetSize(sw->signal))
  34                 return false;
  35
  36         for (const RTLIL::SigBit &bit : sw->signal)
  37                 if (bit.wire == NULL)
  38                         return false;
  39
  40         for (const RTLIL::CaseRule *cas : sw->cases)
  41                 for (const RTLIL::SigSpec &sig : cas->compare)
  42                         if (!sig.is_fully_def())
  43                                 return false;
  44
  45         return true;
  46 }
  47
  48 // This replicates the necessary parts of BitPatternPool's interface, but rather
  49 // than storing remaining patterns, this explicitly stores which fully-defined
  50 // constants have already been matched.
  51 struct FullyDefinedPool
  52 {
  53         FullyDefinedPool(const RTLIL::SigSpec &signal)
  54                 : max_patterns{signal.size() >= 32 ? 0ul : 1ul << signal.size()}
  55         {}
  56
  57         bool take(RTLIL::SigSpec sig)
  58         {
  59                 if (default_reached || patterns.count(sig))
  60                         return false;
  61                 patterns.insert(sig);
  62                 return true;
  63         }
  64
  65         void take_all()
  66         {
  67                 default_reached = true;
  68         }
  69
  70         bool empty()
  71         {
  72                 return default_reached ||
  73                         (max_patterns && max_patterns == patterns.size());
  74         }
  75
  76         pool<RTLIL::SigSpec> patterns;
  77         bool default_reached = false;
  78         size_t max_patterns;
  79 };
  80
  81 void proc_rmdead(RTLIL::SwitchRule *sw, int &counter, int &full_case_counter);
  82
  83 template <class Pool>
  84 static void proc_rmdead_impl(RTLIL::SwitchRule *sw, int &counter, int &full_case_counter)
  85 {
  86         Pool pool(sw->signal);
  87
  88         for (size_t i = 0; i < sw->cases.size(); i++)
  89         {
  90                 bool is_default = GetSize(sw->cases[i]->compare) == 0 && (!pool.empty() || GetSize(sw->signal) == 0);
  91
  92                 for (size_t j = 0; j < sw->cases[i]->compare.size(); j++) {
  93                         RTLIL::SigSpec sig = sw->cases[i]->compare[j];
  94                         if (!sig.is_fully_const())
  95                                 continue;
  96                         if (!pool.take(sig))
  97                                 sw->cases[i]->compare.erase(sw->cases[i]->compare.begin() + (j--));
  98                 }
  99
 100                 if (!is_default) {
 101                         if (sw->cases[i]->compare.size() == 0) {
 102                                 delete sw->cases[i];
 103                                 sw->cases.erase(sw->cases.begin() + (i--));
 104                                 counter++;
 105                                 continue;
 106                         }
 107                         // if (pool.empty())
 108                         //      sw->cases[i]->compare.clear();
 109                 }
 110
 111                 for (auto switch_it : sw->cases[i]->switches)
 112                         proc_rmdead(switch_it, counter, full_case_counter);
 113
 114                 if (is_default)
 115                         pool.take_all();
 116         }
 117
 118         if (pool.empty() && !sw->get_bool_attribute(ID::full_case)) {
 119                 sw->set_bool_attribute(ID::full_case);
 120                 full_case_counter++;
 121         }
 122 }
 123
 124 void proc_rmdead(RTLIL::SwitchRule *sw, int &counter, int &full_case_counter)
 125 {
 126         if (can_use_fully_defined_pool(sw))
 127                 proc_rmdead_impl<FullyDefinedPool>(sw, counter, full_case_counter);
 128         else
 129                 proc_rmdead_impl<BitPatternPool>(sw, counter, full_case_counter);
 130 }
 131
 132 struct ProcRmdeadPass : public Pass {
 133         ProcRmdeadPass() : Pass("proc_rmdead", "eliminate dead trees in decision trees") { }
 134         void help() override
 135         {
 136                 //   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
 137                 log("\n");
 138                 log("    proc_rmdead [selection]\n");
 139                 log("\n");
 140                 log("This pass identifies unreachable branches in decision trees and removes them.\n");
 141                 log("\n");
 142         }
 143         void execute(std::vector<std::string> args, RTLIL::Design *design) override
 144         {
 145                 log_header(design, "Executing PROC_RMDEAD pass (remove dead branches from decision trees).\n");
 146
 147                 extra_args(args, 1, design);
 148
 149                 int total_counter = 0;
 150                 for (auto mod : design->modules()) {
 151                         if (!design->selected(mod))
 152                                 continue;
 153                         for (auto &proc_it : mod->processes) {
 154                                 if (!design->selected(mod, proc_it.second))
 155                                         continue;
 156                                 int counter = 0, full_case_counter = 0;
 157                                 for (auto switch_it : proc_it.second->root_case.switches)
 158                                         proc_rmdead(switch_it, counter, full_case_counter);
 159                                 if (counter > 0)
 160                                         log("Removed %d dead cases from process %s in module %s.\n", counter,
 161                                                         log_id(proc_it.first), log_id(mod));
 162                                 if (full_case_counter > 0)
 163                                         log("Marked %d switch rules as full_case in process %s in module %s.\n",
 164                                                         full_case_counter, log_id(proc_it.first), log_id(mod));
 165                                 total_counter += counter;
 166                         }
 167                 }
 168
 169                 log("Removed a total of %d dead cases.\n", total_counter);
 170         }
 171 } ProcRmdeadPass;
 172
 173 PRIVATE_NAMESPACE_END