2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
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.
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.
20 #include "kernel/yosys.h"
21 #include "kernel/sigtools.h"
22 #include "kernel/macc.h"
25 PRIVATE_NAMESPACE_BEGIN
29 RTLIL::Module
*module
;
41 std::vector
<RTLIL::Cell
*> cells
;
42 RTLIL::SigSpec a
, b
, c
, y
;
43 std::vector
<std::tuple
<bool, bool, bool, bool, RTLIL::SigSpec
>> cmp
;
44 bool is_signed
, invert_b
;
46 RTLIL::Cell
*alu_cell
;
47 RTLIL::SigSpec cached_lt
, cached_gt
, cached_eq
, cached_ne
;
48 RTLIL::SigSpec cached_cf
, cached_of
, cached_sf
;
50 RTLIL::SigSpec
get_lt() {
51 if (GetSize(cached_lt
) == 0)
52 cached_lt
= is_signed
? alu_cell
->module
->Xor(NEW_ID
, get_of(), get_sf()) : get_cf();
56 RTLIL::SigSpec
get_gt() {
57 if (GetSize(cached_gt
) == 0)
58 cached_gt
= alu_cell
->module
->Not(NEW_ID
, alu_cell
->module
->Or(NEW_ID
, get_lt(), get_eq()));
62 RTLIL::SigSpec
get_eq() {
63 if (GetSize(cached_eq
) == 0)
64 cached_eq
= alu_cell
->module
->ReduceAnd(NEW_ID
, alu_cell
->getPort("\\X"));
68 RTLIL::SigSpec
get_ne() {
69 if (GetSize(cached_ne
) == 0)
70 cached_ne
= alu_cell
->module
->Not(NEW_ID
, get_eq());
74 RTLIL::SigSpec
get_cf() {
75 if (GetSize(cached_cf
) == 0) {
76 cached_cf
= alu_cell
->getPort("\\CO");
77 log_assert(GetSize(cached_cf
) >= 1);
78 cached_cf
= alu_cell
->module
->Not(NEW_ID
, cached_cf
[GetSize(cached_cf
)-1]);
83 RTLIL::SigSpec
get_of() {
84 if (GetSize(cached_of
) == 0) {
85 cached_of
= {alu_cell
->getPort("\\CO"), alu_cell
->getPort("\\CI")};
86 log_assert(GetSize(cached_of
) >= 2);
87 cached_of
= alu_cell
->module
->Xor(NEW_ID
, cached_of
[GetSize(cached_of
)-1], cached_of
[GetSize(cached_of
)-2]);
92 RTLIL::SigSpec
get_sf() {
93 if (GetSize(cached_sf
) == 0) {
94 cached_sf
= alu_cell
->getPort("\\Y");
95 cached_sf
= cached_sf
[GetSize(cached_sf
)-1];
101 std::map
<RTLIL::SigBit
, int> bit_users
;
102 std::map
<RTLIL::SigSpec
, maccnode_t
*> sig_macc
;
103 std::map
<RTLIL::SigSig
, std::set
<alunode_t
*>> sig_alu
;
104 int macc_counter
, alu_counter
;
106 AlumaccWorker(RTLIL::Module
*module
) : module(module
), sigmap(module
)
112 void count_bit_users()
114 for (auto port
: module
->ports
)
115 for (auto bit
: sigmap(module
->wire(port
)))
118 for (auto cell
: module
->cells())
119 for (auto &conn
: cell
->connections())
120 for (auto bit
: sigmap(conn
.second
))
126 for (auto cell
: module
->selected_cells())
128 if (!cell
->type
.in("$pos", "$neg", "$add", "$sub", "$mul"))
131 log(" creating $macc model for %s (%s).\n", log_id(cell
), log_id(cell
->type
));
133 maccnode_t
*n
= new maccnode_t
;
134 Macc::port_t new_port
;
137 n
->y
= sigmap(cell
->getPort("\\Y"));
140 for (auto bit
: n
->y
)
141 n
->users
= std::max(n
->users
, bit_users
.at(bit
) - 1);
143 if (cell
->type
.in("$pos", "$neg"))
145 new_port
.in_a
= sigmap(cell
->getPort("\\A"));
146 new_port
.is_signed
= cell
->getParam("\\A_SIGNED").as_bool();
147 new_port
.do_subtract
= cell
->type
== "$neg";
148 n
->macc
.ports
.push_back(new_port
);
151 if (cell
->type
.in("$add", "$sub"))
153 new_port
.in_a
= sigmap(cell
->getPort("\\A"));
154 new_port
.is_signed
= cell
->getParam("\\A_SIGNED").as_bool();
155 new_port
.do_subtract
= false;
156 n
->macc
.ports
.push_back(new_port
);
158 new_port
.in_a
= sigmap(cell
->getPort("\\B"));
159 new_port
.is_signed
= cell
->getParam("\\B_SIGNED").as_bool();
160 new_port
.do_subtract
= cell
->type
== "$sub";
161 n
->macc
.ports
.push_back(new_port
);
164 if (cell
->type
.in("$mul"))
166 new_port
.in_a
= sigmap(cell
->getPort("\\A"));
167 new_port
.in_b
= sigmap(cell
->getPort("\\B"));
168 new_port
.is_signed
= cell
->getParam("\\A_SIGNED").as_bool();
169 new_port
.do_subtract
= false;
170 n
->macc
.ports
.push_back(new_port
);
173 log_assert(sig_macc
.count(n
->y
) == 0);
178 static bool macc_may_overflow(Macc
&macc
, int width
, bool is_signed
)
180 std::vector
<int> port_sizes
;
182 for (auto &port
: macc
.ports
) {
183 if (port
.is_signed
!= is_signed
)
185 if (!port
.is_signed
&& port
.do_subtract
)
187 if (GetSize(port
.in_b
))
188 port_sizes
.push_back(GetSize(port
.in_a
) + GetSize(port
.in_b
));
190 port_sizes
.push_back(GetSize(port
.in_a
));
193 std::sort(port_sizes
.begin(), port_sizes
.end());
195 int acc_sum
= 0, acc_shift
= 0;
196 for (int sz
: port_sizes
) {
197 while ((sz
- acc_shift
) > 20) {
200 acc_sum
= acc_sum
>> 1;
203 acc_sum
+= (1 << (sz
- acc_shift
)) - 1;
207 acc_sum
= acc_sum
>> 1;
211 return acc_shift
> width
;
218 std::set
<maccnode_t
*> delete_nodes
;
220 for (auto &it
: sig_macc
)
224 if (delete_nodes
.count(n
))
227 for (int i
= 0; i
< GetSize(n
->macc
.ports
); i
++)
229 auto &port
= n
->macc
.ports
[i
];
231 if (GetSize(port
.in_b
) > 0 || sig_macc
.count(port
.in_a
) == 0)
234 auto other_n
= sig_macc
.at(port
.in_a
);
236 if (other_n
->users
> 1)
239 if (GetSize(other_n
->y
) != GetSize(n
->y
) && macc_may_overflow(other_n
->macc
, GetSize(other_n
->y
), port
.is_signed
))
242 log(" merging $macc model for %s into %s.\n", log_id(other_n
->cell
), log_id(n
->cell
));
244 bool do_subtract
= port
.do_subtract
;
245 for (int j
= 0; j
< GetSize(other_n
->macc
.ports
); j
++) {
247 other_n
->macc
.ports
[j
].do_subtract
= !other_n
->macc
.ports
[j
].do_subtract
;
249 n
->macc
.ports
[i
--] = other_n
->macc
.ports
[j
];
251 n
->macc
.ports
.push_back(other_n
->macc
.ports
[j
]);
254 delete_nodes
.insert(other_n
);
258 if (delete_nodes
.empty())
261 for (auto n
: delete_nodes
) {
262 sig_macc
.erase(n
->y
);
270 std::set
<maccnode_t
*> delete_nodes
;
272 for (auto &it
: sig_macc
)
275 RTLIL::SigSpec A
, B
, C
= n
->macc
.bit_ports
;
276 bool a_signed
= false, b_signed
= false;
277 bool subtract_b
= false;
280 for (auto &port
: n
->macc
.ports
)
281 if (GetSize(port
.in_b
) > 0) {
283 } else if (GetSize(port
.in_a
) == 1 && !port
.is_signed
&& !port
.do_subtract
) {
285 } else if (GetSize(A
) || port
.do_subtract
) {
289 b_signed
= port
.is_signed
;
290 subtract_b
= port
.do_subtract
;
295 a_signed
= port
.is_signed
;
298 if (!a_signed
|| !b_signed
) {
299 if (GetSize(A
) == GetSize(n
->y
))
301 if (GetSize(B
) == GetSize(n
->y
))
303 if (a_signed
!= b_signed
)
307 if (GetSize(A
) == 0 && GetSize(C
) > 0) {
312 if (GetSize(B
) == 0 && GetSize(C
) > 0) {
323 if (!subtract_b
&& B
< A
&& GetSize(B
))
326 log(" creating $alu model for $macc %s.\n", log_id(n
->cell
));
328 alunode
= new alunode_t
;
329 alunode
->cells
.push_back(n
->cell
);
330 alunode
->is_signed
= a_signed
;
331 alunode
->invert_b
= subtract_b
;
338 sig_alu
[RTLIL::SigSig(A
, B
)].insert(alunode
);
339 delete_nodes
.insert(n
);
343 for (auto n
: delete_nodes
) {
344 sig_macc
.erase(n
->y
);
351 for (auto &it
: sig_macc
)
354 auto cell
= module
->addCell(NEW_ID
, "$macc");
357 log(" creating $macc cell for %s: %s\n", log_id(n
->cell
), log_id(cell
));
359 n
->macc
.optimize(GetSize(n
->y
));
360 n
->macc
.to_cell(cell
);
361 cell
->setPort("\\Y", n
->y
);
362 cell
->fixup_parameters();
363 module
->remove(n
->cell
);
370 void extract_cmp_alu()
372 std::vector
<RTLIL::Cell
*> lge_cells
, eq_cells
;
374 for (auto cell
: module
->selected_cells())
376 if (cell
->type
.in("$lt", "$le", "$ge", "$gt"))
377 lge_cells
.push_back(cell
);
378 if (cell
->type
.in("$eq", "$eqx", "$ne", "$nex"))
379 eq_cells
.push_back(cell
);
382 for (auto cell
: lge_cells
)
384 log(" creating $alu model for %s (%s):", log_id(cell
), log_id(cell
->type
));
386 bool cmp_less
= cell
->type
.in("$lt", "$le");
387 bool cmp_equal
= cell
->type
.in("$le", "$ge");
388 bool is_signed
= cell
->getParam("\\A_SIGNED").as_bool();
390 RTLIL::SigSpec A
= sigmap(cell
->getPort("\\A"));
391 RTLIL::SigSpec B
= sigmap(cell
->getPort("\\B"));
392 RTLIL::SigSpec Y
= sigmap(cell
->getPort("\\Y"));
394 if (B
< A
&& GetSize(B
)) {
395 cmp_less
= !cmp_less
;
399 alunode_t
*n
= nullptr;
401 for (auto node
: sig_alu
[RTLIL::SigSig(A
, B
)])
402 if (node
->is_signed
== is_signed
&& node
->invert_b
&& node
->c
== RTLIL::S1
) {
412 n
->y
= module
->addWire(NEW_ID
, std::max(GetSize(A
), GetSize(B
)));
413 n
->is_signed
= is_signed
;
415 sig_alu
[RTLIL::SigSig(A
, B
)].insert(n
);
418 log(" merged with %s.\n", log_id(n
->cells
.front()));
421 n
->cells
.push_back(cell
);
422 n
->cmp
.push_back(std::make_tuple(cmp_less
, !cmp_less
, cmp_equal
, false, Y
));
425 for (auto cell
: eq_cells
)
427 bool cmp_equal
= cell
->type
.in("$eq", "$eqx");
428 bool is_signed
= cell
->getParam("\\A_SIGNED").as_bool();
430 RTLIL::SigSpec A
= sigmap(cell
->getPort("\\A"));
431 RTLIL::SigSpec B
= sigmap(cell
->getPort("\\B"));
432 RTLIL::SigSpec Y
= sigmap(cell
->getPort("\\Y"));
434 if (B
< A
&& GetSize(B
))
437 alunode_t
*n
= nullptr;
439 for (auto node
: sig_alu
[RTLIL::SigSig(A
, B
)])
440 if (node
->is_signed
== is_signed
&& node
->invert_b
&& node
->c
== RTLIL::S1
) {
446 log(" creating $alu model for %s (%s): merged with %s.\n", log_id(cell
), log_id(cell
->type
), log_id(n
->cells
.front()));
447 n
->cells
.push_back(cell
);
448 n
->cmp
.push_back(std::make_tuple(false, false, cmp_equal
, !cmp_equal
, Y
));
455 for (auto &it1
: sig_alu
)
456 for (auto n
: it1
.second
)
458 if (GetSize(n
->b
) == 0 && GetSize(n
->c
) == 0 && GetSize(n
->cmp
) == 0)
460 n
->alu_cell
= module
->addPos(NEW_ID
, n
->a
, n
->y
, n
->is_signed
);
462 log(" creating $pos cell for ");
463 for (int i
= 0; i
< GetSize(n
->cells
); i
++)
464 log("%s%s", i
? ", ": "", log_id(n
->cells
[i
]));
465 log(": %s\n", log_id(n
->alu_cell
));
470 n
->alu_cell
= module
->addCell(NEW_ID
, "$alu");
473 log(" creating $alu cell for ");
474 for (int i
= 0; i
< GetSize(n
->cells
); i
++)
475 log("%s%s", i
? ", ": "", log_id(n
->cells
[i
]));
476 log(": %s\n", log_id(n
->alu_cell
));
478 n
->alu_cell
->setPort("\\A", n
->a
);
479 n
->alu_cell
->setPort("\\B", n
->b
);
480 n
->alu_cell
->setPort("\\CI", GetSize(n
->c
) ? n
->c
: RTLIL::S0
);
481 n
->alu_cell
->setPort("\\BI", n
->invert_b
? RTLIL::S1
: RTLIL::S0
);
482 n
->alu_cell
->setPort("\\Y", n
->y
);
483 n
->alu_cell
->setPort("\\X", module
->addWire(NEW_ID
, GetSize(n
->y
)));
484 n
->alu_cell
->setPort("\\CO", module
->addWire(NEW_ID
, GetSize(n
->y
)));
485 n
->alu_cell
->fixup_parameters(n
->is_signed
, n
->is_signed
);
487 for (auto &it
: n
->cmp
)
489 bool cmp_lt
= std::get
<0>(it
);
490 bool cmp_gt
= std::get
<1>(it
);
491 bool cmp_eq
= std::get
<2>(it
);
492 bool cmp_ne
= std::get
<3>(it
);
493 RTLIL::SigSpec cmp_y
= std::get
<4>(it
);
496 if (cmp_lt
) sig
.append(n
->get_lt());
497 if (cmp_gt
) sig
.append(n
->get_gt());
498 if (cmp_eq
) sig
.append(n
->get_eq());
499 if (cmp_ne
) sig
.append(n
->get_ne());
501 if (GetSize(sig
) > 1)
502 sig
= module
->ReduceOr(NEW_ID
, sig
);
504 sig
.extend(GetSize(cmp_y
));
505 module
->connect(cmp_y
, sig
);
509 for (auto c
: n
->cells
)
519 log("Extracting $alu and $macc cells in module %s:\n", log_id(module
));
529 log(" created %d $alu and %d $macc cells.\n", alu_counter
, macc_counter
);
533 struct AlumaccPass
: public Pass
{
534 AlumaccPass() : Pass("alumacc", "extract ALU and MACC cells") { }
537 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
539 log(" alumacc [selection]\n");
541 log("This pass translates arithmetic operations like $add, $mul, $lt, etc. to $alu\n");
542 log("and $macc cells.\n");
545 virtual void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
)
547 log_header("Executing ALUMACC pass (create $alu and $macc cells).\n");
550 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
551 // if (args[argidx] == "-foobar") {
552 // foobar_mode = true;
557 extra_args(args
, argidx
, design
);
559 for (auto mod
: design
->selected_modules())
560 if (!mod
->has_processes_warn()) {
561 AlumaccWorker
worker(mod
);
567 PRIVATE_NAMESPACE_END