1 /*
2 * groutePen.c
3 *
4 * Computation of the penalties to be assigned for each net using
5 * certain congested regions.
6 *
7 * *********************************************************************
8 * * Copyright (C) 1985, 1990 Regents of the University of California. *
9 * * Permission to use, copy, modify, and distribute this *
10 * * software and its documentation for any purpose and without *
11 * * fee is hereby granted, provided that the above copyright *
12 * * notice appear in all copies. The University of California *
13 * * makes no representations about the suitability of this *
14 * * software for any purpose. It is provided "as is" without *
15 * * express or implied warranty. Export of this software outside *
16 * * of the United States of America may require an export license. *
17 * *********************************************************************
18 */
19
20 #ifndef lint
21 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/grouter/groutePen.c,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $";
22 #endif /* lint */
23
24 #include <stdio.h>
25 #include "utils/magic.h"
26 #include "utils/geometry.h"
27 #include "utils/hash.h"
28 #include "utils/heap.h"
29 #include "tiles/tile.h"
30 #include "database/database.h"
31 #include "utils/netlist.h"
32 #include "gcr/gcr.h"
33 #include "router/router.h"
34 #include "grouter/grouter.h"
35 #include "utils/signals.h"
36 #include "textio/textio.h"
37 #include "utils/malloc.h"
38 #include "utils/styles.h"
39 #include "utils/list.h"
40
41 /* Forward declarations */
42 void glPenSavePath();
43 int glPenSortNetSet();
44 int glPenFindCrossingFunc();
45 int glPenDeleteFunc();
46 int glPenRouteCost();
47 int glPenRerouteNetCost();
48 NetSet *glPenFindCrossingNets();
49 CZone *glPenScanDens();
50 CZone *glPenFindCZones();
51
52
53 /*
54 * ----------------------------------------------------------------------------
55 *
56 * glPenSetPerChan --
57 * glPenClearPerChan --
58 *
59 * Visit all of the channels on the CZone list for 'net'
60 * (this list is ((NetClient *) net->nnet_cdata)->nc_pens);
61 * glPenSetPerChan will prepend a copy of each CZone
62 * to the penalty list for the appropriate channel, while
63 * glPenClearPerChan will free the list for each channel.
64 *
65 * Results:
66 * None.
67 *
68 * Side effects:
69 * See above.
70 *
71 * ----------------------------------------------------------------------------
72 */
73
74 void
glPenSetPerChan(net)75 glPenSetPerChan(net)
76 NLNet *net;
77 {
78 CZone *czNet, *czChan;
79 GlobChan *gc;
80
81 for (czNet = ((NetClient *) net->nnet_cdata)->nc_pens;
82 czNet;
83 czNet = czNet->cz_next)
84 {
85 gc = (GlobChan *) czNet->cz_chan->gcr_client;
86 czChan = (CZone *) mallocMagic((unsigned) (sizeof (CZone)));
87 *czChan = *czNet;
88 czChan->cz_next = gc->gc_penList;
89 gc->gc_penList = czChan;
90 }
91 }
92
93 int
glPenClearPerChan(net)94 glPenClearPerChan(net)
95 NLNet *net;
96 {
97 CZone *czNet, *czChan;
98 GlobChan *gc;
99
100 for (czNet = ((NetClient *) net->nnet_cdata)->nc_pens;
101 czNet;
102 czNet = czNet->cz_next)
103 {
104 gc = (GlobChan *) czNet->cz_chan->gcr_client;
105 for (czChan = gc->gc_penList; czChan; czChan = czChan->cz_next)
106 freeMagic((char *) czChan);
107 gc->gc_penList = (CZone *) NULL;
108 }
109 return 0;
110 }
111
112 /*
113 * ----------------------------------------------------------------------------
114 *
115 * glPenCompute --
116 *
117 * Some routing regions will have many nets passing through them.
118 * It may be, however, that some of these nets need a given region
119 * much more than others: the cost to them of going around the
120 * region is very high. This procedure attempts to identify
121 * congested regions (CZones), and furthermore to determine the
122 * nets that should be penalized for using those regions and the
123 * amount of the penalty.
124 *
125 * On input, the gc_prevDens and gc_postDens fields of each channel's
126 * associated GlobChan structure should be set up to reflect the
127 * presence of blocking information.
128 *
129 * Algorithm:
130 * Route each net as though it were the first net to be routed.
131 * Avoid routing through any portion of a channel that is already
132 * at density (from pre-existing wiring), but otherwise don't
133 * bother computing penalties. Choose crossing points to give
134 * locally (i.e, per-channel) optimal lengths. This enables
135 * us to avoid looking at most crossing points so we can route
136 * very quickly.
137 *
138 * Remember each of the paths that comprised each net by storing
139 * a permanent copy of each in the list nc_paths in the NetClient
140 * structure for each net.
141 *
142 * After all nets have been processed, update density in the
143 * gc_postDens density map of all channels to reflect the routes
144 * assigned to all nets. For each region of a channel where density
145 * has been exceeded, we look at all the nets that pass through the
146 * region and see how expensive it would be to route each one if it
147 * had to avoid that region entirely. (It is infinitely expensive
148 * if the region contains either the starting or ending point of the
149 * route!)
150 *
151 * While the costs computed above are just an estimate (since they
152 * consider each net independently), the hope is that they will
153 * identify fairly well those nets that can easily avoid congested
154 * areas with only slight detours, as well as those nets for which
155 * certain regions of channels are critical.
156 *
157 * We pick those nets whose cost increases the least by having to
158 * avoid the congested region as those that will be penalized; the
159 * penalty for each net is the additional cost of avoiding the region
160 * for the net for which this cost is highest. (In effect, this gives
161 * us a balanced tradeoff: the net with low cost for not using the
162 * channel won't use it unless it has otherwise to make at least as
163 * big a detour as our estimate for the most expensive one).
164 *
165 * Results:
166 * None.
167 *
168 * Side effects:
169 * Stores a pointer to a list of CZone structures in
170 * the nnet_cdata->nc_pens field of each net in netList.
171 * (The list may be NULL). Each element in the list identifies
172 * a channel and a penalty; the interpretation is that this
173 * net should be penalized by the indicated penalty if it
174 * has to go through this channel.
175 * Also uses nnet_cdata->nc_paths as temporary working storage.
176 *
177 * ----------------------------------------------------------------------------
178 */
179
180 void
glPenCompute(chanList,netList)181 glPenCompute(chanList, netList)
182 GCRChannel *chanList; /* All the channels in the routing problem */
183 NLNetList *netList; /* Netlist being routed */
184 {
185 #ifdef notdef
186 CZone *czones, *cz;
187 GlobChan *gc;
188 GCRChannel *ch;
189 NLNet *net;
190
191 /*
192 * Process nets in the order they appear, since this routing
193 * is order-independent. After all done, we have remembered
194 * the GlPoints for all a net's segments in the NetClient nc_paths
195 * list for that net. Also, the density map gc_postDens in each
196 * channel's GlobChan has been set.
197 */
198 for (net = netList->nnl_nets; net; net = net->nnet_next)
199 glMultiSteiner((CellUse *) NULL, net, glProcessLoc, glPenSavePath,
200 (ClientData) TRUE, (ClientData) NULL);
201
202 /*
203 * Set the density map gc_postDens in all channels.
204 * The initial contents of gc_postDens should have been set
205 * to the same as gc_prevDens by the caller; we just add
206 * all the nets routed in the step above.
207 */
208 for (net = netList->nnl_nets; net; net = net->nnet_next)
209 glPenDensitySet(net);
210
211 /*
212 * Find all the congested zones in the circuit and store them in
213 * a list of CZone structures.
214 */
215 czones = glPenFindCZones(chanList);
216
217 /*
218 * Process each CZone to determine which nets should be assigned
219 * penalties for crossing that zone. The penalties assigned to
220 * a net for a CZone in an earlier iteration apply to attempts
221 * to route that net around other CZones in later iterations.
222 * The final result of this step is to build the nc_pens list
223 * for each net's NetClient structure.
224 */
225 for (cz = czones; cz; cz = cz->cz_next)
226 glPenAssignCosts(cz, netList);
227
228 /*
229 * Final cleanup: free the GlPoints in each net's nc_paths list,
230 * since they're no longer needed. Also reset gc_postDens in
231 * each channel to its initial value, gc_prevDens.
232 */
233 for (net = netList->nnl_nets; net; net = net->nnet_next)
234 glPenCleanNet(net);
235 for (ch = chanList; ch; ch = ch->gcr_next)
236 {
237 gc = (GlobChan *) ch->gcr_client;
238 glDMCopy(&gc->gc_prevDens[CZ_COL], &gc->gc_postDens[CZ_COL]);
239 glDMCopy(&gc->gc_prevDens[CZ_ROW], &gc->gc_postDens[CZ_ROW]);
240 }
241 #endif /* notdef */
242 }
243
244 /*
245 * ----------------------------------------------------------------------------
246 *
247 * glPenFindCZones --
248 *
249 * Build up a list of all congested zones in all channels.
250 * See grouter.h for a definition of a congested zone.
251 * The density map we search is gc_postDens.
252 *
253 * Results:
254 * Returns a pointer to the list.
255 *
256 * Side effects:
257 * Allocates memory.
258 *
259 * ----------------------------------------------------------------------------
260 */
261
262 CZone *
glPenFindCZones(chanList)263 glPenFindCZones(chanList)
264 GCRChannel *chanList; /* All the channels in the routing problem */
265 {
266 CZone *czList;
267 DensMap *dmap;
268 GCRChannel *ch;
269
270 czList = (CZone *) NULL;
271 for (ch = chanList; ch; ch = ch->gcr_next)
272 {
273 dmap = ((GlobChan *) ch->gcr_client)->gc_postDens;
274 czList = glPenScanDens(czList, ch, &dmap[CZ_COL], CZ_COL);
275 czList = glPenScanDens(czList, ch, &dmap[CZ_ROW], CZ_ROW);
276 }
277
278 return czList;
279 }
280
281 /*
282 * ----------------------------------------------------------------------------
283 *
284 * glPenScanDens --
285 *
286 * Scan for portions of a density map where the density exceeds the
287 * capacity, and allocate a CZone for each such range.
288 *
289 * Results:
290 * Returns a pointer to a CZone list with the new elements
291 * described above prepended to czList.
292 *
293 * Side effects:
294 * Allocates memory.
295 *
296 * ----------------------------------------------------------------------------
297 */
298
299 CZone *
glPenScanDens(czList,ch,dm,type)300 glPenScanDens(czList, ch, dm, type)
301 CZone *czList; /* Prepend to this list */
302 GCRChannel *ch; /* Which channel is being processed */
303 DensMap *dm; /* Map to search */
304 int type; /* Type of zone: CZ_ROW or CZ_COL */
305 {
306 short *val = dm->dm_value;
307 CZone *cz;
308 int i;
309
310 /* Nothing to do if the capacity is never exceeded */
311 if (dm->dm_max <= dm->dm_cap)
312 return czList;
313
314 /*
315 * Simple state machine to find the start and end of
316 * each zone of excess density. If cz is NULL then
317 * we're currently out of a zone; otherwise, we're
318 * building one up. Consider elements of the density
319 * map from 1 .. dm->dm_size.
320 */
321 cz = (CZone *) NULL;
322 for (i = 1; i < dm->dm_size; i++)
323 {
324 if (cz)
325 {
326 if (val[i] <= dm->dm_cap)
327 {
328 /* End of congested zone */
329 cz->cz_hi = i - 1;
330 cz = (CZone *) NULL;
331 }
332 }
333 else
334 {
335 if (val[i] > dm->dm_cap)
336 {
337 /* Beginning of congested zone */
338 cz = (CZone *) mallocMagic((unsigned) (sizeof (CZone)));
339 cz->cz_chan = ch;
340 cz->cz_type = type;
341 cz->cz_lo = i;
342 cz->cz_penalty = 0;
343 cz->cz_nets = (NetSet *) NULL;
344 cz->cz_next = czList;
345 czList = cz;
346 }
347 }
348 }
349
350 /* Take care of case when a CZone extends all the way to the end */
351 if (cz) cz->cz_hi = dm->dm_size - 1;
352
353 return czList;
354 }
355
356 /*
357 * ----------------------------------------------------------------------------
358 *
359 * glPenAssignCosts --
360 *
361 * Find all nets that cross a congested zone and determine how expensive
362 * it would be to reroute each if they had to avoid that zone. Once this
363 * cost is determined for all nets affected, pick the N least-cost nets,
364 * where N is the number of nets that would have to be re-routed in order
365 * to reduce the number running through the congested zone to be within
366 * its capacity (N should always be greater than zero). Prepend a CZone
367 * to the np_pens list of each of these N nets NetClients, with a cz_penalty
368 * equal to the cost of the most-expensive-to-reroute net.
369 *
370 * Results:
371 * None.
372 *
373 * Side effects:
374 * Allocates memory for the CZones placed on each NetClient's np_pens
375 * list; see above for details.
376 *
377 * ----------------------------------------------------------------------------
378 */
379
380 void
glPenAssignCosts(cz,netList)381 glPenAssignCosts(cz, netList)
382 CZone *cz; /* A single CZone being processed */
383 NLNetList *netList; /* List of all nets; we look for nets that cross
384 * this zone.
385 */
386 {
387 int oldCost, newCost, maxCost, numCross, density;
388 NetSet *crossNets, *ns, **crossArray, **nsap;
389 GlobChan *gc;
390 DensMap *dm;
391 CZone *czNew;
392 NetClient *nc;
393 List *list;
394
395 /* Find the nets that use this congested zone */
396 crossNets = glPenFindCrossingNets(cz, netList);
397
398 /*
399 * For each net in the set, determine how expensive it would be
400 * if it couldn't use this congested zone at all.
401 */
402 maxCost = 0;
403 numCross = 0;
404 for (ns = crossNets; ns; ns = ns->ns_next)
405 {
406 oldCost = 0;
407 nc = (NetClient *) ns->ns_net->nnet_cdata;
408
409 for (list = nc->nc_paths; list; list = LIST_TAIL(list))
410 oldCost += ((GlPoint *) LIST_FIRST(list))->gl_cost;
411 newCost = glPenRerouteNetCost(cz, ns->ns_net);
412 ns->ns_cost = newCost - oldCost;
413 if (ns->ns_cost > maxCost) maxCost = ns->ns_cost;
414 numCross++;
415 }
416
417 /*
418 * Sort the NetSets on the crossNets list in order of increasing
419 * ns_cost, leaving crossArray[i] pointing to the i'th smallest
420 * NetSet.
421 */
422 crossArray = (NetSet **) mallocMagic((unsigned) (numCross * sizeof (NetSet *)));
423 for (ns = crossNets, nsap = crossArray; ns; ns = ns->ns_next) *nsap++ = ns;
424 qsort(crossArray, numCross, sizeof (NetSet *), glPenSortNetSet);
425
426 /*
427 * Now comes the fun part.
428 * We must select a group of nets to assign a penalty of maxCost.
429 * The best nets to receive this penalty are those whose cost
430 * to reroute around 'cz' is least. However, we also want to
431 * assign this penalty to the minimum number of nets necessary
432 * to eliminate the congestion at 'cz' (i.e, to reduce the
433 * density to equal the channel capacity).
434 *
435 * The approach below is to start pulling nets out of the
436 * congested zone, in order of increasing ns_cost, until
437 * the congestion disappears.
438 */
439 gc = (GlobChan *) cz->cz_chan->gcr_client;
440 dm = &gc->gc_postDens[cz->cz_type];
441 density = glDMMaxInRange(dm, cz->cz_lo, cz->cz_hi);
442 nsap = crossArray;
443 while (density > dm->dm_cap)
444 {
445 ns = *nsap++;
446 nc = (NetClient *) ns->ns_net->nnet_cdata;
447 czNew = (CZone *) mallocMagic((unsigned) (sizeof (CZone)));
448 *czNew = *cz;
449 czNew->cz_penalty = maxCost;
450 czNew->cz_nets = (NetSet *) NULL;
451 czNew->cz_next = nc->nc_pens;
452 nc->nc_pens = czNew;
453
454 /* Update 'dm' to reflect the absence of the net */
455 density = glPenDeleteNet(dm, nc->nc_paths, cz);
456 }
457
458 /* Cleanup */
459 for (ns = crossNets; ns; ns = ns->ns_next)
460 freeMagic((char *) ns);
461 freeMagic((char *) crossArray);
462 }
463
464 /*
465 * glPenSortNetSet --
466 *
467 * Called by qsort() to compare the ns_cost values of two NetSets
468 * pointed to by *ns1 and *ns2 respectively.
469 *
470 * Results:
471 * (*ns1)->ns_cost ? (*ns2)->ns_cost returns
472 * --------------------------------- -------
473 * > 1
474 * < -1
475 * = 0
476 *
477 * Side effects:
478 * None.
479 */
480
481 int
glPenSortNetSet(ns1,ns2)482 glPenSortNetSet(ns1, ns2)
483 NetSet **ns1, **ns2;
484 {
485 if ((*ns1)->ns_cost > (*ns2)->ns_cost) return 1;
486 if ((*ns1)->ns_cost < (*ns2)->ns_cost) return -1;
487 return 0;
488 }
489
490 /*
491 * ----------------------------------------------------------------------------
492 *
493 * glPenFindCrossingNets --
494 *
495 * Find all the nets in 'netList' whose routes cross through the
496 * congested zone 'cz'.
497 *
498 * Results:
499 * Returns a list of NetSet structs pointing to the nets
500 * found to cross through 'cz'.
501 *
502 * Side effects:
503 * Allocates memory.
504 *
505 * ----------------------------------------------------------------------------
506 */
507
508 /* Structure passed to glPenFindCrossingFunc() via glPenEnumCross() */
509 struct glCrossClient
510 {
511 NLNet *rcc_net; /* Net whose segments are being enumerated */
512 NetSet *rcc_set; /* NetSet being built up */
513 };
514
515 NetSet *
glPenFindCrossingNets(cz,netList)516 glPenFindCrossingNets(cz, netList)
517 CZone *cz; /* A single CZone being processed */
518 NLNetList *netList; /* List of all nets; we look for nets that cross
519 * this zone.
520 */
521 {
522 struct glCrossClient rcc;
523 List *list;
524 NLNet *net;
525
526 rcc.rcc_set = (NetSet *) NULL;
527 for (net = netList->nnl_nets; net; net = net->nnet_next)
528 {
529 rcc.rcc_net = net;
530 for (list = ((NetClient *) net->nnet_cdata)->nc_paths;
531 list;
532 list = LIST_TAIL(list))
533 {
534 if (glPenEnumCross(cz, (GlPoint *) LIST_FIRST(list),
535 glPenFindCrossingFunc, (ClientData) &rcc))
536 break;
537 }
538 }
539
540 return rcc.rcc_set;
541 }
542
543 /*
544 * ----------------------------------------------------------------------------
545 *
546 * glPenFindCrossingFunc --
547 *
548 * Filter function for glPenFindCrossingNets() above, called by
549 * glPenEnumCross() for each segment on an GlPoint that crosses
550 * through the CZone 'cz'.
551 *
552 * Results:
553 * Always returns 1.
554 *
555 * Side effects:
556 * Allocates a NetSet for rcc->rcc_net and prepends it
557 * to the NetSet list rcc->rcc_set.
558 *
559 * ----------------------------------------------------------------------------
560 */
561
562 /*ARGSUSED*/
563 int
glPenFindCrossingFunc(cz,srcPin,dstPin,rcc)564 glPenFindCrossingFunc(cz, srcPin, dstPin, rcc)
565 CZone *cz; /* UNUSED */
566 GCRPin *srcPin, *dstPin; /* UNUSED */
567 struct glCrossClient *rcc;
568 {
569 NetSet *ns;
570
571 ns = (NetSet *) mallocMagic((unsigned) (sizeof (NetSet)));
572 ns->ns_net = rcc->rcc_net;
573 ns->ns_cost = 0;
574 ns->ns_next = rcc->rcc_set;
575 rcc->rcc_set = ns;
576 return 1;
577 }
578
579 /*
580 * ----------------------------------------------------------------------------
581 *
582 * glPenEnumCross --
583 *
584 * Find all the segments on the GlPoint 'rp' that pass through the CZone 'cz'.
585 * For each segment, call the supplied procedure (*func)(), which should be
586 * of the following form:
587 *
588 * int
589 * (*func)(cz, srcPin, dstPin, cdata)
590 * CZone *cz; --- same as our argument 'cz'
591 * GCRPin *srcPin, *dstPin; --- two pins in cz's channel
592 * ClientData cdata; --- same as our argument 'cdata'
593 * {
594 * }
595 *
596 * This procedure should return 0 if glPenEnumCross() is to continue
597 * visiting further segments of the GlPoint, or a non-zero value if
598 * we are to stop visiting further segments.
599 *
600 * Results:
601 * Returns 0 if the end of the GlPoint was reached without
602 * (*func)() returning a non-zero value (or if no segments
603 * crossed through 'cz'). Returns 1 if (*func)() returned
604 * a non-zero value for some segment.
605 *
606 * Side effects:
607 * Whatever (*func)() does.
608 *
609 * ----------------------------------------------------------------------------
610 */
611
612 int
glPenEnumCross(cz,rp,func,cdata)613 glPenEnumCross(cz, rp, func, cdata)
614 CZone *cz; /* Look for segments passing through here */
615 GlPoint *rp; /* List of GlPoints (linked by gl_path ptrs) */
616 int (*func)(); /* Apply to each segment passing through cz */
617 ClientData cdata; /* Passed to (*func)() */
618 {
619 GCRPin *srcPin, *dstPin;
620 int cSrc, cDst;
621
622 for ( ; rp->gl_path; rp = rp->gl_path)
623 {
624 /* Only interested if this segment is in cz_chan */
625 srcPin = rp->gl_path->gl_pin;
626 if (srcPin->gcr_ch != cz->cz_chan)
627 continue;
628 dstPin = rp->gl_pin;
629 if (dstPin->gcr_ch != srcPin->gcr_ch)
630 dstPin = dstPin->gcr_linked;
631
632 if (cz->cz_type == CZ_ROW)
633 {
634 cSrc = srcPin->gcr_y;
635 cDst = dstPin->gcr_y;
636 }
637 else
638 {
639 cSrc = srcPin->gcr_x;
640 cDst = dstPin->gcr_x;
641 }
642
643 if ((cSrc >= cz->cz_lo && cSrc <= cz->cz_hi)
644 || (cDst >= cz->cz_lo && cDst <= cz->cz_hi))
645 {
646 if ((*func)(cz, srcPin, dstPin, cdata))
647 return 1;
648 }
649 }
650
651 return 0;
652 }
653
654 /*
655 * ----------------------------------------------------------------------------
656 *
657 * glPenRerouteNetCost --
658 *
659 * Determine how expensive it would be for net 'net' if it couldn't
660 * be routed through 'cz'.
661 *
662 * Results:
663 * Cost value.
664 *
665 * Side effects:
666 * Frees memory; resets the nc_paths list to NULL.
667 *
668 * ----------------------------------------------------------------------------
669 */
670
671 int
glPenRerouteNetCost(cz,net)672 glPenRerouteNetCost(cz, net)
673 CZone *cz;
674 NLNet *net; /* Net to be rerouted */
675 {
676 NetClient *nc = (NetClient *) net->nnet_cdata;
677 CZone fakeCZ;
678 int cost;
679
680 /* Prepend a fake CZone with infinite cost */
681 fakeCZ = *cz;
682 fakeCZ.cz_penalty = INFINITY;
683 fakeCZ.cz_next = nc->nc_pens;
684 nc->nc_pens = &fakeCZ;
685
686 /*
687 * Set the channel penalties and perform a normal routing,
688 * but just sum the cost of the resultant path instead of
689 * storing it anywhere.
690 */
691 cost = 0;
692 glPenSetPerChan(net);
693 glMultiSteiner((CellUse *) NULL, net, glProcessLoc, glPenRouteCost,
694 (ClientData) TRUE, (ClientData) &cost);
695 glPenClearPerChan(net);
696
697 /* Remove the fake CZone */
698 nc->nc_pens = nc->nc_pens->cz_next;
699
700 return cost;
701 }
702
703 /*ARGSUSED*/
704 int
glPenRouteCost(rootUse,bestPath,pNetId,pCost)705 glPenRouteCost(rootUse, bestPath, pNetId, pCost)
706 CellUse *rootUse; /* UNUSED */
707 GlPoint *bestPath; /* Best path for this segment */
708 NetId *pNetId; /* UNUSED */
709 int *pCost; /* Add bestPath->gl_cost to this */
710 {
711 *pCost += bestPath->gl_cost;
712 return 0;
713 }
714
715 /*
716 * ----------------------------------------------------------------------------
717 *
718 * glPenDeleteNet --
719 *
720 * Modify the density map 'dm' to reflect the absence of all
721 * segments on 'list' (a List each of whose elements is the first
722 * GlPoints on a path of GlPoints) that pass through the CZone 'cz'.
723 * Only the entries of the density map that lie between cz->cz_lo
724 * and cz->cz_hi (inclusive) are affected.
725 *
726 * Results:
727 * Returns the new maximum density in 'dm' in the range
728 * cz->cz_lo through cz->cz_hi inclusive.
729 *
730 * Side effects:
731 * Modifies 'dm' as described above.
732 *
733 * ----------------------------------------------------------------------------
734 */
735
736 int
glPenDeleteNet(dm,list,cz)737 glPenDeleteNet(dm, list, cz)
738 DensMap *dm; /* Update this map */
739 List *list; /* List of paths */
740 CZone *cz; /* Remove all segments passing through 'cz' from 'dm' */
741 {
742 for ( ; list; list = LIST_TAIL(list))
743 (void) glPenEnumCross(cz, (GlPoint *) LIST_FIRST(list),
744 glPenDeleteFunc, (ClientData) dm);
745
746 return glDMMaxInRange(dm, cz->cz_lo, cz->cz_hi);
747 }
748
749 /*
750 * glPenDeleteFunc --
751 *
752 * Do the real work of glPenDeleteNet() above. Called by glPenEnumCross()
753 * for each segment of the global routing of a net that passes through 'cz'.
754 * Updates 'dm' to reflect the ripping up of that portion of the segment
755 * that actually passes through 'cz'; portions of 'dm' that lie outside
756 * of 'cz' (cz->cz_lo through cz->cz_hi inclusive) are unaffected.
757 *
758 * Results:
759 * Always returns 0.
760 *
761 * Side effects:
762 * Modifies 'dm' as described in the comments for glPenDeleteNet().
763 */
764
765 int
glPenDeleteFunc(cz,srcPin,dstPin,dm)766 glPenDeleteFunc(cz, srcPin, dstPin, dm)
767 CZone *cz; /* Being passed through by srcPin..dstPin */
768 GCRPin *srcPin, *dstPin; /* Two pins in cz->cz_chan */
769 DensMap *dm; /* Remove srcPin..dstPin segment from 'dm' */
770 {
771 int n;
772 int lo, hi;
773
774 if (cz->cz_type == CZ_COL)
775 {
776 /* Find range of columns spanned by the net */
777 lo = MIN(srcPin->gcr_x, dstPin->gcr_x);
778 hi = MAX(srcPin->gcr_x, dstPin->gcr_x);
779 }
780 else
781 {
782 /* Find range of rows spanned by the net */
783 lo = MIN(srcPin->gcr_y, dstPin->gcr_y);
784 hi = MAX(srcPin->gcr_y, dstPin->gcr_y);
785 }
786
787 /* Clip so we don't modify entries of 'dm' outside of 'cz' */
788 lo = MAX(lo, cz->cz_lo);
789 lo = MIN(lo, cz->cz_hi);
790 hi = MIN(hi, cz->cz_hi);
791 hi = MAX(hi, cz->cz_lo);
792
793 /* Rip up this segment */
794 for (n = lo; n <= hi; n++)
795 dm->dm_value[n]--;
796
797 return 0;
798 }
799
800 /*
801 * ----------------------------------------------------------------------------
802 *
803 * glPenCleanNet --
804 *
805 * Free the GlPoints in a net's nc_paths list.
806 *
807 * Results:
808 * None.
809 *
810 * Side effects:
811 * Frees memory; resets the nc_paths list to NULL.
812 *
813 * ----------------------------------------------------------------------------
814 */
815
816 void
glPenCleanNet(net)817 glPenCleanNet(net)
818 NLNet *net;
819 {
820 List *list;
821 NetClient *nc;
822
823 nc = (NetClient *) net->nnet_cdata;
824 for (list = nc->nc_paths; list; list = LIST_TAIL(list))
825 glPathFreePerm((GlPoint *) LIST_FIRST(list));
826 ListDealloc(list);
827 nc->nc_paths = (List *) NULL;
828 }
829
830 /*
831 * ----------------------------------------------------------------------------
832 *
833 * glPenSavePath --
834 *
835 * Make a permanent copy of the GlPoint list 'path', and prepend the
836 * first element to the list being maintained for pNetId->netid_net's
837 * NetClient nc_paths field.
838 *
839 * Results:
840 * None.
841 *
842 * Side effects:
843 * See above.
844 *
845 * ----------------------------------------------------------------------------
846 */
847
848 void
glPenSavePath(rootUse,path,pNetId)849 glPenSavePath(rootUse, path, pNetId)
850 CellUse *rootUse; /* UNUSED */
851 GlPoint *path; /* Path linked via gl_path pointers */
852 NetId *pNetId; /* Net and segment identifier */
853 {
854 GlPoint *newpath;
855 NetClient *nc;
856
857 nc = (NetClient *) pNetId->netid_net->nnet_cdata;
858
859 /* Keep a permanent copy of the path */
860 newpath = glPathCopyPerm(path);
861 LIST_ADD(newpath, nc->nc_paths);
862 }
863
864 /*
865 * ----------------------------------------------------------------------------
866 *
867 * glPenDensitySet --
868 *
869 * Updates the density in the gc_postDens map in each channel
870 * reflect all of the paths for 'net'.
871 *
872 * Results:
873 * None.
874 *
875 * Side effects:
876 * See above.
877 *
878 * ----------------------------------------------------------------------------
879 */
880
881 void
glPenDensitySet(net)882 glPenDensitySet(net)
883 NLNet *net;
884 {
885 NetClient *nc = (NetClient *) net->nnet_cdata;
886 GCRPin *srcPin, *dstPin;
887 GlPoint *rp;
888 GlPoint *path;
889 List *list;
890 NetId netid;
891
892 netid.netid_net = net;
893 netid.netid_seg = 0;
894
895 for (list = ((NetClient *) net->nnet_cdata)->nc_paths;
896 list;
897 list = LIST_TAIL(list))
898 {
899 path = (GlPoint *) LIST_FIRST(list);
900 for (rp = path; rp->gl_path; rp = rp->gl_path)
901 {
902 srcPin = rp->gl_path->gl_pin;
903 dstPin = rp->gl_pin;
904 if (dstPin->gcr_ch != srcPin->gcr_ch) dstPin = dstPin->gcr_linked;
905 glDensAdjust(((GlobChan *) srcPin->gcr_ch->gcr_client)->gc_postDens,
906 srcPin, dstPin, netid);
907 }
908 }
909 }
910