aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--common/router1.cc221
-rw-r--r--common/router1.h1
-rw-r--r--docs/archapi.md36
-rw-r--r--ecp5/arch.h15
-rw-r--r--generic/arch.h3
-rw-r--r--gui/designwidget.cc6
-rw-r--r--ice40/arch.h43
7 files changed, 178 insertions, 147 deletions
diff --git a/common/router1.cc b/common/router1.cc
index 6a888c45..64f01c0d 100644
--- a/common/router1.cc
+++ b/common/router1.cc
@@ -99,7 +99,6 @@ struct Router1
std::priority_queue<QueuedWire, std::vector<QueuedWire>, QueuedWire::Greater> queue;
std::unordered_map<WireId, int> wireScores;
- std::unordered_map<PipId, int> pipScores;
std::unordered_map<NetInfo*, int> netScores;
int arcs_with_ripup = 0;
@@ -125,6 +124,9 @@ struct Router1
void arc_queue_insert(const arc_key &arc)
{
+ if (queued_arcs.count(arc))
+ return;
+
NetInfo *net_info = arc.net_info;
int user_idx = arc.user_idx;
@@ -151,10 +153,19 @@ struct Router1
auto net_wires_copy = net->wires;
for (auto &it : net_wires_copy) {
- if (it.second.pip == PipId())
- ripup_wire(it.first, 4);
- else
- ripup_pip(it.second.pip, 4);
+ WireId w = it.first;
+
+ for (auto &it : wire_to_arcs[w]) {
+ arc_to_wires[it].erase(w);
+ arc_queue_insert(it);
+ }
+ wire_to_arcs[w].clear();
+
+ if (ctx->debug)
+ log(" unbind wire %s\n", ctx->getWireName(w).c_str(ctx));
+
+ ctx->unbindWire(w);
+ wireScores[w]++;
}
ripup_flag = true;
@@ -163,64 +174,54 @@ struct Router1
void ripup_wire(WireId wire, int extra_indent = 0)
{
if (ctx->debug)
- log(" %*sripup wire %s\n", extra_indent, "", ctx->getWireName(wire).c_str(ctx));
+ log(" ripup wire %s\n", ctx->getWireName(wire).c_str(ctx));
- wireScores[wire]++;
+ WireId w = ctx->getConflictingWireWire(wire);
- if (ctx->getBoundWireNet(wire)) {
- for (auto &it : wire_to_arcs[wire]) {
- arc_to_wires[it].erase(wire);
+ if (w == WireId()) {
+ NetInfo *n = ctx->getConflictingWireNet(wire);
+ if (n != nullptr)
+ ripup_net(n);
+ } else {
+ for (auto &it : wire_to_arcs[w]) {
+ arc_to_wires[it].erase(w);
arc_queue_insert(it);
}
- wire_to_arcs[wire].clear();
- ctx->unbindWire(wire);
- }
+ wire_to_arcs[w].clear();
- NetInfo *net = ctx->getConflictingWireNet(wire);
- if (net != nullptr) {
- wireScores[wire] += net->wires.size();
- ripup_net(net);
+ if (ctx->debug)
+ log(" unbind wire %s\n", ctx->getWireName(w).c_str(ctx));
+
+ ctx->unbindWire(w);
+ wireScores[w]++;
}
ripup_flag = true;
}
- void ripup_pip(PipId pip, int extra_indent = 0)
+ void ripup_pip(PipId pip)
{
- WireId wire = ctx->getPipDstWire(pip);
-
if (ctx->debug)
- log(" %*sripup pip %s (%s)\n", extra_indent, "", ctx->getPipName(pip).c_str(ctx), ctx->getWireName(wire).c_str(ctx));
-
- pipScores[pip]++;
-
- if (ctx->getBoundPipNet(pip)) {
- ctx->unbindPip(pip);
- goto remove_wire_arcs;
- }
+ log(" ripup pip %s\n", ctx->getPipName(pip).c_str(ctx));
- if (ctx->getBoundWireNet(wire)) {
- ctx->unbindWire(wire);
- goto remove_wire_arcs;
- }
+ WireId w = ctx->getConflictingPipWire(pip);
- if (0) {
-remove_wire_arcs:
- wireScores[wire]++;
- for (auto &it : wire_to_arcs[wire]) {
- arc_to_wires[it].erase(wire);
+ if (w == WireId()) {
+ NetInfo *n = ctx->getConflictingPipNet(pip);
+ if (n != nullptr)
+ ripup_net(n);
+ } else {
+ for (auto &it : wire_to_arcs[w]) {
+ arc_to_wires[it].erase(w);
arc_queue_insert(it);
}
- wire_to_arcs[wire].clear();
- }
+ wire_to_arcs[w].clear();
- NetInfo *net = ctx->getConflictingPipNet(pip);
- if (net != nullptr) {
- wire = ctx->getConflictingPipWire(pip);
- if (wire != WireId())
- ripup_wire(wire, 2);
- else
- ripup_net(net);
+ if (ctx->debug)
+ log(" unbind wire %s\n", ctx->getWireName(w).c_str(ctx));
+
+ ctx->unbindWire(w);
+ wireScores[w]++;
}
ripup_flag = true;
@@ -455,57 +456,80 @@ remove_wire_arcs:
WireId next_wire = ctx->getPipDstWire(pip);
next_delay += ctx->getWireDelay(next_wire).maxDelay();
- if (!ctx->checkWireAvail(next_wire)) {
- NetInfo *ripupWireNet = ctx->getConflictingWireNet(next_wire);
+ WireId conflictWireWire = WireId(), conflictPipWire = WireId();
+ NetInfo *conflictWireNet = nullptr, *conflictPipNet = nullptr;
- if (ripupWireNet == nullptr)
- continue;
+ bool wire_reuse = net_info->wires.count(next_wire);
+ bool pip_reuse = wire_reuse && net_info->wires.at(next_wire).pip == pip;
- if (ripupWireNet == net_info) {
- next_bonus += cfg.wireReuseBonus;
- } else {
- if (!ripup)
+ if (!ctx->checkWireAvail(next_wire) && !wire_reuse) {
+ if (!ripup)
+ continue;
+ conflictWireWire = ctx->getConflictingWireWire(next_wire);
+ if (conflictWireWire == WireId()) {
+ conflictWireNet = ctx->getConflictingWireNet(next_wire);
+ if (conflictWireNet == nullptr)
continue;
+ }
+ }
- next_penalty += cfg.wireRipupPenalty;
-
- auto scores_it = wireScores.find(next_wire);
- if (scores_it != wireScores.end())
- next_penalty += scores_it->second * cfg.wireRipupPenalty;
+ if (!ctx->checkPipAvail(pip) && !pip_reuse) {
+ if (!ripup)
+ continue;
+ conflictPipWire = ctx->getConflictingPipWire(pip);
+ if (conflictPipWire == WireId()) {
+ conflictPipNet = ctx->getConflictingPipNet(pip);
+ if (conflictPipNet == nullptr)
+ continue;
}
}
- if (!ctx->checkPipAvail(pip)) {
- NetInfo *ripupPipNet = ctx->getConflictingPipNet(pip);
+ if (conflictWireNet != nullptr && conflictPipWire != WireId() && conflictWireNet->wires.count(conflictPipWire))
+ conflictPipWire = WireId();
- if (ripupPipNet == nullptr)
- continue;
+ if (conflictPipNet != nullptr && conflictWireWire != WireId() && conflictPipNet->wires.count(conflictWireWire))
+ conflictWireWire = WireId();
- if (ripupPipNet == net_info) {
- auto net_info_wire_it = net_info->wires.find(next_wire);
- if (net_info_wire_it == net_info->wires.end() || net_info_wire_it->second.pip != pip)
- goto pip_self_ripup;
- next_bonus += cfg.pipReuseBonus;
- } else {
-pip_self_ripup:
- if (!ripup)
- continue;
+ if (conflictWireWire == conflictPipWire)
+ conflictWireWire = WireId();
- next_penalty += cfg.pipRipupPenalty;
+ if (conflictWireNet == conflictPipNet)
+ conflictWireNet = nullptr;
- auto pip_scores_it = pipScores.find(pip);
- if (pip_scores_it != pipScores.end())
- next_penalty += pip_scores_it->second * cfg.pipRipupPenalty;
+ if (wire_reuse)
+ next_bonus += cfg.wireReuseBonus;
- if (ctx->getConflictingPipWire(pip) == WireId()) {
- auto net_scores_it = netScores.find(ripupPipNet);
- if (net_scores_it != netScores.end())
- next_penalty += net_scores_it->second * cfg.netRipupPenalty;
+ if (pip_reuse)
+ next_bonus += cfg.pipReuseBonus;
- next_penalty += ripupPipNet->wires.size() * cfg.wireRipupPenalty;
- next_penalty += (ripupPipNet->wires.size()-1) * cfg.pipRipupPenalty;
- }
- }
+ if (conflictWireWire != WireId()) {
+ auto scores_it = wireScores.find(conflictWireWire);
+ if (scores_it != wireScores.end())
+ next_penalty += scores_it->second * cfg.wireRipupPenalty;
+ next_penalty += cfg.wireRipupPenalty;
+ }
+
+ if (conflictPipWire != WireId()) {
+ auto scores_it = wireScores.find(conflictPipWire);
+ if (scores_it != wireScores.end())
+ next_penalty += scores_it->second * cfg.wireRipupPenalty;
+ next_penalty += cfg.wireRipupPenalty;
+ }
+
+ if (conflictWireNet != nullptr) {
+ auto scores_it = netScores.find(conflictWireNet);
+ if (scores_it != netScores.end())
+ next_penalty += scores_it->second * cfg.netRipupPenalty;
+ next_penalty += cfg.netRipupPenalty;
+ next_penalty += conflictWireNet->wires.size() * cfg.wireRipupPenalty;
+ }
+
+ if (conflictPipNet != nullptr) {
+ auto scores_it = netScores.find(conflictPipNet);
+ if (scores_it != netScores.end())
+ next_penalty += scores_it->second * cfg.netRipupPenalty;
+ next_penalty += cfg.netRipupPenalty;
+ next_penalty += conflictPipNet->wires.size() * cfg.wireRipupPenalty;
}
delay_t next_score = next_delay + next_penalty;
@@ -596,30 +620,20 @@ pip_self_ripup:
if (ctx->debug)
log(" node %s\n", ctx->getWireName(cursor).c_str(ctx));
- if (!ctx->checkWireAvail(cursor)) {
- NetInfo *ripupWireNet = ctx->getConflictingWireNet(cursor);
- NPNR_ASSERT(ripupWireNet != nullptr);
- NPNR_ASSERT(ripupWireNet->wires.count(cursor));
+ if (pip == PipId())
+ NPNR_ASSERT(cursor == src_wire);
- if (ripupWireNet != net_info || net_info->wires.at(cursor).pip != pip) {
+ if (!net_info->wires.count(cursor) || net_info->wires.at(cursor).pip != pip) {
+ if (!ctx->checkWireAvail(cursor)) {
ripup_wire(cursor);
NPNR_ASSERT(ctx->checkWireAvail(cursor));
}
- }
- if (pip == PipId()) {
- NPNR_ASSERT(cursor == src_wire);
- } else {
- if (!ctx->checkPipAvail(pip)) {
- NetInfo *ripupPipNet = ctx->getConflictingPipNet(pip);
- NPNR_ASSERT(ripupPipNet != nullptr);
-
- if (ripupPipNet != net_info || !net_info->wires.count(cursor) || net_info->wires.at(cursor).pip != pip)
- ripup_pip(pip);
+ if (pip != PipId() && !ctx->checkPipAvail(pip)) {
+ ripup_pip(pip);
+ NPNR_ASSERT(ctx->checkPipAvail(pip));
}
- }
- if (net_info->wires.count(cursor) == 0 || net_info->wires.at(cursor).pip != pip) {
if (pip == PipId()) {
if (ctx->debug)
log(" bind wire %s\n", ctx->getWireName(cursor).c_str(ctx));
@@ -661,11 +675,10 @@ Router1Cfg::Router1Cfg(Context *ctx) : Settings(ctx)
useEstimate = get<bool>("router1/useEstimate", true);
wireRipupPenalty = ctx->getRipupDelayPenalty();
- pipRipupPenalty = ctx->getRipupDelayPenalty();
- netRipupPenalty = ctx->getRipupDelayPenalty();
+ netRipupPenalty = 10*ctx->getRipupDelayPenalty();
wireReuseBonus = wireRipupPenalty/8;
- pipReuseBonus = pipRipupPenalty/8;
+ pipReuseBonus = wireRipupPenalty/2;
estimatePrecision = 100 * ctx->getRipupDelayPenalty();
}
diff --git a/common/router1.h b/common/router1.h
index 65975d53..d6113441 100644
--- a/common/router1.h
+++ b/common/router1.h
@@ -34,7 +34,6 @@ struct Router1Cfg : Settings
bool fullCleanupReroute;
bool useEstimate;
delay_t wireRipupPenalty;
- delay_t pipRipupPenalty;
delay_t netRipupPenalty;
delay_t wireReuseBonus;
delay_t pipReuseBonus;
diff --git a/docs/archapi.md b/docs/archapi.md
index 1bfb7c5c..85bc6ccd 100644
--- a/docs/archapi.md
+++ b/docs/archapi.md
@@ -215,14 +215,15 @@ Return true if the wire is available, i.e. can be bound to a net.
Return the net a wire is bound to.
-### NetInfo \*getConflictingWireNet(WireId wire) const
+### WireId getConflictingWireWire(WireId wire) const
-If this returns a non-nullptr, then unbinding the wire from that net
+If this returns a non-WireId(), then unbinding that wire
will make the given wire available.
-This returns nullptr if the wire is already available,
-or if there is no net that can be unbound from the wire to make it
-available.
+### NetInfo \*getConflictingWireNet(WireId wire) const
+
+If this returns a non-nullptr, then unbinding that entire net
+will make the given wire available.
### DelayInfo getWireDelay(WireId wire) const
@@ -282,28 +283,23 @@ This method must also update `NetInfo::wires`.
Returns true if the given pip is available to be bound to a net.
+Users must also check if the pip destination wire is available
+with `checkWireAvail(getPipDstWire(pip))` before binding the
+pip to a net.
+
### NetInfo \*getBoundPipNet(PipId pip) const
Return the net this pip is bound to.
-### NetInfo \*getConflictingPipNet(PipId pip) const
-
-Return the net that needs to be unbound in order to make this
-pip available. Note that it may be neccessary to unroute that
-entire net to make the pip available.
-
-This returns nullptr if the pip is already available,
-or if there is no single net that can be unrouted to make
-the pip available.
-
### WireId getConflictingPipWire(PipId pip) const
-Return the single wire that needs to be unbound in order to make this pip
-available.
+If this returns a non-WireId(), then unbinding that wire
+will make the given pip available.
+
+### NetInfo \*getConflictingPipNet(PipId pip) const
-This returns WireId() if the pip is already available,
-or if there is no single wire that can be unbound to make
-the pip available.
+If this returns a non-nullptr, then unbinding that entire net
+will make the given pip available.
### const\_range\<PipId\> getPips() const
diff --git a/ecp5/arch.h b/ecp5/arch.h
index c9b1bf43..bd4881c2 100644
--- a/ecp5/arch.h
+++ b/ecp5/arch.h
@@ -619,6 +619,11 @@ struct Arch : BaseCtx
return wire_to_net.at(wire);
}
+ WireId getConflictingWireWire(WireId wire) const
+ {
+ return wire;
+ }
+
NetInfo *getConflictingWireNet(WireId wire) const
{
NPNR_ASSERT(wire != WireId());
@@ -724,6 +729,11 @@ struct Arch : BaseCtx
return pip_to_net.at(pip);
}
+ WireId getConflictingPipWire(PipId pip) const
+ {
+ return WireId();
+ }
+
NetInfo *getConflictingPipNet(PipId pip) const
{
NPNR_ASSERT(pip != PipId());
@@ -733,11 +743,6 @@ struct Arch : BaseCtx
return pip_to_net.at(pip);
}
- WireId getConflictingPipWire(PipId pip) const
- {
- return WireId();
- }
-
AllPipRange getPips() const
{
AllPipRange range;
diff --git a/generic/arch.h b/generic/arch.h
index d64d03c3..9311464e 100644
--- a/generic/arch.h
+++ b/generic/arch.h
@@ -172,6 +172,7 @@ struct Arch : BaseCtx
void unbindWire(WireId wire);
bool checkWireAvail(WireId wire) const;
NetInfo *getBoundWireNet(WireId wire) const;
+ WireId getConflictingWireWire(WireId wire) const { return wire; }
NetInfo *getConflictingWireNet(WireId wire) const;
DelayInfo getWireDelay(WireId wire) const { return DelayInfo(); }
const std::vector<WireId> &getWires() const;
@@ -186,8 +187,8 @@ struct Arch : BaseCtx
void unbindPip(PipId pip);
bool checkPipAvail(PipId pip) const;
NetInfo *getBoundPipNet(PipId pip) const;
- NetInfo *getConflictingPipNet(PipId pip) const;
WireId getConflictingPipWire(PipId pip) const;
+ NetInfo *getConflictingPipNet(PipId pip) const;
const std::vector<PipId> &getPips() const;
Loc getPipLocation(PipId pip) const;
WireId getPipSrcWire(PipId pip) const;
diff --git a/gui/designwidget.cc b/gui/designwidget.cc
index 8eda8a76..8a134c1f 100644
--- a/gui/designwidget.cc
+++ b/gui/designwidget.cc
@@ -453,6 +453,8 @@ void DesignWidget::onSelectionChanged(const QItemSelection &, const QItemSelecti
addProperty(topItem, QVariant::String, "Type", ctx->getWireType(wire).c_str(ctx));
addProperty(topItem, QVariant::Bool, "Available", ctx->checkWireAvail(wire));
addProperty(topItem, QVariant::String, "Bound Net", ctx->nameOf(ctx->getBoundWireNet(wire)), ElementType::NET);
+ addProperty(topItem, QVariant::String, "Conflicting Wire", ctx->getWireName(ctx->getConflictingWireWire(wire)).c_str(ctx),
+ ElementType::WIRE);
addProperty(topItem, QVariant::String, "Conflicting Net", ctx->nameOf(ctx->getConflictingWireNet(wire)),
ElementType::NET);
@@ -513,10 +515,10 @@ void DesignWidget::onSelectionChanged(const QItemSelection &, const QItemSelecti
addProperty(topItem, QVariant::String, "Type", ctx->getPipType(pip).c_str(ctx));
addProperty(topItem, QVariant::Bool, "Available", ctx->checkPipAvail(pip));
addProperty(topItem, QVariant::String, "Bound Net", ctx->nameOf(ctx->getBoundPipNet(pip)), ElementType::NET);
- addProperty(topItem, QVariant::String, "Conflicting Net", ctx->nameOf(ctx->getConflictingPipNet(pip)),
- ElementType::NET);
addProperty(topItem, QVariant::String, "Conflicting Wire", ctx->getWireName(ctx->getConflictingPipWire(pip)).c_str(ctx),
ElementType::WIRE);
+ addProperty(topItem, QVariant::String, "Conflicting Net", ctx->nameOf(ctx->getConflictingPipNet(pip)),
+ ElementType::NET);
addProperty(topItem, QVariant::String, "Src Wire", ctx->getWireName(ctx->getPipSrcWire(pip)).c_str(ctx),
ElementType::WIRE);
addProperty(topItem, QVariant::String, "Dest Wire", ctx->getWireName(ctx->getPipDstWire(pip)).c_str(ctx),
diff --git a/ice40/arch.h b/ice40/arch.h
index 46f2b348..2967ee1f 100644
--- a/ice40/arch.h
+++ b/ice40/arch.h
@@ -566,6 +566,11 @@ struct Arch : BaseCtx
return wire_to_net[wire.index];
}
+ WireId getConflictingWireWire(WireId wire) const
+ {
+ return wire;
+ }
+
NetInfo *getConflictingWireNet(WireId wire) const
{
NPNR_ASSERT(wire != WireId());
@@ -642,49 +647,59 @@ struct Arch : BaseCtx
refreshUiWire(dst);
}
- bool checkPipAvail(PipId pip) const
+ bool ice40_pip_hard_unavail(PipId pip) const
{
NPNR_ASSERT(pip != PipId());
auto &pi = chip_info->pip_data[pip.index];
auto &si = chip_info->bits_info->switches[pi.switch_index];
- if (switches_locked[pi.switch_index] != WireId())
- return false;
-
if (pi.flags & PipInfoPOD::FLAG_ROUTETHRU) {
NPNR_ASSERT(si.bel >= 0);
if (bel_to_cell[si.bel] != nullptr)
- return false;
+ return true;
}
if (pi.flags & PipInfoPOD::FLAG_NOCARRY) {
NPNR_ASSERT(si.bel >= 0);
if (bel_carry[si.bel])
- return false;
+ return true;
}
- return true;
+ return false;
}
- NetInfo *getBoundPipNet(PipId pip) const
+ bool checkPipAvail(PipId pip) const
{
- NPNR_ASSERT(pip != PipId());
- return pip_to_net[pip.index];
+ if (ice40_pip_hard_unavail(pip))
+ return false;
+
+ auto &pi = chip_info->pip_data[pip.index];
+ return switches_locked[pi.switch_index] == WireId();
}
- NetInfo *getConflictingPipNet(PipId pip) const
+ NetInfo *getBoundPipNet(PipId pip) const
{
NPNR_ASSERT(pip != PipId());
- WireId wire = switches_locked[chip_info->pip_data[pip.index].switch_index];
- return wire == WireId() ? nullptr : wire_to_net[wire.index];
+ return pip_to_net[pip.index];
}
WireId getConflictingPipWire(PipId pip) const
{
- NPNR_ASSERT(pip != PipId());
+ if (ice40_pip_hard_unavail(pip))
+ return WireId();
+
return switches_locked[chip_info->pip_data[pip.index].switch_index];
}
+ NetInfo *getConflictingPipNet(PipId pip) const
+ {
+ if (ice40_pip_hard_unavail(pip))
+ return nullptr;
+
+ WireId wire = switches_locked[chip_info->pip_data[pip.index].switch_index];
+ return wire == WireId() ? nullptr : wire_to_net[wire.index];
+ }
+
AllPipRange getPips() const
{
AllPipRange range;
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-19 04:19:41 +0000