check_route.c

fpga设计评估软件

#include <stdio.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "route_export.h"
#include "check_route.h"
#include "check_rr_graph.h"


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

static void check_node_and_range (int inode, enum e_route_type route_type);
static void check_source (int inode, int inet);
static void check_sink (int inode, int inet, boolean *pin_done); 
static void check_switch (struct s_trace *tptr, int num_switch); 
static boolean check_adjacent (int from_node, int to_node);
static int pin_and_chan_adjacent (int pin_node, int chan_node);
static int chanx_chany_adjacent (int chanx_node, int chany_node);
static void reset_flags (int inet, boolean *connected_to_route);
static void recompute_occupancy_from_scratch (t_ivec **clb_opins_used_locally);
static void check_locally_used_clb_opins (t_ivec **clb_opins_used_locally,
         enum e_route_type route_type);


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


void check_route (enum e_route_type route_type, int num_switch,
        t_ivec **clb_opins_used_locally) {
 
/* This routine checks that a routing:  (1) Describes a properly         *
 * connected path for each net, (2) this path connects all the           *
 * pins spanned by that net, and (3) that no routing resources are       *
 * oversubscribed (the occupancy of everything is recomputed from        *
 * scratch).                                                             */
 
 int inet, ipin, max_pins, inode, prev_node;
 boolean valid, connects;
 boolean *connected_to_route;    /* [0 .. num_rr_nodes-1] */
 struct s_trace *tptr;
 boolean *pin_done;
 
 printf ("\nChecking to ensure routing is legal ...\n");
 
/* Recompute the occupancy from scratch and check for overuse of routing *
 * resources.  This was already checked in order to determine that this  *
 * is a successful routing, but I want to double check it here.          */
 
 recompute_occupancy_from_scratch (clb_opins_used_locally);
 valid = feasible_routing ();
 if (valid == FALSE) {
    printf("Error in check_route -- routing resources are overused.\n");
    exit(1);
 }

 check_locally_used_clb_opins (clb_opins_used_locally, route_type);
 
 connected_to_route = (boolean *) my_calloc (num_rr_nodes, sizeof (boolean));
 
 max_pins = 0;
 for (inet=0;inet<num_nets;inet++)
    max_pins = max (max_pins, net[inet].num_pins);

 pin_done = (boolean *) my_malloc (max_pins * sizeof(boolean));

/* Now check that all nets are indeed connected. */

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

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

    for (ipin=0;ipin<net[inet].num_pins;ipin++)
       pin_done[ipin] = FALSE;

/* Check the SOURCE of the net. */

    tptr = trace_head[inet];
    if (tptr == NULL) {
       printf ("Error in check_route:  net %d has no routing.\n", inet);
       exit (1);
    }

    inode = tptr->index;
    check_node_and_range (inode, route_type);
    check_switch (tptr, num_switch);
    connected_to_route[inode] = TRUE;   /* Mark as in path. */

    check_source (inode, inet);
    pin_done[0] = TRUE;
 
    prev_node = inode;
    tptr = tptr->next;
 
/* Check the rest of the net */
 
    while (tptr != NULL) {
       inode = tptr->index;
       check_node_and_range (inode, route_type);
       check_switch (tptr, num_switch);
 
       if (rr_node[prev_node].type == SINK) {
          if (connected_to_route[inode] == FALSE) {
             printf ("Error in check_route.  Node %d does not link "
                     "into the existing routing for net %d.\n", inode, inet);
             exit(1);
          }
       } 
 
       else {
          connects = check_adjacent (prev_node, inode);
          if (!connects) {
             printf("Error in check_route while checking net %d.\n",
                inet);
             printf("Non-adjacent segments in traceback.\n");
             exit (1);
          }
 
          if (connected_to_route[inode] && rr_node[inode].type != SINK) {

 /* Note:  Can get multiple connections to the same logically-equivalent     *
  * SINK in some logic blocks.                                               */

             printf ("Error in check_route:  net %d routing is not a tree.\n",
                      inet);
             exit (1);
          }

          connected_to_route[inode] = TRUE;  /* Mark as in path. */
 
          if (rr_node[inode].type == SINK)
             check_sink (inode, inet, pin_done);
 
       }    /* End of prev_node type != SINK */
       prev_node = inode;
       tptr = tptr->next;
    }  /* End while */
 
    if (rr_node[prev_node].type != SINK) {
       printf("Error in check_route.  Net %d does not end\n", inet);
       printf("with a SINK.\n");
       exit(1);
    }
 
    for (ipin=0;ipin<net[inet].num_pins;ipin++) {
       if (pin_done[ipin] == FALSE) {
          printf("Error in check_route.  Net %d does not \n",inet);
          printf("connect to pin %d.\n",ipin);
          exit(1);
       } 
    }
  
    reset_flags (inet, connected_to_route);
 
 }  /* End for each net */
 
 free (pin_done);
 free (connected_to_route);
 printf("Completed routing consistency check successfully.\n\n");
 
}
 
 
static void check_sink (int inode, int inet, boolean *pin_done) {
 
/* Checks that this SINK node is one of the terminals of inet, and marks   *
 * the appropriate pin as being reached.                                   */
 
 int i, j, ipin, ifound, ptc_num, bnum, iclass, blk_pin;
 
 i = rr_node[inode].xlow;
 j = rr_node[inode].ylow;
 ptc_num = rr_node[inode].ptc_num;
 ifound = 0;
 
 if (clb[i][j].type == CLB) {
    bnum = clb[i][j].u.block;
    for (ipin=1;ipin<net[inet].num_pins;ipin++) {  /* All net SINKs */

       if (net[inet].blocks[ipin] == bnum) {
          blk_pin = net[inet].blk_pin[ipin];
          iclass = clb_pin_class[blk_pin];

          if (iclass == ptc_num) {

/* Could connect to same pin class on the same clb more than once.  Only   *
 * update pin_done for a pin that hasn't been reached yet.                 */

             if (pin_done[ipin] == FALSE) {  
                ifound++;
                pin_done[ipin] = TRUE;
                break;
             }
          }
       } 
    }
 }
 else {  /* IO pad */
    bnum = clb[i][j].u.io_blocks[ptc_num];
    for (ipin=0;ipin<net[inet].num_pins;ipin++) {
       if (net[inet].blocks[ipin] == bnum) {   /* Pad:  no pin class */
          ifound++;
          pin_done[ipin] = TRUE;
       } 
    }
 }
 
 if (ifound > 1) {
    printf ("Error in check_sink:  found %d terminals of net %d of class/pad"
            "\n %d at location (%d, %d).\n", ifound, inet, ptc_num, i, j);
    exit (1);
 }
 
 if (ifound < 1) {
    printf ("Error in check_sink:  node %d does not connect to any terminal "
            "\n of net %d.\n", inode, inet);
    exit (1);
 }
}


static void check_source (int inode, int inet) {
 
/* Checks that the node passed in is a valid source for this net.        */
 
 t_rr_type rr_type;
 int i, j, ptc_num, bnum, blk_pin, iclass;
 
 rr_type = rr_node[inode].type;
 if (rr_type != SOURCE) {
    printf ("Error in check_source:  net %d begins with a node of type %d.\n",
            inet, rr_type);
    exit (1);
 }
 
 i = rr_node[inode].xlow;
 j = rr_node[inode].ylow;
 ptc_num = rr_node[inode].ptc_num;
 bnum = net[inet].blocks[0];
 
 if (block[bnum].x != i || block[bnum].y != j) {
    printf ("Error in check_source:  net SOURCE is in wrong location (%d,%d)."
            "\n", i, j);
    exit (1);
 }
 
 if (block[bnum].type == CLB) {
    blk_pin = net[inet].blk_pin[0];
    iclass = clb_pin_class[blk_pin];

    if (ptc_num != iclass) {
       printf ("Error in check_source:  net SOURCE is of wrong class (%d).\n",
              ptc_num);
       exit (1);
    }
 }
 else {    /* IO Pad.  NB:  check_node ensured ptc_num < occ of this pad.  */
    if (clb[i][j].u.io_blocks[ptc_num] != bnum) {
       printf ("Error in check_source:  net SOURCE is at wrong pad (pad #%d)."
               "\n", ptc_num);
       exit (1);
    }
 }
}


static void check_switch (struct s_trace *tptr, int num_switch) {

/* Checks that the switch leading from this traceback element to the next *
 * one is a legal switch type.                                            */

 int inode;
 short switch_type;

 inode = tptr->index;
 switch_type = tptr->iswitch;

 if (rr_node[inode].type != SINK) {
    if (switch_type < 0 || switch_type >= num_switch) {
       printf ("Error in check_switch: rr_node %d left via switch type %d.\n",
               inode, switch_type);
       printf ("Switch type is out of range.\n");
       exit (1);
    }
 }

 else {  /* Is a SINK */ 

/* Without feedthroughs, there should be no switch.  If feedthroughs are    *
 * allowed, change to treat a SINK like any other node (as above).          */

    if (switch_type != OPEN) {
       printf ("Error in check_switch:  rr_node %d is a SINK, but attempts \n"
               "to use a switch of type %d.\n", inode, switch_type);
       exit (1);
    }
 }
}
 
 
static void reset_flags (int inet, boolean *connected_to_route) {
 
/* This routine resets the flags of all the channel segments contained *
 * in the traceback of net inet to 0.  This allows us to check the     * 
 * next net for connectivity (and the default state of the flags       * 
 * should always be zero after they have been used).                   */
 
 struct s_trace *tptr;
 int inode;
 
 tptr = trace_head[inet];
 
 while (tptr != NULL) {
    inode = tptr->index;
    connected_to_route[inode] = FALSE;   /* Not in routed path now. */
    tptr = tptr->next;
 }
}
 
 
static boolean check_adjacent (int from_node, int to_node) {
 
/* This routine checks if the rr_node to_node is reachable from from_node.   *
 * It returns TRUE if is reachable and FALSE if it is not.  Check_node has   *
 * already been used to verify that both nodes are valid rr_nodes, so only   *
 * adjacency is checked here.                                                */
 
 int from_xlow, from_ylow, to_xlow, to_ylow, from_ptc, to_ptc, iclass;
 int num_adj, to_xhigh, to_yhigh, from_xhigh, from_yhigh, iconn;
 boolean reached;
 t_rr_type from_type, to_type;
 
 reached = FALSE;