diff options
Diffstat (limited to 'common/context.cc')
| -rw-r--r-- | common/context.cc | 409 |
1 files changed, 409 insertions, 0 deletions
diff --git a/common/context.cc b/common/context.cc new file mode 100644 index 00000000..c85f40de --- /dev/null +++ b/common/context.cc @@ -0,0 +1,409 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf <clifford@symbioticeda.com> + * + * 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 "context.h" + +#include "nextpnr_namespaces.h" +#include "log.h" +#include "util.h" + +NEXTPNR_NAMESPACE_BEGIN + +WireId Context::getNetinfoSourceWire(const NetInfo *net_info) const +{ + if (net_info->driver.cell == nullptr) + return WireId(); + + auto src_bel = net_info->driver.cell->bel; + + if (src_bel == BelId()) + return WireId(); + + auto bel_pins = getBelPinsForCellPin(net_info->driver.cell, net_info->driver.port); + auto iter = bel_pins.begin(); + if (iter == bel_pins.end()) + return WireId(); + WireId driver = getBelPinWire(src_bel, *iter); + ++iter; + NPNR_ASSERT(iter == bel_pins.end()); // assert there is only one driver bel pin; + return driver; +} + +SSOArray<WireId, 2> Context::getNetinfoSinkWires(const NetInfo *net_info, const PortRef &user_info) const +{ + auto dst_bel = user_info.cell->bel; + if (dst_bel == BelId()) + return SSOArray<WireId, 2>(0, WireId()); + size_t bel_pin_count = 0; + // We use an SSOArray here because it avoids any heap allocation for the 99.9% case of 1 or 2 sink wires + // but as SSOArray doesn't (currently) support resizing to keep things simple it does mean we have to do + // two loops + for (auto s : getBelPinsForCellPin(user_info.cell, user_info.port)) { + (void)s; // unused + ++bel_pin_count; + } + SSOArray<WireId, 2> result(bel_pin_count, WireId()); + bel_pin_count = 0; + for (auto pin : getBelPinsForCellPin(user_info.cell, user_info.port)) { + result[bel_pin_count++] = getBelPinWire(dst_bel, pin); + } + return result; +} + +size_t Context::getNetinfoSinkWireCount(const NetInfo *net_info, const PortRef &sink) const +{ + size_t count = 0; + for (auto s : getNetinfoSinkWires(net_info, sink)) { + (void)s; // unused + ++count; + } + return count; +} + +WireId Context::getNetinfoSinkWire(const NetInfo *net_info, const PortRef &sink, size_t phys_idx) const +{ + size_t count = 0; + for (auto s : getNetinfoSinkWires(net_info, sink)) { + if (count == phys_idx) + return s; + ++count; + } + /* TODO: This should be an assertion failure, but for the zero-wire case of unplaced sinks; legacy code currently + assumes WireId Remove once the refactoring process is complete. + */ + return WireId(); +} + +delay_t Context::getNetinfoRouteDelay(const NetInfo *net_info, const PortRef &user_info) const +{ +#ifdef ARCH_ECP5 + if (net_info->is_global) + return 0; +#endif + + if (net_info->wires.empty()) + return predictDelay(net_info, user_info); + + WireId src_wire = getNetinfoSourceWire(net_info); + if (src_wire == WireId()) + return 0; + + delay_t max_delay = 0; + + for (auto dst_wire : getNetinfoSinkWires(net_info, user_info)) { + WireId cursor = dst_wire; + delay_t delay = 0; + + while (cursor != WireId() && cursor != src_wire) { + auto it = net_info->wires.find(cursor); + + if (it == net_info->wires.end()) + break; + + PipId pip = it->second.pip; + if (pip == PipId()) + break; + + delay += getPipDelay(pip).maxDelay(); + delay += getWireDelay(cursor).maxDelay(); + cursor = getPipSrcWire(pip); + } + + if (cursor == src_wire) + max_delay = std::max(max_delay, delay + getWireDelay(src_wire).maxDelay()); // routed + else + max_delay = std::max(max_delay, predictDelay(net_info, user_info)); // unrouted + } + return max_delay; +} + +static uint32_t xorshift32(uint32_t x) +{ + x ^= x << 13; + x ^= x >> 17; + x ^= x << 5; + return x; +} + +uint32_t Context::checksum() const +{ + uint32_t cksum = xorshift32(123456789); + + uint32_t cksum_nets_sum = 0; + for (auto &it : nets) { + auto &ni = *it.second; + uint32_t x = 123456789; + x = xorshift32(x + xorshift32(it.first.index)); + x = xorshift32(x + xorshift32(ni.name.index)); + if (ni.driver.cell) + x = xorshift32(x + xorshift32(ni.driver.cell->name.index)); + x = xorshift32(x + xorshift32(ni.driver.port.index)); + x = xorshift32(x + xorshift32(getDelayChecksum(ni.driver.budget))); + + for (auto &u : ni.users) { + if (u.cell) + x = xorshift32(x + xorshift32(u.cell->name.index)); + x = xorshift32(x + xorshift32(u.port.index)); + x = xorshift32(x + xorshift32(getDelayChecksum(u.budget))); + } + + uint32_t attr_x_sum = 0; + for (auto &a : ni.attrs) { + uint32_t attr_x = 123456789; + attr_x = xorshift32(attr_x + xorshift32(a.first.index)); + for (char ch : a.second.str) + attr_x = xorshift32(attr_x + xorshift32((int)ch)); + attr_x_sum += attr_x; + } + x = xorshift32(x + xorshift32(attr_x_sum)); + + uint32_t wire_x_sum = 0; + for (auto &w : ni.wires) { + uint32_t wire_x = 123456789; + wire_x = xorshift32(wire_x + xorshift32(getWireChecksum(w.first))); + wire_x = xorshift32(wire_x + xorshift32(getPipChecksum(w.second.pip))); + wire_x = xorshift32(wire_x + xorshift32(int(w.second.strength))); + wire_x_sum += wire_x; + } + x = xorshift32(x + xorshift32(wire_x_sum)); + + cksum_nets_sum += x; + } + cksum = xorshift32(cksum + xorshift32(cksum_nets_sum)); + + uint32_t cksum_cells_sum = 0; + for (auto &it : cells) { + auto &ci = *it.second; + uint32_t x = 123456789; + x = xorshift32(x + xorshift32(it.first.index)); + x = xorshift32(x + xorshift32(ci.name.index)); + x = xorshift32(x + xorshift32(ci.type.index)); + + uint32_t port_x_sum = 0; + for (auto &p : ci.ports) { + uint32_t port_x = 123456789; + port_x = xorshift32(port_x + xorshift32(p.first.index)); + port_x = xorshift32(port_x + xorshift32(p.second.name.index)); + if (p.second.net) + port_x = xorshift32(port_x + xorshift32(p.second.net->name.index)); + port_x = xorshift32(port_x + xorshift32(p.second.type)); + port_x_sum += port_x; + } + x = xorshift32(x + xorshift32(port_x_sum)); + + uint32_t attr_x_sum = 0; + for (auto &a : ci.attrs) { + uint32_t attr_x = 123456789; + attr_x = xorshift32(attr_x + xorshift32(a.first.index)); + for (char ch : a.second.str) + attr_x = xorshift32(attr_x + xorshift32((int)ch)); + attr_x_sum += attr_x; + } + x = xorshift32(x + xorshift32(attr_x_sum)); + + uint32_t param_x_sum = 0; + for (auto &p : ci.params) { + uint32_t param_x = 123456789; + param_x = xorshift32(param_x + xorshift32(p.first.index)); + for (char ch : p.second.str) + param_x = xorshift32(param_x + xorshift32((int)ch)); + param_x_sum += param_x; + } + x = xorshift32(x + xorshift32(param_x_sum)); + + x = xorshift32(x + xorshift32(getBelChecksum(ci.bel))); + x = xorshift32(x + xorshift32(ci.belStrength)); + + cksum_cells_sum += x; + } + cksum = xorshift32(cksum + xorshift32(cksum_cells_sum)); + + return cksum; +} + +void Context::check() const +{ + bool check_failed = false; + +#define CHECK_FAIL(...) \ + do { \ + log_nonfatal_error(__VA_ARGS__); \ + check_failed = true; \ + } while (false) + + for (auto &n : nets) { + auto ni = n.second.get(); + if (n.first != ni->name) + CHECK_FAIL("net key '%s' not equal to name '%s'\n", nameOf(n.first), nameOf(ni->name)); + for (auto &w : ni->wires) { + if (ni != getBoundWireNet(w.first)) + CHECK_FAIL("net '%s' not bound to wire '%s' in wires map\n", nameOf(n.first), nameOfWire(w.first)); + if (w.second.pip != PipId()) { + if (w.first != getPipDstWire(w.second.pip)) + CHECK_FAIL("net '%s' has dest mismatch '%s' vs '%s' in for pip '%s'\n", nameOf(n.first), + nameOfWire(w.first), nameOfWire(getPipDstWire(w.second.pip)), nameOfPip(w.second.pip)); + if (ni != getBoundPipNet(w.second.pip)) + CHECK_FAIL("net '%s' not bound to pip '%s' in wires map\n", nameOf(n.first), + nameOfPip(w.second.pip)); + } + } + if (ni->driver.cell != nullptr) { + if (!ni->driver.cell->ports.count(ni->driver.port)) { + CHECK_FAIL("net '%s' driver port '%s' missing on cell '%s'\n", nameOf(n.first), nameOf(ni->driver.port), + nameOf(ni->driver.cell)); + } else { + const NetInfo *p_net = ni->driver.cell->ports.at(ni->driver.port).net; + if (p_net != ni) + CHECK_FAIL("net '%s' driver port '%s.%s' connected to incorrect net '%s'\n", nameOf(n.first), + nameOf(ni->driver.cell), nameOf(ni->driver.port), p_net ? nameOf(p_net) : "<nullptr>"); + } + } + for (auto user : ni->users) { + if (!user.cell->ports.count(user.port)) { + CHECK_FAIL("net '%s' user port '%s' missing on cell '%s'\n", nameOf(n.first), nameOf(user.port), + nameOf(user.cell)); + } else { + const NetInfo *p_net = user.cell->ports.at(user.port).net; + if (p_net != ni) + CHECK_FAIL("net '%s' user port '%s.%s' connected to incorrect net '%s'\n", nameOf(n.first), + nameOf(user.cell), nameOf(user.port), p_net ? nameOf(p_net) : "<nullptr>"); + } + } + } +#ifdef CHECK_WIRES + for (auto w : getWires()) { + auto ni = getBoundWireNet(w); + if (ni != nullptr) { + if (!ni->wires.count(w)) + CHECK_FAIL("wire '%s' missing in wires map of bound net '%s'\n", nameOfWire(w), nameOf(ni)); + } + } +#endif + for (auto &c : cells) { + auto ci = c.second.get(); + if (c.first != ci->name) + CHECK_FAIL("cell key '%s' not equal to name '%s'\n", nameOf(c.first), nameOf(ci->name)); + if (ci->bel != BelId()) { + if (getBoundBelCell(c.second->bel) != ci) + CHECK_FAIL("cell '%s' not bound to bel '%s' in bel field\n", nameOf(c.first), nameOfBel(ci->bel)); + } + for (auto &port : c.second->ports) { + NetInfo *net = port.second.net; + if (net != nullptr) { + if (nets.find(net->name) == nets.end()) { + CHECK_FAIL("cell port '%s.%s' connected to non-existent net '%s'\n", nameOf(c.first), + nameOf(port.first), nameOf(net->name)); + } else if (port.second.type == PORT_OUT) { + if (net->driver.cell != c.second.get() || net->driver.port != port.first) { + CHECK_FAIL("output cell port '%s.%s' not in driver field of net '%s'\n", nameOf(c.first), + nameOf(port.first), nameOf(net)); + } + } else if (port.second.type == PORT_IN) { + int usr_count = std::count_if(net->users.begin(), net->users.end(), [&](const PortRef &pr) { + return pr.cell == c.second.get() && pr.port == port.first; + }); + if (usr_count != 1) + CHECK_FAIL("input cell port '%s.%s' appears %d rather than expected 1 times in users vector of " + "net '%s'\n", + nameOf(c.first), nameOf(port.first), usr_count, nameOf(net)); + } + } + } + } + +#undef CHECK_FAIL + + if (check_failed) + log_error("INTERNAL CHECK FAILED: please report this error with the design and full log output. Failure " + "details are above this message.\n"); +} + +namespace { +struct FixupHierarchyWorker +{ + FixupHierarchyWorker(Context *ctx) : ctx(ctx){}; + Context *ctx; + void run() + { + trim_hierarchy(ctx->top_module); + rebuild_hierarchy(); + }; + // Remove cells and nets that no longer exist in the netlist + std::vector<IdString> todelete_cells, todelete_nets; + void trim_hierarchy(IdString path) + { + auto &h = ctx->hierarchy.at(path); + todelete_cells.clear(); + todelete_nets.clear(); + for (auto &lc : h.leaf_cells) { + if (!ctx->cells.count(lc.second)) + todelete_cells.push_back(lc.first); + } + for (auto &n : h.nets) + if (!ctx->nets.count(n.second)) + todelete_nets.push_back(n.first); + for (auto tdc : todelete_cells) { + h.leaf_cells_by_gname.erase(h.leaf_cells.at(tdc)); + h.leaf_cells.erase(tdc); + } + for (auto tdn : todelete_nets) { + h.nets_by_gname.erase(h.nets.at(tdn)); + h.nets.erase(tdn); + } + for (auto &sc : h.hier_cells) + trim_hierarchy(sc.second); + } + + IdString construct_local_name(HierarchicalCell &hc, IdString global_name, bool is_cell) + { + std::string gn = global_name.str(ctx); + auto dp = gn.find_last_of('.'); + if (dp != std::string::npos) + gn = gn.substr(dp + 1); + IdString name = ctx->id(gn); + // Make sure name is unique + int adder = 0; + while (is_cell ? hc.leaf_cells.count(name) : hc.nets.count(name)) { + ++adder; + name = ctx->id(gn + "$" + std::to_string(adder)); + } + return name; + } + + // Update hierarchy structure for nets and cells that have hiercell set + void rebuild_hierarchy() + { + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (ci->hierpath == IdString()) + ci->hierpath = ctx->top_module; + auto &hc = ctx->hierarchy.at(ci->hierpath); + if (hc.leaf_cells_by_gname.count(ci->name)) + continue; // already known + IdString local_name = construct_local_name(hc, ci->name, true); + hc.leaf_cells_by_gname[ci->name] = local_name; + hc.leaf_cells[local_name] = ci->name; + } + } +}; +} // namespace + +void Context::fixupHierarchy() { FixupHierarchyWorker(this).run(); } + +NEXTPNR_NAMESPACE_END |