/*
* $Header: c:\\cygwin\\cvsroot/Vert03/vertlib/routing.c,v 1.1.1.1 2003/11/04 23:34:57 mjames
* Exp $
*
* $Log: routing.c,v $
* Revision 1.1.1.1 2003/11/04 23:34:57 mjames
* Imported into local repositrory
*
* Revision 1.19 2003/01/02 21:37:17 mjames
* Experiment on creating NOT_ROUTABLE_H and NOT_ROUTABLE_L
* properties on the nets so that pin jumpers can be made without a problem.
*
* Still need to sort out pin assignments made to these not_routable nets
* which will become legal in some cases so that pullups and pulldown
* pins can be used on the FPGA.
*
* Revision 1.18 2002/12/09 10:31:49 mjames
* Corrected 2 warnings about #ident
* Added warning about "chip X1" which gets confused with component called "X1"
*
* Revision 1.17 2002/09/27 22:29:31 MJAMES
* Added lhs_expr for cases like
*
* x(0) <= y
*
* where x is std_logic_vector(0 downto 0) and y is std_logic.
*
* Revision 1.16 2002/08/23 09:50:21 mjames
* Altered pin_group search pattern from
* chip_exp.pin_exp to chip_exp(pin_exp) as this is clearer.
*
* Revision 1.15 2001/10/31 22:20:16 mjames
* Tidying up problematical comments caused by CVS
* 'intelligent' comment guessing
*
* Revision 1.14 2001/10/31 16:18:04 mjames
* Added a datastructure to hide regular expression information from programs.
* Changed call to regexec to indicate 0 subexpressions to be matched
* rather than a number dependent on strlen(string) which was wrong.
*
* Revision 1.13 2001/10/10 20:18:21 mjames
* Added a vert_regcomp function to compile regular expressions
* with '^' (match start string) and '$' (match end string) bracketing
* this => wildcard must match entire string not just a part of it.
*
* Revision 1.12 2001/10/07 20:50:51 mjames
* Added wildcard checking (warn user about
* using wildcard '*' on the end of a string in stead of wildcard '.*')
*
* Revision 1.11 2001/09/28 10:16:20 mjames
* Modified to use auto variable pointing at regular expression instead of
* allocating one via calloc.
*
* Revision 1.10 2001/09/25 23:15:23 mjames
* Converted wildcards to use proper regexp pattern match library
*
* Revision 1.9 2001/08/23 20:06:44 mjames
* Added 'reserve' command for use with preroute commands.
* This command provides the 'correct' documented pin reservation
* behaviour.
*
* Revision 1.8 2001/08/09 20:04:03 mjames
* Tidying up indentation
*
* Revision 1.7 2001/07/20 14:49:42 mjames
* Corrected reading names in on multiple boards : if present in a database file
* when reading in a suffixed design
* e.g. CHIP fred
* Will also get its name suffixed.
*
* Revision 1.6 2001/07/20 10:47:43 mjames
* Allowed setting of pin routing group properties on pins on nets
* by the
* "set pin" command
*
* Revision 1.5 2001/07/09 15:39:38 mjames
* Reduced verbose diagnostics
*
* Revision 1.4 2001/06/07 14:00:04 MJAMES
* Producing an error on failing to fix pins
*
* Revision 1.3 2001/06/06 12:10:17 mjames
* Move from HPUX
*
* Revision 1.2 2001/01/02 07:53:53 mjames
* Made changes to allow for interface with TCL/Tk
*
* Revision 1.1.1.1 2000/10/19 21:58:39 mjames
* Mike put it here
*
* Revision 1.57 2000/10/04 10:37:09 10:37:09 mjames (Mike James)
* Modified for Vertical2 : support COMPONENTS and SIGNALS
*
* Revision 1.57 2000/10/04 10:37:09 10:37:09 mjames (Mike James)
* Part of Release PSAVAT01
*
* Revision 1.56 2000/10/02 11:04:20 11:04:20 mjames (Mike James)
* new_vhdl
*
* Revision 1.55 2000/09/27 14:42:20 14:42:20 mjames (Mike James)
* Part of Release Sep_27_ST_2000
*
* Revision 1.54 2000/09/21 10:15:50 10:15:50 mjames (Mike James)
* Part of Release Sep21Alpha
*
* Revision 1.53 2000/08/25 09:57:16 09:57:16 mjames (Mike James)
* Part of Release Aug25_alpha
*
* Revision 1.52 2000/08/16 08:57:32 08:57:32 mjames (Mike James)
* Part of Release CD01_Aug2000
*
* Revision 1.51 2000/08/16 08:55:43 08:55:43 mjames (Mike James)
* corrected routing/unroutable nets errors
*
* Revision 1.50 2000/08/14 14:45:13 14:45:13 mjames (Mike James)
* Part of Release Aug_14_2000
*
* Revision 1.49 2000/08/14 14:43:31 14:43:31 mjames (Mike James)
* Added power pins
*
* Revision 1.48 2000/08/11 08:30:33 08:30:33 mjames (Mike James)
* Part of Release Aug_11_2000
*
* Revision 1.47 2000/08/09 10:31:49 10:31:49 mjames (Mike James)
* Part of Release Aug_9_2000
*
* Revision 1.46 2000/05/31 11:43:00 11:43:00 mjames (Mike James)
* Part of Release May_31_2000
*
* Revision 1.45 2000/05/08 17:01:39 17:01:39 mjames (Mike James)
* Part of Release May_8_2000
*
* Revision 1.44 2000/05/08 16:59:32 16:59:32 mjames (Mike James)
* Part of Release May_8_2000
*
* Revision 1.43 2000/05/08 16:57:09 16:57:09 mjames (Mike James)
* Part of Release May_8_2000
*
* Revision 1.42 2000/03/08 16:19:29 16:19:29 mjames (Mike James)
* New version including PC
*
* Revision 1.39 2000/01/20 15:58:50 15:58:50 mjames (Mike James)
* Part of Release R22
*
* Revision 1.38 99/12/22 11:15:30 11:15:30 mjames (Mike James)
* Part of Release Dec_22_1999
*
* Revision 1.37 99/06/25 14:35:50 14:35:50 mjames (Mike James)
* Added in reference to expression.h, but no changes made
* to the function of acfread yet.
*
* Revision 1.36 99/06/18 09:26:23 09:26:23 mjames (Mike James)
*
* Revision 1.35 99/05/04 09:52:46 09:52:46 mjames (Mike James)
* General checkin
*
* Revision 1.33 98/11/27 15:16:05 15:16:05 mjames (Mike James)
* FIxed small errors
*
* Revision 1.32 98/06/15 14:19:24 14:19:24 mjames (Mike James)
* Removed and added Route Create from general routing algorithm.
* Added routing routing groups
*
* Revision 1.31 98/04/24 14:09:05 14:09:05 mjames (Mike James)
* Removed 'create routes' from default routing algorithm set
* used when route command is used.
*
* Revision 1.30 98/03/16 11:39:50 11:39:50 mjames (Mike James)
* Removed an old bug - suffixing of PCB names has been broken for about
* a year. If a pcb were read in non-suffixed and then another with a suffix,
* the suffix would be applied over all of the sockets and nets, not just the new ones.
*
* Revision 1.29 98/02/11 11:27:14 11:27:14 mjames (Mike James)
* Checked in for version 6.2a
*
* Revision 1.28 97/04/23 08:43:23 08:43414:23 mjames (Mike James)
* CHecked in for release rel23041997
*
* Revision 1.27 97/01/03 13:35:24 13:35:24 mjames (Mike James)
* Tidied up the ensure_reserved() function. Added in a flag to
* indicate that a net has been processed by ensure_reserved()
* And so is not in error for only having 0 or 1 nodes names (which is the
* case for a 1 or 2 node net that has been processed. One of the nodes will
* remain unnnamed and this will result in 0 or 1 nodes apparently in use
*
* Revision 1.26 96/12/23 15:14:38 15:14:38 mjames (Mike James)
* This code for fixing pins has been split from the 'exact path'
* routing as the algorithm has become more reliable
* if there are two independednt routines.
*
* Revision 1.25 96/12/13 08:43:11 08:43:11 mjames (Mike James)
* Update to v5.1, added Write ID , exact routing
*
* Revision 1.24 96/08/06 13:38:54 13:38:54 mjames (Mike James)
* Added FIX_LOCATION pin attribute to netlist
*
* Revision 1.23 96/07/19 14:38:44 14:38:44 mjames (Mike James)
* Update to give to PRL
*
* Revision 1.22 1996/07/12 15:52:12 mjames
* Sorted out things like Alias and Jumpers
* Work Correctly
* Print COrrectly
*
* Revision 1.21 96/07/09 15:54:04 15:54:04 mjames (Mike James)
* Altered aliasing to make it hierarchical, also for jumpering
*
* Revision 1.20 96/06/17 13:01:45 13:01:45 mjames (Mike James)
* Altered the printing of JUMPERED and ALIASED nets
* ,
*
* Revision 1.19 96/06/11 14:46:00 14:46:00 mjames (Mike James)
* Tidying up done to remove an error created by
* trying to fix the wrong symprom of a bug
*
* Revision 1.18 96/06/11 14:11:47 14:11:47 mjames (Mike James)
* Added hierarchical jumpering
*
* Revision 1.17 96/06/04 11:53:22 11:53:22 mjames (Mike James)
* Added the ability to jumper nets by reference to a node on the nets
*
* Revision 1.16 96/05/29 10:53:34 10:53:34 mjames (Mike James)
* Added renaming of IDs for nets and sockets.
*
* Revision 1.15 96/04/26 16:02:28 16:02:28 mjames (Mike James)
* Altered inside/outside determination of signal directions
*
* Revision 1.14 96/04/15 14:19:36 14:19:36 mjames (Mike James)
* Checkin before datatype printing
* modifications
*
* Revision 1.13 96/03/29 14:46:32 14:46:32 mjames (Mike James)
* Added VHDL netlist writing to the capabilities of ACFREAD
*
* Revision 1.12 96/03/26 07:21:16 07:21:16 mjames (Mike James)
* Added LIST XREF socket-name command
*
* Revision 1.11 96/03/19 08:53:43 08:53:43 mjames (Mike James)
* Minor tweaks
*
* Revision 1.7 96/03/13 15:37:34 15:37:34 mjames (Mike James)
* Altered the name_pref field to be used to indicate the routing algorithm used
* to route this net.
*
* Revision 1.6 96/02/13 09:13:30 09:13:30 mjames (Mike James)
* Updated to be version 2.0 with net joining
*
* Revision 1.5 96/02/08 15:28:31 15:28:31 mjames (Mike James)
* First release
*
* Revision 1.4 96/02/07 16:01:35 16:01:35 mjames (Mike James)
* Added correct RCS header
*
* Revision 1.3 96/02/07 15:50:45 15:50:45 mjames (Mike James)
* Added RCS ident message
*
* Revision 1.2 96/02/07 11:04:25 11:04:25 mjames (Mike James)
* Checkin before adding new command parsing to program
*
* Revision 1.1 96/01/10 13:14:36 13:14:36 mjames (Mike James)
* Initial revision
* */
#include "routing.h"
#include "chck_names.h"
#include "cmdlog.h"
#include "cmdparse.h"
#include "database.h"
#include "expression.h"
#include "generic.h"
#include "lx_support.h"
#include "sorting.h"
#include "statistics.h"
#include "unrouted.h"
#include "vertcl_main.h"
#include <ctype.h>
#include <regex.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#ident \
"@(#)$Header: c:\\cygwin\\cvsroot/Vert03/vertlib/routing.c,v 1.1.1.1 2003/11/04 23:34:57 mjames Exp $"
/* used in search for pre-existing path */
int MaxNodesForSearch = MAX_NODES_FOR_PATH_SEARCH;
int global_group_flag = 0;
static void get_num_nets (net_t *list, char *message)
{
int i = 0;
while (list)
{
list = list->next;
i++;
}
Log (LOG_GENERAL, "-- %-4d %s\n", i, message);
}
void count_nets (char *message)
{
Log (LOG_GENERAL, "-- Routing Statistics : %s\n", message);
get_num_nets (unrouted_list, "Connections not routed");
get_num_nets (routed_list, "Nets connected but not in use");
get_num_nets (named_list, "Nets connected and used by named signals");
Log (LOG_GENERAL, "-- \n");
}
/* clear the routing flags on the node references on a particular net */
/* this tries to avoid the situation where two unrouted nets both find the
same pin connection on the routed net when it is searched to see if
it is connected to a socket. The old algorithm found the first
connected pin on a socket and then used this */
void clear_routing_flags (noderef_t *net_nodes)
{
while (net_nodes)
{
/* Indicate not already visited all nodes on this net */
net_nodes->r_flag = 0;
net_nodes = net_nodes->next;
}
}
/* does a net reach the wanted socket with the pin direction correct
and if we are using pin_groups is this pin in the correct group */
noderef_t *
search_net_for_socket (noderef_t *wanted_ref, noderef_t *net_nodes, int use_group_mask)
{
int route_flags = 0;
node_t *wanted = wanted_ref->node;
if (use_group_mask)
route_flags = wanted->socket->route_flags;
while (net_nodes)
{
node_t *nnode = net_nodes->node;
/* if we have not already visited this node */
if ((net_nodes->r_flag == 0) && (nnode->socket == wanted->socket) &&
/* either
NOT a fixed pin (pin direction NOT pin location ) or
IS a fixed pin and in the right direction : probably can use compat_pins
info from template.c here MDJ Aug 2000 */
(nnode->fixed_pin == 0 || nnode->pindir == wanted_ref->pindir) &&
/* either
Not using pin groups
or the pin group is the same */
(!route_flags ||
((nnode->pin_group & route_flags) == (wanted->pin_group & route_flags))))
{
net_nodes->r_flag = 1;
return (net_nodes);
}
net_nodes = net_nodes->next;
}
return NULL;
}
/* removes a net from the list of nets */
net_t *remove_net (net_t **list, net_t *net)
{
noderef_t *refs, *temp;
net_t *next_net, *prev_net;
/*
printf("-- removing %s (%s) (%p) list %p\n",
net->identifier,net->name,*list,net);
*/
next_net = net->next;
prev_net = net->prev;
/* fill in the gap */
/* removal from head of list is different */
if (net == *list)
{
*list = next_net;
if (next_net)
next_net->prev = NULL;
}
else
{
if (prev_net)
prev_net->next = net->next;
if (next_net)
next_net->prev = net->prev;
};
/* get pointer to the nodes on this net */
refs = net->nodes;
/* do not destroy the net linking structure
as it could still be pointed at by unused unrouted
nodes that are still attached to sockets which you will
find if you examine all of the nodes attached to a socket. */
net->list_ref = NULL; /* this net is not held on any list now */
net->nodecount = 0;
net->nodes = NULL;
/*net->subnets = NULL; do not destroy subnets , used for alias listing */
/*change name to something worrying */
net->name = "[DELETED so this is INVISIBLE]";
/* remove the nodes on this net */
while (refs)
{
refs->node->refcount--; /* one less reference */
temp = refs->next;
refs = temp;
};
return next_net;
}
/* moves a net from one list to another */
void transfer_net_to_named (net_t **from_list, net_t *net)
{
/* remove the node from the 'from' list */
/*
printf("-- transferring %s (%s) (%p) list
%p\n",net->identifier,net->name,*from_list,net);
*/
if (net->next)
net->next->prev = net->prev;
if (net->prev)
net->prev->next = net->next;
if (net == *from_list)
*from_list = net->next;
net->list_ref = &named_list; /* net now is on the named list */
/* stick net on tail of 'to' list */
if (named_tail)
named_tail->next = net;
net->prev = named_tail;
if (!named_list)
named_list = net;
net->next = NULL;
named_tail = net;
}
/* ******************************************** */
/*
This function tidies up, setting net names for all of the pins on the
net that have not been used by the unrouted net, to a net whose name
is RSV00001Z where the 00001 is a sequence number .
it also names the routed net
Recently modified such that external connections do not get this treatment
These pins take on the names of the nets connected regardless, as they are
not EPLDs, so there won't be a complaint by Maxplus2.
*/
/* the dummy node count is external to the naming routine, as it
is used in the ensure_reservation code */
static int nodecount = 0;
void name_unused_nodes (net_t *routed_net, char *identifier)
{
noderef_t *routed_nodes;
char *unused_ident;
routed_nodes = routed_net->nodes;
while (routed_nodes)
{
node_t *cnode = routed_nodes->node;
if (routed_nodes->node->net_assigned == 0)
{ /* this node hasnt yet been used by a net */
if (cnode->socket->is_external == 0)
{ /* EPLD or internal node */
/* every reserved pin is unique, so make it a new name c */
unused_ident
= calloc (RES_NAMLEN
+ 1, sizeof (char)); sprintf (unused_ident
, RES_FMT
, nodecount
++); cnode->name = unused_ident; /* use the created name */
cnode->net =
routed_net; /* tell the node its got a net assigned */
cnode->pindir = INPUT;
/* cnode->datatype = "Named through naming unused
* nodes";*/
/* cnode->datatype = routed_net->datatype; */
cnode->vhdltype =
default_vhdl_datatype; /* put something there */
cnode->lhs_expr = NULL;
cnode->orig_vhdltype = NULL; /* put something there */
}
else
{ /* An external flag See SET EXTERNAL <prefix> */
cnode->name = identifier; /* same name as the net */
cnode->net =
routed_net; /* tell the node its got a net assigned */
cnode->pindir = INPUT;
/* cnode->datatype = routed_net->datatype; */ /* routed_net->datatype;
*/
cnode->vhdltype =
routed_net->vhdltype; /* put something there */
cnode->lhs_expr = NULL;
cnode->orig_vhdltype = NULL; /* put something there */
}
cnode->net_assigned = 1; /* tell the node its got a net assigned */
cnode->in_use = 0; /* if the node is in use then set its flag */
}
routed_nodes = routed_nodes->next;
}
}
/* ******************************************** */
/* connect up the routed and unrouted nets */
void combine_sub (net_t *routed_net, net_t *unrouted_net)
{
noderef_t *routed_nodes, *unrouted_nodes;
/*
printf("-- Moving net %s onto routing of %s\n",
unrouted_net->identifier,routed_net->identifier);
*/
unrouted_nodes = unrouted_net->nodes;
routed_nodes = routed_net->nodes;
if (level & 2)
{
Log (
LOG_GENERAL,
"#COMBINE_SUB routed=%s, unrouted=%s\n",
unrouted_net->name,
routed_net->name);
Log (
LOG_GENERAL,
" type def routed = %d unrouted=%d\n",
unrouted_net->type_defined,
routed_net->type_defined);
}
/* for each node on the routed net, is this net needed on
the unrouted net */
while (unrouted_nodes)
{
noderef_t *route_ref;
node_t *routed_node, *unrouted_node;
unrouted_node = unrouted_nodes->node;
/* we have a route, this search _will succeed .. if it doesnt .. oops. */
/* do not need to worry about the groups here as the nets have already
been found */
/* Changed MDJ July 2001 : made it a prerequisite to check if the pin_group
* matches */
route_ref = search_net_for_socket (
unrouted_nodes, routed_nodes, unrouted_node->pin_group);
/* if we have found a node on the right socket on the
routed net that has not yet been used */
if (route_ref)
{
routed_node = route_ref->node;
if (level & 2)
Log (
LOG_GENERAL,
"info %s(%s) '%s'\n",
routed_node->socket->name,
routed_node->identifier,
route_ref->orig_name ? route_ref->orig_name
: unrouted_net->name);
/*
route_ref->r_flag = 1;
*//* we are using this node */
routed_node->pindir =
unrouted_nodes->pindir; /* the node reference holds the
pin direction */
/* routed_node->name = unrouted_net->identifier; Previous !!!*/
if (route_ref->orig_name)
{
routed_node->name = route_ref->orig_name;
routed_node->vhdltype = route_ref->vhdltype;
routed_node->orig_vhdltype = route_ref->orig_vhdltype;
routed_node->lhs_expr = route_ref->lhs_expr;
if (level & 2)
Log (
LOG_GENERAL,
"# Info : found rename to %s on %s\n",
route_ref->orig_name,
unrouted_net->identifier);
}
else
{
routed_node->name = unrouted_net->identifier;
routed_node->vhdltype = unrouted_nodes->vhdltype;
routed_node->lhs_expr = unrouted_nodes->lhs_expr;
routed_node->orig_vhdltype = unrouted_nodes->orig_vhdltype;
}
/* routed_node->datatype = unrouted_nodes->datatype; */
routed_node->net =
routed_net; /* tell the node its got a net assigned */
routed_node->in_use = 1; /* if the node is in use then set its flag */
routed_node->net_assigned = 1;
routed_node->routed_net = NULL; /* all nodes on the routed net are
about to belong to the named list */
}
if (level & 2)
Log (LOG_GENERAL, "#\n");
unrouted_nodes = unrouted_nodes->next;
};
}
static void combine_alias (net_t *routed_net, net_t *unrouted_net)
{
/* printf("combining alias %s with routed %s\n",unrouted_net->identifier,
routed_net->identifier); */
while (unrouted_net)
{
if (unrouted_net->how_joined == Aliased)
{ /* recursion for alias */
if (unrouted_net->subnets)
combine_alias (routed_net, unrouted_net->subnets);
}
else
{
/* and for each aliased subnet ... */
clear_routing_flags (unrouted_net->nodes);
/* printf("moving aliased net .%s.\n",unrouted_net->identifier); */
combine_sub (routed_net, unrouted_net);
/* name_unused_nodes (routed_net, unrouted_net->identifier); */
}
unrouted_net = unrouted_net->joined_nets;
}
}
/* ******************************************** */
/* if a net was created by aliasing names, now we have to copy out each of
the unrouted sub nets to the routed net - getting node names right
in particular . Otherwise just do the one */
void combine_routed_and_unrouted (net_t *routed_net, net_t *unrouted_net)
{
clear_routing_flags (routed_net->nodes);
/* refer across to unrouted net for printout */
/*
printf("Combining '%s' and '%s' \n",routed_net->identifier,
unrouted_net->identifier);
*/
routed_net->unrouted_reference = unrouted_net;
routed_net->name = unrouted_net->identifier;
/* assumption here is that the datatype and vhdltype are the same */
/* routed_net->datatype = unrouted_net->datatype; */
routed_net->vhdltype = unrouted_net->vhdltype;
if (unrouted_net->how_joined == Aliased)
{
/* preserve aliasing information */
combine_alias (routed_net, unrouted_net);
}
else
{
clear_routing_flags (unrouted_net->nodes);
combine_sub (routed_net, unrouted_net);
/* name_unused_nodes (routed_net, unrouted_net->identifier); */
}
}
/* **************************************************************** */
/* This function ensures net reservation is made for all internal
nodes that are on internal sockets .
If any external socket is on the net then all internal pins are reserved.
Otherwise a single internal pin is left as a non-reserved driver */
void ensure_reservation (void)
{
char *unused_ident;
net_t *net_head = routed_list;
int skip; /* the number of nodes on the net to leave unreserved */
/*
puts("ensure_reservation entered");
*/
while (net_head)
{
net_t *altered_net = NULL;
if (net_head->nodecount > 1 && IS_ROUTABLE (net_head->how_routed))
{ /* ignore single node nets as they need to be external */
noderef_t *routed_nodes = net_head->nodes;
net_head->nodes_reserved = 0; /* Begin by clearing the flag */
/* nets with external sockets cannot be allowed */
if (net_head->has_external)
skip = 0;
else
skip = 1;
/*
printf("Net '%s'\n",net_head->identifier);
*/
while (routed_nodes)
{
node_t *cnode = routed_nodes->node;
if (cnode->net_assigned == 0 && /* this node hasnt yet been
used by a net */
/* set the flag to stop count_nets_with_few_nodes() in
statistics.c from complaining */
cnode->socket->is_external == 0)
{ /* EPLD or internal node */
net_head->nodes_reserved = 1;
/* every reserved pin is unique, so make it a new name
*/
if (skip == 0)
{ /* skipped enough ? */
unused_ident =
calloc (RES_NAMLEN
+ 1, sizeof (char)); unused_ident,
RES_FMT,
nodecount++); /* shared node counter */
cnode->name =
unused_ident; /* use the created name */
cnode->net = net_head; /* tell the node its got
a net assigned */
cnode->pindir = INPUT;
/* cnode->datatype = "Named
* through naming unused nodes";*/ /* routed_net->datatype; */
cnode->vhdltype =
default_vhdl_datatype; /* put something
there */
cnode->net_assigned = 1;
cnode->lhs_expr = NULL;
altered_net = net_head;
}
else
skip--;
}
routed_nodes = routed_nodes->next;
}
} /* nodecount */
net_head = net_head->next;
if (altered_net)
{
/*
transfer_net_to_named (&routed_list, altered_net);
*/ }
}
}
/* this function checks to see if the net identifier of an unrouted net matches that
of a routed net, which is itself not routable */
void validate_unrouted (void)
{
net_t *routed_net, *unrouted_net;
unrouted_net = unrouted_list;
while (unrouted_net)
{
if (unrouted_net->identifier[0])
{
/* search first for matching Identifier */
routed_net =
find_net (&routed_list, Ident, unrouted_net->identifier, Search);
/* located a net that could be a candidate . Validate routing status
and report an error if there is a problem */
if (routed_net && IS_NOT_ROUTABLE (routed_net->how_routed))
{
noderef_t *nodes = unrouted_net->nodes;
unrouted_net->how_routed = routed_net->how_routed;
Log (
LOG_ERROR,
"-- WARNING : Routing : Net '%s' with following unrouted\n"
"-- nodes cannot be connected to an UNROUTABLE routed "
"net\n",
unrouted_net->identifier);
while (nodes)
{
Log (
LOG_ERROR,
"-- %s(%s)\n",
nodes->node->socket->identifier,
nodes->node->identifier);
nodes = nodes->next;
}
}
else
unrouted_net->how_routed =
Free; /* can keep on routing this net */
}
unrouted_net = unrouted_net->next;
}
}
/* ******************************************** */
/* this procedure searches the unrouted nets one by one.
if an unrouted net has the same name as a
routed net, then all nodes on the unrouted net take on the
routed net name , and the routed net's status is changed to reflect this
name. All 'spare' nodes on the routed net are set to point at a 'reserved' net
for future safety */
void perform_routing_by_name (void)
{
net_t *routed_net;
noderef_t *routed_nodes, *unrouted_nodes;
net_t *unrouted_net, *prev_net;
int routed_ok;
prev_net = NULL;
unrouted_net = unrouted_list;
while (unrouted_net)
{
routed_ok = 0;
if (unrouted_net->identifier[0] && IS_ROUTABLE (unrouted_net->how_routed))
{
/* search first for matching Name then for matching Identifier */
routed_net =
find_net (&routed_list, Name, unrouted_net->identifier, Search);
if (!routed_net)
routed_net = find_net (
&routed_list, Ident, unrouted_net->identifier, Search);
if (routed_net && IS_ROUTABLE (routed_net->how_routed))
{
/* found a routed net, with this name or
* ident */
/* check status of this net, see if it connects the right
* places */
int f = 1;
/*
printf("Found matching routed net \n");
*/
unrouted_nodes = unrouted_net->nodes;
routed_nodes = routed_net->nodes;
clear_routing_flags (routed_nodes);
while (unrouted_nodes && f)
{
f = search_net_for_socket (
unrouted_nodes, routed_nodes, 1) != NULL;
unrouted_nodes = unrouted_nodes->next;
}
/* if f is 1 then the routed net connects all of the nodes on
the unrouted net */
if (f)
{
/*
printf("and can join together sockets \n");
*/
/* Can fit nets together */
combine_routed_and_unrouted (routed_net, unrouted_net);
/* prevent this net from being recycled, move to
the fully named and routed list */
transfer_net_to_named (&routed_list, routed_net);
routed_net->how_routed =
By_Name; /* This net was routed by name !! */
routed_ok = 1;
}
}
}
if (routed_ok)
/* remove the unrouted net from the list */
unrouted_net = remove_net (&unrouted_list, unrouted_net);
else
/* Not removing net as algorithm hasnt found a match */
unrouted_net = unrouted_net->next;
};
count_nets ("After routing by matching existing net names");
}
/************************************************************************/
/* this algorithm works by considering each of the routed nets in turn
to see if there is an unrouted net 'fixed' to it. */
/************************************************************************/
void perform_routing_by_fixed_net (void)
{
net_t *unrouted_net, *routed_next;
net_t *routed_net = routed_list;
int routed_ok, f;
while (routed_net)
{
routed_next = routed_net->next; /* 'next' will be changed when a routed
net is moved onto the named list */
routed_ok = 0;
f = 1;
/*
printf("Considering ROUTED '%s'\n",routed_net->identifier);
*/
if (IS_ROUTABLE (routed_net->how_routed) && routed_net->has_fix_location &&
routed_net->unrouted_fix_net)
{
unrouted_net = routed_net->unrouted_fix_net;
/*
printf(" with UNROUTED '%s'\n",unrouted_net->identifier);
*/
if (unrouted_net->nodecount > 0 &&
IS_NOT_ROUTABLE (unrouted_net->how_routed))
/* skip all 1-node nets, these will be dealt with by
a later routing algorithm */
{
if (routed_net->nodecount >= unrouted_net->nodecount)
{
/* enough nodes, but does it go the right places ?? */
noderef_t *unrouted_nodes = unrouted_net->nodes;
noderef_t *routed_nodes = routed_net->nodes;
clear_routing_flags (routed_nodes);
while (unrouted_nodes && f)
{
f = search_net_for_socket (
unrouted_nodes, routed_nodes, 1) !=
NULL;
unrouted_nodes = unrouted_nodes->next;
}
/* if f is 1 then the routed net connects all of the
nodes on the unrouted net */
if (f)
{
/* Can join Routed & Unrouted nets together */
/*
printf("Managed '%s' for fixed net
routing '%s' \n",routed_net -> identifier,
unrouted_net->identifier);
*/
combine_routed_and_unrouted (
routed_net, unrouted_net);
/* prevent this net from being recycled, move
to the fully named and routed list */
transfer_net_to_named (
&routed_list, routed_net);
routed_net->how_routed =
By_Fixed_Net; /* This net was routed by
finding a wire! */
routed_ok = 1;
/*
Log (LOG_GENERAL, "#
Sucessfully routed net '%s' by fixing
pins\n", routed_net->name);
*/
}
}
};
if (routed_ok)
{
/* printf("Removing '%s' from
* list\n",unrouted_net->identifier);
*/
/* remove the unrouted net from the list */
remove_net (&unrouted_list, unrouted_net);
}
else
Log (
LOG_ERROR,
"-- Error (probably) : net '%s': Fix pin attempt has "
"failed on this net !!\n",
unrouted_net->identifier);
}
routed_net = routed_next;
}
count_nets ("After routing fixed nets");
}
/* ******************************************** */
/* this code deals with trying to find if a Routed net with
exactly the same connections as the Unrouted net exists.
Preference is to be given to any routed nets that have fixed pins */
/* ******************************************** */
void perform_routing_by_exact_path (void)
{
net_t *unrouted_net;
net_t *routed_net;
int routed_ok, f;
enum
{
CheckFixed,
DoAny
} pass;
for (pass = CheckFixed; pass <= DoAny; pass++)
{
unrouted_net = unrouted_list;
while (unrouted_net)
{
routed_ok = 0;
f = 1;
/* if we are looking for EXACT path matching, then ANY node on the
unrouted list
will be connected to the SAME routed net, so just pick the first
node */
if (unrouted_net->nodes)
routed_net = unrouted_net->nodes->node->routed_net;
else
routed_net = NULL;
if (IS_ROUTABLE (unrouted_net->how_routed) &&
routed_net && /* any nodes ? */
/* on pass= DoAny, consider all. */
/* on pass= CheckFixed, only those with a fixed pin on the net */
(pass == DoAny ||
(pass == CheckFixed && routed_net->has_fix_location)) &&
routed_net->list_ref == &routed_list && /* is routed net still
available on the routed
list ? */
unrouted_net->nodecount > 0) /* skip all 1-node nets, these will be
dealt with by a later routing
algorithm */
{
if (routed_net->nodecount >= unrouted_net->nodecount &&
IS_ROUTABLE (routed_net->how_routed))
{
/* enough nodes, but does it go the right places ?? */
noderef_t *unrouted_nodes = unrouted_net->nodes;
noderef_t *routed_nodes = routed_net->nodes;
clear_routing_flags (routed_nodes);
while (unrouted_nodes && f)
{
f = search_net_for_socket (
unrouted_nodes, routed_nodes, 1) !=
NULL;
unrouted_nodes = unrouted_nodes->next;
}
/* if f is 1 then the routed net connects all of the
nodes on the unrouted net */
if (f)
{
/* Can join Routed & Unrouted nets together */
/* printf("Managed '%s' for exact path
routing '%s' \n",routed_net -> identifier,
unrouted_net->identifier);
*/
combine_routed_and_unrouted (
routed_net, unrouted_net);
/* prevent this net from being recycled, move
to the fully named and routed list */
transfer_net_to_named (
&routed_list, routed_net);
routed_net->how_routed =
By_Exact_Net; /* This net was routed by
finding a wire! */
routed_ok = 1;
/*
Log (LOG_GENERAL, "#
Sucessfully routed net '%s' by exact
path\n", routed_net->name);
*/
}
}
};
if (routed_ok)
{
/* printf("Removing '%s' from
* list\n",unrouted_net->identifier);
*/
/* remove the unrouted net from the list */
unrouted_net = remove_net (&unrouted_list, unrouted_net);
}
else
{
/* Not removing net as algorithm hasnt found a match */
unrouted_net = unrouted_net->next;
}
}
} /* pass counter loop */
count_nets ("After routing by finding exactly identical paths");
}
/* ******************************************** */
void perform_routing_by_path (void)
{
net_t *unrouted_net = unrouted_list;
net_t *routed_net;
int accept_nodes;
while (unrouted_net)
{
int routed_ok = 0;
/*
printf("-- by path : identifier %s\n",unrouted_net->identifier);
*/
/* repeatedly search the routed nodes list for one with more or the same
number of connections wanted */
/* skip all 1-node nets, these will be dealt with by a later routing algorithm
*/
if (unrouted_net->nodecount > 0 && IS_ROUTABLE (unrouted_net->how_routed))
{
for (accept_nodes = unrouted_net->nodecount;
accept_nodes < MaxNodesForSearch && !routed_ok;
accept_nodes++)
{
/* locate any fix_location nodes here eventually */
routed_net = routed_list;
while (routed_net && !routed_ok)
{
if (routed_net->nodecount == accept_nodes &&
IS_ROUTABLE (routed_net->how_routed))
{
/* enough nodes, but does it go the right
* places ?? */
int f = 1;
noderef_t *unrouted_nodes =
unrouted_net->nodes;
noderef_t *routed_nodes = routed_net->nodes;
clear_routing_flags (routed_nodes);
while (unrouted_nodes && f)
{
f = search_net_for_socket (
unrouted_nodes,
routed_nodes,
1) != NULL;
unrouted_nodes = unrouted_nodes->next;
}
/* if f is 1 then the routed net connects all
of the nodes on the unrouted net */
if (f)
{
/* Can join Routed & Unrouted nets
* together */
combine_routed_and_unrouted (
routed_net, unrouted_net);
/* prevent this net from being
recycled, move to the fully named
and routed list */
transfer_net_to_named (
&routed_list, routed_net);
routed_net->how_routed =
By_Net; /* This net was routed by
finding a wire! */
routed_ok = 1;
}
}
routed_net = routed_net->next;
};
}
}
if (routed_ok)
{
/* remove the unrouted net from the list */
unrouted_net = remove_net (&unrouted_list, unrouted_net);
}
else
/* Not removing net as algorithm hasnt found a match */
unrouted_net = unrouted_net->next;
}
count_nets ("After routing by finding existing net paths");
}
/* ******************************************** */
/* this function checks all the unrouted nets to see if any of them
are connected to nodes that are known to exist on a connector, but
are not on any net. This works to join up unrouted nets mentioned in
CHIP descriptions */
void perform_routing_by_making_nets (void)
{
net_t *unrouted_net = unrouted_list;
net_t *next_net;
int failcount = 0;
while (unrouted_net)
{
int routed_ok = 0;
int f = 1;
noderef_t *unrouted_nodes;
next_net = unrouted_net->next;
if (IS_ROUTABLE (unrouted_net->how_routed))
{
unrouted_nodes = unrouted_net->nodes;
/*
printf("-- by making nets : identifier
%s\n",unrouted_net->identifier);
*/
/* repeatedly search the unrouted net list */
/* only route unconnected nodes referred to by one net,
whether routed or unrouted otherwise shorts will happen */
while (IS_ROUTABLE (unrouted_net->how_routed) && unrouted_nodes &&
((f = unrouted_nodes->node->net_assigned == 0) &&
unrouted_nodes->node->refcount == 1))
unrouted_nodes = unrouted_nodes->next;
if (!f && unrouted_nodes)
{
failcount++;
Log (
LOG_ERROR,
"-- FAIL on : net %s\n",
unrouted_net->identifier);
Log (
LOG_ERROR,
"-- node %s(%s)\n",
unrouted_nodes->node->socket->identifier,
unrouted_nodes->node->identifier);
if (unrouted_nodes->node->net_assigned)
Log (
LOG_ERROR,
"-- Node is on an already assigned net\n");
if (unrouted_nodes->node->refcount > 1)
Log (
LOG_ERROR,
"-- Node is referred to by %d nets\n",
unrouted_nodes->node->refcount);
}
/* if f is 1 then the unrouted net contains only unassigned nodes */
if (f)
{
net_t *poss_routed_net;
/* now we need to confirm that the name is unique:
search for it to see if there already*/
poss_routed_net = find_net (
&routed_list, Ident, unrouted_net->identifier, Search);
if (!poss_routed_net)
{ /* its unique */
/* prevent this net from being recycled, move to
the fully named and routed list */
combine_routed_and_unrouted (
unrouted_net, unrouted_net);
transfer_net_to_named (&unrouted_list, unrouted_net);
unrouted_net->how_routed =
By_Creating; /* This net was routed by creating a
new one !! */
Log (
LOG_GENERAL,
"-- Info: Created Wiring for net '%s'\n",
unrouted_net->identifier);
routed_ok = 1;
}
else
{
Log (
LOG_ERROR,
"-- ERROR: Net identifier '%s' already in use in "
"routed list: cannot create\n",
unrouted_net->identifier);
routed_ok = 0;
}
}
}
/* move on , either its been moved from one list to the other or its still
* there */
unrouted_net = next_net;
}
count_nets ("After routing by making nets");
}
/* ******************************************** */
/* Pruning nets that have names like rsv00000z */
/* from a list */
/* ******************************************** */
void prune_nets_from_list (net_t **list, char *res_tpl)
{
net_t *curr_net = *list;
while (curr_net)
{
int i = 0;
while ((i < RES_NAMLEN) &&
/* string match */
(res_tpl
[i
] == tolower (curr_net
->identifier
[i
]) || /* 0 in template matches a digit */
((res_tpl
[i
] == '0') && isdigit (curr_net
->identifier
[i
])))) i++;
if (i == RES_NAMLEN)
curr_net = remove_net (list, curr_net);
else
curr_net = curr_net->next;
}
}
/* ******************************************** */
void prune_nets ()
{
char res_tpl[RES_NAMLEN + 1];
sprintf (res_tpl
, RES_FMT
, 0); /* create a template, with 00000 in it */ prune_nets_from_list (&routed_list, res_tpl);
prune_nets_from_list (&unrouted_list, res_tpl);
count_nets ("After deleting dummy nets e.g. 'rsv00001z'");
}
/* ******************************************** */
/* this function is intended to check to see how many nets have got
how_routed = By_FixPins . */
void check_for_unused_fixed_nets (char *why)
{
net_t *curr_net = routed_list;
int print_flag = 1;
while (curr_net)
{
if (curr_net->how_routed == By_FixPins)
{
if (print_flag)
{
print_flag = 0;
Log (
LOG_ERROR,
"-- ERROR : fix_pin fails due to %s:\n-- Failures :\n",
why);
}
Log (
LOG_ERROR,
"-- '%s' to routed net='%s'\n",
curr_net->name,
curr_net->identifier);
}
curr_net = curr_net->next;
}
}
/* ******************************************** */
void perform_routing (HowRouted_t how)
{
count_nets ("Before fixing up pin aliases");
create_unrouted_list ();
if (need_validate_names)
{
Log (LOG_GENERAL, "# Validating net names and identifiers\n");
validate_names ();
need_validate_names = 0;
}
count_nets ("Before routing");
validate_unrouted ();
prune_nets ();
if (how == Free || how == By_Name)
{
/* get rid of all unrouted nets that have been invented in the first place */
perform_routing_by_name ();
check_for_unused_fixed_nets ("Nets already routed by name");
};
if (how == Free || how == By_Fixed_Net)
{
perform_routing_by_fixed_net ();
check_for_unused_fixed_nets ("Routed nets with fixed pins do not match "
"unrouted");
};
if (how == Free || how == By_Exact_Net)
perform_routing_by_exact_path ();
if (how == Free || how == By_Net)
perform_routing_by_path ();
if (how == By_Creating) /* Will not create missing nets !! : use creation */
perform_routing_by_making_nets ();
if (how == Free)
ensure_reservation ();
count_nets_with_few_nodes (1); /* summarise single connection nets */
}
/* ******************************************** */
/* Experimental bit of code : For all nets that connect to
a pin of an external socket in the unrouted list ,
check to see if the routed net connected to the same pin has a name assigned.
If it does not then try setting the name of the net to the identifier
of the unrouted net . Use this before routing */
void perform_trial_naming (void)
{
net_t *cur_net;
int fixed_counter = 0;
create_unrouted_list ();
cur_net = unrouted_list; /* after pin renames etc have been executed */
prune_nets (); /* will not fix rsv00000z pins !! */
while (cur_net)
{
noderef_t *nodes = cur_net->nodes;
if (level & 8)
Log (LOG_GENERAL, "# Trying to fix net '%s'\n", cur_net->identifier);
while (nodes)
{
/* is this node pointing at an external socket */
node_t *n = nodes->node;
/* only fix one routed net to this un_routed net */
if (n->socket->is_external)
{ /* on an external socket */
n->fix_location = 1; /* set the location fixed flag a*/
if (n->routed_net)
{ /* and set the flag on the routed net */
n->routed_net->unrouted_fix_net = cur_net;
n->routed_net->has_fix_location = 1;
fixed_counter++;
if (level & 8)
Log (
LOG_GENERAL,
"# to net '%s'\n",
n->routed_net->identifier);
}
}
nodes = nodes->next;
}
/*
Log (LOG_GENERAL, "#\n");
*/
cur_net = cur_net->next;
}
Log (LOG_GENERAL, "# Fixed %d pins\n", fixed_counter);
}
/* ********************************************************************* */
/* force routing flag of routed net */
void force_route (char *template, HowRouted_t flag)
{
net_t *net = routed_list;
int rc, any_found = 0;
int found;
/* compile regular expression */
vert_regex_t *preg;
rc = vert_regcomp (&preg, template);
if (rc != 0)
{
char errbuff[100];
regerror (rc, preg->preg, errbuff, 100);
Log (
LOG_ERROR,
"-- Problem (rc=%d) %s with '%s' as regular expression\n",
rc,
errbuff,
template);
/* return TCL_ERROR;
*/
return;
}
else
{
Log (LOG_GENERAL, "-- Using '%s' as match pattern\n", template);
}
while (net)
{
found = regexec (preg->preg, net->identifier, 0, preg->regpatt, 0);
if (!found)
{
char *s;
any_found = 1;
net->how_routed = flag;
switch (flag)
{
case Not_Routable:
s = "not routable";
break;
case Not_Routable_H:
s = "not routable H";
break;
case Not_Routable_L:
s = "not routable L";
break;
default:
s = "routable";
break;
}
Log (LOG_GENERAL, "-- Set net '%s' as %s\n", net->identifier, s);
}
net = net->next;
}
if (!any_found)
Log (LOG_GENERAL, "-- No nets match '%s'\n", template);
vert_regfree (&preg);
}
/* ********************************************************************* */
void set_group_route_flags (char *template, int flag)
{
int found;
socket_t *socket = socket_head;
int rc, any_found = 0;
/* compile regular expression */
vert_regex_t *preg;
rc = vert_regcomp (&preg, template);
if (rc != 0)
{
char errbuff[100];
regerror (rc, preg->preg, errbuff, 100);
Log (
LOG_ERROR,
"-- Problem (rc=%d) %s with '%s' as regular expression\n",
rc,
errbuff,
template);
/* return TCL_ERROR;
*/
return;
}
else
{
Log (LOG_GENERAL, "-- Using '%s' as match pattern\n", template);
}
Log (LOG_GENERAL, "----- Setting pin group routing flags to %d for\n", flag);
while (socket)
{
found = regexec (preg->preg, socket->identifier, 0, preg->regpatt, 0);
if (!found)
{
any_found = 1;
socket->route_flags = flag;
Log (LOG_GENERAL, "-- socket '%s'\n", socket->identifier);
}
socket = socket->next;
}
if (!any_found)
Log (LOG_GENERAL, "-- No sockets match '%s'\n", template);
vert_regfree (&preg);
}
/**************************************************************/
/* Function sets the pin group flags on a device */
/* pattern is ic.pin */
/* changed to ic(pin) */
void set_pin_group_flags (char *device_string, int flag)
{
socket_t *socket;
node_t *node;
int socket_cnt = 0, pin_cnt = 0; /* counters */
int found_socket, found_pin;
char *s = strdup (device_string);
char *p, *q;
int rc;
/* compile regular expression */
vert_regex_t *skt_reg, *pin_reg;
/* find the '(' in the socket name name */
if (p == s)
{
s = ".*"; /* wildcard for chip id */
}
if (!p || !q || q < p)
{
p = ".*"; /* wilcard for pin id */
}
else
{
*p++ = 0;
*q = 0;
}
rc = vert_regcomp (&skt_reg, s);
if (rc != 0)
{
char errbuff[100];
regerror (rc, skt_reg->preg, errbuff, 100);
Log (
LOG_ERROR,
"-- Problem (rc=%d) %s with '%s' as regular expression\n",
rc,
errbuff,
s);
/* return TCL_ERROR;
*/
return;
}
else
{
Log (LOG_GENERAL, "-- Using '%s' as socket match pattern\n", s);
}
rc = vert_regcomp (&pin_reg, p);
if (rc != 0)
{
char errbuff[100];
regerror (rc, pin_reg->preg, errbuff, 100);
Log (
LOG_ERROR,
"-- Problem (rc=%d) %s with '%s' as regular expression\n",
rc,
errbuff,
p);
/* return TCL_ERROR;
*/
return;
}
else
{
Log (LOG_GENERAL, "-- Using '%s' as socket match pattern\n", p);
}
socket = socket_head;
while (socket)
{
found_socket =
regexec (skt_reg->preg, socket->identifier, 0, skt_reg->regpatt, 0);
if (!found_socket)
{
socket_cnt++;
node = socket->nodes;
/*
Log(LOG_GENERAL,"-- Chip ID %s\n",socket->identifier);
*/
found_pin = 0;
while (node)
{
found_pin = regexec (
pin_reg->preg, node->identifier, 0, pin_reg->regpatt, 0);
if (!found_pin)
{
/*
Log(LOG_GENERAL,"-- Pin
%s.%s\n",socket->identifier,node->identifier);
*/
pin_cnt++;
node->pin_group = flag;
}
node = node->sktnext;
}
}
socket = socket->next;
}
if (socket_cnt)
Log (LOG_GENERAL, "-- Checked %d sockets\n", socket_cnt);
if (pin_cnt)
Log (
LOG_GENERAL,
"-- Set pin group to %d on a total of %d pins\n",
flag,
pin_cnt);
else
Log (LOG_GENERAL, "-- Did not locate any pins matching pattern\n");
vert_regfree (&pin_reg);
vert_regfree (&skt_reg);
}