diff options
33 files changed, 1988 insertions, 290 deletions
diff --git a/common/dynamic_bitarray.h b/common/dynamic_bitarray.h index 10a85fbc..2b5ab2bc 100644 --- a/common/dynamic_bitarray.h +++ b/common/dynamic_bitarray.h @@ -70,6 +70,8 @@ template <typename Storage = std::vector<uint8_t>> class DynamicBitarray size_t size() const { return storage.size() * bits_per_value(); } + void clear() { return storage.clear(); } + private: Storage storage; }; diff --git a/common/nextpnr.h b/common/nextpnr.h index ab2f8dca..404900c4 100644 --- a/common/nextpnr.h +++ b/common/nextpnr.h @@ -552,6 +552,10 @@ struct DelayPair { return {min_delay + other.min_delay, max_delay + other.max_delay}; } + DelayPair operator-(const DelayPair &other) const + { + return {min_delay - other.min_delay, max_delay - other.max_delay}; + } }; // four-quadrant, min and max rise and fall delay @@ -575,6 +579,7 @@ struct DelayQuad DelayPair delayPair() const { return DelayPair(minDelay(), maxDelay()); }; DelayQuad operator+(const DelayQuad &other) const { return {rise + other.rise, fall + other.fall}; } + DelayQuad operator-(const DelayQuad &other) const { return {rise - other.rise, fall - other.fall}; } }; struct ClockConstraint; diff --git a/common/placer1.cc b/common/placer1.cc index 619bfbc8..c8b0d385 100644 --- a/common/placer1.cc +++ b/common/placer1.cc @@ -42,6 +42,7 @@ #include "fast_bels.h" #include "log.h" #include "place_common.h" +#include "scope_lock.h" #include "timing.h" #include "util.h" @@ -77,7 +78,7 @@ class SAPlacer public: SAPlacer(Context *ctx, Placer1Cfg cfg) - : ctx(ctx), fast_bels(ctx, /*check_bel_available=*/false, cfg.minBelsForGridPick), cfg(cfg) + : ctx(ctx), fast_bels(ctx, /*check_bel_available=*/false, cfg.minBelsForGridPick), cfg(cfg), tmg(ctx) { for (auto bel : ctx->getBels()) { Loc loc = ctx->getBelLocation(bel); @@ -142,7 +143,8 @@ class SAPlacer bool place(bool refine = false) { log_break(); - ctx->lock(); + + nextpnr::ScopeLock<Context> lock(ctx); size_t placed_cells = 0; std::vector<CellInfo *> autoplaced; @@ -239,8 +241,9 @@ class SAPlacer auto saplace_start = std::chrono::high_resolution_clock::now(); // Invoke timing analysis to obtain criticalities + tmg.setup_only = true; if (!cfg.budgetBased) - get_criticalities(ctx, &net_crit); + tmg.setup(); // Calculate costs after initial placement setup_costs(); @@ -377,7 +380,7 @@ class SAPlacer // Invoke timing analysis to obtain criticalities if (!cfg.budgetBased && cfg.timing_driven) - get_criticalities(ctx, &net_crit); + tmg.run(); // Need to rebuild costs after criticalities change setup_costs(); // Reset incremental bounds @@ -421,7 +424,7 @@ class SAPlacer log_error("constraint satisfaction check failed for cell '%s' at Bel '%s'\n", cell.first.c_str(ctx), ctx->nameOfBel(cell.second->bel)); timing_analysis(ctx); - ctx->unlock(); + return true; } @@ -834,11 +837,9 @@ class SAPlacer double delay = ctx->getDelayNS(ctx->predictDelay(net, net->users.at(user))); return std::min(10.0, std::exp(delay - ctx->getDelayNS(net->users.at(user).budget) / 10)); } else { - auto crit = net_crit.find(net->name); - if (crit == net_crit.end() || crit->second.criticality.empty()) - return 0; + float crit = tmg.get_criticality(CellPortKey(net->users.at(user))); double delay = ctx->getDelayNS(ctx->predictDelay(net, net->users.at(user))); - return delay * std::pow(crit->second.criticality.at(user), crit_exp); + return delay * std::pow(crit, crit_exp); } } @@ -1214,9 +1215,6 @@ class SAPlacer wirelen_t last_wirelen_cost, curr_wirelen_cost; double last_timing_cost, curr_timing_cost; - // Criticality data from timing analysis - NetCriticalityMap net_crit; - Context *ctx; float temp = 10; float crit_exp = 8; @@ -1233,6 +1231,8 @@ class SAPlacer bool require_legal = true; const int legalise_dia = 4; Placer1Cfg cfg; + + TimingAnalyser tmg; }; Placer1Cfg::Placer1Cfg(Context *ctx) @@ -1263,9 +1263,10 @@ bool placer1(Context *ctx, Placer1Cfg cfg) return true; } catch (log_execution_error_exception) { #ifndef NDEBUG + ctx->lock(); ctx->check(); -#endif ctx->unlock(); +#endif return false; } } @@ -1284,9 +1285,10 @@ bool placer1_refine(Context *ctx, Placer1Cfg cfg) return true; } catch (log_execution_error_exception) { #ifndef NDEBUG + ctx->lock(); ctx->check(); -#endif ctx->unlock(); +#endif return false; } } diff --git a/common/placer_heap.cc b/common/placer_heap.cc index 8a3b427f..3ee8503c 100644 --- a/common/placer_heap.cc +++ b/common/placer_heap.cc @@ -49,6 +49,7 @@ #include "nextpnr.h" #include "place_common.h" #include "placer1.h" +#include "scope_lock.h" #include "timing.h" #include "util.h" @@ -138,16 +139,19 @@ template <typename T> struct EquationSystem class HeAPPlacer { public: - HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) : ctx(ctx), cfg(cfg), fast_bels(ctx, /*check_bel_available=*/true, -1) + HeAPPlacer(Context *ctx, PlacerHeapCfg cfg) + : ctx(ctx), cfg(cfg), fast_bels(ctx, /*check_bel_available=*/true, -1), tmg(ctx) { Eigen::initParallel(); + tmg.setup_only = true; + tmg.setup(); } bool place() { auto startt = std::chrono::high_resolution_clock::now(); - ctx->lock(); + nextpnr::ScopeLock<Context> lock(ctx); place_constraints(); build_fast_bels(); seed_placement(); @@ -268,7 +272,7 @@ class HeAPPlacer // Update timing weights if (cfg.timing_driven) - get_criticalities(ctx, &net_crit); + tmg.run(); if (legal_hpwl < best_hpwl) { best_hpwl = legal_hpwl; @@ -312,7 +316,24 @@ class HeAPPlacer log_info("AP soln: %s -> %s\n", cell.first.c_str(ctx), ctx->nameOfBel(cell.second->bel)); } - ctx->unlock(); + bool any_bad_placements = false; + for (auto bel : ctx->getBels()) { + CellInfo *cell = ctx->getBoundBelCell(bel); + if (!ctx->isBelLocationValid(bel)) { + std::string cell_text = "no cell"; + if (cell != nullptr) + cell_text = std::string("cell '") + ctx->nameOf(cell) + "'"; + log_warning("post-placement validity check failed for Bel '%s' " + "(%s)\n", + ctx->nameOfBel(bel), cell_text.c_str()); + any_bad_placements = true; + } + } + + if (any_bad_placements) { + return false; + } + auto endtt = std::chrono::high_resolution_clock::now(); log_info("HeAP Placer Time: %.02fs\n", std::chrono::duration<double>(endtt - startt).count()); log_info(" of which solving equations: %.02fs\n", solve_time); @@ -320,8 +341,11 @@ class HeAPPlacer log_info(" of which strict legalisation: %.02fs\n", sl_time); ctx->check(); + lock.unlock_early(); - placer1_refine(ctx, Placer1Cfg(ctx)); + if (!placer1_refine(ctx, Placer1Cfg(ctx))) { + return false; + } return true; } @@ -334,6 +358,8 @@ class HeAPPlacer FastBels fast_bels; std::unordered_map<IdString, std::tuple<int, int>> bel_types; + TimingAnalyser tmg; + struct BoundingBox { // Actual bounding box @@ -371,8 +397,6 @@ class HeAPPlacer // Performance counting double solve_time = 0, cl_time = 0, sl_time = 0; - NetCriticalityMap net_crit; - // Place cells with the BEL attribute set to constrain them void place_constraints() { @@ -715,11 +739,9 @@ class HeAPPlacer std::max<double>(1, (yaxis ? cfg.hpwl_scale_y : cfg.hpwl_scale_x) * std::abs(o_pos - this_pos))); - if (user_idx != -1 && net_crit.count(ni->name)) { - auto &nc = net_crit.at(ni->name); - if (user_idx < int(nc.criticality.size())) - weight *= (1.0 + cfg.timingWeight * - std::pow(nc.criticality.at(user_idx), cfg.criticalityExponent)); + if (user_idx != -1) { + weight *= (1.0 + cfg.timingWeight * std::pow(tmg.get_criticality(CellPortKey(port)), + cfg.criticalityExponent)); } // If cell 0 is not fixed, it will stamp +w on its equation and -w on the other end's equation, diff --git a/common/router1.cc b/common/router1.cc index efc06b06..bffbc9f9 100644 --- a/common/router1.cc +++ b/common/router1.cc @@ -23,6 +23,7 @@ #include "log.h" #include "router1.h" +#include "scope_lock.h" #include "timing.h" namespace { @@ -805,7 +806,7 @@ bool router1(Context *ctx, const Router1Cfg &cfg) try { log_break(); log_info("Routing..\n"); - ctx->lock(); + nextpnr::ScopeLock<Context> lock(ctx); auto rstart = std::chrono::high_resolution_clock::now(); log_info("Setting up routing queue.\n"); @@ -854,7 +855,6 @@ bool router1(Context *ctx, const Router1Cfg &cfg) router.check(); ctx->check(); #endif - ctx->unlock(); return false; } } @@ -878,13 +878,13 @@ bool router1(Context *ctx, const Router1Cfg &cfg) timing_analysis(ctx, true /* slack_histogram */, true /* print_fmax */, true /* print_path */, true /* warn_on_failure */); - ctx->unlock(); return true; } catch (log_execution_error_exception) { #ifndef NDEBUG + ctx->lock(); ctx->check(); -#endif ctx->unlock(); +#endif return false; } } diff --git a/common/router2.cc b/common/router2.cc index 2f9f0ac4..0a3a4e94 100644 --- a/common/router2.cc +++ b/common/router2.cc @@ -37,6 +37,7 @@ #include "log.h" #include "nextpnr.h" #include "router1.h" +#include "scope_lock.h" #include "timing.h" #include "util.h" @@ -112,16 +113,14 @@ struct Router2 Context *ctx; Router2Cfg cfg; - Router2(Context *ctx, const Router2Cfg &cfg) : ctx(ctx), cfg(cfg) {} + Router2(Context *ctx, const Router2Cfg &cfg) : ctx(ctx), cfg(cfg), tmg(ctx) { tmg.setup(); } // Use 'udata' for fast net lookups and indexing std::vector<NetInfo *> nets_by_udata; std::vector<PerNetData> nets; bool timing_driven; - - // Criticality data from timing analysis - NetCriticalityMap net_crit; + TimingAnalyser tmg; void setup_nets() { @@ -640,7 +639,7 @@ struct Router2 bool debug_arc = /*usr.cell->type.str(ctx).find("RAMB") != std::string::npos && (usr.port == ctx->id("ADDRATIEHIGH0") || usr.port == ctx->id("ADDRARDADDRL0"))*/ false; - while (!t.queue.empty() && (!is_bb || iter < toexplore)) { + while (!t.queue.empty() && iter < toexplore) { auto curr = t.queue.top(); auto &d = flat_wires.at(curr.wire); t.queue.pop(); @@ -1162,6 +1161,8 @@ struct Router2 ThreadContext st; int iter = 1; + nextpnr::ScopeLock<Context> lock(ctx); + for (size_t i = 0; i < nets_by_udata.size(); i++) route_queue.push_back(i); @@ -1173,18 +1174,13 @@ struct Router2 if (timing_driven && (int(route_queue.size()) > (int(nets_by_udata.size()) / 50))) { // Heuristic: reduce runtime by skipping STA in the case of a "long tail" of a few // congested nodes - get_criticalities(ctx, &net_crit); + tmg.run(); for (auto n : route_queue) { - IdString name = nets_by_udata.at(n)->name; - auto fnd = net_crit.find(name); + NetInfo *ni = nets_by_udata.at(n); auto &net = nets.at(n); net.max_crit = 0; - if (fnd == net_crit.end()) - continue; - for (int i = 0; i < int(fnd->second.criticality.size()); i++) { - float c = fnd->second.criticality.at(i); - for (auto &a : net.arcs.at(i)) - a.arc_crit = c; + for (auto &usr : ni->users) { + float c = tmg.get_criticality(CellPortKey(usr)); net.max_crit = std::max(net.max_crit, c); } } @@ -1238,6 +1234,8 @@ struct Router2 log_info("Running router1 to check that route is legal...\n"); + lock.unlock_early(); + router1(ctx, Router1Cfg(ctx)); } }; diff --git a/common/scope_lock.h b/common/scope_lock.h new file mode 100644 index 00000000..7b6c9dcd --- /dev/null +++ b/common/scope_lock.h @@ -0,0 +1,65 @@ +/* + * 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. + * + */ + +#ifndef SCOPE_LOCK_H +#define SCOPE_LOCK_H + +#include <stdexcept> + +namespace nextpnr { + +// Provides a simple RAII locking object. ScopeLock takes a lock when +// constructed, and releases the lock on destruction or if "unlock_early" is +// called. +// +// LockingObject must have a method "void lock(void)" and "void unlock(void)". +template <typename LockingObject> class ScopeLock +{ + public: + ScopeLock(LockingObject *obj) : obj_(obj), locked_(false) + { + obj_->lock(); + locked_ = true; + } + ScopeLock(const ScopeLock &other) = delete; + ScopeLock(const ScopeLock &&other) = delete; + + ~ScopeLock() + { + if (locked_) { + obj_->unlock(); + } + } + void unlock_early() + { + if (!locked_) { + throw std::runtime_error("Lock already released?"); + } + locked_ = false; + obj_->unlock(); + } + + private: + LockingObject *obj_; + bool locked_; +}; + +}; // namespace nextpnr + +#endif /* SCOPE_LOCK_H */ diff --git a/common/timing.cc b/common/timing.cc index a61c0beb..8229f143 100644 --- a/common/timing.cc +++ b/common/timing.cc @@ -30,6 +30,547 @@ NEXTPNR_NAMESPACE_BEGIN +void TimingAnalyser::setup() +{ + init_ports(); + get_cell_delays(); + topo_sort(); + setup_port_domains(); + run(); +} + +void TimingAnalyser::run() +{ + reset_times(); + get_route_delays(); + walk_forward(); + walk_backward(); + compute_slack(); + compute_criticality(); +} + +void TimingAnalyser::init_ports() +{ + // Per cell port structures + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + for (auto port : sorted_ref(ci->ports)) { + auto &data = ports[CellPortKey(ci->name, port.first)]; + data.type = port.second.type; + data.cell_port = CellPortKey(ci->name, port.first); + } + } + // Cell port to net port mapping + for (auto net : sorted(ctx->nets)) { + NetInfo *ni = net.second; + if (ni->driver.cell != nullptr) + ports[CellPortKey(ni->driver)].net_port = NetPortKey(ni->name); + for (size_t i = 0; i < ni->users.size(); i++) + ports[CellPortKey(ni->users.at(i))].net_port = NetPortKey(ni->name, i); + } +} + +void TimingAnalyser::get_cell_delays() +{ + for (auto &port : ports) { + CellInfo *ci = cell_info(port.first); + auto &pi = port_info(port.first); + auto &pd = port.second; + + IdString name = port.first.port; + // Ignore dangling ports altogether for timing purposes + if (pd.net_port.net == IdString()) + continue; + pd.cell_arcs.clear(); + int clkInfoCount = 0; + TimingPortClass cls = ctx->getPortTimingClass(ci, name, clkInfoCount); + if (cls == TMG_STARTPOINT || cls == TMG_ENDPOINT || cls == TMG_CLOCK_INPUT || cls == TMG_GEN_CLOCK || + cls == TMG_IGNORE) + continue; + if (pi.type == PORT_IN) { + // Input ports might have setup/hold relationships + if (cls == TMG_REGISTER_INPUT) { + for (int i = 0; i < clkInfoCount; i++) { + auto info = ctx->getPortClockingInfo(ci, name, i); + if (!ci->ports.count(info.clock_port) || ci->ports.at(info.clock_port).net == nullptr) + continue; + pd.cell_arcs.emplace_back(CellArc::SETUP, info.clock_port, DelayQuad(info.setup, info.setup), + info.edge); + pd.cell_arcs.emplace_back(CellArc::HOLD, info.clock_port, DelayQuad(info.hold, info.hold), + info.edge); + } + } + // Combinational delays through cell + for (auto &other_port : ci->ports) { + auto &op = other_port.second; + // ignore dangling ports and non-outputs + if (op.net == nullptr || op.type != PORT_OUT) + continue; + DelayQuad delay; + bool is_path = ctx->getCellDelay(ci, name, other_port.first, delay); + if (is_path) + pd.cell_arcs.emplace_back(CellArc::COMBINATIONAL, other_port.first, delay); + } + } else if (pi.type == PORT_OUT) { + // Output ports might have clk-to-q relationships + if (cls == TMG_REGISTER_OUTPUT) { + for (int i = 0; i < clkInfoCount; i++) { + auto info = ctx->getPortClockingInfo(ci, name, i); + if (!ci->ports.count(info.clock_port) || ci->ports.at(info.clock_port).net == nullptr) + continue; + pd.cell_arcs.emplace_back(CellArc::CLK_TO_Q, info.clock_port, info.clockToQ, info.edge); + } + } + // Combinational delays through cell + for (auto &other_port : ci->ports) { + auto &op = other_port.second; + // ignore dangling ports and non-inputs + if (op.net == nullptr || op.type != PORT_IN) + continue; + DelayQuad delay; + bool is_path = ctx->getCellDelay(ci, other_port.first, name, delay); + if (is_path) + pd.cell_arcs.emplace_back(CellArc::COMBINATIONAL, other_port.first, delay); + } + } + } +} + +void TimingAnalyser::get_route_delays() +{ + for (auto net : sorted(ctx->nets)) { + NetInfo *ni = net.second; + if (ni->driver.cell == nullptr || ni->driver.cell->bel == BelId()) + continue; + for (auto &usr : ni->users) { + if (usr.cell->bel == BelId()) + continue; + ports.at(CellPortKey(usr)).route_delay = DelayPair(ctx->getNetinfoRouteDelay(ni, usr)); + } + } +} + +void TimingAnalyser::topo_sort() +{ + TopoSort<CellPortKey> topo; + for (auto &port : ports) { + auto &pd = port.second; + // All ports are nodes + topo.node(port.first); + if (pd.type == PORT_IN) { + // inputs: combinational arcs through the cell are edges + for (auto &arc : pd.cell_arcs) { + if (arc.type != CellArc::COMBINATIONAL) + continue; + topo.edge(port.first, CellPortKey(port.first.cell, arc.other_port)); + } + } else if (pd.type == PORT_OUT) { + // output: routing arcs are edges + const NetInfo *pn = port_info(port.first).net; + if (pn != nullptr) { + for (auto &usr : pn->users) + topo.edge(port.first, CellPortKey(usr)); + } + } + } + bool no_loops = topo.sort(); + if (!no_loops && verbose_mode) { + log_info("Found %d combinational loops:\n", int(topo.loops.size())); + int i = 0; + for (auto &loop : topo.loops) { + log_info(" loop %d:\n", ++i); + for (auto &port : loop) { + log_info(" %s.%s (%s)\n", ctx->nameOf(port.cell), ctx->nameOf(port.port), + ctx->nameOf(port_info(port).net)); + } + } + } + std::swap(topological_order, topo.sorted); +} + +void TimingAnalyser::setup_port_domains() +{ + for (auto &d : domains) { + d.startpoints.clear(); + d.endpoints.clear(); + } + // Go forward through the topological order (domains from the PoV of arrival time) + for (auto port : topological_order) { + auto &pd = ports.at(port); + auto &pi = port_info(port); + if (pi.type == PORT_OUT) { + for (auto &fanin : pd.cell_arcs) { + if (fanin.type != CellArc::CLK_TO_Q) + continue; + // registered outputs are startpoints + auto dom = domain_id(port.cell, fanin.other_port, fanin.edge); + // create per-domain data + pd.arrival[dom]; + domains.at(dom).startpoints.emplace_back(port, fanin.other_port); + } + // copy domains across routing + if (pi.net != nullptr) + for (auto &usr : pi.net->users) + copy_domains(port, CellPortKey(usr), false); + } else { + // copy domains from input to output + for (auto &fanout : pd.cell_arcs) { + if (fanout.type != CellArc::COMBINATIONAL) + continue; + copy_domains(port, CellPortKey(port.cell, fanout.other_port), false); + } + } + } + // Go backward through the topological order (domains from the PoV of required time) + for (auto port : reversed_range(topological_order)) { + auto &pd = ports.at(port); + auto &pi = port_info(port); + if (pi.type == PORT_OUT) { + // copy domains from output to input + for (auto &fanin : pd.cell_arcs) { + if (fanin.type != CellArc::COMBINATIONAL) + continue; + copy_domains(port, CellPortKey(port.cell, fanin.other_port), true); + } + } else { + for (auto &fanout : pd.cell_arcs) { + if (fanout.type != CellArc::SETUP) + continue; + // registered inputs are startpoints + auto dom = domain_id(port.cell, fanout.other_port, fanout.edge); + // create per-domain data + pd.required[dom]; + domains.at(dom).endpoints.emplace_back(port, fanout.other_port); + } + // copy port to driver + if (pi.net != nullptr && pi.net->driver.cell != nullptr) + copy_domains(port, CellPortKey(pi.net->driver), true); + } + } + // Iterate over ports and find domain paris + for (auto port : topological_order) { + auto &pd = ports.at(port); + for (auto &arr : pd.arrival) + for (auto &req : pd.required) { + pd.domain_pairs[domain_pair_id(arr.first, req.first)]; + } + } +} + +void TimingAnalyser::reset_times() +{ + for (auto &port : ports) { + auto do_reset = [&](std::unordered_map<domain_id_t, ArrivReqTime> ×) { + for (auto &t : times) { + t.second.value = init_delay; + t.second.path_length = 0; + t.second.bwd_min = CellPortKey(); + t.second.bwd_max = CellPortKey(); + } + }; + do_reset(port.second.arrival); + do_reset(port.second.required); + for (auto &dp : port.second.domain_pairs) { + dp.second.setup_slack = std::numeric_limits<delay_t>::max(); + dp.second.hold_slack = std::numeric_limits<delay_t>::max(); + dp.second.max_path_length = 0; + dp.second.criticality = 0; + dp.second.budget = 0; + } + port.second.worst_crit = 0; + port.second.worst_setup_slack = std::numeric_limits<delay_t>::max(); + port.second.worst_hold_slack = std::numeric_limits<delay_t>::max(); + } +} + +void TimingAnalyser::set_arrival_time(CellPortKey target, domain_id_t domain, DelayPair arrival, int path_length, + CellPortKey prev) +{ + auto &arr = ports.at(target).arrival.at(domain); + if (arrival.max_delay > arr.value.max_delay) { + arr.value.max_delay = arrival.max_delay; + arr.bwd_max = prev; + } + if (!setup_only && (arrival.min_delay < arr.value.min_delay)) { + arr.value.min_delay = arrival.min_delay; + arr.bwd_min = prev; + } + arr.path_length = std::max(arr.path_length, path_length); +} + +void TimingAnalyser::set_required_time(CellPortKey target, domain_id_t domain, DelayPair required, int path_length, + CellPortKey prev) +{ + auto &req = ports.at(target).required.at(domain); + if (required.min_delay < req.value.min_delay) { + req.value.min_delay = required.min_delay; + req.bwd_min = prev; + } + if (!setup_only && (required.max_delay > req.value.max_delay)) { + req.value.max_delay = required.max_delay; + req.bwd_max = prev; + } + req.path_length = std::max(req.path_length, path_length); +} + +void TimingAnalyser::walk_forward() +{ + // Assign initial arrival time to domain startpoints + for (domain_id_t dom_id = 0; dom_id < domain_id_t(domains.size()); ++dom_id) { + auto &dom = domains.at(dom_id); + for (auto &sp : dom.startpoints) { + auto &pd = ports.at(sp.first); + DelayPair init_arrival(0); + CellPortKey clock_key; + // TODO: clock routing delay, if analysis of that is enabled + if (sp.second != IdString()) { + // clocked startpoints have a clock-to-out time + for (auto &fanin : pd.cell_arcs) { + if (fanin.type == CellArc::CLK_TO_Q && fanin.other_port == sp.second) { + init_arrival = init_arrival + fanin.value.delayPair(); + break; + } + } + clock_key = CellPortKey(sp.first.cell, sp.second); + } + set_arrival_time(sp.first, dom_id, init_arrival, 1, clock_key); + } + } + // Walk forward in topological order + for (auto p : topological_order) { + auto &pd = ports.at(p); + for (auto &arr : pd.arrival) { + if (pd.type == PORT_OUT) { + // Output port: propagate delay through net, adding route delay + NetInfo *net = port_info(p).net; + if (net != nullptr) + for (auto &usr : net->users) { + CellPortKey usr_key(usr); + auto &usr_pd = ports.at(usr_key); + set_arrival_time(usr_key, arr.first, arr.second.value + usr_pd.route_delay, + arr.second.path_length, p); + } + } else if (pd.type == PORT_IN) { + // Input port; propagate delay through cell, adding combinational delay + for (auto &fanout : pd.cell_arcs) { + if (fanout.type != CellArc::COMBINATIONAL) + continue; + set_arrival_time(CellPortKey(p.cell, fanout.other_port), arr.first, + arr.second.value + fanout.value.delayPair(), arr.second.path_length + 1, p); + } + } + } + } +} + +void TimingAnalyser::walk_backward() +{ + // Assign initial required time to domain endpoints + // Note that clock frequency will be considered later in the analysis for, for now all required times are normalised + // to 0ns + for (domain_id_t dom_id = 0; dom_id < domain_id_t(domains.size()); ++dom_id) { + auto &dom = domains.at(dom_id); + for (auto &ep : dom.endpoints) { + auto &pd = ports.at(ep.first); + DelayPair init_setuphold(0); + CellPortKey clock_key; + // TODO: clock routing delay, if analysis of that is enabled + if (ep.second != IdString()) { + // Add setup/hold time, if this endpoint is clocked + for (auto &fanin : pd.cell_arcs) { + if (fanin.type == CellArc::SETUP && fanin.other_port == ep.second) + init_setuphold.min_delay -= fanin.value.maxDelay(); + if (fanin.type == CellArc::HOLD && fanin.other_port == ep.second) + init_setuphold.max_delay -= fanin.value.maxDelay(); + } + clock_key = CellPortKey(ep.first.cell, ep.second); + } + set_required_time(ep.first, dom_id, init_setuphold, 1, clock_key); + } + } + // Walk backwards in topological order + for (auto p : reversed_range(topological_order)) { + auto &pd = ports.at(p); + for (auto &req : pd.required) { + if (pd.type == PORT_IN) { + // Input port: propagate delay back through net, subtracting route delay + NetInfo *net = port_info(p).net; + if (net != nullptr && net->driver.cell != nullptr) + set_required_time(CellPortKey(net->driver), req.first, req.second.value - pd.route_delay, + req.second.path_length, p); + } else if (pd.type == PORT_OUT) { + // Output port : propagate delay back through cell, subtracting combinational delay + for (auto &fanin : pd.cell_arcs) { + if (fanin.type != CellArc::COMBINATIONAL) + continue; + set_required_time(CellPortKey(p.cell, fanin.other_port), req.first, + req.second.value - fanin.value.delayPair(), req.second.path_length + 1, p); + } + } + } + } +} + +void TimingAnalyser::print_fmax() +{ + // Temporary testing code for comparison only + std::unordered_map<int, double> domain_fmax; + for (auto p : topological_order) { + auto &pd = ports.at(p); + for (auto &req : pd.required) { + if (pd.arrival.count(req.first)) { + auto &arr = pd.arrival.at(req.first); + double fmax = 1000.0 / ctx->getDelayNS(arr.value.maxDelay() - req.second.value.minDelay()); + if (!domain_fmax.count(req.first) || domain_fmax.at(req.first) > fmax) + domain_fmax[req.first] = fmax; + } + } + } + for (auto &fm : domain_fmax) { + log_info("Domain %s Worst Fmax %.02f\n", ctx->nameOf(domains.at(fm.first).key.clock), fm.second); + } +} + +void TimingAnalyser::compute_slack() +{ + for (auto &dp : domain_pairs) { + dp.worst_setup_slack = std::numeric_limits<delay_t>::max(); + dp.worst_hold_slack = std::numeric_limits<delay_t>::max(); + } + for (auto p : topological_order) { + auto &pd = ports.at(p); + for (auto &pdp : pd.domain_pairs) { + auto &dp = domain_pairs.at(pdp.first); + auto &arr = pd.arrival.at(dp.key.launch); + auto &req = pd.required.at(dp.key.capture); + pdp.second.setup_slack = dp.period.minDelay() - (arr.value.maxDelay() - req.value.minDelay()); + if (!setup_only) + pdp.second.hold_slack = arr.value.minDelay() - req.value.maxDelay(); + pdp.second.max_path_length = arr.path_length + req.path_length; + pd.worst_setup_slack = std::min(pd.worst_setup_slack, pdp.second.setup_slack); + dp.worst_setup_slack = std::min(dp.worst_setup_slack, pdp.second.setup_slack); + if (!setup_only) { + pd.worst_hold_slack = std::min(pd.worst_hold_slack, pdp.second.hold_slack); + dp.worst_hold_slack = std::min(dp.worst_hold_slack, pdp.second.hold_slack); + } + } + } +} + +void TimingAnalyser::compute_criticality() +{ + for (auto p : topological_order) { + auto &pd = ports.at(p); + for (auto &pdp : pd.domain_pairs) { + auto &dp = domain_pairs.at(pdp.first); + float crit = + 1.0f - (float(pdp.second.setup_slack) - float(dp.worst_setup_slack)) / float(-dp.worst_setup_slack); + crit = std::min(crit, 1.0f); + crit = std::max(crit, 0.0f); + pdp.second.criticality = crit; + pd.worst_crit = std::max(pd.worst_crit, crit); + } + } +} + +std::vector<CellPortKey> TimingAnalyser::get_failing_eps(domain_id_t domain_pair, int count) +{ + std::vector<CellPortKey> failing_eps; + delay_t last_slack = std::numeric_limits<delay_t>::min(); + auto &dp = domain_pairs.at(domain_pair); + auto &cap_d = domains.at(dp.key.capture); + while (int(failing_eps.size()) < count) { + CellPortKey next; + delay_t next_slack = std::numeric_limits<delay_t>::max(); + for (auto ep : cap_d.endpoints) { + auto &pd = ports.at(ep.first); + if (!pd.domain_pairs.count(domain_pair)) + continue; + delay_t ep_slack = pd.domain_pairs.at(domain_pair).setup_slack; + if (ep_slack < next_slack && ep_slack > last_slack) { + next = ep.first; + next_slack = ep_slack; + } + } + if (next == CellPortKey()) + break; + failing_eps.push_back(next); + last_slack = next_slack; + } + return failing_eps; +} + +void TimingAnalyser::print_critical_path(CellPortKey endpoint, domain_id_t domain_pair) +{ + CellPortKey cursor = endpoint; + auto &dp = domain_pairs.at(domain_pair); + log(" endpoint %s.%s (slack %.02fns):\n", ctx->nameOf(cursor.cell), ctx->nameOf(cursor.port), + ctx->getDelayNS(ports.at(cursor).domain_pairs.at(domain_pair).setup_slack)); + while (cursor != CellPortKey()) { + log(" %s.%s (net %s)\n", ctx->nameOf(cursor.cell), ctx->nameOf(cursor.port), + ctx->nameOf(get_net_or_empty(ctx->cells.at(cursor.cell).get(), cursor.port))); + if (!ports.at(cursor).arrival.count(dp.key.launch)) + break; + cursor = ports.at(cursor).arrival.at(dp.key.launch).bwd_max; + } +} + +namespace { +const char *edge_name(ClockEdge edge) { return (edge == FALLING_EDGE) ? "negedge" : "posedge"; } +} // namespace + +void TimingAnalyser::print_report() +{ + for (int i = 0; i < int(domain_pairs.size()); i++) { + auto &dp = domain_pairs.at(i); + auto &launch = domains.at(dp.key.launch); + auto &capture = domains.at(dp.key.capture); + log("Worst endpoints for %s %s -> %s %s\n", edge_name(launch.key.edge), ctx->nameOf(launch.key.clock), + edge_name(capture.key.edge), ctx->nameOf(capture.key.clock)); + auto failing_eps = get_failing_eps(i, 5); + for (auto &ep : failing_eps) + print_critical_path(ep, i); + log_break(); + } +} + +domain_id_t TimingAnalyser::domain_id(IdString cell, IdString clock_port, ClockEdge edge) +{ + return domain_id(ctx->cells.at(cell)->ports.at(clock_port).net, edge); +} +domain_id_t TimingAnalyser::domain_id(const NetInfo *net, ClockEdge edge) +{ + NPNR_ASSERT(net != nullptr); + ClockDomainKey key{net->name, edge}; + auto inserted = domain_to_id.emplace(key, domains.size()); + if (inserted.second) { + domains.emplace_back(key); + } + return inserted.first->second; +} +domain_id_t TimingAnalyser::domain_pair_id(domain_id_t launch, domain_id_t capture) +{ + ClockDomainPairKey key{launch, capture}; + auto inserted = pair_to_id.emplace(key, domain_pairs.size()); + if (inserted.second) { + domain_pairs.emplace_back(key); + } + return inserted.first->second; +} + +void TimingAnalyser::copy_domains(const CellPortKey &from, const CellPortKey &to, bool backward) +{ + auto &f = ports.at(from), &t = ports.at(to); + for (auto &dom : (backward ? f.required : f.arrival)) + (backward ? t.required : t.arrival)[dom.first]; +} + +CellInfo *TimingAnalyser::cell_info(const CellPortKey &key) { return ctx->cells.at(key.cell).get(); } + +PortInfo &TimingAnalyser::port_info(const CellPortKey &key) { return ctx->cells.at(key.cell)->ports.at(key.port); } + +/** LEGACY CODE BEGIN **/ + namespace { struct ClockEvent { @@ -86,7 +627,6 @@ struct CriticalPath }; typedef std::unordered_map<ClockPair, CriticalPath> CriticalPathMap; -typedef std::unordered_map<IdString, NetCriticalityInfo> NetCriticalityMap; struct Timing { @@ -96,7 +636,6 @@ struct Timing delay_t min_slack; CriticalPathMap *crit_path; DelayFrequency *slack_histogram; - NetCriticalityMap *net_crit; IdString async_clock; struct TimingData @@ -112,10 +651,9 @@ struct Timing }; Timing(Context *ctx, bool net_delays, bool update, CriticalPathMap *crit_path = nullptr, - DelayFrequency *slack_histogram = nullptr, NetCriticalityMap *net_crit = nullptr) + DelayFrequency *slack_histogram = nullptr) : ctx(ctx), net_delays(net_delays), update(update), min_slack(1.0e12 / ctx->setting<float>("target_freq")), - crit_path(crit_path), slack_histogram(slack_histogram), net_crit(net_crit), - async_clock(ctx->id("$async$")) + crit_path(crit_path), slack_histogram(slack_histogram), async_clock(ctx->id("$async$")) { } @@ -496,156 +1034,6 @@ struct Timing std::reverse(cp_ports.begin(), cp_ports.end()); } } - - if (net_crit) { - NPNR_ASSERT(crit_path); - // Go through in reverse topological order to set required times - for (auto net : boost::adaptors::reverse(topological_order)) { - if (!net_data.count(net)) - continue; - auto &nd_map = net_data.at(net); - for (auto &startdomain : nd_map) { - auto &nd = startdomain.second; - if (nd.false_startpoint) - continue; - if (startdomain.first.clock == async_clock) - continue; - if (nd.min_required.empty()) - nd.min_required.resize(net->users.size(), std::numeric_limits<delay_t>::max()); - delay_t net_min_required = std::numeric_limits<delay_t>::max(); - for (size_t i = 0; i < net->users.size(); i++) { - auto &usr = net->users.at(i); - auto net_delay = ctx->getNetinfoRouteDelay(net, usr); - int port_clocks; - TimingPortClass portClass = ctx->getPortTimingClass(usr.cell, usr.port, port_clocks); - if (portClass == TMG_REGISTER_INPUT || portClass == TMG_ENDPOINT) { - auto process_endpoint = [&](IdString clksig, ClockEdge edge, delay_t setup) { - delay_t period; - // Set default period - if (edge == startdomain.first.edge) { - period = clk_period; - } else { - period = clk_period / 2; - } - if (clksig != async_clock) { - if (ctx->nets.at(clksig)->clkconstr) { - if (edge == startdomain.first.edge) { - // same edge - period = ctx->nets.at(clksig)->clkconstr->period.minDelay(); - } else if (edge == RISING_EDGE) { - // falling -> rising - period = ctx->nets.at(clksig)->clkconstr->low.minDelay(); - } else if (edge == FALLING_EDGE) { - // rising -> falling - period = ctx->nets.at(clksig)->clkconstr->high.minDelay(); - } - } - } - nd.min_required.at(i) = std::min(period - setup, nd.min_required.at(i)); - }; - if (portClass == TMG_REGISTER_INPUT) { - for (int j = 0; j < port_clocks; j++) { - TimingClockingInfo clkInfo = ctx->getPortClockingInfo(usr.cell, usr.port, j); - const NetInfo *clknet = get_net_or_empty(usr.cell, clkInfo.clock_port); - IdString clksig = clknet ? clknet->name : async_clock; - process_endpoint(clksig, clknet ? clkInfo.edge : RISING_EDGE, - clkInfo.setup.maxDelay()); - } - } else { - process_endpoint(async_clock, RISING_EDGE, 0); - } - } - net_min_required = std::min(net_min_required, nd.min_required.at(i) - net_delay); - } - PortRef &drv = net->driver; - if (drv.cell == nullptr) - continue; - for (const auto &port : drv.cell->ports) { - if (port.second.type != PORT_IN || !port.second.net) - continue; - DelayQuad comb_delay; - bool is_path = ctx->getCellDelay(drv.cell, port.first, drv.port, comb_delay); - if (!is_path) - continue; - int cc; - auto pclass = ctx->getPortTimingClass(drv.cell, port.first, cc); - if (pclass != TMG_COMB_INPUT) - continue; - NetInfo *sink_net = port.second.net; - if (net_data.count(sink_net) && net_data.at(sink_net).count(startdomain.first)) { - auto &sink_nd = net_data.at(sink_net).at(startdomain.first); - if (sink_nd.min_required.empty()) - sink_nd.min_required.resize(sink_net->users.size(), - std::numeric_limits<delay_t>::max()); - for (size_t i = 0; i < sink_net->users.size(); i++) { - auto &user = sink_net->users.at(i); - if (user.cell == drv.cell && user.port == port.first) { - sink_nd.min_required.at(i) = std::min(sink_nd.min_required.at(i), - net_min_required - comb_delay.maxDelay()); - break; - } - } - } - } - } - } - std::unordered_map<ClockEvent, delay_t> worst_slack; - - // Assign slack values - for (auto &net_entry : net_data) { - const NetInfo *net = net_entry.first; - for (auto &startdomain : net_entry.second) { - auto &nd = startdomain.second; - if (startdomain.first.clock == async_clock) - continue; - if (nd.min_required.empty()) - continue; - auto &nc = (*net_crit)[net->name]; - if (nc.slack.empty()) - nc.slack.resize(net->users.size(), std::numeric_limits<delay_t>::max()); - - for (size_t i = 0; i < net->users.size(); i++) { - delay_t slack = nd.min_required.at(i) - - (nd.max_arrival + ctx->getNetinfoRouteDelay(net, net->users.at(i))); - - if (worst_slack.count(startdomain.first)) - worst_slack.at(startdomain.first) = std::min(worst_slack.at(startdomain.first), slack); - else - worst_slack[startdomain.first] = slack; - nc.slack.at(i) = slack; - } - if (ctx->debug) - log_break(); - } - } - // Assign criticality values - for (auto &net_entry : net_data) { - const NetInfo *net = net_entry.first; - for (auto &startdomain : net_entry.second) { - if (startdomain.first.clock == async_clock) - continue; - auto &nd = startdomain.second; - if (nd.min_required.empty()) - continue; - auto &nc = (*net_crit)[net->name]; - if (nc.slack.empty()) - continue; - if (nc.criticality.empty()) - nc.criticality.resize(net->users.size(), 0); - // Only consider intra-clock paths for criticality - if (!crit_path->count(ClockPair{startdomain.first, startdomain.first})) - continue; - delay_t dmax = crit_path->at(ClockPair{startdomain.first, startdomain.first}).path_delay; - for (size_t i = 0; i < net->users.size(); i++) { - float criticality = - 1.0f - ((float(nc.slack.at(i)) - float(worst_slack.at(startdomain.first))) / dmax); - nc.criticality.at(i) = std::min<double>(1.0, std::max<double>(0.0, criticality)); - } - nc.max_path_length = nd.max_path_length; - nc.cd_worst_slack = worst_slack.at(startdomain.first); - } - } - } return min_slack; } @@ -999,12 +1387,4 @@ void timing_analysis(Context *ctx, bool print_histogram, bool print_fmax, bool p } } -void get_criticalities(Context *ctx, NetCriticalityMap *net_crit) -{ - CriticalPathMap crit_paths; - net_crit->clear(); - Timing timing(ctx, true, true, &crit_paths, nullptr, net_crit); - timing.walk_paths(); -} - NEXTPNR_NAMESPACE_END diff --git a/common/timing.h b/common/timing.h index f1d18e8a..63c0fc74 100644 --- a/common/timing.h +++ b/common/timing.h @@ -24,6 +24,251 @@ NEXTPNR_NAMESPACE_BEGIN +struct CellPortKey +{ + CellPortKey(){}; + CellPortKey(IdString cell, IdString port) : cell(cell), port(port){}; + explicit CellPortKey(const PortRef &pr) + { + NPNR_ASSERT(pr.cell != nullptr); + cell = pr.cell->name; + port = pr.port; + } + IdString cell, port; + struct Hash + { + inline std::size_t operator()(const CellPortKey &arg) const noexcept + { + std::size_t seed = std::hash<IdString>()(arg.cell); + seed ^= std::hash<IdString>()(arg.port) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } + }; + inline bool operator==(const CellPortKey &other) const { return (cell == other.cell) && (port == other.port); } + inline bool operator!=(const CellPortKey &other) const { return (cell != other.cell) || (port != other.port); } + inline bool operator<(const CellPortKey &other) const + { + return cell == other.cell ? port < other.port : cell < other.cell; + } +}; + +struct NetPortKey +{ + IdString net; + size_t idx; + NetPortKey(){}; + explicit NetPortKey(IdString net) : net(net), idx(DRIVER_IDX){}; // driver + explicit NetPortKey(IdString net, size_t user) : net(net), idx(user){}; // user + + static const size_t DRIVER_IDX = std::numeric_limits<size_t>::max(); + + inline bool is_driver() const { return (idx == DRIVER_IDX); } + inline size_t user_idx() const + { + NPNR_ASSERT(idx != DRIVER_IDX); + return idx; + } + + struct Hash + { + std::size_t operator()(const NetPortKey &arg) const noexcept + { + std::size_t seed = std::hash<IdString>()(arg.net); + seed ^= std::hash<size_t>()(arg.idx) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } + }; + inline bool operator==(const NetPortKey &other) const { return (net == other.net) && (idx == other.idx); } +}; + +struct ClockDomainKey +{ + IdString clock; + ClockEdge edge; + ClockDomainKey(IdString clock_net, ClockEdge edge) : clock(clock_net), edge(edge){}; + // probably also need something here to deal with constraints + inline bool is_async() const { return clock == IdString(); } + + struct Hash + { + std::size_t operator()(const ClockDomainKey &arg) const noexcept + { + std::size_t seed = std::hash<IdString>()(arg.clock); + seed ^= std::hash<int>()(int(arg.edge)) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } + }; + inline bool operator==(const ClockDomainKey &other) const { return (clock == other.clock) && (edge == other.edge); } +}; + +typedef int domain_id_t; + +struct ClockDomainPairKey +{ + domain_id_t launch, capture; + ClockDomainPairKey(domain_id_t launch, domain_id_t capture) : launch(launch), capture(capture){}; + inline bool operator==(const ClockDomainPairKey &other) const + { + return (launch == other.launch) && (capture == other.capture); + } + struct Hash + { + std::size_t operator()(const ClockDomainPairKey &arg) const noexcept + { + std::size_t seed = std::hash<domain_id_t>()(arg.launch); + seed ^= std::hash<domain_id_t>()(arg.capture) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + return seed; + } + }; +}; + +struct TimingAnalyser +{ + public: + TimingAnalyser(Context *ctx) : ctx(ctx){}; + void setup(); + void run(); + void print_report(); + + float get_criticality(CellPortKey port) const { return ports.at(port).worst_crit; } + float get_setup_slack(CellPortKey port) const { return ports.at(port).worst_setup_slack; } + float get_domain_setup_slack(CellPortKey port) const + { + delay_t slack = std::numeric_limits<delay_t>::max(); + for (const auto &dp : ports.at(port).domain_pairs) + slack = std::min(slack, domain_pairs.at(dp.first).worst_setup_slack); + return slack; + } + + bool setup_only = false; + bool verbose_mode = false; + + private: + void init_ports(); + void get_cell_delays(); + void get_route_delays(); + void topo_sort(); + void setup_port_domains(); + + void reset_times(); + + void walk_forward(); + void walk_backward(); + + void compute_slack(); + void compute_criticality(); + + void print_fmax(); + // get the N most failing endpoints for a given domain pair + std::vector<CellPortKey> get_failing_eps(domain_id_t domain_pair, int count); + // print the critical path for an endpoint and domain pair + void print_critical_path(CellPortKey endpoint, domain_id_t domain_pair); + + const DelayPair init_delay{std::numeric_limits<delay_t>::max(), std::numeric_limits<delay_t>::lowest()}; + + // Set arrival/required times if more/less than the current value + void set_arrival_time(CellPortKey target, domain_id_t domain, DelayPair arrival, int path_length, + CellPortKey prev = CellPortKey()); + void set_required_time(CellPortKey target, domain_id_t domain, DelayPair required, int path_length, + CellPortKey prev = CellPortKey()); + + // To avoid storing the domain tag structure (which could get large when considering more complex constrained tag + // cases), assign each domain an ID and use that instead + // An arrival or required time entry. Stores both the min/max delays; and the traversal to reach them for critical + // path reporting + struct ArrivReqTime + { + DelayPair value; + CellPortKey bwd_min, bwd_max; + int path_length; + }; + // Data per port-domain tuple + struct PortDomainPairData + { + delay_t setup_slack = std::numeric_limits<delay_t>::max(), hold_slack = std::numeric_limits<delay_t>::max(); + delay_t budget = std::numeric_limits<delay_t>::max(); + int max_path_length = 0; + float criticality = 0; + }; + + // A cell timing arc, used to cache cell timings and reduce the number of potentially-expensive Arch API calls + struct CellArc + { + + enum ArcType + { + COMBINATIONAL, + SETUP, + HOLD, + CLK_TO_Q + } type; + + IdString other_port; + DelayQuad value; + // Clock polarity, not used for combinational arcs + ClockEdge edge; + + CellArc(ArcType type, IdString other_port, DelayQuad value) + : type(type), other_port(other_port), value(value), edge(RISING_EDGE){}; + CellArc(ArcType type, IdString other_port, DelayQuad value, ClockEdge edge) + : type(type), other_port(other_port), value(value), edge(edge){}; + }; + + // Timing data for every cell port + struct PerPort + { + CellPortKey cell_port; + NetPortKey net_port; + PortType type; + // per domain timings + std::unordered_map<domain_id_t, ArrivReqTime> arrival; + std::unordered_map<domain_id_t, ArrivReqTime> required; + std::unordered_map<domain_id_t, PortDomainPairData> domain_pairs; + // cell timing arcs to (outputs)/from (inputs) from this port + std::vector<CellArc> cell_arcs; + // routing delay into this port (input ports only) + DelayPair route_delay; + // worst criticality and slack across domain pairs + float worst_crit; + delay_t worst_setup_slack, worst_hold_slack; + }; + + struct PerDomain + { + PerDomain(ClockDomainKey key) : key(key){}; + ClockDomainKey key; + // these are pairs (signal port; clock port) + std::vector<std::pair<CellPortKey, IdString>> startpoints, endpoints; + }; + + struct PerDomainPair + { + PerDomainPair(ClockDomainPairKey key) : key(key){}; + ClockDomainPairKey key; + DelayPair period; + delay_t worst_setup_slack, worst_hold_slack; + }; + + CellInfo *cell_info(const CellPortKey &key); + PortInfo &port_info(const CellPortKey &key); + + domain_id_t domain_id(IdString cell, IdString clock_port, ClockEdge edge); + domain_id_t domain_id(const NetInfo *net, ClockEdge edge); + domain_id_t domain_pair_id(domain_id_t launch, domain_id_t capture); + + void copy_domains(const CellPortKey &from, const CellPortKey &to, bool backwards); + + std::unordered_map<CellPortKey, PerPort, CellPortKey::Hash> ports; + std::unordered_map<ClockDomainKey, domain_id_t, ClockDomainKey::Hash> domain_to_id; + std::unordered_map<ClockDomainPairKey, domain_id_t, ClockDomainPairKey::Hash> pair_to_id; + std::vector<PerDomain> domains; + std::vector<PerDomainPair> domain_pairs; + + std::vector<CellPortKey> topological_order; + + Context *ctx; +}; + // Evenly redistribute the total path slack amongst all sinks on each path void assign_budget(Context *ctx, bool quiet = false); @@ -32,19 +277,6 @@ void assign_budget(Context *ctx, bool quiet = false); void timing_analysis(Context *ctx, bool slack_histogram = true, bool print_fmax = true, bool print_path = false, bool warn_on_failure = false); -// Data for the timing optimisation algorithm -struct NetCriticalityInfo -{ - // One each per user - std::vector<delay_t> slack; - std::vector<float> criticality; - unsigned max_path_length = 0; - delay_t cd_worst_slack = std::numeric_limits<delay_t>::max(); -}; - -typedef std::unordered_map<IdString, NetCriticalityInfo> NetCriticalityMap; -void get_criticalities(Context *ctx, NetCriticalityMap *net_crit); - NEXTPNR_NAMESPACE_END #endif diff --git a/common/timing_opt.cc b/common/timing_opt.cc index 28b7f2cf..51c27cc6 100644 --- a/common/timing_opt.cc +++ b/common/timing_opt.cc @@ -79,16 +79,17 @@ NEXTPNR_NAMESPACE_BEGIN class TimingOptimiser { public: - TimingOptimiser(Context *ctx, TimingOptCfg cfg) : ctx(ctx), cfg(cfg){}; + TimingOptimiser(Context *ctx, TimingOptCfg cfg) : ctx(ctx), cfg(cfg), tmg(ctx){}; bool optimise() { log_info("Running timing-driven placement optimisation...\n"); ctx->lock(); if (ctx->verbose) timing_analysis(ctx, false, true, false, false); + tmg.setup(); for (int i = 0; i < 30; i++) { log_info(" Iteration %d...\n", i); - get_criticalities(ctx, &net_crit); + tmg.run(); setup_delay_limits(); auto crit_paths = find_crit_paths(0.98, 50000); for (auto &path : crit_paths) @@ -109,18 +110,14 @@ class TimingOptimiser for (auto usr : ni->users) { max_net_delay[std::make_pair(usr.cell->name, usr.port)] = std::numeric_limits<delay_t>::max(); } - if (!net_crit.count(net.first)) - continue; - auto &nc = net_crit.at(net.first); - if (nc.slack.empty()) - continue; for (size_t i = 0; i < ni->users.size(); i++) { auto &usr = ni->users.at(i); delay_t net_delay = ctx->getNetinfoRouteDelay(ni, usr); - if (nc.max_path_length != 0) { - max_net_delay[std::make_pair(usr.cell->name, usr.port)] = - net_delay + ((nc.slack.at(i) - nc.cd_worst_slack) / 10); - } + delay_t slack = tmg.get_setup_slack(CellPortKey(usr)); + delay_t domain_slack = tmg.get_domain_setup_slack(CellPortKey(usr)); + if (slack == std::numeric_limits<delay_t>::max()) + continue; + max_net_delay[std::make_pair(usr.cell->name, usr.port)] = net_delay + ((slack - domain_slack) / 10); } } } @@ -283,12 +280,18 @@ class TimingOptimiser for (auto net : netnames) { if (crit_nets.size() >= max_count) break; - if (!net_crit.count(net)) - continue; - auto crit_user = std::max_element(net_crit[net].criticality.begin(), net_crit[net].criticality.end()); - if (*crit_user > crit_thresh) - crit_nets.push_back( - std::make_pair(ctx->nets[net].get(), crit_user - net_crit[net].criticality.begin())); + float highest_crit = 0; + size_t crit_user_idx = 0; + NetInfo *ni = ctx->nets.at(net).get(); + for (size_t i = 0; i < ni->users.size(); i++) { + float crit = tmg.get_criticality(CellPortKey(ni->users.at(i))); + if (crit > highest_crit) { + highest_crit = crit; + crit_user_idx = i; + } + } + if (highest_crit > crit_thresh) + crit_nets.push_back(std::make_pair(ni, crit_user_idx)); } auto port_user_index = [](CellInfo *cell, PortInfo &port) -> size_t { @@ -325,8 +328,6 @@ class TimingOptimiser NetInfo *pn = port.second.net; if (pn == nullptr) continue; - if (!net_crit.count(pn->name) || net_crit.at(pn->name).criticality.empty()) - continue; int ccount; DelayQuad combDelay; TimingPortClass tpclass = ctx->getPortTimingClass(cell, port.first, ccount); @@ -336,7 +337,7 @@ class TimingOptimiser if (!is_path) continue; size_t user_idx = port_user_index(cell, port.second); - float usr_crit = net_crit.at(pn->name).criticality.at(user_idx); + float usr_crit = tmg.get_criticality(CellPortKey(cell->name, port.first)); if (used_ports.count(&(pn->users.at(user_idx)))) continue; if (usr_crit >= max_crit) { @@ -364,8 +365,7 @@ class TimingOptimiser NetInfo *pn = port.second.net; if (pn == nullptr) continue; - if (!net_crit.count(pn->name) || net_crit.at(pn->name).criticality.empty()) - continue; + int ccount; DelayQuad combDelay; TimingPortClass tpclass = ctx->getPortTimingClass(cell, port.first, ccount); @@ -374,12 +374,12 @@ class TimingOptimiser bool is_path = ctx->getCellDelay(cell, fwd_cursor->port, port.first, combDelay); if (!is_path) continue; - auto &crits = net_crit.at(pn->name).criticality; - for (size_t i = 0; i < crits.size(); i++) { + for (size_t i = 0; i < pn->users.size(); i++) { if (used_ports.count(&(pn->users.at(i)))) continue; - if (crits.at(i) >= max_crit) { - max_crit = crits.at(i); + float crit = tmg.get_criticality(CellPortKey(pn->users.at(i))); + if (crit >= max_crit) { + max_crit = crit; crit_sink = std::make_pair(pn, i); } } @@ -420,12 +420,7 @@ class TimingOptimiser for (auto port : path) { if (ctx->debug) { - float crit = 0; - NetInfo *pn = port->cell->ports.at(port->port).net; - if (net_crit.count(pn->name) && !net_crit.at(pn->name).criticality.empty()) - for (size_t i = 0; i < pn->users.size(); i++) - if (pn->users.at(i).cell == port->cell && pn->users.at(i).port == port->port) - crit = net_crit.at(pn->name).criticality.at(i); + float crit = tmg.get_criticality(CellPortKey(*port)); log_info(" %s.%s at %s crit %0.02f\n", port->cell->name.c_str(ctx), port->port.c_str(ctx), ctx->nameOfBel(port->cell->bel), crit); } @@ -613,10 +608,9 @@ class TimingOptimiser std::unordered_map<BelId, std::unordered_set<IdString>> bel_candidate_cells; // Map cell ports to net delay limit std::unordered_map<std::pair<IdString, IdString>, delay_t> max_net_delay; - // Criticality data from timing analysis - NetCriticalityMap net_crit; Context *ctx; TimingOptCfg cfg; + TimingAnalyser tmg; }; bool timing_opt(Context *ctx, TimingOptCfg cfg) { return TimingOptimiser(ctx, cfg).optimise(); } diff --git a/common/util.h b/common/util.h index 55718344..540646c7 100644 --- a/common/util.h +++ b/common/util.h @@ -181,6 +181,98 @@ template <typename ForwardRange> inline auto get_only_value(ForwardRange r) return get_only_value(b, e); } +// From Yosys +// https://github.com/YosysHQ/yosys/blob/0fb4224ebca86156a1296b9210116d9a9cbebeed/kernel/utils.h#L131 +template <typename T, typename C = std::less<T>> struct TopoSort +{ + bool analyze_loops, found_loops; + std::map<T, std::set<T, C>, C> database; + std::set<std::set<T, C>> loops; + std::vector<T> sorted; + + TopoSort() + { + analyze_loops = true; + found_loops = false; + } + + void node(T n) + { + if (database.count(n) == 0) + database[n] = std::set<T, C>(); + } + + void edge(T left, T right) + { + node(left); + database[right].insert(left); + } + + void sort_worker(const T &n, std::set<T, C> &marked_cells, std::set<T, C> &active_cells, + std::vector<T> &active_stack) + { + if (active_cells.count(n)) { + found_loops = true; + if (analyze_loops) { + std::set<T, C> loop; + for (int i = int(active_stack.size()) - 1; i >= 0; i--) { + loop.insert(active_stack[i]); + if (active_stack[i] == n) + break; + } + loops.insert(loop); + } + return; + } + + if (marked_cells.count(n)) + return; + + if (!database.at(n).empty()) { + if (analyze_loops) + active_stack.push_back(n); + active_cells.insert(n); + + for (auto &left_n : database.at(n)) + sort_worker(left_n, marked_cells, active_cells, active_stack); + + if (analyze_loops) + active_stack.pop_back(); + active_cells.erase(n); + } + + marked_cells.insert(n); + sorted.push_back(n); + } + + bool sort() + { + loops.clear(); + sorted.clear(); + found_loops = false; + + std::set<T, C> marked_cells; + std::set<T, C> active_cells; + std::vector<T> active_stack; + + for (auto &it : database) + sort_worker(it.first, marked_cells, active_cells, active_stack); + + NPNR_ASSERT(sorted.size() == database.size()); + return !found_loops; + } +}; + +template <typename T> struct reversed_range_t +{ + T &obj; + explicit reversed_range_t(T &obj) : obj(obj){}; + auto begin() { return obj.rbegin(); } + auto end() { return obj.rend(); } +}; + +template <typename T> reversed_range_t<T> reversed_range(T &obj) { return reversed_range_t<T>(obj); } + NEXTPNR_NAMESPACE_END #endif diff --git a/ecp5/arch_place.cc b/ecp5/arch_place.cc index 5565a01c..57c3b181 100644 --- a/ecp5/arch_place.cc +++ b/ecp5/arch_place.cc @@ -95,8 +95,8 @@ bool Arch::isBelLocationValid(BelId bel) const void Arch::permute_luts() { - NetCriticalityMap nc; - get_criticalities(getCtx(), &nc); + TimingAnalyser tmg(getCtx()); + tmg.setup(); std::unordered_map<PortInfo *, size_t> port_to_user; for (auto net : sorted(nets)) { @@ -121,13 +121,7 @@ void Arch::permute_luts() ci->ports[port_names.at(i)].type = PORT_IN; } auto &port = ci->ports.at(port_names.at(i)); - float crit = 0; - if (port.net != nullptr && nc.count(port.net->name)) { - auto &n = nc.at(port.net->name); - size_t usr = port_to_user.at(&port); - if (usr < n.criticality.size()) - crit = n.criticality.at(usr); - } + float crit = (port.net == nullptr) ? 0 : tmg.get_criticality(CellPortKey(ci->name, port_names.at(i))); orig_nets.push_back(port.net); inputs.emplace_back(crit, i); } diff --git a/fpga_interchange/README.md b/fpga_interchange/README.md index df832b94..78dd23ce 100644 --- a/fpga_interchange/README.md +++ b/fpga_interchange/README.md @@ -36,29 +36,25 @@ library. The current implementation is missing essential features for place and route. As these features are added, this implementation will become more useful. - - [ ] Logical netlist macro expansion is not implemented, meaning that any - macro primitives are unplaceable. Common macro primitives examples are - differential IO buffers (IBUFDS) and some LUT RAM (e.g. RAM64X1D). - [ ] The router lookahead is missing, meaning that router runtime performance will be terrible. - - [ ] The routing graph that is currently emitted does not have ground and - VCC networks, so all signals must currently be tied to an IO signal. - Site pins being tied to constants also needs handling so that site - local inverters are used rather than routing signals suboptimally. - [ ] Pseudo pips (e.g. pips that consume BELs and or site resources) should block their respective resources. This effects designs that have some routing in place before placement. - [ ] Pseudo site pips (e.g. site pips that route through BELs) should block their respective resources. Without this, using some pseudo site pips could result in invalid placements. + - [ ] Implemented site router lacks important features for tight packing. + Also the current site router is relatively untested, so legal + configurations may be rejected and illegal configurations may be + accepted. + - [ ] Logical netlist macro expansion is not implemented, meaning that any + macro primitives are unplaceable. Common macro primitives examples are + differential IO buffers (IBUFDS) and some LUT RAM (e.g. RAM64X1D). - [ ] Timing information is missing from the FPGA interchange device database, so it is also currently missing from the FPGA interchange architecture. Once timing information is added to the device database schema, it needs to be added to the architecture. - - [ ] Implemented site router lacks important features for tight packing, - namely LUT rotation. Also the current site router is relatively - untested, so legal configurations may be rejected and illegal - configurations may be accepted. #### FPGA interchange fabrics diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc index dc99f1cd..e9dee580 100644 --- a/fpga_interchange/arch.cc +++ b/fpga_interchange/arch.cc @@ -158,6 +158,7 @@ Arch::Arch(ArchArgs args) : args(args) int tile_type_index = 0; size_t max_tag_count = 0; + for (const TileTypeInfoPOD &tile_type : chip_info->tile_types) { max_tag_count = std::max(max_tag_count, tile_type.tags.size()); @@ -192,6 +193,50 @@ Arch::Arch(ArchArgs args) : args(args) } } + // Initially LutElement vectors for each tile type. + tile_type_index = 0; + lut_elements.resize(chip_info->tile_types.size()); + for (const TileTypeInfoPOD &tile_type : chip_info->tile_types) { + std::vector<LutElement> &elements = lut_elements[tile_type_index++]; + elements.reserve(tile_type.lut_elements.size()); + for (auto &lut_element : tile_type.lut_elements) { + elements.emplace_back(); + + LutElement &element = elements.back(); + element.width = lut_element.width; + for (auto &lut_bel : lut_element.lut_bels) { + auto result = element.lut_bels.emplace(IdString(lut_bel.name), LutBel()); + NPNR_ASSERT(result.second); + LutBel &lut = result.first->second; + + lut.low_bit = lut_bel.low_bit; + lut.high_bit = lut_bel.high_bit; + + lut.pins.reserve(lut_bel.pins.size()); + for (size_t i = 0; i < lut_bel.pins.size(); ++i) { + IdString pin(lut_bel.pins[i]); + lut.pins.push_back(pin); + lut.pin_to_index[pin] = i; + } + } + + element.compute_pin_order(); + } + } + + // Map lut cell types to their LutCellPOD + for (const LutCellPOD &lut_cell : chip_info->cell_map->lut_cells) { + IdString cell_type(lut_cell.cell); + auto result = lut_cells.emplace(cell_type, &lut_cell); + NPNR_ASSERT(result.second); + } + + raw_bin_constant = std::regex("[01]+", std::regex_constants::ECMAScript | std::regex_constants::optimize); + verilog_bin_constant = + std::regex("([0-9]+)'b([01]+)", std::regex_constants::ECMAScript | std::regex_constants::optimize); + verilog_hex_constant = + std::regex("([0-9]+)'h([0-9a-fA-F]+)", std::regex_constants::ECMAScript | std::regex_constants::optimize); + default_tags.resize(max_tag_count); } @@ -603,6 +648,7 @@ bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay bool Arch::pack() { + decode_lut_cells(); merge_constant_nets(); pack_ports(); return true; @@ -666,11 +712,72 @@ bool Arch::route() } else { log_error("FPGA interchange architecture does not support router '%s'\n", router.c_str()); } + + if (result) { + result = route_vcc_to_unused_lut_pins(); + } + getCtx()->attrs[getCtx()->id("step")] = std::string("route"); archInfoToAttributes(); + return result; } +bool Arch::route_vcc_to_unused_lut_pins() +{ + std::string router = str_or_default(settings, id("router"), defaultRouter); + + // Fixup LUT vcc pins. + IdString vcc_net_name(chip_info->constants->vcc_net_name); + for (BelId bel : getBels()) { + CellInfo *cell = getBoundBelCell(bel); + if (cell == nullptr) { + continue; + } + + if (cell->lut_cell.vcc_pins.empty()) { + continue; + } + + for (auto bel_pin : cell->lut_cell.vcc_pins) { + PortInfo port_info; + port_info.name = bel_pin; + port_info.type = PORT_IN; + port_info.net = nullptr; + + WireId lut_pin_wire = getBelPinWire(bel, bel_pin); + auto iter = wire_to_net.find(lut_pin_wire); + if (iter != wire_to_net.end()) { + if (iter->second != nullptr) { + // This pin is now used by a route through. + continue; + } + } + + auto result = cell->ports.emplace(bel_pin, port_info); + if (result.second) { + cell->cell_bel_pins[bel_pin].push_back(bel_pin); + connectPort(vcc_net_name, cell->name, bel_pin); + cell->const_ports.emplace(bel_pin); + } else { + NPNR_ASSERT(result.first->second.net == getNetByAlias(vcc_net_name)); + auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector<IdString>({bel_pin})); + NPNR_ASSERT(result2.first->second.at(0) == bel_pin); + NPNR_ASSERT(result2.first->second.size() == 1); + } + } + } + + if (router == "router1") { + return router1(getCtx(), Router1Cfg(getCtx())); + } else if (router == "router2") { + router2(getCtx(), Router2Cfg(getCtx())); + return true; + } else { + log_error("FPGA interchange architecture does not support router '%s'\n", router.c_str()); + } +} + // ----------------------------------------------------------------------- std::vector<GraphicElement> Arch::getDecalGraphics(DecalId decal) const { return {}; } @@ -791,7 +898,20 @@ const std::vector<std::string> Arch::availableRouters = {"router1", "router2"}; void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants) { cell->cell_mapping = mapping; - cell->cell_bel_pins.clear(); + if (cell->lut_cell.pins.empty()) { + cell->cell_bel_pins.clear(); + } else { + std::vector<IdString> cell_pin_to_remove; + for (auto port_pair : cell->cell_bel_pins) { + if (!cell->lut_cell.lut_pins.count(port_pair.first)) { + cell_pin_to_remove.push_back(port_pair.first); + } + } + + for (IdString cell_pin : cell_pin_to_remove) { + NPNR_ASSERT(cell->cell_bel_pins.erase(cell_pin)); + } + } for (IdString const_port : cell->const_ports) { NPNR_ASSERT(cell->ports.erase(const_port)); } @@ -805,6 +925,11 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants) IdString cell_pin(pin_map.cell_pin); IdString bel_pin(pin_map.bel_pin); + // Skip assigned LUT pins, as they are already mapped! + if (cell->lut_cell.lut_pins.count(cell_pin) && cell->cell_bel_pins.count(cell_pin)) { + continue; + } + if (cell_pin.str(this) == "GND") { if (bind_constants) { PortInfo port_info; @@ -869,11 +994,17 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants) IdString cell_pin(pin_map.cell_pin); IdString bel_pin(pin_map.bel_pin); + // Skip assigned LUT pins, as they are already mapped! + if (cell->lut_cell.lut_pins.count(cell_pin) && cell->cell_bel_pins.count(cell_pin)) { + continue; + } + if (cell_pin.str(this) == "GND") { if (bind_constants) { PortInfo port_info; port_info.name = bel_pin; port_info.type = PORT_IN; + port_info.net = nullptr; auto result = cell->ports.emplace(bel_pin, port_info); if (result.second) { @@ -895,6 +1026,7 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants) PortInfo port_info; port_info.name = bel_pin; port_info.type = PORT_IN; + port_info.net = nullptr; auto result = cell->ports.emplace(bel_pin, port_info); if (result.second) { @@ -1135,6 +1267,70 @@ void Arch::report_invalid_bel(BelId bel, CellInfo *cell) const nameOfBel(bel), mapping); } +void Arch::read_lut_equation(nextpnr::DynamicBitarray<> *equation, const Property &equation_parameter) const +{ + equation->fill(false); + std::string eq_str = equation_parameter.as_string(); + std::smatch results; + if (std::regex_match(eq_str, results, raw_bin_constant)) { + size_t bit_idx = 0; + const std::string &bits = results[0]; + NPNR_ASSERT(bits.size() <= equation->size()); + for (auto bit = bits.rbegin(); bit != bits.rend(); ++bit) { + if (*bit == '0') { + equation->set(bit_idx++, false); + } else { + NPNR_ASSERT(*bit == '1'); + equation->set(bit_idx++, true); + } + } + } else if (std::regex_match(eq_str, results, verilog_bin_constant)) { + int iwidth = std::stoi(results[1]); + NPNR_ASSERT(iwidth >= 0); + size_t width = iwidth; + std::string bits = results[2]; + NPNR_ASSERT(width <= equation->size()); + NPNR_ASSERT(bits.size() <= width); + size_t bit_idx = 0; + for (auto bit = bits.rbegin(); bit != bits.rend(); ++bit) { + if (*bit == '0') { + equation->set(bit_idx++, false); + } else { + NPNR_ASSERT(*bit == '1'); + equation->set(bit_idx++, true); + } + } + } else { + NPNR_ASSERT(false); + } +} + +void Arch::decode_lut_cells() +{ + for (auto &cell_pair : cells) { + CellInfo *cell = cell_pair.second.get(); + auto iter = lut_cells.find(cell->type); + if (iter == lut_cells.end()) { + cell->lut_cell.pins.clear(); + cell->lut_cell.equation.clear(); + continue; + } + + const LutCellPOD &lut_cell = *iter->second; + + cell->lut_cell.pins.reserve(lut_cell.input_pins.size()); + for (uint32_t pin : lut_cell.input_pins) { + cell->lut_cell.pins.push_back(IdString(pin)); + cell->lut_cell.lut_pins.emplace(IdString(pin)); + } + + IdString equation_parameter(lut_cell.parameter); + const Property &equation = cell->params.at(equation_parameter); + cell->lut_cell.equation.resize(1 << cell->lut_cell.pins.size()); + read_lut_equation(&cell->lut_cell.equation, equation); + } +} + // Instance constraint templates. template void Arch::ArchConstraints::bindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); template void Arch::ArchConstraints::unbindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange); diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h index 13cab02f..16c79e8a 100644 --- a/fpga_interchange/arch.h +++ b/fpga_interchange/arch.h @@ -28,6 +28,7 @@ #include <iostream> +#include <regex> #include "constraints.h" #include "dedicated_interconnect.h" #include "site_router.h" @@ -69,7 +70,8 @@ NPNR_PACKED_STRUCT(struct BelInfoPOD { int16_t site; int16_t site_variant; // some sites have alternative types int16_t category; - int16_t synthetic; + int8_t synthetic; + int8_t lut_element; RelPtr<int32_t> pin_map; // Index into CellMapPOD::cell_bel_map }); @@ -119,6 +121,18 @@ NPNR_PACKED_STRUCT(struct ConstraintTagPOD { RelSlice<int32_t> states; // constid }); +NPNR_PACKED_STRUCT(struct LutBelPOD { + uint32_t name; // constid + RelSlice<int32_t> pins; // constid + uint32_t low_bit; + uint32_t high_bit; +}); + +NPNR_PACKED_STRUCT(struct LutElementPOD { + int32_t width; + RelSlice<LutBelPOD> lut_bels; +}); + NPNR_PACKED_STRUCT(struct TileTypeInfoPOD { int32_t name; // Tile type constid @@ -130,6 +144,8 @@ NPNR_PACKED_STRUCT(struct TileTypeInfoPOD { RelSlice<ConstraintTagPOD> tags; + RelSlice<LutElementPOD> lut_elements; + RelSlice<int32_t> site_types; // constid }); @@ -190,12 +206,20 @@ NPNR_PACKED_STRUCT(struct CellBelMapPOD { RelSlice<CellConstraintPOD> constraints; }); +NPNR_PACKED_STRUCT(struct LutCellPOD { + int32_t cell; // constid + RelSlice<int32_t> input_pins; // constids + int32_t parameter; +}); + NPNR_PACKED_STRUCT(struct CellMapPOD { // Cell names supported in this arch. RelSlice<int32_t> cell_names; // constids RelSlice<int32_t> cell_bel_buckets; // constids RelSlice<CellBelMapPOD> cell_bel_map; + + RelSlice<LutCellPOD> lut_cells; }); NPNR_PACKED_STRUCT(struct PackagePinPOD { @@ -1362,6 +1386,7 @@ struct Arch : ArchAPI<ArchRanges> void place_iobufs(WireId pad_wire, NetInfo *net, const std::unordered_set<CellInfo *> &tightly_attached_bels, std::unordered_set<CellInfo *> *placed_cells); void pack_ports(); + void decode_lut_cells(); bool pack() override; bool place() override; bool route() override; @@ -1706,6 +1731,14 @@ struct Arch : ArchAPI<ArchRanges> std::vector<IdString> no_pins; IdString gnd_cell_pin; IdString vcc_cell_pin; + std::vector<std::vector<LutElement>> lut_elements; + std::unordered_map<IdString, const LutCellPOD *> lut_cells; + + std::regex raw_bin_constant; + std::regex verilog_bin_constant; + std::regex verilog_hex_constant; + void read_lut_equation(nextpnr::DynamicBitarray<> *equation, const Property &equation_parameter) const; + bool route_vcc_to_unused_lut_pins(); }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/archdefs.h b/fpga_interchange/archdefs.h index 33d999bb..e355a6c4 100644 --- a/fpga_interchange/archdefs.h +++ b/fpga_interchange/archdefs.h @@ -22,6 +22,8 @@ #error Include "archdefs.h" via "nextpnr.h" only. #endif +#include "luts.h" + NEXTPNR_NAMESPACE_BEGIN #include <cstdint> @@ -107,6 +109,7 @@ struct ArchCellInfo int32_t cell_mapping; std::unordered_map<IdString, std::vector<IdString>> cell_bel_pins; std::unordered_set<IdString> const_ports; + LutCell lut_cell; }; NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/examples/counter/Makefile b/fpga_interchange/examples/counter/Makefile new file mode 100644 index 00000000..27d20cdf --- /dev/null +++ b/fpga_interchange/examples/counter/Makefile @@ -0,0 +1,8 @@ +DESIGN := counter +DESIGN_TOP := top +PACKAGE := cpg236 + +include ../template.mk + +build/counter.json: counter.v | build + yosys -c run.tcl diff --git a/fpga_interchange/examples/counter/counter.v b/fpga_interchange/examples/counter/counter.v new file mode 100644 index 00000000..00f52a20 --- /dev/null +++ b/fpga_interchange/examples/counter/counter.v @@ -0,0 +1,15 @@ +module top(input clk, input rst, output [7:4] io_led); + +reg [31:0] counter = 32'b0; + +assign io_led = counter >> 22; + +always @(posedge clk) +begin + if(rst) + counter <= 32'b0; + else + counter <= counter + 1; +end + +endmodule diff --git a/fpga_interchange/examples/counter/counter.xdc b/fpga_interchange/examples/counter/counter.xdc new file mode 100644 index 00000000..7cbe67f6 --- /dev/null +++ b/fpga_interchange/examples/counter/counter.xdc @@ -0,0 +1,22 @@ +## basys3 breakout board +set_property PACKAGE_PIN W5 [get_ports clk] +set_property PACKAGE_PIN V17 [get_ports rst] +#set_property PACKAGE_PIN U16 [get_ports io_led[0]] +#set_property PACKAGE_PIN E19 [get_ports io_led[1]] +#set_property PACKAGE_PIN U19 [get_ports io_led[2]] +#set_property PACKAGE_PIN V19 [get_ports io_led[3]] +set_property PACKAGE_PIN U16 [get_ports io_led[4]] +set_property PACKAGE_PIN E19 [get_ports io_led[5]] +set_property PACKAGE_PIN U19 [get_ports io_led[6]] +set_property PACKAGE_PIN V19 [get_ports io_led[7]] + +set_property IOSTANDARD LVCMOS33 [get_ports clk] +set_property IOSTANDARD LVCMOS33 [get_ports rst] +set_property IOSTANDARD LVCMOS33 [get_ports io_led[4]] +set_property IOSTANDARD LVCMOS33 [get_ports io_led[5]] +set_property IOSTANDARD LVCMOS33 [get_ports io_led[6]] +set_property IOSTANDARD LVCMOS33 [get_ports io_led[7]] +#set_property IOSTANDARD LVCMOS33 [get_ports io_led[0]] +#set_property IOSTANDARD LVCMOS33 [get_ports io_led[1]] +#set_property IOSTANDARD LVCMOS33 [get_ports io_led[2]] +#set_property IOSTANDARD LVCMOS33 [get_ports io_led[3]] diff --git a/fpga_interchange/examples/counter/run.tcl b/fpga_interchange/examples/counter/run.tcl new file mode 100644 index 00000000..245aab04 --- /dev/null +++ b/fpga_interchange/examples/counter/run.tcl @@ -0,0 +1,15 @@ +yosys -import + +read_verilog counter.v + +synth_xilinx -nolutram -nowidelut -nosrl -nocarry -nodsp +techmap -map ../remap.v + +# opt_expr -undriven makes sure all nets are driven, if only by the $undef +# net. +opt_expr -undriven +opt_clean + +setundef -zero -params + +write_json build/counter.json diff --git a/fpga_interchange/examples/remap.v b/fpga_interchange/examples/remap.v new file mode 100644 index 00000000..6dfc0b4a --- /dev/null +++ b/fpga_interchange/examples/remap.v @@ -0,0 +1,11 @@ +module INV(input I, output O); + +LUT1 #(.INIT(2'b01)) _TECHMAP_REPLACE_ (.I0(I), .O(O)); + +endmodule + +module BUF(input I, output O); + +LUT1 #(.INIT(2'b10)) _TECHMAP_REPLACE_ (.I0(I), .O(O)); + +endmodule diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc new file mode 100644 index 00000000..49f934a4 --- /dev/null +++ b/fpga_interchange/luts.cc @@ -0,0 +1,364 @@ +/* + * 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 "nextpnr.h" + +#include "log.h" +#include "luts.h" + +NEXTPNR_NAMESPACE_BEGIN + +bool rotate_and_merge_lut_equation(std::vector<LogicLevel> *result, const LutBel &lut_bel, + const nextpnr::DynamicBitarray<> &old_equation, const std::vector<int32_t> &pin_map, + uint32_t used_pins) +{ + // pin_map maps pin indicies from the old pin to the new pin. + // So a reversal of a LUT4 would have a pin map of: + // pin_map[0] = 3; + // pin_map[1] = 2; + // pin_map[2] = 1; + // pin_map[3] = 0; + + size_t bel_width = 1 << lut_bel.pins.size(); + for (size_t bel_address = 0; bel_address < bel_width; ++bel_address) { + bool address_reachable = true; + size_t cell_address = 0; + for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) { + // This address line is 0, so don't translate this bit to the cell + // address. + if ((bel_address & (1 << bel_pin_idx)) == 0) { + // This pin is unused, so the line will be tied high, this + // address is unreachable. + if ((used_pins & (1 << bel_pin_idx)) == 0) { + address_reachable = false; + break; + } + + continue; + } + + auto cell_pin_idx = pin_map[bel_pin_idx]; + + // Is this BEL pin used for this cell? + if (cell_pin_idx < 0) { + // This BEL pin is not used for the LUT cell, skip + continue; + } + + cell_address |= (1 << cell_pin_idx); + } + + if (!address_reachable) { + continue; + } + + bel_address += lut_bel.low_bit; + if (old_equation.get(cell_address)) { + if ((*result)[bel_address] == LL_Zero) { + // Output equation has a conflict! + return false; + } + + (*result)[bel_address] = LL_One; + } else { + if ((*result)[bel_address] == LL_One) { + // Output equation has a conflict! + return false; + } + (*result)[bel_address] = LL_Zero; + } + } + + return true; +} + +static constexpr bool kCheckOutputEquation = true; + +struct LutPin +{ + struct LutPinUser + { + size_t cell_idx; + size_t cell_pin_idx; + }; + + const NetInfo *net = nullptr; + std::vector<LutPinUser> users; + + int32_t min_pin = -1; + int32_t max_pin = -1; + + void add_user(const LutBel &lut_bel, size_t cell_idx, size_t cell_pin_idx) + { + if (min_pin < 0) { + min_pin = lut_bel.min_pin; + max_pin = lut_bel.max_pin; + } + + min_pin = std::max(min_pin, lut_bel.min_pin); + max_pin = std::min(max_pin, lut_bel.max_pin); + + users.emplace_back(); + users.back().cell_idx = cell_idx; + users.back().cell_pin_idx = cell_pin_idx; + } + + bool operator<(const LutPin &other) const { return max_pin < other.max_pin; } +}; + +bool LutMapper::remap_luts(const Context *ctx) +{ + std::unordered_map<NetInfo *, LutPin> lut_pin_map; + std::vector<const LutBel *> lut_bels; + lut_bels.resize(cells.size()); + + for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) { + const CellInfo *cell = cells[cell_idx]; +#ifdef DEBUG_LUT_ROTATION + log_info("Mapping %s %s eq = %s at %s\n", cell->type.c_str(ctx), cell->name.c_str(ctx), + cell->params.at(ctx->id("INIT")).c_str(), ctx->nameOfBel(cell->bel)); +#endif + + auto &bel_data = bel_info(ctx->chip_info, cell->bel); + IdString bel_name(bel_data.name); + auto &lut_bel = element.lut_bels.at(bel_name); + lut_bels[cell_idx] = &lut_bel; + + for (size_t pin_idx = 0; pin_idx < cell->lut_cell.pins.size(); ++pin_idx) { + IdString lut_pin_name = cell->lut_cell.pins[pin_idx]; + const PortInfo &port_info = cell->ports.at(lut_pin_name); + NPNR_ASSERT(port_info.net != nullptr); + + auto result = lut_pin_map.emplace(port_info.net, LutPin()); + LutPin &lut_pin = result.first->second; + lut_pin.net = port_info.net; + lut_pin.add_user(lut_bel, cell_idx, pin_idx); + } + } + + if (lut_pin_map.size() > element.pins.size()) { + // Trival conflict, more nets entering element than pins are + // available! +#ifdef DEBUG_LUT_ROTATION + log_info("Trival failure %zu > %zu, %zu %zu\n", lut_pin_map.size(), element.pins.size(), element.width, + element.lut_bels.size()); +#endif + return false; + } + + std::vector<LutPin> lut_pins; + lut_pins.reserve(lut_pin_map.size()); + for (auto lut_pin_pair : lut_pin_map) { + lut_pins.push_back(std::move(lut_pin_pair.second)); + } + lut_pin_map.clear(); + std::sort(lut_pins.begin(), lut_pins.end()); + + std::vector<std::vector<size_t>> cell_to_bel_pin_remaps; + std::vector<std::vector<int32_t>> bel_to_cell_pin_remaps; + cell_to_bel_pin_remaps.resize(cells.size()); + bel_to_cell_pin_remaps.resize(cells.size()); + for (size_t i = 0; i < cells.size(); ++i) { + cell_to_bel_pin_remaps[i].resize(cells[i]->lut_cell.pins.size()); + bel_to_cell_pin_remaps[i].resize(lut_bels[i]->pins.size(), -1); + } + + uint32_t used_pins = 0; + size_t idx = 0; + std::vector<IdString> net_pins(lut_pins.size()); + for (auto &lut_pin : lut_pins) { + size_t net_idx = idx++; + used_pins |= (1 << net_idx); + + for (auto cell_pin_idx : lut_pin.users) { + size_t cell_idx = cell_pin_idx.cell_idx; + size_t pin_idx = cell_pin_idx.cell_pin_idx; + IdString bel_pin = lut_bels[cell_idx]->pins[net_idx]; +#ifdef DEBUG_LUT_ROTATION + log_info("%s %s %s => %s (%s)\n", cells[cell_idx]->type.c_str(ctx), cells[cell_idx]->name.c_str(ctx), + cells[cell_idx]->lut_cell.pins[pin_idx].c_str(ctx), bel_pin.c_str(ctx), + lut_pin.net->name.c_str(ctx)); +#endif + if (net_pins[net_idx] == IdString()) { + net_pins[net_idx] = bel_pin; + } else { + NPNR_ASSERT(net_pins[net_idx] == bel_pin); + } + + cell_to_bel_pin_remaps[cell_idx][pin_idx] = net_idx; + bel_to_cell_pin_remaps[cell_idx][net_idx] = pin_idx; + } + } + + // Try to see if the equations are mergable! + std::vector<LogicLevel> equation_result; + equation_result.resize(element.width, LL_DontCare); + for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) { + const CellInfo *cell = cells[cell_idx]; + auto &lut_bel = *lut_bels[cell_idx]; + if (!rotate_and_merge_lut_equation(&equation_result, lut_bel, cell->lut_cell.equation, + bel_to_cell_pin_remaps[cell_idx], used_pins)) { +#ifdef DEBUG_LUT_ROTATION + log_info("Failed to find a solution!\n"); + for (auto *cell : cells) { + log_info("%s %s : %s\b\n", cell->type.c_str(ctx), cell->name.c_str(ctx), + cell->params.at(ctx->id("INIT")).c_str()); + } +#endif + return false; + } + } + +#ifdef DEBUG_LUT_ROTATION + log_info("Found a solution!\n"); +#endif + + // Sanity check final equation to make sure no assumptions are violated. + if (kCheckOutputEquation) { + for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) { + CellInfo *cell = cells[cell_idx]; + auto &lut_bel = *lut_bels[cell_idx]; + + std::unordered_map<IdString, IdString> cell_to_bel_map; + for (size_t pin_idx = 0; pin_idx < cell->lut_cell.pins.size(); ++pin_idx) { + size_t bel_pin_idx = cell_to_bel_pin_remaps[cell_idx][pin_idx]; + NPNR_ASSERT(bel_pin_idx < lut_bel.pins.size()); + cell_to_bel_map[cell->lut_cell.pins[pin_idx]] = lut_bel.pins[bel_pin_idx]; + } + + check_equation(cell->lut_cell, cell_to_bel_map, lut_bel, equation_result, used_pins); + } + } + + // Push new cell -> BEL pin maps out to cells now that equations have been + // verified! + for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) { + CellInfo *cell = cells[cell_idx]; + auto &lut_bel = *lut_bels[cell_idx]; + + for (size_t pin_idx = 0; pin_idx < cell->lut_cell.pins.size(); ++pin_idx) { + auto &bel_pins = cell->cell_bel_pins[cell->lut_cell.pins[pin_idx]]; + bel_pins.clear(); + bel_pins.push_back(lut_bel.pins[cell_to_bel_pin_remaps[cell_idx][pin_idx]]); + } + + cell->lut_cell.vcc_pins.clear(); + for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) { + if ((used_pins & (1 << bel_pin_idx)) == 0) { + NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1); + cell->lut_cell.vcc_pins.emplace(lut_bel.pins[bel_pin_idx]); + } + } + } + + return true; +} + +void check_equation(const LutCell &lut_cell, const std::unordered_map<IdString, IdString> &cell_to_bel_map, + const LutBel &lut_bel, const std::vector<LogicLevel> &equation, uint32_t used_pins) +{ + std::vector<int8_t> pin_map; + pin_map.resize(lut_bel.pins.size(), -1); + + NPNR_ASSERT(lut_cell.pins.size() < std::numeric_limits<decltype(pin_map)::value_type>::max()); + + for (size_t cell_pin_idx = 0; cell_pin_idx < lut_cell.pins.size(); ++cell_pin_idx) { + IdString cell_pin = lut_cell.pins[cell_pin_idx]; + IdString bel_pin = cell_to_bel_map.at(cell_pin); + size_t bel_pin_idx = lut_bel.pin_to_index.at(bel_pin); + + pin_map[bel_pin_idx] = cell_pin_idx; + } + + // Iterate over all BEL addresses in the LUT, and ensure that the original + // LUT equation is respected. + size_t bel_width = 1 << lut_bel.pins.size(); + NPNR_ASSERT(lut_bel.low_bit + bel_width == lut_bel.high_bit + 1); + for (size_t bel_address = 0; bel_address < bel_width; ++bel_address) { + LogicLevel level = equation[bel_address + lut_bel.low_bit]; + + bool address_reachable = true; + size_t cell_address = 0; + for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) { + // This address line is 0, so don't translate this bit to the cell + // address. + if ((bel_address & (1 << bel_pin_idx)) == 0) { + // This pin is unused, so the line will be tied high, this + // address is unreachable. + if ((used_pins & (1 << bel_pin_idx)) == 0) { + address_reachable = false; + break; + } + continue; + } + + auto cell_pin_idx = pin_map[bel_pin_idx]; + + // Is this BEL pin used for this cell? + if (cell_pin_idx < 0) { + // This BEL pin is not used for the LUT cell, skip + continue; + } + + cell_address |= (1 << cell_pin_idx); + } + + if (!address_reachable) { + continue; + } + + if (lut_cell.equation.get(cell_address)) { + NPNR_ASSERT(level == LL_One); + } else { + NPNR_ASSERT(level == LL_Zero); + } + } +} + +void LutElement::compute_pin_order() +{ + pins.clear(); + pin_to_index.clear(); + + for (auto &lut_bel_pair : lut_bels) { + auto &lut_bel = lut_bel_pair.second; + + for (size_t pin_idx = 0; pin_idx < lut_bel.pins.size(); ++pin_idx) { + IdString pin = lut_bel.pins[pin_idx]; + auto result = pin_to_index.emplace(pin, pin_idx); + if (!result.second) { + // Not sure when this isn't true, but check it for now! + NPNR_ASSERT(result.first->second == pin_idx); + } + } + } + + pins.resize(pin_to_index.size()); + for (auto &pin_pair : pin_to_index) { + pins.at(pin_pair.second) = pin_pair.first; + } + + for (auto &lut_bel_pair : lut_bels) { + auto &lut_bel = lut_bel_pair.second; + lut_bel.min_pin = pin_to_index.at(lut_bel.pins.front()); + lut_bel.max_pin = pin_to_index.at(lut_bel.pins.back()); + } +} + +NEXTPNR_NAMESPACE_END diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h new file mode 100644 index 00000000..a5d3b1d0 --- /dev/null +++ b/fpga_interchange/luts.h @@ -0,0 +1,100 @@ +/* + * 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. + * + */ + +#ifndef NEXTPNR_H +#error Include "luts.h" via "nextpnr.h" only. +#endif + +#include "dynamic_bitarray.h" + +#ifndef LUTS_H +#define LUTS_H + +NEXTPNR_NAMESPACE_BEGIN + +struct CellInfo; +struct Context; + +enum LogicLevel +{ + LL_Zero, + LL_One, + LL_DontCare +}; + +struct LutCell +{ + // LUT cell pins for equation, LSB first. + std::vector<IdString> pins; + std::unordered_set<IdString> lut_pins; + std::unordered_set<IdString> vcc_pins; + nextpnr::DynamicBitarray<> equation; +}; + +struct LutBel +{ + // LUT BEL pins to LUT array index. + std::vector<IdString> pins; + std::unordered_map<IdString, size_t> pin_to_index; + + // What part of the LUT equation does this LUT output use? + // This assumes contiguous LUT bits. + uint32_t low_bit; + uint32_t high_bit; + + int32_t min_pin; + int32_t max_pin; +}; + +// Work forward from cell definition and cell -> bel pin map and check that +// equation is valid. +void check_equation(const LutCell &lut_cell, const std::unordered_map<IdString, IdString> &cell_to_bel_map, + const LutBel &lut_bel, const std::vector<LogicLevel> &equation, uint32_t used_pins); + +struct LutElement +{ + size_t width; + std::unordered_map<IdString, LutBel> lut_bels; + + void compute_pin_order(); + + std::vector<IdString> pins; + std::unordered_map<IdString, size_t> pin_to_index; +}; + +struct LutMapper +{ + LutMapper(const LutElement &element) : element(element) {} + const LutElement &element; + + std::vector<CellInfo *> cells; + + bool remap_luts(const Context *ctx); +}; + +// Rotate and merge a LUT equation into an array of levels. +// +// If a conflict arises, return false and result is in an indeterminate state. +bool rotate_and_merge_lut_equation(std::vector<LogicLevel> *result, const LutBel &lut_bel, + const nextpnr::DynamicBitarray<> &old_equation, const std::vector<size_t> &pin_map, + uint32_t used_pins); + +NEXTPNR_NAMESPACE_END + +#endif /* LUTS_H */ diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc index 7232b635..9d4fc57c 100644 --- a/fpga_interchange/site_router.cc +++ b/fpga_interchange/site_router.cc @@ -697,7 +697,7 @@ bool route_site(const Context *ctx, SiteInformation *site_info) // The simplistic solution (only select when 1 solution is available) // will likely solve initial problems. Once that is show to be wrong, // come back with something more general. - NPNR_ASSERT(false); + return false; } while (!wire_to_expansion.empty()); @@ -747,17 +747,42 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta return site_ok; } } - // + // FIXME: Populate "consumed_wires" with all VCC/GND tied in the site. // This will allow route_site to leverage site local constant sources. // // FIXME: Handle case where a constant is requested, but use of an // inverter is possible. This is the place to handle "bestConstant" // (e.g. route VCC's over GND's, etc). - // - // FIXME: Enable some LUT rotation! - // Default cell/bel pin map always uses high pins, which will generate - // conflicts where there are none!!! + auto tile_type_idx = ctx->chip_info->tiles[tile].type; + const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(tile_type_idx); + std::vector<LutMapper> lut_mappers; + lut_mappers.reserve(lut_elements.size()); + for (size_t i = 0; i < lut_elements.size(); ++i) { + lut_mappers.push_back(LutMapper(lut_elements[i])); + } + + for (CellInfo *cell : cells_in_site) { + if (cell->lut_cell.pins.empty()) { + continue; + } + + BelId bel = cell->bel; + const auto &bel_data = bel_info(ctx->chip_info, bel); + if (bel_data.lut_element != -1) { + lut_mappers[bel_data.lut_element].cells.push_back(cell); + } + } + + for (LutMapper lut_mapper : lut_mappers) { + if (lut_mapper.cells.empty()) { + continue; + } + + if (!lut_mapper.remap_luts(ctx)) { + return false; + } + } SiteInformation site_info(ctx, cells_in_site); diff --git a/fpga_interchange/site_router.h b/fpga_interchange/site_router.h index 561dae9d..6af32747 100644 --- a/fpga_interchange/site_router.h +++ b/fpga_interchange/site_router.h @@ -22,6 +22,9 @@ #error Include "site_router.h" via "nextpnr.h" only. #endif +#ifndef SITE_ROUTER_H +#define SITE_ROUTER_H + NEXTPNR_NAMESPACE_BEGIN struct Context; @@ -43,3 +46,5 @@ struct SiteRouter }; NEXTPNR_NAMESPACE_END + +#endif /* SITE_ROUTER_H */ diff --git a/nexus/arch.cc b/nexus/arch.cc index 9f410758..f804cdd9 100644 --- a/nexus/arch.cc +++ b/nexus/arch.cc @@ -693,7 +693,7 @@ bool Arch::route() router2(getCtx(), Router2Cfg(getCtx())); result = true; } else { - log_error("iCE40 architecture does not support router '%s'\n", router.c_str()); + log_error("Nexus architecture does not support router '%s'\n", router.c_str()); } getCtx()->attrs[getCtx()->id("step")] = std::string("route"); archInfoToAttributes(); @@ -781,7 +781,7 @@ Loc Arch::get_pad_loc(const PadInfoPOD *pad) const BelId Arch::get_pad_pio_bel(const PadInfoPOD *pad) const { - if (pad == nullptr) + if (pad == nullptr || pad->offset == -1) return BelId(); return getBelByLocation(get_pad_loc(pad)); } diff --git a/nexus/arch.h b/nexus/arch.h index 15184d26..9dfc4551 100644 --- a/nexus/arch.h +++ b/nexus/arch.h @@ -373,7 +373,7 @@ inline bool chip_get_hrow_loc(const ChipInfoPOD *chip, int32_t x, int32_t y, int { bool y_found = false; for (auto &s : chip->globals->spines) { - if (std::abs(y - s.spine_row) < 3) { + if (std::abs(y - s.spine_row) <= 3) { hrow_y = s.spine_row; y_found = true; break; @@ -800,6 +800,7 @@ enum CellPinStyle PINSTYLE_DEDI = 0x0000, // dedicated signals, leave alone PINSTYLE_PU = 0x4022, // signals that float high and default high PINSTYLE_PU_NONCIB = 0x0022, // signals that float high and default high + PINSTYLE_PD_NONCIB = 0x0012, // signals that float high and default low PINSTYLE_T = 0x4027, // PIO 'T' signal PINSTYLE_ADLSB = 0x4017, // special case of the EBR address MSBs diff --git a/nexus/constids.inc b/nexus/constids.inc index 08ca5d09..03b144a2 100644 --- a/nexus/constids.inc +++ b/nexus/constids.inc @@ -480,3 +480,26 @@ X(CEB2B3) X(RSTB0B1) X(RSTB2B3) X(M9ADDSUB) + +X(DPHY) +X(DPHY_CORE) +X(CKN) +X(CKP) +X(DN0) +X(DN1) +X(DN2) +X(DN3) +X(DP0) +X(DP1) +X(DP2) +X(DP3) +X(DP4) +X(SCCLKIN) +X(SCRSTNIN) +X(CLKREF) +X(U2TDE4CK) +X(U1ENTHEN) +X(U2END2) +X(U3END3) +X(UED0THEN) +X(URXCKINE) diff --git a/nexus/fasm.cc b/nexus/fasm.cc index 0b8b6377..4394aebc 100644 --- a/nexus/fasm.cc +++ b/nexus/fasm.cc @@ -569,6 +569,15 @@ struct NexusFasmWriter {"SSC_STEP_IN", 7}, {"SSC_TBASE", 12}, {"V2I_PP_ICTRL", 5}, }; + + // Which MIPI params are 'word' values + const std::unordered_map<std::string, int> dphy_word_params = { + {"CM", 8}, {"CN", 5}, {"CO", 3}, {"RSEL", 2}, {"RXCDRP", 2}, + {"RXDATAWIDTHHS", 2}, {"RXLPRP", 3}, {"TEST_ENBL", 6}, + {"TEST_PATTERN", 32}, {"TST", 4}, {"TXDATAWIDTHHS", 2}, + {"UC_PRG_RXHS_SETTLE", 6}, {"U_PRG_HS_PREPARE", 2}, + {"U_PRG_HS_TRAIL", 6}, {"U_PRG_HS_ZERO", 6}, {"U_PRG_RXHS_SETTLE", 6} + }; /* clang-format on */ // Write out config for some kind of PLL cell @@ -596,6 +605,27 @@ struct NexusFasmWriter } pop(); } + // Write out config for a DPHY_CORE cell + // TODO: duplication with PLL and other hard IP... + void write_dphy(const CellInfo *cell) + { + BelId bel = cell->bel; + push(stringf("IP_%s", ctx->nameOf(IdString(ctx->bel_data(bel).name)))); + for (auto param : sorted_cref(cell->params)) { + const std::string &name = param.first.str(ctx); + if (is_mux_param(name) || name == "GSR") + continue; + auto fnd_word = dphy_word_params.find(name); + if (fnd_word != dphy_word_params.end()) { + write_int_vector(stringf("%s[%d:0]", name.c_str(), fnd_word->second - 1), + ctx->parse_lattice_param(cell, param.first, fnd_word->second, 0).as_int64(), + fnd_word->second); + } else { + write_bit(stringf("%s.%s", name.c_str(), param.second.as_string().c_str())); + } + } + pop(); + } // Write out config for an LRAM_CORE cell void write_lram(const CellInfo *cell) { @@ -750,6 +780,8 @@ struct NexusFasmWriter write_pll(ci); else if (ci->type == id_LRAM_CORE) write_lram(ci); + else if (ci->type == id_DPHY_CORE) + write_dphy(ci); blank(); } // Write config for unused bels diff --git a/nexus/global.cc b/nexus/global.cc index 62633df9..53306e21 100644 --- a/nexus/global.cc +++ b/nexus/global.cc @@ -136,10 +136,19 @@ struct NexusGlobalRouter } } + bool is_relaxed_sink(const PortRef &sink) const + { + // This DPHY clock port can't be routed without going through some general routing + if (sink.cell->type == id_DPHY_CORE && sink.port == id_URXCKINE) + return true; + return false; + } + void route_clk_net(NetInfo *net) { for (size_t i = 0; i < net->users.size(); i++) - backwards_bfs_route(net, i, 1000000, true, [&](PipId pip) { return global_pip_filter(pip); }); + backwards_bfs_route(net, i, 1000000, true, + [&](PipId pip) { return is_relaxed_sink(net->users.at(i)) || global_pip_filter(pip); }); log_info(" routed net '%s' using global resources\n", ctx->nameOf(net)); } diff --git a/nexus/pack.cc b/nexus/pack.cc index af1a921d..ffec29bd 100644 --- a/nexus/pack.cc +++ b/nexus/pack.cc @@ -1027,7 +1027,7 @@ struct NexusPacker {id_OSCA, id_OSC_CORE}, {id_DP16K, id_DP16K_MODE}, {id_PDP16K, id_PDP16K_MODE}, {id_PDPSC16K, id_PDPSC16K_MODE}, {id_SP16K, id_SP16K_MODE}, {id_FIFO16K, id_FIFO16K_MODE}, {id_SP512K, id_SP512K_MODE}, {id_DPSC512K, id_DPSC512K_MODE}, {id_PDPSC512K, id_PDPSC512K_MODE}, - {id_PLL, id_PLL_CORE}, + {id_PLL, id_PLL_CORE}, {id_DPHY, id_DPHY_CORE}, }; for (auto cell : sorted(ctx->cells)) { @@ -1959,6 +1959,33 @@ struct NexusPacker } } + // Map LOC attribute on DPHY_CORE to a bel + // TDPHY_CORE2 is Radiant 2.0 style, DPHY0 is Radiant 2.2 + // TODO: LIFCL-17 (perhaps remove the hardcoded map) + const std::unordered_map<std::string, std::string> dphy_loc_map = { + {"TDPHY_CORE2", "X4/Y0/TDPHY_CORE2"}, + {"DPHY0", "X4/Y0/TDPHY_CORE2"}, + {"TDPHY_CORE26", "X28/Y0/TDPHY_CORE26"}, + {"DPHY1", "X28/Y0/TDPHY_CORE26"}, + }; + + void pack_ip() + { + for (auto cell : sorted(ctx->cells)) { + CellInfo *ci = cell.second; + if (ci->type == id_DPHY_CORE) { + auto loc_attr = ci->attrs.find(id_LOC); + if (loc_attr == ci->attrs.end()) + log_error("LOC attribute is required for DPHY_CORE '%s'\n", ctx->nameOf(ci)); + const std::string &loc = loc_attr->second.as_string(); + auto dphy_bel = dphy_loc_map.find(loc); + if (dphy_bel == dphy_loc_map.end()) + log_error("Invalid location '%s' for DPHY_CORE '%s'\n", loc.c_str(), ctx->nameOf(ci)); + ci->attrs[id_BEL] = dphy_bel->second; + } + } + } + explicit NexusPacker(Context *ctx) : ctx(ctx) {} void operator()() @@ -1975,6 +2002,7 @@ struct NexusPacker pack_plls(); pack_constants(); pack_luts(); + pack_ip(); promote_globals(); place_globals(); generate_constraints(); diff --git a/nexus/pins.cc b/nexus/pins.cc index 0e27214b..a283953b 100644 --- a/nexus/pins.cc +++ b/nexus/pins.cc @@ -189,6 +189,32 @@ static const std::unordered_map<IdString, Arch::CellPinsData> base_cell_pin_data {id_SCANRST, PINSTYLE_DEDI}, {id_OPCGLDCK, PINSTYLE_DEDI}, {{}, PINSTYLE_CIB}, + }}, + {id_DPHY_CORE, + { + {id_CKN, PINSTYLE_DEDI}, + {id_CKP, PINSTYLE_DEDI}, + {id_DN0, PINSTYLE_DEDI}, + {id_DN1, PINSTYLE_DEDI}, + {id_DN2, PINSTYLE_DEDI}, + {id_DN3, PINSTYLE_DEDI}, + {id_DP0, PINSTYLE_DEDI}, + {id_DP1, PINSTYLE_DEDI}, + {id_DP2, PINSTYLE_DEDI}, + {id_DP3, PINSTYLE_DEDI}, + {id_SCCLKIN, PINSTYLE_DEDI}, + {id_SCRSTNIN, PINSTYLE_DEDI}, + {id_SCANCLK, PINSTYLE_DEDI}, + {id_SCANRST, PINSTYLE_DEDI}, + {id_LMMIRESETN, PINSTYLE_DEDI}, + {id_CLKREF, PINSTYLE_DEDI}, + {id_U2TDE4CK, PINSTYLE_DEDI}, + {id_OPCGLDCK, PINSTYLE_DEDI}, + {id_U1ENTHEN, PINSTYLE_PD_NONCIB}, + {id_U2END2, PINSTYLE_PD_NONCIB}, + {id_U3END3, PINSTYLE_PD_NONCIB}, + {id_UED0THEN, PINSTYLE_PD_NONCIB}, + {{}, PINSTYLE_CIB}, }}}; } // namespace diff --git a/nexus/post_place.cc b/nexus/post_place.cc index 65676188..b712aea3 100644 --- a/nexus/post_place.cc +++ b/nexus/post_place.cc @@ -28,9 +28,9 @@ NEXTPNR_NAMESPACE_BEGIN struct NexusPostPlaceOpt { Context *ctx; - NetCriticalityMap net_crit; + TimingAnalyser tmg; - NexusPostPlaceOpt(Context *ctx) : ctx(ctx){}; + NexusPostPlaceOpt(Context *ctx) : ctx(ctx), tmg(ctx){}; inline bool is_constrained(CellInfo *cell) { @@ -139,7 +139,7 @@ struct NexusPostPlaceOpt void operator()() { - get_criticalities(ctx, &net_crit); + tmg.setup(); opt_lutffs(); } |