1 /*
2  *  yosys -- Yosys Open SYnthesis Suite
3  *
4  *  Copyright (C) 2012  Claire Xenia Wolf <claire@yosyshq.com>
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/celltypes.h"
22 #include "kernel/sigtools.h"
23 #include "kernel/utils.h"
24 
25 USING_YOSYS_NAMESPACE
26 PRIVATE_NAMESPACE_BEGIN
27 
28 struct TorderPass : public Pass {
TorderPassTorderPass29 	TorderPass() : Pass("torder", "print cells in topological order") { }
helpTorderPass30 	void help() override
31 	{
32 		//   |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
33 		log("\n");
34 		log("    torder [options] [selection]\n");
35 		log("\n");
36 		log("This command prints the selected cells in topological order.\n");
37 		log("\n");
38 		log("    -stop <cell_type> <cell_port>\n");
39 		log("        do not use the specified cell port in topological sorting\n");
40 		log("\n");
41 		log("    -noautostop\n");
42 		log("        by default Q outputs of internal FF cells and memory read port outputs\n");
43 		log("        are not used in topological sorting. this option deactivates that.\n");
44 		log("\n");
45 	}
executeTorderPass46 	void execute(std::vector<std::string> args, RTLIL::Design *design) override
47 	{
48 		bool noautostop = false;
49 		dict<IdString, pool<IdString>> stop_db;
50 
51 		log_header(design, "Executing TORDER pass (print cells in topological order).\n");
52 
53 		size_t argidx;
54 		for (argidx = 1; argidx < args.size(); argidx++) {
55 			if (args[argidx] == "-stop" && argidx+2 < args.size()) {
56 				IdString cell_type = RTLIL::escape_id(args[++argidx]);
57 				IdString cell_port = RTLIL::escape_id(args[++argidx]);
58 				stop_db[cell_type].insert(cell_port);
59 				continue;
60 			}
61 			if (args[argidx] == "-noautostop") {
62 				noautostop = true;
63 				continue;
64 			}
65 			break;
66 		}
67 		extra_args(args, argidx, design);
68 
69 		for (auto module : design->selected_modules())
70 		{
71 			log("module %s\n", log_id(module));
72 
73 			SigMap sigmap(module);
74 			dict<SigBit, pool<IdString>> bit_drivers, bit_users;
75 			TopoSort<IdString, RTLIL::sort_by_id_str> toposort;
76 
77 			for (auto cell : module->selected_cells())
78 			for (auto conn : cell->connections())
79 			{
80 				if (stop_db.count(cell->type) && stop_db.at(cell->type).count(conn.first))
81 					continue;
82 
83 				if (!noautostop && yosys_celltypes.cell_known(cell->type)) {
84 					if (conn.first.in(ID::Q, ID::CTRL_OUT, ID::RD_DATA))
85 						continue;
86 					if (cell->type.in(ID($memrd), ID($memrd_v2)) && conn.first == ID::DATA)
87 						continue;
88 				}
89 
90 				if (cell->input(conn.first))
91 					for (auto bit : sigmap(conn.second))
92 						bit_users[bit].insert(cell->name);
93 
94 				if (cell->output(conn.first))
95 					for (auto bit : sigmap(conn.second))
96 						bit_drivers[bit].insert(cell->name);
97 
98 				toposort.node(cell->name);
99 			}
100 
101 			for (auto &it : bit_users)
102 				if (bit_drivers.count(it.first))
103 					for (auto driver_cell : bit_drivers.at(it.first))
104 					for (auto user_cell : it.second)
105 						toposort.edge(driver_cell, user_cell);
106 
107 			toposort.analyze_loops = true;
108 			toposort.sort();
109 
110 			for (auto &it : toposort.loops) {
111 				log("  loop");
112 				for (auto cell : it)
113 					log(" %s", log_id(cell));
114 				log("\n");
115 			}
116 
117 			for (auto cell : toposort.sorted)
118 					log("  cell %s\n", log_id(cell));
119 		}
120 	}
121 } TorderPass;
122 
123 PRIVATE_NAMESPACE_END
124