/* * Copyright 1996 University of Toronto * * Permission to use, copy, modify, distribute, and sell this software and its * documentation for any purpose is hereby granted without fee, provided that * the above copyright notice appear in all copies and that both that * copyright notice and this permission notice appear in supporting * documentation, and that the name of the University of Toronto not be used * in advertising or publicity pertaining to distribution of the software * without specific, written prior permission. The University of Toronto * makes no representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * THE UNIVERSITY OF TORONTO DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, * IN NO EVENT SHALL THE UNIVERSITY OF TORONTO BE LIABLE FOR ANY SPECIAL, * INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR * PERFORMANCE OF THIS SOFTWARE. */ /* Authors: Guy Lemieux and Dan Vranesic Department of Electrical and Computer Engineering 10 King's College Road University of Toronto, Toronto M5S 3G4, Canada e-mail: lemieux / danv @eecg.toronto.edu */ /* * VPR to SEGA Netlist conversion tool. * * This tool reads in a VPR netlist, one multinet at a time. * It outputs a SEGA netlist, one two-point net at a time. * The output is typically a minimum-distance spanning tree * according to Prim's algorithm. It connects the source to * the closest sink, then it connects successive sinks to the * closest of the source or previously connected sinks. * * Usage: vpr2sega input_vpr.r output_sega.sega [ nosavemem | nodoglegs ] * * Inputs: input_vpr.r a VPR global routing output netlist (.r file) * * Outputs: output_sega.sega a SEGA-compatible input file * * Options: * nosavemem doesn't bother to economize memory usage. * the nosavemem algorithm may be more stable. * the default is to save memory (usually faster too). * * nodoglegs when this is set, every SEGA net is output as a * source-sink pair instead of as an MST. that is, * one end of the two-point net is always the source. * this causes the SEGA description to be bigger and * SEGA to use more memory, but it prevents SEGA from * using input pin switches to change tracks. since * this mode uses a different algorithm, the nosavemem * option is incompatible with nodoglegs. * * Caveats: X, Y default maximum values are about 200 x 200 (UPPER) in * SEGA FPGA coordinates. Recompile if you need to change this. * */ #include #include #include #include #define MAX_STR_LEN 80 #ifndef UPPER #define UPPER 200 #endif /* don't change this yet, FAST doesn't work */ #ifndef FAST #ifndef SAFE #define SAFE #endif #endif /* * Globals */ int maxx = 0; /* largest coords seen so far */ int maxy = 0; int SAVE_MEM = 1; int NO_DOGLEGS = 0; FILE *fp; FILE *fpout; int net_number; /* net currently working on */ char net_name[MAX_STR_LEN]; enum /*directions*/ { NORTH, EAST, SOUTH, WEST }; enum /*class*/ { UNDEFINED, CHANX, CHANY, SBLOCK, IPIN, OPIN }; struct elem { short int x; short int y; signed char pinnum; signed char class; int distance; /* distance from root */ struct elem *prev_dir; /* 'up' or 'back' pointer, one of dirs[] */ struct elem *dirs[4]; /* 4 possible dirs to connect in */ }; struct elem *elem_free_list = NULL; struct elem *fpga[UPPER][UPPER]; char fpga_sink[UPPER][UPPER]; int found_num_sinks; int num_sinks; int num_reused = 0; int num_alloced = 0; char str[MAX_STR_LEN]; /* construct a forest of numerous trees for the same net */ /* each tree is rooted at a different source/sink */ /* we start with one tree rooted at the source and build from there */ struct tree { struct elem *root; struct tree *next; }; struct tree *forest = NULL; struct leaf_pq_elem { struct elem *root; struct elem *leaf; signed short stored_net; int distance; }; /* don't need strict relationship here with UPPER */ /* num entries should be (max#sinks)*(max#sinks)/2+1 */ struct leaf_pq_elem *leaf_pq[UPPER*UPPER*UPPER]; /* element 0 is not used! */ struct leaf_pq_elem *lpqe_free_list = NULL; int num_leaf_pq_entries; int biggest_pq; struct leaf_pq_elem *my_alloc_lpqe(); void my_free_lpqe( struct leaf_pq_elem *lpqe ); void print_net_recurse( struct elem *leaf ); void leaf_pq_print() { int i; struct leaf_pq_elem *lpqe; for( i=1; i<=num_leaf_pq_entries; i++ ) { lpqe = leaf_pq[i]; fprintf( fpout, "%d,%d -> %d,%d = %d\n", lpqe->root->x, lpqe->root->y, lpqe->leaf->x, lpqe->leaf->y, lpqe->leaf->distance ); if( lpqe->root->x == 10 && lpqe->root->y == 16 && lpqe->leaf->x == 10 && lpqe->leaf->y == 10 ) { print_net_recurse( lpqe->leaf ); fprintf( fpout, "%d %d 0 %d\n\n\n", lpqe->leaf->x, lpqe->leaf->y, lpqe->leaf->pinnum ); } } } void leaf_pq_init() { int i = num_leaf_pq_entries; for( ; i>0; i-- ) { my_free_lpqe( leaf_pq[i] ); } memset( leaf_pq, 0, (1+num_leaf_pq_entries)*sizeof(struct leaf_pq_elem*) ); num_leaf_pq_entries = 0; } struct leaf_pq_elem *leaf_pq_pop() { int i; struct leaf_pq_elem *lpqe; lpqe = leaf_pq[1]; if( num_leaf_pq_entries == 0 ) return NULL; else if( num_leaf_pq_entries == 1 ) { leaf_pq[1] = NULL; num_leaf_pq_entries = 0; return lpqe; } /* move bottom heap element to top */ /* this maintains heap balance */ leaf_pq[1] = leaf_pq[num_leaf_pq_entries]; leaf_pq[num_leaf_pq_entries--] = NULL; /* trickle top (costly) item down to restore heap order */ i = 1; while( i < num_leaf_pq_entries ) { int smallest = i; int left = i<<1; int right = left+1; if( left <= num_leaf_pq_entries && leaf_pq[left]->distance < leaf_pq[i]->distance ) { smallest = left; } if( right <= num_leaf_pq_entries && leaf_pq[right]->distance < leaf_pq[smallest]->distance ) { smallest = right; } if( smallest != i ) { struct leaf_pq_elem *temp = leaf_pq[smallest]; leaf_pq[smallest] = leaf_pq[i]; leaf_pq[i] = temp; i = smallest; } else { break; } } return lpqe; } void leaf_pq_insert( struct leaf_pq_elem *lpqe ) { int i; /* put new elem at bottom of heap */ i = ++num_leaf_pq_entries; if( i >= sizeof(leaf_pq)/sizeof(leaf_pq[0]) ) { fprintf( stderr, "error, make bigger priority queue and recompile\n" ); assert( 0 ); } if( num_leaf_pq_entries > biggest_pq ) biggest_pq = num_leaf_pq_entries; leaf_pq[i] = lpqe; /* resort heap, moving cheaper stuff up to top */ while( i > 1 ) { int parent = i>>1; if( leaf_pq[i]->distance < leaf_pq[parent]->distance ) { struct leaf_pq_elem *temp = leaf_pq[parent]; leaf_pq[parent] = leaf_pq[i]; leaf_pq[i] = temp; i = parent; } else { break; } } } struct elem *my_alloc_elem() { struct elem* elemp; if( elem_free_list ) { num_reused++; elemp = elem_free_list; elem_free_list = elem_free_list->prev_dir; elemp->prev_dir = NULL; elemp->dirs[0] = NULL; elemp->dirs[1] = NULL; elemp->dirs[2] = NULL; elemp->dirs[3] = NULL; return elemp; } else { int CHUNK = 128; /* great than 1! */ int i; num_alloced += CHUNK; elemp = (struct elem*)malloc( sizeof(struct elem) * CHUNK ); elem_free_list = elemp; for( i=0; i<(CHUNK-2); i++ ) { elemp->prev_dir = (elemp + 1); elemp++; } elemp->prev_dir = NULL; num_reused++; return ++elemp; } } void my_free_elem( struct elem* elemp ) { elemp->prev_dir = elem_free_list; elem_free_list = elemp; num_reused--; if( num_reused < 0 ) { fprintf( stderr, "error, memory freed twice!\n" ); assert(0); } } struct leaf_pq_elem *my_alloc_lpqe() { struct leaf_pq_elem* lpqe; if( lpqe_free_list ) { lpqe = lpqe_free_list; lpqe_free_list = (struct leaf_pq_elem*)(lpqe_free_list->root); return lpqe; } else { int CHUNK = 128; /* great than 1! */ int i; lpqe = (struct leaf_pq_elem*)malloc( sizeof(struct leaf_pq_elem) * CHUNK ); lpqe_free_list = lpqe; for( i=0; i<(CHUNK-2); i++ ) { lpqe->root = (struct elem*)(lpqe + 1); lpqe++; } lpqe->root = NULL; return ++lpqe; } } void my_free_lpqe( struct leaf_pq_elem *lpqe ) { lpqe->root = (struct elem*)lpqe_free_list; lpqe_free_list = lpqe; } void kill_tree( struct elem* root ) { int i; if( root == NULL ) return; if( root->prev_dir != NULL && (root->class == IPIN || root->class == OPIN) ) { /*fprintf( stderr, "L" );*/ my_free_elem( root ); return; } for( i=0; i<4; i++ ) { if( root->dirs[i] != NULL && root->dirs[i] != root->prev_dir ) kill_tree( root->dirs[i] ); } /*fprintf( stderr, "T" );*/ my_free_elem( root ); return; } void kill_forest() { struct tree *forp = forest; struct tree *old_fp; /*fprintf( stderr, "killing forest\n" );*/ while( forp ) { old_fp = forp; forp = forp->next; /*fprintf( stderr, "." );*/ kill_tree( old_fp->root ); free( old_fp ); } forest = NULL; /*fprintf( stderr, "\n" );*/ } init_fpga() { int i,j; /*memset( fpga, 0, sizeof(fpga) );*/ memset( fpga, 0, UPPER*(maxx+1)*sizeof(fpga[0][0]) ); /* for( i=0; i 0 ) { fprintf( stderr, "while processing net %d \"%s\", ", net_number, net_name ); fprintf( stderr, "%d elements leaked after killing forest\n", num_reused ); } init_fpga(); biggest_pq = 0; num_reused = 0; } int skipped_elem( int prev_x, int prev_y, int next_x, int next_y ) { int diffx = abs( prev_x - next_x ); int diffy = abs( prev_y - next_y ); if( diffx > 1 || diffy > 1 || diffx+diffy > 1 ) { return 1; } else { return 0; } } int intermed_coord( int prev_x, int new_x ) { if( new_x == prev_x ) return new_x; else { if( new_x&1 ) { return new_x; } else if( prev_x&1 ) { return prev_x; } else { return (prev_x + new_x) >> 1; } } } int compute_prev_dir( int prev_x, int prev_y, int next_x, int next_y ) { if( prev_x < next_x ) { return EAST; } else if( prev_x > next_x ) { return WEST; } else if( prev_y < next_y ) { return NORTH; } else if( prev_y > next_y ) { return SOUTH; } else { assert( 0 ); } } int opp( int prev_dir ) { switch( prev_dir ) { case NORTH: return SOUTH; case SOUTH: return NORTH; case EAST: return WEST; case WEST: return EAST; default: assert( 0 ); } } #define GET_UP_TO_CHAR(i) { do { c=getc(fp); } while( c!=i ); } int read_elem( int *x, int *y, int *pinnum, int *class ) { int c; /* first time, we should wait for 'OPIN' only FIXME */ do { *class = UNDEFINED; if( fscanf( fp, "%s", str ) != 1 ) { fprintf( stderr, "error reading input, expecting class\n" ); exit( -1 ); } if( !strcmp(str,"OPIN") ) { *class = OPIN; } else if( !strcmp(str,"IPIN") ) { *class = IPIN; } else if( !strcmp(str,"CHANX") ) { *class = CHANX; } else if( !strcmp(str,"CHANY") ) { *class = CHANY; } else if( !strcmp(str,"Net") || !strcmp(str,"Num_heap_allocated:") ) { return 0; } } while( *class == UNDEFINED ); GET_UP_TO_CHAR('('); if( fscanf( fp, "%d", x ) != 1 ) { fprintf( stderr, "error reading input, expecting X coordinate\n" ); exit( -1 ); } *x = (*x)*2 + ( (*class==CHANY)?1:0 ); if( (*x) > maxx ) { maxx=*x; if( maxx >= UPPER ) { fprintf( stderr, "error, UPPER too small, increase to at least %d and recompile\n", ++maxx ); exit(-1); } } GET_UP_TO_CHAR(','); if( fscanf( fp, "%d", y ) != 1 ) { fprintf( stderr, "error reading input, expecting Y coordinate\n" ); exit( -1 ); } *y = (*y)*2 + ( (*class==CHANX)?1:0 ); if( (*y) > maxy ) { maxy=*y; if( maxy >= UPPER ) { fprintf( stderr, "error, UPPER too small, increase and recompile\n" ); fprintf( stderr, "error, UPPER too small, increase to at least %d and recompile\n", ++maxy ); exit(-1); } } GET_UP_TO_CHAR(')'); if( *class==OPIN || *class==IPIN ) { /* read pin number information */ if( fscanf( fp, "%s", str ) != 1 ) { fprintf( stderr, "error reading input, expecting 'Pin'\n" ); exit( -1 ); } assert( !strcmp( str, "Pin" ) ); if( fscanf( fp, "%s", str ) != 1 ) { fprintf( stderr, "error reading input, expecting 'number:'\n" ); exit( -1 ); } assert( !strcmp( str, "number:" ) ); if( fscanf( fp, "%d", pinnum ) != 1 ) { fprintf( stderr, "error reading input, expecting pin number\n" ); exit( -1 ); } if( *class == OPIN ) { /* remap output pin numbers for SEGA */ if( *pinnum == 4 && (*x) != 0 && (*y) != 0 ) *pinnum = 6; } else { if( *class == IPIN && *pinnum == 5 ) { fprintf( stderr, "error: clock signal encountered, forgot to specify -global " "in blifmap\n", pinnum ); } assert( *pinnum < 4 ); } } else { *pinnum = -1; } return 1; } void read_net() { struct elem *prev_elem; struct elem *new_elem; struct elem *root; int i,c; int class; int pinnum; int x,y; int prev_dir; root = NULL; do { /* search for "Net" */ while( strcmp(str,"Net") ) { /* FIXME */ /* what if net name is 'Net' and it receives a global clock? can have an error! */ if( fscanf( fp, "%s", str ) != 1 ) { fprintf( stderr, "error reading input, expecting 'Net'\n" ); exit( -1 ); } } /* get net number */ if( fscanf( fp, "%d", &net_number ) != 1 ) { fprintf( stderr, "error reading input, expecting net number\n" ); exit( -1 ); } /* get the net name */ GET_UP_TO_CHAR('('); i=0; c = getc( fp ); while( c != ')' ) { net_name[i++] = c; c = getc( fp ); if( i > MAX_STR_LEN ) { fprintf( stderr, "error reading input, net name too big; increase MAX_STR_LEN and recompile\n" ); exit( -1 ); } } net_name[i] = '\0'; c = getc( fp ); /* check if ':' follows. if so, it's a global net so we */ /* can ignore it. this is not very robust. FIXME */ if( c == ':' ) { str[0] = '\0'; do { /* get everything up to the 'Block' statement */ while( strcmp(str,"Block") ) { if( !strcmp(str,"Net") ) break; if( fscanf( fp, "%s", str ) != 1 ) { fprintf( stderr, "error reading input, expecting 'Block'\n" ); exit( -1 ); } } if( !strcmp(str,"Net") ) break; /* get block name */ if( fscanf( fp, "%s", str ) != 1 ) { fprintf( stderr, "error reading input, expecting block name\n" ); exit( -1 ); } /* get next word on block line */ if( fscanf( fp, "%s", str ) != 1 ) { fprintf( stderr, "error reading input, expecting block words\n" ); exit( -1 ); } } while( strcmp(str,"Net") ); } } while( c == ':' ); /* make sure first elem is an OPIN */ (void)read_elem( &x, &y, &pinnum, &class ); root = my_alloc_elem(); assert( class == OPIN ); root->x = x; root->y = y; root->pinnum = pinnum; root->class = class; root->dirs[0] = NULL; root->dirs[1] = NULL; root->dirs[2] = NULL; root->dirs[3] = NULL; root->distance = 0; root->prev_dir = NULL; prev_elem = root; fpga[x][y] = root; /*fpga_sink[x][y] = 1;*/ /* start building the forest */ forest = (struct tree*)malloc( sizeof(struct tree) ); forest->root = root; forest->next = NULL; do { if( !read_elem( &x, &y, &pinnum, &class ) ) break; if( fpga[x][y] != NULL ) { /* starting a new branch of the net */ /* make sure last branch was a leaf IPIN */ if( prev_elem && prev_elem->class != IPIN ) { if( fpga[x][y]->class != OPIN ) { fprintf( stderr, "error near (%d,%d)\n", x>>1, y>>1 ); assert( 0 ); } else { assert( class == IPIN ); print_net_recurse( prev_elem ); fprintf( fpout, "%d %d 0 %d\n\n\n", x, y, pinnum ); prev_elem = NULL; continue; } } if( !prev_elem || prev_elem->class == IPIN ) { /* this element is redundant, don't add it */ prev_elem = fpga[x][y]; if( prev_elem ) { assert( class == prev_elem->class ); assert( prev_elem->class != IPIN ); } continue; } /* if last branch was not an IPIN, this logic */ /* block probably has feedback to itself */ /* this is not yet supported by these data structures */ } if( skipped_elem( prev_elem->x, prev_elem->y, x, y ) ) { /* add new elem if necessary for S block */ struct elem *add_elem; int add_x, add_y; add_x = intermed_coord( prev_elem->x, x ); add_y = intermed_coord( prev_elem->y, y ); assert( add_x & 1 ); /* S block x coord always odd */ assert( add_y & 1 ); /* S block y coord always odd */ add_elem = fpga[add_x][add_y]; if( add_elem != NULL ) { /* S block existed before, just link up to it */ prev_elem = add_elem; } else { /* S block doesn't yet exist */ add_elem = my_alloc_elem(); add_elem->x = intermed_coord( prev_elem->x, x ); add_elem->y = intermed_coord( prev_elem->y, y ); add_elem->pinnum = -1; add_elem->class = SBLOCK; add_elem->dirs[0] = NULL; add_elem->dirs[1] = NULL; add_elem->dirs[2] = NULL; add_elem->dirs[3] = NULL; add_elem->distance = prev_elem->distance + 1; add_elem->prev_dir = prev_elem; fpga[add_elem->x][add_elem->y] = add_elem; prev_dir = compute_prev_dir( prev_elem->x, prev_elem->y, add_elem->x, add_elem->y ); assert( prev_elem->dirs[prev_dir] == NULL ); prev_elem->dirs[prev_dir] = add_elem; add_elem->dirs[opp(prev_dir)] = prev_elem; prev_elem = add_elem; } } new_elem = my_alloc_elem(); new_elem->x = x; new_elem->y = y; new_elem->pinnum = pinnum; new_elem->class = class; new_elem->dirs[0] = NULL; new_elem->dirs[1] = NULL; new_elem->dirs[2] = NULL; new_elem->dirs[3] = NULL; new_elem->distance = prev_elem->distance + 1; new_elem->prev_dir = prev_elem; assert( fpga[x][y] == NULL ); fpga[x][y] = new_elem; prev_dir = compute_prev_dir( prev_elem->x, prev_elem->y, x, y ); assert( prev_elem->dirs[prev_dir] == NULL ); prev_elem->dirs[prev_dir] = new_elem; new_elem->dirs[opp(prev_dir)] = prev_elem; if( class == IPIN ) { /* add leaf to leaf_pq */ struct leaf_pq_elem *lpqe; lpqe = my_alloc_lpqe(); lpqe->root = root; lpqe->leaf = new_elem; if( SAVE_MEM ) { lpqe->stored_net = 0; } else { lpqe->stored_net = 1; } lpqe->distance = new_elem->distance; leaf_pq_insert( lpqe ); fpga_sink[x][y] = 1; num_sinks++; } prev_elem = new_elem; } while( 1 ); } #undef GET_UP_TO_CHAR int print_unstored_net( struct elem *curr, struct elem *prev, struct elem *search_leaf ) { int i; /* curr and prev always point to our place in the original rooted tree */ /* search_leaf points to a leaf in orig. rooted tree we are looking for */ #if 0 if( prev != NULL && curr->class == OPIN ) { /* don't allow following through a src node */ /* don't add this as a valid leaf node because the src node * was already found */ return 0; } #endif if( prev != NULL && ( (curr->class == IPIN && !fpga_sink[curr->x][curr->y] ) || curr->class == OPIN ) ) { /* reached a new leaf, is it the one we're searching for? */ if( curr == search_leaf ) { fprintf( fpout, "%s %d %d %d 1 %d\n", net_name, net_number, curr->x, curr->y, curr->pinnum ); return 1; } else { return 0; } } /* follow all fanouts from curr, but don't backtrack */ for( i=0; i<4; i++ ) { if( curr->dirs[i] && curr->dirs[i] != prev ) { if( print_unstored_net( curr->dirs[i], curr, search_leaf ) ) { if( curr->class==IPIN || curr->class==OPIN ) fprintf( fpout, "%d %d 0 %d\n\n\n", curr->x, curr->y, curr->pinnum ); else fprintf( fpout, "%d %d 1\n", curr->x, curr->y ); return 1; } } } return 0; } void print_net_recurse( struct elem *leaf ) { if( leaf->prev_dir == NULL ) { /* root node */ fprintf( fpout, "%s %d %d %d 1 %d\n", net_name, net_number, leaf->x, leaf->y, leaf->pinnum ); } else { print_net_recurse( leaf->prev_dir ); fprintf( fpout, "%d %d 1\n", leaf->x, leaf->y ); } } void print_net( struct leaf_pq_elem *minleaf ) { if( minleaf->stored_net == 1 ) { print_net_recurse( minleaf->leaf->prev_dir ); fprintf( fpout, "%d %d 0 %d\n\n\n", minleaf->leaf->x, minleaf->leaf->y, minleaf->leaf->pinnum ); } else { /* curr prev search_leaf */ assert( print_unstored_net( minleaf->leaf, NULL, minleaf->root ) ); } fflush( fpout ); } void copy_elem( struct elem *dest, struct elem *src ) { #ifdef SAFE memcpy( dest, src, sizeof(struct elem) ); dest->distance = 0; dest->prev_dir = NULL; dest->dirs[0] = NULL; dest->dirs[1] = NULL; dest->dirs[2] = NULL; dest->dirs[3] = NULL; #else int *i, *j; i = (int*)dest; j = (int*)src; *i++ = *j++; /* copy x,y */ *i = *j; /* copy pinnum, class */ #endif } void follow_tree( struct elem *this_elem, struct elem *curr, struct elem *prev, struct elem *root ) { int i; /* curr and prev always point to original rooted tree */ /* root points to root of new rooted tree; it is a copy of a leaf in the original tree */ /* this_elem is the current element in the new tree */ if( found_num_sinks == 0 ) return; /* don't do any more work if we're all done! */ if( prev != NULL && curr->class == OPIN ) { /* don't allow following through a src node */ /* don't add this as a valid leaf node because the src node * was already found */ return; } if( prev != NULL && (curr->class == IPIN /*|| curr->class == OPIN*/ ) && fpga_sink[curr->x][curr->y] ) { /* reached a new leaf */ struct leaf_pq_elem *lpqe; lpqe = my_alloc_lpqe(); lpqe->root = root; lpqe->leaf = this_elem; lpqe->stored_net = 1; lpqe->distance = this_elem->distance; leaf_pq_insert( lpqe ); found_num_sinks--; return; } /* follow all fanouts from curr, but don't backtrack */ for( i=0; i<4; i++ ) { if( found_num_sinks == 0 ) break; if( curr->dirs[i] && curr->dirs[i] != prev ) { struct elem *next_elem; next_elem = my_alloc_elem(); copy_elem( next_elem, curr->dirs[i] ); next_elem->prev_dir = this_elem; this_elem->dirs[i] = next_elem; next_elem->dirs[opp(i)] = this_elem; next_elem->distance = this_elem->distance + 1; follow_tree( next_elem, curr->dirs[i], curr, root ); } else if( curr->dirs[i] == NULL ) { this_elem->dirs[i] = NULL; } } } void save_tree( struct elem *curr, struct elem *prev, struct elem *root, int distance ) { int i; /* curr and prev always point to our place in the original rooted tree */ /* root points to the root of the orig. rooted tree */ /* distance is our distance from the leaf we started searching at */ if( found_num_sinks == 0 ) return; /* don't do any more work if we're all done! */ if( prev != NULL && curr->class == OPIN ) { /* don't allow following through a src node */ /* don't add this as a valid leaf node because the src node * was already found */ return; } if( prev != NULL && (curr->class == IPIN /*|| curr->class == OPIN*/ ) && fpga_sink[curr->x][curr->y] ) { /* reached a new leaf, add it to the heap */ struct leaf_pq_elem *lpqe; lpqe = my_alloc_lpqe(); lpqe->root = root; lpqe->leaf = curr; lpqe->stored_net = 0; lpqe->distance = distance; leaf_pq_insert( lpqe ); found_num_sinks--; return; } /* follow all fanouts from curr, but don't backtrack */ for( i=0; i<4; i++ ) { if( found_num_sinks == 0 ) break; if( curr->dirs[i] && curr->dirs[i] != prev ) { save_tree( curr->dirs[i], curr, root, distance+1 ); } } } /* create a new rooted tree, starting at 'minleaf', and add it to the forest */ void build_new_tree( struct leaf_pq_elem *minleaf ) { struct elem * root; struct tree * treep; if( !SAVE_MEM ) { root = my_alloc_elem(); copy_elem( root, minleaf->leaf ); root->distance = 0; root->prev_dir = NULL; treep = (struct tree*)malloc( sizeof(struct tree) ); treep->root = root; treep->next = forest; forest = treep; found_num_sinks = num_sinks; /* new curr prev root */ follow_tree( root, minleaf->leaf, NULL, root ); /* fprintf( fpout, "remaining sinks: %d\n", found_num_sinks ); */ } else { found_num_sinks = num_sinks; save_tree( minleaf->leaf, NULL, minleaf->leaf, 0/*distance*/ ); } } void translate_net() { struct leaf_pq_elem *minleaf; do { int x,y; /*leaf_pq_print();*/ minleaf = leaf_pq_pop(); x = minleaf->leaf->x; y = minleaf->leaf->y; if( fpga_sink[x][y] ) { fpga_sink[x][y] = 0; num_sinks--; print_net( minleaf ); /* fprintf( stdout, "cost: %d\n\n", minleaf->distance ); */ if( num_sinks > 0 ) build_new_tree( minleaf ); } } while( minleaf != NULL && num_sinks > 0 ); } void trace_from_source() { int i; struct leaf_pq_elem *minleaf; for( i=num_leaf_pq_entries; i>0; i-- ) { print_net( leaf_pq[i] ); } } int main( int argc, char *argv[] ) { if( argc < 3 ) { fprintf( stderr, "Error: must specify command line parameters\n" ); fprintf( stderr, "%s input_vpr.r output_sega.cct [ nosavemem | nodoglegs ]\n", argv[0] ); exit( -1 ); } if( argc > 3 && !strcmp("nosavemem",argv[3]) ) { printf( "\n\nNOT ECONOMIZING MEMORY\n\n" ); SAVE_MEM = 0; } if( argc > 3 && !strcmp("nodoglegs",argv[3]) ) { printf( "\n\nELIMINATING INPUT DOGLEGS\n\n" ); NO_DOGLEGS = 1; } fp = fopen( argv[1], "r" ); str[0] = '\0'; fpout = fopen( argv[2], "w" ); memset( fpga, 0, sizeof(fpga) ); do { init(); /*fprintf( stderr, "reading net\n" );*/ read_net(); /*fprintf( stderr, "net has %d sinks\n", num_sinks );*/ fflush( stderr ); if( NO_DOGLEGS ) { trace_from_source(); } else { translate_net(); } /*fprintf( stderr, "num alloced %d, num reused %d\n", num_alloced, num_reused );*/ /*fprintf( stderr, "net had %d pq entries\n", biggest_pq );*/ /*fprintf( stderr, "done translating net\n" ); */ /*fprintf( stderr, "maxx=%d, maxy=%d\n", maxx, maxy );*/ /*fflush( stderr );*/ } while( !feof(fp) && strcmp(str,"Num_heap_allocated:") ); return 0; }