1 /* -*- tab-width: 4 -*-
2 *
3 * Electric(tm) VLSI Design System
4 *
5 * File: sc1place.c
6 * Placement modules for the QUISC Silicon Compiler
7 * Written by: Andrew R. Kostiuk, Queen's University
8 *
9 * Copyright (c) 2000 Static Free Software.
10 *
11 * Electric(tm) is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; either version 2 of the License, or
14 * (at your option) any later version.
15 *
16 * Electric(tm) is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with Electric(tm); see the file COPYING. If not, write to
23 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
24 * Boston, Mass 02111-1307, USA.
25 *
26 * Static Free Software
27 * 4119 Alpine Road
28 * Portola Valley, California 94028
29 * info@staticfreesoft.com
30 */
31
32 #include "config.h"
33 #if SCTOOL
34
35 #include <math.h>
36 #include <setjmp.h>
37 #include "global.h"
38 #include "sc1.h"
39
40 /***** blerbs for showing what placement algorithms is used *****/
41
42 static CHAR *sc_placeblerb[] =
43 {
44 M_("************ QUISC PLACEMENT MODULE - VERSION 1.00"),
45 M_("Cluster Tree Creation:"),
46 M_(" o Maxi-cut Algorithm"),
47 M_(" o Minimum use for best pair choice for equal weight"),
48 M_("Cluster Tree Sorting:"),
49 M_(" o Top-down cluster tree sort"),
50 M_(" o Bottom-up cluster tree sort"),
51 M_("Net Balancing:"),
52 M_(" o Independent routing channels"),
53 M_(" o Cross refencing of trunks to improve speed"),
54 M_(" o Effective calculation of rows in costing"),
55 0
56 } ;
57
58
59 /*************** default values for placement control ***************/
60
61 #define DEFAULT_STATS_FLAG 0 /* do not display statistics */
62 #define DEFAULT_SORT_FLAG 1 /* sort cluster tree */
63 #define DEFAULT_NET_BALANCE_FLAG 0 /* no net balance */
64 #define DEFAULT_NET_BALANCE_LIMIT 2 /* movement limit */
65 #define DEFAULT_VERTICAL_COST 2 /* vertical cost multiplier */
66
67
68 /************************* File variables *************************/
69
70 static SCCLUSTER *sc_gcluster; /* global list of cluster groups */
71 static SCCLUSTERTREE *sc_gcluster_tree; /* global root of cluster tree */
72 static int sc_currentcost; /* cost of current cluster tree */
73
74 static SCPLACECONTROL sc_placecontrol =
75 {
76 DEFAULT_STATS_FLAG,
77 DEFAULT_SORT_FLAG,
78 DEFAULT_NET_BALANCE_FLAG,
79 DEFAULT_NET_BALANCE_LIMIT,
80 DEFAULT_VERTICAL_COST
81 };
82
83 /************************* External variables *************************/
84
85 extern jmp_buf sc_please_stop;
86 extern SCCELL *sc_curcell;
87
88 /* prototypes for local routines */
89 static int Sc_place_set_control(int, CHAR*[]);
90 static void Sc_place_show_control(void);
91 static int Sc_place_create_clusters(SCCLUSTER**, SCCELL*);
92 static void Sc_place_total_cell_size(SCNITREE*, int*, int*, int*);
93 static int Sc_place_create_cluster_tree(SCCLUSTERTREE**, SCCLUSTER*[], int, SCCELL*);
94 static int Sc_place_create_ctree_recurse(SCCLUSTERTREE**, SCCLUSTERTREE*, SCCELL*);
95 static void Sc_place_ctree_add_parents(SCCLUSTERTREE*, SCCLUSTERTREE*);
96 static int Sc_place_ctree_num_connects(SCCLUSTERTREE*, SCCLCONNECT**, SCCELL*);
97 static void Sc_clear_ext_nodes(SCEXTNODE*);
98 static void Sc_set_ext_nodes_by_ctree(SCCLUSTERTREE*, int);
99 static int Sc_count_ext_nodes(SCCLUSTERTREE*, int);
100 static int Sc_place_ctree_sort_connects(SCCLCONNECT*, SCCLCONNECT**);
101 static int Sc_place_ctree_pair(SCCLUSTERTREE*, SCCLCONNECT*, SCCLUSTERTREE**);
102 static int Sc_place_best_pair(SCCLCONNECT*, SCCLCONNECT**);
103 static void Sc_place_print_cluster_tree(SCCLUSTERTREE*, int);
104 static int Sc_place_sort_cluster_tree(SCCLUSTERTREE*, SCCELL*);
105 static int Sc_place_sort_swapper_top_down(SCCLUSTERTREE*, SCNBTRUNK*, SCCELL*);
106 static int Sc_place_sort_swapper_bottom_up(SCCLUSTERTREE*, SCNBTRUNK*, SCCELL*);
107 static void Sc_place_switch_subtrees(SCCLUSTERTREE*);
108 static int Sc_place_cost_cluster_tree(SCCLUSTERTREE*, SCNBTRUNK*, SCCELL*);
109 static void Sc_place_cost_cluster_tree_2(SCCLUSTERTREE*, SCNBTRUNK*, int*);
110 static int Sc_place_create_placelist(SCCLUSTERTREE*, SCCELL*);
111 static int Sc_place_add_cluster_to_row(SCCLUSTER*, SCROWLIST*, SCPLACE*);
112 static void Sc_free_cluster_tree(SCCLUSTERTREE*);
113 static int Sc_place_net_balance(SCROWLIST*, SCCELL*);
114 static int Sc_place_nb_all_cells(SCCELL*, SCCHANNEL*);
115 static void Sc_place_nb_do_cell(SCNBPLACE*, SCCHANNEL*, SCCELL*);
116 static int Sc_place_nb_cost(SCROWLIST*, SCCHANNEL*, SCCELL*);
117 static void Sc_place_nb_remove(SCNBPLACE*, SCROWLIST*);
118 static void Sc_place_nb_insert_before(SCNBPLACE*, SCNBPLACE*, SCROWLIST*);
119 static void Sc_place_nb_insert_after(SCNBPLACE*, SCNBPLACE*, SCROWLIST*);
120 static void Sc_place_nb_rebalance_rows(SCROWLIST*, SCPLACE*);
121 static void Sc_place_number_placement(SCROWLIST*);
122 static void Sc_place_show_placement(SCROWLIST*);
123 static void Sc_place_reorder_rows(SCROWLIST*);
124
125 /***********************************************************************
126 Module: Sc_place
127 ------------------------------------------------------------------------
128 Description:
129 Place the nodes in the current cell in optimal position for routing
130 based upon number of connections between cells.
131 ------------------------------------------------------------------------
132 Calling Sequence: err = Sc_place(count, pars);
133
134 Name Type Description
135 ---- ---- -----------
136 count int Number of parameters.
137 pars *char[] Array of pointers to parameters.
138 err int Returned error code, 0 = no error.
139 ------------------------------------------------------------------------
140 */
141
Sc_place(int count,CHAR * pars[])142 int Sc_place(int count, CHAR *pars[])
143 {
144 int err, l, numcl, i;
145 SCPLACE *place;
146 SCROWLIST *row;
147 SCCLUSTER *cl, **cllist;
148
149 /* parameter check */
150 if (count)
151 {
152 l = estrlen(pars[0]);
153 l = maxi(l, 2);
154 if (namesamen(pars[0], x_("set-control"), l) == 0)
155 return(Sc_place_set_control(count - 1, &pars[1]));
156 if (namesamen(pars[0], x_("show-control"), l) == 0)
157 {
158 Sc_place_show_control();
159 return(SC_NOERROR);
160 }
161 return(Sc_seterrmsg(SC_PLACE_XCMD, pars[0]));
162 }
163
164 /* check to see if currently working in a cell */
165 if (sc_curcell == NULL)
166 return(Sc_seterrmsg(SC_NOCELL));
167
168 /* create placement structure */
169 (void)Sc_free_placement(sc_curcell->placement);
170 place = (SCPLACE *)emalloc(sizeof(SCPLACE), sc_tool->cluster);
171 if (place == 0)
172 return(Sc_seterrmsg(SC_NOMEMORY));
173 sc_curcell->placement = place;
174 place->num_inst = 0;
175 place->size_inst = 0;
176 place->avg_size = 0;
177 place->avg_height = 0;
178 place->num_rows = ScGetParameter(SC_PARAM_PLACE_NUM_ROWS);
179 place->size_rows = 0;
180 place->rows = NULL;
181 place->plist = NULL;
182 place->endlist = NULL;
183
184 /* DO PLACEMENT */
185 for (i = 0; sc_placeblerb[i]; i++)
186 ttyputverbose(TRANSLATE(sc_placeblerb[i]));
187 if (sc_placecontrol.stats_flag)
188 Sc_place_show_control();
189 ttyputmsg(_("Starting PLACEMENT..."));
190 (void)Sc_cpu_time(TIME_RESET);
191
192 /* create clusters of cells */
193 sc_gcluster = NULL;
194 if ((err = Sc_place_create_clusters(&sc_gcluster, sc_curcell)))
195 return(err);
196
197 if (sc_gcluster == NULL)
198 {
199 ttyputmsg(_("ERROR - No cells found to place. Aborting."));
200 return(SC_NOERROR);
201 }
202
203 /* place clusters in a binary group tree */
204 sc_gcluster_tree = NULL;
205 numcl = 0;
206 for (cl = sc_gcluster; cl; cl = cl->next)
207 numcl++;
208 cllist = (SCCLUSTER **)emalloc(sizeof(SCCLUSTER *) * (numcl + 1), sc_tool->cluster);
209 if (cllist == NULL)
210 return(Sc_seterrmsg(SC_NOMEMORY));
211 i = 0;
212 for (cl = sc_gcluster; cl; cl = cl->next)
213 cllist[i++] = cl;
214 cllist[i] = NULL;
215 if ((err = Sc_place_create_cluster_tree(&sc_gcluster_tree, cllist, numcl,
216 sc_curcell)))
217 return(err);
218 efree((CHAR *)cllist);
219 ttyputverbose(M_(" Time to create Cluster Tree = %s."),
220 Sc_cpu_time(TIME_REL));
221 if (sc_placecontrol.stats_flag)
222 {
223 ttyputmsg(M_("************ Initial placement of Clusters"));
224 Sc_place_print_cluster_tree(sc_gcluster_tree, 0);
225 }
226 place->size_rows = place->size_inst / place->num_rows;
227
228 /* place clusters in list by sorting groups */
229 if (sc_placecontrol.sort_flag)
230 {
231 if ((err = Sc_place_sort_cluster_tree(sc_gcluster_tree, sc_curcell)))
232 return(err);
233 if (sc_placecontrol.stats_flag)
234 {
235 ttyputmsg(M_("************ Placement of Clusters after Sorting"));
236 Sc_place_print_cluster_tree(sc_gcluster_tree, 0);
237 }
238 }
239
240 /* create first row structure */
241 row = (SCROWLIST *)emalloc(sizeof(SCROWLIST), sc_tool->cluster);
242 if (row == 0)
243 return(Sc_seterrmsg(SC_NOMEMORY));
244 row->start = NULL;
245 row->end = NULL;
246 row->row_num = 0;
247 row->row_size = 0;
248 row->next = NULL;
249 row->last = NULL;
250 sc_curcell->placement->rows = row;
251
252 /* create cell placement list from sorted cluster list */
253 if ((err = Sc_place_create_placelist(sc_gcluster_tree, sc_curcell)))
254 return(err);
255
256 /* number placement */
257 Sc_place_number_placement(sc_curcell->placement->rows);
258 if (sc_placecontrol.stats_flag)
259 {
260 ttyputmsg(M_("************ Placement before Net Balancing"));
261 Sc_place_show_placement(sc_curcell->placement->rows);
262 }
263 Sc_free_cluster_tree(sc_gcluster_tree);
264
265 /* do net balance algorithm */
266 if (sc_placecontrol.net_balance_flag)
267 {
268 if ((err = Sc_place_net_balance(sc_curcell->placement->rows,
269 sc_curcell)))
270 return(err);
271 ttyputmsg(M_(" Time to do Net Balancing = %s."),
272 Sc_cpu_time(TIME_REL));
273 if (sc_placecontrol.stats_flag)
274 {
275 ttyputmsg(M_("************ Placement after Net Balancing"));
276 Sc_place_show_placement(sc_curcell->placement->rows);
277 }
278 }
279
280 /* print process time for placement */
281 Sc_place_reorder_rows(sc_curcell->placement->rows);
282 ttyputmsg(_("Done (time = %s)"), Sc_cpu_time(TIME_ABS));
283
284 return(SC_NOERROR);
285 }
286
287 /***********************************************************************
288 Module: Sc_place_set_control
289 ------------------------------------------------------------------------
290 Description:
291 Set the placement control structure values.
292 ------------------------------------------------------------------------
293 Calling Sequence: err = Sc_place_set_control(count, pars);
294
295 Name Type Description
296 ---- ---- -----------
297 count int Number of parameters.
298 pars *char[] Array of pointers to parameters.
299 err int Returned error code, 0 = no error.
300 ------------------------------------------------------------------------
301 */
302
Sc_place_set_control(int count,CHAR * pars[])303 int Sc_place_set_control(int count, CHAR *pars[])
304 {
305 int numcmd, l, n;
306
307 if (count)
308 {
309 for (numcmd = 0; numcmd < count; numcmd++)
310 {
311 l = estrlen(pars[numcmd]);
312 n = maxi(l, 2);
313 if (namesamen(pars[numcmd], x_("sort"), n) == 0)
314 {
315 sc_placecontrol.sort_flag = TRUE;
316 continue;
317 }
318 if (namesamen(pars[numcmd], x_("rows"), n) == 0)
319 {
320 numcmd++;
321 if (numcmd < count)
322 ScSetParameter(SC_PARAM_PLACE_NUM_ROWS, eatoi(pars[numcmd]));
323 continue;
324 }
325
326 if (namesamen(pars[numcmd], x_("net-balance"), n) == 0)
327 {
328 sc_placecontrol.net_balance_flag = TRUE;
329 continue;
330 }
331 if (namesamen(pars[numcmd], x_("limit-net-balance"), n) == 0)
332 {
333 numcmd++;
334 if (numcmd < count)
335 sc_placecontrol.net_balance_limit = eatoi(pars[numcmd]);
336 continue;
337 }
338 if (namesamen(pars[numcmd], x_("default"), n) == 0)
339 {
340 sc_placecontrol.stats_flag = DEFAULT_STATS_FLAG;
341 sc_placecontrol.sort_flag = DEFAULT_SORT_FLAG;
342 ScSetParameter(SC_PARAM_PLACE_NUM_ROWS, DEFAULT_NUM_OF_ROWS);
343 sc_placecontrol.net_balance_flag = DEFAULT_NET_BALANCE_FLAG;
344 sc_placecontrol.net_balance_limit = DEFAULT_NET_BALANCE_LIMIT;
345 sc_placecontrol.vertical_cost = DEFAULT_VERTICAL_COST;
346 continue;
347 }
348 n = maxi(l, 4);
349 if (namesamen(pars[numcmd], x_("verbose"), n) == 0)
350 {
351 sc_placecontrol.stats_flag = TRUE;
352 continue;
353 }
354 if (namesamen(pars[numcmd], x_("vertical-cost"), n) == 0)
355 {
356 numcmd++;
357 if (numcmd < count)
358 sc_placecontrol.vertical_cost = eatoi(pars[numcmd]);
359 continue;
360 }
361 n = maxi(l, 5);
362 if (namesamen(pars[numcmd], x_("no-verbose"), n) == 0)
363 {
364 sc_placecontrol.stats_flag = FALSE;
365 continue;
366 }
367 if (namesamen(pars[numcmd], x_("no-sort"), n) == 0)
368 {
369 sc_placecontrol.sort_flag = FALSE;
370 continue;
371 }
372 if (namesamen(pars[numcmd], x_("no-net-balance"), n) == 0)
373 {
374 sc_placecontrol.net_balance_flag = FALSE;
375 continue;
376 }
377 return(Sc_seterrmsg(SC_PLACE_SET_XCMD, pars[numcmd]));
378 }
379 } else
380 {
381 return(Sc_seterrmsg(SC_PLACE_SET_NOCMD));
382 }
383
384 Sc_place_show_control();
385 return(SC_NOERROR);
386 }
387
388 /***********************************************************************
389 Module: Sc_place_show_control
390 ------------------------------------------------------------------------
391 Description:
392 Print the placement control structure values.
393 ------------------------------------------------------------------------
394 Calling Sequence: Sc_place_show_control();
395 ------------------------------------------------------------------------
396 */
397
Sc_place_show_control(void)398 void Sc_place_show_control(void)
399 {
400 CHAR *str1;
401
402 ttyputverbose(M_("************ PLACEMENT CONTROL STRUCTURE"));
403 if (sc_placecontrol.stats_flag)
404 {
405 str1 = M_("TRUE");
406 } else
407 {
408 str1 = M_("FALSE");
409 }
410 ttyputverbose(M_("Print statistics = %-s"), str1);
411 if (sc_placecontrol.sort_flag)
412 {
413 str1 = M_("TRUE");
414 } else
415 {
416 str1 = M_("FALSE");
417 }
418 ttyputverbose(M_("Sort cluster tree = %-s"), str1);
419 ttyputverbose(M_("Number of rows = %d"), ScGetParameter(SC_PARAM_PLACE_NUM_ROWS));
420 if (sc_placecontrol.net_balance_flag)
421 {
422 str1 = M_("TRUE");
423 } else
424 {
425 str1 = M_("FALSE");
426 }
427 ttyputverbose(M_("Net balancing = %-s"), str1);
428 ttyputverbose(M_("Net balace limit = %d"),
429 sc_placecontrol.net_balance_limit);
430 ttyputverbose(M_("Vertical cost X = %d"),
431 sc_placecontrol.vertical_cost);
432 }
433
434 /***********************************************************************
435 Module: Sc_place_create_clusters
436 ------------------------------------------------------------------------
437 Description:
438 Create "clusters" of cells of size one.
439 ------------------------------------------------------------------------
440 Calling Sequence: err = Sc_place_create_clusters(clusters, cell);
441
442 Name Type Description
443 ---- ---- -----------
444 clusters **SCCLUSTER Address of where to write start of list.
445 cell *SCCELL Pointer to complex cell.
446 err int Returned error code, 0 = no error.
447 ------------------------------------------------------------------------
448 */
449
Sc_place_create_clusters(SCCLUSTER ** clusters,SCCELL * cell)450 int Sc_place_create_clusters(SCCLUSTER **clusters, SCCELL *cell)
451 {
452 int num, size, height;
453 int i, avg_size, avg_height, warn;
454 SCCLUSTER *cluster, *clusterlist;
455 SCNITREE *node;
456
457 /* find total 'size' and number of all the cells */
458 size = 0; num = 0;
459 Sc_place_total_cell_size(cell->nilist, &num, &size, &height);
460 if (!num)
461 {
462 ttyputmsg(_("WARNING - No leaf cells found for placement."));
463 return(SC_NOERROR);
464 }
465 avg_size = size / num;
466 avg_height = height / num;
467 if (sc_placecontrol.stats_flag)
468 {
469 ttyputmsg(M_("************ Cell Statistics"));
470 ttyputmsg(M_(" Number of cells = %d"), num);
471 ttyputmsg(M_(" Total length = %d"), size);
472 ttyputmsg(M_(" Average size of cells = %d"), avg_size);
473 ttyputmsg(M_(" Average height of cells = %d"), avg_height);
474 }
475 cell->placement->num_inst = num;
476 cell->placement->size_inst = size;
477 cell->placement->avg_size = avg_size;
478 cell->placement->avg_height = avg_height;
479
480 /* create cluster list */
481 i = 0;
482 clusterlist = NULL;
483 warn = FALSE;
484 for (node = cell->nilist; node; node = node->next)
485 {
486 if (node->type != SCLEAFCELL)
487 {
488 if (node->type == SCCOMPLEXCELL)
489 warn = TRUE;
490 continue;
491 }
492 cluster = (SCCLUSTER *)emalloc(sizeof(SCCLUSTER), sc_tool->cluster);
493 if (cluster == 0)
494 return(Sc_seterrmsg(SC_NOMEMORY));
495 cluster->node = node;
496 cluster->size = node->size;
497 cluster->number = i++;
498 cluster->last = NULL;
499 cluster->next = clusterlist;
500 if (clusterlist)
501 clusterlist->last = cluster;
502 clusterlist = cluster;
503 }
504 if (warn)
505 {
506 ttyputmsg(_("WARNING - At least one complex cell found during Create_Clusters."));
507 ttyputmsg(_(" - Probable cause: Forgot to do 'PULL' command."));
508 }
509
510 *clusters = clusterlist;
511 return(SC_NOERROR);
512 }
513
514 /***********************************************************************
515 Module: Sc_place_total_cell_size
516 ------------------------------------------------------------------------
517 Description:
518 Determine the number of cells and total linear size of cells.
519 ------------------------------------------------------------------------
520 Calling Sequence: Sc_place_tottal_cell_size(ilist, num, width, height);
521
522 Name Type Description
523 ---- ---- -----------
524 ilist *SCNITREE Pointer to start of instance list.
525 num *int Address to write number of cells.
526 width *int Address to write total width of cells.
527 height *int address to write total height of cells.
528 ------------------------------------------------------------------------
529 */
530
Sc_place_total_cell_size(SCNITREE * ilist,int * num,int * width,int * height)531 void Sc_place_total_cell_size(SCNITREE *ilist, int *num, int *width, int *height)
532 {
533 *num = 0;
534 *width = 0;
535 *height = 0;
536 for ( ; ilist; ilist = ilist->next)
537 {
538 if (ilist->type == SCLEAFCELL)
539 {
540 (*num)++;
541 *width += ilist->size;
542 *height += Sc_leaf_cell_ysize(ilist->np);
543 }
544 }
545 return;
546 }
547
548 /***********************************************************************
549 Module: Sc_place_create_cluster_tree
550 ------------------------------------------------------------------------
551 Description:
552 Recursively create the cluster tree from a group of clusters. At
553 each "node" in the tree, the goal is to pair groups of clusters
554 which are strongly connected together.
555 ------------------------------------------------------------------------
556 Calling Sequence: err = Sc_place_create_cluster_tree(ctree, clusters, size,
557 cell);
558
559 Name Type Description
560 ---- ---- -----------
561 ctree **SCCLUSTERTREE Address of pointer to cluster tree node.
562 clusters *SCCLUSTER[] Array of pointer to the clusters.
563 size int Size of array (i.e. number of clusters).
564 cell *SCCELL Pointer to cell being placed.
565 err int Returned error code, 0 = no error.
566 ------------------------------------------------------------------------
567 */
568
Sc_place_create_cluster_tree(SCCLUSTERTREE ** ctree,SCCLUSTER * clusters[],int size,SCCELL * cell)569 int Sc_place_create_cluster_tree(SCCLUSTERTREE **ctree, SCCLUSTER *clusters[],
570 int size, SCCELL *cell)
571 {
572 int i, err;
573 SCCLUSTERTREE *node, *nstart;
574
575 /* create a cluster tree node for each cluster */
576 nstart = NULL;
577 for (i = 0; i < size; i++)
578 {
579 node = (SCCLUSTERTREE *)emalloc(sizeof(SCCLUSTERTREE), sc_tool->cluster);
580 if (node == 0)
581 {
582 return(Sc_seterrmsg(SC_NOMEMORY));
583 }
584 node->cluster = clusters[i];
585 node->parent = NULL;
586 node->next = nstart;
587 nstart = node;
588 node->lptr = NULL;
589 node->rptr = NULL;
590 }
591
592 /* recursively create cluster tree */
593 if ((err = Sc_place_create_ctree_recurse(ctree, nstart, cell)))
594 return(err);
595 Sc_place_ctree_add_parents(*ctree, (SCCLUSTERTREE *)NULL);
596
597 return(SC_NOERROR);
598 }
599
600 /***********************************************************************
601 Module: Sc_place_create_ctree_recurse
602 ------------------------------------------------------------------------
603 Description:
604 Recursively create the cluster tree from the bottom up by pairing
605 strongly connected tree nodes together. When only one tree node
606 exists, this is the root and can be written to the indicated
607 address.
608 ------------------------------------------------------------------------
609 Calling Sequence: err = Sc_place_create_ctree_recurse(aroot, nodes, cell);
610
611 Name Type Description
612 ---- ---- -----------
613 aroot **SCCLUSTERTREE Address of where to write the tree root.
614 nodes *SCCLUSTERTREE Pointer to start of tree nodes.
615 cell *SCCELL Pointer to parent cell.
616 err int Returned error code, 0 = no error.
617 ------------------------------------------------------------------------
618 */
619
Sc_place_create_ctree_recurse(SCCLUSTERTREE ** aroot,SCCLUSTERTREE * nodes,SCCELL * cell)620 int Sc_place_create_ctree_recurse(SCCLUSTERTREE **aroot, SCCLUSTERTREE *nodes,
621 SCCELL *cell)
622 {
623 int err;
624 SCCLUSTERTREE *nstart;
625 SCCLCONNECT *nconnects;
626
627 if (Sc_stop())
628 longjmp(sc_please_stop, 1);
629
630 /* if no node, end */
631 if (nodes == NULL)
632 return(SC_NOERROR);
633
634 /* if one node, write to root and end */
635 if (nodes->next == NULL)
636 {
637 *aroot = nodes;
638 return(SC_NOERROR);
639 }
640
641 /* pair nodes in groups */
642 /* create list of connections between nodes */
643 if ((err = Sc_place_ctree_num_connects(nodes, &nconnects, cell)))
644 return(err);
645
646 /* sort number of connects from largest to smallest */
647 if ((err = Sc_place_ctree_sort_connects(nconnects, &nconnects)))
648 return(err);
649
650 /* pair by number of connects */
651 if ((err = Sc_place_ctree_pair(nodes, nconnects, &nstart)))
652 return(err);
653
654 /* recurse up a level */
655 return(Sc_place_create_ctree_recurse(aroot, nstart, cell));
656 }
657
658 /***********************************************************************
659 Module: Sc_place_ctree_add_parents
660 ________________________________________________________________________
661 Description:
662 Add the parent pointer to the cluster tree by doing a preorder
663 transversal.
664 ------------------------------------------------------------------------
665 Calling Sequence: Sc_place_ctree_add_parents(node, parent);
666
667 Name Type Description
668 ---- ---- -----------
669 node *SCCLUSTERTREE Pointer to current node in transversal.
670 parent *SCCLUSTERTREE Pointer to parent node.
671 ------------------------------------------------------------------------
672 */
673
Sc_place_ctree_add_parents(SCCLUSTERTREE * node,SCCLUSTERTREE * parent)674 void Sc_place_ctree_add_parents(SCCLUSTERTREE *node, SCCLUSTERTREE *parent)
675 {
676 if (node == NULL) return;
677 node->parent = parent;
678 Sc_place_ctree_add_parents(node->lptr, node);
679 Sc_place_ctree_add_parents(node->rptr, node);
680 }
681
682 /***********************************************************************
683 Module: Sc_place_ctree_num_connects
684 ------------------------------------------------------------------------
685 Description:
686 Create a list of the number of connections from all groups to all
687 other groups.
688 ------------------------------------------------------------------------
689 Calling Sequence: err = Sc_place_ctree_num_connects(nodes, clist, cell);
690
691 Name Type Description
692 ---- ---- -----------
693 nodes *SCCLUSTERTREE List of current nodes.
694 clist **clist Address of where to write resultant list.
695 cell *SCCELL Pointer to parent cell.
696 err int Returned error code, 0 = no error.
697 ------------------------------------------------------------------------
698 */
699
Sc_place_ctree_num_connects(SCCLUSTERTREE * nodes,SCCLCONNECT ** clist,SCCELL * cell)700 int Sc_place_ctree_num_connects(SCCLUSTERTREE *nodes, SCCLCONNECT **clist, SCCELL *cell)
701 {
702 SCCLUSTERTREE *nextnode;
703 int common, node_num;
704 SCCLCONNECT *newcon, *start, *end;
705
706 start = end = NULL;
707 node_num = 0;
708
709 /* clear flags on all extracted nodes */
710 Sc_clear_ext_nodes(cell->ex_nodes);
711
712 /* go through list of nodes */
713 for ( ; nodes; nodes = nodes->next)
714 {
715 /* check all other node */
716 for (nextnode = nodes->next; nextnode; nextnode = nextnode->next)
717 {
718 node_num += 2;
719
720 /* mark all extracted nodes used by first node */
721 Sc_set_ext_nodes_by_ctree(nodes, node_num);
722
723 /* count number of common extracted nodes */
724 common = Sc_count_ext_nodes(nextnode, node_num);
725
726 if (common)
727 {
728 newcon = (SCCLCONNECT *)emalloc(sizeof(SCCLCONNECT), sc_tool->cluster);
729 if (newcon == NULL)
730 return(Sc_seterrmsg(SC_NOMEMORY));
731 newcon->node[0] = nodes;
732 newcon->node[1] = nextnode;
733 newcon->count = common;
734 newcon->last = end;
735 newcon->next = NULL;
736 if (end)
737 {
738 end->next = newcon;
739 } else
740 {
741 start = newcon;
742 }
743 end = newcon;
744 }
745 }
746 }
747
748 *clist = start;
749 return(SC_NOERROR);
750 }
751
752 /***********************************************************************
753 Module: Sc_clear_ext_nodes
754 ------------------------------------------------------------------------
755 Description:
756 Set the flags field of all extracted nodes to clear.
757 ------------------------------------------------------------------------
758 Calling Sequence: Sc_clear_ext_nodes(nodes);
759
760 Name Type Description
761 ---- ---- -----------
762 nodes *SCEXTNODE Start of list of extracted nodes.
763 ------------------------------------------------------------------------
764 */
765
Sc_clear_ext_nodes(SCEXTNODE * nodes)766 void Sc_clear_ext_nodes(SCEXTNODE *nodes)
767 {
768 for ( ; nodes; nodes = nodes->next)
769 nodes->flags &= ~SCEXTNODECLUSE;
770 }
771
772 /***********************************************************************
773 Module: Sc_set_ext_nodes_by_ctree
774 ------------------------------------------------------------------------
775 Description:
776 Mark all extracted nodes references by any member of all the
777 clusters in the indicated cluster tree.
778 ------------------------------------------------------------------------
779 Calling Sequence: Sc_set_ext_nodes_by_ctree(node, marker);
780
781 Name Type Description
782 ---- ---- -----------
783 node *SCCLUSTERTREE Pointer to cluster tree node.
784 marker int Value to set flags field to.
785 ------------------------------------------------------------------------
786 */
787
Sc_set_ext_nodes_by_ctree(SCCLUSTERTREE * node,int marker)788 void Sc_set_ext_nodes_by_ctree(SCCLUSTERTREE *node, int marker)
789 {
790 SCNIPORT *port;
791
792 if (node == NULL) return;
793
794 Sc_set_ext_nodes_by_ctree(node->lptr, marker);
795
796 /* process node if cluster */
797 if (node->cluster)
798 {
799 /* check every port of member */
800 for (port = node->cluster->node->ports; port; port = port->next)
801 port->ext_node->flags = marker;
802 }
803
804 Sc_set_ext_nodes_by_ctree(node->rptr, marker);
805 }
806
807 /***********************************************************************
808 Module: Sc_count_ext_nodes
809 ------------------------------------------------------------------------
810 Description:
811 Return the number of extracted nodes which have flag bit set only
812 and is accessed by subtree.
813 ------------------------------------------------------------------------
814 Calling Sequence: count = Sc_count_ext_nodes(node, marker);
815
816 Name Type Description
817 ---- ---- -----------
818 node *SCCLUSTERTREE Start of cluster tree node.
819 marker int Value to look for.
820 ------------------------------------------------------------------------
821 */
822
Sc_count_ext_nodes(SCCLUSTERTREE * node,int marker)823 int Sc_count_ext_nodes(SCCLUSTERTREE *node, int marker)
824 {
825 SCNIPORT *port;
826 int count;
827
828 if (node == NULL)
829 return(0);
830
831 count = Sc_count_ext_nodes(node->lptr, marker);
832
833 /* process node if cluster */
834 if (node->cluster)
835 {
836 /* check every port of member */
837 for (port = node->cluster->node->ports; port; port = port->next)
838 {
839 if (port->ext_node->flags == marker)
840 {
841 count++;
842 port->ext_node->flags |= SCEXTNODEGROUP1;
843 }
844 }
845 }
846
847 count += Sc_count_ext_nodes(node->rptr, marker);
848
849 return(count);
850 }
851
852 /***********************************************************************
853 Module: Sc_place_ctree_sort_connects
854 ------------------------------------------------------------------------
855 Description:
856 Sort the passed list on number of connections from largest to
857 smallest.
858 ------------------------------------------------------------------------
859 Calling Sequence: err = Sc_place_ctree_sort_connects(list, gstart);
860
861 Name Type Description
862 ---- ---- -----------
863 list *SCCLCONNECT Pointer to start of connection list.
864 gstart **SCCLCONNECT Address of where to write new start.
865 err int Returned error code, 0 = no error.
866 ------------------------------------------------------------------------
867 */
868
Sc_place_ctree_sort_connects(SCCLCONNECT * list,SCCLCONNECT ** gstart)869 int Sc_place_ctree_sort_connects(SCCLCONNECT *list, SCCLCONNECT **gstart)
870 {
871 SCCLCONNECT *pold, *pp, *plast;
872
873 /* order placement list highest to lowest */
874 if (list)
875 {
876 pold = list;
877 for (pp = list->next; pp;)
878 {
879 if (pp->count > pold->count)
880 {
881 pold->next = pp->next;
882 if (pp->next)
883 pp->next->last = pold;
884 for (plast = pold->last; plast; plast = plast->last)
885 {
886 if (plast->count >= pp->count)
887 break;
888 }
889 if (!plast)
890 {
891 pp->next = list;
892 list->last = pp;
893 list = pp;
894 pp->last = NULL;
895 } else
896 {
897 pp->next = plast->next;
898 pp->next->last = pp;
899 pp->last = plast;
900 plast->next = pp;
901 }
902 pp = pold->next;
903 } else
904 {
905 pold = pp;
906 pp = pp->next;
907 }
908 }
909 }
910
911 *gstart = list;
912 return(SC_NOERROR);
913 }
914
915 /***********************************************************************
916 Module: Sc_place_ctree_pair
917 ------------------------------------------------------------------------
918 Description:
919 Pair up the given nodes by using the information in the connection
920 list.
921 ------------------------------------------------------------------------
922 Calling Sequence: err = Sc_place_ctree_pair(nodes, nconnects, nstart);
923
924 Name Type Description
925 ---- ---- -----------
926 nodes *SCCLUSTERTREE Pointer to start of list of nodes.
927 nconnects *SCCLCONNECT Pointer to start of list of connections.
928 nstart **SCCLUSTERTREE Address of where to write new list.
929 err int Returned error code, 0 = no error.
930 ------------------------------------------------------------------------
931 */
932
Sc_place_ctree_pair(SCCLUSTERTREE * nodes,SCCLCONNECT * nconnects,SCCLUSTERTREE ** nstart)933 int Sc_place_ctree_pair(SCCLUSTERTREE *nodes, SCCLCONNECT *nconnects,
934 SCCLUSTERTREE **nstart)
935 {
936 SCCLUSTERTREE *tptr, *newstart, *newnode;
937 SCCLCONNECT *connect, *bconnect, *nconnect;
938 int err;
939
940 /* clear the placed flag in all tree nodes */
941 for (tptr = nodes; tptr; tptr = tptr->next)
942 tptr->bits &= ~SCBITS_PLACED;
943
944 /* go through connection list */
945 newstart = NULL;
946 for (connect = nconnects; connect;)
947 {
948 /* if either placed, continue */
949 if (connect->node[0]->bits & SCBITS_PLACED ||
950 connect->node[1]->bits & SCBITS_PLACED)
951 {
952 connect = connect->next;
953 continue;
954 }
955
956 /* get best choice */
957 if ((err = Sc_place_best_pair(connect, &bconnect)))
958 return(err);
959
960 /* create new cluster tree node */
961 newnode = (SCCLUSTERTREE *)emalloc(sizeof(SCCLUSTERTREE), sc_tool->cluster);
962 if (newnode == 0)
963 return(Sc_seterrmsg(SC_NOMEMORY));
964 newnode->cluster = NULL;
965 newnode->bits = 0;
966 newnode->parent = NULL;
967 newnode->lptr = bconnect->node[0];
968 newnode->lptr->parent = newnode;
969 bconnect->node[0]->bits |= SCBITS_PLACED;
970 newnode->rptr = bconnect->node[1];
971 newnode->rptr->parent = newnode;
972 bconnect->node[1]->bits |= SCBITS_PLACED;
973 newnode->next = newstart;
974 newstart = newnode;
975
976 /* remove from list */
977 if (connect == bconnect)
978 {
979 nconnect = connect->next;
980 efree((CHAR *)connect);
981 connect = nconnect;
982 } else
983 {
984 bconnect->last->next = bconnect->next;
985 if (bconnect->next)
986 bconnect->next->last = bconnect->last;
987 efree((CHAR *)bconnect);
988 }
989 }
990
991 /* if no connections, arbitrarily combine two clusters */
992 if (!nconnects)
993 {
994 /* create new cluster tree node */
995 newnode = (SCCLUSTERTREE *)emalloc(sizeof(SCCLUSTERTREE), sc_tool->cluster);
996 if (newnode == 0)
997 {
998 return(Sc_seterrmsg(SC_NOMEMORY));
999 }
1000 newnode->cluster = NULL;
1001 newnode->bits = 0;
1002 newnode->parent = NULL;
1003 newnode->lptr = nodes;
1004 newnode->lptr->parent = newnode;
1005 nodes->bits |= SCBITS_PLACED;
1006 newnode->rptr = nodes->next;
1007 newnode->rptr->parent = newnode;
1008 nodes->next->bits |= SCBITS_PLACED;
1009 newnode->next = newstart;
1010 newstart = newnode;
1011 }
1012
1013 /* add any remaining tree nodes as singular nodes */
1014 for (tptr = nodes; tptr; tptr = tptr->next)
1015 {
1016 if (!(tptr->bits & SCBITS_PLACED))
1017 {
1018 /* create new cluster tree node */
1019 newnode = (SCCLUSTERTREE *)emalloc(sizeof(SCCLUSTERTREE), sc_tool->cluster);
1020 if (newnode == 0)
1021 {
1022 return(Sc_seterrmsg(SC_NOMEMORY));
1023 }
1024 newnode->cluster = NULL;
1025 newnode->bits = 0;
1026 newnode->parent = NULL;
1027 newnode->lptr = tptr;
1028 newnode->lptr->parent = newnode;
1029 tptr->bits |= SCBITS_PLACED;
1030 newnode->rptr = NULL;
1031 newnode->next = newstart;
1032 newstart = newnode;
1033 }
1034 }
1035
1036 *nstart = newstart;
1037 return(SC_NOERROR);
1038 }
1039
1040 /***********************************************************************
1041 Module: Sc_place_best_pair
1042 ------------------------------------------------------------------------
1043 Description:
1044 Return a pointer to the cluster connection list which has both
1045 members unplaced, has the same weight as the one top on the list,
1046 and appears the smallest number of times.
1047 ------------------------------------------------------------------------
1048 Calling Sequence: err = Sc_place_best_pair(connect, bconnect);
1049
1050 Name Type Description
1051 ---- ---- -----------
1052 connect *SCCLCONNECT Start of sorted list.
1053 bconnect **SCCLCONNECT Address to write pointer to best pair.
1054 err int Returned error code, 0 = no error.
1055 ------------------------------------------------------------------------
1056 */
1057
Sc_place_best_pair(SCCLCONNECT * connect,SCCLCONNECT ** bconnect)1058 int Sc_place_best_pair(SCCLCONNECT *connect, SCCLCONNECT **bconnect)
1059 {
1060 SCCLCONNECT *nconnect;
1061 struct Itemp
1062 {
1063 struct Iscclustertree *node; /* cluster tree node */
1064 int count; /* number of times seen */
1065 struct Iscclconnect *ref; /* first reference */
1066 struct Itemp *next; /* next in list */
1067 } *nlist, *slist, *blist;
1068 int minuse;
1069
1070 slist = NULL;
1071 for (nconnect = connect; nconnect; nconnect = nconnect->next)
1072 {
1073 if (nconnect->count < connect->count)
1074 break;
1075 if (nconnect->node[0]->bits & SCBITS_PLACED ||
1076 nconnect->node[1]->bits & SCBITS_PLACED)
1077 continue;
1078
1079 /* check if nodes previously counted */
1080 for (nlist = slist; nlist; nlist = nlist->next)
1081 {
1082 if (nlist->node == nconnect->node[0])
1083 break;
1084 }
1085 if (nlist)
1086 {
1087 nlist->count++;
1088 } else
1089 {
1090 nlist = (struct Itemp *)emalloc(sizeof(struct Itemp), sc_tool->cluster);
1091 if (nlist == NULL)
1092 return(Sc_seterrmsg(SC_NOMEMORY));
1093 nlist->node = nconnect->node[0];
1094 nlist->count = 1;
1095 nlist->ref = nconnect;
1096 nlist->next = slist;
1097 slist = nlist;
1098 }
1099 for (nlist = slist; nlist; nlist = nlist->next)
1100 {
1101 if (nlist->node == nconnect->node[1])
1102 break;
1103 }
1104 if (nlist)
1105 {
1106 nlist->count++;
1107 } else
1108 {
1109 nlist = (struct Itemp *)emalloc(sizeof(struct Itemp), sc_tool->cluster);
1110 if (nlist == NULL)
1111 return(Sc_seterrmsg(SC_NOMEMORY));
1112 nlist->node = nconnect->node[1];
1113 nlist->count = 1;
1114 nlist->ref = nconnect;
1115 nlist->next = slist;
1116 slist = nlist;
1117 }
1118 }
1119
1120 /* find the minimum count */
1121 minuse = slist->count;
1122 blist = slist;
1123 for (nlist = slist->next; nlist; nlist = nlist->next)
1124 {
1125 if (nlist->count < minuse)
1126 {
1127 minuse = nlist->count;
1128 blist = nlist;
1129 }
1130 }
1131
1132 *bconnect = blist->ref;
1133 return(SC_NOERROR);
1134 }
1135
1136 /***********************************************************************
1137 Module: Sc_place_print_cluster_tree
1138 ------------------------------------------------------------------------
1139 Description:
1140 Print the cluster placement tree by doing an inorder transversal.
1141 ------------------------------------------------------------------------
1142 Calling Sequence: Sc_place_print_cluster_tree(node, level);
1143
1144 Name Type Description
1145 ---- ---- -----------
1146 node *SCCLUSTERTREE Pointer to cluster tree node.
1147 level int Current level of tree (0 = root).
1148 ------------------------------------------------------------------------
1149 */
1150
Sc_place_print_cluster_tree(SCCLUSTERTREE * node,int level)1151 void Sc_place_print_cluster_tree(SCCLUSTERTREE *node, int level)
1152 {
1153 static CHAR spacer[80], trailer[80];
1154 int i;
1155
1156 if (Sc_stop())
1157 longjmp(sc_please_stop, 1);
1158
1159 if (node == NULL)
1160 return;
1161
1162 Sc_place_print_cluster_tree(node->lptr, level + 1);
1163
1164 /* process node */
1165 i = level << 2;
1166 spacer[i] = 0;
1167 while (i)
1168 spacer[--i] = ' ';
1169 i = 36 - (level << 2);
1170 if (i > 0)
1171 {
1172 trailer[i] = 0;
1173 while (i)
1174 trailer[--i] = '-';
1175 } else
1176 {
1177 trailer[0] = 0;
1178 }
1179 if (node->cluster)
1180 {
1181 ttyputmsg(_("%sCell %s"), spacer, node->cluster->node->name);
1182 } else
1183 {
1184 ttyputmsg(x_("%s%-2d**%s"), spacer, level, trailer);
1185 }
1186
1187 Sc_place_print_cluster_tree(node->rptr, level + 1);
1188 }
1189
1190 /***********************************************************************
1191 Module: Sc_place_sort_cluster_tree
1192 ------------------------------------------------------------------------
1193 Description:
1194 Sort the cluster tree into a list by sorting groups.
1195 Sorting attempts to optimize the placement of groups by
1196 minimizing length of connections between groups and locating groups
1197 close to any specified ports.
1198 ------------------------------------------------------------------------
1199 Calling Sequence: err = Sc_place_sort_cluster_tree(ctree, cell);
1200
1201 Name Type Description
1202 ---- ---- -----------
1203 ctree *SCCLUSTERTREE Pointer to root of cluster tree.
1204 cell *SCCELL Pointer to parent cell.
1205 err int Returned error code, 0 = no error.
1206 ------------------------------------------------------------------------
1207 */
1208
Sc_place_sort_cluster_tree(SCCLUSTERTREE * ctree,SCCELL * cell)1209 int Sc_place_sort_cluster_tree(SCCLUSTERTREE *ctree, SCCELL *cell)
1210 {
1211 SCNBTRUNK *trunks, *newtrunk, *nexttrunk;
1212 SCEXTNODE *enode;
1213 int err;
1214
1215 trunks = NULL;
1216
1217 /* create a list of trunks from the extracted nodes */
1218 for (enode = cell->ex_nodes; enode; enode = enode->next)
1219 {
1220 newtrunk = (SCNBTRUNK *)emalloc(sizeof(SCNBTRUNK), sc_tool->cluster);
1221 if (newtrunk == NULL)
1222 return(Sc_seterrmsg(SC_NOMEMORY));
1223 newtrunk->ext_node = enode;
1224 newtrunk->minx = 0;
1225 newtrunk->maxx = 0;
1226 newtrunk->next = trunks;
1227 trunks = newtrunk;
1228 enode->ptr = (CHAR *)newtrunk; /* back reference pointer */
1229 }
1230
1231 sc_currentcost = Sc_place_cost_cluster_tree(sc_gcluster_tree, trunks, cell);
1232 if (sc_placecontrol.stats_flag)
1233 ttyputverbose(M_("***** Cost of placement before cluster sorting = %d"),
1234 sc_currentcost);
1235
1236 /* call top-down swapper */
1237 if ((err = Sc_place_sort_swapper_top_down(ctree, trunks, cell)))
1238 return(err);
1239 ttyputverbose(M_(" Time for Top-Down Sort = %s."),
1240 Sc_cpu_time(TIME_REL));
1241
1242 /* call bottom-up swapper */
1243 if ((err = Sc_place_sort_swapper_bottom_up(ctree, trunks, cell)))
1244 return(err);
1245 ttyputverbose(M_(" Time for Bottom_Up Sort = %s."),
1246 Sc_cpu_time(TIME_REL));
1247
1248 if (sc_placecontrol.stats_flag)
1249 ttyputverbose(M_("***** Cost of placement after cluster sorting = %d"),
1250 sc_currentcost);
1251
1252 for (newtrunk = trunks; newtrunk; newtrunk = nexttrunk)
1253 {
1254 nexttrunk = newtrunk->next;
1255 efree((CHAR *)newtrunk);
1256 }
1257
1258 return(SC_NOERROR);
1259 }
1260
1261 /***********************************************************************
1262 Module: Sc_place_sort_swapper_top_down
1263 ------------------------------------------------------------------------
1264 Description:
1265 Do preorder transversal of cluster tree, swapping groups to try
1266 and sort tree into a more efficient placement.
1267 ------------------------------------------------------------------------
1268 Calling Sequence: err = Sc_place_sort_swapper_top_down(ctree, trunks, cell);
1269
1270 Name Type Description
1271 ---- ---- -----------
1272 ctree *SCCLUSTERTREE Root of cluster tree.
1273 trunks *SCNBTRUCK List of trunks for costing.
1274 cell *SCCELL Pointer to parent cell.
1275 err int Returned error code, 0 = no error.
1276 ------------------------------------------------------------------------
1277 */
1278
Sc_place_sort_swapper_top_down(SCCLUSTERTREE * ctree,SCNBTRUNK * trunks,SCCELL * cell)1279 int Sc_place_sort_swapper_top_down(SCCLUSTERTREE *ctree, SCNBTRUNK *trunks, SCCELL *cell)
1280 {
1281 int err, cost2;
1282
1283 if (Sc_stop())
1284 longjmp(sc_please_stop, 1);
1285
1286 if (ctree == NULL)
1287 return(SC_NOERROR);
1288
1289 /* process tree node if there are two subtrees */
1290 if (ctree->lptr && ctree->rptr)
1291 {
1292 /* swap groups */
1293 Sc_place_switch_subtrees(ctree);
1294
1295 /* check new cost */
1296 cost2 = Sc_place_cost_cluster_tree(sc_gcluster_tree, trunks, cell);
1297
1298 /* swap back if old cost is less than new */
1299 if (sc_currentcost < cost2)
1300 {
1301 Sc_place_switch_subtrees(ctree);
1302 } else
1303 {
1304 sc_currentcost = cost2;
1305 }
1306 }
1307
1308 if ((err = Sc_place_sort_swapper_top_down(ctree->lptr, trunks, cell)))
1309 return(err);
1310
1311 if ((err = Sc_place_sort_swapper_top_down(ctree->rptr, trunks, cell)))
1312 return(err);
1313
1314 return(SC_NOERROR);
1315 }
1316
1317 /***********************************************************************
1318 Module: Sc_place_sort_swapper_bottom_up
1319 ------------------------------------------------------------------------
1320 Description:
1321 Do a postorder transversal of cluster tree, swapping groups to try
1322 and sort tree into a more efficient placement.
1323 ------------------------------------------------------------------------
1324 Calling Sequence: err = Sc_place_sort_swapper_bottom_up(ctree, trunks, cell);
1325
1326 Name Type Description
1327 ---- ---- -----------
1328 ctree *SCCLUSTERTREE Root of cluster tree.
1329 trunks *SCNBTRUCK List of trunks for costing.
1330 cell *SCCELL Pointer to parent cell.
1331 err int Returned error code, 0 = no error.
1332 ------------------------------------------------------------------------
1333 */
1334
Sc_place_sort_swapper_bottom_up(SCCLUSTERTREE * ctree,SCNBTRUNK * trunks,SCCELL * cell)1335 int Sc_place_sort_swapper_bottom_up(SCCLUSTERTREE *ctree, SCNBTRUNK *trunks, SCCELL *cell)
1336 {
1337 int err, cost2;
1338
1339 if (Sc_stop())
1340 longjmp(sc_please_stop, 1);
1341
1342 if (ctree == NULL)
1343 return(SC_NOERROR);
1344
1345 if ((err = Sc_place_sort_swapper_bottom_up(ctree->lptr, trunks, cell)))
1346 return(err);
1347
1348 if ((err = Sc_place_sort_swapper_bottom_up(ctree->rptr, trunks, cell)))
1349 return(err);
1350
1351 /* process tree node if there are two subtrees */
1352 if (ctree->lptr && ctree->rptr)
1353 {
1354 /* swap groups */
1355 Sc_place_switch_subtrees(ctree);
1356
1357 /* check new cost */
1358 cost2 = Sc_place_cost_cluster_tree(sc_gcluster_tree, trunks, cell);
1359
1360 /* swap back if old cost is less than new */
1361 if (sc_currentcost < cost2)
1362 {
1363 Sc_place_switch_subtrees(ctree);
1364 } else
1365 {
1366 sc_currentcost = cost2;
1367 }
1368 }
1369
1370 return(SC_NOERROR);
1371 }
1372
1373 /***********************************************************************
1374 Module: Sc_place_switch_subtrees
1375 ------------------------------------------------------------------------
1376 Description:
1377 Switch the subtrees recursively to perform a mirror image operation
1378 along "main" axis.
1379 ------------------------------------------------------------------------
1380 Calling Sequence: Sc_place_switch_subtrees(node);
1381
1382 Name Type Description
1383 ---- ---- -----------
1384 node *SCCLUSTERTREE Pointer to top tree node.
1385 ------------------------------------------------------------------------
1386 */
1387
Sc_place_switch_subtrees(SCCLUSTERTREE * node)1388 void Sc_place_switch_subtrees(SCCLUSTERTREE *node)
1389 {
1390 SCCLUSTERTREE *temp;
1391
1392 if (Sc_stop())
1393 longjmp(sc_please_stop, 1);
1394
1395 if (node == NULL)
1396 return;
1397
1398 temp = node->lptr;
1399 node->lptr = node->rptr;
1400 node->rptr = temp;
1401 Sc_place_switch_subtrees(node->lptr);
1402 Sc_place_switch_subtrees(node->rptr);
1403 }
1404
1405 /***********************************************************************
1406 Module: Sc_place_cost_cluster_tree
1407 ------------------------------------------------------------------------
1408 Description:
1409 Return the "cost" of the indicated cluster tree sort. Cost is a
1410 function of the length of connections between clusters and placement
1411 to ports.
1412 ------------------------------------------------------------------------
1413 Calling Sequence: cost = Sc_place_cost_cluster_tree(ctree, trunks, cell);
1414
1415 Name Type Description
1416 ---- ---- -----------
1417 ctree *SCCLUSTERTREE Pointer to cluster tree node.
1418 trunks *SCNBTRUNK Pointer to trunks to use to cost.
1419 cell *SCCELL Pointer to parent cell.
1420 cost int Returned cost.
1421 ------------------------------------------------------------------------
1422 */
1423
Sc_place_cost_cluster_tree(SCCLUSTERTREE * ctree,SCNBTRUNK * trunks,SCCELL * cell)1424 int Sc_place_cost_cluster_tree(SCCLUSTERTREE *ctree, SCNBTRUNK *trunks, SCCELL *cell)
1425 {
1426 int cost, pos, row;
1427 SCNBTRUNK *ntrunk;
1428 SCPORT *pport;
1429
1430 /* clear trunks to record lengths */
1431 for (ntrunk = trunks; ntrunk; ntrunk = ntrunk->next)
1432 {
1433 ntrunk->minx = -1;
1434 ntrunk->maxx = -1;
1435 }
1436
1437 /* set trunks lengths */
1438 pos = 0;
1439 Sc_place_cost_cluster_tree_2(ctree, trunks, &pos);
1440
1441 /* calculate cost */
1442 cost = 0;
1443 for (ntrunk = trunks; ntrunk; ntrunk = ntrunk->next)
1444 {
1445 if (ntrunk->minx < 0)
1446 continue;
1447 cost += ntrunk->maxx - ntrunk->minx;
1448 }
1449
1450 for (pport = cell->ports; pport; pport = pport->next)
1451 {
1452 if (!(pport->bits & SCPORTDIRMASK))
1453 continue;
1454 ntrunk = (SCNBTRUNK *)pport->node->ports->ext_node->ptr;
1455 if (!ntrunk) continue;
1456 if (pport->bits & SCPORTDIRUP)
1457 {
1458 /* add distance to top row */
1459 row = ntrunk->maxx / cell->placement->size_rows;
1460 if ((row + 1) < cell->placement->num_rows)
1461 {
1462 cost += (cell->placement->num_rows - row - 1) *
1463 cell->placement->avg_height *
1464 sc_placecontrol.vertical_cost;
1465 }
1466 }
1467 if (pport->bits & SCPORTDIRDOWN)
1468 {
1469 /* add distance to bottom row */
1470 row = ntrunk->minx / cell->placement->size_rows;
1471 if (row)
1472 {
1473 cost += row * cell->placement->avg_height
1474 * sc_placecontrol.vertical_cost;
1475 }
1476 }
1477 if (pport->bits & SCPORTDIRLEFT)
1478 {
1479 /* EMPTY */
1480 }
1481 if (pport->bits & SCPORTDIRRIGHT)
1482 {
1483 /* EMPTY */
1484 }
1485 }
1486
1487 return(cost);
1488 }
1489
1490 /***********************************************************************
1491 Module: Sc_place_cost_cluster_tree_2
1492 ------------------------------------------------------------------------
1493 Description:
1494 Set the limits of the trunks by doing an inorder transversal of
1495 the cluster tree.
1496 ------------------------------------------------------------------------
1497 Calling Sequence: Sc_place_cost_cluster_tree_2(ctree, trunks, pos);
1498
1499 Name Type Description
1500 ---- ---- -----------
1501 ctree *SCCLUSTERTREE Pointer to cluster tree node.
1502 trunks *SCNBTRUNK Pointer to trunks to use to cost.
1503 pos *int Address of current position.
1504 ------------------------------------------------------------------------
1505 */
1506
Sc_place_cost_cluster_tree_2(SCCLUSTERTREE * ctree,SCNBTRUNK * trunks,int * pos)1507 void Sc_place_cost_cluster_tree_2(SCCLUSTERTREE *ctree, SCNBTRUNK *trunks, int *pos)
1508 {
1509 SCNBTRUNK *ntrunk;
1510 SCNIPORT *port;
1511
1512 if (Sc_stop())
1513 longjmp(sc_please_stop, 1);
1514
1515 if (ctree == NULL)
1516 return;
1517
1518 /* do all nodes left */
1519 Sc_place_cost_cluster_tree_2(ctree->lptr, trunks, pos);
1520
1521 /* process node */
1522 if (ctree->cluster)
1523 {
1524 for (port = ctree->cluster->node->ports; port; port = port->next)
1525 {
1526 ntrunk = (SCNBTRUNK *)port->ext_node->ptr;
1527 if (!ntrunk) continue;
1528 if (ntrunk->minx < 0)
1529 ntrunk->minx = *pos + port->xpos;
1530 ntrunk->maxx = *pos + port->xpos;
1531 }
1532 *pos += ctree->cluster->size;
1533 }
1534
1535 /* do all nodes right */
1536 Sc_place_cost_cluster_tree_2(ctree->rptr, trunks, pos);
1537 }
1538
1539 /***********************************************************************
1540 Module: Sc_place_create_placelist
1541 ------------------------------------------------------------------------
1542 Description:
1543 Create the placement list by simply taking the clusters from the
1544 sorted cluster list and placing members in a snake pattern.
1545 Do an inorder transversal to create placelist.
1546 ------------------------------------------------------------------------
1547 Calling Sequence: err = Sc_place_create_placelist(ctree, cell);
1548
1549 Name Type Description
1550 ---- ---- -----------
1551 ctree *SCCLUSTERTREE Pointer to start of cluster tree.
1552 cell *SCCELL Pointer to parent cell.
1553 err int Returned error code, 0 = no error.
1554 ------------------------------------------------------------------------
1555 */
1556
Sc_place_create_placelist(SCCLUSTERTREE * ctree,SCCELL * cell)1557 int Sc_place_create_placelist(SCCLUSTERTREE *ctree, SCCELL *cell)
1558 {
1559 int err;
1560 SCROWLIST *row;
1561
1562 if (Sc_stop())
1563 longjmp(sc_please_stop, 1);
1564
1565 if (ctree == NULL)
1566 return(SC_NOERROR);
1567
1568 if ((err = Sc_place_create_placelist(ctree->lptr, cell)))
1569 return(err);
1570
1571 /* add clusters to placement list */
1572 if (ctree->cluster)
1573 {
1574 row = cell->placement->rows;
1575 while (row->next)
1576 row = row->next;
1577 (void)Sc_place_add_cluster_to_row(ctree->cluster, row, cell->placement);
1578 }
1579
1580 if ((err = Sc_place_create_placelist(ctree->rptr, cell)))
1581 return(err);
1582
1583 return(SC_NOERROR);
1584 }
1585
1586 /***********************************************************************
1587 Module: Sc_place_add_cluster_to_row
1588 ------------------------------------------------------------------------
1589 Description:
1590 Add the members of the passed cluster to the indicated row.
1591 Add new rows as necessary and also maintain a global placement
1592 bidirectional list.
1593 ------------------------------------------------------------------------
1594 Calling Sequence: err = Sc_place_add_cluster_to_row(cluster, row, place);
1595
1596 Name Type Description
1597 ---- ---- -----------
1598 cluster *SCCLUSTER Pointer to cluster to add.
1599 row *SCROWLIST Pointer to the current row.
1600 place *SCPLACE Pointer to placement information.
1601 err int Returned error code, 0 = no error.
1602 ------------------------------------------------------------------------
1603 */
1604
Sc_place_add_cluster_to_row(SCCLUSTER * cluster,SCROWLIST * row,SCPLACE * place)1605 int Sc_place_add_cluster_to_row(SCCLUSTER *cluster, SCROWLIST *row, SCPLACE *place)
1606 {
1607 SCNBPLACE *newplace;
1608 SCROWLIST *row2;
1609 int old_condition, new_condition;
1610
1611 if (cluster->node->type != SCLEAFCELL)
1612 return(SC_NOERROR);
1613 newplace = (SCNBPLACE *)emalloc(sizeof(SCNBPLACE), sc_tool->cluster);
1614 if (newplace == 0)
1615 return(Sc_seterrmsg(SC_NOMEMORY));
1616 newplace->cell = cluster->node;
1617 newplace->xpos = 0;
1618 cluster->node->tp = (CHAR *)newplace;
1619 newplace->next = NULL;
1620 newplace->last = place->endlist;
1621 if (place->endlist == NULL)
1622 {
1623 place->plist = place->endlist = newplace;
1624 } else
1625 {
1626 place->endlist->next = newplace;
1627 place->endlist = newplace;
1628 }
1629 old_condition = place->size_rows - row->row_size;
1630 new_condition = place->size_rows - (row->row_size + cluster->node->size);
1631 if ((row->row_num + 1) < place->num_rows &&
1632 abs(old_condition) < abs(new_condition))
1633 {
1634 row2 = (SCROWLIST *)emalloc(sizeof(SCROWLIST), sc_tool->cluster);
1635 if (row2 == 0)
1636 return(Sc_seterrmsg(SC_NOMEMORY));
1637 row2->start = NULL;
1638 row2->end = NULL;
1639 row2->row_num = row->row_num + 1;
1640 row2->row_size = 0;
1641 row2->next = NULL;
1642 row2->last = row;
1643 row->next = row2;
1644 row = row2;
1645 }
1646
1647 /* add to row */
1648 if (row->row_num % 2)
1649 {
1650 /* odd row */
1651 if (row->end == NULL)
1652 row->end = newplace;
1653 row->start = newplace;
1654 } else
1655 {
1656 /* even row */
1657 if (row->start == NULL)
1658 row->start = newplace;
1659 row->end = newplace;
1660 }
1661 row->row_size += cluster->node->size;
1662
1663 return(SC_NOERROR);
1664 }
1665
1666 /***********************************************************************
1667 Module: Sc_free_cluster_tree
1668 ------------------------------------------------------------------------
1669 Description:
1670 Do a post-order transversal, freeing up the members of the
1671 cluster tree.
1672 ------------------------------------------------------------------------
1673 Calling Sequence: Sc_free_cluster_tree(node);
1674
1675 Name Type Description
1676 ---- ---- -----------
1677 node *SCCLUSTERTREE Pointer to current node.
1678 ------------------------------------------------------------------------
1679 */
1680
Sc_free_cluster_tree(SCCLUSTERTREE * node)1681 void Sc_free_cluster_tree(SCCLUSTERTREE *node)
1682 {
1683 if (node == NULL)
1684 return;
1685 Sc_free_cluster_tree(node->lptr);
1686 Sc_free_cluster_tree(node->rptr);
1687 if (node->cluster) efree((CHAR *)node->cluster);
1688 efree((CHAR *)node);
1689 }
1690
1691 /***********************************************************************
1692 Module: Sc_place_net_balance
1693 ------------------------------------------------------------------------
1694 Description:
1695 To a net balancing on the placelist.
1696 ------------------------------------------------------------------------
1697 Calling Sequence: err = Sc_place_net_balance(row, cell);
1698
1699 Name Type Description
1700 ---- ---- -----------
1701 row *SCROWLIST Pointer to start of row list.
1702 cell *SCCELL Pointer to parent cell.
1703 err int Returned error code, 0 = no error.
1704 ------------------------------------------------------------------------
1705 */
1706
Sc_place_net_balance(SCROWLIST * row,SCCELL * cell)1707 int Sc_place_net_balance(SCROWLIST *row, SCCELL *cell)
1708 {
1709 SCEXTNODE *nlist;
1710 SCCHANNEL *channel, *endchan, *newchan, *nextnewchan;
1711 SCNBTRUNK *trunks, *ntrunk, *oldtrunk, *sametrunk, *nextntrunk;
1712 int i, err;
1713 Q_UNUSED( row );
1714
1715 /* create channel list */
1716 channel = endchan = NULL;
1717 i = 0;
1718 sametrunk = NULL;
1719 do
1720 {
1721 newchan = (SCCHANNEL *)emalloc(sizeof(SCCHANNEL), sc_tool->cluster);
1722 if (newchan == NULL)
1723 return(Sc_seterrmsg(SC_NOMEMORY));
1724 newchan->number = i;
1725 trunks = oldtrunk = NULL;
1726
1727 /* create trunk list for each channel */
1728 for (nlist = cell->ex_nodes; nlist; nlist = nlist->next)
1729 {
1730 ntrunk = (SCNBTRUNK *)emalloc(sizeof(SCNBTRUNK), sc_tool->cluster);
1731 if (ntrunk == NULL)
1732 return(Sc_seterrmsg(SC_NOMEMORY));
1733 ntrunk->ext_node = nlist;
1734 ntrunk->minx = 0;
1735 ntrunk->maxx = 0;
1736 ntrunk->same = NULL;
1737 if (sametrunk == NULL)
1738 {
1739 nlist->ptr = (CHAR *)ntrunk;
1740 } else
1741 {
1742 sametrunk->same = ntrunk;
1743 sametrunk = sametrunk->next;
1744 }
1745 ntrunk->next = NULL;
1746 if (oldtrunk == NULL)
1747 {
1748 trunks = oldtrunk = ntrunk;
1749 } else
1750 {
1751 oldtrunk->next = ntrunk;
1752 oldtrunk = ntrunk;
1753 }
1754 }
1755 newchan->trunks = trunks;
1756 newchan->last = endchan;
1757 newchan->next = NULL;
1758 if (endchan)
1759 {
1760 endchan->next = newchan;
1761 endchan = newchan;
1762 } else
1763 {
1764 channel = endchan = newchan;
1765 }
1766 sametrunk = trunks;
1767 i++;
1768 } while ((i + 1) < cell->placement->num_rows);
1769
1770 /* report current placement evaluation */
1771 if (sc_placecontrol.stats_flag)
1772 ttyputmsg(M_("Evaluation before Net-Balancing = %d"),
1773 Sc_place_nb_cost(cell->placement->rows, channel, cell));
1774
1775 /* do the net balance for each cell */
1776 if ((err = Sc_place_nb_all_cells(cell, channel)))
1777 return(err);
1778
1779 /* number placement */
1780 Sc_place_nb_rebalance_rows(cell->placement->rows, cell->placement);
1781 Sc_place_number_placement(cell->placement->rows);
1782
1783 /* report new evaluation */
1784 if (sc_placecontrol.stats_flag)
1785 ttyputmsg(M_("Evaluation after Net-Balancing = %d"),
1786 Sc_place_nb_cost(cell->placement->rows, channel, cell));
1787
1788 for (newchan = channel; newchan; newchan = nextnewchan)
1789 {
1790 nextnewchan = newchan->next;
1791 for (ntrunk = newchan->trunks; ntrunk; ntrunk = nextntrunk)
1792 {
1793 nextntrunk = ntrunk->next;
1794 efree((CHAR *)ntrunk);
1795 }
1796 efree((CHAR *)newchan);
1797 }
1798
1799 return(SC_NOERROR);
1800 }
1801
1802 /***********************************************************************
1803 Module: Sc_place_nb_all_cells
1804 ------------------------------------------------------------------------
1805 Description:
1806 Do a net balance for each cell on at a time. Use the SCNITREE to
1807 insure that each cell is processed.
1808 ------------------------------------------------------------------------
1809 Calling Sequence: err = Sc_place_nb_all_cells(cell, channels);
1810
1811 Name Type Description
1812 ---- ---- -----------
1813 cell *SCCELL Pointer to parent cell.
1814 channels *SCCHANNEL Pointer to start of channel list.
1815 err int Returned err code, 0 = no error.
1816 ------------------------------------------------------------------------
1817 */
1818
Sc_place_nb_all_cells(SCCELL * cell,SCCHANNEL * channels)1819 int Sc_place_nb_all_cells(SCCELL *cell, SCCHANNEL *channels)
1820 {
1821 SCNITREE *ilist;
1822
1823 /* process cell */
1824 for (ilist = cell->nilist; ilist; ilist = ilist->next)
1825 {
1826 if (ilist->type == SCLEAFCELL)
1827 Sc_place_nb_do_cell((SCNBPLACE *)ilist->tp, channels, cell);
1828 }
1829
1830 return(SC_NOERROR);
1831 }
1832
1833 /***********************************************************************
1834 Module: Sc_place_nb_do_cell
1835 ------------------------------------------------------------------------
1836 Description:
1837 Do a net balance for the indicated instance.
1838 ------------------------------------------------------------------------
1839 Calling Sequence: Sc_place_nb_do_cell(place, channels, cell);
1840
1841 Name Type Description
1842 ---- ---- -----------
1843 place *SCNBPLACE Pointer to place of instance.
1844 channels *SCCHANNEL Pointer to channel list of trunks.
1845 cell *SCCELL Parent complex cell.
1846 ------------------------------------------------------------------------
1847 */
1848
Sc_place_nb_do_cell(SCNBPLACE * place,SCCHANNEL * channels,SCCELL * cell)1849 void Sc_place_nb_do_cell(SCNBPLACE *place, SCCHANNEL *channels, SCCELL *cell)
1850 {
1851 int min_cost, cost, pos, npos;
1852 SCNBPLACE *old_last, *old_next, *nplace;
1853 SCROWLIST *rows;
1854
1855 if (Sc_stop())
1856 longjmp(sc_please_stop, 1);
1857
1858 if (place == NULL) return;
1859
1860 /* find cost at present location and set as current minimum */
1861 rows = cell->placement->rows;
1862 min_cost = Sc_place_nb_cost(rows, channels, cell);
1863 pos = 0;
1864
1865 /* temporarily remove from list */
1866 old_last = place->last;
1867 old_next = place->next;
1868 Sc_place_nb_remove(place, rows);
1869
1870 /* check locations backwards for nb_limit */
1871 npos = -1;
1872 for (nplace = old_last; npos >= -sc_placecontrol.net_balance_limit;
1873 nplace = nplace->last)
1874 {
1875 if (nplace)
1876 {
1877 /* temporarily insert in list */
1878 Sc_place_nb_insert_before(place, nplace, rows);
1879
1880 /* check new cost */
1881 if ((cost = Sc_place_nb_cost(rows, channels, cell)) < min_cost)
1882 {
1883 min_cost = cost;
1884 pos = npos;
1885 }
1886
1887 /* remove place from list */
1888 Sc_place_nb_remove(place, rows);
1889 } else
1890 {
1891 break;
1892 }
1893 npos--;
1894 }
1895
1896 /* check forward locations for nb_limit */
1897 npos = 1;
1898 for (nplace = old_next; npos < sc_placecontrol.net_balance_limit;
1899 nplace = nplace->next)
1900 {
1901 if (nplace)
1902 {
1903 /* temporarily insert in list */
1904 Sc_place_nb_insert_after(place, nplace, rows);
1905
1906 /* check new cost */
1907 if ((cost = Sc_place_nb_cost(rows, channels, cell)) < min_cost)
1908 {
1909 min_cost = cost;
1910 pos = npos;
1911 }
1912
1913 /* remove place from list */
1914 Sc_place_nb_remove(place, rows);
1915 } else
1916 {
1917 break;
1918 }
1919 npos++;
1920 }
1921
1922 /* move if necessary */
1923 if (pos > 0)
1924 {
1925 while(pos-- > 1)
1926 {
1927 old_next = old_next->next;
1928 }
1929 Sc_place_nb_insert_after(place, old_next, rows);
1930 } else if (pos < 0)
1931 {
1932 while(pos++ < -1)
1933 {
1934 old_last = old_last->last;
1935 }
1936 Sc_place_nb_insert_before(place, old_last, rows);
1937 } else
1938 {
1939 if (old_last)
1940 {
1941 Sc_place_nb_insert_after(place, old_last, rows);
1942 } else
1943 {
1944 Sc_place_nb_insert_before(place, old_next, rows);
1945 }
1946 }
1947 }
1948
1949 /***********************************************************************
1950 Module: Sc_place_nb_cost
1951 ------------------------------------------------------------------------
1952 Description:
1953 Return cost of the indicated placement.
1954 ------------------------------------------------------------------------
1955 Calling Sequence: cost = Sc_place_nb_cost(rows, channels, cell);
1956
1957 Name Type Description
1958 ---- ---- -----------
1959 rows *SCROWLIST Pointer to start of list or rows.
1960 channels *SCCHANNEL Pointer to list of channels.
1961 cell *SCCELL Pointer to parent cell.
1962 cost int Returned cost.
1963 ------------------------------------------------------------------------
1964 */
1965
Sc_place_nb_cost(SCROWLIST * rows,SCCHANNEL * channels,SCCELL * cell)1966 int Sc_place_nb_cost(SCROWLIST *rows, SCCHANNEL *channels, SCCELL *cell)
1967 {
1968 int cost, dis, above, i, fcount, count, fminx, fmaxx;
1969 int row_num, max_rowsize, pos;
1970 SCNBPLACE *nplace;
1971 SCCHANNEL *nchan;
1972 SCNBTRUNK *ntrunk, *strunk, *ftrunk;
1973 SCNIPORT *port;
1974
1975 /* initialize all trunks */
1976 for (nchan = channels; nchan; nchan = nchan->next)
1977 {
1978 for (ntrunk = nchan->trunks; ntrunk; ntrunk = ntrunk->next)
1979 {
1980 ntrunk->minx = MAXINTBIG;
1981 ntrunk->maxx = -MAXINTBIG;
1982 }
1983 }
1984
1985 /* check all rows */
1986 nchan = channels;
1987 above = TRUE;
1988 dis = 0;
1989 row_num = 0;
1990 max_rowsize = cell->placement->size_rows + (cell->placement->avg_size >>1);
1991 for (nplace = rows->start; nplace; nplace = nplace->next)
1992 {
1993 /* check for room in current row */
1994 if (row_num % 2)
1995 {
1996 /* odd row */
1997 if ((dis - nplace->cell->size) < 0)
1998 {
1999 if ((row_num + 1) < cell->placement->num_rows)
2000 {
2001 row_num++;
2002 dis = 0;
2003 if (above ^= TRUE)
2004 nchan = nchan->next;
2005 }
2006 }
2007 } else
2008 {
2009 /* even row */
2010 if ((dis + nplace->cell->size) > max_rowsize)
2011 {
2012 if ((row_num + 1) < cell->placement->num_rows)
2013 {
2014 row_num++;
2015 dis = max_rowsize;
2016 if (above ^= TRUE)
2017 nchan = nchan->next;
2018 }
2019 }
2020 }
2021
2022 /* check all ports on instance */
2023 for (port = nplace->cell->ports; port; port = port->next)
2024 {
2025 /* find the correct trunk */
2026 ntrunk = (SCNBTRUNK *)port->ext_node->ptr;
2027 if (!ntrunk) continue;
2028 for (i = nchan->number; i; i--)
2029 ntrunk = ntrunk->same;
2030 if (ntrunk->minx == MAXINTBIG)
2031 {
2032 if (!above && ntrunk->same)
2033 ntrunk = ntrunk->same;
2034 }
2035 if (row_num % 2)
2036 {
2037 pos = dis - port->xpos;
2038 } else
2039 {
2040 pos = dis + port->xpos;
2041 }
2042 ntrunk->minx = mini(ntrunk->minx, pos);
2043 ntrunk->maxx = maxi(ntrunk->maxx, pos);
2044 }
2045 if (row_num % 2)
2046 {
2047 dis -= nplace->cell->size;
2048 } else
2049 {
2050 dis += nplace->cell->size;
2051 }
2052 }
2053
2054 /* calculate cost */
2055 cost = 0;
2056
2057 /* calculate horizontal costs */
2058 for (nchan = channels; nchan; nchan = nchan->next)
2059 {
2060 for (ntrunk = nchan->trunks; ntrunk; ntrunk = ntrunk->next)
2061 {
2062 if (ntrunk->minx != MAXINTBIG)
2063 cost += abs(ntrunk->maxx - ntrunk->minx);
2064 }
2065 }
2066
2067 /* calculate vertical cost */
2068 for (ntrunk = channels->trunks; ntrunk; ntrunk = ntrunk->next)
2069 {
2070 ftrunk = NULL;
2071 fcount = count = 0;
2072 for (strunk = ntrunk; strunk; strunk = strunk->same)
2073 {
2074 if (strunk->minx != MAXINTBIG)
2075 {
2076 if (ftrunk == NULL)
2077 {
2078 ftrunk = strunk;
2079 fminx = strunk->minx;
2080 fmaxx = strunk->maxx;
2081 fcount = count;
2082 } else
2083 {
2084 /* add new vertical */
2085 cost += (count - fcount) * cell->placement->avg_height *
2086 sc_placecontrol.vertical_cost;
2087 fcount = count;
2088
2089 /* additional horizontal */
2090 if (fmaxx < strunk->minx)
2091 {
2092 cost += abs(strunk->minx - fmaxx);
2093 fmaxx = strunk->maxx;
2094 } else if (fminx > strunk->maxx)
2095 {
2096 cost += abs(fminx - strunk->maxx);
2097 fminx = strunk->minx;
2098 } else
2099 {
2100 if (fminx > strunk->minx)
2101 fminx = strunk->minx;
2102 if (fmaxx < strunk->maxx)
2103 fmaxx = strunk->maxx;
2104 }
2105
2106 }
2107 }
2108 count++;
2109 }
2110 }
2111
2112 return(cost);
2113 }
2114
2115 /***********************************************************************
2116 Module: Sc_place_nb_remove
2117 ------------------------------------------------------------------------
2118 Description:
2119 Remove the indicated placed instance and clean up the rows
2120 structures.
2121 ------------------------------------------------------------------------
2122 Calling Sequence: Sc_place_nb_remove(place, rows);
2123
2124 Name Type Description
2125 ---- ---- -----------
2126 place *SCNBPLACE Pointer to place to be removed.
2127 rows *SCROWLIST Pointer to start of row list.
2128 ------------------------------------------------------------------------
2129 */
2130
Sc_place_nb_remove(SCNBPLACE * place,SCROWLIST * rows)2131 void Sc_place_nb_remove(SCNBPLACE *place, SCROWLIST *rows)
2132 {
2133 SCROWLIST *row;
2134 SCNBPLACE *old_next, *old_last;
2135
2136 old_next = place->next;
2137 old_last = place->last;
2138 if (place->last)
2139 place->last->next = old_next;
2140 if (place->next)
2141 place->next->last = old_last;
2142
2143 /* check if row change */
2144 for (row = rows; row; row = row->next)
2145 {
2146 if (row->start == place)
2147 {
2148 if (row->row_num % 2)
2149 {
2150 row->start = old_last;
2151 } else
2152 {
2153 row->start = old_next;
2154 }
2155 }
2156 if (row->end == place)
2157 {
2158 if (row->row_num % 2)
2159 {
2160 row->end = old_next;
2161 } else
2162 {
2163 row->end = old_last;
2164 }
2165 }
2166 }
2167 }
2168
2169 /***********************************************************************
2170 Module: Sc_place_nb_insert_before
2171 ------------------------------------------------------------------------
2172 Description:
2173 Insert the indicated place before the indicated second place and
2174 clear up the row markers if necessary.
2175 ------------------------------------------------------------------------
2176 Calling Sequence: Sc_place_nb_insert_before(place, oldplace, rows);
2177
2178 Name Type Description
2179 ---- ---- -----------
2180 place *SCNBPLACE Pointer to place to be inserted.
2181 oldplace *SCNBPLACE Pointer to place to be inserted before.
2182 rows *SCROWLIST Start of list of row markers.
2183 ------------------------------------------------------------------------
2184 */
2185
Sc_place_nb_insert_before(SCNBPLACE * place,SCNBPLACE * oldplace,SCROWLIST * rows)2186 void Sc_place_nb_insert_before(SCNBPLACE *place, SCNBPLACE *oldplace, SCROWLIST *rows)
2187 {
2188 SCROWLIST *row;
2189
2190 place->next = oldplace;
2191 if (oldplace)
2192 {
2193 place->last = oldplace->last;
2194 if (oldplace->last)
2195 oldplace->last->next = place;
2196 oldplace->last = place;
2197 } else
2198 {
2199 place->last = NULL;
2200 }
2201
2202 /* check if row change */
2203 for (row = rows; row; row = row->next)
2204 {
2205 if (row->start == oldplace)
2206 {
2207 if (row->row_num % 2)
2208 {
2209 /* EMPTY */
2210 } else
2211 {
2212 row->start = place;
2213 }
2214 }
2215 if (row->end == oldplace)
2216 {
2217 if (row->row_num % 2)
2218 row->end = place;
2219 }
2220 }
2221 }
2222
2223 /***********************************************************************
2224 Module: Sc_place_nb_insert_after
2225 ------------------------------------------------------------------------
2226 Description:
2227 Insert the indicated place after the indicated second place and
2228 clear up the row markers if necessary.
2229 ------------------------------------------------------------------------
2230 Calling Sequence: Sc_place_nb_insert_after(place, oldplace, rows);
2231
2232 Name Type Description
2233 ---- ---- -----------
2234 place *SCNBPLACE Pointer to place to be inserted.
2235 oldplace *SCNBPLACE Pointer to place to be inserted after.
2236 rows *SCROWLIST Start of list of row markers.
2237 ------------------------------------------------------------------------
2238 */
2239
Sc_place_nb_insert_after(SCNBPLACE * place,SCNBPLACE * oldplace,SCROWLIST * rows)2240 void Sc_place_nb_insert_after(SCNBPLACE *place, SCNBPLACE *oldplace, SCROWLIST *rows)
2241 {
2242 SCROWLIST *row;
2243
2244 place->last = oldplace;
2245 if (oldplace)
2246 {
2247 place->next = oldplace->next;
2248 if (oldplace->next)
2249 oldplace->next->last = place;
2250 oldplace->next = place;
2251 } else
2252 {
2253 place->next = NULL;
2254 }
2255
2256 /* check if row change */
2257 for (row = rows; row; row = row->next)
2258 {
2259 if (row->start == oldplace)
2260 {
2261 if (row->row_num % 2)
2262 row->start = place;
2263 }
2264 if (row->end == oldplace)
2265 {
2266 if (row->row_num % 2)
2267 {
2268 /* EMPTY */
2269 } else
2270 {
2271 row->end = place;
2272 }
2273 }
2274 }
2275 }
2276
2277 /***********************************************************************
2278 Module: Sc_place_nb_rebalance_rows
2279 ------------------------------------------------------------------------
2280 Description:
2281 Check balancing for rows as there has been a change in placement.
2282 ------------------------------------------------------------------------
2283 Callling Sequence: Sc_place_nb_rebalance_rows(rows, place);
2284
2285 Name Type Description
2286 ---- ---- -----------
2287 rows *SCROWLIST Pointer to start of row list.
2288 place *SCPLACE Pointer to global placement structure.
2289 ------------------------------------------------------------------------
2290 */
2291
Sc_place_nb_rebalance_rows(SCROWLIST * rows,SCPLACE * place)2292 void Sc_place_nb_rebalance_rows(SCROWLIST *rows, SCPLACE *place)
2293 {
2294 int max_rowsize;
2295 SCNBPLACE *nplace;
2296
2297 max_rowsize = place->size_rows + (place->avg_size >> 1);
2298 rows->row_size = 0;
2299 for (nplace = rows->start; nplace; nplace = nplace->next)
2300 {
2301 if ((rows->row_num + 1) < place->num_rows &&
2302 (rows->row_size + nplace->cell->size) > max_rowsize)
2303 {
2304 rows = rows->next;
2305 rows->row_size = 0;
2306 if (rows->row_num % 2)
2307 {
2308 rows->end = nplace;
2309 } else
2310 {
2311 rows->start = nplace;
2312 }
2313 }
2314 rows->row_size += nplace->cell->size;
2315 if (rows->row_num % 2)
2316 {
2317 rows->start = nplace;
2318 } else
2319 {
2320 rows->end = nplace;
2321 }
2322 }
2323 }
2324
2325 /***********************************************************************
2326 Module: Sc_place_number_placement
2327 ------------------------------------------------------------------------
2328 Description:
2329 Number the x position of all the cells in their rows.
2330 ------------------------------------------------------------------------
2331 Calling Sequence: Sc_place_number_placement(rows);
2332
2333 Name Type Description
2334 ---- ---- -----------
2335 rows *SCROWLIST Pointer to the start of the rows.
2336 ------------------------------------------------------------------------
2337 */
2338
Sc_place_number_placement(SCROWLIST * rows)2339 void Sc_place_number_placement(SCROWLIST *rows)
2340 {
2341 SCROWLIST *row;
2342 int xpos;
2343 SCNBPLACE *nplace;
2344
2345 for (row = rows; row; row = row->next)
2346 {
2347 xpos = 0;
2348 nplace = row->start;
2349 while (nplace)
2350 {
2351 nplace->xpos = xpos;
2352 xpos += nplace->cell->size;
2353 if (nplace == row->end)
2354 {
2355 break;
2356 }
2357 if (row->row_num % 2)
2358 {
2359 nplace = nplace->last;
2360 } else
2361 {
2362 nplace = nplace->next;
2363 }
2364 }
2365 }
2366 }
2367
2368 /***********************************************************************
2369 Module: Sc_place_show_placement
2370 ------------------------------------------------------------------------
2371 Description:
2372 Print the cells in their rows of placement.
2373 ------------------------------------------------------------------------
2374 Calling Sequence: Sc_place_show_placement(rows);
2375
2376 Name Type Description
2377 ---- ---- -----------
2378 rows *SCROWLIST Pointer to the start of the rows.
2379 ------------------------------------------------------------------------
2380 */
2381
Sc_place_show_placement(SCROWLIST * rows)2382 void Sc_place_show_placement(SCROWLIST *rows)
2383 {
2384 SCROWLIST *row;
2385 SCNBPLACE *inst;
2386
2387 for (row = rows; row; row = row->next)
2388 {
2389 ttyputmsg(M_("For Row #%d, size %d:"), row->row_num, row->row_size);
2390 for (inst = row->start; inst != row->end;)
2391 {
2392 ttyputmsg(x_(" %8d %-s"), inst->xpos, inst->cell->name);
2393 if (row->row_num % 2)
2394 {
2395 inst = inst->last;
2396 } else
2397 {
2398 inst = inst->next;
2399 }
2400 }
2401 ttyputmsg(x_(" %8d %-s"), inst->xpos, inst->cell->name);
2402 }
2403 }
2404
2405 /***********************************************************************
2406 Module: Sc_place_reorder_rows
2407 ------------------------------------------------------------------------
2408 Description:
2409 Clean up the placement rows structure by reversing the pointers
2410 of odd rows and breaking the snake pattern by row.
2411 ------------------------------------------------------------------------
2412 Calling Sequence: Sc_place_reorder_rows(rows);
2413
2414 Name Type Description
2415 ---- ---- -----------
2416 rows *SCROWLIST Pointer to start of row list.
2417 ------------------------------------------------------------------------
2418 */
2419
Sc_place_reorder_rows(SCROWLIST * rows)2420 void Sc_place_reorder_rows(SCROWLIST *rows)
2421 {
2422 SCROWLIST *row;
2423 SCNBPLACE *place, *tplace;
2424
2425 for (row = rows; row; row = row->next)
2426 {
2427 if (row->row_num % 2)
2428 {
2429 /* odd row */
2430 for (place = row->start; place; place =place->next)
2431 {
2432 tplace = place->next;
2433 place->next = place->last;
2434 place->last = tplace;
2435 if (place == row->end)
2436 break;
2437 }
2438 row->start->last = NULL;
2439 row->end->next = NULL;
2440 } else
2441 {
2442 /* even row */
2443 row->start->last = NULL;
2444 row->end->next = NULL;
2445 }
2446 }
2447 }
2448
2449 #endif /* SCTOOL - at top */
2450
2451