1 /*
2 * grouteDens.c
3 *
4 * Procedures for manipulating DensMap structures.
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 */
18
19 #ifndef lint
20 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/grouter/grouteDens.c,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $";
21 #endif /* lint */
22
23 #include <stdio.h>
24 #include <string.h>
25
26 #include "utils/magic.h"
27 #include "utils/geometry.h"
28 #include "utils/hash.h"
29 #include "utils/heap.h"
30 #include "tiles/tile.h"
31 #include "database/database.h"
32 #include "utils/netlist.h"
33 #include "gcr/gcr.h"
34 #include "router/router.h"
35 #include "grouter/grouter.h"
36 #include "utils/signals.h"
37 #include "textio/textio.h"
38 #include "utils/malloc.h"
39 #include "utils/styles.h"
40 #include "debug/debug.h"
41
42 /*
43 * ----------------------------------------------------------------------------
44 *
45 * glDensAdjust --
46 *
47 * Increment the density in the channel as a result of routing the segment
48 * from p1 to p2 through the channel common to both. The segment is
49 * identified by the NetId 'netid'. The density map 'dens' is incremented
50 * for each column/row of the channel through which the segment must run,
51 * where the segment doesn't already exist.
52 *
53 * Results:
54 * Returns TRUE if any more of srcPin->gcr_ch became filled
55 * up to maximum density.
56 *
57 * Side effects:
58 * Modifies the local and possibly the maximum densities in *dens.
59 *
60 * ----------------------------------------------------------------------------
61 */
62
63 bool
glDensAdjust(dens,srcPin,dstPin,netid)64 glDensAdjust(dens, srcPin, dstPin, netid)
65 DensMap dens[2];
66 GCRPin *srcPin, *dstPin;
67 NetId netid;
68 {
69 int minprow, maxprow, minpcol, maxpcol, mincol, maxcol, minrow, maxrow;
70 int maxvd, maxhd, col, row, nrow, ncol;
71 GCRChannel *ch = srcPin->gcr_ch;
72 GCRPin *p1, *p2;
73 short *dvec;
74 bool densChanged;
75
76 /* Sanity checking */
77 ASSERT(srcPin && dstPin, "glDensAdjust");
78 ASSERT(srcPin->gcr_ch == dstPin->gcr_ch, "glDensAdjust");
79
80 if (DebugIsSet(glDebugID, glDebGreedy))
81 return FALSE;
82
83 /*
84 * Find the first and last column where this net (netId)
85 * is previously present in the channel, and also the first
86 * and last row.
87 */
88 nrow = dens[CZ_ROW].dm_size - 1;
89 ncol = dens[CZ_COL].dm_size - 1;
90 maxprow = 0, minprow = dens[CZ_ROW].dm_size;
91 maxpcol = 0, minpcol = dens[CZ_COL].dm_size;
92
93 /* Rows */
94 p1 = &ch->gcr_lPins[1], p2 = &ch->gcr_rPins[1];
95 for (row = 1; row < dens[CZ_ROW].dm_size; row++, p1++, p2++)
96 {
97 if (SAMENET(p1, netid.netid_net, netid.netid_seg))
98 {
99 minpcol = 1;
100 minprow = MIN(row, minprow);
101 maxprow = MAX(row, maxprow);
102 }
103 if (SAMENET(p2, netid.netid_net, netid.netid_seg))
104 {
105 maxpcol = ncol;
106 minprow = MIN(row, minprow);
107 maxprow = MAX(row, maxprow);
108 }
109 }
110
111 /* Columns */
112 p1 = &ch->gcr_bPins[1], p2 = &ch->gcr_tPins[1];
113 for (col = 1; col < dens[CZ_COL].dm_size; col++, p1++, p2++)
114 {
115 if (SAMENET(p1, netid.netid_net, netid.netid_seg))
116 {
117 minprow = 1;
118 minpcol = MIN(col, minpcol);
119 maxpcol = MAX(col, maxpcol);
120 }
121 if (SAMENET(p2, netid.netid_net, netid.netid_seg))
122 {
123 maxprow = nrow;
124 minpcol = MIN(col, minpcol);
125 maxpcol = MAX(col, maxpcol);
126 }
127 }
128
129 /*
130 * Increment the density over any range where
131 * this net was not already present but is now.
132 */
133 p1 = srcPin;
134 p2 = dstPin;
135
136 #define CLIPTORANGE(x, min, max) \
137 ((x) < (min) ? (min) : ((x) > (max) ? (max) : (x)))
138
139 densChanged = FALSE;
140 minrow = MIN(p1->gcr_y, p2->gcr_y);
141 minrow = CLIPTORANGE(minrow, 1, nrow);
142 maxrow = MAX(p1->gcr_y, p2->gcr_y);
143 maxrow = CLIPTORANGE(maxrow, 1, nrow);
144 maxvd = dens[CZ_ROW].dm_max;
145 dvec = dens[CZ_ROW].dm_value;
146 for (row = minrow; row <= maxrow; row++)
147 if (row < minprow || row > maxprow)
148 if (++dvec[row] >= maxvd)
149 {
150 densChanged = TRUE;
151 maxvd = dvec[row];
152 }
153 dens[CZ_ROW].dm_max = maxvd;
154
155 mincol = MIN(p1->gcr_x, p2->gcr_x);
156 mincol = CLIPTORANGE(mincol, 1, ncol);
157 maxcol = MAX(p1->gcr_x, p2->gcr_x);
158 maxcol = CLIPTORANGE(maxcol, 1, ncol);
159 maxhd = dens[CZ_COL].dm_max;
160 dvec = dens[CZ_COL].dm_value;
161 for (col = mincol; col <= maxcol; col++)
162 if (col < minpcol || col > maxpcol)
163 if (++dvec[col] >= maxhd)
164 {
165 maxhd = dvec[col];
166 densChanged = TRUE;
167 }
168 dens[CZ_COL].dm_max = maxhd;
169 return densChanged;
170 }
171
172 /*
173 * ----------------------------------------------------------------------------
174 *
175 * glDMAlloc --
176 *
177 * Allocate and zero the dm_value array for the DensMap structure 'dm'.
178 * This array will have size 'top+1'. The maximum capacity is 'cap'.
179 *
180 * Results:
181 * None.
182 *
183 * Side effects:
184 * See above.
185 *
186 * ----------------------------------------------------------------------------
187 */
188
189 void
glDMAlloc(dm,top,cap)190 glDMAlloc(dm, top, cap)
191 DensMap *dm;
192 int top, cap;
193 {
194 dm->dm_max = 0;
195 dm->dm_size = top + 1;
196 dm->dm_cap = cap;
197 dm->dm_value = (short *) callocMagic((unsigned) (sizeof (short) * dm->dm_size));
198 }
199
200 /*
201 * ----------------------------------------------------------------------------
202 *
203 * glDMCopy --
204 *
205 * Copy the DensMap structure *dm1 to *dm2, copying the dm_value array
206 * as well. (The two DensMap structures better have the same size;
207 * also, dm2->dm_value must already be allocated).
208 *
209 * Results:
210 * None.
211 *
212 * Side effects:
213 * See above.
214 *
215 * ----------------------------------------------------------------------------
216 */
217
218 void
glDMCopy(dm1,dm2)219 glDMCopy(dm1, dm2)
220 DensMap *dm1, *dm2;
221 {
222 dm2->dm_max = dm1->dm_max;
223 ASSERT(dm2->dm_size == dm1->dm_size, "glDMCopy");
224 ASSERT(dm2->dm_cap == dm1->dm_cap, "glDMCopy");
225 bcopy((char *) dm1->dm_value, (char *) dm2->dm_value,
226 sizeof (short) * dm1->dm_size);
227 }
228
229 /*
230 * ----------------------------------------------------------------------------
231 *
232 * glDMFree --
233 *
234 * Free the memory allocated to dm->dm_value.
235 *
236 * Results:
237 * None.
238 *
239 * Side effects:
240 * Frees memory.
241 *
242 * ----------------------------------------------------------------------------
243 */
244
245 void
glDMFree(dm)246 glDMFree(dm)
247 DensMap *dm;
248 {
249 freeMagic((char *) dm->dm_value);
250 }
251
252 /*
253 * ----------------------------------------------------------------------------
254 *
255 * glDMMaxInRange --
256 *
257 * Return the maximum value of the DensMap in the inclusive range lo .. hi.
258 *
259 * Results:
260 * See above.
261 *
262 * Side effects:
263 * None.
264 *
265 * ----------------------------------------------------------------------------
266 */
267
268 int
glDMMaxInRange(dm,lo,hi)269 glDMMaxInRange(dm, lo, hi)
270 DensMap *dm;
271 int lo, hi;
272 {
273 short *dval = dm->dm_value;
274 int n, max;
275
276 /* Sanity checks */
277 ASSERT(lo > 0, "glDMMaxInRange");
278 ASSERT(hi < dm->dm_size, "glDMMaxInRange");
279
280 max = 0;
281 for (n = lo; n <= hi; n++)
282 if (dval[n] > max)
283 max = dval[n];
284
285 return (max);
286 }
287
288 /*
289 * ----------------------------------------------------------------------------
290 *
291 * glDensInit --
292 *
293 * Initialize the DensMap pair dmap[] from the already-initialized
294 * density map in the GCRChannel *ch. (The use of two separate kinds
295 * of density maps is a temporary measure that will go away when the
296 * integration of the new routing code is complete).
297 *
298 * Results:
299 * None.
300 *
301 * Side effects:
302 * See above.
303 *
304 * ----------------------------------------------------------------------------
305 */
306
307 void
glDensInit(dmap,ch)308 glDensInit(dmap, ch)
309 DensMap dmap[2];
310 GCRChannel *ch;
311 {
312 short *dSrc, *dDst, *dEnd;
313
314 dmap[CZ_COL].dm_max = ch->gcr_dMaxByCol;
315 dmap[CZ_ROW].dm_max = ch->gcr_dMaxByRow;
316 dSrc = ch->gcr_dRowsByCol;
317 dDst = dmap[CZ_COL].dm_value;
318 dEnd = &dmap[CZ_COL].dm_value[dmap[CZ_COL].dm_size];
319 while (dDst < dEnd)
320 *dDst++ = *dSrc++;
321
322 dSrc = ch->gcr_dColsByRow;
323 dDst = dmap[CZ_ROW].dm_value;
324 dEnd = &dmap[CZ_ROW].dm_value[dmap[CZ_ROW].dm_size];
325 while (dDst < dEnd)
326 *dDst++ = *dSrc++;
327 }
328