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 // [[CITE]] Tarjan's strongly connected components algorithm
21 // Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146-160, doi:10.1137/0201010
22 // http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm
24 #include "kernel/register.h"
25 #include "kernel/celltypes.h"
26 #include "kernel/sigtools.h"
27 #include "kernel/log.h"
33 PRIVATE_NAMESPACE_BEGIN
37 RTLIL::Design
*design
;
38 RTLIL::Module
*module
;
42 std::set
<RTLIL::Cell
*> workQueue
;
43 std::map
<RTLIL::Cell
*, std::set
<RTLIL::Cell
*>> cellToNextCell
;
44 std::map
<RTLIL::Cell
*, RTLIL::SigSpec
> cellToPrevSig
, cellToNextSig
;
46 std::map
<RTLIL::Cell
*, std::pair
<int, int>> cellLabels
;
47 std::map
<RTLIL::Cell
*, int> cellDepth
;
48 std::set
<RTLIL::Cell
*> cellsOnStack
;
49 std::vector
<RTLIL::Cell
*> cellStack
;
52 std::map
<RTLIL::Cell
*, int> cell2scc
;
53 std::vector
<std::set
<RTLIL::Cell
*>> sccList
;
55 void run(RTLIL::Cell
*cell
, int depth
, int maxDepth
)
57 log_assert(workQueue
.count(cell
) > 0);
59 workQueue
.erase(cell
);
60 cellLabels
[cell
] = std::pair
<int, int>(labelCounter
, labelCounter
);
63 cellsOnStack
.insert(cell
);
64 cellStack
.push_back(cell
);
67 cellDepth
[cell
] = depth
;
69 for (auto nextCell
: cellToNextCell
[cell
])
70 if (cellLabels
.count(nextCell
) == 0) {
71 run(nextCell
, depth
+1, maxDepth
);
72 cellLabels
[cell
].second
= min(cellLabels
[cell
].second
, cellLabels
[nextCell
].second
);
74 if (cellsOnStack
.count(nextCell
) > 0 && (maxDepth
< 0 || cellDepth
[nextCell
] + maxDepth
> depth
)) {
75 cellLabels
[cell
].second
= min(cellLabels
[cell
].second
, cellLabels
[nextCell
].second
);
78 if (cellLabels
[cell
].first
== cellLabels
[cell
].second
)
80 if (cellStack
.back() == cell
)
83 cellsOnStack
.erase(cell
);
88 std::set
<RTLIL::Cell
*> scc
;
89 while (cellsOnStack
.count(cell
) > 0) {
90 RTLIL::Cell
*c
= cellStack
.back();
92 cellsOnStack
.erase(c
);
93 log(" %s", RTLIL::id2cstr(c
->name
));
94 cell2scc
[c
] = sccList
.size();
97 sccList
.push_back(scc
);
103 SccWorker(RTLIL::Design
*design
, RTLIL::Module
*module
, bool nofeedbackMode
, bool allCellTypes
, int maxDepth
) :
104 design(design
), module(module
), sigmap(module
)
106 if (module
->processes
.size() > 0) {
107 log("Skipping module %s as it contains processes (run 'proc' pass first).\n", module
->name
.c_str());
114 ct
.setup_internals();
118 SigPool selectedSignals
;
119 SigSet
<RTLIL::Cell
*> sigToNextCells
;
121 for (auto &it
: module
->wires_
)
122 if (design
->selected(module
, it
.second
))
123 selectedSignals
.add(sigmap(RTLIL::SigSpec(it
.second
)));
125 for (auto &it
: module
->cells_
)
127 RTLIL::Cell
*cell
= it
.second
;
129 if (!design
->selected(module
, cell
))
132 if (!allCellTypes
&& !ct
.cell_known(cell
->type
))
135 workQueue
.insert(cell
);
137 RTLIL::SigSpec inputSignals
, outputSignals
;
139 for (auto &conn
: cell
->connections())
141 bool isInput
= true, isOutput
= true;
143 if (ct
.cell_known(cell
->type
)) {
144 isInput
= ct
.cell_input(cell
->type
, conn
.first
);
145 isOutput
= ct
.cell_output(cell
->type
, conn
.first
);
148 RTLIL::SigSpec sig
= selectedSignals
.extract(sigmap(conn
.second
));
149 sig
.sort_and_unify();
152 inputSignals
.append(sig
);
154 outputSignals
.append(sig
);
157 inputSignals
.sort_and_unify();
158 outputSignals
.sort_and_unify();
160 cellToPrevSig
[cell
] = inputSignals
;
161 cellToNextSig
[cell
] = outputSignals
;
162 sigToNextCells
.insert(inputSignals
, cell
);
165 for (auto cell
: workQueue
)
167 cellToNextCell
[cell
] = sigToNextCells
.find(cellToNextSig
[cell
]);
169 if (!nofeedbackMode
&& cellToNextCell
[cell
].count(cell
)) {
170 log("Found an SCC:");
171 std::set
<RTLIL::Cell
*> scc
;
172 log(" %s", RTLIL::id2cstr(cell
->name
));
173 cell2scc
[cell
] = sccList
.size();
175 sccList
.push_back(scc
);
183 while (!workQueue
.empty())
185 RTLIL::Cell
*cell
= *workQueue
.begin();
186 log_assert(cellStack
.size() == 0);
189 run(cell
, 0, maxDepth
);
192 log("Found %d SCCs in module %s.\n", int(sccList
.size()), RTLIL::id2cstr(module
->name
));
195 void select(RTLIL::Selection
&sel
)
197 for (int i
= 0; i
< int(sccList
.size()); i
++)
199 std::set
<RTLIL::Cell
*> &cells
= sccList
[i
];
200 RTLIL::SigSpec prevsig
, nextsig
, sig
;
202 for (auto cell
: cells
) {
203 sel
.selected_members
[module
->name
].insert(cell
->name
);
204 prevsig
.append(cellToPrevSig
[cell
]);
205 nextsig
.append(cellToNextSig
[cell
]);
208 prevsig
.sort_and_unify();
209 nextsig
.sort_and_unify();
210 sig
= prevsig
.extract(nextsig
);
212 for (auto &chunk
: sig
.chunks())
213 if (chunk
.wire
!= NULL
)
214 sel
.selected_members
[module
->name
].insert(chunk
.wire
->name
);
219 struct SccPass
: public Pass
{
220 SccPass() : Pass("scc", "detect strongly connected components (logic loops)") { }
221 void help() YS_OVERRIDE
223 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
225 log(" scc [options] [selection]\n");
227 log("This command identifies strongly connected components (aka logic loops) in the\n");
230 log(" -expect <num>\n");
231 log(" expect to find exactly <num> SSCs. A different number of SSCs will\n");
232 log(" produce an error.\n");
234 log(" -max_depth <num>\n");
235 log(" limit to loops not longer than the specified number of cells. This\n");
236 log(" can e.g. be useful in identifying small local loops in a module that\n");
237 log(" implements one large SCC.\n");
239 log(" -nofeedback\n");
240 log(" do not count cells that have their output fed back into one of their\n");
241 log(" inputs as single-cell scc.\n");
243 log(" -all_cell_types\n");
244 log(" Usually this command only considers internal non-memory cells. With\n");
245 log(" this option set, all cells are considered. For unknown cells all ports\n");
246 log(" are assumed to be bidirectional 'inout' ports.\n");
248 log(" -set_attr <name> <value>\n");
249 log(" set the specified attribute on all cells that are part of a logic\n");
250 log(" loop. the special token {} in the value is replaced with a unique\n");
251 log(" identifier for the logic loop.\n");
254 log(" replace the current selection with a selection of all cells and wires\n");
255 log(" that are part of a found logic loop\n");
258 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
260 std::map
<std::string
, std::string
> setAttr
;
261 bool allCellTypes
= false;
262 bool selectMode
= false;
263 bool nofeedbackMode
= false;
267 log_header(design
, "Executing SCC pass (detecting logic loops).\n");
270 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
271 if (args
[argidx
] == "-max_depth" && argidx
+1 < args
.size()) {
272 maxDepth
= atoi(args
[++argidx
].c_str());
275 if (args
[argidx
] == "-expect" && argidx
+1 < args
.size()) {
276 expect
= atoi(args
[++argidx
].c_str());
279 if (args
[argidx
] == "-nofeedback") {
280 nofeedbackMode
= true;
283 if (args
[argidx
] == "-all_cell_types") {
287 if (args
[argidx
] == "-set_attr" && argidx
+2 < args
.size()) {
288 setAttr
[args
[argidx
+1]] = args
[argidx
+2];
292 if (args
[argidx
] == "-select") {
298 int origSelectPos
= design
->selection_stack
.size() - 1;
299 extra_args(args
, argidx
, design
);
301 RTLIL::Selection
newSelection(false);
304 for (auto &mod_it
: design
->modules_
)
305 if (design
->selected(mod_it
.second
))
307 SccWorker
worker(design
, mod_it
.second
, nofeedbackMode
, allCellTypes
, maxDepth
);
309 if (!setAttr
.empty())
311 for (const auto &cells
: worker
.sccList
)
313 for (auto attr
: setAttr
)
315 IdString
attr_name(RTLIL::escape_id(attr
.first
));
316 string attr_valstr
= attr
.second
;
317 string index
= stringf("%d", scc_counter
);
319 for (size_t pos
= 0; (pos
= attr_valstr
.find("{}", pos
)) != string::npos
; pos
+= index
.size())
320 attr_valstr
.replace(pos
, 2, index
);
322 Const
attr_value(attr_valstr
);
324 for (auto cell
: cells
)
325 cell
->attributes
[attr_name
] = attr_value
;
333 scc_counter
+= GetSize(worker
.sccList
);
337 worker
.select(newSelection
);
341 if (scc_counter
== expect
)
342 log("Found and expected %d SCCs.\n", scc_counter
);
344 log_error("Found %d SCCs but expected %d.\n", scc_counter
, expect
);
346 log("Found %d SCCs.\n", scc_counter
);
349 log_assert(origSelectPos
>= 0);
350 design
->selection_stack
[origSelectPos
] = newSelection
;
351 design
->selection_stack
[origSelectPos
].optimize(design
);
356 PRIVATE_NAMESPACE_END