1 /*
2 * grouteCross.c -
3 *
4 * Global signal router. Code to do crossing placement.
5 *
6 * *********************************************************************
7 * * Copyright (C) 1985, 1990 Regents of the University of California. *
8 * * Permission to use, copy, modify, and distribute this *
9 * * software and its documentation for any purpose and without *
10 * * fee is hereby granted, provided that the above copyright *
11 * * notice appear in all copies. The University of California *
12 * * makes no representations about the suitability of this *
13 * * software for any purpose. It is provided "as is" without *
14 * * express or implied warranty. Export of this software outside *
15 * * of the United States of America may require an export license. *
16 * *********************************************************************
17 * Lawrence Livermore National Laboratory
18 */
19
20 #ifndef lint
21 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/grouter/grouteCrss.c,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $";
22 #endif /* not lint */
23
24 #include <stdio.h>
25 #include <string.h>
26
27 #include "utils/magic.h"
28 #include "utils/geometry.h"
29 #include "utils/geofast.h"
30 #include "utils/hash.h"
31 #include "utils/heap.h"
32 #include "utils/malloc.h"
33 #include "debug/debug.h"
34 #include "tiles/tile.h"
35 #include "database/database.h"
36 #include "gcr/gcr.h"
37 #include "windows/windows.h"
38 #include "utils/main.h"
39 #include "dbwind/dbwind.h"
40 #include "utils/signals.h"
41 #include "router/router.h"
42 #include "grouter/grouter.h"
43 #include "utils/netlist.h"
44 #include "textio/textio.h"
45 #include "utils/styles.h"
46
47 /* Passed to glCrossChoose() */
48 GlPoint *glCrossLookAhead;
49
50 /* The following penalties get scaled by RtrGridSpacing */
51 int glJogPenalty = 5;
52 int glObsPenalty1 = 5, glObsPenalty2 = 3;
53 int glNbrPenalty1 = 2, glNbrPenalty2 = 5;
54 int glOrphanPenalty = 3;
55 int glChanPenalty = 1;
56 bool glPenaltiesScaled = FALSE;
57
58 /* Forward declarations */
59 GlPoint *glCrossAdjust();
60 int glCrossChoose();
61 void glCrossTakePin();
62
63
64 /*
65 * ----------------------------------------------------------------------------
66 *
67 * glCrossMark --
68 *
69 * Mark all the pins crossed by the linked list of GlPoints pointed to
70 * by 'path' as taken. This list is linked along the gl_path pointers.
71 * The starting entry 'path' indicates a pin reserved for a NLTermLoc;
72 * the last entry is one of the pins on the previous starting-point list.
73 *
74 * Results:
75 * None.
76 *
77 * Side effects:
78 * Marks the pins along the path as taken by 'net'.
79 * Assigns a segment identifier to each pin that is different
80 * for each pair of GlPoints in the path.
81 * Increments pNetId->netid_seg once for each new segment identifier
82 * created.
83 * Updates the density information in each channel as the pins are
84 * marked as taken.
85 *
86 * ----------------------------------------------------------------------------
87 */
88
89 void
glCrossMark(rootUse,path,pNetId)90 glCrossMark(rootUse, path, pNetId)
91 CellUse *rootUse; /* For error feedback if non-NULL */
92 GlPoint *path; /* Path linked via gl_path pointers */
93 NetId *pNetId; /* Net and segment identifier; netid_seg is updated */
94 {
95 GCRPin *srcPin, *dstPin;
96 GlPoint *rp;
97 bool srcTaken;
98 NetId markNetId;
99
100 /*
101 * Walk from path back along gl_path pointers down the list.
102 * At each step, process the segment between srcPin and
103 * dstPin in the channel srcPin->gcr_ch.
104 */
105 for (rp = path; rp->gl_path; rp = rp->gl_path)
106 {
107 /*
108 * Increment the segment id once for each channel the net passes
109 * through. The intent is to make this net appear different to
110 * the channel router for each global segment processed.
111 */
112 pNetId->netid_seg++;
113 glCrossingsUsed++;
114
115 /*
116 * Figure out which segment number to use:
117 * If srcPin has already been assigned a net, use its segment id
118 * to mark dstPin and don't do anything to srcPin; otherwise,
119 * use pNetId->netid_seg as the segment identifier and mark
120 * both pins as taken.
121 */
122 markNetId = *pNetId;
123 srcPin = rp->gl_path->gl_pin;
124 srcTaken = srcPin->gcr_pId && srcPin->gcr_pSeg != GCR_STEMSEGID;
125 if (srcTaken)
126 markNetId.netid_seg = srcPin->gcr_pSeg;
127
128 /* Pick the dest pin in the same channel as srcPin */
129 dstPin = rp->gl_pin;
130 if (dstPin->gcr_ch != srcPin->gcr_ch) dstPin = dstPin->gcr_linked;
131 ASSERT(dstPin&&dstPin->gcr_ch == srcPin->gcr_ch, "glCrossMark");
132
133 /* Adjust the density -- must happen before pins are marked! */
134 if (glDensAdjust(((GlobChan *) srcPin->gcr_ch->gcr_client)->gc_postDens,
135 srcPin, dstPin, markNetId))
136 glChanBlockDens(srcPin->gcr_ch);
137
138 /* Mark pins as taken */
139 if (!srcTaken)
140 glCrossTakePin(rootUse, srcPin, markNetId);
141 glCrossTakePin(rootUse, dstPin, markNetId);
142 }
143 }
144
145 /*
146 * ----------------------------------------------------------------------------
147 *
148 * glCrossTakePin --
149 *
150 * Reserve a channel's pin for the given net.
151 * Make a number of sanity checks.
152 *
153 * Results:
154 * None.
155 *
156 * Side effects:
157 * Marks the pin as being taken by the net, by setting
158 * gcr_pId and gcr_pSeg.
159 *
160 * ----------------------------------------------------------------------------
161 */
162
163 void
glCrossTakePin(rootUse,pin,netid)164 glCrossTakePin(rootUse, pin, netid)
165 CellUse *rootUse; /* For error feedback if non-NULL */
166 GCRPin *pin; /* Pin to take */
167 NetId netid; /* Identifier to assign */
168 {
169 char c[256], name1[1024], name2[1024];
170 Rect r;
171
172 if (DebugIsSet(glDebugID, glDebGreedy))
173 return;
174
175 if (DebugIsSet(glDebugID, glDebCross))
176 {
177 glShowCross(pin, netid, CROSS_PERM);
178 TxMore("-- crossing --");
179 }
180
181 r.r_ll = r.r_ur = pin->gcr_point; r.r_xtop++; r.r_ytop++;
182 ASSERT(netid.netid_net != (NLNet *) NULL, "glCrossTakePin");
183
184 if (pin->gcr_pId == (GCRNet *) NULL
185 || (pin->gcr_pId == (GCRNet *) netid.netid_net
186 && pin->gcr_pSeg == GCR_STEMSEGID))
187 {
188 pin->gcr_pId = (GCRNet *) netid.netid_net;
189 pin->gcr_pSeg = netid.netid_seg;
190
191 /* Unlink from list along channel side */
192 if (pin->gcr_pPrev && (pin->gcr_pPrev->gcr_pNext = pin->gcr_pNext))
193 pin->gcr_pNext->gcr_pPrev = pin->gcr_pPrev;
194 }
195 else if (pin->gcr_pId == (GCRNet *) netid.netid_net
196 && pin->gcr_pSeg == netid.netid_seg)
197 {
198 (void) sprintf(c, "Warning: crossing reassigned to same net/seg");
199 if (rootUse)
200 DBWFeedbackAdd(&r, c, rootUse->cu_def, 1, STYLE_PALEHIGHLIGHTS);
201 else TxError("%s\n", c);
202 }
203 else
204 {
205 /* Shouldn't happen: indicates a bug elsewhere */
206 (void) strcpy(name1, NLNetName(pin->gcr_pId));
207 (void) strcpy(name2, NLNetName(netid.netid_net));
208 (void) sprintf(c, "Crossing multiply used, nets %s/%d, %s/%d",
209 name1, pin->gcr_pSeg, name2, netid.netid_seg);
210 if (rootUse)
211 DBWFeedbackAdd(&r, c, rootUse->cu_def, 1, STYLE_PALEHIGHLIGHTS);
212 else TxError("%s\n", c);
213 }
214 }
215
216 /*
217 * ----------------------------------------------------------------------------
218 *
219 * glCrossUnreserve --
220 *
221 * Visit all of the pins used by the stems of the NLNet 'net' and reset
222 * the gcr_pId and gcr_pSeg fields to show a NULL net and no segment id.
223 * This procedure is called only just prior to the global routing for each
224 * net; it keeps the crossings that might be used by this net reserved up
225 * until the last possible minute, but makes sure that they don't stay
226 * reserved once we actually know the routing for this net (since otherwise
227 * the channel router would try to connect them up!).
228 *
229 * Results:
230 * None.
231 *
232 * Side effects:
233 * See above.
234 *
235 * ----------------------------------------------------------------------------
236 */
237
238 void
glCrossUnreserve(net)239 glCrossUnreserve(net)
240 NLNet *net;
241 {
242 NLTermLoc *loc;
243 NLTerm *term;
244 GCRPin *pin;
245
246 /* De-reserve the pins taken by each terminal location in this net */
247 for (term = net->nnet_terms; term; term = term->nterm_next)
248 for (loc = term->nterm_locs; loc; loc = loc->nloc_next)
249 {
250 pin = loc->nloc_pin;
251 ASSERT(pin->gcr_pSeg == GCR_STEMSEGID, "glCrossUnreserve");
252 pin->gcr_pId = (GCRNet *) NULL;
253 pin->gcr_pSeg = 0;
254 }
255 }
256
257 /*
258 * ----------------------------------------------------------------------------
259 *
260 * glCrossEnum --
261 *
262 * Enumerate the crossing points between the tile inPt->gl_tile
263 * and 'tp'. The two tiles should overlap different channels.
264 *
265 * For each available crossing (i.e., a pin that is yet unassigned
266 * and has a linked pin), call the procedure (*func)(), which should
267 * be of the following form:
268 *
269 * int
270 * (*func)(inPt, tp, pin, cdata)
271 * GlPoint *inPt; /# Same as inPt passed to glCrossEnum #/
272 * Tile *tp; /# Same as tp passed to glCrossEnum #/
273 * GCRPin *pin; /# A free pin in 'tp' #/
274 * ClientData cdata; /# Same as cdata passed to glCrossEnum #/
275 * {
276 * }
277 *
278 * If (*func)() returns 1, glCrossEnum() immediately stops visiting
279 * further crossing points and returns 1 itself; otherwise, we keep
280 * going until we run out of crossing points to visit.
281 *
282 * Results:
283 * Returns 1 if (*func)() returned 1; otherwise, returns 0.
284 *
285 * Side effects:
286 * Whatever (*func)() does.
287 *
288 * ----------------------------------------------------------------------------
289 */
290
291 int
glCrossEnum(inPt,tp,func,cdata)292 glCrossEnum(inPt, tp, func, cdata)
293 GlPoint *inPt; /* Top of heap point being expanded */
294 Tile *tp; /* Tile adjacent to inPt->gl_tile */
295 int (*func)(); /* Called for each crossing */
296 ClientData cdata; /* Passed to (*func)() */
297 {
298 int outSide, origin, lo, hi, max, start, n, nhi;
299 GCRChannel *ch = inPt->gl_pin->gcr_ch;
300 Tile *inTile = inPt->gl_tile;
301 GCRPin *pins, *pin;
302
303 /* Sanity checks: callers should ensure that these are true */
304 ASSERT(tp->ti_client != (ClientData) CLIENTDEFAULT, "glCrossEnum");
305 ASSERT((GCRChannel *) tp->ti_client != ch, "glCrossEnum");
306
307 /*
308 * Find out the direction from inTile to tp.
309 * We assume that the two tiles share a side, so this
310 * is pretty straightforward.
311 */
312 if (LEFT(inTile) == RIGHT(tp)) outSide = GEO_WEST;
313 else if (RIGHT(inTile) == LEFT(tp)) outSide = GEO_EAST;
314 else if (TOP(inTile) == BOTTOM(tp)) outSide = GEO_NORTH;
315 else if (BOTTOM(inTile) == TOP(tp)) outSide = GEO_SOUTH;
316
317 /*
318 * Find the range of points shared between the two tiles.
319 * Note that we look at the TILES, not the CHANNELS, since
320 * there can be many tiles for a single channel.
321 */
322 if (outSide == GEO_NORTH || outSide == GEO_SOUTH)
323 {
324 lo = MAX(LEFT(inTile), LEFT(tp));
325 hi = MIN(RIGHT(inTile), RIGHT(tp));
326 origin = ch->gcr_origin.p_x;
327 max = ch->gcr_length;
328 }
329 else
330 {
331 lo = MAX(BOTTOM(inTile), BOTTOM(tp));
332 hi = MIN(TOP(inTile), TOP(tp));
333 origin = ch->gcr_origin.p_y;
334 max = ch->gcr_width;
335 }
336
337 /*
338 * Now find the range of pins shared between the two tiles.
339 * We're careful about which pins are actually shared: we
340 * round the lower coordinate up unless it's grid-aligned,
341 * but round the higher coordinate down even if it is
342 * grid-aligned. I.e.,
343 *
344 * lo' = pin with least coordinate >= lo
345 * hi' = pin with greatest coordinate < hi
346 *
347 * The range of pins shared should be non-NULL; if it's not,
348 * something is wrong (most likely the channel is too small).
349 * The pins range from lo to hi, inclusive, and should not
350 * include pin[0] or pin[length+1] or pin[width+1] (the latter
351 * respectively for vertical or horizontal edges between tiles).
352 */
353 lo = (lo + RtrGridSpacing - 1 - origin) / RtrGridSpacing;
354 hi = (hi - origin - 1) / RtrGridSpacing;
355 ASSERT(lo >= 1 && lo <= max, "glCrossEnum");
356 if (lo > hi)
357 return 0;
358
359 switch (outSide)
360 {
361 case GEO_NORTH: pins = ch->gcr_tPins; break;
362 case GEO_SOUTH: pins = ch->gcr_bPins; break;
363 case GEO_EAST: pins = ch->gcr_rPins; break;
364 case GEO_WEST: pins = ch->gcr_lPins; break;
365 }
366
367 /*
368 * Now comes the fun part: enumerating pins in the range
369 * from lo .. hi inclusive in such a way that we visit
370 * the CLOSEST pin to inPt FIRST. Choose start so that
371 * it's the index of the closest pin on the exit side to
372 * inPt, and then worry about whether or not it's in the
373 * range of pins shared with the next tile.
374 */
375 start = (outSide == GEO_NORTH || outSide == GEO_SOUTH)
376 ? inPt->gl_pin->gcr_x
377 : inPt->gl_pin->gcr_y;
378
379 /* CASE 1: visit from bottom to top (or left to right) */
380 if (start <= lo)
381 {
382 for (n = lo; n <= hi; n++, glCrossingsSeen++)
383 {
384 pin = &pins[n];
385 if (PINOK(pin) && PINOK(pin->gcr_linked)
386 && (*func)(inPt, tp, pin->gcr_linked, cdata))
387 return 1;
388 }
389 return 0;
390 }
391
392 /* CASE 1: visit from top to bottom (or right to left) */
393 if (start >= hi)
394 {
395 for (n = hi; n >= lo; n--, glCrossingsSeen++)
396 {
397 pin = &pins[n];
398 if (PINOK(pin) && PINOK(pin->gcr_linked)
399 && (*func)(inPt, tp, pin->gcr_linked, cdata))
400 return 1;
401 }
402 return 0;
403 }
404
405 /*
406 * CASE 3:
407 * Have to consider candidates alternating from
408 * left to right (or top to bottom) to find the
409 * closest available pin. Start at the center.
410 */
411 for (n = start, nhi = start+1; n >= lo || nhi <= hi; n--, nhi++)
412 {
413 if (n >= lo)
414 {
415 glCrossingsSeen++;
416 pin = &pins[n];
417 if (PINOK(pin) && PINOK(pin->gcr_linked)
418 && (*func)(inPt, tp, pin->gcr_linked, cdata))
419 return 1;
420 }
421 if (nhi <= hi)
422 {
423 glCrossingsSeen++;
424 pin = &pins[nhi];
425 if (PINOK(pin) && PINOK(pin->gcr_linked)
426 && (*func)(inPt, tp, pin->gcr_linked, cdata))
427 return 1;
428 }
429 }
430
431 return 0;
432 }
433
434 /*
435 * ----------------------------------------------------------------------------
436 *
437 * glCrossAdjust --
438 *
439 * Given a path of crossing points, wiggle them around in each channel
440 * to try to reduce the total penalty on the path. Construct a new
441 * path of crossing points that uses the points we select in this way,
442 * and whose cost fields (gl_cost) include both distance and the
443 * penalties. Be careful when wiggling crossings through a river
444 * routing channel: they all have to wiggle at the same time.
445 *
446 * Algorithm:
447 * Two crossing points in the input path are already fixed:
448 * path itself, and the crossing point at the very end (the
449 * one for which gl_path is NULL). Starting from the crossing
450 * point at the end and working back toward 'path', assign
451 * crossings to all points in the middle. The procedure to
452 * do this is recursive, considering at each stage three
453 * crossing points: one that has already been assigned
454 * (which is either the last point in the path, or the result
455 * of the previous recursive call), one that is to be assigned
456 * (the current point along the path), and a "lookahead" point
457 * (the one that will be next assigned, so we can consider
458 * it as well when positining the current point.
459 *
460 * Results:
461 * Returns a pointer to the final point in a new path of crossings,
462 * linked via their gl_path pointers.
463 *
464 * Side effects:
465 * See above.
466 *
467 * ----------------------------------------------------------------------------
468 */
469
470 GlPoint *
glCrossAdjust(lookAhead,path)471 glCrossAdjust(lookAhead, path)
472 GlPoint *lookAhead; /* Normally, lookAhead->gl_path == path, except on the
473 * initial call, in which case lookAhead == NULL.
474 */
475 GlPoint *path; /* Adjust crossings along this path */
476 {
477 GlPoint *newPath, *newRest;
478 GCRPin *linkedPin, *pin;
479 GCRChannel *ch;
480
481 /*
482 * The location of the last crossing along the path is fixed,
483 * since it's the "starting point". Simply return when we
484 * reach this point, since there's no penalty to be computed
485 * yet.
486 */
487 ASSERT(path != (GlPoint *) NULL, "glCrossAdjust");
488 if (path->gl_path == (GlPoint *) NULL)
489 return path;
490
491 /*
492 * Basic recursive step: assign crossings to everything
493 * in the remainder of the path, then cons a new GlPoint
494 * to the front of the path and adjust its position
495 * below. The initial cost of newPath will be that
496 * to the pin it initially occupies, before being
497 * wiggled by glCrossChoose() later. This gives
498 * us an upper bound on an acceptable cost.
499 */
500 newRest = glCrossAdjust(path, path->gl_path);
501 newPath = glPathNew(path->gl_pin, 0, newRest);
502 newPath->gl_cost = newRest->gl_cost + glCrossCost(lookAhead, path, newRest);
503 newPath->gl_tile = path->gl_tile;
504
505 /*
506 * If this was the first crossing in the path, it's also
507 * immutable and so we just cons it to the path and return.
508 * We still use a new GlPoint, though, since the cost of
509 * this point has to include the penalties along the path.
510 */
511 if (lookAhead == (GlPoint *) NULL)
512 return newPath;
513
514 if (TiGetType(newRest->gl_tile) != CHAN_NORMAL)
515 {
516 /*
517 * If newRest was through a river-routing channel, it fixes
518 * the pin on the exit side.
519 */
520 pin = newRest->gl_pin;
521 ch = pin->gcr_ch;
522 switch (pin->gcr_side)
523 {
524 case GEO_NORTH: linkedPin = &ch->gcr_bPins[pin->gcr_x]; break;
525 case GEO_EAST: linkedPin = &ch->gcr_lPins[pin->gcr_y]; break;
526 case GEO_SOUTH: linkedPin = &ch->gcr_tPins[pin->gcr_x]; break;
527 case GEO_WEST: linkedPin = &ch->gcr_rPins[pin->gcr_y]; break;
528 }
529 ASSERT(PINOK(linkedPin), "glCrossAdjust");
530 newPath->gl_pin = linkedPin->gcr_linked;
531 newPath->gl_cost = newRest->gl_cost;
532 newPath->gl_cost += glCrossCost(lookAhead, newPath, newRest);
533 }
534 else
535 {
536 /*
537 * Time to choose a crossing for 'path'.
538 * It has to lie somewhere along the boundary between path->gl_tile
539 * and newRest->gl_tile. (These two tiles will be different unless
540 * path is the destination point, but we checked for that above when
541 * we looked for lookAhead being NULL). Enumerate the crossings
542 * along this boundary looking for the best one.
543 */
544 glCrossLookAhead = lookAhead;
545 (void) glCrossEnum(newRest, path->gl_tile, glCrossChoose,
546 (ClientData) newPath);
547 }
548
549 return newPath;
550 }
551
552 /*
553 * ----------------------------------------------------------------------------
554 *
555 * glCrossChoose --
556 *
557 * Called by glCrossEnum() on behalf of glCrossAdjust() above.
558 * Evaluate 'pin' as a possible crossing by computing the penalty of
559 * a segment from newRest through newPath (setting newPath->gl_pin to
560 * pin), and on through to glCrossLookAhead (if it's non-NULL).
561 *
562 * Results:
563 * Returns 0 normally, or 1 to tell glCrossEnum() that it
564 * can stop looking at further crossings.
565 *
566 * Side effects:
567 * May modify newPath->gl_cost and newPath->gl_pin.
568 *
569 * ----------------------------------------------------------------------------
570 */
571
572 /*ARGSUSED*/
573 int
glCrossChoose(newRest,tp,pin,newPath)574 glCrossChoose(newRest, tp, pin, newPath)
575 GlPoint *newRest; /* Portion of path already assigned */
576 Tile *tp; /* UNUSED */
577 GCRPin *pin; /* Pin on boundary of tp being considered */
578 GlPoint *newPath; /* Update newPath->gl_pin, newPath->gl_cost */
579 {
580 GCRPin *savePin;
581 int cost;
582
583 /*
584 * We've been visiting crossings in order of increasing distance
585 * from newRest. If the distance to 'pin' plus newRest->gl_cost
586 * already exceeds the best cost we've been able to find for
587 * newPath, then we can't gain any more improvement by considering
588 * any more crossing point, so we stop.
589 */
590 cost = ABSDIFF(pin->gcr_point.p_x, newRest->gl_pin->gcr_point.p_x)
591 + ABSDIFF(pin->gcr_point.p_y, newRest->gl_pin->gcr_point.p_y)
592 + newRest->gl_cost;
593 if (cost >= newPath->gl_cost)
594 return 1;
595
596 /*
597 * Evaluate the cost of using 'pin' as the crossing point.
598 * If it's a better choice than what's currently stored in newPath,
599 * then use it and update the cost in newPath.
600 */
601 savePin = newPath->gl_pin;
602 newPath->gl_pin = pin;
603 cost = newRest->gl_cost + glCrossCost(glCrossLookAhead, newPath, newRest);
604 if (cost < newPath->gl_cost)
605 newPath->gl_cost = cost;
606 else
607 newPath->gl_pin = savePin;
608
609 /* Keep looking at more crossing points */
610 return 0;
611 }
612
613 /*
614 * ----------------------------------------------------------------------------
615 *
616 * glCrossCost --
617 *
618 * Evaluate the cost of the segment from 'entryPt' to 'exitPt' (and on through
619 * 'lookAhead' if it is non-NULL).
620 *
621 * Results:
622 * Returns the sum of the distance from rest to path and the
623 * penalties associated with this segment.
624 *
625 * Side effects:
626 * None.
627 *
628 * ----------------------------------------------------------------------------
629 */
630
631 int
glCrossCost(lookAhead,exitPt,entryPt)632 glCrossCost(lookAhead, exitPt, entryPt)
633 GlPoint *lookAhead;
634 GlPoint *exitPt;
635 GlPoint *entryPt;
636 {
637 GCRPin *entryPin, *exitPin, *otherPin;
638 GCRPin *opposite;
639 int count, cost;
640
641 /*
642 * Make sure that both entryPin and exitPin are in the same
643 * channel, and otherPin is in the next channel.
644 */
645 entryPin = entryPt->gl_pin;
646 exitPin = exitPt->gl_pin;
647 if (exitPin->gcr_ch != entryPin->gcr_ch)
648 exitPin = exitPin->gcr_linked;
649 otherPin = exitPin->gcr_linked;
650 ASSERT(exitPin != NULL, "glCrossCost");
651
652 /* Distance cost */
653 cost = ABSDIFF(entryPin->gcr_point.p_x, exitPin->gcr_point.p_x)
654 + ABSDIFF(entryPin->gcr_point.p_y, exitPin->gcr_point.p_y);
655
656 /*
657 * If exitPt is in a river-routing tile, and we have to continue
658 * across the channel (lookAhead is non-NULL), then make sure the pin
659 * on the opposite side is free; otherwise, exitPt has "infinite"
660 * penalty since it's unusable.
661 */
662 if (lookAhead && TiGetType(exitPt->gl_tile) != CHAN_NORMAL)
663 {
664 switch (otherPin->gcr_side)
665 {
666 case GEO_NORTH:
667 opposite = &otherPin->gcr_ch->gcr_bPins[otherPin->gcr_x];
668 break;
669 case GEO_SOUTH:
670 opposite = &otherPin->gcr_ch->gcr_tPins[otherPin->gcr_x];
671 break;
672 case GEO_EAST:
673 opposite = &otherPin->gcr_ch->gcr_lPins[otherPin->gcr_y];
674 break;
675 case GEO_WEST:
676 opposite = &otherPin->gcr_ch->gcr_rPins[otherPin->gcr_y];
677 break;
678 }
679 if (!PINOK(opposite))
680 return INFINITY;
681 }
682
683 /* Penalty for using lots of channels */
684 cost += glChanPenalty;
685
686 /* Penalize if the net doesn't run straight across the channel */
687 if (entryPin->gcr_x != exitPin->gcr_x && entryPin->gcr_y != exitPin->gcr_y)
688 cost += glJogPenalty;
689
690 /*
691 * If there is an obstacle or hazard over a crossing, or an
692 * obstacle somewhere along the track or column of the pin,
693 * then assess a penalty. Look on both sides of the crossing
694 * to get this penalty.
695 */
696 #define BADCROSSFLAGS (GCROBST|GCRHAZRD|GCRTCC)
697 if (otherPin && otherPin->gcr_ch->gcr_type == CHAN_NORMAL)
698 {
699 if ((otherPin->gcr_pFlags & BADCROSSFLAGS) || otherPin->gcr_pSize != 0)
700 {
701 ASSERT(otherPin->gcr_pSize >= 0, "glCrossPenalty");
702 cost += glObsPenalty1;
703 if (otherPin->gcr_pFlags & GCROBST)
704 cost += glObsPenalty2 * otherPin->gcr_pSize;
705 else if (otherPin->gcr_pFlags & GCRHAZRD)
706 cost += MAX(glObsPenalty2*otherPin->gcr_pSize
707 - otherPin->gcr_pDist, 0);
708 }
709 }
710
711 /*
712 * Done if this channel is used for river-routing (in which
713 * case the subsequent penalty computation is not needed).
714 */
715 if (entryPin->gcr_ch->gcr_type != CHAN_NORMAL)
716 return cost;
717
718 if ((exitPin->gcr_pFlags & BADCROSSFLAGS) || exitPin->gcr_pSize != 0)
719 {
720 ASSERT(exitPin->gcr_pSize >= 0, "glCrossPenalty");
721 cost += glObsPenalty1;
722 if (exitPin->gcr_pFlags & GCROBST)
723 cost += glObsPenalty2 * exitPin->gcr_pSize;
724 else if (exitPin->gcr_pFlags & GCRHAZRD)
725 cost += MAX(glObsPenalty2 * exitPin->gcr_pSize
726 - exitPin->gcr_pDist, 0);
727 }
728
729 /* Penalty for "congestion" (neighboring pins in use) */
730 count = 0;
731 if ((exitPin + 1)->gcr_pId) count++;
732 if ((exitPin - 1)->gcr_pId) count++;
733 if (count == 2) cost += glNbrPenalty2;
734 else if (count == 1) cost += glNbrPenalty1;
735
736 /*
737 * If the path turns in the channel and the exit crossing
738 * isn't a paired orphan, assess a penalty.
739 */
740 if (exitPin->gcr_side != GeoOppositePos[entryPin->gcr_side])
741 {
742 switch (exitPin->gcr_side)
743 {
744 case GEO_NORTH:
745 otherPin = &entryPin->gcr_ch->gcr_bPins[exitPin->gcr_x];
746 break;
747 case GEO_SOUTH:
748 otherPin = &entryPin->gcr_ch->gcr_tPins[exitPin->gcr_x];
749 break;
750 case GEO_EAST:
751 otherPin = &entryPin->gcr_ch->gcr_lPins[exitPin->gcr_y];
752 break;
753 case GEO_WEST:
754 otherPin = &entryPin->gcr_ch->gcr_rPins[exitPin->gcr_y];
755 break;
756 }
757 if (otherPin->gcr_pId == (GCRNet *) NULL)
758 cost += glOrphanPenalty;
759 }
760
761 return cost;
762 }
763
764 /*
765 * ----------------------------------------------------------------------------
766 *
767 * glCrossScalePenalties --
768 *
769 * Scale the penalties used in the global router cost function so they
770 * reflect the actual grid size used during routing.
771 *
772 * Results:
773 * None.
774 *
775 * Side effects:
776 * See above.
777 *
778 * ----------------------------------------------------------------------------
779 */
780
781 void
glCrossScalePenalties()782 glCrossScalePenalties()
783 {
784 if (glPenaltiesScaled)
785 return;
786
787 glPenaltiesScaled = TRUE;
788 glJogPenalty *= RtrGridSpacing;
789 glObsPenalty1 *= RtrGridSpacing;
790 glObsPenalty2 *= RtrGridSpacing;
791 glNbrPenalty1 *= RtrGridSpacing;
792 glNbrPenalty2 *= RtrGridSpacing;
793 glOrphanPenalty *= RtrGridSpacing;
794 glChanPenalty *= RtrGridSpacing;
795 }
796