diff options
| -rw-r--r-- | common/design.h | 6 | ||||
| -rw-r--r-- | common/route.cc | 171 | ||||
| -rw-r--r-- | common/route.h | 27 | ||||
| -rw-r--r-- | dummy/chip.h | 27 | ||||
| -rw-r--r-- | ice40/chip.cc | 35 | ||||
| -rw-r--r-- | ice40/chip.h | 106 | ||||
| -rw-r--r-- | ice40/chipdb.py | 34 | ||||
| -rw-r--r-- | ice40/main.cc | 2 | ||||
| -rw-r--r-- | ice40/portpins.inc | 8 |
9 files changed, 370 insertions, 46 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 diff --git a/dummy/chip.h b/dummy/chip.h index 8c66fb96..5c13298b 100644 --- a/dummy/chip.h +++ b/dummy/chip.h @@ -26,8 +26,16 @@ struct DelayInfo { float delay = 0; - float raiseDelay() { return delay; } - float fallDelay() { return delay; } + float raiseDelay() const { return delay; } + float fallDelay() const { return delay; } + float avgDelay() const { return delay; } + + DelayInfo operator+(const DelayInfo &other) const + { + DelayInfo ret; + ret.delay = this->delay + other.delay; + return ret; + } }; typedef IdString BelType; @@ -63,6 +71,7 @@ struct Chip void bindBel(BelId bel, IdString cell); void unbindBel(BelId bel); bool checkBelAvail(BelId bel) const; + IdString getBelCell(BelId bel) const; const vector<BelId> &getBels() const; const vector<BelId> &getBelsByType(BelType type) const; BelType getBelType(BelId bel) const; @@ -72,16 +81,18 @@ struct Chip WireId getWireByName(IdString name) const; IdString getWireName(WireId wire) const; - void bindWire(WireId bel, IdString net); - void unbindWire(WireId bel); - bool checkWireAvail(WireId bel) const; + void bindWire(WireId wire, IdString net); + void unbindWire(WireId wire); + bool checkWireAvail(WireId wire) const; + IdString getWireNet(WireId wire) const; const vector<WireId> &getWires() const; PipId getPipByName(IdString name) const; IdString getPipName(PipId pip) const; - void bindPip(PipId bel, IdString net); - void unbindPip(PipId bel); - bool checkPipAvail(PipId bel) const; + void bindPip(PipId pip, IdString net); + void unbindPip(PipId pip); + bool checkPipAvail(PipId pip) const; + IdString getPipNet(PipId pip) const; const vector<PipId> &getPips() const; WireId getPipSrcWire(PipId pip) const; WireId getPipDstWire(PipId pip) const; diff --git a/ice40/chip.cc b/ice40/chip.cc index ed79be0b..9c6d7a1a 100644 --- a/ice40/chip.cc +++ b/ice40/chip.cc @@ -18,6 +18,7 @@ */ #include "chip.h" +#include "log.h" // ----------------------------------------------------------------------- @@ -45,7 +46,7 @@ BelType belTypeFromId(IdString id) // ----------------------------------------------------------------------- -IdString PortPinToId(PortPin type) +IdString portPinToId(PortPin type) { #define X(t) \ if (type == PIN_##t) \ @@ -57,7 +58,7 @@ IdString PortPinToId(PortPin type) return IdString(); } -PortPin PortPinFromId(IdString id) +PortPin portPinFromId(IdString id) { #define X(t) \ if (id == #t) \ @@ -76,28 +77,26 @@ Chip::Chip(ChipArgs args) #ifdef ICE40_HX1K_ONLY if (args.type == ChipArgs::HX1K) { chip_info = chip_info_1k; - return; + } else { + log_error("Unsupported iCE40 chip type.\n"); } #else if (args.type == ChipArgs::LP384) { chip_info = chip_info_384; - return; } else if (args.type == ChipArgs::LP1K || args.type == ChipArgs::HX1K) { chip_info = chip_info_1k; - return; } else if (args.type == ChipArgs::UP5K) { chip_info = chip_info_5k; - return; } else if (args.type == ChipArgs::LP8K || args.type == ChipArgs::HX8K) { chip_info = chip_info_8k; - return; } else { - fprintf(stderr, "Unsupported chip type\n"); - exit(EXIT_FAILURE); + log_error("Unsupported iCE40 chip type.\n"); } #endif - abort(); + bel_to_cell.resize(chip_info.num_bels); + wire_to_net.resize(chip_info.num_wires); + pip_to_net.resize(chip_info.num_pips); } // ----------------------------------------------------------------------- @@ -120,8 +119,20 @@ BelId Chip::getBelByName(IdString name) const WireId Chip::getWireBelPin(BelId bel, PortPin pin) const { - // FIXME - return WireId(); + WireId ret; + + assert(!bel.nil()); + + int num_bel_wires = chip_info.bel_data[bel.index].num_bel_wires; + BelWirePOD *bel_wires = chip_info.bel_data[bel.index].bel_wires; + + for (int i = 0; i < num_bel_wires; i++) + if (bel_wires[i].port == pin) { + ret.index = bel_wires[i].wire_index; + break; + } + + return ret; } // ----------------------------------------------------------------------- diff --git a/ice40/chip.h b/ice40/chip.h index 3125b17f..87a65b2d 100644 --- a/ice40/chip.h +++ b/ice40/chip.h @@ -26,8 +26,16 @@ struct DelayInfo { float delay = 0; - float raiseDelay() { return delay; } - float fallDelay() { return delay; } + float raiseDelay() const { return delay; } + float fallDelay() const { return delay; } + float avgDelay() const { return delay; } + + DelayInfo operator+(const DelayInfo &other) const + { + DelayInfo ret; + ret.delay = this->delay + other.delay; + return ret; + } }; // ----------------------------------------------------------------------- @@ -51,15 +59,23 @@ enum PortPin #undef X }; -IdString PortPinToId(PortPin type); -PortPin PortPinFromId(IdString id); +IdString portPinToId(PortPin type); +PortPin portPinFromId(IdString id); // ----------------------------------------------------------------------- +struct BelWirePOD +{ + int32_t wire_index; + PortPin port; +}; + struct BelInfoPOD { const char *name; BelType type; + int num_bel_wires; + BelWirePOD *bel_wires; int8_t x, y, z; }; @@ -343,6 +359,10 @@ struct Chip mutable dict<IdString, int> wire_by_name; mutable dict<IdString, int> pip_by_name; + vector<IdString> bel_to_cell; + vector<IdString> wire_to_net; + vector<IdString> pip_to_net; + Chip(ChipArgs args); // ------------------------------------------------- @@ -355,11 +375,31 @@ struct Chip return chip_info.bel_data[bel.index].name; } - void bindBel(BelId bel, IdString cell) {} + void bindBel(BelId bel, IdString cell) + { + assert(!bel.nil()); + assert(bel_to_cell[bel.index] == IdString()); + bel_to_cell[bel.index] = cell; + } + + void unbindBel(BelId bel) + { + assert(!bel.nil()); + assert(bel_to_cell[bel.index] != IdString()); + bel_to_cell[bel.index] = IdString(); + } - void unbindBel(BelId bel) {} + bool checkBelAvail(BelId bel) const + { + assert(!bel.nil()); + return bel_to_cell[bel.index] == IdString(); + } - bool checkBelAvail(BelId bel) const {} + IdString getBelCell(BelId bel) const + { + assert(!bel.nil()); + return bel_to_cell[bel.index]; + } BelRange getBels() const { @@ -425,11 +465,31 @@ struct Chip return chip_info.wire_data[wire.index].name; } - void bindWire(WireId bel, IdString net) {} + void bindWire(WireId wire, IdString net) + { + assert(!wire.nil()); + assert(wire_to_net[wire.index] == IdString()); + wire_to_net[wire.index] = net; + } + + void unbindWire(WireId wire) + { + assert(!wire.nil()); + assert(wire_to_net[wire.index] != IdString()); + wire_to_net[wire.index] = IdString(); + } - void unbindWire(WireId bel) {} + bool checkWireAvail(WireId wire) const + { + assert(!wire.nil()); + return wire_to_net[wire.index] == IdString(); + } - bool checkWireAvail(WireId bel) const {} + IdString getWireNet(WireId wire) const + { + assert(!wire.nil()); + return wire_to_net[wire.index]; + } WireRange getWires() const { @@ -453,11 +513,31 @@ struct Chip return src_name + "->" + dst_name; } - void bindPip(PipId bel, IdString net) {} + void bindPip(PipId pip, IdString net) + { + assert(!pip.nil()); + assert(pip_to_net[pip.index] == IdString()); + pip_to_net[pip.index] = net; + } + + void unbindPip(PipId pip) + { + assert(!pip.nil()); + assert(pip_to_net[pip.index] != IdString()); + pip_to_net[pip.index] = IdString(); + } - void unbindPip(PipId bel) {} + bool checkPipAvail(PipId pip) const + { + assert(!pip.nil()); + return pip_to_net[pip.index] == IdString(); + } - bool checkPipAvail(PipId bel) const {} + IdString getPipNet(PipId pip) const + { + assert(!pip.nil()); + return pip_to_net[pip.index]; + } AllPipRange getPips() const { diff --git a/ice40/chipdb.py b/ice40/chipdb.py index 58dd0dd2..7b1ba93a 100644 --- a/ice40/chipdb.py +++ b/ice40/chipdb.py @@ -1,6 +1,7 @@ #!/usr/bin/env python3 import sys +import re dev_name = None dev_width = None @@ -16,6 +17,7 @@ pip_xy = dict() bel_name = list() bel_type = list() bel_pos = list() +bel_wires = list() wire_uphill_belport = dict() wire_downhill_belports = dict() @@ -24,7 +26,16 @@ wire_names = dict() wire_names_r = dict() wire_xy = dict() +def maj_wire_name(name): + if re.match(r"lutff_\d/(in|out)", name[2]): + return True + return False + def cmp_wire_names(newname, oldname): + if maj_wire_name(newname): + return True + if maj_wire_name(oldname): + return False return newname < oldname with open(sys.argv[1], "r") as f: @@ -126,16 +137,19 @@ def add_bel_input(bel, wire, port): if wire not in wire_downhill_belports: wire_downhill_belports[wire] = set() wire_downhill_belports[wire].add((bel, port)) + bel_wires[bel].append((wire, port)) def add_bel_output(bel, wire, port): assert wire not in wire_uphill_belport wire_uphill_belport[wire] = (bel, port) + bel_wires[bel].append((wire, port)) def add_bel_lc(x, y, z): bel = len(bel_name) bel_name.append("%d_%d_lc%d" % (x, y, z)) bel_type.append("ICESTORM_LC") bel_pos.append((x, y, z)) + bel_wires.append(list()) wire_cen = wire_names[(x, y, "lutff_global/cen")] wire_clk = wire_names[(x, y, "lutff_global/clk")] @@ -159,10 +173,10 @@ def add_bel_lc(x, y, z): add_bel_input(bel, wire_s_r, "SR") add_bel_input(bel, wire_cin, "CIN") - add_bel_input(bel, wire_in_0, "IN_0") - add_bel_input(bel, wire_in_1, "IN_1") - add_bel_input(bel, wire_in_2, "IN_2") - add_bel_input(bel, wire_in_3, "IN_3") + add_bel_input(bel, wire_in_0, "I0") + add_bel_input(bel, wire_in_1, "I1") + add_bel_input(bel, wire_in_2, "I2") + add_bel_input(bel, wire_in_3, "I3") add_bel_output(bel, wire_out, "O") add_bel_output(bel, wire_cout, "COUT") @@ -175,6 +189,7 @@ def add_bel_io(x, y, z): bel_name.append("%d_%d_lc%d" % (x, y, z)) bel_type.append("SB_IO") bel_pos.append((x, y, z)) + bel_wires.append(list()) wire_cen = wire_names[(x, y, "io_global/cen")] wire_iclk = wire_names[(x, y, "io_global/inclk")] @@ -204,6 +219,7 @@ def add_bel_ram(x, y): bel_name.append("%d_%d_ram" % (x, y)) bel_type.append("ICESTORM_RAM") bel_pos.append((x, y, 0)) + bel_wires.append(list()) if (x, y, "ram/WE") in wire_names: # iCE40 1K-style memories @@ -241,10 +257,16 @@ for tile_xy, tile_type in sorted(tiles.items()): print('#include "chip.h"') +for bel in range(len(bel_name)): + print("BelWirePOD bel_wires_%d[%d] = {" % (bel, len(bel_wires[bel]))) + for i in range(len(bel_wires[bel])): + print(" {%d, PIN_%s}%s" % (bel_wires[bel][i] + ("," if i+1 < len(bel_wires[bel]) else "",))) + print("};") + print("BelInfoPOD bel_data_%s[%d] = {" % (dev_name, len(bel_name))) for bel in range(len(bel_name)): - print(" {\"%s\", TYPE_%s, %d, %d, %d}%s" % (bel_name[bel], bel_type[bel], - bel_pos[bel][0], bel_pos[bel][1], bel_pos[bel][2], + print(" {\"%s\", TYPE_%s, %d, bel_wires_%d, %d, %d, %d}%s" % (bel_name[bel], bel_type[bel], + len(bel_wires[bel]), bel, bel_pos[bel][0], bel_pos[bel][1], bel_pos[bel][2], "," if bel+1 < len(bel_name) else "")) print("};") diff --git a/ice40/main.cc b/ice40/main.cc index 073bbae2..9f909bba 100644 --- a/ice40/main.cc +++ b/ice40/main.cc @@ -29,6 +29,7 @@ #include "mainwindow.h" #include "place.h" #include "pybindings.h" +#include "route.h" #include "version.h" void svg_dump_el(const GraphicElement &el) @@ -247,6 +248,7 @@ int main(int argc, char *argv[]) parse_json_file(f, filename, &design); place_design(&design); + route_design(&design); } if (vm.count("run")) { diff --git a/ice40/portpins.inc b/ice40/portpins.inc index 9eda4bbd..13a22bcc 100644 --- a/ice40/portpins.inc +++ b/ice40/portpins.inc @@ -1,7 +1,7 @@ -X(IN_0) -X(IN_1) -X(IN_2) -X(IN_3) +X(I0) +X(I1) +X(I2) +X(I3) X(O) X(LO) X(CIN) |