1 /*
2 * This file is part of the Alliance CAD System
3 * Copyright (C) Laboratoire LIP6 - D�partement ASIM
4 * Universite Pierre et Marie Curie
5 *
6 * Home page : http://www-asim.lip6.fr/alliance/
7 * E-mail : mailto:alliance-users@asim.lip6.fr
8 *
9 * This progam is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU General Public License as published by the
11 * Free Software Foundation; either version 2 of the License, or (at your
12 * option) any later version.
13 *
14 * Alliance VLSI CAD System is distributed in the hope that it will be
15 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
17 * Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with the GNU C Library; see the file COPYING. If not, write to the Free
21 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22 */
23
24 /*
25 * Tool : BooG - library completion
26 * Date : 2000
27 * Author : Francois Donnet
28 */
29
30
31 #include <stdlib.h>
32 #include <mut.h>
33 #include <mlo.h>
34 #include <abl.h>
35 #include <abe.h>
36 #include "bog_lax_param.h"
37 #include "bog_normalize_ARITY.h"
38 #include "bog_lib_specifications.h"
39 #include "bog_lib_utils.h"
40 #include "bog_lib_cell.h"
41 #include "bog_map_befig.h"
42 #include "bog_map_pattern.h"
43 #include "bog_signal_utils.h"
44 #include "bog_lib_complete.h"
45
46
47 /*to memorize kind of operator: dual cells with different arities*/
48 typedef struct dual{
49 struct dual *NEXT;
50 int OPER; /*oper expected*/
51 int ARITY;
52 cell_list *CELL;
53 cell_list *NEG_CELL; /*negation of expected*/
54 } dual_list;
55
56
57 /*simple operator n1_y, a2_y, a3_y, xor, or, nand3, nxr2 ...*/
58 static cell_list* SIMPLE_OPER;
59
60
61
62 /******************************************************************************/
63 /* add a cell in a sorted list of dual cells */
64 /******************************************************************************/
add_dual(dual_list * top,cell_list * cell)65 static dual_list* add_dual(dual_list* top, cell_list* cell)
66 {
67 dual_list* dual, *pred=NULL, *new;
68
69 /*search place*/
70 for (dual=top; dual; dual=dual->NEXT) {
71 if (dual->ARITY>=ABL_ARITY(cell->ABL)) break;
72 pred=dual;
73 }
74
75 /*insert if possible*/
76 if (dual && dual->ARITY==ABL_ARITY(cell->ABL)) {
77 /*not the operator wanted!*/
78 if (dual->OPER!=ABL_OPER(cell->ABL)
79 && (!dual->CELL || ABL_OPER(cell->ABL)!=ABL_OPER(dual->CELL->ABL))){
80 fprintf(stderr,
81 "add_dual: computing error on cell with oper %s and %s (arity %ld)\n",
82 getabloperuppername(ABL_OPER(cell->ABL)),
83 getabloperuppername(dual->OPER),ABL_ARITY(cell->ABL));
84 exit(1);
85 }
86
87 /*memo new cell*/
88 if (dual->OPER==ABL_OPER(cell->ABL)) {
89 /*if already one take the littlest*/
90 if (!dual->NEG_CELL || cell->AREA<dual->NEG_CELL->AREA)
91 dual->NEG_CELL=cell;
92 }
93 else {
94 /*if already one take the littlest*/
95 if (!dual->CELL || cell->AREA<dual->CELL->AREA)
96 dual->CELL=cell;
97 }
98 return top;
99 }
100
101 new=mbkalloc(sizeof(dual_list));
102 new->NEXT=dual;
103 new->NEG_CELL=NULL;
104 new->CELL=cell;
105 new->ARITY=ABL_ARITY(cell->ABL);
106 switch (ABL_OPER(cell->ABL)) {
107 case ABL_AND: new->OPER=ABL_NAND; break; /*oper expected*/
108 case ABL_NAND: new->OPER=ABL_AND; break;
109 case ABL_OR: new->OPER=ABL_NOR; break;
110 case ABL_NOR: new->OPER=ABL_OR; break;
111 case ABL_XOR: new->OPER=ABL_NXOR; break;
112 case ABL_NXOR: new->OPER=ABL_XOR; break;
113 }
114
115 if (!pred) return new;
116 pred->NEXT=new;
117 return top;
118 }
119
120
121 /******************************************************************************/
122 /* free recursively a list of dual cell */
123 /******************************************************************************/
free_dual(dual_list * top)124 static void free_dual(dual_list* top)
125 {
126 if (!top) return;
127 free_dual(top->NEXT);
128 mbkfree(top);
129 }
130
131
132 /******************************************************************************/
133 /*to improve speed of unflattening algorithm */
134 /*isolate simple operator */
135 /******************************************************************************/
simpleCell(cell_list * cell)136 static void simpleCell(cell_list* cell)
137 {
138 chain_list* abl;
139 cell_list* new, *list;
140
141 /*only pure logic*/
142 if (cell->BIABL) return;
143 /*no constant*/
144 if (ABL_ATOM(cell->ABL)) return;
145
146 /*control all leaves are atomic*/
147 for (abl=ABL_CDR(cell->ABL); abl; abl=ABL_CDR(abl)) {
148 if (!ABL_ATOM(ABL_CAR(abl))) return;
149 /*constant forbidden*/
150 if (ABL_ATOM_VALUE(ABL_CAR(abl))==getablatomone()) return;
151 if (ABL_ATOM_VALUE(ABL_CAR(abl))==getablatomzero()) return;
152 }
153
154 new=copyCell(cell);
155 /*sort list (return NULL if not inserted)*/
156 list=classCell(new,SIMPLE_OPER);
157 if (list) SIMPLE_OPER=list;
158 }
159
160
161 /***************************************************************************/
162 /* return the area of cells matching abl */
163 /***************************************************************************/
addgeneric(chain_list * abl,befig_list * befig,int area,float R,float C,float T)164 static int addgeneric(chain_list *abl, befig_list* befig, int area, float R, float C, float T)
165 {
166 port_list* port;
167 port_list* top;
168 cell_list* cell;
169
170 if ( !abl )
171 {
172 fprintf(stderr,"addgeneric() : NULL pointer\n");
173 exit(1);
174 }
175
176 if (ABL_ATOM(abl)) {
177 if (ABL_ATOM_VALUE(abl)!=getablatomone()
178 && ABL_ATOM_VALUE(abl)!=getablatomzero()) {
179 putgenericT(befig,ABL_ATOM_VALUE(abl),T,T,T,T);
180 putgenericR(befig,ABL_ATOM_VALUE(abl),R,R);
181 putgenericC(befig,ABL_ATOM_VALUE(abl),C);
182 }
183 return area;
184 }
185
186 /*cell->PORT contains the result of pattern matching*/
187 cell=cell_pattern(abl);
188
189 top=copyport(cell->PORT); /*not to be disturb by recursion*/
190
191 for (port=top; port; port=port->NEXT) {
192 if (isvss(port->NAME) || isvdd(port->NAME)) continue;
193 switch (port->DIRECTION) {
194 case OUT: case TRISTATE:
195 /*no delay for output*/
196 break;
197 case IN: case INOUT: case TRANSCV:
198 area=addgeneric(port->ABL, befig, area, R==0?port->R/*gate on top*/:R,
199 port->C /*last gate concerned*/, T + port->T + port->R*C);
200 break;
201 }
202 }
203
204 delport(top);
205
206 return area+cell->AREA;
207 }
208
209
210 /******************************************************************************/
211 /* put the bepor with the leaf of abl */
212 /******************************************************************************/
addinput(befig_list * befig,chain_list * abl)213 static void addinput(befig_list* befig, chain_list *abl)
214 {
215 bepor_list* bepor;
216
217 if (!befig || !abl) {
218 fprintf(stderr,"addinput: NULL pointer\n");
219 exit(1);
220 }
221
222 if (ABL_ATOM(abl)) {
223 if (ABL_ATOM_VALUE(abl)==getablatomone()) return;
224 if (ABL_ATOM_VALUE(abl)==getablatomzero()) return;
225 /*already defined*/
226 for (bepor=befig->BEPOR; bepor; bepor=bepor->NEXT) {
227 if (bepor->NAME==ABL_ATOM_VALUE(abl)) return;
228 }
229 befig->BEPOR=beh_addbepor(befig->BEPOR,ABL_ATOM_VALUE(abl),IN,'B');
230 befig->BERIN=beh_addberin(befig->BERIN,ABL_ATOM_VALUE(abl));
231 return;
232 }
233
234 for (abl=ABL_CDR(abl); abl; abl=ABL_CDR(abl)) {
235 addinput(befig,ABL_CAR(abl));
236 }
237 }
238
239
240 /******************************************************************************/
241 /* return a befig with abl_out for output and without beaux */
242 /* build also a lofig to use as if it was a cell in library */
243 /*when you build a cell with this befig to complete a library, you must put */
244 /*the flag MODE of the cell resulting to 'A' (for later mapping) */
245 /******************************************************************************/
complete_lib(char * name,chain_list * abl_out)246 static befig_list* complete_lib(char* name, chain_list* abl_out)
247 {
248 befig_list* befig;
249 char *out_name;
250 int area;
251 bepor_list* bepor;
252 beaux_list* beaux;
253 bebux_list* bebux;
254 bereg_list* bereg;
255 beout_list* beout;
256
257 if (!name || !abl_out) {
258 fprintf(stderr,"complete_lib: NULL pointer\n");
259 exit(1);
260 }
261
262 name=namealloc(name);
263 befig=beh_addbefig(NULL,name);
264
265 out_name=namealloc("f");
266 befig->BEOUT=beh_addbeout(NULL,out_name,abl_out,NULL);
267
268 /*put arity oper*/
269 put_arity(befig);
270
271 befig->BEPOR=beh_addbepor(befig->BEPOR,VSS,IN,'B');
272 befig->BEPOR=beh_addbepor(befig->BEPOR,VDD,IN,'B');
273 befig->BEPOR=beh_addbepor(befig->BEPOR,out_name,OUT,'B');
274 /*all inputs*/
275 for (beout=befig->BEOUT; beout; beout=beout->NEXT) {
276 addinput(befig,beout->ABL);
277 }
278
279 /*define all signals*/
280 for (bepor=befig->BEPOR; bepor; bepor=bepor->NEXT) putdelay(bepor->NAME,0);
281 for (beaux=befig->BEAUX; beaux; beaux=beaux->NEXT) putdelay(beaux->NAME,0);
282 for (bereg=befig->BEREG; bereg; bereg=bereg->NEXT) putdelay(bereg->NAME,0);
283 for (bebux=befig->BEBUX; bebux; bebux=bebux->NEXT) putdelay(bebux->NAME,0);
284 putdelay(getablatomone(),0);
285 putdelay(getablatomzero(),0);
286
287
288 area=addgeneric(befig->BEOUT->ABL,befig,0,0,0,0);
289 putgenericarea(befig,area);
290
291
292 /*create a lofig*/
293 map_befig(befig,befig->NAME);
294
295 /*undefine all signals not to interfer with work*/
296 for (bepor=befig->BEPOR; bepor; bepor=bepor->NEXT) undefdelay(bepor->NAME);
297 for (beaux=befig->BEAUX; beaux; beaux=beaux->NEXT) undefdelay(beaux->NAME);
298 for (bereg=befig->BEREG; bereg; bereg=bereg->NEXT) undefdelay(bereg->NAME);
299 for (bebux=befig->BEBUX; bebux; bebux=bebux->NEXT) undefdelay(bebux->NAME);
300 undefdelay(getablatomone());
301 undefdelay(getablatomzero());
302
303 return befig;
304 }
305
306
307 /******************************************************************************/
308 /* return a cell with the opposite behave of cell */
309 /******************************************************************************/
complete_neg_lib(cell_list * cell)310 static cell_list* complete_neg_lib(cell_list* cell)
311 {
312 chain_list *out_abl, *abl;
313 char *name;
314 char memo;
315 befig_list *befig, *new;
316
317 if (!cell) {
318 fprintf(stderr,"complete_neg_lib: NULL pointer\n");
319 exit(1);
320 }
321
322 befig=cell->BEFIG;
323
324 if (!befig || !befig->BEOUT || !befig->BEOUT->ABL) {
325 fprintf(stderr,"complete_neg_lib: NULL pointer\n");
326 exit(1);
327 }
328
329 out_abl=createablnotexpr(dupablexpr(befig->BEOUT->ABL));
330
331 memo=SEPAR;
332 SEPAR='_';
333 name=concatname("not",cell->NAME);
334 SEPAR=memo;
335
336 new=complete_lib(name,out_abl);
337
338 abl=dupablexpr(createablnotexpr(befig->BEOUT->ABL)); /* f<= not oper (i) */
339 abl=simpablexpr(abl); /* f<= noper (i) */
340 put_arity_abl(abl);
341
342 /*put in library*/
343 return addCell_logic(new,abl);
344 }
345
346
347 /******************************************************************************/
348 /* return a cell generating XOR */
349 /******************************************************************************/
complete_xor_lib()350 static cell_list* complete_xor_lib()
351 {
352 chain_list *out_abl, *abl1, *abl2, *abl;
353 chain_list *i0, *i1, *ni1, *ni0;
354 befig_list *new;
355
356 i0=createablatom(namealloc("i0"));
357 i1=createablatom(namealloc("i1"));
358 ni0=createablnotexpr(dupablexpr(i0));
359 ni1=createablnotexpr(dupablexpr(i1));
360
361 abl1=createablbinexpr(ABL_NOR,i0,ni1);
362 abl2=createablbinexpr(ABL_NOR,ni0,i1);
363 out_abl=createablbinexpr(ABL_NAND,abl1,abl2);
364
365 /*create befig and lofig*/
366 new=complete_lib(namealloc("xr2_y"),out_abl);
367
368 abl=createablbinexpr(ABL_XOR, createablatom(namealloc("i0")),
369 createablatom(namealloc("i1")));
370
371 put_arity_abl(abl);
372 /*put in library*/
373 return addCell_logic(new,abl);
374 }
375
376
377 /******************************************************************************/
378 /* return a cell generating NXOR */
379 /******************************************************************************/
complete_nxor_lib()380 static cell_list* complete_nxor_lib()
381 {
382 chain_list *out_abl, *abl1, *abl2, *abl;
383 chain_list *i0, *i1, *ni1, *ni0;
384 befig_list *new;
385
386 i0=createablatom(namealloc("i0"));
387 i1=createablatom(namealloc("i1"));
388 ni0=createablnotexpr(dupablexpr(i0));
389 ni1=createablnotexpr(dupablexpr(i1));
390
391 abl1=createablbinexpr(ABL_NOR,i0,ni1);
392 abl2=createablbinexpr(ABL_NOR,ni0,i1);
393 out_abl=createablbinexpr(ABL_AND,abl1,abl2);
394
395 /*create befig and lofig*/
396 new=complete_lib(namealloc("nxr2_y"),out_abl);
397
398 abl=createablbinexpr(ABL_XOR, createablatom(namealloc("i0")),
399 createablatom(namealloc("i1")));
400
401 put_arity_abl(abl);
402 /*put in library*/
403 return addCell_logic(new,abl);
404 }
405
406
407 /******************************************************************************/
408 /* control if there is a NOT, a AND, a OR */
409 /* complete the library if some cells are missing */
410 /******************************************************************************/
control_lib()411 extern void control_lib()
412 {
413 cell_list* not=NULL; /*flag*/
414 cell_list* buff=NULL; /*flag*/
415 cell_list* one=NULL; /*flag*/
416 cell_list* zero=NULL; /*flag*/
417 dual_list* or=NULL;
418 dual_list* and=NULL;
419 dual_list* xor=NULL;
420 dual_list* dual;
421 cell_list* cell;
422 int arity;
423
424 for (cell=getcell_logic_lib(); cell; cell=cell->NEXT) {
425 simpleCell(cell); /*build SIMPLE_OPER variable*/
426 if (ABL_ATOM(cell->ABL)) {
427 if (ABL_ATOM_VALUE(cell->ABL)==getablatomone()) one=cell;
428 else if (ABL_ATOM_VALUE(cell->ABL)==getablatomzero()) zero=cell;
429 else buff=cell;
430 }
431 }
432
433 for (cell=SIMPLE_OPER; cell; cell=cell->NEXT) {
434 switch ABL_OPER(cell->ABL) {
435 case ABL_AND: case ABL_NAND: and=add_dual(and,cell); break;
436 case ABL_NOR: case ABL_OR: or=add_dual(or,cell); break;
437 case ABL_XOR: case ABL_NXOR: xor=add_dual(xor,cell); break;
438 case ABL_NOT: not=cell; break;
439 default:
440 fprintf(stderr,"control_lib: unknow oper %ld\n",
441 ABL_OPER(cell->ABL));
442 exit(1);
443 }
444 }
445
446 if (!one) {
447 fprintf(stderr,
448 "Mapping Warning: 'ONE' constant cell is missing in library\n");
449 }
450 if (!zero) {
451 fprintf(stderr,
452 "Mapping Warning: 'ZERO' constant cell is missing in library\n");
453 }
454 if (!not) {
455 fprintf(stderr,"Library Error: 'NOT' cell is missing in library\n");
456 exit(1);
457 }
458
459 if (!or) {
460 fprintf(stderr,"Library Error: 'OR' cell is missing in library\n");
461 exit(1);
462 }
463 else if (or->ARITY!=2) {
464 fprintf(stderr,
465 "Library Error: 'OR 2' is missing in library\n");
466 exit(1);
467 }
468
469 if (!and) {
470 fprintf(stderr,"Library Error: 'AND' cell is missing in library\n");
471 exit(1);
472 }
473 else if (and->ARITY!=2) {
474 fprintf(stderr,
475 "Library Error: 'AND 2' is missing in library\n");
476 exit(1);
477 }
478
479 if (xor && xor->ARITY!=2) {
480 fprintf(stderr,
481 "Library Error: 'XOR 2' is missing in library\n");
482 exit(1);
483 }
484
485 arity=2;
486 for (dual=and; dual; dual=dual->NEXT) {
487 if (!dual->NEG_CELL) {
488 fprintf(stderr,
489 "Mapping Warning: a '%s%d' is missing in cell library...Generating\n",
490 getabloperuppername(dual->OPER), dual->ARITY);
491 /*build a buffer with 2 inverters*/
492 cell=complete_neg_lib(dual->CELL);
493 if (cell) {
494 cell->MODE='A'; /*doesn't really exist in lib*/
495 simpleCell(cell); /*build SIMPLE_OPER variable*/
496 }
497 }
498 arity++;
499 }
500
501 arity=2;
502 for (dual=or; dual; dual=dual->NEXT) {
503 if (!dual->NEG_CELL) {
504 fprintf(stderr,
505 "Mapping Warning: a '%s%d' is missing in cell library...Generating\n",
506 getabloperuppername(dual->OPER), dual->ARITY);
507 /*build a buffer with 2 inverters*/
508 cell=complete_neg_lib(dual->CELL);
509 if (cell) {
510 cell->MODE='A'; /*doesn't really exist in lib*/
511 simpleCell(cell); /*build SIMPLE_OPER variable*/
512 }
513 }
514 arity++;
515 }
516
517 arity=2;
518 for (dual=xor; dual; dual=dual->NEXT) {
519 if (!dual->NEG_CELL) {
520 fprintf(stderr,
521 "Mapping Warning: a '%s%d' is missing in cell library...Generating\n",
522 getabloperuppername(dual->OPER), dual->ARITY);
523 /*build a buffer with 2 inverters*/
524 cell=complete_neg_lib(dual->CELL);
525 if (cell) {
526 cell->MODE='A'; /*doesn't really exist in lib*/
527 simpleCell(cell); /*build SIMPLE_OPER variable*/
528 }
529 }
530 arity++;
531 }
532
533 /*if buffer doesn't exist, build*/
534 if (!buff) {
535 fprintf(stderr,
536 "Mapping Warning: a buffer is missing in cell library...Generating\n");
537 /*build a buffer with 2 inverters*/
538 cell=complete_neg_lib(not);
539 if (cell) {
540 cell->MODE='A'; /*doesn't really exist in lib*/
541 simpleCell(cell); /*build SIMPLE_OPER variable*/
542 }
543 }
544
545 /*if xor doesn't exist, build*/
546 if (xor == NULL) {
547 fprintf(stderr,
548 "Mapping Warning: 'xor' is missing in cell library...Generating\n");
549 cell=complete_xor_lib();
550 if (cell) {
551 cell->MODE='A'; /*doesn't really exist in lib*/
552 simpleCell(cell); /*build SIMPLE_OPER variable*/
553 }
554 cell=complete_nxor_lib();
555 if (cell) {
556 cell->MODE='A'; /*doesn't really exist in lib*/
557 simpleCell(cell); /*build SIMPLE_OPER variable*/
558 }
559 }
560
561 free_dual(xor);
562 free_dual(and);
563 free_dual(or);
564 }
565
566
567 /***************************************************************************/
568 /* return the list of simple oper of the library */
569 /***************************************************************************/
getcell_oper_lib()570 extern cell_list* getcell_oper_lib()
571 {
572 return SIMPLE_OPER;
573 }
574
575
576
577
578
579