check_rr_graph.c

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

#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "rr_graph.h"
#include "check_rr_graph.h"


/********************** Local defines and types *****************************/

#define BUF_FLAG 1
#define PTRANS_FLAG 2
#define BUF_AND_PTRANS_FLAG 3


/*********************** Subroutines local to this module *******************/

static boolean rr_node_is_global_clb_ipin(int inode);

static void check_pass_transistors(int from_node);


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

static boolean rr_graph_error;
static boolean rr_graph_warn;

void
check_rr_graph(IN t_graph_type graph_type,
	       IN int num_types,
	       IN t_type_ptr types,
	       IN int nx,
	       IN int ny,
	       IN struct s_grid_tile **grid,
	       IN int nodes_per_chan,
	       IN int Fs,
	       IN int num_seg_types,
		   IN int num_switches,
	       IN t_segment_inf * segment_inf,
	       IN int global_route_switch,
	       IN int delayless_switch,
	       IN int wire_to_ipin_switch,
	       t_seg_details * seg_details,
	       int *Fc_in,
	       int *Fc_out,
	       t_ivec *** rr_node_indices,
	       int *****opin_to_track_map,
	       int *****ipin_to_track_map,
	       t_ivec **** track_to_ipin_lookup,
	       t_ivec *** switch_block_conn,
	       boolean * perturb_ipins)
{


    int *num_edges_from_current_to_node;	/* [0..num_rr_nodes-1] */
    int *total_edges_to_node;	/* [0..num_rr_nodes-1] */
    char *switch_types_from_current_to_node;	/* [0..num_rr_nodes-1] */
    int inode, iedge, to_node, num_edges;
    short switch_type;
    t_rr_type rr_type, to_rr_type;
    enum e_route_type route_type;
	boolean is_fringe_warning_sent;

    route_type = DETAILED;
    if(graph_type == GRAPH_GLOBAL)
	{
	    route_type = GLOBAL;
	}

    total_edges_to_node = (int *)my_calloc(num_rr_nodes, sizeof(int));
    num_edges_from_current_to_node = (int *)my_calloc(num_rr_nodes,
						      sizeof(int));
    switch_types_from_current_to_node = (char *)my_calloc(num_rr_nodes,
							  sizeof(char));

    for(inode = 0; inode < num_rr_nodes; inode++)
	{
	    rr_type = rr_node[inode].type;
	    num_edges = rr_node[inode].num_edges;

	    check_node(inode, route_type);

/* Check all the connectivity (edges, etc.) information.                    */

	    for(iedge = 0; iedge < num_edges; iedge++)
		{
		    to_node = rr_node[inode].edges[iedge];

		    if(to_node < 0 || to_node >= num_rr_nodes)
			{
			    printf
				("Error in check_rr_graph:  node %d has an edge %d.\n"
				 "Edge is out of range.\n", inode, to_node);
			    exit(1);
			}

		    num_edges_from_current_to_node[to_node]++;
		    total_edges_to_node[to_node]++;

		    switch_type = rr_node[inode].switches[iedge];

		    if(switch_type < 0 || switch_type >= num_switches)
			{
			    printf
				("Error in check_rr_graph:  node %d has a switch type %d.\n"
				 "Switch type is out of range.\n", inode,
				 switch_type);
			    exit(1);
			}

		    if(switch_inf[switch_type].buffered)
			switch_types_from_current_to_node[to_node] |=
			    BUF_FLAG;
		    else
			switch_types_from_current_to_node[to_node] |=
			    PTRANS_FLAG;

		}		/* End for all edges of node. */


	    for(iedge = 0; iedge < num_edges; iedge++)
		{
		    to_node = rr_node[inode].edges[iedge];

		    if(num_edges_from_current_to_node[to_node] > 1)
			{
			    to_rr_type = rr_node[to_node].type;

			    if((to_rr_type != CHANX && to_rr_type != CHANY) ||
			       (rr_type != CHANX && rr_type != CHANY))
				{
				    printf
					("Error in check_rr_graph:  node %d connects to node %d "
					 "%d times.\n", inode, to_node,
					 num_edges_from_current_to_node
					 [to_node]);
				    exit(1);
				}

			    /* Between two wire segments.  Two connections are legal only if  *
			     * one connection is a buffer and the other is a pass transistor. */

			    else if(num_edges_from_current_to_node[to_node] !=
				    2
				    ||
				    switch_types_from_current_to_node[to_node]
				    != BUF_AND_PTRANS_FLAG)
				{
				    printf
					("Error in check_rr_graph:  node %d connects to node %d "
					 "%d times.\n", inode, to_node,
					 num_edges_from_current_to_node
					 [to_node]);
				    exit(1);
				}
			}

		    num_edges_from_current_to_node[to_node] = 0;
		    switch_types_from_current_to_node[to_node] = 0;
		}

	    /* Slow test below.  Leave commented out most of the time. */

#ifdef DEBUG
	    check_pass_transistors(inode);
#endif

	}			/* End for all rr_nodes */


/* I built a list of how many edges went to everything in the code above -- *
 * now I check that everything is reachable.                                */
	is_fringe_warning_sent = FALSE;

    for(inode = 0; inode < num_rr_nodes; inode++)
	{
	    rr_type = rr_node[inode].type;

	    if(rr_type != SOURCE)
		{
		    if(total_edges_to_node[inode] < 1 &&
		       !rr_node_is_global_clb_ipin(inode))
			{
				boolean is_fringe;
				boolean is_wire;

			    /* A global FB input pin will not have any edges, and neither will  *
			     * a SOURCE.  Anything else is an error.                             */

				is_fringe =  ((rr_node[inode].xlow == 1) || (rr_node[inode].ylow == 1) 
						|| (rr_node[inode].xhigh == nx) || (rr_node[inode].yhigh == ny));
				is_wire = (rr_node[inode].type == CHANX || rr_node[inode].type == CHANY);  

				if (!is_fringe && !is_wire)
				{
					printf ("Error in check_rr_graph:  node %d has no fanin.\n", inode);
					exit(1);
				}
				else if (!is_fringe_warning_sent) 
				{
					printf ("WARNING: in check_rr_graph:  fringe node %d has no fanin.\n"
							"This is possible on the fringe for low Fc_out, N, and certain Lengths\n"
							, inode);
					is_fringe_warning_sent = TRUE;
				}
			}
		}

	    else
		{		/* SOURCE.  No fanin for now; change if feedthroughs allowed. */
		    if(total_edges_to_node[inode] != 0)
			{
			    printf
				("Error in check_rr_graph:  SOURCE node %d has a fanin\n"
				 "\tof %d, expected 0.\n", inode,
				 total_edges_to_node[inode]);
			    exit(1);
			}
		}
	}

    free(num_edges_from_current_to_node);
    free(total_edges_to_node);
    free(switch_types_from_current_to_node);
}


static boolean
rr_node_is_global_clb_ipin(int inode)
{

/* Returns TRUE if inode refers to a global FB input pin node.   */

    int ipin;
    t_type_ptr type;

    type = grid[rr_node[inode].xlow][rr_node[inode].ylow].type;

    if(rr_node[inode].type != IPIN)
	return (FALSE);

    ipin = rr_node[inode].ptc_num;

    return (type->is_global_pin[ipin]);
}


void
check_node(int inode,
	   enum e_route_type route_type)
{

/* This routine checks that the rr_node is inside the grid and has a valid  *
 * pin number, etc.                                                         */

    int xlow, ylow, xhigh, yhigh, ptc_num, capacity;
    t_rr_type rr_type;
    t_type_ptr type;
    int nodes_per_chan, tracks_per_node, num_edges, cost_index;
    float C, R;

    rr_type = rr_node[inode].type;
    xlow = rr_node[inode].xlow;
    xhigh = rr_node[inode].xhigh;
    ylow = rr_node[inode].ylow;
    yhigh = rr_node[inode].yhigh;
    ptc_num = rr_node[inode].ptc_num;
    capacity = rr_node[inode].capacity;
    type = NULL;

    if(xlow > xhigh || ylow > yhigh)
	{
	    printf
		("Error in check_node:  rr endpoints are (%d,%d) and (%d,%d).\n",
		 xlow, ylow, xhigh, yhigh);
	    exit(1);
	}

    if(xlow < 0 || xhigh > nx + 1 || ylow < 0 || yhigh > ny + 1)
	{
	    printf
		("Error in check_node:  rr endpoints, (%d,%d) and (%d,%d), \n"
		 "are out of range.\n", xlow, ylow, xhigh, yhigh);
	    exit(1);
	}

    if(ptc_num < 0)
	{
	    printf("Error in check_node.  Inode %d (type %d) had a ptc_num\n"
		   "of %d.\n", inode, rr_type, ptc_num);
	    exit(1);
	}

/* Check that the segment is within the array and such. */

    switch (rr_type)
	{

	case SOURCE:
	case SINK:
	case IPIN:
	case OPIN:
	    /* This is used later as well */
	    type = grid[xlow][ylow].type;

	    if(type == NULL)
		{
		    printf
			("Error in check_node:  Node %d (type %d) is at an illegal\n"
			 " clb location (%d, %d).\n", inode, rr_type, xlow,
			 ylow);
		    exit(1);
		}
	    if(xlow != xhigh || ylow != (yhigh - type->height + 1))
		{
		    printf
			("Error in check_node:  Node %d (type %d) has endpoints of\n"
			 "(%d,%d) and (%d,%d)\n", inode, rr_type, xlow, ylow,