| #include <cstdio> |
| using namespace std; |
| |
| #include "vtr_assert.h" |
| #include "vtr_log.h" |
| #include "vtr_memory.h" |
| #include "vtr_vector.h" |
| |
| #include "vpr_types.h" |
| #include "vpr_error.h" |
| |
| #include "globals.h" |
| #include "route_export.h" |
| #include "check_route.h" |
| #include "rr_graph.h" |
| #include "check_rr_graph.h" |
| #include "read_xml_arch_file.h" |
| |
| struct t_node_edge { |
| t_node_edge(RRNodeId fnode, RRNodeId tnode) { |
| from_node = fnode; |
| to_node = tnode; |
| } |
| |
| RRNodeId from_node; |
| RRNodeId to_node; |
| |
| //For std::set |
| friend bool operator<(const t_node_edge& lhs, const t_node_edge& rhs) { |
| return std::tie(lhs.from_node, lhs.to_node) < std::tie(rhs.from_node, rhs.to_node); |
| } |
| }; |
| |
| struct t_non_configurable_rr_sets { |
| |
| std::set<std::set<int>> node_sets; |
| std::set<std::set<t_node_edge>> edge_sets; |
| }; |
| |
| /******************** Subroutines local to this module **********************/ |
| static void check_node_and_range(RRNodeId inode, enum e_route_type route_type); |
| static void check_source(RRNodeId inode, ClusterNetId net_id); |
| static void check_sink(RRNodeId inode, ClusterNetId net_id, bool * pin_done); |
| static void check_switch(t_trace *tptr, int num_switch); |
| static bool check_adjacent(RRNodeId from_node, RRNodeId to_node); |
| static int chanx_chany_adjacent(RRNodeId chanx_node, RRNodeId chany_node); |
| static void reset_flags(ClusterNetId inet, vtr::vector<RRNodeId, bool>& connected_to_route); |
| static void check_locally_used_clb_opins(const t_clb_opins_used& clb_opins_used_locally, |
| enum e_route_type route_type); |
| |
| static t_non_configurable_rr_sets identify_non_configurable_rr_sets(); |
| static void expand_non_configurable(RRNodeId inode, std::set<t_node_edge>& edge_set); |
| static bool check_non_configurable_edges(ClusterNetId net, const t_non_configurable_rr_sets& non_configurable_rr_sets); |
| |
| /************************ Subroutine definitions ****************************/ |
| |
| void check_route(enum e_route_type route_type, int num_switches) { |
| |
| /* This routine checks that a routing: (1) Describes a properly * |
| * connected path for each net, (2) this path connects all the * |
| * pins spanned by that net, and (3) that no routing resources are * |
| * oversubscribed (the occupancy of everything is recomputed from * |
| * scratch). */ |
| |
| auto& device_ctx = g_vpr_ctx.device(); |
| auto& cluster_ctx = g_vpr_ctx.clustering(); |
| auto& route_ctx = g_vpr_ctx.routing(); |
| |
| int max_pins; |
| unsigned int ipin; |
| bool valid, connects; |
| vtr::vector<RRNodeId, bool> connected_to_route(device_ctx.rr_nodes.size(), false); |
| t_trace *tptr; |
| bool * pin_done; |
| |
| vtr::printf_info("\n"); |
| vtr::printf_info("Checking to ensure routing is legal...\n"); |
| |
| /* Recompute the occupancy from scratch and check for overuse of routing * |
| * resources. This was already checked in order to determine that this * |
| * is a successful routing, but I want to double check it here. */ |
| |
| recompute_occupancy_from_scratch(); |
| valid = feasible_routing(); |
| if (valid == false) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "Error in check_route -- routing resources are overused.\n"); |
| } |
| |
| check_locally_used_clb_opins(route_ctx.clb_opins_used_locally, route_type); |
| |
| auto non_configurable_rr_sets = identify_non_configurable_rr_sets(); |
| |
| max_pins = 0; |
| for (auto net_id : cluster_ctx.clb_nlist.nets()) |
| max_pins = max(max_pins, (int)cluster_ctx.clb_nlist.net_pins(net_id).size()); |
| |
| pin_done = (bool *) vtr::malloc(max_pins * sizeof(bool)); |
| |
| /* Now check that all nets are indeed connected. */ |
| for (auto net_id : cluster_ctx.clb_nlist.nets()) { |
| if (cluster_ctx.clb_nlist.net_is_global(net_id) || cluster_ctx.clb_nlist.net_sinks(net_id).size() == 0) /* Skip global nets. */ |
| continue; |
| |
| for (ipin = 0; ipin < cluster_ctx.clb_nlist.net_pins(net_id).size(); ipin++) |
| pin_done[ipin] = false; |
| |
| /* Check the SOURCE of the net. */ |
| tptr = route_ctx.trace_head[net_id]; |
| if (tptr == nullptr) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_route: net %d has no routing.\n", size_t(net_id)); |
| } |
| |
| auto inode = tptr->index; |
| check_node_and_range(inode, route_type); |
| check_switch(tptr, num_switches); |
| connected_to_route[inode] = true; /* Mark as in path. */ |
| |
| check_source(inode, net_id); |
| pin_done[0] = true; |
| |
| auto prev_node = inode; |
| int prev_switch = tptr->iswitch; |
| tptr = tptr->next; |
| |
| /* Check the rest of the net */ |
| size_t num_sinks = 0; |
| while (tptr != nullptr) { |
| inode = tptr->index; |
| check_node_and_range(inode, route_type); |
| check_switch(tptr, num_switches); |
| |
| if (prev_switch == OPEN) { //Start of a new branch |
| if (connected_to_route[inode] == false) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_route: node %d does not link into existing routing for net %d.\n", inode, size_t(net_id)); |
| } |
| } else { //Continuing along existing branch |
| connects = check_adjacent(prev_node, inode); |
| if (!connects) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_route: found non-adjacent segments in traceback while checking net %d:\n" |
| " %s\n" |
| " %s\n", |
| size_t(net_id), |
| describe_rr_node(prev_node).c_str(), |
| describe_rr_node(inode).c_str()); |
| } |
| |
| connected_to_route[inode] = true; /* Mark as in path. */ |
| |
| if (device_ctx.rr_nodes[inode].type() == SINK) { |
| check_sink(inode, net_id, pin_done); |
| num_sinks += 1; |
| } |
| |
| } /* End of prev_node type != SINK */ |
| prev_node = inode; |
| prev_switch = tptr->iswitch; |
| tptr = tptr->next; |
| } /* End while */ |
| |
| if (num_sinks != cluster_ctx.clb_nlist.net_sinks(net_id).size()) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_route: net %zu (%s) has %zu SINKs (expected %zu).\n", |
| size_t(net_id), cluster_ctx.clb_nlist.net_name(net_id).c_str(), |
| num_sinks, cluster_ctx.clb_nlist.net_sinks(net_id).size()); |
| } |
| |
| for (ipin = 0; ipin < cluster_ctx.clb_nlist.net_pins(net_id).size(); ipin++) { |
| if (pin_done[ipin] == false) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_route: net %zu does not connect to pin %d.\n", size_t(net_id), ipin); |
| } |
| } |
| |
| check_non_configurable_edges(net_id, non_configurable_rr_sets); |
| |
| reset_flags(net_id, connected_to_route); |
| |
| } /* End for each net */ |
| |
| free(pin_done); |
| connected_to_route.clear(); |
| vtr::printf_info("Completed routing consistency check successfully.\n"); |
| vtr::printf_info("\n"); |
| } |
| |
| |
| /* Checks that this SINK node is one of the terminals of inet, and marks * |
| * the appropriate pin as being reached. */ |
| static void check_sink(RRNodeId inode, ClusterNetId net_id, bool * pin_done) { |
| |
| int i, j, ifound, ptc_num, iclass, iblk, pin_index; |
| ClusterBlockId bnum; |
| unsigned int ipin; |
| t_type_ptr type; |
| auto& device_ctx = g_vpr_ctx.device(); |
| auto& cluster_ctx = g_vpr_ctx.clustering(); |
| auto& place_ctx = g_vpr_ctx.placement(); |
| |
| VTR_ASSERT(device_ctx.rr_nodes[inode].type() == SINK); |
| i = device_ctx.rr_nodes[inode].xlow(); |
| j = device_ctx.rr_nodes[inode].ylow(); |
| type = device_ctx.grid[i][j].type; |
| /* For sinks, ptc_num is the class */ |
| ptc_num = device_ctx.rr_nodes[inode].ptc_num(); |
| ifound = 0; |
| |
| for (iblk = 0; iblk < type->capacity; iblk++) { |
| bnum = place_ctx.grid_blocks[i][j].blocks[iblk]; /* Hardcoded to one cluster_ctx block*/ |
| ipin = 1; |
| for (auto pin_id : cluster_ctx.clb_nlist.net_sinks(net_id)) { |
| if (cluster_ctx.clb_nlist.pin_block(pin_id) == bnum) { |
| pin_index = cluster_ctx.clb_nlist.pin_physical_index(pin_id); |
| iclass = type->pin_class[pin_index]; |
| if (iclass == ptc_num) { |
| /* Could connect to same pin class on the same clb more than once. Only * |
| * update pin_done for a pin that hasn't been reached yet. */ |
| if (pin_done[ipin] == false) { |
| ifound++; |
| pin_done[ipin] = true; |
| } |
| } |
| } |
| ipin++; |
| } |
| } |
| |
| if (ifound > 1 && is_io_type(type)) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_sink: found %d terminals of net %d of pad %d at location (%d, %d).\n", ifound, size_t(net_id), ptc_num, i, j); |
| } |
| |
| if (ifound < 1) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_sink: node %d does not connect to any terminal of net %s #%lu.\n" |
| "This error is usually caused by incorrectly specified logical equivalence in your architecture file.\n" |
| "You should try to respecify what pins are equivalent or turn logical equivalence off.\n", inode, cluster_ctx.clb_nlist.net_name(net_id).c_str(), size_t(net_id)); |
| } |
| } |
| |
| /* Checks that the node passed in is a valid source for this net. */ |
| static void check_source(RRNodeId inode, ClusterNetId net_id) { |
| t_rr_type rr_type; |
| t_type_ptr type; |
| ClusterBlockId blk_id; |
| int i, j, ptc_num, node_block_pin, iclass; |
| auto& device_ctx = g_vpr_ctx.device(); |
| auto& cluster_ctx = g_vpr_ctx.clustering(); |
| auto& place_ctx = g_vpr_ctx.placement(); |
| |
| rr_type = device_ctx.rr_nodes[inode].type(); |
| if (rr_type != SOURCE) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_source: net %d begins with a node of type %d.\n", size_t(net_id), rr_type); |
| } |
| |
| i = device_ctx.rr_nodes[inode].xlow(); |
| j = device_ctx.rr_nodes[inode].ylow(); |
| /* for sinks and sources, ptc_num is class */ |
| ptc_num = device_ctx.rr_nodes[inode].ptc_num(); |
| /* First node_block for net is the source */ |
| blk_id = cluster_ctx.clb_nlist.net_driver_block(net_id); |
| type = device_ctx.grid[i][j].type; |
| |
| if (place_ctx.block_locs[blk_id].x != i || place_ctx.block_locs[blk_id].y != j) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_source: net SOURCE is in wrong location (%d,%d).\n", i, j); |
| } |
| |
| //Get the driver pin's index in the block |
| node_block_pin = cluster_ctx.clb_nlist.net_pin_physical_index(net_id, 0); |
| iclass = type->pin_class[node_block_pin]; |
| |
| if (ptc_num != iclass) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_source: net SOURCE is of wrong class (%d).\n", ptc_num); |
| } |
| } |
| |
| static void check_switch(t_trace *tptr, int num_switch) { |
| |
| /* Checks that the switch leading from this traceback element to the next * |
| * one is a legal switch type. */ |
| |
| short switch_type; |
| |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| auto inode = tptr->index; |
| switch_type = tptr->iswitch; |
| |
| if (device_ctx.rr_nodes[inode].type() != SINK) { |
| if (switch_type >= num_switch) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_switch: rr_node %d left via switch type %d.\n" |
| "\tSwitch type is out of range.\n", inode, switch_type); |
| } |
| } |
| |
| else { /* Is a SINK */ |
| |
| /* Without feedthroughs, there should be no switch. If feedthroughs are * |
| * allowed, change to treat a SINK like any other node (as above). */ |
| |
| if (switch_type != OPEN) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_switch: rr_node %d is a SINK, but attempts to use a switch of type %d.\n", inode, switch_type); |
| } |
| } |
| } |
| |
| static void reset_flags(ClusterNetId inet, vtr::vector<RRNodeId, bool>& connected_to_route) { |
| |
| /* This routine resets the flags of all the channel segments contained * |
| * in the traceback of net inet to 0. This allows us to check the * |
| * next net for connectivity (and the default state of the flags * |
| * should always be zero after they have been used). */ |
| |
| t_trace *tptr; |
| |
| auto& route_ctx = g_vpr_ctx.routing(); |
| |
| tptr = route_ctx.trace_head[inet]; |
| |
| while (tptr != nullptr) { |
| auto inode = tptr->index; |
| connected_to_route[inode] = false; /* Not in routed path now. */ |
| tptr = tptr->next; |
| } |
| } |
| |
| static bool check_adjacent(RRNodeId from_node, RRNodeId to_node) { |
| |
| /* This routine checks if the rr_node to_node is reachable from from_node. * |
| * It returns true if is reachable and false if it is not. Check_node has * |
| * already been used to verify that both nodes are valid rr_nodes, so only * |
| * adjacency is checked here. |
| * Special case: direct OPIN to IPIN connections need not be adjacent. These |
| * represent specially-crafted connections such as carry-chains or more advanced |
| * blocks where adjacency is overridden by the architect */ |
| |
| |
| int from_xlow, from_ylow, to_xlow, to_ylow, from_ptc, to_ptc, iclass; |
| int num_adj, to_xhigh, to_yhigh, from_xhigh, from_yhigh, iconn; |
| bool reached; |
| t_rr_type from_type, to_type; |
| t_type_ptr from_grid_type, to_grid_type; |
| |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| reached = false; |
| |
| for (iconn = 0; iconn < device_ctx.rr_nodes[from_node].num_edges(); iconn++) { |
| if (device_ctx.rr_nodes[from_node].edge_sink_node(iconn) == to_node) { |
| reached = true; |
| break; |
| } |
| } |
| |
| if (!reached) |
| return (false); |
| |
| /* Now we know the rr graph says these two nodes are adjacent. Double * |
| * check that this makes sense, to verify the rr graph. */ |
| VTR_ASSERT(reached); |
| |
| num_adj = 0; |
| |
| from_type = device_ctx.rr_nodes[from_node].type(); |
| from_xlow = device_ctx.rr_nodes[from_node].xlow(); |
| from_ylow = device_ctx.rr_nodes[from_node].ylow(); |
| from_xhigh = device_ctx.rr_nodes[from_node].xhigh(); |
| from_yhigh = device_ctx.rr_nodes[from_node].yhigh(); |
| from_ptc = device_ctx.rr_nodes[from_node].ptc_num(); |
| to_type = device_ctx.rr_nodes[to_node].type(); |
| to_xlow = device_ctx.rr_nodes[to_node].xlow(); |
| to_ylow = device_ctx.rr_nodes[to_node].ylow(); |
| to_xhigh = device_ctx.rr_nodes[to_node].xhigh(); |
| to_yhigh = device_ctx.rr_nodes[to_node].yhigh(); |
| to_ptc = device_ctx.rr_nodes[to_node].ptc_num(); |
| |
| switch (from_type) { |
| |
| case SOURCE: |
| VTR_ASSERT(to_type == OPIN); |
| |
| //The OPIN should be contained within the bounding box of it's connected source |
| if ( from_xlow <= to_xlow |
| && from_ylow <= to_ylow |
| && from_xhigh >= to_xhigh |
| && from_yhigh >= to_yhigh) { |
| |
| from_grid_type = device_ctx.grid[from_xlow][from_ylow].type; |
| to_grid_type = device_ctx.grid[to_xlow][to_ylow].type; |
| VTR_ASSERT(from_grid_type == to_grid_type); |
| |
| iclass = to_grid_type->pin_class[to_ptc]; |
| if (iclass == from_ptc) |
| num_adj++; |
| |
| |
| } |
| break; |
| |
| case SINK: |
| /* SINKS are adjacent to not connected */ |
| break; |
| |
| case OPIN: |
| if(to_type == CHANX || to_type == CHANY) { |
| num_adj += 1; //adjacent |
| } else { |
| VTR_ASSERT(to_type == IPIN); /* direct OPIN to IPIN connections not necessarily adjacent */ |
| return true; /* Special case, direct OPIN to IPIN connections need not be adjacent */ |
| } |
| |
| break; |
| |
| case IPIN: |
| VTR_ASSERT(to_type == SINK); |
| |
| //An IPIN should be contained within the bounding box of it's connected sink |
| if ( from_xlow >= to_xlow |
| && from_ylow >= to_ylow |
| && from_xhigh <= to_xhigh |
| && from_yhigh <= to_yhigh) { |
| |
| from_grid_type = device_ctx.grid[from_xlow][from_ylow].type; |
| to_grid_type = device_ctx.grid[to_xlow][to_ylow].type; |
| VTR_ASSERT(from_grid_type == to_grid_type); |
| |
| iclass = from_grid_type->pin_class[from_ptc]; |
| if (iclass == to_ptc) |
| num_adj++; |
| } |
| break; |
| |
| case CHANX: |
| if (to_type == IPIN) { |
| num_adj += 1; //adjacent |
| } else if (to_type == CHANX) { |
| from_xhigh = device_ctx.rr_nodes[from_node].xhigh(); |
| to_xhigh = device_ctx.rr_nodes[to_node].xhigh(); |
| if (from_ylow == to_ylow) { |
| /* UDSD Modification by WMF Begin */ |
| /*For Fs > 3, can connect to overlapping wire segment */ |
| if (to_xhigh == from_xlow - 1 || from_xhigh == to_xlow - 1) { |
| num_adj++; |
| } |
| /* Overlapping */ |
| else { |
| int i; |
| |
| for (i = from_xlow; i <= from_xhigh; i++) { |
| if (i >= to_xlow && i <= to_xhigh) { |
| num_adj++; |
| break; |
| } |
| } |
| } |
| /* UDSD Modification by WMF End */ |
| } |
| } else if (to_type == CHANY) { |
| num_adj += chanx_chany_adjacent(from_node, to_node); |
| } else { |
| VTR_ASSERT(0); |
| } |
| break; |
| |
| case CHANY: |
| if (to_type == IPIN) { |
| num_adj += 1; //adjacent |
| } else if (to_type == CHANY) { |
| from_yhigh = device_ctx.rr_nodes[from_node].yhigh(); |
| to_yhigh = device_ctx.rr_nodes[to_node].yhigh(); |
| if (from_xlow == to_xlow) { |
| /* UDSD Modification by WMF Begin */ |
| if (to_yhigh == from_ylow - 1 || from_yhigh == to_ylow - 1) { |
| num_adj++; |
| } |
| /* Overlapping */ |
| else { |
| int j; |
| |
| for (j = from_ylow; j <= from_yhigh; j++) { |
| if (j >= to_ylow && j <= to_yhigh) { |
| num_adj++; |
| break; |
| } |
| } |
| } |
| /* UDSD Modification by WMF End */ |
| } |
| } else if (to_type == CHANX) { |
| num_adj += chanx_chany_adjacent(to_node, from_node); |
| } else { |
| VTR_ASSERT(0); |
| } |
| break; |
| |
| default: |
| break; |
| |
| } |
| |
| if (num_adj == 1) |
| return (true); |
| else if (num_adj == 0) |
| return (false); |
| |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_adjacent: num_adj = %d. Expected 0 or 1.\n", num_adj); |
| return false; //Should not reach here once thrown |
| } |
| |
| static int chanx_chany_adjacent(RRNodeId chanx_node, RRNodeId chany_node) { |
| |
| /* Returns 1 if the specified CHANX and CHANY nodes are adjacent, 0 * |
| * otherwise. */ |
| |
| int chanx_y, chanx_xlow, chanx_xhigh; |
| int chany_x, chany_ylow, chany_yhigh; |
| |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| chanx_y = device_ctx.rr_nodes[chanx_node].ylow(); |
| chanx_xlow = device_ctx.rr_nodes[chanx_node].xlow(); |
| chanx_xhigh = device_ctx.rr_nodes[chanx_node].xhigh(); |
| |
| chany_x = device_ctx.rr_nodes[chany_node].xlow(); |
| chany_ylow = device_ctx.rr_nodes[chany_node].ylow(); |
| chany_yhigh = device_ctx.rr_nodes[chany_node].yhigh(); |
| |
| if (chany_ylow > chanx_y + 1 || chany_yhigh < chanx_y) |
| return (0); |
| |
| if (chanx_xlow > chany_x + 1 || chanx_xhigh < chany_x) |
| return (0); |
| |
| return (1); |
| } |
| |
| void recompute_occupancy_from_scratch() { |
| |
| /* |
| * This routine updates the occ field in the route_ctx.rr_node_route_inf structure |
| * according to the resource usage of the current routing. It does a |
| * brute force recompute from scratch that is useful for sanity checking. |
| */ |
| |
| int iclass, ipin, num_local_opins; |
| t_trace *tptr; |
| |
| auto& route_ctx = g_vpr_ctx.mutable_routing(); |
| auto& device_ctx = g_vpr_ctx.device(); |
| auto& cluster_ctx = g_vpr_ctx.clustering(); |
| |
| /* First set the occupancy of everything to zero. */ |
| |
| for (auto inode_idx : device_ctx.rr_nodes.keys()) { |
| route_ctx.rr_node_route_inf[inode_idx].set_occ(0); |
| } |
| |
| /* Now go through each net and count the tracks and pins used everywhere */ |
| |
| for (auto net_id : cluster_ctx.clb_nlist.nets()) { |
| if (cluster_ctx.clb_nlist.net_is_global(net_id)) /* Skip global nets. */ |
| continue; |
| |
| tptr = route_ctx.trace_head[net_id]; |
| if (tptr == nullptr) |
| continue; |
| |
| for (;;) { |
| auto inode = tptr->index; |
| route_ctx.rr_node_route_inf[inode].set_occ(route_ctx.rr_node_route_inf[inode].occ() + 1); |
| |
| if (tptr->iswitch == OPEN) { |
| tptr = tptr->next; /* Skip next segment. */ |
| if (tptr == nullptr) |
| break; |
| } |
| |
| tptr = tptr->next; |
| } |
| } |
| |
| /* Now update the occupancy of each of the "locally used" OPINs on each CLB * |
| * (CLB outputs used up by being directly wired to subblocks used only * |
| * locally). */ |
| for (auto blk_id : cluster_ctx.clb_nlist.blocks()) { |
| for (iclass = 0; iclass < cluster_ctx.clb_nlist.block_type(blk_id)->num_class; iclass++) { |
| num_local_opins = route_ctx.clb_opins_used_locally[blk_id][iclass].size(); |
| /* Will always be 0 for pads or SINK classes. */ |
| for (ipin = 0; ipin < num_local_opins; ipin++) { |
| auto inode = route_ctx.clb_opins_used_locally[blk_id][iclass][ipin]; |
| route_ctx.rr_node_route_inf[inode].set_occ(route_ctx.rr_node_route_inf[inode].occ() + 1); |
| } |
| } |
| } |
| } |
| |
| static void check_locally_used_clb_opins(const t_clb_opins_used& clb_opins_used_locally, |
| enum e_route_type route_type) { |
| |
| /* Checks that enough OPINs on CLBs have been set aside (used up) to make a * |
| * legal routing if subblocks connect to OPINs directly. */ |
| |
| int iclass, num_local_opins, ipin; |
| t_rr_type rr_type; |
| |
| auto& cluster_ctx = g_vpr_ctx.clustering(); |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| for (auto blk_id : cluster_ctx.clb_nlist.blocks()) { |
| for (iclass = 0; iclass < cluster_ctx.clb_nlist.block_type(blk_id)->num_class; iclass++) { |
| num_local_opins = clb_opins_used_locally[blk_id][iclass].size(); |
| /* Always 0 for pads and for SINK classes */ |
| |
| for (ipin = 0; ipin < num_local_opins; ipin++) { |
| auto inode = clb_opins_used_locally[blk_id][iclass][ipin]; |
| check_node_and_range(inode, route_type); /* Node makes sense? */ |
| |
| /* Now check that node is an OPIN of the right type. */ |
| |
| rr_type = device_ctx.rr_nodes[inode].type(); |
| if (rr_type != OPIN) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_locally_used_opins: block #%lu (%s)\n" |
| "\tClass %d local OPIN is wrong rr_type -- rr_node #%d of type %d.\n", |
| size_t(blk_id), cluster_ctx.clb_nlist.block_name(blk_id).c_str(), iclass, inode, rr_type); |
| } |
| |
| ipin = device_ctx.rr_nodes[inode].ptc_num(); |
| if (cluster_ctx.clb_nlist.block_type(blk_id)->pin_class[ipin] != iclass) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_locally_used_opins: block #%lu (%s):\n" |
| "\tExpected class %d local OPIN has class %d -- rr_node #: %d.\n", |
| size_t(blk_id), cluster_ctx.clb_nlist.block_name(blk_id).c_str(), iclass, cluster_ctx.clb_nlist.block_type(blk_id)->pin_class[ipin], inode); |
| } |
| } |
| } |
| } |
| } |
| |
| static void check_node_and_range(RRNodeId inode, enum e_route_type route_type) { |
| |
| /* Checks that inode is within the legal range, then calls check_node to * |
| * check that everything else about the node is OK. */ |
| |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| if (inode == RRNodeId::INVALID() || device_ctx.rr_nodes.keys().in_range(inode)) { |
| vpr_throw(VPR_ERROR_ROUTE, __FILE__, __LINE__, |
| "in check_node_and_range: rr_node #%d is out of legal, range (0 to %d).\n", inode, device_ctx.rr_nodes.size() - 1); |
| } |
| check_rr_node(inode, route_type, device_ctx); |
| } |
| |
| //Collects the sets of connected non-configurable edges in the RR graph |
| static t_non_configurable_rr_sets identify_non_configurable_rr_sets() { |
| std::set<std::set<t_node_edge>> edge_sets; |
| |
| //Walk through the RR graph and recursively expand non-configurable edges |
| //to collect the sets of non-configurably connected nodes |
| auto& device_ctx = g_vpr_ctx.device(); |
| for (auto inode : device_ctx.rr_nodes.keys()) { |
| std::set<t_node_edge> edge_set; |
| |
| expand_non_configurable(inode, edge_set); |
| |
| if (!edge_set.empty()) { |
| edge_sets.insert(edge_set); |
| } |
| } |
| |
| std::set<std::set<int>> node_sets; |
| for (auto& edge_set : edge_sets) { |
| std::set<int> node_set; |
| |
| for (const auto& edge : edge_set) { |
| node_set.insert(edge.from_node); |
| node_set.insert(edge.to_node); |
| } |
| |
| VTR_ASSERT(!node_set.empty()); |
| |
| node_sets.insert(node_set); |
| } |
| |
| t_non_configurable_rr_sets non_configurable_rr_sets; |
| non_configurable_rr_sets.edge_sets = edge_sets; |
| non_configurable_rr_sets.node_sets = node_sets; |
| |
| return non_configurable_rr_sets; |
| } |
| |
| //Builds a set of non-configurably connected RR graph edges |
| static void expand_non_configurable(RRNodeId inode, std::set<t_node_edge>& edge_set) { |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| for (int iedge = 0; iedge < device_ctx.rr_nodes[inode].num_edges(); ++iedge) { |
| bool edge_non_configurable = !device_ctx.rr_nodes[inode].edge_is_configurable(iedge); |
| |
| if (edge_non_configurable) { |
| auto to_node = device_ctx.rr_nodes[inode].edge_sink_node(iedge); |
| |
| t_node_edge edge = {inode, to_node}; |
| |
| if (edge_set.count(edge)) { |
| continue; //Already seen don't re-expand to avoid loops |
| } |
| |
| edge_set.emplace(edge); |
| |
| expand_non_configurable(to_node, edge_set); |
| } |
| } |
| } |
| |
| //Checks that the specified routing is legal with respect to non-configurable edges |
| // |
| //For routing to be legal if *any* non-configurable edge is used, so must *all* |
| //other non-configurable edges in the same set |
| static bool check_non_configurable_edges(ClusterNetId net, const t_non_configurable_rr_sets& non_configurable_rr_sets) { |
| auto& route_ctx = g_vpr_ctx.routing(); |
| auto& cluster_ctx = g_vpr_ctx.clustering(); |
| |
| t_trace* head = route_ctx.trace_head[net]; |
| |
| //Collect all the edges used by this net's routing |
| std::set<t_node_edge> routing_edges; |
| std::set<int> routing_nodes; |
| for (t_trace* trace = head; trace != nullptr; trace = trace->next) { |
| int inode = trace->index; |
| |
| routing_nodes.insert(inode); |
| |
| if (trace->iswitch == OPEN) { |
| continue; //End of branch |
| } else if (trace->next) { |
| int inode_next = trace->next->index; |
| |
| t_node_edge edge = {inode, inode_next}; |
| |
| routing_edges.insert(edge); |
| } |
| } |
| |
| //We need to perform two types of checks: |
| // |
| // 1) That all nodes in a non-configurable set are included |
| // 2) That all (required) non-configurable edges are used |
| // |
| //We need to check (2) in addition to (1) to ensure that (1) did not pass |
| //because the nodes 'happend' to be connected together by configurable |
| //routing (to be legal, by definition, they must be connected by |
| //non-configurable routing). |
| |
| //Check that all nodes in each non-configurable set are full included if any element |
| //within a set is used by the routing |
| for (const auto& rr_nodes : non_configurable_rr_sets.node_sets) { |
| |
| //Compute the intersection of the routing and current non-configurable nodes set |
| std::vector<int> intersection; |
| std::set_intersection(routing_nodes.begin(), routing_nodes.end(), |
| rr_nodes.begin(), rr_nodes.end(), |
| std::back_inserter(intersection)); |
| |
| //If the intersection is non-empty then the current routing uses |
| //at least one non-configurable edge in this set |
| if (!intersection.empty()) { |
| |
| //To be legal *all* the nodes must be included in the routing |
| if (intersection.size() != rr_nodes.size()) { |
| //Illegal |
| |
| //Compute the difference to identify the missing nodes |
| //for detailed error reporting -- the nodes |
| //which are in rr_nodes but not in routing_nodes. |
| std::vector<int> difference; |
| std::set_difference(rr_nodes.begin(), rr_nodes.end(), |
| routing_nodes.begin(), routing_nodes.end(), |
| std::back_inserter(difference)); |
| |
| VTR_ASSERT(difference.size() > 0); |
| std::string msg = vtr::string_fmt("Illegal routing for net '%s' (#%zu) some " |
| "required non-configurably connected nodes are missing:\n", |
| cluster_ctx.clb_nlist.net_name(net).c_str(), size_t(net)); |
| |
| for (auto inode : difference) { |
| msg += vtr::string_fmt(" Missing %s\n", describe_rr_node(inode).c_str()); |
| } |
| |
| VPR_THROW(VPR_ERROR_ROUTE, msg.c_str()); |
| } |
| } |
| } |
| |
| //Check that any sets of non-configurable RR graph edges are fully included |
| //in the routing, if any of a set's edges are used |
| for (const auto& rr_edges : non_configurable_rr_sets.edge_sets) { |
| |
| //Compute the intersection of the routing and current non-configurable edge set |
| std::vector<t_node_edge> intersection; |
| std::set_intersection(routing_edges.begin(), routing_edges.end(), |
| rr_edges.begin(), rr_edges.end(), |
| std::back_inserter(intersection)); |
| |
| //If the intersection is non-empty then the current routing uses |
| //at least one non-configurable edge in this set |
| if (!intersection.empty()) { |
| |
| //Since at least one non-configurable edge is used, to be legal |
| //the full set of non-configurably connected edges must be used. |
| // |
| //This is somewhat complicted by the fact that non-configurable edges |
| //are sometimes bi-directional (e.g. electrical shorts) and so appear |
| //in rr_edges twice (once forward, once backward). Only one of the |
| //paired edges need appear to be correct. |
| |
| //To figure out which edges are missing we compute |
| //the difference from rr_edges to routing_edges -- the nodes |
| //which are in rr_edges but not in routing_edges. |
| std::vector<t_node_edge> difference; |
| std::set_difference(rr_edges.begin(), rr_edges.end(), |
| routing_edges.begin(), routing_edges.end(), |
| std::back_inserter(difference)); |
| |
| //Next we remove edges in the difference if there is a reverse |
| //edge in rr_edges and the forward edge is found in routing (or vice-versa). |
| //It is OK if there is an unused reverse/forward edge provided the |
| //forward/reverse edge is used. |
| std::vector<t_node_edge> dedupped_difference; |
| std::copy_if(difference.begin(), difference.end(), |
| std::back_inserter(dedupped_difference), |
| [&](t_node_edge forward_edge) { |
| |
| VTR_ASSERT_MSG(!routing_edges.count(forward_edge), "Difference should not contain used routing edges"); |
| |
| t_node_edge reverse_edge = {forward_edge.to_node, forward_edge.from_node}; |
| |
| //Check whether the reverse edge was used |
| if (rr_edges.count(reverse_edge) && routing_edges.count(reverse_edge)) { |
| //The reverse edge exists in the set of rr_edges, and was used |
| //by the routing. |
| // |
| //We can therefore safely ignore the fact that this (forward) edge is un-used |
| return false; //Drop from difference |
| } else { |
| return true; //Keep, this edge should have been used |
| } |
| }); |
| |
| //At this point only valid missing node pairs are in the set |
| if (!dedupped_difference.empty()) { |
| std::string msg = vtr::string_fmt("Illegal routing for net '%s' (#%zu) some required non-configurable edges are missing:\n", |
| cluster_ctx.clb_nlist.net_name(net).c_str(), size_t(net)); |
| |
| for (t_node_edge missing_edge : dedupped_difference) { |
| msg += vtr::string_fmt(" Expected RR Node: %d and RR Node: %d to be non-configurably connected, but edge missing from routing:\n", |
| missing_edge.from_node, missing_edge.to_node); |
| msg += vtr::string_fmt(" %s\n", describe_rr_node(missing_edge.from_node).c_str()); |
| msg += vtr::string_fmt(" %s\n", describe_rr_node(missing_edge.to_node).c_str()); |
| } |
| |
| VPR_THROW(VPR_ERROR_ROUTE, msg.c_str()); |
| } |
| |
| //TODO: verify that the switches used in trace are actually non-configurable |
| } |
| } |
| |
| return true; |
| } |
