route_common.c

VPR布局布线源码

    inode = hptr->index;

#ifdef DEBUG
    rr_type = rr_node[inode].type;
    if(rr_type != SINK)
	{
	    printf("Error in update_traceback.  Expected type = SINK (%d).\n",
		   SINK);
	    printf("Got type = %d while tracing back net %d.\n", rr_type,
		   inet);
	    exit(1);
	}
#endif

    tptr = alloc_trace_data();	/* SINK on the end of the connection */
    tptr->index = inode;
    tptr->iswitch = OPEN;
    tptr->next = NULL;
    temptail = tptr;		/* This will become the new tail at the end */
    /* of the routine.                          */

/* Now do it's predecessor. */

    inode = hptr->u.prev_node;
    iedge = hptr->prev_edge;

    while(inode != NO_PREVIOUS)
	{
	    prevptr = alloc_trace_data();
	    prevptr->index = inode;
	    prevptr->iswitch = rr_node[inode].switches[iedge];
	    prevptr->next = tptr;
	    tptr = prevptr;

	    iedge = rr_node_route_inf[inode].prev_edge;
	    inode = rr_node_route_inf[inode].prev_node;
	}

    if(trace_tail[inet] != NULL)
	{
	    trace_tail[inet]->next = tptr;	/* Traceback ends with tptr */
	    ret_ptr = tptr->next;	/* First new segment.       */
	}
    else
	{			/* This was the first "chunk" of the net's routing */
	    trace_head[inet] = tptr;
	    ret_ptr = tptr;	/* Whole traceback is new. */
	}

    trace_tail[inet] = temptail;
    return (ret_ptr);
}


void
reset_path_costs(void)
{

/* The routine sets the path_cost to HUGE_FLOAT for all channel segments   *
 * touched by previous routing phases.                                     */

    struct s_linked_f_pointer *mod_ptr;

#ifdef DEBUG
    int num_mod_ptrs;
#endif

/* The traversal method below is slightly painful to make it faster. */

    if(rr_modified_head != NULL)
	{
	    mod_ptr = rr_modified_head;

#ifdef DEBUG
	    num_mod_ptrs = 1;
#endif

	    while(mod_ptr->next != NULL)
		{
		    *(mod_ptr->fptr) = HUGE_FLOAT;
		    mod_ptr = mod_ptr->next;
#ifdef DEBUG
		    num_mod_ptrs++;
#endif
		}
	    *(mod_ptr->fptr) = HUGE_FLOAT;	/* Do last one. */

/* Reset the modified list and put all the elements back in the free   *
 * list.                                                               */

	    mod_ptr->next = linked_f_pointer_free_head;
	    linked_f_pointer_free_head = rr_modified_head;
	    rr_modified_head = NULL;

#ifdef DEBUG
	    num_linked_f_pointer_allocated -= num_mod_ptrs;
#endif
	}
}


float
get_rr_cong_cost(int inode)
{

/* Returns the *congestion* cost of using this rr_node. */

    short cost_index;
    float cost;

    cost_index = rr_node[inode].cost_index;
    cost = rr_indexed_data[cost_index].base_cost *
	rr_node_route_inf[inode].acc_cost *
	rr_node_route_inf[inode].pres_cost;
    return (cost);
}


void
mark_ends(int inet)
{

/* Mark all the SINKs of this net as targets by setting their target flags  *
 * to the number of times the net must connect to each SINK.  Note that     *
 * this number can occassionally be greater than 1 -- think of connecting   *
 * the same net to two inputs of an and-gate (and-gate inputs are logically *
 * equivalent, so both will connect to the same SINK).                      */

    int ipin, inode;

    for(ipin = 1; ipin <= net[inet].num_sinks; ipin++)
	{
	    inode = net_rr_terminals[inet][ipin];
	    rr_node_route_inf[inode].target_flag++;
	}
}


void
node_to_heap(int inode,
	     float cost,
	     int prev_node,
	     int prev_edge,
	     float backward_path_cost,
	     float R_upstream)
{

/* Puts an rr_node on the heap, if the new cost given is lower than the     *
 * current path_cost to this channel segment.  The index of its predecessor *
 * is stored to make traceback easy.  The index of the edge used to get     *
 * from its predecessor to it is also stored to make timing analysis, etc.  *
 * easy.  The backward_path_cost and R_upstream values are used only by the *
 * timing-driven router -- the breadth-first router ignores them.           */

    struct s_heap *hptr;

    if(cost >= rr_node_route_inf[inode].path_cost)
	return;

    hptr = alloc_heap_data();
    hptr->index = inode;
    hptr->cost = cost;
    hptr->u.prev_node = prev_node;
    hptr->prev_edge = prev_edge;
    hptr->backward_path_cost = backward_path_cost;
    hptr->R_upstream = R_upstream;
    add_to_heap(hptr);
}


void
free_traceback(int inet)
{

/* Puts the entire traceback (old routing) for this net on the free list *
 * and sets the trace_head pointers etc. for the net to NULL.            */

    struct s_trace *tptr, *tempptr;

    tptr = trace_head[inet];

    while(tptr != NULL)
	{
	    tempptr = tptr->next;
	    free_trace_data(tptr);
	    tptr = tempptr;
	}

    trace_head[inet] = NULL;
    trace_tail[inet] = NULL;
}


t_ivec **
alloc_route_structs(t_subblock_data subblock_data)
{

/* Allocates the data structures needed for routing.    */

    t_ivec **fb_opins_used_locally;

    trace_head = (struct s_trace **)my_calloc(num_nets,
					      sizeof(struct s_trace *));
    trace_tail = (struct s_trace **)my_malloc(num_nets *
					      sizeof(struct s_trace *));

    heap_size = nx * ny;
    heap = (struct s_heap **)my_malloc(heap_size * sizeof(struct s_heap *));
    heap--;			/* heap stores from [1..heap_size] */
    heap_tail = 1;

    route_bb = (struct s_bb *)my_malloc(num_nets * sizeof(struct s_bb));

    fb_opins_used_locally =
	alloc_and_load_clb_opins_used_locally(subblock_data);

    return (fb_opins_used_locally);
}


struct s_trace **
alloc_saved_routing(t_ivec ** fb_opins_used_locally,
		    t_ivec *** saved_clb_opins_used_locally_ptr)
{

/* Allocates data structures into which the key routing data can be saved,   *
 * allowing the routing to be recovered later (e.g. after a another routing  *
 * is attempted).                                                            */

    struct s_trace **best_routing;
    t_ivec **saved_clb_opins_used_locally;
    int iblk, iclass, num_local_opins;
    t_type_ptr type;

    best_routing = (struct s_trace **)my_calloc(num_nets,
						sizeof(struct s_trace *));

    saved_clb_opins_used_locally =
	(t_ivec **) my_malloc(num_blocks * sizeof(t_ivec *));

    for(iblk = 0; iblk < num_blocks; iblk++)
	{
	    type = block[iblk].type;
	    saved_clb_opins_used_locally[iblk] =
		(t_ivec *) my_malloc(type->num_class * sizeof(t_ivec));
	    for(iclass = 0; iclass < type->num_class; iclass++)
		{
		    num_local_opins =
			fb_opins_used_locally[iblk][iclass].nelem;
		    saved_clb_opins_used_locally[iblk][iclass].nelem =
			num_local_opins;

		    if(num_local_opins == 0)
			{
			    saved_clb_opins_used_locally[iblk][iclass].list =
				NULL;
			}
		    else
			{
			    saved_clb_opins_used_locally[iblk][iclass].list =
				(int *)my_malloc(num_local_opins *
						 sizeof(int));
			}
		}
	}

    *saved_clb_opins_used_locally_ptr = saved_clb_opins_used_locally;
    return (best_routing);
}


static t_ivec **
alloc_and_load_clb_opins_used_locally(t_subblock_data subblock_data)
{

/* Allocates and loads the data needed to make the router reserve some FB  *
 * output pins for connections made locally within a FB (if the netlist    *
 * specifies that this is necessary).                                       */

    t_ivec **fb_opins_used_locally;
    int *num_subblocks_per_block;
    t_subblock **subblock_inf;
    int iblk, isub, clb_pin, opin, iclass, num_local_opins;
    int class_low, class_high;
    t_type_ptr type;

    fb_opins_used_locally =
	(t_ivec **) my_malloc(num_blocks * sizeof(t_ivec *));
    num_subblocks_per_block = subblock_data.num_subblocks_per_block;
    subblock_inf = subblock_data.subblock_inf;

    for(iblk = 0; iblk < num_blocks; iblk++)
	{
	    type = block[iblk].type;
	    get_class_range_for_block(iblk, &class_low, &class_high);
	    fb_opins_used_locally[iblk] =
		(t_ivec *) my_malloc(type->num_class * sizeof(t_ivec));
	    for(iclass = 0; iclass < type->num_class; iclass++)
		fb_opins_used_locally[iblk][iclass].nelem = 0;

	    for(isub = 0; isub < num_subblocks_per_block[iblk]; isub++)
		{
		    for(opin = 0;
			opin < block[iblk].type->max_subblock_outputs; opin++)
			{
			    clb_pin = subblock_inf[iblk][isub].outputs[opin];

			    /* Subblock output used only locally, but must connect to a FB OPIN?  */
			    if(clb_pin != OPEN
			       && block[iblk].nets[clb_pin] == OPEN)
				{
				    iclass = type->pin_class[clb_pin];
				    /* Check to make sure class is in same range as that assigned to block */
				    assert(iclass >= class_low
					   && iclass <= class_high);
				    fb_opins_used_locally[iblk][iclass].
					nelem++;
				}
			}
		}

	    for(iclass = 0; iclass < type->num_class; iclass++)
		{
		    num_local_opins =
			fb_opins_used_locally[iblk][iclass].nelem;

		    if(num_local_opins == 0)
			fb_opins_used_locally[iblk][iclass].list = NULL;
		    else
			fb_opins_used_locally[iblk][iclass].list =
			    (int *)my_malloc(num_local_opins * sizeof(int));
		}
	}

    return (fb_opins_used_locally);
}

void
free_trace_structs(void)
{
    /*the trace lists are only freed after use by the timing-driven placer */
    /*Do not  free them after use by the router, since stats, and draw  */
    /*routines use the trace values */
    int i;

    for(i = 0; i < num_nets; i++)
	free_traceback(i);

    free(trace_head);
    free(trace_tail);
    trace_head = NULL;
    trace_tail = NULL;
}

void
free_route_structs(t_ivec ** fb_opins_used_locally)
{

/* Frees the temporary storage needed only during the routing.  The  *
 * final routing result is not freed.                                */
    int i;

    free(heap + 1);
    free(route_bb);

    heap = NULL;		/* Defensive coding:  crash hard if I use these. */
    route_bb = NULL;

    for(i = 0; i < num_blocks; i++)
	{
	    free_ivec_vector(fb_opins_used_locally[i], 0,
			     block[i].type->num_class - 1);
	}
    free(fb_opins_used_locally);

/* NB:  Should use my chunk_malloc for tptr, hptr, and mod_ptr structures. *
 * I could free everything except the tptrs at the end then.               */

}


void
free_saved_routing(struct s_trace **best_routing,
		   t_ivec ** saved_clb_opins_used_locally)
{

/* Frees the data structures needed to save a routing.                     */
    int i;

    free(best_routing);
    for(i = 0; i < num_blocks; i++)
	{
	    free_ivec_vector(saved_clb_opins_used_locally[i], 0,
			     block[i].type->num_class - 1);
	}
    free(saved_clb_opins_used_locally);
}


void
alloc_and_load_rr_node_route_structs(void)
{

/* Allocates some extra information about each rr_node that is used only   *
 * during routing.                                                         */

    int inode;

    if(rr_node_route_inf != NULL)
	{
	    printf("Error in alloc_and_load_rr_node_route_structs:  \n"
		   "old rr_node_route_inf array exists.\n");
	    exit(1);
	}

    rr_node_route_inf = my_malloc(num_rr_nodes * sizeof(t_rr_node_route_inf));

    for(inode = 0; inode < num_rr_nodes; inode++)
	{
	    rr_node_route_inf[inode].prev_node = NO_PREVIOUS;
	    rr_node_route_inf[inode].prev_edge = NO_PREVIOUS;
	    rr_node_route_inf[inode].pres_cost = 1.;
	    rr_node_route_inf[inode].acc_cost = 1.;
	    rr_node_route_inf[inode].path_cost = HUGE_FLOAT;
	    rr_node_route_inf[inode].target_flag = 0;
	}
}


void
free_rr_node_route_structs(void)
{

/* Frees the extra information about each rr_node that is needed only      *
 * during routing.                                                         */

    free(rr_node_route_inf);
    rr_node_route_inf = NULL;	/* Mark as free */
}

/* RESEARCH TODO: Bounding box heuristic needs to be redone for heterogeneous blocks */
static void
load_route_bb(int bb_factor)
{

/* This routine loads the bounding box arrays used to limit the space  *
 * searched by the maze router when routing each net.  The search is   *
 * limited to channels contained with the net bounding box expanded    *
 * by bb_factor channels on each side.  For example, if bb_factor is   *
 * 0, the maze router must route each net within its bounding box.     *
 * If bb_factor = nx, the maze router will search every channel in     *
 * the FPGA if necessary.  The bounding boxes returned by this routine *
 * are different from the ones used by the placer in that they are     * 
 * clipped to lie within (0,0) and (nx+1,ny+1) rather than (1,1) and   *
 * (nx,ny).                                                            */

    int k, xmax, ymax, xmin, ymin, x, y, inet;

    for(inet = 0; inet < num_nets; inet++)
	{
	    x = block[net[inet].node_block[0]].x;
	    y = block[net[inet].node_block[0]].y;

	    xmin = x;
	    ymin = y;
	    xmax = x;
	    ymax = y;

	    for(k = 1; k <= net[inet].num_sinks; k++)
		{
		    x = block[net[inet].node_block[k]].x;
		    y = block[net[inet].node_block[k]].y;

		    if(x < xmin)
			{
			    xmin = x;
			}
		    else if(x > xmax)
			{
			    xmax = x;
			}

		    if(y < ymin)
			{
			    ymin = y;
			}
		    else if(y > ymax)
			{
			    ymax = y;
			}
		}

	    /* Want the channels on all 4 sides to be usuable, even if bb_factor = 0. */

	    xmin -= 1;
	    ymin -= 1;

	    /* Expand the net bounding box by bb_factor, then clip to the physical *
	     * chip area.                                                          */

	    route_bb[inet].xmin = max(xmin - bb_factor, 0);
	    route_bb[inet].xmax = min(xmax + bb_factor, nx + 1);
	    route_bb[inet].ymin = max(ymin - bb_factor, 0);
	    route_bb[inet].ymax = min(ymax + bb_factor, ny + 1);
	}
}