#include "atom_netlist_utils.h"
#include <unordered_set>
#include <set>
#include <algorithm>
#include <iterator>
#include <cmath>

#include "logic_types.h"
#include "vtr_assert.h"
#include "vtr_log.h"

#include "vpr_error.h"
#include "vtr_vector_map.h"

/**
 * @brief Marks primitive output pins constant if all inputs to the block are constant
 *
 * Since marking one block constant may cause a downstream block to also be constant,
 * marking is repated until there is no further change
 */
int infer_and_mark_constant_pins(AtomNetlist& netlist, e_const_gen_inference const_gen_inference_method, const LogicalModels& models, int verbosity);

///@brief Marks all primitive output pins which have no combinationally connected inputs as constant pins
int mark_undriven_primitive_outputs_as_constant(AtomNetlist& netlist, int verbosity);

///@brief Marks all primitive output pins of blk which have only constant inputs as constant pins
int infer_and_mark_block_pins_constant(AtomNetlist& netlist, AtomBlockId blk, e_const_gen_inference const_gen_inference_method, const LogicalModels& models, int verbosity);
int infer_and_mark_block_combinational_outputs_constant(AtomNetlist& netlist, AtomBlockId blk, e_const_gen_inference const_gen_inference_method, int verbosity);
int infer_and_mark_block_sequential_outputs_constant(AtomNetlist& netlist, AtomBlockId blk, e_const_gen_inference const_gen_inference_method, const LogicalModels& models, int verbosity);

///@brief Returns the set of input ports which are combinationally connected to output_port
std::vector<AtomPortId> find_combinationally_connected_input_ports(const AtomNetlist& netlist, AtomPortId output_port);

///@brief Returns the set of clock ports which are combinationally connected to output_port
std::vector<AtomPortId> find_combinationally_connected_clock_ports(const AtomNetlist& netlist, AtomPortId output_port);

bool is_buffer_lut(const AtomNetlist& netlist, const AtomBlockId blk);
bool is_removable_block(const AtomNetlist& netlist, const AtomBlockId blk, const LogicalModels& models, std::string* reason = nullptr);
bool is_removable_input(const AtomNetlist& netlist, const AtomBlockId blk, const LogicalModels& models, std::string* reason = nullptr);
bool is_removable_output(const AtomNetlist& netlist, const AtomBlockId blk, std::string* reason = nullptr);

/**
 * @brief   Attempts to remove the specified buffer LUT blk from the netlist.
 * @return  true if successful
 */
bool remove_buffer_lut(AtomNetlist& netlist, AtomBlockId blk, const LogicalModels& models, int verbosity);

std::string make_unconn(size_t& unconn_count, PinType type);
void cube_to_minterms_recurr(std::vector<vtr::LogicValue> cube, std::vector<size_t>& minterms);

void print_netlist_as_blif(std::string filename, const AtomNetlist& netlist, const LogicalModels& models) {
    FILE* f = std::fopen(filename.c_str(), "w");
    print_netlist_as_blif(f, netlist, models);
    std::fclose(f);
}

void print_netlist_as_blif(FILE* f, const AtomNetlist& netlist, const LogicalModels& models) {
    constexpr const char* INDENT = "    ";
    size_t unconn_count = 0;

    fprintf(f, "#Atom netlist generated by VPR\n");

    fprintf(f, ".model %s\n", netlist.netlist_name().c_str());

    {
        std::vector<AtomBlockId> inputs;
        for (auto blk_id : netlist.blocks()) {
            if (netlist.block_type(blk_id) == AtomBlockType::INPAD) {
                inputs.push_back(blk_id);
            }
        }
        fprintf(f, ".inputs \\\n");
        for (size_t i = 0; i < inputs.size(); ++i) {
            fprintf(f, "%s%s", INDENT, netlist.block_name(inputs[i]).c_str());

            if (i != inputs.size() - 1) {
                fprintf(f, " \\\n");
            }
        }
        fprintf(f, "\n");
    }

    {
        std::vector<AtomBlockId> outputs;
        for (auto blk_id : netlist.blocks()) {
            if (netlist.block_type(blk_id) == AtomBlockType::OUTPAD) {
                outputs.push_back(blk_id);
            }
        }
        fprintf(f, ".outputs \\\n");
        size_t i = 0;
        std::set<std::pair<std::string, std::string>> artificial_buffer_connections_required;
        for (AtomBlockId blk_id : outputs) {
            VTR_ASSERT(netlist.block_pins(blk_id).size() == 1);
            AtomPinId pin = *netlist.block_pins(blk_id).begin();

            std::string blk_name = netlist.block_name(blk_id);

            std::string out_prefix("out:");
            int strip_size = blk_name.substr(0, out_prefix.size()) == out_prefix ? out_prefix.size() : 0;
            std::string out_name(blk_name.begin() + strip_size, blk_name.end()); //+4 to trim out: prefix if present

            fprintf(f, "%s%s", INDENT, out_name.c_str());

            //BLIF requires that primary outputs be driven by nets of the same name
            //
            //This is not something we enforce within the netlist data structures
            //
            //Since BLIF has no 'logical assignment' other than buffers we need to create
            //buffers to represent the change of net name.
            //
            //See if the net has a different name than the current port, if so we
            //need an artificial buffer LUT
            AtomNetId net = netlist.pin_net(pin);
            if (net) {
                std::string net_name = netlist.net_name(net);
                if (net_name != out_name) {
                    artificial_buffer_connections_required.insert({net_name, out_name});
                }
            }

            if (i != outputs.size() - 1) {
                fprintf(f, " \\\n");
            }
            ++i;
        }
        fprintf(f, "\n");
        fprintf(f, "\n");

        //Artificial buffers
        for (auto buf_pair : artificial_buffer_connections_required) {
            fprintf(f, "#Artificially inserted primary-output assignment buffer\n");
            fprintf(f, ".names %s %s\n", buf_pair.first.c_str(), buf_pair.second.c_str());
            fprintf(f, "1 1\n");
            fprintf(f, "\n");
        }
    }

    //Latch
    LogicalModelId latch_model = LogicalModels::MODEL_LATCH_ID;
    for (auto blk_id : netlist.blocks()) {
        if (netlist.block_type(blk_id) == AtomBlockType::BLOCK) {
            LogicalModelId blk_model = netlist.block_model(blk_id);
            if (blk_model != latch_model) continue;

            //Nets
            std::string d_net;
            std::string q_net;
            std::string clk_net;

            //Determine the nets
            auto input_ports = netlist.block_input_ports(blk_id);
            auto output_ports = netlist.block_output_ports(blk_id);
            auto clock_ports = netlist.block_clock_ports(blk_id);

            for (auto ports : {input_ports, output_ports, clock_ports}) {
                for (AtomPortId port_id : ports) {
                    auto pins = netlist.port_pins(port_id);
                    VTR_ASSERT(pins.size() <= 1);
                    for (auto in_pin_id : pins) {
                        auto net_id = netlist.pin_net(in_pin_id);
                        if (netlist.port_name(port_id) == "D") {
                            d_net = netlist.net_name(net_id);

                        } else if (netlist.port_name(port_id) == "Q") {
                            q_net = netlist.net_name(net_id);

                        } else if (netlist.port_name(port_id) == "clk") {
                            clk_net = netlist.net_name(net_id);

                        } else {
                            VPR_FATAL_ERROR(VPR_ERROR_ATOM_NETLIST, "Unrecognzied latch port '%s'", netlist.port_name(port_id).c_str());
                        }
                    }
                }
            }

            if (d_net.empty()) {
                VTR_LOG_WARN("No net found for .latch '%s' data input (D pin)\n", netlist.block_name(blk_id).c_str());
                d_net = make_unconn(unconn_count, PinType::SINK);
            }

            if (q_net.empty()) {
                VTR_LOG_WARN("No net found for .latch '%s' data output (Q pin)\n", netlist.block_name(blk_id).c_str());
                q_net = make_unconn(unconn_count, PinType::DRIVER);
            }

            if (clk_net.empty()) {
                VTR_LOG_WARN("No net found for .latch '%s' clock (clk pin)\n", netlist.block_name(blk_id).c_str());
                clk_net = make_unconn(unconn_count, PinType::SINK);
            }

            //Latch type: VPR always assumes rising edge
            auto type = "re";

            //Latch initial value
            int init_val = 3; //Unknown or unspecified
            //The initial value is stored as a single value in the truth table
            const auto& so_cover = netlist.block_truth_table(blk_id);
            if (so_cover.size() == 1) {
                VTR_ASSERT(so_cover.size() == 1);    //Only one row
                VTR_ASSERT(so_cover[0].size() == 1); //Only one column
                switch (so_cover[0][0]) {
                    case vtr::LogicValue::TRUE:
                        init_val = 1;
                        break;
                    case vtr::LogicValue::FALSE:
                        init_val = 0;
                        break;
                    case vtr::LogicValue::DONT_CARE:
                        init_val = 2;
                        break;
                    case vtr::LogicValue::UNKNOWN:
                        init_val = 3;
                        break;
                    default:
                        VTR_ASSERT_MSG(false, "Unrecognzied latch initial state");
                }
            }

            fprintf(f, ".latch %s %s %s %s %d\n", d_net.c_str(), q_net.c_str(), type, clk_net.c_str(), init_val);

            fprintf(f, "\n");
        }
    }

    //Names
    LogicalModelId names_model = LogicalModels::MODEL_NAMES_ID;
    for (auto blk_id : netlist.blocks()) {
        if (netlist.block_type(blk_id) == AtomBlockType::BLOCK) {
            LogicalModelId blk_model = netlist.block_model(blk_id);
            if (blk_model != names_model) continue;

            std::vector<AtomNetId> nets;

            //Collect Inputs
            auto input_ports = netlist.block_input_ports(blk_id);
            VTR_ASSERT(input_ports.size() <= 1);
            for (auto in_pin_id : netlist.block_input_pins(blk_id)) {
                auto net_id = netlist.pin_net(in_pin_id);
                nets.push_back(net_id);
            }

            //Collect Outputs
            auto out_pins = netlist.block_output_pins(blk_id);

            if (out_pins.size() == 1) {
                auto out_net_id = netlist.pin_net(*out_pins.begin());
                nets.push_back(out_net_id);
            } else {
                VTR_ASSERT(out_pins.size() == 0);
            }

            fprintf(f, ".names ");
            for (size_t i = 0; i < nets.size(); ++i) {
                auto net_id = nets[i];

                fprintf(f, "%s", netlist.net_name(net_id).c_str());

                if (i != nets.size() - 1) {
                    fprintf(f, " ");
                }
            }
            fprintf(f, "\n");

            //Print the truth table
            for (auto row : netlist.block_truth_table(blk_id)) {
                for (size_t i = 0; i < row.size(); ++i) {
                    //Space between input and output columns
                    if (i == row.size() - 1) {
                        fprintf(f, " ");
                    }

                    switch (row[i]) {
                        case vtr::LogicValue::TRUE:
                            fprintf(f, "1");
                            break;
                        case vtr::LogicValue::FALSE:
                            fprintf(f, "0");
                            break;
                        case vtr::LogicValue::DONT_CARE:
                            fprintf(f, "-");
                            break;
                        default:
                            VTR_ASSERT_MSG(false, "Valid single-output cover logic value");
                    }
                }
                fprintf(f, "\n");
            }
            fprintf(f, "\n");
        }
    }

    //Subckt
    LogicalModelId input_model = LogicalModels::MODEL_INPUT_ID;
    LogicalModelId output_model = LogicalModels::MODEL_OUTPUT_ID;
    std::set<LogicalModelId> subckt_models;
    for (auto blk_id : netlist.blocks()) {
        LogicalModelId blk_model = netlist.block_model(blk_id);
        if (blk_model == latch_model
            || blk_model == names_model
            || blk_model == input_model
            || blk_model == output_model) {
            continue;
        }

        //Must be a subckt
        subckt_models.insert(blk_model);
        const t_model& model = models.get_model(blk_model);

        std::vector<AtomPortId> ports;
        for (auto port_id : netlist.block_ports(blk_id)) {
            VTR_ASSERT(netlist.port_width(port_id) > 0);
            ports.push_back(port_id);
        }

        fprintf(f, "# Subckt %zu: %s\n", size_t(blk_id), netlist.block_name(blk_id).c_str());
        fprintf(f, ".subckt %s \\\n", model.name);
        for (size_t i = 0; i < ports.size(); i++) {
            auto width = netlist.port_width(ports[i]);
            for (size_t j = 0; j < width; ++j) {
                fprintf(f, "%s%s", INDENT, netlist.port_name(ports[i]).c_str());
                if (width != 1) {
                    fprintf(f, "[%zu]", j);
                }
                fprintf(f, "=");

                auto net_id = netlist.port_net(ports[i], j);
                if (net_id) {
                    fprintf(f, "%s", netlist.net_name(net_id).c_str());
                } else {
                    PortType port_type = netlist.port_type(ports[i]);

                    PinType pin_type = PinType::OPEN;
                    switch (port_type) {
                        case PortType::INPUT: //fallthrough
                        case PortType::CLOCK:
                            pin_type = PinType::SINK;
                            break;
                        case PortType::OUTPUT:
                            pin_type = PinType::DRIVER;
                            break;
                        default:
                            VTR_ASSERT_OPT_MSG(false, "Invalid port type");
                    }
                    fprintf(f, "%s", make_unconn(unconn_count, pin_type).c_str());
                }

                if (i != ports.size() - 1 || j != width - 1) {
                    fprintf(f, " \\\n");
                }
            }
        }

        fprintf(f, "\n");

        for (auto param : netlist.block_params(blk_id)) {
            fprintf(f, ".param %s %s\n", param.first.c_str(), param.second.c_str());
        }
        for (auto attr : netlist.block_attrs(blk_id)) {
            fprintf(f, ".attr %s %s\n", attr.first.c_str(), attr.second.c_str());
        }

        fprintf(f, "\n");
    }

    fprintf(f, ".end\n"); //Main model
    fprintf(f, "\n");

    //The subckt models
    for (LogicalModelId model_id : subckt_models) {
        const t_model& model = models.get_model(model_id);
        fprintf(f, ".model %s\n", model.name);

        fprintf(f, ".inputs");
        const t_model_ports* port = model.inputs;
        while (port) {
            VTR_ASSERT(port->size >= 0);
            if (port->size == 1) {
                fprintf(f, " \\\n");
                fprintf(f, "%s%s", INDENT, port->name);
            } else {
                for (int i = 0; i < port->size; ++i) {
                    fprintf(f, " \\\n");
                    fprintf(f, "%s%s[%d]", INDENT, port->name, i);
                }
            }
            port = port->next;
        }

        fprintf(f, "\n");
        fprintf(f, ".outputs");
        port = model.outputs;
        while (port) {
            VTR_ASSERT(port->size >= 0);
            if (port->size == 1) {
                fprintf(f, " \\\n");
                fprintf(f, "%s%s", INDENT, port->name);
            } else {
                for (int i = 0; i < port->size; ++i) {
                    fprintf(f, " \\\n");
                    fprintf(f, "%s%s[%d]", INDENT, port->name, i);
                }
            }
            port = port->next;
        }
        fprintf(f, "\n");

        fprintf(f, ".blackbox\n");
        fprintf(f, ".end\n");

        fprintf(f, "\n");
    }
}

int mark_constant_generators(AtomNetlist& netlist, e_const_gen_inference const_gen_inference_method, const LogicalModels& models, int verbosity) {
    int num_undriven_pins_marked_const = mark_undriven_primitive_outputs_as_constant(netlist, verbosity);
    VTR_LOGV(verbosity > 0, "Inferred %4d additional primitive pins as constant generators since they have no combinationally connected inputs\n", num_undriven_pins_marked_const);

    int num_inferred_pins_marked_const = infer_and_mark_constant_pins(netlist, const_gen_inference_method, models, verbosity);
    VTR_LOGV(verbosity > 0, "Inferred %4d additional primitive pins as constant generators due to constant inputs\n", num_inferred_pins_marked_const);

    return num_undriven_pins_marked_const + num_inferred_pins_marked_const;
}

int mark_undriven_primitive_outputs_as_constant(AtomNetlist& netlist, int verbosity) {
    //For each model/primtiive we know the set of internal timing edges.
    //
    //If there is not upstream pin/net driving *any* of an outputs timing edges
    //we assume that pin is a constant.

    size_t num_pins_marked_constant = 0;

    for (AtomBlockId blk : netlist.blocks()) {
        if (!blk) continue;

        //Don't mark primary I/Os as constants
        if (netlist.block_type(blk) != AtomBlockType::BLOCK) continue;

        for (AtomPortId output_port : netlist.block_output_ports(blk)) {
            const t_model_ports* model_port = netlist.port_model(output_port);

            //Don't mark sequential or clock generator ports as constants
            if (!model_port->clock.empty() || model_port->is_clock) continue;

            //Find the upstream combinationally connected ports
            std::vector<AtomPortId> upstream_ports = find_combinationally_connected_input_ports(netlist, output_port);

            //Check if any of the 'upstream' input pins have connected nets
            //
            //Note that we only check to see whether they are *connected* not whether they are non-constant.
            //Inference of pins as constant generators from upstream *constant nets* is handled elsewhere.
            bool has_connected_inputs = false;
            for (AtomPortId input_port : upstream_ports) {
                for (AtomPinId input_pin : netlist.port_pins(input_port)) {
                    AtomNetId input_net = netlist.pin_net(input_pin);

                    if (input_net) {
                        has_connected_inputs = true;
                        break;
                    }
                }
            }

            if (!has_connected_inputs) {
                //The current output port has no inputs driving the primitive's internal
                //timing edges. Therefore we treat all its pins as constant generators.
                for (AtomPinId output_pin : netlist.port_pins(output_port)) {
                    if (netlist.pin_is_constant(output_pin)) continue;

                    VTR_LOGV(verbosity > 1, "Marking pin '%s' as constant since it has no combinationally connected inputs\n",
                             netlist.pin_name(output_pin).c_str());
                    netlist.set_pin_is_constant(output_pin, true);
                    ++num_pins_marked_constant;
                }
            }
        }
    }

    return num_pins_marked_constant;
}

int infer_and_mark_constant_pins(AtomNetlist& netlist, e_const_gen_inference const_gen_inference_method, const LogicalModels& models, int verbosity) {
    size_t num_pins_inferred_constant = 0;

    //It is possible that by marking one constant generator
    //it may 'reveal' another constant generator downstream.
    //As a result we iteratively mark constant generators until
    //no additional ones are identified.
    size_t num_pins_marked = 0;
    do {
        num_pins_marked = 0;

        //Look through all the blocks marking those pins which are
        //constant generataors
        for (auto blk : netlist.blocks()) {
            if (!blk) continue;

            num_pins_marked += infer_and_mark_block_pins_constant(netlist, blk, const_gen_inference_method, models, verbosity);
        }

        num_pins_inferred_constant += num_pins_marked;
    } while (num_pins_marked != 0);

    return num_pins_inferred_constant;
}

int infer_and_mark_block_pins_constant(AtomNetlist& netlist, AtomBlockId block, e_const_gen_inference const_gen_inference_method, const LogicalModels& models, int verbosity) {
    size_t num_pins_marked_constant = 0;

    num_pins_marked_constant += infer_and_mark_block_combinational_outputs_constant(netlist, block, const_gen_inference_method, verbosity);

    num_pins_marked_constant += infer_and_mark_block_sequential_outputs_constant(netlist, block, const_gen_inference_method, models, verbosity);

    return num_pins_marked_constant;
}

int infer_and_mark_block_combinational_outputs_constant(AtomNetlist& netlist, AtomBlockId blk, e_const_gen_inference const_gen_inference_method, int verbosity) {
    //Only if combinational constant generator inference enabled
    if (const_gen_inference_method != e_const_gen_inference::COMB
        && const_gen_inference_method != e_const_gen_inference::COMB_SEQ) {
        return 0;
    }

    VTR_ASSERT(const_gen_inference_method == e_const_gen_inference::COMB
               || const_gen_inference_method == e_const_gen_inference::COMB_SEQ);

    //Don't mark primary I/Os as constants
    if (netlist.block_type(blk) != AtomBlockType::BLOCK) return 0;

    size_t num_pins_marked_constant = 0;
    for (AtomPortId output_port : netlist.block_output_ports(blk)) {
        const t_model_ports* model_port = netlist.port_model(output_port);

        //Only handle combinational ports
        if (!model_port->clock.empty() || model_port->is_clock) continue;

        //Find the upstream combinationally connected ports
        std::vector<AtomPortId> upstream_ports = find_combinationally_connected_input_ports(netlist, output_port);

        //Check if any of the 'upstream' input pins have connected nets
        //
        //Here we check whether *all* of the upstream nets are constants
        bool all_constant_inputs = true;
        for (AtomPortId input_port : upstream_ports) {
            for (AtomPinId input_pin : netlist.port_pins(input_port)) {
                AtomNetId input_net = netlist.pin_net(input_pin);

                if (input_net && !netlist.net_is_constant(input_net)) {
                    all_constant_inputs = false;
                    break;
                } else {
                    VTR_ASSERT(!input_net || netlist.net_is_constant(input_net));
                }
            }
        }

        if (all_constant_inputs) {
            //The current output port is combinational and has only constant upstream inputs.
            //Therefore we treat all its pins as constant generators.
            for (AtomPinId output_pin : netlist.port_pins(output_port)) {
                if (netlist.pin_is_constant(output_pin)) continue;

                VTR_LOGV(verbosity > 1, "Marking combinational pin '%s' as constant since all it's upstream inputs are constant\n",
                         netlist.pin_name(output_pin).c_str());
                netlist.set_pin_is_constant(output_pin, true);
                ++num_pins_marked_constant;
            }
        }
    }

    return num_pins_marked_constant;
}

int infer_and_mark_block_sequential_outputs_constant(AtomNetlist& netlist, AtomBlockId blk, e_const_gen_inference const_gen_inference_method, const LogicalModels& models, int verbosity) {
    //Only if sequential constant generator inference enabled
    if (const_gen_inference_method != e_const_gen_inference::COMB_SEQ) {
        return 0;
    }

    VTR_ASSERT(const_gen_inference_method == e_const_gen_inference::COMB_SEQ);

    //Don't mark primary I/Os as constants
    if (netlist.block_type(blk) != AtomBlockType::BLOCK) return 0;

    //Collect the sequential output ports
    std::vector<AtomPortId> sequential_outputs;
    for (AtomPortId output_port : netlist.block_output_ports(blk)) {
        const t_model_ports* model_port = netlist.port_model(output_port);

        if (model_port->clock.empty() || model_port->is_clock) continue;

        //Only handle sequential ports
        sequential_outputs.push_back(output_port);
    }

    if (sequential_outputs.empty()) return 0; //No sequential outputs, nothing to do

    //We mark sequential output ports as constants only when *all* inputs are constant
    //
    //Note that this is a safely pessimistic condition, which means there may be some constant
    //sequential pins (i.e. those which depend on only a subset of input ports) are not marked
    //as constants.
    //
    //To improve upon this we could look at the internal dependencies specified between comb/seq
    //inputs and seq outputs. Provided they were all constants we could mark the sequential
    //output as constant. However this is left as future work. In particularl many of
    //the architecture files do not yet specify block-internal timing paths which would make
    //the proposed approach optimistic.

    bool all_inputs_constant = true;
    for (AtomPinId input_pin : netlist.block_input_pins(blk)) {
        AtomNetId input_net = netlist.pin_net(input_pin);

        if (input_net && !netlist.net_is_constant(input_net)) {
            all_inputs_constant = false;
            break;
        } else {
            VTR_ASSERT(!input_net || netlist.net_is_constant(input_net));
        }
    }

    if (!all_inputs_constant) return 0;

    int num_pins_marked_constant = 0;
    for (AtomPortId output_port : sequential_outputs) {
        for (AtomPinId output_pin : netlist.port_pins(output_port)) {
            if (netlist.pin_is_constant(output_pin)) continue;

            VTR_LOGV(verbosity > 1, "Marking sequential pin '%s' as constant since all inputs to block '%s' (%s) are constant\n",
                     netlist.pin_name(output_pin).c_str(),
                     netlist.block_name(blk).c_str(),
                     models.get_model(netlist.block_model(blk)).name);
            netlist.set_pin_is_constant(output_pin, true);
            ++num_pins_marked_constant;
        }
    }

    return num_pins_marked_constant;
}

std::vector<AtomPortId> find_combinationally_connected_input_ports(const AtomNetlist& netlist, AtomPortId output_port) {
    std::vector<AtomPortId> upstream_ports;

    VTR_ASSERT(netlist.port_type(output_port) == PortType::OUTPUT);

    std::string out_port_name = netlist.port_name(output_port);

    AtomBlockId blk = netlist.port_block(output_port);

    //Look through each block input port to find those which are combinationally connected to the output port
    for (AtomPortId input_port : netlist.block_input_ports(blk)) {
        const t_model_ports* input_model_port = netlist.port_model(input_port);
        for (const std::string& sink_port_name : input_model_port->combinational_sink_ports) {
            if (sink_port_name == out_port_name) {
                upstream_ports.push_back(input_port);
            }
        }
    }

    return upstream_ports;
}

std::vector<AtomPortId> find_combinationally_connected_clock_ports(const AtomNetlist& netlist, AtomPortId output_port) {
    std::vector<AtomPortId> upstream_ports;

    VTR_ASSERT(netlist.port_type(output_port) == PortType::OUTPUT);

    std::string out_port_name = netlist.port_name(output_port);

    AtomBlockId blk = netlist.port_block(output_port);

    //Look through each block input port to find those which are combinationally connected to the output port
    for (AtomPortId clock_port : netlist.block_clock_ports(blk)) {
        const t_model_ports* clock_model_port = netlist.port_model(clock_port);
        for (const std::string& sink_port_name : clock_model_port->combinational_sink_ports) {
            if (sink_port_name == out_port_name) {
                upstream_ports.push_back(clock_port);
            }
        }
    }

    return upstream_ports;
}

void absorb_buffer_luts(AtomNetlist& netlist, const LogicalModels& models, int verbosity) {
    //First we look through the netlist to find LUTs with identity logic functions
    //we then remove those luts, replacing the net's they drove with the inputs to the
    //buffer lut

    size_t removed_buffer_count = 0;

    //Remove the buffer luts
    for (auto blk : netlist.blocks()) {
        if (is_buffer_lut(netlist, blk)) {
            if (remove_buffer_lut(netlist, blk, models, verbosity)) {
                ++removed_buffer_count;
            }
        }
    }
    VTR_LOGV(verbosity > 0, "Absorbed %zu LUT buffers\n", removed_buffer_count);

    //TODO: absorb inverter LUTs?
}

bool is_buffer_lut(const AtomNetlist& netlist, const AtomBlockId blk) {
    if (netlist.block_type(blk) == AtomBlockType::BLOCK) {
        const LogicalModelId names_model = LogicalModels::MODEL_NAMES_ID;
        if (netlist.block_model(blk) != names_model) return false;

        auto input_ports = netlist.block_input_ports(blk);
        auto output_ports = netlist.block_output_ports(blk);

        //Buffer LUTs have a single input port and a single output port
        if (input_ports.size() == 1 && output_ports.size() == 1) {
            //Count the number of connected input pins
            size_t connected_input_pins = 0;
            for (auto input_pin : netlist.block_input_pins(blk)) {
                if (input_pin && netlist.pin_net(input_pin)) {
                    ++connected_input_pins;
                }
            }

            //Count the number of connected output pins
            size_t connected_output_pins = 0;
            for (auto output_pin : netlist.block_output_pins(blk)) {
                if (output_pin && netlist.pin_net(output_pin)) {
                    ++connected_output_pins;
                }
            }

            //Both ports must be single bit
            if (connected_input_pins == 1 && connected_output_pins == 1) {
                //It is a single-input single-output LUT, we now
                //inspect it's truth table
                //
                const auto& truth_table = netlist.block_truth_table(blk);

                VTR_ASSERT_MSG(truth_table.size() == 1, "One truth-table row");
                VTR_ASSERT_MSG(truth_table[0].size() == 2, "Two truth-table row entries");

                //Check for valid buffer logic functions
                // A LUT is a buffer provided it has the identity logic
                // function and a single input. For example:
                //
                // .names in_buf out_buf
                // 1 1
                //
                // and
                //
                // .names int_buf out_buf
                // 0 0
                //
                // both implement logical identity.
                if ((truth_table[0][0] == vtr::LogicValue::TRUE && truth_table[0][1] == vtr::LogicValue::TRUE)
                    || (truth_table[0][0] == vtr::LogicValue::FALSE && truth_table[0][1] == vtr::LogicValue::FALSE)) {
                    //It is a buffer LUT
                    return true;
                }
            }
        }
    }
    return false;
}

bool remove_buffer_lut(AtomNetlist& netlist, AtomBlockId blk, const LogicalModels& models, int verbosity) {
    //General net connectivity, numbers equal pin ids
    //
    // 1  in    2 ----- m+1  out
    // --------->| buf |---------> m+2
    //      |     -----     |
    //      |               |
    //      |--> 3          |----> m+3
    //      |               |
    //      | ...           |   ...
    //      |               |
    //      |--> m          |----> m+k+1
    //
    //On the input net we have a single driver (pin 1) and sinks (pins 2 through m)
    //On the output net we have a single driver (pin m+1) and sinks (pins m+2 through m+k+1)
    //
    //The resulting connectivity after removing the buffer is:
    //
    // 1            in
    // --------------------------> m+2
    //      |               |
    //      |               |
    //      |--> 3          |----> m+3
    //      |               |
    //      | ...           |   ...
    //      |               |
    //      |--> m          |----> m+k+1
    //
    //
    //We remove the buffer and fix-up the connectivity using the following steps
    //  - Remove the buffer (this also removes pins 2 and m+1 from the 'in' and 'out' nets)
    //  - Copy the pins left on 'in' and 'out' nets
    //  - Remove the 'in' and 'out' nets (this sets the pin's associated net to invalid)
    //  - We create a new net using the pins we copied, setting pin 1 as the driver and
    //    all other pins as sinks

    //Find the input and output nets
    auto input_pins = netlist.block_input_pins(blk);
    auto output_pins = netlist.block_output_pins(blk);

    VTR_ASSERT(input_pins.size() == 1);
    VTR_ASSERT(output_pins.size() == 1);

    auto input_pin = *input_pins.begin();   //i.e. pin 2
    auto output_pin = *output_pins.begin(); //i.e. pin m+1

    auto input_net = netlist.pin_net(input_pin);
    auto output_net = netlist.pin_net(output_pin);

    VTR_LOGV_WARN(verbosity > 1,
                  "Attempting to remove buffer '%s' (%s) from net '%s' to net '%s'\n",
                  netlist.block_name(blk).c_str(),
                  models.model_name(netlist.block_model(blk)).c_str(),
                  netlist.net_name(input_net).c_str(),
                  netlist.net_name(output_net).c_str());

    //Collect the new driver and sink pins
    AtomPinId new_driver = netlist.net_driver(input_net);

    if (!new_driver) {
        VTR_LOGV_WARN(verbosity > 2,
                      "Buffer '%s' has no input and will not be absorbed (left to be swept)\n",
                      netlist.block_name(blk).c_str(),
                      models.model_name(netlist.block_model(blk)).c_str(),
                      netlist.net_name(input_net).c_str(),
                      netlist.net_name(output_net).c_str());
        return false; //Dangling/undriven input, leave buffer to be swept
    }

    VTR_ASSERT(netlist.pin_type(new_driver) == PinType::DRIVER);

    std::vector<AtomPinId> new_sinks;
    auto input_sinks = netlist.net_sinks(input_net);
    auto output_sinks = netlist.net_sinks(output_net);

    //We don't copy the input pin (i.e. pin 2)
    std::copy_if(input_sinks.begin(), input_sinks.end(), std::back_inserter(new_sinks),
                 [input_pin](AtomPinId id) {
                     return id != input_pin;
                 });
    //Since we are copying sinks we don't include the output driver (i.e. pin m+1)
    std::copy(output_sinks.begin(), output_sinks.end(), std::back_inserter(new_sinks));

    VTR_ASSERT(new_sinks.size() == input_sinks.size() + output_sinks.size() - 1);

    //We now need to determine the name of the 'new' net
    //
    // We need to be careful about this name since a net pin could be
    // a Primary-Input/Primary-Output, and we don't want to change PI/PO names (for equivalence checking)
    //
    //Check if we have any PI/POs in the new net's pins
    // Note that the driver can only (potentially) be an INPAD, and the sinks only (potentially) OUTPADs
    AtomBlockType driver_block_type = netlist.block_type(netlist.pin_block(new_driver));
    bool driver_is_pi = (driver_block_type == AtomBlockType::INPAD);
    bool po_in_input_sinks = std::any_of(input_sinks.begin(), input_sinks.end(),
                                         [&](AtomPinId pin_id) {
                                             VTR_ASSERT(netlist.pin_type(pin_id) == PinType::SINK);
                                             AtomBlockId blk_id = netlist.pin_block(pin_id);
                                             return netlist.block_type(blk_id) == AtomBlockType::OUTPAD;
                                         });
    bool po_in_output_sinks = std::any_of(output_sinks.begin(), output_sinks.end(),
                                          [&](AtomPinId pin_id) {
                                              VTR_ASSERT(netlist.pin_type(pin_id) == PinType::SINK);
                                              AtomBlockId blk_id = netlist.pin_block(pin_id);
                                              return netlist.block_type(blk_id) == AtomBlockType::OUTPAD;
                                          });

    std::string new_net_name;
    auto input_net_name = netlist.net_name(input_net);
    auto output_net_name = netlist.net_name(output_net);

    if ((driver_is_pi || po_in_input_sinks) && !po_in_output_sinks) {
        //Must use the input name to preserve primary-input or primary-output name
        new_net_name = input_net_name;
    } else if (!(driver_is_pi || po_in_input_sinks) && po_in_output_sinks) {
        //Must use the output name to preserve primary-output name
        new_net_name = output_net_name;
    } else {
        new_net_name = input_net_name;
    }

    size_t initial_input_net_pins = netlist.net_pins(input_net).size();

    VTR_LOGV_WARN(verbosity > 2, "%s is a LUT buffer and will be absorbed\n", netlist.block_name(blk).c_str());

    //Remove the buffer
    //
    // Note that this removes pins 2 and m+1
    netlist.remove_block(blk);
    VTR_ASSERT(netlist.net_pins(input_net).size() == initial_input_net_pins - 1); //Should have removed pin 2
    VTR_ASSERT(netlist.net_driver(output_net) == AtomPinId::INVALID());           //Should have removed pin m+1

    //Remove the nets
    netlist.remove_net(input_net);
    netlist.remove_net(output_net);

    //Create the new merged net
    AtomNetId new_net = netlist.add_net(new_net_name, new_driver, new_sinks);

    netlist.add_net_alias(new_net_name, input_net_name);
    netlist.add_net_alias(new_net_name, output_net_name);

    VTR_ASSERT(netlist.net_pins(new_net).size() == initial_input_net_pins - 1 + output_sinks.size());
    return true;
}

bool is_removable_block(const AtomNetlist& netlist, const AtomBlockId blk_id, const LogicalModels& models, std::string* reason) {
    //Any block with no fanout is removable
    for (AtomPinId pin_id : netlist.block_output_pins(blk_id)) {
        if (!pin_id) continue;
        AtomNetId net_id = netlist.pin_net(pin_id);
        if (net_id) {
            //There is a valid output net
            return false;
        }
    }

    //If the model relative to this block is has the never prune flag set
    //it cannot be removed, even if it does not have a fanout
    auto blk_model = netlist.block_model(blk_id);
    if (models.get_model(blk_model).never_prune == true) {
        return false;
    }

    if (reason) *reason = "has no fanout";
    return true;
}

bool is_removable_input(const AtomNetlist& netlist, const AtomBlockId blk_id, const LogicalModels& models, std::string* reason) {
    AtomBlockType type = netlist.block_type(blk_id);

    //Only return true if an INPAD
    if (type != AtomBlockType::INPAD) return false;

    return is_removable_block(netlist, blk_id, models, reason);
}

bool is_removable_output(const AtomNetlist& netlist, const AtomBlockId blk_id, std::string* reason) {
    AtomBlockType type = netlist.block_type(blk_id);

    //Only return true if an OUTPAD
    if (type != AtomBlockType::OUTPAD) return false;

    //An output is only removable if it has no fan-in
    for (AtomPinId pin_id : netlist.block_input_pins(blk_id)) {
        if (!pin_id) continue;
        AtomNetId net_id = netlist.pin_net(pin_id);
        if (net_id) {
            //There is a valid input net
            return false;
        }
    }

    if (reason) *reason = "has no fanin";
    return true;
}

size_t sweep_constant_primary_outputs(AtomNetlist& netlist, int verbosity) {
    size_t removed_count = 0;
    for (AtomBlockId blk_id : netlist.blocks()) {
        if (!blk_id) continue;

        if (netlist.block_type(blk_id) == AtomBlockType::OUTPAD) {
            VTR_ASSERT(netlist.block_output_pins(blk_id).size() == 0);
            VTR_ASSERT(netlist.block_clock_pins(blk_id).size() == 0);

            bool all_inputs_are_const = true;
            for (AtomPinId pin_id : netlist.block_input_pins(blk_id)) {
                AtomNetId net_id = netlist.pin_net(pin_id);

                if (net_id && !netlist.net_is_constant(net_id)) {
                    all_inputs_are_const = false;
                    break;
                }
            }

            if (all_inputs_are_const) {
                //All inputs are constant, so we should remove this output
                VTR_LOGV_WARN(verbosity > 2, "Sweeping constant primary output '%s'\n", netlist.block_name(blk_id).c_str());
                netlist.remove_block(blk_id);
                removed_count++;
            }
        }
    }
    return removed_count;
}

size_t sweep_iterative(AtomNetlist& netlist,
                       bool should_sweep_ios,
                       bool should_sweep_nets,
                       bool should_sweep_blocks,
                       bool should_sweep_constant_primary_outputs,
                       e_const_gen_inference const_gen_inference_method,
                       const LogicalModels& models,
                       int verbosity) {
    size_t dangling_nets_swept = 0;
    size_t dangling_blocks_swept = 0;
    size_t dangling_inputs_swept = 0;
    size_t dangling_outputs_swept = 0;
    size_t constant_outputs_swept = 0;
    size_t constant_generators_marked = 0;

    //We perform multiple passes of sweeping, since sweeping something may
    //enable more things to be swept afterward.
    //
    //We keep sweeping until nothing else is removed
    size_t pass_dangling_nets_swept;
    size_t pass_dangling_blocks_swept;
    size_t pass_dangling_inputs_swept;
    size_t pass_dangling_outputs_swept;
    size_t pass_constant_outputs_swept;
    size_t pass_constant_generators_marked;
    do {
        pass_dangling_nets_swept = 0;
        pass_dangling_blocks_swept = 0;
        pass_dangling_inputs_swept = 0;
        pass_dangling_outputs_swept = 0;
        pass_constant_outputs_swept = 0;
        pass_constant_generators_marked = 0;

        if (should_sweep_ios) {
            pass_dangling_inputs_swept += sweep_inputs(netlist, models, verbosity);
            pass_dangling_outputs_swept += sweep_outputs(netlist, verbosity);
        }

        if (should_sweep_blocks) {
            pass_dangling_blocks_swept += sweep_blocks(netlist, models, verbosity);
        }

        if (should_sweep_nets) {
            pass_dangling_nets_swept += sweep_nets(netlist, verbosity);
        }

        if (should_sweep_constant_primary_outputs) {
            pass_constant_outputs_swept += sweep_constant_primary_outputs(netlist, verbosity);
        }

        pass_constant_generators_marked += mark_constant_generators(netlist, const_gen_inference_method, models, verbosity);

        dangling_nets_swept += pass_dangling_nets_swept;
        dangling_blocks_swept += pass_dangling_blocks_swept;
        dangling_inputs_swept += pass_dangling_inputs_swept;
        dangling_outputs_swept += pass_dangling_outputs_swept;
        constant_outputs_swept += pass_constant_outputs_swept;
        constant_generators_marked += pass_constant_generators_marked;
    } while (pass_dangling_nets_swept != 0
             || pass_dangling_blocks_swept != 0
             || pass_dangling_inputs_swept != 0
             || pass_dangling_outputs_swept != 0
             || pass_constant_outputs_swept != 0
             || pass_constant_generators_marked != 0);

    VTR_LOGV(verbosity > 0, "Swept input(s)      : %zu\n", dangling_inputs_swept);
    VTR_LOGV(verbosity > 0, "Swept output(s)     : %zu (%zu dangling, %zu constant)\n",
             dangling_outputs_swept + constant_outputs_swept,
             dangling_outputs_swept,
             constant_outputs_swept);
    VTR_LOGV(verbosity > 0, "Swept net(s)        : %zu\n", dangling_nets_swept);
    VTR_LOGV(verbosity > 0, "Swept block(s)      : %zu\n", dangling_blocks_swept);
    VTR_LOGV(verbosity > 0, "Constant Pins Marked: %zu\n", constant_generators_marked);

    return dangling_nets_swept
           + dangling_blocks_swept
           + dangling_inputs_swept
           + dangling_outputs_swept
           + constant_outputs_swept;
}

size_t sweep_blocks(AtomNetlist& netlist, const LogicalModels& models, int verbosity) {
    //Identify any blocks (not inputs or outputs) for removal
    std::unordered_set<AtomBlockId> blocks_to_remove;
    for (auto blk_id : netlist.blocks()) {
        if (!blk_id) continue;

        AtomBlockType type = netlist.block_type(blk_id);

        //Don't remove inpads/outpads here, we have separate sweep functions for these
        if (type == AtomBlockType::INPAD || type == AtomBlockType::OUTPAD) continue;

        //We remove any blocks with no fanout
        std::string reason;
        if (is_removable_block(netlist, blk_id, models, &reason)) {
            blocks_to_remove.insert(blk_id);

            VTR_LOGV_WARN(verbosity > 1, "Block '%s' will be swept (%s)\n", netlist.block_name(blk_id).c_str(), reason.c_str());
        }
    }

    //Remove them
    for (auto blk_id : blocks_to_remove) {
        netlist.remove_block(blk_id);
    }

    return blocks_to_remove.size();
}

size_t sweep_inputs(AtomNetlist& netlist, const LogicalModels& models, int verbosity) {
    //Identify any inputs for removal
    std::unordered_set<AtomBlockId> inputs_to_remove;
    for (auto blk_id : netlist.blocks()) {
        if (!blk_id) continue;

        std::string reason;
        if (is_removable_input(netlist, blk_id, models, &reason)) {
            inputs_to_remove.insert(blk_id);

            VTR_LOGV_WARN(verbosity > 1, "Primary input '%s' will be swept (%s)\n", netlist.block_name(blk_id).c_str(), reason.c_str());
        }
    }

    //Remove them
    for (auto blk_id : inputs_to_remove) {
        netlist.remove_block(blk_id);
    }

    return inputs_to_remove.size();
}

size_t sweep_outputs(AtomNetlist& netlist, int verbosity) {
    //Identify any outputs for removal
    std::unordered_set<AtomBlockId> outputs_to_remove;
    for (auto blk_id : netlist.blocks()) {
        if (!blk_id) continue;

        std::string reason;
        if (is_removable_output(netlist, blk_id, &reason)) {
            outputs_to_remove.insert(blk_id);
            VTR_LOGV_WARN(verbosity > 1, "Primary output '%s' will be swept (%s)\n", netlist.block_name(blk_id).c_str(), reason.c_str());
        }
    }

    //Remove them
    for (auto blk_id : outputs_to_remove) {
        netlist.remove_block(blk_id);
    }

    return outputs_to_remove.size();
}

size_t sweep_nets(AtomNetlist& netlist, int verbosity) {
    //Find any nets with no fanout or no driver, and remove them

    std::unordered_set<AtomNetId> nets_to_remove;
    for (auto net_id : netlist.nets()) {
        if (!net_id) continue;

        if (!netlist.net_driver(net_id)) {
            //No driver
            VTR_LOGV_WARN(verbosity > 1, "Net '%s' has no driver and will be removed\n", netlist.net_name(net_id).c_str());
            nets_to_remove.insert(net_id);
        }
        if (netlist.net_sinks(net_id).size() == 0) {
            //No sinks
            VTR_LOGV_WARN(verbosity > 1, "Net '%s' has no sinks and will be removed\n", netlist.net_name(net_id).c_str());
            nets_to_remove.insert(net_id);
        }
    }

    for (auto net_id : nets_to_remove) {
        netlist.remove_net(net_id);
    }

    return nets_to_remove.size();
}

std::string make_unconn(size_t& unconn_count, PinType /*pin_type*/) {
#if 0
    if(pin_type == PinType::DRIVER) {
        return std::string("unconn") + std::to_string(unconn_count++);
    } else {
        return std::string("unconn");
    }
#else
    return std::string("__vpr__unconn") + std::to_string(unconn_count++);
#endif
}

bool truth_table_encodes_on_set(const AtomNetlist::TruthTable& truth_table) {
    bool encodes_on_set = false;
    if (truth_table.empty()) {
        //An empyt truth table corresponds to a constant zero
        // making whether the 'on' set is encoded an arbitrary
        // choice (we choose true)
        encodes_on_set = true;
    } else {
        VTR_ASSERT_MSG(truth_table[0].size() > 0, "Can not have an empty truth-table row");

        //Inspect the last (output) value
        auto out_val = truth_table[0][truth_table[0].size() - 1];
        switch (out_val) {
            case vtr::LogicValue::TRUE:
                encodes_on_set = true;
                break;
            case vtr::LogicValue::FALSE:
                encodes_on_set = false;
                break;
            default:
                VPR_FATAL_ERROR(VPR_ERROR_OTHER, "Unrecognized truth-table output value");
        }
    }
    return encodes_on_set;
}

AtomNetlist::TruthTable permute_truth_table(const AtomNetlist::TruthTable& truth_table, const size_t num_inputs, const std::vector<int>& permutation) {
    AtomNetlist::TruthTable permuted_truth_table;

    for (const auto& row : truth_table) {
        //Space for the permuted row: num inputs + one output
        std::vector<vtr::LogicValue> permuted_row(num_inputs + 1, vtr::LogicValue::FALSE);

        //Permute the inputs in the row
        for (size_t i = 0; i < row.size() - 1; i++) {
            int permuted_idx = permutation[i];
            permuted_row[permuted_idx] = row[i];
        }
        //Assign the output value
        permuted_row[permuted_row.size() - 1] = row[row.size() - 1];

        permuted_truth_table.push_back(permuted_row);
    }

    return permuted_truth_table;
}

AtomNetlist::TruthTable expand_truth_table(const AtomNetlist::TruthTable& truth_table, const size_t num_inputs) {
    AtomNetlist::TruthTable expanded_truth_table;

    for (const auto& row : truth_table) {
        //Initialize an empty row
        std::vector<vtr::LogicValue> expanded_row(num_inputs + 1, vtr::LogicValue::FALSE);

        //Copy the existing input values
        for (size_t i = 0; i < row.size() - 1; ++i) {
            expanded_row[i] = row[i];
        }
        //Set the output value
        expanded_row[expanded_row.size() - 1] = row[row.size() - 1];

        expanded_truth_table.push_back(expanded_row);
    }

    return expanded_truth_table;
}

std::vector<vtr::LogicValue> truth_table_to_lut_mask(const AtomNetlist::TruthTable& truth_table, const size_t num_inputs) {
    bool on_set = truth_table_encodes_on_set(truth_table);

    //Initialize the lut mask
    size_t mask_bits = std::pow(2, num_inputs);
    std::vector<vtr::LogicValue> mask;
    if (on_set) {
        //If we are encoding the on-set the background value is false
        mask = std::vector<vtr::LogicValue>(mask_bits, vtr::LogicValue::FALSE);
    } else {
        //If we are encoding the off-set the background value is true
        mask = std::vector<vtr::LogicValue>(mask_bits, vtr::LogicValue::TRUE);
    }

    for (const auto& row : truth_table) {
        //Each row in the truth table (excluding the output) is a cube,
        //and may need to be expanded to account for don't cares

        std::vector<vtr::LogicValue> cube(row.begin(), --row.end());
        VTR_ASSERT(cube.size() == num_inputs);

        std::vector<size_t> minterms;

        for (auto minterm : cube_to_minterms(cube)) {
            //Mark the minterms in the mask

            VTR_ASSERT(minterm < mask.size());
            if (on_set) {
                mask[minterm] = vtr::LogicValue::TRUE;
            } else {
                mask[minterm] = vtr::LogicValue::FALSE;
            }
        }
    }
    return mask;
}

std::vector<size_t> cube_to_minterms(std::vector<vtr::LogicValue> cube) {
    std::vector<size_t> minterms;
    cube_to_minterms_recurr(cube, minterms);
    return minterms;
}

void cube_to_minterms_recurr(std::vector<vtr::LogicValue> cube, std::vector<size_t>& minterms) {
    bool cube_has_dc = false;
    for (size_t i = 0; i < cube.size(); ++i) {
        if (cube[i] == vtr::LogicValue::DONT_CARE) {
            //If we have a don't care we need to recursively expand
            //the don't care for the true and false cases
            cube_has_dc = true;

            //True case
            std::vector<vtr::LogicValue> cube_true = cube;
            cube_true[i] = vtr::LogicValue::TRUE;
            cube_to_minterms_recurr(cube_true, minterms); //Recurse

            //False case
            std::vector<vtr::LogicValue> cube_false = cube;
            cube_false[i] = vtr::LogicValue::FALSE;
            cube_to_minterms_recurr(cube_false, minterms); //Recurss

        } else {
            VTR_ASSERT(cube[i] == vtr::LogicValue::TRUE
                       || cube[i] == vtr::LogicValue::FALSE);
        }
    }

    if (!cube_has_dc) {
        //This cube is actually a minterm

        //Convert the cube to the minterm number
        size_t minterm = 0;
        for (size_t i = 0; i < cube.size(); ++i) {
            //The minterm is the integer representation of the
            //binary number stored in the cube. We do the conversion
            //by summing up all powers of two where the cube is true.
            if (cube[i] == vtr::LogicValue::TRUE) {
                minterm += (1 << i); //Note powers of two by shifting
            }
        }

        //Save the minterm number
        minterms.push_back(minterm);
    }
}

///@brief Find all the nets connected to clock pins in the netlist
std::set<AtomNetId> find_netlist_physical_clock_nets(const AtomNetlist& netlist, const LogicalModels& models) {
    std::set<AtomNetId> clock_nets; //The clock nets

    vtr::vector_map<LogicalModelId, std::vector<const t_model_ports*>> clock_gen_ports; //Records info about clock generating ports

    //Look through all the blocks (except I/Os) to find sink clock pins, or
    //clock generators
    //
    //Since we don't have good information about what pins are clock generators we build a lookup as we go
    for (AtomBlockId blk_id : netlist.blocks()) {
        if (!blk_id) continue;

        // Ignore I/O blocks
        AtomBlockType type = netlist.block_type(blk_id);
        if (type != AtomBlockType::BLOCK) continue;

        //Save any clock generating ports on this model type
        LogicalModelId model_id = netlist.block_model(blk_id);
        VTR_ASSERT(model_id.is_valid());
        if (clock_gen_ports.find(model_id) == clock_gen_ports.end()) {
            //First time we've seen this model, initialize it
            clock_gen_ports.insert(model_id, {});

            //Look at all the ports to find clock generators
            const t_model& model = models.get_model(model_id);
            for (const t_model_ports* model_port = model.outputs; model_port; model_port = model_port->next) {
                VTR_ASSERT(model_port->dir == OUT_PORT);
                if (model_port->is_clock) {
                    //Clock generator
                    clock_gen_ports[model_id].push_back(model_port);
                }
            }
        }

        //Look for connected input clocks
        for (AtomPinId pin_id : netlist.block_clock_pins(blk_id)) {
            if (!pin_id) continue;

            AtomNetId clk_net_id = netlist.pin_net(pin_id);
            VTR_ASSERT(clk_net_id);

            clock_nets.insert(clk_net_id);
        }

        //Look for any generated clocks
        if (!clock_gen_ports[model_id].empty()) {
            //This is a clock generator

            //Check all the clock generating ports
            for (const t_model_ports* model_port : clock_gen_ports[model_id]) {
                AtomPortId clk_gen_port = netlist.find_atom_port(blk_id, model_port);

                if (!clk_gen_port) continue; //Port not connected on this block

                for (AtomPinId pin_id : netlist.port_pins(clk_gen_port)) {
                    if (!pin_id) continue;

                    AtomNetId clk_net_id = netlist.pin_net(pin_id);
                    if (!clk_net_id) continue;

                    clock_nets.insert(clk_net_id);
                }
            }
        }
    }

    return clock_nets;
}

///@brief Finds all logical clock drivers in the netlist (by back-tracing through logic)
std::set<AtomPinId> find_netlist_logical_clock_drivers(const AtomNetlist& netlist, const LogicalModels& models) {
    std::set<AtomNetId> clock_nets = find_netlist_physical_clock_nets(netlist, models);

    //We now have a set of nets which drive clock pins
    //
    //However, some of them may be the same logical clock (e.g. if there are
    //buffers between them). Here we trace-back through any clock buffers
    //to find the true source
    size_t assumed_buffer_count = 0;
    std::set<AtomNetId> prev_clock_nets;
    LogicalModelId names_model_id = LogicalModels::MODEL_NAMES_ID;
    while (prev_clock_nets != clock_nets) { //Still tracing back
        prev_clock_nets = clock_nets;
        clock_nets.clear();

        for (AtomNetId clk_net : prev_clock_nets) {
            AtomPinId driver_pin = netlist.net_driver(clk_net);
            AtomPortId driver_port = netlist.pin_port(driver_pin);
            AtomBlockId driver_blk = netlist.port_block(driver_port);

            std::vector<AtomPortId> upstream_ports;

            if (netlist.block_model(driver_blk) == names_model_id) {
                //For .names we allow tracing back through data connections
                //which allows us to traceback through white-box .names buffers
                upstream_ports = find_combinationally_connected_input_ports(netlist, driver_port);
            } else {
                //For black boxes, we only trace back through inputs marked as clocks
                upstream_ports = find_combinationally_connected_clock_ports(netlist, driver_port);
            }

            if (upstream_ports.empty()) {
                //This net is a root net of a clock, keep it
                clock_nets.insert(clk_net);
            } else {
                //Trace the clock back through any combinational logic
                //
                // We are assuming that the combinational connections are independent and non-inverting.
                // If this is not the case, it is up to the end-user to specify the clocks explicitly
                // at the intermediate pins in the netlist.
                for (AtomPortId upstream_port : upstream_ports) {
                    for (AtomPinId upstream_pin : netlist.port_pins(upstream_port)) {
                        AtomNetId upstream_net = netlist.pin_net(upstream_pin);

                        VTR_ASSERT(upstream_net);

                        VTR_LOG_WARN("Assuming clocks may propagate through %s (%s) from pin %s to %s (assuming a non-inverting buffer).\n",
                                     netlist.block_name(driver_blk).c_str(), models.model_name(netlist.block_model(driver_blk)).c_str(),
                                     netlist.pin_name(upstream_pin).c_str(), netlist.pin_name(driver_pin).c_str());

                        clock_nets.insert(upstream_net);
                        ++assumed_buffer_count;
                    }
                }
            }
        }
    }

    if (assumed_buffer_count > 0) {
        VTR_LOG_WARN(
            "Assumed %zu netlist logic connections may be clock buffers. "
            "To override this behaviour explicitly create clocks at the appropriate netlist pins.\n",
            assumed_buffer_count);
    }

    //Extract the net drivers
    std::set<AtomPinId> clock_drivers;
    for (AtomNetId net : clock_nets) {
        AtomPinId driver = netlist.net_driver(net);

        if (netlist.pin_is_constant(driver)) {
            //Constant generators (e.g. gnd) are not clocks
            continue;
        }

        clock_drivers.insert(driver);
    }

    return clock_drivers;
}

///@brief Print information about clocks
void print_netlist_clock_info(const AtomNetlist& netlist, const LogicalModels& models) {
    std::set<AtomPinId> netlist_clock_drivers = find_netlist_logical_clock_drivers(netlist, models);
    VTR_LOG("Netlist contains %zu clocks\n", netlist_clock_drivers.size());

    //Print out pin/block fanout info for each block
    for (auto clock_driver : netlist_clock_drivers) {
        AtomNetId net_id = netlist.pin_net(clock_driver);
        auto sinks = netlist.net_sinks(net_id);
        size_t fanout = sinks.size();
        std::set<AtomBlockId> clk_blks;
        for (auto pin_id : sinks) {
            auto blk_id = netlist.pin_block(pin_id);
            clk_blks.insert(blk_id);
        }
        VTR_LOG("  Netlist Clock '%s' Fanout: %zu pins (%.1f%%), %zu blocks (%.1f%%)\n", netlist.net_name(net_id).c_str(), fanout, 100. * float(fanout) / netlist.pins().size(), clk_blks.size(), 100 * float(clk_blks.size()) / netlist.blocks().size());
    }
}
