OptMuxtreeWorker Struct Reference

Collaboration diagram for OptMuxtreeWorker:

Data Structures
struct	bitDef_t
struct	bitinfo_t
struct	knowledge_t
struct	muxinfo_t
struct	portinfo_t

Public Member Functions
	OptMuxtreeWorker (RTLIL::Design *design, RTLIL::Module *module)
bool	list_is_subset (const std::vector< int > &sub, const std::vector< int > &super)
bool	is_in_list (const std::vector< int > &list, int value)
void	add_to_list (std::vector< int > &list, int value)
std::vector< int >	sig2bits (RTLIL::SigSpec sig)
void	eval_mux_port (knowledge_t &knowledge, int mux_idx, int port_idx)
void	eval_mux (knowledge_t &knowledge, int mux_idx)
void	eval_root_mux (int mux_idx)

Data Fields
RTLIL::Design *	design
RTLIL::Module *	module
SigMap	assign_map
int	removed_count
std::map< bitDef_t, int >	bit2num
std::vector< bitinfo_t >	bit2info
std::vector< muxinfo_t >	mux2info

Detailed Description

Definition at line 33 of file opt_muxtree.cc.

Constructor & Destructor Documentation

OptMuxtreeWorker::OptMuxtreeWorker ( RTLIL::Design *  design, RTLIL::Module *  module  )

inline

Definition at line 72 of file opt_muxtree.cc.

                                                               :
            design(design), module(module), assign_map(module), removed_count(0)
    {
        log("Running muxtree optimizier on module %s..\n", module->name.c_str());

        log("  Creating internal representation of mux trees.\n");

        // Populate bit2info[]:
        //  .seen_non_mux
        //  .mux_users
        //  .mux_drivers
        // Populate mux2info[].ports[]:
        //  .ctrl_sigs
        //  .input_sigs
        //  .const_activated
        for (auto cell : module->cells())
        {
            if (cell->type == "$mux" || cell->type == "$pmux")
            {
                RTLIL::SigSpec sig_a = cell->getPort("\\A");
                RTLIL::SigSpec sig_b = cell->getPort("\\B");
                RTLIL::SigSpec sig_s = cell->getPort("\\S");
                RTLIL::SigSpec sig_y = cell->getPort("\\Y");

                muxinfo_t muxinfo;
                muxinfo.cell = cell;

                for (int i = 0; i < sig_s.size(); i++) {
                    RTLIL::SigSpec sig = sig_b.extract(i*sig_a.size(), sig_a.size());
                    RTLIL::SigSpec ctrl_sig = assign_map(sig_s.extract(i, 1));
                    portinfo_t portinfo;
                    for (int idx : sig2bits(sig)) {
                        add_to_list(bit2info[idx].mux_users, mux2info.size());
                        add_to_list(portinfo.input_sigs, idx);
                    }
                    for (int idx : sig2bits(ctrl_sig))
                        add_to_list(portinfo.ctrl_sigs, idx);
                    portinfo.const_activated = ctrl_sig.is_fully_const() && ctrl_sig.as_bool();
                    portinfo.enabled = false;
                    muxinfo.ports.push_back(portinfo);
                }

                portinfo_t portinfo;
                for (int idx : sig2bits(sig_a)) {
                    add_to_list(bit2info[idx].mux_users, mux2info.size());
                    add_to_list(portinfo.input_sigs, idx);
                }
                portinfo.const_activated = false;
                portinfo.enabled = false;
                muxinfo.ports.push_back(portinfo);

                for (int idx : sig2bits(sig_y))
                    add_to_list(bit2info[idx].mux_drivers, mux2info.size());

                for (int idx : sig2bits(sig_s))
                    bit2info[idx].seen_non_mux = true;

                mux2info.push_back(muxinfo);
            }
            else
            {
                for (auto &it : cell->connections()) {
                    for (int idx : sig2bits(it.second))
                        bit2info[idx].seen_non_mux = true;
                }
            }
        }
        for (auto wire : module->wires()) {
            if (wire->port_output)
                for (int idx : sig2bits(RTLIL::SigSpec(wire)))
                    bit2info[idx].seen_non_mux = true;
        }

        if (mux2info.size() == 0) {
            log("  No muxes found in this module.\n");
            return;
        }

        // Populate mux2info[].ports[]:
        //  .input_muxes
        for (size_t i = 0; i < bit2info.size(); i++)
        for (int j : bit2info[i].mux_users)
        for (auto &p : mux2info[j].ports) {
            if (is_in_list(p.input_sigs, i))
                for (int k : bit2info[i].mux_drivers)
                    add_to_list(p.input_muxes, k);
        }

        log("  Evaluating internal representation of mux trees.\n");

        std::set<int> root_muxes;
        for (auto &bi : bit2info) {
            if (!bi.seen_non_mux)
                continue;
            for (int mux_idx : bi.mux_drivers)
                root_muxes.insert(mux_idx);
        }
        for (int mux_idx : root_muxes)
            eval_root_mux(mux_idx);

        log("  Analyzing evaluation results.\n");

        for (auto &mi : mux2info)
        {
            std::vector<int> live_ports;
            for (int port_idx = 0; port_idx < GetSize(mi.ports); port_idx++) {
                portinfo_t &pi = mi.ports[port_idx];
                if (pi.enabled) {
                    live_ports.push_back(port_idx);
                } else {
                    log("    dead port %d/%d on %s %s.\n", port_idx+1, GetSize(mi.ports),
                            mi.cell->type.c_str(), mi.cell->name.c_str());
                    removed_count++;
                }
            }

            if (live_ports.size() == mi.ports.size())
                continue;

            if (live_ports.size() == 0) {
                module->remove(mi.cell);
                continue;
            }

            RTLIL::SigSpec sig_a = mi.cell->getPort("\\A");
            RTLIL::SigSpec sig_b = mi.cell->getPort("\\B");
            RTLIL::SigSpec sig_s = mi.cell->getPort("\\S");
            RTLIL::SigSpec sig_y = mi.cell->getPort("\\Y");

            RTLIL::SigSpec sig_ports = sig_b;
            sig_ports.append(sig_a);

            if (live_ports.size() == 1)
            {
                RTLIL::SigSpec sig_in = sig_ports.extract(live_ports[0]*sig_a.size(), sig_a.size());
                module->connect(RTLIL::SigSig(sig_y, sig_in));
                module->remove(mi.cell);
            }
            else
            {
                RTLIL::SigSpec new_sig_a, new_sig_b, new_sig_s;

                for (size_t i = 0; i < live_ports.size(); i++) {
                    RTLIL::SigSpec sig_in = sig_ports.extract(live_ports[i]*sig_a.size(), sig_a.size());
                    if (i == live_ports.size()-1) {
                        new_sig_a = sig_in;
                    } else {
                        new_sig_b.append(sig_in);
                        new_sig_s.append(sig_s.extract(live_ports[i], 1));
                    }
                }

                mi.cell->setPort("\\A", new_sig_a);
                mi.cell->setPort("\\B", new_sig_b);
                mi.cell->setPort("\\S", new_sig_s);
                if (new_sig_s.size() == 1) {
                    mi.cell->type = "$mux";
                    mi.cell->parameters.erase("\\S_WIDTH");
                } else {
                    mi.cell->parameters["\\S_WIDTH"] = RTLIL::Const(new_sig_s.size());
                }
            }
        }
    }

Here is the call graph for this function:

Member Function Documentation

void OptMuxtreeWorker::add_to_list ( std::vector< int > &  list, int  value  )

inline

Definition at line 253 of file opt_muxtree.cc.

    {
        if (!is_in_list(list, value))
            list.push_back(value);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

void OptMuxtreeWorker::eval_mux ( knowledge_t &  knowledge, int  mux_idx  )

inline

Definition at line 334 of file opt_muxtree.cc.

    {
        muxinfo_t &muxinfo = mux2info[mux_idx];

        // if there is a constant activated port we just use it
        for (size_t port_idx = 0; port_idx < muxinfo.ports.size()-1; port_idx++)
        {
            portinfo_t &portinfo = muxinfo.ports[port_idx];
            if (portinfo.const_activated) {
                eval_mux_port(knowledge, mux_idx, port_idx);
                return;
            }
        }

        // compare ports with known_active signals. if we find a match, only this
        // port can be active. do not include the last port (its the default port
        // that has no control signals).
        for (size_t port_idx = 0; port_idx < muxinfo.ports.size()-1; port_idx++)
        {
            portinfo_t &portinfo = muxinfo.ports[port_idx];
            for (size_t i = 0; i < knowledge.known_active.size(); i++) {
                if (list_is_subset(knowledge.known_active[i], portinfo.ctrl_sigs)) {
                    eval_mux_port(knowledge, mux_idx, port_idx);
                    return;
                }
            }
        }

        // compare ports with known_inactive and known_active signals. If all control
        // signals of the port are know_inactive or if the control signals of all other
        // ports are known_active this port can't be activated. this loop includes the
        // default port but no known_inactive match is performed on the default port.
        for (size_t port_idx = 0; port_idx < muxinfo.ports.size(); port_idx++)
        {
            portinfo_t &portinfo = muxinfo.ports[port_idx];

            if (port_idx < muxinfo.ports.size()-1) {
                bool found_non_known_inactive = false;
                for (int i : portinfo.ctrl_sigs)
                    if (knowledge.known_inactive[i] == 0)
                        found_non_known_inactive = true;
                if (!found_non_known_inactive)
                    continue;
            }

            bool port_active = true;
            std::vector<int> other_ctrl_sig;
            for (size_t i = 0; i < muxinfo.ports.size()-1; i++) {
                if (i == port_idx)
                    continue;
                other_ctrl_sig.insert(other_ctrl_sig.end(),
                        muxinfo.ports[i].ctrl_sigs.begin(), muxinfo.ports[i].ctrl_sigs.end());
            }
            for (size_t i = 0; i < knowledge.known_active.size(); i++) {
                if (list_is_subset(knowledge.known_active[i], other_ctrl_sig))
                    port_active = false;
            }
            if (port_active)
                eval_mux_port(knowledge, mux_idx, port_idx);
        }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

void OptMuxtreeWorker::eval_mux_port ( knowledge_t &  knowledge, int  mux_idx, int  port_idx  )

inline

Definition at line 296 of file opt_muxtree.cc.

    {
        muxinfo_t &muxinfo = mux2info[mux_idx];
        muxinfo.ports[port_idx].enabled = true;

        for (size_t i = 0; i < muxinfo.ports.size(); i++) {
            if (int(i) == port_idx)
                continue;
            for (int b : muxinfo.ports[i].ctrl_sigs)
                knowledge.known_inactive[b]++;
        }

        if (port_idx < int(muxinfo.ports.size())-1 && !muxinfo.ports[port_idx].const_activated)
            knowledge.known_active.push_back(muxinfo.ports[port_idx].ctrl_sigs);

        std::vector<int> parent_muxes;
        for (int m : muxinfo.ports[port_idx].input_muxes) {
            if (knowledge.visited_muxes.count(m) > 0)
                continue;
            knowledge.visited_muxes.insert(m);
            parent_muxes.push_back(m);
        }
        for (int m : parent_muxes)
            eval_mux(knowledge, m);
        for (int m : parent_muxes)
            knowledge.visited_muxes.erase(m);

        if (port_idx < int(muxinfo.ports.size())-1 && !muxinfo.ports[port_idx].const_activated)
            knowledge.known_active.pop_back();

        for (size_t i = 0; i < muxinfo.ports.size(); i++) {
            if (int(i) == port_idx)
                continue;
            for (int b : muxinfo.ports[i].ctrl_sigs)
                knowledge.known_inactive[b]--;
        }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

void OptMuxtreeWorker::eval_root_mux ( int  mux_idx )

inline

Definition at line 396 of file opt_muxtree.cc.

    {
        knowledge_t knowledge;
        knowledge.visited_muxes.insert(mux_idx);
        eval_mux(knowledge, mux_idx);
    }

Here is the call graph for this function:

Here is the caller graph for this function:

bool OptMuxtreeWorker::is_in_list ( const std::vector< int > &  list, int  value  )

inline

Definition at line 245 of file opt_muxtree.cc.

    {
        for (int v : list)
            if (v == value)
                return true;
        return false;
    }

Here is the caller graph for this function:

bool OptMuxtreeWorker::list_is_subset ( const std::vector< int > &  sub, const std::vector< int > &  super  )

inline

Definition at line 237 of file opt_muxtree.cc.

    {
        for (int v : sub)
            if (!is_in_list(super, v))
                return false;
        return true;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

std::vector<int> OptMuxtreeWorker::sig2bits ( RTLIL::SigSpec  sig )

inline

Definition at line 259 of file opt_muxtree.cc.

    {
        std::vector<int> results;
        assign_map.apply(sig);
        for (auto &bit : sig)
            if (bit.wire != NULL) {
                if (bit2num.count(bit) == 0) {
                    bitinfo_t info;
                    info.num = bit2info.size();
                    info.bit = bit;
                    info.seen_non_mux = false;
                    bit2info.push_back(info);
                    bit2num[info.bit] = info.num;
                }
                results.push_back(bit2num[bit]);
            }
        return results;
    }

Here is the call graph for this function:

Here is the caller graph for this function:

Field Documentation

SigMap OptMuxtreeWorker::assign_map

Definition at line 37 of file opt_muxtree.cc.

std::vector<bitinfo_t> OptMuxtreeWorker::bit2info

Definition at line 55 of file opt_muxtree.cc.

std::map<bitDef_t, int> OptMuxtreeWorker::bit2num

Definition at line 54 of file opt_muxtree.cc.

RTLIL::Design* OptMuxtreeWorker::design

Definition at line 35 of file opt_muxtree.cc.

RTLIL::Module* OptMuxtreeWorker::module

Definition at line 36 of file opt_muxtree.cc.

std::vector<muxinfo_t> OptMuxtreeWorker::mux2info

Definition at line 70 of file opt_muxtree.cc.

int OptMuxtreeWorker::removed_count

Definition at line 38 of file opt_muxtree.cc.

---

The documentation for this struct was generated from the following file:

• opt_muxtree.cc