diff options
author | Clifford Wolf <clifford@clifford.at> | 2018-06-09 18:19:20 +0200 |
---|---|---|
committer | Clifford Wolf <clifford@clifford.at> | 2018-06-09 18:19:20 +0200 |
commit | dfbfbf87db6e0fc68d541593b2221db4d5c349f9 (patch) | |
tree | 665a111ab708ef482c5a2e66da089edafa9ef4ae /common | |
parent | 208d3783225e1de6d95650c37f0b0ee69f793f42 (diff) | |
download | nextpnr-dfbfbf87db6e0fc68d541593b2221db4d5c349f9.tar.gz nextpnr-dfbfbf87db6e0fc68d541593b2221db4d5c349f9.tar.bz2 nextpnr-dfbfbf87db6e0fc68d541593b2221db4d5c349f9.zip |
Add very basic router
Signed-off-by: Clifford Wolf <clifford@clifford.at>
Diffstat (limited to 'common')
-rw-r--r-- | common/design.h | 6 | ||||
-rw-r--r-- | common/route.cc | 171 | ||||
-rw-r--r-- | common/route.h | 27 |
3 files changed, 201 insertions, 3 deletions
diff --git a/common/design.h b/common/design.h index f4c24f15..1591e0f2 100644 --- a/common/design.h +++ b/common/design.h @@ -74,7 +74,7 @@ struct CellInfo; struct PortRef { - CellInfo *cell; + CellInfo *cell = nullptr; IdString port; }; @@ -85,8 +85,8 @@ struct NetInfo vector<PortRef> users; dict<IdString, std::string> attrs; - // wire -> (uphill_wire, delay) - dict<WireId, std::pair<WireId, DelayInfo>> wires; + // wire -> uphill_pip + dict<WireId, PipId> wires; }; enum PortType diff --git a/common/route.cc b/common/route.cc new file mode 100644 index 00000000..28a51bc6 --- /dev/null +++ b/common/route.cc @@ -0,0 +1,171 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf <clifford@clifford.at> + * + * 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 <queue> + +#include "log.h" +#include "route.h" + +struct QueuedWire +{ + WireId wire; + PipId pip; + DelayInfo delay; +}; + +namespace std { +template <> struct greater<QueuedWire> +{ + bool operator()(const QueuedWire &lhs, const QueuedWire &rhs) const noexcept + { + return lhs.delay.avgDelay() > rhs.delay.avgDelay(); + } +}; +} + +void route_design(Design *design) +{ + auto &chip = design->chip; + + for (auto &net_it : design->nets) { + auto net_name = net_it.first; + auto net_info = net_it.second; + + if (net_info->driver.cell == nullptr) + continue; + + log("Routing net %s.\n", net_name.c_str()); + + log(" Source: %s.%s.\n", net_info->driver.cell->name.c_str(), + net_info->driver.port.c_str()); + + auto src_bel = net_info->driver.cell->bel; + + if (src_bel == BelId()) + log_error("Source cell is not mapped to a bel.\n"); + + log(" Source bel: %s\n", chip.getBelName(src_bel).c_str()); + + auto src_wire = chip.getWireBelPin( + src_bel, portPinFromId(net_info->driver.port)); + + if (src_wire == WireId()) + log_error("No wire found for port %s on source bel.\n", + net_info->driver.port.c_str()); + + log(" Source wire: %s\n", chip.getWireName(src_wire).c_str()); + + dict<WireId, DelayInfo> src_wires; + src_wires[src_wire] = DelayInfo(); + net_info->wires[src_wire] = PipId(); + chip.bindWire(src_wire, net_name); + + for (auto &user_it : net_info->users) { + log(" Route to: %s.%s.\n", user_it.cell->name.c_str(), + user_it.port.c_str()); + + auto dst_bel = user_it.cell->bel; + + if (dst_bel == BelId()) + log_error("Destination cell is not mapped to a bel.\n"); + + log(" Destination bel: %s\n", chip.getBelName(dst_bel).c_str()); + + auto dst_wire = + chip.getWireBelPin(dst_bel, portPinFromId(user_it.port)); + + if (dst_wire == WireId()) + log_error("No wire found for port %s on destination bel.\n", + user_it.port.c_str()); + + log(" Destination wire: %s\n", + chip.getWireName(dst_wire).c_str()); + + dict<WireId, QueuedWire> visited; + std::priority_queue<QueuedWire, std::vector<QueuedWire>, + std::greater<QueuedWire>> + queue; + + for (auto &it : src_wires) { + QueuedWire qw; + qw.wire = it.first; + qw.pip = PipId(); + qw.delay = it.second; + + queue.push(qw); + visited[qw.wire] = qw; + } + + while (!queue.empty()) { + QueuedWire qw = queue.top(); + queue.pop(); + + for (auto pip : chip.getPipsDownhill(qw.wire)) { + if (!chip.checkPipAvail(pip)) + continue; + + WireId next_wire = chip.getPipDstWire(pip); + + if (visited.count(next_wire) || + !chip.checkWireAvail(next_wire)) + continue; + + QueuedWire next_qw; + next_qw.wire = next_wire; + next_qw.pip = pip; + next_qw.delay = qw.delay + chip.getPipDelay(pip); + visited[next_qw.wire] = next_qw; + queue.push(next_qw); + + if (next_qw.wire == dst_wire) { + std::priority_queue<QueuedWire, std::vector<QueuedWire>, + std::greater<QueuedWire>> + empty_queue; + std::swap(queue, empty_queue); + break; + } + } + } + + if (visited.count(dst_wire) == 0) + log_error("Failed to route %s -> %s.\n", + chip.getWireName(src_wire).c_str(), + chip.getWireName(dst_wire).c_str()); + + log(" Route (from destination to source):\n"); + + WireId cursor = dst_wire; + + while (1) { + log(" %8.2f %s\n", visited[cursor].delay.avgDelay(), + chip.getWireName(cursor).c_str()); + + if (src_wires.count(cursor)) + break; + + net_info->wires[cursor] = visited[cursor].pip; + chip.bindWire(cursor, net_name); + chip.bindPip(visited[cursor].pip, net_name); + + src_wires[cursor] = visited[cursor].delay; + cursor = chip.getPipSrcWire(visited[cursor].pip); + } + } + } +} diff --git a/common/route.h b/common/route.h new file mode 100644 index 00000000..5ecbd823 --- /dev/null +++ b/common/route.h @@ -0,0 +1,27 @@ +/* + * nextpnr -- Next Generation Place and Route + * + * Copyright (C) 2018 Clifford Wolf <clifford@clifford.at> + * + * 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. + * + */ + +#ifndef ROUTE_H +#define ROUTE_H + +#include "design.h" + +extern void route_design(Design *design); + +#endif // ROUTE_H |