1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
/*
* yosys -- Yosys Open SYnthesis Suite
*
* Copyright (C) 2017 Clifford Wolf <clifford@clifford.at>
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*
*/
#include "kernel/yosys.h"
#include "kernel/sigtools.h"
#include "kernel/modtools.h"
USING_YOSYS_NAMESPACE
PRIVATE_NAMESPACE_BEGIN
void demorgan_worker(
ModIndex& index,
Cell *cell,
unsigned int& cells_changed)
{
SigMap& sigmap = index.sigmap;
auto m = cell->module;
//TODO: Add support for reduce_xor
//DeMorgan of XOR is either XOR (if even number of inputs) or XNOR (if odd number)
if( (cell->type != "$reduce_and") && (cell->type != "$reduce_or") )
return;
auto insig = sigmap(cell->getPort("\\A"));
log("Inspecting %s cell %s (%d inputs)\n", log_id(cell->type), log_id(cell->name), GetSize(insig));
int num_inverted = 0;
for(int i=0; i<GetSize(insig); i++)
{
auto b = insig[i];
//See if this bit is driven by a $not cell
//TODO: do other stuff like nor/nand?
pool<ModIndex::PortInfo> ports = index.query_ports(b);
bool inverted = false;
for(auto x : ports)
{
if(x.port == "\\Y" && x.cell->type == "$_NOT_")
{
inverted = true;
break;
}
}
if(inverted)
num_inverted ++;
}
//Stop if less than half of the inputs are inverted
if(num_inverted*2 < GetSize(insig))
{
log(" %d / %d inputs are inverted, not pushing\n", num_inverted, GetSize(insig));
return;
}
//More than half of the inputs are inverted! Push through
cells_changed ++;
log(" %d / %d inputs are inverted, pushing inverter through reduction\n", num_inverted, GetSize(insig));
//For each input, either add or remove the inverter as needed
//TODO: this duplicates the loop up above, can we refactor it?
for(int i=0; i<GetSize(insig); i++)
{
auto b = insig[i];
//See if this bit is driven by a $not cell
//TODO: do other stuff like nor/nand?
pool<ModIndex::PortInfo> ports = index.query_ports(b);
RTLIL::Cell* srcinv = NULL;
for(auto x : ports)
{
if(x.port == "\\Y" && x.cell->type == "$_NOT_")
{
srcinv = x.cell;
break;
}
}
//We are NOT inverted! Add an inverter
if(!srcinv)
{
auto inverted_b = m->addWire(NEW_ID);
m->addNot(NEW_ID, RTLIL::SigSpec(b), RTLIL::SigSpec(inverted_b));
insig[i] = inverted_b;
}
//We ARE inverted - bypass it
//Don't automatically delete the inverter since other stuff might still use it
else
insig[i] = srcinv->getPort("\\A");
}
//Cosmetic fixup: If our input is just a scrambled version of one bus, rearrange it
//Reductions are all commutative, so there's no point in having them in a weird order
bool same_signal = true;
RTLIL::Wire* srcwire = insig[0].wire;
dict<int, int> seen_bits;
for(int i=0; i<GetSize(insig); i++)
seen_bits[i] = 0;
for(int i=0; i<GetSize(insig); i++)
{
seen_bits[insig[i].offset] ++;
if(insig[i].wire != srcwire)
{
same_signal = false;
break;
}
}
if(same_signal)
{
//Make sure we've seen every bit exactly once
bool every_bit_once = true;
for(int i=0; i<GetSize(insig); i++)
{
if(seen_bits[i] != 1)
{
every_bit_once = false;
break;
}
}
//All good? Just use the whole wire as-is without any reordering
//We do have to swap MSB to LSB b/c that's the way the reduction cells seem to work?
//Unclear on why this isn't sorting properly
//TODO: can we do SigChunks instead of single bits if we have subsets of a bus?
if(every_bit_once && (GetSize(insig) == srcwire->width) )
{
log("Rearranging bits\n");
RTLIL::SigSpec newsig;
for(int i=0; i<GetSize(insig); i++)
newsig.append(RTLIL::SigBit(srcwire, GetSize(insig) - i - 1));
insig = newsig;
insig.sort();
}
}
//Push the new input signal back to the reduction (after bypassing/adding inverters)
cell->setPort("\\A", insig);
//Change the cell type
if(cell->type == "$reduce_and")
cell->type = "$reduce_or";
else if(cell->type == "$reduce_or")
cell->type = "$reduce_and";
//don't change XOR
//Add an inverter to the output
auto inverted_output = cell->getPort("\\Y");
auto uninverted_output = m->addWire(NEW_ID);
m->addNot(NEW_ID, RTLIL::SigSpec(uninverted_output), inverted_output);
cell->setPort("\\Y", uninverted_output);
}
struct OptDemorganPass : public Pass {
OptDemorganPass() : Pass("opt_demorgan", "Optimize reductions with DeMorgan equivalents") { }
virtual void help()
{
// |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
log("\n");
log(" opt_demorgan [selection]\n");
log("\n");
log("This pass pushes inverters through $reduce_* cells if this will reduce the\n");
log("overall gate count of the circuit\n");
log("\n");
}
virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
{
log_header(design, "Executing OPT_DEMORGAN pass (push inverters through $reduce_* cells).\n");
int argidx = 0;
extra_args(args, argidx, design);
unsigned int cells_changed = 0;
for (auto module : design->selected_modules())
{
ModIndex index(module);
for (auto cell : module->selected_cells())
demorgan_worker(index, cell, cells_changed);
}
if(cells_changed)
log("Pushed inverters through %u reductions\n", cells_changed);
}
} OptDemorganPass;
PRIVATE_NAMESPACE_END
|
