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/cellaigs.h"
32 bool AigNode::operator==(const AigNode
&other
) const
34 if (portname
!= other
.portname
) return false;
35 if (portbit
!= other
.portbit
) return false;
36 if (inverter
!= other
.inverter
) return false;
37 if (left_parent
!= other
.left_parent
) return false;
38 if (right_parent
!= other
.right_parent
) return false;
42 unsigned int AigNode::hash() const
44 unsigned int h
= mkhash_init
;
45 h
= mkhash(portname
.hash(), portbit
);
46 h
= mkhash(h
, inverter
);
47 h
= mkhash(h
, left_parent
);
48 h
= mkhash(h
, right_parent
);
52 bool Aig::operator==(const Aig
&other
) const
54 return name
== other
.name
;
57 unsigned int Aig::hash() const
59 return hash_ops
<std::string
>::hash(name
);
66 idict
<AigNode
> aig_indices
;
71 AigMaker(Aig
*aig
, Cell
*cell
) : aig(aig
), cell(cell
)
77 int node2index(const AigNode
&node
)
79 if (node
.left_parent
> node
.right_parent
) {
81 std::swap(n
.left_parent
, n
.right_parent
);
85 if (!aig_indices
.count(node
)) {
86 aig_indices
.expect(node
, GetSize(aig
->nodes
));
87 aig
->nodes
.push_back(node
);
90 return aig_indices
.at(node
);
93 int bool_node(bool value
)
96 node
.inverter
= value
;
97 return node2index(node
);
100 int inport(IdString portname
, int portbit
= 0, bool inverter
= false)
102 if (portbit
>= GetSize(cell
->getPort(portname
))) {
103 if (cell
->parameters
.count(portname
.str() + "_SIGNED") && cell
->getParam(portname
.str() + "_SIGNED").as_bool())
104 return inport(portname
, GetSize(cell
->getPort(portname
))-1, inverter
);
105 return bool_node(inverter
);
109 node
.portname
= portname
;
110 node
.portbit
= portbit
;
111 node
.inverter
= inverter
;
112 return node2index(node
);
115 vector
<int> inport_vec(IdString portname
, int width
)
118 for (int i
= 0; i
< width
; i
++)
119 vec
.push_back(inport(portname
, i
));
123 int not_inport(IdString portname
, int portbit
= 0)
125 return inport(portname
, portbit
, true);
130 AigNode
node(aig_indices
[A
]);
131 node
.outports
.clear();
132 node
.inverter
= !node
.inverter
;
133 return node2index(node
);
136 int and_gate(int A
, int B
, bool inverter
= false)
139 return inverter
? not_gate(A
) : A
;
141 const AigNode
&nA
= aig_indices
[A
];
142 const AigNode
&nB
= aig_indices
[B
];
145 nB_inv
.inverter
= !nB_inv
.inverter
;
148 return bool_node(inverter
);
150 bool nA_bool
= nA
.portbit
< 0 && nA
.left_parent
< 0 && nA
.right_parent
< 0;
151 bool nB_bool
= nB
.portbit
< 0 && nB
.left_parent
< 0 && nB
.right_parent
< 0;
153 if (nA_bool
&& nB_bool
) {
154 bool bA
= nA
.inverter
;
155 bool bB
= nB
.inverter
;
156 return bool_node(inverter
!= (bA
&& bB
));
160 bool bA
= nA
.inverter
;
162 return bA
? not_gate(B
) : bool_node(true);
163 return bA
? B
: bool_node(false);
167 bool bB
= nB
.inverter
;
169 return bB
? not_gate(A
) : bool_node(true);
170 return bB
? A
: bool_node(false);
174 node
.inverter
= inverter
;
175 node
.left_parent
= A
;
176 node
.right_parent
= B
;
177 return node2index(node
);
180 int nand_gate(int A
, int B
)
182 return and_gate(A
, B
, true);
185 int or_gate(int A
, int B
)
187 return nand_gate(not_gate(A
), not_gate(B
));
190 int nor_gate(int A
, int B
)
192 return and_gate(not_gate(A
), not_gate(B
));
195 int xor_gate(int A
, int B
)
197 return nor_gate(and_gate(A
, B
), nor_gate(A
, B
));
200 int xnor_gate(int A
, int B
)
202 return or_gate(and_gate(A
, B
), nor_gate(A
, B
));
205 int andnot_gate(int A
, int B
)
207 return and_gate(A
, not_gate(B
));
210 int ornot_gate(int A
, int B
)
212 return or_gate(A
, not_gate(B
));
215 int mux_gate(int A
, int B
, int S
)
217 return or_gate(and_gate(A
, not_gate(S
)), and_gate(B
, S
));
220 vector
<int> adder(const vector
<int> &A
, const vector
<int> &B
, int carry
, vector
<int> *X
= nullptr, vector
<int> *CO
= nullptr)
222 vector
<int> Y(GetSize(A
));
223 log_assert(GetSize(A
) == GetSize(B
));
224 for (int i
= 0; i
< GetSize(A
); i
++) {
225 Y
[i
] = xor_gate(xor_gate(A
[i
], B
[i
]), carry
);
226 carry
= or_gate(and_gate(A
[i
], B
[i
]), and_gate(or_gate(A
[i
], B
[i
]), carry
));
228 X
->at(i
) = xor_gate(A
[i
], B
[i
]);
235 void outport(int node
, IdString portname
, int portbit
= 0)
237 if (portbit
< GetSize(cell
->getPort(portname
)))
238 aig
->nodes
.at(node
).outports
.push_back(pair
<IdString
, int>(portname
, portbit
));
241 void outport_bool(int node
, IdString portname
)
243 outport(node
, portname
);
244 for (int i
= 1; i
< GetSize(cell
->getPort(portname
)); i
++)
245 outport(bool_node(false), portname
, i
);
248 void outport_vec(const vector
<int> &vec
, IdString portname
)
250 for (int i
= 0; i
< GetSize(vec
); i
++)
251 outport(vec
.at(i
), portname
, i
);
257 if (cell
->type
[0] != '$')
260 AigMaker
mk(this, cell
);
261 name
= cell
->type
.str();
264 bool mkname_a_signed
= false;
265 bool mkname_b_signed
= false;
266 bool mkname_is_signed
= false;
268 cell
->parameters
.sort();
269 for (auto p
: cell
->parameters
)
271 if (p
.first
== ID(A_WIDTH
) && mkname_a_signed
) {
272 name
= mkname_last
+ stringf(":%d%c", p
.second
.as_int(), mkname_is_signed
? 'S' : 'U');
273 } else if (p
.first
== ID(B_WIDTH
) && mkname_b_signed
) {
274 name
= mkname_last
+ stringf(":%d%c", p
.second
.as_int(), mkname_is_signed
? 'S' : 'U');
277 name
+= stringf(":%d", p
.second
.as_int());
280 mkname_a_signed
= false;
281 mkname_b_signed
= false;
282 mkname_is_signed
= false;
283 if (p
.first
== ID(A_SIGNED
)) {
284 mkname_a_signed
= true;
285 mkname_is_signed
= p
.second
.as_bool();
287 if (p
.first
== ID(B_SIGNED
)) {
288 mkname_b_signed
= true;
289 mkname_is_signed
= p
.second
.as_bool();
293 if (cell
->type
.in(ID($
not), ID($_NOT_
), ID($pos
), ID($_BUF_
)))
295 for (int i
= 0; i
< GetSize(cell
->getPort(ID::Y
)); i
++) {
296 int A
= mk
.inport(ID::A
, i
);
297 int Y
= cell
->type
.in(ID($
not), ID($_NOT_
)) ? mk
.not_gate(A
) : A
;
298 mk
.outport(Y
, ID::Y
, i
);
303 if (cell
->type
.in(ID($
and), ID($_AND_
), ID($_NAND_
), ID($
or), ID($_OR_
), ID($_NOR_
), ID($
xor), ID($xnor
), ID($_XOR_
), ID($_XNOR_
), ID($_ANDNOT_
), ID($_ORNOT_
)))
305 for (int i
= 0; i
< GetSize(cell
->getPort(ID::Y
)); i
++) {
306 int A
= mk
.inport(ID::A
, i
);
307 int B
= mk
.inport(ID::B
, i
);
308 int Y
= cell
->type
.in(ID($
and), ID($_AND_
)) ? mk
.and_gate(A
, B
) :
309 cell
->type
.in(ID($_NAND_
)) ? mk
.nand_gate(A
, B
) :
310 cell
->type
.in(ID($
or), ID($_OR_
)) ? mk
.or_gate(A
, B
) :
311 cell
->type
.in(ID($_NOR_
)) ? mk
.nor_gate(A
, B
) :
312 cell
->type
.in(ID($
xor), ID($_XOR_
)) ? mk
.xor_gate(A
, B
) :
313 cell
->type
.in(ID($xnor
), ID($_XNOR_
)) ? mk
.xnor_gate(A
, B
) :
314 cell
->type
.in(ID($_ANDNOT_
)) ? mk
.andnot_gate(A
, B
) :
315 cell
->type
.in(ID($_ORNOT_
)) ? mk
.ornot_gate(A
, B
) : -1;
316 mk
.outport(Y
, ID::Y
, i
);
321 if (cell
->type
.in(ID($mux
), ID($_MUX_
)))
323 int S
= mk
.inport(ID(S
));
324 for (int i
= 0; i
< GetSize(cell
->getPort(ID::Y
)); i
++) {
325 int A
= mk
.inport(ID::A
, i
);
326 int B
= mk
.inport(ID::B
, i
);
327 int Y
= mk
.mux_gate(A
, B
, S
);
328 if (cell
->type
== ID($_NMUX_
))
330 mk
.outport(Y
, ID::Y
, i
);
335 if (cell
->type
.in(ID($reduce_and
), ID($reduce_or
), ID($reduce_xor
), ID($reduce_xnor
), ID($reduce_bool
)))
337 int Y
= mk
.inport(ID::A
, 0);
338 for (int i
= 1; i
< GetSize(cell
->getPort(ID::A
)); i
++) {
339 int A
= mk
.inport(ID::A
, i
);
340 if (cell
->type
== ID($reduce_and
)) Y
= mk
.and_gate(A
, Y
);
341 if (cell
->type
== ID($reduce_or
)) Y
= mk
.or_gate(A
, Y
);
342 if (cell
->type
== ID($reduce_bool
)) Y
= mk
.or_gate(A
, Y
);
343 if (cell
->type
== ID($reduce_xor
)) Y
= mk
.xor_gate(A
, Y
);
344 if (cell
->type
== ID($reduce_xnor
)) Y
= mk
.xor_gate(A
, Y
);
346 if (cell
->type
== ID($reduce_xnor
))
348 mk
.outport(Y
, ID::Y
, 0);
349 for (int i
= 1; i
< GetSize(cell
->getPort(ID::Y
)); i
++)
350 mk
.outport(mk
.bool_node(false), ID::Y
, i
);
354 if (cell
->type
.in(ID($logic_not
), ID($logic_and
), ID($logic_or
)))
356 int A
= mk
.inport(ID::A
, 0), Y
= -1;
357 for (int i
= 1; i
< GetSize(cell
->getPort(ID::A
)); i
++)
358 A
= mk
.or_gate(mk
.inport(ID::A
, i
), A
);
359 if (cell
->type
.in(ID($logic_and
), ID($logic_or
))) {
360 int B
= mk
.inport(ID::B
, 0);
361 for (int i
= 1; i
< GetSize(cell
->getPort(ID::B
)); i
++)
362 B
= mk
.or_gate(mk
.inport(ID::B
, i
), B
);
363 if (cell
->type
== ID($logic_and
)) Y
= mk
.and_gate(A
, B
);
364 if (cell
->type
== ID($logic_or
)) Y
= mk
.or_gate(A
, B
);
366 if (cell
->type
== ID($logic_not
)) Y
= mk
.not_gate(A
);
368 mk
.outport_bool(Y
, ID::Y
);
372 if (cell
->type
.in(ID($add
), ID($sub
)))
374 int width
= GetSize(cell
->getPort(ID::Y
));
375 vector
<int> A
= mk
.inport_vec(ID::A
, width
);
376 vector
<int> B
= mk
.inport_vec(ID::B
, width
);
377 int carry
= mk
.bool_node(false);
378 if (cell
->type
== ID($sub
)) {
381 carry
= mk
.not_gate(carry
);
383 vector
<int> Y
= mk
.adder(A
, B
, carry
);
384 mk
.outport_vec(Y
, ID::Y
);
388 if (cell
->type
== ID($alu
))
390 int width
= GetSize(cell
->getPort(ID::Y
));
391 vector
<int> A
= mk
.inport_vec(ID::A
, width
);
392 vector
<int> B
= mk
.inport_vec(ID::B
, width
);
393 int carry
= mk
.inport(ID(CI
));
394 int binv
= mk
.inport(ID(BI
));
396 n
= mk
.xor_gate(n
, binv
);
397 vector
<int> X(width
), CO(width
);
398 vector
<int> Y
= mk
.adder(A
, B
, carry
, &X
, &CO
);
399 for (int i
= 0; i
< width
; i
++)
400 X
[i
] = mk
.xor_gate(A
[i
], B
[i
]);
401 mk
.outport_vec(Y
, ID::Y
);
402 mk
.outport_vec(X
, ID(X
));
403 mk
.outport_vec(CO
, ID(CO
));
407 if (cell
->type
.in(ID($eq
), ID($ne
)))
409 int width
= max(GetSize(cell
->getPort(ID::A
)), GetSize(cell
->getPort(ID::B
)));
410 vector
<int> A
= mk
.inport_vec(ID::A
, width
);
411 vector
<int> B
= mk
.inport_vec(ID::B
, width
);
412 int Y
= mk
.bool_node(false);
413 for (int i
= 0; i
< width
; i
++)
414 Y
= mk
.or_gate(Y
, mk
.xor_gate(A
[i
], B
[i
]));
415 if (cell
->type
== ID($eq
))
417 mk
.outport_bool(Y
, ID::Y
);
421 if (cell
->type
== ID($_AOI3_
))
423 int A
= mk
.inport(ID::A
);
424 int B
= mk
.inport(ID::B
);
425 int C
= mk
.inport(ID(C
));
426 int Y
= mk
.nor_gate(mk
.and_gate(A
, B
), C
);
427 mk
.outport(Y
, ID::Y
);
431 if (cell
->type
== ID($_OAI3_
))
433 int A
= mk
.inport(ID::A
);
434 int B
= mk
.inport(ID::B
);
435 int C
= mk
.inport(ID(C
));
436 int Y
= mk
.nand_gate(mk
.or_gate(A
, B
), C
);
437 mk
.outport(Y
, ID::Y
);
441 if (cell
->type
== ID($_AOI4_
))
443 int A
= mk
.inport(ID::A
);
444 int B
= mk
.inport(ID::B
);
445 int C
= mk
.inport(ID(C
));
446 int D
= mk
.inport(ID(D
));
447 int Y
= mk
.nor_gate(mk
.and_gate(A
, B
), mk
.and_gate(C
, D
));
448 mk
.outport(Y
, ID::Y
);
452 if (cell
->type
== ID($_OAI4_
))
454 int A
= mk
.inport(ID::A
);
455 int B
= mk
.inport(ID::B
);
456 int C
= mk
.inport(ID(C
));
457 int D
= mk
.inport(ID(D
));
458 int Y
= mk
.nand_gate(mk
.or_gate(A
, B
), mk
.or_gate(C
, D
));
459 mk
.outport(Y
, ID::Y
);
467 pool
<int> used_old_ids
;
468 vector
<AigNode
> new_nodes
;
469 dict
<int, int> old_to_new_ids
;
470 old_to_new_ids
[-1] = -1;
472 for (int i
= GetSize(nodes
)-1; i
>= 0; i
--) {
473 if (!nodes
[i
].outports
.empty())
474 used_old_ids
.insert(i
);
475 if (!used_old_ids
.count(i
))
477 if (nodes
[i
].left_parent
>= 0)
478 used_old_ids
.insert(nodes
[i
].left_parent
);
479 if (nodes
[i
].right_parent
>= 0)
480 used_old_ids
.insert(nodes
[i
].right_parent
);
483 for (int i
= 0; i
< GetSize(nodes
); i
++) {
484 if (!used_old_ids
.count(i
))
486 nodes
[i
].left_parent
= old_to_new_ids
.at(nodes
[i
].left_parent
);
487 nodes
[i
].right_parent
= old_to_new_ids
.at(nodes
[i
].right_parent
);
488 old_to_new_ids
[i
] = GetSize(new_nodes
);
489 new_nodes
.push_back(nodes
[i
]);
492 new_nodes
.swap(nodes
);