vpr: Add initial route tree stub check to check_route
diff --git a/vpr/src/route/check_route.cpp b/vpr/src/route/check_route.cpp
index 821ce50..f08d3d6 100755
--- a/vpr/src/route/check_route.cpp
+++ b/vpr/src/route/check_route.cpp
@@ -14,6 +14,8 @@
#include "rr_graph.h"
#include "check_rr_graph.h"
#include "read_xml_arch_file.h"
+#include "route_tree_type.h"
+#include "route_tree_timing.h"
struct t_node_edge {
t_node_edge(int fnode, int tnode) {
@@ -51,6 +53,11 @@
static void expand_non_configurable(int inode, std::set<t_node_edge>& edge_set);
static bool check_non_configurable_edges(ClusterNetId net, const t_non_configurable_rr_sets& non_configurable_rr_sets);
+
+void check_net_for_stubs(ClusterNetId net);
+std::vector<t_rt_node*> find_route_tree_stubs(t_rt_node* rt_root);
+bool find_route_tree_stubs_recurr(t_rt_node* rt_root, std::vector<t_rt_node*>& stubs);
+
/************************ Subroutine definitions ****************************/
void check_route(enum e_route_type route_type) {
@@ -180,6 +187,8 @@
check_non_configurable_edges(net_id, non_configurable_rr_sets);
+ check_net_for_stubs(net_id);
+
reset_flags(net_id, connected_to_route);
} /* End for each net */
@@ -880,3 +889,77 @@
return true;
}
+
+//Cheks for stubs in a net's routing.
+//
+//Stubs (routing branches which don't connect to SINKs) serve no purpose, and only chew up wiring unecessarily.
+//The only exception are stubs required by non-configurable switches (e.g. shorts).
+//
+//We treat any configurable stubs as an error.
+void check_net_for_stubs(ClusterNetId net) {
+ auto& route_ctx = g_vpr_ctx.mutable_routing();
+
+ t_rt_node* rt_root = traceback_to_route_tree(net);
+
+ auto stubs = find_route_tree_stubs(rt_root);
+
+ if (!stubs.empty()) {
+ auto& cluster_ctx = g_vpr_ctx.clustering();
+ std::string msg = vtr::string_fmt("Route tree for net '%s' (#%zu) contains stub branches rooted at:\n",
+ cluster_ctx.clb_nlist.net_name(net).c_str(), size_t(net));
+ for (t_rt_node* stub_root : stubs) {
+ msg += vtr::string_fmt(" %s\n", describe_rr_node(stub_root->inode).c_str());
+ }
+
+ VPR_THROW(VPR_ERROR_ROUTE, msg.c_str());
+ }
+
+ free_route_tree(rt_root);
+}
+
+//Returns the set of stub roots for a given route tree
+std::vector<t_rt_node*> find_route_tree_stubs(t_rt_node* rt_root) {
+ std::vector<t_rt_node*> stubs;
+ find_route_tree_stubs_recurr(rt_root, stubs);
+ return stubs;
+}
+
+//Returns true if rt_root is a configurable stub.
+//If any of rt_root's children are stubs they are added to 'stubs' since they are stub roots
+//
+//A stub is defined as a branch of the route tree which does not connect to a SINK, but has
+//configurable edges (and hence should have been trimmed).
+bool find_route_tree_stubs_recurr(t_rt_node* rt_root, std::vector<t_rt_node*>& stubs) {
+ auto& device_ctx = g_vpr_ctx.device();
+
+ if (rt_root->u.child_list == nullptr) {
+ //If a leaf of the route tree is not a SINK, then it is a stub
+ if (device_ctx.rr_nodes[rt_root->inode].type() != SINK) {
+ return true; //It is the current root of this stub
+ } else {
+ return false;
+ }
+ } else {
+ //If any of the children are not stubs, neither is the current node
+ bool is_stub = true;
+ std::vector<t_rt_node*> child_stubs;
+ for (t_linked_rt_edge* edge = rt_root->u.child_list; edge != nullptr; edge = edge->next) {
+ bool child_is_stub = find_route_tree_stubs_recurr(edge->child, stubs);
+ bool driver_switch_configurable = device_ctx.rr_switch_inf[edge->iswitch].configurable();
+
+ if (child_is_stub && driver_switch_configurable) {
+ child_stubs.push_back(edge->child);
+ } else {
+ is_stub = false;
+ }
+ }
+
+ if (is_stub) {
+ return true; //All children were stubs, so is the current node
+ } else {
+ //This node is not a stub, so add any child stubs as stub roots
+ stubs.insert(stubs.end(), child_stubs.begin(), child_stubs.end());
+ return false;
+ }
+ }
+}
