Debian Codegraph @

himbaechel/uarch/xilinx/pack_carry.cc

raw
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