aboutsummaryrefslogtreecommitdiffstats
path: root/fpga_interchange/site_arch.cc
blob: 4438193b6b179714b71fcae0452b56d9d8371033 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
pre { line-height: 125%; margin: 0; }
td.linenos pre { color: #000000; background-color: #f0f0f0; padding: 0 5px 0 5px; }
span.linenos { color: #000000; background-color: #f0f0f0; padding: 0 5px 0 5px; }
td.linenos pre.special { color: #000000; background-color: #ffffc0; padding: 0 5px 0 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding: 0 5px 0 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight { background: #ffffff; }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
# This file is dual licensed under the terms of the Apache License, Version
# 2.0, and the BSD License. See the LICENSE file in the root of this repository
# for complete details.

import abc

import pytest

import six

from cryptography.utils import InterfaceNotImplemented, verify_interface


class TestVerifyInterface(object):
    def test_verify_missing_method(self):
        @six.add_metaclass(abc.ABCMeta)
        class SimpleInterface(object):
            @abc.abstractmethod
            def method(self):
                """A simple method"""

        class NonImplementer(object):
            pass

        with pytest.raises(InterfaceNotImplemented):
            verify_interface(SimpleInterface, NonImplementer)

    def test_different_arguments(self):
        @six.add_metaclass(abc.ABCMeta)
        class SimpleInterface(object):
            @abc.abstractmethod
            def method(self, a):
                """Method with one argument"""

        class NonImplementer(object):
            def method(self):
                """Method with no arguments"""

        # Invoke this to ensure the line is covered
        NonImplementer().method()
        with pytest.raises(InterfaceNotImplemented):
            verify_interface(SimpleInterface, NonImplementer)

    def test_handles_abstract_property(self):
        @six.add_metaclass(abc.ABCMeta)
        class SimpleInterface(object):
            @abc.abstractproperty
            def property(self):
                """An abstract property"""

        class NonImplementer(object):
            @property
            def property(self):
                """A concrete property"""

        # Invoke this to ensure the line is covered
        NonImplementer().property
        verify_interface(SimpleInterface, NonImplementer)
'#n411'>411 412 413 414 415 416 417 418 419 420 421 422 423
/*
 *  nextpnr -- Next Generation Place and Route
 *
 *  Copyright (C) 2021  Symbiflow Authors
 *
 *
 *  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 "site_arch.h"
#include "site_arch.impl.h"

NEXTPNR_NAMESPACE_BEGIN

SiteInformation::SiteInformation(const Context *ctx, int32_t tile, int32_t site,
                                 const std::unordered_set<CellInfo *> &cells_in_site)
        : ctx(ctx), tile(tile), tile_type(ctx->chip_info->tiles[tile].type), site(site), cells_in_site(cells_in_site)
{
}

bool SiteArch::bindPip(const SitePip &pip, SiteNetInfo *net)
{
    SiteWire src = getPipSrcWire(pip);
    SiteWire dst = getPipDstWire(pip);

    if (!bindWire(src, net)) {
        return false;
    }
    if (!bindWire(dst, net)) {
        unbindWire(src);
        return false;
    }

    auto result = net->wires.emplace(dst, SitePipMap{pip, 1});
    if (!result.second) {
        if (result.first->second.pip != pip) {
            // Pip conflict!
            if (debug()) {
                log_info("Pip conflict binding pip %s to wire %s, conflicts with pip %s\n", nameOfPip(pip),
                         nameOfWire(dst), nameOfPip(result.first->second.pip));
            }

            unbindWire(src);
            unbindWire(dst);
            return false;
        }

        result.first->second.count += 1;
    }

    if (debug()) {
        log_info("Bound pip %s to wire %s\n", nameOfPip(pip), nameOfWire(dst));
    }

    return true;
}

void SiteArch::unbindPip(const SitePip &pip)
{
    SiteWire src = getPipSrcWire(pip);
    SiteWire dst = getPipDstWire(pip);

    if (debug()) {
        log_info("Unbinding pip %s from wire %s\n", nameOfPip(pip), nameOfWire(dst));
    }

    SiteNetInfo *src_net = unbindWire(src);
    SiteNetInfo *dst_net = unbindWire(dst);
    NPNR_ASSERT(src_net == dst_net);
    auto iter = dst_net->wires.find(dst);
    NPNR_ASSERT(iter != dst_net->wires.end());
    NPNR_ASSERT(iter->second.count >= 1);
    iter->second.count -= 1;

    if (iter->second.count == 0) {
        dst_net->wires.erase(iter);
    }
}

void SiteArch::archcheck()
{
    for (SiteWire wire : getWires()) {
        for (SitePip pip : getPipsDownhill(wire)) {
            SiteWire wire2 = getPipSrcWire(pip);
            log_assert(wire == wire2);
        }

        for (SitePip pip : getPipsUphill(wire)) {
            SiteWire wire2 = getPipDstWire(pip);
            log_assert(wire == wire2);
        }
    }
}

SiteArch::SiteArch(const SiteInformation *site_info) : ctx(site_info->ctx), site_info(site_info)
{
    // Build list of input and output site ports
    //
    // FIXME: This doesn't need to be computed over and over, move to
    // arch/chip db.
    const TileTypeInfoPOD &tile_type = loc_info(&site_info->chip_info(), *site_info);
    PipId pip;
    pip.tile = site_info->tile;
    for (size_t pip_index = 0; pip_index < tile_type.pip_data.size(); ++pip_index) {
        if (tile_type.pip_data[pip_index].site != site_info->site) {
            continue;
        }

        pip.index = pip_index;

        if (!site_info->is_site_port(pip)) {
            continue;
        }

        WireId src_wire = ctx->getPipSrcWire(pip);
        if (site_info->is_wire_in_site(src_wire)) {
            output_site_ports.push_back(pip);
        } else {
            input_site_ports.push_back(pip);
        }
    }

    // Create list of out of site sources and sinks.

    bool have_vcc_pins = false;
    for (CellInfo *cell : site_info->cells_in_site) {
        for (const auto &pin_pair : cell->cell_bel_pins) {
            const PortInfo &port = cell->ports.at(pin_pair.first);
            if (port.net != nullptr) {
                nets.emplace(port.net, SiteNetInfo{port.net});
            }
        }

        if (!cell->lut_cell.vcc_pins.empty()) {
            have_vcc_pins = true;
        }
    }

    for (auto &net_pair : nets) {
        NetInfo *net = net_pair.first;
        SiteNetInfo &net_info = net_pair.second;

        // All nets require drivers
        NPNR_ASSERT(net->driver.cell != nullptr);

        bool net_driven_out_of_site = false;
        if (net->driver.cell->bel == BelId()) {
            // The driver of this site hasn't been placed, so treat it as
            // out of site.
            out_of_site_sources.push_back(SiteWire::make(site_info, PORT_OUT, net));
            net_info.driver = out_of_site_sources.back();
            net_driven_out_of_site = true;
        } else {
            if (!site_info->is_bel_in_site(net->driver.cell->bel)) {

                // The driver of this site has been placed, it is an out
                // of site source.
                out_of_site_sources.push_back(SiteWire::make(site_info, PORT_OUT, net));
                // out_of_site_sources.back().wire = ctx->getNetinfoSourceWire(net);
                net_info.driver = out_of_site_sources.back();

                net_driven_out_of_site = true;
            } else {
                net_info.driver = SiteWire::make(site_info, ctx->getNetinfoSourceWire(net));
            }
        }

        if (net_driven_out_of_site) {
            // Because this net is driven from a source out of the site,
            // no out of site sink is required.
            continue;
        }

        // Examine net to determine if it has any users not in this site.
        bool net_used_out_of_site = false;
        for (const PortRef &user : net->users) {
            NPNR_ASSERT(user.cell != nullptr);

            if (user.cell->bel == BelId()) {
                // Because this net has a user that has not been placed,
                // and this net is being driven from this site, make sure
                // this net can be routed from this site.
                net_used_out_of_site = true;
                break;
            }

            if (!site_info->is_bel_in_site(user.cell->bel)) {
                net_used_out_of_site = true;
                break;
            }
        }

        if (net_used_out_of_site) {
            out_of_site_sinks.push_back(SiteWire::make(site_info, PORT_IN, net));
            net_info.users.emplace(out_of_site_sinks.back());
        }
    }

    // At this point all nets have a driver SiteWire, but user SiteWire's
    // within the site are not present.  Add them now.
    for (auto &net_pair : nets) {
        NetInfo *net = net_pair.first;
        SiteNetInfo &net_info = net_pair.second;

        for (const PortRef &user : net->users) {
            if (!site_info->is_bel_in_site(user.cell->bel)) {
                // Only care about BELs within the site at this point.
                continue;
            }

            for (IdString bel_pin : ctx->getBelPinsForCellPin(user.cell, user.port)) {
                SiteWire wire = getBelPinWire(user.cell->bel, bel_pin);
                // Don't add users that are trivially routable!
                if (wire != net_info.driver) {
#ifdef DEBUG_SITE_ARCH
                    if (ctx->debug) {
                        log_info("Add user %s because it isn't driver %s\n", nameOfWire(wire),
                                 nameOfWire(net_info.driver));
                    }
#endif
                    net_info.users.emplace(wire);
                }
            }
        }
    }

    IdString vcc_net_name(ctx->chip_info->constants->vcc_net_name);
    NetInfo *vcc_net = ctx->nets.at(vcc_net_name).get();
    auto iter = nets.find(vcc_net);
    if (iter == nets.end() && have_vcc_pins) {
        // VCC net isn't present, add it.
        SiteNetInfo net_info;
        net_info.net = vcc_net;
        net_info.driver.type = SiteWire::OUT_OF_SITE_SOURCE;
        net_info.driver.net = vcc_net;
        auto result = nets.emplace(vcc_net, net_info);
        NPNR_ASSERT(result.second);
        iter = result.first;
    }

    for (CellInfo *cell : site_info->cells_in_site) {
        for (IdString vcc_pin : cell->lut_cell.vcc_pins) {
            SiteWire wire = getBelPinWire(cell->bel, vcc_pin);
            iter->second.users.emplace(wire);
        }
    }

    for (auto &net_pair : nets) {
        SiteNetInfo *net_info = &net_pair.second;
        auto result = wire_to_nets.emplace(net_info->driver, SiteNetMap{net_info, 1});
        // By this point, trivial congestion at sources should already by
        // avoided, and there should be no duplicates in the
        // driver/users data.
        NPNR_ASSERT(result.second);

        for (const auto &user : net_info->users) {
            result = wire_to_nets.emplace(user, SiteNetMap{net_info, 1});
            NPNR_ASSERT(result.second);
        }
    }

    blocking_net.name = ctx->id("$nextpnr_blocked_net");
    blocking_site_net.net = &blocking_net;
}

const char *SiteArch::nameOfWire(const SiteWire &wire) const
{
    switch (wire.type) {
    case SiteWire::SITE_WIRE:
        return ctx->nameOfWire(wire.wire);
    case SiteWire::SITE_PORT_SINK:
        return ctx->nameOfWire(wire.wire);
    case SiteWire::SITE_PORT_SOURCE:
        return ctx->nameOfWire(wire.wire);
    case SiteWire::OUT_OF_SITE_SOURCE: {
        std::string &str = ctx->log_strs.next();
        str = stringf("Out of site source for net %s", wire.net->name.c_str(ctx));
        return str.c_str();
    }
    case SiteWire::OUT_OF_SITE_SINK: {
        std::string &str = ctx->log_strs.next();
        str = stringf("Out of sink source for net %s", wire.net->name.c_str(ctx));
        return str.c_str();
    }
    default:
        // Unreachable!
        NPNR_ASSERT(false);
    }
}

const char *SiteArch::nameOfPip(const SitePip &pip) const
{
    switch (pip.type) {
    case SitePip::SITE_PIP:
        return ctx->nameOfPip(pip.pip);
    case SitePip::SITE_PORT:
        return ctx->nameOfPip(pip.pip);
    case SitePip::SOURCE_TO_SITE_PORT: {
        std::string &str = ctx->log_strs.next();
        str = stringf("Out of site source for net %s => %s", pip.wire.net->name.c_str(ctx),
                      ctx->nameOfWire(ctx->getPipSrcWire(pip.pip)));
        return str.c_str();
    }
    case SitePip::SITE_PORT_TO_SINK: {
        std::string &str = ctx->log_strs.next();
        str = stringf("%s => Out of site sink for net %s", ctx->nameOfWire(ctx->getPipDstWire(pip.pip)),
                      pip.wire.net->name.c_str(ctx));
        return str.c_str();
    }
    case SitePip::SITE_PORT_TO_SITE_PORT: {
        std::string &str = ctx->log_strs.next();
        str = stringf("%s => %s", ctx->nameOfWire(ctx->getPipSrcWire(pip.pip)),
                      ctx->nameOfWire(ctx->getPipDstWire(pip.other_pip)));
        return str.c_str();
    }
    default:
        // Unreachable!
        NPNR_ASSERT(false);
    }
}

const char *SiteArch::nameOfNet(const SiteNetInfo *net) const { return net->net->name.c_str(ctx); }

bool SiteArch::debug() const { return ctx->debug; }

SitePipUphillRange::SitePipUphillRange(const SiteArch *site_arch, SiteWire site_wire)
        : site_arch(site_arch), site_wire(site_wire)
{
    switch (site_wire.type) {
    case SiteWire::SITE_WIRE:
        pip_range = site_arch->ctx->getPipsUphill(site_wire.wire);
        break;
    case SiteWire::OUT_OF_SITE_SOURCE:
        // No normal pips!
        break;
    case SiteWire::OUT_OF_SITE_SINK:
        // No normal pips!
        break;
    case SiteWire::SITE_PORT_SINK:
        // No normal pips!
        break;
    case SiteWire::SITE_PORT_SOURCE:
        // No normal pips!
        break;
    default:
        // Unreachable!
        NPNR_ASSERT(false);
    }
}

SitePip SitePipUphillIterator::operator*() const
{
    switch (state) {
    case NORMAL_PIPS:
        return SitePip::make(site_arch->site_info, *iter);
    case PORT_SRC_TO_PORT_SINK:
        return SitePip::make(site_arch->site_info, site_arch->output_site_ports.at(cursor), site_wire.pip);
    case OUT_OF_SITE_SOURCES:
        return SitePip::make(site_arch->site_info, site_arch->out_of_site_sources.at(cursor), site_wire.pip);
    case OUT_OF_SITE_SINK_TO_PORT_SINK:
        return SitePip::make(site_arch->site_info, site_arch->output_site_ports.at(cursor), site_wire);
    case SITE_PORT:
        return SitePip::make(site_arch->site_info, site_wire.pip);
    default:
        // Unreachable!
        NPNR_ASSERT(false);
    }
}

SiteWire SiteWireIterator::operator*() const
{
    WireId wire;
    PipId pip;
    SiteWire site_wire;
    switch (state) {
    case NORMAL_WIRES:
        wire.tile = site_arch->site_info->tile;
        wire.index = cursor;
        return SiteWire::make(site_arch->site_info, wire);
    case INPUT_SITE_PORTS:
        pip = site_arch->input_site_ports.at(cursor);
        site_wire = SiteWire::make_site_port(site_arch->site_info, pip, /*dst_wire=*/false);
        NPNR_ASSERT(site_wire.type == SiteWire::SITE_PORT_SOURCE);
        return site_wire;
    case OUTPUT_SITE_PORTS:
        pip = site_arch->output_site_ports.at(cursor);
        site_wire = SiteWire::make_site_port(site_arch->site_info, pip, /*dst_wire=*/true);
        NPNR_ASSERT(site_wire.type == SiteWire::SITE_PORT_SINK);
        return site_wire;
    case OUT_OF_SITE_SOURCES:
        return site_arch->out_of_site_sources.at(cursor);
    case OUT_OF_SITE_SINKS:
        return site_arch->out_of_site_sinks.at(cursor);
    default:
        // Unreachable!
        NPNR_ASSERT(false);
    }
}

SiteWireIterator SiteWireRange::begin() const
{
    SiteWireIterator b;

    b.state = SiteWireIterator::BEGIN;
    b.site_arch = site_arch;
    b.tile_type = &loc_info(&site_arch->site_info->chip_info(), *site_arch->site_info);

    ++b;
    return b;
}

NEXTPNR_NAMESPACE_END