From 7764d0ba1dcf064ae487ee985c43083a0909e7f4 Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Sat, 5 Jan 2013 11:13:26 +0100 Subject: initial import --- passes/proc/Makefile.inc | 8 ++ passes/proc/proc.cc | 44 +++++++ passes/proc/proc_arst.cc | 191 +++++++++++++++++++++++++++++ passes/proc/proc_clean.cc | 160 ++++++++++++++++++++++++ passes/proc/proc_dff.cc | 178 +++++++++++++++++++++++++++ passes/proc/proc_mux.cc | 294 +++++++++++++++++++++++++++++++++++++++++++++ passes/proc/proc_rmdead.cc | 87 ++++++++++++++ 7 files changed, 962 insertions(+) create mode 100644 passes/proc/Makefile.inc create mode 100644 passes/proc/proc.cc create mode 100644 passes/proc/proc_arst.cc create mode 100644 passes/proc/proc_clean.cc create mode 100644 passes/proc/proc_dff.cc create mode 100644 passes/proc/proc_mux.cc create mode 100644 passes/proc/proc_rmdead.cc (limited to 'passes/proc') diff --git a/passes/proc/Makefile.inc b/passes/proc/Makefile.inc new file mode 100644 index 00000000..68564e05 --- /dev/null +++ b/passes/proc/Makefile.inc @@ -0,0 +1,8 @@ + +OBJS += passes/proc/proc.o +OBJS += passes/proc/proc_clean.o +OBJS += passes/proc/proc_rmdead.o +OBJS += passes/proc/proc_arst.o +OBJS += passes/proc/proc_mux.o +OBJS += passes/proc/proc_dff.o + diff --git a/passes/proc/proc.cc b/passes/proc/proc.cc new file mode 100644 index 00000000..c0f502c8 --- /dev/null +++ b/passes/proc/proc.cc @@ -0,0 +1,44 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include +#include + +struct ProcPass : public Pass { + ProcPass() : Pass("proc") { } + virtual void execute(std::vector args, RTLIL::Design *design) + { + log_header("Executing PROC pass (convert processes to netlists).\n"); + log_push(); + + extra_args(args, 1, design); + + Pass::call(design, "proc_clean"); + Pass::call(design, "proc_rmdead"); + Pass::call(design, "proc_arst"); + Pass::call(design, "proc_mux"); + Pass::call(design, "proc_dff"); + Pass::call(design, "proc_clean"); + + log_pop(); + } +} ProcPass; + diff --git a/passes/proc/proc_arst.cc b/passes/proc/proc_arst.cc new file mode 100644 index 00000000..8e57d0ef --- /dev/null +++ b/passes/proc/proc_arst.cc @@ -0,0 +1,191 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/log.h" +#include +#include + +static bool check_signal(RTLIL::Module *mod, RTLIL::SigSpec signal, RTLIL::SigSpec ref, bool &polarity) +{ + if (signal.width != 1) + return false; + if (signal == ref) + return true; + + for (auto &cell_it : mod->cells) { + RTLIL::Cell *cell = cell_it.second; + if (cell->type == "$reduce_or" && cell->connections["\\Y"] == signal) + return check_signal(mod, cell->connections["\\A"], ref, polarity); + if (cell->type == "$reduce_bool" && cell->connections["\\Y"] == signal) + return check_signal(mod, cell->connections["\\A"], ref, polarity); + if (cell->type == "$logic_not" && cell->connections["\\Y"] == signal) { + polarity = !polarity; + return check_signal(mod, cell->connections["\\A"], ref, polarity); + } + if (cell->type == "$not" && cell->connections["\\Y"] == signal) { + polarity = !polarity; + return check_signal(mod, cell->connections["\\A"], ref, polarity); + } + if (cell->type == "$eq" && cell->connections["\\Y"] == signal) { + if (cell->connections["\\A"].is_fully_const()) { + if (!cell->connections["\\A"].as_bool()) + polarity = !polarity; + return check_signal(mod, cell->connections["\\B"], ref, polarity); + } + if (cell->connections["\\B"].is_fully_const()) { + if (!cell->connections["\\B"].as_bool()) + polarity = !polarity; + return check_signal(mod, cell->connections["\\A"], ref, polarity); + } + } + if (cell->type == "$ne" && cell->connections["\\Y"] == signal) { + if (cell->connections["\\A"].is_fully_const()) { + if (cell->connections["\\A"].as_bool()) + polarity = !polarity; + return check_signal(mod, cell->connections["\\B"], ref, polarity); + } + if (cell->connections["\\B"].is_fully_const()) { + if (cell->connections["\\B"].as_bool()) + polarity = !polarity; + return check_signal(mod, cell->connections["\\A"], ref, polarity); + } + } + } + + return false; +} + +static void apply_const(RTLIL::Module *mod, const RTLIL::SigSpec rspec, RTLIL::SigSpec &rval, RTLIL::CaseRule *cs, RTLIL::SigSpec const_sig, bool polarity, bool unknown) +{ + for (auto &action : cs->actions) { + if (unknown) + rspec.replace(action.first, RTLIL::SigSpec(RTLIL::State::Sm, action.second.width), &rval); + else + rspec.replace(action.first, action.second, &rval); + } + + for (auto sw : cs->switches) { + if (sw->signal.width == 0) { + for (auto cs2 : sw->cases) + apply_const(mod, rspec, rval, cs2, const_sig, polarity, unknown); + } + bool this_polarity = polarity; + if (check_signal(mod, sw->signal, const_sig, this_polarity)) { + for (auto cs2 : sw->cases) { + for (auto comp : cs2->compare) + if (comp == RTLIL::SigSpec(this_polarity, 1)) + goto matched_case; + if (cs2->compare.size() == 0) { + matched_case: + apply_const(mod, rspec, rval, cs2, const_sig, polarity, false); + break; + } + } + } else { + for (auto cs2 : sw->cases) + apply_const(mod, rspec, rval, cs2, const_sig, polarity, true); + } + } +} + +static void eliminate_const(RTLIL::Module *mod, RTLIL::CaseRule *cs, RTLIL::SigSpec const_sig, bool polarity) +{ + for (auto sw : cs->switches) { + bool this_polarity = polarity; + if (check_signal(mod, sw->signal, const_sig, this_polarity)) { + bool found_rem_path = false; + for (size_t i = 0; i < sw->cases.size(); i++) { + RTLIL::CaseRule *cs2 = sw->cases[i]; + for (auto comp : cs2->compare) + if (comp == RTLIL::SigSpec(this_polarity, 1)) + goto matched_case; + if (found_rem_path) { + matched_case: + sw->cases.erase(sw->cases.begin() + (i--)); + delete cs2; + continue; + } + found_rem_path = true; + cs2->compare.clear(); + } + sw->signal = RTLIL::SigSpec(); + } else { + for (auto cs2 : sw->cases) + eliminate_const(mod, cs2, const_sig, polarity); + } + } +} + +static void proc_arst(RTLIL::Module *mod, RTLIL::Process *proc, SigMap &assign_map) +{ + if (proc->root_case.switches.size() != 1) + return; + + RTLIL::SigSpec root_sig = proc->root_case.switches[0]->signal; + + for (auto &sync : proc->syncs) { + if (sync->type == RTLIL::SyncType::STp || sync->type == RTLIL::SyncType::STn) { + bool polarity = sync->type == RTLIL::SyncType::STp; + if (check_signal(mod, root_sig, sync->signal, polarity)) { + log("Found async reset %s in `%s.%s'.\n", log_signal(sync->signal), mod->name.c_str(), proc->name.c_str()); + sync->type = sync->type == RTLIL::SyncType::STp ? RTLIL::SyncType::ST1 : RTLIL::SyncType::ST0; + for (auto &action : sync->actions) { + RTLIL::SigSpec rspec = action.second; + RTLIL::SigSpec rval = RTLIL::SigSpec(RTLIL::State::Sm, rspec.width); + RTLIL::SigSpec last_rval; + for (int count = 0; rval != last_rval; count++) { + last_rval = rval; + apply_const(mod, rspec, rval, &proc->root_case, root_sig, polarity, false); + assign_map.apply(rval); + if (rval.is_fully_const()) + break; + if (count > 100) + log_error("Async reset %s yields endless loop at value %s for signal %s.\n", + log_signal(sync->signal), log_signal(rval), log_signal(action.first)); + rspec = rval; + } + if (rval.has_marked_bits()) + log_error("Async reset %s yields non-constant value %s for signal %s.\n", + log_signal(sync->signal), log_signal(rval), log_signal(action.first)); + action.second = rval; + } + eliminate_const(mod, &proc->root_case, root_sig, polarity); + } + } + } +} + +struct ProcArstPass : public Pass { + ProcArstPass() : Pass("proc_arst") { } + virtual void execute(std::vector args, RTLIL::Design *design) + { + log_header("Executing PROC_ARST pass (detect async resets in processes).\n"); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) { + SigMap assign_map(mod_it.second); + for (auto &proc_it : mod_it.second->processes) + proc_arst(mod_it.second, proc_it.second, assign_map); + } + } +} ProcArstPass; + diff --git a/passes/proc/proc_clean.cc b/passes/proc/proc_clean.cc new file mode 100644 index 00000000..ec9fade3 --- /dev/null +++ b/passes/proc/proc_clean.cc @@ -0,0 +1,160 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/log.h" +#include +#include + +static void switch_clean(RTLIL::SwitchRule *sw, RTLIL::CaseRule *parent, bool &did_something, int &count); +static void case_clean(RTLIL::CaseRule *cs, bool &did_something, int &count); + +static void switch_clean(RTLIL::SwitchRule *sw, RTLIL::CaseRule *parent, bool &did_something, int &count) +{ + if (sw->signal.width > 0 && sw->signal.is_fully_const()) + { + int found_matching_case_idx = -1; + for (int i = 0; i < int(sw->cases.size()) && found_matching_case_idx < 0; i++) + { + RTLIL::CaseRule *cs = sw->cases[i]; + if (cs->compare.size() == 0) + break; + for (int j = 0; j < int(cs->compare.size()); j++) { + RTLIL::SigSpec &val = cs->compare[j]; + if (!val.is_fully_const()) + continue; + if (val == sw->signal) { + cs->compare.clear(); + found_matching_case_idx = i; + break; + } else + cs->compare.erase(cs->compare.begin()+(j--)); + } + if (cs->compare.size() == 0 && found_matching_case_idx < 0) { + sw->cases.erase(sw->cases.begin()+(i--)); + delete cs; + } + } + while (found_matching_case_idx >= 0 && int(sw->cases.size()) > found_matching_case_idx+1) { + delete sw->cases.back(); + sw->cases.pop_back(); + } + if (found_matching_case_idx == 0) + sw->signal = RTLIL::SigSpec(); + } + + if (sw->cases.size() == 1 && (sw->signal.width == 0 || sw->cases[0]->compare.empty())) + { + did_something = true; + for (auto &action : sw->cases[0]->actions) + parent->actions.push_back(action); + for (auto sw2 : sw->cases[0]->switches) + parent->switches.push_back(sw2); + sw->cases[0]->switches.clear(); + delete sw->cases[0]; + sw->cases.clear(); + } + else + { + bool all_cases_are_empty = true; + for (auto cs : sw->cases) { + if (cs->actions.size() != 0 || cs->switches.size() != 0) + all_cases_are_empty = false; + case_clean(cs, did_something, count); + } + if (all_cases_are_empty) { + did_something = true; + for (auto cs : sw->cases) + delete cs; + sw->cases.clear(); + } + } +} + +static void case_clean(RTLIL::CaseRule *cs, bool &did_something, int &count) +{ + for (size_t i = 0; i < cs->actions.size(); i++) { + if (cs->actions[i].first.width == 0) { + did_something = true; + cs->actions.erase(cs->actions.begin() + (i--)); + } + } + for (size_t i = 0; i < cs->switches.size(); i++) { + RTLIL::SwitchRule *sw = cs->switches[i]; + if (sw->cases.size() == 0) { + cs->switches.erase(cs->switches.begin() + (i--)); + did_something = true; + delete sw; + count++; + } else + switch_clean(sw, cs, did_something, count); + } +} + +static void proc_clean(RTLIL::Module *mod, RTLIL::Process *proc, int &total_count) +{ + int count = 0; + bool did_something = true; + for (size_t i = 0; i < proc->syncs.size(); i++) { + for (size_t j = 0; j < proc->syncs[i]->actions.size(); j++) + if (proc->syncs[i]->actions[j].first.width == 0) + proc->syncs[i]->actions.erase(proc->syncs[i]->actions.begin() + (j--)); + if (proc->syncs[i]->actions.size() == 0) { + delete proc->syncs[i]; + proc->syncs.erase(proc->syncs.begin() + (i--)); + } + } + while (did_something) { + did_something = false; + case_clean(&proc->root_case, did_something, count); + } + if (count > 0) + log("Found and cleaned up %d empty switch%s in `%s.%s'.\n", count, count == 1 ? "" : "es", mod->name.c_str(), proc->name.c_str()); + total_count += count; +} + +struct ProcCleanPass : public Pass { + ProcCleanPass() : Pass("proc_clean") { } + virtual void execute(std::vector args, RTLIL::Design *design) + { + int total_count = 0; + log_header("Executing PROC_CLEAN pass (remove empty switches from decision trees).\n"); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) { + std::vector delme; + for (auto &proc_it : mod_it.second->processes) { + proc_clean(mod_it.second, proc_it.second, total_count); + if (proc_it.second->syncs.size() == 0 && proc_it.second->root_case.switches.size() == 0 && + proc_it.second->root_case.actions.size() == 0) { + log("Removing empty process `%s.%s'.\n", mod_it.first.c_str(), proc_it.second->name.c_str()); + delme.push_back(proc_it.first); + } + } + for (auto &id : delme) { + delete mod_it.second->processes[id]; + mod_it.second->processes.erase(id); + } + } + + log("Cleaned up %d empty switch%s.\n", total_count, total_count == 1 ? "" : "es"); + } +} ProcCleanPass; + diff --git a/passes/proc/proc_dff.cc b/passes/proc/proc_dff.cc new file mode 100644 index 00000000..ccacc72d --- /dev/null +++ b/passes/proc/proc_dff.cc @@ -0,0 +1,178 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/sigtools.h" +#include "kernel/consteval.h" +#include "kernel/log.h" +#include +#include +#include +#include + +static RTLIL::SigSpec find_any_lvalue(const RTLIL::Process *proc) +{ + RTLIL::SigSpec lvalue; + + for (auto sync : proc->syncs) + for (auto &action : sync->actions) + if (action.first.width > 0) { + lvalue = action.first; + lvalue.sort_and_unify(); + break; + } + + for (auto sync : proc->syncs) { + RTLIL::SigSpec this_lvalue; + for (auto &action : sync->actions) + this_lvalue.append(action.first); + this_lvalue.sort_and_unify(); + RTLIL::SigSpec common_sig = this_lvalue.extract(lvalue); + if (common_sig.width > 0) + lvalue = common_sig; + } + + return lvalue; +} + +static void gen_dff(RTLIL::Module *mod, RTLIL::SigSpec sig_in, RTLIL::Const val_rst, RTLIL::SigSpec sig_out, + bool clk_polarity, bool arst_polarity, RTLIL::SigSpec clk, RTLIL::SigSpec *arst, RTLIL::Process *proc) +{ + std::stringstream sstr; + sstr << "$procdff$" << (RTLIL::autoidx++); + + RTLIL::Cell *cell = new RTLIL::Cell; + cell->name = sstr.str(); + cell->type = arst ? "$adff" : "$dff"; + cell->attributes = proc->attributes; + mod->cells[cell->name] = cell; + + cell->parameters["\\WIDTH"] = RTLIL::Const(sig_in.width); + if (arst) { + cell->parameters["\\ARST_POLARITY"] = RTLIL::Const(arst_polarity, 1); + cell->parameters["\\ARST_VALUE"] = val_rst; + } + cell->parameters["\\CLK_POLARITY"] = RTLIL::Const(clk_polarity, 1); + + cell->connections["\\D"] = sig_in; + cell->connections["\\Q"] = sig_out; + if (arst) + cell->connections["\\ARST"] = *arst; + cell->connections["\\CLK"] = clk; + + log(" created %s cell `%s' with %s edge clock", cell->type.c_str(), cell->name.c_str(), clk_polarity ? "positive" : "negative"); + if (arst) + log(" and %s level reset", arst_polarity ? "positive" : "negative"); + log(".\n"); +} + +static void proc_dff(RTLIL::Module *mod, RTLIL::Process *proc, ConstEval &ce) +{ + while (1) + { + RTLIL::SigSpec sig = find_any_lvalue(proc); + + if (sig.width == 0) + break; + + log("Creating register for signal `%s.%s' using process `%s.%s'.\n", + mod->name.c_str(), log_signal(sig), mod->name.c_str(), proc->name.c_str()); + + RTLIL::SigSpec insig = RTLIL::SigSpec(RTLIL::State::Sz, sig.width); + RTLIL::SigSpec rstval = RTLIL::SigSpec(RTLIL::State::Sz, sig.width); + RTLIL::SyncRule *sync_level = NULL; + RTLIL::SyncRule *sync_edge = NULL; + RTLIL::SyncRule *sync_always = NULL; + + for (auto sync : proc->syncs) + for (auto &action : sync->actions) + { + if (action.first.extract(sig).width == 0) + continue; + + if (sync->type == RTLIL::SyncType::ST0 || sync->type == RTLIL::SyncType::ST1) { + if (sync_level != NULL && sync_level != sync) + log_error("Multiple level sensitive events found for this signal!\n"); + sig.replace(action.first, action.second, &rstval); + sync_level = sync; + } + else if (sync->type == RTLIL::SyncType::STp || sync->type == RTLIL::SyncType::STn) { + if (sync_edge != NULL && sync_edge != sync) + log_error("Multiple edge sensitive events found for this signal!\n"); + sig.replace(action.first, action.second, &insig); + sync_edge = sync; + } + else if (sync->type == RTLIL::SyncType::STa) { + if (sync_always != NULL && sync_always != sync) + log_error("Multiple always events found for this signal!\n"); + sig.replace(action.first, action.second, &insig); + sync_always = sync; + } + else { + log_error("Event with any-edge sensitivity found for this signal!\n"); + } + + action.first.remove2(sig, &action.second); + } + + ce.assign_map.apply(insig); + ce.assign_map.apply(rstval); + ce.assign_map.apply(sig); + + insig.optimize(); + rstval.optimize(); + sig.optimize(); + + if (sync_always) { + if (sync_edge || sync_level) + log_error("Mixed always event with edge and/or level sensitive events!\n"); + log(" created direct connection (no actual register cell created).\n"); + mod->connections.push_back(RTLIL::SigSig(sig, insig)); + continue; + } + + if (!sync_edge) + log_error("Missing edge-sensitive event for this signal!\n"); + + if (!rstval.is_fully_const() && !ce.eval(rstval)) + log_error("Async reset value `%s' is not constant!\n", log_signal(rstval)); + + gen_dff(mod, insig, rstval.chunks[0].data, sig, + sync_edge->type == RTLIL::SyncType::STp, + sync_level && sync_level->type == RTLIL::SyncType::ST1, + sync_edge->signal, sync_level ? &sync_level->signal : NULL, proc); + } +} + +struct ProcDffPass : public Pass { + ProcDffPass() : Pass("proc_dff") { } + virtual void execute(std::vector args, RTLIL::Design *design) + { + log_header("Executing PROC_DFF pass (convert process syncs to FFs).\n"); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) { + ConstEval ce(mod_it.second); + for (auto &proc_it : mod_it.second->processes) + proc_dff(mod_it.second, proc_it.second, ce); + } + } +} ProcDffPass; + diff --git a/passes/proc/proc_mux.cc b/passes/proc/proc_mux.cc new file mode 100644 index 00000000..4d50597d --- /dev/null +++ b/passes/proc/proc_mux.cc @@ -0,0 +1,294 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/bitpattern.h" +#include "kernel/log.h" +#include +#include +#include +#include + +static RTLIL::SigSpec find_any_lvalue(const RTLIL::CaseRule *cs) +{ + for (auto &action : cs->actions) { + if (action.first.width) + return action.first; + } + + for (auto sw : cs->switches) + for (auto cs2 : sw->cases) { + RTLIL::SigSpec sig = find_any_lvalue(cs2); + if (sig.width) + return sig; + } + + return RTLIL::SigSpec(); +} + +static void extract_core_signal(const RTLIL::CaseRule *cs, RTLIL::SigSpec &sig) +{ + for (auto &action : cs->actions) { + RTLIL::SigSpec lvalue = action.first.extract(sig); + if (lvalue.width) + sig = lvalue; + } + + for (auto sw : cs->switches) + for (auto cs2 : sw->cases) + extract_core_signal(cs2, sig); +} + +static RTLIL::SigSpec gen_cmp(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector &compare, RTLIL::SwitchRule *sw) +{ + std::stringstream sstr; + sstr << "$procmux$" << (RTLIL::autoidx++); + + RTLIL::Wire *cmp_wire = new RTLIL::Wire; + cmp_wire->name = sstr.str() + "_CMP"; + cmp_wire->width = 0; + mod->wires[cmp_wire->name] = cmp_wire; + + for (auto comp : compare) + { + RTLIL::SigSpec sig = signal; + sig.expand(); + comp.expand(); + + // get rid of don't-care bits + assert(sig.width == comp.width); + for (int i = 0; i < comp.width; i++) + if (comp.chunks[i].wire == NULL && comp.chunks[i].data.bits[0] == RTLIL::State::Sa) { + sig.remove(i, 1); + comp.remove(i--, 1); + } + if (comp.width == 0) + return RTLIL::SigSpec(); + sig.optimize(); + comp.optimize(); + + if (sig.width == 1 && comp == RTLIL::SigSpec(1,1)) + { + mod->connections.push_back(RTLIL::SigSig(RTLIL::SigSpec(cmp_wire, 1, cmp_wire->width++), sig)); + } + else + { + // create compare cell + RTLIL::Cell *eq_cell = new RTLIL::Cell; + std::stringstream sstr2; + sstr2 << sstr.str() << "_CMP" << cmp_wire->width; + eq_cell->name = sstr2.str(); + eq_cell->type = "$eq"; + eq_cell->attributes = sw->attributes; + mod->cells[eq_cell->name] = eq_cell; + + eq_cell->parameters["\\A_SIGNED"] = RTLIL::Const(0); + eq_cell->parameters["\\B_SIGNED"] = RTLIL::Const(0); + + eq_cell->parameters["\\A_WIDTH"] = RTLIL::Const(sig.width); + eq_cell->parameters["\\B_WIDTH"] = RTLIL::Const(comp.width); + eq_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + + eq_cell->connections["\\A"] = sig; + eq_cell->connections["\\B"] = comp; + eq_cell->connections["\\Y"] = RTLIL::SigSpec(cmp_wire, 1, cmp_wire->width++); + } + } + + RTLIL::Wire *ctrl_wire; + if (cmp_wire->width == 1) + { + ctrl_wire = cmp_wire; + } + else + { + ctrl_wire = new RTLIL::Wire; + ctrl_wire->name = sstr.str() + "_CTRL"; + ctrl_wire->width = 1; + mod->wires[ctrl_wire->name] = ctrl_wire; + + // reduce cmp vector to one logic signal + RTLIL::Cell *any_cell = new RTLIL::Cell; + any_cell->name = sstr.str() + "_ANY"; + any_cell->type = "$reduce_or"; + any_cell->attributes = sw->attributes; + mod->cells[any_cell->name] = any_cell; + + any_cell->parameters["\\A_SIGNED"] = RTLIL::Const(0); + any_cell->parameters["\\A_WIDTH"] = RTLIL::Const(cmp_wire->width); + any_cell->parameters["\\Y_WIDTH"] = RTLIL::Const(1); + + any_cell->connections["\\A"] = cmp_wire; + any_cell->connections["\\Y"] = RTLIL::SigSpec(ctrl_wire); + } + + return RTLIL::SigSpec(ctrl_wire); +} + +static RTLIL::SigSpec gen_mux(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector &compare, RTLIL::SigSpec when_signal, RTLIL::SigSpec else_signal, RTLIL::Cell *&last_mux_cell, RTLIL::SwitchRule *sw) +{ + assert(when_signal.width == else_signal.width); + + std::stringstream sstr; + sstr << "$procmux$" << (RTLIL::autoidx++); + + // the trivial cases + if (compare.size() == 0 || when_signal == else_signal) + return when_signal; + + // compare results + RTLIL::SigSpec ctrl_sig = gen_cmp(mod, signal, compare, sw); + if (ctrl_sig.width == 0) + return when_signal; + assert(ctrl_sig.width == 1); + + // prepare multiplexer output signal + RTLIL::Wire *result_wire = new RTLIL::Wire; + result_wire->name = sstr.str() + "_Y"; + result_wire->width = when_signal.width; + mod->wires[result_wire->name] = result_wire; + + // create the multiplexer itself + RTLIL::Cell *mux_cell = new RTLIL::Cell; + mux_cell->name = sstr.str(); + mux_cell->type = "$mux"; + mux_cell->attributes = sw->attributes; + mod->cells[mux_cell->name] = mux_cell; + + mux_cell->parameters["\\WIDTH"] = RTLIL::Const(when_signal.width); + mux_cell->connections["\\A"] = else_signal; + mux_cell->connections["\\B"] = when_signal; + mux_cell->connections["\\S"] = ctrl_sig; + mux_cell->connections["\\Y"] = RTLIL::SigSpec(result_wire); + + last_mux_cell = mux_cell; + return RTLIL::SigSpec(result_wire); +} + +static void append_pmux(RTLIL::Module *mod, const RTLIL::SigSpec &signal, const std::vector &compare, RTLIL::SigSpec when_signal, RTLIL::Cell *last_mux_cell, RTLIL::SwitchRule *sw) +{ + assert(last_mux_cell != NULL); + assert(when_signal.width == last_mux_cell->connections["\\A"].width); + + std::stringstream sstr; + sstr << "$procmux$" << (RTLIL::autoidx++); + + RTLIL::SigSpec ctrl_sig = gen_cmp(mod, signal, compare, sw); + assert(ctrl_sig.width == 1); + last_mux_cell->type = "$pmux"; + last_mux_cell->connections["\\S"].append(ctrl_sig); + last_mux_cell->connections["\\B"].append(when_signal); + last_mux_cell->parameters["\\S_WIDTH"] = last_mux_cell->connections["\\S"].width; +} + +static RTLIL::SigSpec signal_to_mux_tree(RTLIL::Module *mod, RTLIL::CaseRule *cs, const RTLIL::SigSpec &sig, const RTLIL::SigSpec &defval) +{ + RTLIL::SigSpec result = defval; + + for (auto &action : cs->actions) { + sig.replace(action.first, action.second, &result); + action.first.remove2(sig, &action.second); + } + + for (auto sw : cs->switches) + { + // detect groups of parallel cases + std::vector pgroups(sw->cases.size()); + if (sw->attributes.count("\\parallel_case") == 0) { + BitPatternPool pool(sw->signal.width); + bool extra_group_for_next_case = false; + for (size_t i = 0; i < sw->cases.size(); i++) { + RTLIL::CaseRule *cs2 = sw->cases[i]; + if (i != 0) { + pgroups[i] = pgroups[i-1]; + if (extra_group_for_next_case) { + pgroups[i] = pgroups[i-1]+1; + extra_group_for_next_case = false; + } + for (auto pat : cs2->compare) + if (!pat.is_fully_const() || !pool.has_all(pat)) + pgroups[i] = pgroups[i-1]+1; + if (cs2->compare.empty()) + pgroups[i] = pgroups[i-1]+1; + if (pgroups[i] != pgroups[i-1]) + pool = BitPatternPool(sw->signal.width); + } + for (auto pat : cs2->compare) + if (!pat.is_fully_const()) + extra_group_for_next_case = true; + else + pool.take(pat); + } + } + + // evaluate in reverse order to give the first entry the top priority + RTLIL::SigSpec initial_val = result; + RTLIL::Cell *last_mux_cell = NULL; + for (size_t i = 0; i < sw->cases.size(); i++) { + int case_idx = sw->cases.size() - i - 1; + RTLIL::CaseRule *cs2 = sw->cases[case_idx]; + RTLIL::SigSpec value = signal_to_mux_tree(mod, cs2, sig, initial_val); + if (last_mux_cell && pgroups[case_idx] == pgroups[case_idx+1]) + append_pmux(mod, sw->signal, cs2->compare, value, last_mux_cell, sw); + else + result = gen_mux(mod, sw->signal, cs2->compare, value, result, last_mux_cell, sw); + } + } + + return result; +} + +static void proc_mux(RTLIL::Module *mod, RTLIL::Process *proc) +{ + bool first = true; + while (1) + { + RTLIL::SigSpec sig = find_any_lvalue(&proc->root_case); + + if (sig.width == 0) + break; + + if (first) { + log("Creating decoders for process `%s.%s'.\n", mod->name.c_str(), proc->name.c_str()); + first = false; + } + + extract_core_signal(&proc->root_case, sig); + + log(" creating decoder for signal `%s'.\n", log_signal(sig)); + + RTLIL::SigSpec value = signal_to_mux_tree(mod, &proc->root_case, sig, RTLIL::SigSpec(RTLIL::State::Sx, sig.width)); + mod->connections.push_back(RTLIL::SigSig(sig, value)); + } +} + +struct ProcMuxPass : public Pass { + ProcMuxPass() : Pass("proc_mux") { } + virtual void execute(std::vector args, RTLIL::Design *design) + { + log_header("Executing PROC_MUX pass (convert decision trees to multiplexers).\n"); + + extra_args(args, 1, design); + + for (auto &mod_it : design->modules) + for (auto &proc_it : mod_it.second->processes) + proc_mux(mod_it.second, proc_it.second); + } +} ProcMuxPass; + diff --git a/passes/proc/proc_rmdead.cc b/passes/proc/proc_rmdead.cc new file mode 100644 index 00000000..ca2070ca --- /dev/null +++ b/passes/proc/proc_rmdead.cc @@ -0,0 +1,87 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/register.h" +#include "kernel/bitpattern.h" +#include "kernel/log.h" +#include +#include +#include +#include +#include + +static void proc_rmdead(RTLIL::SwitchRule *sw, int &counter) +{ + BitPatternPool pool(sw->signal); + + for (size_t i = 0; i < sw->cases.size(); i++) + { + bool is_default = sw->cases[i]->compare.size() == 0 && !pool.empty(); + + for (size_t j = 0; j < sw->cases[i]->compare.size(); j++) { + RTLIL::SigSpec sig = sw->cases[i]->compare[j]; + if (!sig.is_fully_const()) + continue; + if (!pool.take(sig)) + sw->cases[i]->compare.erase(sw->cases[i]->compare.begin() + (j--)); + } + + if (!is_default) { + if (sw->cases[i]->compare.size() == 0) { + delete sw->cases[i]; + sw->cases.erase(sw->cases.begin() + (i--)); + counter++; + continue; + } + if (pool.empty()) + sw->cases[i]->compare.clear(); + } + + for (auto switch_it : sw->cases[i]->switches) + proc_rmdead(switch_it, counter); + + if (is_default) + pool.take_all(); + } +} + +struct ProcRmdeadPass : public Pass { + ProcRmdeadPass() : Pass("proc_rmdead") { } + virtual void execute(std::vector args, RTLIL::Design *design) + { + log_header("Executing PROC_RMDEAD pass (remove dead branches from decision trees).\n"); + + extra_args(args, 1, design); + + int total_counter = 0; + for (auto &mod_it : design->modules) + for (auto &proc_it : mod_it.second->processes) { + int counter = 0; + for (auto switch_it : proc_it.second->root_case.switches) + proc_rmdead(switch_it, counter); + if (counter > 0) + log("Removed %d dead cases from process %s in module %s.\n", counter, + proc_it.first.c_str(), mod_it.first.c_str()); + total_counter += counter; + } + + log("Removed a total of %d dead cases.\n", total_counter); + } +} ProcRmdeadPass; + -- cgit v1.2.3