2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2017 Robert Ou <rqou@robertou.com>
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"
25 PRIVATE_NAMESPACE_BEGIN
27 struct ExtractReducePass
: public Pass
35 ExtractReducePass() : Pass("extract_reduce", "converts gate chains into $reduce_* cells") { }
37 void help() YS_OVERRIDE
39 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
41 log(" extract_reduce [options] [selection]\n");
43 log("converts gate chains into $reduce_* cells\n");
45 log("This command finds chains of $_AND_, $_OR_, and $_XOR_ cells and replaces them\n");
46 log("with their corresponding $reduce_* cells. Because this command only operates on\n");
47 log("these cell types, it is recommended to map the design to only these cell types\n");
48 log("using the `abc -g` command. Note that, in some cases, it may be more effective\n");
49 log("to map the design to only $_AND_ cells, run extract_reduce, map the remaining\n");
50 log("parts of the design to AND/OR/XOR cells, and run extract_reduce a second time.\n");
52 log(" -allow-off-chain\n");
53 log(" Allows matching of cells that have loads outside the chain. These cells\n");
54 log(" will be replicated and folded into the $reduce_* cell, but the original\n");
55 log(" cell will remain, driving its original loads.\n");
59 inline bool IsRightType(Cell
* cell
, GateType gt
)
61 return (cell
->type
== "$_AND_" && gt
== GateType::And
) ||
62 (cell
->type
== "$_OR_" && gt
== GateType::Or
) ||
63 (cell
->type
== "$_XOR_" && gt
== GateType::Xor
);
66 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
68 log_header(design
, "Executing EXTRACT_REDUCE pass.\n");
72 bool allow_off_chain
= false;
73 for (argidx
= 1; argidx
< args
.size(); argidx
++)
75 if (args
[argidx
] == "-allow-off-chain")
77 allow_off_chain
= true;
82 extra_args(args
, argidx
, design
);
84 for (auto module
: design
->selected_modules())
86 SigMap
sigmap(module
);
88 // Index all of the nets in the module
89 dict
<SigBit
, Cell
*> sig_to_driver
;
90 dict
<SigBit
, pool
<Cell
*>> sig_to_sink
;
91 for (auto cell
: module
->selected_cells())
93 for (auto &conn
: cell
->connections())
95 if (cell
->output(conn
.first
))
96 for (auto bit
: sigmap(conn
.second
))
97 sig_to_driver
[bit
] = cell
;
99 if (cell
->input(conn
.first
))
101 for (auto bit
: sigmap(conn
.second
))
103 if (sig_to_sink
.count(bit
) == 0)
104 sig_to_sink
[bit
] = pool
<Cell
*>();
105 sig_to_sink
[bit
].insert(cell
);
111 // Need to check if any wires connect to module ports
112 pool
<SigBit
> port_sigs
;
113 for (auto wire
: module
->selected_wires())
114 if (wire
->port_input
|| wire
->port_output
)
115 for (auto bit
: sigmap(wire
))
116 port_sigs
.insert(bit
);
118 // Actual logic starts here
119 pool
<Cell
*> consumed_cells
;
120 for (auto cell
: module
->selected_cells())
122 if (consumed_cells
.count(cell
))
127 if (cell
->type
== "$_AND_")
129 else if (cell
->type
== "$_OR_")
131 else if (cell
->type
== "$_XOR_")
136 log("Working on cell %s...\n", cell
->name
.c_str());
138 // If looking for a single chain, follow linearly to the sink
142 Cell
* head_cell
= cell
;
146 if(!IsRightType(x
, gt
))
151 auto y
= sigmap(x
->getPort("\\Y"));
152 log_assert(y
.size() == 1);
154 // Should only continue if there is one fanout back into a cell (not to a port)
155 if (sig_to_sink
[y
[0]].size() != 1)
158 x
= *sig_to_sink
[y
[0]].begin();
161 sinks
.insert(head_cell
);
164 //If off-chain loads are allowed, we have to do a wider traversal to see what the longest chain is
167 //BFS, following all chains until they hit a cell of a different type
168 //Pick the longest one
169 auto y
= sigmap(cell
->getPort("\\Y"));
170 pool
<Cell
*> current_loads
= sig_to_sink
[y
];
171 pool
<Cell
*> next_loads
;
173 while(!current_loads
.empty())
175 //Find each sink and see what they are
176 for(auto x
: current_loads
)
178 //Not one of our gates? Don't follow any further
179 //(but add the originating cell to the list of sinks)
180 if(!IsRightType(x
, gt
))
186 //If this signal drives a port, add it to the sinks
187 //(even though it may not be the end of a chain)
188 if(port_sigs
.count(x
) && !consumed_cells
.count(x
))
191 //It's a match, search everything out from it
192 auto& next
= sig_to_sink
[x
];
194 next_loads
.insert(z
);
197 //If we couldn't find any downstream loads, stop.
198 //Create a reduction for each of the max-length chains we found
199 if(next_loads
.empty())
201 for(auto s
: current_loads
)
203 //Not one of our gates? Don't follow any further
204 if(!IsRightType(s
, gt
))
212 //Otherwise, continue down the chain
213 current_loads
= next_loads
;
218 //We have our list, go act on it
219 for(auto head_cell
: sinks
)
221 log(" Head cell is %s\n", head_cell
->name
.c_str());
223 //Avoid duplication if we already were covered
224 if(consumed_cells
.count(head_cell
))
227 pool
<Cell
*> cur_supercell
;
228 std::deque
<Cell
*> bfs_queue
= {head_cell
};
229 while (bfs_queue
.size())
231 Cell
* x
= bfs_queue
.front();
232 bfs_queue
.pop_front();
234 cur_supercell
.insert(x
);
236 auto a
= sigmap(x
->getPort("\\A"));
237 log_assert(a
.size() == 1);
239 // Must have only one sink unless we're going off chain
240 // XXX: Check that it is indeed this node?
241 if( allow_off_chain
|| (sig_to_sink
[a
[0]].size() + port_sigs
.count(a
[0]) == 1) )
243 Cell
* cell_a
= sig_to_driver
[a
[0]];
244 if(cell_a
&& IsRightType(cell_a
, gt
))
246 // The cell here is the correct type, and it's definitely driving
247 // this current cell.
248 bfs_queue
.push_back(cell_a
);
252 auto b
= sigmap(x
->getPort("\\B"));
253 log_assert(b
.size() == 1);
255 // Must have only one sink
256 // XXX: Check that it is indeed this node?
257 if( allow_off_chain
|| (sig_to_sink
[b
[0]].size() + port_sigs
.count(b
[0]) == 1) )
259 Cell
* cell_b
= sig_to_driver
[b
[0]];
260 if(cell_b
&& IsRightType(cell_b
, gt
))
262 // The cell here is the correct type, and it's definitely driving only
263 // this current cell.
264 bfs_queue
.push_back(cell_b
);
270 for (auto x
: cur_supercell
)
271 log(" %s\n", x
->name
.c_str());
273 if (cur_supercell
.size() > 1)
275 // Worth it to create reduce cell
276 log(" Creating $reduce_* cell!\n");
278 pool
<SigBit
> input_pool
;
279 pool
<SigBit
> input_pool_intermed
;
280 for (auto x
: cur_supercell
)
282 input_pool
.insert(sigmap(x
->getPort("\\A"))[0]);
283 input_pool
.insert(sigmap(x
->getPort("\\B"))[0]);
284 input_pool_intermed
.insert(sigmap(x
->getPort("\\Y"))[0]);
287 for (auto b
: input_pool
)
288 if (input_pool_intermed
.count(b
) == 0)
291 SigBit output
= sigmap(head_cell
->getPort("\\Y")[0]);
293 auto new_reduce_cell
= module
->addCell(NEW_ID
,
294 gt
== GateType::And
? "$reduce_and" :
295 gt
== GateType::Or
? "$reduce_or" :
296 gt
== GateType::Xor
? "$reduce_xor" : "");
297 new_reduce_cell
->setParam("\\A_SIGNED", 0);
298 new_reduce_cell
->setParam("\\A_WIDTH", input
.size());
299 new_reduce_cell
->setParam("\\Y_WIDTH", 1);
300 new_reduce_cell
->setPort("\\A", input
);
301 new_reduce_cell
->setPort("\\Y", output
);
304 consumed_cells
.insert(head_cell
);
307 for (auto x
: cur_supercell
)
308 consumed_cells
.insert(x
);
314 // Remove all of the head cells, since we supplant them.
315 // Do not remove the upstream cells since some might still be in use ("clean" will get rid of unused ones)
316 for (auto cell
: consumed_cells
)
317 module
->remove(cell
);
324 PRIVATE_NAMESPACE_END