check_route.c

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

    num_adj = 0;

    from_type = rr_node[from_node].type;
    from_xlow = rr_node[from_node].xlow;
    from_ylow = rr_node[from_node].ylow;
    from_xhigh = rr_node[from_node].xhigh;
    from_yhigh = rr_node[from_node].yhigh;
    from_ptc = rr_node[from_node].ptc_num;
    to_type = rr_node[to_node].type;
    to_xlow = rr_node[to_node].xlow;
    to_ylow = rr_node[to_node].ylow;
    to_xhigh = rr_node[to_node].xhigh;
    to_yhigh = rr_node[to_node].yhigh;
    to_ptc = rr_node[to_node].ptc_num;

    switch (from_type)
	{

	case SOURCE:
	    assert(to_type == OPIN);
	    if(from_xlow == to_xlow && from_ylow == to_ylow
	       && from_xhigh == to_xhigh && from_yhigh == to_yhigh)
		{

		    from_grid_type = grid[from_xlow][from_ylow].type;
		    to_grid_type = grid[to_xlow][to_ylow].type;
		    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:
	    assert(to_type == CHANX || to_type == CHANY);
	    num_adj += pin_and_chan_adjacent(from_node, to_node);

	    break;

	case IPIN:
	    assert(to_type == SINK);
	    if(from_xlow == to_xlow && from_ylow == to_ylow
	       && from_xhigh == to_xhigh && from_yhigh == to_yhigh)
		{

		    from_grid_type = grid[from_xlow][from_ylow].type;
		    to_grid_type = grid[to_xlow][to_ylow].type;
		    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 += pin_and_chan_adjacent(to_node, from_node);
		}
	    else if(to_type == CHANX)
		{
		    from_xhigh = rr_node[from_node].xhigh;
		    to_xhigh = rr_node[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
		{
		    assert(0);
		}
	    break;

	case CHANY:
	    if(to_type == IPIN)
		{
		    num_adj += pin_and_chan_adjacent(to_node, from_node);
		}
	    else if(to_type == CHANY)
		{
		    from_yhigh = rr_node[from_node].yhigh;
		    to_yhigh = rr_node[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
		{
		    assert(0);
		}
	    break;

	default:
	    break;

	}

    if(num_adj == 1)
	return (TRUE);
    else if(num_adj == 0)
	return (FALSE);

    printf("Error in check_adjacent: num_adj = %d. Expected 0 or 1.\n",
	   num_adj);
    exit(1);
}


static int
chanx_chany_adjacent(int chanx_node,
		     int 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;

    chanx_y = rr_node[chanx_node].ylow;
    chanx_xlow = rr_node[chanx_node].xlow;
    chanx_xhigh = rr_node[chanx_node].xhigh;

    chany_x = rr_node[chany_node].xlow;
    chany_ylow = rr_node[chany_node].ylow;
    chany_yhigh = rr_node[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);
}


static int
pin_and_chan_adjacent(int pin_node,
		      int chan_node)
{

/* Checks if pin_node is adjacent to chan_node.  It returns 1 if the two   *
 * nodes are adjacent and 0 if they are not (any other value means there's *
 * a bug in this routine).                                                 */

    int num_adj, pin_xlow, pin_ylow, pin_xhigh, pin_yhigh, chan_xlow,
	chan_ylow, chan_xhigh, chan_yhigh;
    int pin_ptc, i;
    t_rr_type chan_type;
    t_type_ptr pin_grid_type;

    num_adj = 0;
    pin_xlow = rr_node[pin_node].xlow;
    pin_ylow = rr_node[pin_node].ylow;
    pin_xhigh = rr_node[pin_node].xhigh;
    pin_yhigh = rr_node[pin_node].yhigh;
    pin_grid_type = grid[pin_xlow][pin_ylow].type;
    pin_ptc = rr_node[pin_node].ptc_num;
    chan_type = rr_node[chan_node].type;
    chan_xlow = rr_node[chan_node].xlow;
    chan_ylow = rr_node[chan_node].ylow;
    chan_xhigh = rr_node[chan_node].xhigh;
    chan_yhigh = rr_node[chan_node].yhigh;

    if(chan_type == CHANX)
	{
	    if(chan_ylow == pin_yhigh)
		{		/* CHANX above FB */
		    if(pin_grid_type->
		       pinloc[pin_grid_type->height - 1][TOP][pin_ptc] == 1
		       && pin_xlow <= chan_xhigh && pin_xhigh >= chan_xlow)
			num_adj++;
		}
	    else if(chan_ylow == pin_ylow - 1)
		{		/* CHANX below FB */
		    if(pin_grid_type->pinloc[0][BOTTOM][pin_ptc] == 1
		       && pin_xlow <= chan_xhigh && pin_xhigh >= chan_xlow)
			num_adj++;
		}
	}
    else if(chan_type == CHANY)
	{
	    for(i = 0; i < pin_grid_type->height; i++)
		{
		    if(chan_xlow == pin_xhigh)
			{	/* CHANY to right of FB */
			    if(pin_grid_type->pinloc[i][RIGHT][pin_ptc] == 1
			       && pin_ylow <= chan_yhigh
			       && pin_yhigh >= chan_ylow)
				num_adj++;
			}
		    else if(chan_xlow == pin_xlow - 1)
			{	/* CHANY to left of FB */
			    if(pin_grid_type->pinloc[i][LEFT][pin_ptc] == 1
			       && pin_ylow <= chan_yhigh
			       && pin_yhigh >= chan_ylow)
				num_adj++;
			}
		}
	}
    return (num_adj);
}


static void
recompute_occupancy_from_scratch(t_ivec ** fb_opins_used_locally)
{

/* This routine updates the occ field in the rr_node 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 inode, inet, iblk, iclass, ipin, num_local_opins;
    struct s_trace *tptr;

/* First set the occupancy of everything to zero. */

    for(inode = 0; inode < num_rr_nodes; inode++)
	rr_node[inode].occ = 0;

/* Now go through each net and count the tracks and pins used everywhere */

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

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

	    tptr = trace_head[inet];
	    if(tptr == NULL)
		continue;

	    for(;;)
		{
		    inode = tptr->index;
		    rr_node[inode].occ++;

		    if(rr_node[inode].type == SINK)
			{
			    tptr = tptr->next;	/* Skip next segment. */
			    if(tptr == NULL)
				break;
			}

		    tptr = tptr->next;
		}
	}

/* Now update the occupancy of each of the "locally used" OPINs on each FB *
 * (FB outputs used up by being directly wired to subblocks used only      *
 * locally).                                                                */

    for(iblk = 0; iblk < num_blocks; iblk++)
	{
	    for(iclass = 0; iclass < block[iblk].type->num_class; iclass++)
		{
		    num_local_opins =
			fb_opins_used_locally[iblk][iclass].nelem;
		    /* Will always be 0 for pads or SINK classes. */
		    for(ipin = 0; ipin < num_local_opins; ipin++)
			{
			    inode =
				fb_opins_used_locally[iblk][iclass].
				list[ipin];
			    rr_node[inode].occ++;
			}
		}
	}
}


static void
check_locally_used_fb_opins(t_ivec ** fb_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, iblk, num_local_opins, inode, ipin;
    t_rr_type rr_type;

    for(iblk = 0; iblk < num_blocks; iblk++)
	{
	    for(iclass = 0; iclass < block[iblk].type->num_class; iclass++)
		{
		    num_local_opins =
			fb_opins_used_locally[iblk][iclass].nelem;
		    /* Always 0 for pads and for SINK classes */

		    for(ipin = 0; ipin < num_local_opins; ipin++)
			{
			    inode =
				fb_opins_used_locally[iblk][iclass].
				list[ipin];
			    check_node_and_range(inode, route_type);	/* Node makes sense? */

			    /* Now check that node is an OPIN of the right type. */

			    rr_type = rr_node[inode].type;
			    if(rr_type != OPIN)
				{
				    printf
					("Error in check_locally_used_opins:  Block #%d (%s)\n"
					 "\tclass %d locally used OPIN is of the wrong rr_type --\n"
					 "\tit is rr_node #%d of type %d.\n",
					 iblk, block[iblk].name, iclass,
					 inode, rr_type);
				    exit(1);
				}

			    ipin = rr_node[inode].ptc_num;
			    if(block[iblk].type->pin_class[ipin] != iclass)
				{
				    printf
					("Error in check_locally_used_opins:  Block #%d (%s):\n"
					 "\tExpected class %d locally used OPIN, got class %d."
					 "\trr_node #: %d.\n", iblk,
					 block[iblk].name, iclass,
					 block[iblk].type->pin_class[ipin],
					 inode);
				    exit(1);
				}
			}
		}
	}
}


static void
check_node_and_range(int 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.                         */

    if(inode < 0 || inode >= num_rr_nodes)
	{
	    printf
		("Error in check_node_and_range:  rr_node #%d is out of legal "
		 "\trange (0 to %d).\n", inode, num_rr_nodes - 1);
	    exit(1);
	}
    check_node(inode, route_type);
}