1 /*--------------------------------------------------------------*/ 2 /* qrouter.h -- general purpose autorouter */ 3 /*--------------------------------------------------------------*/ 4 /* Written by Steve Beccue, 2003 */ 5 /* Modified by Tim Edwards 2011-2013 */ 6 /*--------------------------------------------------------------*/ 7 8 #ifndef QROUTER_H 9 10 #define OGRID(x, y) ((int)((x) + ((y) * NumChannelsX))) 11 #define MIN(x, y) (((x) < (y)) ? (x) : (y)) 12 #define MAX(x, y) (((x) > (y)) ? (x) : (y)) 13 #define ABSDIFF(x, y) (((x) > (y)) ? ((x) - (y)) : ((y) - (x))) 14 15 #define EPS 1e-4 // For handling round-off error; value 16 // is in um (so 1e-4 = 0.1nm), should be 17 // smaller than any feature size. 18 19 // For handling round-off error on signed values. REPS(x) is x + EPS when 20 // x is positive, and x - EPS when x is negative. 21 22 #define REPS(x) (((x) < 0) ? ((x) - EPS) : ((x) + EPS)) 23 24 #define TRUE 1 25 #define FALSE 0 26 27 #ifndef _SYS_TYPES_H 28 #ifndef u_char 29 typedef unsigned char u_char; 30 #endif 31 #ifndef u_short 32 typedef unsigned short u_short; 33 #endif 34 #ifndef u_int 35 typedef unsigned int u_int; 36 #endif 37 #ifndef u_long 38 typedef unsigned long u_long; 39 #endif 40 #endif /* _SYS_TYPES_H */ 41 42 /* Compare functions aren't defined in the Mac's standard library */ 43 #if defined(__APPLE__) || defined(__FreeBSD__) || defined(__OpenBSD__) || \ 44 defined(__DragonFly__) 45 typedef int (*__compar_fn_t)(const void*, const void*); 46 #endif 47 48 /* Maximum number of route layers */ 49 #define MAX_LAYERS 12 50 51 /* Maximum number of all defined layers. Since masterslice and */ 52 /* overlap types are ignored, this just includes all the cuts. */ 53 #define MAX_TYPES (MAX_LAYERS * 2 - 1) 54 55 /* Cell name (and other names) max length */ 56 #define MAX_NAME_LEN 1024 57 58 /* Max reasonable line length */ 59 #define MAX_LINE_LEN 2048 60 61 /* Default configuration filename */ 62 #define CONFIGFILENAME "route.cfg" 63 64 // define possible gate orientations 65 66 #define MNONE 0 67 #define MX 1 // flipped in X 68 #define MY 2 // flipped in Y 69 #define R90 4 // rotated clockwise 90 degrees 70 71 // define search directions 72 73 #define NORTH (u_char)1 74 #define SOUTH (u_char)2 75 #define EAST (u_char)3 76 #define WEST (u_char)4 77 #define UP (u_char)5 78 #define DOWN (u_char)6 79 80 // define types of via checkerboard patterns 81 #define VIA_PATTERN_NONE -1 82 #define VIA_PATTERN_NORMAL 0 83 #define VIA_PATTERN_INVERT 1 84 85 // linked list structure for holding a list of char * strings 86 87 typedef struct linkedstring_ *LinkedStringPtr; 88 89 typedef struct linkedstring_ { 90 char *name; 91 LinkedStringPtr next; 92 } LinkedString; 93 94 // structure holding input and output scalefactors 95 96 typedef struct scalerec_ { 97 int iscale; 98 int mscale; 99 double oscale; 100 } ScaleRec; 101 102 // structure to hold two offset values, one for x offset, one for y offset 103 104 typedef struct obsinforec_ { 105 float xoffset; 106 float yoffset; 107 } ObsInfoRec; 108 109 // define a structure containing x, y, and layer 110 111 typedef struct gridp_ GRIDP; 112 113 struct gridp_ { 114 int x; 115 int y; 116 int lay; 117 u_int cost; 118 }; 119 120 typedef struct proute_ PROUTE; 121 122 struct proute_ { // partial route 123 u_short flags; // values PR_PROCESSED and PR_CONFLICT, and others 124 union { 125 u_int cost; // cost of route coming from predecessor 126 u_int net; // net number at route point 127 } prdata; 128 }; 129 130 // Bit values for "flags" in PROUTE 131 132 #define PR_PRED_DMASK 0x007 // Mask for directional bits 133 134 #define PR_PRED_NONE 0x000 // This node does not have a predecessor 135 #define PR_PRED_N 0x001 // Predecessor is north 136 #define PR_PRED_S 0x002 // Predecessor is south 137 #define PR_PRED_E 0x003 // Predecessor is east 138 #define PR_PRED_W 0x004 // Predecessor is west 139 #define PR_PRED_U 0x005 // Predecessor is up 140 #define PR_PRED_D 0x006 // Predecessor is down 141 142 #define PR_PROCESSED 0x008 // Tag to avoid visiting more than once 143 #define PR_NO_EVAL 0x008 // Used only for making calls to eval_pt() 144 #define PR_CONFLICT 0x010 // Two nets collide here during stage 2 145 #define PR_SOURCE 0x020 // This is a source node 146 #define PR_TARGET 0x040 // This is a target node 147 #define PR_COST 0x080 // if 1, use prdata.cost, not prdata.net 148 #define PR_ON_STACK 0x100 // if 1, position has been recorded for 149 // pending evalutaion 150 151 // Linked string list 152 153 typedef struct string_ *STRING; 154 155 struct string_ { 156 STRING next; 157 char *name; 158 }; 159 160 /* Path segment information */ 161 162 #define ST_WIRE 0x01 163 #define ST_VIA 0x02 164 #define ST_OFFSET_START 0x04 /* (x1, y1) is offset from grid */ 165 #define ST_OFFSET_END 0x08 /* (x2, y2) is offset from grid */ 166 #define ST_SPECIAL 0x10 /* wide metal (special net) */ 167 #define ST_MINMETAL 0x20 /* segment for min metal area */ 168 169 typedef struct seg_ *SEG; 170 171 struct seg_ { 172 SEG next; 173 int layer; 174 int x1, y1, x2, y2; 175 u_char segtype; 176 }; 177 178 /* DSEG is like a SEG, but coordinates are in microns (therefore type double) */ 179 /* Used for gate node and obstruction positions. */ 180 181 typedef struct dseg_ *DSEG; 182 183 struct dseg_ { 184 DSEG next; 185 int layer; 186 double x1, y1, x2, y2; 187 }; 188 189 190 /* POINT is an integer point in three dimensions (layer giving the */ 191 /* vertical dimension). */ 192 193 typedef struct point_ *POINT; 194 195 struct point_ { 196 POINT next; 197 int layer; 198 int x1, y1; 199 }; 200 201 /* DPOINT is a point location with coordinates given *both* as an */ 202 /* integer (for the grid-based routing) and as a physical dimension */ 203 /* (microns). */ 204 205 typedef struct dpoint_ *DPOINT; 206 207 struct dpoint_ { 208 DPOINT next; 209 int layer; 210 double x, y; 211 int gridx, gridy; 212 }; 213 214 typedef struct route_ *ROUTE; 215 typedef struct node_ *NODE; 216 217 struct route_ { 218 ROUTE next; 219 int netnum; 220 SEG segments; 221 union { 222 ROUTE route; 223 NODE node; 224 } start; 225 union { 226 ROUTE route; 227 NODE node; 228 } end; 229 u_char flags; // See below for flags 230 }; 231 232 /* Definitions for flags in struct route_ */ 233 234 #define RT_OUTPUT 0x01 // Route has been output 235 #define RT_STUB 0x02 // Route has at least one stub route 236 #define RT_START_NODE 0x04 // Route starts on a node 237 #define RT_END_NODE 0x08 // Route ends on a node 238 #define RT_VISITED 0x10 // Flag for recursive search 239 #define RT_RIP 0x20 // Flag for route rip-up 240 #define RT_CHECK 0x40 // Route from DEF file needs checking 241 242 /* Structure used to hold nodes, saved nodes, and stub/offset info */ 243 244 typedef struct nodeinfo_ *NODEINFO; 245 246 struct nodeinfo_ { 247 NODE nodesav; 248 NODE nodeloc; 249 float stub; // Stub route to node 250 float offset; // Tap offset 251 u_char flags; 252 }; 253 254 /* Definitions for flags in stuct nodeinfo_ */ 255 256 #define NI_STUB_NS 0x01 // Stub route north(+)/south(-) 257 #define NI_STUB_EW 0x02 // Stub route east(+)/west(-) 258 #define NI_STUB_MASK 0x03 // Stub route mask (N/S + E/W) 259 #define NI_OFFSET_NS 0x04 // Tap offset north(+)/south(-) 260 #define NI_OFFSET_EW 0x08 // Tap offset east(+)/west(-) 261 #define NI_OFFSET_MASK 0x0c // Tap offset mask (N/S + E/W) 262 #define NI_NO_VIAX 0x10 // Via in ViaX array is prohibited 263 #define NI_NO_VIAY 0x20 // Via in ViaY array is prohibited 264 #define NI_VIA_X 0x40 // Placed via is oriented horizontally 265 #define NI_VIA_Y 0x80 // Placed via is oriented vertically 266 267 struct node_ { 268 NODE next; 269 int nodenum; // node ordering within its net 270 DPOINT taps; // point position for node taps 271 DPOINT extend; // point position within halo of the tap 272 char *netname; // name of net this node belongs to 273 u_char numtaps; // number of actual reachable taps 274 int netnum; // number of net this node belongs to 275 int numnodes; // number of nodes on this net 276 int branchx; // position of the node branch in x 277 int branchy; // position of the node branch in y 278 }; 279 280 // these are instances of gates in the netlist. The description of a 281 // given gate (the macro) is held in GateInfo. The same structure is 282 // used for both the macro and the instance records. 283 284 typedef struct gate_ *GATE; 285 286 struct gate_ { 287 GATE next; 288 char *gatename; // Name of instance 289 GATE gatetype; // Pointer to macro record 290 int nodes; // number of nodes on this gate 291 char **node; // names of the pins on this gate 292 int *netnum; // net number connected to each pin 293 NODE *noderec; // node record for each pin 294 float *area; // gate area for each pin 295 u_char *direction; // port direction (input, output, etc.) 296 DSEG *taps; // list of gate node locations and layers 297 DSEG obs; // list of obstructions in gate 298 double width, height; 299 double placedX; 300 double placedY; 301 int orient; 302 }; 303 304 // Define record holding information pointing to a gate and the 305 // index into a specific node of that gate. 306 307 typedef struct gatenode_ *GATENODE; 308 309 struct gatenode_ { 310 GATE gate; 311 int idx; 312 }; 313 314 // Structure for a network to be routed 315 316 typedef struct net_ *NET; 317 typedef struct netlist_ *NETLIST; 318 319 struct net_ { 320 int netnum; // a unique number for this net 321 char *netname; 322 NODE netnodes; // list of nodes connected to the net 323 int numnodes; // number of nodes connected to the net 324 u_char flags; // flags for this net (see below) 325 int netorder; // to be assigned by route strategy (critical 326 // nets first, then order by number of nodes). 327 int xmin, ymin; // Bounding box lower left corner 328 int xmax, ymax; // Bounding box upper right corner 329 int trunkx; // X position of the net's trunk line (see flags) 330 int trunky; // Y position of the net's trunk line (see flags) 331 NETLIST noripup; // list of nets that have been ripped up to 332 // route this net. This will not be allowed 333 // a second time, to avoid looping. 334 ROUTE routes; // routes for this net 335 }; 336 337 // Flags used by NET "flags" record 338 339 #define NET_PENDING 1 // pending being placed on "abandoned" list 340 #define NET_CRITICAL 2 // net is in CriticalNet list 341 #define NET_IGNORED 4 // net is ignored by router 342 #define NET_STUB 8 // Net has at least one stub 343 #define NET_VERTICAL_TRUNK 16 // Trunk line is (preferred) vertical 344 345 // List of nets, used to maintain a list of failed routes 346 347 struct netlist_ { 348 NETLIST next; 349 NET net; 350 }; 351 352 // A structure to hold information about source and target nets for 353 // a route, to be passed between the route setup and execution stages 354 355 struct routeinfo_ { 356 NET net; 357 ROUTE rt; 358 POINT glist[6]; /* Lists of points by priority 0 to 5 */ 359 NODE nsrc; 360 DPOINT nsrctap; 361 int maxcost; 362 u_char do_pwrbus; 363 int pwrbus_src; 364 struct seg_ bbox; 365 }; 366 367 #define MAXRT 10000000 // "Infinite" route cost 368 369 // The following values are added to the Obs[] structure for unobstructed 370 // route positions close to a terminal, but not close enough to connect 371 // directly. They describe which direction to go to reach the terminal. 372 // The Stub[] vector indicates the distance needed to reach the terminal. 373 // The OFFSET_TAP flag marks a position that is inside a terminal but 374 // which needs to be adjusted in one direction to avoid a close obstruction. 375 // The Stub[] vector indicates the distance needed to avoid the obstruction. 376 // 377 // The maximum number of nets must not overrun the area used by flags, so 378 // the maximum number of nets is 0x3fffff, or 4,194,303 nets 379 380 #define OFFSET_TAP ((u_int)0x80000000) // tap position needs to be offset 381 #define STUBROUTE ((u_int)0x40000000) // route stub to reach terminal 382 #define PINOBSTRUCTMASK ((u_int)0xc0000000) // either offset tap or stub route 383 #define NO_NET ((u_int)0x20000000) // indicates a non-routable obstruction 384 #define ROUTED_NET ((u_int)0x10000000) // indicates position occupied by a routed 385 386 #define BLOCKED_N ((u_int)0x08000000) // grid point cannot be routed from the N 387 #define BLOCKED_S ((u_int)0x04000000) // grid point cannot be routed from the S 388 #define BLOCKED_E ((u_int)0x02000000) // grid point cannot be routed from the E 389 #define BLOCKED_W ((u_int)0x01000000) // grid point cannot be routed from the W 390 #define BLOCKED_U ((u_int)0x00800000) // grid point cannot be routed from top 391 #define BLOCKED_D ((u_int)0x00400000) // grid point cannot be routed from bottom 392 #define BLOCKED_MASK ((u_int)0x0fc00000) 393 #define OBSTRUCT_MASK ((u_int)0x0000000f) // with NO_NET, directional obstruction 394 #define OBSTRUCT_N ((u_int)0x00000008) // Tells where the obstruction is 395 #define OBSTRUCT_S ((u_int)0x00000004) // relative to the grid point. Nodeinfo 396 #define OBSTRUCT_E ((u_int)0x00000002) // offset contains distance to grid point 397 #define OBSTRUCT_W ((u_int)0x00000001) 398 #define MAX_NETNUMS ((u_int)0x003fffff) // Maximum net number 399 400 #define NETNUM_MASK ((u_int)0x203fffff) // Mask for the net number field 401 // (includes NO_NET) 402 #define ROUTED_NET_MASK ((u_int)0x303fffff) // Mask for the net number field 403 // (includes NO_NET and ROUTED_NET) 404 #define DRC_BLOCKAGE (NO_NET | ROUTED_NET) // Special case 405 406 // Map and draw modes 407 #define MAP_NONE 0x0 // No map (blank background) 408 #define MAP_OBSTRUCT 0x1 // Make a map of obstructions and pins 409 #define MAP_CONGEST 0x2 // Make a map of congestion 410 #define MAP_ESTIMATE 0x3 // Make a map of estimated congestion 411 #define MAP_MASK 0x3 412 413 #define DRAW_NONE 0x0 // Draw only the background map 414 #define DRAW_ROUTES 0x4 // Draw routes on top of background map 415 #define DRAW_UNROUTED 0x8 // Draw unrouted nets on top of background map 416 #define DRAW_MASK 0xc 417 418 // Mask types (values other than 255 are interpreted as "slack" value) 419 #define MASK_MINIMUM (u_char)0 // No slack 420 #define MASK_SMALL (u_char)1 // Slack of +/-1 421 #define MASK_MEDIUM (u_char)2 // Slack of +/-2 422 #define MASK_LARGE (u_char)4 // Slack of +/-4 423 #define MASK_AUTO (u_char)253 // Choose best mask type 424 #define MASK_BBOX (u_char)254 // Mask is simple bounding box 425 #define MASK_NONE (u_char)255 // No mask used 426 427 // Definitions of bits in needblock 428 #define ROUTEBLOCKX (u_char)1 // Block adjacent routes in X 429 #define ROUTEBLOCKY (u_char)2 // Block adjacent routes in Y 430 #define VIABLOCKX (u_char)4 // Block adjacent vias in X 431 #define VIABLOCKY (u_char)8 // Block adjacent vias in Y 432 433 // Numnets + MIN_NET_NUMBER is guaranteed to be greater than the highest 434 // number assigned to a net. 435 #define MAXNETNUM (Numnets + MIN_NET_NUMBER) 436 437 /* Global variables */ 438 439 extern STRING DontRoute; 440 extern STRING CriticalNet; 441 extern NET CurNet; 442 extern NETLIST FailedNets; // nets that have failed the first pass 443 extern char *DEFfilename; 444 extern char *delayfilename; 445 extern ScaleRec Scales; 446 extern DPOINT testpoint; // for debugging routing problems 447 448 extern GATE GateInfo; // standard cell macro information 449 extern GATE PinMacro; // macro definition for a pin 450 extern GATE Nlgates; 451 extern NET *Nlnets; 452 453 extern u_char *RMask; 454 extern u_int *Obs[MAX_LAYERS]; // obstructions by layer, y, x 455 extern PROUTE *Obs2[MAX_LAYERS]; // working copy of Obs 456 extern ObsInfoRec *Obsinfo[MAX_LAYERS]; // temporary detailed obstruction info 457 extern NODEINFO *Nodeinfo[MAX_LAYERS]; // stub route distances to pins and 458 // pointers to node structures. 459 460 #define NODEIPTR(x, y, l) (Nodeinfo[l][OGRID(x, y)]) 461 #define OBSINFO(x, y, l) (Obsinfo[l][OGRID(x, y)]) 462 #define OBSVAL(x, y, l) (Obs[l][OGRID(x, y)]) 463 #define OBS2VAL(x, y, l) (Obs2[l][OGRID(x, y)]) 464 465 #define RMASK(x, y) (RMask[OGRID(x, y)]) 466 #define CONGEST(x, y) (Congestion[OGRID(x, y)]) 467 468 extern DSEG UserObs; // user-defined obstruction layers 469 470 extern u_char needblock[MAX_LAYERS]; 471 472 extern int Numnets; 473 extern int Pinlayers; // Number of layers containing pin info. 474 475 extern u_char Verbose; 476 extern u_char forceRoutable; 477 extern u_char maskMode; 478 extern u_char mapType; 479 extern u_char ripLimit; 480 extern u_char unblockAll; 481 482 extern char *vddnet; 483 extern char *gndnet; 484 extern char *antenna_cell; 485 486 /* Tcl output to console handling */ 487 488 #ifdef TCL_QROUTER 489 #define Fprintf tcl_printf 490 #define Flush tcl_stdflush 491 #define Vprintf tcl_vprintf 492 #else 493 #define Fprintf fprintf 494 #define Flush fflush 495 #define Vprintf vfprintf 496 #endif 497 498 /* Function prototypes */ 499 500 void update_mscale(int mscale); 501 static int next_route_setup(struct routeinfo_ *iroute, u_char stage); 502 static int route_setup(struct routeinfo_ *iroute, u_char stage); 503 int route_segs(struct routeinfo_ *iroute, u_char stage, u_char graphdebug); 504 ROUTE createemptyroute(void); 505 static void helpmessage(void); 506 507 int set_num_channels(void); 508 int allocate_obs_array(void); 509 int countlist(NETLIST net); 510 int runqrouter(int argc, char *argv[]); 511 void remove_failed(); 512 void apply_drc_blocks(int, double, double); 513 void remove_top_route(NET net); 514 char *get_annotate_info(NET net, char **pinptr); 515 516 void free_glist(struct routeinfo_ *iroute); 517 518 #ifdef TCL_QROUTER 519 void find_free_antenna_taps(char *antennacell); 520 #endif 521 522 void resolve_antenna(char *antennacell, u_char do_fix); 523 524 void createMask(NET net, u_char slack, u_char halo); 525 void createBboxMask(NET net, u_char halo); 526 527 int read_def(char *filename); 528 int write_def(char *filename); 529 530 #ifdef TCL_QROUTER 531 int write_delays(char *filename); 532 int write_spef(char *filename); 533 #endif 534 535 int dofirststage(u_char graphdebug, int debug_netnum); 536 int dosecondstage(u_char graphdebug, u_char singlestep, 537 u_char onlybreak, u_int effort); 538 int dothirdstage(u_char graphdebug, int debug_netnum, u_int effort); 539 540 int doroute(NET net, u_char stage, u_char graphdebug); 541 NET getnettoroute(int order); 542 int route_net_ripup(NET net, u_char graphdebug, u_char onlybreak); 543 544 #ifdef TCL_QROUTER 545 void tcl_printf(FILE *, const char *, ...); 546 void tcl_stdflush(FILE *); 547 void tcl_vprintf(FILE *, const char *, va_list); 548 #endif 549 550 #define QROUTER_H 551 #endif 552 553 /* end of qrouter.h */ 554