1 /*--------------------------------------------------------------*/
2 /* qrouter.c -- general purpose autorouter */
3 /* Reads LEF libraries and DEF netlists, and generates an */
4 /* annotated DEF netlist as output. */
5 /*--------------------------------------------------------------*/
6 /* Written by Tim Edwards, June 2011, based on code by Steve */
7 /* Beccue, 2003 */
8 /*--------------------------------------------------------------*/
9
10 #include <ctype.h>
11 #include <stdio.h>
12 #include <math.h>
13 #include <stdarg.h>
14 #include <stdlib.h>
15 #include <string.h>
16 #include <unistd.h>
17
18 #ifdef TCL_QROUTER
19 #include <tk.h>
20 #endif
21
22 #include "qrouter.h"
23 #include "qconfig.h"
24 #include "point.h"
25 #include "node.h"
26 #include "maze.h"
27 #include "mask.h"
28 #include "output.h"
29 #include "lef.h"
30 #include "def.h"
31 #include "graphics.h"
32
33 int TotalRoutes = 0;
34
35 NET *Nlnets; // list of nets in the design
36 NET CurNet; // current net to route, used by 2nd stage
37 STRING DontRoute; // a list of nets not to route (e.g., power)
38 STRING CriticalNet; // list of critical nets to route first
39 GATE GateInfo; // standard cell macro information
40 GATE PinMacro; // macro definition for a pin
41 GATE Nlgates; // gate instance information
42 NETLIST FailedNets; // list of nets that failed to route
43
44 u_int *Obs[MAX_LAYERS]; // net obstructions in layer
45 PROUTE *Obs2[MAX_LAYERS]; // used for pt->pt routes on layer
46 ObsInfoRec *Obsinfo[MAX_LAYERS]; // temporary array used for detailed obstruction info
47 NODEINFO *Nodeinfo[MAX_LAYERS]; // nodes and stub information is here. . .
48 DSEG UserObs; // user-defined obstruction layers
49
50 u_int progress[3]; // analysis of behavior
51
52 u_char needblock[MAX_LAYERS];
53
54 char *vddnet = NULL;
55 char *gndnet = NULL;
56 char *antenna_cell = NULL;
57
58 int Numnets = 0;
59 int Pinlayers = 0;
60 u_int minEffort = 0; // Minimum effort applied from command line.
61 u_char Verbose = 3; // Default verbose level
62 u_char forceRoutable = FALSE;
63 u_char maskMode = MASK_AUTO;
64 u_char mapType = MAP_OBSTRUCT | DRAW_ROUTES;
65 u_char ripLimit = 10; // Fail net rather than rip up more than
66 // this number of other nets.
67 u_char unblockAll = FALSE;
68
69 char *DEFfilename = NULL;
70 char *delayfilename = NULL;
71
72 DPOINT testpoint = NULL; // used for debugging route problems
73
74 ScaleRec Scales; // record of input and output scales
75
76 /*--------------------------------------------------------------*/
77 /* Upate the output scale factor. It has to be a valid DEF */
78 /* scale factor and it has to be a multiple of the given scale */
79 /* factor. */
80 /*--------------------------------------------------------------*/
81
82 void
update_mscale(int mscale)83 update_mscale(int mscale)
84 {
85 static int valid_mscales[] = {100, 200, 1000, 2000, 10000, 20000};
86 int nscales = sizeof(valid_mscales) / sizeof(valid_mscales[0]);
87 int mscale2, i;
88
89 if (mscale == 0) return;
90
91 if ((Scales.mscale % mscale) != 0) {
92 // Check valid scale values; if none is appropriate, don't update
93 for (i = 0; i < nscales; i++) {
94 mscale2 = valid_mscales[i];
95 if (mscale2 <= Scales.mscale) continue;
96 if ((mscale2 % mscale) == 0) {
97 Scales.mscale = mscale2;
98 break;
99 }
100 }
101 }
102 }
103
104
105 /*--------------------------------------------------------------*/
106 /* Check track pitch and set the number of channels (may be */
107 /* called from DefRead) */
108 /*--------------------------------------------------------------*/
109
set_num_channels(void)110 int set_num_channels(void)
111 {
112 int i, glimitx, glimity;
113 NET net;
114 NODE node;
115 DPOINT ctap, ltap, ntap;
116
117 if (NumChannelsX != 0) return 0; /* Already been called */
118
119 if (PitchX == 0.0) {
120 Fprintf(stderr, "Have a 0 pitch for X direction. Exit.\n");
121 return (-3);
122 }
123 else if (PitchY == 0.0) {
124 Fprintf(stderr, "Have a 0 pitch for Y direction. Exit.\n");
125 return (-3);
126 }
127
128 NumChannelsX = (int)(1.5 + (Xupperbound - Xlowerbound) / PitchX);
129 NumChannelsY = (int)(1.5 + (Yupperbound - Ylowerbound) / PitchY);
130 if ((Verbose > 1) || (NumChannelsX <= 0))
131 Fprintf(stdout, "Number of x channels is %d\n", NumChannelsX);
132 if ((Verbose > 1) || (NumChannelsY <= 0))
133 Fprintf(stdout, "Number of y channels is %d\n", NumChannelsY);
134
135 if (NumChannelsX <= 0) {
136 Fprintf(stderr, "Something wrong with x bounds.\n");
137 return(-3);
138 }
139 if (NumChannelsY <= 0) {
140 Fprintf(stderr, "Something wrong with y bounds.\n");
141 return(-3);
142 }
143 Flush(stdout);
144
145 // Go through all nodes and remove any tap or extend entries that are
146 // out of bounds.
147
148 for (i = 0; i < Numnets; i++) {
149 net = Nlnets[i];
150 for (node = net->netnodes; node != NULL; node = node->next) {
151
152 ltap = NULL;
153 for (ctap = node->taps; ctap != NULL; ) {
154 ntap = ctap->next;
155 glimitx = NumChannelsX;
156 glimity = NumChannelsY;
157 if (ctap->gridx < 0 || ctap->gridx >= glimitx ||
158 ctap->gridy < 0 || ctap->gridy >= glimity) {
159 /* Remove ctap */
160 if (ltap == NULL)
161 node->taps = ntap;
162 else
163 ltap->next = ntap;
164 }
165 else
166 ltap = ctap;
167 ctap = ntap;
168 }
169
170 ltap = NULL;
171 for (ctap = node->extend; ctap != NULL; ) {
172 ntap = ctap->next;
173 glimitx = NumChannelsX;
174 glimity = NumChannelsY;
175 if (ctap->gridx < 0 || ctap->gridx >= glimitx ||
176 ctap->gridy < 0 || ctap->gridy >= glimity) {
177 /* Remove ctap */
178 if (ltap == NULL)
179 node->taps = ntap;
180 else
181 ltap->next = ntap;
182 }
183 else
184 ltap = ctap;
185 ctap = ntap;
186 }
187 }
188 }
189
190 if (recalc_spacing()) draw_layout();
191 return 0;
192 }
193
194 /*--------------------------------------------------------------*/
195 /* Allocate the Obs[] array (may be called from DefRead) */
196 /*--------------------------------------------------------------*/
197
allocate_obs_array(void)198 int allocate_obs_array(void)
199 {
200 int i;
201
202 if (Obs[0] != NULL) return 0; /* Already been called */
203
204 for (i = 0; i < Num_layers; i++) {
205 Obs[i] = (u_int *)calloc(NumChannelsX * NumChannelsY,
206 sizeof(u_int));
207 if (!Obs[i]) {
208 Fprintf(stderr, "Out of memory 4.\n");
209 return(4);
210 }
211 }
212 return 0;
213 }
214
215 /*--------------------------------------------------------------*/
216 /* countlist --- */
217 /* Count the number of entries in a simple linked list */
218 /*--------------------------------------------------------------*/
219
220 int
countlist(NETLIST net)221 countlist(NETLIST net)
222 {
223 NETLIST nptr = net;
224 int count = 0;
225
226 while (nptr != NULL) {
227 count++;
228 nptr = nptr->next;
229 }
230 return count;
231 }
232
233 /*--------------------------------------------------------------*/
234 /* runqrouter - main program entry point, parse command line */
235 /* */
236 /* ARGS: argc (count) argv, command line */
237 /* RETURNS: to OS */
238 /* SIDE EFFECTS: */
239 /*--------------------------------------------------------------*/
240
241 int
runqrouter(int argc,char * argv[])242 runqrouter(int argc, char *argv[])
243 {
244 int i;
245 FILE *configFILEptr, *infoFILEptr;
246 static char configdefault[] = CONFIGFILENAME;
247 char *configfile = configdefault;
248 char *infofile = NULL;
249 char *dotptr;
250 char *Filename = NULL;
251 u_char readconfig = FALSE;
252 u_char doscript = FALSE;
253
254 Scales.iscale = 1;
255 Scales.mscale = 100;
256
257 /* Parse arguments */
258
259 for (i = 0; i < argc; i++) {
260 char optc, argsep = '\0';
261 char *optarg = NULL;
262
263 if (*argv[i] == '-') {
264
265 /* 1st pass---look for which options require an argument */
266 optc = *(argv[i] + 1);
267
268 switch (optc) {
269 case 'c':
270 case 'i':
271 case 'e':
272 case 'k':
273 case 'v':
274 case 'd':
275 case 'p':
276 case 'g':
277 case 'r':
278 case 's':
279 argsep = *(argv[i] + 2);
280 if (argsep == '\0') {
281 i++;
282 if (i < argc) {
283 optarg = argv[i];
284 if (*optarg == '-') {
285 Fprintf(stderr, "Option -%c needs an argument.\n", optc);
286 Fprintf(stderr, "Option not handled.\n");
287 continue;
288 }
289 }
290 else {
291 Fprintf(stderr, "Option -%c needs an argument.\n", optc);
292 Fprintf(stderr, "Option not handled.\n");
293 continue;
294 }
295 }
296 else
297 optarg = argv[i] + 2;
298 }
299
300 /* Now handle each option individually */
301
302 switch (optc) {
303 case 'c':
304 configfile = strdup(optarg);
305 break;
306 case 'v':
307 Verbose = atoi(optarg);
308 break;
309 case 'i':
310 infofile = strdup(optarg);
311 break;
312 case 'd':
313 if (delayfilename != NULL) free(delayfilename);
314 delayfilename = strdup(optarg);
315 break;
316 case 'p':
317 vddnet = strdup(optarg);
318 break;
319 case 'g':
320 gndnet = strdup(optarg);
321 break;
322 case 's':
323 // The "-s" argument is not handled here but is used
324 // to avoid generating a warning message.
325 doscript = TRUE;
326 break;
327 case 'r':
328 if (sscanf(optarg, "%d", &Scales.iscale) != 1) {
329 Fprintf(stderr, "Bad resolution scalefactor \"%s\", "
330 "integer expected.\n", optarg);
331 Scales.iscale = 1;
332 }
333 break;
334 case 'h':
335 helpmessage();
336 return 1;
337 break;
338 case 'f':
339 forceRoutable = TRUE;
340 break;
341 case 'k':
342 Fprintf(stdout, "Option \"k\" deprecated. Use \"effort\""
343 " in stage2 or stage3 command or -e option\n");
344 minEffort = 100 * atoi(optarg);
345 break;
346 case 'e':
347 minEffort = atoi(optarg);
348 break;
349 case 'n':
350 /* Ignore '-noc' or '-nog', handled elsewhere */
351 break;
352 case '\0':
353 /* Ignore '-' */
354 break;
355 case '-':
356 /* Ignore '--' */
357 break;
358 default:
359 Fprintf(stderr, "Bad option -%c, ignoring.\n", optc);
360 }
361 }
362 else {
363 /* Not an option or an option argument, so treat as a filename */
364 Filename = strdup(argv[i]);
365 }
366 }
367
368 if (infofile != NULL) {
369 infoFILEptr = fopen(infofile, "w" );
370 free(infofile);
371 }
372 else {
373 infoFILEptr = NULL;
374 #ifndef TCL_QROUTER
375 fprintf(stdout, "Qrouter detail maze router version %s.%s\n", VERSION, REVISION);
376 #endif
377 }
378
379 if (!doscript) {
380 configFILEptr = fopen(configfile, "r");
381
382 if (configFILEptr) {
383 read_config(configFILEptr, (infoFILEptr == NULL) ? FALSE : TRUE);
384 readconfig = TRUE;
385 }
386 else {
387 if (configfile != configdefault)
388 Fprintf(stderr, "Could not open %s\n", configfile );
389 else
390 Fprintf(stdout, "No .cfg file specified, continuing without.\n");
391 }
392 if (configfile != configdefault) free(configfile);
393 }
394
395 if (infoFILEptr != NULL) {
396
397 /* Print qrouter name and version number at the top */
398 #ifdef TCL_QROUTER
399 fprintf(infoFILEptr, "qrouter %s.%s.T\n", VERSION, REVISION);
400 #else
401 fprintf(infoFILEptr, "qrouter %s.%s\n", VERSION, REVISION);
402 #endif
403 /* Output database units expected by the technology LEF file */
404 /* Note that this comes from MANUFACTURINGGRID, not UNITS DATABASE */
405 fprintf(infoFILEptr, "units scale %d\n", Scales.mscale);
406
407 /* Resolve base horizontal and vertical pitches. */
408 post_config(TRUE);
409
410 /* Print information about route layers, and exit */
411 for (i = 0; i < Num_layers; i++) {
412 double pitch, width;
413 int vnum, hnum;
414 int o = LefGetRouteOrientation(i);
415 char *layername = LefGetRouteName(i);
416
417 check_variable_pitch(i, &hnum, &vnum);
418
419 if (layername != NULL) {
420 pitch = (o == 1) ? PitchY : PitchX,
421 width = LefGetRouteWidth(i);
422 if (pitch == 0.0 || width == 0.0) continue;
423 fprintf(infoFILEptr, "%s %g %g %g %s",
424 layername, pitch,
425 LefGetRouteOffset(i), width,
426 (o == 1) ? "horizontal" : "vertical");
427 if (o == 1 && vnum > 1)
428 fprintf(infoFILEptr, " %d", vnum);
429 else if (o == 0 && hnum > 1)
430 fprintf(infoFILEptr, " %d", hnum);
431 fprintf(infoFILEptr, "\n");
432 }
433 }
434
435 fclose(infoFILEptr);
436 return 1;
437 }
438
439 if (Filename != NULL) {
440
441 /* process last non-option string */
442
443 dotptr = strrchr(Filename, '.');
444 if (dotptr != NULL) *dotptr = '\0';
445 if (DEFfilename != NULL) free(DEFfilename);
446 DEFfilename = (char *)malloc(strlen(Filename) + 5);
447 sprintf(DEFfilename, "%s.def", Filename);
448 }
449 else if (readconfig) {
450 Fprintf(stdout, "No netlist file specified, continuing without.\n");
451
452 // Print help message but continue normally.
453 helpmessage();
454 }
455
456 Obs[0] = (u_int *)NULL;
457 NumChannelsX = 0; // This is so we can check if NumChannelsX/Y were
458 // set from within DefRead() due to reading in
459 // existing nets.
460
461 Scales.oscale = 1.0;
462 return 0;
463 }
464
465 /*--------------------------------------------------------------*/
466 /* remove_from_failed --- */
467 /* */
468 /* Remove one net from the list of failing nets. If "net" was */
469 /* in the list FailedNets, then return TRUE, otherwise return */
470 /* FALSE. */
471 /*--------------------------------------------------------------*/
472
remove_from_failed(NET net)473 u_char remove_from_failed(NET net)
474 {
475 NETLIST nl, lastnl;
476
477 lastnl = (NETLIST)NULL;
478 for (nl = FailedNets; nl; nl = nl->next) {
479 if (nl->net == net) {
480 if (lastnl == NULL)
481 FailedNets = nl->next;
482 else
483 lastnl->next = nl->next;
484 free(nl);
485 return TRUE;
486 }
487 lastnl = nl;
488 }
489 return FALSE;
490 }
491
492 /*--------------------------------------------------------------*/
493 /* remove_failed --- */
494 /* */
495 /* Free up memory in the list of route failures. */
496 /*--------------------------------------------------------------*/
497
remove_failed()498 void remove_failed()
499 {
500 NETLIST nl;
501 while (FailedNets) {
502 nl = FailedNets;
503 FailedNets = FailedNets->next;
504 free(nl);
505 }
506 }
507
508 /*--------------------------------------------------------------*/
509 /* Remove the first (top) route record from a net */
510 /*--------------------------------------------------------------*/
511
remove_top_route(NET net)512 void remove_top_route(NET net)
513 {
514 ROUTE rt;
515 SEG seg;
516
517 rt = net->routes;
518 net->routes = net->routes->next;
519 while (rt->segments) {
520 seg = rt->segments;
521 rt->segments = rt->segments->next;
522 free(seg);
523 }
524 free(rt);
525 }
526
527 /*--------------------------------------------------------------*/
528 /* reinitialize --- */
529 /* */
530 /* Free up memory in preparation for reading another DEF file */
531 /*--------------------------------------------------------------*/
532
reinitialize()533 static void reinitialize()
534 {
535 int i, j;
536 NETLIST nl;
537 NET net;
538 ROUTE rt;
539 SEG seg;
540 DSEG obs, tap;
541 NODE node;
542 GATE gate;
543 DPOINT dpt;
544
545 // Free up all of the matrices
546
547 for (i = 0; i < Pinlayers; i++) {
548 for (j = 0; j < NumChannelsX * NumChannelsY; j++)
549 if (Nodeinfo[i][j])
550 free(Nodeinfo[i][j]);
551 free(Nodeinfo[i]);
552 Nodeinfo[i] = NULL;
553 }
554 for (i = 0; i < Num_layers; i++) {
555 free(Obs2[i]);
556 free(Obs[i]);
557
558 Obs2[i] = NULL;
559 Obs[i] = NULL;
560 }
561 if (RMask != NULL) {
562 free(RMask);
563 RMask = NULL;
564 }
565
566 // Free the netlist of failed nets (if there is one)
567
568 remove_failed();
569
570 // Free all net and route information
571
572 for (i = 0; i < Numnets; i++) {
573 net = Nlnets[i];
574 while (net->noripup) {
575 nl = net->noripup;
576 net->noripup = net->noripup->next;
577 free(nl);
578 }
579 while (net->routes)
580 remove_top_route(net);
581
582 while (net->netnodes) {
583 node = net->netnodes;
584 net->netnodes = net->netnodes->next;
585
586 while (node->taps) {
587 dpt = node->taps;
588 node->taps = node->taps->next;
589 free(dpt);
590 }
591 while (node->extend) {
592 dpt = node->extend;
593 node->extend = node->extend->next;
594 free(dpt);
595 }
596 // Note: node->netname is not allocated
597 // but copied from net record
598 free(node);
599 }
600 free (net->netname);
601 free (net);
602 }
603 free(Nlnets);
604 Nlnets = NULL;
605 Numnets = 0;
606
607 // Free all gates information
608
609 while (Nlgates) {
610 gate = Nlgates;
611 Nlgates = Nlgates->next;
612 while (gate->obs) {
613 obs = gate->obs;
614 gate->obs = gate->obs->next;
615 free(obs);
616 }
617 for (i = 0; i < gate->nodes; i++) {
618 while (gate->taps[i]) {
619 tap = gate->taps[i];
620 gate->taps[i] = gate->taps[i]->next;
621 free(tap);
622 }
623 // Note: gate->node[i] is not allocated
624 // but copied from cell record in GateInfo
625 // Likewise for gate->noderec[i]
626 }
627
628 free(gate->gatename);
629 }
630 Nlgates = NULL;
631 }
632
633 /*--------------------------------------------------------------*/
634 /* apply_drc_blocks() --- */
635 /* */
636 /* Use via and route width and spacing information to determine */
637 /* if blockages are needed in tracks adjacent to routed */
638 /* segments to avoid causing DRC errors in the output. */
639 /* */
640 /* If layer == -1, then determine values normally for all */
641 /* route layers. If layer >= 0, determine values for specified */
642 /* layer only. If via_except > 0, then adjust the value for */
643 /* a DRC violating distance for vias in adjacent tracks by that */
644 /* amount (in microns). If route_except > 0, then adjust the */
645 /* value for a DRC violating distance between a via and a route */
646 /* in adjacent tracks by that amount. */
647 /*--------------------------------------------------------------*/
648
apply_drc_blocks(int layer,double via_except,double route_except)649 void apply_drc_blocks(int layer, double via_except, double route_except)
650 {
651 int i;
652 double sreq1, sreq2, sreq2t;
653
654 // Fill in needblock bit fields, which are used by commit_proute
655 // when route layers are too large for the grid size, and grid points
656 // around a route need to be marked as blocked whenever something is
657 // routed on those layers.
658
659 // "ROUTEBLOCK" is set if the spacing is violated between a normal
660 // route and an adjacent via. "VIABLOCK" is set if the spacing is
661 // violated between two adjacent vias. It may be helpful to define
662 // a third category which is route-to-route spacing violation.
663
664 // There are up to four different via types per base layer with
665 // different geometries based on the permutation of rotations of
666 // the top and bottom layers, so we only register blocking behavior
667 // if all of the via types will generate spacing violations.
668
669 for (i = 0; i < Num_layers; i++) {
670 if ((layer >= 0) && (i != layer)) continue;
671
672 needblock[i] = FALSE;
673
674 sreq1 = LefGetRouteSpacing(i);
675 if (i < Num_layers - 1) {
676 sreq2 = LefGetXYViaWidth(i, i, 0, 0) + sreq1;
677 sreq2t = LefGetXYViaWidth(i, i, 0, 1) + sreq1;
678 if (sreq2t < sreq2) sreq2 = sreq2t;
679 sreq2t = LefGetXYViaWidth(i, i, 0, 2) + sreq1;
680 if (sreq2t < sreq2) sreq2 = sreq2t;
681 sreq2t = LefGetXYViaWidth(i, i, 0, 3) + sreq1;
682 if (sreq2t < sreq2) sreq2 = sreq2t;
683 sreq2 -= via_except;
684 if ((sreq2 - EPS) > PitchX) needblock[i] |= VIABLOCKX;
685 }
686 if (i != 0) {
687 sreq2 = LefGetXYViaWidth(i - 1, i, 0, 0) + sreq1;
688 sreq2t = LefGetXYViaWidth(i - 1, i, 0, 1) + sreq1;
689 if (sreq2t < sreq2) sreq2 = sreq2t;
690 sreq2t = LefGetXYViaWidth(i - 1, i, 0, 2) + sreq1;
691 if (sreq2t < sreq2) sreq2 = sreq2t;
692 sreq2t = LefGetXYViaWidth(i - 1, i, 0, 3) + sreq1;
693 if (sreq2t < sreq2) sreq2 = sreq2t;
694 sreq2 -= via_except;
695 if ((sreq2 - EPS) > PitchX) needblock[i] |= VIABLOCKX;
696 }
697
698 if (i < Num_layers - 1) {
699 sreq2 = LefGetXYViaWidth(i, i, 1, 0) + sreq1;
700 sreq2t = LefGetXYViaWidth(i, i, 1, 1) + sreq1;
701 if (sreq2t < sreq2) sreq2 = sreq2t;
702 sreq2t = LefGetXYViaWidth(i, i, 1, 2) + sreq1;
703 if (sreq2t < sreq2) sreq2 = sreq2t;
704 sreq2t = LefGetXYViaWidth(i, i, 1, 3) + sreq1;
705 if (sreq2t < sreq2) sreq2 = sreq2t;
706 sreq2 -= via_except;
707 if ((sreq2 - EPS) > PitchY) needblock[i] |= VIABLOCKY;
708 }
709 if (i != 0) {
710 sreq2 = LefGetXYViaWidth(i - 1, i, 1, 0) + sreq1;
711 sreq2t = LefGetXYViaWidth(i - 1, i, 1, 1) + sreq1;
712 if (sreq2t < sreq2) sreq2 = sreq2t;
713 sreq2t = LefGetXYViaWidth(i - 1, i, 1, 2) + sreq1;
714 if (sreq2t < sreq2) sreq2 = sreq2t;
715 sreq2t = LefGetXYViaWidth(i - 1, i, 1, 3) + sreq1;
716 if (sreq2t < sreq2) sreq2 = sreq2t;
717 sreq2 -= via_except;
718 if ((sreq2 - EPS) > PitchY) needblock[i] |= VIABLOCKY;
719 }
720
721 sreq1 += 0.5 * LefGetRouteWidth(i);
722
723 if (i < Num_layers - 1) {
724 sreq2 = sreq1 + 0.5 * LefGetXYViaWidth(i, i, 0, 0);
725 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i, i, 0, 1);
726 if (sreq2t < sreq2) sreq2 = sreq2t;
727 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i, i, 0, 2);
728 if (sreq2t < sreq2) sreq2 = sreq2t;
729 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i, i, 0, 3);
730 if (sreq2t < sreq2) sreq2 = sreq2t;
731 sreq2 -= route_except;
732 if ((sreq2 - EPS) > PitchX) needblock[i] |= ROUTEBLOCKX;
733 }
734 if (i != 0) {
735 sreq2 = sreq1 + 0.5 * LefGetXYViaWidth(i - 1, i, 0, 0);
736 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i - 1, i, 0, 1);
737 if (sreq2t < sreq2) sreq2 = sreq2t;
738 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i - 1, i, 0, 2);
739 if (sreq2t < sreq2) sreq2 = sreq2t;
740 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i - 1, i, 0, 3);
741 if (sreq2t < sreq2) sreq2 = sreq2t;
742 sreq2 -= route_except;
743 if ((sreq2 - EPS) > PitchX) needblock[i] |= ROUTEBLOCKX;
744 }
745
746 if (i < Num_layers - 1) {
747 sreq2 = sreq1 + 0.5 * LefGetXYViaWidth(i, i, 1, 0);
748 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i, i, 1, 1);
749 if (sreq2t < sreq2) sreq2 = sreq2t;
750 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i, i, 1, 2);
751 if (sreq2t < sreq2) sreq2 = sreq2t;
752 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i, i, 1, 3);
753 if (sreq2t < sreq2) sreq2 = sreq2t;
754 sreq2 -= route_except;
755 if ((sreq2 - EPS) > PitchY) needblock[i] |= ROUTEBLOCKY;
756 }
757 if (i != 0) {
758 sreq2 = sreq1 + 0.5 * LefGetXYViaWidth(i - 1, i, 1, 0);
759 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i - 1, i, 1, 1);
760 if (sreq2t < sreq2) sreq2 = sreq2t;
761 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i - 1, i, 1, 2);
762 if (sreq2t < sreq2) sreq2 = sreq2t;
763 sreq2t = sreq1 + 0.5 * LefGetXYViaWidth(i - 1, i, 1, 3);
764 if (sreq2t < sreq2) sreq2 = sreq2t;
765 sreq2 -= route_except;
766 if ((sreq2 - EPS) > PitchY) needblock[i] |= ROUTEBLOCKY;
767 }
768 }
769 }
770
771 /*--------------------------------------------------------------*/
772 /* remove_tap_blocks */
773 /* */
774 /* Qrouter avoids routing directly over a tap point, blocking */
775 /* it, if there is a Nodeinfo[][]->nodeloc entry present. */
776 /* Remove this entry to remove the blockage (it can be */
777 /* replaced if needed by copying back the Nodeinfo[][]->nodesav */
778 /* pointer) */
779 /*--------------------------------------------------------------*/
780
781 void
remove_tap_blocks(int netnum)782 remove_tap_blocks(int netnum)
783 {
784 int i, j;
785 NODE node;
786
787 for (i = 0; i < Pinlayers; i++) {
788 for (j = 0; j < NumChannelsX * NumChannelsY; j++) {
789 if (Nodeinfo[i][j]) {
790 node = Nodeinfo[i][j]->nodeloc;
791 if (node != (NODE)NULL)
792 if (node->netnum == netnum)
793 Nodeinfo[i][j]->nodeloc = (NODE)NULL;
794 }
795 }
796 }
797 }
798
799 /*--------------------------------------------------------------*/
800 /* post_def_setup --- */
801 /* */
802 /* Things to do after a DEF file has been read in, and the size */
803 /* of the layout, components, and nets are known. */
804 /*--------------------------------------------------------------*/
805
post_def_setup()806 static int post_def_setup()
807 {
808 NET net;
809 ROUTE rt;
810 DPOINT tpoint;
811 int i;
812
813 if (DEFfilename == NULL) {
814 Fprintf(stderr, "No DEF file read, nothing to set up.\n");
815 return 1;
816 }
817 else {
818 if (Num_layers <= 0) {
819 Fprintf(stderr, "No routing layers defined, nothing to do.\n");
820 return 1;
821 }
822 }
823
824 for (i = 0; i < Numnets; i++) {
825 net = Nlnets[i];
826 find_bounding_box(net);
827 defineRouteTree(net);
828 }
829
830 create_netorder(0); // Choose ordering method (0 or 1)
831
832 set_num_channels(); // If not called from DefRead()
833 allocate_obs_array(); // If not called from DefRead()
834
835 initMask();
836
837 for (i = 0; i < Num_layers; i++) {
838
839 Obsinfo[i] = (ObsInfoRec *)calloc(NumChannelsX * NumChannelsY,
840 sizeof(ObsInfoRec));
841 if (!Obsinfo[i]) {
842 fprintf(stderr, "Out of memory 5.\n");
843 exit(5);
844 }
845
846 Nodeinfo[i] = (NODEINFO *)calloc(NumChannelsX * NumChannelsY,
847 sizeof(NODEINFO));
848 if (!Nodeinfo[i]) {
849 fprintf( stderr, "Out of memory 6.\n");
850 exit(6);
851 }
852 }
853 Flush(stdout);
854
855 if (Verbose > 1)
856 Fprintf(stderr, "Diagnostic: memory block is %d bytes\n",
857 (int)sizeof(u_int) * NumChannelsX * NumChannelsY);
858
859 /* If any watch points were made, make sure that they have */
860 /* the correct geometry values, since they were made before */
861 /* the DEF file was read. */
862
863 for (tpoint = testpoint; tpoint; tpoint = tpoint->next) {
864 if (tpoint->gridx < 0) {
865 /* Compute gridx,y from x,y */
866 tpoint->gridx = (int)(round((tpoint->x - Xlowerbound) / PitchX));
867 tpoint->gridy = (int)(round((tpoint->y - Xlowerbound) / PitchX));
868 }
869 else {
870 /* Compute x,y from gridx,y */
871 tpoint->x = (tpoint->gridx * PitchX) + Xlowerbound;
872 tpoint->y = (tpoint->gridy * PitchY) + Ylowerbound;
873 }
874 }
875
876 /* Be sure to create obstructions from gates first, since we don't */
877 /* want improperly defined or positioned obstruction layers to over- */
878 /* write our node list. */
879
880 expand_tap_geometry();
881 clip_gate_taps();
882 create_obstructions_from_gates();
883 create_obstructions_inside_nodes();
884 create_obstructions_outside_nodes();
885 tap_to_tap_interactions();
886 create_obstructions_from_variable_pitch();
887 adjust_stub_lengths();
888 find_route_blocks();
889 count_reachable_taps(unblockAll);
890 count_pinlayers();
891
892 // If any nets are pre-routed, calculate route endpoints, and
893 // place those routes.
894
895 for (i = 0; i < Numnets; i++) {
896 net = Nlnets[i];
897 for (rt = net->routes; rt; rt = rt->next)
898 route_set_connections(net, rt);
899 writeback_all_routes(net);
900 }
901
902 // Remove the Obsinfo array, which is no longer needed, and allocate
903 // the Obs2 array for costing information
904
905 for (i = 0; i < Num_layers; i++) free(Obsinfo[i]);
906
907 for (i = 0; i < Num_layers; i++) {
908 Obs2[i] = (PROUTE *)calloc(NumChannelsX * NumChannelsY,
909 sizeof(PROUTE));
910 if (!Obs2[i]) {
911 fprintf( stderr, "Out of memory 9.\n");
912 exit(9);
913 }
914 }
915
916 // Remove tap blocks from power, ground, and antenna nets, as these
917 // can take up large areas of the layout and will cause serious issues
918 // with routability if left blocked.
919
920 remove_tap_blocks(VDD_NET);
921 remove_tap_blocks(GND_NET);
922 remove_tap_blocks(ANTENNA_NET);
923
924 // Now we have netlist data, and can use it to get a list of nets.
925
926 FailedNets = (NETLIST)NULL;
927 Flush(stdout);
928 if (Verbose > 0)
929 Fprintf(stdout, "There are %d nets in this design.\n", Numnets);
930
931 return 0;
932 }
933
934 /*--------------------------------------------------------------*/
935 /* read_def --- */
936 /* */
937 /* Read in the DEF file in DEFfilename */
938 /* Return 0 on success, 1 on fatal error in DEF file. */
939 /*--------------------------------------------------------------*/
940
read_def(char * filename)941 int read_def(char *filename)
942 {
943 float oscale;
944 double precis;
945 int result;
946
947 if ((filename == NULL) && (DEFfilename == NULL)) {
948 Fprintf(stderr, "No DEF file specified, nothing to read.\n");
949 return 1;
950 }
951 else if (filename != NULL) {
952 if (DEFfilename != NULL) {
953 reinitialize();
954 free(DEFfilename);
955 }
956 DEFfilename = strdup(filename);
957 }
958 else reinitialize();
959
960 oscale = (float)0.0;
961 result = DefRead(DEFfilename, &oscale);
962 precis = Scales.mscale / (double)oscale; // from LEF manufacturing grid
963 if (precis < 1.0) precis = 1.0;
964 precis *= (double)Scales.iscale; // user-defined extra scaling
965
966 Scales.iscale = (int)(precis + 0.5);
967 Scales.oscale = (double)(Scales.iscale * oscale);
968
969 if (Verbose > 0)
970 Fprintf(stdout, "Output scale = microns / %g, precision %g\n",
971 Scales.oscale / (double)Scales.iscale,
972 1.0 / (double)Scales.iscale);
973
974 post_def_setup();
975 return result;
976 }
977
978 /*--------------------------------------------------------------*/
979 /*--------------------------------------------------------------*/
980
dofirststage(u_char graphdebug,int debug_netnum)981 int dofirststage(u_char graphdebug, int debug_netnum)
982 {
983 int i, failcount, remaining, result;
984 NET net;
985 NETLIST nl;
986
987 // Clear the lists of failed routes, in case first
988 // stage is being called more than once.
989
990 if (debug_netnum <= 0) remove_failed();
991
992 // Now find and route all the nets
993
994 remaining = Numnets;
995
996 for (i = (debug_netnum >= 0) ? debug_netnum : 0; i < Numnets; i++) {
997
998 net = getnettoroute(i);
999 if ((net != NULL) && (net->netnodes != NULL)) {
1000 result = doroute(net, FALSE, graphdebug);
1001 if (result == 0) {
1002 remaining--;
1003 if (Verbose > 0)
1004 Fprintf(stdout, "Finished routing net %s\n", net->netname);
1005 Fprintf(stdout, "Nets remaining: %d\n", remaining);
1006 Flush(stdout);
1007 }
1008 else {
1009 if (Verbose > 0)
1010 Fprintf(stdout, "Failed to route net %s\n", net->netname);
1011 }
1012 }
1013 else {
1014 if (net && (Verbose > 0)) {
1015 Fprintf(stdout, "Nothing to do for net %s\n", net->netname);
1016 }
1017 remaining--;
1018 }
1019 if (debug_netnum >= 0) break;
1020 }
1021 failcount = countlist(FailedNets);
1022 if (debug_netnum >= 0) return failcount;
1023
1024 if (Verbose > 0) {
1025 Flush(stdout);
1026 Fprintf(stdout, "\n----------------------------------------------\n");
1027 Fprintf(stdout, "Progress: ");
1028 Fprintf(stdout, "Stage 1 total routes completed: %d\n", TotalRoutes);
1029 }
1030 if (FailedNets == (NETLIST)NULL)
1031 Fprintf(stdout, "No failed routes!\n");
1032 else {
1033 if (FailedNets != (NETLIST)NULL)
1034 Fprintf(stdout, "Failed net routes: %d\n", failcount);
1035 }
1036 if (Verbose > 0)
1037 Fprintf(stdout, "----------------------------------------------\n");
1038
1039 return failcount;
1040 }
1041
1042 /*--------------------------------------------------------------*/
1043 /* getnettoroute - get a net to route */
1044 /* */
1045 /* ARGS: */
1046 /* RETURNS: */
1047 /* SIDE EFFECTS: */
1048 /* AUTHOR and DATE: steve beccue Fri Aug 8 */
1049 /*--------------------------------------------------------------*/
1050
getnettoroute(int order)1051 NET getnettoroute(int order)
1052 {
1053 NET net;
1054
1055 net = Nlnets[order];
1056 if (net == NULL) return NULL;
1057
1058 if (net->flags & NET_IGNORED) return NULL;
1059 if (net->numnodes >= 2) return net;
1060
1061 // Qrouter will route power and ground nets even if the
1062 // standard cell power and ground pins are not listed in
1063 // the nets section. Because of this, it is okay to have
1064 // only one node.
1065
1066 if ((net->numnodes == 1) && (net->netnum == VDD_NET ||
1067 net->netnum == GND_NET || net->netnum == ANTENNA_NET))
1068 return net;
1069
1070 if (Verbose > 3) {
1071 Flush(stdout);
1072 Fprintf(stderr, "getnettoroute(): Fell through\n");
1073 }
1074 return NULL;
1075
1076 } /* getnettoroute() */
1077
1078 /*--------------------------------------------------------------*/
1079 /* Find all routes that collide with net "net", remove them */
1080 /* from the Obs[] matrix, append them to the FailedNets list, */
1081 /* and then write the net "net" back to the Obs[] matrix. */
1082 /* */
1083 /* Return the number of nets ripped up */
1084 /*--------------------------------------------------------------*/
1085
ripup_colliding(NET net,u_char onlybreak)1086 static int ripup_colliding(NET net, u_char onlybreak)
1087 {
1088 NETLIST nl, nl2, fn;
1089 int ripped;
1090
1091 // Analyze route for nets with which it collides
1092
1093 nl = find_colliding(net, &ripped);
1094
1095 // "ripLimit" limits the number of collisions so that the
1096 // router avoids ripping up huge numbers of nets, which can
1097 // cause the number of failed nets to keep increasing.
1098
1099 if (ripped > ripLimit) {
1100 while (nl) {
1101 nl2 = nl->next;
1102 free(nl);
1103 nl = nl2;
1104 }
1105 return -1;
1106 }
1107
1108 // Remove the colliding nets from the route grid and append
1109 // them to FailedNets.
1110
1111 ripped = 0;
1112 while(nl) {
1113 ripped++;
1114 nl2 = nl->next;
1115 if (Verbose > 0)
1116 Fprintf(stdout, "Ripping up blocking net %s\n", nl->net->netname);
1117 if (ripup_net(nl->net, TRUE, onlybreak, FALSE) == TRUE) {
1118 for (fn = FailedNets; fn && fn->next != NULL; fn = fn->next);
1119 if (fn)
1120 fn->next = nl;
1121 else
1122 FailedNets = nl;
1123
1124 // Add nl->net to "noripup" list for this net, so it won't be
1125 // routed over again by the net. Avoids infinite looping in
1126 // the second stage.
1127
1128 fn = (NETLIST)malloc(sizeof(struct netlist_));
1129 fn->next = net->noripup;
1130 net->noripup = fn;
1131 fn->net = nl->net;
1132 }
1133
1134 nl->next = (NETLIST)NULL;
1135 nl = nl2;
1136 }
1137 return ripped;
1138 }
1139
1140 /*--------------------------------------------------------------*/
1141 /* Do a second-stage route (rip-up and re-route) of a single */
1142 /* net "net". */
1143 /*--------------------------------------------------------------*/
1144
route_net_ripup(NET net,u_char graphdebug,u_char onlybreak)1145 int route_net_ripup(NET net, u_char graphdebug, u_char onlybreak)
1146 {
1147 int result;
1148 NETLIST nl, nl2;
1149
1150 // Find the net in the Failed list and remove it.
1151 if (FailedNets) {
1152 if (FailedNets->net == net) {
1153 nl2 = FailedNets;
1154 FailedNets = FailedNets->next;
1155 free(nl2);
1156 }
1157 else {
1158 for (nl = FailedNets; nl->next; nl = nl->next) {
1159 if (nl->next->net == net)
1160 break;
1161 }
1162 nl2 = nl->next;
1163 nl->next = nl2->next;
1164 free(nl2);
1165 }
1166 }
1167
1168 result = doroute(net, TRUE, graphdebug);
1169 if (result != 0) {
1170 if (net->noripup != NULL) {
1171 if ((net->flags & NET_PENDING) == 0) {
1172 // Clear this net's "noripup" list and try again.
1173
1174 while (net->noripup) {
1175 nl = net->noripup->next;
1176 free(net->noripup);
1177 net->noripup = nl;
1178 }
1179 result = doroute(net, TRUE, graphdebug);
1180 net->flags |= NET_PENDING; // Next time we abandon it.
1181 }
1182 }
1183 }
1184 if (result != 0)
1185 result = ripup_colliding(net, onlybreak);
1186
1187 return result;
1188 }
1189
1190 /*--------------------------------------------------------------*/
1191 /* dosecondstage() --- */
1192 /* */
1193 /* Second stage: Rip-up and reroute failing nets. */
1194 /* Method: */
1195 /* 1) Route a failing net with stage = 1 (other nets become */
1196 /* costs, not blockages, no copying to Obs) */
1197 /* 2) If net continues to fail, flag it as unroutable and */
1198 /* remove it from the list. */
1199 /* 3) Otherwise, determine the nets with which it collided. */
1200 /* 4) Remove all of the colliding nets, and add them to the */
1201 /* FailedNets list */
1202 /* 5) Route the original failing net. */
1203 /* 6) Continue until all failed nets have been processed. */
1204 /* */
1205 /* Return value: The number of failing nets */
1206 /*--------------------------------------------------------------*/
1207
1208 int
dosecondstage(u_char graphdebug,u_char singlestep,u_char onlybreak,u_int effort)1209 dosecondstage(u_char graphdebug, u_char singlestep, u_char onlybreak, u_int effort)
1210 {
1211 int failcount, result, i;
1212 NET net;
1213 NETLIST nl, nl2;
1214 NETLIST Abandoned; // Abandoned routes---not even trying any more.
1215 ROUTE rt, rt2;
1216 SEG seg;
1217 u_int loceffort = (effort > minEffort) ? effort : minEffort;
1218
1219 fillMask((u_char)0);
1220 Abandoned = NULL;
1221 for (i = 0; i < 3; i++) progress[i] = 0;
1222
1223 // Clear the "noripup" field from all of the failed nets, in case
1224 // the second stage route is being repeated.
1225
1226 for (nl2 = FailedNets; nl2; nl2 = nl2->next) {
1227 net = nl2->net;
1228 while (net->noripup) {
1229 nl = net->noripup->next;
1230 free(net->noripup);
1231 net->noripup = nl;
1232 }
1233 net->flags &= ~NET_PENDING;
1234 }
1235
1236 while (FailedNets != NULL) {
1237
1238 // Diagnostic: how are we doing?
1239 failcount = countlist(FailedNets);
1240 if (Verbose > 1) Fprintf(stdout, "------------------------------\n");
1241 Fprintf(stdout, "Nets remaining: %d\n", failcount);
1242 if (Verbose > 1) Fprintf(stdout, "------------------------------\n");
1243
1244 net = FailedNets->net;
1245
1246 // Remove this net from the fail list
1247 nl2 = FailedNets;
1248 FailedNets = FailedNets->next;
1249 free(nl2);
1250
1251 // Keep track of which routes existed before the call to doroute().
1252 for (rt = net->routes; rt && rt->next; rt = rt->next);
1253
1254 if (Verbose > 2)
1255 Fprintf(stdout, "Routing net %s with collisions\n", net->netname);
1256 Flush(stdout);
1257
1258 result = doroute(net, TRUE, graphdebug);
1259
1260 if (result != 0) {
1261 if (net->noripup != NULL) {
1262 if ((net->flags & NET_PENDING) == 0) {
1263 // Clear this net's "noripup" list and try again.
1264
1265 while (net->noripup) {
1266 nl = net->noripup->next;
1267 free(net->noripup);
1268 net->noripup = nl;
1269 }
1270 result = doroute(net, TRUE, graphdebug);
1271 net->flags |= NET_PENDING; // Next time we abandon it.
1272 }
1273 }
1274 }
1275
1276 if (result == 0) {
1277
1278 // Find nets that collide with "net" and remove them, adding them
1279 // to the end of the FailedNets list.
1280
1281 // If the number of nets to be ripped up exceeds "ripLimit",
1282 // then treat this as a route failure, and don't rip up any of
1283 // the colliding nets.
1284
1285 result = ripup_colliding(net, onlybreak);
1286 if (result > 0) result = 0;
1287 }
1288
1289 if (result != 0) {
1290
1291 // Complete failure to route, even allowing collisions.
1292 // Abandon routing this net.
1293
1294 if (Verbose > 0)
1295 Fprintf(stdout, "Failure on net %s: Abandoning for now.\n",
1296 net->netname);
1297
1298 // Add the net to the "abandoned" list
1299 nl = (NETLIST)malloc(sizeof(struct netlist_));
1300 nl->net = net;
1301 nl->next = Abandoned;
1302 Abandoned = nl;
1303
1304 while (FailedNets && (FailedNets->net == net)) {
1305 nl = FailedNets->next;
1306 free(FailedNets);
1307 FailedNets = nl;
1308 }
1309
1310 // Remove routing information for all new routes that have
1311 // not been copied back into Obs[].
1312 if (rt == NULL) {
1313 rt = net->routes;
1314 net->routes = NULL; // remove defunct pointer
1315 }
1316 else {
1317 rt2 = rt->next;
1318 rt->next = NULL;
1319 rt = rt2;
1320 }
1321 while (rt != NULL) {
1322 rt2 = rt->next;
1323 while (rt->segments) {
1324 seg = rt->segments->next;
1325 free(rt->segments);
1326 rt->segments = seg;
1327 }
1328 free(rt);
1329 rt = rt2;
1330 }
1331
1332 // Remove both routing information and remove the route from
1333 // Obs[] for all parts of the net that were previously routed
1334
1335 ripup_net(net, TRUE, FALSE, FALSE); // Remove routing information from net
1336 continue;
1337 }
1338
1339 // Write back the original route to the grid array
1340 writeback_all_routes(net);
1341
1342 // Evaluate progress by counting the total number of remaining
1343 // routes in the last (effort) cycles. progress[2]->progress[1]
1344 // is a progression from oldest to newest number of remaining
1345 // routes. Calculate the slope of this line and declare an end
1346 // to this 2nd stage route if the slope falls to zero.
1347
1348 progress[1] += failcount;
1349 progress[0]++;
1350 if (progress[0] > loceffort) {
1351 if ((progress[2] > 0) && (progress[2] <= progress[1])) {
1352 Fprintf(stderr, "\nNo progress at level of effort %d;"
1353 " ending 2nd stage.\n", loceffort);
1354 break;
1355 }
1356 progress[2] = progress[1];
1357 progress[1] = progress[0] = 0;
1358 }
1359 if (singlestep && (FailedNets != NULL)) return countlist(FailedNets);
1360 }
1361
1362 // If the list of abandoned nets is non-null, attach it to the
1363 // end of the failed nets list.
1364
1365 if (Abandoned != NULL) {
1366 if (FailedNets == NULL) {
1367 FailedNets = Abandoned;
1368 Abandoned = NULL;
1369 }
1370 else {
1371 for (nl = FailedNets; nl->next; nl = nl->next);
1372 nl->next = Abandoned;
1373 Abandoned = NULL;
1374 }
1375 }
1376
1377 if (Verbose > 0) {
1378 Flush(stdout);
1379 Fprintf(stdout, "\n----------------------------------------------\n");
1380 Fprintf(stdout, "Progress: ");
1381 Fprintf(stdout, "Stage 2 total routes completed: %d\n", TotalRoutes);
1382 }
1383 if (FailedNets == (NETLIST)NULL) {
1384 failcount = 0;
1385 Fprintf(stdout, "No failed routes!\n");
1386 }
1387 else {
1388 failcount = countlist(FailedNets);
1389 if (FailedNets != (NETLIST)NULL)
1390 Fprintf(stdout, "Failed net routes: %d\n", failcount);
1391 }
1392 if (Verbose > 0)
1393 Fprintf(stdout, "----------------------------------------------\n");
1394
1395 return failcount;
1396 }
1397
1398 /*--------------------------------------------------------------*/
1399 /* 3rd stage routing (cleanup). Rip up each net in turn and */
1400 /* reroute it. With all of the crossover costs gone, routes */
1401 /* should be much better than the 1st stage. Any route that */
1402 /* existed before it got ripped up should by definition be */
1403 /* routable. */
1404 /*--------------------------------------------------------------*/
1405
dothirdstage(u_char graphdebug,int debug_netnum,u_int effort)1406 int dothirdstage(u_char graphdebug, int debug_netnum, u_int effort)
1407 {
1408 int i, failcount, remaining, result, maskSave;
1409 u_char failed;
1410 NET net;
1411 ROUTE rt;
1412 NETLIST nl;
1413 u_int loceffort = (effort > minEffort) ? effort : minEffort;
1414
1415 // Now find and route all the nets
1416
1417 for (i = 0; i < 3; i++) progress[i] = 0;
1418 remaining = Numnets;
1419
1420 for (i = (debug_netnum >= 0) ? debug_netnum : 0; i < Numnets; i++) {
1421
1422 net = getnettoroute(i);
1423 failed = remove_from_failed(net);
1424 if ((net != NULL) && (net->netnodes != NULL)) {
1425
1426 // Simple optimization: If every route has four or fewer
1427 // segments, then rerouting is almost certainly a waste of
1428 // time.
1429
1430 if (!failed) {
1431 for (rt = net->routes; rt; rt = rt->next) {
1432 int j;
1433 SEG seg = rt->segments;
1434 for (j = 0; j < 3; j++) {
1435 if (seg->next == NULL) break;
1436 seg = seg->next;
1437 }
1438 if (j == 3) break;
1439 }
1440 if (rt == NULL) {
1441 if (Verbose > 0)
1442 Fprintf(stdout, "Keeping route for net %s\n", net->netname);
1443 remaining--;
1444 continue;
1445 }
1446 }
1447
1448 setBboxCurrent(net);
1449 ripup_net(net, FALSE, FALSE, TRUE); /* retain = TRUE */
1450 // Set aside routes in case of failure.
1451 rt = net->routes;
1452 net->routes = NULL;
1453
1454 // set mask mode to BBOX, if auto
1455 maskSave = maskMode;
1456 if (maskMode == MASK_AUTO) maskMode = MASK_BBOX;
1457 result = doroute(net, FALSE, graphdebug);
1458 maskMode = maskSave;
1459 if (result == 0) {
1460 if (Verbose > 0)
1461 Fprintf(stdout, "Finished routing net %s\n", net->netname);
1462 remaining--;
1463 Fprintf(stdout, "Nets remaining: %d\n", remaining);
1464 Flush(stdout);
1465 remove_routes(rt, FALSE); /* original is no longer needed */
1466 }
1467 else if (!failed) {
1468 if (Verbose > 0)
1469 Fprintf(stdout, "Failed to route net %s; restoring original\n",
1470 net->netname);
1471
1472 ripup_net(net, TRUE, FALSE, TRUE); // Remove routes from Obs array
1473 remove_routes(net->routes, FALSE); /* should be NULL already */
1474 net->routes = rt;
1475 writeback_all_routes(net); /* restore the original */
1476 remaining--;
1477 /* Pull net from FailedNets, since we restored it. */
1478 if (FailedNets && (FailedNets->net == net)) {
1479 nl = FailedNets->next;
1480 free(FailedNets);
1481 FailedNets = nl;
1482 }
1483 }
1484 else {
1485 if (Verbose > 0)
1486 Fprintf(stdout, "Failed to route net %s.\n", net->netname);
1487 }
1488 }
1489 else {
1490 if (net && (Verbose > 0)) {
1491 Fprintf(stdout, "Nothing to do for net %s\n", net->netname);
1492 }
1493 remaining--;
1494 }
1495 if (debug_netnum >= 0) break;
1496
1497 /* Progress analysis (see 2nd stage). Normally, the 3rd */
1498 /* stage is run only after all nets have been successfully */
1499 /* routed. However, there is no guarantee of this, so it */
1500 /* is necessary to anticipate convergence issues. */
1501
1502 progress[1] += failcount;
1503 progress[0]++;
1504 if (progress[0] > loceffort) {
1505 if ((progress[2] > 0) && (progress[2] < progress[1])) {
1506 Fprintf(stderr, "\nNo progress at level of effort %d;"
1507 " ending 3rd stage.\n", loceffort);
1508 break;
1509 }
1510 progress[2] = progress[1];
1511 progress[1] = progress[0] = 0;
1512 }
1513 }
1514 failcount = countlist(FailedNets);
1515 if (debug_netnum >= 0) return failcount;
1516
1517 if (Verbose > 0) {
1518 Flush(stdout);
1519 Fprintf(stdout, "\n----------------------------------------------\n");
1520 Fprintf(stdout, "Progress: ");
1521 Fprintf(stdout, "Stage 3 total routes completed: %d\n", TotalRoutes);
1522 }
1523 if (FailedNets == (NETLIST)NULL)
1524 Fprintf(stdout, "No failed routes!\n");
1525 else {
1526 if (FailedNets != (NETLIST)NULL)
1527 Fprintf(stdout, "Failed net routes: %d\n", failcount);
1528 }
1529 if (Verbose > 0)
1530 Fprintf(stdout, "----------------------------------------------\n");
1531
1532 return failcount;
1533 }
1534
1535 /*--------------------------------------------------------------*/
1536 /* Free memory of an iroute glist and clear the Obs2 */
1537 /* PR_ON_STACK flag for each location in the list. */
1538 /*--------------------------------------------------------------*/
1539
1540 void
free_glist(struct routeinfo_ * iroute)1541 free_glist(struct routeinfo_ *iroute)
1542 {
1543 POINT gpoint;
1544 PROUTE *Pr;
1545 int i;
1546
1547 for (i = 0; i < 6; i++) {
1548 while (iroute->glist[i]) {
1549 gpoint = iroute->glist[i];
1550 iroute->glist[i] = iroute->glist[i]->next;
1551 Pr = &OBS2VAL(gpoint->x1, gpoint->y1, gpoint->layer);
1552 Pr->flags &= ~PR_ON_STACK;
1553 freePOINT(gpoint);
1554 }
1555 }
1556 }
1557
1558 /*--------------------------------------------------------------*/
1559 /* doroute - basic route call */
1560 /* */
1561 /* stage = 0 is normal routing */
1562 /* stage = 1 is the rip-up and reroute stage */
1563 /* */
1564 /* ARGS: two nodes to be connected */
1565 /* RETURNS: 0 on success, -1 on failure */
1566 /* SIDE EFFECTS: */
1567 /* AUTHOR and DATE: steve beccue Fri Aug 8 */
1568 /*--------------------------------------------------------------*/
1569
doroute(NET net,u_char stage,u_char graphdebug)1570 int doroute(NET net, u_char stage, u_char graphdebug)
1571 {
1572 ROUTE rt1, lrt;
1573 NETLIST nlist;
1574 int result, lastlayer, unroutable, i;
1575 struct routeinfo_ iroute;
1576
1577 if (!net) {
1578 Fprintf(stderr, "doroute(): no net to route.\n");
1579 return 0;
1580 }
1581
1582 CurNet = net; // Global, used by 2nd stage
1583
1584 // Fill out route information record
1585 iroute.net = net;
1586 iroute.rt = NULL;
1587 for (i = 0; i < 6; i++)
1588 iroute.glist[i] = NULL;
1589 iroute.nsrc = NULL;
1590 iroute.nsrctap = NULL;
1591 iroute.maxcost = MAXRT;
1592 iroute.do_pwrbus = FALSE;
1593 iroute.pwrbus_src = 0;
1594
1595 lastlayer = -1;
1596
1597 /* Set up Obs2[] matrix for first route */
1598
1599 result = route_setup(&iroute, stage);
1600 unroutable = result - 1;
1601 if (graphdebug) highlight_mask();
1602
1603 // Keep going until we are unable to route to a terminal
1604
1605 while (net && (result > 0)) {
1606
1607 if (graphdebug) highlight_source();
1608 if (graphdebug) highlight_dest();
1609 if (graphdebug)
1610 for (i = 0; i < 6; i++)
1611 highlight_starts(iroute.glist[i]);
1612
1613 rt1 = createemptyroute();
1614 rt1->netnum = net->netnum;
1615 iroute.rt = rt1;
1616
1617 if (Verbose > 3) {
1618 Fprintf(stdout,"doroute(): added net %d path start %d\n",
1619 net->netnum, net->netnodes->nodenum);
1620 }
1621
1622 result = route_segs(&iroute, stage, graphdebug);
1623
1624 if (result < 0) { // Route failure.
1625
1626 // If we failed this on the last round, then stop
1627 // working on this net and move on to the next.
1628 if (FailedNets && (FailedNets->net == net)) break;
1629
1630 nlist = (NETLIST)malloc(sizeof(struct netlist_));
1631 nlist->net = net;
1632 nlist->next = FailedNets;
1633 FailedNets = nlist;
1634 free(rt1);
1635 }
1636 else {
1637
1638 TotalRoutes++;
1639
1640 if (net->routes) {
1641 for (lrt = net->routes; lrt->next; lrt = lrt->next);
1642 lrt->next = rt1;
1643 }
1644 else {
1645 net->routes = rt1;
1646 }
1647 draw_net(net, TRUE, &lastlayer);
1648 }
1649
1650 // For power routing, clear the list of existing pending route
1651 // solutions---they will not be relevant.
1652
1653 if (iroute.do_pwrbus) free_glist(&iroute);
1654
1655 /* Set up for next route and check if routing is done */
1656 result = next_route_setup(&iroute, stage);
1657 }
1658
1659 /* Finished routing (or error occurred) */
1660 free_glist(&iroute);
1661
1662 /* Route failure due to no taps or similar error---Log it */
1663 if ((result < 0) || (unroutable > 0)) {
1664 if ((FailedNets == NULL) || (FailedNets->net != net)) {
1665 nlist = (NETLIST)malloc(sizeof(struct netlist_));
1666 nlist->net = net;
1667 nlist->next = FailedNets;
1668 FailedNets = nlist;
1669 }
1670 }
1671 return (unroutable > 0) ? -1 : result;
1672
1673 } /* doroute() */
1674
1675 /*--------------------------------------------------------------*/
1676 /* Catch-all routine when no tap points are found. This is a */
1677 /* common problem when the technology is not set up correctly */
1678 /* and it's helpful to have all these error conditions pass */
1679 /* to a single subroutine. */
1680 /*--------------------------------------------------------------*/
1681
unable_to_route(char * netname,NODE node,unsigned char forced)1682 static void unable_to_route(char *netname, NODE node, unsigned char forced)
1683 {
1684 if (node)
1685 Fprintf(stderr, "Node %s of net %s has no tap points---",
1686 print_node_name(node), netname);
1687 else
1688 Fprintf(stderr, "Node of net %s has no tap points---",
1689 netname);
1690
1691 if (forced)
1692 Fprintf(stderr, "forcing a tap point.\n");
1693 else
1694 Fprintf(stderr, "unable to route!\n");
1695 }
1696
1697 /*--------------------------------------------------------------*/
1698 /* next_route_setup -- */
1699 /* */
1700 /*--------------------------------------------------------------*/
1701
next_route_setup(struct routeinfo_ * iroute,u_char stage)1702 static int next_route_setup(struct routeinfo_ *iroute, u_char stage)
1703 {
1704 ROUTE rt;
1705 NODE node;
1706 int i, j;
1707 int rval, result;
1708
1709 if (iroute->do_pwrbus == TRUE) {
1710
1711 iroute->pwrbus_src++;
1712 iroute->nsrc = iroute->nsrc->next;
1713 rval = -2;
1714 while (rval == -2) {
1715 if ((iroute->pwrbus_src > iroute->net->numnodes) || (iroute->nsrc == NULL)) {
1716 result = 0;
1717 break;
1718 }
1719 else {
1720 result = set_powerbus_to_net(iroute->nsrc->netnum);
1721 clear_target_node(iroute->nsrc);
1722 rval = set_node_to_net(iroute->nsrc, PR_SOURCE,
1723 &iroute->glist[0], &iroute->bbox, stage);
1724 if (rval == -2) {
1725 if (forceRoutable) {
1726 make_routable(iroute->nsrc);
1727 }
1728 else {
1729 iroute->pwrbus_src++;
1730 iroute->nsrc = iroute->nsrc->next;
1731 }
1732 unable_to_route(iroute->net->netname, iroute->nsrc, forceRoutable);
1733 }
1734 else if (rval < 0) return -1;
1735 }
1736 }
1737 }
1738 else {
1739
1740 for (rt = iroute->net->routes; (rt && rt->next); rt = rt->next);
1741
1742 // Set positions on last route to PR_SOURCE
1743 if (rt) {
1744 result = set_route_to_net(iroute->net, rt, PR_SOURCE,
1745 &iroute->glist[0], &iroute->bbox, stage);
1746
1747 if (result == -2) {
1748 unable_to_route(iroute->net->netname, NULL, 0);
1749 return -1;
1750 }
1751 }
1752 else return -1;
1753
1754 result = (count_targets(iroute->net) == 0) ? 0 : 1;
1755 }
1756
1757 // Check for the possibility that there is already a route to the target
1758
1759 if (!result) {
1760
1761 // Remove nodes of the net from Nodeinfo.nodeloc so that they will not be
1762 // used for crossover costing of future routes.
1763 remove_tap_blocks(iroute->net->netnum);
1764 free_glist(iroute);
1765 return 0;
1766 }
1767
1768 if (!iroute->do_pwrbus) {
1769
1770 // If any target is found during the search, but is not the
1771 // target that is chosen for the minimum-cost path, then it
1772 // will be left marked "processed" and never visited again.
1773 // Make sure this doesn't happen by clearing the "processed"
1774 // flag from all such target nodes, and placing the positions
1775 // on the stack for processing again.
1776
1777 clear_non_source_targets(iroute->net, &iroute->glist[0]);
1778 }
1779
1780 if (Verbose > 1) {
1781 Fprintf(stdout, "netname = %s, route number %d\n",
1782 iroute->net->netname, TotalRoutes );
1783 Flush(stdout);
1784 }
1785
1786 if (iroute->maxcost > 2)
1787 iroute->maxcost >>= 1; // Halve the maximum cost from the last run
1788
1789 return 1; // Successful setup
1790 }
1791
1792 /*--------------------------------------------------------------*/
1793 /* route_setup -- */
1794 /* */
1795 /*--------------------------------------------------------------*/
1796
route_setup(struct routeinfo_ * iroute,u_char stage)1797 static int route_setup(struct routeinfo_ *iroute, u_char stage)
1798 {
1799 int i, j;
1800 u_int netnum, dir;
1801 int result, rval, unroutable;
1802 NODE node;
1803 NODEINFO lnode;
1804 PROUTE *Pr;
1805
1806 // Make Obs2[][] a copy of Obs[][]. Convert pin obstructions to
1807 // terminal positions for the net being routed.
1808
1809 for (i = 0; i < Num_layers; i++) {
1810 for (j = 0; j < NumChannelsX * NumChannelsY; j++) {
1811 netnum = Obs[i][j] & (~BLOCKED_MASK);
1812 Pr = &Obs2[i][j];
1813 if (netnum != 0) {
1814 Pr->flags = 0; // Clear all flags
1815 if ((netnum & DRC_BLOCKAGE) == DRC_BLOCKAGE)
1816 Pr->prdata.net = DRC_BLOCKAGE;
1817 else
1818 Pr->prdata.net = netnum & NETNUM_MASK;
1819 } else {
1820 Pr->flags = PR_COST; // This location is routable
1821 Pr->prdata.cost = MAXRT;
1822 }
1823 }
1824 }
1825
1826 if (iroute->net->netnum == VDD_NET || iroute->net->netnum == GND_NET ||
1827 iroute->net->netnum == ANTENNA_NET) {
1828 // The normal method of selecting source and target is not amenable
1829 // to power bus routes. Instead, we use the global standard cell
1830 // power rails as the target, and each net in sequence becomes the
1831 // sole source node
1832
1833 iroute->do_pwrbus = TRUE;
1834 iroute->nsrc = find_unrouted_node(iroute->net);
1835 result = (iroute->nsrc == NULL) ? 0 : 1;
1836 }
1837 else {
1838 iroute->do_pwrbus = FALSE;
1839 if (iroute->net->netnodes != NULL)
1840 iroute->nsrc = iroute->net->netnodes;
1841 else {
1842 Fprintf(stderr, "Net %s has no nodes, unable to route!\n",
1843 iroute->net->netname);
1844 return -1;
1845 }
1846 result = 1;
1847 }
1848
1849 // We start at the node referenced by the route structure, and flag all
1850 // of its taps as PR_SOURCE, as well as all connected routes.
1851
1852 unroutable = 0;
1853
1854 if (result) {
1855 iroute->bbox.x2 = iroute->bbox.y2 = 0;
1856 iroute->bbox.x1 = NumChannelsX;
1857 iroute->bbox.y1 = NumChannelsY;
1858
1859 if (iroute->do_pwrbus == FALSE) {
1860
1861 // Set node to PR_SOURCE
1862 rval = set_node_to_net(iroute->nsrc, PR_SOURCE,
1863 &iroute->glist[0], &iroute->bbox, stage);
1864
1865 if (rval == -2) {
1866 unable_to_route(iroute->net->netname, NULL, 0);
1867 return -1;
1868 }
1869
1870 // Set associated routes to PR_SOURCE (okay to fail)
1871 rval = set_routes_to_net(iroute->nsrc, iroute->net, PR_SOURCE,
1872 &iroute->glist[0], &iroute->bbox, stage);
1873
1874 // Now search for all other nodes on the same net that have not
1875 // yet been routed, and flag all of their taps as PR_TARGET
1876
1877 result = 0;
1878 for (node = iroute->net->netnodes; node; node = node->next) {
1879 if (node == iroute->nsrc) continue;
1880 rval = set_node_to_net(node, PR_TARGET, NULL, &iroute->bbox, stage);
1881 if (rval == 0) {
1882 result = 1;
1883 }
1884 else if (rval == -2) {
1885 if (forceRoutable) make_routable(node);
1886 unable_to_route(iroute->net->netname, node, forceRoutable);
1887 if (result == 0) result = -1;
1888 unroutable++;
1889 break;
1890 }
1891 else if (rval == 1) continue; /* This node was part of source */
1892
1893 // And add associated routes
1894 rval = set_routes_to_net(node, iroute->net, PR_TARGET, NULL,
1895 &iroute->bbox, stage);
1896 if (rval == 0) result = 1; /* (okay to fail) */
1897 }
1898
1899 /* If there's only one node and it's not routable, then fail. */
1900 if (result == -1) return -1;
1901 }
1902 else { /* Do this for power bus connections */
1903
1904 while(1) {
1905 rval = set_node_to_net(iroute->nsrc, PR_SOURCE,
1906 &iroute->glist[0], &iroute->bbox, stage);
1907 if (rval == -2) {
1908 iroute->nsrc = iroute->nsrc->next;
1909 if (iroute->nsrc == NULL) break;
1910 }
1911 else break;
1912 }
1913 if (rval == -2) {
1914 if (forceRoutable) make_routable(iroute->net->netnodes);
1915 unable_to_route(iroute->net->netname, iroute->nsrc, forceRoutable);
1916 return -1;
1917 }
1918
1919 /* Set all nodes that are NOT nsrc to an unused net number */
1920 for (node = iroute->net->netnodes; node; node = node->next) {
1921 if (node != iroute->nsrc) {
1922 disable_node_nets(node);
1923 }
1924 }
1925 set_powerbus_to_net(iroute->nsrc->netnum);
1926 }
1927 }
1928
1929 if (!result) {
1930 // Remove nodes of the net from Nodeinfo.nodeloc so that they will not be
1931 // used for crossover costing of future routes.
1932 remove_tap_blocks(iroute->net->netnum);
1933 free_glist(iroute);
1934 return 0;
1935 }
1936
1937 // Generate a search area mask representing the "likely best route".
1938 if ((iroute->do_pwrbus == FALSE) && (maskMode == MASK_AUTO)) {
1939 if (stage == 0)
1940 createMask(iroute->net, MASK_SMALL, (u_char)Numpasses);
1941 else
1942 createMask(iroute->net, MASK_LARGE, (u_char)Numpasses);
1943 }
1944 else if ((iroute->do_pwrbus == TRUE) || (maskMode == MASK_NONE))
1945 fillMask((u_char)0);
1946 else if (maskMode == MASK_BBOX)
1947 createBboxMask(iroute->net, (u_char)Numpasses);
1948 else
1949 createMask(iroute->net, maskMode, (u_char)Numpasses);
1950
1951 // Heuristic: Set the initial cost beyond which we stop searching.
1952 // This value is twice the cost of a direct route across the
1953 // maximum extent of the source to target, divided by the square
1954 // root of the number of nodes in the net. We purposely set this
1955 // value low. It has a severe impact on the total run time of the
1956 // algorithm. If the initial max cost is so low that no route can
1957 // be found, it will be doubled on each pass.
1958
1959 if (iroute->do_pwrbus)
1960 iroute->maxcost = 20; // Maybe make this SegCost * row height?
1961 else {
1962 iroute->maxcost = 1 + 2 * MAX((iroute->bbox.x2 - iroute->bbox.x1),
1963 (iroute->bbox.y2 - iroute->bbox.y1))
1964 * SegCost + (int)stage * ConflictCost;
1965 iroute->maxcost /= (iroute->nsrc->numnodes - 1);
1966 }
1967
1968 netnum = iroute->net->netnum;
1969
1970 iroute->nsrctap = iroute->nsrc->taps;
1971 if (iroute->nsrctap == NULL) iroute->nsrctap = iroute->nsrc->extend;
1972 if (iroute->nsrctap == NULL) {
1973 unable_to_route(iroute->net->netname, iroute->nsrc, 0);
1974 return -1;
1975 }
1976
1977 if (Verbose > 2) {
1978 Fprintf(stdout, "Source node @ %gum %gum layer=%d grid=(%d %d)\n",
1979 iroute->nsrctap->x, iroute->nsrctap->y, iroute->nsrctap->layer,
1980 iroute->nsrctap->gridx, iroute->nsrctap->gridy);
1981 }
1982
1983 if (Verbose > 1) {
1984 Fprintf(stdout, "netname = %s, route number %d\n", iroute->net->netname,
1985 TotalRoutes );
1986 Flush(stdout);
1987 }
1988
1989 // Successful setup, although if nodes were marked unroutable,
1990 // this information is passed back; routing will proceed for
1991 // all routable nodes and the net will be then marked as
1992 // abandoned.
1993
1994 return (unroutable + 1);
1995 }
1996
1997 /*--------------------------------------------------------------*/
1998 /* route_segs - detailed route from node to node using onestep */
1999 /* method */
2000 /* */
2001 /* ARGS: ROUTE, ready to add segments to do route */
2002 /* RETURNS: NULL if failed, manhattan distance if success */
2003 /* SIDE EFFECTS: */
2004 /* AUTHOR and DATE: steve beccue Fri Aug 8 */
2005 /*--------------------------------------------------------------*/
2006
route_segs(struct routeinfo_ * iroute,u_char stage,u_char graphdebug)2007 int route_segs(struct routeinfo_ *iroute, u_char stage, u_char graphdebug)
2008 {
2009 POINT gpoint, gunproc, newpt;
2010 int i, o;
2011 int pass, maskpass;
2012 u_int forbid;
2013 GRIDP best, curpt;
2014 int rval;
2015 u_char first = TRUE;
2016 u_char check_order[6];
2017 u_char max_reached;
2018 u_char conflict;
2019 u_char predecessor;
2020 PROUTE *Pr;
2021
2022 best.cost = MAXRT;
2023 best.x = 0;
2024 best.y = 0;
2025 best.lay = 0;
2026 gunproc = (POINT)NULL;
2027 maskpass = 0;
2028
2029 for (pass = 0; pass < Numpasses; pass++) {
2030
2031 max_reached = FALSE;
2032 if (!first && (Verbose > 2)) {
2033 Fprintf(stdout, "\n");
2034 first = TRUE;
2035 }
2036 if (Verbose > 2) {
2037 Fprintf(stdout, "Pass %d", pass + 1);
2038 Fprintf(stdout, " (maxcost is %d)\n", iroute->maxcost);
2039 }
2040
2041 while (TRUE) {
2042
2043 // Check priority stack and move down if 1st priorty is empty
2044 while (iroute->glist[0] == NULL) {
2045 for (i = 0; i < 5; i++)
2046 iroute->glist[i] = iroute->glist[i + 1];
2047 iroute->glist[5] = NULL;
2048 if ((iroute->glist[0] == NULL) && (iroute->glist[1] == NULL) &&
2049 (iroute->glist[2] == NULL) && (iroute->glist[3] == NULL) &&
2050 (iroute->glist[4] == NULL))
2051 break;
2052 }
2053 gpoint = iroute->glist[0];
2054 if (gpoint == NULL) break;
2055
2056 iroute->glist[0] = gpoint->next;
2057
2058 // Stop-gap: Needs to be investigated. Occasional gpoint has
2059 // large (random?) value for y1. Suggests a memory leak. Only
2060 // seen occurring during doantennaroute(). Check using valgrind.
2061
2062 if ((gpoint->x1 < 0) || (gpoint->y1 < 0) ||
2063 (gpoint->x1 > NumChannelsX) ||
2064 (gpoint->y1 > NumChannelsY)) {
2065 Fprintf(stderr, "Internal memory error!\n");
2066 freePOINT(gpoint);
2067 continue;
2068 }
2069
2070 curpt.x = gpoint->x1;
2071 curpt.y = gpoint->y1;
2072 curpt.lay = gpoint->layer;
2073
2074 if (graphdebug) highlight(curpt.x, curpt.y);
2075
2076 Pr = &OBS2VAL(curpt.x, curpt.y, curpt.lay);
2077
2078 // ignore grid positions that have already been processed
2079 if (Pr->flags & PR_PROCESSED) {
2080 Pr->flags &= ~PR_ON_STACK;
2081 freePOINT(gpoint);
2082 continue;
2083 }
2084
2085 if (Pr->flags & PR_COST)
2086 curpt.cost = Pr->prdata.cost; // Route points, including target
2087 else
2088 curpt.cost = 0; // For source tap points
2089
2090 // if the grid position is the destination, save the position and
2091 // cost if minimum.
2092
2093 if (Pr->flags & PR_TARGET) {
2094
2095 if (curpt.cost < best.cost) {
2096 if (first) {
2097 if (Verbose > 2)
2098 Fprintf(stdout, "Found a route of cost ");
2099 first = FALSE;
2100 }
2101 else if (Verbose > 2) {
2102 Fprintf(stdout, "|");
2103 Fprintf(stdout, "%d", curpt.cost);
2104 Flush(stdout);
2105 }
2106
2107 // This position may be on a route, not at a terminal, so
2108 // record it.
2109 best.x = curpt.x;
2110 best.y = curpt.y;
2111 best.lay = curpt.lay;
2112 best.cost = curpt.cost;
2113
2114 // If a complete route has been found, then there's no point
2115 // in searching paths with a greater cost than this one.
2116 if (best.cost < iroute->maxcost) iroute->maxcost = best.cost;
2117 }
2118
2119 // Don't continue processing from the target
2120 Pr->flags |= PR_PROCESSED;
2121 Pr->flags &= ~PR_ON_STACK;
2122 freePOINT(gpoint);
2123 continue;
2124 }
2125
2126 if (curpt.cost < MAXRT) {
2127
2128 // Severely limit the search space by not processing anything that
2129 // is not under the current route mask, which identifies a narrow
2130 // "best route" solution.
2131
2132 if (RMASK(curpt.x, curpt.y) > (u_char)maskpass) {
2133 gpoint->next = gunproc;
2134 gunproc = gpoint;
2135 continue;
2136 }
2137
2138 // Quick check: Limit maximum cost to limit search space
2139 // Move the point onto the "unprocessed" stack and we'll pick up
2140 // from this point on the next pass, if needed.
2141
2142 if (curpt.cost > iroute->maxcost) {
2143 max_reached = TRUE;
2144 gpoint->next = gunproc;
2145 gunproc = gpoint;
2146 continue;
2147 }
2148 }
2149 Pr->flags &= ~PR_ON_STACK;
2150 freePOINT(gpoint);
2151
2152 // check east/west/north/south, and bottom to top
2153
2154 // 1st optimization: Direction of route on current layer is preferred.
2155 o = LefGetRouteOrientation(curpt.lay);
2156 forbid = OBSVAL(curpt.x, curpt.y, curpt.lay) & BLOCKED_MASK;
2157
2158 // To reach otherwise unreachable taps, allow searching on blocked
2159 // paths but with a high cost.
2160 conflict = (forceRoutable) ? PR_CONFLICT : PR_NO_EVAL;
2161
2162 if (o == 1) { // horizontal routes---check EAST and WEST first
2163 check_order[0] = EAST | ((forbid & BLOCKED_E) ? conflict : 0);
2164 check_order[1] = WEST | ((forbid & BLOCKED_W) ? conflict : 0);
2165 check_order[2] = UP | ((forbid & BLOCKED_U) ? conflict : 0);
2166 check_order[3] = DOWN | ((forbid & BLOCKED_D) ? conflict : 0);
2167 check_order[4] = NORTH | ((forbid & BLOCKED_N) ? conflict : 0);
2168 check_order[5] = SOUTH | ((forbid & BLOCKED_S) ? conflict : 0);
2169 }
2170 else { // vertical routes---check NORTH and SOUTH first
2171 check_order[0] = NORTH | ((forbid & BLOCKED_N) ? conflict : 0);
2172 check_order[1] = SOUTH | ((forbid & BLOCKED_S) ? conflict : 0);
2173 check_order[2] = UP | ((forbid & BLOCKED_U) ? conflict : 0);
2174 check_order[3] = DOWN | ((forbid & BLOCKED_D) ? conflict : 0);
2175 check_order[4] = EAST | ((forbid & BLOCKED_E) ? conflict : 0);
2176 check_order[5] = WEST | ((forbid & BLOCKED_W) ? conflict : 0);
2177 }
2178
2179 // Check order is from 0 (1st priority) to 5 (last priority). However, this
2180 // is a stack system, so the last one placed on the stack is the first to be
2181 // pulled and processed. Therefore we evaluate and drop positions to check
2182 // on the stack in reverse order (5 to 0).
2183
2184 for (i = 5; i >= 0; i--) {
2185 predecessor = 0;
2186 switch (check_order[i]) {
2187 case EAST | PR_CONFLICT:
2188 predecessor = PR_CONFLICT;
2189 case EAST:
2190 predecessor |= PR_PRED_W;
2191 if ((curpt.x + 1) < NumChannelsX) {
2192 if ((gpoint = eval_pt(&curpt, predecessor, stage)) != NULL) {
2193 gpoint->next = iroute->glist[i];
2194 iroute->glist[i] = gpoint;
2195 }
2196 }
2197 break;
2198
2199 case WEST | PR_CONFLICT:
2200 predecessor = PR_CONFLICT;
2201 case WEST:
2202 predecessor |= PR_PRED_E;
2203 if ((curpt.x - 1) >= 0) {
2204 if ((gpoint = eval_pt(&curpt, predecessor, stage)) != NULL) {
2205 gpoint->next = iroute->glist[i];
2206 iroute->glist[i] = gpoint;
2207 }
2208 }
2209 break;
2210
2211 case SOUTH | PR_CONFLICT:
2212 predecessor = PR_CONFLICT;
2213 case SOUTH:
2214 predecessor |= PR_PRED_N;
2215 if ((curpt.y - 1) >= 0) {
2216 if ((gpoint = eval_pt(&curpt, predecessor, stage)) != NULL) {
2217 gpoint->next = iroute->glist[i];
2218 iroute->glist[i] = gpoint;
2219 }
2220 }
2221 break;
2222
2223 case NORTH | PR_CONFLICT:
2224 predecessor = PR_CONFLICT;
2225 case NORTH:
2226 predecessor |= PR_PRED_S;
2227 if ((curpt.y + 1) < NumChannelsY) {
2228 if ((gpoint = eval_pt(&curpt, predecessor, stage)) != NULL) {
2229 gpoint->next = iroute->glist[i];
2230 iroute->glist[i] = gpoint;
2231 }
2232 }
2233 break;
2234
2235 case DOWN | PR_CONFLICT:
2236 predecessor = PR_CONFLICT;
2237 case DOWN:
2238 predecessor |= PR_PRED_U;
2239 if (curpt.lay > 0) {
2240 if ((gpoint = eval_pt(&curpt, predecessor, stage)) != NULL) {
2241 gpoint->next = iroute->glist[i];
2242 iroute->glist[i] = gpoint;
2243 }
2244 }
2245 break;
2246
2247 case UP | PR_CONFLICT:
2248 predecessor = PR_CONFLICT;
2249 case UP:
2250 predecessor |= PR_PRED_D;
2251 if (curpt.lay < (Num_layers - 1)) {
2252 if ((gpoint = eval_pt(&curpt, predecessor, stage)) != NULL) {
2253 gpoint->next = iroute->glist[i];
2254 iroute->glist[i] = gpoint;
2255 }
2256 }
2257 break;
2258 }
2259 }
2260
2261 // Mark this node as processed
2262 Pr->flags |= PR_PROCESSED;
2263
2264 } // while stack is not empty
2265
2266 free_glist(iroute);
2267
2268 // If we found a route, save it and return
2269
2270 if (best.cost <= iroute->maxcost) {
2271 curpt.x = best.x;
2272 curpt.y = best.y;
2273 curpt.lay = best.lay;
2274 if ((rval = commit_proute(iroute->rt, &curpt, stage)) != 1) break;
2275 if (Verbose > 2) {
2276 Fprintf(stdout, "\nCommit to a route of cost %d\n", best.cost);
2277 Fprintf(stdout, "Between positions (%d %d) and (%d %d)\n",
2278 best.x, best.y, curpt.x, curpt.y);
2279 }
2280 route_set_connections(iroute->net, iroute->rt);
2281 goto done; /* route success */
2282 }
2283
2284 // Continue loop to next pass if any positions were ignored due to
2285 // masking or due to exceeding maxcost.
2286
2287 // If the cost of the route exceeded maxcost at one or more locations,
2288 // then increase maximum cost for next pass.
2289
2290 if (max_reached == TRUE) {
2291 iroute->maxcost <<= 1;
2292 // Cost overflow; we're probably completely hosed long before this.
2293 if (iroute->maxcost > MAXRT) break;
2294 }
2295 else
2296 maskpass++; // Increase the mask size
2297
2298 if (gunproc == NULL) break; // route failure not due to limiting
2299 // search to maxcost or to masking
2300
2301 // Regenerate the stack of unprocessed nodes
2302 iroute->glist[0] = gunproc;
2303 gunproc = NULL;
2304
2305 } // pass
2306
2307 if (!first && (Verbose > 2)) {
2308 Fprintf(stdout, "\n");
2309 Flush(stdout);
2310 }
2311 if (Verbose > 1) {
2312 Fprintf(stderr, "Fell through %d passes\n", pass);
2313 }
2314 if (!iroute->do_pwrbus && (Verbose > 2)) {
2315 Fprintf(stderr, "(%g,%g) net=%s\n",
2316 iroute->nsrctap->x, iroute->nsrctap->y, iroute->net->netname);
2317 }
2318 rval = -1;
2319
2320 done:
2321
2322 // Regenerate the stack of unprocessed nodes
2323 if (gunproc != NULL) iroute->glist[0] = gunproc;
2324 return rval;
2325
2326 } /* route_segs() */
2327
2328 /*--------------------------------------------------------------*/
2329 /* createemptyroute - begin a ROUTE structure */
2330 /* */
2331 /* ARGS: a nodes */
2332 /* RETURNS: ROUTE calloc'd and ready to begin */
2333 /* SIDE EFFECTS: */
2334 /* AUTHOR and DATE: steve beccue Fri Aug 8 */
2335 /*--------------------------------------------------------------*/
2336
createemptyroute(void)2337 ROUTE createemptyroute(void)
2338 {
2339 ROUTE rt;
2340
2341 rt = (ROUTE)calloc(1, sizeof(struct route_));
2342 rt->netnum = 0;
2343 rt->segments = (SEG)NULL;
2344 rt->flags = (u_char)0;
2345 rt->next = (ROUTE)NULL;
2346 rt->start.route = (ROUTE)NULL;
2347 rt->end.route = (ROUTE)NULL;
2348 return rt;
2349
2350 } /* createemptyroute(void) */
2351
2352 /*--------------------------------------------------------------*/
2353 /* helpmessage - tell user how to use the program */
2354 /* */
2355 /* ARGS: none. */
2356 /* RETURNS: nothing. */
2357 /* SIDE EFFECTS: */
2358 /* */
2359 /* NOTES: */
2360 /* 1) "qrouter -v0 -h" prints only the version number and exits */
2361 /* 2) Tcl-Tk based version adds ".T" to the end to alert tools */
2362 /* attempting to query the capabilities of qrouter of the */
2363 /* availability of the scripting. */
2364 /* */
2365 /*--------------------------------------------------------------*/
2366
helpmessage(void)2367 static void helpmessage(void)
2368 {
2369 if (Verbose > 0) {
2370 Fprintf(stdout, "qrouter - maze router by Tim Edwards\n\n");
2371 Fprintf(stdout, "usage: qrouter [-switches] design_name\n\n");
2372 Fprintf(stdout, "switches:\n");
2373 Fprintf(stdout, "\t-c <file>\t\t\tConfiguration file name if not route.cfg.\n");
2374 Fprintf(stdout, "\t-d <file>\t\t\tGenerate delay information output.\n");
2375 Fprintf(stdout, "\t-v <level>\t\t\tVerbose output level.\n");
2376 Fprintf(stdout, "\t-i <file>\t\t\tPrint route names and pitches and exit.\n");
2377 Fprintf(stdout, "\t-p <name>\t\t\tSpecify global power bus name.\n");
2378 Fprintf(stdout, "\t-g <name>\t\t\tSpecify global ground bus name.\n");
2379 Fprintf(stdout, "\t-r <value>\t\t\tForce output resolution scale.\n");
2380 Fprintf(stdout, "\t-f \t\t\tForce all pins to be routable.\n");
2381 Fprintf(stdout, "\t-e <level>\t\t\tLevel of effort to keep trying.\n");
2382 Fprintf(stdout, "\n");
2383 }
2384 #ifdef TCL_QROUTER
2385 Fprintf(stdout, "%s.%s.T\n", VERSION, REVISION);
2386 #else
2387 Fprintf(stdout, "%s.%s\n", VERSION, REVISION);
2388 #endif
2389
2390 } /* helpmessage() */
2391
2392 /* end of qrouter.c */
2393