route_common.c

VPR布局布线源码

void
add_to_mod_list(float *fptr)
{

/* This routine adds the floating point pointer (fptr) into a  *
 * linked list that indicates all the pathcosts that have been *
 * modified thus far.                                          */

    struct s_linked_f_pointer *mod_ptr;

    mod_ptr = alloc_linked_f_pointer();

/* Add this element to the start of the modified list. */

    mod_ptr->next = rr_modified_head;
    mod_ptr->fptr = fptr;
    rr_modified_head = mod_ptr;
}


static void
add_to_heap(struct s_heap *hptr)
{

/* Adds an item to the heap, expanding the heap if necessary.             */

    int ito, ifrom;
    struct s_heap *temp_ptr;

    if(heap_tail > heap_size)
	{			/* Heap is full */
	    heap_size *= 2;
	    heap = my_realloc((void *)(heap + 1), heap_size *
			      sizeof(struct s_heap *));
	    heap--;		/* heap goes from [1..heap_size] */
	}

    heap[heap_tail] = hptr;
    ifrom = heap_tail;
    ito = ifrom / 2;
    heap_tail++;

    while((ito >= 1) && (heap[ifrom]->cost < heap[ito]->cost))
	{
	    temp_ptr = heap[ito];
	    heap[ito] = heap[ifrom];
	    heap[ifrom] = temp_ptr;
	    ifrom = ito;
	    ito = ifrom / 2;
	}
}

/*WMF: peeking accessor :) */
boolean
is_empty_heap(void)
{
    return (heap_tail == 1);
}

struct s_heap *
get_heap_head(void)
{

/* Returns a pointer to the smallest element on the heap, or NULL if the     *
 * heap is empty.  Invalid (index == OPEN) entries on the heap are never     *
 * returned -- they are just skipped over.                                   */

    int ito, ifrom;
    struct s_heap *heap_head, *temp_ptr;

    do
	{
	    if(heap_tail == 1)
		{		/* Empty heap. */
		    printf("Empty heap occurred in get_heap_head.\n");
		    printf
			("Some blocks are impossible to connect in this architecture.\n");
		    return (NULL);
		}

	    heap_head = heap[1];	/* Smallest element. */

	    /* Now fix up the heap */

	    heap_tail--;
	    heap[1] = heap[heap_tail];
	    ifrom = 1;
	    ito = 2 * ifrom;

	    while(ito < heap_tail)
		{
		    if(heap[ito + 1]->cost < heap[ito]->cost)
			ito++;
		    if(heap[ito]->cost > heap[ifrom]->cost)
			break;
		    temp_ptr = heap[ito];
		    heap[ito] = heap[ifrom];
		    heap[ifrom] = temp_ptr;
		    ifrom = ito;
		    ito = 2 * ifrom;
		}

	}
    while(heap_head->index == OPEN);	/* Get another one if invalid entry. */

    return (heap_head);
}


void
empty_heap(void)
{

    int i;

    for(i = 1; i < heap_tail; i++)
	free_heap_data(heap[i]);

    heap_tail = 1;
}

#define NCHUNK 200		/* # of various structs malloced at a time. */


static struct s_heap *
alloc_heap_data(void)
{

    int i;
    struct s_heap *temp_ptr;

    if(heap_free_head == NULL)
	{			/* No elements on the free list */
	    heap_free_head = (struct s_heap *)my_malloc(NCHUNK *
							sizeof(struct
							       s_heap));

/* If I want to free this memory, I have to store the original pointer *
 * somewhere.  Not worthwhile right now -- if you need more memory     *
 * for post-routing stages, look into it.                              */

	    for(i = 0; i < NCHUNK - 1; i++)
		(heap_free_head + i)->u.next = heap_free_head + i + 1;
	    (heap_free_head + NCHUNK - 1)->u.next = NULL;
	}

    temp_ptr = heap_free_head;
    heap_free_head = heap_free_head->u.next;
#ifdef DEBUG
    num_heap_allocated++;
#endif
    return (temp_ptr);
}


void
free_heap_data(struct s_heap *hptr)
{

    hptr->u.next = heap_free_head;
    heap_free_head = hptr;
#ifdef DEBUG
    num_heap_allocated--;
#endif
}


void
invalidate_heap_entries(int sink_node,
			int ipin_node)
{

/* Marks all the heap entries consisting of sink_node, where it was reached *
 * via ipin_node, as invalid (OPEN).  Used only by the breadth_first router *
 * and even then only in rare circumstances.                                */

    int i;

    for(i = 1; i < heap_tail; i++)
	{
	    if(heap[i]->index == sink_node
	       && heap[i]->u.prev_node == ipin_node)
		heap[i]->index = OPEN;	/* Invalid. */
	}
}


static struct s_trace *
alloc_trace_data(void)
{

    int i;
    struct s_trace *temp_ptr;

    if(trace_free_head == NULL)
	{			/* No elements on the free list */
	    trace_free_head = (struct s_trace *)my_malloc(NCHUNK *
							  sizeof(struct
								 s_trace));

/* If I want to free this memory, I have to store the original pointer *
 * somewhere.  Not worthwhile right now -- if you need more memory     *
 * for post-routing stages, look into it.                              */

	    for(i = 0; i < NCHUNK - 1; i++)
		(trace_free_head + i)->next = trace_free_head + i + 1;
	    (trace_free_head + NCHUNK - 1)->next = NULL;
	}
    temp_ptr = trace_free_head;
    trace_free_head = trace_free_head->next;
#ifdef DEBUG
    num_trace_allocated++;
#endif
    return (temp_ptr);
}


static void
free_trace_data(struct s_trace *tptr)
{

/* Puts the traceback structure pointed to by tptr on the free list. */

    tptr->next = trace_free_head;
    trace_free_head = tptr;
#ifdef DEBUG
    num_trace_allocated--;
#endif
}


static struct s_linked_f_pointer *
alloc_linked_f_pointer(void)
{

/* This routine returns a linked list element with a float pointer as *
 * the node data.                                                     */

    int i;
    struct s_linked_f_pointer *temp_ptr;

    if(linked_f_pointer_free_head == NULL)
	{
	    /* No elements on the free list */
	    linked_f_pointer_free_head = (struct s_linked_f_pointer *)
		my_malloc(NCHUNK * sizeof(struct s_linked_f_pointer));

/* If I want to free this memory, I have to store the original pointer *
 * somewhere.  Not worthwhile right now -- if you need more memory     * 
 * for post-routing stages, look into it.                              */

	    for(i = 0; i < NCHUNK - 1; i++)
		{
		    (linked_f_pointer_free_head + i)->next =
			linked_f_pointer_free_head + i + 1;
		}
	    (linked_f_pointer_free_head + NCHUNK - 1)->next = NULL;
	}

    temp_ptr = linked_f_pointer_free_head;
    linked_f_pointer_free_head = linked_f_pointer_free_head->next;

#ifdef DEBUG
    num_linked_f_pointer_allocated++;
#endif

    return (temp_ptr);
}


void
print_route(char *route_file)
{

/* Prints out the routing to file route_file.  */

    int inet, inode, ipin, bnum, ilow, jlow, node_block_pin, iclass;
    t_rr_type rr_type;
    struct s_trace *tptr;
    char *name_type[] =
	{ "SOURCE", "SINK", "IPIN", "OPIN", "CHANX", "CHANY" };
    FILE *fp;

    fp = my_fopen(route_file, "w");

    fprintf(fp, "Array size: %d x %d logic blocks.\n", nx, ny);
    fprintf(fp, "\nRouting:");
    for(inet = 0; inet < num_nets; inet++)
	{
	    if(net[inet].is_global == FALSE)
		{
		    fprintf(fp, "\n\nNet %d (%s)\n\n", inet, net[inet].name);
		    tptr = trace_head[inet];

		    while(tptr != NULL)
			{
			    inode = tptr->index;
			    rr_type = rr_node[inode].type;
			    ilow = rr_node[inode].xlow;
			    jlow = rr_node[inode].ylow;

			    fprintf(fp, "%6s (%d,%d) ", name_type[rr_type],
				    ilow, jlow);

			    if((ilow != rr_node[inode].xhigh) || (jlow !=
								  rr_node
								  [inode].
								  yhigh))
				fprintf(fp, "to (%d,%d) ",
					rr_node[inode].xhigh,
					rr_node[inode].yhigh);

			    switch (rr_type)
				{

				case IPIN:
				case OPIN:
				    if(grid[ilow][jlow].type == IO_TYPE)
					{
					    fprintf(fp, " Pad: ");
					}
				    else
					{	/* IO Pad. */
					    fprintf(fp, " Pin: ");
					}
				    break;

				case CHANX:
				case CHANY:
				    fprintf(fp, " Track: ");
				    break;

				case SOURCE:
				case SINK:
				    if(grid[ilow][jlow].type == IO_TYPE)
					{
					    fprintf(fp, " Pad: ");
					}
				    else
					{	/* IO Pad. */
					    fprintf(fp, " Class: ");
					}
				    break;

				default:
				    printf
					("Error in print_route:  Unexpected traceback element "
					 "type: %d (%s).\n", rr_type,
					 name_type[rr_type]);
				    exit(1);
				    break;
				}

			    fprintf(fp, "%d  ", rr_node[inode].ptc_num);

/* Uncomment line below if you're debugging and want to see the switch types *
 * used in the routing.                                                      */
/*          fprintf (fp, "Switch: %d", tptr->iswitch);    */

			    fprintf(fp, "\n");

			    tptr = tptr->next;
			}
		}

	    else
		{		/* Global net.  Never routed. */
		    fprintf(fp, "\n\nNet %d (%s): global net connecting:\n\n",
			    inet, net[inet].name);

		    for(ipin = 0; ipin <= net[inet].num_sinks; ipin++)
			{
			    bnum = net[inet].node_block[ipin];

			    node_block_pin = net[inet].node_block_pin[ipin];
			    iclass =
				block[bnum].type->pin_class[node_block_pin];

			    fprintf(fp,
				    "Block %s (#%d) at (%d, %d), Pin class %d.\n",
				    block[bnum].name, bnum, block[bnum].x,
				    block[bnum].y, iclass);
			}
		}
	}

    fclose(fp);

#ifdef CREATE_ECHO_FILES
    fp = my_fopen("mem.echo", "w");
    fprintf(fp, "\nNum_heap_allocated: %d   Num_trace_allocated: %d\n",
	    num_heap_allocated, num_trace_allocated);
    fprintf(fp, "Num_linked_f_pointer_allocated: %d\n",
	    num_linked_f_pointer_allocated);
    fclose(fp);
#endif /* CREATE_ECHO_FILES */

}


void
reserve_locally_used_opins(float pres_fac,
			   boolean rip_up_local_opins,
			   t_ivec ** fb_opins_used_locally)
{

/* If some subblock outputs are hooked directly to FB outputs, then      *
 * some FB outputs are occupied if their associated subblock is used     *
 * locally, even though the inter-FB netlist does not say those outputs  *
 * have to connect to anything.  This is important when you have          *
 * logically equivalent outputs.  Code below makes sure any FB outputs   *
 * that are used by being directly hooked to subblocks get properly       *
 * reserved.                                                              */

    int iblk, num_local_opin, inode, from_node, iconn, num_edges, to_node;
    int iclass, ipin;
    float cost;
    struct s_heap *heap_head_ptr;
    t_type_ptr type;

    if(rip_up_local_opins)
	{
	    for(iblk = 0; iblk < num_blocks; iblk++)
		{
		    type = block[iblk].type;
		    for(iclass = 0; iclass < type->num_class; iclass++)
			{
			    num_local_opin =
				fb_opins_used_locally[iblk][iclass].nelem;
			    /* Always 0 for pads and for RECEIVER (IPIN) classes */
			    for(ipin = 0; ipin < num_local_opin; ipin++)
				{
				    inode =
					fb_opins_used_locally[iblk][iclass].
					list[ipin];
				    adjust_one_rr_occ_and_pcost(inode, -1,
								pres_fac);
				}
			}
		}
	}

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

		    if(num_local_opin != 0)
			{	/* Have to reserve (use) some OPINs */
			    from_node = rr_blk_source[iblk][iclass];
			    num_edges = rr_node[from_node].num_edges;
			    for(iconn = 0; iconn < num_edges; iconn++)
				{
				    to_node = rr_node[from_node].edges[iconn];
				    cost = get_rr_cong_cost(to_node);
				    node_to_heap(to_node, cost, OPEN, OPEN,
						 0., 0.);
				}

			    for(ipin = 0; ipin < num_local_opin; ipin++)
				{
				    heap_head_ptr = get_heap_head();
				    inode = heap_head_ptr->index;
				    adjust_one_rr_occ_and_pcost(inode, 1,
								pres_fac);
				    fb_opins_used_locally[iblk][iclass].
					list[ipin] = inode;
				    free_heap_data(heap_head_ptr);
				}

			    empty_heap();
			}
		}
	}
}


static void
adjust_one_rr_occ_and_pcost(int inode,
			    int add_or_sub,
			    float pres_fac)
{

/* Increments or decrements (depending on add_or_sub) the occupancy of    *
 * one rr_node, and adjusts the present cost of that node appropriately.  */

    int occ, capacity;

    occ = rr_node[inode].occ + add_or_sub;
    capacity = rr_node[inode].capacity;
    rr_node[inode].occ = occ;

    if(occ < capacity)
	{
	    rr_node_route_inf[inode].pres_cost = 1.;
	}
    else
	{
	    rr_node_route_inf[inode].pres_cost = 1. + (occ + 1 - capacity) *
		pres_fac;
	}
}