From 77327b2544a30b15e8efc79e1f62661ff25d306c Mon Sep 17 00:00:00 2001 From: Lofty Date: Wed, 24 Nov 2021 21:21:08 +0000 Subject: [PATCH] sta: very crude static timing analysis pass Co-authored-by: Eddie Hung --- backends/aiger/xaiger.cc | 31 ++-- kernel/constids.inc | 1 + kernel/rtlil.cc | 29 ++++ kernel/rtlil.h | 3 + kernel/timinginfo.h | 48 ++++-- passes/cmds/Makefile.inc | 1 + passes/cmds/sta.cc | 312 +++++++++++++++++++++++++++++++++++++ passes/techmap/abc9_ops.cc | 58 ++++--- tests/various/sta.ys | 81 ++++++++++ 9 files changed, 502 insertions(+), 62 deletions(-) create mode 100644 passes/cmds/sta.cc create mode 100644 tests/various/sta.ys diff --git a/backends/aiger/xaiger.cc b/backends/aiger/xaiger.cc index 66955d88e..e223f185e 100644 --- a/backends/aiger/xaiger.cc +++ b/backends/aiger/xaiger.cc @@ -261,26 +261,27 @@ struct XAigerWriter if (!timing.count(inst_module->name)) timing.setup_module(inst_module); - auto &t = timing.at(inst_module->name).arrival; - for (const auto &conn : cell->connections()) { - auto port_wire = inst_module->wire(conn.first); - if (!port_wire->port_output) + + for (auto &i : timing.at(inst_module->name).arrival) { + if (!cell->hasPort(i.first.name)) continue; - for (int i = 0; i < GetSize(conn.second); i++) { - auto d = t.at(TimingInfo::NameBit(conn.first,i), 0); - if (d == 0) - continue; + auto port_wire = inst_module->wire(i.first.name); + log_assert(port_wire->port_output); + + auto d = i.second.first; + if (d == 0) + continue; + auto offset = i.first.offset; #ifndef NDEBUG - if (ys_debug(1)) { - static std::set> seen; - if (seen.emplace(inst_module->name, conn.first, i).second) log("%s.%s[%d] abc9_arrival = %d\n", - log_id(cell->type), log_id(conn.first), i, d); - } -#endif - arrival_times[conn.second[i]] = d; + if (ys_debug(1)) { + static pool> seen; + if (seen.emplace(inst_module->name, i.first).second) log("%s.%s[%d] abc9_arrival = %d\n", + log_id(cell->type), log_id(i.first.name), offset, d); } +#endif + arrival_times[cell->getPort(i.first.name)[offset]] = d; } if (abc9_flop) diff --git a/kernel/constids.inc b/kernel/constids.inc index 8ccb60089..566b76217 100644 --- a/kernel/constids.inc +++ b/kernel/constids.inc @@ -179,6 +179,7 @@ X(SRC_WIDTH) X(SRST) X(SRST_POLARITY) X(SRST_VALUE) +X(sta_arrival) X(STATE_BITS) X(STATE_NUM) X(STATE_NUM_LOG2) diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc index 88153a380..cd0f5ab12 100644 --- a/kernel/rtlil.cc +++ b/kernel/rtlil.cc @@ -480,6 +480,35 @@ vector RTLIL::AttrObject::get_hdlname_attribute() const return split_tokens(get_string_attribute(ID::hdlname), " "); } +void RTLIL::AttrObject::set_intvec_attribute(RTLIL::IdString id, const vector &data) +{ + std::stringstream attrval; + for (auto &i : data) { + if (attrval.tellp() > 0) + attrval << " "; + attrval << i; + } + attributes[id] = RTLIL::Const(attrval.str()); +} + +vector RTLIL::AttrObject::get_intvec_attribute(RTLIL::IdString id) const +{ + vector data; + auto it = attributes.find(id); + if (it != attributes.end()) + for (const auto &s : split_tokens(attributes.at(id).decode_string())) { + char *end = nullptr; + errno = 0; + long value = strtol(s.c_str(), &end, 10); + if (end != s.c_str() + s.size()) + log_cmd_error("Literal for intvec attribute has invalid format"); + if (errno == ERANGE || value < INT_MIN || value > INT_MAX) + log_cmd_error("Literal for intvec attribute is out of range"); + data.push_back(value); + } + return data; +} + bool RTLIL::Selection::selected_module(RTLIL::IdString mod_name) const { if (full_selection) diff --git a/kernel/rtlil.h b/kernel/rtlil.h index 68481b81c..073110f16 100644 --- a/kernel/rtlil.h +++ b/kernel/rtlil.h @@ -718,6 +718,9 @@ struct RTLIL::AttrObject void set_hdlname_attribute(const vector &hierarchy); vector get_hdlname_attribute() const; + + void set_intvec_attribute(RTLIL::IdString id, const vector &data); + vector get_intvec_attribute(RTLIL::IdString id) const; }; struct RTLIL::SigChunk diff --git a/kernel/timinginfo.h b/kernel/timinginfo.h index 9d88ac027..e7e4eab6e 100644 --- a/kernel/timinginfo.h +++ b/kernel/timinginfo.h @@ -49,9 +49,9 @@ struct TimingInfo struct ModuleTiming { - RTLIL::IdString type; dict comb; - dict arrival, required; + dict> arrival, required; + bool has_inputs; }; dict data; @@ -120,11 +120,10 @@ struct TimingInfo } } else if (cell->type == ID($specify3)) { - auto src = cell->getPort(ID::SRC); + auto src = cell->getPort(ID::SRC).as_bit(); auto dst = cell->getPort(ID::DST); - for (const auto &c : src.chunks()) - if (!c.wire->port_input) - log_error("Module '%s' contains specify cell '%s' where SRC '%s' is not a module input.\n", log_id(module), log_id(cell), log_signal(src)); + if (!src.wire || !src.wire->port_input) + log_error("Module '%s' contains specify cell '%s' where SRC '%s' is not a module input.\n", log_id(module), log_id(cell), log_signal(src)); for (const auto &c : dst.chunks()) if (!c.wire->port_output) log_error("Module '%s' contains specify cell '%s' where DST '%s' is not a module output.\n", log_id(module), log_id(cell), log_signal(dst)); @@ -136,34 +135,49 @@ struct TimingInfo max = 0; } for (const auto &d : dst) { - auto &v = t.arrival[NameBit(d)]; - v = std::max(v, max); + auto r = t.arrival.insert(NameBit(d)); + auto &v = r.first->second; + if (r.second || v.first < max) { + v.first = max; + v.second = NameBit(src); + } } } else if (cell->type == ID($specrule)) { - auto type = cell->getParam(ID::TYPE).decode_string(); - if (type != "$setup" && type != "$setuphold") + IdString type = cell->getParam(ID::TYPE).decode_string(); + if (type != ID($setup) && type != ID($setuphold)) continue; auto src = cell->getPort(ID::SRC); - auto dst = cell->getPort(ID::DST); + auto dst = cell->getPort(ID::DST).as_bit(); for (const auto &c : src.chunks()) - if (!c.wire->port_input) + if (!c.wire || !c.wire->port_input) log_error("Module '%s' contains specify cell '%s' where SRC '%s' is not a module input.\n", log_id(module), log_id(cell), log_signal(src)); - for (const auto &c : dst.chunks()) - if (!c.wire->port_input) - log_error("Module '%s' contains specify cell '%s' where DST '%s' is not a module input.\n", log_id(module), log_id(cell), log_signal(dst)); + if (!dst.wire || !dst.wire->port_input) + log_error("Module '%s' contains specify cell '%s' where DST '%s' is not a module input.\n", log_id(module), log_id(cell), log_signal(dst)); int max = cell->getParam(ID::T_LIMIT_MAX).as_int(); if (max < 0) { log_warning("Module '%s' contains specify cell '%s' with T_LIMIT_MAX < 0 which is currently unsupported. Clamping to 0.\n", log_id(module), log_id(cell)); max = 0; } for (const auto &s : src) { - auto &v = t.required[NameBit(s)]; - v = std::max(v, max); + auto r = t.required.insert(NameBit(s)); + auto &v = r.first->second; + if (r.second || v.first < max) { + v.first = max; + v.second = NameBit(dst); + } } } } + for (auto port_name : module->ports) { + auto wire = module->wire(port_name); + if (wire->port_input) { + t.has_inputs = true; + break; + } + } + return t; } diff --git a/passes/cmds/Makefile.inc b/passes/cmds/Makefile.inc index 53bfd40c6..01e052fdf 100644 --- a/passes/cmds/Makefile.inc +++ b/passes/cmds/Makefile.inc @@ -40,3 +40,4 @@ endif OBJS += passes/cmds/scratchpad.o OBJS += passes/cmds/logger.o OBJS += passes/cmds/printattrs.o +OBJS += passes/cmds/sta.o \ No newline at end of file diff --git a/passes/cmds/sta.cc b/passes/cmds/sta.cc new file mode 100644 index 000000000..13e1ee13c --- /dev/null +++ b/passes/cmds/sta.cc @@ -0,0 +1,312 @@ +/* + * yosys -- Yosys Open SYnthesis Suite + * + * Copyright (C) 2012 Clifford Wolf + * (C) 2019 Eddie Hung + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + */ + +#include "kernel/yosys.h" +#include "kernel/sigtools.h" +#include "kernel/timinginfo.h" +#include + +USING_YOSYS_NAMESPACE +PRIVATE_NAMESPACE_BEGIN + +struct StaWorker +{ + Design *design; + Module *module; + SigMap sigmap; + + struct t_data { + Cell* driver; + IdString dst_port, src_port; + vector> fanouts; + SigBit backtrack; + t_data() : driver(nullptr) {} + }; + dict data; + std::deque queue; + struct t_endpoint { + Cell *sink; + IdString port; + int required; + t_endpoint() : sink(nullptr), required(0) {} + }; + dict endpoints; + + int maxarrival; + SigBit maxbit; + + pool driven; + + StaWorker(RTLIL::Module *module) : design(module->design), module(module), sigmap(module), maxarrival(0) + { + TimingInfo timing; + + for (auto cell : module->cells()) + { + Module *inst_module = design->module(cell->type); + if (!inst_module) { + log_warning("Cell type '%s' not recognised! Ignoring.\n", log_id(cell->type)); + continue; + } + + if (!inst_module->get_blackbox_attribute()) { + log_warning("Cell type '%s' is not a black- nor white-box! Ignoring.\n", log_id(cell->type)); + continue; + } + + IdString derived_type = inst_module->derive(design, cell->parameters); + inst_module = design->module(derived_type); + log_assert(inst_module); + + if (!timing.count(derived_type)) { + auto &t = timing.setup_module(inst_module); + if (t.has_inputs && t.comb.empty() && t.arrival.empty() && t.required.empty()) + log_warning("Module '%s' has no timing arcs!\n", log_id(cell->type)); + } + + auto &t = timing.at(derived_type); + if (t.comb.empty() && t.arrival.empty() && t.required.empty()) + continue; + + pool> src_bits, dst_bits; + + for (auto &conn : cell->connections()) { + auto rhs = sigmap(conn.second); + for (auto i = 0; i < GetSize(rhs); i++) { + const auto &bit = rhs[i]; + if (!bit.wire) + continue; + TimingInfo::NameBit namebit(conn.first,i); + if (cell->input(conn.first)) { + src_bits.insert(std::make_pair(bit,namebit)); + + auto it = t.required.find(namebit); + if (it == t.required.end()) + continue; + auto r = endpoints.insert(bit); + if (r.second || r.first->second.required < it->second.first) { + r.first->second.sink = cell; + r.first->second.port = conn.first; + r.first->second.required = it->second.first; + } + } + if (cell->output(conn.first)) { + dst_bits.insert(std::make_pair(bit,namebit)); + auto &d = data[bit]; + d.driver = cell; + d.dst_port = conn.first; + driven.insert(bit); + + auto it = t.arrival.find(namebit); + if (it == t.arrival.end()) + continue; + const auto &s = it->second.second; + if (cell->hasPort(s.name)) { + auto s_bit = sigmap(cell->getPort(s.name)[s.offset]); + if (s_bit.wire) + data[s_bit].fanouts.emplace_back(bit,it->second.first,s.name); + } + } + } + } + + for (const auto &s : src_bits) + for (const auto &d : dst_bits) { + auto it = t.comb.find(TimingInfo::BitBit(s.second,d.second)); + if (it == t.comb.end()) + continue; + data[s.first].fanouts.emplace_back(d.first,it->second,s.second.name); + } + } + + for (auto port_name : module->ports) { + auto wire = module->wire(port_name); + if (wire->port_input) { + for (const auto &b : sigmap(wire)) { + queue.emplace_back(b); + driven.insert(b); + } + // All primary inputs to arrive at time zero + wire->set_intvec_attribute(ID::sta_arrival, std::vector(GetSize(wire), 0)); + } + if (wire->port_output) + for (const auto &b : sigmap(wire)) + if (b.wire) + endpoints.insert(b); + } + } + + void run() + { + while (!queue.empty()) { + auto b = queue.front(); + queue.pop_front(); + auto it = data.find(b); + if (it == data.end()) + continue; + const auto& src_arrivals = b.wire->get_intvec_attribute(ID::sta_arrival); + log_assert(GetSize(src_arrivals) == GetSize(b.wire)); + auto src_arrival = src_arrivals[b.offset]; + for (const auto &d : it->second.fanouts) { + const auto &dst_bit = std::get<0>(d); + auto dst_arrivals = dst_bit.wire->get_intvec_attribute(ID::sta_arrival); + if (dst_arrivals.empty()) + dst_arrivals = std::vector(GetSize(dst_bit.wire), -1); + else + log_assert(GetSize(dst_arrivals) == GetSize(dst_bit.wire)); + auto &dst_arrival = dst_arrivals[dst_bit.offset]; + auto new_arrival = src_arrival + std::get<1>(d); + if (dst_arrival < new_arrival) { + auto dst_wire = dst_bit.wire; + dst_arrival = std::max(dst_arrival, new_arrival); + dst_wire->set_intvec_attribute(ID::sta_arrival, dst_arrivals); + queue.emplace_back(dst_bit); + + data[dst_bit].backtrack = b; + data[dst_bit].src_port = std::get<2>(d); + + auto it = endpoints.find(dst_bit); + if (it != endpoints.end()) + new_arrival += it->second.required; + if (new_arrival > maxarrival && driven.count(b)) { + maxarrival = new_arrival; + maxbit = dst_bit; + } + } + } + } + + auto b = maxbit; + if (b == SigBit()) { + log("No timing paths found.\n"); + return; + } + + log("Latest arrival time in '%s' is %d:\n", log_id(module), maxarrival); + auto it = endpoints.find(maxbit); + if (it != endpoints.end() && it->second.sink) + log(" %6d %s (%s.%s)\n", maxarrival, log_id(it->second.sink), log_id(it->second.sink->type), log_id(it->second.port)); + else { + log(" %6d (%s)\n", maxarrival, b.wire->port_output ? "" : ""); + if (!b.wire->port_output) + log_warning("Critical-path does not terminate in a recognised endpoint.\n"); + } + auto jt = data.find(b); + while (jt != data.end()) { + int arrival = b.wire->get_intvec_attribute(ID::sta_arrival)[b.offset]; + if (jt->second.driver) { + log(" %s\n", log_signal(b)); + 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)); + } + else if (b.wire->port_input) + log(" %6d %s (%s)\n", arrival, log_signal(b), ""); + else + log_abort(); + b = jt->second.backtrack; + jt = data.find(b); + } + + std::map arrival_histogram; + for (const auto &i : endpoints) { + const auto &b = i.first; + if (!driven.count(b)) + continue; + + if (!b.wire->attributes.count(ID::sta_arrival)) { + log_warning("Endpoint %s.%s has no (* sta_arrival *) value.\n", log_id(module), log_signal(b)); + continue; + } + + auto arrival = b.wire->get_intvec_attribute(ID::sta_arrival)[b.offset]; + if (arrival < 0) { + log_warning("Endpoint %s.%s has no (* sta_arrival *) value.\n", log_id(module), log_signal(b)); + continue; + } + arrival += i.second.required; + arrival_histogram[arrival]++; + } + // Adapted from https://github.com/YosysHQ/nextpnr/blob/affb12cc27ebf409eade062c4c59bb98569d8147/common/timing.cc#L946-L969 + if (arrival_histogram.size() > 0) { + unsigned num_bins = 20; + unsigned bar_width = 60; + auto min_arrival = arrival_histogram.begin()->first; + auto max_arrival = arrival_histogram.rbegin()->first; + auto bin_size = std::max(1, ceil((max_arrival - min_arrival + 1) / float(num_bins))); + std::vector bins(num_bins); + unsigned max_freq = 0; + for (const auto &i : arrival_histogram) { + auto &bin = bins[(i.first - min_arrival) / bin_size]; + bin += i.second; + max_freq = std::max(max_freq, bin); + } + bar_width = std::min(bar_width, max_freq); + + log("\n"); + log("Arrival histogram:\n"); + log(" legend: * represents %d endpoint(s)\n", max_freq / bar_width); + log(" + represents [1,%d) endpoint(s)\n", max_freq / bar_width); + for (int i = num_bins-1; i >= 0; --i) + log("(%6d, %6d] |%s%c\n", min_arrival + bin_size * (i + 1), min_arrival + bin_size * i, + std::string(bins[i] * bar_width / max_freq, '*').c_str(), + (bins[i] * bar_width) % max_freq > 0 ? '+' : ' '); + } + } +}; + +struct StaPass : public Pass { + StaPass() : Pass("sta", "perform static timing analysis") { } + void help() override + { + // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| + log("\n"); + log(" sta [options] [selection]\n"); + log("\n"); + log("This command performs static timing analysis on the design. (Only considers\n"); + log("paths within a single module, so the design must be flattened.)\n"); + log("\n"); + } + void execute(std::vector args, RTLIL::Design *design) override + { + log_header(design, "Executing STA pass (static timing analysis).\n"); + + /* + size_t argidx; + for (argidx = 1; argidx < args.size(); argidx++) { + if (args[argidx] == "-TODO") { + continue; + } + break; + } + */ + + extra_args(args, 1, design); + + for (Module *module : design->selected_modules()) + { + if (module->has_processes_warn()) + continue; + + StaWorker worker(module); + worker.run(); + } + } +} StaPass; + +PRIVATE_NAMESPACE_END diff --git a/passes/techmap/abc9_ops.cc b/passes/techmap/abc9_ops.cc index 7a6959971..29fe74ec7 100644 --- a/passes/techmap/abc9_ops.cc +++ b/passes/techmap/abc9_ops.cc @@ -648,40 +648,38 @@ void prep_delays(RTLIL::Design *design, bool dff_mode) auto inst_module = design->module(cell->type); log_assert(inst_module); - auto &t = timing.at(cell->type).required; - for (auto &conn : cell->connections_) { - auto port_wire = inst_module->wire(conn.first); + for (auto &i : timing.at(cell->type).required) { + auto port_wire = inst_module->wire(i.first.name); if (!port_wire) log_error("Port %s in cell %s (type %s) from module %s does not actually exist", - log_id(conn.first), log_id(cell), log_id(cell->type), log_id(module)); - if (!port_wire->port_input) - continue; - if (conn.second.is_fully_const()) + log_id(i.first.name), log_id(cell), log_id(cell->type), log_id(module)); + log_assert(port_wire->port_input); + + auto d = i.second.first; + if (d == 0) continue; - SigSpec O = module->addWire(NEW_ID, GetSize(conn.second)); - for (int i = 0; i < GetSize(conn.second); i++) { - auto d = t.at(TimingInfo::NameBit(conn.first,i), 0); - if (d == 0) - continue; + auto offset = i.first.offset; + auto O = module->addWire(NEW_ID); + auto rhs = cell->getPort(i.first.name); #ifndef NDEBUG - if (ys_debug(1)) { - static std::set> seen; - if (seen.emplace(cell->type, conn.first, i).second) log("%s.%s[%d] abc9_required = %d\n", - log_id(cell->type), log_id(conn.first), i, d); - } + if (ys_debug(1)) { + static pool> seen; + if (seen.emplace(cell->type, i.first).second) log("%s.%s[%d] abc9_required = %d\n", + log_id(cell->type), log_id(i.first.name), offset, d); + } #endif - auto r = box_cache.insert(d); - if (r.second) { - r.first->second = delay_module->derive(design, {{ID::DELAY, d}}); - log_assert(r.first->second.begins_with("$paramod$__ABC9_DELAY\\DELAY=")); - } - auto box = module->addCell(NEW_ID, r.first->second); - box->setPort(ID::I, conn.second[i]); - box->setPort(ID::O, O[i]); - conn.second[i] = O[i]; + auto r = box_cache.insert(d); + if (r.second) { + r.first->second = delay_module->derive(design, {{ID::DELAY, d}}); + log_assert(r.first->second.begins_with("$paramod$__ABC9_DELAY\\DELAY=")); } + auto box = module->addCell(NEW_ID, r.first->second); + box->setPort(ID::I, rhs[offset]); + box->setPort(ID::O, O); + rhs[offset] = O; + cell->setPort(i.first.name, rhs); } } } @@ -1006,16 +1004,16 @@ void prep_box(RTLIL::Design *design) log_assert(GetSize(wire) == 1); auto it = t.find(TimingInfo::NameBit(port_name,0)); if (it == t.end()) - // Assume no connectivity if no setup time - ss << "-"; + // Assume that no setup time means zero + ss << 0; else { - ss << it->second; + ss << it->second.first; #ifndef NDEBUG if (ys_debug(1)) { static std::set> seen; if (seen.emplace(module->name, port_name).second) log("%s.%s abc9_required = %d\n", log_id(module), - log_id(port_name), it->second); + log_id(port_name), it->second.first); } #endif } diff --git a/tests/various/sta.ys b/tests/various/sta.ys new file mode 100644 index 000000000..156c31c47 --- /dev/null +++ b/tests/various/sta.ys @@ -0,0 +1,81 @@ +read_verilog -specify < o) = 10; +endspecify +endmodule + +module top(input i); +wire w; +buffer b(.i(i), .o(w)); +endmodule +EOT + +logger -expect warning "Critical-path does not terminate in a recognised endpoint\." 1 +sta + + +design -reset +read_verilog -specify < o) = 10; +endspecify +endmodule + +module top(input i, output o, p); +buffer b(.i(i), .o(o)); +endmodule +EOT + +sta + + +design -reset +read_verilog -specify < o) = 10; +endspecify +endmodule + +module top(input i, output o, p); +buffer b(.i(i), .o(o)); +const0 c(.o(p)); +endmodule +EOT + +logger -expect warning "Cell type 'const0' not recognised! Ignoring\." 1 +sta + + +design -reset +read_verilog -specify < o) = 10; +endspecify +endmodule +module const0(output o); +endmodule + +module top(input i, output o, p); +buffer b(.i(i), .o(o)); +const0 c(.o(p)); +endmodule +EOT + +sta + +logger -expect-no-warnings -- 2.30.2