2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2017 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/modtools.h"
25 PRIVATE_NAMESPACE_BEGIN
30 unsigned int& cells_changed
)
32 SigMap
& sigmap
= index
.sigmap
;
33 auto m
= cell
->module
;
35 //TODO: Add support for reduce_xor
36 //DeMorgan of XOR is either XOR (if even number of inputs) or XNOR (if odd number)
38 if( (cell
->type
!= "$reduce_and") && (cell
->type
!= "$reduce_or") )
41 auto insig
= sigmap(cell
->getPort("\\A"));
42 log("Inspecting %s cell %s (%d inputs)\n", log_id(cell
->type
), log_id(cell
->name
), GetSize(insig
));
44 for(int i
=0; i
<GetSize(insig
); i
++)
48 //See if this bit is driven by a $not cell
49 //TODO: do other stuff like nor/nand?
50 pool
<ModIndex::PortInfo
> ports
= index
.query_ports(b
);
51 bool inverted
= false;
54 if(x
.port
== "\\Y" && x
.cell
->type
== "$_NOT_")
65 //Stop if less than half of the inputs are inverted
66 if(num_inverted
*2 < GetSize(insig
))
68 log(" %d / %d inputs are inverted, not pushing\n", num_inverted
, GetSize(insig
));
72 //More than half of the inputs are inverted! Push through
74 log(" %d / %d inputs are inverted, pushing inverter through reduction\n", num_inverted
, GetSize(insig
));
76 //For each input, either add or remove the inverter as needed
77 //TODO: this duplicates the loop up above, can we refactor it?
78 for(int i
=0; i
<GetSize(insig
); i
++)
82 //See if this bit is driven by a $not cell
83 //TODO: do other stuff like nor/nand?
84 pool
<ModIndex::PortInfo
> ports
= index
.query_ports(b
);
85 RTLIL::Cell
* srcinv
= NULL
;
88 if(x
.port
== "\\Y" && x
.cell
->type
== "$_NOT_")
95 //We are NOT inverted! Add an inverter
98 auto inverted_b
= m
->addWire(NEW_ID
);
99 m
->addNot(NEW_ID
, RTLIL::SigSpec(b
), RTLIL::SigSpec(inverted_b
));
100 insig
[i
] = inverted_b
;
103 //We ARE inverted - bypass it
104 //Don't automatically delete the inverter since other stuff might still use it
106 insig
[i
] = srcinv
->getPort("\\A");
109 //Cosmetic fixup: If our input is just a scrambled version of one bus, rearrange it
110 //Reductions are all commutative, so there's no point in having them in a weird order
111 bool same_signal
= true;
112 RTLIL::Wire
* srcwire
= insig
[0].wire
;
113 dict
<int, int> seen_bits
;
114 for(int i
=0; i
<GetSize(insig
); i
++)
116 for(int i
=0; i
<GetSize(insig
); i
++)
118 seen_bits
[insig
[i
].offset
] ++;
119 if(insig
[i
].wire
!= srcwire
)
127 //Make sure we've seen every bit exactly once
128 bool every_bit_once
= true;
129 for(int i
=0; i
<GetSize(insig
); i
++)
131 if(seen_bits
[i
] != 1)
133 every_bit_once
= false;
138 //All good? Just use the whole wire as-is without any reordering
139 //We do have to swap MSB to LSB b/c that's the way the reduction cells seem to work?
140 //Unclear on why this isn't sorting properly
141 //TODO: can we do SigChunks instead of single bits if we have subsets of a bus?
142 if(every_bit_once
&& (GetSize(insig
) == srcwire
->width
) )
144 log("Rearranging bits\n");
145 RTLIL::SigSpec newsig
;
146 for(int i
=0; i
<GetSize(insig
); i
++)
147 newsig
.append(RTLIL::SigBit(srcwire
, GetSize(insig
) - i
- 1));
153 //Push the new input signal back to the reduction (after bypassing/adding inverters)
154 cell
->setPort("\\A", insig
);
156 //Change the cell type
157 if(cell
->type
== "$reduce_and")
158 cell
->type
= "$reduce_or";
159 else if(cell
->type
== "$reduce_or")
160 cell
->type
= "$reduce_and";
163 //Add an inverter to the output
164 auto inverted_output
= cell
->getPort("\\Y");
165 auto uninverted_output
= m
->addWire(NEW_ID
);
166 m
->addNot(NEW_ID
, RTLIL::SigSpec(uninverted_output
), inverted_output
);
167 cell
->setPort("\\Y", uninverted_output
);
170 struct OptDemorganPass
: public Pass
{
171 OptDemorganPass() : Pass("opt_demorgan", "Optimize reductions with DeMorgan equivalents") { }
172 void help() YS_OVERRIDE
174 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
176 log(" opt_demorgan [selection]\n");
178 log("This pass pushes inverters through $reduce_* cells if this will reduce the\n");
179 log("overall gate count of the circuit\n");
182 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
184 log_header(design
, "Executing OPT_DEMORGAN pass (push inverters through $reduce_* cells).\n");
187 extra_args(args
, argidx
, design
);
189 unsigned int cells_changed
= 0;
190 for (auto module
: design
->selected_modules())
192 ModIndex
index(module
);
193 for (auto cell
: module
->selected_cells())
194 demorgan_worker(index
, cell
, cells_changed
);
198 log("Pushed inverters through %u reductions\n", cells_changed
);
202 PRIVATE_NAMESPACE_END