1 /*
2 * Copyright (C) 1988-1991 Yale University
3 *
4 * This work is distributed in the hope that it will be useful; you can
5 * redistribute it and/or modify it under the terms of the
6 * GNU General Public License as published by the Free Software Foundation;
7 * either version 2 of the License,
8 * or any later version, on the following conditions:
9 *
10 * (a) YALE MAKES NO, AND EXPRESSLY DISCLAIMS
11 * ALL, REPRESENTATIONS OR WARRANTIES THAT THE MANUFACTURE, USE, PRACTICE,
12 * SALE OR
13 * OTHER DISPOSAL OF THE SOFTWARE DOES NOT OR WILL NOT INFRINGE UPON ANY
14 * PATENT OR
15 * OTHER RIGHTS NOT VESTED IN YALE.
16 *
17 * (b) YALE MAKES NO, AND EXPRESSLY DISCLAIMS ALL, REPRESENTATIONS AND
18 * WARRANTIES
19 * WHATSOEVER WITH RESPECT TO THE SOFTWARE, EITHER EXPRESS OR IMPLIED,
20 * INCLUDING,
21 * BUT NOT LIMITED TO, WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
22 * PARTICULAR
23 * PURPOSE.
24 *
25 * (c) LICENSEE SHALL MAKE NO STATEMENTS, REPRESENTATION OR WARRANTIES
26 * WHATSOEVER TO
27 * ANY THIRD PARTIES THAT ARE INCONSISTENT WITH THE DISCLAIMERS BY YALE IN
28 * ARTICLE
29 * (a) AND (b) above.
30 *
31 * (d) IN NO EVENT SHALL YALE, OR ITS TRUSTEES, DIRECTORS, OFFICERS,
32 * EMPLOYEES AND
33 * AFFILIATES BE LIABLE FOR DAMAGES OF ANY KIND, INCLUDING ECONOMIC DAMAGE OR
34 * INJURY TO PROPERTY AND LOST PROFITS, REGARDLESS OF WHETHER YALE SHALL BE
35 * ADVISED, SHALL HAVE OTHER REASON TO KNOW, OR IN FACT SHALL KNOW OF THE
36 * POSSIBILITY OF THE FOREGOING.
37 *
38 */
39
40 /* -----------------------------------------------------------------
41 FILE: compactor.c
42 DESCRIPTION:This file contains main control for compaction algorithm.
43 CONTENTS:
44 DATE: Apr 8, 1988
45 REVISIONS: Nov 5, 1988 - free violations and modified position of
46 sources and sinks.
47 Dec 4, 1988 - corrected error in where to get data.
48 Jan 15, 1989 - fixed constraint problem for softcells
49 by saving contents of tilebox and set orig_ fields
50 correctly for compaction cycle for softcells.
51 Jan 25, 1989 - removed incorrect force of box size to
52 block area and added \n for new message macro.
53 Mar 11, 1989 - added graphics conditional compile and
54 commented out compactor state dump.
55 Mar 30, 1989 - changed tile datastructure.
56 Apr 17, 1989 - changed compactor to independent program.
57 Apr 30, 1989 - changed compaction algorithm so it is both
58 easier to read and more robust.
59 May 3, 1989 - changed to Y prefixes.
60 Sun Nov 4 13:18:12 EST 1990 - added set_draw_critical
61 for making a pretty picture.
62 Fri Mar 29 14:25:29 EST 1991 - now save the critical
63 path.
64 ----------------------------------------------------------------- */
65
66 #include <compact.h>
67 #include <yalecad/debug.h>
68
69 void freeGraph( INT direction );
70
remove_violations()71 void remove_violations()
72 {
73 ERRORPTR violations, saveError, buildXGraph(), buildYGraph() ;
74
75 /* ---------------------------------------------------------------
76 VIOLATION REMOVAL CYCLE - iterate till all violations are removed
77 */
78 while( TRUE ){
79 buildXGraph() ;
80 violations = buildYGraph() ;
81 if( violations ){ /* violations unresolved */
82 /* move strategy is to resolve overlap violations */
83 moveStrategy( violations ) ;
84 } else {
85 break ; /* exit loop */
86 }
87
88 D( "mc_compact/remove_violations", MEMUSAGE ) ;
89
90 /* G( ) is NOGRAPHICS conditional compile */
91 G( if( graphicsG && TWinterupt() ) ){
92 G( process_graphics() ) ;
93 }
94 G( draw_the_data() ) ;
95
96 freeGraph(XFORWARD ) ;
97 freeGraph(XBACKWARD ) ;
98 freeGraph(YFORWARD ) ;
99 freeGraph(YBACKWARD ) ;
100
101 D( "mc_compact/remove_violations", MEMUSAGE ) ;
102
103 } /* ----- END VIOLATION REMOVAL CYCLE ------ */
104
105 freeGraph(XFORWARD ) ;
106 freeGraph(XBACKWARD ) ;
107 freeGraph(YFORWARD ) ;
108 freeGraph(YBACKWARD ) ;
109 G( draw_the_data() ) ;
110
111 } /* end remove_violations */
112
113
compact()114 void compact()
115 {
116 INT length ; /* length of longest path */
117 INT count ; /* number of compaction cycles */
118 ERRORPTR violations, saveError, buildXGraph(), buildYGraph() ;
119 BOOL compactNotSat ; /* compaction criteria is not satisfied */
120 BOOL xNotY_toggle ; /* toggle between x and y compaction. */
121
122 /* ---------------------------------------------------------------
123 COMPACTION CYCLE - iterate till all violations are removed
124 and compaction criteria is satisfied.
125 */
126 count = 0 ;
127 compactNotSat = TRUE ;
128 xNotY_toggle = TRUE ;
129 if(!(debugG)) fprintf( stderr,"\nCompaction Begins...\n" ) ;
130 while( compactNotSat ){
131 /* first build x and y graphs */
132 buildXGraph() ;
133 violations = buildYGraph() ;
134 if( violations ){ /* violations unresolved */
135 /* move strategy is to resolve overlap violations */
136 G( set_draw_critical( FALSE ) ) ;
137 moveStrategy( violations ) ;
138 fprintf( stderr,"V " ) ;
139 D( "mc_compact/viofail",
140 YexitPgm( PGMFAIL ) ;
141 ) ;
142 if( debugG ) {
143 fprintf( stderr, "\n" ) ;
144 }
145 } else {
146 G( set_draw_critical( TRUE ) ) ;
147 if( xNotY_toggle ){
148 fprintf( stderr,"X " ) ;
149 length = longestxPath( TRUE ) ;
150 /* move strategy is to compact in x direction */
151 move_compactx( length );
152 xNotY_toggle = FALSE ; /* flip toggle */
153 } else {
154 fprintf( stderr,"Y " ) ;
155 length = longestyPath( TRUE ) ;
156 /* move strategy is to compact in y direction */
157 move_compacty( length );
158 xNotY_toggle = TRUE ; /* flip toggle */
159 }
160 compactNotSat = test_area() ;
161 if( debugG) {
162 fprintf( stderr, "\n" ) ;
163 }
164
165 }
166
167 if( (!(debugG)) && (++count % 15) == 0 ){
168 fprintf( stderr, "\n" ) ;
169 }
170
171 D( "mc_compact/compact", MEMUSAGE ) ;
172
173 /* G( ) is NOGRAPHICS conditional compile */
174 G( if( graphicsG && TWinterupt() ) ){
175 G( process_graphics() ) ;
176 }
177 G( draw_the_data() ) ;
178
179 freeGraph(XFORWARD) ;
180 freeGraph(XBACKWARD) ;
181 freeGraph(YFORWARD) ;
182 freeGraph(YBACKWARD) ;
183
184 D( "mc_compact/compact", MEMUSAGE ) ;
185
186 } /* ----- END COMPACTION CYCLE ------ */
187
188 if(!(debugG)){
189 fprintf( stderr, "\n\n" ) ;
190 }
191
192 /* grid the cells */
193 grid_data() ;
194
195 /* make sure we have no violations */
196 remove_violations() ;
197
198 /* show the results */
199 G( draw_the_data() ) ;
200
201 } /* end compact */
202
203
freeGraph(INT direction)204 void freeGraph( INT direction )
205 {
206 INT i ;
207 ECOMPBOXPTR edge , saveEdge ;
208
209 for( i=0 ; i<= last_tileG ; i++ ){
210 switch( direction ){
211 case XFORWARD: edge=xGraphG[i]->xadjF;
212 xGraphG[i]->xadjF = NULL ;
213 break ;
214 case XBACKWARD: edge=xGraphG[i]->xadjB;
215 xGraphG[i]->xadjB = NULL ;
216 break ;
217 case YFORWARD: edge=yGraphG[i]->yadjF;
218 yGraphG[i]->yadjF = NULL ;
219 break ;
220 case YBACKWARD: edge=yGraphG[i]->yadjB;
221 yGraphG[i]->yadjB = NULL ;
222 break ;
223 }
224 /* free all the edges */
225 for( ;edge; ){
226 saveEdge = edge ;
227 edge = edge->next ;
228 Ysafe_free(saveEdge) ;
229 }
230 } /* end for loop */
231 }
232
path(direction)233 INT path(direction)
234 INT direction ;
235 {
236 INT node ;
237 INT source ;
238
239
240 switch( direction ){
241 case XFORWARD : node = numtilesG + 1 ;
242 if( constraintsG ){
243 Ydeck_empty( path_deckG, NIL(VOIDPTR)) ;
244 }
245 D( "mc_compact/path",
246 printf("Longest path in xGraphG-Forward direction:\n" ) ) ;
247 source = 0 ;
248 /* print backwards so list is in correct order columatted */
249 while( node != source ){
250 D( "mc_compact/path",
251 printf("Node:%2d cell:%2d xvalueMin:%4d\n",
252 tileNodeG[node]->node,
253 tileNodeG[node]->cell,
254 tileNodeG[node]->xvalueMin ) ) ;
255 tileNodeG[node]->criticalX = TRUE ;
256 /* update node */
257 node = tileNodeG[node]->pathx ;
258 if( constraintsG && node != source ){
259 Ydeck_push( path_deckG, (VOIDPTR) node ) ;
260 }
261 }
262 return( tileNodeG[numtilesG+1]->xvalueMin ) ;
263 case XBACKWARD: node = 0 ;
264 D( "mc_compact/path",
265 printf("Longest path in xGraphG-Backward direction:\n" ) ) ;
266 source = numtilesG + 1 ;
267 /* print backwards so list is in correct order columatted */
268 while( node != source ){
269 D( "mc_compact/path",
270 printf("Node:%2d cell:%2d xvalueMax:%4d\n",
271 tileNodeG[node]->node,
272 tileNodeG[node]->cell,
273 tileNodeG[node]->xvalueMax ) ) ;
274 /* update node */
275 node = tileNodeG[node]->pathx ;
276 }
277 return( tileNodeG[0]->xvalueMax ) ;
278 case YFORWARD : node = numtilesG + 3 ;
279 if( constraintsG ){
280 Ydeck_empty( path_deckG, NIL(VOIDPTR)) ;
281 }
282 D( "mc_compact/path",
283 printf("Longest path in yGraphG-Forward direction:\n" ) );
284 source = numtilesG + 2 ;
285 /* print backwards so list is in correct order columatted */
286 while( node != source ){
287 D( "mc_compact/path",
288 printf("Node:%2d cell:%2d yvalueMin:%4d\n",
289 tileNodeG[node]->node,
290 tileNodeG[node]->cell,
291 tileNodeG[node]->yvalueMin ) );
292 tileNodeG[node]->criticalY = TRUE ;
293 /* update node */
294 node = tileNodeG[node]->pathy ;
295 if( constraintsG && node != source ){
296 Ydeck_push( path_deckG, (VOIDPTR) node ) ;
297 }
298 }
299 return( tileNodeG[numtilesG+3]->yvalueMin ) ;
300 case YBACKWARD: node = numtilesG + 2 ;
301 D( "mc_compact/path",
302 printf("Longest path in yGraphG-Backward direction:\n" ) ) ;
303 source = numtilesG + 3 ;
304 while( node != source ){
305 D( "mc_compact/path",
306 printf("Node:%2d cell:%2d yvalueMax:%4d\n",
307 tileNodeG[node]->node,
308 tileNodeG[node]->cell,
309 tileNodeG[node]->yvalueMax ) ) ;
310 /* update node */
311 node = tileNodeG[node]->pathy ;
312 }
313 return( tileNodeG[numtilesG+2]->yvalueMax ) ;
314 default:
315 M(ERRMSG,"dpath","invalid direction in graph\n") ;
316 return( 0 ) ;
317 }
318 }
319
cleanupGraph(direction)320 void cleanupGraph( direction )
321 INT direction ;
322 {
323 INT i ;
324 ECOMPBOXPTR edge , match, saveNode ;
325 INT matchNode, sameNode ;
326
327 for( i=0 ; i<= last_tileG ; i++ ){
328 switch( direction ){
329 case XFORWARD: edge=xGraphG[i]->xadjF;
330 sameNode = xGraphG[i]->node ;
331 break ;
332 case XBACKWARD: edge=xGraphG[i]->xadjB;
333 sameNode = xGraphG[i]->node ;
334 break ;
335 case YFORWARD: edge=yGraphG[i]->yadjF;
336 sameNode = yGraphG[i]->node ;
337 break ;
338 case YBACKWARD: edge=yGraphG[i]->yadjB;
339 sameNode = yGraphG[i]->node ;
340 break ;
341 }
342 for( ;edge;edge=edge->next ){
343 matchNode = edge->node ;
344 saveNode = edge ;
345 for(match=edge->next; match ; ){
346 if( match->node == matchNode ){
347
348 D( "mc_compact/cleanupGraph",
349 sprintf( YmsgG,
350 "We discovered redundant edge-N%d -> N%d\n",
351 sameNode, match->node ) ;
352 M(MSG, NULL, YmsgG )
353 ) ;
354
355 /* need to update ancestors */
356 /* the edge in question is sameNode:match->node */
357 switch( direction ){
358 case XFORWARD:
359 tileNodeG[matchNode]->xancestrF-- ;
360 break ;
361 case XBACKWARD:
362 tileNodeG[matchNode]->xancestrB-- ;
363 break ;
364 case YFORWARD:
365 tileNodeG[matchNode]->yancestrF-- ;
366 break ;
367 case YBACKWARD:
368 tileNodeG[matchNode]->yancestrB-- ;
369 break ;
370 }
371
372 ASSERT( edge->constraint == match->constraint,
373 "cleanupGraph",
374 "Redundant edges have mismatching constraints\n");
375
376 /* now delete */
377 saveNode->next = match->next ;
378 Ysafe_free( match ) ;
379
380 /* update loop */
381 match = saveNode->next ;
382
383 } else if( match->node == sameNode){
384 /* a node constrainted to itself delete it. */
385
386 D( "mc_compact/cleanupGraph",
387 sprintf( YmsgG,
388 "We discovered redundant edge-N%d -> N%d\n",
389 sameNode, match->node ) ;
390 M(MSG, NULL, YmsgG )
391 ) ;
392
393 /* need to update ancestors */
394 /* the edge in question is sameNode:match->node */
395 switch( direction ){
396 case XFORWARD:
397 tileNodeG[sameNode]->xancestrF-- ;
398 break ;
399 case XBACKWARD:
400 tileNodeG[sameNode]->xancestrB-- ;
401 break ;
402 case YFORWARD:
403 tileNodeG[sameNode]->yancestrF-- ;
404 break ;
405 case YBACKWARD:
406 tileNodeG[sameNode]->yancestrB-- ;
407 break ;
408 }
409
410 /* now delete */
411 saveNode->next = match->next ;
412 Ysafe_free( match ) ;
413
414 /* update loop */
415 match = saveNode->next ;
416
417 } else {
418 /* edge is OK */
419
420 /* update loop */
421 saveNode = match ;
422 match = match->next ;
423 }
424 }
425 }
426 } /* end for loop */
427 }
428
429 /* find bounding box of tiles */
find_core(l,r,b,t)430 void find_core( l, r, b, t )
431 INT *l, *r, *b, *t ;
432 {
433
434 INT i ;
435 INT expand ;
436 COMPACTPTR tile ;
437
438 blocklG = INT_MAX ;
439 blockbG = INT_MAX ;
440 blockrG = INT_MIN ;
441 blocktG = INT_MIN ;
442
443 for( i=1; i <= numtilesG; i++ ){
444 tile = tileNodeG[i] ;
445 blocklG = MIN( blocklG, tile->l ) ;
446 blockbG = MIN( blockbG, tile->b ) ;
447 blockrG = MAX( blockrG, tile->r ) ;
448 blocktG = MAX( blocktG, tile->t ) ;
449 }
450 expand = (INT) ( 0.25 * (DOUBLE) ABS(blockrG - blocklG) ) ;
451 *l = blocklG -= expand ;
452 *r = blockrG += expand ;
453 expand = (INT) ( 0.25 * (DOUBLE) ABS(blocktG - blockbG) ) ;
454 *b = blockbG -= expand ;
455 *t = blocktG += expand ;
456
457 } /* end find_core */
458