1 /* 2 * yosys -- Yosys Open SYnthesis Suite 3 * 4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at> 5 * (C) 2019 Eddie Hung <eddie@fpgeh.com> 6 * 7 * Permission to use, copy, modify, and/or distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18 * 19 */ 20 21 #include "kernel/yosys.h" 22 #include "kernel/sigtools.h" 23 #include "kernel/timinginfo.h" 24 #include <deque> 25 26 USING_YOSYS_NAMESPACE 27 PRIVATE_NAMESPACE_BEGIN 28 29 struct StaWorker 30 { 31 Design *design; 32 Module *module; 33 SigMap sigmap; 34 35 struct t_data { 36 Cell* driver; 37 IdString dst_port, src_port; 38 vector<tuple<SigBit,int,IdString>> fanouts; 39 SigBit backtrack; t_dataStaWorker::t_data40 t_data() : driver(nullptr) {} 41 }; 42 dict<SigBit, t_data> data; 43 std::deque<SigBit> queue; 44 struct t_endpoint { 45 Cell *sink; 46 IdString port; 47 int required; t_endpointStaWorker::t_endpoint48 t_endpoint() : sink(nullptr), required(0) {} 49 }; 50 dict<SigBit, t_endpoint> endpoints; 51 52 int maxarrival; 53 SigBit maxbit; 54 55 pool<SigBit> driven; 56 StaWorkerStaWorker57 StaWorker(RTLIL::Module *module) : design(module->design), module(module), sigmap(module), maxarrival(0) 58 { 59 TimingInfo timing; 60 61 for (auto cell : module->cells()) 62 { 63 Module *inst_module = design->module(cell->type); 64 if (!inst_module) { 65 log_warning("Cell type '%s' not recognised! Ignoring.\n", log_id(cell->type)); 66 continue; 67 } 68 69 if (!inst_module->get_blackbox_attribute()) { 70 log_warning("Cell type '%s' is not a black- nor white-box! Ignoring.\n", log_id(cell->type)); 71 continue; 72 } 73 74 IdString derived_type = inst_module->derive(design, cell->parameters); 75 inst_module = design->module(derived_type); 76 log_assert(inst_module); 77 78 if (!timing.count(derived_type)) { 79 auto &t = timing.setup_module(inst_module); 80 if (t.has_inputs && t.comb.empty() && t.arrival.empty() && t.required.empty()) 81 log_warning("Module '%s' has no timing arcs!\n", log_id(cell->type)); 82 } 83 84 auto &t = timing.at(derived_type); 85 if (t.comb.empty() && t.arrival.empty() && t.required.empty()) 86 continue; 87 88 pool<std::pair<SigBit,TimingInfo::NameBit>> src_bits, dst_bits; 89 90 for (auto &conn : cell->connections()) { 91 auto rhs = sigmap(conn.second); 92 for (auto i = 0; i < GetSize(rhs); i++) { 93 const auto &bit = rhs[i]; 94 if (!bit.wire) 95 continue; 96 TimingInfo::NameBit namebit(conn.first,i); 97 if (cell->input(conn.first)) { 98 src_bits.insert(std::make_pair(bit,namebit)); 99 100 auto it = t.required.find(namebit); 101 if (it == t.required.end()) 102 continue; 103 auto r = endpoints.insert(bit); 104 if (r.second || r.first->second.required < it->second.first) { 105 r.first->second.sink = cell; 106 r.first->second.port = conn.first; 107 r.first->second.required = it->second.first; 108 } 109 } 110 if (cell->output(conn.first)) { 111 dst_bits.insert(std::make_pair(bit,namebit)); 112 auto &d = data[bit]; 113 d.driver = cell; 114 d.dst_port = conn.first; 115 driven.insert(bit); 116 117 auto it = t.arrival.find(namebit); 118 if (it == t.arrival.end()) 119 continue; 120 const auto &s = it->second.second; 121 if (cell->hasPort(s.name)) { 122 auto s_bit = sigmap(cell->getPort(s.name)[s.offset]); 123 if (s_bit.wire) 124 data[s_bit].fanouts.emplace_back(bit,it->second.first,s.name); 125 } 126 } 127 } 128 } 129 130 for (const auto &s : src_bits) 131 for (const auto &d : dst_bits) { 132 auto it = t.comb.find(TimingInfo::BitBit(s.second,d.second)); 133 if (it == t.comb.end()) 134 continue; 135 data[s.first].fanouts.emplace_back(d.first,it->second,s.second.name); 136 } 137 } 138 139 for (auto port_name : module->ports) { 140 auto wire = module->wire(port_name); 141 if (wire->port_input) { 142 for (const auto &b : sigmap(wire)) { 143 queue.emplace_back(b); 144 driven.insert(b); 145 } 146 // All primary inputs to arrive at time zero 147 wire->set_intvec_attribute(ID::sta_arrival, std::vector<int>(GetSize(wire), 0)); 148 } 149 if (wire->port_output) 150 for (const auto &b : sigmap(wire)) 151 if (b.wire) 152 endpoints.insert(b); 153 } 154 } 155 runStaWorker156 void run() 157 { 158 while (!queue.empty()) { 159 auto b = queue.front(); 160 queue.pop_front(); 161 auto it = data.find(b); 162 if (it == data.end()) 163 continue; 164 const auto& src_arrivals = b.wire->get_intvec_attribute(ID::sta_arrival); 165 log_assert(GetSize(src_arrivals) == GetSize(b.wire)); 166 auto src_arrival = src_arrivals[b.offset]; 167 for (const auto &d : it->second.fanouts) { 168 const auto &dst_bit = std::get<0>(d); 169 auto dst_arrivals = dst_bit.wire->get_intvec_attribute(ID::sta_arrival); 170 if (dst_arrivals.empty()) 171 dst_arrivals = std::vector<int>(GetSize(dst_bit.wire), -1); 172 else 173 log_assert(GetSize(dst_arrivals) == GetSize(dst_bit.wire)); 174 auto &dst_arrival = dst_arrivals[dst_bit.offset]; 175 auto new_arrival = src_arrival + std::get<1>(d); 176 if (dst_arrival < new_arrival) { 177 auto dst_wire = dst_bit.wire; 178 dst_arrival = std::max(dst_arrival, new_arrival); 179 dst_wire->set_intvec_attribute(ID::sta_arrival, dst_arrivals); 180 queue.emplace_back(dst_bit); 181 182 data[dst_bit].backtrack = b; 183 data[dst_bit].src_port = std::get<2>(d); 184 185 auto it = endpoints.find(dst_bit); 186 if (it != endpoints.end()) 187 new_arrival += it->second.required; 188 if (new_arrival > maxarrival && driven.count(b)) { 189 maxarrival = new_arrival; 190 maxbit = dst_bit; 191 } 192 } 193 } 194 } 195 196 auto b = maxbit; 197 if (b == SigBit()) { 198 log("No timing paths found.\n"); 199 return; 200 } 201 202 log("Latest arrival time in '%s' is %d:\n", log_id(module), maxarrival); 203 auto it = endpoints.find(maxbit); 204 if (it != endpoints.end() && it->second.sink) 205 log(" %6d %s (%s.%s)\n", maxarrival, log_id(it->second.sink), log_id(it->second.sink->type), log_id(it->second.port)); 206 else { 207 log(" %6d (%s)\n", maxarrival, b.wire->port_output ? "<primary output>" : "<unknown>"); 208 if (!b.wire->port_output) 209 log_warning("Critical-path does not terminate in a recognised endpoint.\n"); 210 } 211 auto jt = data.find(b); 212 while (jt != data.end()) { 213 int arrival = b.wire->get_intvec_attribute(ID::sta_arrival)[b.offset]; 214 if (jt->second.driver) { 215 log(" %s\n", log_signal(b)); 216 log(" %6d %s (%s.%s->%s)\n", arrival, log_id(jt->second.driver), log_id(jt->second.driver->type), log_id(jt->second.src_port), log_id(jt->second.dst_port)); 217 } 218 else if (b.wire->port_input) 219 log(" %6d %s (%s)\n", arrival, log_signal(b), "<primary input>"); 220 else 221 log_abort(); 222 b = jt->second.backtrack; 223 jt = data.find(b); 224 } 225 226 std::map<int, unsigned> arrival_histogram; 227 for (const auto &i : endpoints) { 228 const auto &b = i.first; 229 if (!driven.count(b)) 230 continue; 231 232 if (!b.wire->attributes.count(ID::sta_arrival)) { 233 log_warning("Endpoint %s.%s has no (* sta_arrival *) value.\n", log_id(module), log_signal(b)); 234 continue; 235 } 236 237 auto arrival = b.wire->get_intvec_attribute(ID::sta_arrival)[b.offset]; 238 if (arrival < 0) { 239 log_warning("Endpoint %s.%s has no (* sta_arrival *) value.\n", log_id(module), log_signal(b)); 240 continue; 241 } 242 arrival += i.second.required; 243 arrival_histogram[arrival]++; 244 } 245 // Adapted from https://github.com/YosysHQ/nextpnr/blob/affb12cc27ebf409eade062c4c59bb98569d8147/common/timing.cc#L946-L969 246 if (arrival_histogram.size() > 0) { 247 unsigned num_bins = 20; 248 unsigned bar_width = 60; 249 auto min_arrival = arrival_histogram.begin()->first; 250 auto max_arrival = arrival_histogram.rbegin()->first; 251 auto bin_size = std::max<unsigned>(1, ceil((max_arrival - min_arrival + 1) / float(num_bins))); 252 std::vector<unsigned> bins(num_bins); 253 unsigned max_freq = 0; 254 for (const auto &i : arrival_histogram) { 255 auto &bin = bins[(i.first - min_arrival) / bin_size]; 256 bin += i.second; 257 max_freq = std::max(max_freq, bin); 258 } 259 bar_width = std::min(bar_width, max_freq); 260 261 log("\n"); 262 log("Arrival histogram:\n"); 263 log(" legend: * represents %d endpoint(s)\n", max_freq / bar_width); 264 log(" + represents [1,%d) endpoint(s)\n", max_freq / bar_width); 265 for (int i = num_bins-1; i >= 0; --i) 266 log("(%6d, %6d] |%s%c\n", min_arrival + bin_size * (i + 1), min_arrival + bin_size * i, 267 std::string(bins[i] * bar_width / max_freq, '*').c_str(), 268 (bins[i] * bar_width) % max_freq > 0 ? '+' : ' '); 269 } 270 } 271 }; 272 273 struct StaPass : public Pass { StaPassStaPass274 StaPass() : Pass("sta", "perform static timing analysis") { } helpStaPass275 void help() override 276 { 277 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| 278 log("\n"); 279 log(" sta [options] [selection]\n"); 280 log("\n"); 281 log("This command performs static timing analysis on the design. (Only considers\n"); 282 log("paths within a single module, so the design must be flattened.)\n"); 283 log("\n"); 284 } executeStaPass285 void execute(std::vector<std::string> args, RTLIL::Design *design) override 286 { 287 log_header(design, "Executing STA pass (static timing analysis).\n"); 288 289 /* 290 size_t argidx; 291 for (argidx = 1; argidx < args.size(); argidx++) { 292 if (args[argidx] == "-TODO") { 293 continue; 294 } 295 break; 296 } 297 */ 298 299 extra_args(args, 1, design); 300 301 for (Module *module : design->selected_modules()) 302 { 303 if (module->has_processes_warn()) 304 continue; 305 306 StaWorker worker(module); 307 worker.run(); 308 } 309 } 310 } StaPass; 311 312 PRIVATE_NAMESPACE_END 313