Skip to content

Commit c8f35db

Browse files
azonenbergazonenberg
committedSep 11, 2017
Initial version of extract_bus pass
1 parent d405923 commit c8f35db

File tree

2 files changed

+423
-0
lines changed

2 files changed

+423
-0
lines changed
 

Diff for: ‎passes/techmap/Makefile.inc

+1
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@ OBJS += passes/techmap/hilomap.o
1818
OBJS += passes/techmap/extract.o
1919
OBJS += passes/techmap/extract_fa.o
2020
OBJS += passes/techmap/extract_counter.o
21+
OBJS += passes/techmap/extract_bus.o
2122
OBJS += passes/techmap/extract_reduce.o
2223
OBJS += passes/techmap/recover_adder.o
2324
$(eval $(call add_share_file,share/untechmap,passes/techmap/adder_untechmap.lib))

Diff for: ‎passes/techmap/extract_bus.cc

+422
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,422 @@
1+
/*
2+
* yosys -- Yosys Open SYnthesis Suite
3+
*
4+
* Copyright (C) 2017 Clifford Wolf <clifford@clifford.at>
5+
*
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.
9+
*
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.
17+
*
18+
*/
19+
20+
#include "kernel/yosys.h"
21+
#include "kernel/sigtools.h"
22+
#include "kernel/modtools.h"
23+
24+
USING_YOSYS_NAMESPACE
25+
PRIVATE_NAMESPACE_BEGIN
26+
27+
/*
28+
//get the list of cells hooked up to at least one bit of a given net
29+
pool<Cell*> get_other_cells(const RTLIL::SigSpec& port, ModIndex& index, Cell* src)
30+
{
31+
pool<Cell*> rval;
32+
for(auto b : port)
33+
{
34+
pool<ModIndex::PortInfo> ports = index.query_ports(b);
35+
for(auto x : ports)
36+
{
37+
if(x.cell == src)
38+
continue;
39+
rval.insert(x.cell);
40+
}
41+
}
42+
return rval;
43+
}
44+
45+
//return true if there is a full-width bus connection from cell a port ap to cell b port bp
46+
//if other_conns_allowed is false, then we require a strict point to point connection (no other links)
47+
bool is_full_bus(
48+
const RTLIL::SigSpec& sig,
49+
ModIndex& index,
50+
Cell* a,
51+
RTLIL::IdString ap,
52+
Cell* b,
53+
RTLIL::IdString bp,
54+
bool other_conns_allowed = false)
55+
{
56+
for(auto s : sig)
57+
{
58+
pool<ModIndex::PortInfo> ports = index.query_ports(s);
59+
bool found_a = false;
60+
bool found_b = false;
61+
for(auto x : ports)
62+
{
63+
if( (x.cell == a) && (x.port == ap) )
64+
found_a = true;
65+
else if( (x.cell == b) && (x.port == bp) )
66+
found_b = true;
67+
else if(!other_conns_allowed)
68+
return false;
69+
}
70+
71+
if( (!found_a) || (!found_b) )
72+
return false;
73+
}
74+
75+
return true;
76+
}
77+
78+
//return true if the signal connects to one port only (nothing on the other end)
79+
bool is_unconnected(const RTLIL::SigSpec& port, ModIndex& index)
80+
{
81+
for(auto b : port)
82+
{
83+
pool<ModIndex::PortInfo> ports = index.query_ports(b);
84+
if(ports.size() > 1)
85+
return false;
86+
}
87+
88+
return true;
89+
}
90+
91+
struct CounterExtraction
92+
{
93+
int width; //counter width
94+
RTLIL::Wire* rwire; //the register output
95+
bool has_reset; //true if we have a reset
96+
RTLIL::SigSpec rst; //reset pin
97+
int count_value; //value we count from
98+
RTLIL::SigSpec clk; //clock signal
99+
RTLIL::SigSpec outsig; //counter output signal
100+
RTLIL::Cell* count_mux; //counter mux
101+
RTLIL::Cell* count_reg; //counter register
102+
RTLIL::Cell* underflow_inv; //inverter reduction for output-underflow detect
103+
pool<ModIndex::PortInfo> pouts; //Ports that take a parallel output from us
104+
};
105+
*/
106+
/*
107+
//attempt to extract a counter centered on the given adder cell
108+
//For now we only support DOWN counters.
109+
//TODO: up/down support
110+
int bus_tryextract(
111+
ModIndex& index,
112+
Cell *cell,
113+
CounterExtraction& extract,
114+
pool<RTLIL::IdString>& parallel_cells,
115+
int maxwidth)
116+
{
117+
SigMap& sigmap = index.sigmap;
118+
119+
//A counter with less than 2 bits makes no sense
120+
//TODO: configurable min threshold
121+
int a_width = cell->getParam("\\A_WIDTH").as_int();
122+
extract.width = a_width;
123+
if( (a_width < 2) || (a_width > maxwidth) )
124+
return 1;
125+
126+
//Second input must be a single bit
127+
int b_width = cell->getParam("\\B_WIDTH").as_int();
128+
if(b_width != 1)
129+
return 2;
130+
131+
//Both inputs must be unsigned, so don't extract anything with a signed input
132+
bool a_sign = cell->getParam("\\A_SIGNED").as_bool();
133+
bool b_sign = cell->getParam("\\B_SIGNED").as_bool();
134+
if(a_sign || b_sign)
135+
return 3;
136+
137+
//To be a counter, one input of the ALU must be a constant 1
138+
//TODO: can A or B be swapped in synthesized RTL or is B always the 1?
139+
const RTLIL::SigSpec b_port = sigmap(cell->getPort("\\B"));
140+
if(!b_port.is_fully_const() || (b_port.as_int() != 1) )
141+
return 4;
142+
143+
//BI and CI must be constant 1 as well
144+
const RTLIL::SigSpec bi_port = sigmap(cell->getPort("\\BI"));
145+
if(!bi_port.is_fully_const() || (bi_port.as_int() != 1) )
146+
return 5;
147+
const RTLIL::SigSpec ci_port = sigmap(cell->getPort("\\CI"));
148+
if(!ci_port.is_fully_const() || (ci_port.as_int() != 1) )
149+
return 6;
150+
151+
//CO and X must be unconnected (exactly one connection to each port)
152+
if(!is_unconnected(sigmap(cell->getPort("\\CO")), index))
153+
return 7;
154+
if(!is_unconnected(sigmap(cell->getPort("\\X")), index))
155+
return 8;
156+
157+
//Y must have exactly one connection, and it has to be a $mux cell.
158+
//We must have a direct bus connection from our Y to their A.
159+
const RTLIL::SigSpec aluy = sigmap(cell->getPort("\\Y"));
160+
pool<Cell*> y_loads = get_other_cells(aluy, index, cell);
161+
if(y_loads.size() != 1)
162+
return 9;
163+
Cell* count_mux = *y_loads.begin();
164+
extract.count_mux = count_mux;
165+
if(count_mux->type != "$mux")
166+
return 10;
167+
if(!is_full_bus(aluy, index, cell, "\\Y", count_mux, "\\A"))
168+
return 11;
169+
170+
//B connection of the mux is our underflow value
171+
const RTLIL::SigSpec underflow = sigmap(count_mux->getPort("\\B"));
172+
if(!underflow.is_fully_const())
173+
return 12;
174+
extract.count_value = underflow.as_int();
175+
176+
//S connection of the mux must come from an inverter (need not be the only load)
177+
const RTLIL::SigSpec muxsel = sigmap(count_mux->getPort("\\S"));
178+
extract.outsig = muxsel;
179+
pool<Cell*> muxsel_conns = get_other_cells(muxsel, index, count_mux);
180+
Cell* underflow_inv = NULL;
181+
for(auto c : muxsel_conns)
182+
{
183+
if(c->type != "$logic_not")
184+
continue;
185+
if(!is_full_bus(muxsel, index, c, "\\Y", count_mux, "\\S", true))
186+
continue;
187+
188+
underflow_inv = c;
189+
break;
190+
}
191+
if(underflow_inv == NULL)
192+
return 13;
193+
extract.underflow_inv = underflow_inv;
194+
195+
//Y connection of the mux must have exactly one load, the counter's internal register
196+
const RTLIL::SigSpec muxy = sigmap(count_mux->getPort("\\Y"));
197+
pool<Cell*> muxy_loads = get_other_cells(muxy, index, count_mux);
198+
if(muxy_loads.size() != 1)
199+
return 14;
200+
Cell* count_reg = *muxy_loads.begin();
201+
extract.count_reg = count_reg;
202+
if(count_reg->type == "$dff")
203+
extract.has_reset = false;
204+
else if(count_reg->type == "$adff")
205+
{
206+
extract.has_reset = true;
207+
208+
//Verify ARST_VALUE is zero and ARST_POLARITY is 1
209+
//TODO: infer an inverter to make it 1 if necessary, so we can support negative level resets?
210+
if(count_reg->getParam("\\ARST_POLARITY").as_int() != 1)
211+
return 22;
212+
if(count_reg->getParam("\\ARST_VALUE").as_int() != 0)
213+
return 23;
214+
215+
//Save the reset
216+
extract.rst = sigmap(count_reg->getPort("\\ARST"));
217+
}
218+
//TODO: support synchronous reset
219+
else
220+
return 15;
221+
if(!is_full_bus(muxy, index, count_mux, "\\Y", count_reg, "\\D"))
222+
return 16;
223+
224+
//TODO: Verify count_reg CLK_POLARITY is 1
225+
226+
//Register output must have exactly two loads, the inverter and ALU
227+
//(unless we have a parallel output!)
228+
const RTLIL::SigSpec qport = count_reg->getPort("\\Q");
229+
const RTLIL::SigSpec cnout = sigmap(qport);
230+
pool<Cell*> cnout_loads = get_other_cells(cnout, index, count_reg);
231+
if(cnout_loads.size() > 2)
232+
{
233+
//If we specified a limited set of cells for parallel output, check that we only drive them
234+
if(!parallel_cells.empty())
235+
{
236+
for(auto c : cnout_loads)
237+
{
238+
if(c == underflow_inv)
239+
continue;
240+
if(c == cell)
241+
continue;
242+
243+
//Make sure we're in the whitelist
244+
if( parallel_cells.find(c->type) == parallel_cells.end())
245+
return 17;
246+
247+
//Figure out what port(s) are driven by it
248+
//TODO: this can probably be done more efficiently w/o multiple iterations over our whole net?
249+
RTLIL::IdString portname;
250+
for(auto b : qport)
251+
{
252+
pool<ModIndex::PortInfo> ports = index.query_ports(b);
253+
for(auto x : ports)
254+
{
255+
if(x.cell != c)
256+
continue;
257+
if(portname == "")
258+
portname = x.port;
259+
260+
//somehow our counter output is going to multiple ports
261+
//this makes no sense, don't allow inference
262+
else if(portname != x.port)
263+
return 17;
264+
}
265+
}
266+
267+
//Save the other loads
268+
extract.pouts.insert(ModIndex::PortInfo(c, portname, 0));
269+
}
270+
}
271+
}
272+
if(!is_full_bus(cnout, index, count_reg, "\\Q", underflow_inv, "\\A", true))
273+
return 18;
274+
if(!is_full_bus(cnout, index, count_reg, "\\Q", cell, "\\A", true))
275+
return 19;
276+
277+
//Look up the clock from the register
278+
extract.clk = sigmap(count_reg->getPort("\\CLK"));
279+
280+
//Register output net must have an INIT attribute equal to the count value
281+
extract.rwire = cnout.as_wire();
282+
if(extract.rwire->attributes.find("\\init") == extract.rwire->attributes.end())
283+
return 20;
284+
int rinit = extract.rwire->attributes["\\init"].as_int();
285+
if(rinit != extract.count_value)
286+
return 21;
287+
288+
return 0;
289+
}
290+
*/
291+
292+
void bus_worker(
293+
ModIndex& index,
294+
Cell *cell,
295+
unsigned int& total_buses)
296+
{
297+
SigMap& sigmap = index.sigmap;
298+
299+
/*
300+
Table of ports on each cell that are guaranteed to be a bus.
301+
302+
Note that with commutative operations such as addition, we cannot make the inputs buses
303+
because we don't know which bits belong to which input.
304+
We also cannot infer a bus from
305+
*/
306+
//TODO: better way to store this table
307+
std::set<RTLIL::IdString> busports;
308+
if(cell->type == "$add")
309+
busports.emplace("\\Y");
310+
else if(cell->type == "$__COUNT_")
311+
busports.emplace("\\POUT");
312+
313+
//Unknown cell, bus ports not supported
314+
else
315+
return;
316+
317+
//Bus-ify each port
318+
log("Inferring buses for port(s) of %s\n", log_id(cell->name));
319+
for(auto p : busports)
320+
{
321+
//See what's on the port now
322+
//If it's a wire, stop - no action needed
323+
//If there's nothing on the port, skip it as well!
324+
if(!cell->hasPort(p))
325+
{
326+
//log(" Cell does not have a port named %s\n", p.c_str());
327+
continue;
328+
}
329+
auto port = sigmap(cell->getPort(p));
330+
if(port.is_wire())
331+
{
332+
//log(" Port %s is already a wire\n", p.c_str());
333+
continue;
334+
}
335+
336+
//Not a wire, create one!
337+
auto wire = cell->module->addWire(NEW_ID, port.size());
338+
339+
//Find downstream entities connected to the old wire and reconnect them
340+
log(" Inferring bus for port %s\n", p.c_str());
341+
for(int i=0; i<port.size(); i++)
342+
{
343+
auto b = port[i];
344+
pool<ModIndex::PortInfo> ports = index.query_ports(b);
345+
346+
log(" Finding additional loads for bit %d / signal %s (found %zu)\n",
347+
i, log_id(b.wire->name), ports.size());
348+
for(auto x : ports)
349+
{
350+
if(x.cell == cell)
351+
continue;
352+
log(" Cell %s port %s is connected to us at offset %d\n",
353+
log_id(x.cell->name), log_id(x.port), x.offset);
354+
355+
//Patch the sigspec one bit at a time as needed
356+
auto dspec = x.cell->getPort(x.port);
357+
dspec[x.offset] = RTLIL::SigBit(wire, i);
358+
x.cell->setPort(x.port, dspec);
359+
}
360+
361+
//See if this signal is a top-level module port
362+
//If so, add buffers to preserve the existing signal names
363+
//TODO: how to handle top level vector ports?
364+
bool found = false;
365+
for(auto p : cell->module->ports)
366+
{
367+
if(p == b.wire->name)
368+
found = true;
369+
}
370+
371+
if(found)
372+
{
373+
log(" Cell %s port %s drives top level module port %s\n",
374+
log_id(cell->name), p.c_str(), log_id(b.wire->name));
375+
376+
cell->module->addBufGate(NEW_ID, RTLIL::SigSpec(wire, i, 1), b.wire);
377+
}
378+
}
379+
380+
//Hook up the new wire
381+
cell->setPort(p, wire);
382+
383+
//We made a match, note it
384+
total_buses ++;
385+
}
386+
}
387+
388+
struct ExtractBusPass : public Pass {
389+
ExtractBusPass() : Pass("extract_bus", "Extract buses from split nets") { }
390+
virtual void help()
391+
{
392+
// |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
393+
log("\n");
394+
log(" extract_bus [selection]\n");
395+
log("\n");
396+
log("This pass finds buses in a design consisting of single-bit nets\n");
397+
log("\n");
398+
}
399+
virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
400+
{
401+
log_header(design, "Executing EXTRACT_BUS pass (find buses in netlist).\n");
402+
403+
//int argidx = 0;
404+
//extra_args(args, argidx, design);
405+
406+
//Extract all of the buses we could find
407+
unsigned int total_buses = 0;
408+
for (auto module : design->selected_modules())
409+
{
410+
ModIndex index(module);
411+
for (auto cell : module->selected_cells())
412+
bus_worker(index, cell, total_buses);
413+
}
414+
415+
//TODO: Recurse and find additional buses by elimination
416+
417+
if(total_buses)
418+
log("Extracted %u buses\n", total_buses);
419+
}
420+
} ExtractBusPass;
421+
422+
PRIVATE_NAMESPACE_END

0 commit comments

Comments
 (0)
Please sign in to comment.