diff options
author | gatecat <gatecat@ds0.me> | 2022-02-26 15:17:46 +0000 |
---|---|---|
committer | gatecat <gatecat@ds0.me> | 2022-02-27 13:47:05 +0000 |
commit | 86699b42f619960bfefd4d0b479dd44a90527ea4 (patch) | |
tree | 06997246ae104b75ce472215fcee3ba37ee5c50c /ice40 | |
parent | 434a9737bb459189b463c8768454ea6c0e151406 (diff) | |
download | nextpnr-86699b42f619960bfefd4d0b479dd44a90527ea4.tar.gz nextpnr-86699b42f619960bfefd4d0b479dd44a90527ea4.tar.bz2 nextpnr-86699b42f619960bfefd4d0b479dd44a90527ea4.zip |
Switch to potentially-sparse net users array
This uses a new data structure for net.users that allows gaps, so
removing a port from a net is no longer an O(n) operation on the number
of users the net has.
Signed-off-by: gatecat <gatecat@ds0.me>
Diffstat (limited to 'ice40')
-rw-r--r-- | ice40/bitstream.cc | 2 | ||||
-rw-r--r-- | ice40/cells.cc | 2 | ||||
-rw-r--r-- | ice40/chains.cc | 61 | ||||
-rw-r--r-- | ice40/pack.cc | 81 |
4 files changed, 54 insertions, 92 deletions
diff --git a/ice40/bitstream.cc b/ice40/bitstream.cc index 89f84262..48fbc132 100644 --- a/ice40/bitstream.cc +++ b/ice40/bitstream.cc @@ -1146,7 +1146,7 @@ bool read_asc(Context *ctx, std::istream &in) if (port.second.type == PORT_OUT) net->driver = ref; else - net->users.push_back(ref); + port.second.user_idx = net->users.add(ref); } } } diff --git a/ice40/cells.cc b/ice40/cells.cc index b5f759b2..9166b41b 100644 --- a/ice40/cells.cc +++ b/ice40/cells.cc @@ -466,7 +466,7 @@ void nxio_to_sb(Context *ctx, CellInfo *nxio, CellInfo *sbio, pool<IdString> &to tbuf->movePortTo(id_A, sbio, id_D_OUT_0); tbuf->movePortTo(id_E, sbio, id_OUTPUT_ENABLE); - if (donet->users.size() > 1) { + if (donet->users.entries() > 1) { for (auto user : donet->users) log_info(" remaining tristate user: %s.%s\n", user.cell->name.c_str(ctx), user.port.c_str(ctx)); log_error("unsupported tristate IO pattern for IO buffer '%s', " diff --git a/ice40/chains.cc b/ice40/chains.cc index e6a37044..6ea261de 100644 --- a/ice40/chains.cc +++ b/ice40/chains.cc @@ -73,8 +73,8 @@ class ChainConstrainer } else { NetInfo *carry_net = cell->ports.at(id_COUT).net; bool at_end = (curr_cell == carryc.cells.end() - 1); - if (carry_net != nullptr && (carry_net->users.size() > 1 || at_end)) { - if (carry_net->users.size() > 2 || + if (carry_net != nullptr && (carry_net->users.entries() > 1 || at_end)) { + if (carry_net->users.entries() > 2 || (net_only_drives(ctx, carry_net, is_lc, id_I3, false) != net_only_drives(ctx, carry_net, is_lc, id_CIN, false)) || (at_end && !net_only_drives(ctx, carry_net, is_lc, id_I3, true))) { @@ -116,15 +116,11 @@ class ChainConstrainer lc->ports.at(id_O).net = cout_port.net; NetInfo *co_i3_net = ctx->createNet(ctx->id(lc->name.str(ctx) + "$I3")); co_i3_net->driver = cout_port.net->driver; - PortRef i3_r; - i3_r.port = id_I3; - i3_r.cell = lc.get(); - co_i3_net->users.push_back(i3_r); + lc->connectPort(id_I3, co_i3_net); PortRef o_r; o_r.port = id_O; o_r.cell = lc.get(); cout_port.net->driver = o_r; - lc->ports.at(id_I3).net = co_i3_net; cout_port.net = co_i3_net; // If COUT also connects to a CIN; preserve the carry chain @@ -133,34 +129,21 @@ class ChainConstrainer // Connect I1 to 1 to preserve carry chain NetInfo *vcc = ctx->nets.at(ctx->id("$PACKER_VCC_NET")).get(); - lc->ports.at(id_I1).net = vcc; - PortRef i1_r; - i1_r.port = id_I1; - i1_r.cell = lc.get(); - vcc->users.push_back(i1_r); + lc->connectPort(id_I1, vcc); // Connect co_cin_net to the COUT of the LC - PortRef co_r; - co_r.port = id_COUT; - co_r.cell = lc.get(); - co_cin_net->driver = co_r; - lc->ports.at(id_COUT).net = co_cin_net; + lc->connectPort(id_COUT, co_cin_net); // Find the user corresponding to the next CIN int replaced_ports = 0; if (ctx->debug) log_info("cell: %s\n", cin_cell->name.c_str(ctx)); for (auto port : {id_CIN, id_I3}) { - auto &usr = lc->ports.at(id_O).net->users; - if (ctx->debug) - for (auto user : usr) - log_info("%s.%s\n", user.cell->name.c_str(ctx), user.port.c_str(ctx)); - auto fnd_user = std::find_if(usr.begin(), usr.end(), - [&](const PortRef &pr) { return pr.cell == cin_cell && pr.port == port; }); - if (fnd_user != usr.end()) { - co_cin_net->users.push_back(*fnd_user); - usr.erase(fnd_user); - cin_cell->ports.at(port).net = co_cin_net; + NetInfo *out_net = lc->ports.at(id_O).net; + auto &cin_p = cin_cell->ports.at(port); + if (cin_p.net == out_net) { + cin_cell->disconnectPort(port); + cin_cell->connectPort(port, co_cin_net); ++replaced_ports; } } @@ -181,30 +164,16 @@ class ChainConstrainer lc->params[id_CARRY_ENABLE] = Property::State::S1; lc->params[id_CIN_CONST] = Property::State::S1; lc->params[id_CIN_SET] = Property::State::S1; - lc->ports.at(id_I1).net = cin_port.net; - cin_port.net->users.erase(std::remove_if(cin_port.net->users.begin(), cin_port.net->users.end(), - [cin_cell, cin_port](const PortRef &usr) { - return usr.cell == cin_cell && usr.port == cin_port.name; - })); - PortRef i1_ref; - i1_ref.cell = lc.get(); - i1_ref.port = id_I1; - lc->ports.at(id_I1).net->users.push_back(i1_ref); + lc->connectPort(id_I1, cin_port.net); + cin_port.net->users.remove(cin_port.user_idx); NetInfo *out_net = ctx->createNet(ctx->id(lc->name.str(ctx) + "$O")); - PortRef drv_ref; - drv_ref.port = id_COUT; - drv_ref.cell = lc.get(); - out_net->driver = drv_ref; - lc->ports.at(id_COUT).net = out_net; + lc->connectPort(id_COUT, out_net); - PortRef usr_ref; - usr_ref.port = cin_port.name; - usr_ref.cell = cin_cell; - out_net->users.push_back(usr_ref); - cin_cell->ports.at(cin_port.name).net = out_net; + cin_port.net = nullptr; + cin_cell->connectPort(cin_port.name, out_net); IdString name = lc->name; ctx->assignCellInfo(lc.get()); diff --git a/ice40/pack.cc b/ice40/pack.cc index 4244f192..c32e346f 100644 --- a/ice40/pack.cc +++ b/ice40/pack.cc @@ -214,14 +214,14 @@ static void pack_carries(Context *ctx) PortRef pr; pr.cell = created_lc.get(); pr.port = id_I1; - i0_net->users.push_back(pr); + created_lc->ports.at(id_I1).user_idx = i0_net->users.add(pr); } created_lc->ports.at(id_I2).net = i1_net; if (i1_net) { PortRef pr; pr.cell = created_lc.get(); pr.port = id_I2; - i1_net->users.push_back(pr); + created_lc->ports.at(id_I2).user_idx = i1_net->users.add(pr); } new_cells.push_back(std::move(created_lc)); ++carry_only; @@ -230,16 +230,12 @@ static void pack_carries(Context *ctx) ci->movePortTo(id_CI, carry_lc, id_CIN); ci->movePortTo(id_CO, carry_lc, id_COUT); if (i0_net) { - auto &i0_usrs = i0_net->users; - i0_usrs.erase(std::remove_if(i0_usrs.begin(), i0_usrs.end(), [ci, ctx](const PortRef &pr) { - return pr.cell == ci && pr.port == id_I0; - })); + if (ci->ports.count(id_I0) && ci->ports.at(id_I0).user_idx) + i0_net->users.remove(ci->ports.at(id_I0).user_idx); } if (i1_net) { - auto &i1_usrs = i1_net->users; - i1_usrs.erase(std::remove_if(i1_usrs.begin(), i1_usrs.end(), [ci, ctx](const PortRef &pr) { - return pr.cell == ci && pr.port == id_I1; - })); + if (ci->ports.count(id_I1) && ci->ports.at(id_I1).user_idx) + i1_net->users.remove(ci->ports.at(id_I1).user_idx); } // Check for constant driver on CIN @@ -251,10 +247,7 @@ static void pack_carries(Context *ctx) cin_net == ctx->id("$PACKER_VCC_NET") ? Property::State::S1 : Property::State::S0; carry_lc->ports.at(id_CIN).net = nullptr; auto &cin_users = ctx->nets.at(cin_net)->users; - cin_users.erase( - std::remove_if(cin_users.begin(), cin_users.end(), [carry_lc, ctx](const PortRef &pr) { - return pr.cell == carry_lc && pr.port == id_CIN; - })); + cin_users.remove(carry_lc->ports.at(id_CIN).user_idx); } } exhausted_cells.insert(carry_lc->name); @@ -326,17 +319,20 @@ static void set_net_constant(const Context *ctx, NetInfo *orig, NetInfo *constne if ((is_lut(ctx, uc) || is_lc(ctx, uc) || is_carry(ctx, uc)) && (user.port.str(ctx).at(0) == 'I') && !constval) { uc->ports[user.port].net = nullptr; + uc->ports[user.port].user_idx = {}; } else if ((is_sb_mac16(ctx, uc) || uc->type == id_ICESTORM_DSP) && (user.port != id_CLK && ((constval && user.port == id_CE) || (!constval && user.port != id_CE)))) { uc->ports[user.port].net = nullptr; + uc->ports[user.port].user_idx = {}; } else if (is_ram(ctx, uc) && !constval && user.port != id_RCLK && user.port != id_RCLKN && user.port != id_WCLK && user.port != id_WCLKN && user.port != id_RCLKE && user.port != id_WCLKE) { uc->ports[user.port].net = nullptr; + uc->ports[user.port].user_idx = {}; } else { uc->ports[user.port].net = constnet; - constnet->users.push_back(user); + uc->ports[user.port].user_idx = constnet->users.add(user); } } } @@ -486,8 +482,8 @@ static void pack_io(Context *ctx) ci->type.c_str(ctx), ci->name.c_str(ctx)); NetInfo *net = sb->ports.at(id_PACKAGE_PIN).net; if (((ci->type == ctx->id("$nextpnr_ibuf") || ci->type == ctx->id("$nextpnr_iobuf")) && - net->users.size() > 1) || - (ci->type == ctx->id("$nextpnr_obuf") && (net->users.size() > 2 || net->driver.cell != nullptr))) + net->users.entries() > 1) || + (ci->type == ctx->id("$nextpnr_obuf") && (net->users.entries() > 2 || net->driver.cell != nullptr))) log_error("PACKAGE_PIN of %s '%s' connected to more than a single top level IO.\n", sb->type.c_str(ctx), sb->name.c_str(ctx)); @@ -531,9 +527,9 @@ static void pack_io(Context *ctx) sb->attrs[attr.first] = attr.second; } else if (is_sb_io(ctx, ci) || is_sb_gb_io(ctx, ci)) { NetInfo *net = ci->ports.at(id_PACKAGE_PIN).net; - if ((net != nullptr) && ((net->users.size() > 2) || + if ((net != nullptr) && ((net->users.entries() > 2) || (net->driver.cell != nullptr && - net->driver.cell->type == ctx->id("$nextpnr_obuf") && net->users.size() > 1))) + net->driver.cell->type == ctx->id("$nextpnr_obuf") && net->users.entries() > 1))) log_error("PACKAGE_PIN of %s '%s' connected to more than a single top level IO.\n", ci->type.c_str(ctx), ci->name.c_str(ctx)); } @@ -554,11 +550,11 @@ static void pack_io(Context *ctx) NetInfo *net_in0 = ci->ports.count(id_D_IN_0) ? ci->ports[id_D_IN_0].net : nullptr; NetInfo *net_in1 = ci->ports.count(id_D_IN_1) ? ci->ports[id_D_IN_1].net : nullptr; - if (net_in0 != nullptr && net_in0->users.size() == 0) { + if (net_in0 != nullptr && net_in0->users.entries() == 0) { delete_nets.insert(net_in0->name); ci->ports[id_D_IN_0].net = nullptr; } - if (net_in1 != nullptr && net_in1->users.size() == 0) { + if (net_in1 != nullptr && net_in1->users.entries() == 0) { delete_nets.insert(net_in1->name); ci->ports[id_D_IN_1].net = nullptr; } @@ -591,28 +587,23 @@ static void insert_global(Context *ctx, NetInfo *net, bool is_reset, bool is_cen std::string glb_name = net->name.str(ctx) + std::string("_$glb_") + (is_reset ? "sr" : (is_cen ? "ce" : "clk")); std::unique_ptr<CellInfo> gb = create_ice_cell(ctx, id_SB_GB, "$gbuf_" + glb_name); - gb->ports[id_USER_SIGNAL_TO_GLOBAL_BUFFER].net = net; - PortRef pr; - pr.cell = gb.get(); - pr.port = id_USER_SIGNAL_TO_GLOBAL_BUFFER; - net->users.push_back(pr); - - pr.cell = gb.get(); - pr.port = id_GLOBAL_BUFFER_OUTPUT; + gb->connectPort(id_USER_SIGNAL_TO_GLOBAL_BUFFER, net); NetInfo *glbnet = ctx->createNet(ctx->id(glb_name)); - glbnet->driver = pr; - gb->ports[id_GLOBAL_BUFFER_OUTPUT].net = glbnet; + gb->connectPort(id_GLOBAL_BUFFER_OUTPUT, glbnet); + std::vector<PortRef> keep_users; for (auto user : net->users) { if (is_clock_port(ctx, user) || (is_reset && is_reset_port(ctx, user)) || (is_cen && is_enable_port(ctx, user)) || (is_logic && is_logic_port(ctx, user))) { user.cell->ports[user.port].net = glbnet; - glbnet->users.push_back(user); + user.cell->ports[user.port].user_idx = glbnet->users.add(user); } else { keep_users.push_back(user); } } - net->users = keep_users; + net->users.clear(); + for (auto &user : keep_users) + user.cell->ports[user.port].user_idx = net->users.add(user); if (net->clkconstr) { glbnet->clkconstr = std::unique_ptr<ClockConstraint>(new ClockConstraint()); @@ -809,7 +800,7 @@ static void place_plls(Context *ctx) log_error("PLL '%s' has a PACKAGEPIN driven by an %s, should be directly connected to an input " "SB_IO.D_IN_0 port\n", ci->name.c_str(ctx), io_cell->type.c_str(ctx)); - if (ni->users.size() != 1) + if (ni->users.entries() != 1) log_error("PLL '%s' clock input '%s' can only drive PLL\n", ci->name.c_str(ctx), ni->name.c_str(ctx)); if (!io_cell->attrs.count(id_BEL)) log_error("PLL '%s' PACKAGEPIN SB_IO '%s' is unconstrained\n", ci->name.c_str(ctx), @@ -911,10 +902,10 @@ static void place_plls(Context *ctx) // Used global connections bool gb_a_used = ci->ports.count(id_PLLOUT_A_GLOBAL) && (ci->ports[id_PLLOUT_A_GLOBAL].net != nullptr) && - (ci->ports[id_PLLOUT_A_GLOBAL].net->users.size() > 0); + (ci->ports[id_PLLOUT_A_GLOBAL].net->users.entries() > 0); bool gb_b_used = is_sb_pll40_dual(ctx, ci) && ci->ports.count(id_PLLOUT_B_GLOBAL) && (ci->ports[id_PLLOUT_B_GLOBAL].net != nullptr) && - (ci->ports[id_PLLOUT_B_GLOBAL].net->users.size() > 0); + (ci->ports[id_PLLOUT_B_GLOBAL].net->users.entries() > 0); // Check for conflict BelPin pll_io_a, pll_io_b; @@ -954,15 +945,15 @@ static void place_plls(Context *ctx) // Used global connections bool gb_a_used = ci->ports.count(id_PLLOUT_A_GLOBAL) && (ci->ports[id_PLLOUT_A_GLOBAL].net != nullptr) && - (ci->ports[id_PLLOUT_A_GLOBAL].net->users.size() > 0); + (ci->ports[id_PLLOUT_A_GLOBAL].net->users.entries() > 0); bool gb_b_used = is_sb_pll40_dual(ctx, ci) && ci->ports.count(id_PLLOUT_B_GLOBAL) && (ci->ports[id_PLLOUT_B_GLOBAL].net != nullptr) && - (ci->ports[id_PLLOUT_B_GLOBAL].net->users.size() > 0); + (ci->ports[id_PLLOUT_B_GLOBAL].net->users.entries() > 0); // Could this be a PAD PLL ? bool could_be_pad = false; BelId pad_bel; - if (ni->users.size() == 1 && is_sb_io(ctx, ni->driver.cell) && ni->driver.cell->attrs.count(id_BEL)) + if (ni->users.entries() == 1 && is_sb_io(ctx, ni->driver.cell) && ni->driver.cell->attrs.count(id_BEL)) pad_bel = ctx->getBelByNameStr(ni->driver.cell->attrs[id_BEL].as_string()); // Find a BEL for it @@ -1035,7 +1026,7 @@ static std::unique_ptr<CellInfo> spliceLUT(Context *ctx, CellInfo *ci, IdString PortRef pr; pr.cell = user.cell; pr.port = user.port; - out_net->users.push_back(pr); + user.cell->ports[user.port].user_idx = out_net->users.add(pr); } // Add LUT to new users. @@ -1045,8 +1036,10 @@ static std::unique_ptr<CellInfo> spliceLUT(Context *ctx, CellInfo *ci, IdString new_users.push_back(pr); pt->ports.at(id_I3).net = port.net; - // Replace users of the original net. - port.net->users = new_users; + // Replace users of the original net + port.net->users.clear(); + for (auto &usr : new_users) + usr.cell->ports.at(usr.port).user_idx = port.net->users.add(usr); return pt; } @@ -1235,7 +1228,7 @@ static void pack_special(Context *ctx) if ((pi.name != id_RGB0) && (pi.name != id_RGB1) && (pi.name != id_RGB2)) continue; - if (net->users.size() > 0) + if (net->users.entries() > 0) log_error("SB_RGB_DRV/SB_RGBA_DRV port connected to more than just package pin !\n"); ctx->nets.erase(net->name); @@ -1585,7 +1578,7 @@ void pack_plls(Context *ctx) // Only if there is actually a net ... if (pi.net != nullptr) { // ... and it's used - if (pi.net->users.size() > 0) { + if (pi.net->users.entries() > 0) { std::unique_ptr<CellInfo> gb = create_padin_gbuf(ctx, packed.get(), pi.name, "$gbuf_" + ci->name.str(ctx) + "_pllout_" + (is_b_port ? "b" : "a")); |