vpr: Add RRGraph class and checking infrastructure
The RRGraph class aims to encapsulate the Routing Resource (RR) Graph
which describes the inter-block FPGA routing network. Historically, this
data structure has not been encapsulated making it difficult to change.
This commit adds the RRGraph class interface, implementation, and some
sanity checking. However the RRGraph class is currently unused by the
VPR code base.
The goal, overtime, is to migrate the various components of the tool
to use the new RRGraph object. Once all components are driven off the
RRGraph object, the old RR Graph data structures (device_ctx.rr_nodes,
device_ctx.rr_node_indices and friends) will be removed.
diff --git a/vpr/src/device/check_rr_graph_obj.cpp b/vpr/src/device/check_rr_graph_obj.cpp
new file mode 100644
index 0000000..253092f
--- /dev/null
+++ b/vpr/src/device/check_rr_graph_obj.cpp
@@ -0,0 +1,200 @@
+#include <map>
+
+#include "vtr_log.h"
+
+#include "check_rr_graph_obj.h"
+
+/***********************************************************************
+ * This function aims at checking any duplicated edges (with same EdgeId)
+ * of a given node.
+ * We will walkthrough the input edges of a node and see if there is any duplication
+ **********************************************************************/
+static bool check_rr_graph_node_duplicated_edges(const RRGraph& rr_graph,
+ const RRNodeId& node) {
+ bool no_duplication = true;
+
+ /* Create a map for each input edge */
+ std::map<RREdgeId, size_t> edge_counter;
+
+ /* Check each input edges */
+ for (const auto edge : rr_graph.node_in_edges(node)) {
+ auto result = edge_counter.insert(std::pair<RREdgeId, size_t>(edge, 1));
+ if (false == result.second) {
+ result.first->second++;
+ }
+ }
+
+ for (auto& elem : edge_counter) {
+ if (elem.second > 1) {
+ /* Reach here it means we find some duplicated edges and report errors */
+ /* Print a warning! */
+ VTR_LOG_WARN("Node %d has duplicated input edges (id = %d)!\n",
+ size_t(node), size_t(elem.first));
+ rr_graph.print_node(node);
+ no_duplication = false;
+ }
+ }
+
+ return no_duplication;
+}
+
+/***********************************************************************
+ * Check the whole Routing Resource Graph
+ * identify and report any duplicated edges between two nodes
+ **********************************************************************/
+static bool check_rr_graph_duplicated_edges(const RRGraph& rr_graph) {
+ bool no_duplication = true;
+ /* For each node:
+ * Search input edges, see there are two edges with same id or address
+ */
+ for (const auto& node : rr_graph.nodes()) {
+ if (false == check_rr_graph_node_duplicated_edges(rr_graph, node)) {
+ no_duplication = false;
+ }
+ }
+
+ return no_duplication;
+}
+
+/***********************************************************************
+ * Identify and report any dangling node (nodes without any fan-in or fan-out)
+ * in the RRGraph
+ **********************************************************************/
+static bool check_rr_graph_dangling_nodes(const RRGraph& rr_graph) {
+ bool no_dangling = true;
+ /* For each node:
+ * check if the number of input edges and output edges are both 0
+ * If so, this is a dangling nodes and report
+ */
+ for (auto node : rr_graph.nodes()) {
+ if ((0 == rr_graph.node_fan_in(node))
+ && (0 == rr_graph.node_fan_out(node))) {
+ /* Print a warning! */
+ VTR_LOG_WARN("Node %s is dangling (zero fan-in and zero fan-out)!\n",
+ node);
+ VTR_LOG_WARN("Node details for debugging:\n");
+ rr_graph.print_node(node);
+ no_dangling = false;
+ }
+ }
+
+ return no_dangling;
+}
+
+/***********************************************************************
+ * check if all the source nodes are in the right condition:
+ * 1. zero fan-in and non-zero fanout
+ **********************************************************************/
+static bool check_rr_graph_source_nodes(const RRGraph& rr_graph) {
+ bool invalid_sources = false;
+ /* For each node:
+ * check if the number of input edges and output edges are both 0
+ * If so, this is a dangling nodes and report
+ */
+ for (auto node : rr_graph.nodes()) {
+ /* Pass nodes whose types are not SOURCE */
+ if (SOURCE != rr_graph.node_type(node)) {
+ continue;
+ }
+ if ((0 != rr_graph.node_fan_in(node))
+ || (0 == rr_graph.node_fan_out(node))) {
+ /* Print a warning! */
+ VTR_LOG_WARN("Source node %d is invalid (should have zero fan-in and non-zero fan-out)!\n",
+ size_t(node));
+ VTR_LOG_WARN("Node details for debugging:\n");
+ rr_graph.print_node(node);
+ invalid_sources = true;
+ }
+ }
+
+ return invalid_sources;
+}
+
+/***********************************************************************
+ * check if all the sink nodes are in the right condition:
+ * 1. non-zero fan-in and zero fanout
+ **********************************************************************/
+static bool check_rr_graph_sink_nodes(const RRGraph& rr_graph) {
+ bool invalid_sinks = false;
+ /* For each node:
+ * check if the number of input edges and output edges are both 0
+ * If so, this is a dangling nodes and report
+ */
+ for (auto node : rr_graph.nodes()) {
+ /* Pass nodes whose types are not SINK */
+ if (SINK != rr_graph.node_type(node)) {
+ continue;
+ }
+ if ((0 == rr_graph.node_fan_in(node))
+ || (0 != rr_graph.node_fan_out(node))) {
+ /* Print a warning! */
+ VTR_LOG_WARN("Sink node %s is invalid (should have non-zero fan-in and zero fan-out)!\n",
+ node);
+ VTR_LOG_WARN("Node details for debugging:\n");
+ rr_graph.print_node(node);
+ invalid_sinks = true;
+ }
+ }
+
+ return invalid_sinks;
+}
+
+/***********************************************************************
+ * This is an advanced checker for RRGraph object
+ * Note that the checker try to report as many problems as it can.
+ * The problems may cause routing efficiency or even failures, depending
+ * on routing algorithms.
+ * It is strongly suggested to run this sanitizer before conducting
+ * routing algorithms
+ *
+ * For those who will develop customized rr_graphs and routers:
+ * On the other hand, it is suggested that developers to create their
+ * own checking function for the rr_graph, to guarantee their routers
+ * will work properly.
+ **********************************************************************/
+bool check_rr_graph(const RRGraph& rr_graph) {
+ bool check_flag = true;
+ size_t num_err = 0;
+
+ if (false == check_rr_graph_duplicated_edges(rr_graph)) {
+ VTR_LOG_WARN("Fail in checking duplicated edges !\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ if (false == check_rr_graph_dangling_nodes(rr_graph)) {
+ VTR_LOG_WARN("Fail in checking dangling nodes !\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ if (false == check_rr_graph_source_nodes(rr_graph)) {
+ VTR_LOG_WARN("Fail in checking source nodes!\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ if (false == check_rr_graph_sink_nodes(rr_graph)) {
+ VTR_LOG_WARN("Fail in checking sink nodes!\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ if (false == check_rr_graph_source_nodes(rr_graph)) {
+ VTR_LOG_WARN("Fail in checking source nodes!\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ if (false == check_rr_graph_sink_nodes(rr_graph)) {
+ VTR_LOG_WARN("Fail in checking sink nodes!\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ /* Error out if there is any fatal errors found */
+ VTR_LOG_WARN("Checked Routing Resource graph with %d errors !\n",
+ num_err);
+
+ return check_flag;
+}
diff --git a/vpr/src/device/check_rr_graph_obj.h b/vpr/src/device/check_rr_graph_obj.h
new file mode 100644
index 0000000..5b50412
--- /dev/null
+++ b/vpr/src/device/check_rr_graph_obj.h
@@ -0,0 +1,11 @@
+#ifndef CHECK_RR_GRAPH_OBJ_H
+#define CHECK_RR_GRAPH_OBJ_H
+
+/* Include header files which include data structures used by
+ * the function declaration
+ */
+#include "rr_graph_obj.h"
+
+bool check_rr_graph(const RRGraph& rr_graph);
+
+#endif
diff --git a/vpr/src/device/rr_graph_fwd.h b/vpr/src/device/rr_graph_fwd.h
new file mode 100644
index 0000000..db35d82
--- /dev/null
+++ b/vpr/src/device/rr_graph_fwd.h
@@ -0,0 +1,23 @@
+#ifndef RR_GRAPH_OBJ_FWD_H
+#define RR_GRAPH_OBJ_FWD_H
+#include "vtr_strong_id.h"
+
+/***************************************************************
+ * This file includes a light declaration for the class RRGraph
+ * For a detailed description and how to use the class RRGraph,
+ * please refer to rr_graph_obj.h
+ ***************************************************************/
+
+class RRGraph;
+
+struct rr_node_id_tag;
+struct rr_edge_id_tag;
+struct rr_switch_id_tag;
+struct rr_segment_id_tag;
+
+typedef vtr::StrongId<rr_node_id_tag> RRNodeId;
+typedef vtr::StrongId<rr_edge_id_tag> RREdgeId;
+typedef vtr::StrongId<rr_switch_id_tag, short> RRSwitchId;
+typedef vtr::StrongId<rr_segment_id_tag, short> RRSegmentId;
+
+#endif
diff --git a/vpr/src/device/rr_graph_obj.cpp b/vpr/src/device/rr_graph_obj.cpp
new file mode 100644
index 0000000..7e31cd4
--- /dev/null
+++ b/vpr/src/device/rr_graph_obj.cpp
@@ -0,0 +1,1356 @@
+/************************************************************************
+ * Member Functions of RRGraph
+ * include mutators, accessors and utility functions
+ ***********************************************************************/
+#include <cmath>
+#include <algorithm>
+#include <map>
+#include <limits>
+
+#include "vtr_vector_map.h"
+#include "vtr_log.h"
+#include "vtr_util.h"
+#include "vtr_assert.h"
+#include "rr_graph_obj.h"
+#include "rr_graph_obj_utils.h"
+
+//Accessors
+RRGraph::node_range RRGraph::nodes() const {
+ return vtr::make_range(node_ids_.begin(), node_ids_.end());
+}
+
+RRGraph::edge_range RRGraph::edges() const {
+ return vtr::make_range(edge_ids_.begin(), edge_ids_.end());
+}
+
+RRGraph::switch_range RRGraph::switches() const {
+ return vtr::make_range(switch_ids_.begin(), switch_ids_.end());
+}
+
+RRGraph::segment_range RRGraph::segments() const {
+ return vtr::make_range(segment_ids_.begin(), segment_ids_.end());
+}
+
+//Node attributes
+t_rr_type RRGraph::node_type(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return node_types_[node];
+}
+
+size_t RRGraph::node_index(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return size_t(node);
+}
+
+short RRGraph::node_xlow(const RRNodeId& node) const {
+ return node_bounding_box(node).xmin();
+}
+
+short RRGraph::node_ylow(const RRNodeId& node) const {
+ return node_bounding_box(node).ymin();
+}
+
+short RRGraph::node_xhigh(const RRNodeId& node) const {
+ return node_bounding_box(node).xmax();
+}
+
+short RRGraph::node_yhigh(const RRNodeId& node) const {
+ return node_bounding_box(node).ymax();
+}
+
+short RRGraph::node_length(const RRNodeId& node) const {
+ return std::max(node_xhigh(node) - node_xlow(node), node_yhigh(node) - node_ylow(node));
+}
+
+vtr::Rect<short> RRGraph::node_bounding_box(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return node_bounding_boxes_[node];
+}
+
+/* Node starting and ending points */
+/************************************************************************
+ * Get the coordinator of a starting point of a routing track
+ * For routing tracks in INC_DIRECTION
+ * (xlow, ylow) should be the starting point
+ *
+ * For routing tracks in DEC_DIRECTION
+ * (xhigh, yhigh) should be the starting point
+ *
+ * For routing tracks in BI_DIRECTION
+ * we always use (xhigh, yhigh)
+ ***********************************************************************/
+vtr::Point<short> RRGraph::node_start_coordinate(const RRNodeId& node) const {
+ /* Make sure we have CHANX or CHANY */
+ VTR_ASSERT((CHANX == node_type(node)) || (CHANY == node_type(node)));
+
+ vtr::Point<short> start_coordinate(node_xlow(node), node_ylow(node));
+
+ if (DEC_DIRECTION == node_direction(node)) {
+ start_coordinate.set(node_xhigh(node), node_yhigh(node));
+ }
+
+ return start_coordinate;
+}
+
+/************************************************************************
+ * Get the coordinator of a end point of a routing track
+ * For routing tracks in INC_DIRECTION
+ * (xhigh, yhigh) should be the ending point
+ *
+ * For routing tracks in DEC_DIRECTION
+ * (xlow, ylow) should be the ending point
+ *
+ * For routing tracks in BI_DIRECTION
+ * we always use (xhigh, yhigh)
+ ***********************************************************************/
+vtr::Point<short> RRGraph::node_end_coordinate(const RRNodeId& node) const {
+ /* Make sure we have CHANX or CHANY */
+ VTR_ASSERT((CHANX == node_type(node)) || (CHANY == node_type(node)));
+
+ vtr::Point<short> end_coordinate(node_xhigh(node), node_yhigh(node));
+
+ if (DEC_DIRECTION == node_direction(node)) {
+ end_coordinate.set(node_xlow(node), node_ylow(node));
+ }
+
+ return end_coordinate;
+}
+
+short RRGraph::node_fan_in(const RRNodeId& node) const {
+ return node_in_edges(node).size();
+}
+
+short RRGraph::node_fan_out(const RRNodeId& node) const {
+ return node_out_edges(node).size();
+}
+
+short RRGraph::node_capacity(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return node_capacities_[node];
+}
+
+short RRGraph::node_ptc_num(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return node_ptc_nums_[node];
+}
+
+short RRGraph::node_pin_num(const RRNodeId& node) const {
+ VTR_ASSERT_MSG(node_type(node) == IPIN || node_type(node) == OPIN,
+ "Pin number valid only for IPIN/OPIN RR nodes");
+ return node_ptc_num(node);
+}
+
+short RRGraph::node_track_num(const RRNodeId& node) const {
+ VTR_ASSERT_MSG(node_type(node) == CHANX || node_type(node) == CHANY,
+ "Track number valid only for CHANX/CHANY RR nodes");
+ return node_ptc_num(node);
+}
+
+short RRGraph::node_class_num(const RRNodeId& node) const {
+ VTR_ASSERT_MSG(node_type(node) == SOURCE || node_type(node) == SINK, "Class number valid only for SOURCE/SINK RR nodes");
+ return node_ptc_num(node);
+}
+
+short RRGraph::node_cost_index(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return node_cost_indices_[node];
+}
+
+e_direction RRGraph::node_direction(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ VTR_ASSERT_MSG(node_type(node) == CHANX || node_type(node) == CHANY, "Direction valid only for CHANX/CHANY RR nodes");
+ return node_directions_[node];
+}
+
+e_side RRGraph::node_side(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ VTR_ASSERT_MSG(node_type(node) == IPIN || node_type(node) == OPIN, "Side valid only for IPIN/OPIN RR nodes");
+ return node_sides_[node];
+}
+
+/* Get the resistance of a node */
+float RRGraph::node_R(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return node_Rs_[node];
+}
+
+/* Get the capacitance of a node */
+float RRGraph::node_C(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return node_Cs_[node];
+}
+
+/*
+ * Get a segment id of a node in rr_graph
+ */
+RRSegmentId RRGraph::node_segment(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+
+ return node_segments_[node];
+}
+
+/*
+ * Get the number of configurable input edges of a node
+ * TODO: we would use the node_num_configurable_in_edges()
+ * when the rr_graph edges have been partitioned
+ * This can avoid unneccessary walkthrough
+ */
+short RRGraph::node_num_configurable_in_edges(const RRNodeId& node) const {
+ return node_configurable_in_edges(node).size();
+}
+
+/*
+ * Get the number of configurable output edges of a node
+ * TODO: we would use the node_num_configurable_out_edges()
+ * when the rr_graph edges have been partitioned
+ * This can avoid unneccessary walkthrough
+ */
+short RRGraph::node_num_configurable_out_edges(const RRNodeId& node) const {
+ return node_configurable_out_edges(node).size();
+}
+
+/*
+ * Get the number of non-configurable input edges of a node
+ * TODO: we would use the node_num_configurable_in_edges()
+ * when the rr_graph edges have been partitioned
+ * This can avoid unneccessary walkthrough
+ */
+short RRGraph::node_num_non_configurable_in_edges(const RRNodeId& node) const {
+ return node_non_configurable_in_edges(node).size();
+}
+
+/*
+ * Get the number of non-configurable output edges of a node
+ * TODO: we would use the node_num_configurable_out_edges()
+ * when the rr_graph edges have been partitioned
+ * This can avoid unneccessary walkthrough
+ */
+short RRGraph::node_num_non_configurable_out_edges(const RRNodeId& node) const {
+ return node_non_configurable_out_edges(node).size();
+}
+
+/* Get the list of configurable edges from the input edges of a given node
+ * And return the range(iterators) of the list
+ */
+RRGraph::edge_range RRGraph::node_configurable_in_edges(const RRNodeId& node) const {
+ /* Make sure we will access a valid node */
+ VTR_ASSERT_SAFE(valid_node_id(node));
+
+ /* By default the configurable edges will be stored at the first part of the edge list (0 to XX) */
+ auto begin = node_in_edges(node).begin();
+
+ /* By default the non-configurable edges will be stored at second part of the edge list (XX to end) */
+ auto end = node_in_edges(node).end() - node_num_non_configurable_in_edges_[node];
+
+ return vtr::make_range(begin, end);
+}
+
+/* Get the list of configurable edges from the input edges of a given node
+ * And return the range(iterators) of the list
+ */
+RRGraph::edge_range RRGraph::node_non_configurable_in_edges(const RRNodeId& node) const {
+ /* Make sure we will access a valid node */
+ VTR_ASSERT_SAFE(valid_node_id(node));
+
+ /* By default the configurable edges will be stored at the first part of the edge list (0 to XX) */
+ auto begin = node_in_edges(node).end() - node_num_non_configurable_in_edges_[node];
+
+ /* By default the non-configurable edges will be stored at second part of the edge list (XX to end) */
+ auto end = node_in_edges(node).end();
+
+ return vtr::make_range(begin, end);
+}
+
+/* Get the list of configurable edges from the input edges of a given node
+ * And return the range(iterators) of the list
+ */
+RRGraph::edge_range RRGraph::node_configurable_out_edges(const RRNodeId& node) const {
+ /* Make sure we will access a valid node */
+ VTR_ASSERT_SAFE(valid_node_id(node));
+
+ /* By default the configurable edges will be stored at the first part of the edge list (0 to XX) */
+ auto begin = node_out_edges(node).begin();
+
+ /* By default the non-configurable edges will be stored at second part of the edge list (XX to end) */
+ auto end = node_out_edges(node).end() - node_num_non_configurable_out_edges_[node];
+
+ return vtr::make_range(begin, end);
+}
+
+/* Get the list of configurable edges from the input edges of a given node
+ * And return the range(iterators) of the list
+ */
+RRGraph::edge_range RRGraph::node_non_configurable_out_edges(const RRNodeId& node) const {
+ /* Make sure we will access a valid node */
+ VTR_ASSERT_SAFE(valid_node_id(node));
+
+ /* By default the configurable edges will be stored at the first part of the edge list (0 to XX) */
+ auto begin = node_out_edges(node).end() - node_num_non_configurable_out_edges_[node];
+
+ /* By default the non-configurable edges will be stored at second part of the edge list (XX to end) */
+ auto end = node_out_edges(node).end();
+
+ return vtr::make_range(begin, end);
+}
+
+RRGraph::edge_range RRGraph::node_out_edges(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return vtr::make_range(node_out_edges_[node].begin(), node_out_edges_[node].end());
+}
+
+RRGraph::edge_range RRGraph::node_in_edges(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ return vtr::make_range(node_in_edges_[node].begin(), node_in_edges_[node].end());
+}
+
+//Edge attributes
+size_t RRGraph::edge_index(const RREdgeId& edge) const {
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ return size_t(edge);
+}
+
+RRNodeId RRGraph::edge_src_node(const RREdgeId& edge) const {
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ return edge_src_nodes_[edge];
+}
+RRNodeId RRGraph::edge_sink_node(const RREdgeId& edge) const {
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ return edge_sink_nodes_[edge];
+}
+
+RRSwitchId RRGraph::edge_switch(const RREdgeId& edge) const {
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ return edge_switches_[edge];
+}
+
+/* Check if the edge is a configurable edge (programmble) */
+bool RRGraph::edge_is_configurable(const RREdgeId& edge) const {
+ /* Make sure we have a valid edge id */
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+
+ auto iswitch = edge_switch(edge);
+
+ return switches_[iswitch].configurable();
+}
+
+/* Check if the edge is a non-configurable edge (hardwired) */
+bool RRGraph::edge_is_non_configurable(const RREdgeId& edge) const {
+ /* Make sure we have a valid edge id */
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ return !edge_is_configurable(edge);
+}
+
+size_t RRGraph::switch_index(const RRSwitchId& switch_id) const {
+ VTR_ASSERT_SAFE(valid_switch_id(switch_id));
+ return size_t(switch_id);
+}
+
+/*
+ * Get a switch from the rr_switch list with a given id
+ */
+const t_rr_switch_inf& RRGraph::get_switch(const RRSwitchId& switch_id) const {
+ VTR_ASSERT_SAFE(valid_switch_id(switch_id));
+ return switches_[switch_id];
+}
+
+size_t RRGraph::segment_index(const RRSegmentId& segment_id) const {
+ VTR_ASSERT_SAFE(valid_segment_id(segment_id));
+ return size_t(segment_id);
+}
+
+/*
+ * Get a segment from the segment list with a given id
+ */
+const t_segment_inf& RRGraph::get_segment(const RRSegmentId& segment_id) const {
+ VTR_ASSERT_SAFE(valid_segment_id(segment_id));
+ return segments_[segment_id];
+}
+
+/************************************************************************
+ * Find all the edges interconnecting two nodes
+ * Return a vector of the edge ids
+ ***********************************************************************/
+std::vector<RREdgeId> RRGraph::find_edges(const RRNodeId& src_node, const RRNodeId& sink_node) const {
+ std::vector<RREdgeId> edges;
+
+ /* Iterate over the outgoing edges of the source node */
+ for (auto edge : node_out_edges(src_node)) {
+ if (edge_sink_node(edge) == sink_node) {
+ /* Update edge list to return */
+ edges.push_back(edge);
+ }
+ }
+
+ return edges;
+}
+
+RRNodeId RRGraph::find_node(const short& x, const short& y, const t_rr_type& type, const int& ptc, const e_side& side) const {
+ initialize_fast_node_lookup();
+
+ size_t itype = type;
+ size_t iside = side;
+
+ /* Check if x, y, type and ptc, side is valid */
+ if ((x < 0) /* See if x is smaller than the index of first element */
+ || (size_t(x) > node_lookup_.size() - 1)) { /* See if x is large than the index of last element */
+ /* Return a zero range! */
+ return RRNodeId::INVALID();
+ }
+
+ /* Check if x, y, type and ptc, side is valid */
+ if ((y < 0) /* See if y is smaller than the index of first element */
+ || (size_t(y) > node_lookup_[x].size() - 1)) { /* See if y is large than the index of last element */
+ /* Return a zero range! */
+ return RRNodeId::INVALID();
+ }
+
+ /* Check if x, y, type and ptc, side is valid */
+ /* itype is always larger than -1, we can skip checking */
+ if (itype > node_lookup_[x][y].size() - 1) { /* See if type is large than the index of last element */
+ /* Return a zero range! */
+ return RRNodeId::INVALID();
+ }
+
+ /* Check if x, y, type and ptc, side is valid */
+ if ((ptc < 0) /* See if ptc is smaller than the index of first element */
+ || (size_t(ptc) > node_lookup_[x][y][type].size() - 1)) { /* See if ptc is large than the index of last element */
+ /* Return a zero range! */
+ return RRNodeId::INVALID();
+ }
+
+ /* Check if x, y, type and ptc, side is valid */
+ /* iside is always larger than -1, we can skip checking */
+ if (iside > node_lookup_[x][y][type][ptc].size() - 1) { /* See if side is large than the index of last element */
+ /* Return a zero range! */
+ return RRNodeId::INVALID();
+ }
+
+ return node_lookup_[x][y][itype][ptc][iside];
+}
+
+/* Find the channel width (number of tracks) of a channel [x][y] */
+short RRGraph::chan_num_tracks(const short& x, const short& y, const t_rr_type& type) const {
+ /* Must be CHANX or CHANY */
+ VTR_ASSERT_MSG(CHANX == type || CHANY == type,
+ "Required node_type to be CHANX or CHANY!");
+ initialize_fast_node_lookup();
+
+ /* Check if x, y, type and ptc is valid */
+ if ((x < 0) /* See if x is smaller than the index of first element */
+ || (size_t(x) > node_lookup_.size() - 1)) { /* See if x is large than the index of last element */
+ /* Return a zero range! */
+ return 0;
+ }
+
+ /* Check if x, y, type and ptc is valid */
+ if ((y < 0) /* See if y is smaller than the index of first element */
+ || (size_t(y) > node_lookup_[x].size() - 1)) { /* See if y is large than the index of last element */
+ /* Return a zero range! */
+ return 0;
+ }
+
+ /* Check if x, y, type and ptc is valid */
+ if ((size_t(type) > node_lookup_[x][y].size() - 1)) { /* See if type is large than the index of last element */
+ /* Return a zero range! */
+ return 0;
+ }
+
+ const auto& matching_nodes = node_lookup_[x][y][type];
+
+ return vtr::make_range(matching_nodes.begin(), matching_nodes.end()).size();
+}
+
+/* This function aims to print basic information about a node */
+void RRGraph::print_node(const RRNodeId& node) const {
+ VTR_LOG("Node id: %d\n", node_index(node));
+ VTR_LOG("Node type: %s\n", rr_node_typename[node_type(node)]);
+ VTR_LOG("Node xlow: %d\n", node_xlow(node));
+ VTR_LOG("Node ylow: %d\n", node_ylow(node));
+ VTR_LOG("Node xhigh: %d\n", node_xhigh(node));
+ VTR_LOG("Node yhigh: %d\n", node_yhigh(node));
+ VTR_LOG("Node ptc: %d\n", node_ptc_num(node));
+ VTR_LOG("Node num in_edges: %d\n", node_in_edges(node).size());
+ VTR_LOG("Node num out_edges: %d\n", node_out_edges(node).size());
+}
+
+/* Check if the segment id of a node is in range */
+bool RRGraph::validate_node_segment(const RRNodeId& node) const {
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ /* Only CHANX and CHANY requires a valid segment id */
+ if ((CHANX == node_type(node))
+ || (CHANY == node_type(node))) {
+ return valid_segment_id(node_segments_[node]);
+ } else {
+ return true;
+ }
+}
+
+/* Check if the segment id of every node is in range */
+bool RRGraph::validate_node_segments() const {
+ bool all_valid = true;
+ for (auto node : nodes()) {
+ if (true == validate_node_segment(node)) {
+ continue;
+ }
+ /* Reach here it means we find an invalid segment id */
+ all_valid = false;
+ /* Print a warning! */
+ VTR_LOG_WARN("Node %d has an invalid segment id (%d)!\n",
+ size_t(node), size_t(node_segment(node)));
+ }
+ return all_valid;
+}
+
+/* Check if the switch id of a edge is in range */
+bool RRGraph::validate_edge_switch(const RREdgeId& edge) const {
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ return valid_switch_id(edge_switches_[edge]);
+}
+
+/* Check if the switch id of every edge is in range */
+bool RRGraph::validate_edge_switches() const {
+ bool all_valid = true;
+ for (auto edge : edges()) {
+ if (true == validate_edge_switch(edge)) {
+ continue;
+ }
+ /* Reach here it means we find an invalid segment id */
+ all_valid = false;
+ /* Print a warning! */
+ VTR_LOG_WARN("Edge %d has an invalid switch id (%d)!\n",
+ size_t(edge), size_t(edge_switch(edge)));
+ }
+ return all_valid;
+}
+
+/* Check if a node is in the list of source_nodes of a edge */
+bool RRGraph::validate_node_is_edge_src(const RRNodeId& node, const RREdgeId& edge) const {
+ /* Assure a valid node id */
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ /* assure a valid edge id */
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ /* find if the node is the src */
+ if (node == edge_src_node(edge)) {
+ return true; /* confirmed source node*/
+ } else {
+ return false; /* not a source */
+ }
+}
+
+/* Check if a node is in the list of sink_nodes of a edge */
+bool RRGraph::validate_node_is_edge_sink(const RRNodeId& node, const RREdgeId& edge) const {
+ /* Assure a valid node id */
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ /* assure a valid edge id */
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ /* find if the node is the sink */
+ if (node == edge_sink_node(edge)) {
+ return true; /* confirmed source node*/
+ } else {
+ return false; /* not a source */
+ }
+}
+
+/* This function will check if a node has valid input edges
+ * 1. Check the edge ids are valid
+ * 2. Check the node is in the list of edge_sink_node
+ */
+bool RRGraph::validate_node_in_edges(const RRNodeId& node) const {
+ bool all_valid = true;
+ /* Assure a valid node id */
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ /* Check each edge */
+ for (auto edge : node_in_edges(node)) {
+ /* assure a valid edge id */
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ /* check the node is in the list of edge_sink_node */
+ if (true == validate_node_is_edge_sink(node, edge)) {
+ continue;
+ }
+ /* Reach here, it means there is something wrong!
+ * Print a warning
+ */
+ VTR_LOG_WARN("Edge %d is in the input edge list of node %d while the node is not in edge's sink node list!\n",
+ size_t(edge), size_t(node));
+ all_valid = false;
+ }
+
+ return all_valid;
+}
+
+/* This function will check if a node has valid output edges
+ * 1. Check the edge ids are valid
+ * 2. Check the node is in the list of edge_source_node
+ */
+bool RRGraph::validate_node_out_edges(const RRNodeId& node) const {
+ bool all_valid = true;
+ /* Assure a valid node id */
+ VTR_ASSERT_SAFE(valid_node_id(node));
+ /* Check each edge */
+ for (auto edge : node_out_edges(node)) {
+ /* assure a valid edge id */
+ VTR_ASSERT_SAFE(valid_edge_id(edge));
+ /* check the node is in the list of edge_sink_node */
+ if (true == validate_node_is_edge_src(node, edge)) {
+ continue;
+ }
+ /* Reach here, it means there is something wrong!
+ * Print a warning
+ */
+ VTR_LOG_WARN("Edge %d is in the output edge list of node %d while the node is not in edge's source node list!\n",
+ size_t(edge), size_t(node));
+ all_valid = false;
+ }
+
+ return all_valid;
+}
+
+/* check all the edges of a node */
+bool RRGraph::validate_node_edges(const RRNodeId& node) const {
+ bool all_valid = true;
+
+ if (false == validate_node_in_edges(node)) {
+ all_valid = false;
+ }
+ if (false == validate_node_out_edges(node)) {
+ all_valid = false;
+ }
+
+ return all_valid;
+}
+
+/* check if all the nodes' input edges are valid */
+bool RRGraph::validate_nodes_in_edges() const {
+ bool all_valid = true;
+ for (auto node : nodes()) {
+ if (true == validate_node_in_edges(node)) {
+ continue;
+ }
+ /* Reach here, it means there is something wrong!
+ * Print a warning
+ */
+ all_valid = false;
+ }
+ return all_valid;
+}
+
+/* check if all the nodes' output edges are valid */
+bool RRGraph::validate_nodes_out_edges() const {
+ bool all_valid = true;
+ for (auto node : nodes()) {
+ if (true == validate_node_out_edges(node)) {
+ continue;
+ }
+ /* Reach here, it means there is something wrong!
+ * Print a warning
+ */
+ all_valid = false;
+ }
+ return all_valid;
+}
+
+/* check all the edges of every node */
+bool RRGraph::validate_nodes_edges() const {
+ bool all_valid = true;
+
+ if (false == validate_nodes_in_edges()) {
+ all_valid = false;
+ }
+ if (false == validate_nodes_out_edges()) {
+ all_valid = false;
+ }
+
+ return all_valid;
+}
+
+/* Check if source node of a edge is valid */
+bool RRGraph::validate_edge_src_node(const RREdgeId& edge) const {
+ return valid_node_id(edge_src_node(edge));
+}
+
+/* Check if sink node of a edge is valid */
+bool RRGraph::validate_edge_sink_node(const RREdgeId& edge) const {
+ return valid_node_id(edge_sink_node(edge));
+}
+
+/* Check if source nodes of a edge are all valid */
+bool RRGraph::validate_edge_src_nodes() const {
+ bool all_valid = true;
+ for (auto edge : edges()) {
+ if (true == validate_edge_src_node(edge)) {
+ continue;
+ }
+ /* Reach here, it means there is something wrong!
+ * Print a warning
+ */
+ VTR_LOG_WARN("Edge %d has a invalid source node %d!\n",
+ size_t(edge), size_t(edge_src_node(edge)));
+ all_valid = false;
+ }
+ return all_valid;
+}
+
+/* Check if source nodes of a edge are all valid */
+bool RRGraph::validate_edge_sink_nodes() const {
+ bool all_valid = true;
+ for (auto edge : edges()) {
+ if (true == validate_edge_sink_node(edge)) {
+ continue;
+ }
+ /* Reach here, it means there is something wrong!
+ * Print a warning
+ */
+ VTR_LOG_WARN("Edge %d has a invalid sink node %d!\n",
+ size_t(edge), size_t(edge_sink_node(edge)));
+ all_valid = false;
+ }
+ return all_valid;
+}
+
+/* This function should be used when nodes, edges, switches and segments have been used after
+ * We will build the fast_lookup, partition edges and check
+ * This function run fundamental and optional checks on internal data
+ * Errors are thrown if fundamental checking fails
+ * Warnings are thrown if optional checking fails
+ */
+bool RRGraph::validate() const {
+ bool check_flag = true;
+ size_t num_err = 0;
+
+ initialize_fast_node_lookup();
+
+ /* Validate the sizes of nodes and node-related vectors
+ * Validate the sizes of edges and edge-related vectors
+ */
+ if (false == validate_sizes()) {
+ VTR_LOG_WARN("Fail in validating node- and edge-related vector sizes!\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ /* Fundamental check */
+ if (false == validate_nodes_edges()) {
+ VTR_LOG_WARN("Fail in validating edges connected to each node!\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ if (false == validate_node_segments()) {
+ VTR_LOG_WARN("Fail in validating segment IDs of nodes !\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ if (false == validate_edge_switches()) {
+ VTR_LOG_WARN("Fail in validating switch IDs of edges !\n");
+ check_flag = false;
+ num_err++;
+ }
+
+ /* Error out if there is any fatal errors found */
+ VTR_LOG_ERROR("Routing Resource graph is not valid due to %d fatal errors !\n",
+ num_err);
+
+ return check_flag;
+}
+
+bool RRGraph::is_dirty() const {
+ return dirty_;
+}
+
+void RRGraph::set_dirty() {
+ dirty_ = true;
+}
+
+void RRGraph::clear_dirty() {
+ dirty_ = false;
+}
+
+/* Reserve a list of nodes */
+void RRGraph::reserve_nodes(const int& num_nodes) {
+ /* Reserve the full set of vectors related to nodes */
+ /* Basic information */
+ this->node_ids_.reserve(num_nodes);
+ this->node_types_.reserve(num_nodes);
+ this->node_bounding_boxes_.reserve(num_nodes);
+ this->node_capacities_.reserve(num_nodes);
+ this->node_ptc_nums_.reserve(num_nodes);
+ this->node_directions_.reserve(num_nodes);
+ this->node_sides_.reserve(num_nodes);
+ this->node_Rs_.reserve(num_nodes);
+ this->node_Cs_.reserve(num_nodes);
+ this->node_segments_.reserve(num_nodes);
+ this->node_num_non_configurable_in_edges_.reserve(num_nodes);
+ this->node_num_non_configurable_out_edges_.reserve(num_nodes);
+
+ /* Edge-relate vectors */
+ this->node_in_edges_.reserve(num_nodes);
+ this->node_out_edges_.reserve(num_nodes);
+}
+
+/* Reserve a list of edges */
+void RRGraph::reserve_edges(const int& num_edges) {
+ /* Reserve the full set of vectors related to edges */
+ this->edge_ids_.reserve(num_edges);
+ this->edge_src_nodes_.reserve(num_edges);
+ this->edge_sink_nodes_.reserve(num_edges);
+ this->edge_switches_.reserve(num_edges);
+}
+
+/* Reserve a list of switches */
+void RRGraph::reserve_switches(const int& num_switches) {
+ this->switch_ids_.reserve(num_switches);
+ this->switches_.reserve(num_switches);
+}
+
+/* Reserve a list of segments */
+void RRGraph::reserve_segments(const int& num_segments) {
+ this->segment_ids_.reserve(num_segments);
+ this->segments_.reserve(num_segments);
+}
+
+/* Mutators */
+RRNodeId RRGraph::create_node(const t_rr_type& type) {
+ //Allocate an ID
+ RRNodeId node_id = RRNodeId(node_ids_.size());
+
+ //Initialize the attributes
+ node_ids_.push_back(node_id);
+ node_types_.push_back(type);
+
+ node_bounding_boxes_.emplace_back(-1, -1, -1, -1);
+
+ node_capacities_.push_back(-1);
+ node_ptc_nums_.push_back(-1);
+ node_cost_indices_.push_back(-1);
+ node_directions_.push_back(NO_DIRECTION);
+ node_sides_.push_back(NUM_SIDES);
+ node_Rs_.push_back(0.);
+ node_Cs_.push_back(0.);
+
+ node_in_edges_.emplace_back(); //Initially empty
+ node_out_edges_.emplace_back(); //Initially empty
+
+ node_num_non_configurable_in_edges_.emplace_back(); //Initially empty
+ node_num_non_configurable_out_edges_.emplace_back(); //Initially empty
+
+ invalidate_fast_node_lookup();
+
+ VTR_ASSERT(validate_sizes());
+
+ return node_id;
+}
+
+RREdgeId RRGraph::create_edge(const RRNodeId& source, const RRNodeId& sink, const RRSwitchId& switch_id) {
+ VTR_ASSERT(valid_node_id(source));
+ VTR_ASSERT(valid_node_id(sink));
+ VTR_ASSERT(valid_switch_id(switch_id));
+
+ //Allocate an ID
+ RREdgeId edge_id = RREdgeId(edge_ids_.size());
+
+ //Initialize the attributes
+ edge_ids_.push_back(edge_id);
+
+ edge_src_nodes_.push_back(source);
+ edge_sink_nodes_.push_back(sink);
+ edge_switches_.push_back(switch_id);
+
+ //Add the edge to the nodes
+ node_out_edges_[source].push_back(edge_id);
+ node_in_edges_[sink].push_back(edge_id);
+
+ VTR_ASSERT(validate_sizes());
+
+ return edge_id;
+}
+
+RRSwitchId RRGraph::create_switch(const t_rr_switch_inf& switch_info) {
+ //Allocate an ID
+ RRSwitchId switch_id = RRSwitchId(switch_ids_.size());
+ switch_ids_.push_back(switch_id);
+
+ switches_.push_back(switch_info);
+
+ return switch_id;
+}
+
+/* Create segment */
+RRSegmentId RRGraph::create_segment(const t_segment_inf& segment_info) {
+ //Allocate an ID
+ RRSegmentId segment_id = RRSegmentId(segment_ids_.size());
+ segment_ids_.push_back(segment_id);
+
+ segments_.push_back(segment_info);
+
+ return segment_id;
+}
+
+/* This function just marks the node to be removed with an INVALID id
+ * It also disconnects and mark the incoming and outcoming edges to be INVALID()
+ * And then set the RRGraph as polluted (dirty_flag = true)
+ * The compress() function should be called to physically remove the node
+ */
+void RRGraph::remove_node(const RRNodeId& node) {
+ //Invalidate all connected edges
+ // TODO: consider removal of self-loop edges?
+ for (auto edge : node_in_edges(node)) {
+ remove_edge(edge);
+ }
+ for (auto edge : node_out_edges(node)) {
+ remove_edge(edge);
+ }
+
+ //Mark node invalid
+ node_ids_[node] = RRNodeId::INVALID();
+
+ //Invalidate the node look-up
+ invalidate_fast_node_lookup();
+
+ set_dirty();
+}
+
+/* This function just marks the edge to be removed with an INVALID id
+ * And then set the RRGraph as polluted (dirty_flag = true)
+ * The compress() function should be called to physically remove the edge
+ */
+void RRGraph::remove_edge(const RREdgeId& edge) {
+ RRNodeId src_node = edge_src_node(edge);
+ RRNodeId sink_node = edge_sink_node(edge);
+
+ //Invalidate node to edge references
+ // TODO: consider making this optional (e.g. if called from remove_node)
+ for (size_t i = 0; i < node_out_edges_[src_node].size(); ++i) {
+ if (node_out_edges_[src_node][i] == edge) {
+ node_out_edges_[src_node][i] = RREdgeId::INVALID();
+ break;
+ }
+ }
+ for (size_t i = 0; i < node_in_edges_[sink_node].size(); ++i) {
+ if (node_in_edges_[sink_node][i] == edge) {
+ node_in_edges_[sink_node][i] = RREdgeId::INVALID();
+ break;
+ }
+ }
+
+ //Mark edge invalid
+ edge_ids_[edge] = RREdgeId::INVALID();
+
+ set_dirty();
+}
+
+void RRGraph::set_node_xlow(const RRNodeId& node, const short& xlow) {
+ VTR_ASSERT(valid_node_id(node));
+
+ node_bounding_boxes_[node].set_xmin(xlow);
+}
+
+void RRGraph::set_node_ylow(const RRNodeId& node, const short& ylow) {
+ VTR_ASSERT(valid_node_id(node));
+
+ node_bounding_boxes_[node].set_ymin(ylow);
+}
+
+void RRGraph::set_node_xhigh(const RRNodeId& node, const short& xhigh) {
+ VTR_ASSERT(valid_node_id(node));
+
+ node_bounding_boxes_[node].set_xmax(xhigh);
+}
+
+void RRGraph::set_node_yhigh(const RRNodeId& node, const short& yhigh) {
+ VTR_ASSERT(valid_node_id(node));
+
+ node_bounding_boxes_[node].set_ymax(yhigh);
+}
+
+void RRGraph::set_node_bounding_box(const RRNodeId& node, const vtr::Rect<short>& bb) {
+ VTR_ASSERT(valid_node_id(node));
+
+ node_bounding_boxes_[node] = bb;
+}
+
+void RRGraph::set_node_capacity(const RRNodeId& node, const short& capacity) {
+ VTR_ASSERT(valid_node_id(node));
+
+ node_capacities_[node] = capacity;
+}
+
+void RRGraph::set_node_ptc_num(const RRNodeId& node, const short& ptc) {
+ VTR_ASSERT(valid_node_id(node));
+
+ node_ptc_nums_[node] = ptc;
+}
+
+void RRGraph::set_node_pin_num(const RRNodeId& node, const short& pin_id) {
+ VTR_ASSERT(valid_node_id(node));
+ VTR_ASSERT_MSG(node_type(node) == IPIN || node_type(node) == OPIN, "Pin number valid only for IPIN/OPIN RR nodes");
+
+ set_node_ptc_num(node, pin_id);
+}
+
+void RRGraph::set_node_track_num(const RRNodeId& node, const short& track_id) {
+ VTR_ASSERT(valid_node_id(node));
+ VTR_ASSERT_MSG(node_type(node) == CHANX || node_type(node) == CHANY, "Track number valid only for CHANX/CHANY RR nodes");
+
+ set_node_ptc_num(node, track_id);
+}
+
+void RRGraph::set_node_class_num(const RRNodeId& node, const short& class_id) {
+ VTR_ASSERT(valid_node_id(node));
+ VTR_ASSERT_MSG(node_type(node) == SOURCE || node_type(node) == SINK, "Class number valid only for SOURCE/SINK RR nodes");
+
+ set_node_ptc_num(node, class_id);
+}
+
+void RRGraph::set_node_cost_index(const RRNodeId& node, const short& cost_index) {
+ VTR_ASSERT(valid_node_id(node));
+ node_cost_indices_[node] = cost_index;
+}
+
+void RRGraph::set_node_direction(const RRNodeId& node, const e_direction& direction) {
+ VTR_ASSERT(valid_node_id(node));
+ VTR_ASSERT_MSG(node_type(node) == CHANX || node_type(node) == CHANY, "Direct can only be specified on CHANX/CNAY rr nodes");
+
+ node_directions_[node] = direction;
+}
+
+void RRGraph::set_node_side(const RRNodeId& node, const e_side& side) {
+ VTR_ASSERT(valid_node_id(node));
+ VTR_ASSERT_MSG(node_type(node) == IPIN || node_type(node) == OPIN, "Side can only be specified on IPIN/OPIN rr nodes");
+
+ node_sides_[node] = side;
+}
+
+void RRGraph::set_node_R(const RRNodeId& node, const float& R) {
+ VTR_ASSERT(valid_node_id(node));
+
+ node_Rs_[node] = R;
+}
+
+void RRGraph::set_node_C(const RRNodeId& node, const float& C) {
+ VTR_ASSERT(valid_node_id(node));
+
+ node_Cs_[node] = C;
+}
+
+/*
+ * Set a segment id for a node in rr_graph
+ */
+void RRGraph::set_node_segment(const RRNodeId& node, const RRSegmentId& segment_id) {
+ VTR_ASSERT(valid_node_id(node));
+
+ /* Only CHANX and CHANY requires a valid segment id */
+ if ((CHANX == node_type(node))
+ || (CHANY == node_type(node))) {
+ VTR_ASSERT(valid_segment_id(segment_id));
+ }
+
+ node_segments_[node] = segment_id;
+}
+
+/* For a given node in a rr_graph
+ * classify the edges of each node to be configurable (1st part) and non-configurable (2nd part)
+ */
+void RRGraph::partition_node_in_edges(const RRNodeId& node) {
+ //Partition the edges so the first set of edges are all configurable, and the later are not
+ auto first_non_config_edge = std::partition(node_in_edges_[node].begin(), node_in_edges_[node].end(),
+ [&](const RREdgeId edge) { return edge_is_configurable(edge); }); /* Condition to partition edges */
+
+ size_t num_conf_edges = std::distance(node_in_edges_[node].begin(), first_non_config_edge);
+ size_t num_non_conf_edges = node_in_edges_[node].size() - num_conf_edges; //Note we calculate using the size_t to get full range
+
+ /* Check that within allowable range (no overflow when stored as num_non_configurable_edges_
+ */
+ VTR_ASSERT_MSG(num_non_conf_edges <= node_in_edges_[node].size(),
+ "Exceeded RR node maximum number of non-configurable input edges");
+
+ node_num_non_configurable_in_edges_[node] = num_non_conf_edges; //Narrowing
+}
+
+/* For a given node in a rr_graph
+ * classify the edges of each node to be configurable (1st part) and non-configurable (2nd part)
+ */
+void RRGraph::partition_node_out_edges(const RRNodeId& node) {
+ //Partition the edges so the first set of edges are all configurable, and the later are not
+ auto first_non_config_edge = std::partition(node_out_edges_[node].begin(), node_out_edges_[node].end(),
+ [&](const RREdgeId edge) { return edge_is_configurable(edge); }); /* Condition to partition edges */
+
+ size_t num_conf_edges = std::distance(node_out_edges_[node].begin(), first_non_config_edge);
+ size_t num_non_conf_edges = node_out_edges_[node].size() - num_conf_edges; //Note we calculate using the size_t to get full range
+
+ /* Check that within allowable range (no overflow when stored as num_non_configurable_edges_
+ */
+ VTR_ASSERT_MSG(num_non_conf_edges <= node_out_edges_[node].size(),
+ "Exceeded RR node maximum number of non-configurable output edges");
+
+ node_num_non_configurable_out_edges_[node] = num_non_conf_edges; //Narrowing
+}
+
+/* For all nodes in a rr_graph
+ * classify the input edges of each node to be configurable (1st part) and non-configurable (2nd part)
+ */
+void RRGraph::partition_in_edges() {
+ /* For each node */
+ for (auto node : nodes()) {
+ this->partition_node_in_edges(node);
+ }
+}
+
+/* For all nodes in a rr_graph
+ * classify the output edges of each node to be configurable (1st part) and non-configurable (2nd part)
+ */
+void RRGraph::partition_out_edges() {
+ /* For each node */
+ for (auto node : nodes()) {
+ this->partition_node_out_edges(node);
+ }
+}
+
+/* For all nodes in a rr_graph
+ * classify both input and output edges of each node
+ * to be configurable (1st part) and non-configurable (2nd part)
+ */
+void RRGraph::partition_edges() {
+ /* Partition input edges */
+ this->partition_in_edges();
+ /* Partition output edges */
+ this->partition_out_edges();
+}
+
+void RRGraph::build_fast_node_lookup() const {
+ invalidate_fast_node_lookup();
+
+ for (auto node : nodes()) {
+ size_t x = node_xlow(node);
+ if (x >= node_lookup_.size()) {
+ node_lookup_.resize(x + 1);
+ }
+
+ size_t y = node_ylow(node);
+ if (y >= node_lookup_[x].size()) {
+ node_lookup_[x].resize(y + 1);
+ }
+
+ size_t itype = node_type(node);
+ if (itype >= node_lookup_[x][y].size()) {
+ node_lookup_[x][y].resize(itype + 1);
+ }
+
+ size_t ptc = node_ptc_num(node);
+ if (ptc >= node_lookup_[x][y][itype].size()) {
+ node_lookup_[x][y][itype].resize(ptc + 1);
+ }
+
+ size_t iside = -1;
+ if (node_type(node) == OPIN || node_type(node) == IPIN) {
+ iside = node_side(node);
+ } else {
+ iside = NUM_SIDES;
+ }
+
+ if (iside >= node_lookup_[x][y][itype][ptc].size()) {
+ node_lookup_[x][y][itype][ptc].resize(iside + 1);
+ }
+
+ //Save node in lookup
+ node_lookup_[x][y][itype][ptc][iside] = node;
+ }
+}
+
+void RRGraph::invalidate_fast_node_lookup() const {
+ node_lookup_.clear();
+}
+
+bool RRGraph::valid_fast_node_lookup() const {
+ return !node_lookup_.empty();
+}
+
+void RRGraph::initialize_fast_node_lookup() const {
+ if (!valid_fast_node_lookup()) {
+ build_fast_node_lookup();
+ }
+}
+
+bool RRGraph::valid_node_id(const RRNodeId& node) const {
+ return size_t(node) < node_ids_.size() && node_ids_[node] == node;
+}
+
+bool RRGraph::valid_edge_id(const RREdgeId& edge) const {
+ return size_t(edge) < edge_ids_.size() && edge_ids_[edge] == edge;
+}
+
+/* check if a given switch id is valid or not */
+bool RRGraph::valid_switch_id(const RRSwitchId& switch_id) const {
+ /* TODO: should we check the index of switch[id] matches ? */
+ return size_t(switch_id) < switches_.size();
+}
+
+/* check if a given segment id is valid or not */
+bool RRGraph::valid_segment_id(const RRSegmentId& segment_id) const {
+ /* TODO: should we check the index of segment[id] matches ? */
+ return size_t(segment_id) < segments_.size();
+}
+
+/**
+ * Internal checking codes to ensure data consistency
+ * If you add any internal data to RRGraph and update create_node/edge etc.
+ * you need to update the validate_sizes() here to make sure these
+ * internal vectors are aligned to the id vectors
+ */
+bool RRGraph::validate_sizes() const {
+ return validate_node_sizes()
+ && validate_edge_sizes()
+ && validate_switch_sizes()
+ && validate_segment_sizes();
+}
+
+bool RRGraph::validate_node_sizes() const {
+ return node_types_.size() == node_ids_.size()
+ && node_bounding_boxes_.size() == node_ids_.size()
+ && node_capacities_.size() == node_ids_.size()
+ && node_ptc_nums_.size() == node_ids_.size()
+ && node_cost_indices_.size() == node_ids_.size()
+ && node_directions_.size() == node_ids_.size()
+ && node_sides_.size() == node_ids_.size()
+ && node_Rs_.size() == node_ids_.size()
+ && node_Cs_.size() == node_ids_.size()
+ && node_segments_.size() == node_ids_.size()
+ && node_num_non_configurable_in_edges_.size() == node_ids_.size()
+ && node_num_non_configurable_out_edges_.size() == node_ids_.size()
+ && node_in_edges_.size() == node_ids_.size()
+ && node_out_edges_.size() == node_ids_.size();
+}
+
+bool RRGraph::validate_edge_sizes() const {
+ return edge_src_nodes_.size() == edge_ids_.size()
+ && edge_sink_nodes_.size() == edge_ids_.size()
+ && edge_switches_.size() == edge_ids_.size();
+}
+
+bool RRGraph::validate_switch_sizes() const {
+ return switches_.size() == switch_ids_.size();
+}
+
+bool RRGraph::validate_segment_sizes() const {
+ return segments_.size() == segment_ids_.size();
+}
+
+void RRGraph::compress() {
+ vtr::vector<RRNodeId, RRNodeId> node_id_map(node_ids_.size());
+ vtr::vector<RREdgeId, RREdgeId> edge_id_map(edge_ids_.size());
+
+ build_id_maps(node_id_map, edge_id_map);
+
+ clean_nodes(node_id_map);
+ clean_edges(edge_id_map);
+
+ rebuild_node_refs(edge_id_map);
+
+ invalidate_fast_node_lookup();
+
+ clear_dirty();
+}
+
+void RRGraph::build_id_maps(vtr::vector<RRNodeId, RRNodeId>& node_id_map,
+ vtr::vector<RREdgeId, RREdgeId>& edge_id_map) {
+ node_id_map = compress_ids(node_ids_);
+ edge_id_map = compress_ids(edge_ids_);
+}
+
+void RRGraph::clean_nodes(const vtr::vector<RRNodeId, RRNodeId>& node_id_map) {
+ node_ids_ = clean_and_reorder_ids(node_id_map);
+
+ node_types_ = clean_and_reorder_values(node_types_, node_id_map);
+
+ node_bounding_boxes_ = clean_and_reorder_values(node_bounding_boxes_, node_id_map);
+
+ node_capacities_ = clean_and_reorder_values(node_capacities_, node_id_map);
+ node_ptc_nums_ = clean_and_reorder_values(node_ptc_nums_, node_id_map);
+ node_cost_indices_ = clean_and_reorder_values(node_cost_indices_, node_id_map);
+ node_directions_ = clean_and_reorder_values(node_directions_, node_id_map);
+ node_sides_ = clean_and_reorder_values(node_sides_, node_id_map);
+ node_Rs_ = clean_and_reorder_values(node_Rs_, node_id_map);
+ node_Cs_ = clean_and_reorder_values(node_Cs_, node_id_map);
+
+ VTR_ASSERT(validate_node_sizes());
+
+ VTR_ASSERT_MSG(are_contiguous(node_ids_), "Ids should be contiguous");
+ VTR_ASSERT_MSG(all_valid(node_ids_), "All Ids should be valid");
+}
+
+void RRGraph::clean_edges(const vtr::vector<RREdgeId, RREdgeId>& edge_id_map) {
+ edge_ids_ = clean_and_reorder_ids(edge_id_map);
+
+ edge_src_nodes_ = clean_and_reorder_values(edge_src_nodes_, edge_id_map);
+ edge_sink_nodes_ = clean_and_reorder_values(edge_sink_nodes_, edge_id_map);
+ edge_switches_ = clean_and_reorder_values(edge_switches_, edge_id_map);
+
+ VTR_ASSERT(validate_edge_sizes());
+
+ VTR_ASSERT_MSG(are_contiguous(edge_ids_), "Ids should be contiguous");
+ VTR_ASSERT_MSG(all_valid(edge_ids_), "All Ids should be valid");
+}
+
+void RRGraph::rebuild_node_refs(const vtr::vector<RREdgeId, RREdgeId>& edge_id_map) {
+ for (const auto& node : nodes()) {
+ node_in_edges_[node] = update_valid_refs(node_in_edges_[node], edge_id_map);
+ node_out_edges_[node] = update_valid_refs(node_out_edges_[node], edge_id_map);
+
+ VTR_ASSERT_MSG(all_valid(node_in_edges_[node]), "All Ids should be valid");
+ VTR_ASSERT_MSG(all_valid(node_out_edges_[node]), "All Ids should be valid");
+ }
+}
+
+/* Empty all the vectors related to nodes */
+void RRGraph::clear_nodes() {
+ node_ids_.clear();
+
+ node_types_.clear();
+ node_bounding_boxes_.clear();
+
+ node_capacities_.clear();
+ node_ptc_nums_.clear();
+ node_cost_indices_.clear();
+ node_directions_.clear();
+ node_sides_.clear();
+ node_Rs_.clear();
+ node_Cs_.clear();
+ node_segments_.clear();
+
+ node_num_non_configurable_in_edges_.clear();
+ node_num_non_configurable_out_edges_.clear();
+
+ node_in_edges_.clear();
+ node_out_edges_.clear();
+
+ /* clean node_look_up */
+ node_lookup_.clear();
+}
+
+/* Empty all the vectors related to edges */
+void RRGraph::clear_edges() {
+ edge_ids_.clear();
+ edge_src_nodes_.clear();
+ edge_sink_nodes_.clear();
+ edge_switches_.clear();
+}
+
+/* Empty all the vectors related to switches */
+void RRGraph::clear_switches() {
+ switch_ids_.clear();
+ switches_.clear();
+}
+
+/* Empty all the vectors related to segments */
+void RRGraph::clear_segments() {
+ segment_ids_.clear();
+ segments_.clear();
+}
+
+/* Clean the rr_graph */
+void RRGraph::clear() {
+ clear_nodes();
+ clear_edges();
+ clear_switches();
+ clear_segments();
+}
diff --git a/vpr/src/device/rr_graph_obj.h b/vpr/src/device/rr_graph_obj.h
new file mode 100644
index 0000000..f34b111
--- /dev/null
+++ b/vpr/src/device/rr_graph_obj.h
@@ -0,0 +1,843 @@
+/************************************************************************
+ * This file introduces a class to model a Routing Resource Graph (RRGraph or RRG)
+ * which is widely used by placers, routers, analyzers etc.
+ *
+ * Overview
+ * ========
+ * RRGraph aims to describe in a general way how routing resources are connected
+ * in a FPGA fabric.
+ * It includes device-level information for routing resources,
+ * such as the physical location of nodes,
+ * routing segment information of each routing resource
+ * switch information of each routing resource.
+ *
+ * A Routing Resource Graph (RRGraph or RRG) is a directed graph (has many cycles),
+ * which consists of a number of nodes and edges.
+ *
+ * Node
+ * ----
+ * Each node represents a routing resource, which could be
+ * 1. a routing track in X-direction or Y-direction (CHANX or CHANY)
+ * 2. an input or an output of a logic block (IPIN or OPIN)
+ * 3. a virtual source or sink node (SOURCE or SINK), which are starting/ending points of routing trees.
+ *
+ * Edge
+ * ----
+ * Each edge represents a switch between routing resources, which could be
+ * 1. a multiplexer
+ * 2. a tri-state buffer
+ * 3. a pass gate
+ * 4. a non-configurable (can not be turned off) buffer
+ * 5. a short (metal connection that can not be turned off
+ *
+ * Note: Multiplexers are the most common type
+ *
+ * The switch information are categorized in the rr_switch_inf of RRGraph class.
+ * rr_switch_inf is created to minimize memory footprint of RRGraph classs
+ * While the RRG could contain millions (even much larger) of edges, there are only
+ * a limited number of types of switches.
+ * Hence, we use a flyweight pattern to store switch-related information that differs
+ * only for types of switches (switch type, drive strength, R, C, etc.).
+ * Each edge stores the ids of the switch that implements it so this additional information
+ * can be easily looked up.
+ *
+ * Note: All the switch-related information, such as R, C, should be placed in rr_switch_inf
+ * but NOT directly in the edge-related data of RRGraph.
+ * If you wish to create a new data structure to represent switches between routing resources,
+ * please follow the flyweight pattern by linking your switch ids to edges only!
+ *
+ * Guidlines on using the RRGraph data structure
+ * =============================================
+ *
+ * For those want to access data from RRGraph
+ * ------------------------------------------
+ * Some examples for most frequent data query:
+ *
+ * // Strongly suggest to use a read-only rr_graph object
+ * const RRGraph& rr_graph;
+ *
+ * // Access type of a node with a given node id
+ * // Get the unique node id that you may get
+ * // from other data structures or functions
+ * RRNodeId node_id;
+ * t_rr_type node_type = rr_graph.node_type(node_id);
+ *
+ * // Access all the fan-out edges from a given node
+ * for (const RREdgeId& out_edge_id : rr_graph.node_out_edges(node_id)) {
+ * // Do something with out_edge
+ * }
+ * // If you only want to learn the number of fan-out edges
+ * size_t num_out_edges = rr_graph.node_fan_out(node_id);
+ *
+ * // Access all the switches connected to a given node
+ * for (const RREdgeId& in_edge_id : rr_graph.node_in_edges(node_id)) {
+ * RRSwitchId edge_switch_id = rr_graph.edge_switch(in_edge_id);
+ * // Do something with the switch
+ * }
+ *
+ * Please refer to the detailed comments on each public accessors
+ *
+ * For those want to build/modify a RRGraph
+ * -----------------------------------------
+ * Do NOT add a builder to this data structure!
+ * Builders should be kept as free functions that use the public mutators
+ * We suggest developers to create builders in separated C/C++ source files
+ * outside the rr_graph header and source files
+ *
+ * After build/modify a RRGraph, please do run a fundamental check, a public accessor.
+ * to ensure that your RRGraph does not include invalid nodes/edges/switches/segements
+ * as well as connections.
+ * The validate() function gurantees the consistency between internal data structures,
+ * such as the id cross-reference between nodes and edges etc.,
+ * so failing it indicates a fatal bug!
+ * This is a must-do check!
+ *
+ * Example:
+ * RRGraph rr_graph;
+ * ... // Building RRGraph
+ * rr_graph.validate();
+ *
+ * Optionally, we strongly recommend developers to run an advance check in check_rr_graph()
+ * This guarantees legal and routable RRGraph for VPR routers.
+ *
+ * This checks for connectivity or other information in the RRGraph that is unexpected
+ * or unusual in an FPGA, and likely indicates a problem in your graph generation.
+ * However, if you are intentionally creating an RRGraph with this unusual,
+ * buts still technically legal, behaviour, you can write your own check_rr_graph() with weaker assumptions.
+ *
+ * Note: Do NOT modify the coordinate system for nodes, they are designed for downstream drawers and routers
+ *
+ * For those want to extend RRGraph data structure
+ * --------------------------------------------------------------------------
+ * Please avoid modifying any existing public/private accessors/mutators
+ * in order to keep a stable RRGraph object in the framework
+ * Developers may add more internal data to RRGraph as well as associate accessors/mutators
+ * Please update and comment on the added features properly to keep this data structure friendly to be extended.
+ *
+ * Try to keep your extension within only graph-related internal data to RRGraph.
+ * In other words, extension is necessary when the new node/edge attributes are needed.
+ * RRGraph should NOT include other data which are shared by other data structures outside.
+ * The rr-graph is the single largest data structure in VPR,
+ * so avoid adding unnecessary information per node or per edge to it, as it will impact memory footprint.
+ * Instead, using indices to point to the outside data source instead of embedding to RRGraph
+ * For example:
+ * For any placement/routing cost related information, try to extend t_rr_indexed_data, but not RRGraph
+ * For any placement/routing results, try to extend PlaceContext and RoutingContext, but not RRGraph
+ *
+ * For those want to develop placers or routers
+ * --------------------------------------------------------------------------
+ * The RRGraph is designed to be a read-only database/graph, once created.
+ * Placement and routing should NOT change any attributes of RRGraph.
+ * Any placement and routing results should be stored in other data structures, such as PlaceContext and RoutingContext.
+ *
+ * Tracing Cross-Reference
+ * =======================
+ * RRGraph is designed to a self-contained data structure as much as possible.
+ * It includes the switch information (rr_switch) and segment_information (rr_segment)
+ * which are necessary to build-up any external data structures.
+ *
+ * Internal cross-reference
+ * ------------------------
+ *
+ * +--------+ +--------+
+ * | | node_in_edges | |
+ * | | node_out_edges | |
+ * | Node |----------------->| Edge |--+
+ * | |<-----------------| | |
+ * | | edge_src_node | | |
+ * +--------+ edge_sink_node +--------+ |edge_switch
+ * | |
+ * | node_segment |
+ * v v
+ * +------------+ +----------+
+ * | | | |
+ * | | | |
+ * | Segments | | Switch |
+ * | | | |
+ * | | | |
+ * +------------+ +----------+
+ *
+ *
+ * External cross-reference
+ * ------------------------
+ * The only cross-reference to outside data structures is the cost_index
+ * corresponding to the data structure t_rr_index_data
+ * Details can be found in the definition of t_rr_index_data
+ * This allows rapid look up by the router of additional information it needs for this node, using a flyweight pattern.
+ *
+ * +---------+ cost_index +------------------------------+
+ * | RRGraph |-------------->| cost_index_data[cost_index] |
+ * +---------+ +------------------------------+
+ *
+ * Note: if you wish to use a customized routing-cost data structure,
+ * please use the flyweigth pattern as we do for t_rr_index_data!
+ *
+ * Access to a node/edge/switch/segment, please use the StrongId created
+ * ---------------------------------------------------------------------
+ * For node, use RRNodeId
+ * For edge, use RREdgeId
+ * For switch, use RRSwitchId
+ * For segment, use RRSegmentId
+ *
+ * These are the unique identifier for each data type.
+ * To check if your id is valid or not, use the INVALID() function of StrongId class.
+ * Example:
+ * if (node_id == RRNodeId::INVALID()) {
+ * }
+ *
+ ***********************************************************************/
+#ifndef RR_GRAPH_OBJ_H
+#define RR_GRAPH_OBJ_H
+
+/*
+ * Notes in include header files in a head file
+ * Only include the neccessary header files
+ * that is required by the data types in the function/class declarations!
+ */
+/* Header files should be included in a sequence */
+/* Standard header files required go first */
+#include <limits>
+#include <vector>
+
+/* EXTERNAL library header files go second*/
+#include "vtr_vector.h"
+#include "vtr_range.h"
+#include "vtr_geometry.h"
+#include "arch_types.h"
+
+/* VPR header files go third */
+#include "vpr_types.h"
+#include "rr_graph_fwd.h"
+
+class RRGraph {
+ public: /* Types */
+ /* Iterators used to create iterator-based loop for nodes/edges/switches/segments */
+ typedef vtr::vector<RRNodeId, RRNodeId>::const_iterator node_iterator;
+ typedef vtr::vector<RREdgeId, RREdgeId>::const_iterator edge_iterator;
+ typedef vtr::vector<RRSwitchId, RRSwitchId>::const_iterator switch_iterator;
+ typedef vtr::vector<RRSegmentId, RRSegmentId>::const_iterator segment_iterator;
+
+ /* Ranges used to create range-based loop for nodes/edges/switches/segments */
+ typedef vtr::Range<node_iterator> node_range;
+ typedef vtr::Range<edge_iterator> edge_range;
+ typedef vtr::Range<switch_iterator> switch_range;
+ typedef vtr::Range<segment_iterator> segment_range;
+
+ public: /* Accessors */
+ /* Aggregates: create range-based loops for nodes/edges/switches/segments
+ * To iterate over the nodes/edges/switches/segments in a RRGraph,
+ * using a range-based loop is suggested.
+ * -----------------------------------------------------------------
+ * Example: iterate over all the nodes
+ * // Strongly suggest to use a read-only rr_graph object
+ * const RRGraph& rr_graph;
+ * for (const RRNodeId& node : rr_graph.nodes()) {
+ * // Do something with each node
+ * }
+ *
+ * for (const RREdgeId& edge : rr_graph.edges()) {
+ * // Do something with each edge
+ * }
+ *
+ * for (const RRSwitchId& switch : rr_graph.switches()) {
+ * // Do something with each switch
+ * }
+ *
+ * for (const RRSegmentId& segment : rr_graph.segments()) {
+ * // Do something with each segment
+ * }
+ */
+ node_range nodes() const;
+ edge_range edges() const;
+ switch_range switches() const;
+ segment_range segments() const;
+
+ /* Node-level attributes */
+ size_t node_index(const RRNodeId& node) const; /* TODO: deprecate this accessor as outside functions should use RRNodeId */
+
+ /* get the type of a RRGraph node : types of each node, can be channel wires (CHANX or CHANY) or
+ * logic block pins(OPIN or IPIN) or virtual nodes (SOURCE or SINK)
+ * see t_rr_type definition for more details
+ */
+ t_rr_type node_type(const RRNodeId& node) const;
+
+ /* Get coordinate of a node. (xlow, xhigh, ylow, yhigh):
+ * For OPIN/IPIN/SOURCE/SINK, xlow = xhigh and ylow = yhigh
+ * This is still the case when a logic block has a height > 1
+ * For CHANX/CHANY, (xlow, ylow) and (xhigh, yhigh) represent
+ * where the routing segment starts and ends.
+ * Note that our convention alway keeps
+ * xlow <= xhigh and ylow <= yhigh
+ * Therefore, (xlow, ylow) is a starting point for a CHANX/CHANY in INC_DIRECTION
+ * (xhigh, yhigh) is a starting point for a CHANX/CHANY in DEC_DIRECTION
+ *
+ * Note: there is only a single drive point for each routing segment (track)
+ * in the context of uni-directional wires
+ *
+ * Example :
+ * CHANX in INC_DIRECTION
+ * (xlow, ylow) (xhigh, yhigh)
+ * | |
+ * \|/ \|/
+ * ---------------------------->
+ *
+ * CHANX in DEC_DIRECTION
+ * (xlow, ylow) (xhigh, yhigh)
+ * | |
+ * \|/ \|/
+ * <----------------------------
+ *
+ * CHANY in INC_DIRECTION
+ *
+ * /|\ <-------(xhigh, yhigh)
+ * |
+ * | <-------(xlow, ylow)
+ *
+ * CHANY in DEC_DIRECTION
+ *
+ * | <-------(xhigh, yhigh)
+ * |
+ * \|/ <-------(xlow, ylow)
+ */
+ short node_xlow(const RRNodeId& node) const;
+ short node_ylow(const RRNodeId& node) const;
+ short node_xhigh(const RRNodeId& node) const;
+ short node_yhigh(const RRNodeId& node) const;
+
+ /* Get the length of a routing track.
+ * Note that it is ONLY meaningful for CHANX and CHANY, which represents the number of logic blocks that a routing track spans
+ * For nodes that are OPIN/IPIN/SOURCE/SINK, the length is supposed to be always 0
+ */
+ short node_length(const RRNodeId& node) const;
+
+ /* A short-cut function to get coordinates of a node,
+ * where xmin of vtr::Rect = xlow,
+ * ymin of vtr::Rect = ylow,
+ * xmax of vtr::Rect = xhigh,
+ * ymax of vtr::Rect = yhigh.
+ */
+ vtr::Rect<short> node_bounding_box(const RRNodeId& node) const;
+
+ /* Get node starting and ending points in routing channels.
+ * See details in the figures for node_xlow(), node_ylow(), node_xhigh() and node_yhigh()
+ * For routing tracks in INC_DIRECTION:
+ * node_start_coordinate() returns (xlow, ylow) as the starting point
+ * node_end_coordinate() returns (xhigh, yhigh) as the ending point
+ *
+ * For routing tracks in DEC_DIRECTION:
+ * node_start_coordinate() returns (xhigh, yhigh) as the starting point
+ * node_end_coordinate() returns (xlow, ylow) as the ending point
+ *
+ * For routing tracks in BI_DIRECTION:
+ * node_start_coordinate() returns (xlow, ylow) as the starting point
+ * node_end_coordinate() returns (xhigh, yhigh) as the ending point
+ *
+ * Applicable to routing track nodes only!!!
+ * This function will requires the types of node to be either CHANX or CHANY
+ */
+ vtr::Point<short> node_start_coordinate(const RRNodeId& node) const;
+ vtr::Point<short> node_end_coordinate(const RRNodeId& node) const;
+
+ /* Get the capacity of a node.
+ * Literally, how many nets can be mapped to the node.
+ * Typically, each node has a capacity of 1 but special nodes (SOURCE and SINK) will have a
+ * large number due to logic equivalent pins
+ * See Vaughn Betz's book for more details
+ */
+ short node_capacity(const RRNodeId& node) const;
+
+ /* Get the number of edges that drives a given node
+ * Note that each edge is typically driven by a node
+ * (true in VPR RRG that is currently supported, may not be true in customized RRG)
+ * This can also represent the number of drive nodes
+ * An example where fan-in of a node C is 2
+ *
+ * edge A
+ * node A -------->+
+ * |
+ * |-->node C
+ * edgeB |
+ * node B -------->+
+ *
+ */
+ short node_fan_in(const RRNodeId& node) const;
+
+ /* Get the number of edges that are driven a given node
+ * Note that each edge typically drives by a node
+ * (true in VPR RRG that is currently supported, may not be true in customized RRG)
+ * This can also represent the number of fan-out nodes
+ * An example where fan-out of a node A is 2
+ *
+ * edge A
+ * node A -+--------> node B
+ * |
+ * |
+ * | edgeB
+ * +--------> node C
+ *
+ */
+ short node_fan_out(const RRNodeId& node) const;
+
+ /* Get the ptc_num of a node
+ * The ptc (pin, track, or class) number is an integer
+ * that allows you to differentiate between wires, pins or sources/sinks with overlapping x,y coordinates or extent.
+ * This is useful for drawing rr-graphs nicely.
+ * For example, all the CHANX rr_nodes that have the same y coordinate and x-coordinates
+ * that overlap will have different ptc numbers, by convention starting at 0.
+ * This allows them to be drawn without overlapping, as the ptc num can be used as a track identifier.
+ * The main routing code does not care about ptc num.
+ *
+ * The ptc_num carries different meanings for different node types
+ * (true in VPR RRG that is currently supported, may not be true in customized RRG)
+ * CHANX or CHANY: the track id in routing channels
+ * OPIN or IPIN: the index of pins in the logic block data structure
+ * SOURCE and SINK: the class id of a pin (indicating logic equivalence of pins) in the logic block data structure
+ *
+ * To ease the access to ptc_num for different types of nodes:
+ * node_pin_num() is designed for logic blocks, which are IPIN and OPIN nodes
+ * node_track_num() is designed for routing tracks, which are CHANX and CHANY nodes
+ * node_class_num() is designed for routing source and sinks, which are SOURCE and SINK nodes
+ *
+ * Due to a useful identifier, ptc_num is used in building fast look-up
+ */
+ short node_ptc_num(const RRNodeId& node) const;
+ short node_pin_num(const RRNodeId& node) const;
+ short node_track_num(const RRNodeId& node) const;
+ short node_class_num(const RRNodeId& node) const;
+
+ /* Get the index of cost data in the list of cost_indexed_data data structure
+ * It contains the routing cost for different nodes in the RRGraph
+ * when used in evaluate different routing paths
+ * See cross-reference section in this header file for more details
+ */
+ short node_cost_index(const RRNodeId& node) const;
+
+ /* Get the directionality of a node
+ * see node coordinate for details
+ * only matters the routing track nodes (CHANX and CHANY)
+ */
+ e_direction node_direction(const RRNodeId& node) const;
+
+ /* Get the side where the node physically locates on a logic block.
+ * Mainly applicable to IPIN and OPIN nodes, which locates on the perimeter of logic block
+ * The side should be consistent to <pinlocation> definition in architecture XML
+ *
+ * TOP
+ * +-----------+
+ * | |
+ * LEFT | Logic | RIGHT
+ * | Block |
+ * | |
+ * +-----------+
+ * BOTTOM
+ *
+ */
+ e_side node_side(const RRNodeId& node) const;
+
+ /* Get resistance of a node, used to built RC tree for timing analysis */
+ float node_R(const RRNodeId& node) const;
+
+ /* Get capacitance of a node, used to built RC tree for timing analysis */
+ float node_C(const RRNodeId& node) const;
+
+ /* Get segment id of a node, containing the information of the routing
+ * segment that the node represents. See more details in the data structure t_segment_inf
+ */
+ RRSegmentId node_segment(const RRNodeId& node) const;
+
+ /* Get the number of non-configurable incoming edges to a node */
+ short node_num_configurable_in_edges(const RRNodeId& node) const;
+
+ /* Get the number of non-configurable outgoing edges from a node */
+ short node_num_non_configurable_in_edges(const RRNodeId& node) const;
+
+ /* Get the number of configurable output edges of a node */
+ short node_num_configurable_out_edges(const RRNodeId& node) const;
+
+ /* Get the number of non-configurable output edges of a node */
+ short node_num_non_configurable_out_edges(const RRNodeId& node) const;
+
+ /* Get the range (list) of edges related to a given node */
+ edge_range node_configurable_in_edges(const RRNodeId& node) const;
+ edge_range node_non_configurable_in_edges(const RRNodeId& node) const;
+ edge_range node_configurable_out_edges(const RRNodeId& node) const;
+ edge_range node_non_configurable_out_edges(const RRNodeId& node) const;
+
+ /* Get a list of edge ids, which are incoming edges to a node */
+ edge_range node_in_edges(const RRNodeId& node) const;
+
+ /* Get a list of edge ids, which are outgoing edges from a node */
+ edge_range node_out_edges(const RRNodeId& node) const;
+
+ /* Edge-related attributes
+ * An example to explain the terminology used in RRGraph
+ * edgeA
+ * nodeA --------> nodeB
+ * | edgeB
+ * +-------> nodeC
+ *
+ * +----------+----------------+----------------+
+ * | Edge Id | edge_src_node | edge_sink_node |
+ * +----------+----------------+----------------+
+ * | edgeA | nodeA | nodeB |
+ * +----------+----------------+----------------+
+ * | edgeB | nodeA | nodeC |
+ * +----------+----------------+----------------+
+ *
+ */
+ size_t edge_index(const RREdgeId& edge) const; /* TODO: deprecate this accessor as outside functions should use RREdgeId */
+ /* Get the source node which drives a edge */
+ RRNodeId edge_src_node(const RREdgeId& edge) const;
+ /* Get the sink node which a edge ends to */
+ RRNodeId edge_sink_node(const RREdgeId& edge) const;
+ /* Get the switch id which a edge represents
+ * using switch id, timing and other information can be found
+ * for any node-to-node connection
+ */
+ RRSwitchId edge_switch(const RREdgeId& edge) const;
+ /* Judge if a edge is configurable or not.
+ * A configurable edge is controlled by a programmable memory bit
+ * while a non-configurable edge is typically a hard-wired connection
+ */
+ bool edge_is_configurable(const RREdgeId& edge) const;
+ bool edge_is_non_configurable(const RREdgeId& edge) const;
+
+ /* Switch Info */
+ size_t switch_index(const RRSwitchId& switch_id) const; /* TODO: deprecate this accessor as outside functions should use RRSwitchId */
+ /* Get the switch info of a switch used in this RRGraph */
+ const t_rr_switch_inf& get_switch(const RRSwitchId& switch_id) const;
+
+ /* Segment Info */
+ size_t segment_index(const RRSegmentId& segment_id) const; /* TODO: deprecate this accessor as outside functions should use RRSegmentId */
+ /* Get the segment info of a routing segment used in this RRGraph */
+ const t_segment_inf& get_segment(const RRSegmentId& segment_id) const;
+
+ /* Utilities */
+ /* Find the edges connecting two nodes */
+ std::vector<RREdgeId> find_edges(const RRNodeId& src_node, const RRNodeId& sink_node) const;
+ /* Find a node with given features from internal fast look-up */
+ RRNodeId find_node(const short& x, const short& y, const t_rr_type& type, const int& ptc, const e_side& side = NUM_SIDES) const;
+ /* Find the number of routing tracks in a routing channel with a given coordinate */
+ short chan_num_tracks(const short& x, const short& y, const t_rr_type& type) const;
+
+ /* This flag is raised when the RRgraph contains invalid nodes/edges etc.
+ * Invalid nodes/edges exist when users remove nodes/edges from RRGraph
+ * RRGraph object will not immediately remove the nodes and edges but
+ * will mark them with invalid ids.
+ * Afterwards the is_dirty flag is raised as an indicator, to tell users
+ * that a clean-up process (invoked by compress() function)is required.
+ * After executing compress(), the is_dirty will be reset to false
+ *
+ * Example:
+ * RRGraph rr_graph;
+ * RRNodeId node_id; // Node id to be removed
+ * rr_graph.remove_node(node_id);
+ * // RRGraph is now dirty (rr_graph.is_dirty() == true)
+ * ...
+ * // During this period, when you perform data query,
+ * // You may encounter invalid nodes and edges
+ * // It may happen that
+ * // 1. their ids are invalid
+ * // 2. the cross-reference between nodes and edge, i.e.,
+ * // node_in_edges(), node_out_edges()
+ * // 3. invalid node returned from find_node(), which use fast look-up
+ * ...
+ * rr_graph.compress();
+ * // RRGraph is now clean (rr_graph.is_dirty() == false)
+ */
+ bool is_dirty() const;
+
+ public: /* Echos */
+ void print_node(const RRNodeId& node) const; /* Print the detailed information of a node */
+
+ public: /* Public Validators */
+ /* Check data structure for internal consistency
+ * This function will
+ * 1. re-build fast look-up for nodes
+ * 2. check all the edges and nodes are connected
+ * Literally, no invalid ids in fan-in/fan-out of edges/nodes
+ * 3. check that all the nodes representing routing tracks have valid id linked to its segment-related data structure
+ * 4. check that all the edges have valid id linked to its switch-related data structure
+ *
+ * Any valid and non-dirty RRGraph should pass this check
+ * It is highly recommended to run this function after building any RRGraph object
+ */
+ bool validate() const;
+
+ /* Validate is the node id does exist in the RRGraph */
+ bool valid_node_id(const RRNodeId& node) const;
+
+ /* Validate is the edge id does exist in the RRGraph */
+ bool valid_edge_id(const RREdgeId& edge) const;
+
+ public: /* Mutators */
+ /* Reserve the lists of nodes, edges, switches etc. to be memory efficient.
+ * This function is mainly used to reserve memory space inside RRGraph,
+ * when adding a large number of nodes/edge/switches/segments,
+ * in order to avoid memory fragements
+ * For example:
+ * RRGraph rr_graph;
+ * // Add 1000 CHANX nodes to the RRGraph object
+ * rr_graph.reserve_nodes(1000);
+ * for (size_t i = 0; i < 1000; ++i) {
+ * rr_graph.create_node(CHANX);
+ * }
+ */
+ void reserve_nodes(const int& num_nodes);
+ void reserve_edges(const int& num_edges);
+ void reserve_switches(const int& num_switches);
+ void reserve_segments(const int& num_segments);
+
+ /* Add new elements (node, edge, switch, etc.) to RRGraph */
+ /* Add a node to the RRGraph with a deposited type
+ * Detailed node-level information should be added using the set_node_* functions
+ * For example:
+ * RRNodeId node = create_node();
+ * set_node_xlow(node, 0);
+ */
+ RRNodeId create_node(const t_rr_type& type);
+ /* Add a edge to the RRGraph, by providing the source and sink node
+ * This function will automatically create a node and
+ * configure the nodes and edges in connection
+ */
+ RREdgeId create_edge(const RRNodeId& source, const RRNodeId& sink, const RRSwitchId& switch_id);
+ RRSwitchId create_switch(const t_rr_switch_inf& switch_info);
+ RRSegmentId create_segment(const t_segment_inf& segment_info);
+
+ /* Remove elements from RRGraph
+ * This function just turn the nodes and edges to an invalid id without deletion
+ * This will cause the RRGraph to be marked as dirty (is_dirty(): false => true)
+ * To thoroughly remove the edges and nodes as well as clear the dirty flag,
+ * use compress() after the remove functions
+ * Example:
+ * RRGraph rr_graph;
+ * rr_graph.remove_node()
+ * .. // remove more nodes
+ * rr_graph.remove_edge()
+ * .. // remove more nodes
+ * // rr_graph.is_dirty() == true
+ * // If you want to access any node or edge
+ * // Check codes for ids should be intensively used
+ * // Such as,
+ * // for (const RREdgeId& in_edge : rr_graph.node_in_edges()) {
+ * // if (RREdgeId::INVALID() != in_edge) {
+ * // ...
+ * // }
+ * // }
+ * rr_graph.compress()
+ * // rr_graph.is_dirty() == false
+ */
+ void remove_node(const RRNodeId& node);
+ void remove_edge(const RREdgeId& edge);
+
+ /* Set node-level information */
+ void set_node_xlow(const RRNodeId& node, const short& xlow);
+ void set_node_ylow(const RRNodeId& node, const short& ylow);
+ void set_node_xhigh(const RRNodeId& node, const short& xhigh);
+ void set_node_yhigh(const RRNodeId& node, const short& yhigh);
+
+ /* This is a short-cut function, set xlow/xhigh/ylow/yhigh for a node
+ * Please respect the following to configure the bb object:
+ * bb.xmin = xlow, bb.ymin = ylow; bb.xmax = xhigh, bb.ymax = yhigh;
+ */
+ void set_node_bounding_box(const RRNodeId& node, const vtr::Rect<short>& bb);
+
+ void set_node_capacity(const RRNodeId& node, const short& capacity);
+
+ /* A generic function to set the ptc_num for a node */
+ void set_node_ptc_num(const RRNodeId& node, const short& ptc);
+
+ /* Only applicable to IPIN and OPIN, set the ptc_num for a node, which is the pin id in a logic block,
+ * See definition in t_type_descriptor data structure
+ */
+ void set_node_pin_num(const RRNodeId& node, const short& pin_id);
+
+ /* Only applicable to CHANX and CHANY, set the ptc_num for a node, which is the track id in a routing channel,
+ * Routing channel is a group of routing tracks, each of which has a unique index
+ * An example
+ * Routing Channel
+ * +------------------+
+ * | |
+ * ---|----------------->|----> track_id: 0
+ * | |
+ * ... More tracks ...
+ * | |
+ * ---|----------------->|----> track_id: 1
+ * | |
+ * +------------------+
+ */
+ void set_node_track_num(const RRNodeId& node, const short& track_id);
+
+ /* Only applicable to SOURCE and SINK, set the ptc_num for a node, which is the class number in a logic block,
+ * See definition in t_type_descriptor data structure
+ */
+ void set_node_class_num(const RRNodeId& node, const short& class_id);
+
+ /* Set the routing cost index for node, see node_cost_index() for details */
+ /* TODO: the cost index should be changed to a StrongId!!! */
+ void set_node_cost_index(const RRNodeId& node, const short& cost_index);
+
+ /* Set the directionality for a node, only applicable to CHANX and CHANY */
+ void set_node_direction(const RRNodeId& node, const e_direction& direction);
+
+ /* Set the side for a node, only applicable to OPIN and IPIN */
+ void set_node_side(const RRNodeId& node, const e_side& side);
+
+ /* Set the RC information for a node */
+ void set_node_R(const RRNodeId& node, const float& R);
+ void set_node_C(const RRNodeId& node, const float& C);
+
+ /* Set the routing segment linked to a node, only applicable to CHANX and CHANY */
+ void set_node_segment(const RRNodeId& node, const RRSegmentId& segment_index);
+
+ /* Edge partitioning is performed for efficiency,
+ * so we can store configurable and non-configurable edge lists for a node in one vector,
+ * and efficiently iterate over all edges, or only the configurable or non-configurable subsets.
+ * This function will re-organize the incoming and outgoing edges of each node,
+ * i.e., node_in_edges() and node_out_edges():
+ * 1. configurable edges (1st part of the vectors)
+ * 2. non-configurable edges (2nd part of the vectors)
+ */
+ void partition_edges();
+
+ /* Graph-level Clean-up, remove invalid nodes/edges etc.
+ * This will clear the dirty flag (query by is_dirty()) of RRGraph object, if it was set
+ */
+ void compress();
+
+ /* top-level function to free, should be called when to delete a RRGraph */
+ void clear();
+
+ private: /* Internal Mutators to perform edge partitioning */
+ /* classify the input edges of each node to be configurable (1st part) and non-configurable (2nd part) */
+ void partition_node_in_edges(const RRNodeId& node);
+
+ /* classify the output edges of each node to be configurable (1st part) and non-configurable (2nd part) */
+ void partition_node_out_edges(const RRNodeId& node);
+
+ /* classify the input edges of each node to be configurable (1st part) and non-configurable (2nd part) */
+ void partition_in_edges();
+
+ /* classify the output edges of each node to be configurable (1st part) and non-configurable (2nd part) */
+ void partition_out_edges();
+
+ private: /* Internal free functions */
+ void clear_nodes();
+ void clear_edges();
+ void clear_switches();
+ void clear_segments();
+
+ private: /* Graph Compression related */
+ void build_id_maps(vtr::vector<RRNodeId, RRNodeId>& node_id_map,
+ vtr::vector<RREdgeId, RREdgeId>& edge_id_map);
+ void clean_nodes(const vtr::vector<RRNodeId, RRNodeId>& node_id_map);
+ void clean_edges(const vtr::vector<RREdgeId, RREdgeId>& edge_id_map);
+ void rebuild_node_refs(const vtr::vector<RREdgeId, RREdgeId>& edge_id_map);
+
+ void set_dirty();
+ void clear_dirty();
+
+ private: /* Internal validators and builders */
+ /* Fast look-up builders and validators */
+ void build_fast_node_lookup() const;
+ void invalidate_fast_node_lookup() const;
+ bool valid_fast_node_lookup() const;
+ void initialize_fast_node_lookup() const;
+
+ /* Graph property Validation */
+ bool validate_sizes() const;
+ bool validate_node_sizes() const;
+ bool validate_edge_sizes() const;
+ bool validate_switch_sizes() const;
+ bool validate_segment_sizes() const;
+
+ bool validate_invariants() const;
+ bool validate_unique_edges_invariant() const;
+
+ bool validate_crossrefs() const;
+ bool validate_node_edge_crossrefs() const;
+
+ /* Node-level validators */
+ bool validate_node_segment(const RRNodeId& node) const;
+ bool validate_node_in_edges(const RRNodeId& node) const;
+ bool validate_node_out_edges(const RRNodeId& node) const;
+ bool validate_node_edges(const RRNodeId& node) const;
+
+ /* Edge-level checking */
+ bool validate_node_is_edge_src(const RRNodeId& node, const RREdgeId& edge) const;
+ bool validate_node_is_edge_sink(const RRNodeId& node, const RREdgeId& edge) const;
+ bool validate_edge_switch(const RREdgeId& edge) const;
+ bool validate_edge_src_node(const RREdgeId& edge) const;
+ bool validate_edge_sink_node(const RREdgeId& edge) const;
+
+ /* List-level checking */
+ bool validate_nodes_in_edges() const;
+ bool validate_nodes_out_edges() const;
+ bool validate_nodes_edges() const;
+ bool validate_node_segments() const;
+ bool validate_edge_switches() const;
+ bool validate_edge_src_nodes() const;
+ bool validate_edge_sink_nodes() const;
+
+ /* Validate switch list */
+ bool valid_switch_id(const RRSwitchId& switch_id) const;
+
+ /* Validate segment list */
+ bool valid_segment_id(const RRSegmentId& segment_id) const;
+
+ private: /* Internal Data */
+ /* Node related data */
+ vtr::vector<RRNodeId, RRNodeId> node_ids_; /* Unique identifiers for the nodes */
+ vtr::vector<RRNodeId, t_rr_type> node_types_;
+
+ vtr::vector<RRNodeId, vtr::Rect<short>> node_bounding_boxes_;
+
+ vtr::vector<RRNodeId, short> node_capacities_;
+ vtr::vector<RRNodeId, short> node_ptc_nums_;
+ vtr::vector<RRNodeId, short> node_cost_indices_;
+ vtr::vector<RRNodeId, e_direction> node_directions_;
+ vtr::vector<RRNodeId, e_side> node_sides_;
+ vtr::vector<RRNodeId, float> node_Rs_;
+ vtr::vector<RRNodeId, float> node_Cs_;
+ vtr::vector<RRNodeId, RRSegmentId> node_segments_; /* Segment ids for each node */
+ /* Record the dividing point between configurable and non-configurable edges for each node */
+ vtr::vector<RRNodeId, size_t> node_num_non_configurable_in_edges_;
+ vtr::vector<RRNodeId, size_t> node_num_non_configurable_out_edges_;
+
+ vtr::vector<RRNodeId, std::vector<RREdgeId>> node_in_edges_;
+ vtr::vector<RRNodeId, std::vector<RREdgeId>> node_out_edges_;
+
+ /* Edge related data */
+ vtr::vector<RREdgeId, RREdgeId> edge_ids_; /* unique identifiers for edges */
+ vtr::vector<RREdgeId, RRNodeId> edge_src_nodes_;
+ vtr::vector<RREdgeId, RRNodeId> edge_sink_nodes_;
+ vtr::vector<RREdgeId, RRSwitchId> edge_switches_;
+
+ /* Switch related data
+ * Note that so far there has been no need to remove
+ * switches, so no such facility exists
+ */
+ /* Unique identifiers for switches which are used in the RRGraph */
+ vtr::vector<RRSwitchId, RRSwitchId> switch_ids_;
+ /* Detailed information about the switches, which are used in the RRGraph */
+ vtr::vector<RRSwitchId, t_rr_switch_inf> switches_;
+
+ /* Segment relatex data
+ * Segment info should be corrected annotated for each rr_node
+ * whose type is CHANX and CHANY
+ */
+ vtr::vector<RRSegmentId, RRSegmentId> segment_ids_; /* unique identifiers for routing segments which are used in the RRGraph */
+ vtr::vector<RRSegmentId, t_segment_inf> segments_; /* detailed information about the segments, which are used in the RRGraph */
+
+ /* Misc. */
+ /* A flag to indicate if the graph contains invalid elements (nodes/edges etc.) */
+ bool dirty_ = false;
+
+ /* Fast look-up to search a node by its type, coordinator and ptc_num
+ * Indexing of fast look-up: [0..xmax][0..ymax][0..NUM_TYPES-1][0..ptc_max][0..NUM_SIDES-1]
+ */
+ typedef std::vector<std::vector<std::vector<std::vector<std::vector<RRNodeId>>>>> NodeLookup;
+ mutable NodeLookup node_lookup_;
+};
+
+#endif
diff --git a/vpr/src/device/rr_graph_obj_utils.h b/vpr/src/device/rr_graph_obj_utils.h
new file mode 100644
index 0000000..910b0ce
--- /dev/null
+++ b/vpr/src/device/rr_graph_obj_utils.h
@@ -0,0 +1,165 @@
+#ifndef RR_GRAPH_OBJ_UTILS_H
+#define RR_GRAPH_OBJ_UTILS_H
+
+/* Include header files which include data structures used by
+ * the function declaration
+ */
+#include <vector>
+#include "vtr_vector_map.h"
+
+/*
+ *
+ * Templated utility functions for cleaning and reordering IdMaps
+ *
+ */
+
+//Returns true if all elements are contiguously ascending values (i.e. equal to their index)
+template<typename Container>
+bool are_contiguous(const Container& values) {
+ using T = typename Container::value_type;
+ size_t i = 0;
+ for (T val : values) {
+ if (val != T(i)) {
+ return false;
+ }
+ ++i;
+ }
+ return true;
+}
+
+//Returns true if all elements in the vector 'values' evaluate true
+template<typename Container>
+bool all_valid(const Container& values) {
+ for (auto val : values) {
+ if (!val) {
+ return false;
+ }
+ }
+ return true;
+}
+
+//Builds a mapping from old to new ids by skipping values marked invalid
+template<typename Container>
+Container compress_ids(const Container& ids) {
+ using Id = typename Container::value_type;
+ Container id_map(ids.size());
+ size_t i = 0;
+ for (auto id : ids) {
+ if (id) {
+ //Valid
+ id_map[id] = Id(i);
+ ++i;
+ }
+ }
+
+ return id_map;
+}
+
+//Returns a vector based on 'values', which has had entries dropped & re-ordered according according to 'id_map'.
+//Each entry in id_map corresponds to the assoicated element in 'values'.
+//The value of the id_map entry is the new ID of the entry in values.
+//
+//If it is an invalid ID, the element in values is dropped.
+//Otherwise the element is moved to the new ID location.
+template<typename ValueContainer, typename IdContainer>
+ValueContainer clean_and_reorder_values(const ValueContainer& values, const IdContainer& id_map) {
+ using Id = typename IdContainer::value_type;
+ VTR_ASSERT(values.size() == id_map.size());
+
+ //Allocate space for the values that will not be dropped
+ ValueContainer result(values.size());
+
+ //Move over the valid entries to their new locations
+ size_t new_count = 0;
+ for (size_t cur_idx = 0; cur_idx < values.size(); ++cur_idx) {
+ Id old_id = Id(cur_idx);
+
+ Id new_id = id_map[old_id];
+ if (new_id) {
+ //There is a valid mapping
+ result[new_id] = std::move(values[old_id]);
+ ++new_count;
+ }
+ }
+
+ result.resize(new_count);
+
+ return result;
+}
+
+//Returns the set of new valid Ids defined by 'id_map'
+//TODO: merge with clean_and_reorder_values
+template<typename Container>
+Container clean_and_reorder_ids(const Container& id_map) {
+ //For IDs, the values are the new id's stored in the map
+ using Id = typename Container::value_type;
+
+ //Allocate a new vector to store the values that have been not dropped
+ Container result(id_map.size());
+
+ //Move over the valid entries to their new locations
+ size_t new_count = 0;
+ for (size_t cur_idx = 0; cur_idx < id_map.size(); ++cur_idx) {
+ Id old_id = Id(cur_idx);
+
+ Id new_id = id_map[old_id];
+ if (new_id) {
+ result[new_id] = new_id;
+ ++new_count;
+ }
+ }
+
+ result.resize(new_count);
+
+ return result;
+}
+
+//Count how many of the Id's referenced in 'range' have a valid
+//new mapping in 'id_map'
+template<typename R, typename Id>
+size_t count_valid_refs(R range, const vtr::vector_map<Id, Id>& id_map) {
+ size_t valid_count = 0;
+
+ for (Id old_id : range) {
+ if (id_map[old_id]) {
+ ++valid_count;
+ }
+ }
+
+ return valid_count;
+}
+
+//Updates the Ids in 'values' based on id_map, even if the original or new mapping is not valid
+template<typename Container, typename ValId>
+Container update_all_refs(const Container& values, const vtr::vector_map<ValId, ValId>& id_map) {
+ Container updated;
+
+ for (ValId orig_val : values) {
+ //The original item was valid
+ ValId new_val = id_map[orig_val];
+ //The original item exists in the new mapping
+ updated.emplace_back(new_val);
+ }
+
+ return updated;
+}
+
+template<typename ValueContainer, typename IdContainer>
+ValueContainer update_valid_refs(const ValueContainer& values, const IdContainer& id_map) {
+ ValueContainer updated;
+
+ for (auto orig_val : values) {
+ if (orig_val) {
+ //Original item valid
+
+ auto new_val = id_map[orig_val];
+ if (new_val) {
+ //The original item exists in the new mapping
+ updated.emplace_back(new_val);
+ }
+ }
+ }
+ return updated;
+}
+
+#endif
diff --git a/vpr/src/device/rr_graph_util.cpp b/vpr/src/device/rr_graph_util.cpp
new file mode 100644
index 0000000..495a665
--- /dev/null
+++ b/vpr/src/device/rr_graph_util.cpp
@@ -0,0 +1,30 @@
+/****************************************************************************
+ * This file include most-utilized functions that manipulate on the
+ * RRGraph object
+ ***************************************************************************/
+#include "rr_graph_util.h"
+#include "rr_graph_obj.h"
+
+/****************************************************************************
+ * Find the switches interconnecting two nodes
+ * Return a vector of switch ids
+ ***************************************************************************/
+std::vector<RRSwitchId> find_rr_graph_switches(const RRGraph& rr_graph,
+ const RRNodeId& from_node,
+ const RRNodeId& to_node) {
+ std::vector<RRSwitchId> switches;
+ std::vector<RREdgeId> edges = rr_graph.find_edges(from_node, to_node);
+ if (true == edges.empty()) {
+ /* edge is open, we return an empty vector of switches */
+ return switches;
+ }
+
+ /* Reach here, edge list is not empty, find switch id one by one
+ * and update the switch list
+ */
+ for (auto edge : edges) {
+ switches.push_back(rr_graph.edge_switch(edge));
+ }
+
+ return switches;
+}
diff --git a/vpr/src/device/rr_graph_util.h b/vpr/src/device/rr_graph_util.h
new file mode 100644
index 0000000..027356b
--- /dev/null
+++ b/vpr/src/device/rr_graph_util.h
@@ -0,0 +1,15 @@
+#ifndef RR_GRAPH_UTIL_H
+#define RR_GRAPH_UTIL_H
+
+/* Include header files which include data structures used by
+ * the function declaration
+ */
+#include <vector>
+#include "rr_graph_fwd.h"
+
+/* Get node-to-node switches in a RRGraph */
+std::vector<RRSwitchId> find_rr_graph_switches(const RRGraph& rr_graph,
+ const RRNodeId& from_node,
+ const RRNodeId& to_node);
+
+#endif
