check_route.c

用于学术研究的FPGA布局布线软件VPR

#include <assert.h>
#include <stdio.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "mst.h"
#include "route_export.h"
#include "check_route.h"
#include "rr_graph.h"
#include "check_rr_graph.h"


/******************** Subroutines local to this module **********************/
static void check_node_and_range(int inode,
				 enum e_route_type route_type);
static void check_source(int inode,
			 int inet);
static void check_sink(int inode,
		       int inet,
		       boolean * pin_done);
static void check_switch(struct s_trace *tptr,
			 int num_switch);
static boolean check_adjacent(int from_node,
			      int to_node);
static int pin_and_chan_adjacent(int pin_node,
				 int chan_node);
static int chanx_chany_adjacent(int chanx_node,
				int chany_node);
static void reset_flags(int inet,
			boolean * connected_to_route);
static void recompute_occupancy_from_scratch(t_ivec ** fb_opins_used_locally);
static void check_locally_used_fb_opins(t_ivec ** fb_opins_used_locally,
					enum e_route_type route_type);

/************************ Subroutine definitions ****************************/


void
check_route(enum e_route_type route_type,
	    int num_switch,
	    t_ivec ** fb_opins_used_locally)
{

/* 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).                                                             */

    int inet, ipin, max_pins, inode, prev_node;
    boolean valid, connects;
    boolean *connected_to_route;	/* [0 .. num_rr_nodes-1] */
    struct s_trace *tptr;
    boolean *pin_done;

    printf("\nChecking 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(fb_opins_used_locally);
    valid = feasible_routing();
    if(valid == FALSE)
	{
	    printf
		("Error in check_route -- routing resources are overused.\n");
	    exit(1);
	}

    check_locally_used_fb_opins(fb_opins_used_locally, route_type);

    connected_to_route = (boolean *) my_calloc(num_rr_nodes, sizeof(boolean));

    max_pins = 0;
    for(inet = 0; inet < num_nets; inet++)
	max_pins = max(max_pins, (net[inet].num_sinks + 1));

    pin_done = (boolean *) my_malloc(max_pins * sizeof(boolean));

/* Now check that all nets are indeed connected. */

    for(inet = 0; inet < num_nets; inet++)
	{

	    if(net[inet].is_global)	/* Skip global nets. */
		continue;

	    for(ipin = 0; ipin < (net[inet].num_sinks + 1); ipin++)
		pin_done[ipin] = FALSE;

/* Check the SOURCE of the net. */

	    tptr = trace_head[inet];
	    if(tptr == NULL)
		{
		    printf("Error in check_route:  net %d has no routing.\n",
			   inet);
		    exit(1);
		}

	    inode = tptr->index;
	    check_node_and_range(inode, route_type);
	    check_switch(tptr, num_switch);
	    connected_to_route[inode] = TRUE;	/* Mark as in path. */

	    check_source(inode, inet);
	    pin_done[0] = TRUE;

	    prev_node = inode;
	    tptr = tptr->next;

/* Check the rest of the net */

	    while(tptr != NULL)
		{
		    inode = tptr->index;
		    check_node_and_range(inode, route_type);
		    check_switch(tptr, num_switch);

		    if(rr_node[prev_node].type == SINK)
			{
			    if(connected_to_route[inode] == FALSE)
				{
				    printf
					("Error in check_route.  Node %d does not link "
					 "into the existing routing for net %d.\n",
					 inode, inet);
				    exit(1);
				}
			}

		    else
			{
			    connects = check_adjacent(prev_node, inode);
			    if(!connects)
				{
				    printf
					("Error in check_route while checking net %d.\n",
					 inet);
				    printf
					("Non-adjacent segments in traceback.\n");
				    exit(1);
				}

			    if(connected_to_route[inode]
			       && rr_node[inode].type != SINK)
				{

				    /* Note:  Can get multiple connections to the same logically-equivalent     *
				     * SINK in some logic blocks.                                               */

				    printf
					("Error in check_route:  net %d routing is not a tree.\n",
					 inet);
				    exit(1);
				}

			    connected_to_route[inode] = TRUE;	/* Mark as in path. */

			    if(rr_node[inode].type == SINK)
				check_sink(inode, inet, pin_done);

			}	/* End of prev_node type != SINK */
		    prev_node = inode;
		    tptr = tptr->next;
		}		/* End while */

	    if(rr_node[prev_node].type != SINK)
		{
		    printf("Error in check_route.  Net %d does not end\n",
			   inet);
		    printf("with a SINK.\n");
		    exit(1);
		}

	    for(ipin = 0; ipin < (net[inet].num_sinks + 1); ipin++)
		{
		    if(pin_done[ipin] == FALSE)
			{
			    printf
				("Error in check_route.  Net %d does not \n",
				 inet);
			    printf("connect to pin %d.\n", ipin);
			    exit(1);
			}
		}

	    reset_flags(inet, connected_to_route);

	}			/* End for each net */

    free(pin_done);
    free(connected_to_route);
    printf("Completed routing consistency check successfully.\n\n");
}

static void
check_sink(int inode,
	   int inet,
	   boolean * pin_done)
{

/* Checks that this SINK node is one of the terminals of inet, and marks   *
 * the appropriate pin as being reached.                                   */

    int i, j, ipin, ifound, ptc_num, bnum, iclass, node_block_pin, iblk;
    t_type_ptr type;

    assert(rr_node[inode].type == SINK);
    i = rr_node[inode].xlow;
    j = rr_node[inode].ylow;
    type = grid[i][j].type;
    ptc_num = rr_node[inode].ptc_num;	/* For sinks, ptc_num is the class */
    ifound = 0;

    for(iblk = 0; iblk < type->capacity; iblk++)
	{
	    bnum = grid[i][j].blocks[iblk];	/* Hardcoded to one block */
	    for(ipin = 1; ipin < (net[inet].num_sinks + 1); ipin++)
		{		/* All net SINKs */
		    if(net[inet].node_block[ipin] == bnum)
			{
			    node_block_pin = net[inet].node_block_pin[ipin];
			    iclass = type->pin_class[node_block_pin];
			    if(iclass == ptc_num)
				{
/* Could connect to same pin class on the same fb 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;
					}
				}
			}
		}
	}

    if(ifound > 1 && type == IO_TYPE)
	{
	    printf("Error in check_sink:  found %d terminals of net %d of pad"
		   "\n %d at location (%d, %d).\n", ifound, inet, ptc_num, i,
		   j);
	    exit(1);
	}

    if(ifound < 1)
	{
	    printf
		("Error in check_sink:  node %d does not connect to any terminal "
		 "\n of net %d.\n", inode, inet);
	    exit(1);
	}
}


static void
check_source(int inode,
	     int inet)
{

/* Checks that the node passed in is a valid source for this net.        */

    t_rr_type rr_type;
    t_type_ptr type;
    int i, j, ptc_num, bnum, node_block_pin, iclass;

    rr_type = rr_node[inode].type;
    if(rr_type != SOURCE)
	{
	    printf
		("Error in check_source:  net %d begins with a node of type %d.\n",
		 inet, rr_type);
	    exit(1);
	}

    i = rr_node[inode].xlow;
    j = rr_node[inode].ylow;
    ptc_num = rr_node[inode].ptc_num;	/* for sinks and sources, ptc_num is class */
    bnum = net[inet].node_block[0];	/* First node_block for net is the source */
    type = grid[i][j].type;

    if(block[bnum].x != i || block[bnum].y != j)
	{
	    printf
		("Error in check_source:  net SOURCE is in wrong location (%d,%d)."
		 "\n", i, j);
	    exit(1);
	}

    node_block_pin = net[inet].node_block_pin[0];
    iclass = type->pin_class[node_block_pin];

    if(ptc_num != iclass)
	{
	    printf
		("Error in check_source:  net SOURCE is of wrong class (%d).\n",
		 ptc_num);
	    exit(1);
	}
}


static void
check_switch(struct s_trace *tptr,
	     int num_switch)
{

/* Checks that the switch leading from this traceback element to the next *
 * one is a legal switch type.                                            */

    int inode;
    short switch_type;

    inode = tptr->index;
    switch_type = tptr->iswitch;

    if(rr_node[inode].type != SINK)
	{
	    if(switch_type < 0 || switch_type >= num_switch)
		{
		    printf
			("Error in check_switch: rr_node %d left via switch type %d.\n",
			 inode, switch_type);
		    printf("Switch type is out of range.\n");
		    exit(1);
		}
	}

    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)
		{
		    printf
			("Error in check_switch:  rr_node %d is a SINK, but attempts \n"
			 "to use a switch of type %d.\n", inode, switch_type);
		    exit(1);
		}
	}
}


static void
reset_flags(int inet,
	    boolean * 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).                   */

    struct s_trace *tptr;
    int inode;

    tptr = trace_head[inet];

    while(tptr != NULL)
	{
	    inode = tptr->index;
	    connected_to_route[inode] = FALSE;	/* Not in routed path now. */
	    tptr = tptr->next;
	}
}


static boolean
check_adjacent(int from_node,
	       int 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.                                                */

    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;
    boolean reached;
    t_rr_type from_type, to_type;
    t_type_ptr from_grid_type, to_grid_type;

    reached = FALSE;

    for(iconn = 0; iconn < rr_node[from_node].num_edges; iconn++)
	{
	    if(rr_node[from_node].edges[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.                 */