| 1 |
/* |
| 2 |
* nextpnr -- Next Generation Place and Route |
| 3 |
* |
| 4 |
* Copyright (C) 2019-2023 Myrtle Shah <[email protected]> |
| 5 |
* |
| 6 |
* Permission to use, copy, modify, and/or distribute this software for any |
| 7 |
* purpose with or without fee is hereby granted, provided that the above |
| 8 |
* copyright notice and this permission notice appear in all copies. |
| 9 |
* |
| 10 |
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
| 11 |
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
| 12 |
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR |
| 13 |
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
| 14 |
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN |
| 15 |
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF |
| 16 |
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
| 17 |
* |
| 18 |
*/ |
| 19 |
|
| 20 |
#include <algorithm> |
| 21 |
#include <boost/optional.hpp> |
| 22 |
#include <iterator> |
| 23 |
#include <queue> |
| 24 |
#include <unordered_set> |
| 25 |
#include "chain_utils.h" |
| 26 |
#include "design_utils.h" |
| 27 |
#include "extra_data.h" |
| 28 |
#include "log.h" |
| 29 |
#include "nextpnr.h" |
| 30 |
#include "pack.h" |
| 31 |
#include "pins.h" |
| 32 |
|
| 33 |
#define HIMBAECHEL_CONSTIDS "uarch/xilinx/constids.inc" |
| 34 |
#include "himbaechel_constids.h" |
| 35 |
|
| 36 |
NEXTPNR_NAMESPACE_BEGIN |
| 37 |
|
| 38 |
bool XC7Packer::has_illegal_fanout(NetInfo *carry) |
| 39 |
{ |
| 40 |
// FIXME: sometimes we can feed out of the chain |
| 41 |
if (carry->users.entries() > 2) |
| 42 |
return true; |
| 43 |
CellInfo *muxcy = nullptr, *xorcy = nullptr; |
| 44 |
for (auto &usr : carry->users) { |
| 45 |
if (usr.cell->type == id_MUXCY) { |
| 46 |
if (muxcy != nullptr) |
| 47 |
return true; |
| 48 |
else if (usr.port != id_CI) |
| 49 |
return true; |
| 50 |
else |
| 51 |
muxcy = usr.cell; |
| 52 |
} else if (usr.cell->type == id_XORCY) { |
| 53 |
if (xorcy != nullptr) |
| 54 |
return true; |
| 55 |
else if (usr.port != id_CI) |
| 56 |
return true; |
| 57 |
else |
| 58 |
xorcy = usr.cell; |
| 59 |
} else { |
| 60 |
return true; |
| 61 |
} |
| 62 |
} |
| 63 |
if (muxcy && xorcy) { |
| 64 |
NetInfo *muxcy_s = muxcy->getPort(id_S); |
| 65 |
NetInfo *xorcy_li = xorcy->getPort(id_LI); |
| 66 |
if (muxcy_s != xorcy_li) |
| 67 |
return true; |
| 68 |
} |
| 69 |
return false; |
| 70 |
} |
| 71 |
|
| 72 |
void XilinxPacker::split_carry4s() |
| 73 |
{ |
| 74 |
std::vector<CellInfo *> carry4s; |
| 75 |
for (auto &cell : ctx->cells) { |
| 76 |
CellInfo *ci = cell.second.get(); |
| 77 |
if (ci->type != id_CARRY4) |
| 78 |
continue; |
| 79 |
carry4s.push_back(ci); |
| 80 |
} |
| 81 |
for (CellInfo *ci : carry4s) { |
| 82 |
NetInfo *cin = ci->getPort(id_CI); |
| 83 |
if (cin == nullptr || cin->name == ctx->id("$PACKER_GND_NET")) { |
| 84 |
cin = ci->getPort(id_CYINIT); |
| 85 |
} |
| 86 |
ci->disconnectPort(id_CI); |
| 87 |
ci->disconnectPort(id_CYINIT); |
| 88 |
|
| 89 |
for (int i = 0; i < 4; i++) { |
| 90 |
CellInfo *xorcy = create_cell(id_XORCY, ctx->idf("%s$split$xorcy%d", ci->name.c_str(ctx), i)); |
| 91 |
CellInfo *muxcy = create_cell(id_MUXCY, ctx->idf("%s$split$muxcy%d", ci->name.c_str(ctx), i)); |
| 92 |
muxcy->connectPort(id_CI, cin); |
| 93 |
xorcy->connectPort(id_CI, cin); |
| 94 |
ci->movePortTo(ctx->idf("DI[%d]", i), muxcy, id_DI); |
| 95 |
muxcy->connectPort(id_S, ci->getPort(ctx->id("S[" + std::to_string(i) + "]"))); |
| 96 |
ci->movePortTo(ctx->idf("S[%d]", i), xorcy, id_LI); |
| 97 |
ci->movePortTo(ctx->idf("O[%d]", i), xorcy, id_O); |
| 98 |
NetInfo *co = ci->getPort(ctx->idf("CO[%d]", i)); |
| 99 |
ci->disconnectPort(ctx->idf("CO[%d]", i)); |
| 100 |
if (!co) |
| 101 |
co = create_internal_net(ci->name, stringf("$split$co%d", i), false); |
| 102 |
muxcy->connectPort(id_O, co); |
| 103 |
cin = co; |
| 104 |
} |
| 105 |
packed_cells.insert(ci->name); |
| 106 |
} |
| 107 |
flush_cells(); |
| 108 |
} |
| 109 |
|
| 110 |
void XC7Packer::pack_carries() |
| 111 |
{ |
| 112 |
log_info("Packing carries..\n"); |
| 113 |
split_carry4s(); |
| 114 |
std::vector<CellInfo *> root_muxcys; |
| 115 |
// Find MUXCYs |
| 116 |
for (auto &cell : ctx->cells) { |
| 117 |
CellInfo *ci = cell.second.get(); |
| 118 |
if (ci->type != id_MUXCY) |
| 119 |
continue; |
| 120 |
NetInfo *ci_net = ci->getPort(id_CI); |
| 121 |
if (!ci_net || !ci_net->driver.cell || ci_net->driver.cell->type != id_MUXCY || has_illegal_fanout(ci_net)) { |
| 122 |
root_muxcys.push_back(ci); |
| 123 |
} |
| 124 |
} |
| 125 |
|
| 126 |
// Create chains from root MUXCYs |
| 127 |
pool<IdString> processed_muxcys; |
| 128 |
std::vector<CarryGroup> groups; |
| 129 |
int muxcy_count = 0, xorcy_count = 0; |
| 130 |
for (auto root : root_muxcys) { |
| 131 |
CarryGroup group; |
| 132 |
|
| 133 |
CellInfo *muxcy = root; |
| 134 |
NetInfo *mux_ci = nullptr; |
| 135 |
while (true) { |
| 136 |
|
| 137 |
group.muxcys.push_back(muxcy); |
| 138 |
++muxcy_count; |
| 139 |
mux_ci = muxcy->getPort(id_CI); |
| 140 |
NetInfo *mux_s = muxcy->getPort(id_S); |
| 141 |
group.xorcys.push_back(nullptr); |
| 142 |
if (mux_s != nullptr) { |
| 143 |
for (auto &user : mux_s->users) { |
| 144 |
if (user.cell->type == id_XORCY && user.port == id_LI) { |
| 145 |
CellInfo *xorcy = user.cell; |
| 146 |
NetInfo *xor_ci = xorcy->getPort(id_CI); |
| 147 |
if (xor_ci == mux_ci) { |
| 148 |
group.xorcys.back() = xorcy; |
| 149 |
++xorcy_count; |
| 150 |
break; |
| 151 |
} |
| 152 |
} |
| 153 |
} |
| 154 |
} |
| 155 |
|
| 156 |
mux_ci = muxcy->getPort(id_O); |
| 157 |
if (mux_ci == nullptr) |
| 158 |
break; |
| 159 |
if (has_illegal_fanout(mux_ci)) |
| 160 |
break; |
| 161 |
muxcy = nullptr; |
| 162 |
for (auto &user : mux_ci->users) { |
| 163 |
if (user.cell->type == id_MUXCY) { |
| 164 |
muxcy = user.cell; |
| 165 |
break; |
| 166 |
} |
| 167 |
} |
| 168 |
if (muxcy == nullptr) |
| 169 |
break; |
| 170 |
} |
| 171 |
if (mux_ci != nullptr) { |
| 172 |
if (mux_ci->users.entries() == 1 && (*mux_ci->users.begin()).cell->type == id_XORCY && |
| 173 |
(*mux_ci->users.begin()).port == id_CI) { |
| 174 |
// Trailing XORCY at end, can pack into chain. |
| 175 |
CellInfo *xorcy = (*mux_ci->users.begin()).cell; |
| 176 |
CellInfo *dummy_muxcy = create_cell(id_MUXCY, ctx->idf("%s$legal_muxcy$", xorcy->name.c_str(ctx))); |
| 177 |
dummy_muxcy->connectPort(id_CI, mux_ci); |
| 178 |
dummy_muxcy->connectPort(id_S, xorcy->getPort(id_LI)); |
| 179 |
group.muxcys.push_back(dummy_muxcy); |
| 180 |
group.xorcys.push_back(xorcy); |
| 181 |
} else if (mux_ci->users.entries() > 0) { |
| 182 |
// Users other than a MUXCY |
| 183 |
// Feed out with a zero-driving LUT and a XORCY |
| 184 |
// (creating a zero-driver using Vcc and an inverter for now...) |
| 185 |
CellInfo *zero_lut = create_lut(mux_ci->name.str(ctx) + "$feed$zero", |
| 186 |
{ctx->nets.at(ctx->id("$PACKER_VCC_NET")).get()}, nullptr, Property(1)); |
| 187 |
CellInfo *feed_xorcy = create_cell(id_XORCY, ctx->id(mux_ci->name.str(ctx) + "$feed$xor")); |
| 188 |
CellInfo *dummy_muxcy = create_cell(id_MUXCY, ctx->id(mux_ci->name.str(ctx) + "$feed$muxcy")); |
| 189 |
|
| 190 |
CellInfo *last_muxcy = mux_ci->driver.cell; |
| 191 |
|
| 192 |
last_muxcy->disconnectPort(id_O); |
| 193 |
|
| 194 |
zero_lut->connectPorts(id_O, feed_xorcy, id_LI); |
| 195 |
zero_lut->connectPorts(id_O, dummy_muxcy, id_S); |
| 196 |
last_muxcy->connectPorts(id_O, feed_xorcy, id_CI); |
| 197 |
last_muxcy->connectPorts(id_O, dummy_muxcy, id_CI); |
| 198 |
|
| 199 |
feed_xorcy->connectPort(id_O, mux_ci); |
| 200 |
|
| 201 |
group.muxcys.push_back(dummy_muxcy); |
| 202 |
group.xorcys.push_back(feed_xorcy); |
| 203 |
} |
| 204 |
} |
| 205 |
|
| 206 |
groups.push_back(group); |
| 207 |
} |
| 208 |
flush_cells(); |
| 209 |
|
| 210 |
log_info(" Grouped %d MUXCYs and %d XORCYs into %d chains.\n", muxcy_count, xorcy_count, int(root_muxcys.size())); |
| 211 |
|
| 212 |
// N.B. LUT6 is not a valid type here, as CARRY requires dual outputs |
| 213 |
pool<IdString> lut_types{id_LUT1, id_LUT2, id_LUT3, id_LUT4, id_LUT5}; |
| 214 |
|
| 215 |
pool<IdString> folded_nets; |
| 216 |
|
| 217 |
for (auto &grp : groups) { |
| 218 |
std::vector<CellInfo *> carry4s; |
| 219 |
for (int i = 0; i < int(grp.muxcys.size()); i++) { |
| 220 |
int z = i % 4; |
| 221 |
CellInfo *muxcy = grp.muxcys.at(i), *xorcy = grp.xorcys.at(i); |
| 222 |
if (z == 0) |
| 223 |
carry4s.push_back(create_cell(id_CARRY4, ctx->idf("%s$PACKED_CARRY4$", muxcy->name.c_str(ctx)))); |
| 224 |
CellInfo *c4 = carry4s.back(); |
| 225 |
CellInfo *root = carry4s.front(); |
| 226 |
if (i == 0) { |
| 227 |
// Constrain initial CARRY4, forcing it to the CARRY4 of a logic tile |
| 228 |
c4->cluster = c4->name; |
| 229 |
c4->constr_abs_z = true; |
| 230 |
c4->constr_z = BEL_CARRY4; |
| 231 |
} else if (z == 0) { |
| 232 |
// Constrain relative to the root carry4 |
| 233 |
c4->cluster = root->name; |
| 234 |
root->constr_children.push_back(c4); |
| 235 |
c4->constr_x = 0; |
| 236 |
// Looks no CARRY4 on the tile of which grid_y is a multiple of 26. Skip them |
| 237 |
c4->constr_y = -(i / 4 + i / (4 * 25)); |
| 238 |
c4->constr_abs_z = true; |
| 239 |
c4->constr_z = BEL_CARRY4; |
| 240 |
} |
| 241 |
// Fold CI->CO connections into the CARRY4, except for those external ones every 8 units |
| 242 |
if (z == 0 && i == 0) { |
| 243 |
muxcy->movePortTo(id_CI, c4, id_CYINIT); |
| 244 |
} else if (z == 0 && i > 0) { |
| 245 |
muxcy->movePortTo(id_CI, c4, id_CI); |
| 246 |
} else { |
| 247 |
NetInfo *muxcy_ci = muxcy->getPort(id_CI); |
| 248 |
if (muxcy_ci) |
| 249 |
folded_nets.insert(muxcy_ci->name); |
| 250 |
muxcy->disconnectPort(id_CI); |
| 251 |
} |
| 252 |
if (z == 3) { |
| 253 |
muxcy->movePortTo(id_O, c4, ctx->id("CO[3]")); |
| 254 |
} else { |
| 255 |
NetInfo *muxcy_o = muxcy->getPort(id_O); |
| 256 |
if (muxcy_o) |
| 257 |
folded_nets.insert(muxcy_o->name); |
| 258 |
muxcy->disconnectPort(id_O); |
| 259 |
} |
| 260 |
// Replace connections into the MUXCY with external CARRY4 ports |
| 261 |
muxcy->movePortTo(id_S, c4, ctx->idf("S[%d]", z)); |
| 262 |
muxcy->movePortTo(id_DI, c4, ctx->idf("DI[%d]", z)); |
| 263 |
packed_cells.insert(muxcy->name); |
| 264 |
// Fold MUXCY->XORCY into the CARRY4, if there is a XORCY |
| 265 |
if (xorcy) { |
| 266 |
// Replace XORCY output with external CARRY4 output |
| 267 |
xorcy->movePortTo(id_O, c4, ctx->idf("O[%d]", z)); |
| 268 |
// Disconnect internal XORCY connectivity |
| 269 |
xorcy->disconnectPort(id_LI); |
| 270 |
xorcy->disconnectPort(id_DI); |
| 271 |
packed_cells.insert(xorcy->name); |
| 272 |
} |
| 273 |
// Check legality of LUTs driving CARRY4, making them legal if they aren't already |
| 274 |
NetInfo *c4_s = c4->getPort(ctx->idf("S[%d]", z)); |
| 275 |
NetInfo *c4_di = c4->getPort(ctx->idf("DI[%d]", z)); |
| 276 |
// Keep track of the total LUT input count; cannot exceed five or the LUTs cannot be packed together |
| 277 |
pool<IdString> unique_lut_inputs; |
| 278 |
int s_inputs = 0, d_inputs = 0; |
| 279 |
// Check that S and DI are validy and unqiuely driven by LUTs |
| 280 |
// FIXME: in multiple fanout cases, cell duplication will probably be cheaper |
| 281 |
// than feed-throughs |
| 282 |
CellInfo *s_lut = nullptr, *di_lut = nullptr; |
| 283 |
if (c4_s) { |
| 284 |
if (c4_s->users.entries() == 1 && c4_s->driver.cell != nullptr && |
| 285 |
lut_types.count(c4_s->driver.cell->type)) { |
| 286 |
s_lut = c4_s->driver.cell; |
| 287 |
for (int j = 0; j < 5; j++) { |
| 288 |
NetInfo *ix = s_lut->getPort(ctx->idf("I%d", j)); |
| 289 |
if (ix) { |
| 290 |
unique_lut_inputs.insert(ix->name); |
| 291 |
s_inputs++; |
| 292 |
} |
| 293 |
} |
| 294 |
} |
| 295 |
} |
| 296 |
if (c4_di) { |
| 297 |
if (c4_di->users.entries() == 1 && c4_di->driver.cell != nullptr && |
| 298 |
lut_types.count(c4_di->driver.cell->type)) { |
| 299 |
di_lut = c4_di->driver.cell; |
| 300 |
for (int j = 0; j < 5; j++) { |
| 301 |
NetInfo *ix = di_lut->getPort(ctx->idf("I%d", j)); |
| 302 |
if (ix) { |
| 303 |
unique_lut_inputs.insert(ix->name); |
| 304 |
d_inputs++; |
| 305 |
} |
| 306 |
} |
| 307 |
} |
| 308 |
} |
| 309 |
int lut_inp_count = int(unique_lut_inputs.size()); |
| 310 |
if (!s_lut) |
| 311 |
++lut_inp_count; // for feedthrough |
| 312 |
if (!di_lut) |
| 313 |
++lut_inp_count; // for feedthrough |
| 314 |
if (lut_inp_count > 5) { |
| 315 |
// Must use feedthrough for at least one LUT |
| 316 |
di_lut = nullptr; |
| 317 |
if (s_inputs > 4) |
| 318 |
s_lut = nullptr; |
| 319 |
} |
| 320 |
// If LUTs are nullptr, that means we need a feedthrough lut |
| 321 |
if (!s_lut && c4_s) { |
| 322 |
PortRef pr; |
| 323 |
pr.cell = c4; |
| 324 |
pr.port = ctx->idf("S[%d]", z); |
| 325 |
auto s_feed = feed_through_lut(c4_s, {pr}); |
| 326 |
s_lut = s_feed; |
| 327 |
} |
| 328 |
if (!di_lut && c4_di) { |
| 329 |
PortRef pr; |
| 330 |
pr.cell = c4; |
| 331 |
pr.port = ctx->idf("DI[%d]", z); |
| 332 |
auto di_feed = feed_through_lut(c4_di, {pr}); |
| 333 |
di_lut = di_feed; |
| 334 |
} |
| 335 |
// Constrain LUTs relative to root CARRY4 |
| 336 |
if (s_lut) { |
| 337 |
root->constr_children.push_back(s_lut); |
| 338 |
s_lut->cluster = root->name; |
| 339 |
s_lut->constr_x = 0; |
| 340 |
s_lut->constr_y = -(i / 4 + i / (4 * 25)); |
| 341 |
s_lut->constr_abs_z = true; |
| 342 |
s_lut->constr_z = (z << 4 | BEL_6LUT); |
| 343 |
} |
| 344 |
if (di_lut) { |
| 345 |
root->constr_children.push_back(di_lut); |
| 346 |
di_lut->cluster = root->name; |
| 347 |
di_lut->constr_x = 0; |
| 348 |
di_lut->constr_y = -(i / 4 + i / (4 * 25)); |
| 349 |
di_lut->constr_abs_z = true; |
| 350 |
di_lut->constr_z = (z << 4 | BEL_5LUT); |
| 351 |
} |
| 352 |
} |
| 353 |
} |
| 354 |
flush_cells(); |
| 355 |
|
| 356 |
for (auto net : folded_nets) |
| 357 |
ctx->nets.erase(net); |
| 358 |
|
| 359 |
// XORCYs and MUXCYs not part of any chain (and therefore not packed into a CARRY4) must now be blasted |
| 360 |
// to boring soft logic (LUT2 or LUT3 - these will become SLICE_LUTXs later in the flow.) |
| 361 |
int remaining_muxcy = 0, remaining_xorcy = 0; |
| 362 |
for (auto &cell : ctx->cells) { |
| 363 |
if (cell.second->type == id_MUXCY) |
| 364 |
++remaining_muxcy; |
| 365 |
else if (cell.second->type == id_XORCY) |
| 366 |
++remaining_xorcy; |
| 367 |
} |
| 368 |
dict<IdString, XFormRule> softlogic_rules; |
| 369 |
softlogic_rules[id_MUXCY].new_type = id_LUT3; |
| 370 |
softlogic_rules[id_MUXCY].port_xform[id_DI] = id_I0; |
| 371 |
softlogic_rules[id_MUXCY].port_xform[id_CI] = id_I1; |
| 372 |
softlogic_rules[id_MUXCY].port_xform[id_S] = id_I2; |
| 373 |
// DI 1010 1010 |
| 374 |
// CI 1100 1100 |
| 375 |
// S 1111 0000 |
| 376 |
// O 1100 1010 |
| 377 |
softlogic_rules[id_MUXCY].set_params.emplace_back(id_INIT, Property(0xCA)); |
| 378 |
|
| 379 |
softlogic_rules[id_XORCY].new_type = id_LUT2; |
| 380 |
softlogic_rules[id_XORCY].port_xform[id_CI] = id_I0; |
| 381 |
softlogic_rules[id_XORCY].port_xform[id_LI] = id_I1; |
| 382 |
// CI 1100 |
| 383 |
// LI 1010 |
| 384 |
// O 0110 |
| 385 |
softlogic_rules[id_XORCY].set_params.emplace_back(id_INIT, Property(0x6)); |
| 386 |
|
| 387 |
generic_xform(softlogic_rules, false); |
| 388 |
log_info(" Blasted %d non-chain MUXCYs and %d non-chain XORCYs to soft logic\n", remaining_muxcy, |
| 389 |
remaining_xorcy); |
| 390 |
|
| 391 |
// Finally, use generic_xform to remove the [] from bus ports; and set up the logical-physical mapping for |
| 392 |
// RapidWright |
| 393 |
dict<IdString, XFormRule> c4_rules; |
| 394 |
c4_rules[id_CARRY4].new_type = id_CARRY4; |
| 395 |
c4_rules[id_CARRY4].port_xform[id_CI] = id_CIN; |
| 396 |
|
| 397 |
for (auto &cell : ctx->cells) { |
| 398 |
CellInfo *ci = cell.second.get(); |
| 399 |
if (ci->type != id_CARRY4) |
| 400 |
continue; |
| 401 |
xform_cell(c4_rules, ci); |
| 402 |
} |
| 403 |
} |
| 404 |
|
| 405 |
NEXTPNR_NAMESPACE_END |